Provably efficient methods for large-scale learning

dc.contributor.advisorSanghavi, Sujay Rajendra, 1979-
dc.contributor.committeeMemberShakkottai, Sanjay
dc.contributor.committeeMemberCaramanis, Constantine
dc.contributor.committeeMemberLiu, Qiang
dc.creatorYang, Shuo, Ph. D.
dc.creator.orcid0009-0005-2356-5666
dc.date.accessioned2023-12-19T04:34:12Z
dc.date.available2023-12-19T04:34:12Z
dc.date.created2023-08
dc.date.issued2023-07-19
dc.date.submittedAugust 2023
dc.date.updated2023-12-19T04:34:12Z
dc.description.abstractThe scale of machine learning problems grows rapidly in recent years and calls for efficient methods. In this dissertation, we propose simple and efficient methods for various large-scale learning problems. We start with a standard supervised learning problem of solving quadratic regression. In Chapter 2, we show that by utilizing the quadratic structure and a novel gradient estimation algorithm, we can solve sparse quadratic regression with sub-quadratic time complexity and near-optimal sample complexity. We then move to online learning problems. In Chapter 3, we identify a weak assumption and theoretically prove that the standard UCB algorithm efficiently learns from inconsistent human preferences with nearly optimal regret; in Chapter 4 we propose an approximate maximum inner product search data structure for adaptive queries and present two efficient algorithms that achieve sublinear time complexity for linear bandits, which is especially desirable for extremely large and slowly changing action sets. In Chapter 5, we study how to efficiently use privileged features with deep learning models. We present an efficient learning algorithm to exploit privileged features that are not available during testing time. We conduct comprehensive empirical evaluations and present rigorous analysis for linear models to build theoretical insights. It provides a general algorithmic paradigm that can be integrated with many other machine learning methods.
dc.description.departmentComputer Sciences
dc.format.mimetypeapplication/pdf
dc.identifier.urihttps://hdl.handle.net/2152/123245
dc.identifier.urihttps://doi.org/10.26153/tsw/50043
dc.language.isoen
dc.subjectMachine learning
dc.subjectOnline learning
dc.subjectDistillation
dc.subjectEfficiency
dc.titleProvably efficient methods for large-scale learning
dc.typeThesis
dc.type.materialtext
thesis.degree.departmentComputer Sciences
thesis.degree.disciplineComputer Science
thesis.degree.grantorThe University of Texas at Austin
thesis.degree.levelDoctoral
thesis.degree.nameDoctor of Philosophy

Access full-text files

Original bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
YANG-DISSERTATION-2023.pdf
Size:
1.64 MB
Format:
Adobe Portable Document Format

License bundle

Now showing 1 - 2 of 2
No Thumbnail Available
Name:
PROQUEST_LICENSE.txt
Size:
4.45 KB
Format:
Plain Text
Description:
No Thumbnail Available
Name:
LICENSE.txt
Size:
1.84 KB
Format:
Plain Text
Description: