Problem

Gradient descent is a greedy search method for optimization, whose analysis varies depending on the kind of constraints you place on it.

We study a baby version of the method. Let ff be a twice continuous differentiable and convex function. We are interested in the minimization problem:

min⁡x∈Rnf(x) \min_{x \in \mathbb{R }^n} f(x)

The convexity of ff guarantees the existence of a unique minimum value min⁡x∈Rnf(x)\min_{x \in \mathbb{R }^n} f(x).

In addition, we assume that ff indeed achieves this minimum value at some point, denoted as x∗x^*. We need this assumption, as in some case, ff can never achieve the minimum value. For example, let f(x)=exf(x) = e^x. ff approaches 00 when x→−∞x \rightarrow -\infty but never achieves it.

Notations

Before we delve into the details, we need to define some frequently used notations.

  • The gradient ∇f(x):Rn→Rn\nabla f(x):\mathbb{R }^n \rightarrow \mathbb{R }^n is the vector of partial derivatives of ff at point xx:
∇f(x)=[∂f(x)∂x1,∂f(x)∂x2,..,∂f(x)∂xn] \nabla f(x) = \left[ \frac{\partial f (x) }{\partial x_1}, \frac{\partial f (x)}{\partial x_2}, .., \frac{\partial f (x) }{\partial x_n} \right]
  • The Hessian ∇2f(x):Rn→Rn×n\nabla^2 f(x) : \mathbb{R }^n \rightarrow \mathbb{R }^{n \times n} is the matrix of second order derivatives of ff at xx:∇f(x)=[∂2f(x)∂x1∂x1,∂2f(x)∂x1∂x2,...,∂2f(x)∂x1∂xn∂2f(x)∂x2∂x1,∂2f(x)∂x2∂x2,...,∂2f(x)∂x2∂xn...∂2f(x)∂xn∂x1,∂2f(x)∂xn∂x2,...,∂2f(x)∂xn∂xn] \nabla f(x) = \left[ \begin{aligned} \frac{\partial^2 f (x)}{\partial x_1 \partial x_1}, \frac{\partial^2 f (x)}{\partial x_1 \partial x_2}, &..., \frac{\partial^2 f (x)}{\partial x_1 \partial x_n} \\ \frac{\partial^2 f (x)}{\partial x_2 \partial x_1}, \frac{\partial^2 f (x)}{\partial x_2 \partial x_2}, &..., \frac{\partial^2 f (x)}{\partial x_2 \partial x_n} \\ &...\\ \frac{\partial^2 f (x)}{\partial x_n \partial x_1}, \frac{\partial^2 f (x)}{\partial x_n \partial x_2}, &..., \frac{\partial^2 f (x)}{\partial x_n \partial x_n} \\ \end{aligned} \right] Since ff is twice continuous differentiable, the Hessian is symmetric.

Algorithm

The algorithm is itself very simple.

Gradient Descent
Require: Initialization point x0∈Rnx_0 \in \mathbb{R }^n; Step size: η∈R+\eta \in \mathbb{R}_+; #iterations: TT.

  1. For t∈[T]t \in [T]:
  2. xt+1←xt−η⋅∇f(xt)\qquad x^{t + 1} \leftarrow x^t - \eta \cdot \nabla f(x^t).

Below is an example that show how ff decreases as the algorithm iterates.

Convergence

To analyze the convergence rate of ff, we need additional assumptions. Here we adopt two strong ones:

Assumptions.

  1. ff is β\beta smooth, i.e., ∇f(z)≤βI\nabla f(z) \le \beta I for ∀z∈Rn\forall z \in \mathbb{R }^n.
  2. ff is α\alpha strongly convex, i.e., ∇f(z)≥αI\nabla f(z) \ge \alpha I for ∀z∈Rn\forall z \in \mathbb{R }^n.

β\beta upper bounds the largest possible eigenvalue of the Hessian of ff at each point in R\mathbb{R}, and α\alpha lower bounds it. By definition we have β≥α\beta \ge \alpha.

Definitions.

  1. For each t∈[T]t \in [T], let Δt≐f(xt)−f(x∗)\Delta_t \doteq f(x^t) - f(x^*) be the gap between f(xt)f(x^t) and the minimum value f(x∗)f(x^*).
  2. Let κ≐βα\kappa \doteq \frac{\beta}{\alpha} between β\beta and α\alpha.

The following theorem characterize the convergence rate of the algorithm:

Theorem (Convergence Rate). If we set η=1β\eta = \frac{1}{\beta}, then it holds that

Δt≤Δ0(1−1κ)t. \Delta_t \le \Delta_0 \left( 1 - \frac{1}{ \kappa } \right)^t.

By the theorem, given any ϵ>0\epsilon > 0, the number of iteration tt for which Δt≤ϵ\Delta_t \le \epsilon is given by

O(κlog⁡Δ0ϵ). O \left( \kappa \log \frac{\Delta_0}{\epsilon} \right).

Proof: The proof consists of two parts. β\beta-smoothness and α\alpha-convexity play a role in each part separately.

The first claim states that

Claim 1. If η=1/β\eta = 1 / \beta, then

