License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2017.35
URN: urn:nbn:de:0030-drops-75842
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7584/
Go to the corresponding LIPIcs Volume Portal

Carmosino, Marco L. ; Impagliazzo, Russell ; Kabanets, Valentine ; Kolokolova, Antonina

Agnostic Learning from Tolerant Natural Proofs

pdf-format:
LIPIcs-APPROX-RANDOM-2017-35.pdf (0.6 MB)

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 (constant-depth 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 quasi-polynomial 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 n-variate function even with exp(-Omega(n)) advantage over random guessing) would yield a polynomial-time 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:1--35:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-044-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{81},
  editor =	{Klaus Jansen and Jos{\'e} D. P. Rolim and David Williamson and Santosh S. Vempala},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7584},
  URN =		{urn:nbn:de:0030-drops-75842},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2017.35},
  annote =	{Keywords: agnostic learning, natural proofs, circuit lower bounds, meta-algorithms, AC0[q], Nisan-Wigderson generator}
}

Keywords: agnostic learning, natural proofs, circuit lower bounds, meta-algorithms, AC0[q], Nisan-Wigderson generator
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)
Issue Date: 2017
Date of publication: 11.08.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI