PARALLEL DEEP NEURAL NETWORKS HAVE ZERO DUALITY GAP
Year: 2021

Abstract:
Training deep neural networks is a well-known highly non-convex problem. In recent work (Pilanci & Ergen, 2020), it is shown that there is no duality gap for regularized two-layer neural networks with ReLU activation, which enables global optimization via convex programs. For multi-layer linear networks with vector outputs, we formulate convex dual problems and demonstrate that the duality gap is non-zero for depth three and deeper networks. However, by modifying the deep networks to more powerful parallel architectures, we show that the duality gap is exactly zero. Therefore, strong convex duality holds, and hence there exist equivalent convex programs that enable training deep networks to global optimality. We also demonstrate that the weight decay regularization in the parameters explicitly encourages low-rank solutions via closed-form expressions. For threelayer non-parallel ReLU networks, we show that strong duality holds for rank-1 data matrices, however, the duality gap is non-zero for whitened data matrices. Similarly, by transforming the neural network architecture into a corresponding parallel version, the duality gap vanishes.

heading: 1 INTRODUCTION
text: Deep neural networks demonstrate outstanding representation and generalization abilities in popular learning problems ranging from computer vision, natural language processing to recommendation system. Although the training problem of deep neural networks is a highly non-convex optimization problem, simple algorithms, such as stochastic gradient descent, can find a solution with good generalization properties. The non-convex and non-linear nature of neural networks render the theoretical understanding of neural networks extremely challenging.
The Lagrangian dual problem (Boyd et al., 2004) plays an important role in the theory of convex and non-convex optimization. For convex optimization problems, the convex duality is an important tool to determine its optimal value and to characterize the optimal solutions. Even for a non-convex primal problem, the dual problem is a convex optimization problem the can be solved efficiently. As a result of weak duality, the optimal value of the dual problem serves as a non-trivial lower bound for the optimal primal objective value. Although the duality gap is non-zero for non-convex problems, the dual problem provides a convex relaxation of the non-convex primal problem. For example, the semi-definite programming relaxation of the two-way partitioning problem can be derived from its dual problem Boyd et al. (2004).
The convex duality also has important applications in machine learning. In (Paternain et al., 2019), the design problem of an all-encompassing reward can be formulated as a constrained reinforcement learning problem, which is shown to have zero duality. This property gives a theoretical convergence guarantee of the primal-dual algorithm for solving this problem. Meanwhile, the minimax generative adversarial net (GAN) training problem can be tackled using duality (Farnia & Tse, 2018).
In lines of recent works, the convex duality can also be applied for analyzing the optimal layer weights of two-layer neural networks with linear or ReLU activations (Pilanci & Ergen, 2020; Ergen & Pilanci, 2020a). Based on the convex duality framework, the training problem of two-layer neural networks with ReLU activation can be represented in terms of a single convex program in (Pilanci & Ergen, 2020). Such convex optimization formulations are extended to two-layer and three-layer convolutional neural network training problems in (Ergen & Pilanci, 2020c). Strong duality also holds for deep linear neural networks with scalar output (Ergen & Pilanci, 2020b). The convex
optimization formulation essentially gives a detailed characterization of the global optimum of the training problem. This enables us to examine in numerical experiments whether popular optimizers for neural networks, such as gradient descent or stochastic gradient descent, converge to the global optimum of the training loss.
Admittedly, the zero duality gap is hard to achieve for deep neural networks, especially for those with vector outputs. This imposes more difficulty to train deep neural networks. Fortunately, neural networks with parallel structures (also known as multi-branch architecture) appear to be easier to train. Practically, the usage of parallel neural networks dates back to AlexNet (Krizhevsky et al., 2012). Modern neural network architecture including Inception (Szegedy et al., 2017), Xception (Chollet, 2017) and SqueezeNet (Iandola et al., 2016) utilize the parallel structure. As the “parallel” version of ResNet (He et al., 2016a;b), ResNeXt (Xie et al., 2017) and Wide ResNet (Zagoruyko & Komodakis, 2016) exhibit improved performance on many applications. Recently, it was shown that neural networks with the parallel architecture have smaller duality gaps (Zhang et al., 2019) compared to standard neural networks. On the other hand, it is known that overparameterized parallel neural networks have benign training landscapes (Haeffele & Vidal, 2017). For training `2 loss with deep linear networks using Schatten norm regularization, Zhang et al. (2019) show that there is no duality gap. From another perspective, the standard two-layer network is equivalent to the parallel two-layer network. This may also explain why there is no duality gap for two-layer neural networks.

heading: 1.1 CONTRIBUTIONS
text: Following the convex duality framework introduced in (Ergen & Pilanci, 2020b;a), which showed the duality gap is zero for two-layer networks, we go beyond two-layer and study the convex duality for vector-output deep neural networks with linear activation and ReLU activation. Surprisingly, we prove that three-layer networks may have duality gaps depending on their architecture, unlike two-layer neural networks which always have zero duality gap. We summarize our contributions as follows.
• For training standard vector-output deep linear networks using `2 regularization, we precisely calculate the optimal value of the primal and dual problems and show that the duality gap is non-zero, i.e., Lagrangian relaxation is inexact. We also demonstrate that the `2- regularization on the parameter explicitly forces a tendency toward a low-rank solution, which is boosted with the depth. However, we show that the optimal solution is available in closed-form.
• For parallel deep linear networks, with certain convex regularization, we show that the duality gap is zero, i.e, Lagrangian relaxation is exact.
• For training vector-output three-layer ReLU networks with standard architecture using `2 regularization, even when the data is whitened, we show that the duality gap is non-zero. The gap can be closed by replacing the neural network to one with parallel architecture.
• For parallel deep ReLU networks of arbitrary depth, with certain convex regularization, we prove strong duality, i.e., the duality gap is zero. Remarkably, this guarantees that there is a convex program equivalent to the original deep ReLU neural network problem.
We summarize the duality gaps for parallel/standard neural network in Table 1.

heading: 1.2 NOTATIONS
text: We use bold capital letters to represent matrices and bold lowercase letters to represent vectors. Denote [n] = {1, . . . , n}. For a matrix Wl ∈ Rm1×m2 , for i ∈ [m1] and j ∈ [m2], we denote wcoll,i as its i-th column and wrowl,j as its j-th row. Throughout the paper, X ∈ RN×d is the data matrix consisting of d dimensional N samples and Y ∈ RN×K is the label matrix for a regression/classification task with K outputs.

heading: 1.3 MOTIVATIONS AND BACKGROUND
text: Recently a series of papers (Pilanci & Ergen, 2020; Ergen & Pilanci, 2020b;a) studied two-layer neural networks via convex duality and proved that strong duality holds for these architectures.
Particularly, these prior works consider the following weight decay regularized training framework for classification/regression tasks. Given a data matrix X ∈ RN×d consisting of d dimensional N samples and the corresponding label matrix y ∈ RN , the weight-decay regularized training problem for a scalar-output neural network with m hidden neurons can be written as follows
P := min W1,w2
1 2 ‖φ(XW1)w2 − y‖22 + β 2 (‖W1‖2F + ‖w2‖22), (1)
where W1 ∈ Rd×m and w2 ∈ Rm are the layer weights, β > 0 is a regularization parameter, and φ is the activation function, which can be linear φ(z) = z or ReLU φ(z) = max{z, 0}. Then, one can take the dual of (1) with respect to W1 and w2 obtain the following dual optimization problem
D := max λ −1 2 ‖λ− y‖22 + 1 2 ‖y‖22, s.t. max w1:‖w1‖2≤1 |λTφ(Xw1)| ≤ β. (2)
We first note that since the training problem (1) is non-convex, strong duality may not hold, i.e., P ≥ D. Surprisingly, as shown in Pilanci & Ergen (2020); Ergen & Pilanci (2020b;a), strong duality in fact holds, i.e., P = D, for two-layer networks and therefore one can derive exact convex representations for the non-convex training problem in (1). However, extensions of this approach to deeper and state-of-the-art architectures are not available in the literature. Based on this observation, the central question we address in this paper is:
Does strong duality hold for deep neural networks?
Depending on the answer to the question above, an immediate next questions we address is
Can we characterize the duality gap (P-D)? Is there an architecture for which strong duality holds independent of the depth?
Consequently, throughout the paper, we provide a full characterization of convex duality for deeper neural networks. Then, based on this characterization, we propose a modified architecture for which strong duality holds regardless of depth.

