PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning Depth-3 Circuits with Polynomial Savings

Xi Chen, Animesh Fatehpuria, Shyamal Patel, Rocco Servedio

arXiv:2609.18166v1cs.DScs.CC

TL;DR

Learning depth-three circuits in the online mistake-bound model is difficult, despite that model avoiding distributional assumptions. The paper combines an improved approximate-degree bound for width-k CNFs with a restriction-based learning approach. For circuits of size n^γ, it achieves running time 2^{n-c_γn}, yielding polynomial savings over the naive approach.

  • Problem

    Learning expressive Boolean functions is difficult in the online mistake-bound model, which avoids distributional assumptions such as a uniform input distribution.

    Source: §1 · p. 2

  • Method

    The approach uses an improved approximate-degree bound for width-k CNFs and restrictions that simplify subfunctions for learning with structured features.

    Source: §1.1 · p. 5

  • Results

    For every constant γ ≥1, the algorithm learns depth-three circuits of size n^γ in time 2^{n-c_γn}, for c_γ>0 depending only on γ.

    Source: §1.1 · p. 4

  • Takeaways & Limitations

    This running time gives polynomial savings over the naive approach for any polynomial-size target depth-three circuit.

    Source: §1.1 · p. 4

    The algorithm is randomized, succeeds with probability at least 1−O(1/n), and selects its live variable set only once at the beginning.

    Source: §3.1 · p. 9

Abstract

from arXiv · show

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$.

1 Introduction

The paper improves online mistake-bound learning for polynomial-size depth-three circuits, a class for which no 2^o(n)-time algorithms were known. Its approach combines random restrictions with improved approximations for width-k CNFs to obtain polynomial savings over memorization.

1 Introduction

  • No 2^o(n)-time distribution-free PAC or online mistake-bound algorithms were known for even polynomial-size depth-three de Morgan circuits.The online mistake-bound model is at least as difficult as distribution-free PAC learning and avoids distributional assumptions.Source: §1 · p. 2
  • The prior approach used random live-variable sets, separate learners on each subcube, and switching lemmas, achieving time 2^(n-n/O(log n)).A larger switching-lemma degree reduces costly failures but increases typical-subcube learning time; balancing these costs sets the live-variable probability to 1/O(log n).Source: §1 · pp. 2–3

1.1 Our main result: Improved running time for learning depth-three circuits.

  • For every constant γ≥1, the algorithm learns size-n^γ depth-three circuits in time 2^(n-c_γn), with c_γ=Ω(1)/γ.The paper gives a warmup with c_γ=2^-O(γ) and obtains the sharper bound by adding further ingredients.Source: §1.1 · p. 4
  • A new approximate-degree bound for width-k CNFs makes the k=Θ(log ℓ) regime nontrivial, unlike the previous bound's 2^(k/2) factor.That regime is useful because known switching-lemma methods can reduce unrestricted polynomial-size CNFs to width Θ(log ℓ).Source: §1.1 · pp. 4–5
  • In the warmup, random restrictions produce width-k CNFs that Perceptron learns over low-degree monomials, with memorization for exceptional assignments.The warmup achieves time 2^(n-2-O(γ)n).Source: §1.1 · p. 5
  • The full method groups live variables into blocks, learns with block-indicator features, and uses an exponential-moment bound on the width-reducing set.These ingredients yield the full 2^(n-Ω(1/γ)n) running-time result.Source: §1.1 · p. 5

2 Technical Overview

The overview links an improved width-k CNF approximation bound to a random-restriction strategy for learning depth-three circuits. A Chebyshev-amplified Johnson-graph walk supports the warm-up, while block-indicator features and tighter control of width-reducing sets support the full result.

2.1 The new approximate degree bound for width-k CNF formulas (Theorem 8)

  • Chebyshev amplification of a Johnson-graph walk improves the width-k CNF degree bound by avoiding the recursive 2^{k/2} penalty, at a slightly worse dependence on ε.The walk marks subsets witnessing a falsified clause; larger r increases the marked fraction but also the polynomial degree.Source: §2.1 · pp. 6–7

2.2 The warmup result: learning in time 2n−2−O(γ)n

  • For most random-restriction subcubes, a small width-reducing set lets the learner form a low-degree polynomial and use Perceptron, memorizing only hard subcubes.With high probability over L, at most a 2^{-ℓ/6} fraction of addresses have |Y(L,z)| > ℓ/100.Source: §2.2 · p. 7

2.3 The full result: learning in time 2n−Ω(1/γ)n

  • The full result uses block-indicator features and an exponential-moment bound on |Y(L,z)| to control Perceptron performance across all subcubes.Unlike the warm-up’s low-degree monomial representation and tail bound, these ingredients address the larger live set and tighter aggregate control needed for the full result.Source: §2.3 · pp. 7–8

3 Preliminaries

The preliminaries specify the randomized online mistake-bound setting and introduce the Johnson-graph, Chebyshev-polynomial, and Perceptron tools used later. They state the model’s runtime accounting and the margin-based mistake guarantee.

3.1 The learning model: online mistake-bound learning

  • The online learner receives arbitrary counterexamples until its hypothesis equals the target, and runtime is bounded by mistakes times per-trial evaluation and update costs.The randomized algorithm succeeds with probability at least 9/10; online mistake-bound learnability also yields a distribution-free PAC result.Source: §3.1 · pp. 8–9

3.2 Johnson Graph

  • The Johnson graph J(ℓ,r) has r-element subsets as vertices, with edges between sets whose intersection has size r−1; the paper studies random walks on it.The transition matrix has largest eigenvalue 1 and second eigenvalue magnitude at most 1−1/r under the stated conditions.Source: §3.2 · p. 9

3.3 Chebychev Polynomials

  • A shifted and scaled Chebyshev polynomial of degree d equals 1 at 1 and has magnitude at most ε on [−1, 1−η] when d ≥ ln(2/ε)/√η.These are the stated properties of the polynomial used in the later construction.Source: §3.3 · p. 10

3.4 Perceptron

  • For examples of norm at most R separated from the origin by margin ρ, Perceptron makes at most R^2∥w*∥^2/ρ^2 mistakes, independently of feature-space dimension.The theorem assumes a halfspace through the origin that correctly separates every labeled example.Source: §3.4 · p. 11

4 Approximate Degree of Width-k CNFs

The section proves an improved approximate-degree bound for width-k CNFs using a Chebyshev-amplified random walk on the Johnson graph. The resulting bound is useful for width O(log ℓ), the regime needed under the paper’s random restrictions.

Theorem 8

  • Theorem 8 gives a pointwise ε-approximating polynomial for width-k CNFs of degree O(ℓ^{k/(k+1)} log^{2/(k+1)}(1/ε)) and coefficient weight at most 32d.When the CNF outputs 1, the polynomial equals 1 exactly; the same degree bound applies to width-k DNFs by Boolean duality.Source: §4 · p. 11

Improved approximate degree

  • The bound removes the prior 2^{k/2} factor, with a slightly worse dependence on ε that is small in the k = Θ(log ℓ), ε = 1/poly(ℓ) regime.The improvement makes the bound nontrivial for a suitable k = Θ(log ℓ).Source: §4 · p. 11

Proof approach

  • The construction treats falsifying subsets as marked vertices in a Johnson-graph walk and applies a Chebyshev polynomial to amplify the walk’s spectral gap.The amplified walk reduces the required number of steps relative to a naive random walk, yielding a lower-degree approximator after parameter optimization.Source: §4 · pp. 11–12

5 Warm-up: Learning in Time 2n(1−2−O(γ))

The warm-up learns separate subfunctions on random subcubes, using Perceptron on tame addresses and memorization on hard ones. A greedy width-reducing set and a tail bound make hard addresses rare enough to obtain a runtime saving.

5.1 Subcubes and width-reducing sets

  • A greedy width-reducing set Y(L,z) ensures that every surviving clause has at most k literals outside Y.Fixing variables in Y reduces the width of each restricted CNF to at most k.Source: §5.1 · p. 14

5.2 Overview of the algorithm and its analysis

  • The algorithm draws a random live set, runs Perceptron on every subcube, and switches to memorization when mistakes exceed the tame-address bound.The live-set size is chosen as ℓ = ⌊pn⌋ with p = 2^{-2γ/c0}.Source: §5.2 · pp. 14–15

5.3 Tail bound on the size of the width-reducing set

  • With probability at least 1−1/n over L, the number of hard addresses is at most 2^{n−ℓ−ℓ/6}.For a random address, the probability that |Y(L,z)| > ℓ/100 is at most 2^{-ℓ/5} in the independent-inclusion analysis.Source: §5.3 · p. 15

5.4 Perceptron on tame subcubes

  • On a tame subcube, Perceptron uses monomial features of degree at most ℓ/90 to learn the restricted target with a bounded mistake count.The polynomial sign representation has degree at most ℓ/90 and coefficient-square sum at most 2^{ℓ/20+o(ℓ)}.Source: §5.4 · pp. 16–17

5 Warm-up: Learning in Time 2n(1−2−O(γ))

  • Using their choice of ℓ, the authors obtain the desired runtime bound 2n(1−2−O(γ)), completing the proof of the warm-up case of Theorem 1.Source: §5.5 · p. 17

6 Learning Depth 3 Circuits in Time 2n(1−Ω(1/γ))

The algorithm partitions variables into live sets and learns each restricted subfunction with Perceptron over a block-based feature space. Its analysis combines a CNF approximation, a bound on the width-reducing set, and subcube separators to obtain a running time of 2^n(1−Ω(1/γ)).

6.1 Overview of algorithm and its analysis

  • The algorithm partitions live variables into blocks and uses a feature map with 2B nonzero entries per input to keep Perceptron efficient.The large-width degree bound would entail Ω(2^ℓ) monomials, motivating the block-based feature construction.Source: §6.1 · p. 18

6.2 Dictionary version of approximating polynomial

  • For the stated block-dependence condition, the constructed q preserves g(x)=1 and approximates g within ε on all inputs.The condition is that each clause depends on at most k of the blocks V1,…,VB′.Source: §6.2 · pp. 18–19

6.3 Moment bound on the size of the width-reducing set

  • When each variable enters L independently with probability 2^-10, the width-reducing set satisfies E[2^(5|Y(L,z)|)] ≤ 2.This moment bound is the technical tool used in the subsection’s analysis.Source: §6.3 · p. 20

6.4 A linear separator over feature space F for the z-subcube

  • On each restricted subcube, the target agrees with a linear separator over the feature space at margin 1/4.The proposition also supplies a bound on the separator’s norm, though its value is not present in these passages.Source: §6.4 · p. 22

6.5 Concluding the proof of the strong form of Theorem 1

  • The total running time is 2^n(1−Ω(1/γ)), giving the section’s stated savings for learning depth-three circuits.The runtime expression follows from summing the costs across the subcube copies.Source: §6.5 · p. 24
Loading 2609.18166v1…