Source-linked AI summary
$R$-Linear Convergence of Barzilai-Borwein Methods on Strictly Convex Quadratics via Closed-Cone Homogeneous Dynamics
Shutai Yang, Ya-xiang Yuan
TL;DR
BB methods use delayed stepsizes, and proving their R-linear convergence requires controlling all compatible gradient-pair states, not only one trajectory. The paper models these states as a closed cone, upgrades pointwise stability to a uniform rate, and uses spectral conjugacy to show BB1, BB2, and fixed positive spectral-weight rules share a homogeneous growth radius.
Problem
The paper addresses how to prove R-linear convergence for delayed BB rules and fixed positive spectral-weight variants on finite-dimensional strictly convex quadratics.
Source: §1 · p. 1Method
The delayed recurrence is represented on a closed cone of compatible consecutive-gradient pairs, where compactness upgrades pointwise stability to a uniform estimate and spectral conjugacy transfers the rate.
Source: §1 · p. 2Results
BB1, BB2, and fixed positive spectral-weight rules have R-linear convergence and the same homogeneous growth radius.
Source: §3.3 · pp. 6–7, §4 · p. 7Takeaways & Limitations
The proof architecture also applies to finite-memory spectral recurrences whose realizable states form a finite-dimensional closed invariant cone and whose transition is continuous, degree-one homogeneous, and pointwise stable.
Source: §4 · p. 7The compactness theorem is finite-dimensional; in ℓ2, pointwise convergence alone need not yield a uniform R-linear estimate without an additional compactness or uniformity hypothesis.
Source: §2.1 · p. 4
Abstract
from arXiv · showhide
We give an $R$-linear convergence proof for BB1, BB2, and fixed positive spectral-weight variants on finite-dimensional strictly convex quadratics. The delayed recurrence is written as a first-order system on the closed cone of compatible consecutive-gradient pairs. Its transition is continuous and positively homogeneous of degree one, including at finite termination. A compactness theorem shows that pointwise convergence of every cone orbit implies a uniform finite-step contraction and hence a global $R$-linear estimate. By a realization lemma, every compatible state initiates a BB1 trajectory, so Raydan's theorem yields pointwise stability on the entire cone. Finally, the transformation $g\mapsto W^{1/2}g$ conjugates every fixed positive spectral-weight rule to BB1. Consequently, BB1, BB2, and all such weighted rules have the same homogeneous growth radius.
1 Introduction
The introduction presents the one-step delay in BB rules and recasts their dynamics on a cone of compatible consecutive-gradient pairs. It combines a compactness-based rate upgrade with a realization argument for BB1 and spectral conjugacy for weighted rules.
1 Introduction
- The BB stepsize applied to g_k is determined by g_{k-1}, the defining one-step delay.Source: §1 · p. 1
- Prior work established global convergence for both BB choices and R-linear convergence for BB1, with an analogous BB2 conclusion.The related proof strengthens a spectral-component induction into a uniform finite-window estimate.Source: §1 · pp. 1–2
- The analysis augments the state to a pair of consecutive gradients, whose realizable values form a cone.Section 3 also derives estimates for gradient pairs, iterates, and objective gaps.Source: §1 · p. 2
- On this closed, forward-invariant cone, the delayed BB update is continuous even at finite termination and positively homogeneous of degree one.Source: §1 · p. 2
- A compactness principle upgrades pointwise convergence on the cone to a uniform R-linear estimate; realization supplies BB1's pointwise input, and spectral conjugacy transfers the rate to BB2 and fixed positive weights.Source: §1 · p. 2
2 Homogeneous dynamics on closed cones
For continuous, degree-one homogeneous dynamics on a finite-dimensional closed cone, pointwise convergence of every orbit is equivalent to a uniform R-linear estimate. The homogeneous growth radius characterizes this stability and the infimum of admissible rates; the compactness argument does not extend to infinite dimensions without an additional hypothesis.
2 Homogeneous dynamics on closed cones
- Pointwise convergence of every orbit is equivalent to a uniform R-linear estimate for continuous, degree-one homogeneous maps on a closed cone.Compactness of the normalized section and continuity allow local decay bounds to yield a uniform estimate.Source: §2 · pp. 2–3
2.1 The homogeneous growth radius
- The homogeneous growth radius is below one exactly when the equivalent stability conditions hold, and it is the infimum of admissible R-linear rates.Source: §2.1 · p. 4
- In ℓ2, pointwise convergence can hold while every iterate has operator norm one, so no uniform R-linear estimate follows without added compactness or uniformity.Source: §2.1 · p. 4
3 BB dynamics on compatible gradient pairs
The section recasts delayed weighted BB updates as dynamics on compatible consecutive-gradient pairs. A closed-cone compactness argument, together with realization and spectral conjugacy, yields state-uniform R-linear convergence for BB1, BB2, and fixed positive spectral-weight rules.
3 BB dynamics on compatible gradient pairs
- For a positive spectral weight W=ω(H), the weighted delayed recurrence includes BB1 at W=I and BB2 at W=H.The recurrence uses a positive finite first stepsize and zero continuation after termination.Source: §3 · p. 4
3.1 The closed invariant cone
- The compatible-state set Ω_BB(H) is a closed cone, and its transition is a continuous, positively homogeneous self-map.The transition preserves the cone; continuity also holds at the origin.Source: §3.1 · p. 5
3.2 Spectral conjugacy
- Conjugacy and homogeneity provide matching upper and lower growth bounds for the weighted and unweighted transitions.The proof takes kth roots of these bounds to obtain the stated growth comparison.Source: §3.2 · p. 6
3.3 State-uniform 𝑅-linear convergence
- Every compatible state is realized by a warm-up step, making its subsequent delayed weighted trajectory an orbit of the transition map.For BB1, this lets Raydan’s convergence theorem supply pointwise convergence from every cone state.Source: §3.3 · p. 6
- For fixed H, constants C_H and ρ_H∈(0,1) give a uniform 𝑅-linear estimate for every positive spectral weight, including BB1, BB2, and fixed power weights.The corollary also covers arbitrary positive finite first stepsizes, with zero continuation after termination.Source: §3.3 · pp. 6–7
4 Conclusion
The conclusion presents a closed-cone proof architecture that upgrades pointwise stability to a uniform geometric rate, then transfers that rate across fixed positive spectral weights. It also states when the architecture extends to other finite-memory spectral recurrences.
4 Conclusion
- For BB1, pointwise convergence from every compatible state supplies the input that compactness and homogeneity upgrade to a uniform 𝑅-linear rate.Spectral conjugacy transfers the rate to BB2 and fixed positive spectral weights while preserving the homogeneous growth radius.Source: §4 · p. 7
- The proof architecture extends to finite-memory spectral recurrences with realizable states forming a finite-dimensional closed invariant cone and a continuous, degree-one homogeneous transition.Pointwise stability must hold from every cone state.Source: §4 · p. 7
- For classical BB rules, a sharper evaluation of the common growth radius is developed in [8].Source: §4 · p. 7
Declarations
The declarations report funding, author contributions, and use of language models for editing. They also state that no datasets or computational code were used and disclose no relevant competing interests.
Declarations
- The authors report institutional and national funding for the work.Shutai Yang’s support was a national student innovation and entrepreneurship training project; Ya-xiang Yuan’s support was a National Natural Science Foundation of China grant.Source: Declarations · p. 7
- The authors report no relevant competing interests, and no datasets or computational code were generated or used.The paper describes the study as entirely theoretical.Source: Declarations · pp. 7–8
- Shutai Yang conceived and developed the study, analyzed it, and drafted the manuscript; Ya-xiang Yuan guided the research direction and reviewed it.Both authors read and approved the final manuscript.Source: Declarations · p. 8
- Shutai Yang used OpenAI language models for language and LaTeX editing and notation presentation, then independently checked and revised the assisted material.Both authors reviewed and approved the final manuscript and take responsibility for its content.Source: Declarations · p. 8