PaperlayerView exact revision on arXiv

Source-linked AI summary

Global and Unconditional $R$-Linear Convergence of Rank-Compressed Weighted LMSD Sweeps for Strictly Convex Quadratics

Shutai Yang, Ya-xiang Yuan

arXiv:2609.12114v1math.OCcs.NAmath.NA

TL;DR

At rank-changing limits, convergence of normalized block-start gradients alone does not control all Ritz values when the prescribed dimension exceeds the limiting Krylov rank. The paper represents the complete-sweep multiplier with fixed spectral templates and uses endpoint-map compactness to establish uniform R-linear estimates.

  • Problem

    At rank-changing limits, normalized block-start gradient convergence alone does not control all Ritz values when the prescribed dimension exceeds the limiting Krylov rank.

    Source: §2.4 · p. 8

  • Method

    The complete-sweep multiplier is represented through fixed spectral templates with nonnegative state-dependent weights, and consecutive endpoints form a continuous positively homogeneous map on the compatible-state cone.

    Source: §1 · p. 2, §12 · p. 25

  • Results

    Endpoint R-linear estimates are uniform over compatible initial states and extend to inner gradients, iterate errors, objective gaps, and matrices with repeated eigenvalues.

    Source: §12 · p. 25

  • Takeaways & Limitations

    Every fixed positive spectral weight shares the standard method's admissible decay factor, including harmonic-Ritz LMSD, fixed power weights, and delayed BB1 and BB2 recurrences.

    Source: §1 · p. 3, §12 · p. 25

    The analysis is limited to strictly convex quadratics in exact arithmetic with algebraic rank compression and fixed positive spectral weights.

    Source: §12 · p. 25

Abstract

from arXiv · show

We study limited memory steepest descent (LMSD) with exact algebraic rank compression for strictly convex quadratic optimization. At each cycle, the method restricts the gradient history to its column space and applies the reciprocals of all Ritz values of the compressed projection in the next sweep. If the block-start gradient has at most $p$ active distinct eigenvalues, the delayed sweep terminates finitely. For nonterminating trajectories, a determinant and Cauchy--Binet formula for the complete-sweep polynomial yields global convergence without a full-rank history or a run-wise normalized-conditioning bound. Consecutive sweep endpoints define a continuous positively homogeneous map on a closed cone of compatible states. Compactness then gives an $R$-linear endpoint estimate, uniform over compatible initial states, with constants depending only on $H$ and $p$; the estimate extends to inner gradients, iterate errors, and objective gaps. Every fixed positive spectral weight $W=\omega(H)$ is linearly conjugate to the standard method. The weighted methods therefore share its decay factor, while the Euclidean-norm prefactor is increased by at most $\sqrt{\kappa_2(W)}$. This includes harmonic-Ritz LMSD, fixed power weights, and the delayed BB1 and BB2 recurrences.

1. Introduction.

The paper analyzes exact rank-compressed LMSD sweeps and establishes global convergence and a state-uniform R-linear endpoint rate for strictly convex quadratics. It also extends the rate to fixed positive spectral weights by conjugacy, while identifying limitations in earlier analyses and a gap in a prior proof.

Method distinction

  • Unlike methods that select and reuse one admissible candidate, the update applies every value of the algebraically compressed pencil once in the following sweep, including when algebraic history rank changes.The paper contrasts this rule with the candidate-selection approaches in [9] and [12].Source: §1 · p. 2

Main results

  • If a completed history starts from a gradient with at most p active distinct eigenvalues, the compressed projection recovers that spectrum and the following delayed sweep terminates finitely.The rule covers both full-rank and rank-deficient termination strata.Source: §1 · p. 2

Motivation and prior analyses

  • A three-dimensional example disproves the fixed-length Ritz lower-bound implication used in Fletcher’s equation (36), leaving that proof step incomplete without an orbit-specific nondegeneracy argument.The paper’s exact-arithmetic analysis avoids the full-rank history and run-wise normalized-conditioning assumptions used in earlier rate analyses.Source: §1 · p. 2

Main results

  • A determinant ratio and Cauchy–Binet expansion represent the complete-sweep multiplier through fixed spectral templates, yielding pointwise global convergence across changes in Krylov rank.The approach uses complete-sweep multipliers rather than relying on individual Ritz roots.Source: §1 · p. 2

Rate interpretation

  • The actual-run rate is initialized at the start/end pair of the first completed sweep after warm-up; a bound relative to the original gradient would also depend on warm-up stepsizes.The transferred estimates cover fixed positive spectral weights and extend to inner gradients, iterate errors, and objective gaps.Source: §1 · p. 3

2. Rank-compressed LMSD sweeps and spectral conjugacy.

The section reduces quadratic gradient histories to active spectral coordinates, then defines delayed LMSD sweeps using compressed history spaces and their Ritz values. It shows that fixed positive spectral weights are conjugate to the standard method and characterizes when rank compression yields finite termination.

2.1. Active spectral reduction.

  • The active spectral reduction places the trajectory in the invariant subspace supported by the initial gradient, where the restricted Hessian is diagonal with distinct eigenvalues.Every generated gradient is a polynomial in H applied to the initial gradient.Source: §2.1 · pp. 3–4

2.2. History blocks and the delayed LMSD sweep.

  • A history block spans the Krylov space generated by its block-start gradient, and the standard method applies the reciprocals of its positive Ritz values as stepsizes in the following sweep.The history rank sets the delayed sweep length; algebraic compression uses the rank of the history rather than its nominal length.Source: §2.2 · pp. 4–5

2.3. Fixed spectral weights and conjugacy.

  • A fixed positive weight W=ω(H) gives a trajectory conjugate to the standard rank-compressed trajectory under S=W^1/2, with identical extracted values, sweep lengths, and finite-termination indices.The weighted method’s convergence bounds transfer back with an explicit norm-equivalence factor.Source: §2.3 · pp. 5–6

2.4. Support, Krylov rank, and finite termination.

  • The history rank is min{p,s(u)}; support above p is the regular branch, while support at or below p leads to finite termination by the next sweep.On a nonterminating run, completed histories have rank p and block-start gradients have support greater than p.Source: §2.4 · pp. 6–8
  • For a block-start gradient with d≤p active eigenvalues, the compressed standard projection recovers those eigenvalues and the delayed sweep annihilates its endpoint in at most d steps.The same finite-termination result holds for every fixed positive spectral weight.Source: §2.4 · p. 7
  • At rank-changing limits, convergence of normalized block-start gradients alone does not control every Ritz value when the prescribed projection dimension exceeds the limiting Krylov rank.The section identifies this as the issue isolated by its counterexample to the lower-bound step in Fletcher’s proof.Source: §2.4 · p. 8

3. Fixed-length Ritz continuity at Krylov-rank loss.

At Krylov-rank loss, the limiting Ritz values need not match the continuity inference used in Fletcher’s argument. The example motivates analyzing complete-sweep multipliers instead of ordered Ritz tuples.

3. Fixed-length Ritz continuity at Krylov-rank loss.

  • For H = diag(1, 2, 3) and p = 2, q_epsilon tends to e3 while the Krylov subspace tends to span{e1, e3} and the Ritz values tend to (3, 1).The limiting generalized Ritz values are also (3, 1) for every fixed positive spectral weight.Source: §3 · pp. 8–9
  • At this rank-changing limit, the smaller prelimit Ritz value tends to 1, below (2/3)lambda_3 = 2, so the ordered-Ritz inference in Fletcher’s equation (36) does not follow from the stated information.Recovering that conclusion requires an orbit-specific constant-rank or quantitative nondegeneracy argument excluding such paths.Source: §3 · p. 9
  • The convergence proof avoids ordered-Ritz continuity by using the complete-sweep multiplier, whose determinant and Cauchy–Binet representations remain suitable at rank-changing limits.The example uses H = diag(1, 2, 3), p = 2, and q_epsilon = (epsilon, epsilon^2, 1)^T / sqrt(4 + epsilon^2).Source: §3 · pp. 8–9

4. Determinant representation of a complete sweep.

The section represents a complete sweep through its multiplier and develops a formula suited to histories whose Krylov structure can approach rank loss. Spectral enclosure and a convex-weight identity support the convergence argument.

4. Determinant representation of a complete sweep.

  • For the regular tail of a nonterminating run, the support stabilizes after finitely many blocks and contains more than p active components.The analysis reduces to that invariant subspace, with n > p and all active components nonzero.Source: §4 · p. 9

4.1. Spectral enclosure.

  • The standard projected matrix has eigenvalues enclosed by the spectrum of H, by the min–max principle.The supplied passage states the enclosure result but does not give its endpoints.Source: §4.1 · p. 10

4.2. The complete-sweep multiplier.

  • For each spectral index r, the multiplier value ψ_k(λ_r) is a convex combination of fixed real numbers ϕ^(r), supporting the spectral induction.The section combines the multiplier proposition with a scalar tail lemma.Source: §4.2 · pp. 10–11
  • The matrix Kk = [gk, Hgk, . . . , Hp−1gk] = DkV; under (2.5), each ∆I is a nonzero Vandermonde determinant, and dividing (4.10) by (4.9) yields (4.8).The same algebraic Cauchy–Binet expansion gives the numerator.Source: §4.2 · pp. 10–11

5. Global convergence.

The method either terminates finitely or converges globally to the quadratic’s unique minimizer. The proof treats a regular tail of nonterminating runs, and fixed positive spectral weights retain the pointwise convergence conclusion.

5. Global convergence.

  • The method either reaches g = 0 in finitely many steps or, if it does not terminate, sweep-start gradients, inner gradients, and iterates converge to zero.In the original variables, every iterate converges to the unique minimizer.Source: §5 · p. 12
  • On a nonterminating run, every post-warm-up block has length p and every block-start gradient has more than p active components.The convergence proof works on this regular tail.Source: §5 · p. 12
  • The spectral induction combines a two-step bound with a trigger condition for the scalar tail lemma to establish convergence of the active components.The recurrence supplies the bound with M = B^p, and the proof verifies the trigger implication for each epsilon > 0.Source: §5 · pp. 12–13
  • Every fixed positive spectral weight W = ω(H) has the same finite-termination alternative and pointwise convergence conclusions.The weighted trajectory is identified with a standard trajectory for the same Hessian.Source: §5 · p. 14

6. Endpoint-state formulation.

Consecutive sweep endpoints are represented as compatible pairs in a closed-cone state space. The endpoint update is continuous, with termination handled at the rank-boundary cases.

6. Endpoint-state formulation.

  • The state space Ω_p(H) consists of endpoint pairs (u, v) with v = q(H)u for some q in Q_p(H), and contains every consecutive endpoint pair of a nonterminating sweep.It serves as the state space for the rate analysis.Source: §6 · p. 14
  • For s(u) = p, the columns of K_p(u) span the active invariant subspace, so the projected values are exactly the active eigenvalues.Consequently, Ψ_u(H)v = 0 for compatible pairs in this case.Source: §6 · p. 15
  • When s(u) = p, the projected values are the active eigenvalues and the endpoint output Ψ_u(H)v is zero; when s(u) < p, exact compression returns the active eigenvalues and the following effective sweep terminates.The cases s(u) > p, s(u) = p, and s(u) < p are the regular branch and the two termination boundaries, respectively.Source: §6 · pp. 14–15
  • The endpoint map T_p is a continuous self-map of Ω_p(H).The cone formulation supplies the setting for the uniform R-linear estimate.Source: §6 · p. 15

7. A compactness principle for homogeneous dynamics.

For a continuous, positively homogeneous map on a closed cone, pointwise convergence of iterates to zero implies a uniform geometric bound over the cone. Compactness of the normalized state set supplies a finite-step contraction, which yields the bound for every iterate.

7. A compactness principle for homogeneous dynamics.

  • If T^k(x)→0 for every x∈Ω, then there exist C≥1 and ρ∈(0,1) such that ∥T^k(x)∥≤Cρ^k∥x∥ for all x∈Ω and k≥0.T is positively homogeneous of degree one: T(tx)=tT(x) for t≥0 and x∈Ω.Source: §7 · p. 15
  • Compactness of the normalized cone section lets a finite subcover turn pointwise decay into a common finite-step contraction.Each normalized state has a neighborhood where some iterate contracts by a factor below one; finitely many such neighborhoods give a uniform bound on the required iterate length.Source: §7 · pp. 15–16
  • The proof applies these contractions at successive stages, with each stage using an iterate length bounded by N0, to obtain the bound for arbitrary k.It yields C = max{1, 2L} and ρ = 2^(−1/N0).Source: §7 · p. 16

8. Compatible endpoint cone and boundary continuity.

Compatible endpoint states form a closed cone preserved by the positively homogeneous transition. Cauchy–Binet coordinates support continuity of the endpoint map, including at finite-termination and rank-changing boundaries.

8.1. Cone properties and the endpoint self-map.

  • The compatible-state set Ωp is a closed cone, and the transition Tp maps it into itself while scaling both endpoint components linearly.The compatibility condition is v = q(H)u for a polynomial q in Qp.Source: §8.1 · pp. 16–17

8.2. Cauchy–Binet coordinates.

  • For regular states, normalized Cauchy–Binet coefficients are nonnegative and sum to one.The coefficients are indexed by p-element subsets; the denominator is positive when the active support has more than p elements.Source: §8.2 · p. 17

8.3. Continuity across the finite-termination strata.

  • The endpoint map Fp and transition Tp are continuous, including at the full-rank finite-termination boundary and rank-changing boundaries.The proof treats regular limits and the finite-termination strata separately, showing the outputs converge to the corresponding endpoint.Source: §8.3 · pp. 17–18
  • At a full-rank finite-termination boundary, the limiting endpoint is zero; at lower-rank boundaries, the regular subsequence also converges to zero.The proof uses vanishing factors on active coordinates and bounds for coordinates outside the active support.Source: §8.3 · pp. 18–19
  • Continuity of Fp gives continuity of Tp because its first component is the continuous map (u, v) ↦ v.The argument establishes sequential continuity by covering all four possible limit-state cases.Source: §8.3 · p. 19

9. Global R-linear convergence.

The paper establishes pointwise global convergence for the rank-compressed sweep and a state-uniform R-linear endpoint estimate. Fixed positive spectral weights inherit the standard decay factor through conjugacy, with bounds extending to inner gradients, iterate errors, and objective gaps.

9.1. Pointwise convergence input.

  • The algorithmic and abstract endpoints agree until termination: if s(u0)>p, the next endpoint is Ψu0(H)u1; if s(u0)≤p, Proposition 2.5 gives the zero output prescribed by Fp.Source: §9.1 · p. 20

9.2. The standard rank-compressed method.

  • For fixed H and p, every compatible initial state has a uniform R-linear endpoint estimate, with constants depending only on H and p.Finite termination is included by extending endpoint sequences with zeros.Source: §9.2 · p. 20

9.3. Fixed spectral weights by conjugacy.

  • The weighted and standard endpoint maps are conjugate, with matching sweep polynomials, orbit structure, Krylov ranks, and finite-termination indices.The conjugacy preserves active support and both finite-termination strata.Source: §9.3 · pp. 20–21
  • Every fixed positive spectral weight shares the standard decay factor, with Euclidean-norm prefactor increased by at most sqrt(kappa_2(W)).The estimates also cover inner gradients, iterate errors, and objective gaps, and remain valid for repeated eigenvalues.Source: §9.3 · p. 21, §9.4 · p. 22

10. Special cases and relation to earlier analyses.

The results cover standard and harmonic-Ritz LMSD, fixed power weights, and delayed BB1 and BB2 recurrences. These cases share the standard endpoint decay factor, while weighted Euclidean-norm prefactors depend on the weight's condition number.

10. Special cases and relation to earlier analyses.

  • Standard Ritz LMSD, harmonic-Ritz LMSD, fixed power weights, and delayed BB1 and BB2 recurrences all admit the standard endpoint decay factor.The BB recurrences correspond to p = 1; weighted prefactors are bounded by condition-number factors.Source: §10 · p. 23
  • Earlier finite-cycle contraction bounds for standard and harmonic-Ritz LMSD use a normalized-conditioning parameter, whereas this analysis uses compatible states and algebraic rank compression.The resulting rate transfers to fixed positive spectral weights by conjugacy.Source: §10 · p. 23
  • For W = I, the determinant representation also recovers Fletcher’s global-convergence result.Source: §10 · p. 23

11. Numerical diagnostics.

The repeated-spectrum experiment compares seven power weights and tracks objective gaps and history conditioning. All weights reach the prescribed gradient tolerance in 231–280 steps, while the histories illustrate that full rank alone does not bound normalized conditioning.

11. Numerical diagnostics.

  • The experiment uses p = 5 and twenty distinct eigenvalues, each with multiplicity three, giving an unreduced dimension of N = 60.The initial gradient has nonzero projection onto every eigenspace.Source: §11 · pp. 23–24, Figure 1 · p. 24
  • 231–280 gradient steps: all seven weights reach the prescribed gradient tolerance, despite strongly nonmonotone objective histories with substantial transient growth.The overall logarithmic-scale decay is consistent with the global R-linear result.Source: §11 · pp. 24–25
  • Rank five alone provides neither a moderate nor an a priori bound on normalized history conditioning.The diagnostics compare standard and harmonic runs; similar or larger values had also been reported by Curtis and Guo [2, Table 1].Source: §11 · p. 25

12. Conclusions and limitations.

Consecutive endpoints yield a continuous positively homogeneous map on the compatible-state cone, and compactness gives a uniform endpoint R-linear estimate. The results cover repeated eigenvalues and fixed positive spectral weights, but are limited to exact-arithmetic strictly convex quadratics with algebraic rank compression.

12. Conclusions and limitations.

  • Endpoint estimates extend to inner gradients, iterate errors, and objective gaps, including for matrices with repeated eigenvalues.Fixed positive spectral weights share the standard decay factor, with Euclidean-norm prefactor increased by at most sqrt(kappa_2(W)).Source: §12 · p. 25
  • The analysis assumes exact arithmetic, strictly convex quadratics, algebraic rank compression, and fixed positive spectral weights; numerical thresholds, trajectory-dependent weights, and nonquadratic extensions remain open.Source: §12 · p. 25
Loading 2609.12114v1…