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: