Marrying Worst-Case Analysis and Machine Learning

Worst-case analysis, the de-facto standard in the analysis of algorithms, certifies that an algorithm is correct and efficient on any possible input. While this lens lends itself to the design of algorithms that are dependable, its rigidity outlaws techniques that rely on nebulous properties of the algorithms' inputs. On the other hand, machine learning models are optimized on a particular distribution of inputs, allowing them to leverage hidden, implicit structure. Machine learning excels whenever the past is indicative of the future but is notoriously unreliable in changing environments. Through two themes in this thesis, we identify opportunities to marry the rigor of worst-case analysis with the flexibility of machine learning:

 

- We augment traditional algorithms with machine learning components so that (a) the algorithms maintain their worst-case guarantees even if the learning fails, and (b) the algorithms far exceed their worst-case performance when the learning succeeds. We develop learning-augmented variants of classic algorithms for fundamental tasks in graph algorithms, streaming algorithms, and online algorithms, and we demonstrate their performance analytically and empirically.

 

- We quantify what it means for a machine learning model to have a faithful world model through the formalism of automata theory. We develop evaluations based on this abstraction which accurately predict the (non-)robustness of machine learning models to worst-case perturbations.