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)
• Exponentially Convergent Algorithms for Supervised Matrix Factorization [2.1485350418225244]
  Supervised factorization (SMF) is a machine learning method that converges extraction and classification tasks. Our paper provides a novel framework that 'lifts' SMF as a low-rank estimation problem in a combined factor space estimation.
  arXiv  Detail & Related papers  (2023-11-18T23:24:02Z)
• Accelerated Fuzzy C-Means Clustering Based on New Affinity Filtering and Membership Scaling [74.85538972921917]
  Fuzzy C-Means (FCM) is a widely used clustering method. FCM has low efficiency in the mid-to-late stage of the clustering process. FCM based on new affinity filtering and membership scaling (AMFCM) is proposed to accelerate the whole convergence process.
  arXiv  Detail & Related papers  (2023-02-14T14:20:31Z)
• AdaSfM: From Coarse Global to Fine Incremental Adaptive Structure from Motion [48.835456049755166]
  AdaSfM is a coarse-to-fine adaptive SfM approach that is scalable to large-scale and challenging datasets. Our approach first does a coarse global SfM which improves the reliability of the view graph by leveraging measurements from low-cost sensors. Our approach uses a threshold-adaptive strategy to align all local reconstructions to the coordinate frame of global SfM.
  arXiv  Detail & Related papers  (2023-01-28T09:06:50Z)
• 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)
• Generalized Federated Learning via Sharpness Aware Minimization [22.294290071999736]
  We propose a general, effective algorithm, textttFedSAM, based on Sharpness Aware Minimization (SAM) local, and develop a momentum FL algorithm to bridge local and global models. Empirically, our proposed algorithms substantially outperform existing FL studies and significantly decrease the learning deviation.
  arXiv  Detail & Related papers  (2022-06-06T13:54:41Z)
• Distributionally Robust Federated Averaging [19.875176871167966]
  We present communication efficient distributed algorithms for robust learning periodic averaging with adaptive sampling. We give corroborating experimental evidence for our theoretical results in federated learning settings.
  arXiv  Detail & Related papers  (2021-02-25T03:32:09Z)
• Mime: Mimicking Centralized Stochastic Algorithms in Federated Learning [102.26119328920547]
  Federated learning (FL) is a challenging setting for optimization due to the heterogeneity of the data across different clients. We propose a general algorithmic framework, Mime, which mitigates client drift and adapts arbitrary centralized optimization algorithms.
  arXiv  Detail & Related papers  (2020-08-08T21:55:07Z)
• Shonan Rotation Averaging: Global Optimality by Surfing $SO(p)^n$ [26.686173666277725]
  Shonan Rotation Averaging is guaranteed to recover globally optimal solutions under mild assumptions on the measurement noise. Our method employs semidefinite relaxation in order to recover provably globally optimal solutions of the rotation averaging problem.
  arXiv  Detail & Related papers  (2020-08-06T16:08:23Z)
• 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)

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.