Scaling Convex Neural Networks with Burer-Monteiro Factorization
Authors: Arda Sahiner
Tolga Ergen
Batu Ozturkler
John M. Pauly
Morteza Mardani
Mert Pilanci
Venue: Submitted to ICLR 2023 (2023)
Keywords: burer-monteiro
convex optimization
neural networks
stationary points
global optima
relu activation

Abstract: Recently, it has been demonstrated that a wide variety of (non) linear two-layer neural networks (such as two-layer perceptrons, convolutional networks, and self-attention) can be posed as equivalent convex optimization problems, with an induced regularizer which encourages low rank. However, this regularizer becomes prohibitively expensive to compute at moderate scales, impeding training convex neural networks. To this end, we propose applying the Burer-Monteiro factorization to convex neural networks, which for the first time enables a Burer-Monteiro perspective on neural networks with non-linearities. This factorization leads to an equivalent yet computationally tractable non-convex alternative with no spurious local minima. We develop a novel relative optimality bound of stationary points of the Burer-Monteiro factorization, thereby providing verifiable conditions under which any stationary point is a global optimum. Further, for the first time, we show that linear self-attention with sufficiently many heads has no spurious local minima. Our experiments demonstrate the utility and implications of the novel relative optimality bound for stationary points of the Burer-Monteiro factorization. 

Under review as a conference paper at ICLR 2023
SCALING CONVEX NEURAL NETWORKS WITH BURER- MONTEIRO FACTORIZATION
Anonymous authors Paper under double-blind review
ABSTRACT
Recently, it has been demonstrated that the training problem for wide variety of (non) linear two-layer neural networks (such as two-layer perceptrons, convolu- tional networks, and self-attention) can be posed as equivalent convex optimization problems, with an induced regularizer which encourages low rank. However, this regularizer becomes prohibitively expensive compute at moderate scales, im- peding training convex neural networks. To this end, we propose applying the Burer-Monteiro factorization to convex neural networks, which for the first time enables a Burer-Monteiro perspective on neural networks with non-linearities. This factorization leads to an equivalent yet computationally tractable non-convex al- ternative with spurious local minima. We develop novel relative optimality bound of stationary points of the Burer-Montein factorization, thereby providing verifiable conditions under which any stationary point is a global optimum. Further, for the first time, we show that linear self- attentio with sufficiently many heads has spurious local minima. Our experiments demonstrate the implications of the relative optimality bound for stationary points of the Burer-Monteiro factorization.
INTRODUCTION
has been demonstrated that the training problem for (non-linear) two-layer neural networks are equivalent to convex programs (Pilanci & Ergen 2020 Ergen & Pilanci 2020 Sahiner et al.) 200Tbb Ergen et al. 202T; Sahiner et al.] [201T))) This has been observed for a variety of architectures, in- cluding multi-layer layer perceptrons (MLPs) (Pilanci & Ergen 2020 Sahiner et al. 2021b), convolutional neural networks (CNNs) (Ergen & Pilanci 2020; Sahiner et al.] (02Tc), and self-attention based transformers (Sahiner et al.) (2022). A major benefit of convex training of neural networks is that global optimality is guaranteed, which brings transparency to training neural networks.
The convex formulation of neural networks induces biases by regularization of the network weights. For linear activation, the convex model directly imposes nuclear-norm regularization which is well- known encourage low-rank solutions (Recht et al., 2010). For ReLU activation, however, the convex model induces a type of nuclear norm which promotes sparse factorization while the left factor is constrained to affine space (Sahiner et al. 2021b). This constrained nuclear-norm is NP-hard to compute. This impedes the utility of convex neural networks for ReLU activation.
To address this computational challenge, seek a method which (i) inherits the per-iteration complexity of non-convex training of neural network, and (ii) inherits the optimality guarantees and transparency of convex training. To find solution, we leverage the well-studied Murer-Monterio (BM) factorization (Burer & Monteiro 2003), which was originally proposed as heuristic method improve the complexity convex semi definief programs (SDPs).
BM has been applied as an efficient solution strategy for problems ranging from matrix factoriza- tion (Zheng Lafferty 2016 Park et al. 2017, Gi al.) 2017 Gillis (017)) to rank minimiza- tion (Mardani et 2013; Recht et al.]
et al. (017)) and matrix completion (Mardani) ct al. 2015 Ge et al. 2017). BM has also been used for over-simplified neural networks such as (Kawaguchi 2016 Haeffele & Vidal 2017 Du & Lee, 2018), where optimality conditions for local minima are provided. However, no work has deployed BM factorization for practical non-linear neural networks, and no guarantees
available about the optimality of stationary points. This is likely because BM theory is not applicable to the standard non-convex ReLU networks due to non-linearity between layer weights.

---

Under review as a conference paper at ICLR 2023
Thus, our focus in this work is to adapt BM for practical two-layer (non-linear) convex neural networks. We consider three common architectures, namely MLPs, CNNs, and self-attention networks. For these scenarios, points, which are easy and interpretable. In light of these conditions, we identify useful insights about the nature of neural networks contributing to optimality. In particular, we observe that for self-attention networks all local minima coincide with the global optima if there are sufficiently many heads. The optimality guarantees also provide useful algorithmic insights, allowing one to verify whether the -ight- first-order methods such as SGD achieve the global optimum for the non-convex training of neural networks. Our experiments with image classification task indicate that this BM factorization enables layerwise training of convex CNNs, which allows for convex networks for the first time to match the performance of multi-layer end-to-end trained non-convex CNNs.
develop verifiable relative optimality bounds for all local minima and stationary
1.1 CONTRIBUTIONS
All in all, our contributions are summarized as follows:
We propose the BM factorization for efficiently solving convex neural networks with ReLU activation for moderate and large scales. This is the first time BM theory has been applied to the non-linear neural network setting.
We derive novel bound the relative optimality of the stationary points of the BM factorization for neural networks.
Accordingly, we identify simple and verifiable conditions which guarantee a stationary point of the non-convex BM formulation achieves the global optimum of the convex neural network.
We yield basic insights into the fundamental nature of neural networks that contribute to optimality; e.g. that linear self-attention has spurious local minima if it has sufficiently many heads.
Our experiments verify the proposed relative optimality bound of stationary points from the BM factorization, and uncovers cases where SGD finds saddle points, even in two-layer neural networks.
1.2 RELATED WORK
Burer-Monteiro factorization. The Burer-Monteiro (BM) factorization was first introduced in (Burer & Monteiro 2003 2005). There has been long line of work studying the use of this factorization for solving SDPs (Boumal et al. 2016 Cifuentes
Moitra 2019 Waldspurger & Waters 2020; Erdogdu et al. (2021). In the rectangular matrix case, gradient descent converges to a global optimum of the matrix factorization problem with high probability for certain classes of matrices (Zheng & Lafferty (016). The BM factorization has been also studied in the rectangular case in more generic settings (Bach et al. 2008 Haeffele et al. 2014 Haeffele & Vidal 2017).
Nuclear norm and rank minimization. The ability of nuclear norm regularization to induce low rank has been studied extensively in compressed sensing (Candès & Rechi, 2009; Recht et al. 2010 Candès & Tao. 2010). BM factorization has been applied to scale up nuclear-norm minimization (Mardani et al. 2015 2013). It has also been deployed for low-rank matrix factorization (Cabral cct 2013 et al., 2017] Park et al.) 20177: Ge et al.) 2017). The results show that all second-order critical points of the BM factorization are global optima if certain qualification conditions are met.
SGD for non-convex neural networks. It has been shown that for over weerparameterized two-layer linear networks, all local minima are global minima (Kawaguchi (016). Accordingly, line of work has attempted to show that gradient descent or its modifications provably find local minima and escape saddle points (Ge et al., 2015 5 Lee et al.) 2016 Jin et al. 2017 Daneshmand et al.) 2018). However, these works assume Lipschitz gradients and Hessians of the non-convex objective, which is not typically satisfied. Another line of work shows that gradient descent converges to global optima for sufficiently highly preaterraeteri neural networks, with either the parameter count being high-order polynomial of the sample count (Du et al. 2018 2019; Arora et al. 2019), or the network architecture being simple (Du & Lee 2018). In practice it has been empirically observed that SGD)
2

---

Under review as a conference paper at ICLR 2023
converge local maxima, get stuck in saddle points (Du et al. 2017: Ziyin et al. 2021). For unregularized matrix factorization, it has also recently been shown that randomly initialized gradient descent BM factorization provably converges to global minima (Ye & Du 2021.
Convex neural networks. ReLU neural networks have equivalent convex programs for training. such networks with scalar outputs (Pilanci & Ergen 2020). vector-outputs (Sahiner al. 2021b) convolutional networks (Ergen & Pilanci] 2020 Sahiner et al. 2021c), polynomial-activaiee
networks 202T), Wasserstein GANs (Sahiner
(Bartan & Pilanci 202T), batch-norm based networks (Ergen
et al. 20221a, and self-attention networks (Sahiner et al. 2022). Despite efforts in developing efficient
solvers, convex networks are only effectively trainable at small scales (Bai et al. 2022] Mishkin et al.)
2022). Our novelty is to adapt BM factorization as fast and scalable solution for training convex networks, with simple, verifialle conditions for global optimality.
PRELIMINARIES
We denote (:)+ (0, the ReLU non-linearity. We superscripts, say A (krik)) to denote blocks of matrices, and brackets, say A 12]. to denote elements of matrices. We let be the vector of ones of appropriate size, and Bи be the unit H-norm ball, {u ||u]| S 1]. Unless otherwise stated, let I' be a convex, differentiable function. We use n to denote the number of samples, and to denote the output dimension of each network. All proofs are presented in the Appendix.
2.1 TWO-LAYER NEURAL NETWORKS CONVEX PROGRAMS
A line of work has demonstrated that two-layer neural networks are equivalent to convex optimization problems. We consider data matrix E Rnnd and consider two-layer o-activation network with e outputs, neurons, weight-decay parameter 3 > 0:
33 PMIL= = min ((W(W))) +
W1j
W2
1
(1)
WI W.ERoX
2
When is linear activation and 2 m" for some m I minfd, c), this problem is equivalent to (Rennie & Srebro 2005), Section 2.2)
PLMLP
min F(XZ) + *]||,
(2)
ZER
whereas for a ReLU activation and m 2 m for some unknown, problem-dependent mn < nc
(Sahiner al. 2021b), Thm. 3.1),
P
PRIME= = min F
+ D XZ,
Σ Z llx.k,
(3)
Zee j=1
j=1
k; (2D) I,
where (D = {diag [u 2 0}) u E Rd) enumerates the possible activation patterns
generated from X, and the number of such patterns satisfies P < 2r (((n1)) where rank X) (Stanley et al. [2004] PPllanci & Ergen 2020). The expression (3) also involves a constrained nuclear
norm expression, which is defined
Z | = min t s.t. Z E 120
C == conv Z uv
Ku 2 0, |ul/2 S 11/122 S 1}.
This norm a quasi-nuclear norm, which differs from the standard nuclear norm that the factoriza- tion upon which it relies imposes constraint its left factors. In convex ReLU neural networks, this norm enforces the existence of [ug, V&} such that = Σx u.Vi and D,XZ and penalizes Σx | I |l.. This norm is NP-hard to compute. variant these ReLU activations, called gated ReLU activations, achieves the piecewise linearity of ReLU activations without enforcing the constraints (Fiat et al. 2019). Specifically, the ReLU gates are fixed to some (h, } to form
VV
(XW1,) diag (1 (Xh; 0)) (Xw1)) D,Xw1j.
(5)

