Pith. sign in

REVIEW 3 major objections 3 minor 10 references

Polyak Stepsize: Estimating Optimal Functional Values Without Parameters or Prior Knowledge

T0 review · 3 major / 3 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Twin iterates make the Polyak stepsize fully parameter-free by estimating the optimal value from above.

desk verdict Genuinely new twin-sequence estimator for f*, but the stopping rule invalidates the stated guarantee and Assumption 1 is unproven outside quadratics; worth refereeing, not a desk reject. read the letter →

arxiv 2508.17288 v1 pith:Y5O7M6FM submitted 2025-08-24 math.OC

Farshed Abdukhakimov , Cuong Anh Pham , Samuel Horváth , Martin Takáč , Slavom{i}r Hanzely This is my paper · ORCID
classification math.OC MSC 90C2590C3068W40
keywords parameter-freeoptimizationPolyakstepsizetwiniteratesstrongconvexitylinearconvergenceadaptivestochasticgradientdescentscaleinvariance
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper tries to establish that the classic Polyak stepsize, which normally requires knowing the optimal functional value f*, can be made entirely parameter-free by running two sequences of iterates at once. The higher-valued sequence takes a Polyak-like step using the lower-valued sequence as an ever-improving upper estimate of f*. Under a gap condition that the paper proves for quadratics, the authors show linear convergence for smooth strongly convex problems with no tunable step size, and sublinear convergence for convex problems with bounded gradients. A stochastic momentum variant is also proposed, and experiments show it competing with tuned baselines across classification and regression tasks.

What carries the argument

The load-bearing object is the pair of twin sequences x_k and y_k together with the loss-difference stepsize η_k = 2(f(x_k)−f(y_k))/‖∇f(x_k)‖², where the sequence with the higher functional value is updated and the lower-valued sequence acts as a dynamic upper bound on f*. Assumption 1 is the mechanism converting the unknown gap to f* into a controlled fraction of the observed loss gap, which ensures the stepsize cannot vanish and drives the linear convergence result.

What would settle it

Run Twin Polyak from two starting points with equal functional values on any strongly convex smooth function, for instance f(x)=x² with x₀=1 and y₀=−1; Algorithm 1 stops at line 4 because |f(x₀)−f(y₀)| < ε, even though x₀ is far from the optimum. More generally, find any smooth strongly convex f where the ratio |f(x_k)−f(y_k)|/(max{f(x_k),f(y_k)}−f*) tends to 0 along the TP trajectory, which would directly violate Assumption 1 and invalidate the linear-rate conclusion.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1: if f is μ-strongly convex and L-smooth, and the Twin Polyak trajectory satisfies Assumption 1, then the stepsize η_k = 2(f(x_k)−f(y_k))/‖∇f(x_k)‖² is at least a/L and the iterates converge linearly to x* with rate 1 − aμ/L. The proof is a direct application of the standard Polyak descent bound once the stepsize is shown to be bounded below by a/L. The paper also establishes a O(1/√k) guarantee for convex functions with bounded gradients under gap assumptions, proves that for quadratics the twin iterates alternate and converge with ratio ‖y₀‖²/‖x₀‖², and provides a stochastic variant that replaces full losses and gradients with batches plus momentum for practical use.

Load-bearing premise

Assumption 1, that the loss gap between the two iterates stays at least a fixed fraction a of the larger iterate's distance to f*, is the only route to the stepsize lower bound a/L; the paper proves this only for quadratics, leaving it unverified for general strongly convex functions.

Editorial extensions

