An Optimization and Generalization Analysis for Max-Pooling Networks

Introduction

Convolutional neural networks (CNNs) have achieved remarkable performance in various computer vision tasks (Krizhevsky et al. 2012; Xu et al. 2015; Taigman et al. 2014). Such networks typically combine convolution and max-pooling layers, and can thus be used for detecting complex patterns in the input. In practice, CNNs typically have more parameters than needed to achieve zero train error (i.e., are overparameterized). Despite the potential problem of non-convexity in optimization and overfitting because of overparameterization, training these models with gradient based methods leads to solutions with low test error. Furthermore, overparameterized CNNs significantly outperform fully connected networks (FCNs) on classifying image data (Malach & Shalev-Shwartz 2020a). Thus, a key question immediately arises:

Why do overparameterized CNNs generalize well on image data and outperform FCNs?

To the best of our knowledge, this question remains largely unanswered. We note that the question contains two significant challenges: the first is to show that minimization of the non-convex training loss leads to high training accuracy (where non-convexity is a result of both max-pooling and ReLU activations), and the other is that over-fitting is avoided despite over-parameterization. The latter challenge is known as the question of inductive bias of gradient descent (Zhang et al. 2017), and understanding it is a key goal of deep learning theory.

In this work, we provide the first results which address the above question. We theoretically analyze learning a simplified pattern recognition task with overparameterized CNNs and overparameterized FCNs. We consider a CNN with a convolution layer, max pooling and fully connected layer and compare it to a one-hidden layer non-linear FCN. Figure 1 shows an example of our setup. We summarize our contributions as follows:

Expressive Power of CNNs with max-pooling: We prove a novel VC dimension lower bound in our setting which is exponential in $d$, the filter dimension of the CNN. This result implies that there exists ERM algorithms which have sample complexity which is exponential in $d$ in our setting.

Optimization and Generalization for learning CNNs with max-pooling: We analyze learning overparamaterized CNNs with a layerwise gradient descent optimizer. We show that the algorithm converges to zero training loss and the learning has a sample complexity of $O(d)$. This is despite the above VC result, which shows that general ERM optimizers can potentially overfit. In our proof, we analyze the dynamics of training the first layer. We show that it induces a representation in the last layer which is separable with large margin and thus implies a good generalization guarantee.

Generalization of FCNs: We apply recent results of Brutzkus et al. 2018 which show a generalization bound for overparameterized FC networks that is independent of the network size. We prove that in our setting, their bound can be at best $O(d^{2r})$ for $r\geq 1$, and can thus be much larger than the sample complexity we derive for the CNN.

Empirical Evaluation: We empirically validate our theoretical results. We show that CNNs generalize well and significantly outperform FCNs in our setting as predicted by our theory. We empirically confirm that this holds also for several extensions of our setup.

Our results make a significant headway on the challenging problem of understanding why overparameterized CNNs can generalize better than overparameterized FCNs on image classification tasks. In particular, to the best of our knowledge, we provide the first optimization and generalization results for overparameterized CNNs with max pooling.

Related Work

Two recent works have provided theoretical support that that CNNs outperform FCNs. Li et al. 2020 consider a simplified image classification task and prove a sample complexity gap between FCNs and single channel CNNs. Malach & Shalev-Shwartz 2020a prove that for simplified pattern detection tasks, there is a computational separation between overparameterized CNNs and FCNs. Their generalization bound for overparameterized CNNs depends on the number of channels of the CNN. Therefore, both works do not show that over-parameterized CNNs are reslient to over-fitting, which is the main focus of our work.

Several recent works have studied the generalization properties of overparameterized CNNs. Some of these propose generalization bounds that depend on the number of channels (Long & Sedghi 2020; Jiang et al. 2019). Others provide guarantees for CNNs with constraints on the weights (Zhou & Feng 2018; Li et al. 2018). Convergence of gradient descent to KKT points of the max-margin problem is shown in (Lyu & Li 2020) and (Nacson et al. 2019) for homogeneous models. However, their results do not provide generalization guarantees in our setting. Gunasekar et al. 2018 study the inductive bias of linear CNNs.

Yu et al. 2019 study a pattern classification problem similar to ours. However, their analysis their sample complexity guarantee depends on the network size, and thus does not explain why large CNNs do not overfit. Other works have studied learning under certain ground truth distributions. For example, Brutzkus & Globerson 2019 study a simple extension of the XOR problem, showing that overparameterized CNNs generalize better than smaller CNNs. Single-channel CNNs are analyzed in (Du et al. 2018b; Du et al. 2018a; Brutzkus & Globerson 2017; Du et al. 2018c). CNNs were analyzed via the NTK approximation (Li et al. 2019; Arora et al. 2019c). Our analysis does not assume the NTK approximation. For example, we require a mild overparameterization in our results which does not depend on the number of samples, in contrast to NTK analyses. Furthermore, our results hold for sufficiently small initialization, which is not the regime of NTK analysis.

