Pith. sign in

REVIEW 3 major objections 3 minor 32 references

On the asymptotic convergence and acceleration of gradient methods

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

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

Pith's one-line read Gradient methods provably zigzag; new stepsize breaks cycle

desk verdict Solid unified analysis of zigzag for a family of gradient stepsizes; main theorems are sound under distinct eigenvalues, but the abstract oversells the result to repeated eigenvalues. read the letter →

arxiv 1908.07111 v1 pith:KWXIJJI5 submitted 2019-08-19 math.OC

Yakui Huang , Yu-Hong Dai , Xin-Wei Liu , Hongchao Zhang This is my paper · ORCID
classification math.OC MSC 90C2090C2590C30
keywords gradientmethodsasymptoticconvergencezigzagphenomenonspectralpropertiessteepestdescentminimalBarzilai-Borweinmethodquadraticoptimization
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

This paper proves that every gradient method whose stepsize is a weighted Rayleigh quotient, $\alpha_k = g_k^T \Psi(A) g_k / (g_k^T \Psi(A) A g_k)$, eventually confines its search to the two-dimensional subspace spanned by the eigenvectors of the smallest and largest eigenvalues of the Hessian. This family includes steepest descent ($\Psi(A)=I$) and the minimal gradient method ($\Psi(A)=A$). The authors derive explicit limits for the objective-value ratios, gradient-norm ratios, and stepsizes on even and odd iterates, showing a two-step alternating cycle. They also construct a new stepsize, chosen to terminate exactly on two-dimensional quadratics, and prove that it converges to $1/\lambda_n$, the reciprocal of the largest eigenvalue. A periodic method that alternates Barzilai-Borwein steps, the family stepsize, and the new stepsize is shown numerically to outperform several recent gradient methods.

What carries the argument

The argument is carried by a nonlinear transformation $T$ on the normalized squared-gradient vector $p$, defined by $(Tp)^{(i)} = (\lambda_i - \gamma(p))^2 p^{(i)} / \sum_j(\lambda_j - \gamma(p))^2 p^{(j)}$, where $\gamma(p) = \sum_i \Psi(\lambda_i)\lambda_i p^{(i)} / \sum_i \Psi(\lambda_i)p^{(i)}$. A monotone quantity $\Theta(p)$ increases under $T$, forcing the even and odd subsequences to converge to a two-point cycle supported on two eigenvalues; a ratio argument then forces those indices to be $1$ and $n$. The acceleration uses a new stepsize derived from a finite-termination condition on two-dimensional quadratics, expressed through a $2\times2$ matrix $H^k$ built from the current and previous gradients.

What would settle it

For a quadratic with distinct eigenvalues, e.g., $A = \mathrm{diag}(1,3,10)$, run the minimal-gradient method from a starting point whose gradient has nonzero components on all three eigenvectors; measure $1/\alpha_{2k}+1/\alpha_{2k+1}$ over many iterations. If it does not converge to $\lambda_1+\lambda_n = 11$, the central theorem is wrong.

Watch

Extended reading notes

Core claim

Under a strictly ordered spectrum $0<\lambda_1<\cdots<\lambda_n$ and an initial gradient with nonzero components on both extreme eigenvectors, the normalized squared-gradient components converge on even and odd subsequences to two-point limits supported on the indices $1$ and $n$, with explicit formulas (2.29) and (2.30). Consequently, the stepsize $\alpha_k$ converges to one of two limits, (2.33) and (2.34), and the sum identity $\lim_{k\to\infty}(1/\alpha_{2k}+1/\alpha_{2k+1}) = \lambda_1+\lambda_n$ holds. The newly derived stepsize $\tilde\alpha_k$ in (3.12) converges to $1/\lambda_n$ along the iterates of any method in the family, thereby eliminating the largest-eigenvalue component and breaking the zigzag pattern.

Load-bearing premise

The Hessian must have strictly distinct eigenvalues, ordered $0<\lambda_1<\cdots<\lambda_n$; if two eigenvalues coincide, the proof that the iterates collapse onto the two extreme eigenvectors no longer goes through.

Editorial extensions

If this is right

  • Every method in the family (1.11) has the same worst-case two-step asymptotic rate $((\kappa-1)/(\kappa+1))^4$, independent of the choice of $\Psi$.
  • The odd and even subsequences of objective values and gradient norms converge at the same two-step speed, while the consecutive-step ratios may converge at different speeds unless $\Psi(\lambda_n)=\Psi(\lambda_1)$ or a similar symmetry holds.
  • The new stepsize $\tilde\alpha_k$ converges to $1/\lambda_n$, so periodically inserting it into the iteration removes the largest-eigenvalue component and provably breaks the zigzag pattern.
  • The proposed periodic gradient method (Algorithm 3.1) converges R-linearly on quadratics and, in the reported experiments, consistently outperforms the BB, DY, ABBmin2, and SDC methods on 630 random test instances.
  • The asymptotic formulas in Theorems 2.7 and 2.9 give testable predictions for the convergence ratios of any method in the family on generic quadratics with distinct eigenvalues.

Reading between the lines

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

  • The strict distinct-eigenvalue assumption is likely not just technical: with repeated eigenvalues, the collapse to the two extreme eigenvectors may be replaced by a cycle supported on any pair of eigenvalues selected by the initial data, so the explicit rate formulas would need reformulation.
  • The spectral property of $\tilde\alpha_k$ suggests a practical heuristic for general smooth optimization: estimate the local largest eigenvalue of the Hessian periodically and take a short step to damp the corresponding gradient component, a strategy that may accelerate Newton-free and quasi-Newton frameworks.
  • The new stepsize formula (3.12) generalizes a known two-dimensional finite-termination construction; the same derivation could be adapted to terminate on three-dimensional subspaces, potentially yielding a family of stepsizes converging to reciprocals of selected interior eigenvalues.
  • The proof that $\tilde\alpha_k \to 1/\lambda_n$ relies only on the asymptotic two-point cycle, so the same acceleration should work for any method in the family, including variants with $\Psi$ chosen to reduce the cost of computing the step.
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 studies gradient methods for strongly convex quadratics whose stepsize is the weighted Rayleigh quotient α_k = g_k^T Ψ(A) g_k / (g_k^T Ψ(A) A g_k), covering steepest descent (Ψ = I) and minimal gradient (Ψ = A) as special cases. Under the assumption that the Hessian has n strictly distinct eigenvalues, the authors prove that the normalized squared gradient components asymptotically concentrate on the two extreme eigenvectors and alternate between them (Theorem 2.4), derive asymptotic rates for the objective value and gradient norm (Theorems 2.7 and 2.9), and give a bound on the underlying alternation constant (Theorem 2.13). In Section 3, a new stepsize α̃_k is derived from a finite-termination condition in two dimensions and is proved to converge to 1/λ_n along the iterates of any method in the family (Theorem 3.1). The paper then proposes a periodic gradient method that mixes BB steps, the family stepsize, and the new short stepsize, and reports numerical comparisons on random quadratics.

Significance. If the results hold as stated, the paper significantly generalizes the classical Akaike and Forsythe analysis of steepest descent to a broad parametric family and provides explicit asymptotic rate formulas that were previously unavailable for the minimal gradient method. The proofs are detailed and largely self-contained, with hypotheses stated precisely; the new stepsize α̃_k and its spectral limit 1/λ_n are potentially useful tools for breaking the zigzagging pattern. The numerical section is reproducible in design and shows consistent gains over the compared methods. The importance of the contribution is real, but the advertised scope is too broad because the central theorem requires strictly distinct eigenvalues and the proof of Theorem 3.1 glosses over an alternating-parity issue; both are fixable, but they are load-bearing.

