Learning Parities with Neural Networks

Abstract

In recent years we see a rapidly growing line of research which shows learnability of various models via common neural network algorithms. Yet, besides a very few outliers, these results show learnability of models that can be learned using linear methods. Namely, such results show that learning neural-networks with gradient-descent is competitive with learning a linear classifier on top of a data-independent representation of the examples. This leaves much to be desired, as neural networks are far more successful than linear methods. Furthermore, on the more conceptual level, linear models don't seem to capture the "deepness" of deep networks. In this paper we make a step towards showing leanability of models that are inherently non-linear. We show that under certain distributions, sparse parities are learnable via gradient decent on depth-two network. On the other hand, under the same distributions, these parities cannot be learned efficiently by linear methods.

References in corpus (19)

• 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
• Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivity
• Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks
• Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers
• 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?
• Towards moderate overparameterization: global convergence guarantees for training shallow neural networks
• Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks
• SGD Learns the Conjugate Kernel Class of the Network
• Diverse Neural Network Learns True Target Functions
• Overparameterized Nonlinear Learning: Gradient Descent Takes the Shortest Path?
• Quadratic Suffices for Over-parametrization via Matrix Chernoff Bound
• An Improved Analysis of Training Over-parameterized Deep Neural Networks
• Neural Networks Learning and Memorization with (almost) no Over-Parameterization
• Mildly Overparametrized Neural Nets can Memorize Training Data Efficiently
• Decoupling Gating from Linearity

Cited by in corpus (9)

• Computational Separation Between Convolutional and Fully-Connected Networks
• Noether: The More Things Change, the More Stay the Same
• The Effects of Mild Over-parameterization on the Optimization Landscape of Shallow ReLU Neural Networks
• Quantifying the Benefit of Using Differentiable Learning over Tangent Kernels
• The Connection Between Approximation, Depth Separation and Learnability in Neural Networks
• When Hardness of Approximation Meets Hardness of Learning
• Particle Dual Averaging: Optimization of Mean Field Neural Networks with Global Convergence Rate Analysis
• On the Power of Differentiable Learning versus PAC and SQ Learning
• Towards Understanding Learning in Neural Networks with Linear Teachers