Learning One Convolutional Layer with Overlapping Patches

Surbhi Goel; Adam Klivans; Raghu Meka

ICML 2018oral90 citations

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 under 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–

BibTeX

@InProceedings{pmlr-v80-goel18a,
  title = 	 {Learning One Convolutional Layer with Overlapping Patches},
  author =       {Goel, Surbhi and Klivans, Adam and Meka, Raghu},
  booktitle = 	 {Proceedings of the 35th International Conference on Machine Learning},
  pages = 	 {1783--1791},
  year = 	 {2018},
  editor = 	 {Dy, Jennifer and Krause, Andreas},
  volume = 	 {80},
  series = 	 {Proceedings of Machine Learning Research},
  month = 	 {10--15 Jul},
  publisher =    {PMLR},
  pdf = 	 {http://proceedings.mlr.press/v80/goel18a/goel18a.pdf},
  url = 	 {https://proceedings.mlr.press/v80/goel18a.html},
  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 under 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–