Publications and Preprints
Fast and Accurate Estimation of Low-Rank Matrices from Noisy Measurements via Preconditioned Non-Convex Gradient Descent
Proceedings of The 27th International Conference on Artificial Intelligence and Statistics (AISTATS 2024)
Abstract
Non-convex gradient descent is a common approach for estimating a low-rank ground truth matrix from noisy measurements, because it has per-iteration costs as low as time, and is in theory capable of converging to a minimax optimal estimate. However, the practitioner is often constrained to just tens to hundreds of iterations, and the slow and/or inconsistent convergence of non-convex gradient descent can prevent a high-quality estimate from being obtained. Recently, the technique of preconditioning was shown to be highly effective at accelerating the local convergence of non-convex gradient descent when the measurements are noiseless. In this paper, we describe how preconditioning should be done for noisy measurements to accelerate local convergence to minimax optimality. For the symmetric matrix sensing problem, our proposed preconditioned method is guaranteed to locally converge to minimax error at a linear rate that is immune to ill-conditioning and/or over-parameterization. Using our proposed preconditioned method, we perform a 60 megapixel medical image denoising task, and observe significantly reduced noise levels compared to previous approaches.
Simple Alternating Minimization Provably Solves Complete Dictionary Learning
SIAM Journal on Mathematics of Data Science (SIMODS 2025)
Abstract
We study the complete dictionary learning problem, where the goal is to recover an unknown dictionary matrix from linear measurements. We show that a simple alternating minimization algorithm provably recovers the true dictionary with high probability, under mild assumptions on the measurement model. Our analysis provides a theoretical justification for the empirical success of alternating minimization in dictionary learning applications.
Preconditioned Gradient Descent for Overparameterized Nonconvex Burer-Monteiro Factorization with Global Optimality Certification
Journal of Machine Learning Research (JMLR 2023)
Abstract
We study the Burer-Monteiro factorization approach for solving semidefinite programs (SDPs). We propose a preconditioned gradient descent algorithm that efficiently finds a global optimum of the nonconvex problem, with a certificate of global optimality. Our approach combines the computational efficiency of nonconvex optimization with the theoretical guarantees of convex optimization.
Accelerating SGD for Highly Ill-Conditioned Huge-Scale Online Matrix Completion
Advances in Neural Information Processing Systems (NeurIPS 2022)
Abstract
We propose an accelerated stochastic gradient descent algorithm for online matrix completion problems with highly ill-conditioned matrices. Our algorithm achieves significant speedups over standard SGD by using a novel preconditioner that adapts to the problem structure. We provide theoretical guarantees and empirical evaluations on large-scale recommendation systems.
Preconditioned Gradient Descent for Over-parameterized Nonconvex Matrix Factorization
Advances in Neural Information Processing Systems (NeurIPS 2021)
Abstract
We study the problem of recovering a low-rank matrix from linear measurements using nonconvex matrix factorization. We propose a preconditioned gradient descent algorithm that efficiently finds a global optimum of the nonconvex problem. Our approach provides both computational efficiency and theoretical guarantees for this important class of problems.
How Many Samples is a Good Initial Point Worth in Low-rank Matrix Recovery?
Spotlight Presentation (Top 4%). Advances in Neural Information Processing Systems (NeurIPS 2020)
Abstract
We study the sample complexity of low-rank matrix recovery with a good initialization. We show that with a sufficiently accurate initial point, the sample complexity can be significantly reduced compared to random initialization. Our results provide theoretical insights into the empirical success of using good initializations in practice.
Weak Solution of a Doubly Degenerate Parabolic Equation
Submitted
Abstract
We study the existence and uniqueness of weak solutions to a class of doubly degenerate parabolic equations. These equations arise in various applications including flow in porous media and image processing. We establish the well-posedness of the problem under suitable assumptions on the initial data and boundary conditions.
Agent-based and Continuous Models of Locust Hopper Bands
Submitted
Abstract
We develop and analyze both agent-based and continuous models for the movement of locust hopper bands. The models incorporate social interactions, alignment, and random motion to capture the complex collective behavior observed in nature. We establish connections between the microscopic agent-based model and the macroscopic continuous model through systematic coarse-graining.