Revisiting the Polyak step size

2019/05/01 by Elad Hazan, Sham Kakade, Sham M. Kakade +2 · 21 citations
Computer Science · Decision Sciences · Engineering · Mathematics · #Advanced Bandit Algorithms Research #FOS: Mathematics #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #math.OC

paper · pdf · doi:10.48550/arxiv.1905.00313

openalex publication_date 2019/05/01 · arxiv created 2022/08/02 · arxiv updated 2022/08/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This paper revisits the Polyak step size schedule for convex optimization problems, proving that a simple variant of it simultaneously attains near optimal convergence rates for the gradient descent algorithm, for all ranges of strong convexity, smoothness, and Lipschitz parameters, without a-priory knowledge of these parameters.

Citations

• A Stochastic Approximation Method

Cited by

• Parameter-Free Accelerated Quasi-Newton Method for Nonconvex Optimization
• Safeguarded Stochastic Polyak Step Sizes for Non-smooth Optimization: Robust Performance Without Small (Sub)Gradients
• Taking the Road Less Scheduled with Adaptive Polyak Steps
• Unified Theory of Adaptive Variance Reduction
• Normalized First-Order Methods for Convex (L0, L1)-Smooth Optimization with Inexact Gradients
• Large-scale empirical tuning and comparison of default optimizers for variational inference
• Accelerated Distance-adaptive Methods for Hölder Smooth and Convex Optimization
• Stochastic Adaptive Gradient Descent Without Descent
• Polyak Stepsize: Estimating Optimal Functional Values Without Parameters or Prior Knowledge
• Gradient Methods with Online Scaling Part II. Practical Aspects
• Sparse Polyak: an adaptive step size rule for high-dimensional M-estimation
• Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence
• Simple Optimizers for Convex Aligned Multi-Objective Optimization
• Complexity Guarantees for Polyak Steps with Momentum
• Approximately Exact Line Search
• Stein Diffusion Guidance: Training-Free Posterior Correction for Sampling Beyond High-Density Regions
• Glocal Smoothness: Line search and adaptive step sizes can help in theory too!
• Gradient Methods with Online Scaling Part I. Theoretical Foundations
• New Perspectives on the Polyak Stepsize: Surrogate Functions and Negative Results
• Entropic Mirror Descent for Linear Systems: Polyak's Stepsize and Implicit Bias
• Discrete-Time Adaptive Control in High Dimensions: Near Dimension-Free Performance via Mirror Descent

Related

• Complexity Guarantees for Polyak Steps with Momentum
• New Results on the Polyak Stepsize: Tight Convergence Analysis and Universal Function Classes
• Two Polyak-Type Step Sizes for Mirror Descent
• New Perspectives on the Polyak Stepsize: Surrogate Functions and Negative Results
• Towards Statistical and Computational Complexities of Polyak Step Size Gradient Descent