Year: 2020

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 rankone or whitened. We then verify our theory via numerical experiments.

heading: 1 INTRODUCTION
text: 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, e.g., Stochastic Gradient Descent (SGD), can be used to successfully train them. Moreover, recent work has shown that highly over-parameterized 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 to fit a linear spline model in 1D regression. Therefore, regularizing the solution towards smaller norm weights might be the key to understand the generalization properties of DNNs. However, analyzing DNNs is still theoretically elusive even in the absence of nonlinear activations. Therefore, we 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 on 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 et al. (2018b); Du et al. (2018) showed that gradient flow enforces the layer weights to align. Ji & Telgarsky (2019) further proved that each layer weight matrix is asymptotically rank-one. These results provide insights to characterize the structure of the optimal layer weights, however, they require multiple strong assumptions, e.g., linearly separable training data and strictly decreasing loss function, which makes the results impractical. Furthermore, Zhang et al. (2019) provided some characterizations 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 to regularized training problems as the extreme points of a convex set, which is valid for vector outputs and popular loss functions including squared, cross entropy and hinge loss1; 2) For deep linear networks with K outputs, we prove that each optimal layer weight matrix aligns
1Extensions to other loss functions, e.g., cross entropy and hinge loss, are presented Appendix A.1
with the previous layers and becomes rank-K via convex duality; 3) For deep ReLU networks, we obtain the same weight alignment result for whitened or rank-one data matrices. As a corollary, we 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 et 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 0k (or 1k) and Ik to denote a 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 ‖ · ‖F , ‖ · ‖2, and ‖ · ‖∗, respectively. Furthermore, σmax(·) and σmin(·) represent the maximum and minimum singular values, respectively and B2 is defined as B2 := {u ∈ Rd | ‖u‖2 ≤ 1}.

