Appendix D — Smoothness and Convexity

In this appendix, we discuss foundations of algorithms for non-linear smooth optimization problem. The topics covered include Taylor’s theorem and its applications, convex sets and convex/strongly-convex functions.

A general problem of interest here is to find a \(\theta^*\) such that

\[ \theta^* \in \argmin_{x \in \D} f(\theta), \tag{D.1} \]

where \(\mathcal{D}\subset \mathbb{R}^d\). The problem (D.1) includes the case where \(\mathcal{D}\) is the whole of \(\mathbb{R}^d\) as well.

The following definitions are relevant in the context of the optimization problem (D.1).

Definition D.1 (local minima).

A point \(\theta^* \in \R^d\) is called a local minimum of \(f\) if there exists a neighborhood \(\N(\theta^*,\epsilon)\) of \(\theta^*\) such that \(f(\theta) \geq f(\theta^*)\) for all \(\theta \in \N(\theta^*,\epsilon) \cap \D\).

Definition D.2 (global minima).

A point \(\theta^* \in \D\) is called a global minimum of \(f\) if \(f(\theta) \geq f(\theta^*)\) for all \(\theta \in \D\).

Definition D.3 (strict local minima).

A point \(\theta^* \in \D\) is called a strict local minimum of \(f\) if there exists a neighbourhood \(\N(\theta^*,\epsilon)\) of \(\theta^*\) such that \(f(\theta) > f(\theta^*)\) for all \(\theta \in \N(\theta^*,\epsilon) \cap \D\) with \(\theta \neq \theta^*\).

D.1 Necessary conditions for local minima

Given a point \(\theta^* \in \D\), how does one determine whether it is a local minimum or not? The following results, which are standard in optimization literature, provide an answer to this question.

Theorem D.1 (First and second-order necessary conditions).

Let \(\theta^*\) be a local minimum of \(f:\D \rightarrow \R\) and \(f\) be continuously differentiable. Then \(\nabla f(\theta^*) = 0\).
Further if \(f\) is twice continuously differentiable, then \(\nabla^2f(\theta^*)\) is a positive semi-definite matrix.

Proof.

Fix \(s \in \R^d\). Recall that \(\theta^*\) is a local minimum. Then we have,

\[ s\tr \nabla f(\theta^*) = \lim_{\delta \rightarrow 0} \frac{f(\theta^* + \delta s) - f(\theta^*)}{\delta} \geq 0. \]

Similarly, we have,

\[ - s\tr \nabla f(\theta^*) \geq 0. \]

Combining the two equations above, we have that \(\nabla f(\theta^*) = 0\).

Further, if \(f\) is twice continuously differentiable, then by Taylor series expansion, we have

\[ f(\theta^* + \delta s) - f(\theta^*) = \delta s\tr \nabla f(\theta^*) + \frac{\delta^2}{2} s\tr \nabla^2 f(\theta^*)s + o(\delta^3). \]

Since \(\nabla f(\theta^* ) = 0\), we have

\[ 0 \leq \frac{f(\theta^* + \delta s) - f(\theta^*)}{\delta^2} = \frac{1}{2} s\tr \nabla^2 f(\theta^*)s + o(\delta). \]

Thus, as \(\delta \rightarrow 0\), for all \(s \in \R^d\), we have \(s\tr \nabla^2 f(\theta^*)s \geq 0\), implying \(\nabla^2 f(\theta^*)\) is positive semi-definite Hence proved.

\(\square\)

Example D.1.

Consider \(f(\theta) = \frac{1}{2} \theta\tr A \theta - b\tr \theta\). From the first-order necessary condition, we have that \(\nabla f(\theta^*) = 0\) and \(\nabla^2f(\theta^*)\) is positive semi-definite, which is equivalent to \(A\theta^* - b = 0\) and \(A\) is positive semi-definite.

We have the following cases in general:

  • If \(A\) is not positive semi-definite, then \(f\) has no local minima.

  • If \(A\) is positive semi-definite, then \(f\) is convex and any \(\theta^*\) solving \(A\theta^* - b = 0\) is a global minimum.

  • if \(A\) is positive definite, then \(f\) has a unique global minimum given by \(\theta^*=A^{-1} b\).

  • The reader is encouraged to think about the case where \(A\) is positive semi-definite and singular. In this case, it is relevant to check if \(b\) is in the column space of \(A\) or not and reason accordingly.

D.2 Taylor’s theorem

Taylor’s theorem shows how a smooth function \(f\) can be approximated locally by polynomials that depend on low-order derivatives of \(f\).

Theorem D.2.

Let \(f: \R^d \rightarrow \R\) be a continuously differentiable function. Given \(\theta,p \in \R^d\), we have

\[ \begin{align*} f(\theta+p) &= f(\theta) + \int_{0}^{1} \nabla f(\theta+ \alpha p)\tr p d\alpha, \textrm{ and} \tag{D.2} \\ f(\theta+p) &= f(\theta) + \nabla f(\theta+ \alpha p)\tr p \textrm{ for some } \alpha\in (0,1). \tag{D.3} \end{align*} \]

If \(f\) is twice continuously differentiable, we have

\[ \begin{align*} \nabla f(\theta+p) &= \nabla f(\theta) + \int_{0}^{1} \nabla^2 f(\theta+ \alpha p)p d\alpha, \textrm{ and } \\ f(\theta+p) &= f(\theta) + \nabla f(\theta)\tr p + \frac{1}{2}p\tr \nabla^2 f(\theta + \alpha p) p, \tag{D.4} \end{align*} \]

for some \(\alpha \in (0,1)\).

A consequence of (D.2) is that for a continuously differentiable \(f\) at \(\theta\), we have

\[ f(\theta + p) = f (\theta) + \nabla f(\theta)\tr p + o(||p||). \]

Definition D.4 (smooth function).

A function \(f:\D(\subset \R^d) \rightarrow \R\) is said to be \(L\)-smooth if for all \(x,y \in \D\), the following condition holds:

\[ ||\nabla f(x) - \nabla f(y)|| \leq L ||x-y||. \tag{D.5} \]

The three results below provide useful characterizations of \(L\)-smooth functions.

Lemma D.3.

Let \(f:\D(\subset \R^d) \rightarrow \R\) be a \(L\)-smooth function. Then for any \(x,y \in \D\), we have the following:

\[ f(y) \leq f(x) + \nabla f(x)\tr (y - x) + \frac{L}{2} ||y-x||^2. \tag{D.6} \]

Lemma D.4.

Suppose \(f:\D(\subset \R^d) \rightarrow \R\) is twice continuously differentiable function. Then, \(\forall \theta\in\D\), (I) \(f\) is \(L\)-smooth implies \(\nabla^2 f(\theta) \preceq L \I\) (II) conversely, if \(- L \I \preceq \nabla^2 f(\theta) \preceq L \I\), then \(f\) is \(L\)-smooth.

Lemma D.5.

Suppose \(f\) is twice continuously differentiable on \(\R^d\). Then if \(f\) is \(L\)-smooth, we have \(\nabla^2 f (\theta) \preceq L\I\) for all \(\theta\in\D\). Conversely, if \(- L \I \preceq \nabla^2 f(\theta) \preceq L \I\), \(\forall \theta\in\D\), then \(f\) is \(L\)-smooth.

D.3 Sufficient conditions for local minima

Theorem D.6 (Sufficient Conditions for Smooth Unconstrained Optimization).

Suppose that \(f\) is twice continuously differentiable and that, for some \(\theta^*\in\mathbb{R}^d\), we have \(\nabla f (\theta^*) = 0\), and \(\nabla^2 f (\theta^*)\) is positive definite. Then \(\theta^*\) is a strict local minimizer of \(\min\limits_{\theta \in \R^d} f(\theta)\).

Proof.

See (Bertsekas 1999).

\(\square\)

D.4 Convex Sets and Functions

Definition D.5.

A set \(\C \subset \mathbb{R}^d\) is a convex set if \(\forall x,y \in \C\) and for all \(\lambda \in [0,1]\), it satisfies:

\[ \lambda x + (1-\lambda)y \in \C. \tag{D.7} \]

Example D.2.

A set \(\{x \mid v\tr x = b \}\) with \(v\in \R^d\) and \(b\in\R\), is a convex set. Such a set is known as a hyperplane. With the same notation, a set \(\{x \mid v\tr x \leq b \}\), which is known as a halfspace, is also a convex set.

Example D.3.

Euclidean Balls: \(B = \{\theta \mid \norm{x} \leq 1 \}\) is a convex set.

Definition D.6.

A function \(f:\Omega \rightarrow \mathbb{R}\) is a convex function if its domain \(\Omega\) is convex and it satisfies the following condition for all \(x, y \in \Omega\) and \(\lambda \in [0,1]\):

\[ f(\lambda x + (1-\lambda) y ) \leq \lambda f(x) + (1 - \lambda) f(y). \tag{D.8} \]

Further, the function \(f\) is strictly convex if the inequality is strict for \(x\ne y\) and \(0<\lambda<1\).

Note that a function \(f\) is concave/strictly concave if \(-f\) is convex/strictly convex.

