Bi-objective Trade-off with Dynamic Barrier Gradient Descent
Year: 2022

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 (lexico) 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. Through a number of experiments on real-world deep learning tasks, we show that 1) lexico optimization provides a tuning-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 on which linear combination methods fail.

heading: 1 Introduction
text: Although machine learning (ML) has been typically conceptualized as optimizing a single objective function, most practical ML tasks actually involve trading off two or more objective functions, such as the data fitness function vs. a regularization or auxiliary loss. Let f and g be two objectives functions of interest on Rd. A principled way to trade-off f and g is through constrained optimization:
min ✓2Rd
f(✓) s.t. g(✓)  c, (1)
where c is a threshold. When varying c, solutions of (1) cover the Pareto points of (f, g), providing different trade-offs on f, g. Moreover, (1) naturally arises when g is an 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 ✓2Rd f(✓) + g(✓), (2)
where the trade-off between f and g is controlled by a weight coefficient , instead of the threshold parameter c. 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 (1) and suffers from a number of disadvantages in both theory and practice:
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
• Interpretability. provides a less intuitive parameter to select than c, since it depends on the relative scale of f and g, whose range is problem-dependent and needs to be optimized as a hyperparameter. In comparison, the threshold c can be specified as a tolerance parameter when g is a metric that users want to control explicitly.
• Pareto Coverage. When f , g are non-convex functions, (1) provides a strictly broader class of problems than (2), because for some c, there may exist no 2 R, 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 f and g. That is, let and 0 be two monotonically increasing maps, then we obtain the equivalent problem if we replace f with f , and g with 0 g, and c with 0(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 g is fully optimized; this can be formulated as the following lexicographic optimization problem:
min ✓2Rd f(x) s.t. g(✓)  g⇤ where g⇤ := inf ✓2Rd g(✓), (3)
where we minimize f inside the optimum set {✓ : g(✓)  g⇤} of g. This can be viewed as a special case of (1) with the minimum threshold c = g⇤ (which is unknown before hand), and can not be captured by (2) with a finite and fixed . 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-free 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 problems. We propose a simple and general local descent algorithm (Algorithm 1) which offers a unified solution to both problems. By placing a dynamic barrier constraint on 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 t; as seen in Eq 4, the t is decided with a simple formula by the inner prod uct between the objective and constraint gradientsrf and rg. In Section 3.1-3.3, we study the continuous-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 approximating Pareto sets and incorporating side information in a variety of deep learning tasks.
Algorithm 1 Dynamic Barrier Gradient Descent for (1) and (3) Choose stepsize {✏t} and the dynamic barrier function in (8) (use ↵ = = 1 by default; set ĝ = c for constrained optimization (1) and ĝ to be any value no larger than g⇤ for lexicographic optimization (3)). for iteration t do
✓t+1 ✓t ✏t(rf(✓t) + trg(✓t)), t = max (✓t) rf(✓t)>rg(✓t)
krg(✓t)k2 , 0
! . (4)
end for

heading: 2 Main Method
text: We introduce the main algorithm 1, a simple gradient-based method for solving both constrained optimization (1) and lexicographic optimization (3) in a unified way. The method performs iterative updates of form
✓t+1 ✓t ✏tvt, (5)
where ✏t 0 is a step size and vt 2 Rd is an update direction to be chosen to balance the minimization of f and constraint satisfaction on g. The vt is designed to satisfy the following desiderata:
1) When the constraint is not satisfied (i.e., g(✓t) > c), we should mainly focus on decreasing g to meet the constraint as fast as possible; meanwhile, f 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.e., g(✓t)  c), we should prioritize to minimize f , which is made possible in general only if we allow g to increase. However, the increasing rate of g should be properly controlled, so that ✓ stays inside or nearby the feasible set while we minimize f .
It turns out that both properties can be achieved if we select vt by the following optimization:
vt = argmin v2Rd
n krf(✓t) vk2 s.t. rg(✓t)>v (✓t) o , (6)
where we want vt to be as close to rf(✓t) as much as possible (and hence decrease f ), but subject to a lower bound on the inner product of rg(✓t) and vt to ensure that the change of g is properly controlled by the location of ✓t; here the lower bound : Rd ! R is a dynamic barrier function which trade-offs loss minimization with constraint satisfaction by controlling the inner product between rg(✓t) and vt. To achieve the desiderata on vt, we should let (✓t) have the same sign as g(✓t) c, so that the constraint {✓ : g(✓)  c} is equivalent to {✓ : (✓)  0}, that is,
sign( (✓)) = sign(g(✓) c), (7)
where sign(x) = x|x| for x 6= 0 and sign(0) = 0. In this way, when the step size ✏t is sufficiently small, we have the following properties that will be studied theoretically in Section 3:
1) When ✓t is outside of the feasible set (g(✓t) > c), the constraint is rg(✓t)>vt (✓t) > 0, which ensures that g decreases strictly outside of the feasible set.
2) When ✓t is on the boundary (g(✓t) = c), the constrain reduces to rg(✓t)>vt (✓t) = 0, meaning that we want to decrease f subject to that g does not increase.
3) When ✓t is in the interior of the feasible set (g(✓t) < c), the lower bound on rg(✓t)>vt is negative, allowing g to increase. In this case, the optimal solution vt in (6) can be shown to have a positive inner product with rf(✓t) unless rf(✓t) = 0, which means that the algorithm monotonically decreases f until a local optimum is reached.
Computing t Since (6) is a simple quadratic convex programming, it is easy to see that the solution is vt = rf(✓t) + trg(✓t) where t solves the following dual problem of (6):
t = argmin 0
n krf(✓t) + rg(✓t)k2 (✓t) o = max
(✓t) rf(✓t)>rg(✓t)
krg(✓t)k2 , 0
! .
Practical Choice of There are a broad range of ’s that satisfy (7). Two particularly simple choices stand out which are suitable for constrained and lexico optimization, respectively:
1) (✓t) = ↵(g(✓t) c), where ↵ > 0. This puts a strong requirement on descending the constraint g when g(✓t) c is large and positive, and it gives higher flexibility for minimizing f when g(✓t) c is negative as we move towards the interior of the feasible set. In this case, the inner product constraint in (6) can be viewed as a linearization of the original constraint (g(✓)  c) in (1): g(✓t ✏tvt) ⇡ g(✓t) ✏trg(✓t)>vt  c, with ✏t = 1/↵. Hence, the algorithm in this case can be viewed as a simple variant of sequential quadratic programming (SQP) (e.g., Nocedal & Wright, 2006) when we use an identity matrix to approximate the Hessian of f .
2) (✓t) = krg(✓t)k2, where > 0. Assume that rg(✓t) = 0 implies global minimum of g, then this satisfies the sign condition (7) for the lexico case (3), without requiring to estimate the unknown threshold g⇤. Because (✓t) 0 in this case, it allows us to strictly decrease g until ✓t 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 f(✓) subject to g(✓)  g(✓̂⇤), where ✓̂⇤ is a local minimum of g that the algorithm encounters.
Combining the two cases into a single , we propose to use
(✓) = min ⇣ ↵(g(✓) ĝ), krg(✓)k2 ⌘ , (8)
where we take ĝ = c if the goal is to solve the constrained optimization (1) with threshold c, and take ĝ to be any lower bound of g⇤ (i.e., ĝ  g⇤) for solving the lexicographic optimization problem (3); for example, if g is a norm or mean square loss, then ĝ = 0 is a natural estimation of the lower bound. If no lower bound can be estimated, we can take ĝ = 1, and (8) reduces back to (✓) = krg(✓)k2. The choice of the hyper-parameters ↵, controls the speed of constraint satisfaction vs. loss minimization. In our experiments, we find that it is sufficient to simply set ↵ = = 1 in most cases so that the algorithm introduces no extra hyper-parameters compared with vanilla gradient descent. See Algorithm 1 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 ✓0, such that f(✓0)  f(✓), g(✓0)  g(✓), and (f(✓0), g(✓0)) 6= (f(✓), g(✓)). 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 corresponds to one of the endpoints of the Pareto set; we then walk through the Pareto points by solving the constrained optimization (1) with c increasing linearly from the g⇤ estimated from lexico optimization. Optionally, we can also solve the mirror version min✓ g(✓) s.t. f(✓)  f⇤ := inf✓0 f(✓0) to obtain the other end point, and then solve (1) with c on a grid between the two end points.

heading: 3 Theoretical Analysis
text: We analyze the convergence of Algorithm 1 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 a sequence of unconstrained 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 d✓t/dt = vt, where t 2 [0,+1) denotes the continuous time.

heading: 3.1 Basic Characterization: KKT Score and L1 Penalty Function
text: We provide a 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 (Nocedal & Wright, 2006) of the constrained optimization (1): Assume ✓⇤ is a local optimal solution of (1), that f and g are continuously differentiable, and that krg(✓⇤)k 6= 0, then there exists a Lagrange multiplier ⇤ 2 [0,+1), such that stationarity: rf(✓⇤) + ⇤rg(✓⇤) = 0, Feasibility: g(✓⇤)  c, Slackness: ⇤(g(✓⇤) c) = 0.
Note that krg(✓⇤)k 6= 0 is an important regularity condition known as a constraint quantification condition. In particular, in the lexico case (c = g⇤), we always have krg(✓⇤)k = 0, and hence the KKT condition above does not hold (we may think that ⇤ = +1 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 a different second-order KKT condition for lexico case in Section 3.3.
Assume that satisfies the sign condition (7). For 0, we can use the following score function, which we call the KKT score, to assess the KKT condition:
K⌫(✓, ) = krf(✓) + rg(✓)k2 + ⌫[ (✓)]+ + [ (✓)]+, (9)
where ⌫ > 0 is a coefficient and [x]+ = max(x, 0); it is easy to see that K⌫(✓, ) 0 for ✓ 2 Rd and 0, and for (✓, ) 2 Rd⇥ [0,1), we have K⌫(✓, ) = 0 iff (✓, ) meets the KKT condition. A different way to access the optimality of (1) is to use the following L1 penalty function:
Pµ(✓) = f(✓) + µ[g(✓) c]+, (10) where µ > 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 1 in terms of the KKT score K⌫(✓, ) and the penalty function Pµ(✓), which underpins all subsequent results regarding the algorithm.
Assumption 3.1. Assume f and g are continuously differentiable. Let {✓t : t 2 [0,+1)} be governed by the continuous-time dynamics d✓t/dt = vt with vt defined in (6) and satisfying the sign condition (7). Assume t < +1 for t 2 [0,+1).
Theorem 3.2. Assume Assumption 3.1 holds. We have for any µ 0, d
dt Pµ(✓t)  Kµ t(✓t, t), 8t 2 [0,1). (11)
Eq (11) shows that, at any time t, the penalty function Pµ(✓t) is non-increasing w.r.t. time t if Kµ t(✓t, t) 0, which, according to the definition of KKT score in (9), holds if either µ is large enough so that µ t 0, or the constraint is met (i.e., g(✓t)  c and hence [ (✓t)]+ = 0). Taking different values of µ allows us to extract some basic properties of the algorithm. By taking µ ! +1 in (11), we show below that the constraint [g(✓t) c]+ is always non-increasing w.r.t. t, meaning that g(✓t) is decreasing w.r.t. t outside of the feasible region and ✓t 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(✓t) decreases monotonically w.r.t. time t within the feasible set, until a KKT point is found.
Corollary 3.3. Assume Assumption 3.1 holds. We have: 1) The thresholded constraint function [g(✓t) c]+ is always non-increasing w.r.t. time t:
d dt [g(✓t) c]+  [ (✓t)]+  0, 8t 2 [0,1), (12)
which yields that R t 0 [ (✓s)]+ds  [g(✓0) c]+, and hence mins2[0,t][ (✓s)]+ = O(1/t).
2) If the constraint is satisfied (i.e., g(✓t)  c), the objective f(✓t) is non-increasing w.r.t. time t: d
dt f(✓t)  krf(✓t) + tg(✓t)k2 t[ (✓t)]+  0, when g(✓t)  c. (13)

