First-Order Methods for Linearly Constrained Bilevel Optimization

Summary

This paper studies fully first-order methods for bilevel optimization with strongly convex lower-level objectives and linear lower-level constraints, including both inequality constraints and equality constraints. For linear inequality constraints, the paper used a penalty methods to construct hypergradient estimators and demonstrate the approximation error. Then combined with a gradient method for nonsmooth nonconvex optimization to obtain a Goldstein stationarity point. While for linear inequality constraints, the paper proposed to use zeroth-order approximation of the hyper-gradient and demonstrate complexity.

Strengths

1. The paper considered both linear inequality and equality constraints. 2. The hypergradient construction in the linear inequality constraint setting is interesting and the paper provides approximation guarantees. It would be useful for follow-up papers. 3. Obviously, the complexity bounds are not yet optimal. But the paper has contributed several interesting directions that worth further exploration. 3. Algorithm 5 uses zeroth-order oracle is very smart as in many bilevel problems, the dimension of the upper-level is small such as hyperparameter optimization. 3. The finite-difference gradient proxy for the linear equality constrained case is also interesting.

Weaknesses

1. How to solve linear inequality constrained case with simple gradient methods to achieve optimal complexity bounds still remain unknown. The current algorithm is a bit complicated and hard to tune in practice. 2. It is unclear if the complexity bounds are optimal for both linearly inequality and equality constrained settings. Following the conventional notation for stationarity such that $||\nabla F(x)||\leq \epsilon^2$, the complexity bound for Alg 1 is $O(\epsilon^{-8})$, for Alg 2 is $O(\epsilon^{-10})$ if further taking into account the complexity to get $tilde \nabla F$, and for Alg 3 is $O(\epsilon^{-4})$. Note that the paper consider deterministic bilevel optimization, it implies that there are a lot of room for improvements. The paper should mention comparison to unconstrained lower-level bilevel optimization so that readers know the results can be improved. Despite the complexity bounds, I still believe that this paper makes good contribution to the community of bilevel optimization. 3. The methods proposed in the paper are not aligning with each other well. Despite the constrained lower-level bilevel optimization setting, the paper lacks a coherent narrative in terms of algorithmic design.

Questions

1. In the Alg 3 perturbed GD, what is the intuition to use perturbed GD instead of just inexact GD $\tilde \nabla F(x_t)$. In other words, why one needs to perturb using samples from sphere distribution? 2. In Sec 3, although the problem is nonsmooth and nonconvex, given Thm 3.3, I would assume that the $\nabla F(x)$ exists but it is not Lipschitz continuous? 3. Please be specific about Lipschitz, i.e., does it mean Lipschitz continuous or Lipschitz smooth. 4. What is the reason to consider zeroth-order methods in the linear equality constrained setting? Is it possible to derive fully first-order gradient estimator for the linear equality constrained setting? If possible, why not do it? 5. In Sec 3.1, assuming knowing $\lambda^*$ means that one also knows $y^*$ and $g^*$. 6. The definition of complexity is not very clear. In line 229, it says solving a single smooth and strongly convex optimization problems amounts to $\tilde O(1)$ oracle calls. But line 226 implies that one of such oracle call requires $\epsilon^{-1}$ gradient evaluations. Then in line 322, the complexity seems to become $O(log(1/\epsilon))$. Please specify how expensive to obtain $y^*$ and $\lambda^*$ in an $\epsilon$ error and clean oracle calls and complexity bounds in a consistent manner. 7. What is the motivation of (5.3) the perturbed lower-level problem? 8. Alg 1 requires computing $y^*_{\lambda^*,\alpha}$, this requires either $f$ to be convex in $y$ or requires $\alpha$ to be large enough to ensure $\mathcal{L}$ is convex in $y$. Please specify explicitly the requirements. Is $\mathcal{L}$ strongly convex in $y$? I am happy to raise the score if these issues are well-addressed.

Rating

6

Confidence

4

Soundness

3

Presentation

2

Contribution

4

Limitations

The paper includes several settings. Yet why adapting a specific strategy to solve each setting is not sufficiently motivated. Such as why one needs to use Alg 2 and Alg 3 instead of directly using the hypergradient estimator with gradient descent. Why one needs to use zeroth-order oracle for the linearly equality constrained setting instead of first-order oracle?

Summary

This works deals with constrained bilevel optimization problems where the lower-level has linear inequality or equality constraints. A set of algorithms is developed that does not require access to the Hessian, but only to zeroth and first-order information. In the case of inequality constraints, convergence is established to an $(\delta,\epsilon)$-Goldstein stationary point, due to the non-smoothness of the problem, using $O(\delta^{-1}\epsilon^{-4})$ or $O(d\delta^{-1}\epsilon^{-3})$ oracle calls (d: dimension of the upper-level).For equality-constrained problems, the convergence rate is nearly optimal with a rate $O(\epsilon^{-2})$.

Strengths

* This work makes progress in the topic of constrained (in the lower-level) bilevel problems, which is a challenging class of problems, much more difficult than unconstrained problems. * The development of first-order algorithms for bilevel problems with linear constraints in the lower-level. On the contrary, typically implicit gradient methods for (unconstrained or constrained) bilevel problems require access to the Hessian. In addition, for the case of inequality constraints there are no assumptions involving second-order derivatives. * The design of algorithms that deal with the non-differentiability of the hyperobjective F. * Some of the proposed algorithms (e.g., Algorithm 3) appears to be simple and easy to implement.

Weaknesses

* A major weakness of this work is the small number of experiments. There is only a single example bilevel problem over which experiments are performed. In addition, there are no experiments on real applications (e.g., in machine learning). * In the experiments section the proposed method is compared only with a single baseline, which does not correspond to any published bilevel method. Why aren’t there any comparisons with other bilevel algorithms that deal with constrained bilevel problems? There are both value function and implicit gradient methods that can, at least in theory, deal with the example problem used here, e.g. [37,38]. * The algorithms require access to exact solutions of certain problems, such as $y^{\ast}(x)$ of the lower-level or $y_{\lambda^{\ast},\alpha}^{\ast}(x)$ of problem (3.6). This is not the case in practice.

Questions

* In the gradient of the penalty function (3.5.), there is the term $\nabla_x g^{\ast}(x)$. How do you compute this gradient given that $g^{\ast}(x)$ is a min function? The authors should explain this. * The authors should explain in more detail Algorithm 2. It is not clear what the utility of each step is. * The authors derive the equations for the gradient of $F$ and $y^{\ast}(x)$ (eq. 3.3). However, as they note in section 1.1, the hyperfunction $F$ is non-smooth. Then, how can we derive a formula for the gradient of $y^{\ast}(x)$? How do we determine if a given point is differentiable? * Perhaps the least common assumption in literature is Assumption 2.3. The authors should justify whether this assumption is easy to be satisfied. For instance, is it typically the case that the dual solution is bounded? How about the Lipschitz property of $y^{\ast}(x)$? Are there other relevant (bilevel) works that use the same or similar assumption? * How does the cvxpyLayer baseline work? This is not explained clearly in the text, besides a minor reference in the Appendix. As this is the only baseline currently used, I believe that some more details are required.

Rating

6

Confidence

3

Soundness

4

Presentation

4

Contribution

4

Limitations

* See weaknesses above. * The authors discuss limitations of their work in section 7. * No negative societal impact

Summary

The paper provides algorithms for bilevel optimization with linear equality and inequality constraints. The main contribution is that the algorithms are fully first order and do not require Hessian computations. This is achieved by reformulating the linearly constrained bilevel optimization problem using the penalty method and assuming access to the upper-level variable $x$ and approximate dual optimal solution. In this setting an inexact gradient oracle for the problem is constructed. The authors provide stationarity guarantees for their algorithms under certain standard assumptions. They also describe how to use their inexact gradient oracle for non-convex non smooth optimization. The algorithms and theoretical results are backed by small set of proof-of-concept experiments.

Strengths

1) Typically, hessian inverse computation is quite expensive and hence coming up with a fully first order method with guarantees for an optimization problem has both good theoretical and practical significance. The paper will be of interest to the community. 2) The paper is written very nicely. There is a lot of clarity regarding the related works, notations, main contributions and techniques. Proof sketches are also provided for some results in the main paper. Though the paper is heavy on technical material, the organization makes it somewhat easier for the reader to follow the arguments. I am not exactly from the same research area but could follow most of the paper. 3) I could not check all the proofs in details, but the main claims of the paper appear correct. 4) Nonconvex non smooth optimization is encountered in many ML problems these days. The applicability of the inexact gradient oracle to these problems with guarantees may be of practical significance.

Weaknesses

1) There are no experiments highlighting the effectiveness of Algorithm 2. 2) The experiments given here are also only of a proof -of -concept nature and are not comprehensive. Some more comparisons with existing algorithms (based on time) and ablation studies may provide more insights regarding the practical applicability of the methods.

Questions

There is a lot of literature available on approximating Hessian computations faster for 2nd order methods (for example using iterative sketching etc.) though not necessarily for bilevel optimization. I would appreciate it if you can comment on such methods when compared to yours in terms of practicality.

Rating

7

Confidence

3

Soundness

3

Presentation

4

Contribution

3

Limitations

Yes, the limitations have been clarified in the paper.

Summary

This paper studies the linearly constrained bilevel optimization problem and provides a fully first-order method with solid theoretical analysis. To approximate hypergradient, the penalty method seems novel to me and it is applied in two settings where the LL problem is linear inequality or equality constraints.

Strengths

1. The presentation is pretty good and I feel easy to follow. 2. Theoretical analysis is solid and rigorous. 3. Code is provided.

Weaknesses

1. The experiment does not seem sufficient. 2. The checklist should be behind the appendix as I memorize.

Questions

1. Could the authors explain the design of Algorithm 2? Why is there a clip? 2. Why do authors not include the experiment of Algorithm 4? 3. Could authors compare the method in [a] though it studies the unconstrained bilevel optimization problem? [a] Yang Y, Xiao P, Ji K. Achieving ${O}(\epsilon^{-1.5}) $ Complexity in Hessian/Jacobian-free Stochastic Bilevel Optimization.

Rating

6

Confidence

2

Soundness

3

Presentation

3

Contribution

3

Limitations

Please check weaknesses and problems.

Discussions

Thanks for the detailed responses. Most of my concerns are addressed. I realize that the definition for the stationary notion in the linear equality case is with exponent 2 while in the linear inequality cases is with exponent 1, making it very confusing to comprehend. The complexity bounds in the linear equality case seems indeed optimal in terms of accuracy if the definition is with exponent 2. In addition, with the perturbation methods, does the complexity bound in the linear equality constrained case depend on the dimension of the problem? The presentation of the work requires serious improvements.

Comment by Reviewer

My main concern during the review was the limited number of experiments. The authors have addressed this issue by providing additional experiments. Given that this is primarily a theoretical work, I also understand the current absence of large-scale experiments. I am raising my score to 6.