Learning small sparse codes matches dense layers in many tasks
On Learning Expand-and-Sparsify Representations
Machine Learning
Summary
The paper looks at a way to turn input data into a higher-dimensional form and keep only the biggest parts, making it easier to find important features. The authors studied if learning this transformation helps, compared to just using a random one. They found that learning helps a lot when this new space isn't too large, making the method more practical. Also, with learning, keeping a small portion of the features works just as well as common methods that keep everything. They tested these ideas on many classification and regression tasks.
What this means in practice
- •For machine learning engineers: Design efficient neural layers that use learned sparse expansions to reduce computation while maintaining accuracy.
- •For data compression teams: Develop sparse binary codes from learned expansions to compress data without accuracy loss.
Authors
Alireza Asghari, Parikshit Ram, Kaushik Sinha
Abstract
Expand-and-sparsify ($\texttt{EaS}$) representations lift an input to a much higher dimension through a linear map and keep only the $k$ largest coordinates. Existing theory builds that map at random and needs the expanded dimension to grow exponentially in the input dimension, which puts the construction out of practical reach. We ask what is gained by learning the map by gradient descent instead, and how that gain depends on how wide the expansion is. We sweep $73$ OpenML classification tasks and $48$ regression tasks under a protocol that holds the datasets, expanded dimensions, sparsity levels and splits fixed across every method, and we summarise each comparison by a median over datasets and a Wilcoxon signed rank test. We report four findings. First, learning the expansion helps most when the expansion is narrowest, and its advantage over a random map decays to nothing by the widest expansions we run, so a learned $\texttt{EaS}$ layer can be made small. Second, with the map learned, a top-$k$ representation that keeps at most a tenth of its coordinates is indistinguishable from a dense $\texttt{ReLU}$ layer of the same expanded dimension at every expansion factor we test, while GELU and SiLU are not. Third, when the representation is forced to be binary the sparse code is the better of the two, and the reason is that binarization costs it nothing while it costs the dense layer accuracy. Fourth, how sparse the representation can be is governed by how wide it is: the sparsity level that is free rises as the expansion grows, so there is no fixed limit on how sparse it can be. The regression tasks reproduce the first finding and qualify the second and third.