Gradient descent · Definition

Convergence with Lipschitz gradient

continuous optimizationgradient descent

When the gradient does not change too abruptly from one point to another, gradient descent progresses predictably. This regularity lets us quantify how close the function value gets to the optimum after each iteration.

Definition

Result guaranteeing that gradient descent with a suitable step size converges for differentiable functions whose gradient \( \nabla f \) is Lipschitz continuous with constant \( L \).

\[f(x_k)-f^* \le \frac{L\|x_0-x^*\|^2}{2k}\]

The Lipschitz condition \( \|\nabla f(x)-\nabla f(y)\| \le L\|x-y\| \) implies the descent lemma \( f(y)\le f(x)+\nabla f(x)^T(y-x)+\frac{L}{2}\|y-x\|^2 \). If \( f \) is also convex, with step \( t=1/L \) the method satisfies \( f(x_k)-f^*\le \frac{L\|x_0-x^*\|^2}{2k} \), that is, an \( O(1/k) \) rate. This result follows Nesterov's treatment.

Consider \( f(x)=\frac{1}{2}x^2 \) on \( \mathbb{R} \), where \( \nabla f(x)=x \) and \( L=1 \). With \( t=1 \) and \( x_0=2 \), the first step gives \( x_1=2-2=0 \), which is the exact optimum, so the bound holds with room to spare. This example shows that the step \( 1/L \) is a natural choice.

A typical mistake is using a step larger than \( 2/L \), which can make the sequence oscillate or diverge even when the function is convex. Another error is applying the \( O(1/k) \) bound without checking that \( \nabla f \) is truly Lipschitz with constant \( L \).

Think about it

Why is the Lipschitz condition on the gradient alone not enough to guarantee that \( f(x_k) \) approaches the global minimum, and what extra hypothesis is needed?

Without convexity, Lipschitz gradient descent only guarantees that the gradient tends to zero, i.e., a stationary point, not the global minimum. The \( O(1/k) \) bound on \( f(x_k)-f^* \) also requires \( f \) to be convex.

Exercises 10

  1. What does it mean for \( \nabla f \) to be Lipschitz with constant \( L \)?
  2. If \( \nabla f \) is Lipschitz with constant \( L \), which gradient step is the standard choice?
  3. What is the function-value convergence rate for convex gradient descent with step \( 1/L \)?
  4. Which inequality follows from the Lipschitz condition on the gradient?
  5. If \( \nabla f \) is Lipschitz, what does convexity of \( f \) add for the descent sequence?
  6. A function has \( L=4 \). What step \( t \) is safe under the rule \( t=1/L \)?
  7. For \( f(x)=x^2 \) on \( \mathbb{R} \), what is the Lipschitz constant \( L \) of the gradient?
  8. If \( \nabla f \) is Lipschitz with \( L=3 \) and \( \|x_0-x^*\|=2 \), what bound does the \( O(1/k) \) rate give for \( k=6 \)?
  9. For \( f(x)=\frac{1}{2}x^2 \) with \( t=1/L \), what is \( x_1 \) if \( x_0=4 \)?
  10. Let \( f(x)=2x^2 \) on \( \mathbb{R} \), with \( x_0=1 \) and step \( t=1/L \). What is \( x_1 \)?

References

  • Stephen Boyd, Lieven Vandenberghe, Convex Optimization, 1st edition, Cambridge University Press, 2004.
  • Jorge Nocedal, Stephen J. Wright, Numerical Optimization, 2nd edition, Springer, 2006.