text:
\begin{document}
\maketitle

\begin{abstract}

As learning solutions reach critical applications in social, industrial, and medical domains, the need to curtail their behavior has become paramount. There is now ample evidence that without explicit tailoring, learning can lead to biased, unsafe, and prejudiced solutions. To tackle these problems, we develop a generalization theory of constrained learning based on the probably approximately correct~(PAC) learning framework. In particular, we show that imposing requirements does not make a learning problem harder in the sense that any PAC learnable class is also PAC \emph{constrained} learnable using a constrained counterpart of the empirical risk minimization~(ERM) rule. For typical parametrized models, however, this learner involves solving a constrained non-convex optimization program for which even obtaining a feasible solution is challenging. To overcome this issue, we prove that under mild conditions the empirical dual problem of constrained learning is also a PAC constrained learner that now leads to a practical constrained learning algorithm based solely on solving unconstrained problems. We analyze the generalization properties of this solution and use it to illustrate how constrained learning can address problems in fair and robust classification.

\end{abstract}

\section{Introduction}
\label{S:intro}

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~\cite{Datta15a, Kay15u, Angwin16m, NationalTransportationSafetyBoard18h, Dastin18a, Bright16t}. Typically, learning is constrained by using domain expert knowledge to either construct models that \emph{embed} the required properties~(see, e.g.,~\cite{Ronneberger15u, Cohen16g, Marcos17r, Henriques17w, Sabour17d, Weiler18l, Ruiz20i}) or \emph{tune} the training objective so as to promote them~(see, e.g.,~\cite{Chen14a, Berk17a, Xu18a, Ravi19e}). The latter approach, known as regularization, is ubiquitous in practice even though it need not yield feasible solutions~\cite{Bertsekas09c}. 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~\cite{Vapnik00t, Shalev-Shwartz04u}. 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~\cite{Bertsekas09c}. 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~\cite{Vapnik00t, Shalev-Shwartz04u}.

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, \emph{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.

\section{Related work}
\label{S:related}

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~\cite{Valiant84a, Haussler92d, Vapnik00t, Shalev-Shwartz04u}. 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~\cite{Goh16s, Kusner17c, Agarwal18a, Donini18e, Kearns18p, Zafar19f, Cotter19o},
robustness~\cite{Madry18t, Sinha18c, Zhang19t},
safety~\cite{Kalogerias18r, Vitt18r, Garcia15a, Achiam17c, Paternain19l},
and semi-supervised learning~\cite{Nguyen08i, Cour11l, Yu17m},
to name a few. While constraints have been used in statistics since Neyman-Pearson~\cite{Neyman33i}, generalization guarantees for constrained learning have been studied only in specific contexts, e.g., for coherence constraints or rate-constrained learning~\cite{Garg01l, Goh16s, Agarwal18a, Cotter19o}. Additionally, due to the non-convexity of typical learning problems, many of these results hold for randomized solutions, e.g., \cite{Goh16s, Kearns18p, Agarwal18a, Cotter19o}. 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~\cite{Chamon20t}, 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.~\ref{S:algorithm}).

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.,~\cite{Goodfellow14e, Berk17a, Xu18a, Zhao18t, Sinha18c, Ravi19e}). 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~\cite{Ehrgott05m, Miettinen98n, Messac03t, Mueller-Gritschneder09a, Schaul19r}. 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~\cite{Bertsekas15c}. 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~\cite{Bertsekas09c}. While primal-dual algorithms have been used in practice, no guarantees can be given for their outcome in general~\cite{Huang15l, Madry18t, Shaham18u, Zhang19t}.

\section{Constrained Learning}
\label{S:csl}

Let~$\fkD_i$, $i = 0,\dots,m+q$, denote \emph{unknown} probability distributions over the space of data pairs~$(\bx,y)$, with~$\bx \in \calX \subset \setR^d$ and~$y \in \calY \subset \setR$. For a hypothesis class~$\calH$ of functions~$\phi: \calX \to \setR^k$, define the generic constrained statistical learning~(CSL) problem as

\begin{prob}[\textup{P-CSL}]\label{P:csl}
	P^\star = \min_{\phi \in \calH}&
		&&\E_{(\bx,y) \sim \fkD_0} \!\Big[ \ell_0\big( \phi(\bx),y \big) \Big]
	\\
	\subjectto& &&\E_{(\bx,y) \sim \fkD_i} \!\Big[ \ell_i\big( \phi(\bx),y \big) \Big] \leq c_i
		\text{,} &&i = 1,\ldots,m
		\text{,}
	\\
	&&&\ell_j\big( \phi(\bx),y \big) \leq c_j
		\quad \fkD_j\text{-a.e.}
		\text{,} &&j = m+1,\ldots,m+q
		\text{,}
\end{prob}

where~$\ell_i: \setR^k \times \calY \to \setR$ are performance metrics. In general, we think of~$\fkD_0$ as a nominal joint distribution over data pairs~$(\bx,y)$ corresponding to feature vectors~$\bx$ and responses~$y$. The additional~$\fkD_i$ can be used to model different conditional distributions over which requirements are imposed either on average, through the losses~$\ell_i$, $i \leq m$, or pointwise, through the losses~$\ell_j$, $j > m$. Note that the unconstrained version of~\eqref{P:csl}, namely

\begin{prob}\label{P:sl}
	P_\text{U}^\star = \min_{\phi\in\calH}&
		&&\E_{(\bx,y) \sim \fkD_0} \Big[ \ell_0\big( \phi(\bx),y \big) \Big]
		\text{,}
\end{prob}

is at the core of virtually all of modern ML~\cite{Friedman01t, Shalev-Shwartz04u}.

Before tackling \emph{if} and \emph{how} we can learn under constraints, i.e., whether we can solve~\eqref{P:csl}, we illustrate \emph{what} constrained learning can enable. To make the discussion concrete, we present two constrained formulations of the learning problems we solve in Section~\ref{S:sims}.

\textbf{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, \eqref{P:csl} can be used to write

\begin{prob}\label{P:invariance}
	\minimize_{\phi\in\calH}&
		&&\E_{(\bx,y) \sim \fkD} \!\Big[ \ell_0\big( \phi(\bx),y \big) \Big]
	\\
	\subjectto& &&\E_{(\bx,y) \sim \fkD} \!\Big[
		\dkl\! \Big( \phi(\bx) \,\Vert\, \phi\big(\rho(\bx)\big) \Big) \Big] \leq c
		\text{,}
\end{prob}

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

\begin{equation}\label{E:invariance_pointwise}
	\dkl\! \Big( \phi(\bx) \,\Vert\, \phi\big(\rho(\bx)\big) \Big) \leq c
		\quad \fkD\text{-a.e.}
		\text{.}
\end{equation}

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)~\cite{Goh16s, Kusner17c, Agarwal18a, Donini18e, Zafar19f, Cotter19o}. In this case, the constraint in \eqref{P:invariance} is related to the average causal effect~(ACE) and~\eqref{E:invariance_pointwise} to \emph{counterfactual fairness}~\cite{Kusner17c}. 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.

\textbf{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~\cite{Szegedy14i, Goodfellow14e, Huang15l, Madry18t, Sinha18c, Shaham18u}. In~\cite{Zhang19t}, 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~\eqref{P:csl} by writing

\begin{prob}\label{P:robustness}
	\minimize_{\phi\in\calH}&
		&&\E_{(\bx,y) \sim \fkD} \!\Big[ \ell_0\big( \phi(\bx),y \big) \Big]
	\\
	\subjectto& &&\E_{(\bx,y) \sim \fkA} \!\Big[ \ell_0\big( \phi(\bx),y \big) \Big] \leq c
\end{prob}

where~$\fkA$ is an adversarial data distributions. What is more, we can soften the worst-case requirements of robust optimization by taking~$\fkA \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~$\fkA$, which can be accessed based on, e.g., adversarial attacks~(Sec.~\ref{S:sims}). In other words, it establishes conditions under which a classifier that is accurate and robust during training is also accurate and robust during testing.

\section{Probably Approximately Correct Constrained Learning}
\label{S:full_pacc}

While~\eqref{P:csl} clearly addresses many of the issues discussed in Sec.~\ref{S:intro}, we cannot expect to solve it exactly without access to the~$\fkD_i$ against which expectations are evaluated. Additionally, solving the variational~\eqref{P:csl} is challenging unless~$\calH$ is finite. In this section, we address the first matter by settling, as in classical learning theory, on obtaining a \emph{good enough} solution~(Sec.~\ref{S:pacc}). We then show that these solutions are not ``harder'' to get in constrained learning than they were in unconstrained learning~(Sec.~\ref{S:pacc_csl}). We then proceed to tackle the algorithmic challenges by deriving and analyzing a practical constrained learning algorithm~(Sec.~\ref{S:algorithm}).

\subsection{From PAC to PACC}
\label{S:pacc}

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~\cite{Valiant84a, Haussler92d, Vapnik00t, Shalev-Shwartz04u}.

\begin{definition}[PAC learnability]\label{D:pac}

A hypothesis class~$\calH$ is~\emph{(agnostic) probably approximately correct~(PAC)} learnable if for every~$\epsilon, \delta \in (0,1)$ and every distribution~$\fkD_0$, a~$\phi^\dagger \in \calH$ can be obtained from~$N \geq N_\calH(\epsilon,\delta)$ samples of~$\fkD_0$ such that~$\E \big[ \ell_0\big( \phi^\dagger(\bx),y \big) \big] \leq P_\textup{U}^\star + \epsilon$ with probability~$1-\delta$.

\end{definition}

A classical result states that~$\calH$ is PAC learnable if and only if it has finite VC dimension and that the~$\phi^\dagger$ from Def.~\ref{D:pac} can be obtained by solving an ERM problem~\cite{Vapnik00t, Shalev-Shwartz04u}. This is, however, not enough to enable constrained learning since a PAC~$\phi^\dagger$ may not be feasible for~\eqref{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., \eqref{P:invariance}]. These observations lead us to the following definition.

\begin{definition}[PACC learnability]\label{D:pacc}

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

\begin{enumerate}[1)]
	\item approximately optimal, i.e.,

	\begin{equation}\label{E:pacc_optimal}
		\E_{(\bx,y) \sim \fkD_0}
			\!\big[ \ell_0\big( \phi^\dagger(\bx),y \big) \big] \leq P^\star + \epsilon
			\quad \text{and}
	\end{equation}

	\item approximately feasible, i.e.,

	\begin{subequations}\label{E:pacc_feasible}
	\begin{alignat}{2}
		\E_{(\bx,y) \sim \fkD_i} \!\big[ \ell_i\big( \phi^\dagger(\bx),y \big) \big]
			&\leq b_i + \epsilon
			\text{,} &&i = 1,\dots,m
			\text{,}
		\\
		\ell_j\big( \phi^\dagger(\bx),y \big)
			&\leq b_j
			\text{,} \ \ \text{for all } (\bx,y) \in \calK_j
			\text{,} \quad &&j = m+1,\dots,m+q
			\text{,}
	\end{alignat}
	\end{subequations}

	where~$\calK_j \subseteq \calX \times \calY$ are sets of~$\fkD_j$ measure at least~$1-\epsilon$.
\end{enumerate}

\end{definition}

Note that every PACC learnable class is also PAC learnable since it satisfies~\eqref{E:pacc_optimal}. However, a PACC learner must also meet the probably approximate feasibility conditions in~\eqref{E:pacc_feasible}. 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.

\subsection{PACC Learning is as Hard as PAC Learning}
\label{S:pacc_csl}

Having formalized what we mean by constrained learning~(Sec.~\ref{S:pacc}), 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~$(\bx_{n_i},y_{n_i}) \sim \fkD_i$, namely

\begin{prob}[\textup{P-ECRM}]\label{P:ecrm}
	\hat{P}^\star = \min_{\phi \in \calH}&
		&&\frac{1}{N_0} \sum_{n_0 = 1}^{N_0} \ell_0\big( \phi(\bx_{n_0}), y_{n_0} \big)
	\\
	\subjectto& &&\frac{1}{N_i} \sum_{n_i = 1}^{N_i} \ell_i\big( \phi(\bx_{n_i}), y_{n_i} \big)
		\leq c_i
		\text{,} &&i = 1,\ldots,m
	\\
	&&&\ell_j\big( \phi(\bx_{n_j}), y_{n_j} \big) \leq c_j
	\text{, for all } n_j
		\text{,} &&j = m+1,\ldots,m+q
		\text{.}
\end{prob}

Notice that~\eqref{P:ecrm} is a constrained version of the classical ERM problem that is ubiquitous in the solution of unconstrained learning problems~\cite{Friedman01t, Shalev-Shwartz04u}. The next theorem shows that, under mild assumptions on the losses, if~$\calH$ is PAC learnable, then it is PACC learnable using~\eqref{P:ecrm}.

\begin{theorem}\label{T:pacc_ecrm}

Let the~$\ell_i$, $i = 0,\dots,m+q$, be bounded on~$\calX$. The hypothesis class~$\calH$ is PACC learnable if and only if it is PAC learnable and~\eqref{P:ecrm} is a PACC learner of~$\calH$. Explicitly, let~$d_\calH < \infty$ be the VC dimension of~$\calH$. If~$N_i \geq C \zeta^{-1}(\epsilon,\delta,d_\calH)$, $i = 0,\dots,m+q$, for an absolute constant~$C$ and

\begin{equation}\label{E:zeta}
	\zeta^{-1}(\epsilon,\delta,d) = \frac{d + \log(1/\delta)}{\epsilon^2}
		\text{,}
\end{equation}

then any solution~$\hat{\phi}^\star$ of~\eqref{P:ecrm} is a PACC solution of~\eqref{P:csl}.

\end{theorem}

\begin{proof}
See Appendix~
\ifappend \ref{X:pacc_ecrm}.\else A in the extended version~\cite{Chamon20p}.\fi
\end{proof}

Theorem~\ref{T:pacc_ecrm} shows that, from a learning theoretic point-of-view, constrained learning is as hard as unconstrained learning. Not only that, but notice the sample complexity of constrained described by~\eqref{E:zeta} matches that of PAC learning~\cite{Vapnik00t, Shalev-Shwartz04u}. It is therefore not surprising that a constrained version of ERM is a PACC learner. A similar result appeared in~\cite{Donini18e} for a particular rate constraint and not in the context of PACC learning. Still, solving~\eqref{P:ecrm} remains challenging. Indeed, while it addresses the statistical issue of~\eqref{P:csl}, it remains, in most practical cases, an infinite dimensional~(functional) problem. This issue is often addressed by leveraging a finite dimensional parametrization of~(a subset of)~$\calH$, such as a kernel model or a (C)NN. Explicitly, we associate to each parameter vector~$\btheta \in \setR^p$ a function~$f_{\btheta} \in \calH$, replacing~\eqref{P:ecrm} by

\begin{prob}\label{P:ecrm_parametrized}
	\hat{P}_\theta^\star = \min_{\btheta \in \setR^p}&
		&&\frac{1}{N_0} \sum_{n_0 = 1}^{N_0} \ell_0\big( f_{\btheta}(\bx_{n_0}), y_{n_0} \big)
	\\
	\subjectto& &&\frac{1}{N_i} \sum_{n_i = 1}^{N_i} \ell_i\big( f_{\btheta}(\bx_{n_i}), y_{n_i} \big)
		\leq c_i
		\text{,} &&i = 1,\ldots,m
	\\
	&&&\ell_j\big( f_{\btheta}(\bx_{n_j}), y_{n_j} \big) \leq c_j
	\text{, for all } n_j
		\text{,} &&j = m+1,\ldots,m+q
		\text{.}
\end{prob}

Even if~\eqref{P:ecrm} is a convex program in~$\phi$, \eqref{P:ecrm_parametrized} typically is not a convex program in~$\btheta$~(except, e.g., if the losses are convex and~$f_{\btheta}$ is linear in~$\btheta$). This issue also arises in unconstrained learning problems, but is exacerbated by the presence of constraints. Though it is sometimes possible to find good approximate minimizers of~$\ell_0$ using, e.g., gradient descent rules~\cite{Zhang16u, Arpit17a, Ge17l, Brutzkus17g, Soltanolkotabi18t}, even obtaining a feasible~$\btheta$ may be challenging. Indeed, although good CNN classifiers can be trained using gradient descent, obtaining a good \emph{fair/robust} classifier is considerably harder. Regularized formulations are often used to sidestep this issue by incorporating a linear combination of the constraints into the objective and solving the resulting unconstrained problem~\cite{Goodfellow14e, Berk17a, Xu18a, Zhao18t, Sinha18c, Ravi19e}. Nevertheless, whereas the generalization guarantees of classical learning theory apply to this modified objective, they say nothing of the requirements it describes. Since strong duality need not hold for the non-convex~\eqref{P:ecrm_parametrized}, this procedure need not be PACC~(Def.~\ref{D:pacc}) and may lead to solutions that are either infeasible or whose performance is unacceptably poor~\cite{Bertsekas09c}.

While no formal connection can be drawn between~\eqref{P:ecrm_parametrized} and its regularized formulation~(due to the lack of strong duality~\cite{Bertsekas09c}), its dual problem turns out to be related to~\eqref{P:csl}. In the sequel, we prove that it provides (near-)PACC solutions for~\eqref{P:csl} with an approximation error in~\eqref{E:pacc_optimal} that depends on the richness of the parametrization and how strict the learning constraints are~(Sec.~\ref{S:ecrm_dual}). In fact, we show that it is a (near-)PACC learner even if the parametrization is PAC learnable but~$\calH$ is not. Based on this result, we obtain a practical constrained learning algorithm~(Sec.~\ref{S:algorithm}) that we use to solve the problems formulated in Sec.~\ref{S:csl}.

\section{A (Near-)PACC Learning Algorithm}
\label{S:near_pacc}

In this section, we derive a practical constrained learning algorithm by first analyzing the dual problem of~\eqref{P:ecrm_parametrized}~(Sec.~\ref{S:ecrm_dual}) and then proposing an algorithm to solve it~(Sec.~\ref{S:algorithm}). Although we know this dual problem is not related to~\eqref{P:ecrm_parametrized}, we prove that it is related directly to the original constrained learning problem~\eqref{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:

\begin{definition}[Near-PACC learnability]\label{D:near_pacc}

A class~$\calH$ is \emph{(near-)PACC} learnable through a class~$\calP$ if there exists an~$\epsilon_0 > 0$ such that for every~$\epsilon, \delta \in (0,1)$ and every distribution~$\fkD_i$, $i = 0,\dots,m+q$, an approximately feasible~$\phi^\dagger \in \calP$~[viz.~\eqref{E:pacc_feasible}] can be obtained with probability~$1-\delta$ based on~$N \geq N_\calP(\epsilon,\delta)$ samples from each~$\fkD_i$ and~$\E_{(\bx,y) \sim \fkD_0}\!\big[ \ell_0\big( \phi^\dagger(\bx),y \big) \big] \leq P^\star + \epsilon_0 + \epsilon$

\end{definition}

In Def.~\ref{D:near_pacc}, $\epsilon_0$ characterizes the \emph{approximation error}. In contrast to unconstrained learning, however, this error cannot be separated from the learning problem due to the constraints. Still, it is \emph{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.~\ref{D:pacc}). Finally, observe that the sample complexity does not depend on the original hypothesis class~$\calH$, but on the parametrized~$\calP$. Near-PACC is therefore related to representation-independent learning~\cite{Shalev-Shwartz04u}.

\subsection{The Empirical Dual Problem of~(\ref{P:csl})}
\label{S:ecrm_dual}

We begin by analyzing the gap between~\eqref{P:csl} and its~(parametrized) empirical dual problem. Define the~(parametrized) empirical Lagrangian of~\eqref{P:csl} as

\begin{equation}\label{E:empirical_lagrangian}
\begin{aligned}
	\hat{L}(\btheta, \bmu, \blambda_j) &=
		\frac{1}{N_0} \sum_{n_0 = 1}^{N_0} \ell_0\big( f_{\btheta}(\bx_{n_0}), y_{n_0} \big)
		+ \sum_{i = 1}^m \mu_i \left[ \frac{1}{N_i} \sum_{n_i = 1}^{N_i}
			\ell_i\big( f_{\btheta}(\bx_{n_i}), y_{n_i} \big) - c_i \right]
		\\
		{}&+ \sum_{j = m+1}^{m+q} \left[ \frac{1}{N_j} \sum_{n_j = 1}^{N_j}
			\lambda_{j,n_j} \left( \ell_j\big( f_{\btheta}(\bx_{n_j}), y_{n_j} \big) - c_j \right)
		\right]
		\text{,}
\end{aligned}
\end{equation}

where~$\bmu \in \setR^m_+$ collects the dual variables~$\mu_i$ relative to the average constraints and~$\blambda_j \in \setR^{N_j}_+$ collects the dual variables~$\lambda_{j,n_j}$ relative to the~$j$-th pointwise constraint. The empirical dual problem of~\eqref{P:csl} is then written as

\begin{equation}\label{P:csl_empirical_dual}
	\hat{D}^\star = \max_{\substack{\bmu \in \setR^m_+,\ \blambda_j \in \setR^{N_j}_+}}\
		\min_{\btheta \in \setR^p} \hat{L}(\btheta, \bmu, \blambda_j)
		\text{,}
		\tag{$\widehat{\textup{D}}$\textup{-CSL}}
\end{equation}

Note that~\eqref{P:csl_empirical_dual} is the dual problem of the parametrized ECRM~\eqref{P:ecrm_parametrized}. 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~\eqref{P:csl_empirical_dual} is not related to a solution of~\eqref{P:ecrm_parametrized}~\cite{Bertsekas09c}. Still, \eqref{P:csl_empirical_dual} can be related directly to~\eqref{P:csl}, which is why we refer to it as its empirical dual. This relation obtains under the following assumptions:

\begin{assumption}\label{A:losses}
	The losses~$\ell_i(\cdot,y)$, $i = 0,\dots,m+q$, are~$[0,B]$-valued, $M$-Lipschitz, convex functions for all~$y \in \calY$. The loss~$\ell_0$ is additionally strongly convex.
\end{assumption}

\begin{assumption}\label{A:parametrization}
	The hypothesis class~$\calH$ is convex, the parametrized~$\calP = \{f_{\btheta} \mid \btheta \in \setR^p\} \subseteq \calH$ is PAC learnable, and there is~$\nu > 0$ such that for each~$\phi \in \calH$ there exists~$f_{\btheta} \in \calP$ for which~$\sup_{\bx \in \calX} \abs{f_{\btheta}(\bx)-\phi(\bx)} \leq \nu$.
\end{assumption}

\begin{assumption}\label{A:slater}
	There exists~$\btheta^\prime \in \setR^p$ such that~$f_{\btheta^\prime}$ is strictly feasible for~\eqref{P:csl} with constraints~$c_i - M \nu$ and~$c_j - M \nu$ and for each datasets~$\calS = \big\{ (\bx_{n_i},y_{n_i}) \big\}_{i = 0,\dots,m+q}$ there exists a~$\btheta^{\prime\prime}$ that is strictly feasible for~\eqref{P:ecrm_parametrized}.
\end{assumption}

In contrast to the unconstrained learning setting or the ECRM result in Theorem~\ref{T:pacc_ecrm}, we require that the losses~$\ell_i$ and the hypothesis class~$\calH$ be convex. This, however, does not imply that~\eqref{P:csl_empirical_dual} or~\eqref{P:ecrm_parametrized} are convex problems since~$\ell_i(f_{\btheta}(\bx),y)$ need not be convex in~$\btheta$. Additionally, only the parametrized class~$\calP$ is required to be PAC learnable. Hence, $\calH$ can be the space of continuous functions or a reproducing kernel Hilbert space~(RKHS) and~$f_{\btheta}$ can be a neural network~\cite{Cybenko89a, Hornik89m, Hornik91a} or a finite linear combinations of kernels~\cite{Berlinet11r, Micchelli05l}, both of which meet the uniform approximation assumption. This assumption can also be relaxed in the absence of pointwise constraints~(Remark~\ref{R:no_pointwise}). Assumption~\ref{A:slater} guarantees that the problem is well-posed, i.e., a feasible solution for~\eqref{P:csl} can be found in~$\calP$.

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

\begin{theorem}\label{T:pacc_csl}

Let~$d_\calP$ be the VC dimension of~$\calP$. Under Assumptions~\ref{A:losses}--\ref{A:slater}, \eqref{P:csl_empirical_dual} is a near-PACC learner of~$\calH$ with~$N_\calP = C \zeta^{-1}(\epsilon,\delta,d_\calP)$, for an absolute constant~$C$ and~$\zeta^{-1}$ as in~\eqref{E:zeta}, and

\begin{equation}\label{E:epsilon0}
	\epsilon_0 = \left( 1 + \norm{\bmu_p^\star}_1 + \norm{\blambda_p^\star}_{L_1} \right) M \nu
		\text{,}
\end{equation}

where~$(\bmu_p^\star,\blambda_p^\star)$ are dual variables of~\eqref{P:csl} with constraints~$c_i - M \nu$ for~$i = 1,\dots,m+q$.

\end{theorem}

\begin{proof}

See Appendix~
\ifappend \ref{X:main}.\else B in the extended version~\cite{Chamon20p}.\fi

\end{proof}

Thus, the approximation error incurred by using the parametrization~$f_{\btheta}$ is affected by (i)~the difficulty of the learning problem and (ii)~the richness of the parametrization. Indeed, under Assumptions~\ref{A:losses}--\ref{A:slater}, \eqref{P:csl} is a strongly dual functional problem whose dual variables have a well-known sensitivity interpretation~\cite[Sec.~5.6]{Boyd04c}. So the bracketed quantity in~\eqref{E:epsilon0} 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~$\calP$, a typical compromise between the approximation error and complexity arises. For small sample sets, the generalization error in Def.~\ref{D:near_pacc} 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~$(\bmu_p^\star,\blambda_p^\star)$ may be hard to evaluate since they are related to a version of the statistical problem~\eqref{P:csl}. While their norms can be estimated using classical results from optimization theory~(see, e.g., \cite{Bertsekas09c, Chamon20f}), they often lead to loose, uninformative bounds. Notice, however, that only~$\epsilon$ depends on the sample size.

\begin{remark}\label{R:no_pointwise}

When the constrained learning problem has no pointwise constraints~[$q = 0$ in~\eqref{P:csl}], Assumption~\ref{A:parametrization} can be relaxed from a uniform to a total variation approximation. Explicitly, Theorem~\ref{T:pacc_ecrm} holds if for each~$\phi \in \calH$ there exist~$\btheta \in \setR^p$ such that~$\E_{(\bx,y) \sim \fkD_i} \!\big[ \abs{f_{\btheta}(\bx)-\phi(\bx)} \big] \leq \nu$ for all~$i$.

\end{remark}

\begin{algorithm}[t]
\caption{Primal-dual near-PACC learner}
	\label{L:primal_dual}
\begin{algorithmic}[1]
	\State \textit{Initialize}: $\btheta^{(0)} = 0$, $\bmu^{(0)} = \ones$, $\blambda_j^{(0)} = \ones$
	\For $t = 1,\dots,T$
		\State Obtain~$\btheta^{(t-1)}$ such that
		$\displaystyle
			\hat{L}\Big( \btheta^{(t-1)}, \bmu^{(t-1)}, \blambda_j^{(t-1)} \Big)
				\leq \min_{\btheta \in \setR^p}
					\hat{L} \Big(\btheta, \bmu^{(t-1)}, \blambda_j^{(t-1)} \Big) + \rho
		$

		\State Update dual variables
		\begin{align*}
			\mu_i^{(t)} &= \Bigg[ \mu_i^{(t-1)} + \eta \Bigg(
				\frac{1}{N_i} \sum_{n_i = 1}^{N_i}
					\ell_i\big( f_{\btheta^{(t-1)}}(\bx_{n_i}), y_{n_i} \big) - c_i
			\Bigg) \Bigg]_+
			\\
			\lambda_{j,n_j}^{(t)} &= \Big[ \lambda_{j,n_j}^{(t-1)} + \frac{\eta}{N_j} \Big(
				\ell_j\big( f_{\btheta^{(t-1)}}(\bx_{n_j}), y_{n_j} \big) - c_j
			\Big) \Big]_+
		\end{align*}
	\EndFor
\end{algorithmic}
\end{algorithm}

\subsection{A Primal-Dual near-PACC Learner}
\label{S:algorithm}

We now proceed to introduce a practical algorithm to solve~\eqref{P:csl_empirical_dual} 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}(\bmu,\blambda_j) = \min_{\btheta} \hat{L}(\btheta,\bmu,\blambda_j)$ is the pointwise minimum of a set of affine functions and is therefore always concave~\cite{Bertsekas09c}. Additionally, its (sub)gradients can be easily computed by evaluating the constraint slacks at the minimizer of~$\hat{L}$~\cite[Ch.~3]{Bertsekas15c}. Hence, the main challenge in~\eqref{P:csl_empirical_dual} is the inner minimization.

