Convex Formulations for Training Two-Layer ReLU Neural Networks
Authors: Karthik Prakhya
Tolga Birdal
Alp Yurtsever
Venue: ICLR 2025 Poster (2025)
Keywords: copositive programming
semidefinite programming
neural networks
Primary area: optimization
TL;DR: We provide copositive and semidefinite formulations for training (in)finite width two-layer ReLU neural networks.

Abstract: Solving non-convex, NP-hard optimization problems is crucial for training machine learning models, including neural networks. However, non-convexity often leads to black-box machine learning models with unclear inner workings. While convex formulations have been used for verifying neural network robustness, their application to training neural networks remains less explored. In response to this challenge, we reformulate the problem of training infinite-width two-layer ReLU networks as a convex completely positive program in a finite-dimensional (lifted) space. Despite the convexity, solving this problem remains NP-hard due to the complete positivity constraint. To overcome this challenge, we introduce a semidefinite relaxation that can be solved in polynomial time. We then experimentally evaluate the tightness of this relaxation, demonstrating its competitive performance in test accuracy across a range of classification tasks.

Published as a conference paper at ICLR 2025
CONVEX FORMULATIONS FOR TRAINING TWO-LAYER RELU NEURAL NETWORKS
Karthik Prakhya', Tolga Birdal' & Alp Yurtsever"
Department of Mathematics and Mathematical Statistics, Umeå University, Sweden f Department of Computing, Imperial College London, United Kingdom
ABSTRACT
Solving non-convex, NP-hard optimization problems is crucial for training machine learning models, including neural networks. However, non-convexity often leads to black-box machine learning models with unclear inner workings. While convex for- mulations have been used for verifying neural network robustness, their application to training neural networks remains less explored. In response to this challenge, we reformulate the problem of training infinite-wide two-layer ReLU networks as a convex completely positive program in a the convexity, solving this problem remains NP-hard due to the complete positivity constraint. To overcome this challenge, can be solved in polynomial time. We then experimentally evaluate the tightness this relaxation, demonstrating its competitive performance test accuracy across a range of classification tasks.
(lifted) space. Despite
introduce semidefinite relaxation that
INTRODUCTION
The outstanding performance of deep neural networks has driven significant changes in the research directions of optimization for machine learning over the past decade, replacing traditional convex optimization techniques with non-convex methods. Nonetheless, non-convexity introduces significant challenges to the analysis, resulting in the use of models that lack comprehensive explanation of their inner workings. While convex formulations have been studied for enhancing reliability through applications like estimating the Lipschitz constant of neural networks (Fazlyab et al., [2019 Chen
et al. 2020 Latorre et al. 2020 Pauli et al. 2023) or verifying their robustness (Raghunathan et al.
2018 Fazlyab al. 2020 Zhang 2020 Lan et al.) 2022] Chiu & Zhang 2023), their application to the training of neural networks remains less explored.
In this paper, we study convex optimization representations for training a two-layer neural network with rectifier linear unit (ReLU) activations and sufficiently wide hidden layer. While the rela- tionships between classical matrix factorization problems and two-layer linear neural networks, as well as those between matrix factorization and semidefinite programming, are well-established, our understanding of the connections between neural networks and convex optimization becomes less clear when non-linear activation functions involved. Our paper advances these connections by establishing links between convex optimization and neural networks with ReLU activations.
In light of this brief introduction, we summarize key contributions:
We present a novel copositive program for training a two-layer ReLU neural network, pro- viding an exact reformulation of the training problem when the network is sufficiently wide. Specifically, for fixed input and output dimensions and a given number of datapoints, there exists finite critical width beyond which the network's 's expressivity saturates, making the training problem equivalent to the proposed copositive formulation. We further extend this equivalence the general infth regime, where the neural network is represented as a Lebesgue integral over a probability measure on the weights.
Although copositive programs are convex, solving them is NP-hard (Bomze et al.) 2000). To mitigate this obstacle, we propose a semidefinite programming relaxation of the original formulation. We then numerically evaluate its tightness two synthetic examples. We also assess its performance on real-data classification tasks, where, combined with a rounding heuristic, our approach achieves competitive test accuracy compared to Neural Network

---

Published as a conference paper at ICLR 2025
Gaussian Process (NNGP) (Lee et al. 2018) and Neural Tangent Kernel (NTK) (Jacot et al. 2018 methods.
We make our implementation available under http:///ghhiaioo///aaataaaaaaaaa
BACKGROUND
Definition 1 (Positive semidefinite cone). A symmetric matrix W RRXX is said to be positive semidefinite if u Wu Z for all R". The set of all positive semidefintte matrices forms self-dual convex cone, known as the positive semidefinite cone, which can defined by
PSD, == conv conv(ww"" w E }
where conv represents the convex hull. We omit the subscript when the size is clear from the context.
Semidefinite programming. (SDP) is powerful framework in convex optimization focused on minimization of convex objective over the positive semidefinite cone. SDPs can solved in polynomial time under mild technical assumptions using interior-poin methods (Vandenberghe & Boyd 1996). We refer to (Majumdar et al. 2020 Yurtsever et al. 2021b) for an overview of recent advances in scalable solvers.
SDPs have been applied in neural networks for various tasks (often as a convex relaxation), including
the estimation of Lipschitz constant (Chen et al.) 2020 Fazlyab et al. 2019 Latorre et al. 2020
Pauli et al. 2023), verification of neural networks (Raghunathan et al., 2018 Zhang 20200 Chiu &
Zhang 2023 Lan al. 2022 Fazlyab et al. 2020), and for stability guarantees (Pauli al. 2022
2021 Revay et al. 2020 Yin et al. (021). A recent line work, initiated by Pilanci & Ergen (2020)
investigates the use of SDPs for training neural networks. We provide a detailed discussion and
comparison with these approaches in Section 6
Definition (Copositive cone). A matrix W E RRxx is said to be copositive if u W 2 0 all RT. The cone of copositive matrices called the copositive cone (COP).
Definition 3 (Completely positive cone). The dual of copositive cone is known as the completely positive cone, defined as
CPn == conv T. w E }.
(2)
is easy to see that completely positive cone is subset of positive semidefinite cone, and positive semidefinite cone is subset of copositive cone, as shown in Figure 1
DNN
Copositive programming (CP) is subfield of convex optimization con- cerned with minimization of convex objective function over copositive or completely positive matrices. Despite its convexity, solving CP is
NP-Hard (Bomze et al.) 2000). Numerous NP-Hard problems are for-
PSD
CP
N
mulated as CP, including the binary quadratic problems (Burer, 2009). problems of finding stability and chromatic numbers a graph (De Klerk & Pasechnik 2002 Dukanovic & Rend]] 2010). 3 3-partitioning problem (Povh & Rend] Rend]|207 2007). and the quadratic assignment problem (Povh & Rendl 2009). We refer to the excellent surveys (Dür 2010 Dür & Rendl
COP
2021 and references therein for more examples.
Figure 1: Cones.
Recent research has broadened the scope of CP into data science. For example, CP formulations have been utilized in machine learning for verifying neural networks (Brown et al.) 2022), and problems such as graph matching and permutation synchronization in computer vision Yurtsever et al.) 2022). CP formulations have also been proposed for training two-layer ReLU networks, though under specific data-related assumptions (Sahiner et al. 2021.
Definition 4 nNon-negative cone). The non-negative cone N comprises of entry-wise non-negative matrices.
Definition 5 (Doubly non-negate non-negatvve cone). The doubly non-negative cone is the set of matrices that both positive semidefinite and elementwise non-negative, defined by DNN == PSD N.. It is an important subset of the positive semidefinite cone that contains the cone of completely positive matrices and is frequently used in relaxations of CP formulations.
2

---

Published as a conference paper at ICLR 2025
Definition 6 (Rank), For matrix W E PSD,,, the rank is the minimum number of vectors w, I required to express W as a convex combination of w.w.!-
Definition 7 (CP-rank), We refer the rank restricted to decomposttions involving non-negative vectors as the CP-rank: The CP-rank of a matrix W E CPp. is the minimum number of non-negative vectors w; R that needed express W as a corvex combination of w.w.
It is well known that the rank of any X n matrix W cannot exceed nt The following result from (Barioli & Berman 2003 Theorem 3.1) characterizes the maximal CP-rank.
Lemma 1. Let W be completely positive matrix of rank r 2 2. Then, the CP-rank of W cannot exceed r(r 1)/2- --- 1. As an immediate corollary, the CP-rank of any n n completely positive matrix for n 2 2 is bounded above by n(n + 1)/2 1, which we denote as the maximal Ca-rank.
3 CP FORMULATION FOR TRAINING TWO-LAYER RELU NETWORKS
We now present our CP formulation for training two-layer ReLU networks. We start by the wide regime with finite width before moving onto the infinite case that carries theoretical importance.
Definition (Two-Layer ReLU Network), A two layer neural network v IRd R with m hidden neurons and ReLU activations given by
(x)) (x uz)+
(NN)
where the function (-)+ max(0, -) denotes the ReLU activation, {u, F 15= are the weights for the first layer and {0, IR 53=1 are the second layer weights.
Assuming that the data matrix X E Rxxd and labels Y E R are given, and using the mean squared error loss and Tikhonov regularization (also known as weight-decay), the problem for training this neural network can be formulated as follows:
min ERR
Σ (Xuj)+ j=1
Y
(1 1 + 1105)12)
(NN-Train)
2
EJER"
where 7 2 is the regularization parameter.
In the following, our main result an equivalence between the above training problem and the following convex optimization problem with PSD and CP constraints when m sufficiently large:
Theorem (CP Formulation). Consider the two-layer ReLU neural network in Eg. (NN) For any fixed input dimension d, output dimension c, and number of data points n, there exists finite critical width R < m 2n + 1}, where c d + 2n, such that, for m 2 R hidden neurons, the training problem [NN-Train) is equivalent to the convex optimization problem (CP-NN), meaning that they have identical optimal values:
PAAP. -II ? (trace P...P... + trace (..PP.))
min A
s.t.
trace(Pa.)) (MAC =0
(CP-NN)
A E PSD
P PasAPT CP,
where M = Pa + P3 XPa and the selection matrices are defined as follows:
P.
Odxn
Oaxn
Taxd
Odxc]
P. [uvn
Onxe
Onxd
Onxel
P Pa
and Pas
P. Ocxn
Ocxn
Ocxd
Lexe]
P3
0nxn
Inx
Onxd
0,xe]
It is noteworthy that this formulation is independent of m and hence does not scale in size with the number of hidden neurons. Our analysis is also independent of the loss. Hence, we can get the same guarantees for any convex loss function long as well. Additional bias terms can be incorporated into this formulation by augmenting the input data with column of ones.
the corresponding loss function in (CP-NN)

---

Published as a conference paper at ICLR 2025
Proof sketch. The first challenge in NN--Trii) problem arises from the non-linear ReLU activation function, which we address by decomposing Xu into its positive and negative parts, inspired by (Brown al. we have X u a 3 if and only if a = (Xu). and B = (Xu) Xu, corresponding to the positive and negative components, respectively.
2022). Specifically, for non-negative vectors a and f such that trace(a.8 0.
Introducing the variable > = |a 53
E RR, we can reformulate NN-Train as:
2 +
min A
Σ
Po P - -Y
P1 + |
2 ==1
(3)
s.t. PaSAj 02nxl trace P ( MA, = 0
Our goal is to show that the problem C is equivalent problem (3) when is sufficiently
large. To this end, we establish that any matrix A E PSD satisfying PagAPas E CP can be factorized as A Σ A where Pasd 2 O, and R is finite number bounded by R < [p 2n² + n l (see Lemma 2 in the supplementary material), Here, the first term (p) represents the maximal rank of A, and the second term (2n² + n 1) is the maximal CP-rank of PagAPat a.
Thus, for any m 2 R, we can reformulate (CP-NN) by expressing A as EiS >z2J, with the constraint Pa 2 02nx1, without changing global solution:
P.AJAAP Y I (1PAA) 11)))13)
min
Ay
(4)
s.t. Pasdj
0 02nx1
(eaacePaa2.a P. |M (l)) 0.
where we used the fact that trace(ab traceeb b a), which further simplifies to ||a l1 when a b. We have omitted the PSD and CP constraints since they are inherently satisfied by the factorization.
Problems 3 and 44) share the same objective function. Next, we show that their feasible sets are also identical. Note that since each term in the summation constraint of problem (4) is non-negative, the sum can be zero only if each individual term is zero. We complete the proof by noting |M, 1
and only if MAj = Opx1. For more details on the proof, we refer the reader to Appendix
Remark 1. Although we focused on the MSE loss for simplicity, our results extend to any convex loss function f. Rdd x Re - TR.
3.1 THE INFINITE WIDTH REGIME
Definition 9 (Infinite-wile width Two Layer RELU Networks). An infinite-widih fully connected two-layer ReLU network can be expressed as a Lebesgue integral over a signed measure v v) defined on the weights u and v, subject the condition that (x (u)+ is integrable w.r.t. v for any Rd:
-f JRARRS
(bxx))
(x. (xTT))_ uu)= du(u,
(NN))
A similar characterization of infinite-width neural networks can be found in (Mhaskar 2004 Bach 2017). For our analysis, we restrict v(u,o) v) to be a probability measure induced over the product space, v Bd+e - [0, 1]. where 8 is the Borel o-algebra over R..
While the case of countably infinite number of hidden neurons, which is represented by an infinite sum in Eq. (NN) is captured as special case of Eq. (NN() with discrete probability measure, Eqq (NN) ) also accommodates other notions of infinite-width networks, as the underlying probability measure can be continuous or combination of discrete and continuous components.
The training of an infinite-widee width ReLU neural network given in Eq. (NN)) with the mean squared error loss can be expressed as follows:
min vg v=Bd+==(0.. [0.1]
[
(x)) ndu v) Y
7
2 (11aal12
+| de v), (NNf-Train)
Rd xB=
2
Rd xie
4

---

Published as a conference paper at ICLR 2025
where optional Tikhonov regularization is controlled by the parameter > 0. The following theorem presents our second main result, which shows that the training problem NN NNj-Train) is also equivalent to our CP formulation.
Theorem 2. Consider the two-layer infinite-width ReLU neural network defined in Eg. (NN)) For any input dimension d and outpul dimension e, the training problem (NNj-Train) is equivalent the convex optimization problem (C--NN,, implying that they share the same optimal values.
We refer the reader to Appendix Cfor the proof. This result implies that the infinite-width ReLU network training problem (NNj -Tain) can be solved to global optimality by training finite-width ReLU network with width exceeding the critical threshold defined in Theorem The resulting solution can then be represented as a discrete probability measure with finite support.
4 SDP RELAXATION FOR TRAINING TWO-LAYER RELU NETWORKS
Despite its convexity, solving CP-NN remains intractable due to the complete positivity constraint. To tackle this challenge, propose SDP relaxation.
Proposition 1 (SDP-NN), The following SDP is a relaxation of the (CP-NN) problem, obtained by replacing the completely positive cone with the doubly non-negative cone, resulting in the constraints ag E PSD. The latter is omitted as it is inherently satisfied for all P.. P. og E N and PaRAPas
E PSD:
PGAP. YII + 2 (..cce + trace( (race(P,APP.) P.AP..)
min АERPXP
s.t.
trace( P.AP.) + trace (MAM)
(SDP-NN)
A E PSD
PaşAPT og EN.
Remark 2. This is essentially the zeroth-order Sum-of-Squaree (SoS) relaxation of (Cp-NN). While tighter relaxations could be constructed using the SoS hierarchy (Parrilo) 2000), the computational requirements often make these higher-order formulations impractical.
After solving (DD--NN rounding procedure required to extract the weights of the trained neural network from the lifted solution A..
Proposition 2 (Rounding). Selecting the rounding width R the critical width of the network, we can formulate the rounding problem follows;
min AERPXR
((A) = |A -X
(5)
S.L.
MA OnXR P.d o PBA= 0
PaR 2 02ax
where ④ denotes the Hadamard product. The first and second layer weights can be recovered from the rounded solution as P, and P.X, respectively.
is straightforward to verify that the feasible set of problem 5 coincides with that of problem (3), which is, in turn, equivalent to the feasible set of the (CP-NN) problem. Consequently, this formulation aims to identify the closest point AX to the SDP solution A, within the feasible set of (CP-NN). While finding global solution intractable due the non-convexity of the objective function and constraints, we propose an effective heuristic based on the three-operator splitting (TOS) method (Davis Yin 2017). We define the two sets comprising the constraints as:
D1 = RAE R P.P 6 p3d = OnxR Pasd A 2 02nxR)
D2 = [ MA OnXR)
Then, we can apply TOS for the rounding, starting from an initial estimate X E RRxXR and iteratively updating by the following formula:
A k projp, (X*)
A projp, (2X X xx-
(TOS)
X k++ = k - x j
5

---

Published as a conference paper at ICLR 2025
Table 1: Summary of datasets, their sizes, and dimensions of the corresponding SDP relaxations.
Dataset
# Instances
# Inp. Feat
# Out. Feat
Variables
# Constraints
Random
25
2
5
3249
8999
Spiral
60
2
3
15625
45651
Iris
75
3
24649
71799
Tonosphere
175
34
2
148996
420493
Pima Indians
383
2
602176
1791109
Bank Notes
685
4
2
1893376
5663653
MNIST
1000
20
10
4120900
12743300
Note: The # Instances column shows the number of training samples.
All real datasets are split into 50% train and 50% test sets.
where 7) 0 the step-size parameter. We can compute the gradient by Vo(A) -A.A projo, (A) (I M M projects À onto the nullspace of M. And projp, can be computed as
2n, As.j <0
0
1 isisn Atti. > Aud
projp, (A)is
(6)
0
n n+1sis 2n, X Ainn.j Xi.j
A
otherwise
Remark We employ the rounding step primarily to demonstrate that the solution obtained from the SDP relaxation is reasonable. Our main objective is to assess the quality of the SDP relaxation, not to guarantee convergence in the rounding phase. To the best of our knowledge, there are no known convergence guarantees for TOS in our setting, as existing results for TOS in non-corvex optimization apply only to smooth non-convex terms (Bian & Zhang 2027 Yurtsever et al. 2021a) and do not extend to non-convex constraint sets. Nonetheless, TOS has proven be effective heuristic in our experiments, validating the (SDP-NN) relaxation. The ability to extract trained newral network weights confirms that the (SDP-NN) solution encodes the necessary information. importantly, the rounding step is not integral to our theoretical contributions and is used only for empirical evaluation.
5 NUMERICAL EXPERIMENTS
We conduct a series of experiments over synthetic and real datasets investigate the empirical tightness of our SDP relaxation.
Datasets. We use the following datasets in our experiments:
Random: A synthetic dataset with a data matrix X E IR 25xx and labels Y 25xx generated using a 2-layer neural network with 100 hidden neurons. We create 100 random datasets by initializing the entries of X and the generator network's weights using standard normal distribution.
Spiral: An artificiall--generatedd 3-class classification dataset, described by (Sahiner et al. 2021 It includes 60 samples (20 per class), with data matrix X E R60x2 containing input features and one-hot encoded labels Y E g60x3
Iris (Fisher 1936): The dataset consists of 150 samples of iris flowers from three different classes, each sample is described by four features. The training partition includes a data matrix X E R75x1 and one-hot encoded labels Y e 75x3
Ionosphere Sigillito et al. 1989): A radar dataset with 351 instances and 34 input features for binary classification, with class imbalance. The training partition includes a data matrix X e 175x34 and one-hot encoded labels Y E 175x2
Pima Indians Diabetes (Smith et al. 1988): A diabetes prediction dataset that consists of 768 patients, with 8 medical predictors features, and binary classification task, with class imbalance. Out of 768 instances, we have 268 positive instances. The training partition includes data matrix X R333xx and one-hot encoded labels Y E 3833x2

---

Published as a conference paper at ICLR 2025
Table 2: SGD Loss, Approximation Ratio (AR) (%), and Runtime (sec) of SDP-NN.
Dataset
Training Objective
AR
Runtime
SGD-5
SGD-10
SGD-100 100
SGD-200
SGD-300
SDP-NN
SDP-NN
SDP-NN
0.1
18.27
#5.76
8.60
#1.16
8.09
+1.04
8.09
#1.04
8.09 +1.04
7.28 +0.98
89.93
11.46
Random
0.01
11.78
+5.53
1.32
#0.25
0.94
+0.12
0.94 #0.12
0,94
20.12
0.76 40.10
80.66
14.85
0.1
16.64
16.59
16.59
T6.59
16.59
16.24
97.84
1566.65
Spiral
0.01
15.56
15.21
15.16
15.16
15.16
11.66
76.90
923.83
Bank Notes Authentication Lohweg 2012): A binary classification dataset with 1372 instances, where features extracted using wavelet transforms are used to determine whether a banknote is genuine or forged. The training data includes X E IR 18688x and one-hot encoded labels Y E IR 68552
MNIST LeCun et al. 2010): A down-sampled and dimensionalll-rrcuued version of the popular image classification dataset, consisting of 1000 instances with 20 features each obtained using Principal Component Analysis (PCA). The training data includes X E 100000000 and one-hot encoded labels Y E R g0000100
Table provides an overview of the dataset sizes and the dimensionality of the corresponding problem size of SDP-NN All real datasets were split 50-50 into train and test partitions.
Computational environment & complexity. The experiments were conducted on Intel Xeon Gold 6132 with 192 GB of RAM and 2x14 cores. Solving CP-NN or the associated rounding problems is NP-hard. The complexity of solving an SDP depends on the specific algorithm used. Our SDP formulations were solved by CVXPY (Diamond & Boyd 2016), employing either the interior point method (IPM) solver by MOSEK (Andersen & Andersen 2000), the Splitting Cone Solver (SCS) O' O'donoghue et al. 2016). depending on the problem size. typical interior point method for solving SDP problem with an n matrix variable and constraints requires approximately On + m²² + m²² arithmetic operations per iteration and about ([log(1/e)) iterations to achieve an e-accurate solution. While the formulation scales with n² (since the rank is absorbed), storing CP factorization of the decision variable (i.e., the neural network weights) requires O(n²) storage.
5.1 EMPIRICAL APPROXIMATION RATIO OF THE SDP RELAXATION
We evaluate the tightness of our SDP relaxation by comparing its optimal objective value to the training loss obtained using Stochastic Gradient Descent (SGD) on (NN-Train). Due to the difficulty of approximating the global optimum with SGD on real datasets, we conduct this experiment using the synthetic Random and Spiral datasets.
The results are summarized in Table 2] For each dataset, we solve the training problem using regularization parameters 7 = 0.T and 7 0.01. The table columns show the training loss achieved by SGD for various hidden layer sizes, ranging from m = 5 to m = 300, along with the training loss achieved by the SDP-NN formulation. For the Random dataset, the results are averaged over 100 trials, with error bars indicating standard deviations.
The last column reports the approximation ratio (AR) of the SDP relaxation, computed the ratio of the loss obtained by SDP-NN to the loss achieved by SGD with 300 hidden neurons. Empirically, we find that the approximation ratio is above 76.90% in these experiments. We also observe that the ratio improves for higher regularization parameters, which is expected, as stronger regularization tends to smooth the optimization landscape and reduces the impact of non-convexity.
Remark 4. Ratio reported in Table 2) represents only lower bound on the actual approximation ratio; since, (i) SGD) may converge to a local solution, and (ūi 300 hidden neurons used in this experiment is smaller than the actual critical width, which scales quadratically with the number of data points, and quickly exceeds practical limits.
To partially address these challenges, we ran SGD five times with different random initializations for each configuration and selected the best outcome. Even so, there is no guarantee of reaching a global optimum. Similarly, although m = 300 is below the critical width, we observe that the results tend to saturate, and increasing further does not lead any significant improvements for SGD. Despite these limitations, SGD training can provide an upper bound on the optimal value for definit-widdt neural network training. To complement this, compute lower bound the optimal values of
7

---

Published as a conference paper at ICLR 2025
Table Evaluating prediction quality (FI Score & Accuracy) and runtime (seconds).
Iris
lonosphere
Pima Indians
Bank Notes
MNIST
Method
0.1
0.01
0.1
0.01
0.1 7
0.01
0.1
0.01
0.1
0.01
Weighted Average Fl Score
SGD
0.96
0.987
0.915
0.898
0.626
0.594
0.993
0.992
0.880
0.863
NNGP
0.866
0.975
0.919
0.928
0.690
0.683
0.978
0.993
0.903
0.919
NTK
0,993
0.993
0.924
0.920
0.668
0.672
0.991
0.993
0.907
0,915
SDP-NN
0.987
0.987
0.924
0.927
0.679
0.703
0.930
0.893
0,862
0.849
SDP-NN-bias
0.946
1.000
0.912
0.921
0.714
0.744
0.991
0.985
0.858
0.838
Overall Test Accuracy
SGD
0.960
0.987
0.891
0.88
0.583
0.557
0.988
0.985
0.818
0,796
NNGP
0.827
0.973
0.886
0.886
0.534
0.602
0.966
0.983
0,858
0,879
NTK
0.987
0.987
0.886
0.897
0.586
0.620
0.983
0.985
0.863
0.876
SDP-NN
0,987
0.987
0.920
0.909
0.646
0.625
0.860
0.767
0.794
0.778
SDP-NN-bias
0.947
1.000
0.909
0.914
0.672
0.703
0.991
0.980
0.791
0.76
Runtime (sec)
SDP-NN
39
171
4416
8150
12256
13564
102919
101952
66157
155810
the SDP formulations using the dual objectives in CVXPY, utilizing the interior-pone solver from MOSEK. Together, these bounds allow us establish reliable approximation lower-bound for the relaxation.
The training loss curves of SGD for each experiment, along with implementation details such as learning rate and number of epochs, are provided in Appendix
5.2 PREDICTION PERFORMANCE OF THE SDP RELAXATION
We assess the prediction quality of our SDP relaxation combined with the TOS-based rounding procedure on real datasets using regularization parameters y = 0.1 and 7 0.01. Due computa- tional constraints, we set the rank R in the rounding procedure to 300, which is lower than the actual critical width. The rounding procedure is initialized using the square root of the SDP-NN solution, obtained via SVD decomposition. We then adjust the resulting factor matrices by either truncating or expanding them to dimensions P000 The TOS step size is set as 1) = L/||A ||2. where A, denotes the solution to the SDP-NN, and the algorithm is run for 1000 iterations.
We benchmark our test accuracy against the NNGP and NTK kernel methods and include results from SGD with 300 hidden neurons baseline. The results of this experiment
summarized in Table 3] where the weighted average Fl score and test accuracy are used as the performance metrics. For classification, the threshold was varied from 0 to 1 in increments of 0.01, and the threshold that maximized the overall test accuracy was selected. Overall, the predictions obtained from the SDP relaxation are competitive across most settings.
Effect of bias. We also experimented with incorporating a bias term to the first layer. As expected, Table (SDP-NN-bias) shows general increase in terms of the weighted average F1 score and overall test accuracy.
6 RELATED WORKS
We now review the literature (in)finite width neural networks as well as convex optimization techniques for training them.
Convex optimization for neural network training. Early discussions of convex neural nets can be found in (Bengio et al., 2005 Bach 2017 Fang et al. 2022). These initial studies primarily focus on networks with infinite width, which leads to optimization problems in an infinieeddimensional space.
Sahiner al. 12021) developed convex equivalents for the non-convex NN training problem with ReLU activations, based on a theory of convex semi-infinite duality. Different than ours, their approach involves explicit summation over all possible sign patterns in the ReLU layer. Since the number distinct sign patterns grows exponentially with the rank of the data matrix, their analysis is primarily focused data matrices of fixed small rank the spike-free structures. Building
8

---

Published as a conference paper at ICLR 2025
this duality theory, Ergen & Pilanci (2021a) derived convex optimization formulations for two- or three-layer convolutional neural networks (CNNs) with ReLU activations. Barttan & Pilanci (2021a) explored semidefinite lifting for training neural networks with polynomial activations, which is further extended to quantized neural networks with polynomial activations in (Bartan & Pilanci 2021b), and to deep neural networks with polynomial and ReI.U activations in (Bartan & Pilancij 2023) ) Ergen & Pilanci] (2021c) demonstrated that training multiple three-layer ReLU regularized sub-networks can be equivalently cast as a convex optimization problem in a higher-dimennsonall space, [Ergen & Pilanci (2021b showed that optimal hidden- -laeer weights for two-layer and deep ReLU neural networks are the extreme points of a convex set. They further applied these methods in transfer learning tasks with large language models. [Sahiner et al. (2022) developed convex optimization problems for vision transformers, focusing on a single self-attention block with ReLU activation. Finally, Wang et al. (2024) introduced randomized algorithms from a geometric algebra perspective to efficiently address the enumeration of sign patterns. (Sahiner et al. (2024) applied the Burer-Monteirg factorization (Burer& & Monteiro 2003) to efficiently solve these formulations at a larger scale.
Our mathematical techniques differ from prior work. Unlike (Sahiner et al. [02T], we do not require enumeration sampling of sign patterns, nor do we rely on the aforementioned duality theory, Unlike (Fang et al., 2022), we do not assume activation functions with continuously differentiable gradients. and formulate the training of finite- and infinite-wiin width ReLU neural networks dimensional convex optimization problem, assuming fixed input/output dimensions and a set number of data points, characterizing finite critical width. Since our CP formulation is exact yet intractable, we propose SDP relaxations that can be solved in polynomial time.
finite-
Infinite- Wefin Neural Networks (IWNNs). Investigations of IWNNs address fundamental questions about the limits of their learning ability and the types of functions they can approximate. This focus is also relevant as overparameterized networks. which are commonly used in practice, often demonstrate strong generalization to unseen data (Zhang et al., (202I). Another motivation for studying IWNNs is their connection to other areas of machine learning, such as Gaussian processes (Neal 2012). There are two main approaches for training infinite-widh fully connected neural networks in the literature: weakly-trained networks and fully-trained networks.
Weakly- networks are those where only the top classification layer is trained, while all other layers remain randomly initialized. [Lee et al.] (2018); Matthews et al. (2018) studied fully- connected weakly-trained IWNNs, while Novak et al. (2019); Garriga-Alonso et al. (2019) focused on convolutional variants. Yang 2019) extended this analysis to other weakly-trained infinite-width architectures. All these works adopt a Gaussian process (GP) perspective of weakly-trained IWNNs.
In contrast, fully-trained networks are those in which all the layers are trained, using variations of gradient descent. [aacot et al. (2018) introduced Neural Tangent Kernel (NTK), which captures the behavior of fully-connected deep neural networks in the infinite-width limit, trained using gradient descent. The NTK is different from the GP kernels: it is defined by the gradient of a fully connected network's output with respect to its weights, based on random initialization. Arora al. (2019) gave a rigorous, non-asymptotic proof that the NTK captures the behavior of a fully-trained wide neural network under weaker conditions and introduced the concept of convolutional neural tangent kernel (CNTK). They also developed an exact and efficient dynamic programming algorithm to compute CNTKs for ReLU activation. [Lee et al. (2020) conducted an empirical study comparing the Neural Network Gaussian Process (NNGP) kernel (Lee et al.) (018)) and the NTK in both finite-width and IWNNs. Unlike these, we do not adopt a GP-based view or kernel methods. Instead, we model fully-trained fully-connected IWNNs using a CP formulation and corresponding computationally tractable SDP relaxations.
Another line of work focuses on the learning theory of infinite-widde neural networks, including
universal approximation bounds (e.g., (Barron) 1993 Mhaskar| 2004 Klusowski & Barron 2018)),
representer theorems (e.g.. (Parhi & Nowak 2021 Bartolucci et al. 2023] Shenouda et al. 2024 ))
and capacity control results (c.g.. (Ongie et al. [019 Savarese et al. 2019)). ). Of particular relevance, in their recent work, (Shenouda et al. (2024) showed that infinite dimensional learning problem in variation spaces (a special class of reproducing kernel Banach spaces) can be solved by training a umite-width neural network with width greater than the square of the number of training data points. Intriguingly, this result draws parallels with our critical width R, which also scales quadratically with the number of training data points, although the underlying assumptions and analytical techniques in the two works are significantly different.

---

Published as a conference paper at ICLR 2025
Other related works. We address the non-convex problem of training two-layer ReLU neural networks by transforming it into a convex optimization problem in a higher-dimensional space. This approach belongs to class of techniques known lifting,, where the decision variable is replaced with a quadratic term W = wow enabling the convex reformulation or relaxation of an otherwise non-convex problem, see (Bomze al. 20000; Burer 2009 |ao et al. 2011; Anstreicher (012) and references therein. In the context of neural networks, Brown et al. (2022) applied lifting for the verification of neural network outputs. A key distinction between our formulation and the prior work in (Burer 2009 Brown et al. 2022) lies in the structure of the objective function. In previous work, the objective function quadratic in the original space and simplifies
linear objective in the lifted space, which plays a crucial role in the analysis, as solutions to linear minimization problems always appear at extreme points of the feasible set. In our problem, the objective function is convex the lifted space (rather than linear), and we establish an exact correspondence between the feasible sets in the original and lifted spaces for both wide and infinite-width networks.
Our work should not be confused with the line of research introduced by |Askari et al. (2018) known as lifted neural networks, as the notion of lifting in our work differs from theirs. Both the goals and approaches are distinct. They reformulate the problem as biconvex optimization, enabling wiser-wise training via block coordinate descent. They do not introduce the quadratic terms that are central to approach, and their resulting problem formulation remains non-convex.
7 CONCLUSIONS AND FUTURE DIRECTIONS
We derived convex optimization formulation for the training problem of a two-layer ReLU neural network with a sufficiently wide hidden layer. Despite its convexity, the problem is intractable using classical computational methods due to the completely positive cone constraints. To address this, proposed an SDP relaxation that can be solved in polynomial time using off-the-shelf SDP solvers, combined with a rounding heuristic. Notably, the size of our formulation is independent of the network width. While previous work has established the critical width for universal approximation of continuous functions with neural networks (Cail 2022). we established limits on the expressivity of wide-width neural networks in terms of the data size as our critical width R is based on the size of the data. These type of findings can help advance theoretical understanding of neural networks.
Limitations. An obvious limitation of the proposed framework its lack of scalability, common issue for many SDP formulations in machine learning applications. Since the problem size scales quadratically with the number of data points, solving these formulations at the scale required for real-world neural network applications poses significant computational challenge. Nevertheless, our findings offer valuable theoretical insights into ReLU networks, for instance, allowing us to interpret the network width as the
of the corresponding completely positive program.
Future work. We proposed exact CP formulation, which is computationally intractable for classical computers. However, rapid progress in quantum computing poses a promising alterna- tive (Birdal et al. 2021a). In particular, hybrid classical-quantum algorithms have demonstrated potential for solving specific classes of copositive programs (Yurtsever et al.) 2022 Brown et al. 2024) as well as training binary versions of neural networks (Krahn et al. 2024). Developing and implementing digorithms-ever as proof-of-concept experiments-to to train general ReLU networks on these platforms represents compelling research direction.
Overm-aaraettrrized networks are often easier to optimize using traditional methods such as SGD (Livni al. 20114). Although is possible to construct compact networks with fewer parameters that generalize comparably, compressed models are significantly more challenging to optimize in the dimensionai space (Arora et al. 2018). similar phenomenon is observed the SDP literature: Waldspurger & Waters (2020) showed that even when an SDP has a unique rank-1 solution, factorizing the variable with rank below a certain threshold may introduce spurious local minima. Given these parallels, natural question arises: is there corresponding bound for completely positive programs, and could this provide insights into the required width of ReLU networks?
10

---

Furthermore, all random seeds are provided to Published as a conference paper at ICLR 2025
ETHICS & REPRODUCIBILITY
Ethics. This work adheres to the ICLR Code of Ethics, ensuring responsible use of publicly available datasets and maintaining full transparency in experimental design and reporting, The study complies with ethical guidelines on research integrity and considers potential societal impacts. Since the contributions are primarily theoretical, the focus is on advancing our understanding of the theory of artificial intelligence rather than targeting specific applications that may have direct societal impacts.
Reproducibility statement. All datasets used in this work are referenced and publicly ac- cessible. The experimental configurations and computational environment tail within the main text and the appendix. We make our implementation available under https:/github..com httprehhwb.ooo/aaatikkkkeee Praaaiikrrraya//SDPPNN.. facilitate precise reproducibility.
outlined in de-
ACKNOWLEDGMENT
AY and KP were supported by the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation. We thank the High Performance Computing Center North (HPC2N) at Umeå University for providing computational resources and valuable support during test and performance runs. The computations were enabled by resources provided by the National Academic Infrastructure for Supercomputing in Sweden (NAISS), partially funded by the Swedish Research Council through grant agreement no. 2022-06725. TB was supported by UKRI Future Leaders Fellowship Igrant number MR/Y0188 1018888//1 18/1]. We acknowledge the use of OpenAT's ChatGPT for editorial assistance in preparing this manuseript.
REFERENCES
Erling D Andersen and Knud D Andersen. The mosek interior point optimizer for linear programming: an implementation of the homogeneous algorithm. In High Performance Optimization, pp. 197-232. Springer, 2000.
Rayna Andreeva, Benjamin Dupuis, Rik Sarkar, Tolga Birdal, and Umut Simsekli. Topological generalization bounds for discrete-time stochastic optimization algorithms. The Thirty-eighth Annual Conference Neural Information Processing Systems, 2024.
Kurt M Anstreicher. On convex relaxations for quadratically constrained quadratic programming. Mathematical Programming. 136(2):233-25 2012.
Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via a compression approach. In International Conference on Machine Learning. PMLR, 2018.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. Advances in Neural Information Processing Systems, 32, 2019.
Armin Askari, Geoffrey Negiar, Rajiv Sambharya, and Laurent El Ghaoui. Lifted neural networks. arXiv preprint 1=05..00000000 08350053,, 2018.
Francis Bach. Breaking the curse of dimensionality with convex neural networks. The Journal of Machine Learning Research, 18(1):6296611, 2017.
Xiaowei Bao, Nikolaos Sahinidis, and Mohit Tawarmalani. Semidefinite relaxations for quadrati- cally constrained quadratic programming: A review and comparisons. Mathematical Programmingg 129:129-1511 2011.
Francesco Barioli and Abraham Berman. The maximal ep-rank of rank k completely positive matrices. Linear Algebra and its Applications, 363, 2003.
Andrew R Barron. Universal approximation bounds for superpositions of sigmoidal function. IEEE Transactions on Information theory, 39(3))930-94) 1993.
Burak Bartan and Mert Pilanci. Neural spectrahedra and semidefinite lifts: Global convex op- timization of polynomial activation neural networks in fully polynomial-ting time. arXiv preprint arXiv:2101.02429, 2021a.
11

---

Published as a conference paper at ICLR 2025
Burak Bartan and Mert Pilanci. Training quantized neural networks to global optimality via semidefi- nite programming. In International Conference on Machine Learning. PMLR, 2021b.
Burak Bartan and Mert Pilanci. Convex optimization of deep polynomial and relu activation neural networks. In ICASSP 2023-2023 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 1-5. IEEE, 2023.
Francesca Bartolucci, Ernesto De Vito, Lorenzo Rosasco, and Stefano Vigogna. Understanding neural networks with reproducing kernel banach spaces. Applied and Computational Harmonic Analysis, 62: 2023.
Yoshua Bengio, Nicolas Roux, Pascal Vincent, Olivier Delalleau, and Patrice Marcotte. Convex neural networks. Advances in Neural Information Processing Systems, 18, 2005.
Fengmiao Bian and Xiaoqun Zhang. A threc-operator splitting algorithm for nonconvex sparsity regularization. SIAM Journal on Scientific Computing, ((44)))22899-88833) 2021.
Tolga Birdal, Vladislav Golyanik, Christian Theobalt, and Leonidas J Guibas. Quantum permutation synchronization. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 13133, 2021a.
Tolga Birdal, Aaron Lou, Leonidas J Guibas, and Umut Simsekli. Intrinsic dimension, persistent homology and generalization neural networks. Advances in Neural Information Processing Systems, 34:6776-67777 6789, 2021b.
Immanuel M Bomze, Mirjam Dür, Etienne De Klerk, Cornelis Roos, Arie J Quist, and Tamás Terlaky. On copositive programming and standard quadratic optimization problems. Journal of Global Optimization, 18(4):301-320 2000.
Robin Brown, David E Bernal Neira, Davide Venturelli, and Marco Pavone. A copositive framework for analysis of hybrid ising-classical algorithms. SIAM Journal on Optimization, 34(2), 2024.
Robin A Brown, Edward Schmerling, Navid Azizan, and Marco Pavone. A unified view of sdp-based neural network verification through completely positive programming. International Conference on Artificial Intelligence and Statistics, pp. 9334-9355. PMLR, 2022.
Samuel Burer. On the copositive representation of binary and continuous nonconvex quadratic programs. Mathematical Programming, 120(2):479 495, 2009.
Samuel Burer and Renato DC Monteiro. A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Mathematical Programming, 95(2), 2003.
Yonggiang Cai. Achieve the minimum width of neural networks for universal approximation. arXiv
preprint arXiv:2209. 2022.
Tong Chen, Jean B Lasserre, Victor Magron, and Edouard Pauwels. Semialgebraic optimization for lipschitz constants of relu networks. Advances in Neural Information Processing Systems, 33: 19189-19200, 2020.
Hong-Ming Chiu and Richard Y Zhang. Tight certification of adverfsarially trained neural net- works via nonconvex low-rank semidefinite relaxations. In International Conference on Machine Learning, pp. 5631-5660. PMLR, 2023.
Damek Davis and Wotao Yin. A three-operator splitting scheme and its optimization applications. Set-valued and Variational Analysis, 25:829- 858, 2017.
Etienne De Klerk and Dmitrii V Pasechnik. Approximation of the stability number of graph via copositive programming. SIAM Journal on Optimization, 12(4):875-892, 2002.
Steven Diamond and Stephen Boyd. CVXPY: A Python-embedded modeling language for convex optimization. Journal of Machine Learning Research, 17(83):1-5, 2016.
Igor Dukanovic and Franz Rendl. Copositive programming motivated bounds on the stability and the chromatic numbers. Mathematical Programming, 121(2):249-28) 228, 2010.
12

