Toward a Unified Theory of Gradient Descent under Generalized Smoothness

Alexander Tyurin

REVIEW 3 major objections 4 minor 16 references

Toward a Unified Theory of Gradient Descent under Generalized Smoothness

T0 review · 3 major / 4 minor · reviewed 2026-08-11 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A single adaptive step size rule for gradient descent is proven to work under generalized smoothness, including the previously open case where the Hessian grows quadratically with the gradient norm.

desk verdict First nonconvex GD rate for ρ=2 under generalized smoothness, proved cleanly; the 'unified' claim has a real boundary at superquadratic ℓ unless gradients are bounded. read the letter →

arxiv 2412.11773 v2 pith:O33LZKML submitted 2024-12-16 math.OC

Alexander Tyurin This is my paper · ORCID

classification math.OC MSC 90C2590C3065K05

keywords gradientdescentgeneralizedsmoothnessℓ-smoothnessadaptivestepsize(L0L1)-smoothnessnonconvexoptimizationconvexstochastic

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Under the assumption that the Hessian norm is bounded by a nondecreasing function of the gradient norm, $\|\nabla^2 f(x)\| \leq \ell(\|\nabla f(x)\|)$, this paper derives a new adaptive step size for gradient descent: $\gamma_k = \int_0^1 \frac{dv}{\ell(\|\nabla f(x_k)\| + \|\nabla f(x_k)\| v)}$. This step size is the exact minimizer of a generalized quadratic upper bound, so it plays the role that $1/L$ plays in classical smooth optimization. The paper proves a master nonconvex bound that yields explicit convergence rates for $(\rho, L_0, L_1)$-smooth functions, including the first guarantee for plain gradient descent in the previously open quadratic-growth case $\rho = 2$. In the convex and stochastic settings it also improves the known rates, reducing the dominant term for small $\varepsilon$ from $\ell(\|\nabla f(x_0)\|)R^2/\varepsilon$ to $\ell(0)R^2/\varepsilon$. If these results hold, one adaptive rule unifies $L$-smoothness, $(L_0, L_1)$-smoothness, and more general growth models under a single theory.

What carries the argument

The central object is the $q$-function $q(s; a) = \int_0^s dv/\ell(a+v)$ and its inverse $q^{-1}$; under $\ell$-smoothness, $q^{-1}(\|y-x\|; \|\nabla f(x)\|)$ bounds the change in gradient along a segment (Lemma 4.3), and integrating it gives a generalized descent lemma (Lemma 4.5). Minimizing the right-hand side of that lemma over step direction and length yields the step size $\gamma_k$ as the optimal point (Corollary 4.6), and the identity $q^{-1}(\gamma_k \|\nabla f(x_k)\|; \|\nabla f(x_k)\|) = \|\nabla f(x_k)\|$ lets the proofs sidestep computing $q^{-1}$ explicitly. The monotone function $\psi_2(x) = x^2/\ell(2x)$ is what converts the master nonconvex bound into an explicit gradient-norm rate; the convex theory instead uses a two-phase argument (Theorem 8.1) based on the fact that the gradient norms $\|\nabla f(x_k)\|$ are nonincreasing along the iterates.

What would settle it

Take the $(2, 800, 2)$-smooth function $f(x) = -\log x - \log(0.1 - x)$ from the paper's experiments, run Algorithm 1 from $x_0 = 10^{-7}$, and measure the iteration count $T(\varepsilon)$ needed to reach $\|\nabla f(x_k)\|^2 \le \varepsilon$ as $\varepsilon \to 0$; the claimed rate $O(800\Delta/\varepsilon + 2\Delta)$ predicts $T(\varepsilon)$ grows like $1/\varepsilon$, so observing growth like $1/\varepsilon^2$ would falsify the $\rho = 2$ nonconvex claim.

Watch

Extended reading notes

Core claim