Δt+1≤Δt−12β∥∇f(xt)∥2. \Delta_{t + 1} \le \Delta_t - \frac{1}{2 \beta} \| \nabla f(x_t) \|^2.

We might still have a problem, if when xtx^t approaches x∗x^*, ∥∇f(xt)∥\| \nabla f(x^t) \| decreases too fast. That where α\alpha convexity comes into play.

Claim 2.

−12α⋅∥∇f(xt)∥2≤Δt. - \frac{1}{2 \alpha } \cdot \| \nabla f(x^t) \|^2 \le \Delta_t.

In combination, we conclude that

Δt+1≤Δt(1−αβ). \begin{aligned} \Delta_{t + 1} &\le \Delta_t \left( 1- \frac{\alpha }{\beta} \right). \end{aligned}

The figure gives some intuition about the algorithm. The function ff is plotted as the blue, real line. Suppose that A=f(xt)A = f( x^t ). We search along the direction of −∇f(x)- \nabla f(x) for the minimum value of f(x)f(x) by computing xt+1=xt−η∇f(x)x^{t + 1} = x^t - \eta \nabla f(x).

We don't want η\eta to be too large, such that xt+1x^{t + 1} passes the minimum point. How do we guarantee this? We create a quadratic approximation y=f(xt)+∇f(xt)(y−x)+(β/2)⋅∥y−x∥22y = f(x^t) + \nabla f(x^t) ( y - x) + (\beta / 2) \cdot \Vert y - x \Vert_2^2 of the ff at xtx^t, whose Hessian is βI\beta I, which upper bounds the Hessian of ff at every point. The minimum point of the quadratic approximation is a conservative estimate of f(xt)f(x^t). As we will prove, it holds that

f(x∗)≤f(xt)−12β∥∇f(xt)∥22. f( x^* ) \le f( x^t ) - \frac{1}{2 \beta} \Vert \nabla f( x^t) \Vert_2^2.

Proof of the Lemma. Via Taylor's expansion, for all x,y∈Rnx, y \in \mathbb{R }^n, there exists some z∈[x,y]z \in [x, y], such that

f(y)=f(x)+∇f(x)T(y−x)+12(y−x)T∇2f(z)(y−x). f(y) = f(x) + \nabla f(x)^T (y - x) + \frac{1}{2} (y - x)^T \nabla^2 f(z) (y - x).

By assumption that αI≤∇f(z)≤βI\alpha I \le \nabla f(z) \le \beta I, we have

f(y)≤f(x)+∇f(x)T(y−x)+12β∥y−x∥2,f(y)≥f(x)+∇f(x)T(y−x)+12α∥y−x∥2. f(y) \le f(x) + \nabla f(x)^T (y - x) + \frac{1}{2} \beta \|y - x \|^2, \\ f(y) \ge f(x) + \nabla f(x)^T (y - x) + \frac{1}{2} \alpha \|y - x \|^2.

For the first inequality, the RHS is minimized when y−x=−(1/β)⋅∇f(x)y - x = - (1 / \beta) \cdot \nabla f(x):

f(x−(1/β)⋅∇f(x))≤f(x)−12β∥∇f(x)∥2. f \big( x - (1 / \beta) \cdot \nabla f(x) \big) \le f( x ) - \frac{1}{2 \beta} \| \nabla f(x ) \|^2.

For the second inequality, we take minimum over both sides,

f(x∗)=min⁡y∈Rnf(y)≥min⁡y∈Rn(f(x)+∇f(x)T(y−x)+α2∥y−x∥2)=f(x)−12α∥∇f(x)∥2. \begin{aligned} f( x^*) &= \min_{y \in \mathbb{R}^n} f(y) \\ &\ge \min_{y \in \mathbb{R}^n} \left( f(x) + \nabla f(x)^T (y - x) + \frac{\alpha}{2} \| y - x \|^2\right) \\ &= f(x) - \frac{1}{2 \alpha } \| \nabla f(x ) \|^2. \end{aligned}

Substituting xx with xtx^t, and xt+1x^{t + 1} with xt−(1/β)∇f(x)x^t - (1 / \beta) \nabla f(x), we see

f(xt+1)−f(xt)≤−12β∥∇f(xt)∥2,f(xt)−f(x∗)≤12α∥∇f(xt)∥2. \begin{aligned} f(x^{t + 1}) - f(x^t) &\le - \frac{1}{2 \beta } \| \nabla f(x^t) \|^2, \\ f( x^t ) - f( x^* ) &\le \frac{1}{2 \alpha } \| \nabla f( x^t ) \|^2. \end{aligned}

Replacing f(xt+1)−f(xt)f(x^{t + 1}) - f(x^t) with Δt+1−Δt\Delta_{t + 1} - \Delta_t, and f(xt)−f(x∗)f(x^t) - f(x^*) with Δt\Delta_t finishes the proof.

Remark: Via a similar argument, we can also prove that

f(xt)−f(x∗)≥12β∥∇f(xt)∥2. f( x^t ) - f( x^* ) \ge \frac{1}{2 \beta} \| \nabla f(x^t) \|^2.

□\square