Learning Mixtures of Low-Rank Models

Abstract

We study the problem of learning mixtures of low-rank models, i.e. reconstructing multiple low-rank matrices from unlabelled linear measurements of each. This problem enriches two widely studied settings -- low-rank matrix sensing and mixed linear regression -- by bringing latent variables (i.e. unknown labels) and structural priors (i.e. low-rank structures) into consideration. To cope with the non-convexity issues arising from unlabelled heterogeneous data and low-complexity structure, we develop a three-stage meta-algorithm that is guaranteed to recover the unknown matrices with near-optimal sample and computational complexities under Gaussian designs. In addition, the proposed algorithm is provably stable against random noise. We complement the theoretical studies with empirical evidence that confirms the efficacy of our algorithm.

References in corpus (29)

• Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks
• Prototypical Networks for Few-shot Learning
• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Guaranteed Matrix Completion via Non-convex Factorization
• Global Optimality of Local Search for Low Rank Matrix Recovery
• Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
• No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
• Inference and Uncertainty Quantification for Noisy Matrix Completion
• Global Optimality in Low-rank Matrix Optimization
• Learning with Bad Training Data via Iterative Trimmed Loss Minimization
• A PAC-Bayesian bound for Lifelong Learning
• Non-convex Robust PCA
• The Benefit of Multitask Representation Learning
• The Non-convex Geometry of Low-rank Matrix Optimization
• Robust Regression via Hard Thresholding
• Alternating Minimization for Mixed Linear Regression
• Spectral Experts for Estimating Mixtures of Linear Regressions
• Provable Meta-Learning of Linear Representations
• Regularized EM Algorithms: A Unified Framework and Statistical Guarantees
• Solving a Mixture of Many Random Linear Equations by Tensor Decomposition and Alternating Minimization
• From Symmetry to Geometry: Tractable Nonconvex Problems
• Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent
• EM Converges for a Mixture of Many Linear Regressions
• Choosing the Sample with Lowest Loss makes SGD Robust
• A Convex Program for Mixed Linear Regression with a Recovery Guarantee for Well-Separated Data
• Mixture Matrix Completion
• Learning Entangled Single-Sample Distributions via Iterative Trimming
• Recovery of Sparse Signals from a Mixture of Linear Samples