Convex Functions and Convex Sets

A convex set $C \subseteq \mathbb{R}^n$ is a set such that for any two points $x, y \in C$ and any $\lambda \in [0,1]$, the point

also lies in $C$. Geometrically, the entire straight-line segment joining any two members of the set stays inside the set — no dents, no holes, no disconnected pieces. Balls, half-spaces, hyperplanes, boxes, and intersections of convex sets are all convex; a crescent moon or a star shape is not. A convex function $f: C \to \mathbb{R}$, defined on a convex set $C$, satisfies for all $x, y \in C$ and $\lambda \in [0,1]$:

This says the chord connecting two points on the graph of $f$ never dips below the graph itself — the function is "bowl-shaped." If the inequality is strict whenever $x \ne y$ and $\lambda \in (0,1)$, $f$ is strictly convex, ruling out flat segments and guaranteeing a unique minimizer when one exists. A function $f$ is concave if $-f$ is convex (the graph bulges upward, like a dome). The domain must itself be convex for the definition to make sense, since we need $\lambda x + (1-\lambda) y$ to remain in the domain for the inequality to be evaluable. This is why convexity is really a joint statement about a function and the convex set it lives on. Common convex functions include $f(x) = x^2$, $f(x) = e^x$, $f(x) = \|x\|_2$ (any norm is convex), and $f(x) = \max(0, 1 - x)$ (the hinge loss). Common convex sets include the entire space $\mathbb{R}^n$, any linear subspace, any half-space $\{x : a^\top x \le b\}$, and any norm ball $\{x : \|x\| \le r\}$.

Working with the definition directly (checking the chord inequality for every pair of points) is correct but impractical. Instead, convexity is diagnosed using calculus-based tests that require checking a condition pointwise rather than over all pairs.

First-order condition. If $f$ is differentiable on a convex set $C$, then $f$ is convex on $C$ if and only if for all $x, y \in C$:

This says the tangent hyperplane at any point $x$ lies entirely below (or touches) the graph of $f$ — the linear (first-order Taylor) approximation is always a global underestimate. This is the single most useful fact in convex optimization: it turns a local piece of information (the gradient at one point) into a global guarantee about the function everywhere.

Second-order condition. If $f$ is twice differentiable on an open convex set $C$, then $f$ is convex on $C$ if and only if its Hessian matrix $\nabla^2 f(x)$ is positive semi-definite (PSD) for every $x \in C$, meaning

In one dimension this collapses to the familiar $f''(x) \ge 0$ everywhere. If the Hessian is positive definite ($v^\top \nabla^2 f(x) v > 0$ for all $v \ne 0$), $f$ is strictly convex. This is usually the most mechanical way to check convexity for a smooth function: compute the Hessian, check its eigenvalues are non-negative.

Algorithmic procedure to certify convexity of a candidate loss: ``` FUNCTION IsConvexCandidate(f, domain C):

# Step 1: confirm the domain is convex IF C is not a convex set (e.g., defined by non-linear equalities): RETURN "cannot certify via standard rules"

# Step 2: try composition rules first (cheapest) IF f = sum of known convex functions: RETURN "convex, by sum rule" IF f = affine composition g(Ax + b) with g convex: RETURN "convex, by affine composition rule" IF f = max(f_1, ..., f_k) with each f_i convex: RETURN "convex, by pointwise-max rule"

# Step 3: fall back to calculus tests compute gradient ∇f(x) symbolically or numerically compute Hessian ∇²f(x) FOR representative sample of points x in C: check eigenvalues of ∇²f(x) IF any eigenvalue < 0: RETURN "not convex (found negative curvature direction)" IF Hessian is PSD at all tested points AND this holds analytically: RETURN "convex, by second-order condition" ELSE: RETURN "inconclusive — verify analytically" ``` This "procedure" is really a checklist a practitioner runs through mentally: recognize the loss as a composition of known convex building blocks (sums of convex functions, affine substitutions, pointwise maxima of convex functions, all preserve convexity), and only compute the Hessian by hand when no shortcut rule applies. For example, ridge regression's loss $\|Xw - y\|_2^2 + \lambda \|w\|_2^2$ is instantly recognized as convex: it is a sum of a convex quadratic and a convex norm-squared term, with no need to ever write down a Hessian.

