Resilient Constrained Learning
Authors: Ignacio Hounie
Alejandro Ribeiro
Luiz F. O. Chamon
Venue: NeurIPS 2023 poster (2023)
Keywords: Constrained Learning
Relaxation
Lagrangian duality
Primal-Dual
Machine Learning
Federated Learning
Invariance
TL;DR: Relaxing constrained learning problems by balancing performance gains obtained from the relaxation against a user-defined cost of that relaxation.

Abstract: When deploying machine learning solutions, they must satisfy multiple requirements beyond accuracy, such as fairness, robustness, or safety. These requirements are imposed during training either implicitly, using penalties, or explicitly, using constrained optimization methods based on Lagrangian duality. Either way, specifying requirements is hindered by the presence of compromises and limited prior knowledge about the data. Furthermore, their impact on performance can often only be evaluated by actually solving the learning problem. This paper presents a constrained learning approach that adapts the requirements while simultaneously solving the learning task. To do so, it relaxes the learning constraints in a way that contemplates how much they affect the task at hand by balancing the performance gains obtained from the relaxation against a user-defined cost of that relaxation. We call this approach resilient constrained learning after the term used to describe ecological systems that adapt to disruptions by modifying their operation. We show conditions under which this balance can be achieved and introduce a practical algorithm to compute it, for which we derive approximation and generalization guarantees. We showcase the advantages of this resilient learning method in image classification tasks involving multiple potential invariances and in federated learning under distribution shift.

