Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity

The analysis of the current paper is mostly based on Assymetric and Symmetric (L0,L1) smoothness, which can be hold for functions that are not twice differentiable. This is good since this class cover the original class of function in (Zhang et al, 2020b), where twice differentiability is a must. However, which meaningful classes of functions satisfy Assymetric/Symmetric (L0,L1) smoothness while not C2? I found that all the examples presented are C2, and thus it seems that the use of Assymetric and Symmetric (L0,L1) smoothness is not neccesary, which reduces the importance of the current paper much. Note that examples for L-smooth functions that are not C2 are diverse, so it is reasonable to use the gradient Lipschitz condition instead of the stronger one, bounded Hessian. I do not think it is the case for (L0,L1) smoothness.

Indeed, we consider a more general assumption, including Hessian free given by (Zhang et al. 2020b) [Corollary A.4] which is equivalent to the standard assumption with Hessian assumption (inequality (5) of our work or C2). The lack of examples does not necessarily reduce the importance. [1] provides various plots which indicate complicated dependence of Hessian norm on Gradient norms. Having a more complicated model may lead to a more general assumption on smoothness. So we believe that our results also create value for a community, by analyzing more general assumption, adaptive methods, and introducing stochasticity.

[1] Zhang, Jingzhao, et al. "Why gradient clipping accelerates training: A theoretical justification for adaptivity." arXiv preprint arXiv:1905.11881 (2019).

Now assume that the function is C2. Lemma 2.1 shows that (L0,L1) smoothness implies (not equivalent) equation (7). In comparison with Lemma 2.2 (Vankov et al., 2024) below, their equation (2.2) seems to be a shaper inequality and in fact is an equivalent condition. Based on this, I suspect that the results obtained by the paper under review is not as tight as claimed by the authors, especially when compared with (Vankov et al., 2024).

First of all it is worth mentioning that (Vankov et al., 2024) appeared on arXiv after the submission deadline, so it is not appropriate to compare.

But as we stated above, we consider a more general assumption, which includes the assumption made in (Vankov et al., 2024). Moreover, to the best of our knowledge, the lower bounds are not obtained yet for the set of considered assumptions. So, it is challenging for us to say that our results or the results of (Vankov et al., 2024) are optimal for the corresponding set of assumptions. Moreover, for sufficiently large number of iterations even constant factors are almost identical. For $(L_0,L_1)$-GD we obtain $2/\nu$ constant which is almost the same as 4 for GD of (Vankov et al., 2024), since $\nu = e^{-\nu}$ and $0.56 < \nu < 0.57$, so we argue, that the assumption we made is not too restrictive.

The convergence theory of algorithms for $(L0,L1)$-smooth function does not explain why they are better than standard gradient descent. For example, can the authors explain why standard GD performs worse than designated algorithms for $(L0,L1)$-smooth function in solving logistic regression?

Appendix B considers some examples of functions satisfying the Hessian-based assumption (5), which is covered by the symmetric assumption we used in our paper. $(L_0,L_1)$-smoothness can be reduced to the case of the standard smoothness by bounding the gradient norm by (24), which leads to a pessimistic constant. The standard gradient descent performs constant step-size steps, and the first one is inversely proportional to that pessimistic constant, so it is very small. $(L_0,L_1)$-GD allows the stepsize to increase as the gradient norm vanishes. The method performs large stepsizes, thus achieving faster convergence.

Regarding logistic regression, we consider the logistic loss function in example B.3, which is expected to share properties with the average of logistic functions. Although we are not aware of an explicit formula for $L_0$ and $L_1$ for the average of logistic functions, one can note that in practice, the Hessian norm can indeed depend on the gradient norm, as shown in Figure 2. Thus, GD performs worse than other methods since GD uses smaller step sizes corresponding to the worst-case smoothness constant.

A new acceleration of GD is proposed. It would be supportive to add more remarks to highlight the theoretical merits of this acceleration compared with the STM in (Gasnikov & Nesterov, 2016). Additionally, it would be more supportive to numerically compare its performance with STM in (Gasnikov & Nesterov, 2016).

