math.OCNov 15, 2026

Near-Optimal Methods for Generalized Lipschitz Convex Optimization

Authors: Dmitry Kovalev, Grigory Malinovsky

Organizations: Yandex Research · King Abdullah University of Science and Technology

Abstract

In this paper, we consider a convex optimization problem, where the upper bound on the subgradient norm depends on the objective function. We establish a lower bound on the number of iterations required by any first-order method to find an approximate solution to the problem. Furthermore, we present two near-optimal algorithms that can match the lower bound up to logarithmic factors. The first algorithm is a projected GD with a carefully designed stepsize schedule which incorporates warm-up and decay phases. The second algorithm is scalar-stepsize clipped AdamW which extends the near-optimal guarantees to the stochastic setting, where only a noisy unbiased estimator of the subgradient is available.

Figures & tables

Explore similar work

May 15, 2026

Stochastic Non-Smooth Convex Optimization with Unbounded Gradients

Much of the existing theory on first-order non-smooth optimization is built on a restrictive assumption that the gradients of the objective function are uniformly bounded. We introduce a much more realistic class of generalized Lipschitz functions, where the gradient norms are bounded by an affine function of the optimality gap. We then ask a natural question: what algorithm achieves the best global convergence rates for solving convex stochastic generalized Lipschitz optimization problems? To address this, we develop a new convergence analysis for several existing algorithms and find that AdamW with clipped updates, provably outperforms other popular stochastic optimization methods, such as SGD and AdaGrad. Moreover, our analysis establishes the critical role of AdamW's exponentially weighted gradient accumulation, as opposed to simple averaging. We further show that clipped AdamW is universal and achieves improved rates under the popular generalized smoothness assumption, analyze the convergence of clipped AdamW with diagonal and matrix preconditioners, and extend our results to the quasar-convex setting.
Jun 23, 2026

New Bounds for the Last Iterate of the Stochastic subGradient Method

We study the last iterate of the stochastic subgradient method for one-dimensional convex Lipschitz objectives. For a fixed horizon nn, we consider the standard fixed stepsizes η=Θ(1/n)η=Θ(1/\sqrt n). We prove that, for such stepsize policies, under additive i.i.d. subgradient noise with uniformly bounded variance, the last iterate features an optimization error of order 1/n1/\sqrt n, thereby removing the extra (log⁡n)(\log n) factor present in existing generic bounds. On the other hand, we show that without the i.i.d. assumption, the optimization error can be of order (log⁡n)/n(\log n)/\sqrt n. Thus, under the uniformly bounded variance assumption alone, the last iterate of SsGM is suboptimal even in dimension one, resolving negatively an open problem posed in Koren and Segal, COLT, 2020.
Sep 26, 2026

Revisiting AdaGrad in Stochastic Convex Optimization: Last Iterates, High Probability, and Lower Bounds

AdaGrad and AdaGrad-Norm are widely used adaptive methods, but their precise behavior in stochastic convex optimization remains less understood. We first show that AdaGrad-Norm and AdaGrad do not admit any universal last-iterate rate, even under sub-Gaussian noise and bounded iterates. We then prove that bounded variance alone is too weak: even with bounded iterates, it cannot yield high-probability average-iterate rates, and without bounded iterates it may not even guarantee convergence in expectation. Besides, we construct tight Ω(log⁡T/T)Ω(\log T/\sqrt T) lower bounds for both AdaGrad-Norm and AdaGrad under sub-Gaussian noise, showing that log⁡T\log T in existing average-iterate upper bounds is unavoidable. Finally, we show that this log⁡T\log T loss disappears once bounded-iterate condition is imposed: under a general ABC condition, both methods achieve rates O(1/T){O}(1/\sqrt{T}).