Skip to main content

Documentation Index

Fetch the complete documentation index at: https://resources.devweekends.com/llms.txt

Use this file to discover all available pages before exploring further.

Convex Optimization

​
Convex Optimization

​
Why Some Problems Are “Easy”

In gradient descent, we worry about getting stuck in local minima. But for some problems, every local minimum is the global minimum. These are convex optimization problems, and they’re the foundation of many ML algorithms. Here is a good analogy: imagine you are dropped somewhere on a landscape and told to find the lowest point. If the landscape is a bowl (convex), any downhill path leads to the same bottom. You cannot get tricked by false valleys. But if the landscape is mountainous (non-convex, like a neural network loss surface), you might walk into a small valley and think you have found the bottom, when the real bottom is on the other side of a ridge you cannot see. This distinction has enormous practical consequences. For convex problems (linear regression, logistic regression, SVMs), you can prove that your solution is globally optimal. For non-convex problems (deep neural networks), you can only hope you found a “good enough” local minimum — and much of modern deep learning research is about ensuring that “good enough” is actually very good.
The Catch: Neural networks are NOT convex. But understanding convexity helps you:
  1. Know when you are guaranteed to find the global optimum (linear models, SVMs)
  2. Design loss functions that are easier to optimize (convex losses + non-convex model = better than both non-convex)
  3. Understand why some algorithms converge faster and with what guarantees
  4. Recognize when adding regularization makes your problem “more convex” (L2 regularization adds a convex term)
Estimated Time: 3-4 hours
Difficulty: Intermediate
Prerequisites: Gradient Descent, Optimization modules
What You’ll Learn: When optimization is easy, and how to leverage it

​
What Is Convexity?

​
Convex Sets

A set CC is convex if the line segment between any two points in CC lies entirely in CC. 
import numpy as np
import matplotlib.pyplot as plt
from matplotlib.patches import Polygon, Circle

fig, axes = plt.subplots(1, 3, figsize=(15, 5))

# Convex set: Circle
theta = np.linspace(0, 2*np.pi, 100)
circle = plt.Circle((0, 0), 1, fill=True, alpha=0.3, color='blue')
axes[0].add_patch(circle)
axes[0].plot([-.7, .5], [-.5, .7], 'r-', linewidth=2, label='Line segment inside')
axes[0].scatter([-.7, .5], [-.5, .7], c='red', s=100, zorder=5)
axes[0].set_xlim(-1.5, 1.5)
axes[0].set_ylim(-1.5, 1.5)
axes[0].set_title('Convex: Circle (Yes)')
axes[0].set_aspect('equal')
axes[0].legend()

# Convex set: Triangle
triangle = Polygon([[-1, -0.5], [1, -0.5], [0, 1]], alpha=0.3, color='blue')
axes[1].add_patch(triangle)
axes[1].plot([-.5, .3], [-.2, .5], 'r-', linewidth=2, label='Line segment inside')
axes[1].scatter([-.5, .3], [-.2, .5], c='red', s=100, zorder=5)
axes[1].set_xlim(-1.5, 1.5)
axes[1].set_ylim(-1, 1.5)
axes[1].set_title('Convex: Triangle (Yes)')
axes[1].set_aspect('equal')
axes[1].legend()

# Non-convex set: Crescent
t = np.linspace(0, 2*np.pi, 100)
x1 = np.cos(t)
y1 = np.sin(t)
x2 = 0.5 + 0.7*np.cos(t)
y2 = 0.7*np.sin(t)
axes[2].fill(x1, y1, alpha=0.3, color='blue')
axes[2].fill(x2, y2, color='white')
axes[2].plot([-.8, .2], [0, 0], 'r-', linewidth=2, label='Line segment OUTSIDE!')
axes[2].scatter([-.8, .2], [0, 0], c='red', s=100, zorder=5)
axes[2].set_xlim(-1.5, 1.5)
axes[2].set_ylim(-1.5, 1.5)
axes[2].set_title('Non-Convex: Crescent (No)')
axes[2].set_aspect('equal')
axes[2].legend()