Despite the Lagrangian~\eqref{E:empirical_lagrangian} often being non-convex in~$\btheta$, \eqref{P:csl_empirical_dual} is an unconstrained optimization problem. Hence, contrary to~\eqref{P:ecrm_parametrized}, 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~\cite{Zhang16u, Arpit17a, Ge17l, Brutzkus17g, Soltanolkotabi18t}. In that vein, we thus assume that we have access to the following oracle:

\begin{assumption}\label{A:oracle}

There exists an oracle~$\btheta^\dagger(\bmu,\blambda_j)$ and~$\rho > 0$ such that~$\hat{L} \big( \btheta^\dagger(\bmu,\blambda_j),\bmu,\blambda_j \big) \leq \min_{\btheta} \hat{L} \big( \btheta,\bmu,\blambda_j \big) + \rho$ for all~$\bmu \in \setR^m_+$ and~$\blambda_j \in \setR^{N_j}_+$, $j = m+1,\dots,m+q$.

\end{assumption}

Assumption~\ref{A:oracle} essentially states that we are able to~(approximately) train regularized unconstrained learners using the parametrization~$f_{\btheta}$. We can alternate between minimizing the Lagrangian~\eqref{E:empirical_lagrangian} with respect to~$\btheta$ for fixed~$(\bmu,\blambda_j)$ and updating the dual variables using the resulting minimizer. This procedure is summarized in Algorithm~\ref{L:primal_dual} and analyzed in the following theorem:

\begin{theorem}\label{T:convergence}

Fix~$\beta > 0$ and consider Algorithm~\ref{L:primal_dual} with at least~$C \zeta^{-1}(\epsilon,\delta,d_\calP)$ samples from each~$\fkD_j$, where~$C$ is an absolute constant, $\zeta^{-1}$ is as in~\eqref{E:zeta}, and~$d_\calP$ is the VC dimension of~$\calP$. Under Assumptions~\ref{A:losses}--\ref{A:oracle}, Algorithm~\ref{L:primal_dual} converges to the neighborhood

\begin{equation}
	P^\star - \rho - \beta - \eta S - \epsilon
		\leq \hat{L}\Big( \btheta^{(T)},\bmu^{(T)},\blambda_j^{(T)} \Big)
		\leq P^\star + \rho + \epsilon_0 + \epsilon
\end{equation}

with probability~$1-\delta$ after at most~$T = O(1/\beta)$ for~$\epsilon_0$ as in~\eqref{E:epsilon0} and~$S = O\big(B^2\big)$.

\end{theorem}

\begin{proof}

See Appendix~
\ifappend \ref{X:algorithm}.\else C in the extended version~\cite{Chamon20p}.\fi

\end{proof}

Theorem~\ref{T:convergence} bounds the suboptimality of Algorithm~\ref{L:primal_dual} with respect to the original learning problem~\eqref{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~$(\btheta^{(T)},\bmu^{(T)},\blambda_j^{(T)})$ of Algorithm~\ref{L:primal_dual} after convergence and not to a randomized solution obtained by sampling from~$(\btheta^{(t)},\bmu^{(t)},\blambda_j^{(t)})$, $t = 0,\dots,T$ as in~\cite{Goh16s, Agarwal18a, Cotter19o}.

Underlying the oracle in Assumption~\ref{A:oracle} 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~$\btheta^{(t)}$ and the dual variables~$(\bmu^{(t)},\blambda_j^{(t)})$. This primal-dual method leads in fact to a classical convex optimization algorithm~\cite{Arrow58s}. While the convergence guarantee of Theorem~\ref{T:convergence} 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.

\section{Numerical experiments}
\label{S:sims}

\begin{figure}[tb]
\begin{minipage}[c]{0.48\columnwidth}
\centering
\includegraphics[width=\columnwidth]{adult_nn_change}
\vspace*{-6mm}

{\small \hspace{0.4cm} (a)}
\end{minipage}
\hfill
\begin{minipage}[c]{0.48\columnwidth}
\centering
\includegraphics[width=\columnwidth]{adult_nn_hard_examples}
\vspace*{-6mm}

{\small \hspace{0.7cm} (b)}
\end{minipage}
\caption{Fair classification~(Adult dataset): (a)~classifier sensitivity and (b)~prevalence of different groups among the~$20\%$ training set examples with largest dual variables.}
	\label{F:main_fair}
\end{figure}

\begin{figure}[tb]
\begin{minipage}[c]{0.48\columnwidth}
\centering
\includegraphics[width=\columnwidth]{fmnist_accuracy}
\vspace*{-6mm}

{\small \hspace{0.7cm} (a)}
\end{minipage}
\hfill
\begin{minipage}[c]{0.48\columnwidth}
\centering
\includegraphics[width=\columnwidth]{fmnist_pdf}
\vspace*{-6mm}

{\small \hspace{0.7cm} (b)}
\end{minipage}
\caption{Robust constrained learning (FMNIST): (a)~Accuracy of classifiers under the PGD attack for different perturbation magnitudes and (b)~distribution of~$\varepsilon$ used during training.}
	\label{F:main_robust}
\end{figure}

Due to space constraints, we only provide highlights of the results obtained for the problems from Section~\ref{S:csl}. For more details and additional experiments, see Appendix
\ifappend \ref{X:sims}.\else D in the extended version~\cite{Chamon20p}.\fi

\textbf{Invariance and fair learning.} In the Adult dataset~\cite{Dua17u}, 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.~\ref{F:main_fair}a). For step~3 of Algorithm~\ref{L:primal_dual}, we use ADAM~\cite{Kingma17a} 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~\eqref{E:invariance_pointwise}, 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~\cite{Donini18e, Dwork12f}. But Algorithm~\ref{L:primal_dual} provides more than an invariant classifier. Due to the bound on the duality gap between~\eqref{P:csl} and~\eqref{P:csl_empirical_dual}, the dual variables have a sensitivity interpretation: the larger their value, the harder the constraint is to satisfy~\cite{Bertsekas09c}. If we analyze the~$20\%$ of individuals with largest~$\lambda_{n}$~(Fig.~\ref{F:main_fair}b), 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~\cite{Kearns18p}. Similar results can be derived when controlling for racial bias in the COMPAS dataset.

\textbf{Robust learning.} In this illustration, we use Algorithm~\ref{L:primal_dual} to train a ResNet18~\cite{He16d} to classify images from the FMNIST dataset~\cite{Xiao17f}. As in the previous example, we once again use the ADAM optimizer with the settings from~\cite{Kingma17a}. The best accuracy over the validation set is achieved after~$67$ epochs, yielding a solution with test accuracy of~$93.5\%$~(Figure~\ref{F:main_robust}a). However, it fails to classify any of the test images when perturbed using a PGD attack with perturbation magnitude~($\ell_\infty$-norm of the perturbation) as low as~$\varepsilon = 0.04$~\cite{Madry18t}. The attack uses a step size of~$\varepsilon/30$ for~$50$ iterations and we show the worst result over~$10$ restarts.

To overcome this issue, we use PGD to sample from a hypothetical ``adversarial distribution''~$\fkA$ and constrain the performance of the solution against~$\fkA$ as in~\eqref{P:robustness}. 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~\ref{F:main_robust}b. Doing so not only yields better performances under perturbation as well as a small loss of nominal accuracy.

