请求讲解AdaGrad与AdaDelta算法的数学原理及学习资源

Hey there! Since you already have a solid grasp of vanilla gradient descent (GD), let's break down AdaGrad and AdaDelta step by step—starting with why they were created to fix vanilla GD's limitations, then diving into the math, and even showing how you can adapt your existing GD code to implement them.

Vanilla GD uses a single global learning rate η for all parameters, which works okay but isn't ideal: some features (parameters) might need larger update steps, while others need smaller ones. AdaGrad solves this by giving each parameter its own adaptive learning rate based on its historical gradient activity.

The Math Behind AdaGrad #

Let's walk through the update rule step by step:

1. Initialize a cumulative gradient tracker: Start with G_t = 0 (a vector of zeros matching your parameter shape). This will store the sum of squared gradients over all previous steps.
2. Compute current gradient: For step t, calculate the gradient of your loss function with respect to parameters: g_t = ∇J(θ_t)
3. Update the cumulative tracker: Add the squared current gradient to G_t (using element-wise multiplication, denoted ⊙):
   G_t = G_{t-1} + g_t ⊙ g_t
4. Update parameters: Adjust each parameter using a learning rate scaled by the square root of its cumulative squared gradient (plus a tiny ε to avoid division by zero, usually 1e-8):
   θ_{t+1} = θ_t - (η / √(G_t + ε)) ⊙ g_t

Key Behavior #

• Parameters that get large, frequent gradients (e.g., common features in sparse data) will have a large G_t, which shrinks their learning rate over time—preventing overshooting.
• Parameters with rare, small gradients (e.g., rare words in NLP) keep a larger effective learning rate, helping them converge faster.
• Downside: Since G_t never stops growing, the effective learning rate can shrink to near zero over long training runs, halting progress.

AdaDelta is a direct improvement on AdaGrad that fixes the "vanishing learning rate" problem. Instead of accumulating all historical gradients, it uses an exponential moving average (EMA) to only keep track of recent gradient activity. It also eliminates the need to manually set a learning rate entirely.

The Math Behind AdaDelta #

We'll track two EMAs (both initialized to zero vectors):

• E[g²]_t: EMA of squared gradients
• E[Δθ²]_t: EMA of squared parameter updates

Here's the step-by-step update:

1. Compute current gradient: g_t = ∇J(θ_t)
2. Update gradient EMA: Use a decay coefficient ρ (typically 0.9) to weight older gradients less:
   E[g²]_t = ρ * E[g²]_{t-1} + (1-ρ) * g_t ⊙ g_t
3. Calculate RMS terms: RMS stands for "root mean square"—we use these to normalize the update:
   RMS[g]_t = √(E[g²]_t + ε)
RMS[Δθ]_{t-1} = √(E[Δθ²]_{t-1} + ε) (for the first step, use η if E[Δθ²]_{t-1} is zero)
4. Compute parameter update: Scale the gradient by the ratio of past update RMS to current gradient RMS:
   Δθ_t = - (RMS[Δθ]_{t-1} / RMS[g]_t) ⊙ g_t
5. Update parameters: θ_{t+1} = θ_t + Δθ_t
6. Update update EMA: Track the squared updates for the next iteration:
   E[Δθ²]_t = ρ * E[Δθ²]_{t-1} + (1-ρ) * Δθ_t ⊙ Δθ_t

Key Behavior #

• By using EMA, we only focus on recent gradients, so the learning rate doesn't keep shrinking indefinitely.
• No need to tune a global learning rate—AdaDelta adapts it automatically based on past update behavior.
• Works well for long training runs and a wide range of tasks.

Quick Code Adaptations (Pseudocode) #

Since you already have vanilla GD code, here's how to modify it for AdaGrad and AdaDelta (using NumPy-like syntax):

Vanilla GD (Your Existing Code) #

def vanilla_gd(theta, grad_fn, eta, num_steps):
    for _ in range(num_steps):
        g = grad_fn(theta)
        theta = theta - eta * g
    return theta

AdaGrad Adaptation #

def adagrad(theta, grad_fn, eta, num_steps, eps=1e-8):
    G = np.zeros_like(theta)  # Initialize cumulative squared gradients
    for _ in range(num_steps):
        g = grad_fn(theta)
        G += g * g  # Element-wise square and accumulate
        theta = theta - (eta / np.sqrt(G + eps)) * g
    return theta

AdaDelta Adaptation #

def adadelta(theta, grad_fn, rho=0.9, num_steps, eps=1e-8):
    E_g_sq = np.zeros_like(theta)  # EMA of gradient squares
    E_delta_theta_sq = np.zeros_like(theta)  # EMA of update squares
    for _ in range(num_steps):
        g = grad_fn(theta)
        # Update gradient EMA
        E_g_sq = rho * E_g_sq + (1 - rho) * g * g
        # Compute RMS terms
        rms_g = np.sqrt(E_g_sq + eps)
        rms_delta_theta = np.sqrt(E_delta_theta_sq + eps)
        # Compute update
        delta_theta = - (rms_delta_theta / rms_g) * g
        theta += delta_theta
        # Update update EMA
        E_delta_theta_sq = rho * E_delta_theta_sq + (1 - rho) * delta_theta * delta_theta
    return theta

Quick Recap #

• AdaGrad: Great for sparse datasets, but avoid long training runs due to vanishing learning rates.
• AdaDelta: Versatile, fixes AdaGrad's flaws, no manual learning rate tuning—ideal for most tasks.

内容的提问来源于stack exchange，提问作者Malay Hazarika