Provable Learning of Convolutional Neural Networks with Data Driven Features
Authors: Alon Brutzkus
Amir Globerson
eran malach
Shai Shalev-Shwartz
Venue: ICLR 2022 Submitted (2022)
Keywords: Deep learning theory
convolutional neural networks

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.

Under review as a conference paper at ICLR 2022
PROVABLE LEARNING OF CONVOLUTIONAL NEURAL NETWORKS WITH DATA DRIVEN FEATURES
Anonymous authors Paper under double-bling review
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 semi-supervised algorithm, that learns 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, 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.
INTRODUCTION
Convolutional Neural Networks (CNNs) have become a primary tool for machine learning on image data, surpassing the performance of "traditional" machine learning algorithms such as linear classifiers or kemel-SVM. On the other hand, unlike such simpler classifiers, neural networks are known to be computationally hard to learn. Namely, has been shown that, under mild cryptographic assumptions, there is no efficient algorithm that can find, under any distribution, a neural network with good, or even non-trivial, test performance. This true even if we assume that there exists neural network that perfectly labels the distribution (Livni et al. 2014).
How can we explain this gap between the practical success and the theoretical hardness of neural networks? One possible answer is that we should introduce distributional assumptions into the analysis of learning algorithms. That is, while in theory we would like our algorithms to perform well under any possible distribution of examples, in practice "natural" distributions appear to enjoy certain structure that traditional theoretical analysis does not take into account. Therefore, it seems that in order to give theoretical analysis that is relevant practice, we must find assumptions the underlying data distributions that are both a) realistic for natural data and b) allow us to guarantee efficient learnability of neural networks.
In this work, we explore such possible distributional assumptions. Specifically, we study learning convolutional functions over data with structure that similar to natural images. Our main assump- tion is that the distribution of "important" patches in the images has a low-dimensional structure (c.g., lies on dimensional manifold). Under this assumption, we analyze semi-supervised algorithm that first constructs a representation based on an unlabeled set of examples, and then learns a linear classifier over the produced representation. Note that this is an improper learning algorithm for learning CNNs. Our algorithm is very similar to the semi-supervised algorithm introduced by Coates et al. (201 which empirically has performance which close to the performance of neural networks several image datasets (Thiry al.) 2021). We show that our algorithm has run-time and sample complexity that depend on the covering number of the space of patches, and therefore the algorithm is efficient when the patches have dineenenniioall structure. We complement this result with a lower bound, showing that such dependence on the covering number is essentially optimal, ie., any learning algorithm must depend on this number in the same way that our algorithm does.

---

Under review as a conference paper at ICLR 2022
2 RELATED WORK
Learning with Data-Dependent Representation Learning linear classifiers over fixed represen- taions of the imput is very well-known and well-studied approach. Specifically, kernel methods SSyaw--Taylor et al. 2004) and random features (Rahimi et al. 2007] Rahimii & Recht 2008 are some prominent examples of such learning methods. However, these methods are known to have their limitations, due to the fact that the representation is fixed a priori, and cannot adapt to the learning task (see for example Kamath et al. 2020);; [aniely & Malach (2020); MMlach et al. (2021)) Therefore, using representations that depend on the properties of the input data instead of fixing the representation in advance seems like sensible way to improve performance. Indeed, such data- dependent representations have been explored for learning over image data. Specifically, the work of Coates et al. (20TT) studies a learning algorithm for image data, which constructs a data-dependent representation in a very similar fashion to the algorithm we analyze in this work. However, Coates (et al. (201T) focuses on empirical evaluation of the algorithm, while our work gives a theoretical analysis of the algorithm. A more recent work by Thiry et al. (2021) suggests similar patch-based representation, and shows that it achieves impressive empirical performance on complex datasets such CIFAR- 10 and ImageNet. They do not perform theoretical analysis. Another related line of works study kernels constructed via random neural networks, such as the Neural Tangent Kernel (Du
cet al. 2019 2018b Arora et al. 2019: Ji & Telgarsky 2019 Cao & Gu. 2019: Jacot et al. 2018).
Learning Neural Networks under Distributional Assumptions As mentioned earlier, efficient learning of neural networks without any distributional assumptions is known to be hard (e.g.. Klivanss & Sherstov (2009): Livni et (2014). In fact, in some cases learning neural networks under simple distributions such Gaussian or Uniform distributions was shown be hard for large family of
algorithms (see Diakonikolas et al. (2020). This fact motivates finding the "right" distributional assumptions, that are both realistic (in some sense), and allow efficient learning of neural networks.
To this end, various works have studied learning of feed-forward networks (Ge et al. (2018 Awasthi al. (202T)) and convolutional networks under different distributional assumptions (Brutzkus & Globerson (2017): Oymak (2017)]0yymkk
& Soltanolkotabi (2018); Du & Goel (2018) 8); Malach &
(2018): Brutzkus & Globerson (2020); Du et al. (2)18a)). However, these distributional assumptions
often seem far from fitting natural data distributions. Our work gives simple characterization of data distributions that both seems reasonable for natural data, and allows efficient learning of convolutional networks.
3 PRELIMINARIES
We begin by describing the problem setting considered in the paper. First, we introduce our assump- tions on the data distribution and the labeling function. We then describe the learning algorithm that we analyze.
3.1 DATA GENERATING DISTRIBUTION
We consider distributions over images, where each image is of size dj. Let X' C Rdd be the input space and y = } be the label space. Each image contains n patches, i.e. n sub-images, where each sub-image is of size dp. We identify each of the patches in the image with a sequence of indices. That is, we define n sequences A1,..., A, such that for every j. A, = (f1,..., kap is a sequence of indices satisfying i1, ......, idr S [dr]. So, A, defines the set of indices of image pixels associated with the j-th patch, and we denote the j-th patch by x[j] s.t.:
x(j] = (XA, (d)(d)))
Note that we do not assume that A A1...., An are disjoint, so the same pixel can belong multiple patches. We now introduce our assumption on the function which labels the input distribution. Consider the following generalization of convolutional networks:
Definition 3.1 (Generalizd Convolutional Function), Let f Rd + R² be some function. We say that F X + R is Generalized Convolutional Function (GCF) over f if
F F'(x)= = Σ (1) (x(())
(1)
2

---

