Why Do Approximate Algorithms Work Well in Machine Learning?

Abstract: Many success stories in machine learning share an intriguing algorithmic phenomenon: while the core algorithmic problems might seem costly to solve or even intractable at first, simple heuristics or approximation algorithms often perform surprisingly well in practice. Common examples include optimizing over non-convex functions or non-convex sets. Even in convex problems, we often settle for sub-optimal solutions returned by stochastic gradient descent. And in nearest neighbor search, a variety of algorithms works remarkably well considering the “curse of dimensionality”.

In this thesis, we study this phenomenon in the context of three algorithmic problems that appear widely in the data sciences: constrained optimization (what non-convex sets can we optimize over?), unconstrained optimization (why don’t we compute high-accuracy ERM solutions?), and nearest neighbor search (can the LSH framework explain the empirical state of the art?). The common theme is that the computational hardness of many algorithmic problems appears only below the inherent noise floor of the overall statistical problem.