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

Abstract

We study finite-horizon one-gradient realizations with the Chebyshev minimax terminal residual on $[\hat{I}¼,L]$. Under time-dependent Hessian perturbations, the terminal first variation is governed by a time-ordered spectral kernel $K_s(\hat{I}»,\hat{I}½)$; its sharp ${\ell }_2$ gain is $A_N$. For the prefix-exact Chebyshev recurrence, $$A_N^{\mathrm{pref}}=\frac{\hat{I}{\mu }_N^{\star }}{L-\hat{I}¼}{\left(4N^2+16\sum _{m=1}^{N-1}{m}^2\right)}^{1/2}=\frac{4}{\sqrt{3}}\frac{N^{3/2}}{L-\hat{I}¼}\hat{I}{\mu }_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-\hat{I}¼}\hat{I}{\mu }_N^{\star }(1+o(1)),2\sqrt{c_{\sin }}\approx 2.137936<4/\sqrt{3}.$$ 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.

37 pages