Pith. sign in

REVIEW 2 major objections 5 minor 15 references

Comparison-oracle variants of normalized GD and Polyak steps converge for convex (L0, L1)-smooth problems once the direction error is below explicit, problem-dependent thresholds.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · grok-4.5

2026-07-30 15:26 UTC pith:3747VX2D

load-bearing objection Clean first rates for NGD and Polyak under (L0,L1)-smoothness with only a comparison-oracle direction; solid proofs, incremental novelty, synthetic-only experiments. the 2 major comments →

arxiv 2607.26969 v1 pith:3747VX2D submitted 2026-07-29 math.OC

Normalized First-Order Methods for Convex (L0, L1)-Smooth Optimization with Inexact Gradients

Evgeniy Kovalev , Fedor Stonyakin This is my paper
classification math.OC MSC 90C2590C3065K05
keywords generalized smoothness(L0, L1)-smoothnessComparison Oraclenormalized gradient descentPolyak stepsizesinexact gradientsconvex optimization
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

Many modern machine-learning objectives are not classically smooth: their gradients grow with the gradient itself. This paper studies convex problems that satisfy the weaker (L0, L1)-smoothness condition and that can be queried only through a Comparison Oracle. That oracle returns a unit vector within absolute error δ of the true normalized gradient, using a linear number of function-value comparisons. The authors construct two first-order methods that use only these inexact directions—Normalized Gradient Descent with a fixed iteration budget and Gradient Descent with Polyak step-sizes (plus an adaptive Polyak variant that estimates a local gradient-norm bound on the fly). They prove explicit upper bounds on δ that still guarantee convergence, and they derive the corresponding rates. The results do not need classical Lipschitz gradients or exact gradient access. Synthetic experiments match the predicted dependence on L1, initialization, and oracle accuracy.

Core claim

For convex (L0, L1)-smooth objectives, Normalized Gradient Descent driven by a Comparison Oracle with step sizes βk = β̂/√(N+1) drives the best function value below any ε once N exceeds an explicit Q(ε) and the direction error δ stays below a concrete threshold of order O(√ε) that depends only on R0, L0 and L1. Parallel explicit δ-thresholds and rates hold for Polyak steps (and a strongly convex linear-rate regime), again without exact gradients.

What carries the argument

The Comparison Oracle (Assumption 3) together with the refined (L0, L1) estimates of Lemma 2: ∥∇f(y)−∇f(x)∥ ≤ (1/L1)((L0+L1∥∇f(x)∥)exp(L1∥y−x∥)−1) and the corresponding integral bound involving φ(t)=et−t−1. These replace classical smoothness and let the authors control the distance decrease when the update uses only an approximate unit direction.

Load-bearing premise

The oracle must return a unit vector whose absolute error δ from the true normalized gradient stays below explicit thresholds that shrink with the target accuracy, the distance to the optimum, and the smoothness parameters; if δ cannot be made that small, the guarantees do not apply.

What would settle it

On a known convex (L0, L1)-smooth test function, run the stated NGD or Polyak iteration with a Comparison Oracle whose error deliberately exceeds the δ-threshold of Theorem 1 or Lemma 4; if the best function value still drops below ε at the predicted N, the claimed necessity of those thresholds is false.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • Normalized first-order methods remain theoretically justified for (L0, L1)-smooth convex problems even when only approximate gradient directions are available.
  • The admissible oracle error need only be O(√ε), so coarser oracles can still be used for moderate accuracy.
  • An adaptive Polyak step that solves a local quadratic for the gradient-norm bound can replace a global M and often converges faster in practice.
  • The same comparison-oracle template can be attached to other normalized or Polyak-style schemes once matching δ-bounds are derived.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Because the Comparison Oracle costs only O(d log(d/δ)) function comparisons, the total work to reach ε scales as roughly that factor times the iteration complexity Q(ε), giving a concrete zeroth-order complexity for (L0, L1)-smooth convex minimization.
  • The same δ-threshold technique should extend immediately to clipped or momentum variants already analyzed under exact (L0, L1) gradients.
  • When f*=0 is known (over-parameterized models), the Polyak variant becomes a practical drop-in replacement for normalized SGD that never needs an exact gradient.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 5 minor

Summary. The paper studies unconstrained convex minimization of (L0,L1)-smooth objectives when the only first-order information is a Comparison Oracle that returns a unit vector within absolute error δ of the true normalized gradient. It proposes fixed-horizon Normalized Gradient Descent (Algorithm 1) with steps β_k=β̂/√(N+1) and Polyak-step Gradient Descent (Algorithm 2) that uses a uniform gradient-norm bound M, together with an unanalyzed adaptive-Polyak variant (Algorithm 3). Under convexity and the (L0,L1) assumption, Theorems 1–2 give explicit upper bounds on admissible δ (of order O(√ε) for NGD) that guarantee min_k f(x_k)−f*≤ε, together with corresponding iteration complexities; a partial linear-rate statement is obtained under strong convexity. The analysis rests on an improved integral remainder (Lemma 2) and standard distance-to-optimum expansions. Synthetic experiments on a separable quartic illustrate the predicted sensitivity to L1, δ and initialization.

Significance. The work supplies the first convergence guarantees for classical normalized and Polyak first-order methods under (L0,L1)-smoothness when only an inexact normalized direction is available. The explicit, non-asymptotic δ-thresholds and the sharpened remainder of Lemma 2 (which improves on twice-differentiable bounds in the literature) are concrete technical contributions. If the Comparison Oracle of Zhang & Li can be realized at the stated linear cost, the results enlarge the set of practical oracles for which generalized-smooth convex optimization is provably tractable. The adaptive Polyak heuristic, while unanalyzed, is shown empirically to be less conservative than the uniform-M version. Overall the paper is a solid, self-contained incremental advance rather than a conceptual breakthrough.

major comments (2)
  1. [Abstract, §4, Algorithm 3] Abstract and Introduction claim that convergence rates are derived “for all proposed methods.” Algorithm 3 (adaptive Polyak) is presented as a proposed method and is the strongest performer in Figures 1–2, yet Section 4 explicitly states that no convergence analysis is given. Either a proof (or a clear counter-example showing why the same δ-thresholds fail) should be supplied, or the abstract/claims should be restricted to Algorithms 1–2 and Algorithm 3 labelled a heuristic.
  2. [Theorem 1, Lemma 4, Remark 1] The admissible δ in Theorem 1 and Lemma 4/Eq. (6) depends on the unknown quantities R0=∥x0−x*∥, L0, L1 and (for Polyak) max_k(f(xk)−f*) or the a-priori bound M. While Remark 1 removes the trajectory-max dependence, the remaining constants are still unavailable to the user who must choose the oracle accuracy before the run. A short discussion of how these thresholds can be estimated or replaced by doubling schedules would make the guarantees operational rather than purely existential.
minor comments (5)
  1. [§5, §6.5] The synthetic test function F̂ is claimed (L0,L1)-smooth for every L0,L1>0; the short Hessian argument in §6.5 is correct but would be clearer if the precise statement of Proposition 2.4.2 of Vankov et al. were recalled.
  2. [§5, Fig. 1–2] Figures 1–2 lack axis labels for the vertical scale (function gap versus iteration) and do not report the dimension d or the precise realization of the Comparison Oracle; both affect reproducibility.
  3. [§4 title, §6.2–6.3] Typographical inconsistencies: “Polyak Stepizes” (section title), “inueqalities”, “guaranty”, and the repeated “Title Suppressed Due to Excessive Length” running head.
  4. [Lemma 5, Theorem 2] The constant ν satisfying νe^ν=1 is introduced without a numerical value; stating ν≈0.567 (the Omega-constant) would aid implementers.
  5. [§1] Related-work paragraph could briefly contrast the absolute-error unit-vector model (Assumption 3) with the relative-error or stochastic-gradient models already studied for (L0,L1)-smooth optimization.

