W Code - Pattern-Based DSA Learning Platform

Bhanu Bisht

Optimization Theory

Convexity, gradient descent variants, and convergence — optimizing ML models

Topics

Convexity

ML-Core

Python Implementation

import numpy as np

print("=" * 55)
print("CONVEXITY")
print("=" * 55)

# Check convexity: f(x) = x²
def f_convex(x): return x**2
def f_nonconvex(x): return np.sin(x)

# Convexity check: f(θx + (1-θ)y) ≤ θf(x) + (1-θ)f(y)
x, y = -2.0, 3.0
thetas = np.linspace(0, 1, 100)

print("\nConvexity Check: f(θx + (1-θ)y) vs θf(x) + (1-θ)f(y)")
print("\nf(x) = x² (should be convex):")
violations = 0
for theta in thetas:
    lhs = f_convex(theta*x + (1-theta)*y)
    rhs = theta*f_convex(x) + (1-theta)*f_convex(y)
    if lhs > rhs + 1e-10:
        violations += 1
print(f"  Violations: {violations}/100 → {'CONVEX ✓' if violations == 0 else 'NOT convex'}")

print("\nf(x) = sin(x) (should be non-convex):")
violations = 0
for theta in thetas:
    lhs = f_nonconvex(theta*x + (1-theta)*y)
    rhs = theta*f_nonconvex(x) + (1-theta)*f_nonconvex(y)
    if lhs > rhs + 1e-10:
        violations += 1
print(f"  Violations: {violations}/100 → {'CONVEX ✓' if violations == 0 else 'NOT convex ✗'}")

# Hessian PSD Check
print("\n" + "=" * 55)
print("HESSIAN CHECK FOR CONVEXITY")
print("=" * 55)

# MSE Loss: L = ||Xw - y||²
# Hessian = 2XᵀX
np.random.seed(42)
X = np.random.randn(100, 3)
H_mse = 2 * X.T @ X
eigenvalues = np.linalg.eigvalsh(H_mse)
print(f"\nMSE Hessian eigenvalues: {np.round(eigenvalues, 2)}")
print(f"All ≥ 0? {np.all(eigenvalues >= -1e-10)} → MSE is CONVEX ✓")

# Cross-entropy is convex
print("\nCross-entropy: second derivative = σ(z)(1-σ(z)) > 0 → convex ✓")

# Neural network is NOT convex
print("\n" + "=" * 55)
print("DEEP LEARNING: NON-CONVEX LOSS")
print("=" * 55)

def nn_loss(w):
    """Simple neural net: 1 hidden layer, 1 neuron"""
    x = 1.0; y = 0.5
    h = np.maximum(0, w * x)  # ReLU
    pred = h * 0.5
    return (pred - y) ** 2

ws = np.linspace(-3, 3, 1000)
losses = [nn_loss(w) for w in ws]

# Find local minima
from scipy.signal import argrelmin
local_min_idx = argrelmin(np.array(losses), order=50)[0]
print(f"\nNeural net loss landscape:")
print(f"  Number of local minima found: {len(local_min_idx)}")
print(f"  Loss is non-convex → SGD may find different minima!")
print(f"  But overparameterized nets → many good minima exist")

Key Takeaways

Convex function: any local minimum IS the global minimum

MSE, cross-entropy, hinge loss are all convex → guaranteed convergence

Neural network loss is NON-convex → but SGD still works in practice

Check convexity: Hessian must be PSD (all eigenvalues ≥ 0)

Sum of convex functions is convex → regularized losses stay convex

import numpy as np print("=" * 55) print("CONVEXITY") print("=" * 55) # Check convexity: f(x) = x² def f_convex(x): return x**2 def f_nonconvex(x): return np.sin(x) # Convexity check: f(θx + (1-θ)y) ≤ θf(x) + (1-θ)f(y) x, y = -2.0, 3.0 thetas = np.linspace(0, 1, 100) print("\nConvexity Check: f(θx + (1-θ)y) vs θf(x) + (1-θ)f(y)") print("\nf(x) = x² (should be convex):") violations = 0 for theta in thetas: lhs = f_convex(theta*x + (1-theta)*y) rhs = theta*f_convex(x) + (1-theta)*f_convex(y) if lhs > rhs + 1e-10: violations += 1 print(f" Violations: {violations}/100 → {'CONVEX ✓' if violations == 0 else 'NOT convex'}") print("\nf(x) = sin(x) (should be non-convex):") violations = 0 for theta in thetas: lhs = f_nonconvex(theta*x + (1-theta)*y) rhs = theta*f_nonconvex(x) + (1-theta)*f_nonconvex(y) if lhs > rhs + 1e-10: violations += 1 print(f" Violations: {violations}/100 → {'CONVEX ✓' if violations == 0 else 'NOT convex ✗'}") # Hessian PSD Check print("\n" + "=" * 55) print("HESSIAN CHECK FOR CONVEXITY") print("=" * 55) # MSE Loss: L = ||Xw - y||² # Hessian = 2XᵀX np.random.seed(42) X = np.random.randn(100, 3) H_mse = 2 * X.T @ X eigenvalues = np.linalg.eigvalsh(H_mse) print(f"\nMSE Hessian eigenvalues: {np.round(eigenvalues, 2)}") print(f"All ≥ 0? {np.all(eigenvalues >= -1e-10)} → MSE is CONVEX ✓") # Cross-entropy is convex print("\nCross-entropy: second derivative = σ(z)(1-σ(z)) > 0 → convex ✓") # Neural network is NOT convex print("\n" + "=" * 55) print("DEEP LEARNING: NON-CONVEX LOSS") print("=" * 55) def nn_loss(w): """Simple neural net: 1 hidden layer, 1 neuron""" x = 1.0; y = 0.5 h = np.maximum(0, w * x) # ReLU pred = h * 0.5 return (pred - y) ** 2 ws = np.linspace(-3, 3, 1000) losses = [nn_loss(w) for w in ws] # Find local minima from scipy.signal import argrelmin local_min_idx = argrelmin(np.array(losses), order=50)[0] print(f"\nNeural net loss landscape:") print(f" Number of local minima found: {len(local_min_idx)}") print(f" Loss is non-convex → SGD may find different minima!") print(f" But overparameterized nets → many good minima exist")