Differentiable Functions | Block Relaxation Algorithms in Statistics -- Part II

II.1.4.3: Differentiable Functions

We first show that differentiable majorizations of differentiable functions must have certain properties at the support point.

Theorem: Suppose $\ f$ and $g$ are differentiable at $y$ . If $g$ majorizes $f$ at $y$ , then

$g(y)=f(y)$ ,
$g'(y)=f'(y)$ ,

If $f$ and $g$ are twice differentiable at $y$ , then in addition

$g''(y)\geq f''(y)$ ,

and if $g$ majorizes $f$ strictly

$g''(y)>f''(y)$ .

Proof: If $g$ majorizes $f$ at $y$ then $g-f$ has a minimum at $y$ . Now use the familiar necessary conditions for the minimum of a differentiable function, which say the derivative at the minimum is zero and the second derivative is non-negative. QED

The conditions in the theorem are only necessary because they are local, they only say something about the value of $g$ and its derivatives at $y$ . But majorization is a global relation to make global statements we need conditions like convexity. We already know that if $g-f$ is convex with a minimum at $y$ equal to zero, then $g$ majorizes $f$ at $y$ . For differentiable $f$ and $g$ this means that if $f-g$ is convex then $g$ majorizes $f$ at $y$ if and only if $f(y)=g(y)$ and $f'(y)=g'(y)$ . And for twice-differentiable $f$ and $g$ with $f''(x)\geq 0$ for all $x$ again $g$ majorizes $f$ at $y$ if and only if $f(y)=g(y)$ and $f'(y)=g'(y)$ .

In the case of majorization at a single $y$ we have $f'(y)=g'(y)$ for differentiable functions. If $g$ majorizes $f$ on $\mathcal{Y}\subseteq\mathcal{X}$ then $g(x,y)-f(x)\geq 0$ for all $x\in\mathcal{X}$ and all $y\in\mathcal{Y}$ . Thus $0=g(y,y)-f(y)=\min_{x\in\mathcal{X}}g(x,y)-f(x)$ for each $y\in\mathcal{Y}$ . In addition $f(x)=g(x,x)=\min_{y\in\mathcal{Y}}g(x,y).$

In the case of majorization at a single $y$ we had $f'(y)=g'(y)$ for differentiable functions. In general the function $f$ defined by $f(x)=\min_{y\in\mathcal{Y}} g(x,y)$ is not differentiable. If the partials $\mathcal{D}_1g$ are continuous then the derivative at $x$ in the direction $z$ satisfies $df_z(x)=\min_y\{z'D_1g(x,y)\mid f(x)=g(x,y)\}.$ In the case of strict majorization this gives $\mathcal{D}f(x)=\mathcal{D}_1g(x,x).$

Theorem \ref{T:nes} can be generalized in many directions if differentiability fails. If $f$ has a left and right derivatives in $y$ , for instance, and $g$ is differentiable, then $f'_R(y)\leq g'(y)\leq f'_L(y).$

If $f$ is convex, then $f'_L(y) \leq f'_R(y)$ , and $f'(y)$ must exist in order for a differentiable $g$ to majorize $f$ at $y$ . In this case $g'(y)=f'(y)$ .

For nonconvex $f$ more general differential inclusions are possible using the four Dini derivatives of $f$ at $y$ [see, for example, McShane, 1944, Chapter V].

Locally Lipschitz functions, Proximinal and Frechet and Clarke subgradients, sandwich and squeeze theorems

One-sided Chebyshev. Find $g\in\mathcal{G}$ such that $g\geq f$ , $g(y)=f(y)$ and $\sup_x|g(x)-f(x)|$ is minimized. For instance $\mathcal{G}$ can be the convex functions, or the polynomials of a certain degree, or piecewise linear functions or splines.