Back to search

Georgia Institute of Technology

Two Aspects of Statistical Learning in High Dimensions: Iterative Algorithms and Average-Case Reductions

Abstract

dc:description.abstract

We 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

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Lou, Mengqi. Two Aspects of Statistical Learning in High Dimensions: Iterative Algorithms and Average-Case Reductions. Georgia Institute of Technology, 2026. https://hdl.handle.net/1853/81702