heading: 1.4 CONVEX DUALITY FOR TWO-LAYER NEURAL NETWORKS
text: We briefly review the convex duality for two-layer neural networks introduced in (Ergen & Pilanci, 2020b;a). Consider the following weight-decay regularized training problem for a vector-output neural network architecture with m hidden neurons
min W1,W2
1 2 ‖φ(XW1)W2 −Y‖2F + β 2 (‖W1‖2F + ‖W2‖2F ), (3)
where W1 ∈ Rd×m and W2 ∈ Rm×K are the variables, and β > 0 is a regularization parameter. Here φ is the activation function, which can be linear φ(z) = z or ReLU φ(z) = max{z, 0}. As long as the network is sufficiently overparameterized, there exists a feasible solution for such that φ(XW1)W2 = Y. Then, a minimal norm variant1 of the training problem in (3) is given by
min W1,W2
1 2 (‖W1‖2F + ‖W2‖2F ) s.t. φ(XW1)W2 = Y. (4)
As shown in (Pilanci & Ergen, 2020), after a suitable rescaling, this problem can be reformulated as
min W1,W2 m∑ j=1 ‖wrow2,j ‖2 s.t. φ(XW1)W2 = Y, ‖wcol1,j‖2 ≤ 1, j ∈ [m]. (5)
where [m] = {1, . . . ,m}. Here wrow2,j represents the j-th row of W2 and wcol1,j denotes the j-th column of W1. The rescaling does not change the solution to (4). By taking the dual with respect to W1 and W2, the dual problem of (5) with respect to variables is a convex optimization problem given by
max Λ tr(ΛTY), s.t. max u:‖u‖2≤1 ‖ΛTφ(Xu)‖2 ≤ 1, (6)
where Λ ∈ RN×K is the dual variable. Provided that m ≥ m∗, where m∗ ≤ N + 1, the strong duality holds, i.e., the optimal value of the primal problem (5) equals to the optimal value of the dual problem (6).

heading: 1.5 ORGANIZATION
text: This paper is organized as follows. In Section 2, we review standard neural networks and introduce parallel architectures. For deep linear networks, we derive primal and dual problems for both standard and parallel architectures and provide calculations of optimal values of these problems in Section 3. We derive primal and dual problems for three-layer ReLU networks with standard architecture and precisely calculate the optimal values for whitened data in Section 4. We also show that deep ReLU networks with parallel structures have no duality gap.

heading: 2 STANDARD NEURAL NETWORKS VS PARALLEL ARCHITECTURES
text: We start with the L-layer neural network with the standard architecture:
fθ(X) = AL−1WL, Al = φ(Al−1Wl), ∀l ∈ [L− 1],A0 = X,
where φ is the activation function, Wl ∈ Rml−1×ml is the weight matrix in the l-th layer and θ = (W1, . . . ,WL) represents the parameter of the neural network. We also denote the input and output dimensions asm0 = d andmL = K for simplicity and assume thatml ≥ max{d,K},∀l ∈ [L−2]. We then introduce the neural network with the parallel architecture:
fprlθ (X) = AL−1WL, Al,j = φ(Al−1,jWl,j),∀j ∈ [m],∀l ∈ [L− 1], A0,j = X,∀j ∈ [m].
Here for l ∈ [L − 1], the l-th layer has m weight matrices Wl,j ∈ Rml−1×ml where j ∈ [m]. Specifically, we let mL−1 = 1. In short, we can view the output AL−1 from a parallel neural network as a concatenation of m scalar-output standard neural work. In Figure 1 and 2, we provide examples of neural networks with standard and parallel architectures. We shall emphasize that for L = 2, the standard neural network is identical to the parallel neural network.
1This corresponds to weak regularization, i.e., β → 0 in (3) as considered in Wei et al. (2018).
Layer 1Input Layer 2 Layer 3 Layer 4
Figure 1: Standard Architecture

heading: 3 DEEP LINEAR NETWORKS
text: In this section, we discuss the convex duality of deep linear network with vector output.

heading: 3.1 STANDARD DEEP LINEAR NETWORKS
text: We first consider the neural network with standard architecture, i.e., fθ(X) = XW1 . . .WL. Consider the following minimal norm optimization problem:
Plin = min {Wl}Ll=1
1
2 L∑ i=1 ‖Wl‖2F , s.t. XW1, . . . ,WL = Y, (7)
where the variables are W1, . . . ,WL. As shown in the Proposition 3.1 in (Ergen & Pilanci, 2020b), by introducing a scale parameter t, the problem (7) can be reformulated as
Plin = min t>0 L− 2 2 t2 + Plin(t),
where Plin(t) is defined as
Plin(t) = min {Wl}Ll=1 K∑ j=1 ‖wrowL,j ‖2,
s.t. ‖Wi‖F ≤ t, i ∈ [L− 2], ‖wcolL−1,j‖2 ≤ 1, j ∈ [mL−1], XW1 . . .WL = Y.
(8)
The following proposition characterize the dual problem of Plin(t) and its bi-dual, i.e., dual of the dual problem.
Proposition 1 The dual problem of Plin(t) defined in (8) is a convex optimization problem given by
Dlin(t) = max Λ
tr(ΛTY)
s.t. ‖ΛTXW1 . . .WL−2wL−1‖2 ≤ 1, ‖Wi‖F ≤ t, ∀i ∈ [L− 2], ‖wL−1‖2 ≤ 1.
(9)
There exists m∗ ≤ KN + 1 such that the dual problem Dlin(t) can be reformulated as the bi-dual, i.e.,
Dlin(t) = min {Wl,j}Ll=1 m∗∑ j=1 ‖wrowL,j ‖2,
s.t. m∗∑ j=1 XW1,j . . .WL−2,jw col L−1,jw row L,j = Y,
‖Wi,j‖F ≤ t, i ∈ [L− 2], j ∈ [m∗], ‖wcolL−1,j‖2 ≤ 1, j ∈ [m∗].
(10)
Detailed derivation of the dual and the bi-dual are provided in Appendix B.1. The reason why we do not directly take the dual of Plin is that the objective function in Plin involves the weights of first L − 1 layer, which prevents obtaining a meaningful dual problem. We note that bi-dual problem is related to the minimal norm problem of a parallel neural network with aligned weights. Namely, the Frobenius norm of the weight matrices in each branch has the same upper bound t.
For a matrix A ∈ Rm×n and p > 0, the Schatten-p quasi-norm of A is defined as
‖A‖Sp = min{m,n}∑ i=1 σpi (A) 1/p , where σi(A) is the i-th largest singular value of A. The optimal value of Plin(t) and Dlin(t) can be precisely calculated.
Theorem 1 For fixed t > 0, the optimal value of Plin(t) and Dlin(t) are given by
Plin(t) = t −(L−2)‖X†Y‖S2/L , (11)
and Dlin(t) = t
−(L−2)‖X†Y‖∗, (12) where X† is the pseudo inverse of X and ‖ · ‖∗ represents the nuclear norm.
As a result, the duality gap exists, i.e., P > D, for standard deep linear networks with L ≥ 3, if the singular values of X†Y are not equal to the same value. We note that the optimal scale parameter t for the primal problem Plin is given by t∗ = ‖W∗‖1/LS2/L . To the best of our knowledge, this result wasn’t shown previously. We leave the proof in Appendix B.2 and provide conditions on W1, . . . ,WL to achieve the optimal value.
In the calculation of Plin(t), we utilize the following proposition. Proposition 2 Suppose that W ∈ Rd×K with rank r is given. Assume thatmi ≥ r for i = 0, . . . , L. Consider the following optimization problem:
min {Wl}Ll=1
1
2
( ‖W1‖2F + · · ·+ ‖WL‖2F ) , s.t. W1W2 . . .WL = W. (13)
Then, the optimal value of the problem (13) is given by L2 ‖W‖ 2/L S2/L .

heading: 3.2 PARALLEL DEEP LINEAR NEURAL NETWORKS
text: For the neural network with parallel structure, we consider the minimal norm optimization problem:
min {Wl,j}Ll=1
1
2 L−1∑ l=1 m∑ j=1 ‖Wl,j‖2F + ‖WL‖2F  , s.t.
m∑ j=1 XW1,j . . .WL−2,jw col L−1,jw row L,j = Y.
(14)
Due to a rescaling to achieve the lower bound of the inequality of arithmetic and geometric means, we have the following result.
Proposition 3 The problem (14) can be formulated as
min {Wl,j}l∈[L],j∈[m]
L
2 m∑ j=1 ‖wrowL,j ‖ 2/L 2 ,
s.t. m∑ j=1 XW1,j . . .WL−2,jw col L−1,jw row L,j = Y,
‖Wl,j‖F ≤ 1, l ∈ [L− 2], j ∈ [m], ‖wcolL−1,j‖2 ≤ 1, j ∈ [m].
(15)
We note that z2/L is a non-convex of z and we cannot take a meaningful dual. The bi-dual problem of the standard neural network does NOT correspond to the primal problem of the parallel neural network because the Frobenius norm of each parallel part of the parallel architecture can be different in formulating (15).
We can consider another regularization, i.e.,
P prllin = min{Wl,j}Ll=1
1
2 L−1∑ l=1 m∑ j=1 ‖Wl,j‖LF + ‖WL‖LF ,
s.t. m∑ j=1 XW1,j . . .WL−2,jw col L−1,jw row L,j = Y.
(16)
Proposition 4 The problem (16) can be formulated as
P prllin = min{Wl,j}l∈[L],j∈[m]
L
2 m∑ j=1 ‖wrowL,j ‖2,
s.t. m∑ j=1 XW1,j . . .WL−2,jw col L−1,jw row L,j = Y,
‖Wl,j‖F ≤ 1, l ∈ [L− 2], j ∈ [m], ‖wcolL−1,j‖2 ≤ 1, j ∈ [m].
(17)
The dual problem of P prllin is a convex problem
Dprllin = maxΛ tr(ΛTY),
s.t. ‖ΛTXW1 . . .WL−2wL−1‖2 ≤ L/2, ∀‖Wi‖F ≤ 1, i ∈ [L− 2], ‖wL−1‖2 ≤ 1.
(18)
For the parallel linear network, the strong duality holds. Theorem 2 There exists m∗ ≤ KN + 1 such that as long as the number of branches m ≥ m∗, the strong duality holds for the problem (16). Namely, P prllin = D prl lin . The optimal values are both L 2 ‖X †Y‖∗.
This implies that there exist equivalent convex problems which achieve the global optimum of the deep parallel linear network. Comparatively, optimizing deep parallel linear neural networks can be much easier than optimizing deep standard linear networks.

heading: 3.3 GENERAL LOSS FUNCTIONS
text: Now we consider general loss functions, i.e.,
min {Wl}Ll=1
`(XW1 . . .WL,Y) + β
2 L∑ i=1 ‖Wi‖2F ,
where `(Z,Y) is a general loss function and β > 0 is a regularization parameter. According to Proposition 2, the above problem is equivalent to
min W
`(XW,Y) + βL
2 ‖W‖2/LS2/L . (19)
The `2 regularization term becomes the Schatten-2/L quasi-norm on W to the power 2/L. Suppose that there exists W such that l(XW,Y) = 0. With β → 0, asymptotically, the optimal solution to the problem (19) converges to the optimal solution of
min W ‖W‖2/LS2/L , s.t. `(XW,Y) = 0. (20)
In other words, the `2 regularization explicitly regularizes the training problem to find a low-rank solution W.

heading: 4 NEURAL NETWORKS WITH RELU ACTIVATION
text: Now, we focus on the three-layer neural network with ReLU activation, i.e., φ(z) = max{z, 0}.

heading: 4.1 STANDARD THREE-LAYER RELU NETWORKS
text: We first focus on the three-layer ReLU network with standard architecture. Consider the minimal norm problem
PReLU = min {Wi}3i=1
1
2 3∑ i=1 ‖Wi‖2F , s.t. ((XW1)+W2)+W3 = Y. (21)
Here we denote (z)+ = max{z, 0}. Similarly, by introducing a scale parameter t, this problem can be formulated as
PReLU = min t>0
1 2 t2 + PReLU(t),
where PReLU(t) is defined as
PReLU(t) = min {Wi}3i=1 K∑ j=1 ‖wrow3,j ‖2,
s.t. ‖W1‖F ≤ t, ‖wcol2,j‖2 ≤ 1, j ∈ [m2], ((XW1)+W2)+W3 = Y.
(22)
The proof is analagous to the proof of Proposition 3.1 in (Ergen & Pilanci, 2020b). For W1 ∈ Rd×m, we define the set
A(W1) = {((XW1)+w2)+|‖w2‖2 ≤ 1}. (23)
Proposition 5 The dual problem of PReLU(t) defined in (22) is a convex problem defined as
DReLU(t) = max Λ
tr(ΛTY), s.t. ‖ΛTv‖2 ≤ 1,v ∈ A(W1),∀‖W1‖F ≤ t. (24)
There exists m∗ ≤ KN + 1 such that the dual problem can be reformulated as the bi-dual problem, i.e.,
DReLU(t) = min {W1,j}m ∗ j=1,W2∈Rm1×m ∗ ,W3∈Rm∗×K K∑ j=1 ‖wrow3,j ‖2,
s.t. m∗∑ j=1 ((XW1,j)+w col 2,j)+w row 3,j = Y, ‖W1,j‖F ≤ t, ‖wcol2,j‖2 ≤ 1.
(25)
For the case where the data matrix is with rank 1 and the neural network is with scalar output, there is no duality gap.
Theorem 3 For a three-layer scalar-output ReLU network, let X be a rank-one data matrix. Then, strong duality holds, i.e., PReLU(t) = DReLU(t). Suppose that λ
∗ is the optimal solution to the dual problem DReLU(t), then the optimal weights for each layer can be formulated as
W1 = tsign(|(λ∗)T (c)+| − |(λ∗)T (−c)+|)ρ0ρT1 ,w2 = ρ1.
Here ρ0 = a0/‖a0‖2 and ρ1 ∈ R ml + satisfies ‖ρ1‖ = 1.
Now, we consider the case where the data matrix is whitened, i.e., XXT = In and Y has orthogonal columns. We leave the proof of Theorem 4 and the characterization of optimal solutions in Appendix C.3.
Theorem 4 Let {X,Y} be a dataset such that XXT = In and Y has orthogonal columns. Then, the optimal value of PReLU(t) and DReLU(t) are given by
PReLU(t) = t −1  K∑ j=1 ( ‖(yj)+‖2/32 + ‖(−yj)+‖ 2/3 2 )3/2 , (26) and
DReLU(t) = t −1 n∑ j=1 (‖(yj)+‖2 + ‖(−yj)+‖2) . (27)
Suppose that Y is the one-hot encoding of the label. Then, we note that yj ≥ 0 and ‖(yj)+‖2 is the square root of the number of data points in the j-th class. Therefore, we recover the result about the duality gap of standard three-layer ReLU networks.

heading: 4.2 PARALLEL DEEP RELU NETWORKS
text: For the parallel architecture, we show that there is no duality gap for arbitrary deep ReLU network with large enough number of branches. Consider the following minimal norm problem:
P prlReLU = min 1
2 L−1∑ l=1 m∑ j=1 ‖Wl,j‖LF + ‖WL‖LF ,
s.t. m∑ j=1 (((XW1,j)+ . . .WL−2,j)+w col L−1,j)+w row L,j = Y.
(28)
Proposition 6 The problem (28) can be reformulated as
P prlReLU = min L
2 m∑ j=1 ‖wrowL,j ‖2,
s.t. m∑ j=1 (((XW1,j)+ . . .WL−2,j)+w col L−1,j)+w row L,j = Y,
‖Wl,j‖F ≤ 1, l ∈ [L− 2], ‖wcolL−1,j‖2 ≤ 1, j ∈ [m].
(29)
The dual problem (29) is a convex problem defined as
DprlReLU = max tr(Λ TY), s.t. max
v=((XW1)+...WL−2)+wL−1)+, ‖Wl‖F≤1,l∈[L−2],‖wL−1‖2≤1
‖ΛTv‖2 ≤ L/2. (30)
For deep ReLU network with parallel architecture, the strong duality holds.
Theorem 5 The strong duality holds for (29) in the sense that P prlReLU = D prl ReLU form ≥ m∗, where m∗ is upper bounded by KN + 1.
Similar to case of parallel deep linear networks, the parallel deep ReLU network also achieves zeroduality gap. Therefore, to find the global optimum for parallel deep ReLU network is equivalent to solve a convex program.

heading: 5 CONCLUSION
text: We present the convex duality framework for standard neural networks, considering both multi-layer linear networks and three-layer ReLU networks with rank-1 or whitened data. In stark contrast to the two-layer case, the duality gap can be non-zero for neural networks with depth three or more. Meanwhile, for neural networks with parallel architecture, with the regularization of L-th power of Frobenius norm in the parameters, we show that strong duality holds and the duality gap reduces to zero. A limitation of our work is that we primarily focus on minimal norm interpolation problems. We expect to generalize our results to general regularized training problems.

heading: 6 ACKNOWLEDGEMENTS
text: This work was partially supported by the National Science Foundation under grants ECCS-2037304, DMS-2134248, the Army Research Office.

heading: A STAIRS OF DUALITY GAP FOR STANDARD DEEP LINEAR NETWORKS
text: Now we consider partially dualizing the non-convex optimization problem by exchanging a subset of the minimization problems with respect to the hidden layers. Consider the Lagrangian for the primal problem of standard deep linear network
Plin(t) = min {Wl}L−1l=1 max Λ
tr(ΛTY)− I ( ‖ΛTXW1 . . .WL−2wL−1‖2 ≤ 1 ) ,
s.t. ‖Wi‖F ≤ t, i ∈ [L− 2], ‖wL−1‖2 ≤ 1. (31)
By changing the order of L− 2 mins and the max in (31), for l = 0, 1, . . . , L− 2, we can define the l-th partial “dual” problem
D (l) lin(t) = minW1,...Wl max Λ min Wl+1,...,WL−2
tr(ΛTY)− I ( ‖ΛTXW1 . . .WL−2wL−1‖2 ≤ 1 ) ,
s.t. ‖Wi‖F ≤ t, i ∈ [L− 2], ‖wL−1‖2 ≤ 1. (32)
For l = 0, D(l)lin(t) corresponds the primal problem Plin(t), while for l = L − 2, D (l) lin(t) is the dual problem Dlin(t). From the following proposition, we illustrate that the dual problem of D (l) lin(t) corresponds to a minimal norm problem of a neural network with parallel structure.
Proposition 7 There exists m∗ ≤ KN + 1 such that the problem D(l)lin(t) is equivalent to the “bidual” problem
min m∗∑ j=1 ‖wrowL,j ‖2, s.t. m∗∑ j=1 XW1 . . .WlWl+1,j . . .WL−2,jw col L−1,jw row L,j = Y,
‖Wi‖F ≤ t, i ∈ [l], ‖Wi,j‖F ≤ t, i = l + 1, . . . , L− 2, j ∈ [m∗], ‖wcolL−1,j‖2 ≤ 1, j ∈ [m∗],
(33)
where the variables are Wi ∈ Rmi−1×mi for i ∈ [l], Wi,j ∈ Rmi−1×mi for i = l + 1, . . . , L − 2, j ∈ [m∗], WL−1 ∈ RmL−2×m ∗ and WL ∈ Rm ∗×mL .
We can interpret the problem (33) as the minimal norm problem of a linear network with parallel structures in (l + 1)-th to (L − 2)-th layers. This indicates that for l = 0, 1, . . . , L − 2, the bi-dual formulation of D(l)lin(t) can be viewed as an interpolation from a network with standard structure to a network with parallel structure. Now, we calculate the exact value of D(l)lin(t). Proposition 8 The optimal value D(l)lin(t) follows
D (l) lin(t) = t −(L−2)‖X†Y‖S2/(l+2) . (34)
Suppose that the eigenvalues X†Y are not identical to each other. Then, we have
Plin(t) = D (L−2) lin (t) > D (L−3) lin (t) > · · · > D (0) lin (t) = D(t). (35)
In Figure 3, we plot D(l)lin(t) for l = 0, . . . , 5 for an example.

