Automatic and Harmless  Regularization  with Constrained and Lexicographic Optimization: A Dynamic Barrier Approach
Authors: Chengyue Gong
Xingchao Liu
qiang liu
Venue: NeurIPS 2021 Poster (2021)
Keywords: constrained optimization
lexicographic optimization
multi-objective optimization
pareto set
multi-task learning

Abstract: Many machine learning tasks have to make a trade-off between two loss functions, typically the main data-fitness loss and an auxiliary loss. 
The most widely used approach is to optimize the linear combination of the objectives, which, however, requires manual tuning of the combination coefficient and is theoretically unsuitable for non-convex functions. In this work, we consider constrained optimization as a more principled approach for trading off two losses, with a special emphasis on lexicographic optimization, a degenerated limit of constrained optimization which optimizes a secondary loss inside the optimal set of the main loss. We propose a dynamic barrier gradient descent algorithm which provides a unified solution of both constrained and lexicographic optimization. We establish the convergence of the method for general non-convex functions. 

Bi-objective Trade-off with Dynamic Barrier Gradient Descent
Chengyue Gong
Xingchao Liu Qiang Liu Computer Science, The University of Texas at Austin (cygong17, xcliu, Aqgiang((ee)) @cs. utexas....... edu
Abstract
Many machine learning tasks have to make trade-off between two loss functions, typically the main data-fitness loss and an auxiliary loss. The most widely used approach to optimize the linear combination of the objectives, which, however, requires manual tuning of the combination coefficient and is theoretically unsuit- able for non-convex functions. this work, we consider constrained optimization as more principled approach for trading off two losses, with special emphasis on lexicographic (lexico) optimization, a degenerated limit of constrained opti- mization which optimizes secondary loss inside the optimal set of the main loss. We propose a dynamic barrier gradient descent algorithm which provides a uni- fied solution of both constrained and lexicographic optimization. We establish the convergence of the method for general non-convex functions. Through number of experiments tion provides a tuning-free free approach to incorporating side loss functions without hurting the main objective, and 2) constrained and lexico optimization combined provide an automatic approach to profiling Pareto sets, especially in non-convex problems which linear combination methods fail.
world deep learning tasks, show that 1) lexico optimiza-
1
Introduction
Although machine learning (ML) has been typically conceptualized as optimizing a single objective function, most practical MI. tasks actually involve trading off two as the data fitness function vs. regularization or auxiliary loss. Let f and g be two objectives func- tions of interest on IR A principled way trade-off and g is through constrained optimization:
objective functions, such
min (()) 8E
s.l. g(0) Sc
where e is a threshold. When varying solutions of (1) cover the Pareto points of (fr g). providing different trade-offs f.g. Moreover, (1) naturally arises when g is important constraint that should be controlled explicitly, e.g., in terms of safety, fairness, and other trustworthy measures.
However, compared to unconstrained optimization, constrained optimization (1) has been much less widely used in practical machine learning. In fact, perhaps the most common approach to handling (1) is to transform it into the unconstrained optimization of the linear combination of f and g.
min f(0) + Ag(0), AER
where the trade-off between f and g is controlled by weight coefficient X, instead of the threshold parameter A folklore argument is that À can be viewed as the Lagrange multiplier of (1), and hence (1) can be mapped into (2) with properly selected
Unfortunately, despite being broadly used, (2) is insufficient to fully replace (I) and suffers from number of disadvantages in both theory and practice:
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Interpretability. À provides less intuitive parameter to select than c, since it depends on the relative scale of f and g. whose range problem-dependent and needs be optimized hyper- parameter. In comparison, the threshold can be specified as a tolerance parameter when g is metric that users want to control explicitly.
Pareto Coverage. When f. 9 are non-convex functions, (1) provides strictly broader class of problems than (2), because for some c, there may exist no À E IR, such that (1) and (2) are equivalent. From the multi-objective optimization (MOO) perspective, this is related to the fact that (2) can only capture the convex envelop of the Pareto front while varying while (1) provides all Pareto optimal points by varying c.
Invariance. The constrained optimization (1) is invariant to arbitrary monotonically increasing maps on I and g. That is, let 1/ and vi be two monotonically increasing maps, then we obtain the equivalent problem if we replace f with di and g with v/ o g. and e with (c). In comparison, applying nonlinear transforms on f and g in (2) yields fundamentally different problems.
Harmless Regularization. In many practical cases, one of the objectives (say f) is of secondary importance w.r.t. the other one (say g), in sense that we are interested in minimizing f only when is fully optimized; this can be formulated as the following lexicographic optimization problem:
min f(x) BER
s.t. g(0) S g
where
g" inf g(0). 6ER
(3)
where we minimize f inside the optimum set g()) S g"} of This can be viewed as a special case of (I) with the minimum threshold 9" (which is unknown before hand), and can not be captured by (2) with a finite and fixed A. Compared with constrained optimization (1), the lexicographic (or simply lexico) problem eliminates the need of setting the threshold c, and hence provides a handy, coefficient-fre approach for incorporating auxiliary losses without hurting the main loss. As our empirical results show, this finds useful in numerous deep learning tasks, e.g.. fairness ML and semi-supervised learning.
Our Contributions We conduct a joint study on the constrained and lexico optimization prob- lems. We propose a simple and general local descent algorithm (Algorithm 1) which offers a unified solution to both problems. By placing dynamic barrier constraint the search direction at each iteration, the algorithm finds a trajectory towards the optimal solution by properly balancing f and g with an adaptive combination coefficient coefficient ' seen in Eq 4, the Ae is decided with simple formula by the inner prod uct between the objective and constraint gradients ff and Vgg.
In Section 3-1.3.3, we study the continuous-ting time convergence of the method for general non-convex functions and both the constrained and lexico optimization cases. In Section 3.4, we elaborate the (often overlooked) fact that methods based on optimizing the linear combination (2) is fundamentally unsound as an approach to constrained optimization (1) with non-convex functions and non-zero duality gap. In Section 4, we empirically show that our method provides an efficient approach to variety of deep learning tasks.
approximating Pareto sets and incorporating side information
Algorithm Dynamic Barrier Gradient Descent for (1) and (3)
Choose stepsize ) and the dynamic barrier function & in (8) (use a = 3 1 by default; set for constrained optimization (1) and ğ to be any value no larger than g" for lexicographic optimization (3)). for iteration do
o++1= + 0: -: (v + +A Vo..)) d = max (OLO)) (T(()))T(()))
0). (4)
[Vg(0.)1
end for
2
Main Method
We introduce the main algorithm 1, a simple gradient-based method for solving both constrained optimization (1) and lexicographic optimization (3) in unified way. The method performs iterative updates of form
8,41 t- 0, U2
(5)

---

where 6, 2 0 is a step size and E I is an update direction to be chosen to balance the minimiza- tion of f and constraint satisfaction on g. The is designed to satisfy the following desiderata:
1) When the constraint is not satisfied (i.e., g(Ox) > c), we should mainly focus on decreasing to meet the constraint as fast as possible; meanwhile, should act as a secondary objective in this phase, meaning that f should be minimized upto the degree that it does not hurt the descent of g.
2) When the constraint is met (i..., g(O,) S e), we should prioritize to minimize f. which is made possible in general only we allow 9 to increase. However, the increasing rate of should be properly controlled, so that f stays inside nearby the feasible set while we minimize f.
turns out that both properties can be achieved we select by by the following optimization:
Ut- = arg min { (IV - =ll s.t. Vg(0.) 200)))
(6)
DERR
where we want U/ to be as close to (0t) as much as possible (and hence decrease f), but subject to lower bound on the inner product of Vg((,)) and U, ensure that the change of g is properly controlled by the location of 05; here the lower bound ø: R R is dynamic barrier function which trade-offss loss minimization with constraint satisfaction by controlling the inner product be- tween Vg((,) and v.2 To achieve the desiderata on Us we should let o(8,) have the same sign as g(ft) c, so that the constraint {0: g(0) I c} is equivalent to {0: x(0) S 0}, that is,
sign( ((0)) sign(g(()) c),
where sign(z) (z) [ for * 0 and sign(0) 0. In this way, when the step size et is sufficiently small, we have the following properties that will be studied theoretically in Section 3:
1) When O, is outside of the feasible set (g().) > c), the constraint is Vg(0,) Tv. 2 ((0,) > 0, which ensures that g decreases strictly outside of the feasible set.
2) When 6g is on the boundary (g(0)) c), the constrain reduces to Vg((,)) 11 2 x(0)) 0, meaning that we want to decrease f subject to that g does not increase.
3) When 0g is in the interior of the feasible set (g(O:) < c), the lower bound on (g( 0s is neg- ative, allowing to increase. In this case, the optimal solution it in (6) can be shown to have a positive inner product with V (0c) unless (f()))) O, which means that the algorithm monotoni- cally decreases f until a local optimum is reached.
Computing A Since (6) is a simple quadratic convex programming, it is easy see that the solution is 82 = f(,,) + A₂ ((,)) where de solves the following dual problem of (6):
A arg min [V + (V)ll xo(81) max ((0,) - V T 0) X
Practical Choice of á There are broad range of d's that satisfy (7). Two particularly simple choices stand out which are suitable for constrained and lexico optimization, respectively:
1) (0,)) = a(g(0,)-c) where > 0. This puts strong requirement on descending the constraint when (0.) -c is large and positive, and it gives higher flexibility for minimizing / when g(0,) - negative as we move towards the interior of the feasible set. In this case, the inner product constraint in (6) can be viewed as lincarization of the original constraint (g(0) < c) in (1): g(O, v24)) R g(O:) c (.(),) v, I c, with G 1/a. Hence, the algorithm in this case can be viewed a simple variant of sequential quadratic programming (SQP) (e.g., Nocedal & Wright, 2006) when we use an identity matrix approximate the Hessian of f-
2) (0,) (V,().) where 8 > 0. Assume that Vg((.)) = implies global minimum of g, then this e satisfies the sign condition (7) for the lexico case (3), without requiring to estimate the unknown threshold g". Because d00,) > in this case, it allows us to strictly decrease g until 0, reaches an optimum of g. Meanwhile, f acts as the secondary objective that is decreased when it does not interfere with the descent of g. In practice, when g has multiple local minima, then the algorithm would minimize [0) subject to g(0) S g(²),, where 0" is a local minimum of g that the algorithm encounters.
3

