Heavy ball on a quadratic — the spectral analysis

ProofGraduate⏱ 3 hoursAdvanced Optimizationheavy ballmomentumspectral radiusaccelerationflagship

Problem

For $f(x)=\tfrac12x^\top Ax$ with $\mu I\preceq A\preceq LI$ , analyse heavy ball $x_{t+1}=x_t-\eta\nabla f(x_t)+\beta(x_t-x_{t-1})$ .

Reduce to $d$ scalar recurrences and write each as a $2\times2$ linear system.
Compute the characteristic roots and show that when the discriminant is negative both have modulus $\sqrt\beta$ .
Choose $\eta,\beta$ making the discriminant non-positive for every eigenvalue in $[\mu,L]$ , and deduce the rate $\rho = \frac{\sqrt\kappa-1}{\sqrt\kappa+1}$ .

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

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

Problem	Field	Type	Difficulty	Time
Simulate and compare convergence rates run	Advanced Optimization	Coding	Intermediate	1 hour
The RNN gradient is a repeated matrix product	Deep Learning	Proof	Intermediate	30 min
Prove the O(1/t) rate for gradient descent abyss	Optimization	Proof	Advanced	1 hour
Acceleration as an optimal polynomial	Advanced Optimization	Proof	Graduate	1 hour
Derive the constant-step SGD noise floor abyss	SGD	Proof	Graduate	1 hour