Abstract

Learning algorithms have enjoyed a lot of publicity lately, with successes in areas from playing Go to self-driving cars to medical diagnostics. Intuitively, "simpler" functions should be easier to learn than more complex ones. But can the mere knowledge that a class of functions is simple give us a way to learn them? We show that complexity-theoretic methods allow us to do just that, provided the proof of simplicity is "natural enough".

In this work, we show how lower bounds for circuit classes can give us an automatic way to design learning algorithms for functions from these classes. More specifically, we show how lower bounds proven in the "natural proof" framework can be converted into learning algorithms. As an application of our method, we obtain the first learning algorithm for functions computable by bounded-depth circuits with parity (and in general mod-p for a prime p) gates.

Joint work with Marco Carmosino (UCSD), Russell Impagliazzo (UCSD), and Valentine Kabanets (SFU).