Understanding Convexity in Optimisation

1. The Optimisation Landscape: Why Convexity?

When we train a machine learning model, we are typically trying to minimise a loss function. This function measures how poorly our model is performing. The parameters of our model are the inputs to this function, and we want to find the set of parameters that results in the lowest possible loss.

Imagine the loss function as a landscape with hills and valleys. Our goal is to find the lowest point in this entire landscape.

As the image suggests, this search is straightforward if the landscape is a simple, single "bowl". Any step we take that goes "downhill" will eventually lead us to the bottom. This is the world of convex optimisation.

However, if the landscape is rugged, with many valleys, we might find the bottom of a small, local valley and get stuck, mistakenly believing we've found the lowest point when a much deeper valley exists elsewhere. This is the challenge of non-convex optimisation, which is typical for complex models like neural networks.

For a significant portion of this course, we will focus on models where the loss function is convex, because it guarantees that simple optimisation strategies will find the one true best solution.

2. Defining Convexity: From Geometry to Algebra

The intuitive idea of a "bowl-shaped" function can be made mathematically precise. There are two common and equivalent ways to define a convex function.

Geometric Definition: The Chord Above the Graph

A function is convex if the line segment connecting any two points on its graph lies on or above the graph itself.

The inequality shown in the image, $f(\lambda x+(1-\lambda )y)\le \lambda f(x)+(1-\lambda )f(y)$ for $\lambda \in [0,1]$, is the algebraic formalisation of this geometric picture. It states that the function value at a point between $x$ and $y$ is less than or equal to the value on the straight line connecting $f(x)$ and $f(y)$.

A slightly more abstract but powerful way to think about this is through the function's epigraph—the set of all points lying on or above its graph. A function is convex if and only if its epigraph is a convex set.

The following video gives a great visual overview of these definitions.

3. The Power of Convexity: Local Minima are Global Minima

Now we come to the single most important property of convex functions for optimisation. For a convex function, any local minimum is also a global minimum.

This means if we use an algorithm (like gradient descent, which we'll study soon) and it finds a point where no small step can further decrease the function's value (a local minimum), we can be certain that we have found the best possible value (the global minimum). This completely eliminates the problem of getting stuck in a suboptimal valley.

This powerful result stems from the "tangent hyperplane" property of convex functions.

As the video explains, if you find a point where the gradient is zero, the tangent line is horizontal. Since the entire function lies above this tangent, that point must be a global minimum. This is the theoretical guarantee that makes convex optimisation so powerful and reliable.

4. The Practitioner's Toolkit: How to Identify Convex Functions

Knowing that convexity is important is one thing; being able to determine if a given function is convex is another. Here are two primary methods.

4.1. Composition Rules (Building Blocks)

Many complex functions in machine learning are built from simpler pieces. If we know the pieces are convex, we can often deduce that the whole function is convex. Key rules include:

• Non-negative weighted sum: If $f_1$ and $f_2$ are convex, then $w_1{f}_1+w_2{f}_2$ is convex for any $w_1,w_2\ge 0$.
• Maximum: If $f_1$ and $f_2$ are convex, then $f(x)=\max (f_1(x),f_2(x))$ is convex.
• Composition with an affine map: If $f$ is convex, then $g(x)=f(Ax+b)$ is also convex.

Let's see this in action with the objective function for Support Vector Machines (SVMs), a classic machine learning model.

This "calculus of convex functions" is a very common way to prove convexity for many machine learning loss functions.

4.2. The Hessian Condition

For twice-differentiable functions of multiple variables, there is a direct test analogous to checking if the second derivative is non-negative in the single-variable case. This test involves the Hessian matrix, which you'll recall from our first lesson is the matrix of second-order partial derivatives.

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

A symmetric matrix $H$ is positive semidefinite (PSD), denoted $H⪰0$, if $z^{T}Hz\ge 0$ for all non-zero vectors $z$. Since you're familiar with eigendecomposition, an equivalent condition is that all eigenvalues of a symmetric matrix must be non-negative.

Let's formalize this and see a worked example.

The Hessian test is a powerful, concrete tool that connects the abstract property of convexity to the calculus and linear algebra we have been studying.

5. A Stronger Guarantee: Strict and Strong Convexity

To conclude, it's worth knowing about two stronger forms of convexity that provide even better guarantees for optimisation.

• Strictly Convex: The inequality in the definition becomes strict ($<$) for distinct points. Geometrically, the chord between any two points is strictly above the function's graph. The main benefit is that if a minimum exists, it is unique. The function $f(x)=x^4$ is convex but not strictly convex at $x=0$, while $f(x)=x^2$ is strictly convex.

• Strongly Convex: A function is $\lambda$-strongly convex if $f(x)-\frac{\lambda }{2}\Vert x{\Vert }^2$ is convex for some $\lambda >0$. This is a very strong condition. It implies strict convexity, but also guarantees that the function has a quadratic lower bound around its minimum. This is crucial for proving fast convergence rates for optimisation algorithms. For example, the objective for ridge regression is strongly convex, while ordinary least squares is only convex.

You can read the formal definitions in the lecture notes we used earlier if you're interested.

Conclusion

In this lesson, we introduced the fundamental concept of convexity and its central role in optimisation. We've seen that while many machine learning problems are non-convex and hard, a large and important class are convex, which allows us to find guaranteed global solutions.

Here are the key takeaways:

• Convex functions are "bowl-shaped," meaning the line segment between any two points on the graph lies on or above the graph.
• The primary role of convexity in optimisation is that any local minimum is also a global minimum, which makes finding the optimal solution reliable.
• We can identify convex functions using composition rules (building them from convex parts) or by checking if the Hessian matrix is positive semidefinite.
• Strict and strong convexity are stronger conditions that guarantee a unique minimum and can be used to prove faster convergence rates for optimisation algorithms.

We now understand what kind of functions are "easy" to optimise. In our next lesson, we will begin learning how to perform this optimisation under constraints by studying the method of Lagrange multipliers.