Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper provides gradient descent-based for solving bi-level optimization problems where the lower-level problem has a strongly convex objective and linear inequality constraints, using implicit gradients. The authors derive conditions under which the implicit objective is differentiable, and propose a perturbation-based smoothing technique to address non-differentiable cases. The authors also propose adaptive step sizing techniques for the gradient descent procedure to ensure convergence. They empirically demonstrate the efficacy of their method on two test cases: (1) linearly constrained quadratic bilevel problems, and (2) adversarial training.
strength_and_weaknesses: Strengths:
* The approach is simple yet powerful. It leverages implicit differentiation and gradient descent to address an important class of bi-level optimization problems, and does so in a very principled manner - establishing theoretically for which cases differentiation-based techniques are likely to work, introducing perturbation-based smoothing to expand the set of problems for which such methods might (approximately) work, and then utilizing techniques such as adaptive step sizing to ensure convergence in a wide variety of cases.
* The experiments, though not overwhelmingly convincing, do reasonably demonstrate the efficacy of the proposed method.
* The paper is accessible and clearly written.

Weaknesses:
* The authors do not seem to be aware of the large body of work in implicit differentiation of optimization problems within the deep learning literature - see, e.g., the list below. The authors should be sure to discuss and situate their work within this literature, as it is very closely related. In particular, [8] below also uses implicit differentiation to address a class of bilevel optimization problems via gradient descent.
* Minor: In Equation (1a), it would be cleaner if the notation $f$ were not overloaded.
* Minor: The paper is missing a Conclusion section, which is standard for such papers.

Overarching note: On the one hand, the existing literature on implicit layers diminishes the contribution of this work from an empirical perspective. On the other hand, this paper perhaps inadvertently fills several gaps in the implicit layers literature (which often lacks principled analyses), thus contributing to the strengths of the present work. For instance, these works often do not contain analysis of the quality of the gradient under an approximate solution to the optimization solution, but the present work does.

Example literature on implicit differentiation of optimization problems:
* [1] Brandon Amos and J Zico Kolter. “OptNet: Differentiable optimization as a layer in neural networks.” International Conference on Machine Learning. 2017.
* [2] Josip Djolonga and Andreas Krause. “Differentiable Learning of Submodular Models.” Advances in Neural Information Processing Systems (NeurIPS). 2017.
* [3] Priya L. Donti, Brandon Amos, and J. Zico Kolter. “Task-based End-to-End Model Learning in Stochastic Optimization.” Advances in Neural Information Processing Systems. 2017.
* [4] Sebastian Tschiatschek, Aytunc Sahin, and Andreas Krause. “Differentiable submodular maximization.” International Joint Conference on Artificial Intelligence. 2018.
* [5] Akshay Agrawal, Brandon Amos, Shane Barratt, Stephen Boyd, Steven Diamond, and J Zico Kolter. “Differentiable convex optimization layers.” Advances in Neural Information Processing Systems (NeurIPS). 2019.
* [6] Stephen Gould, Richard Hartley, and Dylan Campbell. “Deep declarative networks.” IEEE Transactions on Pattern Analysis and Machine Intelligence 44.8 (2021), 3988–4004.
* [7] http://implicit-layers-tutorial.org/
* [8] Priya L. Donti, Aayushya Agarwal, Neeraj Vijay Bedmutha, Larry Pileggi, and J. Zico Kolter. “Adversarially Robust Learning for Security-Constrained Optimal Power Flow.” Advances in Neural Information Processing Systems. 2021.
clarity,_quality,_novelty_and_reproducibility: The papers is clearly written. The idea proposed is simple yet powerful; however, it is not properly situated within the implicit layers/differentiable optimization literature. Sufficient details are provided for reproducibility.
summary_of_the_review: This paper provides a simple, powerful, and principled approach for addressing a class of bi-level optimization problems using gradient descent, specifically leveraging implicit gradients (combined with perturbation-based smoothing and adaptive step sizing). The authors could do a better job situating their work within the literature on implicit layers/differentiable optimization - in my impression, the existence of that literature serves to diminish some of the empirical contributions of the present work, but enhances the significance of some of the theoretical contributions.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: In this paper, the authors consider the problem of bilevel optimization when the lower level optimization (LL) problem is strongly convex and has to satisfy some linear constraints. The main issue with the constraints in the lower level optimization problem is that the solution of the LL problem might not be differentiable and hence applying standard gradient based method to the upper level optimization is not possible. The authors claim that:
  1. They provide a randomized smoothing procedure that makes the LL problem differentiable. Then they show that there is a way to compute the derivatives of the solution of the LL problem approximately and that this is enough for solving the bilevel problem.
  2. The authors then provide experiments that illustrate the advantage of their method compared to state-of-the art.