\section{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~\cite{Paternain19c}. 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~\cite{Chamon20f}.

\section*{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~\cite{Datta15a, Kay15u, Angwin16m, NationalTransportationSafetyBoard18h, Dastin18a, Bright16t}. 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~\cite{Anand20a, Hadavas20h, Loggins20h}) important sources of biases.

\begin{ack}
This work is supported by ARL DCIST CRA W911NF-17-2-0181.
\end{ack}

\bibliographystyle{IEEEtran}
\bibliography{aux_files/IEEEabrv,aux_files/af,aux_files/bayes,aux_files/control,aux_files/gsp,aux_files/math,aux_files/ml,aux_files/rkhs,aux_files/rl,aux_files/sp,aux_files/stat}

\ifappend
\newpage
\appendix

\section{Proof of Theorem \ref{T:pacc_ecrm}}
\label{X:pacc_ecrm}

Start by noticing from the definition of PACC learnability~[more specifically, from~\eqref{E:pacc_optimal} in Def.~\ref{D:pacc}] that any PACC learnable class~$\calH$ is necessarily PAC learnable.

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

\begin{equation}\label{E:vc_bound}
	\abs{\E_{(\bx,y) \sim \fkD} \!\Big[ g\big( \phi(\bx),y \big) \Big]
		- \frac{1}{N} \sum_{n = 1}^{N} g\big( \phi(\bx_{n}), y_{n} \big)} \leq \epsilon
\end{equation}

for all function~$\phi \in \calH$, distributions~$\calD$, and samples~$(\bx_n,y_n) \sim \calD$. Now, let~$\hat{\phi}^\star$ be a solution of~\eqref{P:ecrm}. From~\eqref{E:vc_bound} and the boundedness hypothesis on~$\ell_0$, we immediately obtain that~$\hat{\phi}^\star$ is probably approximately optimal as in~\eqref{E:pacc_optimal}. Additionally, $\hat{\phi}^\star$ must be feasible for~\eqref{P:ecrm}. Hence,

\begin{subequations}\label{E:ecrm_feas}
\begin{align}
	\frac{1}{N_i} \sum_{n_i = 1}^{N_i} \ell_i\big( \hat{\phi}^\star(\bx_{n_i}), y_{n_i} \big) &\leq c_i
		\text{,}
	&&\text{for } i = 1,\dots,m
		\text{,} \quad \text{and}
	\\
	\ell_j\big( \hat{\phi}^\star(\bx_{n_j}), y_{n_j} \big) &\leq c_j
		\text{,}
	&&\text{for all } n_j = 1,\dots,N_j
		\text{ and } j = m+1,\dots,m+q
	\text{.}
\end{align}
\end{subequations}

To show~\eqref{E:ecrm_feas} implies that~$\hat{\phi}^\star$ is a probably approximately feasible, note that we can write, using~\eqref{E:vc_bound},

\begin{subequations}\label{E:ecrm_feas_vc}
\begin{align}
	\E_{(\bx,y) \sim \fkD_i} \!\Big[ \ell_i\big( \hat{\phi}^\star(\bx),y \big) \Big] &\leq
		\frac{1}{N_i} \sum_{n_i = 1}^{N_i} \ell_i\big( \hat{\phi}^\star(\bx_{n_i}), y_{n_i} \big)
			+ \epsilon
		\quad \text{and}
	\\
	\Pr_{(\bx,y) \sim \fkD_j} \!\Big[ \ell_j\big( \hat{\phi}^\star(\bx),y \big) \leq b_j \Big]
		&= \E_{(\bx,y) \sim \fkD_j} \!\Big[
			\indicator \left[ \ell_j\big( \hat{\phi}^\star(\bx),y \big) \leq b_j \right]
		\Big]
	\notag\\
	{}&\geq \frac{1}{N_j} \sum_{n_j = 1}^{N_j}
		\indicator \left[ \ell_j\big( \hat{\phi}^\star(\bx_{n_j}), y_{n_j} \big) \leq b_j \right]
		- \epsilon
		\text{,}
\end{align}
\end{subequations}

each of which hold with probability~$1-\delta$ over the samples~$(\bx_{n_i},y_{n_i})$ as long as~$N_i > C\zeta^{-1}(\epsilon,\delta,d_\calH)$. Combining~\eqref{E:ecrm_feas} and~\eqref{E:ecrm_feas_vc} we conclude that, with probability~$1-(m+q)\delta$, it holds simultaneously that

\begin{align*}
	\E_{(\bx,y) \sim \fkD_i} \!\Big[ \ell_i\big( \hat{\phi}^\star(\bx),y \big) \Big] &\leq
		c_i + \epsilon
		\quad \text{and}
	\\
	\ell_j\big( \hat{\phi}^\star(\bx),y \big) &\leq c_j
		\quad \text{for all } (\bx,y) \in \calK_j \subseteq \calX \times \calY
		\text{,}
\end{align*}

where each~$\calK_j$ is a set of~$\fkD_j$-measure at least~$1-\epsilon$.

Hence, if~$\calH$ is PAC learnable, then there exists~$N$ such that, if~$\hat{\phi}^\star$ is a solution of~\eqref{P:ecrm} obtained using~$N_i \geq N$ samples from each~$\fkD_i$, then~$\hat{\phi}^\star$ is probably approximately optimal as in~\eqref{E:pacc_optimal} and probably approximately feasible as in~\eqref{E:pacc_feasible}.

\hfill$\square$

\section{Proof of Theorem \ref{T:pacc_csl}}
\label{X:main}

As we have argued before, we cannot rely on the duality between~\eqref{P:ecrm_parametrized} and~\eqref{P:csl_empirical_dual} to obtain this result because of its non-convexity. Hence, this proof proceeds directly from~\eqref{P:csl} by applying three transformations that yield~\eqref{P:csl_empirical_dual}, but whose approximation and estimation errors can be controlled. First, we obtain the dual problem of~\eqref{P:csl} and show that this transformation incurs in no error. This stems from the convexity of~\eqref{P:csl} under Assumptions~\ref{A:losses} and~\ref{A:parametrization} and is a straightforward strong duality result from semi-infinite programming theory~(Proposition~\ref{T:zdg}). Second, we approximate the function class~$\calH$ using the finite dimensional parametrization~$f_{\btheta}$ and bound the \emph{approximation error}~$\epsilon_0$~(Proposition~\ref{T:param}). Third, we obtain~\eqref{P:csl_empirical_dual} by replacing the expectations with their empirical versions. Since the problem is now unconstrained, we can use classical learning theory to evaluate the \emph{estimation error}~$\epsilon$~(Proposition~\ref{T:empirical}). We then combine these results to obtain Theorem~\ref{T:pacc_csl}.

Explicitly, we begin by defining the Lagrangian of~\eqref{P:csl} as

\begin{equation}\label{E:lagrangian_csl}
\begin{aligned}
	L(\phi, \bmu, \blambda) &= \E_{(\bx,y) \sim \fkD_0} \!\Big[ \ell_0\big( \phi(\bx),y \big) \Big]
	+ \sum_{i = 1}^m \mu_i \left[
		\E_{(\bx,y) \sim \fkD_i} \!\Big[ \ell_i\big( \phi(\bx),y \big) \Big] - c_i
	\right]
	\\
	{}&+ \sum_{j = m+1}^{m+n} \int \lambda_j(\bx,y) \Big[
		\ell_j\big( \phi(\bx),y \big) - c_j
	\Big] p_{\fkD_j}\!(\bx,y) d\bx dy
		\text{,}
\end{aligned}
\end{equation}

where~$p_{\fkD_j}$ is the density of~$\fkD_j$, $\bmu \in \setR^m_+$ collects the dual variables~$\mu_i$ relative to the expected constraints, and~$\blambda$ is an~$n \times 1$ vector that collects the functional dual variables~$\lambda_j \in L_{1,+}$ relative to the pointwise constraints. By~$f \in L_{1,+}$ we mean that~$f \in L_1$~(absolutely integrable) and~$f \geq 0$ a.e. For conciseness, we leave the measure implicit. Observe that, since the losses~$\ell_j$ are bounded~(Assumption~\ref{A:losses}), the integral in~\eqref{E:lagrangian_csl} exists and is well-defined. This is a direct consequence of H\"older's inequality~\cite[Thm.~1.5.2]{Durrett10p}. Additionally, while the result does not require~$\fkD_j$ to have a density, we assume that it is absolutely continuous with respect to the Lebesgue measure to simplify the derivations. The dual problem of~\eqref{P:csl_1} can then be written as

\begin{equation}\label{P:dual_csl}
	D^\star = \max_{\bmu \in \setR^m_+,\ \lambda_j \in L_{1,+}}\ \min_{\phi \in \calH}\
		L(\phi, \bmu, \blambda)
		\text{.}
		\tag{\textup{D-CSL}}
\end{equation}

Assumptions~\ref{A:losses}--\ref{A:slater} imply that~\eqref{P:csl} is strongly dual:

\begin{proposition}\label{T:zdg}

Under Assumptions~\ref{A:losses}--\ref{A:slater}, the semi-infinite program~\eqref{P:csl} and the saddle-point problem~\eqref{P:dual_csl} are strongly dual, i.e., $P^\star = D^\star$.

\end{proposition}

\begin{proof}

Start by noticing that~\eqref{P:csl} can be equivalently formulated as

\begin{prob}\label{P:csl_1}
	P^\star = \min_{\phi\in\calH}&
		&&\E_{(\bx,y) \sim \fkD_0} \!\Big[ \ell_0\big( \phi(\bx),y \big) \Big]
	\\
	\subjectto& &&\E_{(\bx,y) \sim \fkD_i} \!\Big[ \ell_i\big( \phi(\bx),y \big) \Big] \leq c_i
		\text{,} \quad i = 1,\ldots,m
		\text{,}
	\\
	&&&\ell_j\big( \phi(\bx),y \big) p_{\fkD_j}\!(\bx,y) \leq c_j p_{\fkD_j}\!(\bx,y)
		\text{,} \quad (\bx,y) \in \calX \times \calY
		\text{,}
	\\
	&&&\qquad\qquad\qquad\qquad\qquad\qquad j = m+1,\ldots,n
		\text{.}
\end{prob}

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

From Assumptions~\ref{A:losses} and~\ref{A:parametrization} we obtain that~\eqref{P:csl_1} is a semi-infinite convex program. What is more, Assumption~\ref{A:slater} implies it has a strictly feasible solution~$\phi^\prime = f_{\btheta^\prime}$. This constraint qualification, sometimes known as \emph{Slater's condition}, implies that is strongly dual, i.e., that~$P^\star = D^\star$~\cite{Shapiro09s}.

\end{proof}

\subsection{The approximation gap}

While there is no duality gap between~\eqref{P:csl} and~\eqref{P:dual_csl}, the latter remains a variational problem. The next step is there to approximate the functional space~$\calH$ by~$\calP = \{f_{\btheta} \mid \btheta \in \setR^p\}$, the space induced by the finite dimensional parametrization~$f_{\btheta}$. Thus, \eqref{P:dual_csl} becomes the finite dimensional problem

\begin{equation}\label{P:dual_csl_param}
	D_{\nu}^\star = \max_{\bmu \in \setR^m_+,\ \lambda_j \in L_{1,+}}\
	\min_{\btheta \in \setR^p}\
		L_\nu(\btheta, \bmu, \blambda) \triangleq L(f_{\btheta}, \bmu, \blambda)
		\text{.}
		\tag{$\textup{D}_{\nu}$\textup{-CSL}}
\end{equation}

Since~$\calP \subseteq \calH$~(Assumption~\ref{A:parametrization}), 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.

\begin{proposition}\label{T:param}

Let~$\btheta^\star$ achieve the saddle-point in~\eqref{P:dual_csl_param}. Under Assumptions~\ref{A:losses}--\ref{A:slater}, $f_{\btheta^\star}$ is a feasible, near-optimal solution of~\eqref{P:csl}. Explicitly,

\begin{equation}\label{E:param_gap}
	P^\star \leq D^\star_{\nu} \leq P^\star +
		\left( 1 + \norm{\bmut}_1
			+ \sum_{j = m+1}^{m+q} \Vert \tilde{\lambda}_{j}^\star \Vert_{L_1} \right) L \nu
		\text{,}
\end{equation}

for~$P^\star$ and~$D^\star_\nu$ defined as in~\eqref{P:csl} and~\eqref{P:dual_csl_param} respectively and where~$(\bmut,\blambdat)$ are the dual variables of~\eqref{P:csl} with the constraints tightened to~$c_i - M \nu$ for~$i = 0,\dots,m+q$.

\end{proposition}

\begin{proof}

See Appendix~\ref{X:param}.

\end{proof}

\subsection{The estimation gap}

All that remains, is to turn the statistical Lagrangian~\eqref{E:lagrangian_csl} into the empirical~\eqref{E:empirical_lagrangian}. The incurred estimation error is described in the next proposition.

\begin{proposition}\label{T:empirical}

Let~$\bhtheta$ achieve the saddle-point in~\eqref{P:csl_empirical_dual} and for~$\delta > 0$, let

\begin{equation}\label{E:zeta_inv}
	\zeta(N) = \sqrt{\frac{1}{N} \left[
		1 + \log\left( \frac{4 (m+q+2) (2N)^{d_\calP}}{\delta} \right)
	\right]}
		\text{,}
\end{equation}

where~$d_\calP$ is the VC dimension of the parametrized class~$\calP$. Under Assumptions~\ref{A:losses}--\ref{A:slater}, it holds with probability~$1-\delta$ over the samples drawn from the distributions~$\fkD_i$ that

\begin{align}
	\big\vert D^\star_{\nu} - \hat{D}^\star \big\vert &\leq B \zeta(N_0)
		\text{,}
		\label{E:empirical_gap}
	\\
	\E_{(\bx,y) \sim \fkD_i} \!\Big[ \ell_i\big( f_{\bm{{\hat{\theta}}}^\star}(\bx), y \big) \Big]
		&\leq c_i + B \zeta(N_i)
		\text{,}
		\ \ \text{and}
		\label{E:empirical_feas}
	\\
	\ell_j\big( f_{\bm{{\hat{\theta}}}^\star}(\bx), y \big) &\leq c_j
		\ \ \text{for } (\bx,y) \in \calK_j
		\text{,}
		\label{E:empirical_pointwise}
\end{align}

where~$\calK_j \subseteq \calX \times \calY$ is a set of $\fkD_j$-measure at least~$1 - \zeta(N_j)$ for all~$j = m+1,\dots,m+q$.

\end{proposition}

\begin{proof}

See appendix~\ref{X:empirical}.

\end{proof}

\subsection{The PACC solution}

The proof concludes by combining the parametrization and estimation gap results from Propositions~\ref{T:param} and~\ref{T:empirical}. Namely, notice that~\eqref{E:empirical_feas} and~\eqref{E:empirical_pointwise} imply that the minimizer~$\hat{\btheta}^\star$ that achieves the saddle-point in~\eqref{P:csl_empirical_dual} is probably approximately feasible~[see~\eqref{E:pacc_feasible}] for~\eqref{P:csl}. Then, combining~\eqref{E:param_gap} and~\eqref{E:empirical_gap} using the triangle inequality yields the near-PACC gap from Def.~\ref{D:near_pacc}. Fixing~$N$ such that~$B\zeta(N) \leq \epsilon$ yields the result in Theorem~\ref{T:pacc_csl}.

\hfill$\square$

\subsection{Proof of Proposition~\ref{T:param}: The Approximation Gap}
\label{X:param}

We first prove that~$f_{\btheta^\star}$ is feasible for~\eqref{P:csl} and then bound the gap between~$D^\star_\nu$ and~$P^\star$.

\paragraph{Feasibility.}

Suppose that~$f_{\btheta^\star}$ is infeasible. Then, there exists at least one~$i > 0$ such that~$\E_{(\bx,y) \sim \fkD_i} \!\Big[ \ell_i\big( f_{\btheta^\star}(\bx), y \big) \Big] > c_i$ or~$\ell_i\big( f_{\btheta^\star}(\bx), y \big) > c_i$ over some set~$\calA \subseteq \calX \times \calY$ of positive~$\fkD_i$-measure. Since~$\bmu$ and~$\blambda$ are unbounded above, we obtain that~$D^\star_\nu \to +\infty$. However, Assumptions~\ref{A:losses} and~\ref{A:slater} imply that~$D^\star_\nu < +\infty$. Indeed, consider the dual function

\begin{equation}\label{E:param_d}
\begin{aligned}
	d(\bmu,\blambda) &= \min_{\btheta \in \calH} L_\nu(\btheta, \bmu, \blambda)
	\\
	{}&= \min_{\btheta \in \calH}\
	\E_{(\bx,y) \sim \fkD_0} \!\Big[ \ell_0\big( f_{\btheta}(\bx),y \big) \Big]
	+ \sum_{i = 1}^m \mu_i \Big[
		\E_{(\bx,y) \sim \fkD_i} \!\big[ \ell_i\big( f_{\btheta}(\bx),y \big) \big] - c_i
	\Big]
	\\
	{}&+ \sum_{j = m+1}^{m+q} \int \lambda_j(\bx,y) \Big[
		\ell_j\big( f_{\btheta}(\bx),y \big) - c_j
	\Big] p_{\fkD_j}\!(\bx,y) d\bx dy
		\text{,}
\end{aligned}
\end{equation}

for the Lagrangian defined in\eqref{P:dual_csl_param}. Using the fact that~$\ell_0$ is $B$-bounded~(Assumption~\ref{A:losses}) and that there exists a strictly feasible~$\btheta^\prime$~(Assumption~\ref{A:slater}), $d(\bmu,\blambda)$ is upper bounded by

\begin{align*}
	d(\bmu,\blambda) &\leq \E_{(\bx,y) \sim \fkD_0} \!\Big[
		\ell_0\big( f_{\btheta^\prime}(\bx),y \big)
	\Big]
	+ \sum_{i = 1}^m \mu_i \Big[
		\E_{(\bx,y) \sim \fkD_i} \!\big[ \ell_i\big( f_{\btheta^\dagger}(\bx),y \big) \big]
		- c_i
	\Big]
	\\
	{}&+ \sum_{j = m+1}^{m+q} \int \lambda_j(\bx,y) \Big[
		\ell_j\big( f_{\btheta^\prime}(\bx),y \big) - c_j
	\Big] p_{\fkD_j}\!(\bx,y) d\bx dy
	< B
		\text{,}
\end{align*}

where we used the fact that~$\mu_i \geq 0$ and~$\lambda_j \geq 0$ $\fkD_j$-a.e. Hence, it must be that~$f_{\btheta^\star}$ is feasible for~\eqref{P:csl}.

\paragraph{Near-optimality.}

First, recall that under Assumptions~\ref{A:losses}--\ref{A:slater}, \eqref{P:csl}--\eqref{P:dual_csl} form a strongly dual pair of mathematical programs~(Proposition~\ref{T:zdg}). For the Lagrangian in~\eqref{E:lagrangian_csl}, we therefore obtain the saddle-point relation

\begin{equation}\label{E:saddle_csl}
	L( \phi^\star, \bmu^\prime, \blambda^\prime ) \leq
	\max_{\bmu, \blambda}\ \min_{\phi \in \calH}\
		L(\phi, \bmu, \blambda)
	= D^\star = P^\star
	= \min_{\phi \in \calH}\ \max_{\bmu, \blambda}\
		L(\phi, \bmu, \blambda)
	\leq L( \phi^\prime, \bmu^\star, \blambda^\star )
\end{equation}

holds for all~$\phi^\prime \in \calH$, $\bmu^\prime \in \setR^m_+$, and~$\lambda_j^\prime \in L_{1,+}$, where~$\phi^\star$ is a solution of~\eqref{P:csl} and~$(\bmu^\star,\blambda^\star)$ are solutions of~\eqref{P:dual_csl}. We omit the spaces that~$(\bmu, \blambda)$ belong to for conciseness. Additionally, we have from~\eqref{P:dual_csl_param} that

\begin{equation}
	D_\nu^\star \geq \min_{\btheta \in \setR^p} L( \btheta, \bmu, \blambda )
		\text{,} \quad \text{for all } \bmu \in \setR^m_+ \text{ and } \lambda_j \in L_{1,+}
		\text{.}
\end{equation}

Immediately, we obtain the lower bound in~\eqref{E:param_gap}. Explicitly,

\begin{equation}
	D_\nu^\star
		\geq \min_{\btheta \in \setR^p} L( \btheta, \bmu, \blambda )
		\geq \min_{\phi \in \calH} L( \phi, \bmu^\star, \blambda^\star ) = P^\star
		\text{,}
\end{equation}

where the second inequality comes from the fact that~$\calP \subseteq \calH$~(Assumption~\ref{A:parametrization}).

The upper bound is obtained by relating the parameterized dual problem~\eqref{P:dual_csl_param} to a perturbed~(tightened) version of the original~\eqref{P:csl}. To do so, start by adding and subtracting~$L(\phi,\bmu,\blambda)$ from~\eqref{P:dual_csl_param} to get

\begin{equation}\label{E:lagrangian_difference}
\begin{aligned}
	D^\star_\nu &= \max_{\bmu,\blambda}\
		\min_{\btheta \in \setR^p}\
		L(\phi,\bmu,\blambda) +
		\E_{(\bx,y) \sim \fkD_0} \!\Big[
			\ell_0\big( f_{\btheta}(\bx),y \big) - \ell_0(\phi(\bx),y)
		\Big]
	\\
	{}&+ \sum_{i = 1}^m \mu_i
		\E_{(\bx,y) \sim \fkD_i} \!\Big[
			\ell_i\big( f_{\btheta}(\bx),y \big) - \ell_i(\phi(\bx),y)
		\Big]
	\\
	{}&+ \sum_{j = m+1}^{m+q} \E_{(\bx,y) \sim \fkD_j} \!\Big[
		\lambda_j(\bx,y) \Big(
		\ell_j\big( f_{\btheta}(\bx),y \big) - \ell_j\big( \phi(\bx),y \big)
	\Big) \Big]
		\text{,}
\end{aligned}
\end{equation}

where we wrote the integral against~$p_{\fkD_j}$ as an expectation for conciseness. Then, using the fact that~$\ell_i$ is $M$-Lipschitz continuous~(Assumption~\ref{A:losses}), we bound the expectations in the first two terms of~\eqref{E:lagrangian_difference} as

\begin{equation}\label{E:bound_lipschitz}
\begin{aligned}
	\E_{(\bx,y) \sim \fkD_j} \!\Big[
		\ell_i\big( f_{\btheta}(\bx),y \big) - \ell_i\big( \phi(\bx),y \big)
	\Big]
	&\leq
	\E_{(\bx,y) \sim \fkD_j} \!\Big[ \big\vert
		\ell_i\big( f_{\btheta}(\bx),y \big) - \ell_i\big( \phi(\bx),y \big)
	\big\vert \Big]
	\\
	{}&\leq M \E_{(\bx,y) \sim \fkD_j} \!\Big[ \big\vert  f_{\btheta}(\bx) - \phi(\bx) \big\vert \Big]
		\text{, for } i = 0,\dots,m
		\text{.}
\end{aligned}
\end{equation}

To bound the last expectation in~\eqref{E:lagrangian_difference}, we first use H\"{o}lder's inequality to get

\begin{multline*}
	\E_{(\bx,y) \sim \fkD_j} \!\Big[
		\lambda_j(\bx,y) \Big(
		\ell_j\big( f_{\btheta}(\bx),y \big) - \ell_j\big( \phi(\bx),y \big)
	\Big) \Big]
	\leq{}
	\\
	\E_{(\bx,y) \sim \fkD_j} \!\big[ \lambda_j(\bx,y) \big]
		\norm{\ell_j\big( f_{\btheta}(\bx),y \big) - \ell_j\big( \phi(\bx),y \big)}_{L_\infty}
		\text{,}
\end{multline*}

where we recall that~$\norm{g}_{L_\infty}$ is the essential supremum of~$\abs{g}$.
Then, the~$M$-Lipschitz continuity of~$\ell_j$~(Assumption~\ref{A:losses}) implies that

\begin{multline}\label{E:bound_lipschiptz_pointwise}
	\E_{(\bx,y) \sim \fkD_j} \!\Big[
		\lambda_j(\bx,y) \Big(
		\ell_j\big( f_{\btheta}(\bx),y \big) - \ell_j\big( \phi(\bx),y \big)
	\Big) \Big]
	\leq{}
	\\
	M \norm{f_{\btheta}(\bx) - \phi(\bx)}_{L_\infty}
		\E_{(\bx,y) \sim \fkD_j} \!\big[ \lambda_j(\bx,y) \big]
		\text{.}
\end{multline}

Using~\eqref{E:bound_lipschitz} and~\eqref{E:bound_lipschiptz_pointwise}, together with the approximation property of the class~$\calH$~(Assumption~\ref{A:parametrization}), we upper bound the minimum over~$\btheta$ in~\eqref{E:lagrangian_difference} to obtain

\begin{equation}\label{E:bound_pertubed1}
	D^\star_\nu \leq \max_{\bmu,\blambda}\
		L(\phi,\bmu,\blambda) + \left[
			1 + \sum_{i = 1}^m \mu_i + \sum_{j = m+1}^{m+q}  \E_{(\bx,y) \sim \fkD_j} \!\big[
			\lambda_j(\bx,y) \big]
		\right] M \nu
		\text{.}
\end{equation}

Notice that since~\eqref{E:bound_pertubed1} holds uniformly for all~$\phi \in \calH$, it also holds for the minimizer

\begin{equation}\label{E:bound_pertubed}
	D^\star_\nu \leq \min_{\phi \in \calH}\ \max_{\bmu,\blambda}\
		L(\phi,\bmu,\blambda) + \left[
			1 + \sum_{i = 1}^m \mu_i + \sum_{j = m+1}^{m+n}  \E_{(\bx,y) \sim \fkD_j} \!\big[
			\lambda_j(\bx,y) \big]
		\right] M \nu
		\triangleq \tilde{P}^\star
\end{equation}

and that the right-hand side of~\eqref{E:bound_pertubed}, namely~$\tilde{P}^\star$, is in fact a perturbed version of~\eqref{P:csl}. Hence, we obtain another saddle-point relation similar to~\eqref{E:saddle_csl} relating~$\tilde{P}^\star$, and consequently~$D^\star_\nu$, to~$P^\star$.

Formally, \eqref{E:bound_pertubed} can be rearranged as

\begin{equation}\label{E:primal_perturbed}
\begin{aligned}
	\tilde{P}^\star &= \min_{\phi \in \calH}\ \max_{\bmu,\blambda}\
		\E_{(\bx,y) \sim \fkD_0} \!\Big[ \ell_0\big( \phi(\bx),y \big) + M \nu \Big]
	\\
	{}&+ \sum_{i = 1}^m \mu_i \left[
		\E_{(\bx,y) \sim \fkD_i} \!\Big[ \ell_i\big( \phi(\bx),y \big) \Big]
			- c_i + M \nu
	\right]
	\\
	{}&+ \sum_{j = m+1}^{m+q} \int \lambda_j(\bx,y) \Big[
		\ell_j\big( \phi(\bx),y \big) - c_j + M \nu
	\Big] p_{\fkD_j}\!(\bx,y) d\bx dy
		\text{,}
\end{aligned}
\end{equation}

where we recognize the optimization problem of

\begin{prob}\label{P:csl_perturbed}
	\tilde{P}^\star = \min_{\phi\in\calH}&
		&&\E_{(\bx,y) \sim \fkD_0} \!\Big[ \ell_0\big( \phi(\bx),y \big) \Big]
			+ M \nu
	\\
	\subjectto& &&\E_{(\bx,y) \sim \fkD_i} \!\Big[ \ell_i\big( \phi(\bx),y \big) \Big]
		\leq c_i - M \nu
		\text{,} &&i = 1,\ldots,m
		\text{,}
	\\
	&&&\ell_j\big( \phi(\bx),y \big) \leq c_j - M \nu
		\quad \fkD_j\text{-a.e.}
		\text{,} &&j = m+1,\ldots,m+q
		\text{.}
\end{prob}

Under Assumptions~\ref{A:losses}--\ref{A:slater}, \eqref{P:csl_perturbed} is also strongly dual~(Proposition~\ref{T:zdg}), so that

\begin{equation}\label{E:saddle_perturbed}
\begin{aligned}
	\tilde{P}^\star = \min_{\phi \in \calH}\ L(\phi,\bmut,\blambdat) + \left[
		1 + \sum_{i = 1}^m \tilde{\mu}_{i}^\star
		+ \sum_{j = m+1}^{m+n}  \E_{(\bx,y) \sim \fkD_j} \!\big[
			\tilde{\lambda}_{j}^\star(\bx,y) \big]
	\right] M \nu
		\text{,}
\end{aligned}
\end{equation}

where~$(\bmut,\blambdat)$ are the dual variables of~\eqref{P:csl_perturbed}, i.e., the~$(\bmu,\blambda)$ that achieve

\begin{equation}\label{E:dual_perturbed}
\begin{aligned}
	\tilde{D}^\star &= \max_{\bmu,\blambda}\ \min_{\phi \in \calH}\
		\E_{(\bx,y) \sim \fkD_0} \!\Big[ \ell_0\big( \phi(\bx),y \big) + M \nu \Big]
	\\
	{}&+ \sum_{i = 1}^m \mu_i \left[
		\E_{(\bx,y) \sim \fkD_i} \!\Big[ \ell_i\big( \phi(\bx),y \big) \Big]
			- c_i + M \nu
	\right]
	\\
	{}&+ \sum_{j = m+1}^{m+q} \int \lambda_j(\bx,y) \Big[
		\ell_j\big( \phi(\bx),y \big) - c_j + M \nu
	\Big] p_{\fkD_j}\!(\bx,y) d\bx dy
		\text{.}
\end{aligned}
\end{equation}

Going back to~\eqref{E:bound_pertubed} we can now conclude the proof. First, use~\eqref{E:saddle_perturbed} to obtain

\begin{equation}
	D^\star_\nu \leq \tilde{P}^\star \leq L(\phi^\star,\bmut,\blambdat) + \left[
			1 + \norm{\bmut}_1 + \sum_{j = m+1}^{m+q} \norm{\tilde{\lambda}_{j}^\star}_{L_1}
		\right] L \nu
		\text{,}
\end{equation}

where we used~$\phi^\star$, the solution of~\eqref{P:csl}, as a suboptimal solution in~\eqref{E:saddle_perturbed} and exploited the fact that the dual variables are non-negative to write their sum~(integral) as an~$\ell_1$-norm~($L_1$-norm). The saddle point relation~\eqref{E:saddle_csl} gives~$L(\phi^\star,\bmut,\blambdat) \leq P^\star$, from which we obtain the desired upper bound in~\eqref{E:param_gap}.

\hfill$\square$

\subsection{Proof of Proposition~\ref{T:empirical}: The Estimation Gap}
\label{X:empirical}

\paragraph{Feasibility.}

The proof follows by first showing that~$\bhtheta$ must be feasible for the parametrized ECRM~\eqref{P:ecrm_parametrized} using the same argument as in Sec.~\eqref{X:param}. We then proceed as in the proof of Theorem~\ref{T:pacc_ecrm}.

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

\begin{equation*}
	\frac{1}{N_i} \sum_{n_i = 1}^{N_i} \ell_i\big( f_{\bhtheta}(\bx_{n_i}), y_{n_i} \big) > c_i
	\quad \text{or} \quad
	\ell_i\big( f_{\bhtheta}(\bx_{n_i}), y_{n_i} \big) > c_i
		\text{ for some } n_i
		\text{.}
\end{equation*}

Then, since~$\bmu$ and~$\blambda_j$ are unbounded above, we obtain that~$\hat{D}^\star \to +\infty$. However, Assumptions~\ref{A:losses} and~\ref{A:slater} imply that~$\hat{D}^\star < +\infty$. Indeed, consider the empirical dual function

\begin{equation}\label{E:dual_function_empirical}
	\hat{d}(\bmu, \blambda_j) = \min_{\btheta \in \setR^p} \hat{L}(\btheta, \bmu, \blambda_j)
		\text{.}
\end{equation}

Using the fact that~$\ell_0$ is $B$-bounded~(Assumption~\ref{A:losses}) and that there exists a strictly feasible~$\btheta^\dagger$~(Assumption~\ref{A:slater}), $\hat{d}(\bmu,\blambda) < B$. Hence, it must be that

\begin{subequations}\label{E:feasibility_empirical}
\begin{align}
	\frac{1}{N_i} \sum_{n_i = 1}^{N_i} \ell_i\big( f_{\bhtheta}(\bx_{n_i}), y_{n_i} \big) &\leq c_i
		\text{,}
	&&\text{for } i = 1,\dots,m
		\text{,} \quad \text{and}
	\\
	\ell_j\big( f_{\bhtheta}(\bx_{n_j}), y_{n_j} \big) &\leq c_j
		\text{,}
	&&\text{for all } n_j
		\text{ and } j = m+1,\dots,m+q
	\text{.}
\end{align}
\end{subequations}

We now proceed to use the classic VC bound~\cite[Sec. 3.4]{Vapnik00t} to show that~$f_{\bhtheta}$ is a probably approximately feasible solution of~\eqref{P:csl}. To do so, recall from~\eqref{E:vc_bound} that since the~$\ell_i$ are bounded~(Assumption~\ref{A:losses}) and~$\calP$ has finite VC dimension~$d_\calP$, we obtain that

\begin{subequations}\label{E:feasbility_vc}
\begin{align}
	\E_{(\bx,y) \sim \fkD_i} \!\Big[ \ell_i\big( f_{\btheta}(\bx),y \big) \Big] &\leq
		\frac{1}{N_i} \sum_{n_i = 1}^{N_i} \ell_i\big( f_{\btheta}(\bx_{n_i}), y_{n_i} \big)
			+ B \zeta(N_i)
		\quad \text{and}
	\\
	\Pr_{(\bx,y) \sim \fkD_j} \!\Big[ \ell_j\big( f_{\btheta}(\bx),y \big) \leq b_j \Big]
		&= \E_{(\bx,y) \sim \fkD_j} \!\Big[
			\indicator \left[ \ell_j\big( f_{\btheta}(\bx),y \big) \leq b_j \right]
		\Big]
	\notag\\
	{}&\geq \frac{1}{N_j} \sum_{n_j = 1}^{N_j}
		\indicator \left[ \ell_j\big( f_{\btheta}(\bx_{n_j}), y_{n_j} \big) \leq b_j \right]
		- \zeta(N_j)
\end{align}
\end{subequations}

hold with probability~$1-\delta$ over the datasets~$\{(\bx_{n_i}), y_{n_i})\}_i$ for~$\zeta$ as in~\eqref{E:zeta_inv}. Combining~\eqref{E:feasibility_empirical} and~\eqref{E:feasbility_vc} and using the union bound, we conclude that, with probability~$1-(m+q)\delta$,

\begin{align*}
	\E_{(\bx,y) \sim \fkD_i} \!\Big[ \ell_i\big( f_{\bhtheta}(\bx),y \big) \Big] &\leq
		b_i + B \zeta(N_i)
		\quad \text{and}
	\\
	\ell_j\big( f_{\bhtheta}(\bx),y \big) &\leq b_j
		\quad \text{for all } (\bx,y) \in \calK_j \subseteq \calX \times \calY
		\text{,}
\end{align*}

where~$\calK_j$ is a set of~$\fkD_j$-measure at least~$1-\zeta(N_j)$.

\paragraph{Near-optimality.}

Let~$(\btheta_\nu^\star, \bmu_\nu^\star, \blambda_\nu^\star)$ and~$(\bhtheta, \bhmu, \bhlambda)$ be variables that achieve~$D_{\nu}^\star$ in~\eqref{P:dual_csl_param} and~$\hat{D}^\star$ in~\eqref{P:csl_empirical_dual} respectively. Then, it holds that

\begin{subequations}\label{E:comp_slack}
\begin{align}
	\mu_{\nu,j}^\star \Big(\E \left[\ell_i(f(\btheta_{\nu}^\star,\bx),y)\right]
		- c_j \Big) &= 0
		\text{,}
		\label{E:comp_slack_param1}
	\\
	\lambda_{\nu,j}^\star(\bx,y) \Big( \ell_j(f(\btheta_{\nu}^\star,\bx),y)
		- c_j \Big) &= 0
		\text{,} \quad \fkD_j\text{-a.e.}
		\text{,}
		\label{E:comp_slack_param2}
	\\
	\hat{\mu}_i \bigg(\frac{1}{N} \sum_{n = 1}^N
		\ell_i(f(\bhtheta,\bx_n),y_n)- c_i \bigg) &= 0
		\text{,} \quad \text{and}
		\label{E:comp_slack_emp1}
	\\
	\hat{\lambda}_{j,n_j} \bigg( \ell_i(f(\bhtheta,\bx_n),y_n)- c_j \bigg) &= 0
		\text{,}
		\label{E:comp_slack_emp2}
\end{align}
\end{subequations}

known as \emph{complementary slackness} conditions. While these are part of the classical KKT conditions~\cite[Sec. 5.5.3]{Boyd04c}, it should be noted that the non-convex nature of both~\eqref{P:dual_csl_param} and~\eqref{P:csl_empirical_dual} implies that these are only necessary and not sufficient for optimality. Nevertheless, feasibility is enough to establish~\eqref{E:comp_slack}.

Indeed, recall from Proposition~\ref{T:param} and~\eqref{E:feasibility_empirical} that the constraint slacks in parentheses in~\eqref{E:comp_slack} are non-positive. Hence, the left-hand sides in~\eqref{E:comp_slack} are also non-positive and if~\eqref{E:comp_slack_param1} does not hold for some~$i$ or if~\eqref{E:comp_slack_param2} does not hold for some~$j$ and a set~$\calZ_j$ of positive~$\fkD_j$ measure, then letting~$\mu_{\nu,i}^\star = 0$ or making~$\lambda_j(\bx,y)$ vanish over~$\calZ_j$ would increase the value of~$D_{\nu}^\star$, contradicting its optimality. Note that since~$\calZ_j$ is measurable, the modified~$\lambda_j$ would still be measurable. A similar argument applies to~\eqref{E:comp_slack_emp1} and~\eqref{E:comp_slack_emp2}.

Immediately, \eqref{E:comp_slack} implies that both~\eqref{P:dual_csl_param} and~\eqref{P:csl_empirical_dual} reduce to

\begin{subequations}\label{E:F0}
\begin{alignat}{2}
	D_{\nu}^\star &= \E \left[\ell_0\left(f( \btheta_{\nu}^\star,\bx), y \right)\right]
		&&\triangleq F_0(\btheta_{\nu}^\star)
		\quad \text{and}
	\\
	\hat{D}^\star &= \frac{1}{N_0} \sum_{n_0 = 1}^{N_0}
			\ell_0\left(f( \bhtheta, \bx_{n_0}), y_{n_0} \right)
		&&\triangleq \hat{F}_0(\bhtheta)
		\text{.}
\end{alignat}
\end{subequations}

To proceed, use the optimality of~$\btheta_{\nu}^\star$ and~$\btheta$ for~$F_0$ and~$\hat{F}_0$ respectively to write

\begin{equation*}
	F_0(\btheta_{\nu}^\star) - \hat{F}_0(\btheta_{\nu}^\star) \leq
		F_0(\btheta_{\nu}^\star) - \hat{F}_0(\bhtheta) \leq
		F_0(\bhtheta) - \hat{F}_0(\bhtheta)
		\text{.}
\end{equation*}

Then,~\eqref{E:F0} yields the bound

\begin{equation}\label{E:gapBound}
	\abs{D_{\nu}^\star - \hat{D}^\star} = \abs{
		F_0(\btheta_{\nu}^\star) - \hat{F}_0(\bhtheta)
	} \leq
	\max \bigg\{
		\abs{F_0(\btheta_{\nu}^\star) - \hat{F}_0(\btheta_{\nu}^\star)},
		\abs{F_0(\bhtheta) - \hat{F}_0(\bhtheta)}
	\bigg\}
\end{equation}

and applying the VC generalization bound from~\cite[Sec. 3.4]{Vapnik00t} to~\eqref{E:gapBound}, yields that, uniformly over~$\btheta$,

\begin{equation}\label{E:vcBound}
	\abs{F_0(\btheta) - \hat{F}_0(\btheta)} \leq B \zeta(N_0)
		\text{,}
\end{equation}

with probability~$1-\delta$ and for~$\zeta$ as in~\eqref{E:zeta}. Combining~\eqref{E:gapBound} and~\eqref{E:vcBound} concludes the proof.

\hfill$\square$

\section{Proof of Theorem~\ref{T:convergence}}
\label{X:algorithm}

In this appendix, we prove the following quantitative version of Theorem~\ref{T:convergence}:

\begin{theorem}\label{T:convergence_quant}

Fix~$\beta > 0$ and consider Algorithm~\ref{L:primal_dual} with at least~$C \zeta^{-1}(\epsilon,\delta,d_\calP)$ samples from each~$\fkD_j$, where~$C$ is an absolute constant, $\zeta^{-1}$ is as in~\eqref{E:zeta}, and~$d_\calP$ is the VC dimension of~$\calP$. Under Assumptions~\ref{A:losses}--\ref{A:oracle}, Algorithm~\ref{L:primal_dual} converges to a probably approximately feasible solution and

\begin{equation}\label{E:convergence_quant}
	P^\star - \rho - \frac{\eta}{2} S - \beta - \epsilon
		\leq \hat{L}\Big( \btheta^{(T)},\bmu^{(T)},\blambda^{(T)} \Big)
		\leq P^\star + \rho + \epsilon_0 + \epsilon
\end{equation}

with probability~$1-\delta$ after~$T$ steps for~$\epsilon_0$ as in~\eqref{E:epsilon0},

\begin{equation}
	S = \sum_{i = 1}^m (B - c_i)^2 + \sum_{j = m+1}^{m+q} \frac{1}{N_j} (B - c_j)^2
		\text{,}
\end{equation}

and

\begin{equation*}
	T \leq \frac{U_0}{2 \eta \beta} + 1
		\text{,}
\end{equation*}

where~$U_0$ is the distance to a pair of optimal dual variables at the beginning of the algorithm, namely,

\begin{equation}
	U_0 = \norm{\bmu^\star}^2 + \sum_{j = m+1}^{m+q} \norm{\blambda_{j}^\star}^2
\end{equation}

for~$(\bmu^\star,\blambda_{j}^\star)$ solutions of~\eqref{P:csl_empirical_dual}.

\end{theorem}

\paragraph{Near-optimality.}

We proceed by proving that

\begin{equation}\label{E:convergence_quant1}
	\hat{D}^\star - \rho - \frac{\eta}{2} S - \beta
		\leq \hat{L}\Big( \btheta^{(T)},\bmu^{(T)},\blambda^{(T)} \Big)
		\leq \hat{D}^\star + \rho
		\text{,}
\end{equation}

from which we obtain~\eqref{E:convergence_quant} by recalling that~$\hat{D}^\star$ is near-PACC~(Theorem~\ref{T:pacc_csl}). More precisely, by using Propositions~\ref{T:param} and~\ref{T:empirical}.

Start by defining the empirical dual function

\begin{equation}\label{E:empirical_dual_function2}
	\hat{d}(\bmu,\blambda_j) \triangleq \min_{\btheta} \hat{L}(\btheta,\bmu,\blambda_j)
		\text{.}
\end{equation}

The upper bound in~\eqref{E:convergence_quant1} then holds trivially from the fact that~$\hat{d}(\bmu,\blambda_j) \leq \hat{D}^\star$ for all~$(\bmu,\blambda_j)$. Then, from the characteristics of the approximate minimizer~$\btheta^{(t)} = \btheta^\dagger(\bmu^{(t)},\blambda^{(t)})$ in Assumption~\ref{A:oracle} we obtain that

\begin{equation}\label{E:convergence_bounded}
	\hat{L}\Big( \btheta^{(t)},\bmu^{(t)},\blambda^{(t)} \Big)
		\leq \hat{D}^\star + \rho
		\text{,}\quad \text{for all } t \geq 0
		\text{.}
\end{equation}

For the lower bound, we rely on the following relaxation of Dankin's classical theorem~\cite[Ch.~3]{Bertsekas15c}:

\begin{lemma}\label{T:subgrad_approx}

Let~$\btheta^\dagger$ be the approximate minimizer of the empirical Lagrangian~\eqref{E:empirical_lagrangian} at~$(\bmu,\blambda_j)$ from Assumption~\ref{A:oracle}. Then, the constraint slacks are \emph{approximate} subgradients of the dual function~\eqref{E:empirical_dual_function2}, i.e.,

\begin{equation}\label{E:subgrad_approx}
\begin{aligned}
	\hat{d}(\bmu,\blambda_j) &\geq \hat{d}(\bmu^\prime,\blambda_j^\prime)
		+ \sum_{i = 1}^m (\mu_i - \mu_i^\prime) \left[ \frac{1}{N_i} \sum_{n_i = 1}^{N_i}
			\ell_i\big( f_{\btheta^\dagger}(\bx_{n_i}), y_{n_i} \big) - c_i \right]
	\\
	{}&+ \sum_{j = m+1}^{m+q} \left[ \frac{1}{N_j} \sum_{n_j = 1}^{N_j}
			\left( \lambda_{j,n_j} - \lambda_{j,n_j}^\prime \right)
				\left( \ell_j\big( f_{\btheta^\dagger}(\bx_{n_j}), y_{n_j} \big) - c_j \right)
		\right]
			- \rho
\end{aligned}
\end{equation}

for all~$(\bmu^\prime,\blambda_j^\prime)$.

\end{lemma}

\begin{proof}

From Assumption~\ref{A:oracle}, we obtain that

\begin{equation}\label{E:subgrad_ineq1}
	d(\bmu^\prime,\blambda_j^\prime) \leq d(\bmu^\prime,\blambda_j^\prime) + d(\bmu,\blambda_j)
		- \hat{L} \big( \btheta^\dagger(\bmu^,\blambda_j),
			\bmu,\blambda_j \big)
		+ \rho
		\text{.}
\end{equation}

Additionally, we can upper bound~\eqref{E:subgrad_ineq1} by replacing the optimal minimizer in~$d(\bmu^\prime,\blambda_j^\prime)$ by any~$\btheta$. In particular, we can choose~$\btheta^\dagger(\bmu,\blambda_j)$ to get

\begin{equation}\label{E:subgrad_ineq2}
	d(\bmu^\prime,\blambda_j^\prime) \leq
		\hat{L} \big( \btheta^\dagger(\bmu,\blambda_j),\bmu^\prime,\blambda_j^\prime \big)
		+ d(\bmu,\blambda_j)
		- \hat{L} \big( \btheta^\dagger(\bmu,\blambda_j),
			\bmu,\blambda_j \big)
			+ \rho
		\text{.}
\end{equation}

Notice from~\eqref{E:empirical_lagrangian} that the first term of the Lagrangians in~\eqref{E:subgrad_ineq2} are identical. By expanding them, \eqref{E:subgrad_ineq2} can then be rearranged as in~\eqref{E:subgrad_approx}.

\end{proof}

To proceed, let~$(\bmu^\star,\blambda_j^\star)$ be solutions of the dual problem~\eqref{P:csl_empirical_dual}. We show next that for at least~$T = O(1/\beta)$, the total distance

\begin{equation}\label{E:lyapunov}
	U_t = \norm{\bmu^{(t)} - \bmu^\star}^2
		+ \sum_{j = m+1}^{m+q} \norm{\blambda_j^{(t)} - \blambda^\star}^2
\end{equation}

decreases by at least~$O(\beta)$. To do so, use the updates from Algorithm~\ref{L:primal_dual} to write~\eqref{E:lyapunov} as

\begin{multline*}
	U_t = \sum_{i = 1}^m \Bigg\{ \Bigg[ \mu_i^{(t-1)} + \eta \bigg(
		\frac{1}{N_i} \sum_{n_i = 1}^{N_i}
			\ell_i\big( f_{\btheta^{(t-1)}}(\bx_{n_i}), y_{n_i} \big) - c_i
		\bigg) \Bigg]_+ - \mu_i^\star \Bigg\}^2
	\\
	{}+ \sum_{j = m+1}^{m+q}
		\sum_{n_j = 1}^{N_j} \bigg\{ \Big[ \lambda_{j,n_j}^{(t-1)} + \frac{\eta}{N_j} \Big(
			\ell_j\big( f_{\btheta^{(t-1)}}(\bx_{n_j}), y_{n_j} \big) - c_j
		\Big) \Big]_+ - \lambda_{j,n_j}^\star \bigg\}^2
		\text{.}
\end{multline*}

Since both~$\bmu^\star$ and~$\blambda^\star$ belong to the non-negative orthant, we can then use the non-expansiveness of the projection~$[\cdot]_+$~\cite{Bertsekas09c} to obtain

\begin{multline}\label{E:algorithm_update}
	U_t = \sum_{i = 1}^m \Bigg[ \mu_i^{(t-1)} + \eta \bigg(
		\frac{1}{N_i} \sum_{n_i = 1}^{N_i}
			\ell_i\big( f_{\btheta^{(t-1)}}(\bx_{n_i}), y_{n_i} \big) - c_i
		\bigg) - \mu_i^\star \Bigg]^2
	\\
	{}+ \sum_{j = m+1}^{m+q}
		\sum_{n_j = 1}^{N_j} \bigg[ \lambda_{j,n_j}^{(t-1)} + \frac{\eta}{N_j} \Big(
			\ell_j\big( f_{\btheta^{(t-1)}}(\bx_{n_j}), y_{n_j} \big) - c_j
		\Big) - \lambda_{j,n_j}^\star \bigg]^2
		\text{.}
\end{multline}

By expanding the norms in~\eqref{E:algorithm_update}, we get that

\begin{multline}\label{E:algorithm_update2}
	U_t \leq U_{t-1}
		+ 2 \eta \Bigg[ \sum_i \left( \mu_i^{(t-1)} - \mu_i^\star \right) \Bigg(
			\frac{1}{N_i} \sum_{n_i = 1}^{N_i}
				\ell_i\big( f_{\btheta^{(t-1)}}(\bx_{n_i}), y_{n_i} \big) - c_i
		\Bigg)
	\\
	{}+ \sum_j \sum_{n_j = 1}^{N_j}
		\frac{1}{N_j} \left( \lambda_{j,n_j}^{(t-1)} - \lambda_{j,n_j}^\star \right) \Big(
			\ell_j\big( f_{\btheta^{(t-1)}}(\bx_{n_j}), y_{n_j} \big) - c_j
		\Big)
		\Bigg]
	\\
	{}+ \eta^2 \Bigg[ \sum_{i = 1}^m \bigg[
		\frac{1}{N_i} \sum_{n_i = 1}^{N_i}
			\ell_i\big( f_{\btheta^{(t-1)}}(\bx_{n_i}), y_{n_i} \big) - c_i
		\bigg]^2
	+  \sum_{j = m+1}^{m+q} \sum_{n_j = 1}^{N_j}
		\frac{1}{N_j^2} \Big[ \ell_j\big( f_{\btheta^{(t-1)}}(\bx_{n_j}), y_{n_j} \big) - c_j \Big]^2
		\Bigg]
		\text{.}
\end{multline}

Using the fact that the~$\ell_i$ are bounded~(Assumption~\ref{A:losses}), the last term in~\eqref{E:algorithm_update2} is upper bounded by

\begin{equation*}
	S = \sum_{i = 1}^m (B - c_i)^2 + \sum_{j = m+1}^{m+q} \frac{1}{N_j} (B - c_j)^2 = O\big( B^2 \big)
		\text{.}
\end{equation*}

What is more, Lemma~\ref{T:subgrad_approx} can be used to bound the second term in~\eqref{E:algorithm_update2} and write

\begin{equation*}
	U_t \leq U_{t-1}
		+ 2 \eta \bigg[ \hat{d}\Big( \bmu^{(t-1)},\blambda_j^{(t-1)} \Big)
			- \hat{D}^\star + \rho \bigg] + \eta^2 S
		\text{,}
\end{equation*}

where we used the fact that~$\hat{D}^\star = \hat{d}\big( \bmu^\star,\blambda_j^\star \big)$. Solving the recursion then yields

\begin{equation}\label{E:algorithm_update3}
	U_t \leq U_{0} + 2 \eta \sum_{t = 0}^{t-1} \Delta_t
		\text{,}
\end{equation}

for

\begin{equation}\label{E:delta_t}
	\Delta_t = \hat{d}\Big( \bmu^{(t-1)},\blambda_j^{(t-1)} \Big) - \hat{D}^\star
		+ \rho + \frac{\eta}{2} S
		\text{.}
\end{equation}

To conclude, notice that~$\hat{d}(\bmu,\blambda_j) \leq \hat{D}^\star$ for all~$(\bmu,\blambda_j)$. Hence, when~$\bmu^{(t)}$ and~$\blambda_j^{(t)}$ are sufficiently far from the optimum and the step size~$\eta$ is sufficiently small, we have~$\Delta_t \leq 0$ and~\eqref{E:algorithm_update3} 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

\begin{equation*}
	\Delta_{T} > -\beta \Leftrightarrow \hat{d}\Big( \bmu^{(t-1)},\blambda_j^{(t-1)} \Big) > \hat{D}^\star - \rho - \frac{\eta}{2} S -\beta
\end{equation*}

What is more, \eqref{E:algorithm_update3} yields

\begin{equation*}
	T \leq \frac{U_{0}}{2 \eta \beta} + 1 = O\big( \beta^{-1} \big)
		\text{.}
\end{equation*}

\hfill$\square$

\section{Numerical experiments: additional details}
\label{X:sims}

\subsection{Invariance and fair learning}

\begin{table}\label{B:adult}
\caption{Preprocessing of the Adult dataset}
\centering
\begin{tabular}{lp{0.7\columnwidth}}
\hline
Variable names & Transformation \\
\hline
fnlwgt & Dropped \\
educational-num & Dropped \\
relationship & Dropped \\
capital-gain & Dropped \\
capital-loss & Dropped \\
education & Grouped the levels Preschool, 1st-4th, 5th-6th, 7th-8th, 9th, 10th, 11th, 12th
\\
race & Grouped the levels Other and Amer-Indian-Eskimo \\
marital-status & Grouped the levels Married-civ-spouse, Married-AF-spouse, Married-spouse-absent\\
marital-status & Grouped the levels Divorced, Separated\\
race & Grouped the levels Other and Amer-Indian-Eskimo\\
native-country &
Grouped the levels Columbia, Cuba, Guatemala, Haiti, Ecuador, El-Salvador, Dominican-Republic, Honduras, Jamaica, Nicaragua, Peru, Trinadad\&Tobago
\\
native-country &
Grouped the levels England, France, Germany, Greece, Holand-Netherlands, Hungary, Italy, Ireland, Portugal, Scotland, Poland, Yugoslavia
\\
native-country &
Grouped the levels Cambodia, Laos, Philippines, Thailand, Vietnam
\\
native-country &
Grouped the levels China, Hong, Taiwan
\\
native-country &
Grouped the levels United-States, Outlying-US(Guam-USVI-etc), Puerto-Rico
\\
age & Binned by quantiles (6 bins)\\
hours-per-week & Binned levels into less than 40 and more than 40\\
\hline
\end{tabular}
\end{table}

We begin with our analysis of the Adult dataset~\cite{Dua17u}, 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~\ref{B:adult}. 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_{\btheta}: \calX \to [0,1]^2$). Using this parametrization, we then pose the constrained learning problem