heading: B PROOFS OF MAIN RESULTS FOR LINEAR NETWORKS

heading: B.1 PROOF OF PROPOSITION 1
text: Consider the Lagrangian function
L(W1, . . . ,WL,Λ) = K∑ j=1 ‖wL,j‖2 + tr(ΛT (Y −XW1 . . .WL)). (36)
Here Λ ∈ RN×K is the dual variable. We note that P (t) = min
W1,...,WL max Λ L(W1, . . . ,WL,Λ), s.t. ‖Wi‖F ≤ t, i ∈ [L− 2], ‖wcolL−1,j‖2 ≤ 1, j ∈ [mL−1],
= min W1,...,WL−1 max Λ tr(ΛTY)− mL−1∑ j=1 I ( ‖ΛTXW1 . . .WL−2wL−1,j‖2 ≤ 1 ) ,
s.t. ‖Wi‖F ≤ t, i ∈ [L− 2], ‖wcolL−1,j‖2 ≤ 1, j ∈ [mL−1],
= min W1,...,WL−2,WL−1 max Λ
tr(ΛTY)− I ( ‖ΛTXW1 . . .WL−2wL−1‖2 ≤ 1 ) ,
s.t. ‖Wi‖F ≤ t, i ∈ [L− 2], ‖wL−1‖2 ≤ 1.
(37)
Here I(A) is 0 if the statement A is true. Otherwise it is +∞. For fixed W1, . . . ,WL−1, the constraint on WL is linear so we can exchange the order of maxΛ and minWL in the second line of (37).
By exchanging the order of min and max, we obtain the dual problem
D(t) = max Λ min W1,...,WL−2
tr(ΛTY)− I ( ‖ΛTXW1 . . .WL−2wL−1‖2 ≤ 1 ) ,
s.t. ‖Wi‖F ≤ t, i ∈ [L− 2], ‖wL−1‖2 ≤ 1, = max
Λ tr(ΛTY)
s.t. ‖ΛTXW1 . . .WL−2wL−1‖2 ≤ 1 ∀‖Wi‖F ≤ t, i ∈ [L− 2], ‖wL−1‖2 ≤ 1.
(38)
Now we derive the bi-dual problem. The dual problem can be reformulated as
max Λ
tr(ΛTY),
s.t. ‖ΛTXW1 . . .WL−2wL−1‖2 ≤ 1, ∀(W1, . . . ,WL−2,wL−1) ∈ Θ.
(39)
Here the set Θ is defined as
Θ = {(W1, . . . ,WL−2,wL−1)|‖Wi‖F ≤ t, i ∈ [L− 2], ‖wL−1‖2 ≤ 1}. (40)
By writing θ = (W1, . . . ,WL−2,wL−1), the dual of the problem (39) is given by
min ‖µ‖TV, s.t. ∫ θ∈Θ XW1 . . .WL−2wL−1dµ (θ) = Y.
(41)
Here µ : Σ → RK is a signed vector measure and Σ is a σ-field of subsets of Θ. The norm ‖µ‖TV is the total variation of µ, which can be calculated by
‖µ‖TV = sup u:‖u(θ)‖2≤1 {∫ Θ uT (θ)dµ(θ) =: K∑ i=1 ∫ Θ ui(θ)dµi(θ) } , (42)
where we write µ = µ1... µK . The formulation in (41) has infinite width in each layer. According to Theorem 9 in Appendix E, the measure µ in the integral can be represented by finitely many Dirac delta functions. Therefore, we can rewrite the problem (41) as
min m∗∑ j=1 ‖wrowL,j ‖2, s.t. m∗∑ j=1 XW1,j . . .WL−2,jw col L−1,jw row L,j = Y,
‖Wi,j‖F ≤ t, i ∈ [L− 2], ‖wcolL−1,j‖2 ≤ 1, j ∈ [m∗].
(43)
Here the variables are Wi,j for i ∈ [L − 2] and j ∈ [m∗], WL−1 and WL. As the strong duality holds for the problem (43) and (39), we can reformulate the problem of Dlin(t) as the bi-dual problem (43).

heading: B.2 PROOF OF PROPOSITION 2
text: We restate Proposition 2 with details. Proposition 9 Suppose that W ∈ Rd×K with rank r is given. Consider the following optimization problem:
min 1
2
( ‖W1‖2F + · · ·+ ‖WL‖2F ) , s.t. W1W2 . . .WL = W, (44)
in variables Wi ∈ Rmi−1×mi . Here m0 = d, mL = K and mi ≥ r for i = 1, . . . , L − 1. Then, the optimal value of the problem (44) is given by
L 2 ‖W‖2/LS2/L . (45)
Suppose that W = UΣVT . The optimal value can be achieved when
Wi = Ui−1Σ 1/LUTi , i = 1, . . . , N,U0 = U,UL = V. (46)
Here Ui ∈ Rr×mi satisfies that UTi Ui = I .
We start with two lemmas. Lemma 1 Suppose that A ∈ Sn×n is a positive semi-definite matrix. Then, for any 0 < p < 1, we have
n∑ i=1 Apii ≥ n∑ i=1 λi(A) p. (47)
Here λi is the i-th largest eigenvalue of A. Lemma 2 Suppose that P ∈ Rd×d is a projection matrix. Then, for arbitrary W ∈ Rd×K , we have σi(PW ) ≤ σi(W ),
where σi(W ) represents the i-th largest singular value of W .
Now, we present the proof for Proposition 2. For L = 1, the statement apparently holds. Suppose that for L = l this statement holds. For L = l + 1, by writing A = W2 . . .Wl+1, we have
min ‖W1‖2F + · · ·+ ‖WL‖2F , s.t. W1W2 . . .Wl+1 = W
= min ‖W1‖2F + l‖A‖ 2/l 2/l, s.t. W1A = W,
= min t2 + l‖A‖2/l2/l, s.t. W1A = W, ‖W1‖F ≤ t.
(48)
Suppose that t is fixed. It is sufficient to consider the following problem:
min ‖A‖2/l2/l, s.t. W1A = W, ‖W1‖F ≤ t. (49)
Suppose that there exists W1 and A such that W = W1A. Then, we have WA†A = W1AA
†A = W. As WA† = W1AA†, according to Lemma 2, ‖WA†‖F ≤ ‖W1‖F ≤ t. Therefore, (WA†,A) is also feasible for the problem (49). Hence, the problem (49) is equivalent to
min ‖A‖2/l2/l, s.t. WA †A = W, ‖WA†‖F ≤ t. (50)
Assume that W is with rank r. Suppose that A = UΣVT , where Σ ∈ Rr0×r0 . Here r0 ≥ r. Then, we have A† = VΣ−1UT . We note that
‖WA†‖2F = tr(WVΣ−2VTWT )
= tr(VTWTWVΣ−2)
(51)
Denote G(V) = VTWTWV. This implies that r∑ i=1 σi(A) −2 (G(V))ii ≤ t 2.
Therefore, we have( r0∑ i=1 σi(A) −2 (G(V))ii )( r0∑ i=1 σi(A) 2/l )l ≥ ( r0∑ i=1 (G(V)) 1/(l+1) ii )l+1 .
As WVTV = W, the non-zero eigenvalues of G(V) are exactly the non-zero eigenvalues of WVVTWT = WWT , i.e., the square of non-zero singular values of W. From Lemma 1, we have
r0∑ i=1 (G(V)) 1/(l+1) ii ≥ r0∑ i=1 λi(G(V)) 1/(l+1) ≥ r∑ i=1 σi(W) 2/(l+1). (52)
Therefore, we have
‖A‖2/lS2/l = r0∑ i=1 σi(A) 2/l ≥ t−2/l ( r∑ i=1 σi(W) 2/(l+1) )(l+1)/l (53)
This also implies that
min ‖A‖2/l2/l, s.t. W1A = W, ‖W1‖F ≤ t ≥t−2/l (
r∑ i=1 σi(W) 2/(l+1)
)(l+1)/l .
(54)
Suppose that W = ∑r i=1 uiσiv T i is the SVD of W. We can let
A =
(∑r i=1 σ 2/(l+1) i )1/2 t r∑ i=1 uiσ l/(l+1) i ρ T i ,
W1 = t(∑r
i=1 σ 2/(l+1) i
)1/2 r∑ i=1 ρiσ 1/(l+1) i v T i .
(55)
Here ‖ρi‖2 = 1 and ρTi ρj = 0 for i 6= j. Then, W1A = W and ‖W1‖F ≤ t. We also have
‖A‖2/LS2/L =t −2/l ( r∑ i=1 σ 2/(l+1) i )1/l r∑ i=1 σ 2/(l+1) i
=t−2/l ( r∑ i=1 σi(W) 2/(l+1) )(l+1)/l .
In summary, we have
min t2 + l‖A‖S2/l2/l , s.t. W1A = W, ‖W1‖F ≤ t.
= min t>0
t2 + lt−2/l ( r∑ i=1 σi(W) 2/(l+1) )(l+1)/l
=(l + 1) ( r∑ i=1 σi(W) 2/(l+1) )(l+1)/2 =‖W‖2/(l+1)S2/(l+1) .
(56)
This completes the proof.

