Non-Convex Matrix Completion and Related Problems via Strong Duality

Maria-Florina Balcan, Yingyu Liang, Zhao Song, David P. Woodruff, Hongyang ZhangJMLR 2019 · OpenReview

TL;DR

This paper introduces a novel analytical framework to establish "strong duality" for a broad class of non-convex matrix factorization problems, including matrix completion and robust PCA. This means that these often intractable non-convex problems can be solved by finding the optimal solution to a related, but convex, "bi-dual" problem, achieving global optimality with nearly-optimal sample complexity.

What Problem Does This Paper Address?

Matrix factorization, the task of decomposing a matrix into a product of two or more matrices, is fundamental to many machine learning and data analysis tasks, such as recommendation systems and dimensionality reduction. While convex optimization problems are well-understood in terms of finding global optima, many practical matrix factorization problems are inherently non-convex. This non-convexity leads to challenges in guaranteeing that algorithms find the true global optimum, often getting stuck in local minima or saddle points. Furthermore, even when algorithms can recover the underlying matrix (e.g., in matrix completion), the theoretical understanding of why certain techniques work and the conditions under which they achieve global optimality have been limited for non-convex settings. This paper aims to bridge this gap by providing a unified framework to analyze non-convex matrix factorization problems and demonstrate strong duality, which is crucial for guaranteeing global optimality.

Methods

The core contribution is a novel analytical framework that establishes "strong duality" for non-convex matrix factorization problems. Strong duality, in this context, means that the optimal value of the original non-convex problem is equal to the optimal value of its "bi-dual" problem. Crucially, the bi-dual problem is shown to be convex. The authors achieve this by:

  • Developing a Unified Framework: They propose a general framework that applies to various matrix factorization problems formulated as minimizing a function of the product of two matrices (e.g., $H(AB)$) plus a regularization term.
  • Introducing Dual Certificates: The framework relies on the existence of a "dual certificate," which is a specific matrix that helps bridge the gap between the primal non-convex problem and its convex bi-dual.
  • Leveraging Geometric Analysis: The analysis employs geometric insights into the structure of the problem spaces and the properties of different norms (like the nuclear norm and the $r^*$-norm).
  • Applying to Specific Problems: The framework is then applied to two key problems:
  • Matrix Completion: Recovering a low-rank matrix from a subset of its entries.
  • Robust Principal Component Analysis (PCA): Recovering a low-rank matrix from a sum of the low-rank matrix and a sparse "corruption" matrix.

The novelty lies in extending the concept of strong duality, typically associated with convex optimization, to a significant class of non-convex problems, thereby providing a theoretical guarantee for global optimality.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and algorithmic frameworks, with experiments conducted on synthetic data generated according to specific problem settings (e.g., random matrices for matrix completion) and a real-world dataset (Hopkins 155 for matrix completion).

Key Insights and Ideas

  • Strong Duality for Non-Convexity: The most significant insight is demonstrating that strong duality, a powerful tool for guaranteeing global optimality, can hold for non-convex matrix factorization problems under specific "dual conditions." This is a major theoretical advance, as strong duality was previously understood primarily in convex settings.
  • The Power of the Bi-Dual: By showing that the bi-dual problem is convex, the authors provide a practical pathway to solving complex non-convex problems. Instead of directly tackling the hard non-convex optimization, one can solve its convex counterpart.
  • The Role of Randomness: The paper highlights that the existence of the crucial "dual certificate" often relies on randomness in the sampling of observations (e.g., in matrix completion). This "blessing of randomness" is essential for achieving strong duality and exact recovery in many practical scenarios.
  • Unified Framework for Diverse Problems: The proposed analytical framework is general enough to apply to a range of matrix factorization problems, suggesting a common underlying structure and solution approach.
  • Nuclear Norm vs. $r^*$-Norm: The work provides new insights into why nuclear norm minimization is effective for matrix completion, connecting it to the strong duality framework and the $r^*$-norm.

Key Results

  • Theoretical Guarantees for Strong Duality: The paper establishes theoretical conditions under which strong duality holds for general non-convex matrix factorization problems of the form $H(AB) + \text{regularizer}$.
  • Matrix Completion: The framework leads to algorithms for matrix completion that achieve exact recovery with nearly-optimal sample complexity, matching the best known results.
  • Robust PCA: Similarly, for robust PCA, the framework yields algorithms with nearly-optimal sample complexity for exact recovery.
  • Computational Efficiency: The ability to solve the convex bi-dual problem implies that these non-convex problems can be solved efficiently, often in polynomial time.
  • Lower Bounds: The paper also provides computational lower bounds, showing that achieving near-optimal solutions for these problems is inherently hard for deterministic algorithms, underscoring the importance of the proposed techniques.

Limitations and Future Work

  • Dual Conditions: The strong duality results are contingent on satisfying specific "dual conditions." While these conditions are shown to hold for matrix completion and robust PCA under randomness, their applicability to other non-convex problems might require further investigation.
  • Generalization to Other Problems: While the framework is presented as broadly applicable, its explicit application to a wider range of non-convex optimization problems (e.g., dictionary learning, deep neural networks) is left for future work.
  • Practical Performance: While theoretical guarantees are provided, the practical performance and scalability of the proposed methods compared to existing heuristics are not the primary focus, though experimental results on synthetic and real data are presented.
  • Assumptions on Data Distribution: The analysis for matrix completion and robust PCA often relies on assumptions about the distribution of observed entries or the support of sparse components (e.g., uniform sampling). Relaxing these assumptions could be a direction for future research.

Summary updated

Abstract

This work studies the strong duality of non-convex matrix factorization problems: we show that under certain dual conditions, these problems and the dual have the same optimum. This has been well understood for convex optimization, but little was known for non-convex problems. We propose a novel analytical framework and prove that under certain dual conditions, the optimal solution of the matrix factorization program is the same as that of its bi-dual and thus the global optimality of the non-convex program can be achieved by solving its bi-dual which is convex. These dual conditions are satisfied by a wide class of matrix factorization problems, although matrix factorization is hard to solve in full generality. This analytical framework may be of independent interest to non-convex optimization more broadly. We apply our framework to two prototypical matrix factorization problems: matrix completion and robust Principal Component Analysis. These are examples of efficiently recovering a hidden matrix given limited reliable observations. Our framework shows that exact recoverability and strong duality hold with nearly-optimal sample complexity for the two problems.
BibTeX
@article{balcan2019non,
  author = {Maria-Florina Balcan and Yingyu Liang and Zhao Song and David P. Woodruff and Hongyang Zhang},
  title = {{Non-Convex Matrix Completion and Related Problems via Strong Duality}},
  journal = {J. Mach. Learn. Res.},
  year = {2019},
  url = {https://openreview.net/forum?id=bFq7_bgvf-},
}
Figure