Other works study the inductive bias of gradient descent on fully connected linear or non-linear networks (Ji & Telgarsky 2019a; Arora et al. 2019a; Wei et al. 2019; Brutzkus et al. 2018; Dziugaite & Roy 2017; Allen-Zhu et al. 2019; Chizat & Bach 2020). Fully connected networks were also analyzed via the NTK approximation (Du et al. 2019; Du et al. 2018d; Arora et al. 2019b; Fiat et al. 2019). Kushilevitz & Roth 1996; Shvaytser 1990 study the learnability of visual patterns distribution. However, our focus is on learnability using a specific algorithm and architecture: gradient descent trained on overparameterized CNNs.

Preliminaries

We consider a learning problem that captures a key property of visual classification. Many visual classes are characterized by the existence of certain patterns. For example an 8 will typically contain an x like pattern somewhere in the image. Here we consider an abstraction of this behavior where images consist of a set of patterns. Furthermore, each class is characterized by a pattern that appear exclusively in it. We define this formally below.

Next, we define how labeled points are generated. In our setting we consider three types of patterns: positive, negative and spurious. We will refer to the pattern $\boldsymbol{o}_{1}$ as positive, the pattern $\boldsymbol{o}_{2}$ as negative and the patterns $\boldsymbol{o}_{3},\ldots,\boldsymbol{o}_{l}$ as spurious. We let ${\cal S}=\left\{3,...,l\right\}$.

Given $y=1$, a vector $\boldsymbol{x}$ is sampled as follows. Randomly sample an index $1\leq j_{+}\leq n$ for placing the positive pattern, and set $\boldsymbol{x}\left[j_{+}\right]=\boldsymbol{o}_{1}$. Then, for each $1\leq j\leq n$ such that $j\neq j_{+}$, randomly choose $i_{j}\in{\cal S}$ and set $\boldsymbol{x}[j]=\boldsymbol{o}_{i_{j}}$.

Given $y=-1$, do the same as $y=1$, using $\boldsymbol{o}_{2}$ instead of $\boldsymbol{o}_{1}$.

Fig. 1(a) shows an example of the above distribution ${\cal D}$.

CNN Architecture:

CNN Training Algorithm:

For the analysis of learning CNNs, we will consider a layerwise optimization algorithm which performs gradient updates layer-by-layer, starting from the first layer. Layerwise optimization algorithms are used in practice and have been shown to achieve performance that is comparable to end-to-end methods, e.g., on ImageNet (Belilovsky et al. 2019). Furthermore, the assumption on layerwise optimization has been used previously for theoretically analyzing neural networks (Malach & Shalev-Shwartz 2020b).

The layerwise optimization algorithm for learning CNNs is given in Figure 2. The reason we optimize over two losses is technical: we need a fresh IID sample ($S_{2}$) in the second layer optimization for the generalization analysis (see Section 5).

We define $\boldsymbol{w}^{(t)}_{i}$ to be the $i$th row of $W^{(t)}$. For $\boldsymbol{x}\in S$, $t>0$ and $1\leq i\leq k$, define $j^{(t)}_{i}(\boldsymbol{x})=\argmax_{1\leq j\leq n}{\boldsymbol{w}^{(t)}_{i}\cdot\boldsymbol{x}[j]}$, i.e., $j^{(t)}_{i}(\boldsymbol{x})$ corresponds to the pattern in $\boldsymbol{x}$ that maximally activates $\boldsymbol{w}^{(t)}_{i}$. If $\boldsymbol{w}^{(t)}_{i}\cdot\boldsymbol{x}\left[j^{(t)}_{i}(\boldsymbol{x})\right]>0$, define $\boldsymbol{p}^{(t)}_{i}(\boldsymbol{x})=\boldsymbol{x}\left[j^{(t)}_{i}(\boldsymbol{x})\right]$. Otherwise, define $\boldsymbol{p}^{(t)}_{i}(\boldsymbol{x})=0$. Notice that the following equality holds:

We note that it is necessary to make assumptions regarding the data distribution because the general case is intractable for optimization (because it includes neural net learning as a special case). We believe that our data generating distribution does reflect core aspects of pattern detection problems. Furthermore, the analysis of overparameterized max pooling networks has not been performed for any task, and analysis of simplified tasks has been shown to be fruitful for understanding CNNs (Li et al. 2020; Malach & Shalev-Shwartz 2020a). Additionally, non-overlapping filters are used in practice, and multiple theoretical works have analyzed CNNs with non-overlapping filters due to their tractability (Sharir & Shashua 2018). Finally, we note that in Section 7 we show that our analysis is in line with the performance of CNNs and FCNs in more complex tasks.

VC Dimension Bound

Thus far we described a data generating distribution and a neural architecture. We now ask how expressive is this neural architecture. Because of the pooling layer, it may seem that the network has limited capacity, even for an unbounded number of channels. However, as we show next the capacity in terms of VC dimension is in fact exponential in $d$ in this case. This in turn means that the network can separate datasets of size up to exponential in $d$, and can thus potentially overfit badly. As we show in later sections, overfitting is avoided when learning using gradient descent.