\begin{prob}\label{P:X_fairness}
	\minimize_{\btheta \in \setR^p}&
		&&\E\!\Big[ \ell_0\big( f_{\btheta}(\bx),y \big) \Big]
	\\
	\subjectto& &&\dkl\! \big( f_{\btheta}(\bx,z) \,\Vert\, f_{\btheta}(\bx,1-z) \big) \leq c
		\text{,}
\end{prob}

where~$z$ is the variable gender~(encoded~$0$ for female and~$1$ for male) and~$\ell_0$ is the negative logistic log-likelihood, i.e., $-\log\left( \left[ f_{\btheta}(\bx) \right]_y \right)$. To solve~\eqref{P:X_fairness}, we use ADAM~\cite{Kingma17a} for step~3 of Algorithm~\ref{L:primal_dual}, 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$. We take~$c = 10^{-3}$. Both classifiers were trained over~$300$ epochs.

Without the constraint in~\eqref{P:X_fairness}, 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~\ref{F:adult_sensitivity}). 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\times10^{-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~\eqref{P:X_fairness} obtained in Algorithm~\ref{L:primal_dual} have a sensitivity interpretation: the larger their value, the harder the constraint is to satisfy~\cite{Bertsekas09c}. Almost~$96\%$ of the dual variables are zero after convergence, meaning that the constraint was tight for only~$4\%$ of the individuals. In Figure~\ref{F:adult_lambdas}a, 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~\ref{F:adult_lambdas}b). Clearly, while attempting to control for gender invariance, the constrained learner also had to overcome other prejudices correlated to sexism in the dataset.

