Back to search

Georgia Institute of Technology

Foundations of Efficient Representation Learning

Abstract

dc:description.abstract

Representation learning extracts lower-dimensional, structured features from complex, unstructured data and reuses them across tasks. Despite strong empirical performance, its theoretical foundations remain limited. This thesis bridges this gap by developing formal efficiency guarantees for representation learning. First, we study unsupervised identification of geometric structure and give a polynomial-time algorithm that recovers a halfspace with margin from unlabeled data under broad distributional conditions. Next, we analyze implicit structure in sequence modeling. By formalizing long-range structure using efficient distinguishers, we prove that minimizing next-token prediction loss over bounded-size networks yields an indistinguishable language model, with model size polynomial in the distinguisher parameters and independent of document length. Finally, we study how learned structures can be efficiently transferred in lifelong learning, where tasks arrive sequentially and the model continually refines the representation while maintaining performance on earlier tasks. We propose algorithms that dynamically learn, refine, and reuse features across sequential tasks, achieving near-optimal sample complexity. Together, these results provide a unified learning-theoretic foundation for efficient representation learning, spanning how structure can be identified, induced by training objectives, and transferred across tasks.

Degree

thesis:*
Name thesis:degree_name
Machine Learning, PhD
Department thesis:degree_department
Computer Science
Grantor
Georgia Institute of Technology
Year dc:date.issued
2026

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Cao, Xinyuan
Advisor dc:contributor.advisor
  • Vempala, Santosh S.
Committee members dc:contributor.committeemember
  • Abernethy, Jacob
  • Li, Pan
  • Singla, Sahil
  • Shi, Freda
ORCID person:identifier.orcid

Rights

Language dc:language.iso
English

Identifiers

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

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

Cao, Xinyuan. Foundations of Efficient Representation Learning. Georgia Institute of Technology, 2026. https://hdl.handle.net/1853/81768