Convex vs non-convex functions: Exercises — AI-ML deep dive

Before we start, three tools we lean on constantly. Each is stated in plain words so no symbol appears unearned.

Definition The three convexity lenses (recap in plain words)

Chord test: the curve never rises above the straight line joining any two of its points. In symbols, for any two inputs $x, y$ and any blend weight $λ \in [0, 1]$ : $f (λ x + (1 - λ) y) \leq λ f (x) + (1 - λ) f (y) .$ The left side is the curve at the blended input; the right side is the straight chord at the same spot. (This one needs no differentiability — just a convex domain.)
Second derivative ( $f^{''}$ ): $f^{''} (x)$ measures how the slope itself is changing. Positive $f^{''}$ means the slope keeps increasing — the curve keeps turning upward, like the inside of a cup. 1D rule (for $C^{2}$ $f$ on a convex domain): convex $⟺ f^{''} (x) \geq 0$ for every $x$ .
Hessian ( $\nabla^{2} f$ ): the multivariable version of $f^{''}$ — a square grid of all second derivatives. It is positive semidefinite (written $⪰ 0$ ) when $v^{⊤} \nabla^{2} f v \geq 0$ for every direction vector $v$ . Multi-D rule (for $C^{2}$ $f$ on a convex domain): convex $⟺ \nabla^{2} f ⪰ 0$ everywhere.

For $2 \times 2$ matrices we use one shortcut over and over, so let's earn it now.

Recall Why a diagonal matrix's eigenvalues are its diagonal entries

For $H = [a 0 0 c]$ , the quadratic form is $v^{⊤} H v = a v_{1}^{2} + c v_{2}^{2}$ . Feeding in the axis directions $v = (1, 0)$ gives $a$ and $v = (0, 1)$ gives $c$ : the surface curves by exactly $a$ along one axis and $c$ along the other — those are the two principal curvatures, i.e. the eigenvalues. Equivalently $det (H - λ I) = (a - λ) (c - λ) = 0$ has roots $λ = a, c$ . So for diagonal Hessians you can read convexity straight off the diagonal.

Level 1 — Recognition

Recall Solution L1.1

Each is $C^{2}$ on all of $R$ (a convex domain), so the $f^{''} \geq 0$ everywhere rule applies.

(a) $f^{''} = 0 \geq 0$ everywhere → convex (affine functions are convex and concave — the boundary case).
(b) $f^{''} = 12 x^{2} \geq 0$ everywhere → convex (equals $0$ only at $x = 0$ ; still $\geq 0$ ).
(c) $f^{''} = - cos x$ , which is positive on some intervals and negative on others → not convex.
(d) $f^{''} = 2 \geq 0$ everywhere → convex. Convex: (a), (b), (d). Not: (c).

Recall Solution L1.2

The matrix is diagonal, so (by the boxed recall above) its diagonal entries $3$ and $- 1$ are its eigenvalues — the surface curves by $+ 3$ along the first axis and by $- 1$ along the second. One eigenvalue is negative → the matrix is indefinite → not positive semidefinite → not convex at that point. The negative direction ( $y$ -axis here) is a direction where the surface bends down.

Level 2 — Application

Recall Solution L2.1

$f^{'} (x) = - e^{- x}$ , $f^{''} (x) = e^{- x}$ . Since $e^{- x} > 0$ for every real $x$ , $f^{''} > 0$ everywhere → strictly convex ( $f$ is $C^{2}$ on all of $R$ , so the test is valid). Stationary points need $f^{'} (x) = 0$ , i.e. $- e^{- x} = 0$ . But $e^{- x}$ is never $0$ → zero stationary points. A convex function can have no minimum if it keeps sloping down forever (here toward $x \to + \infty$ ).

Recall Solution L2.2

Second partials: $f_{xx} = 6$ , $f_{y y} = 6$ , $f_{x y} = 2$ . So $\nabla^{2} f = [6226] .$ Check the shortcut: $a = 6 > 0$ , $c = 6 > 0$ , $det = 6 \cdot 6 - 2^{2} = 36 - 4 = 32 > 0$ . Positive definite → strictly convex everywhere.

Recall Solution L2.3

Blended input: $λ x + (1 - λ) y = \frac{1}{4} (0) + \frac{3}{4} (4) = 3$ .

Left (curve): $f (3) = 9$ .
Right (chord): $λ f (x) + (1 - λ) f (y) = \frac{1}{4} f (0) + \frac{3}{4} f (4) = \frac{1}{4} (0) + \frac{3}{4} (16) = 12$ . $9 \leq 12$ ✓. The curve sits below the chord, as convexity promises.

Level 3 — Analysis

Recall Solution L3.1