---

Published as a conference paper at ICLR 2025
Mirjam Dür. Copositive programming- survey. In Recent Advances in Optimization and its Applications in Engineering. pp. 3-20. Springer, 2010.
Mirjam Dür and Franz Rendl, Conic optimization: A survey with special focus on copositive optimization and binary quadratic problems. EURO Journal on Computational Optimization, 9: 100021, 2021.
Faniriana Rakoto Endor and Irene Waldspurger. Benign landscape for burer-monteiro factorizations of maxcut-type semidefinite programs, arXiv preprint arXiv:2411.03103, 2024.
Tolga Ergen and Mert Pilanci. Implicit convex regularizers of cnn architectures: Convex optimization
of two-and three-layer networks in polynomial time. In International Conference Learning Representations, 2021a.
Tolga Ergen and Mert Pilanci. Convex geometry and duality of over- over-parameterized neural networks. Journal of Machine Learning Research, 22(212):1 -63, 2021b.
Tolga Ergen and Mert Pilanci. Global optimality beyond two layers: Training deep relu networks via convex programs. In International Conference on Machine Learning. PMLR, 2021c.
Tolga Ergen and Mert Pilanci. Revealing the structure of deep neural networks via convex duality. In International Conference on Machine Learning, pp. 3004-3014. PMLR, 2021d.
Cong Fang, Yihong Gu, Weizhong Zhang, and Tong Zhang. Convex formulation of overparameterized deep neural networks. IEEE Transactions on Information Theory, 68(3):5340-53522 2022.
Mahyar Fazlyab, Alexander Robey, Hamed Hassani, Manfred Morari, and George Pappas. Efficient and accurate estimation of lipschitz constants for deep neural networks. Advances in Neural Information Processing Systems, 32, 2019.
Mahyar Fazlyab, Manfred Morari, and George Pappas. Safety verification and robustness analysis of neural networks via quadratic constraints and semidefinite programming. IEEE Transactions on Automatic Control, 67(1):1-15 2020.
Ronald Aylmer Fisher. Iris [Dataset]. https:/0bi.org/102444333CCCCCC
UCI Machine Learning Repository, 1936. DOI:
Adrià Garriga-Alonso, Carl Edward Rasmussen, and Laurence Aitchison. Deep convolutional networks shallow gaussian processes. In International Conference on Learning Representations, 2019.
Sepp Hochreiter and Jürgen Schmidhuber. Flat minima. Neural computation, 9(1):1-42, 1997.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. Advances in Neural Information Processing Systems, 31, 2018.
Jason M. Klusowski and Andrew R. Barron. Approximation by combinations of relu and squared relu ridge functions with ed and e controls. IEEE Transactions on Information Theory, 64(12): 7649-7656, 2018.
Maximilian Krahn, Michele Sasdelli, Fengyi Yang, Vladislav Golyanik, Juho Kannala, Tat-Jun Chin, and Tolga Birdal. Projected stochastic gradient descent with quantum anncaled binary gradients. In 35th British Machine Vision Conference, pp. 1-13. BMVA Press, 2024.
Jianglin Lan, Yang Zheng, and Alessio Lomuscio. Tight neural network verification via semidefinite relaxations and linear reformulations. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36. pp. 7272-7280, 2022.
Fabian Latorre, Paul Rolland, and Volkan Cevher. Lipschitz constant estimation of neural networks via sparse polynomial optimization. In International Conference Learning Representations, 2020.
Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. ATT Labs [Online]. Available: http://yann.eccur wwt..e..co//eex///misss.. 2, 2010.
13

---

Published as a conference paper at ICLR 2025
Jachoon Lee, Yasaman Bahri, Roman Novak, Samuel S Schoenholz, Jeffrey Pennington, and Jascha Sohl-Dickstein. Deep neural networks as gaussian processes. International Conference on Learning Representations, 2018.
Jaehoon Lee, Samuel Schoenholz, Jeffrey Pennington, Ben Adlam, Lechao Xiao, Roman Novak, and Jascha Sohl-Dickstein. Finite versus infinite neural networks: an empirical study, Advances in Neural Information Processing Systems, 33:15156-1511 2020.
Eitan Levin, Joe Kileel, and Nicolas Boumal. The effect smooth parametrizations on nonconvex optimization landscapes. Mathematical Programming, pp. 1-49, 2024.
Roi Livni, Shai Shalev-Shwarzz and Ohad Shamir. On the computational efficiency of training neural networks. Advances in Neural Information Processing Systems, 27, 2014.
Volker Lohweg. Banknote Authentication [Dataset]. UCI Machine Learning Repository, 2012. DOI: http:://doo.org111.4442222
Anirudha Majumdar, Georgina Hall, and Amir Ali Ahmadi. Recent scalability improvements for semidefinite programming with applications in machine learning, control, and robotics. Annual Review of Control, Robotics, and Autonomous Systems, 3:331-360, 2020.
Alexander G de G Matthews, Mark Rowland, Jiri Hron, Richard E Turner, and Zoubin Ghahramani.
Gaussian process behaviour in wide deep neural networks. In International Conference on Learning Representations, 2018.
Hrushikesh Narhar Mhaskar. On the tractability of multivariate integration and approximation by neural networks. Journal of Complexity, 2014):561-590, 2004.
Radford M Neal. Bayesian Learning for Neural Networks, volume 118. Springer Science & Business Media, 2012.
Roman Novak, Lechao Xiao, Jaehoon Lee, Yasaman Bahri, Greg Yang. Jiri Hron, Daniel A Abolafia, Jeffrey Pennington, and Jascha Sohl-Dickstein. Bayesian deep convolutional networks with many channels are gaussian processes. In International Conference on Learning Representations, 2019.
Greg Ongic, Rebecca Willett, Daniel Soudry, and Nathan Srebro. A function space view of bounded norm infinite width relu nets: The multivariate case. arXiv preprint arXiv: 190001390 2019.
Brendan D'donoghue, Eric Chu, Neal Parikh, and Stephen Boyd. Conic optimization via operator splitting and homogeneous self-dual embedding. Journal of Optimization Theory and Applications, 169-1042-, 2016.
Rahul Parhi and Robert Nowak. Banach space representer theorems for neural networks and ridge splines. Journal of Machine Learning Research, 22(43):1-40, 2021.
Pablo A Parrilo. Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robust- ness and Optimization. California Institute of Technology, 2000.
Patricia Pauli, Anne Koch, Julian Berberich, Paul Kohler, and Frank Allgöwer. Training robust neural networks using lipschitz bounds. JEEE Control Systems Letters, 6:121-126, 2021.
Patricia Pauli, Niklas Funcke, Dennis Gramlich, Mohamed Amine Msalmi, and Frank Allgöwer. Neural network training under semidefinite constraints. In 2022 IEEE 61st Conference on Decision and Control (CDC), pp. 2731-2736. IEEE, 2022.
Patricia Pauli, Dennis Gramlich, and Frank Allgöwer. Lipschitz constant estimation for Id convolu- tional neural networks. In Learning for Dynamics and Control Conference. PMLR, 2023.
Mert Pilanci and Tolga Ergen. Neural networks are convex regularizers: Exact polynomial-time
convex optimization formulations for two-layer networks. In International Conference on Machine Learning, pp. 7695-7705. PMLR, 2020.
Janez Povh and Franz Rendl. A copositive programming approach to graph partitioning. SIAM Journal Optimization, 18(1):2232441, 2007.
14

---

Published as a conference paper at ICLR 2025
Janez Povh and Franz Rendl. Copositive and semidefinite relaxations of the quadratic assignment problem. Discrete Optimization, 6(3):231-241, 2009.
Aditi Raghunathan, Jacob Steinhardt, and Percy S Liang. Semidefinite relaxations for certifying robustness to adversarial examples. Advances Neural Information Processing Systems, 31, 2018.
Max Revay, Ruigang Wang, and Ian R Manchester. convex parameterization of robust recurrent neural networks. IEEE Control Systems Letters, 5(4)) 1368, 2020.
Arda Sahiner, Tolga Ergen, John 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.
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 International Conference Machine Learning, pp. 19050-19088. PMLR, 2022.
Arda Sahiner, Tolga Ergen, Batu Ozturkler, John M Pauly, Morteza Mardani, and Mert Pilanci. Scaling convex neural networks with burer-monteiro factorization. In International Conference on Learning Representations, 2024.
Pedro Savarese, Itay Evron, Daniel Soudry, and Nathan Srebro. How do infinite width bounded norm networks look in function space? In Conference on Learning Theory, pp. 2667-2690. PMLR, 2019.
Joseph Shenouda, Rahul Parhi, Kangwook Lee, and Robert D Nowak. Variation spaces for multi- output neural networks: Insights on multi-task learning and network compression. Journal of Machine Learning Research, 25(231):1 2024.
Vincent G Sigillito, Simon P Wing. Larrie V Hutton, and Kile B Baker. Ionosphere [Dataset]. UCI Machine Learning Repository, 1989. DOI: http:://oo.og/122233/55000
Jack W Smith, James E Everhart, WC Dickson, William C Knowler, and Robert Scott Johannes. Using the adap learning algorithm to forecast the onset of diabetes mellitus. In Proceedings of the Annual Symposium Computer Application in Medical Care, pp. 261. American Medical Informatics Association, 1988.
Lieven Vandenberghe and Stephen Boyd. Semidefinite programming. SIAM Review, 38(1), 1996.
Irene Waldspurger and Alden Waters. Rank optimality for the borer-monteiro factorization. SIAM Journal on Optimization, 3077:2277- 2020.
Yifei Wang, Sungyoon Kim, Paul Chu, Indu Subramaniam, and Mert Pilanci. Randomized geometric algebra methods for convex neural networks. arXiv preprint Ttt::2006022800 2024.
Changqing Xu. Completely positive matrices. Linear Algebra and its Applications, 379, 2004.
Greg Yang. Scaling limits of wide neural networks with weight sharing: Gaussian process behavior, gradient independence, and neural tangent kernel derivation. arXiv preprint 1902.4490000 2019.
He Yin, Peter Seiler, Ming Jin, and Murat Arcak. Imitation learning with stability and safety guarantees. JEEE Control Systems Letters, 6:409 2021.
Alp Yurtsever, Varun Mangalick, and Suvrit Sra. Three operator splitting with nonconvex loss function. In International Conference on Machine Learning, pp. 12267-12277. PMLR, 2021a.
Alp Yurtsever, Joel A Tropp. Olivier Fercoq, Madeleine Udell, and Volkan Cevher. Scalable semidefinite programming. SIAM Journal on Mathematics of Data Science, 3(1):171-200, 2021b.
Alp Yurtsever, Tolga Birdal, and Vladislav Golyanik. Q-fw: A hybrid classical-quantum frank-wolfe for quadratic binary optimization. In European Conference Computer Vision. Springer, 2022.
Chiyuan Zhang, Samy Bengio, Moritz, Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3), 2021.
Richard Zhang, On the tightness of semidefinite relaxations for certifying robustness to adversarial examples. Advances in Neural Information Processing Systems, 33:3808-383 -8200, 2020.
15

---