Circularity Check

0 steps flagged

No significant circularity: rates follow deductively from stated convexity, (L0,L1)-smoothness, and oracle error assumptions

full rationale

The paper’s central claims (Theorems 1–2 and the supporting Lemmas 2 and 4) are standard first-order convergence arguments. They start from explicit external assumptions—convexity (Ass. 1), the (L0,L1) inequality (Ass. 2), and a unit-vector oracle with absolute error δ (Ass. 3)—and obtain admissible δ-thresholds and iteration complexities by elementary expansions of ||x_{k+1}−x*||², induction on the distance R_k, and the auxiliary inequalities of Lemmas 2–5. Lemma 2 is derived in §6.1 from Ass. 2 via Grönwall; Lemmas 3 and 5 are imported from Nesterov and from Gorbunov et al. (external citations), not from overlapping-author uniqueness theorems. L0, L1, R0 and M appear as problem parameters inside the stated bounds, not as quantities fitted to data and then re-presented as predictions. The synthetic experiments only corroborate the already-proved rates. There is therefore no self-definitional loop, no fitted-input-called-prediction, and no load-bearing self-citation chain that forces the claimed rates by construction.

Axiom & Free-Parameter Ledger

4 free parameters · 5 axioms · 0 invented entities

The central rates rest on three domain assumptions (convexity, (L0, L1)-smoothness, bounded-error unit direction from a comparison oracle) plus standard real-analysis tools (Grönwall, supporting-hyperplane lemma). No new physical entities. Free parameters are the usual tunable steps (β̂, c, M) and the oracle accuracy δ that must be set small enough; they are not fitted to external data but chosen to satisfy the proved inequalities.

free parameters (4)
  • β̂ (NGD step-scale) = 0.1 in experiments
    Tunable constant in β_k = β̂/√(N+1); theory requires β̂ < √3 R0 and suggests β̂ = R0/2. Chosen by user; experiments fix 0.1.
  • δ (oracle absolute error)
    Must lie below explicit problem-dependent thresholds involving R0, L0, L1, ε (and M, max suboptimality for Polyak). Not fitted to data; a design constraint on the oracle.
  • M (Polyak gradient-norm bound) = 10 L1 in experiments
    User-supplied upper bound on ||∇f|| along the trajectory; theory gives M_max ≤ (L0/L1)(exp(L1 R0)−1). Experiments set M = 10 L1.
  • c (gradient-norm threshold in Lemma 4)
    Free positive threshold used to split cases ||∇f|| ≷ c and to obtain δ conditions; must satisfy c ∈ (0, ε/R0).
axioms (5)
  • domain assumption f is convex (or μ-strongly convex) on R^d (Assumption 1).
    Used in every distance-to-optimum decrease and in the supporting-hyperplane argument (Lemma 3).
  • domain assumption f is (L0, L1)-smooth in the sense of Chen et al.: ||∇f(x)−∇f(y)|| ≤ (L0 + L1 sup_{z∈[x,y]} ||∇f(z)||) ||x−y|| (Assumption 2).
    Load-bearing generalized smoothness; Lemma 2 and all rates are derived from it.
  • domain assumption Oracle returns a unit vector g̃(x) with ||g̃(x) − ∇f(x)/||∇f(x)||| ≤ δ < 1 (Assumption 3 / Comparison Oracle of Zhang & Li).
    Defines the only first-order information the algorithms may use; δ-thresholds in Theorems 1–2 are meaningless without it.
  • standard math Grönwall inequality and standard convex supporting-hyperplane / distance lemmas (Lemmas 1, 3, 5 from prior work).
    Technical tools imported to bound gradient variation and convert direction error into function-value decrease.
  • domain assumption For Polyak methods, f* is known and a uniform bound M ≥ ||∇f(x_k)|| exists along the trajectory (or is replaced by the adaptive root Mk).
    Required to form the step length (f(x_k)−f*)/M; common in over-parameterized ML but restrictive in general.

