Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: 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
$, 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.
main_review: ## Assessment

From 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.

The proposed approach is, to the best of my knowledge, theoretically sound and assumptions and limitations are clearly stated throughout the manuscript.

Empirical 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.

The 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.

All 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:
+ 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.
+ No theoretical guarantees are given for the stochastic setting, despite being arguably the most common use case for the proposed approach.
+ 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.



## Other comments / questions


1. 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.

    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.

2. 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.

3. 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)?
 

## Typos (non-exhaustive)

Notation is at times inconsistent. For example, occasionally $\theta$ is changed to $x$, or $P_{\mu}$ is changed to $L_{\mu}$.

L7: emphasize -> emphasis

L15: leixco

L162: an local -> a local

Eq. 9: $g(\theta)$ -> $g(\theta) - c$

L199: $\theta^{\*} = 1 - b$ -> $\theta^{\*} = b$

L266: fairness

L269: predicted attribute -> protected attribute

L295: semi-surprised -> semi-supervised

Lemma A.1: formatting of supremum assumption

L455: close -> closed

Eq. below L461: $v(\theta_t)$ -> $v_t$

L546: multipler -> multiplier
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.

Successfully 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_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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.
 
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.

Cons:

(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. 

(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.

(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)$.

(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?

(5) The writing in the paper need to be polished, and there are many typos, i.e., 
- 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.
- In Line 50, ". But can not"->"and can not"
- In Line 79, "We should $\phi(\theta_t)$ to have"->"We let $\phi(\theta_t)$ have"
- In Theorem 3.3, "O(1/t)"->"O(1/T)"
- In Line 191, "maximizing"->"minimizing"

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_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.  
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. 

Some comments:
- 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” 
- What is L in Theorem 3.3 the second equation?
- Figure 1 (d), is the feasible region supposed to be a line since c = g* = 0?
- What are the \hat{g} used for all the experiments?
- Was there a reason why there are no l2 regularization experiments where you train from scratch? The lexicographic experiments are only for fine tuning.

Update:
It 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.

limitations_and_societal_impact: The authors have adequately addressed the limitations of their work.
review_title: null

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)