Demystifying Batch Normalization in ReLU Networks: Equivalent Convex Optimization Models and Implicit Regularization
Authors: Tolga Ergen
Arda Sahiner
Batu Ozturkler
John M. Pauly
Morteza Mardani
Mert Pilanci
Venue: ICLR 2022 Poster (2022)
Keywords: batch normalization
ReLU networks
deep networks
convex optimization
whitening
implicit regularization
algorithmic bias

Abstract: Batch Normalization (BN) is a commonly used technique to accelerate and stabilize training of deep neural networks. Despite its empirical success, a full theoretical understanding of BN is yet to be developed. In this work, we analyze BN through the lens of convex optimization. We introduce an analytic framework based on convex duality to obtain exact convex representations of weight-decay regularized ReLU networks with BN, which can be trained in polynomial-time. Our analyses also show that optimal layer weights can be obtained as simple closed-form formulas in the high-dimensional and/or overparameterized regimes. Furthermore, we find that Gradient Descent provides an algorithmic bias effect on the standard non-convex BN network, and we design an approach to explicitly encode this implicit regularization into the convex objective. Experiments with CIFAR image classification highlight the effectiveness of this explicit regularization for mimicking and substantially improving the performance of standard BN networks. 

Published as a conference paper at ICLR 2022
DEMYSTIFYING BATCH NORMALIZATION IN RELU NETWORKS: EQUIVALENT CONVEX OPTIMIZATION MODELS AND IMPLICIT REGULARIZATION
Tolga Ergen; Arda Sahiner; Batu Ozturkler, John Pauly, Morteza Mardani & Mert Pilanci
Department of Electrical Engineering
Stanford University Stanford, CA 94305, USA (ergen, sehiner, ozt, o
morteza, pilanci l /estanford.edu
ABSTRACT
Batch Normalization (BN) is commonly used technique to accelerate and stabilize training of deep neural networks. Despite its empirical success, a full theoretical understanding of BN is yet to be developed. In this work, we analyze BN through the lens of convex optimization. We introduce an analytic framework based on weight-decay regularized
convex duality to obtain exact convex representations ReLU networks with BN, which can be trained in polynomial-tmee Our analyses also show that optimal layer weights can be obtained as simple closed-form for- mulas in the nigh-dimensional and/or overparameterized regimes. Furthermore, we find that Gradient Descent provides an algorithmic bias effect on the stan- dard non-convex BN network, and we design approach explicitly encode this implicit regularization into the convex objective. Experiments with CIFAR image classification highlight the effectiveness of this explicit regularization for mimicking and substantially improving the performance of standard BN networks.
INTRODUCTION
Deep neural networks have achieved dramatic progress the past decade. This dramatic progress largely hinged on improvements in terms of optimization techniques. One of the most prominent recent optimization techniques is Batch Normalization (BN) (Toffe Szegedy 2015). BN is an operation that is introduced in between layers to normalize the output and it has been shown to be extremely effective in stabilizing and accelerating training of deep neural networks. Hence, it became standard in state-of-the-ar architectures, c.g., ResNets (He et al. 2016). Despite its empirical success, still theoretically elusive why BN is extremely effective for training deep neural networks. Therefore, investigate the mechanisms behind the success of BN through convex duality.
1.1 RELATED WORK
Batch Normalization: One line of research has focused on alternatives to BN, such as Layer Normalization (Ba et (016)) Instance Normalization (Ulyanov et al.. (016)). Weight Normalization (Salimans & Kingma 2016), and Group Normalization (Wu & He (011)). Although these techniques achieved performance competitive with BN, they do not provide any theoretical insight about its empirical success.
Another line of research studied the effects of BN on neural network training and identified several benefits. For example, Im et al.] (2016) showed that training deep networks with BN reduces dependence on the parameter initialization. Wei et al. (2019) analyzed BN via mean-field theory to quantify its impact the geometry of the optimization landscape. They reported that BN flattens the optimization landscape so that it enables the use of larger learning rates. In addition, Bjorck et al. (2018): Santurkar al. (2018): Arora al. 2018) showed that networks trained with BN achieve
Equual Contribution

---

Published as a conference paper at ICLR 2022
faster convergence and generalize better. Furthermore, Daneshmand et al. (2020) proved that BN
avoids rank collapse so that gradient- based algorithms, e.g., Stochastic Gradient Descent (SGD), able to effectively train deep networks. Even though these studies are important to understand the benefits of BN, they fail to provide a theoretically complete characterization for training deep networks with BN.
Convex Neural Networks: Recently, a series of papers (Pilanci & Ergen 2020] Ergen & Pilanci 2020: 2 by Sahiner et al., 22221a b) studied ReLU networks through the lens of convex opti- mization theory. Particularly, Pilanci & Ergen (2020) introduced exact convex representations for two-layer ReLU networks, which can be trained polynomial
via standard convex solvers. However, this work is restricted to two-layer fully connected networks with scalar outputs. Later on, Ergen & Pilanci (202Ta) first extended this approach to two-layer scalar output Convolutional Neural Networks (CNNs) with average and max pooling and provided further improvements on the training complexity. These results were extended to two-layer fully convolutional networks and two-layer networks with vector outputs (Sahiner et al. 2021a). However, these convex approaches are restricted to two-layer ReLU networks without BN, thus, do not reflect the exact training framework in practice, i.., regularized deep ReLU networks with BN.
1.2 OUR CONTRIBUTIONS
We introduce an exact convex framework to explicitly characterize optimal solutions to ReLU network training problems with weight-decay regularization and BN. Thus, obtain closed-form solutions for the optimal layer weights in the high-dimensional and overparameterized regime.
We prove that regularized ReLU network training problems with BN can be equivalently stated finite-dimensional convex problem. As corollary, we also show that the equivalent convex problems involve whitened data matrices unlike the original non-convex training problem. Hence, using convex optimization, we reveal an implicit whitening effect introduced by BN.
We demonstrate that GD applied to BN networks provides an implicit regularization effect by learn- ing high singular value directions of the training data more aggressively, whereas this regularization is absent for GD applied to the equivalent whitened data formulation. We propose techniques to explicitly regularize BN networks to capture this implicit regularization effect.
Unlike previous studies, our derivations extend to deep ReLU networks with BN, CNNs, BN after ReI.y vector output networks, and arbitrary convex loss functions.
1.3 PRELIMINARIES
Notation: We denote matrices and vectors uppercase and lowercase bold letters, respectively, where subscript indicates a certain element or column. We use 0 (or 1) to denote vector or matrix of zeros (or ones), where the sizes are appropriately chosen depending on the context. We also use I, to denote the identity matrix of size n. To represent Euclidean, Frobenius, and nuclear norms, we use ||. 2l2. || ||r. and || ll., respectively. Lastly, we denote the element-wist 0-1 valued indicator function and ReLU activation as 1 [xr 2 0) and (x) = max m2, 0}, respectively.
w consider an L-layer ReLU network with layer weights ( IR' where mo d and my = C' are the input and output dimensions, respectively. Given a training data X E gaxd and a label matrix Y " we particularly focus on the following regularized training problem
min BEO
C(fo,L Y) (R(()),
where we compactly represent the parameters as 0 == (W(), nt ai and the corresponding parameter space as θ := [((((((W) (W("),"' ( (()) E Rmm- -/t E RRm or E T VI e [L]]. We note that 71 and oi are the parameters of the BN operator, for which we discuss the details below. In addition, L(.,)) -) is an arbitrary convex loss function, including squared, hinge, and cross entropy loss, and R--) is the regularization function for the layer weights with the tuning parameter
3 > O. We also compactly define the network output
(x) = A (1-1) (L), where A (BN (AU-))(())
Pressnned in Appendix
All the proofs and some extensions are presented in Appendix.
2

---

Published as a conference paper at ICLR 2022
denote the (th layer activations as A (1) E R and A ( = X. Here, BN,,a (.) represents the BN operation introduced in loffe & Szegedy (2015) and applies matrices column-wise wise.
Remark 1.1. Note that above consistent with the way introduced in loffe Szegedy (2013). However, BN can be placed after ReLU well, e.g, Chen al.) (2019), and thus in Section of Appendix, we will also consider architectures where BN layers are placed after ReLU.
BN before ReLU activations, which is common practice and
For a layer with weight matrix w E mm Km and arbitrary batch of activations denoted as A (1-1) E R BN applies to each column j independently as follows
= (I. 1111 (1-1)
W 8
18)
1
BN,
[I(I. - 117)
where 70) and ( are trainable parameters that scale and shift the normalized value. In this work, we focus on the full-batch case, i.c. A ((-1) A (f-1) E R=xm, This corresponds to training the network with GD as opposed to mini-batch SGD. We note that our empirical findings with GD) indicate identical if not better performance compared to the mini-batch case, which is also consistent with the previous studies [ian & Liu 22119); Summers & Dinneen (2020).
Throughout the paper. we consider regression framework with squared loss and standard weight- decay regularization. Extensions to general convex loss functions are presented Appendix [B. Moreover, below, we first focus scalar outputs i.e. C = 1, and then extend it to vector outputs.
1.4 OVERVIEW OF OUR RESULTS
Here, we provide an overview of our main results. To simplify the notation, we consider L-layer ReLU networks with scalar outputs, ie., my C' thus the label vector the analysis to vector output networks with the label matrix Y E RaxC' in the next sections.
R" and extend
The regularized training problems for an L-layer network with scalar output and BN is given by
L
2 + (1 p1 = min [x. - x112 Σ
|a + w |
(3)
0 2
where we use 7(4) = (L) as dummy variables for notational simplicity.
Lemma 1.1. The problem in is equivalent the following optimization problem
min 1 2 (x)) y112 + / (1)
(4)
where θ, (0 0 (L- + +a (L-1)²
1, Vj E [mL-1]}.
Using the equivalence in Lemma ((4 to obtain
we now take dual of 4 with respect to the output layer weights
PL d= max max 7 - 1 y s.t. max
T (BN,,o (1
S B. (5)
OEG,
Since the original formulation in (3) is a non-conves optimization problem, any solution v in the dual domain yields lower bound for the primal problem, i.e., Pt 2 di. In this paper, we first show that strong duality holds in this case, i.e., P7 = d', and then derive an exact equivalent convex formulation for the non-convex problem 33. Furthermore, the layer weights in some cases so that there is no need to train a network in an end-to-end manner.
obtain closed-form solutions for
TWO-LAYER NETWORKS
In this section, we analyze two-layer networks. Particularly, we first consider high-dimensional regime, where n < d, and then extend the analysis to arbitrary data matrices by deriving an equivalent convex program. We also extend the derivations to vector output networks.
Details regarding the derivation of the dual problem are presented in Appendix B.3
3

---

Published as a conference paper at ICLR 2022
We now consider the regularized training problem for two-layer network with scalar output and BN.
Using the equivalence in Lemma I.I the problem can be stated as
P2
min fl - v1l2 + B w eee 2
(6)
We then take dual of (6) with respect to the output weights w to obtain the following dual problem
p2 z d2 - max- 1 flv yl 2 11 s.t. max BE
-
v (BN,,o (xw(1)) S 3,
where O = {0 : w()) E Rd , + a1) = 1}. Notice that here we drop the hidden neuron
index j E m1] since the dual constraint scans all possible parameters in the continuous set G,
2.1 HIGH-DIMENSIONAL REGIME (n S d)
In the sequel, we prove that the aforementioned dual problem is further simplifted such that one can find an optimal solution O in closed-form as follows.
Theorem 2.1. Suppose I d and X is full rank,ank, then an optimal solution to (6) is
(0))))
x (1-19)) + (-11) (1 (1(1)))) 112 ),))
my
(2)
((-11)))) 111 ((-18)) 112
11(-11y))+1e
((-18y),
vn
jor 1,2. Therefore. strong duality holds, p2 d2.
2.2 EXACT CONVEX FORMULATION
To obtain an equivalent convex formulation to 6 we first introduce a notion of hyperplane arrange- ments; see also Pilanci & Ergen (2020). We first define diagonal matrix D == diag( [Xw 2 0j) for an arbitrary w E R. Therefore, the output of a ReI.U activation can be equivalently written as (Xw), DXw provided that DXw 2 0 and (I, D) Xw S 0 are satisfied. We can define these two constraints more compactly as (2D I,,) Xw O. We now denote the cardinality of the set of all possible diagonal matrices as P. and obtain the following upperbound P < 2r(e(n-1)/mm -1)/r),, where r == rank (X) S min(n, d). For the rest of the paper, we enumerate all possible diagonal matrices (or hyperplane arrangements) in an arbitrary order and denote them as (D.).-
Based on the notion of hyperplane arrangement, we now introduce an equivalent convex formulation for (6) without an assumption on the data matrix as in the previous section.
Theorem 2.2. For any data matrix X. the non non-convex training problem in (6) can be equivalently stated as the following fiite-dimensional convex program
1
P
(2D; L,) 2
min ER
Σ D.U - s() -y
B Σ (||s:ll2 + [|s( s.s.
vi, (2D; L.) 2
2
(8)
where U Roxr and U' E 1 are computed via the compact SVD of the zero-mean data matrix, namely (I, 111TXx = UEVT and U' =
Notice that (8) is a convex program with 2Pr variables and 2Pn constraints, and thus can be globally 3r,
optimized via interior-point solvers with Or, (²)²²) complexity.
Remark 2.1. Theorem 2.2 shows that classical ReLU network with BN can be equivalently 1p
described as a convex combination of linear models { {U's and {U's multiplied with fixed hyperplane arrangement matrices (D.Ye= Therefore, this result shows that optimal ReLU networks with BN are sparse piecewise linear functions, where sparsity is enforced via the group lasso regularization in (8). The convex program also reveals an implicit mechanism behind BN.
Particularly, comparing (8) with the one without BN (see eqn. (8) in Pilanci & Ergen (0200), we
observe that the data matrix for the convex program is whitened, iee. U U I1,41.
We provide more details in Appendix B.4
4

---

Published as a conference paper at ICLR 2022
2.3
VECTOR OUTPUT NETWORKS
Here, we analyze networks with vector outputs, i.e., Y E R
trained via the following problem
P. min AEB
1 [xx)
YI
3 mag
Σ j=1
+ 2 taj o [
(9)
2
Lemma 2.1. The problem in 9 is equivalent the following optimization problem
P2
min SE8,
2l
W
(10)
where O, =- 1 (0 + +a
())
g) =
Using the equivalence in Lemma 2.1 then take dual of 10 with respect to the output layer
weights (22) obtain the following dual problem
P2e
d22 = max
|
+ Y s.t. max DE
VT (BN (xw(i))
S B. (1I)
Theorem 2.3. The non-convex training problem 9
can be cast as the following convex program
1 Σ
Po2 min
DD,'S Y
B
S
(12)
2
for the norm lle., defined
|S
mint s.t. S E tconv hgg (2D: U'h 0, IZ S 1}
f20
where convt.) denotes the convex hull of its argument and U' U
in Theorem 2.2
Remark 2.2. We note that similar to the scalar output case, vector output BN networks training problem involves a whitened data matrix. Furthermore, unlike (8). the nuclear norm regularization in 12 encourages low rank piecewise linear function the network output.
The above problem can be solved in (nn/d) time in the worst case (Sahiner et al. 202 la). which polynomial for fixed d. We note that the problem in (12) is similar to convex sem non-negative matrix factorizations (Ding et al.) 2008). Moreover, in certain practically relevant cases, ( can be significantly simplified so that one can even obtain closed-fora solutions demonstrated below.
Theorem 2.4. Let Y be one-hot encoded label matrix, and X be a full row-rank data matrix with n S d, then an optimal solution to (10) admits
(w (1)*
w/ (2)
(x'y,, 3)4 e;).
(1)* 20
1
bly; 411""yylaa vR
a
(1)
2
1
Vj E [C], where is the jth ordinary basis vector.
3 CONVOLUTIONAL NEURAL NETWORKS
In this section, we extend our analysis to CNNs. Thus, instead of X, we operate on the patch matrices that are subsets of columns extracted from X and denote them X, Raxh, where h is the filter size and is the patch index. With this notation, convolution operation between the data matrix X and arbitrary filter R² be represented as {X Therefore, given patch matrices [X 1k=1 regularized training problem with BN can be formulated as follows
1 2
8
P2. min lee.
BN v.a (Xazz)) wy y
2 + +2 a + w3), (13)
5

---

Published as a conference paper at ICLR 2022
where given My ak Ek=1 1 1',a BN is defined as
BNC 1 (Xxz))
X p41
(1)
vnk
-W=l Xw 14 1
Using Lemma 1.1 the dual problem with respect to w(2) is
K Σ
P2c 2 d2 max
ll v12
2 1y s.t. max
(BNC Ta (Xxz)
SB.. (14)
BEB.
Next, state the equivalent convex program for CNNs.
Theorem 3.1. The non-convex training problem in 13 be cast convex program
Pe K
(2D -,,U un 2
min ERR+1
ΣΣ
di)) + Σ
(1 (1 s.t.
Vi,
22 I. 2
(15)
where we first define a new matrix M = [X1;; X2; ... X RaK xh and then use the following no- tations: the compact SVD of the zero mean form of this matrix is (InK nk 11 )M == UM V
M
and U M
U
[U'n'' A U2
U k
VnR
Theorem 3.J proves that (13) can be equivalently stated as a fiite-dimensional convex program with 2r. Po variables (see Remark 3.1 for the definitions) and 2n..K constraints. Since P. is polynomial in n and d as detailed in the remark below, we can solve (15) in polynomial-time.
Remark 3.1. The number of arrangements for CNNs rely on the rank of the patch matrices instead X. Particularly, the number of arrangements for M, i.e., denoted P. upperbounded as P. S (r(n - 1)/rr)"s, where Te := rank(M) I h & d. Therefore, given a fixed filter size h, Pa polynomial in n and d even when is full rank (see Ergen & Pilanci (202aa) for more details).
X.
DEEP NETWORKS
We now analyze L-layer neural networks trained via the non-convex optimization problem in Below, we provide an explicit formulation for the last two layers' weights.
Theorem 4.1. Suppose the network is overparameterized such that the range of A (L-2) is R". Then an optimal solution for the last two layer weights in (4) admits
(wfl-")" m
A (2-2))
(1118))
(-11) (1((11))),,1ee
(1-11) 10-1
(1-1))) 1111" 11111 ((-1))) 112]
[I((-18))] 1l
V. 1-1" ((-1)x)+
for 1,2. Thus, strong duality holds, iee, př. di.
4.1 VECTOR OUTPUT NETWORKS
Vector output deep networks are commonly used for multi-class classification problems, where one-hot encoding is prevalent strategy convert categorical variables into binary representation that can be processed by neural networks. Although empirical evidence, e.g., .a..aan et al.) (2020), shows that deep neural networks trained with one-hot encoded labels exhibit some common patterns among classes, it is still theoretically elusive how these patterns emerge. Therefore, in this section, we analyze vector output deep networks trained using one-hot labels via our advocated convex duality.
The following theorem presents a complete characterization for the last two layers' weights. Theorem 4.2. Let Y be one-hot encoded label matrix and the network be overparameterized such that the range of A (L-2) IR",, then an optimal solution to (3) can be found in closed-form as
(w) 11- w (1" (A()-2) yss (11y5112 B34 es).
(1-1)*
1
[ 111T,
(1-1)*
1y
1 1
Vn
Vj E [C], where oj is the jth ordinary basis vector.

---

Published as a conference paper at ICLR 2022
10
09
303
500
08
Singsla Volvo Drociio
3020
1000
1500
3500
0.
2000
2000
04
3000
3000
200
400
100
(a) BN model (9)
(b) Whitened model (16
Figure 1: Cosine similarity of network weights relative initialization for each singular (in de- scending order) value direction of the data. Here, we use the same setting in Figure 2 We compare training the BN model (9) to the equivalent whitened model (T6), noting that the BN model fits high singular value directions of the data first, while the whitened model fits all directions equally, thereby overfitting to non-robust features. This shows implicit regularization effect of SGD.
5 IMPLICIT REGULARIZATION OF GD FOR BN
We first note that proposed convex formulations, c.g., (8) 12 and 15), utilize whitened data. Thus, when train them via a standard optimizers such GD/SGD, the optimizer might follow an unfavorable optimization path that leads to slower convergence and worse generalization throughout the training. Based on this, we first analyze the impact of utilizing a whitened data matrix for the non- convex problem in (9) trained with GD. Then, we characterize this impact as an implicit regularization due to the choice of optimizer. Finally, we propose an approach to explicitly incorporate this benign implicit regularization into both convex (8) and non-convex (9) training objectives.
5.1 EVIDENCE OF IMPLICIT REGULARIZATION
Lemma 5.1. The non-convex problem
equivalent to the following problem (i.e., Pi2 = P'220)
Pize == min 8E8
Σ
Uq |q
a vn
w (3)
Σ
13 +
(1)
(1) a + [|w
(16)
16 is equivalent to problem with new data matrix U and weight normalization (Salimans & Kingma
2016 The identity in Lemma 5.1 is achieved by substituting the transformation q, ΣV w
While 99 and (T6) have identical global optima, in practice, GD behaves quite differently when applied to the two problems. Furthermore, these differences extend to the convex formulations in (8) and (15). In particular, while these programs are adept at finding the global optimum, they generalize quite poorly when trained with local search algorithms such as GD. This suggests an implicit regularization effect of GD, the form of which is demonstrated in the following theorem.
Theorem 5.1. Consider 99) and (6) with corresponding models fx2(X) and (U). At iteration
k of GD, assume that (X) f (U), i.e. both models have identical weights, besides 9,
EV w (1)( Then, the subsequent GD updates to model weights are identical, besides those to
w (1) and q₁- In apsse, the updates A (k) 22.3 and A (k)
respectively, admit
"2b.j'
(K) 62
E 22b.j"
Remark 5.1. Theorem 5.1 indicates that when solving (6). GI) will fit directions corresponding to
higher singular values of data much slower relative to other directions compared to (9. By fitting these directions more aggressively, GD applied to ( provides an implicit regularization effect that fits to more robust features. We also note that although our analysis holds only for GD, we empirically observe and validate the emergence of this phenomenon for networks trained with SGD as well.
7

---

Published as a conference paper at ICLR 2022
To verify this intuition, in Figure compare the training and test loss curves of solving both (9)
and (I6) with mini- baiib SGD applied to CIFAR- 10 (Krizhevsky et al. 2014). demonstrating that SGD applied ( generalizes much better than (16). In Figure
plot the cosine similarity of
the weights of both networks compared to their initialization in each singular value direction.
Our results confirm that the BN model fits high singular value directions much faster than low ones, and in fact the lower-singular value directions almost do not move at all from their initialization. In contrast, the whitened model fits all singular value directions roughly equally, meaning that overfits to less robust components of the data. These experiments confirm our theoretical intuition that SGD applied to BN networks has an implicit regularization effect.
5.2 MAKING IMPLICIT REGULARIZATIO EXPLICIT
Since the convex programs (8) and 15 rely the whitened data matrix U, they lack the regularization nec- essary for generalization when optimized with GD. Thus, we aim to impose an explicit regularizer which does not hamper the performance of standard BN networks, but can improve the generalization the equivalent programs trained using first-order optimizers such as GD. One sim- ple idea to prevent the whitened model from fitting low singular value directions mation of the data by filtering its singular values:
3.0
0.6
obtain low-rank approxi-
BN, training Whitened,
0.2
Whitered. les.
(X) UT(E)V
(17)
with E) == 1i kj, which takes the k S r top singular values and removes the rest. We can then solve [I] using fa, (g(X)) as the network output, to form what we denote the truncated problem. This can also reduce the problem dimension in the whitened-data case since one simply omit the columns of U. We find this low-rank approximation to be effective, which can even improve the generalization of GD applied to BN networks.
Figure 2: CIFAR-10 classification accu- racies for two-layer ReLU network in (9) and the equivalent whitened model (6) with SGD and (n, d, m1; bs) (50000, 3072, 1000, 10 1000), where bs denotes batch size. The whitened model overfits much more than the stan- dard BN model, indicating implicit regu- larization.
NUMERICAL EXPERIMENTS
Here we present experiments to verify our theory. Throughout this section, we denote the baseline model and our non-convex model with truncation as "SGD" and "SGD-Truneated", respectively. Likewise, the proposed convex models are denoted as "Convex" and "Convex TrrnccceTTaatdd"..
0.6
0.20
Acouracy
0.4
0.3
0.10
SGD (Daseline)
SG2 [Baseline)
SGD-Truncatad (Durs)
(Durs)
0.05
SCD- Truncaadd (Duss)
Comvex
0.1
Conves Truncae-r (Dun)
Truncated (Duns)
400
Time (sec)
(sec)
(a) CIFAR-I0- 10-(m1 B, bs) (4096, 10 100)
(b) CIFAR- 100-A--100(mm,,5 bs) (1024, 10-4, 10
Figure Test accuracy of two-r BN ReLU networks including the standard non-convex (baseline), its convex equivalent (8). along with their truncated versions with k: = (215, 200) respectively. All
problems are solved with SGID. The learning rates are chosen based on test performance and we provide learning rate and optimizer comparisons in Appendix A
We present additional numerical experiments and details the experiments in Appendix
8

---

Published as a conference paper at ICLR 2022
Closed-Form Solutions: We first verify Theorem 2.4
We consider three-class classification task with the CIFAR-100 image classification dataset (Krizhevsky al. 2014) trained with squared loss and one-hot encoded la- bels, while set (n, d, mi; (8) (1500, 3072, 1000, 1), where bs denotes the batch size. In Figure 4 we compare the objective values achieved by the closed-form solution and the classical network (6). We observe that our for- mula computationally light-weight and can quickly find
G0. Trial
GD. Trial
0.4
GO. Trial
Obsective Fumchion
GO, Trial
0.3
Theory
0.2
global optimum that cannot be achieved with GD even after convergence.
0.0
1000 2000
Convex Formulation and Implicit Regularization: We now demonstrate the effectiveness of our convex for-
Figure 4: Comparing the objective val- ues of the closed-form solution in The- orem 2.4] ("Theory"), and GD (5 trials) applied to the non-convex problem (9) for three-class CIFAR classification with (n, d, m1, 3) (1500, 3072, 1000, 1). Here, "x" denotes the computation time for the closed-form solution.
mulation to solve (9) CIFAR-10 and CIFAR-100 (Krzzhessky et al. 2014). Here, instead of enumer- ating all hyperplane arrangements, we randomly sam- ple via randomly generated Gaussian vectors such that my P. We compare the results of training with and without the explicit regularizer (17) for both cases. We particularly choose such that singu- lar values explain 95% of the variance in the train- ing data. Then, we consider two-layer networks for image classification on CIFAR- 10 with (n, d, m. bs. k C) (5x10f 3072, 4096, 10 10-4, 100 215, 10) and CIFAR-100 with (n, d, m1, 3, bs, C)= (5x10* 3072, 1024, 10 1,=,,10 100 200. 100). Figure we observe that Con- vex generalizes poorly (as expected with our results in Section After the singular value truncation, and Convex-
SGD, SGD-Truncates Truncated in fact generalizes better for CIFAR- 100. This shows that the optimizer benefits from the convex landscape of the proposed formulation (8). Furthermore, truncation actually improves the performance of SGD in the case of CIFAR-100, suggesting this is good regularizer use.
generalize equally well for CIFAR-10, and Convex-
CONCLUDING REMARKS
In this paper, studied training of deep weight-decay regularized ReLU networks with BN, and introduced a convex analytic framework to characterize an optimal solution to the training problem. Using this framework, proved that the non-convex training problem can be equivalently cast as a convex optimization problem that can be trained in polynomial-tine equivalents involve whitened data matrix in contrast to the original non-convex problem using the raw data, which reveals whitening effect induced by BN. We also extended this approach to analyze different architectures, e.g., CNNs and networks with BN placed after ReLU. In the high dimensional and/or overparameterized regime, our characterization further simplifies the equivalent convex representations such that closed-form solutions for optimal parameters can be obtained. Therefore, in these regimes, there is no need to train network in an end-to-end manner. In the light of our results, we also unveiled an implicit regularization effect GD on non-convex ReLU networks with BN, which prioritizes learning high singular-value directions of the training data. We also proposed a technique to incorporate this regularization to the training problem explicitly, which numerically verified be effective for image classification problems. Finally, remark that after this work, similar convex duality arguments were applied to deeper networks [irgen & Pilanci (2021c ee Wang et al. 22021) and Wasserstein Generative Adversarial Networks JVGANN)JSahing ct al. 2022) Extensions of our convex BN analysis to these architectures are left for future work.
Moreover, the convex
ACKNOWLEDGMENTS
This work was partially supported by the National Science Foundation under grants ECCS- 2037304, DMS-21 2134448, the Army Research Office.
9

---

Published as a conference paper at ICLR 2022
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.
Sanjeev Arora, Zhiyuan Li, and Kaifeng Lyu. Theoretical analysis of auto rate-tuning by batch normalization. 2018.
Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton. Layer normalization. arXiv preprint arXivv1607.06450, 2016.
Nils Bjorek, Carla P Gomes, Bart Selman, and Kilian Q Weinberger. Understanding batch normal- ization. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 31, pp. 7694-7705. Curran As- sociates, Inc., 2018. URL URL/attpa://prooeeeeeeee w3c. 77575300f0.c4477777777777440o60
neurips cc/ wc/ppapee/o0////E...... pddf]
Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
Guangyong Chen, Pengfei Chen, Yujun Shi, Chang- Yu Hsieh, Benben Liao, and Shengyu Zhang. Rethinking the usage of batch normalization and dropout in the training of deep neural networks. arXiv preprint #rXiv:195.05922 2019.
Patrick Marques Ciarelli and Elias Oliveira. Agglomeration and elimination of terms for dimen- sionality reduction. In 2009 Ninth International Conference on Intelligent Systems Design and Applications, pp- 547-552. IEEE, 2009.
Thomas M Cover.
Geometrical and statistical properties of systems of linear inequalities with applications in pattern recognition. IEEE transactions electronic computers, (3):366-334 1965.
Hadi Daneshmand, Jonas Kohler, Francis Bach, Thomas Hofmann, and Aurelien Lucchi. Batch normalization provably avoids rank collapse for randomly initialised deep networks, 2020.
Steven Diamond and Stephen Boyd. CVXPY: A eebbede modeling language for convex optimization. Journal of Machine Learning Research, 17(83)11-5, 1,0,11,,,,6,,6. 2016.
Chris HQ Ding, Tao Li, and Michael Jordan, Convex and semi-nonnegative matrix factorizations.
IEEE transactions pattern analysis and machine intelligence, 32(1):45-55, 2008.
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 2020. PMLR. URL WRRLhttp::. http:httt//poceeeee httt::://proceedingg.. m.r. wttp::/eeeee/esseeeeeeee
html
Tolga Ergen and Mert Pilanci. Implicit convex regularizers of emn architectures: Convex optimization
of two- and three-layer networks in polynomial time. In International Conference on Learning Representations, 202 URL (tRLsst:::/// http///pppneeeeeeeeeeeeeeeeeeeep
/ net wtt.:ooommmmmmm wwwtoormmiiiiii- 0N= JUH4 JMv
Tolga Ergen and Mert Pilanci. Convex geometry and duality of werrpparamterrized neural networks.
Journal of Machine Learning Research, 22(212):1-63, 2021b. URL httt:://mmir... orrg
papers/v22/20-11 1mmm.mmm1
Tolga Ergen and Mert Pilanci. Global optimality beyond two layers: Training deep relu networks via
convex programs. In Marina Meila and Tong Zhang (eds.). Proceedings of the 38th International Conference on Machine Learning. volume 139 of Proceedings of Machine Learning Research, pp. 2993-3003. PMLR, 18 18-24 Jul 2021c. URL httphhttpp:/prreeeiing... http://eeeeiinammmmm.rreesss//se
ergen21a. html
Tolga Ergen and Mert Pilanci. Path regularization: A convexity and sparsity inducing regularization for parallel relu networks. arXiv preprint arXiv:2110.09544 2021d.
10

---

Published as a conference paper at ICLR 2022
Tolga Ergen and Mert Pilanci. Revealing the structure of deep neural networks via convex duality. In
Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 3004-3014. PMLR, 18-24 Jul 2021e. URL htt.ttss::/ /ttp:::e////ooceeiidee ngs. press / v1 http//vvv11eerggenne...e html
Michael Grant and Stephen Boyd. CVX: Matlab software for disciplined convex programming, version 2.1. http://cvx:: www. cvx March 2014.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. In Proceedings of the IEEE international conference on computer vision, pp. 1026-1034, 2015.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 770-778, 2016.
Daniel Jiwoong Im, Michael Tao, and Kristin Branson. An empirical analysis of the optimization of deep network loss surfaces. arXiv preprint 16 2016.
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In Francis Bach and David Blei (eds.). Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pp. 448 456, Lille, France, 07-09 Jul 2015. PMLR. URL http:://proceeedn//// mlr. www.press/v3//lofe... html
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 14126690, 2014.
Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. The CIFAR-10 and -100 datasets. http 7/ 7/www.cc cs. toronto..oo.....o edu/kriz/ciaar html 2014.
Xiangru Lian and Ji Liu. Revisit batch normalization: New understanding and refinement via composition optimization. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 3254-3263. PMLR, 2019.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. In search of the real inductive bias: On the role of implicit regularization in deep learning. arXiv preprint arXiv: 141.661144.. 2014.
Piyush C Ojha. Enumeration of linear threshold functions from the lattice of hyperplane intersections. IEEE Transactions on Neural Networks, 11(4):839-850, 2000.
Vardan Papyan, XY Han, and David L Donoho. Prevalence of neural collapse during the terminal phase of deep learning training. Proceedings of the National Academy of Sciences, 117(40): 16652-24663, 2020.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, gegooperformnnce deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Bue E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems 32, pp. 8024-8035. Curran Associates, Inc., 2019.
Mert Pilanci and Tolga Ergen. Neural networks are convex regularizers: Exact polynomial-time convex optimization formulations for two-layer networks. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 7695-7705. PMLR, 13-18 Jul 2020. URL
http::/pproceedingg www.nng..m......mm..mm......w..m http://pcc..//113/aaooa........
Arda Sahiner, Tolga Ergen, John M. Pauly, and Mert Pilanci. Vector-output relu neural network problems are copositive programs: Convex analysis of two layer networks and polynomial-time algorithms. In International Conference on Learning Representations, 2021a. URL https
wtwp:e/wwwwieeettutteeeaaaaaeeee //openreview .nt/ forum id

---

Published as a conference paper at ICLR 2022
Arda Sahiner, Morteza Mardani, Batu Ozturkler, Mert Pilanci, and John M. Pauly. Convex regular- ization behind neural reconstruction. In International Conference on Learning Representations. Bttpe///ooommmmddemdeee
2021b. URL
Arda Sahiner, Tolga Ergen, Batu Ozturkler, Burak Bartan, John M. Pauly, Morteza Mardani, and Mert Pilanci. Hidden convexity of wasserstein GANs: Interpretable generative models with closed-form solutions. In International Conference on Learning Representations, 2022. URL
https::/cpeeneeiit mner/EooruniddeeeLLLeess.
net
Tim Salimans and Diederik P Kingma. Weight normalization: A simple reparameterization to accelerate training deep neural networks. NIPS, 2016.
Shibani Santurkar, Dimitris Tsipras, Andrew Ilyas, and Aleksander Madry. How does batch normal- ization help optimization? In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 31, pp. 2483- 2493. Curran Associates, Inc., 2018. URL http::ttts///cccetttt/ wew.eediiinnnn.n.n....... www.rnuurr.... cccppprrr 2018
pdf
Pedro Savarese, Itay Evron, Daniel Soudry, and Nathan Srebro. How do infinite width bounded norm networks look function space? CoRR, abs/1902.05040,, 2019. URL
abs/1902. 05040
Maurice Sion. On general minimax theorems. Pacific Math. 8(1):111-176 1958. URL https:
//projecteuclia.ccom org: http://///aaaa.......mmoaa/0
Richard P Stanley et al. An introduction to hyperplane arrangements. Geometric combinatorics, 13: 389-496, 2004.
Cecilia Summers and Michael Dinneen. Four things everyone should know to improve batch
normalization. In International Conference Learning Representations, 2020. URL |
wawprvvviww..eet/ouumm2...... //openreview.oo net/ forumiidd HJX8HANE
RH Tütüncüi KC Toh, and MJ Todd. Sdpt3 matlab software package for ceneddffiiit-quudrree linear programming, version 3.0. Web page http://www. math. nus. edu. sg/mattiohccssdpt3 himl, 2001.
Dmitry Ulyanov, Andrea Vedaldi, and Victor Lempitsky. Instance normalization: The missing ingredient for fast stylization. arXiv preprint 10X7::6677.0022 2016.
Yifei Wang, Tolga Ergen, and Mert Pilanci. Parallel deep neural networks have zero duality gap. CoRR, abs/21 10.06482, 2021. URL /
06482
Mingwei Wei, James Stokes, and David Schwab. Mean-field analysis of batch normalization, 2019.
RO Winder. Partitions of n-space by hyperplanes. SIAM Journal Applied Mathematics, 14(4): 811 811-818, 1966.
Yuxin Wu and Kaiming He. Group normalization. In Proceedings of the European conference on computer vision (ECCV), pp- 3-19, 2018
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107-115. 2021.
12

---

we can use Published as a conference paper at ICLR 2022
Appendix
Table of Contents
Additional Details and Numerical Experiments
13
A.
Inference in BN models
14
A.2
Additional Experiment: Batch Sizes for SGD
14
A.3
Additional Experiment: Singular Value Truncation Ablation
15
A.4
Additional Experiment: Convolutional Architectures
15
A.5
Experiments from Section Evidence of Implicit Regularization
16
A66
Verification Closed Form Solutions
17
Exact Convex Formulation and Implicit Regularization
B
Additional Theoretical Results
21
B.
Extensions to Arbitrary Convex Loss Functions
22
B.2
Proof of Lemma 1.1]
22
B.3
Derivation of the Dual Problem in
23
B.4
Hyperplane Arrangements
................................
24
Two-Layer Networks
24
C.I
Closed-Form Solution the Dual Problem in ................................
24
Proof of Theorem] 2.1]
25
Proof of Theorem 2.2
25
4 Proof of Lemma
28
Proof Theorem 2.3
29
Theorem
D Convolutional Neural Networks
31
D. Proof of Theorem].11
31
E The Implicit Regularization Effect of SGD on BN Networks
32
E.1 Proof of Lemma 5.1
32
Proof of 15.
32
F Deep Networks
34
F Proof Theorem
34
2 Proof of Theorem
35
G BN after ReLU
35
Proof Theorem 2
35
Proof Theorem
36
A ADDITIONAL DETAILS AND NUMERICAL EXPERIMENTS
In this section, we present the details about our experimental setup in the main paper and provide new numerical experiments.
We first note that since we derive exact convex formulations in Theorem 2.2
2.3
3.1
solver such as CVX (Grant& & Boyd, 2014) and CVXPY (Diamond Boyd 2016 Agrawal et al.) 2018) with the SDPT3 solver (T (Tütüicc et al. (001) to train regularized Rel.U networks training problems with BN. Although these solvers ensure quite fast convergence rates global minimum, they do not scale to moderately large datasets, e.g., CIFAR-10. Therefore, in our main experiments,
13

---

Published as a conference paper at ICLR 2022
use equivalent unconstrained form for the constrained convex optimization problems such that it can be simply trained via SGD. Particularly, let us consider the constrained convex optimization problem in ( for which the constraints can be incorporated into the objective as follows
P
P
1
min 8:,8(
Σ
D.U - s/)
+ 3
[|s|112 2 + l|s/112)
2
1=1
P p 1s ((-2D - L,)sss) + +(-(2D; U,))
where p is hyper-parameter penalize the violating constraints. Therefore, using the uncon- strained form above, we are able to use SGD or other standard first-order optimizers to optimize the constrained convex optimization problem in
Unless otherwise stated, all problems are run on single Titan Xp GPU with 12 GB of RAM, with the Pytorch deep learning library (Paszke et al., 2019). All SGD models use a momentum parameter of 0.9. All baseline models are trained with standard weight- regularization as outlined in (3)
All batch-norm models are initialized with scale 1 1 and bias at = 0. and all other non-convex
model weights are initialized with standard Kaiming uniform initialization (He et al. 2015). For the convex program, we simply initialize all weights to zero.
A.1 INFERENCE IN BN MODELS
For the non-convex standard BN network, we perform inference in the traditional way. All BN problems with SGD take an exponential moving average of the mini- batch mean and standard deviation with momentum of 0.1, is used as default in deep learning packages, except in the case of full-batch GD, in which case a momentum value of 1 is used. In truncated variants, while the training data is truncated with the explicit regularizer gX).. for test data X, we compute the standard forward pass fo.((X), i.e. without changing the test data in any fashion, and removing the training-data mean and normalizing by the training-data standard deviation as found with the exponential moving average method described above. For the convex program, we can form the weights to the non-convex standard BN network from the convex program weights, and compute the test-set predictions with the non-convex standard BN network.
A.2 ADDITIONAL EXPERIMENT: BATCH SIZES FOR SGD
The model of BN we present in this paper is with the model with GD without mini-batching. In this section, we demonstrate that mini-batching does not change the training or generalization performance of BN networks in any sigmificant manner. Our observations also align with previous work examining this subject, such as Lian & L.u 2019): Summers & Dinneen (2020).
In particular, compare the effect of different batch sizes using four layer CNN, where the first three layers are convolutional, followed by BN, ReLU, and average pooling, and the final layer is fully-connected layer. Each CNN layer has 1000 filters with kernel size 3 x 3 and padding of 1.
We take the first two classes from CIFAR-100 to perform a binary classification task with X 1000xx3072 and y E 1000 For (Ir, = 10008))-111,,, 10-1), where Ir denotes the learning rate, and weight-decay is applied to all parameters. We compare the effect of using batch size of 50, 100, 500, and 1000. We run the batch size 1000 case for 501 epochs, and then train the other batch size cases such that the training time is roughly matched. Due to memory constraints, the full-batch form of SGD does not fit on standard GPU-thus, all models are trained with standard CPU with 256 GB of RAM. We compare the train and test accuracy curves in Figure [5] where we see that all batch sizes perform roughly equivalently in both test and training performance. This demonstrates that our full-batch model for BN accurately captures the same dynamics as BN as used in the mini-batch case.
We note that we also perform an ablation study on batch sizes for the nonconvex programs in Section 6 in Appendix A.7.2. and find the same conclusion.
14

---

Published as a conference paper at ICLR 2022
Accuracy
0.8
Test-bs=50
0.7
Test-bs=500
Test-bs=1000
Train-bs=50
0.6
Train-bs=500
0.5
Train-bs=1000
10000
20000
Time (sec)
Figure 5: Comparison of different batch sizes (bs) for four-layer CNN with BN layers, (mi, Ir, 3) :3) (1000, 10 10_ We demonstrate that different batch sizes perform roughly equivalently both training and test convergence.
A.3 ADDITIONAL. EXPERIMENT: SINGULAR VALUE TRUNCATION ABLATION
In order make clear the effect of the singular value truncation as proposed Section 5.2 on generalization performance, we include an additional ablation study new dataset to verify our intuition. particular, we evaluated the proposed methods on the CNAE-9 dataset (Ciarelli Oliveira 2009). dataset of 1080 emails with 856 text features over 9 classes. Following Clarelli & Oliveira (2009), the first 900 samples were used as the training set, while the final 180 samples are used the test set in this experiment, to obtain X R900x 856 R900X9
We evaluated the proposed approaches with (m1, bs) (10000. 10 2,--,,00 900), comparing the base- line non-convex SGD approach to the convex truncated formulation for & E {10, 100, 200, 400, 856), where k is the index for which all smaller singular values truncated from the training dataset. We trained each model for roughly an equal amount of time (15 seconds). For all architectures, learning rate of 10
was fixed.
We find in Figure 6 that as expected, singular value truncation can effectively match the training and test performance of the SGD BN baseline, but only in certain range of k. When k is too low, such as l: 10, valuable features the data are eliminated and the convex program underfits, whereas when & is too large, such as 856 the convex program overfits and does not generalize well. Values of k= 100 and A = 200 generalize the best for this problem, and their corresponding truncations preserve 80% and 91% of the training data respectively. The exact value of k which is optimal for generalization is a hyper-paramete that can be tuned, though it clear that a large range of values often work well. This ablation lends additional support to the truncation approach proposed in Section 5.2
A.4 ADDITIONAL EXPERIMENT: CONVOLUTIONAL ARCHITECTURES
To demonstrate the effectiveness of the convex formulation in convolutional settings, we provide an additional experiment to show the success of this approach. In particular, the baseline architecture, we consider a two-layer network which consists of a convolutional layer, followed by channel-wise BN, followed by ReLU activation, then subsequently followed by average pooling operation, flattening. and a fully-connected layer. To use our convex formulation (c.g. (15) for such architecture, to a region whose outputs will be averaged), and apply a global-average pooling model as in (15) each spatial block separately and combine the predictions from each spatial block to- gether to obtain one prediction. This suffices as a relaxation of the baseline convolutional architecture.
split an input image into spatial blocks (each block corresponds
To this end, we implement the non-convex and convex architectures on CIFAR-10 with the AdamW optimizer for 50 epochs. The convolution with a 3 kernel with padding of 2 and stride of 3, with average pooling to spatial dimension of 4 x 4. The parameters cho-
15

---

Published as a conference paper at ICLR 2022
1.00
1,00
0.95
0.90
Accumcr
0.85
0.50
(Baseline)
0.85
Convex-Truee Truncated, 10
Conver-Tunnated, 10
ConwexTTunccatsd
ConvaxTunctted 100
Convex Truncated. 200
Tuncte 200
Convex Truncated,
0.70
Trnceteee 400
Convex
Convex
0.75
0.65
(sec)
Time (sec)
(a) CNAE- --AA---Training accuracy
(b) CNAE-9 West accuracy
Figure 6: Comparison of different truncation schemes of convex program compared SGD baseline, with (m,,& 3, bs, Ir) (10000, 10 10-2, 900, 10 10-5), and E {10, 100, 200, 400, 856), where 856 simply the convex program without truncation. Large values of & overfit, while low values underfit, and intermediate values match exactly the performance of SGD baseline.
Method
Train Accuracy
Test Accuracy
Baseline
87.33
67.06
Baseline Truncated
78.41
66.62
Convex (Ours)
81.60
66.91
Convex Truncated (Ours)
81.35
67.11
Table 1: Results of CIFAR-10 classification with two-layer ReLU CNN architectures, with a 3 kernel size, padding of 2, stride of 3, and averaging to
spatial dimensions, with (n, m1. B8 bs, k. Ir) (5 104, 1024, 5 x 10-4 4 250, 22, 10, 10 10- Consistent with our results on fully-connected architectures, the convex architecture matches or improves upon the performance of the non-convex architecture, verifying our theoretical results. We also observe the less pronounced impact truncation convolutional experiments.
for this model given by (n, mi bs, I, (5x 10 1024, 10-4 250, 22, 10, 10-
We compare the results of the baseline, aaseline-truncated convex, and convex-truncated approaches. In Table ! we see that the accuracy of this CNN approach is higher than the fully-connected methods we reported in our paper, and expected, there strong correspondence between the performance of the convex and baseline models, again reiterating our strong theoretical results, even the case of this convex relaxation.
As illustrated in Table I truncation enables the convex approach to obtain equivalent or higher test accuracy than its non-convex counterparts, while obtaining similar training accuracy. However, notice that the accuracy improvement provided by truncation is considerably less than the ones for fully-connected layers (e.g. Figure 3aj This phenomenon is essentially due the distribution of the singular values of the data matrix. Particularly, for fully connected layers, we have U E gd and therefore the dimension we truncate has d= 3072 features. In this case, the distribution of singular values follows exponentially decaying pattern such that the ratio of maximal and minimum singular values, also known as the condition number of the data, is quite large (amax/ (onxx/mmin min 5892.5). On the contrary, for CNNs, we operate on the patch matrices so that U mi RRxx where 27 is the size of each convolutional filter. Since the data matrix is much more well conditioned (mmax/o /aaax/mmin = 271.2) and has significantly smaller feature dimension, the impact truncation less emphasized in our experiment.
A.5 EXPERIMENTS FROM SECTION 5.1 EVIDENCE OF IMPLICIT REGULARIZATION
As described in the main paper, for both the standard BN architecture and whitened architecture, we use the parameters (n, d, m2, 3, bs. Ir) (50000, 3072, 1000, 10 1000. 10 4), where bs stands for batch size and Ir stands for learning rate. Both models were trained with SGD for 501 epochs,
16

---

Published as a conference paper at ICLR 2022
and the learning rate was decayed by factor of 2 in the case of training loss plateau. We now expand on the definition of cosine similarity to clarify Figure [| (in the main paper).
For weights (W, W define the distance measure
V W) (v, W IV, v W
dx,((W, W')
(18)
where v, the columns of V from the SVD of the zero mean data (I, 111 1111)X )X. This distance metric thus computes the cosine similarity between W and W after heing projected to the right singular subspace V;-
For the same networks trained in Figure (in the main paper), we compute (dx,((W())
) for the BN model 9 and (du,;QQ() (Q)) ()))) for the equivalent whitened model [6.. for each epoch k. We display these in Figure D (in the main paper). These correspond to a measure how far the hidden-layer weights move from their initial values over time in the right singular subspace of the data, with lower values indicating that the weights have moved further from their initialization.
A.6 VERIFICATION OF CLOSED-FORK SOLUTIONS
See Figure for the results of this experiment. The GD baseline model is trained with learning rate of 10-5, and the learning rate was decayed by a factor of 2 in the case of training loss plateau. The closed-form solution takes only 0.578 seconds to compute, whereas we run the GD baseline model for 40001 epochs, which takes approximately 50 minutes to run per trial. Each trial behaves slightly differently due to the randomness of the initialization of each network.
In terms of the generalization performance, the closed-form expression obtains a test three- class classification accuracy of 47.7%, whereas the baseline GD networks achieve an average of 60.1% final test accuracy, again indicating the implicit regularization effect imposed by GD applied to BN networks.
A.7 EXACT CONVEX FORMULATION AND IMPLICIT REGULARIZATIO
In this section, we describe additional details about our main experimental results of the main paper. In particular, we show the effect of training all models for longer duration than displayed in the main paper, the different learning rates considered, the different batch sizes considered, along with the effect of using Adam as opposed SGD, and comparison to a non-BN architecture.
For these experiments, we trained each model (SGD, SGD-Truncated, Convex, Convex- Truncated) for roughly the same amount of time, and considered a range of learning rates for each problem. In particular, for CIFAR-I0, we considered the learning rates {10 33, 5 x 10 10 4), and trained the SGD, SGD-Truncated, Convex, and Trrve--Trnncated models for 501, 501, 51, and 201 epochs respectively, and each model was trained for roughly 700 seconds. In contrast, for CIFAR-100, considered the learning rates (10-5, 5 10-5 10 10-4), and trained the SGD, SGD-Truncated, Convex, and Convex-Truncated models for 621,1001,44 41, and 251 epochs respectively, and each model was trained for roughly 800 seconds.
The range of learning rates was chosen such that all models reached their peak test accu- racy within the allotted time, and the learning rate with the best final test accuracy was chosen for each model. In particular for CIFAR-10, the chosen learning rates for the SGD, SGDD-Truncate, Convex, and Truncatee models were 10-5, 10-5, x 10-5, and 10-4, respectively. In contrast, for CIFAR- 100 the chosen learning rates for the SGD, SGD-Truncated, Convex, and Convex-Truncated models were 5 x 1 1 10 and 5 10-4 respectively.
For CIFAR-10 10 experiments in this section, always (m1, 8, bs) (4096, 10 103). while for CIFAR-100 100, we used (m, 3, bs) (1024, 10-4, 103), where bs stands for batch size, as described in the main paper. The only exception is during our batch size ablation study in Section
17

---

Published as conference paper at ICLR 2022
A.7.2
in which the batch size is varied. All models trained with SGD, except in Section
A.7.4
A.7.1
TRAINING CURVES AND OVERFITTING
0.5
0.4
0.3
(Baseline)
0.2
(Baseline)
Convex (Ours)
Convex (Ours)
[Durs]
(Ours)
Canvex Truncated (Ours)
Convex Truncated (Ours)
0
200
400
600
800
1000
1200
1400
200
400
600
800
1000
1200
1400
(sec)
Time (sec)
(a) CIFAR- -o-rrinni accuracy
(b) CIFAR- SETAR-1O-TRR 10-Test accuracy
1.0
0.30
0.25
0.20
0.6
0.15
0.10
(aaeline]
(Baseline)
0.2
Convex (Ours)
Convex [Ours]
SCD Truncated (Durs]
SGD Truncated (Gurs)
Truncated
(Ours)
1000
1500 1750 2000
1000 1250
1500
1750
(sac)
(sec)
(c) MAAAR--00-Trainin accuracy
(d) CIFAR-100- 100--estt accuracy
Figure 7: Here, we provide longer trained version the CIFAR-10 and CIFAR-IO0 experiments in Figure 3 (in the main paper). We see that training for longer does not affect the results, as all models begin overfit, and they overfit the same rate. For CIFAR-106 100, we observe that the baseline overfits so much that the standard Convex model eventually overtakes it in generalization performance.
To make more robust our claims in the main paper, we consider training each network for longer duration, such that each network can near 100% training accuracy. We plot the results of both training and test accuracy for CIFAR-10 10 and CIFAR-100 in Figure ? We note that extending training for longer only seems to increase over-fitting, and increasing train accuracy to 100% does not improve model performance. Therefore, the results of our main paper, which display the curves for a shorter duration, represent the peak performance all algorithms before they begin to overfit.
A.7.2 IMPACT OF DIFFERENT BATCH SIZES
To further bolster our claim that taking the convex dual form from a full-batch case of SGD is sufficient for capturing the performance of standard BN networks, we compare the performance of Convex and Convex-Trumee Truncated with SGD with different batch sizes, namely bs E {100, 500]. In Figure 8 we show that different batch sizes do not improve the generalization performance of BN networks, thereby validating that the convex dual derived from the full-batch model is accurate representing BN networks when trained with mini-batch SGD. Therefore, for all of other experiments, we use bs = 1000.
18

---

Published as a conference paper at ICLR 2022
0.30
0.55
0.2
0.50
Accurao
0.45
SGD Daselne--b=-1000
0.15
SGD In-niirncttd (Ours) bo00---=000000000
(8ssefnn)--ss=500
(Ours)-bs-500
0.40
SGD (aseine)-bs=-00
0.10
SGD-Irunctte (urr))-s=1000
Convex Truncated (Durs)
ConvexTruncatoed (Ours)
UGu-Truncated (Qurs)-bs=1000
1000
SGD (Beseline/-bs=1000
0.35
SGD- Truncaruddd (bu-s)
SGD (Saseline)) bs-500
UuD-Truncated (Qurs)
(Raselino) bs-
0.30
0.00
100
200
300
400
500
600
700
800
100
300
400
600
830
Time Isec)
Time
(a) CIFAR-10
(b) CIFAR- 100
Figure 8: Batch size (bs) ablation study, considering bs E {100, 500, 1000] for SGD (Baseline) and Sruncaru for the experiment in Figure the main paper). We that smaller batch sizes do not improve the performance of SGD. Therefore, we choose bs = 1000 for all the main experiments.
0.30
0.55
0.50
0.20
Accurag
0.45
SGD-Truncated (Ours)-In-1o-5
0.15
Truncated (Ours)-i--3e:
5C0 Truncaces (0un) In55 ScD-tuusseed (Dun)-iried
0.40
S60 TrD-caructdedd (Ours)-Ir=1c44
Convex (Ouns)
SCD--nunoeee (Dlnn)-inbbed
SGD (Beseline)-Ir1e5
Corves- 1Dumi
0.35
[Baseline)-rr-555
0.05
56D (Baad net inSe
SGD (Beseline)-ir1ee
(Baseline
100
200
300
400
500
600
700
800
0
100
200
300
400
500
600
700
800
Time (sec)
Time (sec)
(a) CIFAR-10
(b) CIFAR-100
Figure Learning rate (Ir) ablation study for the experiment in Figure 3 (in the main paper), considering Ir (10-5,, 10-5 10-4) for SGD and improve the performance SGD, because these models with larger Irs reach the same peak accuracy but overfit quicker. For CIFAR-10, selected learning rates 10-5 for both SGD and For CIFAR-106 100, we chose learning rates 5 x 10-5 for SGD, and 10 -4 for GGD-Trunctted.
We see that larger Irs do not
A.7.3 IMPACT OF DIFFERENT LEARNING RATES
We plot test curves for all considered learning rates for each program for the bascline program for CIFAR- 10 and CIFAR- 1000 in Figure We that the different learning rates considered do not significantly change the peak performance, with higher learning rates simply overfitting earlier.
A.7.4 IMPACT OF DIFFERENT OPTIMIZERS
We also consider training both the standard non-convex and our convex formulations with the Adam optimizer (Kingma & Ba 2014). Not surprisingly, we see similar implicit regularization effect when applied to BN networks. For the Adam experiments, we consider the same set of learning rates as the SGD experiments, and fix hyper-parameters (31, <) (0.9, 0.999, 10 10-8), are the standard default values. We run each program for the number of epochs as the SGD experiments, and consider the same learning rates as the SGD experiments. For CIFAR-10, the chosen learning rates for all the models was 10-5, For CIFAR-100) the chosen learning rates for the Adam, Adam- Maam-Truncated. Convex, and -runcxeTrun models were 10 1 5.xx 10 and 10-5, respectively.
We plot the results of the test curves in Figure 10 and plots of longer trained curves in Figure I1] as well as the effect of different learning rates in Figure [2 We find that with Adam, the results mirror that of SGD. For the best learning rate chosen for each method, the truncated convex formulation performs the best, followed by the truncated non-convex and standard non-convex
19

---

Published as a conference paper at ICLR 2022
0.25
Accurao
0.4
0.15
Adam (Baselinc)
(Baseline)
Convex (Ours]
Convex (Duns)
(Ours)
(Ours)
Sonvex-Truncated (Ours)
Convex-Truccated (Ours)
0.1
0.00
100
200
300
400
500
600
700
800
100
200
300
400
500
600
700
800
Time
Time (sec)
(a) CIFAR-10
(b) CIFAR-100
(in the main paper), where we show test accuracies and all problems solved with Adam. We that these results mirror those with SGD, where
Figure 10: A counterpart of the experiment in Figure (in
performs equally well as or outperforms the baseline.
0.5
0.4
Accine
0.3
Adam (Baseline)
0.2
Adam (Baseline)
Convex (Ours)
Convex (Ours)
0.2
Truncated (Ours)
Adam Truncated
Convex Truncated (Durs)
0.1
Canvex Truncated (Oums
0
200
400
600
1200 1400 1600 Time (sec)
800
1000
200
400
600
800
1000 1200 1400 1600
Time (sec)
(a) CIFAR-IO 10-Trannin accuracy
(b) CIFAR- -OAERR-O---- 10-Test accuracy
0.8
0.25
AcCUr
0.15
0.4
Atam (Baseline)
Adam (Baseline)
Convex (Ours)
Convex (Ours)
Truncated (Ours)
0.05
Adam Truncated (Ours)
Convex Tru nrated (Durs)
Convex-Trunctte Truncoted (Durs)
0.0
0.00
200
400
600
800
1000
1200
1400
200
400
600
600
1000
1200
1400
Time (sec)
Time (sec)
(c) CIFAR- 100-ininn accuracy
(d) CIFAR-I00 -os- accuracy
Figure 11: Here, we provide longer trained version of the CIFAR-10 10 and CIFAR- 100 experiments
in Figure 10 We see that training for longer does not change the results, as all models begin overfit.
formulations, followed by the standard convex formulation. We can conclude that our results are robust the choice of optimizer.
A.7.5 COMPARISON OF BN TO NON-BI BN TWO-LAYER ARCHITECTURES
One might speculate what the impact of adding BN to two-layer network have, compared to a simple standard fully-com cully-connected architecture. In this section, we compare the standard two-layer network in both its primal and convex dual form, first presented in Pilanci & Brgen (2020), the BN networks described in this paper. We let all parameters, i.e. (n, m,, 3, bs, C') be identical to the setting of the main paper, and again consider sweep of learning rates was done for the BN experiments. For the non-conver primal no BN form, the best performance came from a learning rate
20

---

Published as a conference paper at ICLR 2022
0.55
0.25
0.50
0.45
(0urs)-Im=1e5
Adam-Truncated (Ours)-Im=1e4
0.40
Adam Truncated (
0.15
Adam-Tuncated (Ours)-In=Se-
Truncaleed (Ours)-Immee4
Ndam-Trunctted (Ours)-Im1e-3
Convex: Truncated (Durs)
Convex fruncatee [Ours)-Ir=les
(Ours)-In-1o4
Corvex Truncated (Ours)-Ir=Sp5
0.30
Adamm (Baseline)-ir-ee.
Adam Baseline)---les
0.25
(Baseline)-ir-555
(Baseline)-
Adamm (Basellne)-ir-1--
Adam (Bazeline)- F=1e
0.20
100
200
300
400
500
600
700
800
0.00
100
200
300
400
500
600
700
800
Time Isec)
Time (sec)
(a) CIFAR-10
(b) CIFAR-
Figure 12: Learning rate (Ir) ablation study for the experiment in Figure 10 where we consider Ir E
(10-5,5 5 10-5 10-1) } for Adam. We that larger learning rates do not improve the performance of Adam or Convex-Truncated Truncated, because these models reach the same peak accuracy but simply overfit earlier. For all models, we select learning rate of 10 - for the CIFAR-10 1- experiment in Figure 10a We choose a learning rate of 10-5 for Adam and Convex-Truncatee and a learning rate of 10 for
Adam- -runccted for the CIFAR-100 experiment in Figure 10b
0.60
0.55
0.25
0.50
0.20
Accuresy
SGD (Baseline)
(Baseline)
0.10
Convex (Ours)
IGD-Truncated (Ours)
50D-Truncated (Ours)
Convex no BN (Ours)
(Ours)
0.05
Convex Truncated (Durs)
Convox no BN (Ours]
BN
BN (Baseline)
0.30
600
800
600
800
Time (sec)
Time (sec)
(a) CIFAR-10
(b) CIFAR-100
Figure 13: Comparison of two-layer BN networks presented Figure 3 (in the main paper), to the non-convex two-layer ReLU architecture without BN, and its equivalent convex dual as presented solved with SGD and the learning rates chosen
in Pilanci & Hrgen (2020). All problems based on test performance. We find that both the SGI) and Convex-Truncan generalization performance when adding BN, though the margin may vary depending on the problem. We also observe that the Convex BN program without truncation does not perform as well as the standard Bo-BN architecture.
programs improve in
of 5 10-7 7 CIFAR-10 and 10- 5 for CIFAR-100, while for the convex BN problem, the best performance was with learning rate x 10 10 on CIFAR-10 and x 10 for CIFAR-100.
We then compare the best results of each method in Figure 1
We that for both CIFAR-10 and CIFAR- 100, introducing a BN layer can significantly improve the performance the two-layer network architecture, both when compared the result found with SGD, and the equivalent convex formulation.
B ADDITIONAL THEORETICAL RESULTS
In this section, we present additional theoretical results that are not included in the main paper due to the page limit.
21

---

Published as a conference paper at ICLR 2022
B.1 EXTENSIONS TO ARBITRARY CONVEX LOss FUNCTIONS
In this section, we prove that our convex characterization holds for arbitrary convex loss functions including cross entropy and hinge loss. We first restate two-layer training problem with arbitrary convex loss functions after the resealing in Lemma 1.I
min ((),,((X)))) 3 w (L) AEB,
(19)
where y(,,) is convex loss function. Then, the dual of (19) is given by
max (v)
max DE
v v"BN,,, (A (A w w")) 3B,
where L is the Fenchel conjugate function defined as Boyd & Vandenberghe (2004)
(v) max z²' y).
The analysis above proves that our convex characterization in the main paper applies to arbitrary loss function. Therefore, optimal parameters for (3) are a subset of the set that includes the extreme points of the dual constraint in (5) independent of loss function.
B.2 PROOF OF LEMMA 1.1
Here, we first prove that regularizing the intermediate BN parameters and hidden layer weights don't affect the optimization problem therefore the set of optimal solutions for the problems in (20) and (22) are the same. Then, we show that (22) can also be cast as an optimization problem with & norm regularization penalty on the output layer weights WL.
B.2.1 EFFECTIVE REGULARIZATION IN
Here, we prove our claim about the effective regularization. Let us restate the training problem as follows
PL. = min- O 2
WL-1 Σ
(BNy.a
(A (A (1-
w
(1)
(L)
3 L
(1/00112
+ 11 +
+|/wool/))
2
1=1
1=1
(20)
where we 7(()) = (L) = dummy variables for notational simplicity. Now, let rewrite
20
as
2
pi. = min min min
mr-11
Σ
(A
wj
y
3
my--1
(g)
(L-11))
+ +aj + +w, (
(C-1))
+ z'
120 BE
2
2
1=1
j=l
2
L-2
s.t. Σ
|//0
2 +
(1)
2 |
[3) + //
+
After applying the scaling in Lemma paper to obtain the following problem
1.1
we then take the dual with respect to w(1) in the main
7 vll- 113 + 1 1 + 3 2¹
pi. 2 di,- = max max- 120 V
(21)
T
BNN (A (1 )) 533.
mAx BE
where O,, : (0EE: (L-1) 1)2 ta
(1-1)
=1 Vje wje(m--i1, --- (17700 1|2 +1 /w
w((-1) 1/ S1.. Since
BN,,a (A (A ((
(I, 111 (T- 2) w
(L-1)
(L-1)
1 (L-1)
+ vn
a
[I, A (1- w/
11
||2
h(P))
22

---

Published as a conference paper at ICLR 2022
where 9' denotes all the parameters except (f-11) (1-1), w(r). Then, independent of the value t, h(0") is always a unit norm vector. Therefore, the maximization constraint in (21) is independent of the norms of the parameters in 0'. Consequently, regularizing the weights in 8 does not affect the dual characterization in (2T).
Based on this observation, 20
be equivalently stated
mi
pi::ming min BEB 2
(X) - y1l2
(1-1)² + +aj + w) (1)p))
(1-1)²
(22)
2
B.2.2 RESCALING FOR & NORM REGULARIZATION IN
We first note that similar approaches are also presented in Neyshabur et al. (2014); Savarese et al. (011): Pilanci & Ergen (2020); Ergen & Pilanci (2020); ?
For any 0 O, we can rescale the parameters as 7/ 1/-11 mm (1-1) a a((-1) = =njaj n (1) Wj /nj, for any nj > O. Then, the network output becomes
11-1) and wn!)
(I, A (L-1)
fx) Σ
(1-1) + 11 (1--1)
(1)
(II, A11T)AC (L w/ (2-1)
+
(In - - (4-1)
Σ
(1-1) + 1a 1a (b-1)
w(L)
[In, - (117)
= (
which proves (X) - (x)) Moreover, we use the following inequality
(2/0-1) + azj
(1-1)²
(L) + +
(L)
V 1
11-1)
+ az a-)-1)
2
1=1
where the equality is achieved when
(1)
w
Thj 11-
11-1))
+ +o²
used. Since this scaling does not alter the right-hand side of the inequality, without loss of generality,
we can set V3, 1T- + a (I.
=1, e (m.-1). Therefore, the right-hand side becomes || [[((2)] ||
and 22 is equivalent to
1 min
EE 2 (X) y112 + 311 (1(
where θ, : (0:0))) (T-1) + a
11.-1) =1, (jE[mL-ll]
B.3 DERIVATION OF THE DUAL PROBLEM IN
Let us start with reparameterizing the scaled primal problem in (4) as
pi
min SER.
2 || -y112 + 3 w s.t. y
Σ BN
(AlL-3)
(23)
where , = (0=000);0
ta, .1.(-11) =1, Vje [mL-1]}- We now form the following Lagrangian
mL-1
L(V,8, 8, w(())= - 118 -11 v + 3 w
+ T
Σ
BNNra
(A ((-1))))
(L)
w
j=1
23

---

Published as a conference paper at ICLR 2022
Then, the corresponding dual function is
g(v)= = min L(v. V, w()))
y, S.w(L)
1 I|v 11 s.t. vT (BN,a (A <B.vje(mr..)
Hence, the dual of 23 with respect to ÿ and w(L) is
211v r1l + byll s.t. v (BN (A(L-2) SB.vje(mLa
PŻ. min max g(v) min max- RE
e v
We then change the order of min-max to obtain the following lower bound
1 - -y12 2
1
Ilyll s.t. max v (BN,.a AEe,
(( SB.
=
2
B.4 HYPERPLANE ARRANGEMENTS
We first define the set of all hyperplane arrangements for the data matrix X as
H ::=U [iign(Xw)) w WERR).
where [H| S 2nh We now define a new set to denote the indices with positive signs for each element in the set H as S: { [U,,=i h E H). With this definition, we note that given element Ste S, one can introduce a diagonal matrix ((S) E R=** defined as D(S) & == [ie SJ. Therefore. the output of ReLU activation can be equivalently written as (Xw) = ((S) Xw provided that D(S)Xw 2 0 and (I, D(S)) Xw < are satisfied. One can define more compactly these two constraints as (2D(S) I, Xw O. We now denote the cardinality of S as P, and obtain the following upperbound
E(nn 1)
P
2r
b
A=U
where r: r:=rankl rank(X)) S min(n,d d) Ojhha 2000
Winder 1966 Cover 1965). For the rest of the paper, we enumerate all possible hyperplane arrangements in an arbitrary order and denote them (D.)
Stanley al. 2004
C TWO-LAYER NETWORKS
C.1 CLOSED-FORM SOLUTION TO THE DUAL PROBLEM IN
Lemma C.1. Suppose n S. and X is full row-rank, then an optimal solution to is
(5) -I[(-))_T
(-y)
3 [[y)
1 (y) / (1 ll
(v) -3 -1K(-))/lb
(-y),
1f3>1((r) (3 ll2
11r) (-y))
(v)
(l 1l, 8> (-y)
y
1f3>1 ||, B> (-y)+
Proof. Since n 5 d and X is full row-rank, we have
max VT
[[ 1111)111
(I, 1 111 xw (1)
vn _a(1))
1
< max (1) ||2, |l (-v), l12}
max
([ }
)
h=0
||||| xواا =1
< max {1l (v), ||2. |l (-v), [12]
max | [1( 11
< max (1l (v) ||2 (-v), l12)
24

---

Published as a conference paper at ICLR 2022
where s= (7()) aw'j" and the equality is achieved when
1
l|v
1 v12
w = x (v min (v-nmnnu
|v|12
1 1
Thus, the dual problem can be reformulated
lIv yl + | s.t. max (1](v) ll,, (-v) [12] s3
max
The problem above can be maximized using the following optimal dual parameter
3 (v) - (---) 1ly)
(-v),
if ( 112
(y)+ - 33 (1(
(-y)_
if ( l1., ( 112
(v)+
(TY) (-y)+
f ()) /2, ||2
y
if (v) 12, B> (-y) ||2
C.2 PROOF OF THEOREM
For the solution in Lemma
the corresponding extreme points for the two-sided constraint are
X (y) x! (-y)+)
ff |2. (-y) l|2
w
(-y)+
if (y) 12, 81 l2
x (y)_
f (y) 12, (y) l|2
0
i || (y)
l2,, 8> (-y) ll2
and
(1)*
1
[1
11 (x)+ l2] 1 (y)+
(1) 12
1
(-
11 (-y)+ l12 (-y)+
(1)*
[y)) ll2
02 (1)*
y) lla
We now substitute these solutions into the primal problem O and then take the derivative with respect to the output layer weights w Since the primal problem is linear and convex provided that the first
layer weights are fixed (1)) we obtain the following closed-form solutions for the output layer weights
(y) 1
(1, ll2
(- 12
xx(2)*
(1--))12+2
ll2
(1 12
l2
if (8>11())1112.3>1
These set of weights, {W()** 71)** a w }. achieves p3 = therefore, strong duality holds.
C.3 PROOF THEOREM
We first note that if the number of neurons satisfies 2 m. for some m² E N, where m <n + 1, then strong duality holds, i.c., p1 = (see Section 2 of Pilanci & Ergen (2220). In the weakly regularized regime where the network interpolates the training data, there are even simpler ways to verify this upperbound, e.g., Zhang et al. (202T) show how to construct a solution that exactly interpolates the training data with m, and therefore the ReLU network fits any real valued y E Rn with n neurons.
25

---

Published as a conference paper at ICLR 2022
Following the steps in Pilanci & Ergen 2020), we first focus on the dual constraint in
7
max w(t) 7:1) +2(12
V
|| ! (117)X((11))
(In 111 X (1)
(())
+
_
1
l1
max = |8
1
v²
([Ua
Vn
VV (U's')+
||
D'
-max iE(M]
max
|='1|,=1 (2D: -T,))''220
where q:= VV=EVTW w( | 22 s:= [2(1)
s'=(100' "0'", and U':
Now, let us consider the single side of this constraint and introduce dual variable P for the constraint as follows
U Vū
'DD,''''
= max min max (v'D,U' + (2D: U
max =1,,=1 =1
KE[P]
iE[P] p20 ||=||==1
(2D: 100'
max min | V'D,U' + + (2D: 1. p2u
p20
Therefore, we have
max vT AEE.
(In 1 11 X n |[(T. - 111T)x
(0) + vn _
SB = Vie VB
min P20
|| D. + (2D I,) U11 SB SB
[il 3p, 2 s.t.
| V'D.U' + + (2D: I,) 5B.
Similar arguments also hold for the negative side of the absolute value constraint. Therefore, we can reformulate (7) as a convex optimization problem with variables v, Pc. P. ETR"" VEE and 2P constraints as follows
| D.U' (2D. 1,) 3 | + P. (2D, L,) s WiE (24)
d2 = max V.P:
2 lI --1-
1 s.t.
2
As noted in Pilanci Ergen
2020). since the problem in strictly feasible for the particular
choice of parameters Pj P.
0, V e [P]. Slater's condition and therefore strong duality holds
(Boyd& & Vandenberghe 2004).
We now write (24 in a Lagrangian form with the parameters
d5 min X.
Σ 1/
(2D, U))()
p; 20
V
f=1
X1(3 - - D,U' p (2D: L.) |
+
(25)
We next introduce additional variables r,, r E Rdd Vi E [P] to represent 25 as
d; = min
max
min
2 lv y11
+ 2
|yy12
+
Σ
No (s (''D.U'Pp (12) r;)
2
p. 2,
[ 11
i=1
P +
X 8 + D-V_D.U'' + o (2D: - I, U r.))
#=
(26)
Now, we remark that the objective function in 26 is concave in v. Pis p. and convex in r, r. Vie [P]. In addition, the constraint set for the additional variables, i.e., ||r:||2, ||r & 1, are convex and
26

---

Published as a conference paper at ICLR 2022
compact. Then, we use Sion's minimax theorem (Sion 1958 to change the order of the inner max-min problems as
1 v
d2 = min
min A.X 1
y
+ 1r + Σ
A (3 (v'D,U' - 22D. - I,) r.))
V 2.20,
2
of ||
i=1
X 8 (-v + + (2D: L,) r!)
+
(27)
Thus, we can now perform the maximization over the variables v. Pi, pl to simplify 27 into the following form
1
P2 min
min
Σ (AD.UT::XD.U1) y +
(Ae +X)
(28)
1 2 A. 20
r. 1
s.t. (2D; 20, (2D, L.) (P]
We then apply set variable changes as s = Xr, and x [Pe to obtain the following problem
Pbc min
min
Σ D,U'(s: - -y -y
+ 8 Σ (4: xX)
(29)
X.X 200s s: s ISA, 2
o |
s.t. (2D; - U,; (2D; - -,,s (P).
Finally, since the optimality conditions require ||s:||2= A and X/, write
29
as
a single convex minimization problem as
P D. Uss - 51) y Σ
P [||5:112 + ||s(
P2c min
+ B
(30)
8
2
1=1
1=1
s.t. (2D: I.) U's; 20, (2D: I,) [PE
Now, note that since 24 is convex and Slater's 's condition holds shown above, we have ph. d2- In addition, as proven in Pilanci & Ergen (220 strong duality also holds for the original non-convex problem, i.e., p1 dzz therefore, we get P2
dz
Constructing an optimal solution to the primal problem:
One can also construct an optimal solution the non-convex training problem in (6) follows
wwll
(1)*
(1)*
w
(2)*)
VI-
|
ll
87.41
[1s
+0
||
||s|1|2
||s|
(1)* (1)* (1)*
(2)
VΣ 1 1:n
||s
11
if +0.
||s
1
||s|"
112
where s/ |-m are the optimal solutions to (8) and and jas E [[7x given the definitions J1 {i:s; * 0} and Jz: = sf #0). We also note that here the second subseript denotes the selected entries of the corresponding vector, e.g., s,,.. denotes the first r entries of the vector s;. Thus, we have m - |J|
[22..
Verifying strong duality:
Next, we verify strong duality, i.e., p3 = Pp. dz by plugging the optimal solution to the non-convex objective in B and the corresponding convex objective in (30).
Given the optimal solutions {s, s{ 1 to (30). the convex problem has the following objective
P Σ i=1
P
P2.
(s; - s())
+ 3
[[|s)] ll2 + ||s] l12)
(31)
27

---

Published as a conference paper at ICLR 2022
and the corresponding non-convex problem objective is as follows
agon + w 10)
Σ P2 2 11,0,2 (X) - x112 + 2 J
(32)
We first prove that the first terms in both objectives have the same value. To do that, we compute the output of the non-convex neural network with the optimal weight construction above
m1
(In - 11 (1)*
(x,
11)
+
a
(1)*
w
[|(I,,
1171 Xw (1)
ll2
vn
j=1
Σ
Us 1,1r
||
1
1ir+1
||s
||Us
||st1|2
vn
||s
IE
Us!
|
112
sh,r41
Σ
||s 11
|US| 12
||s 113
n
||
112
iEda
Σ (U'st)+
Σ (U's!)
IE
iET2
P
Σ
D, -
(33)
i=1
where the last equality follows from the constraints in (30
Next, we prove that the regularizations terms have the same objective follows
3
m1
+ [
(2)
Σ
||st
s1.+1
(115711)) 11
2
2
||s:
||s:
j=1
JEJ
1
Σ
+ (-11st 11
2
||s
||s 11
SEJ2
8
||st
+ +|ss|ll
2
||s:112
|| ll2
IET1
||s%.1..r 11
+
Σ
+ ||s]" 112
+ ||s/ ll2
2
||s |12
iEJ2
B
Σ
||st|le +
Σ
||s|" ll2
iET
<E.T2
P
B
(1|s
+ ||s]" 112)
(34)
Therefore, by 33 and 34), the non-convex objective 32 and the convex objective 31 are the same, i.e., P5 Pie
C.4 PROOF OF LEMMA 2.1
We note that similar approaches are also presented in Sahiner et al. 202la): ?
28

---

Published as a conference paper at ICLR 2022
For any 0 6 rescale the parameters 7/0
0j -11
(1)
=m (1) and w /nb.
for any fi > 0. Then, the network output becomes
m11
(In 111") Xw
(1) +1a mo(e)"
fā.
Σ
|1 ! 1117) (1)
m
(In - - Xw
(1)
|[ -11)) (1)
= 2 (X),
which proves fa,2(X) = f0,2(X) (X). Moreover, we use the following incquality
(1) + +af + -|1
w 3 lellll/33 Vg00 +ap (1)
2
where the equality is achieved when
(2) W
(1)² + (1) 2
7g
used. Since this scaling does not alter the right-hand side of the inequality, without loss of generality,
we can set / (1) +aj
(1) =1 Vj [m)]. Therefore, the right-hand side becomes Σ/ (2)
We then note that due to the arguments in Appendix B.2.1
we can remove the regularization on w) without loss of generality. Therefore, the final optimization problem is as follows
1 (l,,,((X) - +
W (2)
P2. = min 8ee, 2
where O, : (0=: (1) +a =1, VjE (m1)}
(12
C.5 PROOF OF THEOREM
We first note that if the number of neurons satisfies m, 2 m for some mn E N, where m <nC + 1, then strong duality holds, i.c., pa, di (see Section A.3.1 (f et al. (2021a) for details). Following the steps in Sahiner et al. (202la) and Theorem 2.2 we again focus on the dual constraint
(In 1 Xww 7(0) + [[ -
(1)
VT (LUa
J.2 }
max wil 01 +
max
vn
I1qll,=
-|
+
(VV((U's')4))
max ||='||==1
g gVV" (U's')
max
|||||=-||<||
g TVVDD,''
-mx <E[P]
max
|| ||B||,=||
(2D; U''20 20
Vv.,U's''")
maxx <E[P]
max |
|
(2D,-L.U''sS
max max rE[P] SEK,
VVD,U'S).
29

---

Published as a conference paper at ICLR 2022
where s' [pq a] u'= U | and con= (2D - 1,)''''0 |2||
1.. Thus, we have
V
I [1(1, 11 X Vn
(I, 11 x (1)
(1) _
13 s3 28, (V,
max 0
Similar arguments also hold for the negative side of the absolute value constraint. We then directly follow the steps in (Shhnner al. (2021a) and achieve the following convex program
min S, 2
Σ i=1
D,U' - Y +
S lel
where
Is = min s.t. S (T;
120
denotes constrained version of the standard nuclear norm.
C.6 PROOF OF THEOREM 2.4
We first restate the dual problem as
max- -V-
| s.t. max ||=|||==1
V
(U's)) 111
(35)
where we use the results from Theorem 2.3 modify the dual constraint. Since Y is one-hot encoded, 35 can be rewritten as
max
2 IV
Y
1 +
Y s.t.
max 1
|
u S.S.
(36)
This problem has the following closed-form solution
Y; B
if 3 otherwise
Ty
Vje[C].
(37)
Yj
and the corresponding first layer weights in (36
are
X
if 3 otherwise
VjE
(38)
Now let us first denote the set of indices that achieves the extreme point of the dual constraint as ::= (i: 8 J Then the dual objective in (36) using the optimal dual parameter in
d2.
YI2
+
Y
2
2
1 Σ
(B 1|5,112)
+
1
Σ
1,,
2
2
JEE
==1
} 82
+ 3 Σ
||salla
Σ
(39)
2
JEe
joB
We next restate the scaled primal problem
P2.
min e
2 (I, 111 Xw
1
Σ
(1)
1
(1)
w
12)
Y
m1
[II - 11
11
Vn
+
(40)
30

---

Published as a conference paper at ICLR 2022
and then obtain the optimal primal objective using the hidden layer weights in 38 following optimal solution
which yields the
(1)
200)
{
(Xly,, yj: (11y,112- - 3)
(xl
if 3
w
otherwise
(41)
(
1
|ly; 111
(1)*
lyy, l22
1
aj
Vn
We now evaluate the primal problem objective with the parameters in (41) which yields
(In 1111") Xw (1)*
P5u
1
3
(1)*
(2)*
w
(2)+
Y
w (2)*
2
||(In ! 11 Xw (1)
112
vn
n
2
1
Σ
(lly 3)
y, e7 Y
(lly - 3)
2
|yy 1l
JEE
JEE
1
Σ
jj
6
T
2
1
Ily
P + B Σ
Iy,ll2 - 3
2
lyy
112
2
JEE
JEE
jE8
1
1
1
Σ
1155112
Σ JEE
lyy, 1l2.
(42)
2
J&C
which is the same with (39). Therefore, strong duality holds, i.e., pá. -2 and the layer weights in optimal for the primal problem (40)
D CONVOLUTIONAL NEURAL NETWORKS
D.1 PROOF OF THEOREM 3.1
Following the arguments in Theorem 2.2 and Ergen & Pilanci (2021a), strong duality holds for the
CNN training problem in 13 i..., p2c- d2c. and the dual constraint can be equivalently written as follows
K
max
Σ
V
X - 111
7(1
Vnk la
7 2) 133
k=1
R' =1 |x - -1el
(LnK
nk
1 11 M2 (2)
1
a (1)
max BEE,
[[nK n 11 (1T)M2l12
Vnk
+
V ([UNa
max
vnk
||q||,- ||8||2
(U'ss'))
max
| |=
K
T (U )
max
|=1||==1
1=1
max RE[P]
Σ v D c
U Unss'
*|1,=1
(2D,: I.. 8'2000 20
where C:= 17
X L. M = X1i X2i
... Xx). and we use the following variable changes
q: EM VT
Ar 2
8: (7() a')]" T
s':= s'= any?, and U
Un+==
UM
vRk
[U'm U UM.....
U M
31

---

Published as a conference paper at ICLR 2022
Then, following the steps in Theorem 2.2 and Ergen & Pilanci (2021a), the equivalent convex program for 13 is
Pe K
Pa Mk(q: - -96 +
min 9:
Σ
U
(111 + (1((122
2
1= k=1
1=1
s.t. (2 L.) 20, (2D - I, I,) 20, vie
E
THE IMPLICIT REGULARIZATION EFFECT OF SGD ON BN NETWORKS
PROOF OF LEMMA 5.
We start with the following non-convex training problem
Σ
mi
BN,,a (x)
w (2)
m1 2
(1)
+a
+ [w]
P22 = min-
WEE
j=1
where we note that hidden layer weights are not regularized without loss of generality due to the arguments in Appendix B.2.1 Now, consider the SVD of the zero mean form of the data matrix We can thus equivalently write the problem as
(In -11 UEV
UEVT (1)
(1)
(1)
(1) +
taf
P52 min 8EB
+
UEVT 1
1l2
vn
j=1
Now, simply let q, = EVT w. Noting that Uq;l12= 1|gg12=11;;,1zz we arrive at
Σ
Uq
1
ag)
(2)
(1)
(1)2 (1)2
(2) 2 [j
P52 P7
min DEE
2
q 2
+
vn
w
Y
+
2j
+ +aj
+
j=l
F
E.2 PROOF OF THEOREM 5.1
When solving 9 with GD, we have the updates
(() (1)(++1))
w
Th V
()) C(F (X), Y)
a (M)+1
=a, (2)(1))
V
C( (X), Y) + Ba
n (1)((++11) -000)(4)
7k V
Y) + (n
w (2)()+11))
-w( (2)
Th V w ()), Y) + (w
32

---

Published as a conference paper at ICLR 2022
Now, let D = d (1)
20]] R(() (k) = - 1== BN (xw()(at)
w/ (2)(
Y be
the residual at step k, and X = (I, - Then, with squared loss L, we have the following:
X
7/ (2)(()
(k)
un (() Y)
(K) X
R ( (2)(())
1X (o ()(
112
2,00(00)
(1) T
(D (k) x0)
R (k) W ()(())
) X xw)
\ (1)(
V 21 (X), Y) = - (w (2)
R
D
(k)
1
200 (X), Y)
1
W
(2)
D (h)
x
w (
1x (2)
(A)
1/2
we Y) = R (N) T //0///
(1)
vn 0 (1)
1
(1) (N)
12
To express the updates in qy-Space for w (1) we can compute
A (k)
VV
() ((f Y)
22
(2)
(1)
E R (K) (2)
(1)
x
D
R
(k) w (2)(0))
U x x (o (1)
1X (1)
112
Now, we consider solving
16
with GD. We assume that all weights are equivalent to those in I... i.e.
ΣVT w (R) In this case, the gradients are given by:
1 (X) = 1 (X), and
q (k)
(R)
(1)(1))
V. C(ft22 Y) = |
7
U)
R (3)(K)
9 (b)
U)
R (k) w (1)))) ), (R)
1
00 L(F222 (X), Y) = - (b)
R (N)
D (k)
1
30 2( (), Y) |1 12
w (R)
R T
D
(b)
Uq, (K)
w/ L(102 (X), Y) = R T (b)
Uq (K)
(4)
1
a ())
Vnu
|q (1)
Simplifying, we have
(1)
7 (()(())
A
(A)
7i
U
D.
(k)
R (4) m
(2)
4 (N)
UTD (k) R (
) (A)
22b
l
(b0
2
l1
Uq, (H), and thus that | (1) (K)
Now, noting that X" desired,
112=119 12 we can find that, as
A (b)
22b,j (R) (R)
L(f (X), Y) = V 7, (1)
V a L(St (X), y,,Y=va =
-V
L(S:20 (X), Y) = V L())
33

---

Published as a conference paper at ICLR 2022
F DEEP NETWORKS
F.1 PROOF OF THEOREM
Applying the same steps in Theorem 2.1 for the data matrix A (4-2), i..., replacing X with A (1--2)
yields the following optimal parameters
2)) (y)+ A (L-2)) 2) (-x)+)
(1 112
way
A 2) (-y)+
A 114-2) 2) (y)+
(1)_,,, (1)=11,,,>>((>>) ll2
1|
0
if
[] (y) 11 (y)+ 112]
(1)
(-
1 111 (-y) l12)
"T (y)+
72
2 (-y)+
(1)*
(yy+
(1)*
((-)) 11a
vn
02
(y) 112 8
if 11,. 35 (-y) 112
[1 (-y)+ 112 + 8
(2)
|1 (-y), 112 + 8
1/2
1y)+
1,0_(0)),,,,>>1->),, ||2
110=100,,1,,>>1((<>,, lla
8 [( 2 1 (-9)+
(y)
(123)(()),]//33(((>)])) ll2
(y) 3 (-y)-
192 ll2
(v)
[(y) lE (-y)+
1b) if (1 8> 8> (-y) ll2
y
3 11 (y) 12, >> 11 (-y)+1l ll2
We now substitute these parameters into the primal 33 and the dual (5) to prove that strong duality
holds. For presentation simplicity, we only consider the first case, i.e., 5 SSll (y)+ ll2, 8 (-y), ll
and note that the same derivations apply the other cases as well. We first evaluate the primal objective with these parameters as follows
(I, 2.4 1117) (T.
(1)
1
(1)*
(1)*
w
p1-
[111 1 A (1-1)"
112
Vn
y
+ 3
2
1
(-y)+ (y)+ + - [|[-)]]]]
-3
+ +B(1(()+112 + 11(-))+11 -1/)
2
[|(x)]
=
=((( + ||(-y)+1lg) - 8².
(43)
We then evaluate the dual objective as follows
--=-111 1/ y12 - 11y111
di =
1
(y)+
88 (-y)+
y 2
B
|rl
2 [1((), 1l2 || (1-y)) + lll
= - + ((1l6) + (-1(-r))41g 111))
(44)
By 443 and 44). the set of parameters (W(+-1)",, (1-11)"" (T-1 " achieves pi di therefore, strong duality holds.
34

---

Published as a conference paper at ICLR 2022
F.2 PROOF OF THEOREM 4.2
Applying the same steps in Theorem 2.4 for the data matrix A (4-2), i.e., replacing X with A (4-2) yields the following set of parameters
w (1-1)) w
A (A(L-2)
yJ. (1ly;1l2 B)0s))
if 3 12
otherwise
(1-1))
[yy,
111 y
VjE(C]-
h (1-1)*
|
Vi
if B S 1lysl2
Tyylla yj
otherwise
G BN AFTER RELU
Despite the common practice for BN, i.e. placing BN layers before activation functions, some recent studies show that applying BN after activation function might be more effective (Chen et al. 2019). Thus, we analyze the effects of BN when it is employed after ReLU activations.
After applying the scaling in Lemma
I.1
the primal training problem is as follows
min OE
Σ yN
mi
((xw!")
w (2)
y
+ 31 w (2) 1|1-
(45)
2
In the sequel, we repeat the same analysis in Section Theorem G.I. For any data matrix X, the non-convex training problem in (45) stated as the following mnite-dimensionll convex program
can be equivalently
min 1 8.18
(2D; I,, XV
E Si, 20
Σ U'(s. 5/
s.) - 3 Σ (1|s:]12 [1s( s.t.
Vi
2
(2D: I, Σ S 1 20
(46)
provided that (I, (U- U.: U, n.
and -1,1:;;1 denotes all the entries of except the last one.
Theorem G.2. Suppose d and X full row-rank, then an optimal solution
45 given as
(w("), -
min vs). (lyy B)+.) = (xi((
1y
111 y ll
lyyla
y
These results indicate that applying BN after ReLU leads to completely different phenomena. Specifically, Theorem G.T shows that the hyperplane arrangement matrices D,X are de-meaned and whitened via SVD, namely (I, 111" DD = U,E, This renders whitened features
h U U, 1/v appearing in the convex model. This contrast with applying BN before the ReLU layer, which directly operates on the data matrix X.
Theorem G.2 shows that an optimal solution can be found in closed-form in the high-dimensions regime < d when X is full row-rank, which is typically satisfied in sample- limitedd scenarios. Surprisingly, a single neuron optimizes the training cost, which corresponds single non-zero block in the group ε penalized program 446).
G.1 PROOF OF THEOREM G.2
Applying the approach in Lemma C.1 to the following constraint
(I, !11") (Xw())_
7(1) + a (') 1
max 8
[I, 1117) (Xw(1), l12
/n
35

---

Published as a conference paper at ICLR 2022
yields
Then, the rest of proof is to verify the solutions by substituting them into the primal and dual problems as in Theorem 2.
G.2 PROOF OF THEBREM
We first focus the dual constraint as follows
v (I, - 11117) (Xw(1)) 700) + a1)) v'1
max w 703
11 - (Xw(l)) 112
vn
+a
v (I, 11 D.X
+ a1l) v
max sE[P]
max DE
[In D,
(2D; I,, Xw. 20
U.q. 1
max
max
vT
7 +
av
T
:E[P]
9.9.7
Vi
+7
(2D. 10Q-1,VV,3 4.20
max
max
V
U
vn
=E
(2D. L... -1:
Then, the rest of the proof directly follow from Theorem
2.2
36


Reviews:
[{"review_id": "kzQBr-PLZbw", "reviewer": "Reviewer_pM4k", "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": "Overall I think the results presented in this work are solid and interesting.\n\n**Pros**:\n\n- The paper is well-written and the theory developed is solid and well-organized.\n\n- The author(s) provided a quite comprehensive study (scalar output, vector output, feed-forward NN, convolutional NN, implicit regularization of SGD with BN) of batch normalization from the lens of convex duality.\n\n- Experiments are also quite complete and well-designed.\n\n**Cons**:\n- Missing related work: [1, 2], and maybe some other subsequent papers that cited these works.\n- In Theorem 2.2. $P$ grows exponentially, the convexity does not come free. Transforming a nonconvex problem into a convex problem by introducing more variables (exponential growth) has appeared in the literature of optimization. It might be worth mentioning this point. Also in the abstract, the author(s) stated that the exact convex dual problem can be solved in polytime. Is this statement really true given that you introduced exponentially many variables?\n- In Theorem 2.2 (exact convex dual), our variables are $s_i$'s. How can we get the $W_i$'s from $s_i$'s (primal recovery)? This question is just from my curiosity, and it will not affect my rating given that this paper is studying the property of BN instead of proposing a practical algorithm.\n- For the implicit regularization part. Assume that SGD with BN is converging to $w^*_{BN}$ and SGD without BN is converging to $w^*_{noBN}$. Then can the analysis in Section 4 give us the conclusion that $w^*_{BN}$ is ''better'' than $w^*_{noBN}$ according to some kind of regularization condition? The conclusion from Section 4 is a little bit vague and I think the presentation of that part can be improved.\n\n\n[1] Santurkar et al. How Does Batch Normalization Help Optimization? NeurIPS 2018.\n\n[2] Arora et al. Theoretical analysis of auto rate-tuning by batch normalization. ICLR 2019.", "summary_of_the_paper": "The author(s) presented a quite comprehensive theoretical study of batch normalization from the lens of convex duality. Numerical experiments are also conducted to support the theoretical analysis.", "summary_of_the_review": "Overall I think the results presented in this work are solid and interesting. There is some missing related work, but I think it is fine since the results in this paper have no significant overlap with the existing results. I did not check the proofs in this paper in detail.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "SG8ACHEO11", "reviewer": "Reviewer_YR4A", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The contribution of the paper is to show that regularized ReLU networks with batch normalization can be equivalently stated as convex problem. While there has been some related work investigating the benefits of batch normalization on neural network training, the present work provides a theoretical characterization for training deep networks with batch normalization.\n\nMoreover, the paper provides an alternative algorithm via a convex program which is shown to perform well compared to the standard non-convex optimization. Since batch normalization is widely used in practice, this result may be of great interest to the community. Therefore I vote for acceptance.\n\nAs a minor remark, I found the structure as well as the headings of Section 4 a bit misleading, since first one gets the impression that its purpose is to point out a property of SGD applied to the BN network, while in fact its goal is to fix a weakness of the proposed approach, namely that it tends to generalize poorly. Maybe this could be made more explicit, in particular also reflected in the heading of the section as well as the discussion in the introduction. Furthermore, maybe the ordering of the sections can be improved. Currently Section 4 is placed between the two sections about the extensions to CNNs and the extension to the L-layer case. The flow of the paper could be improved by first covering the extensions to different architectures and then discuss the regularization issues (or the other way round). Moreover, throughout the paper, the abbreviations SGD and GD are used interchangeably.", "summary_of_the_paper": "The paper studies batch normalization in deep neural networks. For a two-layer network with scalar output and batch normalization, a dual of the problem is derived. It is then shown that in the high-dimensional regime, the dual can be further simplified so that an optimal solution can be computed in closed form. In the general case, the concept of hyperplane arrangements can be used to formulate an equivalent finite-dimensional convex program which can be solved in polynomial time. \n\nThe analysis is then extended for vector output networks and different architectures including L-layer neural networks and CNNs. It is then shown that the convex problems tend to fit low singular value directions which will lead to poorer generalization. As a remedy, the authors propose a truncated variant of the problem by obtaining a low-rank approximation of the data.\n\nIn the experimental section, it is shown on the CIFAR-100 dataset that the closed form solution leads to superior results compared to the solution obtained by gradient descent. Moreover it is shown that the truncated variant of the approach is needed to achieve a good generalization performance.", "summary_of_the_review": "Overall, despite some flaws in presentation, I think the paper poses a meaningful contribution which warrants acceptance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "8AvLAGLGqpU", "reviewer": "Reviewer_syyN", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "It is crystal clear that a polynomial-time training algorithm for neural networks (with or without BN) is a breakthrough in machine learning. Yet, we need careful proof checking for this strong claim. I am lost in the notations and the proofs. I kindly request the author to help me to proof check the result. \n1. What is the difference between $W^{(1)}$ and $w^{(1)}$ in equation 7? What are the dimensions of $y$? Why problem (7) is easier than (6) to solve? (7) has a non-convex constraint. \n2. Intuitively, I do not understand why dual with respect to the output weights may make the original non-convex program easier. The original problem is convex w.r.t the output weights. We can compute the optimal output weights in closed form. But this is not helpful for convexifying the objective. \n3. What authors do mean by $\\mp$ in Theorem 2.1?\n4. For a sanity check of Thm. 2.1, consider $\\beta=0$. Using Lemma C.1., one can check that $d_2^*=0$. But, it is easy to design input for which $p_2^* >0$. Why does this sanity check fail? Did I misunderstand the results?  \n5. Does Theorem 2.1 imply that all the $w_j^{(1)}$ are equal? \n6. Recall inequality $P = O(r (n/r)^r)$. If $r=n$, then $P=(n)$? I think this can not be true and $P$ is at least $O(2^n)$. \n7. The proof of Thm 2.2. is not clear. Would authors please add the complete proof instead of \"directly\nfollow the steps in Pilanci & Ergen (2020)\". \n\n", "summary_of_the_paper": "The claim of this paper is casting training neural networks with batch normalization to a convex program solvable in polynomial time. The convex reduction sparks an implicit regularization of batch normalization. Taking inspiration from the convex program and the implicit regularization, the authors improve BN. ", "summary_of_the_review": "If this result is correct, it would be a breakthrough in machine learning. Yet, we need to make sure the proofs are correct. The current version is a bit difficult to read and check. Notations are not introduced well and the proofs are referring to other recent results. I recommend authors make a self-contained paper.  I also need the author's responses on my failed sanity check to understand the proof better. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors rely on the recent convex formulation of neural network training to establish an interesting correspondence between whitening of input data and batch normalization (after and before relu). While convex formulation is not scalable to realistic architectures, it is a great insight that would add value to our understanding of the batch normalization tool.
Decision: Accept (Poster)