Calculus and Optimization

TL;DR

1. Gradient $\nabla f(w)$ = vector of partial derivatives; points in the direction of steepest ascent. At a minimum of a differentiable function: $\nabla f=0$.
2. Two gradients to know by heart: ${\nabla }_w\Vert Xw-y{\Vert }^2=2X^{\top }(Xw-y)$ and ${\nabla }_w\lambda \Vert w{\Vert }^2=2\lambda w$.
3. Gradient descent: $w_{t+1}=w_t-\eta \nabla f(w_t)$. SGD uses the gradient of one random data point.
4. Convex: every local minimum is global. $\mu$-strongly convex: curved at least like $\frac{\mu }{2}\Vert w{\Vert }^2$, unique minimizer. $L$-Lipschitz: $|f(a)-f(b)|\le L\Vert a-b\Vert$ (slope at most $L$). $\beta$-smooth: the gradient is $\beta$-Lipschitz.
5. Logs: $\ln (ab)=\ln a+\ln b$, $\ln (a^k)=k\ln a$, $e^{\ln x}=x$; $\frac{1}{2}\ln \frac{1-\epsilon }{\epsilon }$ is AdaBoost’s vote.

Derivatives and the chain rule

$f(x)$	$f^{\prime }(x)$
$x^k$	$k{x}^{k-1}$
$e^{ax}$	$a{e}^{ax}$
$\ln x$	$1/x$
$|x|$	$\mathrm{sign}(x)$ for $x\ne 0$ (not differentiable at 0)
$\max (0,x)$ (ReLU, hinge)	0 for $x<0$, 1 for $x>0$

Chain rule: $(g(h(x)){)}^{\prime }=g^{\prime }(h(x))h^{\prime }(x)$. Example: $\frac{d}{dw}(y-wx{)}^2=2(y-wx)\cdot (-x)$.

Minimizing a one-dimensional function

$f(w)=(w-3{)}^2+2w^2$: $f^{\prime }(w)=2(w-3)+4w=6w-6=0\Rightarrow w=1$. The "$+2w^2$" (a ridge penalty) pulls the minimizer from 3 towards 0.

Gradients

Gradient

For $f:{\mathbb{R}}^d\to \mathbb{R}$: $\nabla f(w)=(\frac{\partial f}{\partial w_1},\dots ,\frac{\partial f}{\partial w_d})$. It points in the direction of steepest increase; $-\nabla f$ is the direction of steepest descent.

Gradients used in the course

• ${\nabla }_w⟨a,w⟩=a$.
• ${\nabla }_w\Vert w{\Vert }^2=2w$.
• ${\nabla }_w\Vert Xw-y{\Vert }^2=2X^{\top }(Xw-y)$.
• ${\nabla }_w\frac{1}{2}{w}^{\top }Aw=Aw$ for symmetric $A$.

Setting ${\nabla }_w(\Vert Xw-y{\Vert }^2)=0$ gives the normal equations $X^{\top }Xw=X^{\top }y$. For ridge, ${\nabla }_w(\frac{1}{n}\Vert Xw-y{\Vert }^2+\lambda \Vert w{\Vert }^2)=0$ gives $(X^{\top }X+n\lambda I)w=X^{\top }y$ (L5).

Gradient descent and SGD

Update rules

• GD: $w_{t+1}=w_t-\eta \nabla R_n(w_t)$ with step size (learning rate) $\eta$.
• SGD: pick a random data point $i$ and use $\nabla \ell (w_t;x_i,y_i)$ instead of the full gradient.
• Least squares: $w_{t+1}=w_t-\eta X^{\top }(X{w}_t-y)$.

Where it appears: the perceptron is SGD on the linear loss (L2); stability of GD and SGD (L4); implicit regularization of GD (L8).

Memory aid

“Walk downhill”: minus the gradient, times a step size. Too large a step overshoots ($\eta \ge 2/\beta$ can diverge), too small is slow.

Convexity, Lipschitz, smoothness

Convex

$f$ is convex if the line between two points of its graph lies above the graph: $f(ta+(1-t)b)\le tf(a)+(1-t)f(b)$ for $t\in [0,1]$. Equivalent for twice differentiable $f$: $f^{\prime \prime }\ge 0$ (Hessian PSD). Every local minimum is a global minimum.

Examples: $x^2$, $|x|$, $e^x$, hinge $\max (0,1-x)$, logistic $\ln (1+e^{-x})$ are convex; the 0-1 loss is not, which is why surrogate losses are used.

Strongly convex, Lipschitz, smooth

• $\mu$-strongly convex: $f(w)-\frac{\mu }{2}\Vert w{\Vert }^2$ is still convex; the function curves up at least like a parabola with curvature $\mu$. Example: $\lambda \Vert w{\Vert }^2$ is $2\lambda$-strongly convex. Consequence: a unique minimizer.
• $L$-Lipschitz: $|f(a)-f(b)|\le L\Vert a-b\Vert$; for differentiable $f$ the same as $\Vert \nabla f\Vert \le L$. Example: hinge and logistic loss are 1-Lipschitz in the score, the squared loss is not (on an unbounded domain).
• $\beta$-smooth: the gradient is $\beta$-Lipschitz, $f^{\prime \prime }\le \beta$: no sharp kinks.

Where it appears: stability of ERM with strongly convex losses $4L^2/(\mu n)$ and of regularized ERM $2L^2/(\lambda n)$ (L4, L5); Lipschitz constant as robustness measure (L8).

Memory aid

Lipschitz = speed limit (the function cannot change faster than $L$). Strongly convex = bowl (the minimum is sharp and unique, so one changed data point moves it only a little: stability). Smooth = no kinks (the slope changes slowly, so gradient steps are safe).

Logs and exponentials

Rules

$\ln (ab)=\ln a+\ln b$, $\ln (a/b)=\ln a-\ln b$, $\ln (a^k)=k\ln a$, $\ln 1=0$, $e^{\ln x}=x$, $e^{a+b}=e^a{e}^b$. Useful values: $\ln 2\approx 0.693$, $\ln 10\approx 2.303$, $\ln 20\approx 3.00$, $e^{-1}\approx 0.368$. $\sqrt{e^x}=e^{x/2}$. Solving $e^{-cn}=\delta$: $n=\ln (1/\delta )/c$.

AdaBoost's vote

$\alpha =\frac{1}{2}\ln \frac{1-\epsilon }{\epsilon }$: for $\epsilon =0.25$: $\frac{1}{2}\ln 3\approx 0.549$; $\epsilon =0.5$: $\alpha =0$ (a coin flip gets no vote); $\epsilon \to 0$: $\alpha \to \infty$. Weight update: $e^{\alpha }=\sqrt{(1-\epsilon )/\epsilon }$, so a misclassified point is multiplied by $\sqrt{3}$ when $\epsilon =0.25$ (L6).

argmin, sup, inf

• ${\min }_{w}f(w)$ is the smallest value, ${\mathrm{argmin}}_{w}f(w)$ the point where it is attained. ERM: $f_n={\mathrm{argmin}}_{f\in \mathcal{F}}{R}_n(f)$.
• $\sup$ (supremum) is the smallest upper bound, like a maximum that need not be attained (${\sup }_{x<1}x=1$). $\inf$ likewise for lower bounds. The Bayes risk $R^{\ast }={\inf }_{f}R(f)$; uniform convergence looks at ${\sup }_{f\in \mathcal{F}}|R(f)-R_n(f)|$, the worst function in the class.

Memory aid

A $\sup$ over a class means “the worst case in the class”: if even the worst function has a small gap between training and true risk, then so does the one ERM picks.

Self-check

Question cards (4)

Minimize $f(w)=(w-4{)}^2+w^2$.

Answer

$2(w-4)+2w=0\Rightarrow w=2$.

What is ${\nabla }_w\frac{1}{n}\Vert Xw-y{\Vert }^2$?

Answer

$\frac{2}{n}{X}^{\top }(Xw-y)$.

AdaBoost round with $\epsilon =0.1$: compute $\alpha$ and the factor for a misclassified point.

Answer

$\alpha =\frac{1}{2}\ln 9=\ln 3\approx 1.10$; factor $e^{\alpha }=3$ (before normalizing).

Is the squared loss $(y-w{)}^2$ Lipschitz in $w$ on $\mathbb{R}$?

Answer

No, its derivative $2(w-y)$ is unbounded. On a bounded domain it is.

Related

• Math overview · Linear Algebra · Combinatorics and Asymptotics