major comments (3)
  1. [Section 2, Assumption (2.1) and Theorem 2.4] The paper claims in Section 2 that one can assume 'without loss of generality' that 0 < λ1 < λ2 < ... < λn, but strict distinctness is not a harmless normalization. It is used essentially in Lemma 2.1 to conclude that the Cauchy-Schwarz equality case involves at most two indices with distinct eigenvalues, and in Theorem 2.4 to force the limiting set to be {1,n}. If an extreme eigenvalue is repeated, the conclusion (2.29)-(2.30) fails: for A = diag(1,1,κ) with Ψ(A) = A, the squared components of g_k along the two eigenvectors of eigenvalue 1 keep a constant ratio, so q_k^(2) cannot tend to 0 when g_0^(2) ≠ 0. The abstract's statement that 'each method in the family will asymptotically zigzag between two directions' therefore overstates the proven results. The assumption must either be stated explicitly in the abstract and main claims, or the theory must be extended to an eigenspace-grouped version covering repeated eigenvalues.
  2. [Section 3.2, proof of Theorem 3.1] In the proof of Theorem 3.1, the displayed limits for H^k_11 and H^k_22 are asserted for all k, but H^k_11 uses g_{k-1} and therefore alternates between the limits (2.29) and (2.30) of Theorem 2.4. For example, when Ψ(A) = I and r = 0, H^k_11 takes the two values λ1(1+c^2κ)/(1+c^2) and λ1(c^2+κ)/(1+c^2) on the even and odd subsequences, which are different for c^2 ≠ 1. The displayed algebra appears to compute only one parity; the other parity follows by symmetry, and the final combined limit for α̃_k may still be correct, but the proof as written is incomplete because it does not justify the existence of the individual limits used in (3.16)-(3.18). This gap is load-bearing for the central claim (3.15) and needs a two-subsequence argument.
  3. [Section 3.1, derivation around Eq. (3.7)-(3.8)] The finite-termination derivation divides by Γ and concludes that α1 must satisfy the quadratic equation (3.8), but if Γ = 0 the condition (3.7) imposes no constraint on α1. The degenerate case Γ = 0 occurs when g1 is an eigenvector of A, in which case choosing α1 = 1/λ2 still leads to termination; hence the gap is fixable by a short case distinction. As written, however, the argument that (3.8) follows from (3.7) is not valid in all cases, and the derivation of the new stepsize (3.12) is not fully justified.
minor comments (3)
  1. [Abstract and Theorem 2.4] The abstract and the introduction state the zigzag result without the strict-distinct-eigenvalue condition; the condition should be moved from the proof section to the statements of the main results.
  2. [Section 3.2, proof of Theorem 3.1] The symbol v appears in the displayed formula for lim(H^k_12)^2 ('Ψ^{2+2v}') without ever being defined; it should be r or another explicitly defined exponent.
  3. [Section 3.2, after Eq. (3.14)] The sentence claiming that α̃_k is 'asymptotically be smaller than α_k^SD independent of r' is imprecise because Theorem 3.1 states a limit, not an inequality for finite k; rephrase to avoid suggesting a finite-k comparison.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the zigzag limits and the new stepsize's 1/λ_n convergence are derived from the stepsize definition and spectral assumptions, not assumed as inputs.

full rationale

The paper's central results (Theorem 2.4, Corollaries 2.5–2.6, Theorems 2.7, 2.9, 2.13, and 3.1) are derived from the definition of the stepsize α_k in (1.11), the eigenvalue decomposition of the quadratic, and the stated spectral assumption (2.1). The asymptotic two-index limits in (2.29)–(2.30) are obtained by analyzing the nonlinear map T in (2.8)–(2.9), whose monotonicity (Lemma 2.1) and two-point periodicity (Lemma 2.2) are proved in the paper rather than imported from the conclusion. The convergence of the new stepsize (3.12) to 1/λ_n in Theorem 3.1 is proved by applying the already-established limits (2.29), (2.30), and (2.34) to the expressions for H^k_ij; it does not presuppose the target value. No fitted parameter is renamed as a prediction; the constant c in Theorem 2.4 is characterized, not fitted. The self-citations (e.g., [9], [21]) are contextual and do not carry the proof, and the numerical comparisons are empirical. The strict-eigenvalue assumption (2.1) is a genuine hypothesis — repeated extreme eigenvalues would break the two-vector conclusion — but a limitation on scope is not circularity. No step in the derivation reduces to its own input, so no specific circular reduction can be exhibited.

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

