Optimizing $(L_0, L_1)$-Smooth Functions by Gradient Methods

Authors: Daniil Vankov, Anton Rodomanov, Angelia Nedich, Lalitha Sankar, Sebastian U Stich
Primary area: optimization
Keywords: $(L_0, L_1)$-smoothness, gradient methods, convex optimization, worst-case complexity bounds, acceleration, Polyak stepsizes, nonconvex optimization

Abstract:
We study gradient methods for optimizing $(L_0, L_1)$-smooth functions, a
class that generalizes Lipschitz-smooth functions and has gained attention for
its relevance in machine learning.
We provide new insights into the structure of this function class and develop
a principled framework for analyzing optimization methods in this setting.
While our convergence rate estimates recover existing results for minimizing
the gradient norm in nonconvex problems, our approach significantly improves
the best-known complexity bounds for convex objectives.
Moreover, we show that the gradient method with Polyak stepsizes and the
normalized gradient method achieve nearly the same complexity guarantees as
methods that rely on explicit knowledge of $(L_0, L_1)$.
Finally, we demonstrate that a carefully designed accelerated gradient
method can be applied to $(L_0, L_1)$-smooth functions, further improving all
previous results.

Decision: accept (poster)
Reviewer scores: 8, 6, 6, 6

Reviews and discussion:
<thread>
creation date:
1730215154918

thread_type:
official_review

<thread_object>
creator: reviewer_r7w6

<content>
summary:
The paper examines the extension of a certain optimization method to a broader smoothness assumption, specifically $L_0,L_1$-smoothness. While it broadens the class of functions to be minimized, the authors manage to recover convergence rates comparable to those of the standard $L$-smooth case, albeit with an additional term that does not depend on the final accuracy.

strengths:
- For convex problems, authors improves existing results by achieving $O( L_0R^2 / \varepsilon + L^2_1 R^2)$
- Normalized gradient method and gradient method with Polyak stepsizes, which do not require the knowledge of the parameters $L_0$, $L_1$ and have the same rate as above
- Accelerated method with $O( \sqrt{L_0R^2 / \varepsilon} + L^2_1 R^2)$

weaknesses:
- Lack of analysis  for stochastic case is significantly limiting practical value of the work
- Accelerated method requires a line search (minor)
- The second part of the second question from below

questions:
- As a contribution authors listed in line 54 "tighter bounds on descent inequalities". But in line 58 authors "achieve the best-known" rate for non convex functions. I am curious if the tighter bounds actually helps to improve convergence. I would expect improving the rate, if they actually help. As far as I understand, the tighter bounds are supposed to help for the non-simplified stepsize version and some logarithmic improving factor should appear. Am I right? Could the authors answer this question by providing rates with their tighter bounds and with non-tight bounds?
- Acceleration does not seems fair. By initially running non-accelerated method authors enter the area where $\|\|\nabla f(x) \|\|\leq \frac{L_0}{L_1}$, making the right hand side of the generalized smoothness condition (line 121) $L_0 + L_1|\|\nabla f(x) \|\| \leq 2L_0$, that corresponds to the standard smoothness assumption. 
   - In the standard $L$-smooth case there exist accelerated methods without line search (e.g. Similar Triangles Method), that keep iteration bounded ($\|\|x^k - x^* \|\|  \leq R \cdot const$), so I am expecting such methods stay in the area. Can the line search be avoided in your analysis? Or what is it crucial role? 

  - The term  $L^2_1 R^2$ corresponds to the number of iteration to enter the area with bounded gradient. Then the authors in fact deal with the standard $2L$-smooth case, while obtaining the other term. This observation is consistent with non-accelerated methods, considered in the paper. I would like to note, that acceleration in fact is used only in the area where the standard $2L$-smooth case takes place, and does not help to enter the area faster. In other words I would say that the contribution in fact is -- a bound on the number of oracle calls to enter this area. And I am expecting this bound to be improved in the accelerated case. Don't get me wrong, but I could not consider the convergence of AGMSDR in the standard $2L$-smooth case as a contribution. I would like authors to address my concerns, and clarify about their contribution to this part. Is it an application of the authors result of non-accelerated method to bound the number to enter the area with bounded gradient? 

I would like to comment on the scores. Taking the above questions into account, I currently accept the contributions related to first-order methods. The results are new and significantly improve previous rates. But they rely on the only basic result -- descent inequalities. The rest is an application of the new inequalities to the well-known methods. That is why I consider the contribution as limited. I open for a discussion and the authors are likely to expect higher scores if my concerns are convincingly addressed, especially about the area with bounded gradient.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730337448946

thread_type:
official_review

<thread_object>
creator: reviewer_kuu4

<content>
summary:
The author(s) present non-asymptotic convergent analyses of various types of gradient methods on convex and non-convex functions satisfying $(L_0, L_1)$-smoothness, which is a type of generalized smoothness assumption that has gained some interests recently in machine learning community.

They derive a series of first-order upper bounds, implied by the generalized smoothness assumption, which are tigher bounds than previous works. Furthermore, they derive similar lower bounds when the functions are convex.

Using these newly derived bounds, they present a convergent analysis on non-convex functions, which matches the current best-known rate of this function class up to absolute constants.

For convex functions, however, they derive better-than-existing convergent rates for different gradient methods of this particular function class.

Finally, they experiment with a simple $||\mathbf{x}||^p / p$ function, where the constants $L_0$ and $L_1$ can be known in advance.

strengths:
To me, one of this paper's main strengths/contributions is the derivation of tighter first-order upper and lower bounds. The bounds will undoubtedly help any further work on analyzing this particular function class.

In Theorems 3.2 and 5.1, the author(s) is able to dispense $L$-gradient Lipschitz, which was additionally assumed in the previous works Koloskova et al 2023, while improving the current existing rate.

The overall flow of the paper is well-presented.

weaknesses:
1. Numerical results can be strengthened by providing more experiments.

2. For Theorem 3.1, even though your rate is better than the rate provided in Hubler et al 2024, they do not have the dependency on $L_0$ and $L_1$ (See section Questions, 1.).

3. (line 269) I believe "By Theorem 3.1, the smallest number K of iterations required to achieve ..." is incorrect, as one can happen to choose an initial point such that $\|\| \nabla f(x_{0}) || < \epsilon_{\mathbf{g}}$. In this case, $K = 0$, which violates your claim here. The correct wording should be "By Theorem 3.1, obtaining the stationary point requires at most ... ".

4. (Theorem 5.1) The presentation of your theorems should be consistent. It is recommended to present in the form of "$K \geq $", like in your other theorems. 

5. $||\mathbf{x}_0 - \mathbf{x}^*||$ is denoted to be both $R_0$ and $R$, e.g., Theorem 3.2. Notations should be consistent.

6. (line 257) "absolte" -> "absolute"

7. (eq. 14) I think the inequality should be $... \geq \frac{||\nabla f(x)||^2}{2L_0 + 3L_1||\nabla f(x)||}$, i.e., there is no 2 in the numerator (c.f. Lemma B.1)

8. (line 641) I think $s$ should be $s := \nabla f(x) - \nabla f(y)$. Otherwise, the sign in the inequality at line 643 is incorrect.

9. (line 648) Change $\phi^*(\gamma)$ to $\phi_*(\gamma)$ to maintain consistency.

10. (line 651) Some of the gradients should be of variable $y$, not just $x$, i.e., $\nabla f(y)$.

questions:
1. Another way to dispense of the dependency of the constants $L_0$ and $L_1$ in the step-size is to perform backtracking line-search, which also guarantees descents in the objective function value. Can the given new bounds (Lemma 2.2, 2.3) improve the rate derived by Hubler et al 2024?

2. For Theorem 6.1, empirically, is there any way to tell when to switch to AGMsDR? That is, can we tell that we are in a local region?

3. Have you tried experimenting with a softmax function, which I believe the constants $L_0$ and $L_1$ can be analytically evaluated? This example will provide more insights than the simple function $||\mathbf{x}||^p$.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730343356817

thread_type:
official_review

<thread_object>
creator: reviewer_geoz

<content>
summary:
The paper studies gradient methods for solving problems with (L0, L1)-smoothness, a recent class of functions developed by Zhang et al. (2019). Novel convergence results are established in this paper, including tighter bounds on function growth and the complexity bound for finding near stationary points in both nonconvex and convex cases. Some new methods with different step sizes are also examined.

strengths:
1. The paper is well-written and easy to follow. The analysis is thorough and offers many insights for research in optimization.

2. I appreciate the comparison between this paper and Gorbunov et al. (2024), which is comprehensive and particularly crucial for readers.

3. I have attempted to implement some of the suggested algorithms and found that the analysis presented here is essential for practical use, especially when the optimal step size in equation (11) is given explicitly.

weaknesses:
The following are some major concerns about the paper.

1. The numerical experiments are conducted only on simple functions. I suggest that the authors significantly improve this section by employing more diverse examples, particularly in nonconvex cases. For examples, could the authors consider loss functions from deep learning models or other challenging nonconvex optimization problems from applications?

2. If I have not overlooked anything, the current paper does not discuss the difficulties of deriving the convergence properties for (L0, L1)-smooth functions compared to L-smooth functions, nor how the authors overcome these challenges. Can the author discuss key challenges in analyzing (L0,L1)-smooth functions compared to L-smooth functions, and to highlight any novel theoretical tools or techniques they developed to overcome these challenges.

3. I do not find Proposition 2.6 impressive, as the results are rather predictable, and the proofs seem straighforward. 

4. The authors mention that "we cannot guarantee that the class is closed under all standard operations, such as the summation". Can you provide a concrete counterexample showing that the sum of two (L0,L1)-smooth functions is not necessarily (L0,L1)-smooth? If so, are there any additional conditions that could guarantee the sum remains in this function class?

5. The authors claim that the estimate in (4) is tighter than those presented in previous works. Can you provide a numerical example or theoretical argument demonstrating how your estimate in (4) is tighter than previous bounds? Is it possible to prove that this bound is optimal, or are there cases where it could potentially be improved further?

questions:
See weakness
</content>
</thread_object>

</thread>
<thread>
creation date:
1730542567381

thread_type:
official_review

<thread_object>
creator: reviewer_qpgv

<content>
summary:
This paper provides a general understanding of the $(L_0, L_1)$-smooth function class, which has recently gained increasing interest due to its empirically observed connections to deep learning applications. They authors establish a parallelism between the classical optimization theory for $L_0$-smooth functions, and show how analogous inequalities and algorithm design strategies should be carried out with $(L_0, L_1)$-smooth functions. This includes the derivation of $(L_0, L_1)$-smooth version of the cocoercivity inequality, analysis of fixed-stepsize gradient descent method for convex and nonconvex cases, and analysis of gradient methods using normalized stepsizes, Polyak stepsizes, and Nesterov-type acceleration for convex functions.

strengths:
As mentioned in the Summary section, this paper nicely demonstrates the parallelism of how the traditional techniques from smooth (convex) minimization should be properly interpreted and applied to the class of $(L_0, L_1)$-smooth functions. As a reader who is much more familiar with the classical optimization theory but not as much with the recent theory of $(L_0, L_1)$-smooth optimization, the paper was interesting, easily readable, and informative. It seems such viewpoint has not been provided previously with this level of clarity, and I think this work could serve as a solid reference for those future readers who are interested in this area. The algorithms and their convergence results the paper provides within various setups seem correct and competitive.

weaknesses:
The primary weakness of the current version of the paper is the writing. While I think the technical contents are good, the writing does not seem to be polished carefully enough and should be managed before the publication. The general flow is okay, but there are many detailed points which I would recommend the authors to address; please refer to the Questions section. I would recommend acceptance of the paper provided that the writing issues get resolved.

