Skip to content
nonconvexcard

Acceleration as an optimal polynomial

ProofGraduate⏱ 1 hourAdvanced Optimizationchebyshevpolynomiallower boundkrylov

Problem

For f(x)=12x⊤Ax−b⊤xf(x)=\tfrac12x^\top Ax - b^\top x with μI⪯A⪯LI\mu I\preceq A\preceq LI, show that any first-order method whose iterates lie in x0+span⁡{r0,Ar0,…,At−1r0}x_0 + \operatorname{span}\{r_0,Ar_0,\dots,A^{t-1}r_0\} satisfies xt−x⋆=pt(A)(x0−x⋆)x_t-x^\star = p_t(A)(x_0-x^\star) for some degree-tt polynomial with pt(0)=1p_t(0)=1. Deduce that the best achievable worst-case rate is

min⁡ptmax⁡λ∈[μ,L]∣pt(λ)∣=1Tt(L+μL−μ)≈2(κ−1κ+1)t,\min_{p_t}\max_{\lambda\in[\mu,L]}|p_t(\lambda)| = \frac{1}{T_t\big(\frac{L+\mu}{L-\mu}\big)} \approx 2\left(\frac{\sqrt\kappa-1}{\sqrt\kappa+1}\right)^t,

where TtT_t is the Chebyshev polynomial of the first kind.

Write a complete argument. Every inequality you use should be one you could state precisely.

Solution

Opening this before you have a real attempt on paper is the fastest way to feel like you understand something you cannot reproduce.

Related problems

All problems
SolvedProblemFieldTypeDifficultyTime
Markov and Chebyshev are attainedHigh-Dim ProbabilityProofFoundation15 min
The weak law needs only uncorrelatednessProbabilityProofBeginner15 min
Simulate and compare convergence rates runAdvanced OptimizationCodingIntermediate1 hour
Single-stream decode latency floorsLLM OpsNumericalIntermediate30 min
The irreducible loss is the conditional entropyLLMsProofIntermediate30 min