\begin{figure}[tb]
\centering
\includegraphics[width=0.5\columnwidth]{adult_nn_change}
	\caption{Classifier sensitivity on the Adult test set.}
	\label{F:adult_sensitivity}
\end{figure}

\begin{figure}[tb]
\begin{minipage}[c]{0.48\columnwidth}
\centering
\includegraphics[width=\columnwidth]{adult_nn_mus_hist}

{\small \hspace{0.7cm} (a)}
\end{minipage}
\hfill
\begin{minipage}[c]{0.48\columnwidth}
\centering
\includegraphics[width=\columnwidth]{adult_nn_hard_examples}

{\small \hspace{0.7cm} (b)}
\end{minipage}
\caption{Dual variable analysis for Adult dataset: (a)~distribution of the dual variables values and (b)~prevalence of different groups among the~$20\%$ training set examples with largest dual variables.}
	\label{F:adult_lambdas}
\end{figure}

\begin{table}[tb]\label{B:compas}
\caption{Preprocessing of the COMPAS dataset}
\centering
\begin{tabular}{lp{0.7\columnwidth}}
\hline
Variable names & Transformation \\
\hline
age\_cat & Dropped \\
is\_recid & Dropped \\
is\_violent\_recid & Dropped \\
score\_text & Dropped \\
v\_score\_text & Dropped \\
decile\_score & Dropped \\
v\_decile\_score & Dropped \\
race & Grouped the levels Other, Asian, Native American \\
age & Binned by quantiles (5 bins)
\\
priors\_count & Binned levels into 0, 1, 2, 3, 4, and more than 4
\\
juv\_misd\_count & Binned levels into 0, 1, and more than 1
\\
juv\_other\_count & Binned levels into 0, 1, and more than 1
\\
\hline
\end{tabular}
\end{table}

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~\ref{B:compas} 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~\ref{B:compas_results}). 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~\ref{F:compas_mus}). 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~\cite{Kearns18p}.

