Chebyshev-Exact Acceleration under Hessian Variation, I: Sine-Jacobi Method

Technical Summary: Chebyshev-Exact Acceleration under Hessian Variation, I: Sine-Jacobi Method

1. Problem Statement

The paper addresses a fundamental limitation in the analysis of accelerated gradient methods for strongly convex optimization. Classical Chebyshev acceleration is designed to minimize the terminal residual polynomial $p_N(\lambda)$ over a fixed spectral interval $[\mu, L]$. While this ensures optimal convergence rates for static Hessians, it does not uniquely specify the ordered realization (the sequence of gradient updates) that implements this polynomial.

The authors investigate the behavior of these methods under time-dependent Hessian perturbations (Hessian drift). Specifically, they study finite-horizon, one-gradient realizations where the Hessian varies as $H_s = H + \delta B_s$. The central problem is that two methods may share the same terminal Chebyshev polynomial (and thus identical performance on fixed Hessians) but exhibit vastly different sensitivities to multiplicative spectral perturbations. The paper seeks to quantify this sensitivity via a "first-order Hessian-drift gain" and to find a realization that minimizes this gain while maintaining terminal exactness.

2. Methodology and Theoretical Framework

First-Order Drift Gain ($A_N$):
The authors define a realization-level invariant, the sharp $\ell_2$-operator norm of the first variation of the output map with respect to Hessian insertions. For a perturbation mapping the $\nu$-eigenspace to the $\lambda$-eigenspace at time $s$, the propagation is governed by a time-ordered spectral kernel $K_s(\lambda, \nu)$. The gain is defined as:
$$A_N = \sup_{\lambda, \nu \in [\mu, L]} \left( \sum_{s=0}^{N-1} |K_s(\lambda, \nu)|^2 \right)^{1/2}$$
This quantity measures the worst-case amplification of Hessian noise over the finite horizon.

Realization Classes:
The study compares two classes of two-term recurrences that are "Chebyshev-exact" (i.e., they produce the optimal minimax polynomial $p_N^*(\lambda) = T_N(z(\lambda))/T_N(\eta)$ at the final step):

1. Prefix-Exact Chebyshev: The standard recurrence where the residual polynomial is Chebyshev-exact at every intermediate step $t < N$.
2. Terminal-Exact Jacobi: A broader class where exactness is required only at the terminal step $N$. This class is parametrized using Jacobi coordinates (spectral weights on fixed Chebyshev nodes).

The Sine-Jacobi Construction:
Within the terminal-exact class, the authors identify a specific realization by imposing persymmetry (reversal symmetry) on the endpoint Green profile. This leads to a specific choice of spectral weights proportional to $\sin((2j-1)\pi/2N)$, termed the Sine-Jacobi method. The authors derive the explicit recurrence coefficients for this method and analyze its asymptotic drift gain.

3. Key Contributions and Results

Theoretical Bounds:

• Prefix-Exact Gain: For the standard prefix-exact Chebyshev recurrence, the authors derive an exact formula for the drift gain:
  $$A_N^{\text{pref}} = \frac{\epsilon_N^*}{L-\mu} \left( 4N^2 + 16 \sum_{m=1}^{N-1} m^2 \right)^{1/2} \sim \frac{4}{\sqrt{3}} \frac{N^{3/2}}{L-\mu} \epsilon_N^*$$
  They prove this is the sharp lower bound for any causal two-term recurrence that is Chebyshev-exact at every prefix.
• Sine-Jacobi Gain: For the Sine-Jacobi realization, which is only terminal-exact, the gain is:
  $$A_N(J_N^{\text{sin}}) = 2\sqrt{c_{\text{sin}}} \frac{N^{3/2}}{L-\mu} \epsilon_N^* (1 + o(1))$$
  where $2\sqrt{c_{\text{sin}}} \approx 2.1379$.
• Comparison: The Sine-Jacobi method achieves a strictly smaller drift gain than the prefix-exact method ($2.1379 < 4/\sqrt{3} \approx 2.3094$). This demonstrates that the terminal Chebyshev polynomial does not determine the first-order Hessian-drift gain; the ordering of the realization matters.

Experimental Validation:
The authors validate these theoretical findings through several experiments where the terminal polynomial is held fixed, and only the realization varies:

• Stochastic Curvature: On diagonal quadratics with endpoint-coupled stochastic noise, the Sine-Jacobi method requires approximately 13% less curvature-noise budget to achieve the same admissible horizon as the prefix method.
• Time-Varying Quadratics: In non-autonomous quadratic sequences, the Sine-Jacobi method's response to Hessian perturbations matches the theoretical kernel prediction with high accuracy (median ratio $\approx 1.0$) and is significantly lower (median ratio $\approx 0.59$) than the prefix method.
• Finite-Radius GLM: On a smooth, strongly convex logistic regression problem with endpoint-coupled structure, the Sine-Jacobi method admits larger initial radii (1.68x larger median accepted radius) and requires significantly fewer gradient rejections during restarts compared to the prefix method.

4. Significance and Claims

The paper claims that the ordered realization of an optimization method is a distinct property from its terminal polynomial, particularly under time-varying conditions.

• Optimality Shift: While the prefix-exact Chebyshev recurrence is optimal within the class of methods that are exact at every step, relaxing this constraint to terminal-only exactness allows for the Sine-Jacobi realization, which is superior in terms of robustness to Hessian drift.
• Mechanism: The improvement arises because the Sine-Jacobi weights redistribute the intermediate sensitivity profile of the ordered product, reducing the concentration of time-sensitivity energy near the boundaries, thereby lowering the $\ell_2$-gain.
• Practical Implication: The results suggest that for problems with time-varying Hessians or stochastic curvature, one can achieve better robustness and larger admissible block sizes without sacrificing the fixed-Hessian convergence rate, simply by choosing a different realization (Sine-Jacobi) of the same terminal polynomial.

The authors maintain a modest scope, focusing on the theoretical derivation of the drift gain and its empirical verification on specific quadratic and GLM models, without claiming universal superiority for all optimization landscapes. The work is presented as the first part of a series investigating these acceleration properties under Hessian variation.