Author: Daniel Villarraga (SYSEN 6800 Fall 2021)

## Introduction

AdaGrad is a family of sub-gradient algorithms for stochastic optimization. The algorithms belonging to that family are similar to second-order stochastic gradient descend with an approximation for the Hessian of the optimized function. AdaGrad's name comes from Adaptative Gradient. Intuitively, it adapts the learning rate for each feature depending on the estimated geometry of the problem; particularly, it tends to assign higher learning rates to infrequent features, which ensures that the parameter updates rely less on frequency and more on relevance.

AdaGrad was introduced by Duchi et al.[1] in a highly cited paper published in the Journal of machine learning research in 2011. It is arguably one of the most popular algorithms for machine learning (particularly for training deep neural networks) and it influenced the development of the Adam algorithm[2].

## Theory

The objective of AdaGrad is to minimize the expected value of a stochastic objective function, with respect to a set of parameters, given a sequence of realizations of the function. As with other sub-gradient-based methods, it achieves so by updating the parameters in the opposite direction of the sub-gradients. While standard sub-gradient methods use update rules with step-sizes that ignore the information from the past observations, AdaGrad adapts the learning rate for each parameter individually using the sequence of gradient estimates.

### Definitions

${\displaystyle f(x)}$: Stochastic objective function with parameters ${\displaystyle x}$.

${\displaystyle f_{t}(x)}$: Realization of stochastic objective at time step ${\displaystyle t}$. For simplicity ${\displaystyle f_{t}}$.

${\displaystyle g_{t}(x)}$: The gradient of ${\displaystyle f_{t}(x)}$ with respect to ${\displaystyle x}$, formally ${\displaystyle \nabla _{x}f_{t}(x)}$. For simplicity, ${\displaystyle g_{t}}$.

${\displaystyle x_{t}}$: Parameters at time step ${\displaystyle t}$.

${\displaystyle G_{t}}$: The outer product of all previous subgradients, given by ${\textstyle \sum _{\tau =1}^{t}g_{\tau }g_{\tau }^{\top }}$

Standard sub-gradient algorithms update parameters ${\displaystyle x}$ according to the following rule:

${\displaystyle x_{t+1}=x_{t}-\eta g_{t}}$
where ${\displaystyle \eta }$ denotes the step-size often refered as learning rate or step-size. Expanding each term on the previous equation, the vector of parameters is updated as follows:

${\displaystyle {\begin{bmatrix}x_{t+1}^{(2)}\\x_{t+1}^{(2)}\\\vdots \\x_{t+1}^{(m)}\end{bmatrix}}={\begin{bmatrix}x_{t}^{(2)}\\x_{t}^{(2)}\\\vdots \\x_{t}^{(m)}\end{bmatrix}}-\eta {\begin{bmatrix}g_{t}^{(2)}\\g_{t}^{(2)}\\\vdots \\g_{t}^{(m)}\end{bmatrix}}}$

${\displaystyle x_{t+1}=x_{t}-\eta G_{t}^{-1/2}g_{t}}$
where ${\displaystyle G_{t}^{-1/2}}$ is the inverse of the square root of ${\displaystyle G_{t}}$. A simplified version of the update rule takes the diagonal elements of ${\displaystyle G_{t}}$ instead of the whole matrix:

${\displaystyle x_{t+1}=x_{t}-\eta {\text{diag}}(G_{t})^{-1/2}g_{t}}$
which can be computed in linear time. In practice, a small quantity ${\displaystyle \epsilon }$ is added to each diagonal element in ${\displaystyle G_{t}}$ to avoid singularity problems, the resulting update rule is given by:

${\displaystyle x_{t+1}=x_{t}-\eta {\text{diag}}(\epsilon I+G_{t})^{-1/2}g_{t}}$
where ${\displaystyle I}$ denotes the identity matrix. An expanded form of the previous update is presented below,

${\displaystyle {\begin{bmatrix}x_{t+1}^{(2)}\\x_{t+1}^{(2)}\\\vdots \\x_{t+1}^{(m)}\end{bmatrix}}={\begin{bmatrix}x_{t}^{(2)}\\x_{t}^{(2)}\\\vdots \\x_{t}^{(m)}\end{bmatrix}}-{\begin{bmatrix}\eta {\frac {1}{\sqrt {\epsilon +G_{t}^{(1,1)}}}}\\\eta {\frac {1}{\sqrt {\epsilon +G_{t}^{(2,2)}}}}\\\vdots \\\eta {\frac {1}{\sqrt {\epsilon +G_{t}^{(m,m)}}}}\end{bmatrix}}\odot {\begin{bmatrix}g_{t}^{(2)}\\g_{t}^{(2)}\\\vdots \\g_{t}^{(m)}\end{bmatrix}}}$
where the operator ${\displaystyle \odot }$ denotes the Hadamard product between matrices of the same dimension, and ${\displaystyle G_{t}^{(j,j)}}$ is the ${\displaystyle j}$ element in the ${\displaystyle G_{t}}$ diagonal. From the last expression, it is clear that the update rule for AdaGrad adapts the step-size for each parameter ${\displaystyle j}$ accoding to ${\textstyle \eta (\epsilon +G_{t}^{(j,j)})^{-1/2}}$, while standard sub-gradient methods have fixed step-size ${\displaystyle \eta }$ for every parameter.

