Improved algorithm learns polynomial size depth three circuits faster
Learning Depth-3 Circuits with Polynomial Savings
Data Structures and AlgorithmsComputational Complexity
Summary
Learning certain types of logical functions called depth-three circuits is a hard problem in computer science. The authors present a new algorithm that can learn these functions faster than previous methods, saving significant computing time. They achieve this by using advanced math techniques involving random walks and special polynomials to better approximate parts of the function. This improvement means more efficient learning of complex functions on binary inputs.
What this means in practice
- •For machine learning engineers: Speed up learning algorithms that model complex logical functions using depth-three circuits with fewer mistakes and in less time.
- •For algorithm designers: Develop improved algorithms for online learning tasks by applying spectral gap amplification and feature space constructions inspired by this work.
A theory result. No direct application yet.
Authors
Xi Chen, Animesh Fatehpuria, Shyamal Patel, Rocco Servedio
Abstract
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 - Ω(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 $γ\geq1$, we give an algorithm that learns depth-three circuits of size $n^γ$ with running time \[ 2^{n-c_γn}, \] where $c_γ>0$ depends only on $γ$ 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_γ= \exp(-O(γ))$; by augmenting this warmup with further ingredients we obtain the sharp form of our result, which achieves $c_γ=Ω(1)/γ$.