Optimization Theory: Gradient Descent and Beyond

Module: Machine Learning | Difficulty: Advanced

Gradient Descent

Convergence Rate (L-smooth, -strongly convex)

Condition Number

Rate:

Nesterov Momentum

Adam

import numpy as np

class Adam:
    def __init__(self, lr=0.001, beta1=0.9, beta2=0.999, eps=1e-8):
        self.lr = lr; self.beta1 = beta1; self.beta2 = beta2; self.eps = eps
    def update(self, params, grads, t):
        for p, g in zip(params, grads):
            if not hasattr(self, 'm'):
                self.m = [np.zeros_like(p) for p in params]
                self.v = [np.zeros_like(p) for p in params]
            self.m[t] = self.beta1*self.m[t] + (1-self.beta1)*g
            self.v[t] = self.beta2*self.v[t] + (1-self.beta2)*g**2
            m_hat = self.m[t] / (1-self.beta1**(t+1))
            v_hat = self.v[t] / (1-self.beta2**(t+1))
            p -= self.lr * m_hat / (np.sqrt(v_hat) + self.eps)

| Optimizer | Convergence | Memory | Adaptivity | |-----------|-------------|--------|------------| | GD | | Low | No | | Momentum | | Low | No | | Adam | | Medium | Yes | | L-BFGS | Superlinear | High | No |

Research Insight: Adam can diverge on ill-conditioned problems. AMSGrad and AdamW fix this by using the maximum of past gradients or decoupling weight decay from the adaptive learning rate.