PaperlayerView exact revision on arXiv

Source-linked AI summary

Superlinear Convergence of Cyclic Gradient Methods with Historical Ritz Step Sizes

Ran Gu

arXiv:2610.32705v1math.OCcs.NAmath.NA

TL;DR

Actual convergence of spectral gradient methods is not fully understood, especially when historical step sizes are applied to gradients changed by intervening updates. The paper analyzes cyclic reuse of historical Ritz step sizes and establishes doubly exponential convergence results for actual iterations under stated conditions.

  • Problem

    Simplified models predict dimension-dependent superlinear convergence, but whether actual iterations exhibit it remains partly unresolved; historical methods add an offset because the gradients defining and receiving step sizes differ.

    Source: §1 · p. 1, §1.2 · p. 2

  • Method

    The paper studies rolling cyclic reuse of historical Ritz values and sampled cyclic reuse, rebuilding the sampling history from a fresh gradient and counting sampling updates as actual updates.

    Source: §2.2 · p. 6, §2.3 · p. 7

  • Results

    At q=m+1, the rolling rule has an exact rate outside explicit exceptional weights; nonempty open basins occur for m+1<q≤2m and ℓ≥4, and the conclusions establish doubly exponential convergence of actual iterations.

    Source: §4.2 · p. 16, §3 · p. 20, §6 · p. 23

  • Takeaways & Limitations

    The finite-menu extension permits history-dependent sampling, while sparse decisions preserve the condition and rate range.

    Source: §6 · p. 23

    The analysis is for quadratics; changing Hessians and noncommuting updates require a separate history-quality analysis.

    Source: §6 · p. 23

Abstract

from arXiv · show

Simplified spectral models predict dimension-dependent superlinear convergence for gradient methods, but the corresponding behavior of actual iterations remains only partially understood. Historical methods introduce an additional difficulty: the gradients defining the step sizes differ from those receiving them. We study this offset for cyclic reuse of historical Ritz step sizes on strictly convex quadratics. Within the existing limited memory steepest descent with retards (LMSDR) family, a rolling cyclic Ritz (RCR) rule reuses $m$ historical Ritz values $\ell$ times per cycle, ending with a complete sweep. At $q=m+1$ active distinct eigenvalues, an exact delayed recurrence gives almost-everywhere doubly exponential convergence with an explicit rate and exceptional weights. Nonempty open basins also exist for $m+1<q\le2m$ and $\ell\ge4$. Rebuilding the history from each cycle-start gradient costs $m$ additional updates and gives sampled cyclic Ritz reuse (SCR) a cycle-end map determined by the current weights. Under uniform sampling bounds, SCR converges doubly exponentially almost everywhere when $(2\ell-1)^m>\binom{q-1}{m}$. Increasing $\ell$ admits larger $q$ for fixed $m$. The guarantee extends to history-dependent choices from finite sampling menus under a bound on the number of admissible sampling sequences. Geometrically spaced decisions retain the SCR condition and rate range. Every update is counted, including sampling; a numerical illustration compares finite-tolerance update counts.

1. Introduction.

Simplified spectral models predict dimension-dependent superlinearity, but whether actual iterations realize it remains a question, especially when historical Ritz steps act on gradients different from those that define them. The paper studies this delay in cyclic limited-memory Ritz reuse and establishes rolling and sampled convergence regimes.

1. Introduction.

  • Changing only the scalar step along the negative gradient can yield faster-than-linear convergence; the two-dimensional Barzilai–Borwein method is a classical example.The paper asks whether dimension-dependent behavior predicted by simplified models describes actual iterations.Source: §1 · p. 1

1.1. Spectral models and their role in step-size design.

  • Simplified recurrences predict superlinear behavior at spectral dimensions of order m² for MLMSD, compared with order m for LMSD.The cited model analyses also relate dimension and cycle length for cyclic steepest descent.Source: §1 · p. 1

1.2. Actual convergence and the historical offset.

  • Historical Ritz steps act on gradients already transformed by intervening updates, so controlling cancellations and changing dominance is necessary beyond tracking spectral ratios.The paper frames this historical offset as the central challenge for connecting relative spectral dynamics to decay of the actual gradient.Source: §1.2 · p. 2
  • The specified rolling cyclic Ritz rule reuses each of m historical reciprocal Ritz values ℓ times and ends with a complete sweep within the LMSDR family.The paper asks whether actual delayed histories yield precise superlinear convergence and whether the mechanism survives competition among more spectral components.Source: §1.2 · p. 2

1.3. Contributions and scope.

  • For each fixed ℓ and q=m+1, an exact doubly exponential rate holds outside explicit exceptional initial weights; for fixed ℓ≥4 and m+1<q≤2m, nonempty open basins exist.Source: §1.3 · p. 3
  • SCR rebuilds its history from the cycle-start gradient, enabling almost-everywhere doubly exponential convergence under a sufficient sampling condition.Finite-menu history-dependent choices and geometrically spaced decisions preserve the SCR condition and rate range.Source: §1.3 · p. 3

2. Historical Ritz extraction and the two algorithms.

The section defines historical Ritz extraction on a strictly convex quadratic and specifies rolling and sampled reuse rules. It also establishes rank-related termination and a bound for transferring cycle-end decay to individual gradient updates.

2.1. Quadratic model and historical Ritz extraction.

  • A full-rank history yields a Krylov subspace, whose compression polynomial is the unique degree-m monic orthogonal polynomial for the historical spectral weights.Its Ritz values lie in the convex hull of the active eigenvalues.Source: §2.1 · pp. 5–6

2.2. Rolling cyclic Ritz reuse: the specified LMSDR rule.

  • RCR reuses each of m historical reciprocal Ritz values ℓ times, with a complete sweep at the cycle end fixing the next history.The preceding m(ℓ−1) updates may be ordered arbitrarily; the rule assumes uninterrupted cycles and the specified final sweep.Source: §2.2 · p. 6, §2.1 · p. 6

2.3. Sampled cyclic Ritz reuse.

  • SCR rebuilds its history with m updates from the cycle-start gradient, then reuses the extracted reciprocals ℓ times.Its cycle-end map depends on the current spectral weights, and sampling updates count toward the iteration total.Source: §2.3 · p. 7

2.4. Rank and transfer to actual gradient updates.

  • If the effective active Krylov space is invariant and has dimension r≤m, its r Ritz values are all active eigenvalues, so one reciprocal sweep annihilates the gradient.Rank m alone does not guarantee invariance.Source: §2.4 · pp. 7–8
  • A cycle-end doubly exponential bound transfers to intervening gradients when each interval contains a fixed number of Ritz updates and every update is bounded by M.The transfer uses forward propagation and requires no inverse-update bound.Source: §2.4 · p. 8
  • The exactly solvable case q=m+1 retains the historical delay and yields an explicit fixed-count rate with exceptional initial weights.The analysis connects growth of the complete logarithmic state to decay of every original gradient component.Source: §2.4 · p. 8

3. Exact delayed convergence when q = m + 1.

For q=m+1 with full initial support, RCR admits exact delayed dynamics for relative spectral weights. Except for a Lebesgue-null set of initial points, the actual gradients and iterate errors converge at the theorem’s stated rate.

3. Exact delayed convergence when q = m + 1.

  • For ℓ≥3, the subdominant characteristic root is µs=−2/σℓ, while ℓ=3 gives µs=−1.For ℓ=1,2, the roots instead form a nonreal conjugate pair of modulus 2.Source: §3 · p. 9
  • Except for a Lebesgue-null set of full-support initial points, the complete actual gradient sequence and iterate errors satisfy the theorem’s asymptotic rate.For ℓ=1,2, the stated exceptional state is w0=w−1=0; for ℓ≥3, it is the dominant-mode cancellation condition.Source: §3 · pp. 9–10
  • The proof recovers decay of every gradient component by summing componentwise logarithmic losses from the complete ratio-state growth.This yields the rate for all actual updates, including the first update’s fixed initialization term.Source: §3 · p. 10

4. Open convergence basins for m + 1 < q ≤2m.

For ℓ≥4, structured initial conditions yield open basins of actual doubly exponential convergence across m+1<q≤2m. The proofs use uniform filter bounds and recurrences to preserve alternating dominance and establish gradient decay.

4.1. Separated dominant sets at q = 2m.

  • At q=2m and ℓ≥4, sufficiently separated initial spectral groups with bounded within-group spread form a nonempty open basin of RCR trajectories with the exact doubly exponential rate.The same result holds with the two groups interchanged.Source: §4.1 · p. 11

4.1.1. Uniform filter estimates.

  • A weight-uniform two-group filter bound controls the Ritz filters when one spectral group dominates the other, without requiring bounds on within-group weight ratios.The bound also ensures every active filter value is nonzero.Source: §4.1.1 · p. 11

4.1.2. Forced recurrences and separation.

  • Under alternating group dominance, the intergroup gap follows Dk+1=aDk−2Dk−1+Ek, while the forcing is controlled by within-group spread.The spread grows at a slower scale than the gap when ℓ≥4, allowing sufficient initial separation to persist.Source: §4.1 · p. 10, §4.1.2 · pp. 12–13

4.1.3. Continuation and gradient decay.

  • A first-failure argument preserves the separated ordering, and accumulated componentwise filter losses then give the exact rate for all actual updates.The initial conditions are strict and feasible, so the basin is open and has positive measure.Source: §4.1.3 · pp. 13–14

4.2. Overlapping dominant sets for m + 1 < q < 2m.

  • For m+1<q<2m and ℓ≥4, overlapping alternating dominant sets also yield a nonempty open basin with the exact doubly exponential rate.The proof controls shared components’ log-amplitude offsets relative to the intergroup gap; the initial inequalities are feasible and persist.Source: §4.2 · pp. 14, 16
  • These constructions establish actual doubly exponential convergence for m+1<q≤2m only under explicitly structured initial conditions, not almost everywhere.The paper changes the gradient used to define the historical Ritz polynomial to seek a general-dimensional guarantee.Source: §4.2 · p. 16

5. Changing the history construction: a general-dimensional guarantee.

Theorem 5.1 gives a general-dimensional convergence guarantee for SCR under a combinatorial sufficient condition and prescribed sampling bounds. Its proof combines the cycle-start weight map, inverse-branch volume estimates, and control of near-cancellation losses.

5. Changing the history construction: a general-dimensional guarantee.

  • SCR uses the cycle-start gradient to define the Ritz polynomial, yielding a current-weight logarithmic map followed by a bounded translation.The rolling recurrence instead retains the preceding filter, so its state is not described by current weights alone.Source: §5 · pp. 16–17, §5.1 · p. 18
  • Theorem 5.1 gives an almost-everywhere convergence guarantee for SCR under a combinatorial sufficient condition and the stated prescribed-sampling assumptions.The corresponding iterates converge R-superlinearly to x∗.Source: §5 · pp. 16–17

5.1. Constant Jacobian and the exact number of inverse branches.

  • The nonannihilating map has a constant Jacobian and inverse branches associated with choosing distinct spectral gaps for the old polynomial’s roots.Each inverse branch has absolute Jacobian (2ℓ−1)^−m.Source: §5.1 · pp. 17–18

5.2. A sublevel estimate for exponential polynomials.

  • A coefficient-uniform sublevel estimate bounds the volume of near-cancellation sets, with constants independent of other coefficients and box position.The bound is vold{y in the box : |F(y)| < ϵ} ≤ Cϵ^(1/d)L^(d−1).Source: §5.2 · p. 18

5.3. Componentwise loss and Borel–Cantelli.

  • The proof excludes exact-annihilation states and tracks bad-loss events to control cumulative component losses.It uses normalized weights and near-cancellation sublevel sets in the loss argument.Source: §5.3 · p. 19

2. Confinement away from near cancellation.

The section bounds downward excursions by controlling near-cancellation events. It uses large normalizing monomials and places trajectories in a box where sublevel estimates apply.

2. Confinement away from near cancellation.

  • On the event of insufficient reference loss, the recurrence prevents upward escape and bounds downward excursions within a controlled box.The box is BN = [−VN, UN]^d with side length O(Ne^(κN)).Source: §2 · pp. 19–20
  • A sufficiently large normalizing monomial converts a lower bound on the cancellation polynomial into a lower bound on the filter value.The bound is expressed as log |bπk(βi)| ≥ −bN − (m−1)WN − mUN − C.Source: §2 · p. 20
  • The bad-event set includes every admissible cancellation polynomial, so the first near-cancellation event is captured by the sublevel-set bound.If no such event occurs during the first N steps, the state remains in BN at time N.Source: §2 · p. 20

3. Summable bad-event volumes.

The argument makes bad-event volumes summable and applies Borel–Cantelli to obtain almost-everywhere component loss growth. The resulting endpoint gradients decay doubly exponentially.

3. Summable bad-event volumes.

  • For d > 1, both bad-event volume terms are summable; for d = 1, the sublevel sets are empty and the first term suffices.This closes the bad-event estimate used in the argument.Source: §3 · p. 20
  • Borel–Cantelli yields cumulative loss exceeding every fixed multiple of e^(κN) for almost every initial log-ratio state.The argument applies to every reference component and to a countable sequence of κ values approaching κ0.Source: §3 · p. 20
  • The proof lifts the resulting full-measure statement from log-ratio coordinates to the full initial-point space.The lift uses block polar coordinates and Fubini.Source: §3 · p. 20

4. From component losses to actual gradients.

The component-loss estimates yield bounds for actual gradients across every update, including sampling steps. The section also extends the guarantee to history-dependent finite-menu choices under a word-count condition.

4. From component losses to actual gradients.

  • The endpoint component-loss estimate gives doubly exponential decay for actual gradients, including intermediate sampling and Ritz updates.Each update has uniformly bounded norm, allowing endpoint bounds to transfer across a cycle.Source: §4 · p. 20
  • The prescribed-schedule theorem requires sampling steps to be independent of the trajectory; general continuously varying adaptive sampling is not covered.When steps depend on z, the derivative includes Dδk, which condition (5.1) alone does not control.Source: §4 · p. 20

5.4. Adaptive choices from a finite sampling menu.

  • Finite-menu history-dependent sampling is quantified by the exponential growth of admissible list words, without assuming a differentiable selection rule.The allowed decision times are fixed in advance, and the lists share common sampling bounds.Source: §4 · p. 21, §5.4 · p. 21
  • Under the word-count condition h + log ρ < 0, a common full-measure set retains doubly exponential convergence for the permitted sampling choices.The theorem gives separate sufficient conditions for choosing freely each cycle and for choosing once every J cycles.Source: §5.4 · p. 21

3. Choosing at the prescribed cycle indices 0, 1, 2, 4, 8, . . .

The finite-menu extension permits history-dependent sampling choices under a bound on admissible sequences, with geometrically spaced decisions preserving the SCR condition and rate range. A finite-tolerance illustration compares SCR and RCR update counts, with outcomes depending on configuration.

3. Choosing at the prescribed cycle indices 0, 1, 2, 4, 8, . . .

  • Holding the last choice between decisions preserves both the condition and the rate range of Theorem 5.1; the illustrated SCR policy reselects at cycles 1, 2, 4, 8, . . . .Source: §3 · p. 21, §5.5 · p. 22
  • A finite menu supports history-dependent sampling when the number of admissible sampling sequences is bounded, and sparse decisions preserve the original asymptotic rate bound.For q = 5, m = 2, ℓ = 3, arbitrary choices between two safe lists are covered when 2ρ < 1; a sparse schedule requires no loss in the rate bound.Source: §3 · pp. 21–22

5.5. A finite-tolerance illustration of SCR.

  • On 100 paired problems, SCR reached tolerance on all; it used fewer updates on 68, tied on three, and used more on 29.The benefit depends on (m, q, ℓ), and floating-point rank loss or invalid Ritz extraction can stop a run before tolerance.Source: §5.5 · pp. 22–23

6. Conclusions.

The conclusions establish doubly exponential convergence results for actual gradient iterations under specified rolling and sampled rules. They also identify open questions on basin prevalence, spectral range, sampling, and extensions beyond quadratics.

6. Conclusions.

  • Accounting for historical offset yields doubly exponential convergence of actual gradient iterations, with explicit rolling results at q = m + 1 and nonempty open basins for m + 1 < q ≤ 2m when ℓ ≥ 4.SCR converges almost everywhere under its stated combinatorial condition.Source: §6 · p. 23
  • Finite-menu sampling permits history-dependent choices under a bound on admissible sequences, while geometrically spaced decisions preserve the SCR condition and rate range.For fixed m, increasing ℓ admits larger q; both rules use gradients and stored step lengths without additional Hessian–vector products.Source: §6 · p. 23
  • Open questions include rolling-basin prevalence, a rolling dimension condition that grows with repetition, and superlinear behavior beyond q = 2m.Sampling design, finite-precision historical Ritz extraction, and changing Hessians or noncommuting updates also require further analysis.Source: §6 · p. 23

Appendix A. Constants for separated and overlapping basins.

Appendix A makes the basin estimates explicit using finite subset sums and recurrence bounds. It derives constants for separated and overlapping spectral groups and yields finite-time bounds from the first anchor.

Appendix A. Constants for separated and overlapping basins.

  • For separated or overlapping groups, the appendix defines positive filter constants from the set K and its complement L; it does not require |L| = m.The fixed spectrum is used for analysis, while the gradient-only implementation does not require individual eigenvalues.Source: Appendix A · p. 23
  • The normalized-filter estimates use positive lower and upper multiplicative constants, with the one-sided estimate also verified for the overlapping construction.The bounds compare leading terms with remainders controlled by the strong-to-weak weight ratio.Source: Appendix A · pp. 23–24
  • The appendix provides a conservative explicit threshold D*(s) = 1 + max{2Cd(s + 1), 8Cs(s + 1), 4Γ*}, yielding finite-time bounds from the first anchor.The constants are built from recurrence and gap-forcing estimates.Source: Appendix A · p. 24
  • For overlapping sets, the common-component update is bounded by |Fi,k| ≤ Ce(S0 + 1)ν^k, using the same Ce as the outer-gap estimate.The resulting common-displacement bound uses Cd = CeCf/(σ − ν).Source: Appendix A · p. 24
Loading 2610.32705v1…