Provable Learning of Convolutional Neural Networks with Data Driven Features
Lists
Only you see this
Abstract
Convolutional networks (CNN) are computationally hard to learn. In practice, however, CNNs are learned successfully on natural image data. In this work, we study a semi-supervised algorithm, that learns a linear classifier over data-dependent features which were obtained from unlabeled data. We show that the algorithm provably learns CNNs, under some natural distributional assumptions. Specifically, it efficiently learns CNNs, assuming the distribution of patches in the input images has low-dimensional structure (e.g., when the patches are sampled from a low-dimensional manifold). We complement our result with a lower bound, showing that the dependence of our algorithm on the dimension of the patch distribution is essentially optimal.
BibTeX
@inproceedings{brutzkus2022provable,
author = {Alon Brutzkus and Amir Globerson and eran malach and Shai Shalev-Shwartz},
title = {{Provable Learning of Convolutional Neural Networks with Data Driven Features}},
booktitle = {International Conference on Learning Representations},
year = {2022},
url = {https://openreview.net/forum?id=3Li0OPkhQU},
}Loading related content...