strength_and_weaknesses: Strengths
======================
  - The problem of finding provably convergent methods for bilevel optimization problems with constraints on the LL problem is very well-motivated.


Comments to the authors
========================

  Below I explain an issue that I have with the current presentation of the paper. I feel that I don't understand something very important and this makes it difficult for me to judge the overall contribution of the paper. Since ICLR gives us this opportunity I would like to first discuss about the following issue and if this is resolved I commit to updating fast my review to address the contributions of the paper.

  My issue is that I don't see how the addition of the term $q^T y$ makes the function $y^*(x)$ smooth. In particular, I don't even see how this works for the example in page 4. Let me explain with the following simpler example.

$\min_{x \in [0, 1]} x + y*(x) s.t. y^*(x) = \arg\min ((y - x)^2 | 1/2 <= y <= 1) (1)$

  This is almost the same example as in page 4 expect that I slightly changed the objective and the boundaries of y, which I don't understand why they are so complicated in the example in the paper. Now the solution $y^*(x)$ of the LL problem in $(1)$ is similar to the example of the paper. $y^*(x) = 1/2$ for $x <= 1/2$ and $y^*(x) = x$ for $x > 1/2$. So, indeed $y^*(x)$ is not differentiable at $x = 1/2$. Also, unless I am missing something, (1) satisfies Assumptions 1 and 2. Now let's consider the perturbed problem
  $y^*(x) = \arg\min {(y - x)^2 + q y| 1/2 <= y <= 1}$
  where $q$ is sampled from some distribution. In this case, the solution $y^*(x)$ becomes $y^*(x) = 1/2$ for $x <= (1 + q)/2$ and $y^*(x) = x$ for $x > (1 + q)/2$. So, $y^*(x)$ is still non-differentiable with some constant probability, assuming that the distribution of q has constant probability in the interval $[0, 1]$. The only thing that changed is the point where $y^*(x)$ is non-differentiable. I get exactly the same behavior when solving the example of page 4 in Mathematica it is just that the closed form solution is much more involved.

  The only way that I can see to make $y^*(x)$ smooth is if we define
  $y_q^*(x) = \arg\min 
9(y - x)^2 + q y| 1/2 <= y <= 1)$
  and then $y^*(x) = \mathbb{E}_q[y_q^*(x)]$, then maybe there is a way to show that $y^*(x)$ is smooth, at least this is indeed happening in the example of page 4 and the above example. But:
  1. the authors never mention that they take the expected value with respect to q, and
  2. looking in Algorithms 1 and 2, the authors seems to first sample q from its distribution and then proceed with a fixed value of q for the rest of the algorithm as if $y^*(x)$ is smooth. If they indeed want to take the expected value with respect to q then they need to get a different sample q every time they compute the gradient of $y^*(x)$. Also, they need to argue that this additional stochasticity does not affect their algorithm.

  I am very confused with the above. I apologize in advance if I am missing something trivial here and I am looking forward to your response.

(I apologize for the format issue in my review, I just realized and fixed it)
clarity,_quality,_novelty_and_reproducibility: See above.
summary_of_the_review:   Above I explained an issue that I have with the current presentation of the paper. I feel that I don't understand something very important and this makes it difficult for me to judge the overall contribution of the paper. Since ICLR gives us this opportunity I would like to first discuss about the following issue and if this is resolved I commit to updating fast my review to address the contributions of the paper.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: Authors extend implicit differentiation to constraint bilevel optimization problem. Assuming usual qualification conditions, they provide a implicit differentiation formula. Experiments are proposed on toy  bilevel problem, and real adversarial learning.

