Learning One Convolutional Layer with Overlapping Patches

By Surbhi Goel, Adam R. Klivans, Raghu Meka. 2018

81 citations recorded by the source corpus.

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$.

Subfields: Model Architectures

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Model Architectures

Citations in the corpus

Generalization Guarantees for Neural Networks via Harnessing the Low-rank Structure of the Jacobian (2019, background): “Generalization properties of stochastic gradient descent is extensively studied empirically [34, 28, 50, 16, 29, 24, 25].”
A Convergence Theory for Deep Learning via Over-Parameterization (2018, background): “There is sequence of work about one-hidden-layer (multiple neurons) CNN (Brutzkus & Globerson, 2017; Du et al., 2018b; Goel et al., 2018; Oymak, 2018; Zhong et al., 2017a).”
Learning Neural Networks with Two Nonlinear Layers in Polynomial Time (2017, background): “The invention of alternatives to gradient descent is an important goal in deep learning (there are simple examples of shallow convolutional nets where stochastic gradient descent is outperformed by other algorithms (Goel et al. (2018))).”
Gradient Descent for One-Hidden-Layer Neural Networks: Polynomial Convergence and SQ Lower Bounds (2018, background): “Another line of work investigates classes of such networks that can be learned in polynomial time, notably using tensor methods [21, 28] and polynomial kernels [15, 17], more direct methods with assumptions on the structure of the network [16, 13] and a combination of tensor initialization followed ”
Learning Two-layer Neural Networks with Symmetric Inputs (2018, methodology): “The main challenge here is that y is not a linear function on x. Goel et al. (2018) gave a crucial observation that allows us to deal with the non-linearity: Lemma 1.”
Understanding Straight-Through Estimator in Training Activation Quantized Neural Nets (2019, methodology): “They showed the convergence of the so-called Convertron algorithm, which uses the identity STE in the backward pass through the leaky ReLU layer.”