Near-Optimal Solutions of Constrained Learning Problems
Authors: Juan Elenter
Luiz F. O. Chamon
Alejandro Ribeiro
Venue: ICLR 2024 poster (2024)
Keywords: Constrained Learning
Convex Optimization
Duality
Constrained Optimization
Fairness
Primary area: optimization

Abstract: With the widespread adoption of machine learning systems, the need to curtail their behavior has become increasingly apparent. This is evidenced by recent advancements towards developing models that satisfy robustness, safety, and fairness requirements. These requirements can be imposed (with generalization guarantees) by formulating constrained learning problems that can then be tackled by dual ascent algorithms. Yet, though these algorithms converge in objective value, even in non-convex settings, they cannot guarantee that their outcome is feasible. Doing so requires randomizing over all iterates, which is impractical in virtually any modern applications. Still, final iterates have been observed to perform well in practice. In this work, we address this gap between theory and practice by characterizing the constraint violation of Lagrangian minimizers associated with optimal dual variables, despite lack of convexity. To do this, we leverage the fact that non-convex, finite-dimensional constrained learning problems can be seen as parametrizations of convex, functional problems. Our results show that rich parametrizations effectively mitigate the issue of feasibility in dual methods, shedding light on prior empirical successes of dual learning. We illustrate our findings in fair learning tasks.

Published as a conference paper at ICLR 2024
NEAR-OPTIMAL SOLUTIONS OF CONSTRAINED LEARNING PROBLEMS
Juan Elenter*
Luiz F. O. Chamon University of Stuttgart
Alejandro Ribeiro University of Pennsylvania
University of Pennsylvania
ABSTRACT
With the widespread adoption of machine learning systems, the need to curtail their behavior has become increasingly apparent. This is evidenced by recent advancements towards developing models that satisfy robustness, safety, and fair- ness requirements. These requirements can be imposed (with generalization guar- antees) by formulating constrained learning problems that can then be tackled by dual ascent algorithms. Yet, though these algorithms converge in objective value, even in non-convex settings, they cannot guarantee that their outcome is feasible. Doing so requires randomizing over all iterates, which is impractical in virtu- ally any modern applications. Still, final iterates have been observed to perform well in practice. In this work, we address this gap between theory and practice by characterizing the constraint violation of Lagrangian minimizers associated with optimal dual variables, despite lack of convexity. To do this, we leverage the fact that non-convex, finite-dimensional constrained learning problems can be convex, functional problems. Our results show that
seen as parametrizations rich parametrizations effectively mitigate the issue of feasibility in dual methods, shedding light on prior empirical successes of dual learning. We illustrate our findings in fair learning tasks.
INTRODUCTION
Machine learning (ML) has become core technology of information systems, reaching critical applications from medical diagnostics (Engelhard et al., 2023) to autonomous driving (Kiran et al., 2021). Consequently, has become paramount to develop ML systems that not only excel their main task, but also adhere to requirements such as faimess and robustness.
Since virtually all ML models are trained using empirical risk minimization (ERM) (Vapnik, 1999), natural way to impose requirements is to explicitly add constraints to these optimization prob- lems (Cotter et al., 2018; Chamon Ribeiro, 2020; Velloso Van Hentenryck, 2020; Fioretto al., 2021; Chamon et al., 2023). Recent works (Chamon & Ribeiro, 2020; Chamon et al., 2023) have shown that from a probably approximately correct (PAC) perspective, constrained learning essen- tially hard classical learning and that, despite non-convexity, it can be tackled using dual al- gorithms that only involve a sequence of regularized, unconstrained ERM problems. This approach has been used in several domains, such federated learning (Shen al., 2022), fairesss (Cotter et al., 2019; Tran et al., 2021), active learning (Elenter et al., 2022), adversarial robustness (Robey al., 2021), and data augmentation (Hounie et al., 2022).
These theoretical works, however, only address (i) the estimation error, arising from the empir- ical approximation of expectations in ERM and (ii) the approximation error, arising from using finite-dimensional models with limited functional representation capability. These are the leading challenges in unconstrained learning since the convergence properties of unconstrained optimization algorithms are well-understood in convex (c.g., (Bertsekas, 1997; Boyd & Vandenberghe, 2004)) as well as many non-convex settings (e.g., for overparametrized models (Soltanolkotabi et al., 2018: Brutzkus & Globerson, 2017; Ge et al., 2017)). This is not the case in constrained learning, where (iii) the optimization error can play a crucial role.
"orrreponningg author: elenter clenter@sscasuupemmcch

---

Published as a conference paper at ICLR 2024
Indeed, dual methods severely limited when it comes recovering feasible solutions for strained problems. In fact, not only might their primal iterates not converge to a feasible point [e.g, Fig. (Cotter et al., 2019, Section 6.3.1)], but they might not converge at all, displaying cy- clostationary behavior instead. This problem is hard even from an algorithmic complexity point- of-view (Daskalakis al., 2021). For convex problems, this issue be overcome by simply averaging the iterates (Nedić & Ozdaglar, 2009). Non-convex problems, however, require random- ization (Kearns et al., 2018; Agarwal et al., 2018; Goh et al., 2016; Chamon et al., 2023). This approach is not only impractical, given the need to store growing sequence of primal iterates, but also raises ethical considerations, since randomization further hinders explainability.
Yet, it has been observed that for typical modern ML tasks, taking the last or best iterate can perform well in practice (Cotter et al., 2018; Chamon Ribeiro, 2020; Chamon et al., 2023; Robey et al., 2021; Elenter et al., 2022; Hounie et al., 2022; Shen et al., 2022; Gallego-Posade et al., 2022). This work addresses this gap between theory and practice by characterizing the sub-optimality and infeasibility of primal solutions associated with optimal dual variables. To do we observe that, though non-convex, constrained learning problems are generally parametrized versions of benign functional optimization problems. We then show that for sufficiently rich parametrizations, solutions obtained by dual algorithms closely approximate these functional solutions, not only in terms of optimal value per (Cotter et al., 2019; Chamon & Ribeiro, 2020; Chamon et al., 2023), but also in terms of constraint satisfaction. This implies that dual ascent methods yield near-optimal and near-feasible solutions without randomization, despite non-convexity.
2 CONSTRAINED LEARNING
2.1 STATISTICAL CONSTRAINED RISK MINIMIZATION
As in classical learning, constrained learning tasks can be formulated as a statistical optimization problem, namely,
mimin
min REB
lo(fe) == E (o(f(z))
(Pp)
S. (fa) = (x,)))
(ff L v)] S 00, i 1=
where fo : X' + is function associated with the parameter vector E C I' and the hypothesis class Fg (fe subset of some compact functional space F C 2 Throughout the paper. we use the subscript (parametrized) to refer to quantities related to (Pş). The functionals & F + R, denote expected risks for loss functions Z, In this setting, lo can be interpreted as a top-line metric (e.g., accuracy), while the functionals f encode statistical requirements that the solution must satisfy (see example below).
Q} induced by this family of functions is assumed to be
O, m,
Learning under counterfactual fairness constraints. Consider the problem of learning an accurate classifier that is insensitive to changes in set of protected attributes. Due to the correlation between these attributes and other features, simply hiding them from the model not enough to guarantee this insensitivity. To do so, this requirement must be enforced explicitly. Indeed, consider the COMPAS study (ProPublica, 2020), with the goal of predicting recidivism based on past offense data while controlling for gender and racial bias. Explicitly, let to denote the cross-entropy By collecting the protected features into the separate vector z, i.e., formulate the problem of learning a predictor insensitive to transformations ps
Example 2.1:
loss (o(2, y) = - log [yyy
[ 2]. that encompass all possible single variable modifications of z. Explicitly.
min E to (fo(z), v) PERP s. to [So =) (x))) Se, i=
where c > 0 is the desired sensitivity level. Note that this formulation corresponds to the notion of (average) counterfactual faimess from (Kusner et al., 2018, Definition 5). In this setting, each constraint represents a requirement that the output of the classifier be near-imvariant to changes in the protected features (here, gender and race). For instance, the prediction should be (almost) the
2

---

