Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This work focus on adaptive frameworks for bilevel optimization. It first introduce BiAdam that achieves $\tilde{O}(\epsilon^{-4})$ complexity. Then it introduces BiAdam with variance reduction and achieves $\tilde{O}(\epsilon^{-3})$ complexity. Both results matches  state-of-the-art complexities.  
strength_and_weaknesses: strengths: 


a) The complexities matches the previous results, and the algorithm does not need a mini-batch


b) The algorithm can be used in the setting with constraints.


weaknesses:


a) The novelty in this paper is quite limited. The results are built on the large body of bi-level optimization literature and super-ADAM. Noticeable, there are already many works for bi-level optimization can achieve the same complexities. 

b) The adaptive framework is not very meaningful here. Note that all the adaptivity is absorbed in the matrices $A_t$ and $B_t$ in the algorithms. The stepsize can be considered to be inversely related with eigenvalues of matrices. In Assumption 7, it assumes $A_t \succeq \rho I_d$ and $B_t=b I_p\left(b_u \geq b \geq b_l>0\right)$, which basically indicates stepsize for $x$ is upper bounded and stepsize for $y$ is lower and upper bounded. Then by controlling the other parameters in the stepsizes, e.g., $\lambda$ and $\gamma$, the stepsizes  can be treated just like non-adaptive stepsizes. Therefore, the analysis does not need too much novelty to accommodate adaptive stepsize, e.g., Lemma 10.  This leads to some drawbacks: 1) upper and lower bounds for adaptive matrices $A_t$ and $B_t$ need to be know in order to pick other hyperparameters, 2) usually, $\rho$ in Adam is chosen to be very small just for stability. But when $\rho$ is small, Theorem 1 needs a very small $\gamma$ which may reduce the gain from Adam stepsize. 
clarity,_quality,_novelty_and_reproducibility: clarity: typo in the abstract, "mate learning" -> "meta learning. 


summary_of_the_review: The results in this paper is reasonable, but it may lack novelty.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: Inspired from Adam, authors propose adaptive bilevel algorithms, and a variance reduced variation, coined "biAdam" and VR-BiAdam. They show respectively $1/\epsilon^4$ and $1/\epsilon^3$ convergence rate. Authors propose experiments on data hypercleaning and hyperrepresentation learning

strength_and_weaknesses: Major concerns:
- I have doubt about the practical impact of the proposed work, as many bilevel optimization problems, it requires to select $3$ sequences of stepsize $\eta_t, \alpha_t, \beta_t$. To me, it seems very unclear how to select these parameters in practice.
- I also have doubt about the theoretical impact of the paper "Our VR-BiAdam algorithm reaches the best known sample complexity of $1/\epsilon^3$". A recent paper [1] managed to prove $1/\epsilon^2$ rate for a single loop algorithm. Could authors comment on this?

[1] Dagréou, M., Ablin, P., Vaiter, S. and Moreau, T., 2022. A framework for bilevel optimization that enables stochastic and global variance reduction algorithms. NeurIPS2022

clarity,_quality,_novelty_and_reproducibility: Paper is clear, and the idea seems new
summary_of_the_review: I have doubts on the practical and theoretical impact of the paper
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper proposed efficient adaptive bilevel optimization methods based on the momentum techniques for the nonconvex-strongly-convex bilevel optimization. It provided the solid convergence analysis for the proposed methods, and proved that these methods obtain the best-known complexity. The experimental results on data hyper-cleaning and hyper-representation learning tasks demonstrate the efficiency of the proposed algorithms.
strength_and_weaknesses: Strength:

This paper proposed efficient adaptive bilevel optimization methods based on momentum techniques for the nonconvex-strongly-convex bilevel optimization. It provided the solid convergence analysis for the proposed methods, and proved that these methods obtain the best-known complexity.

Weakness:

The parameters in adaptive matrices maybe depend on the tuning parameter in the proposed algorithms.