plt.tight_layout()
plt.show()

​
Convex Functions

A function ff is convex if the line segment between any two points on the graph lies above or on the graph. Mathematically: For all x,yx, y and λ∈[0,1]\lambda \in [0, 1]: f(λx+(1−λ)y)≤λf(x)+(1−λ)f(y)f(\lambda x + (1-\lambda) y) \leq \lambda f(x) + (1-\lambda) f(y) 
# Visualize convex vs non-convex functions
x = np.linspace(-3, 3, 100)

fig, axes = plt.subplots(1, 3, figsize=(15, 5))

# Convex: Quadratic
y_quad = x**2
axes[0].plot(x, y_quad, 'b-', linewidth=2)
# Show the "line above" property
x1, x2 = -2, 1.5
y1, y2 = x1**2, x2**2
axes[0].plot([x1, x2], [y1, y2], 'r--', linewidth=2, label='Line segment')
axes[0].scatter([x1, x2], [y1, y2], c='red', s=100, zorder=5)
# Show a point in between
x_mid = 0.5 * x1 + 0.5 * x2
axes[0].scatter([x_mid], [x_mid**2], c='green', s=100, zorder=5, label='Function value')
axes[0].scatter([x_mid], [0.5*y1 + 0.5*y2], c='orange', s=100, zorder=5, label='Line value')
axes[0].set_title('Convex: f(x) = x^2 (Yes)')
axes[0].legend()
axes[0].grid(True, alpha=0.3)

# Convex: Exponential
y_exp = np.exp(x)
axes[1].plot(x, y_exp, 'b-', linewidth=2)
x1, x2 = -2, 1
y1, y2 = np.exp(x1), np.exp(x2)
axes[1].plot([x1, x2], [y1, y2], 'r--', linewidth=2)
axes[1].scatter([x1, x2], [y1, y2], c='red', s=100, zorder=5)
axes[1].set_title('Convex: f(x) = exp(x) (Yes)')
axes[1].grid(True, alpha=0.3)

# Non-convex: Sine
y_sin = np.sin(x)
axes[2].plot(x, y_sin, 'b-', linewidth=2)
x1, x2 = -2, 2
y1, y2 = np.sin(x1), np.sin(x2)
axes[2].plot([x1, x2], [y1, y2], 'r--', linewidth=2)
axes[2].scatter([x1, x2], [y1, y2], c='red', s=100, zorder=5)
axes[2].set_title('Non-Convex: f(x) = sin(x) (No)')
axes[2].grid(True, alpha=0.3)

plt.tight_layout()
plt.show()

​
Testing for Convexity

​
Second Derivative Test

For a single-variable function, convexity testing is straightforward: compute the second derivative and check its sign. If the second derivative is non-negative everywhere, the function is convex. This is the mathematical version of checking whether a surface always curves “upward” like a bowl. For twice-differentiable functions:
Function TypeConditionVisual Intuition
Convexf′′(x)≥0f''(x) \geq 0 everywhereAlways curves upward (bowl)
Strictly Convexf′′(x)>0f''(x) > 0 everywhereCurves upward with no flat regions
Concavef′′(x)≤0f''(x) \leq 0 everywhereAlways curves downward (hill)
def is_convex(f, f_double_prime, x_range):
    """Check if f is convex over x_range."""
    x = np.linspace(x_range[0], x_range[1], 1000)
    second_derivs = f_double_prime(x)
    
    return np.all(second_derivs >= -1e-10)  # Allow small numerical errors

# Test some functions
functions = [
    ("x²", lambda x: x**2, lambda x: 2*np.ones_like(x)),
    ("eˣ", lambda x: np.exp(x), lambda x: np.exp(x)),
    ("x³", lambda x: x**3, lambda x: 6*x),
    ("|x|", lambda x: np.abs(x), lambda x: np.zeros_like(x)),  # f''=0 except at 0
    ("sin(x)", lambda x: np.sin(x), lambda x: -np.sin(x)),
]

