Skip to content
Get started

Steps for gradient descent on a quadratic

MediumLinear Algebra7 min

You minimise f(x)=12x⊤Axf(x) = \tfrac12 x^\top A x on R2\mathbb{R}^2 with A=(5445),A = \begin{pmatrix}5&4\\4&5\end{pmatrix}, using gradient descent with a fixed step size η\eta: xk+1=xk−η∇f(xk)x_{k+1} = x_k - \eta\nabla f(x_k). You choose η\eta to make the worst-case contraction factor per step as small as possible.

With that η\eta, what is the smallest number of steps kk that guarantees ∥xk∥≤10−6∥x0∥\lVert x_k\rVert \le 10^{-6}\lVert x_0\rVert for every starting point x0x_0?

Show hints (3)+
  1. Each step multiplies the eigen-components by 1−ηλ1 - \eta\lambda.
  2. Pick η\eta to equalise ∣1−ηλmin⁡∣|1-\eta\lambda_{\min}| and ∣1−ηλmax⁡∣|1-\eta\lambda_{\max}|.
  3. Then solve ρk≤10−6\rho^k \le 10^{-6} for the smallest integer kk.

Answer

Reveal answer →

62

Create a free account to see the full worked solution and track your progress.

Interview format: Prop Trading, Systematic & Data-Driven Trading

Related questions