```markdown
### Damped Newton Phase (\(\|\nabla f(x)\|_2 \geq \eta\))
- Most iterations require backtracking steps.
- Function value decreases by at least \(\gamma\).
- If \(p^* > -\infty\), this phase ends after at most \((f(x^{(0)}) - p^*)/\gamma\) iterations.

### Quadratically Convergent Phase (\(\|\nabla f(x)\|_2 < \eta\))
- All iterations use step size \(t = 1\).
- \(\|\nabla f(x)\|_2\) converges to zero quadratically: if \(\|\nabla f(x^{(k)})\|_2 < \eta\), then

\[
\frac{L}{2m^2} \|\nabla f(x^l)\|_2 \leq \left( \frac{L}{2m^2} \|\nabla f(x^k)\|_2 \right)^{2^{l-k}} \leq \left( \frac{1}{2} \right)^{2^{l-k}}, \quad l \geq k
\]

---

*A. d'Aspremont. Convex Optimization M2.* Page 21/53
```