Lemma D.7.

Suppose \(f\) is convex. Then,

  1. Any local minimum is a global minimum.

  2. The set of all global minima is convex.

Theorem D.8 (Necessary condition for optima).

Suppose that \(f\) is continuously differentiable and convex. Then if \(\nabla f (\theta^*) = 0\), then \(\theta^*\) is a global minimizer.

Proof.

By applying Taylor’s theorem,

\[ \begin{align*} f(x + \alpha(y-x)) = f(x) + \alpha \nabla f(x)\tr (y-x) + o(\alpha) \leq (1-\alpha)f(x) + \alpha f(y). \end{align*} \]

\[ \begin{align*} f(y) \geq f(x) + \nabla f(x)\tr (y-x) + o(1). \end{align*} \]

when \(\alpha \downarrow 0\), \(o(1)\) term vanishes, and we obtain

\[ \begin{align*} f(y) \geq f(x) + \nabla f(x)\tr (y-x). \end{align*} \]

Setting \(x = \theta^*\) leads to

\[ \begin{align*} f(y) \geq f(\theta^*),\ \forall y. \end{align*} \]

Hence proved.

\(\square\)

We now provide useful characterizations of convex functions through the result below.

Theorem D.9.

Suppose \(f: \R^d \rightarrow \R\) is twice differentiable over an open domain. Then the following are equivalent

  1. \(f\) is convex;

  2. \(f(y) \geq f(x) + \nabla f(x)\tr (y-x), \forall x, y \in \D\);

  3. \(\nabla^2f(x) \succeq 0\), for all \(x \in \D\).

Proof.

We prove \((i) \Leftrightarrow(i i)\) then \((i i) \Leftrightarrow(i i i)\).

\((i) \Rightarrow(i i)\) If \(f\) is convex, by definition

\[ f(\lambda y+(1-\lambda) x) \leq \lambda f(y)+(1-\lambda) f(x), \forall \lambda \in[0,1], x, y \in \operatorname{dom}(f) \]

After rewriting, we have

\[ \begin{aligned} & f(x+\lambda(y-x)) \leq f(x)+\lambda(f(y)-f(x)) \\ \Rightarrow & f(y)-f(x) \geq \frac{f(x+\lambda(y-x))-f(x)}{\lambda}, \forall \lambda \in(0,1] \end{aligned} \]

As \(\lambda \downarrow 0\), we get

\[ \begin{align*} f(y)-f(x) \geq \nabla f^{T}(x)(y-x) \tag{D.9} \end{align*} \]

\((i i) \Rightarrow(i)\) Suppose (D.9) holds \(\forall x, y \in \operatorname{dom}(f)\). Take any \(x, y \in \operatorname{dom}(f)\) and let

\[ \begin{align*} z=\lambda x+(1-\lambda) y \end{align*} \]

We have

\[ \begin{align*} & f(x) \geq f(z)+\nabla f^{T}(z)(x-z) \tag{D.10} \\ & f(y) \geq f(z)+\nabla f^{T}(z)(y-z) \tag{D.11} \end{align*} \]

Multiplying (D.10) by \(\lambda\), (D.11) by \((1-\lambda)\) and adding, we get

\[ \begin{aligned} \lambda f(x)+(1-\lambda) f(y) & \geq f(z)+\nabla f^{T}(z)(\lambda x+(1-\lambda) y-z) \\ & =f(z) \\ & =f(\lambda x+(1-\lambda) y) . \end{aligned} \]

\((i i) \Leftrightarrow(i i i)\) We prove both of these claims first in dimension 1 and then generalize.

\((i i) \Rightarrow(i i i)\)(uni-variate case) Let \(x, y \in \operatorname{dom}(f), y>x\). We have

\[ \begin{align*} & f(y) \geq f(x)+f^{\prime}(x)(y-x) \tag{D.12} \\ \text{and } & f(x) \geq f(y)+f^{\prime}(y)(x-y) \tag{D.13} \end{align*} \]

\[ \Rightarrow f^{\prime}(x)(y-x) \leq f(y)-f(x) \leq f^{\prime}(y)(y-x) \]

using (D.12) then (D.13). Dividing LHS and RHS by \((y-x)^{2}\) gives

\[ \frac{f^{\prime}(y)-f^{\prime}(x)}{y-x} \geq 0, \forall x, y, x \neq y \]

As we let \(y \rightarrow x\), we get

\[ f^{\prime \prime}(x) \geq 0, \forall x \in \operatorname{dom}(f) \]

\((i i i) \Rightarrow(i i)\)(uni-variate case) Suppose \(f^{\prime \prime}(x) \geq 0, \forall x \in \operatorname{dom}(f)\). By the mean value version of Taylor’s theorem we have

