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 function; additionally, 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

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}$: Outer product of all previous subgradients, given by $\sum _{\tau =1}^{t}g_{\tau }g_{\tau }^{\top }$