More Like this

1. Critical points and convergence analysis of generative deep linear networks trained with Bures-Wasserstein loss

   Brechet, Pierre; Papagiannouli, Katerina; An, Jing; Montufar, Guido (July 2023, Proceedings of the 40th International Conference on Machine Learning)

   Krause, Andreas; Brunskill, Emma; Cho, Kyunghyun; Engelhardt, Barbara; Sabato, Sivan; Scarlett, Jonathan (Ed.)

   We consider a deep matrix factorization model of covariance matrices trained with the Bures-Wasserstein distance. While recent works have made advances in the study of the optimization problem for overparametrized low-rank matrix approximation, much emphasis has been placed on discriminative settings and the square loss. In contrast, our model considers another type of loss and connects with the generative setting. We characterize the critical points and minimizers of the Bures-Wasserstein distance over the space of rank-bounded matrices. The Hessian of this loss at low-rank matrices can theoretically blow up, which creates challenges to analyze convergence of gradient optimization methods. We establish convergence results for gradient flow using a smooth perturbative version of the loss as well as convergence results for finite step size gradient descent under certain assumptions on the initial weights. 

   more » « less
2. Towards Analysis of Covariance Descriptors via Bures–Wasserstein Distance

   https://doi.org/10.3390/math13132157  

   Huang, Huajun; Li, Yuexin; Lin, Shu-Chin; Yi, Yuyan; Zheng, Jingyi (July 2025, Mathematics)

   A brain–computer interface (BCI) provides a direct communication pathway between the human brain and external devices, enabling users to control them through thought. It records brain signals and classifies them into specific commands for external devices. Among various classifiers used in BCI, those directly classifying covariance matrices using Riemannian geometry find broad applications not only in BCI, but also in diverse fields such as computer vision, natural language processing, domain adaption, and remote sensing. However, the existing Riemannian-based methods exhibit limitations, including time-intensive computations, susceptibility to disturbances, and convergence challenges in scenarios involving high-dimensional matrices. In this paper, we tackle these issues by introducing the Bures–Wasserstein (BW) distance for covariance matrices analysis and demonstrating its advantages in BCI applications. Both theoretical and computational aspects of BW distance are investigated, along with algorithms for Fréchet Mean (or barycenter) estimation using BW distance. Extensive simulations are conducted to evaluate the effectiveness, efficiency, and robustness of the BW distance and barycenter. Additionally, by integrating BW barycenter into the Minimum Distance to Riemannian Mean classifier, we showcase its superior classification performance through evaluations on five real datasets. 

   more » « less
3. Robust Matrix Sensing in the Semi-Random Model

   Gao, Xing; Cheng, Yu (December 2023, Proceedings of the 37th Conference on Neural Information Processing Systems)

   Low-rank matrix recovery is a fundamental problem in machine learning with numerous applications. In practice, the problem can be solved by convex optimization namely nuclear norm minimization, or by non-convex optimization as it is well-known that for low-rank matrix problems like matrix sensing and matrix completion, all local optima of the natural non-convex objectives are also globally optimal under certain ideal assumptions. In this paper, we study new approaches for matrix sensing in a semi-random model where an adversary can add any number of arbitrary sensing matrices. More precisely, the problem is to recover a low-rank matrix $$X^\star$$ from linear measurements $$b_i = \langle A_i, X^\star \rangle$$, where an unknown subset of the sensing matrices satisfies the Restricted Isometry Property (RIP) and the rest of the $$A_i$$'s are chosen adversarially. It is known that in the semi-random model, existing non-convex objectives can have bad local optima. To fix this, we present a descent-style algorithm that provably recovers the ground-truth matrix $$X^\star$$. For the closely-related problem of semi-random matrix completion, prior work [CG18] showed that all bad local optima can be eliminated by reweighting the input data. However, the analogous approach for matrix sensing requires reweighting a set of matrices to satisfy RIP, which is a condition that is NP-hard to check. Instead, we build on the framework proposed in [KLL$^+$23] for semi-random sparse linear regression, where the algorithm in each iteration reweights the input based on the current solution, and then takes a weighted gradient step that is guaranteed to work well locally. Our analysis crucially exploits the connection between sparsity in vector problems and low-rankness in matrix problems, which may have other applications in obtaining robust algorithms for sparse and low-rank problems. 

   more » « less
4. A Unified Framework for Nonconvex Low-Rank plus Sparse Matrix Recovery

   Zhang, Xiao; Wang, Lingxiao Wang; Gu, Quanquan (April 2018, International Conference on Artificial Intelligence and Statistics)

   We propose a unified framework to solve general low-rank plus sparse matrix recovery problems based on matrix factorization, which covers a broad family of objective functions satisfying the restricted strong convexity and smoothness conditions. Based on projected gradient descent and the double thresholding operator, our proposed generic algorithm is guaranteed to converge to the unknown low-rank and sparse matrices at a locally linear rate, while matching the best-known robustness guarantee (i.e., tolerance for sparsity). At the core of our theory is a novel structural Lipschitz gradient condition for low-rank plus sparse matrices, which is essential for proving the linear convergence rate of our algorithm, and we believe is of independent interest to prove fast rates for general superposition-structured models. We illustrate the application of our framework through two concrete examples: robust matrix sensing and robust PCA. Empirical experiments corroborate our theory. 

   more » « less
5. On the Crucial Role of Initialization for Matrix Factorization

   Li, B; Zhang, L; Mokhtari, A; He, N (December 2024, https://doi.org/10.48550/arXiv.2410.18965)

   This work revisits the classical low-rank matrix factorization problem and unveils the critical role of initialization in shaping convergence rates for such nonconvex and nonsmooth optimization. We introduce Nystrom initialization, which significantly improves the global convergence of Scaled Gradient Descent (ScaledGD) in both symmetric and asymmetric matrix factorization tasks. Specifically, we prove that ScaledGD with Nystrom initialization achieves quadratic convergence in cases where only linear rates were previously known. Furthermore, we extend this initialization to low-rank adapters (LoRA) commonly used for finetuning foundation models. Our approach, NoRA, i.e., LoRA with Nystrom initialization, demonstrates superior performance across various downstream tasks and model scales, from 1B to 7B parameters, in large language and diffusion models. 

   more » « less