Minimizing FLOPs to Learn Efficient Sparse Representations
This work addresses efficiency in retrieval systems for applications like visual search and recommendation, offering an incremental improvement over existing compact representation methods.
The paper tackles the computational challenge of retrieving deep representations from large databases by learning high-dimensional sparse embeddings that maintain representational capacity while improving efficiency through sparse matrix multiplication. The proposed method, which minimizes a continuous relaxation of FLOPs via regularization, achieves competitive or better speed-accuracy trade-offs on practical datasets compared to baselines.
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.