Pith. sign in

REVIEW 1 major objections 4 minor 15 references

For the last iterate of the subgradient method, the dimension cost is linear, not logarithmic.

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

2026-08-01 21:43 UTC pith:V6YDHJHN

load-bearing objection Sharp last-iterate subgradient bounds: linear in dimension is real, and the min{d, log n} transition is likely right, but the log n half rests on an external theorem via a limit you should check. the 1 major comments →

arxiv 2607.15980 v2 pith:V6YDHJHN submitted 2026-07-17 math.OC

Sharp Dimension Dependence for the Last Iterate of the SubGradient Method

Guglielmo Beretta , Tommaso Cesari , Roberto Colomboni , Andrea Paudice This is my paper
classification math.OC MSC 90C2590C3068Q25
keywords last iteratesubgradient methodconvex optimizationdimension dependenceLipschitz functionsconstant stepsizelower boundnonsmooth 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.

This paper settles how the dimension d enters the worst-case error of the last point produced by the projected subgradient method on convex Lipschitz problems with a constant step size. It proves that in any fixed dimension d the final iterate has error at most ((2d+1)/2) ηL² plus the usual initialization term, so with η=Θ(1/√n) the error is Θ(d/√n) and the logarithmic factor seen in high-dimensional analyses is unnecessary. It also constructs convex Lipschitz examples showing this linear-in-d cost cannot be avoided, and it identifies the exact joint dependence across dimension and horizon as Θ(min{d, log(n+1)}) for the normalized terminal excursion. With the standard stepsize choice this becomes Θ(min{d, log n})/√n, resolving a long-standing open question about whether the true dimension dependence is logarithmic or linear: it is linear.

Core claim

The paper establishes a sharp dimension-dependent bound for the last iterate of projected subgradient descent on convex L-Lipschitz functions: for every dimension d, horizon n, constant step η>0, initialization, and admissible subgradient selection, f(x_n)-f⋆ ≤ ((2d+1)/2) ηL² + dist(x_1,X⋆)²/(2nη). It proves by explicit construction that the linear-in-d coefficient is unavoidable: for every k≥1 and d≥2k+1 there exists a convex globally Lipschitz function, initialized at a minimizer, admitting a valid constant-step trajectory whose terminal gap is exactly (k/4)ηL². Combining this lower bound with a dimension-free logarithmic upper bound gives the exact worst-case normalized terminal excursion

What carries the argument

The proof uses two complementary mechanisms. For the upper bound, after normalizing the problem to a 1-Lipschitz convex function, the paper defines last-exit times from consecutive unit-spaced objective levels. The displacement vectors from these last-exit points to the terminal iterate have strictly negative pairwise inner products whenever their level indices differ by at least two, while a terminal subgradient forces all of them into a common open halfspace; a linear-independence rank argument then caps each parity class at d, bounding the terminal gap above the trajectory minimum by 2d. For the lower bound, a support-function realization lemma turns any prefix-minimizing sequence—where e

Load-bearing premise

The logarithmic branch of the claimed sharp transition assumes that the cited dimension-free error estimate remains valid for trajectories that start exactly at a minimizer and that its slack term vanishes as an auxiliary radius is taken to zero.

What would settle it

Run the paper's k=1, d=3 construction: realize the prescribed Gram vectors, simulate 40,000 repetitions of the pair (u1, v1) followed by the terminal witness z, and check that every selected action indeed has the minimum linear score against the cumulative past actions and that the terminal score equals exactly -1/4. Any defeated step or any terminal score different from -1/4 would falsify the lower-bound theorem.

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

Share X Bluesky LinkedIn Reddit HN

If this is right

  • For every fixed dimension d, the constant-step projected subgradient method achieves O(d/√n) last-iterate error; the logarithmic horizon factor is unnecessary.
  • The uniform all-horizon dimension coefficient A⋆_d is Θ(d), so the deterministic worst-case dimension dependence is linear, not logarithmic.
  • The sharp joint dependence is Θ(min{d, log(n+1)})/√n; the crossover occurs when d is comparable to log n.
  • With the optimized constant stepsize η = D/(L√(4d+1)n), the bound becomes √(4d+1) LD/√n, giving explicit tuning guidance.
  • The lower bound starts exactly at a minimizer, so the linear-in-d term multiplying ηL² is unavoidable even in the unconstrained case and for any admissible subgradient choice.

Where Pith is reading between the lines

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

  • Editorial inference: because the lower-bound construction has horizon exponential in k (n_k ≤ 1000^{k+1}), the linear-in-d behavior becomes visible only for n of order exp(d); in most practical data ranges the log n branch may dominate, which may explain why logarithmic dependence was previously detected.
  • Editorial inference: the prefix-minimizing support-function device is not inherently deterministic; a stochastic oracle capable of realizing the same action sequence could plausibly yield a linear-in-d last-iterate lower bound for SGD in fixed dimension, challenging the earlier conjectured log d behavior in the stochastic setting.
  • Editorial inference: the last-exit/parity geometry underlying the upper bound appears transferable to other projection-based first-order methods, suggesting that dimension-proportional constants are a general phenomenon whenever a terminal subgradient confines all late displacement vectors to one open halfspace.

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

1 major / 4 minor

Summary. The paper studies the last iterate of the projected subgradient method (1) for convex L-Lipschitz objectives on R^d with constant step size η. Its main results are: Theorem 2, a dimension-dependent upper bound f(x_n)-f* ≤ ((2d+1)/2) ηL^2 + dist(x_1,X*)^2/(2nη) that holds for every admissible subgradient selection; Theorem 3, a lower-bound construction in dimensions d ≥ 2k+1 producing a valid trajectory from a minimizer with terminal gap (k/4)ηL^2 after a horizon exponential in k; and Corollary 4, which combines these with a cited dimension-free last-iterate bound of Zamani and Glineur to obtain Γ_{d,n} = Θ(min{d, log(n+1)}), equivalently Θ(min{d, log n}/√n) for η = Θ(1/√n). The upper-bound proof uses a last-exit/obtuse-vector dimension count; the lower bound uses a prefix-minimizing sequence realized by a multiscale positive-definite Gram matrix. The paper claims to resolve the COLT open problem of Koren and Segal.

Significance. If the results hold, the paper closes a significant open problem: it shows that in fixed dimension the last iterate of sGM with constant step size has O(d/√n) error, removing the log n factor, and that the dimension dependence is linear, not logarithmic. The upper bound is elementary, self-contained, and parameter-free; the lower-bound construction is explicit, with no fitted data, and gives a matching linear-in-d coefficient. The sharp min{d, log n} transition is conceptually clean and explains the earlier discrepancy between high-dimensional logarithmic lower bounds and fixed-dimension heuristics. The main caveat is that the log n half of the upper bound is supplied by an external theorem that is not reproduced in the manuscript; the paper's own Theorems 2 and 3 are internally consistent and I found no error in their proofs. If the external estimate is stated and the R↓0 limit is verified, this will be a strong contribution.

major comments (1)
  1. [Corollary 4, Eq. (6), proof] The dimension-free upper bound 1 + 1/4 log(n−1) is load-bearing but is imported without a statement. The proof says that because dist(x1,X*)=0, the trajectory is within every auxiliary radius R>0, applies [15, Thm 3.4] with h=ηL/R, obtains an O(R^2) remainder, and lets R↓0. For this to prove the upper side, the cited estimate must (a) apply uniformly for all sufficiently small R, including trajectories starting at a minimizer; (b) hold in the large-step regime h→∞; and (c) have remainders that vanish as R→0. None of these can be checked from the manuscript because [15, Thm 3.4] is not restated. If the external result behaves differently, the upper bound in (6) is only O(d), leaving a gap versus the Ω(log n) lower bound for d≫log n. Please include the precise statement of the Zamani–Glineur theorem, verify the limit, and reconcile the application to 'n−1 updates' with the log(n−1) term.
minor comments (4)
  1. [Theorem 3 and §4.3] The displayed horizon is n_k ≤ 1000 k+1, but the calculation (54) and Theorem 13 give n_k ≤ 1000^{k+1}. This is presumably a typesetting loss of the exponent; please correct both the statement and the proof display so the exponential horizon is unambiguous.
  2. [§4.4] When embedding into R^d with d > 2k+1, the text says 'zero padding' but does not define the extended function. The standard extension F∘P, where P is orthogonal projection, is convex and 1-Lipschitz; adding this sentence would remove ambiguity.
  3. [Corollary 4 proof] The final comparison to c0 min{d, log(n+1)} and C0 min{d, log(n+1)} is asserted after 'elementary comparison'. Since the floor/step regimes and the base-1000 logarithm hide numerical factors, please spell out the constants or give a short calculation for the transition values; this is not a correctness issue but improves verifiability.
  4. [Title and abstract] The word 'sharp' is used for order-level sharpness while the exact constant in A⋆_d is open. The conclusions already qualify this; consider making the 'up to universal constants' qualification appear earlier so the claim is not over-read.