With $f$ twice differentiable on an open convex domain and a nondecreasing, positive, locally Lipschitz function $\ell$ satisfying $\|\nabla^2 f(x)\| \leq \ell(\|\nabla f(x)\|)$ for all $x$, the paper defines the step size $\gamma_k = \int_0^1 dv / \ell(\|\nabla f(x_k)\| + \|\nabla f(x_k)\| v)$ and proves that gradient descent with this step size satisfies $f(x_{k+1}) \leq f(x_k) - \tfrac{\gamma_k}{4}\|\nabla f(x_k)\|^2$, hence $\min_{0 \le k < T} \|\nabla f(x_k)\|^2 / \ell(2\|\nabla f(x_k)\|) \leq 4\Delta / T$. Under the additional hypothesis that $\psi_2(x) = x^2/\ell(2x)$ is strictly increasing and unbounded, this master bound converts into explicit rates: for $(\rho, L_0, L_1)$-smoothness with $0 \le \rho \le 2$, an $\varepsilon$-stationary point is found in $O(L_0\Delta/\varepsilon + L_1\Delta/\varepsilon^{(2-\rho)/2})$ iterations, and for $\rho = 2$ the rate is $O(L_0\Delta/\varepsilon + L_1\Delta)$, a case for which no plain-GD guarantee previously existed. When $\ell$ grows superquadratically, the same bound yields rates under an additional bounded-gradient assumption $\|\nabla f(x)\| \le M$. In the convex setting, the paper improves the dominating term for small $\varepsilon$ from $\ell(\|\nabla f(x_0)\|)R^2/\varepsilon$ to $\ell(0)R^2/\varepsilon$, discovers a new min-term $L_1\Delta^{1/2}R/\varepsilon^{1/2}$ for $(L_0, L_1)$-smoothness, and gives a stochastic version whose small-$\varepsilon$ complexity matches known lower bounds up to logarithms.

Load-bearing premise

The explicit nonconvex rates require the map $\psi_2(x) = x^2/\ell(2x)$ to be strictly increasing and unbounded, which holds for polynomial growth with $\rho \le 2$ but fails when $\ell$ grows superquadratically, forcing the paper to assume bounded gradients ($\|\nabla f(x)\| \le M$) for the $\rho > 2$ and exponential cases.

Editorial extensions

If this is right

For $(2, L_0, L_1)$-smooth nonconvex functions, plain gradient descent now has a proof of convergence with rate $O(L_0\Delta/\varepsilon + L_1\Delta)$, covering a case previously listed as open in the $\ell$-smoothness literature.
For $(\rho, L_0, L_1)$-smooth functions with $0 \le \rho < 2$, the dependence on the initial gradient norm disappears: the rate improves from $O(\ell(\|\nabla f(x_0)\|)\Delta/\varepsilon)$ to $O(L_0\Delta/\varepsilon + L_1\Delta/\varepsilon^{(2-\rho)/2})$.
In the convex setting, for small target accuracy $\varepsilon$, gradient descent with the new step size behaves like classical GD with step size $1/\ell(0)$, giving a $\Theta(\ell(0)R^2/\varepsilon)$ rate that no longer involves the possibly large initial gradient norm.
The new convex term $L_1\Delta^{1/2}R/\varepsilon^{1/2}$ for $(L_0, L_1)$-smooth functions can be substantially better than the earlier $L_1^2R^2$ or $L_1\|\nabla f(x_0)\|R^2/\varepsilon$ terms when the distance $R$ to the optimum is large.
The stochastic extension achieves, for small $\varepsilon$, complexity $\tilde{O}(\sigma^2 L_0 \Delta/\varepsilon^2)$ up to log factors, recovering the known lower bound for smooth stochastic nonconvex optimization.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Because the step size is defined solely from $\ell$ and the current gradient norm, it can be implemented by numerical quadrature without tuning $L_0$ or $L_1$; a natural testable question is whether it is competitive with tuned clipping in large-scale training with unknown smoothness constants.
The identity $q^{-1}(\gamma_k \|\nabla f(x_k)\|; \|\nabla f(x_k)\|) = \|\nabla f(x_k)\|$ suggests a design principle for other first-order methods—choose the step so that one step limits the gradient change to the current gradient norm—which may extend to heavy-ball or adaptive methods under the same growth model.
The master bound $\min_k \|\nabla f(x_k)\|^2/\ell(2\|\nabla f(x_k)\|) \le 4\Delta/T$ may itself be the meaningful stationarity measure when $\ell$ is superquadratic; whether that measure supports a useful complexity theory without bounded gradients is left open.
A direct stress test is to measure $T(\varepsilon)$ on the paper's own example $f(x) = -\log x - \log(0.1-x)$ at smaller $\varepsilon$ than reported; if the $L_1\Delta$ term is real, the iteration count should scale as $1/\varepsilon$, not $1/\varepsilon^2$.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Colleague,

