Search Results

Documents authored by Karchmer, Ari

Distributional PAC-Learning from Nisan’s Natural Proofs

Authors: Ari Karchmer

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Do natural proofs imply efficient learning algorithms? Carmosino et al. (2016) demonstrated that natural proofs of circuit lower bounds for Λ imply efficient algorithms for learning Λ-circuits, but only over the uniform distribution, with membership queries, and provided AC⁰[p] ⊆ Λ. We consider whether this implication can be generalized to Λ ⊉ AC⁰[p], and to learning algorithms which use only random examples and learn over arbitrary example distributions (Valiant’s PAC-learning model). We first observe that, if, for any circuit class Λ, there is an implication from natural proofs for Λ to PAC-learning for Λ, then standard assumptions from lattice-based cryptography do not hold. In particular, we observe that depth-2 majority circuits are a (conditional) counter example to this fully general implication, since Nisan (1993) gave a natural proof, but Klivans and Sherstov (2009) showed hardness of PAC-Learning under lattice-based assumptions. We thus ask: what learning algorithms can we reasonably expect to follow from Nisan’s natural proofs? Our main result is that all natural proofs arising from a type of communication complexity argument, including Nisan’s, imply PAC-learning algorithms in a new distributional variant (i.e., an "average-case" relaxation) of Valiant’s PAC model. Our distributional PAC model is stronger than the average-case prediction model of Blum et al. (1993) and the heuristic PAC model of Nanashima (2021), and has several important properties which make it of independent interest, such as being boosting-friendly. The main applications of our result are new distributional PAC-learning algorithms for depth-2 majority circuits, polytopes and DNFs over natural target distributions, as well as the nonexistence of encoded-input weak PRFs that can be evaluated by depth-2 majority circuits.

Cite as

Ari Karchmer. Distributional PAC-Learning from Nisan’s Natural Proofs. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 68:1-68:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

  author =	{Karchmer, Ari},
  title =	{{Distributional PAC-Learning from Nisan’s Natural Proofs}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{68:1--68:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-195964},
  doi =		{10.4230/LIPIcs.ITCS.2024.68},
  annote =	{Keywords: PAC-learning, average-case complexity, communication complexity, natural proofs}
Questions / Remarks / Feedback

Feedback for Dagstuhl Publishing

Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail