Accelerating Block Coordinate Descent for Nonnegative Tensor Factorization

• URL: http://arxiv.org/abs/2001.04321v2
• Date: Fri, 20 Nov 2020 11:54:54 GMT
• Title: Accelerating Block Coordinate Descent for Nonnegative Tensor Factorization
• Authors: Andersen Man Shun Ang, Jeremy E. Cohen, Nicolas Gillis, Le Thi Khanh Hien
• Abstract summary: This paper is concerned with improving the empirical convergence speed of block descent algorithms for approximate nonnegative factorization (NTF) We propose an extrapolation strategy in-between block updates and restarts (HER) HER significantly accelerates the empirical convergence speed of most existing blockcoordinate algorithms for dense NTF, in particular for challenging computational scenarios, while requiring a negligible additional computational budget.
• Score: 22.2289974576617
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper is concerned with improving the empirical convergence speed of block-coordinate descent algorithms for approximate nonnegative tensor factorization (NTF). We propose an extrapolation strategy in-between block updates, referred to as heuristic extrapolation with restarts (HER). HER significantly accelerates the empirical convergence speed of most existing block-coordinate algorithms for dense NTF, in particular for challenging computational scenarios, while requiring a negligible additional computational budget.

Related papers

• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  We exploit between first-order algorithms for constrained optimization and non-smooth systems to design a new class of accelerated first-order algorithms. An important property of these algorithms is that constraints are expressed in terms of velocities instead of sparse variables.
  arXiv  Detail & Related papers  (2023-02-01T08:50:48Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  Efficient computation of the optimal transport distance between two distributions serves as an algorithm that empowers various applications. This paper develops a scalable first-order optimization-based method that computes optimal transport to within $varepsilon$ additive accuracy.
  arXiv  Detail & Related papers  (2023-01-30T15:46:39Z)
• Distributed stochastic optimization with large delays [59.95552973784946]
  One of the most widely used methods for solving large-scale optimization problems is distributed asynchronous gradient descent (DASGD) We show that DASGD converges to a global optimal implementation model under same delay assumptions.
  arXiv  Detail & Related papers  (2021-07-06T21:59:49Z)
• New Riemannian preconditioned algorithms for tensor completion via polyadic decomposition [10.620193291237262]
  These algorithms exploit a non-Euclidean metric on the product space of the factor matrices of the low-rank tensor in the polyadic decomposition form. We prove that the proposed gradient descent algorithm globally converges to a stationary point of the tensor completion problem. Numerical results on synthetic and real-world data suggest that the proposed algorithms are more efficient in memory and time compared to state-of-the-art algorithms.
  arXiv  Detail & Related papers  (2021-01-26T22:11:06Z)
• Fast Convergence Algorithm for Analog Federated Learning [30.399830943617772]
  We propose an AirComp-based FedSplit algorithm for efficient analog federated learning over wireless channels. We prove that the proposed algorithm linearly converges to the optimal solutions under the assumption that the objective function is strongly convex and smooth. Our algorithm is theoretically and experimentally verified to be much more robust to the ill-conditioned problems with faster convergence compared with other benchmark FL algorithms.
  arXiv  Detail & Related papers  (2020-10-30T10:59:49Z)
• An Accelerated DFO Algorithm for Finite-sum Convex Functions [0.0]
  Derivative-free optimizationDFO) has recently gained a lot momentum in machine learning. In this paper, we exploit the finite-sum objective functions in order to design accessible DFO algorithms.
  arXiv  Detail & Related papers  (2020-07-07T09:57:31Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  Maximum a posteriori (MAP) inference in discrete-valued random fields is a fundamental problem in machine learning. Due to the difficulty of this problem, linear programming (LP) relaxations are commonly used to derive specialized message passing algorithms. We present randomized methods for accelerating these algorithms by leveraging techniques that underlie classical accelerated gradient.
  arXiv  Detail & Related papers  (2020-07-01T18:43:32Z)
• IDEAL: Inexact DEcentralized Accelerated Augmented Lagrangian Method [64.15649345392822]
  We introduce a framework for designing primal methods under the decentralized optimization setting where local functions are smooth and strongly convex. Our approach consists of approximately solving a sequence of sub-problems induced by the accelerated augmented Lagrangian method. When coupled with accelerated gradient descent, our framework yields a novel primal algorithm whose convergence rate is optimal and matched by recently derived lower bounds.
  arXiv  Detail & Related papers  (2020-06-11T18:49:06Z)
• Age-Based Coded Computation for Bias Reduction in Distributed Learning [57.9123881133818]
  Coded computation can be used to speed up distributed learning in the presence of straggling workers. Partial recovery of the gradient vector can further reduce the computation time at each iteration. Estimator bias will be particularly prevalent when the straggling behavior is correlated over time.
  arXiv  Detail & Related papers  (2020-06-02T17:51:11Z)
• Efficient Nonnegative Tensor Factorization via Saturating Coordinate Descent [16.466065626950424]
  We propose a novel fast and efficient NTF algorithm using the element selection approach. Empirical analysis reveals that the proposed algorithm is scalable in terms of tensor size, density, and rank.
  arXiv  Detail & Related papers  (2020-03-07T12:51:52Z)
• Columnwise Element Selection for Computationally Efficient Nonnegative Coupled Matrix Tensor Factorization [16.466065626950424]
  Nonnegative CMTF (N-CMTF) has been employed in many applications for identifying latent patterns, prediction, and recommendation. In this paper, a computationally efficient N-CMTF factorization algorithm is presented based on the column-wise element selection, preventing frequent gradient updates.
  arXiv  Detail & Related papers  (2020-03-07T03:34:53Z)

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.