An estimate for the uncentered second moment of the objective function's gradient is given by the following expression:

${\displaystyle v={\frac {1}{t}}\sum _{\tau =1}^{t}g_{\tau }g_{\tau }^{\top }}$

which is similar to the definition of matrix ${\displaystyle G_{t}}$, used in AdaGrad's update rule. Noting that, AdaGrad adapts the learning rate for each parameter proportionally to the inverse of the gradient's variance for every parameter. This leads to the main advantages of AdaGrad:

1. Parameters associated with low-frequency features tend to have larger learning rates than parameters associated with high-frequency features.
2. Step-sizes in directions with high gradient variance are lower than the step-sizes in directions with low gradient variance. Geometrically, the step-sizes tend to decrease proportionally to the curvature of the stochastic objective function.

which favor the convergence rate of the algorithm.

### Algorithm

The general version of the AdaGrad algorithm is presented in the pseudocode below. The update step within the for loop can be modified with the version that uses the diagonal of ${\displaystyle G_{t}}$.

### Variants

One main disadvantage of AdaGrad is that it can be sensitive to the initial conditions of the parameters; for instance, if the initial gradients are large, the learning rates will be low for the remaining training. Additionally, the unweighted accumulation of gradients in ${\displaystyle G_{t}}$ happens from the beginning of training, so after some training steps, the learning rate could approach zero without arriving at good local optima [3]. Therefore, even with adaptative learning rates for each parameter, AdaGrad can be sensitive to the choice of global learning rate ${\displaystyle \eta }$. Some variants of AdaGrad have been proposed in the literature [3] [4] to overcome this and other problems, arguably the most popular one is AdaDelta.

AdaDelta is an algorithm based on AdaGrad that tackles the disadvantages mentioned before. Instead of accummulating the gradient in ${\displaystyle G_{t}}$ over all time from ${\displaystyle \tau =1}$ to ${\displaystyle \tau =t}$, AdaDelta takes an exponential weighted average of the following form:

${\displaystyle G_{t}=\rho G_{t-1}+(1-\rho )g_{t}g_{t}^{\top }}$

where ${\displaystyle \rho }$ is an hyperparameter, known as the decay rate, that controls the importance given to past observations of the squared gradient. Therefore, in contrast with AdaGrad, with AdaDelta the increase on ${\displaystyle G_{t}}$ is under control. Typicall choices for the decay rate ${\displaystyle \rho }$ are 0.95 or 0.90, which are the default choices for the AdaDelta optimizer in TensorFlow[5] and PyTorch[6], respectively.

Additionally, in AdaDelta the squared updates are accumulated with a running average with parameter ${\displaystyle \rho }$[3]:

${\displaystyle E[\Delta x^{2}]_{t}=\rho E[\Delta x^{2}]_{t-1}+(1-\rho )\Delta x_{t}^{2}}$

where,

${\displaystyle \Delta x_{t}=-({\sqrt {\Delta x_{t-1}+\epsilon }})G_{t}^{-1/2}g_{t}}$

${\displaystyle \Delta x_{t+1}=x_{t}+\Delta x_{t}}$

#### RMSprop

RMSprop is identical to AdaDelta without the running average for the parameter updates. Therefore, the update rule for this algorithm is the same as AdaGrad with ${\displaystyle G_{t}}$ calculated as done for AdaDelta (${\displaystyle G_{t}=\rho G_{t-1}+(1-\rho )g_{t}g_{t}^{\top }}$)[7].

### Regret Bound

The regret is defined as:

${\displaystyle R(t)=\sum _{t=1}^{T}f_{t}(x_{t})-\sum _{t=1}^{t}f_{t}(x^{*})}$

where ${\displaystyle x^{*}}$is the set of optimal parameters. AdaGrad has a regret bound of order ${\displaystyle O({\sqrt {T}})}$, which leads to the convergence rate of order ${\displaystyle O(1/{\sqrt {T}})}$, and the convergence guarantee (${\textstyle \lim _{T\to \infty }R(T)/T=0}$). The detailed proof and assumptions for this bound can be found in the original journal paper[1]. However, with some modifications to the original AdaGrad algorithm, SC-AdaGrad[4] shows a logarithmic regret bound (${\displaystyle O(\ln T)}$).

Considering the dimension ${\displaystyle d}$ of the gradient vectors, AdaGrad has a regret bound of order ${\displaystyle O({\sqrt {dT}})}$. Nevertheless, for the special case when gradient vectors are sparse, AdaGrad has a regret of an order ${\displaystyle O(\ln d{\sqrt {T}})}$[1]. Therefore, when gradient vectors are sparse, AdaGrad's regret bound can be exponentially better than SGD (which has a regret bound equal to ${\displaystyle O({\sqrt {dT}})}$ in that setting).