print("Convexity Check (on [-5, 5]):")
print("=" * 40)
for name, f, f_pp in functions:
    result = is_convex(f, f_pp, [-5, 5])
    print(f"{name:10} : {'Convex ✓' if result else 'Non-convex ✗'}")

​
Hessian Test (Multivariable)

For functions of multiple variables, check if the Hessian (matrix of second derivatives) is positive semi-definite. 
from scipy.optimize import minimize

def check_hessian_pd(H):
    """Check if matrix H is positive semi-definite."""
    eigenvalues = np.linalg.eigvals(H)
    return np.all(eigenvalues >= -1e-10)

# Example: f(x,y) = x² + y² + xy
# Hessian = [[2, 1], [1, 2]]
H = np.array([[2, 1], [1, 2]])

eigenvalues = np.linalg.eigvals(H)
print(f"Hessian eigenvalues: {eigenvalues}")
print(f"Is convex: {check_hessian_pd(H)}")

# Non-convex example: saddle point
# f(x,y) = x² - y²
# Hessian = [[2, 0], [0, -2]]
H_saddle = np.array([[2, 0], [0, -2]])
eigenvalues_saddle = np.linalg.eigvals(H_saddle)
print(f"\nSaddle Hessian eigenvalues: {eigenvalues_saddle}")
print(f"Is convex: {check_hessian_pd(H_saddle)}")

​
Why Convexity Matters

​
Theorem: Every Local Minimum Is Global

For convex functions, gradient descent is guaranteed to find the global minimum. 
# Demonstrate convergence to global minimum for convex function
def convex_function(x):
    return x[0]**2 + x[1]**2 + x[0]*x[1] + x[0] + 2*x[1]

def convex_gradient(x):
    return np.array([2*x[0] + x[1] + 1, 2*x[1] + x[0] + 2])

# Multiple random starting points
np.random.seed(42)
n_starts = 10
starting_points = np.random.randn(n_starts, 2) * 5

fig, axes = plt.subplots(1, 2, figsize=(14, 6))

# Plot contours
x = np.linspace(-5, 5, 100)
y = np.linspace(-5, 5, 100)
X, Y = np.meshgrid(x, y)
Z = X**2 + Y**2 + X*Y + X + 2*Y

axes[0].contour(X, Y, Z, levels=30)
axes[0].set_title('Convex Function: All Paths Lead to Same Minimum')
axes[0].set_xlabel('x')
axes[0].set_ylabel('y')

# Gradient descent from each starting point
all_endpoints = []
for i, start in enumerate(starting_points):
    path = [start.copy()]
    x = start.copy()
    lr = 0.1
    
    for _ in range(50):
        x = x - lr * convex_gradient(x)
        path.append(x.copy())
    
    path = np.array(path)
    axes[0].plot(path[:, 0], path[:, 1], 'o-', markersize=2, alpha=0.7)
    all_endpoints.append(path[-1])

all_endpoints = np.array(all_endpoints)
axes[0].scatter(all_endpoints[:, 0], all_endpoints[:, 1], c='red', s=100, zorder=10, label='Final points')
axes[0].legend()

# Show that all endpoints are the same
print("All endpoints converge to the same point:")
print(f"Mean: {all_endpoints.mean(axis=0)}")
print(f"Std:  {all_endpoints.std(axis=0)}")

# Non-convex comparison
def nonconvex_function(x):
    return np.sin(x[0]) + np.sin(x[1]) + 0.1*(x[0]**2 + x[1]**2)

def nonconvex_gradient(x):
    return np.array([np.cos(x[0]) + 0.2*x[0], np.cos(x[1]) + 0.2*x[1]])

# Plot non-convex
Z_nc = np.sin(X) + np.sin(Y) + 0.1*(X**2 + Y**2)
axes[1].contour(X, Y, Z_nc, levels=30)
axes[1].set_title('Non-Convex Function: Different Minima!')
axes[1].set_xlabel('x')
axes[1].set_ylabel('y')

