AdaGrad: Adapting Learning Rates per Parameter

Stochastic Gradient Descent (SGD) and its variants like Momentum typically use a single learning rate to govern the update step for all parameters in a neural network. While techniques like learning rate scheduling can adjust this global rate over time, they don't account for the fact that different parameters might require different update magnitudes. Consider a scenario with sparse features: some parameters associated with rare features might only receive informative gradients occasionally, while parameters for frequent features receive updates constantly. A uniform learning rate might be too small for the infrequent parameters to learn effectively or too large for the frequent ones, causing instability.

The AdaGrad (Adaptive Gradient Algorithm) optimizer addresses this by maintaining a per-parameter learning rate that adapts based on the history of gradients observed for that parameter. The intuition is straightforward: parameters that have experienced large gradients frequently should have their learning rate reduced to prevent overshooting, while parameters associated with infrequent updates (and potentially smaller gradients historically) should maintain a larger learning rate to facilitate learning.

The AdaGrad Mechanism

AdaGrad achieves this adaptation by accumulating the square of the gradients for each parameter over all previous time steps. Let $g_{t,i}$ be the gradient of the objective function with respect to parameter $\theta_i$ at time step $t$. AdaGrad maintains a state variable, let's call it $G_{t,i}$, for each parameter $\theta_i$, which is the sum of the squares of the gradients with respect to $\theta_i$ up to time step $t$.

The update rule for $G_{t,i}$ is:

$$G_{t,i} = G_{t-1,i} + g_{t,i}^2$$

Here, $G_{0,i}$ is typically initialized to zero. This value, $G_{t,i}$, represents the historical gradient information accumulated for parameter $\theta_i$.

The Parameter Update Rule

When updating the actual parameter $\theta_i$, AdaGrad modifies the standard gradient descent update by dividing the global learning rate $\eta$ by the square root of this accumulated sum $G_{t,i}$. A small constant $\epsilon$ (epsilon, e.g., $10^{-8}$) is added to the denominator for numerical stability, preventing division by zero, especially during the initial steps when $G_{t,i}$ might be zero.

The parameter update for $\theta_i$ at time step $t$ is:

$$\theta_{t+1, i} = \theta_{t, i} - \frac{\eta}{\sqrt{G_{t,i} + \epsilon}} g_{t,i}$$

Let's break this down:

1. $g_{t,i}$: The current gradient for parameter $\theta_i$.
2. $\eta$: A global learning rate, similar to the one used in SGD.
3. $G_{t,i}$: The accumulated sum of squared gradients for parameter $\theta_i$ up to the current step.
4. $\epsilon$: A small smoothing term to prevent division by zero.

Notice how the effective learning rate for each parameter $\theta_i$, which is $\frac{\eta}{\sqrt{G_{t,i} + \epsilon}}$, changes dynamically. If a parameter consistently receives large gradients, $G_{t,i}$ will grow quickly, causing the effective learning rate for that parameter to decrease. Conversely, if a parameter receives small or infrequent gradients, $G_{t,i}$ will grow slowly, and the effective learning rate will remain relatively high.

Vectorized Form

In practice, these operations are performed element-wise on vectors and matrices. If $\theta_t$ represents the vector of all parameters at time step $t$, $g_t$ is the gradient vector, and $G_t$ is the vector accumulating the element-wise squares of gradients, the update rules are:

$$G_t = G_{t-1} + g_t \odot g_t$$ $$\theta_{t+1} = \theta_t - \frac{\eta}{\sqrt{G_t + \epsilon}} \odot g_t$$

where $\odot$ denotes element-wise multiplication, and the square root and addition of $\epsilon$ are also applied element-wise.

Benefits of AdaGrad

• Automatic Learning Rate Adaptation: AdaGrad effectively tunes the learning rate for each parameter individually, reducing the need for extensive manual tuning of the global learning rate $\eta$.
• Suitable for Sparse Data: It performs well in settings with sparse gradients, such as natural language processing or recommendation systems where certain features (like words or item IDs) appear infrequently. These infrequent features get larger updates compared to frequent ones.

Adaptive Learning Rate Insights

While innovative, AdaGrad has a significant property to keep in mind: the accumulated sum of squared gradients $G_t$ only grows over time. Because $G_t$ appears in the denominator, the effective learning rate for every parameter will monotonically decrease throughout training. In some cases, this decay can become too aggressive, causing the learning rate to shrink to near zero, effectively halting learning prematurely. This limitation motivated the development of subsequent adaptive algorithms like RMSprop and Adam, which we will explore next.