Penalty-based Methods for Simple Bilevel Optimization under Hölderian Error Bounds

Summary

This article presents a nice extension to the broad class of penalty method problems, particularly for the case when the objective functions have a Hölderian error bound. This assumption for this class of problems appears new, and a thorough coverage of interesting results are claimed.

Strengths

- New results presented for bilevel optimization for the Hölderian error bound setting - New relationships between the minimizers of a penalty problem and the exact problem; this is a particularly mature field, and finding new results here is meritorious. - Presentation of a standard prox-based method for solving these bilevel problems with their new theory, with complexity details explained.

Weaknesses

- The article does not distinguish between what type of subdifferential is used. Since the authors also make a mention of the applicability of their results to nonconvex objectives, this is crucial point. Many classical results in optimization and convex analysis are proven using the *convex* subdifferential; however, even for differentiable nonconvex functions (e.g., $-x^2$), the convex subdifferential is empty, while other notions like the Clarke subdifferential is nonempty. - Assumption 3.2 is a very strong one; while I agree with the author(s) that the prox of a sum is widely studied, the list of settings in which one can compute this is still quite limited. However, this is not a major drawback for me, since handling HEB bilevel optimization even in the L-smooth setting appears to be new. - In my opinion, leaving lines 140--142 to stake claim to results for non-convex which are exclusively in the appendix seems improper. The appendix is technically "unreviewed" material; if the formal statement of the result cannot fit into this article, then I do not think it is worth including. I suggest that the authors either try to find a way to incorporate these results into the article (since they are indeed quite interesting), or save the results for another work. - The graphs of the numeric are too small for me to read, especially in-print. Minor comments: - The fact that the argmin of a convex lsc function is closed and convex is a classical result which has been known for decades, so it seems odd to cite [Beck and Sabach, 2014] instead of a classical book, or the article where it was first proven. - The article makes mention to functions $f_2$, $g_2$ far before they are introduced, which is confusiung to the reader. - Names "Pock, Tseng, etc." are not capitalized in the citations. - Citation on lines 391-392 is missing volume number.

Questions

The classical article on penalty methods, Dmitri P. Bertsekas, "Necessary and Sufficient conditions for a penalty method to be exact", Math. Program., vol. 9, pp. 87 - 99, 1975. basically states that, if the penalty function is smooth near the solution set, then the penalty must go to infinity in order to achieve exact penalization; and, if the penalty function is nonsmooth near the solution set, then a finite penalty will suffice. My question is: are your results consistent with this article? In particular, - In the setting where $G$ is smooth, can you confirm that $\lim_{\varepsilon\to 0}\gamma^*\to\infty$? - On the other hand, if $G$ is nonsmooth at its solution set, does $\lim_{\varepsilon \to 0} \gamma^*$ approach a finite value? Violating this second requirement would not contradict the aforementioned article, but it would significantly strengthen your results.

Rating

7

Confidence

3

Soundness

4

Presentation

3

Contribution

3

Limitations

The authors do a good job of explaining the required assumptions for their results.

Summary

This paper deals with a simple bilevel (the lower-level problem has no dependence on the upper-level variable) optimization problem, where both the upper- and the lower-level objectives are convex and potentially non-smooth. To simplify the original bilevel problem the authors consider a penalty-based single-level reformulation and establish the relationship between the solutions of the two problems. An accelerated proximal gradient method (PB-APG) is proposed to solve the penalty problem. Under a Holderian error bound condition and certain additional assumptions about the convexity and smoothness of the objectives, convergence of the PB-APG is shown to approximate global optimal solutions of the original bilevel problem.

Strengths

* Differently from most of the works in literature, this paper deals with a problem in which the global solutions of the original bilevel problem are attainable. As a result, from a theoretical perspective, this is an interesting problem class. In addition, the proposed method is shown to (approximately) converge to these global solutions (of the original bilevel problem) and not to the solutions of some reformulation, as it is usually the case in other bilevel works. * The authors provide a comprehensive and detailed summary of algorithms developed for solving simple bilevel optimization problems (in table 1).

Weaknesses

* From an applications perspective, the problem class considered here does not seem very interesting. The bilevel problem is simple, the objectives are (strongly) convex, a Holderian error bound holds and the non-smooth term is required to be proximal-friendly. This significantly restricts the number and complexity of potential applications. Indeed, the applications presented in the appendix seem to revolve around (regularized) linear least-squares problems and simple learning models like logistic regression. * The proposed algorithm solves the reformulated minimization problem $P_{\Phi}$ rather than the original bilevel. This minimization problem looks fairly standard, and it seems that known algorithms are applied directly for its solution. Thus, it appears that there is no significant novelty in terms of algorithm design.

Questions

* Are Holderian error bounds satisfied in problems involving training of complex learning models, like neural networks. * In table 1 some of the algorithms depend on parameters $\alpha$ and b, but the property to which these parameters correspond to is not specified. Please clarify this.

Rating

5

Confidence

3

Soundness

4

Presentation

4

Contribution

3

Limitations

No negative societal impact

Summary

This work proposes a penalty based algorithm for simple bilevel optimization problems. The paper studies the relationship between the solutions of the penalized problem and the original bilevel problem. It extends the existing results on general bilevel optimization problem, which are established under PL condition, to the more generic Hölderian error bounds. The results are also extended to non-smooth upper and lower-level functions.

Strengths

1) The paper is well written and easy to follow. 2) The generalization of the existing results on PL condition to Hölderian error bound is interesting. 3) The extended results on non-smooth objectives are good contributions.

Weaknesses

1. Missing literature comparison/review: The method proposed in this paper is a penalty-based method. There is a large body of work for penalty-based bilevel optimization methods. While in the related work section in the main text, there is no detailed review/comparison of the previous penalty-based bilevel optimization algorithms. It might be beneficial if the authors could discuss about the advantage of the proposed method compared with the existing ones. 2. In the current state of the paper, the experiments seem to be purely synthetic and might be a little too toy. Though the paper is majorly a theoretical one, it would benefit to have more practical experiments. It is also of great importance to find meaningful applications for the simple bilevel optimization problem. 3. The method proposed in this work falls into the penalty-based methods. It might be interesting if the authors include a comparison with existing penalty-based bilevel optimization methods in, e.g.,

Questions

1. The proposed method is for convex simple bilevel optimization problems, which might be restrictive. Can the author explain how the algorithm can be extended to the non-convex case? 2. How does this algorithm compare to the penalty-based algorithms for general bilevel optimization problems? Are there any advantages demonstrated by this algorithm as compared to the generic ones?

Rating

5

Confidence

3

Soundness

3

Presentation

3

Contribution

2

Limitations

no potential social impact

Summary

The authors propose algorithms to solve simple bilevel optimization problems of the form $\min_x F(x)$ s.t. $x$ minimizes $G$, in the case where $F$ and $G$ are composite convex functions (i.e. some of 2 convex functions, one of which is also smooth), and assuming Lipschitz continuity of $F$ on the set of minimizers of $G$ and $G$ verifying a Holder error bound. The proposed algorithms actually tackle a simple minimization problem, solving a relaxed version of the original problem that authors previously proved to be equivalent.

Strengths

The link between the solutions of the original problem and the ones of the relaxed one is interesting and allows considering a simpler problem to tackle.

Weaknesses

I am not very familiar with this specific piece of literature, so I cannot pretend to be sure of the novelty of the results. In particular, in line 47, the authors say « Tikhonov regularization most related to $P_\gamma$ », I do not see any difference between the two formulations. Can the authors develop on this? What is exactly done in Tikhonov's paper? And what is new here? Minors: - Usually, a proximal-based algorithm can be applied to the particular case where the non-smooth part of the problem is null, then the prox map is simply the identity map, and all the guarantees hold. But in this paper's setting, the non-smooth part is essential and cannot be considered null as a particular case. Indeed, otherwise, $G$ would be smooth, therefore upper bounded by a quadratic function, and $G$ is also assumed to grow faster than $||x-\bar{x}||^{alpha}$ which cannot happen (if alpha<2). - A natural oracle assumption in the case where $F$ and $G$ contain each a non-smooth part would be to assume access to the proximal map associated with each. However, authors assume access to the proximal of all the linear combinations of the 2 non-smooth parts, and this choice seems to be only motivated by the reformulation of the problem. Doing this makes the derivation of PB-APG trivial once Thm 2.5. has been proven. But how could we tackle the same problem with the sole knowledge of the 2 prox maps independently?

Questions

- l.32: Why exclude the particular case where $X_{opt}$ is a singleton? This assumption is not used, therefore if we do not know in advance whether $X_{opt}$ is a singleton or not, one can still run this paper's algorithms, and guarantees will follow. - l.39: Even if what $G^*$ is seems clear, I think it is worth mentioning it before using it in line 35. - l.50: What about the upper problem? - l.50: « where b in (0, 0.5) ». The authors should be more specific here. Is it true for one specific b in the interval, depending on some parameters of the problem? Is it true for any (one proposed algorithm for each value of b)? - l.55: same remark - l.61: It would be more convenient if the authors keep a consistent way of displaying complexity. - l.68: What is g_2? Not defined yet at this stage. Moreover, note that the authors could not look at what happens in their case when $g_2=0$, as discussed in the "weakness" section. - l.101: What is f_2? Again not defined. And I think here that the authors meant $F$. - l.193: typo: « an » is repeated. - l.205: « while samadi … » If they consider the smooth case only, studying $\alpha<2$ would be pointless because it is empty. - It would be great if authors could add explicit stopping criteria in their algorithms. Indeed, if $F^*$ and $G^*$ are not known, I guess we stop PB-APG after K iterations where K is set according to Th3.3. But then, PB-APG is not only a function of $\phi$, $\psi$, $L_{f_1}$, $L_{g_1}, x_0, \epsilon$, but also $\ell_F$, $\alpha$ and $\beta$. Which is important to actually understand the iterates of aPB-APG.

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

2

Limitations

No limitation

Comment from Reviewer fmaf

I would like to thank the authors for their responses. I am raising my score to 5.

Response to authors' rebuttal

I thank the authors for responding to my minor concerns. Overall, the paper is well-written, sound and, I think, interesting for the Neurips community. If the authors process the discussed modifications/clarifications, then I am in favor of the acceptance of this paper.