BiSLS/SPS: Auto-tune Step Sizes for Stable Bi-level Optimization

Summary

This paper studies the bilevel optimization problem, an in particular, focuses on developing effective learning rate schemes for bilevel optimization. In specific, the authors propose two adaptive step-sizes methods named stochastic line search (SLS) and stochastic Polyak step size (SPS) as variants of methods such as SPSmax and DecSPS. Compared to existing approaches, the proposed methods do not require the step-sizes to be monotonic by replacing the constant $\gamma_{b,0}$ by a non-increasing $\gamma_{b,k}$. The adaptive stepsizes are further applied to bilevel optimization on both upper and lower levels. The convergence analysis is provided for SPS and SLS on single-level problems and also for bilevel problems. Simple experiments are provided.

Strengths

1. Studying adaptive learning rates in bilevel optimization is interesting, and has not been explored well in the literature. 2. The proposed adaptive learning rates are more practical than existing methods like SPSmax and DecSPS with milder requirements.

Weaknesses

1. The paper is well written and hard to follow. For example, there are quite a few assumptions and requirements in the paragraphs of describing the proposed methods. There are also many notations and inequalities in Section 2. It makes me a little bit hard to follow the principle of the designs. 2. The adaptive learning rates seem to introduce more hyperparameters such as $l^*_{i_k}, c_{k},\gamma_{b,k}$. It makes me wonder how it can be meaningful in practice given more efforts in tuning such parameters. In addition, no sensitivity analysis is provided for such parameters in experiments. 3. How to find the approximate $l^*_{I,k}$ of the lowest function value? Is the choice of this quantity important in terms of performance? A more comprehensive empirical justification should be provided. 4. In terms of the complexity, it seems to me the proposed stepsizes cannot provide improved sample or computational complexity in theory. Maybe I miss something, but I think the authors can elaborate on this 5. The experiments are not convincing enough. Since the biggest motivation lies in the design of adaptive learning rates, the benefits may come from the empirical side. Thus, it would be better to provide more comprehensive experiments on practical NN architecture and larger datasets for the validation. However, the current experiments are rather toy examples. If the contribution lies in the theoretical side, it fails to show improved complexity performance. Overall, I like the topic of adaptive learning rate for bilevel problems. However, the current theory and experiments are not convincing enough, and how important the proposed methods also are not clear to me. For this reason, I am on the negative side for the current version. I am also open to change my mind if more convincing experiments (e.g., how to select extra parameters, more datasets and backbones, sensitivity analysis, more problems) can be provided.

Questions

Please see Weakness part.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited 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

3 good

Presentation

2 fair

Contribution

2 fair

Limitations

Please see Weakness part.

Summary

This paper presents an adaptive step size algorithm for bi-level optimization, which improves the shortcomings of the existing BO method that requires careful adjustment of the upper and lower learning rate, and gives a proof of convergence. Experiments also verify the robustness of the method to learning rate.

Strengths

1.This paper presents an adaptive and robust bi-level optimization algorithm for adaptive step size, which can obtain a good set of step sizes without prior knowledge and careful modulation. 2.This algorithm is compatible with the accelerated solver Adam in addition to SGD, improving computational efficiency. 3.The analysis framework of this algorithm more generally unifies SPS and SLS.

Weaknesses

1.Theorem 1 only states that f is convex rather than strongly convex, but the full text lacks explanation for the case of multiple solutions at the lower level 2.Potential computational burden. Although the author states that only a small number of matrix vector multiplication and addition operations are usually used to approximate matrix inverses, this still implies additional computational complexity and there is a problem: the trade-off between the performance loss caused by approximation and the improvement of computational efficiency. Specifically, the lack of time analysis in the charts in the paper exacerbates this concern.

Questions

1.The drawing of figure is difficult to read. For example, the line of beta=10.0 in Figure 1 is not fully drawn, different colors and lines are mixed in Figure 2 but have no additional meaning, and the second half of the right subgraph in Figure 3 is too complex, resulting in some lines being unrecognizable. 2. The light colored parts in the figure do not seem to represent the three standard deviations, but rather the upper and lower bounds? 3.I noticed that the sequence of upper and lower bounds for the declared step size in the paper needs to be appropriately controlled, so my point of interest is whether the decay rate is not 1/ sqrt {k+1}? Or can I change the decay rate to change the rate of convergence?

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.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some 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

3 good

Contribution

3 good

Limitations

Yes, the author clearly stated the assumptions of the algorithm.

Summary

This work studies adaptive step-size methods for both single-level optimization and bilevel optimization. The authors propose two novel variants of stochastic line search (SLS) and stochastic Polyak step size (SPS), and they unify these variants into a general envelop strategy. Importantly, these variants are simpler to implement and demonstrate good empirical performance, particularly in non-interpolating scenario. By using the unified envelop strategy, the authors also propose a bi-level line-search algorithm BiSLS-Adam/SGD with convergence guarantees, which demonstrates empirical robustness and generalizes well.

Strengths

1. Both adaptive step-size methods and bilevel optimization are currently active topics. The investigation of auto-tune step sizes for bilevel optimization algorithms is under-explored, and the studied topic in work is interesting and important. 2. The illustrations in Figures 1-5 are helpful in understanding the contributions. 3. The newly proposed variants of stochastic line search (SLS) and stochastic Polyak step size (SPS) in this work are novel and easy to understand. Moreover, these variants can be unified into a general envelop-type step size, and their effectiveness in the context of single-level optimization and bilevel optimization is well-supported by theoretical results and extensive experiments.

Weaknesses

See the Limitations below.

Questions

Q1: Can the authors explain in more details why it is possible to set the number of inner steps to be 1 in Line 213? Minor Comments: 1. For Equation (2), the $+$ should be $-$. 2. In Equation (13), $\nabla_y^2 yg$ should be $\nabla_{yy}^2 g$. 3. In Line 175, $\nabla f_x$ should be $\nabla_x f$. 4. The quadratic functions in Figure 2 and Section B.1 do not satisfy the gradient bounded assumption in Assumption 2. 5. The $+$ in Equation (17) should be $-$.

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed 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

4 excellent

Limitations

The authors discussed some of the limitations on single-level optimization in the conclusion section of the paper. On bilevel optimization, a limitation is the lower-level strong convexity in Assumption 3. It would be of interest to investigate whether this condition can be relaxed or removed, taking into account recent advancements in the field, such as those presented in [1, 2,3]. [1] B. Liu et al. “Bome! bilevel optimization made easy: A simple first-order approach.” NeurIPS 2022. [2] R. Liu et al. “Averaged Method of Multipliers for Bi-Level Optimization without Lower-Level Strong Convexity.” ICML 2023. [3] H. Shen and T. Chen, “On penalty-based bilevel gradient descent method.” ICML 2023.

Summary

The paper introduces the use of stochastic adaptive-step size methods, namely stochastic Polyak step size (SPS) and stochastic line search (SLS), for bi-level optimization. This approach addresses the challenge of tuning both the lower and upper-level learning rates.

Strengths

1. SLS and SPS can be seen as special instances of general family of methods with an envelope-type step-size. 2. The unified envelope strategy enables the algorithm development and convergence analysis.

Weaknesses

The paper compares the proposed algorithms to vanilla SGD or Adam versions, but it does not provide a comprehensive comparison with other existing algorithms for bi-level optimization. This may limit the understanding of the relative performance of the proposed algorithms in the broader context.

Questions

What is the overhead of using the proposed algorithm to tune the step size?

Rating

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

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some 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

3 good

Contribution

3 good

Limitations

N/A

Thanks for the response

I thank the authors' rebuttal, and I increase my score to 5.