Two things to know. First, the paper delivers a real result: under (2,L0,L1)-smoothness — the ρ=2 case that Li et al. explicitly left open — gradient descent with the step size γ_k = ∫_0^1 dv/ℓ(‖∇f(x_k)‖ + ‖∇f(x_k)‖v) converges at rate O(L0Δ/ε + L1Δ) for nonconvex functions. The same step size rule cleans up the convex theory, improving the leading term from ℓ(‖∇f(x0)‖)R²/ε to ℓ(0)R²/ε. I checked the descent lemma and the convex potential argument in the appendix; they are correct. The step size is derived by minimizing a pointwise upper bound, and no constants are fitted; the proofs use only the rule plus the smoothness assumption.

Second, the title's "unified" is doing some work. The main nonconvex guarantee is a quotient bound, min ‖∇f‖²/ℓ(2‖∇f‖) ≤ 4Δ/T. Converting that into a rate for ‖∇f‖² requires the map ψ_2(x)=x²/ℓ(2x) to be increasing. For ℓ(s)=L0+L1s^ρ with ρ>2, ψ_2 tends to 0, the conversion fails, and the paper recovers a rate only under Assumption 6.1, a global bounded-gradient bound that is strong and not usually verifiable. The paper labels this clearly and I don't see a proof error; but "unified" oversells it. The nonconvex theory is genuinely general for ρ≤2, and conditional on bounded gradients beyond that.

The stochastic extension has a smaller version of the same issue: Algorithm 2 requires r=sup ℓ(2s)/ℓ(s), which is infinite for exponential ℓ, making the step size zero. The paper doesn't exclude that case. Again not a proof error, but a reader running the motivating examples from Section 2 will hit it.

Minor: the experiments have no code or data. For a theory paper's illustrative Figure 2 that's a small thing.

Who is this for? Anyone working on (L0,L1)-smoothness, clipping, and generalized smoothness will want the ρ=2 rate and the convex improvement. It deserves a serious referee. I'd recommend sending it to review, with the likely outcome being acceptance after the authors either temper the "unified" language in the nonconvex part or state the superquadratic caveat up front and fix the stochastic r=∞ edge.

Referee Report

3 major / 4 minor

Summary. The paper studies gradient descent under the generalized smoothness assumption ||∇²f(x)|| ≤ ℓ(||∇f(x)||) for a nondecreasing locally Lipschitz positive function ℓ. Its main technical contribution is the step-size rule γ_k = ∫_0^1 dv / ℓ(||∇f(x_k)|| + ||∇f(x_k)|| v), which minimizes a pointwise upper bound derived from the generalized descent lemma. The central nonconvex result, Theorem 5.1, gives the monotonicity inequality f(x_{k+1}) ≤ f(x_k) − (γ_k/4)||∇f(x_k)||² and the quotient bound min_k ||∇f(x_k)||² / ℓ(2||∇f(x_k)||) ≤ 4Δ/T. Under the additional condition that ψ_2(x) = x²/ℓ(2x) is strictly increasing, Corollary 5.2 converts this into a rate on the gradient norm; this recovers classical L-smoothness, matches the best known (L0,L1)-smoothness rate, and gives the first nonconvex GD rate for (2,L0,L1)-smoothness. The paper also proves convex rates (Theorems 7.2, 8.1, 8.3), derives small-ε corollaries with dominant term ℓ(0)R²/ε, extends the analysis to stochastic gradients (Theorem 9.2), and reports numerical experiments on two one-dimensional examples.

Significance. If the results are taken as stated, the paper makes a solid contribution: it identifies a single adaptive step-size rule that provably recovers the L-smoothness rate, improves the existing (ρ,L0,L1)-smoothness rates for ρ<2, closes the previously open ρ=2 case, and gives new convex rates whose leading term ℓ(0)R²/ε is stronger than the earlier ℓ(||∇f(x0)||)R²/ε dependence. The proofs are unusually transparent: Theorem 5.1 is short, the descent inequality and the ψ_2 inversion in Corollary 5.2 check out, and the convex potential Lemma I.2 is correct. The main novelty is the step-size formula itself, and the paper deserves credit for presenting it as a clean, parameter-free derivation rather than as a fitted schedule. The significance is tempered by the fact that the universal quotient bound does not automatically yield a gradient-norm rate for superquadratic ℓ; the nonconvex treatment of ρ>2 and exponential ℓ requires Assumption 6.1, and the stochastic extension requires a finite ratio r = sup_s ℓ(2s)/ℓ(s). These are real restrictions on the 'unified' claim, though they do not invalidate the central mechanism.

major comments (3)

[Section 1.2 and Section 6] The text in Section 1.2 says the theory 'remains applicable to virtually any ℓ functions,' but this is true only for the quotient guarantee (9), not for the gradient-norm convergence rates advertised in Table 1. For ℓ(s) = L0 + L1s^ρ with ρ>2, the map ψ_2(x) = x²/ℓ(2x) is not increasing and in fact tends to 0 at infinity, so Corollary 5.2 cannot be invoked; the paper itself acknowledges this in Section 6 and imposes the bounded-gradient Assumption 6.1 to obtain rates. The manuscript should reword the universality claim so that it refers to the quotient bound and the step-size rule, and should state clearly in the introduction that nonconvex gradient-norm rates for superquadratic ℓ are obtained only under Assumption 6.1.
[Section 9, Algorithm 2, Theorem 9.2] Theorem 9.2 is stated for the general ℓ-smoothness assumption without requiring r = sup_{s≥0} ℓ(2s)/ℓ(s) to be finite, yet Algorithm 2 divides the step size by 5r and the proof uses the bound r ≥ ℓ(||∇f(x_k)|| + ||∇f(x_k)||v)/ℓ(||∇f(x_k)||(1+v)/2). For ℓ(s) = L0 + L1s²e^s, for instance, r = ∞ and the algorithm prescribes γ_k = 0, so the theorem is vacuous in exactly the cases that the paper highlights as novel. The theorem statement and Algorithm 2 should explicitly impose r < ∞, and the text should note that the stochastic extension covers ℓ with at most exponential growth only when the ratio is finite.
[Corollary 5.2 and Section 5.3] The conversion of the quotient bound into the explicit rate (12) is sound for 0 ≤ ρ ≤ 2, but the paper should be more careful about the condition 'ψ_2 is strictly increasing' in Corollary 5.2. The condition is not merely a technical convenience: without it, the quotient min_k ||∇f(x_k)||²/ℓ(2||∇f(x_k)||) can be small precisely because ||∇f(x_k)|| is large, so no bound on the gradient norm follows. Placing this remark immediately after Theorem 5.1, rather than only in the later superquadratic section, would prevent the reader from overreading the main theorem as a universal gradient-norm guarantee.

minor comments (4)

