Research map / Optimization / Nonconvex and smooth optimization

Taking the Road Less Scheduled with Adaptive Polyak Steps

NeurIPS 2026 · Optimization › Nonconvex and smooth optimization · approach: Coordinate and Adam convergence analysis · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Derives Polyak-type adaptive step sizes for Schedule-Free SGD and Adam (oracle and safeguarded variants), proves O(1/sqrt(t)) last-iterate rates for convex Lipschitz objectives, and reports language-modeling and distillation experiments without learning-rate sweeps.

Problem

Schedule-Free methods still require tuning a base learning rate whose optimal value depends on unknown problem constants (Lipschitz constant, initial distance, horizon), and the classical Polyak step sizes do not directly apply to the Schedule-Free update.

Approach

Adapt the SPS+ and safeguarded SPS step sizes to the Schedule-Free z-sequence by bounding the gradient-evaluation inner product via convexity at y_t, yielding a step size that uses only the sampled loss, gradient, and current iterates; a safeguard in the denominator and a lower bound replace the oracle optimal value; the rule reduces to standard Polyak SGD at beta=0.

Key results

• On GPT-2 pretraining, the Polyak variant matches Schedule-Free AdamW in training loss and achieves the best validation loss across both safeguard settings, with a flat LR sensitivity curve.
• A single Polyak run takes about 21 GPU-hours on 4xA100, versus about 220 and 195 GPU-hours for the AdamW and Schedule-Free AdamW LR sweeps on 4xH100.
• The oracle variant proves an O(1/sqrt(t)) anytime last-iterate rate for convex Lipschitz objectives; the safeguarded variant achieves the same rate up to a sigma^2-controlled neighborhood.

Surprising findings

• The safeguarded variant does not guarantee Fejer monotonicity, so its analysis requires Lipschitz continuity globally rather than on the ball.

Limitations

• The convergence theory covers only convex objectives with the SGD-based update; the Adam variant has no guarantee.
• The oracle variant needs per-sample optimal values, approximated in distillation by teacher loss, and the safeguarded variant has a neighborhood term unless interpolation holds.
• Experiments are limited to language modeling and distillation at GPT-2 scale.

Experimental setup

Datasets: FineWeb 10B tiny_shakespeare

Benchmarks: FineWeb 10B validation loss tiny_shakespeare validation loss

Metrics: validation loss training loss learning rate sensitivity

Baselines: AdamW Schedule-Free AdamW SGD with momentum Adam Schedule-Free Adam Iams-Adam

Builds on: Schedule-Free SGD SPS+ SPS_safe Adam AdamW

Closest papers by meaning

• Adaptive Sharpness-Aware Minimization with a Polyak-type Step size: A Theory-Grounded Scheduler (ICML 2026 · similarity 0.90)
• The Road Less Scheduled (NeurIPS 2024 · similarity 0.89)
• General framework for online-to-nonconvex conversion: Schedule-free SGD is also effective for nonconvex optimization (ICML 2025 · similarity 0.86)
• Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on Ill-Conditioned Problems (ICML 2025 · similarity 0.86)
• Stepsize anything: A unified learning rate schedule for budgeted-iteration training (NeurIPS 2025 · similarity 0.86)
• New Perspectives on the Polyak Stepsize: Surrogate Functions and Negative Results (NeurIPS 2025 · similarity 0.86)