Published as a conference paper at ICLR 2024
constraint violation.
Percentage of infeasible iterations.
Fay
Herd
Concrint Average
Infeasible Iterations (9%
6/2
Contraint Voia
30
feasibiity
20
-2/2
230
250
300
350 400
2
Iteration
Constraint
Figure 1: Feastibility of primal iterates in a constrained learning problem with fairness requirements. Left: Example of hard constraint which oscillates between feasibiliy and infeasibility, and an easy constraint which remains feasible for all iterations. Right: After training accuracy has settled (around half of training epochs), all but the last constraint are infeasible 30-45 % of the iterations. In fact, at least one constraint is violated on 85% of the iterations shown. We cannot therefore stop the algorithm and expect obtain a feasible solution.
same whether, all else being equal, the gender of the input is changed from "Male" to "Female" (and vice-versa) or the race is changed from "Caucasian"
Affrica--Americnn.
Note that even if the losses (g) y) are convex in (ÿ. y) (as the case of the cross-entropy), the functions l need not be convex in 0. This is the case, for instance, for typical modern ML mod- els (e.g., if fo is a neural network, NN). Hence, (Pp) is usually a non-convex optimization problem for which there is straightforward way to project onto the feasibility set (e.g., onto the set of fair NNs). light of these challenges, we turn to Lagrangian duality.
2.2 LEARNING IN THE DUAL DOMAIN
Let the Lagrangian L F x Rm R be defined
L(ø, A) = lo(d) + +X
(1)
where [e,, fm is a vector-valued functional collecting the constraints of (Pp). For reasons that will become apparent later, we define L over F 2 Fg. For fixed dual variable Xy. the Lagrangian [fee Ap) is regularized version of (Pp), where l acts as the regularizing functional. This leads to the dual function
(Ap) = min L(fo, Ap), dEE
(2)
based on which we can in turn define the dual problem of (Pp) as
D max gp (Ap).
(D,)
2
This saddle-point problem can be viewed as two-player game or as regularized learning problem, where the regularization parameter is also an optimization variable. As such, (Dp) is relaxation of (P,), implying that D; Pr. This is known weak duality (Bertsekas, 1997).
The dual function 9p in (2) is concave, irrespective of whether (P,) convex (it is the pointwise minimum of family of affine functions on (Boyd & Vandenberghe, 2004)). As such, though Ip may not be differentiable, it can be equipped with supergradients that provide potential ascent directions. Explicitly, vector
R" - R at a point x if f===)= h(x) 2 s (z x) for all z. The set of all supergradients of / at x is called the superdifferential and is denoted Ōh(x). When the losses E, are continuous, the superdifferential of Io admits simple description (Nedić & Ozdaglar, 2009), namely,
R. is supergradient of the concave function
(gp(>p) conv [e(ff(Ap)) fo(Ap) (xp),
where cOnv(S) denotes the convex hull of the set S and Fÿ (Ap) denotes the set of Lagrangian minimizers (e()p) associated to the multiplier Ap. i.c.,
(Ap) = arg min L(fe, Ap)
(3)
3

---

Published as a conference paper at ICLR 2024
Algorithm Dual Constrained Learning
Inputs: number of iterations T E step size 1) 0.
2: Initialize: X(1) 0
3: for .,..., T do
4: Obtain (t) such that
ft( fol x(0
min L(fo, X(1) 8E6
5: Update dual variables
l + max
6: end for
In particular, this leads to an algorithm for solving (Dp) known as projected supergradient ascent (Polyak, 1987; Shor, 2013) that we summarize Algorithm 1.
When executing Algorithm 1, dual iterates (L) move in ascent directions of the concave function Ip (Shor, 2013, Section 2.4). Yet, the sequence of primal iterates (t) obtained as a by- product need not approach the set of solutions of (Pp). The experiment in Figure showcases this behaviour and illustrates that, in general, one can not simply stop the dual ascent algorithm at any iteration and expect the primal iterate ft( to be feasible. Additionally, the Lagrangian minimizers are not unique. In particular, for an optimal dual variable X; E Ap, the set F3 (Ap) is typically not a singleton and could contain infeasible elements (i.e. (A() > 0 for some 2 1). Even more so, as (t) approaches Ap the constraint satisfaction of primal iterates can exhibit pathological cyclostationary behaviour, where one or more constraints oscillate between feasibility and infeasi- bility, see e.g.. (Cotter et al., 2019, Section 6.3.1). For these reasons, convergence guarantees for non-convex optimization problems typically require randomization over (a subset of) the sequence {ff(tt)][1 which is far from practical [see e,g, (Agarwal et al., 2018, Theorem 2), (Kearns et al., 2018, Theorem 1), (Cotter al., 2019, Theorem 2), (Chamon al., 2023, Theorem 3)]. In the sequel, we show conditions under which this is not necessary.
3 NEAR-OPTIMAN SOLUTIONS OF CONSTRAINED LEARNING PROBLEMS
Primal iterates obtained as a by-product of the dual ascent method in Algorithm 1 may fail to be solutions of (Pp). However, it has been observed that taking the last or best iterate can perform well in practice. This can be understood by viewing (Pp) as the parametrized version of benign functional program, ammenable to Lagrangian formulation. This imparametrized problem does not suffer from the same limitations (P₂) in terms of primal recovery and we thus use its solution as a reference point to measure the sub-optimality of the primal iterates obtained with Algorithm 1.
The umparametrized constrained learning problem is defined as
P min DEF
(o(#)
(Pu)
S.o (1(0) & O, i i= 1,.,, m
where is convex, compact subset of an 2 space. For instance, F can be subset of the space of continuous functions or reproducing kemnel Hilbert space (RKHS) and Fg can be induced by a neural network architecture with smooth activations or finite linear combinations of kernels. In both cases, we know that Fa uniformly approximate F arbitrarily well the dimension of 0 grows (Homiik, 1991; Berlinct Thomas-Agnan, 2011). The smallest choice of is in fact cony(Fo) (closed convex hull of Fo).
Analogous to the definitions from Section 2.1,
9u(Aa) == min L(Ø, Aa) dEF
4

---

Published as a conference paper at ICLR 2024
denotes the unparametrized dual function, F (X.u) arg min L(Ø, Au) is the set of Lagrangian minimizers (Axu) associated to Au and
D max Iu (Au) 2=
(Dw)
is the unparametrized dual problem. The subseript u is used to denote quantities related to the unparametrized problem (Pu). We now present two assumptions that allow us to characterize the relation between the dual and primal solutions of problem D...
Assumption 3.1. The functionals & i = ,, are convex and M Lipschitz continuous in F. Additionally, to Po -storngyy convex.
Note that we require convexity of the losses with respect to their functional arguments and not model parameters which holds for most typical losses, e.g. mean squared error and cross-entropy loss. Assumption 3.2. There exists & E F such that E(() < min(0, (()(A))) e((()))) for all ((x;) E F(X2), fo (x,) E (x() and X; E A
Assumption 3.2 is a stronger version of Slater's constraint qualification, which requires only (()) x 0. Here, we require the existence of (suboptimal) candidate & that is strictly feasible even for perturbed versions of (P.)..
Under these assumptions, the Lagrangian minimizer is unique. This makes the superdifferential of the dual function singleton at every Aa: (X.,) = {L()(>a))) which means that the dual function gn (Aw) is differentiable (Shor, 2013). Let o² be a solution of problem (P.).. Assumptions 3.1 and 3.2 imply that strong duality (i.e. Pt = DW holds in this problem, and that at X there is unique Lagrangian minimizer o (Xt,) = 6² which is, by definition, feasible (Bertsekas, 1997).
The only difference between problems (Pp) and (P.) is the set over which the optimization is carried out. Thus, if the parametrization θ is rich enough (c.g. deep neural networks), the set F& is essen- tially the same as F, and we should expect the properties of the solutions to problems (Dp) and (Dw) to be similar. This insight leads us to the Vー near universality of the parametrization assumption. Assumption 3.3. For all & F, there exists 0 θ such that || fo S v.
The constant v in Assumption 3.3 is a measure of how well Fg covers F. Consider, for instance, that F is the set of continuous functions and Fg the set of functions implementable with two- layer neural network with sigmoid activations and K hidden neurons. If the parametrization has 10 neurons in the hidden layer, it is considerably worse representing elements in F than one with 1000 neurons. While determining the exact value of v is in general not straightforward, any v > 0 can be achieved for large enough number of neurons (Hornik, 1991). The same holds for the number of kernels and an RKHS (Berlinet & Thomas-Agnan, 2011).
Given these facts, is legitimate to ask: how close are the elements of Fo() to o in terms their optimality and constraint satisfaction? Bounding these errors would theoretically justify the use of last primal iterates, doing away with the need for randomization.
3.1 NEAR-OPTIMALITY AND FEAR-FEASIBILITY OF DUAL LEARNING
A key challenge of using duality to undertake (Pp) is that the value D of the dual problem (Dp) need not be good approximation of the value Pe of (Pp) (i.e, lack of strong duality). This was tackled in (Chamon et al., 2023, Prop. 3.3). Explicitly, under Assumptions 3.1.3.3, the duality gap of problem (Pp) is bounded as in
PF - DJ S Me(1 + =
(4)
where X maximizes 0p()) (A) + My||A|ia This result, however, only shows that the dual problem can be used to approximate the value of the constrained problem (P,). It says nothing about whether it can provide (near- ffessblee solution, which is the main issue addressed in this paper. We next characterize the sub-optimality and constraint violation of the Lagrangian minimizers fo (A7) e (Ap) by comparing these primal variables with the solution of the unparametrized problem o*.
The curvature of the unparametrtized dual function gu (A.,) around its optimum is central to this analysis. We will first provide result with the following assumption this curvature and then
5

---

Published as a conference paper at ICLR 2024
describe its connection to the properties of (Pp). Let Hy {yy + (1-7)>3 Y E [0. 1]} denote
the segment connecting X and X..
Assumption 3.4. The dual function gu is Pg pt-stnoggl concave and 3, s-mooth along Hx.
The following proposition characterizes the constraint violation for all fo(2²) E FT())) with re- spect to Ø"; the optimal, feasible solution of the unparametrized problem.
Proposition 3.1. Under Assumptions 3.1-3.4, any (x())) E (2)) approximates the constraint value of the solution 6" of (Pa) as in:
3g 1g
(0))))((0)1111))) (())) 23, (1A211))
1+
Since (P.) is feasible, {((²) is non-positive. Hence, the approximation bound in Proposition 3.1 is stronger than an infeasibility bound on fe(A)). Indeed, it says not that ((p))) I 0, but that it approximates the constraint values of the optimal solution o* The ratio 9 (i.e. the condition number of gu), which determines optimal step sizes in dual ascent methods (Polyak, 1987), also plays a key role here, representing the tension between two fundamental forces driving this bound. On the one hand, the sensitivity of the dual problems, controlled by Mg. which determines how different X and X; are. On the other hand, the sensitivity of the primal problems, linked to the smoothness constant fy. which determines the effect of this difference on feasibility.
Nevertheless, Proposition 3.1 remains abstract. To connect it to the properties of (Pp), we rely on the following assumptions to obtain bounds on jıg and Bg. Assumption 3.5.
The functionals l O,...,m are B-smooth on F.
Assumption 3.6. The Jacobian Dol(d") is full-row rank at the optimum, i.e, there exists > O such that inf | Del(d")) 2 where Dzl(ő") denotes the Fréchet derivative of the functional & at 6² (see definition in Appendix A.
Assumption 3.6 is unlike the previous regularity assumptions control and is not straightforward to satisfy at first sight. It is, however, a typical assumption used to derive duality results convex optimization known linear independence constraint qualification or LICQ (Bertsekas, 1997). As such, it could be replaced by different constraint qualification, such as a stricter version of Assumption 3.2. This is. however, left for future work. Under these assumptions, we can describe the curvature of Iu in terms of the problem parameters as follows.
which practitioner has full
Lemma 3.1. Under assumptions 3.1, 3.2, 3.5 and 3.6. 9u(Au) is My stroongyy concave and o² By smooth on H2 for Hg (1++ and By vMM? where A max 11. 11
Having characterized the curvature of the unparametrized dual function Ja- we can now state the main result of this section, which puts together Proposition 3.1, Lemma 1, and the near-optimality result from (Chamon et al., 2023) in (4) to bound the near-optimality and near-feasibility of La- grangian minimizers associated to optimal dual variables.
Theorem 3.1. Under assumptions 3.1, 3.2, 3.3, 3.5 and 3.6, the sub-optimality and infeasi- bility of any fo(2;) F(X;) is bounded by:
Mv
[e((o()))) - 100 < M 1 + A]]
2m
(1 11pll))
(5)
110
P - (o([a(()))) < (1 + IA + + + 1Ap
(6)
with K1 Kgg
8 A max ||; |I. } and I' as in (4).
Theorem 3.1 shows that the dual problem (D,,) not only approximates the value P of (Pp), but also provides approximate solutions for it. The quality of these approximations depends on three factors. First, the sensitivity of the learning problem, as captured by the Lipschitz constant M and the constants Ki and Kg, that correspond to the condition numbers of the constraint Jacobian and the

---

Published as a conference paper at ICLR 2024
objective function respectively. Overall, these quantities measure how well-conditionn the problem is. Second, the requirements difficulty. Indeed, the optimal dual variables can be seen as measures of the sensitivity of the objective value with respect to constraint perturbations (see, e.g., (Boyd & Vandenberghe, 2004)). Hence, the more stringent the constraints, the larger | and/or ||
Finally, the approximation emrrr depends on the factor that denotes the richness of the parametriza- tion, i.e., how good it is at approximating functions in F (Assumption 3.3). In fact, Theorem 3.1 shows that as the model capacity increases (u decreases), the approximation bounds (5)-(6) improve. This behavior is not trivial. Indeed, while we expect that richer parametrizations lead to lower ap- proximation errors, Theorem 3.1 states that they also make solving the optimization problem (Pp) easier, since dual solutions then provide better approximations of primal solutions. Observe that the effect of these factors on feasibility in (5) are similar to those on optimality (6) and, e-g. (Chamon et al., 2023). Next, we leverage these results to provide convergence guarantees for Algorithm 1. But first, we outline the main ideas behind the proof of Proposition 3.1.
3.2 PROOF SKETCH
In this section, we provide brief outline of the proof of Theorem 3.1. We begin by decomposing the distance between constraint violations as
[[((f(A{]) - {(0*)ll2 = (((((()))))))))))))))))()))))( - + -(0
(7)
- {(((fo(())) - =(6 + ([(((()))) - e((())))
The first term captures the effect of parametrizing the hypothesis class for a fixed dual variable. In contrast, the second term characterizes the effect of changing the dual variables on the un- parametrized Lagrangian minimizer. This is made clear in (7) by using the fact that 6= o(X;) (see discussion in Section 3). the sequel, we analyze each of these terms separately. For conciseness, all technical definitions from this section are deferred to Appendix A.1.
3.2.1 DUAL VARIABLE PERTURBATION
We begin by analyzing the second term in (7). Recall from the beginning of Section 3 that un- der Assumption 3.1-3.2, it holds that AAga(A) (()()). Hence, [[(()()))) (()()))) | Ny (X,) -2g)) (xgg(A))le (22)l2.. Using the By -smoothness of gu. this gradient difference can be bounded using 1 12. The latter can in turn be bounded by combining the v-universality of the parametrization (Assumption 3,3) and convex optimization perturbation results to obtain:
Proposition 3.2. Under assumptions 3. 1-34,,4, the distance between the constraint violations of 5(X²) and ((x)) bounded by:
82 2 Me(1 1121l1)
[((((A))) E(O(A < 2 Mg
(8)
3.2.2 HYPOTHESIS CLASS PERTURBATION
Bounding the first term in (7) is less straightforward. To do so, we rely on the perturbation function of the unparametrized problem (P.). defined as
(c) min dEF
to(Ø)
(P.)
5.00 (()) + 30.
for some perturbation é E R". Intuitively, (c) quantifies the impact on the objective value of modifying the constraint specifications by Note that the unparametrized problem (P.) is recovered
for = O. Motivated by the fact that we can get strong handle on the sensitivity of the perturbation
function (P.), we seek to bound [[((f(();)) E(d()t)) Il2 by instead analyzing IPt (e,)) (c.)
for 6p = - -{(so();) and e = -((((A))) Indeed, holds for every À Ry that Pt()) =
(A), where i denotes the Fenchel conjugate (see Appendix A.4). We can therefore relate the curvature of 9N to that (c) (Kakade et al., 2009) obtain:
Proposition 3.3. Under assumptions 3. 3.1.3.4, the distance between constraint violations associated to the parametrization of the hypothesis class is given by:
[[(()()))) E(Jo(2;))11 < 23, Me + 112)11)
7

---

Published as a conference paper at ICLR 2024
Using Propositions 3.2-3.3 in (7) yields Proposition 3.1. Theorem 3.1 is then obtained by further leveraging Lemma 3.1 and the bound on the duality gap P D in (4) (see Appendix A.1..2).
BEST ITERATE CONVERGENCE
In this section, we leverage the connection between the parameterized [ef. (Pp) and (D₂) and unparameterized [ef. (P.) and (Dw)) problems to analyze the convergence of Algorithm 1. Seeking a more general result, we relax Steps 4 and to allow for approximate Lagrangian minimization and the use of stochastic supergradients of the dual function respectively.
Explicitly, we assume that for all 6, the oracle in Step returns function (t) such that
(L)) Ap) S min L(Ja, A(()) + P: 6EB
for approximation emorr 2 0. In contrast to Step 4, equation 9 accounts for potential numerical and approximation errors the computation of the Lagrangian minimizer. The existence of such p-approximate oracle is typical assumption in the analysis of dual algorithms (Cotter et al., 2019; Chamon et al., 2023; Kearns et al., 2018) and often justified by substantial theoretical and empirical evidence that many ML optimization problems can be efficiently solved despite non- convexity. That is the case, e.g., for deep neural networks (Zhang et al., 2021; Brutzkus & Globerson, 2017: Soltanolkotabi al., 2018; Ge et al., 2017). Additionally, consider that the dual variable update in Step is replaced by
11 max (0,A((0) +n
(10)
where (t)) are conditionally unbiased estimates of the statistical risks (s()(()), i.e., (((()(()))) (()) This stochastic update accounts for, e.g., the use of independent sample batches to estimate the constraint slacks (((j)).
The following Lemma establishes the convergence of the best iterate of (9)-(10) i.e., of the dual variables (t) that yield the largest dual function for all t.
mato, 9p (xs) be the maximum value of the parametrized dual function up to time t. Then, for all to > 1, it holds that
Lemma 4.1. Let op (1)((())
(1:52
lim 9p (t(A(to)) 2 D 1000
+D) a.s.,
where 52 E. E[(A080)))10)]
The existence of finite S is implied by the assumption that Fg C C L Lemma 4.1 implies that for any 8 > 0, there exists a finite t" such that A(t*) achieves the value D
n² + + +p++8
We denote this iterate Abest Note that the step size yj can be reduced so as to make g arbitrarily close to D p (asymptotically). In view of the bound the duality gap Py P in (4), Lemma 4.1 implies that best is near-optimal. Combine with the near-feasibility results from Section 3, we can also bound the constraint violations of the Lagragian minimizer associated with best
Proposition 4.1. Let best be any dual iterate that achieves 9p (Dbet)) 2 Dí Suppose there exists & E F such that E(() X min{0, ((m()) ((S, ((te())))))) and that Assumptions 3.1, 3.3, 3.5, and 3.6 hold. Then,
- (11S2/2 p).
8/82
2 + +D) (
Bg Bg
[((())) ((6((Aes)))1 5 2/g [Mv[1+ + 1
(1+
Mo 0² where Fg g=(1+max X J1A 1:)))*
Reasonably, the bound in Proposition 4.1 is governed by the same terms as Theorem 3.1. Here, however, the bound is the loosened by the sub-optimality of ) best with respect Xg.
8

---

Published as a conference paper at ICLR 2024
Houlrumn conorait swwMi tecradao caparty.
2
30 14
Uncoortsieed
Lan
Al. Assrics Cacarito
Gadde
Mi. fundtaan Hipuole
Amerea Olier
Conctio Higesi
Odeor
Conario
All.
Figure 2: Left: the Unconstrained model performs better in terms of average test accuracy than both the Last and Randomized model. Middle: Both constrained models do better in terms of Counterfactual Fairness. The key point is that the Last iterate is never far from the Randomized one terms constraint violation. Right: As the richness of the parametrization increases the maximum constraint violation (i.e: size of the oscillations) decreases.
5 EXPERIMENTAL VALIDATION
To illustrate the theoretical results from Sections 3 and 4, we return to the counterfactually fair learn- ing problem from Example 2.1. We work with the COMPAS dataset, where the task is to predict recidivism while remaining insensitive to the protected variables gender and race, which can take the values ["Male", "Female"] and ['African American". "Hispanic", "Caucasian", "Other"] respec- tively. We take the parametrized model fe to be 2-layer NÑ with sigmoid activations, that the resulting constrained learning problem non-convex. Further experimental details are provided in Appendix A.16. We compare the accuracy and constraint satisfaction of three models: an uncon- strained predictor, trained without any additional constraints; a last iterate predictor, corresponding the final iterate (T') of an empirical version of Algorithm and a randomized predictor that samples model uniformly at random from the sequence of primal iterates {fo(t))) for each prediction.
As shown in Fig. 2 (Left), the unconstrained model is slightly better than the two constrained ones in terms of predictive accuracy. This advantage comes the cost of less counterfactually fair pre- dictions, i.e., a model more sensitive to the protected features (Fig. 2, Middle). The key point of this experiment, however, is that the last iterate and randomized predictors provide similar accuracy and constraint satisfaction, as predicted by Theorem 3.1. Additionally, Fig. 2 (Right) showcases the impact of the parametrization richness on the constraint violation of last primal iterates. We control this richness by means of projecting the data onto a lower dimensional space using a fixed, random linear map. Note that, as Theorem 3.1 indicates, the constraint violation decreases by up to an order of magnitude as we increase the capacity of the model. As have observed before, this behavior is not straightforward: though richer parametrizations are expected to lead to lower approximation errors, it is not immediate that it should make the optimization problem (P,) easier to solve.
CONCLUSION
We analyzed primal iterates obtained from a dual ascent method when solving the Lagrangian dual of primal non-convex constrained learning problem. The primal problem in question is the parametrized version of convex functional program, which is amenable to a Lagrangian formu- lation. Specifically, we characterized how far these predictors are from the solution of the un- parametrized problem in terms of their optimality and constraint violation. This result led a characterization of the infcasibility of best primal iterates and elucidated the role of the capacity of the model and the curvature of the objective. These guarantees bridge a gap between theory and practice in constrained learning, shedding light on when and why randomization is unnecessary. The findings presented in this work can be extended in several ways. For instance, a study of the estimation error incurred by minimizing the empirical Lagrangian in Algorithm I could be added. It might also be possible to characterize the curvature of the dual function by alternative means, which could potentially lift assumptions on the unparametrized problem.

---

Published as a conference paper at ICLR 2024
6.1 ACKNOWLEDGMENTE
The work of A. Ribeiro and J. Elenter is supported by NSF-Simons MoDL, Award 2031985, NSF AI Institutes program. The work of L.F.O.. Chamon funded by the Deutsche Forschungsgemein- schaft (DFG, German Research Foundation) under Germany's Excellence Strategy (EXC 2075- 390740016).
REFERENCES
Alckh Agarwal, Alina Beygelzimer, Miroslav Dudik, John Langford, and Hanna Wallach. A reduc- tions approach to fair classification. In International conference on machine learning, pp. 60-69. PMLR, 2018.
Tamer Başar and Pierre Bernhard. H-infinity optimal control and related minimax design problems: dynamic game approuch. Springer Science & Business Media, 2008
Alain Berlinet and Christine Thomas-Agnan. Reproducing kernel Hilbert spaces in probability and statistics. Springer Science & Business Media, 2011.
Dimitri P Bertsekas. Nonlinear programming. Journal of the Operational Research Society, 48(3): 334-334, 1997.
J. Frédéric Bonnans and Alexander Shapiro. Optimization problems with perturbations: guided tour. SIAM Review, 40(2):228-22 264, 1998. ISSN 00361445. URL http: http://www...ooorooooo/o stable/2653333.
Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
Alon Brutzkus and Amir Globerson. Globally optimal gradient descent for convnet with gaussian inputs. In International conference on machine learning, pp. 605-614, PMLR, 2017.
Luiz Chamon and Alejandro Ribeiro. Probably approximately correct constrained learning. In H. Larochelle. M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neu- ral Information Processing Systems, volume 33, pp. 16722-16735. Curran Associates, Inc., wwwpongg...uuurrrp neurips wwtppcpeepppeaeeeeeeeeeeeeeeeeee www.fs/pppeeee//22//2/ pdf.
2020. URL httpss:/ppoceeednggs
Luiz F. O. Chamon, Santiago Paternain, Miguel Calvo-Fullana, and Alejandro Ribeiro. Constrained learning with non-convex losses. IEEE Transactions on Information Theory, 1739-1177- 2023. doi: 10. 00.1199/1T22022.11889444
Andrew Cotter, Maya R. Gupta, Heinrich Jiang, Nathan Srebro, Karthik Sridharan, Serena Lutong Wang, Blake Woodworth, and Seungil You. Training well-generalizing classifiers for fairness metrics and other data-dependent constraints. In International Conference Machine Learning, 2018. URL https::///.. httt:p::/ap..smmaniiiisseeee.
org Corpus www.nttiscccittoceee Crtpaa//oor//rooCstttrC. 49556538.
Andrew Cotter, Heinrich Jiang, Taman Narayan, Seungil You, and Karthik Sridharan. Optimization with non-differeeniaalle constraints with applications to fairness, recall, churn, and other goals. J. Mach. Learn Res., 20( (0(17))11559 2019.
Constantinos Daskalakis, Stratis Skoulakis, and Manolis Zampetakis. The complexity of constrained min-max optimization. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pp. 1466-1478, 2021.
Juan Elenter, Navid Alizai/, and Alejandro Ribeiro. A lagrangian duality approach to active learning. Advances Neural Information Processing Systems, 35:37575-37589, 2022.
Matthew M. Engelhard, Ricardo Henao, Samuel I. Berchuck, Junya Chen, Brian Eichner, Darby Herkert, Scott H. Kollins, Andrew Olson, Eliana M. Perrin, Ursula Rogers, Connor Sullivan, YiQin Zhu, Guillermo Sapiro, and Geraldine Dawson. Predictive Value of Early Autism Detection Models Based on Electronic Health Record Data Collected Before Age Year. JAMA Network doi: (0.1000/jammneetorropnn
Open, 0e0e22255333-2254400 02 2023. ISSN 2574-3805. 2022.54303. URL https:tppst.. /doi. org/ / 001 httoo//aamaettooooeeeeoeooo 2022. 543035
10

---

Published as a conference paper at ICLR 2024
Ferdinando Fioretto, Pascal Van Hentenryck, Terrence W. K. Mak, Cuong Tran, Federico Baldo, and Michele Lombardi. Lagrangian duality for constrained deep learning. Yuxiao Dong, Georgiana Ifrim, Dunja Mladenić, Craig Saunders, and Sofie Van Hoecke (eds.), Machine Learning and Knowledge Discovery in Databases. Applied Data Science and Demo Track, pp. 118-135, Cham, 2021. Springer International Publishing. ISBN 978-3-030-676704.
Jose Gallego-Posada, Juan Ramirez, Akram Erraqabi, Yoshua Bengio, and Simon Lacoste-Julien. Controlled sparsity via constrained optimization to stop tuning penalties and love constraints. In S. Koyejo, S. Mohamed, A. Agar- wal, D. Belgrave, K. Cho, and A. Oh (eds.), Advances Neural Information Pro- cessing Systems, volume 35, pp. 1253-1266. Curran Associates, Inc., 2022.
How i learned
URL
https: htppss//proceedinggaa neurips cc cc/paper paape__filessppppr//222 08 089552ccoffaffccce88118888333333 watp:e/eeoe--Pape--ooeeeeeeeeeee
Rong Ge, Jason Lee, and Tengyu Ma. Learning one- mee-hidden-layee neural networks with landscape design. arXiv preprint arXiv:1711.0050)) 2017.
Rafal Goebel and R Tyrrell Rockafellar. Local strong convexity and local lipschitz continuity of the gradient of convex functions. Journal of Convex Analysis, 15(2):263, 2008
Gabriel Goh, Andrew Cotter, Maya Gupta, and Michael P Friedlander. Satisfying real-world goals with dataset constraints. Advances in neural information processing systems, 29, 2016.
Vincent Guigues. Inexact stochastic mirror descent for two-stage nonlinear stochastic programs, 2020.
Kurt Hornik, Approximation capabilities of multilayer feedforward networks. Neural networks, (2):251-257, 1991.
Ignacio Hounie, Luiz O. Chamon, and Alejandro Ribeiro. Automatic data augmentation via invariance-constrained learning, 2022.
Sham Kakade, Shai Shalev-Shwarz, Ambuj Tewari, et On the duality of strong convexity and strong smoothness: Learning applications and matrix regularization. Unpublished Manuscript, hup://ttcc. uchicago. cht//hhiippaprrs/kakaaelllee
pdf. 2(1):35, 2009.
Michael Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu. Preventing faimess gerryman- dering: Auditing and learning for subgroup fairness. International conference on machine learning, pp. 2564-2572. PMLR, 2018.
Ravi Kiran, Ibrahim Sobh, Victor Talpaert, Patrick Mannion, Ahmad A Sallab, Senthil Yoga- mani, and Patrick Pérez. Deep reinforcement learning for autonomous driving: A survey. IEEE Transactions on Intelligent Transportation Systems, 23(6):49094499 4926, 2021.
Andrew J Kurdila and Michael Zabarankin. Convex functional analysis. Springer Science & Busi- ness Media, 2006.
Matt J. Kusner, Joshua R. Loftus, Chris Russell, and Ricardo Silva. Counterfactual faimesss, 2018.
Angelia Nedić and Asuman Ozdaglar. Approximate primal solutions and rate analysis for dual subgradient methods. SIAM Journal on Optimization, 1757717757-1880 2009. doi: 10.1137/ 070708111. URL https:/ /ooi. wrg.orgg//oo... 1137/070708811.
Boris T Polyak. Introduction to optimization. 1987.
Compas recidivism risk score data and analysis., 2020. https::/wwww.rroppbh oow.:e---ee..aaaaaaaa-e-eeee-ea-
ProPublica.
URL
Alejandro Ribeiro. Ergodic stochastic optimization algorithms for wireless communication and networking. IEEE Transactions on Signal Processing. (8(12):6369-6338) 2010. doi: 109/
TSP220102057247.
11

---

Published as a conference paper at ICLR 2024
Alexander Robey, Luiz Chamon, George J. Pappas, Hamed Hassani, and Alejandro Ribeiro. Adversarial robustness with semi-infinite constrained learning. In M. Ran- zato, A. Beygelzimer. Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Ad- vances in Neural Information Processing Systems, volume 34, pp. 6198-6215. Curran Asso- ciates, Inc., 2021. URL https: httttp::s/prrcceedieee ngs neurips....... cctppaaerr/22///11ee Paper.
R Tyrrell Rockafellar. Conjugate duality and optimization. SIAM, 1974.
R Tyrrell Rockafellar. Convex analysis, volume 11. Princeton university press, 1997.
Zebang Shen, Juan Cervino, Hamed Hassani, and Alejandro Ribeiro. An agnostic approach to fed- erated learning with class imbalance. International Conference on Learning Representations, 2022. URL https: wwtp//wwwwweeeeeeeeeeeee net/ oet
1bDt 975.
N.Z. Shor. Nondifferentiable Optimization and Polynomial Problems. and Its Applications. Springer US, 2013. ISBN 9781475760156. URL attps://books:
Nonconvex Optimization
google. wtt../ooooosdd_....o.... VBWWAQQAA.
Victor Solo and Xuan Kong- Adaptive signal processing algorithms: Stability and performance. org/CorpusID: 61115048.
1994. URL https: http://aaa..aaaaiiiaae..eeaaeeee
Mahdi Soltamolkotabi, Adel Javanmard, and Jason D Lee. Theoretical insights into the optimization landscape of over-parameterized shallow neural networks. IEEE Transactions on Information Theory, 65(2):742-769, 2018.
Cuong Tran, Ferdinando Fioretto, and Pascal Van Hentenryck. Differentially private and fair deep learning: A lagrangian dual approach. In Proceedings of the AAAI Conference on Artificial Intel- ligence, volume 35, pp. 9932-9939, 2021.
V.N. Vapnik. An overview statistical learning theory. IEEE Transactions on Neural Networks, 10 (5):988-99) 999,89999,110 1999. doi: 10. 10.1109/72.788400
Alexandre Velloso and Pascal Van Hentenryck. Combining deep learning and optimization for security-constrained optimal power flow. arXiv preprint arXiv:2007.07002 2020.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Commun. ACM, 646)):07-115,, feb 2021. ISSN 0001-0782. doi: 10. 145/3446776. URL https: /ttptt:::/o...ooo http:///oo.ooo..//////o 1tt..///111..1134477777.77777771
12

---

Published as a conference paper at ICLR 2024
A APPENDIX
A.1 ADDITIONAL DEFINITIONS
Definition A.1. We say that a functional & : JF + R is Fréchet differentiable Φ0 F if there
exists an operator Dol,(o") E BFF R) such that:
Le + h)) - (((d") (Dal(("),))
lim
|// L1z
where B(F,R) R) denotes the space of bounded linear operators from F to R.
The space (J, R), algebraic dual of F, is equipped with the corresponding dual norm:
[B.b)] DEF, 1l + #0}
|B sup
|
which coincides with the L2-noo norm through Riesz's Representation Theorem: there exists a unique g E F such that (6)) = (Ø. g) for all o and [ 1ل9|1
Definition A.2. A function h : X + R is said to be closed for each a E R. the sublevel set X} closed set.
(h(z) S
Definition A.3. A convex function h X - R is proper if h(x) for all E X and there exists Zo E X such that h(zo) < toc.
Definition A.4. Let X be an Euclidean vector space. Given a convex function X &RUUP (00), its Fenchel conjugate ht X - -RU {oo} is defined as:
he (v)
sup (z, 9) h(x)) ZEX
A.2 PROOF OF LEMMA A.1: DISTANCE BETWEEN DUAL FUNCTIONS
Lemma A.1. The point-wise distance between the parametrized and unparametrized dual functions bounded by:
0 S (A) (A) < Md(1 + ([lI)))
A
0
(11)
As defined section 2.1, o(A) denotes the Lagrangian minimizer associated the multiplier À in the unparametrized problem.
By the near-universality assumption, 30 θ such that [[Ø(A) - falle, S Note that,
L(fa. A) L()(A), = (o(fs) (()(A)) + XT (e(fa) ((o(A)))
< [[(o(Sa) - ((o(A)))l2+ + Σ (llleeecaa) - E(O(A))]l
1=1
where we used the triangle inequality twice. Then, using the M Lipiscchitt continuity of the func- tionals & and the fact that ()x((A) Jalla v, we obtain:
L(fa,A) - - < MIffa @())l,, + M
A - ((A)llzz
< Mv+ Mr M Me(1+ (1A]])
Since fo(A) (A) is Lagrangian minimizer, know that L(fo(A), I L(fa. A). Thus,
< L(fo(A), A) - L(d(A), A) & L(fg. A) A))
where the nen-negatyvyty comes from the fact that Fo C F. This implies:
0 (p) (A) & Mr +1) A A
which conludes the proof.
13

---

Published as a conference paper at ICLR 2024
A.3 PROOF OF LEMMA A.2: DIFFERENTIABILITY OF gu(Pu)
Lemma A.2. Under assumption 3.1, the umparametrized dual function Gu (X) is everywhere differ- entiable with gradient V Vggu (()(A)).
From assumption 3.1, (()) is strongly convex and X (Te( is a non-negative combination of convex functions. Thus, the Lagrangian I.(J,) strongly convex on & for any fixed dual variable À E I
The convexity and compactness of F imply that, in the unparametrized problem, the Lagrangian functional attains its minimizer (()) for each X. (see e.g. (Kurdila & Zabarankin, 2006) Theorem 7.3.1.) Then, by the strong convexity of L(ø, A), this minimizer is unique.
Since L(J,A) is affine on X, it differentiable on X. Then, by application of the Generalized Danskin's Theorem (see e.g: (Başar & Bernhard, 2008) Corollary 10.1) to (a(A) and using that the set of minimizers (() of L(f, X) is a singleton, we obtain:
Vx
which completes the proof.
A.4 PROOF OF LEMMA A.3: DISTANCE BETWEEN OPTIMAL DUAL VARIABLES
Lemma A.3. Under assumptions 3. 3.2, 3.3, 3.4, the proximity between the unparametrized and parametrized optimal dual variables is characterized by:
Mv
|
(1 + (|221))
(12)
Pg
Since gu(A) is differentiable (see A.2) and Mg - strongly concave for X E Hx:
ga(A) S () gg (A;)) (A X Ma 1 Ae Hx
From Lemma A.2 we have that (gn (()())))) then evaluating A; we obtain:
ga(Ag) S 9t + (X - 1g 1 A
By complementary slackness, ((o(At)) = 0. Then, since @(>²) is feasible and X 2 0: ((6(x))) < O. Thus,
Hg 12 x 9m(27) gu()))
2
By Proposition 1: (2g) - Mo(1 + (1b)11) gu(A)), which implies:
(p()7,) Mr(1 + |p S gx
Mg //2 || -
Thus,
2 Hg
2 Mv(1 11)1111)
1 - - <
[g (on(X (,(2
+ Hg
(13)
Finally, since Fo C F we have that gn(A)= S 9p(2)
v. Evaluating X and using that X;
maximizes Ip we obtain:
(x,) < (2,) < 9p (29)
Using this in equation 13 we obtain.
1 - - < Mu + 1251h)
1g
14

---

Published as a conference paper at ICLR 2024
A.5 PROOF OF PROPOSITION 3.2: PERTURBATION DUAL VARIABLES
Proposition. 3.2 Under assumptions 3.1-3.4, the distance between the constraint violations of xxx)) and ((xt) bounded by:
8 - - S 2 Mb(1 1127111) Kg
(14)
The proof follows from straightforward applications of Lemma A.2 and Proposition A.3, Since the dual function (A) is Bg smooth,, we have:
- -
(V Vxgu(A))1
11 - XM
Then, the bound between optimal dual variables given in Proposition A.3 yields:
((<x))))) < - Mv(1 112
By
which concludes the proof.
A.6 PROOF OF LEMMA 3.1: CURVATURE OF THE DUAL FUNCTION
Lemma. 3.1 Under assumptions 3.1, 3.2, 3.5 and 3.6, the unparametrized dual function 9u gu(Au) My strongly concave and Bg smooth on HA with:
Ná o²
vmM²
Hg B2(1+ + A)
and 3g
(15)
Ho.
where A = max(I1A)]l (11
A.6.1 STRONG CONCAVITY CONSTANT Pa
As shown in Lemma A.2, the unparametrized Lagrangian has a unique minimizer Φ(A) for each RTT Let \1, X2 E HA and Φ1 = ((\1), Φ2 = o()2).
By convexity of the functions 4, F + IR for i 1...., we have:
4(02) 2 (((1)) - (Dol(611) 02 Φ1), 4(01) 2 (()2) (Doli(02), 01 ②2)
Multiplying the above inequalities by [Aile 2 0 and Del 2 respectively and adding them, we obtain:
-(((2)) E(01), - -A - -11
(16)
Since Vgu (A) = (()())) we have that:
- -V (A2) - Vg.. A1) 2 (2) +1))
(17)
Moreover, first order optimality conditions yield:
Delo(Øi) + XFD(((01) 0,
(18)
Dolo(o2) + DTE((()2) =
where 0 denotes the null-opereator from F to R (see e.g. (Kurdila & Zabarankin, 2006) Theorem 5.3.1).
15

---

Published as a conference paper at ICLR 2024
Combining equations 17 and 18 obtain:
<(V (gu()2); A2 A1) 2 (DoLo(02) - Dofo(or), Φ1)
(19)
uoll $1 61ll22
where we used the Mo At-strong convexity of the operator fo.
We will now obtain a lower bound on | Φ1
11 starting from the 3 smoothness of to:
1
||
20112
3 D)lo((2) Dalo(di)llrz
B |1 (e(((r)) Do
(20)
p x1 ) X (Daa((0)) Dal(
Then, second term in the previous equality can be characterized using assumption 3.6:
11 D) 2 ol| A1ll2
(21)
For the second term, using the 3 smoothnnss of & we can derive:
m
(AT -
Σ (ill(Do((()) - Dog((2))ll
DrlillDae((d))) Doli(o2)lle
(22)
[1leeBll01 - -22l112
3 Dallullor - 2211L.
Then, using the reverse triangle inequality:
[1(A2 Do) - D
2 l1 -
- -
(23)
2 ool22 A1ll2 - A1lAllilloo dille,
Combining this with equation 20 obtain:
l 01 2 3 (a -ill2 -
(24)
+ 1 مıll 2 B(1 + 111l1)) D1 - Aallz
This means that we can write equation as:
Po o²
-(Vgn(A2) - Vga(,)),>op A1)
8 || Do A1113
Letting Aa X we obtain that the strong concavity constant of Iu in HA Wg o² 3*(1+mxx (IIA In 2 A similar proof in the finite dimensional case can be found in (Guigues, 2020).
A.6.2 SMOOTHNESS CONSTANT 3g
Set '₁ X2 E RT, and let Φ1 = ((A,) and d2 = ((22) denote the Lagrangian minimizers associated to these multipliers.
16

---

Published as a conference paper at ICLR 2024
Since the unparametrized Lagrangian is differentiable and Po stronnyy convex have: ((f.)) 2 (()(A),) (D&C(o()), ( 2 -
o())
Using that ((A) minimizer, we obtain (see e.g. (Kurdila & Zabarankin, 2006) Theorem 5.3.1)
(()(A),A) ((U,))
P0 || - b VSEF
Applying this to Φ2 and 01 we obtain:
(0(02) + (72( & (o(01) + (()1
Ng
02 Φ1 112.
2
(0(6)) + xf & (o(d)) + ((0))
140
02 - @1 112 2
Summing the above inequalities and applying Cauchy- Schwarz:
pollob +1 1 < (A2 X1) (e(())) - -((22))
- A2 A ((()))((())))))))) E(02)112
S \m - A1llell01 &2ll<s
where the last inequality follows from assumption 3.1. Then, applying Lemma A.2 we obtain:
(A) Vag. (A) Hl = (1((d2) E(11)1l2
I M Ml &1 1lz
M
S vm
12/e d11l2
4g
which means that 9u has smoothness constant Bg = m M2
A.7 PROOF LEMMA A.4
Lemma A... Let p denote the Fenchel conjugate of the perturbation function (c)... For every IRT we have that (+()) (A).
By definition of Fenchel conjugate:
P1()) sup x c
(25)
Using the definition of the perturbation function (*(c) obtain: sup XT fo(
Pt())=
+EF.e
(26)
s.t: (()) + 30
Applying the change of variable [(())= e, Pt (A) be written as:
PT(A) = sup X z - x" (()) lo(0)
(27)
s. to: z 1 0
Since z A the term XTz is unbounded above for
Thus, we restrict the domain of pf (A) to
m 0. In this region, maximizing over z E R. yields zt = 0. We can thus write (*) as:
(*()) sup -x ΦEF
{(Φ) -x
- to(d). A 0
(28)
inf X ((()) + lo(0), 2
dEF
Therefore,
A O.
Similar versions of this result can be found in (Rockafellar, 1997), Section 28, (Guigues, 2020), Lemma 2.9 or (Rockafellar, 1974), Theorem 7.
17

---

Published as a conference paper at ICLR 2024
A.8 PROOF OF COROLLARY A.I: CURVATURE OF THE PERTURBATION FUNCTION
Corollary A.I. Let B, = (Ten + (1 (1-7) 7)) E 1]] denote the segment connecting Eu and 6p- The perturbation function P* (e) is pe- PeeSstoongly convex on B, with constant: pe -1/3g.
We begin by stating well-known Lemma on the duality between smoothness and strong convexity Lemma A.5. Let h be closed convex function defined on a subset of the vector space X; h is strongly convex if and only hf has μ sipiscchitz continuous gradients. (See egg, (Kakade et al., 2009) or (Goebel & Rockafellar, 2008)).
In order to apply Lemma A.5 we need to show that the perturbation function P(c) is convex and closed the region of interest.
Convexity of (E) for convex functional programs is shown in (Bonnans & Shapiro, 1998) or (Rockafellar, 1997) Theorem 29.1. 1. Now we will show that (e) is proper and lower semi continu- ous in the region of interest, which implies that it is closed.
The functional lo, defined on the compact set F, is smooth. Thus, bounded on F. From assumption 3.2 we have that the problem is feasible for O. Therefore, P(O) < +oo. Moreover, by boundedness of fa. P(e) > -00 Ve, implying that P(e) is proper.
Now, fix e E B.. Assumption 3.2 implies that the perturbed problem with constraint: L(J)+e 0 strictly feasible. Since this perturbed problem is convex and strictly feasible, its perturbation function ((e) lower semi continuous at 0 (see (Bonnans Shapiro, 1998) Theorem 4.2). Note that P(c) = (* + c)). Thus, (c(c) is lower semi continuous c..
We conclude that (e) is proper and lower semi continuous for all B..
On the other hand, from Corollary 3.1 pi (A) -9a (A) is By-smooth on RT. Thus, we are in the hypothesis of Proposition A.4, which implies that P* (c) is strongly convex on B, with constant F
A.9 PROOF OF PROPOSITION A.1: SUBGRADIENTS OF P
Proposition A.1. Under assumptions 3.1 and 3.2, X7 is subgradient of the perturbation function at That is, X E (eu).
The conjugate nature of the dual function (A) and the perturbation function P*(c) also establishes a dependence between their first order variations. This dependence captured the following lemma.
Lemma A.6. If h is a closed convex function, the subdifferential oht sense of multivalued mappings (see (Rockafellar, 1997) Corollary 23.5.1):
t is the inverse of Öh in the
x E Oh (y)
E @dh(z))
On one hand, from Lemma A.2, we have that V1 = E((())) = -cu- On the other hand, from Lemma A.4, (t()) (A) for all À E TT
Taking the gradient with respect to À and evaluating at X3 obtain: VXPi(2;) E.. Then, Lemma A.6, yields the sensitivity result:
X OP"((E)))
A.10 PROOF OF PROPOSITION A.2: DISTANCE BETWEEN OPTIMAL VALUES
Proposition A.2. Under assumptions 3.3 and 3.1, the difference between the optimal values of problems perturbed by Ep and cu is bounded:
S Mu(1+ (1 + X (cp- cu)
Recall that ((((())) and Cp - ((fo()))). We want to show that:
P* (cp)) P*((e) S Me(1 ||]l]) + X (Ep 6x)
18

---

Published as a conference paper at ICLR 2024
We start by showing that (xp) I (u(fo(A))). Note that fo (Ap)) is feasible in the perturbed prob- lem, since its constraint value 18 - cp. Then,
P(ep) (innnLoo L()) t 303 S Lo(So(2)))
Therefore,
- -
(29)
Note that the dual function of the problem perturbed by Eu is Fa(A, en) = minser (fo()) + X (e(()) + e. Then, weak duality implies that (*n) 2 Gu(A, en) for all x. Evaluating at
d obtain:
('((w) 2 min (To(f) + X; (I(f) + +c,)
DEF
min (lo(o) + Xp {0)) + x²" ΦE
(30)
gu (2p) + T
Combining equations and 29 we obtain:
(ep) - (en) S lolJa gu gu() Xp Eu
(31)
= Lolff (1,)) + +f Ep (x() - Cu
Recall that 6p = (()(()))) Then, we can identify the parametrized dual function gp(A) = (o(fo(A))) XxTC, and write equation 31 as:
(ep) - P* (en) S (pp( - gu((2)) + 1 (ep - e..) Finally, leveraging the bound between dual functions from Lemma A.l obtain:
(ep))) (e.) s Mv(1 + (A X (Ep -u),
which conludes the proof.
A.11 PROOF OF PROPOSITION 3.3: FUNCTION CLASS PERTURBATION
Proposition. 3.3 Under assumptions 3.1-3,4, the distance between constraint violation associated to the parametrization of the hypothesis class is given by:
[(((((A))) - (x, I 23, 112)1
Let Ae Cp - Cus using the strong convexity constant obtained in Proposition A.l we have that:
1 A
(*()e) (*(ew) of Ae
2,3
where & E (cu( is subgradient of (c) at Cu.
From Proposition A.1 know that: X E @P*(ce) Thus.
1
P* (*((p) 2 P* (E..) + Xp A +
|
2,3
Using the bound on ('(()) - ((.) obtained in proposition A.2 we can write:
1
Mv(1 + 1 + 2 AE
AE +
|
23,
1
MM + 17 2
Ac 12
2.9
This implies:
|| < 28, +1121111
(|E()) ((o(22))) 2 20, + 121hh)
which concludes the proof.
19

---

Published as a conference paper at ICLR 2024
A.12 PROOF OF PROPOSITION 3.1: 2-NORM NEAR-FEASIBILIT
Proposition. 3.1 Under assumptions 3.1-3.4, for all Su(X)) E Fo()), the distance between the unparametrized and parametrized constraint violations bounded by:
2
Bg
[e((f((2)) - 28, (125H1))
1+
Hg
Proposition 3.1 stems from combining the feasibility bounds in Corollary 3.2 and Proposition 3.3:
/2 _ Mv(1 (125111)
[I(()()))) - e(d')lla -
(32)
(((((()))) - e(fo())))l2 / Mu, + (
(33)
Combining the above equations through triangle inequality we obtain:
[[((f((7)) - ((o(A)))l22
2 2 + (17 + v 2 Mu(1 + (Apl11)
/2
(34)
Mg
Bg
M 11bp
[+
(35)
kg
Taking squares both sides yields the desired result.
A.13 PROOF OF THEOREM 3.1: GEAR-FEASIBILITY AND EEAR-OPTIMALITY
Theorem. 3.1 Under assumptions 3.1, 3.2, 3.3, 3.5 and 3.6, the sub-optimality and near-feasibility afll fo();) E F(X,) is bounded by
Mv
(((()(27)) (00 S M [1 (1 +]]
2m
(1 + (|A) = T2
(36)
Pg
P - Lo([o(2))) & || (1 + M
(37)
with 1S
M.
KO
B max
| 11, |App11) and I as in eq. 4.
Pd
A.13.1 NEAR-FEASIBILITY
Recall that Lemma 1 characterizes the strong concavity Mg and smoothness 8g of the dual function terms of the properties of the losses f, and the functional space F. The proof of this theorem stems from applying Lemma 3.1 to the 2-norm bound in Theorem 3.1.
We start by observing that: [I((f((A))) - ll & ((((Fo(A)) ((6(At))
(38)
Bg
/ 22 11
(39)
Mg
From proposition 3.1, we have that Bg =
(4g (1(+1))2
and By = vmM This implies that
3g
2 8²
vm
+ A)²
Ug
o² μi
where A = max 11 Plugging this into equation 39, we obtain:
M/1
2
My
(1
1 m/1 M B
(1 (++))
No
Po
S M
Nu
(1
12tlh)
1
M 3 (1 + A) fm
44
20

---

Published as a conference paper at ICLR 2024
Finally, using the definitions of the condition numbers
M1
Ko
P No.
obtain:
Mv
(e(So(2))) (( S M + (1 +
2m
(1 (1a
(40)
μ40
which is the desired near-feasibility bound.
A.13.2 NEAR-OPTIMALITY
To derive the near-optimality bound, we combine equation 40 with the duality gap bound from (Chamon et al., 2023, Prop. 3.3):
P D2 S Me(1 + (²*1)) =
(41)
where X maximizes (A) (2) + Mu/|A|l1-
Since Pr 2 Ps we have:
P D + lo(0") - (o(fo(A))) s (TT((((()))) +1
Then, using that the solution of the unparametrized problem Φt is feasible (i.e, (()")) - 0) and d ž O we obtain
lo(0") - (o(Jo(27)) X ((6))))))())))+)++))))))))))()))
(()))) S 125lille(0">> -((0("")))(((())))ll))))) +
To conclude the derivation, note that the u-universality and M-Lipschitz continuity (Assumptions 3.3 and 3.1) imply that there exists A' such that - ( & Mv for all O...., m. Thus,
lo(o)) - (o(fo(A))) 2 lo(d") + (o(fer) - (o(ff(
(42)
z fo( - Mr - fo(ff (25)
Note that the duality gap bound implies the approximate saddle-point relation:
(Af) X - ((f) - L(fer >²) F1-
Applying the right-hame side of this inequality to equation 42 we obtain:
fo(0*) - (o(Jo()))) 2 (e((((A)))) - -((p)))))((()))))))))))))))))}}) - T1 (1 [Ag
N -1Agllall((("" - ((fo(2))) - (1 + De T2
which completes the proof.
A.14 PROOF OF LEMMA 4.1: BEST ITERATE CONVERGENCE
Lemma. 4.1 Let g ghea (1))(t)) max.e(to.t) (x))) be the maximum value of the parametrized dual function up to time t. Then,
best (L)((10)) 2 D3 11,52 +D) a.s.
lim Sp 1+00
where 52 E[1((()1)1(()) is upper bound the norm of the second order moment of the stochastic supergradients.
similar proof in the context of resource allocation for wireless communications can be found in (Ribeiro, 2010), Theorem 2. To ease the notation, will denote the value of the parametrized dual function at iteration by gt) = (A())). Similarly, best (t) will denote the largest value of g()) encountered far.
We start by deriving a recursive incquality between the distances of iterates A(t) and an optimal dual variable A3 E arg m (A).
21

---

Published as a conference paper at ICLR 2024
Proposition A.3. Consider the dual ascent algorithm described in Section 4 using constant step size 1j > 0. Then,
1
& (1A(1) - -21l + 5 2n g(1) p)
(43)
We delay the proof of Proposition A.3 to section 1.1..1. We can observe that as the optimality gap D2 g() decreases, the fixed term 5² dominates the right hand side of equation (43), suggesting convergence of ((t) only to neighborhood of X7. In order to show this, the main obstacle is that Proposition A.3 bounds the expected value of [|(t++1) - X²
and we wish to establish almost sure convergence. This can be addressed by leveraging the Supermartingale Convergence Theorem (see e.g, (Solo & Kong, 1994) Theorem E7.4), which state here for completeness.
Theorem A.1. Consider nonnegative stochastic processes A(N) and B(N) with realizations ((N) and B(N) having values o(l) > and (3()) 0 and a sequence of nested o-algebras A(O 1)
measuring at least o<(0: : 1) and (300 1). If
B[a + 1) A(O : () S all) - B(L)
(44)
the sequence a(t) converges almost surely and (t) is almost surety summable, ie.. Ea=1 B(u) 0o a.s.
<
We define at) and ((t) as follows,
1/52
((t) == ([((t) - 2;11 I D - >
2 tp]
B(t) = [2m(D; gt()) p) -n²² -²2 II { D g )te)(t)
11.2
2 + p
Note that at)) tracks ||(t) - 2/ until the optimality gap D - 9 (t) falls bellow the threshold nsa
2 + and is then set to O. Similarly, B(t) tracks 2n - (t) - p) - 572 until the optimality
gap D;- - - g0))(() (1) falls bellow the same threshold and is then set to 0.
It is clear that (t) 2 O, since it is the product of a norm and an indicator function. The same holds for 3()), since the indicator evaluates 0 whenever (n, g(t) - p) nj² S2 < 0. We thus have, al)),B()
for all L.
We will leverage Theorem A. to show that ((L) is almost surely summable. Let A(O t) be a sequence of o-algebras measuring a(0 f), 8(0 : t) and X(O: t). We will show that (x and ((t) satisfy the hypothesis of Theorem A. with respect to A(O t). Note that at each iteration, at) and 3(t) are fully determined by A(t). Therefore, conditioning on A(0 f) is equivalent to conditioning on X(t), i.e: B(a(t)]A(O- })} ((a(t)))(t)) Then we can write,
({(())AA0 : () =0)) - =0 ())(((())))))))))))))))))))))( > 0}
(45)
+ +B(a(())(()) (()) ()){))((())))))
From equation 45, we will derive that B(a(t))A(( +) at)) B(t) which is the remaining hypothesis in Theorem A.
On one hand, observe that if a(t) = 0 we have that L( gDm < n5² + p} 0. This is 2
because in the case where |A(() - >1ll2 = 0, the indicator function also evaluates to 0. Therefore,
if a<t) = 0, it must be that (() 0. Then, trivially, (() = 0) aat) - 3(1)
On the other hand, when (tt) > 0:
Ela(t + 1) X(t), 0]
(46)
1252 )
=E
| -x:1| 11 D2 - (t >
2 #p} 12(0)
(47)
$ E 1)
- -3,1² {x()
(48)
22

---

Published as a conference paper at ICLR 2024
where we used the definition of a 1) and the fact the the indicator function is not larger than 1.
Then, from proposition A.3 we have:
Ela(t + 1) X()), a(1) > 0J - ||(()) >² + -2 22n(D; g(() p)
(49)
a 5()).
(50)
equality I [D; (1e- n + p) =1
where the last
comes
from the fact
that a(l) >
0
implies
+
This means that we can write equation 45 as:
B(a(())A(0= ()) S [a((() ((O)(P(o(() 0) + P(a(() 0))
(51)
= at - 3(()
which shows that (t) and (t)) satisfy the hypothesis of Theorem A.1. Then, we have that (8t) is almost surely summable, which implies,
lim inf [2n(D; -g(() p) - -1 I(D -g00((1) > S/5² p = 0 a.s. 1-000
This is true if either D g (t) lim infe- [2n(D; - g(t) p) 5² 0, which concludes the proof.
n for some t, or if
A.14.1 PROOF OF PROPOSITION A.3
Proposition. A.3 Consider the stochastic supergradient ascent algorithm from Section 4 using constant step size 0. Then,
(L + 1) (X11) & ||A()) 2T11 5 - - pp)
(52)
Let (()) denote the approximate stochastic supergradient (1). From the definition of X(I + 1):
|A(L 1) - メلل²² = [I[A(t) + m)((t)+ - - X11
< [IA(1) - - 11)
(53)
(|A()) ン + 1=1)((1)) 21) >20)
where we used the fact that setting the negative components of A(t)+m/štt to 0 decreases its distance to the positive vector X and then expanded the square.
Note that for given A(t), the relations in 53 hold for all realizations of 8(t). Thus, the expectation of [| + 1) Aill. conditioned on A(t) satisifes:
[[][A(++1) 1)1-1)))));,11(11 (I()) < (IA(t) - X (00
(54)
Furthermore, the stochastic supergadient s(t) yields, average, approximate ascent direction of the dual function 9p:
E (((())(())({()) >) - g() (A).
(55)
Evaluating the previous inequality at X and combining with equation 54 we obtain:
E( + 1) 1(()) < ||А(t) >Iلl + 5² 2n(g(t) D2 + p))
(56)
which concludes the proof.
A. PROOF PROPOSITION 4.1
We will bound the distance between (((())) and ((fee)))) by partioning it into terms that have previously analyzed in Corollary 3.2 and Proposition 3.3:
[[(()(>))) - (( 1) - [((()())) - ((0((( bes)
+ [|(((((Abb)) ((
23

---

Published as a conference paper at ICLR 2024
The first term is of the same nature the one analyzed in Corollary 3.2, since it is characterizes a perturbation in dual variables in the unparametrized problem. Thus, using the characterization of the curvature of the dual function from proposition A.3 and the sub-optimality of X A with respect to X this term can be bounded.
We denote by e the segment connecting A Abest and X and by Pig the strong concavity constant of Iu y Using Lemma A.I and the fact that (pp) 2 gu (A2) we obtain:
2 (gu (1,) 9u (Abess)))
||A
11 <
fg
(gp (gp(1p) - (gp(A Mv(1 + I1))
Then, leveraging the almost sure convergence shown in Proposition 4.1 we have:
S 2 [M + | tes (1 +
n
|
2 +
(57)
Big
Note that equation 57 corresponds to the bound in Proposition A.4 but amplified by the sub- optimality of best with respect to Xz. Then, since the gradient VAgu(A) {(ő(A) is By-Lipcchizz continuous:
[((()()))))) ((6())))
AV - Vxga(A;)11
(58)
S 33 1A hew
(59)
2,32 [Mv(1 + ||A (1) 11)
17.22
2 +P)
(60)
which completes the first part of the proof.
The term (1(((((Abes)) (ba))) (( captures perturbation in the function class for a fixed dual variable, and can be bounded by leveraging the perturbation analysis of Proposition 3.3. Let &n -(((()bes)) and Ep (())))) First note that the duality between smoothness and strong convexity detailed in Corollary A.1 implies that (*(e) is strongly convex with constant h on By Then, in Proposition A.2, we can bound the distance between the optimal values associated to these perturbations EØ and E. by:
P'( P*(2.) S Mv(1 + || [11) + Abest (Ep - [n)
(61)
The strong convexity of Pa combined with equation 61 yields:
Mv(1 + besb l1) + best"
Ač > A best"
AE+
(62)
2,3
which implies:
||7:| S 23g + (1
(63)
We conclude the proof by summing the bounds in equations 60 and 63 to obtain:
[K(()()))) - {(fo(A
(64)
2
Mv + ([Abes111) + 17S2
- v Mr + ||tbss/ +
2 +P)
(65)
11.22
2.5
7,52
- 22 MMv( + [| +
+p) + +1
Mv(1+ + || 111)+ +
+
2
2
(66)
17.22
(
Bg
= 23, [Mv(1+ ||
+
+ p)
1+
(67)
2
which concludes the proof.
24

---

Published as a conference paper at ICLR 2024
A.16 ADDITIONAL EXPERIMENTAL DETAILS
We adopt the same data pre-processing steps as in (Chamon & Ribeiro, 2020) and use two-layer neural network with 64 nodes and sigmoid activations. The counterfactual faimess constraint upper bound is set to 0.001. We train this model over T = 400 iterations using a ADAM, with a batch size of 256, a primal learning rate equal 0.1 and weight decay magnituee set to 10 4, The dual variable learning rate is set to 2.
25


Reviews:
[{"review_id": "US2ZsytQVA", "reviewer": "Reviewer_Y13X", "summary": "This paper considers the problem of constrained learning using the dual-ascent relaxation framework. The paper attempts to bound the error in the constraints of the relaxed solution using the dual variables. The approach is based on an infinite-dimensional (not parameterized) formulation/relaxation of the dual problem in which the bounds are obtained. This provides a bound on the error in the infinite-dimensional primal problems and the results are used to bound the error in the actual solution to the primal using the actual finite-dimensional dual ascent.", "questions": "Specific concerns and questions are listed as follows.\n\n1 Please more clearly spell out the motivation in the context of fairness of including the constraint vs. just not including data on the protected classes.\n\n2 \"$\\mathcal{F}_\\theta$ can be a neural network\" -- First, its a set, not a network. But remind me -- in this case will the hypothesis space be convex? Also, take the extreme case of a single arbitrarily chosen Gaussian kernel. Is there not some problem with fragility/generalizability? Performance on untrained data? How does this approach account for the robustness of the parameterization? Maybe this relates to the question of which topology is being used to characterize Lipschitz continuity.\n\n3 The Lipschitz and convexity are defined using $\\ell$ which is a statistical function. Would it not be more suitable to define them using the actual functions, $\\tilde{\\ell}$?\n\n4 Not much mention of the primal-dual gap and whether it is significant in parameterized or unparameterized problems\n\n5 Generally bothersome to have lots of assumptions unless it can be shown they are satisfied in certain basis and useful cases.\n\n6 I'm not sure exactly the point of Section 3.3.2 -- Are we saying that the bounds can be improved by making the constraints strict?\n\n7 \"We will denote by $\\hat \\ell$ an estimate of $\\ell$ using the dataset D....\" First, redefining $D$ casuses confusion. Also, how is this now a dataset? Also, this brings up the $\\ell$ vs $\\tilde{\\ell}$ issue again -- Alg 1 is defined using $\\ell$ and not $\\tilde{\\ell}$. What is $D^*_p$ in Lemma 4.1 -- clearly not related to D.... Actually it seems there are lots of $D$-based notation in this paper.\n\n8  \"We train this model over T = 400 iterations using a ADAM\"  Acronym undefined -- maybe they mean Adam, which is an algorithm. What is $\\ell$ here? Are the Assumptions satisfied? What are the obtained bounds?\n\nMinor corrections are as follows\n\n- Page 1 - \"In fact, this problem is even hard from\" -- which problem?\n\n- Notation $D_{KL}$ on Page 2 is undefined.\n\n- \"guarantees usually pertain a probability distribution over\"\n\n- Assumption 3.2 is unclear. What is $f_\\theta(\\lambda)$ here? It becomes more difficult to interpret the results after this.\n\n- \"the unparametrized Lagrangian minimizer is unique\" -- presumably this is the solution for the unparameterized version, $D_u$?\n\n- \"unparametrtized\"\n\n- Assumption 3.4 seems difficult to verify...\n\n- Thm 3.5. This is difference between the constraint functions, not their violations since $\\ell_i$ are not non-negative.\n\n- Page 12, after Defn A.1. Some conflation of operator $B \\in \\mathcal{B}$ and its representor, $g$.\n\n- Defn A.3 -- what does it mean for $h(x)>-\\infty$? \n\n- \"Linear independence constraint qualification (LICQ)\" -- capitalization issue...\n\n- \"Thus, it can be thought of as the baseline effect\" --  define \"it\"... What is the third component -- I see only two.\n\n- \" Combining the bound in equation in equation 6 with\"\n\n- numerous problems with bibliography entries.\n\n- Proofs in appendix need better organization. No explanation or connecting verbiage is given. For example, Appendix A.6", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The narrative of the paper is initially quite clear and the approach is relatively novel and intuitive. The problems seems interesting. There are clear theorem statements and clearly stated assumptions. The mathematics is mostly rigorous and quite general.", "weaknesses": "The interpretation of the results are not clearly stated. In an attempt to be perfectly general, it is hard to state exactly how the results apply to any particular learning problem. One would think that algorithms based on neural networks would perform quite differently than a kernel-based approach using a single poorly chosen kernel. And yet the results don't seem to account for such differences in any way. Additionally, this makes it hard to understand if the 7 (mostly regularity) assumptions are valid and what the corresponding parameters are.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "KqNpscpQwp", "reviewer": "Reviewer_3wd8", "summary": "The paper studies the problem of contrained learning problems using the dual learning algorithm. The authors provide feasiblity gap (for both the primal and dual variables) between the parameterized/unparameterized problems under certain regularity conditions. The authors then provide optimality gap for the dual learning algorithm, and numerical validations for the hypothesis that the feature space size impacts optimality gap according to the theory.", "questions": "See weakness.", "limitations": "", "rating": 3, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is clearly written and easy to read. The authors make the assumptions clear and define the problem well. The theory for the parts I checked is sound.", "weaknesses": "1. The paper's title is near-optimal solutions which is misleading. The main results compare the stationary points of constrained/unconstrained problems as well as using the dual learning algorithm. I'd expect optimality in statistical sense where a lower bound is provided for rates of convergence/estimation error, instead of studying the limiting points error, which is less interesting to me.\n2. Following the previous point, bounding the error of stationary points is often less interesting in terms of optimality, and lacks of theoretical contributions to the community. Perhaps the authors can provide why such analyses is nontrivial/fundamentally harder than other problems and why it is important to understand this first.\n3. The numerical experiments seem weak. It is not suprising that there will be a gap and as the number of features grow the model approximation error is smaller. I'm not seeing how this directly corrobates the theory. Ideally I would like to see (i) a hypothesis emerged from the theory (ii) an experiment that validates the hypothesis.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Pzfv9cn6df", "reviewer": "Reviewer_2G7p", "summary": "This paper considered the problem of providing a theoretical guarantee on the feasibility of the last-iteration solution of a Dual Constrained Learning Algorithm (i.e., dual ascent algorithm applied to the constrained learning model parameterized by $\\theta$). Typically, to get a feasible output of the dual acsent algorithm applied to the constrained learning models, one need to perform averaging or randomization over the whole output sequence, which is impractical in reality. Let $P_p$ denote the parameterized constrained learning problem where the candidate functional solutions satisfy $f_\\theta\\in F_\\Theta$, $\\theta\\in\\Theta$. In addition, let $P_u$ be the unparameterized constrained learning problem where the candidate functional solutions come from the set $F\\supseteq F_\\theta$. The main contribution of this paper is that authors showed that the optimal lagrangian minimizers of problem $P_p$, denoted by $f_\\theta(\\lambda^*_p)$, are close to the optimal lagrangian minimzer of problem $P_u$, $\\phi(\\lambda_u^*)$.", "questions": "1. Can the authors provide some information about the convergence property of the dual-ascent algorithm applied to a problem with non-convex constraints?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "1. Let $\\ell(f_\\theta)\\leq 0$ be the constraints that are required for the output $f_\\theta$ to satisfy. The author showed for the first time that under some assumptions on the constraints $\\ell$, it holds $||\\ell(f_\\theta(\\lambda_p^*))- \\ell(\\phi)||$ is bounded by some constants, where $f_\\theta(\\lambda^*_p)$ is the optimal lagrangian min of $P_p$ and $\\phi^*$ is the optimal lagrangian min of $P_u$ such that $\\ell(\\phi^*)\\leq 0$.\n2. The authors provided high level explanation and intuition which helps the reader to understand the paper better.", "weaknesses": "1. the bound on $||\\ell(f_\\theta(\\lambda_p^*))- \\ell(\\phi)||$ contains $||\\lambda_p^*||1$, which could be large when the number of coinstraints $m$ is large. When $||\\lambda_p^*||$ is large, we cannot assert that $f_\\theta(\\lambda^*_p)$ is almost feasible. Is there any way to show that $||\\lambda_p^*||_1$ is small under some assumptions?\n2. The authors considered $f_\\theta(\\lambda_p^*)$, the optimal lagrangian minimzer of $P_p$. However, one can only get $f_\\theta(\\lambda_p^*)$ after infinite iterations. It would be more interesting if the authors can provide some information on the feasibility of $f_\\theta(\\lambda(T))$. In particular, how close can $f_\\theta(\\lambda(T))$ and $f_\\theta(\\lambda_p^*)$ be?\n3. The author measured the distance between $\\ell(f_\\theta(\\lambda_p^*))$ and $\\ell(\\phi^*)$. However, $\\phi^*$ doesnot necessarily belong to $F_\\theta$. It seems a feasible solution from $F_\\theta$ should be a better option and perhaps will bring us better bounds.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5yvnJ88Qzr", "reviewer": "Reviewer_rUm3", "summary": "This paper discusses the primal dual algorithm for training a neural network. Since the constraint is difficult to handle, one typical alternative solution is to use Lagrange multiplier to penalize the constraint violation in the objective function and calculates its minimum. This paper specifically calculates and bounds the violation of the constraint to demonstrate that the primal dual algorithm is still good for training NN. Experiments also verify the theoretical conclusion.\n\nUpdate:\nI read the rebuttal. I found the contribution that this paper bounds the optimality gap which is not generally known in convex case, and the way it handles constraint and shows that the primal convergence, which does not in nonconvex case in general, is important. I raise the score to 8 while not having checked all details.\n\nBut I still wonder how good the approximation of the functional class is, i.e., how big is the distance from any function to a function in the parameterized family that the training algorithm is in, and how training error indicates the test error when one has finite samples but a parameterized family to train on being very large. With that, I do not raise confidence and do not raise score to 10.", "questions": "This paper introduces an algorithm which has two inner oracles the first optimizes the Lagrangian function by an argmin expression, while the dual variable part is easy to understand. Is this a typical method when we train your networks under constraints, or one typically use the gradient projection? I guess there is a large difference between the sub optimality gap of these two algorithms, so that the authors prefer Algorithm 1. What is the calculation of complexity of the oracle Line 4, and what is the total convergence rate and complexity of algorithm 1?\n\nHow to solve Line 4? If you solve it multiple times, what is the total complexity?\n\nHow to choose $\\eta$?\n\nPage 3, \"... $P_p$ is convex\" maybe use \"... eq$(P_p)$ is convex\" to differentiate $P_p$ and $P_p^*$.\n\nI think people in ML area are not familiar with functional optimization so it would be great to explain more. For example, Assumption 3.1, it can be \"$M$-Lipschitz \\emph{with respect to functional $\\ell_2$ norm}\" with a footnote about the norm. Also explain strong convexity and smoothness in functional space.\n\nIs there an interpretation of Assumption 3, or for common parameterized classes of functions, can you give an example how large the gap is? \n\nThm. 3.5, I think the $\\ell_2$ norm on left hand side is a two norm on scalar right? Can you just use $(l(...) - l(...))^2$ or $|l(...) - l(...)|$? Typically we only write norm for vectors.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "I think this paper is mathematically correct, detailed, and self consistent. The writing is clear, which gives a lot of discussion, and the logic and the structure that goes to the final conclusion step by step is reader friendly. The analysis of different scenarios under the big primordial framework is comprehensive and detailed.", "weaknesses": "Besides finding the extent of violation of the constraints, it is also very important to bound the objective function’s suboptimality of the final iterates. Especially, since this paper is positioned in NN scenario, the objective function is typically highly nonconvex, and there might be some optimality gap when introducing the dual function, which is relevant to the convex hull of the primal function rather than the primal function itself.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "My9cRieGHl", "reviewer": "Reviewer_z2M9", "summary": "This paper studies a parameterized constrained learning problem and proves that the infeasibility of the Lagrangian minimizer as well as that of the best iterate of dual ascent algorithms is close to that of the corresponding unparameterized convex constrained learning problem. Such a gap is proportional to the parameterization error, which means the Lagrangian minimizer of the parameterized constrained learning problem is nearly feasible under rich parameterization. Compared with the randomized or averaged sequence of primal iterates studied in the existing theoretical results, the best primal iterate studied in this theoretical work is more practical.", "questions": "(1) About the example of Counterfactual Fairness Constraints\n\n(1.1) Is this example proposed by you? If not, cite the sources of the model and data. Otherwise, say that this example is proposed by you. \n\n(1.2) What do the constraints mean in this example? You could add an explanation to the paper. \n\n(1.3) Should we use $\\mathbb{E} _ {x,y}$ in both objective and constraints, with the same distribution of $(x,y)$?\n\n(1.4) Why are some $x$ bolded and some are not? Are they the same $x$?\n\n(1.5) $f _ {\\theta}(x)$ and $f_{\\theta}(x,z)$ have inputs of different dimensionality. How can you make that happen, for example, in a certain neural network with a certain fixed parameter $\\theta$?\n\n(2) At the end of Section 2, you mentioned that Lagrangian minimizers are not unique and some of them could contain infeasible optimal primal variables. Is this found by you or previous literature? If it is found you, you could provide examples to support your claim and emphasize this claim as one of your novelty. Otherwise, you could cite the papers that prove this claim. \n\n(3) Right after the problem $(P_u)$ at the beginning of Section 3.1, you could mention $\\phi\\in\\mathcal{F}$. \n\n(4) It seems that $\\phi(\\lambda_u)$ (in Assumption 3.2) and $\\Phi^*(\\lambda_u)$ are the same, right? If yes, you could unify the notations. If not, you could explain the meaning of $\\phi(\\lambda_p^*)$ in the paper. \n\n(5) In paragraph 2 of Section 3.2, it may be clearer to change ''We will first provide a result assuming this curvature is known'' to something like ''We will first provide a result with the following assumption on the knowledge of this curvature'', so readers can relate to Assumption 3.4.\n\n(6) After ''The second one captures the effect of parametrizing the hypothesis class for a fixed dual variable.'', you could add something like ''We will elaborate these perturbations in Section 3.3.1 and Section 3.3.2 respectively.''\n\n(7) In the experiment, \n\n(7.1) What negative likelihood function $\\ell _ 0$ do you use (or the distribution of $x, y$)? What function $f _ {\\theta}$ do you use? \n\n(7.2) What is the math expression of the counterfactual fairness in the middle of Figure 2?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "Originality: This work provides original theoretical results as explained in my summary above. In addition, the proof techniques in Section 3.3 look novel. \n\nQuality: The theoretical error bound proportional to the parameterization error is reasonable by intuition. \n\nClarity: The general structure of this paper is clear. \n\nSignificance: The best iterate is more practical than the commonly used randomized or averaged sequence of primal iterates, so it is meaningful to provide the first convergence analysis of the best iterate.", "weaknesses": "(1) The theory could be improved in the following aspects: \n\n(1.1) In line 4 of Algorithm 1, the **exact** minimizer of this unconstrained **nonconvex** optimization problem cannot be obtained. This minimization error should be considered which I envision will involve the parameterization error $\\nu$ plus the error rate of the corresponding convex unconstrained optimization. In addition, for the stochastic version of Algorithm 1, the error of $\\widetilde{\\ell}_i\\approx \\ell_i$ should also be considered in line 4, not just in the dual update step in line 5. \n\n(1.2) The error of $f_{\\theta}(t)$ as well as $\\widetilde{\\ell} _ i\\approx \\ell _ i$ will also cause the approximation error of $g_p(\\lambda(t))\\approx\\widetilde{\\ell} _ 0[f _ {\\theta}(t)]+\\lambda(t)^{\\top}\\widetilde{\\ell}[f _ {\\theta}(t)]$ for selecting the best prima iterate. This should also be considered. \n\n**The above two are the most important problems I think. I would like to increase my score once they are addressed.**\n\n(1.3) You could also obtain the difference of $\\ell_0$ between parameterized and convex problems in both Theorem 3.5 and Proposition 4.2 so that the solution of the unparameterized problem is not only nearly feasible but also nearly optimal. \n\n(1.4) You could obtain finite time convergence result, i.e. when replacing $\\lambda^{\\rm best}$ in Proposition 4.2 with $\\lambda _ T^{\\rm best}$, the best iterate up to a fixed iteration $T$, what is the convergence rate involving $T$? I think this is possible by using the existing convergence rates on the convex constrained optimization problems in terms of the constraint violation (like $\\sum _ {i=1}^m \\alpha _ i\\max(\\ell _ i, 0)$ for some constants $\\alpha _ i>0$) as well as optimality. Then we upper bound difference of the convergence rates between the convex and parameterized versions. \n\n(2) A few points are to be clarified as listed in the questions below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)