If this is right

  • If Assumption 1 holds along the trajectory, TP converges linearly at rate 1 − aμ/L for smooth strongly convex functions, matching gradient descent with a well-chosen constant stepsize.
  • TP reaches an ε-accurate solution in O((1/a)(L/μ) log(1/ε)) iterations without ever receiving f*, L, μ, or any stepsize parameter.
  • Because the stepsize depends only on current losses and gradients, TP is invariant under transformations f → c·f and f → c + f, so dataset rescaling or translation does not change the iterates.
  • For convex losses with uniformly bounded gradients, TP has sublinear convergence O(1/√k) under the same type of gap conditions.
  • The stochastic momentum variant STPm is shown numerically to reach performance competitive with tuned SPSmax, DecSPS, SLS, and SGD on binary classification and regression datasets.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Assumption 1 is only verified for quadratics; the linear-rate theorem is conditional on an unproven property of general strongly convex trajectories, so a natural test is to record the ratio |f(x_k)−f(y_k)|/(max{f(x_k),f(y_k)}−f*) along TP on simple strongly convex losses and check whether it stays bounded away from zero.
  • If the gap ratio turns out to fail only in contrived cases, the algorithm could be made more robust by handling the near-equal-loss stopping condition, since TP currently stops when |f(x_k)−f(y_k)| < ε even if the iterates are still far from the optimum.
  • The twin-sequence idea is a general recipe: any method that needs an optimal-value estimate could use a second trajectory as an upper oracle, and the unbiasedness caveat of Lemma 3 suggests that stochastic adaptive stepsizes generally sacrifice gradient unbiasedness, pointing toward momentum-based corrections like STPm as a practical necessity.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 3 minor

Summary. The paper proposes Twin Polyak (TP), a deterministic parameter-free variant of the Polyak stepsize that maintains two sequences of iterates and uses the higher-valued sequence to update with a stepsize based on the functional gap between the two iterates, treating the lower value as a proxy for f*. The authors claim that TP is entirely parameter-free, scaling- and translation-invariant, and that it provides linear convergence for strongly convex smooth functions (Theorem 1) and O(1/sqrt(k)) rates under bounded gradients (Lemma 2), conditional on two assumptions that are proved only for quadratics. The paper also presents stochastic extensions STP and STPm, along with extensive numerical comparisons on LIBSVM datasets and a public code repository.

Significance. If the central claims were valid, the twin-sequence construction would be a noteworthy contribution to parameter-free optimization, and the explicit quadratic analysis in Lemma 1 plus the invariance properties are genuinely interesting. The experiments are broad and reproducible, with comparisons against several tuned baselines. However, the main theorem is conditional on an assumption that is not established for the algorithm, and the algorithm's stopping rule can return an arbitrarily suboptimal point even when all stated assumptions hold. These issues are load-bearing: the paper's headline claim that TP provably estimates f* and converges to an epsilon-neighborhood is not supported as written.

major comments (3)
  1. [Section 2, Algorithm 1, line 4] The stopping rule |f(x_k)-f(y_k)| < epsilon does not certify epsilon-optimality of x_k. For f(x) = 1/2 ||x||^2, x0 = (1,0), y0 = (sqrt(1-epsilon),0) with epsilon in (0,1), we have |f(x0)-f(y0)| = epsilon/2 < epsilon, so Algorithm 1 returns x0 at iteration 0, while f(x0)-f* = 1/2. Assumptions 1 and 2 hold at this point with a = epsilon and b = 1-epsilon, so the failure occurs even when the assumptions of Theorem 1 are in force. The claimed epsilon-neighborhood guarantee of Theorem 1 is therefore false for the algorithm as written.
  2. [Section 3.1, Assumption 1] The existence of a uniform constant a in (0,1) along the TP trajectory is proved only for quadratics (Lemma 1). For general mu-strongly convex and L-smooth functions, the paper provides no argument that the generated sequences satisfy Assumption 1, and nothing in the update rule prevents the ratio |f(x_k)-f(y_k)|/(max{f(x_k),f(y_k)}-f*) from becoming arbitrarily small or zero before x_k reaches the optimum. Since Theorem 1's lower bound eta_k >= a/L and the linear rate both depend on Assumption 1, the conclusion in Section 7 that TP provably enjoys linear convergence for strongly convex functions is unsupported.
  3. [Theorem 1, iteration counter] In Algorithm 1 exactly one of the twin sequences is updated per iteration, so the sequence {x_k} changes only on iterations where f(x_k) > f(y_k). The proof via Proposition 2 applies only to those update steps, yet the theorem states ||x_k - x*||^2 <= (1 - a mu/L)^k ||x0 - x*||^2 for every TP iteration k. This is not justified; the effective number of x-updates is about k/2, so the rate and the complexity bound O((1/a)(L/mu) log(1/epsilon)) need an additional factor of two.
minor comments (3)
  1. [Appendix C, Lemma 3] The proof of equation (19) replaces E_zeta[s_{i,zeta} \nabla f_i(x)] with E_zeta[s_{i,zeta}] \nabla f_i(x), which is exactly the independence that the lemma aims to establish. As written, the proof is circular and the lemma is not established.
  2. [Sections 1.3 and 7] The claim that TP and STPm are completely parameter-free is overstated: Algorithm 1 requires a stopping tolerance epsilon, and Algorithm 2 requires a momentum parameter alpha in [0,1). These are user-specified quantities, even if they are not problem-dependent like L or mu.
  3. [Section 6, Limitations] The stated limitation about initialization sensitivity is too weak. As shown in the first major comment, a positive-measure set of initializations (any pair with |f(x)-f(y)| < epsilon) makes TP terminate at k=0 with suboptimality arbitrarily large relative to epsilon, not merely 'suboptimal performance'.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main result is a conditional convergence theorem under an explicit separation assumption, with the Polyak analysis supplied independently.

full rationale

The paper's central claim, Theorem 1, is explicitly conditional on Assumption 1: |f(x_k)-f(y_k)| >= a(max{f(x_k), f(y_k)} - f*). This assumption is an inequality quantifying separation of the twin losses; it is not a restatement of the theorem's conclusion, nor does the algorithm fit a to data. For quadratics, Lemma 1 independently establishes the required separation with an explicit ratio formula, so the assumption has non-circular content in at least that case. For general strongly convex functions the assumption is not proved, and the conclusion section's phrasing that TP 'provably enjoys linear convergence' overstates the conditional result; this is a soundness gap, not a circular reduction. The use of f(y_k) as an estimate of f* is an upper bound by construction, and the stepsize is a scaled Polyak step; Proposition 2 is a standard external result with a proof included in Appendix D.3, so the convergence argument rests on stated assumptions rather than on the claim being proved. The stopping rule in Algorithm 1 (return when |f(x_k)-f(y_k)| < epsilon) is not certified against f*-suboptimality and can terminate at a non-optimal point; this is a correctness issue, which the Limitations section partially acknowledges by noting that 'poor initialization of x0 and y0 might lead to suboptimal performance.' Self-citations to SANIA, PSPS, SP2, and AI-SARAH appear only in related-work discussions and are not load-bearing for Theorem 1 or Lemma 2. No fitted-input-called-prediction, imported uniqueness, or ansatz-smuggling pattern is present. The derivation is therefore self-contained against the standard Polyak analysis; the main weaknesses are unproven assumptions and stopping-certificate soundness, not circularity.

Assumptions & free parameters 2 free parameters · 6 assumptions · 0 invented entities

The method introduces a second iterate sequence as an algorithmic device, not a new physical or model entity. The free parameters are the stopping threshold epsilon and the momentum alpha in STPm; the deterministic TP itself has no stepsize parameter. The load-bearing axioms are Assumptions 1 and 2, which are not derived for the algorithm and can be violated, plus standard convexity and smoothness conditions from the literature.

free parameters (2)
  • epsilon (stopping threshold)
    Algorithm 1 line 4 returns x_k whenever |f(x_k)-f(y_k)| < epsilon. This is not a standard accuracy tolerance because the guarantee is about f(x)-f*, not about the gap. A large epsilon can stop the method at a suboptimal point.
  • momentum parameter alpha (STPm) = 0.9, 0.85
    Algorithm 2 requires alpha in [0,1); experiments in Section 5 use alpha=0.9 for a1a, w1a, real-sim and alpha=0.85 for mushrooms and colon-cancer. This contradicts the abstract's 'without parameters' claim for the stochastic method.
