Sharp Dimension Dependence for the Last Iterate of the SubGradient Method

2026/07/17 by Guglielmo Beretta, Tommaso Cesari, Roberto Colomboni +1
#math.OC

paper · pdf

Abstract

We study the last iterate of the projected subGradient Method (sGM) for convex Lipschitz objectives defined on ℝ^d. We prove that, for a finite horizon n and a constant stepsize η=Θ(1/√ n), the last iterate achieves an optimization error of order d/√ 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\/√ 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.

Related

• The Convergence Rate of SGD's Final Iterate: Analysis on Dimension Dependence
• Optimal Subgradient Methods for Lipschitz Convex Optimization with Error Bounds
• Lipschitz minimization and the Goldstein modulus
• A gradient sampling method with complexity guarantees for Lipschitz functions in high and low dimensions
• Exact convergence rate of the last iterate in subgradient methods