Efficient Learning of CNNs using Patch Based Features

Alon Brutzkus, Amir Globerson, Eran Malach, Alon Regev Netser, Shai Shalev-Schwartz
Proceedings of the 39th International Conference on Machine Learning, PMLR 162:2336-2356, 2022.

Abstract

Recent work has demonstrated the effectiveness of using patch based representations when learning from image data. Here we provide theoretical support for this observation, by showing that a simple semi-supervised algorithm that uses patch statistics can efficiently learn labels produced by a one-hidden-layer Convolutional Neural Network (CNN). Since CNNs are known to be computationally hard to learn in the worst case, our analysis holds under some distributional assumptions. We show that these assumptions are necessary and sufficient for our results to hold. We verify that the distributional assumptions hold on real-world data by experimenting on the CIFAR-10 dataset, and find that the analyzed algorithm outperforms a vanilla one-hidden-layer CNN. Finally, we demonstrate that by running the algorithm in a layer-by-layer fashion we can build a deep model which gives further improvements, hinting that this method provides insights about the behavior of deep CNNs.

Cite this Paper

BibTeX
@InProceedings{pmlr-v162-brutzkus22a, title = {Efficient Learning of {CNN}s using Patch Based Features}, author = {Brutzkus, Alon and Globerson, Amir and Malach, Eran and Netser, Alon Regev and Shalev-Schwartz, Shai}, booktitle = {Proceedings of the 39th International Conference on Machine Learning}, pages = {2336--2356}, year = {2022}, editor = {Chaudhuri, Kamalika and Jegelka, Stefanie and Song, Le and Szepesvari, Csaba and Niu, Gang and Sabato, Sivan}, volume = {162}, series = {Proceedings of Machine Learning Research}, month = {17--23 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v162/brutzkus22a/brutzkus22a.pdf}, url = {https://proceedings.mlr.press/v162/brutzkus22a.html}, abstract = {Recent work has demonstrated the effectiveness of using patch based representations when learning from image data. Here we provide theoretical support for this observation, by showing that a simple semi-supervised algorithm that uses patch statistics can efficiently learn labels produced by a one-hidden-layer Convolutional Neural Network (CNN). Since CNNs are known to be computationally hard to learn in the worst case, our analysis holds under some distributional assumptions. We show that these assumptions are necessary and sufficient for our results to hold. We verify that the distributional assumptions hold on real-world data by experimenting on the CIFAR-10 dataset, and find that the analyzed algorithm outperforms a vanilla one-hidden-layer CNN. Finally, we demonstrate that by running the algorithm in a layer-by-layer fashion we can build a deep model which gives further improvements, hinting that this method provides insights about the behavior of deep CNNs.} }
Endnote
%0 Conference Paper %T Efficient Learning of CNNs using Patch Based Features %A Alon Brutzkus %A Amir Globerson %A Eran Malach %A Alon Regev Netser %A Shai Shalev-Schwartz %B Proceedings of the 39th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2022 %E Kamalika Chaudhuri %E Stefanie Jegelka %E Le Song %E Csaba Szepesvari %E Gang Niu %E Sivan Sabato %F pmlr-v162-brutzkus22a %I PMLR %P 2336--2356 %U https://proceedings.mlr.press/v162/brutzkus22a.html %V 162 %X Recent work has demonstrated the effectiveness of using patch based representations when learning from image data. Here we provide theoretical support for this observation, by showing that a simple semi-supervised algorithm that uses patch statistics can efficiently learn labels produced by a one-hidden-layer Convolutional Neural Network (CNN). Since CNNs are known to be computationally hard to learn in the worst case, our analysis holds under some distributional assumptions. We show that these assumptions are necessary and sufficient for our results to hold. We verify that the distributional assumptions hold on real-world data by experimenting on the CIFAR-10 dataset, and find that the analyzed algorithm outperforms a vanilla one-hidden-layer CNN. Finally, we demonstrate that by running the algorithm in a layer-by-layer fashion we can build a deep model which gives further improvements, hinting that this method provides insights about the behavior of deep CNNs.
APA
Brutzkus, A., Globerson, A., Malach, E., Netser, A.R. & Shalev-Schwartz, S.. (2022). Efficient Learning of CNNs using Patch Based Features. Proceedings of the 39th International Conference on Machine Learning, in Proceedings of Machine Learning Research 162:2336-2356 Available from https://proceedings.mlr.press/v162/brutzkus22a.html.

Related Material