Source-linked AI summary
meProp: Sparsified Back Propagation for Accelerated Deep Learning with Reduced Overfitting
Xu Sun, Xuancheng Ren, Shuming Ma, Houfeng Wang
TL;DR
Neural-network back propagation is costly because it computes full gradients and updates many parameters. meProp keeps only the top-k gradient values and updates the corresponding parameters, reducing computation. Experiments show that updating 1–4% of parameters can improve accuracy without increasing training iterations, although GPU speedups are less significant with low hidden dimensions.
Problem
Back propagation is computationally expensive because it computes full gradients and updates all parameters in networks with potentially massive parameter counts.
Method
meProp sparsifies back propagation by retaining top-k values of the backward gradient and updating only the corresponding parameter subset.
Results
1–4% of parameters can be updated while reducing back-propagation cost by one to two orders of magnitude and improving model accuracy in most cases.
Takeaways & Limitations
The method provides a general-purpose, optimizer-independent way to reduce back-propagation computation without increasing training iterations.
Takeaways & Limitations
GPU speedup is less significant when the hidden dimension is low because the baseline may already execute fast enough to underuse the GPU.
Abstract
from arXiv · showhide
We propose a simple yet effective technique for neural network learning. The forward propagation is computed as usual. In back propagation, only a small subset of the full gradient is computed to update the model parameters. The gradient vectors are sparsified in such a way that only the top-$k$ elements (in terms of magnitude) are kept. As a result, only $k$ rows or columns (depending on the layout) of the weight matrix are modified, leading to a linear reduction ($k$ divided by the vector dimension) in the computational cost. Surprisingly, experimental results demonstrate that we can update only 1-4% of the weights at each back propagation pass. This does not result in a larger number of training iterations. More interestingly, the accuracy of the resulting models is actually improved rather than degraded, and a detailed analysis is given. The code is available at https://github.com/lancopku/meProp
1. Introduction
meProp sparsifies back propagation by computing and updating only a small, highly relevant portion of gradients and parameters. Experiments report substantial efficiency gains without more iterations and improved accuracy across varied settings.
- meProp computes only a small, critical gradient portion and updates the corresponding parameters, leaving other parameters untouched.This produces sparsified gradients focused on highly relevant parameters.
- Top-k search identifies the most important parameters for each stochastic update.The method is described as general-purpose and independent of models and optimizers such as Adam and AdaGrad.
- 1–4% of weights can be updated at each back propagation pass without increasing the number of training iterations.
- The contributions are framed as a sparsified back propagation technique that reduces computation while preserving or improving trained-model accuracy.
- Accuracy improves rather than degrades across experiments using different deep learning models, optimization methods, and tasks.The experiments include LSTM and MLP models, Adam and AdaGrad, and natural language processing and image recognition.
2. Proposed Method
meProp keeps forward propagation unchanged but sparsifies back propagation by retaining only the top-k gradient components, reducing computation while updating a small subset of parameters. It applies this strategy to computationally intensive linear transformations and repeats sparsification across hidden layers when needed.
- 2.1. meProp: The selected gradient components modify only k rows or columns of the weight matrix, yielding a linear computational reduction proportional to k divided by the vector dimension.The cost reduction follows from restricting gradient computation and parameter updates to the selected subset.
- 2.1. meProp: meProp computes the usual forward pass, then keeps only the top-k components of backward-flowed gradients while masking the rest to zero.The method approximates gradients for the input vector and weight matrix rather than computing the full gradients.
- 2.2.1. WHERE TO APPLY MEPROP: meProp applies sparsification to the back propagation of matrix-matrix and matrix-vector multiplications, while retaining standard back propagation for relatively inexpensive element-wise operations.The implementation targets operations observed to dominate back-propagation time.
- 2.2.1. WHERE TO APPLY MEPROP: When a network has multiple hidden layers, top-k sparsification is applied at the output of every hidden layer because gradients become dense between layers.The output layer may use a different k because its dimension can differ substantially from hidden-layer dimensions.
- 2.2.2. HOW TO IMPLEMENT MEPROP: The top-k subset is found with a min-heap algorithm having time complexity O(n log k) and space complexity O(k).The implementation modifies the standard selection method to emphasize memory reuse.
3. Related Work
Prior work addresses faster learning, sparsity, sampled outputs, mixture-of-experts, or gradient communication, but these approaches differ in scope or mechanism from meProp. The supplied table captions define evaluation layouts and timing terminology for the paper’s model and training comparisons.
- Prior acceleration and sparsity methods: Earlier methods include adaptive weight updates, dropout, sparse coding, and sparse autoencoders, whereas meProp is presented as distinct from these approaches.The cited discussion groups these methods as related work on back propagation, overfitting, or sparse representations.
- Related neural-network methods: Sampled-output-loss methods are limited to the softmax output layer and random sampling, while sparsely-gated mixture-of-experts methods sparsify only a specific gated layer.The passage contrasts those scope restrictions with the stated scope of meProp.
- Evaluation setup: Table 1 compares LSTM and MLP models with AdaGrad and Adam, reporting averaged time per iteration, iterations to the optimal development score, and resulting test scores.The table’s iteration count determines which model is evaluated on the test data.
- Timing comparison: Table 2 separates overall forward-propagation time, overall back-propagation time, and total training time obtained by summing forward and backward times.The caption defines FP as forward propagation, BP as back propagation, and overall time as FP plus BP.
4. Experiments
Experiments evaluate meProp across LSTM and MLP models, Adam and AdaGrad optimizers, and POS tagging, parsing, and MNIST tasks, using standard datasets and task-specific metrics.
- Experiments cover LSTM and MLP models, Adam and AdaGrad optimization, and POS tagging, dependency parsing, and MNIST recognition.
- Experimental datasets and metrics: POS tagging uses Penn Treebank-derived WSJ data with per-word accuracy as the evaluation metric.
- Experimental datasets and metrics: Dependency parsing uses the standard English Penn TreeBank split and evaluates unlabeled attachment score.
- Experimental datasets and metrics: MNIST experiments use 60,000 training images and 10,000 test examples, with per-image accuracy as the metric.
- Model settings: All tasks use hidden layers of dimension 500, while output-layer dimensions vary by task and can motivate different top-k choices.
4.2. Experimental Results
Across model and optimizer settings, meProp reduces backpropagation cost by updating only a small fraction of weights without requiring more iterations, while improving accuracy in the reported experiments.
- MeProp updates only 1–4% of weights per backpropagation pass without increasing the number of training iterations.
- MeProp provides a linear reduction in computational cost while substantially speeding up backpropagation.
- The resulting models improve accuracy rather than degrade it, possibly because weakly relevant parameters remain unmodified and overfitting becomes less likely.
- Backpropagation is the major computational cost in LSTM and MLP training.
- Results are consistent across AdaGrad and Adam, indicating independence from the specific optimization method.
4.3. Varying Backprop Ratio
Varying the top-k backpropagation ratio shows that meProp maintains better test accuracy than the baseline, including at highly sparse update ratios.
- 98.15% (+0.33) is the best test accuracy reported for meProp when varying the backpropagation ratio.For k=5, the backpropagation ratio is 5/500=1%.
- MeProp achieves consistently better accuracy than the baseline across the tested backpropagation ratios.
4.4. Top-k vs. Random
Top-k selection outperforms random gradient selection, and meProp’s gains are not explained by simply using smaller hidden layers; it can also complement dropout and deeper models.
- Top-k versus random: Top-k meProp performs better than random meProp, suggesting that top-k gradient elements carry the most important information.
- Top-k versus smaller hidden dimensions: Models with hidden dimension equal to k perform much worse than meProp, so meProp’s results are not explained by smaller hidden layers alone.
- MeProp and dropout: MeProp can further improve performance when added to dropout, including a 0.46 UAS improvement on parsing.
- MeProp and dropout: The results suggest that meProp reduces an overfitting type probably different from dropout’s, allowing both methods to be used together.
4.7. Adding More Hidden Layers
Adding hidden layers from 2 to 5 does not hurt meProp's performance, with a dropout rate of 0.1 used for comparison.
- Across models with 2 to 5 hidden layers, adding layers does not hurt meProp's performance.The experiments use a dropout rate of 0.1 for the different layer counts.
4.8. Speedup on GPU
The GPU implementation uses unified top-k sparsity across each mini-batch, but speedup depends strongly on model size. GPU acceleration is more substantial for heavy models with large hidden dimensions.
- Unified top-k averages mini-batch gradients to create consistent sparse patterns across examples.The resulting sparse matrix can be converted into a small dense matrix by removing zero values.
- GPU speedup is less significant for low-dimensional hidden layers because the baseline does not fully consume available computational power.For MLPs with hidden dimensions 64 and 512, forward propagation takes 572ms and 644ms, respectively, despite a theoretical 8x difference.
- MeProp achieves much higher GPU speed than traditional backpropagation on synthetic matrix multiplication with large hidden dimensions.The speedup test is more meaningful when the baseline can fully consume the GPU's computational power.
- MeProp also provides substantial GPU speedup on MNIST with large hidden dimensions.The paper reports this result in its GPU experiments on MLPs.
- Other GPU implementations, including sparse matrix multiplication, remain possible directions for future work.The paper identifies alternative implementation choices beyond the simple unified top-k approach.
4.9. Related Systems on the Tasks
On POS tagging, dependency parsing, and MNIST, meProp's reported scores are within the ranges or near the reference results described for prior systems.
- 97.31% per-word accuracy is reported for meProp on POS tagging, within the cited prior range of 97.2% to 97.4%.
- 91.99 UAS is reported for meProp on transition-based dependency parsing, near Chen and Manning's 92.0 UAS.
- 98.37% accuracy is reported for meProp on MNIST, within the cited 98–99% range for MLP-based approaches.The paper notes that convolutional layers and other techniques can raise accuracy above 99%, but those additions are outside its focus.
5. Conclusions
MeProp sparsifies back propagation by computing and applying only a small, relevant portion of the gradient. The paper reports one-to-two-order computational savings while updating 1–4% of parameters and improving accuracy in most cases.
- MeProp computes only a small, critical gradient portion and updates the corresponding parameters during each training step.This produces sparsified gradients that target highly relevant parameters for each training sample.
- Updating only 1–4% of parameters reduces back-propagation computational cost by one to two orders of magnitude.
- MeProp is independent of the optimization method.
- Model accuracy improves in most cases despite the sparse parameter updates.