heading: 3.2 Constrained Optimization with Bounded t
text: For constrained optimization (1) with a finite Lagrange multiplier ⇤, it is natural to expect that t is bounded by a finite number max outside of the feasible set {✓ : g(✓)  c}. In this case, it is easy to see from (11) that any penalty function Pµ(✓) with µ max is a Lyapunov function of the algorithm, and the best KKT score upto time t (i.e., mins2[0,t] K⌫(✓s, s)) decays with O(1/t) rate for any ⌫ 0.
Assumption 3.4. Assume supt{ t : g(✓t)>c, t 2 [0,1)} = max <1.
Corollary 3.5. Under Assumption 3.1 and 3.4, we have: 1) The penalty function Pµ(✓t) with µ max is non-increasing w.r.t. time t :
d dt Pµ(✓t)  Kµ max(✓t, t)  0, 8t 2 [0,+1). (14)

heading: 2) Assume f⇤ = inf✓2Rd f(✓) > 1. The KKT score K⌫(✓t, t) with any ⌫ 0 satisfies
text: Z t
0 K⌫(✓s, s)ds  (P⌫+ max(✓0) f⇤), 8t 2 [0,+1),
which yields that mins2[0,t] K⌫(✓s, s) = O(1/t).

heading: 3) If ✓t is a fixed point in the sense that vt = 0, with t < 1, then (✓t, t) satisfies the first-order KKT necessary condition above, i.e., K⌫(✓t, t) = 0 for any ⌫ 0.
text: Below we provide a condition when Assumption 3.4 of finite max holds.
Proposition 3.6. Assume Assumption 3.1 holds. Let c0 = max(c, g(✓0)). Then, we have: 1) The trajectory {✓t : t 2 [0,1)} is contained inside the sublevel set {✓ : g(✓)  c0}.
2) If max( (✓), krf(✓)k , 1/ krg(✓)k) < 1 for 8✓ 2 := {✓ 2 Rd : c<g(✓)  c0}, then Assumption 3.4 holds (i.e., max <1).
The most significant assumption in Proposition 3.6 is that 1/ krg(✓)k < 1 for ✓ 2 . If is compact and rg(✓) is continuous, it can be replaced by a weaker condition of krg(✓)k 6= 0, 8✓ 2 . This condition is necessary because otherwise there can be local optima of g outside of the feasible set, in which case a 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 a weaker one as we discuss in the proof of Proposition 3.6.

