Chebyshev-Exact Acceleration under Hessian Variation, II: Computer-Assisted Variational Lower Bound
Abstract
We study two-step recurrences with positive step sizes and nonnegative momentum coefficients whose terminal residual is the Chebyshev minimax polynomial on a prescribed spectral interval [μ,L]. These recurrences have the same terminal error on a fixed quadratic, but their first-order responses to stepwise Hessian perturbations can differ. We prove that the sine-Jacobi recurrence of Part I is asymptotically optimal for this response norm within a factor of $1.000004$, uniformly over 0<μ<L. Every terminal-exact recurrence satisfies AN≥(2√(ccert)−o(1))N3/2εN⋆/(L−μ) with ccert>1.14268353624, whereas the sine-Jacobi recurrence attains the constant 2√(csin) with csin<1.14269218. The proof reduces the gain to the diagonal energy of a Jacobi Green matrix. A centering lift represents this matrix by an exponential kernel; packing its diagonal into a density on the line preserves the energy and controls the change in the Birman-Schwinger spectrum. A calibrated identity gives a lower bound using the ground parameter and one Fredholm determinant. Two further determinants and a trace observation improve the bound through a pointwise inequality on an explicit compact state region. One rational certificate verifies this inequality by interval arithmetic. A second certificate constructs a density satisfying the selected observations and both normalizations with energy below the sine value. Finally, no C1 function of finitely many observations of the specified kinds gives a locally sharp lower bound at the sine density.
Related
- Chebyshev-Exact Acceleration under Hessian Variation, I: Sine-Jacobi Method
- 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
- A Projection Anderson Acceleration Algorithm for Non-quasi-monotone Variational Inequalities with Hölder Continuous Terms
- Acceleration and its Limits in Gaussian Variational Inference
BibTeX
@misc{pasechnyukvilensky2026chebyshevexact,
title = {{Chebyshev-Exact Acceleration under Hessian Variation, II: Computer-Assisted Variational Lower Bound}},
author = {Dmitry Pasechnyuk-Vilensky and Martin Takáč},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.05164},
eprint = {2610.05164},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.05164},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Chebyshev-Exact Acceleration under Hessian Variation, II: Computer-Assisted Variational Lower Bound
AU - Dmitry Pasechnyuk-Vilensky
AU - Martin Takáč
PY - 2026
DA - 2026/10/06
PB - arXiv
DO - 10.48550/arxiv.2610.05164
UR - https://arxiv.org/abs/2610.05164
AB - We study two-step recurrences with positive step sizes and nonnegative momentum coefficients whose terminal residual is the Chebyshev minimax polynomial on a prescribed spectral interval [μ,L]. These recurrences have the same terminal error on a fixed quadratic, but their first-order responses to stepwise Hessian perturbations can differ. We prove that the sine-Jacobi recurrence of Part I is asymptotically optimal for this response norm within a factor of $1.000004$, uniformly over 0<μ<L. Every terminal-exact recurrence satisfies A_N≥(2√(c_cert)−o(1))N^3/2ε_N^⋆/(L−μ) with c_cert>1.14268353624, whereas the sine-Jacobi recurrence attains the constant 2√(c_sin) with c_sin<1.14269218. The proof reduces the gain to the diagonal energy of a Jacobi Green matrix. A centering lift represents this matrix by an exponential kernel; packing its diagonal into a density on the line preserves the energy and controls the change in the Birman-Schwinger spectrum. A calibrated identity gives a lower bound using the ground parameter and one Fredholm determinant. Two further determinants and a trace observation improve the bound through a pointwise inequality on an explicit compact state region. One rational certificate verifies this inequality by interval arithmetic. A second certificate constructs a density satisfying the selected observations and both normalizations with energy below the sine value. Finally, no C^1 function of finitely many observations of the specified kinds gives a locally sharp lower bound at the sine density.
ER -