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

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.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Electrical & Computer Engr

Grantor

University of Illinois Urbana-Champaign

Year dc:date

2025

Author dc:creator

• Zhang, Jialun

Contributors dc:contributor

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

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

Statement dc:rights

• Copyright 2025 Jialun Zhang

Language dc:language

en, eng

Handle dc:identifier

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

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F129360