Convexity & Why It Matters

What is a Convex Function?

A function $f(x)$ is Convex if drawing a straight line segment between any two points on its graph shows that the function lies on or below the line segment:

$$f(\lambda x + (1-\lambda) y) \le \lambda f(x) + (1-\lambda) f(y) \quad \forall \lambda \in [0, 1]$$

  CONVEX FUNCTION (Bowl Shape)                 NON-CONVEX FUNCTION (Multiple Local Minima)
  Loss                                         Loss
   High ┤  \        Secant Line /               High ┤    /\      /\
        │   \   .--------------.                │   /  \    /  \
        │    \ /  Function    /                 │  /    \  /    \  Global Min
    Low ┴─────'──────────────'─────► x          Low ┴─'──────\'──────'──────────► x
            Single Global Min                         Local Min   Global Min

First and Second-Order Convexity Conditions

For twice-differentiable function $f$:

1. First-Order Condition: $f(y) \ge f(x) + \nabla f(x)^T (y - x)$ for all $x, y$. (The 1st-order Taylor tangent line lies everywhere below the function).
2. Second-Order Condition: Hessian matrix $\nabla^2 f(x)$ is Positive Semi-Definite ($\nabla^2 f(x) \succeq 0$) for all $x$.

Convex vs Non-Convex ML Models

┌───────────────────────────────────────┬───────────────────────────────────────┐
│       CONVEX ML MODELS                │       NON-CONVEX ML MODELS            │
├───────────────────────────────────────┼───────────────────────────────────────┤
│ Linear Regression (MSE Loss)          │ Deep Neural Networks (MLP, CNN, LLM)  │
│ Logistic Regression (Cross-Entropy)   │ Matrix Factorization                  │
│ Support Vector Machines (Hinge Loss)  │ Autoencoders                          │
│ Lasso / Ridge Regression              │ Gaussian Mixture Models (GMM)         │
│ Single Global Minimum Guaranteed!     │ Thousands of Saddle Points & Minima!  │
└───────────────────────────────────────┴───────────────────────────────────────┘

Why Deep Learning Works Despite Non-Convexity

Deep neural networks are non-convex, yet Gradient Descent reliably trains them to state-of-the-art performance. Why?

1. Saddle Points, Not Local Minima: High-dimensional geometry (Dauphin et al., 2014) proves true sub-optimal local minima are extremely rare. Most zero-gradient points are Saddle Points, which SGD with momentum escapes easily.
2. Over-parameterization: Having millions of parameters creates many equivalent zero-loss paths through weight space.
3. Implicit Regularization of SGD: Stochastic mini-batch noise acts as implicit regularization, kicking optimization out of sharp sub-optimal basins into broad flat minima.

Say this out loud

Convexity means the secant line between any two points lies above the function graph, guaranteeing that any local minimum is a global minimum. Models like Linear Regression, SVMs, and Logistic Regression are convex. Deep neural networks are non-convex, but SGD succeeds because high-dimensional zero-gradient points are mostly saddle points rather than local minima traps.

Follow-ups to expect

• What is Strong Convexity? A function is m-strongly convex if $\nabla^2 f(x) \succeq m I$ for $m > 0$. Strong convexity guarantees a quadratic lower bound on growth, ensuring linear convergence rates for gradient descent.
• What is Jensen's Inequality? For any convex function $f$ and random variable $X$: $f(\mathbb{E}[X]) \le \mathbb{E}[f(X)]$. Forms the basis of the Variational Autoencoder (VAE) evidence lower bound (ELBO).