strength_and_weaknesses: Weaknesses:

**Literature review** Non-smooth optimization
- The provided results are very interesting and seems to extend older and more restrictive results [1] [3] [9]. More recent results on implicit differentiation for non-smooth problems also include [5] and [6].
- In particular, assumptions 1c and 1e seem to imply assumption 7 of [3] or assumption 2 of [4]. For Lasso-type problems, [1] and [3] restricts the linear system to solve only to the non-zeros coefficients (ie the non-active constraints in the dual). It seems that you observe the same kind of computational speedups for $\nabla {\bar \lambda}^*(x) $, but not for $\nabla_{y^*}(x)$. Could you comment on this?
- Related to the previous point, could you comment on the algorithmic complexity of the proposed methods? (formula in Lemma 2 for instance). It feels like one could inverse a linear system of size the dimension of the active constraints (using the tangent space of the projection operator as in [4])
- In the same vein, if the constraint in the inner bilevel optimization problem is rewritten as an indicator over a set, would it be possible to apply the framework of [4] to your problem?

**Literature review** Convex programming differentiation:
- It seems that other works previously obtained implicit differentiation for quadratic programming [7] and more general constrained optimization problems [8]. How does the proposed implicit differentiation formula compares to this previous approaches?


**Proposition 1**: Proposition 1 seems misleading to me, it requires Assumption 1 to be true for all $x$, which is very strong. It seems to me that Assumption 1 is true for almost every $x$, and thus the $x \mapsto G(x)$ is continuous by part, not on all $\khi$. Could authors comment on this.

**Assumption 3** is very strong, and is usually assumed only locally, see assumption 4 of [3], or Assumption 3 of [4].

**Experiments**
- I found it underwhelming that authors do not propose experiments on problem with non-separable matrix constraints. The proposed constrained problems are separable: on these examples one could use [3] and [4] to compute the hypergradient. **In other words: the problems considered in the experiments could be solved with preexisting techniques**.
- I think there are plenty of other interesting non-separable problems, I was wondering if authors considered experiments on more complex problems, and if authors planned to released open-source code, potentially compatible with pytorch?
- I am not sure what is the takeaway message from the *Adversarial Learning* part, could authors comment on it?


Typos:
p27 in appendix "Proof of theorem1" >> "Proof of Theorem 1"



[1] Mairal, J., Bach, F. and Ponce, J., 2011. Task-driven dictionary learning. IEEE transactions on pattern analysis and machine intelligence, 34(4)

[2] Deledalle, C.A., Vaiter, S., Fadili, J. and Peyré, G., 2014. Stein Unbiased GrAdient estimator of the Risk (SUGAR) for multiple parameter selection. SIAM Journal on Imaging Sciences, 7(4), pp.2448-2487.

[3] Bertrand, Q., Klopfenstein, Q., Massias, M., Blondel, M., Vaiter, S., Gramfort, A. and Salmon, J. Implicit differentiation for fast hyperparameter selection in non-smooth convex learning. JMLR 2022.

[4] Mehmood, S. and Ochs, P., 2022. Fixed-Point Automatic Differentiation of Forward--Backward Splitting Algorithms for Partly Smooth Functions. arXiv preprint arXiv:2208.03107.

[5] Bolte, J., Le, T., Pauwels, E. and Silveti-Falls, T., 2021. Nonsmooth implicit differentiation for machine-learning and optimization. Advances in neural information processing systems, 34, pp.13537-13549.

[6] Bolte, J., Pauwels, E. and Vaiter, S., 2022. Automatic differentiation of nonsmooth iterative algorithms. arXiv preprint arXiv:2206.00457.

[7] Amos, B. and Kolter, J.Z., 2017, July. Optnet: Differentiable optimization as a layer in neural networks. In International Conference on Machine Learning (pp. 136-145). PMLR.

[8] Agrawal, A., Amos, B., Barratt, S., Boyd, S., Diamond, S. and Kolter, J.Z., 2019. Differentiable convex optimization layers. Advances in neural information processing systems, 32.

