Learning Boolean Circuits with Neural Networks

Abstract

While on some natural distributions, neural-networks are trained efficiently using gradient-based algorithms, it is known that learning them is computationally hard in the worst-case. To separate hard from easy to learn distributions, we observe the property of local correlation: correlation between local patterns of the input and the target label. We focus on learning deep neural-networks using a gradient-based algorithm, when the target function is a tree-structured Boolean circuit. We show that in this case, the existence of correlation between the gates of the circuit and the target label determines whether the optimization succeeds or fails. Using this result, we show that neural-networks can learn the (log n)-parity problem for most product distributions. These results hint that local correlation may play an important role in separating easy/hard to learn distributions. We also obtain a novel depth separation result, in which we show that a shallow network cannot express some functions, while there exists an efficient gradient-based algorithm that can learn the very same functions using a deep network. The negative expressivity result for shallow networks is obtained by a reduction from results in communication complexity, that may be of independent interest.

References in corpus (22)

• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• A Convergence Theory for Deep Learning via Over-Parameterization
• Gradient Descent Provably Optimizes Over-parameterized Neural Networks
• Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
• Provable Bounds for Learning Some Deep Representations
• Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers
• Representation Benefits of Deep Feedforward Networks
• On the number of response regions of deep feed forward networks with piece-wise linear activations
• A Comparative Analysis of the Optimization and Generalization Property of Two-layer Neural Network and Random Feature Models Under Gradient Descent Dynamics
• What Can ResNet Learn Efficiently, Going Beyond Kernels?
• Benefits of depth in neural networks
• Towards moderate overparameterization: global convergence guarantees for training shallow neural networks
• Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputs
• On the Expressive Power of Deep Neural Networks
• SGD Learns the Conjugate Kernel Class of the Network
• Bounding and Counting Linear Regions of Deep Neural Networks
• Provable limitations of deep learning
• Why do Larger Models Generalize Better? A Theoretical Perspective via the XOR Problem
• Greedy Layerwise Learning Can Scale to ImageNet
• A Provably Correct Algorithm for Deep Learning that Actually Works
• Is Deeper Better only when Shallow is Good?
• On the Learnability of Deep Random Networks

Cited by in corpus (1)

• The Connection Between Approximation, Depth Separation and Learnability in Neural Networks