# Sketchy: Memory-efficient Adaptive Regularization with Frequent Directions

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 81 references that are in the map.
- First posted on arXiv 7 Feb 2023.

## Builds on (most cited first, 30 of 32)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [ImageNet Large Scale Visual Recognition Challenge](https://mlsanity.com/paper/1409.0575/) (2014)
- [Layer Normalization](https://mlsanity.com/paper/1607.06450/) (2016)
- [Outrageously Large Neural Networks: The Sparsely-Gated Mixture-of-Experts Layer](https://mlsanity.com/paper/1701.06538/) (2017)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Conformer: Convolution-augmented Transformer for Speech Recognition](https://mlsanity.com/paper/2005.08100/) (2020)
- [Do ImageNet Classifiers Generalize to ImageNet?](https://mlsanity.com/paper/1902.10811/) (2019)
- [Relational inductive biases, deep learning, and graph networks](https://mlsanity.com/paper/1806.01261/) (2018)
- [On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima](https://mlsanity.com/paper/1609.04836/) (2016)
- [Adafactor: Adaptive Learning Rates with Sublinear Memory Cost](https://mlsanity.com/paper/1804.04235/) (2018)
- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Optimizing Neural Networks with Kronecker-factored Approximate Curvature](https://mlsanity.com/paper/1503.05671/) (2015)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Shampoo: Preconditioned Stochastic Tensor Optimization](https://mlsanity.com/paper/1802.09568/) (2018)
- [An Investigation into Neural Net Optimization via Hessian Eigenvalue Density](https://mlsanity.com/paper/1901.10159/) (2019)
- [Empirical Analysis of the Hessian of Over-Parametrized Neural Networks](https://mlsanity.com/paper/1706.04454/) (2017)
- [Gradient Descent Happens in a Tiny Subspace](https://mlsanity.com/paper/1812.04754/) (2018)
- [Eigenvalues of the Hessian in Deep Learning: Singularity and Beyond](https://mlsanity.com/paper/1611.07476/) (2016)
- [A Deeper Look at the Hessian Eigenspectrum of Deep Neural Networks and its Applications to Regularization](https://mlsanity.com/paper/2012.03801/) (2020)
- [Disentangling Adaptive Gradient Methods from Learning Rates](https://mlsanity.com/paper/2002.11803/) (2020)
- [Frequent Directions : Simple and Deterministic Matrix Sketching](https://mlsanity.com/paper/1501.01711/) (2015)
- [On the Factory Floor: ML Engineering for Industrial-Scale Ads Recommendation Models](https://mlsanity.com/paper/2209.05310/) (2022)
- [Efficient Second Order Online Learning by Sketching](https://mlsanity.com/paper/1602.02202/) (2016)
- [Logistic Regression: Tight Bounds for Stochastic and Online Optimization](https://mlsanity.com/paper/1405.3843/) (2014)
- [When Does Preconditioning Help or Hurt Generalization?](https://mlsanity.com/paper/2006.10732/) (2020)
- [Memory-Efficient Adaptive Optimization](https://mlsanity.com/paper/1901.11150/) (2019)
- [Lecture Notes: Optimization for Machine Learning](https://mlsanity.com/paper/1909.03550/) (2019)
- [Extreme Tensoring for Low-Memory Preconditioning](https://mlsanity.com/paper/1902.04620/) (2019)

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

- [Old Optimizer, New Norm: An Anthology](https://mlsanity.com/paper/2409.20325/) (2024)
- [Flora: Low-Rank Adapters Are Secretly Gradient Compressors](https://mlsanity.com/paper/2402.03293/) (2024)
- [Modular Duality in Deep Learning](https://mlsanity.com/paper/2410.21265/) (2024)
- [ASGO: Adaptive Structured Gradient Optimization](https://mlsanity.com/paper/2503.20762/) (2025)
- [Memory-Efficient LLM Training with Online Subspace Descent](https://mlsanity.com/paper/2408.12857/) (2024)
- [LoRA Done RITE: Robust Invariant Transformation Equilibration for LoRA Optimization](https://mlsanity.com/paper/2410.20625/) (2024)
- [Purifying Shampoo: Investigating Shampoo's Heuristics by Decomposing its Preconditioner](https://mlsanity.com/paper/2506.03595/) (2025)
- [4-bit Shampoo for Memory-Efficient Network Training](https://mlsanity.com/paper/2405.18144/) (2024)
- [MuonEq: Balancing Before Orthogonalization with Lightweight Equilibration](https://mlsanity.com/paper/2603.28254/) (2026)
- [Memory-Efficient Optimization with Factorized Hamiltonian Descent](https://mlsanity.com/paper/2406.09958/) (2024)
- [Revisiting Matrix Sketching in Linear Bandits: Achieving Sublinear Regret via Dyadic Block Sketching](https://mlsanity.com/paper/2410.10258/) (2024)
- [Low-rank Momentum Factorization for Memory Efficient Training](https://mlsanity.com/paper/2507.08091/) (2025)
- [Ginger: An Efficient Curvature Approximation with Linear Complexity for General Neural Networks](https://mlsanity.com/paper/2402.03295/) (2024)
- [Convergence Rate Analysis of the AdamW-style Shampoo: Unifying One-Sided and Two-Sided Preconditioning](https://mlsanity.com/paper/2601.07326/) (2026)
- [Muse: Representation Geometry of Muon Beyond Normalized Momentum](https://mlsanity.com/paper/2607.14536/) (2026)
- [Subspace Langevin Monte Carlo](https://mlsanity.com/paper/2412.13928/) (2024)
- [Minimax Optimality of Shampoo for Nonstationary Stochastic Optimization](https://mlsanity.com/paper/2610.16923/) (2026)

## Abstract (arXiv)

Adaptive regularization methods that exploit more than the diagonal entries exhibit state of the art performance for many tasks, but can be prohibitive in terms of memory and running time. We find the spectra of the Kronecker-factored gradient covariance matrix in deep learning (DL) training tasks are concentrated on a small leading eigenspace that changes throughout training, motivating a low-rank sketching approach. We describe a generic method for reducing memory and compute requirements of maintaining a matrix preconditioner using the Frequent Directions (FD) sketch. While previous approaches have explored applying FD for second-order optimization, we present a novel analysis which allows efficient interpolation between resource requirements and the degradation in regret guarantees with rank k: in the online convex optimization (OCO) setting over dimension d, we match full-matrix d2 memory regret using only dk memory up to additive error in the bottom d-k eigenvalues of the gradient covariance. Further, we show extensions of our work to Shampoo, resulting in a method competitive in quality with Shampoo and Adam, yet requiring only sub-linear memory for tracking second moments.