Chebyshev-Exact Acceleration under Hessian Variation, I: Sine-Jacobi Method
For researchers in optimization and numerical analysis, this provides a refined understanding of acceleration under time-varying Hessians, though the results are incremental and domain-specific.
The paper studies finite-horizon Chebyshev acceleration under Hessian variations, deriving sharp bounds on the first-order Hessian-drift gain. It shows that the sine-Jacobi method achieves a lower gain constant (≈2.138) than the prefix-exact Chebyshev recurrence (4/√3 ≈ 2.309), demonstrating that the Chebyshev terminal polynomial does not determine the gain, with experiments confirming lower curvature overhead and better performance on a GLM.
We study finite-horizon one-gradient realizations with the Chebyshev minimax terminal residual on $[μ,L]$. Under time-dependent Hessian perturbations, the terminal first variation is governed by a time-ordered spectral kernel $K_s(λ,ν)$; its sharp $\ell_2$ gain is $A_N$. For the prefix-exact Chebyshev recurrence, $$ A_N^{\rm pref} =\frac{ε_N^\star}{L-μ} \left(4N^2+16\sum_{m=1}^{N-1}m^2\right)^{1/2} =\frac4{\sqrt3}\frac{N^{3/2}}{L-μ}ε_N^\star(1+o(1)), $$ and this is sharp in the causal two-term class with Chebyshev exactness at every prefix. For terminal-only exactness, Jacobi coordinates give $P_N=2^{1-N}T_N$: the spectrum is fixed at the midpoint Chebyshev nodes, while the spectral weights parametrize the realizations. The sine weights give a final-exact Jacobi method with the same terminal residual and $$ A_N(J_N^{\sin}) =2\sqrt{c_{\sin}}\frac{N^{3/2}}{L-μ}ε_N^\star(1+o(1)), \; 2\sqrt{c_{\sin}}\approx2.137936<4/\sqrt3. $$ Thus the Chebyshev terminal polynomial does not determine the first-order Hessian-drift gain. The experiments show the finite-horizon effect: lower stochastic curvature overhead, larger admissible-block frontiers, accurate time-varying quadratic predictions, and lower restart cost on an endpoint-coupled smooth strongly convex GLM.