Optimization

Optimization = Gradient Descent: (almost) just one algorithm

1.1 Gradient Descent

• To minimize a function \(f(x)\):

  \[ x_{t+1}=x_t-\eta \nabla f(x_t) \]

• \(\eta\) is the step size (learning rate).

1.1.1 Smoothness Assumption

• Gradient is Lipschitz:

  \[ \|\nabla f(w)-\nabla f(w')\| \leq L\|w-w'\|, \qquad \forall\, w,w'. \]

• Equivalent to:

  \[ \left| f(w')-f(w) - \left\langle \nabla f(w),\, w'-w \right\rangle \right| \leq \frac{L}{2}\|w-w'\|^2. \]

• Equivalent to:

  \[ \|\nabla^2 f(x)\| \leq L. \]

If \(w' = w - \eta \nabla f(w)\), we have

\[ f(w') - f(w) \leq \left\langle \nabla f(w),\, w' - w \right\rangle + \frac{L}{2}\|w' - w\|^2 \]

\[ = \left\langle \nabla f(w),\, -\eta \nabla f(w) \right\rangle + \frac{L\eta^2}{2}\|\nabla f(w)\|^2 = -\eta \left( 1-\frac{L\eta}{2} \right) \|\nabla f(w)\|^2. \]

So we should set

\[ \eta < \frac{2}{L} \]

to make sure

\[ f(w') - f(w) < 0. \]

\[ \eta=O\left(\frac{1}{L}\right). \]

1.1.2 \(\mu\)-Strongly Convex Function

• A function \(f\) is \(\mu\)-strongly convex if

  \[ f(w') \ge f(w) + \left\langle \nabla f(w),\, w'-w \right\rangle + \frac{\mu}{2}\|w'-w\|^2. \]

• Equivalently, if \(f\) is twice differentiable,

  \[ \lambda_{\min}\left(\nabla^2 f(w)\right) \ge \mu > 0, \]

• Equivalently

  \[ f(ax + (1 - a)y) \le af(x) + (1 - a)f(y) - \frac{\mu}{2}a(1 - a)\|x - y\|^2, \quad \forall a \in [0, 1]. \]

  i.e., the Hessian is positive definite.

• Strong convexity is a stronger notion than convexity.

• The gradient is strongly monotone:

  \[ \left\langle \nabla f(w')-\nabla f(w),\, w'-w \right\rangle \ge \mu \|w'-w\|^2. \]

1.1.3 Convergence Guarantee

• If \(f\) is \(L\)-smooth and convex, and

  \[ w^*=\arg\min_w f(w), \]

  then running gradient descent with step size

  \[ \eta\leq \frac{1}{L} \]

  satisfies

  \[ f(w_t) \leq f(w^*) + \frac{\|w_0-w^*\|^2}{2\eta t}. \]

• Therefore, if \(\eta = \frac{1}{L}\), we only need

  \[ T = \frac{L\|w_0-w^*\|^2}{2\epsilon} \]

  iterations to find a solution such that

  \[ f(w_T)\leq f(w^*)+\epsilon. \]

• This is called a convergence rate of

  \[ \frac{1}{T}, \]

  or equivalently, gradient descent needs

  \[ O\left(\frac{1}{\epsilon}\right) \]

  iterations to converge to an \(\epsilon\)-optimal solution.

Step 1:

\[ f(w_{i+1}) \le f(w_i) - \frac{\eta}{2} \|\nabla f(w_i)\|^2. \]

Step 2: By convexity, we have

\[ f(w_i) \le f(w^*) + \left\langle \nabla f(w_i),\, w_i-w^* \right\rangle. \]

1.2 Stochastic Gradient Descent

Similar to GD, but the gradient has some randomness:

\[ w_{t+1} = w_t-\eta G_t, \]

with

\[ \mathbb E[G_t] = \nabla L(w_t). \]

\[ G_t = \frac{1}{|S|} \sum_{i\in S} \nabla l(w,x_i,y_i), \]

where \(S\subseteq[N]\) is a randomly selected subset.

1.2.1 Analysis of SGD

If \(f\) is an \(L\)-smooth convex function, and we run SGD with

\[ \operatorname{Var}(G_t)\leq \sigma^2, \]

and step size

\[ \eta\leq \frac{1}{L}, \]

then

\[ \mathbb E\left[f(\bar w_t)\right] \leq f(w^*) + \frac{\|w_0-w^*\|^2}{2t\eta} + \eta\sigma^2, \]

where

\[ \bar w_t = \frac{\sum_{i=1}^{t} w_i}{t}. \]

Step 1:

\[ \mathbb E\left[f(w_{i+1})\right] \le f(w_i) - \frac{\eta}{2} \|\nabla f(w_i)\|^2 + \frac{\eta}{2}\sigma^2. \]

Step 2: By convexity

\[ \mathbb E\left[f(\bar w_t)\right] \le f(w^*) + \frac{\|w_0-w^*\|^2}{2t\eta} + \eta\sigma^2. \]

1.2.2 Convergence Speed

If we set

\[ T = \frac{2\|w_0-w^*\|^2\sigma^2}{\epsilon^2}, \qquad \eta = \frac{\epsilon}{2\sigma^2}, \]

then the two error terms are bounded by \(\epsilon\).

Notice that

\[ \eta \le \frac{1}{L}, \]

Therefore, SGD converges at rate

\[ \frac{1}{\sqrt{T}}. \]

1.2.3 Convergence Comparison

If the function is smooth and strongly convex:

• GD achieves linear convergence, so the convergence is exponentially fast:

  \[ T = O\left(\log \frac{1}{\epsilon}\right). \]

• SGD achieves a

  \[ T = O\left(\frac{1}{\epsilon}\right). \]

1.2.4 SVRG algorithm

For \(s=1,2,\ldots\)

1. \(\widetilde{w}=\widetilde{w}_{s-1}\)

   \[ \widetilde{u} = \frac{1}{N}\sum_{i=1}^{N}\nabla l_i(\widetilde{w}) = \nabla f(\widetilde{w}) \]

2. \[ w_0=\widetilde{w} \]

3. For \(t=1,2,\ldots,m\)

   • Random pick \(i\in[N]\)

     \[ w_t = w_{t-1} - \eta \left( \nabla l_i(w_{t-1}) - \nabla l_i(\widetilde{w}) + \widetilde{u} \right) \]

• Option I:

  \[ \widetilde{w}_s=w_m \]

• Option II:

  \[ \widetilde{w}_s=w_t \quad \text{for randomly chosen } t\in\{0,1,\ldots,m-1\}. \]

1.2.5 SAG

\[ x_{t+1}=x_t-\eta\left[ \bar g^t+\frac1n\left(\nabla f_{i_t}(x_t)-g_{i_t}^t\right) \right] \]

1.2.6 SAGA

\[ x_{t+1}=x_t-\eta\left[ \bar g^t+\nabla f_{i_t}(x_t)-g_{i_t}^t \right] \]

1.2.7 Comparison of SGD, SAG, SAGA, and SVRG

Property	SGD	SAG	SAGA	SVRG
Gradient estimator	\(\nabla f_{i_t}(x_t)\)	\(\bar g^t+\frac1n(\nabla f_{i_t}(x_t)-g_{i_t}^t)\)	\(\bar g^t+\nabla f_{i_t}(x_t)-g_{i_t}^t\)	\(\mu_s+\nabla f_{i_t}(x_t)-\nabla f_{i_t}(\tilde x_s)\)
Unbiased	Yes	No	Yes	Yes
Variance reduction	No	Yes	Yes	Yes
Variance vanishes asymptotically	Not generally	Yes, under convergence conditions	Yes, under convergence conditions	Yes, under convergence conditions
New component gradients per inner iteration	1	1	1	Usually 2
Periodic full gradient	No	No	No	Yes
Additional storage	\(O(d)\)	\(O(nd)\)	\(O(nd)\)	\(O(d)\)
Strongly convex convergence	\(O(1/T)\) (suitable averaging)	Linear	Linear	Linear

Here,

\[ \kappa=\frac{L}{\mu}, \]

where each \(f_i\) is convex and \(L\)-smooth, and \(f\) is \(\mu\)-strongly convex.

The complexity bounds assume standard algorithm-specific conditions and parameter choices.

The four gradient estimators can be summarized as

\[ \boxed{ \begin{aligned} v_t^{\mathrm{SGD}} &=\nabla f_{i_t}(x_t),\\[6pt] v_t^{\mathrm{SAG}} &=\bar g^t+\frac1n\left(\nabla f_{i_t}(x_t)-g_{i_t}^t\right),\\[6pt] v_t^{\mathrm{SAGA}} &=\bar g^t+\nabla f_{i_t}(x_t)-g_{i_t}^t,\\[6pt] v_t^{\mathrm{SVRG}} &=\mu_s+\nabla f_{i_t}(x_t)-\nabla f_{i_t}(\tilde x_s). \end{aligned} } \]

1.3 Mirror Descent

1.3.1 Bregman divergence:

• Given any 1-strongly convex function \(w\) as the distance generating function, we can define distance between \(x\) and \(y\).

  \[ V_x(y) = w(y) - \langle \nabla w(x), y-x \rangle - w(x) \]

• So

  \[ V_x(y) \ge \frac{1}{2}\|x-y\|^2 \]

• Three-point identity of Bregman divergence:

  \[ \langle \nabla w(x)-\nabla w(y), y-u \rangle = V_x(u)-V_y(u)-V_x(y) \]

1.3.2 Mirror Descent Algorithm

Mirror step with length \(\alpha\) is:

\[ x_{k+1} = \operatorname{Mirr}_{x_k}(\alpha \cdot \nabla f(x_k)), \]

where

\[ \operatorname{Mirr}_x(g) = \arg\min_y \left\{ V_x(y) + \langle g, y-x\rangle \right\}. \]

equation:

\[ \nabla w(y) = \nabla w(x) - \alpha \nabla f(x_k). \]

1.3.3 Convergence Analysis

We have:

\[ \begin{aligned} \alpha(f(x_k)-f(u)) &\le \alpha\langle\nabla f(x_k),x_k-u\rangle\\ &\le \frac{\alpha^2}{2}\|\nabla f(x_k)\|^2 +V_{x_k}(u)-V_{x_{k+1}}(u). \end{aligned} \]

1.3.4 Convergence Rate

Assume \(f\) is \(\rho\)-Lipschitz. Then

\[ \|\nabla f(x_k)\|\le\rho. \]

Let

\[ \bar{x}=\frac1T\sum_{k=0}^{T-1}x_k, \qquad \Theta=V_{x_0}(x^*). \]

Summing over \(k=0,\ldots,T-1\), we obtain

\[ f(\bar{x})-f(x^*) \le \frac{\alpha\rho^2}{2} +\frac{\Theta}{\alpha T}. \]

Let

\[ \alpha=\frac{\sqrt{2\Theta}}{\rho\sqrt{T}}. \]

Then

\[ f(\bar{x})-f(x^*) \le \frac{\sqrt{2\Theta}\cdot\rho}{\sqrt{T}}. \]

To guarantee \(f(\bar{x})-f(x^*)\le\epsilon\), it suffices to take

\[ T=O\left(\frac{\Theta\rho^2}{\epsilon^2}\right). \]

1.4 Matrix Completion

Matrix completion problem:

• \(n \times m\) matrix \(A\)
• Score is in \(\{1,2,3,4,5\}\)
• Some are known (existing ratings)
• Some are unknown (?)
• Want to recommend movies to users

Assumptions:

• \(A\) is low rank

• Known entries are uniformly distributed

• Incoherence. Formally, for \(A = U\Sigma V^T\), \(\forall i \in [n], j \in [m]\),

  \[ \|e_i^T U\| \le \sqrt{\frac{ur}{n}}, \qquad \|e_j^T V\| \le \sqrt{\frac{ur}{m}} \]

  for some constant \(u\) (scan every row of \(U,V\)). Here \(U \in \mathbb{R}^{n \times r}\), \(V \in \mathbb{R}^{m \times r}\),

  \[ 1 \le u \le \frac{\min\{n,m\}}{r}. \]

Minimizing the nuclear norm: the sum of singular values (SDP Problem).

Alternating least square minimization: We solve the following problem:

\[ \min_{U,V\in\mathbb{R}^{n\times r}} \left\|P_{\Omega}(UV^T)-P_{\Omega}(A)\right\|_F^2. \]

• For \(t=0,1,\ldots,T-1\):

  \[ \begin{aligned} V^{t+1} &\leftarrow \arg\min_V \left\|P_\Omega\left(U^tV^T-A\right)\right\|_F^2,\\ U^{t+1} &\leftarrow \arg\min_U \left\|P_\Omega\left(U(V^{t+1})^T-A\right)\right\|_F^2. \end{aligned} \]

• Every subproblem is convex and can be solved efficiently.

• In practice, way faster than the convex relaxation

1.5 Nonconvex Optimization

Important property: No-spurious-local-min (all the local min are equally good).

• For stationary points, \(\nabla L(w)=0\):
  • If \(\nabla^2L(w)\succ0\), it’s a local minimum.
  • If \(\nabla^2L(w)\prec0\), it’s a local maximum.
  • If \(\nabla^2L(w)\) has both positive and negative eigenvalues, it’s a strict saddle point.
    • At least one direction to escape!
  • If \(\nabla^2L(w)\succeq0\), it’s a local minimum or a flat saddle point.
    • No good direction to get out!
• We call a function strict saddle if it does not contain any flat saddle points.

Theorem: If \(L\) is smooth, bounded and strict saddle (actually a more general version applies to points with small gradients rather than zero gradients), and the Hessian is smooth, and if SGD noise has non-negligible variance in every direction with constant probability, then SGD will escape all saddle points and local maxima and converge to a local minimum after a polynomial number of steps.

1.6 Appendix

• If \(f\) is \(L\)-smooth and convex, then \[ f(y) \ge f(x) + \langle \nabla f(x), y-x\rangle + \frac{1}{2L} \|\nabla f(x)-\nabla f(y)\|^2. \] which implies

\[ \langle \nabla f(x)-\nabla f(y), x-y\rangle \ge \frac{1}{L} \|\nabla f(x)-\nabla f(y)\|^2. \]

• We have the Hölder’s inequality: \[\langle x, y \rangle \le \|x\|_{p} \cdot \|y\|_{q}\] where \(\frac{1}{p} + \frac{1}{q} = 1\). When \(p = q = 2\), this becomes the Cauchy-Schwarz inequality.

• For a finite probality function \(p(x)\), we define \[ w(p) = \sum_x p(x) \log p(x) . \] Then \(w(p)\) is 1-strongly convex with respect to \(\|\cdot\|_1\). The Bregman divergence is the KL divergence: \[ V_p(q) = \sum_x p(x) \log \frac{p(x)} {q(x)} = D_{\mathrm{KL}}(p \| q) \ge \frac{1}{2}\|p-q\|_1^2. \]

 

• Let \(C \subseteq \mathbb{R}^n\) be a nonempty closed convex set. The Euclidean projection onto \(C\) is defined as \[ \Pi_C(x) = \arg\min_{y \in C} \|x-y\|_2. \] For any \(x,y \in \mathbb{R}^n\), \[ \|\Pi_C(x)-\Pi_C(y)\|_2 \leq \|x-y\|_2. \]