### Comparison with Other Gradient-based Methods

AdaGrad is an improved version of regular SGD; it includes second-order information in the parameter updates and provides adaptative learning rates for each parameter. However, it doesn't incorporate momentum, which could improve convergence rates. An algorithm closely related to AdaGrad that incorporates momentum is Adam.

SGD's update rule is fairly simple:

${\displaystyle x_{t+1}=x_{t}-\eta g_{t}}$

so, in comparison with AdaGrad, SGD doesn't have an independent learning rate for each parameter and doesn't include second-order information from the accumulation of square gradients in ${\displaystyle G_{t}}$

Adam includes estimates of the gradient's first and second uncentered moments in its update rule. The estimate for the first moment is a bias-corrected running average of the gradient, and the one for the second moment is equivalent to the one in AdaGrad. Therefore, for a particular set of hyperparameters, Adam is equivalent to AdaGrad[2].

## Numerical Example

To illustrate how the parameter updates work in AdaGrad take the following numerical example. The dataset consists of random generated obsevations ${\displaystyle x,y}$ that follow the linear relationship:

${\displaystyle y=20\cdot x+\epsilon }$
where ${\displaystyle \epsilon }$ is random noise. The first 5 obsevations are shown in the table below.

${\displaystyle x}$ ${\displaystyle y}$
0.39 9.83
0.10 2.27
0.30 5.10
0.35 6.32
0.85 15.50

The cost function is defined as ${\textstyle f(a,b)={\frac {1}{N}}\sum _{i=1}^{n}([a+b\cdot x_{i}]-y_{i})^{2}}$. And an observation of the cost function at time step ${\displaystyle t}$ is given by ${\displaystyle f_{t}(a,b)=([a+b\cdot x_{t}]-y_{t})^{2}}$, where ${\displaystyle x_{t},y_{t}}$ are sampled from the obsevations. Finally, the subgradient is determined by:

${\displaystyle g_{t}={\begin{bmatrix}2([a_{t}+b_{t}\cdot x_{t}]-y_{t})\\2x_{t}([a_{t}+b_{t}\cdot x_{t}]-y_{t})\end{bmatrix}}}$

Take a learning rate ${\displaystyle \eta =5}$, initial parameters ${\displaystyle a_{1},b_{1}=0}$, and ${\displaystyle x_{1}=0.39,y_{1}=9.84}$. For the first iteration of AdaGrad the subgradient is equal to:

${\displaystyle g_{1}={\begin{bmatrix}2([0+0\cdot 0.39]-9.84)\\2\cdot 0.39([0+0\cdot 0.39]-9.84)\end{bmatrix}}={\begin{bmatrix}-19.68\\-7.68\end{bmatrix}}}$

and ${\displaystyle G_{t}}$ is:

${\displaystyle G_{1}=\sum _{\tau =1}^{1}g_{1}g_{1}^{\top }={\begin{bmatrix}-19.68\\-7.68\end{bmatrix}}{\begin{bmatrix}-19.68&-7.68\end{bmatrix}}={\begin{bmatrix}387.30&151.14\\151.14&58.98\end{bmatrix}}}$
So the first parameter's update is calculated as follows:

${\displaystyle {\begin{bmatrix}a_{2}\\b_{2}\end{bmatrix}}={\begin{bmatrix}0\\0\end{bmatrix}}-{\begin{bmatrix}5\cdot {\frac {1}{\sqrt {387.30}}}\\5\cdot {\frac {1}{\sqrt {58.98}}}\end{bmatrix}}\odot {\begin{bmatrix}-19.68\\-7.68\end{bmatrix}}={\begin{bmatrix}5\\5\end{bmatrix}}}$
This process is repetated until convergence or for a fixed number of iterations ${\displaystyle T}$. An example AdaGrad update trajectory for this example is presented in Figure 1. Note that in Figure 1, the algorithm converges to a region close to ${\displaystyle (a,b)=(0,20)}$, which are the set of parameters that originated the obsevations in this example.

## Applications

The AdaGrad family of algorithms is typically used in machine learning applications. Mainly, it is a good choice for deep learning models with sparse gradients[1], like recurrent neural networks and transformer models for natural language processing. However, one can apply it to any optimization problem with a differentiable cost function.

### Natural Language Processing

Natural language processing (NLP) is an area of research concerned with the interactions between computers and human language. Multiple tasks fall within the giant umbrella of NLP, such as sentiment analysis, automatic summarization, machine translation, and text completion. Deep learning models, like recurrent neural networks and transformer models[8], are the usual choices for these tasks, and one common issue faced when training is sparse gradients. Therefore, AdaGrad and Adam work better than standard SGD for that settings.