all_endpoints_nc = []
for start in starting_points:
    path = [start.copy()]
    x = start.copy()
    lr = 0.1
    
    for _ in range(100):
        x = x - lr * nonconvex_gradient(x)
        path.append(x.copy())
    
    path = np.array(path)
    axes[1].plot(path[:, 0], path[:, 1], 'o-', markersize=2, alpha=0.7)
    all_endpoints_nc.append(path[-1])

all_endpoints_nc = np.array(all_endpoints_nc)
axes[1].scatter(all_endpoints_nc[:, 0], all_endpoints_nc[:, 1], c='red', s=100, zorder=10)

plt.tight_layout()
plt.show()

print("\nNon-convex endpoints (different!):")
print(all_endpoints_nc.round(3))

​
Common Convex Functions in ML

​
Loss Functions

LossFormulaConvexity
MSE(y−y^)2(y - \hat{y})^2Convex ✓
MAE∥y−y^∥\|y - \hat{y}\|Convex ✓
Cross-Entropy−ylog⁡(y^)-y\log(\hat{y})Convex ✓
Hingemax⁡(0,1−yy^)\max(0, 1-y\hat{y})Convex ✓
HuberCombinationConvex ✓

​
Regularization

RegularizerFormulaConvexity
L2 (Ridge)∑wi2\sum w_i^2Strictly Convex ✓
L1 (Lasso)∑∥wi∥\sum \|w_i\|Convex ✓
Elastic Netα∑∥wi∥+(1−α)∑wi2\alpha \sum \|w_i\| + (1-\alpha) \sum w_i^2Convex ✓
# Visualize common loss functions
x = np.linspace(-3, 3, 500)

fig, axes = plt.subplots(2, 3, figsize=(15, 10))

# MSE
axes[0, 0].plot(x, x**2, 'b-', linewidth=2)
axes[0, 0].set_title('MSE: (y - ŷ)²')
axes[0, 0].grid(True, alpha=0.3)

# MAE
axes[0, 1].plot(x, np.abs(x), 'b-', linewidth=2)
axes[0, 1].set_title('MAE: |y - ŷ|')
axes[0, 1].grid(True, alpha=0.3)

# Hinge loss
axes[0, 2].plot(x, np.maximum(0, 1-x), 'b-', linewidth=2)
axes[0, 2].set_title('Hinge: max(0, 1 - yŷ)')
axes[0, 2].grid(True, alpha=0.3)

# Cross entropy (for p ∈ (0,1))
p = np.linspace(0.01, 0.99, 500)
axes[1, 0].plot(p, -np.log(p), 'b-', linewidth=2, label='-log(p)')
axes[1, 0].plot(p, -np.log(1-p), 'r--', linewidth=2, label='-log(1-p)')
axes[1, 0].set_title('Cross-Entropy Components')
axes[1, 0].legend()
axes[1, 0].grid(True, alpha=0.3)

# Huber loss
delta = 1.0
huber = np.where(np.abs(x) <= delta, 0.5*x**2, delta*(np.abs(x) - 0.5*delta))
axes[1, 1].plot(x, huber, 'b-', linewidth=2)
axes[1, 1].plot(x, x**2, 'r--', alpha=0.5, label='MSE')
axes[1, 1].plot(x, np.abs(x), 'g--', alpha=0.5, label='MAE')
axes[1, 1].set_title('Huber Loss (δ=1)')
axes[1, 1].legend()
axes[1, 1].grid(True, alpha=0.3)

# L1 vs L2 regularization
w = np.linspace(-3, 3, 500)
axes[1, 2].plot(w, np.abs(w), 'b-', linewidth=2, label='L1 (Lasso)')
axes[1, 2].plot(w, w**2, 'r-', linewidth=2, label='L2 (Ridge)')
axes[1, 2].set_title('Regularization Penalties')
axes[1, 2].legend()
axes[1, 2].grid(True, alpha=0.3)

plt.tight_layout()
plt.show()

​
Linear Regression: A Convex Problem

Linear regression with MSE loss is convex: L(w)=∑i=1n(yi−wTxi)2L(w) = \sum_{i=1}^{n} (y_i - w^T x_i)^2 This is a quadratic function in ww, which is always convex! 
from mpl_toolkits.mplot3d import Axes3D

