Convexity and concavity · Calculus × Computing

What is it?

$f$ is convex if the chord between any two points of its graph lies above the graph — equivalently, for smooth $f$ , if $f'' \ge 0$ . For convex functions every local minimum is global, which is why convex problems are the ones optimization can reliably solve.

Why does it exist?

General optimization is hopeless: a function can hide its minimum anywhere. Convexity is the structural property that makes local information (the slope here) globally trustworthy: if the slope says "downhill is that way", the global minimum really is that way.

Intuition

A convex function is a bowl: no bumps, no secondary valleys. The tangent line at any point lies entirely below the graph, so $f(y) \ge f(x) + f'(x)(y - x)$ — the linear prediction is always an underestimate, and a point with zero slope beats every other point.

Formal definition

$f$ is convex on an interval if for all $x, y$ and $t \in [0,1]$ :

f\big(tx + (1-t)y\big) \le t f(x) + (1 - t) f(y).

For differentiable $f$ : convex $\iff f(y) \ge f(x) + f'(x)(y - x)$ ; for twice differentiable $f$ : convex $\iff f'' \ge 0$ . $f$ is concave if $-f$ is convex. An inflection point is where concavity changes.

Idea of the proof

Local ⇒ global: if $x^\ast$ were a local but not global minimum, the chord to a lower point $y$ would lie below $f(x^\ast)$ arbitrarily close to $x^\ast$ , contradicting local minimality.

Formulas

$f\big(tx + (1-t)y\big) \le t f(x) + (1 - t) f(y)$; $f\big(\E[X]\big) \le \E\big[f(X)\big]$
Jensen's inequality (convex $f$ ): $\nabla^2 f(x) \succeq 0 \ \ \forall x \iff f \text{ convex}$
several variables: positive semidefinite Hessian

Why does it matter?

Linear and logistic regression, support vector machines, LASSO and most of operations research are convex: they come with guarantees and reliable solvers. Deep networks are not, which is why their training is an empirical art — and why it is remarkable that gradient descent works so well on them anyway.

Where it shows up in computing

Operations research and logistics★★★★★fundamentalOptimization and systems
Convex optimization (linear, quadratic, conic programs) is the workhorse of planning and logistics.

Where it shows up in AI

Loss function★★★★★fundamentalAI and machine learning
Squared error and cross-entropy are convex in the predictions; for linear models, in the parameters too.
Support vector machines★★★★★fundamentalAI and machine learning
Training an SVM is a convex quadratic program: a unique global optimum.
Loss landscape★★★★★frequentAI and machine learning
Deep-network losses are non-convex: many minima and saddles, yet good minima are easy to find in practice.

Where is it used?

Computing topics reachable from here, through the chain of ideas that leads to them:

What depends on it

KKT conditions

Exercises

1Proof

Show that $f(x) = \ln(1 + e^x)$ (softplus) is convex.

Solution

$f'(x) = \sigma(x)$ and $f'(x) = \sigma(x)(1 - \sigma(x)) > 0$ .

2AI

Is the loss of a 1-hidden-layer network convex in its weights? Hint: swap two hidden neurons.