We begin by recalling the definition of the VC dimension.

Let $\mathcal{H}$ be a hypothesis class of functions from ${\cal X}$ to $\{\pm 1\}$. For any non-negative in integer $m$, we define:

If $\left|\left\{\left(h(x_{1}),...,h(x_{m})\right)\mid h\in\mathcal{H}\right\}\right|=2^{m}$, we say that $\mathcal{H}$ shatters the set $\left\{x_{1},...,x_{m}\right\}$. The VC dimension of $\mathcal{H}$, denoted by, $\textup{VCdim}\left(\mathcal{H}\right)$, is the size of the largest shattered set, or equivalently, the largest $m$ such that $\Pi_{\mathcal{H}}(m)=2^{m}$.

Assume that $d=2n$ and $n\geq 2$, then $\textup{VCdim}\left(\mathcal{H}_{\textup{CNN}}({\cal X})\right)\geq 2^{\frac{d}{2}-1}$.

We will construct a set $B\subseteq{\cal X}$ of size $2^{n-1}=2^{\frac{d}{2}-1}$ that can be shattered. We note that the inclusion $B\subseteq{\cal X}$ will hold for any $\epsilon_{i}>0$, $1\leq i\leq d$. For a given $I\in\{0,1\}^{n-1}$ let $I[j]$ be its $j$th entry. For any such $I$, define a point $\boldsymbol{x}_{I}$ such that for any $1\leq j\leq n-1$, $\boldsymbol{x}_{I}[j]=I[j]\boldsymbol{o}_{2j+1}+(1-I[j])\boldsymbol{o}_{2j+2}$. Furthermore, arbitrarily choose $\boldsymbol{x}_{I}[n]=\boldsymbol{o}_{1}$ or $\boldsymbol{x}_{I}[n]=\boldsymbol{o}_{2}$ and define $B=\left\{\boldsymbol{x}_{I}\mid I\in\{0,1\}^{n-1}\right\}$.

Now, assume that each point $\boldsymbol{x}_{I}\in B$ has label $y_{I}$. We will show that there is a network $N_{\textup{CNN}}\in\mathcal{H}_{\textup{CNN}}({\cal X})$ such that $N_{\textup{CNN}}(\boldsymbol{x}_{I})=y_{I}$ for all $I$. For each $I\in\{0,1\}^{n-1}$, define $\boldsymbol{w}^{(I)}=\max\left\{\alpha_{I},0\right\}\sum_{1\leq j\leq n-1}\boldsymbol{x}_{I}[j]$ and $\boldsymbol{u}^{(I)}=\max\left\{-\alpha_{I},0\right\}\sum_{1\leq j\leq n-1}\boldsymbol{x}_{I}[j]$, where $\left\{\alpha_{I}\right\}$ is the unique solution of the following linear system with $2^{n-1}$ equations. For each $I\in\{0,1\}^{n-1}$ the system has the following equation:

where for any $I\in\{0,1\}^{n-1}$, $I^{c}\in\{0,1\}^{n-1}$ is defined such that $I^{c}[j]=1-I[j]$ for all $1\leq j\leq n-1$. There is a unique solution because the corresponding matrix of the linear system is the difference between an all 1’s matrix and the identity matrix. By the Sherman-Morrison formula (Sherman & Morrison 1950), this matrix is invertible, where in the formula the outer product rank-1 matrix is the all 1’s matrix and the invertible matrix is minus the identity matrix.

Set $W$ to be the matrix with rows $\boldsymbol{w}^{(I)}$ followed by rows $\boldsymbol{u}^{(I)}$. Let $\boldsymbol{a}$ be the a vector of dimension $2^{n}$ such that $\boldsymbol{a}=(\underbrace{1,...,1}_{2^{n-1}},\underbrace{-1,...,-1}_{2^{n-1}})$.

Then, for $N_{\textup{CNN}}$ with parameters $\boldsymbol{\theta}=\left(W,\boldsymbol{a}\right)$ and any $\boldsymbol{x}_{I}$:

by the definition of $N_{\textup{CNN}}$, the orthogonality of the patterns $\{\boldsymbol{o}_{i}\}_{i}$, and Eq. 5. We have shown that any labeling $y_{I}$ can be achieved, and hence the set is shattered, completing the proof. ∎

The main limitation of the VC analysis is that it does not take into account the specific implementation of the ERM algorithm (Zhou & Feng 2018). In the next section, we will show a more fine-grained analysis which is specific to the layerwise optimization algorithm, and can thus benefit from the specific inductive bias of this algorithm. As a result, we will obtain a significantly better generalization guarantee.

Generalization Analysis of Gradient Descent

