Why sparse features should have bigger learning rates associated? And how Adagrad achieves this?
Intuition behind learning rates
With Adagrad, parameters that model the influence of the features in our problem tend to be updated at the same rhythm, something that is accomplished by what you explained in your question $\rightarrow$ the parameters are updated with different learning rates/ steps which may depend on how frequent (or sparse) the features are.
But why the parameters that we are learning should be updated with different learning rates? $\rightarrow$ For example, if our cost function was $f(x,y,z) = 20x^2+y^2+z^2 \rightarrow$ and $x,y,z$ were our parameters, it is clear that having a point far away from the global minimum, the function will be more sensitive to changes on $x$ than on $y$ or $z$. But the same parameter step applied to $y$ and $z$ will lead to the same change on our cost function $f(x,y,z)$.
In the general case, when we don't know exactly the terms of our cost function, one conservative rule for updating would be to use smaller learning rates on the directions with &quot;big&quot; gradients. This would prevent us from overshooting on these directions if the decision of moving along them with a big step was wrong.
To visualize the previous reasoning we can plot how would be the paths followed by our parameters applying different learning rates to them. In this case, the hypotetical cost function that I have used is $f(x,y)=20x^2+y^2$ and the number of iterations made are the same in all of them ($20$). With this plots we can see that:

Left plot $\rightarrow$ Applying a &quot;big&quot; learning rate to both $x$ and $y$ directions lead to overshooting on the $x$ direction, which causes that the path doesn't reach the minimum.
Center plot $\rightarrow$ Applying a &quot;small&quot; learning rate to both $x$ and $y$, solves the issue of overshooting, but causes the learning to be very slow.
Right plot $\rightarrow$ Applying a &quot;small&quot; learning rate to $x$ than to $y$ not only solves the issue of overshooting on the $x$ direction, but also makes faster the optimization.

Note that the optimization used here is not exactly like Adagrad optimization, but with it I pretend to show the effects of different learning rates.

Adagrad
With Adagrad we are able to take this previous intuition of why the learning rates should be different for each parameter but with another point of view.
For understanding why Adagrad behaves in the way described by the question, we should take a look at the practical formula that is commonly used for applying it:
$$ \mathbf{w}_{t+1}= \mathbf{w}_t - \frac{\alpha}{\sqrt{\epsilon I + \text{diag}(G_{t+1})}}\,\,g_{t+1} $$
Where $\mathbf{w}$ is the vector of parameters that we want to update, $g$ is the gradient of the cost function w.r.t. these parameters $\mathbf{w}$, $t$ is the number of the iteration taking place and $G_t$ is given by:
$$G_{t+1}=\sum_{\tau=1}^{t+1} g_\tau\,g_\tau^T$$
So, if we have a look at one parameter $w^j$ from the vector $\mathbf{w}= [w^1,w^2,...,w^n]^T$, we have:
$$ w_{t+1}^j = w_t^j - \frac{\alpha}{\sqrt{\epsilon + G_{t+1}^{jj}}}\,\,g_{t+1}^j \,\,\,\,\,\, \leftrightarrow \,\,\,\,\,\, G_{t+1}^{jj}=\sum_{\tau=1}^{t+1}(g_\tau^j)^2$$
What does this mean? $\rightarrow$ As $t\uparrow\uparrow$ the learning rate related to the parameter $w^j$ will tend to decrease. This is because in the denominator we have the cummulative sum of the absolute value of its previous gradients.
Thereby, using Adagrad we could also solve the problem presented in the previous plots. Due to the fact that the plotted function was more sensitive to changes on the $x$ direction (hence the x-component of the gradient was bigger), Adagrad will automatically give a lower learning rate to the updates in $x$ than on $y$.
But what is the relation of the above with the more/less common features?
Common features here take the meaning of features that during a significant number of updates their influence on the problem has been poorly analysed. This can happen because during these iterations the components of the gradient vector related to these features have had significant lower magnitudes.
Let's look at an example using Stochastic Gradient Descent $\rightarrow$ we will be updating the parameters for every single sample that we have.
Let's consider that our model of parameters is linear, and have two parameters $(w^{(1)},w^{(2)})$ that have to be trained $\rightarrow$ so we can have a predictive function like this:
$$\hat{y} = w^{(1)} x^{(1)} + w^{(2)} x^{(2)}$$
where $x^{(1)}$ and $x^{(2)}$ are the features of our problem.
So if we make use of a cost function ($J$) that represents the mean squared error of the prediction ($\hat{y}$) given by our parameters, the gradient at iteration $t$ will be given by a quantity proportional to the features:
$$ g_t = \left(\frac{\partial J}{\partial w^{(1)}_t}, \frac{\partial J}{\partial w^{(2)}_t}\right)^T \propto (x^{(1)}_t, x^{(2)}_t)^T $$
Thereby, using SGD the quantity that we use to update each of our parameters $\delta w_{t+1}$ is also proportional to the associated feature:
$$ \delta w_{t}^{(j)} \propto x^{(j)}_t$$
With this already set up, lets imaging that our training is done in three samples (just for visualization purposes). During these samples the $x^{(1)}$ feature is more frequent (or less sparse) than the other feature $x^{(2)}$, so we have a dataset, $\mathbb{X}$, similar to the next:
$$ \mathbb{X} = \begin{pmatrix}
1 &amp; 0\\
5 &amp; 0\\
3 &amp; 3\\
\end{pmatrix}$$
Where each row represents a sample of $x^{(1)}_t$ and $x^{(2)}_t$, with $t\in\{1,2,3\}$.
Now it is clear that the parameter $w^{(2)}$ won't be updated until the last sample ($t=3$), because during the first two samples ($t=1, 2$) its gradient component has been zero (becase its proportional to $x^{(2)}_t$).
But what would have happened at this point to $w^{(1)}$? $\rightarrow$ it would have been updated during the first two samples (non-zero gradient component), and because of it, its associated learning rate will be smaller than the one of $w^{(2)}$ in spite of having the same $x^{(1)}_3 = x^{(2)}_3$!
So now we understand why the parameters associated with sparse features can be updated with greater learning rates using Adagrad.
Conclusion
Adagrad allows us to give more importance to updates in parameters that have associated features which are sparse, or more generally, to give more importance to parameter updates that have experimented a record of relatively lower gradients (in magnitude).
Why is this useful? To answer this, we can cite the original authors (see paper: &quot;Adaptive Subgradient Methods for
Online Learning and Stochastic Optimization &quot;):
&gt; &quot;Our procedures give frequently occurring features
very low learning rates and infrequent features high learning rates, where the intuition is that each
time an infrequent feature is seen, the learner should “take notice.” Thus, the adaptation facilitates
finding and identifying very predictive but comparatively rare features&quot;