# Frequency-aware SGD for Efficient Embedding Learning with Provable Benefits

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 42 references that are in the map.
- First posted on arXiv 10 Oct 2021.

## Builds on (most cited first, 24 of 24)

- [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)
- [RoBERTa: A Robustly Optimized BERT Pretraining Approach](https://mlsanity.com/paper/1907.11692/) (2019)
- [Efficient Estimation of Word Representations in Vector Space](https://mlsanity.com/paper/1301.3781/) (2013)
- [Distributed Representations of Words and Phrases and their Compositionality](https://mlsanity.com/paper/1310.4546/) (2013)
- [Pointer Sentinel Mixture Models](https://mlsanity.com/paper/1609.07843/) (2016)
- [Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour](https://mlsanity.com/paper/1706.02677/) (2017)
- [On the Convergence of Adam and Beyond](https://mlsanity.com/paper/1904.09237/) (2019)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [DeepFM: A Factorization-Machine based Neural Network for CTR Prediction](https://mlsanity.com/paper/1703.04247/) (2017)
- [Deep Interest Network for Click-Through Rate Prediction](https://mlsanity.com/paper/1706.06978/) (2017)
- [Lower Bounds for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1912.02365/) (2019)
- [Understanding the Difficulty of Training Transformers](https://mlsanity.com/paper/2004.08249/) (2020)
- [AdaGrad stepsizes: Sharp convergence over nonconvex landscapes](https://mlsanity.com/paper/1806.01811/) (2018)
- [On the Convergence of A Class of Adam-Type Algorithms for Non-Convex Optimization](https://mlsanity.com/paper/1808.02941/) (2018)
- [A Simple Convergence Proof of Adam and Adagrad](https://mlsanity.com/paper/2003.02395/) (2020)
- [On the Convergence of Adaptive Gradient Methods for Nonconvex Optimization](https://mlsanity.com/paper/1808.05671/) (2018)
- [A Troubling Analysis of Reproducibility and Progress in Recommender Systems Research](https://mlsanity.com/paper/1911.07698/) (2019)
- [On the Dimensionality of Word Embedding](https://mlsanity.com/paper/1812.04224/) (2018)
- [The Complexity of Finding Stationary Points with Stochastic Gradient Descent](https://mlsanity.com/paper/1910.01845/) (2019)
- [Stochastic Block Mirror Descent Methods for Nonsmooth and Stochastic Optimization](https://mlsanity.com/paper/1309.2249/) (2013)
- [Origins of power-law degree distribution in the heterogeneity of human activity in social networks](https://mlsanity.com/paper/1304.4523/) (2013)
- [Power laws in citation distributions: Evidence from Scopus](https://mlsanity.com/paper/1402.3890/) (2014)

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

- [Heavy-Tailed Class Imbalance and Why Adam Outperforms Gradient Descent on Language Models](https://mlsanity.com/paper/2402.19449/) (2024)
- [Outliers Dimensions that Disrupt Transformers Are Driven by Frequency](https://mlsanity.com/paper/2205.11380/) (2022)
- [Scaling Laws for Gradient Descent and Sign Descent for Linear Bigram Models under Zipf's Law](https://mlsanity.com/paper/2505.19227/) (2025)
- [AdaGrad under Anisotropic Smoothness](https://mlsanity.com/paper/2406.15244/) (2024)
- [The Evolution of Embedding Table Optimization and Multi-Epoch Training in Pinterest Ads Conversion](https://mlsanity.com/paper/2505.05605/) (2025)
- [Let Training Guide Selection: Online Synthetic Data Filtering via Real-Anchored Utility](https://mlsanity.com/paper/2609.29988/) (2026)

## Abstract (arXiv)

Embedding learning has found widespread applications in recommendation systems and natural language modeling, among other domains. To learn quality embeddings efficiently, adaptive learning rate algorithms have demonstrated superior empirical performance over SGD, largely accredited to their token-dependent learning rate. However, the underlying mechanism for the efficiency of token-dependent learning rate remains underexplored. We show that incorporating frequency information of tokens in the embedding learning problems leads to provably efficient algorithms, and demonstrate that common adaptive algorithms implicitly exploit the frequency information to a large extent. Specifically, we propose (Counter-based) Frequency-aware Stochastic Gradient Descent, which applies a frequency-dependent learning rate for each token, and exhibits provable speed-up compared to SGD when the token distribution is imbalanced. Empirically, we show the proposed algorithms are able to improve or match adaptive algorithms on benchmark recommendation tasks and a large-scale industrial recommendation system, closing the performance gap between SGD and adaptive algorithms. Our results are the first to show token-dependent learning rate provably improves convergence for non-convex embedding learning problems.