# Efficient Exact Gradient Update for training Deep Networks with Very Large Sparse Targets

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Dec 2014.

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

- [THE-X: Privacy-Preserving Transformer Inference with Homomorphic Encryption](https://mlsanity.com/paper/2206.00216/) (2022)
- [Fast Variational AutoEncoder with Inverted Multi-Index for Collaborative Filtering](https://mlsanity.com/paper/2109.05773/) (2021)
- [Escaping the Gradient Vanishing: Periodic Alternatives of Softmax in Attention Mechanism](https://mlsanity.com/paper/2108.07153/) (2021)
- [TaylorShift: Shifting the Complexity of Self-Attention from Squared to Linear (and Back) using Taylor-Softmax](https://mlsanity.com/paper/2403.02920/) (2024)
- [Online Neural Path Guiding with Normalized Anisotropic Spherical Gaussians](https://mlsanity.com/paper/2303.08064/) (2023)
- [On the Interpretability of Attention Networks](https://mlsanity.com/paper/2212.14776/) (2022)
- [Privacy-Preserving Diffusion Model Using Homomorphic Encryption](https://mlsanity.com/paper/2403.05794/) (2024)
- [Sparse-softmax: A Simpler and Faster Alternative Softmax Transformation](https://mlsanity.com/paper/2112.12433/) (2021)
- [Adaptive Temperature Based on Logits Correlation in Knowledge Distillation](https://mlsanity.com/paper/2503.09030/) (2025)
- [Adaptive Sparse Softmax: An Effective and Efficient Softmax Variant](https://mlsanity.com/paper/2508.03175/) (2025)

## Abstract (arXiv)

An important class of problems involves training deep neural networks with sparse prediction targets of very high dimension D. These occur naturally in e.g. neural language models or the learning of word-embeddings, often posed as predicting the probability of next words among a vocabulary of size D (e.g. 200 000). Computing the equally large, but typically non-sparse D-dimensional output vector from a last hidden layer of reasonable dimension d (e.g. 500) incurs a prohibitive O(Dd) computational cost for each example, as does updating the D x d output weight matrix and computing the gradient needed for backpropagation to previous layers. While efficient handling of large sparse network inputs is trivial, the case of large sparse targets is not, and has thus so far been sidestepped with approximate alternatives such as hierarchical softmax or sampling-based approximations during training. In this work we develop an original algorithmic approach which, for a family of loss functions that includes squared error and spherical softmax, can compute the exact loss, gradient update for the output weights, and gradient for backpropagation, all in O(d^2) per example instead of O(Dd), remarkably without ever computing the D-dimensional output. The proposed algorithm yields a speedup of D/4d , i.e. two orders of magnitude for typical sizes, for that critical part of the computations that often dominates the training time in this kind of network architecture.