Georgia Institute of Technology
Two Aspects of Statistical Learning in High Dimensions: Iterative Algorithms and Average-Case Reductions
Abstract
dc:description.abstractWe focus on both the computational and statistical aspects of learning in high-dimensional settings. On the computational side, iterative algorithms are commonly used to fit complex models to random data, but their design and analysis are often guided by worst-case upper bounds that may not reflect practical performance. On the statistical side, classical information-theoretic limits on sample complexity or signal-to-noise ratio may be unattainable by any polynomial-time procedure, making these limits an impractical benchmark for modern high-dimensional problems. This thesis develops two general frameworks to address these challenges. In the first part, we develop a toolkit that yields sharp, iterate-by-iterate characterizations of solution quality for complex iterative algorithms on a canonical non-convex model fitting problem–rank one matrix sensing–with random data. Our precise characterizations can provide fine-grained separations between families of algorithms while also revealing nonstandard convergence phenomena that are often invisible in worst-case analyses. In the second part, we study the problem of approximately transforming a sample from a source statistical model to a sample from a target statistical model without knowing the parameters of the source model, and construct several computationally efficient such reductions between canonical statistical models. We leverage our technique to establish reduction-based computational lower bounds for several canonical high-dimensional statistical models, including sparse phase retrieval, under widely-believed conjectures in average-case complexity. We also point to a possible application in transforming one differentially private mechanism to another.
Degree
thesis:*- Name thesis:degree_name
- Algorithms, Combinatorics, and Optimization, PhD
- Department thesis:degree_department
- Industrial and Systems Engineering
- Grantor
- Georgia Institute of Technology
- Year dc:date.issued
- 2026
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Lou, Mengqi
- Advisor dc:contributor.advisor
-
- Pananjady, Ashwin
- Committee members dc:contributor.committeemember
-
- Mao, Cheng
- Perkins, Will
- Romberg, Justin
- Bresler, Guy
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- https://hdl.handle.net/1853/81702