# Convexity

> For a convex function, every local minimum is a global minimum.

Source: https://www.mlfoundry.in/learn/convexity  
Section: Mathematics › Calculus & Optimization  
Level: core · 5 min read · updated 2026-10-03

**Convex function:** A function $f:\mathbb{R}^n\to\mathbb{R}$ is **convex** if the chord between any two points of its graph never lies below the graph: $f(\theta a+(1-\theta)b)\le\theta f(a)+(1-\theta)f(b)$ for all $a,b$ and all $\theta\in[0,1]$. Its graph is a bowl with no bumps, so there is nowhere for a descent method to get stuck except the bottom.

- **Notation:** $\theta\in[0,1]$ mixes the endpoints $a,b$; $\nabla^2 f\succeq 0$ means the Hessian is positive semidefinite
- **Tests:** chord inequality; tangent below graph; $f''\ge0$ (1-D) or $\nabla^2f\succeq0$ everywhere
- **Key property:** every local minimum is global, and $\nabla f(x^*)=0$ is sufficient for a global minimum
- **Strict / strong:** strict: at most one minimizer; $\mu$-strong ($\nabla^2f\succeq\mu I$): exactly one, and GD converges linearly
- **Prerequisites:** derivatives & gradients, Taylor approximation
- **Used in:** linear & logistic regression, SVMs, lasso, convex relaxations, convergence guarantees

## The intuition

Stretch a string between two points on the graph. For a convex function the string always hangs on or above the curve — the curve sags below every chord. A bump would poke through the string; a bump is also exactly what creates a second, worse valley where a downhill walker can stop.

That is why convexity matters in practice: on a convex loss, gradient descent started anywhere ends in the same valley, and "the gradient is zero" certifies that you are done. On a non-convex loss the answer depends on where you start.

## The math

$$
f\big(\theta a+(1-\theta)b\big)\ \le\ \theta f(a)+(1-\theta)f(b)\qquad \forall\, a,b\in\mathbb{R}^n,\ \theta\in[0,1]
$$