In this section we analyze the optimization and generalization performance of the layer-wise gradient descent algorithm $\text{LW}_{\text{CNN}}$ for training overparameterized CNNs (Eq. 1). We will show that it converges to zero training loss and its sample complexity is $O(d)$. This is in contrast to the result of the previous section which shows a VC dimension lower bound which is exponential in $d$, and therefore there are other ERM algorithms that can result in arbitrarily bad test error.

The first part of the theorem is an optimization result stating that the $\text{LW}_{\text{CNN}}$ will converge to zero $\mathcal{L}_{2}$ loss. We note that this is despite the non-convexity of the loss $\mathcal{L}_{2}$. The second part of the theorem states that the learned classifier will have a test error of order $\sqrt{\frac{d}{m}}$. Thus, the sample complexity is linear in $d$. This is contrast to the VC dimension bound which is exponential in $d$.

Before proving the theorem, we make several remarks on the result. First, for simplicity we present asymptotic results for $T_{2}$. We can provide convergence rates that depend linearly on $d$ by changing the second layer optimization hyper-parameters (initialization and step size) and use recent results of Ji & Telgarsky 2019c. See Section A for details. Second, note that $k>8d^{3}$ is a mild overparameterization condition, compared to other results which require $k$ to depend on the number of samples (Du et al. 2018d; Ji & Telgarsky 2019b).

We will prove the theorem in three parts. We defer the proofs of technical lemmas to the supplementary. We first outline the main ideas of the proof. In the first part we will prove a property of the initialization of the first layer. We show that at initialization there are sufficiently many “lucky” filters $\boldsymbol{w}^{(0)}_{i}$ in the following sense. Either the pattern in $\mathcal{O}$ that maximally activates them is $\boldsymbol{o}_{1}$ and $a^{(0)}_{i}=1$, or the maximum activating pattern is $\boldsymbol{o}_{2}$ and $a^{(0)}_{i}=-1$. In essence, these filters are “good” detectors because they detect the discriminative patterns, with the right sign of $a^{(0)}_{i}$.

In the second part we analyze the dynamics of the filters in the first layer. We will show that the “lucky” filters continue to detect the discriminative patterns and their projection on either $\boldsymbol{o}_{1}$ or $\boldsymbol{o}_{2}$ becomes larger in each iteration. In contrast, we upper bound the norm of the filters that are ”non-lucky”. Thus, after training the first layer, $\text{LW}_{\text{CNN}}$ creates a new representation of the data in the second layer with the following properties: there are sufficiently many discriminative features with sufficiently large absolute values, and the remaining features have a bounded absolute value.

In the third part, we analyze the optimization of the second layer on the new representation. Using the properties of the representation, proved in the second part, we show that this representation induces a distribution on the samples which is linearly separable. Furthermore, it can be classified with margin 1 by a linear classifier of low norm. Then, we apply a result of Soudry et al. 2018, which implies that training the second layer, which is equivalent to logistic regression on the new representation, converges to a low norm solution with zero training loss. Finally, we apply a norm-based generalization bound (Shalev-Shwartz & Ben-David 2014) to obtain the sample complexity guarantee.

Part 1: Properties of the Initialization:

Define the sets ${\cal A}^{+}=\left\{i\mid a^{(0)}_{i}=1\right\}$, ${\cal A}^{-}=\left\{i\mid a^{(0)}_{i}=-1\right\}$ and the following sets:

The sets $\mathcal{W}^{+}_{0}\cap{\cal A}^{+}$ and $\mathcal{W}^{-}_{0}\cap{\cal A}^{-}$ correspond to the set of “lucky” filters. We prove a lower and upper bound on the size of these sets.

The following lemma shows the dynamics of the “lucky” neurons that detect the positive patterns.

For all $0\leq t\leq T_{1}$ and all $i\in\mathcal{W}^{+}_{0}\cap{\cal A}^{+}$ the following holds:

$\boldsymbol{o}_{1}\cdot\boldsymbol{w}^{(t)}_{i}\geq\frac{t\eta_{1}}{9}$.

For all $j\neq 1$, it holds that $\boldsymbol{o}_{j}\cdot\boldsymbol{w}^{(t)}_{i}\leq r$.

Furthermore, for all $\boldsymbol{x}_{+}\in S_{1}^{+}$, $\boldsymbol{p}^{(t)}_{i}(\boldsymbol{x}_{+})=\boldsymbol{o}_{1}$.

The lemma shows that the projection of the filter on $\boldsymbol{o}_{1}$ grows significantly, while the projection on other $\boldsymbol{o}_{i}$ remains small. Finally, it shows that for any positive point in $S_{1}$, the pattern which maximally activates the filter is $\boldsymbol{o}_{1}$. Thus, the filter is correctly detecting the positive pattern. The proof is technical and shows that the properties above hold by induction on $t$. It is given in Section C.

By the symmetry of our setting we get by Lemma 5.3 a similar result for the “lucky” neurons that detect negative patterns.

With probability at least $1-4e^{-d}-4e^{-\frac{m}{36}}$, for all $0\leq t\leq T_{1}$ and all $i\in\mathcal{W}^{-}_{0}\cap{\cal A}^{-}$ the following holds:

$\boldsymbol{o}_{2}\cdot\boldsymbol{w}^{(t)}_{i}\geq\frac{t\eta_{1}}{9}$.

For all $j\neq 2$, it holds that $\boldsymbol{o}_{j}\cdot\boldsymbol{w}^{(t)}_{i}\leq r$.

Furthermore, for all $\boldsymbol{x}_{-}\in S_{1}^{-}$, $\boldsymbol{p}^{(t)}_{i}(\boldsymbol{x}_{-})=\boldsymbol{o}_{2}$.

Finally, we provide a simple bound on the output of all neurons (including the ”non-lucky” ones).

For all $1\leq t\leq T_{1}$, $1\leq i\leq k$, $1\leq j\leq d$ and $\boldsymbol{x}$ sampled from ${\cal D}$, it holds that $\boldsymbol{x}[j]\cdot\boldsymbol{w}^{(t)}_{i}\leq 2\eta_{1}t$.

We conclude the proof of the theorem by analyzing the optimization of the second layer. Here we sketch the analysis and defer the details to Section E.

Using the results of the first layer dynamics, we show that ${\cal D}_{\boldsymbol{z}}$ is linearly separable and can be separated with margin 1 by a classifier $\boldsymbol{v}$ with $\left\|\boldsymbol{v}\right\|=O\left(\sqrt{\frac{d}{k}}\right)$. Then, we use recent results on logistic regression (Soudry et al. 2018), to show that by optimizing the second layer, $\text{LW}_{\text{CNN}}$ will converge to a low norm solution with zero training loss. Finally, we apply norm-based generalization bounds (Shalev-Shwartz & Ben-David 2014). Since for all $\boldsymbol{x}$, $\left\|\boldsymbol{z}(\boldsymbol{x})\right\|=O(\sqrt{k})$, we obtain a sample complexity guarantee for $\text{LW}_{\text{CNN}}$ of order $O\left(\left\|\boldsymbol{v}\right\|^{2}\max_{\boldsymbol{x}}\left\|\boldsymbol{z}(\boldsymbol{x})\right\|^{2}\right)=O\left(d\right)$. ∎

Comparison with FCNs

In the previous section we showed that overparameterized CNNs have good sample complexity for learning the pattern distributions ${\cal D}$ in Section 3. How do overparameterized fully connected networks compare with CNNs in our setting? To address this question, we apply recent results of Brutzkus et al. 2018. They provide generalization guarantees for one-hidden layer overparameterized fully connected networks on linearly separable data. We will show that their bound for FC networks can be $O(d^{2r})$ for any $r\geq 1$. In contrast, Theorem 5.1 shows a generalization bound for CNNs which is linear in $d$. We note that to fully demonstrate a gap between the methods we also need a lower bound on the FCN for the distribution ${\cal D}$, and we leave this for future work. Nonetheless, we show empirically, that these generalization bounds predict the performance gap between CNNs and FCNs in our setting.

Assume that ${\cal D}$ is linearly separable with margin 1 by a classifier $\boldsymbol{w}^{*}$, i.e., for all $(\boldsymbol{x},y)\in{\cal D}$, $y\boldsymbol{w}^{*}\cdot\boldsymbol{x}\geq 1$. In Brutzkus et al. 2018 they consider the following fully connected network:

They show that SGD converges to a zero training error solution with sample complexity of $O(\left\|\boldsymbol{w}^{*}\right\|^{2}R^{2})$, where $R$ is the maximum norm of the data, $R=\max_{\boldsymbol{x}}{\left\|\boldsymbol{x}\right\|}$. In our setting it holds that $R^{2}=n$ (because each point $\boldsymbol{x}$ consists of $n$ patterns, each of norm $1$). Importantly, this bound is independent of the network size $k$.

We note that the bound $O(\left\|\boldsymbol{w}^{*}\right\|^{2}R^{2})$ also holds for the hard-margin linear SVM (Shalev-Shwartz & Ben-David 2014). Therefore, our following conclusions hold for this algorithm as well. In the next section we show experiments that compare CNNs, FCNs and SVMs in our setting and corroborate our findings.

The generalization bound of $O(\left\|\boldsymbol{w}^{*}\right\|^{2}R^{2})$ holds for any $\boldsymbol{w}^{*}$ which separates with margin 1. Thus, the best bound can be achieved with $\boldsymbol{w}^{*}$ that has the lowest norm and separates the data with margin 1. Next we show that the lowest norm is at least $\sqrt{n}$.

Then $\left\|\hat{\boldsymbol{w}}\right\|^{2}\geq n$.

Assume by contradiction that $\left\|\hat{\boldsymbol{w}}\right\|^{2}=\sum_{1\leq i\leq n}\left\|\hat{\boldsymbol{w}}[i]\right\|^{2}<n$. Then, there exists $1\leq i\leq n$ such that $\left\|\hat{\boldsymbol{w}}[i]\right\|^{2}<1$. Define a positive point $(\boldsymbol{x}_{+},1)$ such that $\boldsymbol{x}_{+}[i]=\boldsymbol{o}_{1}$ and $\boldsymbol{x}_{+}[j]=\boldsymbol{o}_{3}$ for $j\neq i$. Similarly, define a negative point $(\boldsymbol{x}_{-},-1)$ such that $\boldsymbol{x}_{-}[i]=\boldsymbol{o}_{2}$ and $\boldsymbol{x}_{-}[j]=\boldsymbol{o}_{3}$ for $j\neq i$. Then it holds that:

By subtracting Eq. 11 from Eq. 10 we get:

but since $\left|\hat{\boldsymbol{w}}[i]\cdot(\boldsymbol{o}_{1}-\boldsymbol{o}_{2})\right|\leq 2\left\|\hat{\boldsymbol{w}}[i]\right\|$, we have by Eq. 12 $\left\|\hat{\boldsymbol{w}}[i]\right\|\geq 1$, which is a contradiction. ∎

Proposition 6.1 implies that the best possible bound of Brutzkus et al. 2018 for FC networks, or margin bound for linear SVM is $O(n^{2})$ in our setting. Thus for $n=\Theta(d^{r})$, $r\geq 1$ the bounds for FC networks and linear SVM are $O(d^{2r})$. In contrast, Theorem 5.1 shows a generalization guarantee for CNNs of $O(d)$ for any $n$. This gap suggests that CNNs should significantly outperform FCNs and linear SVM in our setting. Next, we provide empirical evidence for this.

Experiments

In this section we provide empirical evaluation of learning with our pooling architecture and compare it to several other models. As baselines we consider:

ConvPool: Our convolution and max-pooling model in Eq. 1. We verified that layer-wise training performs very similarly to standard training, and thus we report results on standard training with Adam (Kingma & Ba 2014) in what follows.

MLP: A standard fully connected neural network with one hidden layer. The network receives the complete $\boldsymbol{x}$ as input (with all patterns). We use a number of hidden neurons that results in the same number of parameters as ConvPool.

SVM: A hard-margin linear SVM with $\boldsymbol{x}$ as input. This will return zero training errors only when the data is linearly separable. This is the case for our distribution ${\cal D}$, but no longer the case when we add noise to the patterns (see below).

All experiments used a test set of size $1000$, and were repeated $5$ times with mean and std reported on figures.

Next, we consider the effect of the number of patterns $n$ on performance. As shown in Proposition 6.1, the norm of the max-margin linear classifier is lower bounded by $n$. Thus, increasing $n$ is expected to result in worse performance for MLP and SVM by the results in the previous section. In Figure 4, we vary the number of patterns, and indeed observe that performances of MLP and SVM deteriorate while that of ConvPool is only mildly affected (we used the same parameters as above and noise level $\left\|\boldsymbol{v}\right\|\leq 1$).

Finally, we evaluate on the MNIST data set. We create a detection problem as in Fig. 5 where the discriminative patterns are the digits three and five and the spurious patterns are all other digits. Each input image contains four patterns (i.e., four digits). We used a relatively small number of patterns to make the problem not linearly separable for moderate sample sizes. We trained a 3 layer convolutional network as in Eq. 1 with 500 channels. Results in Fig. 3(c) again show excellent performance of the pooling model compared to the baselines.

Discussion

In this paper we presented the first analysis of a convolutional max-pooling architecture in terms of optimization and generalization under over-parameterization. Our analysis is for a natural setting of a detection problem where certain patterns “identify” the class and the others are irrelevant. Our analysis predicts a significant performance gap between CNNs and FCNs, which we observe in experiments.

While our analysis is the first step towards understanding pattern detection architectures, many open problems remain. The first is extending the pattern structure from orthogonal patterns to more general distributions. For example, we can consider the discriminative pattern to be a combination of patterns across the image (e.g., the class of the image is positive only if certain multiple patterns appear in the image). Second, it would be interesting to extend the convolution so that there are overlaps between filters (although this is known to generate local optima even for simpler settings (Brutzkus & Globerson 2017)). Finally, a challenging extension is to a multi-layer architecture with repeated application of pooling.

Acknowledgements

This research is supported by the European Research Council (ERC) under the European Unions Horizon 2020 research and innovation programme (grant ERC HOLI 819080). AB is supported by the Google Doctoral Fellowship in Machine Learning.

References

Appendix A Convergence Rates for Theorem 5.1

In Ji & Telgarsky 2019c, Theorem 4.2, they show the following for logistic regression initialized at zero and a certain learning rate schedule. The margin of the learned classifier is $\frac{\gamma}{2}$ where $\gamma$ is the max-margin after $O\left(\frac{1}{\gamma^{2}}\right)$ iterations. $O$ hides a dependency on $\log{m}$. They show this for normalized points with norm 1. In our case (see the proof of Theorem 5.1), the max margin after normalizing the points to have norm 1, is $\frac{1}{\sqrt{d}}$. Thus, under their assumptions, after $O(d)$ iterations we converge to a solution whose margin is a $\frac{1}{2}$-multiplicative approximation of the max margin. Therefore, we obtain for this solution, up to a constant, the same generalization guarantees as the max margin classifier (which we provide in the theorem).