Circularity Check

0 steps flagged

No circularity found: the main upper and lower bounds are self-contained proofs, and the cited Zamani-Glineur bound is used as an independent external benchmark, not as an assumed version of the target result.

full rationale

The paper's central claims do not reduce to their inputs. Theorem 2 is proved directly from the projection comparator, an exact normalization, last-exit times, and an elementary dimension-counting argument (Section 3); Theorem 3 is built from an explicit positive-definite Gram matrix and a verified prefix-minimizing sequence (Section 4). Neither proof assumes the target bound or fits parameters to the claimed conclusion. Corollary 4 combines the paper's own d-linear upper bound and k-linear lower construction with the independent dimension-free estimate of Zamani and Glineur [15]; this is a legitimate use of an external theorem, not a self-citation or an ansatz smuggled via citation. The auxiliary-radius argument for the log n regime is a technical step whose uniformity would need checking against [15], but potential concerns about that limit are correctness risks, not circularity: the cited result is not defined in terms of the present paper's claims. Overall the derivation is self-contained apart from a clearly identified external benchmark, so no circular step is present.

Axiom & Free-Parameter Ledger

2 free parameters · 4 axioms · 0 invented entities

No parameters are fitted to data. Q=100 and δ=1/4 are hand-picked universal constants for the lower-bound Gram construction; they are not tuned to any numerical instance and only affect universal constants. The upper bound is parameter-free. The support-function and Gram designs are mathematical constructions, not invented physical entities.

free parameters (2)
  • Q (stage scale ratio) = 100
    Chosen by hand in (27). It guarantees the scale-separation inequalities (γ>1/2, ε_i<1/400) in the lower-bound construction; it affects only universal constants.
  • δ (per-stage terminal contribution) = 1/4
    Chosen by hand in (27). Every completed stage contributes δ to the terminal score via N_i ε_i = δ; γ = 3δ − 2δ/(Q−1) > 1/2 depends on it.
axioms (4)
  • standard math Finite-valued convex functions on R^d are continuous, have nonempty subgradients, and Euclidean projection is non-expansive.
    Used in Lemmas 6-7 and Propositions 15-16; standard finite-dimensional convex analysis.
  • standard math Positive semidefinite matrices are Gram matrices; Gershgorin's theorem bounds spectra.
    Used in Lemma 14 to convert the prescribed inner-product table into actual Euclidean vectors.
  • domain assumption The problem class: f convex and L-Lipschitz on R^d, X nonempty closed convex, X* nonempty, arbitrary subgradient selections allowed.
    Assumptions 1-2 plus Definition 1 define the adversarial black-box model in which the bounds are stated.
  • domain assumption Zamani-Glineur dimension-free last-iterate estimate for constant-step projected subgradient method (Ref. [15], Thm 3.4).
    Used only in Corollary 4 to obtain the 1 + (1/4) log(n−1) upper side of the min{d, log n} bound; not re-derived in this paper.

reviewed 2026-08-01 · how reviews work

0 comments
Cite this review

Pith. "Pith review of Sharp Dimension Dependence for the Last Iterate of the SubGradient Method." pith.science (2026). https://pith.science/paper/V6YDHJHN

@misc{pith2026260715980,
  author       = {Pith},
  title        = {Pith review of: Sharp Dimension Dependence for the Last Iterate of the SubGradient Method},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/V6YDHJHN}},
  note         = {Machine review of arXiv:2607.15980}
}
Share X Bluesky LinkedIn Reddit HN
read the original abstract

