Convex vs non-convex functions

WHY do we care? (the 80/20 core)

Machine learning is mostly minimizing a loss function $L(\theta)$ . The whole game is: find parameters $\theta$ that make loss small.

If $L$ is convex: there's essentially one basin. Follow the slope downhill → guaranteed to reach the best answer. (Linear/logistic regression, SVM.)
If $L$ is non-convex: multiple valleys, ridges, saddle points. Downhill can strand you in a mediocre valley (a bad local minimum). (Neural networks.)

So "convex vs non-convex" tells you how hard your optimization is and whether you can trust the answer you converged to.

WHAT exactly is convexity?

HOW do we check convexity? (three lenses)

Lens 1 — The chord test (definition itself)

Pick the midpoint $\lambda = \tfrac12$ : convex means $f\!\left(\frac{x+y}{2}\right) \le \frac{f(x)+f(y)}{2}.$ The average of the outputs is at least the output of the average.

Lens 2 — First-order (tangent line) condition

For a differentiable $f$ , convex $\iff$ the graph lies above every tangent line: $f(y) \ge f(x) + \nabla f(x)^\top (y - x) \quad \forall x,y.$

Lens 3 — Second-order (curvature) condition — the practical one

For twice-differentiable $f$ :

1D: convex $\iff f''(x) \ge 0$ everywhere (curves upward / never bends down).
Multivariate: convex $\iff$ the Hessian $\nabla^2 f(x)$ is positive semidefinite (PSD) everywhere, i.e. $v^\top \nabla^2 f(x)\, v \ge 0$ for all $v$ .

Deriving the 1D second-order test from scratch

We show: if $f''(x)\ge 0$ everywhere, then the tangent-line condition (Lens 2) holds.

Step 1 — Taylor with exact remainder. For some $c$ between $x$ and $y$ : $f(y) = f(x) + f'(x)(y-x) + \tfrac12 f''(c)\,(y-x)^2.$ Why this step? Taylor's theorem gives an exact expression, isolating the curvature term.

Step 2 — Bound the remainder. Since $f''(c)\ge 0$ and $(y-x)^2 \ge 0$ : $\tfrac12 f''(c)(y-x)^2 \ge 0.$ Why this step? This is the only unknown term; nonnegative curvature makes it nonnegative.

Step 3 — Conclude. $f(y) \ge f(x) + f'(x)(y-x).$ Why this step? That's exactly Lens 2 — graph above tangent — hence convex. $\blacksquare$

Worked examples

Common mistakes (Steel-manned)

Flashcards

Convex function definition (inequality form)

f(\lambda x+(1-\lambda)y) \le \lambda f(x)+(1-\lambda)f(y)

for all

\lambda\in[0,1]

— curve below the chord.

Geometric meaning of convexity

The line segment joining any two points on the graph lies on or above the graph (bowl shape).

Second-order convexity test in 1D

f''(x)\ge 0

for ALL

x

in the domain.

Multivariate convexity test

Hessian

\nabla^2 f(x)

is positive semidefinite everywhere (

v^\top H v \ge 0

Key optimization payoff of convexity

Every local minimum is a global minimum (stationary point ⇒ global min).

x^3

convex?

No —

f''=6x

changes sign;

x=0

is an inflection point.

x^2+y^2

convex?

Yes — Hessian

=\mathrm{diag}(2,2)

, positive definite everywhere.

Why is

x^2-y^2

non-convex?

Hessian eigenvalues

2,-2

(indefinite); origin is a saddle point.

What functions are both convex AND concave?

Only affine (linear + constant) functions.

Why do neural nets have non-convex loss?

Composition of nonlinear activations creates multiple minima/saddles ⇒ Hessian not PSD everywhere.

First-order convexity condition

f(y)\ge f(x)+\nabla f(x)^\top(y-x)

— graph lies above every tangent line.

Recall Feynman: explain to a 12-year-old

Imagine a skateboard ramp. A convex ramp is a single smooth U-shaped bowl: no matter where you drop a marble, it always rolls down to the same lowest point. Easy — you can't get stuck. A non-convex ramp is a bumpy skate park with many dips. Your marble might stop in a small dip that isn't the deepest one, thinking "I'm done!" while a deeper valley sits right over the hill. Convex = one honest bowl; non-convex = tricky landscape with fake bottoms.

Connections

Gradient Descent — convergence to global optimum is guaranteed only under convexity.
Hessian Matrix — its positive-semidefiniteness is the convexity test.
Positive Semidefinite Matrices — the eigenvalue/quadratic-form criterion used above.
Taylor Series Expansion — the tool used to derive the second-order test.
Saddle Points — the non-convex failure mode ( $x^2-y^2$ ).
Loss Functions — MSE/logistic loss are convex; neural-net loss is not.
Convex Optimization — the theory built entirely on this property.
Local vs Global Minima — the distinction convexity dissolves.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, machine learning me hum hamesha ek loss function ko minimize karte hain — matlab aise parameters dhoondhna jaha error sabse kam ho. Ab yaha sawal aata hai: function ka shape kaisa hai? Agar function convex hai, toh woh ek single katora (bowl) jaisa hota hai. Kahin se bhi marble chhodo, woh ghum-ghum ke same sabse neeche wale point pe pahunch jaata hai. Iska matlab: gradient descent chalao, aur guaranteed global minimum mil jaayega. No tension of getting stuck.

Convex check karne ka sabse practical tareeka: second derivative. 1D me agar $f''(x) \ge 0$ har jagah (poore domain me, sirf ek point pe nahi!), toh function convex hai. Multi-dimension me yahi cheez Hessian matrix ke through hoti hai — Hessian positive semidefinite honi chahiye (saare eigenvalues $\ge 0$ ). Jaise $x^2$ ka $f''=2$ hamesha positive — convex. Lekin $x^3$ ka $f''=6x$ kabhi negative kabhi positive — isliye NON-convex.

Non-convex functions me kai saare valleys hote hain — bilkul bumpy skate park jaisa. Gradient descent kisi chhoti si dip me phas sakta hai (local minimum) aur soch le "bas ho gaya," jabki asli deepest valley pahaad ke us paar hai. Neural networks ka loss aisa hi non-convex hota hai, kyunki nonlinear activations layer-by-layer milke bahut tedhi-medhi landscape bana dete hain.

Yaad rakhne ka simple funda: convex ka matlab local minimum hi global minimum hota hai — yahi convexity ka asli power hai. Non-convex me yeh guarantee tut jaati hai. Isliye jab bhi koi optimization problem dekho, pehle poochho: "Yeh convex hai kya?" — agar haan, toh life easy; agar nahi, toh tricks (random restarts, momentum, etc.) chahiye.

WHY do we care? (the 80/20 core)

WHAT exactly is convexity?

HOW do we check convexity? (three lenses)

Lens 1 — The chord test (definition itself)

Lens 2 — First-order (tangent line) condition

Lens 3 — Second-order (curvature) condition — the practical one

Deriving the 1D second-order test from scratch

Worked examples

Common mistakes (Steel-manned)

Flashcards

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Calculus & Optimization Basics

Connections