questions:
Writing issues (in the order of appearance)
- In pg. 3, lines 108-109, it will be illustrative to explain in more detail in which aspects the authors' proof techniques differ from that of the work [1], cited as Gorbunov et al. (2024) in the manuscript. Also I think the authors should be more cautious about claiming that the proof is more "elegant" than something else. One possible suggestion is to emphasize their clearer parallelism with the classical theory, rather than to describe the value of this paper's framework with a subjective expression like "elegant".
- The statement of Lemma 2.2 involves the notation $\phi(t) = e^t - t - 1$, while its proof in the Appendix uses the symbol $\phi$ to denote something else. Please change it.
- The bound $\phi_* (\gamma) \ge \frac{\gamma^2}{2+\gamma}$ appears suddenly in the statement of Lemma 2.3, while the relevant discussion appears later in Section 3. I think this should be relocated to somewhere near Lemma 2.3.
- In pg. 4, lines 164-165, the meaning of the sentence "we present some examples to support the choice of generalized smooth assumption" is unclear.
- Proposition 2.6 and the subsequent discussion doesn't seem very relevant to the rest of the paper. To some readers this information could be valuable, but generally speaking, I even think the whole part can be moved to the Appendix without altering the flow of the paper. Also, please clearly define the expressions like "$M$-Lipschitz twice continuously differentiable" before using it.
- In line 183-184, there is dangling "for some" after the period.
- In Theorem 3.1, it should have been assumed/defined that $f^* := \inf f > - \infty$. In general, the authors did not properly state that they assume the existence of a minimizer $x^*$, etc. (in subsequent theorems regarding convex cases). Please be precise about these points.
- In the statement of Theorem 3.2, is $||x_0 - x^*||$ intended to be denoted as $R_0$?
- In pg. 6, in lines 297-298, it is not clear what the authors mean with "by using the preceding estimate and the update rule of the method". Only after reading the proof in the Appendix I could understand the technique deriving equation (20), and I still do not feel that the text surrounding the equation is successfully conveying the idea. If you intend to provide a high-level intuition, please be more precise and detailed. Also, note that the exponent 2 is missing in $R_{k+1}^2$ within (20), and in equation (43), the $g_k^2$ factors seem to be missing.
- Lines 304-310 provide an interesting insight on the complexity $\mathcal{O}(L_0 R_0^2 / \epsilon + L_1^2 R_0^2)$, but I think the complexity analysis does not clearly show that the constant $\mathcal{O}(L_1^2 R_0^2)$ complexity corresponds to the phase where the algorithm reaches the regime where $f$ behaves like a smooth function. (Which is in contrast with Section 6, where the algorithm is deliberately designed in this way.) Can this discussion somehow be made more precise?
- In Theorem 4.2, $R$ is used without being defined.
- I do not see any reason why Lemma 4.1 is introduced in pg. 7. I think a discussion on how (22) is utilized in the analysis is missing.
- In lines 349-350, the authors say "time-varying stepsizes can be eliminated", but this seems to be a conjecture (or at least, something that the authors do not formally prove) and I think it should be reworded. Please be careful about making such statement.
- In pg. 8, lines 378-380, the authors emphasize that their rate does not have an exponential dependency on $L_0, L_1$, but why does this worth emphasis? Are there prior work which analyzed gradient method with Polyak stepsizes in the same setup and obtained rate that involves $\exp (L_0), \exp (L_1)$? If so, please specify.
- In lines 400-401, the authors mention that "Our rate is better than $\mathcal{O}(L_0 R^2 / \epsilon + \sqrt{L / \epsilon} L_1 R^2)$", but where does this rate come from?
- In the beginning of Section 6 (and also the same for Sections 4, 5) please clearly specify in the first sentence introducing the setup that you are dealing with convex functions.
- It is weird that Algorithm 1 (which is not the algorithm that the authors develop) is packaged using the Algorithm environment, while the authors' algorithm (lines 427-431) isn't. 
- The Step 1 of the authors' algorithm in Section 6 requires to find a point $\bar{x}$ satisfying $f(\bar{x}) - f(x^*) \le \frac{L_0}{8 L_1^2}$. I think this requires either the knowledge of $f(x^*)$ or $R=||x_0 - x^*||$ (in order to determine when to stop). Is this understanding correct? If so, this is a limitation that should be clearly explained.
- Theorem 6.1 misses the convexity assumption in the statement. Also, it analyzes the AGMsDR algorithm with initial point satisfying  $f(x_0) - f(x^*) \le \frac{L_0}{8 L_1^2}$, but this is inconsistent with the $\bar{x}$ notation used in lines 427-431. I think this also comes from the problem of not highlighting their "procedure" as a separate algorithm with a proper name.
- In lines 477-478, should the two occurrences of $R$ be the same values? It seems like one is $||x_0 - x^*||$ and one is $||\bar{x} - x^*||$.
- In line 483, the authors again mention "not have an exponential dependency". Please cite a relevant prior work explaining why this is worth emphasis.
- It is not clearly defined what the figure labels like NGD, GD1, GD2, etc. precisely means. Even though it could be speculated if one reads through Section 7, this should be done somewhere, for example, within the figure caption.
- In Figure 2, please specify that you are using $L_0 = (\frac{p-2}{L_1})^{p-2}$ according to Example 2.4 (if this understanding is correct).

[1] Gorbunov et al., Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732534244380

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Global Response

comment:
We thank all the reviewers for their time and suggestions. We are delighted that most of you found our work interesting, insightful, and correct.

Based on the obtained feedback, we have prepared a revised version of the manuscript where we significantly improved the paper's structure and fixed many typos.
Please see the updated PDF file.
Below is a quick summary of the most important changes (highlighted in blue in the revised version): 

1. We have considerably improved the writing and explanations. For instance, in Section~3, we now more carefully introduce and compare the three stepsizes. Also, we rewrote the explanations for the accelerated method to highlight the main idea and challenges. Please see Section 6 and Appendix F for more details.

