Over-parameterized low-rank matrix estimation: Theory, algorithms, applications

Zhang, Jialun

Permalink

https://hdl.handle.net/2142/129360 Copy

Description

Title

Over-parameterized low-rank matrix estimation: Theory, algorithms, applications

Author(s)

Zhang, Jialun

Issue Date

2025-04-20

Director of Research (if dissertation) or Advisor (if thesis)

Zhang, Richard

Doctoral Committee Chair(s)

Zhang, Richard

Committee Member(s)

• Raginsky, Maxim
• Zhao, Zhizhen
• Srikant, Rayadurgam

Department of Study

Electrical & Computer Eng

Discipline

Electrical & Computer Engr

Degree Granting Institution

University of Illinois Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• low-rank matrix recovery
• nonconvex optimization
• mathematical optimization

Abstract

This thesis considers the non-convex methods for low-rank matrix estimation based on Burer-Monteiro factorization, which offers better scalability and lower per-iteration costs compared to convex methods. However, non-convex optimization faces challenges from spurious local minima or critical points, which can lead gradient-based algorithms to converge to suboptimal solutions. Prior research has shown that a sufficiently large training dataset can eliminate spurious minima in non-convex problems, enabling successful low-rank estimation. However, these guarantees are often impractical in real-world applications for two reasons. First, they require a large amount of data to remove spurious local minima across the entire parameter space, which is costly and challenging for large-scale applications. Second, they assume ``regular" measurement conditions (e.g., restricted isometry property or incoherence), which are rarely satisfied in practice. To address these challenges, we first prove that a good initial point can reduce the required sample size to avoid spurious minima near the ground truth. This insight reveals that practical low-rank estimation problems are often less demanding in terms of data than prior theory suggests. Specifically, there is a direct tradeoff: better initial point quality linearly reduces sample complexity, and vice versa. The thesis thus sheds light on how non-convex landscapes become more manageable with improved initialization or increased samples, providing insights that could extend to other non-convex problems. The major focus of our thesis is how over-parameterization can be used to effectively solve non-convex matrix estimation problems. Over-parameterization serves two purposes: it certifies global optimality by allowing sufficient flexibility in the model, and it ensures solution accuracy even when the true rank $r^*$ is hard to estimate. Unfortunately, over-parameterization slows gradient descent exponentially, which dramatically increases the cost to converge to the ground truth. To overcome this, the thesis introduces PrecGD (preconditioned gradient descent), a method that preserves the fast convergence of gradient descent, achieving exponential error reduction per iteration. PrecGD’s convergence rate is independent of ill-conditioning or over-parameterization, with a per-iteration cost only slightly higher than standard gradient descent. Finally, we also extend our algorithm, PrecGD, to two important practical settings: (1) first, we present a stochastic version of PrecGD that applies even to huge-scale matrix completion type problems where even on full-batch gradient evaluation is too expensive. (2) Then, we consider adapting our algorithm to scenarios where the measurements are extremely noisy, which makes preconditioning significantly more difficult since it is easy to magnify the noise as well. In both cases we present a rigorous proof for the success of our method, which is also validated extensively in numerical experiments.

Graduation Semester

2025-05

Type of Resource

Thesis

Handle URL

https://hdl.handle.net/2142/129360

Copyright and License Information

Copyright 2025 Jialun Zhang

Owning Collections