Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper studies the nonconvex outer-objective and strongly convex inner-objective bilevel optimization problem through the lens of Bregmen distance. The paper covers the deterministic optimizaton and stochastic optimization. in both situation, the authors provide the algorithm and its convergence analysis. The theoretical results shows the proposed algorithm with the aid of Bregman distance improve the performance with respect to the condition number $\kappa$ and utilizing the variance reduction technique could further improve the dependency on $\epsilon$ with a order of $\frac{1}{2}$. The numerical experiment further prove the efficiency of the proposed algorithm.
strengths_and_weaknesses: The strengths of the paper is obvious that it proposes the algorithms that could improve the theoretical upper-bound of previous state-of-the-art results, the presentation is clear, and the numerical experiment is sound.

The weaknesses mainly because the improvement is predictable. It is well-known that the variance-reduction technique could improve the oder w.r.t. the accuracy $\epsilon$, and the Bregman disctance helps with the condition number $\kappa$.
questions: Q1: On the algorithmic design side, is there any extra effort that we need to make rather than directly replace the exact gradient with the gradient estimations? If it need some specific design, I would like to increase my score.

Q2: On the theoretical side, is there any extra effort other than incorporating the biases introduced by the gradient estimation? I would like to increase my score of rating if so.
limitations: The numerical verifications of the problem is limited, for each algorithm, we only have one experiment. The experiment shows the proposed algortihms have lower losses. It would be better if the authors provide more experiments. I would like increase my score if the author could provide more experimental results during rebuttal.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper incorporate the Bregman distance into bilevel optimization and propose three methods (BiO-BreD, SBiO-BredD, ASBiO-BreD) which targets at addressing deterministic and stochastic bilevel problem. Such proposed algorithms have matched best target accuracy $\epsilon$ and improved the condition number $\kappa$ compared with other benchmarks. Meanwhile, such analysis is adaptable for nonsmooth outer function. The experiments also demonstrate the superior performance of proposed algorithms.
strengths_and_weaknesses: In terms of strengths, the proposed work shows the condition number improvement in terms of convergence analysis. Meanwhile, in different experimental settings, the proposed algorithms have demonstrated its superior performance individually. Both assumptions and convergence analysis are standard and easy to follow.

In terms of weakness, several Lemmas (Lemma2, Lemma4) in main body lack explanations. The theoretical analysis is very standard while it will be better to point out the technical innovations.
questions: 1. It will be better to include explanations for different Lemmas which can help reader to know what is the meaning behind each lemma in main body.

2. It will be better to discuss the technical innovations compared with previous work [21].  Note that [21] refers to different works in main body and supplementary.

3. It will be better to include a short ablation studies to compare current algorithms performances in different settings. (e.g. different batch sizes). 

4. The algorithm is analyzed in non-smooth function space while the experiments are based on smooth function. It will be better to try non smooth experiment. 
limitations: Non negative societal impact.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper proposes a new class of bilevel optimization (BO) problems both in deterministic and stochastic forms. Compared to the classic BO problem, their outer function has an additional nonsmooth term, which makes their model more general, e.g. it contains the case when we use $L_1$ regularization.

Then three algorithms are proposed. The first two are used to solve deterministic/stochastic BO problems (in the new form) respectively. And the last one is an accelerated version of the second algorithm.
strengths_and_weaknesses: Strengths: 1) this paper broadens the class of BO problems that appeared in previous literature which leads to the demand for new algorithms (because previous algorithms can not deal with non-smooth outer function); 2) under similar assumptions compared with related works, the algorithms proposed in this paper achieve the best convergence rate with known condition number

Weaknesses: 1) This paper only mentions one circumstance where we need to consider a non-smooth outer function (when we use $L_1$ regularization).  That may narrow the unique field of application of this work, i.e. this work can do but the previous works can not. It is good to mention more examples/applications of using non-smooth objectives. 

questions: 1) It is not very clear how to compute the partial derivative $\omega_t$ in Algorithm 1 line 8. Maybe more explanation is needed.

2) In Algorithm 2, the usage of $\eta_t$ may need more explanations. Why the step size is $\lambda \eta_t$ however in Algorithm 1 $\lambda$ is used?

3) It is nice that in both the theoretical and experiment parts, the performance of proposed algorithms is better than baseline algorithms. But where does this improvement come from? When compared with baseline algorithms, I guess $h(x) = 0$, then the major difference is the usage of Bregman distance. Does it account for the improvement? If the authors can find more explanations, this work may have more theoretical value.
limitations: The efficiency of proposed algorithms depends on the choice of $\psi$, which is used to define Bregman distance.  In the experiment part, it is chosen such that the updating of $x$ is very easy, i.e. a closed-form solution exists when $h(x) = 0$.  But when other $\psi$ is chosen or $h(x) \neq 0$, how to efficiently solve the problem to update $x$? The complexity of solving this subproblem seems does not appear in the comparison with other algorithms. Maybe the authors can make it more clear how to solve this subproblem for general $h(x)$.
review_title: null

Meta-review: metareview: The paper studies bilevel optimization problems, provides three algorithms for different settings, and improves the convergence analysis in terms of the condition number. In addition, numerical experiments are conducted that provide illustration of the effectiveness of the algorithms. Three reviewers all agree that the paper should be published as it contributes to the literature and will be of interest to the NeurIPS audience. 

When preparing the final version of the manuscript, please incorporate the discussion that addressed the reviewers' comments either in the main text or the appendix. 
confidence: Certain
Decision: Accept