Metraipolis › archive › dc_99086de4e6ee

Learning Depth-3 Circuits with Polynomial Savings — arXiv:2609.18166

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.18166
License (as archived)
CC0-1.0
Archived
2026-10-15T17:09:18.457Z
SHA-256 of the archived text
dfadaab62a35e36b1676e25333df2e9923db31e05b0b17952456ffc468bc9492
Stable URL of this page
https://metraipolis.com/documento/dc_99086de4e6ee

How to cite

Learning Depth-3 Circuits with Polynomial Savings — arXiv:2609.18166 — arXiv (en), https://arxiv.org/abs/2609.18166 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_99086de4e6ee (Metraipolis archive dc_99086de4e6ee, sha256 dfadaab62a35e36b1676e25333df2e9923db31e05b0b17952456ffc468bc9492)
BibTeX
@misc{dc99086de4e6ee,
  title = {Learning Depth-3 Circuits with Polynomial Savings — arXiv:2609.18166},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.18166},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_99086de4e6ee; sha256 dfadaab62a35e36b1676e25333df2e9923db31e05b0b17952456ffc468bc9492},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.18166. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We study the challenging problem of learning depth-three circuits in the mistake-bound model of (realizable) online learning, which is a more difficult model than distribution-free PAC learning. Prior algorithms for this problem, due to Servedio and Tan [ST17], could only learn polynomial-size depth-three circuits of poly$(n)$ size over $\{0,1\}^n$ with a running time of $2^{n - \Omega(n/\log n)}$, and hence they ran in time $N^{1-o(1)}$ where $N=2^n$ is the running time of a naive memorization-based approach. In this work we substantially improve on the [ST17] result: for any constant $\gamma\geq1$, we give an algorithm that learns depth-three circuits of size $n^\gamma$ with running time \[ 2^{n-c_\gamma n}, \] where $c_\gamma>0$ depends only on $\gamma$ and not on $n$. Hence we achieve a polynomial savings over the naive approach for learning any polynomial-size depth-three circuit. The main driving force behind our improvement is an improved bound on the approximate degree of width-$k$ CNFs. Inspired by Szegedy [Sze04] and Magniez et al. [MNRS11], the rough idea of our construction is to use a Chebyshev polynomial to efficiently amplify the spectral gap of a carefully designed random walk. This is combined with a random-restriction-like approach to separately learn different subfunctions corresponding to different assignments to a randomly chosen set of variables, using the Perceptron algorithm over a specially designed feature space. A simplified warmup instantiation of our approach achieves $c_\gamma = \exp(-O(\gamma))$; by augmenting this warmup with further ingredients we obtain the sharp form of our result, which achieves $c_\gamma=\Omega(1)/\gamma$.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-17 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2609.18166 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-15T16:17:15.259Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-17?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).