heading: 1.1 OVERVIEW OF OUR RESULTS
text: We consider an L-layer network with layer weights Wl ∈ Rml−1×ml , ∀l ∈ [L], where m0 = d and mL = 1, respectively. Then, given a data matrix X ∈ Rn×d, the output is fθ,L(X) = AL−1wL, Al = g(Al−1Wl) ∀l ∈ [L − 1], where A0 = X and g(·) is the activation function. Given a label vector y ∈ Rn, training problem can be formulated as follows
min {θl}Ll=1
L(fθ,L(X),y) + βR(θ) , (1)
where L(·, ·) is an arbitrary loss function, R(θ) is regularization for the layer weights, β > 0 is a regularization parameter, θl = {Wl,ml}, and θ := {θl}Ll=1. In the paper, for the sake of presentation simplicity, we illustrate the conventional training setup with squared loss and `2-norm regularization, i.e., L(fθ,L(X),y) = ‖fθ,L(X) − y‖22 and R(θ) = ∑L l=1 ‖Wl‖2F . However, our analysis is valid for arbitrary loss functions and different regularization terms as proven in Appendix. Thus, we consider the following optimization problem
P ∗ = min {θl}Ll=1 L(fθ,L(X),y) + β L∑ l=1 ‖Wl‖2F . (2)
Next, we show that the minimum `22 norm is equivalent to minimum `1 norm after a rescaling. Lemma 1.1. The following problems are equivalent :
min {θl}Ll=1 L(fθ,L(X),y) + β L∑ l=1 ‖Wl‖2F = min {θl}Ll=1,t L(fθ,L(X),y) + 2β‖wL‖1 + β(L− 2)t2 s.t. wL−1,j ∈ B2, ‖Wl‖F ≤ t, ∀l ∈ [L− 2] ,
where wL−1,j denotes the jth column of WL−1.
Using Lemma 1.12, we first take the dual with respect to the output layer weights wL and then change the order of min-max to achieve the following dual deep network training problem, which provides a lower bound 3
P ∗ ≥D∗ = min t max λ min wL−1,j∈B2,∀j
‖Wl‖F≤t, ∀l∈[L−2]
−L∗(λ) + β(L− 2)t2 s.t. ‖ATL−1λ‖∞ ≤ 2β .
2The proof is presented in Appendix A.3. 3For the definitions and details see Appendix A.1.
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 is 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 a one-dimensional dataset. We also provide an experiment in Figure 1 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 it to arbitrary depth L (see Table 1 for details).

heading: 2 WARMUP: TWO-LAYER LINEAR NETWORKS
text: To illustrate an application of the convex dual D∗, we consider the simple case of two-layer linear networks with the output fθ,2(X) = XW1w2 and define the parameter space as θ ∈ Θ = {(W1,w2,m) |W1 ∈ Rd×m,w2 ∈ Rm,m ∈ Z+}. Motivated by recent results (Neyshabur et al., 2014; Chizat & Bach, 2018; Savarese et al., 2019; Parhi & Nowak, 2019; Ergen & Pilanci, 2020a;b), we first focus on a minimum norm4 variant of equation 1 when L(fθ,L(X),y) = ‖fθ,L(X) − y‖22 and then extend it to equation 1. The minimum norm primal training problem can be written as
min θ∈Θ ‖W1‖2F + ‖w2‖22 s.t. fθ,2(X) = y. (3)
Using Lemma A.15, we equivalently have P ∗ = min
θ∈Θ ‖w2‖1 s.t. fθ,2(X) = y,w1,j ∈ B2,∀j, (4)
which has the following dual form. Theorem 2.1. The dual of the problem in equation 4 is given by
P ∗ ≥ D∗ = max λ∈Rn λTy s.t. max w1∈B2 ∣∣λTXw1∣∣ ≤ 1 . (5) For finite width networks, there exists a finitem such that strong duality holds, i.e., P ∗ = D∗, and an optimal W1 for equation 4 satisfies ‖(XW∗1)Tλ∗‖∞ = 1 , where λ∗ is the dual optimal parameter.
Using Theorem 2.1, we now characterize the optimal neurons as the extreme points of a convex set.
Corollary 2.1. Theorem 2.1 implies that the optimal neurons are extreme points which solve the following problem arg maxw1∈B2 |λ
∗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 λ λTy s.t. max w1∈B2 |λTXw1| ≤ 1. (6)
Let X = UxΣxVTx be the singular value decomposition (SVD) of X 6. If we assume that there exists w∗ such that Xw∗ = y due to Proposition 2.1, then equation 6 is equivalent to
max λ̃
λ̃TΣxw̃ ∗ s.t. ‖ΣTx λ̃‖2 ≤ 1, (7)
where λ̃ = UTxλ and w̃ ∗ = VTxw ∗. Notice that in equation 7, we use an alternative formulation for the constraint, i.e., ‖XTλ‖2 ≤ 1 instead of |λTXw1| ≤ 1, ∀w1 ∈ B2 since the extreme point is achieved when w1 = XTλ/‖XTλ‖2. Given rank(X) = r ≤ min{n, d}, we have
λ̃TΣxw̃ ∗ = λ̃TΣx
[ Ir 0r×d−r
0d−r×r 0d−r×d−r ] w̃∗︸ ︷︷ ︸
w∗r
≤ ‖ΣTx λ̃‖2‖w̃∗r‖2 ≤ ‖w̃∗r‖2, (8)
4This corresponds to weak regularization, i.e., β → 0 in equation 1 (see e.g. Wei et al. (2018).). 5All the equivalence lemmas and proofs are presented in Appendix A.3. 6In this paper, we use full SVD unless otherwise stated.
which shows that the maximum objective value is achieved when ΣTx λ̃ = c1w̃ ∗ r . Thus, we have
w∗1 = VxΣ
T x λ̃
‖VxΣTx λ̃‖2 =
Vxw̃ ∗ r ‖w̃∗r‖2 = PXT (w∗) ‖PXT (w∗)‖2 ,
where PXT (·) projects its input onto the range of XT . In the following results, we show that one can consider a planted model without loss of generality and prove strong duality for equation 4. Proposition 2.1. [Du & Hu (2019)] Given w∗ = arg minw ‖Xw − y‖2, we have
arg min W1,w2 ‖XW1w2 −Xw∗‖22 = arg min W1,w2 ‖XW1w2 − y‖22.
Theorem 2.2. Let {X,y} be feasible for equation 4, then strong duality holds for finite width networks.

heading: 2.1 REGULARIZED TRAINING PROBLEM
text: In this section, we define the regularized version of equation 4 as
min θ∈Θ
1 2 ‖fθ,2(X)− y‖22 + β‖w2‖1 s.t. w1,j ∈ B2,∀j (9)
which has the following dual form
max λ −1 2 ‖λ− y‖22 + 1 2 ‖y‖22 s.t. max w1∈B2 |λTXw1| ≤ β.
Then, an optimal neuron needs to satisfy the condition
w∗1 = XTPX,β(y) ‖XTPX,β(y)‖2
where PX,β(·) projects its argument to {u ∈ Rn | ‖XTu‖2 ≤ β}. We now prove strong duality for equation 9. Theorem 2.3. Strong duality holds for equation 9 with finite width networks.

heading: 2.2 TRAINING PROBLEM WITH VECTOR OUTPUTS
text: Here, the model is fθ,2(X) = XW1W2 to estimate Y ∈ Rn×K , which can be optimized as follows min θ∈Θ ‖W1‖2F + ‖W2‖2F s.t. fθ,2(X) = Y. (10)
Using Lemma A.2, we reformulate equation 10 as
min θ∈Θ m∑ j=1 ‖w2,j‖2 s.t. fθ,2(X) = Y,w1,j ∈ B2,∀j. (11)
which has the following dual with respect to W2 max
Λ trace(ΛTY) s.t. ‖ΛTXw1‖2 ≤ 1, ∀w1 ∈ B2. (12)
Since we can assume Y = XW∗ due to Proposition 2.1, where W∗ ∈ Rd×K , we have
trace(ΛTY) = trace(ΛTXW∗) = trace(ΛUxΣxW̃ ∗ r) ≤ σmax(ΛTUxΣx) ∥∥∥W̃∗r∥∥∥∗ ≤ ‖W̃∗r‖∗ (13)
where σmax(ΛTX) ≤ 1 due to equation 12 and W̃∗r = [
Ir 0r×d−r 0d−r×r 0d−r×d−r
] VTxW ∗. Given the
SVD of W̃∗r , i.e., UwΣwV T w, choosing
ΛTUxΣx = Vw
[ Irw 0rw×d−rw
0K−rw×rw 0K−rw×d−rw
] UTw
achieves the upper-bound above, where rw = rank(W̃∗r). Thus, optimal neurons are a subset of the first rw right singular vectors of ΛX. Moreover, the next result shows that strong duality holds. Theorem 2.4. Let {X,Y} be feasible for equation 11, then strong duality holds for finite width networks.

heading: 2.2.1 REGULARIZED CASE
text: Here, we define the regularized version of equation 11 as follows
min θ∈Θ
1 2 ‖fθ,2(X)−Y‖2F + β m∑ j=1 ‖w2,j‖2 s.t. w1,j ∈ B2,∀j.
which has the following dual with respect to W2
max Λ −1 2 ‖Λ−Y‖2F + 1 2 ‖Y‖2F s.t. σmax(ΛTX) ≤ β.
Then, the optimal neurons are a subset of the maximal right singular vectors of PX,β(Y)TX, where PX,β(·) projects its input to the set {U ∈ Rn×K | σmax(UTX) ≤ β}. Remark 2.1. Note that the optimal neurons are the right singular vectors of PX,β(Y)TX that achieve the upper-bound of the set, i.e., ‖PX,β(Y)TXw∗1‖2 = β, where ‖w∗1‖2 = 1. This implies that the optimal neurons satisfy ‖YTXw∗1‖2 ≥ β. Therefore, the number of optimal neurons and the rank of the optimal weight matrix, i.e., W∗1 , are determined by β. Remark 2.2. There might exist optimal solutions other than the right singular vectors of PX,β(Y)TX. As an example, consider u1 and u2 as the optimal right singular vectors. Then, any u = α1u1 + α2u2 with α21 + α 2 2 = 1 also achieves the upper-bound, therefore, optimal.

heading: 3 DEEP LINEAR NETWORKS7
text: We now consider an L-layer linear network with fθ,L(X) = XW1 . . .wL, and the training problem
P ∗ = min {θl}Ll=1 L∑ l=1 ‖Wl‖2F s.t. fθ,L(X) = y. (14)
Proposition 3.1. First L − 2 hidden layer weight matrices in equation 14 have the same operator and Frobenius norms, i.e., t1 = t2 = . . . = tL−2, where tl = ‖Wl‖F = ‖Wl‖2, ∀l ∈ [L− 2].
Theorem 3.1. Optimal layer weights for equation 14 satisfy the following relation
W∗l =  t∗ Vxw̃ ∗ r ‖w̃∗r‖2 ρT1 if l = 1 t∗ρl−1ρ T l if 1 < l ≤ L− 2
ρL−2 if l = L− 1 ,
where ‖ρl‖2 = 1, ∀l ∈ [L− 2] and w̃∗r follows the definition in equation 8.
This result clearly shows that the intra-layer weights need to satisfy an aligment condition. The next theorem shows that strong duality holds in this case. Theorem 3.2. Let {X,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., XW1ρ1 = cy, where c > 0. Therefore, the remaining layers do not contribute to the expressive power.

heading: 3.1 TRAINING PROBLEM WITH VECTOR OUTPUTS
text: Here, we consider vector output, i.e., mL = K, deep networks with the output fθ,L(X) = XW1 . . .WL. In this case, we have the following training problem
min {θl}Ll=1 L∑ l=1 ‖Wl‖2F s.t. fθ,L(X) = Y. (15)
With the same approach, the optimal layer weights for equation 15 can be characterized as follows. 7Since the derivations are similar, we present the details in Appendix A.4 and A.6.
Theorem 3.3. Optimal layer weight for equation 15 can be formulated as follows
W∗l =  t∗ ∑K j=1 ṽw,jρ T 1,j if l = 1 t∗ ∑K j=1 ρl−1,jρ T l,j if 1 < l ≤ L− 2∑K
j=1 ρL−2,j if l = L− 1 ,
where ṽw,j is the jth maximal right singular vector of ΛTX and we may pick a set of unit norm vectors {ρl,j}L−2l=1 such that ρTl,jρl,k = 0, ∀j 6= k.
The next theorem formally proves that strong duality holds for the primal problem in equation 15.
Theorem 3.4. Let {X,y} be feasible for equation 15, then strong duality holds for finite width networks.

heading: 4 DEEP RELU NETWORKS
text: Here, we consider an L-layer ReLU network with fθ,L(X) = AL−1wL, where Al = (Al−1Wl)+, ∀l ∈ [L − 1], A0 = X, and (x)+ = max{0, x}. Below, we first state the training problem and then present our results
min {θl}Ll=1 L∑ l=1 ‖Wl‖2F s.t. fθ,L(X) = y, (16)
Theorem 4.1. Let X be a rank-one data matrix such that X = caT0 , where c ∈ Rn+ and a0 ∈ Rd, then strong duality holds and the optimal weights for each layer can be formulated as follows
Wl = φl−1 ‖φl−1‖2 φTl , ∀l ∈ [L− 2], wL−1 = φL−2 ‖φL−2‖2 ,
where φ0 = a0 and {φl}L−2l=1 is a set of vectors such that φl ∈ R ml + and ‖φl‖2 = t∗, ∀l ∈ [L− 2].
Our derivations can also be 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 to a multi-layer network.
Theorem 4.2. Let X be a data matrix such that X = caT0 , where c ∈ Rn and a0 ∈ Rd. Then, a set of optimal solutions to equation 16 satisfies {(wi, bi)}mi=1, where wi = si a0‖a0‖2 , bi = −sici‖a0‖2 with si = ±1,∀i ∈ [m].
Corollary 4.1. As a result of Theorem 4.2, when we have one dimensional data, i.e., x ∈ Rn, an optimal solution to equation 16 can be formulated as {(wi, bi)}mi=1, where wi = si, bi = −sixi with si = ±1,∀i ∈ [m]. Therefore, the optimal network output has kinks only at the input data points, i.e., the output function is in the following form: fθ,2(x̂) = ∑ i ( x̂ − xi ) +
. 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.1 still holds when we add a bias term to the last hidden layer, i.e., the output becomes ( AL−2WL−1 + 1nb T )
+ wL = y, where Al = (Al−1Wl)+, ∀l ∈ [L− 2].
Corollary 4.2. As a result of Theorem 4.2 and Proposition 4.1, when we have one dimensional data, i.e., x ∈ Rn, the optimal network output has kinks only at the input data points, i.e., the output function is in the following form: fθ,L(x̂) = ∑ i ( x̂− xi ) +
. 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 twolayer results for one-dimensional data in Savarese et al. (2019); Parhi & Nowak (2019); Ergen & Pilanci (2020a;b) to arbitrary depth. We also remark 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 data assumption.
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 a dataset such that XXT = In8 and Y has orthogonal columns, then the optimal weight matrices for each layer can be formulated as follows
Wl = 1√ 2K 2K∑ r=1 φl−1,r ‖φl−1,r‖2 φTl,r, ∀l ∈ [L− 2], WL−1 = 1√ 2K [ φL−2,1 ‖φL−2,1‖2 . . . φL−2,2K ‖φL−2,2K‖2 ] ,
where (φ0,2j−1,φ0,2j) = ( XT ( yj )
+ ,XT
( − yj ) + ) , ∀j ∈ [K] and {φl,r}L−2l=1 is a set of vectors
such that φl,r ∈ Rml+ , ‖φl,r‖2 = t∗, and φTl,iφl,j = 0, ∀i 6= j.
Remark 4.2. In one hot encoded labeling, which is the conventional labeling for classification tasks, the label matrix Y ∈ Rn×K 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 assumption XXT = In necessitates that n ≤ d, which might appear to 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 problems involving high dimensional data such as in medical imaging (Hyun et al., 2020) and genetics (Singh & Yamada, 2020), where n ≤ d is typical. More importantly, SGD employed in deep learning frameworks, e.g., PyTorch 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 nb satisfies nb d. Hence, the n ≤ d case implicitly occur during the training phase.
We note that these results also hold for regularized ReLU 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 XTX = In and Y has orthogonal columns, then a set of optimal layer weight matrices for the following regularized training problem
min θ∈Θ
1 2 ‖fθ,L(X)−Y‖2F + β 2 L∑ l=1 ‖Wl‖2F (17)
can be formulated as follows
Wl =
{∑2K r=1 φl−1,r ‖φl−1,r‖2φ
T l,r, if 1 ≤ l ≤ L− 1∑2K
r=1 (‖φ0,r‖2 − β)φl−1,rêTr if l = L ,
where ê2j−1 = ê2j = ej , ∀j ∈ [K], ej is the jth ordinary basis vector, and the other definitions follows from Theorem 4.3 except t∗ = 1.
Remark 4.4. Theorem 4.4 proves that when the data matrix is whitened and the label matrix satisfies 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 regression/classification frameworks. As an example, for image classification tasks, it has been shown that whitening significantly improves the classification accuracy of the state-of-the-art architectures, e.g., ResNets, on benchmark datasets such as CIFAR-100 and ImageNet (Huang et al., 2018). Furthermore, since the label matrix is one hot encoded in image classification tasks, it directly satisfies the condition in the theorem. Therefore, in such cases, there is no need to train a deep ReLU network in an end-to-end manner. Instead one can directly use the closed-form formulas in Theorem 4.4.
8This can be achieved by applying batch whitening, which often improves accuracy (Huang et al., 2018).

heading: 5 NUMERICAL EXPERIMENTS
text: Here, we present numerical results to verify our theoretical analysis. We first use synthetic datasets generated from a random data matrix with zero mean and identity covariance and the corresponding output vector is obtained via a randomly initialized teacher network9. We first consider a two-layer linear network with W1 ∈ R20×50 and W2 ∈ R50×5. To prove our claim in Remark 2.1, we train the network using GD with different β. In Figure 2a, we plot the rank of W1 as a function of β, as well as the location of the singular values of Ŵ∗ΣxVTx using vertical red lines. This shows that the rank of the layer changes when β is equal to one of the singular values, which verifies Remark 2.1. We also consider a four-layer linear network with W1 ∈ R5×50, W2 ∈ R50×30, W3 ∈ R30×40, and W4 ∈ R40×5. We then select different regularization parameters as β1 < β2 < β3 < β4. 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, to verify Proposition 3.1, we 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 a five-layer ReLU network with W1 ∈ R10×50, W2 ∈ R50×40, W3 ∈ R40×30, W4 ∈ R30×20, and w5 ∈ R20×1. Here, we use data such that X = caT0 , where c ∈ Rn+ and a0 ∈ Rd. In Figure 3b, we plot the rank of each weight matrix, which converges to one as claimed Proposition 4.1.
We also verify our theory on two real benchmark datasets, i.e., MNIST (LeCun) and CIFAR10 (Krizhevsky et al., 2014). We first randomly undersample and whitened these datasets. Furthermore, we convert the labels into one hot encoded form. Then, we consider ten class classification/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 training) 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.

heading: 6 CONCLUDING REMARKS
text: 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 a convex set via the dual problem. We then proved that strong duality
9Additional numerical results can be found in Appendix A.2.
holds for both deep linear and ReLU networks and provided a 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 or rank-one, instead of training an L-layer deep ReLU network in an end-to-end manner, one can directly use the closed-form solutions provided in Theorem 4.1, 4.3, 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 one-dimensional datasets, which was previously known only for two-layer networks (Savarese et al., 2019; Parhi & Nowak, 2019; Ergen & Pilanci, 2020a;b). 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.

heading: Appendix

heading: Table of Contents

heading: A Appendix 12
text: 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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 A.5 Proofs for the two-layer networks . . . . . . . . . . . . . . . . . . . . . . . . . 15 A.6 Proofs for the deep linear networks . . . . . . . . . . . . . . . . . . . . . . . . 18 A.7 Proofs for the deep ReLU networks . . . . . . . . . . . . . . . . . . . . . . . . 23

heading: A APPENDIX
text: Here, we present additional materials and proofs of the main results that are not 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.

heading: A.1 GENERAL LOSS FUNCTIONS
text: In this section, we show that our extreme point characterization holds for arbitrary convex loss functions including cross entropy and hinge loss.
min θ∈Θ L(fθ,2(X),y) + β‖w2‖1 s.t. w1,j ∈ B2,∀j, (18)
where L(·,y) is a convex loss function. Theorem A.1. The dual of equation 18 is given by
max λ −L∗(λ) s.t. ‖XTλ‖2 ≤ β,
where L∗ is the Fenchel conjugate function defined as
L∗(λ) = max z zTλ− L(z,y) .
Theorem A.1 proves that our extreme point characterization in Corollary 2.1 applies to arbitrary loss function. Therefore, optimal parameters for equation 3 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 is generic in the sense that it holds for vector output, deep linear and deep ReLU networks (see the main paper for details), Theorem A.1 is valid for all of our derivations.

heading: A.2 ADDITIONAL NUMERICAL RESULTS
text: 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 to check whether the hidden neurons of a 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., ‖w1,j‖2 = 1,∀j, and then compute the sum of the projections of each neuron onto each right singular vector, i.e., denoted as vi. Since we choose β such that W1 is a rank-two matrix, most of the neurons align with the first two right singular vectors as expected. Therefore, this experiment verifies our analysis and claims in Remark 2.1. Furthermore, as an alternative to Figure 2a, we plot the singular values of W1 with respect to the regularization parameter β in Figure 5b.

heading: A.3 EQUIVALENCE (RESCALING) LEMMAS FOR THE NON-CONVEX OBJECTIVES
text: In this section, we present all the equivalence (scaling transformation) lemmas we used in the main paper and the the proofs are presented in Appendix A.5, A.6, and A.7, two-layer, deep linear, and deep ReLU networks, respectively. Lemma 1.1. The following problems are equivalent :
min {θl}Ll=1 L(fθ,L(X),y) + β L∑ l=1 ‖Wl‖2F = min {θl}Ll=1,t L(fθ,L(X),y) + 2β‖wL‖1 + β(L− 2)t2 s.t. wL−1,j ∈ B2, ‖Wl‖F ≤ t, ∀l ∈ [L− 2] ,
where wL−1,j denotes the jth column of WL−1.
Proof of Lemma 1.1. For any θ ∈ Θ, we can rescale the parameters as w̄L−1,j = αjwL−1,j and w̄L,j = wL,j/αj , for any αj > 0. Then, the network output becomes
fθ̄,L(X) = (( XW1 ) + . . .W̄L−1 ) + w̄L = (( XW1 ) + . . .WL−1 ) + wL,
which proves fθ,L(X) = fθ̄,L(X). In addition to this, we have the following basic inequality
L∑ l=1 ‖Wl‖2F ≥ L−2∑ l=1 ‖Wl‖2F + 2 m∑ j=1 |wL,j | ‖wL−1,j‖2,
where the equality is achieved with the scaling choice αj = ( |wL,j | ‖wL−1,j‖2 ) 1 2 is used. Since the scaling operation does not change the right-hand side of the inequality, we can set ‖wL−1,j‖2 = 1,∀j. Therefore, the right-hand side becomes ‖wL‖1. Now, let us consider a modified version of the problem, where the unit norm equality constraint is relaxed as ‖wL−1,j‖2 ≤ 1. Let us also assume that for a certain index j, we obtain ‖wL−1,j‖2 < 1 with wL,j 6= 0 as an optimal solution. This shows that the unit norm inequality constraint is not active for wL−1,j , and hence removing the constraint for wL−1,j will not change the optimal solution. However, when we remove the constraint, ‖wL−1,j‖2 → ∞ reduces the objective value since it yields wL,j = 0. Therefore, we have a contradiction, which proves that all the constraints that correspond to a nonzero wL,j must be active for an optimal solution. This also shows that replacing ‖wL−1,j‖2 = 1 with ‖wL−1,j‖2 ≤ 1 does not change the solution to the problem. Then, we use the epigraph form for the norm of the first L− 2 to achieve the equivalence.
Lemma A.1. [Neyshabur et al. (2014); Savarese et al. (2019); Ergen & Pilanci (2020a;b)] The following two problems are equivalent:
min θ∈Θ ‖W1‖2F + ‖w2‖22 s.t. fθ,2(X) = y =
min θ∈Θ ‖w2‖1 s.t. fθ,2(X) = y,w1,j ∈ B2 .
Lemma A.2. The following problems are equivalent:
min θ∈Θ ‖W1‖2F + ‖W2‖2F s.t. fθ,2(X) = Y =
min θ∈Θ m∑ j=1 ‖w2,j‖2
s.t. fθ,2(X) = Y,w1,j ∈ B2,∀j .
Lemma A.3. The following problems are equivalent:
min {θl}Ll=1 L∑ l=1 ‖Wl‖2F
s.t. fθ,L(X) = y
= min
{θl}Ll=1,{tl} L−2 l=1 ‖wL‖1 + L−2∑ l=1 t2l
s.t. fθ,L(X) = y, wL−1,j ∈ B2, ‖Wl‖F ≤ tl, ∀l ∈ [L− 2]
.
Lemma A.4. The following problems are equivalent:
min {θl}Ll=1 L∑ l=1 ‖Wl‖2F
s.t. fθ,L(X) = Y
= min
{θl}Ll=1,{tl} L−2 l=1 mL−1∑ j=1 ‖wL,j‖2 + L−2∑ l=1 t2l
s.t. fθ,L(X) = Y, wL−1,j ∈ B2, ‖Wl‖F ≤ tl, ∀l ∈ [L− 2]
.

heading: A.4 REGULARIZED EXTENSIONS
text: In this section, we present the regularized versions of the training problems presented in the main paper and the proofs are presented in Appendix A.5, A.6, and A.7, two-layer, deep linear, and deep ReLU networks, respectively.

heading: A.4.1 REGULARIZED TRAINING PROBLEM FOR DEEP LINEAR NETWORKS WITH SCALAR OUTPUTS
text: Using Lemma A.3 and Proposition 3.1, we have the following dual for the regularized version of equation 14
max λ −1 2 ‖λ− y‖22 s.t. ‖(XW1 . . .WL−2)Tλ‖2 ≤ β, ∀θl ∈ ΘL−1, ∀l.
Then, the weight matrices that maximize the value of the constraint can be described as
W∗l =  t∗ XTPX,β(y) ‖XTPX,β(y)‖2ρ T 1 if l = 1 t∗ρl−1ρ T l if 1 < l ≤ L− 2
ρL−2 if l = L− 1 .
where PX,β(·) projects its input to { u ∈ Rn | ‖XTu‖2 ≤ βγ−1 } .
Corollary A.1. The analysis above and Theorem 3.2 also show that strong duality holds for the regularized deep linear network training problem.

heading: A.4.2 REGULARIZED TRAINING PROBLEM FOR DEEP LINEAR NETWORKS WITH VECTOR OUTPUT
text: Using Lemma A.4 and Proposition 3.1, we have the following dual for the regularized version of equation 15
max Λ −1 2 ‖Λ−Y‖2F s.t. σmax(ΛTXW1 . . .WL−2) ≤ β, ∀θl ∈ ΘL−1,
where we define ΘL−1 = {θ1, . . . , θL−1|‖wL−1,j‖2 ≤ 1,∀j ∈ [mL−1], ‖Wl‖F ≤ t∗, ∀l ∈ [L− 2]}. Then, as in equation 32, a set of optimal layer weights is
W∗l =  t∗ ∑K j=1 ṽx,jρ T 1,j if l = 1 t∗ ∑K j=1 ρl−1,jρ T l,j if 1 < l ≤ L− 2∑K
j=1 ρL−2,j if l = L− 1 (19)
where ṽx,j is a maximal right singular vector of PX,β(Y)TX and PX,β(·) projects its input to the set {U ∈ Rn×k | σmax(UTX) ≤ βγ−1}. Additionally, ρl,j’s is an orthonormal set. Therefore, the rank of each hidden layer is determined by β as in Remark 2.1.

heading: A.5 PROOFS FOR THE TWO-LAYER NETWORKS
text: Lemma A.1. [Neyshabur et al. (2014); Savarese et al. (2019); Ergen & Pilanci (2020a;b)] The following two problems are equivalent:
min θ∈Θ ‖W1‖2F + ‖w2‖22 s.t. fθ,2(X) = y =
min θ∈Θ ‖w2‖1 s.t. fθ,2(X) = y,w1,j ∈ B2 .
Proof of Lemma A.1. For any θ ∈ Θ, we can rescale the parameters as w̄1,j = αjw1,j and w̄2,j = w2,j/αj , for any αj > 0. Then, the network output becomes
fθ̄,2(X) = m∑ j=1 w̄2,jXw̄1,j = m∑ j=1 w2,j αj αjXw1,j = m∑ j=1 w2,jXw1,j ,
which proves fθ,2(X) = fθ̄,2(X). In addition to this, we have the following basic inequality
1
2 m∑ j=1 (w22,j + ‖w1,j‖22) ≥ m∑ j=1 (|w2,j | ‖w1,j‖2),
where the equality is achieved with the scaling choice αj = ( |w2,j | ‖w1,j‖2 ) 1 2 is used. Since the scaling operation does not change the right-hand side of the inequality, we can set ‖w1,j‖2 = 1,∀j. Therefore, the right-hand side becomes ‖w2‖1. Now, let us consider a modified version of the problem, where the unit norm equality constraint is relaxed as ‖w1,j‖2 ≤ 1. Let us also assume that for a certain index j, we obtain ‖w1,j‖2 < 1 with w2,j 6= 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 w1,j will not change the optimal solution. However, when we remove the constraint, ‖w1,j‖2 →∞ reduces the objective value since it yields w2,j = 0. Therefore, we have a contradiction, which proves that all the constraints that correspond to a nonzerow2,j must be active for an optimal solution. This also shows that replacing ‖w1,j‖2 = 1 with ‖w1,j‖2 ≤ 1 does not change the solution to the problem.
Theorem 2.1. The dual of the problem in equation 4 is given by
P ∗ ≥ D∗ = max λ∈Rn λTy s.t. max w1∈B2 ∣∣λTXw1∣∣ ≤ 1 . (5) For finite width networks, there exists a finitem such that strong duality holds, i.e., P ∗ = D∗, and an optimal W1 for equation 4 satisfies ‖(XW∗1)Tλ∗‖∞ = 1 , where λ∗ is the dual optimal parameter. Corollary 2.1. Theorem 2.1 implies that the optimal neurons are extreme points which solve the following problem arg maxw1∈B2 |λ ∗TXw1 |.
Proof of Theorem 2.1 and Corollary 2.1. We first note that the dual of equation 4 with respect to w2 is
min θ∈Θ\{w2} max λ
λTy s.t. ‖(XW1)T+λ‖∞ ≤ 1, ‖w1,j‖2 ≤ 1,∀j.
Then, we can reformulate the problem as follows
P ∗ = min θ∈Θ\{w2} max λ λTy + I(‖(XW1)T+λ‖∞ ≤ 1), s.t. ‖w1,j‖2 ≤ 1,∀j.
where I(‖(XW1)Tλ‖∞ ≤ 1) is the characteristic function of the set ‖(XW1)Tλ‖∞ ≤ 1, which is defined as
I(‖(XW1)Tλ‖∞ ≤ 1) = {
0 if ‖(XW1)Tλ‖∞ ≤ 1 −∞ otherwise .
Since the set ‖(XW1)Tλ‖∞ ≤ 1 is closed, the function Φ(λ,W1) = λTy +I(‖(XW1)Tλ‖∞ ≤ 1) is the sum of a linear function and an upper-semicontinuous indicator function and therefore upper-semicontinuous. The constraint on W1 is convex and compact. We use P ∗ to denote the
value of the above min-max program. Exchanging the order of min-max we obtain the dual problem given in equation 5, which establishes a lower bound D∗ for the above problem:
P ∗ ≥ D∗ = max λ min θ∈Θ\{w2} λTy + I(‖(XW1)Tλ‖∞ ≤ 1), s.t. ‖w1,j‖2 ≤ 1,∀j,
= max λ
λTy, s.t. ‖(XW1)Tλ‖∞ ≤ 1 ∀w1,j : ‖w1,j‖2 ≤ 1,∀j,
= max λ
λTy, s.t. ‖(Xw1)Tλ‖∞ ≤ 1 ∀w1 : ‖w1‖2 ≤ 1,
We now show that strong duality holds for infinite size NNs. The dual of the semi-infinite program in equation 5 is given by (see Section 2.2 of Goberna & López-Cerdá (1998) and also Bach (2017))
min ‖µ‖TV s.t. ∫
w1∈B2 Xw1dµ(w1) = y ,
where TV is the total variation norm of the Radon measure µ. This expression coincides with the infinite-size NN as given in Bach (2017), and therefore strong duality holds. We also note that although the above formulation involves an infinite dimensional integral form, by Caratheodory’s theorem, the integral can be represented as a finite summation of at most n+ 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 & López-Cerdá (1998). We first define the set
K = cone
{( sXw1
1
) ,w1 ∈ B2, s ∈ {−1,+1}; ( 0n −1 )} .
Note that K is the union of finitely many convex closed sets, since the function Xw1 can be expressed as the union of finitely many convex closed sets. Therefore the set K is closed. By Theorem 5.3 Goberna & López-Cerdá (1998), this implies that the set of constraints in equation 5 forms a Farkas-Minkowski system. By Theorem 8.4 of Goberna & López-Cerdá (1998), primal and dual values are equal, given that the system is consistent. Moreover, the system is discretizable, i.e., 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 & López-Cerdá (1998) implies that y = XW∗1w ∗ 2 for some vector w ∗ 2 . Since the primal and dual values are equal, we have λ∗Ty = λ∗TXW∗1w ∗ 2 = ‖w∗2‖1, which shows that the primal-dual pair ({w∗2,W∗1},λ∗) is optimal. Thus, the optimal neuron weights W∗1 satisfy ‖(XW∗1)Tλ∗‖∞ = 1.
Proposition 2.1. [Du & Hu (2019)] Given w∗ = arg minw ‖Xw − y‖2, we have
arg min W1,w2 ‖XW1w2 −Xw∗‖22 = arg min W1,w2 ‖XW1w2 − y‖22.
Proof of Proposition 2.1. Let us first define a variable w∗ that minimizes the following problem
w∗ = min w ‖Xw − y‖22.
Thus, the following relation holds
XT (Xw∗ − y) = 0d.
Then, for any w ∈ Rd, we have
f(w) = ‖Xw −Xw∗ + Xw∗ − y‖22 = ‖Xw −Xw∗‖22 + 2(w −w∗)T XT (Xw∗ − y)︸ ︷︷ ︸
=0d
+‖Xw∗ − y‖22
= ‖Xw −Xw∗‖22 + ‖Xw∗ − y‖22.
Notice that ‖Xw∗−y‖22 does not depend on w, thus, the relation above proves that minimizing f(w) is equivalent to minimizing ‖Xw −Xw∗‖22, where w∗ is the planted model parameter. Therefore, the planted model assumption does not change solution to the linear network training problem in equation 4.
Theorem 2.2. Let {X,y} be feasible for equation 4, then strong duality holds for finite width networks.
Proof of Theorem 2.2. Since there exists a single extreme point, we can construct a weight vector we ∈ Rd that is the extreme point. Then, the dual of equation 4 with W1 = we is
D∗e = max λ λTy s.t. ‖(Xwe)Tλ‖∞ ≤ 1. (20)
Then, we have
P ∗ = min θ∈Θ\{w2} max λ λTy ≥ max λ min θ∈Θ\{w2} λTy
s.t ‖(XW1)Tλ‖∞ ≤ 1, ‖w1,j‖2 ≤ 1,∀j s.t. ‖(XW1)Tλ‖∞ ≤ 1, ‖w1,j‖2 ≤ 1,∀j = max
λ λTy
s.t. ‖(Xwe)Tλ‖∞ ≤ 1 = D∗e = D ∗ (21)
where the first inequality follows from changing order of min-max to obtain a 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 a solution with the objective value lower than or equal to the objective value of a finite width NN, we have
P ∗e = min θ∈Θ\{W1,m} |w2| ≥ P ∗ =min θ∈Θ ‖w2‖1 (22)
s.t. Xwew2 = y s.t. XW1w2 = y, ‖w1,j‖2 ≤ 1,∀j, where P ∗ 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 is an `1-norm minimization problem with linear equality constraints. Therefore, strong duality holds for this problem, i.e., P ∗e = D ∗ e . Using this result along with equation 21, we prove that strong duality holds for a finite width NN, i.e., P ∗e = P ∗ = D∗ = D∗e .
Theorem 2.3. Strong duality holds for equation 9 with finite width networks.
Proof of Theorem 2.3. Since there exists a single extreme point, we can construct a weight vector we ∈ Rd that is the extreme point. Then, the dual of equation 9 with W1 = we
D∗e = max λ −1 2 ‖λ− y‖22 + 1 2 ‖y‖22 s.t. |λTXwe| ≤ β.
Then the rest of the proof directly follows Proof of Theorem 2.2.
Theorem A.1. The dual of equation 18 is given by max λ −L∗(λ) s.t. ‖XTλ‖2 ≤ β,
where L∗ is the Fenchel conjugate function defined as L∗(λ) = max
z zTλ− L(z,y) .
Proof of Theorem A.1. The proof follows from classical Fenchel duality (Boyd & Vandenberghe, 2004). We first describe equation 18 in an equivalent form as follows
min z,θ∈Θ
L(z,y) + β‖w2‖1 s.t. z = XW1w2, ‖w1,j‖2 ≤ 1,∀j.
Then the dual function is
g(λ) = min z,θ∈Θ
L(z,y)− λT z + λTXW1w2 + β‖w2‖1 s.t. ‖w1,j‖2 ≤ 1,∀j.
Therefore, using the classical Fenchel duality (Boyd & Vandenberghe, 2004) yields the claimed dual form.
Lemma A.2. The following problems are equivalent:
min θ∈Θ ‖W1‖2F + ‖W2‖2F s.t. fθ,2(X) = Y =
min θ∈Θ m∑ j=1 ‖w2,j‖2
s.t. fθ,2(X) = Y,w1,j ∈ B2,∀j .
Proof of Lemma A.2. The proof directly follows from Proof of Lemma A.1.
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 rw possible extreme points, we can construct a weight matrix We ∈ Rd×rw that consists of all the possible extreme points. Then, the dual of equation 11 with W1 = We
D∗e = max Λ trace(ΛTY) s.t. ‖ΛTXwe,j‖2 ≤ 1,∀j ∈ [rw].
Then the rest of the proof directly follows Proof of Theorem 2.2.

