Learning One Convolutional Layer with Overlapping Patches

Abstract

We give the first provably efficient algorithm for learning a one hidden layer convolutional network with respect to a general class of (potentially overlapping) patches. Additionally, our algorithm requires only mild conditions on the underlying distribution. We prove that our framework captures commonly used schemes from computer vision, including one-dimensional and two-dimensional "patch and stride" convolutions. Our algorithm-- $Convotron$ -- is inspired by recent work applying isotonic regression to learning neural networks. Convotron uses a simple, iterative update rule that is stochastic in nature and tolerant to noise (requires only that the conditional mean function is a one layer convolutional network, as opposed to the realizable setting). In contrast to gradient descent, Convotron requires no special initialization or learning-rate tuning to converge to the global optimum. We also point out that learning one hidden convolutional layer with respect to a Gaussian distribution and just $one$ disjoint patch $P$ (the other patches may be arbitrary) is $easy$ in the following sense: Convotron can efficiently recover the hidden weight vector by updating $only$ in the direction of $P$.

Cited by in corpus (16)

• A Convergence Theory for Deep Learning via Over-Parameterization
• Understanding Straight-Through Estimator in Training Activation Quantized Neural Nets
• Implicit Regularization and Momentum Algorithms in Nonlinearly Parameterized Adaptive Control and Prediction
• Learning Two Layer Rectified Neural Networks in Polynomial Time
• How Many Samples are Needed to Estimate a Convolutional or Recurrent Neural Network?
• A Local Convergence Theory for Mildly Over-Parameterized Two-Layer Neural Network
• Hardness of Learning Neural Networks with Natural Weights
• An Approximation Algorithm for training One-Node ReLU Neural Network
• Guaranteed Recovery of One-Hidden-Layer Neural Networks via Cross Entropy
• Improved Learning of One-hidden-layer Convolutional Neural Networks with Overlaps
• Towards Lower Bounds on the Depth of ReLU Neural Networks
• A Deep Conditioning Treatment of Neural Networks
• Self-Regularity of Non-Negative Output Weights for Overparameterized Two-Layer Neural Networks
• Nonlinear Inductive Matrix Completion based on One-layer Neural Networks
• From Local Pseudorandom Generators to Hardness of Learning
• Learning stochastic decision trees