Hardness of Learning

STOC/SoCG 2016 Tutorial
Amit Daniely

Proving hardness of learning problems is a key challenge in Valiant's PAC learning model. As reductions from NP-hard problems do not seem to apply in this context, this area evolved somewhat separately. Traditionally, hardness of learning was proved under cryptographic assumptions. Such assumptions imply that it is hard to learn log-depth circuits, intersections of halfspaces, and more. More recently a new technique was developed for proving hardness of learning based on hardness on average of Constraint Satisfaction Problems like K-SAT and K-XOR. In particular, such assumptions imply that already very simple classes, like DNF formulas, are hard to learn.

The tutorial will cover most central hardness of learning techniques and results, with emphasis on the aforementioned recent progress.

Tentative program:
9:00 - 9:50
1. Introduction
The PAC model. What is known about basic PAC problems

2. Proving Hardness: Learning vs. Computation
Inapplicability of NP-hardness techniques. Boosting vs. Hardness of Approximation

3. Hardness under Cryptographic assumptions
9:50 - 10:05
Break
10:05 - 10:45
4. Hardness under Average Case assumptions