Back to search

Georgia Institute of Technology

Robust Learning in High Dimension

Abstract

dc:description.abstract

This thesis focuses on designing efficient and robust algorithms for learning high-dimensional distributions, particularly in the presence of adversarial corruptions. We addresse existing challenges in robust learning in high dimension and establish new connections between robust statistics and algorithmic solutions. In particular, we give polynomial-time algorithms for the following two open problems: robust learning of Gaussian Mixture Models (GMMs) and robust learning of affine transformations of hypercubes. For GMMs, we give a polynomial-time algorithm for robustly learning a mixture of $k$ arbitrary Gaussians in \Rd, for any fixed $k$, in the presence of a constant fraction of arbitrary corruptions. This resolves the main open problem in several previous works on algorithmic robust statistics, which addressed the special cases of robustly estimating (a) a single Gaussian, (b) a mixture of TV-distance separated Gaussians, and (c) a uniform mixture of two Gaussians. Our main tools are an efficient partial clustering algorithm that relies on the sum-of-squares method (building on previous work), and a novel tensor decomposition algorithm that allows errors in both Frobenius norm and low-rank terms. The second contribution is a polynomial-time algorithm for robustly learning an unknown affine transformation of the standard hypercube from samples, an important and well-studied setting for independent component analysis (ICA). Our algorithm, based on a new method that goes beyond the limitations of the method of moments, achieves asymptotically optimal error in total variation distance. Lastly, we introduce a faster algorithm for the isotropic transformation of convex bodies, whose complexity is directly tied to the KLS (Kannan-Lovász-Simonovits) constant. This serves as a useful tool to high-dimensional learning and volume computation.

Degree

thesis:*
Level thesis:degree_level
Doctoral
Department dc:contributor.department
Computer Science
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2024

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Jia, He
Advisor dc:contributor.advisor
  • Vempala, Santosh S.
Committee members dc:contributor.committeemember
  • Diakonikolas, Ilias
  • Kothari, Pravesh
  • Mao, Cheng
  • Pananjady, Ashwin

Subjects

dc:subject × 5

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/1853/75271

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
citation

Jia, He. Robust Learning in High Dimension. Doctoral thesis, Georgia Institute of Technology, 2024. https://hdl.handle.net/1853/75271