Learning with Statistical Equality Constraints
Authors: Aneesh Barthakur
Luiz F. O. Chamon
Venue: NeurIPS 2025 poster ()
Keywords: Machine learning
Constrained optimization
Constrained learning
Fairness
Duality
Primary area: optimization
TL;DR: We extend generalization guarantees for constrained statistical optimization problems with only statistical inequalities to problems that include statistical equality constraints.

Abstract: As machine learning applications grow increasingly ubiquitous and complex, they face an increasing set of requirements beyond accuracy. The prevalent approach to handle this challenge is to aggregate a weighted combination of requirement violation penalties into the training objective. To be effective, this approach requires careful tuning of these hyperparameters (weights), involving trial-and-error and cross-validation, which becomes ineffective even for a moderate number of requirements. These issues are exacerbated when the requirements involve parities or equalities, as is the case in fairness and boundary value problems. An alternative technique uses constrained optimization to formulate these learning problems. Yet, existing approximation and generalization guarantees do not apply to problems involving equality constraints. In this work, we derive a generalization theory for equality-constrained statistical learning problems, showing that their solutions can be approximated using samples and rich parametrizations. Using these results, we propose a practical algorithm based on solving a sequence of *unconstrained*, *empirical* learning problems. We showcase its effectiveness and the new formulations enabled by equality constraints in fair learning, interpolating classifiers, and boundary value problems.

Learning with Statistical Equality Constraints
Aneesh Barthakur
University of Stuttgart
aneesh. baarch.barthaakaee barthakur@siimtcch www.umiitittttttcoomm
Luiz F. O. Chamon
École polytechnique, Institut Polytechnique de Paris
luiz. Salamon@polytechniiooe edu
Abstract
As machine learning applications grow increasingly ubiquitous and complex, they face an increasing set of requirements beyond accuracy. The prevalent approach handle this challenge to aggregate weighted combination of requirement violation penalties into the training objective. To be effective, this approach requires careful tuning of these hyperparameters (weights), involving trial-and- error and cross- voos-vvali,tion, which becomes ineffective even for moderate number requirements. These issues are exacerbated when the requirements involve parities or equalities, is the case in fairness and boundary value problems. An alternative technique uses constrained optimization to formulate these learning problems. Yet, existing approximation and generalization guarantees do not apply to problems involving equality constraints. In this work, we derive a generalization theory for squullty--oostraiine solutions can be approximated using samples and rich parametrizations. Using these results, propose practical algorithm based solving sequence of unconstrained, empirical learning problems. We showcase its effectiveness and the new formulations enabled by equality constraints in fair learning, interpolating classifiers, and boundary value problems.
statistical learning problems, showing that their
Introduction
Across a wide range of domains, machine learning (ML) is becoming the core technology driving entire systems rather than specific components. It therefore increasingly faces multi-faccted problems involving not only accuracy, but also requirements such fairness [1]. robustness 2 3
privacy 44) and safety [5] [). The standard approach to handling multiple criteria to represent them as alternate loss functions (penalties) aggregated into single training objective 97 3]. Designing effective
penalties and aggregation weights, however, is often a time consuming process involving trial-and- error, hyperparameter search, and cross-validation data. Hence this approach becomes unwieldy even for a moderate number of criteria.
Constrained learning offers alternative by framing each requirement as constraint rather than a penalty (0H12]. While in convex settings these approaches are equivalent [13], this is not the case for the non-convex optimization problems arising in ML. Nevertheless, recent work has shown that such a duality still holds for rich parametrizations under mild conditions. This result has been used to establish generalization guarantees similar those of unconstrained learning theory and develop practical algorithms based on (primal- )dual methods [T] [2]. Yet, these results hold only for inequality constraints and do account for equality-constiee constrained learning tasks.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

