optimisation-theory

Optimisation

Resources:

• Numerical Methods I - CS 357 @ UIUC Textbook
• EE364a: Convex Optimization I, EE364b - Convex Optimization II
• EE227BT: Convex Optimization, EE 227C (Spring 2018) Convex Optimization and Approximation

First-order Methods

Momentum: Instead of just using past gradient, create a weighted average of all the past gradients.

• $m_{t+1}=\beta m_t+g_t$, where $m_t$ is the momentum and $g_t$ is the gradient of the objective function at step t, and $0<\beta <1$.
• ${\theta }_{t+1}={\theta }_t-{\eta }_{t+1}{m}_{t+1}$

• Why does using past gradients reach convergence faster?

• Problem with simple momentum is that it not slow down enough at the bottom of the valley.

Nesterov Momentum:

• $m_{t+1}=\beta m_t-{\eta }_t\nabla \mathcal{L}({\theta }_t+\beta m_t)$
• ${\theta }_{t+1}={\theta }_t+m_{t+1}$
• For each step, Nesterov’s momentum uses gradient at new location ${\theta }_t+\beta m_t$ instead of current location.

Second order Methods

Newton’s method: ${\theta }_{t+1}={\theta }_t-{\eta }_t{\mathrm{H}}_t^{-1}{g}_t$, where ${\mathrm{H}}_t=\mathrm{H}({\theta }_t)={\nabla }^2\mathcal{L}({\theta }_t)$.

• when Hessian is convex, the descent direction is chosen as $-{\mathrm{H}}_t^{-1}{g}_t$
• Can be derived using taylor approximation of $\mathcal{L}(\theta )$ around ${\theta }_t$, and finding the minimum.
• BFGS
• Trust region: Do the opposite of line search, i.e. instead of determining the direction and then travelling optimally. Determine the distance first, and then solve for optimal direction.
  • around parameter ${\theta }_t$ determine a Region ${\mathcal{R}}_t$, where objective function can be approximated as $M_t(\delta )$ locally as a quadratic using taylor approximation.
  • At each step, we solve: ${\delta }^{\ast }=\arg \underset{\delta \in {\mathcal{R}}_t}{\min }M{(}_t(\delta ))$, where $M_t(\delta )=\mathcal{L}({\theta }_t)+g_t^{\top }\delta +\frac{1}{2}{\delta }^{\top }{\mathrm{H}}_t\delta$.
  • If ${\mathcal{R}}_t$ is taken as a ball of radius r, then adding a Lagrange multiplier to M, ${\delta }^{\ast }=\arg \underset{{}_{\delta }}{\min }M(\delta )+\lambda \Vert \delta {\Vert }_2^2$.
  • Solve this using $\delta =-(H+\lambda I{)}^{-1}g$, i.e. $\lambda$ can be taken such that all eigenvalues are non-negative, and convex optimization methods like Momentum can be applied.

SGD

Lagrange Multipliers: Calculus III - Lagrange Multipliers

Steepest Descent: Done using different norms: Lp norms.

derive dual norm $\Vert a{\Vert }_q^{†}$ of $a^{T}b$ subject to arbitrary $L_p$ norm $\Vert b{\Vert }_p=1$.

Dual formulation of steepest descent

$$\begin{array}{c}\underset{\Delta w\in {\mathbb{R}}^n}{\mathrm{argmin}}\left[g^{\top }\Delta w+\frac{\lambda }{2}\Vert \Delta w{\Vert }^2\right]=-\frac{\Vert g{\Vert }^{†}}{\lambda }\cdot \arg \underset{t\in {\mathbb{R}}^n:\Vert t\Vert =1}{\min }{g}^{\top }t\end{array}$$

• From the definition of dual norm, $\Vert g{\Vert }^{†}=\underset{\Vert b\Vert =1}{\max }{g}^{\top }b$ which implies, for any unit vector $\frac{w}{\Vert w\Vert }$, $g^{\top }w\le \Vert g{\Vert }^{†}\Vert w\Vert$
• Flipping the sign and adding the extra term: $-\Vert g{\Vert }^{†}\Vert \Delta w\Vert +\frac{\lambda }{2}\Vert \Delta w{\Vert }^2\le g^{\top }\Delta w+\frac{\lambda }{2}\Vert \Delta w{\Vert }^2$
• Our goal is to find $\Delta w$ to minimise $-\Vert g{\Vert }^{†}\Vert \Delta w\Vert +\frac{\lambda }{2}\Vert \Delta w{\Vert }^2$. Let $u=\Vert \Delta w\Vert$, taking the gradient, we get $u=\Vert g{\Vert }^{†}/\lambda$.
• Now, from dual norm, $g^{\top }\frac{\Delta w}{\Vert \Delta w\Vert }\ge -\Vert g{\Vert }^{†}=-\underset{t\in {\mathbb{R}}^n:\Vert t\Vert =1}{\max }{g}^{\top }t$. This becomes an equality when $\frac{\Delta w}{\Vert \Delta w\Vert }=-\underset{t\in {\mathbb{R}}^n:\Vert t\Vert =1}{\mathrm{argmax}}{g}^{\top }t$.
• Thus $\Delta w=-\Vert \Delta w\Vert \underset{t\in {\mathbb{R}}^n:\Vert t\Vert =1}{\mathrm{argmax}}{g}^{\top }t=-\frac{\Vert g{\Vert }^{†}}{\lambda }\underset{t\in {\mathbb{R}}^n:\Vert t\Vert =1}{\mathrm{argmax}}{g}^{\top }t$

For $L_2$ based norm, dual norm = standard $L_2$ norm $\Vert g{\Vert }_2$ and $\arg \underset{\Vert t{\Vert }_2=1}{\max }{g}^{\top }t=\frac{g}{\Vert g\Vert }$, then $\Delta w=-\frac{\Vert g{\Vert }_2}{\lambda }$. This is the standard Gradient descent formula.

For $L_{\infty }$ based norm, dual norm = $L_1$ norm $\Vert g{\Vert }_1$ and $\underset{\Vert t{\Vert }_{\infty }=1}{\mathrm{argmax}}{g}^{\top }t=\text{sign}(g)$, then $\Delta w=-\left(\frac{\Vert g{\Vert }_1}{\lambda }\right)\text{sign}(g)$. Note that, this is equivalent to Adam update when setting the parameters ${\beta }_1,{\beta }_2,ϵ=0$. So, direction depends only on the sign and not the magnitude.

EM