Revisiting the Polyak step size

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

paper · pdf · doi:10.48550/arxiv.1905.00313

openalex publication_date 2019/05/01 · 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
• Schedulers for Schedule-free: Theoretically inspired hyperparameters
• 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\n Convergence
• Simple Optimizers for Convex Aligned Multi-Objective Optimization

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