Smoothness

Definition

A differentiable $f$ is $\beta$-smooth if $\Vert \nabla f(x)-\nabla f(y)\Vert \le \beta \Vert x-y\Vert$. It is an upper bound on the curvature, while strong convexity is a lower bound.

Formula

For convex, $\beta$-smooth, $L$-Lipschitz losses and step sizes ${\eta }_t<2/\beta$ (GD or SGD, $T$ steps):

$${\Delta }_{\sup }\le \frac{2L^2}{n}\sum _{t=1}^T{\eta }_t$$

Examples: the squared loss $\frac{1}{2}(⟨x,w⟩-y{)}^2$ is $\Vert x{\Vert }^2$-smooth, the logistic loss is smooth for bounded $\Vert x\Vert$. Key step in the proof: a gradient step is non-expansive, $\Vert (w-\eta \nabla g(w))-(v-\eta \nabla g(v))\Vert \le \Vert w-v\Vert$.

Appears in

• Lecture 4, definition and examples
• Lecture 4, Theorem 4 and proof
• Lecture 4, Theorems 5 and 6

Related concepts

• Strong Convexity
• Stochastic Gradient Descent
• Algorithmic Stability