clarity,_quality,_novelty_and_reproducibility: The novelty of this article is that it studied the adaptive bilevel methods for the nonconvex-strongly-convex bilevel optimization and provided solid theoretical analysis. This article is well-organized and easy to understand.
summary_of_the_review: This paper proposed efficient adaptive bilevel optimization methods based on momentum techniques for the nonconvex-strongly-convex bilevel optimization. It provided the solid convergence analysis for the proposed methods, and proved that these methods obtain the best-known complexity. The experimental results on data hyper-cleaning and hyper-representation learning tasks demonstrate the efficiency of the proposed algorithms.

Some Comments:

1. It would be great if the authors would write how they can solve the subproblems in lines 5 and 6 of Algorithms 1-2. 

2. What is the intuition to use the momentum steps in the lines 5-6 of Algorithms 1-2? 

3. These momentum steps improve the sample complexity in the proposed algorithms?

4. In Theorem 6, the term $\sqrt{\frac{1}{T}\sum_{t=1}^T\mathbb{E}\|A_t\|^2}$ is bounded?

5. How to choose the adaptive learning rates of Algorithms 1-2 in the experiments?
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper proposed a class of efficient adaptive bilevel optimization methods based on momentum techniques to solve the nonconvex-strongly-convex bilevel optimization problems. Moreover, it studied the convergence properties of the proposed methods, and provided the solid convergence analysis. It also conducted the empirical experiments on data hyper-cleaning and hyper-representation learning tasks to verify the efficiency of the proposed algorithms.
strength_and_weaknesses: **Strength:**

This paper proposed a class of efficient adaptive bilevel optimization methods, which build on the unified adaptive matrices and momentum techniques. Moreover, it provides the solid theoretical analysis for the proposed algorithms, and proved the proposed algorithm reaches the best known sample complexity.

**Weakness:**

The proposed algorithms have many tuning parameters.
clarity,_quality,_novelty_and_reproducibility: This paper is well written. The novelty of this paper is that it proposed the adaptive gradient-based methods for nonconvex-strongly-convex bilevel optimization and it also provided solid convergence convergence.
summary_of_the_review: This paper studied the adaptive bilevel methods for the nonconvex-strongly-convex bilelve optimization. One of the main contribution of this paper the the theoretical analysis for the proposed adaptive gradient-based methods for bilelve optimization. Experimentally, the proposed algorithms outperform various algorithms in data hyper-cleaning and hyper-representation learning tasks. 

Some Questions:

1. Why use the momentum steps in the lines 5-6 of Algorithms? 

2. Why the norm of adaptive matrix has a lower bound in Assumption 7?

3. Why the authors choose the decreasing parameter $\eta_t$ ? Could we choose the 
constant parameter $\eta_t$ in the proposed algorithms ?

4. How to choose the tuning parameters in the proposed Algorithms ?

5. The convergence analysis does not show the advantage of the adaptive gradient method since 
it does not exploit the specific coordinate-wise adaptive stepsize used by Adagrad? In the best case, the convergence can be as good as the non-adaptive gradient descent ascent.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper studies stochastic bilevel optimization problems where the outer objective function is possibly non-convex and the inner objective function is strongly convex. Prior works only consider the unconstrained setting and propose algorithms with non-adaptive step sizes. The paper introduces an algorithmic framework based on Adam that leverages adaptive step sizes and it supports general constraints. The core algorithm is then combined with momentum-based variance reduction. The convergence guarantees for the core algorithm and its variance-reduced counterpart match the best-known convergence guarantees.

The reviewers' opinions were divided, with two reviewers being positive about the paper and supporting accept and two reviewers being concerned about the novelty of the contribution and its practical applicability. The ability to handle general constraints was appreciated by the reviewers. The main concerns about the novelty were that there already exist several works for bilevel optimization that attain the same convergence guarantee and, although incorporating adaptive step sizes into the framework is a valuable contribution, it is fairly standard and straightforward to do. The main concerns about the practical applicability were that the algorithm has many parameters that need to be tuned and assumes knowledge of suitable upper and lower bounds on the eigenvalues of the adaptive matrices.
justification_for_why_not_higher_score: The novelty and practical applicability of the algorithm is limited.
Decision: Reject