Existence | Block Relaxation Algorithms in Statistics -- Part II

II.5.5.2: Existence of Quadratic Majorizers

We first study the univariate case, following De Leeuw and Lange [2009]. If a quadratic $g$ majorizes a differentiable $f$ over $\mathcal{X}$ at $y$ then we must have $g(x,y)=f(y)+f'(y)(x-y)+\frac12 a(y)(x-y)^2\geq f(x)$ for all $x\in\mathcal{X}.$ Define $\delta(x,y):=\frac{f(x)-f(y)-f'(y)(x-y)}{\frac12(x-y)^2}$ with, for continuity, $\delta(y,y)=f''(y).$ Then we must have $a(y)\geq\sup_{x\in\mathcal{X}}\delta(x,y),$ and consequently a quadratic majorizer exists if and only if $a^\star(y):=\sup_{x\in\mathcal{X}}\delta(x,y)<\infty.$

By the mean value theorem there is some $z$ between $x$ and $y$ such that $\delta(x,y)=f''(z).$ Thus if $f''$ is bounded on $\mathcal{X}$ a quadratic majorizer exists. And if $f''$ is unbounded on $\mathcal{X}$ a quadratic majorizer does not exist.

From Taylor's theorem with integral form of the remainder $\delta(x,y)=2\int_0^1\lambda f''(\lambda y+(1-\lambda)x) d\lambda,$ which gives, by differentiating under the integral sign, $\mathcal{D}_1\delta(x,y)=2\int_0^1\lambda(1-\lambda)f'''(\lambda y+(1-\lambda)x)d\lambda.$

We now generalize some of these results to the multivariate case. If a quadratic $g$ majorizes a differentiable $f$ at $y$ then we must have $g(x,y)=f(y)+(x-y)'\mathcal{D}f(y)+\frac12(x-y)'A(x-y)\geq f(x)$ for all $x.$ This can be rewritten as the infinite system of linear inequalities in the elements of $A$ $(x-y)'A(x-y)\geq 2b(x,y),\tag{1}$ with $b(x,y):=f(x)-f(y)-(x-y)'\mathcal{D}f(y).$ If $A$ satisfies the inequalities $(1)$ , then clearly any $B\gtrsim A$ also satifies them, and the set of all matrices satisfying $(1)$ is a closed convex set $\mathcal{A}(y)$ . Quadratic majorizers at $y$ exist if and only if $\mathcal{A}(y)$ is non-empty. Moreover if $B\gtrsim\mathcal{D}^2f(x)$ for all $x$ then $B\in\mathcal{A}(y)$ for all $y.$ Thus uniform boundedness of the second derivatives is sufficient for quadratic majorizers to exist. Note that if $f$ is concave then $b(x,y)\leq 0$ for all $x$ , and thus any $A\gtrsim 0$ , including $A=0$ , satisfies $(1)$ .

Although $\mathcal{A}(y)$ is convex and closed, it is generally not a simple object. We can give a simple necessary and sufficient condition for it to be non-empty. Choose an arbitrary positive definite $V$ . Define $\delta_V(x,y):=\frac{b(x,y)}{\frac12(x-y)'V(x-y)},$ and $\beta_V(y):=\sup_x\delta_V(x,y).$ Suppose $\beta_V(y)<\infty$ . Take $A=\beta_V(y)V$ . Then for all $x$ we have $(x-y)'A(x-y)=\beta_V(y)(x-y)'V(x-y)\geq 2b(x,y)$ and thus $A$ is a solution of $(1)$ . In fact, any $A\gtrsim\beta_V(y)V$ is a solution. Conversely suppose $\beta_V(y)=\infty$ and $A$ is a solution to $(1)$ , with largest eigenvalue $\lambda_{\text{max}}$ . Then there is a $x$ such that $\delta_V(x,y)>\lambda_{\text{max}}$ , and thus $2b(x,y)>\lambda_{\text{max}}(x-y)'V(x-y)$ , and $(x-y)'A(x-y)>\lambda_{\text{max}} (x-y)'V(x-y)$ , a contradiction. It follows that $\beta_V(y)<\infty$ is necessary and sufficient for $(1)$ to be solvable and for $f$ to have a quadratic majorization at $y$ .

Nothing in this argument assumes that $A$ is positive semidefinite or that $\beta_V(y)\geq 0$ . In fact, for concave $f$ we have $\beta_V(y)\leq 0.$ Also, of course, there is nothing that implies that the $\sup$ is actually attained at some $z$ . Note that the condition $\beta_V(y)<\infty$ is independent of $V$ , although the value $\beta_V(y)$ , if finite, depends on both $V$ and $y.$

We do know, from Taylor's Theorem (see section III.14.2.3), that if $f$ is twice continuously differentiable at $y$ then $\delta_V(x,y)=2\frac{(x-y)'\left\{\int_0^1(1-\tau)\mathcal{D}^2f(x+\tau(y-x))d\tau\right\}(x-y)}{(x-y)'V(x-y)}.$ It follows that $\beta_V(y)\geq\limsup_{x\rightarrow y}\delta_V(x,y)=\lambda_{\text{max}}(V^{-1}\mathcal{D}^2f(y)).$ Also, because of the concavity of the minimum eigenvalue, $\delta_V(x,y)\geq\lambda_{\text{min}}\left(2\int_0^1(1-\tau)\mathcal{D}^2f(x+\tau(y-x))d\tau\right)\geq\min_{0\leq\tau\leq 1}\lambda_{\text{min}}\left(\mathcal{D}^2f(x+\tau(y-x))\right),$ and thus quadratic majorizations do not exist for any $y$ if $\lambda_{\text{min}}\left(\mathcal{D}^2f(x)\right)$ is unbounded.

Example: As an example, consider $f$ defined by $f(x)=\sum_{i=1}^n\log(1+\exp(r_i'x)).$ The function is convex, and as we have shown $\mathcal{D}^2f(x)\leq\frac14 R'R.$ Let's look at the case in which $x$ has only two elements (as in simple logistic regression). We first study a simple subset of $\mathcal{A}(y)$ , those matrices which are positive definite and have equal diagonal elements. Thus $A=\beta\begin{bmatrix}1&\rho\\\rho&1\end{bmatrix},$ with $\beta>0$ and $-1<\rho<+1.$ Simply choose a $\rho$ and then numerically compute the corresponding $\beta_\rho(y).$ This will give a convex region that is within $\mathcal{A}(y).$

Figure 1: Set $\mathcal{A}(y)$ for logistic example.

More generally we can parametrize $A$ by using $A=\beta\begin{bmatrix}\alpha&\gamma\\\gamma&1-\alpha\end{bmatrix},$ with $\beta>0$ , $0<\alpha<1$ , and $\gamma^2<\alpha(1-\alpha).$ The constraints on $\alpha$ and $\gamma$ define the interior of a circle in the plane with center $(\frac12,0)$ and radius $\frac12.$ For each element in the circle we can compute the corresponding $\beta_V(y)$ , which will give a complete description of $\mathcal{A}(y).$