Optimisation for Data Science HT25, Useful miscellany

\[g^\top v - \frac{1}{2L} \vert \vert g \vert \vert ^2 = \frac{L}{2}( \vert \vert v \vert \vert ^2 - \vert \vert v - \frac{1}{L} g \vert \vert ^2)\]

---

E.g. when $g = \nabla f(x^k)$ and $v = x^k - x^\ast$, this becomes

\[\begin{aligned} \nabla f(x^k)^\top (x^k - x^\ast) - \frac{1}{2L} \vert \vert x^k - x^\ast \vert \vert ^2 &= \frac{L}{2}( \vert \vert x^k - x^\ast \vert \vert ^2 - \vert \vert x^k - x^\ast - \frac{1}{L}\nabla f(x^k) \vert \vert ^2) \\\\ &= \frac L 2( \vert \vert x^k - x^\ast \vert \vert ^2 - \vert \vert x^{k+1} - x^\ast \vert \vert ^2) \end{aligned}\]

which can then be used in a telescoping sum.

\[\begin{aligned} g^\top v - \frac{1}{2L} \vert \vert g \vert \vert ^2 &= \frac{L}{2} \left( \frac{2}{L} \langle g, v \rangle - \frac{1}{L^2} \langle g, g \rangle \right) \\\\ &= \frac{L}{2}\left( \langle v, v\rangle - \langle v, v \rangle + \frac{2}{L} \langle g, v \rangle - \frac{1}{L^2} \langle g, g\rangle \right) \\\\ &= \frac{L}{2}\left( \langle v, v\rangle - \langle v, v \rangle + \frac{1}{L} \langle g, v \rangle + \frac{1}{L} \langle g, v \rangle - \frac{1}{L^2} \langle g, g\rangle \right) \\\\ &= \frac{L}{2}\left( \langle v, v\rangle - \langle v, v \rangle + \left\langle \frac{1}{L} g, v \right\rangle + \left\langle v, \frac{1}{L} g \right\rangle - \left\langle \frac{1}{L} g, \frac{1}{L} g\right\rangle \right) \\\\ &= \frac{L}{2} \left(\langle v, v\rangle - \left\langle v - \frac 1 L g, v - \frac 1 L g \right\rangle\right) \\\\ &=\frac{L}{2}( \vert \vert v \vert \vert ^2 - \vert \vert v - \frac{1}{L} g \vert \vert ^2) \end{aligned}\]

\[f(x + d) = f(x) + \int^1 _ 0 \nabla f(x + td)^\top d \text dt\]

Consider the function $g : [0, 1] \to \mathbb R$ defined by $g(t) = f(x + td)$. Then by the fundamental theorem of calculus,

\[g(1) - g(0) = \int^1 _ 0 g'(t) \text dt\]

Hence

\[f(x + d) = f(x) + \int^1 _ 0 \nabla f(x + td)^\top d \text dt\]

\[\vert \vert a + b \vert \vert ^2 \le 2( \vert \vert a \vert \vert ^2 + \vert \vert b \vert \vert ^2)\]

\[\sqrt{a + b} \le \sqrt a + \sqrt b\]

\[\kappa(A) =\frac{\lambda _ \text{max} }{\lambda _ \text{min} }\]

\[\mathbf J(f)^\top (\nabla g \circ f)\]

e.g. $\nabla ( \vert \vert u - 2x \vert \vert ^2) = 4(u - 2x)$.

\[\nabla f(x) \cdot g'(f(x))\]

$f$ convex?	$f$ increasing?	$g$ convex?	Then $f \circ g$ convex?
0	0	0	Nothing in general
0	0	1	0
0	1	0	0
0	1	1	Nothing in general
1	0	0	1
1	0	1	Nothing in general
1	1	0	Nothing in general
1	1	1	1

Suppose:

• $f$ is a real convex function
• $x _ 1, \ldots, x _ n$ are points in the domain
• $\alpha _ 1, \ldots, \alpha _ n$ are positive weights

Then:

• $f\left(\frac{\sum \alpha _ i x _ i}{\sum \alpha _ i}\right) \le \frac{\sum \alpha _ i f(x _ i)}{\sum \alpha _ i}$, or
• $f(\mathbb E[x]) \le \mathbb E[f(x)]$

Suppose:

• $p$ and $q$ are such that $\frac 1 p + \frac 1 q = 1$
• $x _ 1, \ldots, x _ n$ and $y _ 1, \ldots, y _ n$ are arbitrary real or complex numbers

Then:

\[\sum^n _ {i = 1} \vert x _ i y _ i \vert \le \left(\sum^n _ {i = 1} \vert x _ i \vert ^p\right)^{1/p} \left(\sum^n _ {i = 1} \vert y _ i \vert ^q\right)^{1/q}\]

The Cauchy-Schwarz inequality corresponds to the case where $p = 1/2, q = 1/2$.

Let $u _ i = e^{x _ i}$ and $v _ i = e^{y _ i}$. Therefore

\[\begin{aligned} f((1-\lambda)x + \lambda y) &= \log\left( \sum^n _ {i=1} e^{(1 - \lambda)x _ i + \lambda y _ i} \right) \\\\ &= \log\left( \sum^n _ {i=1} u _ i^{(1-\lambda)} v _ i^{\lambda} \right) \\\\ &\le \log\left(\left(\sum^n _ {i=1} u _ i^{(1 - \lambda) \cdot \frac{1}{1-\lambda} }\right)^{1 - \lambda}\cdot \left(\sum^n _ {i=1} v _ i^{\lambda \cdot \frac{1}{\lambda} }\right)^\lambda\right) \\\\ &\le (1 - \lambda)\log\left(\sum^n _ {i = 1} u _ i^{}\right) + \lambda \log\left(\sum^n _ {i=1} v _ i\right) \end{aligned}\]

as required.

• $f : \mathbb R^d \to \mathbb R$ is $L$-smooth iff for all $x$, $\lambda _ \text{max}(\nabla^2 f(x)) \le L$.

• This is equivalent to the Hessian being uniformly bounded above by $L$, i.e. for all $x$, $ \vert \vert \nabla^2 f(x) \vert \vert \le L$.

• $f : \mathbb R^d \to \mathbb R$ is $\gamma$-strongly convex iff for all $x$, $\lambda _ \text{min}(\nabla^2 f(x)) \ge \gamma$.
• This is equivalent to the inverse Hessian being uniformly bounded above by $1/\gamma$, i.e. for all $x$, $ \vert \vert \nabla^2 f(x))^{-1} \vert \vert \ge \gamma$.

The sum is $\sum \lambda _ i L _ i$-smooth.

It is $L \vert \vert A \vert \vert ^2$-smooth (i.e. $L \sigma _ \max^2$ where $\sigma _ \max$ is the largest singular value).