Towards Understanding Learning in Neural Networks with Linear Teachers
arXiv:2101.02533
Abstract
Can a neural network minimizing cross-entropy learn linearly separable data? Despite progress in the theory of deep learning, this question remains unsolved. Here we prove that SGD globally optimizes this learning problem for a two-layer network with Leaky ReLU activations. The learned network can in principle be very complex. However, empirical evidence suggests that it often turns out to be approximately linear. We provide theoretical support for this phenomenon by proving that if network weights converge to two weight clusters, this will imply an approximately linear decision boundary. Finally, we show a condition on the optimization that leads to weight clustering. We provide empirical results that validate our theoretical analysis.
References in corpus (19)
- Neural Tangent Kernel: Convergence and Generalization in Neural Networks
- A Convergence Theory for Deep Learning via Over-Parameterization
- A Mean Field View of the Landscape of Two-Layers Neural Networks
- Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data
- 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 ReLU Networks on Linearly Separable Data: Algorithm, Optimality, and Generalization
- Recovery Guarantees for One-hidden-layer Neural Networks
- Gradient descent aligns the layers of deep linear networks
- Gradient Descent Maximizes the Margin of Homogeneous Neural Networks
- What Can ResNet Learn Efficiently, Going Beyond Kernels?
- Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputs
- Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks
- Why do Larger Models Generalize Better? A Theoretical Perspective via the XOR Problem
- Directional convergence and alignment in deep learning
- Decoupling Gating from Linearity
- Learning Parities with Neural Networks
- Implicit Bias in Deep Linear Classification: Initialization Scale vs Training Accuracy
- Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTK