# Scalable Adaptive Stochastic Optimization Using Random Projections

arXiv: https://arxiv.org/abs/1611.06652 · HTML: https://mlsanity.com/paper/1611.06652/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Nov 2016.

## Built on by (most cited first, 3 of 3)

- [Sketchy: Memory-efficient Adaptive Regularization with Frequent Directions](https://mlsanity.com/paper/2302.03764/) (2023)
- [EigenGame Unloaded: When playing games is better than optimizing](https://mlsanity.com/paper/2102.04152/) (2021)
- [Dynamic Low-rank Approximation of Full-Matrix Preconditioner for Training Generalized Linear Models](https://mlsanity.com/paper/2508.21106/) (2025)

## Abstract (arXiv)

Adaptive stochastic gradient methods such as AdaGrad have gained popularity in particular for training deep neural networks. The most commonly used and studied variant maintains a diagonal matrix approximation to second order information by accumulating past gradients which are used to tune the step size adaptively. In certain situations the full-matrix variant of AdaGrad is expected to attain better performance, however in high dimensions it is computationally impractical. We present Ada-LR and RadaGrad two computationally efficient approximations to full-matrix AdaGrad based on randomized dimensionality reduction. They are able to capture dependencies between features and achieve similar performance to full-matrix AdaGrad but at a much smaller computational cost. We show that the regret of Ada-LR is close to the regret of full-matrix AdaGrad which can have an up-to exponentially smaller dependence on the dimension than the diagonal variant. Empirically, we show that Ada-LR and RadaGrad perform similarly to full-matrix AdaGrad. On the task of training convolutional neural networks as well as recurrent neural networks, RadaGrad achieves faster convergence than diagonal AdaGrad.