Parallel Deep Neural Networks Have Zero Duality Gap
Authors: Yifei Wang
Tolga Ergen
Mert Pilanci
Venue: ICLR 2022 Submitted (2022)
Keywords: Deep neural networks
convex duality
convex optimization

Abstract: Training deep neural networks is a well-known highly non-convex problem. In recent works, 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 three-layer 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.

Under review as a conference paper at ICLR 2022
PARALLEL DEEP NEURAL NETWORKS HAVE ZERO DUALITY GAP
Anonymous authors Paper under double-blind review
ABSTRACT
Training deep neural networks is well-known highly non-convex problem. In re- cent work (Pilanci & Ergen 2020), it shown that there is no duality gap for reg- ularized 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 optimal- ity. We also demonstrate that the weight decay regularization in the parameters explicitly encourages low-rank solutions via closed-form expressions. For three- layer non-parallel ReLU networks, data matrices, however, the duality gap is non-zero for whitened data matrices. Similarly, by transforming the neural network architecture into corresponding parallel version, the duality gap vanishes.
show that strong duality holds for rank-1 I
INTRODUCTION
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 a highly non-convex optimization problem, simple algorithms, such as stochastic gradient descent, can find solution with good gener- alization 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 important tool to determine its optimal value and to characterize the optimal solutions. Even for a non-convex primal problem, the dual problem is convex optimization problem the can be solved efficiently. As a result of weak duality, the optimal value of the dual problem serves as 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 al. 2019), the design problem of an all-encompassing reward can be formulated as constrained reinforcement learning problem, which shown 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 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 & Pilancil (020c). Strong duality also
holds for deep linear neural networks with sealar output (Brgen & Pilanci 2020b). The convex

---

Under review as a conference paper at ICLR 2022
optimization formulation essentially gives 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 gradient descent or stochastic gradient descent, converge to the global optimum of the training loss.
Admittedly, the 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 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. (017). Xception Chollet (017) and SqueezeNet (landola et al. (0116) utilize the parallel structure. As the "parallel" version of ResNet (He et al. 2016a b). ResNe Xt (Xie al., (017) 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.) a (019)) com- pared to standard neural networks. On the other hand, it is known that overparametterized parallel neural networks have benign training landscapes (Haeffele Vidal 2017). For training & loss with deep linear networks using Schatten norm regularization, [Zhang et al. (2019) show that there is 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 duality gap for two-layer neural networks.
1.1 CONTRIBUTIONS
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 l regularization, pre- cisely 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 lz- 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 & regularization, even when the data is whitened, we show that the duality gap 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/stadard neural network in Table
1.2 NOTATIONS
We use bold capital letters to represent matrices and bold lowercase letters to represent vectors. De- note [n] = {1....,n1} nn). For a matrix W. E Xm2, for E [mi] and j E [ma]. we denote wf." as its i-th column and wiyh its j-th row. Throughout the paper, X E Nxd is the data matrix consisting of dimensional N samples and e X is the label matrix for a regression/classif- cation task with K outputs.
1.3 MOTIVATIONS AND BACKGROUND
Recently a series of papers PPlaaci & Ergen 2020 Ergen & Pilanci 2020b a studied two-layer neural networks via convex duality and proved that strong duality holds for these architectures.
2

---