The paper's central theorems rest on: the SPD distinct-spectrum assumption (2.1), nondegenerate initial extreme components (2.28), positivity of Psi on the spectrum, and standard analysis tools. The rate formulas depend on an undetermined constant c that encodes initial conditions. The proposed algorithm has hand-tuned block sizes, and its convergence guarantee is asserted via prior work rather than proved. No new physical or mathematical entities are introduced.

free parameters (3)
  • c (asymptotic ratio mu_n/mu_1 on even iterates) = unspecified; depends on initial point
    Appears in all asymptotic rate formulas (2.40), (2.41), (2.46), (2.47). It is not fitted to data but is an undetermined constant of the initial conditions; Theorem 2.13 bounds it but does not determine it.
  • Algorithm 3.1 parameters (Kb, Km, Ks) = Kb=100 for problem sets 1 and 5, 30 otherwise; Km, Ks chosen from {9,13,15}
    The periodic method's block lengths are tuned on the benchmark problems; the reported superiority is partly due to this tuning.
  • r in the new stepsize (3.12) = r=1/2 in the implemented formula (4.3)
    The stepsize definition depends on r for numerical implementation; r=1/2 is chosen for computational convenience. The asymptotic limit in Theorem 3.1 is independent of r, so this is a design choice rather than a fitted constant.
assumptions (6)
  • domain assumption The Hessian A is symmetric positive definite with strictly ordered distinct eigenvalues, 0 < lambda_1 < lambda_2 < ... < lambda_n (Assumption (2.1)).
    The proof of Theorem 2.4 uses strict ordering to force the limiting pair of indices to be {1,n}; repeated eigenvalues are not analyzed.
  • domain assumption The initial gradient satisfies g0^T xi_1 != 0 and g0^T xi_n != 0 (Assumption (2.28)).
    The zigzag limit and all subsequent rate formulas depend on both extreme eigencomponents being present initially; if one vanishes, the limiting subspace changes.
  • domain assumption Psi is a real analytic function on [lambda_1, lambda_n], expressible as a Laurent series, with 0 < sum c_k z^k < +infinity for all z in [lambda_1, lambda_n].
    This ensures the stepsize (1.11) is positive and the weighted average gamma(p) lies between lambda_1 and lambda_n, which is used throughout Sections 2 and 3.
  • standard math Cauchy-Schwarz inequality and standard spectral/continuity arguments for the transformation T.
    Used in Lemma 2.1 and Lemma 2.3; straightforward background.
  • domain assumption The finite termination construction in Section 3.1 assumes the two search directions Psi^r(A)g0 and Psi^{1-r}(A)g1 are orthonormal in R^2, which follows from (3.1) only when both vectors are nonzero.
    If either vector is zero, the derivation of the stepsize formula (3.9) is not justified; degenerate cases are not discussed.
  • domain assumption The R-linear convergence of Algorithm 3.1 follows from the property in [5] as in Theorem 3 of [7].
    The paper asserts, but does not prove, that the periodic scheme satisfies the convergence property of [5]; this is a gap.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On the asymptotic convergence and acceleration of gradient methods." pith.science (2026). https://pith.science/paper/KWXIJJI5

@misc{pith2026190807111,
  author       = {Pith},
  title        = {Pith review of: On the asymptotic convergence and acceleration of gradient methods},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/KWXIJJI5}},
  note         = {Machine review of arXiv:1908.07111}
}
read the original abstract

We consider the asymptotic behavior of a family of gradient methods, which include the steepest descent and minimal gradient methods as special instances. It is proved that each method in the family will asymptotically zigzag between two directions. Asymptotic convergence results of the objective value, gradient norm, and stepsize are presented as well. To accelerate the family of gradient methods, we further exploit spectral properties of stepsizes to break the zigzagging pattern. In particular, a new stepsize is derived by imposing finite termination on minimizing two-dimensional strictly convex quadratic function. It is shown that, for the general quadratic function, the proposed stepsize asymptotically converges to the reciprocal of the largest eigenvalue of the Hessian. Furthermore, based on this spectral property, we propose a periodic gradient method by incorporating the Barzilai-Borwein method. Numerical comparisons with some recent successful gradient methods show that our new method is very promising.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

