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

Guillaume Perez, Laurent Condat, Michel Barlaud

TL;DR

Researchers have developed a "near-linear" time algorithm for projecting matrices onto the $\ell_{1,\infty}$ ball, a critical operation for enforcing structured sparsity in neural networks. By iterating backward and using efficient heap structures, the method is significantly faster than existing state-of-the-art solvers—especially in high-sparsity scenarios like feature selection for biological data.

What Problem Does This Paper Address?

Training massive neural networks is a resource hog, consuming vast amounts of energy and memory. Sparsity—the practice of making many network weights zero—is a primary solution to reduce this "processing tax." While standard $\ell_1$ (Lasso) regularization is common, it often results in "unstructured" sparsity, where zeros are scattered randomly.

In contrast, the $\ell_{1,\infty}$ norm (often used for group sparsity) is powerful because it can zero out entire columns of a matrix. In a neural network, this effectively "turns off" specific neurons or input features entirely, which is much more useful for hardware optimization and interpretability. However, the mathematical operation required to enforce this—projecting a matrix onto the $\ell_{1,\infty}$ ball—has historically been computationally expensive or required complex, approximate solvers. This paper aims to make this projection fast, exact, and easy to implement.

Methods

The authors introduce the Projection Inverse Total Order algorithm. Its key innovation lies in how it finds the optimal threshold ($\theta$) used to truncate the matrix values.

  1. Inverse Iteration: Most algorithms sort the entire matrix or iterate forward to find which values to keep. This algorithm works backward. Since most values will be zeroed out in a sparse model, starting from the "bottom" allows the algorithm to converge much faster.
  2. Hierarchical Heaps: Instead of a single massive sort, the algorithm maintains a global heap of columns and individual heaps for the elements within those columns. This reduces the worst-case complexity.
  3. Complexity: The time complexity is $O(nm + J \log(nm))$, where $n \times m$ is the matrix size and $J$ represents the number of non-modified values. When sparsity is high, $J$ approaches zero, making the algorithm effectively linear ($O(nm)$).
  4. Supervised Autoencoder (SAE) Integration: The authors integrate this projection as a constraint during the training of an autoencoder. This forces the encoder to select only the most relevant features (e.g., specific biomarkers) while discarding the rest.

Datasets

  • Synthetic Projection Benchmarks: Randomly generated matrices (up to 10,000 x 10,000) used to compare the raw speed of the projection algorithm against existing methods.
  • Artificial Biological Data: Generated using scikit-learn's make_classification to mimic high-dimensional biological datasets (1,000 samples, 10,000 features), where only a tiny fraction (64 features) are actually informative.
  • Real Biological Data: The paper mentions applications to RNA and protein biomarker identification, though the primary quantitative results in this specific paper focus on the synthetic/artificial benchmarks to prove the algorithm's efficiency.

Key Insights and Ideas

  • The "J" Factor: The algorithm's performance is tied to the resulting sparsity. The more sparse the target, the faster the algorithm runs. This is a perfect alignment of goals for researchers seeking high-efficiency models.
  • Structured Sparsity = Better Accuracy: Interestingly, the $\ell_{1,\infty}$ projection didn't just make the model smaller; it made it better. By forcing the model to ignore "noise" features, the accuracy on synthetic biological data improved significantly compared to a dense baseline.
  • Linear Behavior in Practice: Even when the resulting matrix is completely full (zero sparsity), the overhead of the algorithm's complexity constant ($J$) is only about 3% of the total matrix size, meaning it remains highly efficient across all use cases.

Key Results

  • Speedup: The proposed method was, on average, 2.2x faster than the previous state-of-the-art (the semi-smooth Newton method by Chu et al.) when integrated into a neural network training loop.
  • Sparsity vs. Accuracy: On artificial biological data, the method achieved 99.6% column sparsity (selecting only ~40 features out of 10,000) while increasing classification accuracy from 86.6% (baseline) to 92.77%.
  • Efficiency: The algorithm outperformed all existing methods (Chu et al., Quattoni et al., Bejar et al.) once the target sparsity exceeded 40%.

Limitations and Future Work

  • Low-Sparsity Overhead: If a user requires very low sparsity (keeping most of the weights), the overhead of managing multiple heaps makes the algorithm slightly slower than simpler methods, though it remains competitive.
  • Future Directions: The authors suggest extending this work to Convolutional Neural Networks (CNNs) for image coding and exploring bi-level optimization strategies to further refine feature selection.

Summary updated

Abstract

Looking for sparsity is nowadays crucial to speed up the training of large-scale neural networks. Projections onto the $\ell_{1}$ and $\ell_{1,\propto}$ 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 $\ell_{1,\infty}$ norm ball. Its worst-case time complexity is $\mathcal{O}(nm+J\log(nm))$ for a matrix in $\mathbb{R}^{n\times m}. J$ is a term that tends to 0 when the sparsity is high, and to $n\times m$ in the worst case. The algorithm is easy to implement and it is guaranteed to converge to the exact solution in finite time. Moreover, we propose to incorporate the $\ell_{1,\infty}$ ball projection while training an auto encoder 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 in both the biological and general cases of sparsity, our method is the fastest.
BibTeX
@inproceedings{perez2024near,
  author = {Guillaume Perez and Laurent Condat and Michel Barlaud},
  title = {{Near-Linear Time Projection onto the 𝓁1, ∞ Ball; Application to Sparse Autoencoders}},
  booktitle = {ICTAI},
  year = {2024},
  url = {https://openreview.net/forum?id=NhcDnHfzs1},
}
Figure