8. Acceleration, and what comes next (Newton's method)

Gradient descent is not optimal

Question raised: in this oracle model (value + gradient, with Hessian bounds), is O((L/μ)·log(1/ε)) the best possible? (1:20:48, 1:21:08).
No. Accelerated gradient descent halves the error in O(√(L/μ)) iterations — due to Nesterov, Soviet Math 1983 (1:21:08, 1:22:02).
Not covered in the course: for the interior point application all control parameters will be constants, so L/μ versus √(L/μ) makes no difference here. Mentioned purely so students know it exists for other problems (1:22:02, 1:22:42).

Next up: state the second-order method — Newton's method — and its bounds; the proof will be left to the course notes (1:22:58, 1:23:39).
Then: show how to use Newton's method to go from x̃_{λk} to x̃_{λk+1} (1:23:39).
Why not gradient descent for IPM: interior point needs to explicitly compute the Hessian, not merely have bounds on it (1:24:14).
The warm-start mechanics to keep in mind: x̃_{λk}, the approximate minimizer of f_{λk} already in hand, becomes the x₀ that seeds Newton's method for minimizing f_{λk+1}; run the update rule until the error is small enough, and the result is x̃_{λk+1}, which seeds the next round for f_{λk+2} (1:24:35, 1:24:58, 1:25:22).

A problem set and the project proposal are due; the proposal deadline is confirmed by students as Thursday 11:59 PM, with the instructor deferring to the course website (1:25:48, 1:26:07, 1:26:22).