# Taking the Road Less Scheduled with Adaptive Polyak Steps

arXiv: https://arxiv.org/abs/2511.07767 · HTML: https://mlsanity.com/paper/2511.07767/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 35 references that are in the map.
- First posted on arXiv 11 Nov 2025.

## Builds on (most cited first, 25 of 25)

- [SGDR: Stochastic Gradient Descent with Warm Restarts](https://mlsanity.com/paper/1608.03983/) (2016)
- [FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness](https://mlsanity.com/paper/2205.14135/) (2022)
- [The FineWeb Datasets: Decanting the Web for the Finest Text Data at Scale](https://mlsanity.com/paper/2406.17557/) (2024)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Scaling Laws and Compute-Optimal Training Beyond Fixed Training Durations](https://mlsanity.com/paper/2405.18392/) (2024)
- [The Road Less Scheduled](https://mlsanity.com/paper/2405.15682/) (2024)
- [The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learning](https://mlsanity.com/paper/1712.06559/) (2017)
- [Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence](https://mlsanity.com/paper/2002.10542/) (2020)
- [SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and Interpolation](https://mlsanity.com/paper/2006.10311/) (2020)
- [Revisiting the Polyak step size](https://mlsanity.com/paper/1905.00313/) (2019)
- [Training Neural Networks for and by Interpolation](https://mlsanity.com/paper/1906.05661/) (2019)
- [Dynamics of SGD with Stochastic Polyak Stepsizes: Truly Adaptive Variants and Convergence to Exact Solution](https://mlsanity.com/paper/2205.04583/) (2022)
- [MoMo: Momentum Models for Adaptive Learning Rates](https://mlsanity.com/paper/2305.07583/) (2023)
- [Stochastic Mirror Descent: Convergence Analysis and Adaptive Variants via the Mirror Stochastic Polyak Stepsize](https://mlsanity.com/paper/2110.15412/) (2021)
- [Cutting Some Slack for SGD with Adaptive Polyak Stepsizes](https://mlsanity.com/paper/2202.12328/) (2022)
- [A Stochastic Proximal Polyak Step Size](https://mlsanity.com/paper/2301.04935/) (2023)
- [Generalized Polyak Step Size for First Order Optimization with Momentum](https://mlsanity.com/paper/2305.12939/) (2023)
- [Stochastic Polyak Step-sizes and Momentum: Convergence Guarantees and Practical Performance](https://mlsanity.com/paper/2406.04142/) (2024)
- [An Adaptive Stochastic Gradient Method with Non-negative Gauss-Newton Stepsizes](https://mlsanity.com/paper/2407.04358/) (2024)
- [Function Value Learning: Adaptive Learning Rates Based on the Polyak Stepsize and Function Splitting in ERM](https://mlsanity.com/paper/2307.14528/) (2023)
- [Locally Adaptive Federated Learning](https://mlsanity.com/paper/2307.06306/) (2023)
- [New Perspectives on the Polyak Stepsize: Surrogate Functions and Negative Results](https://mlsanity.com/paper/2505.20219/) (2025)
- [Analysis of an Idealized Stochastic Polyak Method and its Application to Black-Box Model Distillation](https://mlsanity.com/paper/2504.01898/) (2025)
- [Polyak Stepsize: Estimating Optimal Functional Values Without Parameters or Prior Knowledge](https://mlsanity.com/paper/2508.17288/) (2025)
- [Analysis of Schedule-Free Nonconvex Optimization](https://mlsanity.com/paper/2508.06743/) (2025)

## Built on by (most cited first, 2 of 2)

- [ScheduleFree+: Scaling Learning-Rate-Free & Schedule-Free Learning to Large Language Models](https://mlsanity.com/paper/2605.19095/) (2026)
- [Polyak-Type Extragradient Methods for Monotone Root-Finding Problems](https://mlsanity.com/paper/2609.26581/) (2026)

## Abstract (arXiv)

Schedule-Free SGD, proposed in [Defazio et al., 2024], achieves optimal convergence rates without requiring the training horizon in advance, by replacing learning rate schedules with a principled form of iterate averaging. However, the method still requires tuning a base learning rate whose optimal value depends on unknown problem constants. In this work, we continue down this road by deriving Polyak-type step sizes for Schedule-Free SGD and Adam that compute the learning rate at each iteration from the sampled loss, gradient, and current iterates alone. We first propose an oracle variant that uses per-sample optimal function values and prove an O(1/√t) anytime last-iterate rate for convex Lipschitz objectives. We then remove the oracle requirement with a safeguarded variant that replaces the unknown optimal values with any available lower bound, achieving the same rate up to a neighborhood that vanishes under interpolation. Both step sizes reduce to existing Polyak rules for standard SGD when momentum is set to zero, unifying standard and schedule-free Polyak methods. Numerical experiments on language modeling, including pretraining and distillation, show that the proposed methods match or surpass tuned Schedule-Free baselines while offering greater robustness to hyperparameter choices.