Implicit Convex Regularizers of CNN Architectures: Convex Optimization of Two- and Three-Layer Networks in Polynomial Time
Authors: Tolga Ergen
Mert Pilanci
Venue: ICLR 2021 Spotlight (2021)
Keywords: Convex optimization
non-convex optimization
group sparsity
$\ell_1$ norm
convex duality
polynomial time
deep learning

Abstract: We study training of Convolutional Neural Networks (CNNs) with ReLU activations and introduce exact convex optimization formulations with a polynomial complexity with respect to the number of data samples, the number of neurons, and data dimension. More specifically, we develop a convex analytic framework utilizing semi-infinite duality to obtain equivalent convex optimization problems for several two- and three-layer CNN architectures. We first prove that two-layer CNNs can be globally optimized via an $\ell_2$ norm regularized convex program. We then show that multi-layer circular CNN training problems with a single ReLU layer are equivalent to an $\ell_1$ regularized convex program that encourages sparsity in the spectral domain. We also extend these results to three-layer CNNs with two ReLU layers. Furthermore, we present extensions of our approach to different pooling methods, which elucidates the implicit architectural bias as convex regularizers.

Published as a conference paper at ICLR 2021
IMPLICIT CONVEX REGULARIZERS OF CNN ARCHI- TECTURES: CONVEX OPTIMIZATION OF TWO- AND THREE-LAYER NETWORKS IN POLYNOMIAL TIME
Tolga Ergen & Mert Pilanci
Department of Electrical Engineering
Stanford University Stanford, CA 94305, USA
(ergen, pil @estanord.edu
ABSTRACT
We study training of Convolutional Neural Networks (CNNs) with ReLU activa- tions and introduce exact convex optimization formulations with a polynomial complexity with respect to the number of data samples, the number of neurons, and data dimension. More specifically, we develop a convex analytic framework utilizing semi-infinite duality to obtain equivalent convex optimization problems for several two- and three-layer CNN architectures. We first prove that two-layer CNNs can globally optimized via an E norm regularized convex program. We then show that multi-layer circular CNN training problems with single ReL.U layer are equivalent to an l regularized convex program that encourages sparsity in the spectral domain. We also extend these results to three-layer CNNs with two ReLU layers. Furthermore, we present extensions our approach to differ- ent pooling methods, which elucidates the implicit architectural bias convex regularizers.
INTRODUCTION
Convolutional Neural Networks (CNNs) have shown remarkable success across various machine learning problems (LeCun et al. 2015). However, our theoretical understanding of CNNs still remains restricted, where the main challenge arises from the highly non-convex and nonlinear structure of CNNs with nonlinear activations such as ReLUU. Hence, we study the training problem for various CNN architectures with ReLU activations and introduce equivalent finite dimensional convex formulations that can be used to globally optimize these architectures. Our results characterize the role of network architecture terms of equivalent convex regularizers. Remarkably, we prove that the proposed methods polynomial time with respect all problem parameters.
Convex neural network training was previously considered in Bengio et al. (2006); Bach (017)). However, these studies restricted to two-layer fully connected networks with infinite width, thus, the optimization problem involves infinite dimensional variables. Moreover, it has been shown that even adding single neuron neural network leads non-convex optimization problem which cannot be solved efficiently (Bach) 2017). Another line of research in Parhi & Nowak (2019); Ergen Pilanci (2019] 2020a b db Pilanci & Ergen (2020); Savarese al. (2019); Gunasekar et al. (2018) 8); Maennel et al. (2018) Blane et (2019): Zhang et al. (2016) focuses on the effect of implicit and explicit regularization in neural network training and aims explain why the resulting network generalizes well. Among these studies, Parhi & Nowak (2019); Ergen & Pilanci (2020b)
Savarese et al.) (2019) proved that the minimum & norm two-layer network that perfectly fits a one dimensional dataset outputs the linear spline interpolation. Moreover, Gunasekar et al. (2018) studied certain linear convolutional networks and revealed an implicit non-convex quasi-norm regularization. However, the number of layers increases, the regularization approaches to to quasi-norm, which is not computationally tractable. Recently, Pilaacii & Ergen (2020) showed that two-layer CNNs with regularized convex problems.
linear activations can be equivalently optimized as nuclear and E Although all the norm characterizations provided by these studies are insightful for future research, existing results quite restricted due to linear activations, simple settings or intractable problems.

---

