Projection-Free Methods for Stochastic Simple Bilevel Optimization with Convex Lower-level Problem

Summary

A nice and clean result for stochastic simple bilevel optimization. The manuscript extends the algorithm design from the deterministic simple bilevel optimization with convex lower-level problem to the stochastic setting and demonstrate the sample complexity, which seems to be near-optimal (ignoring the log factor) when restricting the problem to classical stochastic optimization setting.

Strengths

New results with good quality that are demonstrated in a nice and clean way. The motivation is very clear. It may push forward the study of general stochastic bilevel optimization when the lower-level is non-singleton.

Weaknesses

The manuscript has no major flaws. The idea to add a $K_t$ and to estimate g using samples are rather straightforward though. The motivation for using variance reduction are not well-explained. Using variance reduction for lower level is to ensure that decaying $K_t$ makes sense. This step I doubt if it is possible to only use moving average estimator [Chen et al., 2021 NeurIPS, Closing the Gap: Tighter Analysis of Alternating Stochastic Gradient Methods for Bilevel Problems] on the lower-level problem to achieve the same effect. Using variance reduction for upper level is to obtain the current complexity bound. Otherwise, using vanilla Frank-wolfe on the upper level will result in larger complexity. But nevertheless, the manuscript already provides a full story. So that the algorithm would requires less hyperparameter to tune. See my questions below.

Questions

1. Throughout your discussion of related literature and contributions, please accurately denote if the reference or contribution pertains to simple stochastic bilevel optimization or the broader general stochastic bilevel optimization. This applies to numerous instances, such as Line 139 and Line 45. 2. Regarding Line 103, is it $A\subset \mathbb{R}^m$ or $a_i\in\mathbb{R}^m$? There appears to be a typographical error. 3. How are $p$ and $q$ determined in continual dictionary learning? Do the old dataset $A$ and the new dataset $A^\prime$ have any correlation? If uncorrelated, why merge them? If correlated, would the results still hold? 4. In the 'Random set for the subproblem' subsection, is there a missing $\hat $ on $g(x_0)$? How is $g(x_0)$ known? This query also applies to equations (8)(9) and Algorithms 1 and 2. 5. Lemma 4.1 seems to miss a space in "c, (d is ". Additionally, why does the estimation error in Lemma 1 depend on the dimension? In other variance reduction papers, like STORM and SPIDER, the estimation error is generally dimension-independent. 6. In Theorem 1 and 2, $\mathcal{G}$ is not defined anywhere in the main context. 7. My understanding of general bilevel optimization implies variance reduction aims for $O(\epsilon^{-4})$ complexity bound in the nonconvex regime ($O(\epsilon^{-3})$ with variance reduction). However, Chen et al., 2021 [NeurIPS, closing the gap, tighter analysis] indicated that variance reduction isn't essential for achieving optimal complexity in strong and convex settings. Moreover, for nonconvex settings, an $O(\epsilon^{-4})$ rate can still be obtained without variance reduction. Therefore, I question whether variance reduction is genuinely necessary when $\hat{\nabla g}$ can be adaptively estimated using a moving average estimator, possibly achieving the same rate. This could be an avenue for future consideration.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

The authors have adequately addressed the limitations and there is no societal impact involved as it is a pure theoretical work.

Summary

The paper presents a novel approach for solving stochastic simple bilevel optimization problems. The authors develop new methods that locally approximate the solution set of the lower-level problem using a stochastic cutting plane and then employ a conditional gradient update with variance reduction techniques to manage error from stochastic gradients. The specific contributions are: - For the convex upper-level function case, the proposed method requires ${\tilde{\mathcal{O}}}(\max ( 1/\epsilon_f^2, 1/\epsilon_g^2 ) )$ stochastic oracle queries to find a solution that is $\epsilon_f$-optimal for the upper-level and $\epsilon_g$-optimal for the lower-level. This is a substantial improvement over the previous complexity of $\mathcal{O}(\max(1/\epsilon_f^4, 1/\epsilon_g^4))$. - For the non-convex upper-level function case, the method requires at most ${\tilde{\mathcal{O}}}(\max(1/\epsilon_f^3, 1/\epsilon_g^3))$ stochastic oracle queries to find an $(\epsilon_f, \epsilon_g)$-stationary point. - In the finite-sum setting, the method requires ${\tilde{\mathcal{O}}}(\sqrt{n}/\epsilon)$ and ${\tilde{\mathcal{O}}}(\sqrt{n}/\epsilon^2)$ stochastic oracle calls for the convex and non-convex settings, respectively, where $\epsilon= \min(\epsilon_f,\epsilon_g)$.

