Vector-output ReLU Neural Network Problems are Copositive Programs: Convex Analysis of Two Layer Networks and Polynomial-time Algorithms
Authors: Arda Sahiner
Tolga Ergen
John M. Pauly
Mert Pilanci
Venue: ICLR 2021 Poster (2021)
Keywords: neural networks
theory
convex optimization
copositive programming
convex duality
nonnegative PCA
semi-nonnegative matrix factorization
computational complexity
global optima
semi-infinite duality
convolutional neural networks

Abstract: We describe the convex semi-infinite dual of the two-layer vector-output ReLU neural network training problem. This semi-infinite dual admits a finite dimensional representation, but its support is over a convex set which is difficult to characterize. In particular, we demonstrate that the non-convex neural network training problem is equivalent to a finite-dimensional convex copositive program. Our work is the first to identify this strong connection between the global optima of neural networks and those of copositive programs. We thus demonstrate how neural networks implicitly attempt to solve copositive programs via semi-nonnegative matrix factorization, and draw key insights from this formulation. We describe the first algorithms for provably finding the global minimum of the vector output neural network training problem, which are polynomial in the number of samples for a fixed data rank, yet exponential in the dimension. However, in the case of convolutional architectures, the computational complexity is exponential in only the filter size and polynomial in all other parameters. We describe the circumstances in which we can find the global optimum of this neural network training problem exactly with soft-thresholded SVD, and provide a copositive relaxation which is guaranteed to be exact for certain classes of problems, and which corresponds with the solution of Stochastic Gradient Descent in practice.

Published as a conference paper at ICLR 2021
VECTOR-OUTPUT RELU NEURAL NETWORK PROB- LEMS ARE COPOSITIVE PROGRAMS: CONVEX ANAL- YSIS OF TWO LAYER NETWORKS AND POLYNOMIAL-
TIME ALGORITHMS
Arda Sahiner, Tolga Ergen, John Pauly & Mert Pilanci Department of Electrical Engineering Stanford University (sahiner, ergen, pauly,
ABSTRACT
We describe the convex semi-infinite dual of the two-layer vector-output ReLU neural network training problem. This semi-infinite dual admits a finite dimen- sional representation, but its support is over convex set which is difficult to char- acterize. particular, we demonstrate that the non-convex neural network train- ing problem equivalent to dintee-amensional convex copositive program. Our work is the first to identify this strong connection between the global optima of neural networks and those of copositive programs. We thus demonstrate how neu- ral networks implicitly attempt to solve copositive programs via eonegavoneee matrix factorization, and draw key insights from this formulation. We describe the first algorithms for provably finding the global minimum of the vector output neu- ral network training problem, which are polynomial in the number of samples for a fixed data rank, yet exponential in the dimension. However, in the case of con- volutional architectures, the computational complexity is exponential in only the filter size and polynomial in all other parameters. We describe the circumstances in which we can find the global optimum of this neural network training prob- lem exactly with coft-thresholder SVD. and provide copositive relaxation which is guaranteed to be exact for certain classes of problems, and which corresponds with the solution of Stochastic Gradient Descent in practice.
INTRODUCTION
In this paper, we analyze vector-output two-layer ReLU neural networks from an optimization per- spective. These networks, while simple, are the building blocks of deep networks which have been found to perform tremendously well for a variety of tasks. We find that vector-output networks reg- ularized with standard weight-decay have convex semi-infinite strong dual-a convex program with infinitely many constraints. However, this strong dual has a finite parameterization, though express- ing this parameterization non-trivial. In particular, we find that expressing a vector-output neural network as a convex program requires taking the convex hull of completely positive matrices. Thus, we find an intimate, novel connection between neural network training and copositive programs, ie. programs over the set of completely positive matrices (Anjos & Lasserre (011). We describe algorithms which can be used to find the global minimum of the neural network training problem in polynomial time for data matrices of fixed rank, which holds for convolutional architectures. We also demonstrate under certain conditions that we can provably find the optimal solution to the neu- ral network training problem using soft-thresholde Singular Value Decomposition (SVD). In the general case, we introduce a relaxation to parameterize the neural network training problem, which in practice find be tight in many circumstances.
1.1 RELATED WORK
Our analysis focuses on the optima of finite-width neural networks. This approach contrasts with certain approaches which have attempted to analyze infinite-width neural networks, such as the

---

Published as a conference paper at ICLR 2021
Neural Tangent Kernel (Jacot et al. 2018). Despite advancements in this direction, infinite wiith neural networks do not exactly correspond to their finite-width counterparts, and thus this method of analysis is insufficient for fully explaining their success (Arora et al. 2019).
Other works may attempt to optimize neural networks with assumptions the data distribu- tion. Of particular interest is (Ge et al.) 2018). which demonstrates that a polynomial number of samples generated from planted neural network model sufficient for extracting its parameters using tensor methods, assuming the inputs are drawn from symmetric distribution. If the input distribution simple convolutional neural network with one filter is Gaussian, it has also been shown that gradient descent can find the global optimum in polynomial time (Brutzkus & Glober- son 2017). contrast to these works, we seek to find general principles for learning two-layer ReLU networks, regardless of the data distribution and without planted model assumptions.
Another line of work aims to understand the success of neural networks via implicit regular- ization, which analyzes how models trained with Stochastic Gradient Descent (SGD) find solutions which generalize well, even without explicit control of the optimization objective (Gunasekar al.) 2017 Neyshabur et al. 2014). In contrast, we consider the setting of explicit regularization, which often used in practice in the form of weight-decay, which regularizes the sum of squared norms of the network weights with single regularization parameter B, which can be critical for neural network performance (Golatkar et al. 2019).
Our approach of analyzing finite-width neural networks with a fixed training dataset has been explored for networks with scalar output (Pilanci & Ergen] [020] |Ergen & Pilanci] d020ald). In fact, our work here can be considered a generalization of these results. We consider ReLU-activation two-layer network f :Rd + R with m neurons:
m
f(x) = Σ x uz)+0
where the function (++ m0. denotes the ReLU activation, fu, ) the first-layer weights of the network, and {Ø, R are the second-layer weights. In the scalar-output case, the weights vy are scalars, i.e. = 1. Pilanci & Ergen (2020) find that the neural network training problem in this setting corresponds finite-dimensional convex program.
_i=1
However, the setting of scalar-output networks is limited. In particular, this setting cannot account for tasks such as multi-class classification or multi-dimensiont regression, which are some of the most common uses of neural networks. contrast, the rector-output setting is quite general, and even greedily training and stacking such shallow vector-output networks can match or even exceed the performance
deeper networks on large datasets for classification tasks (Belilovsky let al. 2019). We find that this important task of extending the scalar case to the vector-output case an exceedingly non-trivial task, which generates novel insights. Thus, generalizing the results of Pilanci & Ergen| (2020) is important task for more complete knowledge of the behavior of neural networks in practice.
Certain works have also considered technical problems which arise in our analysis, though in application they are entirely different. Among these is analysis into cone-constrained PCA, as explored by Deshpande et al. (2014) and Asteris et al. (2014). They consider the following optimization problem
max u Ru
s.t Xu 2 0: |
This problem is in general considered NP-hard. Asteris et al. (2014) provide an exponential algo- rithm which runs in ((d)) time to find the exact solution to 2). where X E guxd and R Sd is symmetric matrix. We leverage this result to show that the optimal value of the vector-output neural network training problem can be found in the worst case in exponential time with respect to rank(X), (X), while in the case of fixed-rank data matrix In particular, convolutional networks with fixed filter sizes (c.g., x 3 x m convolutional kernels) correspond to the fixed-rank data case (e.g., 9). In search of polynomial-time approximation
algorithm is polynomial-time
2

---

Published as a conference paper at ICLR 2021
to Deshpande al. (2014) evaluate relaxation of the above problem, given as
max (R. U)
(3)
s.t XUX 0; tr(U) = 1
While the relaxation not tight all cases, the authors find that in practice it works quite well for approximating the solution to the original optimization problem. This relaxation, in particular, corresponds what we call copositive relaxation, because consists of relaxation of the set Crсa fuu" T | 1, Xu 0}. When X = and the norm constraint is removed, Crea is the set of completely positive matrices (Dür 2010). Optimizing over the set of completely positive matrices is NP-hard, as is optimizing over its convex hull:
C == conv(uu' xu20)
Thus, optimizing over C is convex optimization problem which is nevertheless NP-hard. Various relaxations to C' have been proposed, such as the copositive relaxation used by (Despaande et al, 2014) above:
(U:UUUU)) XUX 2 0}
In fact, this relaxation is tight, given that TRd and d S 4 Burer 2015 Kogan & Berman 1993). However, C Ć for d 2 so the copositive relaxation provides lower bound in the general case. These theoretical results prove insightful for understanding the neural network training objective.
1.2 CONTRIBUTIONS
We find the semi-infii semi-infinite convex strong dual for the vector-outpur two-layer ReLU neural network training problem, and prove that it has a finite-dimensional exact convex optimiza- tion representation.
We establish new connection between vector-output neural networks, copositive programs and cone-constrained PCA problems, yielding new insights into the nature of vector-output neural network training, which extend upon the results of the scalar-output case.
We provide methods that globally solve the vector-output neural network training prob- lem in polynomial time for data matrices of fixed rank, but for the full-rank case, the complexity is necessarily exponential in d assuming P # HPP.
We provide conditions on the training data and labels with which we can find a closed- form expression for the optimal weights of vector-output ReLU neural network using soft-thresholded SVD.
We propose a copositive relaxation to establish a heuristic for solving the neural network training problem. This copositive relaxation is often tight in practice.
2 PRELIMINARIES
In this work, we consider fitting labels Y E Rxx from inputs X E R with a two layer neural network with ReLU activation and m neurons in the hidden layer. This network is trained with weight decay regularization on all of its weights, with associated parameter 3 > 0. For some general loss function ( Y), this gives us the non-convex primal optimization problem
3 2
m
D² min {(f(x) u, Eld
Σ
+ 11,,113
(4)
ny ER
In the simplest case, with fully-connected network trained with squared los this becomes:
p" min
Σ o - Y + 2 Σ (1u,,11 + |1011
(5)
uyeR" 0 e
==1
Appendix A.6 contains extensions general convex loss functions.
3

---

Published as a conference paper at ICLR 2021
However, alternative models can be considered. In particular, for example, Ergen & Pilanci (2020d) consider two-layer CNNs with global average pooling, for which we can define the patch matrices {Xx which define the patches which individual convolutions operate upon. Then, the vector- output neural network training problem with global average pooling becomes
K m
Pronu min u ER EyER"
X + YI? + Σ (1u, + +101113)
(6)
2
A=
We will show that in this convolutional setting, because the rank of the set of patches M == [1,, xx] cannot exceed the filter size of the convolutions, there exists an algorithm which is polynomial in all problem dimensions to find the global optimum of this problem. We note that such matrices typically exhibit rapid singular value decay due to spatial correlations, which may also motivate replacing it with approximation of much smaller rank.
In the following section, we will demonstrate how the vector-output neural network problem has convex semi-infinite strong dual. To understand how to parameterize this semi-infinite dual in a finite fashion, we must introduce the concept of hyper-plane arrangements. We consider the set of diagonal matrices
== [diag(1
|/ull2 S 1}
This is a finite set of diagonal matrices, dependent on the data matrix X, which indicate the set of possible arrangement activation patterns for the ReLU non-linearity, where value of indicates that the neuron is active, while 0 indicates that the neuron is inactive. In particular, we can enumerate the set of sign patterns D (D.) where P depends X but is in general bounded by
((
P 2r
for :- rank(X (X) Pilanci & Ergen 2020 Stanley et al. 2004). Note that for fixed rank r, such as
the convolutional case above, is pol polynomial in n. Using these sign patterns, we can completely characterize the range space of the first layer after the ReLU:
{(xu++ |lu||2 S 1} = (D,Xu: ||u/|2 S 1, (2D; - 1) 2 0, i i [PT}
We also introduce class of data matrices X for which the analysis of scalar-output neural net- works simplifies greatly, as shown in (Ergen & Pilanci 20206). These matrices are called spike-free matrices. particular, matrix X is called spike-free if holds that
{Xu)++ : ||u/|2 S 1} = {Xu: [|u]|2 S 1
(7)
When X spike-free, then, the set of sign patterns reduces to a single sign pattern, because of the identity in ( The set of spike-free free matrices includes (but is not limited to) diagonal matrices and whitened matrices for which n S d, such as the output of Zero-phase Component Analysis (ZCA) whitening. The setting of whitening the data matrix has been shown to improve the performance of neural networks, even deeper settings where the whitening transformation applied to batches of data at each layer (Huang al. 2018).. We will see that spike-free matrices provide polynomial-time algorithms for finding the global optimum of the neural network training problem in both and d (Ergen & Pilanci 2020b), though the same does not hold for vector-output networks.
{I},
2.1 WARM-UP: SCALAR-OUTPUT NETWORKS
We first present strong duality results for the scalar-output case, i.e. the case where 1.
Theorem Pilaaci & Ergen 2020) There exists m S + such that if m m², for all B > 0, the neural network training problem 5 has a conver semi-infinite strong dual, given by
d'= 2: == (Xx)
max ISA
ylا = 1
(8)
Villlas!
Furthermore, the neural network training problem has a convex, fimite-dimensional strong bi-dual, given by
1
p"
min (2D. -1, ViE[P 2
D.X (w: v.) v1l +
1ws//2 + ||1///2
(9)
(2D.-1)Xer 20 (
1=
1=1
4

---

Published as a conference paper at ICLR 2021
This is convex program with 2dP variables and 2n linear inequalities. Solving this problem with standard interior point solvers thus has a complexity of (dd (2drr((a)) (r)))) which is thus exponential in but for fixed rank is polynomial in
In the case of spike-free X, however, the dual problem simplifies single sign pattern constraint D1 = I. Then the convex strong bi-dual becomes (Ergen & Pilanci (020b)
w 2 [(w v) 2112 B (10ol12 ||0|12)
1
p' min
(10)
Xe20
This convex problem has much simpler form, with only 2n linear inequality constraints and 2d variables, which therefore has complexity of (ndd). We will see that the results scalar-output ReLU neural networks specific case of the vector-output case.
STRONG DUALITY
3.1 CONVEX SEMI-INFINITE DUALITY
There exists an m I nc + 1 such that if m 2 for all 3 > 0, the neural network training problem (5 has convex semi-infinite strong dual, given by
Theorem
p Z:
max Sa SI
-
Y 1
(11)
IT (Xu)
Furthermore, the neural network training problem has a convex, finite-dimensional strong bi-dual, given by
P
P
D"
min
1
Σ D,X,, YI + Σ |ill=
(12)
Viek: ViE[P]
2
for convex sets KG;
K. = conv
(2D, - I)xu 2 0, ||و||2 1
(13)
The strong dual given in is convex, albeit with infinitely many constraints. In contrast, 12 is convex problem has finitely many constraints. This convex model learns a sparse set of locally linear models Vú which are constrained over hyperplane arrangements is induced by the sum of nuclear-norms penalty. The emergence of the nuclear norm penalty is particularly interesting, since similar norms have also been used for rank minimization problems (Candès & Tao 2010 Recht et al., 2010), proposed as implicit regularizers for matrix factorization models (Gunasekar et al.J 2017). and draws similarities
be in a convex set, for which group sparsity and low-rankness
nuclear norm
regularization in multitask learning (Argyriou al. 2008 Abernethy et al. 2009), and trace Lasso (Grave et al. 201T). We note the similarity this result to that from Pilanci Ergen 2020), whose formulation special case of this result with 1, where K,, reduce to
Ic: = (u: (2D; - X) 2 00 (2D, 1)X 2 0}
from which we can obtain the convex program presented by Pilanci & Ergen (2020). Further, this result extends to CNNs with global average pooling, which is discussed in Appendix A.3.2.
Remark 1.1 It is interesting to observe that the corvex program 12 can be interpreted as a piece- wise low-rank model that is partitioned according the set of hyperplane arrangements of the data matrix. In other words, a two-layer ReLU network with vector output is precisely linear learner over the features [D,X.- ... DpX), where convex constraints and group nuclear norm regulariza- V[]|= is applied to the linear model weights. In the case of the CNNs, the piecewise tion Σ low-rank model is over the smaller dimensional patch matrices {Xx) AK which result in signifi- cantly fewer hyperplane arrangements, and therefore, fewer local low-rank models.
5

---

Published as a conference paper at ICLR 2021
3.2 PROVABLY SOLVING THE NEURAL NETWORK TRAINING PROBLEM
In this section, we present a procedure for minimizing the convex program as presented in (12) for general output dimension This procedure relies on Algorithm for cone-constrained PCA from (Asteris et al.) 2014), and the Frank Wolfe algorithm for constrained convex optimization (Frank al.) 1956). Unlike SGD, which is a heuristic method applied to non-convex training problem, this approach is built upon results of convex optimization and provably finds the global minimum of the objective. In particular, we can solve the problem in epigraph form,
min 220 V.EK WiE[P) E. Vt
min
DAXV, YI + 31
(14)
where we can perform bisection over / in outer loop to determine the overall optimal value of 12). Then, we have the following algorithm to solve the inner minimization problem (14):
A Agorithm 1:
1. Initialize (V Ji=1 0.
2. For steps k:
(a) For each i [P] solve the following subproblem:
(1)
(D.Xug² T Y Σ D
max 1IlaS1
(2D, 9 11
11)200
And define the pairs {(u, 9.)) be the argmaxes the above subproblems. This is is form of semi semnenonneettive matrix factorization (semi-NMF) on the residual at step (Ding et al. 2008). can be solved via cone-constrained PCA in O(n") time where r= raak(X),
(b) For the semi-NMF factorization obtaining the largest objective value, i* arg max; si (k) form M,AA) g.. For all other + i", simply let M
(c) For step size (k) E (0, 1). update
V. ( (1-a" (*) V (a M. (R)
The derivations for the method and complexity of Algorithm are found Appendix A.4. We have thus described Frank- Wolfe algorithm which provably minimizes the convex dual problem, where each step requires a semi-NMF operation, which can be performed Onn") time.
3.3
SPIKE-FREE DATA MATRICES AND CLOSED-FORM SOLUTIONS
As discussed in Section 2, if X is spike-free, the set of sign partitions is reduced to the single partition D = I. Then, the convex program 112 becomes
min Veconv(ug" (el2o, 2
XV - +
(15)
This problem can also be solved with Algorithm However, the asymptotic complexity of this algorithm is unchanged, due to the cone-constrained PCA step. If the constraint on V were removed, (15) would be identical to optimizing a linear-activation network. However, additional cone constraint on V allows for more complex representation, which demonstrates that even in the spike-free case, Rel.u-activation network is quite different from linear-activation network.
Recalling that whitened data matrices where n I are spike-free, for a further simplified class of data and label matrices, we can find closed-form expression for the optimal weights.
Theorem Consider whitened data matrix X E goxd where n < d, and labels Y with SVD of Y = Σi= a.a.b. If the left-singular vectors of X Y satisfy Xa; 2 0 E {i: a; > 8). there exists flomed-form solution for the optimal V to problem (T) given by
Σ (a. abb
(16)

---

Published as a conference paper at ICLR 2021
The resulting model is soft-thresolded SVD of X x Y, which arises the solution of maximum- margin matrix factorization (Srebro et al. 2005). The scenario that all the left singular vectors of X Y satisfy the affine constraints Xa; 0 vi occurs when the all of the left singular vectors Y are nonnegative, which is the case for example when Y is a one-hot-encoded matrix. In this scenario where the left-singular vectors of X Y satisfy Xa; Vi E {i: 0; > 8). note that the ReL.U constraint on V is not active, and therefore, the solution of the ReLU-activvtion network training problem is identical that of the linear-activation network. This linear-activation setting has been well-studied, such as in matrix factorization models by (Cabral et al. 2013) Li et al. 2017). and in the context of implicit bias of dropout (Mianjy et al., 2018] Mianjy & Arora 2019). This theorem thus provides a setting in which ReLU-activation and linear-activation networks perform identically.
4 NEURAL NETWORKS AND COPOSITIVE PROGRAMS
4.1 AN EQUIVALENT COPOSITIVE PROGRAM
We now present an alternative representation of the neural network training problem with squared loss, which has ties to copositive programming.
Theorem For all O, the neural network training problem has a convex strong dual, given
by
tr Y 1 Σ (D.X)U
P
P B22
p¹ p²=
min
Σ tr(U,)
(17)
U,EC, vie[M]
for convex sets C, given by
c= covv (2D; I)Xu 20}
(18)
This is a minimization problem with a convex objective over P sets of convex, completely positive cones-a copositive program, which is NP-hard. There exists cutting plane algorithm solves this problem in Onn"), which is polynomial n for data matrices of rank r (see Appendix A.5). This formulation provides framework for viewing ReLU neural networks implicit copositive pro- grams, and we can find conditions during which certain relaxations can provide optimal solutions.
4.2 COPOSITIVE RELAXATION
We consider the copositive relaxation of the sets C, from 17 We denote this set
:= (U U 0, (2D; TXXUX (2D; - T) 2 0)
In general, C, S č, with equality when < (Kogan & Berman 1993 define the relaxed program
Dickinson
2013). We
P dep = min 1 tr Y ( "r)) U,EC, WE(M
P
+ 8 Σ tr(U.)
(19)
E=1
1=1
Because of the enumeration over sign-patterns, this relaxed program still has complexity of O(n")
to solve, and thus does not improve upon the asymptotic complexity presented in Section 3.
4.3 SPIKE-FREE DATA MATRICES
If X restricted be spike-free, the convex program 19 becomes
(1+2XUXT) "r) "x) + +BBrT(U))
dGp = min UzO XUX 20
- tr
(20)
With spike-free free data matrices, the copositive relaxation presents a heuristic algorithm for the neural network training problem which is polynomial in both and d. This contrasts with the exact for- mulations of (12) and (17). for which the neural network training problem is exponential even for a spike-free X. Table summarizes the complexities of the neural network training problem.
7

---

Published as a conference paper at ICLR 2021
Table I: Complexity of global optimization for two-layer ReLU networks with scalar and vector outputs. Best known upper-bounds are shown where is the number of samples, d is the dimension of the samples and is the rank of the training data, Note that for convolutional networks, r the size of single filter, e.g., a convolutional layer with kernll size of 3 3 corresponds to = 9.
Scalar-output
Vector-output (exact)
Vector-output (relaxation)
Spike-free X
(ndd))
((n")
Onndtt
General X
((())3)
((n"())²r
(((5)))
5 EXPERIMENTS
5.1 DOES SGD ALWAYS FIND THE GLOBAL OPTIMUM FOR NEURAL NETWORKS?
While SGD applied to the non-convex neural network training objective is heuristic which works quite well in many cases, there may exist pathological cases where SGD fails to find the global minimum. Using Algorithm I, we can now verify whether SGD find the global optimum. In this experiment, we present one such case where SGD has trouble finding the optimal solution in certain circumstances. In particular, we generate random inputs X E IR 25x where the elements of X are drawn from an i.i.d standard Gaussian distribution: Xij N0 1). We then randomly initialize a data-generator neural network with 100 hidden neurons and and an output dimension of 5, and generate labels Y f(x) 225x5 using this model. We then attempt to fit these labels using neural network and squared loss, with 3 = 10 ?. We compare the results of training this network for 5 trials with 10 and 50 neurons to the global optimum found by Algorithm 1. In this cireumstance, with 10 neurons, none of the realizations of SGD converge to the global optimum as found by Algorithm 1, but with 50 neurons, the loss is nearly identical to that found by Algorithm 1.
0.20
0020
SGD,
Trial
Trid2
Triat
0019
0019
Trisl
SCD. Trul
5GO Triul
Optimal solution (Algorttim
Optimal solution (Aigonthmm 13
0027
0017
0816
0016
0035
0015
(a) 10 neurons
(b) 50 neurons
Figure 1: As the number of neurons increases, the solution of SGD approaches the optimal value.
5.2 MAXIMUM-MARGI MATRIX FACTORIZATION
In this section, we evaluate the performance of the soft-thresholded SVD closed-form solution pre- sented in Theorem 2. order to evaluate this method, we take a subset of 3000 points from the CIFAR-10 and CIFAR- 100 datasets (Krizhevsky et al.] 2009). For each dataset, we first me-mean the data matrix X E TR 3000x3372 then whiten the data-matrix using ZCA whitening. We seek to fit one-hot-encoded labels representing the class labels from these datasets. In Fig. 2 we observe that the soft-thresholde SVD method from Theorem 2 finds the same solution as SGD in far shorter time. Appendix 1.1.4 contains further details of this experiment.
5.3 EFFECTIVENESS OF THE COPOSITIVE PROGRAM
In this section, we compare the objective values obtained by SGD, Algorithm 1, and the copositive program defined in (17). We use an infficiillly-generate spiral dataset, with X E R00x2 and
8

---

Published as a conference paper at ICLR 2021
2015
200
2004
3015
2425
300
JICE
Trasz bo)
(a) CIFAR-10
(b) CIFAR-
Figure 2: The maximum-matee SVD from Theorem provides the closed-form solution for the optimal value of the neural network training problem for whitened CIFAR-IN 10 and CIFAR-100.
classes (see Fig. a) for illustration). In this case, since d S 4, note that the copositive relaxation in (19 is tight. Across different values of 8, we compare the solutions found by these three methods. As shown in Fig. the copositive relaxation, the solution found by SGD, and the solution found by Algorithm all coincide with the same loss across various values of B. This verifies our theoretical proofs of equivalence of
and
Algonthm
Non convex SGD solution Copcatiive relasation
22
10
10
10 bota
10
10*
(a) 3-class Spiral Dataset
Loss across
3
Figure 3: Spiral classification: SGD (1000 neurons), Algorithm 1, and copositive relaxation
19
6 CONCLUSION
We studied the vector-output ReLU neural network training problem, and designed the first algo- rithms for finding the global optimum this problem, which are polynomial-time the number of samples for fixed data rank. We found novel connections between this vector-output ReI.U neu- ral network problem and a variety other problems, including semi-NMF, cone-constrained PCA, soft-thresholded SVD, and copositive programming. Of particular interest is extending these results to deeper networks, which would further explain the performance of neural networks as they are often used in practice. One such method to extend the results in this paper to deeper networks is to greedily train and stack two-layer networks to create one deeper network, which has shown to mimic the performance deep networks trained end-to-end. Some preliminary results for convex program equivalents of deeper training problems are presented under whitened input data assumptions in (Er- gen & Pilanci 2020c). Another interesting research direction investigating efficient relaxations of our vector output convex programs for larger scale simulations, which have been studied in (Bartan Pilanci 2019: Ergen & Pilancil 201 9b a d' Aspremont & Pilanci| 2020). Furthermore, landscapes of vector output neural networks and dynamics of gradient descent type methods can be analyzed by leveraging our results. In (Lacotte & Pilanci] 2020), an analysis of the landscape for scalar output given which establishes direct mapping between
networks based on the convex formulation the non-convex and convex objective landscapes. Finally, our copositive programming and semi- NMF representations of ReLU networks can be used develop more interpretable neural models. An investigation of scalar output convex neural models for neural image reconstruction was given in (Sahiner al. 2020).

---

Published as a conference paper at ICLR 2021
ACKNOWLEDGEMENTS
This work was partially supported by the National Science Foundation under grants IIS- 1838179 and ECCS-2037300 the National Institutes of Health under grants RO1EB009690 and ROIEBO026136 Facebook Research, Adobe Research and Stanford SystemX Alliance.
REFERENCES
Jacob Abernethy, Francis Bach, Theodoros Evgeniou, and Jean-Philippe Vert. A new approach to collaborative filtering: Operator estimation with spectral regularization. Journal of Machine Learning Research, 10(3), 2009.
Miguel F Anjos and Jean B Lasserre. Handbook on semidefinite, conic and polynomial optimization, volume 166. Springer Science & Business Media, 2011.
Andreas Argyriou, Theodoros Evgeniou, and Massimiliano Pontil. Convex multi-task feature learn- ing. Machine learning, 73(3):243-272, 2008.
Sanjeev Arora, Simon $ Du, Wei Hu, Zhiyuan Li, Russ Salakhutdinov, and Ruosong Wang. On exact computation with infinitely wide neural net. In Advances in Neural Information Processing Systems, pp. 8141-8150, 2019.
Megasthenis Asteris, Dimitris Papailiopoulos, and Alexandros Dimakis. Nonnegative sparse pea with provable guarantees. In International Conference on Machine Learning, pp. 1728-1736, 2014.
Burak Bartan and Mert Pilanci. Convex relaxations of convolutional neural nets. In ICASSP 2019- 2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp- 4928 4932. IEEE, 2019.
Eugene Belilovsky, Michael Eickenberg, and Edouard Oyallon. Greedy layerwise learning can scale to imagenet. In International conference on machine learning, pp. 583-593. PMLR, 2019.
Jonathan Borwein and Adrian S Lewis. Convex analysis and nonlinear optimization: theory and examples. Springer Science Business Media, 2010.
Alon Brutzkus and Amir Globerson. Globally optimal gradient descent for convnet with gaussian inputs. arXiv preprint arXiv: 17Xh::170..07666, 2017.
Samuel Burer. A gentle, geometric introduction copositive optimization. Matherattial Program- ming, 151(1):89-16, 2015.
Ricardo Cabral, Fernando De la Torre, João P Costeira, and Alexandre Bernardino. Unifying nuclear norm and bilinear factorization approaches for low-rank matrix decomposition. In Proceedings of the IEEE International Conference Computer Vision, pp. 2488-2495, 2013.
Emmanuel J Candès and Terence Tao. The power of convex relaxation: Near-optimal matrix com- pletion. IEFE Transactions on Information Theory, 56(5):2053-2080, 2010.
Alexandre d' Aspremont and Mert Pilanci. Global convergence of frank wolfe on one hidden layer networks. arXiv preprini 20i::2002.002008 2020.
Yash Deshpande, Andrea Montanari, and Emile Richard. Cone-constrained principal component analysis. In Advances in Neural Information Processing Systems, pp. 2717-2725, 2014.
Steven Diamond and Stephen Boyd. Cvxpy: A python-embedded modeling language for convex optimization. The Journal of Machine Learning Research, 17(1):299-22913 291,, 2016.
Peter JC Dickinson. The copositive cone, the completely positive cone and their generalisations. Citeseer, 2013.
Chris HQ Ding, Tao Li, and Michael Jordan. Convex and semi- semi-nonnegative matrix factorizations. 2008
IEEE transactions on pattern analysis and machine intelligence,
10

---

Published as a conference paper at ICLR 2021
Mirjam Dür. Copositive programming survey. In Recent advances in optimization and its appli-
cations in engineering, pp. 3-20. Springer, 2010.
Tolga Ergen and Mert Pilanci. Convex duality and cutting plane methods for over-parameterized neural networks. In OPT-ML workshop, 2019a.
Tolga Ergen and Mert Pilanci. Convex optimization for shallow neural networks. 2019 57th Annual Allerton Conference Communication, Control, and Computing (Allerton), pp. 79-83. IEEE, 2019b.
Tolga Ergen and Mert Pilanci. Convex geometry of two-layer relu networks: Implicit autoencoding and interpretable models. In International Conference Artificial Intelligence and Statistics, pp- 4024-4033, PMLR, 2020a.
Tolga Ergen and Mert Pilanci. Convex geometry and duality of over-parameterized neural networks. arXiv preprint arXiv:2002. 1219, 2020b.
Tolga Ergen and Mert Pilanci. Convex duality of deep neural networks. arXiv:2002.09773, 2020c.
arXiv preprint
Tolga Ergen and Mert Pilanci. Training convolutional relu neural networks in polynomial time:
Exact convex optimization formulations. arXiv preprini arXiv:2006. 14798, 2020d.
Marguerite Frank, Philip Wolfe, et al. An algorithm for quadratic programming. Naval research logistics quarterly, 3(1-2)955-100, 1956.
Rong Ge, Rohith Kuditipudi, Zhize Li, and Xiang Wang. Learning two-layer neural networks with symmetrie inputs. arXiv preprint arXiv:1810.06793, 2018
Nicolas Gillis and Abhishek Kumar. Exact and heuristic algorithms for semi-nonnegative matrix factorization. SIAM Journal on Matrix Analysis and Applications, 36(4): 1404-14444, 2015.
Aditya Sharad Golatkar, Alessandro Achille, and Stefano Soatto. Time matters in regularizing deep networks: Weight decay and data augmentation affect early learning dynamics, matter little near convergence. In Advances in Neural Information Processing Systems, pp. 10678-10688, 2019.
Edouard Grave, Guillaume Obozinski, and Francis R Bach. Trace lasso: trace norm regu- larization for correlated designs. In Advances in Neural Information Processing Systems, pp- 2187-2195, 2011.
Suriya Gunasekar, Blake E Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro. Implicit regularization in matrix factorization. In Advances in Neural Information Processing Systems, pp. 6151-11666 -6159, 2017.
Trevor Hastie, Rahul Mazumder, Jason D Lee, and Reza Zadeh. Matrix completion and low-rank svd via fast alternating least squares. The Journal of Machine Learning Research, 16(1):3367-3402, 2015.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. In Proceedings of the IEEE international conference on computer vision, pp. 1026 1026-1034, 2015.
Lei Huang, Dawei Yang. Bo Lang, and Jia Deng. Decorrelated batch normalization. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 791-800, 2018.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and gen- cralization in neural networks. Advances in neural information processing systems, pp. 8571- 8580, 2018.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980. 2014.
Natalia Kogan and Abraham Berman. Characterization of completely positive graphs. Discrete Mathematies, 1 (1((1-3):27-3004 1993.
11

---

Published as a conference paper at ICLR 2021
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Jonathan Lacotte and Mert Pilanci. All local minima are global for two-layer relu neural networks: The hidden convex optimization landscape. arXiv preprini arXiv:2006.0533 05900, 2020.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11) (0(11):227-2233 1998.
Qiuwei Li. Zhihui Zhu, and Gongguo Tang. Geometry of factored nuclear norm regularization.
arXiv preprint arXiv:170..0126. 2017.
Poorya Mianjy and Raman Arora. On dropout and nuclear norm regularization. arXiv preprint arXiv:1905: 1887, 2019.
Poorya Mianjy, Raman Arora, and Rene Vidal. On the implicit bias of dropout. arXiv preprint arXiv:/806.09777, 2018.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. In search of the real inductive bias: On the role of implicit regularization deep learning. arXiv preprint arXiv:1412.6614. 2014.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high- performance deep learning library. arXiv preprint arXiv: 2019.
Mert Pilanci and Tolga Ergen. Neural networks are convex regularizers: Exact polynomial-tmme con- vex optimization formulations for two-layer networks. arXiv preprint arXiv:2002. 10553, 2020.
Benjamin Recht, Maryam Fazel, and Pablo Parrilo. Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM review, 52(3):471-501, 2010.
Arda Sahiner, Morteza Mardani, Batu Ozturkler, Mert Pilanci, and John Pauly. Convex regulariza- tion behind neural reconstruction. arXiv preprint 2rX:v:2012.05116, 2020.
Pedro Savarese, Itay Evron, Daniel Soudry, and Nathan Srebro. How do infinite width bounded norm networks look function space? arXiv preprint arXiv: 190.00500 2019.
Alexander Shapiro. Semi-infinite programming, duality, discretization and optimality conditions. Optimization, 58(2):133-161 2009.
Nathan Srebro, Jason Rennie, and Tommi S Jaakkola. Maximum-margee matrix factorization. In Advances in neural information processing systems, pp. 1329-1336, 2005.
Richard P Stanley et al. An introduction to hyperplane arrangements. Geometric combinatorics, 13: 389-496, 2004.
12

---

Published as a conference paper at ICLR 2021
A APPENDIX
A.1 ADDITIONAL EXPERIMENTAL DETAILS
All neural networks in the experiments were trained using the Pytorch deep learning library (Paszke et al. 2019), using single NVIDIA GeForce GTX 1080 Ti GPU. Algorithm was trained using CPU with 256 GB of RAM, was the maximum margin matrix factorization. Unless otherwise stated, the Frank-Wold method from Algorithm used step size of ( 2+ and all methods trained minimize squared loss.
Unless otherwise stated, the neural networks were trained until full training loss convergence with SGD with momentum parameter of 0.95 and a batch size the size of the training set (i.e. full-batch gradient descent), and the learning rate was decremented by factor of whenever the training loss reached plateau. The imitial learning rate was set as high as possible without causing the training to diverge. All neural networks were initialized with Kaiming uniform initialization (He et al. 2015).
A.1.1 ADDITIONAL EXPERIMENT: COPOSITIVE RELAXATION WHEEN 2 4
The copositive relaxation for the neural network training problem described in (99 is not guaran- teed to exactly correspond the objective when d 2 4. However, we find that in practice, this relaxation is tight even in such settings. To demonstrate such an instance, we consider the problem of generating images from noise.
In particular, we initialize X element-wise from an i.id standard Gaussian distribution. To analyze the spike-free setting, we whitened X using ZCA whitening. Then, we attempted to fit images Y from the MNIST handwritten digits dataset (LeCun et al. 1998) and CIFAR-10 10 dataset (Krihevskyy et al.] 2009) respectively. From each dataset, we select 100 random images with 10 samples from each class and flatten them into vectors, to form YMNIST E 1000784 and YCIFAR x000x3072, We allow the noise inputs to have the in these cases, with d = 784 and d 3072 respectively, the copositive relaxation 20 is not guaranteed correspond exactly to the neural network training optimum.
shape the output. Clearly,
However, we find across variety of regularization parameters B, that the solution found by SGD and this copositive relaxation exactly correspond, as demonstrated in Figure
MAST generation
CITAR-10 image generation
Capesstive relexation
Copositive relecation Nancomves 5GD solution
Noncorvex SGD solutin
30a
38
3019
30a
201
10P
10a
10t1
22a
X01
barta
bata
(a) MNIST
(b) CIFAR-10
Figure 4: The copositive relaxation all B.
20 and solution found by SGD nearly correspond for almost
While for the lowest value of 3, the copositive relaxation does not exactly correspond with the value obtained by SGD, we note that we showed the objective value of the copositive relaxation to be lower bound of the neural network training objective-meaning that the differences seen in this plot are likely due to a numerical optimization issue, rather than a fundamental one. Non-convex SGD trained for 60,000 epochs with 1000 neurons with a learning rate of 5 x 10-5, while the copositive relaxation was trained using Adam (Kingma Ba, (014) with the Geotorch library for constrained optimization and manifold optimization for deep learning in PyTorch, which allowed us
13

---

Published as a conference paper at ICLR 2021
to express the PSD constraint, with additional hinge loss penalize the violations of the affine constraints. This copositive relaxation was trained for 60,000 epochs with a learning rate 10-2 for CIFAR-10 and 4 x 10 2 for MNIST, and 31 0.9, $2 0.999 and 10 parameters for Adam.
A.1.2 ADDITIONAL. EXPERIMENT: COMPARING RELU ACTIVATION TO LINEAR ACTIVATION IN THE CASE OF SPIKE-FREE MATRICES
ReLU network
X
ReLU network
10
Linear network
Linear network
Test Loss
10
x 10
X
10
10
3
2
X
10>
10
10
1011
10
101
10a
10-a
10
10
10
10
10a
beta
beta
(a) Train Loss across 8
(b) Test Loss across
B
Figure 5: Comparing train and test accuracy of linear and ReLU two-layer networks on generated continuous labels CIFAR-10. We note that for 3 > 1.0, the optimal solution for both networks to simply set all weights to zero. The best-case test loss for the ReLU network nearly half the best-case test loss for the linear network.
As discussed in Section 3.3., if the data matrix X is spike-free, the resulting convex ReLU model (15) is similar to a linear-activation network, with the only difference being an additional cone constraint on the weight matrix V. It stands to wonder whether in the case of spike-free data matrices, the use of a ReLU network is necessary at all, and whether a activaatio network would perform equally well.
In this experiment, compare the performance of ReL.U-activation network to linear- activation onc, and demonstrate that even in the spike-free case, there exist instances in which the ReLU-activation network would be preferred. In particular, meaned and ZCh-whitened images from the CIFAR-10 10 dataset to form our spike-free free training data X E 3070 We then generate continuous labels E 3:000x from randomly-initialzz ReLU two-layer network with 4000 hidden units. We use this same label-generating neural network to generate labels images from the full 10,000-sample test set of CIFAR-10 as well, after the test images are pre-processed with the same whitening transformation used on the training data.
take our training data 3000 de-
Across different values of 3, measured the training and generalization performance of both ReL.U-activation and linear-activation two-layer neural networks trained with SGD on this dataset. Both networks used 4000 hidden units, and were trained for 400 epochs with learning rate of 10-2 and momentum of 0.95. Our results are displayed in Figure
As we can see, for all values of 3, while the linear-activation network has equal or lesser training loss than the ReLU-activation network, the ReLU-activation network generalizes sig- nificantly better, achieving orders of magnitude better test loss. We should note that for values of 1.0 and above, both networks learn the zero network (i.e. all weights at optimum are zero), so both their training and test loss are identical to each other. We can also observe that the best-case test loss for the linear-activation network to simply learn the zero network, whereas for value of 3 10-2 the ReLU-activation network can learn to generalize better than the zero network (achieving a test loss 63038, compared to a test loss of 125383 of the zero-network).
These results demonstrate that even for spike-free data matrices, there are reasons to prefer Rel.U-activation network linear-activation network. In particular, because of the cone-
14

---

Published as a conference paper at ICLR 2021
constraint the dual weights V. the ReLU network is induced to learn more complex representation than the linear network, which would explain its better generalization performance.
The CIFAR-10 dataset consists of 50,000 training images and 10,000 test images of 32 x 32 for 3 RGB channels, with 10 classes (Krizhevsky et al.) 2009). These images the per-channel training set mean and standard deviation. To form our training set, selected 3,000 training images from these datasets at random, where each class was equally represented. This data was then Peature-wise de-meaned and transformed using ZCA. This same training class mean and ZCA transformation was also then used on the 10,000 testing points for evaluation.
normalized by
A.1.3 DOES SGD ALWAYS FIND THE GLOBAL OPTIMUM FOR NEURAL NETWORKS?
For these experiments, SGD was trained with an initial learning rate of x 10-5 for 20,000 epochs. We used a regularization penalty value of 3 10 The value for for Algorithm
found by first starting at the value of regularization penalty 2 2_1 ||u, 12 + |0 l1 from the solution from SGD, then refining this value using manual tuning. A final value of / = 1.495 was chosen. For this experiment, there were 50 sign patterns. Algorithm X seconds to solve.
run for 30,000 iterations, and took
A.1.4 MAXIMUM-MARGIN MATRIX FACTORIZATION
The CIFAR-10 and CIFAR- 100 datasets consist of 50,000 training images and 10,000 test images of 32 x 32 for 3 RGB channels, with 10 and 100 classes respectively (Krizhevsky et al. 2009). These images were normalized by the per-channel training set mean and standard deviation. To form our training set, selected 3,000 training images from these datasets at random, where each class was equally represented. This data then feature-wist de-meaned and transformed using ZCA. This same training class mean and ZCA transformation was also then used on the 10,000 testing points for evaluation. For CIFAR-IO, we used regularization parameter value of 3 1.0, whereas for CIFAR-100 100, we used a value of β = 5.0.
SGD was trained for 400 epochs with learning rate of 10-2 with 1000 neurons, trained with one-hot encoded labels and squared loss. Figure 6 displays the test accuracy the learned networks. Surprisingly the whitened classification from only 3, 3,000 images generalizes quite well in both circumstances, far exceeding performance of the null classifier. For the CIFAR- 10 experiments, the algorithm from Theorem 2 took only 0.018 seconds to solve, whereas for CIFAR-100 it took 0.36 seconds to solve.
0.40
0.34
(Thm
033
Test Accurecy
0.30
0.34
0.66
033
022
030
10
20
50
50
Time
Time
(a) 10
(b) CIFAR-108
Figure 6: Test accuracy for maximum- maximum-margin matrix factorization and SGD for whitened CIFAR-10 and CIFAR-100.
A.1.5 EFFECTIVENESS THE COPOSITIVE PROGRAM
For this classification problem, we use one-hot encoded labels and squared loss. For 3 < 1, SGD used learning rate of 10 and otherwise used learning rate of 2 x 10-3, SGD was trained for 8,000 epochs with 1000 neurons, while Algorithm I ran for 1,000 iterations. The copositive relaxation was optimized with CVXPY with first-order solver CPU with 256 GB of RAM
15

---

Published as a conference paper at ICLR 2021
Diamond & Boyd 2016). The first-order convex solver for the copositive relaxation used maxi- mum of 20,000 iterations. This dataset had P = 114 sign patterns. The value for Algorithm
was chosen as the regularization penalty 2 Eド=1 | 11 +
|| 11 from the solution of SGD.
A.2 NOTE ON DATA MATRICES OF A FIXED RANK
Consider the neural network training problem
3 2
Σ ( - YIF My.
min
|uy |00
(21)
Let = TDV be the compact SVD of X with rank r, where R D R and V E Rdxr. Let u V uj and u V1 Uj. We note that Xu, XVu, and ||,l
u (VVT V1 Uj = | + || 112. Then, we can re-parameterize the problem as
m Σ j=1
m Σ
min "J 14 My
2
(XVu)) YI +
|
1
(22)
We note that u+ only appears in the regularization term. Minimizing over u thus means simply setting to O. Then, we have
1
min ug.0g 2
Σ 1 (XVu))+o) Y + 2
(23)
We note that XV UD Raxr and u/j R", Thus, for X of rank r, can effectively reduce the dimension of the neural network training problem without loss of generality. This thus holds for all results concerning the complexity of the neural network training problem with data matrices of fixed rank.
A.3 PROOFS
A.3.1 PROOF OF THEOREM
We begin with the primal problem 5 repeated here for convenience:
min ER vy ERS
Σ [
r
3 2
(Iu5 + ||us1
(24)
We start by re-scaling the weights in order to obtain slightly different, equivalent objective, which has been performed previously in (Pilanci & Ergen 2020: Savarese et al., 2019)
Lemma 4 The primal problem is equivalent to the following optimization problem
p"
min ||u,llaS1
min ER 2
1
Σ (uu)++J
m
Y
3
(25)
Proof:
Note that for any 7 > O, we can re-scale the parameters ú, = 7i Ujj új = 0//3,. Noting that the network output is unchanged by this re-scaling scheme, we have the equivalent problem
3 Σ
p" min min Σ
(Xu))++
YI
(7 1 111,,
11,,11/133)
(26)
u 7> ERE
2
Minimizing with respect to Yj. thus end up with
8
p" = min
Σ (xu,) - 12:
Σ
(1u,lallo;)12)
(27)
ERER ERC
2
j=1
j=1
16

---

Published as a conference paper at ICLR 2021
We can thus set ||2y|22 1 without loss of generality. Further, relaxing this constraint |/ does not change the optimal solution. In particular, for the problem
TR Σ (Xu))+00 Y + 3 j=1
m
min min eyeRe
0 12
(28)
the constraint ||ull22 1 will be active for all non-zero Vy. Thus, relaxing the constraint will not change the objective. This proves the Lemma.
Now, we are ready to prove the first part of Theorem 1, i.e. the equivalence to the semi-infinite program (17).
Lemma For all B 0 primal neural network training problem 25 has strong dual, in the form of
1 2
p" d"
max (Xu)+
1
2 + 1
(29)
2:
2
VI
Proof: We first form the Lagrangian of the primal problem, by firs-reparameterizing the problem
as
min min lusllas R R2
R + B 5=1
||0 12 s.t. R
Σ
(Xu)) -Y
(30)
j=1
and then forming the Lagrangian as
min min max الااام uy
R
B
luylla +
2
Y
+
Z R T
[(uu))+0
(31)
By Sion's minimax theorem, we can switch the inner maximum and minimum, and minimize over by and R. This produces the following problem:
min 21
max (Xu) 18
1 2
2 - Y
YY
(32)
We then simply need to interchange max and min to obtain the desired form. Note that this inter- change does not change the objective value due to semi-infinite strong duality. In particular, for any O, this problem is strictly feasible (simply let Z 0) and the objective value is bounded by Then, by Theorem 2.2 (Shapiro 2009), we know that strong duality holds, and
p¹ ==
max
- 12 2
1
+ Y
(33)
2: 1 1 1
as desired.
Furthermore, by (Shapiro 2009), for a signed measure we obtain the following strong dual of the dual program (TI:
1 1
I / S (IZ (x (3) du(u) (34)
d'
max min #Z0 ZERoXd
where Bg defines the unit ball By discretization arguments in Section of (Shapiro 2009). and by Helly's theorem, there exists some m < nc 1 such that this is equivalent to
d' = max min #20 ZEREXA M 1
- - 1
1
1
|
m
(Xu;)+ - -3)-3)))) B)Rs (35) z
Minimizing with respect to Z. we obtain
min min min || 1 a20
Σ
n
- -113 + Σ
#4
(36)
11g1
i=1
1=1
17

---

Published as a conference paper at ICLR 2021
which we can minimize with respect μ to obtain the finite parameterization
m Σ (xu)++g) M 1 9:
m Σ gill2
min
min
X12
(37)
This proves that the semi-infinite dual provides a finite support with at most mn S CCC+ non-zero neurons. Thus, if the number of neurons of the primal problem 2 m", strong duality holds. Now, we seek to show the second part of Theorem 1, namely the equivalence to 12) Starting from have that the dual constraint is given by
max |
| (Xu)+ +112 $
(38)
Using the concept of dual norm, we can introduce variable to further re-express this constraint as
max g TTT S 1
(39)
Then, enumerating over sign patterns (Dill have
max EE[P]
max fulaa11
- D, $
(40)
1 S1 (2D, u2x20
Now, we express this in terms of an inner product.
max PE[
D.X ug )) 8
(41)
(2D.-1) X
|
g 251
Letting V = ug" :
max iE(
(xV) SB
(42)
V ug
(2D: Nu220
V L-s
Now, we can take the convex hull of the constraint set, noting that since the objective is affine, this does not change the objective value.
max P
(Z,DXVV) 3B
(43)
VeR
IVIS1
Thus, the dual problem is given by
p" = d' = max
- 2 - Y 1 + 1
2
(44)
s.t. maxx
(2, s E
V.EK:
VVIl.51
We now form the Lagrangian,
p² d' max min
min
- 2
1 +
(B,
(45)
Z X20 ViEk; WiE[P]
We note that by Sion's minimax theorem, we can switch the max and min, and then minimize over
Z. Following this, we obtain
p" d'
min min V.eR. Vie[P] X20 2
Σ ADX YI + Σ A
(46)
1=1
18

---

Published as a conference paper at ICLR 2021
We can re-scale our variables to obtain
P D YI + Σ X
P
p d'
min ViEK Viel]] A20 2 |I
min
Σ
(47)
i=1
1=1
And now minimize over to obtain the desired result:
P ViER WEE(P 2 Σ D,X, - Y + Σ |ill-
p- = =d=
min
(48)
Remark 5.1 Given the optimal solution (22, is natural wonder how these dual variables relate to the optimal neurons of the neural network training problem (5). Given an optimal {V;").= we
simply need to factor them into V = = Gi wwere (2D, I) 2 0. This is similar in flavor to semi-NMF. Since V is in the cone K,,, exact semi-NMF factorization can be performed in polynomial time (Gillis & Kumar 2015). Once this factorization obtained, assuming without loss of generality that Dis = 1, the optimal neurons are given by
h
9iy i [P]. [c]
(49)
Thus, given a solution to [2). a polynomial-time algorithm exists for reconstructing weights of the original neural network training algorithm.
A.3.2 A COROLLARY FOR CNNS WITH AVERAGE POOLING
We first introduce additional notation for CNNs with average pooling, In particular, following Ergen Pilanci (2020d), we use the set patch matrices {X to define new data matrix as M
[X1, X2,
Xx k E RRR where h is the convolutional filter size. This matrix thus has set of
sign patterns, which we define as
Te -1)
Pconu S 2r
where = rank(M) S h. We then can enumerate the set of patch matrices
(D) ii [Pconu]: k E [K]
Corollary 5.1 the case of a two-layer CNN with global average pooling as in 6 the strong dual of the neural network training problem
Perno
min
ΣΣ
X YI + Vill
Σ
(50)
V.ek, ViE[P]
for convex sets Kr, given by
Kr (ug (2D) I)X 2 0 Vk: |[ < 11}
(51)
This strong dual is convex. For a fixed kernel-size. and r. are fixed, and the problem is polynomial in n, i.c. of complexity proportional O(n*)). Since in practice, M is tall matrix with relatively few columns,
almost always full-rank, in which case the computational complexity of solving the strong dual is O(n²). This problem can be solved with the same Frank- Wolfe algorithm as presented in Algorithm
A.3.3 PROOF OF THEOREM? 2
We note that whitened data matrices such that < d satisfy X I. Then, solve the modified problem
min || X T + VI|
(52)
Veconv(ugg -x200.lg (ellllll
19

---

Published as a conference paper at ICLR 2021
This is simply by noting that left- left-muliipyyngg by X does not change the norm. Now, note that
Veconv (ug min x 2 VV- + 2
min Veconv = 2
-
The relaxed problem on the right-hand side given exactly by maximum moxiiuu-marggin matrix factoriza- tion (Srebro et al. 2005), i.e. can be expressed
min V=Σ== u:g
I
I - x X V|I
Furthermore, this has a closed-form solution, given by soft coft-hhresoolding the singular values of Y (Hastie et al. 2013). Thus, we have the solution of the relaxed problem
V Σ 0. - 3) a.,b E11
Noting that Xa; 2 0 for all i E (i o; B:) by assumption, this solution is feasible for the original problem. Thus, because the optimal value obtained by the solution to the relaxed problem was a lower bound to 415). it must be the optimal solution to (15).
Remark 5.2 It is interesting to note that when Y one-hot encoded,
X [m())(()) ((2))((2)
T(c))(e)
(53)
where ((() refers to the number of instances in class i, and p() refers to the mean of all data points belonging class i. In this scenario, then, the optimal neural network weights, V*, are found via the maximum-man margin factorization of this matrix.
Further, if YY is element-wise non non-negative, by Perron-Froud Frobenius theorem, its maximal left singular non-negative. For such data matrices, if 8 is chosen be larger than the second largest singular value of Y, the solution T6 is guaranteed to be exact.
A.3.4
PROOF OF THEOREM 3
Start with
p² = d" = max 2 =1 - Y + Y
(54)
s.t 1 (Xu)+ S 1//121// $
We can express this as
2 - 1 + 1 Y -
p= = d" = max 2
(55)
s.t max 1 (Xu) + 11 S 32
||
Enumerating over all possible sign patterns tr Z L D'uuu' T x xDDI)), we have
i E [P]. and noting that 2 12 D.Xull
p" = d' = max 7 11 2- --1 + 1 1
tr Z D,Xum T x D:Z) < 3²
(56)
S.t
(E(
(2D.- Xux20
Noting the maximization constraint is linear in un." T we can take the convex hull of the constraint and not change the optimal value. Thus,
- Z ---11 + 1
1
p¹ = d" max Z
2
tr D.XUX D.Z) 882
(57)
max (E[P] UEC, tr(U)S1
20

---

Published as a conference paper at ICLR 2021
Which is then equivalent to
p³ = max 2 - - Y + 2 1
(58)
tr tr(Z Z D D.Z) < E
s.t U.EC, tr(UUS1
max
We thus have a problem with convex objective and P constraints, so we can take the Lagrangian
p= d' max 2
min U,EC, PI
- 1I
Σ ==1
No 82 - DiXU,X D.Z)
tr( A20
(59)
Noting that this function convex over Z, affine over X, and concave over U; and the constraint set is convex, by Sion's 's minimax theorem we can change max and min without changing the objective.
Thus,
p' d'
min U,eC, We( Z tr(U.){1 X20
max
|
F
YIF
Σ No
82 3-tr
-tr(tzz DD D.Z))
(60)
Solving for Z and re-substituring, we thus have
Y II [+2 (1+ (DDX)UU(D) -1
p¹ d'
min EC
tr
x
3 X
(61)
2
X20
as in the proof of Theorem 1, we easily re-scale this to obtain the desired objective:
p' d min U. vie(P) 2 tr Y (I+2 (T(+22
ED.X,,))
+ 3 Σ
tr(U,)
(62)
i=
A.4 NOTES ON THE FRANK-WOLDD METHOD APPLIED TO 122
A.4.1 DERIVATION THE FRANK-WOLFE ALGORITHM
In general, the Frank Wolfe algorithm Frank et al. 1956 aims to solve the problem
min f(x) s.t. e
(63)
for some convex function / and convex set D. It does so the following iterative steps 1, K with step sizes (k) and initial point (1)
1. (LMO step) Solve the problem
m (1) == arg min V fz
(64)
RED
2. (Update step) Update the decision variable
z (A+1) (1 - a (z)) (1) m (k)
(65)
We will now apply the Frank- problem to the inner minimization of 14
i.e., for a fixed value
of I, solving
P Σ
min V.E,, WE[[P] 2 ΣP, [IVI] St 1=1
D.V,,
Y + 3t
(66)
21

---

Published as a conference paper at ICLR 2021
In partieular the LMO step becomes:
P
P S (DiX)
( (ED;
{M, 11 = arg
mim
(67)
s,ek, (iE
E ||
Σ {(DiXs, Σ S1
DIXS, DD ( - -Y) r)
arg min S, WEE[
(68)
Note that the objective value in the optimization problem of the LMO step is affine with respect to the variables S. Thus, the optimal value occurs at extreme point of the feasible set. Thus, only one of [M: is active at optimum at index = i", and moreover this M,- occurs at an extreme point of K,,,, i.e M,- R₁. All other Mj where o i are zero at optimum. Thus, we can re-write this problem as
P D,XS, DD r)
M,- arg min iElP SeK, ||S| St
(69)
j=1
Recalling that K, = conv(ug" (2D; I) 2 0, 1gl12 S 1] boundary of K2 is simple to express, leaving with M,- u. g,., where
D,Xug T Σ D, Dv - ==1
(u:: gi-) arg
min iE( (2D
(70)
T)X X220
g g St
Note that we can change the constraint ||u|22 to ||l|2 and simply multiply by factor of to the solution afterwards. We can thus write the key Frank-War Wolfe LMO step subproblem as
(D.Xug) Y D, 19)
(9+)))====
max SE[P! (
(71)
j=1
g
||
as desired, For each E [P], we thus solve the problem
P (D.Xug' T Y DD
(b)
8,
max (2D.
(72)
Xuu
g 1151
1=l
and store the arg maxes (u;, gi) for each i. Then, from the index which attains the maximum
i" := arg max; s; (k) Then, we must re-multiply by the factor i which was removed 7T to obtain the update rule for all i [P]:
form M (k) uu V.-g.. For all other + i", stated previously, M 0.
((++)) a to (+)
A.4.2 SOLVING EACH FRANK-WOLFE ITERATE
We discuss here how to solve the subproblem
P (D,Xug Y. Y - (1)
(k)
8
max u 1
1 <1
1=1
(2.:
X)x20
22

---

Published as a conference paper at ICLR 2021
using cone- cone-constr PCA. In particular, note that for fixed u, solve for in closed form.
Let R(() Σ j=1 D, D.XV(
(b) Then, we have
R(K) D
g (u)
| D,Xulla
Then, re-substituting this back into the objective, we have
(4)
[ D.Xull2 =
u T (D,X) (ID.))RR(OPE R (D,X)u
max $1
max 1
X)2-
(2D. 22D.-1)Xu20
Without loss of generality, we can square the objective, since objective only takes on non-negative values. The LMO step of the Frank-Won algorithm is thus identical to the cone-constrained PCA problem
(k)2
M (D.X) R R(() (D,X)
max Uala (2D.
This problem, via Lemma of Asteris et al. 2014). can be performed Onn)) time. However, we note that because we can reduce the dimension of the problem to without loss of generality (see Appendix A.2), this thus simplifies to O(n"). We perform P such maximization problems per iteration of Frank-Wolfe.
A.5 A CUTTING PLANE METHOD FOR SOLVING
17
Consider the dual problem
1 Z 2
d'
Y
1
+
1
(73)
s.t max
1 (Xu)+ 5
||
Enumerating over sets of hyperplanes, have
p" = d" max- Z
2 1z - r1? 1
s.t max
2z D:X 5
(74)
iE
(2D: Xuu20
|
We can express the dual constraint as
max P) (2D. Dx
u M,u < 32
(75)
1
where M, = -X D E Bdddd For each i, this is cone-constrained PCA problem in dimension d with n linear incquality constraints. Using Lemma 7 of (Asteris et al. 2014), there exists algorithm which solves the cone-constrained PCA problem in O(n') time. Thus, solving the optimization problem in the dual constraint 77) O(Pn") time. For a fixed rank r, P has order O(n"), but otherwise P is O(n") well. Thus, determining the feasibility of a dual variable Z from 75 has complexity (nzd) in the general case, and Onn") in the rank-r case.
Now, using the Analytic Center Cutting Plane Method (ACCPM), the cone-constrained PCA procedure above provides an oracle for the feasibility of dual variable Z. Using this oracle, ACCPM solves the convex problem (73) in polynomial steps in terms of the dimension of Z, i.c. poly(nc) steps. Thus, the overall complexity of the cutting plane method is One ((n(poly(ne)) in the general case, and (n"" polypolynnn (nc)) in the rank-r case, which is polynomial for fixed
We note that while this is similar in complexity to the results of (Pilanci & Ergen 2020 there are a few subtle differences. In particular, there are additional terms polynomial in e which do not appear in their work. However, the broader picture of the analyses align-for full-rank matrices, solving the convex dual of the neural network training problem is NP-hard, while for matrices of fixed rank, polynomial time algorithm exists.
23

---

Published as a conference paper at ICLR 2021
A.6 EXTENSIONS GENERAL CONVEX LOSS FUNCTIONS
This follows closely from a similar discussion by Pilanci & Eiren 2020). Consider the objective of the neural network training problem with general convex loss function E, given by
8 2
p
min 1
E > 2
(Xu))+v Y)
Σ j=1
(1u) + 10,
(76)
==1
Then, can follow the same proof of Theorem 1 exactly, instead substituting the Fenchel dual of f, defined as
(Z) mmxx (,, Rt - Y)
(77)
Then, we have the dual objective analog of
max
(Z)
(78)
Z: Z (X+)+ S V|jula
We can further elucidate the convex constraint on dual variable Z done in the proof of Theorem 1. Then, we can follow the same steps from this previous proof, noting that by Menchel-Moreau Theorem, e- (Borwein Lewis 2010). Thus, the finiteddmmensional convex strong dual is given by
P ED.VV, x) + Σ IIII 1=1
L 2
p =
min Viek: FiE[P]
(79)
1=1
as desired. We note that the Frank Wolfe method in Algorithm holds for general convex é as well, with small modification corresponding the gradient of the loss function.
24


Reviews:
[{"review_id": "p_3u4RuwAw", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: This paper generalizes the results of Pilanci and Ergen (2020) showing that the non-convex optimization problem corresponding to the training of a one-hidden-layer muti-output ReLU neworks can be solved using convex programming. In particular they show that the problem has (I) a finite convex bidual that can be solved efficiently using some variant of the Frank-Wolfe algorithm and (II) a convex strong dual given by a copositive program. Unfortunately in the general case the complexity is exponential in the rank of the data matrix. A spike-free assumption is introduced that facilitates things and allows polynomial time algorithms, however this assumption is pretty strong and I doubt it is useful in practice as it makes the training 'almost' equivalent to training a linear classifier. Some references are missing as the problem is related to the low-rank matrix factorization problem. The notation in some critical parts of the paper is not clear and makes reading difficult.\n\nI would like to start saying that I am open to increasing my score (**Update: score updated after author feedback**) if the authors are able to clarify notation and add references/discussion, because I think that the essential contributions of this paper are important\n\nPros:\n1. Quality/Significance: The paper continues the vein of previous convex reformulations of the training of ReLU networks of Pilanci-Ergen (2020), extending the results of the single output case to multi-output which is arguably the interesting case in contemporary applications of Deep Learning. It opens the way to certified global optimality of solutions via convex programming of ReLU networks, and provides insight into the fundamental complexity of the optimization problem in nonconvex (factored) vs\nconvex form.\n\n2. Originality: There are few papers trying to understand the connections between the nonconvex formulation of the training of ReLU networks with convex formulations that provide certified optimality. For this reason I find the paper original although it builds upon previous work exploring this idea. Most papers deal with heuristic or ad-hoc arguments of convergence of GD/SGD in the non-convex formulation with many assumptions that might not hold in practice or that are cumbersome.\n\n3. Clarity: The \"text\" part of the paper is clearly written and the pace seems good. However there are crucial points where I could not understand the notation (see cons).\n\nCons:\n1. **This has been fixed in an updated version and is now not a problem** Clarity: I could not really understand the optimization problem (9) and (11) because the variable $i$ appears as an optimization variable $\\min_{i \\in [P]}$ but it does not appear in the optimization objective? In the objective the letter $i$ is used but as an index in the summation $\\sum_{i=1}^P$ which makes things really confusing. It appears that $i$ is not really an optimization variable and perhaps what the authors meant is that the constraint in (9) and (11) should read $V_i \\in K_i \\forall i \\in [P]$? at least this is what I would find most natural. This should be clarified and corrected if needed.  \n\n2. **This has been fixed in an updated version and is now not a problem** Clarity: It is not so clear how Algorithm 1 follows the Frank-Wolfe template. As I understand an initial value of $t$ is chosen and then the inner minimization problem is solved. Following this a new value of t is chosen and so on. So in the inner minimization problem the constraint set (assuming my understanding in the previous point) is $\\sum_{i=1}^P ||V_i|| \\leq t$ . Then the step (a) looks like the LMO but it is not clear where is the constraint \\sum_{i=1}^P \\| V_i \\|_ enforced? It looks like the FW update necessarily modifies only one $V_i$ and that the solution can be obtained from the LMO corresponding to only one constraint ||V_i||_ \\leq 1 is this the case? I think it is enforced through the constraint $\\|u\\|_2 \\leq 1$.\nIt would be great if the authors can confirm and flesh out the intermediate steps in the appendix, which does not explain much besides the algorithm in the main text. This would make it more accesible.\n\n3. **The authors argue in rebuttal that ReLU networks on spike-free data is still different from a linear classifier, some experiments were added** Significance: The Spike-free assumption seems to simplify things but it might be unrealistic. what is even more evident is that\nit is somehow equivalent to learning a linear classifier as it implies that $(XU)_+ = XU$ so the network is actually $XUV^T$ so it is equivalent to $XA$ with $A=UV^T$. Under this identification it is well known that the variational formulation of the nuclear norm\nimplies that the regularizer $\\|U\\|_F^2 + \\|V\\|_F^2$ is equivalent to the nuclear norm of the unfactored matrix $A$. There are multiple works studying this that should be mentioned and it should be acknowledge that the spike-free assumption is more convenient for simplifying the analysis, rather than realistic (or it should be argued why it is ok to do the assumption).  Also it is not clear in the statement of the theorem what is the relation to spike-free. Does whitened $X$ imply spike-free $X$?\n\n4. Significance: Theorem 2 is a simple consequence of this \"spike-free\" simplified setting and corresponds to the solution of the proximal operator of the nuclear norm.\n\n5. Significance: the previous two points suggest that the important results here are those corresponding to general $X$ matrix. Unfortunately in that case the complexity is exponential in the rank of the data, which I guess is just the \"real\" dimensionality of the data? for example if data is collinear this would be 1 and it is not surprising that the problem would become easier. It looks like the proposed algorithms are currently only of theoretical interest.\n\n6. **Authors have answered this in the revision** Experiments: exp 5.1: Perhaps add here the corresponding plots for the 0-1 error? it would be great to understand if the solution obtained with convex programming translates to better misclassification error compared to sgd. Currently how much time does the convex program take to solve? compared to SGD\ndo you think there is any benefit given that SGD seems to find good solutions in the overparametrized case?\u0000\n\n7. **Authors have answered this in the revision** Experiments: exp. 5.2. same as before: what happens with the misclassification error? what stops you from doing the computation on all the data? memory?\nDoes the red cross mean that the soft thresholded SVD is solved in less than one second?\u0000\n\nReferences:\n1. Unifying Nuclear Norm and Bilinear Factorization Approaches for Low-Rank Matrix Decomposition\nRicardo Cabral, Fernando De La Torre, Joao P. Costeira, Alexandre Bernardino; Proceedings of the IEEE International Conference on Computer Vision (ICCV), 2013, pp. 2488-2495\n2. Geometry of Factored Nuclear Norm Regularization. Qiuwei Li, Zhihui Zhu, Gongguo Tang\n3. Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization. Benjamin Recht, Maryam Fazel, and Pablo A. Parrilo\n\n+ many references therein\n\noverall I would be happy to recommend acceptance if the previous issues were adressed in a succint way.\n\n**Update** After author feedback many of my concerns have been addressed, in particular the optimization problem\ntemplates are much easier to understand now as well as the derivation of the algorithm. Also some important differences\nbetween linear classifiers vs ReLU networks on 'Spike-free' data have been clarified. These were my main concerns and thus I am inclined to raise my score. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "e3Urg-DEdIU", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "## Summary\nThe paper proposes a convex formulation for shallow neural networks with one hidden layer and vectorial outputs. This is an extension on a line of previous works (Ergen & Pilanci, 2020a) and (Ergen & Pilanci, 2020b) where similar results have been established for the case of scalar outputs. A Frank-Wolfe algorithm for finding the global optimum of the resulting convex program is proposed and evaluated on smaller datasets. \n\n## Explanation of Rating\nOverall, the paper tackles an important problem, is technically sound and well-written. I recommend acceptance of this paper, but have some smaller doubts which are mainly due to the incremental nature of the results (see detailed comment #1) and the strong assumptions for the proposed relaxation to be exact (see comment #2).\n\n## Detailed Comments\n1. My main concern with the paper is, that it is a direct extension of the results from (Ergen & Pilanci, 2020a) and (Ergen & Pilanci, 2020b) to the vectorial setting and therefore lacks novelty. Therefore, I feel the results presented in this paper might be better suited for a journal version of these previous works. \n\n2. The tightness guarantee for the relaxation requires the number of hidden neurons to be larger than the number of data points. In practice, this assumption is often not satisfied. The paper would be stronger if there was some theory (e.g. a duality gap analysis) that quantifies how the quality of the relaxation degrades as the number of data points is increased.  \n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "KzZSzkwus3Z", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The draft is a vector extension of [1] on studying how to approximately solve the global optima of a two-layered Relu network. The key of the analysis is to enumerate all possible sign patterns of the ReLU unit generating from specific data. Once we have the enumeration, we can also enumerate the linear area separated by ReLU, and the whole optimization problem will become a non-convex quadratic optimization problem. The non-convex quadratic can be approximately solved with its convex dual (or exactly under some conditions), or we can relax it to a copositive program (which might still be NP-hard to solve). With some assumption on the data, the sign pattern of the ReLU is a singleton, then we will have efficient algorithms to exactly recover the global optima of the two-layered network.\n\nI like the idea of linking 2-layer NN with copositive programs, the writing is good, and the proofs seem to be correct.\nHowever, I feel that the study on the whiten case with a singleton ReLU sign pattern is really not useful. When all the sign patterns of the ReLU are pinned, the representation power of a two-layered network reduces to a linear model (in a polyhedron). And if the representation power is equivalent to a linear model, why not reparameterize it linearly? The specific case lost all the existential meaning for a ReLU unit. (prove me wrong by showing it is better than linear in experiment.) \n\nOverall, this is a good extension of [1], but the improvement in complexity only works in trivial case.\n\nMinor issues:\n1. (Algorithm 1, (b)) The uj gj is undefined. The sj^(k) is not used anywhere.\n2. (equation at the bottom of p.18) Misisng sqrt{}\n3. Compleity below Section 4.2: enumeration takes O(n^r), but solving a copositive program is still NP.\n4. (Algorithm 1) It takes me a while to realize how the Frank-Wolfe algorithm works for the $\\sum_i|Vi|\\leq t$ constraint. Maybe it can be more clear.\n5. (Writing) There are many reference to appendix without specific section number... Please add them.\n\n[1] Neural Networks are Convex Regularizers: Exact Polynomial-time Convex Optimization Formulations for Two-layer Networks. Mert Pilanci and Tolga Ergen", "extra_scores": {}, "extra_text": {}}, {"review_id": "Eeajt7FUFKF", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper showed that a two-layer vector-output ReLU neural network training problem is equivalent to a finite-dimensional convex copositive program. Based on this connection, the authors gave the first algorithm that finds the global min of the network training problem, which has running time polynomial in the number of samples but exponential in the data matrix. For CNN, the running time is only exponential in the filter size, which is usually a constant. The authors also described circumstances in which the global min can be efficiently found by soft-thresholded SVD; provided a copositive relaxation that is exact for certain cases. The effectiveness of the proposed algorithms is verified in experiments.\n\nI think this is a good theory paper that shows an interesting connection between two layer network training and copositive program. My questions/concerns are as follows:\n\n1. What’s the role of the regularizer in the current analysis? Does the result extend to the setting where the loss function does not have a regularizer? \n2. The current analysis seems to be restricted to two-layer neural networks. I understand the analysis of multiple layer neural networks can be potentially much more difficult. It would be good if the authors can add some discussion on the possibility of extending the analysis to more general multiple-layer nets. \n3. The current paper focuses on minimizing the training loss. In practice, people usually use over-parameterized neural networks which has an infinite number of global min for training loss. It’s believed that SGD works well because SGD has an implicit bias which tends to converge to a global min that also generalizes well. So I think it would be good if the authors can check the generalization performance of the proposed new algorithm. \n4. Since the algorithm in this paper is limited to a two-layer ReLU neural network, which is rarely used in practice. So I wonder what’s the general implication/message of this paper to the practical ML community.\n5. A closely related paper [Ge et al 2018] also studies two-layer ReLU neural networks with vector-output. Under the assumption of symmetric distribution and more output dimension than hidden neurons, they gave a tensor decomposition algorithm that can recover the ground truth parameters in polynomial time. It might be good to compare the current paper and their result.\nhttps://arxiv.org/abs/1810.06793", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper extends an earlier work with scalar output to vector output. It establish a relationship of two-layer ReLu network and convex program. The result can be used to design training algorithms for ReLu networks with provably computational complexity. Overall, this is an interesting idea, leading to better theoretical insights to computational issues of two-layer ReLu networks. 
Decision: Accept (Poster)