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

Thank you for your feedback.

We want to start by highlighting some challenges in developing an accelerated method for $(L_0, L_1)$-smooth functions.

• Firstly, it is not enough to find a good starting point $x_0$ such as $||\nabla f(x)|| \leq \frac{L_0}{L_1}$, because previously considered STM, NAG, and all other existing versions of the standard FGM do not guarantee a monotonic decrease of the gradient norms. As a result, the gradient norm can increase during optimization, and these methods can escape good regions with bounded Hessian norms.

• Secondly, it is not enough to keep iterates inside $||x - x^*|| \leq R \cdot const$ because the iterates might not stay in the initial sublevel set. This also might lead to an increase of gradient norms during the optimization and consequently might lead methods, such as STM, to leave the region where $||\nabla^2 f(x)|| \leq 2 L_0$. The need to upper bound the gradient consequently leads to an additional $\exp(L_1 R)$ (by Lemma 2.2 in our paper) factor in the complexity.

• Instead, we propose to keep iterates inside a good sublevel set by running a method with monotonically decreasing function values. While the idea of staying in a sublevel set is ``simple,'' the complexity of the proposed procedure is significantly better than the existing results. Moreover, this idea might be intuitively simple, but the implementation of such an idea turns out to be a non-trivial task for FGM; however, it is possible with careful analysis. To implement it, we have to (1) identify a good region where iterates would stay, (2) modify the original proof of AGMsDR to work with any update rule $T(\cdot)$, (3) find a general condition for operation $T(\cdot)$ to make proof of AGMsDR work.

• Finally, we did not explain the idea clearly in the initial submission, but now we rewrote the explanations and clearly explained the problem of maintaining the gradient norm small. For details, please see Section 6 and Appendix F.

Next, we provide answers to the reviewer's questions.

1. Answer to the second question. We kindly disagree that the accelerated procedure is unfair. Even when NAG from [7] and STM from [3] start with a point $x_0$ such that $f(x_0) - f^* \leq \frac{L_0}{5 L_1^2}$, STM requires $\exp(O(1) L_1 R) \sqrt{\frac{L_0 R^2}{\epsilon}}$ and NAG requires $\mathcal{O}((L_1^2 R^2 +1)\sqrt{\frac{L_0 R^2}{\epsilon} })$ while our procedure (only the second stage, AGMsDR) will require $\mathcal{O}(\sqrt{\frac{L_0 R^2}{\epsilon}})$. It happens since even when starting point $||\nabla f(x_0)|| \leq \frac{L_0}{L_1}$ neither STM nor NAG does not ensure that the gradient norms don't grow, while AGMsDR does. Please see Section 6 and Appendix F for a detailed comparison. Thus, our procedure already achieves much better results than other available methods. That being said, we do agree that our procedure does not accelerate the $O(L_1^2 R^2)$ complexity of the first stage, and it is an interesting open question how to improve on this.

2. Answer to the first question. Yes, the tighter bound helps us to obtain non-simplified stepsizes $\eta_k^*$ and provides an intuition for all three stepsizes: non-simplified, simplified, and clipping. We are not aware of whether it is possible to improve the complexity of the method in the non-convex case.

We believe that we have addressed all the reviewer's concerns and weaknesses in our paper, and we kindly ask the reviewer to reevaluate their rating in light of these revisions.

1. Regarding AGMsDR:

• It is already possible to use any update rule providing the sufficient decrease. I can not see authors obtaining something new here.
• I checked the proof, it is identical, authors do not even use $L_0, L_1$, it is just $L$ like originally. When the methods enters the $2L$ smooth area, there is nothing hew here. I agree that it is a good observation that gradient norm stays bounded. But I still believe it might be possible to make iterations of STM bounded as well by increasing the number of iterations of the first stage.
• It would be great to have the only stage method. Is it possible to introduce another $T(\cdot)$ such that the first stage is avoided? Even by the cost of a worse rate?
• What if one uses the GD update as $T(\cdot)$? What would be the bound?

2. I feel that the second question was not answered. As far as I understand (Chen et al., 2023) proved a condition which is equivalent to bounds from Lemma 2.2. Could the authors answer this question by providing rates with their tighter bounds and with non-tight bounds? Please show what improvements I can get in terms of final bounds.

Thank you for the positive evaluation of our paper and feedback. We incorporated all the writing mistakes and typos in the updated version of our paper. Please see Global Response and the updated version. Below we provide answers to reviewer's concerns

• Regarding comparison with Hübler et al. (2024). The rate in Hübler et al. 2024 depends on $L_0, L_1$, but to run the gradient method with backtracking line search, they don't need to know $L_0, L_1$. We added this comment in the updated version of our paper.

• Regarding line 641. It does not matter if $s := \nabla f(x) - \nabla f(y)$ or $s := \nabla f(y) - \nabla f(x)$, since the sign is included inside of $h \in \mathbb{R}^m$ which we maximize over.

Next, we provide answers to the reviewer's questions.

1. Answer to the first question. We don't think that the complexity of the gradient method with backtracking line search, as presented in Hübler et al. 2024, can be improved using our tighter bound.

