Unbiased Approximate Vector-Jacobian Products for Efficient Backpropagation

Killian Bakong, Laurent Massoulié, Edouard Oyallon, Kevin Scaman

TL;DR

This paper proposes a method to slash the computational and memory costs of training deep neural networks by replacing exact backpropagation steps with randomized, unbiased approximations. By mathematically optimizing these "sketches" to minimize variance, the authors demonstrate that you can significantly speed up training with negligible impact on final model accuracy.

What Problem Does This Paper Address?

Backpropagation is the engine of modern AI, but it is also a massive resource hog. Specifically, it relies on vector-Jacobian products (VJPs)—the mathematical operation that propagates error signals backward through the network. As models grow, these VJPs become a bottleneck in two ways:

  1. Memory/Computation: Storing activations and computing exact derivatives for every single parameter is expensive.
  2. Communication: In distributed training (like pipeline parallelism), moving these high-dimensional signals between GPUs creates massive latency.

While previous work has focused on compressing gradients after they are computed, this paper asks: Can we compress the computation itself during the backprop process?

Methods

The authors introduce a framework for Randomized Sketching of VJPs. Instead of computing the exact product $J^T g$ (where $J$ is the Jacobian and $g$ is the incoming gradient), they compute $J^T R g$, where $R$ is a random "sketching" matrix.

The key technical contributions are:

  • Unbiasedness: They ensure that the expected value of the approximation equals the true value. This is critical because Stochastic Gradient Descent (SGD) is mathematically robust to noise, provided that noise doesn't introduce a systematic bias.
  • Optimal Low-Rank Sketches: They derive the "best" possible sketching matrix (one that minimizes variance) using Singular Value Decomposition (SVD).
  • Data-Dependent Masking: Recognizing that SVD is too slow for real-time training, they propose Diagonal Sketches (DS). These use "importance weights"—like the $\ell_1$ norm or the variance of gradient coordinates—to decide which parts of the signal to keep and which to drop.
  • Correlated Sampling: They use a specific sampling scheme to ensure the "sketch" always has a fixed size (rank), which stabilizes the training process compared to independent random dropping.

Datasets

The researchers evaluated their methods across several architectures and tasks:

  • MNIST: Used for initial proof-of-concept experiments on 4-layer Multi-Layer Perceptrons (MLPs).
  • CIFAR-10: Used to test scalability on more complex architectures, specifically BagNet-17 (a variant of ResNet) and Visual Transformers (ViT).

Key Insights and Ideas

  • The Variance-Efficiency Trade-off: The authors prove that you can use a noisy gradient surrogate as long as it's unbiased. While noise might require you to train for more epochs, if each epoch is significantly cheaper (due to sketching), the total "wall-clock time" to reach a target accuracy still goes down.
  • Smart Dropping > Random Dropping: Uniformly masking out neurons (like a backward-pass version of Dropout) performs poorly. However, using data-dependent proxies—specifically the $\ell_1$-score—to keep high-impact directions allows for massive compression with minimal accuracy loss.
  • Local Optimality vs. Global Dynamics: The paper identifies that while their sketches are "locally optimal" (minimizing variance at a single layer), the way this variance propagates through a deep stack of layers is complex. Interestingly, they found that errors in the later layers of the network (closer to the output) degrade accuracy more than errors in the early layers.

Key Results

  • Superiority of Data-Dependent Methods: In all tests, data-dependent sketches (like DS and RCS) significantly outperformed agnostic uniform masking.
  • High Compression, Low Loss: On BagNet and ViT, the authors showed that you could reduce the "sampling budget" (the fraction of the VJP kept) significantly. For example, using an $\ell_1$ proxy, they maintained high accuracy even when using only a fraction of the standard computational budget.
  • Spectral Methods Win (at a cost): Strategies based on SVD (Rank-Constraint Sketches) provided the highest accuracy for a given budget, confirming their theoretical optimality, though they are computationally heavier to implement than diagonal masks.

Limitations and Future Work

  • Implementation Overhead: While sketching reduces the cost of the VJP itself, calculating the "importance weights" (like $\ell_1$ norms or variances) adds a new, albeit smaller, computational cost.
  • Layer Coordination: Currently, each layer is sketched independently. The authors suggest that "coordinated sketching"—where layers communicate to decide which directions are globally most important—could yield even better results.
  • Hardware Acceleration: The paper focuses on the algorithmic side; future work is needed to see how these sparse, randomized operations can be best mapped to specialized hardware like TPUs or new generations of GPUs to realize the theoretical speedups.

Summary updated

Abstract

In this work we introduce methods to reduce the computational and memory costs of training deep neural networks. Our approach consists in replacing exact vector-jacobian products by randomized, unbiased approximations thereof during backpropagation. We provide a theoretical analysis of the trade-off between the number of epochs needed to achieve a target precision and the cost reduction for each epoch. We then identify specific unbiased estimates of vector-jacobian products for which we establish desirable optimality properties of minimal variance under sparsity constraints. Finally we provide in-depth experiments on multi-layer perceptrons, BagNets and Visual Transfomers architectures. These validate our theoretical results, and confirm the potential of our proposed unbiased randomized backpropagation approach for reducing the cost of deep learning.
BibTeX
@misc{bakong2026unbiased,
  author = {Killian Bakong and Laurent Massoulié and Edouard Oyallon and Kevin Scaman},
  title = {{Unbiased Approximate Vector-Jacobian Products for Efficient Backpropagation}},
  year = {2026},
  eprint = {2602.14701},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2602.14701},
}
Figure