New Perspectives on the Polyak Stepsize: Surrogate Functions and Negative Results

Francesco Orabona, Ryan D’Orazio · 2025

Read New Perspectives on the Polyak Stepsize: Surrogate Functions and Negative Results by Francesco Orabona, Ryan D’Orazio (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-20219.txt.

Introduction

Francesco Orabona and Ryan D'Orazio reframe the Polyak stepsize, a classic rule in optimization, as gradient descent on a stand-in loss, in a paper from 2025. The Polyak rule sets each step from the gap to the known best value, and it is near optimal across many settings. Stochastic versions abound, but their analyses are scattered and their failures murky.

The surrogate view unifies them: each variant secretly minimizes its own surrogate function, with steps that adapt to guaranteed local curvature. One analysis then covers many variants at once. The paper also proves negative results, showing that some non-convergence in earlier upper bounds is real, not a proof artifact. The authors offer the frame as a map of what the rule can and cannot do.

Catalog record

CREATORFrancesco Orabona, Ryan D’Orazio
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE96 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-20219

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

New Perspectives on the Polyak Stepsize: Surrogate Functions and Negative Results Francesco Orabona, Ryan D’Orazio Abstract The Polyak stepsize has been proven to be a fundamental stepsize in convex optimization, giving near optimal gradient descent rates across a wide range of assumptions. The universality of the Polyak stepsize has also inspired many stochastic variants, with theoretical guarantees and strong empirical performance. Despite the many theoretical results, our understanding of the convergence properties and shortcomings of the Polyak stepsize or its variants is both incomplete and fractured across different analyses. We propose a new, unified, and simple perspective for the Polyak stepsize and its variants as gradient descent on a surrogate loss. We show that each variant is equivalent to minimize a surrogate function with stepsizes that adapt to a guaranteed local curvature . Our general surrogate loss perspective is then used to provide a unified analysis of existing variants across different assumptions. Moreover, we show a number of negative results proving that the non-convergence results in some of the upper bounds is indeed real. 1 Introduction The iterative optimization of complex functions forms a cornerstone of modern machine learning, scientific computing, and engineering. Among the most foundational first-order methods is gradient descent, which iteratively refines a solution by moving in the direction opposite to the function’s gradient. A critical aspect of gradient descent is the selection of an appropriate stepsize (or learning rate), as it dictates both the speed of convergence and the stability of the algorithm. The wrong choice of the stepsizes can lead to slow convergence or, conversely, to divergence, making the tuning process a significant practical hurdle. In this landscape of stepsize selection strategies, the Polyak stepsize, proposed by Polyak [36] stands out for its theoretical elegance and convergence properties. Starting from an arbitrary \boldsymbol{x}_{1}\in\mathbb{R}^{d} , the Polyak stepsize is defined as \boldsymbol{x}_{t+1}=\boldsymbol{x}_{t}-\frac{f(\boldsymbol{x}_{t})-f^{\star}}{\|\boldsymbol{g}_{t}\|^{2}}\boldsymbol{g}_{t}, (1) where \boldsymbol{0}\neq\boldsymbol{g}_{t}\in\partial f(\boldsymbol{x}_{t}) and f^{\star}=\min_{\boldsymbol{x}}f(\boldsymbol{x}) . If \boldsymbol{g}_{t}=\boldsymbol{0} , then \boldsymbol{x}_{t+1}=\boldsymbol{x}_{t} . This update rule can achieve linear convergence for strongly convex and smooth functions, \mathcal{O}(1/T) rate for convex smooth functions, and \mathcal{O}(1/\sqrt{T}) rate for non-smooth convex ones. This is particularly interesting because all of these rates are achieved with a unique stepsize and without knowledge of smoothness or curvature constants. In other words, this update rule is adaptive to the geometry of the functions to optimize. Recently, the Polyak stepsize has seen a resurgence in the machine learning literature, with a plethora of variants. However, despite the big number of papers on this topic, one essential research question seems still to be missing: What makes the Polyak stepsize adaptive and when can it fail? Contributions. This paper aims to provide a novel framework to understand the Polyak stepsize, providing a clear geometric explanation of its adaptivity. In particular, we show that the adaptivity is due to a simple but powerful observation: The Polyak stepsize minimizes a surrogate objective function that is always locally smooth. As for standard smooth functions, we will show that the knowledge of the local smoothness constant is enough to obtain the correct rates. In addition, the local smoothness will depend only on the gradient itself, removing the need to estimate it. Furthermore, we show that minimal curvature of the surrogate is inherited from the original function as well. We also use this framework to extend its core idea to a family of algorithms. Then, we will show a number of negative results when f(\boldsymbol{x}^{\star}) is not known and for its use in the stochastic case. These negative results complete our understanding by showing that some non-vanishing terms in existing upper bounds are necessary. 2 Related Work In the pionnering work of Ermol’ev [14] stepsizes of the form \eta_{t}\propto\nicefrac{{1}}{{\|\boldsymbol{g}_{t}\|^{2}}} were proposed for non-smooth optimization. Despite the many convergence guarantees enabled by Ermol’ev [14] ’s framework, in Polyak [36] it is noted that linear convergence is not possible with such stepsizes. As an alternative, Polyak suggests the stepsize ( 1 ), which is shown to converge at favourable rates with non-smooth convex functions, and strongly convex and smooth functions. In fact, contrary to common belief, Polyak [36] was the first to show linear convergence with a rate comparable to gradient descent in the smooth and strongly convex case. Furthermore, the case where f^{\star} is estimated was also studied, showing convergence to a level set if f^{\star} is overestimated, and best-iterate convergence to a neighboorhood if it is underestimated. The Polyak stepsize has since been extended and studied across several applications and domains. Non-smooth convex. In non-smooth convex optimization, several schemes have been developed to estimate f^{\star} on the fly [ 7 , 6 , 16 , 41 , 31 , 27 ] . In the finite-sum case with interpolation, ( 1 ) and variants have been studied as an incremental subgradient method [ 31 , 27 ] . Non-expansive operators. In the context of non-expansive operators, the update ( 1 ) has also been studied as a special case of the subgradient projector [ 2 , 8 , 10 ] ; where it can be shown that subgradient descent with \eta_{t}=\nicefrac{{(f(x)-c)_{+}}}{{\|\boldsymbol{g}_{t}\|^{2}}} is a quasi-firmly non-expansive operator 1 1 1 An operator T is quasi-firmly non-expansive if for all fixed points \boldsymbol{x}^{\star} , \|T(\boldsymbol{x})-\boldsymbol{x}^{\star}\|^{2}\leq\|\boldsymbol{x}-\boldsymbol{x}^{\star}\|^{2}-\|T(\boldsymbol{x})-\boldsymbol{x}\|^{2} . Note that a quasi-firmly non-expansive operators are also referred to as cutters . if f is convex and c\geq f^{\star} , and \boldsymbol{x}\to\boldsymbol{x}^{\star} if f is continuous [ 2 ] . Moreover, in the finite-sum setting, interpolation can also be viewed as iterating different quasi-firmly non-expansive operators with a common fixed point. For example, applying a subgradient projector sequentially (i.e., cycling through the different component functions) in a way such that each function eventually gets visited guarantees that \boldsymbol{x}_{t}\to\{f(\boldsymbol{y})\leq c\} [ 8 , Example 5.9.7] . For a survey on this topic see Censor [9] . Deterministic. In modern optimization, ( 1 ) has been shown to achieve similar rates to gradient descent in various common assumptions (e.g., Lipschitz, smoothness and strong convexity) [ 22 ] , and more recently with other assumptions such as weakly convex functions [ 12 ] , (L_{0},L_{1}) -smooth functions [ 42 , 17 ] , and directional smoothness [ 30 ] . Stochastic. The Polyak stepsize has also been extended to the stochastic case with emphasis on applications to machine learning [ 39 , 5 , 29 , 38 ] . The ALI-G method [ 5 ] and SPS max [ 29 ] use stochastic estimates via the sampled function f(\boldsymbol{x},\boldsymbol{\xi}) and its gradient \nabla f(\boldsymbol{x},\boldsymbol{\xi}) to perform a Polyak-like stepsize. SPS max in addition uses \inf_{x}f(x,\boldsymbol{\xi}) as an estimate to f^{\star} , and is shown to converge at fast rates without a neighbourhood under interpolation. Folowing SPS max many variants have been proposed for SGD: StoPS [ 24 ] , DECSPS and SPS {}_{\max}^{\ell} [ 35 ] , \texttt{SPS}_{+} [ 15 ] . Beyond SGD, other extensions include: mirror descent [ 13 ] , with preconditioning [ 1 ] , with line-search [ 25 ] , and with momentum [ 43 , 40 , 33 ] . Neighbourhood of Convergence. For SPS max , Loizou et al. [29] proved that the suboptimality gap is only guaranteed to shrink up to a factor that depends on the loss themselves. As

Read the complete text