Convexity Conditions: First and Second Order

What is a Convex Function?

At its core, a convex function is one that curves "upwards". We can formalize this intuition in a few ways.

The Geometric Definition

The most intuitive way to think about a convex function is to visualize its graph. If you pick any two points on the function's curve and draw a straight line segment between them (a "chord"), the entire portion of the curve between those two points will lie on or below the line segment.

This idea is captured by Jensen's inequality. A function $f$ is convex if its domain is a convex set and for any two points $x$ and $y$ in its domain, and for any $\theta$ between 0 and 1, the following holds:

Here, $\theta x+(1-\theta )y$ represents any point on the line segment between $x$ and $y$. The left side of the inequality is the function's value at that point, while the right side is the value on the straight line connecting $(x,f(x))$ and $(y,f(y))$.

A function is strictly convex if the inequality is strict ($<$) for $x\ne y$ and $\theta \in (0,1)$. A function $f$ is concave if $-f$ is convex.

To get a more formal handle on this, please read the introductory section of the following notes.

The property that local minima are global minima is precisely why convexity is so desirable in optimization. It means that an algorithm can't get "stuck" in a suboptimal valley, believing it has found the best solution when a better one exists elsewhere.

First-Order Condition for Convexity

For functions that are differentiable, we can use their derivatives to check for convexity. The first-order condition provides a powerful geometric interpretation.

A differentiable function $f$ is convex if and only if it always lies above its tangent lines. Formally, for any two points $x$ and $y$ in its domain:

Here, the term $f(x)+\nabla f(x{)}^T(y-x)$ is the first-order Taylor approximation of $f$ around $x$. This expression defines the tangent hyperplane (a line in 1D, a plane in 2D, etc.) to the function at point $x$. The condition states that the function's value, $f(y)$, is always greater than or equal to the value predicted by the tangent line approximation based at $x$.

This condition is not just a theoretical curiosity; it's the foundation for the correctness of gradient-based optimization methods.

For the formal statement and a proof, please continue with the lecture notes.

Second-Order Condition for Convexity

For functions that are twice differentiable, there is an even more direct and often easier test for convexity that involves the second derivative. In single-variable calculus, you know that if $f^{\prime \prime }(x)\ge 0$, the function is convex (or "concave up"). The second-order condition for multivariable functions is the natural generalization of this idea.

To understand this generalization, we first need to understand the multivariable equivalent of the second derivative: the Hessian matrix. This video from OptWhiz provides an excellent intuition for why the gradient is a vector and the Hessian is a matrix.

With the concept of the Hessian in hand, the second-order condition is as follows:

A twice-differentiable function $f$ is convex if and only if its Hessian matrix, ${\nabla }^{2}f(x)$, is positive semidefinite for all $x$ in its domain.

A matrix $H$ is positive semidefinite (written as $H⪰0$) if for any non-zero vector $z$, the quadratic form $z^{T}Hz\ge 0$. If $z^{T}Hz>0$ for all non-zero $z$, the matrix is positive definite ($H\succ 0$), which implies strict convexity.

This is arguably the most common method used to verify convexity in machine learning.

The following video provides a clear, step-by-step walkthrough of how to compute a Hessian and test for positive semidefiniteness.

Examples

Let's solidify this with a few examples. The CS229 notes are a great resource for this.

Let's consider that quadratic function example more closely. The Hessian is simply ${\nabla }^{2}f(x)=A$. Therefore, the function is convex if and only if the matrix $A$ is positive semidefinite.

This is a profoundly important result. The objective function for ordinary least squares regression is $||X\mathbf{w}-\mathbf{y}|{|}_2^2=({\mathbf{w}}^T{X}^T-{\mathbf{y}}^T)(X\mathbf{w}-\mathbf{y})$, which can be expanded into a quadratic form in $\mathbf{w}$ with the matrix $A=2X^{T}X$. The matrix $X^{T}X$ is always positive semidefinite, which means the least squares objective is always convex. This guarantees that the solution we find via the normal equations (or gradient descent) is the unique global minimum.

Conclusion

In this lesson, we established the fundamental importance of convexity for optimization in machine learning. We explored three key criteria for verifying if a function is convex:

• Jensen's Inequality: The formal definition, stating that the function's graph lies below any of its chords. $f(\theta x+(1-\theta )y)\le \theta f(x)+(1-\theta )f(y)$.
• First-Order Condition: For differentiable functions, the graph must lie on or above all of its tangent hyperplanes. $f(y)\ge f(x)+\nabla f(x{)}^T(y-x)$.
• Second-Order Condition: For twice-differentiable functions, the Hessian matrix must be positive semidefinite everywhere. ${\nabla }^{2}f(x)⪰0$.

Understanding these conditions is not just a mathematical exercise; it provides the theoretical guarantee that many of the algorithms we will study are able to find optimal solutions efficiently.

In our next lesson, we will put this theory into practice by deriving our first, and perhaps most famous, optimization algorithm: gradient descent. We will see how it uses the first-order information of a function to iteratively move towards a minimum, a process that is guaranteed to succeed for the convex functions we've just learned to identify.