Under review as a conference paper at ICLR 2022
where u()), "u.,.... (())
.....,(())
R*
Observe that a GCF is generalization of CNN in two aspects, First, we allow the function f to be any arbitrary function over patches, and we do not restrict only to be neural network. Second, we allow the patch indices to be arbitrary (as discussed above). which allows implementing overlapping or non-overlapping convolutions, dilated convolutions and also arbitrary choice of "patches" from the image. Our main result shows algorithm that can learn GCFs (under appropriate assumptions), and therefore can be applied to standard CNNs, as well as broader family of functions.
Let I be some distribution over X' x V, i.e. distribution of labeled examples. Given our definition of GCFs, we make the following assumption on I:
Assumption 3.2. There exists a GCF F* X + over some function f Rdd R such that:
For any (x. 3) ~I (F*(x) 1.
f is L-Lipschitz, for some Lipschitz constant 0.
There exists some M > 0 such that [l.(())]l s M for every u Rdp,
There exists some constant B > 0 such that the weights of F* satisfy E | < B.
Simply put, we assume that the distribution I is realizable (with a margin) by a GCF over a Lipschitz and bounded function.
3.1.1 STANDARD CNN ARCIITECTURES
We now show that distribution labeled by standard CNN architecture, with Lipschitz and bounded activation function, satisfies Assumption 3.2 Since a CNN is an instance GCF, all we need to show is bound on the Lipschitz constant L and bound the norm M of the relevant function f. We show this for both deep and shallow (one hidden-layer) CNNs.
Let be 1-Lipschitz activation function. Then, if f(x) over f is simply a one hidden-layer CNN. In this case, we have the following result:
(Wx), for some W RRXP, GCF F
Theorem 3.3. Let a be a 1-Lipschitz activation s.f. sup, [x)) S c. Then, any distribution over X' x y labeled by one hidden-layer CNN F(x)= = Σ. (u ( (Wx(())))) with activation and
weights W E &R& Rkxdp; (1)). u E R satisfies Assumption 3.2 with L = || and M = cv k.
The above follows immediately fromt the following Lemma:
Lemma 3.4. Let a TR > be a 1-Lipschitz activation function. Let f RRdr - R& be a function such that (xx (Wx), for W E TR. exdr, Then, f is ||W -iisschhz
Similarly to the above, if we let be deep neural network with activation a, namely f(x) = a (W (. ( (W) then a GCF F over f is equivalent to a depth & C In this case, we have the following result:
Theorem 3.5. Let be 1-Lipschitz activation s.t. sup, [a(2)) c. Then, any distribution X x y labeled by a dpeth CNN network
F(x) = - (()) (
(u))
with activation a and weights ((I) E Rxdd W() W() E R ,..., (.....,
(n) E R
satisfies Assumption 3.2 with = II. [| and M = cvk.
This follows immediately from the following Lemma:
Lemma 3.6. Let f (1() og.. .oo....or oo (1)), (1()),,e for some 1-Lipschitz activation a. Then,
is II. [WO]] Lipschitz
Forraally F will be depth & CNN if ((), ...., ( convolutions. However, since convolutions linear operations, our definition describes larger family of functions.
3

---

Under review as a conference paper at ICLR 2022
Note that the bound on the Lipshchitz constant of deep CNNs in Theorem 3.5 the norm of the weights. That is, the weight matrices have norm > 1. then the Lipschitz constant grows exponentially with depth, which may be unsatisfactory for deep networks. However, do note that this is only an upper bound on the Lipschitz, constant of the network, and fact we can expect that deep networks in practice have much smaller Lipschitz constatns (see Combettes & Pesquet (2020); Jordan & Dimakis 2020 ).
grows product of
3.2 THE COVERING NUMBER OF PATCH DISTRIBUTIONS
Let I be a distribution over X' y that satisfies Assumption 3.2 with some GCF F over f. We assume that the marginal distribution of I on X has density function and we denote its support by supp(Z). We denote by Pz the set of supported patches in the distribution I which have non-zero value under f. Namely, Pr_ {x [i] x supp(Z), f(x(i]) + O, S i S n). In cases where the distribution I is clear from the context, we simply use == Pr. So, P the set of patches that both have non-zero probability to appear in images sampled from I, and which are not "ignored" by the GCF, This captures the fact that for image classification tasks, some patches of the image may be very important for determining the object class, while other patches can simply be ignored. The set P is therefore exactly this set of "important" patches.
The sample complexity and the run-time of our algorithm depend on one important factor the covering number of the set P. In general, an r-covering number is defined as follows:
Definition 3.7. For a set A, we say that is an r-covering of A if A C. UvecB,(v), where (v) is the &g ball of radius centered around v. The r-covering number of set A, denoted by (A). is the minimal size of an r-covering of A \Vershynn 2018).
So, the main ingredient in our analysis showing that if the covering number of the P is small (for example. if the important patches lie on a -iwddimnniooall manifold, as described in Section 4.2) then our algorithm can efficiently learn GCFs, and therefore CNNs. Notice that assuming that (P) is small is distributional assumplion, and it does not necessarily hold in general. In fact, in some cases the covering number of P can exponential in the patch size dp, or even unbounded (if the distribution of patches is unbounded), in which case our bounds become vacuous. That said, we show in Section 4.3 that in general, such dependence on the covering number is unavoidable for learning GCFs.
3.3 LEARNING ALGORITHM
We now describe the learning algorithm analyzed in this work. The algorithm has two stages. In the first stage, which unsupervised, dictionary of patches is learned by clustering patches from an unlabeled set of examples. In the second stage, which is supervised, a linear classifier is learned over a feature-map generated using the patch dictionary. We begin by describing the patch embedding feature-map. and continue with a detailed description of the learning algorithm.
vr} C Rd be a set of patches. We refer to as a dictionary. We next describe how to use dictionary to obtain representation of given image x.
Patch embedding. Let D = [v.,...,
For distance parameter + > 0, we define the patch-embedding ((; Rd + {0, 13 where for every i < I:
{
|V. ull ST
(n: D,T):
otherwisc
Namely, & maps given patch vector indicating all the patches in the dictionary D that 7-close to We use normalized patch embedding & defined as:
duu; D,
b(u D, = | uu D,
Using the embedding o. define an input-embedding (c; D) : {0, 10,,
(x: D, 7) (
...., - D,7)
(3)
4

---

Under review as a conference paper at ICLR 2022
P2
Pw
3/2
(<+[1]) 1/2
1/2
1/2
x[1]
x[2]
((x[2)
1/3
1/3
0
1/3
x[[]
x(n]
(x([R)) -
1/5 1/s
1/s
1/s
1/3
1/3 3/s
Figure 1: Construction of the patch embedding representation. First, each patch x[i] is mapped to normalized indicator vector, indicating all its neighbours in ball of radius within the dictionary D. Then the representations all the patches are concatenated together to obtain a representation for the full image.
Algorithm 1 Clustering
Input: Set of patches P.. N > 0.
Pick an arbitrary u E Pa.
Set D {u}.
for i = 2,..., do:
Find Pa which maximizes minueD ||v u/|-
D - D U {v}
return D.
Figure 2: Patch clustering algorithm.
That is, maps each patch of x using the patch embedding e and concatenates all patch embeddings. Figure showr shows illustraction of how the embedding constructed using the dictionary and the input image x.
Learning algorithm. We consider a semi-supervised algorithm APatch for learning from image data, which similar to the algorithm presented by Coates et al. 12.1T). The algorithm takes two parameters: the size the dictionary N, and the patch embedding radius 7. The algorithm consists of unsupervised stage, followed by supervised stage.
Unsupervised stage: We assume that we have access to an unlabeled training dataset S, S supp(Z). Define the set P, [x[i] x E Su, 15 i S n). i... the set of all patches of images in S.. We perform clustering procedure which given P, and number N, returns set of patches 1) of size N. For our theoretical analysis we will consider a greedy clustering algorithm, which performs farthest-first traversal. The clustering algorithm is described in Figure I This algorithm was originally proposed for the k-center problem and it is 2-approximation algorithm (Gonzalez 1985 In practice, other clustering algorithms can be considered, such as k-means.
Supervised stage; Here we assume that we have dictionary D = (V1..., vN} of patches obtained by the unsupervised stage. We assume that we given training set S {(11, v/)...., (xm. Vm } of labeled points, sampled IID from the distribution I. Then, we perform hard linear SVM on the training set S. {( (x1; D, v1), (#(x.. D,T), vm) }. and return predictor E N-N- s.t.
arg min s.t. E [m], y: (w, (xx;; D,T)) 2
|
(Hard-SVM)
w
"See also Williamson & Shmoys 201
Section 2.2.

---

Under review as a conference paper at ICLR 2022
The prediction of the label of point (x, y) ~ I is sign ((w, o(x: D, 7))).
4 MAIN RESULT
In this section we give a detailed analysis of the algorithm presented in the previous section. Our main result shows that for every distribution I satisfying Assumption 3.2 with some fixed constants L, .M and B such that the covering number satisfies (Pr) I N (with some proper choice of r), given a large enough sample, our algorithm returns predictor with small error.
To state this more formally, we show learnability result, using the following notion of learnability:
Definition 4.1. Let be a family of distributions over X' y. We say that a learning algorithm A PAC learns the family P, if every c, E (0, 1 1/4), there exists some m(c, 5) s.I. for every I E D the algorithm A uses m((e 6) samples from I and returns a hypothesis h such that w.p. Z - 6:
P P(xx))I [x) + yl S
So, let PL.MBB.N. be the family of distributions satisfying Assumption 3.2 with constants L, M, B and for which (P2) < N. Then, we show that APathh PAC learns the family PL.M, for any r S 1/22BB)) Note that this definition only addresses the supervised stage, and we will show holds under a condition on the unsupervised stage.
We start by bounding the sample complexity of our algorithm assuming that our unlabeled training set (the data used for the unsupervised stage) is sufficient for covering the patch set P. Next, in Section 4.1. we show that this assumption is essentially satisfied when our unlabeled training set is large enough, and we give a bound on the required sample size of the labeled as well the unlabeled training data (without the additional assumption).
So, we start by making the following assumption:
Assumption 4.2. There exists some S 241.B and some set C s.t. C is an r-covering of P of size (P). and for each v E C, there exists Pu, such that u E (v).).
That is, we assume that the unlabeled training set is representative in the sense that the patches in the unlabeled set (denoted P.) cover the "important" patches of the distribution (i.e., the set P). Under this assumption (and the realizability assumption introduced in the previous section), we prove that our algorithm PAC learns the family of distributions PLL.MB,N.1//C (2ALL)) via the following theorem:
Theorem 4.3. Fix (0, 1/4). Let I be some distribution which satisfies Assumption 3.2 and
assume that S, satisfies Assumption 4.2 Then, running algorithm Apaeh with parameters N (y) and = returns a hypothesis s.s. with probability at least 5:
nM2
log(3)
P(x.))~I [x(x) # v] S av
+
(4)
m
m
for some universal constant > 0.
We give the full proof of the theorem in Appendix and give sketch of the argument here. To prove Theorem 4.3) we show that the function F* can be approximated by linear classifier over the representation Φ Specifically, we use the fact that the set of patches from the unlabeled data P. covers the set P of patches with non-zero probability and non-zero value under f. So. after clustering, we still get a good covering. Next, we define the following vector:
w = f(v)). (um),
(u)). .... (1 f(vi)) (..
(u f(x)))))))) R No.
where the v, are the vectors in the dictionary D from the unsupervised stage. Then, using the guarantees on the unsupervised stage (that the dictionary covers the set patches), the function F(x) = (w, (x; D,T)) can be shown to approximate F*. Thus, the algorithm succeeds because can get from the unsupervised stage vectors that cover the set of patches, which in turn allows it to produce a sufficiently rich representation for learning the distribution with a linear classifier.
The above result shows how the error of our algorithm decays with the (labeled) sample size, assuming the unlabeled training set is "good". This immediately gives a bound on the sample complexity the algorithm:

---

Under review as a conference paper at ICLR 2022
Corollary 4.4. Fix L,M.B,N O and let S 241,B" Then, Apatch with parameters N and т T= 6r, given access to a sample Su satisfying Assumption 4.2 PAC learns PL.M.B.N. with sample complexity:
m(e, 6) a n B2 B 2
l0g(1/8)
In Section 4.3 we show that the dependence of the sample complexity nN,(P) is optimal.
As for the run-time our algorithm, notice that both the unsupervised and the supervised stage use efficient (polynomial time) algorithms. The run-time of the clustering algorithm used in the unsupervised stage is O(N2dp), and the hard SVM used in the supervised stage runs in time O(mn"N N²), depending the implementation.
4.1 RELAXING THE ASSUMPTION UNSUPERVISED LEARNING
In this section show learning guarantee which does not require Assumption 4.2 We denote ma = [. So, we show that if my is large enough, then Assumption 4.2 is essentially satisfied with high probability:
Theorem 4.5. Let 8',8,8' E (0,1). F I 24LB and let N (P). Assume that my 2 N o log (3) and m S 27. Then, running algorithu Apach with parameters N and T = 6r returns hypothesis h s.1. with probubility at least 8' - -
5
log(
P (xxy)~II [h(x) # vl S ay
+ 01
+
(5)
for some universal constant a.
The proof of Theorem 4.5 is very similar to the proof of Theorem 4.3 except that now we do not assume that we have an unlabeled set that covers the patch space. Rather, we prove that if we sample enough unlabeled examples from the marginal distribution over the inputs, such "good" data is guaranteed with high probability. This done by observing all the balls from the covering of that have at least distributional mass, and showing that sample from each of them is guaranteed with high probability. The full proof of the theorem is given in Appendix B
Using the above result, we can prove learnability result, which does not depend on Assumption To do so, we use more refined version of PAC learning, which distinguishes between labeled and unlabeled sample complexity:
Definition 4.6. Let be a family of distributions over X' We say that a learning algorithm A PAC learns the family P. for every e, (0, 1/4), there exists some m(c,8) 8) and male, 5) s.t. for every I E D, the algorithm uses mie, 8) labeled samples and mu(e, 8) unlabeled samples from and returns hypothesis h such that w.p. 6:: 6:
P(xy)~ 1x() + se Se
Note that the two notions of PAC learnability (of Definition 4.1 and [.6) are equivalent, as we can always use some labeled examples and disregard their labels, or otherwise not use unlabeled data at However, the later definition accounts separately for labeled and unlabeled sample complexity, which often can be of interest. So. Theorem 4.5 implies the following lcarnability result:
Corollary 4.7. Fix L, B, N and let 241.3
1
Then, Apatch with parameters N and
6r, given access to a sample S, satisfying Assumption 4.2 PAC learns PL.MBB.N. with sample complexity:
m(c, 5) 40 B 2
log(3/0) and m,,c, 6N mlee 8)
33N
log
2
8
'vee the randomness of and

---

Under review as a conference paper at ICLR 2022
Table 1: Test classification accuracies on MNIST, Fashion MNIST (FMNIST) and noisy FMNIST.
DATA SET
DEEP CNN
SHALLOW CNN
OUR ALGORITHM
MNIST
99.11 0.01 92.5 0.1
98.81 0.04
97.7 1 0.09
FMNIST
90.61 0.1
89.5 1 0.1
NOISY FMNIST
73.1 = 0.1
4.2 FROM INTRINSIC DIMENSION TO COVERING NUMBER
Our analysis, as shown in previous sections, shows that the sample complexity and run-time of our algorithm depends on one important measure the covering number of the patch set P. Observe that the covering number is often used mcasure of the intrinsic dimension of some given space. For example, the d-dimensional ball B has covering number (B*) = Ca(1/r)², and note that this remains true even if the ball is embedded in space with larger extrinsic dimension. More generally, a bounded d-dimensional manifold has a covering number that grows exponentially with the intrinsic dimension d (which again can be much smaller than the extrinsic dimension). For more examples and further discussion on the relation between the covering number and measures of intrinsic dimension refer Falconer [2004] Hamm & Steinwart 2020
All in all, we see that if the distribution of "important" patches (captured by the set P) is concentrated on low-dimensional structure (e.g., on a low-dimensional manifold), we can expect the covering number of P to be moderate. On the other hand, if the patches fill truly high-dimensional space, then our complexity guarantees becomes impractical, as these can grow exponentially with the dimension. That said, we show in the next section that such dependence on the covering number is essentially unavoidable, if one wishes learn GCFs small loss.
4.3 SAMPLE COMPLEXITY LOWER BOUND
In the previous section, showed that with sample complexity that depends the number of patches n and the covering number N == (P), our algorithm returns with high probability a hypothesis with small loss. Now, we will show that dependence on N is unavoidable for guaranteeing such PAC learnability result. Namely, any algorithm that PAC learns all distribution with covering number N, must have sample complexity of ((nN)):
Theorem 4.8. Let A be some learning algorithm that uses samples. Assume that for every I which satisfie Assumption 3.2 and for which N1/1 (z)) = N, A returns w.p. at least 7/8 a hypothesis 3 1/8. Then, m 2 n2/22
s.f. P(x (x)
The proof of Theorem 4.8 follows the same arguments as standard sample complexity lower bounds, e.g. the No-Free-Lunce Theorem (for example, see Section 5 in -Shale-SSwwatze & BeviD (2114). The full proof is given in Appendix B
From the above result we can derive a lower bound on the sample complexity of any algorithm that PAC learns N..MIB,N.A/L
Corollary 4.9. Fix some L,, .,, B,N it must hold that for all c, (0.1/8).
N > O. Then, for any algorithm A that PAC learns PL.MBB.N1/L.
nN
m(e,5) 2
2
EXPERIMENTS
In this section we perform experiments to show the efficacy of our method in practice and obtain insights from our theoretical results. Coates et al. (2011) and Thiry et al. (2021) have performed extensive experiments on algorithms similar to ours. They showed that the performance of their algorithm is close to the performance of neural networks challenging computer vision datasets. For completeness, we perform experiments on MNIST (LeCun) 1998) and Fashion MNIST (FMNIST) (Xiao al. 2017). We compare the performance of algorithm with shallow CNN (2 layers) and
8

---

deeper CNN (4 layers). We implement the clustering stage of our algorithm with k-means after performing whitening of the patches, similar to cofCesses et al. (2011). We used the whole training set for the unsupervised stage. See Section C for further details the experiments. Table shows the Under review as a conference paper at ICLR 2022
results. We see that for both MNIST and FMNIST, the semi-supervised algorithm has comparable performance the shallow CNN and the deep CNN has the best performance.
Our theorems suggest that the sample complex- ity of the semi-supervised algorithm depends the covering number of the patches. Covering numbers are related the number of clusters of the data. If a dataset has low covering number, should possible to cluster the dataset with small number of clusters, and vice versa. Thus, by our theoretical results, we should expect that for data in which clustering algorithms work better, our algorithm should have better test per- formance. To check this, plotted the mean distance to center as a function of the number of clusters for three datasets MNIST, FMNIST and a noisy version of FMNIST. Note that all patches are whitened and therefore the distances are rel- atively comparable between datasets. This is also illustrated by the fact that for few clusters the mean distances to the centers are roughly the same for all datasets. The mean distance to the center measures how well the data is clus- tered for a given number of clusters. Figure 3 shows the results for three datasets. We see that MNIST is the most well clustered while the noisy FMNIST is the hardest to cluster. This correlates with the test performances in T where on MNIST our algorithm has the best test performance and on noisy FMNIST it has the worse. This is in line with our theoretical results, which suggest that learning difficulty should be correlated with covering numbers.
MNIST
4.5
FMNIST
Mean distance center
Noisy FMNIST
4.0
3.5
3.0
2.5
2.0
1000
2000
3000
4000
Num clusters
Figure 3: Mean distance to center for various num- ber of clusters.
6 DISCUSSION AND FUTURE WORK
In this work, we showed that although learning convolutional networks may be computationally hard the general case, introducing distributional assumptions allows us to learn a broad class of convolu- tional functions efficiently. Specifically, assumed that the "important" patches of the input have moderate covering number (i.c., the patches are well-clustered). Under this assumption, we proved that our step semi-supervised learning algorithm PAC learns the distribution. Following this, it is also of interest to study the behavior of other learning algorithms under the low covering number assumption. Specifically, understanding whether "vanilla" SGD on standard CNN architecture can learn such distributions efficiently is of great interest.
Furthermore, while our assumption on the patches covering number does seem capture some properties of natural distributions, it might still be too "generous". Since the covering number can grow exponentially with the extrinsic dimension of the patches, it might be the case that for complex datasets this number is still too large to guarantee "efficient" Icarnability. So, promising future direction is to find distributional properties that lead to similar learnablility results, and yet are expected to behave more moderately on natural data. Another possible direction for research is to find distributional properties that use the specific structure of CNNs more explicitly. For example, CNNs with ReLU activation induce separation of the patch space to linear regions. So, we can use different sort of covering, where each linear region has at least one representative patch, such that all neighbouring patches can be associated with this linear region. Finally, another direction for future work is to explore similar distributional properties for learning other neural network architectures, such RNNs and transformers.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learning, pp. 322-332, 2019.
Pranjal Awasthi, Alex Tang, and Aravindan Vijayaraghavan. Efficient algorithms for learning depth-2 neural networks with general relu activations. arXiv preprint arXiv:2107.10209, 2021.
Peter L Bartlett and Shahar Mendelson. Rademacher and gaussian complexities Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463-482, 2002.
Stéphane Boucheron, Olivier Bousquet, and Gábor Lugosi. Theory of classification: A survey of some recent advances. ESAIM: probability and statistics, 9:323-375, 2005.
Alon Brutzkus and Amir Globerson. Globally optimal gradient descent for a convnet with gaussian inputs. In International Conference on Machine Learning, pp. 605-614, 2017.
Alon Brutzkus and Amir Globerson. An optimization and generalization analysis for max maxx-oooiigg networks. arXiv preprint arXiv:2002.09781, 2020.
Yuan Cao and Quanquan Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. In Advances in Neural Information Processing Systems, pp. 10836-10846, 2019.
Adam Coates, Andrew Ng, and Honglak Lee. An analysis of single-layer networks in unsupervised feature learning. In Proceedings of the fourteenth international conference on artificial intelligence and statistics, pp. 215-223, JMLR Workshop and Conference Proceedings, 2011.
Patrick L Combettes and Jean- Chrrstohtt Pesquet. Lipschitz certificates for layered network structures driven by averaged activation operators. SIAM Journal on Mathematics of Data Science, 2(2): 529-557, 2020.
Amit Daniely and Eran Malach. Learning parities with neural networks. Advances in Neural Information Processing Systems, 33, 2020.
Ilias Diakonikolas, Daniel M Kane, Vasilis Kontonis, and Nikos Zarifis. Algorithms and sq lower bounds for pac learning me-hidden-laaer relu networks. Conference on Leurning Theory, pp. 1539. PMLR, 2020.
Simon Du, Jason Lee, Yuandong Tian, Aarti Singh, and Barnabas Poczos. Gradient descent learns mne-hidden-layer cnn: Don't be afraid of spurious local minima. International Conference on Machine Learning, pp. 1339-1344 1348. PMLR, 2018a.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In International Conference on Machine Learning, pp. 1675- 1685, 2019.
Simon Du and Surbhi Goel. Improved learning of one-hidden-layer convolutional neural networks with overlaps. arXiv preprint 1805v:880.0777 2018.
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. International Conference on Learning Representations, 2018h 8b.
Kenneth Falconer. Fracial geometry: mathematical foundations and applications. John Wiley & Sons, 2004.
Rong Ge, Rohith Kuditipudi, Zhize Li, and Xiang Wang. Learning two-layer neural networks with symmetric inputs. arXiv preprint arXiv:1810.0679 2018.
Teofilo F Gonzalez. Clustering to minimize the maximum intercluster distance. Theoretical computer science, 38:293-306, 1985.
Thomas Hamm and Ingo Steinwart. Adaptive learning rates for support vector machines working on data with low intrinsic dimension. arXiv preprint arXiv:2003.06202 2020.
10

---

Under review as a conference paper at ICLR 2022
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization neural networks. In Advances in neural information processing systems, pp. 8571-8580, 2018.
Ziwei and Matus Telgarsky. Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow relu networks. In International Conference on Learning Representations, 2019.
Matt Jordan and Alexandros G Dimakis. Exactly computing the local lipschitz constant of relu networks. arXiv preprint arXiv:2003.01219, 2020.
Pritish Kamath, Omar Montasser, and Nathan Srebro. Approximate is good enough: Probabilistic variants of dimensional and margin complexity. In Conference Learning Theory, pp.
PMLR, 2020.
Adam R Klivans and Alexander A Sherstov. Cryptographic hardness for learning intersections of halfspaces. Journal of Computer and System Sciences, 75(1):2-12 2009.
Yann LeCun. The mnist database of handwritten digits. http://yann. lecun. com/exdb/mmist/, 1998.
Roi Livni, Shai Shalev-Shwatzz and Ohad Shamir. On the computational efficiency of training neural networks. In Advances in Neural Information Processing Systems, pp. 855-863, 2014.
Eran Malach and Shai Shalev-Shwartz. A provably correct algorithm for deep learning that actually works. arXiv preprint arXiv: /80. 099222 2018.
Eran Malach, Pritish Kamath, Emmanuel Abbe, and Nathan Srebro. Quantifying the benefit of using differentiable learning over tangent kernels. arXiv preprint arXiv:2103.01210. 2021.
Samet Oymak and Mahdi Soltanolkotabi. End-to-end learning of a convolutional neural network via deep tensor decomposition. arXiv preprint 105502180,.06523, 2018.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32: 8026-8037, 2019.
Ali Rahimi and Benjamin Recht. Weighted sums of random kitchen sinks: replacing minimization with randomization in learning. In Nips, pp. 113-1320.. Citeseer, 2008.
Ali Rahimi, Benjamin Recht, et al. Random features for large-scale kernel machines. In NIPS, volume 3. pp. 5. Citeseer, 2007.
Shai Shalev-Shware and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
John Shawe-Taylor, Nello Cristianini, et al. Kernel methods for pattern analysis. university press, 2004.
Cambridge
Louis Thiry, Michael Arbel, Eugene Belilovsky, and Edouard Oyallon. The unreasonable effectiveness of patches in deep convolutional kernels methods. arXiv preprint S003v::2011.05288, 2021.
Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47, Cambridge university press, 2018.
David P Williamson and David Shmoys. The design of approximation algorithms. Cambridge university press, 2011.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv: 1708007777 2017.
Matthew D Zeiler. Adadelta: an adaptive learning rate method. arXiv preprint arXiv: arXiv:1212.5155 12/2.5701, 2012.
11

---

Under review as a conference paper at ICLR 2022
A
PROOFS OF SECTION 3.1.1
Proof of Lemma 3.4 let -1, T2 E Rár, and we have:
[lf(x)) f(x2)11 Σ (o(Wx))) -o(xx)))>((Xxx)))) oWWx)),)
$ (Wx: Wx2); = [[ - xx2)11 & |W]? || x211
Proof of Lemma 3.6 Observe that if 91 is an Li-Lisschitz function, and g2 is an L2 Li-Lipschitz function, then is L, Lippsshchii:
[1(91 o 92 (x1) - (g1 (x2))l & L1 l192(x1) g2(xe)ll S م1 || x2ll
Now, using Lemma 3.4 gives the required.
B PROOF OF SECTION
Proof of Theorem 4.3
By Assumption 4.2 there exists set A S Pa of size N, NP) such that:
P C Uveo,, C Uve (v)
(6)
The clustering algorithm guarantees that (Gonzalez) 1985),
min ||v u|| max min ||v ull S 4r
vEP. uED
vEP. uEA
where the last inequality follows by Eq. (6) It follows that P. S Bar (v) which implies that
Uver, B2-(v) S UvE DvrDBe,(v)) Then, by Eq. we get S UvEr, B2r(v) S UvEDBor
Now, define the vectors w (f(v1), f(VN)) E and,
w = f(v))) -.... ( (1 ((1))((v))))
(K)
[(vi]())))))))))
[u(x),((v)))) CR..
ie., ((--))++ = (1) f(v,)) for all s S n and 1 S S N. Let F(x) = (wr, ((x: and notice that Fxx) E, (u()) (w, [(x(i
For each u P define T(u) = D | v|l < r). Then, the following holds for every P:
[s[uu) (w, D. D)
s(u) [T(1]
Σ S(v)
vET(u)
Σ
(1 - s(v)l
[Tu]
vET(u)
Σ
L - v/ TI Gr
[T(]]
vET(u)
Therefore for all x E supp(Z):
(x) F(x)
Σ ( f(x(ii) (w, x(x|]; D. D.T)))
Σ
|u00) [[
(w, [(x(1); D.
1r Σ
(
1
<
2
12

---

Under review as a conference paper at ICLR 2022
which implies that for any (x. I, Fxx) > 1/4 Therefore, 2w satisfies Eq. (Hard-SVD) and so we get that w satisfies Eq. (Hard-SVM. M with [w] S 2 |
Now, consider the ramp loss:
uy S 0
1.amp (y, w)
1
uy 0 < my < 1
(8)
0
uy 2 1
Then, by a standard generalization bound (Bartlett Mendelson 2002 Boucheron et al. 2005).
there exists constant 0 such that with probability least over the randomness of S:
L Lamp (y. (w, (xx < a 1xx; D. r) [
log(:)
E (x
+ a
2/m
Since the ramp loss upper bounds the 0-1 loss I,0 (v. (uy <0), and by the inequalities
[x; D) S vn and || < 2 || < 2 (PN, Ei= || S 2/M"N,(P)B' we
have:
(P)B,
log(
(x)))= (y (w, (xx; D,r)) < 0] S a
+ +aj
m
which completes the proof.
Proof of Theorem 4.3 Let C' be an r-covering of P of minimal size, namely |C| N. Let co be the subset of balls that have mass 2 é' N. i.e.:
c'= VEC PANI |ist. E B,(v) 2 d')
N
We first show that with probability 2 - 8 for every E O' we have (v n Pa + 0. Indeed, fix some v E C", and by definition of C":
m N
8'
P (B. = 1
I
exxp
N
N
The required follows from the union bound.
Now, assume that for every C' there exists E Pa such that By(v). Therefore, we also have (v) C B2r (u). and so:
B, S UveP, B2r
(10)
Since Ps P. there exists set A C Pa of size (P) such that:
Pa C U2r (v)
(11)
The clustering algorithm guarantees that (Gonzalez 1985).
max min ||v -ul ul| < VEP. WED
max min ||v u/l S 4r
(12)
veP,
where the last inequality follows by Eq. It follows that P., S LvreDBirV) which implies that
UveR (v) C (v) Then, by Eq. 10 we get:
Uver (v) C UvenBar(y)
(13)
We say that x E X is good for all $ i n, x[i] E Uvecr B, We say that the training S is good if for all S, is good.
Now, define w and as in the proof of Theorem 4.3
13

---

Under review as a conference paper at ICLR 2022
By the definition of C² the probability that x is not good is at most Everro Px~x Bi, x E (v)] I d. Let Ey E {0,1] be the random variable indicating
whether the j-th example in is not good. Observe that R Therefore, by Markov's inequality we have:
Σ Σ==15 Es
ンー= [
me'.
P E E [m] s.t. Ey = =] P
E 1
S E
E
=mé <
Therefore, the probability that S is good is at least
For each E UveC (v) define T(u) = {v D : ||u following holds for u E (v))
vll S 6r). Then, by Eq.
13 the
[[(()) - (w, ø(u; D. Gr) = [(u)
1
Σ S(v)
[T(u)
vET(u)
1
Σ
Ilf(u) - f(v)l
[T(u)]
veT(u)
$ [T(u)]
Σ
L| v/l 1rL
vET(u)
Therefore for all good x:
(x) - ((x))
Σ ( s(x(i) - (w, x(x(] ((x)))))TT))) D.T)))
=
| || [x(())
(w, x(x|(]; (, D,T)>|
1r Σ
(
SE<
which implies that for any (x, v) I where x is good, y F (x) 2 1
For now we consider two events: (1) Event where for every v E C" we have (,) * 0 which occurs with probability at least 8' and (2) Event that S is good which holds with probability at least 8. Now, consider the ramp loss in Eq. (8) Then, by a standard generalization bound (Bartlett & Mendelson 2002, [Boucheron et al. 2005) and considering the events above, there exists a constant ar > 0 such that with probability at least 8' 28 over the randomness of S and S.:
[L (y, (w, (xx; D. r))]] < a |x: D,T)I
log(t)
JE (x..))~Ixx is good
(14)
2 2/m
m
Since the ramp loss upper bounds the 0-1 loss T (y.u) u) 1 (wy < 0), and by the inequalities
(xx S /n and || < 2 || - 2 MPN, (P) Σ ||((t) we have:
nMNN, PP) En
log(?)
P(x,))=I,xin i good (w; ))))
< 0] < at
+ a
m
m
Therefore,
P P(xa))z (w. (W,
< 0 = P P(xx)) I, x good IV (w, D( D.T)) <0 0
w) w-I II, x is not good [y (w, ((x; 7)) < 0]
nM2N, En (0
log( m
< a
+ a
e'
m
14

---

Under review as a conference paper at ICLR 2022
which concludes the proof.
Proof of Theorem 4.8 Assume that < nN/2. For every E [n] and [M], let Xi,j RR such that Xij = Li/L)e where k = A,(1).
Let = (z,, Z1,..., NN} C Rdr set N+ points s.t. 2, = (i/ I,, 0, 0). Let Rdr - RN
the function such that:
0 T. -0))((1))]
<(1) $ [ij 1)/L, (1))
f(Z);
211) E (1-1)/1,,jT]
j L.2())+1
2(1)
[j/ (i+
Namely, f(z;) = c; if 0 and f(z)) 0. Observe that f I--Lipshitz and [x) S for all x. Now, for some F(x) = Ei=1 (u fxx())) notice that F(x,)) = /f =: Yi, for all d E [m]. E [N]. So, for any choice of y {vs., (is.)hie(n).eeEN C {+1}, define the distribution Iy defined by (xx.) It.5) where i ~ [n] and j ~ [AV] uniformly.
Note that (Z) contains nM examples, and since m < n2N/2 there are at least n.V/2 2 examples in sZpp(Z) that are not seen by the algorithm A. Let S be the sample seen by the algorithm A, and A(S) be the hypothesis returned by A upon seeing the sample S. Let S be the samples not seen by the algorithm. We also denote yS)) the coordinates of y that appear in S, and yS)) the coordinates of y that do not appear in S. So, we have:
E
EEP (K. (A(S)(x),) # Ve ZE S
EE nN
Σ 1(A(5)(x) + Fy}
(x.))E3
S
2n.N
4
Therefore, there exists a distribution Iy such that
E IP (x,))~z (A(S)()) +
and observe that by definition of Zy. this distribution satisfies Assumption 3.2 Now, the required follows from a simple application Markov's 's inequality (see 5.5.1 in (2014).
Ben-David
C EXPERIMENTAL DETAILS
Here provide details of the experiments performed in Section 5 All experiments were run NVidia Titan Xp GPUs with 12GB of memory. Neural network training algorithms were implemented with PyTorch (Paszke et al. 2019). All of the empirical results can replicated in approximately 20 hours on a single Nvidia Titan Xp GPU. The shallow network consists of convolution layer with 32 channels with kernels of size 5x5 and stride 1, 2x2 max pooling layer and fully connected layer. The deep CNN network consists of two convolution layers followed by max pooling and two fully connected layers. The first convolution layer has 32 channels with 3x3 kernels and stride 1, the second has 64 channels and kernels as in the first convolution layer. Between the fully connected layers there are 128 hidden neurons. We used dropout in both networks after the max pooling and for the deep network also between the fully connected layer. The networks were trained with Adadelta (Zeiler 2012) with learning rate 1.0 (it performed better than learning rate 0.1). We trained both networks for 30 epochs and chose the best performing network on validation set. For MNIST and FMNIST, the training set has 55000 points, the validation 5000 points and the test set 10000 points.
We implemented our semi-supervised algorithm where the unsupervised stage was performed with k-means on whitened patches with 100 cluster centers. For clustering, we sampled 100000 patches of size 5x5 from the training images and performed whitening. Given cluster centers, calculated a representation for patches. In this representation, the entry for a corresponding center is 1 the distance between the patch and the center is less than the average of the minimum distance to the
15

---

Under review as a conference paper at ICLR 2022
centers and the mean distance to the centers. Otherwise it O. We performed k-means with 4 random seeds and 100 cluster centers and obtained 4 representations which were concatenated to get the full representation of the patch. Then, calculated the representation for each image of the training set by concatenating the representations of the 5x5 patches of the image with stride 2 between patches. linear classifier was trained the representation set of the training which consisted of 60000 data points for all three datasets in Table [ Then, we evaluated the algorithm using the learned linear classifer
of size 10000 with the new representations.
The noisy FMNIST dataset was constructed by adding to each iamge a random isotropic Gaussian vector with zero mean and standard deviation 5. For each pair of algorithm and dataset we performed 5 runs with different Numpy and Py Torch seeds.
16


Reviews:
[{"review_id": "x6sKUUhsuLg", "reviewer": "Reviewer_g4Er", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "** Strength **\n+ The paper is well-written and well organized. It is easy to read.\n+ The distribution assumption, namely Assumption 3.2, is natural, and the authors have verified the realizability of such assumption if a dataset can be classified using shallow/deep CNN.\n+ Theoretical analysis seems to be sound.\n\n** Weakness **\n- The proved result seems to be \"underwhelming\" compared to the author's claim. The learning algorithm is constrained to learn a linear classifier on top of a pre-defined patch embedding function based on patches mined from the unlabeled data. However, the learned model is not necessarily a \"standard CNN\". More specifically, the patch/input-embedding function $\\Phi$ is not necessarily realized by convolutions.\n- The authors stressed the importance of covering number in the paper. However, no theoretical analysis or empirical study has been provided on an estimate on it. In particular, the experiments in section 5 is especially underwhelming. The authors hand-wavingly explain that noisy FMNIST appears hard to learn because it has large covering number, but no estimate has been provided, making the theoretical analysis unverified.\n- Also, the scaling of the proposed algorithm is questionable. The unsupervised learning mines patches from the entire patch domain, which might be costly.\n- The performance of the proposed algorithm is also not convincing. On the easy MNIST and FashionMNISt dataset, it underperforms even shallow CNNs. I would suggest test the algorithm on more complicated datasets, and report the runtime.", "summary_of_the_paper": "The authors propose a semi-supervised learning method, that learns a linear classifier over data-dependent features obtained from unlabeled data. Under some distribution assumption on the images based on their patches, the authors claim that the algorithm provably learns CNN. Experiments are conducted on MNIST and FashinMNIST aiming to verify the importance of covering number of the patches.", "summary_of_the_review": "Based on my review above, I am leaning towards rejecting the paper based on the utility and scalability of the algorithm, and the lack of empirical study to verify the theoretical contribution of the paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "v24RYO3aTa9", "reviewer": "Reviewer_nV5M", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Section 3.1.1 is not really useful, as most of the Lipschitz bounds can be found in the literature (e.g., https://arxiv.org/abs/1312.6199) - I’d prone to remove this section, also because the considered architecture is not Lipschitz (it’s not even continuous)\n\nBasically, this work relies on the assumption that the patches (implying the training data) are low dimensional. As stated in this work (sec 4.2), this remains to be proved, at least numerically, and this is here tractable. Secondly, if experiments can be conducted on MNIST, they should also be conducted on datasets such as CIFAR-10. These are two major flaws of this work: I believe that the idea that if some data are low dimensional then it's easier to learn is not really new and specific to this method - it needs to be shown that this is actually the good underlying model of the data.\n", "summary_of_the_paper": "This work studies from the PAC-Bayes perspective the learning of predictors that consists in an aggregation of patch detectors. The main principle is to claim that if a low-dimensional structure is present in the patches, then a function of the data (e.g., a function to regress) inherits this low-dimensional structure too. From my perspective, all the proofs are direct and rely on straightforward applications of the PAC-Bayes theory and the proposed classifier isn't really studied from a game-changer perspective.", "summary_of_the_review": "This paper tries to address the difficult question of understanding CNNs through a simplified model. While this is its main focus, I believe more works needs to be done to get to this result. Indeed, if the authors could certify that their assumptions are correct and are reflected by the data, then I’d be inclined to raise my score. In other words, that the method proposed here is actually working and employs fully the structure of some (complex) data, and is not vacuous.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "dBMtHiH0Nd", "reviewer": "Reviewer_WV6X", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### Strengths\n- The paper is well-referenced, well-written, and well-motivated. It studies\n  several timely issues: theory for data-driven embeddings applied in deep\n  learning-esque setting (following empirical results of Thiry et al.\n  mentioned), learnability of CNNs on natural data distributions.\n- The mathematical formalism is precisely presented and the arguments explained\n  with a great combination of technical precision and intuition, making it easy\n  to understand the authors' algorithm and technical claims. I believe the\n  results obtained are reasonable given these arguments, although I have not\n  checked the proofs in the appendix line-by-line.\n\n### Weaknesses\n\nI would appreciate clarification around how the authors see several modeling\naspects of their setup, relative to the stated goal of understanding\nlearnability of CNNs under practical data distributions. In general, I feel an\nexplicit discussion of some of these aspects in the paper would be helpful:\nsome of this material could be worked into section 3.1.1 (although the\nresults there are helpful to see when thinking about $M$ and $L$, I believe\nthey are standard and the lemmas could be placed in the appendix).\n- The GCF target model is significantly more general than CNNs, while also\n  missing certain aspects of practical CNN architectures. E.g. the GCF is\n  presented like a \"linear probe\" of a convolutional network's intermediate\n  features, but I do not think modern convolutional networks use bounded\n  activation functions (as in assumption 3.2); the GCF does not allow for\n  hierarchical interactions between intermediate features for each patch,\n  implying that representing complex visual relationships in this model will\n  require $k$ to be very large (and potentially $f$ to have a large Lipschitz\n  constant) -- so although $f$ can be a deep CNN, the overall classifier does\n  not have some standard depth benefits that one expects in practical CNNs.\n  These make me have some caution when interpreting what the theoretical\n  results imply about practical, deep CNNs.\n- Assumption 4.2 and the later $m_u$ condition assuming i.i.d. samples from the\n  marginal image distribution seem to require the algorithm to have access to\n  an unlabeled training set of all possible patches one will observe (at a\n  sufficient resolution).  This might be reasonable depending on the patch\n  structure in practice, but it might be helpful to discuss this a bit in the\n  paper, and possibly cite prior works that argue for similar points.\n- The definition of $P_{\\mathcal{I}}$ is distribution-specific, but the\n  algorithmic results on PAC learnability in section 4 eventually require to use \n  one set $S_u$ for all possible distributions: it therefore seems like what is\n  being used here via Assumption 4.2 is a definition of $P$ that does not\n  involve a specific function $f$. I see that definition 4.6 attempts to handle\n  this issue for the later results, but Corollary 4.7 still references\n  assumption 4.2, and it is not clear to me that access to iid samples from the\n  marginal distribution over images (I assume this is what is being used in\n  Theorem 4.5, although it is not stated, based on the subsequent discussion) \n  leads to a covering of $P_{\\mathcal{I}}$ here, given that the function $f$\n  does not seem to be involved in the marginal distribution.\n\nIn general, it seems from section 4.2 that the authors' argument for how their\nanalysis relates to the stated aim of giving theory that explains how neural\nnetworks may be efficiently learnable in practice amounts to the fact that\nlearning Lipschitz functions over $d$-dimensional data has a\ncursed-in-dimensionality sample complexity $\\exp(d)$ (whether this $d$ is the\ndimension of the ambient space, as in the hardness results of Livni et al.\ncited, or the dimension of a low-dimensional manifold). I am under the\nimpression this is a well-known fact in computational learning theory;\nmoreover, the literature contains numerous results *specific* to neural\nnetworks trained with (S)GD that prove how these dependencies can be achieved:\nfor example [1-5] discussed below (there are also non-algorithmic results on\napproximation by deep networks, e.g. [6-9] below). The insight/contribution\nhere would be enhanced if the authors discussed ways in which their result on\nGCFs provided insights beyond the standard result in learning theory (perhaps,\nas discussed below, in terms of contributions to learning theory through their\nanalysis of the embedding algorithm and comparisons of their result to existing\nones).\n\nAfter Corollary 4.4, the authors state that their algorithm runs in polynomial time. This description may not be appropriate, given that the parameter $N$ is not a true input parameter, but rather a derived one\n  from $r$ and the properties of the set of all patches $P$ (and without\n  further assumptions on $P$, one cannot guarantee a priori that this is not\n  exponential in $d_P$).\n\n[6] http://arxiv.org/abs/1908.01842\n\n[7] http://arxiv.org/abs/2008.02545\n\n[8] http://arxiv.org/abs/1908.00695\n\n[9] https://openreview.net/forum?id=BJ3filKll\n\n### Related work\n\nIt would be helpful in assessing the authors' contribution if more reference\nwas made to prior art in the learning theory literature that might be relevant\nto the authors' algorithm and its analysis. Given the amount of study that has\nbeen devoted to sparse coding/nearest neighbor embedding/dictionary learning\nprocedures in the literature, it seems to me that analysis similar to the\nauthors might exist. If so, it would be helpful to compare the authors' rates\nto the rates in these algorithms, or point out other novelties of the authors'\nresults; if not, it would speak well to the novelty of the authors' analysis,\nwhich I would like to credit. In general, the related work section is helpful,\nbut it spends most of the time discussing learnability results for neural\nnetworks: it seems to me that the authors' analysis is applicable to a\nsignificantly more general bounded Lipschitz learning setting, and lacks some\nnuances associated with direct learning of NNs by GD/SGD (as mentioned above),\nand so it would be appropriate to discuss more general learning results to aid\nin the interpretation of the contribution.\n\nIt might be relevant to point out certain prior works that have been motivated\nsimilarly as the authors: e.g. [1-5] below. These works imagine that the data\nunder consideration have a low-dimensional manifold structure, and provide some\nalgorithmic results for training deep networks to classify them (some\nasymptotic).\n\n[1] http://dx.doi.org/10.1103/PhysRevX.10.041044\n\n[2] https://openreview.net/forum?id=O-6Pm_d_Q-\n\n[3] http://arxiv.org/abs/2107.14324\n\n[4] https://arxiv.org/abs/2106.04156\n\n[5] http://arxiv.org/abs/2006.13409\n\n\n### Minor issues/corrections\n- page 5 \"unsupervised stage\": reference should be to figure 2 or algorithm 1\n- definition 4.1: script D instead of script P?\n- theorem 4.5: should this reflect what is stated in the discussion below\n  ($S_u$ is composed of iid samples from the marginal over inputs?)\n- bottom of page 6: $\\hat{w}$ equation seems indexed incorrectly (the $v$'s\n  should index from $1$ to $N$ and the $u$'s should index from $1$ to $n$)\n\n\n", "summary_of_the_paper": "Motivated by the empirical successes of CNNs for classification tasks on\nnatural image data in spite of certain known computational hardness barriers,\nthe authors consider a model for semi-supervised learning of CNNs under certain\ndistributional assumptions. They consider a classification setup given samples\n$(x, y)$ from a distribution $\\mathcal{I}$, assumed to be separable with a\npositive margin (in population) by a \"generalized convolution function\" $F$\n(which is a linear function of a bounded Lipschitz function acting on patches),\nwhich only depends on certain low-dimensional projections of the images $x$ (in\nvision parlance, the \"image patches\"). The authors study a two-stage\nsemi-supervised algorithm for classifying such data, originally given by Coates\n(2011): the first stage takes in unlabeled data samples $x$ and creates a patch\ndictionary $D$, and the second stage uses this patch dictionary $D$ together\nwith a training set of i.i.d.\\ labeled examples from $\\mathcal{I}$ to learn a\nlinear classifier via solving a hard margin SVM problem with features obtained\nfrom the dictionary $D$ (the embedding is something like a nearest-neighbor\nembedding: given an input image, the image is decomposed into patches, and a\none-hot vector indicating the patches in the dictionary falling within a\nspecified radius of each input patch is output (and then normalized by its\nsum)). The authors' analysis proves that this model PAC learns this family of\ndistributions given a sufficiently expressive patch dictionary $D$: the sample\ncomplexity ultimately depends on the covering number of the set of all patches\nthat can be observed, and the authors argue that this indicates that when the\nset of all possible patches has low-dimensional structure, we avoid the\naforementioned hardness results and learn efficiently. A lower bound is\nprovided to prove certain dependencies on the number of patches and the\ncovering number is unavoidable in the PAC learning setting. Some experiments\nare provided to demonstrate the algorithm on MNIST and Fashion MNIST.\n\n", "summary_of_the_review": "This is a well-written theory paper, but I am unclear on the extent to which it accomplishes its stated goal of providing insights into how CNNs can be efficiently learned in practice relative to the existing literature (on neural network training and on learning theory), given the very general target function model and the fact that the final bounds essentially depend on a covering number for the entire space of input patches one will observe. The CNNs that can be modeled by the authors' target function model are essentially \"shallow\" models with a linear probe evaluation: no hierarchical structure is captured.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "7nwOLGQok8F", "reviewer": "Reviewer_vjtz", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is satisfyingly well-written and somehow clear and easy to follow. I am not very familiar with the literature on hardness results for neural networks and I am not able to judge the novelty of this work. It seems to be well motivated with a simple tractability result with a natural assumption for PAC learnability. I have a few comments:\n\nI don’t think the section 3.1.1 is necessary and could be replaced by a short paragraph in order to make space for more high level discussions about the assumptions and the related literature. In particular, the relation between the covering number assumption and the settings considered in previous work (low-dimensional manifolds etc). \n\nI am also not entirely convinced that the dependence in the covering number is the right measure here. Especially, the algorithm would require to sample from every covering ball, which does not seem to be practical. Furthermore, this covering number is on all patches at the same time, and might be impractically large. I don't think the simulations are particularly convincing.\n\nOn the other hand, some function class are tractable without requiring small covering number (by for example, restricting the GCF to have all its functions in a small RKHS ball, and taking a convolutional kernel as the learning method).", "summary_of_the_paper": "In this paper, the authors consider learning the function class of one-layer convolutional networks. While multiple results show that learning neural networks is NP-hard in general, meaning there is no efficient algorithm that is guaranteed to succeed at learning the function class of neural networks. Hence, in order to close the gap between theory and practice, and guarantee tractability, distributional assumptions should be introduced. In this work, an abstract distribution is considered, where only the covering number is assumed to be bounded. With this assumption, the authors show that a learning algorithm with an unsupervised clustering procedure creates features that are then used in a linear classifiers, learn a class of one-layer convolutional networks, with sample complexity that is tight for the number of supervised samples in terms of $nN$.", "summary_of_the_review": "This paper  give a simple example of tractability under the natural assumption of covering number (somehow necessary for PAC learnability). Even if it is a simple example, it is not trivial that this lower bound is achieved by an efficient algorithm, and the fact that the semi-supervised method presented in this paper works is not obvious. However, the author falls short of convincing that this covering number could a feature of real dataset that ensure tractability. For these reasons, my recommendation is marginally below the acceptance. If the authors can convince me that this covering number assumption has strong theoretical or empirical backing, I would be willing to raise my recommendation!\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a new distributional assumption and a new algorithm for learning convolutional neural networks. However, the reviewers reach a consensus that this paper's assumptions are not natural and may not be satisfied in real-world domains. The meta reviewer agrees and thus decides to reject the paper.
Decision: Reject