We study the last iterate of the projected subGradient Method (sGM) for convex Lipschitz objectives defined on $\mathbb{R}^d$. We prove that, for a finite horizon $n$ and a constant stepsize $\eta=\Theta(1/\sqrt n)$, the last iterate achieves an optimization error of order $d/\sqrt n$, showing that the extra $\log n$ factor appearing in high dimensions is unnecessary in every fixed dimension. We complement this result with a matching linear-in-$d$ lower bound and show that the sharp worst-case dimension-horizon dependence is of order $\min\{d,\log n\}/\sqrt n$. This solves, in particular, a COLT open problem posed by Koren and Segal in 2020 and shows that the correct dependence on the dimension is linear rather than logarithmic.

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 · 1 linked inside Pith

  1. [1]

    MIT Press, 2024

    Francis Bach.Learning Theory from First Principles. MIT Press, 2024

    2024

  2. [2]

    Nicholas J. A. Harvey, Christopher Liaw, Yaniv Plan, and Sikander Randhawa. Tight analyses for non-smooth stochastic gradient descent. InProceedings of the 32nd Conference on Learning Theory, volume 99 ofProceedings of Machine Learning Research, pages 1579–1613, 2019

    2019

  3. [3]

    Nicholas J. A. Harvey, Christopher Liaw, and Sikander Randhawa. Tight analyses for subgradi- ent descent i: Lower bounds.Open Journal of Mathematical Optimization, 5:1–17, 2024

    2024

  4. [4]

    Nagaraj, and Praneeth Netrapalli

    Prateek Jain, Dheeraj M. Nagaraj, and Praneeth Netrapalli. Making the last iterate of SGD information theoretically optimal.SIAM Journal on Optimization, 31(2):1108–1130, 2021

    2021

  5. [5]

    Openproblem: TightconvergenceofSGDinconstantdimension

    TomerKorenandShaharSegal. Openproblem: TightconvergenceofSGDinconstantdimension. InProceedings of the 33rd Conference on Learning Theory, volume 125 ofProceedings of Machine Learning Research, pages 3847–3851, 2020

    2020

  6. [6]

    Modified Fejér sequences and applications.Computational Optimization and Applications, 71(1):95–113, 2018

    Junhong Lin, Lorenzo Rosasco, Silvia Villa, and Ding-Xuan Zhou. Modified Fejér sequences and applications.Computational Optimization and Applications, 71(1):95–113, 2018

    2018

  7. [7]

    The convergence rate of SGD’s final iterate: Analysis on dimension dependence, 2021

    Daogao Liu and Zhou Lu. The convergence rate of SGD’s final iterate: Analysis on dimension dependence, 2021. arXiv:2106.14588

    Pith/arXiv arXiv 2021

  8. [8]

    Revisiting the last-iterate convergence of stochastic gradient methods

    Zijian Liu and Zhengyuan Zhou. Revisiting the last-iterate convergence of stochastic gradient methods. InProceedings of the 12th International Conference on Learning Representations, 2024

    2024

  9. [9]

    Nemirovsky and David B

    Arkadii S. Nemirovsky and David B. Yudin.Problem Complexity and Method Efficiency in Optimization. Wiley, 1983

    1983

  10. [10]

    Boris T. Polyak. Minimization of unsmooth functionals.USSR Computational Mathematics and Mathematical Physics, 9(3):14–29, 1969

    1969

  11. [11]

    Princeton University Press, 1970

    Ralph Tyrrell Rockafellar.Convex Analysis. Princeton University Press, 1970

    1970

  12. [12]

    Stochastic gradient descent for non-smooth optimization: Convergence results and optimal averaging schemes

    Ohad Shamir and Tong Zhang. Stochastic gradient descent for non-smooth optimization: Convergence results and optimal averaging schemes. InProceedings of the 30th International Conference on Machine Learning, volume 28 ofProceedings of Machine Learning Research, pages 71–79, 2013

    2013

  13. [13]

    Naum Z. Shor. An application of the method of gradient descent to the solution of the network transportation problem. InMaterialy Nauchnogo Seminara po Teoreticheskim i Prikladnym Voprosam Kibernetiki i Issledovaniia Operatsii, volume 1, pages 9–17. Nauchnyi Sovet po Kibernetike Akademii Nauk Ukrainskoi SSR, Kiev, 1962. In Russian

    1962

  14. [14]

    Naum Z. Shor. The rate of convergence of the generalized gradient descent method.Cybernetics, 4(3):79–80, 1968

    1968

  15. [15]

    Exact convergence rate of the last iterate in subgradient methods.SIAM Journal on Optimization, 35(3):2182–2201, 2025

    Moslem Zamani and François Glineur. Exact convergence rate of the last iterate in subgradient methods.SIAM Journal on Optimization, 35(3):2182–2201, 2025. 21 A Some Standard Facts from Convex Analysis This appendix collects standard facts from convex analysis used in the paper; see, e.g., [11]. Proofs are included for completeness. Proof of Lemma 6.Since ...

    2025

This paper was first reviewed by deepseek-v4-flash on August 1, 2026.