AdaGrad

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. 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.

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

$f(x)$: Stochastic objective function with parameters $x$.

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

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

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

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

Standard Sub-gradient Update

Standard sub-gradient algorithms update parameters $x$ according to the following rule:

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

where $\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:

$${\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}}$$

AdaGrad Update

The general AdaGrad update rule is given by:

$$x_{t+1}=x_{t}-\eta G_{t}^{-1/2}g_{t}$$

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

$$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 $\epsilon$ is added to each diagonal element in $G_{t}$ to avoid singularity problems, the resulting update rule is given by:

$$x_{t+1}=x_{t}-\eta {\text{diag}}(\epsilon I+G_{t})^{-1/2}g_{t}$$

where $I$ denotes the identity matrix. An expanded form of the previous update is presented below,

$${\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 $\odot$ denotes the Hadamard product between matrices of the same dimension, and $G_{t}^{(j,j)}$ is the $j$ element in the $G_{t}$ diagonal. From the last expression, it is clear that the update rule for AdaGrad adapts the step-size for each parameter $j$ accoding to ${\textstyle \eta (\epsilon +G_{t}^{(j,j)})^{-1/2}}$, while standard sub-gradient methods have fixed step-size $\eta$ for every parameter.

Adaptative Learning Rate Effect

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

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

which is similar to the definition of matrix $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 $G_{t}$.

Regret Bounds

AdaGrad has strong convergence guarantees and regret bound proven in the original paper. It has a regret bound of order $O({\sqrt {T}})$, which leads to the convergence rate of the regret with order $O(1/{\sqrt {T}})$, and the guarantee that it converges ($\lim _{T\to \infty }R(T)/T=0$).