Convergence rate O(1/k) of gradient descent

• Preliminary
  • kk-strongly convex
  • Lipschitz w.r.t norm ||x||||x||
• Gradient descent
  • choose step size tkt_k
  • convergence rate under Lipschitz gradient
  • convergence rate under strong convexity
• Steepest descent

Preliminary

$k$-strongly convex

$$f(y)\geq f(x) + (y-x)f'(x) + \frac{k(y-x)^2}{2}$$
$f(x)=|x|+x^2$ is 2-strongly convex. Roughly speaking, the faster a function grows (in either direction), the stronger convexity it has.

Lipschitz w.r.t norm $||x||$

$$\{f\mid |f(x) - f(y)| \leq L||x-y|| \}$$
A function which satisfies Lipschitz condition cannot grow too fast, precisely, faster than linear. A function cannot be both Lipschitz and strongly convex.

http://www.cs.cmu.edu/~ggordon/10725-F12/schedule.html
Roughly speaking, if $f$ is Lipschitz, $\nabla f \leq L$.
If $\nabla f$ is Lipschitz, $\nabla^2f \leq L$.

Gradient descent

Consider the expansion (linear approximation plus proximity term)
$$f(y) \approx f(x)+\nabla f(x)^T (y-x) + \frac 1 {2t} \lVert y-x \rVert ^2$$
$$\partial_y f(y) = 0 \implies x^{k+1} = x^k - t\nabla f(x)$$

choose step size $t_k$

Backtracking line search.

1. fix $\beta$ with $0<\beta<1$
2. while $f(x-t\nabla f(x)) > f(x) - \frac t2 ||\nabla f(x)||^2$, update $t=\beta t$.

Exact line search. (usually not possible and it’s not worth it)
$$t=\arg\min_{s\geq 0} f(x-s\nabla f(x))$$

convergence rate under Lipschitz gradient

Assume that $f : \mathbb R^n \to \mathbb R$ is convex and differentiable, and additionally
$$||\nabla f(x) - \nabla f(y) || \leq L || x-y || \quad \forall x,y$$
Gradient descent with fixed step size $t \leq 1/L$ satisfies
$$f(x^k) - f(x^*) \leq \frac{||x^0 - x^*||^2}{2tk}$$

Proof.

Convergence analysis for backtracking.
Same rate for a step size chosen by backtracking search

Gradient descent with backtracking line search satisfies
$$f(x^k) - f(x^*) \leq \frac{||x^0 - x^*||^2} {2t_{min} k}$$
where $t_{min} = \min \{ 1, \beta / L \}$.

Proof is similar.

convergence rate under strong convexity

Strong convexity : $\nabla^2 f(x) \succeq dI \quad\forall x$.
Better lower bound than that from usual convexity: $$f(y)\leq f(x) + \nabla f(x) ^T (y-x) + \frac d2 ||y-x||^2 \quad\forall x,y$$

Gradient descent with fixed step size $t\leq 2/ (d+L)$ or with backtracking line search satisfies
$$f(x^k) - f(x^*) \leq c^k \frac L2 ||x^0 - x^*||^2 \text{ with } 0<c<1$$

Convergence rate is $O(c^k)$, exponentially fast. To get $f(x^k) - f(x^*) \leq \epsilon$, we need $O(\log (1/\epsilon))$ iterations.
For example, $f(x) = \frac 12 ||y-Ax||^2$. $A^TA\preceq LI$, take $L=\sigma_{max}^2(A)$.
Stopping rule: stop when $||\nabla f(x)||$ is small.
If $f$ is strongly convex with parameter $d$, then
$$||\nabla f(x)|| \leq \sqrt{2d\epsilon} \implies f(x) - f(x^*)\leq\epsilon$$

Steepest descent

Just change the choice of norm. $1/q + 1/r=1$.
Updates are $x^+ = x+t\Delta x$ where
$$\Delta x = ||\nabla f(x)||_r \cdot u\\ u = \arg\min_{||v||_q \leq 1} \nabla f(x)^T v$$
If $q=2$, gradient descent.
If $q=1$, $\Delta x = -\partial f(x) / \partial x_i \cdot e_i$ where
$$|\frac{\partial f}{\partial x_i} (x)| = \max_{j=1,...,n} |\frac{\partial f}{\partial x_j} (x)| = ||\nabla f(x)||_\infty$$
Normalized steepest descent just takes $\Delta x = u$ (unit $q$-norm).

• Preliminary
  • kk-strongly convex
  • Lipschitz w.r.t norm ||x||||x||
• Gradient descent
  • choose step size tkt_k
  • convergence rate under Lipschitz gradient
  • convergence rate under strong convexity
• Steepest descent