Revealing the Structure of Deep Neural Networks via Convex Duality
Authors: Tolga Ergen
Mert Pilanci
Venue:  (2021)
Keywords: Convex optimization
non-convex optimization
deep learning
convex duality
regularization
ReLU activation
linear networks

Abstract: We study regularized deep neural networks (DNNs) and introduce a convex analytic framework to characterize the structure of the hidden layers. We show that a set of optimal hidden layer weights for a norm regularized DNN training problem can be explicitly found as the extreme points of a convex set. For the special case of deep linear networks with $K$ outputs, we prove that each optimal weight matrix is rank-$K$ and aligns with the previous layers via duality. More importantly, we apply the same characterization to deep ReLU networks with whitened data and prove the same weight alignment holds. As a corollary, we prove that norm regularized deep ReLU networks yield spline interpolation for one-dimensional datasets which was previously known only for two-layer networks. Furthermore, we provide closed-form solutions for the optimal layer weights when data is rank-one or whitened. We then verify our theory via numerical experiments.

Under review as a conference paper at ICLR 2021
REVEALING THE STRUCTURE OF DEEP NEURAL NET- WORKS VIA CONVEX DUALITY
Anonymous authors Paper under double-blind review
ABSTRACT
We study regularized deep neural networks (DNNs) and introduce a convex ana- lytic framework to characterize the structure of the hidden layers. We show that a set of optimal hidden layer weights for a norm regularized DNN training problem can be explicitly found as the extreme points of convex set. For the special case of deep linear networks with K outputs, we prove that each optimal weight ma- trix rank-K and aligns with the previous layers via duality. More importantly we apply the same characterization to deep ReLU networks with whitened data and prove the same weight alignment holds. As corollary. we prove that norm regularized deep ReLU networks yield spline interpolation for one-dimensional datasets which was previously known only for two-layer networks. Furthermore, we provide closed-form solutions for the optimal layer weights when data is rank- one or whitened. We then verify our theory via numerical experiments.
INTRODUCTION
Deep neural networks (DNNs) have become extremely popular due to their success in machine learning applications. Even though DNNs are highly over-parameterized and non-convex, simple first-order algorithms, c.g., Stochastic Gradient Descent (SGD). can be used to successfully train them. Moreover, recent work has shown that highly parapparamtterieed networks trained with SGD obtain simple solutions that generalize well (Savarese et al. 2019 Parhi & Nowak 2019; Ergen & Pilanci| 2020a b). where two-layer ReLU networks with the minimum Euclidean norm solution and zero training error are proven fit linear spline model in ID regression. Therefore, regularizing the solution towards smaller norm weights might be the key to understand the generalization properties of DNNs. However, analyzing DNNs still theoretically elusive even the absence of nonlinear activations. Therefore, study norm regularized DNNs and develop a framework based on convex duality such that a set of optimal solutions to the training problem can be analytically characterized.
Deep linear networks have been the subject of extensive theoretical analysis due to their tractability. A line of research (Saxe et al. 2013] Arora et al., 2018a Laurent & Brecht 2018 Du & Hu 2019
Shamir 2018) focused GD training dynamics, however, they lack the analysis of generalization
properties of deep networks. Another line of research (Gunasekar et al. 2017 Arora et al.) 2019
Bhojanapalli et al. 2016) studied the generalization properties via matrix factorization and showed that linear networks trained with GD converge to minimum nuclear norm solutions. Later on, Arora al. (2018b): Du et al. (2018) showed that gradient flow enforces the layer weights to align. Ji & Telgarsky (201)) further proved that each layer weight matrix is asymptotically rank-one. These results provide insights characterize the structure the optimal layer weights, however, they re- quire multiple strong assumptions, e.g., linearly separable training data and strictly decreasing loss function, which makes the results impractical. Furthermore. ZZang et al. (2019) provided some char- acterizations for nonstandard networks, which are valid for hinge loss and specific regularizations where the data matrix is included. Unlike these studies, we introduce a complete characterization for the regularized deep network training problem without requiring such assumptions.
Our contributions: 1) We introduce a convex analytic framework that characterizes a set of optimal solutions regularized training problems the extreme points of convex set, which is valid for vector outputs and popular loss functions including squared, cross entropy and hinge loss 2) For deep linear networks with K outputs, we prove that each optimal layer weight matrix aligns
"Extensions other loss functions, e.g., cross entropy and hinge loss, presented Appendix A.1

---

Under review as a conference paper at ICLR 2021
Numpen
Width (m)
Depth (L)
Vector outputs (K)
Savarese et al. [2019]
2
X(K = 1)
Parhi & Nowak (2019
DO
2
X(K = 1)
Ergen & Pilanci [2020a] b
finite
2
X (K =
Our work
finite
L
/ (K 2
(Dus))
De
Figure & Table One dimensional interpolation using L-layer ReLU networks with 20 neurons in each
hidden layer. As predicted by Corollary 4.2 the optimal solution is given by piecewise linear splines for any
L 2 2. Additionally, we provide a comparison with previous studies about this characterization.
with the previous layers and becomes rank-K K via convex duality; 3) For deep ReL.U networks, we obtain the same weight alignment result for whitened or rank-one data matrices. As corollary, achieve closed-form solutions for the optimal hidden layer weights when data is whitened or rank-one (see Theorem 4.1 and 4.3) As another corollary, we prove that the optimal networks are linear spline interpolators for one-dimensional, i.e., rank-one, data which generalizes the two-layer results for one-dimensional data in Savarese al. (2019); ; Parhi & Nowak (2019); Ergen & Pilanci (2020a]b) to arbitrary depth. We note that the analysis of ReLU networks for the one dimensional data considered in these works is non-trivial, which is a special case of our rank-one/whitened data assumption.
Notation: We denote matrices/vectors as uppercase/lowercase bold letters. We use 0g (or 1;) and L to denote vector of zeros (or ones) and the identity matrix of size k, respectively. We denote the set of integers from 1 to n as [n] To denote Frobenius, operator, and nuclear norms, we use II- |l, -I ll2. and ||+, respectively. Furthermore, mmax(+) and Jmin (-) represent the maximum and minimum singular values, respectively and Bg is defined as B2 == {u E Rd ||u|| 1}.
1.1 OVERVIEW OF OUR RESULTS
We consider an L-layer network with layer weights Wi E M VI E [L], where mo d and my = 1, respectively, Then, given data matrix X E Raxd the output is fx, = AL-1WL, A; - Wi) VI E [L- I], where Ag = X and g(-) is the activation function. Given a label vector y E IR,, training problem can be formulated as follows
min L(fe,L(X), + BR(O), (0:)=1
where L(.,-) is an arbitrary loss function, R(0) is regularization for the layer weights, ,3 > 0 regularization parameter, 0, = (Wa, mr). and := {0. In the paper, for the sake of presentation simplicity, we illustrate the conventional training setup with squared loss and nn-mr regularization, i.e., (()o_
fo y1 and R(0)) Ets | However, our analysis valid for arbitrary loss functions and different regularization terms as proven in Appendix. Thus, consider the following optimization problem
P min ((fe.(X),)) + 3 (0:)
w
Next, we show that the minimum &j norm is equivalent to minimum & norm after a rescaling. Lemma 1.1. The following problems are equivalent:
min
[(Jo,(XX. + 23 wr + 3(L 2)1²
min ( + Σ W (0:)
(0
s.t. WL-1J B2, |Will St, W [L - 2]
where 1.j denotes the jth column of WL-1-
Using Lemma 1.1 we first take the dual with respect to the output layer weights wy and then change the order min-max to achieve the following dual deep network training problem, which provides a lower bound 3
p >D" min max
min
-C* + B(L 2) s.t. ||Ab_>//oo 23.
W Wi-11 BB, |willsst vlE[L-2]
"The proof is presented in Appendix A.3 For the definitions and details see Appendix A.1
2

---

Under review as a conference paper at ICLR 2021
To the best of our knowledge, the above dual deep network characterization is novel. Using this result, we first characterize a set of weights that minimize the objective via the optimality conditions and active constraints in the dual objective. We then prove the optimality of these weights by proving strong duality, i.e., p = D" for deep networks. We then show that, for deep linear networks with K outputs, optimal weight matrices are rank- K and align with the previous layers.
More importantly, the same analysis and conclusions also apply to deep ReLU networks with K outputs when the input is whitened and/or rank-one. To the best of our knowledge, this the first work providing a complete characterization for deep ReLU networks via convex duality. Based on this analysis, we even obtain closed form solutions for the optimal layer weights. As a corollary, we show that deep ReLU networks fit a linear spline interpolation when the input is one-dimensional dataset. We also provide an experiment in Figure [ to verify this claim. We emphasize that this result was previously known only for two-layer networks (Savarese et al.) 2019 Parhi & Nowak 2019 Ergen & Pilanci 2020a b) and here we extend arbitrary depth (see Table | for details).
WARMUP: TWO-LAYER LINEAR NETWORKS
To illustrate an application of the convex dual D", we consider the simple case of two-layer lin-
ear networks with the output (X) XW W2 and define the parameter space 0 O
{(W,, W2,
W1 E Rdxm
W2 RT
Z,)) }. Motivated by recent results (Neyshabur al.
2014 Chizat & Bach 2018 Savarese et al. 2019 Parhi & Nowak 2019 Ergen & Pilanci 2020a
first focus on minimum norm variant of equation when (()o,((X),,
[ (X) y
and then extend it to equation I
The minimum norm primal training problem can be written as
min KEB
| ||2ll2 s.t. f0,2(X) =
Using Lemma A. we equivalently have
p = min w2lli s.t. Sa,2(X) = wis E B2, Vj,
(4)
AED
which has the following dual form.
Theorem 2.1. The dual of the problem in equation f is given by
P D = max X
y s.f. max
X $1.
(5)
XER
wiEB,
For finite width networks, there exists a finite m such that strong duality holds, i.e., P = D*, and an optimal for equation 4 satisfies ((XWi) 11 = where X" is the dual optimal parameter.
Using Theorem 2.1 we now characterize the optimal neurons as the extreme points of convex set.
Corollary 2.1. Theorem 2./ implies that the optimal neurons are extreme points which solve the following problem arg max EB, |A- Txw1
Definition 1. We call the maximizers of the constraint in Corollary 2.1 extreme points.
From Theorem 2.1 we have the following dual problem
max X s.t. max X 1. w,EBz
(6)
Let X U.E.V VT be the singular value decomposition (SVD) of X If we assume that there exists w such that Xw = y due to Proposition 2.1 then equation 6 is equivalent to
max V'Ew" s.t.
Σ X 2
<
X
where A = U and w
VT wt Notice that in equation
7 we use an alternative formulation 1 instead of X < 1, tw, E B3 since the extreme point
for the constraint, i.e., |X
achieved when W1 X
X
2ll. Given rank(X) = r min (n, d]. we have
XTE, w = -T'
I
Oxxd-r
2 w 1|2
[Wlll,,
(8)
0 Od-rxr
Od-rxd-r
"This corresponds to weak regularization, ie.. 3 in equation 'All the equivalence lemmas and proofs are presented in Appendix A.3 IIn this paper, we use full SVD unless otherwise stated.
(see e.g.
Wei al.
2018
3

---

Under review as a conference paper at ICLR 2021
which shows that the maximum objective value is achieved when ΣT C1 W. Thus, we have
V V V.W:
Pxr(w")
w
IV where Px (.) projects its input onto the range of X". In the following results, we show that one can consider a planted model without loss of generality and prove strong duality for equation
well 1xxx (w*)
Proposition 2.1. (Du & Hu 2 Given w arg minw ||w y1l2, we have
arg min IXWiw2 Xw"ll arg min |X Wi W2 - -y12
W1
Wi.2
Theorem 2.2. Let y be feasible for equation networks.
then strong duality holds for finite width
2.1 REGULARIZED TRAINING PROBLEM
In this section, we define the regularized version of equation 4 as
min 8EB
(X) y1l B|[wa]l WiJ B2, Vj
which has the following dual form
|| yl
1yl1 s.t. max
xx S.B.
wiEB,
Then, an optimal neuron needs to satisfy the condition
w X"Px.3(y)
|XTPx,syyll
where Px,e(1 projects its argument to {u R" equation 9
|X u112 S B}. We now prove strong duality for
Theorem 2.3. Strong duality holds for equation 9 with finite width networks.
2.2
TRAINING PROBLEM WITH VECTOR OUTPUTS
Here, the model is Sa.2 ())
XW,W, W to estimate Y E |R which can be optimized as follows
min 0ee
W 1 + W2ll s.t. fa,((X) Y.
(10)
Using Lemma A.2
we reformulate equation 10 as
min
Wa,ill s.t. (x, wi. B2, Vj.
(11)
BEB
which has the following dual with respect to W2
max trace(A" s.t. | 1, Vwi E B2.
(12)
A
Since we can assume Y XW" due Proposition 2.1 where W Raxk we have
trace(AU, trace( YY) trace (A XW*) trace (AU, E, W S Omao (A U
W
||
(13)
where Tman XX < due to equation
and W
I
Oxxd-r Od-rxd-r
V2 W* Given the
Od-rxr
SVD of W ie., U, En V choosing
A V
Inw
Orwxd-rw
UT
Ox Ox-raxra
OK- Xd-ru
achieves the upper-bound above, where rur rank(W;;. Thus, optimal neurons are a subset of the first Tw right singular vectors of AXX. Moreover, the next result shows that strong duality holds.
Theorem 2.4. Let (X, Y} be feasible for equation then strong duality holds for finite width networks.
4

---

max Under review as a conference paper at ICLR 2021
2.2.1 REGULARIZED CASE
Here, we define the regularized version of equation [1
follows
min 1 = [x,) YI + 3 SEB
m
Σ
Wesll2 s.t. wis E B2, Vj.
==1
which has the following dual with respect to W
YI -
|Y|| s.t. o ( (A"X) S B.
A
Then, the optimal neurons are a subset of the maximal right singular vectors of (Y),,, where (.) projects its imput to the set {U E Ra*k] |maz mmmozU'XX) S 3}.
Remark 2.1. Note that the optimal neurons are the right singular vectors of Px (Y) that achieve the upper-bound of the set, Le., (Px,,(())Xw(lll = B. where || = 1. This implies that the optimal neurons satisfy \|Y Xxwilll Kwill2 2 3. Therefore, the number of optimal neurons and the rank of the optimal weight matrix, i.e., Wi, determined by B.
Remark 2.2. There might exist optimal solutions other than the right singular vectors of Px. (Y) 1)"X. X. As example, consider u₁ and U2 as the optimal right singular vectors. Then, any 01 + O2 with of + +0 also achieves the upper-bound, therefore, optimal.
DEEP LINEAR NETWORKS
We now consider an I--layer linear network with fo. XWI... Wz, and the training problem
P min (0:)
Σ
Will s.t. (x, =
(14)
Proposition 3.1. First L 2 hidden layer weight matrices in equation 14 have the same operator 2- where t = |Willr [ill2, vI E [T. - 2).
and Frobenius norms, i.e., t = 122
Theorem 3.1. Optimal layer weights for equation
14 satisfy the following relation
t V. W pT
ifl=1 =
Wi
t P1 f
PI.-2 i
where |p:|12 = 1, V [L 2] and follows the definition equation
This result clearly shows that the intra-layer weights need satisfy an aligment condition. The next theorem shows that strong duality holds in this case.
Theorem 3.2. Let y be feasible for equation 14 then strong duality holds for finite width networks.
Corollary 3.1. Theorem 3.1 implies that deep linear networks can obtain a scaled version of y using only the first layer, i.e., XWW WiPi cy, where contribute to the expressive power.
0. Therefore, the remaining layers do not
3.1 TRAINING PROBLEM WITH VECTOR OUTPUTS
Here, we consider vector output, i.e., my K, deep networks with the output (x, In this case, we have the following training problem
min Σ will s.t. (x) Y. (0.1
(15)
With the same approach, the optimal layer weights for equation can be characterized follows.
Since the derivations similar, present the details in Appendix A.4 and A.6

---

Under review as a conference paper at ICLR 2021
Theorem 3.3. Optimal layer weight for equation 15 can be formulated follows
K Vu P ifl=
W
i=1 i--. if <ls 2
21=1 PL- 2.j i.
where Vw.j is the j"h maximal right singular vector of A and we may pick a set of unit norm vectors {Prs)h=? 1-= such that Pi. 0, vj # k.
The next theorem formally proves that strong duality holds for the primal problem in equation 15
Theorem 3.4. Let y be feasible for equation 15 then strong duality holds for finite width networks.
4 DEEP RELU NETWORKS
Here, we consider an L-layer ReLU network with (x) A WT. where A (Ar-1 Wi)+, Vi E [L IJ, Ao X, and (I:++ (0, Below, we first state the train- ing problem and then present our results
min Elwil s.t. (X) y,
(16)
Theorem 4.1. Let X be rank-one data matrix such that X = cap where c E RT and ag E Rd then strong duality holds and the optimal weights for each layer can be formulated as follows
Φ1-1
Φ1-2
W.
Al [L 2 w.-1
|
1
where do = and {<)) 1-2 is a set of vectors such that Φi E R7 and 1101122= tt, VI E [L - 2}.
Our derivations can also extended to cases with bias term. Below, we first examine a two-layer ReLU network training problem with bias term and then extend this result multi-layer network.
Theorem 4.2. Let X be data matrix such that X = caf where E I=" and ag R.d. Then, set ag of optimal solutions to equation 16 satisfies ((w; b,) m where w. = ||olla b, = - anl|2 with s; =1, Vi [m].
Corollary 4.1. As result of Theorem when have one dimensional data, i.e., x E RR"" an optimal solution to equation 16 can be formulated as {w,, b,) )m,, where w, = 84. by = -,Y;
with s; =1, Vi E [m]. Therefore, the optimal network output has kinks only the input data points, i.e. the output function in the following form: fe.2($) E, (t x.) Therefore, the network output becomes linear spline interpolation for one dimensional datasets.
We now extend the results in Theorem 4.2 and Corollary 4.1 for multi-layer ReLU networks.
Proposition 4.1. Theorem 4.7 still holds when add bias term the last hidden layer, i.e., the output becomes (AL-2 AL--WL- L-1 + 1,,b7). WL = yy where A (A-11i))
E [L 2].
Corollary 4.2. As a result of Theorem 4.2 and Proposition 4. when we have one dimensional data, i.e., x E RR, the optimal network output has kinks only at the input data points, i.e., the output function in the following form: fe (.) = E, (xxx Therefore, the network output becomes linear spline interpolation for one dimensional datasets.
Remark 4.1. Note that in Corollary 4.1 and 4.2 we prove that the optimal output function for multi-layer networks are linear spline interpolators for rank-one data, which generalizes the two- layer results for oie-dimensional data Savarese et al. (2019): : Parhi Nowak (2019): Ergen & Pilanci 2020aab) b) arbitrary depth. We also remark that the analysis of ReLU networks for the one dimensional data considered in these works non-trit non-trivial, which is special case of our rank-one data assumption.

---

Under review as a conference paper at ICLR 2021
The analysis in Theorem 4.1 also holds for vector output multi-layer ReLU networks as shown in the next result.
Proposition 4.2. Strong duality also holds for deep ReLU networks with vector outputs and the optimal layer weights can be formulated as in Theorem 4.1
Now, we extend our characterization to arbitrary rank whitened data matrices and fully characterize the optimal layer weights of a deep ReLU network with K outputs.
Theorem 4.3. Let (X, Y) be dataset such that XXT = Fan Y has orthogonal columns, then the optimal weight matrices for each layer can be formulated as follows
2K
W
1
@1-11
Ti.r 1L WL-1= 1
L LL-2.
L 22.2 10x
V2
1 1,1-1,112 1|2
V2K
12-22
where (00.25-1, = (x)(()) X" (-3,) +) Vj E [K] and ( 14-2 is a set of vectors such that Φ1. E RT,,, 11 = t", and (T, . = 0, Vi $
Remark 4.2. In one hot encoded labeling, which the conventional labeling for classification tasks, the label matrix Y E |R has nonoverlapping, therefore orthogonal, columns. Hence, classification tasks with one hot encoded labels directly satisfy the assumption in Theorem 4.3
Remark 4.3. We note that the whitening ussumption XXT = I, necessitates that n S d, which might appear be restrictive. However, this case is common in few-shot classification problems with limited labels (Chen et al. 2018). Moreover, it is challenging to obtain reliable labels in prob- lems involving high dimensional data such as in medical imaging (Hyun al. 2020) and geneties Singh& & Yamada 2020), where n S d is rypical. More importantly, SGD employed in deep learn- ing frameworks, e.g. Pylorch and Tensorflow, operate in minibatches rather than the full dataset.
Therefore, even when n > d, each gradient descent update can only be evaluated on small batches, where the batch size ny satisfies nhg < d. Henne,, the n S d case implicitly occur during the training phase.
We note that these results also hold for regularized ReI.U networks as in the previous sections and we can obtain closed-form solutions for all the layers weights as proven in the next result.
Theorem 4.4. Let (X, Y) be a dataset such that T = I, and Y has orthogonal columns, then set of optimal layer weight matrices for the following regularized training problem
min 1 _
( Y o
W
(17)
2
can be formulated as follows
2K 11 TT.
W
Tol-1
(1o00rl12 3) 6,
ifl=
where 62j-1 e2j
[K], ej is the jth ordinary basis vector, and the other definitions except to = 1.
Vj E
follows from Theorem 4.3
Remark 4,4. Theorem proves that when the data matrix is whitened and the label matrix sat- isfies certain conditions, all the layer weights can be obtained as closed-form analytical formulas. We further note the conditions in this theorem are common in some generic regressiondllasiffcatii frameworks. As an example, for image classification tasks, it has been shown that whiteming sig- nificantly improves the classification accuracy of the state-of-the-ar architectures, e.g., ResNets, on benchmark datasets such as CIFAR- --00 and ImageNet (Huang et al. [2018). Furthermore, since the label matrix is one hot encoded in image classification lasks, it directly satisfies the condition in the theorem. Therefore, in such cases, there is no need to train deep ReLU network in an end-to end-to-end manner. Instead one can directly use the closed-fone form formulas in Theorem 4.4
Thiis can be achieved by applying batch whitening, which often improves accuracy (Huang et al.
2018

---

Under review as a conference paper at ICLR 2021
W
Wx
Wa
25
25
B
13
20
20
34
15
15
2-
10
10
0
10
10
x x10
(a)
(b)
Figure 2: Verification of Remark 2.1 (a) Rank the hidden layer weight matrix as function of 8 and (b)
rank the hidden laver weights for different regularization parameters, i.c. 31 < 88 < Ax < S1.
1.5
30
W.
Wilr
Rank
Walr
Walr
0.5
Wala
Wil
10
Wala
200
400
800
800
1000
Iteration
Iteration
x10*
(a)
(b)
Figure 3: Verification of Proposition
(a) Evolution of the operator and Frobenius norms for the layer weights of linear network and (h) Rank of the layer weights of ReLU network with K =
3.1 and 4.1
NUMERICAL EXPERIMENTS
Here, we present numerical results verify our theoretical analysis. We first use synthetic datasets generated from random data matrix with zero mean and identity covariance and the corresponding output vector obtained via a randomly initialized teacher network We first consider two-layer linear network with W1 E _220x50 and W2 150x5 To prove claim in Remark 2.1 we train the network using GD with different B. Figure 2a we plot the rank of W1 as function of B, as well as the location of the singular values W Eg VT using vertical red lines. This shows that the rank of the layer changes when 3 is equal one of the singular values, which verifies Remark 2. We also consider four-layer linear network with W, E R5x50 W₂ E 500x30 Wa E R300 and W4 E IR: 10x0 We then select different regularization parameters As illustrated in Figure [2b] | determines the rank of each weight matrix and the rank is same for all the layers, which matches with our results. Moreover, verify Proposition 3.1 choose such that the weights are rank-two. In Figure 3a we numerically show that all the hidden layer weight matrices have the same operator and Frobenius norms. We also perform an experiment for five-layer ReLU network with W E R x0x50 Ws IR 10 Here, we use data such that X = cat" where c E R and an Rd Figure we plot the rank of each weight matrix, which converges to one as claimed Proposition 4.1
< < 33 84-
W2 E 50x400 Wa R 400330
W4 E R 20 and
We also verify our theory on two real benchmark datasets, i.e., MNIST (LeCun) and CIFARIO (Krizhevsky al. (014). We first randomly undersample and whitened these datasets. Further- more, we convert the labels into one hot encoded form. Then, we consider ten class classifica- tion/regression task using three multi-layer ReLU network architecture with L 3, 4, 5. For each architecture, we use SGD with momentum for training and compare the training/test performance with the corresponding network constructed via the closed-form solutions (without any sort of train- ing) in Theorem 4.3, i.e., denoted as "Theory". In Figure 4 we observe that Theory achieves the optimal training objective, which also yields smaller error and higher accuracy in the test phase. Hence, these experiments numerically verify our claims in Theorem 4.3
6 CONCLUDING REMARKS
We studied regularized DNN training problems and developed an analytic framework to characterize a set of optimal solutions. We showed that optimal layer weights can be explicitly formulated as the extreme points of convex via the dual problem. We then proved that strong duality
Additional numerical results can be found in Appendix A.2
8

---

Under review as a conference paper at ICLR 2021
100
0.6
0.98
0.5
0.4
L-2 + L-4
101
0.94
0.3
0 90D-L
Theory
Theory Lod
Theory Lnd
0.9
0.2
2000
4000
10000
Epoch
Epoch
Epoch
(a) MNIST Training objective
(b) MNIST-Test error
(c) M.MMNNSTT-e Test accuracy
0.18
10
0.88
SGD L-3
SGD L-d
0.14
Theory-
0.97
Treory
Thenryd
0.865
0.12
2000 6000
8000
10000
2000
4000
6000 8000 10000
2000
4000
6000
8000
10000
Epoch
Epoch
Epoch
(I) CIFARIO-Tes accuracy Figure 4: Training and lest performance on whitened sampled datasets, where (nz, = (60, 90), 10,
(d) CIFARIO-Trainie
objective
(e) CIFARIO- Test emror
= 3, 4, 5 with 50 neurons per layer and we use squared loss with one hot encoding. For Theory, we use the layer weights in Theorem which achieves the optimal performance as guaranteed by Theorem 4.3
holds for both deep linear and ReLU networks and provided set of optimal solutions. We also extended our derivations to the vector outputs and many other loss functions. More importantly, our analysis shows that when the input data is whitened rank-one, instead of training L-layer deep ReLU network in an end-to-end manner, one can directly use the closed-form solutions provided in Theorem 4.1 and 4.4 As another corollary, we proved that the kinks of ReLU activations occur exactly at the input data points so that the optimized network outputs linear spline interpolations for -inedimensional datasets, which was previously known only for two-layer networks (Savarese) et al., 2019 Parhi & Nowak] 2019 Ergen & Pilanci 2020albb We conjecture that our extreme points characterization can also be extended to reveal the structure behind cases with arbitrary data. Therefore, one can explain the extraordinary generalization properties of DNNs.
REFERENCES
Sanjeev Arora, Nadav Cohen, Noah Golowich, and Wei Hu. A convergence analysis of gradient descent for deep linear neural networks. CoRR, hbs//880000281, 2018a. URL http::/ttaaaa:
org/abs 02281
Sanjeev Arora, Nadav Cohen, and Elad Hazan. On the optimization of deep networks: Implicit acceleration by overparameterivaaton. arXiv preprint arXiv: (002.08800059 2018b.
Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix factorization. arXiv preprint arXiv: /905. /3655, 2019.
Francis Bach. Breaking the curse of dimensionality with convex neural networks. The Journal of Machine Learning Research, 18(1):629-68) 681, 2017.
Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro. Global optimality of local search for low rank matrix recovery. In Advances Neural Information Processing Systems, pp. 3873-3881, 2016.
Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
Wei- Yu Chen, Yen-Cheng Liu, Zsolt Kira. Yu-Chiang Frank Wang, and Jia-Bin Huang. closer look at few-shot classification. In International Conference Learning Representations, 2018.
Lenaic Chizat and Francis Bach. A note on lazy training in supervised differentiable programming. arXiv preprint arXiv: 18/2.07922.6 2018

---

Under review as a conference paper at ICLR 2021
Simon Du and Wei Hu. Width provably matters in optimization for deep linear neural networks. In International Conference on Machine Learning, pp. 1655-1664, 2019.
Simon Du, Wei Hu, and Jason Lee. Algorithmic regularization in learning deep homogeneous models: Layers automatically balanced. In Advances in Neural Information Processing Sys- tems, pp. 384-395, 2018.
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 2020a. PMLR.
/ pttpp/epcccenn...ccoooccp.o m..r. press www. hww.0//////eee0.....m pta.ppprees//i0///eeeeeaaaaaaaa
URLhttte
Tolga Ergen and Mert Pilanci. Convex geometry and duality of over-parameterizee neural networks.
arXiv preprint arXiv:2002./1219 2020b.
Miguel Angel Goberna and Marco López-Cerdá. Linear semi-infinite optimization. 01 1998. doi: 10.1007/978- 1--4999-8044-- 3.
Suriya Gunasekar, Blake E Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro. Implicit regularization in matrix factorization. In Advances in Neural Information Processing Systems, pp. 6151-6159, 2017.
Lei Huang, Dawei Yang, Bo Lang, and Jia Deng. Decorrelated batch normalization. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 791-800, 2018
Chang Min Hyun, Kang Cheol Kim, Hyun Cheol Cho, Jae Kyu Choi, and Jin Keun Seo. Framelet pooling aided deep learning network: the method to process high dimensional medical data. Ma- chine Learning: Science and Technology, 1(1):015009, 2020.
Ziwei Ji and Matus Telgarsky. Gradient descent aligns the layers of deep linear networks. In International Conference on Learning Representations, 2019. URL /ttp:ttttp:///peeerrieeer
Dett/Eozummidd-JELLge
Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. The CIFAR-10 dataset. http://www wttpt///r.iii/if....aaaaaeaaaaat html 2014.
Thomas Laurent and James Brecht. Deep linear networks with arbitrary loss: All local minima are global. In International Conference on Machine Learning, pp. 2902-2907, 2018.
Yann LeCun. The MNIST database of handwritten digits. http:://aan... hetp::///aan..ecun..mm www. /xdb//
mni mnist/
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. search of the real inductive bias: On the role of implicit regularization in deep learning. arXiv preprint 1rXiv:1412.661// 2014.
Rahul Parhi and Robert D Nowak. Minimum "norm" neural networks splines. arXiv preprint 1910033910 2019.
Saharon Rosset, Grzegorz Swirszez, Nathan Srebro, and Ji Zhu. LI regularization in infinite di- mensional feature spaces. In International Conference Computational Learning Theory, pp- 544-558. Springer, 2007.
Pedro Savarese, Itay Evron, Daniel Soudry, and Nathan Srebro. How do infinite width bounded norm networks look in function space? CoRR, abs/1902.05040, 2019. URL http:://arxiv
org/abs/1900 9022. 1ttp://1920000000 05040
Andrew M Saxe, James L McClelland, and Surya Ganguli. Exact solutions to the nonlinear dynam- ics of learning in deep linear neural networks. arXiv preprint arXiv:1312.6122 2013.
Ohad Shamir. Exponential convergence time of gradient descent for one-dimensional deep linear neural networks. arXiv preprint wwX.:0/80.00888/ 2018.
Dinesh Singh and Makoto Yamada. Fsnet: Feature selection network on high-dimensional biological data. arXiv preprint arXiv:2001.08322 008322, 2020.
10

---

Under review as a conference paper at ICLR 2021
Colin Wei, Jason D Lee, Qiang Liu, and Tengyu Ma. On the margin theory of feedforward neural networks. arXiv preprint arXiv:1810.05369 2018.
Hongyang Zhang, Junru Shao, and Ruslan Salakhutdinov, Deep neural networks with multi-brand architectures are intrinsically less non-convex. In The 22nd International Conference Artificial Intelligence and Statistics, pp. 1099-1109, 2019.

---

Under review as a conference paper at ICLR 2021
Appendix
Table of Contents
Appendix
12
A.1
General loss functions
12
A.2
Additional numerical results
12
A.3
Equivalence (Rescaling) lemmas for the non-convex objectives
13
A.4
Regularized extensions
Proofs for two-layer networks
A.6
Proofs for the deep linear networks
18
A.7 Proofs for the deep ReLU networks
23
A
APPENDIX
Here, present additional materials and proofs of the main results that included in the main paper due to the page limit. We also restate each result before the corresponding proof for the convenience of the reader.
A.1 GENERAL LOSS FUNCTIONS
In this section, show that our extreme point characterization holds for arbitrary convex loss functions including cross entropy and hinge loss.
min (()),((X)))) + welli s.t. W1,j E B2, Vj.
(18)
8EB
where y(: is convex loss function.
Theorem A.1. The dual of equation 18 given by
max C*) s.t. |X $ B,
where L is the Fenchel conjugate function defined
(*) = max L(z.y).
Theorem A. proves that our extreme point characterization in Corollary 2.1 applies to arbitrary loss function. Therefore, optimal parameters for equation and equation 9 are a subset of the same extreme point set, i.e., determined by the input data matrix X, independent of loss function.
Remark A.1. Since our characterization generic in the sense that it holds for vector output, deep linear and deep ReLU networks (see the main paper for details), Theorem A. valid for all of our derivations.
A.2 ADDITIONAL NUMERICAL RESULTS
Here, we present numerical results that are not included in the main paper due to the page limit. In Figure 5a we perform an experiment check whether the hidden neurons of two-layer linear network align with the proposed right singular vectors. For this experiment, we select a certain / such that W1 becomes rank-two. After training, we first normalize each neuron to have unit norm, i.e., w/,, 2 1, Vj. and then compute the sum of the projections of each neuron onto each right singular vector, i.e., denoted as v.. Since we choose 3 such that W1 is a rank-two matrix, most of the neurons align with the first two right singular vectors expected. Therefore, this experiment verifies our analysis and claims in Remark 2.1 Furthermore, as an alternative to Figure 2a the singular values of W, with respect the regularization parameter / in Figure
we plot
12

---

Under review as a conference paper at ICLR 2021
1.5
Projection
V1
0.5
0
2
4
6
8
10
Iteration
x10
3
(b)
Figure 5: (a) Projection hidden neurons right singular vectors claimed Remark and (b)
singular values of W, with respect to B.
A.3 EQUIVALENCE (RESCALING) LEMMAS FOR THE NON-CONVEX OBJECTIVES
In this section, we present all the equivalence (scaling transformation) lemmas we used in the main paper and the the proofs are presented Appendix A.5 A.6 and two-layer, deep linear, and deep ReI.U networks, respectively.
Lemma 1.1. The following problems are equivalent:
L(fo, + 23 W 11 + B(L 2)t² (0:)
min
min (X), + + Σ Will (0:
WL-15 B2, W
st 4/ E [L -
where WL-1,5 denotes the jth column of W--1-
Proof of Lemmal 1.1 For any O we can rescale the parameters as WL-15 = 03 WL-1 and LL WL.j/aj, for any ag > O. Then, the network output becomes
(x) = ((WW)) ) Wi.1) Wr. = ((XW.) Wi-1) WT.
which proves (X) fa, (X). addition to this, we have the following basic inequality
L-2
Σ Ww 2 Σ Will +2 +2 WLL ||L--,512.
where the equality is achieved with the scaling choice og
(TwZ-11ll is used. Since the scaling
|
operation does not change the right-hand side of the inequality, we can |/wr-tllll Vj. Therefore, the right-hand side becomes ||wr.11i-
Now, let us consider a modified version the problem, where the unit norm equality constraint relaxed as (w-11,ll2 112 S 1. Let us also assume that for a certain index we obtain ||w--1lll < with WL,j * as an optimal solution. This shows that the unit norm inequality constraint is not active for Wz-1j. and hence removing the constraint for WL-1. will not change the optimal solution. However, when we remove the constraint, ||WL-1,5llz - oo reduces the objective value since it yields WL.j = 0. Therefore, that correspond to a nonzero Wr.j must be active for an optimal solution. This also shows that replacing || 1|122- 1 with ||wr.-1,j|l does not change the solution to the problem.
have contradiction, which proves that all the constraints
Then, we use the epigraph form for the norm the first I. 2 to achieve the equivalence.
Lemma A.I. (Neyhaabur et al. 2214)) Savarese et al. 2019; Ergen Pilanci 2000a byj The
following two problems equivalent:
min W W=ll 112 ||2ll2 8EB
min |/2ll1
0E8
s.t. fe.2 (X)
s.t. fe.((N) = -,W1, B2
13

---

Under review as a conference paper at ICLR 2021
Lemma A.2. The following problems equivalent:
min W W 113 |22l
min DE6
W2.2112
BEB
==1
s.t. f0.2 =Y
s.t. (X) = Y.w E B2
Lemma A.3. The following problems are equivalent:
4-2 |wwll +
min Σlw Wwl (fi)t-1 1=1
min (6: 16:H-1-tti--1
Σ
&
1=1
S.I. (0. =
s.t. fe y, WL-15 E B2, WillF & 4, W e
Lemma A.4. The following problems are equivalent:
mL-1
min Σ will
min Σ (0.) (0) j=1
/Lall22 Σ
t
(0.HE 1=1
1=1
s.t. (x) Y
s.1. fo = Y, WL-15 E B2, W r 4, vI E [L - 2]
A.4 REGULARIZED EXTENSIONS
In this section, present the regularized versions of the training problems presented in the main paper and the proofs are presented in Appendix A.5 ReLU networks, respectively.
A.6 and A.7 two-layer, deep linear, and deep
A.4.1 REGULARIZED TRAINING PROBLEM FOR DEEP LINEAR NETWORKS WITH SCALAR OUTPUTS
Using Lemma
A.3 and Proposition 3.1 have the following dual for the regularized version of
equation 14
| y v.2... s.t. (XW Wr.22) S 3, v0 Or.-1, Vl.
max 2
Then, the weight matrices that maximize the value of the constraint can be described
1" PFPx, pf ifl = 1X ax,iiil
W7
1" PPP if <1SL-2
PI-2 i-
where Px,a(-) projects its input to {u R"
||| uu|2 S B.-1).
Corollary A.1. The analysis above and Theorem regularized deep linear network training problem.
3.2 also show that strong duality holds for the
A.4.2 REGULARIZED TRAINING PROBLEM FOR DEEP LINEAR NETWORKS WITH VECTOR OUTPUT
Using Lemma and Proposition 3.1 we have the following dual for the regularized version of equation 15
A 2I S.l. mar (A"xW, W VO, E 1 2
max- A
where we define 1 = (f...., 0, 1.5 l2 < 1, E [m1-1), [Willr t", A e
[L- 2]). Then, as equation 32 a set of optimal layer weights is
= Vn PT, i
Wi-
PI PI Pi
if 111k5LL-2
(19)
ブ== PL- if
where Vay is a maximal right singular vector of set {U E gaxk Fmax (U"X) < 1}. Additionally, Pt. 's is an orthonormal set. Therefore, the rank of each hidden layer is determined by / in Remark 2.1
and Px,s(-) projects its input to the
14

---

We first note that the dual of equation 4 with respect to Under review as a conference paper at ICLR 2021
A.5
PROOFS FOR THE TWO-LAYER NETWORKS
Lemma A.I. (Neyshabur et al. (2014) Savarese al. (2019);
Ergen Pilanci (2020u b The
following two problems equivalent:
min 8EB
W + ||wal
min ||wll1 EEB
s.t. f0. ( = y
(x -y, B2
Proof of Lemma A.I For any O rescale the parameters as W1.j 0, Wi, and W22
W2.5 /oj, for any 0j 0. Then, the network output becomes
fa
(X)
Σ
m
W2
1.j
W23 0j X.1,
Σ j=1
m
W2,
XW1,j
5=1
which proves (x, = (X), In addition to this, we have the following basic inequality
2 Σ
(w3, + [11,)12)
(122,5 l/W1,)l2),
==1
where the equality is achieved with the scaling choice ay = ( used. Since the scal- ing operation does not change the right-hand side of the inequality, we can [| Vj. Therefore, the right-hand side becomes ||Wall1-
Now, let consider modified version of the problem, where the unit norm equality constraint is relaxed as |willl2 <. 1. Let us also assume that for a certain index j. we obtain [|w1 ll, < with 22 * 0 as an optimal solution. This shows that the unit norm inequality constraint is not active for W1.j. and hence removing the constraint for Wi,j will not change the optimal solution. However, when we remove the constraint, ||w1,1l22 > oc reduces the objective value since it yields W2.j 0. Therefore, we have contradiction, which proves that all the constraints that correspond to a nonzero W2,j must active for an optimal solution. This also shows that replacing ||Wi,j]l2 with || < 1 does not change the solution to the problem.
Theorem 2.1. The dual of the problem in equation 4 is given by
> D"
max XEE"
X s.f. max wiEB2
X $1.
(5)
For finite width networks, there exists finite m such that strong duality holds, iee,, = and an optimal W for equation 4 satisfies ((XWi) X = 1, where X is the dual optimal parameter. Corollary 2.1. Theorem 2.7 implies that the optimal neurons are extreme points which solve the following problem arg max EB2 A Xwi).
Proof of Theorem 2.1
W2 is 2.1 and Corollary
2.1
min max X y (XWW)) $1, || 1, (wa)
X
Then, reformulate the problem as follows
P
min max X + I [[( 1), s.t. [w1, < 1, 1j.j. (w))
where (XW,,) TT S 1) the characteristic function the set [IWW)) Alloo S which
is defined as
0 -o0
if I[(W,,) T./ls $
I(I(XW,) > 5
otherwise
Since the set [I(XW,) W /l < 1 is closed, the function Φ(A, Wi)
<
1) is the sum of a linear function and an apper-semicontinuour indicator function and therefore upper-semicootimuous The constraint W, is convex and compact. We use p* denote the
15

---

Under review as a conference paper at ICLR 2021
value of the above min-max max program. Exchanging the order of min-max obtain the dual problem given equation [ which establishes a lower bound D for the above problem:
p 2 D max min
X + +[[[] All I 1), s.t. [| & Vj,
X
(WB)
max y, s.t. || (XW1) Alll S VW1, |1.5 112 S 1,
X
max X"y y, s.t. || (Xw1) ) S kwi |w 1,
We now show that strong duality holds for infinite size NNs. The dual the semi-infinite program in equationSjis given by (see Section 2.2 of Goberna & López-Cerdá (1998) and also Bach (2017)
min ||l||V
S.L.
Xwidp(w1) y,
WiEB2
where TV is the total variation norm of the Radon measure μa. This expression coincides with the infinite-size NN as given in Bach (017)), and therefore strong duality holds. We also note that although the above formulation involves infinite dimensional integral form, by Caratheodory's theorem, the integral can be represented as finite summation of at most + 1 Dirac delta functions (Rosset et al. 2007). Next we invoke the semi-infinite optimality conditions for the dual problem in equation 5 in particular we apply Theorem 7.2 of Goberna & López-Cerde (1998). We first define the set
= cone {
( &XWi Wi E B2, E (1: On }
Note that K is the union of finitely many convex closed sets, since the function Xw, can be pressed as the union of finitely many convex closed sets. Therefore the set K closed. By Theorem 5.3 Goberna & López-Cerdä (1998), this implies that the of constraints in equation 5 forms Farkas-Minkowski system. By Theorem 8.4 of Goberna & López-Cerdä (1998), primal and dual values are equal, given that the system is consistent. Moreover, the system is discretizable, i.c., there exists a sequence of problems with finitely many constraints whose optimal values approach to the optimal value of equation [5], The optimality conditions in Theorem 7.2 Goberna & López-Cerda (1998) implies that y = W for some vector w Since the primal and dual values are equal, we have X X X XWi [ ||wlll, which shows that the primal-dual pair ((w2, Wi), X*) " lloc = 1. is optimal. Thus, the optimal neuron weights Wi satisfy (IXW;)) X
Proposition 2.1. (Du & Hu 2019))] Given w arg min |Xw w yl12. we have
arg min [XWiy) 12W222 Xw" Wi.w2
arg mig XW W2 y11.. W..w2
Proof of Proposition 2.1
Let us first define a variable w" that minimizes the following problem
w' min Xw yl
Thus, the following relation holds
x (Xw" - -y) =0a-
Then, for any Rdd, have
f(w) = Xw Xw" Xw" - -112
= Xw Xw {
+((w w') X (Xw* -r)- + Xw yyl
Xw Xw Xw 112
Notice that Xw" 1y does not depend on w, thus, the relation above proves that minimizing f(w equivalent to minimizing Xw Xw* where w is the planted model parameter. Therefore, the planted model assumption does not change solution to the linear network training problem in equation
16

---

Under review as a conference paper at ICLR 2021
Theorem 2.2. Let y) be feasible for equation 4 then strong duality holds for finite width networks.
Proof of Theorem 2.2 Since there exists single extreme point, can construct a weight vector We E R2 that is the extreme point. Then, the dual of equation 4 with W1 = We is
Dee max X s.t. (Xw..)
X cc 1
(20)
Then, we have
P min max X
max min X
(w2)
(wa)
s.t xt|,(X),
l0c I TA/
|1.jll2 1,
s.t. (XW1) )
>/ Al130 I 1, ||iilll - 1,
= max X²x y
X
(Xwe)) A1120 S
D = D
(21)
where the first inequality follows from changing order of min-max to obtain lower bound and the equality in the second line follows from Corollary 2.1
From the fact that an infinite width NN can always find solution with the objective value lower than or equal to objective value of finite width NN, we have
P
min BEE) (W.m))
W2
IV
pd min ||2/1 8E0
(22)
s.t. Xw y
s.t.
||w1,5 S 1, V.j
where Pa is the optimal value of the original problem with infinitely many neurons. Now, notice that the optimization problem on the left hand side of equation 22 is convex since it an -nom minimization problem with linear equality constraints. Therefore, strong duality holds for this prob- lem, i.e., P D Using this result along with equation 21 we prove that strong duality holds for a finite width NN, ie., P. = P =
D D' D
Theorem 2.3. Strong duality holds for equation 9 with finte width networks.
Proof of Theorem 2.3 Since there exists single extreme point, we can construct a weight vector We Edd that is the extreme point. Then, the dual of equation 9 with W1 We
D max A
1 a
yll2
1x11 s.t. XX S 3.
Then the rest of the proof directly follows Proof of Theorem 2.2
Theorem A.1. The dual of equation 18 given by
max L s.t. | $ 8B,
where L' the Fenchel conjugate function defined as
(*) max L(z,y).
Proof of Theorem 4.1 The proof follows from classical Fenchel duality (Boyd & Vandenberghe 2004
We first describe equation 18 in equivalent form follows
min L(z.y) 8 wel1 s.t. XWiw2, ||W1,1l2 S 1, 2
Then the dual function
g(A) min C(z,y) XT z + X - -B[lwell s.t. ||W1,112 S 1, Vj. z
Therefore, using the classical Fenchel duality (Boyd & Vandenberghe 2004] yields the claimed dual form.
17

---

Under review as a conference paper at ICLR 2021
Lemma A.2. The following problems equivalent:
min 6E8
W |1 + /|21
min M
W2.5122
=
==1
s.t. (X)= =Y
fe. X) = Y, w., B2, Vj
Proof of Lemma A.2
The proof directly follows from Proof of Lemma A.I
Theorem 2.4. Let (X. Y be feasible for equation 11 then strong duality holds for finite width networks.
Proof of Theorem 2.4 Since there exist Tw possible extreme points, we can construct a weight matrix W. E RR that consists of all the possible extreme points. Then, the dual of equation 11
with W1 We
D
max trace( A Y) s.t. ||A Xwealle S 1, E [rw]
Then the rest of the proof directly follows Proof of Theorem 2.2
A.6 PROOFS FOR THE DEEP LINEAR NETWORKS
Lemma A.3. The following problems are equivalent:
min Σ will (01) 1=1
min (6: (
|wu/l +
Σ t
1=1
s.t. (X)
s.t. (X) y, WL-15 E B2, WillF s 4, VI E L -
Proof of Lemma A.3
Applying the scaling trick Lemma A. to the last two layers of the I--layer
network in equation gives
L-2
min (0.
wwll1 Σ
Will
[/ ll2 S 1, Vj [m
XW W
Then, we use the epigraph form for the norm of the first L 2 to achieve the equivalence.
Proposition 3.1. First L 2 hidden layer weight matrices in equation 14 have the same operator and Frobenius norms, i.e., 4 = 12 = lI.22, where I = || [ill2, vl E [L-2] 2).
Proof of Proposition 3.1 Let first denote the sum of the norms for the first L - 2 layer as I, i.e.. t= Et-² ti, where t | [[Wi]r since the upper-bound is achieved when the matrices are rank-one (secequation problem
28 Then, to find the extreme points, we need to solve the following
max Wiz-ll2.... [Wi]|a/l... w; (
We can equivalently rewrite this problem using the variables (t,)/=² as follows
1-2
max
II
h
max
1 I
1
(t.)
(1) (1))
L-2 ti
T-33 3 t
s.t.
t 2 0
s.t.
420
1=1
-=1
18

---

Under review as a conference paper at ICLR 2021
If take the derivative of the objective function of the latter problem, ie., denoted as f(t with respect to EN, we obtain the following
@5 ...,....
L-3
L-3
L-3
L-3
I
Σ
4
Ötk
1=1
Then, equating the derivative to zero yields the following relation
=
77
t=1
where t denotes the optimal operator norm for the Athh layer's weight matrix. We also note that these solutions satisfy the constraints in the optimization problem above. Since by definition
L- of 2 have t =t =t. 2-
Theorem 3.1. Optimal layer weights for equation 14
satisfy the following relation
V. willa pf ifl =
Wi
l' P iflilsL-2
PL-2 ill=L-1
where ||ill2 = V [L 2] and w follows the definition in equation
Proof of Theorem 3.1
Using Lemma A.3 3 and Proposition 3.1 we have the following dual problem
for equation
P min max A7 y + (L - 2)t s.t. (XW WL-15) S WL-1. E B2 (9))
(23)
[Wilee St, 4 E [L - 2].
Now, 1et us assume that the optimal Frobenius norm for each layer is tt Then, if define , { reduces the following problem
S 1, E [ma-1], ||Will S 8*, VI
L 2] equation 23
p D max X s.t. (XW, .... ....) 1, 40 E O 11.
X
(24)
where we change the order of min-max obtain lower bound for equation 23 The dual of the semi-infinite problem in equation 24 is given by
{
min M|l|
(001 XW,
I.... ... Ww-idu((0,,.... ... 0L-1 =
(25)
where is a signed Radon measure and || I!r is the total variation norm. We emphasize that equation [5 has infinite width each layer, however, an application of Caratheodory's 's theorem shows that the measure in the integral can be represented by finitely many (at most + 1) Dirac delta functions (Rosset et al. 2007). Such selection of μu yields the following problem
Pa min /w/ll s.t. Σ XW (a))
w WL-1 =, of E AI
(26)
We first note that since the model in equation 26 has multiple weight matrices for each layer, it has more expressive power than regular network. Thus, we have P > P Since the dual of equation 14 and equation 26 are the same, we also have D D*, where D is the optimal dual value for equation 26
We now apply the variable change in equation to equation 24 follows
max X
T E. W s.t. I| 2 WTV Σ X 1, VO, E O1.1, 1I
(27)
With this assumption, (T. 2)t² hecomes constant ignore this term for the rest of derivations.
19

---

Under review as a conference paper at ICLR 2021
which shows that the maximum objective value is achieved when ΣTA C1 w. Thus, the optimal layer weights be found the maximizers of the constraint when Σ X
w. To find the
formulations explicitly, we first find an upper-bound for the constraint in equation 27 as follows
[ W 2T c1 WT-2... WTV wille S c @ WWL2ll2.... IV w 12 s w
where the inequality follows from the constraint on each layer weight's norm and 7 = 1th This upper-bound can be achieved when the layer weights are
V- Twlll PT if = PPP if
W7-
(28)
PL-2 =
2]. This shows that the weight matrices are rank-one and align with each other. Therefore, an arbitrary set of unit norm vectors, i.e., {p:) can be chosen achieve the maximum dual objective.
where || = 4l E [Z.
We note that the layer weights equation 28 are optimal for the relaxed problem in equation 26 However, since there exists single possible choice for the left singular vector of W, and we can select an arbitrary set for {pi L-2 we achieve D D using the same layer weights. Therefore,
the set of weights in equation 28 are also optimal for equation 14
Theorem 3.3. Optimal layer weight for equation 15 can be formulated as follows
V. V...pl ifl=1
Wi
P1-1, if ff1c11 2-2
EE= PL-2. =
where Vu.j is the jth maximal right singular vector of " and we may pick set of unit norm vectors (pt.) such that Pi,yPL. 0, # k.
Proof of Theorem 3.3
Using Proposition 3.1 and Lemma A.4 obtain the following dual problem
max traco A Y) s.t. Oman (A XW, ... W, Wr-2) S 1, v0, i
(29)
It is straightforward show that the optimal layer weights the extreme points of the constraint in equation 29 which achieves the following upper-bound
Oman (XW W1-2) S omaz (A X)7.
max (0)) 101--78 EEL
This upper-bound is achieved when the first L - 2 layer weights are rank-one with the singular value by Proposition 3.1 Additionally, the left singular vector W, needs align with one of the maximum right singular vectors of A Since the upper-bound for the objective is achievable for any A, we can maximize the objective value, as in equation by choosing a matrix A such that
Oraxd-rw
A V 0 Ok-raxrz X
U
O Ok Xd-ra
where W U in VT. Thus, a set of optimal layer weights can be formulated as follows
I'V NV..P ifl =
w/
< <15L-2 UPP T if
(30)
PL-2, =
where V is the 7 maximal right singular vector of A A However, notice that the layer weights in equation 30 are the optimal weights for the relaxed problem, i.e.,
mP-1
mL-1
min (f:) j=1
WLL. S.L.
XW
w C.w =Y, AOA E 0
(31)
20

---

Under review as a conference paper at ICLR 2021
Using the optimal layer weights in equation 30 we have the following network output for the relaxed model
ML
XW W W WL
Σ amo W L.
Since know that the objective value for equation 31 is lower bound for equation 15 the layer weights that achieve the output above for the original problem in equation [3 is optimal. Thus, set of optimal solutions to equation 15 can be formulated follows
mL-1 j=l Vu.PP. if =
W
mL
P--1jPts if < T. -2
(32)
PL-23
i-
where we select set of unit norm vectors {Lt 1 such that PijPi, = Vj
Theorem 3.2. Let y) be feasible for equation 14 then strong duality holds for finite width networks.
Proof of Theorem
3.2 We first select set of unit norm vectors, i.e., {p L-2 to construct weight
I- matrices (WO)
that satisfies equation 28 Then, the dual of equation 14 can be written
Dr = max X A
s.t. (XWi
w W
Then, we have
min
max ATy
2
max A y X
(33)
(8)) E02 A
s.t. [XW WL-1) $
s.t. (XW WL-1) S1,
AO E θ1-1
max X"y
s.t. (XW w )
D. D" = D
where the first inequality follows from changing the order of min- max to obtain a lower bound and the first equality follows from the fact that (Wi)/=1 maximizes the dual problem. Furthermore, have the following relation between the primal problems
Pe = min |wzlla WL
Pr min (8)E,EL
1/wlla
(34)
s.t. W
W
Wi
s.t. W.... WV....W.... WL-IWL=Y.
where the inequality follows from the fact that the original problem has infinite width in each layer. Now, notice that the optimization problem on the left hand side of equation 34 is convex since is
an fi-nrrm minimization problem with linear equality constraints. Therefore, strong duality holds
for this problem, i.e., p D and we have Pa > p 2 P 2 D = D =D* Using this result
along with equation 33 we prove that strong duality holds, i.e., P p P* Dr D* D
Corollary 3.1. Theorem 3.1 implies that deep linear networks can obtain scaled version of
using only the first layer, iee. XW cy. where c 0. Therefore, the remaining layers do not contribute the expressive power.
Proof of Corollary 3.1
The proof directly follows from equation 28
Corollary A.1. The analysis above and Theorem 3.2 also show that strong duality holds for the regularized deep linear network training problem.
21

---

Under review as a conference paper at ICLR 2021
Proof of Corollary A.1
The proof directly follows from the analysis in this section and Theorem
Lemma A.4. The following problems are equivalent:
L-2 WL +
min (OL
Σ
will?
min Σ
Σ
ti
(t) j=1
1=1
(x)
s.t. fx) Y, WL-15 Bz,
W
St. 4E
IL 2]
Proof of Lemma A.4
Applying the scaling trick in Lemma A.l to the last two layer of the L-layer gives
network in equation 15
mi-1
1-2
min (0: 1 14
WI 1l2 +
Σ
j=l
s.t. || S 1, Vj E [ma-i]]
XW I... WL-I
Then, the epigraph form for the norm of the first L - 2 to achieve the equivalence.
Theorem 3.4. Let y} be feasible for equation 75 then strong duality holds for finite width networks.
L-2 Proof of Theorem 3.4 We first select set of unit norm vectors, i.e., {pI. U=1 to construct weight
matrices (W ) that satisfies equation 30 Then, the dual of equation can be written as
D max trace
s.t. o max (A X W $1, Vj
Then, we have
p
min
max trace(A">)
max trace (arace((2 A YY)
(35)
10 10 Ee0...
A
A
s.t. maaz
AXW, 21-2)
s.t. maz (A XW,, WL-2) $1, 40, E 1
max trace trace (A TY)
s.t. maa (A" W 1 Vj
D"= D
where the first inequality follows from changing the order of min-max to obtain a lower bound and the first equality follows from the fact that { (W |_- maximizes the dual problem. Furthermore, have the following relation between the primal problems
Ps min W.
Σ
WWL.3l12
p' min
Σ j=l
WL.lllz
(36)
10tH
mL
S.L.
WeJ...
Wer wI, -Y
S.L. W ... W
1=1
where the inequality follows from the fact that the original problem has infinite width in each layer. Now, notice that the optimization problem on the left hand side of equation i6]] convex since is an fy-norm minimization problem with linear equality constraints. Therefore, strong duality holds for this problem, i.e., P De and we have P 2 P 2 P 2 D = D* =D* Using this result along with equation 35 prove that strong duality holds, i.e., P P P* = D = D' D*
22

---

Under review as a conference paper at ICLR 2021
A.7 PROOFS FOR THE DEEP RELU NETWORKS
Theorem 4.1. Let X be rank-one data matrix such that X = then strong duality holds and the optimal weights for each layer can be formulated as follows
cap where E R and ag E IR.,
Φ1-1 of. VIE [L 2). WL-1 201-2
ΦL-2
Wi 101-1
where Φo and { is set of vectors such that Φr E R2 and || = t,, A E [L - 2]. Proposition 1. First L hidden layer weight matrices in equation T6 have the same operator and Frobenius norms.
Proof of Proposition Z Let us first denote the sum of the norms for the first I. 2 layer as f, i.e.,
t= - t4, where t |Will [|Wr]] l since the upper-bound is achieved when the matrices are rank-one. Then, to find the extreme points (see the details in Proof of Theorem 4.1 we need to solve the following problem
arg max (X* ? c/ c|lla_22/l2- arg max 10.1
cl wr.-2)+l1
10.1 f0.11-1ELL... FEBL-1
where we use a (a W0-221 L-2)+. Since | (WL-2llF = 1
the objective E
value above becomes X cl (a aala
(t- ((-)
Applying this step to all the remaining layer
weights gives the following problem
I--
arg ( E0
|X cl |aola
Σ
II s.t. s.t.
Σ
4
S 42 0.
1=1
Then, the proof directly follows from Proof of Proposition 3.1
Proof of Theorem 4.1 Using Lemma A.3 and Proposition this problem can be equivalently
stated as
min (0: { E0L-1
Iw 1lll s.t. A (Ai-1 W [ 1]
(37)
A1.
which also has the following dual form
min 1a1L-en c0
max TTy
(38)
s.t. | / 1
Notice that we remove the recursive constraint in equation 38 for notational simplicity, however, Ar, still function of all the layer weights except w.. Changing the order of min-max in equation
38 gives
D'2D''max = max MaX y s.t.
||| S 1, vo E 0 WE WELL- -L- 1].
(39)
The dual of the semi-infinite problem in equation 39 is given by
min ||
(40)
s.t. (00) (AL-2WL-1) 4p@0......
=
where ya is signed Radon measure and || the total variation norm. We emphasize that equation [40 has infinite width each layer, however, an application of Caratheodory's theorem shows that the measure 4 the integral can be represented by finitely many (at most n 1) Dirac delta functions (Rosset et al. 2007). Thus, we choose
1 Σ
8(W1 w
WL-1 W/-1)WLS.
23

---

Under review as a conference paper at ICLR 2021
where 8(.) is the Dirac delta function and the superseript indicates particular choice for the corre- sponding layer weight. This selection of fi yields the following problem
P
min l|
18:
M
(41)
s.t. Σ (AL- y. 8f E E WE j=1
Here, we first note that even though the model in equation [41 has the same layer widths with regular deep ReLU networks, has more expressive power since it allows matrices for each layer. Based on this observation, we have P 2 Pm.
choose multiple weight
As consequence of equation 39 we can characterize the optimal layer weights for equation as the extreme points that solve
arg |X (AL-2WL-1+41 (0, 10
(42)
where A is the optimal dual parameter. Since we assume that X = ca. with с E RT, we have AL-2 ca.-2- where a/ = (af_ Wi)+, a E BR and vo E [T. - 1]. Based on this observation,
we have WL-1 = aL-2 20-2/l 2//laa/ aaa-- 2112, which reduces equation 42 to the following
arg max (0.15, -
|X- cl c|LLa222
(43)
We then apply the same approach to all the remaining layer weights. However, notice that each neuron for the first L - 2 layers must have bounded Frobenius norms due to the norm constraint. If we denote the optimal la norms vector for the neuron in the 1th layer as Oi E RTT then we have the following formulation for the layer weights that solve equation 42
Φ1-1 of AI e 2]. W.-1
$1.-2
W
(44)
1
1Ø1-21122
where <b = ao. 2
1-2 set of nonnegative vectors satisfying |011|2 =t, I - 2).
We note that the layer weights equation 44 are optimal for the relaxed problem in equation 41
However, since there exists single possible choice for the left singular vector of W and we can select an arbitrary set for { the dual problems coincide for equation 16 equation 41 i.e.,
we achieve D = D using the same layer weights, where D is the optimal dual objective value
for equation 41 Therefore, the set of weights in equation 44 are also optimal for equation 16
O
Theorem 4.2. Let X be a data matrix such that X = cat.. where E R." and an E IRd, Then, a set of optimal solutions equation 16 satisfies ((w; bz) 1m where W: 8t Taollaa bi S |a |
with s; = +1, vi E [m]]
Proof of Theorem 4.2
Given X caf. all possible extreme points can be characterized as follows |X (cal + +b1
IXT (Xw + b1)
arg max
arg max
b, w.:l/w/l 12==
6.wi w||2=1
= arg max w.w:l w||2=1
X (ccaf w + +b
which can be equivalently stated as
caf w + 0,ViES
Σ
A.c;aT + Σ Arb s.t.
arg max
caal w + b 5 V.
b. w:wlww// I|a 1 iES
iES
which shows that w must be either positively or negatively aligned with an, i.e., w = Toll where
= 1. Thus, 6 must be in the range of |maxess( sccl|aalll)) minjes=(-soe (-sc, bacyl|agl1 ||ام||>) observations, extreme points can be formulated as follows
[|))] Using these
if Eies Arc 2 0 otherwise
(- if Eies X 0 and by (maxxes(=sxc:/lan)) otherwise
|
Wx+
P
where 8A sign (ies Asc:).
24

---

Under review as a conference paper at ICLR 2021
Proposition 4.1. Theorem 4.7 still holds when add a bias term to the last hidden layer, i.e., the output becomes (AL-2W W L-1 + 1,,b),
WL +
y, where A = (At-1Wi)+, VI | 2].
Proof of Proposition 4.1 Here, we add biases to the neurons in the last hidden layer of equation 16 For this case, all the equations in equation 37 equation 39 hold except notational changes due the bias term. Thus, equation 42 changes as
arg max (0: [0:) 4-1
| (Al- + b1n)+1=
arg max (6:) 100 E
|^-
+ +b1))
E0%-1,6
Σ i=1
Xi W 1
arg max
(6:) 2 E6.
(45)
which can also be written
Σ s.t..t s.t. {
arg max
ExiCaL-WW--14
0aal-2w.-11 1 - +,
- iES
iES
where S and S are the indices for which ReLU is active and inactive, respectively. This shows that (-an)es=(-cc)) |a. 2||2]]-
WL-1 must be WL-1 +1 Tae Taz-alla Then, we obtain the following
ax-2 and b E mmaxes(-cc|lar-2/l/
if Eies Mo 20
and b* (ainnes-(ssx-n ||1)) if Eies X 2 0
w
R 2 a1
otherwise
maxies(-sx-ca 2 otherwise
Aa
(46)
where sx- = sign (ies (cc.). This result reduces equation 45 to the following problem
arg max |C(X*, c) |
where C(X", c) is constant scalar independent of (Wi Wil Hence, this problem and its solutions are the same with equation 43 and equation 44, respectively.
1-2
Corollary 4.1. As a result of Theorem 4.2 when we have one dimensional data, i.e., X E IR", an optimal solution to equation 16 can be formulated as {(w,, b,) b,)m,m, where w, S;. by = - with = +1, Vi E [m]. Therefore, the optimal network output has kinks only at the input data points, i.e., the output function is in the following form: fe.2($) = E; ( (x) Therefore, the network output becomes linear spline interpolation for one dimensional datasets.
Corollary 4.2. As result of Theorem 4.2 and Proposition 4. when have one dimensional data, i.e., x E TR?,, the optimal network output has kinks only at the input data points, i.e., the output function is in the following form: fe,1 -+)= E. (z= +. Therefore, the network output becomes linear spline interpolation for one dimensional datasets.
Proof of Corollary 4.7 and 4.2 Let particularly consider the input sample ag. Then, the activa- tions of the network defined by equation 44 and equation are
af (a W, W.)
(a
ag
Φ
||an
|a
2
ax (af W2)
(af
ai
2
T
||a0||2||05
12
|ail] ||1
af. = = =aaf. WL-2)+ a
a -
|aallell0f 112 ... .al.llaalll055...
| 111
aL-1= = (a. 2 L-11 + 6)+ 2|a,-2||2 - ||aL-21l24
1 = 0.
Thus, if we feed caay the network, get a=-1 (c|lal-ellz c|lar_2||2+ 0, where use the fact that optimal biases are in the form of = -c, 22 as proved in equation 466 This analysis proves that the kink of each ReI.U activation occurs exactly one of the data points. n1
25

---

Under review as a conference paper at ICLR 2021
Proposition 4.2. Strong duality also holds for deep ReLU networks with vector outputs and the optimal layer weights can be formulated as in Theorem 4.1
Proof of Proposition 4.2
For vector outputs, we have the following training problem
min
W s.t. So,1(X)= = Y.
(0:
After a suitable rescaling as in the previous case, the above problem has the following dual
P D max trace A Y) s.t. || (Ar.- S 1, v0, E Or.1, E [L []. (47)
Using equation we can characterize the optimal layer weights as the extreme points that solve
arg max
|| (AL-2WL-1)+1l2.
(48)
(0:) EB
where A is the optimal dual parameter. Since we assume that X caf with c E RT, we have AL-2 caf where af" = (af_, Wi)+, E 14 and V/ E [L 1]. Based on this observation, we have Wr.-1 ar. 2/ ar. 2112. which reduces equation 48 to the following
arg max [0] E
||
cl|a aa. |/122
Then, the rest of steps directly follow Theorem yielding the following weight matrices
Φ1-1 of, V [L - 2]. WL-1 1
ØL-2
W
where do = { is set of nonnegative vectors satisfying ı 1" AI E [L 2]. Moreover, as a direct consequence of Theorem 3.4 strong duality holds for deep ReLU networks.
Theorem 4.3. Let (X, (X be dataset such that Xx" then the optimal weight matrices for each layer can be formulated as follows
I and Y has orthogonal columns,
2K
W
1
@1-15
VI E -22, WL-1 pi,,
1
22-2 1 1 2.28 l
V2K
1
10-111112 1|2
V2K
OL 11-22112
where (0o.2j-11 Ø0,25) = (xx();) X ,))+ Vj E [K] and (
1L-2 is set of vectors
such that Φt. E RT!,
|| t", and ΦT, 01. = 0, Vi +
Proof of Theorem
4.3 For vector outputs, have the following training problem
Σ will s.t. fx, = Y. (OLLE
min
After suitable rescaling as in the previous case, the above problem has the following dual
Pa D* max trace(A A YY) s.t. ||A [AA" < 1, v0, E Or.-I, VI [L- 1]. (49)
Using equation we can characterize the optimal layer weights the extreme points that solve
arg max
I|A" (AL-2
(50)
(0.11 'E9,-1
where A is the optimal dual parameter. We first note that since X is whitened such that XXT I..
equation 50 implies "maz((A) < t Then, the objective is trivially maximized by A
11This be achieved by applying batch whitening, which often improves accuracy (Huang al. 2018
26

---

Under review as a conference paper at ICLR 2021
Y Y/O /ma (Y), which is also feasible solution. Therefore, equation 50 can be equivalently
written as
arg (A
(51)
{0:) E02-1
We now note that since Y has orthogonal columns, equation 51 can be decomposed into & maxi- mization problems each of which can be maximized independently to find set of extreme points. In particular, the jth problem can be formulated as follows
(A S max {1(xx)) |I( +11))
arg max
Then, noting the whitened data assumption, the rest of steps directly follow Theorem the following weight matrices
yielding
1 W = V2 r=1 11111112 pi Al E
11
[L 2), WL-1
1
61-21 22122
22-2
V2
2
where po = X T ( + y, + and (=r is a set of nonnegative vectors satisfying 11 = ll. Thus, combining the extreme points for each j yields
and 26,1011 Φ1.2
1 2K
W
11 1,
T 4
E
E
2], WL-1 -
1
Φ1-2,1
ΦL 2.22
V2K
p 1, 112
/2K
#1-2212
where (00,2)-1, 00,21)
x
14-2 is set of nonneg- (y,) x y3 Vj E [K] and (
ative vectors satisfying || | l2 t' and ΦT, Ø1.5 0 Vi $ Moreover, as a direct consequence of Theorem 3.4 strong duality holds for deep ReLU networks.
Theorem 4.4. Let (X, Y) be a dataset such that X In and Y has orthogonal columns, then a set of optimal layer weight matrices for the following regularized training problem
1 llf
Y + Σ W
min = OE
(17)
2
can be formulated as follows
2K
$1 1.r
Pir-
gi
W
2K
(ll@url12 3) 61
ifl= I.
where G2j-1
Vj E
[] oj is the jth ordinary basis vector, and the other definitions
follows from Theorem 4.3
except
Proof of Theorem 4.4 From Section A.4.2 and the proof of Theorem 4.3
the dual problem has
closed-form solution as follows
y; 8
if < 1ysll2
X;
Ty. YJ
Vj [K].
(52)
otherwise
and the corresponding extreme points of the constraint in
W
-r=1
2K
di-i.
if1 i
(53)
where the definitions follows from Theorem
We now that given the hidden layer weight in equation 53 the primal problem in equation 17 is convex and differentiable with respect to the output layer weight W, y.- Thus, we can find the optimal output layer weights by simply taking derivative and equating it to zero. Applying these steps yields the following output layer weights
2K
W =
Σ
(ll - B) ΦL-1,
where 62j-1 = O22 = =o Vj E [ and oy is the jth ordinary basis vector.
27


Reviews:
[{"review_id": "t3aPkvQNThN", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper provides theoretical analysis and numerical experiments to characterize the structure of hidden layers and a set of optimal solutions. After warm-up with two-layer neural networks, the paper provides main theoretical results for deep linear networks and deep ReLU networks. Finally, numerical results are presented to verify theoretical analysis. \n\nThe paper cites the previous results in the literature of gradient dynamics of deep linear networks, and compare the contributions with this paper. However, the comparison is not done appropriately in the following sense. These previous results analyze the gradient dynamics of deep linear networks, whereas this paper analyses the set of optimal solutions. The set of optimal solutions is more well studied in the literature of loss landscapes of deep linear networks, where stationary points, saddle points as well as the set of optimal solutions are well studied. \n\nWhat this paper proves would be interesting if these results apply for the characterization of stationary points, saddle points, local minima, or gradient dynamics, instead of the set of globally optimal solutions. For example, alignment of the layers through gradient dynamics is studied in the previous work https://arxiv.org/abs/1810.02032, which is interesting because it is implicitly done by gradient dynamics. However, in the present paper, the alignment of the layers is explicitly imposed by the constraints or the regularization on the norm of each layer’s weight. This is trivial since with this constraints, the norm is minimized with the alignment, of course. There is no need to use duality, which is superficial for this type of results and is unnecessary. \n\nThe results on deep ReLU networks are also trivial because of the unrealistic assumptions on the data, as I explained in the following. For Theorem 4.1., the author assumes that X = c a_0^T, where each entry of c is nonnegative. This assumption makes ReLU to be trivial by the following observation: for any vector v in R^d, (c v^T)_+ = (\\diag(c) V)_+ where V = [v … v]^T, which is a n by d matrix. Because c is nonnegative, (\\diag(c) V)_+ = \\diag(c) (V)_+. Therefore, (c v^T)_+ = \\diag(c) (V)_+ = \\diag(c) V^+ where V^+ = [(v)_+ … (v)_+]^T. This means that the activation (on or off for ReLU nonlinearity) is exactly same for all data (over the dimension of n). This makes the results trivial for optimal solutions. Again, this setting would be interesting if the results are about gradient descent dynamics or loss surface, instead of optimal solutions. In that case, the activation is still the same for all data in this setting, but changes during time or vary in loss surface. For Theorem 4.2, the assumption on XX^T = I_n makes the result trivial by the following observation: the optimal solutions are simply the ones that memorize the data by using I_n. In the theorem, the optimal solution essentially memorizes the label at the first layer, as I expected. Again this might potentially be interesting if this is about stationary points, gradient descent or local minima, because this is nontrivial for those points. But, for the optimal solution with XX^T = I_n, this is trivial. This paper does not consider the case without XX^T = I_n: but, if it considers the case, if d >= n, then optimal solution is still trivial, because we can still memories the label at the first layer in a similar way. The assumption of XX^T = I_n is a strictly stronger version of the assumption of d >= n. Therefore, the results on deep ReLU networks are also trivial.\n\nI would recommend the authors to carefully read the papers in the literature of implicit regularization versus explicit regularization, and in the literature of gradient dynamics and loss landscape of deep linear networks. Those papers are motivated to study the problem beyond the optimal solutions. Understanding optimal solutions is also interesting but not in the same or similar setting and the setting where optimal solutions are trivial. For example, characterizing optimal solutions would be interesting for deep ReLU networks if we cannot easily construct optimal solutions, which is the not case in the setting of this paper as I described above.\n\n------------\nUPDATE AFTER AUTHORS RESPONSE: The authors did not address my concerns. The author response and discussion in the paper for the whitening is wrong: this paper use the whitening to mean $\\bf{X}\\bf{X}^T=\\bf{I}_n$ where n is the data size, but the whitening in machine learning means $\\bf{X}^T \\bf{X}=\\bf{I}_d$ where d is input dimension. This is completely different: the former makes the problem trivial whereas the latter does not. The explanation with the mini-batch is also wrong: optimization problem and the optimal solution are defined for the full dataset, and not for the mini-batch. For the memorization, I am not talking about label memorization, but the fact that we can set the weight matrix to have the direction of Y at the first layer, which is done in this paper. \n\nIn Figure 4, for MNIST, it has only 60% test accuracy. For CIFAR10, it has only 18% test accuracy. This demonstrates my points above. We know closed-form solutions easily for deep neural networks in this paper's setting (as explained above), but this should not work as it is using very strange models so that we can easily have closed-form solutions. Closed-form solutions have no value with 18% test accuracy for simple datasets. It is memorizing the direction of the training data and over-fitting a lot. Linear models work better.\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "pMMVg722sm_", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This work uses dual formulations of Neural Networks with ReLU activations. It starts explaining the dual formulations with simplest single layer unregularised linear neural networks with a single dimensional output layer. Then gradually extends the models to deep, regularised models with ReLU activations. There is also an assumption on the data to be of rank one or whitened. The experiments are limited and not essential, since they only show that the theory can be confirmed with experiments, albeit they also demonstrate the limitations of simplified models studied here.\nThis work builds on a recently published work by Ergen and Pilanci, where more limited NNs have been studied, although with a similar dual formulation approach. The main contributions of this paper are the proofs of Theorems 4.1 and 4.2 (given in the appendix). The theorems in section 3 are also novel, but the simplified case of the results in section 4. While very interesting, these results are not applicable in practice, because as the experiments in section 5 show, the models studied here are too simple. However, this is a good step forward towards building a more complete framework to study better NNs. Specifically, it would be interesting to see if a NN with a softmax activation on the output layer can be reformulated with a similar technique.\nI did not find the paper easy to read. For example, I haven't found the proof of Lemma 1.1. Several other results have proofs in the appendix, but it is not clear from the main article which proofs are available in the appendix.", "extra_scores": {}, "extra_text": {}}, {"review_id": "KyFHXvRilC", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors consider training neural networks with a variety of losses and regularization (such as weight decay).  The authors introduce a novel convex-dual formulation which allows them to characterize optimal solutions as being extreme points of particular convex sets.    For multi-layer linear networks, the authors prove that the optimal weight matrices have rank equal to the number of outputs of the network, and whose singular vectors align with those of neighboring layers.  For ReLU nets in one-dimension, the authors prove that optimal solutions act as linear spline interpolators (the kinks between linear pieces occur at data points), and the authors prove closed form expressions for optimal weights at intermediate layers when input data is whitened.  \n\nThe conclusions of this paper are strong and apply to a wide variety of neural networks.  The extension of linear spline interpolation results from 2-layers to more than 2-layers is a significant contribution.  The empirical comparisons of the presented analytical formulae for optimal weights to solutions via SGD are impressive (even though they are only performed on MNIST and CIFAR10 datasets).  The results of this paper themselves form a substantial contribution to the field and motivate clear followup work to test the performance of the provided formulae to larger and more realistic datasets, along with weakening the whitening assumptions.  Analytical expressions for weights of trained deep ReLU neural networks is a significant development, and the authors may want to provide more commentary on its significance (possibly with a small review of the most closely related works in this sense).  While I am not an expert in this subfield, there appear to be multiple significant contributions.\n\nMinor comment:\nSpelling error in footnote 3.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "Gzaiqp032j", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "-------------- Overview of the paper -----------------\n\nThe paper theoretically studies the structure of optimal weights in deep linear and ReLU neural networks. Using the convex duality formulation, the findings in the paper includes 1) alignment of the weight matrices in deep linear networks; 2) alignment of the weight matrices in deep ReLU networks when the input is rank-one or whitened. Some experiments are provided to verify the theory.\n\n-------------- Contributions and strength -----------------\n\nI think the main contribution of the paper comes from the convex duality formulation of the training problem, which is new. Such an idea allows for extensions of existing works, for example, Savarese et al. (2019), Parhi&Nowak(2019), and Ergen & Pilanci (2020a;b). The corresponding comparison is listed in Table 1.\n\nThe paper largely devotes to the theoretical results, while the presentation is clearly organized. I appreciate the warmup section on two-layer linear neural networks, which provides a primary understanding of the more complicated deep networks. I haven't checked every detail of the theory, albeit it appears to be correct and sound in the paper.\n\n-------------- Weakness -----------------\n\nOne crucial difficulty in deep learning theory is that deep neural networks are notoriously nonconvex due to their compositional structures. The setup in the paper removes this non convexity (for deep ReLU networks, certain assumption is imposed to enable the duality theory), which undermines the impact of the work. It is not clear to me what are the implications of the theory proposed in the paper to practitioners.\n\n-------------- Further questions and suggestions -----------------\n\n1. The overview section (section 1.1) is a bit deviate from the rest of the section, in that, the training objective is not the minimum norm training problem in the following sections 2 - 4. Lemma 1.1 does not provide understandings of later results.\n\n2. The duality theory requires (X, Y) is feasible, which is a pretty strong condition, given the network is linear. This in turn says the data are noiseless and are obtained from a linear model. An interesting direction to work on is using the dual formulation in Lemma 1.1 to analyze the situation where noise is present.\n\n3. The layout of the paper can be improved:\nIn Lemma 1.1, the right-hand side of the equation is a bit weird. \nIn lemma 2.1, the equal sign is used to indicate the two optimization problems are equivalent, which is a bit confusing (reads like the constraint on the left equals the objective on the right).\nFigure 2 is not centered compared to Figure 3. The right panel consists of three parallel figures, yet the size is small.\n\n-------------- Minor comments -----------------\n\nDoes the training algorithm have an impact on the experimental results, e.g., implicit bias? We observe momentum SGD is used in the MNIST and CIFAR experiment.\n\n———————— update after reading author’s response\n\nI raised my rating to 6 due to the clarification on assumptions in the paper. I am now more convinced of the relevance of the theories in the paper to practice.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies the globally optimal solutions to deep network training problems using convex duality. It derives duals of training problems in which we attempt to fit a dataset while regularizing the network weights with weight decay (L2 regularization). The paper uses strong duality to characterize optimal solutions to several instances of this problem. For fitting deep linear networks, it proves that the globally optimal weights “align” across layers. For fitting ReLU networks, it studies two cases: rank one data and “whitened” data, which satisfy $X^T X = I$. It proves that the optimal weights satisfy certain alignment and orthogonality conditions. 

Pros and cons:

[+] The paper uses the machinery of convex duality to characterize alignment of weights in optimal solutions to various neural network training problems. The extension of this approach from shallow networks to deep networks is potentially significant. 

[+] The paper is well written and technically precise. 

[-] As noted by the reviewers, the assumptions required to analyze deep ReLU networks are somewhat restrictive. In particular, the paper assumes a form of whitening in which the observed data vectors are orthonormal. This is much a much stronger assumption than the whitening usually applied in statistics, in which a linear transformation is applied to ensure that $XX^T = n I$, i.e., the empirical covariance is the identity. While the paper and rebuttal are correct to argue that SGD often uses minibatches of size $n’ \ll d$, the paper’s main claims are about the globally optimal solutions to the overall training problem. 

[+/-] Several reviewers raise concerns about the significance of results on the rank-one case for practice. The paper correctly notes that a number of previous works have studied rank one data, and that this paper generalizes those results to deep networks. The paper gives a very clear and explicit recipe for the optimal weights in this restricted setting.  Reviewers are split on the importance of this generalization — in particular, the extent to which results for the rank one case lead to insights that generalize to higher ranks. 

[-] Experiments verify the theory, in the sense that the theoretically derived weights are equal or better than those learned by SGD, in terms of the training loss. However, the learned networks do not seem to generalize (right panels of Figure 4), again raising concerns about the realism of the setting. 

Reviewers evaluation of the paper is split, with most reviewers appreciating its technical rigor and clean resolution of the rank-1/linear/whitened cases. While the review generated enthusiasm for the paper and its results, there were also significant concerns about the relatively restricted setting and the strength of the paper’s implications for training realistic networks, some of which remain after the authors response. 
Decision: Reject