Path Regularization: A Convexity and Sparsity Inducing Regularization for Parallel ReLU Networks
Authors: Tolga Ergen
Mert Pilanci
Venue: Submitted to ICLR 2023 (2023)
Keywords: Convex optimization
deep learning theory
path norm
group sparsity
polynomial-time training
ReLU networks
parallel architectures
global optimality
computational complexity

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, we show that the computational complexity required to globally optimize the equivalent convex problem is fully polynomial-time in feature dimension and number of samples. Therefore, we prove polynomial-time trainability of path regularized ReLU networks with global optimality guarantees. We also provide experiments corroborating our theory.

Under review as a conference paper at ICLR 2023
PATH REGULARIZATION: A CONVEXITY AND SPAR- SITY INDUCING REGULARIZATION FOR PARALLEL RELU NETWORKS
Anonymous authors Paper under double-bling review
ABSTRACT
Understanding the fundamental principles behind the success of deep neural net- works is one of the most important open questions 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 dard 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, path regularized parallel ReLU network can be viewed tantly, since the original training problem may not be trainable polynomial-time, we propose an approximate algorithm with 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.
parsimonious convex model in high dimensions. More impor-
Optimal 2-layer with WD
Optimal 3-layer with WD
Optimal 3-layer with PR
0.5
25
P
2.0
n
-05
-0.-
-05-
(a) 2-layer NN with WD
(b) 3-layer NN WD
(c) 3-layer NN with PR (Ours)
Figure 1: Decision boundaries of 2-layer and 3-layer ReLU networks that are globally optimized with weight decay (WD) and path regularization (PR). Here, our convex training approach (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 is 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 is regularizing layer weights so that the network can fit function that performs well on unseen test data. Even though weight decay, i.c., penalizing the Zz- norm of the layer weights, is commonly employed regularization technique in practice, recently, has been shown that 22-path regularizer (Neyshabur et al., 2015b). i.e., the sum over all paths in the network of the squared product over all weights in the path, achieves further empirical gains (Neyshabur et al., 2015a). Therefore, this paper, we investigate the underlying mechanisms behind path regularized DNNs through the lens of convex optimization.

---

Under review as a conference paper at ICLR 2023
Parallel ReLU Network
Path Regularization
Ei- ((XW)), Wor] was
R(0) Endio (lway 1 Sp
Ourput
Sub-network 1
Sub-netwock 2
Sub-network R
Inpot
Figure 2: (Left):: Parallel ReLU network in (1) with K sub-networks and three layers (L = 3)
(Right): Path regularization for three-layer network.
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, K < r: chosen according to (10) such that accuracy is achieved)
Loss function
2-layer complexity (2m1 poly'n, m))
L-layer complexity
Globally optimal ((Brute-force)
Arora et al. (2018a)
Convex Joss
Goel al. (2021)
f2-loss
20 polyfn, d)
x(NP-hard)
Proese al. (2021)
Ey-los
(h polly poly'ns m.))
/ (Brute-force)
Pilanci & Ergen (2020)
Convex loss
Oin poly(d,r))
(Convex, exact)
Ours
Convex loss
Olf"pofy(d:
[1 " poigld, 11 ml)
(Coonvex, exact)
Ours
Convex loss
O(x"poly(4, k))
o n Ilii m pollyldd 11- m))
/CConvex, c-ppt)
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 (Shalev- Shwartz et al., 2017: Goodfellow et al., 2016). Similarly, Ge et al. (2017); Safran Shamir (2018) showed that these pathological cases also apply to stochastic algorithms such Stochastic GD (SGD). They further show that some these issues can be avoided by increasing the number of trainable parameters, i..., operating in overparameterizzed regime. However, Anandkumar & Ge (2016) reported the existence of more complicated cases, where SGD/GD usually fails. Therefore, training DNNs to global optimality remains challenging optimization problem (DasGupta al., 1995; Blum & Rivest, 1989; Bartlett & Ben-David, 1999).
To cireumvent difficulties in training, recent studies focused on models that benefit from overparam- eterization (Brutzkus et al., 2017; Du & Lee, 2018; Arora et al., 2018b; Neyshabur et al., 2018). As an example, Wang al. (2021); Ergen & Pilanci (2021 1202):;c): Zhang al. (2019); Haeffele & Vidal (2017) considered a new architecture by combining multiple standard NNs. termed as sub- sub-networks, in parallel. Evidences in Ergen & Pilanci (2021d:c); Zhang al. (2019); Haeffele & Vidal (2017); Zagoruyko & Komodakis (2016); Veit et al. (2016) 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 global minimum. Therefore, many recently proposed NN-based architectures that achieve state-of-the-at performance in practice, e.g., SqueezeNet (landola et al., 2016), Inception (Szegedy et al., 2017), Xception (Chollet, 2017), and ResNext (Xie et al., 2017), are in this form.
Notation and preliminaries: Throughout the paper, we denote matrices and vectors as uppercase and lowercase bold letters, respectively. For vectors and matrices, certain column/element. As an example, Wikj in denotes the ji-1 entry of the matrix Wik- We use I and 0 (or 1) to denote the identity matrix of size k x k and vector/matrix of zeros (or ones)
subscripts to denote
2

---

