Heuristic learning on the border between success and failure – Learning Club talk by Eran Malach, HUJI

Title: Heuristic learning on the border between success and failure

Abstract: Many popular hypothesis classes, such as neural-networks or decision trees, are computationally hard to learn. In practice, however, heuristic algorithms are used to learn these classes with remarkable success. To better understand this gap, we explore probabilistic models where a small change in the distribution determines whether the optimization process succeeds or fails. We use these models to suggest specific distributional properties that differentiate between problems that are hard or easy to learn using common heuristic algorithms. We show theoretically and empirically that such properties play a key role in learning our “borderline” models, and suggest that they might be relevant for the broader effort of understanding algorithms used in practice.