Learning constant-depth circuits from random examples

By the Linial–Mansour–Nisan theorem above an explicit degree (Circuits.Boolean.Unbounded.sum_fourierCoeff_sq_le_of_computes_of_depth_le), a function computed by a circuit of negations and unbounded fan-in conjunctions and disjunctions of depth at most d with at most g gates (UniformLearning.circuitClass) has Fourier weight at most 2 g / 2 ^ s above degree t, for every s ≥ 2 and t + 1 ≥ 2 max 8 (2 s) (16 s + 1) ^ d. Taking 2 ^ s ≥ 4 g / ε, the weight is at most ε / 2, so the low-degree algorithm learns these circuits from uniform random examples (UniformLearning.lowDegreeLearner_learns_circuitClass): a form of O'Donnell, Theorem 4.31 [LMN93] with exponent d + 1. With s = max 2 ⌈log₂ ⌈4 g / ε⌉⌉ the degree is t = UniformLearning.lmnDegree d g ε, which is O (log (g / ε)) ^ (d + 1) for fixed d (UniformLearning.lowDegreeLearner_learns_lmnDegree), and the algorithm uses m ≥ (4 N / ε) log (2 N / δ) examples, where N ≤ (n + 1) ^ t is the number of sets of at most t coordinates (BitString.card_filter_card_le_le_pow). Read asymptotically (this reading is not itself formalized), for g polynomial in n and constant d, ε and δ this is n ^ O (log n) ^ (d + 1) examples: quasi-polynomially many.

Depth counts every gate on a path, negations included (Circuit.depth). For a circuit whose negations sit at the inputs, of AND/OR depth d' in the usual sense, this depth is at most d' + 1; this conversion is not formalized here. The exponent d + 1 is inherited from the Fourier bound used here (Circuits.Boolean.Unbounded.sum_fourierCoeff_sq_le_of_computes), in which each restriction stage keeps a 1 / (16 s + 1) fraction of the free bits. It is weaker than the degree O (log (g / ε)) ^ d of Linial, Mansour and Nisan, and than the degree O (log (g / ε)) ^ (d - 1) · log (1 / ε) of the sharper form presented by O'Donnell O'Donnell, Section 4.5.

The learner computes N empirical coefficients from m examples, O (N m t) arithmetic operations; this running time is an informal count, not certified by a machine model.

Main definitions

• Cslib.MachineLearning.UniformLearning.circuitClass: the functions computed by circuits of bounded depth and size.
• Cslib.MachineLearning.UniformLearning.lmnDegree: the degree used for circuits of depth d with g gates and error ε.

Main results

• Cslib.MachineLearning.UniformLearning.lowDegreeLearner_learns_circuitClass, Cslib.MachineLearning.UniformLearning.lowDegreeLearner_learns_lmnDegree: the low-degree algorithm learns circuits of constant depth from uniform random examples.

References

• N. Linial, Y. Mansour, N. Nisan, Constant depth circuits, Fourier transform, and learnability
• R. O'Donnell, Analysis of Boolean Functions

def Cslib.MachineLearning.UniformLearning.circuitClass (n d g : ℕ) : PACLearning.ConceptClass (BitString n) Bool

The functions of n bits computed by circuits of negations and unbounded fan-in conjunctions and disjunctions of depth at most d with at most g gates.

theorem Cslib.MachineLearning.UniformLearning.lowDegreeLearner_learns_circuitClass {n d g s t m : ℕ} {ε δ : ℝ} (hε : 0 < ε) (hδ : 0 < δ) (hs : 2 ≤ s) (hsg : 4 * ↑g ≤ ε * 2 ^ s) (ht : 2 * max 8 (2 * s) * (16 * s + 1) ^ d ≤ t + 1) (hm : 4 * ↑{S : Finset (Fin n) | S.card ≤ t}.card / ε * Real.log (2 * ↑{S : Finset (Fin n) | S.card ≤ t}.card / δ) ≤ ↑m) : Learns (lowDegreeLearner (Fin n) t m) (circuitClass n d g) ε δ

The low-degree algorithm learns constant-depth circuits, a form of O'Donnell, Theorem 4.31 [LMN93] with exponent d + 1. Let s ≥ 2 with 4 g ≤ ε 2 ^ s, let t + 1 ≥ 2 max 8 (2 s) (16 s + 1) ^ d, and let N be the number of sets of at most t of the n coordinates. Then the low-degree algorithm of degree t from m ≥ (4 N / ε) log (2 N / δ) uniform random examples learns the functions computed by circuits of negations and unbounded fan-in conjunctions and disjunctions of depth at most d with at most g gates, with error ε and confidence 1 - δ.

noncomputable def Cslib.MachineLearning.UniformLearning.lmnDegree (d g : ℕ) (ε : ℝ) : ℕ

The degree of the low-degree algorithm for circuits of depth d with g gates and error ε: 2 max 8 (2 s) (16 s + 1) ^ d - 1 for s = max 2 ⌈log₂ ⌈4 g / ε⌉⌉, which is O (log (g / ε)) ^ (d + 1) for fixed d.

theorem Cslib.MachineLearning.UniformLearning.lowDegreeLearner_learns_lmnDegree {n d g m : ℕ} {ε δ : ℝ} (hε : 0 < ε) (hδ : 0 < δ) (hm : 4 * ↑{S : Finset (Fin n) | S.card ≤ lmnDegree d g ε}.card / ε * Real.log (2 * ↑{S : Finset (Fin n) | S.card ≤ lmnDegree d g ε}.card / δ) ≤ ↑m) : Learns (lowDegreeLearner (Fin n) (lmnDegree d g ε) m) (circuitClass n d g) ε δ

The low-degree algorithm learns constant-depth circuits, with the explicit degree t = lmnDegree d g ε = O (log (g / ε)) ^ (d + 1) [LMN93] O'Donnell, Section 4.5: from m ≥ (4 N / ε) log (2 N / δ) uniform random examples, where N ≤ (n + 1) ^ t is the number of sets of at most t of the n coordinates, it learns the functions computed by circuits of negations and unbounded fan-in conjunctions and disjunctions of depth at most d with at most g gates, with error ε and confidence 1 - δ.