Nonparametric Learning of Two-Layer ReLU Residual Units
Authors: Zhunxuan Wang
Linyun He
Chunchuan Lyu
Shay B Cohen
Venue: Accepted by TMLR ()

Abstract: We describe an algorithm that learns two-layer residual units using rectified linear unit (ReLU) activation: suppose the input $\mathbf{x}$ is from a distribution with support space $\mathbb{R}^d$ and the ground-truth generative model is a residual unit of this type, given by $\mathbf{y} = \boldsymbol{B}^\ast\left[\left(\boldsymbol{A}^\ast\mathbf{x}\right)^+ + \mathbf{x}\right]$, where ground-truth network parameters $\boldsymbol{A}^\ast \in \mathbb{R}^{d\times d}$ represent a full-rank matrix with nonnegative entries and $\boldsymbol{B}^\ast \in \mathbb{R}^{m\times d}$ is full-rank with $m \geq d$ and for $\boldsymbol{c} \in \mathbb{R}^d$, $[\boldsymbol{c}^{+}]_i = \max\{0, c_i\}$. We design layer-wise objectives as functionals whose analytic minimizers express the exact ground-truth network in terms of its parameters and nonlinearities. Following this objective landscape, learning residual units from finite samples can be formulated using convex optimization of a nonparametric function: for each layer, we first formulate the corresponding empirical risk minimization (ERM) as a positive semi-definite quadratic program (QP), then we show the solution space of the QP can be equivalently determined by a set of linear inequalities, which can then be efficiently solved by linear programming (LP). We further prove the strong statistical consistency of our algorithm, and demonstrate its robustness and sample efficiency through experimental results on synthetic data and a set of benchmark regression datasets.

Published in Transactions on Machine Learning Research (11/2022)
Nonparametric Learning of Two-Layer ReLU Residual Units
Zhunxuan Wang
zhwneuaa, htt.://wwn.uonnggmmill.coo
Amazon'
London EC2A 2FA, United Kingdom
Linyun He
1he85@gatecke edu
Georgia Institute of Technology Atlanta, GA 30332, United States
Chunchuan Lyu
chunchuan.lu@gmac
Instituto Telecomunncacéées Torre Norte 1049-001 Lisbon, Portugal
Shay B. Cohen
scohen&uing ed..cc. ac. uk
University of Edinburgh Edinburgh EH8 9AB, United Kingdom
Reviewed on OpenReview: https: // ottpr//veerrvvee....m net/ forum? id= Yt0IOvq
Abstract
We describe an algorithm that learns two-layer residual units using rectifiod linear unit (RcLU) activation: suppose the input is from a distribution with support space Idd and the ground- truth generative model is a residual unit of this type, given by B (A'x)* +x where
ground-truth network parameters A Rdxd represent full-rank matrix with nonnegative entries and B RRxd is full-rank with m 2 d and for E RR., [c+]: max c3. We design layer-wise objectives as functionals whose analytic minimizers express the exact ground-trus network in terms of its parameters and nonlincaritics. Following this objective landscape, learning residual units from finite samples can be formulated using convex optimization nonparametric function: for each layer, we first formulate the corresponding empirical risk minimization (ERM) as positive semi-definite quadratic program (QP), then we show the solution space of the QP can be equivalently determined by set of linear inequalities, which can then be efficiently solved by linear programming (LPP.. We further prove the strong statistical consistency of our algorithm, and demonstrate its robustness and sample efficiency through experimental results on synthetic data and a set of benchmark regression datasets
1
Introduction
Neural networks have achieved remarkable success in various fields such computer vision LeCun al.
1998
Krizhevsky et al.) 2012 He et al. 2016a) and natural language processing (Kim 2014 Sutskever et al.
2014
This success is largely due to the strong expressive power of neural networks (Bengio & Delalleau
2011
where nonlinear activation units, such as rectified linear units (ReLU; Nair & Hinton 2010) and
hyperbolic tangents (tanh) play a vital role to ensure the large learning capacity of the networks (Maas) 2013). However, the nonlinearity of neural networks makes them significantly more difficult to train than linear models (Livni al. 2014). Therefore, with the development of neural network applications, finding efficient algorithms with provable properties to train such nontrivial neural networks has become an important and relatively new goal.
et al.
Work done mostly University of Edinburgh.
1 'Qur code available attps://github

---

Published in Transactions on Machine Learning Research (11/2022)
Residual networks, or ResNets (He et al. 2016a), are class of deep neural networks that adopt skip connections to feed values between nonadjacent layers, where skipped layers may contain nonlinearities in between. Without loss of expressivity, ResNets avoid the vanishing gradient problem by directly passing gradient information from previous layers to current layers where otherwise gradients might. vanish without skipping. In practice, ResNets have shown strong learning efficiency in several tasks, c.g. achieving at least 93% test accuracy on CIFAR-10 classification, lowering single-crop error to 20.1% on the 1000-class ImageNet dataset Ruusaakvvsy
R-T.U
et al. 2015 He et al. 2016b; Allen-Zhu & Li 2019
Common ResNets are often aggregated by many repeated shallow networks, where each network acts as a minimal unit with this kind of skip propagation, named a residual unit (He et al.) 2016b).
Given the flexibility and simplicity of residual units, much theoretical work has been devoted to studying them and developing training algorithms for them in a way that sidesteps from the standard backpropagation
regime and provides guarantees on the quality of estimation (sce Section [.1). In this paper, we propose algorithms that learn a general class of single-skip two-layer residual units with ReLU activation as shown on the right by the equation: y - B (Ax)* +x] where for scalar c, c = max(0, c} (for a vector, this maximization is applied coordinate-wise), x is a random voctor as the network input with support space R4, and A E gadd with nonnegative entries and B E Rmxd are weight matrices of layer and layer 2, respectively.
Compared to previous work (Ge al. 2019 2018 Zhang et al.) 2019 Wu et al. 2019 Tian 2017 Du
et al. 2018 Brutzkus & Globerson 2017 Soltanolkotabi 2017: Li & Yuan 2017 Zhong et al. 2017 the
introduction of residual connections simplifies the recovery of the network parameters by removing the permutation and scaling invariance. However, the naive mean square error minimization used in estimating the parameters remains nonconvex. Unlike most previous work, we do not assume a specific input distribution nor that the distribution is symmetric (Ge et al. 2019; Du & Goel 2018).
We show that under regularity conditions on the weights of the residual unit, the problem of learning the ReLU unit be formulated through quadratic programming (QP). We use nonparametrie estimation (Guntuboyina & Sen 2018) to estimate the ReLU function values in the networks. We further rewrite our constructed quadratic programs to linear programs (LPs). The LP formulation is simpler to optimize and has the same solution space as the QP for the network parameters.
1.1 Related Work
The study of two-layer ReLU networks (and two-layer networks in general, with one hidden layer) has received much attention in recent years because of the balance they present between their practical and theoretical propertics. On one hand, two-layer networks represent non-convex learning problems and embody many of the same diifficlties that we have with several layers. On the other hand, they are simple enough to study from a theoretical perspective. Arora et al.] (2014) recover a multi-layer generative network with sparse connections and Livni et al. (2014) study the learning of multi-layer neural networks with polynomial activation. Goel et al. 2018)) learns one-layer convolution network with a perceptron- rule. They prove the correctness of an iterative algorithm for exact recovery of the target network. Rabusseau et al. (2019)
describe a spectral algorithm for two-layer linear networks. Recent work has connected optimization and
two-layer network learning (Ergen & Pilanci 2021a Sahiner et al. 2021 Ergen & Pilanci
2021b Pilanci & (Belilovsky et al.
Ergen 2020 Mishkin et al., 2022) and has shown how to optimize networks layer by layer
2019) or their relationship to lincar classification (Yang ct al. 2021) Arjevani & Field (2021) study the
symmetries that two-layer ReLU networks present.
For learning one-layer ReLU network, Wu et al. 2019 optimize the norm and direction of neural network weight vectors scparately, and Zhhan et al. (2019) use gradient descent with a specific initialization. For
learning a two-layer ReLU network, [e et. al. (208)) redesign the oplinization landscape such that it is more
amenable to theoretical analysis and Ge et al. (2019) use a moment-based method for estimating a neural
network (Janzamin et al. (2015). Many others have studied ReLUU networks in various scttings (Tian 2017
Du et al. 2018 Brutzkus & Globerson 2017
Soltanolkotabi
2017 Li & Yuan 2017 Zhong et al.
2017
Goel
& Klivans 2019)
2

---

Published in Transactions on Machine Learning Research (11/2022)
The study of ReLU networks with two hidden layers has also been gaining attention (Goel & Klivans 2019
Allen-Zhu et al. 2019), with a focus on Probably Approximately Correct (PAC) learning (Valiani 1984 ). In relation to our work, Allen-Zhu & Li (2019) examined the PAC-learnable function of a specific three-layer neural network with residual connections. Their work differs from ours in two aspects. First, their learnable functions include a smaller (in comparison to the student network) three-layer residual network. Second, the assumptions they make on their three-layer model are rather different than ours.
In relation to nonparametric estimation, Guntuboyina & Sen 2018) treat the final output of shape-restricted regressor as parameter, placing some restrictions on the type of function that can be estimated (such convexity). They provide solutions for estimation with isotonic regression (Brunk) 1955, Ayer et al.
1955 van
Eeden 1956, convex regression (Seijo & Sen 2011), shape-restricted additive models (Meyer] 2013
Chen &
Samworth 2016) and shape-restricted single index models (Kakade et al. 2011 Kuchibhotla et al.
2021
1.2 Main Results
We design quadratic objective functionals with linear bounded feasible domain that take network parameters and activation functions as variables to estimate the ground-truth network parameters and nonlinearities. The values of the objectives are moments over the input distribution.
In Theorems 4.1 and 5.1 we show that if a ground-truth residual unit has nondegenerate weights in both layers and nonnegative weights layer 1, then there are quadratic functionals (sce Eqs. 2 and (6) with a domain defined by línear constraints whose minimizers a) are unique, and are the exact ground-truth, or b) are not unique, but can be adjusted to the exact ground-truth by process of rescaling (see Theorem 5.2)
The minimizers above use moments of the input distribution. In practice, exact moments from the underlying distribution are not available. To address that, we use empirical risk minimization (ERM) of the moment- valued objectives by generated samples. With functions as variables in moment-valued objectives being optimized nonparametrically, the empirical objectives become quadratic functions with linear constraints (quadratic program: QP).
We further show the convexity of our QP which guarantees its solution in polynomial time w.r.t. sample size and dimension. With the available QP solution, our learning algorithm is strongly consistent (Theorem 6.3 We show that if samples are generated by ground-truth residual unit that has nondegenerate weights in both layers and nonnegative weights in layer 1, then our algorithm learns a network closer to the exact ground-truth (in Frobenius norm) as sample size grows.
Assume A and B are student network weights of layer and 2. We first give a warm-up vanilla lincar regression approach only knowing A is in Rdxd and B is in Rmxd (Section 3 We then move to the details of our nonparametric learning for layer 2 (Section and similarly, layer (Section 5p. We formalize the quadratic functional mininization result above, showing how nonparametrie learning allows us to select the values of A and B from reduced spaces that are seeded by A' and B*, under which we can use linear regression (LR) effectively compared to vanilla LR. In Section G we describe the strong consistency of our methods for respective layers, formalizing the consistency result using the continuous mapping theorem (Mann & Wald 1943). In Appendix [ we describe a sample complexity analysis of our algorithm. We further discuss the multi-layer case in Appendix C
Roadmap:
2 Preliminaries
We describe the notations used in this paper, introduce the model and its underlying assumptions, and state conditions which simplify the problem but which can be removed without loss of learnability.
Notation The ReLU residual units we use take a vector æ E Rd input and return a vector y RT We use A' Baxd and B" E mxd to denote the ground-truth network parameters for layer 1 and 2, respectively. We use circumflex to denote predicted terms (c.g. an empirical objective function f, estimated layer 1 weights
By strong consistency, we are referring almost sure convergence of the estimator to the true parameters, rather than convergence in probability, which a weaker type of probahilistic convergence.
3

---

Published in Transactions on Machine Learning Research (11/2022)
A). We use to denote the number of independently and identically distributed (ii.d.) samples available for the training algorithm, (ax(), y } to denote the i-th sample drawn. For an integer k, We define [k] to be 21, k), and eli) as the standard basis vector with a 1 at position j. All scalar-based operators are element wise in the case of vectors or matrices unless specified otherwisc. For a matrix G and an index j, G. denotes its jth column and Gy.: denotes its jth row. We use x and y to refer to the input and output. vectors, respectively, as random variables.
Linear Regression: Linear regression, or LR, in this paper refers to the problem of estimating L for unbiased model y La. In this case, estimation is done by minimizing the empirical risk R (L)
In Eiena | - y f012² using linear least squares (LLS). Its solution has closed form which we use as given. We refer the reader to Hamilton (2020) for more information.
Models, Assumptions and Conditions Following previous work (Livni et al. 2014), we assume given neural network structure specifies a hypothesis class that contains all the networks conforming to this structure. Learning such a class means using training samples to find a set of weights such that the neural networks predictions generalize well to unseen samples, where both the training and the unseen samples are drawn from an unobserved ground-truth distribution. In this paper, the hypothesis class is given by ReLU residual units and we assume it has sufficient expressive power to fit the ground-truth model. More specifically, we discuss the realizable case of learning, in which the ground-truth model is set to be residual unit taken from the hypothesis class with the form:
y B" (A'x)* +x].
(1)
and is used to draw samples for learning. Unlike other multi-layer ReLU-affine models which do not apply skip connections, we cannot permute the weight matrices of the residual unit and retain the same function because of skip-adding (it breaks symmetry). This helps us circumvent issues of identifiability to precisely estimate the ground-truth weight matrices A and B*
3 and allows
Our general approach for residual unit layer 2 learns a scaled ground-truth weight matrix that also minimizes the layer 2 objective. The existence of such scaled equivalence of our layer approach comes from what is defined below.
Definition 2.1 component-wisc scale transformation). A matrix A E Raxd is said to be a scale transformation w.r.t. the j-th component if (A,.)² Aj.j e
Additionally, estimation more complex when the layer weight matrix B" nonsquare. For simplicity of our algorithm presentation for layer 2, we use Condition 2.1 in the following sections +
Condition 2.1 (layer 2 objective minimizer unique). A is not a scale transformation w.r.t. any components and B" is a square matrix, L.c. m = d.
3 Wprm-Up: Vanilla Linear Regression
Consider ground-truth (wo-layer residual unit. If we assume that the inputs only contain vectors with negative entries, i.e. x < O, the effect of the ReLU function in the residual unit then disappears because of the nonnegativity of A The residual unit turns into linear model y B'x. Thus, direct LR on samples with negative inputs can learn the exact ground-truth layer 2 parameter B with at least d samples, when formulating the LR as a solvable full-rank linear equation system.
On the contrary, if the inputs only contain vectors with positive entries, i.e. x 0, all the neurons in the hidden layer are then activated by the ReLU and the nonlinearity is eliminated. The residual unit in this case turns into y B (A* + Ia) x. Taking the value that left-multiplies x as single weight matrix D*, this is also a lincar model. Direct LR on at least d samples with positive inputs by the residual unit can
Here, are referring to the ability identify the true model parameters using infinite samples. In Appendix F we show that estimation of B remains possible without satisfying Condition 2.1
4

---

Published in Transactions on Machine Learning Research (11/2022)
learn the exact D Since have the access to the exact B", solving for the exact A can be accomplished through solving full-rank linear equation system B* D" where the unique solution À = A + la-
While simple, this vanilla LR approach requires large number of redundant samples, since sampled inputs usually have a small proportion of fully negative /positive vectors. Taking random input vectors i.idd with respect to each entry as an example, the probability of sampling a vector with all negative entries p", where p- is the probability of sampling a negative vector entry, then the expected number of samples get one negative vector is 1/p". Denoting p+ similarly, 1/p4 samples are expected for positive vector. In addition, each LR step in this approach requires d such samples respectively to make the linear equation system full-rank, which implics the expected sample size to be d-cxponential d (1/p" + +1/4). For other common input distributions such as Gaussian, the proportions of fully negative/ peepsoosiiveeeeeee vectors in sampled inputs are also expected to decrease exponentially as grows, as high-dimensional Gaussian random vectors are essentially concentrated uniformly in sphere (Johnstonc) 2007). Technical and experimental details about sample size expectations and the vanilla LR algorithm are further discussed in Appendix D
4 Nonparametric Learning: Layer 2
We present how we learn residual unit layer under Condition 2.1 (estimating B*): We first design an objective functional with the arguments being a matrix and a function. The objective uses expectation of loss over the true distribution generating the data and is uniquely minimized by [B*]-L and rectifier function (ReLU). We then formulate its ERM using nonparametric estimation as standard convex QP, further simplified as an LP that (in the noiseless case) has the same solution as the QP to learn layer 2.
4.1 Objective Design and Landscape
Consider the formulation of a residual unit as in Eq. D It is possible to rewrite the model as equation: C*y = (A'x)* + + x, where the output of the hidden neuron with skip addition is on both sides of the equation, and C"B' = Ia. We aim to estimate the inverse of B" by matrix variable C and the nonlinearity x + (A'z)* + by a function variable h. The objective is formulated risk functional by the L error between values respectively computed by C' and h,
(C,Ch) 1 x
(2)
where the estimator C Rddmm the domain of h the nonnegative contimuous Rdd + Rd function space, written as CO in shorthand. This objective is quadratic because the forward mapping a + h(())+++ + a and the backward mapping y + Cy are both linear w.r.t. C' and h, and the two are linearly combined in an T,2 norm. The objective in Eq. (2 is minimized by the ground-truth, i.c. C and æ + (A*x)*, is one of its minimizers. However, it is not simple to describe other variable values that minimize the objective if any exist. We give that detail under Condition 2.1 the minimizer of G2 is unique, as the exact ground- -ound-truth in the given domain.
22
Theorem 4.1 (objective minimizer, layer 2). Define G2(C,, h) as Eg. 2 where C E Rdxm, h E C2 Then under Condition 2.1 h2) reaches its zero minimum iff C B and h x (A
Technical details in Appendix F where we Lemma 4.2 (in Scction 4.3
to prove more general theorem which does not require Condition 2.1 and is sulficient for Theorem 4.1 In the next subsection, we construct the ERM of G2 and present our convex QP formulation.
SSetting à nonuegative ensures that a) only ReLU nonlincarity minimizes G2 (sce Theorem 4.1 and b) hts nomparametric estimator is linearly constrained (cxplained in Scction 4.2
off h a continuous function, only null of disontinuities possihle make G2 reach zero as its minimum. Setting continuous simplifies our theoretical results that still strictly support empirical discussion.
5

---

Published in Transactions on Machine Learning Research (11/2022)
4.2 ERM with Nonparametric Estimation is Convex QP
Consider the second layer objective (Eq. (2) with nonnegative continuous function space as the domain of h. We follow
Vapnik (1911) and define its standard empirical risk functional:
1 Σ (M(a + x -Cy(1) 2n sEin
(2,
(3)
The function variable h C2 can be optimized either parametrically nonparametrically. If we parameterize h such nonlinearity w.r.t. its parameters would make G2 lose its quadratic form. Instead, we estimate h nonparametrically: for each sample input x(0), we introduce variables g(() that estimate mapped values by h. This avoids introducing nonlincarity to the objective and keeps G2 quadratic. On the other hand, the domain of h, iee nonnegative continuous function space, turns into a set of linear inequalities constraints when optimizing the learning objective nonparametrically In this sense, learning the second layer of the residual unit can be formulated the following QP:
min C2 C,
ANPE
(C,3) = 2n
Σ RE(n)
elo + x0 -Cylo0 s.l. g(0) 20,
(4)
where E == ( is the nonparametric estimator of + (A'x)*
Nonparametric Estimation Validation: A solution to the ERM with nonparametric estimation, i.c. the QP, is guaranteed to be sufficient for minimizing the standard empirical risk functional (Eq. (3)). More specifically, assuming C and = = { are a solution to layer 2 QP (Eq. (4), we see now that C and
h h C2 such that (() = (()) minimize the empirical risk functional Fq. 33 Conversely, a minimizer of
the standard empirical risk Eq. (3). C and h, corresponds to solution to layer QP as we set {() h((x!)).
Therefore, minimizing G2 and solving layer 2 QP are equivalent problems.
The convexity of the QP: Eq. 4 is also guaranteed. First, its constraints are linear. Second, for each sample with index i E [n], the 2 norm wraps linearity w.r.t. C' and g()) Such formulation ensures the quadratic coefficient matrix is positive semidefinite. Thus, with the sum of convex functions still being convex, the QP objective (Eq. 4 becomes convex. Even without the knowledge of how samples are generated, this QP would be a convex program. Strict proofs are in Appendix G
Convexity:
4.3 LP Simplification
If there is feasible C such that Cy x 2 O holds for all æ E IRd then C and h: x x+ Cy - x always minimize J2 as zero, and thereby minimize the layer 2 objective (Eq. 2 Thus, we obtain a condition that is equivalent to G2 reaching the minimum in Theorem 4.1 and avoids randomness (see Lemma 4.2)
Consider single-sample error written as 92 (C, x; y) (2) + Cyll
Lemma 4.2. G2(C, h) reaches its zero minimum iff Cy x 2 0 holds for any x E Rdd and its corresponding residual unit output y, and h x + Cy-xx
The pointwise (for every x E Rdd) satisfaction of the incquality in Lemma 4.2 describes the solution space for the minimization of G2- The sufficiency of satisfying this inequality to minimize G2 is directly obtained by assigning
+ Cy - æ where C complics with Cy x 2 for all æ in the support space Rd The necessity of satisfying this inequality comes from its contraposition: If C violates the inequality, there must. be a non-null set of that yield the violation due to the continuity of Cy In this sense, the resulting G2 value becomes nonzero.
Empirically speaking, we cannot solve an inequality that holds w.r.t. to every point in the support space if we only observe finite samples. We can only estimate C' by solving the inequality that holds w.rtt. each sample. Following this, we formulate such estimation as find a feasible point in the space defined by a set of linear inequalities, each of which corresponds a sample: Cy x 2 0. Each point in the feasibility defined by the inequalities has one-to-one correspondence in the solution space to layer 2 QP

---

Published in Transactions on Machine Learning Research (11/2022)
Algorithm Learn ReLU residual unit, layer 2.
1: Input: {(xx(, y ) samples drawn by Eq.
Output: B, E. layer 2 and + (A'z)* estimate.
Go to line 4 if QP, line 5 if T.P.
4: Solve QP: Eq. 14 and obtain 22 minimizer, denoted by Ć S. Go to line 6.
5: Solve LP: Eq. (5) and obtain a minimizer C, then assign g()) +- Cyl() (1)
6: return
(Eq. 41:: C ++ (C,(Cy0-=()hee) he(m)) The set of incqualities can be solved by a standard LP with a constant objective and with constraints that are inequalities, i.e.
-
min const, s.t. Cy x 2 0, ViE [n].
(5)
With the one-to-one correspondences, LP: Eq. and QP: Eq.
have identical solution spaces (feasible
regions) for layer 2. Moreover, LP: Eq. is also convex program.
Algorithm summarizes the layer 2 estimator: Simply solve the QP QP/LF and return the inverse of Ć as the estimate of layer 2 weights and E as x - (A*x)* estimate. Regardless of time complexity, QP and LP in Algorithm I work equivalently since their solution spaces are equivalent to each other.
Our nonparametric learning directly finds a unique layer estimate under Condition 2.1 In the general case without Condition 2.1 (discussed in Appendix [F), nonparametric learning essentially reduces the possible values of B from Raxd to B scale-equivalent matrix space, where LR uses sampled data much more efficiently than vanilla LR on layer 2 (Section 3).
5 Nonparametric Learning: Layer 1
With layer learned, the outputs of the hidden neurons become observable. The two-layer problem is thereby reduced to single-layer. Consider a ground-truth single-layer model: h = (A'x)*. To construct a learning objective for this model, we rewrite the model as nonlinearity plus a linear mapping by A h = (-A*x) + A'x, where on both sides of the equation is the output of layer 1, and the nonlinearity is æ (- A'x) + The objective of layer formulated as:
1 Ex [[r(x)) Ax hi] 2
G (4,
(6)
where A E Rddd of the layer weights estimator, the domain of r is also Cou The minimizer A of the risk G2 falls into matrix space such that for any matrix A the space, each row of A is a scaled-down version of the same of A without changing the direction (Theorem 5.1
Theorem 5.1 (objective minimizer space, layer 1). Define GA,Ar)) Eg. where A E Edxd r E C Then G. G1 (A,r) reaches its zero minimum iff for each [d], Aj: A where kg 1, and xA*x) - diag(k) (k) x'x.
r: x
The scale equivalence in the solution space is derived from ReLU incquality: (x)+ 2 kz where 0 < k < 1. Let the j-th row of A be a scaled-down version of A", i.e. Aj.- = Ky where < kj < 1. According to the incquality, we have (4). x) 2 ky Aj, which indicates (A"x)** 2 (k) A'x. Thus, r minimizing G1 in Theorem 5.1 lies in feasibility Coo when A = diag(k) A
Due to the existence scale equivalence, we must compute the scale factor to obtain the ground-truth weights A". The scale factor kj is sufficiently obtainable with xA and (Aj,x) x) observable: Conditioned
on nonnegative ReLU input, we have a linear model A = ky A where A and A are observed.
We CVX Grant & Boyd 2014 2008 that calls SDPT3 Toh al.
1999 (a free solver under GPLv3 license) solves our
convex QP/L.P in polynomial time. See Appendix for technical details.
7

---

Published in Transactions on Machine Learning Research (11/2022)
Algorithm 2 Learn ReLU residual unit, layer 1.
1: Input: {(x11) h))) layer 1 samples.
Output: Á, laver estimate.
Solve QP: Eq. (7) or LP: Eq. (8) and obtain G minimizer, denoted by A, $. { is no longer needed.}
4: for all j E [d] do
kj < [R(h)) )), 1
(6)
6:
A Ajolkg {Rescale A.}
7: end for
8: return Á.
Theorem 5.2 summarizes layer scale factor property, allowing us to correct a minimizer of G1 to the ground-truth weights A' by computing a scalar for each row.
Theorem 5.2 (scale factor, layer 1). Assume A is a minimizer of G1. Then for any j E [d], (A,, / xA is always equal to the scale factor ki given that xA 0.
The elimination of randomness for G₁ follows the same pattern layer 2. If there is feasible A such that (A'za AA*))* Ax holds for all Rd, such A is solution to our objective by Eq. (6. We also have the following proposition that avoids randomness.
Lemma 5.3. Gi(A, reaches ils zero minimum is h Ax 2 0 holds for any E Rdd and ils corresponding hidden output h, and r: + h Ax.
We now turn into empirical discussion. Similar to layer 2, we formulate layer QP by its empirical objective with nonparametric estimation and linear constraints representing the nonnegalivity of r:
1 Σ (60)) + Ax (0) - (0 s.t. 110) 2 [n).
min ANPE (A, = 2n
(7)
EE(D)
where +- = [2 is the function estimator of x (A* diag(k) A where k refers to the scaling equivalence. Similarly, the solution space of QP: Eq.
7 can be represented by set of linear inequalities
constraints of the following efficiently solvable LP
min const, s.t. h( A
Ax 2 0, ViE [n].
(8)
Algorithm 2 describes how a layer is learned: First, G1 minimizer estimate Å obtained by solving the QP/I.P. Then for the j-th row, the scale factor ky is estimated by running LR on 1.f9) and ,,,²( s.t. 2/9) > 0 to correct Å, as A kyhy is an unbiased linear model given that hy > 0. By nonparametric learning, the value space of A is reduced from Raxd to (diag(k) A 1 k 1}, where LR uses sampled data much more efficiently than vanilla LR layer 1 (Section 3h
6 Full Algorithm and Analysis
The full algorithm concatenates Algorithms 1 and 2 in a layerwise fashion, with observations of input/output samples from the ground-truth network and follows these steps: a) Estimates layer and nonlinearity: w + (** by Algorithm 1 b) Estimates layer 1 by running Algorithun 2 on input samples and the monlinearity estimate. has provable guarantees. For empirical analysis, we use C, to denote the estimation of C" from n random samples. Similar notation is applied to other estimations. First of all, our methods solve respective layers, Algorithms and are strongly consistent. if any convex QPs/ PLs/ involved can be solved exactly.
Lemma 6.1 (layer 2 strong consistency). Under Condition 2.1 Cn
G.S. C and B,, a.s. B + co.

---

Published in Transactions on Machine Learning Research (11/2022)
For Cn In Appendix H prove its more general a.s. (almost sure) convergence without satisfying Condition 2.1 where the solution space to layer 2 objective is non-compact continuous set where all the elements are scaling equivalences. We use Hausdorff distance [Rockafellar & Wets 2009] as metric and prove that the empirical solution space a.s. converges to the thcorctical solution space. Then the more general 8.s. convergence holds with the strong consistency of layer 2 scale factor estimator where we use LR to estimate the scale factors.
For B, Using the continuous mapping theorem Mannn & Wald 1943). we directly propagate the strong consistency of C estimator to its inverse ' estimator.
According to full algorithm description, layer I estimation uses C,y( x(0 as the outputs where E [n]. Thus, the strong consistency of the hidden neuron estimator is also guaranteed by the continuous mapping theorem. Following the proof sketch of the C, a.s. convergence, we obtain the strong consistency of layer estimator (See Lemma 6.2
Lemma 6.2 (layer 1 strong consistency). An - A", 7 00.
By the continuous mapping theorem, the strong consistency of the full algorithm (Theorem 6.3 which is commonly defined by loss function that continuous on network weights, is implied by the strong consistency of network weights estimators (Lemmas 6.1 and 6.2 See Appendix H for proofs of strong consistency discussions in this section.
Theorem 6.3 (strong consistency). Define as L output loss. L(An, a.a. n + 00.
7 Experiments
In our experiments, we describe a first set of synthetic datasel experiments, that show that our algorithm identifies the true parameters from which the data were generated (Section 7.1 and then a second set of experiments that use our algorithm on standard real-world benchmark datasets (Section 7.2 In the appendices we provide further experiments. For example, in Appendix []] we describe what happens when the conditions required for the correctness of our algorithms are not satisfied.
7.1 Synthetic Data Experiments
We provide experimental analysis to demonstrate the effectiveness and robustness of our approach in comparison to stochastic gradient descent (SGD) L oulput loss: L(A, E || yll where we parameterize the output prediction by ý (Ax)* +x]. Our proposed methods outperform SGD in terms of sample efficiency and robustness to different network weights and noise strengths, which indicates a poor optimization landscape of L output loss for ReLU residual units.
Sctup: The ground-truth weights are generated through i.i.d. folded standard Gaussiar S and standard Gaussian for layer 1 and 2 respectively, i.e. A ii.d. | (0, 1), B i.id (000, 1). The input distribution is set to be an i.i.d. zero mcan Gaussian-unifon mini-batch empirical losses of L(A, B) with batch size 32 for 256 epochs in each learning trial. We apply time-based learning rate decay 7, = n (1 + T) with initial rate 700 = 10-3 and decay rate 7 = 10-5, where T the epoch number. The above hyperparameters are tuned to outperform other hyperparameters learning ReLU residual units in terms of output errors.
equal mixture N (-0.1, - (-0.9, SGD is conducted on
Evaluation: We use relative errors to measure the accuracy of our vector iacoor//ma matrix estimates: For network with weights A and B and its teacher network with weights A and B', a) layer 1 error refers to ||A A ||*]]] similar to layer 2. b) output error refers to É [|ly - f ||yll] by test data. Due to the equivalence between the solution spaces of our QP and LP without label noise, we choose LP in noiseless experiments, referred to as "ours". In addition, to reduce variance, the results of learning the same ground-trutha are computed as means across 16 trials.
8 A folded Gaussian the absolute value of Gausslan, with p.d.f. p(xx) where AG, denoted as [M We use falded Gaussian to ensure layer weights are nonnegative.

---

Published in Transactions on Machine Learning Research (11/2022)
SG0
866
10
Table 1: Means Standard deviations of net- work estimate errors for different network weights. Values are computed from the process of learning 128 different ground-truth networks with
Timmmson
14
14
16
03
18
18
02
20
01
= 16. 512 training samples are drawn for each
150
224 256 320
190 192 224
288 384
learning trial.
Sample
Samppl
Figure Output errors by SGD and our method for different dimensions and sample sizes. For the same d, we fix the ground-truth network as sample size grows.
Layer
Layer 2
Output
Mean
Std
Mean
Std
Mean
Std
SGD Ours
0.715 0.039
0.090
1.203
0.134
0.431
0.038
0.008
R
RS 0
0.055
0.008
0.5
1.4
1.2g
Ostput Exvor
Lager Errrr
Lager Error
0.3
SGD
0.6
SGD
0.8
S60
LP
LP
0.2
OP
0.4
QP
0.8
0.4
0.1
0.2
0.2
0.4
Noise Strength
Noise Strength
Noise Streegtth
Figure 2: Respective errors of layers 1 and 2 and outputs of different label noise strengths for SGD, LP and QP. We fix the ground-truth weights with d 10 and only the noise strength varies. 512 training samples are drawn for each learning trial.
Sample Efficiency: Consider Figure [ It depicts the variation in the prediction errors (warmer color, larger error) as a function of d (input dimension) and the number of samples the learning algorithm using. We compare SGD against our algorithm. We observe that our approach to the estimating the neural network is more sample efficient. For SGD, the estimation is relatively easy with only up to 10 dimensions. As expected, once the dimension grows, the sample size required for the same level of error our method is larger. Still, overall, method is capable of learning robustly with small sample sizes and more efficiently than SGD even for larger sample sizes.
Network Weight Robustness: This experiment aims to verify whether our method can learn a broader class residual units. In Table 1, we see our method shows a light-tailed distribution with nearly-zero means and standard deviations for layers 1 and 2, and output errors across various ground-truth networks, whereas SGD is less robust in the same context. Our method shows strong robustness to network weight changes, indicating its applicability across the whole hypothesis class.
Figure 2 confirms the robustness of our methods when output noise exists. Samples are generated by a ground-truth residual unit with output noise being i.id.. zero-mean Gaussian in different strengths (i.e. standard deviations). We try both QP and LP because in noisy setting the two approaches are not equivalent w.r.t. the solution space First, SGD always gives larger errors than our methods, even though is hardly affected by tuning the noise strength. For QP/LP, the errors for layer 1, and output grow almost linearly as noise strength increases, indicating that both QP/LP learn the optima robustly when output noise is present, where QP slightly outperforms L.P.
Noise Robustness:
S Appendix A for noisy model discussion.
10

---

Published in Transactions on Machine Learning Research (11/2022)
32
59
0.2
Output Erroz [in logso)
Outpps Earoe (in logis)
07
Uhdr
Output Eiros (Gn logoo
1e-0r
LP-07
undr
000-07
LP-d7
4.2
500
uhdt
044
044
-.5
0.6
/12
10
Rumning Time (6)
Running Time (6)
Running Time (8)
Figure 3: Output errors against running time by SGD and our LP algorithm for different dimensions of networks. For each dimension size of d = 8, d = 16 and d = 32, we report the learning curves of SGD and the final output error of our LP algorithm against time used on different ground-truth networks. We used 512 training samples, drawn for learning each ground-truth network. SGD has different epochs, while the LP algorithm runs once. (CPU specification: 2.8 GHz Quad-Cort Intel Core 17.)
SGD
LP
8
16
10
16
d=
82
Layer 2 Eivoor
Loyer 2 Error
10
R(B")
k(B")
Figure 4: Layer 2 errors against layer 2 ground-truth weight condition numbers for different dimensions of networks by SGD and our LP algorithm. Each data point is the mcan across lcarning 32 different ground-truth networks with the same pair of and condition number for B". The condition number denoted by x(B"). We used 512 training samples, drawn for learning each ground grunnd-truhh network.
Rumning Time Efficiency versus SGD In Figure we compare the running time of our algorithm against the rumning time of SGD for ground-truth networks sampled at random. The running time of our algorithm is siguificantly lower, with an error level which is also significantly lower. Furthermore, this is retonstrated across imput dimensions, where the difference between the running time of SGD until convergence and our algorithm's 's running time increases as d increases. In addition, the running time of our algorithm is fixed, and does not depend on the ground-truth network, while the running time SGD varies based on the network sampled.
Layer 2 Weights Condition Number Robustness Our algorithm depends on matrix-inversion step to obtain the estimated parameters. This affects the estimation of B*. Due this, we further investigate the effect of the condition number of B* in the ground-truth parameters the accuracy of estimation. For this experiment, to obtain ground-truth network parameters with different condition number, we follow the procedure of Ge et al. (2019), and multiply a diagonal matrix with exponentially-droppnng values on the Ge
diagonal (X- for the i-th element,) by two random orthonormal matrices, U and VT, on the left and on the right respectively: B = U diag (X-1,... x-...".---dyy
In Figure we compare the effect of the condition mumber of B* on SGD and on our algorithm. SGD turns out to be quite sensitive to the condition number, especially for lower dimensions. Our algorithm, the
11

---

Published in Transactions on Machine Learning Research (11/2022)
Table 2: Results on regression benchmarks. We give RMSE on several datasets with our algorithm (QP), backpropagation with SGD and backpropagation initialized with our algorithm estimates (SGD+QP). Numbers after slash denote the (average) number of epochs required for backpropagation to converge.
Root Mean Squared Error
Datasct
QP
SGD
SGD+QP
HOUSING
19.46
18.08
459
12.43
1379
ELEVATERSSSO
0.00240
0.01360
8638
0.00209 843
DELTAAILERONS
0.00030
0.00216
16555
0.00030 /
ATLERONS
0.00070
0.00193
8039
0.00023 / 1047
WINE
2.73
2.49 / 5270
1.48 5610
WHITEWINE
2.99
2.59
/ 8200
1.61
3129
JIGSAW
1.17
2.45 / 6731
0.92
2413
other hand, is almost not affected by the condition number, with final estimation error consistently close to 0, recovering the matrix B"
7.2 Experiments with Regression Benchmark Datasets
In this set of experiments, we test our algorithm and compare it against stochastic gradient. descent for four datasets: HOUSING (506 examples, 13 features), DELTAELEVATORS (9,517 examples, features), DELTAAILERONS (7,129 examples, 5 features), AILERONS (7,154 examples, 41 features), WINE (1,599 examples, 11 features), WHITEWINE (4,898 examples, 11 features) and JIGSAW (47,991 examples, 100 features). The first six datasets are standard benchmark datasets taken from Delve and the UCI Machine Learning Repository! The last dalasel, JIGSAW, is bigger with its goal to use word Fest embbddingg of tweets to predict their level of taxicity. For this set of experiments, with all datasets, we use the MOSEK solver with an academic license (ApS) 2019).
In all of our experiments, we report five-fold cross-validation results, where the first fold is used to tune the hyperparameters, and the last fold used as both a validation set for early stopping (first half) and to report the results (sccond half). The models we use for backpropagation and our algorithm are identical, in the form of Eq. [ We report (the fold-average) Root Mean Square Error (RMSE), defined as the square-root of the average of the squared deviations between the predicted value and the true value. Each fold is run with five different random seeds to initialize the backpropagation algorithm (results are averaged).
To satisfy the constraint on the length yf we duplicate the regression target multiple times, each time adding Gaussian noise as large as 0.1 of the standard deviation of the regression target. More specifically, let y be *,00 = (1 + 0.1G., (o1G),))((++0- mod d) the vth example in a dataset. Then, we create a new y *+) E Rd such that yj
for 2 2 (for i i= 1, we add no noise, and just copy )),, where Si are Gaussians with the mean being the standard deviation of y over the dataset.
With backpropagation, we use SGD with learning rate of 0.000001 and batch size of 500. We run backpropagation until the mean squared error does not change between epochs within fraction of 1/10000. We experiment with two types of initializations for the backpropagation algorithm: one in which we initialize all the weights randomly with a standard Gaussian distribution, and one in which we initialize it with the result of our quadratic programming algorithm. It has recently been shown that initializing a ResNet. with positive values (or even just zero-one values) yields an improvement in estimating the network with backpropagation Zhao et al. (2022), supporting our use of the nonnegativity constraint for the first layer. An additional advantage of such an approach is that it removes the randomness that characterizes neural network learning.
10 http://www...ooooo.eaaaaa//////a https://archive.. ics. edd/a///////// html https://aasteext.co
12

---

Published in Transactions on Machine Learning Research (11/2022)
Table 2 gives the RMSE values, comparing QP algorithm and the backpropagation algorithm. We note that our algorithm is especially potent when used to ialize the backpropagation algorithm: not only then it achieves lower RMSE on the test set, but it also does so in fewer iterations.
8 Conclusion
In this paper, we address the problem of learning general class of two-layer residual units and propose algorithm based landscape design and convex optimization: We demonstrate firstly that minimizers of our objective functionals can express the enact ground-truth network. Then, we show that the corresponding ERM with nonparametric function estimation can be solved using conver QP/LP, which indicates polynomial--ine solvability w.r.t. sample size and dimension. Moreover, our algorithms that are used to estimate both layers as well as the whole networks are strongly consistent, with very weak conditions on input distributions.
Limitations and Future Work The main limitation of our work is that the use of Le loss with the QP objective is not readily adaptable to other loss functions. Our preliminary experiments with classification datasets demonstrate that while our algorithm behaves better than L2 backpropagation on such datasets, using the log-loss is more effective for these datasets. We leave it future work to generalize our QP to a convex program with an arbitrary loss.
Our algorithm is not yet scalable for large datasets. We believe the learning algorithm could still be added to the MT. toolkit. for problems at a smaller scale for which we need a predictor, problems where linear regression is a good fit. Finally, we note that while we have nonnegativity constraints on the parameters (A), the class of networks we learn is expressive. Previous work that has similar nonnegativity constraints includes binary neural networks (Courbariaux et al., 2015) and others, without 0/11 constraint (Chorowski & Zurada 2014
Hosseini-Ase Asl et al. 20155). We leave it for future work to alleviate this constraint. Recently, Zhao et al. 2022 showed that initializing ResNets with 0/1 weights is effective for training as random initialization.
Acknowledgments
We thank Yftah Ziser, the anonymous reviewers and the action editor for their useful feedback and comments. Computational resources and software were partially provided by Edinburgh Parallel Computing Centre and through the Amazon Enterprise License for MATLAB.
References
Zeyuan Allen-Zhu and Yuanzhi Li. What can ResNet learn efficiently, going beyond kernels? In Advances in Neural Information Processing Systems, volume 32, 2019.
Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization in overparameterized neural networks, going beyond two layers. In Advances in Neural Information Processing Systems, volume 32, 2019.
Mosek ApS. MOSEK optimization toolbox for MATLAB. User's Guide and Reference Manual, Version, 4, 2019.
Yossi Arjevani and Michael Field. Analytic study of families of spurious minima in two-layer ReLU neural networks: tale of symmetry ii. In Advances in Neural Information Processing Systems, volume 34, 2021.
Sanjeev Arora, Aditya Bhaskara, Rong Ge, and Tengyu Ma. Provable bounds for learning some deep representations. In Proceedings of the 31st International Conference on Machine Learning, volume 32, pp.
584-592. PMLR, 2014.
Miriam Ayer, Daniel Brunk, George M. Ewing, William T. Reid, and Edward Silverman. An empirical distribution function for sampling with incomplete information. The Annals of Mothematical Statistics, pp. 641-647, 1955.
13

---

Published in Transactions on Machine Learning Research (11/2022)
Eugene Belilovsky, Michael Eickenberg, and Edouard Oyallon. Greedy layerwise learning can scale to ImageNet. In Proceedings of the 36th International Conference on Machine Learning, volume 97, pp- 583 593. PMLR, 2019.
Yoshua Bengio and Olivier Delallcau. On the expressive power of deep architectures. In Algorithmic Learning Theory, pp. 18 36. Springer, 2011.
M. Émile Borel. Les probabilités dénombrables et leurs applications arithmétiques. Rendiconti del Circolo Matematico di Palermo (1884-1940), 27(1):247-271, 1909.
Hugh D. Brunk. Maximum likelihood estimates of monotone parameters. The Annals of Mathemalical Statistics, pp. 607-616, 1955.
Alon Brutzkus and Amir Globerson. Globally optimal gradient descent for a ConvNet with Gaussian inputs. Proceedings of the 34th International Conference on Machine Learning, volume 70, pp. 605-614. PMLR, 2017.
Yining Chen and Richard J. Samworth. Generalized additive and index models with shape constraints. Journal of the Royal Statistical Society: Series B (Statistical Methodology). 78(4):729-78) 754, 2016.
Jan Chorowski and Jacek M. Zurada. Learning understandable neural networks with nonnegative weight constraints. IEEE Transactions on Newral Networks and Learning Systems, 26(1):62-66) (2-69, 2014.
Matthieu Courbariaux, Yoshua Bengio, and Jean-Pierre David. Binaryconnect: Training deep neural networks with binary weights during propagations. In Advances in Neural Information Processing Systems, volume 28, 2015.
Simon S. Du and Surbhi Goel. Improved learning of see-hidden-layer convolutional neural networks with overlaps. arXiv preprint arx: 10:::8000000 007907798, 2018.
Simon S. Du, Jason D. Lee, Yuandong Tian, Aarti Singh, and Barnabas Poczos. Gradient descent learns one-hidden-layer CNN: Don't be afraid of spurious local minima. In Proceedings of the 35th International Conference on Machine Learning, volume 80, pp. 1339-1348. PMLR, 2018.
Tolga Ergen and Mert Pilanci. Implicit convex regularizers of CNN architectures: Convex optimization of two- and three-layer networks in polynomial time. In International Conference on Learning Representations, 2021a.
Tolga Ergen and Mert Pilanci. Revealing the structure of deep neural networks via convex duality. In Proceedings of the 38th International Conference on Machine Learning, volume 139, pp. 3004 3014. PMLR, 2021b.
Julius Farkas. Theorie der einfachen ungleichungen. Journal für die reine und angewandte Mathematik (Crelles Journal), 1902(124):1 27, 1902.
Rong Ge, Jason D. Lee, and Tengyu Ma. Learning one-hidden-layer neural networks with landscape design. Tn International Conference on Learning Representations, 2018.
Rong Ge, Rohith Kuditipudi, Zhize Li, and Xiang Wang. Learning two-layer neural networks with symmetric inputs. In International Conference on Learning Representations, 2019.
Surbhi Goel and Adam R. Klivans. Learning neural networks with two nonlinear layers polynomial time. In Proceedings of the 32nd Conference on Learning Theory, volume 99, pp. 1470-1499. PMLR, 2019.
Surbhi Goel, Adam R. Klivans, and Raghu Meka. Learning one convolutional layer with overlapping patches. In Proceedings of the 35th International Conference on Machine Learning, volume 80, pp. 1783-1791. PMLR, 2018.
14

---

Published in Transactions on Machine Learning Research (11/2022)
Michael Grant and Stephen Boyd. Graph implementations for nonsmooth convex programs. In V. Blondel, S. Boyd, and H. Kimura (eds.), Recent Advances in Learning and Control, Lecture Notes in Control and Information Sciences, pp. 95 110. Springer- Verlag Limited, 2008. http://stanforddeddd/bby//o//// dcp.html
Michael Grant and Stephen Boyd. CVX: MATLAB software for disciplined convex programming, version 2.1. http://cvxr.com// March 2014.
Adityanand Guntuboyina and Bodhisattva Sen. Nonparamctric shape-restricted regression. Statistical Science, 33(4):568 594, 2018.
James Douglas Hamilton. Time series analysis. Princeton University Press, 2020.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE Conference on Computer Vision and Pallern Recognition, pp. 770 778, 2016a.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Identity mappings in deep residual networks. In European Conference on Computer Vision, pp. 630-645. Springer, 2016b.
Ehsan Hosscini-Asl, Jacek M. Zurada, and Olfa Nasraoui. Deep learning of part-based representation of data using sparse autoencoders with nonnegativity constraints. JEEE Transactions on Neural Networks and Learning Systems, (7(1))22486 2498-2498, 2015.
Majid Janzamin, Hanie Sedghi, and Anima Anandkumar. Beating the perils of non-convexity: Guaranteed training of neural networks using tensor methods. arXiv preprint arXic:1506. 154,:.083,7, 2015.
Florian Jarre. On the convergence of the method of analytic centers when applied to convex quadratic
programs. Mathematical Programming, 49(1-3))341-356 1990.
Robert Jemnrich. Asymptotic properties of non-lineat least squares estimators. The Annols of Mathematical Statistics, 40(2):633 643, 1969.
Tain M. Johnstone. High dimensional statistical inference and random matrices. In Proceedings of the International Congress of Mathematicians Madrid, August 22 30, 2006, pp. 307 333, 2007.
Sham M. Kakade, Varun Kanade, Ohad Shamir, and Adam Kalai. Efficient learning of generalized linear and single index models with isotonic regression. In Advances in Neural Information Processing Systems, volume 24, 2011.
Narendra Karmarkar. A new polynomial-time algorithm for lincar programming. In Proceedings of the 16th Annual ACM Symposium on Theory of Compuling, pp. 302 311, 1984.
Yoon Kim. Convolutional neural networks for sentence classification. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 1746-1751 Association for Computational Linguistics, 2014. doi: 10.3115/11/D14-1111 URL attpp://accaattooogg.ooo//444
Mikhail K. Kozlov, Sergei P. Tarasov, and Leonid G. Khachiyan. The polynomial solvability of convex quadratic programming. USSR Computational Mathematics and Mathemotical Physics, 20(5):223-2) -288, 1980.
Alex Krizhevsky, Iyya Sutskever, and Geoffrey E. Hinton. ImageNet classification with deep convolutional neural networks. In Advances in Neural Information Processing Systems, volume 25, 2012.
Arun K. Kuchibhotla, Rohit K. Patra, and Bodhisattva Sen. Semiparametric efficiency in convexity constrained single-index model. Journal of the American Statistical Association, pp. 1-15, 2021.
Yann LeCun, Léon Bottou, Yoshua Bengio, Patrick Haffner, et al. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278-23)) 2324, 1998.
Yuanzhi Li and Yang Yuan. Convergence analysis of two-layer neural networks with ReLU activation. In Advances in Neural Information Processing Systems, volume 30, 2017.
15

---

Published in Transactions on Machine Learning Research (11/2022)
Roi Livni, Shai Shalev-Shwarte and Ohad Shamir. On the computational efficiency of training neural networks. In Advances in Neural Information Processing Systems, volume 27, 2014.
David G. Luenberger. Oplimization by vector space melhods. John Wiley & Sons, 1997.
Andrew L. Maas, Awni Y. Hannun, and Andrew Y. Ng. Rectifier nonlinearities improve neural network acoustic models. In Proceedings of the 30th International Conference on Machine Learning Workshop on Deep Learning for Audio, Speech and Language Processing, 2013.
Henry B. Mann and Abraham Wald. On stochastic limit and order relationships. The Annals of Mathematical Statistics, 14(3):217-22) 1943.
Mary C. Meyer. simple new algorithm for quadratic programming with applications in statistics. Commu- nications in Statistics Simulation and Computation, 42:1126 1139, 2013.
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 on Machine Learning, volume 162, pp. 15770-15816. PMLR, 2022.
Renato D. C. Monteiro and Ilan Adler. Interior path following primal-dual algorithms. part ii: Convex quadratic programming. Mathematical Programming, 44(1):43 66, 1989.
Katta G. Murty. Computational complexity of parametric linear programming. Mathematical Programming, 19(1):213 219, 1980.
Vinod Nair and Geoffrey E. Hinton. Rectified linear units improve restricted Boltzmann machines. In Proceedings of the 27th International Conference Machine Learning, pp. 807-814, 2010.
Mert Pilanci and Tolga Ergen. Neural networks are convex regularizers: Exact polynomial-time convex optimization formulations for two-layer networks. In Proceedings of the 37th International Conference on Machine Learning, volume 119, pp. 7695-7705. PMLR, 2020.
Guillaume Rabusseau, Tianyu Li, and Doina Precup. Connecting weighted automata and recurrent neural networks through spectral learning. In Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, volume 89, pp. 1630-1639. PMLR, 2019.
R. Tyrrell Rockafellar and Roger J-B Wets. Variational analysis, volume 317. Springer Science Business Media, 2009.
Olga Russakovsky, Jia Dong, Hao Su, Jonathan Krause, Sanjeev Satheesh, Scan Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, et al. ImageNet large scale visual recognition challenge. International Journal of Computer Vision, (1:(3):211 252, 2015.
Arda Sahiner, Tolga Ergen, John M. Pauly, and Mert Pilanci. Vector-output ReLU neural network problems are copositive programs: Convex analysis of two layer networks and polynomial-ting algorithms. In International Conference on Learning Representations, 2021.
Brian K. Schmidt and T. H. Mattheiss. The probability that a random polytope is bounded. Mathematics of Operalions Research, 2(3):292 296, 1977.
Emilio Scijo and Bodhisattva Sen. Nonparametric least squares estimation of a multivariate convex regression function. The Armals of Slatistics, 39(3):1633- 1657, 2011.
Pranab K. Sen and Julio M. Singer. Large sample methods in statistics: an introduction with applications, volume 25. CRC Press, 1994.
Alexander Shapiro, Darinka Dentcheva, and Andrzej Ruszczyúski. Lectures stochastic programming: modeling and theory. SIAM, 2014.
Mahdi Soltanolkotabi. Learning ReLUs via gradient descent. In Advonces in Neural Information Processing Systems, volume 30, 2017.
16

---

Published in Transactions on Machine Learning Research (11/2022)
Ilya Sutskever, Oriol Vinyals, and Quoe V. Le. Sequence to sequence learning with neural networks. In Advances in Newral Information Processing Systems, volume 27, 2014.
Yuandong Tian. An analytical formula of population gradient for two-layered ReLU network and its applications in convergence and critical point analysis. In Proceedings of the 34th International Conference on Machine Learning, volume 70, pp. 3404-3413, 2017.
Kim-Chuan Toh, Michael J. Todd, and Reha H. Tütüncü. SDPT3 MATLAB software package for semidefinite programming, version 1.3. Optimization Methods and Software, 11(1-4):545 581, 1999.
Osaba D. Toth, Joseph O'Rourke, and Jacob E. Goodman. Handbook of discrete and computational geometry. CRC Press, 2017.
Leslie G. Valiant. A theory of the learnable. Communications of the ACM, 27(11):113-11142 1984.
Constance van Eeden. Maximum likelihood estimation of ordered probabilities, 2. Stichting Mathematisch Centrum. Statistische Afdeling, (S 196/56), 1956.
Vladimir Vapnik. Principles of risk minimization for learning theory. In Advances in Neural Information Processing Systems, volume 4, 1991.
Vladimir Vapnik. The nature of statistical learning theory. Springer Science & Business Media, 1999.
Shanshan Wu, Alexandros G. Dimakis, and Sujay Sanghavi. Learning distributions generated by one-layer ReLU networks. In Advances in Neural Information Processing Systems, volume 32, 2019.
Qiuling Yang, Alireza Sadeghi, Gang Wang, and Jian Sun. Learning two-layer ReLU networks is nearly easy learning linear classifiers on separable data. IEEE Transactions on Signal Processing, 69:4416-4444 2021.
Yinyu Ye and Edison Tse. An extension of Karmarkar's projective algorithm for convex quadratic programming. Mathematical Programming, 44(1-3):157 179, 1989.
Xiao Zhang, Yaodong Yu, Lingxiao Wang, and Quanquan Gu. Learning one-hidden-layer ReLU networks via gradient descent. In Proceedings of the 22nd International Conference Artificial Intelligence and Stalislics, volume 89, pp. 1524 1534. PMLR, 2019.
Yin Zhang, Richard A. Tapia, and John E. Demnis, Jr. On the superlinear and quadratic convergence of primal-dual interior point linear programming algorithms. SIAM Journal Optimization, 2(2):304-33) 324, 1992.
Jiawei Zhao, Florian Tobias Schaefer, and Anima Anandkumar. ZerO initialization: Initializing neural networks with only zeros and ones. Transactions Machine Learning Research, 2022. URL https:
//openreview.crm wttp://www....eooooo///////////a
Kai Zhong, Zhao Song, Prateek Jain, Peter L. Bartlett, and Inderjit S. Dhillon. Recovery guarantees for ono-hidden-layer neural networks. In Proceedings of the 34th International Conference Machine Learning, volume 70, pp. 4140-4149) 2017.
Appendices
We include an outline of the appendices:
Appendix A A brief discussion of our learning algorithms a noisy context, referring the LP slack variable technique that is used in our experiments with noise in the main paper. Also, this section provides insight to potential future direction of this work.
Appendix detailed explanation of the computational complexity and the methods through which the QPs/LPs in this paper solved.
17

---

Published in Transactions on Machine Learning Research (11/2022)
Appendix A preliminarily proposed general optimization formula for the extension of learning multi-layer ResNets, to show the scalability of our algorithm.
Appendix D A formal result and an empirical validation of the example given in the main paper in the context of the vanilla línear regression method (Section 3
Appendix
generalization of layer 2 learning to the case where Condition 2.1 is not satisfied.
Appendix
Proofs regarding the minimizers of the objective functions we
Appendix
G
Proofs that justify the convexity of our QPs.
Appendix Proofs that show our estimation algorithm is strongly consistent.
Appendix sample complexity justification of how our QP /LP approaches improves the exponential convergence rate that the vanilla LR approach (Section 3 has.
Appendix J Experiments with negative entries in A and a demonstration of the practicalities of the nonnegative entries assumption.
A
Discussion: Noisy Model
Here, we discuss our learning methods in the noisy case. We introduce output noise to our model, namely
y= B" (A'x) +2,
where the label noise z E Rd is an i..d. random vector with respect to each component, satisfying E [z] = 0. In addition & and x are statistically independent.
Taking layer 2 as an example, our original objective functional does not reach zero by substituting the ground-truth: G2(C*, x )A*=))> = Ex||["²z|[]] T C*C* where is the noise strength. However, if layer 2 is well conditioned, the ground-trute will still assign value close zero to the objective. In this sense, with Gz's continuity, the ground-truth can approximately minimize G2, which validates our QP approach in terms of learning noisy residual units.
Our original LP (Eq. 5 fails to give feasible solutions due to possible violation of the inequality C'yy x 2 0, since C*y - x = xA'x) + C" z is not necessarily an entrywise nonnegative vector because the term C z might have negalive entries. So we introduce slack variables (()) to soften the constraints:
ΣΣ C iE[n]
min C,Z
s.t. Cy x > ((()) (()) 0.
For sample (z=(), ()) with noise 200, if (A'z( C² (1) then its I norm would be added to the
objective. This method remedies violations to the inequality C"y O. With access to sufficiently large sample and with the "stability" assumption, our solution Ó would be close to C since large deviations seldom rise and their penalties are diluted in the objective.
B Discussion: Solving Convex Programs
The thcoretical foundation of solving convex QP and LP has been driven to maturity in terms of computational complexity (Kozlov el al. 1980 Murty 1980) and convergence analysis (Jarre 1990 Zhang el al.) 1992). The time complexity for a convex QP/LP number of bits in the input (Yo & Tse 1989). For example, under Condition 2.1 N d2 nd for the QP because the matrix variables have d' scalars and the function estimators have nd scalars. Similarly we have N = d2 for the noiseless I.P and N d² + nd for the noisy L.P. It is guaranteed that primal-dual interior
LP is analyzed in terms the number of scalar variables N and the
18

---

Published in Transactions on Machine Learning Research (11/2022)
Algorithm 3 Learn ReLU residual unit by LR.
1: Input: {(x(1, , ) samples drawn by Eq. 1
Output: Á, B, estimated weight matrices.
B < (ax y) [(x() ( m/2] x < <0).
Đ + [R( y) {(x(), ()) (m/2]]+1 x > 0}. {the estimation of B" (A* + +.)]
5: Solve full-rank linear equation system A return Ā Ia. B.
point methods can solve the convex QP/LP in a polynomial number of iterations O(vNL), where each iteration costs at worst ((22.5) arithmetic operations from the Cholesky decomposition for the needed matrix inversion MMontciro & Adler 1989 Karmarkar 1984). This indicates that our QPs/LP /Ls are guaranteed be solvable in O(N*L) arithmetic operations, which is generally an Oppoly(n, m, d, L)) complexity.
N
To solve convex QPs/LPs in this paper, mostly CVX, commonly used package for specifying and solving convex programs (Grant & Boyd 2014 2008). For both QPs and LPs, CVX calls a solver, SDPT3 (Toh et al. 1999 which is specified for www.eeiinttniiaaiiiieeiieeeeeeee methods with the computational complexity mentioned above. Experimentally, SDPT3 indeed specifies and solves our programs fast and makes our numerical results robust and stable.
programming and applies interior-point
C Discussion: Extension to Multi-Layer
In this appendix, propose generalized optimization formula of nonparametric learning of multi-layer residual networks to show that algorithm is scalable. Assume we have L-layer network of the form
To x
Ti (W2 + l= L....- L-1
Wi-1rt-11
We can scale the objective to use nonparameter variables (&) he(c-1) to estimate every ReLU activation tW in this nelwork, Generally, for the I-th ReLU we can have the outer layer objective
+ ..... + <l0 + (0 vihl s.t. ( 20
min V
where hat denotes estimated values and h 1 y and its corresponding inner layer objective
Φ + Wi-1 + - ( m01)) -/(0 s.t. Φ 2 0, el 2 0.
min 802h W
We can apply techniques, c.g., tune the combinations of those objectives with respect to layers or whether to have a hat or not, or even get them weighted, keep its convex quadratic form and at the same time improve its optimization landscape. Specifically when 2, this becomes the two-layer ResNet learning discussed in the main paper.
D Vanilla Linear Regression: More Details
Algorithm 3 gives the full list of steps of learning two-layer residual units by LR, where we first split the drawn samples into two halves for the respective two key steps, then for both halves we filter negative and positive vectors, respectively. By running LR on both filtered sets we obtain an estimation of the ground-truth network.
In the following sections, we formalize this intuition and describe the exponential sample complexity of this approach under entry-wise i.i.d. setting example of the inefficiency of this method.
19

---

Published in Transactions on Machine Learning Research (11/2022)
Theorem D.1 (exponential sample complexity, vanilla LR). Assume the input vectors are i.i.d. d. with respect to each component. Then Algorithm 3 learns neural network from ground-truth residual unit with at least. O (d. 2d+1) expected number of samples.
Proof. For each j E [d], let P3 be the marginal probability of xy being positive, i.e. P, = P(x, 0) 0. Thus, the probability that sample is positive P(x 0) = -- P3. Then the expected number of sampling trials to obtain d positive samples is d/ [[j Pj- Similarly, the expected number of sampling trials to obtain d uegalive samples is d/ [[eete| [1 11-P P3 P(x; = 0)] Let n be random natural number s.t. with n samples the network has learned. The expected number of samples that guarantees successful learning is the sum of the two expectations
L[1|= d
] P3
h [1 P3 P(x, -0]
1
d
[e Pj + I1EE(1] (1 (1-
2 d.
II
PP (1 11-P.. P3)
jEld]
2 2
II
(P3 + 1-3)12
jE|d]
= d 2d+1
Thus E[n] 2 Old 24+1).
With an exponential sample complexity, the time complexity of the LR approach is thereby also exponential because filtering through all the samples costs time with the same complexity as the number of samples, even though the LR itself only costs polynomial time in the number of samples. To summarize, this vanilla LR approach learns exact ground-truth residual units but with exponential complexity terms of both computational cost and sample size. While this approach to learning residual unit such as ours is simple and intuitive, aim to improve this approach, making full use of all samples available.
Experiments: Sample Efficiency We present the results of the vanilla LR in learning the residual units. As discussed in Section 3 LR requires full-rank linear systems parameterized by samples to learn the exact ground-truth parameters. However, with degenerate linear systems, LR is completely incapable of learning the paramelers. Therefore, there exists a hard threshold for the number of samples required by LR that makes the linear equation system full-rank. With such a dichotomous constraint on LR learning, we take the learning success rate among 1000 trials as the metric to evaluate the performance of LR with different sample sizes and number of dimensions.
Table Ssoww the learning success rates with zero-mean Gaussian inputs. For each fixed number of dimensions, it appears there is a hard threshold that switches the learnability of LR. The exponential sample complexity is also reflected there as the number of dimensions grows linearly. Table shows the rates with input mean non-zero, where an overall decline in success rates happens. This observation is explainable because the bottleneck of LR learning is the lower value found between the probability of sampling a positive and a negative vector. positive mean reduces the probability of the latter, and thereby increases the sample size required.
E Generalization of Layer 2 Learning
In this appendix, we discuss how layer 2 is learned without satisfying Condition 2.1 We note that the fact that A is a scale transformation w.r.t. some components leads to scaling equivalence our layer 2 objective functional minimizers just in layer 1. To be more specific, we give a general version of Theorem 4.1
20

---

Published in Transactions on Machine Learning Research (11/2022)
Table Learning success rate vanilla LR on residual units with input x Lid. N (0, 1). The success rates shows an exponentially decreasing trend with the same number of samples. The sample sizes achieve close to the same rale grows exponentially as the number of dimensions grows linearly.
π2
Iel
1e2
5e2
1e3
5e3
le4
5e4
1e5
0.002
0.137
0.999
1
6
0
0.041
0.614
1
1
8
0
0
0.579
0.998
1
1
10
0
0
0
0
0.002
12
0
0
0
0.001
0.322
Table Learning success rate of vanilla LR on residual units with input x i.d. N (0.1, With the non-zero Gaussian mcan, the success rates show an overall decline compared with the rates shown in Table for zero-mean Gaussian inputs.
n
Le1
1e2
5e2
1e3
5e3
le4
5e4
1e5
0.001
0.122
0.996
1
1
6
0
0.030
0.346
1
1
8
0
0
0
0.116
0.792
1
1
10
0
0
0
0
0.619
1
12
0
0
0
0.001
that handles the case without Condition 2.1 and doscribes the scaling equivalence of G2 minimizers. Seo
Theorem E.1 for a formal description.
Theorem E.1 (objective minimizer space, layer 2, general). Let G2 be 1 [ll((x) (x) + Cyll²
functional, where C E igdxm h C2 Then G2 (C, h) reaches its zero minimum iff CB* diagg() where for each j [d].
a) I+ 55
I ki 11, if A" is scale transformation w.r.t. the j-th component. b) Kj = 1, A' is not a scale transformation w.r.t. the j-th component.
layer 1, the scaling equivalence in layer 2 can also obtained by assigning A as a scale transformation w.r.t. some component and using the propertics of the ReLU nonlincarity. See Appendix F.I for a detailed explanation of Theorem E.1 To obtain the scale factors and correct scale-equivalent G2 minimizer C to the ground-truth, [Cyl, kyxj given that x, 0. See Theorem E.2 and its proof for justifications of the linear models that are used to compute k.
observe linear models parameterized by the scale factors, where for each j E [d],
Theorem E.2 (scale factor, layer 2, general). Assume is a minimizer of G2 in the context of Theorem E.1 Then for any j [d], the following three propositions are equivalent:
a) A is scale transformation w.r.l. the j-th component. b) Cyy; /xj is constant ei given that x; < 0.
c) [Cyl, /x, is constant d given that x, >
Additionally, if one of the above three propositions is true, then kj cy.
21

---

Published in Transactions on Machine Learning Research (11/2022)
Algorithm Rescale a GNPE minimizer.
Parameters: etel > O, LR objective tolerance. Input: {(x10) (((0) y()
samples drawn by Eq. 11 C, GNPE minimizer.
Output: k, layer 2 scale factor estimate.
for each j [d] do
kj LR 3j (8)
[Cy("1]]
6: if the LR objective optimal (ky) > Etol then
Ky 1.
8: end if end for
10: return k.
Proof. For j E [d], we first prove a)
b)
c) From (Aj.)
= AAis eli e00) we have
[yyl;
[kyeloi|
(A'x)* +x]
xy
Xj.
xAj + + +X-
ki (A],)s;)) +Xy
Xj
Xj
lig.
Xj <0
My (Aj, +1),
Xj 20
Then we prove
a. =
3 E [d] and *ン s.t. Aj. + 0. Recall
kn (A)x))* + +x/
[Cyl,
Xj
Xj
The value of Xy' affects the value of [Cyl, /xy because AJ.r # O. In fact, from supp p(x) = Rd have supp p(xy' xx,) = IE, indicating that the value of [Cyl, /x, can never be kept as a constant when given both Xj < 0 and > 0 because Xy can be any real number.
With the exact derivations above, we are able to obtain a left inverse of B", namely C, that satisfies CB = Consider Eq. (1] left multiplied by B'C
B'Cy=y.
(9)
Eq. g is also a noiseless unbiased linear model where Cy and are observable, and thereby B is computable due to the easy solvability of its linearity.
Algorithm deseribes how residual unit second layer learned without satisfying Condition 2.1 We first solve the QP/L. and obtain scaling equivalence to estimated left inverse of B and the function estimate, namely Č and E. Then we compute the scale factor estimate & by running Algorithm where for each component index ground-truth layer is scale transformation, and if so, run LR to estimate the model [Cyl, kyæj, otherwise the scale factor is directly assigned by 1. Upon correcting Ò and É by k, we obtain a layer 2 estimate B by running LR to estimate the linear model Eq. 9 The strong consistency of our results in this appendix is justified Appendix H
[d], we first. use tolerance parameler
threshold to determine whether
F Exact Derivation of Objective Functional Minimizers
We give the exact derivation of the objective functional minimizers in the next two subsections. We begin with layer 2 and continue to layer 1.
22

---

Published in Transactions on Machine Learning Research (11/2022)
Algorithm 5 Learn ReLU residual unit layer 2.
1: Input: {(x(1, y (0)) samples drawn by Eq.
Output: B, E. layer 2 and + (A*z)* estimate.
Go to line 4 if QP, line if L.P.
4: Solve QP: Eq. 14 and obtain 22 minimizer, denoted by Ć, E. Go to line 6.
Solve LP: Eq- (5 and obtain a minimizer C, then assign g(()) x- Cyy() x+(1 for each i E [n].
Run Algorithm on ((x() " Heej)) Ć and obtain k.
B LR diag
(k) ( y
[E[m]
8: (00) + diag (At) (5()) + x00 - (*) for each E [n]. {Correct E to the function estimation of (A'x)"
return B, E.
F.1 Layer 2
Lemma 4.2 is proved as follows.
Proof- = ": Since h(x)) Cy 2 0, random vector h(x) Cy is always vector, which
implies G2(C, h)) 0. Hence == holds.
": Since [1(x) + Cyl1 2 0 we have
G2(C,,) h) = = ({ E ERR Rdd [[b(z)) + - Cyll > [[]{>>0}} =
(10)
where À is the Lebesgue mcasure on Rdd
Proof by contradiction: Assume that Arr Rdd, Fi E [d], s.t. (Cy' x'); < <0, where y' is the corresponding
network output. Let f(x) (Cy æ); which is continuous on Rd. Therefore for -f(x') > 0, 36 > 0, V æ E ((x;8) iee. ||æe x'll < 6,
(f()) f(x') <6 = 2f(x)) f(x) <0 = - 1 >0
[h(x)) Cyl, >0 = |1(x)) + Cyll² > 0.
4/2
Since (B(=:8)) [d/2 1)
8d > 0 and B(x; 6) is subset of the mcasured set in Eq. (10) have
contradiction. Thus Cy x
2 0 holds in a pointwise manner in Ed, indicating {æ E Rd
h(x) # Cy x
must be mull set. With h's contimuity, h must be a Cy Therefore = holds.
Lemma F.I. Cy - x 2 0 holds for any a e Rdd and ils corresponding outpul y only if CBB is diagonal matria.
Proof. Let = CB", We rewrite Cy x 2 0
D (A"x))+ + x 2
(11)
For further use, we substitute by and the resulting inequality D (-AAa)) a 2 0 still holds.
Added by Eq. 11 we have
D ([A #1) ax1 20.
(12)
Proof by contradiction: Assume is not diagonal, then 3i # j, such that Das # O. Consider the following two cases:
23

---

Published in Transactions on Machine Learning Research (11/2022)
a) Da. 0. We take the i-th row of Eq. 11
follows
Di,k (A x²* + + J4 2 Iz.
Let z-j O and 2j < O. Then Σx km Di,k ( Ak: xz) ) + 22
= Dig 2j <0 = 1.
b) Dry < O. We take the i-th row of Eq.
12 as follows
Σ k=1
Di.k Ak. -0 2 0.
Let x: = (A*)--o, where v = eb). Then Ei= Disk A x = Dii <0 = 1.
With Lemma and Lemma
we prove Theorem E. as follows.
Proof. With Lemma 4.2 we only need to prove Vo E Rd, Cy - xx x2 7 CB' = dk)
": We have
cy-x=Ch (A'x)* + + - x = diag(k) (A'x)) + + x.
(13)
For the i-th row of Eq. 13 consider the following two cases:
a) A x A,,r,, i.e. A is a scale transformation w.r.t. the i-th row. With 1477,
- S hy S we have
ICy æ1. ki (Ai + xi ks (A), + (k: 1) xz.
For H; 2 0, [Cy a) = (k:Ais ; + ki -5-1) x; 2 O.
For I₁ [Cy x = (k: -1) 24 2 0.
b) A, + Ag, With k; =1 we have
+ 2 0. CCy - x]; = kis xA + + - -x = (Ai
Hence " = " holds.
": Let D = CB". With Lemma F.1 is diagonal. Consider the following two cases:
a) A Ar, The i-th inequality can be written
[Cy - xx); Dis (AI, xz - 24
= D1, (A) + + (Di,: - 1) x, 0.
(14)
Proof by contradiction: need to find Rd which contradicts with Eq. 14 in the following
three cases:
a) If Dia < 0, then, x, > = Di, (At,at)* + (D,, 1) < 0 1.
b) If Daa > 1, then, H; < - 1.
c) O < Dí, < 14A then 3a > 0, s.t. D = 1+4,,+a* +a Letting 24 > O, we have
(Ai, +a) I; + Ag, + A + aa
(1.)
Dis (A),)r))* + +Di, 1)x;
1.
24

---

Published in Transactions on Machine Learning Research (11/2022)
Hence 1447 S Dis 1. b) A:. a o A,, i.e. 3j + i, s.t. Aig > 0. The i-th inequality can be written as
Cy x); = Da.s 2A + zt - Iz
Di (Ai. + (Di, 1) 2.0
(15)
Proof by contradiction: need to find Rd which contradicts with Eq. 15 in the following
three cases:
a) If Da, I 0, then, 2; > 0 - Di (4i.z) + (Di, 1) < = L.
b) If D1, > 1, then, 2, 50AA= 0 = 1.
Al
c) Iro < Di. 1, then, x; 0A < A
xi A < 0 = 1, where Ao ti, j.
Hence Di.-= 1.
Hence D CCB diag(k), and thereby holds.
F.2 Layer 1
The proof of Lemma 5.3 is similar to that of Lemma because the two lemmas follow the same idea, which is link objective functional minimization with always-hold inequalities. With Lemma 5.3 we prove Theorem 5.1 as follows.
Proof. With Lemma 5.3 only need to prove Yæ R., (A'x)* Ax 20 = ViE [d], A.. K; where 0 S K2 S 1. This is equivalent to what it is for single row, i.e. Vx E Rd (a x a 0 = a = kaa, where < < 1.
" " The case where a' = 0 is clear. a is not a zero vector and a ka", we have
a) If a x20, aa x
a x = Txx Ta == k)) a Tx 2 0.
b) If a < 0,
aa x
+
a _ ka" Tx 2 0.
Hence = holds.
- " If a = 0, a must. be a zero vector, otherwise let x = a, then -a Ta < =
1. If a a is not a zero
vector, consider two cases below:
a) If a * ka" where & 2 O. Let
||"'||
a", then æ is not zero vector, and
|all
a" x = ||a" 2 (cos 0 - 1) < 0, } - - (a' - -ax00+
T x = || a (1 cos 0) >
where denotes the angle between and a* b) If ka where &s 1, then let a we have
(a x
aTx (1 (1- k1a <0 - 1.
Hence kat where 0 5 k 1 if a* is not zero, and thereby = holds.
G
QP Convexity
The LPs in the main paper trivially convex. So in this appendix, only justify the convexity of our QPs: We first prove the convexity of single-sample objectives, then the convexity of the empirical objectives with nonparametric estimation, i.e. GNPE. and ČNPE is obtained by the convexity of convex function summations.
Lemma G.I. Suppose fuu) TTu blla where is real matria. Then f is conver w.r.l.
25

---

Published in Transactions on Machine Learning Research (11/2022)
Lemma G.1
easily obtained since the Hessian (T) T is positive semidefinite. In the following, we demonstrate and justify the convexity of the QPs of both layers by rewriting their single-sample objectives into the formulation of f and summing them without loss of convexity.
Theorem G.2. QP: Eq. 4 and QP: Eq. are convez optimization problems.
Proof. First of all, constraints of both QPs are trivially linear and conveex Thus, we only need to justily the convexity of the two empirical objectives, GNPE and G (see Eqs. (4) and (7). Consider the single-sample version of CNPE, namely N [A, Φ; w. h) z 1 + Ax hll which, in the formulation of f, can be rewritten with
A
A
T
b h
A
which guarantoes the convexity of gi NPE w.r.t. A and Φ by Lemma G.1
For 92 (C,
2 lle + x - Cyll², we have
C
2
y
a
b
Cm.:
which guarantees the convexity of g2 NPE w.r.t. and & by Lemma G.1
Now we consider the summation.
Taking layer 1 example, by definition have
ANPE (A, CA
Σ kE(n)
NPE
(A, of ao ()).
9i
For each i E [n], equivalently, we take + variable instead of (60) in si APE, but with only Φ(0) E + determining the value of N.E. In this sense, NNP is convex w.r.t. A and & for each i E [n]. Thus, the sum ÖNPE is convex w.r.t. A and T. Similarly, ČNPE is convex w.r.t. C and E.
H Strong Consistency
In this appendix, we justify the strong consistency of our estimators for the residual unit layer 1/2 learning and the whole network.
According to Theorem E.1 and Theorem 5.1 the solutions to our objective functionals are continuous sets. In addition, we also present intermediate results in terms of continuous sets, e.g. possible left-inverse matrices for B" in the results for layer 2. Thus, to analyze the consistency of our lcarning algorithm, we define distances between sels, so that the convergence of sets can be well defined. Further point convergence results, i.e. layer 1/2 estimator strong consistency, are based on the
convergence we define.
Definition H.1 (deviation). Let A C M and IB C M be two non-empty sets from metric space (M, d). The deviation of set A from the set B, denoted by D(A, BB), is
D(A sup d(a, B)) sup inf d(a, b), aeA
ae BEB
where sup and inf represent supremum and infimum, respectively.
Definition H.2 (Hausdorff distance). Let A M and B S MI be two non-empty sets from metric space dM.,)). The Hausdorff distance between A. and BB denoted by (A, is
DH(A, = max (AA, IB), D(B,)) A)).
Remark. In the following, we use the Frobenius norm to define the distance between matrices, i.c. d(X,Y) Y) X Yl
26

---

Published in Transactions on Machine Learning Research (11/2022)
H.1
Layer 2
In this subsection, prove the strong consistency of the layer 2 estimator.
H.1.1 Objective Minimizer Space Estimator
For simplicity of notation, we use Sn to denote layer QP /LP solution space by random samples random set
S2 = {C E R Rdxm_ Cy ( 0, Vi [n]]
(16)
and S" to denote the value space of C' in Lemma 4.2 which minimizes layer 2 objective functional
S" = {C E Rdxm Cy 2 0, V E E2 and its corresponding output y).
For further use, we name Pn as the set of n sampled inputs which define Sn, i.e. P.. = [x(m) where each x(( is the same random variable in Eq. 16). By the definitions above, describe the strong consistency of our QP/LP Lemma H.l
Lemma H.1 (QP/LP strong consistency, layer 2). (S,,SS 0 as
First we prove that DH S*) 2 0 0aasss + co. Recall Theorem E.1 Cy x 2 0 only if = diag(k). We inherit the notation as defining D CB Theorem F. is based on Lemma F.1 and we prove them by raising points that show contradiction, i.c. violate the incquality that holds in pointwise fashion:
Proof.
a) In the proof of Lemma
F.1
we use d points: -e("), for i [d], to make
Σ k- Di,k
AA.
+ 26 < Ii, so that Di.j (i j) cannot be positive; and another d points:
(A") to show Ed= Di, A x < 0, that Di.j (i cannot be negative. For each e we use hore, since the violations follow strict incqualitics, we know there exists a neighborhood of e0)) N; N(-e()), such that V2 Ni, Dd Di,e (AL..
zk zz-
We can similarly
find such neighborhood of each (At)-1e(0) that the strict inequality holds within the neighborhood respectively. We index them as No+1 to Nea-
b) In the proof of Theorem E.
further construct d points: for each [d] we take point such Ary S O, where * i, j. This counterxxappee shows [Cy py--aj x), and eliminates the possibility of 0 < D1, < 1 when A is not scale transformation. We can similarly find neighborhood of each point and index them as N2d+1 to Nzd- Note that we omit some cases in the proof of Theorem E.1 because the first 2d points are sufficient to use in those cases to show contradiction.
that 0A A7
A7,
In the sampling procedure, if sample least point in each neighborhood N., Theorem assures the solution get C, would lie in the true optimal set St. The probability that the sampling procedure "omits" any of the neighborhoods is
P P
0 N1 or P... n N₂ or or P., n Nad = 0) s 2
N2
p
N. = 9)
i=1
(17)
S 3d
min P(N,)) ic iE(3d]
Since the measure on each neighborhood P(N.) JoEN p(x) 0,
P P N1 0 or P N2 0 or ... or P. Nad =0) 0, as n + 00.
Heree take samples random variahles empirical analysis.
27

---

Published in Transactions on Machine Learning Research (11/2022)
Here obtain Du (H S*) E 0 as + Now we take the infinite sum over the both sides of Eq.
17
Σ P
N = 0 or Pn n N2 = 0 or or Pn n Nsd = 6)
oo)
3d xE|oc]
min P(N:) k [e]d
3d
[3d P(N:) / < +00.
By the Borel-Cantelli lemma
Borel
1909
Du(SS, S*)
1... as + 00.
H.1.2 Scale Factor Estimator
To avoid ambiguity, we use Rer to denote the number of samples used in Algorithm 4 The samples pains are {(x(9) y 1=1. Without loss of generality, the following discussion focuses on some fixed index j E [d]. In
Algorithm 4 plug in estimator C, and use LR to estimate ky given that x,)
[, - kx Eielnal x) [C
knne(Cr) = arg min
Σ
(18)
2ns sE(ond
Eie(nal
We first give the strong consistency of layer 2 scale factor estimator for as nhat 7 oc, as described Lemma H.2 Lemma H.2 (scale factor estimator strong consistency, layer 2). Suppose A is a scale transformation w.r.t.
the j-th component, and (Cn) is the sample estimator of kj via LR: Eg. (18) given that x)) 0.
Define sels
Ungnn == (kn,(C) C Sn), and U = 1 A3j
Then lim lim DH(Ungmi U*) O.
n-000
Proof. Following our notation, Theorem E.1 and Theorem E.2 ensure that if A is a scale transformation
w.r.t. the j-th component, for any C belonging to the true optimal set S* (C) E T 1 And the
"iff" statement strengthens that U = (kn,, C' E S*} for any Not E Z+ Note that since S* c Sn, we have
U C Una.. We only need to prove D(Unan U*) a.a. 0 as n + cc.
A C, Sn and
Kng Sinr(Cip (Cn) kn (C)
Σ (() (ebi)T (Cn-C) B² (A>x(1)) + xx(1)
(z(()))
Eie(nal
xE(mar
Σ x (E(r)a)
(000]( (C,--) -c) B' (1 (| + |
Eie(nai)
[x3
x
C - -cl | 1r (1AA") A + +1) |
(x(()))
Σ Die(mar
Eie(ma))
[1255)
|| LB 1 (IAA ||x 2
C, - c c
Exenaal (x)9)²
28

---

Published in Transactions on Machine Learning Research (11/2022)
Then
sup inf kna (Cn) knt (C) C c Ces*
Σ Eie(nai
x
B BrIl (IIAA11 1F + 1)
2 (x(())
sup C, E8, Ces
inf
Cn - C
Eie(nal
which implies
Eielnad
x
( BB
(1| 1) ||x(00
D(Ungn U) <
D S*).
(19)
(8)) (x)
2
Eie(nad
Take the not + oo limit over both sides Eq.
19
With the strong law of large numbers we have
E
(3)
B 1p (1 + 1) 1|x
lim nyg
D
U)
D(Sn, S*), w.p. 1.
(1)
E
Since D(Sn, S*) aeg 0 n 0o, we have M(Una. U*) a- n oo then nat + 00.
H.1.3 Layer Weights Estimator
Algorithm we solve via LR. Let z diag - (k) C,y(() E R4, where k is obtained through
Algorithm with imput C,, Assume we are using sample size of nw do the LR. The optimization problem
is
min [E(Dw]
y(0 B2
(20)
Now we present the strong consistency of layer estimator, described in Theorem H.3
Theorem H.3 (strong consistency, layer 2). Suppose Bug is the solution to Eq. 20 n. Bof. + oc.
Then B.d
0.s.
B
Proof. Let B denote vec B (flattening B into vector), then ( (2 & Im. Here the operation denotes the Kronecker product. Then we can define equivalent optimization problem
(20))
T 8 Im
min 2nw
B
se sc(mm.)
Take the derivatives 3, we obtain
[2200 8 Im
(5:00
(210)
-2 Σ
&
Im 3 =
Ke [nw]
Here assume that the Kolmogorov's strong assumption on in similar analysis.
Singer 1994
is commonly done
29

---

Published in Transactions on Machine Learning Research (11/2022)
Then the optimal solution Pn.. of this optimization can be written in closed form:
Bnn
(1)
Im
(2(1)
mm
(2(1) mm
se/mwll
[E(mm)
(+))
2 mm
(2(1) T
2 mm
(((0)
2
Im
sr(i)
[E(
(11) (2(1) T
2 Im
Σ
2
2 Im
y(11)
iefnw]
sE/mml
(0)
(2(3))
T
& Im
y(t)
m
[E|m
[E(rw]
We inherit the notation from the last two subsections. By Lemma H.1 di d(C,,, S*) A.S. 0 as n Co. Thus Ve > 0. 3 N such that Vn 2 N, d(C.,. S e w-p. 1, i.c. 3C,, E s.t. d(C.. Ca) S E w-p. 1. Then by Lemma H.2 A K > 0, for e that is small enough, 3 Nat such that Vnntt 2 Not, we have Knas (C,)) - kync (Cn) S
KE w.p w.p.1. For simplicity, we omit the under-script not of knd in the following discussion. In fact,
1//0 z3 (9)
1
(e()) Cryy(0) 1 k(Cr) (e()) Cry(
k(Cm,)
((C.(((() Cn -((x)) (e(t) Cnl ycu)
k ((C))((C.)
k(C,)) (c(0) T C,yY - k(Cr) (e!t) Chylil/
k(C,))(CC.)
(xCC.) ((CW)((CW)
T - -n(C)) (e())) T (1/0001 C₂2 - Calle= - |k((C,) k(C,)) IC,BBlIp (1A 11p + +1) xx01]
C,y,(())
(1+A3))
Ke (1 AJ.))
(1+ A11)) A) 2
Ke (1 + + (1100)
+ dk (114-1/ + (114411++1) 11)//x001
(21)
Then
(1) (2(1) -2(0) (2(01) T
F
2 (0))) 200 (2(0)
+ z (5) (1)) ((() (2(0)
(2())
(3 71I
(0) )2
(()
(2(1)
+
200
(4)
(2(10 (0)
2(0)
(2(0) T - -(2(5)
+ 2
2 (0)
2
+ 2
2
2 ( z
JE/d
30

---

Published in Transactions on Machine Learning Research (11/2022)
It follows that | (z(1)²
-z(1) (z(0)
is also bounded by OEe). With similar techniques we can prove
Σ (() (1())
Σ (
(2(1)
0((e)
se/mwl
[
and
(2())) & Im z @ Im ((E)
Denote Eve(mn)) z(0) (x(1))
as and Eie(nm) z as Q. Substitute z00 with 2 in the above expression
we have P and Q Hence,
18... 3r
P 2 Im
T. (( & Im Im]x(()) s(())) - - Im] 1n ( 8 [m] (1)mm))
<
p & I m
1m sn(o)) - [ Im
(10 2 1m (1))
p 00 m
( mm))(())
[ -IP mm -1 (QQ Im]] yr(1)
p & Im
[[(@ 2) @
Im yr(1
+
p Im
[P
I
F
Q @ Im y
In the first part, by triangle inequality,
& Im
p Im - P I
+ P Im 1|-
1m1
So only need prove
P m
p
(s) to claim - O(s).. Denote
P = AP. From Eq.
21
we know every entry of APP Im can be bounded by O(e). By simple
calculation we have
(P I AP+ -
- - O
Then we have
p-1 p-1 - P- - -0))
H.2 Layer
In this subsection, we justify the strong consistency of layer 1 objective functional minimizer estimator in detail, i.c. the layer 1 QP /LP solution space. We will omit the detailed proof of Algorithm 2 line 4 to 7 strong consistency since it is similar to the proof of Lemma H.2 Additionally, we also omit the strong consistency of the x + ()* function estimator because can be directly obtained by Lemmas H.1 and H.2 and the continuous mapping theorem.
We use a new optimization problem equivalent the optimization of Gi. Before that, we first define the equivalence between two optimization problems follows.
Definition H.3. Let opt1 and opt2 be two optimization problems, with fi, fa as the respective objective functions. Then opt1 and opt2 are said to be equivalent if given feasible solution to opt1, namely æı, feasible solution to opt2 is uniquely corresponded, namely ø2, such that fi( fa(æz), and vice versa.
The new optimization problem and its equivalence the optimization of G1 is described in Lemma
H.4
31

---

Published in Transactions on Machine Learning Research (11/2022)
Lemma H.4. The optimization of G1 (Eq.
(6) is equivalent to
min f(A) = Ex
||
[Ax
h))*1
(22)
2
Proof. To see this, suppose A is one optimal solution to Eq. so that G1 (AI,TI) f(Ai) and the optimality implies
22
then we can construct r1 = (A1 h)+
min G. (A,r) & min f(4). A,r
A
On the other hand, suppose (A2, r2) is an optimum of G Let ra(æ) = (h - A2x)+ then Vo Rd and be the corresponding hidden output, if Agæl; 2 0, then (r3(2) + A2æ hl, = 0, otherwise (r)( + A2æ h13 = [A2æ h22 1 [h2 (x) A2æ h13 since h2 is nonnegative. So that we know that
min (A. Gi (A2, r2) = (A), f(A2) A.r
From the optimality, we further have
min G (A, 2 min (AA
A,
From the simple calculation above, we can see that one optimal solution to Eq. 22 has a one-to-one correspondence to an optimal solution to G1.
Similarly, the empirical version of the two problems are equivalent, which indicates their consistency in the empirical estimation being equivalent. In the following, we justify the strong consistency of empirical Eq. (22 instead of G₁
min fa (A) A
1
Σ AE(m]
-Anl)
2n
Denote T" (diag(k) A" 1 k2 11jj [d] as the true optimal solution set, and Tn as the optimal solution set corresponding the n-sammle problem. In the following, we justify four conditions in row that hold for f to derive the strong consistency of its optimal solution estimator.
Lemma H.5. Let The be the layer 1 QP/LP solution space by n' somples. Then there exists a compact sel C determined by A", nomely C(A'), s.t. Tw C(A") w.p. 1 as +
Proof. VI [d], let a" be the l-th row of A", and à be the 1-th row of Aw. We'd like first to prove that the set
Th = {a az is the 1-th row of A, where A E fw
is compact w.p.1.
Suppose n' d, and among the n' samples, we classify them into two folds. To avoid ambiguity, let (0) be
the points such that (a*) (t) > 0, E [q]: and x(5) be the points such that (a*) v(()) < 0, [n q). From
the analysis of Theorem 5.1 we have (a*) (1) 2 à (t)), Vi [q] and à +00 20, Vj E [n g). It follows
that we can rewrite f, as a polyhedron
T/ {a E Rd: a TT S saa) u a T < 20}
We are going to show the polyhedron T is bounded by contradiction. If it is not bounded, then 3d e Rd. d * 0 and à fhy such that AA > 0, à Xd E fty Then
(a (a+ Ad) (1) = ā T Xd ( - (a") T ( = xd s (a") (9) à (
similarly,
(a + Ad) T (+) ā. (1)) Xd (() 50
32

---

Published in Transactions on Machine Learning Research (11/2022)
From the definition, À can be arbitrarily big, then d'a (1( s 0, Vi [g], and d' v()) 1 Vj nn g).
Since we know span| (u ( = R2 w.p. 1, then there 3 some i' such that d u(²)) < O, w.p. 1. (Otherwise if d' (t = 0 for all i E [4], then either span(u(") o R or d = 0.) Under our assumption that, T, is not bounded, we know the following system (w.r.t x) has a feasible solution w.p.
U -v
x 0, x (( <0
where every row of U and V is (uli)² and (nlii) respectively. By Farkas' Lemma Farkas system
1902), the
-UT.-V (1) 20
(II)
is not feasible (w.p. 1). We claim that u(t) lies in the conic hull of -old)'s w.p. 1. So that the second system actually has feasible solution and thus it raises the contradiction. Denote the conic hull as
H LERR:
Σ X (-o(0), 20 for 2j jE(a-q
Now suppose (1") $ Hi,, by the supporting hyperplane theorem Luenberger 1997 that bt (²)))) < T for vt E H. Then by definition,
36 E Rd, of 0, such
- E (t. b S bb ('))),) for Vj e (m (m-nop
Denote the hyperplane J
b
u(( ), then
< P (-o0) E J. for Vj E In q1) = = p E n-g EJ)²²
P
f H
Since we have this case a geometric sequence, we know its infinite sum bounded. By Borel-Cantell lemma [Borel 1909), we conclude that (²")) w.p. 1. Then system II is feasible w.p. So that T, is compact w.p.
Now we prove that there exists compact set C(A"), s.t. Th C C(A") w.p. 1 as xo. Similarly, we focus on the analysis of one row. As discussed above, TV is compact w.p. 1. Let W7, be the set of all (9 sampled in estimating Tw', and W2 be the set of all o sampled. Now for another set Tw", similarly define sample point sets WT and Wy. We claim that (i) Wil nf: ((() lies the conic hull of Wi Actually, this part of the proof very similar to the way we prove ((0) IH w.p. 1, so we will omit it here.
Va In", let (1) and (2) be two different points in WT... Then a T (Aix(()) +12aa())))))))) (2) < (a*) (A)z + (2)) for AYı 2 0 and A2 0. This simple calculation reveals (0) < (a*) T (0) for () Wa, (from the claim
we made). This implies that T, C C(A') w.p. as n + 0o, too.
Lemma H.6. The minimizer space of fAA, i.e. T = (k: A |0 1 by I 1,j E [d]}, is contained in C(A').
Lemma H.7. f(A) is finite valued and continuous on C(A").
Lemmas
H.6 and H.7 are easily obtained by the formulation of f (see Eq. 222 and Lemma H.5
Lemma H.8 (uniform a.s. convergence). fA( a.d. f(A) + oo, uniformly in A C(A").
Proof. Name single-sample objective g(x: A) = 1 (Ax h) h)+1 The uniform a.s. convergence is guaranteed
2
by the uniform law of large numbers (Jennrich, 1969):
a) By Lemma H.5 C(A*) ) is a compact set.
b) g is continuous w.r.t. A by its formulation and measurable over at each A C(A)).
33

---

Published in Transactions on Machine Learning Research (11/2022)
c) In fact,
g( A) (Ax h)
- 111 Az/1/ + || a0
(|| -1|A11pp) ||=:1
Since A E C(A*) is in compact set,
g(a, A)
sup AEC(A-)
||A||r + ||"l|
|0:1
Thus the dominating function exists
By Lemmas H.5 to H.8 all of the conditions are satisfied in (Shapiro 2014 Thm. 5.3). Thus, we have the strong consistency of layer objective optima estimator described in Lemma H.9 Lemma H.9 (QP/LP strong consistency, layer 1). (f TM) 0."., as n + oo.
Similar to Lemma H.2 we have the strong consisteney of the layer scale factor estimator as described Lemma 1.10
Lemma H.10 (scale factor estimator strong consistency, layer 1). Let kny of by via LR: Algorithm
(nn((n)) (Cn) be the n' nag-sample estimator
line 5. given that hy 0. Define sets
V m = fkng (A) E Tn and V = [0,1]]
Then lim lim DH WV n' V*) 0.c. O. 700 n' 100
Remark. case ky = 0, suppose the algorithm finds a solution over a continuous distribution with [0, as support and the probability that it finds solution with scale factor 0 is 0.
With Theorem 5.2 and the contimuous mapping theorem, the strong consistency of layer estimation is guaranteed.
Theorem H.11 (strong consistency, layer 1). Suppose An is scaled by kni, Then Aw a.a, A as
n/, n/,n + co.
By Theorems and H.11 Theorem 6.3 is guaranteed by the continuous mapping theorem.
Sample Complexity Results
In this appendix, begin with intuition that justifies how our QP/LP approaches eliminate the exponential sample efficiency compared to the vanilla LR approach. In layer learning, C's optimization is to find feasible point in the space determined by n incqualities cach of which corresponds to a sample. Taking the j-th row of the inequality, i.e. C,.y y 2 xz. Every time we get a new sample (60), ( in,
The incquality ()) 2 2 climinates the solution space of Cj. by one of the spaces divided by
plane ( = = This property guarantees fast convergence speed early phase since Cja's feasibility starts from Rdd
18 Here, assume [][[[[|]] as commonly done empirical analysis.
34

---

Published in Transactions on Machine Learning Research (11/2022)
In fact, when ReLU does not activate A'x(9 at the j-th row, i.. A3.x I O, the theoretical solution of Cj:: that C². = (0,.... 0, 1,1,0..... 0) (a 1 at index j) directly lies on the separating plane Cg.3y = vg: (0)
( (A'z(1)) Cj.
+ z()0
(0)
This property remarkably speeds up further constraints on the solution space of C₁ the correct estimate and is with high probability, since it directly depends the sign of A A'x())
With the vanilla LR approach mentioned in Section 3 all the dimensions need to have the correct sign at the same time. This is the reason for the exponential complexity of this approach. Our main algorithm only requires one dimension to get the correct sign for a single sample, which avoids the exponential sample size expectation. The convergence speed is determined by the actual probability of each dimension not getting activated by ReLU, and such probability is determined by specified input distribution.
Roadmap Our sample complexity results follow several intermediate results. We first demonstrate that the constraints that define our optimization objective give a bounded polytope (Theorem L.2) This happens with high probability, given a sel of samples. Once we have shown that, we then show that the optimization problem constraints we use define polytope with small diameter with a high probability given a sufficient number of samples, where the true network paramcters exist. The boundnesses of the constraint polytope is required for this result.
Details We follow the above intuitive explanation with more rigorous analysis that describes the sample complexity of recovering Cj.; for j E [d].
Let us assume we have n samples of (0) [n]. We denote by F E Raxd such that Fg = V3 ()) n > d. We denote by L, = E[x]]
We assume
Condition I.1 (Haar condition on samples). F satisfies the Haar condition, i.c. that every submatrix of size is invertible, almost surely.
We will assume that Condition holds for the rest of the discussion. For a discussion of the Haar condition, see Schmidt & Mattheiss (1977).
Fix j E [d]. The first step in our process is to show that with high likelihood, the inequalities Cy.y 2 zj for i E [n]. or equivalently (),(-y()) < (-zz²), ) or equivalently FCJ; S =zz define a bounded polytope
with high probability.
Schnidt & Mattheiss 19777 describe a necessary and sufficient condition for this set of inequalities, which describe an intersection of half-spaces, to be bounded. More specifically, under Condition I.] such an intersoction is unbounded if and only if the subspace spanned by the columns of F intersccted with the negative quadrant of R" is non-emply.
This means that this halfspace intersection is unbounded if and only if there exists E Rd a a 0, such that F S 0 for i E [m].
d' a4y:) where sgn(z) for 2 E IR is 0 if 2 S 0 and otherwise. For given Rd, * 0, let ha E Define:
P(a) = ([)a(y)), 1 n
(a(a)
ha ()).
n
A well-known result of VC-theory (Vannik
1999,, specialized to linear separators, states that:
35

---

Published in Transactions on Machine Learning Research (11/2022)
Theorem 1.1 (Vapnik 1999). For any t 22n it holds that:
(d+1)
2en
sup (a(a)) -(a)) 2t) $4 d d+1
exp( (ont-nt//)
LaE
We contimue with the assuming the following separability condition:
Condition 1.2 (separability of y). There exists 0 such that for any Rd, + 0, P(a)
Theorem I.2 (unboundedness of halfspace intersection). Under Condition L. and Condition I.1 the halfspace
intersection defined by F for identifying Cj;; is bounded with probability
2en d++1
(d+1)
(F defines unbounded intersection) 2
exp( /8)
if max(2/a²,d))
Proof. For any Rd + 0, it holds that if (m) 0 then for all E [n], sgn(2) a,y,") 0. Each such case means that for this specific a, we found span of the columns of F such that its ith coordinate is 0, and as such, case in which F is unbounded.
This means that for all a E R it holds that (a((a) > O, then the n samples define a bounded halfspace intersection.
In addition, if Pa(a) 0, then
(a(a)) - P(a) -P(a),
(23)
therefore,
(Px(a) - P(a)) = P(a).
Since a < P(a), it holds that if Eq. 23 holds then:
- > a.
Thercfore,
P (F defines unbounded intersection)
S p Ba + 0, (a) = =0
3 sup Pa(a) P(a)) >
2en (d+1)
exp(-na? 2/8)
d d+1)
where the last. inequality is the result of Theorem
L1
Theorem 1.2 gives well-behaving sample complexity for the m samples define halfspace intersoction that is bounded, when solving for Cy.- Note that the theorem does not depend on j, because the use of x, is not necessary for the boundedness result of Schmidt. & Mattheiss 1977).
36

---

Published in Transactions on Machine Learning Research (11/2022)
We now further show that when the halfspace intersection is bounded, then the diameter of the bounded space is smaller (where diameter is defined the maximal distance between any two points).
The diameter is bounded by the maximal distance between all pairs of vertices of the intersection (the intersection is bounded polytope)- Let E {e Fu I -x be the set of these vertices. The size [E] is bounded from above by O(n4/2) (by McMullen's Upper Bound theorem; Toth et al. 2017).
Condition I.3 (equality saturation for vertices). For every v E E, there are d equalities that are satisfied, in (1) the form of Fi.00 - such that C [n] and | d.
Condition I.4 (bounded input distribution). For every j [d], |را|
for some b 0.
Lemma 1.3 (Hoeffding's inequality). Let Zz Zn be n random variables such that Zi E (a by] abmost surely. Then, for all 0:
212
P
7
B
E
21
exp
Ei=1 (b; a;)²
Lemma I.4. Assume Condition
L.1
Condition
T.3 and Condition
1.4 ore salisfied.
Vdba
In addition, let 0² = =Bao] where a is the smallest singular value of FL; for I = fl,..., df. Let e >
0+v
where 0 v- log(5/4) + < 1 for any > 8> 0.
Define:
1 4D2 exp
(2((0*)002 - dL,)² )
de,, L.. V
d212
For any set of samples (x(1) (()), i E [n] such that the halfspace intersection is bounded, it holds that with probability at least 1 - 5 > the diameter of the halfspace intersection is smaller than if the following inequalily is sulisfied:
n 2 L(e, o. 0" b, 2d.
Proof. The diameter of the intersection not larger than the maximal distance between two pairs of vertices || u|], u, v E By Condition I.3 let I, be the two subsets of integers such that |/| = |J| = d and
(T) Fr,.u -x FJ:U= -a (.) (J)
By the Haar assumption on F, the inverse of F exists, and it holds that:
|u u|l = || 2j
F 2 (1) FJ.
S 11FT. ||= (1) + || 11" - 1
Consider || II", the operator norm of FT. which equals 1/a, where or is the smallest singular value of Fi.. Similarly, define oy. Therefore:
||m w|| < ||m)) 11///1 +
The event that the diameter larger than can be bounded by (A(I. the event 0i c, 0. 2 for some c):
37

---

Published in Transactions on Machine Learning Research (11/2022)
2rr sp(r 2 A(T.))) + SeAer
In addition,
(r 2 e, A,A P
max (1,0EE
1/u w/1 2 e, A(I,J)
||a8) (1) 11/cc
< p
max u,v
2 Σ
(1 (1) 11/c
||0 11/0
We know that |E| < D(n for some constant D (oth al. 2017 therefore prr2 A(I, can be further bounded by
Den pp (11a/"11/c+ 11a,
Since the distribution of 2 and / (and the singular values) is identical, p(r e,)(I can be further bounded by
nD p (1aff11/cee)
(24)
for any I, for example / = (I.....d).
We can use any value for c F[aa] v to be smaller than dr, and the inequality still holds. Therefore, Eq. 24 can be further bounded by (assuming < 1):
2n2ndd (p (1 11//o///
This be further bounded by:
2D'n. (p (12 (1 22,,,
(25)
where we also square the norm of ( (and its bounding term).
The term p ( s B[ar] va & B|a.] v) for small v is going to be close to 0, more specifically, it measures the probability of the complement of the event JJ. This probability is at most twice the probability that exp(-o1) 2 exp(-v-E[or
which by Markov's incquality is smaller than E [exp(-oy)] exp(-v- E(ay]) s exp(B [(v - 1) or]) = exp((u I)o*) (by Jensen's inequality). Therefore, the probability of the complement. of A(I,J) is bounded by:
p (ar S vo haj S S0¹) < 2exp((u-1).ot) o0))
(26)
Consider that (112 is the sum of d iid samples oj. Under Condition L.4 by Hoeffding's inequality, we can get an upper bound on the probability term in Eq. 25 to hold:
assume [x)]] < b. Therefore,
22((0))2 d. F(xx))))
(112//11 d. E|ze| (0-)302E2 d. E(xji)] s exp
(27)
db2
38

---

Published in Transactions on Machine Learning Research (11/2022)
remembering it is stated in the theorem that o've 2 vdba and the fact that vdba 2 Va Bla3] by Condition [.4 Hence, [[ar]]uRE? - d E[ag)) > 0, and the use of Hoeffding's inequality is allowed.
Vd.Ela3
Let > O, then taking Eq. (27 with the union bound constant from and setting it to 6/2:
-2((0")\ve - dl,)²) ) S 8//2
2D exp
db3
We now get upper bound
2((0")22202 - -[e, o² Lj.
4D2 exp
d2b2
We want, in addition, the complement of J( to have probability at most 8/2, therefore, we choose log()/4) + according to Eq. (26).
Noting that the diameter of the sphere gets smaller n increases (bocause there are more halfspaces that possibly intersect into smaller space).
Note that Lemma I.4 requires d 2 exp(-o") in its statement (this can be inferred from the relationship between & and 8). To have an arrytrary confidence 1 1 in the diameter being smaller than e, we can run the algorithm & times with an n as needed. The probability of all of them having diameter larger than e is smaller than 8*
Lemma 1.4 describes under which condition we get small error for Cj.: if fix j. Using union bound, we bound the probability that for any j E [d], the corresponding feasible halfspace intersection space is small. This will require adding a factor of d to 8, and a factor of d to n. We overcome this by making sure that the probability for each j having a diameter larger than is smaller than 6/d, and we use dn samples for a choice n satisfied by Lemma I.4 Using a union bound, we can show that the probability that for any j the
diameter is larger than e is smaller than
In addition, note that Lemma works only when we assume the halfspace intersection is bounded. This is the diameter bound through the set of vertices. To take this into account, also use Theorem 1.2 This leads to the following result regarding the sample complexity of our algorithm.
the case where we
Theorem 1.5 (sample complexity of learning ReLU two-layered networks (layer 2)). Assume Condition I.1
Condition L.2 Condition T.3 and Condition 1.4 salisfied.
Vaba
In addition, let a² E[o] where a is the smallest singular value of F1,: for I {l....,df d}. Let where OSv= (5/8))
o+v
< for any 0.
Define:
d 8
(((o0)22
dL,)2 )2>
L"(,,d,,",b,, min
8dD2 exp
d212
and define:
8
(d 1) log 6 log log
L (a,
a²/8 1/e
39

---

Published in Transactions on Machine Learning Research (11/2022)
For any set of samples (x(), y00,)))).))) i E [nd], it holds that with probability at least 1 - 8 > the diameter of the halfspace, intersection is smaller than if the following inequalities hold:
n2 d- ,', L' ('E,d,,"",b,) 2 max ())
Proof. Let U be the event that the diameter larger than e for any j E [d]. Let V be the event that F represents bounded space, The event U is the one we need to show has small probability.
By Theorem I.2 know that if 2 Lu 6,, then F is unbounded with probability smaller than 8/2. Therefore, p (V) 8/2.
From Lemma L.4 and the analysis before this theorem statement, we know that for n as required by this theorem statement, any time F represents an bounded half-space intersection, the probability of the diameter this intersection (for any j) being larger than smaller than 8/2. Therefore, p (U V) S 8/2.
Hence,
= P10)=p(111000))>0001xx0 <p (1- s 8/2 8/2
Table 5: Prediction errors (RMSE) as p (the fraction of nonnegative entrics in A) increases (n 512,
16). Each set of rows describes an experiment with a different number scale vector rows in A (s).
Alg.
p -=
0.1
0.2
0.3
0.6
0.7
0.8
0.9
1.0
SGD
0.4353
0.4135
0.3844
0.3511
0.3364
0.3255
0.3310
0.3480
0.3792
0.4158
0.4117
LP
0.0923
0.0991
5.2210
18.3364
0c
00
00
00
00
00
55.4519
QP
0.0492
0.0583
0.5445
10.0328
00
00
00
00
0.4129
SGD
0.4252
0.4058
0.3777
0.3510
0.3315
0.3216
0.3293
0.3447
0.3704
0.4060
0.4234
2
QP 0.0729
0.0819
0.5072
7,8984
9.8862
00
00
00
0
5.8306
0.4297
SGD
0.4152
0.3962
0.3711
0.3423
0.3286
0.3213
0.3228
0.3382
0.3683
0.3944
0.4118
QP
0.0926
0.1070
0.4480
5.6844
00
00
12.0391
CC
SGD
0.39411
0.3823
0.3637
0.3410
0.3289
0.3248
0.3256
0.3428
0.3578
0.3743
0.3874
QP
0.1221
0.1527
0.2835
1.3792
8.4902
7.2903
7.4253
80
5.9887
8.2727
0.5928
SGD
0.3820
0.3829
0.3827
0.3812
0.3825
0.3825
0.3827
0.3815
0.3831
0.3818
0.3827
16
QP
0.1810
0,1841
0.1853
0.1823
0.1833
0.1845
0.1823
0.1823
0.1825
0.1840
0.1803
J
Nonnegativity of A and the Scale Transformation Condition
Throughout the paper, we assume that the first layer, the matrix A, has nonnegative entries. As we mention before in Section and Section 7.2 such restrictions on neural network weights have successfully been studied before and shown to be effective practice.
While the thcory of our algorithm does require A be nonnegative, we use this condition in a specific part of the proof of Theorem E.1 in Appendix F. This theorem is only necessary to prove that the objective functional for layer 2 achieves the correct estimate of the network. It is not necessary for proofs for layer or for the proofs of the transition from the layer objectives into the QP or LP formulation. In that sense, can aim to alleviate this nonnegativity condition quite in a modular way when addressing this issue. For example, we could parametrize the number negative entries in A and make more nuanced arguments (albeit more complex) in the proofs in Appendix F.1
This condition does not prevent us from running the algorithm as-is with negative entries in A. To test our algorithm sensitivity to this assumption, we repeated the experiment in Section 7.1 with d = 16 and
40

---

Published in Transactions on Machine Learning Research (11/2022)
512, and checked what error the algorithm gives function of p {k/10 {0.... 101)
fraction of random entries that are set to be negative in A. To test the effect of Condition 2. (which is alleviated in Appendix Ed. we also vary the number of rows that are a scaling vector (through parameter E {0, 2,4, 8, 16), which denotes the number of such rows in A). We repeated each experiment five times with different, parameters (and each experiment includes multiple execulions with different. samples). We experimented both with the LP and the QP objectives for and the QP objective for > and compared them against the SGD algorithm.
The results are given in Table 5 When the assumption about nonnegative entries holds, both the QP algorithm and the LP algorithm (for s s= 0) give an error much lower than SGD. This holds even for a small > O. However, as increases, the results of LP and QP degrade quickly and then recover (for the QP) when p 1.0. This latter result could be due to the symmetry of our input distribution. we also note that general, the QP algorithm, as expected, is more robust. to p >> than the I.P algorithm. As we increase the number of rows number of negative entries in the matrix A (with respect does seem to make the learning problem more difficult for the QP algorithm.
that are scale vectors, we see that our algorithm becomes much more robust to the entries). However, having scale vectors in A
41


Reviews:
[{"review_id": "IPd5nRGTpI", "reviewer": "Reviewer_XZBi", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- Strengths: This is an important problem and the algorithm is simple. The authors provide experiments for their results.\n- Weaknesses: The main weakness is that this is a very restrictive setting. Are these conditions required? The answer is: It depends. If you want to explicitly learn the parameters then you required to have a unique solution, in the literature usually we required assumptions in the condition number of $A$. For learning, it is well known that a uniqueness of the solution is not required. Now the assumption that the matrix is non-negative is a bit of strange and I do not believe it is an interesting setting.\nIn my opinion this work has several problems that the authors need to address.\n1. The fact that the entries of A are non-negative is hidden and need to be explicitly stated in the Condition 2.1.\n2. Many statements are not well-supported. For example: Appendix A. It does not make sense to have a section for a different model without any proofs.\n3. Vanilla Linear Regression. I do not see the reason to compare with an algorithm that does not really work. No ones expects to draw samples from the space X>0. Even, for gaussian distribution, this area has tiny probability. \n4. Appendix I is a mess. I suggest the authors to put somewhere a theorem with the sample complexity and put more explanations.\n\nOverall, this work may be interested for some audience but the authors should fix some of the issues raised above.", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the problem of learning a two-hidden layer relu network.  The authors propose an algorithm based on QP/LP and the basic idea is that they first learn the second layer and then using the new information they learn the first layer. They show that the algorithm is consistent and provide a comparison with linear regression. They work in the realizable case and they assume non-negative entries in matrix A and they also require the matrix not to be a scale transformation, ( Definition 2.1), which is required so there is a unique solution.\n\n", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "See above. 1,2,3,4. I suggest putting some effort and improve the clarity of this work and the presentation. The paper will be improved if the authors explain their proofs and provide details on why each lemma is required.\n", "broader_impact_concerns": "no ethical concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "2yN31it9KN", "reviewer": "Reviewer_Rwh4", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The proposed algorithm is novel, and the paper proves that it can indeed recover ground truth network under certain assumptions. Further, the algorithm runs in polynomial time.\n2. Parts of the proof techniques can be of general interest. In particular, I liked the idea of learning the network layer by layer, by formulating the problem of learning the second layer as minimization problem with constraints, and then reducing the problem to that of learning a single (first) layer.\n3. The paper is well written, easy to understand. The concepts and proof ideas are explained really well.\n\nWeaknesses:\n1. The major weakness in my opinion, which the paper also acknowledges, is that the weight matrix of the first layer of the ground truth network needs to have all positive entries. The paper says that such networks are still quite expressive. However, I think in high dimensions, such matrices would have an exponentially small measure (for example if we consider the operator norm as the distance metric in this matrix space), although I could be wrong. This is certainly true if we consider the measure of vectors with all positive entries in high dimensions. \n2. The time complexity of the algorithm seems to be d^6 and n^3 where d is the input dimension and n is the dataset size. This is prohibitively large for modern ML tasks.\n3. The consistency results in Section 6 are asymptotic. It would be better to have non-asymptotic results (maybe by using some distributional assumptions on inputs).\n4. The networks considered do not have any biases. Although, this might not be a big problem to fix, maybe the authors can comment on how biases can be included in the networks presented in this paper?", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes an algorithm which learns a 2-layered residual network with ReLU activation. The algorithm works in two steps, first by learning the weights of the second layer and then those of the first layer. The paper proves that this algorithm recovers the ground truth network (the data is assumed to be generated from a 2 layer residual network), if the ground truth network has first layer which has non-negative weights. The algorithm's run time is polynomial, and seems to outperform SGD on synthetic and small real datasets.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "Critical:\n1. To verify the claim that first layer being all non-negative is indeed not restrictive, please re-run the experiments on synthetic dataset, but where the ground truth comes from a residual network with negative values allowed in first layer (use Gaussian instead of folded Gaussian). Then, please report the comparison of output error for your algorithm vs SGD. Note that even if the proposed algorithm performs much worse than SGD, the comparison should be included, so that the readers can have a better understanding of the algorithm's performance.\n\nNon-critical:\n\n2. In the experiments measuring output error, was SGD constrained to have non-negative first layer? \n3. It would be nice to have a discussion in the main paper why the requirement of A* being non-negative is needed, and if the authors have any ideas about how it can be bypassed by future work.\n4. Can the idea of learning the last layer and then the ones before it layer-wise be extended to deeper networks?\n\nMinor:\n5. This seems to be an incomplete sentence on Page 5:\n     \"If we parameterize h, and show that the nonlinearity w.r.t. its parameters would make Gˆ2 lose its quadratic form.\"", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Yg6UPKcOjq", "reviewer": "Reviewer_adXy", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper focuses on the important problem of learning a single-hidden-layer (thus non-convex) neural network having ReLU activation and a residual unit, by providing an efficient algorithm with theoretical guarantees (in the sense that one is able to recover the ground-truth parameters in a teacher-student setup).\nFrom a technical perspective, this paper contains some interesting ideas that are, I would say, inspired by previous efforts but well adapted to the problem under study.\nMy major concern is the presentation of this paper: as a theoretical paper, it contains many vague and unclear statements (specifically in Section 1.2) that need to be clarified. \nI believe that this paper needs to be carefully revised by adding clarifications (in words and also possibly in figures/tables, etc.) to help the interested readers (myself being one of them) better digest the results.\nSee my detailed comments below.", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In this paper, the authors present an algorithm (Algorithm 1+2) that learns a two-layer residual unit/network with ReLU activation in a teacher-student setup, under the assumption that the first-layer weights are nonnegative (without specific assumption on the data distribution), and shows that the student network is able to recover, with the proposed layer-by-layer approach, the teacher parameters in the infinite data limit (Theorem 6.3).\nEmpirical results are provided in Section 7 to further elaborate the proposed method on both synthetic data (in Section 7.1) and real-world data (in Section 7.2).", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "* Abstract: should one understand \"nonnegative\" as nonnegative definite for symmetric matrices or matrices having non-negative entries? This remains unclear, at least at this point of the paper.\n* Section 1.2 needs some reworking: I understand, in the case of some ML conferences, the use of informal theorems to allow the readers to have a first grasp of the main results and ideas of the paper. But I am not so sure that this is appropriate in a 12-page long journal paper and, even if this is the case, the current versions of Theorem 1.1 and 1.2 are not easy to understand.\n   * Theorem 1.1 needs some more explanations, for example on \"quadratic functionals defined in linear-constrained domains\" and how they correspond to the (teacher or student) NN model defined above, and on the precise meaning of \"can be adjusted to.\" A few clarifying sentences should be enough. Also, the paragraph after Theorem 1.1 is on the computation of the moments, but the motivation is not clear at all: the only available information at this point is \"The values of the objectives are moments over the input distribution,\" but it remains unclear if the estimation (from the available samples) of these moments are difficult or not.\n   * What does \"that learns a network $\\overset{a.s.}{\\to}$ the exact ground-truth\" mean? Should we take this as \"recover the ground-truth network parameters\"? in which metric sense? and the almost sure convergence is with respect to what? the input data distribution I imagine?\n   * More generally speaking, the statements in Theorem 1.1 and 1.2 are very unclear and vague. Even worse, it is not easy to find the corresponding \"formal\" version of them (since they are announced as \"informal\") in the remainder of the paper. I can understand that for conference papers, this allows readers to have a quick grasp of the main contribution of this work, but I am not sure if this is a good idea for a (more lengthy) journal paper here.\n* In the paragraph \"Roadmap\", please first define and then use LR.\n* \"further simplified as an LP that has the same capability as the QP to learn layer 2\": what does \"same capacity\" mean here?\n* after Theorem 4.1: \"to prove a more general theoremwhich\"\n* Above Section 4.3 \"and solving layer 2 QP are empirically equivalent\": please clarify the precise meaning of \"empirically equivalent.\"\n* I find the discussion in Sec 4.3 on the LP simplification somewhat unclear: what do the authors mean by \"LP and QP\" have equivalent solution space? Cannot one say anything about the solutions achieved by these two programs? Are they the same, or are they different? Can any formal statement be announced here?\n* Could the authors comment on the limitation of this work by focusing on the *non-negativity* of the first layer weight? Is this assumption intrinsic? Can it be relaxed with some additional effort? Or from a different perspective, does this assumption correspond to a practical scenario or application?\n", "broader_impact_concerns": "The authors discussed the limitation of this work and their thoughts on future work.\nIt would be great if the authors could discuss more on how to extend the proposed approach to generic and more involved neural nets with, e.g., not necessarily nonnegative weights, other activation rather than ReLU, more layers, etc.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers are all in favour of accepting the paper and to the extent that the paper is sound and adequately presents the full mathematical derivations and description of experimental results, it should be accepted. The authors should follow-up on the comments made by the reviewers and add a fuller description of the positivity constraint on A in particular, and also discuss the new experimental results about what happens when the conditions don't hold. 
Decision: Accept (poster)