We have a detailed comparison of our accelerated GD method with the STM from [Gasnikov & Nesterov, 2016]. As highlighted in the line 362-364, our algorithm differs from the original STM in line 6 of Algorithm 3. Moreover, as discussed in lines 408-409, we recover the convergence guarantees of the original STM from Theorem 5.1 with $L_1 = 0$.

However, we agree that it would be valuable to include experiments to evaluate the empirical performance of the proposed method. We will add these experiments in the camera-ready version.

Example 1.3 considers a logistic function with L2 regularization. However, f(x) is not related to L2. It would be better to specify where the L2 regularization is.

Thank you for pointing this out. This is indeed a typo. The problem in example 1.3 is a simple logistic function (without L2 regularization). We fixed this typo in the revised version of our manuscript.

The discussion after Theorem 7.1 (line 521) claims that the probability must be smaller than ……. It would be clearer to explain why the probability should be smaller than this value.

Thank you for your question. We agree that due to space constraints, we were unable to include all the necessary details. For clarity, we added Remark H.1 in line 2146.

We welcome the reviewer to check the revised version of our manuscript for the clarifications.

Ultimately, a high-level takeaway of the work (which is likely also a takeaway that follows from the Chen paper if one could quickly bridge their stationarity to function suboptimality here) seems to be that the results are ultimately of a local nature. What I mean by that is that due to the unavoidable dependence of the type , the terms involving that in the bound will be large, unless is sufficiently small, and hence, in spirit the results can be viewed as showing that the GD methods studied in the paper are good but only locally. This aspect is not a criticism of the paper, but just a comment on how one can typically interpret bounds that involve exponentials.

We respectfully disagree with the reviewer that our result is of local nature. For $(L_0, L_1)$-GD we have a clear characterization of two-stage convergence and the leading term in the rate is independent of $L_1$ and any exponentially large terms (inequality (15)). Furthermore, for GD-PS we also show better results without requiring any change of the method. Finally, our analysis for AdGD does not involve these stages at all, and does not show local nature.

Do the results really offer a significant improvement over Li et al. 2024a (Convex and Non-convex Optimization Under Generalized Smoothness). The results provided by Li et al. 2024a for GD and NAG also do not rely on the assumption of L-smoothness, and their acceleration results for NAG do not have a dependence on exp(L1). The authors claim that the advantage of their results is that they do not require dependencies on and , as in Li et al. 2024a, and they argue that these quantities could potentially be exponentially large in the worst case (Line 408-420)---But in the reviewer's opinion, assuming these initial quantities to be constants is not a very strong assumption, whereas in comparison, the authors' acceleration result depends on exp(L1), which seems to be less favorable.

We thoroughly discuss and explain in detail the improvements on the results of (Li et al., 2024a) in lines 135-154, 157-165, 286-290, 326-329, 386-398, 836-837. We added lines 221-224 for additional discussion. We would like to briefly summarize it here.

• constant $\ell$ can be much larger than $L_0$ and $L_1$,
• $\ell \sim L_0(1 + 2L_1R_0 \exp(L_1 R_0))$ in the worst case, and the derived complexity is not optimal
• our bound does not depend on $f(x^0) - f(x^*)$ and on any bound for $\|\nabla f(x^k)\|$ including $\|\nabla f(x^0)\|$ which is of order $L_0R_0\exp(L_1 R_0)$

Assuming initial quantities to be constants does not lead to a good bound. For example, trivial bound (24) reduces $(L_0, L_1)$-smoothness to the standard smoothness with a pessimistic constant, having double exponential of $L_1D$. We further improve the results of (Li et al., 2024a) by removing the $L_1$ dependent factors from $\ell$ in the worst case, e.g. our bound for GD is $\mathcal O (\max [ \frac{L_0 R_0^2}{\varepsilon}, L_1^2R_0^2])$ vs. (Li et al., 2024a) which is $\mathcal O (\frac{\ell R_0^2}{\varepsilon})$ where $\ell \sim L_0(1 + 2L_1R_0 \exp(L_1 R_0))$ in the worst-case. We improve the result by a factor of $1 + 2L_1R_0 \exp(L_1 R_0)$ which is significantly larger in the worst case.