heading: 3.3 Lexicographic Optimization with Unbounded t
text: When applying Algorithm (1) to the lexicographic optimization 3, we expect that krg(✓t)k decays to zero and hence t converges to +1. Correspondingly, the KKT condition in Section 3.1 does not hold since we would have ⇤ = +1. However, it is important to point out that the KKT score K⌫(✓, ) still indicates useful information regarding local optimality even in the lexico case. To see this, note that in the lexico case, we always have (✓) 0 and hence
K⌫(✓t, t) = krf(✓t) + trg(✓t)k2 + ⌫ (✓t), where (✓t) = 0 indicates that ✓t is a stationary (and hopefully minimum) point of g, and krf(✓t) + trg(✓t)k = kvtk = 0 indicates the local optimality w.r.t. f , because it is the KKT condition of a relax problem min✓{f(✓) s.t. g(✓)  ct}, where ct = g(✓t). In the following, we show that with a proper choice of in the lexico case, the algorithm still decays the best KKT score mins2[0,t] K⌫(✓s, s) upto time t, despite with a rate slower than O(1/t).
Proposition 3.7. Assume Assumption 3.1 holds, and c = g⇤ = inf✓2Rd g(✓) > 1, and f⇤ = inf✓2Rd f(✓) > 1. Further, assume satisfies 0  (✓t)  krg(✓t)k⌧ , where > 0 and ⌧ 1. Then we have for any time t 2 [0,1),
min s2[0,t] (✓s)  g t , min s2[0,t] kvsk2  C0 ✓ g t ◆1 1⌧ + f t ,
where g = g(✓0) g⇤, f = f(✓0) f⇤, and C0 = sup✓2Rd ⇣ krg(✓)k⌧ 1 + krf(✓)k ⌘ 1 ⌧ .
This suggests that mins2[0,t] K⌫(✓s, s) = O(1/t1 1/⌧ ) for a fixed ⌫ 0. If we take (✓) = krg(✓)k⌧ , we have mins2[0,t] krg(✓s)k2 = O(1/t2/⌧ ) and mins2[0,t] kvsk2 = O(1/t1 1/⌧ ). Therefore, the power index ⌧ controls the relative convergence speed of krg(✓t)k (measuring the minimization of g), and that of kvtk (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 r2g can be derived for lexico optimization (see e.g., Dempe et al. (2010)). To see this, we relax the lexico problem (3) into
min ✓2Rd
f(✓) s.t. rg(✓) = 0. (15)
If ✓⇤ is a local optimum of (3), then it is also a local optimum of (15). Assume f andrg are continuously differenitable, and the rank of the Hessian matrixr2g(✓) equals a constant in a neighborhood of ✓⇤ (known as 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 !⇤ 2 Rd, such that
rf(✓⇤) +r2g(✓⇤)!⇤ = 0. (16) This is equivalent to that rf(✓⇤) is orthogonal to the null space of r2g(✓⇤), which is the tangent space of stationary manifold {✓ : rg(✓) = 0} of g. In Proposition 6.2 in Appendix , we show that a point ✓⇤ satisfies the lexico KKT condition in (16) if it is a limit of a sequence {✓t} that satisfies limt!+1 K⌫(✓t, t) = 0 for a positive ⌫. With this, if our algorithm converges to a point ✓⇤, it satisfies the lexico KKT condition.
Proposition 3.8. Assume that the conditions in Proposition 3.7 holds, and is continuous w.r.t. ✓. Assume rg is continuously differentiable. If ✓t converges to a limit point ✓⇤ with limt!1 ✓t = ✓⇤ and limt!1 vt = 0, and the rank of the Hessian matrixr2g(✓) equals a constant in a neighborhood of ✓⇤, then there exists !⇤ 2 Rd such that ✓⇤ satisfies the lexico KKT condition in (16).

heading: 3.4 Non-convexity and Primal vs. Dual Methods
text: 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 ✓2Rd max 0 f(✓) + (g(✓) c). (17)
If the strong duality holds, exchanging the order of min and max yields an equivalent dual problem: max 0 ( ), ( ) = min ✓2Rd {f(✓) + (g(✓) c)} . (18)
Therefore, one can estimate ⇤ by maximizing ( ) with gradient ascent, yielding the dual ascent algorithm. Because calculating ( ) requires to solve the whole unconstrained optimization (2) and is costly, a simplification is to alternate between the gradient ascent on and gradient descent on ✓ for solving the minimax problem, yielding the following primal-dual gradient method:
t [ t 1 + ⇠(g(✓t) c)]+, ✓t+1 ✓t ✏(rf(✓t) + trg(✓t)), (19) where ✏ and ⇠ are step sizes.
Unfortunately, all these methods, which decouple the estimation of ✓ and , are not suitable for non-convex functions that lack strong duality. In fact, when f and/or g are sufficiently non-convex, the true solution ✓⇤ can be a local maximum (rather than local minimum), or saddle point of f(✓)+ ⇤ g(✓), which happens once r2f(✓⇤) + ⇤r2g(✓⇤) is not positive (semi)-definite, where ⇤ is the Lagrangian multiplier associated with ✓⇤ in the KKT condition. In this case, even if we know the true Lagrange multiplier ⇤, minimizing f(✓) + ⇤g(✓) as advocated in (2) would not yield the true solution ✓⇤. Similarly, the primal-dual update in (19) would fail in this case because one can show that (✓⇤, ⇤) is an unstable fixed point of (19). The augmented Lagrange methods (Bertsekas, 2014), which amount to replacing the objective f with f⇢(✓) := f(✓)+⇢[g(✓) c]2+, ⇢ > 0, can help “convexify” the objective if [g(✓) c]2+ is convex (such as the case of linear constraints), but may not help when [g c]2+ is non-convex. In comparison, Algorithm 1 works for general non-convex functions we show in Section 3.1-3.3.
Example 3.9. Consider a toy problem: min✓2R |✓ 1|↵ s.t. |✓|↵  b↵ with b 2 (0, 1) and ↵ > 0. Note that all ↵ > 0 yields an equivalent problem whose true solution is ✓⇤ = b and Lagrange multiplier ⇤ = (1 b)↵ 1/b↵ 1. However, the choice of ↵ changes the convexity of the problem. One can show that if ↵ < 1, the true solution is a local maximum of f(✓) + ⇤g(✓), and hence methods based on minimizing f(✓) + ⇤g(✓) would fail. However, Algorithm 1 solves the problem correctly for all ↵ > 0. See Appendix for more analysis.

heading: 3.5 Related Works
text: Constrained Optimization There is a large classical literature on constrained optimization (Nocedal & 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 1 can be viewed as a special case if we take = ↵(g c). However, the general dynamic barrier view allows a broader class of , which is necessary for the lexico case; importantly, Algorithm 1 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 to be complicated/expansive 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 a 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.
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 bilevel 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 optimization is known as the "-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 "-constrained method does not consider the lexico case and hence needs extra steps/information to decide the range of the threshold c. 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 "-constrained method.

heading: 4 Experiments
text: 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 a parameter-free and stable approach to incorporate auxiliary regularization/loss without hurting the optimization of the main loss function, as we show in a variety of tasks: fine-grained image classification, semi-supervised learning, and semantic segmentation.
Hyperparameters and Settings We use Algorithm 1 with in (8). We always set ↵ = = 1 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 5 random trails.
Sparsity Representation Learning We learn sparse feature representations on a supervised dataset D of (x, y) pairs by applying a non-convex Lp regularization:
f(✓) = ED[`(y, ✓(h✓(x)))], g(✓) = ED[kh✓(x)kpp],
where `(·, ·) is the data loss, h✓(x) 7! z 2 Rm is a hidden feature map, ✓ is a prediction head, and p is a power coefficient. We choose p = 0.5 which yields a non-convex sparsity penalty. We choose h✓(x) to be a simple linear model on a simulated dataset (Figure 1(a)) and the pretrained BERT-base model (Devlin et al., 2018) on the IMDb binary classification dataset (Figure 1(b)) and on the 20 news group (NG20) dataset (Figure 1 (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 c 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 ! := /(1 + ) 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 ML models may yield unfair prediction in real world systems, making it necessary to regularize the training with fairness metrics. Assume we learn a predictor ŷ✓(x) on a dataset D of (x, y, a) pairs, where x, y are feature and label, and a a protected demographic attribute (e.g., male vs. female). We consider fairness-regularized learning with
f(✓) = (covD(ŷ✓(x), a)) 2 , g(✓) = ED[`(y, ŷ✓(x))],
where f measures fairness using the co-variance between the protected attribute a and the prediction ŷ✓(x); it can be viewed as a continuous surrogate of the disparate impact criterion (Calders & Verwer, 2010). g is the standard classification loss. For the experiments, we use the Adult Income
dataset (Kohavi, 1996) for predicting whether the annual income of a person is $50, 000, with gender as the protected attribute. Following the setting in related works (e.g. Martinez et al., 2020; Liu & Vicente, 2020), we randomly sample a 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 /(1 + ) uniformly taken from a 20 ⇥ 1 grid of [0, 1]. Our method finds a good non-convex Pareto set, while (interestingly) the linear combination method finds a different convex, but sub-optimal Pareto set, in a different local mode of the landscape. Note that since our Pareto front is concave, the points on it are the local maxima (not minima) of the linear combination loss (2), and hence can not be found by gradient descent on (2) even if the corresponding is given. Figure 2(a,right) shows the prediction accuracy on the true disparate impact score on the testing data; Figure 2(b) shows the trajectory of f and g in Algorithm 1 for the Lexico case (3), and the gradient descent of (2) with a large .
Lexicographic `2 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-grained image classification with L2 regularization:
f(✓) = k✓k22, g(✓) = ED[`(y, ŷ✓(x))],
where the main loss g is the typical training loss, and the secondary loss f is the squared L2 norm. 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 a holdout data (which causes high training cost). Lexico optimization eliminates the need for tuning .
For our experiments, we use two fine-grained classification datasets: Oxford Flower (Nilsback & Zisserman, 2008) and Stanford Car (Krause et al., 2013), with two deep neural architectures, including EfficientNet (Tan & Le, 2019), and AlphaNet (Wang et al., 2021); AlphaNet is the state-ofthe-art mobile model on ImageNet. We use the official checkpoints provided by (Tan & Le, 2019) and (Wang et al., 2021). Table 1 shows that the Lexico approach, which requires no tuning of , 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 et al., 2018; Salman et al., 2020).
Lexico Optimization for Semi-Supervised Learning Recently, various unsupervised auxiliary losses based on data augmentation have been used in semi-supervised 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
f(✓) = ET⇠T Ex⇠Du [KL(ŷ✓(x) || ŷ✓(T(x)))], g(✓) = E(x,y)⇠Ds [`(ŷ✓(x), y)],
where the main loss g is the typical training loss on a labeled dataset Ds of (x, y) pairs, and the secondary loss f is the unsupervised data augmentation (UDA) loss (e.g. Xie et al., 2019) on an unlabeled dataset Du consisting of x only; intuitively, f measures the consistency of the prediction from x and a perturbed x0 = T(x) using a randomly transform T (e.g., rotation, flipping, etc). Table 2 shows that the result of lexico optimization is comparable with or even better than the baseline provided by e.g., Xie et al. (2019), which uses linear combination with gradually decayed during training from a very large value (e.g. +1) to 0.2. The improvement of the lexico method is especially significant when the size of the labelled dataset is small (e.g. 100).
Lexico Optimization for Semantic Segmentation Recent state-of-the-art (SOTA) semantic segmentation methods are trained with the linear combination of loss functions from two models with different complexity/resolutions (MMSegmentation, 2020):
f(✓) = ED[`(ỹ✓(x), y)], g(✓) = ED[`(ŷ✓(x), y)],
where ŷ✓ is the main prediction model and ỹ✓ an auxiliary model with lower complexity and cost. Table 3 shows that lexico optimization yields better or comparable results on these two losses than linear combination. Here we use Swin Transformer (Liu et al., 2021), a recent-proposed SOTA model, as our backbone and use the code provided by (MMSegmentation, 2020). We use the Cityscapes (Cordts et al., 2016) benchmark, and calculate the main loss with UperNet (Xiao et 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.

heading: 5 Conclusion, Limits, Future Directions
text: We provide a joint treatment of constrained and lexicographic optimization with a 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 positive social impact for providing new tools for more efficient and fairness ML. Currently, our work focuses on a 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 t (which would be a vector) requires solving a convex quadratic program that can be expensive when the number of constraints is large. In practice, we recommend to reform the multiple constraint problems into a single constraint one and then apply our method. For theoretical 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.
Acknowledgements The work is conducted in the statistical learning and AI group in the computer science department at UT Austin, which is supported in part by CAREER-1846421, SenSE2037267, EAGER-2041327, 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.

Review summaries:
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.  

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.  

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 $, 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}) $.  In 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.  The 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.  Finally, 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.