Under review as a conference paper at ICLR 2022
Table 1: Duality gaps for L-layer standard and parallel architectures. we compare our duality gap characterization with previous literature. Each check mark indicates whether characterization of the duality gap exists for the corresponding architecture and the number next to it indicates whether the gap is zero not.
Linear
ReLU
= 2
L =
L>
3
L=
2
L ==
3
L >
3
Ergen & Pilanci (2020a)
2021a)
x
X
X
((0)
X
X
Standard
Bach (2017)
(0)
(0)
X
Pilanci & Ergen 2020
Ergen & Pilanc1 2021b
/(0)
X
Ergen & Pilanei [202Ic
70)
X
X
X
This paper
7(0)
V 0)
/
0)
/00)
0)
Parallel
Ergen & Pilanci (2021b
X
X
X
V(0)
V(0)
X
Zhang et (2019)
4(0)
7(0)
<(0)
X
X
Ergen & Pilanci (2021c
This paper
7(0)
(0)
7(0)
(0)
(0)
7(0)
Particularly, these prior works consider the following weight decay regularized training framework for clasifficationrreerssioo tasks. Given a data matrix X IR consisting of d dimensional N samples and the corresponding label matrix E RX,, the weight-decay regularized training problem for ccclar-output neural network with m hidden neurons can written as follows
3 (I 2
p: min (Xo( - y11 W1.w2 2
+ || 12)
(1)
where W1 Rd and E Rm are the layer weights, B 0 is regularization parameter, and the activation function, which can be linear ((z) = ReLU (0=) max(2 0}. Then, one can
take the dual of ( with respect to W1 and W2 obtain the following dual optimization problem
D max X
a y112 11y112. s.t.
max wi:lww 11
XX ( S 8.
We first note that since the training problem T is non-convex, strong duality may not hold, i.e.,
P 2 D. Surprisingly, as shown in Pilancii & Ergen (2020); |Ergen & Pilanci (2020b a). strong duality in fact holds, i.c., representations for the non-convex training problem in (I). However, extensions of this approach to deeper and state-of-the-ar architectures are not available the literature. Based on this observation. the central question we address in this paper is:
D, for two-layer networks and therefore one can derive exact convex
Does strong duality hold for deep neural networks?
Depending on the answer the question above, immediate next questions address is
Can we characterize the duality gap (P-D)? Is there architecture for which strong duality holds independent of the depth?
Consequently, throughout the paper, we provide full characterization of convex duality for deeper neural networks. Then, based on this characterization, we propose modified architecture for which strong duality holds regardless of depth.
1.4 CONVEX DUALITY FOR TWO-LAYER NEURAL NETWORKS
We briefly review the convex duality for two-layer neural networks introduced in (Ergen & Pilanci, 2020bla) a). Consider the following weight-decay regularized training problem for a vector-output neural network architecture with hidden neurons
3 min } (ix(WW)), YI + (1 (W W., 2
3

---

Under review as a conference paper at ICLR 2022
where W1 Rd and W2 E R are the variables, and 3 >> 0 is regularization parameter. Here o is the activation function, which can be linear ((2) = & or ReLU ((z) = max 0}. As long the network is sufficiently overparameterized. there exists feasible solution for such that oi ((W,))W, = Y. Then, a minimal norm varian of the training problem (3) is given by
1 ( + 222)) s.t. ((XW Y. W..W, 2
min
As shown in (Pilanci & Ergen 20200, after a suitable rescaling, this problem can be reformulated as
min W1. W
Σ
w
tow 2jj
s.t. o(W,)) = -Y // 2 I 1, E [m]].
(5)
where [m]] {..... (L....,,. m). Here w2.j represents the j-th of We and wi. denotes the j-th column of W1. The rescaling does not change the solution to (4). By taking the dual with respect W, and W2, the dual problem of (5) with respect to variables is convex optimization problem given by
max br (A S.I. max ||A (Xu)]l2 <
where A RRNKK is the dual variable. Provided that 2 mm, 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)
1.5 ORGANIZATION
This paper is organized as follows. In Section 2 we review standard neural networks and intro- duce parallel architectures. For deep linear networks, 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 archi- tecture and precisely calculate the optimal values for whitened data in Section 4 We also show that deep ReLU networks with parallel structures have duality gap.
STANDARD NEURAL NETWORKS VS PARALLEL ARCHITECTURES
We start with the L-layer neural network with the standard architecture:
fe(X) AL-1WL A = = Wi), VI E [L - = A0
where Φ is the activation function, W, E mm is the weight matrix in the I-th layer and 0 =
(W...., Wz 2 represents the parameter of the neural network. We also denote the input and output
dimensions as mo = d and m K for simplicity and assume that my 2 max(d, K}. VI [L 2-2).
We then introduce the neural network with the parallel architecture:
f (X) = WZ
A1,j ((A+-1,) W Wi.). M 1).
Ao.j = X. Vj E im].
Here for I E [L - 1], the 1-th layer has m weight matrices Wi, E Rm 1xm; where j [m]. Specifically, we let mi-1 1. short, we can view the output AL-1 from parallel neural network as a concatenation of m scalar-output standard neural work. In Figure [ 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.
Thiis corresponds weak regularization, i.c., in considered in Wei al. 2018

---

Under review as a conference paper at ICLR 2022
Input
Layer
Layer 2 Layer Layer
Input
Layer I Layer Layer 3 Layer 4
Figure 1: Standard Architecture
Figure 2: Parallel Architecture
DEEP LINEAR NETWORKS
In this section, we discuss the convex duality of deep linear network with vector output.
3.1 STANDARD DEEP LINEAR NETWORKS
We first consider the neural network with standard architecture, i.e., fo(X) XW, W Con- sider the following minimal norm optimization problem:
Pin
min (WilL.
Will s.t. XW WL ===Y,
where the variables are W Wi...., W. As shown in the Proposition 3.1 in (Ergen & Pilanci 2020b by introducing a scale parameter t, the problem (7 can be reformulated as
L L-2 + (tn
Pin
min 1>0
where Pin (1) is defined as
(tin(t)
min (wilf.)
Σ
w row Lg
l12,
(8)
s.t. || ll S St,t [L - 2), 1l 1,j [m1-1h.
XW1 =
The following proposition characterize the dual problem of (t) and its bi-dual, i.c., dual of the dual problem.
Proposition 1 The dual problem of Pin (t) defined in 8 is a convex optimization problem given by
(ti(()) = max tr
S.1. || XX,, ... W W1-2WL-111e S 1, |Will Si,i E [T. 2). |WL-1 1 There exists m S KN + 1 such that the dual problem Dim (t) be reformulated the bi-dual, i.e.
Dun(l)
min (Wi,)f
why [|2,
j=1
m"*
(10)
col XW WI.... W2-2,W2-1, = Y.
s.f.
1=1
|Wll St,ie L 2],j E [m*] lw S 1.j E [m*].

---

Under review as a conference paper at ICLR 2022
Detailed derivation of the dual and the bi-dual provided in Appendix B.I do not directly take the dual Pin that the objective function in Pin involves the weights of first L layer, which prevents obtaining meaningful dual problem. We note that bi-dual problem is related to the minimal norm problem of parallel neural network with aligned weights. Namely, the Frohenius norm of the weight matrices in each branch has the same upper bound t.
The reason why
For a matrix E R and > O, the Schatten-p quasi-norm of A defined as
"min (m,.)
1/p
||A|| =
Σ
d((A)
where (A) is the i-th largest singular value of A. The optimal value of Pin(t) and (tu can be precisely calculated.
Theorem For fixed 1 > 0, the optimal value of Piin (1) and Dri (1) are given by
Piu (t) -1-11- | Y2l
(11)
and
(ti(() =t t (1- X where X is the pseudo inverse of X and || ||+ represents the nuclear norm.
(12)
As result, the duality gap exists, i.e., P > D, for standard deep linear networks with L 2 3, if the singular values of y are not equal to the same value. We note that optimal scale parameter t for the primal problem Pin is given by t" = || To the best of our knowledge, this result wasn't shown previously. We leave the proof in Appendix B.2 and provide conditions WI,..., W. to achieve the optimal value.
In the calculation of (t), utilize the following proposition. Proposition 2 Suppose that W E Rdx K with rank is given. Assume that zrror 0,..., L. Consider the following optimization problem:
mii
(|
[WL])?)
S.t. W.W2 ... WL W.
(13)
Then, the optimal value of the problem (3) is given by [ 11
S2y1.
3.2 PARALLEL DEEP LINEAR NEURAL NETWORKS
For the neural network with parallel structure, consider the minimal norm optimization problem:
L-1 1
min (Wi,)f-
Σ
W 1 + | [WLl
2
t=1
(14)
m
s.t.
Σ
XW
W WL-22
row YY
Due to a rescaling to achieve the lower bound of the inequality of arithmetic and geometric means, have the following result.
Proposition 3 The problem 14
can be formulated as
row 2/L w
min [Wiyhe(4)
2
L,j 2
1=1
(15)
S.f.
XW L.
WL-2 W1-1 w.s = =Y,
1=1
Wialee 1,, [L 2).j E [m]. // S 1,j E [m].

---

Under review as a conference paper at ICLR 2022
We note that 2/ is non-convex of and cannot take 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 consider another regularization, i.e.,
min (Wis)
Woyll + W
2
1=
(16)
s.t. Σ XW15... WL-2 Y.
Proposition 4 The problem (16) can be formulated as
m
pprl
min (Wi.)
W
row Lg
2
j=1
m
(17)
s.t.
XW1, 1j... WL-2, w wTJ NOW Y, j=1
I wllle S 1.leeL 21, [ / S j.j [m].
The dual problem of phn is convex problem
Dprl
max tr(AT))
A
A XW ... Wi-2W1-1lle S L/2,
(18)
AA W. s L,ie [L - 2], /|WL-llll $
For the parallel linear network, the strong duality holds. Theorem There exists m < KN + such that as long as the number of branches m 2 m.. the strong duality holds for the problem [6 Namely, pir Dirl The optimal values are both L |
2
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.
3.3
GENERAL LOSS FUNCTIONS
Now we consider general loss functions, i.c.,
8 L (XW, WT. Y) + Σ w. W.
min
where f(Z, Y) is general loss function and B 0 is regularization parameter. According
Proposition 2 the above problem is equivalent to
BL 2/L SayL
min ((WW, Y
(19)
2
The lg regularization term becomes the Schatten 2/ quasi-norm on W to the power 2/L. Suppose that there exists W such that I(WW, Y) 0. With 3 - 0, asymptotically, the optimal solution to the problem [99 converges to the optimal solution of
min W
W| 2/L S2/z> s.t. ((WW, Y) = 0.
(20)
In other words, the l regularization explicitly regularizes the training problem to find a low-rank solution W.

---

Under review as a conference paper at ICLR 2022
4 NEURAL NETWORKS WITH RELU ACTIVATION
Now, we focus on the three-layer neural network with ReLU activation, i.e. x(z) = [ 0}.
4. STANDARD TIREE-LAYER RELU NETWORKS
We first focus on the three-layer ReLU network with standard architecture. Consider the minimal norm problem
PROLU
min
|Wil s.t. ((XW1) W2) W3 Y.
(21)
(W ) 2
Here we denote (z)+ = max max 0}. Similarly, by introducing a scale parameter 4, this problem can be formulated
PRELU = min - PRoLU(t),
1>0 2
where PRELU (t) is defined as
PRoLu(t)
min
Σ
w3,1 Il2.
(W.).-
(22)
s.t. W Ill - t, w 2 l2 S 1,j [ma].
(XW1)4 2 W, Y.
The proof is analagous the proof of Proposition 3.1 in (Ergen & Pilanci 2020b). For W1 Rdxmm we define the set
A(W1) =
- 1}.
(23)
Proposition 5 The dual problem of PReLU(t) defined in (22 is convex problem defined
DReLU(t) max mmxxt((A s.t. |A |AAv|22 L.
St.
(24)
There exists m S KN + such that the dual problem can be reformulated as the bi-dual problem,
i.e,
min DRA..U()= (Wi.)
Pow [|2,
Wa XK
(25)
s.t. Σ (XW1,)) w2)) w Y. / S st, 11 1.
For the case where the data matrix with rank and the neural network is with scalar output, there no duality gap.
Theorem For a three-layer scalar-output ReLU network, let X be a rank-one data matrix. Then, strong duality holds, Le., PReLU(t) = DReLU(t). Suppose that X is the optimal solution to the dual problem (t), then the optimal weights for each layer can be formulated as
Wi Aasiis((((()))
Pr.
Here Po | aolla and P1 E Th satisfies ||e||| 1.
Now, consider the where the data matrix is whitened, i.e., XX" I, and Y has orthogonal columns. We leave the proof of Theorem and the characterization of optimal solutions in Appendix
8

---

Under review as a conference paper at ICLR 2022
Theorem 4 Let (X, Y be dataset such that XX" In and Y has orthogonal columns. Then, the optimal value of PRELU (t) and (R) are given by
K
(t)Lu(t) = =t
(1(x5)+1122 2/33 + ( +1(-8))++12
(26)
and
Σ (1ly,))+12 + 1111-1+++11))
(27)
Suppose that Y is the one-hot encoding of the label. Then, note that yy 2 0 and 1|(y))+ll2 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.
4.2 PARALLEL DEEP RELU NETWORKS
For the parallel architecture, we show that there is no duality gap for arbitrary deep ReLU network with large enough number branches. Consider the following minimal norm problem:
pprl ReLU = min
W + WLll
1=
(28)
s.t.
((WW. WT-25)+ w enl w-1 = YY
Proposition 6 The problem
28
can be reformulated
min
w E,j 12,
2
j=l
(29)
s.t.
(((X
W
= Y,
[Wille S1. L - 2], 1/ 1LL-1,jl2 $1. [m].
The dual problem (29 is convex problem defined as
Deel max tr(A YY, s.t.
max ((W W WW 1
| V & L/2.
(30)
For deep ReLU network with parallel architecture, the strong duality holds.
Theorem The strong duality holds for (29h in the sense that ReLU = DReLu for m 2 m², where m² upper bounded by KN
Similar to case of parallel deep linear networks, the parallel deep ReLU network also achieves zero- duality gap. Therefore, to find the global optimum for parallel deep ReLU network is equivalent to solve convex program.
CONCLUSION
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 more. Meanwhile, for neural networks with parallel architecture, with the regularization of L-th power of Frobenius norm in the parameters, zero. A limitation of our work is that we primarily focus on minimal norm interpolation problems. We expect to generalize results general regularized training problems.
show that strong duality holds and the duality gap reduces to

---

Under review as a conference paper at ICLR 2022
6 ACKNOWLEDGEMENTS
This work was partially supported by the National Science Foundation under grants ECCS-2037304, DMS-2134248, the Army Research Office.
REFERENCES
Francis Bach. Breaking the curse of dimensionality with convex neural networks. The Journal of Machine Learning Research, 18(1):22-661, 2017.
Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge uni- versity press, 2004.
François Chollet. Xception: Deep learning with depthwise separable convolutions. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 1251-1258, 2017.
Tolga Ergen and Mert Pilanci. Convex geometry of two-layer relu networks: Implicit autoencoding and interpretable models. In International Conference on Artificial Intelligence and Statistics, pp-
4034-4033. PMLR, 2020a.
Tolga Ergen and Mert Pilanci. Convex duality of deep neural networks. arXiv preprint arXiv:2002.09773, 2020b.
Tolga Ergen and Mert Pilanci. Implicit convex regularizers of enn architectures: Convex opti- mization of two-and three-layer networks in polynomial time, arXiv preprint arXiv:2006. 14798, 2020c.
Tolga Ergen and Mert Pilanci. Convex geometry and duality of over-parameterized neural networks. Journal of Machine Learning Research, 22(212):1 2021a.
Tolga Ergen and Mert Pilanci. Global optimality beyond two layers: Training deep relu networks convex programs. International Conference on Machine Learning, pp. 2993-3003, PMLR, 2021b.
Tolga Ergen and Mert Pilanci. Revealing the structure of deep neural networks via convex duality. In International Conference on Machine Learning, pp. 3004-3014. PMLR, 2021c
Farzan Farnia and David Tse. A convex duality framework for gans. In Ben- gio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Gamett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran Asso- ciates, Inc., 2018. URL http:/tts//pppoceeeeiiie https//sssc..pppppee////101// pctpc///pppe//1////ieeee/ 351ca1180F52277444900eaaa-----13
pdf
Benjamin D Haeffele and René Vidal. Global optimality in neural network training. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 7331-7339, 2017.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 770-778, 2016a.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Identity mappings in deep residual networks. In European conference computer vision, pp. 630-645. Springer, 2016b.
Forrest N landola, Song Han, Matthew W Moskewicz, Khalid Ashraf, William Dally, and Kurt Keutzer. Squeezenet: Alexnet-level accuracy with 50x fewer parameters and; 0.5 mb model size. arXiv preprint 1r0iv: 2016.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep con- volutional neural networks. Advances in neural information processing systems, 15:1097-1105, 2012.
Santiago Paternain, Luiz FO Chamon, Miguel Calvo-Fullana, and Alejandro Ribeiro. Constrained reinforcement learning has zero duality gap. arXiv preprint arXiv: 2019.
10

---

Under review as a conference paper at ICLR 2022
Mert Pilanci and Tolga Ergen. Neural networks convex regularizers: Exact polynomial--ime vex optimization formulations for two-layer networks. arXiv preprint arXiv:2002.105553 2020.
Saharon Rosset, Grzegorz Swirszez, Nathan Srebro, and Ji Zhu. LI regularization in infinite di- mensional feature spaces. In International Conference on Computational Learning Theory, pp.
544-558. Springer, 2007.
Christian Szegedy, Sergey Ioffe, Vincent Vanhoucke, and Alexander Alemi. Inception-v4. inception- resnet and the impact of residual connections on learning. Proceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017.
Colin Wei, Jason D Lee, Qiang Liu, and Tengyu Ma. On the margin theory of feedforward neural networks. arXiv preprint arXiv: 180005539, 2018.
Saining Xie, Ross Girshick, Piotr Dollár. Zhuowen Tu, and Kaiming He. Aggregated residual trans- formations for deep neural networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 1492-1500, 2017.
Sergey Zagoruyko and Nikos Komodakis. 160.v:1605.07146 2016.
Wide
residual
networks
arXiv preprint
Hongyang Zhang, Junru Shao, and Ruslan Salakhutdinov. Deep neural networks with multi bolti-branchh architectures are intrinsically less non-convex. In The 22nd International Conference Artificial Intelligence and Statisfics, pp. 1099-1109 PMLR, 2019.

---

Under review as a conference paper at ICLR 2022
A STAIRS OF DUALITY GAP FOR STANDARD DEEP LINEAR NETWORKS
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
(t)
min max tr Y) - (1A'XW, WL-2w 11) (Wi)
(31)
s.t. |W,lle StiE (1, 1.
By changing the order of L 2 mins and the max in (1. for = 1, L 1-2, 2, we can define the 1-th partial "dual" problem
(t) = min max min
W.....W A WiiI..., W. YY II (IAAXX WL-2wL-1ll221) (32)
s.t. |l S St,ie [L 2]. 1.lll1ll 1.
For = 0, 1 (1) corresponds the primal problem Pún (l), while for = 2, D (1) is the
dual problem Din (t). From the following proposition, we illustrate that the dual problem of D corresponds to a minimal norm problem of neural network with parallel structure.
Proposition? 7 There exists m S KN such that the problem D (10 (t) equivalent to the "bi- dual" problem
w
row by
112.
s.t.
XW, .... W.WH1.... WL-2, W why row Y, j=1
(33)
| Stiee [4, W - l,... L 2- E [m²],
l[ 1WE-1, 1 ll1 11 1 [m"],
where the variables are W; E mm for i E [1] Wij E Rmm--xm,, for = 1+ 1,..., L 2 j E [m*], W 1 1 and WL E Rmn Xma.
We can interpret the problem 33 as the minimal norm problem of a linear network with parallel structures in (Z 1)-th to (L 2) layers. This indicates that for I = 0, L 2, the bi-dual formulation of ( (t) can be viewed as an interpolation from a network with standard structure to network with parallel structure. Now, calculate the exact value of 100 (4).
Proposition 8 The optimal value 1 (t) follows
D (1) (L. X Y 1ay10-2)
(34)
Suppose that the eigenvalues X Y are not identical to each other. Then, we have
(tin(t) D 2) (t) > DIL (t)> D D (t) D(t).
(L-
(35)
In Figure we plot D (9) (t) for l O...., for an example.
B PROOFS OF MAIN RESULTS FOR LINEAR NETWORKS
B. PROOF OF PROPOSITION II
Consider the Lagrangian function
K Σ
LWW..... WL,
w WL tr(AA XW ... W
(36)
12

---

Under review as a conference paper at ICLR 2022
o
10
Figure 3: Example of D (t).
Here A E R. NxK is the dual variable. We note that
P(t) = min max L(W1..... WL, A),
Wi....WZ We A
s.t. Wille S St,tE E [L 2), W/ so--l I 1.j E [mL-1),
min max tr ( Y) Σ I1 (IA"XW Wo-2w1-1ulk $1). Wi..., WT.1
(37)
s.t. Well 1 i E [L 2], 1/ L- 2-1l S 1, E [ML-1).
WT... W.....W. W max tr A Y) (IA (IA"XW W (1).
min
S.t. | S e [L - 2], ||w,--1112 1
Here I(A) is if the statement A is true. Otherwise is +oc. For fixed WI.... W the constraint on W. linear so we can exchange the order of maxa and minw, in the second line of
37
By exchanging the order of min and max, we obtain the dual problem
D(t) max min tr(A" YY) -
(IA ... W2-2WL-1l22 $1),
A W.... WL-2
s.t. |W st,te LL 2), 1/WL1/l 1
ma A
(38)
s.t. |A XW WL-2WL-112 1 V/ S slie [L - 2]. - 1.
Now derive the bi-dual problem. The dual problem can be reformulated
max tr(A tY(TTY,
A
s.t.
A XW, ... W W1-2W1-1lla ll12 $ (W, W WL-2, WL-1) E e.
(39)
Here the set θ is defined
θ ((W
W WL-1 W. t,i - 1 1).
(40)
By writing 0 = (W1, W. WL-1), the dual of the problem 39 is given by
min | TV. s.t. Sace XW, W2-221.-1d4
(41)
Here Σ + K is signed vector measure and Σ is o-field of subsets of e. The norm || the total variation of μ, which can calculated by
{ ae (0)))))()))) =: Σ u:(0)dui(0))
K
pl b = sup
(42)
13

---

Under review as a conference paper at ICLR 2022
P1
where we write μ
The formulation in 41 has infinite width each layer. According to
MK
Theorem in Appendix the measure in the integral can be represented by finitely many Dirac delta functions. Therefore, we can rewrite the problem (41) as
min
11
(43)
Σ XW 1 ... W1-2, 1o0 Y,
[W,lle Stie [T. - 2], l1 W S 1, E [m*).
Here the variables are W. for E L - 2] and j E [m*', Wi-1 and W L. As the strong duality holds for the problem (33 and (39. we reformulate the problem of Diin()) the bi-dual problem 43
B.2 PROOF OF PROPOSITION
We restate Proposition 2 with details.
Proposition 9 Suppose that W Raxk with rank is given. Consider the following optimization
problem:
1
min 2
(IW1 + ... |W21?). S.. W.W. WL = W,
(44)
in variables W, E 1x Here = d, mL K and m, 2 for i = 1, L 1. Then, the optimal value of the problem (44) is given by
2/L
(45)
SaLL"
Suppose that W UEVT
The optimal value can be achieved when
W; = U,-12 i= U,
(46)
Here U, Rexm; satisfies that UTU, =I
We start with two lemmas. Lemma Suppose that A E Sux is a positive semi semi-definite matrix. Then, for any < p we have
A
MAA..
(47)
i=1
Here di is the i-th largest eigenvalue of A.
Lemma Suppose that P Iddxd is projection matrix. Then, for arbitrary W BdxK we have (PW) S (W),
where o; (W) represents the i-th largest singular value of W.
Now, we present the proof for Proposition 2 For = 1, the statement apparently holds. Suppose
that for L = this statement holds. For + 1, by writing A W.... W1+1, we have
min W
|| i s.t. W, W.... W W
min W 12 1| 2/1
s.t. W,A = W,
(48)
min + 1//1
2/1
s.t. W,A W, | 5.
Suppose that is fixed. It is sufficient to consider the following problem:
min A
2/1 2/12
s.t. W,A W, W.|.W,lr tt.
(49)
14

---

Under review as a conference paper at ICLR 2022
Suppose that there exists W1 and A such that W WIAA'A = W. As WAT = WIAAt, according to Lemma 2
W1A.
Then, have WAT
wA s |Wilee I t.
Therefore, (WA), A) is also feasible for the problem 49 to
Hence, the problem 49
is equivalent
2/ min 2/0 S.L. WATA W, |AA || St.
(50)
Assume that W is with rank Suppose that A UEVT, where E Ro Here ro Then, we have At VE VE-'U. We note that
WAT
= -tr(WVE WTW"
(51)
= W
Denote G(V) WV. This implies that
Σ oi(A) (G(V)), st.
Therefore, we have
TO L E.CCAPP))
1+1
Σ (oi(A)"
2 Σ (C(V))
As WVVV W. the non-zero eigenvalues of G(V) exactly the non-zero eigenvalues of WVV = WWT i.c. the square non-zero singular values of W. From Lemma
we
have
(GVV)) 1/41)
X(G(V)) 1/41
o. (W)
(52)
1=1
Therefore, we have
(1+1//1
To
Σ (a((W)rrat)
A
2/1 Son
(A) 2
(53)
This also implies that
2/1 min |A|
|||///
s.t. W,A W St
2/13
(+1)/1
(54)
2/1
Σ (W)
Suppose that W = Ei i. is the SVD of W. We can let
2/(+1)) 1/2
El= of
1/(+1) u10
pf
t
(55)
W1
t
Pio 2/1111) of.
El o, ?
1/2
Here ||p:||2 = 1 and p: p; = 0 for # j. Then, W,A = W and Walle S t. We also have
1/1
2/L A
2211
Σ 2/(+1)
2/(+1)
Say1.
i=1
(41)/11
2/1
Σ
os (W)
i=1
15

---

Under review as a conference paper at ICLR 2022
In summary, we have
min 1² +1| +1| S221 s.t. WIA W.
Will St.
(+1)/l
=min t2 + 1t 2/1 1>0
Σ (W)
(56)
1) Σ (W)) (111//2
||
2/((+1) S2/041)
This completes the proof.
B.3 PROOF OF THEOREM 1
We first compute the optimal value P the primal problem. From Proposition 2 the minimal norm problem 7 equivalent to
min L W
2/L Sa/n. s.t. XW Y,
(57)
variable W E Baxk According to Lemma 2 for any feasible W satisfying XW Y, because Xtxw x and X is projection matrix, we have
L||
2/1/ 2 L v
2/1 Sayz.
2/L Saye.
(58)
We also note that XX XX XW Y. Therefore, X Y is also feasible for the problem This indicates that Pii- Y
2/1. S25t.
On the other hand, for feasible point (WI...., WL) for (f) we note that (W1/t,..., WL-2/t, W1-11 (1,th-2W,, n))== is feasible for Piin (1). This implies that 2l-22 Pin
Pli (1), or equivalently, Pin(t) t (pm (ln Recall that
T-2
Pin min
12 + (4-2) (1--2) P(m (1)
t>0
2
(59)
L
2 (Pim
This implies that Pnn
|X 1//21 and
Pin (f) -t
x Y
Sayar
(60)
For the dual problem (t) defined in 388 we note that
A Xxw.
Wr.-aw
XW ... Wn.-elellwz.-1ll
L-2
< X
W
(61)
A X
II 2=1
W || t A
The equality can be achieved when W, tu for I E [L. 2], where |ulla for I 1,..., L 1. Specifically, we set u = w and let ug as right singular vector corresponds to the largest singular value of A A'x. Therefore, the constraints A is equivalent to
| X||2 < (1--2)
(62)
Thus, according to the Von Neumann's 's trace inequality, follows tr(A = tr xxxx) <
(1-)) ( X
(63)
As a result, we have D (t) = (4-2) X (1--22 duality gap exists for the standard neural network.
X 122/2 = Pin (t). Namely, the
16

---

Under review as a conference paper at ICLR 2022
B.4 PROOF OF PROPOSITION 3
For simplicity, we write W WI-1ij = w 1. and Wr.f Wid for E [m]] For the j-th branch of the parallel network, let Wi, on Wt, for E [Z]. Here on, for [L] and they satisfies that Ii at = for j E [m.. Therefore, we have
XW 1..... Wt 2- W WLJ XW 1.j..... W 22 L.3
(64)
This implies that (Wi,) (e( is also feasible for the problem inequality of arithmetic and geometric means, the objective function
14
According to the the lower bounded by
m 1
W
L.
2/L
W
(65)
1=1
L
EI
W 12L
2
11 W Willl
The equality is achieved when aij
Weylle for 1 [4] and j [m]] As the scaling
operation does not change Il
||W,,5
2/L we can simply let [|illle and the lower bound 2/I.. This completes the proof.
becomes
$ E [W
2/
Em w/ 2
B.5 PROOF OF PROPOSITION
We first show that the problem (6) is equivalent to 17 The proof is analogous to the proof of Proposition 3 For simplicity, we write W W--1j w and WL. who
L. for [m]] Let
aij > 0 for I E [L] and they satisfies that I ai 1 for j [m]. Consider another parallel network [W..heeee) whose j-th branch defined by W an WT for I E [4]. As I 0n 1, we have
FOw = XW W WW-2, L-1 LLj. XW13 WL-2 W WLS
(66)
This implies that (Wij)en (eeeeeee))em is also feasible for the problem 16 inequality of arithmetic and geometric means, the objective function in is lower bounded by
According the the
W
m
(on, Wisl(e)
(67)
j=1
ΣI W Will..
1=
I Wi.l for [4] and j [m]] As the scaling Wislle
The equality is achieved when aij
operation does not change - [WL,llF, we can simply let ||Wi, and the lower bound
becomes & Σm W., E [[wzyy 2. Hence, the problem (I6) is equivalent to (17)
For the problem
consider the Lagrangian function
L WL)
L(W
Fow w Lag
22 + tr
AT
A
Σ 1=1
XW 1. WI-1 WLy))
(68)
2
17

---

Under review as a conference paper at ICLR 2022
The primal problem is equivalent to
min max L(W I...., WL,4), Wi..,,, Wt A
s.t. [ F S Stje mm]. I [L 2]. |WT.-1 S 1.j [mz-1]:
max L(W I....... WL,
W W2- A WL
(69)
s.t. Wi, F S 1, I E [L - 2], 1 S 1.j [m]]
mi
min max tr(A YY - Σ Wi--WW-
I XIA' W2 1, L/2).
j=1
s.t. Wiille 11,E [L.
/ 2-11 1 [m]
The dual problem follows
Drrl max tr(A A
s.t. | XW 1. ... WD-2.lle S L/2, WiWee 1,/ E [L- 2), // 1, [m]
(70)
max trAA' Y),
s.t. A XW .... WL-2WL-1112 - L/2, W.ll 1, E [L. - 2, w. 1 1.
B.6 PROOF OF THEOREM 2
We can rewrite the dual problem as
D max ir A Y),
s.t. A XW WL-2WL-1ll $ L/2,
(71)
YW WL-2 6,
where the set θ is defined as
θ ((W1.... WL-2 WL-1) = 1, -L- -2, 2/,1///-1lle S 1}.
(72)
By writing (W given by
W1-2. wr.1),, the bi-dual problem, i.e., the dual problem of 71 is
min ||||
(73)
s.t. Jose XW, WL-2wZ-1dH(0) Y.
Here μ + K a signed vector measure, where a-field of subsets of and || its total variation. The formulation in 773 has infinite width in each layer. According to Theorem Din in Appendix E. the measure in the integral can be represented by finitely many Dirac delta functions.
Therefore, there exists m KN such that we can rewrite the problem 73
m
WW lla.
(74)
XW 1. W2.-2, W w Y,
[W < 1,1 T. 2), w| 1-1--ll2 ||| S 1,j [m*].
Here the variables are W. for / [L - 2) and j [m*], WL-1 and W.. This is equivalent to (I7). As the strong duality holds for the problem and (73). the primal problem (17 p is equivalent to the dual problem (7 long 2 m².
18

---

Under review as a conference paper at ICLR 2022
Now, compute the optimal value of Dma Similar the proof of Theorem the constraints in the dual problem (71) is equivalent to
show that
|| T./2.
(75)
Therefore, we have
L 2 I
tr(A" Y & ||AX | -
(76)
This implies that lin
D
- |
B.7 PROOF OF PROPOSITION 8
We note that
maxtr(A (ATY) Y),
| XW
WL-21l2 $ W 24, 1,.,,..,,11 1-2
(77)
Y) s.t. A " XW,... will2 S (1--2-)))
max A Witi..WW.. WL-2
min
Therefore, we can rewrite (() as
( min max Ir(A Y), W.....W, W.
s.t. | A XW; Willa S (1-2-0),
|W. 1, i E [1]
(78)
min max (L-2-0) YY),
Wi...W;
s.t. | T XW1... will s 1, st,ie 17.
From the equation
note that
min max YY WI... W A
W,ll 1, 1, s.t. XW,,
st,ee [bb
min
W1425ll2
(79)
s.t. |. & Sti -- |wr-lllle S 1.j [mz-1];
XW, W42 =Y
X Y $25042)
This completes the proof.
C PROOFS OF MAIN RESULTS FOR RELU NETWORKS
C.1 PROOF PROPOSITION
For the problem of P(t), introduce the Lagrangian function
K
L(W,, W2, W According to the convex duality of two-layer ReLU network, we have
A)
Σ
|
row
l2 - ur(A TTAT(((SES (((XW1) W2) Wa Y)).
(80)
j=1
max tr (A Y) IIIIAA ((XW)) $1) (t) |Wwllest[[/alll
min
min max min tr(A T Y) ((WW.) $1) IlWilles A ||wallg1
(81)
= min max maxtr(A s.t. |ATvll2 11, E A(W1)
iiilles A
19

---

Under review as a conference paper at ICLR 2022
By changing the min and max, obtain the dual problem.
(t) max maxtr(A s.t. || |A'vila vil2 s,,e A(W1), W St.
(82)
The dual of the dual problem writes
min p [||TV,
I. lle St.llallas (XWW1) w2) du (W1, W2) = Y.
(83)
Here ys is signed vector measure and || u TV is its total variation. Similar to the proof of Proposition we can find a finite representation for the optimal measure and transform this problem to
min (WiJ) WEER 1 1m W.ERm XK
W
j=1
(84)
(eWWi))+22. W3. = Y, [|illl st, l|wallll S 1.
Here m S KN + 1. This completes the proof.
C.2 PROOF OF THEOREM 3
For rank-1 data matrix that X = cat suppose that A = (XWi)) It easy to observe that A (c)+ + (-c))aa
Here we let a1,+ = (W,ag)+ and an. = (-Waao))+
For three-layer network, i.e., L 3, suppose that A is the optimal solution to the dual problem (t).u(t). We consider the extreme points
arg
max
(85)
|| I[W rst.][wallss
For fixed W1, because aT a a1,- = 0, suppose that
We u1a1+ U2a1,- + Ugr,
where r" aj,- = r" a-aa 0 and ||||| = 1. The maximization problem on W2 becomes
arg max (A* (A+) |a,+
s.l. u |a 112 + u + +
v3 1
(C*) and (-)) have different signs, then the optimal value is
max
(aa)
[12]
And the corresponding optimal W.-1 is WI-1 a 01.-2++||arr-22 2,+ or wz-1 ar.-2.-|laar.- 2.-1 Then, the problem becomes
arg max max (
We note that
max 1|a ||2 ||a.. [1
WF
W W1/12|a00: 1" |11||0012
Thus the optimal W, follows
Wi ('sign(((A*)) (c)+ (c)) (x)
Here Po aooll and P1 I satisfies ||p,|| This also gives the optimal W2 P1-
On the other hand, if (A (A*) and (-*) have same signs, then, the optimal wa follows
= [(0
The maximization problem is equivalent to arg max
( 13 ((>* (2 |a6-2
By noting that |ar-2, 112 |la ||t 2,+ 1
W 2o 113
| | ||
10 (1*)211an113
the optimal W₂ follows
Wi = (sign(((>)) (-))
|(X*)
Here Po aa0/|aaolt and P1 T satisfies
|P| || This also gives the optimal W2 P1-
20

---

Under review as a conference paper at ICLR 2022
C.3 PROOF OF THEOREM 4
We restate Theorem 4 with details as follows.
Theorem Let (X, Y be a dataset such that XX* T In and has orthogonal columns. Then, the optimal value of PRELU (1) and (Ro(x(() are given by
k
(R)LU(t)= =
(1(x))+1122 2/3 +1(--++++12))
(86)
and
DR t-
Σ (116,;) 11(-y;)+11
(87)
For the bi-dual formulation of (ReLU( defined in can be constructed as
25 the optimal weight matrices for each layer
Porr
Φ 1rr
W,r
110.rl11
Wa.
|
for = 1,....,.,. ,2K. Here (00.23-17 20,25)
(y)()))+, x (-y;)+), 11 = 1, 11, E
For PRoLu(t), the optimal weight matrices for each layer write
2K
W
gr
T P.r: W2 [ 11,2k]
@
1|
Here
[1yy))+ 1123
92f+1
E (1(3s)) (115))+122 22/3 + +1(-85)+1233) 2//3) 3/2
11(-y,)+112 1//3
92j+2
(>K (116r)) 2/3
+12/3 + +1((-y)++12 12/3))
3/2
We require that |11, f E [2K] and TT, = f i +
Since XX" In. we can characterize the set as
Ulwiles:
{(z)+1z E R ||z/22 S t).
(88)
Here A(W,) 1) is defined in (3). For one thing, for z E R.V. ||2||| S t. we can let Wi = XTzvT and
W2 V, where E R with |v||a 1. Then, | ||. S t, |
and (XW1) w2)+
(z) For another, for any W1 |F S and ||wll S 1, we note that
[(XW1) w2 ll - || [ + 112 S (XW ) S |XWW $ W|Wl St.
Therefore, U|W] (z)) N ||z||2 t).
24 is equivalent to say that t (z) I 1 for all z E R satisfying ||z||2 < 1. As Y has orthogonal columns, we note that
Thus, the constraint A in the dual problem
K - - -( Σ j=1
tr((A') -
+ 1 (I(x)))+
1=1
Suppose that (y,)= and (-y,)+ # for ffr L,..,,K. K. Then, the dual problem is minimized by
(y1)+
(-y1)+
(yk)+
(-yk)+
Λ --1
[[y1))+ll
[[-y:)+1le>
[[yx)+ 11a
[[-yx)+
We also verify that
(89)
21

---

Under review as a conference paper at ICLR 2022
Suppose that (2)+ Σ aj.
(-8,) + r, where R is orthogonal to ITys)= 43, --y))_1 -
(y,)+ and (-y,)+- Here oj,,, 03, 2 O. As (2) - | S 1, we have
Σ
(0 + (22)) 5 - -1-111 1. ==1
We note that
K (0g) - 0,,))
K
[I
I3)+
S
Σ
(a + +052) S.
(90)
Thus, A satisfies the constraint 89
We can characterize the optimal layer weight the bi-dual problem as the extreme points that solves
arg max W. St.l
((X)))(
(91)
These extreme points correspond to the constraints
(A [1y,)
+(yy)+
$1, $1, (A t(-y,)+ 1. 11(y5;++1 12
In other words, the dual problem equivalent to (I.L.(() max YY)
A
(y,)+ 1 12
1,, AT (-y,))
(92)
s.t. A T
$1,1jsk.
[[ ((-,))+ll2]
Now, we consider an arbitrary matrix W, satisfying W F L. Denote
P(W1) maxtr(AA Y), s.t. || v112 1, A(W1).
(93)
A
Suppose that A is the optimal solution. Then, we have
K Σ (A:)T ((y,)+ - (-ys)+)
tr((A'))
j=1
(y:)+
Σ (A))
1[(y))+112 11(y))+112
Σ (A;)* (-ys)+ ==1
[1(-y;)+1p 11(-ys)+1lz
For vector X N define
g(A: W1) = max
(T((XW))ww2)4
(94)
||wa||<1
For given u E R we want to estimate
max ju s.t. g(A: W1) 1
(95)
The following lemma gives an upper bound.
Lemma Suppose that g satisfying ||u||2 1. Then, for arbitrary À satisfying g(>; Wi) < 1, we have Ju X < 1/g(u; W.).
+I and 02s+2 = I[ 1+ For simplicity, we write g(z; Wi) = g(z). We note that Xÿ satisfies that 9(A5) 1. According Lemma have
Denote z2j+1 =
[x,)+
(-)))
[[(y))+ ll2 g(22)+1)
1(>r))112 g(22)42)
P*(W,) tr(((t())))))))
Σ
22

---

Under review as a conference paper at ICLR 2022
This serves as upper bound for P* (W.). We note that for IN,, we have
g(u)²
max
Iu" ((XW))
w2)
max wwalll
In' ("WW) w2]
=I|u' ((XW1)+ 1
<|lu" XW l
$ str(uu' XW, XW,,WWW w/
Then, we have
2K
2K Σ 2
gg(z,) str ur
XW
<(x(XW,WXX)) 12.
j=1
According to the Holder's inequality, we have
2/3
1/3
2K
Σ
(
Σ g(,))²
K
(11x))++12* + + +1((-5)++1200)
Thus, it follows
K
j=1
3/2
2t
[1(x,)+112 2/3
+1(-88)+1133)
The optimal g(z,) follows
+1((x;)+112' 1/3
g(Z2)+1)
j=1 (1(xx)) 12/3 + -I1( -1(-8r))+12)) 11/30) 3/2
+11(-8,)+11**
g(Z2)+2)
Σ (16x)))+123** + +1(-88)++12 11/33) 3/2
This bound can be achieved for
W1 Σ g(zz) (Zzz))z,0T..
where 11 for E [2K] and TT
$1. = 0 for i j
C.4 PROOF OF PROPOSITION 6
Analogous the proof of Proposition we can reformulate 28 into 29
The rest of the proof is
analogous to the proof of Proposition For the problem 29 we consider the Lagrangian function
L(W WL)
L
(96)
w Laj
row
ll + tr
AT - Σ ((WW 1=1
W w2.,)))22_.)
2
==1
23

---

Under review as a conference paper at ICLR 2022
The primal problem is equivalent to
ppri
ReLU
min max L(W1,
,.......... ..... Wr, A),
Wi....W
[Wisl S S15j E [mm], [L. 2), l/ L-1, 11, E [mz-1))
min
min (WI,.... Wr,,
W.....W--I Wz
s.t. | 1, [T. - 2). -o S 1, E [m],
2 min Lr () - (IA (IA"(((WWI))+ WT 2y)-25)+ w w2-1))+11a 1./2). Wi....W-1
s.t. Wiille 1 [1, w L- lll S 1,j E [m]-
(97)
By exchanging the order of min and max, the dual problem follows
D maxtr maxtr(A YY),
s.t. |A ((((XW))).... Wt, 2.-22)): wool 1i)+1)+12 S L/2, Wisll $1,1 [T. 2). | L-1ي lll S 111 E [m]
(98)
max YY, A
s.t. (A"((
W1-2) L/2,
W/ & 1, -2, || 1
C.5 PROOF OF THEOREM
5
The proof is analogous to the proof of Theorem
We can rewrite the dual problem as
DR = max tr Y),
A
|A ((XW1)++.. Wz-2)4W1-11+1lz S L./2, s.t.
(99)
V(W,... I.... Wr.-2 E
where the set θ is defined as
θ {(W 1. W L-2, WL-1 Wille < 1,1 [L-
1 2], ||WL-llla $ 11}.
(100)
By writing 0 = (W
WL-2 WL-1), the bi-dual problem, i.e., the dual problem of (71) is
given by
min H
(101)
s.t. (( W1-2)
Here fe E + R is a signed vector measure, where E is a aaro-flldd of subsets of θ and || is its total variation. The formulation in [OT] has infinite width in each layer. According to Theorem in Appendix(E] the measure in the integral can be represented by finitely many Dirac delta functions. Therefore, there exists m KN such that we can rewrite the problem (101) as
min
Row w
Lg l12,
m
(102)
s.t.
((XX11)) WI-25)+ weol w 1
Y,
1=1
|W lll < 1, [L - 2], || 1اا $ 1,j j E [m+].
Here the variables are Wt for I [-- and j [m*]. W カ-1 and W This is equivalent 29 As the strong duality holds for the problem (99) and (IOT). the primal problem (9) is equivalent to the dual problem (71) long 2 m
24

---

Under review as a conference paper at ICLR 2022
D PROOFS OF AUXILIARY RESULTS
D.1 PROOF OF LEMMA 0
Denote IR" such that ag Au and denote IR" such that by (A)).. We show that is
majorized by b, i.e., for k E [n 1), we have
ENSS
(103)
and Σi=1 04 = =Ei= b, Here (()) is the i-th largest entry in We first note that
Σ
Aa=tr(Al Σ (A).
On the other hand, for & [n- 1]. we have
(()
max VERn 1 e=
max a. 1r (rddiag())Adiag(())
(104)
tr(VAV))
max VER Km VV,VV==
Σ A(AA) = Σ (())
i=1
i=1
Therefore, is majorized by b. As f(x) = =xx is a convex function, according to the Karamata's inequality, we have
Σ f(ai) S Σ f(b.).
This completes the proof.
D.2 PROOF OF LEMMA
According to the min-max principle for singular value, we have
(W))
min max (
1|
As P is projection matrix, for arbitrary x E Rd, we have || & ||Z2]...
Therefore, we have
max ==
|Wall2 S max [Wa||2
=ES,[|=[2==1
This completes the proof.
D.3 PROOF OF LEMMA 3
Suppose that Auu) is optimal solution to
arg max,, |u T A| s.t. g(A; Wi) < 1.
(105)
Denote n. is the number of extreme points of
arg max vE,(WW)
[(A(u))
Denote Vis..., Vn. as extreme points of (T05). We note that (055 is the dual problem for scalar output three-layer neural network. By applying the previous duality theorem, we can write Eee a, where v, E A(W1). We also have Ju X(u)
Σn= la.. Besides, we note that
The
u Σ
aa v
au Wt) ju X())l((u; W1).
This completes the proof.
25

---

Under review as a conference paper at ICLR 2022
E CARATHEODORY'S THEOREM AND FINITE REPRESENTATION
We first review a generalized version of Caratheodory's theorem introduced in Rosset et al. 2007
Theorem 7 Let μ be positive measure supported bounded subset D S RN Then, there
exists a measure y whose support a finite subset of D, {21,...,24 2k), with k v + such that
J. zdp(z)= Σ z,du(zi),
(106)
and || ||r]|a
We generalize this theorem to signed vector measures.
Theorem Let E - IR be a signed vector measure supported on bounded subset D S INN. Here E is a o-field of subsets of D. Then, there exists a measure u whose support a finite subset of D, {z1,..., FA with l S KN + 1 such that
J zdp(z)=
Σ zid((z);,
(107)
and [|z||zv= = ||l||av.
PROOF Let ya be a signed vector measure supported on bounded subset C R. Consider the extended set D {zu²|z E D,u E RK ||u|| = 1}. Then, f corresponds to scalar-valued measure jt on the set D and ||all = l We note that is also bounded. Therefore, by applying Theorem to the set and the measure j., there exists a measure ù whose support is a finite subset of D, { ,..., 2 J. with &o & KN + such that
J Zdz(Z)
Σ zn dī di(zu
(108)
and ||й||TV |Tv. We can define the signed vector measure whose support is finite subset {ei....,zp) } and dz(z)) = u.d(z.)) Then, || = || || = || This completes
the proof.
Now are ready to present the theorem about the finite representation of a signed-vector measure.
Theorem Suppose that 0 the parameter with bounded domain C RPP and 6(X, 0) :
R xd θ + R is an embedding of the parameter into the feature space. Consider the following optimization problem
min [P s.t. / ((xx0)))(())x
=
(109)
Assume that an optimal solution to 109 exists. Then, there exists an optimal solution ja supported on at most K. N features in O.
PROOF Let fa be an optimal solution to 109 We can define a measure P on N as the push- forward of ja by P(B) = ju((0lo(X,0) E B}). Denote D = {ot(X, 0)10 E O). We note that f 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. -2....., 24 with S 2K 1). For each 2; E D, we can find 0 such that &f (xX, 0,) 2,. Then, j Σt_ 5(0 (z))((z,) is an optimal solution to (109) with at most 20(N + 1) features and j TV = |l|TT. Here 8(-) is the Dirac delta measure.
26


Reviews:
[{"review_id": "kZujXZ67Dms", "reviewer": "Reviewer_Pya1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths.\n\n    1. The claims are very interesting.\n    2. The message delivered in the introduction is clear.\n\nWeakness.\n\n    1. The mathematical presentation is confusing and full of typos. For example:\n           1.1. In (1) its W_2, not w_2, this happens many times. \n           1.2. In the first formula of section 2, A_{\\ell-1} is left-multiplied by W_l. It should be right-multiplied. This happens many times.           \n           1.3. In the definition of parallel networks, its A_{0,j}, not A_{0}^{j}.\n           1.4. Problem (7) has a typo.\n\n    2. There seems to be very few technical novelty. Most of the paper is about the standard step of calculating the dual problem, the rescaling technique is also quite standard and well-known (e.g., in SVM), and was used in (Ergen & Pilanci, 2020b) for neural networks. Please clarify any technical novelty compared to prior works.\n\n    3. There are no experiments that validate the theorems, while the claimed theorems lead to at least the following suspection. Specifically, the main result, Theorem 1, has two closed-form expressions for optimal values of P_{lin}(t) and D_{lin}(t) respectively, and in its proof (page 16) the authors claim that D_{lin}(t) is \"strictly\" smaller than P_{lin}(t). However, the two terms are obviously equal if X^{dagger}Y has its all singular values equal to 1. This means something wrong in the proof or in the statement of Theorem 1.\n\n    4. Please provide some discussion on m^* of Proposition 1. It seems important to bound it.\n\n    5. Assume Proposition 2 is correct. Further assume that we have ample and general enough data samples (so that X is a tall matrix of full rank). Then I could conclude that the optimal value of (7) is directly given by the optimal value of Proposition 2 where W is replaced by X^dagger Y. As a result, much of the development of the paper becomes pointless as the optimal value of (7), and thus an optimal solution, is already known. In this situation, why do we care about whether the duality gap is zero or not?\n\nQuestions: Please shed some light on proof techniques for deep linear networks and deep parallel networks as they are tightly related. My feeling is that the results for deep parallel networks are natural consequences of those for deep linear networks. Is that correct?\n", "summary_of_the_paper": "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.", "summary_of_the_review": "The above concerns on mathematical clarity, technical novelty, technical correctness, and practical vadility lead me to form the opnion of reject. However, I am not an expert in this field of \"theory of training neural networks\", so I am looking forward to rebuttals from the authors, as well as comments from other reviewers and the area chair.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "jVFzKXK7pQm", "reviewer": "Reviewer_3piH", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper tackles an interesting and I believe important problem in NN optimization. Although the results are limited to minimum norm training of over-parametrized NN, the theoretical analysis may be useful in future development and analysis of deep NN optimizations. The paper has some shortcomings and some parts of the analysis were not clear, such as\n\n1. As a theoretical paper, I expected to see more precise statements. For example, the paper claims that the duality gap is zero for parallel NN, but it seems that this is true only for NNs with enough number of parallel branches. \n2. Do the authors define parallel NNs such that the output of each branch is a scalar?\n3. Some equations and derivations are not clear or obvious, e.g., proof of proposition 4, why equation (64) is equivalent to (16)? Why the power $L$ is dropped? Is deriving equation (22) similar to the ones in the references ? In the proof of proposition 6, it is not clear how the power $L$ (in equation (28), $\\\\|W_L\\\\|^L$) is dropped and the optimizaiton become over $\\ell_2$ norm of the rows of $W_L$.\n4. In the paragraph after equation (5), the authors claim that \"The rescaling does not change the solution to (4).\". Although by appropriate scaling $W_1$ and $W_2$ can still satisfy the constraint, but as the value of the objective function changes, the statement seems  inaccurate. Can the authors explain?\n5. In section 4.1, Theorem 3, the authors assumed that data is rank 1. Does it simply imply that data samples are simply given by a scaling of a base vector, i.e., $x_i = s_i a$, for scalar $s_i$?\n6. Theorem 5, is there any constraint on the number of branches or $m$?  \n  \nThere are some minor typos in the equations, such as\n- Section 2, first equation, $A_l=\\Phi(W_lA_{l-1})$ should be $A_l=\\Phi(A_{l-1}W_l)$. Similarly, for the second set of equations in that section.\n- Is summation in equation (7) over $\\\\|W_i\\\\|^2$ rather than fixed $\\\\|W_L\\\\|$?\n- First sentence section 4.2, \"there is no duality gap for arbitrary deep ReLU networks\", seems \"parallel with large enough number of branches\" should be added to make the statement accurate.\n", "summary_of_the_paper": "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.", "summary_of_the_review": "The ideas and analysis of the paper to find the duality gap in training deep neural networks and when it achieves zero (at least for over-parametrized deep NNs) can be useful in understanding the optimization and training deep NNs and their properties. The paper adds non-trivial and solid results to the previous works in this domain, esp. works by Ergen and Pilanci. However, the writing and presentation of the paper falls short from the expectations.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "KC3pc6dDOs", "reviewer": "Reviewer_c3BS", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "[Contributions]\n\nThe analysis of the loss landscape of deep neural networks is an important topic to understand the global convergence property of optimization. Recently, the dual formulation of two-layer neural networks has been studied and the strong duality has been shown by the series of [Ergen and Pilanci] works and [Zhang et al. (2019)]. A natural question is to extend these results to deep models and this study answer the question. In particular, the strong duality theorem for the parallel deep ReLU model is quite interesting.\n\n\n[Weaknesses]\n\nI basically like the theoretical results in this paper, but I think the quality should be much improved and the paper is not ready for publication because of typos, ambiguity, and the lack of proof.  For the detail see below.\n\n- I could not find the proof of the first part of Proposition 4 and 6. These are important statements that make the equivalence between (16) and (17), (28) and (29).\n- Notations (Subsection 1.2): The notation $W_l \\in \\mathbb{R}^{m_1\\times m_2}$ is somewhat confusing because $W_l$ represents the parameter of $l$-th layer in the main text.\n- Eq. (1): $W_2$ → $w_2$. Moreover, there are many similar typos with the wrong uppercase and lowercase letters in the paper.\n- Section2:\n    - The formulation of standard networks: $W_l A_{l-1}$ → $A_{l-1}W_l$.\n    - Inconsistent conditions: $m_l \\geq \\max\\\\{d,K\\\\}$, ($l \\in [L-1]$), and $m_{L-1}=1$.\n    - Lack of specification for the type of $A_{L-1}$ and $W_L$.\n- Eq. (7): $\\|W_L\\|_F^2$ → $ \\|  W_i \\|_F^2$ ?\n- Eq. (9): Notation $\\forall$ is in the wong place ($\\forall \\| W_i \\|_F$ → $\\forall i \\in [L-2]$).\n\n\n[Additional references]\n\nIt is interesting that bi-dual problems become learning problems of mean field neural networks with TV-norm regularization and additional constraints (e.g., (41), (79), (97)). Hence, I think the strong duality theorem for parallel models is a reasonable consequence because parallel models are essentially neural networks in the (finite-width) mean field regime. There are many studies on the mean field regime. For instance, \n\n- A. Nitanda and T. Suzuki. Stochastic particle gradient descent for infinite ensembles. arXiv, 2017.\n- S. Mei, A. Montanari, and P. M. Nguyen. A mean field view of the landscape of two-layer neural networks. PNAS, 2018.\n- L. Chizat and F. Bach. On the global convergence of gradient descent for over-parameterized\nmodels using optimal transport. NeurIPS, 2018.\n- S. Mei, T. Misiakiewicz, and A. Montanari. Mean-field theory of two-layers neural networks:\ndimension-free bounds and kernel limit. COLT, 2019.\n- G. M. Rotskoff, S. Jelassi,  J. Bruna, and E. Vanden-Eijnden. Global convergence of neuron\nbirth-death dynamics. ICML, 2019.\n- J. Sirignano and K. Spiliopoulos. Mean field analysis of neural networks: A central limit theorem. Stochastic Processes and their Applications, 2020.\n- S. Akiyama and T. Suzuki. On learnability via gradient method for two-layer relu neural networks in teacher-student setting. ICML, 2021.\n- L. Chizat. Sparse optimization on measures with over-parameterized gradient descent. Mathematical Programming, 2021.\n- A. Nitanda, D. Wu, and T. Suzuki. Particle dual averaging: Optimization of mean field neural\nnetworks with global convergence rate analysis. NeurIPS, 2021.", "summary_of_the_paper": "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. ", "summary_of_the_review": "The statements of main theorems are interesting and important, but the quality of the paper should be much improved. See the main review for detail.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "CzZjHPVImN5", "reviewer": "Reviewer_eU6M", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength:\n1. Analyzing the duality gap in neural network is an important research question both theoretically and empirically. \n2. The paper is well written and very good to follow.\n3. Showing the duality gap is non-zero for three-layer ReLU networks is important. \n\nWeakness:\n1. The author proves that the duality gap is zero when the neural network has parallel architecture, but I find there are little discussion behind this setting, i.e. why the parallel architecture can help closing the duality gap?\n2. Is the parallel architecture setting practical? Has it been used empirically?\n3. There is no numerically experiments supporting the theoretical result. \n4. In general, even when the duality gap is zero and we can solve the dual problem, how can we recover the primal solution? ", "summary_of_the_paper": "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. ", "summary_of_the_review": "I found the manuscript to be clearly written and technically sound. Although it has some weakness points, I think it still worth a publication. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This is an interesting paper which further extends the duality theory of deep networks.  Unfortunately, reviewers had many concerns about, presentation, technical details, and missing prior work.  I will add that a large volume of relevant implicit bias work (e.g., in the setting of deep linear networks, mirroring Proposition 2) is completely uncited (e.g., works by Arora et al., Soudry et al., Ji et al.), despite being earlier than many of the works which are currently cited.  As such, I urge the authors to continue in their valuable line of work, taking into consideration all of these points and also the reviewer comments.

Separately, I note that there is a violation of the blind policy in the current revision: grant information was included.  The PC decide this was a minor violation and should not affect the review process, however their decision could have easily been otherwise.  I urge the authors to be exceptionally careful with such issues in the future.
Decision: Reject