Pith. sign in

REVIEW 6 cited by

Revisiting the Polyak step size

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 1905.00313 v2 pith:E4JF2PAA submitted 2019-05-01 math.OC

Elad Hazan , Sham Kakade This is my paper · ORCID
classification math.OC
keywords parameterspolyaksizestepa-prioryalgorithmattainsconvergence
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
read the original 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.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 6 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Discrete-Time Adaptive Control in High Dimensions: Near Dimension-Free Performance via Mirror Descent

    math.OC 2026-08 conditional novelty 8.0 of 10

    Mirror-descent adaptive laws with a non-Euclidean Polyak step size keep the regret of high-dimensional adaptive control nearly independent of the ambient dimension for sparse, low-rank, and simplex-structured parameters.

  2. Safeguarded Stochastic Polyak Step Sizes for Non-smooth Optimization: Robust Performance Without Small (Sub)Gradients

    math.OC 2025-12 conditional novelty 7.0 of 10

    A safeguarded stochastic Polyak step size, SPS_safe, yields O(1/√T) convergence to a neighborhood for convex non-smooth problems without interpolation or oracle loss values, with a momentum variant.

  3. Nesterov Finds GRAAL: Optimal and Adaptive Gradient Method for Convex Optimization

    math.OC 2025-07 conditional novelty 7.0 of 10

    Accelerated GRAAL is the first adaptive first-order method that proves near-optimal accelerated complexity for convex L-smooth and (L0,L1)-smooth functions with geometric stepsize growth.

  4. Gradient Methods with Online Scaling Part I. Theoretical Foundations

    math.OC 2025-05 conditional novelty 7.0 of 10

    Online scaled gradient methods adapt matrix step sizes via online learning, match the best fixed step size asymptotically, and achieve non-asymptotic superlinear convergence on smooth strongly convex problems.

  5. Simple Optimizers for Convex Aligned Multi-Objective Optimization

    cs.LG 2025-09 reject novelty 6.0 of 10

    Convex AMOO is analyzed under Lipschitz and smooth assumptions with a maximum-gap metric, giving simple gradient methods with rates independent of the number of objectives, plus a flawed equal-weights lower bound.

  6. Normalized First-Order Methods for Convex (L0, L1)-Smooth Optimization with Inexact Gradients

    math.OC 2026-07 conditional novelty 5.0 of 10

    Comparison-oracle variants of NGD and Polyak GD converge for convex (L0, L1)-smooth objectives when the normalized-gradient error δ is bounded by explicit O(√ε)-scale thresholds.

Pith tools