Cheatsheet: Convexity, Smoothness & Strong Convexity Equivalences

---

1 Convexity Equivalences

For a twice-differentiable $f:D\to \mathbb{R}$ on convex $D\subseteq {\mathbb{R}}^n$, the following are equivalent:

1. Basic Convexity: $f(\theta x+(1-\theta )y)\le \theta f(x)+(1-\theta )f(y)$, $\mathrm{\forall }\theta \in [0,1]$.
2. First-Order Condition (FOC): $f(y)\ge f(x)+\mathrm{\nabla }f(x{)}^{\mathrm{\top }}(y-x)$, $\mathrm{\forall }x,y\in D$.
3. Gradient Monotonicity (GM): $⟨\mathrm{\nabla }f(x)-\mathrm{\nabla }f(y),x-y⟩\ge 0$, $\mathrm{\forall }x,y\in D$.
4. Second-Order Condition (SOC): ${\mathrm{\nabla }}^{2}f(x)⪰0$ (Hessian PSD).

Convexity $⟺$ FOC

($\Rightarrow$) Assume $f$ convex. For $\theta \in (0,1]$:

$$f(x+\theta (y-x))\le (1-\theta )f(x)+\theta f(y)$$$$⟹\frac{f(x+\theta (y-x))-f(x)}{\theta }\le f(y)-f(x)$$

Take $\theta \to 0$: $\mathrm{\nabla }f(x{)}^{\mathrm{\top }}(y-x)\le f(y)-f(x)$.

($\Leftarrow$) Assume FOC holds. Let $z=\theta x+(1-\theta )y$:

$$f(x)\ge f(z)+\mathrm{\nabla }f(z{)}^{\mathrm{\top }}(x-z)$$$$f(y)\ge f(z)+\mathrm{\nabla }f(z{)}^{\mathrm{\top }}(y-z)$$

Multiply by $\theta$ and $(1-\theta )$ respectively and add:

$$\theta f(x)+(1-\theta )f(y)\ge f(z)+\mathrm{\nabla }f(z{)}^{\mathrm{\top }}(\underset{=0}{\underbrace{\theta x+(1-\theta )y-z}})=f(z)$$

FOC $⟺$ GM

($\Rightarrow$) Write FOC twice swapping $x,y$ and add:

$$f(y)\ge f(x)+\mathrm{\nabla }f(x{)}^{\mathrm{\top }}(y-x)$$$$f(x)\ge f(y)+\mathrm{\nabla }f(y{)}^{\mathrm{\top }}(x-y)$$$$⟹0\ge \mathrm{\nabla }f(x{)}^{\mathrm{\top }}(y-x)+\mathrm{\nabla }f(y{)}^{\mathrm{\top }}(x-y)⟹⟨\mathrm{\nabla }f(x)-\mathrm{\nabla }f(y),x-y⟩\ge 0$$

($\Leftarrow$) By FTC along $x+t(y-x)$:

$$f(y)-f(x)={\int }_0^1\mathrm{\nabla }f(x+t(y-x){)}^{\mathrm{\top }}(y-x)dt$$

Subtract the tangent at $x$:

$$f(y)-f(x)-\mathrm{\nabla }f(x{)}^{\mathrm{\top }}(y-x)={\int }_0^1(\mathrm{\nabla }f(x_t)-\mathrm{\nabla }f(x){)}^{\mathrm{\top }}(y-x)dt$$

By GM, integrand is $\ge 0$. Thus $f(y)\ge f(x)+\mathrm{\nabla }f(x{)}^{\mathrm{\top }}(y-x)$.

GM $⟺$ SOC

($\Rightarrow$) For $y=x+ϵd$, GM implies $\frac{(\mathrm{\nabla }f(x+ϵd)-\mathrm{\nabla }f(x){)}^{\mathrm{\top }}d}{ϵ}\ge 0$. Take $ϵ\to 0$: $d^{\mathrm{\top }}{\mathrm{\nabla }}^{2}f(x)d\ge 0$.

($\Leftarrow$) By FTC:

$$\mathrm{\nabla }f(y)-\mathrm{\nabla }f(x)={\int }_0^1{\mathrm{\nabla }}^{2}f(x+t(y-x))(y-x)dt$$$$⟹(\mathrm{\nabla }f(y)-\mathrm{\nabla }f(x){)}^{\mathrm{\top }}(y-x)={\int }_0^1(y-x{)}^{\mathrm{\top }}{\mathrm{\nabla }}^{2}f(x_t)(y-x)dt\ge 0$$

---

2 L-Smoothness Equivalences

For a twice-differentiable $f$, the following are equivalent definitions of $L$-smoothness:

1. Lipschitz Continuous Gradient: $\parallel \mathrm{\nabla }f(x)-\mathrm{\nabla }f(y)\parallel \le L\parallel x-y\parallel$, $\mathrm{\forall }x,y\in D$.
2. Alternative (Convexity): $g(x)=\frac{L}{2}\parallel x{\parallel }^2-f(x)$ is convex.
3. Descent Lemma: $f(y)\le f(x)+\mathrm{\nabla }f(x{)}^{\mathrm{\top }}(y-x)+\frac{L}{2}\parallel y-x{\parallel }^2$.
4. Hessian Bound: ${\mathrm{\nabla }}^{2}f(x)⪯L\cdot I$, $\mathrm{\forall }x\in D$.

Lipschitz Gradient $⟺$ Hessian Bound

($\Rightarrow$) Let $v$ be a unit vector. By definition of Hessian:

$${\mathrm{\nabla }}^{2}f(x)v=\underset{h\to 0}{lim}\frac{\mathrm{\nabla }f(x+hv)-\mathrm{\nabla }f(x)}{h}$$

Taking norms and using Lipschitz:

$$\parallel {\mathrm{\nabla }}^{2}f(x)v\parallel \le \underset{h\to 0}{lim}\frac{L\parallel hv\parallel }{h}=L⟹{\mathrm{\nabla }}^{2}f(x)⪯L\cdot I$$

($\Leftarrow$) By FTC on gradient:

$$\parallel \mathrm{\nabla }f(y)-\mathrm{\nabla }f(x)\parallel =\Vert {\int }_0^1{\mathrm{\nabla }}^{2}f(x+t(y-x))(y-x)dt\Vert$$$$\le {\int }_0^1\parallel {\mathrm{\nabla }}^{2}f(x_t){\parallel }_2\cdot \parallel y-x\parallel dt\le L\parallel y-x\parallel$$

Hessian Bound $⟺$ Alternative Definition

$g(x)=\frac{L}{2}\parallel x{\parallel }^2-f(x)$. Compute Hessian:

$${\mathrm{\nabla }}^{2}g(x)=L\cdot I-{\mathrm{\nabla }}^{2}f(x)$$

$g$ is convex $⟺{\mathrm{\nabla }}^{2}g(x)⪰0⟺{\mathrm{\nabla }}^{2}f(x)⪯L\cdot I$.

Alternative $⟺$ Descent Lemma

If $g$ is convex, by standard FOC: $g(y)\ge g(x)+\mathrm{\nabla }g(x{)}^{\mathrm{\top }}(y-x)$. Substitute $g(x)=\frac{L}{2}\parallel x{\parallel }^2-f(x)$, $\mathrm{\nabla }g(x)=Lx-\mathrm{\nabla }f(x)$:

$$\frac{L}{2}\parallel y{\parallel }^2-f(y)\ge \frac{L}{2}\parallel x{\parallel }^2-f(x)+(Lx-\mathrm{\nabla }f(x){)}^{\mathrm{\top }}(y-x)$$

Rearrange:

$$f(y)\le f(x)+\mathrm{\nabla }f(x{)}^{\mathrm{\top }}(y-x)+\frac{L}{2}(\parallel y{\parallel }^2-\parallel x{\parallel }^2-2x^{\mathrm{\top }}(y-x))$$$$=f(x)+\mathrm{\nabla }f(x{)}^{\mathrm{\top }}(y-x)+\frac{L}{2}\parallel y-x{\parallel }^2$$

Direct: Lipschitz Gradient $\Rightarrow$ Descent Lemma

By FTC:

$$f(y)-f(x)-\mathrm{\nabla }f(x{)}^{\mathrm{\top }}(y-x)={\int }_0^1(\mathrm{\nabla }f(x_t)-\mathrm{\nabla }f(x){)}^{\mathrm{\top }}(y-x)dt$$

Apply Cauchy-Schwarz and Lipschitz:

$$\le {\int }_0^1\parallel \mathrm{\nabla }f(x_t)-\mathrm{\nabla }f(x)\parallel \cdot \parallel y-x\parallel dt\le {\int }_0^{1}L\cdot t\parallel y-x\parallel \cdot \parallel y-x\parallel dt=\frac{L}{2}\parallel y-x{\parallel }^2$$

---

3 Gradient Descent Convergence

Gradient descent update: $x_{t+1}=x_t-\eta \mathrm{\nabla }f(x_t)$.

3.1 Smooth Functions (L-smooth, step size $\eta =1/L$)

Descent Lemma:

$$f(x_{t+1})\le f(x_t)-\frac{1}{2L}\parallel \mathrm{\nabla }f(x_t){\parallel }^2$$

Convergence to stationary point ($O(1/T)$):

$$\underset{0\le t\le T-1}{min}\parallel \mathrm{\nabla }f(x_t){\parallel }^2\le \frac{2L(f(x_0)-f(x^{\ast }))}{T}$$

3.2 Smooth & Convex Functions ($\eta =1/L$)

Convergence rate ($O(1/T)$):

$$f(x_T)-f(x^{\ast })\le \frac{L}{2T}\parallel x_0-x^{\ast }{\parallel }^2$$

Derivation sketch: From convexity FOC, $\mathrm{\nabla }f(x_t{)}^{\mathrm{\top }}(x_t-x^{\ast })\ge f(x_t)-f(x^{\ast })$. Combined with distance contraction:

$$\parallel x_{t+1}-x^{\ast }{\parallel }^2\le \parallel x_t-x^{\ast }{\parallel }^2-\frac{2}{L}(f(x_{t+1})-f(x^{\ast }))$$

Telescoping sum yields the bound.

3.3 Smooth & Strongly Convex Functions ($\eta =1/L$, $m>0$)

Linear convergence:

$$f(x_T)-f(x^{\ast })\le {(1-\frac{m}{L})}^T[f(x_0)-f(x^{\ast })]$$

Key inequalities:

• Descent Lemma: $f(x_{t+1})\le f(x_t)-\frac{1}{2L}\parallel \mathrm{\nabla }f(x_t){\parallel }^2$
• Gradient Lower Bound (from $m$-strong convexity): $\parallel \mathrm{\nabla }f(x){\parallel }^2\ge 2m(f(x)-f(x^{\ast }))$
• Substitute: $f(x_{t+1})-f(x^{\ast })\le (f(x_t)-f(x^{\ast }))-\frac{m}{L}(f(x_t)-f(x^{\ast }))$
• Condition number $\kappa =L/m$; smaller $\kappa$ gives faster convergence.

---

4 Strong Convexity Equivalences

For a twice-differentiable $f:D\to \mathbb{R}$ on convex $D\subseteq {\mathbb{R}}^n$, the following are equivalent ($m>0$):

1. Alternative Definition: $h(x)=f(x)-\frac{m}{2}\parallel x{\parallel }^2$ is convex.
2. Strong FOC: $f(y)\ge f(x)+\mathrm{\nabla }f(x{)}^{\mathrm{\top }}(y-x)+\frac{m}{2}\parallel y-x{\parallel }^2$.
3. Strong GM: $⟨\mathrm{\nabla }f(x)-\mathrm{\nabla }f(y),x-y⟩\ge m\parallel x-y{\parallel }^2$.
4. Strong SOC: ${\mathrm{\nabla }}^{2}f(x)⪰m\cdot I$, $\mathrm{\forall }x\in D$.

Alternative $⟺$ Strong SOC

Define $h(x)=f(x)-\frac{m}{2}\parallel x{\parallel }^2$. Then:

$$\mathrm{\nabla }h(x)=\mathrm{\nabla }f(x)-mx$$$${\mathrm{\nabla }}^{2}h(x)={\mathrm{\nabla }}^{2}f(x)-mI$$

$h$ convex $⟺{\mathrm{\nabla }}^{2}h(x)⪰0⟺{\mathrm{\nabla }}^{2}f(x)⪰mI$.

Alternative $⟺$ Strong FOC

($\Rightarrow$) $h$ convex $⟹$ standard FOC for $h$:

$$h(y)\ge h(x)+\mathrm{\nabla }h(x{)}^{\mathrm{\top }}(y-x)$$

Substitute $h(x)=f(x)-\frac{m}{2}\parallel x{\parallel }^2$, $\mathrm{\nabla }h(x)=\mathrm{\nabla }f(x)-mx$:

$$f(y)-\frac{m}{2}\parallel y{\parallel }^2\ge f(x)-\frac{m}{2}\parallel x{\parallel }^2+(\mathrm{\nabla }f(x)-mx{)}^{\mathrm{\top }}(y-x)$$

Rearrange quadratic terms:

$$\frac{m}{2}\parallel y{\parallel }^2-\frac{m}{2}\parallel x{\parallel }^2-m{x}^{\mathrm{\top }}(y-x)=\frac{m}{2}\parallel y-x{\parallel }^2$$$$⟹f(y)\ge f(x)+\mathrm{\nabla }f(x{)}^{\mathrm{\top }}(y-x)+\frac{m}{2}\parallel y-x{\parallel }^2$$

($\Leftarrow$) Assume strong FOC holds. Compute:

$$h(y)-h(x)-\mathrm{\nabla }h(x{)}^{\mathrm{\top }}(y-x)=[f(y)-f(x)-\mathrm{\nabla }f(x{)}^{\mathrm{\top }}(y-x)]-\frac{m}{2}\parallel y-x{\parallel }^2$$

By strong FOC, the bracket $\ge \frac{m}{2}\parallel y-x{\parallel }^2$. Thus:

$$h(y)-h(x)-\mathrm{\nabla }h(x{)}^{\mathrm{\top }}(y-x)\ge 0⟹h\text{ convex}$$

Strong FOC $⟺$ Strong GM

($\Rightarrow$) Write strong FOC twice:

$$f(y)\ge f(x)+\mathrm{\nabla }f(x{)}^{\mathrm{\top }}(y-x)+\frac{m}{2}\parallel y-x{\parallel }^2$$$$f(x)\ge f(y)+\mathrm{\nabla }f(y{)}^{\mathrm{\top }}(x-y)+\frac{m}{2}\parallel x-y{\parallel }^2$$

Add and cancel $f(x)+f(y)$:

$$0\ge \mathrm{\nabla }f(x{)}^{\mathrm{\top }}(y-x)+\mathrm{\nabla }f(y{)}^{\mathrm{\top }}(x-y)+m\parallel x-y{\parallel }^2$$$$⟹⟨\mathrm{\nabla }f(x)-\mathrm{\nabla }f(y),x-y⟩\ge m\parallel x-y{\parallel }^2$$

($\Leftarrow$) Fix $x,y$, define $x_t=x+t(y-x)$. By FTC:

$$f(y)-f(x)={\int }_0^1\mathrm{\nabla }f(x_t{)}^{\mathrm{\top }}(y-x)dt$$

Add/subtract $\mathrm{\nabla }f(x)$:

$$=\mathrm{\nabla }f(x{)}^{\mathrm{\top }}(y-x)+{\int }_0^1(\mathrm{\nabla }f(x_t)-\mathrm{\nabla }f(x){)}^{\mathrm{\top }}(y-x)dt$$

Apply strong GM with $u=x_t$, $v=x$:

$$(\mathrm{\nabla }f(x_t)-\mathrm{\nabla }f(x){)}^{\mathrm{\top }}(t(y-x))\ge m\parallel t(y-x){\parallel }^2=m{t}^2\parallel y-x{\parallel }^2$$

Divide by $t$, integrate:

$${\int }_0^1(\mathrm{\nabla }f(x_t)-\mathrm{\nabla }f(x){)}^{\mathrm{\top }}(y-x)dt\ge {\int }_0^{1}mt\parallel y-x{\parallel }^{2}dt=\frac{m}{2}\parallel y-x{\parallel }^2$$$$⟹f(y)\ge f(x)+\mathrm{\nabla }f(x{)}^{\mathrm{\top }}(y-x)+\frac{m}{2}\parallel y-x{\parallel }^2$$