32 extracted references · 31 canonical work pages

  1. [5]

    Dai , Alternate step gradient method , Optimization, 52 (2003), pp

    Y.-H. Dai , Alternate step gradient method , Optimization, 52 (2003), pp. 395–415

    work page 2003

  2. [7]

    Y.-H. Dai, Y. Huang, and X.-W. Liu , A family of spectral gradient methods for optimization , Comp. Optim. Appl., 74 (2019), pp. 43–65

    work page 2019

  3. [1]

    Akaike , On a successive transformation of probability distributio n and its application to the analysis of the optimum gradient method , Ann

    H. Akaike , On a successive transformation of probability distributio n and its application to the analysis of the optimum gradient method , Ann. Inst. Stat. Math., 11 (1959), pp. 1–16

    work page 1959

  4. [2]

    Barzilai and J

    J. Barzilai and J. M. Borwein , Two-point step size gradient methods , IMA J. Numer. Anal., 8 (1988), pp. 141–148

    1988

  5. [3]

    E. G. Birgin, J. M. Mart ´ınez, and M. Raydan , Nonmonotone spectral projected gradient methods on convex sets , SIAM J. Optim., 10 (2000), pp. 1196–1211

    work page 2000

  6. [4]

    Cauchy , M´ ethode g´ en´ erale pour la r´ esolution des systemes d’´ equations simultan´ ees, Comp

    A. Cauchy , M´ ethode g´ en´ erale pour la r´ esolution des systemes d’´ equations simultan´ ees, Comp. Rend. Sci. Paris, 25 (1847), pp. 536–538

    work page

  7. [6]

    Dai and R

    Y.-H. Dai and R. Fletcher , On the asymptotic behaviour of some new gradient methods , Math. Program., 103 (2005), pp. 541–559

    work page 2005

  8. [8]

    Dai and L.-Z

    Y.-H. Dai and L.-Z. Liao , R-linear convergence of the Barzilai and Borwein gradient me thod, IMA J. Numer. Anal., 22 (2002), pp. 1–10

    work page 2002

