Polyak Step Size: Why Does It Work So Well Across All Function Types?

The Polyak step is a learning-rate rule for gradient descent that dates back to 1969. Instead of a fixed step, it adapts based on the gap between the current function value and an estimated optimum. Recent work shows this simple idea is remarkably powerful.

The authors built worst‑case functions to prove that the known convergence rates are tight: for smooth strongly convex functions the error shrinks by a factor \(1-1/\kappa\) each iteration, and for smooth convex functions the rate is \(1/K\). No general improvement is possible.

A surprise emerges: floating‑point rounding errors, usually a nuisance, are actually used by the Polyak step to escape these worst‑case scenarios. In practice, numerical noise helps the algorithm find faster routes.

The study also extends the theory to Hölder smoothness and growth conditions, meaning the step adapts not only to smooth or strongly convex landscapes but also to milder curvature without knowing parameters like the condition number. In short, the Polyak step is universal: it self‑adjusts, guaranteeing rapid convergence across a wide range of optimization problems.

The Polyak step, formally defined as \(\alpha_k = \frac{f(x_k)-f^*}{\|\nabla f(x_k)\|^2}\), requires an estimate of the optimal value \(f^*\). In practice one uses a lower bound or an iterative estimate. The tightness proof starts by constructing quadratic functions with Hessian matrix \(Q\) having eigenvalues \(\lambda_{\min}=\mu\) and \(\lambda_{\max}=L\), where \(\kappa=L/\mu\). It is shown that for such functions the iterate \(x_{k+1}=x_k-\alpha_k\nabla f(x_k)\) yields exactly the contraction factor \(1-1/\kappa\). For smooth convex cases, a family \(f_t(x)=\frac{1}{t}\|x\|^t\) with \(t\in(1,2]\) is used to prove the \(O(1/K)\) lower bound.

Floating‑point error analysis relies on the IEEE‑754 model: \(fl(a\cdot b)=a\cdot b(1+\delta)\) with \(|\delta|\le\epsilon_{mach}\). Inserting these terms into the Polyak recursion yields a noise term that, on average, adds a positive component to the function decrease, breaking the worst‑case sequence.

Hölder conditions introduce exponents \(\nu\in(0,1]\) for smoothness (\(\|\nabla f(x)-\nabla f(y)\|\le L\|x-y\|^{\nu}\)) and \(\theta\in(0,1]\) for growth (\(f(x)-f^*\ge c\|x-x^*\|^{\theta}\)). With these assumptions the step choice remains unchanged, but convergence proofs employ Young’s inequality and self‑bounding properties to obtain rates \(O(k^{-\nu/\theta})\). This demonstrates that Polyak’s step is intrinsically adaptive, requiring no prior knowledge of \(L,\mu,\nu,\theta\).