Resilient Constrained Learning
Ignacio Hounie
Alejandro Ribeiro University of Pennsylvania
Luiz F. O. Chamon University of Stuttgart
University Pennsylvania
Abstract
When deploying machine learning solutions, they must satisfy multiple require- ments heyond accuracy, such as fairness, robustness, or safety. These requirements are imposed during training either implicitly, using penalties, explicitly, using constrained optimization methods based on Lagrangian duality. Either way, speci- fying requirements is hindered by the presence of compromises and limited prior knowledge about the data. Furthermore, their impact on performance can often only be evaluated by actually solving the learning problem. This paper presents a constrained learning approach that adapts the requirements while simultaneously solving the learning task. To do so, relaxes the learning constraints contemplates how much they affect the task at hand by balancing the performance gains obtained from the relaxation against a user-defined cost of that relaxation. We call this approach resilient constrained learning after the term used to describe ecological systems that adapt disruptions by modifying their operation. We show conditions under which this balance can be achieved and introduce practical algorithm to compute it, for which we derive approximation and generalization guarantees. We showcase the advantages of this resilient learning method in image classification tasks involving multiple potential invariances and in heterogeneous federated learning.
way that
Introduction
Requirements are integral to engineering and of growing interest in machine learning (ML) (T] This growing interest evident in, e.g., the advancement towards designing ML systems that fair [2]. robust [3]. and safe (4) as well as numerous applications in which we want to attain good performance with respect to more than one metric 24). Two concrete applications that we will use as examples (Section (5) are heterogeneous federated learning, where each client realizes different loss due distribution shifts (as in, e.g., (0)) and invariant learning, where we seek to achieve good performance even after the data has undergone variety of transformations (as in, e.g..
15 21
The goal in these settings is to strike a compromise between some top-line objective metric and the requirements. To this end, an established approach to combine the top-line and requirement violation metrics in single training loss. This leads to penalty methods that are ubiquitous in ML, as attested by, e.g., fairness 25 28 and robustness (29 30 applications. Another approach balance objective and requirements is formulating and sol ving constrained learning problems. Though less typical in ML practice, they are not uncommon (5 18 21]24. In particular, they have also been used in fair (31-34] and robust [12 35) learning, to preceed with common set of applications. It is worth noting that penalty and constrained methods are not unrelated. They are fact equivalent convex optimization, in the sense that every constrained problem has an equivalent cenalty-based formulation. similar result holds in non-convex MI. settings for sufficiently expressive parametrizations ().
In either case, the compromise between objective and different requirements are specified by (hy- per)parameters, be they penalty coefficients constraint levels (Section 2).. Finding penalties or constraints specifications that yield reasonable trade-offs is particularly difficutt in ML, which often
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

involves statistical requirements, such as fairess and robustness, that have intricate dependencies with the model and unknown data distributions. Case point, consider invariant learning for image classification [3) While we know that invariance to rotations and translations is desirable, we do not know how much invariance to these transformations is beneficial. This depends on the level of invariance of the data distribution, its prevalence in the dataset, and the capability of the model to represent invariant functions. The standard solution to this problem involves time consuming and computationally expensive hyperparameter searches.
This paper addresses this issue by automating the specification of constraint levels during training. To do so, it begins by interpreting constraints as nominal specifications that can be relaxed to find better compromise between objective and requirements (Section We call this approach resilient constrained learning after the term used to describe ecological systems that adapt to disruptions by modifying their operation (3).7]]. Our first contribution is the following insight:
(C1)
We relax constraints according their relative difficulty, which we define the sensitivity of the objective to perturbations of the constraint (Section 3.1)
That difficult constraints should be relaxed more is a natural choice. The value of (C1) is in defining what a difficult constraint. We then seek constraint levels such that the objective loss is relatively insensitive to changes in those levels. This relative insensitivity incorporates a user-defined cost that establishes a price for relaxing nominal specifications.
The learning problem implied by (C1) seems challenging. Our next contribution is to show that is not:
(C2) We use duality and perturbation theory to present reformulations of the resilient learning problem from (C1) (Section 3.2) that lead to a practical resilient learning algorithm (Sec-
tion for which we derive statistical approximation bounds (Thm. D
Our final contribution is the experimental evaluation of the resilient learning algorithm:
C33 We evaluate resilient formulations of federated learning and invariant learning (Section 5
Our experiments show that (C1) effectively relaxes constraints according to their difficulty, leading solutions that less sensitive to the requirement specifications. It illustrates how resilient learning constitutes an interpretable and flexible approach to designing requirements while contemplating performance trade-offs.
2 Learning with Constraints
Let Do be distribution over data pairs (x, y) composed of the feature vector x E X' C Rd and the corresponding output E y
C TR. Let fo X > IR be the function associated with parameters 0 θ RRp and to R$ x y + [-B, B] be the loss that evaluates the fitness of the estimate fo(x) relative to y. Let Fe = {fo by these functions. Different from traditional (unconstrained) learning, we do not seek fo that simply minimizes [[(((((x), v)]. but also account for its expected value with respect to additional losses & R x + [- B] and distributions D;, i = 1,..., m. These losses/distributions typically encode statistical requirements, such as robustness (where D, denote distribution shifts adversarial perturbations) and fairness (where D2 are conditional distributions of protected subgroups).
E b} be the hypothesis class induced
Explicitly, the constrained statistical learning (CSL) problem is defined as
E (xx.))Do [Lo [fo(f((x),
P min AEO
subject to (x (f(()))) S0, i 1= 1....,mm.
Without loss of generality, we stipulate the nominal constraint specification to be zero Other values
can be achieved by offsetting l, i.e., [E](ff( y) I e obtained using l.(-) E(-) c in (P). We also let p* take values the extended real line R U {oo} by defining P = whenever (P) is
infeasible, i.c., whenever for all 0 ④ there exists such that Ep, (f) v)] > 0.

---

A challenge in formulating meaningful CSL problems lies in specifying the constraints, i.e., the & Indeed, while solution fo- always exists for unconstrained learning [m 0 in (P), there may be no 0 that satisfies the constraints in (P). This issue is exacerbated when solving the problem using data: even arbitrarily good approximations of the expectations (P) may introduce errors that hinder the estimation of P* (see Appendix [ for a concrete example). In practice, landing on feasible requirements may require some constraints to be relaxed relative to their initial specification. Then, in lieu of (P). we would use the relaxed problem
min (*(
E(x,))>Do [ (o([o(x))))
dEB
(P
subject to E( 4 (fo Uis i= I,...,
where u E RT collects the relaxations u, 2 0. The value P*(u) ) is known as the cnnturbationfuncttinn the optimal value. Given P P*()) P and (Po)
of (P) since it describes the effect of the relaxation
equivalent to (P), this abuse of notation should not lead to confusion.
It is ready that (*(u) is componentwise non-increasing function, i.e.. that for comparable argu- ments V; < we for all (denoted v I w), holds that P (v) 2 P*(w). However, large relaxations u drive (P.) away from (P). the learning problem of interest. Thus, relaxing (P) too much can be as detrimental as relaxing too little (see example in Appendix [A]. The goal of this paper is to exploit
properties of P* (*(u) together with relaxation cost strike balance between these conflicting objectives. We call this balance a resilient version of (P).
3 Resilient Constrained Learning
We formulate resilient constrained learning using functional form of P.. Explicitly, consider a convex function class F 2 Fo and define the relaxed functional problem
P*(u) min ΦEF
(xx,))Do
(octssCeoo(ss (o((()))))
(P.)
subject to B(x,))DD (: (((())) S us. i 1,..., m.
The difference between P and P is that the latter does not rely parametric model. Instead, its solutions take values on the convex space of functions F. Still, if Fo sufficiently rich parameterization of FF (see Section for details), then P*(u) and P*(u) are close [38 Sec. 3].
Throughout the rest of the paper, we use to identify these functional problems.
The advantage of working with convex. This holds readily if the losses are convex (e.g., quadratic or cross-entropy) (39 chap. 5]
is that under mild conditions the perturbation function P is
However, the perturbation function is also convex for variety of non-convex programs, e.g., ( with non-convex losses, non-atomic D., and decomposable F (see Appendix B For conciseness, encapsulate this hypothesis in an assumption.
Assumption 1. The perturbation function P*(u) is convex function of the relaxation u E R
A consequence of Assumption is that the perturbation function P* has non-empty subdifferential at every point. Explicitly, let its subdifferential aP* (u") at u E RT be defined as the set of vectors describing supporting hyperplanes at u of the epigraph of P i.c.
Op*(u') = {DE ETERTIN 1
+ p (v uz), for all v E IT
The elements of (P*( are called subgradients of P* at u If P is differentiable at u², then it has single subgradient that is equal its gradient, i.c., 0p* (u")
(VP((u")) In general, however, the subdifferential is non-singleton set (40). Further notice that since P (u) is componentwise nonpositive the subgradients are componentwise negative, Pn = 0.
Next, we use this property to formalize resilient constrained learning as compromise between reducing P Pu( by increasing and staying close the original problem Po
3

---

Infeasible
PP (M)
Infeasible
dP (w)
Infeasible
(1)
dh(u) du
du
db(u) du
dvz
dhi [1)
04.2
M6
1
M
(a)
(b)
(c)
Figure 1: Resilient equilibrium from Def. | for h(u) u² w2/2.. The shaded area indicates infeasible specifications: (a) nominal specification (u 0) is feasible and easy to satisfy; (b) nominal specifica-
tion is feasible but difficult to satisfy (close to infeasible); (c) nominal specification is infeasible.
3.1 Resilient Equilibrium
Consider the effect of increasing the value of specific relaxation in (P while keeping the rest unchanged. The solution of (Pu.) is allowed suffer higher losses on the constraints (4, for 2 1), which may lead to a smaller objective loss (f)). Hence, while larger relaxations are detrimental because they violate more the requirements, they are also beneficial because they reduce the objective loss. To balance these conflicting outcomes of constraint relaxations, we introduce a function h to capture their costs. Then, since relaxing both increases the costs and decreases the objective value, we conceptualize resilience as equilibrium between these variations.
Definition (Resilient Equilibrium). Let RT R_ be a convex, differentiable, normalized (i.e., h(0) = 0), and componentwise increasing (i.e., h(v) < h(w) for w) function. A resilient equilibrium ( is a relaxation u satisfying
Vl(n") E (u*)
(2)
The resilient constrained learning problem amounts to solving Pu-)). i.e., solving P for a relax- ation u* that satisfies (2). We call this equilibrium resilient because describes how far (Po) can be relaxed before we start seeing diminishing returns. Indeed, u from (2) is such that relaxing by an additional c > would incur in a relaxation cost least Vh(u*)" larger, whereas tightening to u² would incur in an optimal value increase of at least the same Vh(u")Tec.
Notice that resilient constrained learning is defined in terms of sensitivity. Indeed, the resilient equilibrium in Def. (1) specifies learning task that is as sensitive to changes in its requirements as sensitive to changes in the relaxation cost. This has the marked advantage of being invariant constant translations of lo. as is also the case for solutions of (P.). Sensitivity also measures the difficulty of satisfying constraint, since Op*(u (u) quantifies the impact of each constraint specification on the objective loss. Hence, the equilibrium in has the desirable characteristic of affecting stringent requirements more.
Two important properties of the equilibrium in Def. I are summarized next (proofs provided in appendices D.I and D.2) Proposition 1. Under Ass. 7 the resilient equilibrium 2 exists. If is strictly convex, it is unique. Proposition 2. Let v, E Ry be such that [v]; = [w], for i j. and [v]; < [wi,. Under Ass. 7 (i) [Vh(v)], [Vh(w)], and (ii) p 2 [- Pwly for all Py E aP*(v) and P ap (w))
Prop. M shows that the equilibrium in 2 is well-posed Prop. 2 states that, all things being equal, relaxing the j-th constraint increases the sensitivity of the cost
while simultaneously decreasing its effect the objective value P*. To illustrate these points better, Fig. considers prototypical learning problems with a single constraint [m 1 in cost h(w) u² 22 According (). the resilient relaxations are obtained h'(u*)
differentiable P*(u), and relaxation p''(")), where we let g' ()) = du(u)/ du denote the derivative of the function g. As per Prop. 2 h1' is increasing
and -P is decreasing. Further observe that the sensitivity -p'(u) diverges as v approaches the value that makes the problem infeasible and vanishes as the constraint is relaxed. These two curves must therefore intersect, claimed by Prop.

---

The illustrations in Fig. represent progressively more sensitive/difffeull problems. In Fig. Lt the nominal problem (u = 0) is easy to solve (small P*())), making the resilient equilibrium u s 0. The original problem and the relaxed problem are essentially equivalent. In Fig. Dp. the nominal problem is difficult to solve (large (*)),, inducing a significant change in the constraint and objective losses. In Fig. C the nominal problem is unsolvable, but the resilient relaxation recovers feasible problem.
Having motivated the resilient compromise in Def. I and proven that it is well-posed, we proceed obtain equivalent formulations that show it is also computationally tractable. These formulations are used to show traditional learning tasks that can be seen as resilient learning problems (Sec. (3)c.3.3) before deriving practical algorithm tackle the resilient learning problem uu (Sec.
3.2 Equivalent Formulations
While we have shown that the resilient relaxation from Def. exists (Prop. D the equilibrium in 2 does not provide a straightforward way to compute it. In this section, we show two more computationally amenable reformulations of Def. by relating u* to the Lagrange multipliers of (P and to the solution of related optimization problem.
Let À R collect multipliers X; associated to the i-th constraint of P and define the Lagrangian
u:) ED. [ex(((x)), y)]
X ED, [((()(x). Us
Based on 3), define dual functions 9(\; u) and dual problems (r( for given constraint level u,
(u) max u); max min L(o, u) 2
(Du)
X dEF
While ò+ < p* (weak duality) in general, there are cases in which D = P (strong duality), e.g., in convex optimization. The constrained (P.. is then essentially equivalent (Du) that can be tackled by solving an unconstrained, penalized problem (minimizing 3 with respect to ø and u), while adapting the weights A; of the penalties (maximizing 33) with respect to A). This is, in fact, the basis of operation of primal-dual constrained optimization algorithms (39) Chapter 5]. The penalties A (u)
that achieve this equivalence, known as Lagrange multipliers, are solutions of (D.,) and subgradients of the perturbation function. Strong duality also holds under the milder Assumption Tand constraint qualification requirement stated next.
Assumption There exist a finite relaxation < and a function & E J such that all constraints are met with margin e > 0, i.e., Ep, (((xx), v) I u4 c, for all =1, 1,...,m.
Note that since can be large, this requirement is mild. We can thus leverage strong duality to provide an alternative definition of the resilient relaxation in 2
Proposition 3. Let X (u) be solution of (D.) for the relaxation u. Under Assumptions / and P*(u") (u()) and any u² T such that Vh(u') X²())) is resilient relaxation of Pu
See appendix D.3 for proof. Whereas Def. [ specifies the resilience relaxation in terms of the marginal performance gains 0P*, Prop. formulates it in terms of the penalties X. Indeed, it establishes that the penalty X ((()) that achieves the resilient relaxation of (P..) is encoded in the relaxation cost Vh(u*). That is not say that / directly weighs the requirements in fixed penalty formulations, since the equilibrium in Prop. aalso depends on the relative difficulty of satisfying those requirements. Though Prop. does not claim that all resilient relaxations satisfy the Lagrange multiplier relation, this holds under additional continuity conditions on (P.) [40).
Prop. 3 already provides more computationally amenable definition of resilient relaxation, given that Lagrange multipliers are often computed while solving (Pu). e.g.. when using primal-dual methods. Yet, even more straightforward formulation of Def. is obtained by rearranging ( as 0 E a(p + (u'),, as did in the proof of Prop. 1 which suggests that u² is related to the minimizers of p+ + h. This is formalized in the following proposition (see proof in appendix D.4).
5

---

2 and only if it is solution of Proposition 4. A relaxation u² satisfies the resilient equilibrium
PR = min +E NERT
B(x.y))D, ((x.))),((eo000 (o(((x))))) + h(u)
(P-RES)
subject to B(x.NDD, (o (0(())) S Wi, Su i 1......,
The corresponding minimizer of is a resilient solution of the functional learning problem
Prop. shows that it is possible to simultancously find a resilient relaxation u² and solve the corresponding resilient learning problem. Indeed, resilient solution of constrained learning problem can be obtained by incorporating the relaxation cost in its objective. This is reminiscent of
first-phase solvers found in interior-point methods used tackle convex optimization problems (39 Chap. 11]. Note, once again, that this is not the same as directly adding the constraints in the objective as penalties or regularizations. Indeed, recall from Def. that the resilient relaxation balances the marginal effects of h on P and not lg. Before using Prop. introduce a practical resilient learning algorithm and its approximation and generalization properties (Sec. 4) we use these equivalent formulations to relate resilient learning to classical learning tasks.
3.3 Relation to Classical Learning Tasks
(Un)constrained learning: Both traditional unconstrained and constrained learning can be seen as limiting cases of resilient learning. Indeed, if h O, u has effect the objective of (P-RSS] We can then take и; = B for = 1...., m. which reduces (P-RES) to an unconstrained learning problem (recall that all losses are [-B, -llluuedd) On the other hand, if h is the indicator function of the non-negative orthant (i.e., hu))) = O for u N 0 and huu) = oc, otherwise), then it must be that u = in (P-RES) as long as this specification satisfy the conditions from Def. [ since they are not componentwise increasing differentiable, respectively. Still, there exists valid relaxation costs that approximate these problems arbitrarily well (see Appendix D.5).
feasible. Neither of these relaxation costs
Penalty- based methods:
Rather than the constrained formulations in (P or requirements are often incorporated directly into the objective of learning tasks using fixed penalties as in
minimize ED, [fo(@(x).))) y)] ΦEF
MED, [((()))
where the fixed > 0 represent the relative importance of the requirements. It is immediate from Prop. 3 that resilient learning with linear relaxation cost h(u) = Σ; You, is equivalent to (4) as long as ED, (e (Ø (x),(xxx))))))> (x).)) v)] 2 O. From Def.) 1 this is the same as fixing the marginal effect of relaxations on the perturbation function.
Soft-margin SVM: Linear relaxation costs are also found soft-margin SVM formulations, namely
minimize BEO, uc Rm
2 |10|| + Σ 44
(PI)
subject to
1 1 --,,00xx0 Ui. i m.
Though written here in its parametrized form, the hypothesis class underlying PI classifiers) is convex. It can therefore be seen an instance of (P-RES) where each loss & represent classification requirement on an individual sample. Soft-margin SVM is therefore a resilient learning problem as opposed to its hard-margin version, where u, 0 for 1, I....,m.
(namely, linear
4 Resilient Constrained Learning Algorithm
We defined the resilient equilibrium u² in (2) and the equivalent resilient learning problems and (P-RES) in the context of the convex functional space J. Contrary to (P.... that are defined on the finite dimensional Fo. these problems are not amenable to numerical solutions. Nevertheless, we have argued that as long as Fo good approximation of F. the values of (P.) and (P.. are close. We use this idea to obtain practical primal-dual algorithm (Alg. I to approximate solutions

---

Algorithm Resilient Constrained Learning (1) Muu nx > 0; p(0)
E e) X (0) RR
for t I:
8 8(t-1)
8nt1 = 8n
V (fo, (Xn,)) Un.)) + + Aeli(Fo. (Xn.)): n I....,N
(00) -ON+1
(4
(t-1) 1/1
(Vi(u(-1)) - \
A 11-1) + 1/1
+ l: 1) (x Un.)) -ug u ) i I,...,m m
end
of (PRRSS (and thus Pu )) The main result of this section (Thm. establishes how good this approximation can be when using only samples from the D,
Explicitly, consider a set N iid. sample pairs (xn,5, yn.s) drawn from D; and define the parametrized, empirical Lagrangian of the resilient learning problem (-RESS as
N
Lo u) = h(u) +
1 N
Σ n=1
(o(fo(Xn.)) Un.u) +
Σ
A
1 N
Σ
(fo(x.))) Un.)) us (5)
1=
The parametrized, empirical dual problem of P-RESS then given by
D
max AER
min QE
Lo u)
(D-RES)
The gap between Dğ and the optimal value PR of the original problem P... can be bounded under the following assumptions.
Assumption 3. The loss functions L, = O... are M-Lipschitz continuous.
Assumption 4 For every e E F, there exists øi E such that Ed, [lo(x) - for (x)1] S v, for
all i .....,m. m. m.
Assumption 5. There exists E(N, 6) 2 0 such that for all i = O...., m and all E e,
Ep, [e](f(x))
(fo(xmm))) Vn.i) $ SE(N6)
N
with probability 1-6 8 over draws of {X )n.,)).
Although the parameterized functional space Fg can be non-convex, as is the case for neural networks, Ass. rssuiress that it is rich in the sense that the distance to its convex hull is bounded. When & exists for all 5 and is decreasing function of N, Ass. (5) describes the familiar uniform convergence from learning theory. Such generalization bounds can be derived based on bounded VC dimension,
Rademacher complexity, or algorithmic stability, to name a few [41]
We can now state the main result of this section, whose proof is provided in Appendix C
Theorem 1. Consider Pa and u² from P-RES) and Dğ from D-RES
Under Ass.
it
holds with probability of (3m + 2)8 that
P D h(u" + 1 MD) - M(n))())))))))))){()))) Mr + (1 +1+ A)E(N,))
(6)
Thm. |suggesss that resilient learning problems can be tackled using D-RES
which can be solved
using saddle point methods, as in Alg. Even if the inner minimization problem is non-convex, dual
ascent methods can be shown to converge as long as its solution can be well approximated using
stochastic gradient descent (88 Thm. 2), as is often the case for overparametrizee NNs [42 44]
more detailed discussion on algorithm can be found in Appendix Next, we showcase its performance and our theoretical results in two learning tasks.
7

---

Numerical Experiments
We now showcase the numerical properties of resilient constrained learning. As illustrative case studies, we consider federated learning under class imbalance and invariance constrained learning. Additional experimental results for both setups are included in Appendix H We also include ablations on the hyperparameters of the method, including dual and perturbation learning rates, and the choice of the perturbation cost function h.
5.1 Heterogeneous Federated Learning
Federated learning 45 entails learning common model in distributed manner by leveraging data samples from different clients. Usually, average performance across all clients is optimized under the assumption that data from different clients is identically distributed. In practice, heterogeneity in local data distributions can lead to uneven performance across clients [7). Since this may be undesirable, sensible requirement in this setting that the loss of the model is similar for all clients.
Let De be the distribution of data pairs for Client c, and Re(So) = [x(xw// [x(So(x) v)] its statistical risk. We denote the average performance R(fe) (1/C) Σ Re(fo). where C' is the number of clients. As proposed in [18] heterogeneity issues can tackled by imposing a proximity constraint between the performance each client Rg. and the loss averaged over all clients R. This leads to the constrained learning problem
min. DEe
R(fe)
(P-FL)
to
- -5 c=
where < > 0 is a small (fixed) positive scalar. It is ready to see that this problem of the form in (P) Appendix [F] Note that the constraint in (P-FD is an asymmetric (and relaxed) version of the equality of error rates common in fairness literature.
As shown by [18] this problem can be solved via a primal-dual approach in a privacy-preserving manner and with a negligible communication overhead, that involves sharing dual variables. However, because the heterogeneity of the data distribution across clients is unknown priori, it can be challenging to specify a single constraint level e for all clients that results in a reasonable trade-off between overall and individual client performance. In addition, the performance of all clients may be significantly reduced by few clients whose poor performance make the constraint hard to satisfy. The heuristic adopted in 18 is to clip dual variables that exceed fixed value.
In contrast, we propose solve resilient version of P.FL by including relaxation Mee c 1..... C' for each constraint and quadratic relaxation cost h ( = al|u/l The resilient version of problem (P-FL.) can also be solved in a privacy preserving manner as long as hu()) separable in each of the constraint perturbations the In that case u, can be updated locally by client c.
Following the setup of [18), heterogeneity across clients is generated through class imbalance. More specifically, samples from different classes are distributed among clients using Dirichlet distribution. Experimental and algorithmic details along with privacy considerations are presented in Appendix |
Constraint relaxation and relative difficulty: Our approach relaxes constraints according to their relative difficulty. In the context of class imbalance, the majority classes exert stronger influence on the overall objective (average performance). Therefore, the overall performance Tł tends to favor smaller losses in the majority classes rather than in the minority ones. As a result, meeting the proximity constraint in (L-FL for clients whose datasets contain higher fraction of training samples from the minority classes can deteriorate performance. In Figure fleft, we demonstrate that the constraint is effectively relaxed more for these clients.
Controlling the performance vs. relaxation trade-off: Through the choice of the relaxation cost function, we can control the trade-off between relaxing the equalization requirements from (P-FL) and performance. To illustrate this, we perform an ablation on the coefficient a the quadratic relaxation cost l1(1 u) = a ai|ul| As sown in Figure middle) smaller values of enable better performance at the cost of larger relaxations. a increases, the relaxations vanish and the problem approaches the original constrained problem. In this manner, the resilient approach enables navigating this trade-off
8

---

Formulition Reallient
Constra nt Violation
Perturbation [ul
Perturbation
0.4-
0.075
0.300
Jub:
0.003
Objective
044
62-
02-
0,000
6.005
0.051
0.022
15
100
1002
Train Split
Minority Class Samples (%)
Relaxation Cost (at
Figure 2: (Left) Constraint relaxation and relative difficulty for federated learning under heteroge- ncous class imbalance across clients (crosses). We plot the perturbation u. against the fraction of the dataset of client e from the minority class, which is associated to how difficult is to satisfy the constraint, since minority classes typically have higher loss. (Middle) Relaxation cost parame- ter (h(u) a | vs. final training loss and perturbation norm. (Right) Constraint violations on train and test sets
by changing a single hyperparameter. Still, the optimal relaxation for each client is determined by their local data distribution, i.e., the relative difficulty of the constraint. In Appendix F.4 we also perform an ablation on the cost function by changing the perturbation norm.
Constraint violation and generalization: Relaxing stringent requirements not only makes the empirical problem casier to solve, but it can also lead to a better empirical approximation of the underlying statistical problem. As shown in Figure right), the resilient approach has a smaller fraction of clients that infeasible the end of training. In addition, when constraints evaluated on the test set, larger constraint violations are observed for some (outlier) clients in the hard constrained approach (u,- 0). In Appendix F.4 we show that this holds across different problem settings. In addition, we also illustrate the fact that this is partly due to generalization issues, i. e., that overly stringent requirements can harm generalization. This observation line with the constrained learning theory developed in
Comparing client performances: Our method should sacrifice the performance of outliers- represent hard to satisfy constraints- in order to benefit the performance the majority of the clients. In order to showcase this, sort clients according to their test accuracy Accp] Acc 2 ... (cc We report the fraction of clients in the resilient method that outperform equally ranked clients
for the constrained baseline [18) (Acefe) 2 Accigra)) ), as well as the average and maximum increases and decreases in performance. As shown in Table [ the majority of clients achieve small increase in performance, while small fraction experiences larger decrease. In Appendix F4 we include
plots of ordered accuracies to further illustrate this.
Dataset
Imbalance Ratio
Improved over constrained (%)
Max Improvement
Max Deterioration
10
77
1.5
10.0
CIFAR10
20
79
2.1
9.1
10
92
4.8
23.3
F-MNIST
20
94
2.6
19.4
Table 1: Changes in accuracy for equally ranked clients for the resilient method compared to the constrained baseline (18). We report the fraction of equally ranked clients which improved their accuracy, along with the mean and maximum change across all clients that improve (imp.) and decrease (dec.) their accuracy, respectively. Performance improves for most clients, although at the cost of decrease in performance for few outliers
5.2 Invariance Constrained Learning
As in 21). we impose a constraint on the loss on transformed inputs, mean of achieving robustness transformations which may describe invariances or symmetries of the data. Explicitly,
min. BE0
Ex [((fo(x).)))
(P-IC)
S. to
B(xx)~
max ((folex),)) v) -c 500 i= 1. 1......m 9EG.

---

Fansfomac.on on Santh Other
Fomu ation
Dual variables (11)
10t
Const nined lent
Porturbation
10"
0.2
10-1
0.0
(100)
More
Sckie
Synthetic
Synthetic
Figure 3: (Left)) Constraint Relaxation and Relative difficulty for Synthetically invariant datasets. Bars denote the perturbation u, associated with different transformations, and the x-axis shows the synthetic invariance of the dataset. (Right) Sensitivity (Dual variables) for Synthetically invariant datasets. Bars correspond to the values of dual variables (for all constraints) at the end of training. We compare the resilient and constrained approach accross different synthetic datasets.
where 9j is a set of transformations g X + X' such as image rotations, scalings, or translations. The constraint can be approximated by sampling augmentations using MCMC methods (see [12 for details). However, is challenging to specify the transformation sets G, and constraint levels e; adequately, since they depend on the invariances of the unknown data distribution and whether the function class is sufficiently expressive to capture these invariances. Therefore, we propose to solve a resilient version of problem (P-IC) using h(u) ai|uu| perturbation cost.
We showease our approach on datasets with artificial invariances. following the setup of [3] Explicitly, we generate the synthetic datasets, by applying either rotations, translations, or scalings, to each sample in the MNIST (48) and FashionMNIST (49) datasets. The transformations are sampled from uniform distributions over the ranges detailed in Appendix H
Constraint relaxation and relative diffiiculy As shown in Figure Beftt the relaxations (u) associ- ated with synthetic invariances are considerably smaller than for other transformations. This indicates that when the transformations in the constraint correspond to a true invariance of the dataset, the constraint is easier to satisfy. On the other hand, when the transformations are not associated with synthetic invariances of the dataset, they are harder to satisfy and thus result in larger relaxations.
This results in smaller dual variables, as shown in Figure (right).
Resilience Improves Performance The resilient approach is able handle the misspecification of invariance requirements, outperforming in terms test accuracy both the constrained and uncon- strained approaches. We include results for MNIST in Table 2 and F-MNIST in Appendix H. In addition, though it was not designed for that purpose, our approach shows similar performance to the invariance learning method Augerino [22].
Dataset
Method
Rotated (180)
Rotated (90)
Translated
Scaled
Original
Augerino
97.78 + 0.03
96.38 0.00
94.65 0.01
97.53 + 0.00
98.44 1 0.00
Unconstrained
94.49 1 0.12
96.25 +: 0.13
94.64
0.20
97.47 + 0.03
98.45 1: 0.06
MNIST
Constrained
94.55 1 0.18
96.90 0.07
93.74 0.07
97.92 1 0.15
98.74 +: 0.08
Resilient
95.38 + 0.18
97.19 0.09
95.21 + 0.15
98.20 - 0.04
98.86 0.02
Table 2: Classification accuracy for synthetically invariant MNIST. We use the same invariance con-
straint level e, 0.1 for all transformations. We include the invariance learning method Augerino [2]
as a baseline.
Conclusion
This paper introduced method to specify learning constraints by balancing the marginal decrease in the objective value obtained from relaxation with the marginal increase relaxation cost. This resilient equilibrium has the effect of prioritizing the relaxation of constraints that harder to satisfy. The paper also determined conditions under which this equilibrium exists and provided an algorithm automatically find it during training, for which approximation and statistical guarantees were derived. Experimental validations showcased the advantages of resilient constrained learning for classification with invariance requirements and federated learning. Future work includes exploring different relaxation costs and applications to robustness against disturbances and outliers.
10

---

Acknowledgments and Disclosure of Funding
The work of A. Ribeiro and Hounie is supported by NSF-Simons MoDI., Award 2031985, NSF Al Institutes program, Award 21 12665, and NSF HDR TRipods Award 1934960. The work of Dr. Chamon is supported by the Deutsche Forschungsgermennshaall (DFG, German Research Foundation) under Germany's 's Excellence Strategy (EXC 2075-390740001).
References
[1] Z. Wan, X. Xia, D. Lo, and G. C. Murphy, "How does machine learning change software development practices?" IEEE Transactions on Software Engineering, vol. 47, no. 9, pp. 1857-1871, 2021.
[2] N. Mehrabi, F. Morstatter, N. Saxena, K. Lerman, and A. Galstyan, "A survey on bias and fairness in machine learning," ACM Computing Surveys (CSUR), vol. 54, no. 6, pp. 1-35, 2021.
[3] S. H. Silva and P. Najafirad, "Opportunities and challenges in deep learning adversarial robust- ness: A survey," arXiv preprint vrXiv:2007.00755 2020.
[4] Q. Yang, T. D. Simão, S. H. Tindemans, and M. 'T. Spaan, "Safety-constraine reinforcement learning with distributional safety critic," Machine Learning, vol. 112, no. 3, pp. 859-887, 2023.
[5] C. Dwork, M. Hardt, T. Pitassi, O. Reingold, and R. Zemel, "Faimess through awareness," in Proceedings of the 3rd innovations in theoretical computer science conference, 2012, pp-
21 214-226.
[6] M. Donini, L. Oneto, S. Ben-David, S. Shawe- Thawer and M. Pontil, "Empirical risk mini- mization under fairness constraints," Advances in neural information processing systems, vol. 31, 2018.
[7] L. Chamon and A. Ribeiro, "Probably approximately correct constrained learning," Advances in Neural Information Processing Systems, vol. 33, 2020.
[8] L. F. Chamon, S. Paternain, M. Calvo-Fullana, and A. Ribeiro, "Constrained learning with non-convex losses," IEEE Transactions on Information Theory, 2022.
[9] S. Paternain, I.. Chamon, M. Calvo-Fullana, and Ribeiro, "Constrained reinforcement learning has zero duality gap," Advances in Neural Information Processing Systems, vol. 32, 2019.
[10] C. Tran, F. Fioretto, and P. Van Hentenryck, "Differentially private and fair deep learning: A lagrangian dual approach," in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 35, no. 11, 2021, pp. 9932-99999999 9939.
[11] F. Fioretto, P. Van Hentenryck, T. W. Mak, C. Tran, F. Baldo, and M. Lombardi. "Lagrangian duality for constrained deep learning," in Machine Learning and Knowledge Discovery in Databases. Applied Data Science and Demo Track: European Conference, ECML PKDD 2020, Ghent, Belgium, September 14-18, 2020, Proceedings, Part Springer, 2021, pp. 118-135.
[12] A. Robey, L. Chamon, G. J. Pappas, H. Hassani, and A. Ribeiro, "Adversarial robustness with semi-infinite constrained learning," Advances in Neural Information Processing Systems, vol. 34,
pp. 6198-6215, 2021.
[13] A. Robey, G. J. Pappas, and H. Hassani, "Model-based domain generalization," Advances in Neural Information Processing Systems, vol. 34, pp. 20 210-20222,, 2021.
[14] E. Diana, W. Gill, M. Kearns, K. Kenthapadi, and A. Roth, "Minimax group fairness: Algorithms and experiments," in Proceedings of the 202/ AAAI/ACM Conference on AI, Ethics, and Society, 2021, pp. 66-76.
[15] Y. Xu. A. Noy, M. Lin, Q. Qian, H. Li, and R. Jin, "Wemix: How to better utilize data augmentation." arXiv preprint arXiv:2010.01260 2020.
[16] L. Peng, P. V. Giampouras, and R. Vidal, "The ideal continual learner: An agent that never forgets," arXiv preprint arXiv:2305.003: 2023.
[17] J. Gallego-Posada. J. Ramirez, A. Erraqabi, Y. Bengio, and S. Lacoste-Julien, "Controlled sparsity via constrained optimization or: How learned to stop tuning penalties and love constraints." 2022. [Online]. Available: https//aarivvorgaa////00444
11

---

[18] Z. Shen, J. Cervino, H. Hassani, and A. Ribeiro, "An agnostic approach to federated learning with class imbalance," in International Conference on Learning Representations, 2022.
[19] T. Nishio and R. Yonetani, "Client selection for federated learning with heterogeneous resources in mobile edge," " in ICC 2019-2019 IEEE international conference on communications (ICC).
IEFE, 2019, pp. 1-7.
[20] F. Yu, W. Zhang, Z. Qin, Z. Xu, D. Wang, C. Liu, Z. Tian, and X. Chen, "Heterogeneous federated learning," " arXiv preprint arXiv:2008.00 06767, 2020.
[21] I. Houmie, L. F. O. Chamon, and A. Ribeiro, "Automatic data augmentation via invariance- constrained learning," ArXiv, vol. abs/2209. 15031, 2022.
[22] G. Benton, M. Finzi, P. Izmailov, and A. G. Wilson, "Learning invariances in neural networks from training data," Advances in Neural Information Processing Systems, vol. 33, pp. 17 605-
17 6766, 2020.
[23] A. Immer, T. F. A. der Ouderaa, V. Fortuin, G. Rätsch, and M. van der Wilk, "Invariance learning in deep neural networks with differentiable laplace approximations," CoRR, vol. abs/2202.10638,, 2022. [Online]. Available: https://arxiv.oo//bbb///000 10638
[24] J. Elenter, N. NaderiAllzzadeh, and A. Ribeiro, "A lagrangian duality approach to active learning," arXiv preprint urXiv:2202.04100 2022.
[25] N. Quadrianto, V. Sharmanska, and O. Thomas, "Discovering fair representations in the data do- main," in Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, 2019, pp. 8227-8236.
[26] S. Baharlouei, M. Nouiehed. A. Beirami, and M. Razaviyayn, "Ry 'enyi fair inference," arXiv preprint arXiv: 1906. /2005, 2019.
[27] S. Jung, D. Lee, T. Park, and T. Moon, "Fair feature distillation for visual recognition," in Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, 2021, pp.
12 1111121 124.
[28] S. Jung, T. Park, S. Chun, and T. Moon, "Re-weighting based group fairness regularization via classwise robust optimization." arXiv preprint WxXiv:2303.00444 2023.
[29] A. Sinha, H. Namkoong, R. Volpi, and J. Duchi, "Certifying some distributional robustness with principled adversarial training," arXiv preprini arXiv: 10571, 2017.
[30] H. Zhang, Y. Yu, Jiao, E. Xing, L. El Ghaoui, and M. Jordan, "Theoretically principled trade-off between robustness and accuracy," in International Conference on Machine Learning. PMLR, 2019, pp. 7472-7482.
[31] A. Agarwal, A. Beygelzimer, M. Dudík, J. Langford, and H. Wallach, "A reductions approach to fair classification," in International Conference on Machine Learning. PMLR, 2018, pp.
60-69.
[32] M. Donini, L. Oneto, S. Ben- Ravid,vid, J. Shawe- Taylor, and M. Pontil, "Empirical risk minimiza- tion under fairness constraints," arXiv preprint arXiv: 1802:v8800008666 2018.
[33] M. Kearns, Neel, A. Roth, and S. Wu, "Preventing faimess gerrymandering: Auditing and learning for subgroup fairness," in International Conference on Machine Learning. PMLR, 2018, pp.
[34] A. Cotter, H. Jiang, M. R. Gupta, S. Wang. T. Narayan, S. You, and K. Sridharan, "Optimization with non- non-differentiable constraints with applications to fairness, recall, churn, and other goals." " Journal of Machine Learning Research, vol. 20, no. 172, pp. 1-59, 2019.
[35] A. Robey, L. Chamon, G. J. Pappas, and H. Hassani, "Probabilistically robust learning: Balancing average and worst-case performance," in Proceedings of the 39th International Conference
Machine Learning, ser. Proceedings of Machine Learning Research, K. Chaudhuri, S. Jegelka, I. Song, C. Szepesvari, G. Niu, and S. Sabato, Eds., vol. 162. PMLR, 17-23 Jul 2022, pp. 18 186-7-18 686. [Online]. Available: https:/prroceedigs..ll press/v wwtress/v112//obbee 162/robe
[36] C. S. Holling, "Resilience and stability of ecological systems," Annual Review of Ecology, Evolution, and Systematics, vol. 4, pp. 1-23, 1973.
[37] "Engineering resilience versus ecological resilience," Engineering within ecological constraints, vol. 31, no. 1996, p. 32, 1996.
12

---

[38] L. F. O. Chamon, S. Paternain, M. Calvo-Fullana, and A. Ribeiro, "Constrained learning with non-convex losses," " IEEE Transactions on Information Theory, vol. 69, no. pp. 1739-1760, 2023.
[39] S. Boyd, S. P. Boyd, and L. Vandenberghe, Convex optimization. Cambridge university press, 2004.
[40] F. Bonnans and A. Shapiro. "Optimization problems with perturbations: A guided tour," SIAM review, vol. 40, no. 2, pp. 228-264, 1998.
[41] M. Mohri, A. Rostamizadeh, and A. Talwalkar, Foundations of machine learning. MIT press, 2018.
[42] R.
and T. Ma, "Learning one-hidden-layer neural networks with landscape design." in International Conference on Learning Representations, 2018.
[43] A. Brutzkus and A. Globerson, "Globally optimal gradient descent for convnet with gaussian inputs," in International Conference on Machine Learning, 2017, pp. 605-61 614.
[44] M. Soltanolkotabi, A. Javanmard, and D. Lee, "Theoretical insights into the optimization landscape of over- wver-parameterized shallow neural networks," IEEE Transactions on Information Theory, vol. 65, no. pp. 742-769, 2018.
[45] R. Shokri and V. Shmatikov, "Privacy-pree preneeving deep learning," in Proceedings of the 22nd ACM SIGSAC conference on computer and commumications security, 2015, pp. 1310-1321.
[46] T. Li, A. K. Sahu, M. Zaheer, M. Sanjabi, A. Talwalkar, and V. Smith, "Federated optimization in heterogeneous networks," Proceedings of Machine learning and systems, vol. 2, pp. 429-4449444 2020.
[47] H. Wang, 7. Kaplan, Niu, and Li, "Optimizing federated learning on non-iid data with rein- forcement learning." in IEEE INFOCOM 2020-IEEE Conference on Computer Communications. IEEE, 2020, pp. (698-1707.
[48] Y. LeCun, C. Cortes, and Burges, "Mnist handwritten digit database," " ATT Labs [Online]. Available: http://yann wwwww.coo//e//////eeeetoe vol. 2, 2010.
[49] H. Xiao, K. Rasul, and R. Vollgraf, "Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms," 2017.
[50] R. T. Rockafellar, Conjugate duality and optimization. SIAM, 1974.
[51] D. P. Bertsekas, "Nonlinear programming," Journal of the Operational Research Society, vol. 48,
no. pp. 334-334, 1997.
[52] D. Bertsekas, Convex optimization theory. Athena Scientific, 2009, vol. 1.
[53] R. T. Rockafellar, Convex analysis. Princeton university press, 1997, vol. 11.
[54] D. P. Kingma and J. Ba, "Adam: A method for stochastic optimization," arXiv preprint
arXiv:1412.6980 2014.
[55] S. Boyd, L. Xiao, and A. Mutapeic, "Subgradient methods," lecture notes of EE392o, Stanford University, Autumn Quarter, vol. 2004, pp. 2004-2005, 2003.
[56] B. MeMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas, "Communication-efficiien learning of deep networks from decentralized data," in Artificial intelligence and statistics. PMLR, 2017, pp. 1273-1282.
[57] X. Zhang, M. Hong, S. Dhople. W. Yin, and Y. Liu, "Fedpd: A federated learning framework with adaptivity to non-iid data," IEEE Transactions on Signal Processing, vol. 69, pp. 6055- 6070, 2020.
[58] D. A. E. Acar, Y. Zhao, R. M. Navarro, M. Mattina, P. N. Whatmough, and V. Saligrama, "Federated learning based on dynamic regularization," arXiv preprint arXiv:21/1.0422 2021.
[59] A. Krizhevsky, "Learning multiple layers of features from tiny images," " Canadian Institute for Advanced Research, Tech. Rep., 2009.
[60] L. Wang, S. Xu, X. Wang, and Q. Zhu. "Addressing class imbalance in federated learning," in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 35, no. 11, 2021, pp.
10 (65-1001 173.
13

---

A Constrained learnability and relaxations
In this section, we illustrate how constraints affect learnability, an issue that can be exacerbated by relaxing their specification either too much or too little. Resilient constrained learning, on the other hand, progressively adapts to the underlying problem, striking a balance between modifying the learning task and improving the objective value that can overcome these issues.
Let us begin by stating what mean by constrained learnability (see (38] Def. 4] for details).
Definition (PACC). A hypothesis class Fe is probably approximately correct constrained (PACC) learnalle with respect to the losses ( if there exists an algorithm that, for every c, (0, 1) and every distribution Dj = O...., m, can obtain fa E Fg using [(c, 6, m) samples from each Dj that is, with probability 1 6,
1) probably approximately optimal, i.e., for P* as in P
(<o -P*| S. and
2) probably approximately feasible, i...
(x (fo (x)) S. for all i 121 1.
(8)
Definition 2 is an extension of the probably approximately correct (PAC) framework from classical learning theory to the problem of learning under requirements. Indeed, note that for unconstrained learning problems [m = 0 in (P)). P - Ep, fu (x), for all E e. In that case, 7 reduces to the classical definition of PAC learnability [41] Def. 2.14]. In general, however, PACC learner must also satisfy the approximate feasibility condition
Constrained learning theory shows that, under mild conditions, the PAC learnability of Fo with respect to each individual loss & implies its PACC learnability (38, Thm. 1J. This does not mean that an empirical version of (P) is a PACC learner, i.e., approximates the value of P In fact, this is typically not the the case.
Case in point, consider the learning problem
P min DE
J(A) & ED.[10
10 x[]
(PII)
subject
[D x] --1. [v0 x] s
where Do is the distribution of
(x. v) ([T, -1) with prob. 1/2
(10
with prob. 1/2
Dj is such that (x, v) = [1, 1). and D2 such that (x, v) = ((-T, , 11, 1), uniformly at random from [0, 1/4] and is drawn uniformly at random from 1-1/2, 1/2). Notice that the Dj are correlated through the random variable r. The parameters 0 = [0i. 02] are taken from the finite set {0", gd, 8d). described below together with their corresponding objective values:
1), where a is drawn
1/32,
da 1/22,
1/16,
0 = 0b [],
J(Ø)
(9)
1/16 + 1/24,
0 0- [1,1/3]
1/8,
0d A [1,0]"
Notice that under these distributions, the constraints in (PII) reduce to 01 < -1 and 02 < 1. Hence,
all parameters expect for [1 1/, 1/2)" are feasible for the statistical (PII. From 9 its optimal value therefore P 1/16 achieved for 0* = 0h.
In the sequel, we will show that (i) the empirical version of (III) [as in (IIII) recovers its solution
with exponentially small probability (Sec. I. (ii) relaxing the empirical problem [as in (PIV) too
little or too much fails to mitigate this issue (Sec. AA.2;; and (iii) a resilient relaxation [as in (VV) allows the empirical version of (PII) to recover its solutions with high probability. In summary, the
empirical counterpart of (PI)) can be relaxed into a PACC learner, but care must be taken when choosing that relaxations.
14

---

A.1 Empirical constrained risk minimization (ECRM)
Consider the empirical version of 9
which can be written as
N
P min I
(0)
0
Xm
N
(PIIT)
n=1
subject to
01 2 1 + 702,
02
S 1 + 501.
where F 1
N Σx=1 Ta is the empirical average of i.d. samples Tn drawn uniformly at random
from [-1/2, 1/2]. Notice that
for 09, the first constraint reduces to 1/2 2 1 + and since F 2 -1/2, it is violated unless 7 0; and
for 08, the constraints read 1 2 1 + 7 and 1 S 1 + F, so that at least one is violated unless F = 0.
Since r is a continuous distribution, f * 0 almost surely. Immediately, we obtain that P 2 Additionally, P: < oo since 0 is always feasible. Hence,
PiIP: P2l S 1/64] = (() P. - 1/64 U j((0)) - P:l 1/64]
s {P(]j(8') P: = 1/64 +
- (()) -(0)) > 1/24 1/64 +1[1)0(0)) .(09) 1/16 1/64
S 0.001.
A.2 Relaxed ECRM
Consider now a relaxation of PIII namely
N
1
P min AE
J(0)
10 Xn
N
(PIV)
subject to 01 2 1 + 702 u1, 02 12 701 + u2-
Problem PIIV) is the empirical version of (P for the relaxation [u1, uz]". Is straightforward to see that if u1, U2 F, then we are in the situation of Sec. A.1 and once again P[IP: P <
1/64 + 0 as
+ 00.
On the other hand, notice that the constraints always hold whenever tn 2 1 F0, 01 and U22 2 02- F01 1:
For 0a, this reduces to We therefore obtain that
2 (F + 1)/2, since u2 2 -(F + 1)/2 is satisfied for all u 2 O.
0 < P < i(0)), for u 2 ++1
2
In this case, recalling that + 0 almost surely yields
P[iP: P 1/64] -()5(()) 1/16 s 1/64 j((0) < j((b) v 5(0 5(0"))
< -P(1_(00) - 1/16| < 1/64].
where we use x V min(x, 3). Using the fact that [(a)) 1/32, we obtain
P[IP: P < 1/64| < TP[ -((0) - 1/32 < 1/64
< ((()(())- - -(80) 2 1 1/64] < 2c 0.00011
For 0², this becomes in 2 7 and جn 2 न. Hence,
++1
j((0) # - < (((8), for 7 $ 2n
and U2 2 7.
2
15

---

Since P. = J(6"), we therefore get
P| - - S 1/64 = - - J(0') & 1/64 J(0)) = j(00) v }(00)] 2 P s J(00) v J(0") P(I((0)) J(00)) 1/64]
Notice that since j(0 concentrates around (() for O for every > 0, there exists No such that [ - J(0)) v ](0d)]
2 - e. We therefore conclude that
P[P: P - 1/64
2 1 - - P1 J(0D) 2 1/64]
> 1 - 2 0.0004.N
In summary, we have that
S 4e 0.0011
U1 U2 <9
7+1
P[P P.l S 1/64
2 1 - 3e N22
i3 u1
and U2 2 7
=
7+1 2
S 2e 0.0001N
2 2
2
A.3 Resilient ECRM
Finally, consider the resilient version of (PII)
||||
P min
j(0) + 2
BEG, HERT
(PV)
subject to
0 2 1 1-1-70g 702 u1. 02 S
701 + 1/2
and let 0= be a solution of (PV). Notice that (PV) is empirical version of the equivalent formulation
in Prop. We consider the value of the problem for each possible element of
For 8 to be feasible, must be that d1 2 (F + 1)/2 (ug, on the other hand, can be 0).
Hence, we have that
P7 - ((0)) + (F +++1 1)²
8
For 8h to be feasible, it must be that d₁ 2 F and U2 2 F. Hence,
P - J j((b) + +
For & to be feasible, it must be that 11 2 F 3 (once again the second constraint need not be relaxed). Hence,
272
P s ((0%) +
9
Finally, 0d feasible for all u E R.. Hence,
P < ((0)..
Putting together these conditions, we obtain that for 0³ to be optimal, i.e., for ((02) - P it must be that
+(0)+++$ (++1)2
27
v(00) + v ((0t)
(10)
8
From the fact that j(0) concentrates around (0) for 0 E O (e.g., by Hoeffding's inequality) and using the values of J from (9), holds that there exists No such that 6¹ is optimal for N 2 N, as long |F| < 0.2. We therefore conclude that
(( PTl < 1/64] > PlOR 0r) 2 P[
S 0.2 > 1 2e -0.88N
16

---

B Convexity of the Perturbation Function for Nonconvex Losses
The definition of resilient equilibrium and all subsequent results in the paper require convexity of the perturbation function (*( defined in P..) This requisite is stated in Assumption |
Assumption 1 is well known to hold if the optimization problem P
is convex, for which it is
12
sufficient for the class JF to be a convex set and the losses to be convex functions (see, e-g., [40). If the problem is not parametric, as is, e.g.. (P), then assuming the hypothesis class F is convex is mild. Consider, e.g., the set F to be the intersection of the space of Dy-measurable functions. Overall, it is not significant restriction assume that the losses are convex since this is the case for typical losses, such as cross entropy and mean squared erro
This convex losses requirement can be relaxed as long as the distributions are well-behaved and the hypothesis class JF is rich enough. We define these conditions in two technical assumptions. In what follows, we consider the distributions Dj are defined over the same probability space ( x P,) for the sigma-algebra Σ and the measures P,.
Assumption 6 (Non-atomic distributions). The set V is finite and the conditional random vari- ables x y induced by the D; measures are non atomic... That is, for every measurable event Z E E with strictly positive conditional measure IP xx (Z) > O, there exist event Σ a Z' C Z strictly included in Z with positive conditional measure màl' ( > O.
Assumption 7 (Decomposable hypothesis class). The set JF is decomposable in the sense that for all pair of functions 11 Ø2 E FF and all measurable set Z E Σ, it holds that ő E F for
[0i(x), x x x(x) = -0-1122e (2)
2 Z
Assumption O requires data probability distributions in which all points have zero measure. Assump- tion 7 requires hypothesis classes that are closed under "cutting and stitching" of functions.
In turns out that Assumptions G 7 are enough to guarantee that the perturbation function is convex. In particular, they imply the following result (38] Lemma A.1].
Lemma 1. Define the cost constraint epigraph of Pu)) be the set
C = [[ E m=++
36 F such that ED, ((((((x), w) 8; ==:0...... o,...,
(11)
Under Assumptions 0 andd the set is convex.
Notice that Lemma does not require the losses & to be convex for the cost-constraint epigraph to be convex. This a significant fact since implies that the perturbation function of P is also convex, as we show next.
Proposition 5. Consider the perturbation function (*( defined in Under Assumptions and 7
P (u) is convex.
Proof. Let v and w be two perturbations of P. and define the convex combination perturbation
u. = ov + (1 - a)w for some a E [0, 1]. To prove that p=(u) is convex we need to show that P*(u,) - a (v) + (1 - a)P (w) for all a.
either v or w yield infcasible problems we have P*(v) = xo or P*(w) = oc. In this case, P*(u,)) S aP*(v) + (1 - a)Px(w) = oc. In the more interesting case where v and w both yield feasible problems, we have that
P [V(vv) and (P((w:: EC.
(12)
for C defined in [... Indeed, any of that solves (P.) must satisfy ED, (x)()) v)1 S u, for i and ED. (o x) v)) = Pv()). Likewise for a function oi that solves (w
>
Under Assumptions 6 and we can combine (12) and Lemma to get that
(v): - (1 I)
w| EC for all E [0.
(13)
It is only when dealing with the parametrized Fo that the composition of the parametrization with the loss may lead to convex function of the decision variable 0.
17

---

For this to hold, the definition of C in implies that there exists function da E F such that
E [eu((o - ap (v) + (1- (1-a)P" a)) and IE
(14a)
I au; + (1 a)w, for i m...,
(14b)
From (14b) we obtain that da is feasible for u. implies that
Hence, it is suboptimal solution of Up
which
p*(u.) S ([(o((a(x))))))) S aP*((v) + aw))"
(15)
thus concluding the proof.
Proposition shows that the perturbation function P*(u) can be convex even when PP is defined based on non-convex losses. In the context of resilient learning, this is important because it allows us to quantify the variations the perturbation function, which the basis for the resilient equilibrium from Def.
The convexity of the perturbation function (*(u) also relevant because, under a constraint qualifi- cation such the one stated in Assumption 2 it implies that the optimization problem is strongly
dual. We encapsulate this result in the next lemma since will be used subsequent derivations.
Lemma 2.
Suppose (*( associated to P m is convex (Assumption and there exists & F
strictly feasible for Pol (Assumption Then, strong duality holds for i.e. P D
Proof. The result follows from 50 Thm. 15] since the constraint qualification in Assumption
implies that P* is lower semi-continuous 50 Thm. 18(a)], i.e., that its epigraph is closed 51 Prop. 1.1.2].
C Proof of Thm.
The proof is divided in three steps that transform the resilient functional dual problem PRRES) into the resilient, parametrized, empirical dual problem D-RES). Explicitly. define the Lagrangian of (P-RES) as
LR(a, u) ED, [lo(0(x),))) + h(u)
A ED, [4((x)))) us
(16)
and its dual problem as
D
min XER 6EF, DERT
La (2( u).
(D-RES)
First, from lemma 2 we have that if assumption dual, i.e., P D
I and assumption 2 hold then the problem is strongly
Then, to relate (D-RES) to its parametrized, emprricaa version D-RES by Fg. Explicitly, we consider the difference between Pj and
we begin by approximating F
D = max XERT
min BEE, uER
LR( u).
(D
This difference, which we call the approximation error, is bounded in the following proposition: Proposition 6. Under Assumptions
2 holds that
P < D < P h(u" +1 MD) - h((u)()) + Mv,
(17)
for PR and u² as in P-RES and Dj as in DD-RESS
The proof of Prop. c deferred Sec. C.I We proceed by replacing the expectations in DE-RES
by empirical averages, leading to generalization error bounded as follows:
18

---

Proposition 7. Let D be the value of the parametrized dual problem DE-RES) achieved for Lagrange multiplier X and D2 be the value of the empirical, parametrized dual problem (DRESS)
achieved for a Lagrange multiplier X² Under Assumption ( it holds that
D - D2l - (1 + ()N,6))
(18)
with probability 2(m + 1)6, where A = max (1) |l1, 1|*1)))-
Combining the results in Prop. and using the triangle inequality yields (6) and concludes the proof of Thm.
A proof can be found in Sec. co
C.1 Bounding the parametrization error: proof of Prop. 6
The lower bound stems directly from the definition the dual problem in DD-RES Indeed, is immediate that
D
min (n A; for all E IR 8EB, uE
(19)
In particular, we can write
19 holds for a solution A of the resilient functional dual problem D-RES
Explicitly,
D 2 min uERT
LR(fo. ;u)
Since Fo S F, it follows that
D
min uER!
(R. X
min (R X D2 P
(20)
$EF, uERT
The upper bound is obtained by relating the parameterized dual problem (Dy-RES) version of (P-RES) Start by adding and subtracting Lx(Ø, u) in (16) from the objective of the parametrized dual problem RDES to get
tightened
LR(Fo, x; u) Ln u; + [i x: u) Ln(d, Auj]
iR(0. x u) + ED [lo(ff()) v) -o(())))))))))()).).))))))))))))
(21)
ABD, [c((Jo(x),)) (<(0(x)
where the relaxations u, and relaxation costs h(u) canceled out. To proceed, use the Lipschitz continuity of the losses (Assumption 3) to bound the expected loss difference as
ED, (c(o ((((()),)) < ED, [|e (((()))))))) [=(((()),))]
< MED. [lfo ((x)]]. for i o,...,m.
We can then bound (1 as
Σ \/ |
m
in Au S in(o, M (1+11))
max ic (0.....))
ED, [1oo +(x)
(22)
i=1
Minimizing 22 over 0 yields
Ep, [1fo [(<01]]
min Tn ix A; + M 1 8EB
Σ 1=1
A
min max EE0 ie (o......
(23)
However, from the e-approximation property of the parametrization (Assumption for every & F there exists E such that ED, [1fo x(x)]] < v, for i = =,...., m. Hence, 23 simplifies to
min T A; S T, A; + (1 Σ N Mv. BE0
(24)
Notice that 24) holds uniformly over & E F. Additionally, since the left-hand side does not depend on o. minimizing it over u and then maximizing with respect to À recover the dual value from Da-RES) We immediately obtain the upper bound
m
D < max min XER" dEF, uER"
in(ó, A; + 1+ Σ A
MR.
(25)
1=1
19

---

Expanding Lg and rearranging the terms in 25 we recognize the Lagrangian of a perturbed version of (PRES)) namely
Pire
min NE UERT
Ex (o(0(x),))) v)] + h((u) + MM
(PVI)
subject to B (o(x))))) w) Su MV, i= 1=
Hence, the right-hand side of
25 is the dual problem of (PVI). Since (PVI) is strongly dual (from
lemma 2). obtain that Dž I Pār-- To bound P note that
construct feasible pair
for (PVI) from any pair (ø u²) that solves the resilient functional learning problem PP-EES.
Explicitly, observe that the pair (Ø²", ,0*,"" + D. Mv) is a (suboptimal) feasible point of (PVI). Thus,
D < PM S ED (x)))(x),))) + h(u" + Mu) M
(26)
I Pk h(u') h(u' + -M) Mv
Combining 220 and 26 concludes the proof.
C.2
Bounding the generalization error: Proof of Prop.
Let A and A be solution pairs of DD-RES)) and D-RES respectively and consider the sets of dual minimizers
M(A) = argmin Ln u) and M(A) = argmin Lo u) uER,
0E@, uER"
Note that member of these set are pairs (0, u). Since X maximizes the minimum (with re- spect to 0 and u) of the empirical Lagrangian in (5). it holds that minsee, uER" Lo x); 2 mingge, uERT (0, u) for all A E RT. In particular,
Dj - Dj min Ln(fo. X' min Lo Ai OEe, uERm
o MERT
< min LR(fe. x² 0EO, HER
min OEO, NERT
(0 u))
Since (Ōt,at) M(x*) is suboptimal for i. (So; u²) get
Dj - D < iu(Jar X² (²)= - (ot út).
Using similar argument yields
D D in &t:ut) Lot )z;ut)
for (ot, ,ut) M(²+). We thus obtain
[ - Dğl S max {
[IR[far x+; - X;; [R (;;))) Lo (
Lo -
(27)
Using the uniform convergence bound from Assumption
5
we obtain that
m
[m(ff, (o, A: u) s E(N, +
Σ XEENN [AII))(N,,) 8), (28)
holds uniformly over 0 with probability 1 - (m + 1)6. Combining 27 with (88 using the union bound concludes the proof.
D Proofs from Main Text
D.1 Proof of Proposition T
Proof. [Existence] To show there exists u² HR satisfying Def. T notice that 2 is equivalent to
showing that there exists u² such that af(u)) for (uu P*(u) + h(u). Notice that f is convex function, so that its subgradient is well-defined [see []].
20

---

Start by noticing that the set of minimizers of f is not empty. Explicitly, let Ut* = argmin f(u).
Observe that since the losses (; are bounded, P^(u) P*(v) for all v ž û = B 1. Immediately, we obtain that [(vv is a componentwise increasing function for v ž u, which implies that U argminuea f(u), where U = {u ET < u}. Since U is compact and is convex, its set of
minimizers 2t" is compact and non-empty [51 Prop. B.10(b)].
For all u' E int( where int (2) denotes the interior of the set 2, it must be that 0 E Of( 52 Prop. 5.4.7J. This is simply a statement of the first-order optimality condition for u'.
Suppose, now, that Lt* has no interior and that for all u' E 44", |u'] = 0 for some j. Then, could be that for all p (f('') are such that [p]j 0. However, this would lead to a contradiction. Indeed, since h is normalized, it holds that [Vh(u')];
0, so that 0f(u') = OP* (u'(''. Thus, all p E (u')) are such that [p], > 0, then all p E @P*(u') are such that [p], > 0. From the convexity of P* this would imply that Pr(u' + + 2 P*(u") + [pl; > P*(u'), where o₁ is the j-th element of the canonical basis. This contradicts the fact that P* is componentwise non-increasing. must therefore be that E af('').
[Unicity] If h is strictly convex, then f is strictly convex. Then, its minimizer is unique (53 Chap. 27J, i.c., 21 is a singleton. Suppose there exists u' & Ut that satisfies the equilibrium in Def. Then, from (2) it holds that 0 E 0f(u') Since f is convex, this implies that u' is minimizer, which violates the hypothesis that not in"
D.2 Proposition 2
Proof. From the definition of sub-differential, holds for any Pv (v)(v) and Pw E (w)(w) that
(*(v) > P'(w) + PT (v w)
(29)
P P'(w) 2 P (v) p (w v)
(30)
Adding (29) and 30
we can rearrange the terms to get
0 0 (p. -P P=) (w
(31)
Then, since v; u; > 0ff jj j and 0 otherwise, (31 implies that [pel] [P I 0, which yields the desired result. Applying the same argument for h concludes the proof.
D.3
Proposition
Proof. The strong duality of (P-RES) under assumptions 1 and holds due to Lemma 2 The proof then follows the same steps used to prove that optimal Lagrange multipliers are subgradients of the dual function in convex problems; see, e.g., [39 Section 5.6.2). We just verify that the proof holds despite the non-convexity of the problem as long as the problem is strongly dual.
By definition of the dual function we can write
P (u) = D' (u( u)) min <( (u)): s < (c(0,\(u):u) ai
(32)
where the inequality is true for any function Φb We particularize this inequality to function o' d'v:v that attains the minimum of (Pu. for relaxation v. We can therefore write
P*(u) < c ((v). (u)
(33)
We now substitute the definition of the Lagrangian (3) for the right hand side of (33) write
m (u) ED, [e<(0= (x; v).
(*(u) Eo (x;0((x;));
Σ
(x(00((x)))
24
(34)
The important property to observe in 344 p that we consider perturbation u and corresponding dual variable X" (u) while evaluating the Lagrangian at the function o* (xx v) that is primal optimal for perturbation v. This latter fact implics that the following equality and inequalities are true
ED. [o (x; v) (v)),, ED. (1 (x:
v), (x:v), S Us.
(35)
21

---

Using the relationships in
35 and (3 we conclude that
P (u) & (*(v) + Σ A5()) us
(36)
The two sums in the right hand side of (36) equal the inner product of multiplier X (u( with (v - u).
Implementing this substitution in (36) and reordering terms yields
P*(v) P*(u) X
(37)
Comparing (37 with I we see that X (u) satisfies Definition
D.4 Proposition
Proof. As we did in the proof of Prop. P*(u) h(u). Explicitly,
| we begin by showing that u is minimizer of (p* (h*+h)(u)) =
u" E argmin (P* + ()) uER
(P-RES')
As shown in proposition 1 u' minimizes P* + h iff 0(P + h)()). Then 0 E a(p* h)()))
also equivalent to the resilient equilibrium definition (2).
In P the function P (u) is defined as the solution of (Pn). show that PRRESS and P-RES) are equivalent nested minimization over variables Φ and u1 is equivalent to joint minimization over and u. To confirm that this holds here recall the definition of u* as the resilient relaxation and of
6 (x; u) as the minimizer of the relaxed problem (P.) which holds for all u and u² in particular. Since u² is the solution of (PRESS' We therefore have that for all perturbations u
B(x.))>D Ca(s (x; u)) >((u)) < B(X.)) (o(0 (x; + h(u).
(38)
Further observe that o² (x;; u) is the minimizer of the relaxed problem (P associated with perturba- tion u. We then have that for any feasible function e we must have
E (x.a)) lo(d" (x; u), u) + h(u) s E( [eo(((x)))))) + h(u).
(39)
The bound in (39) is true for all and u. In particular, it is true for the solution d', u of P-RES
Particularizing (39 to this pair and combining the resulting inequality with the bound in conclude that
38 we
B( Coll" (x; u'), h(uu) S (xx))) (eol0 (x), 8)] + h(u").
(40)
On the other hand, given that σ², u solve P-RES we have that for all feasible and ø
B(x,)>D, (x). hu(")) s (x (o(((x).)) w) + M(u).
(41)
In particular, this is true if we make 11 = u² and = x (x; We can then write,
B(xa)>Do lo(0 (x)) + h(un)( < E (x.))~Do lolo ,.)v)) v)
+ hhuu))
(42)
For 40 and to hold we must have that oz, solution of P-RES if and only if u² and are resilient perturbation and corresponding resilient minimizer.
D.5 Proposition
g
Proposition 8. Let x- = argmin ((x,)) (o( ut), w. denote the solution set of the unconstrained problem and b; min E( (x(0(x; u²) w)) i = 1.... m be the min- imum constraint losses achieved. We show there exists costs such that us S and ot 2 - for 1,..., M.
22

---

Proof.
First, we will show sufficient conditions for u 3 l and u > Ic, in terms of ap. and Vh evaluated at Le and b Ic, respectively. For any ET the strong duality of P (lemma implies that @P*(w) is non empty and bounded. Also, the convexity of P* (assumption I implies that for all Pu E OP*(u) and Pu- E @P*((") by (31 from proposition
(3) holds that
Pu- - Pui u² - u) 2
(43)
Analogously, due to the convexity of we have that
Vh(u') Vh(u), u² -u)
(44)
Adding (43) and 44 we obtain
[Pu + Vh(u")] [Pu Vh(u)), u² u 20
(45)
45
holds for any Pu E OP*(u"). Since u* achieves the resilient equilibrium, by definition Vh(u") Pur E @P*(u"), which implies that for all Pu (P*(u)
Pu + Vh(u)) u' 0
(46)
Finally, by choosing particular values of u in 46 we obtain the desired conditions.
(u* < Ile): Letting
446 implies that if there exists
P1c E @1*(1e) such that P(tc) + h(1c) > 0 then u* = 1c.
(47)
(u" > 1b- 1e): Letting b 1e, (46) implies that if there exists
P(b-1c)+ . 1) such that P(b-1c)+ + +(((- - Ile+)) x then u² 2 (b- - lle)+
(48)
Let h(u) al u 123 a R.,, which has Vh(u) 2cc.. We will now show that there exist
coefficients ā and such that the associated costs and h satisfy the conditions (4) and (48
(h): Let pee then
Vb(lc,, = 2ge > P-Peels for all í = 1....,m
which implies that h satisfies (47) and thus u² = 1c.
11 2(b
(h): Let ā min;
then
Vh((b 1c)+); = 20(u; - 6) < [Pi(b.-o): for all i == 1,...,. m
which implies that ho satisfies (48 and thus ü* > b 1e. Since the definition of b and ensures that (-ob-11),k
min;
there exists ā 0 that satisfies the above condition.
2(b,-4
E Primal and Dual Updates
In section introduced the unconstrained problem (D-RES) problem (P as the saddle point of the empirical Lagrangian Lg:
that approximates our original
m
N
(o, huu)
Σ (o(]f(Xnn.o) vn.o)
Σ
((Jo((x))) us (49) N
Σ
As described in Algorithm 1 he saddle point can be obtained by alternating the minimization and the maximization the Lagrangian with respect to the primal variables and dual variables respectively. We now describe the updates of both primal and dual variables in greater detail. For clarity,
23

---

describe the updates using gradient descent and sub-grut gradient ascent for primal and dual variables, respectively. However, nothing precludes our method from using other optimization algorithms, such as Adam [4 or SGD with nesterov momentum.
The optimization is done via gradient descent and and stochastic gradient descent for the primal variables
((++1) = 0(() 1)dd
(50)
u (1+1) u0 nud
and stochastic subgradient ascent for the dual variables
( = (4) + nxx
(51)
In order to obtain the gradients of the Lagrangian with respect to the primal variables, observe that the minimization of the Lagrangian can be separated into two parts that each depend only one primal variable.
É A, u) Lo A) + Lu(A,u)
(52)
where (0, A) = L(o and Éu u) is
L, u) = h(u) Au.
(53)
The gradient with respect to u is obtained from (53
du ac(X, u)
= Vh(u) X
(54)
Ou
Solving for the optimal 0 is similar to solving regularized empirical risk minimization problem. The gradient with respect to 9 is estimated from L(0,, A; using minibatch of B samples
1 B
do
= Σ B n=
(olooSo(xx)) vn) + Σ Vole(Jo(xx)).n)
(55)
The constraints evaluated at the optimal Lagrangian minimizers are supergradients of the corre- sponding Lagrange multipliers [55]. In the same manner, stochastic supergradient ascent done by updating the dual variable À with the super-gradient estimated using a batch of B samples.
A
4(fo(xn). u, 1 B Σ
(56)
F Heterogenous Federated Learning Experiments
F.1 Formulation
In this section, we show that the constrained problem P-FL can be re-written as constrained learning problem of the form of P and then introduce its resilient version,
Let D, be the distribution of data pairs for Client i, and R,(fo) = Ex (x). its statistical risk. We denote the average performance as R(fe) == (1/0) (fo). where C is the number of clients. As proposed in (18) heterogeneity issues in federated learning can be tackled by imposing proximity constraint between the performance of each client R,, and the loss averaged over all clients R. This leads the constrained learning problem:
min
R((()
(P-FL)
BEE
s. to
Re(fo) R(fo) 5
1=
where the number of clients and D, the distribution of data pairs for client i, and is a small (fixed) positive scalar.
In order show that problem P-LL can be re-written as a constrained learning problem of the form of P we introduce random variable uniformly distributed over client indices (1...., C).i.e.
P(c = i) for all i = 1, 1....,C
C
24

---

Then, we construct mixture distribution D for data pairs such that
(x, u)|c = i ~ Dj.
Then we-write the average risk R(fe) as the expected loss under D:
ESs (e((((()))
Ro [((Fo(x),
(so),
where the first inequality holds by law of total expectation.
Let & ((o(x))))) = (cT(c- = i) - 1)8(Jo(x))))) e, where 1(c = i) is the indicator function for client i.
In the same manner, we re-write the i th constraint R₂(Se) -R((Je) the expectation of the loss l, under D;:
Es (5((ff(x))))) ED. [e(fo(x), - Σ 0 ED, [((fo(x).
R,(fo) - -((o)) -c
Then, we can re-write
P-FL as
min p*
F [()(()))))
8E0
(PC-FL')
subject to
Ep ((f((x),, v) 50, i= I,..,,m
which is in the form As motivated in section
5.1 we then propose to solve the resilient version of (P-FL
p min
R(fo) h(u)
(PR-FL)
8c0
E(x,)) [((f((x)))) R(So) - S u1; i i= 1....,C.
In the next section we derive the primal dual algorithm that enables us to tackle (PR-FL. in distributed, privacy preserving manner.
F22 Resilient FL Algorithm
this section we show that the resilient problem (R-FFL) can be tackled a distributed and privacy preserving manner, as long as h is additively separable in in each component. Explicitly, we assume that
huu) = Σ (u,)
which holds for the quadratic cost used throughout the experimental section. We thus derive distributed version of the resilient primal-dual algorithm presented in Section 4 (A (Algorithm
We begin by writing the empirical Lagrangian associated to problem (PR-FL
C
( u)) +
Σ
((fo(Xx.).B0.)
(57)
N
N
+ A
le(So (Xnx) D, Un.)]
(58)
N
m1=11
C
N:
Σ C
(1 + Ao -x) N
[e(fo(xm.) Aou; + (,()))
(59)
m=1
25

---

with x=
1 x EE A/-
Note that in (59) we have used the assumption that the perturbation cost is additively separable. This enables us to update the perturbation for each client locally, and thus the resilient formulation does not incurr in any additional communication costs (with respect to the constrained problem in (18). That is, clients do not need to communicate u, during optimisation. The server need only compute and communicate all clients the average dual variable À and the average loss R(fe). Therefore, Homomorphic Encryption techniques can be leveraged to compute these averages without revealing the values of individual dual variables X; and local losses to the server. the same manner, Homomorphic Eneryption could be used to aggregate the relaxation cost huu) = E' (u,) at the server without loss of privacy.
0 update. For a fixed and u, the minimization of L with respect is equivalent to a re-weighted version of the standard unconstrained FL objective:
1 (1+ -
1
min L(0, A, u) 0E0
min o C
Σ [((fo(xm.)) N.
Therefore, 0 can be updated using any FL solver. We thus refer the update on @ as a subroutine ClientUpdate ([w.))=1,0) 0*) 0t+1, which can be implemented using, for example FedAVG [56) or FedPD 57
C
update. For a fixed and the minimization of & with respect to u is can be carried independently by each client, since the objective is additively separable:
min C(0, A. u) uet
min
xmna + hu,
We can thus employ gradient descent (or any other optimization algorithm) locally each client. update. For fixed perturbation u and model 0, we perform dual update on À by taking dual ascent steps of the following equivalent objective,
A(
A
[((f((x.)) vn. - u n1=1
AERN
A
C
N
If server then computes and communicates the average of the client's 's losses R()( the updates to each multiplier X; can be made locally by each client as in 56
As stated before, these update steps can be applied in alternated manner find solution of the empirical dual problem, as as described in Algorithm
Algorithm 2 Resilient Federated Learning
Initialize (0)). ((). u(0), and 0 < 17 < 1.
for t l.... Compute weights: for alli E [N], w. = 1 + A, - A, with Ā = N EiE As;
Theta Update: 8¹ + ClientUpdate [ 0C-11
Perturbation Update: ut) ju:(t - 1) nudu, (t 1)]+
Dual Update: Ax(t)= A,(t 1) + n
N. Ein ((fo(x)) wz) -u,( - [D]]]
1
end
F.3
Experimental Setup
As in (18) we create hetereogeneity between clients through class imbalance. Unless stated other- wise, we use three minority classes (Class Labels (0. 2, 4)), and simulate the phenomenon of class imbalance by keeping only p = 10% of the data data belonging to the minority classes in the training set.
26

---

We follow the implementation from [58] in which Dirichlet prior (over the ten classes) is sampled independently for each client. One client at time, we sample without replacement according each client's prior. Once class runs out of samples, the subsequent clients do not own samples of that class.
We also create test set for each client with the same class balance as the train set. Test sets are then sampled without replacement for each client (but with replacement among different clients, i.e., test sets overlap accross clients).
We the small neural network architecture as in [18 58). Namely, CNN model consisting of 2 convolutional layers with 645 x 5 filters followed by fully connected layers with 384 and 192 neurons. For both the constrained and resilient formulations, use FedAVG [56] to update 6, using 5 communication rounds for each primal update, as in 18
In all experiments we use 100 clients, and all clients participate from each communication round. We run 500 communication rounds in total. We set < 0.1, dual learning rate `ix 0.1, local learning rate 7e 5 10-2 and use data augmentation in all experiments. In the resilient learning formulation, unless stated otherwise, we use a quadratic penalty on the perturbation huu) = ||u]] and perturbation learning rate Tuu 0.1.
All of the plots in section correspond to CIFARIO 59 Results for FashionMNIST 49 can be found on F.4.4
F.4
Additional Results
F,4.1
Performance Relaxation trade off.
As we have already shown, through the choice the relaxation cost function, we can control the trade- off between relaxing requirements and performance. Figure 4 shows that changing the ablation the coefficient a in the quadratic relaxation cost huu) = a ||u [ not only results in larger relaxations, but that these larger relaxations effectively lead to clients with higher losses.
0.16
X
0.060
0.14
Worst Client Loss (constraint)
x
Mean Client Loss (objective)
0.12
0.058
X
0.10
Worst
0.08
X
Mean
0.056
0.06
x
0.04
0.054
0.02
X
2
4
10
20
40
100 1000
Relaxation Cost (a)
Figure 4: Train loss for the worst client and averaged over all clients for different values of the perturbation cost coefficient a.
F.4.2 Sensitivity to Problem Specification
The resilient approach is less sensitive the specification of the constraints. Dual variables indicate the sensitivity of the objective with respect to constraint perturbations. As shown by Figure the resilient approach yields smaller dual variables, irespectively of the tolerance in the constraint specification. In this context, setting the constraint levels a priori requires knowledge about the heterogeneity the client local distributions, which in our setup depends on the imbalance of dataset. As shown by figure 6 the resilient approach yields smaller dual variables, irrespectively of the tolerance irrespectively of the percentage of samples of minority classes that are kept, whereas the dual variables grow for more imbalanced and thus harder to satisfy scenarios.
27

---

Formul ation
Constrained
Resi leen
2-
0.002
Figure 5: Dual variables after training with respect to constraint specification
1-
Minority Class Samples (%)
Figure 6: Dual variables at the end of training with respect to the percentage of minority samples kept dataset. Smaller p means more imbalance, and thus results harder to satisfy requirements.
F.4.3 Constraint violation across setups.
Relaxing stringent requirements not only makes the empirical problem easier to solve, but it can also lead to a better empirical approximation of the underlying statistical problem. That is, overly stringent requirements can result not only in large dual variables, but can also harm generalization. showss that more stringent constraint specifications can lead to poor constraint satisfaction in the test set. This improvement constraint satisfaction is associated with smaller generalization gaps for the constraints were observed for the resilient approach, as shown in Figure
E.4.4 Test Accuracy.
In this section we aim to give quantitative performance metrics. We include a constrained baseline 18 and another method for federated learning under class imbalance (60) for comparison.
We first compare approaches in terms the objective, by averaging the test accuracy over clients. As shown in Table the average accuracy of the resilient approach is overall similar to the constrained approach and the baseline [60].
In order to asses how the distribution o performance among clients varies we also report spread metrics for the test accuracy across clients. As shown in Table Resilient learning has (generally) less spread in the interquartile range and higher maximum spread than its constrained counterpart.
E.4.5 Comparing client performances
We sort clients according to their test accuracy Acc[1] Accpi 2 ... Acc We plot the accuracy of equally ranked clients for the constrained baseline
(Acc res 2 Acc const As shown in Figures TO in all setups the majority clients achieve small increase performance, while small fraction experiences a larger decrease. For higher imbalance ratios, this is more pronounced.
18
28

---

Constraint Violation (Test)
1,00
Formulation Constrained
Constraint Violation (Test)
0.8
Resillent
0.6-
0.25
-0.2
-0.50
0.4
0.002
0.02
30
Minority Class Samples (%)
Figure 7: Constraint violation (evaluated no the test set) for Resilient and constrained learning using
different (left) constraint specifications e, and (right) fraction of minority classes.
Largest Constraint Generalization error
0.6
-
0.2
0.002
0.02
0.2
Figure 8: Largest generalization error across clients for different constraint specifications e.
F5 Ablation on perturbation cost function h.
In all experiments, we have used quadratic perturbation cost function h = al|ull In order to assess the impact of the choice of cost the function, we rum our algorithm using cost [|w]]s with 3 = 1, 4, oc, for fashion MNIST in both the federated and invariant setting.
As shown in Table both the mean and spread statistics similar for 1, 4. i.e. our approach is not overly sensitive to the choice of cost function in this experimental setup. However, 3 = oo does show substantially different behaviour. Penalizing the only the largest perturbation results in smaller range while attaining a higher IQR and lower mean accuracy. That is, it reduces the worst client test accuracy, but the performance of most clients deteriorates. both in terms of its average and spread. The infinity norm is related to Rawlsian (i.c. minimax) formulations which have been proposed in the context of fairness see e.g. 14
G Ablation on dual and resilient learning rates
We also perform an ablation on The 7A, the perturbation and dual learning rates, over small grid of 12 values. In this particular setup, we find that the performance of the algorithm is not overly sensitive this choice. We also observe that that the rates that were used in the paper (1), 0.1, 7/> 2) are not optimal in this case, and thus further improvements in performance could be obtained through
Dataset
Imb. Ratio
Mean
IQR
Range 18
[60
[18
Ours
660
[18]
Ours
60
Ours
10
92.5
92.6
93.4
2.2
3.5
2.4
64.1
28.6
50.6
F-NNIST
20
94
93.8
94.4
2.2
2.7
1.7
50.2
28.6
45.8
10
81.3
81.5
81.5
8.1
8.7
8.7
49.4
35.8
46.4
CIFAR10
20
83.4
82.4
82.6
8.6
8.4
7.9
44.5
32
41.1
Table 3: Client accuracy spread metrics for different setups. IQR denotes interquantile range and
range denotes the maximum minus the minimum accuracy, both computed across 100 clients.
29

---

CIFARIO, imbalance Ralio:10
GIAR1O, Imbalance Ralio-20
70
restiant
reslient
constrained
constrained
imprvvement
imprevement
100
20
100
Figure 9: Test Accuracy for equally ranked clients for the resilient and constrained baseline 18 in CIFARIO.
FASHION-NVER
100
90
restient
resilient
improvement
Improvement
50
40
60
100
20
40
60
100
Figure 10: Test Accuracy for equally ranked clients for the resilient and constrained baseline 18 in CIFAR10.
more extensive hyperparameter tuning. However, the main aim of our numerical experiments is to validate empirically the properties our approach.
H Invariance Constrained Learning Experiments
H.1 Experimental setup.
We showcase our approach on datasets with artificial invariances, following the setup of 23 Explicitly, we generate the synthetic datasets, by applying either rotations, translations or scalings, to each sample in the MNIST (48) and FashionMNIST [49] datasets. The transformations are sampled from uniform distributions
the ranges detailed in Table We the same MLP and CNN architectures and hyperparameters as [23]. except that we use only 6 augmentations per sample instead of 31 during training.
For each transformation set (rotations, translations and scalings), we constraint the expected loss over samples augmented with the transformations sampled from uniform distributions over the ranges detailed in Table 7 Note that there is a mismatch between the distribution used to generate the
Mean Acc.
IQR
Max Range
1.0
93.3
2.5
49.5
2.0
93.4
2,4
50.6
4.0
93.4
2.6
45.6
0C
92.7
3.8
28.1
Table 4: Cost function ablation for the heterogeneous federated learning in MushiOn-MNIST using 100 clients, minority classes, an imbalance ratio of 10 and dirichlet allocation with parameter d = 0.3. We report the mean, interquartile range and range (maximum value minus minimum value) test accuracy across clients.
30

---

Tu MI
0.1
0.5
0.1
81.4
81.6
81.8
81.8
0.5
81.4
80.9
81.4
81.1
81.6
81.6
81.6
81.7
Table 5: Dual and resilient learning rate ablation in Heterogenous federated learning setting. We report mean Test Accuracy for CIFARI00 using 100 clients, 3 minority classes, an imbalance ratio of = 10 and dirichlet allocation with parameter d = 0.3.
data and that used in the constraints. That is, except for the fully rotated dataset, the constraints are larger than the true transformation range used to construct the synthetic dataset (Table 6 The purpose of this experiments
showcase that the resilient approach can relax constraints associated to transformation sets that do not describe symmetries or invariances of the data and can thus hinder performance. We use the same transformation sets and constraint specification (c) for all synthetic datasets.
Synthetic invariance
Parameter
Distribution
Full Rotation
Angle in radians.
U [ 3.
Partial Rotation
Angle radians.
U π, m
Translation
Translation in pixels.
-1-8,88 8)2
Scale
Exponential Scaling factor.
U U[-Log(2),
Table 6: Sampling parameters for transformations used to obtain synthetically invariant datasets,
from 23
Constraint Set
Parameter
Range
Rotations
Angle in radians.
[- π. π|
Translation
Translation in pixels.
[-16, 16]2
Scale
Exponential Scaling factor.
[-1.5, 1.5]
Table Transformation sets G; used as invariance constraints. All sets are used simultanously. with the same constraint level (c,) for all datasets (0.1).
H.2 Results
H.2.1
Ablation on perturbation cost.
As in the case of federated learning (presented in section 4 perform an ablation on the cost function
h using ||lm| with 3 1,2, 4, co.
showed slightly better performance in terms of average test accuracy across all invariant settings. As discussed in Section 3.3 3 1 recovers penalty based methods, i.e. is equivalent to setting a fixed penalization coefficient. Nonetheless, the dynamics of our algorithm are different and can thus lead to different solutions.
As shown table g
8
Partially Rotated
Translated
Scaled
1.0
86.08 + 0.38
86.85 + 0.20
85.02 + 0.46
2.0
85.37 = 0.17
86.65 0.25
84.92 + 0.39
4.0
85.23 = 0.20
86.64 0.11
84.65 + 0.68
20
82.94 = 0.17
85.47 0.19
83.35 + 0.49
Table 8: Cost function ablation for invariant fashion-MNIST datasets. We compute the mean and standard deviation in test accuracy across three independent runs.
31

---

H.2.2 Performance on F-MNIST
The resilient approach is able to handle the misspecification of invariance requirements, outperforming in terms of test aceuracy both the constrained and unconstrained approaches. In addition, though was not designed for that purpose, our approach shows similar performance to the invariance learning method Augerino
Dataset
Method
Rotated (180)
Rotated (90)
Translated
Scaled
Original
Augerino
85.28
0.54
81.48 0.49
81.13 0.77
83.17
0.46
90.09 0.20
Unconstrained
77.94 0.06
81.57 1 0.36
79.23 0.17
82.99
0.18
90.20 0.23
F-MNIST
Constrained
84.96 0.12
85,66
0.32
83.61 0.10
86.49 0.09
91.02 0.02
Resilient
85.57 + 0.26
86.48 + 0.15
85.06 + 0.23
87.26 0.14
91.55 0.31
Table Classification accuracy for synthetically invariant F-MNIST. We use the same invariance
constraint level
0.1 for all datasets and transformations. We include the invariance learning
method Augerino
[2] as a baseline.
32


Reviews:
[{"review_id": "hDKAIm7T4m", "reviewer": "Reviewer_tedN", "summary": "This paper proposes a novel resilient learning approach for constrained learning problem. In the presented approach, constraints are interpreted as nominal specification that can be relaxed to find a better compromise between objective and requirements. The first main contribution of this paper is to relax constraints according to the sensitivity of the objective to perturbations of the constraint. Then the next contribution is to design a practical resilient learning algorithm based on duality and perturbation theory.", "questions": "I cannot find the evaluation of resilient formulation of invariant learning. Where is it? ", "limitations": "No limitations or potential negative societal impact are mentioned.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "1.\tThe assumption and properties of the convex function of relaxation and resilient equilibrium are discussed in detail in this paper, which provides a theoretical proof to the effectiveness of the presented approach.      \n2.\tThe authors also interpret why both traditional unconstrained and constrained learning can be seen as limiting cases of resilient learning.  \n3.\tThe paper is well written.\n", "weaknesses": "1.\tSome basic concepts should be explained more clearly, such as the definition of nominal specification.\n2.\tThe experiment of invariant learning is missed in Section 5 although in the abstract it is claimed to has been conducted.\n3.\tThe authors do not explain which constrained approaches are involved in the contrast experiment.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback. In what follows, we address the main points raised by the author. \n\n*(Weakness 1) Some basic concepts should be explained more clearly, such as the definition of nominal specification.* Thanks, we will add the clarification that nominal specification means u = 0.\n\n*(Weakness 2) The experiment of invariant learning is missed in Section 5 although in the abstract it is claimed to has been conducted.* \n\nAs stated at the start of Section 5 (line 272) experimental results for invariance learning are included in appendix G. We reproduce some of the results below for convenience. \n\n*The authors do not explain which constrained approaches are involved in the contrast experiment* We compare with an existing primal-dual alternating algorithm as previously used for both the imbalanced federated learning [1] and inveriant learning [2] setup. Note that this algorithm is a particular case of ours (i.e., when $h$ is the indicator function of the non-negative orthant) as discussed in section 3.3.\n\n*References* \n [1] Shen, Zebang, et al. \"An agnostic approach to federated learning with class imbalance.\" International Conference on Learning Representations. 2021.\n [2] Hounie, Ignacio, Luiz FO Chamon, and Alejandro Ribeiro. \"Automatic data augmentation via invariance-constrained learning.\" International Conference on Machine Learning. PMLR, 2023.\n\n## Invariant Learning Results\n\nIn Table 4 (Appendix G.3.2) we  compared to Augerino [4], which is a popular invariant learning method. In an easy dataset like MNIST our approach shows similar performance whereas in a more challenging dataset like FMNIST - except for the fully rotated version - our method performs statistically significantly better.\n\n| Dataset | Method        | Fully Rotated             | Partially Rotated         | Translated                 | Scaled                    | Original                  |\n|---------|---------------|---------------------------|---------------------------|----------------------------|---------------------------|---------------------------|\n| MNIST   | Augerino      | $\\mathbf{97.78 \\pm 0.03}$ | $96.38 \\pm 0.00$          | $94.65 \\pm 0.01$           | $97.53 \\pm 0.00$          | $98.44 \\pm 0.00$          |\n| MNIST   | Unconstrained | $94.49 \\pm 0.12$          | $96.25 \\pm 0.13$          | $94.64 \\pm 0.20$           | $97.47 \\pm 0.03$          | $98.45 \\pm 0.06$          |\n| MNIST   | Constrained   | $94.55 \\pm 0.18$          | $96.90 \\pm 0.07$          | $93.74 \\pm 0.07$           | $97.92 \\pm 0.15$          | $98.74 \\pm 0.08$          |\n| MNIST   | Resilient     | $95.38 \\pm 0.18$          | $\\mathbf{97.19 \\pm 0.09}$ | $\\mathbf{95.21 \\pm 0.15}$ | $\\mathbf{98.20 \\pm 0.04}$ | $\\mathbf{98.86 \\pm 0.02}$ |\n| F-MNIST | Augerino      | $\\mathbf{85.28 \\pm 0.54}$ | $81.48 \\pm 0.49$          | $81.13 \\pm 0.77$           | $83.17 \\pm 0.46$          | $90.09 \\pm 0.20$          |\n| F-MNIST | Unconstrained | $77.94 \\pm 0.06$          | $81.57 \\pm 0.36$          | $79.23 \\pm 0.17$           | $82.99 \\pm 0.18$          | $90.20 \\pm 0.23$          |\n| F-MNIST | Constrained   | $84.96 \\pm 0.12$          | $85.66 \\pm 0.32$          | $83.61 \\pm 0.10$           | $86.49 \\pm 0.09$          | $91.02 \\pm 0.02$          |\n| F-MNIST | Resilient     | $\\mathbf{85.57 \\pm 0.26}$ | $\\mathbf{86.48 \\pm 0.15}$ | $\\mathbf{85.06 \\pm 0.23}$  | $\\mathbf{87.26 \\pm 0.14}$ | $\\mathbf{91.55 \\pm 0.31}$ |\n\n*Table 4: Classification accuracy for synthetically invariant datasets. We use the same invariance constraint level $\\epsilon_i=0.1$ for all datasets and transformations. We report the mean and standard deviation computed across three independent runs.*\n\n \n [4] Benton, Gregory, et al. \"Learning invariances in neural networks from training data.\" Advances in neural information processing systems 33 (2020): 17605-17616."}, {"review_id": "ai7RSizMd3", "reviewer": "Reviewer_iyNP", "summary": "This paper introduces the concept of resilient constrained learning, which aims to find a compromise between reducing the objective loss and staying close to the original problem. This paper presents conditions for achieving a resilient equilibrium and provides equivalent formulations of resilient relaxation. This paper derives approximation and statistical guarantees for the algorithm used to find this equilibrium. It showcases its advantages in image classification tasks involving multiple potential invariances and federated learning under distribution shift. The paper's contributions include introducing a practical algorithm to compute the resilient equilibrium, determining conditions under which this equilibrium exists, and showcasing the advantages of resilient constrained learning in real-world applications.\n\n", "questions": "See Above", "limitations": "N/A", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "+ In terms of originality, resilient constrained learning is introduced, a novel approach to balancing multiple requirements in machine learning tasks. The idea of adapting the requirements while simultaneously solving the learning task is innovative. It addresses the challenge of specifying requirements in the presence of compromises and limited prior knowledge about the data. The paper also presents conditions for achieving a resilient equilibrium and provides equivalent formulations of resilient relaxation.\n\n+ The paper's significance lies in its potential to enable machine learning solutions that better satisfy real-world requirements beyond accuracy, such as fairness, robustness, or safety. \n\n", "weaknesses": "\n\n- One weakness is that the paper does not comprehensively compare existing approaches to constrained learning, such as penalty-based methods or Lagrangian duality-based methods. While the article mentions these approaches, it does not compare their strengths and weaknesses with the Resilient Constrained Learning approach. Such a comparison could help clarify the advantages and limitations of the Resilient Constrained Learning approach and provide insights into when it is most appropriate.\n\n- Additionally, the paper could benefit from a more detailed discussion of the limitations and assumptions of the proposed method. \n\n- From my humble understanding, the inequality in eq (1) should be P(v) >= P(u) + p\\top (v - u_0).\n\n- Grammar issues: L 39. be they penalty coefficients or constraint levels", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable feedback. In what follows, we address the points raised by the reviewer.\n\n*... the inequality in eq (1) should be...* Thanks for the observation, it was a typo.\n\n*...the paper does not comprehensively compare existing approaches to constrained learning,...*\n\nWe do compare with existing primal-dual algorithms for solving constrained learning problems. These algorithms have been used in recent works in both the imbalanced federated learning [R3] and invariant learning [R5] setup. All of our experimental  comparisons include constrained learning:\n\n-  Resilient solutions sacrifice stringent constraints to improve overall performance. For instance, the results shown in Figures 2(left) and 8 (in the supplementary materials) demonstrate that more stringent requirements are relaxed more and Figures 2 (right), 7 and 8 along with Tables 1 and 4 demonstrate that these relaxations lead to performance improvements as measured by the objective loss.\n- We have also included several numerical experiments to highlight properties of resilient constrained learning. For instance, Figures 3 (left), 5 and 6 show decreased sensitivity to problem specification and Figures 3 (right) and 7 show better empirical approximation of the underlying statistical problem. Both of these are properties that resilient cosntrained learning has by definition.\n\nIn addition, we have included new results and comparisons to further highlight the differences between our approach and constrained learning, as detailed below.\n\nWe adopt as benchmarks Ratio-Loss [R2] and CLIMB [R3]. The latter is a constrained learning approach which we adopt with the modification that constrains can be relaxed as per the definition of resilient equilibrium.\n\n Also, we did not tune any hyperparameters and used the same hyperparameters as in [R3], since the objective was to provide a fair comparison. In order to see how the hyperparameters that are exclusive to our method, namely $\\eta_u$ and $h(u)$, we conducted ablations detailed below.\n  \nIn this setup, average accuracy is not really the pertinent metric. Observe that the *average* accuracy (Response Table 1) is  overall similar to the constrained approach, and consistently higher than the baseline [R3].\n| Dataset | Imb. Ratio | Num Minority | Ratio-Loss[R2] | CLIMB[R3]  | OURS   |\n|---------|------------|--------------|------------|--------|--------|\n| F-MNIST | 10         | 3            | $92.5$     | $92.6$ | $93.4$ |\n| F-MNIST | 20         | 3            | $94.0$     | $93.8$ | $94.4$ |\n| CIFAR10 | 10         | 3            | $81.3$     | $81.5$ | $81.5$ |\n| CIFAR10 | 20         | 3            | $83.4$     | $82.4$ | $82.6$ |\n\n**Response Table 1**: Average  Accuracy for different setups. The imbalance ratio denotes the fraction of samples kept in minority classes. As in [R4] we use a dirichlet distribution to allocate samples among clients, with parameter $d=0.3$.\n\nHowever, the distribution o performance among clients varies. We actually chose this experiment as one in which the differences between resilient learning and standard constrained learning are apparent. Resilient learning has (generally) less spread in the interquartile range and higher maximum spread (Response Table 2) than the constrained approach. \n\n| Dataset | Imb. Ratio | Ratio Loss[R2]     | CLIMB[R3]          | OURS           |\n|---------|------------|----------------|----------------|----------------|\n| F-MNIST | 0.1        | $2.2$ $(64.1)$ | $3.5$ $(28.6)$ | $2.4$ $(50.6)$ |\n| F-MNIST | 0.05       | $2.2$ $(50.2)$ | $2.7$ $(28.6)$ | $1.7$ $(45.8)$ |\n| CIFAR10 | 0.1        | $8.1$ $(49.4)$ | $8.7$ $(35.8)$ | $8.7$ $(46.4)$ |\n| CIFAR10 | 0.05       | $8.6$ $(44.5)$ | $8.4$ $(32.0)$ | $7.9$ $(41.1)$ |\n\n**Response Table 2**: Client accuracy spread metrics for different setups. The first number denotes interquantile range and the number in parentheses denotes the maximum minus the minimum accuracy, both computed across 100 clients. \n\nThis is precisely what the method is designed to do. Sacrifice the performance of outliers to benefit the performance of the majority of the agents. In order to showcase this, we order clients by their accuracy. We then compute the fraction of clients in the resilient method that outperform equally ranked clients for baseline methods (Response Table 3).\n| Dataset | Imb. Ratio | Improved (%) | Mean Improvement | Max Improvement | Mean Decrease | Max Decrease |\n|---------|------------|--------------|------------------|-----------------|---------------|--------------|\n| CIFAR10 | 10         | 77           | 0.4              | 1.5             | 0.5           | 10.0         |\n| CIFAR10 | 20         | 79           | 0.5              | 2.1             | 0.3           | 9.1          |\n| F-MNIST | 10         | 92           | 1.6              | 4.8             | 0.9           | 23.3         |\n| F-MNIST | 20         | 94           | 1.3              | 2.6             | 0.7           | 19.4         |\n\n**Response Table 3**: Changes in accuracy for equally ranked clients for the resilient method.\nAs intended, performance improves for most clients, though at the cost of a decrease in performance for a few *outliers*.\n\n*References* \n\n[R1] \"Federated learning on non-IID data: A survey.\" Neurocomputing (2021).\n [R2]\"Addressing class imbalance in federated learning.\" AAAI 2021.\n [R3] \"An agnostic approach to federated learning with class imbalance.\" ICLR 2021.\n [R4] \"Federated Learning Based on Dynamic Regularization.\" ICLR 2021.\n[R5] \"Automatic data augmentation via invariance-constrained learning.\" ICML 2023.\n\n\n"}, {"review_id": "28Dph4foag", "reviewer": "Reviewer_69dA", "summary": "This paper proposes an approach to solve the constrained learning problem (where the considered function is convex), named resilient constrained learning. The main idea is to relax the learning constraints according to how much they affect the considered task. It can be viewed as a generalization of the standard constrained learning and studies the tradeoff between the gain from constraint relaxations and the cost from the relaxations. The main theoretical result shows that the gap between the relaxed solution and the optimal solution of the original problem is bounded by a function of the relaxation amount. Numerical experiments verified the basic properties of the proposed approach.", "questions": "It would be much better if there were some comparison with existing constrained learning algorithms, and discuss the cases where $u=0$ and $u>0$.", "limitations": "Did not see discussions of limitations.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The idea of relaxing the constraints and balance between relaxation gain and cost is interesting. When $u$>0, it can be seen as an interpolation between unconstrained learning and constrained learning. The main theorem states a bound for the gap between the relaxed solution and the original optimal solution and the derivation process seems solid (although I did not check every step carefully). It can have meaningful real life applications since in many real cases, the constraints are considered as compromisable depending on the gains of relaxations.", "weaknesses": "The writing is a little hard to follow and some important parts are put in the appendix, like the algorithm 2 mentioned below theorem 1. \n\nOne major concern is that the experimental results are quite weak even considering that this is a theoretical paper. The experiments are only sanity checks to make sure the proposed method can indeed solve some constrained learning problems, but did not demonstrate how well the solution is. There is no comparison with existing algorithms for solving constrained learning problems, which hinders the contribution of the proposed method to a large extent.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable feedback. In what follows, we address the main points raised by the reviewer.\n\n*some important parts are put in the appendix, like the algorithm 2* The algorithm referenced below theorem 1 should be Algorithm 1, which is indeed included in the main text. Algorithm 2 in the appendix pertains the federated setup only (i.e., it is more specific).\n\n*There is no comparison with existing algorithms for solving constrained learning problems*. \nWe do compare with existing primal-dual algorithms for solving constrained learning problems. This algorithm has been used in recent works in both the imbalanced federated learning [R3] and invariant learning [R5] setup. All of our experimental  comparisons include constrained learning. In addition, we have added new experiments in order to give a more detailed quantitative comparison between methods.\n\nThe main concern is that we *did not demonstrate how well the solution is*. In that sense, we reported performance on Tables 1 (Imbalanced-FL) and 4(Invariant Learning), showing that our method performs well compared to baselines. Below, we add a more in depth discussion of existing and new results.\n\n### New results in rebuttal\n\nWe point out that federated learning with class imbalance, also known as heterogeneous federated learning, is a problem motivated by practical considerations which has received substantial attention; see e.g [R1] and references therein. We adopt it as an example in this paper as a prototypical situation in which accommodating some clients -- i.e., constraints -- can be much more difficult than accomodating most clients.\n\nWe adopt as benchmarks Ratio-Loss [R2] and CLIMB [R3]. The latter is a constrained learning approach which we adopt with the modification that constrains cab be relaxed as per the definition of resilient equilibrium.\n\n Also, we did not tune any hyperparameters and used the same hyperparameters as in [R3], since the objective was to provide a fair comparison. In order to see how the hyperparameters that are exclusive to our method, namely $\\eta_u$ and $h(u)$, we conducted ablations detailed below.\n  \nWe also thank the reviewer for their suggestion to include more quantitative metrics. In this setup, average accuracy is not really the pertinent metric. Observe that the *average* accuracy (Response Table 1) is  overall similar to the constrained approach, and consistently higher than the baseline [R3].\n\nHowever, the distribution o performance among clients varies. We actually chose this experiment as one in which the differences between resilient learning and standard constrained learning are apparent. Resilient learning has (generally) less spread in the interquartile range and higher maximum spread (Response Table 2) than the constrained approach. \n\nThis is precisely what the method is designed to do. Sacrifice the performance of outliers to benefit the performance of the majority of the agents. In order to showcase this, we order clients by their accuracy. We then compute the fraction of clients in the resilient method that outperform equally ranked clients for baseline methods (Response Table 3).\n\n*References* \n\n[R1] Zhu, Hangyu, et al. \"Federated learning on non-IID data: A survey.\" Neurocomputing 465 (2021): 371-390.\n [R2] Wang, Lixu, et al. \"Addressing class imbalance in federated learning.\" Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 35. No. 11. 2021.\n [R3] Shen, Zebang, et al. \"An agnostic approach to federated learning with class imbalance.\" International Conference on Learning Representations. 2021.\n [R4] Durmus, Alp Emre, et al. \"Federated Learning Based on Dynamic Regularization.\" International Conference on Learning Representations. 2021.\n\n## Comparisons to constrained learning and discussion.\n\nIn addition to the quantitative metrics presented above, the results included both in the experimental section and appendix mainly aim to highlight the differences between our approach and existing constrained learning approaches. In doing so, we discuss the inherent trade-offs or limitations of out approach. Here we provide a brief summary and expand on how these address the fundamental aspects of our method.\n\n**Constraint Relaxation and Relative difficulty**:\nThis illustrates how our method adapts $u$ depending on how difficult it is to satisfy the constraint, whereas the constrained approach enforces the constraint ($u=0$) regardless of the price to pay in performance. Since the impact on performance depends on the data distribution, the most imbalanced clients (Figure 2 in main text) are relaxed more. This shows empirically that our method behaves as intended *in a learning setup*. The same happens for invariances that are not present in the dataset (Figure 8 in Appendix).\n\n**Controlling the performance  vs. relaxation trade-off**:\nThese experiments (Figure 2 in main text, Figure 4 in the Appendix) illustrate the inherent trade-off between imposing constraints and having better performance in terms of statistical risk in the objective.\n\n**Sensitivity to Problem Specification**:\nThese experiments (Figure 3 left in main text, Figure 6 in the appendix) highlight that our method effectively eases the challenge of specifying constraint levels in both practical setups.\n\n**Constraint violation and Generalization**:\n Based on our theoretical approximation bounds, resilient learning should have better generalization. These experiments (Figure 3 right in main text, Figure 6 in the Appendix) show that this holds in practice.\n"}, {"review_id": "rqbdtFRmFi", "reviewer": "Reviewer_4YtT", "summary": "Reasonable requirement specification in constrained learning has long been hindered by the presence of compromises and limited prior knowledge about the data. As a treatment, this paper proposes resilient constrained learning that adapts the requirements while simultaneously solving the learning task. Specifically, it balances the performance gains obtained from the constraint relaxation against a user-defined relaxation cost function. The paper provides theoretical provements for the balance (e.g. approximation and generalization guarantees) along with a practical algorithm. The algorithm is validated in invariant learning and federated learning experiments.", "questions": "1. Have you try cost functions other than $\\alpha||u||^2$, and how does different cost functions impact the algorithm's performance and efficiency?\n2. How does the learning rates $\\eta, \\eta_u,\\eta_\\lambda$ influence the algorithm's performance? Do they require meticulous joint tuning, or are they effective within certain ranges of individual values?", "limitations": "1. First, the federated and invariance learning problem are manually synthesized for validating the effectiveness of the proposed method, which I regard not convincing enough without results on large-scale real-world datasets.\n2. The federated learning experiment lacks quantitative metrics and diverse baselines other than single constrained learning.\n3. The empirical efficiency has not been studied in the paper.\n4. The paper lacks a detailed limitation discussion section.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well motivated to solve the constraint-performance trade-off problem, with the algorithm derived from detailed assumptions and theorems.\n2. Overall, I think the paper is well-written and easy-to-follow.\n3. The final algorithm is simple yet effective, allowing for a straightforward and flexible adjustment of the trade-off through a relaxation cost parameter $\\alpha$.", "weaknesses": "1. My primary concern regarding the acceptance of this paper lies in its simplistic experimentation. From my view, the federated learning problem is more like a toy example.\n2. The paper lacks in-depth study on various aspects of the algorithm's performance.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable feedback. In what follows, we address the points raised by the reviewer.\n\nWe respectfully disagree with the claim that the experimentation conducted is *(Weaknesses 1) simplistic*. Both the federated and invariant learning are benchmark setups used in recent literature [R4, R5]. We also disagree on the claim that we did not conduct several experiments that assess *(Weaknesses 2) various aspects of the algorithm's performance*. In both setups, we analyze several properties of our method, that validate empirically the motivating theory, for example:\n- *Figure 2 (left) and 8*: more stringent requirements are relaxed more\n- *Figure  2 (right), 7,  8, Table 1 and 4*: these relaxations lead to an improvement in performance.\n\n\nIn what follows, we provide a detailed discussion of new experimental results addressing the reviewers concerns.\n\nIn the federated setup, we adopt as benchmarks Ratio-Loss [R2] and CLIMB [R3]. The latter is a constrained learning approach which we adopt with the modification that constrains cab be relaxed as per the definition of resilient equilibrium. In this setup, average accuracy is not really the pertinent metric. Observe that the *average* accuracy (Response Table 1) is  overall similar to the constrained approach, and consistently higher than the baseline [R3].\n\nHowever, the distribution o performance among clients varies. We actually chose this experiment as one in which the differences between resilient learning and standard constrained learning are apparent. Resilient learning has (generally) less spread in the interquartile range and higher maximum spread (Response Table 2) than the constrained approach. \n\nThis is precisely what the method is designed to do. Sacrifice the performance of outliers to benefit the performance of the majority of the agents. In order to showcase this, we order clients by their accuracy. We then compute the fraction of clients in the resilient method that outperform equally ranked clients for baseline methods (Response Table 3).\n\n## New Ablations\n\n### Choice of cost function\n We run $||u||_\\beta$ with $\\beta =1, 2, 4$, and infinity, for fashion MNIST in both the federated and invariant setting. As discussed in Section 3.3, $\\beta = 1$ recovers penalty based methods.\n **Federated Learning**\n| $\\beta$    | Mean Acc | IQR   | Max Range |\n|------------|----------|-------|-----------|\n| 1.0        | $93.3$   | $2.5$ | $49.5$    |\n| 2.0        | $93.4$   | $2.4$ | $50.6$    |\n| 4.0        | $93.4$   | $2.6$ | $45.6$    |\n| $\\infty$   | $92.7$   | $3.8$ | $28.1$    |\n\n**Response Table 4**:*Cost function ablation for the heterogeneus federated learning in fashion-MNIST using 100 clients, 3 minority classes, an imbalance ratio of $\\rho=10$ and dirichlet allocation with parameter $d=0.3$. We report the mean, interquartile range and range (maximum value minus minimum value) test accuracy across clients.*\n\n**Invariance**\n \n | $\\beta$  | Partially Rotated | Translated      | Scaled          |\n|----------|-------------------|-----------------|-----------------|\n| 1.0      | $86.08\\pm 0.38$   | $86.85\\pm 0.20$ | $85.02\\pm 0.46$ |\n| 2.0      | $85.37\\pm 0.17$   | $86.65\\pm 0.25$ | $84.92\\pm 0.39$ |\n| 4.0      | $85.23\\pm 0.20$   | $86.64\\pm 0.11$ | $84.65\\pm 0.68$ |\n| $\\infty$ | $82.94\\pm 0.17$   | $85.47\\pm 0.19$ | $83.35\\pm 0.49$ |\n\n**Response Table 5**:*Cost function ablation for invariant fashion-MNIST datasets. We compute the mean and standard deviation in test accuracy across three independent runs.*\n\n### Learning Rates\nWe run an ablation on $\\eta_u, \\eta_\\lambda$, the perturbation and dual learning rates over a small grid of 12 values, and find that, in this range, the performance of the algorithm is not overly sensitive to this choice. We also observe that  that the rates that were used in the paper ($\\eta_u = 0.1, \\eta_\\lambda = 2$) are not optimal in this setup, and thus further improvements in performance could be obtained through more extensive hyperparameter tuning, but this was not the focus of our experiments.\n\n| $\\eta_u$ \\ $\\eta_\\lambda$ | 0.1  | 0.5  | 1    | 2    |\n|-----------------------|------|------|------|------|\n| 0.1                   | 81.4 | 81.6 | 81.8  | 81.8 |\n| 0.5                   | 81.4 | 80.9 | 81.4 | 81.1 |\n| 1                     | 81.6 | 81.6 | 81.6 | 81.7 |\n\n**Response Table 6**:*Dual and resilient learning rate ablation in Heterogenous federated learning setting. We report mean Test Accuracy for CIFAR100 using 100 clients, 3 minority classes, an imbalance ratio of $\\rho=10$ and dirichlet allocation with parameter $d=0.3$.*\n \n *References* \n\n[R1] Zhu, Hangyu, et al. \"Federated learning on non-IID data: A survey.\" Neurocomputing 465 (2021): 371-390.\n [R2] Wang, Lixu, et al. \"Addressing class imbalance in federated learning.\" Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 35. No. 11. 2021.\n [R3] Shen, Zebang, et al. \"An agnostic approach to federated learning with class imbalance.\" International Conference on Learning Representations. 2021.\n [R4] Durmus, Alp Emre, et al. \"Federated Learning Based on Dynamic Regularization.\" International Conference on Learning Representations. 2021.\n [R4] Durmus, Alp Emre, et al. \"Federated Learning Based on Dynamic Regularization.\" International Conference on Learning Representations. 2021.\n [R5] Immer, Alexander, et al. \"Invariance learning in deep neural networks with differentiable Laplace approximations.\" Advances in Neural Information Processing Systems 35 (2022): 12449-12463."}]

Author rebuttal:
# Response to all Reviewers

We sincerely thank all reviewers for their efforts in reviewing our paper. We are glad to see that all reviewers have expressed that this is a novel and well-motivated method with high potential impact in practical applications. We are also thankful for the reviewers insights and feedback which we find pertinent and valuable. We have carefully addressed your comments and suggestions and hope that the forthcoming exchanges and discussions can lead to further improvements.

The major concern about our work is whether there is sufficient empirical evaluation of resilient constrained learning. We believe that our experiments provide sufficient empirical evaluation of resilient constrained learning. We developed this idea as a way of striking compromises in situations where multiple conflicting requirement result in poor performance. Our experiments show that this does happen in practice. Resilient solutions sacrifice stringent constraints to improve overall performance. For instance, the results shown in Figures 2(left) and 8 (in the supplementary materials) demonstrate that more stringent requirements are relaxed more and Figures 2 (right), 7 and 8 along with Tables 1 and 4 demonstrate that these relaxations lead to performance improvements as measured by the objective loss.

That said, the reviewers' comment that more evidence is required is, as we said above, pertinent and valuable. We have therefore added new results based on the reviewers feedback. In particular, we have performed the following additional experimental analyses:

- *Response Table 1*: We compare average performance of resilient constrained learning with benchmarks for federated learning with class imbalance. It is notable that average performance is comparable with benchmarks. 
- *Response Table 2*: We show spread metrics of accuracy -- maximum range and interquantile range -- across clients. Constrained resilient learning reduces the interquantile range at the cost of increasing the maximum range. I.e., it improves the accuracy of most clients at the cost of reducing the accuracy of a few.
- *Response Table 3*: We rank clients according to their realized losses in standard constrained learning and resilient constrained learning. We then compare the relative performance of equally ranked clients. We see that a large fraction of clients have 1% to 5% better accuracy at the cost of possibly substantial decreases in the accuracy of a few outlier clients.
- *Response Tables 4 and 5*: We consider cost functions $h(u) = \| u\|_\beta$ with varying values of $\beta$ in the federated and invariant learning setup.
- *Response table 6*: Ablation on dual and resilient learning rates for the federated learning setup, showing that our method is not overly sensitive to these hyperparameters.

We also highlight in the individual responses several numerical experiments that were already included in the supplementary materials of our submission. The reviewers feedback suggests that having some of these results in the main body of the paper would make for a stronger contribution. We will streamline the presentation of the results in future versions of the manuscript in order to include some of these results in the main body.

We have also included several numerical experiments to highlight properties of resilient constrained learning. For instance, Figures 3 (left), 5 and 6 show decreased sensitivity to problem specification and Figures 3 (right) and 7 show better empirical approximation of the underlying statistical problem. Both of these are properties that resilient cosntrained learning has by definition.


Meta-review: This paper introduces Resilient Constrained Learning, a novel approach that strikes a balance between optimizing the primary objective and relaxing constraints. The contributions, such as sensitivity-based relaxation and a practical algorithm, have garnered positive reviews from the reviewers. Notably, the paper excels in terms of clarity, adaptability to real-world requirements, and its potential for significant impact. Both theorems and experiments provide substantial evidence of its effectiveness. In conclusion, the meta-reviewer finds the contribution of this paper to be worthy of publication and recommends that the authors incorporate the feedback received during the preparation of the camera-ready version.
Decision: Accept (poster)