This gap is significant. Indeed, many important requirements are expressed as equality constraints, including group fairness [14 invariance [97 calibration [20 2I], interpolation [22], distribu- tion matching [23] and independence (24]. These are fundamentally different from inequalities since they impose a specific target value rather than a bound, making their feasibility set and sensitivity more intricate to analyze. As such, reformulations of these requirements as inequalities relaxations based on penalties can substantially change the solution of an ML task. In fact, none the duality or generalization results obtained for inequality-constrained learning apply to these problems (see Remark 2.T).
In this paper, we address this knowledge gap by developing a generalization theory for equality- constrained learning tasks. To do so, we derive additional regularity conditions under which we obtain duality and sensitivity results for non-convex ggustity-onsttained optimization problems (Section B) Based on these results, we put forward an empirical, unconstrained (saddle-point) problem and characterize the approximation and generalization error of its solutions, showing trade-off between model capacity ("bias"), sample size ("variance"),, and constraint difficulty (Theorem (3.1). This problem is amenable to practical dual ascent algorithm (Section whose effectiveness we illustrate in learning problems involving fairness, boundary value problems, and interpolating classifiers (Section
2 Problem formulation
2.1 Equaaity-constrained learning
Consider data pairs (x, v) E X' x y and a model fo : - R parametrized by finite dimensional vector E θ C IP and denote by H = {fo : y | A θ} the hypothesis class induced by these models. The goal of classical (unconstrained) learning is to use fa to map feature vector x E X C Rd to its target E V. which can be continuous ()' C R e.g., regression) or discrete ( (1...., K) e.g., classification). This is usually done by minimizing the expected value of one loss function & R x + R describing a top-line objective, e.g., accuracy, with respect to distribution D. In contrast, constrained learning accounts for additional loss functions g:, h, and distributions P,, Q2 by tackling
subject to p= inf eEB
Ep [e(f((x)))
Ep, (fa (x), y)] - 0, for i ,,...,4 1 Ba, [h (f)()).)) y)] = 0, for = 1,..., J.
(P)
We consider homogeneous constraints (whose righ side is zero) without loss of generality since
any constant can be absorbed into the losses gi, h2. We denote the set of optimal solutions for (P)
by Opt(P) and the of feasible solutions (i.e., those that satisfy the constraints of (P)) by Feas(P). (P).
These additional expected losses can be used to impose a rich class of constraints and ancillary
requirements based on data, such as fairness [10 [[] robustness (25), and invariance [99] These
works and the majority of the constrained learning literature considers problems with incquality constraints [J- 0 in (P).. In contrast, this paper concerned with problems explicitly involving equality constraints. Before proceeding, we illustrate a few instances in which this additional
expressiveness is beneficial (see also Section 5).
Fairness. Statistical definitions of fairness in ML are naturally formulated as equality con- straints (26] 27). Consider, for instance, demographic parity (DP) in binary classification, where the score fo (x) E [0, 1] is thresholded to determine a positive (x) > 0.5) or negative (fe (x) < 0.5) outcome. DP requires that the prevalence of positive (or negative) outcomes within the protected groups } be the same as that of the whole population [28] 29 [4]. Protected groups are often based on a sensitive attribute of the feature vector x, although we impose no such restrictions.
DP-constrained binary classification can be cast as (P.. explicitly,
minimize BEB
E> [E(((((()))))
(P-DP)
subject to
Ep [x) > 0.5] xx E G,] = Ee [I]fo(x) > 0.5]]. for 1,......
where l is a classification loss and [[]] on the event E and otherwise. Note that (P indeed has the form (P). for h, (fo(x), = F(xε,,) [x) > 0.5) [ e G,] - [fe(x) > 0.5 and

---

Q2 P. Other statistical definitions of fairness, such as equality of opportunity, can be similarly formulated [15]. While the equality in (P-DP) is sometimes approximated by an inequality with some slack TO [1], this can change the solution in non-trivial ways (see Figure
Equality constraints also enable prescriptive forms of equity that enforce specific rates rj 0 of positive outcomes for each group Gj. which can be cast as
minimize Bg
Ep (e(f(((x))
(P-F)
subject to
Ee [1] > 0.5] X Gj Tjj for I....,J.
Boundary value problems. Boundary value problems (BVPs) arise in many scientific applications. While they can be solved with classical methods such as the finite element methods (30) (1), they have recently also been tackled using learning methods by directly parametrizing their solution with a neural network (e.g. PINNs (32). Indeed, let S2 F be a bounded connected region with boundary
an and define the domain D = Ω x (0. (where T > 0) and let H {fe 0 Q} be set of functions defined on D. A BVP is typically posed as
find subject to
fo H (x,,)(x,)) = =T,(xx)),
v(x,1) E ED, Vx E 02, (0,7);
(BVP)
fo 1) -o((x, I), fx 0) = [x 0),
Vx E S2
where D is a differential operator defined over a superset of H. f is called the forcing functiio, and out that (BVP) To: T2 describe the boundary and initial conditions (BC and IC) respectively.
can be solved with an instance of (P) as in
minimize BE0
_ $10122
subject to
(x,](()()((x ((x,1)) = O,
(P-BVP)
Er,1(fo(x,)) t) - Tx t)) 0,
[p,((fe(x,0) 0) - Tx, 0))) 0,
where PP, Ps. and I. are arbitrary distributions (usually uniform) over D, 02 x (0,T), and Ω respectively [33]. Thus, the constraints enforce mean squared error versions the PDE together with the BC, and the IC. This is in contrast to PINNs that aggregate the errors into single weighted loss, leading to solutions sensitive to the choice of weights [4 35
Interpolating classifiers. Modern MI. models are typically overparametrized and often trained to perfectly fit (interpolate) the training data. Several works [36
22 have found that interpolating models performs well in practice, contrary to conventional statistical wisdom overfitting. However, overparametrization leads problems with multiple optimal solutions that do not all share the same performance. Hence, the quality of the interpolating model is to large extent determined by the training algorithm. Alternate formulations the prediction problem can therefore lead to different interpolating algorithms with beneficial properties.
Explicitly, consider a multi-clase classification problem ()' {1, ........ .))...,K)) with non-negative loss function E, vanishing when fx( = (e.g., cross entropy). Instead of directly minimizing the expected loss (() (x) v)], namely,
we can use (P) formulate a classwise interpolation problem,
minimize 6EB
2
$10112
(P-CI)
subject to Ep [x) v)ly b k] = 0. for t: = = l,..,,
As shown by experiments in Section 5 (P-CI) measures and exploits the heterogeneous difficulty of fitting each class- information that is hard to obtain from the training data given that it is interpolated.
2.2 Empirical dual formulation
In MI., the objective/constraints of (P) are non-convex functions of 0, either because the parametriza- tion fe is complex nonlinear function (c.g. a neural network) or because the losses themselves

---

non-convex (as in, e.g., (PDDP). This hinders the use of constrained optimization methods based on projections, conditional gradients, or barrier functions 8 What is more, we only have access to the distribution TD, P,, Q through samples, so that the expectations in (P) must be estimated empirically. This leads to errors that affect Pa and (Pas(P) in non-trivial ways. To overcome these
issues, we turn to aualety-based methods [3]. Explicitly, define the Lagrangian of (P) as
T.Jo, X, n4) = Ep ([(Jo())
+ Ar, (9:(Jo(x), vi Σ Mg [M,()(x)),)), (1)
i=1
for x E R4 and u E R collecting the A and Hy respectively. The dual problem of P is then
D
sup
inf DEE
L(fo,),
(D)
XER ,
MER!
In this context, the weights X; Mú are called dual variables and the set Opt(D) of all solutions (A* of (D) is known the set of Lagrange multipliers. The dual (D) is relaxation of (P). i.e. D P (weak duality) and pS - D is called the duality gap. Convex optimization problems are
strongly dual, i.e. p D under certain regularity conditions such as Slater's condition (see [3
Proposition 5.3.ID). Of particular interest in this work is the empirical version of (D).
((), A inf L(fo,>, D sup
(i)
AERL MER.
OE
where q(>, (i) is the empirical dual function defined based on the empirical Lagrangian
M;
1
i(fe,>,
é (ffo(Xmo) vmoo
A
g: (. Mmmi) M.mi)
Mo mo=1
Mi
m,=1
h
j=1
11=1
that uses independently drawn samples (Xmo+ ymo) B. (Xm, Fm.) P., and (Xays In,) Qg-
10 have shown that (D) provides an effective way of solving P by showing that the solutions of D approximate
For inequality
learning problems [J = 0 in (P)l. prior works
those of (P) (generalization) and deriving practical algorithms to do so. The goal of this paper is to extend these results to the more general (P). While (D) remains empirical, unconstrained program amenable to be solved using stochastic optimization techniques (see Section 4 is no longer clear that its solutions generalize to (approximate) those of (P). Indeed, non-convexity hinders the use of classical duality theory to show P = D* and the presence of equalities invalidate the results from [1I. What is more, the errors introduced by using empirical, finite sample estimates of the expectations in (P) pose challenges even before considering equality constraints 11 Example 1]. We
address these concerns in the sequel after a pertinent remark.
Remark 2.1. While equality constraints can be written as inequalities, these reformulations pose theoretical and numerical challenges. For instance, the feasibility set of (P) does not change when replacing its equalities with (Ea2, [h, (x)(xxx))))))))))))))))))))))( S O. This formulation, however, involidates current duality and generalization guarantees for constrained learning (see, e-g., (2)), potentially even for convex problems (see, e.g., (42) Theorem 5.5. 5.11J). We may also consider appreximating each equality by the pair -E S Ee, (f)()()), v)] e. Interesttingy. taking
0 yields the same (empirical) Lagrangians and dual problems as (2) and (D) (see Appendix D.2,. though the feasibility set of the resulting problem has once again no interior. For e >> O, it is not straighfforward to determine the effect of this relaxation on the solution of (P) and the use of very small can lead to illconditioned problems even in the convex case (see Appendix D.T
3 Generalization error
In this section, we quantify how well the empirical dual problem D approximates the constrained learning problem (P). We do so by bounding the generalization error 1 D*1 (Theorem 3.1
which can be decomposed as
P - - p - D D D
(3)

---

The first term is the duality gap of (P) and the second is the dual estimation enror. The first assumption we make ensures that the dual problems and are well-posed. Explicitly, define the constraint value epigraph as
C (=
30 O s.t. Ep, (fx())))) v)] S wi, for 1, 1.....). and Ea, (f)( bj for 1,
(4)
Similarly, define é by replacing the expectations in (4) with empirical averages in 2). We will now discuss the assumptions under which Theorem 3.1 is derived, starting with the following.
Assumption There exists & > such that B(O E) = fce R ||c|| - {) S int (C) n
int (C) where int denotes the interior of the set and 0++J is the origin of R
Assumption [ ensures that (D) and ( have non-empty and compact solution (see e.g.
13
Proposition 1.4.1, 4.4.2J). It can be seen as a stronger version of Slater's condition 43 used in convex optimization, and in particular, implies that P* exists and is finite.
Duality gap. The bound on the duality gap is based on analyzing the properties of (P) when H. is large enough approximate benign function classes that have the property of decomposability. We 02 E + and measurable subset 2,
say that a set d is decomposable 444, if for any Φ1,
(1(x)
X Z xx(x,,
0s(x)
E Z
is also member of Φ. The L spaces and their analogue for vector valued functions, Bochner spaces [45] (see also Appendix B.I.I). are decomposable function spaces. We now introduce the functional version of (P.
P inf oe
En ((((()))) w)
subject to
Ee, [o(()))),)) y)] $ 0, for i = I,...,I, I, PB [ (((x). v)] 0. for 1, I....,J. is the same as in T. Similarly, its dual problem is given by
(P&)
Notice that the Lagrangian for
D sup inf AER MERJ de
L(ø, N1).
(D&)
When the distributions DD, Pr, Qj are atomless probability measures and & is decomposable, (P is strongly dual, i.e., P = D (see Appendix B.2 Proposition B.I We can therefore bound the duality gap in (3) by the decomposition
Pa D' = p P D D
(5)
The following assumptions allow
P to inherit similarly favourable duality properties based on (
Assumption 2. Let P+ corresponding to (R& K PP). Assume that
D = Σ Q3- and let (R( (RK :P4) denote the Bochner space
1. the distributions ID, P., Qj are atomless probability measures, and,
2. there exists a decomposable set C TP(RK, such that C T and solution Ø² Opt(P&) such that for some E θ and v > 0, 11 foll LF(K%:P) S
Assumption 3. The loss funcctions gis hi R y + R are L-Lipschitz continuous and the model fo(x) is Lg- Lipschitz continuous with respect to 0 at every x x X.
Atomlessness satisfied, for instance, measure has a density with respect the Lebesgue measure (Appendix(B.1)) Lemmm B.2). Several works have studied the approximation of decomposable sets like the [.P spaces by parametrized model classes like neural networks (46/48 and support vector machines 49 A concrete value of can be found in some cases, for example in 48 The regularity assumptions on the model and loss functions are mild. Loss functions only need to Lipschitz
continuous on the range of fe (x), as is the case for the Huber loss, square loss, and hinge loss when
5

---

the range of (x) and ) is bounded. An example of a model that is Lipschitz with respect to its parameters a feedforward neural network with Lipschitz activations when the data and parameters are bounded in norm.
To bound the terms in ( we also use the following quantity that measures the sensitivity of the feasibility set (P), namely,
R(v) sup inf 110 10-00ll22 o (FFFes(())
Er, (o:(ff(x), y)1 & Lv, for i = 1,..,,
where , D
(6)
and
Fo [),(((())) b)] Lu for j 1,...,J
R(v) measures the maximum distance between O, and Feas(P). Hence, it is decreasing function of e and vanishes when v = 0. However, relaxing the constraints causes the feasibility set to change radically, R(v) could be unbounded for >> 0. This can be avoided by ensuring that θ₂ is bounded, by e.g., regularizing θ by enforcing ||0||2 I W for some W > 0.
Dual estimation error. The next assumption allows us to bound the dual estimation error 1D--Dr
Assumption 4. Let P E {D.PI..... Q5} and let (x(*), y (()) be an i.idd sample of size N drawn from P. Denote LL = {f,g (l.g...... 91, h1,... h.J. Then, assume that there exists a function (UC,NO) N [0, 1] IR, such that, for all ó (0,1), 1), (a) quC is strictly decreasing in N, (b)
satisfies lim 5 UC [N, 6) O, and (c) for any L E L, the following is true:
P sup Ep [x), AE
Σ [(fo(x))
<C S 2 21-8.
4 is called uniform convergence, and is satisfied if e.g. H. has a finite VC-dimension Rademacher complexity (see [5o][Corylyryy 3.19, Theorem 3.3] and also [i[pooopsiiiooon III.)). Bounds on the VC dimension and Rademacher complexity, which are measures of model complexity, available for many model classes [51 52
Assumption
Main Result. The generalization enror in 33 can be bounded under these assumptions by combining (5) and the uniform convergence bound in Assumption 4 We next use yy to denote the tuple of dual variables for inequalities and equalities, i.e., (2,
Theorem 3.1. Let Nmin = min (M. M.... ... Mr, Ni...... .N, and assume that R(v) and P -0. Under Assumptions I there exist Riz E Opt(De), Opr(D), and 6 Opt(D). Moreover, for any 8 E (0, 1), holds with probability least + J)ö, that
|P 1 (1+
D'
Insll.) Lv LLeR(v) + (1+ max (1h I| 11,,) " 8).
(8)
The proof of Theorem 3.1 is deferred to Appendix
B We next discuss the main factors driving the
generalization error bound.
The main difference hetween constrained and unconstrained generalization bounds is that (8) is driven by the constraint sensitivity. This is represented by the Lagrange multipliers of (P) and its empirical and functional versions, which appear in the bound through their norms. More specifically, it is well known that for strongly dual problems, Lagrange multipliers are sensitivity measures (subgradients) of the optimal value with respect to the constraint constants. Explicitly, suppose that we were to perturb the constraints of (P) obtain
(* d) = inf
Ep [p[e(fe(x),
0
subject
Ep, (x:((f(()) w) sc. for I,..,,
(P-pert)
B2 [))()())), v)] = =d,.
for j = I,...,J.

---

The problem (P- (P-pert) defines the (perturbation) function (* d). If convex program) and (=(c d) is differentiable, then
were strongly dual (e.g.
x aP (0' ,0')
and 13 = OP OP* 00)
dc,
dd,
for i = I.....I and] j 1, (see 40 Equation 5.58)). Though differentiability and strong duality of (P-pet)) does not generally hold in our setting, approximate relations can be obtained in terms of the bound the duality gap P D (see Remark (..6). Thus, II ||^*|| + ||01 that appears in (8) measures how much the objective changes when the constraints are perturbed. Constraint sensitivity also appears in terms of R(v), which marks clear difference from the generalization bounds for inequality constraints (J = 0) that depend solely on ||^||] (see Remark3.11 The bound in (8) also depends the sensitivity of the loss functions and the model (with respect to its parameters) through their Lipschitz constants L and Lg respectively.
While these factors are dictated by the problem formulation, Theorem 3.1 shows us that they can be mitigated by using richer parametrizations (i.e., reducing v) and larger datasets (i.c., increasing Nmii)). Indeed, + 0, the first set of terms (relating to the duality gap) vanish. However, the sample complexity <VC (Nmin: 6) typically increases with larger model classes, i.e., as v decreases. Hence, find trade-off between approximation error and estimation error that mirrors the trade-off in unconstrained learning [53 Section 5.2].
To summarise, Theorem 3.1 reveals four key drivers of the generalization error: (a) constraint sensitivity, (b) sensitivity the losses and parametrization, (c) model capacity, and (d) sample size. The bound also mirrors the classical decomposition of the unconstrained learning error into an approximation error (here, the duality gap P - D*) and the estimation error (here, the dual estimation error D - D*)) We conclude this section with a few remarks.
Remark 3.1 (Comparison with results for inequality constraints). Notably, the bounds for prob- lems involving only inequality constraints from [12 TT) do not depend on the smoothness of the parametrization Lg (Assumption 3). This fundamental distinction is rooted in the fact that in the absence of equality constraints (J 0) going from & to H is akin to contracting the functional feasibility set Feas(P&) by tightening the functional inequality constraints. Consequently, (P&) and its parametrized formulation (P) remain closely aligned, and the latter approximately inherits the duality properties of the former. The equality constraints in (P) however make it that the feasibility sets are no longer nested. Changing the targets lead to more intricate changes in the set of feasible parameters 9. The sensitivity of the parametrization Lg therefore affects generalization. This is also the reason why Assumption [ reduces to the existence of a strictly feasible solution when J 0. Indeed, the presence of equalities requires the stronger regularity conditions in Assumption 7 to ensure that (P) is feasible for any small perturbation. The reader is referred to Appendix B.5 for additional technical distinctions.
Remark 3.2 (Functional strong duality). The core result underpinning Theorem 3.1 is the strong (Proposition B.I). The crux of the proof lies in proving that the
duality of the functional problem (P cost-constraint epigraph,
MØ = { V...)
3Ø E +b
s.l.
ED [((((x), w)1 =
Ep. (o:()()), x), w)1 S Ui for 1,
and
Eo, [h, (0(x), x)] for
is convex under Assumption Thus, while Pa) is not a convex optimization problem, a classical result from corvex optimization [13] Proposition 4.4. can be applied to the previous fact show that (P&) is strongly dual. The convexity of M is established using Lyapunov's 's theorem on the range of atomless measures 154 Chaper IX Corollary 5], closely related to the bang-bang principle in control theory (55). Proposition B.Ijhas appeared with minor variations in (56458 [1],, though our proof improves on for the regression case (continuous Y), which we prove without additional assumptions.
Algorithm
Theorem 3.1 essabllihhss that solving provides (approximate) solutions to P Next, we propose an algorithm to tackle (D) based on the traditional dual ascent method. This algorithm assumes access to an oracle for unconstrained problems as in [10] M. fact formalised in the following assumption.
7

---

Algorithm Primal-dual constrained learning algorithm
1: Inputs Loss functions l, Si hj, samples (Xma: ymo) ID, (Xm,: Mym,) ~ IP., (Xny, Mon)) Q for i = 1...... J = 1.....
iterations E N, dual learning rate fj > 0.
2: Initialize: ( t 0' (0) 0
3: for = 1,..., do
4:
((t) - O[L(f,, \1=-1), 11,((((111))
>> Assumption 5
5:
X - max
0, A, (1-1) + +1( Nr, Lm; Di (Sows (Xmz) Bm.))}
b for = 1,...,!
6:
Pj
(1) t ((-11 + n Ny Enjzi 1 1 (Soc (xng);
D for ,,....J
7: end for
Assumption 5. The solution (2, O(i A. returned by the oracle in Algorithm Cattoritnmppppee aapprox- imately minimizes the empirical Lagrangian 2 i.e, for p 2 0 holds that LiSe (uay 2. S p(),p) + + for all u.
In Algorithm T this oracle is used to update the model (primal variable) in Step while the empirical constraint violations (or slacks) are used to update the dual variables X, μ (Steps 5-6). If the oracle is optimal (i.e., p 0), Line 6-7 constitute projected subgradient ascent with respect to the dual objective q(), u)) [59]. Since the dual objective is always concave, subgradient ascent converges global optimum for certain reducing step size rules [59] Chapter 2]. However, the descent is generally non-monotonic, i.e., the last iterate is not necessarily the best iterate. Hence, guarantees
are often of the following form. Note that Theorem 4.1 relates the empirical dual value D to the average of the Lagrangian iterates.
Theorem 4.1. Suppose Assumptions Fandd and let the loss functions e, Dc. h be B-bounded.
Let Uo T'E0p(()
inf
(1~000 -r" Then, for any T E 19, it holds that,
T-1 D
Σ T
(ilfacs,(1))
Un sp
+ 2 JmBB2
(10)
2n/T"
1=0
If S (1+J)B2 and T then the bound is equal to 2p.
Uo. up"
Theorem establishes results for the dual iterates, modulo the averaging, but does characterise the feasibility optimality of g(t), Since the set of primal variables defined by the Lagrange multipliers (A+,a") need not be unique, all feasible, recovering feasible near-optimal model can be difficult. This not a substantial issue in convex optimization, where averaging solves this problem (e.g. [59] 62) Non-convex settings often rely randomization overcome this challenge (see, e.g. [1
10 63 ), although there is empirical and theoretical evidence that this not 65].
substantial issue in ML
Our experiments in Section show that replacing line 5 with single (stochastic) gradient descent step can produce feasible solutions (without additional primal recovery techniques) that also perform well with respect to the objective loss.
In practice, we do not have access to the oracle from Assumption 5
Experiments
In this section, we demonstrate the empirical performance of Algorithm on instances of presented in Section Detailed descriptions of the experiments can be found in Appendix E
Exact vs. approximate fairness. Figure compares models trained the COMPAS dataset [66 using the fairness formulation in (P-D)) against models trained with a double-sided inequality approximation with tolerance parameter (see Remark 2.1 and unconstrained baseline. The

---

Mean trend
67.9%
0.15
Aantrun-mmericn
Final Dual Variahles
Caucasian
Rate Disparity
0.10
0.3
Hispanic
67.8%
67.8%
0.05
Other
0.2
66.9%
66.8%
67.2%
0.00
0.1
0.05
0.100
DP
10
0.01
0.05
0.1
DP
0.0001
0.01
0.05
Tolerance (c)
Tolerance (e)
(a)
(b)
Figure 1: Exact approximate fairness. (a) Comparison betweeen (P-DP) and the incquality relaxation described in Remark 2.T with parameter splits) is reported for each method/tolerance. (b) Final (effective) dual variables for Algorithm [ Indeed, since the inequality relaxation uses two constraints for each group (upper and lower bound), show only the difference between upper and lower dual variables.
(10 random splits). Mean accuracy (across
1.0
Mean trend
54.8%
44.8%
Mean trend
0.8
Group Disparity
Overall Rate
0.3
0.6
66.
9%
67.8%
66.9%
0.2
0.1
64.1%.
55.2%
0.0
Unc.
DP
0.1
0.3
0.5
0.7
0.9
Unc.
DP
0.1
0.3
0.5
0.7
0.9
Preseribed Rate (rz)
Prescribed Rate (ry)
(a)
(b)
Figure 2: Prescribed rates. Solutions of (P-F) for different r, (10 random splits). (a) Average rate of positive outcomes across population, annotated with the mean accuracy (across splits); (b) Rate disparity across different groups
indicator functions that appear in the constrained formulations replaced by sigmoid functions to enable the use of gradient descent to replace the oracle in Step 4 of Algorithm [
Explicitly, we use
Ep [T [x(x) > 0.5] x E 9,] Ep [a (a (Jo(x) - 0.5)) x E 9,]
and similarly for the overall rate Ep [T [xx 0.5]] where denotes the sigmoid function. We split the dataset into a training (70%) and test (30%) set 10 times and report the results.
Figure Ta) shows that the equality formulation achieves the lowest disparity in group rates (measured the difference between the maximum and minimum group rates) comparable the inequality- based model with small tolerances (e.g., 10-+). Figure [ shows that the final (effective) dual variables for 10-4 are also indistinguishable from those of the equality formulation. However, see that looser tolerance (c = 10-3) introduces noticeable differences, both in the dual solution and the group disparity. This highlights the challenge of selecting an appropriate tolerance, a difficulty circumvented by directly enforcing the equality constraints.
Prescribed rates. In Figure 2 we showcase the results of imposing specific group rates using P-FF) and compare them to unconstrained and DP-constrained fi.e., (P-DP) problems. With the exception of extreme rates (0.1 and 0.9), which yield nearly constant classifiers, models with intermediate targets ry achieve low group disparities, comparable to those of the DP- model. However, while (P-D)) maintains an overall rate of positive outcomes close to the unconstrained model, (-FF) allows this rate to be adjusted more granularly. This flexibility comes negligible difference in accuracy for prescribed rates close the DP rate. For example, Т 0.5 achieves the same test accuracy as P-DP) (Figure 2 a)) and similar (test) group disparities (FigureD(b))

---

1.2
PINN
1.0
Relative I.2 Error
P-BVP
40
0.8
Test Eiror
30
0.0
20
0.4
10-
0.2
0.0
30
0.200
0.225
0.250
0.275
0.300
0.325
Epach
x10*
Dual Value
Figure 3: Relative L error for convection BVP
Figure 4: Comparison of classwise test errors and dual values for CIFAR-I00 trained with (P-CT) (along with the best fit line). The correlation is 0.89 indicating a strong linear relationship.
(3 = 50). The lines show the mean curve across 5 runs, and the shaded region indicates the max and min curves.
Table
Relative L error for convection
Table 2: Test Accuracy on CIFAR-10/100
8
PINN
[-BVP]
Dataset
ERM
(P-CI)
30
2.46 + 0.99 %
0.62 + 0.17 %
CIFAR-IO 10
95.03 + 0.21 %
95.01
0.10 %
50
56.0 25.8
30.7 + 24.2 %
CIFAR- 100
76.11 + 0.28 %
75.17 0.21 %
Boundary value problems. Table shows that taking constrained approach to solving con- vection BVP with sinusoidal initial condition (see Appendix [F.2 for details) outperforms the un- constrained approach with fixed multipliers for the boundary and initial conditions (PINN). The mean and standard deviation of 5 seeds have been reported. The primary challenge of solving this BVP propagating the initial condition through time since the solution itself is very regular. Thus, the improvement may be explained by larger dual variables for the boundary conditions (as seen in Appendix Figure 9).
Interpolating classifiers. Table 2 (also computed over 5 seeds) shows that (-CII has worse test accuracy compared the unconstrained problem (ERM) on (IFAR-100-though the gap is not large. On the other hand, solving (P-CT) using Algorithm I yields dual variables that exhibit an approximately linear relationship with the mean test error of the class. Since models are trained to interpolation on the train set, this information is not generally available without cross- validation. It can be used as a confidence measure for the performance of the model to detect biases in the model. Meanwhile, (P-CI) performs virtually the same as ERM on CIFAR-10. 10. This relationship between test error and dual variables may be partially explained by 9 which suggests that large dual variable indicates constraint on the class wise error that significantly contributes to the model complexity (10133)since relaxing the constraint would lead to large decrease in the parameter norm. Though this norm has been tied to generalization error in [67 (68) definitive answer would require a more detailed analysis that is beyond the scope of this work.
6 Conclusion
In this paper, we studied equality-constrained learning problems, i.e., statistical optimization problems with equality constraints. We extended the existing generalization theory for meequllty-constraimn problems, showing that equalities are also tractable through Lagrangian methods as long as the parametrization is rich enough. Nevertheless, they demand stronger assumptions than inequalities. We also introduced practical algorithm based on dual ascent to solve problems with both equality and inequality constraints. We illustrated the behavior of this algorithm in fair learning problem, showing results for both classical problems, involving demographic parity, as well as new formulations enabled problems, namely, learning tasks that enforce specific prediction rates
by these for each group. We also showcase results for solving BVPs and fitting interpolating classifiers.
10

---

Acknowledgements
The work of Aneesh Barthakur funded by Deutsche Forschungsgemeinsshatt (DFG, German Research Foundation) under Germany's ' Excellence Strategy EXC 2075 390744006. The work of L.F.O. Chamon is supported by the Agence Nationale la Recherche (ANR) project ANR-25- CE23-3477-01 as well as a chair from Hi!PARIS, funded in part by the ANR AI Cluster 2030 and ANR-22-CMAS-0002. The authors thank the Stuttgart Center for Simulation Science (SimTech) and the International Max Planck Research School for Intelligent Systems (IMPRS-IS) for supporting Aneesh Barthakur and acknowledge the computing time provided on the high-performance computer HoreKa by the National Performrrre Computing Center KIT (NHR @ KIT). This center is supported by the Federal Ministry of Education and Research and the Ministry of Science, Research and the Arts of Wurtttebbrr as well as the DFG.

---

References
[1] Solon Barocas, Moritz Hardt, and Arvind Narayanan. Fairness and Machine Learning: Limita- tions and Opportunities. MIT Press, 2023.
[2] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards Deep Learning Models Resistant to Adversarial Attacks. In International Conference on Learning Representations, 2018.
[3] Hongyang Zhang. Yaodong Yu, Jiantao Jiao, Erie P. Xing, Laurent EI Ghaoui, and Michael I. Jordan. Theoretically Principled Trade-off between Robustness and Accuracy. International Conference Machine Learning, pages 1472-7482, 2019.
[4] Cynthia Dwork and Aaron Roth. The Algorithmic Foundations of Differential Privacy. Founda- tions and Trends@ in Theoretical Computer Science, 9(3-4):211 11221114001 407, 2014.
[5] Javier Gareía and Fernández. A Comprchensive Survey on Safe Reinforcement Learning. Journal of Machine Learning Research, (00(42):14371444 2015.
[6] Santiago Paternain, Miguel Calvo-Fullana, Luiz F. O. Chamon, and Alejandro Ribeiro. Safe Policies for Reinforcement Learning via Primal-Dual Methods. IEEE Transactions on Automatic Control, 68(3):1321-1336, 2023.
[7] Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and Harnessing Adver- sarial Examples. In International Conference on Learning Representations, 2015.
[8] Richard Berk, Hoda Heidari, Shahin Jabbari, Matthew Joseph, Michael J. Kearns, Jamie Morgenstem, Seth Neel, and Aaron Roth. A Convex Framework for Fair Regression. CoRR, 2017.
[9] Irina Higgins, Loic Matthey, Arka Pal, Christopher Burgess, Xavier Glorot, Matthew Botvinick, Shakir Mohamed, and Alexander Lerchner. beta-VAE: Learning Basic Visual Concepts with Constrained Variational Framework. In International Conference on Learning Representations, 2017.
[10] Andrew Cotter, Heinrich Jiang, Maya R. Gupta, Serena Lutong Wang. Taman Narayan, Scungil You, and Karthik Sridharan. Optimization with Non-Diffcreetiabbl Constraints with Applica- tions to Fairness, Recall, Chum, and Other Goals. Journal of Machine Learning Research, 20:1 20:172:1-172:59, 2019.
[11] Luiz F. O. Chamon, Santiago Paternain, Miguel Calvo-Fullana, and Alejandro Ribeiro. Con- strained Learning With Non-Convex Losses. IEEE Transactions on Information Theory, 2023.
[12] Luiz F. O. Chamon and Alejandro Ribeiro. Probably Approximately Correct Constrained Learning. In Advances in Neural Information Processing Systems, 2020.
[13] Dimitri Bertsekas. Convex Optimization Theory. Athena Scientific, 2009.
[14] Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez-Rodriguez, and Krishna P. Gummadi. Fairness Constraints: Mechanisms for Fair Classification. In International Conference on Artificial Intelligence and Statistics, pages 962-970, 2017.
[15] Moritz Hardt, Eric Price, and Nati Srebro. Equality Opportunity in Supervised Learning. In Advances in Neural Information Processing Systems, pages 3315-3323, 2016.
[16] Matt J. Kusner, Joshua R. Loftus, Chris Russell, and Ricardo Silva. Counterfactual Fairness. In Advances Neural Information Processing Systems, pages 4066-4076, 2017.
[17] Taco Cohen and Max Welling. Group Equivariant Convolutional Networks. In International Conference on Machine Learning, pages 2990-2999 2016.
[18] Risi Kondor and Shubhendu Trivedi. On the Generalization of Equivariance and Convolution in Neural Networks to the Action of Compact Groups. In International Conference on Machine Learning, pages 2752-2760, 2018
12

---

[19] I. Hounie, L. F. O. Chamon, and A. Ribeiro. Automatic Data Augmentation via Invariance- Constrained Learning. In International Conference on Machine Learning, pages 13410-13433, 2023.
[20] Geoff Pleiss, Manish Raghavan, Felix Wu, Jon M. Kleinberg, and Kilian Q. Weinberger. On Fairness and Calibration. In Advances in Neural Information Processing Systems, pages 5680- 5689, 2017.
[21] Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q. Weinberger. On Calibration Modern Neural Networks. In Proceedings of the 34th International Conference Machine Learning, volume 70, pages 1321-1330. Proceedings of Machine Learning Research, 2017.
[22] Mikhail Belkin. Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolation, 2021.
[23] Shengjia Zhao, Jiaming Song. and Stefano Ermon. The Information Autoencoding Family: A Lagrangian Perspective on Latent Variable Generative Models, 2018.
[24] Xi Chen, Yan Duan, Rein Houthooft, John Schulman, Ilya Sutskever, and Pieter Abbeel. InfoGAN: Interpretable Representation Learning by Information Maximizing Generative Ad- versarial Nets. In Advances in Neural Information Processing Systems, 2016.
[25] A. Robey, L. F. O. Chamon, G. J. Pappas, H. Hassani, and A. Ribeiro. Adversarial Robustness with Semi-Infinite Constrained Learning. In Conference on Neural Information Processing Systems, pages
2021. equal contribution.
[26] Sam Corbett- -avets, Emma Pierson, Avi Feller, Sharad Goel, and Aziz Huq. Algorithmic Decision Making and the Cost of Faimesss. In ACM SIGKDD International Conference Knowledge Discovery and Data Mining, pages 797-806, 2017.
[27] Alexandra Chouldechova. Fair Prediction with Disparate Impact: A Study of Bias in Recidivism Prediction Instruments. Big Data, 5(2):153-163, 2017.
[28] Sam Corbett-Daviee and Sharad Goel. The Measure and Mismeasure of Fairness: Critical Review of Fair Machine Learning. 1rxiv:/808.0000 2018.
[29] Michael Feldman, Sorelle A. Friedler, John Moeller, Carlos Scheidegger, and Suresh Venkata- subramanian. Certifying and Removing Disparate Impact. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 259-268, 2015.
[30] Lloyd N. Trefethen. Finite Difference and Spectral Methods Ordinary and Partial Differential Equations. 1996. Unpublished text.
[31] Hans Petter Langtangen and Kent-Andre Mardal. Introduction to Numerical Methods for Variational Problems. Springer International Publishing. 2019.
[32] M. Raissi, P. Perdikaris, and G.E. Karniadakis. Physics-informed neural networks: A deep learning framework for solving forward and inverse problems involving nonlinear partial differential equations. Journal of Computational Physics, 378:686-707, 2019.
[33] Viggo Moro and Luiz F. O. Chamon. Solving Differential Equations with Constrained Learning. In International Conference on Learning Representations, 2025.
[34] Sifan Wang, Yujun Teng, and Paris Perdikaris. Understanding and Mitigating Gradient Flow Pathologies in Maysics-Informed Neural Networks. SIAM Journal on Scientific Computing. 43(5):A3055-A308. 2021.
[35] Aditi S. Krishnapriyan, Amir Gholami, Shandian Zhe, Robert M. Kirby, and Michael W. Mahoney. Characterizing possible failure modes in physics-informed neural networks. In Advances in Neural Information Processing Systems, pages
2021.
[36] Robert F. Schapire, Yoav Freund, Peter Barlett, and Wee Sun Lee. Boosting the margin: new explanation for the effectiveness of voting methods. In ICML, pages 322-330, 1997.
13

---

[37] Mikhail Belkin, Daniel J. Hsu, and Partha Mitra. Overfitting perfect fitting? Risk bounds for classification and regression rules that interpolate. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett, editors, NeurIPS, pages 2306-2317, 2018.
[38] Sébastien Bubeck. Convex Optimization: Algorithms and Complexity, 2015.
[39] Gábor Braun, Alejandro Carderera, Cyrille W. Combettes, Hamed Hassani, Amin Karbasi, Aryan Mokhtari, and Sebastian Pokutta. Conditional Gradient Methods, 2025.
[40] Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
[41] Juan Elenter, Luiz F. O. Chamon, and Alejandro Ribeiro. Near-Optimal Solutions of Constrained Learning Problems. In International Conference on Learning Representations, 2024.
[42] Alexander Shapiro, Darinka Dentcheva, and Andrzej Ruszczynski. Lectures on Stochastic Programming: Modeling and Theory, Third Edition. Society for Industrial and Applied Mathematics, 2021.
[43] Morton Slater.
Lagrange Multipliers Revisited. Cowles Foundation Discussion Papers 80,
Cowles Foundation for Research in Economics, Yale University, 1959.
[44] Andrzej Fryszkowski. Fixed Point Theory Decomposable Sets. Springer, 2004.
[45] Tuomas Hytönen, Jan van Neerven, Mark Veraar, and Lutz Weis. Analysis in Banach Spaces. Springer, 2016.
[46] Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks universal approximators. Neurul Networks, 2(5):359-366, 1989.
[47] Boris Hanin and Mark Sellke. Approximating Continuous Functions by ReLU Nets Minimal Width, 2017.
[48] Zuowei Shen, Haizhao Yang, and Shijum Zhang. Deep Network Approximation Characterized by Number of Neurons. Communications in Computational Physics, 1688 2020.
[49] Ingo Steinwart and Andreas Christmann. Support Vector Machines. Springer, 2008. Information Science and Statistics.
[50] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning. MIT Press, 2012.
[51] Peter L. Bartlett, Nicholas A. Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly-tight VC-dimension and Pseudodimension Bounds for Piecewise Linear Neural Networks. Journal of Machine Learning Research, 20(63):1-17, 2019.
[52] Taeyoung Kim and Myungjoo Kang. Bounding the Rademacher Complexity of Fourier Neural Operator. Machine Learning, 113(5)24477225) 24998 2024.
[53) Shai Shalev-Shwartz and Shai Ben-David, Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014.
[54] J. Diestel and J. J. Uhl. Vector Measures. Mathematical Surveys and Monographs. American Mathematical Society, 1977.
[55] M. Ali Khan and Nobusumi Sagara. The Bang-Bang, Purification and Convexity Principles in Infinite Dimensions: Additional Characterizations of the Saturation Property. Set- Valued and Variational Analysis, 22(4):721-746, 2014.
[56] Alejandro Ribeiro. Optimal resource allocation in wireless communication and networking.
EURASIP Journal Wireless Communications and Networking, 2012(1), 2012.
[57] Luiz F. O. Chamon, Yonina C. Eldar, and Alejandro Ribeiro. Strong Duality of Sparse Functional Optimization. In Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 4,49,9474,,2000
14

---

[58] Dionysis Kalogerias and Spyridon Pougkakiotis. Strong Duality in Risk-Constrained Nonconvex Functional Programming, 2023.
[59] Naum Zuselevich Shor. Minimization Methods for Non-Differentiable Functions. Springer, 1985. Springer Series in Computational Mathematics.
[60] Hanif D. Sherali and Choi Gyunghyun. Recovery of primal solutions when using subgradient optimization methods to solve lagrangian duals of linear programs. Operations Research Letters, 19(3):105-11 113, 1996.
[61] Torbjöm Larsson, Michael Patriksson, and Ann-Brith Strömberg. Ergodic, primal convergence in dual subgradient schemes for convex programming. Mathematical Programming, 86(2):283-
3 122 1999.
[62] Angelia Nedić and Asuman Ozdaglar. Approximate Primal Solutions and Rate Analysis for Dual Subgradient Methods. SIAM Journal on Optimization, 19(4):1757-1780, 2009.
[63] Michael Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu. Preventing Fairness Gerryman- dering: Auditing and Learning for Subgroup Fairness. International Conference on Machine Learning, volume 80, pages 2564-2572. 2018.
[64] Tianyi Lin, Chi Jin, and Michael Jordan. On Gradient Descent Ascent for Nonconvex-Coneee Minimax Problems. In International Conference on Machine Learning, volume 119, pages 6083-6093, 2020.
[65] Tanner Fiez, Lillian J. Ratliff, Eric Mazumdar, Evan Faulkner, and Adhyyan Narang. Global Convergence to Local Minmax Equilibrium in Classes of Nonconvex Zero-Sum Games. In Advances Neural Information Processing Systems, pages 29049-290009 2021.
[66] ProPublica.
Compas data analysis, 2016.
compas cempas-analysia.
[67] Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-Based Capacity Control in
Neural Networks. volume 40 Proceedings of Machine Learning Research, pages 1376-1401, 2015.
[68] Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-Independent Sample Complexity of Neural Networks. In COLT, volume 75 of Proceedings of Machine Learning Research, pages 297-299, 2018.
15

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our contributions are listed in the abstract/introduuciin and accurately describe the contributions of the paper, namely generalization theory for equality-constrant learning problem based on new regularity assumptions (Section characterization of approximation and generalization error of solutions (Theorem 3. and analysis of dual ascent algorithm (Sections)) 5).
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer:
[Yes]
Justification: The limitations of the theory developed here are clearly listed throughout the paper, e.g., the issues of primal recovery, non monotonicity of dual ascent (Section 4 and the need for stronger regularity assumptions than inequality-constrinne constrained problems (Section
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "I "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
16

---

3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: All assumptions are clearly listed and justified (namely, Assumptions [
Proofs to all claims stated in the paper are available in the appendices. Explicitly, Theorem
3.1 (Appendix [B). and Theorem [4. (Appendix C). Supporting results referred in the paper are proven and discussed in Appendix D
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: All experimental details needed to reproduce the experimental results, includ- ing optimizer and hyperparameters, are described in Section 5 and Appendix F
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access hosted model (e.g., in the of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
17

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification The python code used to reproduce all experiments in the camera-ready will be uploaded to GitHub.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cr
Soddddes/CodSuumisstt
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended the paper) is recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All experimental details needed to reproduce the experimental results, includ- ing the data preprocessing and splits, are described Section 5 and Appendix E
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Error bars are provided on all experiments across different seeds and train/test splits (see Figures
2).
Guidelines:
18

---

The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: The experiments do not require any particularly intensive computer resources. We describe all the resources used during our experiments in Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics /
Answer: [Yes]
Justification: We have reviewed the NeurIPS Code of Ethics and found that our work presents none of the issues raised therein.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
19

---

The primary contribution of this work is theoretical and presents no major direct societal impact, be they positive or negative. That being said, its developments can be used to address issues of, e.g., fairness, as the work illustrates. This application is clearly presented and discussed in the manuscript. Guidelines:
Justification:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negatíve societal impacts include potential malicious or unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g.. gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This work poses such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging. and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
The usage of the COMPAS dataset is properly credited in Section
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
20

---

The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g.. website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperssi thoode com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out to the asset's ' creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
This paper does not release new assets.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the datasct/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing research with human subjects.
Guidelines:
21

---

The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: Commercial LLM tools were used only during the writing of the manuscript and no LLM tools contributed to the analyses, methodology, or main results of the paper. As per the L.M policy, we do not disclose this use the main body of the manuscript.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https://neure) httpps//eearrpss.c/o/ooeeeeeeeee for what should or should be described.
22

---

LEARNING WITH EQUALITY CONSTRAINTS
ADDITIONAL MATERIAL
Related work
24
Proof of 3..
25
Preliminaries
25
B.2
Functional strong duality
31
B.3
Duality gap
33
B44
Dual estimation error
37
Proof of Theorem
39
Proof of T'heorem 4.1
41
Additional theory
45
D.I Example: : minimum norm interpolation
45
D.2 Comparing equalities with double sided approximation
49
Experiment details
50
Fairness
50
2
Boundary value problems
51
Interpolating classifiers
52
Additional plots
53
Pairness
53
Boundary value problems
56
Interpolating classifiers
58
Additional References
60
23

---

A Related work
Unconstrained learning. Empirical risk minimization forms the cornerstone of modern machine learning applications, supported by a rich theory of generalization [ However, as machine learning becomes increasingly embedded in real world applications, there a growing need to deal with multi-faceted problems involving multiple losses and/or requirements beyond accuracy, such as fairness [4] (. robustness [6] 77, privacy (8) safety [9] [0], and scientific knowledge [[]] The traditional approach to handling multiple requirements is to use weighted sum of the loss functions as the objective (e.g.. [12 ID), ) choosing the weights by trial and error, cross- validation, or a problem-specific heuristic. This approach is often brittle and time consuming.
Inequality-cone constrained learning. Inequality-constrr incorporate requirements into traditional learning problems. As in unconstrained learning, these tasks are formulated as statistical risk minimization problem, albeit with inequality constraints. Yet, this leads to non-convex programs for virtually every modern ML model, which make them challenging to solve [1] [6]. In convex settings, classical results for Sample Average Approximation (SAA) methods can be found in [8]. Generalization bounds have also been derived in [19] (for linear classifiers and fairness constraints), (20] (for convex losses, fonvex-fractional losses, and fairness constraints), and [21] (for fairness constraints). In the general non-convex settings, certain duality properties have been shown to hold when using sufficiently expressive parametrizations, leading to a practical learning rule with generalization guarantees 22 23]. The resulting primal-dua algorithms can be interpreted as incorporating the combination weights from unconstrained learning into the optimization process and have been used in various ML applications, such as fairness
learning uses constrained optimization to
19 24 22 23 25), invariance (26).
classification (27]. and robustness (28). Our work is an extension of these works on non-convex, constriiee learning problems.
Equality constrained learning, Equality constraints have been used in ML to express important problems, such as group fairness 3TI invariance [2] 33,, calibration M 35), distribution matching [36), and independence (7). While stochastic optimization with deterministic equality constraints has been extensively studied in the literature
41. less is known about stochastic
problems with statistical equality constraints e.g., constraints defined via expectations over data, such those considered in this work (Section 2).
or enforced by post-processing schemes (e.g., group fairness in 30) When the constraint function and its derivatives are only accessible by noisy oracles, solutions based on upper/lower bounds as well as Sequential Quadratic Programming (SQP) or trust region methods have been investigated 44
Equality constraints are often incorporated directly into the model (see, e.g., 42 43
More similar to our setup [88 that uses a primal-dual approach similar to ours, but rely on transforming equalities into inequalities using non-negative wrapping function (e.g.. quadratic). While their empirical results are promising, this approach has severe numerical and theoretical issues as discussed in Remark 2.1 From theoretical perspective, [49] considers the same problem we do, extending the SAA framework to equality constraints using inequality relaxations. They show that if the relaxation is carefully tightened as the sample size increases, it is possible to asymptotically obtain solutions of the population problem. These results are, nevertheless, (a) asymptotic, assuming access to infinitely many i..dd. samples; (b) focused a relaxation of the original problem; and (c) reliant on interior-poinl methods that are not well-suited to the large-scale, non-convex settings of ML.
24

---

B Proof of Theorem 3.1
B.1 Preliminaries
B.1.1 Bochner spaces
Let (X V: Exxy, P) be the probability space [50] corresponding to the random variables (x, y)- Let (R* [)(R)) be the Borel sigma algebra associated with I i.c. the smallest sigma algebra containing all the open sets. The Bochner spaces [S]][Section 1.2.b] are a direct generalization the L spaces, for measurable vector valued functions. Consider mappings from X' to R The Bochner space (PR
K PP,, for p [1, oo), the space all vector valued functions Φ X - IR
such that
( [(x(x)]1 dF)
1/p
| (P(K)))))
finite. (RRK); is similarly defined by the norm,
[00 esssupxEXXP |1ø(x)]1, = sup fc 0 0 2 ct) = =
For p E [1, oo] the spaces LPR IP) Banach spaces. The space L ( K P)) is precisely the space of functions for which the Bochner integral, form vector integral, exists.
Our primary space of interest, ( where P+ = D + - + Q, is actually the intersection the Bochner spaces corresponding to the summands. This follows from the linearity of the Lebesgue integral (for scalar functions) with respect to the measure ([50) Exercise 4.27).
Lemma B.1. Let IB, PP be positive measures measurable space, and f X - R be non-negative measurable function. Then,
f f(x) d(B+P) f(xx) dB + f(x) dr.
and moreover, (a) ( (B P) = LB) L' (P), and more generally (b) T(RK: (PRRK;)) P) for E oo]
Proof. Part 1 Suppose 0. Let X'a be the characteristic function of measurable set A. Recall that there exists a sequence of positive simple functions (x) = Σi= a,K',, (x) that are upper bounded by f and converge to f. The integral of fn (with respect to any measure the same measurable space) is an increasing convergent sequence whose limit defined as the integral of f (see [50] Definition I.b.3(b) and Theorem 1.2.17 for more details).
By applying the fact that (IP + (A) (PA)) ) + B(A) (by definition) for any measurable set A, we obtain that,
/ fx( d(B + = / fn (x) dB fn (x) dF.
the limits (with respect to ni) of both terms on the RHS exist, then the limit on the LHS exists as well (52) Theorem 3.4). This proves that / (B) (I) = L.- L. PP).
On the other hand, note that f (x) dIB < (x) d(B + IP) since / (x) dP 2 0. Therefore (x) d(B + IP) is convergent, since / [x) d(B + $ f(x) d(B + P), therefore.
[n(()) dB < / f(x) d(B FF)
Therefore J (x) dB is convergent sequence since it increasing and bounded (and by symmetry so is f fx() dP). This proves that f L' (BB P) f L' (B) n L (P). Therefore for non-negative function E (B + f (B)
25

---

Part 2: Now, consider a general f. It is known Theorem 1.33] that f f L (IP + +B) iff.
11 / [x(x] (dP + dB) < co.
Therefore,
f T = Ifl (B+P)
(11)
If (B)
(12)
fE (B)
(13)
Equation 112 follows from the first part, and and This proves (a).
13 are applications of 53 Theorem 1.33].
Part 3: The proof for (b) follows similarly, For p E [1, 00),
Φ E 1 IR B)
= 101 E ( F)
(14)
= (BB)
(15)
ò E B)
(16)
Equation (15 follows from the first part, and 14 and 16 are applications of the definition of the Bochner norm.
Part 4: Finally we consider the case where = co. Let O(c) = fx X [lx(x)]1 2 c}. Then, consider,
|| (B(BPP) = inf {c > 0 (IB P)((c) = 0}
inf fc > 0 [B((()) = 0.P(O(c)) = 0}
inf {c > 0 [B((())) = 0) inf {c P(O(c)) 0}}
max
mmax (10) ( [=)
(17)
The steps are trivial. It is obvious from Equation L PP.
that L (R + PP) (R*;
B.1.2 Atomless vector measures
A vector measure [54] over (X V/ Exxy) is set function that takes values in Banach space (instead of RR).
Definition B.1. 154 pp. Let (X x x) Exxy) be a measurable space and let (I-l) be a Banach space. Then G Exxy + V is countably additive vector measure, if for all sequences of disjoint
sets { G(U E,) 1im Ei_, G(E)).
We are interested in atomless vector measures, which appear as intermediate object in the proof of Proposition B.I
Definition B.2. Let (X, Σx) be a measurable space and (V, II-II) be a Banach space. A vector measure G Σx + V is called non-atomic or atomless iff for any A E Ex, such that G(A) # 0, there exists B Σx such that S and G(B) & {0, G(A)).
We are interested in the following "closure" properties of atomless measures.
Lemma B.2. I: R integrable with respect to a measure space (X, Fxx, P), where an atomless measure, then the measure V Σx TR,
YA E Ex. v(A) C(x) dp.
is atomless scalar measure.
26

---

Lemma B.3. Let N E N. If....... .N Ex I. are atomless scalar measures measurable
space (X, )x), then the vector measure Ex + RN defined by.
Ae G(A) (A) PN()]]
is countably additive atomless vector measure.
Before we prove Lemma B.2 we note a few properties of the indefinite integral u(A) = SA L(x) dP.
Remark B.1. Note that v is indeed measure over the measure space (X', Σx) 150 Section 1.5, Indefinite integrals). Moreover, is absolutely continuous with respect P, i.e. for any Σx.
P(A) = 0 v(A)=
(18)
This can be inferred from the fact that if A is a P-negligible set (i.e. P(A) = 0) then the indefinite integral SA ((x) dP is 0 for every function & (50 Proposition 1.4.13) 13].
Remark B.2. If u is a finite signed measure Ex, then it admits so-called Jordan Decomposition
53
Section 6.6).
AA Σx, ((A) VA v-(A),
(19)
where V4,V- V- are non-negative measures. The Hahn decomposition theorem (53 Theorem 6. 14] further states that there exists disjoint measurable sets X+ and X_ such that X+ UX X, and for all A E Ex.
(A) = ((An2+) and V- (A( - -v-=
(20)
In particular, Equations 19 and (20) imply that the measure of any subset of X4 (resp. X-) with respect to u non-negative (resp. non con-positive). We will also need the following set,
No fx X' [(x) = 0}
No is a measurable set since X, = (0), and 0 E B(R), the Borel sigma algebra on R. as it can be represented as countable intersection of open sets (e.g. n2 n: n 1)). It is obvious that v( F)) for any C Xg-
We will now prove Lemma B.2
Proof of Lemma B.2
Proof. As noted in Remark B.I v is indeed a (signed) measure. Suppose that for an arbitrary
A E Σx, v(A) * O. Without loss of generality, assume that v(A) >> 0, the negative case follows by symmetry. To prove that v is atomless we need to prove the existence of a measurable set C Á such that v/ (B) (u(A),0) 0).
Consider the Jordan decomposition of 1/,
((A) 14 (A) (A).
Since v_ is non nog-nigative measure, and v(A) > 0, therefore = (A) r(A) + > 0. Remark B.2 states that 2 (A) v(A X.). Therefore (An > Clearly,
v( ( x4) vrwnnAnn Xx) + v(An n (9).
Clearly (A = 0, therefore vAA n X = v(An > O. Let A, = AnX n2g.
The absolute continuity of μ with respect to P implies that PP(A.) >> 0 since v(A)) > 0. Since is atomless, therefore there exists a set B C A such that (B) E (P(A.). 03. Clearly,
((A)) P(B) P A+))
(21)
Since P is a nen-negative measure therefore P(B 2 and P(B n.44) 2 0. Now since P(B) 4 (IP 0}. (2l) implies that
0 < P(B) < P(A_) and 0 < B 0 A4) < P(A.).
(22)
27

---

Now, it is also true that,
- + + n nA+).
(23)
Let I (x) be the indicator function of the set B. taking the value 1 when x E B and 0 otherwise. Since B S Xx, therefore r(B) 2 O. Now suppose, if possible, that v(B) Sg (xx) dP Then according 50 Proposition 1.4.13], g (xx)) is 0 almost everywhere with respect to P. Since everywhere on B. this implies that [(x) must be O almost everywhere on B, i.e. except for null subset, say N. Explicitly, [(x) is 0 on B \ N and since IP () > 0, therefore N * B and B \ N j 0. However, since Xn is superset of B, therefore [(x) + everywhere on B, including B N, which is a contradiction. Therefore v 0.
= [x(x)
Similarly, we can argue that (B nA) > since P(B ((BBOA, nA+)) > 0 and B n n. S & No. Therefore,
0 <<<B)<<(A)))
v(A) - v- and D_ non-negative, therefore v(A+) = (A) v(A). If v(B) # v( (A), we are done since B C A and v(B) > O. Now suppose that v(B) r(A). Then since P(B) > 0, there exists 1' C B such
Recall that we showed that
(4 Since 44 (A) 2
that 0 < P(B)) < PBB). As before we can prove that < v(B) < v(B) by utilising the fact
that PBB') and B' C X4 O No. But this time, v(B") < v(B) ((A) by construction. Since
B' C and B(B') $ (0, ((4) therefore v atomless.
The proof for Lemma B.3 almost trivial.
Proof of Lemma B.3.
Proof. It is easy to verify that countable additivity is preserved by concatenating scalar measures, so will verify that atomlessness is also preserved. Consider A E Ex such that G(A) + 0. Therefore there exists an index such that (A) * 0. Since 24 is atomless, therefore there exists B C A such that (B) (A) It follows that G(B) & {G(AA) 0} which proves the atomlessness of G.
B.1.3 Constrained optimization problems
In this section we will define and discuss the main objects involved in Lagrangian duality in a unified manner with respect to generic optimization problem (Pa). For this section, let 1, 9i, hy be functions from X' R, then consider the following optimization problem,
inf P
{(x:)
=EX
subject to
gx())= 1 0, for = I,...,I I hy(x) 0, for 1.....JJ J.
(Pp)
Let Feas(Po) refer to the subset of X that satisfies all the constraints, i.c. the set of feasible solutions. If (Po) is infeasible, we set Po to +00. If P/ -c then we say that (Po) is unbounded. If é is bounded, then (Po) is also bounded (from below). Let Opt(Pa) refer the subset of Feas(Po) that achieves Pg i.e. the set of optimal solutions. Closely related to (Po) is its Lagrangian,
Lo(z,A,p) = ((x) Σ (x)(()) Σ (g)
R. (non-negative) and μ R. are the dual variables, collecting X and μ respectively. The dual function of (Po) is (o(,, inf Lo(æ, X, n). The dual function defines the dual problem, xEX
where À E
D sup 20 ERER
qu(A, p1)
sup min Lo(æ, X, 14).
(Dn)
E, ZEX
The optimal dual variables, when they exist, are denoted with a x, such as (*:p")) We denote the set of all optimizers of (D,) Opt(Do), which are also often called Lagrange multipliers. Let
28

---

Fo X' + I1+++J be the vector function obtained by stacking the objective and the constraint functions, i.c. Vx X
Fo(a)) = ((()))))))))) (() h=()=
We call Fo the cost constraint vector of Pol. and the following set will be called the cost constraint epigraph of (PD).
Mo Fo(2) + + x 10)".
Another important set the projection of MM on the constraint axes,
Co {(,,)) v) E R (f.. u, Mo}
Co( + x (0)".
(24)
where Cu(x)) = ..... 91 h1)) (x)] the vector function formed by stacking only the I + J constraint functions. We call Co the constraint vector and Co the constraint value epigraph. The relative interior of Co defined as,
relint (Co) = fy E Co Be > 0, s.t. B c) naff (Co) S Co}
where aff (Co) is the affine hull of Co and e {=1 |1 =|| S e) is ball centered E RI+J
B.1.4 Geometric conditions for strong duality
D is relaxation of (Po). i.e. Dj Pj- This fact is called weak duality in convex optimization.
When the equality holds, this fact is called strong duality and (Pn) is said to be strongly dual. Classical
convex optimization provides the following result tying the convexity of the cost constraint epigraph
Mo and the strong duality of (Po).
Theorem B.1. 1S Proposition 4.4.1 (variation)] Let P > -o. 1f E relint (Co) then
Opt(Do) + 0. Moreover, if Ma is convex then P = Dū-
Theorem B.I underlies our functional strong duality result (Proposition B. It can be seen as consequence of the fact that Ma provides geometric embedding of (Po namely,
P
inf (f,0".0")es J.MM.
f-
(25)
Similarly, the convex closure of Mo. denoted conv (Mo), provides a geometric embedding of the dual problem Do when (P)) is feasible ([15) Proposition 4.3.2)). Explicitly,
D
inf (f.0' _0 (ECoNv,,o))
f.
(26)
Equations 255 and (26) suggest that the convexity and closure of Mo is closely related to strong duality. In fact, convexity and closure are together sufficient for strong duality [5 Proposition 4.3.2). However, the requirement for closure can also be dropped when the target value of the constraints (o*+>) is in the relative interior of the constraint set Co. as seen in Theorem B. Theorem B. also provides sufficient conditions (i.e. the non-extremality of the constraint levels) for the existence of Lagrange multipliers. This is non-trivial, since strong duality not sufficient for the existence of Lagrange multipliers- [15] Example 5.3.3] provides an example where Mo is both convex and closed but Opt(Do) = 0.
If the dimension of C, is I + J, then the set of Lagrange multipliers is bounded, and the converse is also true [15] Proposition 4.4.2). The linear independence of the constraint functions sufficient for the dimension of Co to be + J (as we implicitly assume in Assumption [ For problems with only inequalities is sufficient for (x()) to be non-empty for Co to be of dimension / + In the next section will analyse another perturbation of P one where relax all the constraints by
29

---

B.1.5 Constraint perturbations
In this section we investigate the following relaxation of Po
P = inf {(x)
-xx
subject to
gx(x) e,
for i 1, ..... 1 c c h))(( S c, for j = I. J.
(P.)
Note that P. has 1 + 23 inequality constraints. Its dual problem is as follows,
D² sup min Le(x, A, (+.. P- -- 20
(D.)
where Le is the Lagrangian function of (P While know that PT 2 P the relationship is difficult to characterize further without additional assumptions. However, the relationship between the dual problems follows from the relationship between the Lagrangians.
Lemma B.4. Assume Opr(Do), Opt(D.) + W. If % (A6:15) E Opr(Do) and n
Me H E Opt(Dz), ) then holds that,
1l - D - D s <lhōll1
(27)
Moreover, 27 implies that Dj 2 D and lh 2 lh:
Proof. Upper bound Let x E RC and a R. be arbitrarily chosen. Let μ4 and p- be defined pointwise as j+,jj = max (4, and μー = max {0, --,}- Clearly μl = 44+ μ and || + ||ا||| = || Applying these facts,
verify that Lo can be rewritten as follows,
J Σ j=1
Lo(x, A, (1) = ((x) Σ X((((1) -c) Σ Euns(hy(0)) - 6)
p p (- (1)) - +)
+e(1|A112 + 1114112)
It is clear that the first term is (e,, p4+ )1_), therefore,
Lo(æ, A, μ) Le (z, X, p4, /-) + e(IIA]I + 1I
(28)
Taking the infimum with respect to both sides obtain,
2o(A, 11) = de (), ((+ + < <(IAl], + (|
(29)
Let 16+ and #ó_ be defined pointwise as Mú+.j max (0.1 } and vā- max {0, (0,,)b
Then, we have,
Do D 20 (No m6) Me H(,_)
S 40 (oo (5) (Nar Mō, Mô.-),
since (Ng, Mū.+, (ū.-) is not necessarily optimal with respect D... Applying 29 the above inequality, we obtain,
D D. = + (I < Ihlll.
which proves the upper bound.
Lower bound. Now let us prove the lower bound. Let À E TR and p4, E Ry. be arbitrarily chosen. Then we can rewrite L. as follows,
J - -) 3=1
Le(x, X, A. ((x) + Σ X1(o(()) - +) Σ (x) Σ 2 (- -) 1=1 - p_) -1 -c(1Aall + || 11)).
1=11
Lo,
(30)
30

---

Again, taking the infimum with respect to 2 gives
(e(A, 14 14: 20(,,, p4+ - (--) - - + 111+++11 + 1-111-1111 111)
(31)
Next, we have,
D - Do - qe Me - 2o(A) (GA011)) 16)
S qe (X Me.tt - 2o(22 M - _
since (E,t - - - is suboptimal for 9o. Applying (31 to the last inequality, we obtain,
D. - DĀ - + |++++ + ||,,--11).
(32)
Since || (11 + ||,,,++11,11-10 ||t--1| multiplying (32) by -1 completes the proof.
B.2 Functional strong duality
B.2.1 Convexity of MM
In this section we are concerned with the range of the functional problem.
P inf ΦE
Ep [[(((()),))) y)]
subject to
Er, (xx)) s 0,
for = 1,..., I
(P
Ec, (o(x), v) 0, for = 1, 1.....J.
The Lagrangian associated with P is the same as for (P) (see and D was defined in Section
3 Of particular interest in this section is the cost constraint function,
Fo( = Ep [x() (((xx))))))) y)1 Ee, [9 (x(x), y)] .................. Ee, [9 (x). y)],
Eq, [0(x)))) v)] ,..., Ea, [)(((()),,)))))))))))))))(())))) v)]]"
We will also need the constraint epigraph and the cost-constraint epigraphs of P namely,
Co = (u.))R' X
36 E s.t. Ep, (o.())x),, y)1 S ui
+
for i 1,...,I. I, for = l.....J] J.
and Bo, (()x) = vy
36 E O
s.t. Es [(()(x), v)]= = =
and Ma = ('..,))
for 1....... I, and Eo, (6,()(x), vil oj for 1, I...., J.
Ex, (o(x), y)] S us
Remark B.3 (Well definedness Pa). The expectations must exist for all E + for P to be well defined, i.e. require & dom Fs. This is true, for example, when l. Is, S.g,, are bounded functions. We derive another condition later in Lemma but for now we assume &b C dom F& for our Lenmas.
As noted Section (.1.33 the convexity of Ma is sufficient for strong duality when 0 is in the interior of the augmented constraint set. We will prove that M, is convex under certain conditions when tb a decomposable set. Let us now define decomposability.
Definition B.3. function class {Ø: X
R} is said to be decomposable with respect measurable space (X, Ex) iff for every Φ1. d2 + and 7 Ex, there exists d3 E T such that,
&1 (x)
E Z
(x(x)
(2(x)
x E Ze.
We use Lyapunov's 's convexity theorem as a tool for the proof.
Theorem B.2. (154) Chapter IX Corollary Let (X, Ex) be a measurable space, and let (V, II-1) be a finite dimensional Banach space. G Σx + V. is a countably additive vector measure, then the range of G is a compact and convex subset of
The range of G is the set (G(A) A Σx}. We will now prove that Mg is convex.
31

---

Lemma B.S. Let de S dom Fø. If the distributions P, Q are atomless and & is decompos- able set of functions, then it follows that Ms convex.
Proof. Consider the following set function formed by integrating {((((x), v), ge (x(((x);;)) y). (x(())))))) with respect to ID, PP, Q2 respectively, over sets of the form A x, where A E Ex (Eix is the marginal sigma algebra over 2
UnI {((()).)) dD, J..ls gi (6(x), dPP d........
JAIs he hr(((x)))) dQe
AA Ex, G(A;
Lemma B.2 implies that each entry of G(A; is an atomless scalar measure, since D, P,, Q2 are atomless. Suppose that Φ1, 02 E Φ. Define another set function, p(A) Ex - (R2(1+++))) given by
[G(A; 01)
AA Ex, P(A)
G(A:)2)
As before, each of the entries of (AA) are atomless scalar measures, therefore Lemma B.3 implies that p(A) is an atomless vector measure. Therefore Lyapunov's 's convexity theorem (Theorem B.2) implies that the range of p, denoted p p(Ex), is convex. Therefore for any E [0, 1]. there exists a set Tx C X such that,
P(TA) Ap (1 x)p(X) (1 ())
(33)
where applied the fact that p(O) 0. Since for any finite measure it holds that p(A) p(X) p(A"), therefore it follows that,
P(T)) = p(x) P(T)) = (1 (1 -1- ()) =
-1-
(34)
We will use these relations to prove that the range of Fg. denoted (D)) is also convex. We do so by constructing an imput Φ3 such that (o)))) is convex combination of (e(1)) and Fo(02). The required function d3 is defined as follows.
[x)
x Tx:
Vx E X, dx(x)
(x)(x)
x Tx.
By the definition of decomposabilityy 63 is also an element of 4. Next we note that,
G(X; 0s) G(TA:0s) + G(T3: os).
since Tx, T form mutually exclusive cover of X. Therefore,
da) G(Tx; Φ1) G(T);
by applying the definition of Φ3. Equations
33 and 34 applied to the above relation implies that,
G(X: XG(X: o1) (1 A);(X;
(35)
But clearly, Fo(Ø) G(X;;) (b) for any d. Therefore,
Fo(ds) (Fs( + (02)
This proves that the range ( is convex, because é1, d2 picked arbitrarily.
Recall that Ma Fs + x Clearly [R++ 0 is convex set, and since the Minkowski sum of two convex sets is convex (55) Theorem 3.1), therefore Ms is also convex, which concludes the proof.
B.2.2 Strong duality
(
In this section we will utilise Theorem B. and Lemma B.5 along with the assumptions we made in Section 3 to prove that (P&) is strongly dual.
32

---

Proposition B.1. Let (a) & S dom Fe. (b) & be decomposable and (c) P -00. Under
Assumptions and I. P is strongly dual and Opt(Do) ) non-empry.
Proof. The premise of the proposition, along with atomlessness from Assumption 2 allows invoke Lemma B.5 to conclude that Ma a convex set.
From Assumption we know that for some ç > 0, B(O .)) S int (C) and C C.. therefore B(O <) S int (C) S int (Co). In particular, int (C&), therefore, we can invoke Theorem B.1 to conclude that Opt(D,) + 0 and P3 D
B.3 Duality gap
In this section we will bound the duality gap of (P). For this, we define the following relaxation,
Pe inf AE
ED (((f((x))
subject to
Ep, (F((())) S Lu, Lv $ Egg [hy (fo v)1 - Lv, for 1...... J.
for i = ,,...,I, I
(Pov)
Note that the set O (defined in Section nothing but the feasibility of (Pau). i.c. Feas(Pau).
Define the Lagrangian Leu(fe,7) of Po similarly . where the dual variable Y IR /2/22/ now corresponds to I + 2J inequality constraints. Let its dual value be Daw, defined similarly to D
(Section 3)
We define its functional version,
Pd inf dc
Ep (e(((x)))))
subject to
Ep, ( v)) I T.V, Lu Ba, (15(0(x),))) v)] < Lv, for j I,...,J.
for i = ,,...,1 1
(Pow)
Let its Lagrangian and dual value be denoted as (ov 7) and D respectively, where T+2J We will bound the duality gap of (P) based on (5) which uses the functional strong duality relation P Di and which further decompose as,
p D
P P + D D
(P" P + (P - P)) + (D' -D + (D%, (D D*).
-Da)
Note that this decomposition contains the duality gap of (Paw) i.c. we can alternatively decompose p - D* as,
- D* (P* P + (Pž - - + (Dă, - D*).
First, we will prove few helper lemmas (Sections B.3. B.3.2 B.3.3). Then we will bound the duality gap (Paw) Section B.3.4 and we will bound the remaining terms, i.e., p* - -Pr and D2 D* in Section B.3.5 and summarise everything with bound on the duality gap p D* (Proposition B.2).
B.3.1 Lipschitz continuity of F&
First, we will prove that the mapping Fo LP(KK + R++++ is a Lipschitz continuous mapping.
Lemma B.6. Let the loss functions f, gi, h, be L-Lipschitz continuous. Then the components of the range function F& LP :F+) ) - - e.g. & + ED [f(Ø(x), v)], are L-Lipschitz continuous and Fo is (VI + + J L-ipsschtt continuous, for p E o0).
33

---

Proof. We will prove that Φ + En [()(()), y)] is Lipschitz continuous the proof is the same for the then,
other components. Let 01 92 E [ [
EED (e() w)] - ED [x()2(x), w)]l s Ep [[((()((); ((62(x),
Ep [ 11 (x) - 02(x))111
D [1) +2(x))1])
(36)
The first inequality is an application of Jensen's inequality (1-1 is convex) and the second inequality
applies the Lipschitz condition on l( ). Equation (36) proves the continuity of Φ + lEp [((Ø(x), v) with respect to the norm LP(R* K D), but we need to prove it for the norm on L L ;P+)
Linearity of the integral with respect to the integral (Lemma B.I implies that,
Ep_ (x) x2(x) = Ep (x) - (x(x)] + EEL o [x) (x)))
Clearly EyL, B.+ Q2 |l|oi (x) (xx since both measure and integrand non- negative. This implies that,
Ep (x) - Φ2 (x 1g I Ex, (x) - x2(x)11))
(37)
Equation 36 and 37 together imply that,
EEp [(( (x), w)]
Ep [x(02(x), w)]l z L'Ep, (x) - x2(x)]1]) L' |1 22 (2
which proves the first part (after taking the thh root on both sides). The second part is proved as follows.
I+1+J
Fa(()) F =
Σ (Fo, - (022()))
1=1
+ JYL2 |1 db2 (R
(38)
Here used the L-Lipschitz continuity of the components of Fx( that was proved in the first part. Taking the square both sides proves that Fg is (v1+1 J>L--iipschhtz continuous with respect the domain IP" (TR ( IP)).
B.3.2 Well definedness of P
Continuity of the loss functions almost solves the problem of well-definedness of P
Lemma B.7. Let the loss functions l, gis h be L-Lipschitz continuous and & S LP (P P+). If Φ dom F + U, then &b C dom F
Proof. Let do $ dom Fg and Φ E t. By the triangle inequality,
[F < (o) Fo(do)ll + +IFo(00))l2
Since F IP(RK P.) K is (v1+T++ J. + continuuus (Lemma B.6 therefore,
(0) S (VI+1++ J) 11:0 @ [[F((6o))22
Since do dom Fs, therefore ((p())) ll, co. Since Φi do E 1 therefore the first is also bounded. Therefore ( 2l, < oo and + C dom Pg.
B.3.3 Lipschitz continuity parametrization
We will now show that pointwise Lipschitz continuity of the map fo(x) at each x implies the Lipschitz continuity of the map 0 + fo (RK:P.)
34

---

Lemma B.8. Let fx(x) be La-Lipschitz continuous for every X E 0 fo E 1P(R=;P, is also L8-Lipschitz continuous (for p E [1, 00)).
Then, the map fo 3
Proof.
Consider 01, 02 O. Then,
Ilfo. fog [2 / [so, [see (x) - dIP_
- / Li 110 02112 dP+
(39)
llfo, foz (R (F - 1. ||0
0g 112
Equation (39) is the application of the pointwise Lipschitz continuity. Taking the p root on both sides of the last inequality completes the proof.
B.3.4 Duality gap of
Lemma B.4
provides an upper bound for D D Next we show that D 2 ou and thereafter
bound p
P
Lemma B.9. If C 4 then Dēu 2 Dow
Proof. Let E 4+2 denote the dual variable for (Pow or 2v Therefore.
Clearly Lev (fo. Lou
inf Lou (S. = inf Lav (ao, 7) 2 inf focM
(d, 7)
BE
de
The supremum preserves the inequality, therefore,
D&u sup inf (fo(fo,7) vER(12/ BEB
sup inf (ov D'v gea 125 de
which was to be proved.
Lemma B.10. Under Assumption
2 Feas(Pov) is non-empty and Pé, P < Lv.
Proof. Let o* e Opt(P&) * 0 be the solution defined by Assumption 2. Since o is feasible for P therefore it follows that,
Ee, [9,(0* (x(("*(x),vl v)] < O and Eo, [hi(0* (x). v)] = 0.
By Assumption 2 there exists fo E such that IIfe x0 11 p4) S Since the range function
(o) is component-we L-Lipschitz continuous (Lemma B.6), therefore we can upper bound the inequality constraint functions follows,
Ep. [9x(f(()), v)] Ep, [9:(0"(x) (x), v)] + L II.o o" (( 50+ Lv.
(40)
Similarly the equality constraint functions can be bounded symmetrically as,
Eg, (fo Eo, [h, (x)),, w)] $ L Ilfe
x" (
Ea, [fo w))l < Lv.
(41)
Equations 440 and 41 imply that 0 is feasible for (aa.). Therefore, Feas(Pav) # 0 and.
P < Ep (x).
(42)
35

---

Using Lemma B. with == O, we can prove that Pi - Pbt < Tv only if P this may not be the case, if of S inf Ep, (0x( (x)x)))) + Lv, i.e. is in the neighbourhood of the But the L-Lipschizzness of the objective (Assumption 3 Lemma B.6 implies that,
Ep [e(fo(x), v)1 Eo (x)=)(x,,)) v) L fife x -0 (z(
P + Lv.
(43)
Therefore (42 and 43
implies,
p S P + Lt,
which to be proved.
We will now summarize our arguments and bound the duality gap of Pew in the next lemma.
Lemma B.11. Under Assumptions
2 and 3 Ps > -o,, Opt(Da) is non-empty and for any
% E Opt(Do), Pe Dev $ (1+ + 2 Lv.
Proof. We can decompose the duality gap as follows,
Pe Dīu = (Ptu
Pa) + (P* D + (D' -
+ +Di -Dx))
D.v)).
From Lemma B.10 (which requires Assumption 2 Pō P Lv.
Next, if 0 E int (C) (Assumption T then 0 E int (Co) since C Cs. Then, by the construction of Cg. Feas(P&) * 0. Clearly Feas(P&) S dom Fg. therefore & n dom Fs * 0. Since we also have Assumption 3 (Lipschitz losses), we can apply Lemma B.7 to conclude & C dom F The premise stipulates that P7 -00. Assumption gives us atomlessness of the measures and decomposability of Φ, which provides the remaining requirements invoke Proposition B. giving us that P D and Opt(D,) + 0.
Since (p)(D&) ) # 9, we can apply Lemma B.4 to conclude that D - DD S Lv 2 for some
7 E Op)(D&). Lemma B.9 which only requires that H C Φ proves that D - Dio S 0. Putting
these bounds together gives us the required bound on the duality gap of (Par)-
Remark B.4. This result is the same upper bound on the parametrized duality gap presented in (23) This proof technique, specifically Lemma B. 10 however, does not work with equality constrained problems such as PP. This is because replacing 6² with 0 leads to perturbation that localises the constraint function values upto an interval of size 2Lv. Therefore, no fanctional problem (or solution) generates 0 that satisfies equality constraint, e.g. Bo, (J(x)) O, since the constraint function value has to be exactly O.
The limitation of this proof technique also applies to inequality constrained problems. Consider the following family of problems,
p = inf
En [((fo(x),))
(P,)
subject to
Ez, (x). S c, for i I....,I
231 used tighter functional problem to upper bound P7, namely,
Psr inf dew
ED [[(((x). v)]
(Por)
subject to
Ee, [gx()(x), v)1 S c, Lv, for I.....I.
bare is feasible. However,
deo
minimal achievable value. In this case the analysis in the next section still applies.
36

---

B.3.5 Duality gap of (P)
In this section we will bound the duality gap of (P). Since D 2 Dev (see Lemma B.4 therefore,
p - D = (P* + (Po - Dov) + (D D*) & (P* Pou) - (Pov Dēu). (44)
Pio Diu is upper bounded by Lemma B.11 We now upper bound p P'te
Lemma B.12. Let Feas(P) * 0. Under Assumption
it follows that P P LLoR(v).
Proof. Let be chosen arbitrarily and let 8 be feasible solution for (Pov) that is c-optimal, i.e.,
Pe. S ED [e(Je v) S Pau +
(45)
Such solution always exists if Pew is feasible, since the optimal value is the infimum of the objective Es ((ffo(x), v) over the feasible set. Note that since (P) assumed feasible, so is Paa
110 0|l ô, i.e. Oo is 8-close to the projection of fr onto the feasible set of (P) (which may not be closed). Note that O nothing but Feas(Poz)) Therefore, by the definition R(v).
Next for arbitrary 8 > let On Feas(P) be such that 10) Ool inf
@eFeas(P)
|10; 0oll R(v) 8
(46)
Next apply the L-Lipschitzness of the map ø Ep [x(fo(x) vi) (Lemma B.6.. and the Le- Lipschitzness of the map + fo (Lemma B.8) to conclude that,
ED [e( (x). v) Ep [e(for v)] s L llfe, foz feollec(RK._) S LLg 110. - 000--111- (47)
Since On is feasible with respect to (P). therefore IED [e(So, (x), P This and 445 implies that,
p P--P P Ep [C(Seo (x), w)) Ep [e(Se (x), +
Thereafter apply 466 and
conclude that,
p Pt < L())(v) LL +c.
Since the bound holds for every > O and 8 >> O, therefore it also holds for = and ó = 0 (simply take the infimum both sides). This completes the proof.
We will now state the bound on the duality gap for (P).
Proposition B.2. Let Assumptions 7
2 and hold and let Pz -o. Then Opr(Do) + 0 and for
any 7 E Opr(D&), P D* $ (1 + n Lv + LLgR(v).
Proof. We can invoke Lemma B.11 with the premise obtain that Opt(D,) and P/ D2 S +1+| ||=8]],, Lv for any % Opt(Ds). Note that Assumption implies that (P) feasible due the construction of C, and this, along with Assumption 3 allows us to invoke Lemma B.12 which states that p Pa < LLgR(v) Applying these bounds 44 completes the proof.
B.4 Dual estimation error
In this section we will upper bound the absolute difference between the optimal values of the dual problem (D) and the empirical dual problem (D). i.e. DD* D*1, beginning with technical lemma that helps take the conjunction of probabilistic statements.
Lemma B.13. Let (X, Σx, P) be measure space and let {ai...., ax} be random statements. as holds with probability at least 6, for k: 1,..., K, then N ags that is the conjuction of on holds with probability at least K6.
K
37

---

Proof. Let aa denote the negation of dg. Then.
K
K
PP V ak) =1
V
aak)
Σ ((--)))
(48)
k=1
The last inequality is the union bound (156) Applying this to (48) gives us the bound.
Lemma 2.2). Since P(aa)) 2 1 - therefore P(-ax) S 8.
K P
2 1 16,
which completes the proof.
Proposition B.3, Let Nmin = min {Mo. Mi..., then OD)( Opt(D) + 0 and, for all E 1),
If Assumptions 1 and 4 hold,
D D' s (1 max (1 115 (NC(Nii 8),
holds with probability at least 1 (1 + T + J) for any y E Opt(D), E Opt(D).
Proof. Assumption states that ()) S int C int ć and therefore 0 E int C and 0 E int Ć. Therefore Theorem B. implies that Opt(D) f 0 and Opt(D) + 0.
The empirical dual function (4), inf i(fo, X, 1) was defined with D similarly define the AEB
dual function of as q(, μ4) inf L(fa, A, p). Let = (A*, 1²) and 7" (X*, f(*) be members #ee
of Opt(D) and Opt(D) respectively. Therefore,
D' D* D--D=g(('+ g(>" 14) '{*20, (*))
S9(2", "(x* ,²),
(49)
where the inequality follows from the suboptimality of (X* ,²) with respect to D i.c. because g(X", s ((*x,pp)) D*. Let > 0 be arbitrary and let 0 be e-optimal with respect g(A", =²),
i.e
i(x", 1²) S i ,,) S a(A* ,4", + Clearly, ((A",²²) I L(fe. X*, p²) since q(²", n²)) inf L(fe, X3, ,²). This fact and 50 applied
(50)
to 149 implies that,
+ D D < g(* ,1*) 1(> ,1*² & L(Jo, x n₂)) - L( x² ,², +
(51)
Now let us expand the difference of Lagrangians in the RHS of (5I).
Mg
L(So, X p²) i(So, (.,,))"'') Ex [B(((fo(x))
Σ
e(fo(Xmo): mmo))
Mo
Mi
X
Ep. Er. (r.():(fo(x)),))
Σ
gs (fo(xmi)) vmaa)
M, m;=1
1=1
+
Σ 14 Ec, (fo((((())
Σ by (f (.foxxn)).Bm)) Bmn)
(52)
N₂
Now, since Assumption holds, therefore the following holds,
Mo
Ep [[((fox)),,)] - Mo
Σ
(xfo(xmo) Umo)
< (
(53)
mm=1
38

---

for every 8 E θ with probability at least 1 5, in particular the chosen. We apply the uniform convergence bound on the remaining samples corresponding to c. Q3 to obtain inquualities analogous to 53 All of the bounds hold simultaneously with probability 1 (1 + + J)ō (see Lemma B.13)
Applying all the bounds 1222
we obtain,
( L(fo, X3, , &
( (M. 8) + Σ (tC + Σ (N
2m1
2
Since (N)(N) decreasing with respect to N, therefore,
L(fe, X", n²) L(fo, X3, - (1 + | + I| II 11 [C (N 6).
(54)
Chaining (5D and (54) and noticing that ||>"
||^l|1 + || we obtain that D - - <
(1+ + I1 1 c /Mmin 5) + e. Notice that we can eliminate since none of the other terms depend
on e, and so we can take the infimum on both sides. Therefore,
- D' S (1 117"11)))
(55)
and this holds with probability greater than 1 (1 + 1 J)ö, since it is consequence of (53) and its analogues for P., Q2-
We can make a symmetric argument, switching the roles of 7 and f+, to prove that
n* - D* < (1 + (l 8).
(56)
This time we pick some 0 that is e-ppiiall with respect to q(*,, fa*) (instead of q(**; (²)).. Since
(53) holds for any (with probability greater than 1 - (1 + + J) therefore Equations (55) and
(56) hold simultaneously with probability greater than the same bound, 1 1 (1 / + J)ö. Therefore,
they together imply that D D*1 s (1 max {1>>ll 11 (issC(NNnii 5), which completes
the proof.
B.5 Proof of Theorem 3.1
Theorem 3.1. Let Nmin = min (oo, Mi..., Mr, .i,..., ,NN} and assume that R(v) < oo and
P > -c. Under Assumptions I there exist v% E Opt(De), E Opt(D), and 6i* E Opr(D). Moreover, for any 8 E (0, 1), it holds with probability at least - (1 +1+I++ J)ō, that
PP* - 1P*- (1+ Ináll.) Lu + LLoR(v) + (1 + max (lh* 11 I1),) S"C (Niin 6). (8)
Proof. Note that the requirements for Proposition B.2 and B.3 triangle inequality implies that,
included in the premise. The
P' D D' + D D*I
Proposition B.2 asserts that Opt(D.) + 0, and provides an upper bound for |P* - DI1= p. D* which always holds. Proposition B.3 asserts that Opt(D) * 0, Opt(D) * 0, and provides upper bound for - D*1 that holds with probability greater than (1 + I + J)6.
Adding both bounds gives us the necessary bound on P D*1 which holds in probability greater than (1 + I + J)8.
next discuss technical distinctions between Theorem 3. and 2x Theorem 1] (which pertains to problems where J = 0) that were omitted in the main text (see also Remark 3.1
Remark B.5. Firstly, we lift the assumption that θ is compact. Secondly, we prove the case for regression problems (Y) continuous) without additional assumptions (see (23) Assumption 6]). This is due to a (small) modification of the argument for Lemma B.5 which yields both results together. Note that (57] also provided a unified proof for functional strong duality, however, their proof takes slightly different approach using the weak Lyapunov theorem 154] Chapter IX Theorem 10).
39

---

Finally, note that while both bounds feature the norm of the Lagrange multiplier of functional problem, the Lagrange multiplier in [23) depends on V, while ours does not. This is because we have chosen to treal equalities and inequalities symmetrically (see Remark B.4 for justification). Therefore, both llnallı and R(v) depend on both inequalities and equalities. However, the proof can be repeated with a slightly different definition of R(v) to obtain two separate "sensitivity" terms for inequalities and equalities, with the former term depending Lagrange multiplier like 123], and the latter term depending on the modified R(v).
In the next remark expand upon the sensitivity interpretation of ||>" when P is non-convex and not strongly dual, as is generally the case in our setting.
Remark B.6. If (P) strongly dual, then the perturbation function (* d) corvex (see 158 Section 5.).1 In Jact, its epigraph is nothing but the set we called the "cost-constraint epigraph", corresponding to (P) i.e.
30 E θ
s.t. Es ((((ff()),))))))))))))(())) 8)1 =,
= (F,,))
Er, (Jo()())), S ui, for 1, v)] and Eg,, (Lx()))),,)) u for _,...,,"
the perturbation function were additionally differentiable, then (9) holds. More generally, without differentiability,
-("',²" is subgradient of P* (c, d) at (0', 0*) (see A75 Example 5.4.21), i.e,
d' P* - 0²) /= T (d 0²).
(57)
We now derive approximate version of 57 from Proposition B.2 ass follows
d) - P (T d) - p*
(58)
2 D) - D D (11 |1 Lu + LLa
(59)
Here we have used the weak duality relation for (c d) in (58) and Proposition (B.2) in (59) can bound the gap D (c, D in an identical manner as Lemma (B.4) to obtain.
We
D' d) D (c- 0²) -ppppp (0
(60)
Combining
559 and
600
we obtain an approximate subgradient relation similar to
57 Explicitly,
P'(c, P* - G(v),
(61)
+ is the remainder term that disappears as v + Equation 67 thus enables to interpret X* constraint sensitivity even in the non-convex case, albeit approximately.
where
- G(v)=-(a1
40

---

C Proof of Theorem 4.1
In this section will provide guarantees for Algorithm the quantities related the empirical dual problem, i.e. L(fo 1,, ((2, and D (defined in Section 2) Also define the empirical constraint vector,
| which approximately solves (D) Recall
M₁
M₁
C(0)
Σ
91 (fo(Xmm)) ).
Σ m==1
gr ( 9ms)):
Mi
Mr
m==1
N1 Σ hn (x
NJ Σ he (fo(xn)))
Note that O' has I I+J J entries. Let denote the tuple (X, 11) in the sequel, and similarly for yM, ( etc. We will denote ((,, μu) as ((7) and L(fe. A, μi) [(fa: for brevity.
We can prove that the set of supergradients for ((7) ? equal to the convex hull conv (((10) 10 O, i(So, 7) ((>))) (e.g. with [59 Theorem 2.87)). We will now show that approximate minimizers produce approximate supergradients.
Lemma C.1. Let g(0) satisfy 0() I i(fo, )0)) s (()(1)) + p. Then, it follows that, for all y' E R4 R
1+J
1(7 2 ((7)) + Σ hk Cz(())
Proof. From the premise of the lemma we have that,
)(> 2 i.Soco. 70)) By the definition of the dual function, we have for any 7 E <Te4, x R.
(62)
((>') < L(focs,)))
(63)
since ((>')= = inf L(fo, 7¹). Then,
((>(1)) - ((>') 2 L(grs (0) L(Soco (00/:oo.7))
If we expand ff (2)) and L(for) " then the terms in the Lagrangians correspond to the ob- jective cancel out. We are left with the product of the constraint functions (Ć, (0t))....,C_,((()))
and the difference dual variables 70,),' i.c Elt( (t) - 7/2 (O((t) Bringing g(n') to the RHS completes the proof.
n
Subgradient ascent algorithms that use any subderivative are not guaranteed descend monotonically in the objective, in this case the dual function q. This is also true of approximate subgradient descent. Using Lemma C.I we can prove recurrence which helps prove descent with respect to the mean squared error in the dual variable, which we define
11>00 30 1|
U inf EOp()(
(64)
where Opt(D) is the set of optimal dual variables for D We will also need technical lemma first. Lemma C.2. Define H++ I RT such that [x]+ max (x, 0). where the maximum is taken componentwise. Let x, TRd, then it follows that,
[|x]]
[y]+ < |x yll2.
Proof. Since [[[x]+ [1]+12 En (max (5;; 0) max max 0))2 therefore we only need to prove, mmax(2;, 0) - max(y), 0)1 - [x; vel.
(65)
If Ir; 0, 0, both sides equal. If s; 0. yi 0. the LHS evaluates to 0 so 65 holds true
again. If o; < 0, y: > O, the LHS is equal to lys| and the RHS is equal to | + lysl (trivial) so 66
holds true again. The last case follows by symmetry. This proves (65). which proves the lemma.
41

---

Lemma C.3. Let 8 ,70) (2(0) ())) ) be the thh iterate of Algorithm If Assumptions and hhold, and the loss functions f, gi h2 are B-bounded, it follows that,
U, U.SU + 2n ((0(1111) D + +P] + (1 + J)B²
Proof. Let ()) = [,,()....,C,()) and C2(0)
denote the
concatenated empirical constraint funetions for the inequalities and equalities respectively. Clearly the constraint vector C(0) the concatenation of both. Since Assumption holds and the loss functions are bounded, therefore Opt(D&) (Theorem B.I.
Decompose (1) (A(*), ())) then it holds that,
8- | - x- 10111 | 12-112
(66)
Using the update rules for the dual variables, we obtain,
|/(0) 9r 1
2 = | n)(((((- 2- + (1(t-11 + ) -p""
666
(67)
where [x]+ applies max (+,0) to each component of x. We can write X = {+
since X is
non-negative by definition. By Lemma C.2 we know that,
{x] + s $1>000 + (00((11-))) -i-112
(68)
Applying (68) to 67/. we obtain,
1| 9"
|| < \ (0-1) (((((((-1))- - + | + ,)(((((-11) -
-1( ((((tt-1)) - -
(69)
where in the last step we have recombined inequalities and equalities. since the rest of the proof is not affected by the difference. Expanding the squared norm the RHS of 69 we obtain,
1/:0 111 (----))) -
--(-=))~+(13 1=11, + (1(7 (/) ((g(tt-i) + n ((
(70)
Since Assumption 5 holds, therefore we can apply Lemma C.I which implies that (7 " s (()((t-1) "( ) + p (t-1) D* + p.
(71)
And from the boundedness of the loss functions we have that,
||c(ol-1)) || s (I+
(72)
Applying (1 and
(22)
70 obtain.
1,000
7 (t- 1) (--1))
+112== --
(t +)
Applying the operation
inf to both sides preserves the inequality. Notice that only the LHS 4- EOp((t)
and the first term in the RHS depends on 4*h Taking the other terms out of the infimum and applying the definition of Up gives us the required bound.
Although we cannot directly show that the objective ((), monotonically increases, we can show that by picking the learning rate appropriately, the initial phase of the algorithm monotonically reduces the mean squared error (U,) of the dual iterates, upto the point where (()( is some ap close to D* for some a > 1.
42

---

Lemma C.4. Let 800, ,00) (20),, )) be the tth iterate of Algorithm tions !
1
Let Assump- Define To
and [ hold, and let the loss functions E. h2 be B B-bounded.
min t t N D - (()(1) ap} 0 for some 1 and let rj S (1+J)B2 Then it holds for
all S To that
Ut < U1-1-
Moreover, To S Taaz
Un 2mp
Proof. Lemma proves the following for arbitrary 1,
U + 2n/ (((())1)) D' + 0) + 1/ J)B²
(73)
Assume To, then the premise states that D' -'-99( 90--((((-11) > ap, i.e. :(> ((-1) D (1-a)p.
Moreover 1) S [TJJ)B > ty(T J)B² I ap. Applying these bounds to 73 gives us,
op
U₂ < - 2(a - 1)mp + 2nap
-U, U,- 2np-
(74)
Equation (74 proves that U2 U--1 since -2mp < 0.
Now, to achieve an upper bound for To, apply (74) recursively obtain,
UT, Uo 2npTo-
(75)
Since Ur, 2 0, therefore
75 implies that,
Uo
Uo -mmTTo > 0 = To
<
2np
Note that the proof requires that > to show descent. Once ((y(t-1)) D' p. 73 cannot prove descent because both terms are non-negative. Note the dependence of T max on v) and p. While interpreting To and T maxx. it is important to note that we cannot detect To since we have neither D nor (since oracle is approximate). However, bound on Tb. Proposition C.4 does not tell us what happens between To and Tiaxx in particular it does not tell us if our iterates become worse, either with respect the mean squared error dual function. While giving a guarantee for the last iterate (at T = Tmax) is challenging, we can give guarantee for the average of the Lagrangian iterates. The following can also be written randomized result, such as in (23]
compute Tmaxx which is simply upper
Theorem 4.1. Suppose Assumptions 7 3a and let the loss functions l, gis h B-bounded. Let Ug = inf ||>000 - - Then, for any E 14, holds that,
E0pp(D)
D
Σ
Σ (i(Jevs,
Un S spt
1 (1 JMB².
(10)
2//
If S (T and T N Uo hp
then the bound is equal to 2p.
Proof. We know, by the definition of the oracle and the order of updates that, any
((700) "(forn,,,)) I (1)) + p.
(76)
Since (() < D*. therefore 76 implies that i(fore, - D S for all t, therefore
((faoo221)) D* S P.
(77)
2=
43

---

which proves one part of the bound, since hand, since (()(*)) - L(fcco, (()). therefore.
2n7
2 JnBB²) is non-negative. On the other
1 T-1
(() D.)
((()1))-i)
(78)
T t=0
T
1=u
We will now derive an upper bound for Σ ((()(0)) D.)) by applying Lemma C.3
recursively
T times to obtain,
UT S Up + 2n
Σ (i(7(0) - + T(2np + n2 J)B²).
(79)
(=0
Now, since Ur 2 0, dividing by 2n/T and rearranging the terms, we get the following inequality,
T (1)())))
1D* 2
Un
1 (7+ 2
2n
Multiply the above equation by -1 and applying (78) we obtain the required upper bound,
T D
Uo 20/7
[(oors S sp
+ (1 JynB²
(80)
T
t=
Now since 1 S (1+J) + Tnnld + B) S p.. and T to,
Ue
Ui 2n
S G. therefore, (80) reduces
i(Jow,, (0) -10)= S 2p,
T
0=
which proves the remainder.
44

---

D Additional theory
D.1 Example: minimum norm interpolation
Let X E x and w,y E R". Consider the following problem, that finds the minimum norm solution to system of linear equalities,
P inf wER"
1
2
(Pe)
subject to
X y.
The problem (Pa) can be transformed a problem with single inequality constraint, by constraining the aggregated violation of the equalities, namely,
P inf
2 ||ll1
(Pr)
subject to || y112 SC..
The feasibility and optimality sets of (Pr coincide with (P.) when 0. However, the dual problems of both problems are different. The dual problem for does not depend on c, and is well posed. However, the dual solution of (P.) diverges e - and the dual problem of (P.) becomes ill-posed, Note that this also implies that recovering a good approximation of the solution to (Pe) using an
unconstrained objective | 2 + A||X - yll would need a very large weight X.
We will now state and prove these facts. We need the following standard identities concerning the derivatives matrix forms (which can be found e.g. in (60] Equations 69 and 81).
Lemma D.1. Let R be a symmetric matrix and x, E IR". Then, the following identities hold true.
1. (a ( Ar) 2Axt
2. Vx (b) (b x)) b.
We make the following simplifying assumptions.
Assumption 6. Assume that XXx is full rank matrix and there exists wo E R" such that Xwo
and we # O.
We will now characterize the dual solution of P
Proposition D.1. Let Assumption hold. Then there always exists a dual solution of say
X 0. Moreover, as e > 0, X + DC.
Proof. Consider the constraint function,
1
g(w)=
Xww -112
2
[Xw - -y1 [Xw y]
2
1
( X Xw 2w T 11012))
2
clear that g(w) is quadratic w. Since its second derivative the gram matrix XXT (Lemma D. which is positive semi-definite [6 Theorem 4.6.6.], therefore ((w) is convex 55 Theorem 4.5]. The existence of wo such that X ww further implies that strictly feasible point (wy) exists. Since the objective also convex, therefore the set of dual solutions is non-empty and strong duality holds [1] Proposition 5.3.
Existence of dual solution and strong duality.
45

---

Existence of primal solution. below by O, therefore -o Pr cc. Therefore the following modification P.) is well defined, for any > 0,
Since Feas(P;) is non-empty, and the objective is bounded from
P2 inf
||l|12
wE
2
subject to
|| y 1 S
(P12)
2
1
2 || S P. +7-
Clearly (e2) C (P),,P;), therefore P. v Pi Note that since P.
inf (PFea((P)) 2 11w1
therefore for any 0, there exists w E Feas(P)) (P:) such that,
[ 2 S P +
(81)
Let ( S IR be the sequence 63 = 3. Using 81 by setting ò = Ej. we can construct sequence {w,} that satisfies,
Wj E Feas(P:) and ||u; 112 - PT + 65.
Clearly {wj} C (Pi)) since ô1 and oj is strictly decreasing. Since 83 + 0, therefore ||uy 12 + Pr. Therefore P2 P.. Now, since g(w) is convex, and clearly continuous, therefore its sub-level set g(w) S e is closed [55 Theorem 7.1]. Clearly, the set (w |||| P is nothing but the norm ball B(O, 2( +6)), and is closed and compact. Therefore Feas(P:2) is compact. Setting = 7 in (81) proves that Feas(Pz2) is non-empty as well. Since the objective, 2 || is continuous, the compact non-emptiness of the feasibility set implies that Opt(P:2) * (see 52 Theorem 4.1.6)).
+5}
Clearly, since Opt(P:2) S Feas(P:) and P = Pr, therefore Opt(P:2) C Opt(P.). Therefore Opt(P.) + 0.
Diverging dual solution. Now that have established that the primal and dual solutions exist for all > O, let X,, " be primal dual solution pair. Since strong duality holds, therefore they must satisfy the KKT conditions (see [58 [Section 5.5.3)).
The Lagrangian function associated with PP. as follows,
L(w", A)
||=" 1 +
2 |Xw" -112
u1/2- -c)
2
X"
w TT "*
TT T Xw= -2w*T X y |1 26
TT [I X+X X] w* TT x y X (Iuel 2c)
2
The KKT condition for the stationarity of the Lagrangian implies that,
V N (w- X+) 0
[+ X :- Xm xTT 4n
[T X w² X y=
- - = X* [ + X x] -1 XT y
cdl x x] xTy
where we have defined A
46

---

Since XT X is symmetric, we can assume the following eigen value decomposition,
x
where V Rnx" is an orthonormal matrix and A E R=x is a diagonal matrix with positive entries (since XXT is positive semi definite and full rank). Now we will rewrite the constraint function evaluated at w*.
X cl + x xx xT / 2
Xw v112
x cl + x -1 x Xwu -Xwo
2
12
x [cT x x x r| wo
X [ONVT + +VAV VAVT 1
Wg
X + V r
w70
x [ AV 1 Wy 2
=wo VieT+ A) AV 1] X X Ver++ +| AVT AV - wo
=wo [Vic + AV - - ] VAVT [vicl+ A] - AV vVT] wo
=w V [C[+ A --1 -1" VTVAVTV [ICI+A] A - 1 VTw T
=wo V [C|+A] A 4-1 1 A - 11
-g.
Bg.
where,
B [cT 1 A A- -1] A [[cT+ AJ -1].
which is diagonal matrix, and V wg. Clearly,
V wo + #
since wp + 0, and V has full rank. Now,
0, (
2
Ba σi
c+
Therefore,
[Xw" -vll 9 Bq Σ Buq; 2
i=1
c+ 0i -1) 0.03.
σi
Now, the feasibility of the primal solution implies,
ai -1)
o. Sc.
iml
47

---

Without loss of generality, assume that 9: * 0. therefore,
Since the LHS is sum of non non-negative terms,
2
0,
-1
1)
oil Sc
c+ 0j
c²
(c+
Se
(1+ 96 Sc.
Clearly, as + O, the LHS must also vanish, which only possible if X - 3o since the remaining terms don't depend on
Next, we will characterize the dual solution of P
Proposition D.2. Lel Assumption hoold. Then, μ (XXT)- is a dual solution of
P
Proof. We will proceed by explicitly computing the dual function q(v) for P Note that the Lagrangian
L(w, p) = 2 |10 + 1² (Xw y)
a convex function of w. Therefore, the first order condition necessary and sufficient to find global minimiser of L(w,0 u)) with respect to w ([58)[Section 3.1.3.J). Proceeding.
W Low p))
| 3 + T (Xw - v)
3 + X =00
U - X
Thus,
4(1) inf wERt
L(w, = L(-x H,
1
1x 11122 + nT (x(-X) 11) v)
2
2 || T ml12 - -||x 1112 p
|| m1l22 TTy.
The first order condition for q(p) must be satisfied by μ², therefore.
Vng(u)) p= =0 0
XXT p 1 y1
11-
XXT 4¹ y ==0
XX 40- - y
-/¹ = -(XXT)-1y
which completes the proof.
48

---

D.2 Comparing equalities with double sided approximation
Consider the following equality constrained problem,
=
inf =Ex
f(x:)
(Po)
subject to hy(x)= =0, for = L....,,,
and its symmetric relaxation.
= inf f(x) subject to - e = S.
(P.)
for J.
We analysed the relationship between a pair of similar problems Appendix [B1.3 and Lemma B.4 The only difference is that we have now dropped the inequality constraints (z(z) S 0 from (Po) for the sake of a clearer exposition.
The difference between [Po] and (P.) is in the constraints P.. has twice the number of constraints as (Po). and they are all inequality constraints, as opposed the equality constraints in (Po)- This implies that both problems have different dual variables. Let E R denote the dual variable for (Po) and let p+ p IR denote the dual variables for (Pa with + corresponding to the upper bound and corresponding to the lower bound.
Consider the Lagrangian for (P
(,, H-) = ((x)= + Σ
(h) -) Σ Enma(-h((0) - e)
j=1
5=1
= ((x) + Σ
- - (111 + lI).
(82)
It is clear from (82) that at O, Le (I,, p4 μ-) Lo(x, بuا - )_ Moreover, Lemma B.4 proves that when 0, Dj
Dr. i.e. the value of the dual problems equal. Taking the infimum with
respect to in Equation 82 we can obtain,
ge (e(,, = c0(u+ F-) e(Ilx+11 + (1)-)1
(83)
Clearly Opt(D.) is not directly equal to Opt(Do). however from (83) it is clear that any solution of (Dz) can be transformed solution of (Do), when e 0. by the following mapping,
p :== M4 μ4-
Similarly, can verify (as in the proof of Lemma B.4 that any solution of (Do) be transformed to solution of (D.) (when = 0) by the following mapping,
M+j == max 0) and p-j = max(- (-x-, 0).
easy to verify that if the constraint functions are B-bounded, and the dual variables for P. are initialised with some large positive value,
M4.j B' > BT,
then the trajectories for the dual variables for both problems under Algorithm [ are virtually the same. More precisely, if is the dual variable for (Po). and He = μ4 μ is the effective dual variable identical. Theoretically, if f44, /r_ are not initialised to a large
of (P.). then their trajectories enough values, the projection by max (-. 0) on line 6 may cause differences in the trajectories. Figure 7 compares the dual trajectories for (P-DP) and its double sided relaxation for small value of although all the dual variables were initialised to O. See also Figure[[b) where we see that "effective" dual variables of the relaxed problem converge to the dual variables of the equality constrained problem as e +
Note that if the "effective" dual trajectories are identical, then 82 implies that the primal trajectories are identical too, meaning that both methods are virtually the same. Finally, observe that when > 83 suggests that relaxing the constraints by is equivalent to regularizing the dual solution.
49

---

E
from the features and set it as the target Experiment details
Our implementation was made with pytorch and other standard MI libraries, and our codebase can be found at https://gi thub. com/ hataar/uawineeuallttyyootttaaaaa experiments were run on an internal computing resources.
All
E.1 Fairness
Dataset. All our experiments on fairness applications were conducted on the COMPAS dataset downloaded from httpp://githtbb coop/propublic/// compas-ppaa-peaaaaaa analysis Our starting point is the compas-scores-taenn
cav file, which was processed by the following pipeline following
22
1. Remove rows where the attribute bayys_bssrreninge arrestt is not in the range 3-].
2. Remove all columns except sex, age, race, www_misd_coune juv_other_count, priors_count, e_charge_degree and wo-_year_reid,
3. Recode the race attribute by clubbing values Asian, Native-American Other to Other.
4. Split the data into train (70%) and test (30%) sets.
5. Encode categorical attribute race with one-hot encoding.
6. Encode the binary attributes sex, c_charge_degree as (single) binary columns.
7. Quantize the numerical attributes griors_count using the following bins, and then use one-hot encoding for the resultant categorical variable.
hw__misd_coune
(a) priors_ count [[0, 0.99), (0.99, 1), (1, (3, (4, 1000)
(b) juv_ juv_misd__omm count [00, (. (0.99, 1), (1, 1000)]
(c) juv_other___e count -(00, 0.99), (0.99, 1), (1, 1000)]
8. Bin the numerical attribute age by quantiles using bins. Use the quantiles the training set to quantize both training and test sets. Encode the resultant categorical variable using one-hot encoding.
9. Remove the binary attribute variable y.
10. Copy the categorical attribute race from the features, and set it as the protected attribute defining 9, in P-DP) and PP-
This process repeated 10 times produce 10 different train-test splits. After preprocessing and filtering, the full dataset (train and test together) consists of 23 features and 6,172 samples.
Sigmoidal relaxation. We replace the indicator functions in (P-DP) and P-F with a sigmoid function in order to make the problem tractable (and aligned with our previous results). Explicitly, we use
Ep [fx()) 0.5] x Gj]
Ee [a (a (fo(x) 0.5)) |x Gj],
and similarly for the overall rate EEp fe (x) > 0.5]], where a denotes the sigmoid function. A similar approach was taken, e.g.,
24
23
Model and hy perparameeerss. The following are the details of the hyperparameters.
The Adam optimizer was used for both primal (step Alg. D and dual updates (step 6-7 of Alg. [ with learning rates of 0.2 (primal) and 0.001 (dual). The other hyperparameters for Adam were set to their default values (e = 10 ,1 0.9, B2 = 0.999).
2. A logistic regression classifier was used as the model. The cross-entropy loss was used as the objective.
50

---

3. The full dataset was used to compute the objective and constraint functions at each step.
4. The temperature parameter in the sigmoidal approximation of the rate constraints (see Section[5), was set to 8.0.
5. Training was terminated when the average of the last 100 Lagrangian iterates, changed by less than 10-5 in window of 100 steps. In case the termination condition was not met, the algorithm ran till 16, 000 epochs.
Computing resources. The fairness experiments were run on CPU-only nodes with 32 threads, with about 10-20 runs in parallel. Each run took at most 20m (when the termination condition was not met).
E.2 Boundary value problems
Let Ω C Rd be bounded connected region with boundary i2, and define the domain of a BVP as D Q (0, 2'] (where 7 IR,) and let H {.e 0 θ be of functions defined on D. A BVP is typically posed as the following problem : We call the three constraints the partial differential equation (PDE), boundary condition (BC) and initial condition (IC) respectively. As discussed in Section the PDE constraint can be transformed to the constraint Ep, [x] t) - T(x, 1))
for some distribution Pp that has support over the entire domain D. The difference between this and the original formulation is essentially that the latter is with respect the I,2 norm, while the former a pointwise constraint, or equivalently over the 7 norm with respect to any distribution whose support contains D. The BC and IC constraints can similarly be transformed into their counterparts in (P-BVP) by picking IP, and P. as distributions over ae X (0, T*) and Ω respectively.
Dataset. In our experiments we solve the convection BVP, with sinusoidal initial condition and periodic boundary conditions:
find
fo H
Of Ot + 3 Ofe =0
subject to
for [0, 2T, (0, 1], for E [0, 1],
Ox
(BVP-C)
(0, fo(2 t)
fe(2, = sin(x)
for æ e 2m]
We express this the following instance of P-BVP
a' 2 1101
minimize IEB
(
O5e
0fe
21
subject to Er,
0,
0t
Ox
(P-C)
Er,
(Jo( fo(2T, (()= t))² 0,
Ep, (fo(zz, 0) sin(x))² 0.
Here Pp, Pp and P; are taken to be uniform distributions over (0, 2Tr] x [0. 1]. [0. 1] and [0, 2m) respectively. We followed training and evaluation setup (including model and hyperparameters) similar to [62]. For the training dataset, 1000 collocation points (z, t) were sampled uniformly, and dynamically at each iteration/epoch, from the domain X' x T [0, 2T] x [0, 1] which were used to compute the PDE, IC and BC constraints. For evaluation, a uniform grid over (æ,, t) with (512, 251) divisions was used as the test set. We used the implementation by [62] generate the ground truth. Evaluation was done with respect to the relative L2 error on the test set, which can be written as,
E= (fo(Dns) bn) - ft kn))² (x,))))))))
Relative I Error
where ft is the ground truth solution and (In, to N is the test set.
51

---

Model and hy hyperparameters. The following are the details of the hyperparameters.
1. All models were trained for 300k iterations or epochs.
2. Both methods (PINN/ (-BVP)) used 4 layered MLP with 50 hidden neuron layers and Tanh activation to represent the primal model fa.
3. Adam was used to optimize the primal model, with an initial learning rate of le-3, and learning rate scheduler was used that multiplies the learning rate by a factor 0.9 every 5000 steps/epochs (available as the class StepI. from pytorch). The other hyperparameters for Adam were left at their default values ((31, 32, <) =0.9, 0.999, le-8)).
4. A batch size of 1000 was used, and each batch was sampled dynamically at each step.
5. For the PINN formulation, the multipliers for the PDE, BC and IC losses were picked to be
(1, 100, 100) respectively.
6. No weight decay was applied to either method. In particular, a was set to 0 in P--).
7. The dual variables optimized using Adam with learning rate le-4. The other hyperpa- rameters were left at their default values.
Computing resources. The BVP experiments were run (one run at time) on an accelerated node with 16 CPU threads and one GPU. Both PINN and (P-C) took approximately 1h40m for each run (300k epochs), with negligible overhead for the constrained method.
E.3 Interpolating classifiers
Dataset. We used the CIFAR-10 10 and CIFAR-100 100 datasets from the torchvision library. We applied dynamic data augmentation, i.e. transformed samples at train time using the following pipeline
1. random cropping of the image after padding with 4 pixels,
2. random horizontal flip,
3. random rotation between -15 15 degrees,
4. channel-wise normalization by the (pixel) mean and standard deviation from the training set.
Model and hyperparameters.
1. The cross entropy loss function was used for lo All runs were for 200 epochs.
2. Both methods (ERM/(P-CI) were trained with ResNet18 model, with standard mod- ification to the first layer using smaller filter sizes to adapt it to smaller images (com- pared ImageNet). The reader is referred
codebase (or the open source repository git) t) for the exact implementation.
https::/gitta /ttbbbb.tttt..../. com haamm/uuagglluu cowm://uangglluuyyyooooooo-i.ff-
3. SGD was used to optimize the primal model for both datasets, with a batch size of 128, and initial learning rate of le-3, and momentum hyperparameter of 0.9. For CIFAR-I0, cosine annealing learning rate scheduler
AnnealinnLL was used with T Tiax = 200. For CIFAR-100, the initial learning rate was decayed by a factor of 0.2 at the 60th, 120th and 160th epoch (i.e. these were the milestones passed to MultiStepL.R.
4. A weight decay value of 5e-4 was used for all runs.
5. Adam used optimize the dual variables, with learning rate of 1e-4 for CIFAR-10. 10. and le-5 for CIFAR-100, All other hyperparameters were held to their default values.
Computing resources. The interpolation experiments with 12 CPU threads and one GPU. On CIFAR-10 10, ERM took about 16m while (P-CI) took about 18m. On CIFAR-100, the overhead was larger, with ERM still taking about 16m while the constrained method took out m1m. This may be mitigated by a vectorised implementation of the Lagrangian, but left for future work.
(one
time) workstation
52

---

Additional plots
F1
Fairness
0.75
Mean trend
0.70
0.65
Accuracy
0.60
0.55
0.50
0.45
0.40
Unc. DP
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
(67.76%)
(66.85%) (55.16%) (57.08%) (64.10%) (66.49%) (66.89%) (63.18%) (54.78%) (44.99%) (44.84%)
Prescribed Rate (Mean Accuracy)
Figure 5: Prescribed rates. We see that at r = 0.5, the mean accuracy of the model is slightly better than the Exact DP solution. the same time, for ry 0.5, the model achieves a group disparity that
is comparable to the Exact DP solution (see Figure b)) but at different rate. Thus (P-F) enables new tradeoffs between group disparity and accuracy, that cannot be found by using (PDPP.
53

---

African
Afncan-Ammrrcat
Cuncasian Hispanic Other
Caucasioa
0.025
Constraint Functions (E)A))AAAx))))
Hiqqanic
Other
Doal Variahles
00.25
-0.050
-0005
-02
0..000
-0.3
-0.125
-0.4
130
250
380
2000 Epochs
550
2.0
Ppochs
(a) Training trajectories for (P-F) at r.
= 0.5
0.0
Africun
0.0
Alfican-Ammriian
Cuocasian
Caucosian
Hispanic
Constraint Functions (EjA, (aaeo))
-01
Hispanic
Other
Other
-02
Doal Variales
-0.4
-0.6
-0.5
-0,0
-07
-1.0
-088
4090
1003
1200
34803
100.00
200
1500
00000
12091 1098) 3930
Epochs
Epochs
(b) Training trajectories for at ry = 0.9
Figure 6: Prescribed rales. We that while training converges quickly for rj 0.5, about 400 epochs, it takes more than 10 times as many epochs for ry 0.9 to converge (and it still does reach the termination condition). This is understandable, since the population prevalence of the binary label, i.c. P(y 1). is about 0.46. As such, prescribing a very high rate, c.g. Ty = 0.9, is hard constraint satisfy while maximising the predictive performance. And in fact, restrictive that the model yields the constant classifier after thresholding.
54

---

0.04
Aftican American
0.15
African-Amenii American
Cancesian
Caucasina
Elispanic
Constaint Functions (Z)by)6el)))
Hispanic
Elfectivee Deal Variables
0.00
0.00
-000
-0.05
-000
-0.0
-0.0
-0.13
100
200
3.0
300
600
100
200
9.0
0.0
500
610)
700
Epochs
Epochs
Training trajectory for double sided approximate DP constraints (see Section at
Amerian-mmercan
6.15
AfricunAmmeriaa
Cincasian
Caucasion
Constiint Functions (ZWo)(ee)))
Hispanic
Hispanic
0.000
Effeciiv Dual Variables
0.035
0.00
-0.055
-0.03
-0,000
-0.10
-00055
0.000
-0.00
50
100
100
200
250
300
30
100
120
200
250
300
300
Ejochs
Egochs
(b) Training trajectory for double sided approximate DP constraints (sce Section
at 10
Arriam-American
African-Ammeriaa
0.073
Cincssian
Cancasion
Hispanic
Constraint Functions (EAA, (Atr)))
Hispanic
0.000
Other
Other
0.05
Doal Variables
0.000
0.00
-0.05
-0.05
0.033
-0.15
0.000
-0.20
50
100
150
200
250
300
350
50
100
150
200
250
300
350
(c) Training trajectory for exact DP constraints.
Figure Exact vs approximate fairness. The trajectories the effective dual variables (i.e. the difference of pairs) and constraint functions of the approximately constrained problem and the exact constrained problem are very similar at = 10 14-4, as compared to at = 0.05. Section D.2 discusses theoretical reasons for why this is the case.
55

---

F2
Boundary value problems
1.2
PINN
1.0
Relative L Error
P-BVP
0.8
0.6
0.4
0.2
25
30
Epoch
x10
Figure 8: Evolution of relative L2 error for Convection BVP (3 30). We see that besides a smaller final error, P-BVP also converges much quicker to smaller error.
35
35
29.48
30
30
27.87
26.43
24.99
25
Doal MMan
21.19
Dual Meun
10
5
IC
(a) 8=30
(b) |3=5
Figure 9: This figure shows the final dual variable per constraint, averaged across 5 runs. The dual values for the boundary condition are the largest for both values of (3, which possibly be explained by the simplicity of the solution to the convection equation with a sinusoidal initial condition which makes the propagation of the information through the boundary condition the challenging part of the problem.
56

---

Run
Run
Run
Run
Run
0.8
PNN
0.75
0.4
0.50
0.2
0.25
0.00
1.0
0.25
0.50
P-BVP
0.6
0.75
0.0
Figure 10: Predicted solutions for 3 = 50. We can visually see the difference between the solutions of PINN and P-BVP). where the former struggles solve the problem for most runs.
57

---

F33
Interpolating classifiers
CIFAR-100
CIFAR-10
0.90
f= 0.94
60
10
20
0.200
0.225
0.250
0.275
0.300
0.325
5.0
0.89
r= 0.92
60
10
40
20
0,200
0.225
0.250
0.275
0.300 0.325
4.5
5.0
5.5
6.0
Test Error (%)
60
40
20
0.200
0.225
0.250
0.275
0.300
0.325
4.5
5,0
5.5
6.0
0.88
r= 0.93
10
20
0.200 0.225
0.250
0.275
0.300
0.325
6.0
0.87
r= 0.87
60
10
40
20
0,200
0.225
0.250
0.275 0.300 0.325
4.5
5.0
5.5
6.0
Dual Value
Dual value vs test error (for all seeds). We see a strong linear relationship between the dual value and the test error of each class across runs, for both CIFAR-10 and CIFAR- 100, with correlation consistently greater than 0.87.
Figure 11:
58

---

0.3
Constraint Value
Dual Value
0.1
0.9
50
100
150
200
0
50
100
150
200
Epoch
Epoch
(a)
(b)
Lagrangian Value
150
Epech
(c)
Figure 12:
Training plots for CIFAR-100 for one random seed. Subfigures (a) and (b) show the constraint and dual values during training, with the mean across classes shown by the solid line, while the maximum and minimum (across classes) is denoted by the extents of the shaded region. Subfigure (c) shows the evolution of the Lagrangian.
airplane
dog
Constraint Value
1.5
bird frog
aulomobile
horse
Dual Value
4
1.0
ship
deer
truck
0.5
150
Epoch
Epoch
(a)
R-
Lagranggen
50
100
125
150
175
200
Eporh
(c)
Figure 13: Training plots for CIFAR-10 for one random seed. Each class denoted by different color in subfigures (a) and (b).
59

---

Appendix references
References
[1] Ingo Steinwart and Andreas Christmann. Support Vector Machines. Springer, 2008. Information Science and Statistics.
[2] Vladimir N. Vapnik. The Nature of Statistical Learning Theory. Springer, 2000.
[3] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning. MIT Press, 2012.
[4] Solon Barocas, Moritz Hardt, and Arvind Narayanan. Fairness and Machine Learning: Limita- fions and Opportunities. MIT Press, 2023.
[5] Sam Corbett- Daveet, Emma Pierson, Avi Feller, Sharad Goel, and Aziz Huq. Algorithmic Decision Making and the Cost of Fairness. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 797-806, 2017.
[6] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards Deep Learning Models Resistant to Adversarial Attacks. In International Conference on Learning Representations, 2018.
[7] Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric P. Xing, Laurent El Ghaoui, and Michael I. Jordan. Theoretically Principled Trade-off between Robustness and Accuracy. International Conference Machine Learning, pages 7472-7482, 2019.
[8] Cynthia Dwork and Aaron Roth. The Algorithmic Foundations of Differential Privacy. Founda- lions and Trends in Theoretical Computer Science, 9(3-4):211 117-444 2014.
[9] Javier Gareía and Fernández. A Comprehensive Survey on Safe Reinforcement Learning. Journal of Machine Learning Research,
2015.
[10] Santiago Paternain, Miguel Calvo-Fullana, Luiz F. O. Chamon, and Alejandro Ribeiro. Safe Policies for Reinforcement Learning via Primal-Dual Methods. IEEE Transactions on Automatic Control, 1321111321-3336 2023.
[11] M. Raissi, P. Perdikaris, and G.E. Karniadakis. Physics-informed neural networks: A deep learning framework for solving forward and inverse problems involving nonlinear partial differential equations. Journal of Computational Physics, 378:686-707, 2019.
[12] Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and Harnessing Adver- sarial Examples. In International Conference on Learning Reprexentations, 2015.
[13] Richard Berk, Hoda Heidari, Shahin Jabbari, Matthew Joseph, Michael J. Kearns, Jamie Morgenstern, Seth Neel, and Aaron Roth. A Convex Framework for Fair Regression. CoRR, 2017.
[14] Irina Higgins, Loic Matthey, Arka Pal, Christopher Burgess, Xavier Glorot, Matthew Botvinick, Shakir Mohamed, and Alexander Lerchner. beta- VAE: Learning Basic Visual Concepts with a Constrained Variational Framework. In International Conference Learning Representations, 2017.
[15] Dimitri Bertsekas. Convex Optimization Theory. Athena Scientific, 2009.
[16] J. F. Bonnans and A. Shapiro. Perturbation Analysis of Optimization Problems. Springer Series in Operations Research and Financial Engineering. Springer New York, 2000.
[17] B. K. Pagnoncelli, S. Ahmed, and A. Shapiro. Sample Average Approximation Method for Chance Constrained Programming: Theory and Applications. Journal of Optimization Theory and Applications, 142(2)399-416, March 2009.
[18] Alexander Shapiro. Darinka Dentcheva, and Andrzej Ruszezynski. Lectures Stochastic Programming: Modeling and Theory, Third Edition. Society for Industrial and Applied Mathematics, 2021.
60

---

[19] Andrew Cotter, Michael P. Friedlander, Gabriel Goh, and Maya R. Gupta. Satisfying Real-Worle Goals with Dataset Constraints. arXiv: 07556, 2017.
[20] Harikrishna Narasimhan. Learning with Complex Loss Functions and Constraints, In Inter- national Conference on Artificial Intelligence and Statistics, volume 84, pages 1646-1654, 2018.
[21] Alekh Agarwal, Alina Beygelzimer, Miroslav Dudik, John Langford, and Hanna Wallach, A Reductions Approach to Fair Classification, 2018.
[22] Luiz F. O. Chamon and Alejandro Ribeiro. Probably Approximately Correct Constrained Learning. In Advances in Neural Information Processing Systems, 2020.
[23] Luiz F. O. Chamon, Santiago Paternain, Miguel Calvo-Fullana, and Alejandro Ribeiro. Con- strained Learning With Non-Convex Losses. IEEE Transactions on Information Theory, 69(3):1739-1 1760, 2023.
[24] Andrew Cotter, Heinrich Jiang, Maya R. Gupta, Serena Lutong Wang. Taman Narayan, Seungil You, and Karthik Sridharan. Optimization with Don-Differentiable Constraints with Applica- tions to Fairness, Recall, Chur,, and Other Goals. Journal of Machine Learning Research, 20:172:1-172:59 2019.
[25] Michael Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu. Preventing Fairness Gerryman- dering: Auditing and Learning for Subgroup Fairness. In International Conference on Machine Learning, volume 80, pages 2564-2572, 2018
[26] Hounie, L. O. Chamon, and A. Ribeiro. Automatic Data Augmentation via Invariance- Constrained Learning. In International Conference on Machine Learning, pages 13410-13433, 2023.
[27] Gilles Gasso, Aristidis Pappaioannou, Marina Spivak, and Léon Bottou. Batch and online learning algorithms for nonconvex Neyman-Pearser classification. ACM Transactions Intelligent Systems and Technology, 2:1-19, 2011.
[28] A. Robey, L. F. O. Chamon, J. Pappas, H. Hassani, and A. Ribeiro. Adversarial Robustness with
Constrained Learning. In Conference on Neural Information Processing Systems, pages 6198-6215, 2021. equal contribution.
[29] Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rodriguez and Krishna P. Gummadi. Fairness Constraints: Mechanisms for Fair Classification. In International Conference on Artificial Intelligence and Statistics, pages 962-970, 2017.
[30] Moritz Hardt, Eric Price, and Nati Srebro. Equality of Opportunity in Supervised Learning. In Advances in Neural Information Processing Systems, pages 3315-3323, 2016.
[31] Matt J. Kusner, Joshua R. Loftus, Chris Russell, and Ricardo Silva. Counterfactual Fairness. In Advances in Neural Information Processing Systems, pages 4066-4076, 2017.
[32] Taco Cohen and Max Welling. Group Equivariant Convolutional Networks. In International Conference on Machine Learning, pages 2990-2999, 2016.
[33] Risi Kondor and Shubhendu Trivedi. On the Generalization of Equivariance and Convolution in Neural Networks to the Action of Compact Groups. In International Conference Machine Learning, pages 2752-2760, 2018
[34] Geoff Pleiss, Manish Raghavan, Felix Wu, Jon M. Kleinberg, and Kilian Q. Weinberger. On Fairness and Calibration. In Advances in Neural Information Processing Systems, pages 5680- 5689, 2017.
[35] Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q. Weinberger. On Calibration Modern Neural Networks. In Proceedings of the 34th International Conference Machine Learning, volume 70, pages 1321-1330. Proceedings of Machine Learning Research, 2017.
[36] Shengjia Zhao, Jiaming Song, and Stefano Ermon. The Information Autoencoding Family: Lagrangian Perspective on Latent Variable Generative Models, 2018.
61

---

[37] Xi Chen, Yan Duan, Rein Houthooft, John Schulman, Ilya Sutskever, and Pieter Abbeel. InfoGAN: Interpretable Representation Learning by Information Maximizing Generative Ad- versarial Nets. In Advances in Neural Information Processing Systems, 2016.
[38] Richard H. Byrd, Frank E. Curtis, and Jorge Nocedal. An Inexact SQP Method for Equality Constrained Optimization. SIAM Journal on Oplimization, 19(1):351336, 2008.
[39] Albert S. Berahas, Frank E. Curtis, Daniel Robinson, and Baoyu Zhou. Sequential Quadratic Optimization for Nonlinear Equality Constrained Stochastic Optimization. SIAM Journal Optimization, 31(2):1352-1375) 2021.
[40] Frank E. Curtis, Daniel P. Robinson, and Baoyu Zhou. Inexact Sequential Quadratic Opti- mization for Minimizing a Stochastic Objective Function Subject Deterministic Nonlinear Equality Constraints, 2021.
[41] Michael J. O'Neill. A Two Stepsize SQP Method for Nonlinear Equality Constrained Stochastic Optimization, 2024.
[42] Hao Chen, Gonzalo E. Constante Flores, and Can Li. Physics-informed neural networks with hard linear equality constraints. Computers & Chemical Engineering, 189:108764, 2024.
[43] Linlin Cao, Ran He, and Bao-Gang Hu. Locally imposing function for Generalized Constraint Neural Networks A study on equality constraints. International Joint Conference on Neural Networks, pages 4795-4802, 2016.
[44] M. Hintermüller. Solving Nonlinear Programming Problems with Noisy Function Values and Noisy Gradients. Journal of Optimization Theory and Applications, 114(1):133-169 2002.
[45] Figen Oztoprak, Richard Byrd, and Jorge Nocedal. Constrained Optimization in the Presence of Noise. SIAM Journal on Optimization, 33:21 18-2166,, 2023.
[46] Shigeng Sun and Jorge Nocedal. Trust-Region Algorithm for Noisy Equality Constrained Optimization. arXiv:2411 1.006665.
[47] Haoming Shen, Yang Zeng, and Baoyu Zhou. Sequential Quadratic Optimization for Solving Expectation Equality Constrained Stochastic Optimization Problems, 2025.
[48] Ferdinando Fioretto, Pascal Van Hentenryck, Terrence W.K. Mak, Cuong Tran, Federico Baldo, and Michele Lombardi. Lagrangian Duality for Constrained Deep Learning, 2020.
[49] Thomas Lew; Riccardo Bonalli, and Marco Pavone. Sample average approximation for stochas- tie programming with equality constraints. SIAM Journal on Optimizationn, 34(4):3506-353) 2024.
[50] E. Cinlar. Probability and Stochastics. Graduate Texts in Mathematies. Springer New York, 2011.
[51] Tuomas Hytönen, Jan van Neerven, Mark Veraar, and Lutz Weis. Analysis in Banach Spaces. Springer, 2016.
[52] W. Rudin. Principles of Mathematical Analysis. International Series Pure and Applied Mathematics. McGraw-Hill, 1976.
[53] Walter Rudin. Real and Complex Analysis, Third Edition. McGraw-Hill, Inc., 1987.
[54] Diestel and J. Uhl. Vector Measures. Mathematical Surveys and Monographs, American Mathematical Society, 1977.
[55] R.T. Rockafellar. Convex Analysis. Princeton University Press, 1997.
[56] Shai Shalev-Shwartz and Shai Ben-David, Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014.
[57] Dionysis Kalogerias and Spyridon Pougkakiotis. Strong Duality Risk-Constrained Nonconvex Functional Programming, 2023.
62

---

[58] Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
[59]
Andrzej Ruszezyúski. Nonlinear Optimization. 2006.
[60]
Kaare Brandt Petersen, Michael Syskind Pedersen, et al. The matrix cookbook. 2008.
[61] Lokenath Debnath and Piotr Mikusinski. Introduction to Hilbert Spaces with Applications,
Third Edition. Academic Press, 2005.
[62] Arka Daw, Jie Bu, Sifan Wang, Paris Perdikaris, and Anuj Karpatne. Mitigating Propagation Failures in Physics-informer Neural Networks using Retain-Resample Resample-Release (R3) Sampling. In International Conference on Artificial Intelligence and Statistics, volume 202, pages 7264-
7302, 2023.
63


Reviews:
[{"review_id": "nqeorCecCP", "reviewer": "Reviewer_Q9iw", "summary": "This paper presents a theory and algorithm for equality constrained learning, addressing the limitations of existing approaches to inequality constraints with an application to fair machine learning. The authors dualized a learning problem with inequality and equality constraints, investigated the generalization bound, and proposed a dual ascent algorithm to solve the problem. Moreoverm the authors demonstrated that the proposed algorithm works in practice, even though its theoretical properties were analyzed under the assumption of access to an oracle optimizer, which is not guaranteed in real applications.", "questions": "- For my major concerns, please see the weaknesses above.\n- In Remark 2.1, for the claim that 'small values $\\epsilon > 0$ lead to numerical issues and worse generalization bounds arising from large Lagrange multipliers,' the authors refer to Theorem 3.1. However, it is not immediately clear to me how Theorem 3.1 supports this claim.\n- There are some minor formatting issues. It would be better to use consistent terms for references. For example, consistently using either the full term or the abbreviation (e.g., theorem vs. thm, section vs. sec, assumption vs. ass, lemma vs. lem) to avoid confusion.", "limitations": "Although the examples given in the paper seem decent, I doubt fair machine learning is the best example to motivate equality constrained learning. When developing fair models, the goal is usually to balance overall performance with fairness across sensitive groups, rather than enforcing strict equality constraints at all costs. In many cases, it is hard to justify compromising the performance of a better-performing group (often the majority) to improve fairness. This raises a concern that if equality constraints are applied, we may end up with trivial or counterproductive solutions that lower performance for all groups. I think this is why recent algorithmic fairness work shifted to encourage a better performance-fairness trade-off instead.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "strengths\n- Provides a theory and algorithm for equality constrained learning which has been underexplored. \n- Provides theoretical results (though I am not fully confident in their correctness, as they are outside my area of expertise) and a numerical algorithm that works in practice.\n\nweaknesses\n- The major contribution of this paper is to develop a theory and algorithm for equality constrained learning. But the examples, applications, and experiments seem biased solely toward fair machine learning. The authors insisted in the introduction that many important requirements are expressed as equality constraints. Why did the authors focus on fair machine learning? I doubt that fair machine learning is the best beneficiary of this work (please see limitations). It would have been better if the authors presented more diverse examples and empirically demonstrated the advantages of applying equality constraints in those examples.\n- Figure 1 shows that the approximate algorithm with a small tolerance for the inequality constraints works as good as the exact algorithm with equality constraints. If we are able to achieve a sufficiently good approximation by choosing an appropriate tolerance for the inequality constraint, why do we need an exact algorithm? This example does not support the claim \"small values $\\epsilon > 0$ lead to numerical issues and worse generalization bounds (although it is true). An example that the inequality with small tolerance cannot approximate the exact one will be more convincing. \n- In summary, I’m not entirely convinced that developing theory and optimization algorithms for equality constrained learning is important, however, I do believe this line of work is valuable and will offer useful contributions.", "was_revised": true, "final_justification": "As highlighted in the original manuscript and further reinforced by the authors’ responses, learning with equality constraints has many applications, yet the supporting theory and algorithms remain underdeveloped. The manuscript is well-organized, and with the added results and clarifications, I see no reason to undervalue the contribution.", "rebuttal": "We thank the reviewer for their comments.  We address their concerns point-by-point below.\n\n\n> **W1: Why did the authors focus on fair machine learning? I doubt that fair machine learning is the best beneficiary of this work (please see limitations)**\n\nAs the reviewer points out, equality constraints find many applications beyond fairness. The manuscript uses fairness to illustrate *one* potential use of equalities since the focus is on deriving generalization bounds for equality-constrained learning problems (despite non-convexity). For instance, consider the unsupervised learning problem of approximating solutions of a differential equations (DE), namely, finding $u$ such that\n\n$$\n\\begin{alignat*}{2}\n\\\\mathcal{D}\\[u\\](x,t) &= 0, \\\\quad &&\\\\forall (x,t) \\\\in \\\\Omega \\\\times (0,T\\]\\\\\\\\\nu(x,t) &= h(x,t), \\\\quad &&\\\\forall x \\\\in \\\\partial \\\\Omega \\\\times (0,T\\]\\\\\\\\\nu(x,0) &= h(x,0), \\\\quad &&\\\\forall x \\\\in \\\\Omega \\\\cup \\\\partial\\\\Omega\n\\end{alignat*}\n$$\n\nHere, $\\mathcal{D}$ denotes a differential operator, $\\Omega$ is a domain with boundary $\\partial \\Omega$, and $h$ defines the boundary (and initial) conditions (see, e.g., [Raissi et al \"Physics-informed neural networks: A deep learning framework for solving forward and inverse problems involving nonlinear partial differential equations\", 2019; Daw et al., \"Mitigating Propagation Failures in Physics-informed Neural Networks using Retain-Resample-Release (R3) Sampling\", 2023] for more details). We can cast this problem using (P) by parametrizing the solution $u$ using, e.g., a NN, as in\n\n$$\n\\begin{align*}\n\\text{minimize}\\_{\\theta \\in \\Theta} &\\;\\|\\theta\\|^2 \\\\\\\\\n\\text{subject to} & \\\\; \\mathbb{E}\\_{\\mathbb{P}\\_1}[(\\mathcal{D}\\[u\\_{\\theta}\\](x,t))^2] = 0 \\\\\\\\\n& \\\\; \\mathbb{E}\\_{\\mathbb{P}\\_2}\\[(u\\_{\\theta}(x,t) - h(x,t))^2\\] = 0 \\\\\\\\\n& \\\\; \\mathbb{E}\\_{\\mathbb{P}\\_3}\\[(u\\_{\\theta}(x,0) - h(x,0))^2\\] = 0\n\\end{align*}\n$$\n\nThe distributions $\\mathbb{P}_1$, $\\mathbb{P}_2$, and $\\mathbb{P}_3$ are taken to be uniform over $\\Omega \\times (0,T]$, $\\partial \\Omega \\times (0,T]$, and $\\Omega \\cup \\partial\\Omega$ respectively. Below we show preliminary results for a convection problem ($\\beta=30$) with sinusoidal boundary conditions following the experimental setup of [Daw et al.] (the starred column was taken from [Daw et al., Table 1] and represent the mean of 5 runs). Note that these improvements come at essentially no additional computational cost, since the dual variable update (step 7 of Algorithm 1) is almost trivial.\n\n| PINN (5 runs)* | Constrained (5 runs) |\n| -------------- | -------------------- |\n| 2.81           | 2.06                 |\n\nA supervised learning example based on the CIFAR-10 dataset can be found in our response to `Reviewer 1hsE`. If the reviewer finds it beneficial, we can include this example and results in the camera-ready.\n\nThat being said, we sustain that equality constraints are particularly well-suited for fairness. Indeed, as the reviewer points out, the goal of fair learning is often to obtain the best possible accuracy (performance) while remaining fair. As this manuscript proves, this is exactly what the constrained learning problem (P) can achieve in contrast to penalty approaches. Though certain application may accommodate relaxations of, e.g., demographic parity, that may not always be the case. It is more appropriate in these cases use an equality constraint as in (P-DP) than to try to find a tight relaxation $\\epsilon$ that achieves such strict demands (in our example, even $\\epsilon=0.05$ substantially changes the solution).\n\nBeing accurate may also mean matching prior decisions that are themselves biased. Then, improving fairness requires making predictions that are different from those in the dataset (reducing \"accuracy\"). The definition of algorithmic fairness in (P-F), which we dub \"prescriptive fairness,\" is more appropriate in these settings. Indeed, while (P-DP) can \"overcome\" biases that affect the prediction within the groups compared to the population (e.g., too many positive predictions for one group compared to another), (P-F) can *simultaneously* overcome predictive bias affecting the population (e.g., too many positive predictions in general). This is clear from Figure 2a: unconstrained and DP achieve essentially the same predicted recidivism rate. On the other hand, (P-F) enables other desired predictive rates to be achieved uniformly across group (Figure 2b).\n\nWe should emphasize at this point that equalities and inequalities are not competing tools to solve fair learning problems, but rather complementary ones. Indeed, (P) accomodates both types of constraints and the most useful type will depend on the application. In fact, fair learning problems may need to involve both, as we detail in our response to `Reviewer SL24`.\n\n\n> **W2: Figure 1 shows that the approximate algorithm with a small tolerance for the inequality constraints works as good as the exact algorithm with equality constraints... This example does not support the claim \"small values lead to numerical issues and worse generalization bounds (although it is true)**\n\nAs we argue in Remark 2.1 and Appendix D, there is a close relation between (P) with an equality constraint as in $\\mathbb{E}[h_j(f_{\\theta}(x), y)] =0$ and (P) when that constraint is replaced with two inequality constraints as in $-\\epsilon \\leq \\mathbb{E}[h_j(f_{\\theta}(x), y)] \\leq \\epsilon$. Indeed, it is straightforward that both problems become the same as $\\epsilon$ vanishes. Hence, it is natural to expect that their solutions would be similar. There is also a close *numerical* relation between their dual problems which, though not equivalent, are again very similar (see Appendix D.2).\n\nThat being said, current generalization guarantees for (inequality) constraints do not hold as $\\epsilon$ vanishes (see, e.g., [11,12]). Additionally, it is not straightforward to determine how small $\\epsilon$ must be to achieve the performance of the equality-constrained problem. In our example, it has to be as small as $10^{-4}$ (Figure 1), but it could be even smaller for more sensitive problems. As such, there is a need for a new theory and algorithm that can accomodate equality constraints (i.e., vanishing $\\epsilon$). We again emphasize that equalities and inequalities are not competing solutions, but complementary tools to tackle constrained learning problems.\n\nYet, the reviewer has a point that Figure 1 does not support the claim that \"small $\\epsilon$ lead to numerical issues and worse generalization bounds.\" That is, in fact, not necessarily the case and depends on how equality constraints are turned into inequalities. Indeed, as we point out in Remark 2.1 and Appendices D.1, replacing an interpolation constraint by the mean-square error can lead to arbitrarily large dual variables as $\\epsilon$ vanish. On the other hand, under the conditions of Theorem 3.1, this does not happen when directly relaxing (P) as in Lemma B.5. We will extend Remark 2.1 (line 111) to ensure that this is clear in the camera-ready version of the manuscript.\n\n\n> **W3: In summary, I’m not entirely convinced that developing theory and optimization algorithms for equality constrained learning is important, however, I do believe this line of work is valuable and will offer useful contributions.**\n\nAs the reviewer points out in W1, a variety of ML problems are inherently equality constrained learning problems. Yet, as argued in Remark 2.1 and the response to W2, current generalization guarantees do not hold for constrained learning problems containing equality constraints (e.g., [11,12]). Additionally, it is not clear beforehand (i.e., without knowing the equality solution) how tight the inequality relaxation should be to remain close to the equality-constrained problem. Indeed, notice from Figure 1 how much the solution changes even for $\\epsilon=0.05$. What is more, certain relaxations may lead to numerical issues (large dual variables, see Appendix D.1). As such, we believe that the theoretical and algorithmic contributions of this manuscript are indeed important. We will make these points clearer in the introduction of the camera-ready version of this paper.\n\n\n> **Q1: In Remark 2.1, ... the authors refer to Theorem 3.1. However, it is not immediately clear to me how Theorem 3.1 supports this claim.**\n\nAs we detailed in W2, the quality and generalization properties of the relaxed problem depend on how the equality constraints are relaxed to inequality constraints. Remark 2.1, in particular, refer to the benign, convex learning problem ($\\text{P}_e$) presented in Appendix D.1, where we prove that, when replacing interpolation equalities by a bound on the mean squared error as in ($\\text{P}_i$), the magnitude of the Lagrange multipliers $||\\gamma^\\star||$ become arbitrarily large as $\\epsilon$ vanishes. Since the guarantees in Theorem 3.1 are proportional to $||\\gamma^\\star||$, they therefore become vacuous for this problem as $\\epsilon$ vanishes. We therefore obtain \"worse generalization bounds arising from large Lagrange multipliers (see Thm 3.1)\" (Remark 2.1, line 112). We will extend Remark 2.1 to ensure this point (and those from the response of W2) are clear in the camera-ready version.\n\n\n> **Q2: There are some minor formatting issues.**\n\nWe will copy-edit the whole manuscript to correct such inconsistencies."}, {"review_id": "YVDKugEhiq", "reviewer": "Reviewer_SL24", "summary": "This paper addresses the problem of learning under equality constraints. It proposes a theoretical framework for non-convex problems and proves strong duality and generalization bounds under a set of relatively strong assumptions. Based on this, the authors introduce a practical primal-dual algorithm that reduces the problem to a sequence of unconstrained optimizations.", "questions": "please see weakness section", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "**Strengths**\n\n- The paper are clearly written.\n- The paper fills a theoretical gap by extending constrained learning theory from inequality to equality constraints.\n\n**Weaknesses**\n\n- Would Assumption 1 still hold if multiple potentially conflicting fairness constraints are imposed simultaneously? Have the authors considered or tested such settings?\n- It is unclear how robust the theory is when the assumption only approximately holds or fails in more constrained or imbalanced scenarios.\n- The algorithm requires solving a full learning problem at each dual update, which can be costly with large models or many constraints.", "was_revised": true, "final_justification": "I am satisfactory with the author's responses and vote for the acceptance", "rebuttal": "> **W1. Would Assumption 1 still hold if multiple potentially conflicting fairness constraints are imposed simultaneously? Have the authors considered or tested such settings?**\n\nIf (P) includes conflicting fairness criteria (in the sense of impossibility theorems such as [Kleinberg et al - Inherent Trade-Offs in the Fair Determination of Risk Scores]), then it is infeasible (has no solution), which in turn implies that Assumption 1 does not hold. Note that since the population problem (P) has no solution in this setting, which makes its value $P^\\star$ undefined (or, as per the typical convention, $\\infty$), which invalidates any traditional notion of generalization. In such a case, at least one of the equalities needs to be relaxed. In view of the duality results in this paper, it would make sense to relax the most stringent one (largest dual variables) or use an automatic relaxation technique such as in [Hounie et al., Resilient Constrained Learning, 2023]. If the reviewer believes it would be beneficial, we can include an example of such a procedure in the appendices of the camera-ready.\n\n\n> **W2. It is unclear how robust the theory is when the assumption only approximately holds or fails in more constrained or imbalanced scenarios.**\n\nAs we comment throughout the paper, the majority of our assumptions are typical in the literature and mild in practice, including Lipschitz continuity of losses and models (Assumption 3 and 4), sufficiently rich parametrizations (Assumption 3), atomlessness of distributions (Assumption 2), and uniform convergence (Assumption 5). As the reviewer correctly notices, Assumption 1 is potentially more stringent. Yet, what it does is ensure that (P) and neighboring problems have at least one solution (as we explain in line 131). In other words, that (P) is and remains feasible even if when perturbed. As we explain above, this is necessary to even talk about generalization: if (P) has no solution, then its value $P^\\star$ is undefined and cannot be approximated. This point will be clarified in the camera-ready version of the manuscript.\n\n> **W3. The algorithm requires solving a full learning problem at each dual update, which can be costly with large models or many constraints.**\n\nIndeed, the convergence guarantees in Theorem 4.1 are for Algorithm 1 which does (approximately) solve an *unconstrained* learning problem (step 5). That is, however, not *necessary* to obtain good results in practice as our numerical examples illustrate. Indeed, Figure 4(a) in Appendix F shows that the results of taking a single gradient step at each dual update does yield results that satisfy the constraints. In fact, there is substantial empirical evidence that a perfect oracle (full solution in step 5) is not necessary for constrained learning problems (see, e.g., [11,12,19,24,32]). While we believe that this is an interesting research direction, it is beyond the scope of this work. Note also that while by the model size does affect the complexity of step 5 (primal gradient), the number of constraints only affects the dimensionality of the dual problem, whose gradient is trivial to compute (steps 6 and 7)."}, {"review_id": "UUyThVvymG", "reviewer": "Reviewer_1hsE", "summary": "This paper studies the problem of optimization with equality constraints, where the duality and generalization results obtained for inequality-constrained learning apply to these problems. This is motivated by the practical needs that machine learning systems with goals such as in fairness tends to require equality constraints instead of a bound. This paper developed a generalization theory for equality constrained learning tasks:\n- the paper derived additional regularity conditions under which duality and sensitivity results for non-convex equality-constrained optimization problems are obtained\n- the paper then propose a practical algorithm based on solving a sequence of unconstrained, empirical learning problems, and characterized the approximation and generalization error of its solutions\n- experiments using examples in group fairness show the effectiveness of the proposed solution", "questions": "- there is a lack of any discussions on the optimality of the provided error bound: under what scenarios it is tight  / lose?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n- this paper studied a practical but less explored formulation with the equality constraints instead of inequality constraints, the problem is well-motivated from practical applications especially fairness\n- the derivation of the error bound is intuitive via the duality formulation, and the bound itself reflects the different drivers of the error, including the sensitivity on constraints / formulation, model capacity, sample size etc\n- experimental results show that with small tolerance, inequality formulation achieves similar results as the proposed DP, however the difference becomes non-negligible when the tolerance parameter is high\n\nWeakness:\n- The algorithm in section 4 assumes the access to an oracle optimizer. Although the experiments show that single alternating updates with an optimizer eg Adams work relatively well, the results are only based on simple setting and one dataset. The experimental support should be strengthened with more diverse setups and complex data.", "was_revised": true, "final_justification": "The author response was helpful in addressing my concern about the oracle optimizer. I will keep my original score for a weak acceptance.", "rebuttal": "> **W1. The algorithm in section 4 assumes the access to an oracle optimizer... The experimental support should be strengthened with more diverse setups and complex data.**\n\nIndeed, the convergence guarantees in Theorem 4.1 hold for Algorithm 1 which does require an *unconstrained* learning problem to be (approximately) solved in step 5. This is not, however, *necessary* to obtain good results in practice as our numerical examples illustrate (see, e.g., Figure 4(a) in Appendix F). This fact has been observed in a myriad of constrained learning problems involving inequality constraints of various types (see, e.g., [11,12,19,24,32]). While we believe that explaining this behavior is an interesting research direction, it is beyond the scope of this work.\n\nNevertheless, we agree with the reviewer that additional examples could help illustrate not only the behavior of the algorithm, but also other use cases of equality constraints. In our response to W1 of `Reviewer Q9iw`, we detail an application to solving a partial differential equation (PDE). But (P) and Algorithm 1 can also be used to train interpolating classifiers. Indeed, if we train a CNN (ResNet18) on CIFAR-10 using the traditional ERM formulation with cross-entropy loss, we obtain a test accuracy of 85.18% after approximately 90 epochs (using ADAM with lr=5e-4 and batch size=256). The same interpolating classifier can also be trained using (P) to disaggregate the classes as in\n$$\n\\begin{align*}\n\\text{minimize}_{\\theta \\in \\Theta} & \\;  \\|\\theta\\|^2 \\\\\\\\\n\\text{subject to} & \\\\; \\mathbb{E}\\_{\\mathbb{P}}[\\ell(f\\_{\\theta}(x),y)|y=j] = 0, \\quad \\text{for } j = 1,\\ldots, 10.\n\\end{align*}\n$$\nWhen using Algorithm 1 to solve this problem, the dual variables have the effect of reweighting the loss of each class [see the Lagrangian definition in (1)]. This leads to an improvement in the test accuracy (86.06%) using the same hyperparameters as before. This is due to classes that are harder to fit (e.g., \"bird\") being \"prioritized\" during training. Due to NeurIPS restrictions on the use of images in the rebuttal phase, we cannot show the complete training dynamics, but we show the final dual variables values ($\\mu_j$) below.\n\nIf the reviewer finds it beneficial, we will use the additional content page of the camera-ready to include these use cases. Additionally, if they had another specific application and dataset in mind, we would happily consider using it in our experiments as well.\n\n| airplane | automobile | bird    | cat     | deer    | dog     | frog    | horse  | ship   | truck  |\n| -------- | ---------- | ------- | ------- | ------- | ------- | ------- | ------ | ------ | ------ |\n| 1074.09  | 912.54     | 1124.30 | 1232.01 | 1061.10 | 1180.55 | 1039.51 | 984.14 | 971.45 | 957.56 |\n\n\n> **Q1. there is a lack of any discussions on the optimality of the provided error bound: under what scenarios it is tight / lose?**\n\nIn contrast to unconstrained learning, to the best of our knowledge, *no lower bounds* have been proposed for the constrained learning error $|P^\\star - \\hat{D}^\\star|$. As such, we cannot formally discuss the tightness of our bound. We agree that this is an interesting direction, but it is beyond of the scope of this work. Qualitatively, we believe there are situations in which the upper bound *can* be improved, particularly when (P) is convex and more refined perturbation and statistical results can be used (see, e.g., [Bonnans and Shapiro. \"Perturbation Analysis of Optimization Problems\"; Shapiro et al. \"Lectures on Stochastic Programming: Modeling and Theory\"] which are references [16;18] from the appendices)."}, {"review_id": "bG7zOKpx57", "reviewer": "Reviewer_8xzy", "summary": "This article studies the statistical learning problem with statistical equality constraints. It establishes a generalization bound (Thm 3.1) for this problem and discusses clearly and explicitly how this result is complementary to known properties of inequality-constrained statistical optimization problems. It introduces a primal-dual algorithm for the problem that alternates between the solution of unconstrained, empirical learning problems and the optimization of Lagrange parameters via an oracle (Assumption 6). The empirical dual value is related to the average of the Lagrangian iterates (Thm., 4.1), without solving the primal recovery problem, and with respect to the oracle. Toward experiments, the oracle is replaced by single alternating updates. The effectiveness of this practical algorithm is analyzed in an application to practical instances of the problem in which fairness is expressed in the form of statistical equality constraints.", "questions": "- While I understand both (P) and (P-DP), it took me a bit to see how (P-DP) can be put in the form (P). Would you like to introduce the $g_i$ that does this instead of using the Iverson bracket in (P-DP)?\n- Define the image of $f_\\theta$ consistently as $\\mathcal{Y}$ (as in Line 52) or $\\mathbb{R}^K$ (as in Line 51).", "limitations": "The article communicates explicitly all assumptions made by the authors. This includes, in particular, the important assumption of uniform convergence (Assumption 5). This assumption is satisfied in many relevant cases, including families with finite VC-dimension.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The problem is interesting and important.\n- The theoretical results are plausible, the high-level reasoning in the main article is correct and convincing. (I have not checked the proofs in detail).\n- Although the article is an immediate continuation of [11,32], the authors are explicit about this fact (e.g. in Line 98) and explain why this continuation is non-trivial (notably in Remark 2.1).\n- The empirical method is convincing; the empirical results are interesting and insightful.\n- The article is well-written.\n\nWeaknesses:\n- I am not sure whether the case of deterministic (hard) equality constraints is merely a special case. The authors should discuss this. If special attention is needed, I suggest to use a more specific title \"Learning with Statistical Equality Constraints\".", "was_revised": true, "final_justification": "I find all my points addressed and maintain my positive rating.", "rebuttal": "> **W1. I am not sure whether the case of deterministic (hard) equality constraints is merely a special case... I suggest to use a more specific title \"Learning with Statistical Equality Constraints\".**\n\nThe reviewer has a point. We will include an explicit remark on this fact following Theorem 3.1 and adopt the title they suggest.\n\n\n> **Q1. While I understand both (P) and (P-DP), it took me a bit to see how (P-DP) can be put in the form (P). Would you like to introduce the $g_i$ that does this instead of using the Iverson bracket in (P-DP)?**\n\nThe reviewer has a point that this transformation is not straightforward. Explicitly, (P-DP) can be cast in the form of (P) by taking\n\n$g\\_j(f\\_{\\theta}(x), y) = \\mathbb{I}[f\\_{\\theta}(x) > 0.5] \\mathbb{I}[x \\in \\mathcal{G}\\_j] - \\mathbb{I}[f\\_{\\theta}(x) > 0.5]$\n\nand $\\mathbb{Q}\\_j = \\mathbb{P}$, the data distribution. Alternatively, we could consider $g\\_j(f\\_{\\theta}(x), y) = \\mathbb{I}[f\\_{\\theta}(x) > 0.5]$ and take the expectation with respect to $\\mathbb{Q}\\_j = \\mathbb{P}(\\cdot | x \\in \\mathcal{G}\\_j) - \\mathbb{P}$. While the latter is not a probability measure, the guarantees of Theorem 3.1 hold for general measures.\n\nWe will include the first formulation in the camera-ready version of the manuscript.\n\n> **Q2. Define ... consistently as in Line 52...**\n\nWe thank the reviewer for pointing out this typo. The correct function signature is $f\\_{\\theta}: \\mathcal{X} \\to \\mathbb{R}^K$. We will fix this and other typos in the camera-ready version."}]

Author rebuttal:

Meta-review: The reviewers, the authors, and I as Area Chair all agree that the submission is of high enough quality for publication at NeurIPS. Congratulations!
Decision: Accept (poster)