[9] Bertrand, Q., Klopfenstein, Q., Blondel, M., Vaiter, S., Gramfort, A. and Salmon, J., 2020, November. Implicit differentiation of Lasso-type models for hyperparameter optimization. In International Conference on Machine Learning (pp. 810-821). PMLR

clarity,_quality,_novelty_and_reproducibility: The paper is fairly well written, idea is interesting, and the tackled problem is important.
summary_of_the_review: I think that differentiating efficiently constrained optimization problem is extremely important.
My current score is due to some important references missed in the literature review, as well as problems which can be solved with preexisting techniques in the experiments. **If authors solved these two issues (which can take some time I agree) I will raise my score**.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies a special class of bilevel optimization, where the inner problem has linear constraints. For this problem, one major difficulty is that outer (main) problem might be non-differentiable. The authors elegantly address this challenge by constructing a smoothed approximation of the original problem via adding noise to the inner problem. The show their smoothed version is a good approximation of the original problem, and has differentiable gradients. They then developed implicit gradient methods on the smoothed problem, and prove nice convergence rates for the original problem.  
strength_and_weaknesses: On the smoothing technique:
This paper proposes a very novel way of smoothing the constrained bilevel optimization problem by slightly perturbing the objective function of the inner problem. The perturbation only has a small influence on the main problem (Proposition 2), but it makes the problem smooth and differentiable. I think the idea is novel and interesting, and may also be useful in other related optimization problems.


On the convergence guarantees: 
1)	The non-convex non-smooth problem is in general NP-hard, and it is a bit supervising that the algorithm can still converge to the stationary point (Although asymptotically). But I have a hard time understanding Theorem 1, especially the definition of $hat{d}^r$. Can the authors help me understand this condition (e.g., intuitively, what is $hat{d}^r$? and why the algorithm can still converge when the problem is non-convex non-smooth)?
2)	On the other hand, when the functions are non-smooth by convex/strongly convex, I am not sure about the significance of the proposed algorithm: It seems to me that, now since we have a closed form of gradient, we could just to GD (or other more advanced algorithms) and still have similar rates. What are the advantages of the proposed methods? 

On the writing: 
This paper is in general very easy to read. 


Other comments:
This work reminds me of Nesterov’s excessive gap technique [1]/ Nesterov’s smoothing technique [2] for bilevel (min-max) constrained optimization problem. For the inner function, they added a smoothed regularizer to smooth the function instead of using perturbation. Moreover, some recent work shows that in some cases perturbation and regularization are strongly related [3]. I wonder if the authors could add some comments on this point? 



[1] https://epubs.siam.org/doi/pdf/10.1137/S1052623403422285
[2] Smooth minimization of non-smooth functions. 
http://luthuli.cs.uiuc.edu/~daf/courses/Optimization/MRFpapers/nesterov05.pdf
[3] Perturbation Techniques in Online
Learning and Optimization https://dept.stat.lsa.umich.edu/~tewaria/research/abernethy16perturbation.pdf

There are two definitions of y^*(x) (1b and 5b), one is the exact inner solution and the other one is the approximation. I wonder if the authors could use different notions for the two to make it more clear?

clarity,_quality,_novelty_and_reproducibility: See above. 
summary_of_the_review: I find the smoothed technique for constrained bilevel optimization is novel and interesting, and I vote for acceptance.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: In this paper, the authors consider the problem of bilevel optimization when the inner optimization problem is strongly convex and has to satisfy some linear constraints.

Strengths:
- The approach is simple
- The experiments demonstrate the efficacy of the proposed method

Weaknesses: 
- As pointed out by reviewer gXua, and agreed by the authors themselves, Lemma 5 is currently not applicable in the proofs of Theorem 1 and 2: the proof is incomplete

The authors say that they will add an assumption that all the intermediate points of the algorithm are differentiable for their proof to be complete. As pointed out by reviewer gXua (1) such an assumption defies the whole purpose of the paper which was to make the function  smooth, and (2) it should be possible to be proven, so it is worth to wait for a newer version that includes this proof as well (rather than using an assumption).

Therefore, while the paper is promising, we believe it is not ready for publication in its current state and recommend rejection.
justification_for_why_not_higher_score: Incomplete proof for Theorem 1 and 2
Decision: Reject