Published as a conference paper at ICLR 2021
Table CNN architectures and the corresponding norm regularization in our convex programs
Blager equason
2-Aayer
F
D-laer eqaiio
El
2/agerr equico
S-laye equaing
L-lege equco
Archirectre
Σ, maxpool ((1
Σ. Xaliyay
(X,u,), Wor),
X
Implict Requlataztion
Σ1 ls
(ruckaa ncea)
El
Shallow CNNs and their representational power: As opposed to their relatively simple and shal- low architecture, CNNs with two/three layers very powerful and efficient models. [Belilovsky et al. (2019) show that greedy training of two/three layer CNNs can achieve comparable performance to deeper models, e.g., VGG-11(Simone (SSionnyan & Zisserman 2014). However, a full theoretical under- standing and interpretable description of CNNs even with a single hidden layer is lacking in the literature.
Our contributions: Our contributions can be summarized as follows:
We develop convex programs that are polynomial time with respect to all input parameters: the number of samples, data dimension, and the number of neurons to globally train CNNs. To the best of our knowledge, this is the first work characterizing polynomial time trainability of non- convex CNN models. More importantly, we achieve this complexity with explicit and interpretable convex optimization problems. Consequently, training CNNs, especially in practice, can be further accelerated by leveraging extensive tools available from convex optimization theory.
Our work reveals hidden regularization mechanism behind CNNs and characterizes how the architecture and pooling strategies, e.g., max-pooling, average pooling, and flattening, dramatically alter the regularizer. As we show, ranging from & and & norm nuclear norm (see Table []] for details), ReLU CNNs exhibit an extremely rich and elegant regularization structure which is implicitly enforced by architectural choices. In convex optimization and signal processing, l, la and nuclear norm regularizations are well studied, where these structures have been applied in compressed sensing, inverse problems, and matrix completion. Our results bring light to unexplored and promising connections of ReLU CNNs with these established disciplines.
Notation and preliminaries: We denote matrices/vectors as uppercase/lowercan which subscript indicates a certain element/column. We use Ig for the identity matrix of size k. We denote the set of integers from 1 to n as [n)]. Moreover, || || and || ||~ are Frobenius and nuclear norms and B, == {u E Cd ||u/|p S 1} is the unit E, ball. We also use [[x 2 0] as an indicator.
bold letters, for
To keep the presentation simple, we will use regression framework with scalar outputs and squared loss. However, we also note that all of our results can be extended to vector outputs and arbitrary convex regression and classification loss functions. We present these extensions in Appendix. In our regression framework, we denote the input data matrix and the corresponding label vector as X E Rad and E R", respectively. Moreover, we represent the patch matrices, i.e., subsets of columns, extracted from X as X E Raxh &o E [K], where denotes the filter size. With this notation, {X k= describes a convolution operation between the filter
R and the data matrix
X. Throughout the paper, we will use the ReLU activation function defined as (x) 4 = max(0, x). However, since CNN training problems with ReLUS are not convex in their conventional form, below we introduce an alternative formulation for this activation, which will be crucial for our derivations.
Prior Work (Pilanci & Ergen 2020): Recently, Pilanci & Ergen 2020) introduced an exact convex formulation for training two-layer fully connected ReLU networks in polynomial time for training data X E Raxd of constant rank, where the model is standard two-layer scalar output network fx(X) = Σm (Xuy), ay. However, this model has three main limitations. First, as noted by the authors, even though the algorithm is polynomial time, i.e., O(n"), ), provided that r == rank the complexity exponential in = d. i.e., O(n"), if X is full rank. Additionally, as a direct consequence of their model, the analysis is limited to fully connected architectures. Although they briefly analyzed some CNN architectures in Section 4, as emphasized by the authors, these are either fully linear (without ReLU) or separable over the patch index l as fully connected models, which do not correspond to weight sharing in classical CNN architectures in practice. Finally, their analysis does not extend to three-layer architectures with two ReLU layers since the analysis of two ReLU layers is significantly more challenging. On the contrary, we prove that classical CNN architectures can be globally optimized by standard convex solvers in polynomial time independent of the rank
'The results on two-layer CNNs are presented in Appendix A.4
This refers to an I--layer network with only one ReI.U layer and circular convolutions.
2

---

Published as a conference paper at ICLR 2021
Table Computational complexity results for training CNNs to global optimality using a standard interior-pois porrtttt-poottttoe solver (n: # of data samples, d: data dimensionality, : # of patches, re: maximal rank for the patch matrices (r' S h), rec: rank for the circular convolution, h: filter size ,m: of filters)
2-layer equation
2-layer equation 7
L-layer cquation
3-layer equation
# of variables # of constraints
PhPonnv 2nP InPPonnK K
Pheromo
AdPomme
AdP,PsK PrK 2m (P 1)P3
PnPoran
Complexity
o
0 1r 2x
d m97e.
(see Table 2 More importantly, we extend this analysis to three-layer CNNs with two ReLU layers to achieve polynomial time convex training proven in Theorem 4.1
1.1 HYPERPLANE ARRANGEMENTS
Let H. be the set of all hyperplane arrangement patterns of X, defined as the following set
H = ((ignn((X))) : w WERR.
which has finitely many elements, i.e., [7] S NH < 0o, NH E N. We now define a collection of sets that correspond to positive signs for each element in H. by S [[=[(Un-- [[Un.-I(t)) We first note that ReLU is an elementwise function that masks the negative entries of a vector or matrix. Hence, given a set S E S, we define diagonal mask matrix D(S) E R defined as D(S), 1/i E S]. Then, we have an alternative representation for ReLU as (Xw)+
h H}.
Xw given XW 2 0 and (I, D(S) Xw < 0. Note that these constraints can be compactly defined as (2D ()) I,) Xw 2 O. we denote the cardinality of S as P. i.e. the number of regions in partition of R by hyperplanes passing through the origin and are perpendicular to the rows of the data matrix X with r == rank(X) (X) s min(n, d), then P can be upper-bounded as follow
(e(n-1))
e 1)
P 2
<
2r
h
k=U
Ojha 2000
Stanley et al. 2004
Winder 1966
Cover 1965) (see Appendix A.2 for details).
1.2 CONVOLUTIONAL HYPERPLANE ARRANGEMENTS
We now define a notion of hyperplane arrangements for CNNs, where we introduce the patch matrices (X+ k= instead of directly operating on X. We first construct a new data matrix as M = [X:; X2; ... Xx) Ra We then define convolutional hyperplane arrangements the hyperplane arrangements for M and denote the cardinality of this set as P Peonv. Then, we have
nK- -
[((nK 1)
To
P Peonv 2
< 2r.
Te
Amm
where r=: rank(M) < / and K polynomial in n and Similarly, we consider hyperplane arrangements for circular CNNs followed is circulant matrix generated by the elements
d= uride
+ 1. Note that when the filter size h is fixed, P Peone is
by a linear pooling layer, i.e., XUw, where U E u RA Then, we define circular convolutional hyperplane arrungements and denote the cardinality of this set as P Pezonu, which is exponential in the rank of the circular patch matrices, i.e., Tec-
Remark 1.1. There exist P hyperplane arrangements of X where P is exponential in Thus, if X is full rank, r = d, then P can be exponentially large in the dimension As we will show, this makes the training problem for fully connected networks challenging. On the other hand, for CNNs, the number of relevant hyperplane arrangements P Poono is exponential in Te- M M is full rank, then To h < d and accordingly Poono < P. This shows that the parameter sharing structure in CNNs enables a significant reduction in the number of possible hyperplane arrangements. Consequently, as shown in the sequel and Table our results imply that the complexity of training problem is significantly lower compared to fully connected networks.
2 TWO-LAYER CNNS
In this section, we present exact convex formulation for two-layer CNN architectures.
3

---

Published as a conference paper at ICLR 2021
2.1 TWO-LAYER CNNS WITH AVERAGE POOLING
We first consider an architecture with m filters, average pooling i.e., is defined as fo(X) == Σ, Σx (Xx Wj with parameters 0 == {u,, wÿ}: and standard weight decay regularization, which can be trained via the following problem
m
K
m
pi
min w
Xxuy) Wj -
+
||
+ wf)
(I)
3-11 2
where u, R and w E 1 are the filter and output weights, respectively, and 8 regularization parameter. After a rescaling (see Appendix A.3), we obtain the following problem
K
pi
min augary Feen By EB
( By y + 31/w//12-
(2)
2
j=1
Then, taking dual with respect w and changing the order of min-max yields the weak dual
K
pi 2 = max
=ma
1 2
y1l
s.t. max uEB,
Σ
V (X+u)_
- 3,3,
(3)
which is a semi-infinite optimization problem and the dual can be obtained as finite dimensional convex program using semi-infinite optimization theory (Goberna López-Cerdá 1998). The same dual also corresponds to the bidual of equation Surprisingly, strong duality holds when exceeds a threshold. Then, using strong duality, we characterize a set of optimal filter weights as the extreme point of the constraint in equation Below, formulation for equation [
this characterization to derive exact convex
Theorem 2.1. Let be number such that m 2 m² for some m E N. m S n + then strong i.e., pi di, and the equivalent convex program for equation 7 is
duality holds for equation
Peonv K
Peanv
1
min feree P 0, ER
D(S X (c - ci) -y +
(leaal2 + (|c//12)
(4)
2
s.f. ( 2 0, (2D(5)) - &, 2 O, Vi,k.
Moreover, optimal solution to equation 7 Twtt mn* filters can be constructed as follows
of
(u',,, w)x,)
VileTlla
||c 1l2 >0
Vilc""aa'
(ujun (ujn)))f))=
c;
-llctll
||cill2 >
Vilc;lla*
where {c of Hem are optimal, m² EPern 1[l|c]1l * 0] + Elene 1[1| |22 + 0j. and Jsi E [[J.]] given the definitions Ji = (i) ||c,,| 0} and Jn (iz ||c, > 0}
Therefore, we obtain a finite dimensional convex formulation with PhPoone variables and 2nP Poon K constraints for the non-convex problem in equation] 1 Since Poonn is polynomial in and d given fixed re & h, equation can be solved by a standard convex optimization solver in polynomial time.
Remark 2.1. Table shows that for fixed rank re, or fixed filter size h, the complexity is polynomial in all problem parameters: n (number of samples), m (number of filters, i.e., neurons), and (dimension). The filter size h is typically a small constant, e.g., h = for 3 filters. We also note that for fixed n and rank(X), = d, the complexity of fully connected networks is exponential in d, which cannot be improved unless P N. even for m 2 (Boob al.) 2018 Pilanci & Ergen 2020 However, this result shows that CNNs can be trained to global optimality with polynomial complexity as convex program.
e We define the average pooling operation as ΣK (Xau)) which is also known as global average pooling.
'iine proof technique similar for different CNNSs, we present only the proof of Theorem 2.1 in Section
The rest of the proofs can be found in Appendix (including the strong duality results in A.7
4

---

Published as a conference paper at ICLR 2021
Interpreting non-convex CNNs convex variable selection models: Interestingly, have the sum of the squared & norms of the weights (i.e., weight decay regularization) in the non-convex problem equation D as the regularizer. however, the equivalent convex program in equation 4 is regularized by the sum of the & norms of the weights. This particular regularizer known as group & norm, and is well-studied in the context of sparse recovery and variable selection (Yuan & Lin |006 Meier et al., 2008). Hence, our convex program reveals an implicit variable selection mechanism the original non-convex problem. More specifically, the original features in X are mapped to higher dimensions via convolutional hyperplane arrangements as ) feane ) and followed by convex variable selection strategy using the group & norm. Below, we show that this implicit regularization changes significantly with the CNN architecture and pooling strategies and can range from l and &2 norms to nuclear norm.
2.2 TWO-LAYER CNNS WITH MAX POOLING
Here, we consider the architecture with max pooling, i.e., fo(X) Σ3 maxpool ((xxau)))xx) wy. which is trained as follows
pi
min
maxpool (((Xxu;)4) wy y B||w||
(5)
[u
where maxpool(.) is an elementwise max function over the patch index k. Then, taking dual with respect to w and changing the order of min-max yields
pi 2 di max - 212 1yl1 s.t. max |v" maxpool (((Xx))) nEB:
B. (6)
Theorem 2.2. Let m be a number such that m 2 m² for some m E N, m I n + 1, then strong duality holds for equation
i.e., pi di, and the equivalent convex program for equation 5
min (c Peonv c,,c,E"MM
1
Pron
Σ
D(S X (c) (c) -y +
Poans
Σ
(1aall2 + ||c/112)
2
2
S.I. -2D(S))LL,Xxco 0, (2D(5)) - I.) 2 V,Vi,
D X ) ((S)) Z
Moreover, an optimal solution to equation Jean be constructed from equation 7 as in Theorem 2.7
We note that max pooling corresponds to the last two linear constraints of the above program. Hence, max pooling can be interpreted as additional regularization, which constraints the parameters further.
MULTI-LAYER CIRCULAR CNNS
In this section, we first consider L-layer circular CNNs with 2 pooling layers before ReLU, i.e. So (x) = E3 [I Uij Ulywis) W2j. which is trained via the following non-convex problem
2
min ([ws)leT wiglwas)) Wi vL.
2
1
Σ
m
X
L-2
II
U W
W2 y
8
2
3
(1l +11,+ (8)
j=1
where Uij Rxd is circulant matrix generated using uy E R and U1 {u uu 22-2)
Ur E Rd,, "ol, [ -
| 1) and we include unit norm constraints w.l.o.g.
Theorem 3.1. Let m be a number such that m 2 m² for some m E N, m. S n + then strong duality holds for equation 8 i.e., p dł, and the equivalent convex problem is
2
Peeune
B
Pecomo
min ( c.ee Wi
D(S)) (c) -c: -.)
-y
([|c:]l + [l(]11))
(9)
d
2
(2D(S)) x,); 20, (2D I))xc( V,Vi,
5

---

Published as a conference paper at ICLR 2021
where = XF and F Cdxd is the DFT matrix. Additionally, as in Theorem 2.1 an optimal solution to equation 8 from equation
construct
Remarkably, although the sum of the squared & norms in the non-convex problem in equation 8 stann for the standard weight decay regularizer, the equivalent convex program in equation is regularized by the sum of the l norms which encourages sparsity in the spectral domain X. Thus, even with the simple choice of the weight decay the non-convex problem, the architectural choice for a CNN implicitly employs more sophisticated regularizer that is revealed by our convex optimization approach. We further note that in the above problem ((S,) X the spectral features of subset of data points which are seperated by hyperplane from all the other spectral features. While such spectral features be very predictive for images in many applications, we believe that convex program also sheds light into the undesirable bias of CNNs, c.g., towards certain textures and low frequencies (Geirhos al. 2018 Rahaman al. 2019).
4 THREE-LAYER CNNs WITH TWO RELU LAYERS Here, we consider three-layer CNNs with two ReLU layers, which has the following primal problem
m
m
P3
min (ug.way.2aa 1 EyEB2
(Xau;) wijk
W21 y
(Iwi)) w22)) (10)
with [o(X)= E, (Ex(XRR)) w1)k) w2j and the following convex equivalent problem.
Theorem 4.1. Let m be a number such that m 2 m² for some m² & N, m² S n + then strong duality holds for equation
i.e. p3 dž, and the equivalent convex problem is
P K
min (ouje dyse,
Saa
Inja Ii D(S - ( -
+
(I[C,]] [[C])])))
2
j=
s.t. (2)( Inn
Lij 20, (2D()))) I, Xn)a 2 0, Vi,jk
(11)
P1 K
(2D(S2)) I.,) Σ
Σ
Typ X(S 20, (2D(S)) - X.C.E 20
where Pi and P2 are the number hyperplane arrangements for the first and second layers, Lija E [+1} are sign patterns to enumerate all possible sign patterns of the second layer weights, and Cg [cij.... (see A.pendix(A.10 further details).
It is interesting to note that, although the sum of the squared & norms in the non-convex problem equation 10 the standard weight decay regularizer, the equivalent convex program equation [T is regularized by the sum of the Frobenius norms that promote matrix group sparsity, where the groups are over the patch indices. Note that this is similar to equation 4except an extra summation due to having more ReLU layer. Therefore, ReLU implicitly regularizes for group sparsity over a richer hierarchical representation of the data via consecutive hyperplane arrangements.
observe that adding more convolutional layers with
5 PROOF OF THE MAIN RESULT (THEOREM 2.1
Here, we provide our proof technique for Theorem 2.1 We first focus on the single-sided constraint
K
max
(X,) - 3,
(12)
'The details are presented in Appendix A.9

---

Published as a conference paper at ICLR 2021
where the maximization problem can be written
T
DD(S))xau s.t. (2D(S*) 1,)X, 0, Ak.
max s Sinl u
(13)
S ES
Since the maximization is convex and strictly feasible for fixed D(S*), equation can be written as
max min max
D (2D(s*) I, xx,)
s sin 20 B s*Es
K Σ D(s X5 + +o (2D(5*) - Xx
max min S*I 20 s*es
now enumerate all hyperplane arrangements and index them an arbitrary order, i.e., denoted as Prone
(tt...,,sk where i E [Pomn))
= |Sk], Sx == (SS)...., E E Vk, i}. Then,
K
equation
Vi E [P Peonlly min ax
Σ
D(*) + a (2D(S)) I
Vi E [P Poonu], 3ock 2 S.t.t
D X a 2D (S
I,, X
S.9.
We now use the same approach for the two-sided constraint in equation
to obtain the following
K
max
2
1 ll
1 1112
1
2
s.t.
v
- I,
S (14)
k=1
K
D(S X + a (2D(S)) - Xx
S B, Vi.
Note that this problem is convex and strictly feasible for v 0ik- d = 0. Therefore, Slater's conditions and consequently strong duality holds, and equation 14
can can be written as
Peane
K
min X.X22
max
2 l|v
y112 +
11y 2
X
B
DD X + I (2D(S)) - I, Ix,
CESk a/ 20
Peine
K
X
D(S + o (2D(S)) I., Xx
(15)
Next. we first introduce variables z,, 2 R Then, by recalling Sion's minimax theorem 1958), we change the order the inner max max-min as follows
Sion
Peans
K X
min min X, EB2 EB an..a a 20
max -211v llv - y1 + 1lyl2 +
A
B+
DV'
(2D
I,,
2;
im
Ponns
K
B
Σ
T
D
+ a (2D(S I, I,,X2
(16)
now compute the maximum with respect to v, Olkk; a' analytically to obtain the following
Peona Σ
Prann
min min 22 c
D(S X (X/z) \,zi) -y + +
(As + X²)
2
(2D(S!) X,2, 2 (2D S I, X2, 2 0, Vi,k.
(17)
7

---

Published as a conference paper at ICLR 2021
10
109
Trial 82
Objedhve Value
Trial #5
Conves opt vol
Ohiochve
10
10.4
Time(s)
(a) Independent realizations with m =
(b) Independent realizations with m 15
Figure 1: Training cost of the three-layer circular CNN trained with SGD (5 initialization trials) on synthetic dataset (n marker represent the objective value obtained by the proposed convex program in equation and the non-convex objective value in equation of feasible network with the weights found by the convex program, respectively. We use markers to denote the total computation time of the convex solver.
20, 3. stride 1). where the green and red line with
0.95
Osjeciive Value
10-1
Test Test Accuracy
0.9
Trial
Trial
Trial
Trial
Trial
opt
convex
10
0.75
100
200
900
400
500
100
200
300
400
500
Timo(s)
Timo(s)
(a) MNIiS-Trraning objective
(b) MNIST- accuracy
0.75
Objective Value
1011
Test Accuraoj
0.85
Trial
Trial
0.6
2
Convex opt, vol.
convex
0.5
Time(s)
Time(s)
(c) STEAR10-Training objective
(d) CIFAR10- 10RRO0-Tee Test accuracy
Figure 2: Evaluation of the three-layer circular CNN trained with SGD (5 initialization trials) on
subset of MNIST (n -9, d = 50, 20, h 3, stride 1) and CIFARIO (n -9, d 50, m 40, h 3, stride = 1).
Then, apply change of variables and define λιz; and cf = Mzk. Thus, obtain
Peans K Σ
2
Pronv
min C. ERA 2
Σ
D(S X (c) - c;) y
+
Σ
||c|||2+|||///// + [|c/
1=1 k=1
2
i=1
s.t. (2D(S
I,) 0, (2D(S) I, X.cc O, Vi,k,
(18)
since X; = ||c/12 and X ||c||2 are feasible and optimal. Then, using the prescribed {uz, w me we evaluate the non-convex objective in equation as follows
(Ivie'
8
cf
pi < Xxuj)+w3 y
+
Σ
Vio
+
V
lc
l1
2
lla
(=1,c," #0
Poune
<lyct ct V||c
I'
|
+
I,c; y/
which has the same objective value with equation| 18 Since strong duality holds for the convex
program, pi = dj. which is equal the value of equation 18 achieveed by the prescribed parameters.
8

---

Published as a conference paper at ICLR 2021
6 NUMERICAL EXPERIMENTS
In this sectior 7 dataset, where (n. d) = (6, 20), X E TR6x20 is generated using multivariate normal distribution with zero mean and identity covariance, and y = [1 11 - 11j². We then train the three- layer circular CNN model in equation using SGD and the convex program equation In Figure I we plot the regularized objective value with respect to the computation time with 5 different independent realizations for SGD. We also plot both the non-convex objective in equation g and the convex objective in equation Canatiiooooor for our convex program, where optimal prescribed parameters are used to convert the solution the convex program to the original non-convex CNN architecture (see Appendix A.9). In Figure Ta we use 5 filters with h = 3 and stride 1, where only one trial converges to the optimal objective value achieved by both our convex program and feasible network. As increases, all the trials are able to converge to the optimal objective value in Figure 16 We also evaluate the same model on subset of MNIST (LeCun) and CIFARIO (Krizhevsky et al. 2014) for binary classification. Here, we first randomly sample the dataset and then select (n, d, m, h. stride) = (99, 50, 20, 3. 1) and batch size of 10 for SGD. Similarly for CIFAR 10, we select (n, d, m, h, stride) = (99, 50, 40,3,1) 1) and a batch size of 10 for SGD. In Figure 2 plot both the regularized objective values in equation S and equation [ and the corresponding test accuracies with the computation time. Since the number of filters is large enough, all the SGD trials converge the optimal value provided by our convex program.
we present numerical experiments to verify our claims. We first consider a synthetic
CONCLUDING REMARKS
We studied various non-convex CNN training problems and introduced exact finite dimensional convex programs. Particularly, we provide equivalent convex characterizations for ReLU CNN architectures in a higher dimensional space. Unlike the previous studies, we prove that these equivalent characterizations have polynomial complexity in all input parameters and can be globally optimized via convex optimization solvers. Furthermore, we show that depending on the type of a CNN architecture, equivalent convex programs might exhibit different norm regularization structure, c.g., L,, l2, and nuclear norm. Thus, we claim that the implicit regularization phenomenon in modern neural networks architectures can be precisely characterized convex regularizers. Therefore, extending our results to deeper networks is a promising direction. We also conjecture that the proposed convex approach modern deep learning architectures. For example, after our work, Ergen et al. (202T) studied batch normalization through our convex framework and revealed implicit patchwise whitening effect. Similarly, /ahiner et (202T) extended our model to vector outputs. More importantly, in the light of our results, efficient optimization algorithms can be developed to exactly (or approximately) optimize deep CNN architectures for large scale experiments in practice, which is left for future research.
also be used to analyze popular heuristic techniques train
ACKNOWLEDGEMENTS
This work was partially supported by the National Science Foundation under grants IIS- and ECCS-2037304, Facebook Research, Adobe Research and Stanford SystemX Alliance.
REFERENCES
Akshay Agrawal, Robin Verschueren, Steven Diamond, and Stephen Boyd. A rewriting system for convex optimization problems. Journal of Control and Decision, 5(1):42-60, 2018.
Francis Bach. Breaking the curse of dimensionality with convex neural networks. The Journal of Machine Learning Research, 18(1):6296681, 2017.
Eugene Belilovsky, Michael Eickenberg, and Edouard Oyallon. Greedy layerwise learning can scale to imagenet. In International Conference on Machine Learning, pp. 583-593, 2019.
6 Additional numerical results can be found in Appendix A.1
We use CVX (Grntt& & Boyd 2014) and CVXPY (Diamond & Boyd 2016 Agrawal et al. 2018 with the
SDPT3 solver Tütüncüü et al. 2001 solve convex optimization prohlems.

---

Published as a conference paper at ICLR 2021
Yoshua Bengio, Nicolas L Roux, Paseal Vincent, Olivier Delalleau, and Patrice Marcotte. Convex neural networks. In Advances in neural information processing systems, pp. 123-130, 2006.
Guy Blanc, Neha Gupta, Gregory Valiant, and Paul Valiant. Implicit regularization for deep neural networks driven by an ornstein-uhlenbeck like process. CoRR, abs/1904.09080, 2019. URL
http://arxiv.co
abs /1904.994.. 09080
Digvijay Boob, Santanu Dey, and Guanghui Lan. Complexity of training relu neural network. arXiv preprint arXiv:1809. 10787, 2018.
Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
Thomas M Cover. Geometrical and statistical properties of systems of linear inequalities with applications in pattern recognition. IEEE transactions electronic computers, (3):326-333) 334, 1965.
Steven Diamond and Stephen Boyd. CVXPY: Python-embedded modeling language for convex optimization. Journal of Machine Learning Research, 17(83):1-5, 2016.
Herbert Edelsbrunner, Joseph O' O'Rourke, and Raimund Seidel. Constructing arrangements of lines and hyperplanes with applications. SIAM Journal on Computing, 1 15(2):341-363. 1986.
Tolga Ergen and Mert Pilanci. Convex duality and cutting plane methods for over-parameteriiee neural networks. In OPT-ML workshop, 2019.
Tolga Ergen and Mert Pilanci. Convex programs for global optimization of convolutional neural networks in polynomial-time In OPT-ML workshop, 2020a.
Tolga Ergen and Mert Pilanci. Revealing the structure of deep neural networks via convex duality. arXiv preprini 2rXiv:2002. 1219, 2020b.
Tolga Ergen and Mert Pilanci. Convex geometry and duality of over- over- parameterized neural networks. arXiv preprint arXiv:200..11219 2020c.
Tolga Ergen and Mert Pilanci. Convex geometry of two-layer relu networks: Implicit autoencoding and interpretable models. In Silvia Chiappa and Roberto Calandra (eds.), Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pp. 4024 4033, Online, 26-28 Aug 2020d. PMLR. URL
prwss v 08 0 html
Tolga Ergen, Arda Sahiner, Batu Ozturkler, John Pauly, Morteza Mardani, and Mert Pilanci. Demys- tifying batch normalization in relu networks: Equivalent convex optimization models and implicit regularization. 2021.
Robert Geirhos, Patricia Rubisch, Claudio Michaelis, Matthias Bethge, Felix A Wichmann, and Wieland Brendel. Imagenet-trained cnns are biased towards texture; increasing shape bias improves accuracy and robustness. In International Conference on Learning Representations, 2018.
Miguel Angel Goberna and Marco López-Cerdá. Linear semi-infinite optimization. 01 1998. doi: 10.10077978- 14499998044-13
Michael Grant and Stephen Boyd. CVX: Matlab software for disciplined convex programming, version 2.1. http:://vve cwm/ cvx March 2014.
Suriya Gunasekar, Jason D Lee, Daniel Soudry, and Nati Srebro. Implicit bias of gradient descent on linear convolutional networks, In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems 31, pp. 9461-9477 Curran Associates, Inc., 2018.
Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. The CIFAR-10 dataset. htttp://ww... Eoronto. wttpeeteeddkkkkiii/eeeeee
html 2014.
Yann LeCun. The MNIST database of handwritten digits. lec.na
mn i st/
10

---

Published as a conference paper at ICLR 2021
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. nature, 521(7553):436 444, 2015.
Hartmut Maennel, Olivier Bousquet, and Sylvain Gelly, Gradient descent quantizes relu network features. arXiv preprint Ttth:/8003088661 2018.
L. Meier, S. van de Geer, and P. Bühlmann. The group lasso for logistic regression. Journal of the Royal Statistical Society, Series B, 70:53-71, 2008.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. search of the real inductive bias: On the role of implicit regularization in deep learning. arXiv preprint arXiv:1412.600 2014.
Piyush C Ojha. Enumeration of linear threshold functions from the lattice of hyperplane intersections. IEEE Transactions on Neural Networks, 11(4):899850, 2000.
Rahul Parhi and Robert D. Nowak. Minimum "norm" neural networks are splines, 2019.
Mert Pilanci and Tolga Ergen. Neural networks are convex regularizers: Exact polynomial-time convex optimization formulations for two-layer networks, 2020.
Nasim Rahaman, Aristide Baratin, Devansh Arpit, Felix Draxler, Min Lin, Fred Hamprecht, Yoshua Bengio, and Aaron Courville. On the spectral bias of neural networks. In International Conference on Machine Learning. pp. 5301-5310, PMLR, 2019.
Benjamin Recht, Maryam Fazel, and Pablo Parrilo. Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM review, 52(3):411-011 2010.
Saharon Rosset, Grzegorz Swirszez, Nathan Srebro, and Ji Zhu. L1 regularization in infinite dimensional feature spaces. In International Conference on Computational Learning Theory, pp. 544-558. Springer, 2007.
Walter Rudin. Principles of Mathematical Analysis. McGraw-Hill, New York, 1964.
Arda Sahiner, Tolga Ergen, John M. Pauly, and Mert Pilanci. Vector-output relu neural network problems copositive programs: Convex analysis of two layer networks and polynomial-time algorithms. In International Conference on Learning Representations, 2021. URL https //openreview. net/ ottp://eoooommmaaaoooooapppppaa
Pedro Savarese, Itay Evron, Daniel Soudry, and Nathan Srebro. How do infinite width bounded norm networks look in function space? CoRR, abs/1902.050400, 2019. URL http:://axiiv.orr
abs/1902. 05040
Alexander Shapiro. Semi-infinite programming, duality, discretization and optimality conditions. Optimization, 133-)1133-161, 2009.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv:1409.1556, 2014.
Maurice Sion. On general minimax theorems. Pacific J. Math., 8():171-176, 1958. URL https
Richard Stanley al. An introduction to hyperplane arrangements. Geometric combinatorics, 13: 496. 2004.
RH Tütüncü, KC Toh, and MJ Todd. Sdpt3 matlab software package for semidefinite semidefinite-quadratii linear programming, version 3.0. Web page http://www. math. nus. edu. sg/mattohkc/sddpt. html, 2001.
RO Winder. Partitions of n-space by hyperplanes. SIAM Journal on Applied Mathematics, 14(4): 811-818, 1966.
Ming Yuan and Yi Lin. Model selection and estimation in regression with grouped variables. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 68(1):49-67, 2006.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint arXiv: /6/ 1.05330 2016.
11

---

Published as a conference paper at ICLR 2021
Table of Contents
Appendix
Additional numerical results
12
A.2
Constructing hyperplane arrangements in polynomial time
12
A.3
Equivalence of the & penalized objectives)
14
A.4
Two-layer linear CNNs
A.5
Extensions vector outputs
A.6
Extensions to arbitrary convex loss functions
17
A.7
Strong duality results
18
A88
Proof Theorem 2.2
19
Proof Theorem
20
10 Proof of Theorem
23
A APPENDIX
In this section, we present additional materials and proof' of the main results that are not included in the main paper due to the page limit.
A.I ADDITIONAL NUMERICAL RESULTS
Here, we present additional numerical experiments to further verify our theory. We first perform an experiment with another synthetic dataset, where X RR, is generated using a multivariate normal distribution with zero mean and identity covariance, and y = [1 1111 - -1 In this case, we use the two-layer CNN model in equation and the corresponding convex program in equation 4 In Figure g we perform the experiment using 5, 8, 15 filters of size h 10 and stride 5, where we observe that as the number of filters increases, the ratio of the trials converging to the optimal objective value increases well.
In order to apply our convex approach in Theorem 2.1 to larger scale experiments, we now introduce unconstrained version of the convex program in equation 4 as follows
1 Peonu K
Peans
min (f Peonv 2 c E.c Wi
D(S X (c- c.)
+ -c)
(leall2 + ||c]
(19)
kmm
2
Paonv
pl
Σ (-(2D())) I,)X ( II, I,)x
where p a trade-off parameter. Since the problem in equation 19 in an unconstrained form, we can directly optimize its parameters using conventional algorithms such as SGD. Hence, we use PyTorch to optimize the parameters of two-layer CNN architecture using both the non-convex objective in equation] and the convex objective in equation 19 where we use the full CIFAR-10 10 dataset for binary classification, i.e., (n, d) = (10000, 3072). Figure 4 we provide the training objective and the test accuracy of each approach with respect the number of epochs. Here, we observe that the optimization on the convex formulation achieves lower training objective and higher test accuracy compared to the classical optimization the non-convex problem.
A.2 CONSTRUCTING HYPERPLANE ARRANGEMENTS IN POLYNOMIAL TIME
In this section, we discuss the number of distinct hyperplane arrangements, i.e., P. and present algorithm that enumerates all the distinct arrangements in polynomial time.
We first consider the number of all distinct sign patterns sign(Xw) for all w Rdd This number corresponds to the number of regions in a partition of IRd by hyperplanes passing through the origin,
12

---

Published as a conference paper at ICLR 2021
10'
Objectiv Valuo
10
Conver opt. val.
Objeciive
Objecttve
Non comnex fees vol.
10
10
10
10
10
10"
Timajs)
Timets)
Time(s)
(a) Independent realizations
(b) Independent rcalizations with
(c) Independent realizations with 15
with
Figure 3: Training cost of two-layer CNN (with average pooling) trained with SGD (5 initialization trials) synthetic dataset (n 6, d 15, h 10, stride = 5), where the green line with marker represents the objective value obtained by the proposed convex program in equation and the red line with a marker represents the non-convex objective value in equation of feasible network with the weights found by the convex program. Here, we use markers to denote the total computation time of the convex optimization solver.
0.9
100
SGD
Convex
Objective Value
Test Accuracy
0.7
10-1
0.6
SGD
Convex
0.5
10
20
30
40
50
10
20
30
40
50
Epochs
Epochs
(a) Objective value
(b) Test accuracy
Figure 4: Evaluation of two-layer CNNs trained with SGD on full CIFAR- (n 10000, 3072,
50, h 12, stride
4).
and are perpendicular to the rows of X. Here, one can replace the dimensionality d with the rank of the data matrix X, ie.. denoted as r, without loss of generality. Let us first introduce the Singular Value Decomposition of X in compact form X UEV? where U Raxr, Σ E R and E Re Then, for given vector w E Rdd Xw = Uw', where w' ΣVT w, w' E R.. Hence, the number of distinct sign patterns (ggnXw) for all possible w Rd is equal the number of sign patterns sign( Uw') for all possible w/ E RT.
Consider arrangement of hyperplanes in RT, where n 2 r. Let us denote the number of regions in this arrangement by Po.r. In Ojha (2000); Cover 1965). it is shown that this number satisfies
Σ n-1) ))
Per $
For hyperplanes in general position, the above inequality is in fact an equality. In Edelsbrunner et al. (1986), the authors present algorithm that enumerates all possible hyperplane arrangements ((n') time, which can be used to construct the data for the convex programs we present throughout the paper.
13

---

Published as a conference paper at ICLR 2021
A.3 EQUIVALENCE THE & PENALIZED OBJECTIVES
In this section, we prove the equivalence between the original problems with & regularization and their & penalized versions. We also note that similar equivalence results were also presented in
Savarese et al. (2019) Neyshabur et al. (2014); Ergen & Pilanci (2019 2020c d). We start with the
equivalence between equation and equation 2
Lemma A.1. The following two problems are equivalent:
K
m
min [
(xuu)) wj-3
+ 2 j=1
(1 | + wf)
2
m u Wi y
m
min (u 1 uy K.
+ 8
w |||
j=1
Proof of Lemma A.7 Then, the output becomes
We rescale the parameters as üj Uy and új wy/Tj, ,, for any 75 0.
M
m
m
ΣΣ
(x,
Σ
Σ (
W
%
which proves that the scaling does not change the network output. In addition to this, we have the following basic inequality
1 Σ
m
11 +
w
N
Σ [1yy] f=1
||
12),
1=1
is used. Since the scaling operation does not change the right-hand side of the inequality, we can set Juyllz = 1, Vj. Therefore, the right-hand side becomes ||w|11-
where the equality is achieved with the scaling choice % =
|
Now, let us consider a modified version of the problem, where the unit norm equality constraint relaxed ||uz|l2 < Let also assume that for certain index wy # 0 as an optimal solution. This shows that the unit norm inequality constraint not active for uy, and hence removing the constraint for u, will not change the optimal solution. However, when we remove the constraint, ||u ||2 + reduces the objective value since it yields wy = 0. Therefore, we have contradiction, which proves that all the constraints that correspond to a nonzero w, must be active for an optimal solution. This also shows that replacing ||ulla = 1 with ||u ll S 1 does not change the solution the problem.
obtain ||uر||2 < 1 with
Next, prove the equivalence between equation g for L 3 and equation 30 Lemma A.2. The following two problems are equivalent:
m XUU W11) W2j - y
m
min (ng.wig.toss uy EB.
+
(1 + wzz))
1
2
j=1
2
min (u, (15.Wi;-W2. 1 Wy EB.VV
(XU,W15)4
W25
+ w2ll1
2
Proof of Lemma 4.2 We rescale the parameters as W1j Wi and W2j ww2///5 for any
Vi > 0. Then, the output becomes
W2j xU, = (UU,Wiy
XUU, Wzj-
j=1
14

---

Published as a conference paper at ICLR 2021
which proves that the scaling does not change the network output. In addition to this, have the following basic inequality
1 2
W1y 12 + w3z 2 ==1
(1wiill2 /w2y]):
1=1
is used. Since the scaling operation does not change the right-hand side of the inequality, we can set [|W1yll = 1, Vj. Therefore, the right-hand side becomes w2ll1. The rest of the proof directly follows from the proof of Lemma
where the equality is achieved with the scaling choice 7/ = [|was
|era
A.
A.4 TWO-LAYER LINEAR CNNS
We now consider two-layer linear CNNs, for which the training problem is
3
min {uy w. f=1
X Wyk
||w,,
(20)
2
k= j=1
Theorem A.1. (Pilanci & Ergen 2020) The equivalent convex program for equation 20 is
min [m ERA
Σ X y + 1[l1........ .i...... 2x
(21)
2
Proof of Theorem A.1
We first apply a rescaling (as in Lemma A.I to the primal problem in
equation 20 as follows
min [u, w, w 2 8,EB,
X
3
wwll2.
Then, taking the dual with respect to the output layer weights wy yields
max l|
y
+ 1lyl 2
s.t. max
Σ |
(vTXxu)² S
(22)
uEB
Let us then reparameterize the problem above follows
flv - y1 + 2 |rl s.t. max (M) S 3, M V Xfvv,,
max M.v
where maz (M) represent the maximum singular value of M. Then the Lagrangian is as follows
1 - - ||v -11 +
1
2 y 112 + x Omax (M)) + trace (Z"M) trace T v x
2
1 || y
+ 2 | 1 + x 0max (M) + trace Z M)
V
2
where A 2 0. Then maximizing over M and v yields the following dual form
K
1
min {xa 15 24
Σ
X
y
+ 11 *x]],..
2
1=1
where |||
xx] 1|l. = |Z]]. Σ; (Z) the & norm of singular values, i... nuclear norm
(Recht et al. 2010).
15

---

Published as a conference paper at ICLR 2021
The regularized training problem for two-layer circular CNNs follows
m Σ
XU,W, w y m
min { Fiml
(1
w3)12)
(23)
j=1
where U, E Raxd is circulant matrix generated by circular shift modulo d using uj IR
Theorem A.2. PPilanci & Ergen 2020)
The equivalent convex program for equation 23 is
112
1
min *E 2
Xz x
1z/1,.
(24)
vd
where X = XF and F E Cdxd is the DFT matrix.
Proof of Theorem A.2
We first apply a rescaling (as in Lemma
A.1
to the primal problem in
equation 23 as follows
min w i-m uy
Σ XU,W;
+
w ll
2
and then taking the dual with respect to the output layer weights wy yields
max 2 y11 +
1 s.t. max DED
XFDF"
||2 S 8,
where D (D D S d}. the problem above, we use the eigenvalue decomposition U FDF where E Cdxd is the DFT matrix and E Cd is a diagonal matrix defined as D = diag( (VdFu). We also note that the unit norm constraint in the primal problem, i.e., U, B2, equivalent to D, E D since D, = diag( (lag(VdFg) /Fu,) and [D, = d'|u, l| due the properties of circulant matrices.
Now let us first define a variable change as x XF, Then, the problem above can be equivalently written
y 11 s.t. max |v XD l - 3.
DED
Since D is a diagonal matrix with norm constraint on its diagonal entries, for an arbitrary vector S E C", we have
ss D'l2
D
<
Smaa
Σ
Disl 8 8man Vd,
where Smaz == max; |sg]. If we denote the maximum index as imaz == arg max, [8:1, then the upper-bound is achieved when
Va i
D
0, otherwise
Using this observation, the problem above can be further simplified as
8 Vd
y11 + 111
|| X T
Then, taking the dual of this problem gives the following
min = 2
Xz
1/- +
8 vd
|2]|
16

---

Published as a conference paper at ICLR 2021
A.5 EXTENSIONS VECTOR OUTPUTS
Here, we present the extensions of our approach to vector output. To keep the notation and presentation simple, consider the vector output version of the two-layer linear CNN model in Section A.4 The training problem is as follows
1
B
min
X.u,w - Y
|
2
w
w
(uy. 1-1
2
k=
The corresponding dual problem is given by
2 -|I Y
S.L. IYI
IVT S.
max
u
The maximizers of the dual are the maximal eigenvectors of Σ filters.
X VVVVTX, Xx. which are optimal
We now focus on the dual constraint as Proof of Theorem
K
K
max uEB2
max EB
sagk
V
max X
8k V X ug.
EB₁
A=1
k=
k=
K
K (V, V
max G BEB
8k (V,
max ||aall San sEB,
Then, the rest of the derivations directly follow Section A.4
A.6 EXTENSIONS TO ARBITRARY CONVEX LOSS FUNCTIONS
In this section, first show the procedure to create optimal standard CNN architecture using the optimal weights provided by the convex program in. Then, we extend our derivations to arbitrary convex loss functions.
In order to keep our derivations simple and clear, we use the regularized two-layer architecture in For given convex loss function E(:,y) y), the regularized training problem be stated as
equation 1 follows
K ΣΣ
3
Pi
min Mu
X ( W
| 12 +w))
(25)
2
Ø=1 1=
j=1
Then, the corresponding finite dimensional convex equivalent
Peone
Peonv
min (Paans C. .Y8
(EL
Σ
D(S Xu(c -.),y +
(/cill2 + (l(/122)
(26)
s.t. ) 1,),) 2 0, (2D(S)) 1,, 20, Vi,k.
We now define m = EPeae |||c + 0] EPeonv [[le ||2 # 0). where {c, 1 optimal weights in equation 26
Peone are the
Theorem A.3. The convex program equation 26 and the non-convex problem equation 25 where
m 2 m has identical optimal values. Moreover, an optimal solution to equation can be constructed from optimal solution to equation 26 as follows
cf'
VileTlla 122
if ||" l|2 > 0
Vil T
c
-Viclll
if |ct > 0,
Vilctlla
Pawn the optimal solutions equation where (c, C Sim
26
17

---

Published as a conference paper at ICLR 2021
We first note that there will be m vectors {c/ ct). Constructing {u), 2 11 stated in the theorem, and plugging in the non-convex objective equation 25 obtain the value
Proof of Theorem A.3
K
P Prans
c
P SE
Σ
Σ
+
Vilc;
+
V ||,
ll2
2
ll
12
j=1 km
i=
#0
Peony
2
8
c
V || 1|
+
cg
ll
which is identical to the objective value of the convex program equation 26
Since the value of the convex program is equal the value of it's dual d" the dual, we conclude that pi dj, which is equal to the value of the convex program equation 26 achieveed by the prescribed parameters.
We also show that our dual characterization holds for arbitrary convex loss functions
K X
min (ug.nn Fim Uy EB2.Vj
Σ 1=1
B1 B||w||i,
(27)
where y(:,) is convex loss function.
Theorem A.4. The dual of equation 27 is given by
- Es (v) s.t.
Σ (X,+)))++ k=1
S,B, Vu E B2.
where En is the Fenchel conjugate function defined
E' (v) = max zT f(z,y).
Proof of Theorem A.4
The proof follows from classical Fenchel duality (Boyd & Vandenberghe We first describe equation 27 an equivalent form follows
2004
min tu uy EB.
((z,)) y) + B1 w s.t. z
(xuj)+Wjs.
==
Then the dual function
K (xuu))+ + 3/ll
g(v)=
min (ny.ng) 1 (z, - v
k=1
Therefore, using the classical Fenchel duality (Boyd & Vandenberghe 2004) yields the claimed dual form.
A.7 STRONG DUALITY RESULTS
Proposition A.I. Given m strong duality holds for equation Le., p di.
We first review the basic properties of infinite size neural networks and introduce technical details to derive the dual of equation 3 We refer the reader to Rosset et al. (007):: Bach (2017) for further details. Let us first consider measurable input space X' with set of continuous basis functions (i.e., neurons or filters in our context) Vuu : X + R, which are parameterized by u E By. Next, we real-valued Radon measures with the uniform norms (Rudin) 1964). Let us consider signed Radon measure denoted as p. Now, we can use to formulate an infinite size neural network as [(x) SuEs, Va (u)) where X is the input. The norm for μ is usually defined as its
18

---

Published as a conference paper at ICLR 2021
total variation norm, which is the supremum of Sues, ((u)dp(u) over all continuous functions g(u) that satisfy Ig(u)] I 1. Now, we consider the case where the basis functions are ReLUs, i.c., d (x"u)++ Then, the output of network with finitely many neurons, say neurons, can be written
f(x) = Σ ==1
Buy Wj
which can be obtained by selecting f as weighted sum of Dirac delta functions, i.e., μ Dラ=1 wyz(u uz). In this case, the total variation norm, denoted || corresponds to the norm |w|l.-
Now, we ready to derive the dual of equation 3 which can be stated as follows (see Section 8.6 of Goberna López-Cerdie (1998) and Section of Shapiro 2009) for further details)
di S P1.00 min
(xu) du(u) - y + BllITTVV.
(28)
2
DEB k=1
Although equation 28 involves an infinite dimensional integral form, by Caratheodory's theorem, we know that the integral can be represented as finite summation, to be more precise, summation of at most n + 1 Dirac delta functions (Rosset et al. 2007). we denote the number of Dirac delta functions m where m I + 1, then we have
P1,00
min (uy,ey 1m 2
(Xuu)) Wj -y + B w/w
1=
u, B)
Pi
provided that m 2 m² We now need to show that strong duality holds, i.e., př = d;
We first note that the semi-infinite problem equation is convex. Then, we prove that the optimal
value is finite. Since / > 0. we know that v = 0 is strictly feasible, and achieves O objective value.
Moreover, since - lly v12 S O, the optimal objective value pi is finite. Therefore, by Theorem 2.2 of Shapiro (209), strong duality holds, i.e., Pi di provided that the solution set of equation 3 is nonempty and bounded. We also note that the solution set of equation is the Euclidean projection of y onto convex, closed and bounded set since (X+ can be expressed as the union of finitely many convex closed and bounded sets.
A.8 PROOF OF THEOREM 2.2
The proof follows the proof of Proposition A.I The dual of equation 6 follows
1
2 + 311 ITV,
di S Pl, min 2
maxpool (((Xau))) du(u) y
JuE,,
which has the following finite equivalent
2
m
P1.00
min {u,.0s we pmm u, VJ
Σ
maxpool (((X,;)),,Ki)) wy y + 3 w//l
pi
provided that m 2 m.. We now need to show that strong duality holds, i.e., pl = dj-
Since maxpool(-) can be expressed as the union of finitely many convex, closed and bounded sets, the of the strong duality results directly follow from the proof of Proposition A.
We now focus on the single-sided dual constraint
max v" maxxpoll (oxxpoo(((Xxuu,,,))) 4 S 3, ue8,
19

---

Published as a conference paper at ICLR 2021
which can be written
( (2D(5*) I,, X 2 0, vk,
max uEB st
S'n
K Vj D(S D u,
Σ D(S*) = I,-
k=1
We again enumerate all hyperplane arrangements and index them in arbitrary order, where define the overall set as SK { S() Poone = |Sk] Then, following the same steps in
S
S, Yk, E D(S L, vi} and
13
17
gives the following convex problem
Prana
Prona
min
Σ
D(S X (W, wi)
y
+
(29)
ERA
s.t. (S) - I,)x 2 2, (2D(S)) -111-,)) L,) 2 0, Vi
X D(S D(S 2 D(S Vi,j,
now note that there will be mn* pairs {we w Then, we can construct set of weights Im= {uj, w 1j=1 as defined in the theorem and evaluate the non-convex objective in equation using these weights as follows
pi
maxpool (((Xau)), wz y
II 112
2
la
1=1, #0
Peune
+
+
w/
l|
(=1, #00
which has the same objective value with equation 29 program, we have pi = di. which is equal to the value of the convex program equation 29 achieved by the prescribed parameters above.
Since strong duality holds for the convex
A.9 PROOF OF THEOREM 3.1
By using rescaling for each Wij and w2j, equation can be equivalently stated as
1
min p$ (fuy He 2 "wwy. 1mm Wi ElG,, bl.
X
U
W1j
W22
+ 3 W2ll1-
(30)
2
h=1
Let us denote the eigenvalue decomposition of Uty as U. FD, where F E Edxd is the DFT matrix and Dıj Caxd a diagonal matrix. Then, we again take the dual with respect Wa and change the order of min-max as follows
1-2
p 2 di max
| 2
y12
1y S.L. max DI, ED, WiyEBs
VT
XF
D F F"
S 3, Vj.
(31)
where Dz := (Di..... DL-2 Di Cdxd VI [L - 2]: I1 D F
< d Below we
prove that strong duality holds for equation
In order to obtain the dual of the semi-infinie problem in equation 31 we again take dual with respect
v (see Appendix A.7 and Goberna & López-Cerdá (1998); Shapiro 20099 for further details), which yields
1
d' S P2.00 min
XF [=1
w1 D Ww1
du(OL) y
+ Bllaalzv
Ar E02
20

---

Published as a conference paper at ICLR 2021
where Ø ..D.....DL--.. w1) Dj E DL, 1A
[L -12,:: w/:w1 B2).
Then, selecting
a = 2j=1 W2) 8 01z), where m S n + 1, gives
m
1.-2
12,00
((Dg) i
min
2
Σ
XF
I
Dig DiS Wij
W2j
+
w2ll
1=1
2
22
provided that m m" holds. Then, the rest of the strong duality proof directly follows from Proof of Proposition A.I
We now focus the single-sided dual constraint
L-2
max V D.EDr. W1EB2
X
II 333,
which can be written as
1-2
L-2
max max D(S)) II D.w s.t. (2D(5) - I,) D:w 2
II
(32)
SC D.ED2 SES w1EB2
Since the inner maximization is convex (after a variable change as q -= D, and there exists strictly feasible solution for fixed D(S) matrix, equation 32 can also be written as
max min max DzD(S,) a² (2D(S.) I, X II D.w SCin 220 DrED1 SES Wi EB
I
max min
I D(S)X a (2D((S) I,,) I, oood
SCIn SES
We now enumerate all hyperplane arrangements and index them in an arbitrary order, which are denoted as D(S:), where [Prcono]. Then, we have
equation 32
Vi E [Pocone]; min | | D(S) T (2D(S.) I, ) ao S B
a20
Vi [ [ccooee]. Ea, 2 s.t. V D(S) a (2D(S)) I, X 1lod < 8.
We now use the same approach for the two-sided constraint in equation 31 to represent equation finite dimensional convex problem follows
31
max 2 y12 1yl1 22
(33)
s.t. D (S.)
I, II (2
1 + a; (2D(S.) I, X ae -2z S B, Vi.
We note that the above problem is convex and strictly feasible for v = =a; = 0. Therefore, equation 33 can be written as
Peconu
min
max
2 l/
y112 + 11yl2 + Σ
A (8
I, |
1l0 L-2
X.
a2,0/20
Pecone
X
a (D( - I, X
/ |
(34)
Next, we introduce new variables Zi, 2/4 E Cd to represent equation 34 as
min 200
max
min Z.EB: EB;
1 ||v y113
1yl12
Pecanv
X (B+d'²2 (VD(S.)*+a((2DD (
I,)x) 2:)
2
2
as
Pecenv
X ( 2ي²
(-v (2D(S)) I, 1,)))=1
(35)
21

---

Published as a conference paper at ICLR 2021
We note that the objective is concave in v, Qt, a and convex in 2, z Moreover the set B1 is convex and compact. We recall Sion's 's minimax theorem (Sion 1958 for the inner max-min problem and express the strong dual of the problem equation 35 as
Peconv
1 -211 y112 lyllă
1
d (B+ (a (2D(S.) I,)X) 2i
min min AGA200 eR, EBI 2, EB
v 0/22
Penanu
2-2 X (B+d
(-v'DSS)XX (2D(S)) - I, | xz
(36)
Now, we can compute the maximum with respect to v, at, a analytically to obtain the following problem
P Preanu
min min A,, 2,88 2iEB,
d D(S - X,2 + B
(1+
(37)
2
s.t. (S, - Xz, 0, (2D - I,, Xz, 2 V.
Now we apply a change of variables and define c; = _²² X;Z; and ci = - X24. Thus, we obtain
Peconu
Peconc
min o
Σ
D(S))X c.) - y
(I|c:]l ||c((1)
(38)
d
s.t. (2D - Xc; 2 0, (2D(S)) I,, Ix,cc 2 0, vi,
where we eliminate the variables A, X/ since X = /d= and X || /d are feasible and optimal.
Optimal weight construction for equation g
Given the optimal weights for the convex program in equation 38 i.e. denoted as {ct cf Jizm" we use the following relation
|c
|c -²²
| |l -
Xc Xdiag
diag
e
V
||
V
d
L-2
|c3|
c
|
-
II
diag
diag
||
1l
where Φ, is defined such that c₁ = diag (lc?l) cdd: Thus. we can directly set the parameters as follows
lcil ||c
(v
|cjl dh
| 1 d
D = diag
d V
wi, = diag
wag =
||
1
which can be equivalently written as
c |c VIclh
lo d
|| d
U = Fdiag
d
FH
wii
=
V
w
exactly match with the problem formulation in equation 8 I = 2 Ii therefore, this set of parameters is feasible for equation 8 Now, we prove the optimality by showing that these parameters have the same regularization cost with the convex program in equation 38 as follows
We first note that ||
U
(IWil1
+
| |1-
The same steps can also be applied to c," Then, the rest of the proof directly follows from The- Therefore, we prove that a set of optimal layer weights for equation g. denoted as
orem 2.1
{[U Gjtt wiys why 1m 1= can be obtained from the optimal solution to equation 38 denoted as
{c) c 1
Poonv
22

---

Published as a conference paper at ICLR 2021
A.10 PROOF OF THEOREM 4.1
We now provide the proof for the three-layer CNN architecture with two ReLU layers, which has the following primal optimization problem
3
Pg
min WL. 2
Σ
Wish
W21
(Iw1 w221)
2
B,EB2
+
Then, the dual is
Ps z d3
max
1|v y112 2 ~11x112
s.t.
max u. w. EB2
T Σ
(Xxu) Wik
SB (39)
Dual of equation 39
2
1
I Juwweess
d3 S P3,00 min
Σ
( Wik
dp(u, w1) y + BlllllV,
(40)
where strong duality holds, i.c., dz = P3,00, by Proof Proposition A.1 follows
Then, the finite equivalent
P3,00 P3
min uy Way EB
Σ
(Xau)) wish
w2) y
+ B B//wel
W2
+
2
now focus on a single-sided dual constraint
max VT E.W,EB,
Σ (Xau) wik
$
(41)
which can be written as
v D(2))
D(S Xauwne s.t. (2D(S²) I..) Σ
D(Ss)xxuury 20, (2D( I. 1.)Xaury 2
max
52. Cin] W.W
So $p.$t
max I, ((E1
max
max
max S
V(())
I.D(St
(42)
82.8 [[n] CB Ilq
$2.5f
s.t. (2D(Ss) I.) Σ I 20, (2D(S)) I.. X 2 0.
where we introduce the notation In E {+1} to enumerate all possible sign patterns for wik- Since the inner maximization convex and there exists strictly feasible solution for fixed D(S)). D(S2). and Za equation 42 can also be written as
Σ
D'D + aT L.)X.q (2D(() (.JD((t)xig))
max
max
min max
max
Sa [(n] 92:720 WIEBS IIE 125 1=1 [=]
82.8
K
Σ
TD(S + + (FD())())) I.)X,q. +ID L.)D(()) |201
min
I, (+1) st 72
BB,
k
K
J D +ona-aad (2D())) I.)X IxT ( - -..). (2)
max
min
Σ
E(#1)
S(Cn] 720 8f
23

---

Published as a conference paper at ICLR 2021
Then, have equation 4T
31 min 067720
Σ
v
((S))) + (2D(()) - 1,)x + TINEY (2D(S)) I. D.) 5g
K
J, 30isks Yy 2 s.t.
Σ
v' (od I,)xxq. Saaqu+Iupe (2(()) ( ss.
L.D(S))Xx
We now use the same approach for the two-sided constraint as follows
max
- y 11 1
(43)
P1jao0,6220 20 1g.0
s.t.
Σ
D(S X + (2D(())) I,)xxq + (2n7) - D())
$ SB,
Σ - D(S)) + (2D(s)) - 1..)x.q + (2D -, D.) XA 1.)
S S Vi,j.
We note that the above problem is convex and strictly feasible for -iih = e'u Mi Therefore, Slater's conditions and consequently strong duality holds (Boyd Vandenberghe 2004 and equation
0.
43 can be written as
min Ag
108x V. 20
212
2 1
(44)
70
P
K
Asj
Σ
(2
+ I2 + I,
P2
K
Σ
v" (
Sk X + a (2D(
X, + Y - L,),(s))
Next, we introduce new variables Zijk, z'yz E R to represent equation 44 as
min
max
min
y |y
(45)
Ag 20
moalllaa laS =yge-lla laseige af EB2
a 20
B2
K D(S) T2 - I.)Xaq + (2nn7)((D(S2e)) L.)D(s))) Zigh
Xij
3 +
k=1
P3
K
3 +
(-v
X + (T I,)xaq + (2D2)() - I, D(),) ziip
i=1
A=1
Then, the strong dual of the problem equation 45
min Ai 20 mgsell Saipk
max
- y12 1 1y
(46)
1,,20
qu 41 EB2
K
Xij
3 +
(V"D(S) + (2D(() I,) + (2 (.) Xx)) wiga
i=1
k=1
I2
K
X
3+
D D + 22
I,)x + - I,, (s)) Aiuu
k=1
24

---

Published as a conference paper at ICLR 2021
Now, compute the maximum with respect v, aijk: Alyk Yeg, K/ analytically to obtain the following problem
min Nej Ag 20 and Aagallasgu
min
S
I D (( Xxx (NgziyA (1zZ(sE) y
(As X13)
2
s t lall Saipk 4i A.g.B
j=1
(47)
P K
s.t. (2D (25)) - I
20, (2D(S)) I,) 2 0, Vi, Ii
i=1 1=1
(2D(S2)) I,,)
L,,, 20, (2D(S)) I, X, 2 0, Vi,
Now we apply change of variables and define Ctyk- 2is and c'jj
Kigk Thus, obtain
P2
P
B
min cijt.Ciyk
Σ
IR D(S)) (cija - cijū)) -y
+
(I +CC,ll)
2
1=1
k=
1
P. K
s.t. (2D(S2)) - -I,)
D(j 20, (2D(S%) X4cijk 2 0, j.
1=1 1=1
(2D(S2)) -I,) Σ
Σ
Lyj Dij 20, (2D(S,,,), I, Xxc 2 V,
25


Reviews:
[{"review_id": "Zz8q4LhbbU9", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "[Summary] This paper focuses on training convolutional neural networks (CNNs) by using convex optimization techniques. By taking the dual of the nonconvex training problems, (and the dual of its dual), the main contribution of the paper is to show the strong duality between the convex problem and its original nonconvex training problems. This result has been proved for multi-layer CNNs with one ReLU layer and three-layer CNNs with two ReLU layers.\n\n[Pros] This paper presents interesting results on the convex equivalent formulation for the training problems in deep learning. This result could potentially lead to new algorithms for training the network. The convex formulation also reveals the hidden regularization property of the original nonconvex training problems, such as the group L_1 norm regularizer. \n\n[Cons] 1. This paper is an extension of previous work (Pilanci & Ergen, 2020) that provides an exact convex formulation for training two-layer fully connected ReLU networks. This paper extends this work to CNNs, multi-layers, but still has a very strong limitation on the number of ReLU layers: only one ReLU layer for multi-layer CNNs and two ReLU layers for a three-layer CNN. Also, it is not clear what are the technical difficulties in extending the previous results (Pilanci & Ergen, 2020) to this work. \n\n2. Since the modern neural network is often over-parameterized, which is also true in Theorem 2.1 as the number of filters $m$ needs to be relatively large compared to the number of data points, the nonconvex training problems can usually be solved to a global solution, either in practice or in theory under certain conditions. It's more interesting to see why the solution obtained has good generalization property, which is not discussed in this paper. \n\n3. This paper only uses toy examples in the experiments. For example, only n = 99 training samples are used in the MNIST experiments, which makes the results not that convincing. \n\nMinor comment: \n1. Adding the main idea in proving Theorem 2.1 (the strong duality) after Theorem 2.1 will be helpful for the reader to follow. Also, the authors could briefly mention why only taking the dual with respect to the output weights instead of all the network parameters in deriving eq. (3). This is different from the standard approach to computing the dual problem.\n \n2. The notatin is very complicated, making the main results like Theorem 2.1 difficult to follow. For example, $w_i$ are used as the optimization variables in the convex problem (4), while $w$ is also used as an optimization variable in the original problem (1). Also, what are $j_{1i}$ and $j_{2i}$ in Theorem 2.1? Why only $m^*$ filters can be constructed from the solution of the convex problems in Theorem 2.1? \n\n3. typo in the first sentence right after Theorem 4.1: gIt\n\n\n%%%%%%%%%%%% After rebuttal %%%%%%%%%%%%%%%%%%%%%%%%%%%%\nI appreciate the great efforts the authors have made in responding to the comments. Most of my comments have been well addressed, so I have increased my score. Nevertheless, another important question is in the over-parameterization setting, why the solution obtained by the convex approach has good generalization property. This question is not addressed in the rebuttal. Probably it is too much to have this in one paper and can be an interesting question for future work. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "O39z7ZwcEz_", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nThe paper considers several types of CNN and proposes convex reformulations for non-convex problems of training these networks. As a result a polynomial complexity is shown for the training problem. The results are also interpreted as implicit regularization induced by the choice of the architecture. Finally, numerical experiments are made to support the theoretical findings and show that in the predicted regime, SGD for the original problem converges to the global minimizer given by the convex reformulation.\n\nEvaluation:\nOn the one hand it is good to know that the vast list of the analyzed architectures are amenable to convex reformulations and polynomial complexity of their training. On the other hand, the main techniques to obtain these results were developed in (Pilanci & Ergen, 2020), which is already published at ICML 2020 https://proceedings.icml.cc/static/paper_files/icml/2020/2660-Paper.pdf. I believe that the results are of interest also to the ICLR community, so I'm leaning more to the accept side.\n\nPros:\n1. Good to know that many CNN architectures can be trained in a polynomial time and which implicit regularization they introduce. \n2. In comparison to (Pilanci & Ergen, 2020) the exponent of the polynomial in the complexity bound could be much smaller than the dimension. In this sense, as far as I understood, the convolution operation helps to get better complexity estimate.\n\nCons:\n1. The proof of the main result (Theorem 2.1) looks as a verbatim of proof of the main result (Theorem 1) of (Pilanci & Ergen, 2020). The only difference is that now there are may X_k's and a summation over k.\n2. The proofs of the other results are not completely clear.\na. Proof of Theorem A.1. Why the first reparametrization is equivalent? Why strong duality holds?\nb. Proof of Theorem A.2 also is lacking details.\nc. Similarly for Appendix A.5.\nd. Proof of Theorem A.3. First line. Why are there $m^*$ pairs of such vectors?\n3. The clarity could be improved\na. What is precisely meant by \"circulant matrix generated by the elements of u\"?\nb. In Sect. 1.2 what is \"stride\"?\nc. In Theorem 4.1 what are \"sign patterns\"?\nd. It seems that in (13) somewhere $\\beta$ is missing.\ne. First paragraph of Appendix A.6, there is an undefined reference.\n\nMinor comments:\n1. Extra \"g\" in the first line after Theorem 4.1.\n2. In (17) there is an extra summation over $k$ in the $\\lambda$-term.\n3. There should be comma between 6 and 7 in the first line of Sect. 6.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "FZQ9TNuGYAh", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper studies the non-convex optimization problem of training CNNs with ReLU activations under different choices for the CNN architecture, and shows how these can be framed as convex problems with a poly time complexity w.r.t. relevant variables. The derived convex problems provide valuable insights on how the CNN architecture induces different weight regularizers by giving them in explicit form -- these show a rich connection between the architecture and regularizer.\n\nI believe the contributions are significant and two-fold. First, the convex problems are solvable with reasonable time complexities (polynomial in all relevant parameters) even for networks with two non-linear layers -- this is in contrast with the cost of optimizing ReLU fully-connected networks, where an exponential dependency on the input dimension if the data matrix is full rank, hence global optimization of CNNs seem more likely to have practical implications than that of fully-connected networks. The condition for strong duality to hold seems quite restrictive, though, and further discussion on it would be valuable.\n\nSecond, it further expands what is currently known about how network architectures induce different regularizers on the parameters, showing that precise characterizations for CNNs with ReLU activations. The induced regularizers have a rich variety, including \\ell_1, \\ell_2, nuclear and Frobenius norms.\n\nThe fact that the theoretical results hold for classification losses is also valuable, and the experimental results are very appreciated. I think the CIFAR experiments in Appendix A.2 are more interesting and relevant than the MNIST one in the main body (esp. considering the time cost of convex opt. vs SGD), and swapping them would make Section 6 more appealing -- alternatively, shrinking Section 5 could possibly open up space to have Figure 4 in the main body of the paper.\n\nAlso, additional discussion on the induced regularization would be fruitful in making the paper more clear: in prior work that analyzes linear deep networks, the induced penalties are on the parameters of the induced linear predictor, and the same cannot be said for CNNs with ReLU activations and the induced penalties found here due to the binary diagonal matrices D. Making this distinction (which is mostly technical) more explicit would help readers in understanding how the derived penalties relate to ones given in prior work.\n\nMinor comments:\n- typo in beginning of last paragraph of Section 4 \"gIt\"\n- missing mathbb/mathbbm/mathds/etc for indicator functions, towards end of Theorem 2.1's statement\n- the equations would be easier to parse if the output weights were placed before the ReLU, e.g. w_j (X_k u_j)_+ instead of (X_k u_j)_+ w_j in Eq 1\n- what are the sign patterns I_ijk in Theorem 4.1?\n- Fig 1 and 2 seem to have wrong aspect ratios (horizontal stretching) and too much negative vspacing in their captions: Fig 2 occludes overlaps the caption of Fig 1 and there is almost no space between the caption of Fig 2 and Section 6\n- inconsistent reference style: some entries in the bibliography have editors while other don't, same for doi etc\n\nOverall I find the contributions to be significant and suggest acceptance.\n\n---\n\nI thank the authors for the response, which addresses my questions. I still believe that the paper provides valuable contributions and insights.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper introduces convex reformulations of problems arising in the training of two and three layer convolutional neural networks with ReLU activations. These formulations allow shallow CNNs to be training in time polynomial in the number of data samples, neurons and data dimension (albeit exponential in filter lengths). These problems are regularized in different ways (L2 regularization for two layers, L1 regularization for three layers), providing new insights into the connection between architectural choices and regularization. The paper also provides experiments showing convex training of neural networks on small datasets.  

Pros and cons:

[+] The theoretical results show that globally optimal training of shallow CNNs can be achieved in time fully polynomial, i.e., polynomial in the number of data samples, neurons and data dimension. This is significant theoretical progress, since the corresponding results for fully connected neural networks require time exponential in the rank of the data matrix. There is, however, an exponential dependence on the filter length (or the rank of the patch matrix). In particular, the computational complexity is proportional to $(nK/r_c)^{3r_c}$, where $n$ is the number of data points. While CNNs do use relatively small filters, this becomes prohibitive even when $r_c$ is a moderate constant. E.g., the experiments use filters of length $3$. Here, the comments of the reviewers about generalization may be appropriate; perhaps experiments that evaluate the performance of these networks in terms of generalization may show the disadvantages of using very small filters. 

[+] The work provides interesting and rigorous insights into the relationship between architecture and implicit regularization, with different network architectures leading to different regularizers (L1, L2, nuclear). Developing these insights for deeper architectures could lead to important insights even in situations where the convex relaxation is challenging to solve efficiently. 

[+] Although the theoretical results require overparameterization, in the sense that strong duality holds when the number of filters is large relative to the number of data points, the authors convincingly argue that this degree of overparameterization is commensurate with, or even smaller than, the degree of overparameterization present in many experimental/theoretical works in the literature. 

[+/-] The paper is mathematically precise and is written in a rigorous fashion, but is occasionally heavy on notation. The paper could be more impactful on empirical work on neural networks if it could provide more intuition about how the various forms of equivalent regularization arise from different architectures. 

All three reviewers express appreciation for the paper’s fresh insights into global optimization of shallow CNNs and the connection between architectural choices and regularization. The AC recommends acceptance. 

Decision: Accept (Spotlight)