Probably Approximately Correct Constrained Learning

Introduction

Learning has become a core component of the modern information systems we increasingly rely upon to select job candidates, analyze medical data, and control “smart” applications (home, grid, city). As these systems become ubiquitous, so does the need to curtail their behavior. Left untethered, they can fail catastrophically as evidenced by the growing number of reports involving biased, prejudiced models or systems prone to tampering (e.g., adversarial examples), unsafe behaviors, and deadly accidents . Typically, learning is constrained by using domain expert knowledge to either construct models that embed the required properties (see, e.g., ) or tune the training objective so as to promote them (see, e.g., ). The latter approach, known as regularization, is ubiquitous in practice even though it need not yield feasible solutions . In fact, existing results from classical learning theory guarantee generalization with respect to the regularized objective, which says nothing about meeting the requirements it may describe . While the former approach guarantees that the solution satisfies the requirements, the scale and opacity of modern machine learning (ML) systems render this model design impractical.

Since ML models are often trained using empirical risk minimization (ERM), an alternative solution is to explicitly add constraints to these optimization problems. Since requirements are often expressed as constraints in the first place, this approach overcomes the need to tune regularization parameters. What it more, any solution automatically satisfies the requirements. Nevertheless, this approach suffers from two fundamental drawbacks. First, its involves solving a constrained optimization problem that is non-convex for typical parametrizations (e.g., neural networks). Though gradient descent can often be used to obtain good minimizers for differentiable models, it does not guarantee constraint satisfaction. Indeed, there is typically no straightforward way to project onto the feasibility set (e.g., the set of fair classifiers) and strong duality need not hold for non-convex programs . Second, even if we could solve this constrained ERM, the issue remains of how its solutions generalize since classical learning theory is involved only with unconstrained problems .

In this work, we address these issues in two steps. We begin by formalizing the concept of constrained learning using the probably approximately correct (PAC) framework. We prove that any hypothesis class that is unconstrained learnable is constrained learnable and that the constrained counterpart of the ERM rule is a PAC constrained learner. Hence, we establish that, from a learning theoretic perspective, constrained learning is as hard as unconstrained (classical) learning. This, however, does not resolve the practical issue of learning under requirements due to the non-convexity of the constrained ERM problem. To do so, we proceed by deriving an empirical saddle-point problem that is a (representation-independent) PAC constrained learner. We show that its approximation error depends on the richness of the parametrization and the difficulty of satisfying the learning constraints. Finally, we put forward practical constrained learning algorithm that we use to illustrate how constrained learning can address problems involving fairness and robustness.

Related work

Central to ML is the concept of ERM in which statistical quantities are replaced by their empirical counterparts, thus allowing learning problems to be solved from data, without prior knowledge of its underlying distributions. The set of conditions under which this is a sensible approach is known in learning theory as (agnostic) PAC learnability. More generally, the PAC framework formalizes what it means to solve a statistical learning problem and studies when it can be done . While different learning models, such as structured complexity and PAC-Bayes, have been proposed, they are beyond the scope of this work.

The objects studied in (PAC) learning theory, however, are unconstrained statistical learning problem. Yet, there is a growing need to enable learning under constraints to tackle problems in fairness , robustness , safety , and semi-supervised learning , to name a few. While constraints have been used in statistics since Neyman-Pearson , generalization guarantees for constrained learning have been studied only in specific contexts, e.g., for coherence constraints or rate-constrained learning . Additionally, due to the non-convexity of typical learning problems, many of these results hold for randomized solutions, e.g., . In contrast, this work puts forward a formal constrained learning framework in which generalization results are derived for deterministic learners. A first step in that direction was taken in , albeit from an optimization perspective. This work also accounts for pointwise constraints, fundamental in the context of fairness, and provides a practical, guaranteed constrained learning algorithm (Sec. 5.2).

Due to these challenges, learning under requirements is often tackled using regularization, i.e., by integrating a fixed cost for violating the constraints into the training objective (see, e.g., ). Selecting these costs, however, can be challenging, especially as the number of constraints grows. In fact, their values often depend on the problem instance, the objective value, and can interact in non-trivial ways . In the case of convex optimization problems, a straightforward relation between constraints and regularization costs can be obtained due to strong duality. A myriad of primal-dual methods can then be used to obtain optimal, feasible solutions . However, most modern parametrizations (e.g., CNNs) lead to non-convex programs for which a regularized formulation need not yield feasible solutions, all the more so good ones . While primal-dual algorithms have been used in practice, no guarantees can be given for their outcome in general .

Constrained Learning

is at the core of virtually all of modern ML .

Before tackling if and how we can learn under constraints, i.e., whether we can solve (P-CSL), we illustrate what constrained learning can enable. To make the discussion concrete, we present two constrained formulations of the learning problems we solve in Section 6.

Invariance and fair learning. Constrained learning is a natural way to formulate learning problems in which invariance is required. Consider a model $\phi$ whose output is a discrete distribution over $k$ possible classes. Then, (P-CSL) can be used to write

where $\rho$ is an input transformation we wish the model to be invariant to and $c>0$ determines the sensitivity level. Formulation (PII) can be extended trivially to multiple transformations (see Sec. 6). When the average invariance in (PII) is not enough, a stricter, pointwise requirement can be imposed, by using

