Carmosino, Marco L. ;
Impagliazzo, Russell ;
Kabanets, Valentine ;
Kolokolova, Antonina
Agnostic Learning from Tolerant Natural Proofs
Abstract
We generalize the "learning algorithms from natural properties" framework of [CIKK16] to get agnostic learning algorithms from natural properties with extra features. We show that if a natural property (in the sense of Razborov and Rudich [RR97]) is useful also against functions that are close to the class of "easy" functions, rather than just against "easy" functions, then it can be used to get an agnostic learning algorithm over the uniform distribution with membership queries.
* For AC0[q], any prime q (constantdepth circuits of polynomial size, with AND, OR, NOT, and MODq gates of unbounded fanin), which happens to have a natural property with the requisite extra feature by [Raz87, Smo87, RR97], we obtain the first agnostic learning algorithm for AC0[q], for every prime q. Our algorithm runs in randomized quasipolynomial time, uses membership queries, and outputs a circuit for a given Boolean function f that agrees with f on all but at most polylog(n)*opt fraction of inputs, where opt is the relative distance between f and the closest function h in the class AC0[q].
* For the ideal case, a natural proof of strongly exponential correlation circuit lower bounds against a circuit class C containing AC0[2] (i.e., circuits of size exp(Omega(n)) cannot compute some nvariate function even with exp(Omega(n)) advantage over random guessing) would yield a polynomialtime query agnostic learning algorithm for C with the approximation error O(opt).
BibTeX  Entry
@InProceedings{carmosino_et_al:LIPIcs:2017:7584,
author = {Marco L. Carmosino and Russell Impagliazzo and Valentine Kabanets and Antonina Kolokolova},
title = {{Agnostic Learning from Tolerant Natural Proofs}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
pages = {35:135:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770446},
ISSN = {18688969},
year = {2017},
volume = {81},
editor = {Klaus Jansen and Jos{\'e} D. P. Rolim and David Williamson and Santosh S. Vempala},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7584},
URN = {urn:nbn:de:0030drops75842},
doi = {10.4230/LIPIcs.APPROXRANDOM.2017.35},
annote = {Keywords: agnostic learning, natural proofs, circuit lower bounds, metaalgorithms, AC0[q], NisanWigderson generator}
}
11.08.2017
Keywords: 

agnostic learning, natural proofs, circuit lower bounds, metaalgorithms, AC0[q], NisanWigderson generator 
Seminar: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)

Issue date: 

2017 
Date of publication: 

11.08.2017 