Problem bank

Problem 321 of 333HardCalculusP321

Choosing a learning rate for a narrow valley

  1. You minimize f(x,y)=6.5x2+12xy+6.5y2f(x, y) = 6.5x^2 + 12xy + 6.5y^2 by gradient descent with a fixed step size η\eta: vk+1=vk−η∇f(vk)v_{k+1} = v_k - \eta\nabla f(v_k).

    • For which η\eta does the method converge from every starting point?
    • Which η\eta gives the fastest guaranteed convergence, and how many steps does it need to cut the distance to the minimum by a factor of 10610^6?
    • A colleague plays safe with η=0.04\eta = 0.04. How many steps does that take in the worst case?
    • How many steps would Newton's method need?