Abstract

Computational learning theory, like most of the analysis of algorithms, is based on worst-case complexity, requiring algorithms that work for every problem instance. We apply "smoothed analysis" (Spielman and Teng, 2001) to revisit some classic open problems in learning Boolean function, such as learning sparse polynomials, decision trees, and DNF formulas, from random examples drawn from a product distribution over the n-dimensional hypercube. We give algorithms to efficiently learn such classes. Smoothed analysis provides guarantees that lie in between worst-case and average-case complexity.

The talk will be self contained and will not require prior knowledge in computational learning theory. It is based on joint work with Alex Samorodnitsky and Shang-Hua Teng.