Abstract
dc:description.abstractRepresentation 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