Minimizing FLOPs to Learn Efficient Sparse Representations

Biswajit Paria, Chih-Kuan Yeh, Ian En-Hsu Yen, Ning Xu, Pradeep Ravikumar, Barnabás Póczos

Overview

Instead of squeezing neural network embeddings into compact, low-dimensional dense vectors, this research proposes learning high-dimensional sparse representations. By introducing a novel regularization function that directly minimizes a continuous relaxation of floating-point operations (FLOPs), the authors achieve up to a 50x speedup in retrieval tasks with minimal loss in accuracy.

In modern AI, data such as images or text are often represented as "embeddings"—dense vectors in a high-dimensional space. To find the most similar item in a database of millions, systems perform a Nearest-Neighbor Search (NNS).

The industry standard for accelerating NNS relies on "compact" representations: either reducing the number of dimensions (e.g., PCA) or compressing the values (e.g., Product Quantization). However, shrinking the vector inherently shrinks its "representational capacity," often leading to lower accuracy.

This paper explores an alternative path: sparsity. If a vector is mostly zeros, systems can use an inverted index to skip the vast majority of calculations. The challenge, however, is that standard sparsity techniques (like $\ell_1$ regularization) do not guarantee faster retrieval. They often fail to ensure that non-zero entries are distributed efficiently across all dimensions, creating computational bottlenecks.

A FLOPs-Aware Approach to Sparsity

The authors introduce an end-to-end framework for learning distributed sparse embeddings that are optimized specifically for retrieval speed.

1. The FLOPs Insight

The core mathematical insight of the paper is that the number of operations required for retrieval decreases quadratically with sparsity—provided the non-zero entries are distributed uniformly across all dimensions. If all non-zeros cluster in just a few dimensions, the inverted index becomes congested, and the theoretical speedup vanishes.

2. The Continuous FLOPs Regularizer ($\tilde{\mathcal{F}}$)

Because the actual number of FLOPs is a discontinuous "step function" (which is notoriously difficult for neural networks to optimize via gradient descent), the authors derive a continuous relaxation. This novel regularizer—mathematically similar to the exclusive lasso—penalizes the squared $\ell_1$ norm of activations across a batch. This forces the model to not only be sparse but to actively spread its "active" neurons evenly across the entire embedding space.

3. The Inference Pipeline

At test time, the system performs a highly efficient two-stage retrieval:

  • Sparse Retrieval: A fast sweep using an inverted index (Sparse Matrix-Vector multiplication) to find the top-$k$ candidates.
  • Dense Re-ranking: A final, high-accuracy check on just those $k$ candidates using the original dense features.
Sparse Retrieval Pipeline

Key Insights and Performance

The authors evaluated their approach on large-scale, real-world benchmarks, including MegaFace (trained on MS-Celeb-1M) and CIFAR-100.

  • Sparsity $\neq$ Speed: The most critical takeaway is that simply having many zeros isn't enough. Uniformity across dimensions is what unlocks the quadratic speedup. The authors used a "sub-optimality ratio" to demonstrate that their method successfully balances non-zero entries, whereas standard $\ell_1$ regularization produces "clumpy" activations that slow down search.
  • Orthogonality by Default: Minimizing the proposed FLOPs regularizer is equivalent to promoting orthogonality between the absolute values of the embedding vectors. This naturally pushes different concepts into different dimensions, reducing interference and preserving representational capacity.
  • Massive Speedups: The proposed method achieved similar or better accuracy than baselines while being significantly faster. In optimal configurations, it reached a 50x speedup compared to exhaustive dense search, yielding a vastly superior speed-vs-accuracy trade-off compared to Sparse Deep Hashing (SDH) and standard $\ell_1$ penalties.

Limitations and Future Directions

While the theoretical and empirical results are strong, the authors note a few practical limitations. The paper uses FLOPs as a proxy for speed; however, modern hardware (like GPUs) is highly optimized for dense matrix multiplication via SIMD and cache hierarchies. Consequently, sparse operations can sometimes be slower in practice than their FLOP count suggests due to irregular memory access patterns.

Future work may involve adaptive methods that find the optimal sparsity level automatically (rather than relying on a fixed hyperparameter) and incorporating more complex hardware models—such as cache misses and parallelization constraints—directly into the loss function.

Summary updated

Abstract

Deep representation learning has become one of the most widely adopted approaches for visual search, recommendation, and identification. Retrieval of such representations from a large database is however computationally challenging. Approximate methods based on learning compact representations, have been widely explored for this problem, such as locality sensitive hashing, product quantization, and PCA. In this work, in contrast to learning compact representations, we propose to learn high dimensional and sparse representations that have similar representational capacity as dense embeddings while being more efficient due to sparse matrix multiplication operations which can be much faster than dense multiplication. Following the key insight that the number of operations decreases quadratically with the sparsity of embeddings provided the non-zero entries are distributed uniformly across dimensions, we propose a novel approach to learn such distributed sparse embeddings via the use of a carefully constructed regularization function that directly minimizes a continuous relaxation of the number of floating-point operations (FLOPs) incurred during retrieval. Our experiments show that our approach is competitive to the other baselines and yields a similar or better speed-vs-accuracy tradeoff on practical datasets.
BibTeX
@inproceedings{paria2020minimizing,
  author = {Biswajit Paria and Chih-Kuan Yeh and Ian En-Hsu Yen and Ning Xu and Pradeep Ravikumar and Barnabás Póczos},
  title = {{Minimizing FLOPs to Learn Efficient Sparse Representations}},
  booktitle = {International Conference on Learning Representations},
  year = {2020},
  url = {https://openreview.net/forum?id=BSfSUGxLhSU},
}
Figure