# 2D linear regression to visualize the loss surface
np.random.seed(42)
n = 50
X = np.random.randn(n, 2)
true_w = np.array([2.0, -1.0])
y = X @ true_w + np.random.randn(n) * 0.5

def mse_loss(w):
    return np.mean((y - X @ w)**2)

# Plot the loss surface
w0_range = np.linspace(-1, 5, 100)
w1_range = np.linspace(-4, 2, 100)
W0, W1 = np.meshgrid(w0_range, w1_range)

Z = np.zeros_like(W0)
for i in range(len(w0_range)):
    for j in range(len(w1_range)):
        Z[j, i] = mse_loss(np.array([w0_range[i], w1_range[j]]))

fig = plt.figure(figsize=(14, 6))

# 3D surface
ax1 = fig.add_subplot(1, 2, 1, projection='3d')
ax1.plot_surface(W0, W1, Z, cmap='viridis', alpha=0.8)
ax1.set_xlabel('w₀')
ax1.set_ylabel('w₁')
ax1.set_zlabel('MSE Loss')
ax1.set_title('MSE Loss Surface (Convex Bowl)')
ax1.scatter([true_w[0]], [true_w[1]], [mse_loss(true_w)], c='red', s=200, label='Optimum')

# Contour plot with gradient descent paths
ax2 = fig.add_subplot(1, 2, 2)
contour = ax2.contour(W0, W1, Z, levels=30, cmap='viridis')
ax2.scatter([true_w[0]], [true_w[1]], c='red', s=200, zorder=10, label='Optimum')

# Gradient descent
def mse_gradient(w):
    return -2/n * X.T @ (y - X @ w)

for _ in range(5):
    start = np.random.randn(2) * 2
    path = [start]
    w = start.copy()
    
    for _ in range(50):
        w = w - 0.1 * mse_gradient(w)
        path.append(w.copy())
    
    path = np.array(path)
    ax2.plot(path[:, 0], path[:, 1], 'o-', markersize=3, alpha=0.7)

ax2.set_xlabel('w₀')
ax2.set_ylabel('w₁')
ax2.set_title('All Paths Converge to Global Minimum')
ax2.legend()

plt.tight_layout()
plt.show()

print(f"True weights: {true_w}")
print(f"Found weights: {np.linalg.lstsq(X, y, rcond=None)[0].round(3)}")

​
Strong Convexity: Even Better Guarantees

A function is strongly convex with parameter μ\mu if: f(y)≥f(x)+∇f(x)T(y−x)+μ2∥y−x∥2f(y) \geq f(x) + \nabla f(x)^T(y-x) + \frac{\mu}{2}\|y-x\|^2 Why it matters: Strong convexity guarantees faster convergence!
PropertyConvexStrongly Convex
Unique minimum?MaybeYes!
Convergence rateO(1/t)O(1/t)O(e−μt)O(e^{-\mu t}) (exponential!)
Effect of L2 regularizationMakes strongly convexIncreases μ\mu
# Demonstrate faster convergence with strong convexity
def f_convex(x):
    return np.abs(x)  # Convex but not strongly convex

def f_strongly_convex(x, mu=1):
    return np.abs(x) + 0.5 * mu * x**2  # Strongly convex

# Subgradient method for non-smooth functions
def subgradient_descent(f, grad, x0, lr, n_iters):
    x = x0
    history = [x]
    for t in range(n_iters):
        step = lr / np.sqrt(t + 1)  # Decreasing step size
        x = x - step * grad(x)
        history.append(x)
    return np.array(history)

# Gradient/subgradient functions
def grad_convex(x):
    return np.sign(x)

def grad_strongly(x, mu=1):
    return np.sign(x) + mu * x

# Run optimization
n_iters = 100
x0 = 5.0

history_convex = subgradient_descent(f_convex, grad_convex, x0, 1.0, n_iters)
history_strong = subgradient_descent(f_strongly_convex, lambda x: grad_strongly(x, 0.5), x0, 1.0, n_iters)