heading: B.3 PROOF OF THEOREM 1
text: We first compute the optimal value P of the primal problem. From Proposition 2, the minimal norm problem (7) is equivalent to
minL‖W‖2/LS2/L , s.t. XW = Y, (57)
in variable W ∈ Rd×K . According to Lemma 2, for any feasible W satisfying XW = Y, because X†XW = X†Y and X†X is a projection matrix, we have
L‖W‖2/LS2/L ≥ L‖X †Y‖2/LS2/L . (58)
We also note that XX†Y = XX†XW = XW = Y. Therefore, X†Y is also feasible for the problem (57). This indicates that Plin = L2 ‖X
†Y‖2/LS2/L On the other hand, for a feasible point (W1, . . . ,WL) for Plin(t), we note that (W1/t, . . . ,WL−2/t,WL−1, t
L−2WL) is feasible for Plin(1). This implies that tL−2Plin(t) = Plin(1), or equivalently, Plin(t) = t−(L−2)Plin(1). Recall that
Plin = min t>0 L− 2 2 t2 + t−(L−2)Plin(1)
= L
2 (Plin(1))
2/L .
(59)
This implies that Plin(1) = ‖X†Y‖S2/L and
Plin(t) = t −(L−2)‖X†Y‖S2/L . (60)
For the dual problem Dlin(t) defined in (38), we note that
‖ΛTXW1 . . .WL−2wL−1‖2 ≤‖ΛTXW1 . . .WL−2‖2‖wL−1‖2
≤‖ΛTX‖2 L−2∏ l=1 ‖Wl‖2‖wL−1‖2
≤‖ΛTX‖2 L−2∏ l=1 ‖Wl‖F ‖wL−1‖2 = tL−2‖ΛTX‖2.
(61)
The equality can be achieved when Wl = tuluTl+1 for l ∈ [L − 2], where ‖ul‖2 = 1 for l = 1, . . . , L− 1. Specifically, we set uL−1 = wL−1 and let u0 as right singular vector corresponds to the largest singular value of ΛTX. Therefore, the constraints on Λ is equivalent to
‖ΛTX‖2 ≤ t−(L−2). (62) Thus, according to the Von Neumann’s trace inequality, it follows
tr(ΛTY) = tr(λTXX†Y) ≤ ‖λTX‖2‖X†Y‖∗ ≤ t−(L−2)‖X†Y‖∗. (63) As a result, we have Dlin(t) = t−(L−2)‖X†Y‖∗ < t−(L−2)‖X†Y‖S2/L = Plin(t). Namely, the duality gap exists for the standard neural network.

heading: B.4 PROOF OF PROPOSITION 3
text: For simplicity, we write WL−1,j = wcolL−1,j and WL,j = w row L,j for j ∈ [m]. For the j-th branch of the parallel network, let Ŵl,j = αl,jWl,j for l ∈ [L]. Here αl,j > 0 for l ∈ [L] and they satisfies that ∏L l=1 αl,j = 1 for j ∈ [m]. Therefore, we have
XW1,j . . .WL−2,jw col L−1,jw row L,j = XŴ1,j . . .ŴL−2,jŵ col L−1,jŵ row L,j . (64)
This implies that {Ŵl,j}l∈[L],j∈[m] is also feasible for the problem (14). According to the the inequality of arithmetic and geometric means, the objective function in (14) is lower bounded by
1
2 m∑ j=1 L∑ l=1 α2l,j‖Wl,j‖2F
≥ m∑ j=1 L 2 L∏ l=1 ( α 2/L l,j ‖Wl,j‖ 2/L F )
= L
2 m∑ j=1 L∏ l=1 ‖Wl,j‖2/LF .
(65)
The equality is achieved when αl,j = ∏L l=1 ‖Wl,j‖ 1/L F
‖Wl,j‖F for l ∈ [L] and j ∈ [m]. As the scaling operation does not change ∏L l=1 ‖Wl,j‖ 2/L F , we can simply let ‖Wl,j‖F = 1 and the lower bound
becomes L2 ∑m i=1 ‖WL,j‖ 2/L F = L 2 ∑m i=1 ‖wrowL,j ‖ 2/L 2 . This completes the proof.

heading: B.5 PROOF OF PROPOSITION 4
text: We first show that the problem (16) is equivalent to (17). The proof is analogous to the proof of Proposition 3. For simplicity, we write WL−1,j = wcolL−1,j and WL,j = w row L,j for j ∈ [m]. Let
αl,j > 0 for l ∈ [L] and they satisfies that ∏L l=1 αl,j = 1 for j ∈ [m]. Consider another parallel network {Ŵl,j}l∈[L],j∈[m] whose j-th branch is defined by Ŵl,j = αl,jWl,j for l ∈ [L]. As∏L l=1 αl,j = 1, we have
XW1,j . . .WL−2,jw col L−1,jw row L,j = XŴ1,j . . .ŴL−2,jŵ col L−1,jŵ row L,j . (66)
This implies that {Ŵl,j}l∈[L],j∈[m] is also feasible for the problem (16). According to the the inequality of arithmetic and geometric means, the objective function in (14) is lower bounded by
1
2 m∑ j=1 L∑ l=1 αLl,j‖Wl,j‖LF
≥ m∑ j=1 L 2 L∏ l=1 (αl,j‖Wl,j‖F )
= L
2 m∑ j=1 L∏ l=1 ‖Wl,j‖F .
(67)
The equality is achieved when αl,j = ∏L l=1 ‖Wl,j‖ 1/L F
‖Wl,j‖F for l ∈ [L] and j ∈ [m]. As the scaling operation does not change ∏L l=1 ‖Wl,j‖F , we can simply let ‖Wl,j‖F = 1 and the lower bound
becomes L2 ∑m i=1 ‖WL,j‖F = L 2 ∑m i=1 ‖wrowL,j ‖2. Hence, the problem (16) is equivalent to (17).
For the problem (17), we consider the Lagrangian function
L(W1, . . . ,WL) = L
2 m∑ j=1 ‖wrowL,j ‖2 + tr ΛT (Y − m∑ j=1 XW1,j . . .W col L−1,jW row L,j )  . (68)
The primal problem is equivalent to
P prllin = minW1,...,WL max Λ L(W1, . . . ,WL,Λ),
s.t. ‖Wl,j‖F ≤ t, j ∈ [ml], l ∈ [L− 2], ‖wcolL−1,j‖2 ≤ 1, j ∈ [mL−1], = min
W1,...,WL−1 max Λ min WL L(W1, . . . ,WL,Λ),
s.t. ‖Wl,j‖F ≤ 1, l ∈ [L− 2], ‖wcolL−1,j‖2 ≤ 1, j ∈ [m],
= min W1,...,WL−1 max Λ tr(ΛTY)− mL∑ j=1 I ( ‖ΛTXW1,j . . .WL−2,jwcolL−1,j‖2 ≤ L/2 ) ,
s.t. ‖Wl,j‖F ≤ 1, l ∈ [L− 2], ‖wcolL−1,j‖2 ≤ 1, j ∈ [m].
(69)
The dual problem follows
Dprllin = maxΛ tr(ΛTY),
s.t. ‖ΛTXW1,j . . .WL−2,j‖2 ≤ L/2, ∀‖Wl,j‖F ≤ 1, l ∈ [L− 2], ‖WcolL−1,j‖2 ≤ 1, j ∈ [m]
= max Λ
tr(ΛTY),
s.t. ‖ΛTXW1 . . .WL−2wL−1‖2 ≤ L/2, ∀‖Wi‖F ≤ 1, i ∈ [L− 2], ‖wL−1‖2 ≤ 1.
(70)

heading: B.6 PROOF OF THEOREM 2
text: We can rewrite the dual problem as
Dprllin = maxΛ tr(ΛTY),
s.t. ‖ΛTXW1 . . .WL−2wL−1‖2 ≤ L/2, ∀(W1, . . . ,WL−2,wL−1) ∈ Θ,
(71)
where the set Θ is defined as
Θ = {(W1, . . . ,WL−2,wL−1)|‖Wl‖F ≤ 1, l ∈ [L− 2], ‖wL−1‖2 ≤ 1}. (72)
By writing θ = (W1, . . . ,WL−2,wL−1), the bi-dual problem, i.e., the dual problem of (71), is given by
min ‖µ‖TV, s.t. ∫ θ∈Θ XW1 . . .WL−2wL−1dµ (θ) = Y.
(73)
Here µ : Σ→ RK is a signed vector measure, where Σ is a σ-field of subsets of Θ and ‖µ‖TV is its total variation. The formulation in (73) has infinite width in each layer. According to Theorem 9 in Appendix E, the measure µ in the integral can be represented by finitely many Dirac delta functions. Therefore, there exists m∗ < KN + 1 such that we can rewrite the problem (73) as
min m∗∑ j=1 ‖wrowL,j ‖2, s.t. m∗∑ j=1 XW1,j . . .WL−2,jw col L−1,jw row L,j = Y,
‖Wi,j‖F ≤ 1, l ∈ [L− 2], ‖wcolL−1,j‖2 ≤ 1, j ∈ [m∗].
(74)
Here the variables are Wl,j for l ∈ [L − 2] and j ∈ [m∗], WL−1 and WL. This is equivalent to (17). As the strong duality holds for the problem (71) and (73), the primal problem (17) is equivalent to the dual problem (71) as long as m ≥ m∗.
Now, we compute the optimal value of Dprllin . Similar to the proof of Theorem 1, we can show that the constraints in the dual problem (71) is equivalent to
‖ΛTX‖2 ≤ L/2. (75) Therefore, we have
tr(ΛTY) ≤ ‖λTX‖2‖X†Y‖∗ ≤ L
2 ‖X†Y‖∗. (76)
This implies that P prllin = D prl lin = L 2 ‖X †Y‖∗.

heading: B.7 PROOF OF PROPOSITION 8
text: We note that
max Λ
tr(ΛTY),
s.t. ‖ΛTXW1 . . .WL−2‖2 ≤ 1, ‖Wi‖F ≤ t, i = l + 1, . . . , L− 2 = max
Λ min Wj+1,...,WL−2 tr(ΛTY), s.t. ‖ΛTXW1 . . .Wl‖2 ≤ t−(L−2−l)
(77)
Therefore, we can rewrite D(l)lin(t) as
D (l) lin(t) = minW1,...Wl max Λ tr(ΛTY),
s.t. ‖ΛTXW1 . . .Wl‖2 ≤ t−(L−2−l), ‖Wi‖F ≤ t, i ∈ [l], = min
W1,...Wl max Λ t−(L−2−l) tr(ΛTY), s.t. ‖ΛTXW1 . . .Wl‖2 ≤ 1, ‖Wi‖F ≤ t, i ∈ [l].
(78)
From the equation (11), we note that
min W1,...Wj max Λ
tr(ΛTY)
s.t. ‖ΛTXW1 . . .Wj‖2 ≤ 1, ‖Wi‖F ≤ t, i ∈ [j],
= min K∑ j=1 ‖wl+2,j‖2,
s.t. ‖Wi‖F ≤ t, i ∈ [L− 2], ‖wL−1,j‖2 ≤ 1, j ∈ [mL−1], XW1 . . .Wl+2 = Y
=t−l‖X†Y‖S2/(l+2) .
(79)
This completes the proof.

heading: C PROOFS OF MAIN RESULTS FOR RELU NETWORKS

heading: C.1 PROOF OF PROPOSITION 5
text: For the problem of P (t), introduce the Lagrangian function
L(W1,W2,W3,Λ) = K∑ j=1 ‖wrow3,j ‖2 − tr(Λ T (((XW1)+W2)+W3 −Y)). (80)
According to the convex duality of two-layer ReLU network, we have
PReLU(t) = min ‖W1‖F≤t,‖w2‖≤1 max Λ
tr(ΛTY)− I(‖ΛT ((XW1)+w2)+‖2 ≤ 1)
= min ‖W1‖F≤t max Λ min ‖w2‖≤1
tr(ΛTY)− I(‖ΛT ((XW1)+w2)+‖2 ≤ 1)
= min ‖W1‖F≤t max Λ
tr(ΛTY), s.t. ‖ΛTv‖2 ≤ 1,∀v ∈ A(W1).
(81)
By changing the min and max, we obtain the dual problem. DReLU(t) = max
Λ tr(ΛTY), s.t. ‖ΛTv‖2 ≤ 1,v ∈ A(W1),∀‖W1‖F ≤ t. (82)
The dual of the dual problem writes min ‖µ‖TV, s.t. ∫ ‖W1‖F≤t,‖w2‖2≤1 ((XW1)+w2)+ dµ (W1,w2) = Y.
(83)
Here µ is a signed vector measure and ‖µ‖TV is its total variation. Similar to the proof of Proposition 1, we can find a finite representation for the optimal measure and transform this problem to
min {W1,j}m ∗ j=1,W2∈Rm1×m ∗ ,W3∈Rm∗×K K∑ j=1 ‖w3,j‖2, s.t. m∗∑ j=1 ((XW1,j)+w2,j)+w3,j = Y, ‖W1,j‖F ≤ t, ‖w2,j‖2 ≤ 1.
(84)
Here m∗ ≤ KN + 1. This completes the proof.

heading: C.2 PROOF OF THEOREM 3
text: For rank-1 data matrix that X = caT0 , suppose that A1 = (XW1)+. It is easy to observe that A1 = (c)+a T 1,+ + (−c)+aT1,−, Here we let a1,+ = (W1a0)+ and a0,− = (−W1a0)+. For a three-layer network, i.e., L = 3, suppose that λ∗ is the optimal solution to the dual problem DReLU(t). We consider the extreme points
arg max ‖W1‖F≤t,‖w2‖2≤1
|(λ∗)∗((XW1)+w2)+|. (85)
For fixed W1, because aT1,+a1,− = 0, suppose that w2 = u1a1,+ + u2a1,− + u3r, where rTa1,+ = rTa1,− = 0 and ‖r‖2 = 1. The maximization problem on w2 becomes arg max
∣∣(λ∗)T (c)+‖a1,+‖22(u1)+ + (λ∗)T (−c)+‖aL−2,−‖22(u2)+∣∣ s.t. u21‖a1,+‖22 + u22‖a1,+‖22 + u23 ≤ 1.
If (λ∗)T (c)+ and (λ∗)T (−c)+ have different signs, then the optimal value is max{|(λ∗)T (c)+|‖aL−2,+‖2, |(λ∗)T (−c)+|‖aL−2,−‖2}. And the corresponding optimal wL−1 is wL−1 = aL−2,+/‖aL−2,+‖ or wL−1 = aL−2,−/‖aL−2,−‖. Then, the problem becomes arg max max{|(λ∗)T (c)+|‖aL−2,+‖2, |(λ∗)T (−c)+|‖aL−2,−‖2}. We note that max{‖aL−2,+‖2, ‖aL−2,−‖2} ≤ ‖WT1 a0‖2 ≤ ‖W1‖2‖a0‖2 ≤ t∗‖a0‖2. Thus the optimal W1 follows
W1 = t ∗sign(|(λ∗)T (c)+| − |(λ∗)T (−c)+|)ρ0ρT1
Here ρ0 = a0/‖a0‖2 and ρ1 ∈ R ml + satisfies ‖ρ1‖ = 1. This also gives the optimal w2 = ρ1.
On the other hand, if (λ∗)T (c)+ and (λ∗)T (−c)+ have same signs, then, the optimal w2 follows
w2 = |(λ∗)T (c)+|aL−2,+ + |(λ∗)T (−c)+|aL−2,−√
((λ∗)T (c)+)2‖aL−2,+‖22 + ((λ ∗)T (−c)+)2‖aL−2,−‖22
.
The maximization problem is equivalent to arg max((λ∗)T (c)+) 2‖aL−2,+‖22 + ((λ ∗)T (c)−)
2‖aL−2,−‖22 By noting that ‖aL−2,+‖22 + ‖aL−2,+‖22 = ‖WT1 a0‖22 ≤ ‖W1‖22‖a0‖22 ≤ (t∗)2‖a0‖22, the optimal W1 follows W1 = tsign(|(λ∗)T (c)+| − |(λ∗)T (−c)+|)ρ0ρT1 . Here ρ0 = a0/‖a0‖2 and ρ1 ∈ R m1 + satisfies ‖ρ1‖ = 1. This also gives the optimal w2 = ρ1.

heading: C.3 PROOF OF THEOREM 4
text: We restate Theorem 4 with details as follows. Theorem 6 Let {X,Y} be a dataset such that XXT = In and Y has orthogonal columns. Then, the optimal value of PReLU(t) and DReLU(t) are given by
PReLU(t) = t −1  K∑ j=1 ( ‖(yj)+‖2/32 + ‖(−yj)+‖ 2/3 2 )3/2 , (86) and
DReLU(t) = t −1 n∑ j=1 (‖(yj)+‖2 + ‖(−yj)+‖2) . (87)
For the bi-dual formulation of DReLU(t) defined in (25), the optimal weight matrices for each layer can be constructed as
W1,r = φ0,r ‖φ0,r‖2 φT1,r,w2,r = φ1,r ‖φ1,r‖ ,
for r = 1, . . . , 2K. Here (φ0,2j−1,φ0,2j) = ( XT (yj)+,X T (−yj)+ ) , ‖φ1,r‖ = t, φ1,r ∈ R m1 + .
For PReLU(t), the optimal weight matrices for each layer write
W1 = 2K∑ r=1 gr φ0,r ‖φ0,r‖2 φT1,r,W2 = [ φ1,1, . . . ,φ1,2K ] .
Here
g2j+1 = ‖(yj)+‖1/32(∑K
j=1 ( ‖(yj)+‖2/32 + ‖(−yj)+‖ 2/3 2 ))3/2 , g2j+2 =
‖(−yj)+‖1/32(∑K j=1 ( ‖(yj)+‖2/32 + ‖(−yj)+‖ 2/3 2 ))3/2 . We require that ‖φ1,j‖2 = 1 for j ∈ [2K] and φ T 1,iφ1,j = 0 for i 6= j.
Since XXT = In, we can characterize the set as
∪‖W1‖F≤tA(W1) = {(z)+|z ∈ R N , ‖z‖2 ≤ t}. (88)
HereA(W1) is defined in (23). For one thing, for z ∈ RN , ‖z‖2 ≤ t, we can let W1 = XT zvT and w2 = v, where v ∈ Rm1+ with ‖v‖2 = 1. Then, ‖W1‖F ≤ t, ‖w2‖2 ≤ 1 and (XW1)+w2)+ = (z)+. For another, for any ‖W1‖F ≤ t and ‖w2‖ ≤ 1, we note that
‖(XW1)+w2‖2 ≤ ‖(XW1)+‖2 ≤ ‖(XW1)+‖F ≤ ‖XW1‖F ≤ ‖W1‖F ≤ t.
Therefore, ∪‖W‖F≤tA(W ) = {(z)+|z ∈ RN , ‖z‖2 ≤ t}.
Thus, the constraint on Λ in the dual problem (24) is equivalent to say that t‖(Λ∗)T (z)+‖2 ≤ 1 for all z ∈ RN satisfying ‖z‖2 ≤ 1. As Y has orthogonal columns, we note that
tr((Λ∗)TY) = K∑ j=1 (λ∗j ) T ((yj)+ − (−yj)+) ≤ t−1 n∑ j=1 (‖(yj)+‖2 + ‖(−yj)+‖2) .
Suppose that (yj)+ 6= 0 and (−yj)+ 6= 0 for all j = 1, . . . ,K. Then, the dual problem is minimized by Λ∗ = t−1 [
(y1)+ ‖(y1)+‖2 − (−y1)+ ‖(−y1)+‖2 , . . . , (yK)+ ‖(yK)+‖2 − (−yK)+ ‖(−yK)+‖2
] .
We can also verify that t‖(Λ∗)T (z)+‖2 ≤ 1,∀‖z‖2 ≤ 1. (89)
Suppose that (z)+ = ∑K j=1 αj,1 (yj)+ ‖(yj)+‖2 + αj,2 (−yj)+ ‖(−yj)+‖2 + r, where r ∈ R N + is orthogonal to (yj)+ and (−yj)+. Here αj,1, αj,2 ≥ 0. As ‖(z)+‖ ≤ ‖z‖2 ≤ 1, we have K∑ j=1 (α2j,1 + α 2 j,2) ≤ 1− ‖r‖22 ≤ 1.
We note that
‖(Λ∗)T t(z)+‖22 = K∑ j=1 (αj,1 − αj,2)2 ≤ K∑ j=1 (α2j,1 + α 2 j,2) ≤ 1. (90)
Thus, Λ∗ satisfies the constraint (89).
We can characterize the optimal layer weight to the bi-dual problem as the extreme points that solves
arg max ‖W1‖F≤t,‖w2‖2≤1
‖(Λ∗)T ((XW1)+w2)+‖2. (91)
These extreme points correspond to the constraints∥∥∥∥(Λ∗)T t(yj)+‖(yj)+‖2 ∥∥∥∥
2
≤ 1, ∥∥∥∥(Λ∗)T t(−yj)+‖(−yj)+‖2 ∥∥∥∥ 2 ≤ 1.
In other words, the dual problem is equivalent to
DReLU(t) = max Λ
tr(ΛTY), s.t. ∥∥∥∥ΛT t∗(yj)+‖(yj)+‖2 ∥∥∥∥ 2 ≤ 1, ∥∥∥∥ΛT t∗(−yj)+‖(−yj)+‖2 ∥∥∥∥ 2 ≤ 1, 1 ≤ j ≤ K. (92)
Now, we consider an arbitrary matrix W1 satisfying ‖W1‖F ≤ t. Denote
P (W1) = max Λ
tr(ΛTY), s.t. ‖ΛTv‖2 ≤ 1,∀v ∈ A(W1). (93)
Suppose that Λ∗ is the optimal solution. Then, we have
tr((Λ∗)TY) = K∑ j=1 (λ∗j ) T ((yj)+ − (−yj)+)
= K∑ j=1 (λ∗j ) T (yj)+ ‖(yj)+‖2 ‖(yj)+‖2
− K∑ j=1 (λ∗j ) T (−yj)+ ‖(−yj)+‖2 ‖(−yj)+‖2.
For a vector λ ∈ RN , define g(λ; W1) = max
‖w2‖≤1 |λT ((XW1)+w2)+|. (94)
For a given u ∈ RN+ , we want to estimate
max |uTλ| s.t. g(λ; W1) ≤ 1. (95) The following lemma gives an upper bound. Lemma 3 Suppose that u ∈ RN satisfying ‖u‖2 = 1. Then, for arbitrary λ satisfying g(λ; W1) ≤ 1, we have |uTλ| ≤ 1/g(u; W1).
Denote z2j+1 = (yj)+ ‖(yj)+‖2 and z2j+2 = (−yj)+ ‖(−yj)+‖2 . For simplicity, we write g(z; W1) = g(z). We note that λ∗j satisfies that g(λ ∗ j ) ≤ 1. According to Lemma 2, we have
P ∗(W1) = tr((Λ) TY) ≤ K∑ j=1 ( ‖(yj)+‖2 g(z2j+1) + ‖(yj)+‖2 g(z2j+2) ) .
This serves as an upper bound for P ∗(W1). We note that for u ∈ RN+ , we have
g(u)2 = max ‖w2‖≤1 |uT ((XW1)+w2)+|2
≤ max ‖w2‖≤1 |uT (XW1)+w2|2
=‖uT ((XW1)+‖22 ≤‖uTXW1‖22 ≤ tr(uuTXW1WT1 XT ).
Then, we have
2K∑ j=1 g(zj) 2 ≤ tr  2K∑ j=1 zjz T j XW1WT1 X  ≤ tr(XW1WT1 XT ) = t2.
According to the Holder’s inequality, we have K∑ j=1 (‖(yj)+‖2/g(z2j+1) + ‖(yj)+‖2/g(z2j+2)) 2/3 2K∑ j=1 g(zj) 2 1/3
≥ K∑ j=1 ( ‖(yj)+‖2/32 + ‖(−yj)+‖ 2/3 2 ) .
Thus, it follows K∑ j=1 (‖(yj)+‖2/g(z2j+1) + ‖(yj)+‖2/g(z2j+2))
≥t−1  K∑ j=1 ( ‖(yj)+‖2/32 + ‖(−yj)+‖ 2/3 2 )3/2 . The optimal g(zj) follows
g(z2j+1) = t‖(yj)+‖1/32(∑K
j=1 ( ‖(yj)+‖2/32 + ‖(−yj)+‖ 2/3 2 ))3/2 , g(z2j+2) =
t‖(−yj)+‖1/32(∑K j=1 ( ‖(yj)+‖2/32 + ‖(−yj)+‖ 2/3 2 ))3/2 . This bound can be achieved for
W1 = 2K∑ j=1 g(zj)zjφ T 1,j ,
where ‖φ1,j‖2 = 1 for j ∈ [2K] and φ T 1,iφ1,j = 0 for i 6= j.

heading: C.4 PROOF OF PROPOSITION 6
text: Analogous to the proof of Proposition 4, we can reformulate (28) into (29). The rest of the proof is analogous to the proof of Proposition 4. For the problem (29), we consider the Lagrangian function
L(W1, . . . ,WL)
= L
2 m∑ j=1 ‖wrowL,j ‖2 + tr ΛT (Y − m∑ j=1 (((XW1,j)+ . . . . . .WL−2,j)+w col L−1,j)+w row L,j )  . (96)
The primal problem is equivalent to
P prlReLU = min
W1,...,WL max Λ L(W1, . . . ,WL,Λ),
s.t. ‖Wl,j‖F ≤ t, j ∈ [ml], l ∈ [L− 2], ‖wcolL−1,j‖2 ≤ 1, j ∈ [mL−1], = min
W1,...,WL−1 max Λ min WL L(W1, . . . ,WL,Λ),
s.t. ‖Wl,j‖F ≤ 1, l ∈ [L− 2], ‖wcolL−1,j‖2 ≤ 1, j ∈ [m],
= min W1,...,WL−1 max Λ tr(ΛTY)− m∑ j=1 I ( ‖ΛT (((XW1,j)+ . . .WL−2,j)+wcolL−1,j)+‖2 ≤ L/2 ) ,
s.t. ‖Wl,j‖F ≤ 1, l ∈ [L− 2], ‖wcolL−1,j‖2 ≤ 1, j ∈ [m]. (97)
By exchanging the order of min and max, the dual problem follows
DprlReLU = max Λ tr(ΛTY),
s.t. ‖ΛT (((XW1,j)+ . . .WL−2,j)+wcolL−1,j)+‖2 ≤ L/2, ∀‖Wl,j‖F ≤ 1, l ∈ [L− 2], ‖WcolL−1,j‖2 ≤ 1, j ∈ [m]
= max Λ
tr(ΛTY),
s.t. ‖ΛT (((XW1)+ . . .WL−2)+wL−1)+‖2 ≤ L/2, ∀‖Wi‖F ≤ 1, i ∈ [L− 2], ‖wL−1‖2 ≤ 1.
(98)

heading: C.5 PROOF OF THEOREM 5
text: The proof is analogous to the proof of Theorem 2. We can rewrite the dual problem as
DprlReLU = max Λ tr(ΛTY),
s.t. ‖ΛT (((XW1)+ . . .WL−2)+wL−1)+‖2 ≤ L/2, ∀(W1, . . . ,WL−2,wL−1) ∈ Θ,
(99)
where the set Θ is defined as
Θ = {(W1, . . . ,WL−2,wL−1)|‖Wl‖F ≤ 1, l ∈ [L− 2], ‖wL−1‖2 ≤ 1}. (100)
By writing θ = (W1, . . . ,WL−2,wL−1), the bi-dual problem, i.e., the dual problem of (71), is given by
min ‖µ‖TV, s.t. ∫ θ∈Θ(((XW1)+ . . .WL−2)+wL−1)+dµ (θ) = Y.
(101)
Here µ : Σ→ RK is a signed vector measure, where Σ is a σ-field of subsets of Θ and ‖µ‖TV is its total variation. The formulation in (101) has infinite width in each layer. According to Theorem 9 in Appendix E, the measure µ in the integral can be represented by finitely many Dirac delta functions. Therefore, there exists m∗ ≤ KN + 1 such that we can rewrite the problem (101) as
min m∗∑ j=1 ‖wrowL,j ‖2, s.t. m∗∑ j=1 (((XW1,j)+ . . .WL−2,j)+w col L−1,j)+w row L,j = Y,
‖Wi,j‖F ≤ 1, l ∈ [L− 2], ‖wcolL−1,j‖2 ≤ 1, j ∈ [m∗].
(102)
Here the variables are Wl,j for l ∈ [L−2] and j ∈ [m∗], WL−1 and WL. This is equivalent to (29). As the strong duality holds for the problem (99) and (101), the primal problem (29) is equivalent to the dual problem (71) as long as m ≥ m∗.

heading: D PROOFS OF AUXILIARY RESULTS

heading: D.1 PROOF OF LEMMA 1
text: Denote a ∈ Rn such that ai = Aii and denote b ∈ Rn such that bi = λi(A). We can show that a is majorized by b, i.e., for k ∈ [n− 1], we have
k∑ i=1 a(i) ≤ k∑ i=1 b(i), (103)
and ∑n i=1 ai = ∑n i=1 bi. Here a(i) is the i-th largest entry in a. We first note that
n∑ i=1 Aii = tr(A) = n∑ i=1 λi(A).
On the other hand, for k ∈ [n− 1], we have k∑ i=1 a(i) = max v∈Rn,vi∈{0,1},1T v=k vTa
= max v∈Rn,vi∈{0,1},1T v=k tr(diag(v)Adiag(v))
≤ max V ∈Rk×n,V V T =I tr(V AV T )
= k∑ i=1 λi(A) = k∑ i=1 b(i).
(104)
Therefore, a is majorized by b. As f(x) = −xp is a convex function, according to the Karamata’s inequality, we have
n∑ i=1 f(ai) ≤ n∑ i=1 f(bi).
This completes the proof.

heading: D.2 PROOF OF LEMMA 2
text: According to the min-max principle for singular value, we have σi(W ) = min
dim(S)=d−i+1 max x∈S,‖x‖2=1 ‖Wx‖2.
As P is a projection matrix, for arbitrary x ∈ Rd, we have ‖PWx‖2 ≤ ‖Wx‖2. Therefore, we have max
x∈S,‖x‖2=1 ‖PWx‖2 ≤ max x∈S,‖x‖2=1 ‖Wx‖2.
This completes the proof.

heading: D.3 PROOF OF LEMMA 3
text: Suppose that λ(u) is optimal solution to
arg maxv|uTλ| s.t. g(λ; W1) ≤ 1. (105) Denote ne is the number of extreme points of
arg max v∈A(W1)
|(λ(u))Tv|.
Denote v1, . . . ,vne as extreme points of (105). We note that (105) is the dual problem for a scalar output three-layer neural network. By applying the previous duality theorem, we can write u =∑ne i=1 aivi, where vi ∈ A(W1). We also have |uTλ(u)| = ∑ne i=1 |ai|. Besides, we note that
1 = ‖u‖22 = ne∑ i=1 aiu Tvi ≤ ne∑ i=1 |ai|g(u; W1) = |uTλ(u)|g(u; W1).
This completes the proof.

heading: E CARATHEODORY’S THEOREM AND FINITE REPRESENTATION
text: We first review a generalized version of Caratheodory’s theorem introduced in (Rosset et al., 2007).
Theorem 7 Let µ be a positive measure supported on a bounded subset D ⊆ RN . Then, there exists a measure ν whose support is a finite subset of D, {z1, . . . , zk}, with k ≤ N + 1 such that∫
D
zdµ(z) = k∑ i=1 zidν(zi), (106)
and ‖µ‖TV = ‖ν‖TV.
We can generalize this theorem to signed vector measures. Theorem 8 Let µ : Σ→ RK be a signed vector measure supported on a bounded subset D ⊆ RN . Here Σ is a σ-field of subsets of D. Then, there exists a measure ν whose support is a finite subset of D, {z1, . . . , zk}, with k ≤ KN + 1 such that∫
D
zdµ(z) = k∑ i=1 zidν(zi), (107)
and ‖ν‖TV = ‖µ‖TV. PROOF Let µ be a signed vector measure supported on a bounded subset D ⊆ RN . Consider the extended set D̃ = {zuT |z ∈ D,u ∈ RK , ‖u‖2 = 1}. Then, µ corresponds to a scalar-valued measure µ̃ on the set D̃ and ‖µ‖TV = ‖µ̃‖TV. We note that D̃ is also bounded. Therefore, by applying Theorem 7 to the set D̃ and the measure µ̃, there exists a measure ν̃ whose support is a finite subset of D̃, {z1uT1 , . . . , zkuTk }, with k ≤ KN + 1 such that∫
D̃
Zdµ̃(Z) = k∑ i=1 ziu T i dν̃(ziu T i ), (108)
and ‖µ̃‖TV = ‖ν̃‖TV. We can define ν as the signed vector measure whose support is a finite subset {z1, . . . , zk} and dν(zi) = uid(̃ziui). Then, ‖ν‖TV = ‖ν̃‖TV = ‖µ̃‖TV = ‖µ‖TV. This completes the proof.
Now we are ready to present the theorem about the finite representation of a signed-vector measure.
Theorem 9 Suppose that θ is the parameter with a bounded domain Θ ⊆ Rp and φ(X, θ) : RN×d ×Θ→ RN is an embedding of the parameter into the feature space. Consider the following optimization problem
min ‖µ‖TV, s.t. ∫
Θ
φ(X, θ)dµ(θ) = Y. (109)
Assume that an optimal solution to (109) exists. Then, there exists an optimal solution µ̂ supported on at most KN + 1 features in Θ.
PROOF Let µ̂ be an optimal solution to (109). We can define a measure P̂ on RN as the pushforward of µ̂ by P̂ (B) = µ̂({θ|φ(X, θ) ∈ B}). Denote D = {φ(X, θ)|θ ∈ Θ}. We note that P̂ is supported on D and D is bounded. By applying Theorem (8) to the set D and the measure P̂ , we can find a measure Q whose support is a finite subset of D, {z1, . . . , zk} with k ≤ 2K(n + 1). For each zi ∈ D, we can find θi such that φ(X, θi) = zi. Then, µ̃ = ∑k i=1 δ(θ − θi)dQ(zi) is an optimal solution to (109) with at most 2C(N + 1) features and ‖µ̃‖TV = ‖µ‖TV. Here δ(·) is the Dirac delta measure.

Review summaries:
The topic of this paper is the duality theorem for deep neural networks with linear and ReLU activation functions. In particular, this study shows that the strong duality (i.e., zero duality gap) does not hold for the standard deep models but it holds for parallel deep neural networks which are ensembles of networks with an appropriate regularization. These results are certainly useful because it enables global optimization of parallel deep models via the convex dual programs. 

Using duality theory, this paper studies the duality gap between prime and dual optimization problems for deep linear (or relu) networks that have sequential or parallel structure. The major claim is that, assuming the networks is sufficiently over-parameterized, linear networks of depths at least 3 have nonzero duality gap, while strong duality holds for deep parallel networks. Similar conclusions are given for relu networks.

The authors theoretically analyzed the dual of minimum norm optimization of over-parameterized deep neural networks. Specifically, they focused on deep neural networks with linear and ReLU activation functions, as well as parallel architectures where the output of each branch is a scalar. First, the authors considered the linear NNs and showed that the duality gap of general deep NN is non-zero, but for parallel NN with enough number of parallel branches, that would be zero. Next, they considered neural networks with ReLU activation functions and derived the duality gap for standard 3 layers neural networks. However, for an arbitrary deep parallel NN with ReLU activation, the duality gap would be zero if the L-th power of Frobenius norms of the weights is used as the regularizer.

In this paper, the author studies the duality gap in the neural network training problem. They show that in general (deep linear networks and three-layer ReLU networks), the duality gap is not zero. However, when restricting the parallel architecture, the authors show that the duality gap is indeed zero.