[Section 5.3] There is a typo in the displayed definition of ℓ: 'ℓ(s) = ℓ(s) = L0 + L1s^ρ' repeats ℓ(s); also Remark 4.7 says 'for any p ≥ 0' where the variable is ρ.
[Corollary 5.2] The condition 'for all T ≥ 1 such that 2 8∆/T ∈ im(ψ_2)' appears to contain a typo: the factor should be 8∆/T, matching the bound in (10).
[Theorem 9.2 proof] In the last paragraph of the proof of Theorem 9.2, the text says to sum the descent inequality and 'use Assumption 6.1'; the argument only needs the lower bound on f from Assumption 3.2, not the bounded-gradient Assumption 6.1. This should be corrected.
[Section 9, after Theorem 9.2] The sentence 'Overall, for any ℓ, the total number of computed stochastic gradients is Θ(B × T)' is too strong in view of the finite-r issue; it should be qualified to hold for ℓ with r < ∞.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the step-size rule is derived from the ℓ-smoothness upper bound, and the convergence rates follow by explicit algebra from the descent lemma; no fitted constants or load-bearing self-citations.

full rationale

The derivation chain is self-contained and non-circular. Assumption 3.1 (ℓ-smoothness) is used in Lemma 4.3 to prove the generalized gradient-difference bound (6) via a Gronwall argument, and Lemma 4.5 integrates this bound into the upper bound (8). Corollary 4.6 then minimizes (8) exactly, yielding the step size γ_k = ∫_0^1 dv / ℓ(‖∇f(x_k)‖ + ‖∇f(x_k)‖v); this is a genuine minimization of the proven upper bound, not an ansatz that presupposes the final rate. Theorem 5.1 follows by summing the descent inequality f(x_{k+1}) ≤ f(x_k) − (γ_k/4)‖∇f(x_k)‖² and using the lower bound γ_k ≥ 1/ℓ(2‖∇f(x_k)‖), giving the quotient bound (9). Corollary 5.2 and the rate conversions in Section 5.3 are straightforward algebra with ψ₂(x) = x²/ℓ(2x); the paper explicitly notes where the conversion requires ψ₂ to be increasing and where it fails (Section 6), and it does not hide that superquadratic ℓ needs the extra bounded-gradient Assumption 6.1. No parameter is fitted to data, no prediction is a renamed input, and no load-bearing claim rests on a self-citation — the author has no self-citations, and references to Li et al. (2024a) and Vankov et al. (2024) are used for the assumption and proof techniques, not to import the target theorem. The main honest weakness is a correctness/generality limitation rather than circularity: for superquadratic ℓ with unbounded gradients the nonconvex guarantee reduces to a quotient and does not yield a gradient-norm rate, and Algorithm 2's ratio r = sup ℓ(2s)/ℓ(s) can be infinite for exponential ℓ, making the step size zero. These limitations are explicitly acknowledged in the paper and are weighed as scope restrictions, not as circular derivations.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

No new physical or algorithmic entities are postulated. The q-function (Definition 4.1) is a mathematical tool introduced for the proofs, not an entity with independent evidence requirements.

assumptions (6)

domain assumption Assumption 3.1 (ℓ-smoothness): ||∇²f(x)|| ≤ ℓ(||∇f(x)||) for a non-decreasing positive locally Lipschitz ℓ
This defines the class of functions studied; all results are conditional on it. Invoked throughout the paper.
domain assumption Assumption 3.2: f is bounded below on X
Needed for the descent sum in Theorem 5.1 to yield a finite bound.
domain assumption Assumption 7.1: f is convex and attains a minimum
Used in the convex analysis (Lemma I.1, Theorems 7.2 and 8.1).
domain assumption Assumption 6.1: bounded gradients ||∇f(x)|| ≤ M for superquadratic ℓ
Only assumed in Section 6 and used for ρ>2 and exponential ℓ; it is a strong restriction and is the paper's least universal premise.
domain assumption Assumption 9.1: light-tailed stochastic gradients with E[exp(||∇f(x;ξ)-∇f(x)||²/σ²)] ≤ exp(1)
Used in the stochastic SGD section for concentration inequalities.
standard math Grönwall's lemma and standard Taylor expansion
Used in the proofs of Lemmas 4.3 and 4.5 to control gradient differences along a line.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Toward a Unified Theory of Gradient Descent under Generalized Smoothness." pith.science (2026). https://pith.science/paper/O33LZKML

@misc{pith2026241211773,
  author       = {Pith},
  title        = {Pith review of: Toward a Unified Theory of Gradient Descent under Generalized Smoothness},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/O33LZKML}},
  note         = {Machine review of arXiv:2412.11773}
}

abstract

We study the classical optimization problem $\min_{x \in \mathbb{R}^d} f(x)$ and analyze the gradient descent (GD) method in both nonconvex and convex settings. It is well-known that, under the $L$-smoothness assumption ($\|\nabla^2 f(x)\| \leq L$), the optimal point minimizing the quadratic upper bound $f(x_k) + \langle\nabla f(x_k), x_{k+1} - x_k\rangle + \frac{L}{2} \|x_{k+1} - x_k\|^2$ is $x_{k+1} = x_k - \gamma_k \nabla f(x_k)$ with step size $\gamma_k = \frac{1}{L}$. Surprisingly, a similar result can be derived under the $\ell$-generalized smoothness assumption ($\|\nabla^2 f(x)\| \leq \ell(\|\nabla f(x)\|)$). In this case, we derive the step size $$\gamma_k = \int_{0}^{1} \frac{d v}{\ell(\|\nabla f(x_k)\| + \|\nabla f(x_k)\| v)}.$$ Using this step size rule, we improve upon existing theoretical convergence rates and obtain new results in several previously unexplored setups.

Figures

Figures reproduced from arXiv: 2412.11773 by the authors.

**Figure 2.** Experiment with f(x) = − log x − log(0.1 − x). We repeat this experiment with the function f : R → R defined as f(x) = e x + e 1−x (see [PITH_FULL_IMAGE:figures/full_fig_p011_2.png] view at source ↗

**Figure 3.** Experiment with f(x) = e x + e 1−x . 4 finds x¯ such that f(¯x) − f(x∗) ≤ 10−5 11 [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

16 extracted references · 9 canonical work pages

[1]

For any M ≥ 0, taking ¯T (M ) such that ∥∇f (x ¯T )∥ ≤M, we get f (xT ) − f (x∗) ≤ ℓ(2M ) ∥x0 − x∗∥2 2(T − ¯T (M ) + 1)

, where use the inequalities ∥x0 − x∗∥2 ≥ ∥x ¯T − x∗∥2 ≥ ∥xT − x∗∥2 ≥ 0 due to (33). For any M ≥ 0, taking ¯T (M ) such that ∥∇f (x ¯T )∥ ≤M, we get f (xT ) − f (x∗) ≤ ℓ(2M ) ∥x0 − x∗∥2 2(T − ¯T (M ) + 1). Thus, after ¯T (M ) + ℓ(2M ) ∥x0 − x∗∥2 2ε iterations the inequality f (xT ) − f (x∗) ≤ ε holds. The final result holds since M >0 is arbitrary. 18 Tow...

work page 2008
[3]

This function is (3.3, 1)–smooth, meaning we can run Algorithm 1 with ℓ(s) = 3.3 + s

which has its minimum at x∗ = 0.5. This function is (3.3, 1)–smooth, meaning we can run Algorithm 1 with ℓ(s) = 3.3 + s. It converges after at most 20 iterations. At the same time, if we choose ℓ(s) = 3.3 + s2 or γk = (3.3 + 2|f ′(x0)|)−1 (Li et al., 2024a), GD requires at least 200 iterations to converge. These experiments underscore the importance of ou...

work page
[4]

and Nemirovski, A

Juditsky, A. and Nemirovski, A. S. Large deviations of vector-valued martingales in 2-smooth normed spaces. arXiv preprint arXiv:0809.0813,

arXiv
[5]

B., Yu, F

Koneˇcn´y, J., McMahan, H. B., Yu, F. X., Richt ´arik, P., Suresh, A. T., and Bacon, D. Federated learning: Strate- gies for improving communication efficiency. arXiv preprint arXiv:1610.05492,

arXiv
[7]

Vankov, D., Rodomanov, A., Nedich, A., Sankar, L., and Stich, S. U. Optimizing (L0, L1)-smooth functions by gra- dient methods. arXiv preprint arXiv:2410.10800,

arXiv
[8]

Gradient-Variation Online Learning under Generalized Smoothness

Xie, Y .-F., Zhao, P., and Zhou, Z.-H. Gradient-variation online learning under generalized smoothness. arXiv preprint arXiv:2408.09074,

work page Pith review arXiv
[9]

Why gradient clipping accelerates training: A theoretical justification for adaptivity

Zhang, J., He, T., Sra, S., and Jadbabaie, A. Why gradient clipping accelerates training: A theoretical justification for adaptivity. arXiv preprint arXiv:1905.11881,

arXiv 1905
[11]

Next, we take the step size γk = 1/(800 + 2(2f ′(x0))2) from (Li et al., 2024a) and observe that GD requires at least 20.000 iterations because f ′(x0) is huge

Consequently, we run Algorithm 1 with ℓ(s) = 800 + 2s2, starting at x0 = 10−7, and observe that it converges4 after 75 iterations. Next, we take the step size γk = 1/(800 + 2(2f ′(x0))2) from (Li et al., 2024a) and observe that GD requires at least 20.000 iterations because f ′(x0) is huge. Finally, to verify whether the exponent 2 is necessary, we take ℓ...

work page 2024

Show all 16 references

[13]

Using the standard differential algebra, we can solve it: dg(t) ℓ(∥∇f (x)∥ + g(t)) = dt ⇒ Z t 0 dg(v) ℓ(∥∇f (x)∥ + g(v)) = t ⇒ Z g(t) 0 dv ℓ(∥∇f (x)∥ + v) = t

Instead of this inequality, consider the differential equation g′(t) = ℓ(∥∇f (x)∥ + g(t)), g (0) = 0, (23) where g : R+ → R is a solution, and ∥∇f (x)∥ is a fixed quantity. Using the standard differential algebra, we can solve it: dg(t) ℓ(∥∇f (x)∥ + g(t)) = dt ⇒ Z t 0 dg(v) ℓ(...

1919
[14]

If ρ ≤ 2, then we can guarantee mink∈{0,...,T −1} ∥∇f (xk)∥2 ≤ ε after at most max 8L0∆ ε , 32L1∆ ε(2−ρ)/2 iterations. H. Derivation of the Rate from Section 6.2 Using (29), either min k∈{0,...,T −1} ∥∇f (xk)∥2 ≤ 8L0∆ T or max k∈{0,...,T −1} ∥∇f (xk)∥ρ−2 ≥ T 2ρ+3L1∆ . We now r...

2018
[15]

Due to the strategy from Alg

Proof. Due to the strategy from Alg. 1, we get ∥xk+1 − x∗∥2 = ∥xk − x∗∥2 − 2γk ⟨xk − x∗, ∇f (xk)⟩ + γ2 k ∥∇f (xk)∥2 . (32) We now consider the last two terms: − 2γk ⟨xk − x∗, ∇f (xk)⟩ + γ2 k ∥∇f (xk)∥2 = 2γk (−f (x∗) + f (xk) + ⟨∇f (xk), x∗ − xk⟩ −f (xk) + f (x∗)) + γ2 k ∥∇f (...

2024
[2017]

Polyak meets parameter-free clipped gradient descent

Takezawa, Y ., Bao, H., Sato, R., Niwa, K., and Yamada, M. Polyak meets parameter-free clipped gradient descent. arXiv preprint arXiv:2405.15010,

arXiv
[2019]

10 Toward a Unified Theory of Gradient Descent under Generalized Smoothness A. Experiments We verify our theoretical results by asking whether it is necessary to use the step size rule from Algorithm 1, and maybe it is sufficient to use the step size rules by Li et al. (2024a)...

2024
[2022]

Methods for convex (L0, L1)-smooth optimization: Clipping, acceler- ation, and adaptivity

Gorbunov, E., Tupitsa, N., Choudhury, S., Aliev, A., Richt´arik, P., Horv´ath, S., and Tak ´aˇc, M. Methods for convex (L0, L1)-smooth optimization: Clipping, acceler- ation, and adaptivity. arXiv preprint arXiv:2409.14989,

arXiv
[2023]

A theoretical study of the(l 0, l1)-smoothness condition in deep learning

Cooper, Y . A theoretical study of the(l 0, l1)-smoothness condition in deep learning. In OPT 2024: Optimization for Machine Learning,

2024
[2024]

Grimmer, B., Shu, K., and Wang, A. L. Accelerated ob- jective gap and gradient norm convergence for gradient descent via long steps. arXiv preprint arXiv:2403.14045,

arXiv

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.

[1] [1]

For any M ≥ 0, taking ¯T (M ) such that ∥∇f (x ¯T )∥ ≤M, we get f (xT ) − f (x∗) ≤ ℓ(2M ) ∥x0 − x∗∥2 2(T − ¯T (M ) + 1)

, where use the inequalities ∥x0 − x∗∥2 ≥ ∥x ¯T − x∗∥2 ≥ ∥xT − x∗∥2 ≥ 0 due to (33). For any M ≥ 0, taking ¯T (M ) such that ∥∇f (x ¯T )∥ ≤M, we get f (xT ) − f (x∗) ≤ ℓ(2M ) ∥x0 − x∗∥2 2(T − ¯T (M ) + 1). Thus, after ¯T (M ) + ℓ(2M ) ∥x0 − x∗∥2 2ε iterations the inequality f (xT ) − f (x∗) ≤ ε holds. The final result holds since M >0 is arbitrary. 18 Tow...

work page 2008

[2] [3]

This function is (3.3, 1)–smooth, meaning we can run Algorithm 1 with ℓ(s) = 3.3 + s

which has its minimum at x∗ = 0.5. This function is (3.3, 1)–smooth, meaning we can run Algorithm 1 with ℓ(s) = 3.3 + s. It converges after at most 20 iterations. At the same time, if we choose ℓ(s) = 3.3 + s2 or γk = (3.3 + 2|f ′(x0)|)−1 (Li et al., 2024a), GD requires at least 200 iterations to converge. These experiments underscore the importance of ou...

work page

[3] [4]

and Nemirovski, A

Juditsky, A. and Nemirovski, A. S. Large deviations of vector-valued martingales in 2-smooth normed spaces. arXiv preprint arXiv:0809.0813,

arXiv

[4] [5]

B., Yu, F

Koneˇcn´y, J., McMahan, H. B., Yu, F. X., Richt ´arik, P., Suresh, A. T., and Bacon, D. Federated learning: Strate- gies for improving communication efficiency. arXiv preprint arXiv:1610.05492,

arXiv

[5] [7]

Vankov, D., Rodomanov, A., Nedich, A., Sankar, L., and Stich, S. U. Optimizing (L0, L1)-smooth functions by gra- dient methods. arXiv preprint arXiv:2410.10800,

arXiv

[6] [8]

Gradient-Variation Online Learning under Generalized Smoothness

Xie, Y .-F., Zhao, P., and Zhou, Z.-H. Gradient-variation online learning under generalized smoothness. arXiv preprint arXiv:2408.09074,

work page Pith review arXiv

[7] [9]

Why gradient clipping accelerates training: A theoretical justification for adaptivity

Zhang, J., He, T., Sra, S., and Jadbabaie, A. Why gradient clipping accelerates training: A theoretical justification for adaptivity. arXiv preprint arXiv:1905.11881,

arXiv 1905

[8] [11]

Next, we take the step size γk = 1/(800 + 2(2f ′(x0))2) from (Li et al., 2024a) and observe that GD requires at least 20.000 iterations because f ′(x0) is huge

Consequently, we run Algorithm 1 with ℓ(s) = 800 + 2s2, starting at x0 = 10−7, and observe that it converges4 after 75 iterations. Next, we take the step size γk = 1/(800 + 2(2f ′(x0))2) from (Li et al., 2024a) and observe that GD requires at least 20.000 iterations because f ′(x0) is huge. Finally, to verify whether the exponent 2 is necessary, we take ℓ...

work page 2024