Minimizing FLOPs to Learn Efficient Sparse Representations

• URL: http://arxiv.org/abs/2004.05665v1
• Date: Sun, 12 Apr 2020 18:09:02 GMT
• Title: Minimizing FLOPs to Learn Efficient Sparse Representations
• Authors: Biswajit Paria, Chih-Kuan Yeh, Ian E.H. Yen, Ning Xu, Pradeep Ravikumar, Barnab\'as P\'oczos
• Abstract summary: We learn high dimensional and sparse representations that have similar representational capacity as dense embeddings. Our approach is competitive to the other baselines and yields a similar or better speed-vs-accuracy tradeoff on practical datasets.
• Score: 36.24540913526988
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Efficient Fairness-Performance Pareto Front Computation [51.558848491038916]
  We show that optimal fair representations possess several useful structural properties. We then show that these approxing problems can be solved efficiently via concave programming methods.
  arXiv  Detail & Related papers  (2024-09-26T08:46:48Z)
• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  Clustered multi-task compressive sensing is a hierarchical model that solves multiple compressive sensing tasks. The existing inference algorithm for this model is computationally expensive and does not scale well in high dimensions. We propose a new algorithm that substantially accelerates model inference by avoiding the need to explicitly compute these covariance matrices.
  arXiv  Detail & Related papers  (2023-09-30T15:57:14Z)
• Enhancing Representation Learning on High-Dimensional, Small-Size Tabular Data: A Divide and Conquer Method with Ensembled VAEs [7.923088041693465]
  We present an ensemble of lightweight VAEs to learn posteriors over subsets of the feature-space, which get aggregated into a joint posterior in a novel divide-and-conquer approach. We show that our approach is robust to partial features at inference, exhibiting little performance degradation even with most features missing.
  arXiv  Detail & Related papers  (2023-06-27T17:55:31Z)
• Provably Efficient Representation Learning with Tractable Planning in Low-Rank POMDP [81.00800920928621]
  We study representation learning in partially observable Markov Decision Processes (POMDPs) We first present an algorithm for decodable POMDPs that combines maximum likelihood estimation (MLE) and optimism in the face of uncertainty (OFU) We then show how to adapt this algorithm to also work in the broader class of $gamma$-observable POMDPs.
  arXiv  Detail & Related papers  (2023-06-21T16:04:03Z)
• Federated Representation Learning via Maximal Coding Rate Reduction [109.26332878050374]
  We propose a methodology to learn low-dimensional representations from a dataset that is distributed among several clients. Our proposed method, which we refer to as FLOW, utilizes MCR2 as the objective of choice, hence resulting in representations that are both between-class discriminative and within-class compressible.
  arXiv  Detail & Related papers  (2022-10-01T15:43:51Z)
• Learning Optical Flow from a Few Matches [67.83633948984954]
  We show that the dense correlation volume representation is redundant and accurate flow estimation can be achieved with only a fraction of elements in it. Experiments show that our method can reduce computational cost and memory use significantly, while maintaining high accuracy.
  arXiv  Detail & Related papers  (2021-04-05T21:44:00Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.