2. We have modified the proof of Theorem 3.2 for the Gradient Method (GM) in the convex case and obtained the $\mathcal{O}(\frac{L_0 R^2}{\epsilon} + L_1 R \ln \frac{F_0}{\epsilon})$ complexity which is better than the previous $\mathcal{O}(\frac{L_0 R^2}{\epsilon} + L_1^2 R^2)$, especially when $F_0$ is reasonably bounded. Please see Section 3 for more details.

3. We have added the formal proof of the fact that the Normalized Gradient Method (NGM) with time-varying stepsizes obtains the same complexity as that with fixed stepsizes, up to an extra logarithmic factor. Please see Appendix C.3 for more details.

4. We have also clarified, in Section 4, that NGM does not need to know the exact value of $R$ and converges with any $\hat{R}$ at the expense of multiplying the complexity by the squared ratio of $\hat{R}$ and $R$. We have also elaborated on the proof idea behind Theorem 4.1. 

Finally, we would like to point out a few important aspects of our work that some of the reviewers might have missed.

First, we provide many useful insights for the optimization of $(L_0, L_1)$-smooth functions. In particular, in Section 3, we show, for the first time, that the popular clipping stepsize is indeed natural for $(L_0, L_1)$-smooth functions, and is nothing but an (accurate) approximation of the optimal stepsize resulting from minimizing an upper bound on the objective function.

Second, we establish several **completely novel** convergence rate results which are **significantly** better than those available in the literature:

- Our $\mathcal{O}(\frac{L_0 R^2}{\epsilon} + L_1 R \ln \frac{F_0}{\epsilon})$ complexity of GM is much better than the $\mathcal{O}(\frac{(L_0 + L_1 \| \nabla f(x_0) \|) R^2}{\epsilon})$ from [Li et al 2023].
It is also significantly better than the $\mathcal{O}(\frac{L_0 R^2}{\epsilon} + L_1 R \sqrt{\frac{L}{\epsilon}})$ complexity from [Koloskova et al 2023], and, in contrast to the latter work, we do not need to impose any additional (rather strange) assumption that $f$ is also $L$-smooth.

- Our $\mathcal{O}(\frac{L_0 R^2}{\epsilon} + L_1^2 R^2)$ complexity for GM with Polyak stepsizes is significantly better than the only available result of $\mathcal{O}(\frac{L_0 R^2}{\epsilon} + L_1 R \sqrt{\frac{L}{\epsilon}})$ from [Takezawa et al 2024] (which also assumes, as [Koloskova et al 2023], that $f$ is additionally $L$-smooth).

- The $\mathcal{O}(\frac{L_0 R^2}{\epsilon} + L_1^2 R^2)$ complexity we establish for NGM is entirely new and there are no other results for this method in the literature.

- Our $\mathcal{O}(m \sqrt{\frac{L_0 R^2}{\epsilon}} + L_1^2 R^2)$ complexity for the two-stage acceleration procedure is significantly better than the $O((L_1^2 R^2 + \frac{L_1^2 F_0}{L_0} + 1) \sqrt{\frac{F_0 + L_0 R^2}{\epsilon}})$ complexity for NAG from [Li et al 2023], even when the starting point is such that $F_0 \equiv f(x_0) - f^* = O(\frac{L_0}{L_1^2})$, as required for the second stage of our procedure. Please see Section 6 for more details. 


[Koloskova et al 2023] Anastasia Koloskova, Hadrien Hendrikx, and Sebastian U Stich. Revisiting gradient clipping:
Stochastic bias and tight convergence guarantees, ICML, 2023

[Li et al 2023] Haochuan Li, Jian Qian, Yi Tian, Alexander Rakhlin, and Ali Jadbabaie. Convex and non-convex
optimization under generalized smoothness, NeurIP, 2023.

[Takezawa et al 2024] Yuki Takezawa, Han Bao, Ryoma Sato, Kenta Niwa, and Makoto Yamada. Polyak meets parameter free clipped gradient descent, NeurIPS, 2024.
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper studies gradient methods for optimization problems with \((L_0, L_1)\)-smooth objectives, a generalization of Lipschitz-smooth functions. It offers new insights into this class and introduces a unified analysis framework for related methods. The authors establish state-of-the-art complexity guarantees for the simple gradient method in both convex and non-convex settings. They also analyze two variants--Polyak stepsize and normalized gradient methods--achieving optimal bounds without requiring prior parameter knowledge. Additionally, the paper extends accelerated gradient methods to this function class, demonstrating desirable convergence properties.

Overall the reviewers agree that the paper is interesting, contains several novel ideas, and makes notable contributions to the theory of first-order optimization methods.