Foundations — Convex vs non-convex functions

This page assumes you know nothing. Every squiggle the parent note used — $f$, $\theta$, $\lambda$, $\nabla$, $\top$, $⪰$ — is built here from the ground up, one at a time, each with a picture and a reason it exists. Read top to bottom; nothing is used before it's earned.

0. What is a function $f$, really?

The picture of a function is its graph: for every input $x$ on the horizontal axis, we plot a point at height $f(x)$. Sweep across all inputs and the dots join into a curve.

Why the topic needs it: in machine learning the machine is a loss function Loss Functions $L(\theta )$ — you feed it your model's settings, it tells you how wrong the model is. The whole topic is about the shape of that curve.

1. The parameter symbol $\theta$

So $L(\theta )$ = "how bad is the model when the knobs are set to $\theta$." Turning the knobs moves you left/right along the floor; the loss curve tells you the height there. Optimization = find the knob setting with the lowest height.

Why the topic needs it: the parent note's sentence "minimize $L(\theta )$" is meaningless until you know $\theta$ is just the input to a function-machine.

2. Two points and the segment between them

To even state convexity we must talk about "any two points" and "the line between them." So we need a clean way to name every point on that connecting line using one slider.

Given two floor-positions $x$ and $y$, the blended position is $\lambda x+(1-\lambda )y.$

Read it as a recipe: take $\lambda$ scoops of $x$ and $(1-\lambda )$ scoops of $y$.

• $\lambda =1$: all $x$ → you're standing at $x$.
• $\lambda =0$: all $y$ → you're standing at $y$.
• $\lambda =\frac{1}{2}$: half-and-half → the exact midpoint.

As $\lambda$ slides from $0$ to $1$, the blended point sweeps the entire straight segment between $x$ and $y$. One dial, every in-between point.

Why the topic needs it: this exact expression appears on both sides of the master convexity inequality. Left side blends the inputs; right side blends the outputs.

3. The chord vs the curve

Take the two graph points $(x,f(x))$ and $(y,f(y))$. The straight line joining them is the chord.

Convex means: curve height $\le$ chord height, for every choice of $x,y,\lambda$. That's it — the parent's "master definition" decoded.

4. Slope, then the derivative $f^{\prime }$

To talk about tangent lines (Lens 2) and curvature (Lens 3), we need slope.

Why this tool and not another? We ask "which way is downhill, and how steep?" — that is a question about instantaneous slope, and the derivative is the one tool that answers it. Averages over an interval won't do; we need the slope at a single knob-setting so we know which way to nudge.

A point where $f^{\prime }(x)=0$ is flat — a stationary point. Bottoms of valleys, tops of hills, and saddle flat-spots all have zero slope. (Which kind it is comes next.)

5. Second derivative $f^{\prime \prime }$ — the curvature

Slope tells you the tilt. But convexity is about whether the curve bends up or down. So we take the slope of the slope.

Why this is THE practical convexity test: "does the curve cup upward everywhere?" is exactly "$f^{\prime \prime }\ge 0$ everywhere." One clean sign-check, no dragging chords around. This is the parent's Lens 3 in 1D. See Taylor Series Expansion for why $f^{\prime \prime }$ is precisely the coefficient of curvature in the local picture.

6. Going multivariate: the gradient $\nabla f$ and the transpose $\top$

Real models have many knobs, so $\theta$ is a list of numbers (a vector), and $f$ eats the whole list.

So the first-order condition $f(y)\ge f(x)+\nabla f(x{)}^{\top }(y-x)$ reads: the number $\nabla f(x{)}^{\top }(y-x)$ is just "slope $\times$ how far you moved," i.e. the height the flat tangent predicts.

Why the topic needs it: with many knobs you can't say "left/right"; the gradient packages all directions, and $\top$ is the glue that turns a direction-of-motion $(y-x)$ into a predicted height change.

7. The Hessian ${\nabla }^{2}f$ and "$⪰0$"

Curvature in many dimensions isn't a single number — a surface can cup up one way and dome down another (a saddle!). We need a table of curvatures.

Why the topic needs it: multivariate convex $⟺{\nabla }^{2}f⪰0$ everywhere. One downward-bending direction (one negative slice) and you get a saddle — non-convex — and the guarantee that local = global evaporates.

8. Putting the payoff in one line

Convex bowl ⇒ a flat spot ($\nabla f=0$) can only be the bottom ⇒ every local minimum is the global minimum. That single implication is why Convex Optimization is "easy" and neural nets are "hard."

Prerequisite map

Equipment checklist

Reveal each and check you could explain it cold.