Convexity, Optimization Dynamics & Duality

Taylor approximations, Hessian condition numbers, momentum acceleration, and KKT duality.

⏱ 20 min read🎯 Prerequisites: Multivariate Calculus & Matrix Calculus

🔍 Inspect Architecture: Support vector machine

💡 1. Core Intuition & Concepts

Optimization algorithms traverse high-dimensional loss landscapes to locate minima. Understanding the condition number of the Hessian matrix explains why standard gradient descent oscillates in narrow ravines, how momentum damps orthogonal oscillations, and how Lagrange duality transforms constrained problems into solvable duals.

📐 2. Mathematical Formulations & Derivations

Second-Order Taylor Loss Surface

f(w + \Delta w) \approx f(w) + \nabla f(w)^T \Delta w + \frac{1}{2} \Delta w^T H \Delta w

Local quadratic approximation where H is the symmetric positive semi-definite Hessian.

Hessian Condition Number & Convergence

\kappa = \frac{\lambda_{\max}(H)}{\lambda_{\min}(H)} \implies \|w_t - w^*\| \le \left( \frac{\kappa - 1}{\kappa + 1} \right)^t \|w_0 - w^*\|

Ill-conditioned surfaces (κ ≫ 1) cause gradient descent to bounce between valley walls.

Momentum Accelerated Dynamics (Polyak Heavy Ball)

m_t = \beta m_{t-1} + (1-\beta) \nabla f(w_t) \implies \text{Accelerated Rate: } \frac{\sqrt{\kappa}-1}{\sqrt{\kappa}+1}

Damps high-frequency oscillations along high-curvature directions and accelerates flat valleys.

Karush-Kuhn-Tucker (KKT) Conditions & Duality

\mathcal{L}(w, \alpha, \mu) = f(w) + \sum_{i=1}^m \alpha_i g_i(w) + \sum_{j=1}^p \mu_j h_j(w) \quad \text{s.t. } \alpha_i \ge 0, \; \alpha_i g_i(w) = 0

Primal-dual optimality conditions. Complementary slackness α_i g_i(w) = 0 isolates support vectors.

• Let the gradient update rule be w_{t+1} = w_t - alpha * ∇f(w_t) = w_t - alpha * H w_t = (I - alpha * H) w_t.

• Eigendecompose the Hessian H = Q Lambda Q^T, where eigenvalues satisfy 0 < lambda_1 <= ... <= lambda_D.

• In the rotated coordinate frame z_t = Q^T w_t, the update decouples: z_{t+1, i} = (1 - alpha * lambda_i) z_{t, i}.

• For convergence in all directions, the contraction factor must satisfy |1 - alpha * lambda_i| < 1 for all i, which requires 0 < alpha < 2 / lambda_max.

• The optimal rate minimizing the worst-case contraction max(|1 - alpha * lambda_min|, |1 - alpha * lambda_max|) occurs when 1 - alpha * lambda_min = -(1 - alpha * lambda_max), giving alpha* = 2 / (lambda_min + lambda_max). Q.E.D.

⚙️ 3. Step-by-Step Computational Mechanism

Convexity Criterion

A function f is strictly convex iff f(lambda x + (1-lambda) y) < lambda f(x) + (1-lambda) f(y), guaranteeing any local minimum is the global minimum.

Ill-Conditioned Ravines

When kappa = lambda_max / lambda_min >> 1, gradients point almost perpendicularly to the direct path toward the true minimum.

Lagrangian Dual Formulation

Transforming constrained optimization min_w f(w) into dual max_alpha min_w L(w, alpha) allows kernel trick inner-product substitutions.

💻 4. Code from Scratch (python)

math_opt_duality.py

import numpy as np

# Simulating Gradient Descent vs Momentum on an Ill-Conditioned Ravine (Condition Number kappa = 50)
def simulate_optimization():
    # Quadratic: f(x, y) = 0.5 * (50 * x^2 + y^2) -> Hessian diag(50, 1), kappa = 50
    H = np.array([[50.0, 0.0], [0.0, 1.0]])
    lr = 0.035  # Near optimal for fastest convergence
    
    # 1. Plain Gradient Descent
    w_gd = np.array([1.0, 10.0])
    gd_path = [w_gd.copy()]
    for _ in range(30):
        grad = np.dot(H, w_gd)
        w_gd -= lr * grad
        gd_path.append(w_gd.copy())

    # 2. Momentum (Polyak Heavy Ball)
    w_mom = np.array([1.0, 10.0])
    v = np.zeros(2)
    beta = 0.85
    mom_path = [w_mom.copy()]
    for _ in range(30):
        grad = np.dot(H, w_mom)
        v = beta * v + (1 - beta) * grad
        w_mom -= lr * 3.0 * v
        mom_path.append(w_mom.copy())

    print(f"Final GD distance to minimum:       {np.linalg.norm(w_gd):.4f}")
    print(f"Final Momentum distance to minimum: {np.linalg.norm(w_mom):.4f}")

if __name__ == "__main__":
    simulate_optimization()

🧠 5. Comprehension Checkpoint

Answer all 1 questions correctly to complete the chapter · 0 / 1 done

Q1/1 What is the primary geometric consequence of a high Hessian condition number κ = λ_max / λ_min ≫ 1 during gradient descent?

In the catalog

Support vector machines

Finished this chapter?

Learn ML from Scratch: Beginner to Advanced