Complexity of checking convexity. Verifying convexity from the raw definition requires checking the chord inequality for infinitely many pairs of points and all $\lambda \in [0,1]$ — this is not a finite algorithm at all. The practical cost comes from the certificates instead:

• Composition rules (sum, affine composition, pointwise max) cost $O(1)$ per rule application, since they are syntactic checks on how the function is built from known convex pieces.
• Second-order (Hessian) test costs $O(n^2)$ to write down the Hessian for $x \in \mathbb{R}^n$, plus the cost of an eigenvalue/PSD check, which is $O(n^3)$ via Cholesky decomposition or eigendecomposition. For many losses of interest, the Hessian has closed-form structure (e.g., $X^\top X$ for least squares) so this is done once, symbolically, rather than at every point.
• In machine learning, we rarely certify convexity at runtime; it is verified once, analytically, when the loss function is designed, and then exploited by the optimizer for the lifetime of the model.

Correctness of the first-order condition (why it matches the definition). Suppose $f(y) \ge f(x) + \nabla f(x)^\top(y-x)$ holds for all $x, y \in C$. Pick any $x, y \in C$ and $\lambda \in [0,1]$, and let $z = \lambda x + (1-\lambda) y$. Apply the tangent inequality at $z$ with target points $x$ and $y$:

Multiply the first by $\lambda$, the second by $(1-\lambda)$, and add:

But $\lambda(x - z) + (1-\lambda)(y-z) = \lambda x + (1-\lambda) y - z = 0$ by the definition of $z$. So the gradient term vanishes, leaving

which is exactly the definition of convexity. The converse direction (convexity implies the tangent inequality) follows by taking the limit of the chord slope as one endpoint approaches the other, using the definition of the derivative. This proves the two definitions are equivalent, not merely correlated.

Correctness of "local minimum implies global minimum." This is the central theorem that justifies using convexity as a design principle for loss functions. Suppose $f$ is convex on convex domain $C$, and $x^*$ is a local minimum: there is a neighborhood $U$ around $x^*$ where $f(x^*) \le f(x)$ for all $x \in U \cap C$. We show $f(x^*) \le f(x)$ for every $x \in C$, not just nearby ones. Take any $x \in C$. By convexity of $C$, the segment from $x^*$ to $x$ stays in $C$. For small enough $\lambda \in (0,1)$, the point $z_\lambda = x^* + \lambda(x - x^*)$ lies inside $U \cap C$ (since $z_\lambda \to x^*$ as $\lambda \to 0$). Local optimality gives:

where the last step is the convexity inequality. Rearranging:

Since $x \in C$ was arbitrary, $x^*$ is a global minimum. $\blacksquare$ This is the entire reason convexity matters for Gradient Descent: any algorithm that finds a point with zero gradient (or, for constrained problems, a point satisfying the KKT conditions) on a convex objective has found the answer, not merely an answer. There is no landscape of decoys to worry about.

Honest tradeoffs. Convexity is a strong assumption, and most interesting models (neural networks, mixtures, most probabilistic graphical models with latent variables) are not convex in their parameters. Enforcing convexity often means giving up expressiveness — a linear model is convex in its weights, but a neural network is not, precisely because it composes nonlinear functions with themselves in ways that destroy the convexity of the composite. Convexity also does not by itself say anything about the speed of convergence; for that, you additionally need properties like Lipschitz-continuous gradients or strong convexity (a stronger form where the function curves upward at least quadratically), which give explicit convergence rates for gradient descent.

Consider the logistic regression loss for a single training example $(x_i, y_i)$ with $y_i \in \{0, 1\}$ and weight vector $w \in \mathbb{R}^d$:

We verify convexity in $w$ by computing gradient and Hessian, tracing the algebra step by step.

Step 1: reduce to a 1-D composition. Let $t = w^\top x_i$ (an affine function of $w$), and define

Since $\ell(w) = g(w^\top x_i)$ is $g$ composed with an affine map, $\ell$ is convex in $w$ if $g$ is convex in $t$ (affine composition preserves convexity — no need to redo the multivariable Hessian test).

Step 2: compute $g'(t)$. Using $\sigma'(t) = \sigma(t)(1-\sigma(t))$:

Step 3: compute $g''(t)$.

Step 4: check the sign. Since $\sigma(t) \in (0,1)$ for all finite $t$, we have $\sigma(t)(1-\sigma(t)) > 0$ always. So $g''(t) > 0$ everywhere, meaning $g$ is strictly convex in $t$, hence $\ell(w)$ is convex in $w$ (though not strictly, since the affine map $w \mapsto w^\top x_i$ can be non-injective when $d>1$).

Step 5: numeric trace. Let $x_i = (2, -1)$, $y_i = 1$, and compare two candidate weight vectors $w_a = (0.1, 0.2)$ and $w_b = (1.0, -0.5)$.

The chord midpoint value is $\tfrac{1}{2}(0.693) + \tfrac{1}{2}(0.079) = 0.386$. The actual function value at the midpoint weight is $\ell(w_m) = 0.252$. Since $0.252 \le 0.386$, the chord lies above the function at this sampled point — consistent with (though not a proof of) convexity, exactly as the theory predicts.

Step 6: consequence for training. Because $\ell$ is convex (and the sum of convex functions over all training examples is convex, by the sum rule), the full logistic regression loss over a dataset is convex in $w$. Gradient descent starting from any initialization $w_0$ and converging to a point with $\nabla L(w) \approx 0$ has found the global minimum of the training loss — this is why logistic regression training is considered "solved" in a way that deep network training is not.

The systematic mathematical study of convex sets and functions matured in the early-to-mid twentieth century, driven by connections to geometry, economics, and — eventually — computation.

Convex analysis was, for decades, a subject pursued mostly by mathematicians interested in geometry and economics (convex sets model resource constraints and utility functions naturally). Its explosive relevance to machine learning arrived once researchers realized that many core estimation problems — least squares, logistic regression, support vector machines — are convex programs in disguise, meaning decades of theory about duality, optimality conditions, and efficient algorithms could be imported wholesale into statistics and learning theory.

Convexity is not an abstract nicety; it is load-bearing infrastructure in production machine learning systems. Linear and logistic regression solvers in libraries like scikit-learn, Vowpal Wabbit, and glmnet rely on convexity to guarantee that Newton's method, L-BFGS, or coordinate descent converges to the actual optimal fit, not an arbitrary stationary point. Support vector machines are formulated explicitly as convex quadratic programs, which is why SVM training has reliable, reproducible solvers (SMO, libsvm) rather than requiring dozens of random restarts. LASSO and ridge regression, workhorses of high-dimensional statistics and feature selection pipelines, are convex programs whose sparsity or shrinkage properties are provable precisely because of convex duality. In deep learning, individual layers and losses are analyzed through a convex lens even though the full network is not convex: cross-entropy loss is convex in the logits, hinge loss is convex, and the softmax layer's log-partition function is convex, all of which stabilizes training even inside a globally non-convex optimization. Convex relaxations — replacing a hard combinatorial or non-convex problem with the closest convex approximation — power compressed sensing, low-rank matrix completion (recommender systems like the Netflix Prize solutions), and robust statistics. Portfolio optimization in finance, control system design in robotics, and network resource allocation in distributed systems all reduce, at their core, to convex programs solved by algorithms whose correctness rests on exactly the definitions and theorems in this article.

Ask the tutor: How does strong convexity change the convergence rate guarantees for gradient descent compared to plain convexity?