---

Under review as a conference paper at ICLR 2023
With gated ReLU activation, the equivalent convex program is given by (iishkin al. 2022) Thm. 2.2;
(Sahiner et al. 2022). e.q. (8))
min F POE D2 + ZjER
2 2 ll:
PGMLP
which thereby converts the constrained nuclear norm penalty standard nuclear norm penalty, thereby improving the complexity of the ReL.U network. In addition to the multi-layer perceptron (MLP) formulation, two-layer ReLu-activation convolutional neural networks (CNNs) with global average pooling have been demonstrated be equivalent to convex programs as well (Sahiner et al. 2021b
Ergen & Pilanci 2020 The non-convex formulation is given by
3 (X, W (X)
PRONN
min WiyER" w2y ER
F
W2j
W1y 11 + w[ 12.
2
where samples X, E KR are represented by patch matrices, which hold a convolutional patch of size h in each their K rows. In particular, each row of X; contains the data a convolutional kernel would perform an inner-produce with, and fi is the product of kernel dimensions while K is the number of patches each kernel passes over. It has been shown (Sahiner et al., 2021b) that as long 2 m" where m I nc, this is equivalent to convex program ((Sahiner
2021b). Cor. 5.1)
PRONN = min Σ
D
X, x
+
(8)
2jERaXe
1=1
==1
j=1
X1
K₁ = (2D; Ink X, X ==
X
( where (Dj}e- = {diag (1 2 0}): : u E and D E R Noting that S 2r c(n-1) and r S h, the only exponential dependence of P is on h, which is typically fixed. Lastly, we review existing convexity results for self-attention transformers (Sahiner et al. 2022). We have the following non-convex objective for single block of multi-head self-attention with heads, where X; E Raxd with s tokens and d features
3
PSA
min WijeRdad WayeRuxe
Σ
X W
X,W
W W1,112- + [2 1i,
(9)
2 j=1
for which a variety of objectives F can be posed, including classification (e.g. F incorporates global average pooling followed by -oftmax--ross-entrooy with labels) or denoising (e.g. is squared loss against a label matrix). In the linear activation case, as long as m 2 m², where m < min(dl de}. this is equivalent (Sahiiner et 2022). Thm. 3.1)
d
Pi.SA min Σ
ΣΣ
G. (XK,
(10)
ZER
k=1t=1
where G; : x G.lk, E and (k.0) E [dxx) are block matrices which form Z. A similar formulation can be posed for ReLU and Gated ReLU activations. In this work, we show that these network architectures amenable the BM factorization.
2.2 THE BURER-MONTEIRO FACTORIZATION
First proposed by Burer Monteiro 2003). the Burer-Monteiro (BM) factorization proposes to solve SDPs over some square matrix Q in terms of rectangular factors R where substituted by R.R.T. It was first demonstrated that solving over R. does not introduce spurious local minima, given rank(R) > rank(Q") for optimal solution to the original SDP Q" (Burer & Monteiro 2005). In general, we seek applications where we optimize over non-square matrix Z, i.c.
PCVx
min FZ))
(1I)
ZERaxc
4

---

Under review as a conference paper at ICLR 2023
for convex, differentiable function F. One may approach this by factoring Z = UVT, where U E Raxm V E R for some arbitrary choice m. Then, we have an equivalent non-convex
U
problem over R
for f(R) F(UV)):
V
PCVx min (RR. R UUT UV VUT VVTJ one may apply directly the result of Burer & Monteiro (2005) to conclude that as long as m 2 rank(Z*). all local minima of 12 are global minima of (11) (see Appendix A.I). A major issue with these results is that rank is not known priori. Naively, one may simply choose m 2 min(d, c} and be assured that m 2 rank (Z)) but this approach is not satisfactory if further mnder-paramettrization is desired. To address this issue, work from Bach et al. (2008) and Haeffele et al. (2014) demonstrates that all rank-deficient lo- cal minimizers of 12 achieve the global minimum PCvx x (under conditions, see Appendix A.2
(12)
Noting that (11) is convex over R.R.T
long line of work has analyzed the conditions where known non-convex optimization al- gorithms will converge to second-order critical points (local minima) (Ge et al. 2015 Jin et al. 2017] Daneshmand al. 2018). Under the assumption of bounded and its Hessian, second critical point can be found by noisy gradient descent (Ge et al.) 2013). or other second-order algorithms (Sun et al. 2015). Even vanilla gradient descent with random initialization has been demonstrated to almost surely converge to local minimum for f with Lipschitz gradient (Lee et al.) 2016). However, if the gradient of ff is not tipshitz-continuout descent will find second-order critical point of (12): one may encounter stationary point which is a saddle. For example, in the linear regression setting, i.e.
there are no guarantees that gradient
f(R) |XUV Y
(13)
the gradient of f is Lipschitz continuous with respect U when is fixed and vice-versa, versa, but not Lipschitz continuous with respect to R (Mukkamala & Ochs 2019). Thus, one may not directly
apply the results of Ge et al. (2015): [Sun et al. (2015): Lee al. (2016) in this case. Instead, we seek
to understand the conditions under which stationary points to 12) correspond to global optima of
(T)..
One such condition given Mardani et al. (2013] 20150.
Theorem 2.1 (From (Mardani et al.
2013 Stationary points U, V of the optimization problem
min U.V 2
UVT - -YII (IUB + IVII?)
(14)
2
correspond to global optima Z
UVT of the equivalent convex optimization problem
p
min Y +
(15)
z
provided that Y ÜV 22 3
3 BURER-MONTEIRO FACTORIZATION FOR CONVEX NEURAL NETWORKS
3.1 MLPs
We first seek to compare the convex formulations of the MLP training problem 3 and 6 to
their BM factorizations. We describe how to find the BM factorization for any convex MLP.
Lemma 3.1. For any matrix M Raxde, let f(U V) F(MUVT) be differentiable function.
For any 3 > 0 and arbitrary vector norms || and llllc. we define the Burer-Monteiro factorization
8
p²
min UER Ve
f(U.))+
j + l1 1lv
(16)
For the matrix norm
|| || defined
2) s.t. u Rv < 1 Vu E Bo, Vv E BR. i == max trace(R 2)
(17)
R
5

---

Under review as a conference paper at ICLR 2023
the problem 16 is equivalent to the convex optimization problem
min
F(MZ) + Z
(18)
Z ZER
Remark 3.2. In the case of linear MLP, M X. de d, d, and || -11-11.. using the = 2 and = 2 (Bach et al. 2008
definition of -|--1 ||D. in the corresponding BM factorization, For gated ReLU network, the regularizer is still the nuclear norm, and thus the same πt= -C=2 regularization appears in the BM factorization. In the case of the ReLU MLP, the nuclear norm is replaced by ||-I|p = Σj= 13 ll..k, which in the BM factorization amounts to having the constraint K2 U, 2 0. We accordingly express the BM factorization of convex MLPs below.
)
B (IUIP IV
PLMLP- min F(XUVT) + 2
(19)
UERdxm
VEReXm
8 2
PGMLP=
min USERnMM
F D D
Σ
+ I (V
(20)
VyEReXm
8 2
PRMLP=
min U,ERuXM,2D. (2 F
F
D.JUVvJ +
(21)
3=1
VjERoxm
To the best of our knowledge, (27) presents the first application of BM factorization to a non-linear neural network, which enabled by the convex model
In the linear case, the BM factorization (19) is identical to the original non-convex formulation of a linear MLP with neurons. Furthermore, in the case of gated ReLU, the BM factorization when m = is is equivalent to the original non-convex formulation. However, for ReLU activation two-layer networks, the B. factorization even when m corresponds to different (i.e. constrained, rather than ReLU activation) model than the non-convex formulation. While the original convex program is NP-hard, the computation of the cost function of the BM factorization is very simple. Thus, the per-iteration complexity of the BM factorization much lower than for the convex ReI.U MI..
The BM factorizations of these convex MLPs are non-convex, hence finding global min- imum appears intractable. However, the following theorem demonstrates that as long as a rank-deficient local minimum to the BM factorization is obtained, it corresponds to global optimum.
Theorem 3.3. If m Z rank(Z"), ). where Z is minimizer of (18,, all local minima of the BM factorization [6 global minima. Furthermore, if F is twice- diccedifferentiable any yank-deficient
Ú
local minimum R
16) corresponds to global minimizer Z UV of 18)...
This result demonstrates that these two-layer convex MLPs have no spurious local minima under mild conditions. However, there remains an algorithmic challenge: it is not straightforward to obtain a guaranteed local minima when the gradients of are not Lipschitz continuous. The following result provides a general condition under which stationary points of the (6) are global optima of (18).
Theorem 3.4. For any non-negative objective function F, for stationary VU.V) of 16) with corresponding Ż ÜVT with objective p for 188, the relative optimality gap p-p satisfies
B
p
-1
S
(22)
p"
where || -1%,, is the dual norm of
I|D-
In particular, this bound can be calculated by taking the gradient of the unregularized objective function, evaluated at candidate solution Z to the convex problem (18). which formed by the stationary point of BM problem [16). Intuitively. if the - norm of this solution is less than 3, then by the subgradient condition, Z is an optimal solution of (18). In the case of linear MLP with X Id F squared-loss objective, and V| [M2))1 B, result exactly replicates the result

---

Under review as a conference paper at ICLR 2023
of Theorem 2.1
from Mardani al. (2013). Furthermore, when this condition is not exactly satisfied, provides a novel result in the form of an optimality gap bound. To our knowledge, this is the first result that generalizes the optimality conditions for stationary points from any BM factorization of neural network. This provides an easily computable bound after solving (16) which quantifies how close solution is the global minimum. In the case of ReLU MLP, the relative optimality gap is given by
p p³
max jE uEB, Kyu20
Vz, F(
Σ 5'=1
Dj. DyyZZy Ju/2
(23)
Computing this quantity amounts to solving cone-constrained PCA problem (Deshpande et al. 2014), which can be done polynomial-time when d is constant. We should note that some stationary points are clearly present in any problem, such (Ü, V) (0, 0), so we cannot conclude that all stationary points are global optima. However, in certain cases, the optimality gap of stationary points
(22) always zero as we show next.
Theorem 3.5. A stationary point (Ü, V) of (6) is a global minimizer of if
C and (24)
rank(U Ü) rank V) = min(de, dr
Thus, for linear and gated ReLU MLPs, we can ensure that if the Burer-Monteiro factorization achieves a stationary point with full rank, it is corresponds with the global optimum of the convex program. We now can further extend these results CNNs and self-attention architectures.
3.2 CNNS
Before proceeding to explore the BM factorization in the context of two-layer CNNs, we first provide a new result on an equivalent convex program for two-layer ReLU CNNs with arbitrary linear pooling operations, which extends the results of Sahiner al. 2021bb: Ergen & Pilanci (2020) on Global Average Pooling CNNs. Define P. E Baxa to be a linear pooling matrix which pools the K spatial dimensions to arbitrary size a. Then, express the non-convex two-layer CNN problem
B
PONN min ERJER" Way ex
Σ
Pa
(25)
Theorem 3.6. For > and ReLU activation a(.) (.)+, , if m 2 m² where m S nac, then
25
equivalent to convex optimization problem, given by
trace P.
x (1)
PCNN
min ZgERbxae
B
Z l
(26)
trace P x (c)
X1
K₁ = (2Ds Ink)
z (d)
h vd [c].
x
Thus, we provide novel result which characterizes two-layer CNNs with arbitrary linear pooling operations convex program. Similar results can be shown for the linear and Rated-ReLU activation case With this established, we present our main results on the BM factorization for CNNs.
Lemma 3.7. The BM factorization of the convex CNN problem with ReLU activation is given as follows.
8
PRRN
min MujLeR"M leg (V 1- (2D -DX.u
F
V S
P.D
|V l1:)
2
k=11=1
k=11=1
(27)
We examine linear and gated ReI.U activations for CNNs in the Appendix.
7

