Introduction to High-Dimensional Statistics, 2nd Edition

Appendix D

Subdifferentials of Convex Functions

D.1 Subdifferentials and Subgradients

A function F : ℝⁿ → ℝ is convex if F (λx + (1 - λ)y) ≤ λ F (x) + (1 - λ)F (y) for all x, y ∈ ℝⁿ and λ ∈ [0,1]. An equivalent definition is that the epigraph {(x,y), x ∈ ℝⁿ, y ∈ [F(x), +∞ [} is a convex subset of ℝⁿ⁺¹.

Lemma D.1 When the function F : ℝⁿ → ℝ is convex and differentiable, we have

$F\left(y\right)\ge F\left(x\right)+\langle \nabla F\left(x\right),y-x\rangle ,forallx,y\in {ℝ}^n.$

Proof. Let x, h ∈ ℝⁿ, and define f : ℝ → ℝ by f(t) = F (x + th). Since F is differentiable, so is f and f'(t) = <∇F(x + th), h>. By Taylor’s expansion, we have for some t* ∈ [0,1]

$F\left(x+h\right)-F\left(x\right)=\langle \nabla F\left(x+t*h\right),h\rangle =f^{\prime }\left(t*\right).$

Since

$f\left(\lambda t+\left(1-\lambda \right)s\right)=F(\lambda \left(x+th\right)+\left(1-\lambda \right)(x+sh$