\[ \begin{aligned} & f(y)=f(x)+f^{\prime}(x)(y-x)+\frac{1}{2} f^{\prime \prime}(z)(y-x)^{2}, \text { for some } z \in[x, y] . \\ & \Rightarrow f(y) \geq f(x)+f^{\prime}(x)(y-x) \text {. } \end{aligned} \]

Now to establish \((i i) \Leftrightarrow(i i i)\) in general dimension, we recall that convexity is equivalent to convexity along all lines; i.e., \(f: \mathbb{R}^{n} \rightarrow \mathbb{R}\) is convex if \(g(\alpha)=f\left(x_{0}+\alpha v\right)\) is convex, \(\forall x_{0} \in \operatorname{dom}(f)\) and \(\forall v \in \mathbb{R}^{n}\). We just proved this happens if and only if

\[ g^{\prime \prime}(\alpha)=v^{T} \nabla^{2} f\left(x_{0}+\alpha v\right) v \geq 0 \]

\(\forall x_{0} \in \operatorname{dom}(f), \forall v \in \mathbb{R}^{n}\) and \(\forall \alpha\) s.t. \(x_{0}+\alpha v \in \operatorname{dom}(f)\). Hence, \(f\) is convex if and only if \(\nabla^{2} f(x) \succeq 0\) for all \(x \in \operatorname{dom}(f)\).

\(\square\)

D.5 Strongly Convex Functions

Definition D.7.

A function \(f: \R^d \rightarrow \R\) is said to be \(\mu\)-strongly convex \((\mu > 0)\) if for all \(x,y \in \R^d\), then

\[ f((1-\lambda)x + \lambda y) \leq (1-\lambda)f(x) + \lambda f(y) + \frac{m}{2} (1-\lambda) \norm{y-x}_2^2 \tag{D.14} \]

Theorem D.10.

Suppose \(f\) is continuously differentiable and \(\mu\)-strongly convex, then for any \(x,y\in\R^d\)

\[ \begin{align*} f(y) \geq f(x) + \nabla f(x)\tr (y-x) + \frac{\mu}{2}\norm{y-x}_2^2 \end{align*} \]

Lemma D.11.

Suppose that \(f\) is twice-continuously differentiable on \(\R^d\). Then \(f\) has modulus of convexity \(\mu\) if and only if \(\nabla^2 f (x) \succeq \mu I\) for all \(x\).

Proof.

For any \(x,u \in \R^d\) and \(\alpha > 0\), we have from Taylor’s theorem that

\[ f(x + \alpha u) = f(x) + \alpha \nabla f(x)\tr u + \frac{1}{2}\alpha^2 u\tr \nabla^2 f(x+\gamma \alpha u)u, \]

for some \(\gamma \in (0,1)\).

From the strong convexity property, we have

\[ \begin{align*} f(x + \alpha u) \geq f(x) + \alpha \nabla f(x)\tr u + \frac{\mu}{2}\alpha^2 \norm{u}^2 \end{align*} \]

By comparing the two equations above, we obtain

\[ \begin{align*} u\tr \nabla ^ 2 f(x + \gamma \alpha u) u \geq \mu \norm{u}^2 \end{align*} \]

By taking \(\alpha \downarrow 0\), we obtain

\[ u\tr \nabla ^ 2 f(x) u \geq \mu \norm{u}^2. \]

Since the above is true for all \(u\in \mathbb{R}^d\), we have

\[ \begin{align*} \nabla ^2 f(\theta) \succeq \mu I. \tag{D.15} \end{align*} \]

\(\square\)

D.6 Bibliographic remarks

For an introduction to convex optimization, the reader is referred to either classic textbooks such as (Boyd and Vandenberghe 2004; Nocedal and Wright 1999; Bertsekas 1999), or the more recent machine learning-oriented optimization book (Wright and Recht 2022). The material presented in this appendix is based on (Wright and Recht 2022) and (Bertsekas 1999).

D.7 Exercises

Exercise 1.

The convex hull of a set \(C\), denoted \(\conv(C)\) is defined as

\[ \conv(C) =\{\alpha_1 x_1 +\ldots+\alpha_k x_k\mid |x_i \in C, \alpha_i \ge 0, \forall i, \alpha_1 +\ldots +\alpha_k =1\}. \]

For each of the following sets in \(\R^2\), provide a visual depiction of their convex hulls by sketching:

  1. \(C = \{ (0,1), (0,4), (-2,-1), (0,0), (3,-2), (-1,2)\}.\)

  2. Union of two unit circles, centered at \((1,1)\) and \((-1,-1)\), respectively.