2. Answer to the second question. Our accelerated procedure requires some extra parameters to switch to the second stage. We assume that we can check that $f(x) - f^* \leq \Delta$ for any given $\Delta$. Another option is to run GM for $K=O(L_1^2 R^2)$ number of iterations if we know $L_1$ and $R$); then the inequality $f(x) -f^* \leq \Delta$ is guaranteed to be satisfied by our Theorem 3.2. Developing an adaptive procedure with the same complexity is an interesting open question for future research.

3. Answer to the third question. We are not aware of any results explicitly showing parameters $L_0, L_1$ for the softmax function. Unfortunately we were not able to compute constants $L_0, L_1$ explicitly for the softmax function.

Regarding experiments. The focus of this paper is mostly theoretical and numerical experiments are conducted to verify our theoretical findings. There are already many works with experiments showing an advantage of clipped Zhang et al. (2019), normalized methods Hübler et al. (2024), and Polyak-stepsizes Takezawa et al. (2024). However, in the updated version of our paper, we provided more experiments comparing accelerated methods to support our theoretical findings.

We believe that we have addressed all the reviewer's concerns and weaknesses in our paper, and we kindly ask the reviewer to reevaluate their rating in light of these revisions.

[Zhang et al. (2019)] Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie. Why gradient clipping accelerates training: A theoretical justification for adaptivity. ICLR 2020.

[Hübler et al 2024] Florian Hubler, Junchi Yang, Xiang Li, and Niao He. Parameter-agnostic optimization under relaxed ¨ smoothness. AISTATS, 2024.

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

Thank you for your feedback and recommendations. Below we provide answers to reviewer's concerns

1. Regarding numerical experiments. We want to highlight that most of our results are in a convex setting where we significantly improved the best-known complexity. The main focus of this paper is on theoretical insights. There are already many works with experiments on non-convex setting showing an advantage of clipped [Zhang et al. (2019)], normalized methods [Hübler et al. (2024)] and polyak-stepsizes [Takezawa et al. (2024)]. To address this concern, we provided more experiments comparing accelerated methods to support our theoretical findings.

2. Regarding challenges in analysis of $(L_0, L_1)$-smooth functions. Our work is not the first paper focusing on $(L_0, L_1)$-smooth functions. The previous works discussed the difficulty of analyzing $(L_0, L_1)$-smooth functions (see Zhang et al 2019, Koloskova et al 2023, Li et al 2023, Hübler et al 2024). We don't provide such a discussion since it was already done previously and due to space limitations.

3. Regarding Proposition 2.6. In our paper, we are not claiming that Prop 2.6 is impressive. However, these results might be important for a community to investigate further properties of $(L_0, L_1)$-smooth functions. We believe that it's useful to have such results explicitly written somewhere to streamline their application. We also wanted to attract the attention of the readers to the problem of insufficient calculus rules for this class of functions (problems with summation and affine substitution of the argument).

4. Regarding closedness under summation. We do agree that finding such an example is interesting and important. But we are not claiming that it is not closed; in our paper, we wrote that we could not guarantee that. Please note that Proposition 2.6 (Proposition A.3 in the updated version) provides a condition when the sum of two $(L_0, L_1)$-smooth function is preserved: $f$ is $(L_0, L_1)$-smooth, $g$ is $(L, 0)$-smooth and is Lipschitz continuous, and their sum $f+g$ is $(L_0 + M L_1 +L , L_1)$-smooth. However, even under this condition the resulting parameter $L_0 + M L_1 +L$ is larger than $\max \{L_0, L\}$.

5. Regarding tighter bounds. Our estimate in the first inequality of Lemma 2.5 is tighter than inequality (13) in Corollary A.4 [Zhang et al 2020], since ours $(e^t - 1)/t \leq 1 + e^t - (e^t - 1)/t$ for $t \geq 0$. Our second bound in Lemma 2.5 is tighter than the bound in eq (7) in Lemma A.3 in Zhang et al 2020 since our $\phi(t) = e^t - t -1 \leq (e^t - 1) t \leq 1 + e^t - (e^t - 1)/t$.

We believe that we have addressed all the reviewer's concerns and weaknesses in our paper, and we kindly ask the reviewer to reevaluate their rating in light of these revisions.

[Zhang et al. (2019)] Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie. Why gradient clipping accelerates training: A theoretical justification for adaptivity. ICLR 2020.

[Zhang et al 2020] Bohang Zhang, Jikai Jin, Cong Fang, and Liwei Wang. Improved analysis of clipping algorithms for non-convex optimization, NeurIPS, 2020.

[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.

[Hübler et al 2024] Florian Hubler, Junchi Yang, Xiang Li, and Niao He. Parameter-agnostic optimization under relaxed ¨ smoothness. AISTATS, 2024.

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

Thank you for the positive evaluation of our paper and a detailed list of recommendations regarding our paper's writing. We significantly improved our new version, given all the reviewer's recommendations. Please see our global response and updated version of our paper for details.

Regarding the knowledge of $f^*$ for the accelerated two-stage procedure (Algorithm 6.1). You are right; Algorithm 6.1 requires prior knowledge of $f^*$. We added this discussion. Another option is to run GM for $K = O(L_1^2 R^2)$ iterations; please see our response to reviewer KuU4.

We believe that we have addressed all the reviewer's concerns and weaknesses in our paper, and we kindly ask the reviewer to reevaluate their rating in light of these revisions.