Show all 32 references
  1. [9]

    Dai and X

    Y.-H. Dai and X. Yang , A new gradient method with an optimal stepsize property , Comp. 28 Y. Huang, Y-H, Dai, X-W, Liu and H. ZHANG Optim. Appl., 33 (2006), pp. 73–88

    2006

  2. [10]

    Dai and Y.-X

    Y.-H. Dai and Y.-X. Yuan , Alternate minimization gradient method , IMA J. Numer. Anal., 23 (2003), pp. 377–393

    2003

  3. [11]

    Dai and Y.-X

    Y.-H. Dai and Y.-X. Yuan , Analysis of monotone gradient methods , J. Ind. Mang. Optim., 1 (2005), p. 181

    2005

  4. [12]

    De Asmundis, D

    R. De Asmundis, D. Di Serafino, W. W. Hager, G. Toraldo, and H. Zha ng, An efficient gradient method using the Yuan steplength , Comp. Optim. Appl., 59 (2014), pp. 541–563

    2014

  5. [13]

    De Asmundis, D

    R. De Asmundis, D. di Serafino, F. Riccio, and G. Toraldo , On spectral properties of steepest descent methods , IMA J. Numer. Anal., 33 (2013), pp. 1416–1435

    2013

  6. [14]

    Di Serafino, V

    D. Di Serafino, V. Ruggiero, G. Toraldo, and L. Zanni , On the steplength selection in gradient methods for unconstrained optimization , Appl. Math. Comput., 318 (2018), pp. 176–195

    2018

  7. [15]

    E. D. Dolan and J. J. Mor ´e, Benchmarking optimization software with performance profi les, Math. Program., 91 (2002), pp. 201–213

    2002

  8. [16]

    H. C. Elman and G. H. Golub , Inexact and preconditioned Uzawa algorithms for saddle poi nt problems, SIAM J. Numer. Anal., 31 (1994), pp. 1645–1661

    1994

  9. [17]

    Fletcher , On the Barzilai–Borwein method , Optimization and control with applications, (2005), pp

    R. Fletcher , On the Barzilai–Borwein method , Optimization and control with applications, (2005), pp. 235–256

    2005

  10. [18]

    G. E. Forsythe , On the asymptotic directions of the s-dimensional optimum g radient method, Numer. Math., 11 (1968), pp. 57–76

    1968

  11. [19]

    Frassoldati, L

    G. Frassoldati, L. Zanni, and G. Zanghirati , New adaptive stepsize selections in gradient methods, J. Ind. Mang. Optim., 4 (2008), p. 299

    2008

  12. [20]

    C. C. Gonzaga and R. M. Schneider , On the steepest descent algorithm for quadratic func- tions, Comp. Optim. Appl., 63 (2016), pp. 523–542

    2016

  13. [21]

    Huang, Y.-H

    Y. Huang, Y.-H. Dai, X.-W. Liu, and H. Zhang , Gradient methods exploiting spectral prop- erties, arXiv preprint arXiv:1905.03870, (2019)

    2019 arXiv

  14. [22]

    Huang and H

    Y. Huang and H. Liu , Smoothing projected Barzilai–Borwein method for constrai ned non- Lipschitz optimization , Comp. Optim. Appl., 65 (2016), pp. 671–698

    2016

  15. [23]

    Huang, H

    Y. Huang, H. Liu, and S. Zhou , Quadratic regularization projected Barzilai–Borwein met hod for nonnegative matrix factorization , Data Min. Knowl. Disc., 29 (2015), pp. 1665–1684

    2015

  16. [24]

    Jiang and Y.-H

    B. Jiang and Y.-H. Dai , Feasible Barzilai–Borwein-like methods for extreme symme tric ei- genvalue problems , Optim. Method Softw., 28 (2013), pp. 756–784

    2013

  17. [25]

    Liu, Y.-H

    Y.-F. Liu, Y.-H. Dai, and Z.-Q. Luo , Coordinated beamforming for MISO interference chan- nel: Complexity analysis and efficient algorithms , IEEE Trans. Signal Process., 59 (2011), pp. 1142–1157

    2011

  18. [26]

    Nocedal, A

    J. Nocedal, A. Sartenaer, and C. Zhu , On the behavior of the gradient norm in the steepest descent method, Comp. Optim. Appl., 22 (2002), pp. 5–35

    2002

  19. [27]

    Pronzato, H

    L. Pronzato, H. P. Wynn, and A. A. Zhigljavsky , Asymptotic behaviour of a family of gradient algorithms in Rd and Hilbert spaces , Math. Program., 107 (2006), pp. 409–438

    2006

  20. [28]

    Raydan , On the Barzilai and Borwein choice of steplength for the grad ient method , IMA J

    M. Raydan , On the Barzilai and Borwein choice of steplength for the grad ient method , IMA J. Numer. Anal., 13 (1993), pp. 321–326

    1993

  21. [29]

    Raydan , The Barzilai and Borwein gradient method for the large scale unconstrained minimization problem , SIAM J

    M. Raydan , The Barzilai and Borwein gradient method for the large scale unconstrained minimization problem , SIAM J. Optim., 7 (1997), pp. 26–33

    1997

  22. [30]

    Yuan , A new stepsize for the steepest descent method , J

    Y.-X. Yuan , A new stepsize for the steepest descent method , J. Comput. Math., (2006), pp. 149–156

    2006

  23. [31]

    Yuan , Step-sizes for the gradient method , AMS IP Studies in Advanced Mathematics, 42 (2008), pp

    Y.-X. Yuan , Step-sizes for the gradient method , AMS IP Studies in Advanced Mathematics, 42 (2008), pp. 785–796

    2008

  24. [32]

    B. Zhou, L. Gao, and Y.-H. Dai , Gradient methods with adaptive step-sizes , Comp. Optim. Appl., 35 (2006), pp. 69–86

    2006

Pith tools

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