$f^{'} (x) = 3 x^{2} - 3$ , $f^{''} (x) = 6 x$ .

$f^{''} (x) \geq 0 ⟺ x \geq 0$ → convex on $[0, \infty)$ .
$f^{''} (x) \leq 0 ⟺ x \leq 0$ → concave on $(- \infty, 0]$ . The sign of $f^{''}$ flips at $x = 0$ : this is the inflection point. Because $f^{''}$ is not $\geq 0$ over the whole line, $f$ is not convex globally — it's a textbook non-convex shape.

The figure below draws exactly this. Look at the two thick coloured pieces of the curve: the plum left half ( $x \leq 0$ ) caves down like a frown — that's the concave region where $f^{''} < 0$ . The teal right half ( $x \geq 0$ ) cups up like a smile — the convex region where $f^{''} > 0$ . The orange dashed line marks $x = 0$ , the single point where the curvature flips sign (the inflection). Notice the curve is perfectly smooth there — nothing dramatic happens to $f$ itself, only to its bending direction. That visual is why "convex" can never describe the whole cubic: no single bowl shape covers both halves.

Figure s01 — Convex vs concave regions of the cubic $f (x) = x^{3} - 3 x$ . The plum arc on $x \leq 0$ is concave ( $f^{''} < 0$ , curving down like a frown); the teal arc on $x \geq 0$ is convex ( $f^{''} > 0$ , cupping up like a smile); the orange dashed vertical at $x = 0$ marks the inflection point where curvature flips sign. Axes: horizontal $x$ , vertical $f (x)$ .

Recall Solution L3.2

$\nabla^{2} f = [2442]$ (constant, so same everywhere). $det = 2 \cdot 2 - 4^{2} = 4 - 16 = - 12 < 0$ → eigenvalues have opposite signs → indefinite. Eigenvalues satisfy $λ_{1} + λ_{2} = 2 + 2 = 4$ and $λ_{1} λ_{2} = - 12$ , giving $λ = 2 \pm 4$ , i.e. $6$ and $- 2$ . One up-curving direction, one down-curving → saddle point, non-convex.

Recall Solution L3.3

$\nabla^{2} f = [20 0 2 k]$ , diagonal so eigenvalues are $2$ and $2 k$ . PSD requires both eigenvalues $\geq 0$ : $2 \geq 0$ ✓ always, and $2 k \geq 0 ⟺ k \geq 0$ . Convex $⟺ k \geq 0$ . For $k = 0$ it's a flat "valley trough" (still convex, min not unique — a whole line of minima). For $k < 0$ the second eigenvalue is negative → saddle.

Level 4 — Synthesis

Recall Solution L4.1

Proof via the chord test. Fix inputs $x, y$ and weight $λ \in [0, 1]$ . Convexity of $f$ and $g$ gives $f (λ x + (1 - λ) y) \leq λ f (x) + (1 - λ) f (y), g (λ x + (1 - λ) y) \leq λ g (x) + (1 - λ) g (y) .$ Multiply the first by $a \geq 0$ and the second by $b \geq 0$ — inequalities survive multiplication by nonnegatives — then add: $a f (\cdot) + b g (\cdot) \leq λ (a f (x) + b g (x)) + (1 - λ) (a f (y) + b g (y)),$ which is exactly $h (λ x + (1 - λ) y) \leq λh (x) + (1 - λ) h (y)$ . So $h$ is convex. $■$ Why the regularizer stays convex: $∥ θ ∥^{2}$ has constant Hessian $2 I$ (PSD). Adding it to a convex data loss is a nonnegative combination ( $a = b = 1$ ), so the total is convex. This is why ridge regression stays a nice single-bowl problem — see Convex Optimization.

Recall Solution L4.2

Step 1 — Taylor's theorem with exact (Lagrange) remainder. For a $C^{2}$ function, expanding $f$ around a base point $x$ and evaluating at $y$ gives, for some point $c$ strictly between $x$ and $y$ , $f (y) = f (x) + f^{'} (x) (y - x) + \frac{1}{2} f^{''} (c) (y - x)^{2} .$ Why this tool? Taylor's theorem is the one device that writes $f (y)$ exactly — no approximation — while isolating the curvature into a single remainder term $\frac{1}{2} f^{''} (c) (y - x)^{2}$ . That is precisely the term our hypothesis $f^{''} \geq 0$ controls. Step 2 — Bound the remainder. Since $f^{''} (c) \geq 0$ (hypothesis) and $(y - x)^{2} \geq 0$ (a square), the remainder is $\geq 0$ . Dropping a nonnegative term can only decrease the right side: $f (y) \geq f (x) + f^{'} (x) (y - x) .$ This is the first-order (tangent) condition: the graph lies above every tangent line. Step 3 — Tangent condition $\Rightarrow$ chord test. Let $z = λ x + (1 - λ) y$ . Apply the tangent inequality from Step 2 twice, based at $z$ : $f (x) \geq f (z) + f^{'} (z) (x - z), f (y) \geq f (z) + f^{'} (z) (y - z) .$ Weight by $λ \geq 0$ and $(1 - λ) \geq 0$ and add. The slope terms combine into $f^{'} (z) [λ (x - z) + (1 - λ) (y - z)]$ , and the bracket is $λ x + (1 - λ) y - z = z - z = 0$ , so it vanishes: $λ f (x) + (1 - λ) f (y) \geq f (z) = f (λ x + (1 - λ) y) .$ That is the chord test — $f$ is convex. $■$ What it looks like: Taylor gives us "curve above tangent" from the sign of curvature; averaging two such tangent inequalities gives "curve below chord."

Level 5 — Mastery

Recall Solution L5.1

(a) Stationary points — set the gradient to zero. $f_{x} = 2 x = 0 \Rightarrow x = 0$ . $f_{y} = 4 y^{3} - 4 y = 4 y (y^{2} - 1) = 0 \Rightarrow y \in {0, 1, - 1}$ . Stationary points: $(0, 0), (0, 1), (0, - 1)$ . (b) Hessian $\nabla^{2} f = [20 0 12 y^{2} - 4]$ (diagonal → eigenvalues on the diagonal).

At $(0, 0)$ : $[20 0 - 4]$ → eigenvalues $2, - 4$ → indefinite → saddle point.
At $(0, 1)$ : $12 (1) - 4 = 8$ → $[2008]$ → both positive → local min, value $f = 0 + 1 - 2 = - 1$ .
At $(0, - 1)$ : identical, $12 (1) - 4 = 8$ → local min, value $f = - 1$ . (c) Since the Hessian is indefinite at $(0, 0)$ , $f$ is not convex. There are two equally-deep global minima at $(0, \pm 1)$ plus a saddle between them. Gradient descent starting with $y > 0$ flows to $(0, 1)$ ; starting with $y < 0$ flows to $(0, - 1)$ . Same loss value here, but this is the mechanism by which non-convex losses split into basins — the outcome depends on initialization.

The figure below is the slice through $x = 0$ , so we watch the $y$ -behaviour alone (where all the interesting non-convexity lives). Trace the black curve: it dips into a teal basin at $y = - 1$ , climbs up over an orange hump at the origin, then dips into a second plum basin at $y = + 1$ . Both basins bottom out at $f = - 1$ — equally deep global minima — while the orange point at the top ( $f = 0$ ) is the saddle. This is the visual proof of "two basins": a marble released on the left of the hump rolls to $(0, - 1)$ , one on the right rolls to $(0, + 1)$ . Which minimum you reach is decided purely by which side of the hump you start on — the essence of initialization-dependent optimization.

Figure s02 — Two basins plus a saddle for $f (0, y) = y^{4} - 2 y^{2}$ (slice at $x = 0$ ). The black curve dips to a teal minimum at $y = - 1$ (value $- 1$ ), rises over an orange hump/saddle at $y = 0$ (value $0$ ), then dips to a plum minimum at $y = + 1$ (value $- 1$ ). Two equally deep global minima separated by a hump — descent reaches one or the other depending on the sign of the starting $y$ . Axes: horizontal $y$ , vertical $f$ .

Recall Solution L5.2

Domain $x > 0$ (a convex set) and $f$ is $C^{2}$ there. $f^{'} (x) = lo g x + 1$ . $f^{''} (x) = \frac{1}{x}$ . On $x > 0$ , $\frac{1}{x} > 0$ everywhere → convex on all of $(0, \infty)$ . Minimizer: $f^{'} (x) = 0 \Rightarrow lo g x = - 1 \Rightarrow x = e^{- 1}$ . Value $f (e^{- 1}) = e^{- 1} lo g (e^{- 1}) = e^{- 1} (- 1) = - e^{- 1} \approx - 0.3679$ . Since $f$ is convex, this single stationary point is the global minimum.

Recall Solution L5.3

Compute the Hessian. Second partials: $g_{xx} = 2 α = 4$ , $g_{y y} = 2 β = 10$ , $g_{x y} = 2 γ$ . So $\nabla^{2} g = [4 2 γ 2 γ 10] .$ Apply the $2 \times 2$ PSD shortcut: $4 \geq 0$ ✓, $10 \geq 0$ ✓, and $det = 4 \cdot 10 - (2 γ)^{2} = 40 - 4 γ^{2} \geq 0 ⟺ γ^{2} \leq 10 ⟺ ∣ γ ∣ \leq 10 .$ Convex $⟺ - 10 \leq γ \leq 10$ (with $10 \approx 3.162$ ). Beyond that, the cross term dominates, $det < 0$ , and a downhill direction opens up.

Recall One-line self-quiz before you leave

For a $2 \times 2$ Hessian $[a b b c]$ , what three conditions guarantee convexity? ::: $a \geq 0$ , $c \geq 0$ , and $a c - b^{2} \geq 0$ (nonnegative diagonals and nonnegative determinant).

Connections

Hessian Matrix — the object every L2–L5 problem tested for PSD.
Positive Semidefinite Matrices — the $a c - b^{2} \geq 0$ shortcut lives here.
Saddle Points — L3.2 and L5.1 both produced these.
Gradient Descent · Local vs Global Minima — why L5.1's two basins matter in practice.
Convex Optimization · Loss Functions · Taylor Series Expansion — the L4 synthesis threads.