Cover Image

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

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Orabona, Francesco, D'Orazio, Ryan
Format:	Preprint
Published:	2025
Subjects:	Optimization and Control Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Solving Hidden Monotone Variational Inequalities with Surrogate Losses
by: D'Orazio, Ryan, et al.
Published: (2024)

Adaptive SGD with Line-Search and Polyak Stepsizes: Nonconvex Convergence and Accelerated Rates
by: Wu, Haotian
Published: (2025)

A Modern Introduction to Online Learning
by: Orabona, Francesco
Published: (2019)

A Note on How to Remove the $\ln\ln T$ Term from the Squint Bound
by: Orabona, Francesco
Published: (2026)

New Results on the Polyak Stepsize: Tight Convergence Analysis and Universal Function Classes
by: He, Chang, et al.
Published: (2025)

A Finite-Time Analysis of TD Learning with Linear Function Approximation without Projections or Strong Convexity
by: Lee, Wei-Cheng, et al.
Published: (2025)

An Equivalence Between Static and Dynamic Regret Minimization
by: Jacobsen, Andrew, et al.
Published: (2024)

A Best-of-Both-Worlds Proof for Tsallis-INF without Fenchel Conjugates
by: Lee, Wei-Cheng, et al.
Published: (2025)

New Lower Bounds for Stochastic Non-Convex Optimization through Divergence Decomposition
by: Saad, El Mehdi, et al.
Published: (2025)

Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion
by: Cutkosky, Ashok, et al.
Published: (2023)

Accelerating Level-Value Adjustment for the Polyak Stepsize
by: Liu, Anbang, et al.
Published: (2023)

Minimisation of Polyak-Łojasewicz Functions Using Random Zeroth-Order Oracles
by: Farzin, Amir Ali, et al.
Published: (2024)

Negative Stepsizes Make Gradient-Descent-Ascent Converge
by: Shugart, Henry, et al.
Published: (2025)

Beyond the Ideal: Analyzing the Inexact Muon Update
by: Shulgin, Egor, et al.
Published: (2025)

Polyak Stepsize: Estimating Optimal Functional Values Without Parameters or Prior Knowledge
by: Abdukhakimov, Farshed, et al.
Published: (2025)

Stochastic Approximation with Block Coordinate Optimal Stepsizes
by: Jiang, Tao, et al.
Published: (2025)

Adaptive Polyak Stepsize with Level-value Adjustment for Distributed Optimization
by: Ouyang, Chen, et al.
Published: (2026)

Constrained Online Convex Optimization with Polyak Feasibility Steps
by: Hutchinson, Spencer, et al.
Published: (2025)

Non-convex Stochastic Composite Optimization with Polyak Momentum
by: Gao, Yuan, et al.
Published: (2024)

Parameter-free Clipped Gradient Descent Meets Polyak
by: Takezawa, Yuki, et al.
Published: (2024)

AdaGrad Meets Muon: Adaptive Stepsizes for Orthogonal Updates
by: Zhang, Minxin, et al.
Published: (2025)

Simple Stepsize for Quasi-Newton Methods with Global Convergence Guarantees
by: Agafonov, Artem, et al.
Published: (2025)

Constant Stepsize Q-learning: Distributional Convergence, Bias and Extrapolation
by: Zhang, Yixuan, et al.
Published: (2024)

Bias and Extrapolation in Markovian Linear Stochastic Approximation with Constant Stepsizes
by: Huo, Dongyan, et al.
Published: (2022)

Sparse Polyak with optimal thresholding operators for high-dimensional M-estimation
by: Qiao, Tianqi, et al.
Published: (2025)

Faster Stochastic Algorithms for Minimax Optimization under Polyak--Łojasiewicz Conditions
by: Chen, Lesi, et al.
Published: (2023)

Stochastic Polyak Step-sizes and Momentum: Convergence Guarantees and Practical Performance
by: Oikonomou, Dimitris, et al.
Published: (2024)

On the Complexity of Finite-Sum Smooth Optimization under the Polyak-Łojasiewicz Condition
by: Bai, Yunyan, et al.
Published: (2024)

Coupling-based Convergence Diagnostic and Stepsize Scheme for Stochastic Gradient Descent
by: Li, Xiang, et al.
Published: (2024)

An Adaptive Stochastic Gradient Method with Non-negative Gauss-Newton Stepsizes
by: Orvieto, Antonio, et al.
Published: (2024)

Sparse Polyak: an adaptive step size rule for high-dimensional M-estimation
by: Qiao, Tianqi, et al.
Published: (2025)

Gradient Descent with Polyak's Momentum Finds Flatter Minima via Large Catapults
by: Phunyaphibarn, Prin, et al.
Published: (2023)

SANIA: Polyak-type Optimization Framework Leads to Scale Invariant Stochastic Algorithms
by: Abdukhakimov, Farshed, et al.
Published: (2023)

MARINA-P: Superior Performance in Non-smooth Federated Optimization with Adaptive Stepsizes
by: Sokolov, Igor, et al.
Published: (2024)

Enhancing Stochastic Optimization for Statistical Efficiency Using ROOT-SGD with Diminishing Stepsize
by: Li, Chris Junchi
Published: (2024)

High-Probability Bounds for SGD under the Polyak-Lojasiewicz Condition with Markovian Noise
by: Kar, Avik, et al.
Published: (2026)

A Local Polyak-Lojasiewicz and Descent Lemma of Gradient Descent For Overparametrized Linear Models
by: Xu, Ziqing, et al.
Published: (2025)

Two-Timescale Linear Stochastic Approximation: Constant Stepsizes Go a Long Way
by: Kwon, Jeongyeol, et al.
Published: (2024)

On the Interplay Between Stepsize Tuning and Progressive Sharpening
by: Roulet, Vincent, et al.
Published: (2023)

Dynamics of SGD with Stochastic Polyak Stepsizes: Truly Adaptive Variants and Convergence to Exact Solution
by: Orvieto, Antonio, et al.
Published: (2022)