Regret-Minimizing Algorithms Beyond Classical Optimization and Control

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.