---

Under review as a conference paper at ICLR 2023
The BM factorization closely resembles the original non-convex formulation 25
Generally, (7
inherits the results of Theorems (3.3). (3.4). and (3.5); we present one such corollary here.
Corollary 3.7.1. A stationary point (Ügs, jk 1=))==))== of (7) corresponds to global minimizer 2 25=1 Vev
(vix)
26 provided that of
trace(P (..D x
Z F
u/12 S E Vu (
(6) -IXX 2 0.
1=1
ttrace X x
(28)
3.3 MULTI-HEAD SELF-ATTENTION
We now for the first time extend BM factorization theory to self-attention networks. Lemma 3.8. The BM factorization of the convex self-attention problem with linear activation given as follows.
m Σ
PiSA min U, UReadxd VyERdRe
Σ X.UXXXXVV
+ U
|V,
(29)
2
==1
In addition to inheriting all of the results of Theorems 3.3
3.4 and 3.5 noting the equivalence of the
BM factorization with the original non-convex program ( we are the first to show conditions under which there are spurious local minima for self-attention networks.
Corollary 3.8.1. The linear- antivtaacivaaton self-attention network (29) has no spurious local minima as long as the number of heads satisfies m 2 m² where m S min(d? de). Furthermore, for any twice-differenee diicedifferettiable objective F, if for any local minimum (U,, V V of 29) the matrix
veo (v)(( (V)
veo(Ūm) veo(Vm))
R
(d(++))xm
(30)
is rank-deficient, then this local minimum is also global minimum of TO
EXPERIMENTAL RESULTS: THE RELATIVE OPTIMALITY GAP BOUND
04
0950
1 45
(b) m 150
Figure 1: Example of three-class spiral dataset, with different number of samples n.
In this section, we illustrate the utility of our proposed relative optimality bound for stationary points in the setting of two-layer fully-connected networks. We also seek to examine how this bound changes with respect to the number of samples n, the regularization parameter 3 (which controls the sparsity of the convex solution), and the number of factors in the BM factorization
We examine gated ReI.U and ReL. activations for self-attention the Appendix.
8

---

Under review as a conference paper at ICLR 2023
10-1
10-1
Relative Catimality Cap
Relative Oatimality Gap
10-3
10-3
10-7
10-7
20-9
10-9
10:41
Achud, m=1
41
Achad, m=1
Actud,
Actad,
10-43
10-43
(a) 15
(b) 45
10-1
10:1
Ralative Opt ma. by Gap
Ralative Opt ma by Gap
10-3
10-3
Bound, m-1
Bound m-1
Bound, m-5
Bound, mm2
10-4
Bound, m=5
Bound mm2
10
10
10-15
Actuel, m-5
10-13
Actual, m-5
13
10
10
10
10
10
10
10
beta
beta
(c) TL 75
(d) 1 150
Figure 2: Relative optimality gap of the non-convex BM factorization of gated-ReL.U two-layer MLP for three-class spiral data classification (d = 2, == 3). For fixed values of n, we demonstrate how 3 and affect relative optimality gap, both in terms of the proposed bound and the actual gap, where the global minimum is determined by convex optimization.
m. We initialize a class- balanced three-class spiral data set with varied number of samples n (see Figure for examples). For this dataset, we then train the gated ReLU MLP BM factor- ization 20) with varying number of factors m. We then compare the stationary points of these BM factorizations found by gradient descent (GD) to the global optimum, which compute from (6).
For each stationary point of the BM factorization, we compute the relative optimality gap bound provided in our result in Theorem 3.4 We note that since d 2, c = 3 in this case, for all ran S 2, so long as m all local minima of the BM factorization are global minima (Burer & Monteiro 2005 Haeffele et al.) 2014). While[Lee et (2016) demonstrated that gradient descent with a random initialization converges to a local optimum almost surely for losses whose gradient is Lipschitz continuous, we use squared loss with one-hot-encoded class labels, for which if is not Lipschitz continuous (Mukkamala Ochs 2019). Thus, there no guarantee that GD will find the global minimum. We display results over for each fixed in Figure 2 For larger values of 3, it becomes much easier for GD to find an optimal solution. We nevertheless find that bound gives useful proxy for whether the BM factorization has converged the global minimum.
We find that GD applied the BM factorization finds "subtle" saddle points: not quite lo- cal minima, but close. Interestingly, there only minor relationship between the optimality gap and the rank of the BM factorization m. While our optimality gap bound for 1 larger than larger values of m for small 3, the actual optimality gap is nearly identical across m. This experiment further validates the need to consider stationary points of the BM factorization, rather than just local minima, to fully characterize the BM factorization for efficient solutions to convex problems.
5 CONCLUSION
We are the first to adapt the Burer-Monteiro (BM) factorization for two-layer convex neural networks with linear and ReLU activations, which offers new insights on their global optima. We provide novel relative optimality bound stationary point of the BM factorization, which provides condition whose satisfaction guarantees a globally optimal solution.

---

Under review as a conference paper at ICLR 2023
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.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learning, pp. 522-332 PMLR, 2019.
Francis Bach, Julien Mairal, and Jean Ponce. Convex sparse matrix factorizations. arXiv preprint arXiv:0812.1869, 2008.
Yatong Bai, Tanmay Gautam, and Somayeh Sojoudi. Efficient global optimization of two-layer relu networks: Quadratic-time algorithms and adversarial training. arXiv preprint arXiv:2201.01900 2022.
Burak Bartan and Mert Pilanci. Neural spectrahedra and semidefinite lifts: Global convex op- timization of polynomial activation neural networks in fully polynomial-time. arXiv preprint arXiv:2101.02429, 2021.
Eugene Belilovsky, Michael Eickenberg. and Edouard Oyallon. Greedy layerwise learning can scale to imagenet. In International conference machine learning, pp. 583-593, PMLR, 2019.
Shobhit Bhatnagar, Deepanway Ghosal, and Maheshkumar H Kolekar. Classification of fashion article images using convolutional neural networks. In 2017 Fourth International Conference Image Information Processing (ICIP), pp. 1-6. IEEE, 2017.
Nicolas Boumal, Vlad Voroninski, and Afonso Bandeira. The non-convex burer-monteiro approach works on smooth semidefinite programs. Advances in Neural Information Processing Systems, 29, 2016.
Samuel Burer and Renato DC' Monteiro. A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Mathematical Programming, 95(2):329- 357, 2003.
Samuel Burer and Renato DC Monteiro. Local minima and convergence low-rank semidefinite programming. Mathematical programming, 103(3):427-444, 2005.
Ricardo Cabral, Fernando De la Torre, João P Costeira, and Alexandre Bernardino. Unifying nuclear norm and bilinear factorization approaches for low-rank matrix decomposition. In Proceedings of the IEEE international conference on computer vision, pp. 2488-2495, 2013.
Emmanuel J Candès and Benjamin Recht. Exact matrix completion via convex optimization. Foun- dations of Computational mathematics, 96):717-777, 2009.
Emmanuel Candès and Terence Tao. The power of convex relaxation: Near-optimal matrix
completion. IEEE Transactions Information Theor,, 5655)2233388) 2010.
Diego Cifuentes and Ankur Moitra. Polynomial time guarantees for the burer-monteiro method. arXiv preprint arXiv:1912.01749 2019.
Hadi Daneshmand, Jonas Kohler, Aurelien Lucchi, and Thomas Hofmann. Escaping saddles with stochastic gradients. In International Conference on Machine Learning, pp. 1155-1164, PMLR, 2018.
Yash Deshpande, Andrea Montanari, and Emile Richard. Cone-constrained principal component analysis. Advances Neural Information Processing Systems, 27, 2014.
Steven Diamond and Stephen Boyd. Cvxpy: A python-embeddded modeling language for convex optimization. The Journal of Machine Learning Research, 17(1):290--29) 2016.
Laurent Dinh, Jascha Sohl-Dickster and Samy Bengio. Density estimation using real nvp. arXiv preprint ar05v:/605.08800 08803, 2016.
10

---

Under review as a conference paper at ICLR 2023
Simon Du and Jason Lee. On the power of over- parametrization in neural networks with quadratic activation. International conference on machine learning, pp. 1 1338. PMLR, 2018
Simon Du, Jason Lee, Yuandong Tian, Aarti Singh, and Barnabas Poczos. Gradient descent learns one-hidden-layer cnn: Don't 't be afraid of spurious local minima. International Conference on Machine Learning, pp. 1339-1348, PMLR, 2018.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In International conference on machine learning, pp. 1675-1688 PMLR, 2019.
Simon S Du, Chi Jin, Jason D Lee, Michael I Jordan, Aarti Singh, and Barnabas Poczos. Gradient descent can take exponential time to escape saddle points. Advances in neural information processing systems, 30, 2017.
Murat A Erdogdu, Asuman Ozdaglar, Pablo Parrilo, and Nuri Denizean Vanli. Convergence rate of block-coordinate maximization burer-monteiro method for solving large sdps. Mathematical Programming, pp. 1-39, 2021.
Tolga Ergen and Mert Pilanci. Implicit convex regularizers of emn architectures: Convex optimization of two-and lhyee-layer networks in polynomial time. In International Conference Learning Representations, 2020.
Tolga Ergen, Arda Sahiner, Batu Ozturkler, John M Pauly, Morteza Mardani, and Mert Pilanci. Demystifying batch normalization in relu networks: Equivalent convex optimization models and implicit regularization. In International Conference Learning Representations, 2021.
Jonathan Fiat, Eran Malach, and Shai Shalev-Shwartz. Decoupling gating from linearity. arXiv
preprint arXiv: 190::0002.,000 2019.
Rong Ge, Furong Huang. Chi Jin, and Yang Yuan. Escaping from saddle points online stochastic gradient for tensor decomposition. In Conference on learning theory, pp. 797-842. PMLR, 2015.
Rong Ge, Chi Jin, and Yi Zheng. No spurious local minima in nonconvex low rank problems: A unified geometric analysis. In International Conference on Machine Learning, pp. 1233-1242. PMLR, 2017.
Nicolas Gillis. Introduction to nonnegative matrix factorization. arXiv preprint I 2017.
Benjamin Haeffele, Eric Young, and Rene Vidal. Structured low-rank matrix factorization: Optimality, algorithm, and applications to image processing. In International conference machine learning, pp. 2007-2015. PMLR, 2014.
Benjamin D Haeffele and René Vidal. Global optimality in neural network training. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 7331-7339, 2017.
Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M Kakade, and Michael Jordan. How to escape saddle points efficiently. In International Conference on Machine Learning, pp. 1724 1732. PMLR, 2017.
Kenji Kawaguchi. Deep learning without poor local minima. Advances in neural information
processing systems, 29, 2016.
Serhat Kiliçarslan and Mete Celik. Rsigelu: A nonlinear activation function for deep neural networks. Expert Systems with Applications, 174:1 144005, 2021.
Alex Krizhevsky, Geoffrey Hinton, al. Learning multiple layers of features from tiny images. 2009.
Jason D Lee, Max Simchowitz, Michael Jordan, and Benjamin Recht. Gradient descent only converges minimizers. In Conference on learning theory, pp. 1246-1257. PMLR, 2016.
Jan R Magnus and Heinz Neudecker. Matrix differential calculus with applications statistics and econometrics. John Wiley & Sons, 2019.
11