Under review as a conference paper at ICLR 2023
with appropriate sizes. We use [n] for the set of integers from 1 to We use || ll2 and || - ||e to represent the Euclidean and Frobenius norms, respectively. Additionally, we denote the unit lp ball as B, := {u E Rd : ||u||p I 1}. We also use [ 2 0] and (x)+ = max(x, 0} to denote the 0-1 valued indicator and ReLU, respectively.
In this paper, we particularly consider a parallel ReLU network with sub-networks and each nub-network is L-layer ReLU network (see Figure 2) with layer weights Wi:- E R" 1xm,, VI E [L - 1] and w E R 1, where mi = d, m. = and my denotes the number of neurons in the 1t hidden layer. Then, given a data matrix X Raxdd the output of the network follows
K
fo(X) = - ((WI1)) 1 ((---1364 Wik.
where we compactly denote the parameters as == W.LWIR with the parameter space as θ and each sub-network represents a standard deep ReLU network.
Remark 1. Most commonly used neural networks in practice can be classified special cases of parallel networks, e.g., standard NNs and ResNets (He et al., 2016) see Appendix A.2 for details.
2.1 OUR CONTRIBUTIONS
We prove that training the path regularized parallel ReLU networks (I) equivalent 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 Pilanci & Ergen (2020) to multiple nonlinear layer without any strong assumptions in contrast to Ergen & Pilanci (2021c) and much broader class of NN architectures including ResNets.
As already observed by Pilanci & Ergen (2020); Ergen & Pilanci (2021c), regularized deep ReLU network training problems require exponential-tmme complexity when data matrix full rank, which is unavoidable. However, in this paper, develop approximate training algorithm which has fully polynomial-time complexity in all data dimensions and prove global optimality guarantees in Theorem To the best of our knowledge, this is the first convex optimization based and polynomial-timg global approximation guarantees.
complexity (in data dimensions) training algorithm for ReLU networks with
We show that the equivalent convex problem is regularized by group norm regularization where grouping effect is among the sub-networks. Therefore the equivalent convex formulation reveals an implicit regularization that promotes group sparsity among sub- networks and generalizes prior works on linear networks such Dai al. (2021) to ReLU networks.
We derive closed-form mapping between the parameters of the non-convex parallel ReLU net- works and its convex equivalent in Proposition 1. Therefore, instead of solving the challenging non-convex problem, can globally solve the equivalent convex problem and then construct optimal solution to the original non-convex network architecture via our closed-form mapping.
2.2 OVERVIEW OF OUR RESULTS
Given data X E Raxd and labels y E R consider the following regularized training problem
PE = min L (Jo (X),)) + (R(0),
(2)
where θ (0 Wi E R xm VI [L], vk [K]} is the parameter space, L ((. is
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 regression/Classifcatiio framework with arbi- trary loss functions, e.g., squared loss, cross entropy or hinge loss. We also note that our derivations can be straightforwardly extended to vector outputs networks as proven in Appendix A.1 More importantly, we use 22-path regularizer studied in Neyshabur al. (2015b;a), which defined as
L
R())
Σ
[|
II I=2
T (iikj-ns
j1.ja....j
We analyze scalar outputs, however, derivations extend to outputs as shown in Appendix A.1I.
3

---

Under review as a conference paper at ICLR 2023
where = is the ji-1 entry of Wik- The above regularizer sums the square of all the parameters along each possible path from input to output of each sub-network & (see Figure 2) and then take the squared root of the summation. Therefore, we penalize each path in each sub-network and then group them based on the sub-network index k.
We now propose scaling to show that (2) is equivalent a group & regularized problem. Lemma 1. The following problems are equivalent :
min () min L(fo +3 W DEG,
OEG
where WE& E Rm are the last layer weights of each sub-network k, and O {0 E θ
Ja....... 2 (IWING) 1-1 wikh in)) I 1, 1, vk E [K]] denotes the parameter space (1Wiki)1l11 11
after rescaling.
The advantage of the form in Lemma is that output layer weights WLA and then characterize the optimal layer weights via optimality conditions and the prior works E regularization we first apply the rescaling in Lemma 1 and then take the dual with respect to the output weights WLK- To characterize the hidden layer weights, we 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
infinite dimensional spaces (Rosset al., 2007). Thus,
PL
2 di ==
max (v) s.t. max OEG,
vT ((XW))...WWL.D)4 3B
W(L-D)
(3)
where L the Fenchel conjugate function of L, which defined as (Boyd & Vandenberghe, 2004)
(* maxz"v 20---aa (z.y).
The dual problem in (3) is critical for our derivations since it provides us with an analytic perspective to characterize a 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, ie.. pi = di Then, based on the exact dual problem (3), we propose an 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 (Wang et al., 2021; Ergen & Pilanci, 2021c; Pilanci & Ergen, 2020; Ergen & Pilanci, 202 lb; Zhang et al., 2019; Bach, 2017), however, this 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 a three-layer parallel network with K sub-networks, which is special case of (1) when L =33. Thus, we have the following training problem
P min C(fo (X).)
Σ J1:d2
Wikk 12 w Wikjs
(4)
where θ ((Wik, W 2k. W
Wik 1k
R ddxmi
Wes
Rmixma Wak Rm By Lemma 1,
Pb min L (Jo(
3
Wax
eES.
Then, taking the dual of (5) with respect the output layer weights Wat. E Rm and then changing the order of the minimization for { Ik. Wat and the maximization for the dual variable yields
max max L (v) s.t. max p 2
[VT ((XW1), Wa) < B.
(6)
FEE,
2 All the proofs are presented in the supplementary file. We present the details in Appendix A.7.
4

---

Under review as a conference paper at ICLR 2023
1
0
0
0
0
0
0
01
D =
0
1
0
D
0 0
0
D3
0
1 0
D,
0
0
1
0
0
0
0
0
10
1
(3.3)
(33)
(3.3)
(3.9)
Noeer dlappii
[?/)*
[3:]
(2:2
[1.0]
Sonor cheuder
[100
(1.0)
Soage d3
(1.0)
Figure 3: Illustration of possible hyperplane arrangements that determinc the diagonal matrices D Here, we have three samples in two dimensions and we want to separate these samples with a linear classifier. D, basically encodes information regarding which side of the linear classifier samples lie.
Here, we remark that (4) is non-convex with respect the layer weights, may have duality gap, i.e., pS 2 dz. Therefore, we first show that strong duality holds in this case, i.e., P1 = d3 as detailed in Appendix A.4. We then introduce an equivalent representation for the ReLU activation as follows.
Since ReLU masks the negative entries of inputs, we have the following equivalent representation
m2
mi
((XW1)+ w2) =
(Xw [
W2i
Σ ==
(Xw )__ Ií
D2
Σ
Dij,
Xwn
f=
(7)
where Wj, = Wajn Ij sign(wyz)) E {-1,+1}, and we use the following alternative representation for ReLU (see Figure for a two dimensional visualization)
DXw20
(ww) DXW (I, 5W
(2D L, Xw
where E R= a diagonal matrix of zeros/ones, i.e., D E 10. Therefore, we first enu- merate all possible signs and diagonal matrices for the ReLU layers and denote them Ij Draj, and D2r respectively, where ji E [mi], i E [Pi], I E [P2]. Here, Dus, and D2 denotes the masking/diagonal matrices for the first and second ReLU layers, respectively and Pt and P2 are the corresponding total number diagonal matrices in each layer as detailed in Section A0 Then, we convert the non-convex dual constraints (6) convex constraint using Diij D21 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-convex training problem in (4) can be cast as the following convex program
min L (x((zz'),x))) (oo-=zz))=++ /mz (lz]) + +|z=|| 1z'))
2. 2.2'EC
where ll 11,,,,1 denotes d Xm dimensional group Frobenius norm operator such that given a vector E RdmmPP [[ = Σ the convex sel C is defined [UZ][F, where U; E [Rdxms are reshaped partitions of u. Moreover,
C:= (z: Zight Ca,VE Vi [P],EE [P2]. [M]]
Ca ( {Wiidi (2D21 In) Σ I Dioj, Xw,, 2 (2D 18)1 I,),,,, 20, Vji [mi]
my
where Iūg E {+1,-1}, M 2m, and z, [ddm MPT are constructed by stacking 2 znn E Rd, Vi E [P], [Ps).1 E [m1]. E [M). respectively, Also, the effective data matrix X E Ruxdmy is defined as
: IM X.,
X, = D Dr, X... ...De, DiPom, X].
5

---

Under review as a conference paper at ICLR 2023
We next derive mapping between the convex program (8) and the non-convex architecture (4). Proposition 1. An optimal solution to the non-convex parallel network training problem in (4), de- noted as { (Wiks W2k: W3 can be recovered from an optimal solution to the convex program in (8), i.e., {z", xz" via closed-form mapping. Therefore, we prove a mapping between the parame- ters of the parallel network in Figure 2 and its convex equivalent.
Next, we prove that the convex program in (8) can be globally optimized with polynomial-time complexity given X has fixed rank, ie., rank(X) = r min (n. d).
(n,, d), the convex program in (8) can be globally optimized via standard convex solvers with (ndmmmmmm2mmm+t) 33 p complexity, which is a polynomial-time complexity in terms of n, d. Note that here globally optimiz- ing the training objective means achieve the exact global minimum up to any arbitrary machine precision or solver tolerance.
Proposition 2. Given data matrix such that rank (X)
Below, we show that the complexity analysis in Proposition 2 extends to arbitrarily deep networks.
Corollary 1. The same analysis can be readily applied to arbitrorily deep networks. Therefore, given rank(X (X) =r < min(n,d) d), we prove that I-layer architectures can be globally optimized with O @ (I
T.- m3) 2 Ei my mo 3r Ih m))) which is polynomial in n, d.
3.1 POLYNOMIAL-TIME TRAINING FOR ARBITRARY DATA
Based on the analysis in Corollary 1, exponential complexity is unavoidable for deep networks when the data matrix is 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, ll2 S 0r+1, where 0441 represents the (r + 1)th largest singular value of X. Then, we have the following result.
Theorem 2. Given R-Lipschitz convex loss function L ()))), the regularized training problem
p--min ( dEB
Σ
2kiii w
i1st2
be solved using the data matrix X, to achieve the following optimality guarantee
PS S P. S ps [
(10)
B
where p, denotes the objective value achieved by the parameters trained using X,.
Remark 2. Theorem and 2 imply that for a given arbitrary rank data matrix X, the reg- ularized training problem in (4) can be approximately solved by convex solvers to achieve
worst-case approximation P [1+ RRo.+.)) with complexity mm) 3mmr+1 where
mii d}. Therefore, even for fill rank data matrices where the complexity is exponential in Moreover we remark that the approximation error proved in Theorem can be arbitrarily small for practically relevant problems. As an example, consider a parallel network training problem with &z loss func-
or d, one can approximately solve the convex program in (8) in polynomial-time
tion, then the upperbound becomes (1+ + ymim20r-1 )2, which is typically close to one due fast decaying singular values in practice (see Figure 4).
B
3.2
REPRESENTATIONAL POWER: TWO VERSUS THREE LAYERS
Here, we provide complete explanation for the representational power of three-layer networks by comparing with the two-layer results Pilanci & Ergen (2020). We first note that three-layer net- works have substantially higher expressive power due the non-convex interactions between hidden layers as detailed Allen-Zhr et al. (2019); Pham & Nguyen (2021). Furthermore, Belilovsky et al. (2019) show that layerwise training of three-layer networks can achieve comparable performance

---

Under review as a conference paper at ICLR 2023
10a
#of hyperplanc arrangoments I
5000
Excac Proposed Upgerbound
Exact
4000
Proposed
Objective value
10
3000
10
2000
109
1000
10
4
6
9
4
6
8
of features (d)
# of features (d)
(a) Objective value (L)
(b) # hyperplane arrangements (P)
Figure 4: Verification of Theorem 2 and Remark 2. We train parallel network using the convex program in Theorem with &2 loss on a toy dataset with n 15, B 0.1, m2 = 1, and the low-rank approximation 2 I. To obtain low-rank model, we first sample data matrix from a standard normal Gaussian distribution and then set 0 = od
Table 2: Training objective of three-layer parallel network trained with non-convex SGD
(5 independent initialization trials) on toy dataset with (n, d, mi, m2, 3, batch size)
(5, 2, 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
Training objective
0.0221
0.0239
0.0031
0.0027
0.0027
0.0007
K 5
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
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
to deeper models, e.g.. VGG-11, on Imagenet. There exist several studies analyzing two-layer net- works, however, despite their empirical success, a full theoretical understanding and interpretation of three-layer networks is still lacking in the literature. In this work, provide complete char- acterization 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 Pilanci & Ergen (2020).
Pilanci & Ergen (2020) analyzes two-layer networks with one ReLU layer, so that the data matrix X is multiplied with single diagonal matrix (or hyperplane arrangement) D,. Thus, the effective data matrix is in the form of X, X DpX]. However, since our convex program in (8) has two nonlinear ReLU layers, the composition of these two-layer can generate substantially more complex features via locally linear variables { multiplying the d-dimensional blocks of the columns of
the effective data matrix X. Theorem Although this may seem similar to the features in Ergen & Pilanci (2021c), here, we have n variables for each linear region unlike Ergen & Pilanci (2021c) which employ variables per linear region. Moreover, Ergen & Pilanci (2021c) only considers the case where the second hidden layer has only neuron, i.e., m2 1, therefore do consider standard three layer or deeper networks. Hence, we exactly describe the impact of having one more ReLU layer and its contribution the representational power of the network.

---

Under review as a conference paper at ICLR 2023
Test Acourrcc
Test Accuracy
0.50
Comse (Duns)
Corvec (Sun)
Adligad
Adlggnd
Adadeet
Adtes YU
Adkr
0.00
0.0
Time(s)
Time(s)
(a) CIFAR-10
(b) Mishion-MNISS
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-I0 with (n, d. my, m2, K, batch size) (5x10*. 3072, 100, 40, 10 11110001000 110)) and (b) Fashion-MNIST
with (n, d. my, m2, K, 3, batch size) = (6x10*, 784, 100, 1, 40, 10-3, 103). We note that the con- vex model is trained using (a) SGD and (b) Adam.
4 EXPERIMENTS
In this section", we present numerical experiments corroborating our theory.
Low rank model in Theorem 2: To validate our claims, we generate a synthetic dataset as follows. We first randomly generate a set of layer weights for parallel ReLU network with K = 5 sub-networks by sampling from standard normal distribution. We then obtain the la- bels as y = E. (I) W2x) W3k + 0.le, where e ~ (0, I,). To promote a low rank structure in the data, we first sample a matrix from the standard normal distribution and then set 0d 1. We consider a regression framework with la loss and (n, r. B, mi, m2) (15, 0/2, 1, and present the numerical results in Figure 4. Here, we observe that the low rank approximation of the objective p, closer to P3 than the worst-case upper-bound predicted by The- orem 2. However, in Figure 4b, the low rank approximation provides a significant reduction in the number of hyperplane arrangements, and therefore in the complexity of solving the convex program.
0r+1
Toy dataset:
We use toy dataset with 5 samples and 2 features, i.e., (n,d) d) = (5. To gen- erate the dataset, we forward propagate i.i.d samples from standard normal distribution, i.e., X; (O, Iz), through parallel network with 3 layers, 5 sub-networks, and 3 neurons, i.e., (I, K, m1, m2) = (3, 5,3, 1). We then train the parallel network in (4) on 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, show the benign overparametterizaton impact.
Image classification: We conduct experiments on benchmark image datasets, namely CIFAR- 10 (Krizhevsky al., 2014) and Fashion-MNIST (Xiao al., 2017). We particularly consider ten class classification task and use a parallel network with 40 sub-networks and 100 hidden neurons, i.e., (K, mi, m2) (40, 100, 1). Figure we plot the test accuracies against wall-clock time, where we include several different optimizers as well as SGD. Moreover, we include a parallel net- work trained with SGD/Adam and Weight Decay (WD) regularization 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 Mushion-MNIIS seems to be significantly less compared to the CIFAR-10 experiment. This is due to the nature of these datasets. More specifically, since CIFAR-10 is a much more challenging dataset, the base- line accuracies quite low (around 50%) unlike Fashion-MNIST 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
Details on the experiments be found in Appendix A.1.
8

---

Under review as a conference paper at ICLR 2023
regularization yields higher final test accuracies. is normal to have faster convergence with weight decay since it can be incorporated into gradient-based updates without any computational overhead.
5 RELATED WORK
Parallel neural networks were previously investigated by Zhang et al. (2019); Haeffele & Vidal (2017). Although these studies provided insights into the solutions, they require assumptions, c.g., sparsity among sub-networks in Theorem 1 of Haeffele & Vidal (2017)) and linear activations and hinge loss assumptions in Zhang al. (2019), which invalidates applications in practice.
Recently, Pilanci & Ergen (2020) studied weight decay regularized two-layer ReLU network training problems and introduced polynomial-time trainable convex formulations. However, their analysis is restricted to standard two-layer ReLU networks, i.e., in the form of fo(X) = (XW1) W2- The reasons for this restriction that handling more than one ReLU layer is a substantially more challenging optimization problem. As an example, a direct extension of Pilanci & Ergen (2020) to three-layer NNs will yield doubly exponential complexity, i.e., Onn"²) for a rank-r data matrix, due to the combinatorial behavior of multiple ReI.U layers. Thus, they only examined the case with a single ReLU layer (see Table I for details and the other relevant references in Pilanci & Ergen (2020)). In addition, 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, Ergen & Pilanci (2021c) extended this approach to three- llyeerlayer ReLU networks. However, since they analyzed l fo-norm regularized training problem, they had to put unit Frobenius norm constraints on the first layer weights, which does not reflect the settings in practice. In addition, their analysis is restricted to the networks with single neuron in the second layer (i.e. m2 = 1) that is in the form of fx) E. (XXW1)) W Wag. Since this architecture only allows a single neuron in the second layer, each sub-network has an expressive power that is equivalent to a 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 Ergen & Pilanci (2021c) has decoupled constraints across the hidden layer index ji whereas our formulation sums the responses over hidden neurons before feeding through the next layer as standard deep networks do. Therefore, this analysis does not reflect the true power of deep networks with L > 2. Moreover, the approach in Ergen & Pilanci (2021c) has exponential complexity when the data matrix has full rank, which is unavoidable.
However, we analyze deep neural networks in (1) without any assumption on the weights. Further- more, we develop an approximate training 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 can be equivalently cast as single convex optimization problem. Therefore, we achieved the following advantages over the training on the original non-convex formulation: 1) Since our model is convex, can be globally optimized via standard convex solvers whereas the non-convex formulation trained with optimizers such as SGD might be stuck at a local minimum, 2) Thanks to convexity, our model does not require any sort of heuristics and additional tricks such as learning rate schedule and initialization scheme selection or dropout. More importantly, we pro- posed an approximation to the convex program to enable fully polynomial-tin of the number of data samples and feature dimension d. Thus, we proved the polynomial-time trainability of deep ReLU networks without requiring any impractical assumptions unlike Pilanci & Ergen (2020); Ergen & Pilanci (2021c). Notice that derive an exact convex program only for three-layer networks, however, recently Wang et al. (2021) proved that strong duality holds for arbitrarily deep parallel networks. Therefore, a similar analysis can be extended to deeper networks to achieve an equivalent convex program, which is quite promising for future work. Additionally, although we analyzed fully connected networks in this paper, our approach can be directly extended to various NN architectures, e.g., convolution networks (Ergen & Pilanci, 2021a), generative ad- versarial networks (Sahiner et al., 2021a), NNs with batch normalization (Ergen et al., 2021), and autoregressive models (Gupta et al., 2021).
training in terms

---

Under review as a conference paper at ICLR 2023
REFERENCES
Akshay Agrawal, Robin Verschueren, Steven Diamond, and Stephen Boyd. A rewriting system for convex optimization problems. Journal of Control and Decision, 5(1):42-66) 60, 2018.
Zeyuan Allen-Zhu, Yuanzhi Li. and Yingyu Liang. Learning and generalization in overparameter- ized neural networks, going beyond two layers. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, Buch E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Sys- tems, volume 32. Curran Associates, Inc., 2019. URL https /ttp://///oceeeeeeeeeeeeeeeee neurips. pdf.
hcc/paper/2019 file/
Animashree Anandkumar and Rong Ge. Efficient approaches for escaping higher order saddle points in non-convex optimization. In Conference on learning theory, pp. 81-
Raman Arora, Amitabh Basu, Poorya Mianjy, and Anirbit Mukherjee. Understanding deep neural networks with rectified linear units. In 6th International Conference on Learning Representations, ICLR 2018, 2018a.
Sanjeev Arora, Nadav Cohen, and Elad Hazan. On the optimization of deep networks: Implicit acceleration by overparamtterization. In 35th International Conference Machine Learning, ICML 2018, pp. 372-389. International Machine Learning Society (IMLS), 2018b.
Francis Bach. Breaking the curse of dimensionality with convex neural networks. The Journal of Machine Learning Research, 18(1):629-66) 681, 2017.
Peter Bartlett and Shai Ben-David. Hardness results for neural network approximation problems. In European Conference on Computational Learning Theory, pp. 50-62. Springer, 1999.
Eugene Belilovsky, Michael Eickenberg, and Edouard Oyallon. Greedy layerwise learning can scale to imagenet. In International conference on machine learning, pp. 583-593. PMLR, 2019.
Avrim Blum and Ronald L Rivest. Training a 3-node neural network is np-complete. In Advances in neural information processing systems, pp. 494 4011, 1989.
Stephen Boyd and Lieven Vandenberghe. Conver optimization. Cambridge university press, 2004.
Alon Brutzkus, Amir Globerson, Eran Malach, and Shai Shalev-Shwarzz. SGD lears over-parameterizee networks that provably generalize on linearly separable data. CoRR, abs/1710.101744 2017. URL
Daniel Smilkov Carter and Shan. URL hattpp://playgrooun.ttttooooeee
François Chollet. Xception: Deep learning with depthwise separable convolutions. In Proceedings of the IEEE conference on computer vision and puttern recognition, pp. 1251-1258, 2017.
Thomas M Cover. Geometrical and statistical properties of systems of linear inequalities with ap- plications in pattern recognition. IEEE transactions on electronic computers, (3):22-333, 1965.
Zhen Dai, Mina Karzand, and Nathan Srebro. Representation costs of linear neural networks: Anal- ysis and design. In M. Ranzato, A. Beygelzimer, Dauphin, P.S. Liang, and Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. ran Associates, Inc., 2021. URL https:://rocceeeeaa/eeaeo httee//e222bbbbbbb2b//0000000000
Cur- neurips cc/ pptpp/ppppp//////////p pdf.
Bhaskar DasGupta, Hava Siegelmann, and Eduardo Sontag. On the complexity training neural networks with continuous activation functions. IEEE Transactions on Neural Networks, 6(6): 1490-1504, 1995.
Steven Diamond and Stephen Boyd. CVXPY: A Python-embeddedd modeling language for convex optimization. Journal of Machine Learning Research, 17
Simon S Du and Jason D Lee. On the power of over- wve-parrmettization in neural networks with quadratic activation. arXiv preprint arXiv:/803 0000.0030000000 0/206, 2018.
10

---

Under review as a conference paper at ICLR 2023
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL http::///arce ics. uci. meiieedu/ml.
Tolga Ergen and Mert Pilanci. Implicit convex regularizers of architectures: Convex op- timization of two- and three-layer networks in polynomial time. In International Confer- ence on Learning Representations, 2021a. URL https::t/////. petttp:://ppereviiee net forum?id-
ON8 JUH4 JMv6.
Tolga Ergen and Mert Pilanci. Convex geometry and duality over-parameterized neural networks. Journal of Machine Learning Research, 22(212):1-63, lb.
Tolga Ergen and Mert Pilanci. Global optimality beyond two layers: Training deep relu networks via convex programs. CoRR, 10.0551,, 2021c. URL hwtpt:tt/t//.tttee org abs abs/2110. 05518.
Tolga Ergen and Mert Pilanci. Revealing the structure of deep neural networks via convex duality. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 3004-3014. PMLR, 18-24 Jul 2021d. URL http:hhtt///ceeeeeeee http:///eroeeeingm.....e...ee..e html.
Tolga Ergen, Arda Sahiner, Batu Ozturkler, John M. Pauly, Morteza Mardani, and Mert Pilanci. Demystifying batch normalization in relu networks: Equivalent convex optimization models and implicit regularization. CoRR, abs/2103.01499 2021. URL https:///axxiiii 2103.00 01499.
abs/
Manuel Fernández- Delgaddo, Eva Cernadas, Senén Barro, and Dinani Amorim. Do we need hun- dreds of classifiers to solve real world classification problems? Journal of Machine Learning Re- search, 13333131, 2014. URL httt:://ttmlll/ wrt. wwtppppprg.p//ppotaattoaaaeeeeet html.
4a.
Vincent Froese, Christoph Hertrich, and Rolf Niedermeier. The computational complexity of relu network training parameterized by data dimensionality, 2021.
Rong Ge, Jason D. Lee, and Tengyu Ma. Learning oee-iddeen-laye neural networks with landscape design, 2017.
Surbhi Goel, Adam Klivans, Pasin Manurangsi, and Daniel Reichman. Tight Hardness Results for Training Depth-2 ReLU Networks. In James R. Lee (ed.), 12th Innovations in Theoretical Computer Science Conference (ITCS 2021), volume 185 of Leibniz International Proceedings in Informatics (LIPlcs). pp. 22:1-22:14, Dagstuhl, Germany, 2021. Schloss Dagstuhl-Leibniz Zentrum für Informatik. ISBN 978-3-95977-177-1. doi: 10.4230/LIPIcs.ITCSS httpss: /rrpsso dagst de/ opus/ volllllo wwwlleeeeeeeeeeeeee 2ttee//222111355
URL
Ian Goodfellow, Yoshua Bengio, Aaron Courville, and Yoshua Bengio. Deep learning, volume 1. MIT press Cambridge, 2016.
Michael Grant and Stephen Boyd. CVX: Matlab software for disciplined convex programming, version 2.1. http: cvxr, com/ cvx, March 2014.
Vikul Gupta, Burak Bartan, Tolga Ergen, and Mert Pilanci. Convex neural autoregressive models: Towards tractable, expressive, and tbeoreticallybbacked models for sequential forecasting and generation. In ICASSP 2021 2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 1894, 2021. doi: 10.1109/CCASSP3972.. 2021 0000..91111100 9413662.
Benjamin D Haeffele and René Vidal. Global optimality in neural network training. In Proceedings of the IEEE Conference on Computer Vision and Puttern Recognition, pp. 7331-7339, 2017.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp- 770-778, 2016.
11

---

Under review as a conference paper at ICLR 2023
Forrest N landola, Song Han, Matthew W Moskewicz, Khalid Ashraf, William J Dally, and Kurt Keutzer. Squeezenet: Alexnet-level accuracy with 50x fewer parameters andj 0.5 mb model size. arXiv preprint arXiv: 2016.
Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. The CIFAR-10 dataset. http://www cs.
toronto. edu/krdtt kri / cifar. html, 2014.
Behnam Neyshabur, Russ R Salakhutdinov, and Nati Srebro. Path-sgd: Path-normalized opti- mization in deep neural networks. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Gameet (eds.), Advances in Neural Information Processing Systems, volume 28. Curran Asso- ciates, Inc., 2015a. URL https: /tttpp::/prrcceeee http:////ccceeeeng..ccoo www.ips.......... wttpccppppppp.///../ Paper.
eaa32c96 6200000665055555
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks. In Peter Grünwald, Elad Hazan, and Satyen Kale (eds.), Proceedings of The 28th Conference on Learning Theory, volume 40 of Proceedings of Machine Learning Research, pp. 1376-1401, Paris, France, 03-06 Jul 2015b. PMLR. URL pestp://proceedeee press/v400 /a0as///V///esabburr11//
mlr.
Neyshaburls 11 html.
Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LeCun, and Nathan Srebro. To- wards understanding the role of over-parametrization in generalization of neural networks. arXiv preprint arXiv: 1206, 2018.
Piyush C Ojha. Enumeration of linear threshold functions from the lattice of hyperplane intersec- tions. IEEE Transactions on Neural Networks, 11(4):83--800 2000.
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. URL https: / /pwprevveeeeeeeeeeeeee/eee/eeeee
net/ / forum?id=KuyxxFq/5
Mert Pilanci and Tolga Ergen. Neural networks are convex regularizers: Exact polynomial-ting convex optimization formulations for two-layer networks. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Reseurch, pp. 7695-7705. PMLR, 13-18 Jul 2020. URL attpss:/pzee /proceedigos wtt...eeese//llllplll.....
html.
Saharon Rosset, Grzegorz Swirszez, Nathan Srebro, and Ji Zhu. LI regularization in infinite di- mensional feature spaces. In International Conference Computational Learning Theory, pp. 544-558. Springer, 2007.
Itay Safran and Ohad Shamir. Spurious local minima are common in two-layer relu neural networks. In International Conference on Machine Learning, pp. 4433-4441. PMLR, 2018
Arda Sahiner, Tolga Ergen, Batu Ozturkler, Burak Bartan, John Pauly, Morteza Mardani, and Mert Pilanci. Hidden convexity wasserstein gans: Interpretable generative models with closed-form solutions. arXiv preprint arXiv:2107.05680 202
Arda Sahiner, Tolga Ergen, John M. Pauly, and Mert Pilanci. Vector-output relu neural network problems are copositive programs: Convex analysis of two layer networks and polynomial time algorithms. In International Conference on Learning Representations, 2021b. URL https: / //ooperrviies net./ f forum? d= FGF FGF
Shai Shalev-Shwartz, Ohad Shamir, and Shaked Shammah. Failures of gradient- deep learning. arXiv preprint arXiv: arXiv:1703.00 1703007950 2017.
Maurice Sion. On general minimax theorems. Pacific J. Math., 8(1):171-176, 1958. URL https: / //ppoojecteeclldd.rrrr :43: 0443//cclid.ppmmm11330000000
Richard P Stanley et al. An introduction to hyperplane arrangements. Geometric combinatorics, 13: 389-496, 2004.
Christian Szegedy, Sergey loffe, Vincent Vanhoucke, and Alexander A Alemi. Inception-v4, inception-restte and the impact of residual connections on learning. In Thirty-first AAAI con- ference artificial intelligence, 2017.
12

---

Under review as a conference paper at ICLR 2023
Andreas Veit, Michael J Wilber, and Serge Belongie. Residual networks behave like ensembles of relatively shallow networks. In Advances neural information processing systems, pp. 550-558, 2016.
Yifei Wang, Tolga Ergen, and Mert Pilanci. Parallel deep neural networks have zero duality gap. 2021.
RO Winder. Partitions of n-space by hyperplanes. SIAM Journal on Applied Mathematics, 14(4): 811-818, 1966.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnin mnist: a novel image dataset for benchmark- ing machine learning algorithms, 2017.
Saining Xie, Ross Girshick, Piotr Dollár, Zhuowen Tu, and Kaiming He. Aggregated residual trans- formations for deep neural networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 1492-1500, 2017.
Sergey Zagoruyko and Nikos Komodakis. 1605.0060 2016.
Wide
residual
networks.
arXiv preprini
Hongyang Zhang, Junru Shao, and Ruslan Salakhutdinov. Deep neural networks with multi-bre branch architectures are intrinsically less non-convex. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1099-19999001 1109, 2019.
13

---

Under review as a conference paper at ICLR 2023
Supplementary Material
Table of Contents
A
Appendix
14
A.1
Additional numerical results and details
14
A.2 Parallel ReLU networks
16
A.3 Proof of Lemma
A.4 Proof of Theorem
17
A.5 Proof of Proposition
19
A.6 Proof of Theorem
20
A.7 Proof for the dual problem in (3)
22
A.8 Hyperplane arrangements
22
A.9 Low rank model in Theorem 2
23
A.10 Proof of Proposition 2 and Corollary
23
A.11 Extension vector outputs
25
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 training labels) (Carter & Shan). As the baselines of our analysis, we include the two-layer convex training approach in Pilanci & Ergen (2020) and recently introduced three-layer convex training approach (with weight decay regularization and several architectural and parametric assumptions) in Ergen Pilanci (2021c). As our experimental setup, we consider a binary classification task with E [1].-1}" and squared loss. We choose (n, m., M2, P1, P2, (3) = (30, 5, 11, 11, Ie 4) and for Pilanci Ergen (2020) we use P 50 neurons/hyperplane arrangements. We also use CVPXY with MOSEK solver (Grant & Boyd, 2014; Diamond & Boyd, 2016; Agrawal et al., 2018) to globally solve the convex programs. As demonstrated Figure 1, baselines methods, especially Ergen & Pilanci (2021c), fit function that is significantly different than the underlying spiral data distribution. This clearly shows that since Pilanci & Ergen (2020) is restricted two-layer networks and Ergen & Pilanci (2021c) have multiple assumptions, i.e., unit Frobenius the layer weights [ || < 1, 4I E [T. 2)) and last hidden layer weights cannot be matrices (W(L-1)& E mm-)), both baseline approaches fail 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.
Decision boundary plots in Figure 1:
readily interpolate the training data (i.e. exactly fit the
constraints
Additional experiments: We also conduct experiments on several datasets available in UCI Ma- chine Learnnng Repository (Dua & Graff. 2017), where we particularly selected the datasets from Femánndez-eelaal et al. (2014) such that < 500. For these datasets, we consider conventional binary classification framework with (m1, m2, K, (3) = (100, 1, 40, 0.5) and compare the test ac- curacies 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, 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-convex 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 Pilanci & Ergen (2020).
14

---

Under review as a conference paper at ICLR 2023
Table Test accuracies for UCI experiments ((m1, m2, K, (100, 40,00,0 0.5) and 80% 20% training-tes, test split). Here, we present the standard non-convex architectures and the proposed convex counterpart trained with SGD and Adam optimizers. one approach achieves higher accuracy on certain dataset, display the corresponding accuracy value in bold font. We observe that our convex approach achieves either higher or the same accuracy 20 and 19 datasets (out of datasets) when trained with SGD and Adam, respectively
SGD
Adam
Datasel
7
Non-convex
Convex(Ours)
Non-convex
Convex(Ours)
infllammmmatii
1.000
1.000
1.000
1.000
acute-nephritis
1.000
1.000
1.000
1.000
balloons
1.000
1.000
1.000
1.000
breast-cancer
286
0.690
0.707
0.655
0.672
treas--cnneerwwis-eee
198
33
0.750
0.800
0.800
0.825
congressional-von voting
435
16
0.667
0.667
0.551
0.597
Conn-bench-sone sonarr rocks
208
60
0.714
0.786
0.738
0. 0.833
echocardiogram
131
10
0.704
0.704
0.666
0.703
fertility
100
0.750
0,800
0,800
0,800
haberman-surrival
306
0.710
0.774
0.677
0.709
heart-hungarian
294
12
0.831
0.831
0.779
0.813
hepatitis
155
19
0.645
0.710
0.709
0.741
ionosphere
351
33
0.887
0.901
0.929
0.887
selec-biol-promoooe
106
57
0.818
0.818
0.727
0.772
musk-1
476
166
0.958
0.927
0.947
0.927
parkinsons
195
22
0.974
1.000
0.923
1.000
Drabbur--riiges---ORR-D-
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
vertebral-column-clle
310
0.806
0.839
0.758
0.822
Highest test accuracy
20/21
19/21
90
85
CIFAR-10 Test Accuracy
80
75
70
convex layerwise training
1.0
1.5
2.0
2.5
3.5
4.5
Stage
Figure 6: Test accuracy for convex layerwise training, where each stage is our three-layer convex formulation in Theorem Here, we train three-layer neural networks sequentially using convex optimization to build deep networks.
Details for the experiments in Table and Figure 5: We first note that for the experiments in Table 2, use CVX/CVPXY (Grant & Boyd, 2014; Diamond & Boyd, 2016; Agrawal et al., 2018) to globally solve the proposed convex program in (8). For these experiments, we use a laptop with i7 processor and 16GB of RAM. In order to tune the learning of SGD/GD, first perform training
15

---

Under review as a conference paper at ICLR 2023
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, utilize cluster GPU with 50GB 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 Gupta et al. (2021)
min n,xx giRdmng MP,
(x (2), +
(l1elo,, + ||2||l..) +/ze,.++llzlll..11
(hc(z) + hc(z'))
(11)
where > 0 coefficient to penalize the violated constraints and (z(z) is function to sum the absolute value of all constraint violations defined as
he(z) = 1S Σ ((-(2Dis) X.)x((n)))))) 1 f.11de
Σ 1,,,
Fn II, Din X
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-10 and Fashion-MNIST, we use 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
WD (JConeery PSGD: Adam: ; Adagrad, 1 Adadelta: PSGD) = (5e 7,5e 3, 2e and
5.2e 3,3e 1, 1)
WD (JConvez: DS Adam, (AAdggrdd: Adadelta, MgGD = (1e - 5, 2e 11,2e 3, le 2,3,
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 P2 K and X = le 5.
More importantly, we remark that these experiments are performed by using a small sampled subset of hyperplane arrangements rather than sampling all possible arrangements as detailed in Remark 3.3 of Pilanci Ergen (2020). In particular, we first generate random weight matrices from a multi- variate 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, Belilovsky et al. (2019) shows that one can train three- layer neural networks sequentially to build deep networks that outperform end-to-end training with SOTA architectures. 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 1. Here, we use the same experimental setting in the previous section. We observe that making the network deeper by stacking convex layers resulted in significant performance improvements. Specificaly, at the fifth stage, we achieved almost 85% accuracy for CIFAR-10 unlike below 60% accuracies in Figure 5.
A.2 PARALLEI. RELU NETWORKS
The parallel networks (X) models wide range of NNs in practice. As example, standard NNs and ResNets (He et al., 2016) 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., K and L 4. If we set W = W E [2].7 E [4] then our architecture reduces to a standard four-layer network
2
Σ ((XW11) WoR), Wox).
W4t (((XW1), W2) Wa) W4,
where W, Rdxmm W₂ E M xm2 W3 R mms W4 E Rms, For ResNets, first remark that since residual blocks are usually used after a ReLU activation function, which is positively homogeneous of degree one, in practice each residual block takes only nonnegative entries as its inputs. Thus, can assume X Raxd without loss of generality. We also assume that weights
16

---

Under review as a conference paper at ICLR 2023
obey the following form: Wn1 W1, W21 W2. W12 W22 Lı, W3 W32 W3, and
W11 = 12 = W4 then
((XXW)) W2), Wa) Wa (XW3) W4 which is a shallow ResNet as demonstrated in Figure 1 of Veit et al. (2016).
fx( - Σ ((XWI)), W28) 33
W4k
A.3 PROOF OF LEMMA 1
Let first define Tkic
V Ein--ie-
[Wikk 112 1112 wikee 13:
0. Notice that if
-kic-1 O, this means that Ethh sub-network does not contribute the output of the parallel net- work in (1). Therefore, we can remove the paths with Tkiz-1 = 0 without loss of generality. Now, use the following change of variable
W(L-1)Rju-1, VI E [T. 1}, w'kiz-1 -kju- WLKjE-
Wi Wik vi [T. 2}, W (L-1))kio-1
Tkjo-1
We now note that
L-1 Wing 151
L-1 II
Σ
[WIRS 112 II
Σ
[|wik] 11
winsi Ii1
1.
PRiL- jtamdees
Then, (2) can be restated as follows
pi
min
L Σ ((WW1)) ... W(- WLLYY
+ Σ
Σ ilimd
|| 113
II winh
K (XWix)+... .......wW............ W(L- d w'
min (wwx) 18 (w (W2x)
Tkiz-1
k=
Estraties (IWIK)) 12 I w
Wiiiit-1
16-1
Σ (XWW1)+ F..5 WWLL-)N .)_ whnss-i + 8 w
min ([Wul 1--1 K [w (wiahee
C
Am13n-1
(XWix) ... Wa--ne), WYERY) + Σ /wwz
min ((W/elis 1 (Wi (C- (C..:..W---))
where O = -WW,..... WL-1):
(IWiJ) :
I w w =1 VjL-1 E [m
We also note that one can relax the equality constraint generality. This basically due to the fact that a constraint is not tight, i.e., strictly less than one, at the optimum then we can remove that constraint and make the corresponding output layer weight arbitrarily small via simple scaling to 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 layer weights (that yields a strict inequality in the constraints) are not optimal.
inequality constraint without loss of
A.4 PROOF OF THEOREM 1
To obtaín the bidual problem of (4), we first utilize semi-infinite duality theory as follows. We first compute the dual of (6) with respect to the dual parameter to get
Pio = min min L ( ((W1)), W2), wydu(0), 3.111A1lTV.
(12)
I S1
17

---

Under review as a conference paper at ICLR 2023
where ||l|Ty denotes the total variation norm of the signed measure μ.. Notice that (12) is an dimensioam neural network training problem similar to the one studied in Bach (2017). More importantly, this problem is convex since the model is linear with respect to the measure and the loss and regularization functions are convex (Bach, 2017). Thus, we have no duality gap, i.e., dz P In addition to this, even though (12) is an infiniteddimensional convex optimization problem, it reduces to a problem with at most nt + 1 neurons at the optimum due to Caratheodory's theorem (Rosset al., 2007). Therefore, (12) can be equivalently stated the following finite-size convex optimization problem
K' Σ
Poo
min L EEO.
(XWI1)+ W2s) Wak. y
B
Was ||2
K Wax 12s
min L (Jo(X),)) BE
(13)
where K < n + 1. We further remark that given K 2 K", (13) and (5) are the same problems, which also proves strong duality as pa Pio dz. In the remainder of the proof, we show that using an alternative representation for the ReLU activation, we can achieve a finiteddimensional convex bidual formulation.
Now we restate the dual problem (6) as
43 = max - (v) s.t. max 8EB,
VT (XXW)), Wa)+ $33.
(14)
We first note that using the representation in (7), the dual constraint in (14) can be written as
max T (XW11), wa)+ SB 0ES,
Σ (vr ((XW1), ) S B
max DEB,
(vT ((XW1)+ w2) )² S 3
max ree,
V m2
2
max max
m2
VT
Is (Xw15) Ju2s 12+
S B
I3 6(11) AER,
v1=1
max
max
max
/m2
D2x
> Diy, Xw51
S
PE J, E(21) [w),
EC
ECR
Pg
(15)
where O {(W1, 1, W2) ΣØ= W1j, 12 Ju
1,, [m2]]. we apply variable change
as W,, |W2j [Wi,, and define the set C3 as
mgg
Ca C( (2D2: - I.) Σ I, 2 2, (2D I,),,,, 2 0, Aij E [mi],
Iw 12 51 1}.
=1
We also note that P1 and Pz denote the number of possible hyperplane arrangement for the first and second ReLU layer (see Appendix A.10 for details).
Then we have
max BE
VvT (XWI)), W2) 11,
3B
max
max (w), 14 ECu
VT2a
T
04 D'
Ij
D Dig Xwj1
SB.
e[[P]]
LE(P]
;1=1
Zz ((21)
max (wi,ths E0g
Vivz" D2i
I Dia Xwi,i SB.
Vi [P]], [P3), Vs E E [M].
max
-V Dzi
1i Disn Xw B
(w cog
=1
18

---

Under review as a conference paper at ICLR 2023
where M | = 2 enumerate all possible sign patterns (I 1n of the size my. Using the equivalent representation above, we rewrite the dual (14) as
max (v) s.t.
max (wo ECG
Vmgy D21
T Dish Xwijt SB, Vi,1,
(16)
max the ECG
Mm2vv
D21
DiG Xwint S,, Vi,l,s.
(17)
Since the problem above is convex and satisfies the Slater's condition when all the parameters are set to zero, we have strong duality (Boyd & Vandenberghe, 2004), and thus we can state (16) as
M
P
P2 Vil
mi
min max min
-L(v)'
B -
Vmmvv D21
I Dis. Xw
1h, EC0 19 20 v
=1=1
Ti 20
(wy EC2
(18)
M
P
3 m
DD2
Σ 31=1
T D
Xw
in!
(19)
Due to Sion's minimax theorem (Sion, 1958), we can change the order the inner minimization and maximization to obtain closed-form solutions for the maximization over the variable v. This yields following problem
m1 ΣΣΣΣ
min "a db ECG thy ECG
min
D2 Day X Iianawshih
Cā + va)
(20)
Finally, we introduce a set variable changes changes as z = a w and /m2Th Ii wight such that (20) can be cast as the following convex problem
P2 P ΣΣΣΣ ==
M
min (diy))s ecd 1s ect!
C
DzD X(Z 2inW..
M
Σ
1 +
(21)
mm2
1==1
where the constraint set C are defined as
ct = ( (zn (2D I,,
Σ
D Dig. Xz 2 0, (2Dag. I, 2 0, Vj
[mi]]
J==1
Notice that (21) is a constrained convex optimization problem with 2dm, M P2 variables and 2n(m; 1)MP, constraints in the set Cū
A.5 PROOF OF PROPOSITION
In this section, prove that the convex program in (21) is globally optimized to obtain set of optimal solutions {2f is one recover optimal solution the non-convex
19

---

Under review as a conference paper at ICLR 2023
training problem (4) via simple closed-fore form mapping detailed below
I
22
I imm iimt
if k S MP if + 2MP.P
Wir
i
T: f1
I iim Fimst)
m2
Li
Zir
Ti
if I MP,22
Is
im1l
I
mmal
Timil
W
2k
I
Ti
Ti
I immlt
immp
1
if k MPP: if
...
3k
-1 -1
where
k-1 P
(a- 1/
+ +1, - 11-1-
if MP else
(s,
P1
W-1
+1,
(11
+1,K (s- - (1-1)P) ((
P1
with V = M2 Hence, achieve optimal solution to the original non-convex training
problem (4) (Wis 1k: W 2k. w W=
12MP, where W Rdxmm W 24 E pmmx,, and w
I= 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.
We first verify that both the optimal convex and non-convex layer weights give the same network output as follows (8), i.c.
2MP,
m1
Σ (XWi1)) W2t W3A
ΣΣΣΣDAD D2D mi X ( -
Now, show that the proposed of weight matrices for the non-convex problem achieves the same regularization cost with (21), i.e.
2MP.P,
mi
mi
M P.
mi
mi
Wikg, BR "ak
Σ f==
Elll +
1 Telillll
m2
1==1
Since (Wi 1k: W 2k: w 12MP Pa yields the same network output and regularization cost with the optimal parameters of the convex program in (21), conclude that the proposed set parameters for the non-convex problem also achieves the optimal objective value pi, i.e.,
1==
2MP.3
2MP.P
m2
mi
P5 = L
Σ (XWW1)) Wan) W +
Σ
Σ
w
BB Wakja
ja=1i
A.6 PROOF OF THEBREM 2
We start with defining the optimal parameters for the original and rank-k approximation of the rescaled problem in (5)
K
K
{(Wig ik W wilk = argmin L #ee,
(XWIR), W22.. Wak. y +
+
Wa ll2
1=1
K
((W 1k, Wak. KK
argmin L dee.
Σ
(X.
War
Wak.
Wa
k=1
(22)
20

---

Under review as a conference paper at ICLR 2023
and the objective value achieved by the parameters trained using X,
K
K
pr:= = C
Σ
(xWix).
Wex
Was. y
+ 3
Was ll2.
Then, we have
K
P3
W2n)
W + 8
| l2
k=1
(
Σ
K
(XW11) 1K
W2t
W3k. y
K
W3R ll2 = Pr
+
k=1
k=1
K
K
4
WI.
W2s
W
+ (3 +
|a l|
+
-=1
k
K
C
Σ
(x,
W26
w
+ 3
| l12
(1+
Vm my Ro
A=1
+
Σ
X, Wix
W
W y
+ B k=1
/waall2 ll
(1+
/m mg Ro R
1
(10)
K
K
(1+
Vmumng Roy+1
L
(XWix)+
Wex)
W y
B
w/wlllla
B
k=1
Am 1
/mimyRo,
2
= +
3
where (i) and (iit) follow from the optimality definitions of the original and approximated problems in (22). In addition, (ii) and (iv) follow from the relations below
Σ
(XW1)), Wax) wax.y)
K
Σ
Σ
(XWix). wani)) 1anis - (x.W... wanss) 133s2 + (x. (wass)
sanis .x
11
Σ
Σ
(XW12) wars)) 03k22 (x. (xx.
88
+ L
Σ
Σ
my
h=
Na 12
R
(XWIx).
wanss) wanss - (in) (aoss
+
K m2
(x.W..), warss)
aioess y
R
(XW.:). mmns)) - ((x...))) W2k02)
+ c
Σ
(x. mane
1=
Σ
K m2
Σ
(XW1))_ waxss) ((x.W warss)
+
Σ
K
Σ
my
(x.
warss) ). Se y
<
R
max
(XWI)) wanis)
((x. wanss) Seanzt))
Σ | 11a +
Σ k=
Σ
(xx
(ani)
x x-
1|2
Σ
Miselll
Σ Σ
(x.W.:), wakks)
mosess y
kE[K]
31
11--1
R R max =c[k]
X- &
11
Σ Waaks 12 1
Wwwlll +
Σ
Σ ( (x). s 2a2r2.8
km أس
21

---

Under review as a conference paper at ICLR 2023
mi Ro
E
K
|| 1b2 +
Σ
K mg
Σ (xxWiN) 12=1
wakis) )
Mm ||
Σ Σ (X, (1x: wakss) Wiskig . km1
where we use the convexity and R-Lipschtiz property of the loss function, convexity of E2- norm, 1-Lipschitz property of the ReLU activation, ||x|| I /m||xxl2 for x R". and
max; ΣØ= [[ 2kjutz S from the rescaling in Lemma for (1), (2), (3). (5), and (6) respectively.
A.7 PROOF FOR THE DUAL PROBLEM IN (3)
In order to prove the dual problem, we directly utilize Fenchel duality (Boyd & Vandenherghe, 2004). Let us first rewrite the primal regularized training problem after the application of the rescal- ing Lemma as follows
K Σ (XW1))
PL
min DER",BEO,
((r + 3
Σ ww s.t. y
( WEA- (23)
km
The corresponding Lagrangian can be computed by incorporating the constraints into objective via a dual veriable as follows
K
L(v, w = L (8.y) - v"
(XWIR), ... W(L-1)&) WE + B
w W
We then define the following dual function
g(v) min L(v. ÿ, WL.)
y.wkk
K
K > w
min C Cy. v +
V Σ
(XW11) ... W(1-1)6) WLk + 3
y.wzk
| (XW11)44... W(L-1)&) 11| S B, vk [K],
-v- s.t.
where L is the Fenchel conjugate function defined as (Boyd & Vandenberghe, 2004)
(*(v): == max oJ V- - yz.
Hence, we write the dual problem of (23) as
PÊ = min max g(v) = min max (v) s.t. |77 ((X.i)....Ww-nn)4/ 88, Ak E (K]. 8Ee. v
W(L
9EB,
However, since the hidden layer weights are the variables of the outer minimization, we cannot directly characterize the optimal hidden layer weight in the form above. Thus, as the last step of the derivation, we change the order of the minimization over and the maximization over v to obtain the following lower bound
př. 2 di. = max min v BEE,
(v) s.t.
VT (XXi1)) ... ()o- $ B, Vk E [K]
max - (v) s.t. max v
v (XXW)).... ......) 5B. 8EB,
A.8 HYPERPLANE ARRANGEMENTS
Here, we review the notion of hyperplane arrangements detailed in Pilanci & Ergen (2020).
We first define the of all hyperplane arrangements for the data matrix X
H = ((sin( ((sign(Xw)) (Xw)) : w E Rd),
22

---

Under review as a conference paper at ICLR 2023
where [7|] Σ 2". The set H. all possible {+1, -1} labelings of the data samples {x)]== via linear classifier w E IRd. We now define new set to denote the indices with positive signs for each element in the set as == [[ h E H). With this definition, we note that given an element S, one can introduce a diagonal matrix D(S) E R defined as
D(S) = f1 i
otherwise
D(S) can be also viewed a diagonal matrix of indicators, where each diagonal entry one the the corresponding sample labeled as +1 by the linear classifier w, zero otherwise. Therefore, the output of ReLU activation can be equivalently written as (Xw)+
Xw provided that D 2 0 and (In (()) Xw S are satisfied. One can define more compactly these two constraints as (2D (S) In) Xw N O. We now denote the cardinality of S as P. and obtain the following upperbound
2r (e(n-1) 1
2 2
k
r
k=0
where r == rank(X) I min(n, d) (Ojha, 2000; Stanley et al., 2004; Winder, 1966; Cover, 1965).
A.9 Low RANK MODEL IN THEOREM
In Section 3.1, propose 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 eπror 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 upperhound becomes
(1 + mmmm330,+1 ) which can arbitrarily close to one due to presence of noise component (with small 01) in most datasets in practice (see Figure 4 for an empirical verification). This observation 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 to set the target rank and the value of the regularization coefficient to obtain any desired approximation ratio using Theorem 2.
B
A. PROOF OF PROPOSITION AND COROLLARY
We first review the multi-layer hyperplane arrangements concept introduced in Section 2.1 of Ergen & Pilanci (2021c). Based on this concept, we then calculate the training complexity to globally solve the convex program Theorem
If we denote the number of hyperplane arrangements for the first ReLU layer as PI, then from Appendix A.8 we know that
S c(nn (en- xe O(n").
(24)
In order obtain bound for the number of hyperplane arrangements in the second ReLU layer we first note that preactivations of the second ReLU layer, i.c., (XW1), W2 can be equiv- alently represented as a matrix-vector product form by using the effective data matrix X == Img Dim, X| due to the equivalent representation in (7). Therefore,
[n 12D
given rank rank(X) = T2 S mir
P₂ 2
Σ k=0
-
< 2r
e((n - 1)
2m1r
(e(n - 1)
k
mir
However, notice that X is not fixed data matrix since
choose each diagonal Dij. among (D of size Pt due to (24) and the sign pattern Zí among the (+1, of size 2. Thus, in the worst-case, we have the following upper-bound
22m +1 (c(n - 2m1r
P2 < (m(2)
mi mjr- 1 1m2mr-mm11 2 O(n
(25)
23

---

3000 Under review as a conference paper at ICLR 2023
10
Normalized SVs
Normalized SVs
10
0.06
10-3
0.04
10
0.02
10
100
200
300
400
500
600
700
800
100
200
300
400
500
600
700
800
SV index
SV index
(a) MNIST-Linear scale
(b) MNIST- Log scale
10-1
0.10
Normalized SVs
0.08
10
Normalized
0.06
10-1
0.04
10-1
0.02
10
0.00
0
500
1000
1500
2000 2500 3000
500
1000
1500
2000
2500
SV index
index
(c) -O-Linrr scale
(d) CIFAR- scale
Figure 7: The values of normalized singular values of the data matrix for the MNIST and CIFAR-10 datasets. As illustrated in both figures, the singular values follow an exponentially decaying trends indicating an effective low rank structure.
Notice that given fixed scalars m and r, both P1 and P/2 are polynomial terms with respect to the number of data samples and the feature dimension d.
Notice that Convolutional Neural Networks (CNNs) operate on the patch matrices [X,) b=1 instead of the full data matrix X, where X,, E Rx and h denotes the filter size. Hence, even when the data matrix is full rank, ie., r min d}, the number of hyperplane arrangements
Remark 3.
B
P. is upperbounded as Pi < O(n²=), where == max; (ank(X;) S h < min(n, d} (see Ergen & Pilanci (202Ia) for details). For instance, let us consider a CNN with m, 512 filters of size 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 CNNs in practice.
3 x 3, then
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, P P2 Pa variables and 2n(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 Oddm3323 32 3(m)))())))) which is polynomial-tin time complexity in terms of n, d.
The analysis in this section can be recursively extended to arbitrarily deep parallel networks. First notice that we apply the same approach to obtain an upperbound on Ps, then due to the mul- tiplicative pattern in (25), we obtain P3 P2(222) < mmnmrrr In a similar manner, the number of hyperplane arrangements in the 7th layer is upperbounded as P < O(n" [T/=) my), which polynomial in both and d for fixed data rank and fixed layer widths (m, )
24

---

Under review as a conference paper at ICLR 2023
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 Y E Rxxe provided that there exist C' classes/outputs. Then the primal convex training problem is as follows
L-1
min Pe = min L SEB EOOA(X), Y
+ 3 Σ
Σ
|Wikk l2
II
w 1ik 1=2
| Wikk 112
Applying Lemma and each step in the proof of Theorem yield
d = max min (V) s.t. | ((XWi)) 1I ... W(--IN)+ SB, Ak E [K],
BEO,
where the corresponding Fenchel conjugate function is trace (z'v) (Z,
(V)
Notice that above have dual matrix V instead of the dual vector in the scalar output case. More importantly, here, we have & norm in the dual constraint unlike the scalar output case with absolute value. Therefore, the vector-output case 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 Sahiner al, (2021b).
25


Reviews:
[{"review_id": "xVAkNnOJQ7", "reviewer": "Reviewer_n2WM", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies convex formulations of the problem of training parallel ReLU networks.\n\nThese are models of the form \\sum_{i=1}^K f_i(x; \\theta^i), where each f_i is a ReLU network.\n\nThe problem gives algorithms for exactly/approximately learning these networks with path regularization.\n\nThe result is by a convex formulation of the networks, extending results of Pilanci and Ergen'20 beyond 2 layers.", "summary_of_the_review": "I would be willing to accept this paper if the authors could clarify my confusions and address the weaknesses I have listed above.", "strength_and_weaknesses": "\n### Weaknesses / places I was confused\n\n* I am confused about the duality claimed in (3) and proved in Appendix A.7. It seems that the authors only prove weak duality ($p_L^* \\geq d_L^*$), but then in the subsequent paragraphs they claim that they prove strong duality $p_L^* = d_L^*$ as guaranteed in Lemma 1. However, the Lemma 1 seems to me unrelated to the arguments in Appendix A.7? In Appendix A.4 it is shown there is no duality gap, but only for the case of L = 3 layers. I would also appreciate clarification with what is new here compared to the paper Wang et al. '21, which is cited at the end and proves there is no duality gap in the same setting, but for any L. (Also, Corollary 1 of this paper states that the analysis extends to any number of layers, but no proof is given.)\n\n* The authors state that ResNets are special cases of this parallel network architecture. However, I am unconvinced by this because it requires tying weights (see Appendix A.2) and fixing weights to equal the identity in the parallel network. Doesn't this mean that the optimization problem for finding the minimum-cost ResNet is completely different from the optimization problem for finding the minimum-cost parallel network architecture?\n\n* I found Theorem 1 to be difficult to read. Several new variables have been introduced right before stating this theorem. Specifically \"we first enumerate all possible signs and diagonal matrices for the ReLU layers and denote them as $ I_{j_1}, D_{1ij_{1}}$, \nand $D_{2l}$ respectively, where $j_1 \\in [m_1], i \\in [P_1], l \\in [P_2]$\". This notation is not very clear to me, and also it took some work to understand that the authors must assume that the data lies in a rank $r$ subspace of the $d$-dimensional input space, where effectively $r = O(1)$ for the algorithm to run in polynomial time.\n\n* Since the data must lies in a $r = O(1)$-dimensional subspace of $\\mathbb{R}^d$ for the exact algorithm to run in polynomial time, it seems like a stretch to advertise in the abstract that the algorithm runs in polynomial-time in feature dimension. This is true, but if the rank $r \\ll d$, it seems that one can preprocess the data and project it onto the lower-dimensional space and now treat $d$ as $d = O(1)$.\n\n* The sentence \"Based on the analysis above, exponential complexity is unavoidable for deep networks when the data matrix is full rank, i.e., $rank(X) = min(n, d)$\" is not justified. The previous analysis was an upper bound on running times, and it does not say anything about the (unlikely) possibility that there is a better algorithm that runs in time $\\mathrm{poly}(n,d)$ time for full-rank data.\n\n* Section 3.2 claims \"Here, we provide a complete explanation for the representational power of three-layer networks by comparing with the two-layer results in Pilanci & Ergen (2020)\". However, (1) it is already known in the literature that two-layer networks are universal representers, so Section 3.2 must be about the cost of representing with 2 vs. 3 layers. And (2) it is already known in the literature that there are functions that take exponentially more neurons to represent with 2 layers than with 3 layers. In short, I am unsure what is contributed by Section 3.2.\n\n* Finally, why do the authors take a path regularization instead of an L2 regularization? It would be nice to have an intuitive explanation of \nwhy the former yields a better convex problem than the latter.\n\n### Strengths\n\n* An approximate algorithm is given with a runtime that depends as $n^{\\kappa}$, where $\\kappa$ effective rank of the data. This addresses one of the weaknesses above. The idea here is nice: take a low-rank approximation of the data, and run the exact convex solver on it.\n\n* The authors provide experiments on small datasets and small networks, showing that learning with the convex program can yield better/faster solutions than training with SGD or Adam. I found Table 3 in the appendix particularly impressive. However, I would like to know -- if you take a very wide, overparametrized network, and train it with SGD/Adam, will it still be outperformed by the convex program?\n\n### Typos\n* Footnote 2: \"all proofs are provided in the supplementary file\", should say in appendix A.3\n* \"with three-layer layers\"\n* why is $w_{3k} \\in \\mathbb{R}^K$ ? I think this is a typo\n* \"therefore we show that strong duality holds in this case, i.e., $p_3^* \\geq d_3^*$ as detailed in Appendix A.4\". Should be $p_3^* = d_3^*$", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "FcMNnpvVkCP", "reviewer": "Reviewer_QEB5", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper presented a method to convert the non-convex optimization problem of parallel neural network trained with path regularization into a convex optimization problem, and proposed a low rank approximation to the model such that the model can be trained in polynomial time. Experiments show that the proposed method can achieve higher accuracy than gradient descent-style algorithms in the same amount of time.", "summary_of_the_review": "The paper proposed a new method to train a neural network . The author provided good theoretical support to this method. \nThis method yields higher accuracy and speed in a toy dataset experiments and small image classification tasks. However, there are some flaw in the paper which should be fixed.", "strength_and_weaknesses": "The paper proposed a new method to solve three-layer parallel neural network training problem with path regularization, and experiments show that this method outperform gradient descent-style algorithms in speed and accuracy. \nThere are some flaws in the paper. The path regularization given in Table 2 in different from that in equation 4 by a square root. Is something missing here? \nThe proof of Lemma 1 is not clear to me. $w$ and $w’$ in the third to the last equation in page 16 have 3 subscripts each, while those in the second to the last equation in this page have 4. Besides, the  second to the last equation in this page does not make sense to me.\nSome equations in the appendix go beyond the page boundary. Eg. the last set of equations in page 16.\nSection A.1 mention that results in Figure 5 are computed by converting the constraint optimization problem into an unconstrained one so SGD can be used. I would suggest to move this part to the main paper and thoroughly discuss how to implement this, eg. how to select $\\lambda$.\nIn Figure 5, I suggest the author to add the results of weight decay using Adam, etc., which reflects the most common empirical methods. The accuracy on cifar-10 dataset is too low to make much sense. I would suggest to replace it with MNIST, for example.\nAlso, I am curious whether this method can be extended to neural networks beyond 3 layers. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "8w_zLBQb42", "reviewer": "Reviewer_mUtW", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper studies the training of deep parallel ReLU networks with L2 regularization/weight decay.\nAs has been done for 2 layers Relu networks by Pilanci and Ergen (2020), it derives an equivalent convex reformulation of the original optimization problem. This reformulation involves a group sparsity penalty, that generalizes the results of Pilanci and Ergen (2020).\n\nThe technique is the same as in the original paper: use positive homogeneity of the ReLU to derive an equivalent constrained formulation (Lemma 1), then derive the dual of this formulation and show that strong duality holds, so that the solution of the derived dual can be mapped back to a global solution of the primal. The derivation is based on diagonal binary matrices $D_i$ that correspond to activation patterns of the ReLU layers.\nThe novelty compared to the original paper is the grouping effect over parallel networks, and the extended number of layers.\n", "summary_of_the_review": "Approach marginally improving on known results using same duality techniques. Claims of polynomial time solving are overstated and experiments make it clear that the proposed method is still more of theoretical interest than of practical one. ", "strength_and_weaknesses": "Strengths:\nThe training of deep neural networks is a major topic of interest in the current literature. Understanding how neural networks generalize so well despite the non convex cost function and abundance of bad local minimizers is a critical question.\nHighlighting hidden convexity in such training is a promising direction.\n\nWeaknesses:\n- The \"polynomial\" claim is based on a trick where the design matrix is approximated by a low rank one through a truncated SVD (Eq 10).\nThus **only an approximation is solved**. The original problem remains of exponential complexity as one would expect, and as is mentioned in Table 1. The paper's claim is thus exaggerated in my opinion: the **original** problem is not solved in polynomial time, as there is no indication that $r \\ll \\min (n, d)$ in the general case.\nNevertheless the paper explicitly writes several times sentences such as \"We prove that training the path regularized parallel ReLU networks (1) is equivalent to a convex optimization problem that can be solved in polynomial-time by standard convex solvers\". That is not correct.\n\nThe paper cannot be accepted in its current form due to these claims. Removing them, and saying \"The problem can be approximately solved in polynomial time\" would fix the issue.\n\n- The exponential dependency on the product over the layers of the numbers of hidden neurons also prevents the method from being used practically. I believe it is still of interesting theoretical nature, but the authors may consider acknowledging this fact in the paper.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "0d1VJzJHBrU", "reviewer": "Reviewer_ctH6", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes an \"equivalent\" convex formulation to a family of regularized neural network (with ReLU activation) optimization problems. This has very nice consequences such as interpreting neural network as sparsification machine in overparameterized regime or polynomial time trainability. The authors demonstrate numerically the advantages of considering such formulation.", "summary_of_the_review": "1) The path regularization (which is not explicitly defined in the paper) might be ill defined. Based on Lemma 1, I guess the authors refer to the path $\\beta \\mapsto \\hat \\theta(\\beta)$ where $\\hat \\theta(\\beta)$ is an element of the argmin of the regularized solution. However, the non-uniqueness of the solution implies that the notion of path regularization is ill defined here (a single beta mapsto different solutions).\n\n2) Ambiguity with the notion of “exact solution”.  Standard convex solvers do not provide exact solutions but only approximate to a prescribed tolerance. Can the authors clarify this point specially with respect to proposition 2. More specifically, what does it mean to “solve” the optimization problem globally?  Note that even for vanilla Lasso problem, exact solutions cannot be obtained without exponential complexity in general (explicit worst case example exists.)\n\n3) In proposition 1, provide explicitly the mapping between the convex solution and “the” non-convex one. Since the latter is non-unique, the authors might want to clarify the meaning here. Also, since the exact solution cannot be obtained, how the approximation error affects the claim in the proposition 1.\n\n4) The alternative representation for ReLU in section 3 might be incorrect. Can the authors explain the first equality? \nThe product is $XW_1$ first. I don't understand how the index $j_1$ travels inside the positive part and affects only $W_1$.\n\n\nMinor:\n- Define precisely $\\Theta$\n- The constants $P_1, P_2$ are not defined?\n- Why the bidual objective coincide with the primal? Is it because of strong duality? Can the authors detail that part a bit.\n- The sentence \"Based on the analysis above, exponential complexity is unavoidable for deep networks when the data\nmatrix is full rank\" is confusing since the authors just argue that the complexity is polynomial.\n- After Eq. 6, \"Therefore, we first show that strong duality holds in this case, i.e.,\", it should be an equality\n- The first sentence after Eq 6 is very confusing too.\n- In figure 3, what does the points $(1, 0), (2,2), (3,3)$ represent? The message of this figure is quite unclear.\n- Define $h_C$ in Eq. 11\n- After Eq. 14, the index is missing on $XW$ ? Why does the sum disappear in the second equivalence?\n- More comments on the generalization to more than 3 Layers ", "strength_and_weaknesses": "The main result, provably polynomial time training for neural nets, is quite strong and novel.\n\nThe major weakness is that the paper is very hard to read, and the authors should benefit from simplifying the notation and improving the clarity.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject