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 [μ,L]. Under time-dependent Hessian perturbations, the terminal first variation is governed by a time-ordered spectral kernel Ks(λ,ν); its sharp ℓ2 gain is AN. For the prefix-exact Chebyshev recurrence, ANpref=4/√3N3/2/(L−μ)εN⋆(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 PN=21−NTN: 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 AN(JNsin)=2√(csin)N3/2/(L−μ)εN⋆(1+o(1)), 2√(csin)≈2.1379<4/√3. Thus the Chebyshev terminal polynomial does not determine the first-order Hessian-drift gain. Momentum is necessary for this order: every Chebyshev-exact stepsize schedule has AN≥2√(2/3) N2εN⋆/(L−μ). Beyond first order, the response to drift Es=Hs−H of size δ=maxs|Es| is a finite polynomial expansion, and for both realizations the terminal error is at most εN⋆ TN(1+2δ/(L−μ)), the Chebyshev bound of the interval widened by δ. This bound is attained, holds for objectives with Lipschitz Hessian, and shows that drift reduces the accelerated rate exponent by the factor 1−√(δ/μ). The two realizations thus share the worst-case response and differ in the ℓ2-in-time response measured by AN. 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.
Related
- Chebyshev-Exact Acceleration under Hessian Variation, II: Computer-Assisted Variational Lower Bound
- Polynomial Acceleration of Alternating Projections: Chebyshev Acceleration, Convergence Rates, and Retractions
- Uniform Chebyshev approximations of functions satisfying a variation-type condition: reconstruction of time-varying signals on graphs
- Spectral Chebyshev wavelet method for state-dependent fractional integro-differential equations in adaptive tumor growth modeling
- The Jacobi Spectrum and Global Second Variation of Pansu Spheres
BibTeX
@misc{pasechnyukvilensky2026chebyshevexact,
title = {{Chebyshev-Exact Acceleration under Hessian Variation, I: Sine-Jacobi Method}},
author = {Dmitry Pasechnyuk-Vilensky and Martin Takáč},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2606.16671},
eprint = {2606.16671},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2606.16671},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Chebyshev-Exact Acceleration under Hessian Variation, I: Sine-Jacobi Method
AU - Dmitry Pasechnyuk-Vilensky
AU - Martin Takáč
PY - 2026
DA - 2026/10/04
PB - arXiv
DO - 10.48550/arxiv.2606.16671
UR - https://arxiv.org/abs/2606.16671
AB - 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 ℓ_2 gain is A_N. For the prefix-exact Chebyshev recurrence, A_N^pref=4/√3N^3/2/(L−μ)ε_N^⋆(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−NT_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√(c_sin)N^3/2/(L−μ)ε_N^⋆(1+o(1)), 2√(c_sin)≈2.1379<4/√3. Thus the Chebyshev terminal polynomial does not determine the first-order Hessian-drift gain. Momentum is necessary for this order: every Chebyshev-exact stepsize schedule has A_N≥2√(2/3) N^2ε_N^⋆/(L−μ). Beyond first order, the response to drift E_s=H_s−H of size δ=max_s|E_s| is a finite polynomial expansion, and for both realizations the terminal error is at most ε_N^⋆ T_N(1+2δ/(L−μ)), the Chebyshev bound of the interval widened by δ. This bound is attained, holds for objectives with Lipschitz Hessian, and shows that drift reduces the accelerated rate exponent by the factor 1−√(δ/μ). The two realizations thus share the worst-case response and differ in the ℓ_2-in-time response measured by A_N. 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.
ER -