For instance, fairness can be seen as a form of invariance in which $\rho$ induces an alternative distribution of a certain protected variable (e.g., a gender change) . In this case, the constraint in (PII) is related to the average causal effect (ACE) and (1) to counterfactual fairness . While fairness goes beyond invariance, our goal is not to litigate the merit of any fairness metrics, but to show how constrained learning may provide a natural way to encode them.

Robust learning. Another issue affecting ML models, especially CNNs, is robustness. It is straightforward to construct small input perturbations that lead to misclassification and there are now numerous methods to do so. While adversarial training has empirically been shown to improve robustness, it often results in classifiers with poor nominal performance . In , a constrained formulation involving an upper bound on the worst-case error was used to tackle this issue. Similarly, we can address this compromise using (P-CSL) by writing

where $\mathfrak{A}$ is an adversarial data distributions. What is more, we can soften the worst-case requirements of robust optimization by taking $\mathfrak{A}\mid\varepsilon$ to be a distribution of adversarials with perturbation at most $\varepsilon$ and pose a prior on $\varepsilon$ (e.g., an exponential). This results in classifiers whose performance degrades smoothly with the perturbation magnitude. The theory and algorithms developed in this work give generalization guarantees on solutions of this problem obtained using samples of $\mathfrak{A}$, which can be accessed based on, e.g., adversarial attacks (Sec. 6). In other words, it establishes conditions under which a classifier that is accurate and robust during training is also accurate and robust during testing.

Probably Approximately Correct Constrained Learning

While (P-CSL) clearly addresses many of the issues discussed in Sec. 1, we cannot expect to solve it exactly without access to the $\mathfrak{D}_{i}$ against which expectations are evaluated. Additionally, solving the variational (P-CSL) is challenging unless $\mathcal{H}$ is finite. In this section, we address the first matter by settling, as in classical learning theory, on obtaining a good enough solution (Sec. 4.1). We then show that these solutions are not “harder” to get in constrained learning than they were in unconstrained learning (Sec. 4.2). We then proceed to tackle the algorithmic challenges by deriving and analyzing a practical constrained learning algorithm (Sec. 5.2).

Let us begin by defining what it means to learn under constraints. To do so, we start by looking at the unconstrained case, which is addressed in learning theory under the PAC framework .

A classical result states that $\mathcal{H}$ is PAC learnable if and only if it has finite VC dimension and that the $\phi^{\dagger}$ from Def. 1 can be obtained by solving an ERM problem . This is, however, not enough to enable constrained learning since a PAC $\phi^{\dagger}$ may not be feasible for (P-CSL). In fact, feasibility often takes priority over performance in constrained learning problems. For instance, regardless of how good a fair classifier is, it serves no “fair” purpose in practice unless it meets fairness requirements [see, e.g., (PII)]. These observations lead us to the following definition.

A hypothesis class $\mathcal{H}$ is probably approximately correct constrained (PACC) learnable if for every $\epsilon,\delta\in(0,1)$ and every distribution $\mathfrak{D}_{i}$, $i=0,\dots,m+q$, a $\phi^{\dagger}\in\mathcal{H}$ can be obtained based $N\geq N_{\mathcal{H}}(\epsilon,\delta)$ samples from each $\mathfrak{D}_{i}$ such that it is, with probability $1-\delta$,

where $\mathcal{K}_{j}\subseteq\mathcal{X}\times\mathcal{Y}$ are sets of $\mathfrak{D}_{j}$ measure at least $1-\epsilon$.

Note that every PACC learnable class is also PAC learnable since it satisfies (2). However, a PACC learner must also meet the probably approximate feasibility conditions in (3). The additional “C” in PACC is used to remind ourselves of this fact. Next, we show that the converse is also true, i.e., that PAC and PACC learning are equivalent problems.

2 PACC Learning is as Hard as PAC Learning

Having formalized what we mean by constrained learning (Sec. 4.1), we turn to the issue of when it can be done. To do so, we follow the unconstrained learning lead and put forward an empirical constrained risk minimization (ECRM) rule using $N_{i}$ samples $(\bm{x}_{n_{i}},y_{n_{i}})\sim\mathfrak{D}_{i}$, namely

Notice that (P-ECRM) is a constrained version of the classical ERM problem that is ubiquitous in the solution of unconstrained learning problems . The next theorem shows that, under mild assumptions on the losses, if $\mathcal{H}$ is PAC learnable, then it is PACC learnable using (P-ECRM).

then any solution $\hat{\phi}^{\star}$ of (P-ECRM) is a PACC solution of (P-CSL).

While no formal connection can be drawn between (PIV) and its regularized formulation (due to the lack of strong duality ), its dual problem turns out to be related to (P-CSL). In the sequel, we prove that it provides (near-)PACC solutions for (P-CSL) with an approximation error in (2) that depends on the richness of the parametrization and how strict the learning constraints are (Sec. 5.1). In fact, we show that it is a (near-)PACC learner even if the parametrization is PAC learnable but $\mathcal{H}$ is not. Based on this result, we obtain a practical constrained learning algorithm (Sec. 5.2) that we use to solve the problems formulated in Sec. 3.

A (Near-)PACC Learning Algorithm

In this section, we derive a practical constrained learning algorithm by first analyzing the dual problem of (PIV) (Sec. 5.1) and then proposing an algorithm to solve it (Sec. 5.2). Although we know this dual problem is not related to (PIV), we prove that it is related directly to the original constrained learning problem (P-CSL) by showing it is a PACC learner except for an approximation error determined by the quality of the parametrization. We formalize this concept as follows:

In Def. 3, $\epsilon_{0}$ characterizes the approximation error. In contrast to unconstrained learning, however, this error cannot be separated from the learning problem due to the constraints. Still, it is fixed, i.e., it is independent of the sample set, and affects neither the sample complexity nor the constraint satisfaction. Hence, the parametrized constrained learner sacrifices optimality, but not feasibility, which remains dependent only on the number of samples $N$ (Def. 2). Finally, observe that the sample complexity does not depend on the original hypothesis class $\mathcal{H}$, but on the parametrized $\mathcal{P}$. Near-PACC is therefore related to representation-independent learning .

We begin by analyzing the gap between (P-CSL) and its (parametrized) empirical dual problem. Define the (parametrized) empirical Lagrangian of (P-CSL) as

Note that ($\widehat{\textup{D}}$-CSL) is the dual problem of the parametrized ECRM (PIV). However, due to its non-convexity, its holds only that $\hat{D}^{\star}\leq\hat{P}^{\star}_{\theta}$ and, in general, a saddle-point of ($\widehat{\textup{D}}$-CSL) is not related to a solution of (PIV) . Still, ($\widehat{\textup{D}}$-CSL) can be related directly to (P-CSL), which is why we refer to it as its empirical dual. This relation obtains under the following assumptions:

The main result of this section is collected in the following theorem.

Let $d_{\mathcal{P}}$ be the VC dimension of $\mathcal{P}$. Under Assumptions 1–3, ($\widehat{\textup{D}}$-CSL) is a near-PACC learner of $\mathcal{H}$ with $N_{\mathcal{P}}=C\zeta^{-1}(\epsilon,\delta,d_{\mathcal{P}})$, for an absolute constant $C$ and $\zeta^{-1}$ as in (4), and

where $(\bm{\mu}_{p}^{\star},\bm{\lambda}_{p}^{\star})$ are dual variables of (P-CSL) with constraints $c_{i}-M\nu$ for $i=1,\dots,m+q$.

Thus, the approximation error incurred by using the parametrization $f_{\bm{\theta}}$ is affected by (i) the difficulty of the learning problem and (ii) the richness of the parametrization. Indeed, under Assumptions 1–3, (P-CSL) is a strongly dual functional problem whose dual variables have a well-known sensitivity interpretation [66, Sec. 5.6]. So the bracketed quantity in (6) quantifies how stringent the learning constraints are in terms of how much performance could be gained by relaxing them. In addition, $\epsilon_{0}$ is affected by the approximation capability $\nu$ of the parametrization. Since better parametrizations typically involve more parameters, which in turn affects the VC dimension of $\mathcal{P}$, a typical compromise between the approximation error and complexity arises. For small sample sets, the generalization error in Def. 3 is dominated by the estimation error $\epsilon$, which improves for lower complexity classes. If there is abundance of data or the learning requirements are particularly stringent, the approximation error $\epsilon_{0}$ dominates and more accurate, even if more complex, parametrizations should be used.

Note that the dual variables $(\bm{\mu}_{p}^{\star},\bm{\lambda}_{p}^{\star})$ may be hard to evaluate since they are related to a version of the statistical problem (P-CSL). While their norms can be estimated using classical results from optimization theory (see, e.g., ), they often lead to loose, uninformative bounds. Notice, however, that only $\epsilon$ depends on the sample size.

2 A Primal-Dual near-PACC Learner

We now proceed to introduce a practical algorithm to solve ($\widehat{\textup{D}}$-CSL) based on a (sub)gradient primal-dual method. To do so, start by noting that the outer maximization is a convex optimization program. Indeed, the dual function $\hat{d}(\bm{\mu},\bm{\lambda}_{j})=\min_{\bm{\theta}}\hat{L}(\bm{\theta},\bm{\mu},\bm{\lambda}_{j})$ is the pointwise minimum of a set of affine functions and is therefore always concave . Additionally, its (sub)gradients can be easily computed by evaluating the constraint slacks at the minimizer of $\hat{L}$ [51, Ch. 3]. Hence, the main challenge in ($\widehat{\textup{D}}$-CSL) is the inner minimization.

Despite the Lagrangian (5) often being non-convex in $\bm{\theta}$, ($\widehat{\textup{D}}$-CSL) is an unconstrained optimization problem. Hence, contrary to (PIV), it is often the case that good minimizers can be found, especially for differentiable losses and parametrizations (i.e., most common ML models). For instance, there is ample empirical and theoretical evidence that gradient descent can learn to good parameters for (C)NNs . In that vein, we thus assume that we have access to the following oracle:

Assumption 4 essentially states that we are able to (approximately) train regularized unconstrained learners using the parametrization $f_{\bm{\theta}}$. We can alternate between minimizing the Lagrangian (5) with respect to $\bm{\theta}$ for fixed $(\bm{\mu},\bm{\lambda}_{j})$ and updating the dual variables using the resulting minimizer. This procedure is summarized in Algorithm 1 and analyzed in the following theorem:

Fix $\beta>0$ and consider Algorithm 1 with at least $C\zeta^{-1}(\epsilon,\delta,d_{\mathcal{P}})$ samples from each $\mathfrak{D}_{j}$, where $C$ is an absolute constant, $\zeta^{-1}$ is as in (4), and $d_{\mathcal{P}}$ is the VC dimension of $\mathcal{P}$. Under Assumptions 1–4, Algorithm 1 converges to the neighborhood

with probability $1-\delta$ after at most $T=O(1/\beta)$ for $\epsilon_{0}$ as in (6) and S=O\big{(}B^{2}\big{)}.

Theorem 3 bounds the suboptimality of Algorithm 1 with respect to the original learning problem (P-CSL). The size of this neighborhood depends polynomially on $\epsilon_{0}$, $\epsilon$, the oracle quality $\rho$, and the step size $\eta$. The number of iterations needed to reach this neighborhood is inversely proportional to the desired accuracy $\beta$. It is worth noting that this result applies to the deterministic outputs $(\bm{\theta}^{(T)},\bm{\mu}^{(T)},\bm{\lambda}_{j}^{(T)})$ of Algorithm 1 after convergence and not to a randomized solution obtained by sampling from $(\bm{\theta}^{(t)},\bm{\mu}^{(t)},\bm{\lambda}_{j}^{(t)})$, $t=0,\dots,T$ as in .

Underlying the oracle in Assumption 4 is often an iterative procedure, e.g., gradient descent, and the cost of running this procedure until convergence to obtain an approximate minimizer can be prohibitive. A common option then is to alternately update the primal variable $\bm{\theta}^{(t)}$ and the dual variables $(\bm{\mu}^{(t)},\bm{\lambda}_{j}^{(t)})$. This primal-dual method leads in fact to a classical convex optimization algorithm . While the convergence guarantee of Theorem 3 no longer holds in this case, we observe good results by performing the primal and dual updates at different timescales, e.g., by performing step 3 once per epoch. This is exactly what we do in the next section where we illustrate the usefulness of this constrained learner.

Numerical experiments

Due to space constraints, we only provide highlights of the results obtained for the problems from Section 3. For more details and additional experiments, see Appendix D.

Invariance and fair learning. In the Adult dataset , our goal is to predict whether an individual makes more than US$50,000.00 while being insensitive to gender. If left unconstrained, a small, one-hidden layer NN would change predictions on around$8\%$of the test samples had their genders been reversed (Fig. 1a). For step 3 of Algorithm 1, we use ADAM with batch size$128$and learning rate$0.1$. All other parameters were kept as in the original paper. After each epoch, we update the dual variables (step 4), also using ADAM with a step size of$0.01$. All classifiers were trained over$300$ epochs.

When constrained using the pointwise (1), the classifier becomes insensitive to the protected variable in over $99\%$ of the test set. In such simple cases, invariant classifiers can be easily obtained by masking the training samples, although it can bring fairness issues of its own . But Algorithm 1 provides more than an invariant classifier. Due to the bound on the duality gap between (P-CSL) and ($\widehat{\textup{D}}$-CSL), the dual variables have a sensitivity interpretation: the larger their value, the harder the constraint is to satisfy . If we analyze the $20\%$ of individuals with largest $\lambda_{n}$ (Fig. 1b), we find that a significantly higher prevalence of non-white, non-US natives, married individuals. Clearly, while attempting to control for gender invariance, the constrained learner also had to overcome other prejudices correlated to sexism, a well-known challenge in fair classification . Similar results can be derived when controlling for racial bias in the COMPAS dataset.

To overcome this issue, we use PGD to sample from a hypothetical “adversarial distribution” $\mathfrak{A}$ and constrain the performance of the solution against $\mathfrak{A}$ as in (PIII). To accelerate training, we use a much weaker attack running PGD without restarts for only $5$ steps with step size $\varepsilon/3$. Notice that, as we increase $\varepsilon$, the model becomes increasingly more robust at the cost of nominal performance. Still, the performance degradation remains abrupt. As we argued before, smoother degradation can be obtained by training against a distribution of magnitudes, e.g., the one in Figure 2b. Doing so not only yields better performances under perturbation as well as a small loss of nominal accuracy.

Conclusion

We put forward a theory of learning under requirements by extending the PAC framework to constrained learning. We then prove that unconstrained and constrained learnability are equivalent by showing that a constrained version of the classical ERM rule is a PACC learner. To overcome the challenges in solving the optimization problem underlying this learner, we derive an alternative learner based on a parametrized empirical dual problem. We show that its approximation error is related to the richness of the parametrization as well as the difficulty of meeting the learning constraint and use it to propose a practical algorithm to learn under requirements. We expect that these generalization results can be used to theoretically ground techniques used in practice to address constrained learning problems beyond fairness and robustness. In particular, similar arguments can be used to develop a constrained theory for reinforcement learning . We also believe that these results can be extended to non-convex losses using recent results on the strong duality of certain non-convex variational problems .

Broader Impact

