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

Abstract: Training deep neural networks is a challenging non-convex optimization problem. Recent work has proven that the strong duality holds (which means zero duality gap) for regularized finite-width two-layer ReLU networks and consequently provided an equivalent convex training problem. However, extending this result to deeper networks remains to be an open problem. In this paper, we prove that the duality gap for deeper linear networks with vector outputs is non-zero. In contrast, we show that the zero duality gap can be obtained by stacking standard deep networks in parallel, which we call a parallel architecture, and modifying the regularization. Therefore, we prove the strong duality and existence of equivalent convex problems that enable globally optimal training of deep networks. As a by-product of our analysis, we demonstrate that the weight decay regularization on the network parameters explicitly encourages low-rank solutions via closed-form expressions. In addition, we show that strong duality holds for three-layer standard ReLU networks given rank-1 data matrices.

Published as a conference paper at ICLR 2023
PARALLEL DEEP NEURAL NETWORKS HAVE ZERO DUALITY GAP
Yifei Wang, Tolga Ergen & Mert Pilanci Department of Electrical Engineering Stanford University (wangyf18, ergen, lanci (estanford.edu
ABSTRACT
Training deep neural networks is challenging non-convex optimization problem. Recent work has proven that the strong duality holds (which means zero duality gap) for regularized knite-width two-layer ReLU networks and consequently provided an equivalent convex training problem. However, extending this result to deeper networks remains to be an open problem. In this paper, we prove that the duality gap for deeper linear networks with vector outputs is non-zero. In contrast, we show that the zero duality gap can obtained by stacking standard deep networks in parallel, which we call parallel architecture, and modifying the regularization. Therefore, we prove the strong duality and existence of equivalent convex problems that enable globally optimal training of deep networks. As by-product of our analysis, we demonstrate that the weight decay regularization on the network parameters explicitly encourages low-rank solutions via closed-form expressions. In addition, we show that strong duality holds for three-layer standard ReI.U networks given rank- data matrices.
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 is highly non-convex optimization problem, simple first order gradient based algorithms, such as stochastic gradient descent, can find solution with good generalization properties. However, due the non-convex and non-linear nature of the training problem, underlying theoretical reasons for this remains an open problem.
The Lagrangian dual problem (Boyd et al. 2004) plays important role in the theory of convex and non-convex optimization. For convex optimization problems, the convex duality an important tool to determine their optimal values and to characterize the optimal solutions. Even for non-convex primal problem, the dual problem is a convex optimization problem the can be solved efficiently. As result of weak duality, the optimal value of the dual problem serves 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 al. 2004).
The convex duality also has important applications in machine learning. In Paternain et al. (2019). the design problem of an alllpasoopassing reward can be formulated as 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 be tackled using duality (Farnia & Tse. 2018).
In lines of recent works, the convex duality can also applied for analyzing the optimal layer
weights of two-layer neural networks with linear or ReLU activations (Ergen & Pilanci| 2019 Pilanci
Ergen 2020 Ergen & Pilanci 2020a by Lacotte Pilanci 2020 Sahiner et al.) 2020). Based
on the convex duality framework, the training problem of two-layer neural networks with ReLU
activation can be represented in terms of single convex program in Pilanci & Ergen 2022). Such
convex optimization formulations extended to two-layer and three-layer convolutional neural

---

Published as a conference paper at ICLR 2023
network training problems in Ergen & Pilanci (2021b). Strong duality also holds for deep linear neural networks with scalar output (Ergen & Pilanci 2021a). The convex 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 the global optimum of the training loss.
Admittedly, a zero duality gap is hard to achieve for deep neural networks, especially for those with vector outputs. This imposes more difficulty to understand deep neural networks from the convex optimization lens. Fortunately, neural networks with parallel structures (also known as bulti-branch architecture) appear to be easier to train. Practically, the usage of parallel neural networks dates back AlexNet (Krizhevsky et al. 2012). Modern neural network architecture including Inception (Szegedy et al. (017). Xception (Chollet 2017) and SqueezeNet (landola et al., 2016) utilize the parallel structure. As the "parallel" version of ResNet (He et al.) 2016a b), ResNeXt (Xie al.. 2017) and Wide ResNet (Zagoruyko & Komodakis 6016) exhibit improved performance on many applications. Recently, it was shown that neural networks with parallel architectures have smaller duality gaps Zhang al., 2019) compared to standard neural networks. Furthermore, |Ergen & Pilanci 202 proved that there is no duality gap for parallel architectures with three-layers.
On the other hand, it is known that overparameterized parallel neural networks have benign train- ing landscapes (Haeffele & Vidal 2017 Ergen & Pilanci 2019). The parallel models with the over-parameetrrizatoo are essentially neural networks in the mean-field regime (Nitanda & Suzuki
6017,Mct et al. 2018 Chizat & Bach, 2018 Mei et al. 2019 Rotskoff et al. 2019 Sirignano &
Spiliopoulos] 2020 Akiyama Suzuki 202 Chizat 2021 Nitanda et al. 2020h. The deep linear model is also of great interests in the machine learning community. For training by loss with deep
linear networks using Schatten norm regularization, /Zhagg et al. (2019) show that there is no duality gap. The implicit regularization in training deep linear networks has been studied in Di & Telgarsky
(2018): Arora et al. 2019);; Moroshko al. (2020). 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.
1.1 CONTRIBUTIONS
Following the convex duality framework introduced in Ergen Pilanci (202 2020a). 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 follows.
For training standard vector-output deep linear networks using & regularization, we precisely calculate the optimal value of the primal and dual problems and show that the duality gap is non-zero, i.c., 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 exact.
For parallel deep ReLU networks of arbitrary depth, with certain convex regularization and sufficient number of branches, we prove strong duality, i.e., show that 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.2 NOTATIONS
We use bold capital letters to represent matrices and bold lowercase letters to represent vectors. Denote [n] (1, (1...., n.) For a matrix W, R xm; for i E [m--1] and j [ma)) denote w as its
2

---

Published as a conference paper at ICLR 2023
linear activation
ReLU activation
==
L=
I 3
1=
L=
3
T>
3
standard networks
previous work
1(0)
X
7()
X
X
this paper
1(0) V( 0)
V(
0)
((0)
X
X
parallel networks
previous work
7(0)
(0))
700)
(0)
(0)
X
this paper
7(0)
(0)
(0)
(0)
Table 1: Existing and current results for duality gaps in L-layer standard and parallel architectures. we compare our duality gap characterization with previous literature. Each check mark indicates whether a characterization of the duality gap exists for the corresponding architecture and the number next to it indicates whether the gap is zero or not.
i-th column and wi.)" its j-th row. Throughout the paper, X RNxd is the data matrix consisting of d dimensional samples and Y N the label matrix for regression/classffcatiin task with K outputs. We use the letter P (D) for the optimal value of the primal (dual) problem.
1.3 MOTIVATIONS AND BACKGROUND
Recently a series of papers PPllanci & Ergen 2020 Ergen & Pilanci 202 2020a) 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 clasifiiation/regrsssin tasks. Given data matrix X R. xd consisting of d dimensional N samples and the corresponding label matrix y E TR,, the weight-decay regularized training problem for scalar-output neural network with m hidden neurons can written as follows
B 2
p:= min W. 2 Fl y11
(1[
+ || 1
(1)
where W1 E _dxm and w2 E R are the layer weights, B 0 is regularization parameter, and the activation function, which can be linear (02) = or ReLU 6(2) max(2. 0). Then, one can
take the dual of (I) with respect to W1 and Wa obtain the following dual optimization problem
3 IA - 1-2 2 1
= max X
2
| Oh ((Xw)) $
will wx S1
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 Pilanci Ergen 2020); Ergen & Pilanci| (2021a 2020a), strong duality in fact holds, i.c., P = D, for two-layer networks and therefore representations for the non-convex training problem in (T.. However, extensions of this approach to deeper and state-of-the-an architectures the central question we address in this paper is:
derive exact convex
not available in the literature. Based this observation,
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 an architecture for which strong duality holds regardless of the depth?
Consequently, throughout the paper, we provide full characterization of convex duality for deeper neural networks. We observe that the dual the convex dual problem of the nonconvex minimum norm problem of deep networks correspond to minimum problem of deep networks with parallel branches. Based on this characterization, we propose a modified architecture for which strong duality holds regardless of depth.
3

---

Published as a conference paper at ICLR 2023
1.4 ORGANIZATION
This paper is organized as follows. In Section [ 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 networks with parallel structures have no duality gap.
We also show that deep ReLU
STANDARD NEURAL NETWORKS VS PARALLEL ARCHITECTURES
We briefly review the convex duality theory for two-layer neural networks in Appendix [A] To extend the theory to deep neural networks, we fist consider the L-layer neural network with the standard architecture:
fx(X) = AL-1 WL, A = 6(Ar- e [L - -
(3)
where is the activation function, W. I is the weight matrix in the 1-th layer and 0 (W1...., WL) represents the parameter the neural network.
We then introduce the neural network with parallel architectures:
(x) A WL, Ar, (Ai-1. Wi,), E [L. Ao, = [m]. Here for [L. Specifically, we let m---1 = to make each parallel branch as scalar-output neural network. In short, we can view the output A from a parallel neural network as a concatenation of m scalar-output standard neural work. In Figures 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 the parallel neural network. We next present summary of our main result.
(4)
1). [L-1]. the 1-th layer has m weight matrices Wt., RRm xxm; where j E [m]]
Theorem (main result) For L 2 3, there exists an activation function & and L-layer standard neural network defined in (3) such that the strong duality does not hold, i.e., P D. In contrast, for any L-layer parallel neural network defined in (4) with linear or ReLU activations and sufficiently large number of branches, strong duality holds, i.e., P D.
We elaborate on the primal problem with optimal value P and the dual problem with optimal value D in Section Bland
3 DEEP LINEAR NETWORKS
Input
Layor
Layer 2 Layer 3 Layer
3.1 STANDARD DEEP LINEAR NETWORKS
We first consider the neural network with standard ar- chitecture, i.c., (x( = XW,... Wz. Consider the following minimum norm optimization problem:
Figure Standard Architecture Input
Layer
Layer 2 Layer Layer
1
Pim min (WiH
Will
(5)
s.t. XW
Wr Y,
where the variables are W W1.... W...., W.. As shown in the
Proposition 3.1 in (Ergen & Pilanci 2021a), by introduc- ing a scale parameter the problem (5) can be reformulated as
L- + Pin (1),
Pin min
2>
2
where the subproblem Pin (t) is defined as
Figure 2: Parallel Architecture
K
(tn
min (Wi)
row Lgg
I|,,
s.. XW .... Wz Y, Y, swlees
/ool |w2 S 1.j E [mz-1].
4

---

Published as a conference paper at ICLR 2023
To be specific, these two formulations have the same optimal value and the optimal solutions of one problem can be rescaled into the optimal solution of another solution. Based on the rescaling of parameters in Pin (t) characterize the dual problem of (t) and its bi-dual, i... dual of the dual problem.
Proposition 1 The dual problem of Pin(t) is convex optimization problem given by
Diin maxtr((A")
| A XW1. WL- 5
S.I. IIW:
max
S...iEL 21.l:--------1 11
There exists a threshold of the number of branches m & KN + such that Dia(t) = BDnn(t). where Binm (t) is the optimal value of the bi-dual problem
(t)
min
WwEg 11
(Wiyhe(M))EN
(6)
S.1.
XW 1.... ... W WL-2.w col
L-1, WLJ = Y.
TOw
j=1
W S4iE 2), E [mm), | | s 1, E [m*].
Detailed derivation of the dual and the bi-dual problems are provided in Appendix C.1 As A 0 is a strict feasible point for the dual problem, the optimal dual solutions exist due to classical results in strong duality for convex problems. The reason why we do not directly take the dual of Pin is that the objective function in Pin involves the weights of first L 1 layer, which prevents obtaining non- non-trivis trivial dual problem. An interesting observation that the bi-dual problem is related the minimum norm problem of a parallel neural network with balanced weights. Namely, the Frobenius norm of the weight matrices (Wi,) L-2 in each branch j E [m)] has the same upper bound t. |=m
To calculate the value Pin (t) for fixed IR, we introduce the definition of Schatten-p norm. Definition For matrix A gmxx and p 0, the Schatten-p quasi-norm of A is defined
1/P
min (m.n)
|||| s.
Σ
o((A))
where (A) is the i-th largest singular value of A.
The following proposition provides a closed-form solution for the sub-problem Pin(t) and determines its optimal value.
Proposition 2 Suppose that W RdxK with rank is given. Assume that 2 r for 1. =
1....,L L Consider the following optimization prohlem:
ST (1W ... | ((ll), S.S. W.W.... Wt = W.
min (W.HL
(7)
Then, the optimal value of the problem 7 is given by W optimal value is achieved when
2/L S2yz" Suppose that W UEVT The
W, U, m 'U, i=
(8)
Here U, = U. U. V and = 1,..., I -
U, Rmixr satisfies that U,U,=0
To the best of our knowledge, this result was not known previously. Proposition 2 implies that Pin can be equivalently written as
2/L S2y1
s.t. XW=
2
Denote X as the pseudo inverse of X. Although the objective is non-convex for L 2 3, this problem has dlsed-form solution show next.
5

---

Published as a conference paper at ICLR 2023
Theorem Suppose that X UEVT is the singular value decomposition and let rank Y). Assume that my 2 r for = 1,...,L L- The optimal solution to Pin is given in closed-form follows:
W. U 1
where Up U. = For L,..,, L-
U₁ E R xr satisfies U² I,-
Based on Theorem
2 the optimal value of (lin(1) and Diin can be precisely calculated as follows.
Theorem 3 Assume that my 2 rank(X (X| (onk(iiY).nne for 1...., L- 1. For fixed >> 0, the optimal value of Pin (t) and Diaa(t) (t) are given by
(1) = (1-2) | Y|l
(10)
and
Dri (1
(11)
Here II represents the nuclear norm. Pin (t) = Dun (t) if and only if the singular values of X are equal.
As result, if the singular values of X are not equal to the same value, the duality gap exists, i.c., P > D. for standard deep linear networks with L > We note that the optimal scale parameter for the primal problem Pin is given by 1" W
Sayz" This proves the first part of Theorem
We conclude that, the deep linear network training problem has duality gap whenever the depth three or more. In contrast, there exists no duality gap for depth two. Nevertheless, the optimal solution can be obtained in closed form have shown. In the following section, we introduce parallel bratc- architecture that always has zero duality gap regardless of the depth.
3.2 PARALLEL DEEP LINEAR NEURAL NETWORKS
Now consider the parallel multi- network structure as defined in Section and consider the corresponding minimum norm optimization problem:
ΣΣ
min (Wi.heel)).etn
(12)
S.t. Σ XWI.
WL-2,
L-1
col
rOW L.j
Y.
j=1
Due to rescaling to achieve the lower bound of the inequality of arithmetic and geometric means, we can formulate the problem (12) in the following way. other words, two formulations (12) and L have the same optimal value and the optimal solutions of one problem can be mapped to the optimal solutions of another problem.
Proposition 3 The problem
12)
can be formulated as
L
TOw 2/L
min (Wi, (cck).ccm)
2
2
(13)
S.l. Σ XW13 15 ... W W WL3 rOW Y,,
|Wollle < e [L 2) E [m], wi < 1,j E [m].
We note that 2/2 is a non-convex function of z and we cannot hope obtain a non-trivial dual. To solve this issue, we consider the || 1 regularized objective given by
L-1 1
m
ppel li
min heishee
w 1
row Eaj
2
(14)
Σ XW I...... W W. Y.

---

Published as a conference paper at ICLR 2023
Utilizing the arithmetic and geometric mean (AM-GM) inequality, rescale the parameters and formulate (14). To be specific, the two formulations (14) and (15) have the same optimal value and the optimal solutions of one problem can be rescaled to the optimal solutions of another problem and vice versa.
Proposition 4 The problem (4) can be formulated as
ppr
min [W
Σ
row
Li 1l,
2
==1
(15)
S.T.
XW15 1.j
W 2- 2L-2,
w L- WT. = Y.
j=1
Wislle $1, L 2). E [m]. 12 11,. 1,j E [m]]
The dual problem of phnll is convex problem
Dim
max tr(A" Y),
A
(16)
| ... W2-2WL-1123 L/2
S.L. I. S1 2- w
max
In contrary to the standard linear network model, the strong duality holds for the parallel linear network training problem (14.
Theorem There exists critical width m² S KN + such that long the number of branches m m", the strong duality holds for the problem Namely, ppr) -prl The optimal values are both ||
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.
NEURAL NETWORKS WITH RELU ACTIVATION
4.1 STANDARD THREE-LAYER RELU NETWORKS
We first focus the three-layer ReLU network with standard architecture. Specifically, we set <(=) = max 0}. Consider the minimum norm problem
PRELU min
Σ w.ll s.t. ((WW1) W2) W; = Y. (W.H
(17)
Here denote (z)4 max 2, 0}. Similarly, by introducing scale parameter f, this problem can be formulated as PROLU min o 1t2 + (R)LU(t), where (R) is defined as
(R)LLC() min (W.)...
Σ
w
row 1|
(18)
s.t. W/llee &
wo ll2 S 1,j E ((XW)) W W Y
The proof is analagous to the proof of Proposition 3.1 in (Ergen & Pilanci 2021a). To be specific, these formulations have the same optimal value and their optimal solutions be mutually transformed into each other. For W, E IRdx we define the set
A(Wi) =
w2) w2ll2 < 1}.
(19)
We derive the convex dual problem of (RELU(t) in the following proposition. Proposition 5 The dual problem of PRELU(t) (t) defined in (18) is a convex problem defined as
DRcLu = max tr(A ATTY TY), S.1.
max ||A [.vv|22 S 1.
max W::WWill-SwwweAA
(20)
A

---

Published as a conference paper at ICLR 2023
There exists threshold of the number of branches m KN + such that DReLU(t) = B (DReLu(t) where BDRLLU (t) the optimal value of the bi-dual problem
(DReLU(t)-
min W.ER" XX
W33 112.
W 15-1 W Xm
==1
S.L.
(XW1.)
W3 TOW
Y, | St, || S 1, E [m=).
(21)
We note that the bi-dual problem defined in (21) indeed optimizes with a parallel neural network satisfying WWilll F S I, [| 2 S 1, E [m=]. For the case where the data matrix is with rank 1 and the neural network with scalar output, we show that there is no duality gap. We extend the result in (Ergnn & Pilanci 2021d) from two-layer ReLU networks to three-layet ReLU networks.
Theorem For a three-layer scalar-outpul ReLU network, let X = cag be rank-one data matrix. Then, strong duality holds, ie., PReLU (1) DReLU(I). Suppose that X is the optimal solution to the dual problem DReLU (t), then the optimal weights for each layer can be formulated as
W =Isign(
(c)+1- (-)) W2 Pt.
Here Pa = 20/ ||00||2 and P1 E R satisfies || =
For general standard three-layer neural networks, although have (D (R) it may not hold that (t) DRELU (f) as the bi-dual problem corresponds to optimizing a parallel neural network instead of a standard neural network fit the labels.
To theoretically justify that the duality gap can be zero, we consider parallel multi-branch architec- ture for ReLU networks in the next section.
4.2 PARALLEL DEEP RELU NETWORKS
For the corresponding parallel architecture, we show that there is no duality gap for arbitrary depth ReLU networks, as long as the number branches large enough. Consider the following minimum norm problem:
L- ΣΣ 2
pprl ReLU min
W l 1 s.t. (XW11))+ W
L-15
TOW
Y. LJ
(22)
As the ReLU activation is homogeneous, we can rescale the parameter to reformulate 22 and derive the dual problem. We note that two formulations 22 and (23 have the optimal value and the optimal solutions of one problem can be rescaled to the optimal solutions of another problem and vice versa.
Proposition 6 The problem (22) can be reformulated as
min
WwE. I|2,
1
s.t.
Σ (XW
1.) wT- TOW
= WWolle $1,1e [L 2], Ww S 1, [m].
(23)
The dual problem of (3) is convex problem defined as
ReLU = max (A YY),
| v/l222 I/2. (24)
V=(W W W 1-1 21
For deep parallel ReLU networks, we show that with sufficient number of parallel branches, the strong duality holds, i.e., P P= D.
8

---

Published as a conference paper at ICLR 2023
Theorem 6 Let m² be the threshold of the number of branches. which is upper bounded by KN 1. Then, as long as the number of branches m 2 m", the strong duality holds for (23) in the sense that R = P ReLU-
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 ReI.U network is equivalent to solve a convex program. This proves the second part of Theorem !
Based on the strong duality results, assuming that we can obtain optimal solution to the convex dual problem (24). then we can construct an optimal solution to the primal problem 23
as follows.
Theorem Let A be the optimal solution to Denote the set of maximizers
arg maxx
|[ [I(A*) v122
(25)
v=((X + WL WL-244 w2- D Wille SIEEEL w
as {V1,.... Mm }. where v, ((XW ... WL-2:)+ + with Wt,lle S1, [L -
and |L-1, l2 I 1 and m S KN + 1 is the critical threshold of the number of branches. Let wtow
LL1..... w row be an optimal solution to the corvex problem
L Σ
pprl.ub
ReLU
min
Lig 112, s.t. Σ (xW =Y
(26)
Then, (W W...,, WL) is an optimal solution to
We note that finding the set of maximizers in 25 dimensionality of the constraint set.
be challenging in practice due the high-
5 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. 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 zero. A limitation of our work is that primarily focus minimum norm interpolation problems. We believe that results can be easily generalized to a regularized training problems with general loss function, including squared loss, logistic loss, hinge loss, etc..
Another interesting research direction is investigating the complexity of solving our convex dual prob- lems. Although the number of variables be high for deep networks, the convex duality framework offers a rigorous theoretical perspective to the structure of optimal solutions. These problems can also shed light into the optimization landscape of their equivalent non-convex formulations. We note that it is not yet clear whether convex formulations of deep networks present practical gains in training. However, in Mishkin et al. (2022): Pilanci & Ergen 2020) it was shown that convex formulations provide sigmificant computational speed-ups in training two-layer neural networks. Furthermore, similar convex analysis was also applied various architectures including batch normalization (Ergen) et al. 2022b), vector output networks (Sahiner et al., 2021). threshold and polynomial activation networks (Ergen al.) 20233 Bartan & Pilanci, 2021)) GANs (Sahiner et al.] (002aa), autoregressive
models (Gupta al. 202 and Transformers (Ergen et al. 2022a Sahiner al. (022b).
ACKNOWLEDGEMENTS
This work was partially supported by the National Science Foundation (NSF) under grants ECCS- 2037304, DM3-2134248. NSF CAREER award CCF-2236829, the U.S. Army Research Office Early Career Award W91 sponsored by InnoHK funding, Hong Kong SAR.
and the ACCESS Al Chip Center for Emerging Smart Systems,
9

---

Published as a conference paper at ICLR 2023
REFERENCES
Shunta Akiyama and Taiji Suzuki. On learnability via gradient method for two-layer relu neural networks teacher-student setting. arXiv preprint arXiv:2106.062555 2021.
Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix factorization. arXiv preprint arXiv:9955.1355. 2019.
Burak Bartan and Mert Pilanci. Neural spectrahedra and semidefinite lifts: Global convex op- timization of polynomial activation neural networks in fully polynomial-tiee. arXiv preprint arXiv:2101.02229, 2021.
Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe. Convex optimization. university press, 2004.
Cambridge
Lenaic Chizat. Sparse optimization measures with werrppaaametrrized gradient descent. Mathe- matical Programming, pp. 1-46, 2021.
Lenaic Chizat and Francis Bach. On the global convergence of gradient descent for over-parameterized models using optimal transport. arXiv preprint 0rXiv:/805.000 09555, 2018.
François Chollet. Xception: Deep learning with depthwise separable convolutions. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 1251 2017.
T. Ergen and M. Pilanci. Convex optimization for shallow neural networks. In 2019 57th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 79-83, 2019.
Tolga Ergen and Mert Pilanci. Convex duality and cutting plane methods for over-parameterized neural networks. OPT-ML workshop, 2019.
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. 4024-4033. PMLR, 2020a.
Tolga Ergen and Mert Pilanci. Convex programs for global optimization of convolutional neural networks polynomial-time In OPT-ML workshop, 2020b.
Tolga Ergen and Mert Pilanci. Revealing the structure of deep neural networks via convex duality. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 3004-3014. PMLR, 18-24 Jul 2021a. URL
Tolga Ergen and Mert Pilanci. Implicit convex regularizers of emn architectures: Convex optimization of two- and three-layer networks in polynomial time. In International Conference on Learning Representations, 2021b. URL
net htt//forummm/ ON8 JUH 4MH6)
Tolga Ergen and Mert Pilanci. Global optimality beyond two layers: Training deep relu networks via convex programs. In International Conference Machine Learning, pp. 2993-3003 PMLR, 2021c.
Tolga Ergen and Mert Pilanci. Convex geometry and duality of over-parameterriedd neural networks. Journal of machine learning research, 2021d.
Tolga Ergen and Mert Pilanci. Path regularization: A convexity and sparsity inducing regularization for parallel relu networks. arXiv preprint arXiv: wxxiv22110009445 2021e.
Tolga Ergen, Behnam Neyshabur, and Harsh Mehta. Convexifying transformers: Improving Improvvng optimiza- tion and understanding of transformer networks, 2022a. URL
221 11052
Tolga Ergen, Arda Sahiner, Batu Ozturkler, John M. Pauly, Morteza Mardani, and Mert Pilanci. Demystifying batch normalization in reLU networks: Equivalent convex optimization models and implicit regularization. In International Conference on Learning Representations, 2022b. URL httpps://ppenret net ott.eeeeeeeoooooioaaaoeeeaeeeee 6xxpptttti0dd0
10

---

Published as a conference paper at ICLR 2023
Tolga Ergen, Halil Ibrahim Gulluk, Jonathan Lacotte, and Mert Pilanci. Globally optimal training of neural networks with threshold activation functions. In The Eleventh International Confer- ence Learning Representations, 2023. URL
net forum?id
9k5kTgyHT
Farzan Farnia and David Tse. A convex duality framework for gans. In S. Ben- gio, Н. Wallach, H. Larochelle, K. Grauman, Cesa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran Asso- ciates, Inc., 2018. URL ftttps://pple htttps://prrceeedingss www.ipe cttpp//ss.c//ppppe///////////// (311aaa0600033222144444444333889
pdf
Vikul Gupta, Burak Bartan, Tolga Ergen, and Mert Pilanci. Convex neural autoregressive models: Towards tractable, expressive, and theoretically-bacee backed models for sequential forecasting and generation. In ICASSP 2021 2021 IEEE International Conference on Acousties, Speech and Signal Processing (ICASSP), pp. 3890-3894, 2021. doi: 10. 0011099CCSSS3997322221199999
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 recognition. In Proceedings of the IEEE conference on 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 on computer vision, pp. 630-645. Springer. 2016b.
Forrest N landola. Song Han, Matthew W Moskewicz, Khalid Ashraf, William J Dally, and Kurt Keutzer. Squeezenet: Alexnet-level accuracy with 50x fewer parameters and< 0.5 mb model size. arXiv preprint arXi: /602.07620..00.. 2016.
Ziwei Ji and Matus Telgarsky. Gradient descent aligns the layers of deep linear networks. arXiv preprint arXiv: wrXiv:1810.02032. 2018.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep con- volutional neural networks. Advances in neural information processing systems, 25:1097-1105, 2012.
Jonathan Lacotte and Mert Pilanci. All local minima are global for two-layer relu neural networks: 2020.
The hidden convex optimization landscape. arXiv e-prints, pp.
Song Mei, Andrea Montanari, and Phan-Minh Nguyen. A mean field view of the landscape of two- layer neural networks. Proceedings of the National Academy of Sciences, 115(33):E7665- E7671, 2018
Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Mean-field theory of two-layers neural networks: dimension-fiee bounds and kernel limit. In Conference Learning Theory, pp. 2388-2464. PMLR, 2019.
Aaron Mishkin, Arda Sahiner, and Mert Pilanci. Fast convex optimization for two-layer relu networks: Equivalent model classes and cone decompositions. arXiv preprint arXiv:2202.01333,, 2022.
Edward Moroshko, Suriya Gunasekar, Blake Woodworth, Jason D Lee, Nathan Srebro, and Daniel Soudry. Implicit bias in deep linear classification: Initialization scale vs training accuracy. arXiv preprint 20Xi::2007.06738, 2020.
Atsushi Nitanda and Taiji Suzuki. Stochastic particle gradient descent for infinite ensembles. arXiv preprint arXivv 2017.
Atsushi Nitanda, Denny Wu. and Taiji Suzuki. Particle dual averaging: Optimization of mean field neural networks with global convergence rate analysis. arXiv preprint arXiv:20/2. /54777, 2020.
Santiago Paternain, Luiz FO Chamon, Miguel Calvo-Fullana, and Alejandro Ribeiro. Constrained reinforcement learning has zero duality gap. arXiv preprint 1900:19//01/39// 2019.
11

---

Published as a conference paper at ICLR 2023
Mert Pilanci and Tolga Ergen. Neural networks are regularizers: Exact polynomial -ime convex optimization formulations for two-layer networks. International Conference on Machine Learning, 2020.
Saharon Rosset, Grzegorz Swirszez, Nathan Srebro, and Ji Zhu. LI regularization in infinite dimensional feature spaces. In International Conference on Computational Learning Theory, pp. 544-552 Springer, 2007.
Grant Rotskoff, Samy Jelassi, Joan Bruna, and Eric Vanden Mijndnn. Global convergence of neuron birth-death dynamics, arXiv preprint 19Xiv:902200143. 2019.
Arda Sahiner, Morteza Mardani, Batu Ozturkler, Mert Pilanci, and John Pauly. Convex regularization behind neural reconstruction. arXiv preprint 1rXiv:2002..55169, 2020.
Arda Sahiner, Tolga Ergen, John M. Pauly, and Mert Pilanci. Vector-output relu neural network
problems are copositive programs: Convex analysis of two layer networks and polynomial algorithms, In International Conference on Learning Representations, 2021. URL https
//openreview.o
Arda Sahiner, Tolga Ergen, Batu Ozturkler, Burak Bartan, John M. Pauly, Morteza Mardani, and Mert Pilanci. Hidden convexity of wasserstein GANs: Interpretable generative models with closed-form solutions. In International Conference on Learning Representations, 2022a. URL
lhttps://epenreviit wttp:/ewwwww..eeeeeeeeeeeeeeee htte:/fooummll=eelleeee
Arda Sahiner, Tolga Ergen, Batu Ozturkler, John Pauly, Morteza Mardani, and Mert Pilanci. Un- raveling attention via convex duality: Analysis and interpretations of vision transformers. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference on Machine Learning. volume 162 of Proceedings of Machine Learning Research, pp. 19050 190888-9088. PMLR, 17-23 Jul 2022b. URL htttps://proceedingg www.mmr...rrpp.mmmmmmmmmmmmm. v www.v/v22sssiiiia http:/aaaieeeaaaaa.a htm.
Justin Sirignano and Konstantinos Spiliopoulos. Mean field analysis of neural networks: A central limit theorem. Stochastic Processes and their Applications, (000))3880-185222 2020.
Christian Szegedy, Sergey loffe, 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: / 181005336, 2018
Saining Xie, Ross Girshick, Piotr Dollár, Zhuowen Tu, and Kaiming He. Aggregated residual transformations for deep neural networks. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 1492-1500, 2017.
Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. arXiv preprint arXiv:1605.07146 2016.
Hongyang Zhang, Junru Shao, and Ruslan Salakhutdinov. Deep neural networks with bratc- architectures are intrinsically less non-convex. In The 22nd International Conference Artificial Intelligence and Statistics, pp. 1099-1109, PMLR, 2019.
12

---

Published as a conference paper at ICLR 2023
A CONVEX DUALITY FOR TWO-LAYER NEURAL NETWORKS
We briefly review the convex duality theory for two-layer neural networks introduced in Ergen & Pilanci a 2020a). Consider the following weight-decay regularized training problem for vector-output neural network architecture with m hidden neurons
8 (I + (2 min ] [lo((W,) YI + 2 W..Wa
(27)
where W1 Rdxm and W2 m are the variables, and 3 0 is regularization parameter. Here ø is the activation function, which can be linear ((2) = or ReLU ((2) = max 0). As long the network is sufficiently overparameterized, there exists feasible point for such that ((XW,))) = Y. Then, a minimum norm variant of the training problem in (27) is given by
1 (I + 1/22) s.t. ( =Y.
min W. 2
(28)
As shown in Pilanci & Ergen 2020 after a suitable rescaling, this problem can be reformulated as
m
min W.
w row lla, s.t.
o(WW,)W2 Y. |[ I 1,j [m]]
(29)
where [m]] {1, (1....,m, m.. Here w2, represents the j-th of W₂ and w denotes the j-th column of W,. The rescaling does not change the solution to (28). By taking the dual with respect
W and W2, 2, the dual problem of (29) with respect variables is convex optimization problem given by
max A Y), S.t. max
||A (Xu))l2 1,
(30)
mljullaS1
where A RNNK is the dual variable. Provided that m=" where m is critical threshold of width upper bounded by m < N + 1, the strong duality holds, i.c., the optimal value of the primal problem 29 equals the optimal value of the dual problem 30
B DEEP LINEAR NETWORKS WITH GENERAL LOSS FUNCTIONS
We consider deep linear networks with general loss functions, i.e.,
8 L min (XW, WL Y) (W
W
2
where ((Z, Y) is general loss function and B 0 is regularization parameter. According to the above problem is equivalent to
Proposition 2
BL 2
min (XW, Y)
W 2
2/2 SayL
(31)
The & regularization term becomes the Schatten-2/ 2/ L quasi-norm on W to the power 2/L. L. Suppose that there exists W such that (XW,,) Y)= 0. With 3 + 0, asymptotically, the optimal solution to the problem 31 converges to the optimal solution of
min W|
2/L Sayz ((WW, Y) 0.
(32)
In other words, the regularization explicitly regularizes the training problem find a low-rank solution W.
This corresponds weak regularization, i.c., in 277 as considered in Wei al. 2018
13

---

Published as a conference paper at ICLR 2023
C PROOFS OF MAIN RESULTS FOR LINEAR NETWORKS
C.I PROOF OF PROPOSITION II
Consider the Lagrangian function
K
L(W1. WL, Σ
W -Y-XY, Wt)).
(33)
Here E NxK is the dual variable. We note that
P(t)= = min max L(W1...... WL. A),
WI....W.
s.t. | St,ie [L 2], // S 1.J E [me-1].
mL-1
min max maxir(A (rxx W Wi....W.. WL-1 A
Σ (IA"X V1olew
(34)
1=1
Wells S 1, [T. 2], 1 1, E [mL-1).
max maxxtr(A (I^ (IA"'XW W1-22s--11251)
min
WI... WL 2.W2
W || SLiE [L 2), 1/ 1.
Here I((A) is O if the statement is true. Otherwise it is +oc For fixed WT,... W the constraint Wr is linear
exchange the order of max and minw, in the second line of
34).
By exchanging the order of min and max, obtain the dual problem
D(t) = max min A W WL Vi....W..
tr(A (IA i... W1 11),
s.t. |F Sl,E [L 2), 1/w s 1,
= max (rA"
(35)
A
s.t. AAWW, I... WL-2WL-1112 1
A W. St,i [L 2], WLLll 1.
Now we derive the bi-dual problem. The dual problem can be reformulated
max tr YY)
s.l. XW, ... W1-2W2-1122
(36)
W2-1) A (W
Here the set θ is defined
+ {(W
W L- 2, WL- 1/ ||F s stii ||w--
1 1).
(37)
By writing 0 = I......, Wt WL-1), the dual the problem 36 is given by
min ||lIITV s.t. Sace XW, ()=
(38)
Here fa: - R a signed vector measure and Σ is o-field of subsets of O The norm | the total variation of μ., which can be caleulated by
pp 1plzy= = sup { (()))))()))) = E/ u:(0)dpu((0) )
K
(39)
14

---

Published as a conference paper at ICLR 2023
A1
where we write μ
:
The formulation (38) has infinite width in each layer. According to
PK
Theorem 10 in Appendix G the measure in the integral can be represented by finitely many Dirac delta functions. Therefore, we can rewrite the problem (38) as
1|,,
(40)
Σ XW1, 1. ... W WL-2, whJ Y
[ Willle Stiee [L 2], |I S L,j E [m").
Here the variables are Wij for i E [L - 2] and e [mm*). W and W L. As the strong duality
holds for the problem 40 and 36). reformulate the problem of Dum (t) the bi-dual problem (40)
C.2 PROOF OF PROPOSITION 2
We restate Proposition 2 with details.
Proposition 7 Suppose that W E IRdx with rank is given. Consider the following optimization problem:
1 (1Wil + [W S.L. W W2 WL = W
min 2
(41)
in variables W; E m Here ma = d, m. K and m, 2 r for 1,... Then, the optimal value of the problem given by
2/L Say1.
(42)
Suppose that W- UEV! The optimal value can be achieved when
W, = U, U. i= Here U, Trxm, satisfies that U.U II
N. U,U, U,U,
(43)
We start with two lemmas.
Lemma Suppose that A E gaxn is positive semi-definite matrix. Then, for any < < 1, we have
i=1 X(AYP.
ΣA
(44)
Here As is the i-th largest eigenvalue of A.
Lemma Suppose that P E Rdxd is a projection matrix, i.e., p2 P. Then, for arbitrary
W E daxk have
(PW) S (W),
where or (W) represents the i-th largest singular value of W.
Now, we present the proof for Proposition 2 For I. = 1, the statement apparently holds. Suppose that for L = this statement holds. For + 1, by writing A = W.... W1+1, we have
min
W1
+ 12
W.W.... W W
2/1 s.t. W,A = W, min W 12 + ||A|/
(45)
=in t2 + |||
2/11
2/t
s.t. W,A W. | <t.
Suppose that is fixed. is sufficient to consider the following problem:
min A
2/1 2/12
s.t. W,A W. |. tt.
(46)
15

---

Published as a conference paper at ICLR 2023
Suppose that there exists W1 and A such that W W. As WA = WAAA according to Lemma
WIA. Then, have WATA WiAAAA
WA f Wille S t. Therefore, (WA AA)
is also feasible for the problem (46). Hence, the problem 46 equivalent to
min
A
2/1 2/11
s.t. WA W, |A st.
(47)
Assume that W is with rank r. Suppose that A UEVT, where RroXro, Here To 2 r. Then, we have A VΣ VE"'U", We note that
[WA 1/
= -tr(WVE (V(WVE-VWWW)
(48)
Denote G(V) V"WT This implies that
Oi(A) (G(V)), (G()) St.
1=1
Therefore, we have
) Eos (A)))))))) E
141
Σ oi)(A) (G(V)) ((V))))
2 Σ (G(V)))/4))
As WVTV W, the non-zero eigenvalues of G(V) exactly the non-zero eigenvalues of WVV' = WWT,, i.e., the square of non-zero singular values of W. From Lemma we have
(GV)) 1/(11)
X(G(V))
(W))/(()
(49)
Therefore, we have
(1+1)/1
to
(A)2 2/- (
|A
2/1 S
(50)
This also implies that
min
||
2/1
s.t. W W St 2/11
((+1)/1
(51)
2t 2/1
Σ (W)
Suppose that W = Ei "o the SVD of W. We can let
Σl 0, 2((11) 1/2
1/(++1 T
A
U40
t
(52)
Pio !/1+1))) oi.
W1
Ein 0, 2/(4-1) 1/2
Here ||p:l12 = 1 and p.'p; p; = 0 for i + j. Then, W,A
W and Walle S f. We also have
1/1
|A
2/L 12/1.
2211 2/1
Σ 0
2/(+1)
2/(111
(1+1//1
=t 2/11 2/1
Σ
oi 2/121)+))
16

---

Published as a conference paper at ICLR 2023
In summary, we have
min + A
S2n 2/1
s.t. W W,
W. SL.
(+11/1
=min 2² + 2/1 120
oi (W)2
(53)
(++1/22
1) Σ (W)2(((4)))
2/(+1) Sppann
This completes the proof.
C.3
PROOF OF THEOREM 2
From Proposition] the minimum norm problem
5 is equivalent to
min L W
2/L Sp/2 s.t. XW = Y,
(54)
in variable W e Raxk According to Lemma 2 for any feasible W satisfying XW Y, because X Y and X is projection matrix, have
L||
2/5
2 L Y
2/L S2/2
(55)
S2yz
We also note that XX XX XW Y. Therefore, X is also feasible for the problem This indicates that Pin
X
2/L 825t.
C.4 PROOF OF THEOREM 3
For a feasible (W WW,,,.... WI-2/1, W W1-1, 11-1,,4-2W- W., 1.) is feasible for
point (W,, ....., Wx) for Pin (t), (1). 24-2 (1) (1), equivalently, Pun (1) t- (L(-2) Pia(1)) Recall that
we note
that
This
implies
that
Pin = min
L - 2 f + (1--2) (1
(im())
130
2
(56)
= (1)
From Theorem we have Piin | S2/1." This implies that Pin = |
S2/2 and
Piin (t) = 1- (1-2) X Y 11ssa
(57)
For the dual problem Dnn(t) (t) defined in (35 we note that
A Xxw ... W Wi-2WL-1lle
A XW ......W.. W, W
< T X
W Wwll2//wz-al
(58)
[=1
2-
~
W W:lll//wz-111
2
The equality can be achieved when W, = Lnnii for / E [T. - 2]. where ||l/|l = for / = 1.... I. 1. Specifically, set u w and let un right singular vector corresponds to the largest singular value of A T'x X. Therefore, the constraints on A is equivalent
| x & (4--2)
(59)
17

---

Published as a conference paper at ICLR 2023
Thus, according to the Von Neumann's 's trace inequality, it follows
tr A 2 Y) = Ir(A xxx' s X| (4-(2))) Y|
(60)
Suppose that X = UEVT is the singular value decomposition. Let E = diag
where 01 2 02 2 ... 2 or and ra We note that
L/2
Y S2/2
Σ lio1
o
2
1/2
(01/01)2/1
=0
1+
i=2
(61)
201
1+
(ai/o1)
dr.
The equality holds if and only if ... This is because for given x E (0,1) and 2 1, (a++*) 1/2 is strictly decreasing w.r.t. p E (0, 1]. As result, we have - (1-22) | S (-(2-) | = (t). The equality is achieved if and only if the singular values of X the same. In other words, the inequality is strict when X Y has different singular values. Then, the duality gap exists for the standard neural network.
C.5 PROOF OF PROPOSITION 3
For simplicity, write W L-11 1- and W. =wi,j for [m]] For the j-th branch of the parallel network, let Wi, on Wt, for E [L]. Here ar >> for E [Z] and they satisfies that I 0ijj 1 for j [m]. Therefore, have
XW Ly W WL-2,
col WT. XW1. ... W W--2, WT- L- W
row Wr.j
(62.)
This implies that (1,3 he(t).jelm is also feasible for the problem inequality of arithmetic and geometric means, the objective function in
12
According the the
is lower bounded by
m
a
W 1
2/L
Wis 12'")
(63)
L
Il
2
l W W
The equality achieved when (nl
for I E [L] and j [m)]. As the scaling /
operation does not change [ [ 11 we can simply let ||Wryll = 1 and the lower bound
becomes Em |
2/4 4 Em [| 2
2/L This completes the proof.
C.6 PROOF OF PROPOSITION
We first show that the problem 14 is equivalent to 15
The proof is analogous to the proof of
Proposition For simplicity, we write W
L-1,
w
1j and WL.5 whoh for j E [m]. Let
0r 0 for 1 E [T.] and they satisfies that [= 0n for j E [m]. Consider another parallel
18

---

Published as a conference paper at ICLR 2023
network (W je(]).e( whose j-th branch is defined by Wa. an Wij for I [L]. As Il Jn = 1, we have
col tow W...... WL 2,-2,WL-1 W- WL. XW W.y....... Wt 2-22 W. L-1.3 L.j
(64)
This implies that { a hetl).emm is also feasible for the problem
14
According to the the
inequality of arithmetic and geometric means, the objective function in is lower bounded by
W
(on. ((gllF)
(65)
lm1
Σ 1 E1
II Willee.
I [ |
The equality is achieved when or
W for I E [L] and j [m²]. As the scaling
operation does not change I |Willr, rr we can simply let [|,,,l and the lower bound
becomes 1 D |WLalle = Ex [[wigy 2. Hence, the problem (14) is equivalent to (15).
For the problem
15
we consider the Lagrangian function
L 2
L(W
W
|wLS ll2 + tr A A
Σ
XW1, by WL1,5 W2.5)
(66)
The primal problem is equivalent to pprl
min max L(WI...... WI, Wi....W, W. A
s.t. [ IF S L,j E [m]]. I E [T. - 2], /o 2-11l S 111 [mr.1))
W min max min L(WI,... Wi, A),
W.....W--1 A WL
s.t.
[iille I 1,7 E [T. - 2], rol bng S 1,j E [m].
(67)
mi
min maxtr(A Y) Σ WI....WL... WL-1 A
XW W 1 L/2).
j=1
s.t. |Wile S 1,1 E [1 - 2], (l S 1.j [m].
The dual problem follows
Dedel max tr(A A²
s.t. A T XWL 1. W WL-251l2 S L/2,
A W S 1,1E [L-2), 2), / S 1,j [m],
(68)
max ma YY...
s.t. A xww..... Wr-2w1-1112 112 V/ S 1, -L 1
C.7 PROOF THEOREM 4
We rewrite the dual problem
D = max tr (r T YY, A
s.t. A XW ... WI.-2w1-118 2 L/2,
(69)
(W, (W,....
WT-2 -L-1) E,,
19

---

Published as a conference paper at ICLR 2023
where the set θ is defined as
θ {(W WL-2 WL-1)||Wille s 1, 21, s 1}.
(70)
By writing 0 = (W1,..
WL-2 WL-1), the bi-dual problem, i.c., the dual problem of 66 is
given by
min | s.t. Jeco XW1 ... WL-2WL-Idu(0)=- =
(71)
Here µ : 2 + E is signed vector measure, where Σ is o-field of subsets of θ and || is its total variation. The formulation in (7I) has infinite width in each layer. According to Theorem 10 in Appendix G the measure μ in the integral can be represented by finitely many Dirac delta functions. Therefore, there exists a critical threshold of the number of branchs vn" < KN + such that we can rewrite the problem as
min
W TOW Lg 2|,
m
(72)
row = Y, Σ XW W..... WL-2., L-1, WL. jml
s.t.
[ Wollee S $1,1 T. - 2/, ||
col 2-1 S 1, E [m*).
Here the variables are Wi, for / E L - 2] and [m*].
Wi.1 and W,, This is equivalent to [5]
As the strong duality holds for the problem (69 and 71 the primal problem (15) equivalent to the dual problem 669 as long m 2 m
Now, we compute the optimal value of DRd. Similar to the proof of Theorem we can show that the constraints in the dual problem 69 is equivalent to
A 2 X L/2.
(73)
Therefore, have
tr(A YY)
& | X 1 X
- |X
(74)
2
This implies that ppel_ lin
1 |XtY||..
D STAIRS OF DUALITY GAP FOR STANDARD DEEP LINEAR NETWORKS
We consider partially dualizing the non-convex optimization problem by exchanging 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 trnotr(AA (Y) - (IA |A Xw..... W1-2
(W.) A
(75)
W 1ll S ttit [L - 2 WL-L 1.
By changing the order of L mins and the max in (5). for I.... L 2, we can define the 1-th partial "dual" problem
(1) = min max min W.... W W
tr(A Y)- - (1()-1111AAA X We-2w1-1la 11). (76)
s.t. W | St.ie 2), 1W 1.
For 1 = 0, D (1) corresponds the primal problem (t), while for -, (10 is the dual problem Din (t). From the following proposition, we illustrate that the dual problem of D corresponds to minimum norm problem of a neural network with parallel structure.
(
20

---

Published as a conference paper at ICLR 2023
Proposition 8 There exists threshold the number of branches m S KN such that the problem Did (t) is equivalent the "bi-dual" problem
m
min
row
12
1.g
s.t.
XW1 ... W/W1+1J... ... WL-2, WLJ Y.
(77)
f=1
|Wile & stie E [4, W Wille st,i= I,..,, - 2 E [m*].
[w 1- 12 - 1,j E (m").
where the variables are W; E m 1xm; for E [1] Wis E ERm--xm,, for = = 1+ 1,.,,,.... I,.....
j E [m*), W R and W. E Rm xoa,
We can interpret the problem 777 as the minimum norm problem of a linear network with parallel structures in (I 1)-th to (L 2)-th layers. This indicates that for = 0, 0, L 2, the bi-dual formulation of (1) 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 Di (t).
Proposition 9 The optimal value Di (1) follows
(1) ii (1) (4--2) X (25(02)) D
(78)
Suppose that the eigenvalues X are not identical to each other. Then, we have
(t) D (T.-2) 2)
(t) D(1111)
Di (1) D(I).
(79)
In Figure we plot D (1) (1) for 1 O...., for an example.
101
Figure Example of (1). (t).
D.1 PROOF OF PROPOSITION 9
note that
max tr( Ar(A"Y)
A
s.t. A XW,
W W st,i=l+,..., 1-....--2. 2,
(80)
ir(A"Y), s.t. | xww, Will 5 (1.-2--))
max
min
A W,+i WL-2
Therefore, we can rewrite (t) as
D (t)
min maxtr(A Y). WI..., W,
s.t. || XW, Wilk S - (1-2211
| St, [1)
(81)
min max t (L-2-1) tr TY),
Wi...W, A
s.t. | A Xx....... W1l22 < 1, W.ll St,i !I]
21

---

Published as a conference paper at ICLR 2023
From the equation
10
note that
min max (eretr(A' YY Wi...W W
s.t. A XW
W, Stii (5).
K
min
Ww+2,lle
(82)
s.t. |Will
S 1, E [L- 2), || < 1, [mr.-1];
XW1 W42 =
X Y| $2/012)
This completes the proof.
E PROOFS OF MAIN RESULTS FOR RELU NETWORKS
E. PROOF PROPOSITION
For the problem of P(t), introduce the Lagrangian function
L( 22, W) According to the convex duality of two-layer ReLU network, we have
w 12 tr(A" (((W())))))) W2) W3 Y)).
(83)
(R) =
min max tr T Y) - I([I ((XW1) 11) SWillsStlwaa A
min max min tr(A YY) II||II/((A0 (XW:)) 1) IWillest [[wal1S1
(84)
min maxtr(A YY),, s.t. |AAv//2 Vv A(W,). WWillege A
By changing the min and max, we obtain the dual problem.
A (R) = m Y), s.t. v I 1, A(W.). |F St.
(85)
A
The dual of the dual problem writes
min
/W Sallwallest ((XW1), w2) du (W1, w2) Y.
(86)
Here is a signed vector measure and ||lly is its total variation. Similar to the proof of Proposition
I we can find a finite representation for the optimal measure and transform this problem to
K
min W
Wa.illa,
W. XX
==1
(87)
s.t.
(XW (XW1))) 12) W2,) w = Y, W st,//wa5ll S 1.
Here m < KN + 1. This completes the proof.
E.2 PROOF OF THEOREM 5
For rank-1 data matrix that X = caf. suppose that A, 1XW1)+. It is easy to observe that
A af + (-c)+
22

---

Published as a conference paper at ICLR 2023
Here we let a1,+ (Wfau)+ and a1,- (-WI a.
For a three-layer network, suppose that X is the optimal solution to the dual problem (t) We consider the extreme points defined by
arg
(XW)((W)))
(88)
[[W lll St,llwa la
For fixed WT, because af. a1,- = 0, suppose that
W2 u a + u2a1 + Ugr,
where I a1,t = r a1 = and | = 1. The maximization problem on W2 reduces to
arg max (A*) (c) a (1)
Mn M6,
s.t. u |1,+1
ش | + 5 1.
If (x)) and (A*) have different signs, then the optimal value is
l12] And the corresponding optimal is W2 a1,+ ||a+/ |l2 w2 at.-/|lar, ||a1,-112- 1l2. Then, the problem becomes
max (1l (x))
arg max max W,
We note that
m {
| 11, ||a).-122] < |W] |Will||aoll2 4||aoll2.
Thus the optimal W, is given by
W1 = tsign (
(c) 1(x) (-c))DDoff
Here Po an/ aan/|la// ||a0|2 and P1 T satisfies || This implies that the optimal wa is given by
W2 P1-
On the other hand, if (c) and (A*)*(-c) c) have same signs, then, the optimal Wa follows
1(*") (c) a (A*) c) aa
W2
((A') a ((> )
The maximization problem W, is equivalent to
arg max Willese
11
By noting that
a 1 [t|aa = WT a
|
ag
a
the optimal W, is given by
W
Here Ps = 20ol2 and p RT satisfies ||pl| = 1.
E.3 PROOF PROPOSITION
Analogous to the proof of Proposition we can reformulate (2 into 23
The rest of the proof is
analogous the proof of Proposition For the problem 23 consider the Lagrangian function
L(W1... WL)
(89)
w Lij
row
l2 + tr AT Σ ((XW1)))
W w +
==1
23

---

Published as a conference paper at ICLR 2023
The primal problem is equivalent to
pprl ReLU
min max L(W1, 1, Wr, A);
Wi....W A
s.t. W S4Ú [mm], [T. 2], [/ L- S 1, [mn_-1}
min max min L(W1,... 1...., W.,,A), W...., WL.1 A Wz
s.L. ( S 1, [T. - 1 lo S 1,j e [m],
min max tr (r Σ [[AF(((W1s))) W W2.-2))+ w2-1,)) S T./2). W..... WL-1 A
==1
s.t. Wiille $ E [T. - w ll S 1, E [m].
(90)
By exchanging the order of min and max, the dual problem follows
D max (r(A'rAAA' Y).
A
s.t.
A (((XW (((XX11))44 1.)) W 2 S L/2, Willl S 11.1 [T. 2), / 2-111112 - 1, [m],
(91)
(r A
max
A
s.t.
(((WW))
W L/2.
Wille s 1, -L- |LL-l 1
E.4 PROOF OF THEOREM
The proof is analogous to the proof of Theorem 4 We can rewrite the dual problem as
DR = max tr(A (A T Y),
s.t. | ((XW1)) 1)+... W S L./2, V.W..... Wr.12
(92)
where the set θ is defined as
θ {(
W WL-2, WL-1) W < 1,1 1| S $1}.
(93)
By writing 0 = (W,,
W 2. wr.-)), the bi-dual problem, i.e., the dual problem of (92 is
given by
min H
(94)
s.t. (oes((( ((W,)) Wp-2)
Here : Σ - R is a signed vector measure, where Σ is a a-field of subsets of O and || is its total variation. The formulation in (94) has infinite width in each layer. According Theorem I0 in Appendix G the measure u in the integral can be represented by finitely many Dirac delta functions. Therefore, there exists m² KN such that we can rewrite the problem (94) as
min
row w
L,
1
(95)
s.t.
((XW1,)) WL-25)+ w wo w row Y, J=1
Wiolle $ 1,1 [L 2), || 1 - 1,j E [m=)]
Here the variables are Wt, for / L 2] and [m=] As the strong duality holds for the problem 992 and 94 the dual problem (92) long m
W L-1 and Wz W. This is equivalent to (3 the primal problem (23) equivalent to
24

---

Published as a conference paper at ICLR 2023
E.5 PROOF OF THEOREM
Consider the following dual problem
D
ReLU max tr(A"Y), s.t. max
|A'v. vill2 S L/2. vE[m!]
(96)
Apparently we have aub ReLU
D I ReLU- As A is the optimal solution to ReLU and A feasible
Dorl
to De we have D pprlssh
teLU 2 Dpri
ReLU- This implies that Dprl.anh = -
ReLL
ReLU- We note that (26) is
the dual problem of 16p. Therefore, as corollary of Theorem we have
6
pptl.sub
Dprl.sub
Dprl
pprl RtLU
ReLU
ReLU
ReLU
Therefore, (Wi. W is the optimal solution to 23
F PROOFS OF AUXILIARY RESULTS
F.1 PROOF OF LEMMA II
Denote E IR" such that 0g A; and denote IR" such that b, Ac(A). We can show that
majorized by 6, i.e. for k E [n 1), we have
b
(97)
and Σi= 0i -Ei b, Here a()) is the i-th largest entry in We first note that
Σ
Aa=tr(A) Σ (AA)..
On the other hand, for k E [n - 1]. we have
k
TTo tr(diag(1) (c(dia)())Adiag()))
0(3)
max VER" o. ((0.0) 1 F==k
1=1
max HER" (E 17 o=
(98)
max VEREXN VVT=I tr(VAVT)
Σ (x(A)) Σ b(()-
Therefore, is majorized by b. As f(x) = xx is convex function, according to the Karamata's inequality, we have
Σ
f(a,) < f(b.).
1=1
i=1
This completes the proof.
F.2 PROOF OF LEMMA 2
According to the min- max principle for singular value, we have
(W( min max idd |//12
As P is projection matrix, for arbitrary Rd, we have | 2 I [|al Therefore, we have
max =
|PWx|22 S max |xl|2
=
This completes the proof.
25

---

Published as a conference paper at ICLR 2023
G CARATHEODORY'S THEOREM AND FINITE REPRESENTATION
We first review a generalized version of Caratheodory's 's theorem introduced in (Rosset et al. 2007
Theorem Let be a positive measure supported on a bounded subset D C RR Then, there exists measure whose support is finite subset of D, {Z1...., , with k I N 1 such that
J 2dp(2) Σ 2z)((zi,,
(99)
and ||||| = ||/|/r--
We can generalize this theorem to signed vector measures.
Theorem Let p.: E K be a signed vector measure supported on a bounded subset D C R.N. Here E is a o-field of subsets of D. Then, there exists a measure D whose support is finite subset of D, {21,..., J, with k S KN + such that
J, zdp(z)= = Σ zz)((Z),
(100)
and [|z||av = 1|H||av.
PROOF Let be signed vector measure supported bounded subset D C R. Consider the extended set 1) |= D.u TRKK, ||ull2 1}. Then, μ corresponds to scalar-valued measure on the set D and ||д||г llAl[v.. We note that D is also bounded. Therefore, by applying Theorem 8 to the set D and the measure j,, there exists measure ù whose support is finite subset of D, {21u]" ...., 2621 with &s < KN such that
J Zdi(Z) = Σ znu di(zz
(101)
and ||Al|rv = |pllrv. We can define as the signed vector measure whose support is a finite subset {21,...,2x) ) and du(z;) = u,d(zzu;). Then, ||/||y = |illT the proof.
|| = ||/|/Ty. This completes
Now we are ready to present the theorem about the finite representation of signed-vector measure.
Theorem 10 Suppose that 0 is the parameter with a bounded domain O C RD and o(X, 0) R.d θ > IRN is an embedding of the parameter into the feature space. Consider the following optimization problem
min Iplliv s.t. [ ((x,0)du(0))2 =Y.
(102)
Assume that an optimal solution to 102) exists. Then, there exists an optimal solution fa supported on most KN N features in O.
PROOF Let j be an optimal solution to 102
We can define measure on R- as the push-forward
of fa by P(B)= = (x(o) 0) E B)). Denote D = {Ø(X, 0)(0 E θ}. We note that P is supported
find measure Q whose support is a finite subset D, [21...., . with S KN + 1. For each 2; E D,
on D and D is bounded. By applying Theorem 9 to the set D and the measure P.
we can find 0; such that ((X,0,) 2;. Then, fa >k 8(0 0, (=()(=;) is optimal solution to 102 with at most K. KN- features and |Ø|lTV = [V Here 5(-) is the Dirac delta measure.
26


Reviews:
[{"review_id": "WgODQn6oGp9", "reviewer": "Reviewer_Lv6H", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "It has been recently been shown that 2 layers L2 regularized relu networks are equivalent to convex problems and have \"zero duality gap\".\nThe paper studies a generalization of this result: does it hold when the network's output is vectorial, and for more than 3 layers?\nThe paper shows that some regularized neural networks with more than 2 layers and vector output have a non zero duality gap.\nThe authors prove that this duality gap vanishes for so-called \"parallel architectures\", with a particular regularization.", "summary_of_the_review": "Marginal improvement over literature on the theoretical side, no practical contribution on the the practical one.", "strength_and_weaknesses": "Strength:\n- the convex reformulation of neural networks with path or L2 regularization is an interesting direction of research that has attracted attention lately, from the theoretical point of view.\n\nWeaknesses:\n- half of the paper is devoted to linear networks, that are not, to my knowledge, used in practice\n- there is a stream of papers on the same topic with marginal improvements from one to the other (i.e., Ergen and Pilanci 2021e) and the contribution here may seem incremental. The proofs techniques are based on already known dual reformulations by Ergen and Pilanci; the main novelty to me is Proposition 2 that is easy to prove.\n- the proposed approach is not practical (for example, considering rank 1 design matrices); there are not experiments in the paper.", "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": "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": "Oh2BaFYNPd", "reviewer": "Reviewer_jwcy", "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": "", "summary_of_the_paper": "This is a theoretical paper that extends previous results on the duality gap of neural network training. Its main results are: 1) linear networks with L2 regularization and 3 or more layers have in general positive duality gap, though its primal and dual solution can be computed in closed form; and 2) strong duality holds in parallel ReLU networks with a specific regularization of more than 3 layers. ", "summary_of_the_review": "This paper tackles an important problem and generalises previous results. Although the extension is incremental, it is general in the number of layers and seems to be a steppingstone towards more general results. On the other hand, it is not clear whether the authors have to innovate in the proof techniques. \n\nAll in all, the paper can be interesting for a part of the community studying this particular problem, and though it might not have an immediate impact in the community at large, it will hopefully inspire future research to study the practical impact of this research (by, e.g., leveraging fast parallel convex optimisers for practical applications of deep parallel networks.)", "strength_and_weaknesses": "#### Strengths\n- The paper tackles the challenge of understanding the optimisation problem of training neural networks by focusing on the duality gap. This is an important area of research, with the high potential impact of making training deep learning models more easily and efficiently.\n- The results are consistent with previous works and extend the state of the art. \n\n#### Weaknesses\n- The results seem incremental with respect to previous works. \n- The authors don't make clear why previous works couldn't analyse the current case, and what the key novel technical contributions are that allow the current results, so it is difficult to evaluate the contribution.\n- As a minor comment, there are some clarity issues that should be easily addressed, see below.", "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": {}}, {"review_id": "GndJbPZofWz", "reviewer": "Reviewer_BG6i", "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": "", "summary_of_the_paper": "This paper studies the duality gap of deep neural networks and parallel neural networks. Two kinds of activation functions are considered: identity function and ReLU function. The author reformulated the optimization problem to a convex problem using AM-GM inequality, and study their dual problem. The bi-dual problem of neural networks are parallel neural networks. The author proved that the duality gap of deep neural networks may not be zero except for some special cases, while the duality gap of parallel neural networks are zero. ", "summary_of_the_review": "This paper extended the results by Ergen & Pilanci 2020 and studied the duality gap of neural networks and parallel neural networks. However, the regularizer used in the two neural networks are different, which makes the statement that parallel neural networks have zero duality gap problematic.\n ", "strength_and_weaknesses": "This paper extended the results by Ergen 2020 and studied the dual problem and bi-dual problem of deep neural networks. The author proved that the bi-dual problem of deep neural networks are in the form of parallel neural networks, and proved that strong duality may not hold for standard deep neural networks. The author proposed a parallel nerual network which strong duality holds.\nHowever, as for the parallel neural networks, the author used $\\\\|\\cdot\\\\|\\_F^L$ regularization, which is different from standard neural networks. It is not possible to tell whether strong duality comes from the parallel architecture or the difference in regularization. Could the author proved more discussion on this point?\nBesides, proposition 3 may be flawed. The proof includes the term $\\sum_{j=1}^m\\\\|W\\_{L,j}\\\\|\\_F^L$ while the statement includes $\\\\|W\\_{L}\\\\|\\_F^L=(\\sum_{j=1}^m \\\\|W\\_{L,j}\\\\|\\_F^2)^{L/2}$ . These two terms are not equal unless $L=2$.", "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": "2zKM2gjGW4u", "reviewer": "Reviewer_RuMQ", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work shows new results on convex formulations of neural networks. The goal is to formulate the nonconvex optimization problem as minimum norm problems, derive the convex dual problem and study whether the duality gap is zero. If it is zero, then the dual can be solved via convex optimization tools with theoretical guarantees, instead of the nonconvex problem. For linear networks, it is shown that standard networks of depth at least 3 have non-zero duality gap. In contrast parallel linear architectures have zero duality gap. A similar result holds for networks with ReLU activations.", "summary_of_the_review": "This paper shows novel theoretical results on convex formulations of neural networks. Experiments would improve the paper and clarify its practical significance.", "strength_and_weaknesses": "Strengths:\n\n1. Solid theoretical results.\n2. Novel results for convex formulations of neural networks.\n3. The paper is well written.\n\nWeaknesses:\n\n1. There are no experiments on the performance of parallel networks and whether the convex optimization problems can be solved in practice.\n2. It is not clear if the results on parallel linear networks in Section 3.2 are new. Table 1 shows that they were studied in previous works.\n3. The process of obtaining the solution to the primal problem from the solution of the dual problem is not explained. Can the authors elaborate on this?\n", "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": {}}]

Author rebuttal:

Decision: Accept: poster