Definition

A differential function f:Rn→Rf: \mathbb{R}^n \rightarrow \mathbb{R} is β\beta-smooth if

∥∇f(y)−∇f(x)∥≤β∥y−x∥ \|\nabla f(y) - \nabla f(x) \| \le \beta \|y - x\|

where ∥⋅∥\|\cdot \| is ℓ2\ell_2 norm.

Theorem 1.

A twice continuously differential function f:Rn→Rf : \mathbb{R}^n \rightarrow \mathbb{R} is β\beta-smooth if and only if

vT∇2f(z)v≤β∥v∥2 v^T \nabla^2 f(z) v \le \beta \|v\|^2

for any z,v∈Rnz, v \in \mathbb{R}^n.

Proof.

  1. (ONLY IF). vT∇2f(z)v≤β∥v∥2v^T \nabla^2 f(z) v \le \beta \|v\|^2 is equivalent to that the maximum eigenvalue of ∇2f(z)\nabla^2 f(z) is at most β\beta. Let vv be the eigenvector of ∇2f(z)\nabla^2 f(z). By mean value theorem

    ∂f∂xi(z+v)−∂f∂xi(z)=∑j=1n(∂f∂xi∂xj(c))vj \frac{\partial f}{\partial x_i} (z + v) - \frac{\partial f}{\partial x_i} (z) = \sum_{j = 1}^n \left( \frac{\partial f}{\partial x_i \partial x_j} (c) \right) v_j

    For some cc between zz and z+vz + v. As ff is twice continuously differentiable, for any given ϵ>0\epsilon > 0, ∃v\exists v that is small enough, such that

    ∣∂f∂xi(z+v)−∂f∂xi(z)∣∈∣∑j=1n(∂f∂xi∂xj(z))vj∣±ϵn \left| \frac{\partial f}{\partial x_i} (z + v) - \frac{\partial f}{\partial x_i} (z) \right| \in \left| \sum_{j = 1}^n \left( \frac{\partial f}{\partial x_i \partial x_j} (z) \right) v_j \right| \pm \frac{\epsilon}{n}

    Hence,

    ∣∇f(z+v)−∇f(z)∣∈∣∇2f(z)v∣+ϵ | \nabla f(z + v) - \nabla f(z) | \in |\nabla^2 f(z) v| + \epsilon

    By equivalence of ℓ1\ell_1-norm and ℓ2\ell_2 norm, we get for vv small enough,

    ∥∇f(z+v)−∇f(z)∥∈∥∇2f(z)v∥+ϵ \| \nabla f(z + v) - \nabla f(z) \| \in \| \nabla^2 f(z) v \| + \epsilon

    As ϵ\epsilon can be arbitrary small, it concludes that

    ∥∇2f(z)v∥≤β∥v∥ \| \nabla^2 f(z) v \| \le \beta \|v \|

    which is equivalent to that the eigenvalues of ∇2f(z)\nabla^2 f(z) is at most β\beta.

  2. (IF). We prove a stronger result that

    ∥∇f(y)−∇f(x)∥⋅∥∇f(y)−∇f(x)∥≤β(∇f(y)−∇f(x))T(y−x) \| \nabla f(y) - \nabla f(x) \| \cdot \| \nabla f(y) - \nabla f(x) \| \le \beta \left( \nabla f(y) - \nabla f(x) \right)^T (y - x)

    By Cauchy-Schwartz inequality, we have

    (∇f(y)−∇f(x))T(y−x)≤∥∇f(y)−∇f(x)∥⋅∥y−x∥ \left( \nabla f(y) - \nabla f(x) \right)^T (y - x) \le \| \nabla f(y) - \nabla f(x) \| \cdot \| y - x \|

    which will finish our proof.

    By Taylor series expansion, we have

    f(y)=f(x)+∇f(x)T(y−x)+12(y−x)T∇2f(z)(y−x)≤f(x)+∇f(x)T(y−x)+12β∥y−x∥2 \begin{aligned} f(y) & = f(x) + \nabla f(x)^T (y - x) + \frac{1}{2} (y - x)^T \nabla^2 f(z) (y - x) \\ &\le f(x) + \nabla f(x)^T (y - x) + \frac{1}{2} \beta \| y - x \|^2 \end{aligned}

    for some zz between xx and yy. The inequality holds since vT∇2f(z)v≤β∥v∥2v^T \nabla^2 f(z) v \le \beta \|v\|^2 for any v∈Rnv \in \mathbb{R}^n.

    By symmetry, we get

    f(x)≤f(y)+∇f(y)T(x−y)+12β∥y−x∥2 \begin{aligned} f(x) &\le f(y) + \nabla f(y)^T (x - y) + \frac{1}{2} \beta \| y - x \|^2 \end{aligned}

    Summing up the two inequalities, we obtain

    (∇f(y)−∇f(x))T(y−x)T≤β∥y−x∥2 \left( \nabla f(y) - \nabla f(x) \right)^T (y - x)^T \le \beta \| y - x \|^2

□\square

Theorem 2.

If ff is β\beta-smooth, then for x,y∈Rnx, y \in \mathbb{R}^n, we have

f(y)≤f(x)+∇f(x)T(y−x)+12β∥y−x∥2 f(y) \le f(x) + \nabla f(x)^T (y - x) + \frac{1}{2} \beta \| y - x \|^2

Proof. By fundamental theorem of calculus,

f(y)−f(x)−∇f(x)T(y−x)=∫01∇f(x+t(y−x))T(y−x) dt−∇f(x)T(y−x)=∫01(∇f(x+t(y−x))−∇f(x))T(y−x) dt≤∫01∥∇f(x+t(y−x))−∇f(x)∥⋅∥y−x∥ dt≤∫01βt∥y−x∥⋅∥y−x∥ dt≤12β∥y−x∥2 \begin{aligned} f(y) - f(x) - \nabla f(x)^T (y - x) &= \int_{0}^1 \nabla f(x + t(y - x))^T(y - x) \ dt - \nabla f(x)^T (y - x) \\ &= \int_{0}^1 \left( \nabla f(x + t(y - x)) - \nabla f(x) \right)^T(y - x) \ dt \\ &\le \int_{0}^1 \| \nabla f(x + t(y - x)) - \nabla f(x) \| \cdot \| y - x \| \ dt \\ &\le \int_{0}^1 \beta t \| y - x \| \cdot \| y - x \| \ dt \\ &\le \frac{1}{2} \beta \| y - x \|^2 \end{aligned}

□\square