Appendix B Proof of Lemma 5.2

where in the last inequality we used the assumption on $k$. Since $\frac{\left(1-2^{-d+1}\right)}{2(d-1)}\geq\frac{1}{2d}$ and $\frac{\left(1-2^{-d+1}\right)}{2(d-1)}\leq\frac{1}{d}$ for $d\geq 3$, we get that with probability at least $1-2e^{-d}$, $\left|\mathcal{W}^{+}_{0}\cap{\cal A}^{+}\right|\geq\frac{\left(1-2^{-d+1}\right)k}{2(d-1)}-\frac{k}{4d}\geq\frac{k}{4d}$ and $\left|\mathcal{W}^{+}_{0}\cap{\cal A}^{+}\right|\leq\frac{\left(1-2^{-d+1}\right)k}{2(d-1)}+\frac{k}{4d}\leq\frac{k}{d}$. By the symmetry of our problem and definitions of the sets $\mathcal{W}^{+}_{0}$, $\mathcal{W}^{-}_{0}$, ${\cal A}^{+}$, ${\cal A}^{-}$, we similarly get that with probability at least $1-2e^{-d}$, $\frac{k}{4d}\leq\left|\mathcal{W}^{-}_{0}\cap{\cal A}^{-}\right|\leq\frac{k}{d}$. Applying the union bound concludes the proof.

Appendix C Proof of Lemma 5.3

We first prove the following two auxiliary lemmas.

For all $0\leq t\leq T_{1}$ and all $1\leq i\leq k$, $\left\|\boldsymbol{w}^{(t)}_{i}\right\|\leq\eta_{1}(t+1)$.

First we notice that for all $1\leq i\leq k$, $\left\|\frac{\partial\mathcal{L}_{1}}{\partial\boldsymbol{w}_{i}}\left(W,\boldsymbol{a}^{(0)}\right)\right\|\leq 1$. This follows since for all $1\leq j\leq n$ and all $\boldsymbol{x}\in S_{1}$, $\left\|\boldsymbol{x}[j]\right\|=1$ (recall that $\left\|\boldsymbol{o}\right\|=1$ for $\boldsymbol{o}\in\mathcal{O}$).

Therefore, for all $0\leq t\leq T_{1}$ and $1\leq i\leq k$, $\left\|\boldsymbol{w}^{(t)}_{i}\right\|\leq r+\eta_{1}t\leq\eta_{1}(t+1)$. ∎

For all $\boldsymbol{x}\in S_{1}$ and $0\leq t\leq T_{1}$ $\left|N_{\textup{CNN}}[(W^{(t)},a^{(0)})](\boldsymbol{x})\right|\leq\frac{1}{2}$.

By Lemma C.1 we have for all $\boldsymbol{x}\in S_{1}$:

where the last inequality follows by the assumption on $\eta_{1}$. ∎

Lemma 5.3 follows by the following lemma.

With probability at least $1-4e^{-\frac{m}{36}}$, for all $0\leq t\leq T_{1}$ and all $i\in\mathcal{W}^{+}_{0}\cap{\cal A}^{+}$ the following holds:

$\boldsymbol{o}_{1}\cdot\boldsymbol{w}^{(t)}_{i}\geq\frac{t\eta_{1}}{9}$.

For all $j\neq 1$, it holds that $\boldsymbol{o}_{j}\cdot\boldsymbol{w}^{(t)}_{i}\leq r$.

We will prove the claim for $i\in\mathcal{W}^{+}_{0}\cap{\cal A}^{+}$. We prove the two claims by induction on $t$. In the proof by induction we also show a third claim that: for all $\boldsymbol{x}_{+}\in S_{1}^{+}$, $\boldsymbol{p}^{(i)}_{t}(\boldsymbol{x}_{+})=\boldsymbol{o}_{1}$.

For the proof, we condition on the event:

This holds with probability at least $1-4e^{-\frac{m}{36}}$ by applying Hoeffding’s inequality and a union bound (over positive and negative samples).

For $t=0$, we have by definition for all $i\in\mathcal{W}^{+}_{0}\cap{\cal A}^{+}$, $\boldsymbol{o}_{1}\cdot\boldsymbol{w}^{(t)}_{i}>0$. The second claim holds by the definition of the initialization. The third claim follows by the definition of $\mathcal{W}^{+}_{0}\cap{\cal A}^{+}$.

Assume the three claims above hold for $t=T$. We will prove them for $t=T+1$.

Proof of Claim 1. By the gradient update in the first layer, the following holds for $i\in\mathcal{W}^{+}_{0}\cap{\cal A}^{+}$:

By Lemma C.2 we have for all $\boldsymbol{x}\in S_{1}$ $\left|N_{\textup{CNN}}[(W^{(t)},a^{(0)})](\boldsymbol{x})\right|\leq\frac{1}{2}$. Therefore, for all $\boldsymbol{x}_{+}\in S_{1}^{+}$:

By the induction hypothesis, we have for $i\in\mathcal{W}^{+}_{0}\cap{\cal A}^{+}$ and all $\boldsymbol{x}_{+}\in S_{1}^{+}$ that $\boldsymbol{p}^{(i)}_{T}(\boldsymbol{x}_{+})=\boldsymbol{o}_{1}$. Therefore we have:

For all $\boldsymbol{x}_{-}\in S_{1}^{-}$, we have $\boldsymbol{p}^{(i)}_{T}(\boldsymbol{x}_{-})=\boldsymbol{o}_{j}$ for $j\neq 1$ that depends on $\boldsymbol{x}_{-}$. Therefore:

By the facts above we complete the proof of the first claim:

where the last inequality follows from the induction hypothesis.

Proof of Claim 2. Since for all $\boldsymbol{x}_{+}\in S_{1}^{+}$, $\boldsymbol{p}^{(i)}_{T}(\boldsymbol{x}_{+})=\boldsymbol{o}_{1}$ we have for all $1\leq j\leq d$, $j\neq 1$:

By the facts (1) for all $\boldsymbol{x}_{-}\in S_{1}^{-}$ and $j\neq 1$ it holds that $\boldsymbol{p}^{(i)}_{T}(\boldsymbol{x}_{-})\cdot\boldsymbol{o}_{j}\geq 0$ and (2) $l^{\prime}(z)<0$ for all $z$, we have:

where the right inequality follows by the induction hypothesis.

Proof of Claim 3. Since $r<\frac{\eta_{1}(T+1)}{9}$ we conclude by Eq. C and Eq. 23 that for all $\boldsymbol{x}_{+}\in S_{1}^{+}$, $\boldsymbol{p}^{(i)}_{T+1}(\boldsymbol{x}_{+})=\boldsymbol{o}_{1}$. ∎

Appendix D Proof of Lemma 5.5

By Lemma C.1, for all $1\leq t\leq T_{1}$ and $1\leq i\leq k$, $\left\|\boldsymbol{w}^{(t)}_{i}\right\|\leq\eta_{1}(t+1)$. Therefore, for all $1\leq j\leq d$ and $\boldsymbol{x}$ sampled from ${\cal D}$, $\boldsymbol{x}[j]\cdot\boldsymbol{w}^{(t)}_{i}\leq 2\eta_{1}t$.

Appendix E Proof of Part 3 of Theorem 5.1

Our goal is to show that ${\cal D}_{\boldsymbol{z}}$ is linearly separable and can be separated with a classifier of relatively low norm. Then, we will use recent results on logistic regression, which show that GD converges to low norm solutions. Therefore, by optimizing the second layer, $\text{LW}_{\text{CNN}}$ will converge to a low norm solution. Finally, we will apply norm-based generalization bounds to obtain a generalization guarantee for $\text{LW}_{\text{CNN}}$.

where the inequality follows by Lemma 5.2, Lemma 5.3 and Corollary 5.4. By symmetry, we have $-\boldsymbol{z}(\boldsymbol{x}_{-})\cdot\boldsymbol{v}^{*}>1$ for all $(\boldsymbol{x}_{-},-1)\sim{\cal D}$.

Therefore, by this theorem we are guaranteed that:

Specifically, gradient descent converges to zero training loss, i.e., $\lim_{T_{2}\rightarrow\infty}\mathcal{L}_{2}\left(\left(W_{T_{1}},\boldsymbol{a}_{T_{2}}\right)\right)=0$.

By optimality of $\hat{\boldsymbol{a}}$ and Lemma 5.2 we have $\left\|\hat{\boldsymbol{a}}\right\|^{2}\leq\left\|\boldsymbol{v}^{*}\right\|^{2}\leq\frac{80^{2}d^{2}}{k^{2}\eta_{1}^{2}T_{1}^{2}}\frac{2k}{d}=\frac{2\cdot 80^{2}d}{k\eta_{1}^{2}T_{1}^{2}}$. Furthermore, $\left\|\boldsymbol{z}(\boldsymbol{x})\right\|^{2}\leq 4k\eta_{1}^{2}T_{1}^{2}$ by Lemma 5.5. Therefore, we have $\left\|\hat{\boldsymbol{a}}\right\|^{2}\left\|\boldsymbol{z}(\boldsymbol{x})\right\|^{2}=O(d)$. Thus, by a standard margin generalization bound (e.g. Theorem 26.13 in Shalev-Shwartz & Ben-David 2014 or Bartlett & Mendelson 2002) we have with probability at least $1-\delta$:

where $O$ hides an additive term which depends on $\delta$.