Escaping Spurious Local Minima of Low-Rank Matrix Factorization Through Convex Lifting

• URL: http://arxiv.org/abs/2204.14067v1
• Date: Fri, 29 Apr 2022 13:04:36 GMT
• Title: Escaping Spurious Local Minima of Low-Rank Matrix Factorization Through Convex Lifting
• Authors: Ching-pei Lee, Ling Liang, Tianyun Tang, Kim-Chuan Toh
• Abstract summary: This work proposes a global rapid solver for non low-rank matrix factorization (MF) problems that we name MF-Global. Through convex steps, our method efficiently escapes saddle and spurious local minima ubiquitous in noisy real-world data. We show that MF-Global can indeed effectively escapes local solutions at which existing MF approaches stuck, and is magnitudes faster than state-of-the-art algorithms for the lifted convex form.
• Score: 10.76492224896965
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This work proposes a rapid global solver for nonconvex low-rank matrix factorization (MF) problems that we name MF-Global. Through convex lifting steps, our method efficiently escapes saddle points and spurious local minima ubiquitous in noisy real-world data, and is guaranteed to always converge to the global optima. Moreover, the proposed approach adaptively adjusts the rank for the factorization and provably identifies the optimal rank for MF automatically in the course of optimization through tools of manifold identification, and thus it also spends significantly less time on parameter tuning than existing MF methods, which require an exhaustive search for this optimal rank. On the other hand, when compared to methods for solving the lifted convex form only, MF-Global leads to significantly faster convergence and much shorter running time. Experiments on real-world large-scale recommendation system problems confirm that MF-Global can indeed effectively escapes spurious local solutions at which existing MF approaches stuck, and is magnitudes faster than state-of-the-art algorithms for the lifted convex form.

Related papers

• A Stochastic Approach to Bi-Level Optimization for Hyperparameter Optimization and Meta Learning [74.80956524812714]
  We tackle the general differentiable meta learning problem that is ubiquitous in modern deep learning. These problems are often formalized as Bi-Level optimizations (BLO) We introduce a novel perspective by turning a given BLO problem into a ii optimization, where the inner loss function becomes a smooth distribution, and the outer loss becomes an expected loss over the inner distribution.
  arXiv  Detail & Related papers  (2024-10-14T12:10:06Z)
• Tailed Low-Rank Matrix Factorization for Similarity Matrix Completion [14.542166904874147]
  Similarity Completion Matrix serves as a fundamental tool at the core of numerous machinelearning tasks. To address this issue, Similarity Matrix Theoretical (SMC) methods have been proposed, but they suffer complexity. We present two novel, scalable, and effective algorithms, which investigate the PSD property to guide the estimation process and incorporate non low-rank regularizer to ensure the low-rank solution.
  arXiv  Detail & Related papers  (2024-09-29T04:27:23Z)
• Block Majorization Minimization with Extrapolation and Application to $\beta$-NMF [17.97403029273243]
  We propose a Block Majorization Minimization method with Extrapolation (BMMe) for solving a class of multi- optimization problems. We show that block majorization parameters of BMMe can be reformulated as a block mirror method with the Bregman divergence adaptively updated. We empirically illustrate the significant acceleration BM for $beta$NMF through extensive experiments.
  arXiv  Detail & Related papers  (2024-01-12T15:52:02Z)
• On the Global Solution of Soft k-Means [159.23423824953412]
  This paper presents an algorithm to solve the Soft k-Means problem globally. A new model, named Minimal Volume Soft kMeans (MVSkM), is proposed to address solutions non-uniqueness issue.
  arXiv  Detail & Related papers  (2022-12-07T12:06:55Z)
• Optimization of Annealed Importance Sampling Hyperparameters [77.34726150561087]
  Annealed Importance Sampling (AIS) is a popular algorithm used to estimates the intractable marginal likelihood of deep generative models. We present a parameteric AIS process with flexible intermediary distributions and optimize the bridging distributions to use fewer number of steps for sampling. We assess the performance of our optimized AIS for marginal likelihood estimation of deep generative models and compare it to other estimators.
  arXiv  Detail & Related papers  (2022-09-27T07:58:25Z)
• Factorization Approach for Low-complexity Matrix Completion Problems: Exponential Number of Spurious Solutions and Failure of Gradient Methods [18.16094563534453]
  It is well-known that the Burer-Monteiro (B-M) factorization approach can efficiently solve low-rank matrix optimization problems under the RIP condition. It is natural to ask whether B-M factorization-based methods can succeed on any low-rank matrix optimization problems with a low information-theoretic complexity.
  arXiv  Detail & Related papers  (2021-10-19T21:52:14Z)
• Fast Batch Nuclear-norm Maximization and Minimization for Robust Domain Adaptation [154.2195491708548]
  We study the prediction discriminability and diversity by studying the structure of the classification output matrix of a randomly selected data batch. We propose Batch Nuclear-norm Maximization and Minimization, which performs nuclear-norm on the target output matrix to enhance the target prediction ability. Experiments show that our method could boost the adaptation accuracy and robustness under three typical domain adaptation scenarios.
  arXiv  Detail & Related papers  (2021-07-13T15:08:32Z)
• Rotation Coordinate Descent for Fast Globally Optimal Rotation Averaging [47.3713707521106]
  We present a fast algorithm that achieves global optimality called rotation coordinate descent (RCD) Unlike block coordinate descent (BCD) which solves SDP by updating the semidefinite matrix in a row-by-row fashion, RCD directly maintains and updates all valid rotations throughout the iterations. We mathematically prove the convergence of our algorithm and empirically show its superior efficiency over state-of-the-art global methods.
  arXiv  Detail & Related papers  (2021-03-15T11:31:34Z)
• Community detection using fast low-cardinality semidefinite programming [94.4878715085334]
  We propose a new low-cardinality algorithm that generalizes the local update to maximize a semidefinite relaxation derived from Leiden-k-cut. This proposed algorithm is scalable, outperforms state-of-the-art algorithms, and outperforms in real-world time with little additional cost.
  arXiv  Detail & Related papers  (2020-12-04T15:46:30Z)
• 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)
• Low-Rank Factorization for Rank Minimization with Nonconvex Regularizers [0.0]
  Minimizing the convex relaxation to the nuclear norm is of interest in recommender systems and robust principal component analysis. We develop efficient algorithms for the rank factorization of nuclear programs put forth by Buriro and nucleariro.
  arXiv  Detail & Related papers  (2020-06-13T19:04:37Z)

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.