Pixelated Butterfly: Simple and Efficient Sparse training for Neural Network Models
arXiv:2112.00029
Abstract
Overparameterized neural networks generalize well but are expensive to train. Ideally, one would like to reduce their computational cost while retaining their generalization benefits. Sparse model training is a simple and promising approach to achieve this, but there remain challenges as existing methods struggle with accuracy loss, slow training runtime, or difficulty in sparsifying all model components. The core problem is that searching for a sparsity mask over a discrete set of sparse matrices is difficult and expensive. To address this, our main insight is to optimize over a continuous superset of sparse matrices with a fixed structure known as products of butterfly matrices. As butterfly matrices are not hardware efficient, we propose simple variants of butterfly (block and flat) to take advantage of modern hardware. Our method (Pixelated Butterfly) uses a simple fixed sparsity pattern based on flat block butterfly and low-rank matrices to sparsify most network layers (e.g., attention, MLP). We empirically validate that Pixelated Butterfly is 3x faster than butterfly and speeds up training to achieve favorable accuracy--efficiency tradeoffs. On the ImageNet classification and WikiText-103 language modeling tasks, our sparse models train up to 2.5x faster than the dense MLP-Mixer, Vision Transformer, and GPT-2 medium with no drop in accuracy.
arXiv commentInternational Conference on Learning Representations (ICLR) 2022 spotlight
References in corpus (33)
- An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale
- Language Models are Few-Shot Learners
- On the Opportunities and Risks of Foundation Models
- Reconciling modern machine learning practice and the bias-variance trade-off
- Scaling Laws for Neural Language Models
- MLP-Mixer: An all-MLP Architecture for Vision
- Neural Tangent Kernel: Convergence and Generalization in Neural Networks
- The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks
- A Convergence Theory for Deep Learning via Over-Parameterization
- To prune, or not to prune: exploring the efficacy of pruning for model compression
- Generating Long Sequences with Sparse Transformers
- Pointer Sentinel Mixture Models
- Deep Learning Recommendation Model for Personalization and Recommendation Systems
- Gradient Descent Provably Optimizes Over-parameterized Neural Networks
- Reformer: The Efficient Transformer
- Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data
- Long Range Arena: A Benchmark for Efficient Transformers
- Picking Winning Tickets Before Training by Preserving Gradient Flow
- Stabilizing the Lottery Ticket Hypothesis
- One ticket to win them all: generalizing lottery ticket initializations across datasets and optimizers
- CondenseNet: An Efficient DenseNet using Learned Group Convolutions
- Tunable Efficient Unitary Neural Networks (EUNN) and their application to RNNs
- Quadratic Suffices for Over-parametrization via Matrix Chernoff Bound
- Learning Fast Algorithms for Linear Transforms Using Butterfly Factorizations
- Movement Pruning: Adaptive Sparsity by Fine-Tuning
- Quadrature-based features for kernel approximation
- Nyströmformer: A Nyström-Based Algorithm for Approximating Self-Attention
- Optimal Lottery Tickets via SubsetSum: Logarithmic Over-Parameterization is Sufficient
- Variable Selection is Hard
- Fast Approximation of Rotations and Hessians matrices
- Recovering Model Structures from Large Low Rank and Sparse Covariance Matrix Estimation
- Sparse Weight Activation Training
- Kaleidoscope: An Efficient, Learnable Representation For All Structured Linear Maps