---

Combining the two cases into a single o, we propose to use
min (a(a()) (0) mmin
g). 3 (VV(())))
(8)
where we take و if the goal is to solve the constrained optimization (1) with threshold and take o to be any lower bound of g" (i.e.. 0 I g²) for solving the lexicographic optimization problem (3); for example, if 9 is norm mean square loss, then
0 is a natural estimation of the lower bound. If no lower bound can be estimated, we can take 9 = -oc, and (8) reduces back to x()) = 3 II Vg( The choice of the hyper-parameters ar, 3 controls the speed of constraint satisfaction vs. loss minimization. In our experiments, we find that it is sufficient simply set = 3 = 1 in most cases so that the algorithm introduces no extra hyper-parameters compared with vanilla gradient descent. See Algorithm I for a summary of the algorithm procedure.
Profiling Pareto Set The Pareto set of (f.g) is the set of points for which there exists no 6', such that f(0') < f(0), g(0)) S g(0), and (f(0", g((()) & (f(1), (0)). The combination of the constrained and lexico optimization provides an automatic approach to obtain uniformly distributed points from the Pareto set of (f.g). To do so, we start with solving the lexico problem (3), which cor- responds to one of the endpoints of the Pareto set; we then walk through the Pareto points by solving the constrained optimization (I) with increasing linearly from the g estimated from lexico opti- mization. Optionally, we can also solve the mirror version ming g(0) s.t. f()) S f := inf f(0))
to obtain the other end point, and then solve (I) with on grid between the two end points.
3 Theoretical Analysis
We analyze the convergence of Algorithm I for solving both constrained optimization (Section 3.1) and lexico optimization (Section 3.3). A key of our results is that they hold for general non-convex functions, which is essential for deep learning applications. In comparison, we show in Section 3.4 that the commonly used methods that transform constrained optimization (1) into sequence of un- constrained optimization problems (2) rely on the strong duality assumption and are hence unsound for non-convex cases. For simplicity, we focus on the continuous-time limit of the algorithm with d0./ /dt = - Ut, where t E [0, +o0) denotes the continuous time.
3.1 Basic Characterization: KKT Score and L1 Penalty Function
We provide basic characterization of our method in connection with the first-order KKT condition and the L1 penalty function. We start with recalling the first-order KKT necessary condition (No- cedal Wright, 2006) of the constrained optimization (I): Assume 0 is a local optimal solution of (1), that f and g are continuously differentiable, and that [V * O, then there exists a Lagrange multiplier X* E [0, +oo), such that
stationarity: vf(0") + A X0") = 0, Feasibility: g(0") S, Slackness: (gg(0)) - -) =) 0.
Note that 1V((0))] I| * 0 is important regularity condition known as a constraint quantification condition. In particular, in the lexico case (c = g"), we always have [V =I O, and hence the KKT condition above does not hold (we may think that X = toc in this case). However, the results in this subsection (Theorem 3.2 and Collorary 3.3) remain to be true for the lexico case. We discuss different second-order KKT condition for lexico case in Section 3.3.
Assume that & satisfies the sign condition (7). For 2 O, we can use the following score function, which we call the KKT score, assess the KKT condition:
(0, X) = [V + AV (0) (0) 12 + =[((0))+ + X--
where v > is a coefficient and [x]+ = max( (z. 0): it is easy to see that (0, 2 for E Rdd and X 2 0, and for (0, A) सd x [0, oo), we have (0, A) = 0 iff (8, A) meets the KKT condition.
A different way to access the optimality of (1) is to use the following Lı penalty function:
(0) ((0) + +(](()) - c]+,
(10)
where p. > 0 is a coefficient. It is known that the minimum points of (10) coincide with the solution of (1) if μ is taken to be sufficiently large (see e.g., Nocedal & Wright (2006)).
Below is a basic property of Algorithm in terms of the KKT score (0, A) and the penalty function Pa (!), which underpins all subsequent results regarding the algorithm.

---

Assumption 3.1. Assume f and are continuously differentiable. Let (0r: E (0,+)))} be gov- erned by the continuous- dynamics d0,/dt -t with v defined in (6) and & satisfying the sign condition (7). Assume X < t00 for I E (0,+
Theorem 3.2. Assume Assumption 3.1 holds. We have for any μ 2 0.
d (0.) S (0,,,, Ae), VI [0, o0).
(11)
dt
Eq (11) shows that, at any time I, the penalty function (0,( is non-increasing w.r.t. time K Ky- (0c: xr) 2 0. which, according to the definition of KKT score in (9), holds if either js large enough so that μ - de 2 0, or the constraint is met (i.c., g(O)) S с and hence [o(0,)]+ = 0).
Taking different values of allows us to extract some basic properties of the algorithm. By taking " - in (11), we show below that the constraint [g(0,) - c|+ is always non-increasing w.r.t. meaning that g(O,) is decreasing w.r.t. outside of the feasible region and 6g stays within the feasible region once it is reached for the first time. On the other hand, by taking μ = 0 in (11), we can show that f(0,) decreases monotonically w.r.t. time f within the feasible set, until KKT point is found.
Corollary 3.3. Assume Assumption 3.1 holds. We have:
1) The thresholded constraint function (g(0,) - c]+ always non-increasing w.r.t. time t:
d dt (g())) c]+ -(o(0)) 00
Vt E [0, 00),
(12)
which yields that St' ((0))+ & (g(()) - c)+, and hence min.e(o.|((000]]+ O(1/t.
2) If the constraint is satisfied (i.e., g(0,) S e). the objective f(0)) is non-increasing w.r.t. time t:
d dt f(0.) - - A.g(O.) 2[-0(00))1 s 0, when g(O,) S c.
(13)
3.2 Constrained Optimization with Bounded A
For constrained optimization (1) with finite Lagrange multiplier X it is natural to expect that A bounded by a finite number Amax outside of the feasible set {0: g(0) I c). In this case, is easy to from (11) that any penalty function (,,(0) with μ 2 Amaa Lyapunov function of the algorithm, and the best KKT score upto time (i.e., minse[o.1] (, X₂)) decays with O(1/t) rate for any y 0.
Assumption 3.4. Assume sup, (ee: g(0,)>c, E [0, 00)} = Amax < CC.
Corollary 3.5. Under Assumption 3.1 and 3.4, we have:
1) The penalty function (0t) with μ Amax is non-increasing w.r.f. time t::
d (p.) S Kpp- (0c, Ae) $O, O, Vt E [0, +oo).
(14)
dt
2) Assume f infaers f(0) > -00 The KKT score (o( Ac) with any 2 0 satisfies
L Kr Ax) S (PutAmna (0)) - ft), Vt [0, +00),
which yields that min.efo.1) Ku (0,, Xa) = O(1/t).
3) If 0, a fxee point in the sense that v, = O, with Ae < co, then (O,, Ar) satisfies the first-order KKT necessary condition above, i.e., (o,, = 0 for any v 2 0.
Below provide condition when Assumption 3.4 of finite Amax holds.
Proposition 3.6. Assume Assumption 3.1 holds. Let co = max(c, maxx)),g(0o)). Then, we have;
1) The trajectory {6,: E [0, co)} is contained inside the sublevel set (0: g(f) I cu).
2) If max( 1/ < oo for VO T = {0 E Rd: e<g(0) S ca). then Assumption 3.4 holds (i.e., Amax oc).
5

---

The most significant assumption in Proposition 3.6 is that 1/ Vo(+]] < oo for 8 E T. If compact and Vg(()) is continuous, it can be replaced by a weaker condition of [|Vg + O, v0 E r. This condition is necessary because otherwise there can be local optima of g outside of the feasible set, in which case local descent algorithm may get stuck at an infeasible local optimum and hence can not guarantee to reach the feasible set. This condition can be replaced by weaker one as we discuss in the proof of Proposition 3.6.
3.3 Lexicographic Optimization with Unbounded X2
When applying Algorithm (1) to the lexicographic optimization 3, we expect that (()] decays to zero and hence X converges to +00. Correspondingly, the KKT condition Section 3.1 does not hold since we would have X = +x0 However, it is important to point out that the KKT score (0, A) still indicates useful information regarding local optimality even the lexico case. To see this, note that in the lexico case, always have <(0) 2 0 and hence
(0,, A²) = ((.)) + Vg(e))) + vv)(
where 6(0,) 0 indicates that 0, is stationary (and hopefully minimum) point of g, and ((.) + Xe (f((l)] || || = 0 indicates the local optimality w.r.t. f. because it is the KKT condition of relax problem mfno(f(() s.t. g( I a.), where G₁ g(()).
In the following, we show that with a proper choice of é in the lexico case, the algorithm still decays the best KKT score mit),e[0.0) (0,0,, X.) upto time L, despite with a rate slower than O(1/l).
Proposition 3.7. Assume Assumption 3.1 holds, and c = g" = infoeRs g(0) > - -c, and f inloeRs l(0) > -00. Further, assume & satisfies
0 0 (0+)) S (B())'(0))1"""
where 3 > 0 and T 2 1.
Then we have for any time t E [0,
Ag
Ag
1-
A 8
min (l0.) -
min |1aa12 S Co .E
+
=E(0.8]
t
t
where 4, = g00)) g¹, D, = f(0o) - f and Co = supbEr
+ "1
+[V)(())) B
This suggests that m0 (0,,,, Aa) = 0(1/(-1//z for a fixed v 2 0. If we take (0)) [0)]'"" we have min [|.)())) - 0(1/2//)) and min ||v, = = 0(1/t-11/T)
Therefore, the power index controls the relative convergence speed of [[))l (measuring the
minimization of g), and that of [|vel] (measuring the minimization of f).
The Lexico KKT Condition Although the first order KKT condition in Section 3.1 does not apply, a different KKT condition that involves the Hessian matrix V²g can be derived for lexico optimization (see e.g., Dempe et al. (2010)). To see this, we relax the lexico problem (3) into
min f() s.t. Vg(0) = dER
(15)
If 0" is local optimum of (3), then it also a local optimum of (15). Assume f and Vg are continu- ously differenitable, and the rank of the Hessian matrix V²)(0) cquals a constant in a neighborhood of 8* (known the constant rank constraint quantification (Janin, 1984)). Then the first-order KKT necessary condition of (15) says that, there exists a vector-valued Lagrange multiplier w' E Rd. such that
vf(0") + V "0"(""""" = 0.
(16)
This is equivalent to that (f(0)) is orthogonal to the null space of V²g(O"), which is the tangent space of stationary manifold {0: Vg(0)= = 0} of g.
In Proposition 6.2 in Appendix, we show that point 0" satisfies the lexico KKT condition in (16) if it is limit of sequence {0,} that satisfies lim (6, >x) for positive v. With this, if our algorithm converges to point 0", it satisfies the lexico KKT condition.
Proposition 3.8. Assume that the conditions in Proposition 3.7 holds, and o is continuous w.r.t. 8. Assume Vg is continuously differentiable. If 6g converges to a limit point H* with lim 0₂ = A and limy Vi = O, and the rank the Hessian matrix V (()) equals a constant in a neighborhood of 0", then there exists w" E B such that 0* satisfies the lexico KKT condition in (16).

---

3,4 Non-convexity and Primal vs. Dual Methods
Many popular approaches for constrained optimization (1) used in machine learning are based on transforming it into a sequence of unconstrained optimization of form (2) with À iteratively updated in certain way by viewing it as the Lagrange multiplier. However, all these methods based on (2) are fundamentally dual methods which are guaranteed to work only when the strong duality holds. In comparison, Algorithm 1 is a primal method, which directly solves the primal problem and is hence more suitable for non-convex functions.
To elaborate, note that the constrained optimization is equivalent to the following minimax problem:
min max (0) + (g((0) c).
(17)
BER A20
If the strong duality holds, exchanging the order of min and max yields an equivalent dual problem:
max (A), X20
((A)
{f(0) + M(g(0) c)}. BER
min
(18)
Therefore, one can estimate X by maximizing (A) with gradient ascent, yielding the dual ascent algorithm. Because calculating (A) requires to solve the whole unconstrained optimization (2) and costly, simplification to alternate between the gradient ascent on and gradient descent on for solving the minimax problem, yielding the following primal-dual gradient method:
A + [ + {(g(0))
B.t1 + 0. f(V) + Vo(()))
(19)
where e and & are step sizes.
Unfortunately, all these methods, which decouple the estimation of I and X, are not suitable for non-convex functions that lack strong duality. In fact, when ff and/or g are sufficiently non-convex, the true solution 0* can be a local maximam (rather than local minimum), is not positive (semi)-definite where X the
saddle point of f(0) +
X g0)), which happens once V²f(0") + X " Lagrangian multiplier associated with 8* in the KKT condition. In this case, even if we know the true Lagrange multiplier X", minimizing f() + X g0(( as advocated in (2) would not yield the true solution 0" Similarly, the primal-dual update in (19) would fail in this case because one can show that (0*, X*) is an unstable fixed point of (19). The augmented Lagrange methods (Bertsekas, 2014), which amount replacing the objective f with (0) == f(0)+ + p(g(0)- -c p > O, can help "convexify" the objective if [g) - c]} is convex (such the case of linear constraints), but may not help when [g ci is non-convex. In comparison, Algorithm I works for general non-convex functions we show in Section 3.1-3.3.
Example 3.9. Consider toy problem: minøER 10 1 s.t. 10 < 6 with b E (0,1) and a >>00 O. Note that all a > 0 yields an equivalent problem whose true solution is 6" = and Lagrange multiplier X = (1 b)o-1 /ba- However, the choice of changes the convexity of the problem. One can show that if a < 1, the true solution is a local maximum of f(0) + X g(), and hence methods based on minimizing [0) X" (²)( would fail. However, Algorithm I solves the
problem correctly for all a > O. See Appendix for more analysis.
3.5 Related Works
Constrained Optimization There is a large classical literature on constrained optimization (No- cedal & Wright, 2006; Bertsekas, 2014; Bonnans et al., 2006), including the primal methods such as the penalty function methods, interior point methods, feasible direction methods, sequential quadratic programming (SQP), and Lagrange multiplier and dual methods. Our method is mostly related to SQP (Nocedal & Wright, 2006), of which Algorithm can be viewed special case if ((gg-c)..
we take & = (<(g-c). c). However, the general dynamic barrier view allows a broader class of o. which necessary for the lexico case; importantly, Algorithm is fast and simple to implement, making it suitable for large-scale deep learning tasks, which is the main target domain of the method. In comparison, the traditional SQP methods tend be complicated/expansiee and have not found wide applications in large-scale deep learning tasks. The penalty function methods are widely used but require a use of large penalty coefficient which may cause numerical issues. There is vast literature on Lagrange multiplier and (primal- )dual methods (Bertsekas, 2014), which, however, are designed for convex problems and problematic for non-convex problems as we show in Section 3.4. The high-level idea of dynamic barriers is similar to the control barrier functions in control theory (e.g.. Ames et al., 2019), which does not consider solving the constraint optimization and its theoretical connection to KKT conditions.
7

---

Lexicographic Optimization Despite offering a promising tool for incorporating secondary loss functions, lexico optimization (3) has been still under-explored in machine learning. In the bi- level optimization literature, (3) is known as simple bi-level programming (SBP), which is a special case of optimization on efficient sets, and more generally mathematical program with equilibrium constraints (MPEC) (Dempe et al., 2020, 2010). A number of algorithms (e.g., Sabach & Shtern (2017); Solodov (2007b.a) have been proposed in the optimization literature, which, however, focus on convex functions and yield double loop algorithms that repeatedly call an inner loop optimization and are more expensive than our method. Kissel et al. (2020) proposes a method of lexicographic optimization for training neural networks by descending in the null space of batch activations, which, however, is not scalable to large datasets and models.
Approximating Pareto Set The method of constructing Pareto sets using constrained optimiza- tion is known as the E-constrained method in the multi-objective optimization literature (e.g., (Mavrotas, 2009)), which improves over the linear scalarization approach (2) for non-convex Pareto sets. However, the traditional e-constrained method does not consider the lexico case and hence needs extra steps/information to decide the range of the threshold There is a vast literature of other approaches that work for non-convex Pareto sets in the MOO literature (Miettinen, 2012; Hwang & Masud, 2012: Pardalos et al., 2017), which has different advantages and drawbacks w.r.t. the e-constrained method.
Experiments
Our simple method can find broad applications in various deep learning tasks. We show that 1) the constrained and lexico optimization approach provides an efficient approach to profile non-convex Pareto sets, as we demonstrate in a fairness classification and a sparse representation learning task; and 2) lexico optimization alone offers parameter-free and stable approach to incorporate auxiliary regularization/lss without hurting the optimization of the main loss function, as we show in a variety of tasks: fine-gra une-grained image classification, supervised learning, and semantic segmentation.
Hype pepepaarreeeess and Settings We use Algorithm I with é in (8). We always set a B except ablation studies and hence introduce no extra hyper-parameters beyond regular (stochastic) gradient descent. For step size, we fix the learning rate to be 10-2 when profiling Pareto sets, and use the default step size scheduler of the baseline methods of each of the other applications. All the results and error bars are estimated over random trails.
Sparsity Representation Learning We learn sparse feature representations on a supervised dataset DD of (xr v) pairs by applying non-convex L, regularization:
[(0) = En(((y, (o(ho()))))
g(0) = ED (1ha(()))))]
where ((s.)) is the data loss, hx(2)) + = E R. is a hidden feature map, de is a prediction head, and i is power coefficient. We choose p 0.5 which yields non-convex sparsity penalty. We choose he(x) to be a simple linear model on a simulated dataset (Figure I (a)) and the pretrained BERT-base model (Devlin al., 2018) on the IMDb binary classification dataset (Figure 1(b)) and on the 20 news group (NG20) dataset (Figure (c)). NG20 is processed into 4-class classification following Han et al. (2016). For IMDb, we randomly sample 2K examples from the full training dataset.
We profile the Pareto set by first finding the two endpoints with lexico optimization (3) and its mirror version. Then we solve the constrained optimization (1) with e distributed evenly between the two end points (see Section 2). Figure/ 1 shows that our method (blue points) profiles the Pareto fronts evenly, which are all non-convex. The red stars are obtained by gradient descent on the linear combination (2), with w == X/(1 + A) taken from the uniform grid of [0, 1]. which can not profile the whole Pareto sets and yield unevenly distributed points as theory predicts.
Fairness Regularization Standard MI. models may yield unfair prediction in real world systems, making it necessary to regularize the training with faimess metrics. Assume we learn a predictor (e(r)) on a dataset D of (z, y, a) pairs, where I, y are feature and label, and a a protected demo- graphic attribute (e.g., male vs. female). We consider faimess regulariee learning with
(0) = (fo)),
g = Ep (5(, (o()))}
where / measures fairness using the co-variance between the protected attribute and the prediction (o(x); it can be viewed as continuous surrogate of the disparate impact criterion (Calders & Verwer, 2010). g is the standard classification loss. For the experiments, we use the Adult Income
8

---

Training Loss (
2.0
Trainin (
Training Loss
Ours
Comb
0.0
0.0
0.2
0.0
0.3
Tr norm (g)
I norm (g)
1 morm (d)
(a) Linear on Toy Data
(b) BERT-base on NG20
(c) BERT- base on IMDb
Figure 1: Our method (blue dots) profiles Pareto fronts evenly in sparse representation learning, while
linear combination (red stars) only finds parts of the Pareto front and yields unevenly distributed points.
dataset (Kohavi, 1996) for predicting whether the annual income of person is 2 $50, 000, with gender as the protected attribute. Following the setting in related works (e.g. Martinez et al., 2020; Liu & Vicente, 2020), randomly sample subset of 5,000 data points from the original training set as our training set.
Figure 2 (a.left) shows the Pareto front profiled by our method (blue dots) and the linear combination loss (2) (red dots) with A/(1 + X) uniformly taken from 20 grid of [0, 1]. Our method finds good non-convex Pareto set, while (interestingly) the linear combination method finds different convex, but sub-optimal Pareto set, in a different local mode the landscape. Note that since our Pareto front is concave, the points loss (2), and hence can not be found by gradient descent on (2) even if the corresponding À is given. Figure right) shows the prediction accuracy the true disparate impact score on the testing data; Figure 2(b) shows the trajectory of I and in Algorithm for the Lexico case (3), and the gradient descent of (2) with large X.
are the local maxima (not minima) of the linear combination
10'4
Linearonnt
Training Lass (c)
10")
Fainesss Loss
Dispurate
2:10
BG
be
Faimans
0.22
Linsert - 10% Ourstionccl
9:00
0.00
3.85
5400
0,75
0.79
1000
2000
2000
1900
2000
3000
Training Loss
Testing Accuracy
Iteration
Iteration it
(a) Pareto Front on Training& Testing Sets
(b) Training curves of and g.
Figure 2: Fairness regularization the Adult Income Dataset.
Lexicographic E Regularization Lexico optimization (3) provides a parameter- free approach to adding secondary regularization without hurting the optimization of the main loss. We apply it to fine-tune ImageNet pretrained models on fine-gras ine-grained image classification with L2 regularization:
f(0) |0012
g(0) Ep[((y, ùe (x))),
where the main loss g is the typical training loss, and the secondary loss f is the squared La Recent works (e.g. Huang et al., 2018; Salman et al., 2020) have shown that the L2 regularization (when combined linearly as (2)) helps improve the accuracy with optimally selected with holdout data (which causes high training cost). Lexico optimization eliminates the need for tuning X.
fine-grained classification datasets: Oxford Flower (Nilsback & Zisserman, 2008) and Stanford Car (Krause et al., 2013), with two deep neural architectures, in- cluding EfficientNet (Tan & Le. 2019), and AlphaNet (Wang et al., 2021); AlphaNet is the state-of- the-art mobile model on ImageNet. We use the official checkpoints provided by (Tan Le, 2019) and (Wang al., 2021). Table shows that the Lexico approach, which requires tuning of X, is almost on par with the best results of the linear combination approach with the best À on a grid. The grid search space is given by the baseline code of (Huang al., 2018; Salman et al., 2020).
For our experiments, we
Lexico Optimization for Supervisee Learning Recently, various unsupervised auxiliary losses based on data augmentation have been used in sumissuper learning (Bachman et al., 2019; Berthelot et al., 2019; Gong et al., 2020; Sohn et al., 2020; Xie et al., 2019, 2020). Typically, the auxiliary loss is linearly combined with the main supervised loss. Instead of this approach, we combine these two using lexico optimization. Following (e.g. Xie et al., 2019), we consider
f0) = Ey-rErw,, (fo || do ((x)))).
g = (x [e (z),

---

Eg regularization (lincar comhination)
Lexico
2.5 10'
2.5 10"
2.5 10"
2.5 10"
AlphaNet-A0
96.610.2
9.2
97.210.1
97.710.22
97.310.1
97.610.1
Oxford Flower
El[Net-BO
96,410.1
96.7-0.1
96.910.1
97.2:10.1
96.910.1
97.110.11
Alp
91.610.1
91.3-002
91.010.1
90.810.2
90.610.2
91.610.11
Stanford Car
EONeetBO
91.010.1
90.7=0.2
90.6:0022
90.6:10.1
90.3-0.11
91.010.1
Table I: Top-1 test accuracy on fine-grant fine-grained image classification tasks obtained by lexicographic optimization, and the lincar combination with different A.
where the main loss g is the typical training loss on a labeled dataset D, of (ar y) pairs, and the secondary loss f is the unsupervised data augmentation (UDA) loss (e.g. Xic et al., 2019) unlabeled dataset D, consisting of z only; intuitively, f measures the consistency of the prediction from x and perturbed x' T(x) using randomly transform T (e.g., rotation, flipping, etc). Table shows that the result of lexico optimization is comparable with or even better than the baseline provided by e.g., Xie al. (2019), which uses linear combination with À gradually decayed during training from a very large value (e.g. +00) to 0.2. The improvement of the lexico method is especially significant when the size of the labelled dataset is small (e.g. 100).
CIFAR-10
CIFAR-II labels labels
Method
100 labels
250 labels
1000 labels
1000 labels
2500 labels
UDA
91.1811.08 1..39
0.21
54.85 0.83
66.37-1.22 67.06:0.26
67.42.10.22 67.57
UDA Lexico
77.61
9.15 10.85
56.91 0.78
Table 2: Testing accuracy (%) of different methods on CIFAR 100 and CIFAR- 10.
Lexico Optimization for Semantic Segmentation Recent state-of-the-a (SOTA) semantic seg- mentation methods are trained with the linear combination of loss functions from two models with different complexityrresolutions (MMSegmennation,, 2020):
((0) ED (())
( ED (1))
where do is the main prediction model and ÿe auxiliary model with lower complexity and cost. Ta- ble 3 shows that lexico optimization yields better or comparable results on these two losses than lin- ear combination. Here we use Swin Transformer (Liu al., 2021), a recent-proposed SOTA model, as our backbone and use the code provided by (MMSSegmentation, 2020). We use the Cityscapes (Cordts et al., 2016) benchmark, and calculate the main loss with UperNet (Xiao al., 2018), and use FCN (Long et al., 2015) on the 3/4 of the total depth of the network to calculate the auxiliary loss.
Linear Combination À
Model
Lexico
10
5
10/3
2.5
2
Swin-Base UperNets
79.3
79.6.10.2
79.510.1
79.510.1
79.1
79.7.1..1
Swin-Base FCN
78.3+0.2
78.2+0.11
78.1
78.2+0.2
78.0+00.2
78.5+0011
Table 3: mloU for segmentation Cityscapes validation set. All the models are trained with 40K iterations and batch size 8. The results are averaged over five trials.
5 Conclusion, Limits, Future Directions
We provide a joint treatment of constrained and lexicographic optimization with general dynamic barrier gradient descent algorithm, which provides an efficient tool for profiling non-convex Pareto sets and incorporating secondary losses as we show in experiments. Our work has a potential pos- itive social impact for providing new tools for more efficient and fairness ML. Currently, our work focuses on single constraint, which yields a particularly simple algorithm. and is sufficient for broad applications. The extension to multiple constraints is straightforward (see Appendix 7), but the calculation of X₂ (which would be vector) requires solving a convex quadratic program that can be expensive when the number of constraints large. In practice, we recommend to reform the multiple constraint problems into single constraint one and then apply our method. For theoret- ical analysis, our results focus on the continuous time limit and the exact (rather than mini-batch) gradient. A future direction is to relax these constraints.
10

---

Acknowledgements The work is conducted in the statistical learning and Al group in the com- puter science department at UT Austin, which supported part by CAREER CAREER-I846421, SenSE- and Office of Navy Research, and NSF AI Institute for Foundations of Machine Learning (IFML). We would like to thank the anonymous reviewers and the area chair for their thoughtful comments and efforts towards improving our manuscript.
2037267, EAGER-200 SAIER-2041322 2041327,
References
Ames, Aaron D, Coogan, Samuel, Egerstedt, Magnus, Notomista, Gennaro, Sreenath, Koushil, and Tabuada, Paulo. Control barrier functions: Theory and applications. In 2019 18th European Control Conference (ECC), pp. 3420-3431. IEEE, 2019.
Bachman, Philip, Hjelm, R Devon, and Buchwalter, William. Learning representations by maximiz- ing mutual information across views. arXiv preprint arXiv: 00910, 2019.
Berthelot, David, Carlini, Nicholas, Goodfellow, lan, Papernot, Nicolas, Oliver, Avital, and Raf- fel, Colin. Mixmatch: A holistic approach to semi-supervised learning. arXiv preprint 1xXiv:1905.02200 2019.
Bertsekas, Dimitri P. Constrained optimization and Lagrange multiplier methods. Academic press, 2014.
Bonnans,
Gilbert, Jean Charles, Lemaréchal, Claude, and Sagastizábal, Claudia A. Numerical optimization: theoretical and practical aspects. Springer Science & Business Media, 2006.
Calders, Toon and Verwer, Sicco. Three naive bayes approaches for discrimination freet classifica- tion. Data Mining and Knowledge Discovery, 21(2):277-292 2010.
Cordts, Marius, Omran, Mohamed, Ramos, Sebastian, Rehfeld, Timo, Enzweiler, Markus, Benen- son, Rodrigo, Franke, Uwe, Roth, Stefan, and Schiele, Bernt. The cityscapes dataset for semantic urban scene understanding. In Proceedings of the IEEE conference computer vision and pat- tern recognition, pp. 3213-3223 2016.
Dempe, S, Dinh, N, and Dutta, J. Optimality conditions for a simple convex bilevel programming problem. In Variational analysis and generalized differentiation in optimization and control, pp- 149-161. Springer, 2010.
Dempe, Stephan, Dinh, Nguyen. Dutta, Joydeep, and Pandit, Tanushree. Simple bilevel program- ming and extensions. Mathematical Programming, pp. 1-27, 2020.
Devlin, Jacob, Chang, Ming-Wol Lee, Kenton, and Toutanova, Kristina. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint 1wX.vv1810.048000 2018.
Gong, Chengyue, Wang, Dilin, and Liu, Qiang. Alphamatch: Improving consistency for semi- supervised learning with alpha-divergence. arXiv preprint arXiv:2011.11777 2020.
Han, Song, Mao, Huizi, and Dally, William J.
Deep compression: Compressing deep neural net- works with pruning, trained quantization and huffman coding. The International Conference on Learning Representations, 2016.
Huang, Yanping, Cheng, Youlong, Bapna, Ankur, Firat, Orhan, Chen, Mia Xu, Chen, Dehao, Lee, HyoukJoong, Ngiam, Jiquan, Le, Quoc V, Wu, Yonghui, et al. Gpipe: Efficient training of giant neural networks using pipeline parallelism. arXiv preprint arXiv:1811.06965. 2018.
Hwang, C-L and Masud, Abu Syed Md. Multiple objective decision making- and applica- fions: a stute-of-the-art survey, volume 164. Springer Science & Business Media, 2012.
Janin, Robert. Directional derivative of the marginal function in nonlinear programming. In Sensi- fivity, Stability and Parametric Analysis, pp. 110-126. Springer, 1984.
Kissel, Matthias, Gottwald, Martin, and Diepold, Klaus. Neural network training with safe regu- larization in the null space of batch activations. International Conference on Artificial Neural Nenworks, pp. 217-228. Springer, 2020.

---

Kohavi, Ron. Scaling up the accuracy of naive-bayes classifiers: A decision- tree hybrid. In Kdd, volume 96, pp. 202-207. 1996.
Krause, Jonathan, Stark, Michael, Deng, Jia, and Fei-Fei, Li. 3d object representations for fine- grained categorization. In 4th International IEEE Workshop on 3D Representation and Recogni- lion (3dRR-13) 13), Sydney, Australia, 2013.
Liu, Suyun and Vicente, Luis Nunes, Accuracy and fairness trade-off's in machine learning: A stochastic multi-objective approach. arXiv preprint arXiv:2008.011322 2020.
Liu, Ze, Lin, Yutong, Cao, Yuc, Hu, Han, Wei, Yixuan, Zhang, Zheng, Lin, Stephen, and Guo, Baining. Swin transformer: Hicrarchical vision transformer using shifted windows. arXiv preprint arXiv:2103.14030, 2021.
Long, Jonathan, Shelhamer, Evan, and Darrell, Trevor. Fully convolutional networks for semantic segmentation. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 3431-34400 2015.
Martinez, Natalia, Bertran, Martin, and Sapiro, Guillermo. Minimax pareto fairnsss A multi ob- jective perspective. In International Conference on Machine Learning, pp. 6755-6764. PMLR, 2020.
Mavrotas, George.
Effective implementation of the e-constraint method in multi-objective mathe- matical programming problems. Applied mathematics and computation, 213(2):455-665, 2009.
Miettinen, Kaisa. Nonlinear multiobjective optimization, volume 12. Springer Science & Business Media, 2012.
MMSegmentation. MMSegmentation: Openmmlab semantic segmentation toolbox and benchmark. https://githhu: com open-mmlabe wtwpaaa/mmmmmmmeeiiiioooo 2020.
Nilsback, M-E. and Zisserman, A. Automated flower classification over large number of classes. In Proceedings of the Indian Conference on Computer Vision, Graphics and Image Processing. Dec 2008
Nocedal, Jorge and Wright, Stephen. Numerical optimization. Springer Science & Business Media, 2006.
Pardalos, Panos M. Žilinskas, Antanas, and Žilinskas, Julius. Non-convex multi-objective optimiza- tion. Springer, 2017.
Sabach, Shoham and Shtern, Shimrit. A first order method for solving convex bilevel optimization problems. SIAM Journal on Optimization, 27(2):640-66) 2017.
Salman, Hadi, Ilyas, Andrew, Engstrom, Logan, Kapoor, Ashish, and Madry, Aleksander. Do ad- versarially robust imagenet models transfer better? arXiv preprint arXiv:2007.08489, 2020.
Sohn, Kihyuk, Berthelot, David, Li, Chun-Liang, Zhang. Zizhao, Carlini, Nicholas, Cubuk, Ekin D, Kurakin, Alex, Zhang, Han, and Raffel, Colin. Fixmatch: Simplifying semi-supervised learning with consistency and confidence. arXiv preprint urXiv:2001.07688. 2020.
Solodov, Mikhail. An explicit descent method for bilevel convex optimization. Journal of Convex Analysis, 14(2):227, 2007a.
Solodov, Mikhail V. A bundle method for class of bilevel nonsmooth convex minimization prob- lems. SIAM Journal on Optimization, 18(1):242-259, 2007b.
Stewart, Gilbert W. On the perturbation of pseudo-inversed projections and linear least squares problems. SIAM review, 19(4)6334-66) 1977.
Tan, Mingxing and Le, Quoe. Efficientnet: Rethinking model scaling for convolutional neural networks. In International Conference on Machine Learning, pp. 6105 14. PMLR, 2019.
Wang, Dilin, Gong, Chengyue, Li, Meng, Liu, Qiang, and Chandra, Vikas. Alphanet: Improved training of supemnet with alpha-divergence. arXiv preprint arXiv:2102.07954 2021.
12

---

Xiao, Tete, Liu, Yingcheng, Zhou, Bolei, Jiang, Yuning, and Sun, Jian. Unified perceptual pars- ing for scene understanding, Proceedings of the European Conference on Computer Vision (ECCV), pp. 418-434, 2018.
Xie, Qizhe, Dai, Zihang, Hovy, Eduard, Luong, Minh-Thang, and Le, Quoe V. Unsupervised data augmentation for consistency training. arXiv preprint arXiv: 12848. 2019.
Xie, Qizhe, Luong, Minh-Thang, Hovy, Eduard, and Le, Quoe V. Self-training with noisy student improves imagenet classification. In Proceedings of the IEEE/CVF Conference Computer Vision and Puttern Recognition, pp. 10687-10698, 2020.
13


Reviews:
[{"review_id": "iqfpvp89DGn", "reviewer": "Reviewer_TEma", "summary": "This work studies constrained and also lexicographic optimization problem. The authors first propose a general local descent algorithm which places a dynamic barrier constraint on the search direction. The authors then investigate the theoretical properties of their algorithm and claim that their algorithm is guaranteed to converge to a local optima for both constrained and lexico optimization with non-convex functions. Finally, the authors conduct experiments to evaluate the performance of their method on several real-world deep learning tasks.\n ", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper considers non-convex constrained and lexicographic optimization problem. This problem is important and has many applications in modern machine learning (especially in deep learning) tasks. The paper also provide empirical results of their method on some popular deep learning task such as fair classification and semantic segmentation. Their approach using a dynamic barrier function to guide the selection of update direction is interesting, despite that I have some concerns outlined below about their theoretical analysis, especially proof of the Theorems.\n\nCons:\n\n(1) In the proof (Line 455-456) of Lemma A.1 in Appendix, the authors claim that \"we must have $||\\Delta g(\\theta)||\\geq e>0$ for some positive number e\". This is not true as the minimizer of a continuous function on a closed set does not necessarily lies in the set. A simple counterexample is $g(\\theta)=1/(1+e^{-\\theta})$. Typically, for that claim to be true, $\\bar{G}$ should be bounded. However this boundedness condition is not satisfied in the case of the paper. \n\n(2) In the proof of Theorem 3.3 (Line 462), the authors use $-K_{\\mu-\\lambda_t}(\\theta_t, \\lambda_t)\\leq -K_{\\mu-\\bar{\\lambda}}(\\theta_t, \\lambda_t)$. Why the inequality holds? Because of $\\bar{\\lambda}\\geq\\lambda_t$? However $\\bar{\\lambda}\\geq\\lambda_t$ only when $g(\\theta)\\geq t$. When $g(\\theta)\\leq t$ during the update, we do not know which one is bigger. Moreover, the authors claim that $(\\theta_t, \\lambda_t)$ converges to a limit $(\\theta^*, \\lambda^∗)$ which satisfy the KKT condition just because $P_\\mu(\\theta_t)$ is decreasing function w.r.t $t$. This claim is not rigorous as the limit of the derivative of a bounded smooth monotone function is not always 0. The authors need additional assumption, i.e., the limit of the derivative exists.\n\n(3) In the proof of Theorem 3.5, why (15) holds? According to my calculation, (15) is not correct and should be $\\frac{d}{dt}f(\\theta_t)=-\\nabla f(\\theta_t)^Tv_t\\geq -||v_t||^2+\\lambda_t \\phi(\\theta_t)$. The authors should carefully check for the correctness of the step. Moreover, in the last step of the proof (Line 481), the authors negligently treat the term $\\int_0^T \\phi(\\theta_t)dt$ as a constant, which is incorrect as it depends on $T$. If assuming that $\\phi(\\cdot)$ is bounded, $\\int_0^T \\phi(\\theta_t)dt$ should be $O(T^{1-\\frac{1}{\\tau}})$. Therefore, the final result should be $\\frac{1}{T}\\int_0^T||v_t||^2dt=O(1)$.\n\n(4) There are many questionable claims. In lemma 3.4, the authors assume that the limit of $\\theta_t$ exists, which may not be true in general. Moreover, in Theorem 3.5, the authors claim that the sequence $\\{\\theta_t\\}$ converges to a limit $\\theta^*$ and $\\theta^*$ satisfies $\\nabla g(\\theta^*)=0$. Can the authors please explain this?\n\n(5) The writing in the paper need to be polished, and there are many typos, i.e., \n- The authors interchange $x_t$ and $\\theta_t$, $P_\\mu$ and $L_\\mu$ in the whole paper. It would be better if the symbols are consistent.\n- In Line 50, \". But can not\"->\"and can not\"\n- In Line 79, \"We should $\\phi(\\theta_t)$ to have\"->\"We let $\\phi(\\theta_t)$ have\"\n- In Theorem 3.3, \"O(1/t)\"->\"O(1/T)\"\n- In Line 191, \"maximizing\"->\"minimizing\"\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have pointed out how to improve the paper such as extending their method to multiple constraints or SGD and discussed potential societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "20"}, "extra_text": {}}, {"review_id": "D3UG5OsRL8R", "reviewer": "Reviewer_youY", "summary": "In this paper, the authors introduce a unified first-order approach for non-convex constrained optimization with a single constraint, $\\min_{\\theta \\in \\mathbb{R}^d} f(\\theta) \\text{ s.t. } g(\\theta) \\le c\n$, and simple bilevel programming (SBP), $\\min_{\\theta \\in \\mathbb{R}^d} f(\\theta) \\text{ s.t. } \\theta \\in \\mathrm{argmin}_{\\tilde{\\theta} \\in \\mathbb{R}^d} g(\\tilde{\\theta})\n$.\n\nIn a nutshell, the approach relies on the introduction of a *dynamic barrier* $\\phi(\\theta)$ whose sign coincides with that of the constraint in canonical form, and that is used to bound from below the rate of decrease of $g$. Precisely, the authors propose to use as update direction the vector $v_t$ closest in $L_2$ norm to $\\nabla f$ among all directions whose inner product with $\\nabla g$ is at least as large as $\\phi(\\theta)$. The resulting quadratic program can be solved in closed form, leading to $v_t = \\nabla f(\\theta_t) + \\lambda_t \\nabla g(\\theta_t)$ where $\\lambda_t$ can be obtained in closed form as well as the maximizer of the dual. In other words, the resulting algorithm can be informally understood as an adaptive variant of unconstrained minimization over a linear combination of $f$ and $g$, $\\min_{\\theta \\in \\mathbb{R}^d} f(\\theta) + \\lambda g(\\theta)$, where the multiplier $\\lambda$ is not fixed throughout but adaptively estimated for each $\\theta$. Finally, the authors propose a unified choice for the dynamic barrier, $\\phi(\\theta) = \\min(\\alpha(g(\\theta) - \\hat{g}), \\beta \\vert\\vert \\nabla g(\\theta) \\vert\\vert^{2})$, where $\\hat{g}$ is either set to $c$ in the case of constrained minimization or a lower bound on $g^{*}$ for SBP, and $\\alpha, \\beta$ are hyperparameters that the authors suggest fixing to $1$ in practice.\n\nThe authors provide theoretical guarantees for both setups. For constrained optimization, it is shown that under certain regularity conditions, a continuous-time version of the algorithm with make the penalty function $P_{\\mu}(\\theta) = f(\\theta) + \\mu \\max(g(\\theta) - c, 0)$ decrease monotonically and, at convergence, the iterates $(\\theta^{\\*}, \\lambda^{\\*})$ will satisfy the KKT conditions for the problem, with “KKT suboptimality” decreasing at a linear rate. Analogously, the continuous-time version of the algorithm is shown to converge to a local minimum of $g$ with the resulting iterates $\\theta_t$ being approximate minimizers of a sequence of constrained optimization problems with constraint $c_t := g(\\theta_t)$. Moreover, these theoretical results are extended to the discrete-time setting in the Appendix.\n\nFinally, the authors illustrate their approach on a suite of real-world tasks (sparse representation learning, fairness regularization, $L_2$ regularization, semi-supervised learning and semantic segmentation) as well as a toy 2D example. In these, they primarily compare their method against a linear combination baseline treating $\\lambda$ as a (non-adaptive) hyperparameter with encouraging results.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "## Assessment\n\nFrom a pragmatic point of view, this manuscript contributes a gradient-based optimizer that allows practitioners typically relying on SGD-based optimization pipelines to incorporate either one (non-convex) constraint or a simple bilinear program (SBP) with an arguably low implementation burden and *de facto* no additional hyperparameters.\n\nThe proposed approach is, to the best of my knowledge, theoretically sound and assumptions and limitations are clearly stated throughout the manuscript.\n\nEmpirical results are shown for a wide range of real-world tasks suggesting that the proposed approach matches or outperforms unconstrained optimization over a linear combination of losses with a fixed, tunable weight.\n\nThe manuscript is also for the most part clearly written, precise, and plenty of intuition is given to the reader about the main ideas and concepts the proposed approach relies on. It would however benefit from proof-reading and additional polishing, as it contains abundant typos.\n\nAll things considered, I lean towards supporting acceptance of the manuscript in its current form. However, a few issues and limitations, some of which are discussed by the authors themselves, prevent me from further raising my score at this time, as I believe these limit potential impact to some extent. In brief:\n+ The method is currently limited in practice to two losses, which undercuts its applicability to large multi-modal models and other related state-of-the-art approaches.\n+ No theoretical guarantees are given for the stochastic setting, despite being arguably the most common use case for the proposed approach.\n+ Relatedly, while experimental results were shown involving stochastic optimization, the effect of stochasticity on convergence rates and quality of the resulting solutions was not exhaustively studied empirically.\n\n\n\n## Other comments / questions\n\n\n1. There are some aspects of Example A.12 which I have not fully grasped. I would be grateful if the authors could provide additional detail on (1) how the red curve was computed; (2) how one can infer from that curve what the fixed point for the algorithm will be; and (3) to provide the value for all hyperparameters ($\\alpha$, \\$b$, $\\phi$) to reproduce Figure 4.\n\n    More generally, I am intrigued by how the discontinuity in $\\nabla f$ at $\\theta = 1$ for $\\alpha < 1$ does not cause $\\lambda_t$ to diverge as $\\theta -> 1$ from the left.\n\n2. During the abstract and introduction it is claimed that the method is optimal in the non-convex setting. However, what that optimality entails is not precisely stated until Section 3. It could help to give an informal description of these theoretical guarantees early on.\n\n3. Is there a practical need to modify the computation of $\\lambda_t$ in Algorithm 1 for numerical stability (e.g. by ensuring the denominator does not approach zero)?\n \n\n## Typos (non-exhaustive)\n\nNotation is at times inconsistent. For example, occasionally $\\theta$ is changed to $x$, or $P_{\\mu}$ is changed to $L_{\\mu}$.\n\nL7: emphasize -> emphasis\n\nL15: leixco\n\nL162: an local -> a local\n\nEq. 9: $g(\\theta)$ -> $g(\\theta) - c$\n\nL199: $\\theta^{\\*} = 1 - b$ -> $\\theta^{\\*} = b$\n\nL266: fairness\n\nL269: predicted attribute -> protected attribute\n\nL295: semi-surprised -> semi-supervised\n\nLemma A.1: formatting of supremum assumption\n\nL455: close -> closed\n\nEq. below L461: $v(\\theta_t)$ -> $v_t$\n\nL546: multipler -> multiplier", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "As stated in the main review, I believe the main limitations of the proposed approach are its inability to handle more than two losses and, perhaps somewhat less importantly, the lack of theoretical guarantees for stochastic optimization. Both of these limitations are clearly stated and discussed in the manuscript, which is appreciated.\n\nSuccessfully extending the approach to an arbitrary number of losses with compelling empirical results on large scale multi-modal models could be a highly impactful contribution for the community.  ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "6Km3OHhUAXV", "reviewer": "Reviewer_Cn8E", "summary": "This paper proposes a method called Dynamic Barrier Gradient Descent, which can solve constrained optimization problems, and more specific lexicographic optimization problems, in a way that is amenable for use in deep learning. The idea is to solve a convex quadratic program whose solution is an update direction that trades off minimization of the original loss and constraint satisfaction. The proposed method can be used in place (with no additional parameters) of the more conventional way of incorporating additional objectives (e.g. regularization), which is to simply optimize the linear combination with a tunable weighting coefficient. The authors prove convergence for the proposed method for general non-convex functions. They show empirically on a variety of deep learning tasks that their method is superior to the linear combination method in terms of profiling non-convex Pareto sets, and yields on par, or better final performance when used in place of the linear combination method.  ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The proposed method is novel, simple, and theoretically sound, and the paper is well written and easy to follow. The experiments include a variety of tasks, and support the claims of the paper. Although the absolute performance of using the proposed method might not be better than the linear combination method (sometimes better, mostly on par), the fact that the proposed method doesn’t require tuning makes this work significant. \n\nSome comments:\n- There are a couple of small typos: 1) line 146 “Assumption 3.1 ensures that is no local …” -> “Assumption 3.1 ensures that there is no local …” 2) line 180 “min and max yields a equivalent” -> “min and max yields an equivalent” 3) line 191 “maximizing f(\\theta) + \\lambda*g(\\theta)” -> “minimizing f(\\theta) + \\lambda*g(\\theta)” 4) line 248 “ We learning sparse feature…” -> “We learn sparse feature…” 5) line 266 misspelled fairness 6) Table 1 misspelled AlphaNet 7) line 321 “..which yields a particularly…” -> “which yields a particular..” 8) line 323 “...convex quadratic programming,” -> “convex quadratic program” \n- What is L in Theorem 3.3 the second equation?\n- Figure 1 (d), is the feasible region supposed to be a line since c = g* = 0?\n- What are the \\hat{g} used for all the experiments?\n- Was there a reason why there are no l2 regularization experiments where you train from scratch? The lexicographic experiments are only for fine tuning.\n\nUpdate:\nIt seems like there is an issue with the proof of lemma A.1 pointed out by reviewer TEma. As this affects the proof of theorem 3.3, I am going to lower my score. Once the authors address this issue and polish the paper with feedback from the reviews, I would be happy to champion this paper.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have adequately addressed the limitations of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper unfortunately only received three reviews. 

One reviewer was negative due to concerns with some proofs but I think the authors have mostly addressed them.

Two reviewers were very positive and ready to back up the paper.

I would therefore like to accept the paper, assuming that the authors comply to the following two requests:

- Carefully proofread the paper and fix the numerous small typos

- Change the title, as the current title is awkward and uninformative (honestly with such a title, the authors are shooting themselves in the foot). I would suggest "Bi-objective optimization: a dynamic barrier approach" but other choices are of course possible.
Decision: Accept (Poster)