pith-pipeline@v1.2.0-daily-grok45 · 17118 in / 3633 out tokens · 69498 ms · 2026-07-30T15:26:02.679845+00:00 · methodology

0 comments
read the original abstract

Generalized smoothness, such as (L0, L1)-smoothness, have recently attracted considerable attention due to their ability to model optimization problems arising in modern machine and deep learning, where the classical Lipschitz assumptions of the gradient is often violated. At the same time, computing exact gradients may be impractical or computationally expensive in many applications. In this work, we study convex (L0, L1)-smooth optimization under access only to a normalized approximation recently proposed Comparison Oracle, which returns an inexact normalized gradient in linear time with a bounded absolute error. Within this framework, we develop comparison-oracle variants of Normalized Gradient Descent and Gradient Descent with Polyak stepsizes. We establish explicit upper bounds on the approximation error that guarantee convergence and derive convergence rates for all proposed methods. Unlike existing analyses, our results require neither classical smoothness assumptions nor access to exact gradients or their exact normalized counterparts. Finally, numerical experiments corroborate the theoretical findings.

Figures

Figures reproduced from arXiv: 2607.26969 by Evgeniy Kovalev, Fedor Stonyakin.

Figure 1
Figure 1. Figure 1: Convergence behavior of NGD (top row) and the Polyak method (bottom row) on the synthetic (L0, L1)-smooth objective function Fˆ for different values of L1, ini￾tialization point x0, and approximation error δ [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Convergence behavior of Polyak and adaptive Polyak on the synthetic (L0, L1)- smooth objective function Fˆ for different values of L1 and approximation error δ [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

15 extracted references · 2 canonical work pages · 2 internal anchors

  1. [1]

    arXiv preprint arXiv:2303.02854 (2023),https://arxiv.org/abs/2303.02854

    Chen, Z., Zhou, Y., Liang, Y., Lu, Z.: Generalized-smooth nonconvex optimization is as efficient as smooth nonconvex optimization. arXiv preprint arXiv:2303.02854 (2023),https://arxiv.org/abs/2303.02854

    Pith/arXiv arXiv 2023

  2. [2]

    arXiv preprint arXiv:2403.02967 (2024),https: //arxiv.org/abs/2403.02967

    Gao, Y., Rodomanov, A., Stich, S.U.: Non-convex stochastic composite optimiza- tion with polyak momentum. arXiv preprint arXiv:2403.02967 (2024),https: //arxiv.org/abs/2403.02967

    Pith/arXiv arXiv 2024

  3. [3]

    arXiv preprint arXiv:2409.14989 (2024),https://arxiv.org/abs/ 2409.14989

    Gorbunov, E., Tupitsa, N., Choudhury, S., Aliev, A., Richtárik, P., Horváth, S., Takáč, M.: Methods for convex(l0, l1)-smooth optimization: Clipping, acceleration, and adaptivity. arXiv preprint arXiv:2409.14989 (2024),https://arxiv.org/abs/ 2409.14989

    Pith/arXiv arXiv 2024

  4. [4]

    arXiv preprint arXiv:1905.00313 (2019),https://arxiv.org/abs/1905.00313

    Hazan, E., Kakade, S.: Revisiting the polyak step size. arXiv preprint arXiv:1905.00313 (2019),https://arxiv.org/abs/1905.00313

    Pith/arXiv arXiv 1905

  5. [5]

    arXiv preprintarXiv:2305.01588(2023), https://doi.org/10.48550/arXiv.2305.01588

    Koloskova, A., Hendrikx, H., Stich, S.U.: Revisiting gradient clipping: Stochastic bias and tight convergence guarantees. arXiv preprintarXiv:2305.01588(2023), https://doi.org/10.48550/arXiv.2305.01588

    Pith/arXiv arXiv doi:10.48550/arxiv.2305.01588 2023

  6. [6]

    Proceedings of the 24th International Conference on Artificial Intelligence and Statistics (AISTATS) (2021),https://arxiv.org/abs/2002.10542

    Loizou, N., Vaswani, S., Laradji, I., Lacoste-Julien, S.: Stochastic polyak step- size for sgd: An adaptive learning rate for fast convergence. Proceedings of the 24th International Conference on Artificial Intelligence and Statistics (AISTATS) (2021),https://arxiv.org/abs/2002.10542

    Pith/arXiv arXiv 2021

  7. [7]

    Nesterov, Y.: Lectures on Convex Optimization, Springer Optimization and Its Applications, vol. 137. Springer, 2 edn. (2018).https://doi.org/10.1007/ 978-3-319-91578-4

    2018

  8. [8]

    Takezawa, Y., Bao, H., Sato, R., Niwa, K., Yamada, M.: Parameter-free clipped gradientdescentmeetspolyak.AdvancesinNeuralInformationProcessingSystems (NeurIPS) (2024),https://arxiv.org/abs/2405.15010

    Pith/arXiv arXiv 2024

  9. [9]

    arXiv preprint arXiv:2410.10800 (2024), https://arxiv.org/abs/2410.10800

    Vankov,D.,Rodomanov,A.,Nedich,A.,Sankar,L.,Stich,S.U.:Optimizing(l 0, l1)- smooth functions by gradient methods. arXiv preprint arXiv:2410.10800 (2024), https://arxiv.org/abs/2410.10800

    Pith/arXiv arXiv 2024

  10. [10]

    (eds.) Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics

    Vaswani, S., Bach, F., Schmidt, M.: Fast and faster convergence of sgd for over- parameterizedmodelsandanacceleratedperceptron.In:Chaudhuri,K.,Sugiyama, M. (eds.) Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics. Proceedings of Machine Learning Research, vol. 89, pp. 1195–1204. PMLR (16–18 Apr 2019),https...

    2019

  11. [11]

    Frank-Wolfe Algorithms for (L0, L1)-smooth functions

    Vyguzov, A., Stonyakin, F.: Frank-wolfe algorithms for (l0, l1)-smooth functions. arXiv preprintarXiv:2510.16468(2025),https://doi.org/10.48550/arXiv. 2510.16468

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.2510.16468 2025

  12. [12]

    Improved Analysis of Clipping Algorithms for Non-convex Optimization

    Zhang, B., Jin, J., Fang, C., Wang, L.: Improved analysis of clipping algorithms for non-convex optimization. In: Advances in Neural Information Processing Systems (NeurIPS). vol. 33, pp. 15511–15521 (2020),https://doi.org/10.48550/arXiv. 2010.02519

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.2010.02519 2020

  13. [13]

    Zhang, C., Li, T.: Comparisons are all you need for optimizing smooth functions (2024),https://arxiv.org/abs/2405.11454

    Pith/arXiv arXiv 2024

  14. [14]

    Zhang, J., He, T., Sra, S., Jadbabaie, A.: Why gradient clipping accelerates train- ing: A theoretical justification for adaptivity. arXiv preprint arXiv:1905.11881 (2020) Title Suppressed Due to Excessive Length 11 6 Missing proofs 6.1 Proof of Lemma 2 The following derivation adheres to the framework established in [1], extending their results to derive...

    Pith/arXiv arXiv 1905

  15. [15]

    Sincea >0andb >0, the parabola opens upward with its vertex in the negative half-plane (− b 2a <0)

    We define the corresponding condition as a quadratic function inδ: E(δ) = ˆβ2 |{z} a δ2 + (2ˆβ2 + 4R0 √ N+ 1 ˆβ)| {z } b δ+ ˆβ2 −3R 2 0| {z } c . Sincea >0andb >0, the parabola opens upward with its vertex in the negative half-plane (− b 2a <0). ProvidedE(0) =c <0(i.e., ˆβ2 <3R 2 0),E(δ)≤0holds for allδup to the positive rootδ +.By boundingδ + from below,...