# Near-Linear Time Projection onto the ℓ1,∞ Ball; Application to Sparse Autoencoders

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in Sparse autoencoder training and evaluation, one of 13 directions in Mechanistic interpretability.
- Builds on 17 of its 56 references that are in the map.
- First posted on arXiv 19 Jul 2023.

## Placed in

- Mechanistic interpretability / [Sparse autoencoder training and evaluation](https://mlsanity.com/mechinterp/sparse-autoencoder-training-and-evaluation/)

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

- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- [Auto-Encoding Variational Bayes](https://mlsanity.com/paper/1312.6114/) (2013)
- [Green AI](https://mlsanity.com/paper/1907.10597/) (2019)
- [Semi-Supervised Learning with Deep Generative Models](https://mlsanity.com/paper/1406.5298/) (2014)
- [Lossy Image Compression with Compressive Autoencoders](https://mlsanity.com/paper/1703.00395/) (2017)
- [Data-Driven Sparse Structure Selection for Deep Neural Networks](https://mlsanity.com/paper/1707.01213/) (2017)
- [PanGu-α: Large-scale Autoregressive Pretrained Chinese Language Models with Auto-parallel Computation](https://mlsanity.com/paper/2104.12369/) (2021)
- [Checkmate: Breaking the Memory Wall with Optimal Tensor Rematerialization](https://mlsanity.com/paper/1910.02653/) (2019)
- [Learning the Number of Neurons in Deep Networks](https://mlsanity.com/paper/1611.06321/) (2016)
- [On Controllable Sparse Alternatives to Softmax](https://mlsanity.com/paper/1810.11975/) (2018)
- [Learning Sparse Neural Networks via Sensitivity-Driven Regularization](https://mlsanity.com/paper/1810.11764/) (2018)
- [Effective Model Sparsification by Scheduled Grow-and-Prune Methods](https://mlsanity.com/paper/2106.09857/) (2021)
- [Proximal Splitting Algorithms for Convex Optimization: A Tour of Recent Advances, with New Twists](https://mlsanity.com/paper/1912.00137/) (2019)
- [Dropout as a Low-Rank Regularizer for Matrix Factorization](https://mlsanity.com/paper/1710.05092/) (2017)
- [Sparse-IFT: Sparse Iso-FLOP Transformations for Maximizing Training Efficiency](https://mlsanity.com/paper/2303.11525/) (2023)
- [Efficient Projection onto the ℓ∞,1 Mixed-Norm Ball using a Newton root search method](https://mlsanity.com/paper/1806.10041/) (2018)
- [Learning sparse auto-encoders for green AI image coding](https://mlsanity.com/paper/2209.04448/) (2022)

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

- [Multi-level projection with exponential parallel speedup; Application to sparse auto-encoders neural networks](https://mlsanity.com/paper/2405.02086/) (2024)

## Abstract (arXiv)

Looking for sparsity is nowadays crucial to speed up the training of large-scale neural networks. Projections onto the ℓ1,2 and ℓ1,∞ are among the most efficient techniques to sparsify and reduce the overall cost of neural networks. In this paper, we introduce a new projection algorithm for the ℓ1,∞ norm ball. The worst-case time complexity of this algorithm is Obig(nm+Jlog(nm)big) for a matrix in ℝn× m. J is a term that tends to 0 when the sparsity is high, and to nm when the sparsity is low. Its implementation is easy and it is guaranteed to converge to the exact solution in a finite time. Moreover, we propose to incorporate the ℓ1,∞ ball projection while training an autoencoder to enforce feature selection and sparsity of the weights. Sparsification appears in the encoder to primarily do feature selection due to our application in biology, where only a very small part (<2%) of the data is relevant. We show that both in the biological case and in the general case of sparsity that our method is the fastest.