Path Regularization: A Convexity and Sparsity Inducing Regularization for Parallel ReLU Networks
Authors: Tolga Ergen
Mert Pilanci
Venue: NeurIPS 2023 poster (2023)
Keywords: Convex optimization
deep learning theory
path norm
group sparsity
polynomial-time training
ReLU networks
parallel architectures
global optimality
computational complexity
TL;DR: We introduce a convex analytic framework to unveil a hidden convex optimization landscape for training path regularized deep neural networks.

Abstract: Understanding the fundamental principles behind the success of deep neural networks is one of the most important open questions in the current literature. To this end, we study the training problem of deep neural networks and introduce an analytic approach to unveil hidden convexity in the optimization landscape. We consider a deep parallel ReLU network architecture, which also includes standard deep networks and ResNets as its special cases. We then show that pathwise regularized training problems can be represented as an exact convex optimization problem. We further prove that the equivalent convex problem is regularized via a group sparsity inducing norm. Thus, a path regularized parallel ReLU network can be viewed as a parsimonious convex model in high dimensions. More importantly, since the original training problem may not be trainable in polynomial-time, we propose an approximate algorithm with a fully polynomial-time complexity in all data dimensions. Then, we prove strong global optimality guarantees for this algorithm. We also provide experiments corroborating our theory.