Exercise 2.

Let \(f:\R\rightarrow\R\) be a convex function. For any three points \(x_1, x_2, x_3\) such that \(x_1 < x_2 < x_3\), show that

\[ \dfrac{f(x_2)-f(x_1)}{x_2-x_1} \le \dfrac{f(x_3)-f(x_2)}{x_3-x_2}. \]

Exercise 3.

Consider the following two statements:
I: If \(\log f\) is convex, then \(f\) is convex.
II: If \(f\) is convex, then \(\log f\) is convex.
Which of the statements above are true?

Exercise 4.

Give an example of a convex function \(f:\R\rightarrow\R\) that is bounded above.

Exercise 5.

Let \(x\in \R^d\), with \(x_i\) denoting the \(i\)th coordinate. Are the functions defined below convex? Justify your answer.

  1. \(f(x) = \log\left(\exp(x_1) + \ldots + \exp(x_d)\right)\).

  2. \(f(x)=\exp(x\tr A x)\), where \(A\) is a positive semi-definite matrix.

Exercise 6.

Answer the following questions concerning necessary conditions for local minima:

  1. Let \(f:\R\rightarrow\R\). Recall that \(f'(x^*)=0\) and \(f''(x^*)\ge 0\) are the first and second-order necessary conditions for a local minimizer. In a similar spirit, derive a third-order necessary condition, assuming \(f\) is three-times continuously differentiable.

  2. Show an example function \(f\) and a point \(x^*\) that satisfies the first, second and third-order necessary conditions, but \(x^*\) is not a local minimizer of the function \(f\).

Exercise 7.

Suppose we want to minimize the function \(f:\R^2\rightarrow\R\) defined by

\[ f(x_1,x_2) = (x_1-x_2)^4 + x_1^2 - x_2^2 -2x_1 + 2x_2+1. \]

Find points where the first-order necessary condition for a minimum is satisfied. For each of these points, characterize whether the second-order necessary condition is satisfied.

Exercise 8.

Let \(f_1,f_2:\R\rightarrow\R\) and let \(\alpha_1,\alpha_2\) be two positive scalars.

  1. Prove or disprove: If \(f_1,f_2\) are convex, then \(\max(\alpha_1 f_1, \alpha_2 f_2)\) is convex.

  2. Prove or disprove: If \(f_1,f_2\) are concave, then \(\max(\alpha_1 f_1, \alpha_2 f_2)\) is concave.

Exercise 9.

Suppose a function \(f: \R \to \R\) is \(L\)-Lipschitz and differentiable. Show that \(\sup_{x}|f'(x)| \leq L.\)

Exercise 10.

Exhibit a real-valued function \(f\) that is \(L\)-smooth but not \(L\)-Lipschitz.

Exercise 11.

Exhibit a real-valued function \(f\) that is Lipschitz and differentiable, but not smooth.

Exercise 12.

Suppose \(f_1:\mathbb{R}^d \to \mathbb{R}\) is \(L_1\)-smooth and \(f_2:\R^d \to \R\) is \(L_2\)-smooth. Show that \(f_1 + f_2\) is \((L_1+L_2)\)-smooth.

Exercise 13.

Consider the function \(f:\R^2\rightarrow\R\) defined by

\[ f(x_1,x_2) = a x_1^2 + 2b x_1 x_2 +c x_2^2. \]

Answer the following:

  1. Prove or disprove: \(f\) is strongly convex if \(a>0\) and \(c>0\).

  2. Derive a necessary and sufficient condition for strong convexity of \(f\). This condition should be in terms of \(a,b,c\).

  3. Under the condition from the part above, characterize the minimizer, say \(x^*\) of \(f\).

Exercise 14.

Suppose that \(f: \R^d \rightarrow \R\) is a \(m\)-strongly convex function with a \(L\)-Lipschitz gradient. Let \(x^*\) be the minimizer with corresponding function value \(f^*=f(x^*)\).

  1. Let \(g(x) = f(x) - \frac{m}{2}\left\| x\right\|^2\). Show that \(g(x)\) is convex with \((L-m)\) Lipschitz continuous gradients.

  2. Using the fact that \(g\), defined in the part above, is convex, prove the following property: For any \(x,y \in \R^d\),

    \[ \begin{align*} &\left(\nabla f(x) - \nabla f(y)\right)\tr(x-y) \\ &\qquad \ge\frac{mL}{m+L}\left\| x-y\right\|^2 + \frac{1}{m+L} \left\| \nabla f(x)- \nabla f(y)\right\|^2. \end{align*} \]