Globally Optimal Training of Neural Networks with Threshold Activation Functions
Authors: Tolga Ergen
Halil Ibrahim Gulluk
Jonathan Lacotte
Mert Pilanci
Venue: ICLR 2023 poster (2023)
Keywords: Convex optimization
Lasso
threshold activation
binary activation
quantization
neural networks

Abstract: Threshold activation functions are highly preferable in neural networks due to their efficiency in hardware implementations. Moreover, their mode of operation is more interpretable and resembles that of biological neurons. However, traditional gradient based algorithms such as Gradient Descent cannot be used to train the parameters of neural networks with threshold activations since the activation function has zero gradient except at a single non-differentiable point. To this end, we study weight decay regularized training problems of deep neural networks with threshold activations. We first show that regularized deep threshold network training problems can be equivalently formulated as a standard convex optimization problem, which parallels the LASSO method, provided that the last hidden layer width exceeds a certain threshold. We also derive a simplified convex optimization formulation when the dataset can be shattered at a certain layer of the network. We corroborate our theoretical results with various numerical experiments.

Published as a conference paper at ICLR 2023
GLOBALLY OPTIMAL TRAINING OF NEURAL NET- WORKS WITH THRESHOLD ACTIVATION FUNCTIONS
Tolga Ergen, Halil Ibrahim Gulluk, Jonathan Lacotte & Mert Pilanci
Department of Electrical Engineering
Stanford University Stanford, CA 94305, USA {ergen, gulluk, lacotte, pilaancjjsstanfordd.ee
ABSTRACT
Threshold activation functions are highly preferable in neural networks due their efficiency in hardware implementations. Moreover, their mode of operation is more interpretable and resembles that of biological neurons. However, tradi- tional gradient based algorithms such as Gradient Descent cannot be used to train the parameters neural networks with threshold activations since the activation function has zero gradient except at single non-differentiable point. To this end, we study weight decay regularized training problems of deep neural networks with threshold activations. We first show that regularized deep threshold network training problems can be equivalently formulated as standard convex optimization problem, which parallels the LASSO method, provided that the last hidden layer width exceeds certain threshold. We also derive a simplified convex optimization formulation when the dataset can be shattered at certain layer of the network. We corroborate our theoretical results with various numerical experiments.
INTRODUCTION
In the past decade, deep neural networks have proven remarkably useful in solving challenging prob- lems and become popular in many applications. The choice of activation plays crucial role in their performance and practical implementation. In particular, even though neural networks with popular activation functions such as ReLU are successfully employed, they require advanced computational resources in training and evaluation, e.g., Graphical Processing Units (GPUs) (Coates et al., 2013). Consequently, training such deep networks is challenging especially without sophisticated hardware. the other hand, the threshold activation offers multitude of advantages: (1) computational effi- to binary latent dimension, (3) interpretability. Unfortunately,
ciency, (2) compression/quantiaaiiii gradient based optimization methods fail in optimizing threshold activation networks due to the fact that the gradient is zero almost everywhere. To close this gap, analyze the training problem of deep neural networks with the threshold activation function defined as
{
if x 2 0
T. (x) :- s1 1
-
0}
(1)
otherwise
where s E IR is a trainable amplitude parameter for the neuron. Our main result is that globally optimal deep threshold networks be trained by solving convex optimization problem.
1.1 WHY SHOULD WE CARE ABOUT THRESHOLD NETWORKS?
Neural networks with threshold activations highly desirable due to the following reasons:
Since the threshold activation (1) is restricted to take values in {0, s), threshold neural network models are far more suitable for hardware implementations (Bartlett & Downs, 1992; Corwin et al., 1994). Specifically, these networks have significantly lower memory footprint, less computational complexity, and consume less energy (Helwegen et al., 2019).
Modern neural networks have extremely large number of full precision trainable parameters so that several computational barriers emerge during hardware implementations. One approach to

---

Published as a conference paper at ICLR 2023
Objective Value
10a
Renconves-Toll Triiee
Objective Value
Objective Value
Rencames-Trrue2 Truik2
1.F
honcomex
Trair
20
10'7
(Ours)
10"2
1620
0
Time(s)
Time(s)
Time(s)
(a) (n, d) (20, 100)
(b) (m,, d) (50,50)
(c) (n, d) (100,20)
Figure 1: Training comparison of our convex program in (7) with the non-convex training heuristic
STE. We also indicate the time taken to solve the convex programs with markers. For non-convex STE, we repeat the training with 5 different initializations. In each case, our convex training algorithms achieve lower objective than all the non-convex heuristics (see Appendix B.5 for details).
mitigate these issues is reducing the network size by grouping the parameters via hash function (Hubara et al., 2017; Chen et al., 2015). However, this still requires full precision training before the application of the hash function and thus fails remedy the computational issues. On the other hand, neural networks with threshold activations need a minimal amount of bits.
Another approach reduce the complexity is quantize the weights and activations of the network (Hubara et al., 2017) and the threshold activation is inherently in two level quantized form. The threshold activation is a valid model to simulate the behaviour of a biological neuron as detailed in Jain et al. (1996). Therefore, progress in this research field could shed light into the connection between biological and artificial neural networks.
1.2 RELATED WORK
Although threshold networks essential for several practical applications as detailed in the previous section, training their parameters is difficult -on-differentiable optimization problem due to the discrete nature in (I). For training of deep neural networks with popular activations, the common practice is to use first order gradient based algorithms such as Gradient Descent (GD) since the well known backpropagation algorithm efficiently calculates the gradient with respect to parameters. However, the threshold activation in (I) has zero gradient except at a single non-differentiable point zero, and therefore, one cannot directly use gradient based algorithms train the parameters the network. In order to remedy this issue numerous heuristic algorithms have been proposed in the literature as detailed below but they still fail to globally optimize the training objective (see Figure 1).
The Straight- Through Estimator (STE) is widely used heuristics to train threshold networks (Bengio et al., 2013; Hinton, 2012). Since the gradient is zero almost everywhere, Bengio et al. (2013); Hinton (2012) proposed replacing the threshold activation with the identity function during only the backward pass. Later on, this approach is extended to employ various forms of the ReLU activation function, e.g., clipped ReLU, vanilla ReLU, Leaky ReLU (Yin et al., 2019b; Cai et al., 2017; Xiao et al.), during the backward pass. Additionally, clipped versions of the identity function were also used an alternative to STE (Hubara et al., 2017; Courbariaux et al., 2016; Rastegari et al., 2016).
1.3
CONTRIBUTIONS
We introduce polynomial-time trainable convex formulations of regularized deep threshold network training problems provided that a layer width exceeds a threshold detailed Table
In Theorem 2.2, prove that the original non-convex training problem for two-layer networks is equivalent to standard convex optimization problems.
We show that deep threshold network training problems equivalent to standard convex optimiza- tion problems in Theorem 3.2. In stark contrast to two-layer networks, deep threshold networks have richer set of hyperplane arrangements due multiple nonlinear layers (see Lemma 3.5). In Section 3. we characterize the evolution of the set of hyperplane arrangements and consequently hidden layer representation space as a recursive process (see Figure 3) the network gets deeper. We prove that when a certain layer width exceeds ((/n// L). the regularized L-layer threshold network training further simplifies a problem that can be solved in (n) time.
2

---

Published as a conference paper at ICLR 2023
Table Summary of our results for the optimization of weight decay regularized threshold network training problems (n: # of data samples, d: feature dimension, my: # of hidden neurons in layer 1, r: rank of the training data matrix, m²: critical width, i.e. # of neurons that obeys S m - n 1)
Result
Depth
Complexity O(a"r)
Minimum width m 2 m 2
Globally optimal
Thenrem 2.2
Viconvex opt)
Thenrem 2.3
((n)
V (convex opt)
Theorem 3.2
O(n 11-- m))
ML-1 2 m
v (convex opt)
Corollary 3.4
((n)
-I -l: my 2 Olyn/L)
V (convex opt)
Notation and preliminaries: We use lowercase and uppercase bold letters to denote vectors and matrices, respectively. We also use [n]] to denote the set 2........ n). We denote the training data matrix consisting of d dimensional n samples as X E Rnxdd label vector as E IR", and the 7 layer weights of a neural network as W(() E 1=m Xmy, where my = my
TWO-LAYER THRESHOLD NETWORKS
We first consider the following two-layer threshold network
fo2(X)=o,(XW
3y 9 FOXW522000 2203u
(2)
where the set of the trainable parameters are W()) E Rdxm_ E RM w(2) E R. and 0 is a compact representation for the parameters, i.e., 0= (W(1), s, w(2)). Note that we include bias terms by concatenating vector of ones to X. Next, consider the weight decay regularized training objective
B m
P2 Pnonevx
W( w 2 |l,o,((X) y11
min
+
Σ
(I
11 |s,s,11 (wm (2)
(3)
2
j=1
Now, we apply a scaling between variables 8j and w to reach an equivalent optimization problem.
Lemma 2.1 (Optimal scaling). The training problem in (3) can be equivalently stated as
P Pnonevx min (l - y1l + dee,
(4)
where θ, = {0: |8y| = 1, E [m]].
We next define the set of hyperplane arrangement patterns of the data matrix X
H(X)= (1 2 0) Rd) C 10,1)"
(5)
We denote the distinct elements of the set H(X) by di,.... dp E 10" where P:= [X( is the number of hyperplane arrangements. Using this fixed of hyperplane arrangements {d,),-) we next prove that (4) is equivalent to the standard Lasso method (Tibshirani, 1996).
Theorem 2.2. Let m 2 m", then the non-convex regularized training problem (4) is equivalent to
DEvx
min WEBP
DDw 1a--llll y12 B||w11,,
(6)
2
where = [d] d2 dp} a fixed n P matrix. Here, m² is the cardinality of the optimal solution, which satisfies m² S + Also, it holds that Pronevx = Pevx
Theorem 2.2 proves that the original non-convex training problem in (3) can be equivalently solved as standard convex Lasso problem using the hyperplane arrangement patterns as features. Surprisingly, the non-zero support of the convex optimizer in (6) matches to that of the optimal weight-decay regularized threshold activation neurons in the non-convex problem (3). This brings us two major advantages over the standard non-convex training:
Since (6) standard convex problem, it can be globally optimized without resorting to non-convex optimization heuristics, e.g., initialization schemes, learning rate schedules etc. Since (6) is convex Lasso problem, there exists many efficient solvers (Efron et al., 2004).

---

Published as a conference paper at ICLR 2023
2.1 SIMPLIFIED CONVEX FORMULATION FOR COMPLETE ARRANGEMENTS
We now show that if the set of hyperplane arrangements of X is complete, i.e., H - {0, 13" contains all boolean sequences of length n, then the non-convex optimization problem in (3) can be simplified. We call these instances complete arrangements. In the case of two-layer threshold networks, complete arrangements emerge when the width of the network exceeds a threshold, specifically 2 n +
We note that the m 2 n. regime, also known as memorization, has been extensively studied in the recent literature (Bubeck al., 2020; de Dios & Bruna, 2020; Pilanci & Ergen, 2020; Rosset et al., 2007). Particularly, these studies showed that as long as the width exceeds the number of samples, there exists a neural network model that can exactly an arbitrary dataset. Vershynin (2020); Bartlett et al. (2019) further improved the condition on the width by utilizing the expressive power of deeper networks and developed more sophisticated weight construction algorithms fit the data.
Theorem 2.3. We assume that the set of hyperplane arrangements of X complete, i.e., equal the set of all length-n Boolean sequences" H = {0, 1}". Suppose m 2 + 2, then (4) is equivalent to
peex
8 y 1( + +1(++11()))))) 11(-8)+11=)). RER"
min
and it holds that P = P22. Also, one can construct an optimal network with n + neurons in time (n) based the optimal solution to the convex problem (7).
Based on Theorem 2.3, when the data matrix can be shattered, i.e., all 2" possible y E {0, 1)"" labelings of the data points can be separated via a linear classifier, it follows that the set of hyperplane arrangements is complete. Consequently, the non-convex problem in (3) further simplifies to (7).
2.2 TRAINING COMPLEXITY
We first briefly summarize our complexity results for solving (6) and (7), and then provide the details of the derivations below. Our analysis reveals two interesting regimes:
(incomplete arrangements) When n n 2 m 2 m", we can solve (6) in (n²*)) complexity, where whenever the rank r is fixed.
r := ran. Notice this polynomial-time
(complete arrangements) When m 2 n 2, we can solve (7) in closed-form, and the reconstruction of the non-convex parameters (()) and (2) only ((n) time independent of d.
Computational complexity of (6): To solve the optimization problem in (6), we first enumerate all possible hyperplane arrangements {d.)-= It is well known that given a rank-r data matrix the number of hyperplane arrangements P is upper bounded by (Stanley et al., 2004; Cover, 1965)
(enn= (e(n-1)
P
< 2r
where r = rann(X) < min(n, d). Furthermore, these can be enumerated in O(n") (Edelsbrunner et al., 1986). Then, the complexity for solving (6) is ((P3) x O(n"r) (Efron et al., 2004).
Computational complexity of (7): The problem in (7) is the proximal operator of a polyhedral norm. Since the problem is separable over the positive and negative parts of the parameter vector 5, the optimal solution can be obtained by applying two proximal steps (Parikh & Boyd, 2014). As noted in Theorem 2.3, the reconstruction of the non-convex parameters (1) and w(2) requires ((n) time.
2.3 GEOMETRIC INTERPRETATION
To provide geometric interpretation, we consider the weakly regularized case where 3 + 0. In this case, (6) reduces to the following minimum norm interpolation problem
||/ s.t. WERP
min
Dw= =w
Proposition 2.4. The minimum E norm interpolation problem in (9) can be equivalently stated as mint 220
s.t. E yCtConv(+d, Vj E [P]}.
4

---

Published as a conference paper at ICLR 2023
where Conv(A) denotes the convex hull of a set A. This corresponds the gauge function (see Rock- afellar (2015)) of the hyperplane arrangement patterns and their negatives. We provide visualizations of the convex set Conv Vj E [P]] in Figures 3 and (see Appendix) for Example 3.1.
Proposition 2.4 implies that the non-convex threshold network training problem in (3) implicitly represents the label vector y as the convex combination of the hyperplane arrangements determined by the data matrix X. Therefore, we explicitly characterize the representation space of threshold networks. We also remark that this interpretation extends to arbitrary depth as shown in Theorem 3.2.
2.4 HOw TO OPTIMIZE THE HIDDEN LAYER WEIGHTS?
After training via the proposed convex programs in (6) and (7), we need to reconstruct the layer
weights of the non-convex model in (2). We first construct the optimal hyperplane arrangements d; for (7) as detailed in Appendix A.4. Then, we have the following prediction model (2). Notice
(1) to any other vector w with same norm and such that 1 ((Xw)") > 0} 1 [[ww) 2 0}
changing w; j
does not change the optimal training objective. Therefore, there are multiple global optima and the
one we choose might impact the generalization performance as discussed in Section 5.
3 DEEP THRESHOLD NETWORKS
We now analyze L-layer parallel deep threshold networks model with m subnetworks defined as
(x)
Σ
xilz
(X (I- (1-1))
W
Dw (I)
(10)
k=1
where 0:= ((W())
11 1m 1, 1.0 : 10 w!!
Rm 1xm1 .8 E R VI, k},
0 x-
WE
and the subscript & is the index for the subnetworks (see Ergen & Pilanci (2021a;b); Wang al. (2023) for more details about parallel networks). We next show that the standard weight decay regularized training problem can be cast an -oomm minimization problem in Lemma 2.1.
Lemma 3.1. The following L-layer regularized threshold network training problem
Phonevx min ff, M88 2
1 y1
8 MZ-1
( 19 11=
(11)
be reformulated
P Phonevx min [l/,,,(() y112 311 (1)
(12)
8EB, 2
where O, := 1 (1- (1-1)) 1}.
3.1 CHARACTERIZING THE SET OF HYPERPLANE ARRANGEMENTS FOR DEEP NETWORKS
We first define hyperplane arrangements for L-layer networks with single subnetwork (i.e., my-1 1, thus, we drop the index k). We denote the set of hyperplane arrangements as
Hr {1 w. (I-1) > 0} : 8
We also denote the elements of the set HX,(X) X) by di....,,d, dr... E 1]" and PL-1 (X)
the number of hepelalane arrangements in the layer L 1-1.
To construct the hyperplane arrangement matrix ( we define a matrix valued operator as follows
D A(X) jd, d2 ... drl (
U (D W [-2]].
(13)
S =m=
5

---

Published as a conference paper at ICLR 2023
Here, the operator (-) outputs matrix whose columns contain all possible hyperplane arrangements corresponding its input matrix in (5). In particular, ( denotes the arrangements for the first layer given the input matrix X. The notation D {0, 1 denotes the submatrix of D E {0. 1 1)=* indexed by the subset size my, Finally, LJ is operator that takes union of these column vectors and outputs a matrix of size n x Pi+1 containing these as columns. Note that we may omit repeated columns and denote the total number of unique columns as P1+1, since this does not change the value of our convex program.
its columns, where the index runs over all subsets of
We next provide analytical example describing the construction of the matrix D
Example 3.1. We illustrate an example with the training data X [-1 1:0 1;1 1] E R Inspecting the data samples (rows of X). observe that all possible arrangement patterns are
0 D = A = 0
1
0
-
=6
(14)
0
For the second layer, we first specify the number of neurons the first layer as my 2. Thus, we need to consider all possible column pairs in (14). We have
0
0
0
0
0
0
0
0
0
1
(1.2}
0
1
0
1
0
1
0
0
07
0
07
0
1
17
(1)
0
1
= A
0
(1,3)
[
1
0
1
0
1
0
We then construct the hyperplane arrangement matrix as
0
0
D L A ( 2
0
1
0
1
1
0
0
1
which shows that P2 8. Consequently, obtain the maximum possible arrangement patterns, i.e., (0, 1)3, in the second layer even though we are not able to obtain some of these patterns in the first layer in (14). We also provide three dimensional visualization of this example in Figure 3.
3.2 POLYNOMIAL- TIME TRAINABLE CONVEX FORMULATION
Based on the procedure described in Section 3.1 to compute the arrangement matrix D we now derive exact formulation for the non-convex training problem in (12).
Theorem 3.2. Suppose that mL-1 2 m², then the non-convex training problem (12) is equivalent to min WEB
D -x11 Bl[wll
P
(15)
where D(4-1) E 1n is fixed matrix constructed via (13) and m denotes the cardinality Also, holds that Puoncvx P
of the optimal solution, which satisfies where m
Theorem 3.2 shows that two-layer and deep networks simplify to very similar convex Lasso problems (i.e. (6) and (15)). However, the of hyperplane arrangements larger for deep networks as analyzed in Section 3.1. Thus, the structure of the diagonal matrix D and the problem dimensionality are significantly different for these problems.
3.3 SIMPLIFIED CONVEX FORMULATION
Here, we show that the data X can be shattered certain layer, i.e., Hi(X) {0, 11th for certain I E [L], if the number of hidden neurons in a certain layer my satisfies m; 2 C./n/L Then we simpler convex problem. Therefore, compared to the two-layer networks Section 2.1, we substantially improve the condition on layer width by benefiting from the depth I., which also confirms the benign impact of the depth the optimization.
alternatively formulate (11)

---

Published as a conference paper at ICLR 2023
Lemma 3.3. 3f C. such that mi 2 C.TiLL, then the of hyperplane arrangements is complete, i.e. (x) = {0.
We next use Lemma 3.3 to derive a simpler form of (11).
Corollary 3.4. As direct consequence of Theeoem 2.3 and Lemma 3.3, the non-convex deep threshold network training problem in (12) can be cast as the following convex program
1 min | y112 3(11(0) + + +1| (1(-6)+llso). SER" 2
Ph = P22
Surprisingly, both two-layer and deep networks share the same convex formulation in this case. However, notice that two-layer networks require a condition on the data matrix in Theorem 2.3 whereas the result in Corollary 3.4 requires milder condition the layer widths.
3.4 TRAINING COMPLEXITY
Here, we first briefly summarize our complexity results for the convex training of deep networks. Based the convex problems in (15) and Corollary 3.4, we have two regimes:
When n+I 2 mL-1 m", we solve (15) with (n I m*) complexity, where rank (X). Note that this polynomial-time when and the number of neurons in each layer {mi {m/]/=² are constants.
When 31, C: my 2 C/v/LL we solve (7) in closed-form, and the reconstruction of the non-conver parameters requires (n) time as proven in Appendix A.9.
Computational complexity for (15): We first need to obtain an upperbound on the problem dimen- sionality PL-1, which is stated in the next result.
Lemma 3.5. The cardinality of the hyperplane arrangement set for an L--ayer network (X)
can be bounded as [X)( = Pt-11 1 S O(n" "T'=i m,), where r = rank(X) and my denotes the number of hidden neurons in the th layer.
Lemma 3.5 shows that the set of hyperplane arrangements gets significantly larger as the depth of the network increases. However, the cardinality of this set is still polynomial term since that min(n, df and {m) are fixed constants.
To solve (15), we first enumerate all possible arrangements { to construct the matrix (4-11), Then, solve standard convex Lasso problem, which requires ((P).)) complexity (Efron et al., 2004). Thus, based on Lemma 3.5, the overall complexity is O(P)_2) x On II= m=).
Pt-1
Computational complexity for (7): Since Corollary 3.4 yields (7), the complexity is O(n) time.
EXTENSIONS TO ARBITRARY LOSS FUNCTIONS
In the previous sections, considered squared error as the loss function give clear description of our approach. However, all the derivations extend to arbitrary convex loss. Now, we consider the regularized training problem with convex loss function C(. y), e.g., hinge loss, cross entropy.
3
mL
( 2 I 11))
min C(fo +
(16)
BE
2
Then, have the following generic loss results. Corollary 4.1. Theorem 3.2 implies that when mL-1 2 m" (16) can be equivalently stated as L (D(L-))
pexx min
(17)
WERPL-1
Alternatively when (x) {0, 13", based on Corollary 3.4, the equivalent convex problem is
min C( y) (() + (l(=))+
(18)
BER
Corollary 4.1 shows that (17) and (18) are equivalent to the non-convex training problem (16). More importantly, they can be globally optimized via efficient convex optimization solvers.
7

---

Published as a conference paper at ICLR 2023
Objective Value
10
Pall)
i Acc
1.00
0.80
Test Acc
136-
Conlaso (Dkan))
(Duem)
30.85-
0.90-
0.75
0.00
0.75
10
84
0.65
0.0
0.5
10
1.5
2.0
2.5
3.0
3.5
0.00
00
0.5
1.0
15
2.0
2.5
2.5
0.0
0.5
1.0
1.5
2.0
25
36
Time(s)
Time(s)
Time(s)
(a) (n, d, m1, m2) (100, 20, 1000, 100)
Objective Value
10
Weseeven
0.70
10a
0.5
0.65-
Natiemues (eell
10"
Conwer-f (Bur))
D0.5
0.60
0.00
Test
0.55
1074
0.20
0.50
X-X
0.65-
0.0
0.5
1.0
1.5
2.0
3.0
0.
05
15
2.0
25
3.0
0.0
0.5
2.0
25
30
355
Time(s)
Time(s)
Time(s)
(b) (n, d, m1, m2)
(50,50) 50, 1000, 50)
Objective Value
Mecomand'
1.00-
10"
UKLD
0.5
(Duen)
80
0.50
10:2
0.75
0.70
10"0
15
0.60
1.0
25
Time(s)
Time(s)
Time(s)
(c) (n, d, mi, m2) = (20, 100, 1000, 20)
In this figure, we compare the classification performance three-layer threshold networks trained with the setup described in Figure for single initialization trial. This experiment shows that our convex training approach not only provides the globally optimal training performance but also generalize remarkably well on the test data (see Appendix B.5 for details).
Figure 2:
EXPERIMENTS
In this section', present numerical experiments verifying our theoretical results in the previous sections. As discussed in Section 2.4, after solving the proposed convex problems in (15) and (7), there exist multiple set of weight matrices yielding the same optimal objective value. Therefore. to have a good generalization performance construction of the non-convex parameters { ( _ Below, we provide details regarding the weight construction and review some baseline non-convex training methods.
test data, we use some heuristic methods for the
Convex-Lasee To solve the problem (15), we first approximate arrangement patterns of the data matrix X by generating i.i.d. Gaussian weights G gdxP and subsample the arrangement patterns via [ 2 Oj. Then, we use G as the hidden layer weights to construct the network. We repeat this process for every layer. Notice that here sample fixed subset of arrangements instead of enumerating all possible arrangements. Thus, this approximately solves (15) by subsampling its decision variables, however, still performs significantly better than standard non-convex training.
Convex-PE After solving (7), to recover the hidden layer weights of (2), we solve 1 (Xw]) 2 0}
dy as w xidd, where X denotes the pseudo-inverse of X. The resulting weights w
(1) enforce
the preactivations Xw to be zero or one. Thus, if an entry slightly higher or less than zero due to precision issues during the pseudo-inverse, it might give wrong output after the threshold activation.
To avoid such cases, we use 0.5 threshold in the test phase, i.c., 1 1(Xtest w. 2 0.5).
ConveX-SVM: Another approach to solve 1 ((
(1) 2 0} = d, is to use Support Vector Machines
We provide additional experiments and details in Appendix
8

---

Published as a conference paper at ICLR 2023
Table 2: Test performance comparison on CIFAR-10 (Krizhevsky et al., 2014), MNIST (LeCun), and UCI (Dua & Graff, 2017) datasets. We repeat simulations over multiple seeds with two-layer networks and compare the mean/std of the test accuracies of non-convex heuristics trained with SGD with our convex program in (6). Our convex approach achieves highest test accuracy for 9 of 13 datasets whereas the best non-convex heuristic achieves the highest test accuracy only for 4 datasets.
Dutnect
Cesves-Lass (Ours)
Nevoonees-ST STE
Nancouees ReLU
Natcoures LRaLU
NenomnecsCBell
Accuracy
Tanoyo
Accuracy
Tamaaa
Accuracy
Tindds)
Accurscy
Tineds)
Accuracy
Timett
CHARR-I 10
0.816 0.00s
0.31
B.5 11001
151.5 4.3
1 811 0.014
15.8 L.7
0.708 (1351
12.1 6.5
0.815 100044
57.3 1:43
MNIST
0.5001 =: 1.9c
00.4 2- 0.1
0,0085 + 3.5c
2,5064 = 4.G.
62.4 = D.]
0,9065 = 2.Bc.
T0.5 0.1
0,0065 + =:2.=
bank
0,805 +-0007
7.75 0:331 1.03
0 4-0.00
6-68.2.00
0.0.0 06
0.000 2-0 0.008
5,00 0.10
0.5m =00 0.005
5.41 2.0.1
0.807 2-0.05
6.55 n:111
chessloskp
0.78
0,818
3.64 0.52
0 0-001
3.83:4-0.61
0.0.04
0.51
0.501 =00013
5.70 0.365
0.817 5-0000
6:59=0013
oxcges-4 4d
0.787 4 0.030
2.23 0.00
0.787 5 0.038
3.01 4-0
0 0.70 8 0.023
7.00 0003=000 0.27
0.733 0.000
0.23 0.13
0.722 000000
5.0020004
T90 0-000---33
1:90-1 0.06
0.776 0-633
3:21-400:5
0 2-0.03
6.07 0.00
0.T15 0007
0.89 00000
0.781 4-0.03
5.46-0.0
0.33-4:00 0:333
0.067
0.719 0-000
0:11
0.717
0.033
0.736
0.735 +-0005
5.59 0.00
sperehoo
00:00-
0:01 4-0 0:31
0.911 0.004
7:41 0.00
(1915 6 0.035
6.1 0.07
0.001 - 0.003
0778- 0.30
0.038 0.005
6.61 -011
sarlgggrmmn
0.761 0-0.00
3
0.00
0
0-0.3
3.81 0.00
0 T90 0-037
0.33 0.05
0 01:3
0.89 0.07
0.758 000-37
5.15 -.17
0.778 0-004
0.03
à 0.034
0 4 0.076
0.017
4 0.076
5.19
(SVMs), which find the maximum margin vector. Particularly, we set the zero entries of d: as -1 and then directly run the SVM to get the maximum margin hidden neurons corresponding to this arrangement. Since the labels are in the form (+1,-1} in this case, we do not need additional thresholding as in the previous approach.
Nonconvex-STE (Bengio et al., 2013): This is the standard non-convex training algorithm, where the threshold activations is replaced with the identity function during the backward pass.
STE Variants: We also benchmark against variants of STE. Specifically, we replace the threshold activation with ReLU (Nonconvex-Rel) (Yin et al., 2019a)), Leaky ReLU (Nonconvex-LRelle (Xiao et al,)), and clipped ReLU (Nonconvex-CReLU (Cai et al., 2017)) during the backward pass.
Synthetic Datasets:
We compare the performances of Convex-PI and Convex-SVM trained via (7) with the non-convex heuristic methods mentioned above. We first run each non-convex heuristic for five different initializations and then plot the best performing one in Figure 1. This experiment clearly shows that the non-convex heuristics fail to achieve the globally optimal training performance provided by our convex approaches. For the same setup, we also compare the training and test accuracies for three different regimes, i.e., n > d, n = d, and n < d. As seen in Figure 2, our convex approaches not only globally optimize the training objective but also generalize well on the test data.
In Table 2, we compare the test accuracies of two-layer threshold network trained via our convex formulation in (15), i.e., Convex-Lasso and the non-convex heuristics mentioned above. For this experiment, we use CIFAR-10 (Krizhevsky et al., 2014), MNIST (LeCun), and the datasets in the UCI repository (Dua & Graff, 2017) which are preprocessed as in Fernández-Delgaan (2014), Here, our convex training approach achieves the highest test accuracy for most of the datasets while the non-convex heuristics perform well only for few datasets. Therefore, we also validates the good generalization capabilities of the proposed convex training methods on real datasets.
Real Datasets:
et al.
CONCLUSION
We proved that the training problem of regularized deep threshold networks can be equivalently formulated as standard convex optimization problem with a fixed data matrix consisting of hyper- plane arrangements determined by the data matrix and layer weights Since the proposed formulation parallels the well studied Lasso model, we have two major advantages over the standard non-convex training methods: 1) We globally optimize the network without resorting to any optimization heuris- tic or extensive hyperparameter search (e.g., learning rate schedule and initialization scheme); 2) We efficiently solve the training problem using specialized solvers for Lasso. We also provided a computational complexity analysis and showed that the proposed convex program can be solved in polynomial- time. Moreover, when a layer width exceeds certain threshold, a simpler alternative convex formulation can be solved in (n). Lastly, as a by product of our analysis, we characterize the recursive process behind the set of hyperplane arrangements for deep networks. Even though this set rapidly grows as the network gets deeper, globally optimizing the resulting Lasso problem still requires polynomial-time complexity for fixed data rank. We also note that the convex analysis proposed in this work is generic in the sense that it can be applied to various architectures including batch normalization (Ergen al., 2022b), vector output networks (Sahiner et al., 2020; 2021), poly- nomial activations (Bartan & Pilanci, 2021), GANs (Sahiner et al., 2022a), autoregressive models (Gupta et al., 2021), and Transformers (Frgen et al., 2022a; Sahiner al., 2022b).

---

Published as a conference paper at ICLR 2023
7 ACKNOWLEDGEMENTS
This work was partially supported by the National Science Foundation (NSF) under grants ECCS- 2037304, DMS-2134248, NSF CAREER award CCF-2236829, the U.S. Army Research Office Early Career Award W91 INF-21-1-0242, Stanford Precourt Institute, and the ACCESS - Al Chip Center for Emerging Smart Systems, sponsored by InnoHK funding, Hong Kong SAR.
REFERENCES
Burak Bartan and Mert Pilanci. Neural spectrahedra and semidefinite lifts: Global convex op- timization of polynomial activation neural networks in fully polynomial-time -imee. arXiv preprint arXiv:2101.02429, 2021.
Peter L. Bartlett and Tom Downs. Using random weights to train multilayer networks hard- limiting units. IEEE Trans. Neural Networks, 3(2):02--200, 1992. doi: 10.1109/22.25561. URL https:// /tt.///oi..//////////////... www.orggoooooo wwt....111....1.6666
Peter L. Bartlett, Nick Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly-tight ve-dimension and pseudodimension bounds for piecewise linear neural networks, Journal of Machine Learning Research, 20(63):1-17, 2019. URL http: jmlr. org. pttrg/papps///200.
/ 612 html.
Yoshua Bengio, Nicholas Léonard, and Aaron Courville. Estimating propagating gradients through stochastic neurons for conditional computation. arXiv preprint / 2013.
Stephen Boyd and Lieven Vandenberghe. Corvex optimization. Cambridge university press, 2004.
Sébastien Bubeck, Ronen Eldan, Yin Tat Lee, and Dan Mikulincer. Network size and size of the weights in memorization with two-layers neural networks. Advances in Neural Information Processing Systems, 33:4977-4986, 2020.
Zhaowei Cai, Xiaodong He, Jian Sun, and Nuno Vasconcelos. Deep learning with low precision by half-wave gaussian quantization. Computer Vision and Pattern Recognition, 2017.
Wenlin Chen, James Wilson, Stephen Tyree, Kilian Weinberger, and Yixin Chen. Compressing neural networks with the hashing trick. In International conference on machine learning, pp. 2285-2294,
PMLR, 2015.
Adam Coates, Brody Huval, Tao Wang, David Wu, Bryan Catanzaro, and Ng Andrew. Deep learning with cots hpc systems. In International conference machine learning, pp. 1337-1345. PMLR, 2013.
Edward M. Corwin, Antonette M. Logar, and William J. B. Oldham. An iterative method for training multilayer networks with threshold functions. IEEE Trans. Neural Networks, 5(3):507-508, 1994. doi: 10.1109/72.286926 URL https: / doi org/10 11...1109/77... 2277722.66222 286926.
Matthieu Courbariaux, Itay Hubara, Daniel Soudry, Ran El- Yaniv, and Yoshua Bengio. Binarized neural networks: Training neural networks with weights and activations constrained +1 or -1. arXiv preprint arXiv:1602.02888 2016.
Thomas M Cover. Geometrical and statistical properties of systems of linear inequalities with
applications in pattern recognition. IEEE transactions on electronic computers, (3):326-334, 1965.
Jaume de Dios and Joan Bruna. On sparsity in overparametrised shallow relu networks. arXiv
preprint arXiv:2006. 10225, 2020.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL http://///archi ics. www.uciiee. aici.edu/ml.
Herbert Edelsbrunner. Joseph O' O'Rourke, and Raimund Seidel. Constructing arrangements of lines and hyperplanes with applications. SIAM Journal on Computing, 15(2):34-333, 1986.
Bradley Efron, Trevor Hastie, lain Johnstone, and Robert Tibshirani. Least angle regression. The Annals of statistics, 32(2):407-499, 2004.
10

---

Published as a conference paper at ICLR 2023
Tolga Ergen and Mert Pilanci. Convex geometry and duality of over- pere-paramttriieed neural networks. arXiv preprint arXiv:2002.11219 2020.
Tolga Ergen and Mert Pilanci. Global optimality beyond layers: Training deep relu networks via convex programs, 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. 2993-3003. PMLR, 18-24 Jul 2021a. ergen21a a html.
URL https:::p.... /ttp://roceeeee igg w..r.press/vi3.
Tolga Ergen and Mert Pilanci. Path regularization: A convexity and sparsity inducing regularization for parallel relu networks. arXiv preprint arXiv: 10x00-2110.09548, 2021b.
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 2021c. URL http: http:///oocceeddeeee mml. prwss/essssse........ /vcss/vv1339/ wtt.s//rsss////////eee http///199eeeeeeeee html.
Tolga Ergen, Behnam Neyshabur, and Harsh Mehta. Convexifying transformers: Improving tion and understanding of transformer networks, 2022a. URL https://arxiiy org/ /bs/
Transvinmers_Imprroinng optimiza-
2211.11055
Tolga Ergen, Arda Sahiner, Batu Ozturkler, John M. Pauly, Morteza Mardani, and Mert Pilanci. Demystifying batch normalization in reLU networks: Equivalent convex optimization models and implicit regularization. In International Conference on Learning Representations, 2022b. URL https: /pppreevieeee....oe net/ forum? i d= 6XGgutacQ08.
Manuel Sernnnnddz-Delgadde 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, 15(90):3133-318,, 2014. URL http: /ttt:://mmma jmir. wttpppapprs//aaeeeooaoo de gadolllllllo 4a html.
Vikul Gupta, Burak Bartan, Tolga Ergen, and Mert Pilanci. Convex neural autoregressive models: Towards tractable, expressive, and theoretically-bee -bcked models for sequential forecasting and generation. In ICASSP 2021 2021 IEEE International Conference on Acousties, Speech and Signal Processing (ICASSP), pp. 3890-3894, 2021. doi: 10. 10.1 10110ASSSS33399 1.9916662..
Koen Helwegen, James Widdicombe, Lukas Geiger, Zechun Liu, Kwang-Ting Cheng, and Roeland Nusselder. Latent weights do not exist: Rethinking binarized neural network optimization. Neural Information Processing Systems, 2019.
Geoffrey Hinton. Neural networks for machine learning. Coursera Video Lectures, 2012.
Itay Hubara, Matthieu Courbariaux. Daniel Soudry, Ran El- Ea-Yi,iv, and Yoshua Bengio. Quantized neural networks: Training neural networks with low precision weights and activations. The Journal of Machine Learning Research, 2017.
Anil K Jain, Jianchang Mao, and K Moidin Mohiuddin. Artificial neural networks: A tutorial. Computer, 29(3):31-44, 1996.
Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. The CIFAR-10 dataset. http::/www.c..
toronto. wtt.ttoo.ddd/rii////e ceaiiiicciaaa.eeee farr.r...e html, 2014.
Yann LeCun. The MNIST database of handwritten digits. http:///yam..eeun.ccom mnist/.
Neal Parikh and Stephen Boyd. Proximal algorithms. Foundations and Trends in optimization, 1(3): 127-239, 2014.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, perf-paeformance deep learning library. Advances in neural information processing systems, 32: 8026-8037, 2019.
11

---

Published as a conference paper at ICLR 2023
Mert Pilanci and Tolga Ergen. Neural networks are regularizers: Exact polynomial-timg convex optimization formulations for two-layer networks. International Conference on Machine Learning, 2020.
Mohammad Rastegari, Vicente Ordonez, Joseph Redmon, and Ali Farhadi. Xnor-net: Imagenet classification using binary convolutional neural networks. European conference on computer vision, pp. 525-542, 2016.
Ralph Tyrell Rockafellar. Convex analysis. Princeton university press, 2015.
Saharon Rosset, Grzegorz Swirszez, Nathan Srebro, and Ji Zhu. LI regularization infinite dimensional feature spaces. In International Conference Computational Learning Theory, pp- 544-558. Springer, 2007.
Arda Sahiner, Morteza Mardani, Batu Ozturkler, Mert Pilanci, and John Pauly. Convex regularization behind neural reconstruction. arXiv preprint (rXx::2012.05169, 2020.
Arda Sahiner, Tolga Ergen, John M. Pauly, and Mert Pilanci. Vector-output relu neural network problems are copositive programs: Convex analysis of two layer networks and polynomial-time algorithms. In International Conference on Learning Representations, 2021. URL https:
//openrevieww.o///////e/ net htte//oormmmiiiieeeeeeeeeeemmeee EGG
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 Learning Representations, 2022a. URL https: /ttpr///e//eeeeee..... net forum? iid 22LLee5ci
Arda Sahiner, Tolga Ergen, Batu Ozturkler, John Pauly, Morteza Mardani, and Mert Pilanci. Un- raveling attention via convex duality: Analysis and interpretations of vision transformers. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 19050-19088. PMLR, 17-23 Jul 2022b. URL https:: http:///ooeeeeeeeeeee/eeee mlr. press v1 62 sahiner22a html.
Richard Stanley et al. An introduction to hyperplane arrangements. Geometric combinatorics, 13: 389-496, 2004.
Robert Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Soccity: Series B (Methodological), (8(1):2677228) 1996.
Roman Vershynin. Memory capacity of neural networks with threshold and relu activations, arXiv preprint XXXi:20001.0693, 2020.
Yifei Wang, Tolga Ergen, and Mert Pilanci. Parallel deep neural networks have zero duality gap. In International Conference on Learning Representations, 2023. URL https: http:::://pperevieee
net/ / forrm?fomm? id= 1id-
Xia Xiao, Zigeng Wang, and Sanguthevar Rajasekaran. Autoprune: Automatic network pruning by regularizing auxiliary parameters. Advances in Neural Information Processing Systems.
Penghang Yin, Jiancheng Lyu, Shuai Zhang, Stanley Osher, Yingyong Qi, and Jack Xin. Under- standing traiihh-throuuge estimator in training activation quantized neural nets. International Conference on Learning Representations, 2019a.
Penghang Yin, Shuai Zhang, Jiancheng Lyu, Stanley Osher, Yingyong Qi, and Jack Xin. Blended coarse gradient descent for full quantization of deep neural networks. Research in the Mathematical Sciences, 6:1-23, 2019b.
12

---

Published as a conference paper at ICLR 2023
Appendix
Table of Contents
A Proofs of the results in the main paper
13
A.1
Lemma 2.1
13
A.2
Proposition 2.4
15
A.3
Theorem 2.2
15
A.4
Theorem 2.3
16
A.5
Lemma 3.1
17
A.6
Theorem 3.2
17
A.7
Lemma 3.3
18
A.8
Lemma 3.5
18
A.9 Corollary 3.4
19
A.10
Corollary 4.1
20
B Additional experiments and details
20
B.1
Experiment Figure
20
B.2 Experiment Table
20
Two-layer experiments Figure 6. 7,
22
B.4 Three-layer experiments with representation matrix Figure 10, 11. and
23
B.5 Standard three-layer experiments Figure and
25
B.6
Standard ten-layer experiments in Figure 14
25
2-layer network
(b) 3-layer network
Figure 3: The convex hull of D A(X corresponding to the 2-layer network (a) and the convex hull of Lisi=m, A (D!¹ corresponding the 3-layer network (b) for the data in Example 3.1. Here, we visualize the convex constraint in Proposition 2.4, which is the implicit representation revealed by convex analysis. We observe that the hidden representation space becomes richer with an additional nonlinear layer (from 2-layer to 3-layer), and the resulting symmetry in the convex hull enables the simpler convex formulation (7).
A PROOFS OF THE RESULTS IN THE MAIN PAPER
A.1
LEMMA 2.1
Proof of Lemma 2.1. We first restate the original training problem below.
m Σ
pnonevx
min W0..s.
(l)x,(X) -y1 1 +
(1) [Iw
+ +57
(wm
(19)
j=1
As already noted in the main paper the loss function is invariant to the of w (1) and may have w!! w(1)) 0 reduce the regularization cost. Therefore, omit the regularization penalty
13

---

Published as a conference paper at ICLR 2023
(a) = 2
(b) n =
Figure Two and three dimensional visualizations of hidden layer representation space of the weight decay regularized threshold networks. Here, we visualize the convex hull in Proposition 2.4, which is the implicit representation space revealed by our analysis.
wj (1)
simplify (19)
8
Phonevx
min W (P)
(X)) - -x12
2
+
10
13)
(2)
2 j=1
We now note that one can rescale the parameters as
(2)
W
aj
without the changing the network's output, i.e.,
m
fx.((X) = Σ 1
1) 100 (2)
Σ x )wm (X)
==1
where orz O. We next note that
8
m
m
a789
m 22
2 3
m
s ||0
22)
Σ
a
j=1
(2)
where the equality holds when aj- objective function in (19) where the regularization term takes a multiplicative form
Thus, we obtain the following reformulation of
m
Ph Pnonevx
min W (9)
(l) y12
88 I (2)
(20)
Next, we apply variable change for the new formulation in (20) as follows
(2)'= := w sz1.
With the variable change above (20) can be equivalently written
P
Pnonevx
w (2 2 Il -y1 + (2)
min
1
(21)
s/ =1
This concludes the proof and yields the following equivalent formulation of (21)
Phonevx=
W (2y 2 2l,f, - -y1l + 3 w (2)' ||,
min
8 1 =1
14

---

Published as a conference paper at ICLR 2023
A.2 PROPOSITION 2.4
Proof of Proposition 2.4. Using the reparameterization for Lasso problems, we rewrite (9) as
min " m 20
[wj w5)
Ed wj -
y.
(22)
5=1
We next introduce slack variable t such that (22) can be rewritten
min min s.t. 200 3j ; 20
- -,) w y Σ (wt + ( =t.
(23)
2=1
We now rescale wt. wj with 1/t obtain the following equivalent of (23)
min min s.t. 200 m ; 20
E (wj w= =y/, E (w) + =w)== =1
(24)
j=1
1=1
The problem in (24) implies that
P
P
Bwf+ w 2 Os.t.
E + w - [ -5)
+ tConv(=d, Vj E [P], y/t wy) -
.=1
where Conv denotes the convex hull operation. Therefore, (9) can be equivalenly formulated as minl s.t. y (Conv Vj [P]}.
A.3 THEOREM 2.2
Proof of Theorem 2.2. We first remark that the activations can only be either zero or one, i.e.,
Jo, [Xw (1) 10, 13", since |sy| = 1, Vjj E [m]. Therefore, based on Lemma 2.1, we reformulated
(4) as
P Dhonevx
min E (d de)
[ d:.. y12 + 3 B|[w]|
(25)
where we denote the elements of the set XX) by di..... dp E 13 and P is the number of hyperplane arrangements. The above problem similar Lasso (Tibshirani, 1996), although is non-convex due to the discrete variables d,, ...., di... These m hyperplane arrangement patterns are discrete optimization variables along with the coefficient vector w. In fact, the above problem is equivalent to constraie Lasso problem.
We have
Phonevx-
min PER" d Ci...dd Am (X( we 2 11-113 + w/1
r= d. do W-
|111/ + 1 + z 2 +r+
T' d,w,
min
max
FER" d (H(X) WER" ZER"
1=1
min M. ZER rER" wERm
min
max
x y
+
|r/3 zT + Σ
Blws| - w.z T d
2
1
min
max
2 1y113
||z y11
d....dd,, (H(X EH(X)
ZER"
2
1xT
ISA [immm]
2 1ly11
2 zz y1
max
ZER maNac NOX IZT S
|1y11
2 112 = D
max
RER"
15

---

Published as a conference paper at ICLR 2023
where inequality (i) holds by weak duality, inequality (ii) follows from augmenting the set of constraints Iz dz', I 3 to hold for any sign pattern H(X), and inequality (iii) follows from enumerating all possible sign patterns, i.c., H(X) {di, d2, .2........ .p..
We now prove that strong duality in fact holds, i.c., P D2 We first form the Lagrangian of the dual problem x
1
D2n
ZE wi, 2 -lyy
max min
12
y12
+
[w - z²',)) + w + d.).)
2
P
(
min max
2
1ly
2 1z yyl +
Σ
(w:(B - z d.) + w/ + +zd).)
00 20 202ER"
==1
P Σ i=1
di(ws -w/ -- y 2
1
min w4,"r 20
Σ
3 (w: + w
2
1=1
1
min WER
Dw
v112 + 31 B/|wl]| = P2
(26)
2
where, in equality (i) follows from the fact that DE is a convex optimization problem satisfying Slater's conditions that strong duality holds (Boyd & Vandenberghe, 2004), i.e., D = Pavx and the matrix D E {0, 1]
P is defined as
D:= D:=Id,,d, ddi,d...., dp].
Now, based on the strong duality results in Ergen & Pilanci (2020); Pilanci & Ergen (2020), there exist a threshold for the number of neurons, i.c., denoted as m², such that if 2 m then strong duality holds for the original non-convex training problem (25), i.e., Pronevx = D2vx Payx. Thus, (26) exactly equivalent to the original non-convex training problem (3).
A.4 THEOREM 2.3
Proof of Theorem 2.3. Following the proof of Theorem 2.2, we first note that strong duality holds
for the problem in (25), i.e., Phonevx Dzyx
Under the assumption that H((X) {0, 13" the dual constraint maxdeH(x)) |zT d| S 8 is equivalent to {max z' d < 3} U {maxx' [j -z" d' S 33. Forming the Lagrangian based on this reformulation of the dual constraint, we have
D2 max min
7
1
+ t(B 1-11
max z'd) f(B
max xJ d') d'E(0.1
xER 1,20
de|o,1|
max xER"
min 1.220 d
|yy1
2 ly
2112 + 2T(TtTt (t'd' (d) + 3(' + t)
|yy1 1 211 + x z' d) + 3(1 +t)
max zER"
min 1.220
dE ""004",d'''l"" "'
min 2 de a d'
max zER"
2 2 Ily 21 T(d' d) + 3(' +1)
|1yl
min 20
d' d y1l + +(+++))
dE d "'
where, in equality (i), we used the change of variables d = td and d' = t'd', and, in equality (ii), we used the fact that the objective function I b 2 + zz (d' - d) + 3(' +t) is strongly concave in z and convex in (d, d', t, t') and the constraints are linear, so that strong duality holds and can switch the order of minimization and maximization.
zT(d'
16

---

Published as a conference paper at ICLR 2023
Given feasible point (d, (d, ,t, t'), i.e. d [0,t]" and d' E 10, we set ò = d' - d. Note that [|(6)+1lcc I (I(dd)+ ll = ||d'llcc I t'. Similarly, (((-))+le lo - This implies that
1
min f,4'20
2
Ild' - yll + 8(1 + ())
min- |8 y y1 + 3(1(()++ll + (1(--)+1loo) = P22
SER 2
Conversely, given 8 E IR", we set d = (6) 1 == |||| d' = +)+ and === =Idd' It holds that (d, d', 1,4") is feasible with same objective value, and consequently, the above inequality is an equality, i.e,, D2 = P.22.
Optimal threshold network construction: We now show how construct an optimal threshold net- work given an optimal solution to the convex problem (7), Let 6 E I be an optimal solution. Set d = (6)+ and d' = (-0)+ We have [0, [|d]] so]" and d' [0, ||d'] so]" It is easy to show that can transform such that, for each index i [n], either the i-th coordinate of d is active or the i-th co- ordinate of d' active. Therefore, by Caratheodory's 's theorem, there exist R2. n-
such that n-
n4 I n, and d1,...,,,, dn++1 E {0, 1 and n...., 7n 2 0 such that - % = and d =
||d]| x0 Σi= %d; and, d , d {0, 1}"h and - % 2 0 such that Σ Li=1 +1
74
and d' |d'll 0c Ei=1 +1 /dd, with n. n4 n. Then,
pick w (1)
w (1)
#1+
w w nn
(2)
+11 51: $1...... ................................ 844+1 +1 such that 1 (Xw (1) 0} d, w ||]] 7/2 and s;
and,
w (1)
#2 ny +2
w n4 +2
(2)
w
nt +m +m_ +2 Sny +2, Sn4 4n +2 such that 1(xw;
(2)
(1) N
0} = d' +1)+++1) 03 = |d h- +1) and 8: = 1. Note that, given E IR, finding
the corresponding d da +1 7 14 and .'...., d da t1: M.... 14411 takes time
O(n + ++) (n).
A.5 LEMMA 3.1
Proof of Lemma 3.1. We first restate the standard weight decay regularized training problem below
3 mI-1
min #EB
(X) v12
O + (s((11)) 12).
(27)
Then, we remark that the loss function in (27), i.e., 1 II (X) y1l2 is invariant the norms of 1-
hidden layer weights {[W() (27) can be rewritten as
| Ik=1" "Ern" and amplitude parameters (15) (1) 1_2 ]k= Therefore,
mL-1
min # 2 (X) - x12
Σ
(wo + (s (1- 11)))
(28)
k=1
Then, we can directly upply the scaling in the proof of Lemma 2.1 to obtain the claimed 4o-mrrm regularized optimization problem.
A.6 THEOREM 3.2
Proof of Theorem 3.2. We first remark that the last hidden layer activations can only be either zero
or one, i.c., x ((--1) {0, 1p=xme-1, since |sk (1-1)) 1, vk [mz-1]. Therefore, based on
Lemma 3.1, we reformulated (12) as
PHonevx
min d, (X)
1 Ill 2
d d . w y| + + ww/l
(29)
w
As in (25), the above problem is similar to Lasso, although it is non-convex due to the discrete variables d ..., dim.... These m hyperplane arrangement patterns are discrete optimization variables along with the coefficient vector w.
We now note that (29) has following dual problem
1 lly 2 - -y11 + 2
Dry
Dovx
max
(30)
maxae R2 (X)
17

---

Published as a conference paper at ICLR 2023
Since the above dual form is the same with the dual problem of two-layer networks, i.e., D D2 we directly follow the proof Theorem 2.2 to obtain the following bidual formulation.
D P
min WER SER22-1 2
D(L-1)
>11 s||W]
[dl, d, . dp .l- where D(L-1) _
Hence, based on the strong duality results in Ergen & Pilanci (2020); Pilanci & Ergen (2020); Ergen & Pilanci (2021c), there exist threshold for the number of neurons, i... denoted such that mL-1 2 m² then strong duality holds for the original non-convex training problem (25), i.c., Pronevx D P.x
A.7 LEMMA 3.3
Proof of Lemma 3.3. Based on the construction in (Bartlett al., 2019), a deep network with layers and W parameters, where W = E m in our notation, can shatter dataset of the size C₁ W. L where C₁ is constant. Based on this complexity results, if we choose my m = C.nCC.ll E [L.] the number of samples that can be shattered by an L--laer threshold
network is
# of data samples that be shattered C1 W.W... log(W)
Cim² L log(mm
C²n
C2CCn
L
n
= n
> n
LC
provided that n > L. which is usually holds in practice and we choose the constant such that C = 1/Cf. Therefore, make the architecture deeper, can in fact improve the assumption
m 2 n + assumption the two-layer networks case by benefiting from the depth.
A.8 LEMMA 3.5
Proof of Proposition 3.5. Let start with the 2 case for which hyperplane arrangement can described as detailed (5)
H₂ [1(Xw(") (1) 2 03 00 θ}
= -((X)
:di....., dp, 10,
Now, in order construct (X) (with mL-1 1 drop the index k), need choose mi arrangements from H2 (X) and then consider all hyperplane arrangements for each of these choices. Particularly, since H2 X) Pi, where
c(n (c(n-1))
r 1) = O(n")
P <
S
2r
k
A
from (8), we have (.9) choices and each of them yields a different activation matrix denoted as x( (1) E maxm: Based on the upperbound (8), each x can generate Onn")) patterns.
Therefore, overall, the set of possible arrangement in the second layer is follows
(X) U (1 w 2 20::0 0 xx
18

---

Published as a conference paper at ICLR 2023
which implies that
Pi m4
[X) P2 x
O(1 m1) O(
This analysis can be recursively extended to the 1 layer where the hyperplane arrangement set and the corresponding cardinality values can be computed as follows
P--2)
Hi(X) = U 1=1
21X
20):
X -==(---)
(P-2
[x)()) = P1- S
0(n ~ Onn m.)
m1-2
A.9 COROLLARY 3.4
Proof of Corollary 3.4. We first remark that the last hidden layer activations can only be either (L-1) E {0, 1juxmz=i, since 1s (1-11) 1, Ak E [mL-1]. Therefore, based on Lemma 3.1, reformulated (12) as
zero or one, i.e., x k
di d dime-1) - x|1 + B B||l
min di EH2 (x)
(31)
As in (25), the above problem is similar to Lasso, although it is non-convex due to the discrete variables d dim....' These m,-1 hyperplane arrangement patterns are discrete optimization variables along with the coefficient vector w.
We now note that (31) has following dual problem
1 1| - 11/22 + 11y11
max M 1 SB
Since (x) = (0, 13 by Lemma 3.3, all the steps in the proof of Theorem 2.3 directly follow.
Optimal deep threshold network construction: For the last two layers' weights, we exactly follow the weight construction procedure in the Proof of Theorem 2.3 as detailed below.
Let E I be an optimal solution. Set = (5)+ and d' = ( 5)+ We have d E [0, [|d]]]<]] and transform ö such that, for each index E [n), either
d' [0, [[d' It is easy to show that the i-th coordinate of d is active or the i-th coordinate of d' is active. Therefore, by Caratheodory's theorem, there exist n4, n 2 such that n_ + n. S n, and di,..., dn,+1 d..
E 10, and +1 7, and, d'....,
n...., Tx++1 2 0 such that D 7/ = 1 and d = ||d]|o Σn i=l
e
(0. 1)m and 7/....,7h__.. 2 such that Σn= +1 7/4 = and d' = ||d'] Σn ddd with
n_ n4 I n. Then, we can pick w (L-1) ..... w (L-1)
(4) (L-1)
(L-1)
#1+ wi ..... w #1
..... n++1 +1 such
that 1 ((X(2-2) (L-1) 0) = d, w! (4-1) || and = -1, and, w n +2: ...... W t4
(L-1)
will w +2 W -u- +2 nn (1-11) ................................ ,
(1.
(1)
(I-1) +2 such that 1(X (L-2) w (I- (1.11)
> 0} d' d (m_ 1)'
a; = ld 70 +1) and 8; 1. Note that, given E R", finding the corresponding
di..... d1,+1, ....., 7--1 and d/ ....... t1. 2n takes time O(n+ + + (n)).
Then, the rest of the layer weights can be reconstructed using the construction procedure detailed in (Bartlett et al., 2019).
19

---

Published as a conference paper at ICLR 2023
A.10 COROLLARY 4.1
Proof of Corollary 4.1. We first apply the scaling in Lemma 3.1 and then follow the same steps in the proof of Theorem 2.3 to get the following dual problem
MXX) ( (z),
(32)
where L the Fenchel conjugate of L and defined as
L (z) = max v² L(v.y).
Therefore, we obtain a generic version of the dual problem in (30), where we can arbitrarily choose the network's depth and the convex loss function. Then the rest of the proof directly follows from Theorem 3.2 and Corollary 3.4.
B ADDITIONAL EXPERIMENTS AND DETAILS
In this section, we present additional numerical experiments and further experimental details that are not presented in the main paper due the page limit.
We first note that all of the experiments in the paper are run on single laptop with Intel(R) Core(TM) 17-7700HQ CPU and 16GB of RAM.
B.1 EXPERIMENT IN FIGURE 5
Objective value
Nonconvex-lnit#)
109
Nonconvex-Initee
Nonconvex
Nonconvex-
Nonconvex Init#
10-1-
Convex (Ours)
10
2000
4000
6000
8000
10000
Iteration
Figure Comparison of our convex training method in (6) with standard non-convex training heuristic for threshold networks, known as Shrought-Through Estimator (STE) (Bengio et al., 2013). For the non-convex heuristic, we repeat the training process using 5 independent initializations, however, all trials fail to converge to the global minimum obtained by our convex optimal method, and lack stability. We provide experimental details Appendix
For the experiment in Figure 5, we consider simple one dimensional experiment, where the data matrix is [-2, 0, 2)" Using this data matrix, we generate the corresponding labels y by simply forward propagating the data through randomly initialized two-layer threshold networks with m = 2 neurons as described in (2). We then run our convex training method in (6) and the non-convex training heuristic STE (Bengio et al., 2013)
the objective with the regularization coefficient 3 = 1e 2. For fair comparison, we used P1 = 24 for the convex method and mi 24 for STE. We also tune the learning rate of STE by performing a grid search on the (5e - 1, le 1, 5e 2, le 2, 5e 3, le 3}. As illustrated in Figure 5, the non-convex training heuristic STE fails achieve the global minimum obtained by our convex training algorithm for different initialization trials.
B.2 EXPERIMENT IN TABLE
Here, we provide a test performance comparison on on CIFAR-10 (Krizhevsky et al., 2014), MNIST (LeCun), and the datasets taken from UCI Machine Learning Repository (Dua & Graff, 2017), where
20

---

Published as a conference paper at ICLR 2023
Table Dataset sizes for the experiments in Table 2.
Dataset
d
CIFAR-10
10000
3072
MNIST
12663
784
bank
4521
16
chess-krvkp
3196
36
mammographic
961
5
oocytes-4d
1022
41
oocytes-2f
912
25
ozone
2536
72
pima
768
8
spambase
4601
57
statlog-german
1000
24
tic-tac-toe
958
9
titanic
2201
3
we follow the preprocesing in Fernández-Delgaddo et al. (2014) such that 750 < < 5000 (see Table for the exact dataset sizes). We particularly consider conventional binary classification framework with two-layer networks and performed simulations over multiple seeds and compare the mean/std of the test accuracies of non-convex heuristics trained with SGDnamely Nonconvex- STE (Bengio et al., 2013). Nonconvex-ReLA, (Yin et al., 2019a), Nonconvex-LRell (Xiao et al.) (Cai et al., 2017), with our convex program in (6), i.e., Convex- For the non-convex training, we use the SGD optimizer. We also use the 80% 20% splitting ratio for the training and test sets of the UCI datasets. We tune the regularization coefficient and the learning rate for the non-convex program by performing grid search the sets Slist = {le - 6, le 3, le - 2, le 1, 0.5, 1,5] and Plist {le 3, 5e 3, 2, le 1}. respectively. In all experiments, PyTorch's (Paszke et al., 2019) scheduler ReduceLLOnn Patenu.. Moreover, we choose the number of neurons, number of epochs (ne), batch size (bs) m 1000, bs 5000, bs n. respectively. Our convex approach achieves highest test accuracy for precisely 9 of 13 datasets whereas the best non-convex heuristic achieves the highest test accuracy only for 4 datasets. This experiment verifies that our convex training approach not only globally optimize the training objective but also usually generalizes well on the test data. In addition, our convex training approach shown be significantly more time efficient than standard non-convex training.
and Nonconvex-CRele
also decayed the selected learning rate systematically using
Objective Value
30..
Objective Value
Objective Value
Triif3
10"7-
Triil4
10-1-
10"1.
Triiies
Conwax-Lasse (Ours)
30
10-2
10
7
0.0
0.
1.0
15
2.0
0.
05
1.0
15
2.0
0.0
05
1.0
155
200
Time(s)
Time(s)
Time(s)
(a) (vs, d) (20, 100)
(b) (n, (50, 50)
(c) (n, d) (100, 200
Figure 6: Training performance comparison of our convex program for two-layer networks in (6) with four standard non-convex training heuristics (STE and its variants in Section 5). To generate the dataset, we randomly initialize a two-layer network and then sample a random i.i.d. Gaussian data matrix X E Rexd Then, we set the labels as = sgn(tand (W)))( (2)) where sgn and tanh the sign and hyperbolic tangent functions. We specifically choose the regularization coefficient 3 le - 3 and run the training algorithms with m = 1000 neurons for different (n, d) combinations. For each non-convex method, we repeat the training with 5 different initialization and then plot the best performing non-convex method for each initialization trial. In each case, our convex training algorithm achieves significantly lower objective than all the non-conver heuristics. We also indicate the time taken to solve the convex program with a marker.
21

---

Published as a conference paper at ICLR 2023
Objective Value
Notconeex-AoLJ
Nerconeex STE
Training Acc
1.00
Noncomesx-Lcau
Test Acc
Conveic- Lunso [Ours)
0050
0.75
10-1
0.50
10
00
0.5
1.0
15 Time(s)
2.0
2.5
2.0
00
0.5
10
1.5
2.0
25
0.0
0.5
10
1.
24
25
30
Time(s)
Time(s)
(b)
Figure 7: In this figure, we compare the classification performance of the simulation in Figure 6c for a single initialization trial, where n = 100 and 20. This experiment shows that our convex training approach not only provides the optimal training performance but also generalizes on the test data as demonstrated (c).
Objective Value
10P
Kanconees
Konconees ReLli
konconves LeeLU
Training Acc
1.00-
Test Acc
0.625
0.050
Noncoreex CRCUU
Conves Lusso (Ours)
0050-
0.600
0.65
0.575
30
0.30
0.550
0.525
10'7
0.500
0.0
05
1.0
15
2.0
2.5
3.0
0.0
0.5
1.0
1.5
2.0
25
3.0
0.0
1.0
15
20
25
20
Time(s)
Time(s)
Time(s)
(a)
(c)
Figure 8: The setup for these figures is completely the same with Figure 7 except that we consider the (n, d) = (50, 50) case Figure 6b. Unlike Figure 7, here even though our convex training approach provides the optimal training, the non-convex heuristic methods that are stuck at local minimum yield better test accuracy. This due the fact that we have less data samples with higher dimensionality compared to Figure
B.3 TWO-LAYER EXPERIMENTS IN FIGURE 6, 7, 8, AND
Here, compare two-layer threshold network training performance of convex program (6), which we call Convex-Lasso, with standard non-convex training heuristics, namely Nonconvex-STE (Bengio et al., 2013), Nonconvex-ReL.. (Yin et al., 2019a), Nonconvex-LReLL (Xiao al.) and Nonconvex-CReL.U (Cai et al., 2017). For the non-convex heuristics, we train standard two- layer threshold network with the SGD optimizer. to be 0.01 and they are decayed systematically using PyTorch's 's (Paszke et al., 2019) scheduler ReduceLROnPPI w.t.onllna..........aa To generate a dataset, we first sample an i.i.d. Gaussian data matrix and then obtain the corresponding labels as y (gn(tann(XW(!) (w-))) where sgn and tanh are the sign and hyperbolic tangent functions, respectively. Here, we denote the the ground truth parameters as ((1) E d and (2) E IR"" where m 20 is the number of neurons in the ground truth model. Notice that we use tanh and sign in the ground truth model have balanced label distribution
all experiments, learning rates are initialized
1+ 111.-111 _ We also note that for all the experiments, we choose the regularization coefficient as 3 = le
We now emphasize that to have fair comparison with the non-convex heuristics, we first randomly sample small subset hyperplane arrangements and then solve (6) with this fixed small subset. randomly sample
Specifically, instead of enumerating all possible arrangements {d,) subset (d,, 1 to have fair comparison with the non-convex neural network training with m hidden neurons. So, Convex-Lasso is approximate way to solve the convex program (6) yet still performs extremely well in our experiments. We also note that the other convex approaches Convex-PI and Convex-SVM exactly solve the proposed convex programs.
In Figure 6, we compare training performances. We particularly solve the convex optimization problem (6) once. However, for the non-convex training heuristics, try five different initializations.
22

---

Published as a conference paper at ICLR 2023
Objective Value
Noncarvex STE
koncanvex BGLJ
Training Acc
1.00-
0.50
Noncamvee LR:L0
Test AcC
0.56
10"
Convess Lasso (Ours)
10500
0.54
10
0.50
10-2
00
d.
100
15
2.0
25
3.0
0.0
05
1.
1.5 Time(s)
2.0
25
30
0.0
5.
1.
15 Time(s)
2.0
25
50
Time(s)
(a)
(c)
Figure 9: The setup for these figures is completely the same with Figure 7 except that consider the (n,,) = (20, 100) case Figure 6a. in Figure 8, even though the non-convex heuristic training methods fail to globally optimize the objective, they yield higher test accuracies than the convex program due to the low data regime (n S d).
We then select the trial with the lowest objective value to plot. In the figure, we plot the objective value defined in (3). As it be seen from the figures, Convex-Lasso achieves much lower objective value than the non-convex heuristics in three different regimes, i.e., overparameterized (n < d), underparameterrized (n d) and moderately parameterized ((n = d)). This mainly because the non-convex and heuristic nature of the standard optimizers.
Moreover, illustrate training and test accuracies of these training algorithms in Figure and 9 for different (n, d) combinations. To generate the test data with 3000, samples we use the same ground truth model defined above. Here we observe that in some cases even though Convex-Lasos provides better training performance, it might yield worse test accuracies than the non-convex heuristic especially in the low data regime (n S d). Therefore, understanding the generalization performance and optimal weight reconstruction (discussed in Section 2.4) remains to be open problem.
Objective Value
Objective Value
10
Objective Value
10-1
10
Trials
(Oura)
(Ours)
10-4-
20"2
:0
0.0
0.5
1.0
15
0.5
200
0.0
1.0
155
25
Time(s)
Time(s)
Time(s)
(a)
(n. d, m2)
(b) (n, d, mi m2)
(c)
(n. d, m2)
(20, 100, 1000, 20)
(50, 50, 1000,50) 50)
(100, 20, 1000, 100)
Figure 10: Training comparison of our convex program in (7) with three-layer threshold networks trained with the non-convex heuristies. Here, we directly follow the setup in Figure except the following differences. This time we randomly initialize three-layer network and then sample i.i.d. Gaussian data matrix. We then set the labels as sgn(tanh(tanhi (X ((() ( (2)))/(() (3)). To have our convex formulation, we require H(X)) to be complete. Thus, we first use random representation matrix H E RdxM where M 1000, and then apply the transformation X (XH). We also apply this transformation to the non-convex methods if we train two-layer networks the modified data matrix X. We also indicate the time taken to solve the convex programs with markers. We again observe that our convex training approach achieves lower objective value than all the non-convex heuristic training methods in all initialization trials.
B.4 TIREE-LAYER EXPERIMENTS WITH REPRESENTATION MATRIX FIGURE 10, 11, 12, AND 13
We also compare our alternative convex formulation (7) with non-convex approaches for three-layer network training. To do first generate dataset via the following ground truth model
23

---

Published as a conference paper at ICLR 2023
Objective Value
10
0.22
Matsewe-- PAll
Training Acc
0.50
0.55
*
13F-
Conless (Dka)))
0.50
Test ACC
0.76
0.7
0.55
0.70
10"
0.75
6.0
0.5
10 Time(s)
1.
0.5
155
20
00
0.5
1.0
15
20
Time(s)
Time(s)
(a)
(c)
Figure 11: In this figure, compare the classification performance of the simulation in Figure 10c for a single initialization trial, where (n, d) = (100, 20). This experiment shows that our convex training approach not only provides the optimal training performance but also generalizes on the test data as demonstrated (c).
Objective Value
10a
0.70
Watreure Beild
Training Acc
0.95
Test Acc
13P-
Conwortf di (Dums
0.60
0.85
10-
0.75
0.50
96
96
0.0
0.5
100
15
0.0
0.5
1.0
15
0.0
05
1.0
1.5
Time(s)
Time(s)
Time(s)
(a)
(b)
(c)
Figure 12: The setup for these figures is completely the same with Figure 11 except that we consider the (n, d) (50,50) case in Figure 10b. This experiment shows that when have all possible hyperplane arrangements, our convex training approach generalizes better even in the low data regime (n S d).
sgn(tanh(tanh(XX (X)()) (W))) where W(1) E RRxmm ( RRm and (3) E TR" and we choose m m3 20 for all the experiments. As is described in Theorem 2.3, require H(X) to be complete this case. To ensure that, we transform the data matrix X using a random representation matrix. In particular, we first generate random representation matrix H Rd and then multiply with the data matrix followed by a threshold function. Therefore, effectively, we obtain a new data matrix X = o (XH). By choosing M large enough, which M 1000 in our experiments, we are able to enforce X to be full rank and thus the set of hyperplane arrangements H(X) is complete as assumed Theorem 2.3. We also apply the same steps for the non-convex training, i.e., train the networks if we perform two-layer network training the data matrix X. Notice that we also provide standard three-layer network training comparison, where all of three layers are trainable, in Section B.5, More importantly, after solving the convex problem (7), we need to construct a neural network that gives the same objective value. As discussed in Section 2.4, there are numerous ways to reconstruct the non-convex network weights and we particularly use Convex-PI and Convex-SVM as detailed in Section 5, which seem to have good generalization performance. We also note that these approaches are exact in the sense that they globally optimize the objective in B.3. Additionally, we have n neurons our reconstructed neural network to have fair comparison with the non-convex training with hidden neurons.
In Figure 10, we compare objective values and observe that Convex-Pi PI and Convex-SVM. which solve the convex problem 7, obtain the globally optimal objective value whereas all trials of the non-convex training heuristics are stuck at a local minimum. Figure 11, 12, and 13 show that our convex training approaches also yield better test performance in all cases unlike the two-layer training in Section B.3. Again, for the testing phase we generate 3000 samples via the ground truth model defined above.
24

---

Published as a conference paper at ICLR 2023
Objective Value
10
1.00
0.50
Netsewe-- Pally
ining Acc
0.55
0.d1
0.56
13F-
Conless (Dua)))
Conteso
00.85
0.54
0.00
0.52
0.75
0.50
10"*
0.70
0.40
2
0.65
0.66
6.
0.5
1.0
15
0.0
16 Time(s)
6.0
0.5
10
15
Time(s)
Time(s)
(a)
(c)
Figure 13: The setup for these figures is completely the same with Figure 11 except that we consider the (n, d)- = (20, 100) case in Figure 10a. This experiment also confirms better generalization of our convex training approach as in Figure 11 and 12.
B.5 STANDARD THREE--AYER EXPERIMENTS IN FIGURE AND 2
Here, we compare our convex program in (7) with 3-layer networks trained with non-convex heuristics. Similar to the case in Section B.4 we generate dataset via the ground truth model = (tanh(X
)w()), where X E Rx w() E Rdxmi, W(2) R"ix" and w E 2 and we choose m = mi = 20 for all the experiments.
Rdx where M 1000, and then apply the transformation X o (XHH) for the convex methods. We perform standard training procedure for three-layer non-convex networks, i.c., we train fully three-layer network without any sort of representation matrix. To have fair comparison, we choose m. M and m2 = n for both non-convex and convex settings.
In contrast to Section B.4, we use a representation matrix
In Figure 1, we compare the objective values and observe that our convex training approaches achieve global optimum in all cases unlike the non-convex training heuristics. We also provide the test and training accuracies for three-layer networks trained with different (n, d) pairs in Figure 2. all cases convex approaches outperform the non-convex heuristics in terms of test accuracy.
Objective Value
10P
1.00
0.20
raining Acc
0.70
0.55
0.76
CReUl
1.54
(Ound)
0.74
0.25
GSt
0.72
0.70
10'
0.75
0.60
36
0.66
10
24
10
15
Time(s)
Time(s)
Time(s)
(a)
(b)
(c)
Figure 14: Performance comparison of our convex training approaches trained via (7) and non-convex training heuristics for a 10-layer threshold network training problem. Here, the setup in Figure 1. As in the previous experiment, our convex training approaches yields outperforms the non-convex heuristics both training and test metrics.
B.6 STANDARD TEN-LAYER EXPERIMENTS IN FIGURE 14
In order to verify the effectiveness the proposed convex formulations in training deeper networks, we consider a threshold network training problem for 10-layer network, i.e., (10) with L = 10. We directly follow the same setup with Section B.5 for (n, d, B) = (100, 20, Ie - 3). Since in this case the network is significantly deeper than the previous cases, all of the non-convex training heuristics failed to the training data, i.e., they couldn't achieve 100% training accuracy. Therefore, for the non-convex training, also include Batch Normalization in between hidden layers to stabilize and improve the training performance. Figure 14, we present the results for this experiment. Here, we observe that convex training approaches provide globally optimal training performance and
25

---

Published as a conference paper at ICLR 2023
yield higher test accuracies than all of the non-convex heuristics that are further supported by Batch Normalization.
26


Reviews:
[{"review_id": "ewiwAFk2wB", "reviewer": "Reviewer_VvcU", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "Paper develops a convex program for **memorizing** data with a two-layer neural network that extends to higher layers.  **Memorization** in neural nets is a theoretical topic that studies required conditions on a number of neurons to perfectly fit a finite number of samples. What makes this result apart from existing results in the literature is the use of the threshold activation function. The authors motivate the choice of threshold activation by (i) the compression of outputs and (ii) the biological origins of threshold activations. Despite compression and biological simulations, a network with threshold activation is difficult to optimize. There are rare algorithms to optimize networks with such activations. This paper proposes a convex program for memorization with the following guarantees: \n- #neurons>#samples: the algorithm finds the weights in poly-time \n- #neurons<#samples: the algorithm suffers from the complexity $O(\\text{samples}^{\\text{input-rank}})$", "summary_of_the_review": "The paper presents interesting theoretical results. Yet, I believe that experimental results may lead to over-claiming and need further clarifications, and also it misses a large body of related literature. \n\n**Post Rebuttal**\nI thank the authors for their detailed response. I updated my score after reading the response. ", "strength_and_weaknesses": "**Strengths**\n- The main strength of the paper is motivating learning threshold neural nets very well. Learning such networks is an important topic. In my opinion, the neural nets community will welcome novel algorithms and optimization techniques for neural nets with threshold activations.\n- Extending memorization to deep neural nets is an interesting contribution of this paper. \n- Experiments on generative and real data are a plus for this theoretical work. \n\n**Weakness** \n- *Memorization.* The paper stresses the proposed algorithm can lead to a practical algorithm. But I am not sure about this. The memorization setting (#samples<#neurons) is not standard in machine learning. \n- *Presentation.* The intro and abstract may lead to a misunderstanding that threshold activation leads to convex optimization. While the memorization setting (#neurons>#samples) enables us to cast training to a convex program. I recommend explicitly declaring that the overparameterization #neurons>#samples are the key assumption enabling us to learn with a convex program. \n- *Literature review* The literature on memorization is missing in this paper. The paper neglects closely related references, including [1-5] and many more references on the same topic. For example, it is very important to drive the connection between general position assumption on inputs [2] and the completeness of the arrangements in this paper.  \n- *Experiments.* I could not find the number of neurons, batch size, stepsize, number of epochs, and more details on experimental settings in Table 2. \n\n**References**\n\n\n1.  Rosset, Saharon, et al. \"L1 regularization in infinite dimensional feature spaces.\" International Conference on Computational Learning Theory. Springer, Berlin, Heidelberg, 2007.\n2. Bubeck, Sebastien, et al. \"Network size and weights size for memorization with two-layers neural networks.\" arXiv preprint arXiv:2006.02855 (2020).\n3. Zhang, Chiyuan, et al. \"Understanding deep learning (still) requires rethinking generalization.\" Communications of the ACM 64.3 (2021): 107-115.\n4. Pilanci, Mert, and Tolga Ergen. \"Neural networks are convex regularizers: Exact polynomial-time convex optimization formulations for two-layer networks.\" International Conference on Machine Learning. PMLR, 2020.\n5. de Dios, Jaume, and Joan Bruna. \"On sparsity in overparametrised shallow relu networks.\" arXiv preprint arXiv:2006.10225 (2020).", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "H7iGChTR8kl", "reviewer": "Reviewer_n5sD", "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": "1. This paper proved that the training of deep threshold networks with weight decay can be formulated as a convex optimization problem. The size of the convex optimization problem depends on the total number of hyperplane arrangements, which can be exponentially large in the number of samples in the worst case. \n2. For two-layer threshold networks, this paper proved that the associated convex optimization problem can be solved in polynomial time when (1) the data matrix has constant rank or (2) the hyperplane arrangements of the data matrix is complete. \n3. For deep threshold networks, this paper proved that the associated convex optimization problem can be solved in polynomial time when (1) the data matrix rank and the network widths are all constant or (2) one hidden layer has a width of at least the number of samples.\n4. In the experiments, this paper showed that training the threshold networks using the proposed convex approaches archived better performance than the non-convex counterparts trained by back-propagation. ", "summary_of_the_review": "This paper proposed convex approaches to optimize threshold neural networks, which is particularly appealing due to the zero gradient issues in back-propagation for such networks. However, my major concern is that such convex approach can be exponentially slow in general. The experiments are also restricted to very simple networks, which further reinforces my suspicion that the proposed convex approaches may not be practical for modern deep neural networks. ", "strength_and_weaknesses": "Strengths:\nThis paper formulated the training of weight decay regularized threshold networks as convex optimization problems. It then proposed convex approaches to optimize such neural networks, which seems appealing especially when the back-propagation fails because of the zero gradient issues. It also provides a relatively complete picture of the computational complexity of such convex approaches for different-depth networks under different data assumptions. \n\nWeaknesses:\n1. This paper only proved the polynomial-time complexity of the convex optimization problem in some special cases. In many other cases, solving this convex optimization problem can still take exponential time, which then makes the algorithm impractical. For example, when none of the layers has a width of at least $n$, the running time is exponential in the product of layer widths. This can be extremely slow since the width of each layer can easily be larger than $100$ in modern neural networks.\n2. The experiments are also restricted to two or three-layer neural networks, which further reinforces my suspicion that the proposed convex approaches may not be practical for modern deep neural networks. \n\nSome minor questions:\n1. In the two-layer case when the arrangements are complete, why is the reconstruction of parameters only taking O(n)? Shouldn't it also depend on $m$ and $d$ because $W^{(1)}$ has dimension $d\\times m$?\n2. What's the reconstruction time when the arrangements are incomplete? ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "CBYIRNi1Ht", "reviewer": "Reviewer_tBqd", "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 formulates the problem of training neural networks with threshold activation functions to a convex optimization problem. As a result, global minima can be obtained with standard convex optimizers. ", "summary_of_the_review": "Overall, I find this paper is solid and contains interesting theoretical results. But I am concerned with its extensibility and therefore the impact, as written in Weaknesses.", "strength_and_weaknesses": "Strengths:\n1. The paper is well-written and easy to follow. The notations are clear.\n2. Equivalenting neural network training to convex optimization under mild conditions is theoretically interesting.\n3. The theoretical results seem rigorous, though I didn't check the proofs thoroughly.\n4. Experiment were conducted on various datasets and the results in terms of testing accuracy and training time are encouraging.\n5. The code is attached for reproducibility.\n\nWeaknesses:\n1. It seems to me that the weight decay terms in the objective function (3) are needed to derive the equivalent formulation (4). This is somewhat artificial as deep learning practitioners nowadays barely employ weight decay in training. Can the authors shed some lights on the equivalent derivation without weight decay?\n2. The overall approach does not seem scale well with the depth of a neural network, unless some strong conditions are imposed. As in Theorem 3.2, the convex formulation essentially flattens the deep nested structure of the network. Therefore, it can result in exponentially many parameters to optimize, as indicated in Table 1. Please note that the point of doing neural networks is employing the deep nested structure, so as not to have exponentially many parameters, in approximating complicated functions.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster