Transforming machine learning heuristics into provable algorithms: classical, stochastic, and neural Open Access

A recurring pattern in many areas of machine learning is the empirical success of a handful of “heuristics”, that is, any simple learning procedure favored by practitioners. Many of these heuristic techniques lack formal theoretical justification. For unsupervised learning, Lloyd's k-means algorithm, while provably exponentially slow in the worst-case remains popular for clustering problems arising from different applications.For supervised learning, random forest is another example of a winning heuristic with many variants and applications.But the most prominent example is perhaps the blossoming field of deep learning, which is almost entirely composed of heuristics; the practical success of a deep learning algorithm usually relies on an experienced user skillfully and creatively combining heuristics.The main contribution of this thesis is in advancing our theoretical understanding of some of the most widely-used machine learning heuristics. In doing so, we uncover the mechanism behind heuristics and the properties of data that enable their empirical success. This in turn sheds light on important practical and algorithmic questions: knowing why a heuristic works helps us answer questions such as when and how to properly it; capturing the hidden structure in data leveraged by a heuristic can answer questions such as how to develop better and faster algorithms on realistic data, an alternative to the traditional approach of devising worst-case algorithms.


In Administrative Set:


Attribute NameValues
Date created
Type of Work
Rights statement
GW Unit
Committee Member(s)
Persistent URL
Last modified:

Downloadable Content

Download PDF

EndNote | Zotero | Mendeley