Nonparametric Learning of Two-Layer ReLU Residual Units
Authors: Zhunxuan Wang
Linyun He
Chunchuan Lyu
Shay B Cohen
Venue: ICLR 2022 Submitted (2022)
Keywords: neural network learning
nonparametric methods
convex optimization

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 nonnegative full-rank matrix 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 statistical strong consistency of our algorithm, and demonstrate its robustness and sample efficiency  through experimental results.

Under review as a conference paper at ICLR 2022
NONPARAMETRIC LEARNING OF TWO-LAYER RELU RESIDUAL UNITS
Anonymous authors Paper under double-blind review
ABSTRACT
We describe an algorithm that learns two-layer residual units using rectified linear unit (ReI.U) activation: suppose the input x is from distribution with support space 12d and the ground-truth generative model is residual unit of this type, given by y B (A*x)* + x where ground-truth network parameters A E Rdxd
represent nonnegative full-rank matrix and B" E <Rmxdd is full-rank with 2 d and for e E TR., [c+]: = max m0, c.). We design layer-wise objectives as function- als 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 program- ming (LP). We further prove the statistical strong consistency of our algorithm, and demonstrate its robustness and sample efficiency through experimental results.
INTRODUCTION
Neural networks have achieved remarkable success in various fields such as computer vision (LeCun Cun al. [998 Krizhevsky et al.] 2012 He et al., (216 and natural language processing (Kim 2014 4
Sutskever el 2014). This success is largely due to the strong expressive power of neural networks
(Bengio & Delalleau 2011), where nonlinear activation units, such 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 al.) 2013). However, the nonlinearity of neural networks makes
them significantly more difficult to train than linear models (Livni et al. (014). 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.
Residual networks, or ResNets (He et al. 20l are a 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, e.g. achieving least 93% test accuracy on CIFAR- 10 classification, lowering single-crop error to 20.1% on the 1000-class ImageNet dataset (Russakovsky et al. 2015 He al. 20166).
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.) 20166). Given the flexibility and simplicity of residual units, much theoretical work has been devoted to study them and develop training algorithms for them in a way that sidesteps from the standard backpropagation regime and provides guarantees on the quality of estimation (see subsection 1.T). In this paper, we propose algorithms that can learn a general class of single-skip two- layer residual units with ReL.U activation shown on right the equation: y = =B (Ax)+ + +X
where for scalar e, et max (0, c) (for vector, this maximization is applied coordinate-wist

---

Under review as a conference paper at ICLR 2022
is random vector the network input with support space R and A E R and B weight matrices of layer and layer 2, respectively.
R Rmxd
Compared to previous work (Ge et al., 2018
2017; Zhang al. 2018 Wu et al. 2019; Tian 2017
Du et al. 2017 Brutzkus & Globerson 2017 Soltanolkotabi 2017; Li & Yuan 2017 Zhong ct al.
2017p, 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 assume a specific input distribution nor that the distribution is symmetric (Ge et al. 2018 Du & Goel 2018).
We show that under regularity conditions on the weights of the residual unit, the problem of learning the unit can be formulated through quadratic programming (QP). We use nonparametric estima- tion (Guntuboyina al. 2018) 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
Provable learning of neural networks has become an important topic of research. Arora et al. (2014) recover a multi-layer generative network with sparse connections and Livni et al. (2014) 4) study the
learning of multi-layer neural networks with polynomial activation. Goel et al. (2018) learns
one-layer convolution network with a perceptron-lice rule. They prove the correctness of an iterative algorithm for exact recovery of the target network. Rabusscau et al. (2019) describe spectral algorithm for two-layer linear networks. Recent work has connected optimization and two-layer
network learning (Ergen & Pilanci [021] Sahiner et al. 2020 Ergen & Pilanci 20200 Pilanci &
Ergen 2020) and has showed how to optimize networks layer by layer (Belilovsky et al. 2019).
For learning one-layer ReLU network, Wu al. (2019) optimize the norm and direction of neural network weight vectors separately, and /Zhang et al. (2018) use gradient descent with a specific initialization. For learning two-layer ReLU network, Ge et al. (2017) redesign the optimization landscape such that it is more amenable to theoretical analysis and Ge et al. (2018) use moment- based method for estimating neural network JJnzaaminn
(2015). Many others have studied ReLU
networks in various settings (Tian 2017 Du et al. 2017 Brutzkus & Globerson 2017 Soltanolkotabi
2017
Li Yuan 2017 Zhong et al. 2017 Goel Klivans 2017).
The study of ReLU networks with two hidden layers has also been gaining attention (Goel & Klivans 2017 Allen-Zhu et al. 2019), with a focus on PAC learning (Valiant) 1984). In relation to our work, Allen-Zhu & L. (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 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 et al. (2088) treat the final output of shape- restricted regressor as a 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 et al. 2011), shape-restricted additive models (Myerr 2013 Chen & Samworth) 2016) and shape-restricted single index mod-
els (Kakade et al. 2011
Kuchibhotla et al. 2017).
1.2 MAIN RESULTS
We design quadratic objective functionals with linear bounded feasible domain that take network parameters and functions as variables to estimate the ground-truth network parameters and nonlinear- ities. The values of the objectives are moments over the input distribution. Thm. 1.1 summarizes the landscapes of the objectives.
Theorem 1.1 (objective landscape, informal). Suppose a ground- truth residual unit has nondegener- weights in both layers and nonnegative weights in layer 1. Then there exist quadratic functionals defined in conetr-cnnt domains whose minimizers a) are unique, and are the exact ground-trutt or b) are unique, but can be adjusted to the exact ground-truth.
2

---

Under review as a conference paper at ICLR 2022
In practice, the exact moments over unobserved variables are not available. We can only construct the empirical risk minimization (ERM) of the moment-valued objectives by generated samples. With functions variables in moment-valuce objectives being optimized nonparamettriclly, the empirical objectives become quadratic functions with linear constraints (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 solution to the QP available, the strong consistency of our network learner is guaranteed:
Theorem 1.2 (strong consistency, informal). Suppose samples are generated by a ground-truft residual unit that has nondegenerate weights in both layers and nonnegative weights in layer 1. Then there exists algorithu that learns network "h, the exact ground-truth sample size grows.
Assume A and B are student network weights of layer and 2. We first give warm-up vanilla linear regression approach only knowing A in Rdxd and B in mx (section 3). We then move to the details of our nonparametric learning for layer 2 (section 4), and similarly, layer 1 (sectionn 5). We formalize Thmm. 1.] showing how nonparametric learning allows us to select the values of A and B from reduced spaces that are seeded by A and B", under which LR is faster than vanilla LR. In seccionn 6) we describe the strong consistency of our methods for respective layers, formalizing Thm. 1.2using the continuous mapping theorem (Mann & Wald 1943).
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 æ Rd input and return vector E R. We use A' E Rddd and B" E Rxx to denote the ground-truth network parameters for layer and 2, respectively. We use circumflex denote predicted terms (e.g. an empirical objective function f. estimated layer weights A). We use n to denote the number of i.i.d. samples available for the training algorithm, (x:(0, (") to denote the i-th sample drawn. For an integer k. We define [k] to be 2I, k), and e(i) as the standard basis vector with 1 at position j. All scalar-based operators are element wise in the case of vectors or matrices unless specified otherwise. We use x and y to refer to the input and output vectors, respectively, as random variables.
Linear Regression: Linear regression (LR) in this paper refers to the problem of estimating L for unbiased model y Læ. In this case, estimation is done by minimizing the empirical risk 1 Eie(n]
R (L) = 2n [n] || Lx(()) - 01 using linear least squares (LLS). Its solution has a closed form which we use as given. We refer the reader to Hamilton 1994) for more information.
Models, Assumptions and Conditions Following previous work (Livni et al. 2014), we assume a given neural network structure specifies 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 set to be residual unit taken from the hypothesis class with the form:
y B (A'x) + +x]
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 x (it breaks symmetry). This helps us circumvent issues of identifiability]] and allows us to precisely estimate the ground-truth weight matrices A and B*
Our general approach for residual unit layer learns scaled ground-truth weight matrix that also minimizes the layer 2 objective. The existence of such scaled equivalence of our layer 2 approach comes from what is defined below.
Here, referring to the ability identify the model parameters using infinite samples.
3

---

Under review as a conference paper at ICLR 2022
Definition 2.1 (component-wird wise scale transformation). A matrix A E Raxd is said to be scale transformation w.r.t. the j-th component if (Aj.:) Aju eli)
Additionally, estimation is more complex when the layer 2 weights B' is nonsquare. For simplicity of our algorithm presentation for layer 2, we stick to Conon 2.1 in the following sections
Condition 2.1 (layer 2 objective minimizer unique). A" is not scale transformation w.r.t. any components and B" a square matrix, i.e. m d.
3 WARM-UP: VANILLA LINEAR REGRESSION
Consider a ground-truth two-layer residual unit. If we assume that the inputs only contain vectors with negative entries, i.c. x 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 = x. Thus, direct LR on samples with negative inputs can learn the exact ground-truth layer parameter B" with at least d samples, when formulating the LR as solvable full-rank linear equation system.
On the contrary, if the imputs only contain vectors with positive entries, i.c. 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 a single weight matrix D' this is also linear model. Direct LR on at least d samples with positive inputs by the residual unit can learn the exact D Since we have the access to the exact B solving for the exact
A' can be accomplished through solving a full-rank linear equation system B A 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..dd with respect to each entry all negative entries is p". where p- is the probability of sampling a negative vector entry, then the expected number of samples to get one negative vector is 1/p".. Denoting p- similarly, 1/p". samples are expected for positive vector. Besides, each LR step in this approach requires d such samples respectively to make the linear equation system full-rank, which implies the expected sample size to be d-exponential d (1/p" + 1/r(). For other common random vectors like Gaussian samples, the proportions of fully negative/positive vectors in sampled inputs are also expected to decrease exponentially as grows, as higg--iieeniionl random vectors like Gaussian are essentially concentrated uniformly in sphere (Johnstone) (0066). Technical and experimental details about sample size expectations and the vanilla LR algorithm are further discussed in AApeendix F
example, the probability of sampling vector with
4 NONPARAMETRIC LEARNING: LAYER 2
We present how we learn residual unit layer 2 under Cond. 2.1 (estimating B*); We first design an objective functional with the arguments being a matrix and a function. The objective uses expectation of a loss over the true distribution generating the data and is uniquely minimized by [B']-1 and a rectifier function (ReI.U). We then formulate its ERM using nonparametric estimation as a standard convex QP, further simplified as an LP that has the same capability as the QP to learn layer 2.
4.1 OBJECTIVE DESIGN AND LANDSCAPE
Consider the formulation of a residual unit as in Eq. 1
It is possible to rewrite the model as equation:
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 æ + (A'z) 'x) by a function variable h. The objective is formulated as risk functional by the I error between values respectively computed by C and h
C"y = x +
G2 (C, h)
2 Fx [[
+ ( x10++xCyylpp -yll
2
In Appendix G we show that estimation of B" remains solvable without satisfying Cond. 2.1
4

---

Under review as a conference paper at ICLR 2022
where the estimator C E Rdxm the domain of h is the nonnegative continuous R R function space, written as Co in shorthand. This objective is quadratic because the forward mapping a + h(x) + æ and the backward mapping + C'tl are both linear w.r.t. C and h, and the two are linearly combined in I,2 norm. The objective in [Eq. is minimized by the ground-truth, i.e. C" and + (A"a) is of its minimizers. However, it is not simple describe other variable values that minimize the objective if any exist. We give that detail under Cond. 2. the minimizer of G2 is unique, as the exact ground -truh in the given domain.
Theorem 4.1 (objective minimizer, layer 2). Define Gz(C, h) as Eq. where C E gd h E Co 2200 Then under Cond. 2.1 (2 h)) reaches its zero minimum iff C [B]]] and x + (A" x)
Technical details are in Appendix HI where we use Lem. 4.2 (in subsection 4.3) to prove a more general theorem which does not require Cond. and sufficient for Thm. 4.1 In the next subsection, construct the ERM of G2 and present our convex QP formulation.
4.2 ERM WITH NONPARAMETRIC ESTIMATION CONVEX QP
Consider the second layer objective Eq. 2 with nonnegative continuous function space as the domain of h. We follow Vapnik (1992) and define its standard empirical risk functional:
G2(C,h)
1
Σ VE(M)
h(x) + x(() CCy(
(3)
2n
The function variable h E C22 can be optimized either parametrically or nonparametrically. If we parameterize h, and show that the nonlinearity w.r.t. its parameters would make G2 lose its quadratic form. Instead, we estimate h nonparametrrcally: for each sample input (9), we introduce variables ( that estimates mapped values by h. This avoids introducing nonlinearity to the objective and keeps G2 quadratic. On the other hand, the domain of h, i.c. nonnegative continuous function space, turns into a set of linear inequalities as constraints when optimizing nonparametrically. this sense, learning the second layer of the residual unit can be formulated as the following QP:
ANPE min 22
(C,
Σ EE|D]
( + ( - 0y s.t. g 20, ViEi [n].
(4)
2n
where E = ( is the nonparametric estimator of æ + (A' (Axx)*
Nonparametric Estimation Validation: solution to the ERM with nonparametric estimation, i.e. the QP. is guaranteed to be sufficient for minimizing the standard empirical risk functional (Eq. 3). More specifically, assuming C and E = ( are a solution to layer QP (Eq. 4h. it is clear that C' and E CO such that (x((())) = (()) minimize the empirical risk functional Eq. Conversely, a minimizer of the standard empirical risk [q. 3 C and ht, corresponds to a solution to layer 2 QP as we set g ( = (1). Therefore, minimizing G2 and solving layer 2 QP are empirically equivalent.
The convexity of the QP: Eq. 4 also guaranteed. First, constraints are linear. Second, for each sample with index i E [n]] the L norm wraps linearity w.r.t. C' and (+t), Such formulation ensures the quadratic coefficient matrix positive semidefinite. Thus, with the sum of convex
Convexity:
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 Appendixx I
4.3 LP SIMPLIFICATION
Cylla If there is feasible C' such that Cy - x 2 holds for all æ R2d, then C and h x + Cy x always minimize 92 as zero, and thereby minimize the layer 2 objective (Eq. 2}. Thus, we obtain a condition that is equivalent G. reaching the minimum in Thm. 4.1 and avoids randomness (see Lee. 4.2).
Consider single-sample enror written 92 (C, h,; 11h
3 Setting nonnegative ensures that a) only ReLU nonlinearity minimizes G2 (see Thm. 4.1 and b) h's nonparametric estimator lincarly constrained (explained in subsectioo 4.2).
'If h is not continuous function, only a null set of discontinuities possible make G2 reach zero its minimum. Setting continuous simplifies our theoretical results that still strictly support empirical discussion.
5

---

Under review as a conference paper at ICLR 2022
Algorithm Learn a ReLU residual unit, layer
Algorithm Learn a ReLU residual unit, layer 1.
Input:
((x(1), ( >= samples drawn by
Input: ((x((), h ) layer samples.
Eq. 1
2: Output: A, a layer 1 estimate.
2: Output: B, S, layer 2 and æ + (A"x)*
Solve QP: [q.
LP: [.q. 8 and obtain
estimate.
GA minimizer, denoted by A, ②. ( is no longer needed.)
3: Go to line if OP, line 5 if LP.
4: Solve QP:
Eq. 4 and obtain a G minimizer,
for all j E [d] do
denoted by C, E. Go to line 6
5: kj + LR( A ) Jn5050
5: Solve LP: Eg. and obtain minimizer Č
6: Á + Ag./hy. (Rescale A.
then assign < +- Cy 10.
7: end for
6: return C- E.
8: return Á.
Lemma 4.2. G2(C, reaches its zero minimum iff Cy x 2 0 holds for any x E Rd and its corresponding residual unit output y, and h x+ Cy x.
The pointwise satisfaction of the inequality in Lem. 4.2 describes the solution space for the mini- mization of G2. The sufficiency satisfying this inequality to minimize G2 is directly obtained by assigning h : + Cy where C' complies with Cy Rd. The necessity of satisfying this inequality comes from its contraposition: If a C' violates the inequality, there must be non-null set of æ that yield the violation due to the continuity of Cy In this sense, the resulting G2 value becomes nonzero.
2 0 for all x in the support space
Empirically speaking, we cannot solve inequality that holds w.r.t. every point in the support space we only observe finite samples. We can only estimate C' by solving the inequality that holds w.r.t each sample. Following this, we formulate such estimation as find feasible point in the space defined by a set of linear inequalities, each of which corresponds to a sample: Cy 2+) > 0. Each point in the feasibility defined by the inequalities has a one-to-one correspondence in the solution space to layer QP [Eq. 4 C + (C, (Cy( (+) )etm)) The set of inequalities can be solved by standard LP with constant objective and with constraints that are inequalities, i.e.
min const, s.t. Cy C
(1) 2 0. Vi E (m).
With the one-to-one correspondences, LP: Eq. 5 and QP: Eq. 4 have equivalent solution spaces. Moreover, LP: Eq. is also convex program. Alg. summarizes the layer 2 estimator: Simply solve the QP/LP and return the inverse of C' as the estimate of layer weights and $ as + (A"x)* estimate. Regardless of time complexity, QP and L.P in Alg. work equivalently since their solution
spaces are equivalent to each other.
Our nonparametric learning directly finds unique layer 2 estimate under Cond. 2.1 In the general case without [ond. 2. (discussed in (Appendix G), nonparametric learning essentially reduces the possible values of B from mm to a B* scale-equivalent matrix space, where LR uses sampled data much more efficiently than vanilla LR on layer (section 3).
5 NONPARAMETRIC LEARNING: LAYER
With layer learned, outputs by hidden neurons become observable. The two-layer problem is thereby reduced to single-layer. Consider a ground-truth single-layer model: = (A"x)+. To construct a learning objective for this model, rewrite the model as nonlinearity plus linear mapping by A h (-A*x) x+* + A"x, where on both sides of the equation is the output of layer 1, and the nonlinearity is x (- A xx):" The objective of layer 1 is formulated
G (A, r) - Ex [|](()) Ax
1999) (a free solver under GPI.v3 license) and salves our convex QP/L polynomial time. See Appendix for technical details.
'We use CVX Grant & Boyd 2014 2008 that calls SDPT3 Toh et al.

---

Under review as a conference paper at ICLR 2022
where A R is of the layer 1 weights estimator, the domain of r is also C The minimizer A of the risk G1 falls into a matrix space such that for any matrix A in the space, each row of A is a cowled-down version of the same row of A without changing the direction 5.I.
Theorem 5.1 (objective minimizer space, layer 1). Define Gi (A. r) as Eq. 6 where A E Rdxd r CD Then Gi rA reaches its zero minimum iff for each E [d. Aj ki Aj, where 0 s h3 I 1, and r: a + (A*x)* - (iag(() A'xx.
The scale equivalence in the solution space is derived from ReLU inequality: (x)* > kx where 0 < k 1 1. Let the j-th row of A be a scaled-down version of A", i.. Ay.: = kyAj, where S ky S 1. According to the inequality, we have (A). 2 k; AJ. a. which indicates (A*a)) 2
diag(k) (k) A'*.. Thus, r minimizing G1 in Thm. 5.1 lies in feasibility C22 when A = diag (k) A"
Due the existence of scale equivalence, we must compute the scale factor obtain the ground-truth weights A The scale factor kj is sufficiently obtainable with (A,, and (A observable: Conditioned on nonnegative ReLU input, we have a linear model AJ. kj A J. where A
and A x are observed. Thm. 5.2 summarrizs layer I scale factor property, allowing us to correct a minimizer of G to the ground-truth weights A' by computing 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,.x) / (A), is always equal to the scale factor k; given that (Aj:x)+ O.
The elimination of randommess for G1 follows the same pattern as layer 2. If there is a feasible A such that (A*x) + - Ax 2 O holds for all x E Rd such A is a solution to our objective by Eq. 6 We can also have the following proposition that avoids randomness.
Lemma 5.3. G1 rA) reaches its zero minimum iff h Ax 2 0 holds for any x E TRd and its corresponding hidden output h, and x + 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 nonnegativity of r:
min ANPE
(A,
1
Σ 6
Az
h00)
s.t. Φ Vi
2n
5E/m]
where 4 = 1 is the function estimator of x + (A x diag(k) A where k refers to the scaling equivalence. Similarly, the solution space of QP: Eq. can be represented by a set of linear inequalities as constraints of the following efficiently solvable LP
min const, s.t. h (+) Am! 0, Vie [n]. A
Alg. 2 describes how a layer 1 is learned: First, a G₁ minimizer estimate is obtained by solving
the QP/LP. Then for the j-th row, the scale factor kj is estimated by running LR h.))) and A x,
s.t. 1/))) 0 to correct A, A, k,h is an unbiased linear model given that h, > 0. By nonparametric learning, the value space of A is reduced from dxd to {diag(k) where LR uses sampled data much more efficiently than vanilla LR layer 1 (section 30.
(k) -A) S kj S 1}.
6 FULL ALGORITHM AND ANALYSIS
The full algorithm concatenates Alg. Tand 2 in layerwise fashion, with observations of input/output by the ground- truth network: a) Estimates layer 2 and nonlinearity: + (A'x)* by Alg.
b) Estimates layer by running Alg. on input samples and the nonlinearity estimate. It has provable guarantees. For empirical analysis, we use C, denote the estimation of C* from n random samples. Similar notations are applied to other estimations. First of all, our methods to solve respective layers, are strongly consistent if any convex QPs/LPs involved can be solved exactly.
Alg. and 2
Lemma 6.1 (layer 2 strong consistency). Under Cond. 2.1 C, a. C' and B, a. B" n co.
For C, In Appendix we prove its more general a.s. convergence without satisfying Cond. 2.1 where the solution space to layer 2 objective is non-compact continuous set where all the elements
7

---

Under review as a conference paper at ICLR 2022
scaling equivalences. We use Hausdorff distance (Rockafellar & Wets 2009 as metric and prove that the empirical solution space a.s. converges to the theoretical solution space. Then the more general a.s. convergence holds with the strong consistency of layer 2 scale factor estimator where use LR to estimate the scale factors.
For B, Using the continuous mapping theorem (Mann & Wald 1943), we directly propagate the strong consistency of C" estimator to its inverse B" s estimator.
According to full algorithm description, layer estimation uses C,,y (1) x(1) as the outputs where i 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 Lem. 6.2p
Lemma 6.2 (layer strong consistency). A, 6.5. A 11 X0.
By the continuous mapping theorem, the strong consistency of the full algorithm (Thm. 6.3 formal version of [Tmm 1.2), which is commonly defined by a loss function that continuous on network weights, is implied by the strong consistency of network weights estimators (Lem. 6. and 6 See Appendix for proof' of strong consistency discussions in this section.
Theorem 6.3 (strong consistency, formal). Define L as L² output loss. L(A,, B,) 0.s. O, n + oo.
7 EXPERIMENTS
We provide experimental analysis to demonstrate the effectiveness and robustness of our approach
in comparison to stochastic gradient descent (SGD) on 1.2 output loss: L(A, B) = Ex y yll?.
where we parameterize the output prediction by ý =B (Ax)*= + +x]. Our proposed methods outperform SGD in terms of sample efficiency and robustness to different network weights and noise strengths, which indicates poor optimization landscape of L output loss for ReLU residual units.
Setup: The ground-trute truth weights are generated through i.i.d. folded standard Gaussiar and standard Gaussian for layer 1 and 2 respectively, i.e. A Lid. [W| (0(0, 1), B Lid. (O 1). The input distribution set to be an i.i.d. zero mean Gaussian-uniform equal mixture N 1) -24 (.19,, is conducted on 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 1) = 70/ (1+7-27 with initial rate No = 10-3 and decay rate ? 10-5, where T is the epoch number. The above hyperparameters are tuned to outperform other hyperparameters in learning ReLU residual units in terms of output errors.
1.1). SGD)
Evaluation: We use relative errors measure the accuracy of our vector/matrix estimates: For a network with weights A and B and its teacher network with weights A and B", a) layer error refers to A A |I ||A/| similar to layer 2. b) output error refers to É [lý yll / ||y 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- ground-truths are computed as means across 16 trials.
Consider FindderFFig... 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 is using. We compare SGD against our algorithm. We observe that approach 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 as our method is larger. Still, overall, our method is capable of learning robustly with small sample sizes and more efficiently than SGD even for larger sample sizes.
Sample Efficiency:
Network Weight Robustness: This experiment aims to verify whether our method can learn a broader class of residual units. In Tab. I our method shows a light-tailed distribution with nearly zero means and standard deviations for layers 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.
A folded Gaussian is the absolute value of a Gaussian, with p.d.f. p(xx) where N,, denoted as [W]. We folded Gaussian ensure layer 1 weights are nonnegative.
8

---

Under review as a conference paper at ICLR 2022
800
Ours
:4
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 d 16. 512 training samples drawn for each learning trial.
12
12
14
16
29
100 152 224 256 238 120 252 360 Sauple Sac
100 192 224 256 238 300 352 304
Sample Saee
Figure 1: 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
Sid
Mean
Std
SGD Ours
0.715
0.090
1.203
0.134
0.431
0.038
0.039
0.00S
0
0.055
0.008
0.5
0.409
0.0
Outpil Iever
Layer Mano
Layoz Bloo
08
0.6
02
OP
GP
0.6
0m
0.2
0.2
066 Nolio Strongth
0.4
0.8
0.2
0.4
0.5
0.
0.2
0.4
0.5
08
Naiso Stronggth
Noten Steength
Figure 2: Respective errors of layers 1 and 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.
Noise Robustness: Fig. 2 confirms the robustness of our methods when output noise exists. Samples generated by ground-truth residual unit with output noise being i.i.d. 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 it is hardly affected by tuning the noise strength. For QP/LP, all the errors for layer 2 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.
8 CONCLUSION
In this paper, we address the problem of learning a general class of two-layer residual units and propose algorithm based on landscape design and convex optimization: We demonstrate firstly that minimizers of our objective functionals can express the exact ground-truth network. Then, we show that the corresponding ERM with nonparametric function estimation be solved using convex QP/LP, which indicates polynomial-ting algorithms that are used to estimate both layers well as the whole networks are strongly consistent, with very weak conditions on input distributions.
solvability w.r.t. sample size and dimension. Moreover, our
Our work opens the door to variety of open problems to explore. We provide strong consis- tency result without assuming a particular input distribution. It would be interesting to explore the sample complexity of our algorithm when stronger assumptions are placed on input distribution. Another extension could be to dispose of the limitations on ground-truth weights, e.g. 2 d, non-degeneration, nonnegativity of A". In addition, given that our algorithm solves ReLUU by using nonparametric estimation through convex optimization, this might provide inspiration to solving learning problems with other nonlinearities using nonparametric methods that improve or change the optimization landscape.
See Appendix for noisy model discussion.

---

Under review as a conference paper at ICLR 2022
REPRODUCIBILITY STATEMENT
The full of assumptions of all theoretical results in this paper are stated |section Appendix and G The complete proofs of all theoretical results are all included - Appendix [ G
H
and
Code MATLAB is zipped as supplementary file. The numerical simulation details, incluning data
sizes and splits, hyperparameters and how they were chosen, clear definitions of the specific measures
or statistics used to report results, are discussed in detail the Setup and Evaluation paragraphs in section 7 Results with central tendency (e-g. mean) and variation (e.g. stddev) are reported Tab. The use of external computing infrastructure, CVX, clarified, and the consent obtaining and
licensing of CVX and SDPI3 solver used in this work exactly follows the original author instructions:
http://cvxz com/ Cvx/
www//oc/ceeceee/cooo doc/ ctxx//ooccitingo citgiiiiiii..................iie html
Tootnote
REFERENCES
Zeyuan Allen-Zhu and Yuanzhi Li. What can ResNet learn efficiently, going beyond kernels? In Advances in Neural Information Processing Systems, pp. 9015-9025, 2019.
Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization in overparameterized neural networks, going beyond two layers. Advances in neural information processing systems, pp. 6155-6166, 2019.
Sanjeev Arora, Aditya Bhaskara, Rong Ge, and Tengyu Ma. Provable bounds for learning some deep representations. International Conference on Machine Learning, pp- 584-592, 2014.
Miriam Ayer, H Daniel Brunk, George Ewing, William Reid, and Edward Silverman. An empir- ical distribution function for sampling with incomplete information. The annals of mathematical statistics, pp. 641-647, 1955.
Eugene Belilovsky, Michael Eickenberg, and Edouard Oyallon. Greedy layerwise learning can scale to imagenet. In International conference machine learning, pp. 583-593, PMLR, 2019.
Yoshua Bengio and Olivier Delalleau. On the expressive power of deep architectures. In International Conference on 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 ( 1940), 27(1):247-271, 1909.
Hugh D Brunk. Maximum likelihood estimates of monotone parameters. The Annals of Mathematical Statistics, pp. 607-616, 1955.
Alon Brutzkus and Amir Gloherson. Globally optimal gradient descent for a ConvNet with Gaussian inputs. ArXiv, abs/ 702./700..7966. 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-754, 2016.
Simon S. Du and Surbhi Goel. Improved learning of one-hidden-layer convolutional neural networks with overlaps. ArXiv, abs/1805.0777 2018
Simon S. Du, Jason D. Lee, Yuandong Tian, Barnaáás Póezos, and Amrendra Kumar Singh. Gra- dient descent learns one-hidden-layer cnn: Don't be afraid of spurious local minima. ArXiv, abs/1712.00079, 2017.
Tolga Ergen and Mert Pilanci. Revealing the structure of deep neural networks via convex duality. arXiv preprini arXiv:2002.09773 2020.
Tolga Ergen and Mert Pilanci. Implicit convex regularizers of enn architectures: Convex optimization of two-and three-layer networks in polynomial time. In International Conference on Learning Representations (ICLR), 2021.
J Farkas. Ober die theorie der einfachen ungleichungen. J. Reine Angew. Math, 124:1-24, 1902.
Rong Ge, Jason Lee, and Tengyu Ma. Learning design. arXiv preprint 17Xv:/71110000// 2017.
neural networks with landscape
10

---

Under review as a conference paper at ICLR 2022
Rong Ge, Rohith Kuditipudi, Zhize Li, and Xiang Wang. Learning two-layer neural networks with symmetric inputs. arXiv preprint arXiv:1810.0679) 2018.
Surbhi Goel and Adam R. Klivans. Learning neural networks with two nonlinear layers in polynomial time. In COLT, 2017.
Surbhi Goel, Adam R. Klivans, and Raghu Meka. Learning one convolutional layer with overlapping patches. ArXiv, abs/1 802.02547, 2018.
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. 10. Springer- Verlag Limited, 2008. http: //stanford. wwwpedddoooooeeeeeeeeeeee dep.
Michael Grant and Stephen Boyd. CVX: Matlab software for disciplined convex programming. version 2.1. http: com CVX March 2014.
Adityanand Guntuboyina, Bodhisattva Sen, et al. Nonparametric shape-restricted regression. Statisti- cal Science, 33(4):568 5948,59942772 2018.
James Douglas Hamilton. Time series analysis, volume 2. Princeton university press Princeton, NJ, 1994.
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 pattern 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.
Majid Janzamin, Hanie Sedghi, and Anima Anandkumar. Beating the perils of non-convexity: Guaranteed training of neural networks using tensor methods. arXiv preprint 156444150 2015.
Florian Jarre. On the convergence of the method of analytic centers when applied to convex quadratic programs. Mathematical Programming, 49(1-3):341-355 1990.
Robert I Jennrich. Asymptotic properties of non-linear least squares estimators. The Annals of
Mathematical Statisties, 40(2):633-643, 1969.
lain M Johnstone. High dimensional statistical inference and random matrices. arXiv preprint math/0611589, 2006.
Sham M. Kakade, Adam Tauman Kalai, Varun Kanade, and Ohad Shamir. Efficient learning of generalized linear and single index models with isotonic regression. In NIPS, 2011.
Narendra Karmarkar. A new polynomial-time -ime algorithm for linear programming, In Proceedings of the sixteenth annual ACM symposium on Theory of computing, pp. 302-311, 1984.
Yoon Kim. Convolutional neural networks for sentence classification. arXiv preprint 1408.::408.8888 2014.
Mikhail K Kozlov, Sergei P Tarasov, and Leonid G Khachiyan. The polynomial solvability of convex quadratic programming. USSR Computational Mathematics and Mathematical Physics, 20(5): 223-228, 1980.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolu- tional neural networks. Advances in neural information processing systems, pp. 1097-1105, 2012.
Arun K Kuchibhotla, Rohit K Patra, and Bodhisattva Sen. Efficient estimation in convex single index models. Preprint. Available at, 2017.
Yann LeCun, Léon Bottou, Yoshua Bengio, Patrick Haffner, et al. Gradient-bo based learning applied to document recognition. Proceedings of the IEFE, 86(1) (6(11):22782222) 1998.
11

---

Under review as a conference paper at ICLR 2022
Yuanzhi Li and Yang Yuan. Convergence analysis of two-layer neural networks with ReLU activation. ArXiv, hass/7755.0886, 2017.
Roi Livni, Shai Shalev-Shward and Ohad Shamir. On the computational efficiency of training neural networks, Advances in neural information processing systems, pp. 855-863, 2014.
David G Luenberger. Optimization by vector space methods. John Wiley & Sons, 1997.
Andrew L Maas, Awni Y Hannun, and Andrew Y Ng. Rectifier nonlinearities improve neural network acoustic models. In ICML 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-226, 1943.
Mary C. Meyer. A simple new algorithm for quadratic programming with applications in statistics. Communications in Statistics Simulation and Computation, 42:1 22:1126-11 139, 2013.
Renato DC Monteiro and Ilan Adler. Interior path following primal-dual algorithms, part ii: Convex quadratic programming. Mathematical Programming, 44(1-3):43 66, 1989.
Katta G Murty. Computational complexity of parametric linear programming. Matherattiaa programming, 19(1)2213211, 1980.
Vinod Nair and Geoffrey E Hinton. Rectified linear units improve restricted boltzmann machines. In Proceedings of the 27th international conference on machine learning (ICML-10), 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 International Conference on Machine Learning, pp. 7695-7705. PMLR, 2020.
Guillaume Rabusseau, Tianyu Li, and Doina Precup. Connecting weighted automata and recurrent neural networks through spectral learning. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. (630-1639, PMLR, 2019.
R Tyrrell Rockafellar and Roger J-B Wets. Variational analysis, volume 317. Springer Science & Business Media, 2009.
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, al. Imagenet large scale visual recognition challenge. International journal of computer vision, 115(3):211-252, 2015.
Arda Sahiner, Tolga Ergen, John Pauly, and Mert Pilanci. Vector-output ReLU neural network problems are copositive programs: Convex analysis of two layer networks and polynomial-timg algorithms. arXiv preprint arXiv:2012.13329, 2020.
Emilio Seijo, Bodhisattva Sen, et al. Nonparametric least squares estimation of a multivariate convex regression function. The Annals of Statisties, 1633 2011.
Pranab K Sen and Julio M Singer. Large sample methods in statistics: an introduction with applica- tions, volume 25, CRC press, 1994.
Alexander Shapiro, Darinka Dentcheva, and Andrzej Ruszczyóski. Lectures on stochastic program- ming: modeling and theory. SIAM, 2014.
Mahdi Soltanolkotabi. Learning ReLUs via gradient descent. In NIPS, 2017.
Ilya Sutskever, Oriol Vinyals, and Quoc Le. Sequence to sequence learning with neural networks. In Advances neural information processing systems, pp. 3104-3112, 2014.
Yuandong Tian. An analytical formula of population gradient for two-layered ReLU network and its applications in convergence and critical point analysis. In ICMI., 2017.
12

---

Under review as a conference paper at ICLR 2022
Kim-Chuan Toh, Michael 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-5111 1999.
Leslie Valiant. theory of the learnable. Commun. ACM, 27:1134-1142, 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, pp. 831-838, 1992.
Shanshan Wu, Alexandros G. Dimakis, and Sujay Sanghavi. Learning distributions generated by one-layer ReLU networks. In NeurIPS, 2019.
Yinyu Ye and Edison Tse. An extension of karmarkar's projective algorithm for convex quadratic programming. Mathematical programming, 44(1-3)1157-179 1989.
Xiao Zhang, Yaodong Yu, Lingxiao Wang. and Quanquan Gu. Learning one-hidden-layer ReLU networks via gradient descent. ArXiv, 0tt//800607760 2018.
Yin Zhang, Richard Tapia, and John E Dennis, Jr. On the superlinear and quadratic convergence of primal-dual interior point linear programming algorithms. SIAM Journal Optimization, 2(2): 304-324, 1992.
Kai Zhong, Zhao Song, Prateek Jain, Peter L. Bartlett, and Inderjit S. Dhillon. Recovery guarantees for one- neural networks. In ICML, 2017.
APPENDICES
We include an outline the appendices:
Appendix A An empirical analysis of the running time of our algorithm and an analysis of the effect of condition number on the estimation accuracy.
Appendix B A brief discussion of our learning algorithms in noisy context, referring to the L.P slack variable technique that is used in our experiments with noise in the main paper. Also, this section provides an insight to potential future direction of this work.
Appendix C A detailed explanation of the computational complexity and the methods
through which the QPs/LPs this paper are solved.
Appendix D A preliminarily proposed general optimization formula for the extension of learning multi-layer ResNets, to show the scalability of our algorithm.
Appendix E. A justification of how our QP/LP approaches get rid of the exponentiality that vanilla LR approach (section 3) has.
Appendix formal result and an empirical validation the example given in the main paper in the context of the vanilla linear regression method (section 3).
Appendix G
A generalization of layer 2 learning to the case where Cond. 2.1 is not satisfied.
Appendix
Proofs regarding the minimizers of the objective functions we use.
Appendix
Proofs that justify the convexity of our QPs.
Appendix
Proofs that show our estimation algorithm is strongly consistent.
A RUNNING TIME AND SENSITIVITY TO CONDITION NUMBER
Following the setup in section 7| report additional experiments testing the running time of our algorithm in comparison to SGD and the feasibility of estimating the inverse of B when ill-conditioned.
13

---

Under review as a conference paper at ICLR 2022
16
Output Etroe (ts 1oba)
Outpul Mega
Ontpon losta)
50041
502-0 und
-62
-0
15
25
Rumning Time
Ronning Tame
Ruaning Time (6)
Figure 3: Output errors against running time by SGD and 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 LP algorithm against time used on 5 different ground-truth networks. We used 512 training samples, drawn for learning each ground-truth network. (CPU specification: 2.8 GHz Quad-Core Intel Core 17.)
SGD
11
d
10
d 16
d
32
d 32
Layer 2 Error
Layer 2 Error
10
18
30
10
10
10
16 x(B")
x(B")
Figure 4: Layer 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 mean across learning 32 different ground-truth networks with the same pair of d and a condition number for B The condition number is denoted by Λ: (B*). We used 512 training samples, drawn for learning each ground-trute network.
A.1 RUNNING TIME EFFICIENCY VERSUS SGD
In Fig. compare the running time of our algorithm against the running time of SGD for ground-truth networks sampled at random. The rumning time of our algorithm is significantly lower, with eиror level which is also significantly lower. Furthermore, this is demonstrated across input dimensions, where the difference between the running time of SGD until convergence and our algorithm's running time increases d increases. In addition, the running time of our algorithm is fixed, and does not depend on the ground-trute network, while the running time of SGD varies based on the network sampled.
A.2 LAYER 2 WEIGHTS CONDITION NUMBER ROBUSTNESS
Our algorithm depends on a matrix-inversinn step to obtain the estimated parameters. This affects the estimation of B Due to this, we further investigate the effect of the condition number of B" the ground-truth parameters network parameters with different condition number, we follow the procedure of Ge et al. (2018). and multiply diagonal matrix with exponentially-diee droopppnn values the diagonal (A for the i-th element) by two random orthonormal matrices, and V on the left and on the right respectively: B U diag -.....,-d)V
the accuracy of estimation. For this experiment, to obtain ground-truth
14

---

Under review as a conference paper at ICLR 2022
we compare the effect of the condition number of B' SGD and algorithm. SGD turns out to be quite sensitive to the condition number, especially for lower dimensions. Our algorithm, on the other hand, is almost not affected by the condition number, with a final estimation emor consistently close to 0, recovering the matrix B"
In Fig. 4
B DISCUSSION: NOISY MODEL
Here, we discuss our learning methods in the noisy case. We introduce output noise our model, namely
y= B" B= (A'x) +x +
(9)
where the label noise z Id is an i.idd random vector with respect to each component, satisfying E [2] O. In addition and x statistically independent.
Taking layer as an example, our original objective functional does not reach zero by substituting the ground-truth: (2 x + (A*x)*) = |=[l[""']]" x² Tr C'C"" where a is the noise strength. However, if layer is well conditioned, the ground-truth will still assign value close to zero to the objective. In this sense, with G2'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"y x 2 0, since Cry y x (A'x:** + C' z is not necessarily an entrywise nonnegative vector because the term C* z might have negative entries. So we introduce slack variables ç() to soften the constraints:
1 1 (())
Σ1
min C,Z
(10)
n iE|n]
s.t. Cy - 2 (0)) (()) 2202 20. 0.
(11)
For sample (x) (0) with noise z01 if (0) C'2(0 < 0, then its L norm would be added to the objective. This method remedies violations to the inequality C"y x 2 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.
C DISCUSSION: SOLVING CONVEX PROGRAMS
The theoretical foundation of solving convex QP and LP has been driven maturity in terms of computational complexity (Kozlov et al. 1980 Murty 1980) and convergence analysis (Jarre) 1990. Zhang et al. 1992). The time complexity for convex QP/LP is analyzed in terms of the number of scalar variables N and the number of bits L in the input Ye & Tse 1989). For example, under Cond. 2.1 N df + nd for the QP because the matrix variables have df scalars and the function estimators have nd scalars. Similarly we have N = d2 for the noiseless LP and N = d2 + nd for the noisy LP. is guaranteed that primal-dual interior point methods can solve the convex QP/LP in polynomial number of iterations O(vNL). where each iteration costs at worst O(N2.55 arithmetic operations from the Cholesky decomposition for the needed matrix inversion (Monteiro & Adler 1989 Karmarkar 1984p. This indicates that our QPs/I.Ps are guaranteed to be solvable in O(N3T) arthhmetic operations, which is generally Oppoly (n,, m, d, L)) complexity.
To solve convex QPs/LPs in this paper, we use CVX, a commonly used package for specifying and solving convex programs (Grant & Boyd 2014 2008). For both QPs and LPs, CVX calls solver, ceaeffintt-quurrttiiice -ineer programming and
SDPT3 (Toh et al., 1999), which is specified for applies interior-pont point methods with the computational complexity mentioned above. Experimentally. SDPT3 indeed specifies and solves our programs fast and makes our numerical results robust and stable.
15

---

Under review as a conference paper at ICLR 2022
D DISCUSSION: EXTENSION TO MULTI-LAYER
In this appendix, propose generalized optimization formula of nonparametric learning of multi- layer residual networks to show that our algorithm is scalable. Assume we have an L-layer network of the form
Tu xb
ri (Wi-) T--11 1....,, y Wi-1FL-1-
We can scale the objective to use nonparameter variables (c) hElL-1] to estimate every ReLU activation (Wir)) this network. Generally, for the 1-th ReLU we can have the outer layer objective
min V
+
{ + (0) Vih
s.t.
2 0
where hat denotes estimated values and h (+), and its corresponding inner layer objective
min 66 W
Wi-
( + ................................
(()) + x | s.t. Φ 2 0, E 2 0.
We apply techniques, e.g., tune the combinations of those objectives with respect layers whether to have a hat or not, or even get them weighted, to keep its convex quadratic form and at the same time improve its optimization landscape. Specifically when I. 2, this becomes the two-layer ResNet learning discussed in the main paper.
E SAMPLE EFFICIENCY: VANILLA LR VERSUS OURS
In this appendix, describe an example to justify how core QP/LP approaches climinate the exponential sample efficiency compared to the vanilla LR approach. In layer 2 learning, C's optimization is find feasible point in the space determined by inequalities each of which corresponds to a sample. Taking the j-th row the inequality, i.e. Cj. 2 Iz. Every time we get new sample (i), (+) in,
The inequality () 2 Ij eliminates the solution space of Cj.: by one of the spaces divided by plane Cy = x; This property guarantees fast convergence speed at early phase since Cj. 's feasibility starts from Rd
In fact, when ReLU does activate (* the j-th row, i.. A'x() < the theoretical solution of C₁,, that C₁,, B = (O,... 0, 1, ..O,..., (a at index j) directly lies on the divisive plane Cy.y = x
Cj.y ( = =G. (A
x(0)
=x
This property remarkably speeds up further constraints the solution space of Cj, the correct estimate and with high probability, since directly depends on the sign of A (1)
With the vanilla LR approach mentioned section alll 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.
16

---

Under review as a conference paper at ICLR 2022
Algorithm 3 Learn a ReLU residual unit by LR.
1: Input: {(z(1) >===+ nt samples drawn by Eq.
2: Output: A, B, estimated weight matrices.
3: B (az y) E ((x()) ) [n/2]
< 0}.
4: δ 4- LR{ (ar, y) E ((x() ) [n/2]+1 x > 0}. {the estimation B (A* + Ia)]
5: Solve full-rank linear equation system B B-Á- =Ā=
6: return À I B.
F VANILLA LINEAR REGRESSION: MORE DETAILS
Alg. 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 as example of the inefficiency of this method.
Theorem F.1 (exponential sample complexity, vanilla LR). Assume the input vectors are i.i.d. with respect to each component. Then [lgg. learns neural network from ground- trrth residual unit with at least O (d- (22+))) expected number of samples.
Proof. For each j E [d]. let Pj be the marginal probability of x, being positive, i.. P, = P(x; > 0) 0. Thus, the probability that sample is positive P(x 0) jEj Pj- Then the expected P.. Similarly, the expected number of sampling trials to obtain d negative samples is d/ [[jetd] [1 P3 P(x, 0)]. Let be a random natural number s.t. with samples the network has learned. The expected number of samples that guarantees successful learning is the of the expectations
number of sampling trials obtain d positive samples is d/ [[
1
Ein] d
[ieiq Pj
ILeta (1 - P3 - P(x; = 0)
2 d
[i Pj + IhELd (1 Pj)
2 d
II
VP, (1 PT)
jE(d]
2 d.2 II jE(d
(P, + - 12)
2d+1
Thus [[n] > O(d: 2d+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 in terms of both computational cost and sample size. While this approach to learning residual unit such as ours is simple and intuitive, we aim to improve on this approach, making full use of all samples available.
F.1 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 learn the exact ground-truth parameters.
17

---

Under review as a conference paper at ICLR 2022
Table Learning success rate of vanilla LR on residual units with input x i.d N (0. 1). The success rates shows exponentially decreasing trend with the same number of samples. The sample sizes to achieve close to the same rate grows exponentially as the number of dimensions grows linearly.
lel
1e2
5e2
1e3
5e3
le4
5e4
1e5
0.002
0.137
0.999
1
1
0.041
0.614
1
0
0.579
0.998
1
10
0
0.002
12
0.001
0.322
Table 3: Learning success rate of vanilla LR residual units with input ltd. N (0.1, 1). With the non-zero Gaussian mean, the success rates show an overall decline compared with the rates shown in Tab. 2 for zero-mean Gaussian inputs.
T1
lel
1e2
5e2
1e3
5e3
1e4
5e4
1e5
4
0.001
0.122
0.996
1
1
1
0
0.030
0.346
1
1
0
0
0.116
0.792
1
10
0
0
0.619
1
0.001
However, with degenerate linear systems, LR is completely incapable of learning the parameters. Therefore, there exists 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 evaluate the performance of L. with different sample sizes and number of dimensions.
Tab. shows the learning success rates with zero-mean Gaussian inputs, For each fixed number of dimensions, it appears there is hard threshold that switches the learnability of LR. The exponential sample complexity is also reflected there as the number of dimensions grows linearly. Tab. 3 shows the rates with input mean non non-zero, where an overall decline in success rates happens. This observation explainable because bottleneck of sampling positive and negative vector. A positive mean reduces the probability of the latter, and thereby increases the sample size required.
learning the lower value found between the probability
G GENERALIZATION OF LAYER 2 LEARNING
In this appendix, we discuss how layer 2 learned without satisfying Cond. 2.1 It is a fact that A' being scale transformation w.r.t. some components causes scaling equivalence to layer objective functional minimizers just as in layer To be more specific, we give general version of Thm. 4.1 that handles the case without Cond. 2.1 and describes the scaling equivalence of G2 minimizers. See Thm. G.T for a formal description.
Theorem G.1 (objective minimizer space, layer 2, general), Let G2 be 1EEx [1I (x) + Cyl?]
as functional, where C E d h E C2. Then G2 (C, h) reaches its zero minimum iff CB = diag(k) where for each j E [d].
a) I 1+4; S kg 1, if A a scale transformation w.r.t. the j-th component. b) kj A" is not scale transformation w.r.t the j-th component.
18

---

Under review as a conference paper at ICLR 2022
As in layer 1, the scaling equivalence in layer 2 can also be obtained by assigning A' as scale transformation w.rt. some component and using the properties of the ReLU nonlinearity. See subsection H.1 for detailed explanation of Thm. G.I] To obtain the scale factors k and correct scale-equivalent G2 minimizer to the ground-truth, we observe linear models parameterized by the scale factors, where for each j E [d], [Cyl, kjxj given that X See Thm. G.2 and its proof for justifications of the linear models that are used to compute k.
Theorem G.2 (scale factor, layer 2, general). Assume C' is minimizer of G1 in the context of Thm. G.I Then for any j E [d]. the following three propositions are equivalent:
a) A is scale transformation w.r.t. the j-th component.
b) Cyyl g |xg is a constant oj given that x3 < O.
c) [Cyly /xg is constant oj given that x3 > 0.
Additionally, if one of the above three propositions is true, then k- = C.g
Proof. For j E [d], we first prove a)
b)
c) From (At.)² AJ,s el) have
[Cyl,
[k)el
T
(A*x)*
+x
xj
Xj
K3 (A).x)* + +X/
kj (A],),s) +xy
Xj
Xj
Kgg
Kg
(Aj,
1).
Xj >
Then we prove
a
b)
C)
a)
3 E [d] and j" jss. Ajis * 0. Recall
kj (Ajxx) + + x3}
[Cyl,
X,
Xj
The value of Xy' affects the value of [Cyl, /x, because A3.3' F O. In fact, from supp p(x) = Rd we have supp p(x;' {z)) RR indicating that the value of (Cyl, /x, can never be kept constant when given both x, and x, 0 because Xy can be any real number.
With the exact derivations above, are able to obtain a left inverse of B", namely C, that satisfies CB' = Ia. Consider Eq. left multiplied by B
B'Cy=y.
(12)
Eq. i2 also noiseless unbiased linear model where Cy and y are observable, and thereby B* is computable due to the easy solvability of its linearity.
Alg. describes how residual unit second layer is learned without satisfying Cond. 2.1 We first solve the QP/LP and obtain a scaling equivalence to an estimated left inverse of B and the function estimate, namely Ć and E. Then we compute the scale factor estimate & by running Alg. 4 where for each component index E [d]. we first use a tolerance parameter as a threshold to determine whether ground-truth layer is scale transformation, and if so, run LR to estimate the model
[Cyl, kyx,, otherwise the scale factor is directly assigned by 1. Upon correcting Č and E by
k. we obtain layer 2 estimate B by running LR to estimate the linear model Eq. 12 The strong consistency of our results in this appendix justified in Appendixx J
H EXACT DERIVATION OF OBJECTIVE FUNCTIONAL MINIMIZERS
H.
LAYER 2
Lem. 4.2 is proved as follows.
19

---

Under review as a conference paper at ICLR 2022
Algorithm 4 Rescale T minimizer.
1: Parameters: Etol > 0, LR objective tolerance.
2: Input: {(z(*) ) samples drawn by [q. 1 C, a GNPE minimizer.
3: Output: k. layer 2 scale factor estimate.
4: for each j E [d] do
5: ky LR (5) [C
15}
1/ 6: if the LR objective optimal Ry(k,) >
Stal then
7:
Kg 1.
8: end if
9:
end for
10: return k.
Algorithm 5 Learn a ReLU residual unit layer 2.
Input: f(x:(9, ()) samples drawn by Eq.
2: Output: B, E. layer 2 and æ + (A*x) estimate.
3: Go to line if OP, line 5 if LP.
4: Solve QP:
Eq. 4 and obtain G minimizer, denoted by Č, S. Go to line 6.
5: Solve LP:
Eq.3 and obtain a minimizer C, then assign (()) Cyl
x(0) for each i [n]]
6: Run Alg. on (x y (0) [E)n) Ć a'd obtain k.
7: + LR diag (ke) C,y0y00 (
8: {(9) < diag (k) (5(0) + x0) - (+) for each i [m]. (Correct E to the function estimation
of (A'x) .]
9: return B, S
Proof. - Since h(x) Cy x 2 random vector l(x) - x - Cy always zero vector, which implies Gz(C,,) h) = 0. Hence = holds.
Since r.v. [lh(x) 1y we have
(2 =
(<ER"') [1h(z) + -cyl =0] 01)
(13)
where À is the Lebesgue measure on Rdd
Proof by contradiction: Assume that 3w' Rd. 3i [d]. s.t. (Cy'-x'), O, where y is the z); which continuous Rd. Therefore for = -f(x') > 0, 36 0, v E ((x;0) i.c | - fe'=xl|= < d,
corresponding network output. Let fzx (Cy (Cy=2),
[f(x) f(x') <E = 2f(x²) < f()) <0 = je -yl, >0
[h(z) Cyl, > |1(xx) + Cyll² >0. 0.
4/22
Since X (B(x; 8)) (d/22 1) 5d > and B(x; 8) is subset of the measured set in Eq. 13
we have contradiction. Thus Cy > 0 holds in a pointwise manner in Rd indicating
{ Rd 1((x) # Cy 2 must a null set. With h's continuity, à must be x + Cy x. holds.
Therefore
Lemma H.1. Cy 2 0 holds for any Bdd and its corresponding output y only if CB" is diagonal matrix.
Proof. Let D CB". We rewrite Cy x 2 Oas
x 2 0. D (A'x)* x) + #0
(14)
20

---

Under review as a conference paper at ICLR 2022
For further use, we substitute æ by - and the resulting inequality D (-A'x))
+ x 2
still holds. Added by Eq. 14 we have
D (
2)) dx1 2 0.
(15)
Proof by contradiction: Assume D is not diagonal, then Bi + j. such that Da, # 0. Consider the following two cases:
a) Dis > O. We take the i-th row of Eq. 14 as follows
Di, (Ak, x) " + Ib Iz.
(16)
Let Ø- = and Ij < O. Then Σi=1 Di.k A 2
+ Ik
Dig - Bg <0 = 1.
b) Dis < 0. We take the i-th row of Eq. 13 as follows
Di,k Ak. 2 20
(17)
Let (At)- v. where e(), Then 1k=1 Di, Ak.. -Di <0 - 1.
With Lem. 4.2 and Lem. H.l
we prove
Thm. G.1 as follows.
Proof. With Lem. 4.2
we only need to prove V E Rd, Cy x2-220 = CB = dk)
We have
Cy -y-z= x-- c- (A xx) + x - x = di) (A'x)) + x x.
(18)
For the i-th row of Eq. 18 consider the following two cases:
a) A A,, i.c. A is scale transformation w.r.t the i-th row. With 144;, $ k <
we have
(Cy x121 k; (A) + Iz
= (Ai,0r)) (k: 1) 5z-
x4 2 O. For x; 2 0, [Cy x), = (k: + kū - -1)
For v; < 0, (Cy x = (k: - 1) xz 2 0.
b) A # A,, With k; = 1 have
[Cy x), = k; xA)
+ 1
- - = (A 2 0.
Hence = "holds.
Let CB". With Lem. H.I D is diagonal. Consider the following two cases:
a) A x Ar The i-th inequality can be written as
(yy 2z) = D,, (A) xz 22 D (A), + + (Di.: 1) x; 0.
(19)
Proof by contradiction: we need to find x E gd which contradicts with Eq. 19 in the following three cases:
a) If D2, < 0, then, x; b) If Dz. > 1, then, 2; <
Da. (At + (D., - 1) x <0 I.
21

---

Under review as a conference paper at ICLR 2022
If0 < Dis 1+47, then 3a 0, s.t. D1,t 144,,ta" Letting 0, have
(A + () 10--11)a 14 = 1 Ai, + + A7, + < =
(Ai,)a))
Di, (4),at)) + (Di, -
1 Hence 1447, I D 1.
b) A x + Ai, i.e. 3j * i, s.t. A., > 0. The i-th inequality can be written as
[Cy æ); = - (Ai.z) + + zz 22
= 2A
(Di,i 1) 2; 2 0.
(20)
Proof by contradiction: we need to find x E Rd which contradicts with Eq. 20 in the following three cases:
a) Da, S O, then, x; > Dr. (A + (Dis - 1) < L.
b) If Da.i > 1, then, <0 50
Aii A Ar S = 1, where ts + i, Al
c) IfO < Dr, < 1, then, 0 A xy S
Hence Dú, = 1.
Hence D CBB* diag(k) (k), and thereby = holds.
H.2 LAYER 1
The proof Lem. 5.3 is similar to that of Lem. 4.2 because the two lemmas follow the same idea, which is to link objective functional minimization with always-hold inequalities. With Lem. 5.3, prove Thm. 5.1 as follows.
Proof. With Lem, 5.3, we only need to prove Væ E IR, (A*x)* Ax 2
+ Vi E
[d],
A.:
A. where 0 k; < This is equivalent what it is for single row, i.e. V
Rd
[a" x a a
ka", where 1.
:: The case where a" = 0 is clear. If a" is not zero vector and = ka", we have
a) a x 2 0, (a x
-a a =a kak x= (1- k) a 2 0.
b) a x < 0,
a x
+ Ta ka- x 2 O.
Hence = holds.
af 0, a must be a zero vector, otherwise let x = a, then -a T x 0 = If
not a zero vector, consider two cases below:
a) If a & ka" where k 2 0. Let ||""||
[
a", then is not zero vector, and
a x |a" (cos 0 1) 0, a Tx= || a
(a Tx) a <n =
cos 0) 0
where @ denotes the angle between and a' b) If a ka where & > then let = aa we have
T x = - k)) la 2 < _ 1.
a
x
Hence a = ka" where s < if a* is not zero, and thereby " " holds.
I QP CONVEXITY
The LPs in the main paper are 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.c. G and G is obtained by the convexity convex function summations.
22

---

Under review as a conference paper at ICLR 2022
Lemma 1.1. Suppose f(u) Tu - blß where is real matrix. Then f is convex W.E.
Lem. 1.1 is easily obtained since the Hessian (T) T is positive semidefinite. In the following, we demonstrate and justify the convexity the QPs of both layers by rewriting their single-sample objectives into the formulation of f and summing them without loss of convexity. Theorem I.2. QP: Eq. 4 and QP: Eq. 7 are convex optimization.
Proof. First of all, constraints of both QPs are trivially linear and convex. Thus, we only need to
justify the convexity of the two empirical objectives, GA and G (see Eq. 7 and 4 Consider the single-sample version GATE, namely gi N (A, Φ; x h) 1/2 1 Ax hl1² which, in the formulation of f, can be rewritten with
A
x
2
Σ
T
b h
(21)
A
which guarantees the convexity of gi NPE w.r.t. A and Φ by Lem. I.I 2 we have
For 92
(C, 2,,y)
[l + x
C
y
C
y
T
(22)
C
which guarantees the convexity of 92 NPE w.r.t. C' and & by Lem. I.1 Taking layer 1 as an example, by definition we have
Now consider the summation.
GN 1)
Σ VE(M)
gi NPE
(A, Φ (0) ()).
(23)
For each E 'n]. equivalently, we take o as a variable instead of (6) g NPE, but with only gf() E + deternining the value of gi NPF. In this sense, N is convex w.r.t. A and o for each E [n]. Thus. the sum GNPE is convex w.r.t. A and 4. Similarly, ČANE is convex w.r.t. C and E.
J 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 Thm. G. and Thm. 3.1] the solutions to our objective functionals are continuous sets. In addition, there theoretical intermediate results that also represented continuous sets, e.g. possible left-inverse matrices for 8 in the results for layer 2. Thus, to analyze the consistency of our learning algorithm, define distances between sets, that the convergence of sets can be well defined. Further point convergence results, i.c. layer 1/2 estimator strong consistency, are based on the set convergence we define.
Definition J.1 (deviation). Let C M. and B C M. be two non-empty sets from a metric space (M, d). The deviation of set A. from the set B, denoted by D(A, B), is
D(A, BB) sup d(a, B) sup inf d(a. b), aeı
(24)
a beB where sup and inf represent supremum and infimum, respectively.
Definition J.2 (Hausdorff distance). Let A C M and I C M be two non-empty sets from metric space (M, d). The Hausdorff distance between and B, denoted by (H B), DH (A, IB) m(x BB,, D)B
(25)
Remark. the following, we use the Frobenius norm to define the distance between matrices, i... d X, Y) pp
23

---

Under review as a conference paper at ICLR 2022
J.1. LAYER 2
In this subsection, we prove the strong consistency of the layer 2 estimator.
J.1.1 OBJECTIVE MINIMIZER SPACE ESTIMATOR
For simplicity of notation, we use Sn to denote layer 2 QP/LP solution space by random samples as a random set
S2 = (C Rdxm Cy x(1) 2 0, Vi [n]]
(26)
and S to denote the value space of C in Lem. 4.2 which minimizes layer 2 objective functional
S =C E Rdxm Cy - x 2 0, A Rd and its corresponding output y).
(27)
For further use, we name P. as the set of n sampled inputs which define S,, i.e. I,, fx(²) hel where each x()) is the same random variable in Eq. 26 By the definitions above, we describe the strong consistency of our QP/LP Lem.
Lemma J.1 (QP/LP strong consistency, layer 2). S") 0s 0 as n DC.
Proof. First we prove that DH (S.., 5*) & 0 xc. Recall Thm. G.1 Cy 0 only CB* = diag(k). We inherit the notation as defining D = CB". Theorem G. based on Lem. H.1 and we prove them by raising points that show contradiction, i.e. violate the inequality that holds in pointwise fashion:
a) In the proof of Lem. H.l
we use d points: (e( for E [d], to make
Ei Di,k
Ak. x
+ Ik
< 24. so that Da.5 (i + j) cannot positive; and another
d points: (A')-le(), to show Ei Di, A x < 0, so that Di, (i * j) cannot
be negative. For each et(1) we use here, since the violations follow strict inequalities, we know there exists a neighborhood of -e(+), N, N(-e(f)), such that V2 E N,
Ek=1 Di,k (Ai..
+ 2k
<
24. We can similarly find such neighborhood of each
-A that the strict inequality holds within the neighborhood respectively. We index them N441 to N2d-
b) In the proof of Thm. G.I we further construct d points: for each E [d]. we take point A vx < 0, where k * i, j. This counterexample shows Cy-zzj < O, and eliminates the possibility of < D, < 1 when A", is not a scale transformation. We can similarly find neighborhood of each point and index them as N2d+1 to Nza- Note that we omit some cases in the proof Thm. G.I] because the first 2d points sufficient use in those cases show contradiction.
A A
such that x; > 0 0A
In the sampling procedure, we sample at least one point each neighborhood N,, Thm. G. assures the solution we get Čn would lie in the true optimal set S*. The probability that the sampling procedure "omits" any of the neighborhoods
3d
P N = or P. n No = or or P 1Nad
Nad = Nad=0) <
Σ
N; = 9)
(28)
i= < 3d
min P(N,)) rE[3d]
Since the each neighborhood P(N.) SaEN p(x) 0.
P (P. @ or T N2 ... TP., NNs 0)
(29)
Here, take samples random variables for empirical analysis.
24

---

Under review as a conference paper at ICLR 2022
Here obtain Du (Sn, S*) & 0 as n - co. Now take the infinite sum over the both sides of
Eq. 28
Σ P
P
N = or PA n N2 = or or P., n Naa = 0)
RE/00]
3d
min P P(N,)
= 3d minue [3d] P(N.) 1 < +00.
iE [d
nE/oo]
By the Borel-Cantelli lemma (Borel 1909). DH S*) 85 0 as -0.
J.1.2 SCALE FACTOR ESTIMATOR
To avoid ambiguity, we use nar to denote the number of samples used in Alg. The samples pairs are {(x(0) yy Pa Without loss generality, the following discussion focuses on some fixed index
j E [d]. In Alg. 4. we plug in our estimator C, and use LR estimate ky given that x
Die(ma) Xj (1) ['ny""
Kn (Cn))
arg min Σ
|inny kx 902
(30)
k
2nst
VE(Mul
Eie(ne) (1)
We first give the strong consistency of layer 2 scale factor estimator for as Put - OC, as described in Lem. J.2
Lemma J.2 (scale factor estimator strong consistency, layer 2). Suppose A is a scale transformation w.r.f the j-th component, and kn,((C,,, ) the nay-sample estimator ki via LR: Eq. 30 given that
(8)
xj
0. Define sets
1 U Unyo = (C) C S. and U = 1 A+
(31)
Then lim lim DH Du(Ungnn U*) a. O.
200
Proof. Following our notation. Thm. G. and Thm. G.2jensure that if A is scale transformation the j-th component, for any C belonging to the true optimal set S", kng (C) E 1+4,, And the "iff" statement strengthens that U (C) C E S*) for any n&r Z+ Note that since S* c S we have U C Una.. We only need to prove D(Ung,n U*) n8, as n + cc.
V C, E S. and ES.
kng (nn(Cr)) - kny (C)
(c)-c Σ (1) (el))) (Cn- c) B ( (Aixl0) + +x(0
Eie(na) (x(10)²
xE(mxc
[//0|(((01) (C., - -c) B 2 (1 + (601111
Eie(nal (x,0))²
x
c/| |B 1l (IIA*) 1| + +1) xx
+1)/1x000
Eie(nal (x/00)²
Eie(nal [1x55)
|B 1l (|AA + ||x
C, - C clp.
Exe(nel (x)9)² 2
25

---

Under review as a conference paper at ICLR 2022
Then
sup inf C c,, CE3-
knd (Cn) - knn (C)
(32)
Eie[nal
(0) |B |F (1A 1| + 1))(x((1)
C -c
sup inf
(33)
Eielnel
(x()))
E8, Ce8*
which implics
Eie[mul
[
(3) |B
11
(IIA"lE
+
||x
D(Una U) S
D(S s*).
(34)
Σie(ne)
(8)
Take the n&t + so limit over both sides of Eq.
34 With the strong law of large numbery we have
E
B
1p
(IAA*)
11 + 1) ||xx1*11 112
lim D(Ungin U) 700
D D(S,, S*), w.p. 1.
(35)
(8)
E
Since St) S*) n as + oo, we have D(W U*)
B. as n - oo then nst - oc.
J.1.3 LAYER WEIGHTS ESTIMATOR
In Alg. we solve B via LR. Let ((0)
diag ' (k) C,y(()) Rd, where k is obtained through
Alg. 4 with input C,,. Assume we are using sample size of nw to do the LR. The optimization problem is
min B
y B2
(36)
VE [.,]
Now we present the strong consistency of layer 2 estimator, as described in Thm. J.3
Theorem J.3 (strong consistency, layer 2). Suppose Brd is the solution to Eq. 36 Then Ba. as n,, Rof fw Do.
ax B
Proof. Let denote vee B (flattening B into vector), then (2
(Z(1)
c Im- Here the
operation denotes the Kronecker product. Then we can define equivalent optimization problem
tE(mu) 1-0
( & Im B
min B
(37)
2nw
Take the derivatives of B3, obtain
- Σ [300] 2 Im (510),
(x(0)-
-[2(0))
T =
x Im 3
0
(38)
iE(m.)
Here assume that the Kolmogorov's 's strong law assumption moments commonly done in empirical analysis.
Sen & Singer
1994 is met as
26

---

Under review as a conference paper at ICLR 2022
Then the optimal solution Bn., of this optimization can be written in closed form:
Brn =
Σ
(2())
T
8
mm
(26))
T
Im
Σ
(2(0)
2 mm
yr(1)
iE(mul
sE(mul
I m
(2(1)
In
Σ
(+)
2 Im
xr(1)
iE(mml
iE(mal
(1) T
(1)
② Im
(0)
& Im yr(1)
iE [m]]
(m))
T
(1)
(2(0)
X Im
2
Im
Jr(()
(E(mu)
[E(m))]
0 n + co. Thus VE > 0, N. such that vn 2 N, d(C,,, S*)) S e w.p. 1, i.e. C E S" s.t. d(C,, C.) S c
We inherit the notation from the last two subsections. By Lem. J.1 di ((Cn, S²)
w.p. 1. Then by Lem. J.2. E K > 0, for E that is small enough, N such that V na 2 Nos we have (Č.) - kn (C.)) I Ke w.p.1. For simplicity, we omit the under-seript nsr of kng in the following discussion. In fact.
10000 2001 = k(C,) (et1)) Cny(()) 1 (e(1)) T
(.y
k(Cn)
k(C,) (c(i)) Cn -(Ck)) (eli)) [c] yrl))
On
((C,))((..)
k(C,)) (e()) T C,y(0 -xC,0-K(CC,))))))))))))))))) (e(1)) T Curll)
k(C,.)((..)
k(C,)) (e()) T Cny( (k(()))(((((p (el))) T Cry(i)) k(čn)
((C,)
(1+ A
(1/500///
Cr C.ll== +
-(CW))| - -k(C,))(((C))) I 11 (1AAl) 1|F + 1) ||x10) 1)
1 Ke (1+ Aj.))
(1+A;A) A;5)²
(11000/
+ dd (1 + 1) 10/1/x00
(39)
1 1- Ke (1+ A
Then
(1)
(2(1)
2(() (2(01) T
F
2
(0))
( (2())
+ z (5) (1)) (())
(2())
(2(0)
(2/00) 71I
(0)
20 (2())
(()
(2(0)
200
(4)
(2(1) (0)
+ 2
2())
)200) - -(250)
(2(0) T
2 (00)
2
+ 2
2
2
200
JE/d
27

---

Under review as a conference paper at ICLR 2022
follows that can prove
( (2())²
2 (2(0) T
is also bounded by OEE). With similar techniques we
Σ iE(mal
(()) (2()) (
Σ 20 (2(0) T
(2(1))
S(ee)
(40)
iE(mul
and
(2()) & Im z (0)
② Im
1 <E(E)
(41)
Denote [ie(mn) z (z
P and EiE(n.)
2
Q. Substitute z(4) with 2 in the above
expression we have P and Q. Hence,
@ -3
P & Im
(10 2 Im r((1) - - )
mm
(1Q 2 Im)
p 2 1m
( [ Lm| s1(1)) - [ Im
(Q Im] (1)
+
p 2 Im
( (1 km))(())
- [m]
(00 [m y((1)
P 3 Im
[1((@- - q s mm y00 F
+
p Im
PP 00
ml
Q @ Im (
In the first part, by triangle inequality,
p Im
S
p 3 Im
Im
+ P
x Im 1
(42)
F
So we only need prove
[
Im
[P x mm]
S O()) to claim
|m.. 3
O(e).
Denote P - P = AP. From Eq. 39
we know every entry of AP & Im can be bounded by O
By simple calculation we have
(P+AP) -1
- p- ---PP-----PPPP+00--: 0
(43)
Then we have
p- pr-
(44)
J.2 LAYER 1
In this subsection, we justify the strong consistency layer objective functional minimizer estimator in detail, i.e. the layer QP/LP solution space. We will omit the detailed proof of Aflg. 2 line 4 to 7 strong consistency since is similar to the proof of Lem. J.2, Additionally, we also omit the strong consistency of the æ + +x)** function estimator because it can be directly obtained by Lem. J.1 J.2 and the continuous mapping theorem.
We use a new optimization problem equivalent to the optimization of G1. Before that, we first define the cquivalence between two optimization problems follows.
Definition J.3. Let opt and opt2 be two optimization problems, with fi, /2 as the respective objective functions. Then opt1 and 2 are said to be equivalent if given feasible solution to op namely æ1, a feasible solution to opt 2 is uniquely corresponded, namely æ2, such that fi(21) f2(22), and vice versa.
The new optimization problem and its equivalence to the optimization of G1 is described in Lem. J.4 Gi (E. 6) is equivalent to
Lemma J.4. The optimization G
1
h) ||((A-b)**)
min f(A) = - Fx
(45)
2
28

---

Under review as a conference paper at ICLR 2022
Proof. To this, suppose A₁ is one optimal solution to Eq. 45 then we construct (2x (A1z - h)* so that G1 (1) = f(A1) and the optimality implies
min G1 (A.r) S min S(A). A.r
On the other hand, suppose (Az, r2) is an optimum of G1. Let r3(2)) = (h- A22)+ then vo E R and h be the corresponding hidden output, if [h Agælj 0, then (r)(2) + A2æ h1, 0, otherwise (x)) + A2 h = A22 h22 I [12 (x) + A2æ hl3 since h22 is nonnegative. So that we know that
G1 min = f(A2) ((A))
Gi
From the optimality, we further have
min Gi (A, A,
2 min ((A)
A
From the simple calculation above, we can see that one optimal solution to Eq. 45 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. 43 instead of G
(Amm)) - N00
min fn (A)
Σ sEini
-Axt)-
(46)
2n
Denote T == (kiag(k) A 0 < kj S 1,1 E [d]} as the true optimal solution set, and Tr as the optimal solution corresponding to the n-sample 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 J.S. Let Tw be the layer I QP/LP solution space by n' samples. Then there exists compact sei C determined by A", namely C(A*), ), s.t. T.. C C(AA)) w.p. 1 as XX.
Proof. VI E [d], let a" be the I-th row of A", and àj be the I-th row of An' We'd like first to prove that the set
TN = {at : a the 1-th row of A, where A Tw/)
(47)
is compact 1.
Suppose n' > d, and among the ni samples, we classify them into two folds. To avoid ambiguity, let
(()) be the points such that (a*) (6) >> 0, i E [q]: and wli) be the points such that (a") v(
j E [n q]. From the analysis of Thm. 5.1 we have (a*) ()) > à (1), Vi E [q] and à v))) <
Vj E [n 4). It follows that we can rewrite fV. as a polyhedron
TyJ = (a E Rd a ( S (a") Tu) T 1 < 0}
(48)
We are going to show the polyhedron TV is bounded by contradiction. If not bounded, then
Ed E Rd, d + O and à E Ty, such that AA > 0, ā + Xd E Ty. Then
(ä + (d) T (i) = à (1) + Ad (1) < <aa") (1) + Ad (0)) s s(a') -āa (49)
similarly,
(ā + Xd) ( a x() + Ad x0)) 50
(50)
From the definition, À can be arbitrarily big, then d ( < 0, E [4], and d (1)) S 0, Vj E [n-q]- 4
Since we know span(u ( (Otherwise if d (t) 0 for all E [q]. then either (u) * dd or d 0.) Under our assumption that, IN is not bounded, we know the following system (w.rt x) has a feasible solution w.p. 1
Rd w.p. 1, then there 3 some i such that d (t) 0, w.p. 1.
U V
x 0.
(3) < 0
29

---

Under review as a conference paper at ICLR 2022
where every row U and V (u(t)² and (v()) T respectively. By Farkas' lemma (Farkas 1902 the system
I- -UT x x- 2
is not feasible (w.p. 1). We claim that u((") lies in the conic hull of - -(0i's w.p. 1. So that the second system actually has a feasible solution and thus it raises the contradiction.
Denote the conic hull as
H LE :ER:
E Ms (-0(0) Σ
>3 0 for Vj [n Φ
jE(n-o)
Now suppose u(²') ) & H., by the supporting hyperplane theorem LLeeberger 1997). 3b E RR,, b + 0.
such that bJ (+)) TT t for vt E H. Then by definition,
--(1 (t: b dJ u () for for bj E [n q]
Denote the hyperplane J [t: b b ( then
P ((
$ H S (-v()
の E J. for Vj E [n al) P (-ob) (-ob)EEJ)*
"-9
Since we have this case geometric sequence, we know its infinite sum bounded. By Borel- Cantelli lemma (Borel 1909), we conclude that (x') H w.p. 1. Then system i feasible w.p. So that fVy is compact w.p. 1.
Now we prove that there exists a compact set C(A"), s.t. Tn C C(A") w.p. as n + co. Similarly, we focus on the analysis of one row. As discussed above, T2 is compact w.p. 1. Let W be the set of all ( sampled in estimating Tn', and V8, be the set of all eúو) sampled. Now for another set h Tx", similarly define sample point sets WT. and W "r. We claim that (u( W ( lies in the
conic hull of W,,.. Actually, this part of the proof is very similar to the way we prove ((") E H w.p. so will omit it here.
Va E Tw", let a(1) and (x2) be two different points in WT... Then T (A) + )2a((2) S (a") (A) + )2x(?)) for Aλ1 2 and A2 2 0. This simple calculation reveals a T u(()
(a*) T ()) for (i WT, (from the claim we made). This implies that Tw" C(A*) w.p. 1 as
+ too.
Lemma J.6. The minimizer space of [(A), iee. T = =kdaag(k) A contained in C(A*).
S kg S 1,j E [d], is
Lemma J.7. [(A) is finite valued and continuous on C(A").
Lem. J.6 and J.7 are easily obtained by the formulation of (see Eq. 45) and Lem. J.5
Lemma J.8 (uniform a.s. convergence). (A) a.t, ((A) + oo, uniformly in A E C(A').
Proof. Name single-sampl objective (αx A) (Ax h)
The uniform a.s. convergence
guaranteed by the uniform law of large numbers (Jennrich) 1969):
a) By Lem. J.5] C(A*) is a compact set.
b) g is continuous w.r.t. A by its formulation and measurable over æ at each E C(A*).
c) In fact,
g(x, A) = 1
2 (Ax h)*
< | 11 + x=12
$ (|| + ||A")))) ||=
Since E C(A") is in compact set,
g(x, A) <
sup AEC(A-)
|| + ||A
||0:12
(51)
30

---

Under review as a conference paper at ICLR 2022
Thus the dominating function exists
By Lem. J.5 J.6 J.7 and J.8. all of the conditions satisfied in (Shapiro et al. 2014 Thm. 5.3).
Thus, we have the strong consistency of layer objective optima estimator as described in Lem. J.9
Lemma J.9 (QP/LP strong consistency, layer 1). PI T*)
Similar to Lem. J.2 we have the strong consistency of the layer 1 scale factor estimator as described
in Lem. 1.10
Lemma J.10 (scale factor estimator strong consistency, layer 1). Let Knn (Cn) be the n sample estimator of ky via LR: Alg. line 5. given that hn)) > 0. Define sets
m (kng (A) A E Thc and V = [0, 1].
(52)
Then lim lim Du (V n'nn', V*) 0... 0.
Remark. In case ky = 0, suppose the algorithm finds solution over continuous distribution with [0, as support and the probability that finds a solution with scale factor is 0.
With Thm. 5.2 and the continuous mapping theorem, the strong consistency of layer estimation is guaranteed.
Theorem J.11 (strong consistency, layer 1). Suppose A.' is scaled by knig Then A. aie A as n', n'y
+ Do.
By Thm.
and
hmm 6.3 is guaranteed by the continuous mapping theorem.
Here, assume [[[[|[|]] < is commonly done in empirical analysis.
31


Reviews:
[{"review_id": "pDvJuqe63x", "reviewer": "Reviewer_1xAR", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is in general in good shape, I've not checked the details of the proof, but the main lines of arguments and numerical results in Section 7 look compelling. Related previous efforts are appropriately discussed. \n\nFrom a technical perspective, this paper contains some interesting ideas that are, I would say, inspired by previous efforts but adapted to the problem under study.\n\nSince one of the major contributions of this work is that the results do not rely on strong assumptions on the data distribution, it would be of interest to provide numerical experiments on more \"realistic\" data and tasks (instead of the toy model presented in Section 7).\n ", "summary_of_the_paper": "In this paper, the author describes an algorithm 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 the teacher parameters in the infinite data limit (Theorem 6.2 and 6.3). ", "summary_of_the_review": "The major novelty and contribution of this work lies in the study of the residual unit model, without relying on the assumption on the (specific) data distribution. The paper contains some interesting ideas that would be of interest in the study of more involved neural network models.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "_bxibaWuRxH", "reviewer": "Reviewer_T6Yf", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "STRENGHTS:\n\n(1) The problem is timely: residual networks have enjoyed great popularity in practical applications, but from a theoretical perspective, many basic questions about their optimization are still open. \n\n(2) The algorithm is novel and its computational complexity is polynomial in the number of samples, due to the QP (and, subsequently, LP) simplification. As for the dependence on the number of samples, the algorithm is consistent (the error vanishes, as the sample size grows), it significantly improves upon the vanilla linear regression and the numerical simulations also show a significant improvement over gradient descent.\n\n----------------------------------------------------------------\n\nWEAKNESSES:\n\n(1) The whole paper (starting from the vanilla linear regression to the non-parametric learning of the two layers) is based on the fact that $A^*$ has positive entries. This assumption is rather restrictive, not particularly practical, and it simplifies the problem significantly. As the paper appears to rely strongly on this assumption, it is not clear at all to me whether the methods discussed here can still work for a more general choice of $A^*$. \n\n(2) The sample complexity is only briefly discussed in Appendix D: here, the authors provide some rather heuristic arguments to justify that the sample complexity is polynomial (as opposed to vanilla linear regression whose sample complexity is exponential). I understand that, ultimately, in order to get a convergence speed result, one has to make assumptions on the data distribution. However, I guess that also the vanilla linear regression is a consistent algorithm, so proving just consistency appears to be a rather low bar. In order to fully understand the power of the QP/LP simplification presented here, the authors should make assumptions on the data distribution and show sample complexity results (instead of only giving experimental evidence). ", "summary_of_the_paper": "This paper considers the problem of learning the parameters of a two-layer ReLU network with a residual unit: given samples of the form $(x_i, y_i)$, with $y_i = B^*[(A^* x_i)^+ + x_i]$, the authors provide an algorithm that provably learns $A^*$ and $B^*$, as the sample size grows. It is crucially assumed that the entries of $A^*$ are non-negative and, by exploiting this fact, the learning problem is formulated via quadratic programming (QP): the authors show that there exist quadratic functionals whose minimisers can be used to deduce the ground-truth parameters. Furthermore, the QPs are re-written as linear programs (LPs), which are simpler to optimise and have the same solution space. Numerical results demonstrate the superiority of the proposed approach with respect to gradient descent methods.  ", "summary_of_the_review": "While I generally appreciate the problem tackled in this paper (provable optimization of two-layer ReLU residual networks) and the idea of re-writing the learning problem as a QP (or even LP), unfortunately the paper in its current status appears to be (slightly) below the acceptance bar, because of the weaknesses (1)-(2) mentioned above.\n\nOn the one hand, weakness (1) seems to be inherent to the approach pursued in the manuscript (but I would still appreciate if the authors could comment on it and suggest possible ways to overcome it). On the other hand, weakness (2) does not seem fundamental, but it would require additional work. I encourage the authors to pursue the direction of giving concrete sample complexity bounds since, in my opinion, it would add value to their paper. This would mean not only to show that the sample complexity is polynomial, but also to understand the degree of such a polynomial. It would also add value to provide simulation results that indicate a certain polynomial dependence of the algorithm on the number of samples (e.g., linear, quadratic, etc) -- even better if the simulation results confirmed the theoretical bounds.\n\nA couple of other comments are below:\n\n(a) The discussion on the computational complexity is deferred to Appendix B. I think that this part is actually important and I would suggest to discuss it directly in the main paper. This is especially important if the authors are able to obtain sample complexity bounds, since the computational complexity bounds would be complementary to them.\n\n(b) The input distribution chosen for the numerical experiments (mixture of N(-0.1, 1) and U(-0.9, 1.1)) seems a bit ad-hoc. Do the results change for different input distributions? (say only Gaussian, only uniform, and as a function of the mean of the Gaussian and of the uniform distributions)\n\n(c) Page 7. nonparamatric --> nonparametric ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "IN298xCpvid", "reviewer": "Reviewer_3xzu", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is mostly well written, however, there are issues requiring further discussions and explanations. See below for my detailed comments:\n\n* Can the authors comment on the ground truth parameter assumption? This does seem quite restrictive to me since it precludes any scaling/permutation invariance which is one of the main challenges in neural network training problems. Is this really necessary for the analysis if so where exactly?\n\n* The authors cited a series of papers training shallow neural networks via convex optimization, e.g., (Pilanci & Ergen, 2020), what are the advantages/disadvantages of the proposed method here compared to the ones in these papers? I think there should be a detailed discussion regarding this comparison?\n\n* In Appendix B, the authors provided a complexity analysis of the algorithm, however, I think they should also include a comparison with respect to the standard SGD applied the non-convex training problem and some baselines e.g., (Pilanci & Ergen, 2020) also proposed a convex approach with a polynomial complexity in the problem parameters.\n\n* After solving the nonparametric problem is there a way to recover a proper two-layer Residual network parameters? Does that require solving additional problems? If so can you provide some details, e.g., computational complexity?\n\n* Since the proposed method is nonparametric, how do you obtain the estimates during the inference time? Do you need to solve additional optimization problems?\n\n* I appreciate the experiments provided to verify the theory, however, there should have been some experiments on real benchmark datasets. Are there any specific reasons preventing such experiments, e.g., the scalability of the algorithm to larger datasets?  \n\n-Pilanci M, Ergen T. Neural networks are convex regularizers: Exact polynomial-time convex optimization formulations for two-layer networks. ICML 2020", "summary_of_the_paper": "\nThis paper considers the special case of two-layer ReLU residual units and introduces a nonparametric convex approach to optimize the training objective. The experiments also highlight the effectiveness of the proposed approach with respect to SGD applied to the original non-convex training objective. \n\n", "summary_of_the_review": "I think that the main contribution of this paper is incremental due to the following reasons. First of all, the model seems to be so simple that it even doesn't allow permutation and/or scaling invariance. Moreover, the paper lacks satisfactory comparative experimental analysis. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "BdWzaarlYon", "reviewer": "Reviewer_UrKE", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths: The proposed techniques are simple and lead to easy-to-implement algorithms. Also, it is interesting to know that an algorithm apart from the SGD works well for learning the parameters. The theoretical results are well-supported by experiments.\n\nWeakness: One concern I had is that the authors solve the problem of learning the layer 2 parameters by learning its inverse matrix. Computing matrix inverse may bring in numerical issues and ill-conditioning problem. I would have liked if the authors had done some experiments regarding this. Are there cases where learning the weight matrix itself instead of its inverse may lead to better performance? Another limitation of the paper is that there are no finite-sample guarantees, as opposed to asymptotic guarantees.", "summary_of_the_paper": "This paper gives an algorithm for learning two-layer neural networks with ReLU activation (realizable case). The network also consists of skip connections to avoid the problems of identifiability. As a warm up, the authors first give a simple algorithms based on linear regression, whenever enough samples could be observed with all-positive and all-negative entries. \n\nThey start with an algorithm for recovering the layer two parameters. For this step, they use the $\\ell_2$ loss and show that its minimizer is unique and matches with the ground truth parameters under certain condition. Subsequently, the authors replace the expectation in the objective with an average over the samples (based on the empirical risk minimization principle), which they could write as a convex quadratic program without making any parametric assumption. Finally, they show that the quadratic program can be equivalently written as a linear program, which lets them recover the parameters of the second layer (in fact the inverse matrix of this weight matrix).\n\nOnce layer 2 is learnt, the original problem reduces to that of learning the single layer non-linearity. They write the objective as a sum of weight estimator and a function estimator. They show that the minimizer of this loss is achieved when the estimated weight matrix is a diagonal matrix times the ground truth and the function measures the difference between the true nonlinear function and the scaled wright matrix. Again, they learn the function non-parametrically using a quadratic program, which they equivalently write as a linear program to get the scaled weight matrix. The scaling factors in the diagonal matrix can then be learnt using a linear regression.\n\nFinally, the authors conduct extensive experimentation to validate that their algorithms performs superior to the vanilla SGD-based algorithm. They also show that their algorithm, especially the QP algorithm is robust to noise.", "summary_of_the_review": "Understanding theoretical properties of neural networks is a major unsolved problem in learning theory. Considering that, this paper makes an important progress using simple algorithms and techniques. Although setting is somewhat simple, I felt the results should be encouraged. It would be interesting to extend this result to more complicated classes of neural networks.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: In this paper, the authors propose a non-parametric approach for learning a two-layer neural net. I agree with the authors and reviewers that this is a timely problem. However, the solution in this paper come short of achieving this goal. In particular, the assumtions are very strong and cannot be generalized (e.g., non-negativity). The authors also need to better spell out the sample complexity.
Decision: Reject