- $a,b$: any two points in the domain (the chord's endpoints)
- $\theta$: mixing weight: $\theta=1$ gives $a$, $\theta=0$ gives $b$
- $\theta f(a)+(1-\theta)f(b)$: height of the chord above that point

**Differentiable tests.** If $f$ is differentiable, convexity is equivalent to every tangent plane lying below the graph; if it is twice differentiable, to non-negative curvature in every direction:

$$
f(y)\ \ge\ f(x)+\nabla f(x)^{\top}(y-x)\qquad\Longleftrightarrow\qquad \nabla^2 f(x)\succeq 0\ \ \forall x
$$

- $\nabla f(x)$: gradient of $f$ at $x$
- $\nabla^2 f(x)$: Hessian (matrix of second derivatives); $\succeq0$ means all its eigenvalues are $\ge0$

The tangent condition gives the payoff at once: if $\nabla f(x^*)=0$, then $f(y)\ge f(x^*)$ for every $y$ — a stationary point is a global minimum.

**Local implies global.** Suppose $x^*$ is a local minimum but some $y$ has $f(y)<f(x^*)$. Points $z_\theta=\theta y+(1-\theta)x^*$ approach $x^*$ as $\theta\to0$, and the chord inequality gives $f(z_\theta)\le\theta f(y)+(1-\theta)f(x^*)<f(x^*)$. So arbitrarily close to $x^*$ there are lower points — contradicting local minimality.

**Building convex functions.** Non-negative weighted sums, composition with an affine map $x\mapsto Ax+b$, and pointwise maxima all preserve convexity. That is how you certify losses without computing a Hessian: $\|Xw-y\|^2$ (a norm of an affine map), hinge loss $\max(0,1-y\,w^\top x)$, the log-loss $\log(1+e^{-y\,w^\top x})$ and log-sum-exp are all convex in $w$, and adding an L1 or L2 penalty keeps them so.

## See it

> Figure: Drag a and b: rose marks where the graph rises above the chord. For x⁴ − 3x² + x with the chord on [−1.28, 1.28] the graph pokes 2.23 above it. Run gradient descent: from five starts it lands at x = −1.30 three times and x = 1.13 twice — two different minima (0.15x² + sin 2x gives three). Switch to x², |x|, eˣ − x or log-sum-exp and every start reaches the same point.

## Worked example

**Convex.** $f(x)=x^2$, $a=-1$, $b=3$, $\theta=\tfrac12$: the midpoint is $x=1$ with $f(1)=1$, the chord there is $\tfrac12(1+9)=5$, and $1\le5$. In general $f''(x)=2>0$, so the inequality holds for every chord.

**Non-convex.** $f(x)=x^4-3x^2+x$ has $f''(x)=12x^2-6<0$ for $|x|<0.707$. Its stationary points ($4x^3-6x+1=0$) are $x=-1.301$ with $f=-3.514$ (global minimum), $x=0.170$ (local maximum, $f''=-5.65$) and $x=1.131$ with $f=-1.070$ (a local minimum that is **not** global). The chord test fails between the two minima: at the midpoint $x=-0.085$, $f=-0.107$ but the chord is at $\tfrac12(-3.514-1.070)=-2.292$ — the graph is 2.19 above it.

## In code

```python
import numpy as np
from scipy.optimize import minimize

f = lambda x: x[0]**4 - 3 * x[0]**2 + x[0]
for x0 in [-1.76, -0.88, 0.0, 0.88, 1.76]:
    res = minimize(f, [x0])
    print(x0, res.x.round(3), round(res.fun, 3))   # -1.301 (f=-3.514) or 1.131 (f=-1.07)

# Logistic regression: Hessian of the mean log-loss is X^T S X / n, S = diag(p(1-p))
rng = np.random.default_rng(0)
X, w = rng.normal(size=(200, 3)), rng.normal(size=3)
p = 1 / (1 + np.exp(-X @ w))
H = X.T @ (X * (p * (1 - p))[:, None]) / len(X)
print(np.linalg.eigvalsh(H).min() >= 0)            # True at every w: convex
```

A local optimizer finds whichever minimum is downhill of its start. The logistic-loss Hessian XᵀSX/n has non-negative eigenvalues for any data, which is the convexity certificate.

- **Linear & logistic regression:** Squared error and log-loss are convex in the weights, so any solver — closed form, L-BFGS, SGD — reaches the same optimum, and its gradient norm is a valid stopping test.
- **SVMs and the lasso:** Hinge loss plus an L2 penalty, and squared error plus an L1 penalty, are convex but non-smooth; subgradient, coordinate-descent and proximal methods still find the global optimum.
- **Convex relaxations:** Hard problems are replaced by convex surrogates: the L1 norm for the count of non-zeros (sparse recovery), the nuclear norm for rank (matrix completion), hinge for 0–1 loss.
- **Reading deep-learning theory:** Neural-network losses are non-convex, so guarantees are local. Convex results (step size $\eta<2/L$, linear rates under strong convexity) are the baseline that optimizer analyses and learning-rate heuristics start from.

> **Convex does not mean a unique minimizer — or any:** $f(x)=\max(0,|x|-1)$ is convex and minimized on the whole interval $[-1,1]$; least squares with collinear features has a line of equally good weights. $e^x$ is convex and has no minimum at all. Uniqueness needs **strict** convexity; a ridge penalty $\lambda\|w\|^2$ makes the loss strongly convex and restores it.

> **Convex is not "GD always converges":** Convexity removes bad local minima, not bad step sizes. On $f(x)=x^2$, gradient descent multiplies $x$ by $1-2\eta$ each step: it diverges for $\eta>1$. For an $L$-smooth convex function, $\eta\le1/L$ guarantees descent.

**Question:** Which function is **not** convex on all of $\mathbb{R}$?

- A. x²
- B. |x|
- C. eˣ
- D. x³

**Answer:** D. x³ — $\frac{d^2}{dx^2}x^3=6x<0$ for $x<0$. Concretely, $a=-2$, $b=0$, $\theta=\tfrac12$: $f(-1)=-1$ exceeds the chord value $\tfrac12(-8+0)=-4$.

**Question:** $f$ is convex and differentiable, and $\nabla f(x_0)=0$. Then $x_0$ is…

- A. a global minimum
- B. a local minimum that may not be global
- C. possibly a saddle point
- D. possibly a maximum

**Answer:** A. a global minimum — The tangent inequality $f(y)\ge f(x_0)+\nabla f(x_0)^\top(y-x_0)=f(x_0)$ holds for every $y$. Stationary points of convex functions are always global minima.

**Key points**

- Convex: every chord lies on or above the graph — $f(\theta a+(1-\theta)b)\le\theta f(a)+(1-\theta)f(b)$.
- Equivalent tests: tangents below the graph; $\nabla^2f\succeq0$ everywhere.
- Local minima are global, and $\nabla f=0$ certifies optimality.
- Sums, affine compositions and maxima of convex functions are convex — that is how ML losses are certified.

---

From MLFoundry (https://www.mlfoundry.in). The web page adds interactive figures and diagrams.