\subsection{Robust learning}

\begin{table}[tb]\label{B:compas_results}
\caption{Classifier insensitivity on the COMPAS dataset}
\centering
\begin{tabular}{lcc}
\hline
Counterfactual & Unc. (Acc: $69.4\%$) & ACE (Acc: $67.9\%$) \\
\hline
Male $\leftrightarrow$ Female & $21.4\%$ & $0\%$\\
African-American $\leftrightarrow$ Caucasian & $10.86\%$ & $0\%$\\
African-American $\leftrightarrow$ Hispanic & $14.32\%$ & $0.02\%$\\
African-American $\leftrightarrow$ Other & $11.38\%$ & $0\%$\\
Caucasian $\leftrightarrow$ Hispanic & $9.11\%$ & $0\%$\\
Caucasian $\leftrightarrow$ Other & $6.54\%$ & $0\%$\\
Hispanic $\leftrightarrow$ Other & $3.08\%$ & $0\%$\\
Male $\leftrightarrow$ Female + African-American $\leftrightarrow$ Caucasian & $28.84\%$ & $0.02\%$\\
Male $\leftrightarrow$ Female + African-American $\leftrightarrow$ Hispanic & $27.47\%$ & $0\%$\\
Male $\leftrightarrow$ Female + African-American $\leftrightarrow$ Other & $29.17\%$ & $0\%$\\
Male $\leftrightarrow$ Female + Caucasian $\leftrightarrow$ Hispanic & $22.71\%$ & $0\%$\\
Male $\leftrightarrow$ Female + Caucasian $\leftrightarrow$ Other & $24.27\%$ & $0\%$\\
Male $\leftrightarrow$ Female + Hispanic $\leftrightarrow$ Other & $21.15\%$ & $0\%$\\
\hline
\end{tabular}
\end{table}

\begin{figure}[tb]
\centering
\includegraphics[width=0.6\columnwidth]{compas_nn_lambdas}
	\caption{Dual variables of different counterfactual constraints for the COMPAS dataset.}
	\label{F:compas_mus}
\end{figure}

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~\cite{Szegedy14i, Goodfellow14e, Huang15l, Madry18t, Sinha18c, Shaham18u}. To overcome this issue, \cite{Zhang19t} 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~\eqref{P:robustness} for a given adversarial distribution~$\fkA$ 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.

To be concrete, consider the problem of training a ResNet18~\cite{He16d} to classify images from the FMNIST dataset~\cite{Xiao17f}. We reserve~$100$ images from each class sampled at random for validation. When trained without constraints over~$100$ epochs using the ADAM optimizer with the settings in~\cite{Kingma17a} and batches of~$128$ images, it reaches it best accuracy over the validation set after~$67$ epochs. The nominal accuracy of this solution~(over the test set) is~$93.5\%$. However, when the input is attacked using PGD~\cite{Madry18t}, it fails to classify any of the test images for perturbation magnitudes as low as~$\varepsilon = 0.04$~(Figure~\ref{F:fmnist}a). In what follows, $\varepsilon$ indicates the maximum pixel modification allowed~($\ell_\infty$-norm of the perturbation) and we run the PGD attack using a step size of~$\varepsilon/30$ for~$50$ iterations and display the worst result over~$10$ restarts, unless stated otherwise.

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~\eqref{P:robustness}. 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~\ref{F:fmnist}a 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~$\fkA$ as

\begin{equation}\label{E:hierarchical_epsilon}
	\Pr\left( \fkA \right) = \Pr\left( \fkA \mid \varepsilon \right) \Pr\left( \varepsilon \right)
		\text{,}
\end{equation}

where~$\Pr\left( \fkA \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~\ref{F:fmnist}a we take~$\varepsilon \sim 0.25 \times \textup{Beta}(3,8)$~(Figure~\ref{F:fmnist}b). 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$.

Similar results are obtained when training a ResNet18~\cite{He16d} to classify images in the CIFAR-10 dataset. The training was performed as above, once again reserving~$100$ random images from each class sampled for validation. The unconstrained classifier trained over~$100$ epochs reached it best accuracy over the validation set after~$82$ epochs, which corresponds to a nominal test accuracy of~$85.4\%$. However, when the input is attacked using PGD~\cite{Madry18t}, the accuracy falls to~$5\%$ already for~$\varepsilon = 0.01$~(Figure~\ref{F:cifar}a). When using the fixed~$\varepsilon$ training method described above, we once again observe a trade-off between nominal accuracy and robustness. This can, however, be improved using the hierarchical training technique from~\eqref{E:hierarchical_epsilon}. Taking~$\varepsilon \sim 0.1 \times \textup{Beta}(3,10)$, such that~$\E \left[ \varepsilon \right] = 0.02$, we obtain the same nominal accuracy as for the fixed-$\varepsilon$, but improve the robustness for higher perturbation values.

\begin{figure}[tb]
\begin{minipage}[c]{0.48\columnwidth}
\centering
\includegraphics[width=\columnwidth]{fmnist_accuracy}

{\small \hspace{0.7cm} (a)}
\end{minipage}
\hfill
\begin{minipage}[c]{0.48\columnwidth}
\centering
\includegraphics[width=\columnwidth]{fmnist_pdf}

{\small \hspace{0.7cm} (b)}
\end{minipage}
\caption{Robust constrained learning (FMNIST): (a)~Accuracy of classifiers under the PGD attack for different perturbation magnitudes and (b)~distribution of~$\varepsilon$ used during training.}
	\label{F:fmnist}
\end{figure}

\begin{figure}[tb]
\begin{minipage}[c]{0.48\columnwidth}
\centering
\includegraphics[width=\columnwidth]{cifar_accuracy}

{\small \hspace{0.7cm} (a)}
\end{minipage}
\hfill
\begin{minipage}[c]{0.48\columnwidth}
\centering
\includegraphics[width=\columnwidth]{cifar_pdf}

{\small \hspace{0.7cm} (b)}
\end{minipage}
\caption{Robust constrained learning (CIFAR-10): (a)~Accuracy of classifiers under the PGD attack for different perturbation magnitudes and (b)~distribution of~$\varepsilon$ used during training.}
	\label{F:cifar}
\end{figure}

\fi

\end{document}


TITLE: Is the ideal $I=(X-Y, X+Y) $ in the polynomial ring $ \mathbb{Z} [X,Y]$ a prime ideal?
QUESTION [0 upvotes]: Is the ideal $I=(X-Y, X+Y) $ in the polynomial ring $ \mathbb{Z} [X,Y]$ a prime ideal? Does replacing $ \mathbb{Z} [X,Y]$ by $ \mathbb{C} [X,Y]$ affect the nature of the given ideal?

My Attempt

As for any commutative ring with unity, $ R$ and and its ideal $I$, the quotient ring $ R/I$ is an integral domain iff $I$ is a prime ideal in $R$.
Here using ring isomorphism theorems,  the quotient ring
$ \mathbb{Z}[X,Y]/ (X-Y,X+Y) $   is  isomorphic to the quotient ring $ \mathbb{Z}[X]/ (2X) $. I was not able to proceed further.
Is the ideal $ I= (X-Y, X+ Y) $ is same as the ideal $ (X, Y)$ in $ \mathbb{Z} [X,Y] $?

REPLY [1 votes]: Using your quotient description, you can see right away that $2*X=0$, but neither $2$ nor $X$ is zero in the quotient, so that the ring has zero divisors. A quotient by a prime is an integral domain and would not have zero divisors, so it isn’t a prime ideal.
In the case of $\mathbb C$ or any field not or characteristic $2$, the same work gets you to $\mathbb C[X]/(2X)$, but now you can divide by $2$ and so the ideal is $X$, which leaves you with just $\mathbb C$. That is a field, so you must have quotiented by a maximal, hence prime, ideal.