Skip navigation
Please use this identifier to cite or link to this item:
Title: Regret-Minimizing Algorithms Beyond Classical Optimization and Control
Authors: Zhang, Cyril
Advisors: Hazan, Elad
Contributors: Computer Science Department
Subjects: Computer science
Artificial intelligence
Issue Date: 2020
Publisher: Princeton, NJ : Princeton University
Abstract: Temporally correlated data and non-convex programs are two core challenges which lie at the frontier of reconciling theory and practice in machine learning. In this thesis, we present varied perspectives on algorithms and provable learning guarantees in stateful and non-convex environments, such as those encountered in reinforcement learning, control theory, time-series analysis, and deep learning. These ideas are unified by the framework of online convex optimization, which provides robust algorithmic primitives and regret guarantees under minimal assumptions on the data. The recurring theme of leveraging regret minimization beyond classical settings will manifest in several ways, eclectic in their scope. First, we develop a solution concept and efficient algorithms for online non-convex optimization in its most generic form. Next, in a line of theoretical work on prediction and control in the presence of linear time-invariant state transitions, beyond the linear-quadratic-Gaussian assumptions of classical control theory, we use online learning with convex relaxations to bypass the computational and statistical brittleness of the usual system identification pipelines. Finally, we use online convex optimization as a testbed for principled algorithm design, towards improving and better understanding ubiquitous training heuristics in deep learning.
Alternate format: The Mudd Manuscript Library retains one bound copy of each dissertation. Search for these copies in the library's main catalog:
Type of Material: Academic dissertations (Ph.D.)
Language: en
Appears in Collections:Computer Science

Files in This Item:
File Description SizeFormat 
Zhang_princeton_0181D_13514.pdf3.19 MBAdobe PDFView/Download

Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.