---

Under review as a conference paper at ICLR 2023
Morteza Mardani, Gonzalo Mateos, and Georgios B Giannakis. Decentralized sparsity regularized rank minimization: Algorithms and applications. IEEE Transactions on Signal Processing, (1(2)): 5374-5388, 2013.
Morteza Mardani, Gonzalo Matcos, and Georgios B Giannakis. Subspace learning and imputation for streaming big data matrices and tensors. IEEE Transactions on Signal Processing, 63(10):
2663-2677, 2015.
Aaron Mishkin, Arda Sahiner, and Mert Pilanci. Fast convex optimization for two-layer relu networks: Equivalent model classes and cone decompositions. In Proceedings of the 39th International Conference Machine Learning. 2022.
Mahesh Chandra Mukkamala and Peter Ochs. Beyond alternating updates for matrix factorization with inertial bregman proximal gradient algorithms. Advances in Neural Information Processing Systems, 32, 2019.
Dohyung Park, Anastasios Kyrillidis, Constantine Carmanis, and Sujay Sanghavi. Non-square matrix sensing without spurious local minima via the burer-monteiro approach. In Artificial Intelligence and Statistics, pp. 65-74. PMLR, 2017.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32: 8026-8037, 2019.
Mert Pilanci and Tolga Ergen. Neural networks are convex regularizers: Exact polynomial-tim time convex optimization formulations for two-layer networks. In International Conference on Machine Learning, pp. 7695-7705. PMLR, 2020.
Benjamin Recht, Maryam Fazel, and Pablo Parrilo. Guaranteed minimum-rait solutions of linear matrix equations via nuclear norm minimization. SIAM review, 52(3):471-501, 2010.
Jasson DM Rennie and Nathan Srebro. Fast maximum margin matrix factorization for collaborative prediction. In Proceedings of the 22nd international conference on Machine learning, pp. 713-719, 2005.
Arda Sahiner, Tolga Ergen, Batu Ozturkler, Burak Bartan, John M Pauly, Morteza Mardani, and Mert Pilanci. Hidden convexity wasserstein gans: Interpretable generative models with closed-form solutions. In International Conference Learning Representations, 2021a.
Arda Sahiner, Tolga Ergen, John Pauly, and Mert Pilanci. Vector-output relu neural network problems copositive programs: Convex analysis of two layer networks and polynomial-time algorithms. In ICLR, 2021b.
Arda Sahiner, Morteza Mardani, Batu Ozturkler, Mert Pilanci, and John M Pauly. Convex regulariza- tion behind neural reconstruction. In ICLR, 2021c.
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 Proceedings of the 39th International Conference on Machine Learning, 2022.
Alexander Shapiro. Semi-infinite programming, duality, discretization and optimality conditions.
Optimization, 58(2):333161,, 2009.
Richard P Stanley et al. An introduction to hyperplane arrangements. Geometric combinatorics, 13 (389-496):24, 2004.
Ju Sun, Qing Qu, and John Wright. When are nonconvex problems not scary? arXiv preprint 150.v:/510.06066, 2015.
Irene Waldspurger and Alden Waters. Rank optimality for the burer-monteing factorization. SIAM journal Optimization, 30(3):2577-2602, 2020.
12

---

Under review as a conference paper at ICLR 2023
Lingxiao Wang, Xiao Zhang, and Quanquan Gu. A unified computational and statistical framework for nonconvex low-rank matrix estimation. In Artificial Intelligence and Statistics, pp. 981-990. PMLR, 2017.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv:1708.07747, 2017.
Tian Ye and Simon S Du. Global convergence of gradient descent for asymmetric low-rank matrix factorization. Advances in Neural Information Processing Systems, 34, 2021.
Qinqing Zheng and John Lafferty. Convergence analysis for rectangular matrix completion using burer-monteiro factorization and gradient descent. arXiv preprint arXiv:1605.0705// 2016.
Zhihui Zhu, Qiuwei Li, Gongguo Tang, and Michael B Wakin. The global optimization geometry of low-rank matrix optimization. arXiv preprint 1XXv::703.00255 2017.
Liu Ziyin, Botao Li, James B Simon, and Masahito Ueda. Sgd can converge to local maxima. In International Conference on Learning Representations, 2021.
13

---

Under review as a conference paper at ICLR 2023
A PROOFS
A.1 RESULT OF (BURER & MONTEIRO 2005) AND ITS APPLICATIONS TO RECTANGULAR MATRICES
In this subsection, outline the precise theoretical statement of (Burer & Monteiro 2005 and describe exactly how it corresponds to our summary in Section 2.2 and thus the application to the later derivations in our work. We first describe the following result, without proof, from (Burer & Monteiro 2005).
Lemma A.1 (Lemma 2.1 of (Burer & Monteiro 2005)), Suppose R (ddt))x E R(
satisfy R. SST Then, S = RQ for some orthogonal Q E RRrx,.
Now, we proceed to prove analogs of Theorem 2.3 of (Burer & Monteiro with a rank constraint.
2005) for general SDPs
Lemma A.2 (Analog of Lemma 2.2 of (Burer Monteiro
2005
Consider the problem
min RER(
F'(RR
(31)
R a local minimum of 31 if and only if RQ is a local minimum of 31 for all orthogonal Q E grxr.
= RQ attains the same objective value, gradients, and higher order derivatives as R. Thus, R. is a local minimum if and only if R' is local minimum.
Proof. Since Q is orthogonal, (RQ) = RQQ R = RR Thus, :'
Theorem A.3 (Analog of Theorem 2.3 of (Burer & Monteiro 2005)). Consider the following two problems.
min
F(XX,;
(32)
XER (d44)) X=0 Sr
min RER(d+eixr
F'RRR
(33)
Then, for any continuous function F", a feasible solution X is local minimizer of 32 if and only if. for X RR.T, R. is a local minimizer of 33
Proof. We follow the exact same lines (Burer & Monteiro 2005). By continuity of the map
R R.... we know that if X local minimizer of (32). then R is local minimizer of 33
Now, must prove the other direction, namely that if X -RR. is not local minimizer of 32 then R a local minimizer of (33
Suppose that X is not local minimum. By continuity of F', then, there must be se- quence of feasible solutions {X*} of (32) converging to X such that F'(X*) < FX for all k. For each k. choose R such that X R Since {X*} is bounded, it follows that {R*) is bounded and hence has subsequence (R* kER converging some R such that X RR T. Since
F" = (x) < (X) = FRRR ), we see that R is not a local minimum of (33
Using the fact that x = RR RR. together with Lemmas A. and A.2 we conclude that R is not a local minimum
33
With this established, we now describe how this theorem applies to the setting described in Section 2.2 i.e. the rectangular matrix, non-SDP case.
Lemma A.4. Consider the solution X* to
pi
min
F' F'(X),
(34)
(e
X²0
14

---

Under review as a conference paper at ICLR 2023
and define m rank(X*). Then, for any 2 m². (34
is equivalent
P2
Xe x(d))) (X),
min
(35)
X=0
Le. pl = P2, and the solutions to 335 and
34 are identical.
Proof. Clearly, adding a rank constraint to 34 can only increase the objective value, so ph 2 Pi. However, since the optimal solution to (4 satisfies the rank constraint for any 2 mmm every optimal solution (34) maps to a feasible point for (35) that obtains the same objective, so p S Pi Putting these together, we have p1 Pī. and the solutions are identical.
Lemma A.5. Consider the solution X to 34 with m == rank(X*). Then, for any convex,
continuous function F', the global minimizer X -RR corresponds to a local minimizer R of
min RER(++)
FRRRR).
(36)
as long as m 2 m.
Proof. We simply use the result from Lemma A.4 and apply the equivalence to Theorem that if F' is convex, all local minimizers of (34) are global optimizers.
A.3 noting
Lemma A.6. Consider the optimization problem
PS = min F(Z).
(37)
ZERdxe
Define F² p(d+c)x(d+e) + R such that
X X3
X2
= F(X2)
(38)
X4
for X, Raxd, X2 E Rddxe X3 E Rexd, X, E Rexx Then, 37 is equivalent to 34 meaning that pi Pig and their solutions map to each other.
Proof. For any solution X*
34
simply form solution Z' to 37 by letting Z' = =X,, factor Z" V e.g. with SVD. Then, let
so clearly pi 2 P.- For any solution Z
37
U R and form solution to (34)
X T Clearly, X > 0. so X is feasible, and
the objective value is given by F" = T) = F(Z')= = pi. Thus, p S pl. Putting these
two together, we conclude pi P3 and the solutions of the two problems map to each other. O
Lemma A.7 (Used in Section 2.2). Consider the optimization problem (37) with optimal solution Z with m² := rank Then, for any convex, continuous function F', the solution Z = UUT corresponds local minimum (U, V) of
F(UV
(39)
dER V VeReXm
as long 2 m
Proof. Define F" (dd+c)x(dtt) + IR such that
Xi
X
F'
= F(X2)
(40)
X3
X4
U
for X, E Bdddd X, E RRxxe X2 E Rexd X, E Rex Then, let R
(dd+))xm One can
V
re-write F(UV] as F' F'(RT). Then, that 39 be expressed as 336 and any local minimizer to 336 is a local minimizer to 33
15

---

Under review as a conference paper at ICLR 2023
Furthermore, noting from Lemma A.6 any optimal solution
Z UVT of 37 is equiva-
x R Furthermore, lent to any optimal solution (34) by constructing RR
m rank(Z*) rank X
Putting everything together, have that rank-m" global optimum Z'
UV 37
corresponds to rank-m" global optimum X* to (3) (Lemma A.6), which, as long as m 2 m
U
corresponds to a local minimum R
(Lemmaa A.51, which is exactly the local minimum
V
(Ü, V) of (39)
A.2 RESULT (HAEFFELE ET AL. 2014) AND ITS APPLICATION TO RECTANGULAR MATRICES
In this subsection, we outline the precise theoretical statement (Haeffele et al. 2014) and describe exactly how it corresponds to summary in Section 2.2 and thus the application to the later derivations in our work. We first describe the following result, without proof, from (Haeffele et al. 2014).
Theorem A.8 (Theorem 2 of (Haeffele et al 2014 Let St - R be of the form such that F'() = G'(X) + HX),,, where G' is convex, twice differentiable with compact level sets, and
is proper convex function such that F' is lower semi-continuous. Then, if R is rank-deficient local minimizer of
min
F'RRR)
(41)
RER
then X = RR. is global minimizer of
min XER(d+0) X
F((X).
(42)
We now describe how this theorem applies to the setting described in Section 2.2 i.e. the rectangular matrix, non-SDP case.
Lemma A.9 (Used in Section 2.2p. Let F gaxe E. be of the form such that F(Z) G(Z) (Z), where G is convex, twice differentiable with compact level sets, and H is a proper convex
function such that F is lower semi-continnous. Then, if R
is a rank- local minimizer
V
of
min F(UVT), mxm VeRdxm
(43)
then Z- ÜV is global minimizer of
min F(Z).
(44)
ZERuxO
Proof. Define F', (Rd+c))(d+tc) IR such that
X Xa
X X4
F
= F(X2)
(45)
for X, E Rdxdd X, E Rdxe X, E Bexd X, E Rxx Clearly, if F = = + H, where G twice-differentiaale and H is proper convex, then, F' G + H' where G" is twice-
differentiable and H' is proper convex. From the proof of Lemma A.7 we know that (43) is
U V
exactly the same as (41 for R
Furthermore, we know from Lemma A.6 that any
global minimum Z of 44) corresponds to global minimum X of 42 Lastly, we know from Theorem that any rank deficient local minimum of 4I corresponds to a global minimizer (42)
16

---

Under review as a conference paper at ICLR 2023
U
Putting it all together, we have that rank-deficient local minimizer R
of (43
V
rank-deficient local minimizer [41, which corresponds to a global optimizer X
RB of (42)
(Theorem A.Sp, which corresponds to a global optimizer Z -VV of (44) (Lemma A.6
A.3 PROOF OF LEMMA 3.1
Proof. We first analyze the solution of the following optimization problem
min
|u + 1lv
s.t. UV Z.
(46)
My.y
We write this equivalent problem here Bach et al.
2008
Pilanci & Ergen
2020
m l
min EjEBC.y,
s.t. UV = Z.
(47)
We can form the Lagrangian of this as
m ||v,lR
min u, Be R
max
trace (RUUVT) + trace (R (R
(48)
By Sion's 's minimax theorem, we can switch the maximum over R and minimum over V and minimize over V to obtain
f min max trace (R T Z) s.t.||u R < 1.
(49)
uEBe
As long as m 2 rank (Z), by Slater's condition, we can switch the minimum and maximum (Shapiro 2009) to obtain
f traee R T Z) s.t./|u TR]]j S Vu E Bo.
(50)
R
By the definition of dual norm, we can also write this as
max
trace (R. Z) s.t.u RR S 1 Vu Be, Vv Bn |Z||oo
(51)
R
Thus, with this result, we have
m
p
min ((U,)) +
Σ
u 11e + ||v
(52)
Ue Ve
equivalently as
8 +
min
F(MUVT)
Σ
11a + 1Iv, 11:
(53)
UE
2
VER xm
or also
8
min
F(MZ)
+
min
Σ | 1|v
(54)
Z. Zzrank(Z)SM 5m
UER
2
dm
UV
=Z
where we now apply our previous result to obtain
min Z.rank(Z)) Z
F(MZ) B|
(55)
which if (Znk 2 m is equivalent
p" min F(MZ) + Z
(56)
2
17

---

Under review as a conference paper at ICLR 2023
A.4 PROOF OF THEOREM 3.3
Proof. We simply note that (16) is the Burer-Monteiro factorization of (18). Thus, from Lemma A. as long as 2 rank(Z*), all local minima of (16) are global minima. Furthermore, note that (88) is composed of two components, one of which is twice-differentiable function, and the other is proper convex function. Thus, by Lemma A.9 all rank-deficient local minima are global minima.
A.5 PROOF OF THEOREM 3.4
Proof. Stationary points of 16 satisfy
E Vuf(ú, +
O V) +
where we define
| = Itylle
and the same for [|V]] R. By the definition of the subgradient, this stationarity condition can be written
UU trace(U
| | x 0 0 Vuf(ū, V) / EV' s.t. traco TVV) = [ V = 1, 0 Vv V) + V
By the chain rule, we have that
0 V2F(MZ) 3| 1
0 = VZF(MZ) U + B /| V
We now right-multiply the top equation by ÚT and the bottom equation by V to obtain
VzF(MZ)VO + U'Ü = ( + +
(57)
(58)
Taking the trace, we have
trace (VZF(M2) = | Ictrace (U'TT) = ||]]]attace (V'VT).
(59)
Noting the definitions of U' and V', we have
trace (ZF(M2) T 2) = 110 = ||V|
(60)
Furthermore, since clearly F(M2) f(ū, V). we have that
1 3 trace (VZF(M2) 2) |111 | (1011 +IVI -1
(61)
Now, we examine the optimality conditions for 18 In particular, we have
p" min F MZ) + Z|ID
(62)
2
which by definition of the dual norm, is equivalent to
min F(MZ) Strace (ZTZ'). Z')
(63)
Z'E
Now suppose we have approximate saddle point (Ž, Ż') with objective value e such that VzF(Z)
32' 0, trace 2 TT 2²)= ||ž] D. and Ż' (1 e) B) for some 2 Let 2 I Z'. By strong
18

---

Under review as a conference paper at ICLR 2023
duality and non-negativity of F, we have
p' = max min F(MZ) + Btrace z
(64)
z' Bp 2
2 min F(MZ) + Strace Z 2)
(65)
2
B
min F(MZ)
+
trace Z 4')
(66)
2
1+c
2
1
min
(F(MZ) + Btrace Z 2')
(67)
1+6
Z
1
(68)
1+
Rearranging, we have that
p -ー p" | Solving the former equality for
Se.
(69)
p"
For the assumptions of this inequality hold, for any candidate solution Ż, one must sat- isfy V2F(MZ) + 32' and trace (''')
Z' = V2 we have by (61) that the latter equality is satisfied at any stationary point of
the BM factorization. Lastly, for (69) to hold for a particular c, one must have
Ż' = B V2F(M2) E (1 + c))
(70)
[VF((M))I 1i
1) i.e.
80 E
p
[zzF(M2) 11
-
(71)
1r
A.6
PROOF OF THEOREM 3.5
Proof. From the stationary point condition, we have
0 = V2F(M2) + BÚ
(72)
0 V2F(M2) Ü U....
(73)
From 73 we can obtain
U ÚTV2F(M2) -
(74)
Substituting this into 772 we have
0 = V
V+ -ŪT
(75)
= -
(76)
Thus, letr rank(V) rank(U)= minfder dr.. We write the compact SVD of the stationary
point as
0 = L T
V = LyARR,
where Lu E Rdderr Lv E Rdder, Assume without loss of generality that de > d,, so dr min(de, d.).. We have
0 V2F(MŽ)V 3U
(77)
0 = VZF(M22JLAAR + AR
(78)
Lu V2F(MZ)LV.
(79)
19

---

Under review as a conference paper at ICLR 2023
If r b, Ly is square and therefore unitary,
|2F(M22]|z = Lvl)
(80)
/Lull2
(81)
= 3.
(82)
Thus, we satisfy (2 with equality.
In general, note that when min(de, J. we have
[>Z((Z)] | (MZ)
2 VZF(MM))vvll
(83)
= BLul2
(84)
= B,
(85)
so 22 is lower bound, which depends on how Vz (Z) behaves when operating on vectors in
mul
A.7 PROOF OF THEOREM 3.6
Proof. We begin with the non-convex objective
25
8 m Σ
PONN min ERA
Σ F
Σ W 2
P
+
1
11 +
|| 1...
(86)
W2yeRoxa
We can re-write this as (Bach et al.
2008
Pilanci & Ergen
2020)
PONN
min WiJEB,
Σ
F
W2, Pa (X,(1))))+
+ 8
W W2llle.
(87)
Wa
1=1
j=1
We can also re-write this as
n Fr.) 3
PONN
min
W W s.t. Σ
W2, Pa Pa
(X,1)))) =
(88)
Wiy EB EReKa t=1
Forming the Lagrangian, we have
PCNN
min wiJEBg W2XC
max
Σ F(a))
+
W 23 |
W Pa (X
1=1
(89)
By Sion's minimax theorem, we can swap the minimum over W2j. r, and maximum over vi, and minimize over W2y, r, obtain
PONN min max- ueB, v;
Σ -F:(v:)
s.L. Σ v. 5.
(90)
where F* is the Fenchel conjugate of F. Now, long and m m where m < nac,
can switch the order of max and min by Slater's condition (Shapiro 2009: Sahiner et al.] 2021b to obtain
T
PONN V,
max
F" FV.v.))
8.t. max Σ
P. 38
(91)
i=1
20

---

Under review as a conference paper at ICLR 2023
Enumerating over the hyperplane arrangements {D&]e=1 can further write this as
PCNN = max
(v.),)
v;
max
Σ P.D (6) X uv 1F S B.
(92)
kE
ngBa
(2D 1
Now, noting that vec( vec(ABC) = (C) @ A) AJvec(B)
Magnus & Neudecker 2019), this is equivalent
to
PCNN
Σ Fv.v.) i=1
s.t.
max (E(
Σ 1=1
vi & P.D. x,)ul2 S
(93)
uEB2
(2D
u20
This may also be written further as
Σ (v:))
PCNN max
Vi
8.b.
m88
g ΣΣN
O X,)u 3
(94)
uEB;
1=1
(2D -
gEB,
and thereby as
PCNN = max Σ FV(v))
t=1
s.t.
max
trace
Σ 1=1
(v.
P.D O X,) SB.
(95)
nEB
(2D (9) -12
gEB,
Now, we let 2 = ug' to obtain
PCNN max Σ Fv)))
max kE[P]
trace Σ v. @ P.D X,)Z SB.
(96)
Z=ug"
u
(2D (4) -
gEB,
We let C. == conv ug (2D
I)X,u u B2, g and note that since our objective
linear we can take the convex hull of the constraints without changing the objective, to obtain
PONN
max
F (v:)
s.t. max trace ke[P] ZeC;
(vv & P&D X, 33.
(97)
21

---

Under review as a conference paper at ICLR 2023
Note that the constraint Z Cs is equivalent stating that |[]| I for the constrained nuclear norm definition with K₁ = (2D; I)X. Then, we have
PCNN max
Σ (v:)
i=1
s.t.
max
trace
Σ v. &
P.D.
x2) sB.
(98)
ke[P]
| |2|l_, $1
Now, we form the Lagrangian, given by
P
PCNN = max
min
min
Σ F
(v)
A
8 Σ
vec
(z))
vec (v. "
(P.D ( x.)
- $1 20
k=1
1=1
(99)
By Sion's minimax theorem, we are permitted change the order of the maxima and minima, to obtain
P
PONN = min A=20
min
max- Vi
Σ
F"
(v.)+
AR 8 Σ vec(Zz) vec (v. Tvec
(P.D x.)
Zu l.
(100)
Now, defining K as the (a, 1) commutation matrix we have the following identity from (Magnus Neudecker 2019:
vec (v. (P.D) (I. & (K.,, & ( (( vec(v:).
Using this identity and maximizing over v,, we obtain
P
PONN = min
min AL20
F
Σ
La &
vec(X..D)
P (K,, @ (n)))) vec(Zs)
+,3 Σ AE-
12. IZ.l--K,
k=1
(101)
Rescaling such that Zu
d Zi. we obtain
P
r +B Σ
PCNN
min
Σ F
Σ
I.
&
(K1,a @ kn))) T(,
vec(Zx)
1Z
Zr ZIERRAxa xe
k=1
k=1
(102)
Simplifying further, write this as
trace (P. P.D (1) (1))
P
PONN
min
F
+ B
Z
(103)
Zu Ex
R=
trace (P.D X,Z (0))
where Z((2) gaxx
A.8 PROOF OF LEMMA 3.7
Proof. We start with the convex formulation
ttrace (P.D (0) x, (1)1
Ya
P
PRENN
min Zy ERA
F
Σ
+
3
Σ
(104)
trace P.DD xiz (c)
22

---

Under review as a conference paper at ICLR 2023
In order to compute the Burer- Moner-Monteiro factorization, factor Z₁ V k where U₃ R U) 2 0. Then, with v(c') Raxm Then for each k,
Va E R and (2D
trace P.D X Z
trace P. X
trrcce (..D x )
UUV. O
trace P,DD
&
(Va (1)
P.D. U,U))
(Tacce(V.
P X U
Σ j=1
P R
jk
ン==1 jk
P.D X,
P Uuyk
where
jk
E Rxx
(105)
jk
The equivalent Burer-Monteiro formulation thus given by
m
B
P m
PRONN
min [u ym y ([ (2D 2,
Σ F
Σ
V 5k P
Σ
Σ
(1
II sw
(106)
A.9 PROOF OF COROLLARY 3.7.1
Proof. We simply apply the result of Theorem 3.4 noting that stationary points correspond to global minima if the norm the gradient is less than B. Thus, this condition is equivalent to
trace(P (P.D X X.Z (1)
Z5 F
u/1a S 8, vA E [P], e (2D
I)X,u
0.
Lrace ( D. x
(107)
A.
PROOF OF LEMMA 3.8
Proof. We begin from the convex formulation
110
d d
PiSSA
min
Σ k= t=1
G Z(, + Z
(108)
ZER dee
Now, we seek to find the Burer-Monteiro factorization. We let = UVT where U E of xm and V E [Rdexm, Let vec vug) Raxd be the result of taking chunks of d-length vectors from
uj for [m] and stacking them in columns. Similarly, let vec=+(v;) E Rexd be the result of
23

---

Under review as a conference paper at ICLR 2023
taking chunks of c-length vectors from vy and stacking them in columns. Furthermore, will let (uj) be the kth column of vec (uj). Then, recognize that
(R,
(uu))vve='(vy) (vv))z
vec
==1
Thus,
d
G.lk, (x,
G. viec vec (iee
k= t=1
d
X
vec Cyy
1=1
X;
vec Guy)
X,ve (u)) X,vec (vv)
Now, overloading notation, let vec ( (uj) = U, and ver vec = V-- We have clearly that the Burer-Monteiro factorization of (10) is given by
m
8 m
Pi.SA min USERaxa i=1 VyeRdxe
Σ
Σ 5=1
X,U,X
U + IV
(109)
2
A.11 PROOF OF COROLLARY 3.8.1
Proof. We simply nee dto apply the result of 3.3 this setting. In this case, the non-convex linear self- attention network is equivalent to the Murer-Monteiro factorization of the convex form. To obtain this Burer-Monteiro factorization, we factorize convex weights Z R x rank(Z") < minfd? de}.
Thus, letting m = rank(2 z min dc}, we can observe that as long as the number heads m
exceeds m from Lemma A.7 all local optima are global. Further, we can form U
and as
V
long as this is a rank-deficient local minimum, also corresponds to a global minimum when F twice-differentiable by Lemma A.9
B
ADDITIONAL THEORETICAL RESULTS
B.
MLPs
The following theorem demonstrates that extend the results of (Sahiner al. 2021b) beyond simply weight-decay regularization, and to arbitrary regularization. Theorem B.1. The non-convex ReL. training objective
p" min F (Xw1)) 3
w + 1lwas
(110)
W2j.Wa
is equivalent to the convex training objective
P +,3
p² = min F F D.XZ,, Z,
Σ
|Zgllo,
(111)
3=1
1=1
as long as B and m m² where m S nc, where
Z D, := max tracc R Z) s.t. u Rv <uuE Be (2D, I 2 0. Vv BR. (112)
R
24

---

Under review as a conference paper at ICLR 2023
Proof. We start by re-staning the convex objective (Bach et al. 2008
Pilanci & Ergen 2020
Mim
F
Xw1,)+
W2,)
+ 8
W25 lla.
(113)
EBC
==1
==1
Then, we can re-write this in a constrained form
m Σ
min F(R)
Wed R s.1.
((X11))+WW
Was -R,
(114)
Wiy EBC
Way
==1
and then the Lagrangian
Xwis) - R 1) (115)
m
p² min
max F(R) + =
way |R trace
V
WiyEBe Way
R
By Sion's minimax theorem, over Waj and R. Then, minimizing over these two, we have
swap the order of the maximization over V and minimization
min max - (V) s.t. V (Xu)+1IR S.B. uEBe
(116)
By Slater's condition, which holds when 3 > 0 and m S mn where m S ne (Shapiro 2009 Sahiner al. 2021c), switch the order of minimum and maximum obtain
max P (V) s.t. max ||V (Xu)))) B. uEBe
(117)
Introducing hyperplane arrangements, we have
max F* s.l.
IV D,Xu R S.B.
(118)
uE (2D 1)X220
By the concept of dual norm, this is equivalent
max F* (V) s.t. p²
max jE (2D) 1|X220 gEB,
trace Dy 1) SB..
(119)
Define
7
maxt s.t. Z E tconv/ug' T. u E Be, (2D, I)Xu 2 0, e B,). 120
(120)
Then, can write our problem
p" = max F* (V) s.t. max trace (V D, $ B.
(121)
jEP
|
Now, observe that |Z|, = [ D., In particular, let us examine 112). which we can re-write as
||||D,,
max trace R ') s.t. max trace Z R) s
(122)
R
31
= max trace( Z) s.t. R <
(123)
R
|Z]|,
(124)
where the simplifications are made noting the definition of the dual norm. Now, we can write our objective as
p" = max (V) s.t.
max JEPP
trace (V D,XZ) < 3.
(125)
|| n, $1
25

---

Under review as a conference paper at ICLR 2023
Forming the Largrangian, we have
p' max
min - F (V) + 1 $1 2
E> trace (V) D2
(126)
j=1
By Sion's minimax theorem, we can switch max and min and solve over V to obtain
p= min
F ,,DxXZ,) + Σ A/.
F
(127)
Z ll S1
==1
2
Lastly, we can combine 2₃ into one variable to obtain
p min F
Dj D2XZ,) ; +
(128)
as desired.
B.2 CNNS
Lemma B.2. The Burer-Monteiro factoioaat of the convex CNN problem with linear and gated ReLU activation are given as follows.
3
PLCNN
min yom
Σ F
Σ
Σ
(1 +
1V?)
(129)
(uyeR" Jm (V,ERexa 33ml
2
1=1
8
PGCNN Fa-llam ([V 13-11m-1
min [[ujeER" pm 18
F
V
jk
P.
[1 + |I (1
2
k=1j=1
k=1
(130)
Proof. The proofs follow almost identically from the proof of 3.7 In the linear case, the convex objective is given by
ttrace P.X,Z(1))
PLNNN-
F min ZER
+ B|
(131)
trace P. P,X,
In order to compute the Burer-Monteiro factorization, we factor = UVT where E phxm
E Raexm, Then, with v(d)) E Raxm Then,
trace P.X,Z()) )
trace (PX,Z((o)
(racoePP,,UUU (V())
trace (1)) P.X,U)
trace(V(o) P.X,U)
Σ V (1) P.X.uj
m (c) 1== 3
P.X,u,
Σ V P.X,u,
F=1
26

---

Under review as a conference paper at ICLR 2023
where
R Rexa
(132)
The equivalent Burer-Monteiro formulation thus is given by
PLCNN= (u f m 13-1
min
Σ F
V
PaPaa
X.uj
+
(133)
t=1
In the gated ReLU case, the convex program is given by
trace (P.D X.2 11)
(eacee(P.l)
PGCNN
min ZeeR
F
+ 3 Σ IZ
(134)
k=
trace P. P.D. X
In order to compute the Burer-Monteing factorization, we factor Z₁
U2 V where U₁ E R
VA & E gacxm, Then, with ((d') Iaax Then for each ht
&
trace P D ( X 11)
trace P P.D. (1)
X
.trace P.DD x
X.U.V()) T
Irace (aaceeP..Di (P.D.
traco(((()) (1) P.D. X,U))
k
trace( (c)
P U.
(1)
P D
X U
jk
P.D X,ukk
P
1==
jk
X.uj.
j=1
where
(1)
cxa
(135)
(c)
The equivalent Burer-Monteiro formulation thus is given by
P
P 5V 11:))
POCNN= =
min UP ERu 1 (XV 1
Σ F
V
jk
P
D
(1l +
1=1
k=1j=1
k=
(136)
27

---

Under review as a conference paper at ICLR 2023
B.3
Lemma B.3. The Burer-Monteiro factorization of the convex self- attentinnnn problem with gated ReLU and ReLU activations are given as follows.
P
m
PGSA = min
F
diag
O x.V
(137)
Jk
8
m
J +
2
k=1
P
PRSA min
F
diag
'(D (X.UxXX)) 54
(138)
V5k
1=1
k=
P
8
Σ
U
J + +V*l s.t. (2diag" (D - 11 @ (X.U,xX.)) 2 0,
2
k=1j=l
where diag (D E xx takes elements along the diagonal of D and places them in matrix form.
Proof. Courtesy of (Sahiner al.) 2022), we first present the equivalent convex models for gated ReLU and ReLU activation self attention. First, define
X1 X1
X
X, & X,
(D)} (diag (1(Xu 2 0
then, have
PASA
min
C
ΣΣΣ
G
(6.0 (K.)) Y;
+.3
|Zzll
(139)
ER
j=1k=1
5=1
PRSA min
L
G
(k x, (k:0) Y;
3 Σ
|Z |lag
(140)
2,
de
1=1
k= 8=1
j=1
where
(X, D. (0)
X IL),
for (k.f) Rxx and Z, (8.00 Bdxe
We then proceed take the Burer-Monteiro factorization of these models. Here, we will show the Burer-Monteine factorization of the ReLU model, noting that the proof is the same for the Gated ReLU model sans the constraints.
We let Z, U.VJ. where U, E of and V, E Rddomm where K,U, vec (ujx) E ddxd be the result of taking chunks of d-length vectors from Uyz for j E [m]] and stacking them in columns. Similarly, let vec- vexx)(vjj) e gexd be the result of taking chunks of c-length vectors from Viz and stacking them columns. Furthermore, we will let vec (ujx)s be the kth column of vec (ujz). Then, recognize that
Let
Zi (1:E))
(1.00
Σ vec (ujx))avec -v
28

---

Under review as a conference paper at ICLR 2023
Thus, for each J,
d
(k.0) x
G
(k.0)
G (k.e) 5.
X, (uxx)a {(vxx)
k=1
==1
(X, 1.) D (X, 2 1.) (4,00
X,vec X (ujx) '(vxx)
[X 00 (.) 10 ( I.) ( ((ux))avec"(vvv
vvee- ( (VVx)) k.
diag - o (X. X,V 1zy
where the constraint that (2D J 2 0 can also be re-written as (2diag (DD 11 )
(X,U)=XT)) 2 for all [m]. Thus, we have proven the statement.
C EXPERIMENTAL DETAILS
In all cases, we solve the BM factorization with GD using Pytorch (Paszke al., 2019) on CPU with momentum parameter of 0.9, a learning rate of 1.0 which decays by a factor of 0.9 whenever the training loss plateaus, and train for 20000 epochs such that GD always converges. For convex optimization, to determine the global optimum of each problem, we use the MOSEK interior point solver (Andersen & Andersen 2000) with CVXPY (Diamond & Boyd 2016). The parameters we [3, 15, 45, 75, 150). 3 E [10~4,10 10 10 10 and
[1,2,5]. We use randomly subsampled set of p 100 hyperplane arrangements. We perform this experiment over three random seeds, which are used to generate the hyperplane arrangements as well as the random Gaussian initializations of the weights.
evaluate
D ADDITIONAL EXPERIMENTAL RESULTS: BM ENABLES LAYERWISE TRAINING OF CONVEX CNNS
CIFAR-10 10 Accuracy
90
Test
Fēshion-MNIST MNIIS Accuracy
100
Test
Train
Irain
80
70
90
60
85
Stage
Stage
(a) CIFAR-10
(b) Fashion-MNIST
Figure 3: BM enables layerwise training of convex gated ReLU CNNs, which are competitive with end-to-end ReLU networks of similar depth. For CIFAR- 10, we achieve test accuracy of 80.5% compared to 81.6% for end-to-end non-convex training, and for Fashion-MNIS, we achieve a test accuracy of 91.5% compared 91.2% for end-to-end non-convex training (Kiliçarslan & Celik 2021 Bhatnagar et al. 2017).
We also provide some additional experimental results not presented in the main paper in order to supplement submission.
29

---

Under review as a conference paper at ICLR 2023
We consider the task of leveraging the theory of two-layer convex ReLU neural networks for training deep image classifiers. In particular, following the approach of (Belilovsky et al. 2019). we seek to train two-layer convex CNNs greedily to mimick the performance of a deep network. In the non-convex setting, the greedy approach proceeds by training single two-layer CNN, then freezing the weights of this CNN, using the latent representation of this CNN as the input features for another two-layer CNN, and repeating this process for specified number of stages. We leverage the result of Theorem 3.6 to convert this non-convex layerwise training procedure to a convex one, training stages of convex two-layer gated ReLU CNNs with average pooling. We apply this procedure to the image classification datasets of CIFAR-10 (Krizhevsky et al. 2009) and Fashion-MNIST (Xiao) jet al. 2017). following all general architecture choices from (Belilovsky et al. 2019) (see Appendix for details). We model the scenario in which we are in memory- memery-limited setting, restricting our memory to a single 12GB GPU.
In this memory-limited setting, layerwise training with the full convex model is impossible, because the nuclear norm penalty requires an SVD at each iteration, and further because the latent representation to be used as input for the second stage, given by (ID) (6) x,Z ( 15 has Pac channels, which for reasonable choices of P 256, 4, 10 yields upwards of 10 channels for the input to the second CNN stage. Accordingly, for this model, we employ the BM factorization with m = 1, allowing for latent representation for the second stage consisting of only P channels.
As show in Figure 3 this BM scheme for layerwise training allows for both test and train accuracies to improve one stage the next of the layerwise training procedure, reaching the performance of much deeper networks while enabling a convex optimization procedure. In particular, training five stages of a BM factorized convex two-layer gated ReLU CNN on CIFAR-10 resulted in a final test accuracy of 80.5%. Previously, it has been demonstrated that a six-layer ReLU CNN achieves 81.6% on CIFAR- 10 when trained end-to-end (Kiliçarslan & Celik] (021). In addition, the three-stage trained BM factorized convex two-layer gated Rel.U CNN on -NSST achieved a final test accuracy of 91.5%, compared to 91.2% for four-layer ReI.U CNN trained end-to-end
(Bhatnagar et al. 2017). These results demonstrate that the BM factorization is essential for convex neural networks to match the performance of deep end-to-end trained ReLU networks.
Our layerwise training procedure was trained Pytorch deep learning library (Paszke et al. 2019). In particular, we follow the implementation of (Belilovsky et al., 2019), who proposed greedily, sequentially training two-layer CNNs. At each stage, a two-layer CNN (convolutional layer + average pooling fully connected layer) is trained, and then the weights are frozen, the fully connected layer and average pooling are discarded, and the trained convolutional layer is used as a fcature-generatee generator for the following stage. At certain stages, before the CNN is applied, an invertible downsampling operation (Dinh al. 2016) is used to reduce the spatial dimensions of the image. In (Belilovsky et al. 2019), m = 128 convolutional features per stage are used, with ReLU activations as well as an average pooling operation to spatial dimensions of 2 x 2 (i.e.
single NVIDIA 1080 Ti GPU using the
4) is used, followed by flattening operation and fully connected layer. They also use softmax cross-entropy loss, a batch size of 128, weight decay parameter of / = 5e 4, along with stochastic gradient descent (SGD) with momentum fixed to 0.9. 50 epochs per stage, and learning rate decay by a factor of 0.2 every 15 epochs.
In our experiments, we keep all network and optimization parameters the same, aside from replacing the non-convex CNN at each stage with our convex CNN objective (26). We then apply the Burer-Monteiro factorization with m = to this architecture to make it tractable for layerwise learning as described in the main paper. At each stage, we randomly subsample f = 256 hyperplane arrangements, rather than enumerate over all P, which is a high-order polynomial in terms of n. We further use gated ReI.U rather than ReI.U activations for simplicity, which can work as well as ReLU in practice (Fiat al. 2019). These techniques have been used effectively for convex learning to exceed the performance of two-layer non-convex neural networks (Pilanci & Ergen 2020 Pilanci 2020 Ergen et al. 2021).
Ergen &
For the CIFAR- 10 experiment, we use 5 stages (following (Belilossky et al. 2019)), whereas for the Fashion-MNIST experiment, we use 3 stages, since the training accuracy saturates after 3 stages. We
30

---

Under review as a conference paper at ICLR 2023
choose learning rates per stage from {10-1, 20000.0003..000... 1.1044 11044]pprr per stage based training accuracy for CIFAR-10. The chosen learning rates were [10-1,10- 1.10% 10 10 10022 for CIFAR-10 10. For Fashion-MNIST, empirically observed the training loss better optimized with slightly higher learning rates, so we used [2 x 10-1,5 55 x 10-2,5 x 10-3). All code used to run our experiments is provided. Ultimately, our CIFAR-10 network with stages took 9163 seconds to train, and the MaSSI network with 3 stages took 4931 seconds to train. In (Kiliçarslan & Celik 2021). is shown that an end-to-end 6-layer CNN with ReLU activations takes 640 seconds to train on CIFAR-10 10 and 285 seconds to train on Fasion-MNIST. We note that the purpose of this experiment is advocate for the use of layerwise BM networks over end-to-end trained networks, but simply to demonstrate the utility of the BM network in enabling convex neural networks to scale to the performance of end-to-end deep networks by using layerwise learning.
31


Reviews:
[{"review_id": "nIcbfgdHhZD", "reviewer": "Reviewer_f4LA", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work studies the problem of formulating several (non)linear two-layer neural networks (NNs) as equivalent convex optimization problems, where existing results of equivalent convex optimization problems are computationally expensive.\n\nThis work proposes to use Burer-Monteiro (BM) factorization to obtain equivalent and computationally tractable non-convex alternative (rather than convex optimization problems) with no spurious local minima.\n\nSection 3.1 first calculates BM factorization for convex MLP with linear, gated ReLU, and ReLU activations, as shown in Eqs. (19) - (21). Theorem 3.4 characterize the relative optimality gap in and show that under some rank conditions the stationary points of BM factorization  in Eq. (16) are global minimizers of the equivalent convex optimization problem of Eq. (18), meaning that solving stationary points Eqs. (19) - (21) for those NNs could obtain global minimizers of their existing equivalent convex optimization problems.\n\nSection 3.2 first characterizes two-layer convolutional neural networks (CNNs) with arbitrary linear pooling operations as a convex program (Theorem 3.6). Lemma 3.7 gives BM factorization of the convex CNN problem with ReLU activation. Corollary 3.7.1 gives a result for stationary points of Eq. (27) are global minimizers of Eq. (26), under the condition of Eq. (28).\n\nSection 3.3 then studies self-attention networks. Lemma 3.8 shows the BM factorization of the the convex self-attention problem with linear activation (gated ReLU and ReLU activations are also calculated in the appendix), and Corollary 3.8.1 shows that Eq (29) has no spurious local minima as long as the number of heads is large enough.\n\nSection 4 uses experimental results on synthetic dataset, with a gated-ReLU two-layer MLP; as well as (shown in the appendix) on CIFAR-10 and Fashion-MNIST datasets, with  two-layer gated ReLU CNNs. The results show that BM factorization enables layer-wise training of two-layered MLPs and CNNs, achieving comparable results to end-to-end training of networks.", "summary_of_the_review": "The idea of using BM factorization to improve the computational efficiency of equivalent convex problems of two-layered NNs is reasonable and novel to me. However, most of the results are for two-layered NNs and restricted models like linear activations in self-attention networks, which makes it questionable how useful those results could be in practical NNs.\n\n\n\n=====UPDATE=====\n\nI would like to thank the authors for the feedback. I increased my score since it addressed my questions well.", "strength_and_weaknesses": "**Strength**:\n\n1. The idea of using BM factorization to improve the computational efficiency of equivalent convex problems of two-layered NNs is interesting, and the results seem novel.\n2. The presentation of results is clear and easy to follow.\n3. Experimental results can verify the proposed BM factorizations.\n\n**Weaknesses**:\n\n1. The neural networks studied in this work are not practical, mainly two-layered MLPs and CNNs. This weakness is from existing equivalent convex optimization problems are for two-layered models.\n2. The results for self-attention networks are interesting. However, it has a similar problem of using linear activation, which makes it questionable how useful those results are in practice.\n3. The characterizations of relative gaps and conditions for stationary points being global minimizers are presented without explanation, making the implications not clear to me, e.g., the gradient norm in Eq. (23), and the trace conditions in Eq. (28). Could the authors provide some intuitions or detailed explanations for the audience to better understand the meaning of those results?\n4. The comments of BM factorization finds \"subtle\" saddle points at the end of Section 4 is interesting. However, it is not clear to me how is it concluded that from the results in Figure 2 that the found solutions are saddle points rather than local minima, and is there a calculation to verify that?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "gCHRkkWqFHB", "reviewer": "Reviewer_JjJ3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "It has been shown by Ergen and Pilanci (2020) that 2 layer relu neural networks with squared L2 regularization are equivalent to regularized convex problems. The latter convex problems are in extremely high dimension and thus not tractable.\nThe regularization in the equivalent convex problems encourages low rank. hence, the paper proposes to use a Burer-Monteiro factorization to solve them.\n", "summary_of_the_review": "Incremental contribution to the field of convex reformulations of neural networks. Experiments are in dimension 2, and models limited to 2 layers.\n\nI would update my score if the rebuttal included an experiment with the number of samples and the number of features in the thousands (without the data matrix being low rank).", "strength_and_weaknesses": "I see several weaknesses:\n\n- The improvement is marginal. There are such results of tens of types of 2 layer neural networks (see the 9 cited, all in the last two years by Pilanci, Ergen, Sahiner and coauthors). This is yet another paper exploiting the same idea, thus the incrementality of the proposed approach.\n- The focus is on 2 layer neural networks, which contradicts the claims about \"useful practical information\". Can the authors point relevant practical papers in the literature where linear 2 layer networks are used?\n- The experiments are in dimension 2, which tends to indicate that the methods scales very badly with the dimension/rank of the data, as all convex reformulation methods for neural networks. It seems to me the benefits of the method, compared to SGD, are only on toy setting like this one, and the method becomes impractical in real life scenarios.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "d8rrz2QMuW", "reviewer": "Reviewer_NEnW", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors describe an application of Burer-Monteiro factorization to convex programs on neural networks.  The aim is to produce a non-convex, but tractable, optimization problem that, under certain conditions, do not have spurious local minima.  The approach is applied on a variety of NN architectures and validated with a simple synthetic experiment.", "summary_of_the_review": "The paper seems to provide novel approaches and insights, but it is plagued by too much information in too short a space.", "strength_and_weaknesses": "Strengths:  The general approach appears to be quite applicable to a wide variety of NN architectures.\n\nWeaknesses:  There are too many NNs considered at the expense of more detailed experimental evaluation.  The main text just reads like a laundry list of similar results that don't seem to add any depth to the discussion.  In its current form, this work feels more appropriate for journal publication.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Vdnddx3JN4s", "reviewer": "Reviewer_jgFt", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper discusses the use of the Burer Monteiro factorization in the setting of convex neural network. The main result of the paper are a number of theoretical guarantees on the convergence of gradient descent (i.e. absence of saddles) for appropriate choices of a variety of parameters such as the size of the hidden layer, number of training examples and rank of the Burer Monteiro factorization. The authors tackle a number of architectures from the simple multilayer fully connected perceptron defined on a variety of activation functions (linear , Relu, gated Relu), convolutional neural networks and self attention networks and derive corresponding convergence guarantees for each architecture. ", "summary_of_the_review": "\npage 3\n\n- You never introduce F. I assume this corresponds to the loss? l2 loss ?\n\n- Aren’t the D_j matrices redundant? given that the factorization enforced by the quasi nuclear norm requires Ku to be non negative? I.e. this also seems to be suggested by your expression of D_j X Z in the paragraph below equation (4)\n\n- What does e stand for in the bound on P? Is that ln(1) ?\n\npage 4\n\n- When you introduce the convex formulation for the Relu based convolutional neural networks, it is not clear what X_i and in particular h and K represent. Is the matrix X_i reorganizing the prototype x_i as a circulant matrix?\n\n- Again, in the paragraph above Equation (8), you use the notation n. I guess ’n’ refers to the input dimension as before. Is c the hidden layer size? you should say it more clearly\n- The condition m>=m^* on the one hand and m^*<= nc on the other seem a little too simple to me. I.e. take m^* = 1 and you get unconditional convexity?\n- When you write “Since P is exponential in the rank of X, for fixed filter size h, P is polynomial in all other problem dimension” do you mean “Although P is exponential…” ?  If the D_j’s are the same matrices as those you introduce in (3), why not getting rid of this line and adding a reference to the bound on P which you provide below (3), indicating that in the case of  a convolutional network the dependence on n reduces to a dependence on h?\n- In the paragraph above equation (10). Again, I have some concern with your bounds on m as they seem to suggest that the equivalence holds for any value of m\n\npage 5 \n\n- The sentence “However, if the gradient of f is not Lipschitz-continuous, there are no guarantees that gradient descent will find a second-order critical point of (12): one may encounter a stationary point which is a saddle” which comes at the end of the parameter above Equation (13) should come earlier. When you cite the result of Bach according to which all local mins are global mins, you should indicate that convergence to those minimas is not necessarily guaranteed.\n\npage 6\n\n- At the beginning of the page, what do \\mathcal{B}_C and \\mathcal{B}_R stand for here? I guess this is related to the corresponding norms in (16)\n- I don’t see the link between the variational formulation you introduce in (17) and the regularization terms appearing in each of your formulations (19), (20), (21). In particular in (21), what do the sets \\mathcal{B}_C and \\mathcal{B}_R represent? \n- It is not clear to me how formulation (3) can be written equivalently as (21). In particular, if the original formulation (3) is NP hard to solve, how can the Burer Monteiro factorization become tractable? Either you have poorer/lose convergence guarantees, or you must have some conservation of complexity. Some more details would be welcome\n- At the end of the page, in the last paragraph, why would it make sense to take X = I? Isn’t X used to represent the feature matrix ?\n- Equation (22), Either you add the hat on the Z subscript of the gradient, or you remove it from the argument of F\n\npage 7\n- The transition from (22) to (23) in the case of the Relu is not clear. What does \\mathcal{B}_2 mean in this case ?\n- if you look at (21) the K_j matrix multiplies U_j (the left factor of Z) while in (23) it multiplies a vector u, which from the constraint u \\in \\mathcal{B}_2  seems to be the vector appearing in the definition of the D norm in (17).. This is not clear\n- I would remove the paragraph “We should note that some stationary points are clearly present in any problem, such as (Uˆ , Vˆ ) = (0, 0), so we cannot conclude that all stationary points are global optima. However, in certain cases, the optimality gap of stationary points (22) is always zero as we show next. ” which is unclear\n\npage 8\n- In the statement of Corollary 3.7.1. What is the meaning of Z^{(j)}_{k’} ? What is the meaning of \\mathcal{B}_2 ?\n- In the statement of Lemma 3.8\n- In the statement of Corollary 3.8.1, it would be useful to recall the meaning of d,c,m. d is the number of features. How about c, m ?\n- In the statement of Corollary 3.8.1. Again, I wondering if what you mean is not m^*\\geq min\\left\\{d^2, cd\\right\\}?\n\npage 9\n\n- The plots in figure 2 look very similar. Also from formulation (20) which seems to be the one you use, using d=2, c=3, does not look like a very challenging scenario. In fact you know you are in the regime in which all local minimas are also global. Although I know there can be saddles as well, it might be more interesting to study the evolution of the optimality gap for larger values of n. \n- “We find that GD applied to the BM factorization finds “subtle\" saddle points: not quite lo- cal minima, but close”. Do you mean that optimality gaps are small but not small enough to ensure a local minimum ?\n- “there is only a minor relationship between the optimality gap and the size of the BM factorization m ”. I would replace “size” by rank (which seems more appropriate to me here). Also when you say \"there is only a minor relationship between the optimality gap and the size of the BM factorization m”, it seems to me that the optimality gap is independent from pretty much all the quantities you consider except for the regularization. You should be able to get the analytic expression of the gap. How does this expression vary as a function of m, n? This should be further discussed. \n- The last paragraph of section 4 is not very clear. In particular, I don’t see why the experiments particularly highlight the need to consider saddles (i.e. in fact if you look at the plots, you see that for m>max(c,d) the gradient iterates converge to the global minimum of the loss. To me, the relevance of saddles would be illustrated if the bound was non zero in that regime where all local mins are also guaranteed to be global mins). \n \nAdditional typos:\n- page 6, first line : “provides a novel result in the form of a optimality gap bound” —> “aN optimality gap bound” \n- same page, next sentence, “To our knowledge, this is the first result of that generalizes the optimality” —> “the first result that generalizes” \n- page 7, below equation (24) “we can be assured” —> “we can ensure”\n\n", "strength_and_weaknesses": "The paper is interesting. My main concern is with the readability/organization of the paper. I feel that it would improve readability a lot if you were just removing some of the discussion between your introduction of the formulations p_{LMLP}, p_{GMLP} and p_{RMLP} and their corresponding Burer Monteiro factorizations. I would suggest compressing (if not completely removing) section 1.2 and expand on Lemma 3.1 and Theorem 3.4. providing diagrams (As an example in Corollary 3.8.1. it is hard to picture the network.) for some of the models discussed to clarify the meaning of the variables appearing in each of the optimisation formulations (e.g. 28/29).\n\nAlso after reading the whole paper, instead of introducing the convex programs in section 2.1. and then discuss their BM factorisations in separate later subsections, I would replace section 2.1. with a short general introduction to the whole paper and then introduced the convex formulation along each of their BM factorisations. This will make the reading easier by eliminating the need to go back and forth between 2.1 and pages 6/7/8 . \n\nFrom the space you will spare by eliminating section 1.2, you will also gain space to discuss and improve the numerical experiments. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "K9qxGsUKz-", "reviewer": "Reviewer_tmAf", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper presents new algorithms for learning (two-layer) multi-layer perceptrons with ReLU activations. The approach uses the Burer-Monteiro factorization, which yields a nonconvex optimization problem that (under certain low-rank conditions) does not admit spurious local optima. A collection of other related results are applied to other architectures, and brief computational results are provided.", "summary_of_the_review": "The paper is well-written and self-contained, and is seemingly a natural and worthy contribution to the literature. However, I am not an expert in the subfield studied in the paper, so my degree of confidence in this assessment is relatively low.", "strength_and_weaknesses": "The paper does a great job summarizing the prior art in this line of work. The contributions are seemingly novel, and the use of the BM factorization in this context is a smart and natural one.\n\nI think the authors could be a bit clearer in stating the scope of their contributions in the abstract and introduction. It seems that the results of the paper are restricted to _two layer_ MLPs, but the abstract and Section 1.1 do not make this explicit (though some preceding text on page 2 does mention that this).\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject