A High-Performance Implementation of Bayesian Matrix Factorization with Limited Communication

• URL: http://arxiv.org/abs/2004.02561v2
• Date: Tue, 14 Apr 2020 07:41:19 GMT
• Title: A High-Performance Implementation of Bayesian Matrix Factorization with Limited Communication
• Authors: Tom Vander Aa, Xiangju Qin, Paul Blomstedt, Roel Wuyts, Wilfried Verachtert, Samuel Kaski
• Abstract summary: Matrix factorization algorithms can quantify uncertainty in their predictions and avoid over-fitting. They have not been widely used on large-scale data because of their prohibitive computational cost. We show that the state-of-the-art of both approaches to scalability can be combined.
• Score: 10.639704288188767
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Matrix factorization is a very common machine learning technique in recommender systems. Bayesian Matrix Factorization (BMF) algorithms would be attractive because of their ability to quantify uncertainty in their predictions and avoid over-fitting, combined with high prediction accuracy. However, they have not been widely used on large-scale data because of their prohibitive computational cost. In recent work, efforts have been made to reduce the cost, both by improving the scalability of the BMF algorithm as well as its implementation, but so far mainly separately. In this paper we show that the state-of-the-art of both approaches to scalability can be combined. We combine the recent highly-scalable Posterior Propagation algorithm for BMF, which parallelizes computation of blocks of the matrix, with a distributed BMF implementation that users asynchronous communication within each block. We show that the combination of the two methods gives substantial improvements in the scalability of BMF on web-scale datasets, when the goal is to reduce the wall-clock time.

Related papers

• Federated Binary Matrix Factorization using Proximal Optimization [43.01276597844757]
  In this paper, we adapt a state-of-the-art binary matrix factorization relaxation to BMF. We show that our algorithm outperforms, in terms of quality and efficacy, federation schemes of state-of-the-art BMF methods on a diverse set of real-world and synthetic data.
  arXiv  Detail & Related papers  (2024-07-01T20:10:24Z)
• Accelerating Matrix Factorization by Dynamic Pruning for Fast Recommendation [0.49399484784577985]
  Matrix factorization (MF) is a widely used collaborative filtering algorithm for recommendation systems (RSs) With the dramatically increased number of users/items in current RSs, the computational complexity for training a MF model largely increases. We propose algorithmic methods to accelerate MF, without inducing any additional computational resources.
  arXiv  Detail & Related papers  (2024-03-18T16:27:33Z)
• DB-LLM: Accurate Dual-Binarization for Efficient LLMs [83.70686728471547]
  Large language models (LLMs) have significantly advanced the field of natural language processing. Existing ultra-low-bit quantization always causes severe accuracy drops. We propose a novel Dual-Binarization method for LLMs, namely DB-LLM.
  arXiv  Detail & Related papers  (2024-02-19T09:04:30Z)
• Statistically Optimal K-means Clustering via Nonnegative Low-rank Semidefinite Programming [25.210724274471914]
  $K$-means clustering is a widely used machine learning method for identifying patterns in large datasets. In this paper, we consider an NMF-like algorithm that solves nonnegative low-rank $K$-means factorization problem. Our algorithm achieves significantly smaller mis-clustering errors compared to the existing state-the-art while maintaining scalability.
  arXiv  Detail & Related papers  (2023-05-29T00:39:55Z)
• Unitary Approximate Message Passing for Matrix Factorization [90.84906091118084]
  We consider matrix factorization (MF) with certain constraints, which finds wide applications in various areas. We develop a Bayesian approach to MF with an efficient message passing implementation, called UAMPMF. We show that UAMPMF significantly outperforms state-of-the-art algorithms in terms of recovery accuracy, robustness and computational complexity.
  arXiv  Detail & Related papers  (2022-07-31T12:09:32Z)
• Asymmetric Scalable Cross-modal Hashing [51.309905690367835]
  Cross-modal hashing is a successful method to solve large-scale multimedia retrieval issue. We propose a novel Asymmetric Scalable Cross-Modal Hashing (ASCMH) to address these issues. Our ASCMH outperforms the state-of-the-art cross-modal hashing methods in terms of accuracy and efficiency.
  arXiv  Detail & Related papers  (2022-07-26T04:38:47Z)
• Asynchronous Parallel Incremental Block-Coordinate Descent for Decentralized Machine Learning [55.198301429316125]
  Machine learning (ML) is a key technique for big-data-driven modelling and analysis of massive Internet of Things (IoT) based intelligent and ubiquitous computing. For fast-increasing applications and data amounts, distributed learning is a promising emerging paradigm since it is often impractical or inefficient to share/aggregate data. This paper studies the problem of training an ML model over decentralized systems, where data are distributed over many user devices.
  arXiv  Detail & Related papers  (2022-02-07T15:04:15Z)
• An Adaptive Memory Multi-Batch L-BFGS Algorithm for Neural Network Training [0.951828574518325]
  A limited memory version of the BFGS algorithm has been receiving increasing attention in recent years for large neural network training problems. We propose a multi-batch L-BFGS algorithm, namely MB-AM, that gradually increases its trust in the curvature information.
  arXiv  Detail & Related papers  (2020-12-14T11:40:41Z)
• Efficient semidefinite-programming-based inference for binary and multi-class MRFs [83.09715052229782]
  We propose an efficient method for computing the partition function or MAP estimate in a pairwise MRF. We extend semidefinite relaxations from the typical binary MRF to the full multi-class setting, and develop a compact semidefinite relaxation that can again be solved efficiently using the solver.
  arXiv  Detail & Related papers  (2020-12-04T15:36:29Z)
• Positive Semidefinite Matrix Factorization: A Connection with Phase Retrieval and Affine Rank Minimization [71.57324258813674]
  We show that PSDMF algorithms can be designed based on phase retrieval (PR) and affine rank minimization (ARM) algorithms. Motivated by this idea, we introduce a new family of PSDMF algorithms based on iterative hard thresholding (IHT)
  arXiv  Detail & Related papers  (2020-07-24T06:10:19Z)
• Federated Matrix Factorization: Algorithm Design and Application to Data Clustering [18.917444528804463]
  Recent demands on data privacy have called for federated learning (FL) as a new distributed learning paradigm in massive and heterogeneous networks. We propose two new FedMF algorithms, namely FedMAvg and FedMGS, based on the model averaging and gradient sharing principles.
  arXiv  Detail & Related papers  (2020-02-12T11:48:54Z)

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.