Strengths

- Originality: In this paper, the idea of using cutting planes to approximate the optimal solution set for solving deterministic simple bilevel optimization is extended to the stochastic version. Due to the stochastic nature of the problem, this generalization is not trivial. - Quality: From a theoretical standpoint, the quality of the research is notable, with the authors demonstrating a substantial improvement over previous complexity results. - Clarity: The overall structure of the paper is clear. - Significance: This research provide lower complexity guarantees for stochastic simple bilevel optimization.

Weaknesses

- The authors make an assumption that the constraint set $\mathcal Z$ is compact and convex, which may not hold for many real applications. This strong assumption limits the method's applicability. - In their experiments, the authors employ the number of samples as the measure on the abscissa axis without providing a clear rationale for this choice. Furthermore, a comparative analysis of the time efficiency across various methods is missing, which should ideally be included to give a more comprehensive evaluation of their approach. - The paper contains numerous typographical errors which, although not affecting the technical content, detract from the overall readability and professionalism of the paper. - In Example 1, the authors do not clearly delineate how randomness is incorporated and why it necessitates the use of stochastic simple bilevel optimization as a modeling approach for this particular problem.

Questions

- Line 15 and elsewhere: The authors discard the logarithmic terms in the complexity results. I suggest the authors use $\tilde{\mathcal{O}}$ to hide the logarithmic terms. - Line 46: The authors state that their approach is ``tight". Why? - Example 1: The paper doesn't clarify where the element of randomness lies, nor does it explain why the problem specifically requires a stochastic simple bilevel optimization model. - Line 156, the formula (8): How to compute the exact $g(x_0)$? - Line 158: Why is there $\hat{g}(x_0)$ instead of $g(x_0)$? - Algorithm 1, Line 7; Line 160, the formula (9); Line 163 and elsewhere: The notations $\mathcal{X}_t$, $\hat{\mathcal{X}}_t$, $\mathcal{X}_t^{S}$ should be unified. - Line 177: The citation (7) should be (9). - Line 226, the formula (16): The term $\sqrt{\log(6/\delta)}$ should be changed to $\sqrt{\log(6d/\delta)}$. - The authors state that $\omega=1$ and $\omega=2/3$ are the ``best'' choice for the convex and nonconvex settings, respectively. How to ensure that the choices are the best? - Lemma 4.2 and Lemma 4.3: The authors could swap the places of these two lemmas and rewrite Lemma 4.2 to be more precise. - Line 238, the last sentence: add "we" before "establish". - In numerical experiments: Why do the authors use the number of samples be the abscissa axis? The paper doesn't include a comparative analysis of the time efficiencies across different algorithms, an omission that needs clarification. - Line 316: The matrix $D^{'*}$ is not clearly defined. - In Supplementary material: Many formulas are numbered but not cited, please consider removing these numbers. Sometimes the paper doesn't provide an explanation for the validity of two adjacent formulas. An appropriate clarification would be helpful for understanding. - Line 479: The $S$ in the formula should be changed to $s_2$. - Line 480 and elsewhere: The use of both "t" and "T" in the paper could lead to confusion. To avoid this, the authors could consider replacing one of them, such as changing "T" to "M". - Line 482 and elsewhere: The "$\alpha$" should be replaced by "$\omega$". - Line 526: the citation (47) is not correct. - Line 563, the formula (55) and elsewhere: The term $g(x_t)-g(x_0)$ should be $(g(x_t)-g(x_0))$. - Line 565, the formulas and elsewhere: The subscript $t+1$ in $g(x_{t+1})$ in the formula does not match the subscript $t$ in $g(x_t)$ in the theorem. This situation occurs many times in the proofs of theorems. - Line 567, the formula (57) and elsewhere: The Lipchitz constant $L_g$ should be replaced by $L_f$. - Line 677: The number $40$ should be replaced by $50$.

