# A new Linear Time Bi-level ℓ1,∞ projection ; Application to the sparsification of auto-encoders neural networks

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 48 references that are in the map.
- First posted on arXiv 23 Jul 2024.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [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)
- [Green AI](https://mlsanity.com/paper/1907.10597/) (2019)
- [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)
- [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)
- [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)
- [Learning sparse auto-encoders for green AI image coding](https://mlsanity.com/paper/2209.04448/) (2022)

## 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 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 n× m. Moreover, we provide a new ℓ1,∞ identity with mathematical proof and experimental validation. Experiments show that our bi-level ℓ1,∞ projection is 2.5 times faster than the actual fastest algorithm and provides the best sparsity while keeping the same accuracy in classification applications.