# Multi-level projection with exponential parallel speedup; Application to sparse auto-encoders neural networks

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 50 references that are in the map.
- First posted on arXiv 3 May 2024.

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

- [Auto-Encoding Variational Bayes](https://mlsanity.com/paper/1312.6114/) (2013)
- [The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks](https://mlsanity.com/paper/1803.03635/) (2018)
- [Learning both Weights and Connections for Efficient Neural Networks](https://mlsanity.com/paper/1506.02626/) (2015)
- [Semi-Supervised Learning with Deep Generative Models](https://mlsanity.com/paper/1406.5298/) (2014)
- [High-Fidelity Generative Image Compression](https://mlsanity.com/paper/2006.09965/) (2020)
- [Lossy Image Compression with Compressive Autoencoders](https://mlsanity.com/paper/1703.00395/) (2017)
- [Deconstructing Lottery Tickets: Zeros, Signs, and the Supermask](https://mlsanity.com/paper/1905.01067/) (2019)
- [Data-Driven Sparse Structure Selection for Deep Neural Networks](https://mlsanity.com/paper/1707.01213/) (2017)
- [A Review on Bilevel Optimization: From Classical to Evolutionary Approaches and Applications](https://mlsanity.com/paper/1705.06270/) (2017)
- [Group Sparse Regularization for Deep Neural Networks](https://mlsanity.com/paper/1607.00485/) (2016)
- [Learning the Number of Neurons in Deep Networks](https://mlsanity.com/paper/1611.06321/) (2016)
- [Learning Sparse Networks Using Targeted Dropout](https://mlsanity.com/paper/1905.13678/) (2019)
- [Learning Sparse Neural Networks via Sensitivity-Driven Regularization](https://mlsanity.com/paper/1810.11764/) (2018)
- [Dropout as a Low-Rank Regularizer for Matrix Factorization](https://mlsanity.com/paper/1710.05092/) (2017)
- [Classification and regression using an outer approximation projection-gradient method](https://mlsanity.com/paper/1506.02196/) (2015)
- [Efficient Projection onto the ℓ∞,1 Mixed-Norm Ball using a Newton root search method](https://mlsanity.com/paper/1806.10041/) (2018)
- [Exclusive Group Lasso for Structured Variable Selection](https://mlsanity.com/paper/2108.10284/) (2021)
- [Near-Linear Time Projection onto the ℓ1,∞ Ball; Application to Sparse Autoencoders](https://mlsanity.com/paper/2307.09836/) (2023)

## Abstract (arXiv)

The ℓ1,∞ norm is an efficient structured projection but the complexity of the best algorithm is unfortunately Obig(n m log(n m)big) for a matrix in ℝn× m. In this paper, we propose a new bi-level projection method for which we show that the time complexity for the ℓ1,∞ norm is only Obig(n m big) for a matrix in ℝn× m, and Obig(n + m big) with full parallel power. We generalize our method to tensors and we propose a new multi-level projection, having an induced decomposition that yields a linear parallel speedup up to an exponential speedup factor, resulting in a time complexity lower-bounded by the sum of the dimensions, instead of the product of the dimensions. we provide a large base of implementation of our framework for bi-level and tri-level (matrices and tensors) for various norms and provides also the parallel implementation. Experiments show that our projection is 2 times faster than the actual fastest Euclidean algorithms while providing same accuracy and better sparsity in neural networks applications.