Rating

4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

2 fair

Presentation

2 fair

Contribution

2 fair

Limitations

NA

Summary

This paper introduces novel projection-free optimization methods for solving a class of *simple* stochastic bilevel optimization problems. The proposed methods are based on the conditional gradient algorithm and use variance reduction techniques to approximate the solution set of the lower-level problem. The paper provides theoretical guarantees for the convergence of the proposed methods and analyzes their sample complexity. The methods are shown to be efficient for both convex (global convergence) and non-convex upper-level (local convergence) functions.

Strengths

The paper introduces a new framework for solving a class of stochastic bilevel optimization problems, which is an important and challenging problem in optimization. The proposed methods are shown to be efficient in experiments and have theoretical guarantees.

Weaknesses

I am concerned that the paper makes no reference to the game theory literature on the topic (general-sum Stackelberg games). Related work on the topic would make the work accessible to a broader audience.

Questions

Questions: Can you describe how we can see this optimization problem from a game theory perspective?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

NA

Summary

This paper proposes methods for solving nonconvex/convex-convex simple bilevel optimization problems. The proposed methods are proven to have better non-asymptotic convergence guarantee than existing works. Numerical experiments are done on two applications to verify the effectiveness of the proposed methods.

Strengths

The main contribution of this work is the improved convergence rates for solving nonconvex/convex-convex simple bilevel optimization problems. The proposed methods use a cutting plane to approximate the solution set of the lower-level problem, of which the solution may not be unique. In order to have a more accurate approximation, the work proposes to use variance reduced estimators (STORM for stochastic setting and SPIDER for finite-sum setting) for gradient and function value estimations.

Weaknesses

1. In the related work section, line 69~71 says that existing works on solving general bilevel optimization only consider strongly convex lower-level problems. This statement is not true. There have several works done on studying general bilevel optimization without strong convexity condition of lower-level problems. Just to name a few: (Liu et al., 2021), (Sow et al., 2022), (Shen et al., 2023), etc. Since these works are solving general bilevel optimization, they are potentially applicable to the simple bilevel optimization. I believe it is reasonable to provide a more detailed discussion on how these existing works are/aren't applicable to the target formulation of this draft. 2. I notice that the algorithm SBCGI uses only one sample data per iteration, and the sample data batch size in algorithm SBCGF is fixed to $\sqrt{n}$. In general, fixed batch size is often not very practical, especially for large dataset. I wonder if the authors have any insights on why the batch size cannot be set arbitrarily and be a dependency parameter in the convergence rate. 3. Typo: in line 73, one->on. References: Risheng Liu, Yaohua Liu, Shangzhi Zeng, Jin Zhang, Towards Gradient-based Bilevel Optimization with Non-convex Followers and Beyond, 2021. Daouda Sow, Kaiyi Ji, Ziwei Guan, Yingbin Liang, A Primal-Dual Approach to Bilevel Optimization with Multiple Inner Minima, 2022. Han Shen, Quan Xiao, Tianyi Chen, On Penalty-based Bilevel Gradient Descent Method, 2023.

Questions

Please see the weaknesses section.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

The fixed batch size limits the proposed methods from applying on large-scale datasets.

Discussion period

Dear reviewers and authors, Thank you very much for your work on this submission and its evaluation. Now that the authors have responded to the reviews, I *strongly encourage* the reviewers to acknowledge the review, to look at other reviews and rebuttals for this submission, and to adjust their scores if needed. Thanks to those that have already done so. Authors have the possibility to reply if further questions are needed, until the 16th. Thank you very much to all, Area Chair