assumptions (6)
  • ad hoc to paper Assumption 1: |f(x_k)-f(y_k)| >= a (max{f(x_k),f(y_k)} - f*) for some a in (0,1)
    Stated in Section 3.1, not proven for TP trajectories on general functions; can be false when the two iterates have equal function values.
  • ad hoc to paper Assumption 2: min{f(x_k),f(y_k)} - f* >= b (max{f(x_k),f(y_k)} - f*) for some b in (0,1)
    Stated in Section 3.1 for the bounded-gradient result (Lemma 2); similarly unverified for TP trajectories.
  • domain assumption Strong convexity (Definition 1)
    Used in Theorem 1 for linear convergence.
  • domain assumption L-smoothness (Definition 2)
    Used in Theorem 1 to bound the stepsize below by a/L.
  • domain assumption G-bounded gradients (Definition 3)
    Used in Lemma 2 for the O(1/sqrt(k)) rate; the paper itself notes this is mutually exclusive with strong convexity.
  • standard math Proposition 2 (standard Polyak convergence)
    Stated in Section 3 and proved in Appendix D.3; TP's proof reduces to this.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Polyak Stepsize: Estimating Optimal Functional Values Without Parameters or Prior Knowledge." pith.science (2026). https://pith.science/paper/Y5O7M6FM

@misc{pith2026250817288,
  author       = {Pith},
  title        = {Pith review of: Polyak Stepsize: Estimating Optimal Functional Values Without Parameters or Prior Knowledge},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/Y5O7M6FM}},
  note         = {Machine review of arXiv:2508.17288}
}
read the original abstract

The Polyak stepsize for Gradient Descent is known for its fast convergence but requires prior knowledge of the optimal functional value, which is often unavailable in practice. In this paper, we propose a parameter-free approach that estimates this unknown value during the algorithm's execution, enabling a parameter-free stepsize schedule. Our method maintains two sequences of iterates: one with a higher functional value is updated using the Polyak stepsize, and the other one with a lower functional value is used as an estimate of the optimal functional value. We provide a theoretical analysis of the approach and validate its performance through numerical experiments. The results demonstrate that our method achieves competitive performance without relying on prior function-dependent information.

Figures

Figures reproduced from arXiv: 2508.17288 by the authors.

Figure 1
Figure 1. Sensitivity of stochastic methods SGD, SPSmax, and DecSPS to their respective hyperparameters on LIBSVM datasets [Chang and Lin, 2011]. We repeat the experiments for 5 different random seeds and plot mean ± standard deviation. For easier readability, we reduce variance by plotting running average of functional subpotimality. Gradient Descent (SGD) parameter-free via a backtracking procedure. Ivgi et al. [2023] intro… view at source ↗
Figure 2
Figure 2. Performance and stepsize evolution of STPm compared to other methods on binary classification problems minimizing logistic regression loss function. 10 10 10 8 10 6 10 4 10 2 10 0 10 2 10 4 Learning rate 0.50 0.55 0.60 0.65 0.70 0.75 Test Accuracy Adam Adagrad Momo SPS STPm Stochastic, covtype.binary (a) Linear model 10 10 10 8 10 6 10 4 10 2 10 0 10 2 10 4 Learning rate 0.0 0.2 0.4 0.6 0.8 Test Accuracy Adam Adagra… view at source ↗
Figure 3
Figure 3. Test accuracy after 50 epochs, for varying learning rate. [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figures from the paper (5 more)
Figure 4
Figure 4. Figure 4: Performance and stepsize evolution of STP compared to other methods on binary classification problems minimizing logistic regression loss function. 13 [PITH_FULL_IMAGE:figures/full_fig_p013_4.png]
Figure 5
Figure 5. Figure 5: Performance and stepsize evolution of TP compared to other methods on binary classification problems minimizing logistic regression loss function. 14 [PITH_FULL_IMAGE:figures/full_fig_p014_5.png]
Figure 6
Figure 6. Figure 6: Performance and stepsize evolution of STP compared to other methods on regression problems minimizing least squares loss function. 15 [PITH_FULL_IMAGE:figures/full_fig_p015_6.png]
Figure 7
Figure 7. Figure 7: Performance and stepsize evolution of TP compared to other methods on regression problems minimizing least squares loss function. 16 [PITH_FULL_IMAGE:figures/full_fig_p016_7.png]
Figure 8
Figure 8. Figure 8: Performance and stepsize evolution of STPm compared to other methods with momentum on logistic regression problems. 17 [PITH_FULL_IMAGE:figures/full_fig_p017_8.png]

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

10 extracted references · 4 canonical work pages

  1. [1]

    SANIA: Polyak-type optimization framework leads to scale invariant stochastic algorithms

    Farshed Abdukhakimov, Chulu Xiang, Dmitry Kamzolov, Robert Gower, and Martin Takáˇc. SANIA: Polyak-type optimization framework leads to scale invariant stochastic algorithms. arXiv preprint arXiv:2312.17369,

    arXiv

  2. [1969]

    MoMo: Momentum models for adaptive learning rates

    Fabian Schaipp, Ruben Ohana, Michael Eickenberg, Aaron Defazio, and Robert Gower. MoMo: Momentum models for adaptive learning rates. arXiv preprint arXiv:2305.07583,

    arXiv

  3. [2001]

    SARAH: a novel method for machine learning problems using stochastic recursive gradient

    Lam Nguyen, Jie Liu, Katya Scheinberg, and Martin Takáˇc. SARAH: a novel method for machine learning problems using stochastic recursive gradient. In In 34th International Conference on Machine Learning, ICML 2017,

    work page 2017

  4. [2011]

    Remove that Square Root: A New Efficient Scale-Invariant Version of AdaGrad

    URL https: //www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/. Sayantan Choudhury, Nazarii Tupitsa, Nicolas Loizou, Samuel Horváth, Martin Takáˇc, and Eduard Gorbunov. Remove that square root: A new efficient scale-invariant version of AdaGrad. arXiv preprint arXiv:2403.02648,

    work page Pith review arXiv

  5. [2019]

    Adaptive learning rates for faster stochastic gradient methods

    10 Samuel Horváth, Konstantin Mishchenko, and Peter Richtárik. Adaptive learning rates for faster stochastic gradient methods. arXiv preprint arXiv:2208.05287,

    arXiv

  6. [2020]

    Aleksandr Beznosikov and Martin Takáˇc

    URL https://proceedings.mlr.press/ v119/berrada20a.html. Aleksandr Beznosikov and Martin Takáˇc. Random-reshuffled SARAH does not need a full gradient computations. In Optimization for Machine Learning Workshop @ NeurIPS 2021,

    work page 2021

  7. [2021]

    Prodigy: An expeditiously adaptive parameter-free learner

    Konstantin Mishchenko and Aaron Defazio. Prodigy: An expeditiously adaptive parameter-free learner. arXiv preprint arXiv:2306.06101,

    arXiv

  8. [2022]

    Robert Gower, Guillaume Garrigos, Nicolas Loizou, Dimitris Oikonomou, Konstantin Mishchenko, and Fabian Schaipp

    URL https://arxiv.org/abs/2202.12328. Robert Gower, Guillaume Garrigos, Nicolas Loizou, Dimitris Oikonomou, Konstantin Mishchenko, and Fabian Schaipp. Analysis of an idealized stochastic Polyak method and its application to black-box model distillation. arXiv preprint arXiv:2504.01898,

    arXiv

Show all 10 references
  1. [2023]

    SP2: A second order stochastic polyak method

    Shuang Li, William J Swartworth, Martin Takáˇc, Deanna Needell, and Robert M Gower. SP2: A second order stochastic polyak method. ICLR 2023,

    2023

  2. [2025]

    Revisiting the Polyak step size

    Elad Hazan and Sham Kakade. Revisiting the Polyak step size. arXiv preprint arXiv:1905.00313,

    1905 arXiv

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.