Regarding our results for the accelerated method, the reviewer fairly noticed an extra term $\exp(L_1D)$ in contrast to others' results. In fact (Li et al., 2024a) have the same issue; we have the discussion in lines 386-398. Our analysis faced a challenge bounding the term (20), discussed in Lines 371-377. However, in experiments we see that $(L_0, L_1)$ STM shows better performance than $(L_0, L_1)$-GD. And we believe that the term (20) can be bounded. We think that it would be an important contribution to bound the term, and decide to put this challenge into the main part.

The authors's motivation for studying AdGD should be as a result further enhanced: it seems inherently unsuitable to use under the generalized smoothness assumptions since AdGD does not utilize clipping.

Indeed, Zhang et al. (2020) noticed that $(L_0, L_1)$-smoothness is sufficient for the study of clipping algorithms. Stepsize selection rule from Malitsky and Mishchenko (2019) states that

where the latter expression represents the form of a stepsize for Normalized Gradient Descent (NGD). Given that NGD is a very close method to Clipped-SGD (Zhang et al. 2019)[Section 3.1 GRADIENT DESCENT ALGORITHMS], the stepsize from Malitsky and Mishchenko (2019) can be interpreted as a form of adaptive clipping.

Zhang, Jingzhao, et al. "Why gradient clipping accelerates training: A theoretical justification for adaptivity." arXiv preprint arXiv:1905.11881 (2019).

Zhang, Bohang, et al. "Improved analysis of clipping algorithms for non-convex optimization." Advances in Neural Information Processing Systems 33 (2020): 15511-15521.

And the result for the stochastic case (Section 7) requires a common minimizer for all the stochastic components (Assumption 4). Although such an assumption is also used in some works, this assumption is not that weak, and renders the results less applicable.

We partially agree with the reviewer that this assumption may be restrictive and give a proper discussion about this in lines 477-484. In line 479, we state that it is a typical assumption for over-parameterized models and provide a number of references. We would like to note that over-parameterized models have become increasingly common in modern applications, driven by the emergence of larger models like GPT, BERT, and their derivatives year after year, making overparameterization the norm. Supporting this, we highlight that over-parameterized networks are widely studied, as evidenced by the references provided below. However, we agree that the generalization that does not require the over-parameterization assumptions is an interesting direction for future research, but out of scope of our current work.

Zhang, Guodong, James Martens, and Roger B. Grosse. "Fast convergence of natural gradient descent for over-parameterized neural networks." Advances in Neural Information Processing Systems 32 (2019).

Kong, Zhifeng. "Convergence Analysis of Training Two-Hidden-Layer Partially Over-Parameterized ReLU Networks via Gradient Descent." International Journal of Computer and Information Engineering 14.6 (2020): 166-177.

Li, Yuanzhi, and Yingyu Liang. "Learning overparameterized neural networks via stochastic gradient descent on structured data." Advances in neural information processing systems 31 (2018).

Arora, Sanjeev, et al. "Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks." International Conference on Machine Learning. PMLR, 2019.

Allen-Zhu, Zeyuan, Yuanzhi Li, and Yingyu Liang. "Learning and generalization in overparameterized neural networks, going beyond two layers." Advances in neural information processing systems 32 (2019).

Can a version of the method that is somewhat more agnostic of the knowledge of L0 and L1 be designed, since right now this knowledge is quite necessary for selecting the correct step sizes?

In fact, the problem of knowing $L_0$ and $L_1$ is identical to the standard L-smooth case. It is enough to tune only one parameter $\hat L$, s.t. $\hat L \geq L_0$ and $\hat L \geq L_1$; in the standard case, we tune $\hat L \geq L$. In other words, in practice, it is enough to take a sufficiently large constant $\hat L$. However, in the case of $(L_0, L_1)$- smoothness, the constants itself can be much smaller.

Furthermore, we wish to highlight that GD-PS is agnostic to $L_0$ and $L_1$, the only required parameter $f(x^\ast)$ is often known in many applications, such as overparameterized models. Even when $f(x^\ast)$ is unknown, there are techniques that can adapt to its value, e.g., see (Elan and Kakade, 2019).

Hazan, Elad, and Sham Kakade. "Revisiting the Polyak step size." arXiv preprint arXiv:1905.00313 (2019).

Finally, our result for AdGD of Malitsky and Mishchenko (2019) does not require any knowledge of any parameters while recovering the standard GD rates.

From a quick skim of the literature, it seems that Zhang et al noted in passing that twice differentiability could be dropped at the expense of some more analysis, but the full details of the differentiable case were worked out in subsequent work. This aspect is not clear from how the current work cites related work, and should be fixed.

Indeed, (Zhang et al, 2020b) provides an equivalent assumption for $(L_0, L_1)$ smoothness, not involving Hessian (avoiding twice differentiability). This assumption is very similar to the one we use in our work which originates from (Chen et al., 2023. We explicitly refer this in Lemma 2.1, see line 188. We also added a remark in line 197. See also discussion in lines 826-837 about other notions of generalized smoothness. Our assumption covers the Hessian one (so the assumption we use is more general), but,to the best of our knowledge, the assumption equivalent to the Hessian one can improve our results only up to a constant factor, preserving exponentials at their form, see line 197.

We kindly ask the reviewers to let us know whether our revised version addresses their concern.

While the related work section is overall fairly good, a more precise statement about the results of Chen et al is needed, especially because that work introduced some of the key technical tools too, and studied the nonconvex case; in particular, it would be worth noting what happens if one trivially takes their nonconvex results, and tries to adapt them to the convex case (by boosting stationarity to function suboptimality using the current assumptions). Also, their slightly more general $\alpha$-version of Assumption 3 could be noted.

We respectfully and explicitly refer to (Chen et al., 2023) contribution in Lemma 2.1 (see line 185-187), related work section and extra related work in the appendix. Indeed, our results utilize their assumption. We also discuss the results of the $\alpha$-version of the assumption in Appendix A.

We are not aware of any technique allowing trivially adapts the results of the nonconvex case to the convex case, but we believe that a trivial adaptation does not lead to tight results.

We welcome the reviewer to check the revised version of our manuscript for the improved statement of (Chen et al., 2023) results in appendix A. All the changes are highlighted in red.

Section 5 on acceleration could be deferred to the appendix or noted in passing, and more discussion given to the exponential terms in the bound, which are tantamount to saying that essentially no practical acceleration happens, even though the technical result itself is interesting to note. Similarly, the bounds arising in Section 6 should be discussed a bit more, because due to the central assumption of the paper, ultimately the pessimistic exponential terms in D arise.

Regarding Section 5, our bound for the accelerated method indeed follows from the pessimistic bound on the gradient norm, which leads to the effective smoothness given by the inequality (24). It actually means an accelerated convergence with a pessimistic bound on smoothness constant. Despite a challenge proving better bound due to the term (20), in experiments, we see $(L_0, L_1)$-STM shows a certain acceleration. We also conjecture that the term (20) can be bounded better. We believe this is an interesting open question, and we want to highlight it in the main part.

Regarding Section 6, we also present a pessimistic bound (25) based on (24). Then, in lines 432-435, we point out that the constant in the bound can be huge and then provide the improved result, avoiding additional exponent. We believe that further discussion in lines 450-463 is quite comprehensive since it provides an example that the improved analysis can lead to a convergence rate up to 10^5 times faster; see line 451. However, we would greatly appreciate any suggestions from the reviewer to enhance this discussion.

Dear Reviewer jtK8,

The author discussion phase will be ending soon. The authors have provided detailed responses. Could you please reply to the authors whether they have addressed your concern and whether you will keep or modify your assessment of this submission?

Thanks.

Area Chair

We thank the reviewer for participating in the discussion with us. Below, we address the reviewer's remaining concerns/comments.

As I noted in the review, any bounds involving exponentials can be viewed in spirit as local results; the authors are free to disagree and interpret the bounds whichever way they want, I am just expressing here what I believe would be a valid takeaway for anybody who wants to use the bound for either understanding the algorithm, or for developing subsequent theory of their own.

We respectfully disagree with the takeaway suggested by the reviewer. In particular, the results presented in our Theorems 3.1, 4.1, and 7.1 are independent of any exponential terms and hold globally, i.e., the starting point can be arbitrarily far from a solution. Therefore, it is incorrect to say that our results are local.

The reason I raised the flag about (Zhang et al 2020b) is to make sure that the narrative of the current paper is more accurate. The authors should be a bit more careful in citing related work precisely, otherwise, anybody else who reads this work (or people who read Chen et al) will believe that the possibility of handling only once differentiable functions was first considered by Chen et al, which seems to be not precise, even though, the credit for properly working things out, as well as introducing more refined notions of smoothness belongs to them.

We added the proper reference to the introduction. Please, see our revised version (the end of the second paragraph and footnote 3 on page 3).

In its current version (and even from the authors' reply here), the paper seems to claim greater novelty for dropping twice differentiability.

We never claimed any novelty in dropping twice differentiability.

The question is not about tight results, but for stronger positioning of the current paper it would be valuable to answer this question with mathematical precision. In particular, the zeroth order adaptation (that requires no work), is simply the stationarity result of the nonconvex case also applies to the convex one. The next step of adaptation would be good to put into the motivation part / related work part of the paper, so that is is clear how big a jump from those results is the present work (including, some simple, non-tight results that arise).

In the non-convex case, the convergence is characterized by the norm of the gradient, while in the convex case, the convergence is measured by a stronger criterion - function value sub-optimality, i.e., $f(x^N) - f(x^\ast)$. These two performance criteria are not directly comparable for convex problems, and a small gradient norm does not necessarily imply small function sub-optimality. To illustrate this, consider a Huber loss function $f:\mathbb{R} \to \mathbb{R}$ with parameter $\varepsilon$ defined as follows:

This function is convex and $L$-smooth with $L=1$. Moreover, for any $x\in\mathbb{R}$ we have $|f'(x)| \leq \varepsilon$. However, the function sub-optimality $f(x) - f(x^\ast)$ is unbounded. Therefore, in general, analysis in the non-convex case cannot be easily adapted to the convex case. More precisely, the proofs from Chen et al. (2023) use inequality (7) as a starting point, while our proofs are based on the careful analysis of $\|\|x^k - x^\ast \|\|$. Moreover, Chen et al. (2023) consider normalized versions of GD and SPIDER, while we do not study normalization. Next, the analysis from Chen et al. (2023) does not consider cases when $\|\| \nabla f(x^k) \|\| \geq L_0 / L_1$ and $\|\| \nabla f(x^k) \|\| < L_0 / L_1$ separately and also their analysis does not show two-stage behavior of the considered methods. Therefore, our analysis cannot be seen as an extension of the analysis from Chen et al. (2023).

We believe that we addressed all the reviewer's concerns. Therefore, we kindly ask the reviewer to reconsider their score.

We thank the reviewer for a very positive evaluation of our work. Below, we address the reviewer’s questions and comments.

The paper is missing the conclusion and experiments sections. However, the experiments are provided in the appendix.

We thank the reviewer for the comment. Following the request, we moved the discussion of the related works on gradient clipping and Polyak stepsizes to Appendix A, moved Figure 1 to the main part, and added a conclusion to the paper. All changes are highlighted in red.

The assumptions for stochastic problem is restrictive; however, the derived results are new and better than previous ones

Тhank you for the comment, but the result is indeed non-trivial. A generalization of deterministic results is challenging, since the analysis involves cases when either $\|\| \nabla f(x^k) \|\| \geq L_0 / L_1$ or $\|\| \nabla f(x^k) \|\| < L_0 / L_1$; for the stochastic case we need to consider the norm of stochastic gradient instead. Dealing with the norm of stochastic gradient instead is challenging due to the need to take the expectation (see lines 2025-2035). But we think our analysis of this challenge is already interesting and brings value. The generalization that does not require the over-parameterization assumptions is an interesting direction for future research.

In the last part of the equation (15), should it be N+1 - T instead of N+1?

We believe that the bound is correct. We derive the final bound in (15) by maximizing it with respect to $T$; please, see the further details in Appendix D (lines 1258-1275).

Why is it so crucial to choose $\gamma = 1/4$? In Theorem 6.1, to achieve a rate better than in (25)? Can it be relaxed?

We chose $\gamma = 1/2$ for the sake of simplicity and ease of presentation, but the original paper (Malitsky & Mishchenko, 2020) also provides more complicated analysis allowing larger $\gamma$. We follow the simplicity motivation while setting $\gamma = 1/4$. We reduce $\gamma$ to get an extra term \frac{1}{2}||x^{k+1}-x^k||^2 appearing while introducing $\Sigma_{k+1} = \frac{1}{2} \sum_{i=0}^{k}\| \|x^{i+1} - x^{i}\|\|^2$ to the potential (lines 1663-1667). Having $\Sigma_{k+1}$ to be bounded for all $k$ is crucial for obtaining convergence. But any $\gamma <= 1/2 - \delta$, for any $\delta > 0$ keeps the same results up to the $\delta$ factor in the final rate for the simple approach. We believe that larger stepsizes ($\gamma = 1/2$) lead to faster convergence, but $\gamma = 1/4$ gives a better tradeoff between practical and theoretical performance.

My major concern is about the significance of the results. To be specific, for the first two variants of Gradient Descent, this paper only improves the non-dominant $\mathcal{O}(\sqrt{1/\varepsilon})$ term of iteration complexity, which is inconsequential for small $\varepsilon$, i.e., when finding a solution with good quality.

As I mentioned in the Weaknesses section, are there any practical examples (either theoretical or experimental) that can justify the importance of the improved complexities?

We emphasize that our results hold without $L$-smoothness assumption, while the existing results for Clipped GD and GD with Polyak Stepsize do require standard L-smoothness, and, in particular, the mentioned $\mathcal{O}(\sqrt{1/\varepsilon})$ term is proportional to $\sqrt{L}$. Of course, one can show that for small enough stepsize parameters, the methods do not escape the ball centered at the solution and have radius $\|\| x^0 - x^\ast \|\|$. However, the smoothness constant is dependent on the size of this ball. This means that the $\mathcal{O}(\sqrt{1/\varepsilon})$ term can be the leading one even for very small values of $\varepsilon$. To illustrate this, consider the function from Example 1.1: $f(x) = \|\| x \|\|^{2n}$. As we show in Appendix B, it is $(2n, 2n-1)$-smooth, but it is not smooth for $n \geq 2$ on the whole space. However, on the ball centered at $0$ and radius $\|\| x^0 \|\|$ the smoothness constant equals $2n(2n-1)\|\| x^0 \|\|^{2n-2}$. For example, if $n=5$ and $\|\| x^0 -x^\ast \|\| = 10$, then $L_0 = 10, L_1 = 9$ and the smoothness constant on the mentioned ball equals $L = 9\cdot 10^9$. Plugging these values in the bound $\mathcal{O}(\max\{L_0R_0^2/\varepsilon, \sqrt{R_0^4 LL_1^2/\varepsilon}\})$ term shown by (Koloskova et al., 2023; Takezawa et al., 2024), we observe that the second term is dominant even for small values of $\varepsilon = 10^{-6}$. In contrast, the leading term in our bound $\mathcal{O}(\max\{L_0R_0^2/\varepsilon, L_1^2 R_0^2\})$ is the first one and it is significantly smaller than $\mathcal{O}(\sqrt{R_0^4 LL_1^2/\varepsilon})$ term even for reasonably small values of $\varepsilon$. Moreover, as one can see from Lemma 2.1, the smoothness constant on the described ball is proportional to $\exp(L_1\|\| x^0 - x^\ast \|\|)$ in the worst case, i.e., it can be exponentially large. We also highlight that our result for $(L_0, L_1)$-GD provides a refined characterization of the method’s behavior: we prove that the norm of the gradient is non-increasing and that the method’s convergence has two clear phases (large gradient and small gradient regimes). Previous results do not provide such detailed characterization. Considering all of these aspects, we believe that our results make a noticeable and significant improvement over the previous ones.

For the adapted versions of Similar Triangles Method and Adaptive Gradient Descent, the iteration complexity is in the form of $\mathcal{O}(\sqrt{L_0L_1A\exp(L_1A)A^2/\varepsilon^2})$, where $A$ equals either $R_0$ or $D$, which generally aligns with a specification of Li et al. (2024).

Indeed, as we explain in lines 409-416, our result for $(L_0, L_1)$-STM matches the result derived by Li et al. (2024) in the case of $(L_0, L_1)$-smooth problems, though we consider a different method, which is of the interest on its own. However, Adaptive Gradient Descent (AdGD) is not considered by Li et al. (2024), and, in particular, our Theorem 6.1 gives the result of a different form. To achieve this, we modify the proof of AdGD significantly – see the proof of Theorem G.2 in Appendix G.2. This new approach to the analysis of AdGD allows us to show a better bound than the one that directly follows from $(L_0, L_1)$-smoothness and existing analysis by Malitsky & Mishchenko (2020) (see more details in lines 424-450 and the discussion after Theorem 6.1).

Thus, the overall contribution in terms of novel theoretical guarantees appears quite limited to me at this stage.

We hope that our above responses clarify the novelty of the derived results. Moreover, we also highlight that in Section 7, we provide the results for the stochastic extensions of $(L_0, L_1)$-GD and GD-PS. These results are novel, and the proof technique is also also new for stochastic optimization, e.g., see lines 2004-2051 – we are unaware of similar tricks used in prior works on stochastic optimization.

You mention new technical results for $(L_0,L_1)$-smooth functions in Section 1.3. Could you specify these results for reference?

Lemma 2.2 is new and provides several useful inequalities. In particular, we are not aware of analogs of inequality (10) in the literature on generalized smoothness. Moreover, in the revised version, we expanded the discussion about the relation to the known analogs of inequalities (8) and (11) from (Koloskova et al., 2023; Li et al., 2024a).

For Theorem 3.1, it appears that you integrate the analyses from Li et al. (2024) and Koloskova et al. (2023), substituting the normalization term $\ell(G)$ in $\eta$ into something related to $\|\|\nabla f(x^k)\|\|$, so that the sequence enjoys the monotonic properties and can be analyzed in two cases. Could you elaborate on the intuition behind this approach?

Our proof follows the one from (Koloskova et al., 2023), which follows the analysis of standard GD. Then, similarly to (Koloskova et al., 2023), we consider two possible situations: either $\|\| \nabla f(x^k) \|\| \geq L_0 / L_1$ or $\|\| \nabla f(x^k) \|\| < L_0 / L_1$. In the second case, the gradient is small, and $L_1$-term in $(L_0, L_1)$-smoothness is dominated by $L_0$-term, i.e., in inequality (8), the denominator of the left-hand side is $\mathcal{O}(L_0)$. In this case, the method behaves as standard GD for $L$-smooth problems with $L = \mathcal{O}(L_0)$. However, when $\|\| \nabla f(x^k) \|\| \geq L_0/L_1$, the $L_1$-term in $(L_0, L_1)$-smoothness is the leading one and this is the crucial difference between our proof and the one obtained by Koloskova et al. (2023): to handle this case, we use (8) and show that such situations lead to the decrease of $\|\| x^{k+1} - x^\ast \|\|^2$ by some positive constant $\nu\eta / (8L_1^2)$. In contrast, Koloskova et al. (2023) use traditional smoothness, which leads to worse complexity, as we explained in our first response. Moreover, Lemma 3.2 shows that the gradient norm is non-increasing along the trajectory of the method – similar to standard GD (e.g., see Lemma C.3 from [1]).

Next, Li et al. (2024a) show that under $(r,\ell)$-smoothness, the function is locally smooth, and thus, the standard analysis of GD for smooth problems can be applied under the assumption that the stepsize is sufficiently small. However, this approach leads to a worse dependency on $L_0$ and $L_1$ than we have in our bounds for $(L_0, L_1)$-GD, as we explain in lines 147-153.

Typos and minor suggestions

We thank the reviewer for spotting the typos and for the suggestions. We incorporated all of them in the revised version. All the changes are highlighted in red.

— References

[1] Gorbunov et al. Extragradient Method: O (1/K) Last-Iterate Convergence for Monotone Variational Inequalities and Connections With Cocoercivity. AISTATS 2022

Dear Reviewer RdU1,

The author discussion phase will be ending soon. The authors have provided detailed responses. Could you please reply to the authors whether they have addressed your concern and whether you will keep or modify your assessment of this submission?

Thanks.

Area Chair