Acceleration as an optimal polynomial
ProofGraduate⏱ 1 hourAdvanced Optimizationchebyshevpolynomiallower boundkrylov
Problem
For with , show that any first-order method whose iterates lie in satisfies for some degree- polynomial with . Deduce that the best achievable worst-case rate is
where 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| Solved | Problem | Field | Type | Difficulty | Time |
|---|---|---|---|---|---|
| Markov and Chebyshev are attained | High-Dim Probability | Proof | 15 min | ||
| The weak law needs only uncorrelatedness | Probability | Proof | 15 min | ||
| Simulate and compare convergence rates run | Advanced Optimization | Coding | 1 hour | ||
| Single-stream decode latency floors | LLM Ops | Numerical | 30 min | ||
| The irreducible loss is the conditional entropy | LLMs | Proof | 30 min |