On Learning Expand-and-Sparsify Representations

Overview & Synopsis

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.