Published as a conference paper at ICLR 2025
APPENDIX
We will first provide additional discussions before moving onto the proofs and additional experiments.
A DISCUSSIONS
On the contributions to theoretical understanding of neural networks. Convex formulations of neural networks can offer significant benefits in advancing our understanding of deep networks. We now provide a brief exposition and perspective on this:
Interpretability. Convex formulations are essential in converting pesky non-convex landscapes into interpretable ones. By doing so, they provide a clearer view of the solution space, revealing its geometric structure, and help identify properties of optimal solutions without getting trapped in suboptimal configurations.
Rigorous analysis. They pave the way for a rigorous theoretical analysis, including guarantees of convergence, uniqueness, and stability of solutions. This is in contrast to traditional training where guarantees are often limited or conditional on specific initialization schemes or overparameteriza- tion. We leave such analysis for future work.
lifting of data affects separability and decision boundaries can offer insights into how neural networks learn representations and resolve ambiguities in the data.
Lifting. Thanks to our exact co- co-positive formulation, studying how high-dimensin
A holistic learning theory. Bridging the gaps between optimization, geometry, and learning theory is fundamental to develop a modern theory for deep networks. This is what we precisely contribute towards with our theoretical formulation.
In the light of these, one particularly compelling avenue for future work involves leveraging our convex formulation to study generalization. Let elaborate on this. Characterizing the loss landscape of neural networks is crucial to understanding the capacity and limitations of deep learning. Generalizing solutions are known to reside in the wide minima of the loss landscape (Hochreiter & Schmidhuber 1997). This gives a relationship between the generalization error and the location of critical points. For our lifted convex formulations, the critical points are readily identifiable and can be mapped back to the non-convex landscape of the original problem through smooth parameterizations as demonstrated by (Levin al., 2024). By characterizing the local convexity of these points, we can potentially determine which solutions generalize better. While we have not yet investigated this, we plan to make such connections clearer in the future, where we further like to investigate the link between our formulation and the training dynamics (Andreeva et al. 2024 Birdal et al.) 1b2
On another frontier, the exact CP-NN formulation, combined with an analog of the results by Waldspurger and Waters the tightness of the Pataki-Barvinok (PB) bound for factorization rank in CP-NN formulations, could provide insights into the minimal width required for ReLU neural networks to succeed (Waldspurger & Waters 2020 Endor & Waldspurger 2024). Specifically, these works studied the MaxCut SDP and its factorized (non-convex) formulation. It is well-established that the factorized (non-convex) problem does not exhibit spurious local minima when the factorization rank exceeds the PB bound, which scales as ((vT), where n is the number of vertices (number of constraints, for a more general SDP template). Recently, same authors demonstrated that the PB bound is tight, meaning that even if the original SDP problem has a unique rank-1 I solution, the factorized (non-convex) problem can fail unless the factorization rank greater than the PB bound. This result provides critical guidance for selecting the rank in matrix factorization problems.
On NTK, NNGP and SGD. NNGP models the prior predictive distribution of an untrained neural network in the infinite-width limit, while NTK captures the training dynamics of gradient descent under similar assumptions. Our formulation differs significantly from NTK and NNGP, and does not share the same constraints. Unlike NTK and NNGP, our convex formulation is exact and applies to both finite and infinite-width regimes as long as the critical-width threshold is satisfied. Additionally, our method is not dependent on initialization. Any empirical inexactness arises solely from the relaxation and rounding processes, which do not undermine the theoretical validity of what we present, even if the computation is Na-hard.
Neither NTK, NNGP or our work is equivalent to SGD. While NTK can approximate SGD dynamics under specific overparameterized conditions, this correspondence is not universal and relies several assumptions. Importantly, as stated in the main paper, we use SGD with a hidden layer of 300 neurons in our experiments. Under these conditions, do not expect SGD to align with NTK.
16

---

Published as a conference paper at ICLR 2025
On the losses and the lower bounds. SDP-NN is a relaxation of the original problem, meaning it provides a lower bound on the objective. Therefore, its loss value is not directly comparable to SGD, which provides an upper bound by finding a feasible (but possibly suboptimal) solution. The lower loss for SDP-NN does not mean it performs better in the traditional sense, but rather indicates the quality of the relaxation. To evaluate the relationship between the two, we computed the approximation ratio (AR) in the main paper, quantifying how close the solution obtained by SGD is to the lower bound provided by SDP-NN. It is important to see that this is not a limitation of our method but stems from the nature of the problem the global solution of the training being unavailable.
Let us elaborate on that a little. Specifically. the exact approximation ratio defined as: Aeexact F / F", where F relaxed denotes the relaxed solution. However, since we do not know the true global minimum F", we instead compute the empirical AR, which provides only a lower bound on how well the SDP-NN relaxation captures the training problem: AR = F relaxed/ SGD. Here, FEGD corresponds to the local minimum found by SGD, and because F'GDD 2 F., we ensure that AR S ARexactt This guarantees that the reported AR provides a lower bound on the actual approximation ratio.
On rounding. Although our rounding step lacks convergence guarantees, as noted in Remark 3 serves as a valuable tool for validating our SDP-NN relaxation. Despite the heuristic nature of rounding, the ability to extract the trained weights of successful neural network demonstrates that the SDP-NN solution contains the necessary information. It is important to emphasize that the rounding step is not integral to the theoretical contributions of the proposed framework and is used solely for empirical evaluations. It is possible to leverage other rounding mechanisms and we leave it as a future study determine the optimal choice.
B PROOF OF THEOREM
Our formulation in Theorem I jinvolvss (p p) matrix decision variable A E PSD, which contains (q x q) principal submatrix PAPT E CP, where P = [ 1998 0gx(p-9: is the row-selection operator. The following lemma plays a crucial role in our analysis, in showing that there exists a finite critical width for two-layer ReLU network, beyond which increasing the number of hidden neurons does not improve the network's 's expressive power.
Lemma 2. Let A E R be a positive semidefinite matrix of rank k. with completely positive principal submatrix A 12989 of Ca-rank K. Without loss of generality, we assume A is the leading principal submatrix of A given by A = PAP with P [Ixxq 0px(r-n] Then, A can be
decomposed
R
A = E such that R and PX E R
(7)
j=1
for some R S max,k, K). As an immediate corollary, for any (p p) PSD matrix with (q X q) dimensional CP submatrix (without any restriction on their rank or CP-rank), we have < max (p. R. where Ry is the maximal CP-rank Rg == + 1)/2 1.
We will use the following result (see Lemma in Xu 2004)) in the proof of Lemma? 2
Fact Ifa PSD matrix A E Rxx admits two distinct factorizations, A CCT and A DD where C.D R then we can find an orthogonal matrix Q E N such that D = CQ
N
Proof of Fact Let G, E N and d; E N be the ith rows of C and D, respectively. Since {c and {d:}a span the same subspace, there exists linear transformation Q mapping span(c...... C,) to span .i.....d dm) such that d, = Q,Q for each = 1,..., n. By construc- tion, we have dd) (c,Q. c2 = (c,, cy), so Q preserves inner products on this subspace. Therefore, by extending Q to all of N we obtain orthogonal matrix.
Proof of Lemma 2 For the PSD matrix A and any non-negative integer R 2 k, we have a factoriza- tion of the form columns of B are not required to be linearly independent. Similarly, for the CP matrix A, we have a factorization Ä = DDT, where D E R for any R 2 K. As before, this factorization is not necessarily unique, and the columns of D need not be linearly independent.
BB" T, where B E IR R. This factorization is not necessarily unique, and the
17

---

Published as a conference paper at ICLR 2025
Consider these factorizations with R = max K}. Define C as the first g of B, given by C- CB We have À CC Then, by Fact 1 since any CP matrix is also PSD, there exists an orthogonal matrix Q E R such that D = CQ. Finally, let us define E = BQ. It is easy to verify that EE A, and PE D is entrywise non-negative. Hence, if we set w equal to the jth column of E, we obtain the desired decomposition.
The following lemma will be used to handle the non non-convexity introduced by ReLU activation:
Lemma 3. For real-valued vector â E TR" and non-negative real-valued vectors a, β RC with (x)- and B a ōτ, the following conditions are equivalent:
a (a)+
if and only if trace(a;31) 0.
(8)
Proof of Lemma 3) First, observe that trace(a.3T) tracelB3 a) = B a -= a,
Assume that the left-hand side in Eq. (8) (8) holds. Note that a represents the positive part of  then 33 is the negative part. Consequently, for each index i, either or B3 is zero, hence trace(o;f3
0.
Now, suppose that the right-hand side in Eq. (8) holds. Given that the elements of a and /3 are non-negative, we have (raco(a,3" 0 if and only if a;,3; = ag â;) = 0 for all i = -,, -....., This implies that a; > 0, then å; = oss. Otherwise, if ax = O, we have d; = Os - 3 S 0. Thus, we conclude that (6))..
Proof of Theorem
We start by rewriting NN-Train) in the constrained form as
min "yER" my ER" 0j oy ER"
Eajy Y
(1/5 112 110)112)
2
==1
s.t. åj Xuj and 0j (az)+ for j = 1,...,,7 m.
We introduce non-negative variables 3, == a &j. As both aj and B3 are non-negative valued, it be shown that Ox- (ar)+ + if and only if trace(a,,3) constraints in Eq. (9) can be equivalently rewritten in terms of a; and Bj as:
O, see see Lemma 3 As result, the
Bj Bj E RT, (race(a,,3)) O, and Xu; aj + Bj Onx1, for j j= m. (10)
The quadratic terms in the objective function in Eq. (9) and the trace constraint in Eq. (10) introduce challenges due to non-convexity. We address this by lifting the problem into higher- dighes-dimensional space, introducing variables A3 Rº and Aj E RPxp, where p 2n c d:
ajj
AajaJ
A TT
Dajuj A
Aajo
Bj
A
A p
A A
x===
=
U
and
Ay==
Aujaj
Au,33
Aujuj
A u
such that A, =
Aoja7
A
Aoju]
A Y
Ug
(11)
This allows us to express the objective as a convex function of Ay:
EPA.P
P. P.
P. P.,
(12)
F
1=1
j=1
Similarly, we reformulate the constraints in Eq. (10) as
P PasA; 2 0, Irace(P.A,8)
0, and MXj = 0,x1,
for j= 11 1...,mm
(13)
So far, we have shown that NN- Nraina is equivalent to the following problem:
7 m
min A,ERP
Σ PaA PT
+
6 P + P. P.,
2
#=1
1=1
s.t.
for j 1...,,
INN-Trai-Liftoor
MA; = 0
trace P.A,Pa P. =0
A, = > and Pasdj 2 02nx1
18

---

Published as a conference paper at ICLR 2025
Next, we will show that CC--NN is also equivalent to NN- SAN-Train-Laee Life-L when m is sufficiently large. Since A PSD, it follows that trace(MAM)) = 0 and trace(Pa.AA) = is equivalent to
trace trace(Pa.P) PP.PP)) trace(MAM ) = 0. By Lemma 2 we can find a positive integer I such that any matrix PSD such that PasAPal as E CP can be factorized as
Σ j=1
for some X E IP such that Pasd, 2 02nx1
(14)
Given this decomposition, we write
R trace (acceMMM)).. = Σ
n Σ
trace [MA,A]M]
MM
(15)
j=1
Therefore,
= if and only if MX; = =0nx1 for all - I...,, R. Similarly,
R
R trace (PaAAA}PP) = Σ P.A)) 5=1
trace PaaAP = Σ ==1
(16)
Note that (Pad,, P3AS} 2 0 for j since both Pay, and PBd are non-negative valued. As a result, trace (P.AP if and only if trace Pa PP) (P.>,. P3Aş) = for all
j 1..... R. Therefore, the formulation in (C--NN) is equivalent the following:
R Σ j=1
2
R P P. P.P.,A)
min EyER
PoA, P. Y
==1
s.t.
for j = :il==...... 1,...,R. R:
(17)
MXj = -0,x1
trace PPAc 00
A, = 2,21 and Pasdj 2 02xx1
This concludes the proof.
C PROOF OF THEOREM 2
We first introduce the following lemmas that will be required for stating the proof Theorem 2
Lemma 4. Let E IRPx be a positive semidefinite matrix of rank k, with a completely positive principal submatrix E R2a8 of CP-rank K. Without loss of generality, we assume A is the leading principal submatrix of & given by = PAP with P = [Lxx O 0gx(p-a)]- Then, there exists probability measure v and a corresponding random variable such that A can be decomposed as
= E
XA dxT).
(18)
JRP
such that X E IpP and PA 2 a.s. with respect to
Proof of Lemma 4
Let define the set θ as follows:
e = {A RPxP A E PSD, PAPT e CP}.
(19)
By Lemma we can find a positive integer It such that any matrix W E O can be factorized as
A
Σ A for some A R such that PA 2
(20)
19

---