Path Regularization: A Convexity and Sparsity Inducing Regularization for Parallel ReLU Networks
Tolga Ergen LG Al Research tergenelggreseachh.o ai
Mert Pilanci Stanford University pilanci@stanford. edu
Abstract
Understanding the fundamental principles behind the success of deep neural net- works is one of the most important open questions in the current literature. To this end, we study the training problem of deep neural networks and introduce an analytic approach to unveil hidden convexity in the optimization landscape. We consider deep parallel ReLU network architecture, which also includes standard deep networks and ResNets as its special cases. We then show that pathwise regularized training problems can represented as an exact convex optimization problem. We further prove that the equivalent convex problem is regularized via group sparsity inducing norm. Thus, a path regularized parallel ReLU network can be viewed as parsimonious convex model in high dimensions. More importantly, since the original training problem may not be trainable in polynomial -ime, we propose an approximate algorithm with fully polynomial-tine -imem complexity in all data dimensions. Then, we prove strong global optimality guarantees for this algorithm. We also provide experiments corroborating our theory.
Optimal 2-layer with WD
Optimal 3-layer with WD
Optimal 3-layer with PR
0.0
3.0
-05
-05-
-0.
(a) 2-layer NN with WD
(b) 3-layer NN with WD
(c) 3-layer NN with PR (Ours)
Figure Decision boundaries of 2-layer and 3-layer ReLU networks that are globally optimized with weight decay (WD) and path regularization (PR). Here, convex training approach in (c) successfully learns the underlying spiral pattern for each class while the previously studied convex models in (a) and (b) fail (see Appendix A.1 for details).
Introduction
Deep Neural Networks (DNNs) have achieved substantial improvements in several fields of machine learning. However, since DNNs have a highly nonlinear and non-convex structure, the fundamental principles behind their remarkable performance still an open problem. Therefore, advances in this field largely depend on heuristic approaches. One of the most prominent techniques to boost the generalization performance of DNNs regularizing layer weights so that the network can fit function that performs well on unseen test data. Even though weight decay, i.e., penalizing the &-- norm of the layer weights, is commonly employed as regularization technique in practice, recently,
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Table I: Complexity comparison with prior works (n: # of data samples, d: feature dimension, my: # of hidden neurons in layer 1, c: approximation accuracy, r: rank of the data, & & r: chosen according to (10) such that accuracy is achieved)
Loss function
2-layer complexity
L-yayer complexity
Globally optimal
[30]
Convex loss
① 2 polkyyynn d, mi))
/BBruee-force
[31]
Ey-loss
20( polyfn, d)
X(NP-hard)
[32]
fp-loss
0 p2 poly(n, d. mi))
/ (Brute-force)
[6]
Convex loss
O(n" Onnppoly(d,n roly(d, O(n'poly(d,r))
/ (Convex, exact)
Ours
Convex loss
o 11 "y poly(d, rI,;r, m.)
/Convex, exact)
Ours
Convex loss
O(u"poy((d x))
o
ne I1 mi pody n. II mc)
(CConvex, c-opt)
has been shown that 22-path regularizer [1], i.e., the sum over all paths in the network of the squared product over all weights in the path, achieves further empirical gains [2]. Additionally, recent studies have elucidated that convex optimization reveals surprising generalization and interpretability properties for Deep Neural Networks (DNNs). [3-6] Therefore, in this paper, we investigate the underlying mechanisms behind path regularized DNNs through the lens of convex optimization.
Parallel ReLU Network
Path Regularization
(XWi)), Was)_
((() Li ([wa)
Outgut
Sub-network 1
Sub-netwock 2
Sub-zetwork K
Inpot
Figure 2: (Left)): Parallel ReLU network in (1) with K sub-networks and three layers (I. 3) (Right): Path regularization for three-layer network.
2 Parallel Neural Networks
Although DNNs are highly complex architectures due to the composition of multiple nonlinear functions, their parameters are often trained via simple first order gradient based algorithms, e.g.. Gradient Descent (GD) and variants. However, since such algorithms only rely on local gradient of the objective function, they may fail to globally optimize the objective in certain cases [7, 8). Similarly, [9. 10] showed that these pathological cases also apply to stochastic algorithms such as Stochastic GD (SGD). They further show that some of these issues can be avoided by increasing the number trainable parameters, i.c., operating in an overparameterized regime. However, [11] reported the existence of more complicated cases, where SGD/GD usually fails. Therefore, training DNNs to global optimality remains a challenging optimization problem [12-14].
To circumvent difficulties in training, recent studies focused on models that benefit from overparame- terization [15-18]. As an example, [19-23] considered a new architecture by combining multiple standard NNs, termed sub-networks, in parallel. Evidences in [20-25] showed that this way of combining NNs yields an optimization landscape that has fewer local minima and/or saddle points so that SGD/GD generally converges to global minimum. Therefore, many recently proposed NN-based architectures that achieve state-of-the-art performance in practice, e.g., SqueezeNet [26], Inception [27], Xception [28], and ResNext [29], are in this form.

---

Throughout the paper, we denote matrices and vectors as uppercase and lowercase bold letters, respectively. For vectors and matrices, we use subscripts to denote certain column/element, As an example, 1 denotes the jt-1 entry of the matrix Wik- We use Is and (or 1) to denote the identity matrix of size k x k and vector/matrix with appropriate sizes. We use [n]] for the set of integers from 1 to n. We use || ll2 and || || to represent the Euclidean and Frobenius norms, respectively. Additionally, we denote the unit l ball as B, := {u E R2 ||u||p S 13. We also use 1 a 2 0] and (x)+ = max 0} to denote the 0-1 valued indicator and ReI.U, respectively.
Notation and preliminaries:
zeros (or ones)
In this paper, we particularly consider a parallel ReLU network with K sub-networks and each sub-network is an L-layer ReLU network (see Figure 2) with layer weights Wi E - 1 VI E [L 1] and WLS E _m where my my 1', and my denotes the number of neurons in the t hidden layer. Then, given a data matrix X Rnxd, the output of the network is as follows
K
fo(X) = (XW1))) (IL-114) WLk.
where we compactly denote the parameters as 0 == W with the parameter space as O and each sub-network represents standard deep ReLU network.
Remark 1. Most commonly used neural networks in practice can be classified as special cases of parallel networks, e.g., standard NNs and ResNets [33] see Appendix A.2 for details.
2.1 Our Contributions
We prove that training the path regularized parallel ReLU networks (1) equivalent to a convex optimization problem that can be approximately solved in polynomial-time by standard convex solvers (see Table 1). Therefore, we generalize the two-layer results in [6] multiple nonlinear layer without any strong assumptions in contrast to [21] and much broader class of NN architectures including ResNets.
As already observed by [6, 21], regularized deep ReLU network training problems require exponential-time complexity when the data matrix is full rank, which is unavoidable. How- ever, in this paper, we develop an approximate training algorithm which has fully polynomial-tima complexity in all data dimensions and prove global optimality guarantees in Theorem 2. To the best our knowledge, this is the first convex optimization based and polynomial time complexity (in data dimensions) training algorithm for ReLU networks with global approximation guarantees.
We show that the equivalent convex problem regularized by group norm regularization where grouping effect is among the sub-networks. Therefore the equivalent convex formulation reveals implicit regularization that promotes group sparsity among sub-networks and generalizes prior works on linear networks such as [34] to ReLU networks.
We derive a closed-form mapping between the parameters of the non-convex parallel ReLU networks and its convex equivalent in Proposition 1. Therefore, instead of solving the challenging non-convex problem, one can globally solve the equivalent convex problem and then construct an optimal solution to the original non-convex network architecture via our closed-form mapping.
2.2 Overview of Our Results
Given data e gaxd and labels y E R" we consider the following regularized training problem
Pi. min L (fo (X) y) + BR(#).
BE0
where = {0 E θ: Wi E
VI E [L] Vk E [K]} is the parameter space, L (:. is an arbitrary convex loss function, R(-) represents the regularization on the network weights, and 3 > 0 the regularization coefficient.
For the rest of the paper, we focus on a scalar output regrrsssioncctassfccation framework with arbitrary loss functions, e.g., squared loss, cross entropy or hinge loss. We also note that our derivations
We analyze scalar outputs, however, derivations extend to vector outputs shown in Appendix A.
3

---

can be straightforwardly extended to vector outputs networks proven in Appendix A.11. More importantly, we use path regularizer studied in [1. 2]. which is defined
R(0)
Σ J2.0....
[| 12
II whissish) f=2
where - is the ji 1t entry of Wi. The above regularizer sums the square all the parameters along each possible path from input to output of each sub-networt & (see Figure and then take the squared root of the summation. Therefore, we penalize each path in each sub-network and then group them based the sub-network index k.
We now propose scaling to show that (2) is equivalent to a group & regularized problem. Lemma 1. The following problems are equivalent 2
K
min ([(( = min BE
W W
BE
where Wik E R are the last layer weights of each sub-network k. and O {0 θ
Sam-aioee (IWiK) (iwikiIBille 11 wit wiks--i)) 1, 1, vk [K]] denotes the parameter space
after rescaling.
The advantage of the form in Lemma 1 is that layer weights w. and then characterize the optimal layer weights via optimality conditions and the prior works & regularization in infinite dimensional spaces [35]. Thus, first apply the rescaling in Lemma and then take the dual with respect to the output weights W... To characterize the hidden layer weights, then change the order of minimization for the hidden layer weights and the maximization for the dual parameter to get the following dual problem'
derive dual problem with respect to the output
PL 2 di == (v) s.t. max OEG,
VT ((XW1) (..W)))..WW-D)4//44 SB,
where L the Fenchel conjugate function C, which is defined [36]
(*(v) maxz L (z.
The dual problem in (3) critical for our derivations since it provides us with an analytic perspective to characterize set of optimal hidden layer weights for the non-convex neural network in (1). To do so, we first show that strong duality holds for the non-convex training problem in Lemma 1, i.e. Pž di Then, based on the exact dual problem in (3), we propose equivalent analytic description for the optimal hidden layer weights via the KKT conditions.
We note that strong duality for two-layer ReLU networks has already been proved by previous studies [6. 19, 21, 22, 37, 38]. however, this is the first work providing an exact characterization for path regularized deep ReLU networks via convex duality.
3 Parallel networks with three layers
Here, we consider three-layer parallel network with K sub-networks, which is a special case of (1)
when L = 3. Thus, we have the following training problem
min L(fo (X) BEB
Σ Jn.da
Wiik 12 "
(4)
where θ ((W1,, W 2k: W
Wik il mddxm
Was gmixma Wak E R" By Lemma 1,
min L + O
+
(5)
k=
2 All the proofs are presented the supplementary file. We present the details in Appendix A.7.

---

1
0
0
0
0
1 0
01
0
D
0
1
0
D2
0
0
0
D3
0
1
0
D,
0
0
0
1
0
0
0
L
0
0
10
1.
(1.1)
(33)
03.3
(3.3)
Noner dlosiin
[2:7]
(7:2)
(2:7)
dadl
(1.0]
Sonte datter
(1.0)
(1.0)
Figure 3: Illustration of possible hyperplane arrangements that determine the diagonal matrices D;- Here, we have three samples in two dimensions and we want separate these samples with linear classifier. D; basically encodes information regarding which side of the linear classifier samples lie.
Then, taking the dual of (5) with respect the output layer weights Wa E R and then changing the order of the minimization for [WIs. ik. W2x and the maximization for the dual variable v yields
Ps ž dz max - (v)
max BEG,
v (XXW1), W2) s B.
Here, we remark that (4) is non-convex with respect to the layer weights, we may have duality gap, i... p3 2 dz. Therefore, we first show that strong duality holds in this case, i.e., p d as detailed in Appendix A.4. We then introduce an equivalent representation for the ReLU activation follows.
Since ReLU masks the negative entries of inputs, have the following equivalent representation
m21
m1
((XW1), w2)
Σ
(Xw1j) wan
Σ
(X
In
1==1
+
mi
D2
Di, Xwi.
h=
where W,, [22 Wij+ I, = sign(W25.) [f-1,++], and we use the following alternative
representation for ReLU (see Figure 3 for two dimensional visualization)
DXw20
(2D HD-L,) Xn)
Ww
where D E Ruxn is diagonal matrix of zeros/ones, i.e., D. E {0, 13. Therefore, we first enumerate all possible signs and diagonal matrices for the ReLU layers and denote them as In Dishi and D2: respectively, where jı [m1],i [Pi], [Pg]. Here, Das,, and D denotes the masking/diagonal matrices for the first and second ReLU layers, respectively and Pı and P2 are the number diagonal matrices in each layer as detailed in Section 1010. Then, convert the non-convex constraints in (6) to convex constraints using Diúj. D2 and I,--
Using the representation in (7), we then take the dual of (6) to obtain the convex bidual of the primal problem (4) as detailed in the theorem below.
Theorem 1. The non-conve training problem in (4) can be cast as the following convex program
min L (x(2 -20))==)))
3 ([1 + 12())
Vmn
where 11F, denotes a x m2 dimensional group Frobenius norm operator such that given a vector E RddmiP, ||uu]| := >. |UU||F, where U, Rdxma are reshaped partitions of u. Moreover, the convex ser C is defined as
: fz: (2:2ih Ca.Vi E [P]. E [Pa]. 8 [M]
Ca = { (W5r : (2D I.)
mi
I Dioj Xw,, (2D I,),w,, 2 20, Vj1 E [m1]]
=1
5

---

where Light E [+1,-1}, M- = 2 and 2, z E Rd P3 are constructed by stacking zij ihl E R., Vi E [Pi), E [P2l, E [mi]. E [M], respectively. Also, the effective data matrix X
B MPPP is defined as X 1M X, and
X, = DDDDDDD
D&D 16j ... D2p, DIPmm,
We next derive a mapping between the convex program (8) and the non-convex architecture (4). Proposition An optimal solution the non-convex parallel network training problem in (4), denoted as { [Wi, Ike Wat. k== can be recovered from an optimal solution to the convex program in (8), Le., {z" z via a closed-form mapping. Therefore, we prove mapping between the parameters of the parallel network in Figure and its convex equivalent.
Next, we prove that the convex program in (8) can be globally optimized with a polynomial-time complexity given X has fixed rank, i.e., rank(X] (X) r < min(n,d):
Proposition Given a data matrix such that rank (X) = = min(n, d}, the convex program in (8) can be globally optimized via standard convex solvers with ( mmm2mmm + n +1)r) complexity, which is polynomial-tine complexity in terms of n, d. Note that here globally optimizing the training objective means to achieve the exact global minimum up to any arbitrary machine precision solver tolerance.
Below, we show that the complexity analysis in Proposition 2 extends arbitrarily deep networks. Corollary 1. The same analysis can be readily applied to arbitrarily deep networks. Therefore, given rank( X) < min(n, d), prove that L-layer architectures be globally optimized 2-2
with O d 11 m3) 2 Ei my n 31+E m=)) ). which is polynomial in n, d.
3
5000
Exact F
#of hyperplane trrangements
Exact
Proposed Pr
Proposed
4000
Objective value
2
Upperbound
3000
10
2000
10
1000
10
5
9
8
# of features (d)
# of features (d)
(a) Objective value (L)
(b) # of hyperplane arrangements (P)
Figure 4: Verification of Theorem 2 and Remark 2. We train parallel network using the convex program in Theorem with & loss on a toy dataset with 15, 3 0.1, approximation r = _
1, and the low-rank J. To obtain low-rank model, we first sample a data matrix from a standard normal Gaussian distribution and then set 0, ... σa 1. Please the subsection for low rank models in Section 4 for more details.
3.1 Polynomial-time training for arbitrary data
Based on Corollary I, exponential complexity is unavoidable for deep networks when the data matrix full rank, i.e., rank(X) min(n, d). Thus, we propose low rank approximation the model in (4). We first denote the rank-r approximation of X X, such that ||X-X,,11 S ar+1, where d++1 represents the (r 1)th largest singular value of X. Then, have the following result.
Theorem 2. Given an R-Lipschitz convex loss function L ((,y), the regularized training problem
K
--=min L(Do (()((X)))+ BE0
1 33kjs'
(9)
Ji.Ja

---

Table 2: Training objective of a three-layer parallel network trained with non-convex SGD (5 indepen- dent initialization trials) on a toy dataset with (n, d, m1, m2, 3, batch size) = (5. 2, 3. 1, 0.002, 5), where the convex program in (8) are solved via the interior point solvers in CVX/CVXPY.
Method
Non-convex SGD
Convex(Ours)
Run #1
Run #2
Run #3
Run #4
Run #5
K- Training objective
0.0221
0.0239
0.0031
0.0027
0.0027
0.0007
Time(s)
11.62
11.62
11.62
11.62
11.62
4.947
Training objective
0.0010
0.0027
0.0009
0.0010
0.0027
0.0007
K 20
Time(s)
44.37
44.37
44.37
11.55
44.37
4.947
Training objective
0.0008
0.0009
0.0009
0.0009
0.0008
0.0007
K= 40
Time(s)
91.87
91.87
91.87
91.87
91.87
4.947
can be solved using the data matrix X, to achieve the following optimality guarantee
ps S Pr S ps (1+ mm m2 M2gRo,+1
(10)
3
where pr denotes the objective value achieved by the parameters trained using X,.
Remark 2. Theorem I and 2 imply that for a given arbitrary rank data matrix X, the regularized training problem in (4) can be approximately solved by convex solvers to achieve a worst-case approximation pl 1 Smmmmyoo
where & min(n, d). Therefore, even for full rank data matrices where the complexity is exponential in d, one can approximately solve the convex program in (8) in polynomial-time Moreover, we remark that the approximation error proved in Theorem 2 can be arbitrarily small for practically relevant problems. As an example, consider a parallel network training problem with Eg loss function, then the upperbound becomes (1 + fmimpor11 which is typically close to one due to fast decaying singular values in practice (see Figure 4).
with complexity ((d"m)22Mmmmn))ite
3.2 Representational power: Two versus three layers
Here, we provide a complete explanation for the representational power of three-layer networks by comparing with the two-layer results in [6]. We first note that three-layer networks have substantially higher expressive power due to the non-convex interactions between hidden layers as detailed in [39, 40J. Furthermore, [41] show that layerwise training of three-layer networks can achieve comparable performance to deeper models, e.g., VGG-11 I, on Imagenet. There exist several studies analyzing two-layer networks, however, despite their empirical success, full theoretical understanding and interpretation of three-layer networks is still lacking in the literature. In this work, we provide complete characterization for three-layer networks through the lens of convex optimization theory. To understand their expressive power, we compare our convex program for three-layer networks in (8) with its two-layer counterpart in [6].
[6] analyzes two-layer networks with one ReLU layer, so that the data matrix X multiplied with single diagonal matrix (or hyperplane arrangement) D,. Thus, the effective data matrix is in the form of x, [D, ... DpX]. However, since our convex program in (8) has nonlinear ReLU layers, the composition of these two-layer can generate substantially more complex features via locally linear variables ( (w multiplying the d-dimensional blocks of the columns of the effective
data matrix X, in Theorem 1. Although this may seem similar to the features in [21], here, we have 2 variables for each linear region unlike [21] which employ 2 variables per linear region. Moreover, [21] only considers the case where the second hidden layer has only one neuron, i.e., m2 1, which not a standard deep networks. Hence, we exactly describe the impact of having one more ReLU layer and its contribution to the representational power of the network.
7

---

4 Experiments
In this section", we present numerical experiments corroborating our theory.
To validate our claims, we generate synthetic dataset follows. We first randomly generate a set of layer weights for a parallel ReLU network with K = sub- networks by sampling from a standard normal distribution. We then obtain the labels as y Ex (XWW1+)+ W2x) W3k + 0.1e, where E ~ (O, To promote a low rank structure in the data, we first sample a matrix from the standard normal distribution and then set 0+1 = 0o 1. We consider regression framework with &g loss and (n, r, 3,, ; m22 present the numerical results in Figure 4. Here, we observe that the low rank approximation of the objective pr- is closer to p than the worst-case upper-bound predicted by Theorem 2. However, in Figure 4b, the low rank approximation provides significant reduction in the number of hyperplane arrangements, and therefore the complexity of solving the convex program.
Low rank model in Theorem 2:
(15, d/2, and
We use a toy dataset with 5 samples and 2 features, i.e., (n, d) = (5, 2). To generate the dataset, we forward propagate i.i.d. samples from standard normal distribution, i.e., X; ~ NN La). through a parallel network with 3 layers, 5 sub-networks, and neurons, i.e., (L, K, m., m2) = (3, 5, 3, 1). We then train the parallel network in (4) this toy dataset using both our convex program (8) and non-convex SGD. We provide the training objective and wall-clock time in Table 2, where we particularly include initialization trials for SGD. This experiment shows that when the number of sub-networks K is small, SGD trials fail to converge to the global minimum achieved by our convex program. However, as we increase K, the number of trials converging to global minimum gradually increases. Therefore, we show the benign overparameterizttio impact.
Toy dataset:
Image classification: We conduct experiments benchmark image datasets, namely CIFAR-10 [42] and Pashion-MNIS [43]. We particularly consider a ten class classification task and use a parallel network with 40 sub-network and 100 hidden neurons, i.e., (K, m2, (40, 100, 1). In Figure 5, we plot the test accuracies against wall-clock time, where we include several different optimizers as well SGD. Moreover, we include parallel network trained with SGD/Adam and Weight Decay (WD) regularization to show the effectiveness of path regularization in (4). We first note that our convex approach achieves both faster convergence and higher final test accuracies for both dataset. However, the performance gain for Mashion-MNISY seems to be significantly less compared to the CIFAR-10 experiment. This is due the nature of these datasets. More specifically, since CIFAR- 10 is a much more challenging dataset, the baseline accuracies are quite low (around ~ 50%) unlike Bishion-MNIS" with the baseline accuracies around 90%. Therefore, the accuracy improvement achieved by the convex program seems low in Figure 5b. We also observe that weight decay achieves faster convergence rates however path regularization yields higher final test accuracies. is normal to have faster convergence with weight decay since it can be incorporated into muddient-based updates without any computational overhead.
5 Related Work
Parallel neural networks were previously investigated by [22, 23]. Although these studies provided insights into the solutions, they require impractical assumptions, e.g., sparsity among sub-networks in Theorem I of [23]) and linear activations and hinge loss assumptions in [22].
Recently, [6] studied weight decay regularized two-layer ReLU network training problems and
introduced polynomial-time time trainable convex formulations. However, their analysis is restricted to standard two-layer ReLU networks, i.e., in the form of fx) = (XW1)4 W2. The reasons for this restriction is that handling more than one ReLU layer is a substantially more challenging optimization problem. As an example, a direct extension of [6] to three-layer NNs will yield doubly exponential complexity, i.e., O(n"") ) for rank-r data matrix, due to the combinatorial behavior of multiple ReLU layers. Thus, they only examined the case with a single ReLU layer (see Table I for details and references in [6]). Additionally, since they only considered standard two-layer ReLU networks, their analysis is not valid for a broader range of NN-based architectures as detailed in Remark 1. Later on, [21] extended this approach to three-layer ReLU networks. However, since they analyzed &y norm regularized training problem, they had to put unit Frobenius norm constraints on
'Details on the experiments can be found in Appendix A.I.
8

---

2.00
2.50
Test Accuracy
Test Accuracy
2:00
0.40
5903
Convex (Cluns)
503
Convex (Curs)
Adam
Adagrad
Adadetta
082
Adadells
SGD WD
SGD WD
Adam WD
Time(s)
Time(s)
(a) CIFAR-10
(b) MoIiiO
Figure 5: Accuracy of three-layer architecture trained using the non-convex formu-
lation (4) and the proposed convex program (8), where we use (a) CIFAR-10 with (n, d, m1, m2, K, batch size)
(5x10*, 3072, 100, 40, 10 110)) and (b) Fashion-MNIST
with (n, d, m., m2, K, 3, batch size) = (6x10*, 784, 100, 1, 40, 10-3, 100). We note that the convex model trained using (a) SGD and (b) Adam.
the first layer weights, which does not reflect the settings in practice. In addition, their analysis is restricted the networks with single neuron in the second layer (i.e. m2 1) that is in the form of fx(X) Ex ((XW1+)4 W2k). Wak- Since this architecture only allows a single neuron in the second layer, each sub-network has expressive power that is equivalent to standard two-layer network rather than three-layer. This can also be realized from the definition of the constraint set C in Theorem 1. Specifically, the convex set C in [21] has decoupled constraints across the hidden layer index j1 whereas our formulation sums the responses over hidden neurons before feeding through the next layer standard deep networks do. Therefore, this analysis does reflect the power of deep networks with data matrix has full rank, which is unavoidable.
2. Moreover, the approach in [21] has exponential complexity when the
However, we analyze deep neural networks in (1) without any assumption on the weights. Further- more, develop algorithm which has fully polynomial-time complexity in data dimensions and prove strong global optimality guarantees for this algorithm in Theorem 2.
Concluding Remarks
We studied the training problem of path regularized deep parallel ReLU networks, which includes ResNets and standard deep ReLU networks as its special cases. We first showed that the non-convex training problem be equivalently cast single convex optimization problem. Therefore, achieved the following advantages over the training on the original non-convex formulation: 1) Since our model is convex, it can be globally optimized via standard convex solvers whereas the non-convex formulation trained with optimizers such as SGD might be stuck at local minimum, 2) Thanks to convexity, learning rate schedule and initialization scheme selection or dropout, More importantly, we proposed training terms of the
model does not require any sort of heuristics and additional tricks such as
an approximation the convex program enable fully polynomial-tnn number of data samples n and feature dimension d. Thus, we proved the polynomial-tin trainability of deep ReLU networks without requiring any impractical assumptions unlike [6. 21J. Notice that we derive an exact convex program only for three-layer networks, however, recently [19] proved that strong duality holds for arbitrarily deep parallel networks. Therefore, similar analysis can be extended to deeper networks to achieve an equivalent convex program, which is quite promising future work. Additionally, although we analyzed fully connected networks in this paper, our approach can be directly extended to various NN architectures, e.g., threshold/binary networks [44]. convolution networks [45], generative adversarial networks [46], NNs with batch normalization [47], autoregressive models [48], and Transformers [49, 50].

---

Acknowledgements
This work was supported in part by the National Science Foundation (NSF) CAREER Award under Grant CCF-2236829, Grant DMS-2134248 and Grant
in part by the U.S. Army Research Office Early Career Award under Grant W911NF-21-1-0244 in part by the Stanford AICESS-AICE Al Chip Center for Emerging Smart Systems through
Precourt Institute; and in part by the ACCESS
InnoHK, Hong Kong, SAR.
10

---

References
[1] Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-hased capacity control neural networks. In Peter Grünwald, Elad Hazan, and Satyen Kale, editors, Proceedings The 28th Conference on Learning Theory, volume 40 of Proceedings of Machine Learning Research, pages 1376-1401, Paris, France, 03-06 Jul 2015. PMLR.
[2] Behnam Neyshabur, Russ Salakhutdinov, and Nati Srebro. Path-sgd: Path-normalized optimization in deep neural networks. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 28, Curran Associates, Inc., 2015.
[3] Tolga Ergen and Mert Pilanci. Convex geometry of two-layer relu networks: Implicit autoen- coding and interpretable models. Silvia Chiappa and Roberto Calandra, editors, Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 4024-4033, Online, 26-28 Aug 2020. PMLR.
[4] Tolga Ergen and Mert Pilanci. Convex geometry and duality of over-parameterized neural networks. Journal of Machine Learning Research, 22(212):1-63, 2021.
[5] T. Ergen and M. Pilanci. Convex optimization for shallow neural networks. In 2019 57th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages
79-83. 2019.
[6] Mert Pilanci and Tolga Ergen. Neural networks are convex regularizers: Exact polynomial convex optimization formulations for two-layer networks. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 1 119 of Proceedings of Machine Learning Research, pages 7695-7705. PMLR, 13-18 Jul 2020.
[7] Shai Shalev-Shwartz, Ohad Shamir, and Shaked Shammah. Failures of maddient-based deep learning. arXiv preprint arXiv: /
770.07950. 2017.
[8] Ian Goodfellow, Yoshua Bengio, Aaron Courville, and Yoshua Bengio. Deep learning, volume 1. MIT press Cambridge, 2016.
[9] Rong Ge, Jason D. Lee, and Tengyu Ma. Learning mee-hddee-llaer neural networks with landscape design, 2017.
[10] Itay Safran and Ohad Shamir. Spurious local minima are common in two-layer relu neural networks. In International Conference Machine Learning, pages 4433-4441. PMLR, 2018.
[11] Animashree Anandkumar and Rong Ge. Efficient approaches for escaping higher order saddle points in non-convex optimization. In Conference on learning theory, pages 81 81-102, 2016.
[12] Bhaskar DasGupta, Hava T Siegelmann, and Eduardo Sontag. On the complexity of training neural networks with continuous activation functions. IEEE Transactions on Neural Networks, 6690:1490- 1995.
[13] Avrim Blum and Ronald I. Rivest. Training 3-node neural network is np-complete. In Advances in neural information processing systems, pages 494-501, 1989.
[14] Peter Bartlett and Shai Ben-David. Hardness results for neural network approximation problems. In European Conference on Computational Learning Theory, pages 50-62. Springer, 1999.
[15] Alon Brutzkus, Amir Globerson, Eran Malach, and Shai Shalev-Shwarde SGD learns pyerpprrameterized networks that provably generalize on lincarly separable data. CoRR, abs/1710.101744, 2017.
[16] Simon S Du and Jason D Lee. On the power of wwerparramttiizttoon in neural networks with quadratic activation. arXiv preprint 1003.v1800.0100 2018
[17] Sanjeev Arora, Nadav Cohen, and Elad Hazan. On the optimization of deep networks: Implicit acceleration by overparameterization. In 35th International Conference on Machine Learning, ICML 2018, pages 372-389. International Machine Learning Society (IMLS), 2018.
[18] Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LeCun, and Nathan Srebro. Towards understanding the role of wee-paramettization in generalization of neural networks. arXiv preprint
1800.100766.6 2018.
[19] Yifei Wang, Tolga Ergen, and Mert Pilanci. Parallel deep neural networks have zero duality gap.
In The Eleventh International Conference Learning Representations, 2023,
11

---

[20] Tolga Ergen and Mert Pilanci. Revealing the structure of deep neural networks via convex duality. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning. volume 139 of Proceedings of Machine Learning Research, pages 3004-3014. PMLR, 18-24 Jul 2021.
[21] Tolga Ergen and Mert Pilanci. Global optimality beyond two layers: Training deep relu networks via convex programs. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 2993-3003, PMLR, 18-24 Jul 2021.
[22] Hongyang Zhang, Junru Shao, and Ruslan Salakhutdinov. Deep neural networks with multi- branch architectures are intrinsically less non-convex. In The 22nd International Conference on Artificial Intelligence and Slatistics, pages 1099-1109, 2019.
[23] Benjamin D Haeffele and René Vidal. Global optimality in neural network training. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 7331-7339, 2017.
[24] Sergey Zagoruyko and Nikos Komodakis. arXiv: 07746 2016.
Wide residual networks. arXiv preprint
[25] Andreas Veit, Michael Wilber, and Serge Belongie. Residual networks behave like ensembles of relatively shallow networks. In Advances in neural information processing systems, pages 550-558, 2016.
[26] Forrest N landola, Song Han, Matthew W Moskewicz, Khalid Ashraf, William Dally, and Kurt Keutzer. Squeezenet: Alexnet-level accuracy with 50x fewer parameters and< 0.5 mb model size. arXiv preprint arXiv: /60. 07360, 2016.
[27] Christian Szegedy, Sergey loffe, Vincent Vanhoucke, and Alexander A Alemi. Inception-v4, inception-resnet and the impact of residual connections on learning. In Thirty-frst AAAI conference on artificial intelligence, 2017.
[28] François Chollet. Xception: Deep learning with depthwise separable convolutions. In Proceed- ings of the IEEE conference on computer vision and pattern recognition, pages 1251-1258, 2017.
[29] 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 on computer vision and pattern recognition, pages 1492-1500, 2017.
[30] Raman Arora, Amitabh Basu, Poorya Mianjy, and Anirbit Mukherjee. Understanding deep neural networks with rectified linear units. In 6th International Conference Learning Representations, ICLR 2018, 2018
[31] Surbhi Goel, Adam Klivans, Pasin Manurangsi, and Daniel Reichman. Tight Hardness Results for Training Depth-2 ReLU Networks. In James R. Lee, editor, 12th Innovations in Theoretical Computer Science Conference (ITCS 202/), volume 185 of Leibniz International Proceedings in Informatics (LIPlcs), pages 22:1-22:14, Dagstuhl, Germany, 2021. Schloss Dagstuhl-Leibnizz Zentrum für Informatik.
[32] Vincent Froese, Christoph Hertrich, and Rolf Niedermeier. The computational complexity of relu network training parameterized by data dimensionality, 2021.
[33] 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, pages 770-778, 2016.
[34] Zhen Dai, Mina Karzand, and Nathan Srebro. Representation costs of linear neural networks: Analysis and design. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 26884-26896. Curran Associates, Inc., 2021.
[35] Saharon Rosset, Grzegorz Swirszez, Nathan Srebro, and Ji Zhu. LI regularization in infinite dimensional feature spaces. In International Conference on Computational Learning Theory, pages 544-558. Springer, 2007.
[36] Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
12

---

[37] Tolga Ergen and Mert Pilanci. Convex geometry and duality of pvrrpparameterized neural networks. Journal of Machine Learning Research, 22(212):1-63, 2021.
[38] Francis Bach. Breaking the curse of dimensionality with convex neural networks. The Journal of Machine Learning Research, 18(1):629-681) 2017.
[39] Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization in overparame- terized neural networks, going beyond two layers. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[40] Huy Tuan Pham and Phan-Minh Nguyen. Global convergence of three-layer neural networks in the mean field regime. In International Conference on Learning Representations, 2021.
[41] Eugene Belilovsky, Michael Eickenberg, and Edouard Oyallon. Greedy layerwise learning can scale to imagenet. In International conference machine learning, pages 583-593. PMLR, 2019.
[42] Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. The CIFAR-10 dataset. http://www.. cs.
toronto. aadu/krii/ee httte////aarr///r/ html, 2014.
[43] Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: novel image dataset for benchmarking machine learning algorithms, 2017.
[44] Tolga Ergen, Halil I. Gulluk, Jonathan Lacotte, and Mert Pilanci. Globally optimal training of neural networks with threshold activation functions. In The Eleventh International Conference on Learning Representations, 2023.
[45] Tolga Ergen and Mert Pilanci. Implicit convex regularizers of enn architectures: Convex optimization of two- and three-layer networks in polynomial time. In International Conference on Learning Representations, 2021.
[46] 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, 2022.
[47] Tolga Ergen, Arda Sahiner, Batu Ozturkler, John M. Pauly, Morteza Mardani, and Mert Pilanci. Demystifying batch normalization in reI.U networks: Equivalent convex optimization models and implicit regularization. In International Conference on Learning Representations, 2022.
[48] Vikul Gupta, Burak Bartan, Tolga Ergen, and Mert Pilanci. Convex neural autoregressive models: Towards tractable, expressive, and theoretically-bade backed models for sequential forecasting and generation. In ICASSP 202/ 2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 3890-3894, 2021.
[49] Tolga Ergen, Behnam Neyshabur, and Harsh Mehta. Convexifying transformers: Improving optimization and understanding of transformer networks. arXiv, 2022.
[50] Arda Sahiner, Tolga Ergen, Batu Ozturkler, John Pauly, Morteza Mardani, and Mert Pilanci. Unraveling attention via convex duality: Analysis and interpretations of vision transformers. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 19050-19088. PMLR, 17-23 Jul 2022.
[51] Daniel Smilkov Carter and Shan.
A
neural
network playground.
[52] Michael Grant and Stephen Boyd. CVX: Matlab software for disciplined convex programming,
version 2.1. http: //tp:////////////// wtt.co//cccooo cvm/ March 2014.
[53] Steven Diamond and Stephen Boyd CVXPY: A Python-embedded modeling language for convex optimization. Journal of Machine Learning Research, 17(83):1-5, 2016.
[54] Akshay Agrawal, Robin Verschueren, Steven Diamond, and Stephen Boyd. A rewriting system for convex optimization problems. Journal of Control and Decision, 5(1): 60, 2018.
[55] Dheeru Dua and Casey Graff. UCI machine learning repository, 2017.
[56] Manuel Fernández-Delgadoo Eva Cernadas, Senén Barro, and Dinani Amorim. Do we need hundreds of classifiers to solve real world classification problems? Journal of Machine Learning Research, 13390):1 2014.
13

---

[57] Maurice Sion. On general minimax theorems. Pacific J. Math., 8(1):171-176, 1958.
[58] Piyush C Ojha. Enumeration of linear threshold functions from the lattice of hyperplane intersections. IEEE Transactions Neural Networks, 11(4):839-80, 2000.
[59] Richard P Stanley et al. An introduction to hyperplane arrangements. Geometric combinatorics,
13:389-4P 490,9999660000 2004.
[60] RO Winder. Partitions of n-space by hyperplanes. SIAM Journal on Applied Mathematics, 14(4):811-8) 818, 1966.
[61] Thomas M Cover. Geometrical and statistical properties of systems of linear inequalities with applications in pattern recognition. IEEE transactions electronic computers, (3):326-334, 1965.
[62] 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 salyooomil-timm algorithms. International Conference on Learning Representations. 2021.
14

---

Supplementary Material
Table of Contents
A
Appendix
15
Additional numerical results and details
A.2 Parallel ReLU networks
17
A.3 Proof of Lemma
18
A.4 Proof of Theorem
18
Proof Proposition
20
A.6 Proof of Theorem
21
A.7 Proof for the dual problem in (3)
23
A.8 Hyperplane arrangements
23
A.9 Low rank model in Theorem 2
24
A.10 Proof of Proposition 2 and Corollary
24
A.11 Extension to vector outputs
26
A
Appendix
A.1
Additional numerical results and details
In this section, we provide new numerical results and detailed information about experiments in the main paper.
In order to visualize the capabilities of our convex training approach, we perform an experiment on the spiral dataset which known to be challenging for 2-layer networks while 3-layer networks can readily interpolate the training data (i.e. exactly fit the training labels) [51]. As the baselines of our analysis, we include the two-layer convex training approach in [6] and recently introduced three-layer convex training approach (with weight decay regularization and several architectural and parametric
Decision boundary plots in Figure 1:
setup, we consider binary classification task with assumptions) in [21]. our experimental [-1,-1] and squared loss. We choose (n, (n, my, m2, Pı, P2, 3) (30, 5, 1, 1,111,1, le 4) and for [6] we use = 50 neurons/hyperplane arrangements. We also use CVPXY with MOSEK solver [52-54] to globally solve the convex programs. As demonstrated in Figure 1, baselines methods, especially [21], fit function that significantly differrntt than the underlying spiral data distribution. This clearly shows that since [6] is restricted two-layer networks and [21] have multiple assumptions, i.c., unit Frobenius norm constraints the layer weights (|) (| u|lF < 1, VI [L - 2)) and last hidden layer weights cannot be matrices (W 1M E R=). both baseline approaches fail to reflect true expressive power of deep networks (L > 2). On the other hand, our convex training approach for path regularized networks fits a model that successfully describes the underlying data distribution for this challenging task.
Additional experiments: We also conduct experiments on several datasets available in UCI Machine Learning Repository [55], where we particularly selected the datasets from [56] such that < 500. For these datasets, we consider conventional binary classification framework with (m1,my m2, K, .) = (100, 1, 40, 0.5) and compare the test accuracics of non-convex architectures trained with SGD and Adam with their convex counter parts in (8). For these experiments, we use the 80% 20% splitting ratio for the training and test sets. Furthermore, we train each algorithm long enough to reach training accuracy one. As shown in Table 3, our convex approach achieves higher or the same test accuracy compared to the standard non-conve conconeex training approach for most of the datasets (precisely 20 and 19 out of 21 datasets for SGD and Adam, respectively). We also note that for this experiment, we used the unconstrained form in (11) with the approximate version in Remark 3.3 of [6].
Details for the experiments in Table and Figure 5: We first note that for the experiments Table 2, we use CVX/CVPXY [52-54] to globally solve the proposed convex program in (8). For these
15

---

Table Test accuracies for UCI experiments (m1, m2, K. 3) (100. 1, 40, 0.5) and 80% 20% training- test split). Here, we present the standard non-convex architectures and the proposed convex counterpart trained with SGD and Adam optimizers. If one approach achieves higher accuracy on certain dataset, we display the corresponding accuracy value in bold font. We observe that our convex approach achieves either higher or the same accuracy for 20 and datasets (out of 21 datasets) when trained with SGD and Adam, respectively
SGD
Adam
Dataset
72
Non-convex
Convex(Ours)
Non-convex
Convex(Ours)
acute-inflammation
120
1.000
1.000
1.000
1.000
acute-nephritis
120
1.000
1.000
1.000
1.000
balloons
16
1.000
1.000
1.000
1.000
breast-cancer
286
0.690
0.707
0.655
0.672
breast-cancer-wisee proc
198
33
0.750
0,800
0.800
0.825
congressional-votin voting
435
16
0.667
0.667
0.551
0,597
www.heench-sonarmmine--eee
208
60
0.714
0.786
0.738
0.833
echocardiogram
131
10
0.704
0.704
0.666
0.703
fertility
0.750
0,800
0.800
0,800
Inperman-survisee
0.710
0.774
0.677
0,709
hart-hungarian
12
0.831
0.831
0.779
0,813
hepatitis
155
19
0.645
0.710
0.709
ionosphere
33
0.887
0.901
0.929
0.887
molec-biol-promant
106
57
0.818
0.818
0.727
0.772
musk-1
166
0.958
0.927
0.947
0.927
parkinsons
195
22
0.974
1.000
0.923
1.000
beisshurgbridggs-Teee
102
0.952
0.952
0.809
0.857
planning
182
12
0.541
0.568
0.649
0.703
statlog-heart
270
13
0.759
0.796
0.759
0.833
trains
10
29
1.000
1.000
1.000
1.000
310
0.806
0.839
0.758
0.822
Highest test accuracy
20/21
19/21
experiments, we use a laptop with i7 processor and 16GB of RAM. order to tune the learning rate of SGD/GD, first perform training with bunch of learning different learning rates and select the one with the best performance on the validation datasets, which is 0.005 in these experiments.
For comparatively larger scale image classification experiments in Figure 5, we utilize cluster GPU with 50GB of memory. However since the equivalent convex program in (8) has constraint which are challenging to handle for these datasets, we propose the following unconstrained convex problem which has the same global minima with the constrained version as discussed in [48]
L (x 2) x), 3 (1lz)le, ||21||,1) (he(z) + he(z') (11)
min 2,2' Eiddong P.
where À > 0 coefficient to penalize the violated constraints and hz(2) is function to sum the absolute value of all constraint violations defined as
(z(z) = T Σ ((-(2D - X,)xx(g,)) +1 $J148
E 1.1.8
Ii, I,) Xzigi
51
Thus, obtain unconstrained version of convex optimization problem (11), where can commonly employed first-order gradient based optimizers, e.g., SGD and Adam, available in deep learning libraries such PyTorch and Tensorflow. For both CIFAR-I0 and Fashion-MNIST, the same training and test splits in the original datasets. We again perform a grid search to tune the learning rate, where the best performance is achieved by the following choices
use
WD (AConeexs PSGD: Adams Adagrad' Adadelta PSGD) and
(5e 5. 3, 2e
- 1,1)
WD (HConver: Ds Adams Addgradd: l Adadelta (SGD) (1e 5, 2e 1,2c 3e 2, as the learning rates for CIFAR-10 and Fashion-MNIST. respectively. We choose the momentum coefficient of the SGD optimizer as 0.9. In addition to this, we set P.P K and A 1e 5.
16

---

CIFAR-10 Test Accuracy
80
75
70
65
60
convex layerwise training
55
1.0
1.5
2.0
2.5
3.0
3.5
4.0
4.5
5.0
Stage
Figure 6: Test aceuracy for convex layerwise training, where each stage is our three-layer convex formulation in Theorem 1. Here, we train three-layer neural networks sequentially using convex optimization to build deep networks.
More importantly, remark that these experiments are performed by using small sampled subset of hyperplane arrangements rather than sampling all possible arrangements as detailed Remark 3.3 of [6]. In particular, we first generate random weight matrices from multivariate standard normal distribution and then solve the convex program using only the arrangements of the sampled weight matrices.
Details for the experiments in Figure 6: Layerwise training with shallow neural networks was proven to work remarkably well. Particularly. [41] shows that one can train three-layer neural build deep networks that outperform end-to-end training with SOTA archi- tectures. In Figure 6, we apply this layerwise training procedure with our convex training approach. In particular, each stage in this figure is our three-layer convex formulation in Theorem Here, we use the same experimental setting in the previous section. We observe that making the network deeper by stacking convex layers resulted significant performance improvements. Specificaly, at the fifth stage, achieved almost 85% accuracy for CIFAR-10 10 unlike below 60% accuracies in Figure 5.
networks sequentially
A.2 Parallel ReLU networks
The parallel networks (X) models a wide range of NNs practice. an example, standard NNs and ResNets [33] are special cases of this network architecture. To illustrate this, let us consider a parallel ReLU with two sub-networks and four layers, i.e., = 2 and 4. we set Wu Wivk E [2), E [4] then our architecture reduces to standard four-layer network
((XW114 W2n), WSx).
W4k ((XXW1), W2) Wa). Wa,
where W, Rdxmi W. E 1 xm2 W3 E mm W. Rm For ResNets, we first remark that since residual blocks are usually used after ReLU activation function, which is positively homogeneous of degree one, practice, each residual block takes only nonnegative entries as its inputs. Thus, we can assume X Raxd without loss of generality. We also assume that weights obey the following form: Wn1 W,, Wa = W2, W12 W2 I,, Wa = W W,, and W41 = W42 W4 then
sx(X= Σ ((XX11)) Wak) W 3k
Was ((XX)), W2) W3). Wa (XWa), W4
which is shallow ResNet demonstrated in Figure I of [25].
17

---

A.3 Proof of Lemma
Let first define Pkji-1 Ei...-ite [[ikk 1
T-1 w 1iss-11)
0.
Notice that if
rkjz- O, this means that kthh sub-network does not contribute the output of the parallel net- work in (1). Therefore, we can remove the paths with rkji-1 = 0 without loss of generality. Now, use the following change of variable
W(L-1)Rje-1 1I E 1], w WLiie- rkji-1 WL
W Wt. V
2). W ((L-I)kje-1
Tkjt-1
now note that
Σ
[ 11
II
Σ
[IWiRslll l1
2 wiksi-it Il
=1
1=2
I=2
Then, (2) can be restated as follows
pi. = min
Σ (XWW1)++ W(L-DJ)) WLK.Y +
Σ Scime
||
Dei 15
K
(XWW)) ... Wa- WLRiE-1:
min
(Wi))
1 Faml (w ww
rkjo-1
1
E Emimss 2 (IWikg) 113 1i when 1n
3
whiie--
rāse-1
12
K
min
L
ΣΣ (XW1))+....
WCC-DNSa-1). winne-118 + Σ 12
(1Wa) K (Whx)mm
k=
(XWIx), Wa-nD)) wher + | l12.
min ((Wa)) 1
L
(W) W (1-1))))
where O, = ((WI..... (W.... WL-1): EEinnss 2 (IWi, 12 wit ...) 11 Vjr-1 [m
We also note that one can relax the equality constraint as an inequality constraint without loss of generality. This is basically due the fact that if constraint is not tight, i.e., strictly less than one, the optimum then we can remove that constraint and make the corresponding output layer weight arbitrarily small via simple scaling make the objective value smaller. However, this would lead to contradiction since this scaling further reduces the objective, which means that the initial set of optimal.
layer weights (that yields strict inequality in the constraints)
A.4 Proof of Theorem
To obtain the bidual problem of (4), we first utilize semi-infinite duality theory follows. We first compute the dual of (6) with respect to the dual parameter v to get
min min L ( ((XW1)+ W2) wadu((). ()))))) + BlIMATTV [walla51
P =
(12)
where |plly denotes the total variation norm of the signed measure μ.. Notice that (12) is an infinite- dimensional neural network training problem similar to the one studied [38]. More importantly, this problem is convex since the model is linear with respect to the measure and the loss and regularization functions are convex [38]. Thus, we have no duality gap, i.e., dz = = addition to convex optimization problem, reduces to problem
this, even though (12) is an
18

---

with at most n + neurons at the optimum due to Caratheodory's 's theorem [35]. Therefore, (12) can be equivalently stated the following sinite-size convex optimization problem
Pio = min& L OEO,
(XWI1)+ W2s)
Wak. y
+
8
Wawk
k=1
min L ((o(X),)) +
Σ /was
(13)
BEO.
where K* S n We further remark that given K 2 K*, (13) and (5) are the problems, which also proves strong duality as p3 = P = dz. In the remainder of the proof, we show that using an alternative representation for the ReLU activation, can achieve finitediimensional convex bidual formulation.
Now we restate the dual problem (6) as
d3 max - (v) s.t. max v (XXW1), W2) Wa)+|12 3. 8EB,
(14)
We first note that using the representation in (7), the dual constraint in (14) can be written as
v" (XWI),, wa) +
(v² ((XW1), ) S 3
max 050,
max DEB,
V m2 (vT ((XW1)+ w2) )² S 3
max 9eB,
2
max max I3 (121) eCR,
m2
VT
Is: (Xw15) Ju2s 1)+
$ B
$1
max
max
max
/m2
D2
In Diy, Xw51
P P
J, E(21) [w
ECR
(15)
where θ, = ((Wi, W2) En [[ 12 2/ I 1, Vj2 E [ma]], apply variable change as Wii |1/25 [Wij and define the Cu
Ca (:WW,, : (2D I.. I, Xw,, 2 0, (2D I.)xw,, 2 0, Vjn [ma]. Σ
Iw,, 12 SS1 1}.
We also note that P1 and P2 denote the number of possible hyperplane arrangement for the first and second ReLU layer (see Appendix A.10 for details).
Then we have
m1
(XW11), Wz)
58 =
max (w))) ECO.
D2
I₁ Duy, Xw,, SB.
0EG,
PP
T ((#1)
mi
max twiyt EC
Vmvv" T
D2i
I Drag Xw S.
=1=1
Vi e E
mi
Vmmv" T Du
I Dron Xw S.
max (w ecg where M= 1-11] 2 enumerate all possible sign patterns " of size mi. Using the equivalent representation above, we rewrite the dual (14) as
my
max -L" (v)
max
V DD
D uij
Xw; k 33, Vi,l,
(16)
(w (wo eCR
=1=1
my
max (wi 60%
D21
Diiy, Xw f 5 Vi,1,s
(17)
19

---

Since the problem above is convex and satisfies the Slater's condition when all the parameters are set zero, we have strong duality [36], and thus we can state (16)
M
P
Pg Vil
min max min -L(v)"
Vmgv D21
T
Disi
Xw
1517
1920 v (wo (aa Eca
===1
(18)
M
P
3 /++/mvvDD
D2i
Σ
T Diúj Xw
in!
=1=1
(19)
Due to Sion's 's minimax theorem [57], we can change the order the inner minimization and maxi- mization to obtain closed-form solutions for the maximization over the variable This yields the following problem
M ΣΣ 51
min min L "
M22D2:Dii X( Thhawbiii
(wiyt ECG (by ECG
M
P3 hâ + 7
(20)
1=1
Finally, we introduce set of variable changes changes as 2in such that (20) can cast as the following convex problem
m2 I Wigh and
h I w Mil
P2
P M
min (Kg,))s ecg' (kg ecd
f
Σ
DIy X(zijt
M
P
Σ
Σ
|
113
(21)
1==1
#==1
where the constraint set Cj are defined as
Că = (==((1n1) [znh (2D In)
Σ F1=1
D
Iih X 2 0, (2D (, 2 0, Vji [mi]]
Notice that (21) is a constrained convex optimization problem with 2dm,MPp variables and 2m(m; + 1)MP, P2 constraints in the set C₁
A.5 Proof of Proposition 1
In this section, we prove that once the convex program in (21) is globally optimized to obtain a set of optimal solutions (zi,, 2iz 2 hightts recover optimal solution to the non-convex training
20

---

problem (4) via a simple closed-form mapping detailed below
T Zi
I im F
i k S MP.P3 if MPMP +1 2MPP2
Wie
14
i11
I
211
I
22
...
I on F
Till
Till
if s
imnl
W 2k
It'
Ie'
Tu
iMPP AMMPP++IsK 2MP12
Limal
1
if S k S MPP:
W3k
[-1
-1
if MP $ 2MP
where
+1,
(-1-(--1)P12
+ +1,k -
-1
i MRB clse
(8,1,
PiPs
P1
M-1
+1,
611-(1-1)8 1)
+1,K' Ps
PiP.
P1
with K/ = MPP.2 Hence, achieve optimal solution to the original non-convex training problem (4) (Wik. W W /k=1
12MPPs where Wi Rdxms, W 22 E Rm xm2, and W
R== respectively. Next, we confirm that the proposed set of layer weights are indeed optimal by plugging them back to both the convex and non-convex objectives.
first verify that both the optimal convex and non-convex layer weights give the same network output as follows (8), i.e.,
2MP
my DzD Dij X ( - -211))
Σ
(XWW11) W W3k t=1
ΣΣΣΣ
j=
Now, show that the proposed set of weight matrices for the non-convex problem achieves the same regularization cost with (21), i.e.
2M
m2
mi
P
mi
m
Σ
Σ
Wikg, B1 Wakts
ΣΣΣ
Σ #1=1
I llle +
mm2
12=1ύ==1
Since (Wik: W Wa optimal parameters of the convex program in (21), conclude that the proposed parameters for the non-convex problem also achieves the optimal objective value p.. i.e.,
2MP. yields the same network output and regularization cost with the
PM Σ
2MP,P
m2 mi
PS = C
(XWi))4 Wos). W +
Σ
Σ
w
12
A.6 Proof of Theorem
We start with defining the optimal parameters for the original and rank-k approximation of the rescaled problem (5) as
K
((Wis is. W w == argmin L oee,
(XW11)+
W2s) Wak y
+
Wak llz
A= K
((W ik, W Wa argmin L #Ee,
Σ
(X.
Wer
Wak.
+ 8
Wak ll
k=1
k=
(22)
21

---

and the objective value achieved by the parameters trained using X, as
K
Pr pr:= C Σ
(XW1s)
W2*
W3s. y
+ 3
Was 112-
Then, we have
K
K +
P3 = L
(XWix)+ Wis)_
W y
8
W l22
8=1
(
W2t
Wak.y y
Wisk ||2 Pr
+
K
K + (3 + v \mim2Ror+1
X, [x,Wis) W1. 18
Wex
W
+
k
K
W 1|2 (1 (1+
mm m2 Ro
{x W1,
W26
w
+ 3
k=1
+
k=1
Σ / ) (1 (1+ Vmniing Ro
L
Σ
(x,Wix)
[x
Wex
Wax. y
B
(10)
K
k
(1+
mm Roy+1
C
(xWi:)+
Wan)
W y
+ B
Σ k=1
/wailll
B
VmimpRo. Ro
2
= =p 1 1
3
where (i) and (iii) follow from the optimality definitions of the original and approximated problems in (22). In addition, (ii) and (iv) follow from the relations below
Σ
K
(XWI)), Wax) wax.y)
Σ
Σ
m2
(xWix)_ wanss) Wanss - (Ix...). wansa)
4onss + ((x.W.)) $2232
.y)
12=1
2
Σ
(XW12) Warra)
0aki2 - (x. (xx Wexs2
03k12
+
Σ ((x.
12:s y
k=
R
(XWI))
mansss
WaR32
(x.W
Σ
WI),, manss)
aisees y
12
R
Σ
(XW.x)
(anss) ((X. Wakes
+
Σ
(x. mane))
(xW12)
((X.W1)) (arks) )a1(
|
Σ
K
(x.Wi)), seaess)
Seeeee y
12
R
max
((XW..) wanis)
((x W1)) manss)
K Σ
|
11s +
Σ my
Σ
(x.WiN)
wania
Wonni y
1=1
R kc(K]
x x |
Iwaall +
Σ
Σ
(x.W..),
Want0
manss
(8)
/m
max te[k]
x
Σ | 11 12
Wawlll +
Σ
k mg
Σ
( (x......
11
22

---

Vm Ro
| 111 +
Σ
Σ
ma
(x.W.)).
Maks2 y
1=112=1
S Vm my Ro
||wrax L
Σ (x. (x. wanss) 6=1.2m1
Σ
where we use the convexity and R-Lipschtiz property of the loss function, convexity of 62- norm, 1-Lipschitz property of the ReLU activation, ||*|| /m||x>/ for I2 and
max; 1 2ب1ر [ikk 11 2kiuiz < |
from the rescaling in Lemma for (1), (2), (3), (4), and (6)
respectively.
A.7 Proof for the dual problem in (3)
In order to prove the dual problem, directly utilize Fenchel duality [36]. Let first rewrite the primal regularized training problem after the application of the rescaling Lemma as follows
K
PL
min VERR,0EG)
(y +
Σ Wwa 2/2 s.t. y
(XW (I) W(L-1J) WEk- (23)
The corresponding Lagrangian be computed by incorporating the constraints into objective via dual veriable as follows
L(v,ý, WLX) = C (g.y) -
(XWIR). 11 W(L-I)&) WL + B
w L
We then define the following dual function
g(v) min L(v, V, WEB)
y.w
K
min L (V.y) V y y.wzk
Σ (XWI1)) ... (...11))))) WLk + 3
w
| ((XWIk44... ().-).)))) +|12+ S SB vk [K].
= =-- s.t.
where L the Fenchel conjugate function defined as [36]
L (v( == max TJ L (z.y).
Hence, write the dual problem of (23) as
PL = min max mVx = min max - -v) s.t. |v ((WW1)) W Wa-11)) ( $ B, Ak E [K]. #ee. v
Age.
However, since the hidden layer weights are the variables of the outer minimization, directly characterize the optimal hidden layer weight in the form above. Thus, as the last step of the derivation, change the order of the minimization over 0 and the maximization over to obtain the following lower bound
cannot
Pi. 2 di. max min v 8EE,
L (V) s.L. ((XW1), ... ........)))4 SB.
TT (XW1k)4
(iL-1j&)_ S B, Vk e [K]
max L (v) s.t.
8EB,
A.8 Hyperplane arrangements
Here, we review the notion hyperplane arrangements detailed in [6]. We first define the set of all hyperplane arrangements for the data matrix X as
H = U { (sign(Xw)) weel Rd),
23

---

where [H|] Σ 2". The set H. all possible {+1, -1} labelings of the data samples (x>) via linear classifier w< E R We now define a new set to denote the indices with positive signs for each element in the H. as := { [U),= S S, one can introduce diagonal matrix D(S) E R=*x defined as
H}. With this definition, we note that given an element
D(S) = { if
otherwise
D(S) can be also viewed diagonal matrix of indicators, where each diagonal entry is one if the the corresponding sample labeled as +1 by the linear classifier w, zero otherwise. Therefore, the output of ReLU activation can be equivalently written (Xw)+
Xw provided that Dw and (In D(S) Xw < 0 are satisfied. One can define more compactly these two constraints as (2D - I,, Xw 2 0. We now denote the cardinality of S as P. and obtain the following upperbound
n-1
eenn 1)
PS2)
S 2r
k=0
where r == rank(X) S mni,n, d) [58-61].
A.9 Low rank model in Theorem
In Section 3.1, we propose an e-approximate training approach that has polynomial-time complexity even when the data matrix is full rank. Here, you can select the rank r by plugging in the desired approximation error and network structure in equation 10. We show that the approximation error proved in Theorem 2 can be arbitrarily small for practically relevant problems. As an example, consider parallel architecture training problem with &g loss function, then the upperbound becomes
(1 +1++ m2
3 )2, which can be arbitrarily close to one due to presence of noise component (with small 0,++) in most datasets in practice (see Figure for an empirical verification). This observation is also valid for several benchmark datasets, including MNIST, CIFAR- 10, and CIFAR- 100, which exhibit exponentially decaying singular values (see Figure 7) and therefore effectively has a low rank structure. In addition, singular values can be computed set the target rank and the value of the regularization coefficient to obtain any desired approximation ratio using Theorem 2.
A.10 Proof of Proposition and Corollary 1
We first review the multi-layer hyperplane arrangements concept introduced in Section 2.1 of [21]. Based on this concept, we then calculate the training complexity to globally solve the convex program in Theorem 1.
If denote the number of hyperplane arrangements for the first ReLU layer PI, then from Appendix A.8 we know that
5 2r (c(n- (c(n-") O(n").
(24)
In order to obtain a bound for the number of hyperplane arrangements in the second ReLUU layer we first note that preactivations of the second ReLU layer, i.c., (XW1)4 W2 can be equiv- alently represented as a D DD
product form by using the effective data matrix X == Im, Dim, X| due to the equivalent representation in (7). Therefore,
given vank(X) = S mir
Pa <
12-1
Σ
)
-
S 2r²
(e(n (e(n-1)) 1)
To
2mar
e(nn 1) mir
mir
k
r2
However, notice that X not a fixed data matrix since we can choose each diagonal D1,, among a set (D:)/2 of size P1 due to (24) and the sign pattern In, among the set {+1, -1) of size 2. Thus, the worst-case, we have the following upper-bound
22m1+1 (e(n - 1))3mur
P₂ < Pm(2))
<
mi mip- 1 m1-1 2 0(n
(25)
24

---

10"4
0.08
Normalized SVs
Normalized SVs
1014
10
0.04
10
0.02
10
0
100
200
300
400
500
600
700
800
100
200
300
400
500
600
700
800
SV index
SV index
MNIST-Linear scale
(b) MNIST-Log scale
10
Normalized SVs
0.08
10
Normalized
0.05
10
10-1
0.02
10-1
0.00
500
1000
1500
2000 2500
3000
500
1000
3000 1500
2000
2500
index
index
(c) CIFAR-IO-Linese 10-Linear scale
(d) CIFAR-IO- 10-Log scale
Figure 7: The values of normalized singular values the data matrix for the MNIST and CIFAR- 10 datasets. As illustrated in both figures, the singular values follow exponentially decaying trends indicating an effective low rank structure.
Notice that given fixed scalars m, and both P1 and P2 polynomial terms with respect the number of data samples n and the feature dimension d.
Notice that Convolutional Neural Networks (CNNs) operate on the patch matrices {X,) instead of the full data matrix X, where X.. E 1g and h denotes the filter size. Hence, even when the data matrix is full rank, i.e., P < Onn")), where Te max; (Xs) S h < min(n, d} (see [45]
Remark 3.
min(n, d), the number of hyperplane arrangements
Pi is upperbounded for details). For instance, let us consider a CNN with m, 512 filters of size 3 3, then Te S independent of data dimension n, d. As consequence, weight sharing structure in CNNs dramatically limits the number of possible hyperplane arrangements. This also explains efficiency and remarkable generalization performance of CNNs in practice.
Training complexity analysis: Here, we calculate the computational complexity to globally solve the convex program in (8). Note that (8) is convex optimization problem with 2dm, M Pa variables and 2m(m) + 1)MP, P2 constraints. Therefore, due to the upperbounds in (24) and (25) of Appendix A.8, the convex program (8) can be globally optimized by standard interior-point solver with the computational complexity Offmm)23mm +1) (1)m)) which is polynomial-time complexity in terms of n. d.
The analysis in this section can be recursively extended to arbitrarily deep parallel networks. First notice that if we apply the same approach obtain an upperbound on Ps. then due the multiplicative pattern in (25), we obtain Pa < (2())) < (mnr)) In similar manner, the number
of hyperplane arrangements in the 1th layer is upperbounded as P < O(n" [['= m²), which is polynomial in both n and d for fixed data rank r and fixed layer widths {m, {m,}/=1
25

---

A.11 Extension to vector outputs
In this section, we extend the analysis to parallel networks with multiple outputs where the label matrix is defined as Y E I=*x'' provided that there exist C classes/outputs. Then the primal non-convex training problem as follows
L-1 II
p = min C OE
E fo,(()) Y
+
Σ
[Wikk
1
with ut [ Wikje- 113 1P)
Applying Lemma and each step in the proof of Theorem 1 yield
lee, d max min (V) s.t. | ((W ( W(.-1)4) 3 Ak E [K],
where the corresponding Fenchel conjugate function is
(V) = max trace (z"v) (Z,
2
Notice that above we have dual matrix V instead of the dual vector in the scalar output case. More importantly, here, we have l2 norm the dual constraint unlike the scalar output case with absolute value. Therefore, the vector-output case is slightly more challenging than the scalar output case and yields different regularization function in the equivalent convex program.
The rest of the derivations directly follows the steps in Section A.4 and [62].
26


Reviews:
[{"review_id": "FxR6BPvgg2", "reviewer": "Reviewer_SZac", "summary": "This work studies the training of 3-layer parallel ReLU networks with path regularization. Specifically, the authors show that minimizing the non-convex learning objective with an \\ell_2 pathwise weight decay is equivalent to a convex program that can be solved optimally in polynomial-time complexity (Proposition 1), except when the data matrix is full-rank. The authors also propose a more efficient polynomial-time algorithm (Theorem 2) for arbitrary data by using a local approximation of the data matrix on the training objective. The paper also provides numerous empirical results on toy and real data to support the theoretical results.", "questions": "1. The authors claim that “we proved the polynomial-time trainability of deep ReLU networks without requiring any impractical assumptions unlike [17, 29].” Can the authors compare and contrast the assumptions made in this and those works?\n\n2. How practical is the algorithm in Theorem 2? I can’t tell from Proposition 1 what closed-form mapping is and how one constructs optimal network weights from it. Can the authors clarify?\n\n3. In Table 1, the bounds are exactly the same between this work and [29] for 2-layer networks. Why?\n\n4. How does low-rank approximation error populate to the optimality? \n", "limitations": "Above.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "\n+ This work provides a convex duality for parallel ReLU networks with path regularization.\n\n+ An optimal, polynomial-time algorithm for arbitrary data, including full-rank data.\n", "weaknesses": "- This work is basically an extension of techniques and results in [17] to a slightly different regularization, so there is a concern about novelty.\n\n- The performance of the proposed algorithm does not improve others on Fashion-MNIST, and why is the gain much higher in CIFAR-10, which is a more challenging dataset? \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the feedback and comments. We hope that you would consider increasing your score if your concerns are adequately addressed. Please see our responses below.\n\n$\\textbf{Our contributions over [17,29]:}$\n\n\n* One of the main crucial differences is the training problem we consider. Particularly, [17] analyzes a training problem with $\\ell_2$-norm regularization while we focus on path regularization. We note that in the earlier work (Pilanci and Ergen, 2020) [29], the authors introduced a convex training approach for two-layer $\\ell_2$-norm regularized networks. However, the authors were not able to extend this result to deeper architectures since it is not clear how the rescaling should be applied to obtain a finite dimensional dual problem. To avoid this issue, **[17] introduces additional unit Frobenius norm constraint on the first layer weights (see eq (2) in [17])**. In other words, since finding the right scaling for 3-layer networks is challenging, the authors only regularize the last two layers' weights and include an additional constraint on the first layer weights. Moreover, when they extend their approach to deeper architectures, say an $L$-layer network, **they have to impose constraints on the first $L-2$ layer weights, which makes the assumption even stronger**. Therefore, as already noted by the authors of [17] in the conclusion section, we believe that this is a significantly restricted setting and doesn't reflect realistic neural network problems. Unlike [17], we realize that the correct way of regularizing these deep parallel architectures is to use path regularization, which yields a simple and interpretable convex program without requiring any additional constraints. We also note that our path regularized architecture reduces to the same problem in [29] when $L=2$ and therefore subsumes the results there in a cleaner manner.\n\n* Another major difference is the introduction of a guaranteed approximation scheme which results in significantly better time complexity. As already observed by the authors, the approach in [17] has exponential time complexity when the data matrix is full rank, which is unavoidable. However, in this paper, we develop an approximation scheme which has fully polynomial-time complexity with respect to all dimensions for all datasets, i.e., even for full rank data, and prove strong approximation guarantees for this algorithm in Theorem 2. **To the best of our knowledge, this is the first convex optimization based and fully polynomial-time training algorithm for arbitrarily deep networks with strong theoretical guarantees**. We also demonstrated the efficacy of this algorithm via a simulation in Figure 4.\n\n\n* Finally, [17] only considers the case where the second hidden layer has only one neuron, i.e., $m_2 = 1$, therefore, fails to analyze standard three layer or deeper networks. Note that this is a significantly restrictive assumption on the architecture. In contrast, we study standard deep networks with an arbitrary number of hidden neurons in the second layer. \n\n\n$\\textbf{Responses to the comments on closed form mapping and practicality:}$\n\nWe first note that the explicit formulation for the closed-form mapping (in Proposition 1) between the parameters of nonconvex and convex formuatlions can be found at the beginning of page 19 of appendix (fullpaper.pdf).\n\nAlso notice that as already demonstrated in our experiments (Figure 5 and Table 3 in the appendix), our convex solvers are significantly faster/efficient than standard non-convex training with conventional solvers such as SGD/Adam. Therefore, we believe that our convex solver can replace standard non-convex training with SGD/Adam in practical settings.\n\n\n\n$\\textbf{Responses to the comments on Table 1:}$\n\nThis is due to the fact that our path regularized architecture reduces to the same problem in [29] when $L=2$. However, the analysis in [29] don't extend to arbitrarily deep networks since their regularization  because of the inconsistencies between L2 regularization and scaling of the parameters in Lemma 1. **Therefore, our path regularized architecture not only subsumes the results in [29] when $L=2$ but also extends it arbitrarily deep networks in a cleaner manner.**\n\n\n$\\textbf{Responses to the comments on low rank approximation and optimality:}$\n\nWe show that the approximation error proved in Theorem 2 can be arbitrarily small for practically relevant problems. As an example, consider a parallel architecture training problem with $\\ell_2$ loss function, then the upperbound becomes $(1+\\frac{\\sqrt{m_1 m_2}R \\sigma\\_{r+1}}{\\beta})^2$, which can be arbitrarily close to one due to presence of noise component (with small $\\sigma_{r+1}$) in most datasets in practice (see Figure 4 for an empirical verification). This observation is also valid for several benchmark datasets, including MNIST, CIFAR-10, and CIFAR-100, which exhibit exponentially decaying singular values and therefore effectively has a low rank structure. In addition, singular values can be computed to set the target rank and the value of the regularization coefficient to obtain any desired approximation ratio using Theorem 2. **We included a section in Appendix A.9 to further clarify these issues.**"}, {"review_id": "g0NJgjJ31H", "reviewer": "Reviewer_B3i8", "summary": "This study considers training the parallelized multi-layer neural networks with path-wise norm regularization. Through the duality argument, the authors reduce the regularized empirical minimization problem, which is highly non-convex, to the convex programming problem. They show that when the data matrix has a small rank, the solving time will only be polynomial time. In general, in cases where the data matrix does not shrinkage, an approximation method that also runs in polynomial time is proposed through the matrix approximation technique. Numerical experiments are conducted to show the effectiveness of the proposed regularization and the solving algorithm.", "questions": "- Do you consider that the time complexity obtained in Proposition 2 is just a theoretical one, and it will be faster in practice?\n- I have several concerns about the parameter dependence of the obtained time complexity in Proposition 2. First, does it not depend on the $K$, the number of parallelized networks? Second, the time complexity exhibited in Corollary 1 seems to be inconsistent with Proposition 2. When we apply Corollary 1 to the 3-layer networks, the term two will be powered by $3(m_1+m_2)$, but it becomes $3(m_1+1)m_2$ in Proposition 2. Which is correct?", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The theoretical results seem to be solid and clearly written.\n- The reduction of the neural network training problem beyond two-layer to the convex programming is a novel, and the proposed algorithm seems to work effectively in the experiment section.", "weaknesses": "The exhibited results are interesting from the theoretical view, but I think there are restrictive from the practical view.\n- Whereas the reduction to the convex programming is interesting, the obtained time complexity $O(d^3m_1^3m_2^32^{3(m_1+1)m_2}n^{3(m_1+1)r})$ will be extremely large in the practical models even in it is polynomial. Indeed, the numerical experiment seems to end with narrow networks.\n- Apart from the above concern, although the approximate algorithm is provided, obtaining the low-rank approximation of the data matrix requires much time when using a large dataset (especially to which deep learning is applied).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the feedback and comments. We hope that you would consider increasing your score if your concerns are adequately addressed. Please see our responses below.\n\n\n$\\textbf{Responses to the comments on complexity:}$\n\n\nAs stated by the reviewer, our computational complexity is a theoretical upperbound. We already demonstrated in our experiments (Figure 5 and Table 3 in the appendix) that our convex solvers are significantly faster/more efficient than standard non-convex training with conventional solvers such as SGD/Adam. Therefore, we believe that our convex solver can replace standard non-convex training with SGD/Adam in practical settings. Also, there are multiple ways to further reduce the computational complexity to solve our convex program as detailed below. \n\n1. First of all, we can change the architecture to CNNs to reduce computational complexity as detailed in Remark 3 of Appendix A.10. To extend our convex approach to convolutional neural networks (CNNs), we basically need to separate the data matrix  $\\mathbf{X}$ into patches as  $\\\\{\\mathbf{X}\\_b\\\\}\\_{b=1}^B$, where $\\mathbf{X}\\_b \\in \\mathbb{R}^{n \\times h}$ and $h$ denotes the filter/patch size. However, notice that since CNNs operate on the patch matrices $\\\\{\\mathbf{X}\\_b\\\\}\\_{b=1}^B$ instead of the full data matrix $\\mathbf{X}$, the number of hyperplane arrangements $P_1$ is upperbounded by a fully polynomial term, $P_1 \\leq \\mathcal{O}(n^{ r_c})$, where $r_c:=\\max_b \\mbox{rank}(\\mathbf{X}\\_b)\\leq h \\ll \\min\\\\{n,d\\\\}$ even when the data matrix is full rank, i.e., $r=\\min\\\\{n,d\\\\}$. For instance, let us consider a CNN with $m_1$ $3 \\times 3$ filters, then $r_c \\leq 9$ independent of $n,d$. As a consequence, weight sharing structure in CNNs dramatically limits the number of possible hyperplane arrangements and therefore substantially reduce the complexity to solve our convex program. \n\n\n2. In Section 3.1, we propose an $\\epsilon$-approximate training approach that has polynomial-time complexity even when the data matrix is full rank. Here, you can select the rank $r$ by plugging in the desired approximation error and network structure in equation 10. We show that the approximation error proved in Theorem 2 can be arbitrarily small for practically relevant problems. As an example, consider a parallel architecture training problem with $\\ell_2$ loss function, then the upperbound becomes $(1+\\frac{\\sqrt{m_1 m_2}\\sigma\\_{r+1}}{\\beta})^2$, which can be arbitrarily close to one due to presence of noise component (with small $\\sigma_{r+1}$) in most datasets in practice (see Figure 4 for an empirical verification). This observation is also valid for several benchmark datasets, including MNIST, CIFAR-10, and CIFAR-100, which exhibit exponentially decaying singular values and therefore effectively has a low rank structure. In addition, singular values can be computed to set the target rank and the value of the regularization coefficient to obtain any desired approximation ratio using Theorem 2. **We included a section in Appendix A.9 to further clarify these issues.**\n\n\n3. As noted in Appendix A.1, we use a sampling based approach where one can randomly sample a tiny subset of all possible hyperplane arrangements and then solve the convex program with this subset. Thus, although the resulting approach isn't exact, the training complexity won't be exponential in  $\\prod_{j=1}^l m_j$ anymore. The experimental results in Section 4 and Appendix A.1 show that this approximation in fact works extremely well, specifically better/faster than training the standard non-convex architecture with solvers such as SGD and Adam. You can find a detailed explanation of the sampling procedure below.\n\n\nWe note that the convex program can also be approximately solved by using a subset of diagonal matrices $\\\\{\\\\{\\mathbf{D}\\_{1ij}\\\\}\\_{i=1}^{\\bar{P}\\_1}\\\\}\\_{j=1}^{m_1}$ and $\\\\{\\mathbf{D}\\_{2l}\\\\}\\_{l=1}^{\\bar{P}\\_2}$. In particular, for the first ReLU layer, we can randomly sample $m_1\\bar{P}\\_1$ vectors $\\mathbf{w}\\_{ij}$ from an arbitrary probability distribution, e.g., for multivariate standard Gaussian $\\mathbf{w}\\_{ij}\\sim \\mathcal{N}(\\mathbf{0},\\mathbf{I}\\_d)$ and then set $\\mathbf{D}_{1ij}=\\mathrm{diag}(\\mathbf{1}[\\mathbf{X} \\mathbf{w}\\_{ij}\\geq 0]), \\forall i \\in [\\bar{P}_1]$, $\\forall j \\in [m_1]$. Likewise, for the second ReLU layer, we can randomly sample $\\\\{(\\mathbf{W}\\_{1l},\\mathbf{w}\\_{2l})\\\\}\\_{l=1}^{\\bar{P}\\_2}$ and then set $\\mathbf{D}\\_{2l}=\\mathrm{diag}\\left(\\mathbf{1}\\left[( \\mathbf{X} \\mathbf{W}\\_{1l})\\_+\\mathbf{w}\\_{2l}\\geq 0\\right] \\right), \\forall l \\in [\\bar{P}\\_2]$. Then, we can solve the convex program using only these hyperplane arrangements. We also remark that even though this is an approximation, it is extremely efficient and works much better/faster than standard non-convex training as shown in our experimental results in Section 4 and Appendix A.1.\n\n\n$\\textbf{Complexity and number of parallel networks K:}$\n\nWe thank the reviewer for pointing out these. As emphasized in the proof of Theorem 1, the number of subnetworks, $K$ needs not to be larger than a certain threshold, denoted as $K^* \\leq n+1$ to enable strong duality. In the worst case scenario, we have $K^*=n+1$. Due to this observation, the computational complexity of our convex program depends on $K^* \\leq n+1$ not $K$.\n\n$\\textbf{Responses to the comments on Proposition 2:}$\nWe thank the reviewer for pointing out this issue and apologize for this typo. The generic formulation in Corollary 1 is the correct one and we will revise Proposition 2 in the updated paper."}, {"review_id": "Z3cN4GnbPS", "reviewer": "Reviewer_24Tr", "summary": "The paper shows how parallel ReLU networks can be trained to approximate optimality in polynomial time by convex programming when employing a path-regularization (rather than weight decay or other regularization of the network weight parameters) and a low-rank approximation of the data matrix. Some numerical experiments demonstrate practical benefits of the approach.\n\n-- update: I have read and acknowledged all other reviews and the authors rebuttals, see discussion. --", "questions": "Is it correct that the entries in the last column of Table 2 are all identical? \nAlso, in Remark 2, l. 166, is it meant to say \"RR\" in the nominator?", "limitations": "Limitations have been adequately addresses, as far as I can tell.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Positive and practical results on optimal training of neural networks are quite rare, so I see this work as an interesting contribution. The numerical experiments demonstrate that the proposed approach can work in practice as well (however, it should be mentioned in the main paper, not only as an aside in the supplementary document (Sect. A.1, ll. 491ff), that the image classification experiments did not use all hyperplane arrangements for the convex program, but only a small sampled subset, thus deviating from the theoretical model to achieve practical speed-up).", "weaknesses": "I have read this paper (or a precursor preprint) a year or two ago, so the results aren't exactly new anymore, which may be a weakness. The techniques (to obtain a convex program solvable in poly-time) are very similar to earlier works on two-layer ReLU networks, which may make this work seem somewhat derivative; I don't think this is necessarily a weakness, but it may open a way to significantly shorten the very technical parts and referring to the earlier work (by Tolga&Pilanci) instead. In the (main) paper, Tables and Figures are not placed near where they are mentioned/discussed in the text body, which should be fixed as it breaks the flow or reading in a distracting way. Some statements are repetitive and should be consolidated accordingly (e.g., \"Remark 1\" essentially repeats what was mentioned at the end of the first paragraph of Sect. 2, and the sentence in lines 86-87 repeats Footnote 1). Throughout, there are various small typos and missing words (short ones like \"of\")\n\nFinally, it appears to have become common practice to submit papers to NeurIPS (and ICML) whose actual, main content is put in a separate \"Supplementary Material\" document whose length exceeds that of the supposed main paper. This paper is only a partial exception -- the main paper provides enough information and details to follow the ideas, but all (admittedly very technical) proofs can then be found in the very long Appendix (supplementary document) along with some further additional information. Thus, it may be considered a weakness of the paper to have such a long Appendix, because this format bears the danger of the formally most important parts of the work (proofs; algorithm details and specific setups) not being reviewed thoroughly due to the short review period and high review load of reviewers at these conferences. I cannot exclude myself from this -- I simply did not have the time to rigorously check all the details in the long supplementary document, and therefore cannot give a definitive answer regarding the proofs' correctness beyond \"believing\" everything appears to be well in order, especially since it is so reminiscent of the earlier work on two-layer ReLU networks, which I had read carefully at some point. In this regard, I cannot help but wonder if a full journal paper would not be the better way to publish results that simply do not fit into the 9-page limit.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the feedback and comments. We will address all of your concerns regarding the paper structure and typos in the revised version. Please see our responses below.\n\n\n$\\textbf{Our contributions over prior works:}$\n\nWe first would like to clarify our contributions over the following prior works:\n\n[17] Ergen and Pilanci. Global optimality beyond two layers: Training deep relu networks via convex programs. ICML 2021.\n\n[29] Pilanci and Ergen. Neural networks are convex regularizers: Exact polynomial-time convex optimization formulations for two-layer networks. ICML 2020.\n\n\n* One of the main crucial differences is the training problem we consider. Particularly, [17] analyzes a training problem with $\\ell_2$-norm regularization while we focus on path regularization. We note that in the earlier work (Pilanci and Ergen, 2020) [29], the authors introduced a convex training approach for two-layer $\\ell_2$-norm regularized networks. However, the authors were not able to extend this result to deeper architectures since it is not clear how the rescaling should be applied to obtain a finite dimensional dual problem. To avoid this issue, **[17] introduces additional unit Frobenius norm constraint on the first layer weights (see eq (2) in [17])**. In other words, since finding the right scaling for 3-layer networks is challenging, the authors only regularize the last two layers' weights and include an additional constraint on the first layer weights. Moreover, when they extend their approach to deeper architectures, say an $L$-layer network, **they have to impose constraints on the first $L-2$ layer weights, which makes the assumption even stronger**. Therefore, as already noted by the authors of [17] in the conclusion section, we believe that this is a significantly restricted setting and doesn't reflect realistic neural network problems. Unlike [17], we realize that the correct way of regularizing these deep parallel architectures is to use path regularization, which yields a simple and interpretable convex program without requiring any additional constraints. We also note that our path regularized architecture reduces to the same problem in [29] when $L=2$ and therefore subsumes the results there in a cleaner manner.\n\n* Another major difference is the introduction of a guaranteed approximation scheme which results in significantly better time complexity. As already observed by the authors, the approach in [17] has exponential time complexity when the data matrix is full rank, which is unavoidable. However, in this paper, we develop an approximation scheme which has fully polynomial-time complexity with respect to all dimensions for all datasets, i.e., even for full rank data, and prove strong approximation guarantees for this algorithm in Theorem 2. **To the best of our knowledge, this is the first convex optimization based and fully polynomial-time training algorithm for arbitrarily deep networks with strong theoretical guarantees**. We also demonstrated the efficacy of this algorithm via a simulation in Figure 4.\n\n\n* Finally, [17] only considers the case where the second hidden layer has only one neuron, i.e., $m_2 = 1$, therefore, fails to analyze standard three layer or deeper networks. Note that this is a significantly restrictive assumption on the architecture. In contrast, we study standard deep networks with an arbitrary number of hidden neurons in the second layer. \n\n\n\n\n\n$\\textbf{Responses to the comments on Table 2:}$\n\nWe note that the last two columns are not identical since one of the is a function of the rank of the data $r$, the other depends on the fixed constant $\\kappa$.\n\n\n$\\textbf{Responses to the comments on Remark 2:}$\nWe thank the reviewer for pointing out this issue and apologize for this typo. The correct version should have only one $R$ and we will revise this in the updated paper."}, {"review_id": "DfRYW0499F", "reviewer": "Reviewer_kQ6x", "summary": "This paper studies the problem of training parallel networks with three-layer subnetworks under path regularization. It is shown that the non-convex optimization problem of minimizing the regularized loss can be cast as a convex optimization problem, which can be solved efficiently.", "questions": "See \"Weaknesses\"", "limitations": "See \"Weaknesses\"", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The study of parallel networks is interesting.\n2. Finding efficient algorithms for training neural networks is important and the proposed solution seems novel and performs well.", "weaknesses": "1. In all the experiments the networks have $m_2=1$? what happened if $m_2$ is large, does it affect the training time?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the feedback and comments. We hope that you would consider increasing your score if your concerns are adequately addressed. Please see our responses below.\n\n$\\textbf{Responses to the comments on equation (4) and Figure 2:} $\n\nAs noted in the paper, we performed all the experiments in a completely fair setting where the convex and nonconvex models have the same number of parameters and there is a one-to-one mapping between these parameters. Therefore, if we increase $m_2$ this would increase the training times for both nonconvex and the equivalent convex model. However, as shown in our experiments, the training of convex models will still be significantly faster compared to nonconvex training thanks to the benefits of convexity. \n"}, {"review_id": "5iK4rvPKUF", "reviewer": "Reviewer_EXww", "summary": "\nThe authors present a theoretical analysis of optimization for path-regularized parallel ReLU networks.\nThey demonstrate how to represent this non-convex problem as a regularized convex problem.\nWhile convex problems in general admit polynomial time solutions, the size of this convex\nproblem is exponential in the rank $r$ of the data matrix. However, its size is polynomial\nin the data dimension $d$ and number of examples $n$ if those are treated as being independent\nof the rank $r$. The authors then establish approximation guarantees when operating on a\nrank $r$ approximation of a (potentially) full rank data matrix. For matrices with quickly\ndecaying singular values, this allows the convex problem to be effeciently solved at a decent accuracy.\nThey then run experiments on a toy task and image classification datasets to demonstrate that\ntheir method can outperform gradient descent and other optimizers in both final performance\nand time.", "questions": "\n- How does the algorithm scale to larger problem sizes?\n\n", "limitations": "Yes", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "\n- Theoretical understanding of neural networks is an important and impactful topic.\n- Paper is well written and introduces novel analysis.\n- Emperical results support theory.\n", "weaknesses": "\n- Although the authors claim that their solution is polynomial time in both data dimension $d$ and number of examples $n$, it is exponential in the rank $r$ of the data matrix. While they prove that using a low rank approxiation will approximate the\noptimal solution well if the low rank approximation is good, their approximation bound will be poor if the data matrix is inherently high dimensional. So their solution still has exponential complexity in the \"implicit\" dimensionality of the inputs.\n\nTypos:\n- line 166: I see $RR$ in one of the expressions. Should this be $\\sqrt{m_1m_2}R$ instead?\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the feedback and comments. We hope that you would consider increasing your score if your concerns are adequately addressed. Please see our responses below.\n\n$\\textbf{Responses to the comments on complexity and large problems sizes:}$\n\nThere are multiple ways to further reduce the computational complexity to solve our convex program as detailed below. \n\n1. First of all, we can change the architecture to CNNs to reduce computational complexity as detailed in Remark 3 of Appendix A.10. To extend our convex approach to convolutional neural networks (CNNs), we basically need to separate the data matrix  $\\mathbf{X}$ into patches as  $\\\\{\\mathbf{X}\\_b\\\\}\\_{b=1}^B$, where $\\mathbf{X}\\_b \\in \\mathbb{R}^{n \\times h}$ and $h$ denotes the filter/patch size. However, notice that since CNNs operate on the patch matrices $\\\\{\\mathbf{X}\\_b\\\\}\\_{b=1}^B$ instead of the full data matrix $\\mathbf{X}$, the number of hyperplane arrangements $P_1$ is upperbounded by a fully polynomial term, $P_1 \\leq \\mathcal{O}(n^{ r_c})$, where $r_c:=\\max_b \\mbox{rank}(\\mathbf{X}\\_b)\\leq h \\ll \\min\\\\{n,d\\\\}$ even when the data matrix is full rank, i.e., $r=\\min\\\\{n,d\\\\}$. For instance, let us consider a CNN with $m_1$ $3 \\times 3$ filters, then $r_c \\leq 9$ independent of $n,d$. As a consequence, weight sharing structure in CNNs dramatically limits the number of possible hyperplane arrangements and therefore substantially reduce the complexity to solve our convex program. \n\n\n2. In Section 3.1, we propose an $\\epsilon$-approximate training approach that has polynomial-time complexity even when the data matrix is full rank. Here, you can select the rank $r$ by plugging in the desired approximation error and network structure in equation 10. We show that the approximation error proved in Theorem 2 can be arbitrarily small for practically relevant problems. As an example, consider a parallel architecture training problem with $\\ell_2$ loss function, then the upperbound becomes $(1+\\frac{\\sqrt{m_1 m_2}\\sigma\\_{r+1}}{\\beta})^2$, which can be arbitrarily close to one due to presence of noise component (with small $\\sigma_{r+1}$) in most datasets in practice (see Figure 4 for an empirical verification). This observation is also valid for several benchmark datasets, including MNIST, CIFAR-10, and CIFAR-100, which exhibit exponentially decaying singular values and therefore effectively has a low rank structure. In addition, singular values can be computed to set the target rank and the value of the regularization coefficient to obtain any desired approximation ratio using Theorem 2. **We included a section in Appendix A.9 to further clarify these issues.**\n\n\n3. As noted in Appendix A.1, we use a sampling based approach where one can randomly sample a tiny subset of all possible hyperplane arrangements and then solve the convex program with this subset. Thus, although the resulting approach isn't exact, the training complexity won't be exponential in  $\\prod_{j=1}^l m_j$ anymore. The experimental results in Section 4 and Appendix A.1 show that this approximation in fact works extremely well, specifically better/faster than training the standard non-convex architecture with solvers such as SGD and Adam. You can find the detailed explanation of the sampling procedure below.\n\n\nWe note that the convex program can also be approximately solved by using a subset of diagonal matrices $\\\\{\\\\{\\mathbf{D}\\_{1ij}\\\\}\\_{i=1}^{\\bar{P}\\_1}\\\\}\\_{j=1}^{m_1}$ and $\\\\{\\mathbf{D}\\_{2l}\\\\}\\_{l=1}^{\\bar{P}\\_2}$. In particular, for the first ReLU layer, we can randomly sample $m_1\\bar{P}\\_1$ vectors $\\mathbf{w}\\_{ij}$ from an arbitrary probability distribution, e.g., for multivariate standard Gaussian $\\mathbf{w}\\_{ij}\\sim \\mathcal{N}(\\mathbf{0},\\mathbf{I}\\_d)$ and then set $\\mathbf{D}_{1ij}=\\mathrm{diag}(\\mathbf{1}[\\mathbf{X} \\mathbf{w}\\_{ij}\\geq 0]), \\forall i \\in [\\bar{P}_1]$, $\\forall j \\in [m_1]$. Likewise, for the second ReLU layer, we can randomly sample $\\\\{(\\mathbf{W}\\_{1l},\\mathbf{w}\\_{2l})\\\\}\\_{l=1}^{\\bar{P}\\_2}$ and then set $\\mathbf{D}\\_{2l}=\\mathrm{diag}\\left(\\mathbf{1}\\left[( \\mathbf{X} \\mathbf{W}\\_{1l})\\_+\\mathbf{w}\\_{2l}\\geq 0\\right] \\right), \\forall l \\in [\\bar{P}\\_2]$. Then, we can solve the convex program using only these hyperplane arrangements. We also remark that even though this is an approximation, it is extremely efficient and works much better/faster than standard non-convex training as shown in our experimental results in Section 4 and Appendix A.1.\n\n\n$\\textbf{Typos:}$\n\nWe thank the reviewer for pointing out these typos. We will correct them in the revised version.\n"}]

Author rebuttal:

Meta-review: This paper considers theoretical aspects of the problem of optimization over deep parallel ReLU architectures. When regularized with the path norm, the authors demonstrate that this can be cast as a convex optimization problem with a group-sparsity inducing norm. This yields a polynomial-time exact optimization algorithm when the data matrix is of low-rank. In the more general case of full-rank data, the authors propose an approximate algorithm and show global guarantees. Experiments on toy datasets supplement the theoretical contributions.

All reviewers (and the AC) agreed that the paper is well written and the (theoretical) contributions are solid. The authors are encouraged to further clarify differences between their work and earlier related works [17,29] while preparing the final manuscript.
Decision: Accept (poster)