# Compare convergence
fig, axes = plt.subplots(1, 2, figsize=(14, 5))

axes[0].plot(np.abs(history_convex), label='Convex (MAE)')
axes[0].plot(np.abs(history_strong), label='Strongly Convex (MAE + L2)')
axes[0].set_xlabel('Iteration')
axes[0].set_ylabel('|x|')
axes[0].set_title('Convergence Comparison')
axes[0].legend()
axes[0].grid(True, alpha=0.3)
axes[0].set_yscale('log')

# Function values
axes[1].plot([f_convex(x) for x in history_convex], label='Convex')
axes[1].plot([f_strongly_convex(x) for x in history_strong], label='Strongly Convex')
axes[1].set_xlabel('Iteration')
axes[1].set_ylabel('f(x)')
axes[1].set_title('Function Value Over Iterations')
axes[1].legend()
axes[1].grid(True, alpha=0.3)
axes[1].set_yscale('log')

plt.tight_layout()
plt.show()

​
Practice Exercises

Problem: Prove that log-loss (binary cross-entropy) is convex.L(p)=−[ylog⁡(p)+(1−y)log⁡(1−p)]L(p) = -[y \log(p) + (1-y)\log(1-p)]Hint: Compute the second derivative and show it’s non-negative.
Problem: Why does L1 regularization produce sparse solutions (many zeros) while L2 doesn’t?Hint: Think about the geometry of the constraint sets and where they intersect the loss contours.
Problem: The function f(x)=x4−3x2f(x) = x^4 - 3x^2 is non-convex. Add L2 regularization to make it convex. What’s the minimum regularization strength needed?Hint: The regularized function is f(x)+λx2f(x) + \lambda x^2. Find λ\lambda such that f′′(x)+2λ≥0f''(x) + 2\lambda \geq 0 for all xx.

​
Summary

ConceptWhat It MeansPractical Impact
Convex FunctionBowl-shaped, no local minimaGradient descent finds global optimum
Convex Set”Solid” without holesFeasible region for optimization
Strongly Convex”Very bowl-shaped”Faster convergence
L2 RegularizationMakes function more convexImproves optimization
Non-ConvexMultiple minimaNo global optimum guarantee
Key Takeaway: Convexity is your friend. When designing ML systems, prefer convex loss functions and regularization. When you must use non-convex models (neural networks), understand that you are trading optimization guarantees for model flexibility. Good initialization, learning rate schedules, and regularization help navigate non-convex landscapes.A senior engineer’s mental model: “Use the simplest model that works. If linear regression (convex) solves your problem, do not use a neural network. When you do need a neural network, make the optimization landscape as friendly as possible — convex losses, proper initialization, batch normalization, residual connections.”
Numerical Pitfall: Testing Convexity with EigenvaluesWhen checking positive-definiteness of a Hessian matrix computationally, be careful with floating-point comparisons. Due to rounding errors, a theoretically positive-definite matrix might have an eigenvalue like -1e-15. Always use a tolerance:
def is_positive_definite(H, tol=1e-10):
    """Check positive-definiteness with numerical tolerance."""
    eigenvalues = np.linalg.eigvalsh(H)  # Use eigvalsh for symmetric matrices
    return np.all(eigenvalues > -tol)
Note the use of eigvalsh instead of eigvals — it is both faster and more numerically stable for symmetric matrices (and the Hessian is always symmetric for twice-differentiable functions).

​
Interview Deep-Dive

Strong Answer:
  • This is one of the most important open questions in deep learning theory, and the honest answer is that we do not have a complete theoretical understanding. But we have strong empirical and theoretical insights.
  • First, the loss landscape of overparameterized neural networks (more parameters than training examples) is surprisingly benign. Choromanska et al. (2015) showed that for large networks, the loss values at different local minima are clustered close together — there are many local minima, but they are nearly as good as the global minimum. Getting stuck in a “bad” local minimum becomes increasingly rare as the network gets larger.
  • Second, saddle points are more common than local minima in high dimensions, and modern optimizers (SGD with noise, momentum, Adam) handle saddle points well. The gradient noise from mini-batch training naturally perturbs the optimizer away from saddle points.
  • Third, overparameterization creates a phenomenon where the loss surface has large flat regions at near-zero loss. With enough parameters, there are many weight configurations that fit the training data perfectly, and gradient descent can find one of them relatively easily. The challenge shifts from “finding a minimum” to “finding a minimum that generalizes” — which is a regularization question, not a convexity question.
  • Fourth, the architecture matters. Residual connections, normalization layers, and careful initialization all smooth the loss landscape. Li et al. (2018) visualized the loss surfaces of ResNets versus plain networks and showed that skip connections dramatically smoothen the landscape.
  • The practical takeaway: we trade convexity guarantees for representational power. A convex model (like logistic regression) is easy to optimize but limited in what it can learn. A neural network can learn arbitrarily complex functions but has no global optimality guarantee. In practice, the optimization works well enough, and the expressiveness gain far outweighs the theoretical risk.
Follow-up: You mentioned overparameterization helps optimization. Does this mean we should always use models that are as large as possible?Not without qualification. Overparameterization helps the optimization landscape, but it introduces a generalization risk. However, the “double descent” phenomenon (Belkin et al., 2019) showed something surprising: as you increase model size past the interpolation threshold, test error initially increases but then DECREASES again as you keep adding parameters. The explanation is that in the heavily overparameterized regime, gradient descent has an implicit bias toward simple (low-norm) solutions, which generalize well. This is the empirical foundation behind the scaling laws that drive modern LLM development — bigger models trained on more data consistently perform better, provided you also scale training data and compute appropriately.
Strong Answer:
  • Both L1 and L2 regularization add a convex penalty to the loss function, which helps with both optimization (makes the problem more convex) and generalization (reduces overfitting). But their geometric properties are fundamentally different.
  • L2 regularization adds lambda * ||w||^2. This is a smooth, strictly convex function. Its gradient is 2lambdaw, which pushes weights toward zero proportionally to their current value. Large weights get large pushes, small weights get small pushes. Weights shrink but never exactly reach zero.
  • L1 regularization adds lambda * ||w||_1 = lambda * sum(|w_i|). This is convex but NOT smooth — it has a kink at w_i = 0. The subgradient is lambda * sign(w_i), which pushes ALL weights toward zero with the same force, regardless of magnitude. Small weights are actively driven to exactly zero, producing sparsity.
  • Geometrically, L2’s constraint is a sphere, and loss contours typically touch it where no coordinates are exactly zero. L1’s constraint is a diamond with corners on the axes. The loss contours are much more likely to touch the diamond at a corner, which corresponds to one or more coordinates being exactly zero. In higher dimensions, the L1 diamond has even more corners relative to its surface area, making sparsity increasingly likely.
  • Practical implications: L1 is used when you want automatic feature selection (LASSO identifies important features by zeroing out irrelevant ones). L2 is used when you want to keep all features but prevent any single feature from dominating. Elastic Net combines both: alpha * L1 + (1-alpha) * L2, getting sparsity plus the grouping effect for correlated features.
Follow-up: In neural networks, we typically use L2 regularization (weight decay) rather than L1. Why?Several reasons. First, the non-differentiability of L1 at zero interacts poorly with gradient-based optimizers. The gradient of |w| is discontinuous at w=0, which can cause oscillation rather than clean convergence. Proximal gradient methods handle this properly, but standard SGD and Adam do not. Second, sparsity at the individual weight level is less useful in neural networks than in linear models. In linear regression, a zero weight means a feature is irrelevant. In a neural network, individual weights lack such clean interpretations. Third, for network compression, structured sparsity (zeroing entire neurons or channels) is more useful than unstructured weight-level sparsity, and requires different techniques like magnitude pruning or group LASSO.
Strong Answer:
  • L2 regularization adds lambda * ||w||^2 to the loss. The Hessian of this term is 2lambdaI (a scaled identity matrix). So the Hessian of the regularized loss is H_original + 2lambdaI. This shifts ALL eigenvalues upward by 2*lambda.
  • If the original loss has minimum Hessian eigenvalue mu_min (which could be zero or negative), the regularized loss has minimum eigenvalue mu_min + 2*lambda. If lambda is large enough, all eigenvalues become positive, making the loss strongly convex.
  • Strong convexity with parameter mu = 2lambda gives exponential convergence: O(exp(-mut)) instead of O(1/t) for merely convex functions. The condition number (ratio of largest to smallest eigenvalue) also improves because the denominator increases by 2*lambda.
  • For non-convex neural networks, L2 regularization does not make the landscape convex (the non-convexity from activations dominates). But it flattens the landscape by penalizing large weights, eliminating sharp minima and favoring flatter solutions. It also prevents weight explosion for numerical stability.
  • An important subtlety: in Adam, L2 regularization and weight decay are NOT equivalent. The L2 gradient (2lambdaw) gets divided by sqrt(v) in Adam, so parameters with large historical gradients receive less effective regularization. AdamW applies weight decay directly to the weights, preserving the intended regularization strength. This distinction matters significantly for transformer training.
Follow-up: If strong convexity guarantees a unique global minimum, does very large L2 regularization always improve optimization even if it hurts accuracy?Yes, from a pure optimization standpoint, large lambda makes the problem trivially easy — the landscape becomes a smooth bowl with a single minimum near w=0. Gradient descent converges in very few steps. But that minimum heavily ignores the training data. The model outputs near-constant predictions. So the trade-off is clear: small lambda gives a complex landscape but data-fitting solutions; large lambda gives an easy landscape but underfitting solutions. The sweet spot is lambda that makes the landscape “convex enough” for reliable convergence while preserving model expressiveness. Typical weight decay values for neural networks are 1e-4 to 1e-2 — small enough to learn from data, large enough to prevent weight explosion.
Strong Answer:
  • Logistic regression with cross-entropy loss is a convex optimization problem. The loss function is strictly convex (with L2 regularization), meaning gradient descent is guaranteed to find the unique global minimum. No local minima, no saddle points, no sensitivity to initialization. You can solve it with off-the-shelf solvers (L-BFGS, coordinate descent) in seconds. The solution is deterministic and reproducible.
  • A neural network’s loss is non-convex. Different random initializations lead to different solutions. Training involves hyperparameter tuning (learning rate, architecture, batch size), takes longer, and requires more compute. There is no guarantee of finding the globally optimal solution.
  • For 50 features and 10,000 samples, I would start with logistic regression. At this scale, the convex optimizer will find the provably optimal linear decision boundary in under a second. If the accuracy is sufficient for the business requirement, stop here. You get interpretability (feature importances from coefficients), reproducibility, fast inference, and easy deployment.
  • I would switch to a neural network only if: (1) the logistic regression accuracy is insufficient, suggesting the decision boundary is nonlinear; (2) the features have complex interactions that a linear model cannot capture; or (3) domain knowledge suggests the data has hierarchical structure that benefits from learned representations.
  • The key insight for the interview: choosing the right model is not about picking the most powerful one — it is about matching the model’s complexity to the problem’s complexity. A convex model that solves the problem is strictly better than a non-convex one, because you get the same accuracy with stronger guarantees, faster training, easier debugging, and simpler deployment.
Follow-up: At what dataset size or feature complexity does the balance typically shift from convex models to neural networks?There is no universal threshold, but heuristics help. For tabular data with engineered features, gradient-boosted trees (XGBoost, LightGBM) often outperform neural networks even at millions of samples — and while tree ensembles are not convex, they have well-understood optimization. Neural networks start winning when the data is unstructured (images, text, audio) where learned representations are essential, or when the dataset exceeds roughly 100K-1M samples and the features have complex nonlinear interactions that handcrafted features cannot capture. The recent “tabular data benchmarks” from researchers at Meta and elsewhere consistently show that for tabular data below ~100K rows with fewer than ~100 features, properly tuned gradient boosting matches or beats neural networks. The neural network advantage emerges for very large datasets, multi-modal data, or when transfer learning from pretrained models is possible.