heading: A.6 PROOFS FOR THE DEEP LINEAR NETWORKS
text: Lemma A.3. The following problems are equivalent:
min {θl}Ll=1 L∑ l=1 ‖Wl‖2F
s.t. fθ,L(X) = y
= min
{θl}Ll=1,{tl} L−2 l=1 ‖wL‖1 + L−2∑ l=1 t2l
s.t. fθ,L(X) = y, wL−1,j ∈ B2, ‖Wl‖F ≤ tl, ∀l ∈ [L− 2]
.
Proof of Lemma A.3. Applying the scaling trick in Lemma A.1 to the last two layers of the L-layer network in equation 14 gives
min {θl}Ll=1,{tl} L−2 l=1 ‖wL‖1 + L−2∑ l=1 ‖Wl‖2F
s.t. ‖wL−1,j‖2 ≤ 1,∀j ∈ [mL−1] XW1 . . .WL−1wL = y
.
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., t1 = t2 = . . . = tL−2, where tl = ‖Wl‖F = ‖Wl‖2, ∀l ∈ [L− 2].
Proof of Proposition 3.1. Let us first denote the sum of the norms for the first L− 2 layer as t, i.e., t = ∑L−2 l=1 tl, where tl = ‖Wl‖2 = ‖Wl‖F since the upper-bound is achieved when the matrices are rank-one (seeequation 28). Then, to find the extreme points, we need to solve the following problem
max {θl}L−2l=1
‖WL−2‖2 . . . ‖W1‖2‖Vxw̃∗r‖2.
We can equivalently rewrite this problem using the variables {tl}L−2l=1 as follows
max {tl}L−2l=1 L−2∏ l=1 tl
s.t. t = L−2∑ l=1 tl, tl ≥ 0
=
max {tl}L−3l=1
( t−
L−3∑ l=1 tl ) L−3∏ j=1 tl
s.t. L−3∑ l=1 tl ≤ t, tl ≥ 0
.
If we take the derivative of the objective function of the latter problem, i.e., denoted as f(t1, . . . , tL−3), with respect to tk, we obtain the following
∂f(t1, . . . , tL−3)
∂tk = t L−3∏ l=1 l 6=k tl − 2 L−3∏ l=1 tl − L−3∑ l=1 l 6=k tl L−3∏ j=1 l 6=k tl.
Then, equating the derivative to zero yields the following relation
t∗k = t− L−3∑ l=1 t∗l
where t∗k denotes the optimal operator norm for the k th layer’s weight matrix. We also note that
these solutions satisfy the constraints in the optimization problem above. Since by definition t −∑L−3 l=1 t ∗ l = t ∗ L−2, we have t ∗ 1 = t ∗ 2 = . . . = t ∗ L−2.
Theorem 3.1. Optimal layer weights for equation 14 satisfy the following relation
W∗l =  t∗ Vxw̃ ∗ r ‖w̃∗r‖2 ρT1 if l = 1 t∗ρl−1ρ T l if 1 < l ≤ L− 2
ρL−2 if l = L− 1 ,
where ‖ρl‖2 = 1, ∀l ∈ [L− 2] and w̃∗r follows the definition in equation 8.
Proof of Theorem 3.1. Using Lemma A.3 and Proposition 3.1, we have the following dual problem for equation 14
P ∗ = min {θl}L−1l=1 ,t max λ λTy + (L− 2)t2 s.t. |(XW1 . . .wL−1,j)Tλ| ≤ 1, wL−1,j ∈ B2 (23)
‖Wl‖F ≤ t, ∀l ∈ [L− 2].
Now, let us assume that the optimal Frobenius norm for each layer l is t∗ 10. Then, if we define ΘL−1 = {θ1, . . . , θL−1|‖wL−1,j‖2 ≤ 1,∀j ∈ [mL−1], ‖Wl‖F ≤ t∗, ∀l ∈ [L − 2]}, equation 23 reduces to the following problem
P ∗ ≥ D∗ = max λ λTy s.t. |(XW1 . . .wL−1)Tλ| ≤ 1, ∀θl ∈ ΘL−1, ∀l, (24)
where we change the order of min-max to obtain a lower bound for equation 23. The dual of the semi-infinite problem in equation 24 is given by
min ‖µ‖TV s.t. ∫ {θl}L−1l=1 ∈ΘL−1 XW1 . . .wL−1dµ(θ1, . . . , θL−1) = y , (25)
where µ is a signed Radon measure and ‖ · ‖TV is the total variation norm. We emphasize that equation 25 has infinite width in each layer, however, an application of Caratheodory’s theorem shows that the measure µ in the integral can be represented by finitely many (at most n + 1) Dirac delta functions (Rosset et al., 2007). Such selection of µ yields the following problem
P ∗m = min {θl}Ll=1 ‖wL‖1 s.t. mL−1∑ j=1 XWj1 . . .w j L−1wL,j = y, θ j l ∈ ΘL−1, ∀l (26)
We first note that since the model in equation 26 has multiple weight matrices for each layer, it has more expressive power than a regular network. Thus, we have P ∗ ≥ P ∗m. Since the dual of equation 14 and equation 26 are the same, we also have D∗m = D
∗, where D∗m is the optimal dual value for equation 26.
We now apply the variable change in equation 7 to equation 24 as follows
max λ
λ̃TΣxw̃ ∗ r s.t. ‖WTL−2 . . .WT1 VxΣTx λ̃‖2 ≤ 1, ∀θl ∈ ΘL−1, ∀l (27)
10With this assumption, (L− 2)t2 becomes constant so we ignore this term for the rest of our derivations.
which shows that the maximum objective value is achieved when ΣTx λ̃ = c1w̃ ∗ r . Thus, the optimal layer weights can be found as the maximizers of the constraint when ΣTx λ̃ = c1w̃ ∗ r . To find the formulations explicitly, we first find an upper-bound for the constraint in equation 27 as follows
‖WTL−2 . . .WT1 VxΣTx λ̃‖2 = c1‖WTL−2 . . .WT1 Vxw̃∗r‖2 ≤ c1‖WL−2‖2 . . . ‖Vxw̃∗r‖2 ≤ c1γ‖Vxw̃∗r‖2,
where the last inequality follows from the constraint on each layer weight’s norm and γ = t∗ L−2
. This upper-bound can be achieved when the layer weights are
W∗l =  t∗ Vxw̃ ∗ r ‖w̃∗r‖2 ρT1 if l = 1 t∗ρl−1ρ T l if 1 < l ≤ L− 2
ρL−2 if l = L− 1 , (28)
where ‖ρl‖2 = 1, ∀l ∈ [L − 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., {ρl}L−2l=1 can be chosen to achieve the maximum dual objective.
We note that the layer weights in equation 28 are optimal for the relaxed problem in equation 26. However, since there exists a single possible choice for the left singular vector of W1 and we can select an arbitrary set for {ρl}L−2l=1 , we achieve D∗m = 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
W∗l =  t∗ ∑K j=1 ṽw,jρ T 1,j if l = 1 t∗ ∑K j=1 ρl−1,jρ T l,j if 1 < l ≤ L− 2∑K
j=1 ρL−2,j if l = L− 1 ,
where ṽw,j is the jth maximal right singular vector of ΛTX and we may pick a set of unit norm vectors {ρl,j}L−2l=1 such that ρTl,jρl,k = 0, ∀j 6= k.
Proof of Theorem 3.3. Using Proposition 3.1 and Lemma A.4, we obtain the following dual problem
max Λ
trace(ΛTY) s.t. σmax(ΛTXW1 . . .WL−2) ≤ 1, ∀θl ∈ ΘL−1. (29)
It is straightforward to show that the optimal layer weights are the extreme points of the constraint in equation 29, which achieves the following upper-bound
max {θl}L−2l=1 ∈ΘL−1
σmax(Λ TXW1 . . .WL−2) ≤ σmax(ΛTX)γ.
This upper-bound is achieved when the first L−2 layer weights are rank-one with the singular value t∗ by Proposition 3.1. Additionally, the left singular vector of W1 needs to align with one of the maximum right singular vectors of ΛTX. Since the upper-bound for the objective is achievable for any Λ, we can maximize the objective value, as in equation 13, by choosing a matrix Λ such that
ΛTUxΣx = Vw
[ γ−1Irw 0rx×d−rw
0k−rw×rx 0k−rw×d−rw
] UTw
where W∗r = UwΣwV T w. Thus, a set of optimal layer weights can be formulated as follows
Wjl =  t∗ṽw,jρ T 1,j if l = 1 t∗ρl−1,jρ T l,j if 1 < l ≤ L− 2
ρL−2,j if l = L− 1 , (30)
where ṽw,j is the jth maximal right singular vector of ΛTX. However, notice that the layer weights in equation 30 are the optimal weights for the relaxed problem, i.e.,
min {θl}Ll=1 mL−1∑ j=1 ‖wL,j‖2 s.t. mL−1∑ j=1 XWj1 . . .w j L−1w T L,j = Y, ∀θ j l ∈ ΘL−1. (31)
Using the optimal layer weights in equation 30, we have the following network output for the relaxed model
mL−1∑ j=1 XWj1 . . .w j L−1w T L,j = γ mL−1∑ j=1 qw,jw T L,j .
Since we know that the objective value for equation 31 is a lower bound for equation 15, the layer weights that achieve the output above for the original problem in equation 15 is optimal. Thus, a set of optimal solutions to equation 15 can be formulated as follows
W∗l =  t∗ ∑mL−1 j=1 ṽw,jρ T 1,j if l = 1 t∗ ∑mL−1 j=1 ρl−1,jρ T l,j if 1 < l ≤ L− 2∑mL−1
j=1 ρL−2,j if l = L− 1 (32)
where we select a set of unit norm vectors {ρl,j}L−2l=1 such that ρTl,jρl,k = 0, ∀j 6= k.
Theorem 3.2. Let {X,y} be feasible for equation 14, then strong duality holds for finite width networks.
Proof of Theorem 3.2. We first select a set of unit norm vectors, i.e., {ρl}L−2l=1 , to construct weight matrices {Wel } L−1 l=1 that satisfies equation 28. Then, the dual of equation 14 can be written as
D∗e = max λ λTy
s.t. |(XWe1 . . .weL−1)Tλ| ≤ 1 .
Then, we have
P ∗ = min {θl}L−1l=1 ∈ΘL−1 max λ λTy ≥ max λ λTy (33)
s.t. |(XW1 . . .wL−1)Tλ| ≤ 1 s.t. |(XW1 . . .wL−1)Tλ| ≤ 1, ∀θl ∈ ΘL−1 = max
λ λTy
s.t. |(XWe1 . . .weL−1)Tλ| ≤ 1 = D∗e = D ∗ = D∗m
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 {Wel } L−1 l=1 maximizes the dual problem. Furthermore, we have the following relation between the primal problems
P ∗e = min wL ‖wL‖1 ≥ P ∗ = min {θl}Ll=1∈ΘL−1 ‖wL‖1 (34) s.t. We1 . . .W e L−1wL = y s.t. W1 . . .WL−1wL = 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 it is an `1-norm minimization problem with linear equality constraints. Therefore, strong duality holds for this problem, i.e., P ∗e = D ∗ e and we have P ∗ e ≥ P ∗ ≥ P ∗m ≥ D∗e = D∗ = D∗m. Using this result along with equation 33, we prove that strong duality holds, i.e., P ∗e = P ∗ = P ∗m = D ∗ e = D
∗ = D∗m.
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., XW1ρ1 = cy, where c > 0. Therefore, the remaining layers do not contribute to 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.
Proof of Corollary A.1. The proof directly follows from the analysis in this section and Theorem 3.2.
Lemma A.4. The following problems are equivalent:
min {θl}Ll=1 L∑ l=1 ‖Wl‖2F
s.t. fθ,L(X) = Y
= min
{θl}Ll=1,{tl} L−2 l=1 mL−1∑ j=1 ‖wL,j‖2 + L−2∑ l=1 t2l
s.t. fθ,L(X) = Y, wL−1,j ∈ B2, ‖Wl‖F ≤ tl, ∀l ∈ [L− 2]
.
Proof of Lemma A.4. Applying the scaling trick in Lemma A.1 to the last two layer of the L-layer network in equation 15 gives
min {θl}Ll=1,{tl} L−2 l=1 mL−1∑ j=1 ‖wL,j‖2 + L−2∑ l=1 ‖Wl‖2F
s.t. ‖wL−1,j‖2 ≤ 1,∀j ∈ [mL−1] XW1 . . .WL−1WL = Y
.
Then, we use the epigraph form for the norm of the first L− 2 to achieve the equivalence.
Theorem 3.4. Let {X,y} be feasible for equation 15, then strong duality holds for finite width networks.
Proof of Theorem 3.4. We first select a set of unit norm vectors, i.e., {ρl,j}L−2l=1 , to construct weight matrices {We,jl } L−1 l=1 that satisfies equation 30. Then, the dual of equation 15 can be written as
D∗e = max Λ trace(ΛTY)
s.t. σmax(ΛTXW e,j 1 . . .W e,j L−2) ≤ 1, ∀j
.
Then, we have
P ∗ = min {θl}L−1l=1 ∈ΘL−1 max Λ trace(ΛTY) ≥ max Λ trace(ΛTY) (35)
s.t. σmax(ΛTXW1 . . .WL−2) ≤ 1 s.t. σmax(ΛTXW1 . . .WL−2) ≤ 1, ∀θl ∈ ΘL−1 = max
Λ trace(ΛTY)
s.t. σmax(ΛTXW e,j 1 . . .W e,j L−2) ≤ 1, ∀j
= D∗e = D ∗ = D∗m
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 {We,jl } L−1 l=1 maximizes the dual problem. Furthermore, we have the following relation between the primal problems
P ∗e = min WL mL−1∑ j=1 ‖wL,j‖2 ≥ P ∗ = min {θl}Ll=1∈ΘL−1 mL−1∑ j=1 ‖wL,j‖2 (36)
s.t. mL−1∑ j=1 We,j1 . . .W e,j L−1w T L,j = Y s.t. W1 . . .WL−1WL = 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 36 is convex since it is an `2-norm minimization problem with linear equality constraints. Therefore, strong duality holds for this problem, i.e., P ∗e = D ∗ e and we have P ∗ e ≥ P ∗ ≥ P ∗m ≥ D∗e = D∗ = D∗m. Using this result along with equation 35, we prove that strong duality holds, i.e., P ∗e = P ∗ = P ∗m = D ∗ e = D
∗ = D∗m.

heading: A.7 PROOFS FOR THE DEEP RELU NETWORKS
text: Theorem 4.1. Let X be a rank-one data matrix such that X = caT0 , where c ∈ Rn+ and a0 ∈ Rd, then strong duality holds and the optimal weights for each layer can be formulated as follows
Wl = φl−1 ‖φl−1‖2 φTl , ∀l ∈ [L− 2], wL−1 = φL−2 ‖φL−2‖2 ,
where φ0 = a0 and {φl}L−2l=1 is a set of vectors such that φl ∈ R ml + and ‖φl‖2 = t∗, ∀l ∈ [L− 2]. Proposition 1. First L−2 hidden layer weight matrices in equation 16 have the same operator and Frobenius norms.
Proof of Proposition 1. Let us first denote the sum of the norms for the first L − 2 layer as t, i.e., t = ∑L−2 l=1 tl, where tl = ‖Wl‖2 = ‖Wl‖F 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 {θl}L−2l=1
|λ∗ T
c| ‖aL−2‖2 = arg max {θl}L−2l=1 ∈ΘL−1
|λ∗ T
c| ‖(aTL−3WL−2)+‖2
where we use aTL−2 = (a T L−3WL−2)+. Since ‖WL−2‖F = tL−2 = t − ∑L−3 l=1 , the objective
value above becomes |λ∗T c| ‖(aL−3‖2 ( t− ∑L−3 l=1 ) . Applying this step to all the remaining layer weights gives the following problem
arg max {tl}L−3l=1 ∈ΘL−1
|λ∗ T c| ‖a0‖2 ( t−
L−3∑ l=1 ) L−3∏ j=1 tl s.t. s.t. L−3∑ l=1 tl ≤ t, tl ≥ 0.
Then, the proof directly follows from Proof of Proposition 3.1.
Proof of Theorem 4.1. Using Lemma A.3 and Proposition 1, this problem can be equivalently stated as
min {θl}Ll=1∈ΘL−1
‖wL‖1 s.t. Al = (Al−1Wl)+, ∀l ∈ [L− 1]
AL−1wL = y , (37)
which also has the following dual form
P ∗ = min {θl}L−1l=1 ∈ΘL−1 max λ λTy
s.t. ‖ATL−1λ‖∞ ≤ 1 . (38)
Notice that we remove the recursive constraint in equation 38 for notational simplicity, however, AL−1 is still a function of all the layer weights except wL. Changing the order of min-max in equation 38 gives
P ∗ ≥ D∗ = max λ λTy s.t. ‖ATL−1λ‖∞ ≤ 1, ∀θl ∈ ΘL−1, ∀l ∈ [L− 1]. (39)
The dual of the semi-infinite problem in equation 39 is given by
min ‖µ‖TV s.t. ∫ {θl}L−1l=1 ∈ΘL−1 ( AL−2wL−1 ) + dµ(θ1, . . . , θL−1) = y ,
(40)
where µ is a signed Radon measure and ‖ · ‖TV is the total variation norm. We emphasize that equation 40 has infinite width in each layer, however, an application of Caratheodory’s theorem shows that the measure µ in the integral can be represented by finitely many (at most n + 1) Dirac delta functions (Rosset et al., 2007). Thus, we choose
µ = mL−1∑ j=1 δ(W1 −Wj1, . . . ,wL−1 −w j L−1)wL,j ,
where δ(·) is the Dirac delta function and the superscript indicates a particular choice for the corresponding layer weight. This selection of µ yields the following problem
P ∗m = min {θl}Ll=1 ‖wL‖1
s.t. mL−1∑ j=1 ( AjL−2w j L−1 ) + wL,j = y, θ j l ∈ ΘL−1, ∀l ∈ [L− 1] . (41)
Here, we first note that even though the model in equation 41 has the same layer widths with regular deep ReLU networks, it has more expressive power since it allows us to choose multiple weight matrices for each layer. Based on this observation, we have P ∗ ≥ P ∗m. As a consequence of equation 39, we can characterize the optimal layer weights for equation 41 as the extreme points that solve
arg max {θl}L−1l=1 ∈ΘL−1
|λ∗ T (AL−2wL−1)+| (42)
where λ∗ is the optimal dual parameter. Since we assume that X = caT0 with c ∈ Rn+, we have AL−2 = ca T L−2, where a T l = (a T l−1Wl)+, al ∈ R ml + and ∀l ∈ [L− 1]. Based on this observation, we have wL−1 = aL−2/‖aL−2‖2, which reduces equation 42 to the following
arg max {θl}L−2l=1 ∈ΘL−1
|λ∗ T c| ‖aL−2‖2 (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 `2 norms vector for the neuron in the lth layer as φl ∈ Rml+ , then we have the following formulation for the layer weights that solve equation 42
Wl = φl−1 ‖φl−1‖2 φTl , ∀l ∈ [L− 2], wL−1 = φL−2 ‖φL−2‖2 , (44)
where φ0 = a0, {φl}L−2l=1 is a set of nonnegative vectors satisfying ‖φl‖2 = t∗, ∀l ∈ [L− 2]. We note that the layer weights in equation 44 are optimal for the relaxed problem in equation 41. However, since there exists a single possible choice for the left singular vector of W1 and we can select an arbitrary set for {φl}L−2l=1 , the dual problems coincide for equation 16 and equation 41, i.e., we achieve D∗m = D
∗ using the same layer weights, where D∗m is the optimal dual objective value for equation 41. Therefore, the set of weights in equation 44 are also optimal for equation 16.
Theorem 4.2. Let X be a data matrix such that X = caT0 , where c ∈ Rn and a0 ∈ Rd. Then, a set of optimal solutions to equation 16 satisfies {(wi, bi)}mi=1, where wi = si a0‖a0‖2 , bi = −sici‖a0‖2 with si = ±1,∀i ∈ [m].
Proof of Theorem 4.2. Given X = caT0 , all possible extreme points can be characterized as follows arg max b,w:‖w‖2=1 |λT ( Xw + b1 ) + | = arg max b,w:‖w‖2=1 |λT ( caT0 w + b1 ) + |
= arg max b,w:‖w‖2=1 ∣∣∣ n∑ i=1 λi ( cia T 0 w + b ) + ∣∣∣ which can be equivalently stated as
arg max b,w:‖w‖2=1 ∑ i∈S λicia T 0 w + ∑ i∈S λib s.t. { cia T 0 w + b ≥ 0,∀i ∈ S cja T 0 w + b ≤ 0,∀j ∈ Sc ,
which shows that w must be either positively or negatively aligned with a0, i.e., w = s a0‖a0‖2 , where s = ±1. Thus, bmust be in the range of [maxi∈S(−sci‖a0‖2), minj∈Sc(−scj‖a0‖2)] Using these observations, extreme points can be formulated as follows
wλ =
{ a0 ‖a0‖2 if ∑ i∈S λici ≥ 0
−a0 ‖a0‖2 otherwise
and bλ = { minj∈Sc(−sλcj‖a0‖2) if ∑ i∈S λi ≥ 0
maxi∈S(−sλci‖a0‖2) otherwise ,
where sλ = sign( ∑ i∈S λici).
Proposition 4.1. Theorem 4.1 still holds when we add a bias term to the last hidden layer, i.e., the output becomes ( AL−2WL−1 + 1nb T )
+ wL = y, where Al = (Al−1Wl)+, ∀l ∈ [L− 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 to the bias term. Thus, equation 42 changes as
arg max {θl}L−1l=1 ∈ΘL−1,b
|λ∗ T
(AL−2wL−1 + b1n)+| = arg max {θl}L−1l=1 ∈ΘL−1,b
|λ∗ T ( caTL−2wL−1 + b1n ) + |
= arg max {θl}L−2l=1 ∈ΘL−1,b ∣∣∣ n∑ i=1 λ∗i ( cia T L−1wL−1 + b ) + ∣∣∣ (45)
which can also be written as
arg max {θl}L−1l=1 ∈ΘL−1,b ∑ i∈S λ∗i cia T L−2wL−1 + ∑ i∈S λ∗i b s.t. { cia T L−2wL−1 + b ≥ 0,∀i ∈ S cja T L−2wL−1 + b ≤ 0,∀j ∈ Sc ,
where S and Sc are the indices for which ReLU is active and inactive, respectively. This shows that wL−1 must be wL−1 = ±1 aL−2‖aL−2‖2 and b ∈ [maxi∈S(−ci‖aL−2‖2), minj∈Sc(−cj‖aL−2‖2)]. Then, we obtain the following
w∗L−1 =
{ aL−2 ‖aL−2‖2 if ∑ i∈S λ ∗ i ci ≥ 0
−aL−2 ‖aL−2‖2 otherwise
and b∗ = { minj∈Sc(−sλ∗cj‖aL−2‖2) if ∑ i∈S λ ∗ i ≥ 0
maxi∈S(−sλ∗ci‖aL−2‖2) otherwise ,
(46) where sλ∗ = sign( ∑ i∈S λ ∗ i ci). This result reduces equation 45 to the following problem
arg max {θl}L−21 ∈ΘL−1
|C(λ∗, c)| ‖aL−2‖2,
where C(λ∗, c) is constant scalar independent of {Wl}L−2l=1 . Hence, this problem and its solutions are the same with equation 43 and equation 44, respectively.
Corollary 4.1. As a result of Theorem 4.2, when we have one dimensional data, i.e., x ∈ Rn, an optimal solution to equation 16 can be formulated as {(wi, bi)}mi=1, where wi = si, bi = −sixi with si = ±1,∀i ∈ [m]. Therefore, the optimal network output has kinks only at the input data points, i.e., the output function is in the following form: fθ,2(x̂) = ∑ i ( x̂ − xi ) +
. Therefore, the network output becomes linear spline interpolation for one dimensional datasets. Corollary 4.2. As a result of Theorem 4.2 and Proposition 4.1, when we have one dimensional data, i.e., x ∈ Rn, the optimal network output has kinks only at the input data points, i.e., the output function is in the following form: fθ,L(x̂) = ∑ i ( x̂− xi ) +
. Therefore, the network output becomes linear spline interpolation for one dimensional datasets.
Proof of Corollary 4.1 and 4.2. Let us particularly consider the input sample a0. Then, the activations of the network defined by equation 44 and equation 46 are
aT1 = (a T 0 W1)+ = ( aT0
a0 ‖a0‖2 φT1 ) + = ‖a0‖2φT1
aT2 = (a T 1 W2)+ = ( aT1
a1 ‖a1‖2 φT2 ) + = ‖a0‖2‖φT1 ‖2φT2
...
aTL−2 = (a T L−3WL−2)+ = ( aTL−3
aL−3 ‖aL−3‖2 φTL−2 ) + = ‖a0‖2‖φT1 ‖2 . . . ‖φTL−3‖2φTL−2
aL−1 = (a T L−2wL−1 + b)+ = (‖aL−2‖2 − ‖aL−2‖2)+ = 0.
Thus, if we feed cia0 to the network, we get aL−1 = (ci‖aL−2‖2 − ci‖aL−2‖2)+ = 0, where we use the fact that optimal biases are in the form of b = −ci‖aL−2‖2 as proved in equation 46. This analysis proves that the kink of each ReLU activation occurs exactly at one of the data points.
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 {θl}Ll=1 L∑ l=1 ‖Wl‖2F s.t. fθ,L(X) = Y.
After a suitable rescaling as in the previous case, the above problem has the following dual
P ∗ ≥ D∗ = max λ
trace(ΛTY) s.t. ‖ΛT ( AL−2wL−1 ) + ‖2 ≤ 1, ∀θl ∈ ΘL−1, ∀l ∈ [L− 1]. (47)
Using equation 47, we can characterize the optimal layer weights as the extreme points that solve
arg max {θl}L−1l=1 ∈ΘL−1
‖Λ∗ T (AL−2wL−1)+‖2, (48)
where Λ∗ is the optimal dual parameter. Since we assume that X = caT0 with c ∈ Rn+, we have AL−2 = ca T L−2, where a T l = (a T l−1Wl)+, al ∈ R ml + and ∀l ∈ [L− 1]. Based on this observation, we have wL−1 = aL−2/‖aL−2‖2, which reduces equation 48 to the following
arg max {θl}L−2l=1 ∈ΘL−1
‖Λ∗ T c‖2 ‖aL−2‖2.
Then, the rest of steps directly follow Theorem 4.1 yielding the following weight matrices
Wl = φl−1 ‖φl−1‖2 φTl , ∀l ∈ [L− 2], wL−1 = φL−2 ‖φL−2‖2 ,
where φ0 = a0, {φl}L−2l=1 is a set of nonnegative vectors satisfying ‖φl‖2 = t∗, ∀l ∈ [L − 2]. Moreover, as a direct consequence of Theorem 3.4, strong duality holds for deep ReLU networks.
Theorem 4.3. Let {X,Y} be a dataset such that XXT = In11 and Y has orthogonal columns, then the optimal weight matrices for each layer can be formulated as follows
Wl = 1√ 2K 2K∑ r=1 φl−1,r ‖φl−1,r‖2 φTl,r, ∀l ∈ [L− 2], WL−1 = 1√ 2K [ φL−2,1 ‖φL−2,1‖2 . . . φL−2,2K ‖φL−2,2K‖2 ] ,
where (φ0,2j−1,φ0,2j) = ( XT ( yj )
+ ,XT
( − yj ) + ) , ∀j ∈ [K] and {φl,r}L−2l=1 is a set of vectors
such that φl,r ∈ Rml+ , ‖φl,r‖2 = t∗, and φTl,iφl,j = 0, ∀i 6= j.
Proof of Theorem 4.3. For vector outputs, we have the following training problem
min {θl}Ll=1 L∑ l=1 ‖Wl‖2F s.t. fθ,L(X) = Y.
After a suitable rescaling as in the previous case, the above problem has the following dual
P ∗ ≥ D∗ = max λ
trace(ΛTY) s.t. ‖ΛT ( AL−2wL−1 ) + ‖2 ≤ 1, ∀θl ∈ ΘL−1, ∀l ∈ [L− 1]. (49)
Using equation 49, we can characterize the optimal layer weights as the extreme points that solve
arg max {θl}L−1l=1 ∈ΘL−1
‖Λ∗ T (AL−2wL−1)+‖2, (50)
where Λ∗ is the optimal dual parameter. We first note that since X is whitened such that XXT = In, equation 50 implies σmax(Λ∗) ≤ t∗ L−2 . Then, the objective is trivially maximized by Λ∗ =
11This can be achieved by applying batch whitening, which often improves accuracy (Huang et al., 2018).
t∗ L−2
Y/σmax(Y), which is also a feasible solution. Therefore, equation 50 can be equivalently written as
arg max {θl}L−1l=1 ∈ΘL−1
‖YT (AL−2wL−1)+‖2. (51)
We now note that since Y has orthogonal columns, equation 51 can be decomposed into k maximization problems each of which can be maximized independently to find a set of extreme points. In particular, the jth problem can be formulated as follows
arg max {θl}L−1l=1 ∈ΘL−1
|yTj (AL−2wL−1)+| ≤ max { ‖ ( yj ) + ‖2, ‖ ( −yj ) + ‖2 } .
Then, noting the whitened data assumption, the rest of steps directly follow Theorem 4.1 yielding the following weight matrices
Wl = 1√ 2 2∑ r=1 φl−1,r ‖φl−1,r‖2 φTl,r, ∀l ∈ [L− 2], WL−1 = 1√ 2 [ φL−2,1 ‖φL−2,1‖2 φL−2,2 ‖φL−2,2‖2 ] ,
where φ0,r = XT ( ± yj ) +
and {φl,r}L−2l=1 is a set of nonnegative vectors satisfying ‖φl,r‖2 = t∗ and φTl,1φl,2 = 0, ∀l. Thus, combining the extreme points for each j yields
Wl = 1√ 2K 2K∑ r=1 φl−1,r ‖φl−1,r‖2 φTl,r, ∀l ∈ [L− 2], WL−1 = 1√ 2K [ φL−2,1 ‖φL−2,1‖2 . . . φL−2,2K ‖φL−2,2K‖2 ] ,
where (φ0,2j−1,φ0,2j) = ( XT ( yj )
+ ,XT
( − yj ) + ) , ∀j ∈ [K] and {φl,r}L−2l=1 is a set of nonneg-
ative vectors satisfying ‖φl,r‖2 = t∗ and φTl,iφl,j = 0 ∀i 6= j. 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 XTX = In and Y has orthogonal columns, then a set of optimal layer weight matrices for the following regularized training problem
min θ∈Θ
1 2 ‖fθ,L(X)−Y‖2F + β 2 L∑ l=1 ‖Wl‖2F (17)
can be formulated as follows
Wl =
{∑2K r=1 φl−1,r ‖φl−1,r‖2φ
T l,r, if 1 ≤ l ≤ L− 1∑2K
r=1 (‖φ0,r‖2 − β)φl−1,rêTr if l = L ,
where ê2j−1 = ê2j = ej , ∀j ∈ [K], ej is the jth ordinary basis vector, and the other definitions follows from Theorem 4.3 except t∗ = 1.
Proof of Theorem 4.4. From Section A.4.2 and the proof of Theorem 4.3, the dual problem has a closed-form solution as follows
λ∗j =
{ β
yj ‖yj‖2 if β ≤ ‖yj‖2 yj otherwise , ∀j ∈ [K]. (52)
and the corresponding extreme points of the constraint in Wl = {∑2K
r=1 φl−1,r ‖φl−1,r‖2φ T l,r, if 1 ≤ l ≤ L− 1 , (53)
where the definitions follows from Theorem 4.3.
We now note 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 WL. 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
WL = 2K∑ r=1 (‖φ0,r‖2 − β)φL−1,rêTr ,
where ê2j−1 = ê2j = ej , ∀j ∈ [K] and ej is the jth ordinary basis vector.

Review summaries:
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.  

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.