Abstract
Problems that we encounter in real-world applications are often NP-hard. Therefore, a wealth of algorithms have been developed to provide approximate solutions to these problems efficiently. Max-cut, clustering, and many other partitioning problems fall into this camp, with widespread applications ranging from statistical physics to computational biology. Since the most commonly used heuristics and approximation algorithms for these problems are often characterized by real-valued parameters, it is crucial to decide which algorithm from a parametrized family of infinitely many algorithms is the “best” to use. While conventionally, one would then choose the algorithm with the best worst-case performance, the worst-case scenario may never materialize in a specific application domain. This calls for an application-specific algorithm selection approach in which one tunes the parameters of the algorithm to suit an unknown distribution over problem instances defining which problems are typical in that application. While this question has been studied empirically over the past several decades, there has been little work in developing a firm theoretical understanding until recently when Gupta and Roughgarden [2016] proposed a learning-theoretic model where one “learns” the best algorithm for an application by sampling problem instances from the underlying distribution. We work in this framework and focus on two widely used classes of algorithms: i) an infinite family of clustering algorithms which involve an agglomerative step followed by dynamic programming ii) a rich class of randomized rounding techniques for SDP relaxations of integer quadratic programs such as max-cut. We provide tight bounds on the learning-theoretic dimensions of these algorithm classes which demonstrates their intrinsic complexity. Based on this we present simple and computationally efficient techniques with sample complexity guarantees to learn the best algorithm from these classes for a given application domain.
Joint work with Maria-Florina Balcan, Ellen Vitercik and Colin White.