As learning becomes an ubiquitous technological solution and begins to affect real societal impact, its shortcomings become more evident. A growing number of reports show that its solutions can be prejudiced and prone to tampering or unsafe behaviors . Constrained learning allows requirements to be imposed during learning, so that the models and solutions obtained are guaranteed to behave in the desired way despite being learned fully from data. This work provides a framework under which to study learning under requirements and shows how and when it can be done. By providing generalization guarantees on the solutions, it enables learning to be used in critical applications in which there is little tolerance for failure. Naturally, solutions learned under constraints are not necessarily safe or fair. How the learning problem is formulated, i.e., which constraints are imposed, play a definite role on these outcomes and policies determining such requirements can be (and indeed are ) important sources of biases.

Acknowledgments and Disclosure of Funding

This work is supported by ARL DCIST CRA W911NF-17-2-0181.

References

Appendix A Proof of Theorem 1

Start by noticing from the definition of PACC learnability [more specifically, from (2) in Def. 2] that any PACC learnable class $\mathcal{H}$ is necessarily PAC learnable.

To prove the converse, recall that if $\mathcal{H}$ is PAC learnable, then $\mathcal{H}$ has finite VC dimension [19, Sec. 3.4]. More precisely, for $N>C\zeta^{-1}(\epsilon,\delta,d_{\mathcal{H}})$, where $C$ is an absolute constant and $\zeta^{-1}$ is as in (4), and any bounded function $g$ it holds with probability $1-\delta$ that

To show (9) implies that $\hat{\phi}^{\star}$ is a probably approximately feasible, note that we can write, using (8),

each of which hold with probability $1-\delta$ over the samples $(\bm{x}_{n_{i}},y_{n_{i}})$ as long as $N_{i}>C\zeta^{-1}(\epsilon,\delta,d_{\mathcal{H}})$. Combining (9) and (10) we conclude that, with probability $1-(m+q)\delta$, it holds simultaneously that

where each $\mathcal{K}_{j}$ is a set of $\mathfrak{D}_{j}$-measure at least $1-\epsilon$.

Hence, if $\mathcal{H}$ is PAC learnable, then there exists $N$ such that, if $\hat{\phi}^{\star}$ is a solution of (P-ECRM) obtained using $N_{i}\geq N$ samples from each $\mathfrak{D}_{i}$, then $\hat{\phi}^{\star}$ is probably approximately optimal as in (2) and probably approximately feasible as in (3). $\square$

Appendix B Proof of Theorem 2

As we have argued before, we cannot rely on the duality between (PIV) and ($\widehat{\textup{D}}$-CSL) to obtain this result because of its non-convexity. Hence, this proof proceeds directly from (P-CSL) by applying three transformations that yield ($\widehat{\textup{D}}$-CSL), but whose approximation and estimation errors can be controlled. First, we obtain the dual problem of (P-CSL) and show that this transformation incurs in no error. This stems from the convexity of (P-CSL) under Assumptions 1 and 2 and is a straightforward strong duality result from semi-infinite programming theory (Proposition 1). Second, we approximate the function class $\mathcal{H}$ using the finite dimensional parametrization $f_{\bm{\theta}}$ and bound the approximation error $\epsilon_{0}$ (Proposition 2). Third, we obtain ($\widehat{\textup{D}}$-CSL) by replacing the expectations with their empirical versions. Since the problem is now unconstrained, we can use classical learning theory to evaluate the estimation error $\epsilon$ (Proposition 3). We then combine these results to obtain Theorem 2.

Explicitly, we begin by defining the Lagrangian of (P-CSL) as

Assumptions 1–3 imply that (P-CSL) is strongly dual:

Under Assumptions 1–3, the semi-infinite program (P-CSL) and the saddle-point problem (D-CSL) are strongly dual, i.e., $P^{\star}=D^{\star}$.

Start by noticing that (P-CSL) can be equivalently formulated as

In fact, both problem have the same objective function and feasibility set. Indeed, if $\mathfrak{D}>0$, the transformation in the pointwise constraints is vacuous. On the other hand, when $\mathfrak{D}$ vanishes, the constraint is not enforced in (PV). However, neither is it in (P-CSL) since the pointwise constraint need not hold on sets of $\mathfrak{D}$-measure zero. Note that this is different from satisfying the constraint with probability $\mathfrak{D}$.

From Assumptions 1 and 2 we obtain that (PV) is a semi-infinite convex program. What is more, Assumption 3 implies it has a strictly feasible solution $\phi^{\prime}=f_{\bm{\theta}^{\prime}}$. This constraint qualification, sometimes known as Slater’s condition, implies that is strongly dual, i.e., that $P^{\star}=D^{\star}$ . ∎

Since $\mathcal{P}\subseteq\mathcal{H}$ (Assumption 2), it is clear that $D_{\nu}^{\star}\geq D^{\star}=P^{\star}$. Yet, if the parametrization is rich enough, we should expect the gap $D_{\nu}^{\star}-P^{\star}$ to be small. This intuition is formalized in the following proposition.

Let $\bm{\theta}^{\star}$ achieve the saddle-point in ($\textup{D}_{\nu}$-CSL). Under Assumptions 1–3, $f_{\bm{\theta}^{\star}}$ is a feasible, near-optimal solution of (P-CSL). Explicitly,

B.2 The estimation gap

All that remains, is to turn the statistical Lagrangian (11) into the empirical (5). The incurred estimation error is described in the next proposition.

Let $\bm{{\hat{\theta}^{\star}}}$ achieve the saddle-point in ($\widehat{\textup{D}}$-CSL) and for $\delta>0$, let

where $d_{\mathcal{P}}$ is the VC dimension of the parametrized class $\mathcal{P}$. Under Assumptions 1–3, it holds with probability $1-\delta$ over the samples drawn from the distributions $\mathfrak{D}_{i}$ that

where $\mathcal{K}_{j}\subseteq\mathcal{X}\times\mathcal{Y}$ is a set of $\mathfrak{D}_{j}$-measure at least $1-\zeta(N_{j})$ for all $j=m+1,\dots,m+q$.

B.3 The PACC solution

The proof concludes by combining the parametrization and estimation gap results from Propositions 2 and 3. Namely, notice that (15) and (16) imply that the minimizer $\hat{\bm{\theta}}^{\star}$ that achieves the saddle-point in ($\widehat{\textup{D}}$-CSL) is probably approximately feasible [see (3)] for (P-CSL). Then, combining (12) and (14) using the triangle inequality yields the near-PACC gap from Def. 3. Fixing $N$ such that $B\zeta(N)\leq\epsilon$ yields the result in Theorem 2. $\square$

B.4 Proof of Proposition 2: The Approximation Gap

We first prove that $f_{\bm{\theta}^{\star}}$ is feasible for (P-CSL) and then bound the gap between $D^{\star}_{\nu}$ and $P^{\star}$.

where we used the fact that $\mu_{i}\geq 0$ and $\lambda_{j}\geq 0$ $\mathfrak{D}_{j}$-a.e. Hence, it must be that $f_{\bm{\theta}^{\star}}$ is feasible for (P-CSL).

Near-optimality.

First, recall that under Assumptions 1–3, (P-CSL)–(D-CSL) form a strongly dual pair of mathematical programs (Proposition 1). For the Lagrangian in (11), we therefore obtain the saddle-point relation

Immediately, we obtain the lower bound in (12). Explicitly,

where the second inequality comes from the fact that $\mathcal{P}\subseteq\mathcal{H}$ (Assumption 2).

The upper bound is obtained by relating the parameterized dual problem ($\textup{D}_{\nu}$-CSL) to a perturbed (tightened) version of the original (P-CSL). To do so, start by adding and subtracting $L(\phi,\bm{\mu},\bm{\lambda})$ from ($\textup{D}_{\nu}$-CSL) to get

To bound the last expectation in (21), we first use Hölder’s inequality to get

Using (22) and (23), together with the approximation property of the class $\mathcal{H}$ (Assumption 2), we upper bound the minimum over $\bm{\theta}$ in (21) to obtain

Notice that since (24) holds uniformly for all $\phi\in\mathcal{H}$, it also holds for the minimizer

where we recognize the optimization problem of

Under Assumptions 1–3, (PVI) is also strongly dual (Proposition 1), so that

Going back to (25) we can now conclude the proof. First, use (27) to obtain

B.5 Proof of Proposition 3: The Estimation Gap

The proof follows by first showing that $\bm{{\hat{\theta}^{\star}}}$ must be feasible for the parametrized ECRM (PIV) using the same argument as in Sec. (B.4). We then proceed as in the proof of Theorem 1.

Formally, suppose there exists at least one $i>0$ such that

Then, since $\bm{\mu}$ and $\bm{\lambda}_{j}$ are unbounded above, we obtain that $\hat{D}^{\star}\to+\infty$. However, Assumptions 1 and 3 imply that $\hat{D}^{\star}<+\infty$. Indeed, consider the empirical dual function

hold with probability $1-\delta$ over the datasets $\{(\bm{x}_{n_{i}}),y_{n_{i}})\}_{i}$ for $\zeta$ as in (13). Combining (31) and (32) and using the union bound, we conclude that, with probability $1-(m+q)\delta$,

where $\mathcal{K}_{j}$ is a set of $\mathfrak{D}_{j}$-measure at least $1-\zeta(N_{j})$.

Near-optimality.

Let $(\bm{\theta}_{\nu}^{\star},\bm{\mu}_{\nu}^{\star},\bm{\lambda}_{\nu}^{\star})$ and $(\bm{{\hat{\theta}^{\star}}},\bm{{\hat{\mu}^{\star}}},\bm{{\hat{\lambda}^{\star}}})$ be variables that achieve $D_{\nu}^{\star}$ in ($\textup{D}_{\nu}$-CSL) and $\hat{D}^{\star}$ in ($\widehat{\textup{D}}$-CSL) respectively. Then, it holds that

known as complementary slackness conditions. While these are part of the classical KKT conditions [66, Sec. 5.5.3], it should be noted that the non-convex nature of both ($\textup{D}_{\nu}$-CSL) and ($\widehat{\textup{D}}$-CSL) implies that these are only necessary and not sufficient for optimality. Nevertheless, feasibility is enough to establish (33).

Indeed, recall from Proposition 2 and (31) that the constraint slacks in parentheses in (33) are non-positive. Hence, the left-hand sides in (33) are also non-positive and if (33a) does not hold for some $i$ or if (33b) does not hold for some $j$ and a set $\mathcal{Z}_{j}$ of positive $\mathfrak{D}_{j}$ measure, then letting $\mu_{\nu,i}^{\star}=0$ or making $\lambda_{j}(\bm{x},y)$ vanish over $\mathcal{Z}_{j}$ would increase the value of $D_{\nu}^{\star}$, contradicting its optimality. Note that since $\mathcal{Z}_{j}$ is measurable, the modified $\lambda_{j}$ would still be measurable. A similar argument applies to (33c) and (33d).

Immediately, (33) implies that both ($\textup{D}_{\nu}$-CSL) and ($\widehat{\textup{D}}$-CSL) reduce to

To proceed, use the optimality of $\bm{\theta}_{\nu}^{\star}$ and $\bm{\theta}$ for $F_{0}$ and $\hat{F}_{0}$ respectively to write

and applying the VC generalization bound from [19, Sec. 3.4] to (35), yields that, uniformly over $\bm{\theta}$,

with probability $1-\delta$ and for $\zeta$ as in (4). Combining (35) and (36) concludes the proof. $\square$

Appendix C Proof of Theorem 3

In this appendix, we prove the following quantitative version of Theorem 3:

Fix $\beta>0$ and consider Algorithm 1 with at least $C\zeta^{-1}(\epsilon,\delta,d_{\mathcal{P}})$ samples from each $\mathfrak{D}_{j}$, where $C$ is an absolute constant, $\zeta^{-1}$ is as in (4), and $d_{\mathcal{P}}$ is the VC dimension of $\mathcal{P}$. Under Assumptions 1–4, Algorithm 1 converges to a probably approximately feasible solution and

with probability $1-\delta$ after $T$ steps for $\epsilon_{0}$ as in (6),

where $U_{0}$ is the distance to a pair of optimal dual variables at the beginning of the algorithm, namely,

for $(\bm{\mu}^{\star},\bm{\lambda}_{j}^{\star})$ solutions of ($\widehat{\textup{D}}$-CSL).

from which we obtain (37) by recalling that $\hat{D}^{\star}$ is near-PACC (Theorem 2). More precisely, by using Propositions 2 and 3.

Start by defining the empirical dual function

The upper bound in (40) then holds trivially from the fact that $\hat{d}(\bm{\mu},\bm{\lambda}_{j})\leq\hat{D}^{\star}$ for all $(\bm{\mu},\bm{\lambda}_{j})$. Then, from the characteristics of the approximate minimizer $\bm{\theta}^{(t)}=\bm{\theta}^{\dagger}(\bm{\mu}^{(t)},\bm{\lambda}^{(t)})$ in Assumption 4 we obtain that

For the lower bound, we rely on the following relaxation of Dankin’s classical theorem [51, Ch. 3]:

Let $\bm{\theta}^{\dagger}$ be the approximate minimizer of the empirical Lagrangian (5) at $(\bm{\mu},\bm{\lambda}_{j})$ from Assumption 4. Then, the constraint slacks are approximate subgradients of the dual function (41), i.e.,

for all $(\bm{\mu}^{\prime},\bm{\lambda}_{j}^{\prime})$.

Additionally, we can upper bound (44) by replacing the optimal minimizer in $d(\bm{\mu}^{\prime},\bm{\lambda}_{j}^{\prime})$ by any $\bm{\theta}$. In particular, we can choose $\bm{\theta}^{\dagger}(\bm{\mu},\bm{\lambda}_{j})$ to get

Notice from (5) that the first term of the Lagrangians in (45) are identical. By expanding them, (45) can then be rearranged as in (43). ∎

To proceed, let $(\bm{\mu}^{\star},\bm{\lambda}_{j}^{\star})$ be solutions of the dual problem ($\widehat{\textup{D}}$-CSL). We show next that for at least $T=O(1/\beta)$, the total distance

decreases by at least $O(\beta)$. To do so, use the updates from Algorithm 1 to write (46) as

Since both $\bm{\mu}^{\star}$ and $\bm{\lambda}^{\star}$ belong to the non-negative orthant, we can then use the non-expansiveness of the projection $[\cdot]_{+}$ to obtain

By expanding the norms in (47), we get that

What is more, Lemma 1 can be used to bound the second term in (48) and write

where we used the fact that \hat{D}^{\star}=\hat{d}\big{(}\bm{\mu}^{\star},\bm{\lambda}_{j}^{\star}\big{)}. Solving the recursion then yields

To conclude, notice that $\hat{d}(\bm{\mu},\bm{\lambda}_{j})\leq\hat{D}^{\star}$ for all $(\bm{\mu},\bm{\lambda}_{j})$. Hence, when $\bm{\mu}^{(t)}$ and $\bm{\lambda}_{j}^{(t)}$ are sufficiently far from the optimum and the step size $\eta$ is sufficiently small, we have $\Delta_{t}\leq 0$ and (49) shows that the distance to the optimum $U_{t}$ decreases. Formally, fix a precision $\beta>0$ and let $T=\min\{t\mid\Delta_{t}>-\beta\}$. Then, from the definition of $\Delta_{t}$ we obtain the desired lower bound

Appendix D Numerical experiments: additional details

We begin with our analysis of the Adult dataset , in which our goal is to predict whether an individual makes more than US$50,000.00 while being insensitive to gender. The transformations performed on the data are listed in Table 1. We use a neural network with two outputs and a single hidden-layer with 64 nodes using a sigmoidal activation function. The output is encoded into a probability using a softmax transformation ($f_{\bm{\theta}}:\mathcal{X}\to^{2}$). Using this parametrization, we then pose the constrained learning problem

Without the constraint in (PVII), the resulting classifier is quite sensitive to gender: its prediction would changes for approximately $8\%$ of the test samples if their gender were reversed (Figure 3). With the pointwise constraint, the classifier becomes insensitive to the protected variable in $99.9\%$ of the test set, which is on the order of $1/\sqrt{N}\approx 0.008$. While the less strict ACE can also be imposed, it leads to slightly more sensitive classifiers (for $c=5\times 10^{-4}$, the classifier changes prediction in $0.2\%$ of the test set).

As we mention in the main text, due to the bound on the duality gap, the dual variables of (PVII) obtained in Algorithm 1 have a sensitivity interpretation: the larger their value, the harder the constraint is to satisfy . Almost $96\%$ of the dual variables are zero after convergence, meaning that the constraint was tight for only $4\%$ of the individuals. In Figure 4a, we show the distribution of $\lambda>0$ over the Adult training set. If we analyze the group with the largest dual variables (the $80\%$ percentile to be exact), we find a significantly higher prevalence of married individuals, non-white, non-US natives, and with a Masters degree (Figure 4b). Clearly, while attempting to control for gender invariance, the constrained learner also had to overcome other prejudices correlated to sexism in the dataset.

This situation even clearer in the COMPAS dataset. Here, the goal is to predict recidivism based on an individual’s past offense data (see Table 2 for details on the data processing). We use the same neural network as before trained over $400$ iterations using a similar procedure, but with batch size $256$, primal learning rate $0.1$, and dual variables learning rate $2$ (halved every 50 iterations). Unconstrained, it reaches an accuracy of almost $70\%$, but is sensitive to both gender, race, and gender $\times$ race (Table 3). By including ACE constraints on these counterfactuals, we obtain a classifier that is now invariant to these variables.

Once again, the value of the dual variables capture insights into the different forms of biases existing in the dataset (Figure 5). If we do not include constraints on the cross-term counterfactuals, then the hardest constraint to satisfy is the gender-invariant one. Invariance to the Caucasian-Hispanic and Hispanic:Other counterfactuals is effectively “implied” by the other constraints, since their dual variables vanish. If we include all $13$ counterfactuals, i.e., add the cross-terms between gender and race, then the cross-terms dominate the satisfaction difficulty, with the Male/Female $\times$ African-American/Caucasian dichotomy dominating over all others. What is interesting, however, is that the dual variable for the African-American/Caucasian counterfactual does not vanish, indicating the existence of a gender-independent race bias in the dataset. This does not occur with other combinations of the race factor. This type of combinatorial (gerrymandering) fairness is a serious challenge in fair classification .

D.2 Robust learning

Although adversarial training has been successfully used to train robust ML models, it often leads to solutions with poor nominal performance, i.e., poor performance on original, clean data . To overcome this issue, poses a constrained learning that explicitly trades-off nominal performance and performance against a worst-case perturbation. They propose an algorithm that optimizes over an upper bound of this robust constraint, leading to solutions that are simultaneously accurate on clean data and robust against input perturbations. Here, we follow a similar lead, but pose the problem as in (PIII) for a given adversarial distribution $\mathfrak{A}$ instead of optimizing of the worst possible one. This distribution can then be tailored to provide a smooth performance degradation instead of a worst-case robustness one.

A first attempt is then to use PGD with $\varepsilon=0.04$ to sample from a hypothetical adversarial distribution and constrain its performance against that distribution as in (PIII). Though the adversarial distribution is now dependent on the model $\phi$, by using a smaller learning rate for the dual variables, $\phi$ can be considered almost static for the dual update and we have observed no instability issues in practice. To accelerate training, we use a much weaker attack running PGD without restarts for only $5$ steps with step size $\varepsilon/3$. Notice from Figure 6a that when training against $\varepsilon=0.04$ ($c=0.4$), the resulting classifier trades-off nominal performance (now $88\%$) for adversarial performance (now $85\%$). However, as the strength of the attack increases, the performance of the classifier deteriorates abruptly: for $\varepsilon=0.08$, it is down to $9\%$. Increasing the training adversarial strength to $\varepsilon=0.1$ ($c=0.7$) yields a more robust classifier, albeit at the cost of a lower nominal accuracy ($84.6\%$). Still, the performance degradation remains quite abrupt.

This issue can be fixed by training against using a hierarchical adversarial distribution. Explicitly, we build the adversarial distribution $\mathfrak{A}$ as

where $\Pr\left(\mathfrak{A}\mid\varepsilon\right)$ is induced by an adversarial attack of magnitude at most $\varepsilon$ (in our case, PGD) and $\Pr\left(\varepsilon\right)$ denotes a prior distribution on the magnitude of the attacks. In Figure 6a we take $\varepsilon\sim 0.25\times\textup{Beta}(3,8)$ (Figure 6b). Notice that even though the mean value of the perturbation is approximately $0.07$, the resulting classifier has a nominal performance close to $87\%$ and retains a $67\%$ accuracy for perturbations of magnitude up to $0.12$.