Published as a conference paper at ICLR 2025
Thus, by performing scaling: X σ,A9 for some oj [0, 1] such that Σ 03 equivalently express O as follows:
1, we
R Σ
PA 20, 2, Vj = l.... R. and Σ
jj
j=1
(21)
We also define the set I as follows:
{ AA (2 is probability measure over X, PA 2 0 a.s. with respect to
(22)
is clear that S r, because any element of θ, expressed as Σイ= of can be represented
by the measure プラ= x where ودرY is the Dirac delta measure centered at > The Dirac delta measure o has support the point 2, assigning probability 1 to sets containing x and otherwise.
To prove the opposite direction, that - O, we define an indicator function Ie(+) given by
(0 if
Ie(A) = too if o O
(23)
Since θ is closed convex set, it is clear that Te is a closed convex function.
Let A J2 AAT dA() for some probability measure v. Applying Jensen's 's inequality gives the following:
Ie(A) To (Je,, AA AATdo(s)) $ Ie(AAT)au(A 0,
(24)
so A E θ. This completes the proof.
We recall the following standard result from measure theory without proof, as it will be used in the subsequent analysis:
Fact 2. Let f be absolutely integrable function and be a measure defined the measure space (R",B) . If 2 0 almost surely, then Sgr (x))dv(x) = if and only if = almost surely.
Proof of Theorem 2
We begin by rewriting NNj Train) in constrained form:
[0.1] | su T duluu, 1) Y
+ +2 nuxx (1] + ++++|llli [ll
min viBetc
(25)
s.t.
8(u, v) = Xu
s(u, v) ($(u, 2))+
We introduce non-negative variables a(u, v), B(u v) En that splits and follows: a(u, u, v) = s(u, v) and Buu v) = su, v) 8( uu, v)
(26)
For the sake of brevity, will the following shorthand notation: ar u, v) and B(u, v). Using the equivalence described in Lemma 3, we can reformulate Eq. (25) as follows:
//
min w:
xx cooTue(,, v) -Y + (1/[112 (1
RdxR=
J
F
(27)
s.t.
Xu a a + 3= 0ax1
diag(a
0nx1-
Let v(u, v) be probability measure defined on the support of the variables and v. Then v(u, v)
represents a feasible solution to (Nai-Train). Define the random vector À == X(u.v) E R with p 2n dl À A(u,
a
B u. Also, let A [A where
20

---

Published as a conference paper at ICLR 2025
the expectation is with respect to the probability measure v(u, v). We represent the objective function in Eq. (27) follows:
|x - -1 + "T,uuu' +w0 bo "),
(28)
or equivalently, in terms of A, as:
P.AP. Y 7 PPP P
(29)
which is exactly the objective function in (CP-NN) Then, similar the proof of Theeremm
I we can reformulate the constraints Eqq. (27) as
Pas 02 (PaA, PąA) =0, 0, and MX = 0xx1-
(30)
Next, we will show that we can replace these with
trace( MAM 0, trace( PaAP)) = 0, A E PSD, and PasAPa CP,
(31)
which is exactly the feasible set of CP-NN
By Lemma 4]
find probability measure and corresponding random variable À such that any matrix E PPD such that PasAPas E CP can be factorized as
= Ex
XA AATd((A)
such that Pas 2 021x1 a.s. with respect to v.
(32)
JRP
Given this decomposition, we can show that trace (MAM = 0 if and only if MA = -Onx a.s., by using Fact
since
trace MAX M du(A) / JEP
trace MAM
|| du(A).
(33)
JKP
Similarly, we can show that traco P...PPPPP..... if and only (PaA, P3A) a.s., since
trace (PAAP = JPP trace (Pace(PaAATTo Pa
(Pa), (PAd,
(34)
and (P.A, P3A) > a.s. since P. > 0nx1 and P3d 2 0nx1 a.s. by Eq. (32) Therefore, the constraints in Eq. (3ply those Fg.. (31) and the constraints in (31) imply l.q. (30)almost
surely. However, since the objective in Eq. (29) depends only A = E, AX and sets of measure zero do not affect A, we can omit the almost surely condition on the constraints without affecting the solution.
D INTERPRETATION OF THE SOLUTION TO CP-NN
The solution to (P-NN) be interpreted
matrix the weights and activations with respect to the representing measure for the IWNN. Based on the factorization in En|Eq. (32) the solution to (Cr-NN) is EyA ] for some measure and corresponding random variable A:
Taa
a
acu
Ba
33u
3v
A E,
(35)
ua
u
uu
uv
va
vu
vo
Suppose solve CP-NN) to obtain the solution A and consider the submatrix E,, [y(uu"] J. Using this,
we can compute the expected kernel matrix K[X,, X,] over the measure v, where Xo R and X, 1 xd are two input datasets of size 7hp and 71,, K[X,, X1] X JXx (Xx))(XX J]. It is thus possible to extract the expected kernel matrix of the infinite-width (or wide) neural network from the solution of (CP-NN), which stores the learned features.
21

---

Published as a conference paper at ICLR 2025
E ADDITIONAL DETAILS ON NUMERICAL EXPERIMENTS
We used SGD with small step sizes and trained until convergence. We observed that this approach provides better approximation of the global solution. Based this observation, we tuned the learning rate (LR) and the number of iterations for each dataset as:
Random: Initial LR 10-5; 9; of iterations 500K.
Spiral: Initial LR 10 10:3; of iterations = 8K.
Iris: Initial LR 10 6; # of iterations 2.M.
tonosphere: Initial LR = 10-6; # of iterations = 2M for y 0.1 and 5M for 0.01.
Pima Indians Diabetes: Initial LR = 10-3; 88 # of iterations 5M for = 0.1 and 6M for y 0.01.
Bank Notes Authentication: Initial LR 10-6; # of iterations = 5M.
MNIST: Initial LR 10 10-"; # of iterations = 8M.
The SGD training curves for Random and Spiral with varying number of hidden neurons, ranging from to 300, are shown Figure 2
10"
10a
10a
10a
Objective Loss
Objective Loss
102
16a
10a
16P
10-1
SGD 1.0-SBillie Haddez Sernm
SGD 200 Hiddin Neuoee
SGD Eiddez Nemro
SCD Hidden Neuree
10
10
liikknn Nommee
10
10
Iteration
Iteration
(a) Random Dataset, 7 0.1.
(b) Random Dataset, 7 = 0.01.
4 10
3. 10'
101
2. 10
Objective Loss
10a
Objective
101
SGID
Riiden Nearons
SCD 200 Hidden Neannn
SGD Hidden Neunon Ehadin Neanoe
SCD 203 Hidden Naunoe
SGD Elidde Vaamoe
SC31 900 thokkn Neanos
SCD 900 Iilckon Naunei
10
10
10
10a
Beration
Ieration
(c) Spiral Dataset, 0.1.
(d) Spiral Dataset, 0.01.
Figure 2: Objective value (training loss) for Random and Spiral datasets trained with SGD using different numbers of hidden neurons. The dashed line indicates the lower bound obtained from solving SDP-NN with the interior point method as a reference.
22

---

Published as a conference paper at ICLR 2025
Comparison with other convex relaxations. We compared our SDP-NN approach against two convex formulations proposed in (Shhine et al. 2021). The first the convex semi-infinite bi-dual formulation (Equation (14) in their paper), solved using Trank-Wolffe type algorithm, which refer to as 'Sahiner FW. The second is their copositive relaxation the problem (Equation (19) in their paper), which we refer as 'Sahiner CP,' solved with CVXPY. We used their publicly available code for these methods. The comparison was conducted on the Random dataset for regression and the Spiral dataset for classification. The results are shown in Table for the regression and Table for the classification. Since the provided implementation of "Sahiner CP' was designed specifically for classification, only 'Sahiner FW" included in Table
It is important to note that the training objectives obtained by these methods are not directly compara- ble SDP-NN. In particular, both 'Sahiner FW' and 'Sahiner CP' require enumerating all possible sign patterns for given network width (300) hidden neurons in this experiment) and training dataset. As result, they approximate the training solution with 300 hidden neurons accurately, as seen in the tables, with slightly higher objective values than SGD, In contrast, SDP-NN is relaxation for an unnfinnte-width network (and, as can be easily verified, the critical width R in these examples can be larger than 300), hence provides a lower-bound noting that the epigraph level-set parameter t Sahiner FW method, which theoretically should be optimized using bisection, is instead directly set using the SGD solution for simplicity. Including bisection would further increase the runtime for Sahiner FW.
the global optimal value. It also worth
Table 4: Comparison of convex formulations for regression with the Random dataset.
Algorithm
7 0.1
Y 0.01
Train Obj.
Std Dev.
Time (s)
Train Obj.
Std Dev.
Time (s)
SDP-NN
7.275
0.976
11.35
0.755
0.099
12.47
Sahiner FW
8.213
1.083
1341.8
1.099
0.159
1024.8
SGD
8.090
1.041
0.936
0.116
*Sahiner FW and SGD are applied with 300 hidden neurons.
Train objective and time are averaged over 100 random dataset.
Table Comparison convex formulations for classification with the Spiral dataset.
Algorithm
7 0.1
7
0.01
Train Obj.
Time (s)
Train Obj.
Time (s)
SDP-NN
16.235
1724.05
11.658
1062.81
Sahiner FW
16.593
1885.60
15.184
1911.77
Sahiner CP
16.660 16.593
4.75
15.853
5.07
SGD
15.159
*Sahiner FW, Sahiner CP and SGD are applied with 300 hidden neurons.
23


Reviews:
[{"review_id": "10PwT1VJyG", "reviewer": "Reviewer_FSdn", "summary": "In this paper, the authors propose a novel model for infinite-width neural network training based on copositive programming. In theorems 1 and 2, the authors carefully demonstrate that the training of an RELU network of sufficient width using the MSE loss is equivalent to a certain convex copositive program. Next, the authors derive a semidefinite relaxation of the proposed copositive program and an associated rounding scheme to recover weights from the solution to the SDP. On a variety of synthetic and small real datasets, the authors demonstrate that their method recovers neural network weights that achieve smaller MSE (table 2) compared to networks trained via SGD and competitive predictive performance compared to NTK-based kernel methods.", "questions": "- can the authors comment on the runtime of solving the SDP?\n- can the authors provide additional discussion about what kinds of insights can be gained by applying the proposed framework?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This is an interesting paper that derives an equivalence between infinite-width RELU network training and solving a certain convex copositive program. This work contributes to the growing literature relating neural network training and convex optimization. The empirical results are also promising. Overall, I think this is an interesting work that provides valuable insight.", "weaknesses": "The empirical results seem somewhat weak to me. The authors acknowledge the similarity of their work to earlier work relating copositive programming and RELU network training. Although the existing methods make additional assumptions on the data distribution, a numerical comparison to prior work (e.g. the approximation ratio) would be beneficial in understanding how the proposed framework compares to earlier work in practice or further discussion on the applications of their technique.", "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": "", "extra_scores": {}}, {"review_id": "6nnZG3rHq7", "reviewer": "Reviewer_py4d", "summary": "The paper investigates the training of shallow NN using convex optimization techinques.\nIt provides a brief background on Semi-Definite programming and Copositive Programming. Then it provides a formulation for the training of a NN as a CP problem (for a sufficiently wide 2-layer net with ReLU activations), which is then relaxed to make it computationally feasible.\nThe tightness of the relaxation is evaluated empirically.", "questions": "I have some concerns on the empirical evaluation. MSE is not a suitable loss function for classification problems, a selection of regression tasks would have been more representative. Regardless, the hyperparameters chosen for the SGD baseline are quite strange (especially for PIMA Indians). Finally, the dataset is divided in train-test split, this penalizes models that overfit on the training data. However, if the goal is to evaluate how well a model is solving the given optimization problem, it should be evaluated on the training set.\n\nIn most cases, the addition of a bias term in the linear projections significantly improves performance, especially for 2-layer ReLU networks. In fact, running the proposed SGD baselines with the addition of a bias term improves performance across the board (gaining up to +15% accuracy). Given this, the lack of a bias term and its implications should probably be noted in the text.\n\nI don't understand the results in Table 2. The metric is the loss, lower mean better, i.e. SDP-NN significantly improves on SDG. However the way the approximation ratio is computed and is presented in the main text implies that the SDP-NN performs worse than SGD.\n\nSome equation are labelled instead of being numbered. I personally find this beaks the flow of the main text as it is not immediately clear that it is a reference to an equation (as most people are used to see numbers). If you want to refer to some equation by a meaningful name, you can use the name in the definition, i.e. instead of \"... in (CP-NN)\" consider using something like \"... in the CP-formulation (equation 2)\".\nIf you decide to keep the labels, at least try to use them to refer to the equations only, not to the concepts they are tied to. For instance in \"While the case of countably infinite number of hidden neurons – represented by an infinite sum in (NN) – is captured as a special case of (NN∫) with a discrete probability measure, the (NN∫) model ...\" you use (NN∫) to denote both the infinite width model concept as a whole, and its equation.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper is clear, and reads well.\nThe supplementary material provides the code to reproduce the results.\nSection 2 provides a complete yet brief background on the relevant optimization topics and concepts.", "weaknesses": "The paper does not consider bias terms in the linear layers.\nThe tightness of the proposed relaxation is evaluated only empirically.\nThere is no convergence guarantee for the TOS rounding step.\nThe rounding step is performed using the critical width, however in practice this is unfeasible.\nTime complexity is not considered in the evaluations.\nThe empirical evaluation is performed on classification tasks, using L2 loss.", "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": "", "extra_scores": {}}, {"review_id": "79SerQJw8c", "reviewer": "Reviewer_T7kD", "summary": "This paper proposes a novel training method for two-layer neural networks based on a formulation of a convex completely positive program. The authors also propose a semidefinite relaxation which ensures that the problem can be solved in polynomial time. Experiments on several simple synthetic and real datasets are conducted to demonstrate the performance of the proposed method in comparison to the Neural Network Gaussian Process and Neural Tangent Kernel methods.", "questions": "I suggest that the authors should address the weaknesses point out above.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The idea of the proposed method based on convex completely positive program and semidefinite relaxation is interesting. \n\n- The presentation of the paper is fairly clear.", "weaknesses": "- The proposed method is only for training wide two-layer neural networks with ReLU activation function. It seems that extending the method to deeper networks is non-trivial, which limits the practical value of the proposed method. It would be beneficial if the authors could discuss the possibility to implement the proposed methods to train modern deep neural networks.\n\n- As the authors have commented, the problem (Cp-Nn) is NP-hard due to the complete positivity constraint, and as far as I can see, the corresponding (Sdp-Nn) is not guaranteed to find the actual solution to (Cp-Nn). It would be helpful if the authors can add discussions about this point.\n\n- To my knowledge, the Neural Network Gaussian Process and Neural Tangent Kernel methods are also settings (mainly about parameter/initialization scale and network width) under which SGD training of neural networks is almost equivalent to a convex optimization procedure. It is widely agreed that NNGP and NTK cannot fully explain the success of deep learning. These models only characterize scenarios where the obtained neural networks have weights very close to their random initialization. As a result, they fail to explain how deep networks learn effective feature representations. Therefore, even if the proposed method achieves competitive results compared with NNGP and NTK, it does not necessarily mean that the proposed method can compete with actual neural network training beyond the “NTK regime”.\n\n- The experiments are not representative enough. All datasets considered in this paper are very small datasets, and the performance of the proposed method on these datasets are insufficient to demonstrate its advantage. I think the authors should at least include results on datasets such as MNIST and CIFAR-10. \n\n- The experiment setup requires some clarification. As mentioned above, NNGP and NTK represent specific regimes in which SGD training of neural networks may fall [1,2,3,4]. Therefore, it is not reasonable to directly list “SGD”, “NNGP”, “NTK” as different training methods. Discussion how the SGD setting differs from NNGP and NTK and why they are not equivalent according to [1,2,3,4] is necessary to explain the experiment setting clearly.\n\n- The authors should also discuss the relationship between the proposed method and the study in [5].\n\n\n[1] Simon Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. ICLR 2019.\n\n[2] Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over-parameterization. ICML 2019.\n\n[3] Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. ICML 2019.\n\n[4] Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Gradient descent optimizes over-parameterized deep ReLU networks.\" Machine learning 2020\n\n[5] Cong Fang, Yihong Gu, Weizhong Zhang, and Tong Zhang. Convex formulation of overparameterized deep neural networks. IEEE Transactions on Information Theory 2022", "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": "", "extra_scores": {}}, {"review_id": "AZ0leklvJK", "reviewer": "Reviewer_9js6", "summary": "The paper studies 2-layer ReLU neural networks trained with MSE loss and $l_2$ regularization. The main contribution of the paper is in showing that beyond certain critical width (of at most quadratic dependence on the number of samples), the standard optimization problem is equivalent to a convex problem over a matrix of quadratic number of parameters in number of samples and input/output dimensions. The optimal values of this problem match.\n\nThe equivalence further applies to infinite-width 2-layer ReLU networks with analogical loss function. The optimal solutions of the convex problem can be used to construct optimal solutions of the infinite-width problem. \n\nFinally, the paper proposes a computationally efficient algorithm that approximates the convex, yet copositive program. This new, semidefinite program is solvable in polynomial time and the solution of the original problem can be recovered from the solution of the SDP problem by a rounding scheme described in the paper, using existing approaches such as the three-operator splitting method. \n\nThe authors then evaluate this method as well as the tightness of the SDP relaxation on some tabular datasets of small size, demonstrating (within these datasets) that the SDP relaxation is rather tight and the practical optimization algorithm works comparably to known optimization methods, despite using number of parameters that is not theoretically guaranteed to work.", "questions": "- Q1: Do you expect Theorem 1 to be applicable in theoretical analyses of 2-layer NNs in different contexts? \n\n- Q2:  Assume an oracle would give us a solution to the CP-NN problem directly. What is the computational complexity of an algorithm that would recover a solution to the NN-TRAIN problem? \n\n- Q3: Regarding Theorem 2, are there solutions to the NN-integral-train that are not discrete? \n\n- Q4: What would be the training loss of the recovered NN-TRAIN solution in Table 2? I am asking to see how far off would the projection back into feasible set be from the actual solution to NN-TRAIN. \n\n- Q5: What makes the bank notes dataset so different from the others that your method is so significantly worse than all the others, while being pretty good on all the other datasets? \n\n**Summary:** Despite several flaws outlined above, I still think this paper meets acceptance threshold due to the novel, compact and parameter-light convex formulation of the 2-layer NN training which does not rely on enumerating all the activation patterns of the intermediate layer (as in the previous literature). This result is of theoretical interest and, though simple in nature, it is novel and insightful. Therefore, I recommend acceptance. However, I condition this opinion as well as the score on the satisfying discussion period.\n\n**After the rebuttal:** The authors satisfactorily answered my questions and discussed my concerns. I am keeping my original score.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- S1: The strongest part of the paper is, in my opinion, the theoretical contribution (Theorem 1). To the best of my knowledge, this convex formulation significantly improves the number of parameters (as a function of the number of samples and input/output dimension) in the convex program from high-degree polynomial [1], to quadratic. The price the authors pay is the minimal width required to achieve this equivalence, which is also quadratic in the number of samples, as opposed to linear in previous works. Nevertheless, this neat and parameter-light reformulation is of independent theoretical interest and I believe it can be used as a tool in theoretical analyses of 2-layer NNs outside the scope of this paper. I checked the proof of the result and everything seems to be all right with only a small issue that I will discuss in typos. \n\n- S2: The paper is overall well written, clear and interesting. \n\n[1] Sahiner, Arda, et al. \"Vector-output relu neural network problems are copositive programs: Convex analysis of two layer networks and polynomial-time algorithms.\" arXiv preprint arXiv:2012.13329 (2020).", "weaknesses": "- W1: The practical contribution of this paper is limited. Even if we ignored the fact that the practical algorithm introduced in this paper is only suitable to train 2-layer neural networks, the main issue remains -- there already are algorithms in the literature that can obtain approximate solutions of the convex re-formulations using quadratic time per-iteration in the number of samples (see for instance [1]). Moreover, the experimental evaluation is not very convincing. The tested datasets are very small so the results are not very convincing. It is known (both theoretically and empirically), that gradient-based methods work well also with widths linear in the number of samples (see for instance [2], which considers only marginally different setting). Whether your method works well with R constant (the linear dependence on $n$ already comes from lifting into the higher-dimensional space) or at least sub-quadratic in $n$ is questionable (and not addressed in the paper). Moreover, the performance is comparable with already existing and well-established optimization methods (as demonstrated in the paper). \n\n- W2: While it is written in the paper that the algorithm scales quadratically with the number of samples (which is true in the plain CP-NN formulation), recovering a solution to the original problem actually requires cubic number of parameters and thus also time. This can be seen in equation (3), where it is clear that already the dimension of the $\\lambda_j$ vectors scales with $n$ and $R$ scales quadratically with $n$, thus in total the dependence is cubic. Even if an oracle gave us *directly* a solution to CP-NN problem, recovering a solution to the original problem would still require $n^3$ number of parameters. \n\n- W3 (minor): The computational complexities of all the involved procedures should be explicitly discussed in the paper.\n\n**Small issues:**\n\n- Lemma 3 is wrong, the $w$ can have positive values where $\\hat W$ has negative values. A correct version of this lemma removes $\\lambda$ completely from the statement and replaces the $\\lambda$ in the if and only if statement with $w$. This would also be consistent with the later use of this lemma in the actual proof of Theorem 1. \n\n- Typo: line 176 you refer to Lemma 4 but should be Lemma 2. \n- Typo: In line 167 index should be also added to the $u, v$ variables. \n- Typo: across the entire proof of theorem 1 including the lemmas that precede it, you use $W$ and $\\Lambda$ supposedly to denote the same object. Please only use one of these (preferably $\\Lambda$).\n\n[1] Bai, Yatong, Tanmay Gautam, and Somayeh Sojoudi. \"Efficient global optimization of two-layer relu networks: Quadratic-time algorithms and adversarial training.\" SIAM Journal on Mathematics of Data Science 5.2 (2023): 446-474.\n\n[2] Bombari, Simone, Mohammad Hossein Amani, and Marco Mondelli. \"Memorization and optimization in deep neural networks with minimum over-parameterization.\" Advances in Neural Information Processing Systems 35 (2022): 7628-7640.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)