A Theoretical Analysis on Feature Learning in Neural Networks: Emergence from Inputs and Advantage over Fixed Features
Authors: Zhenmei Shi
Junyi Wei
Yingyu Liang
Venue: ICLR 2022 Poster (2022)
Keywords: neural networks
feature learning
provable advantage
theoretical analysis

Abstract: An important characteristic of neural networks is their ability to learn representations of the input data with effective features for prediction, which is believed to be a key factor to their superior empirical performance. To better understand the source and benefit of feature learning in neural networks, we consider learning problems motivated by practical data, where the labels are determined by a set of class relevant patterns and the inputs are generated from these along with some background patterns. We prove that neural networks trained by gradient descent can succeed on these problems. The success relies on the emergence and improvement of effective features, which are learned among exponentially many candidates efficiently by exploiting the data (in particular, the structure of the input distribution). In contrast, no linear models on data-independent features of polynomial sizes can learn to as good errors. Furthermore, if the specific input structure is removed, then no polynomial algorithm in the Statistical Query model can learn even weakly. These results provide theoretical evidence showing that feature learning in neural networks depends strongly on the input structure and leads to the superior performance. Our preliminary experimental results on synthetic and real data also provide positive support. 

Published as a conference paper at ICLR 2022
A THEORETICAL ANALYSIS ON FEATURE LEARNING IN NEURAL NETWORKS: EMERGENCE FROM INPUTS AND ADVANTAGE OVER FIXED FEATURES
Zhenmei Shi', Junyi Wei", Yingyu Liang University of Wisconsin-Madison iemeishiee wisc. edu, jwei 3ew.5550wwwc..c.. y yliang@es. wisc. edu
ABSTRACT
An important characteristic of neural networks is their ability learn represen- tations of the input data with effective features for prediction, which is believed to be a key factor to their superior empirical performance. To better understand the source and benefit of feature learning in neural networks, we consider learn- ing problems motivated by practical data, where the labels are determined by a set of class relevant patterns and the inputs generated from these along with some background patterns. We prove that neural networks trained by gradient descent can succeed these problems. The success relies on the emergence and improvement of effective features, which are learned among exponentially many candidates efficiently by exploiting the data (in particular, the structure of the input distribution). In contrast, no linear models on data-independent features of polynomial sizes can learn as good errors. Furthermore, if the specific input structure is removed, then no polynomial algorithm in the Statistical Query model can learn even weakly. These results provide theoretical evidence showing that fea- ture learning in neural networks depends strongly on the input structure and leads to the superior performance. Our preliminary experimental results on synthetic and real data also provide positive support.
INTRODUCTION
Various empirical studies have shown that important characteristic of neural networks is their feature learning ability, i.c., to learn a feature mapping for the inputs which allow accurate prediction (e.g...Zeilee & Fergus (2014) Girshick et al. (2014); Zhang et al. Manninng et al. (2020). This widely believed to be a key factor to their remarkable success in many applications, in particular, an advantage over traditional machine learning methods. To understand their success, it is then crucial to understand the source and benefit of feature learning in neural networks. Empirical observations show that networks can learn neurons that correspond to different semantic patterns in the inputs (e.g., eyes, bird shapes, tires, etc. in images (Zeiler & Fergus 2014 Girshick et al. (2014)) Moreover, recent progress (c.g., Caron et al. (2018); et al. (2020b): He al. (2020); Jing & Tian (2020) shows that one can even learn feature mapping using only unlabeled inputs and then learn an accurate predictor (usually linear function) on it using labeled data. This further demonstrates the feature learning ability of neural networks and that these input distributions contain important information for learning useful features. These empirical observations strongly suggest that the structure of the input distribution is crucial for feature learning and feature learning is crucial for the strong performance. However, it is largely unclear how practical training methods (gradient descent its variants) learn important patterns from the inputs and whether this is necessary for obtaining the superior performance, since the empirical studies do not exclude the possibility that some other training methods can achieve similar performance without feature learning or with feature learning that does not exploit the input structure. Rigorous theoretical investigations are thus needed for answering these fundamental questions: How can effective features emerge from inputs in the training dynamics of gradient descent? Is learning features from inputs necessary for the superior performance?
Equal contribution

---

Published as a conference paper at ICLR 2022
Compared to the abundant empirical evidence, the theoretical understanding still remains largely (J.ot
open. One line of work (c.g. Jacot et al. (2018): [ & Liang (2018); Du et al. (2019); [llle- -Zuu- et al.
(2019) Zou et al. (2020); Chizat et al. (2019) and many others) shows in certain regime, sufficienlly linear models, i.e., a linear function on the Neural Tangent Kernel (NTK). This falls into the traditional approach of linear models fixed features, which also includes random features (Rahimi & Recht (2008) and other kernel methods (Kamath et al. 2020). The kernel viewpoint thus does not explain feature learning in networks nor the advantage over fixed features. A recent line of work (e.g. Daniely & Malach (020); Bai & Lee (2019); Ghorbani ct al. (2020); : Yehudai Shamir (2019: Allen-Zhu Li [202) 2020a); Li et al. (2020); Malach
overparameterized networks are approximatell
et al. (202T) and others) shows examples where networks provably enjoy advantages over fixed
features, under different settings and assumptions. While providing insightful results separating the two approaches, most studies have not investigated if the input structure is crucial for feature learning and thus the advantage. Also, most studies have not analyzed how gradient descent can learn important input patterss effective features, or rely strong assumptions like models or data atypical in practice (e.g., special networks, Gaussian data, etc).
Towards more thorough understanding, we propose to analyze learning problems motivated by practical data, where the labels are determined by a set of class relevant patterns and the inputs are generated from these along with some background patterns. We use comparison for our study: (1) by comparing network learning approaches with fixed feature approaches on these problems, we analyze the emergence of effective features and demonstrate feature learning leads to the advantage over fixed features; (2) by comparing these problems to those with the input structure removed, we demonstrate that the input structure is crucial for feature learning and prediction performance.
More precisely, we obtain the following results. We first prove that two-layer networks trained by gradient descent can efficiently learn to small errors on these problems, and then prove that no linear models on fixed features of polynomial sizes can learn to as good errors. These two results thus establish the provable advantage of networks and implies that feature learning leads to this advantage. More importantly, our analysis reveals the dynamics of feature learning: the network first learns a rough approximation of the effective features, then improves them to get a set of good features, and finally learns an accurate classifier on these features. Notably, the improvement of the effective features in the second stage is needed for obtaining the provable advantage. The analysis also reveals the emergence and improvement of the effective features by exploiting the data, and in particular, they rely on the input structure. To formalize this, we further prove the third result: if the specific input structure is removed and replaced by uniform distribution, then no polynomial algorithm can even weakly learn in the Statistical Query (SQ) learning model, not to mention the advantage over fixed features. Since SQ learning includes essentially all known algorithms (in particular, mini-batch stochastic gradient descent used in practice), this implies that feature learning depends strongly on the input structure. Finally, we perform simulations on synthetic data to verify our results. We also perform experiments on real data and observe similar phenomena, which show that our analysis provides useful insights for the practical network learning.
Our analysis then provides theoretical support for the following principle: feature learning in neural networks depends strongly on the inpul structure and leads to the superior performance. In particular, our results make it explicit that learning features from the input structure is crucial for the superior performance. This suggests that cnput-distibuttio-fre analysis (c.g., traditional PAC lcarning) may not be able to explain the practical success, and advocates an emphasis of the input structure in the analysis. While these results are for our proposed problem setting and network learning in practice can be more complicated, the insights obtained match existing empirical observations and are supported by our experiments. The compelling evidence hopefully can attract more attention to further studies on modeling the input structure and analyzing feature learning.
2 RELATED WORK
This section provides an overview while more technical discussions be found in Appendix A
Neural Tangent Kernel (NTK) and Linearization of Neural Networks. One line of work (e.g. Jacot
et al.
22018; Li & Liang (2018), )): Matthews al. (2018); Lee et al. (2019); Novak et al. (2019):
Yang 2019%:
Du et al. (2019) 9 Allen- et al. (2019); ; Zou et al. (2020); Ji & Telgarsky| (2019) (0019) Cao
al.
2020
Geiger al. (2020); Chizat et al. (2019) and more) explains the success of sufficietlly
2

---

and then generate Published as a conference paper at ICLR 2022
over-paramenn perrparameterzee neural network by connecting them to linear methods like NTK. Though their approaches are different, they all base on the observation that when the network is sufficiently large, the weights stay close to the initialization during the training, and training is similar to solving kernel method problem. This is typically referred to as the NTK regime, or lazy training, or linearization. However, networks used in practice are usually not large enough to enter this regime, and the weights are frequently observed to traverse away from the initialization. Furthermore, in this regime, network learning is essentially the traditional approach of linear methods over fixed features, which cannot establish or explain feature learning and the advantage of network learning.
Ad Advantage of Neural Networks over Linear Models on Fixed Features. Since the superior network learning results via gradient descent are not well explained by the NTK view, recent line of work has turned to learning settings where neural networks provably have advantage over linear models on fixed features (e.g. Daniely & Malach (2020); Refinttt et al. (202T): Malach et al. (202T); Dou & Liang (2200) Bai Leel ) Ghorbani et al. (2020): : Allen-Zhu (209)) see the great summary in Malach et al. (2021)) While formally establishing the advantage, they have not thoroughly answered the two fundamental questions this work focuses on; in particular, most existing work has not studied whether the input structure is crucial factor for feature learning and thus the advantage, and/or has not considered how the features are learned in more practical training scenarios. For example, Ghoobani et al. (2020) show the advantage of networks in approximation power and Dou & Liang (2200) show their statistical advantage, but they do not consider the learning dynamics (i.e., how the training method obtains the good network). [Allen-Zhu & Li (219)) prove the advantage of the networks for PAC learning with labels given by a depth-2 2 ResNet and Allen-Zhu & Li (2020a) prove for Gaussian inputs with labels given by a multiple-layer network, while neither considers the influence of the input structure on feature learning or the advantage. Daniely & Malach (2020) prove the advantage of the networks for learning sparse parities on specific imput distributions that help gradient descent learn effective features for prediction, and Malach et al. (2021) consider similar learning problems but with specifically designed differentiable models, while our work analyzes data distributions and models closer to those in practice and also explicitly focuses
whether the input structure is needed for the learning. There are also other thcoretical studies on feature learning in networks (e.g. Yehudda & Ohad (2020); (Zhou et al. (2021): ): Diakonikolas et al. (2020); |Frei et al. (2020), which however do not directly relate feature learning to the input structure or the advantage of network learning.
3 PROBLEM SETUP
To motivate our setup, consider images with various kinds of patterns like lines and rectangles. Some patterns are relevant for the labels (e.g., rectangles for distinguishing indoor or outdoor images), while the others are not. If the image contains sufficient number of the former, then we are confident that the image belongs to certain class. Dictionary learning or sparse coding is a classic model of such data (e.g.. Olshausen & Field (997);; Vinje & Gallant (2000); [Blii et al. (2003)). We thus model the patterns as a dictionary, generate hidden vector indicating the presence of the patterns, and generate the input and label from this vector.
Let X = Rdd be the input space, and y = {+1} be the label space. Suppose M E RdxD D is an unknown dictionary with D columns that can be regarded patterns. For simplicity, assume A is orthonormal. Let ò E {0, 1)" be a hidden vector that indicates the presence of each pattern. Let A C [D] be a subset of size ls corresponding to the class relevant patterns. Then the input is generated by M. and the label can be any binary function on the number of class relevant patterns. More precisely, let P C [k.]. Given A and P, we first sample & from a distribution Dz. the input and the class label from き.
+1, if EieA &e E V= [1, otherwise.
t ~ Dār di
i = MO.
y y=
(I)
Learning with Input Structure. We allow quite general D with the following assumptions:
(A0) The class probabilities are balanced: Pr Pr|Eie 4 d. E P = 1/2.
(A1) The patterns in A are correlated with the labels with the same correlation: for any i E A,
7 = Elyo:] Ely/ [(} 0.
3

---

Published as a conference paper at ICLR 2022
(A2) Each pattern outside A is identically distributed and independent of all other patterns, Let
Po Priø, 1] and without loss of generality assume po 1/2.
Let P, denote the distribution on (ž,y) y) for some A, P. and Dz. Given parameters E (d, D, 7oPo, the family Fe of distributions include all P,
P,) with A S [D], P S [k), and
D3 satisfying the above assumptions. The labeling function includes some interesting special cases:
Example 1. Suppose P = {i E [k] : i k/2} for some threshold, i.e. we will set the label +1 when more than half of the relevant patterns are presented in the input.
Example 2. Suppose k is odd, and let P {i E [k] i is odd}, i.e., the labels are given by the parity function on أأرة E A). This is useful to prove our lower bounds via the properties of parities.
Appendix presents results for more general settings (e.g., incoherent dictionary, unbalanced classes, etc.). On the other hand, our problem setup does not include some important data models. In particular, one would like to model hierarchical representations often observed in practical data and believed to be important for deep learning. We leave such more general cases for future work.
Learning Without Input Structure. For comparison, we also consider learning problems without input structure. The data are generated as above but with different distributions Dz:
(A1') The patterns are uniform over 10,1)P: for any i E [D], Pr(o: = 1] = 1/2 independently.
Given parameters E. (d, D, D. the family Fe, of distributions without input structure is the set of all the distributions with A C [D), P C [ki and Dz satisfying the above assumptions.
3.1 NEURAL NETWORK LEARNING
Networks, We consider training a two-layer network via gradient descent on the data distribution:
2m
g(x)
Σ
aoo x) + b.)
(2)
where wi E T2d, bi, E RR and (2) = min(1, max(2, 0)) is the truncated rectified linear unit (ReLU) activation function. Let (w;, b,, a; )/m denote all the parameters, and let superscript (t)
denote the time step, c.g., (()) denote the network at time step with g(t) = [w, (0) ((0) a (2)
Loss Function. Similar to typical practice, we will normalize the data for learning: first compute
x == (a T ( where 2² E E (ū. B[ū,]) is the variance of the data, and then train on (z,y). This is equivalent to setting é (Ø- E(ol)/ā and generating and the normalized (Ir y). we will simply say (xx v) D.
M For (ū, y) from D
For the training, we consider the hinge-loss ((y, 9) max(1 - yÿ. 0). We will inject some noise to the neurons for the convenience of the analysis. (This be viewed using smoothed version of the activation ((2) = Ego(z- + {) similar to those in existing studies like Allen- & Li (2020b);
Malach et al. (2021) See Section [ for more explanations.) Formally, the loss 1S:
2m
Lp(g; os) = E( ((v, where g( {) = Σ
as a. 2) + by + Ed) 1=1
(3)
where { ~~ N NO o2)mmmmmmm)) are independent Gaussian noise. Let LD(g) denote the typical hinge-loss 2m
without noise. We also consider & regularization: R(g; Xa, Ano) = Σ2m >alas|2 + >w.llus113 with regularization coefficients Xas Aw.
Training Process. We first perform an unbiased initialization: for every i E [m], initialize (0)
(0, Taxa) with on 1/k,
6 (()) N NO, of) with or 11k22, a N/ o with o,
x2 /()kk), and then set w wn+s wa b (0) (0)
(0)
(0) (0)
a -a; We then do gradient updates:
((t)_ = g(t-1) - LD(g (1-1) _ (1)
+ (11) ( for = 1,2,..., T, (4)
for some choice of the hyperparameters (0)) Na Aw 0e and T.
(1) (t)
4

---

Published as a conference paper at ICLR 2022
4 MAIN RESULTS
Provable Guarantee for Neural Networks. The network learning has the following guarantee:
Theorem 1. For any o,e E (0,1), i
Z (log" (D/(61))), Po = S2(k2 /D), and max( /))2)) ,, D} S m S poly(D), then with properly set hyperparameters, for any D E Fs. with probability at least - 6, there exists & E [T] such that Pr|sigu(g( (x)) + yl S Lb(g S
The theorem shows that for a wide range the background pattern probability pa and the number of class relevant patterns k. the network trained by gradient descent can obtain small classification error. More importantly, the analysis shows the success comes from feature learning. In the early stages, the network learns and improves the neuron weights such that on the features (i.c., the neurons' outputs) there is an accurate classifier; afterwards learns such a classifier. The next section will provide a detailed discussion on the feature learning.
Lower Bound for Fixed Features. Empirical observations and Theorem do not exclude the possibility that some methods without feature learning can achieve similar performance. We thus prove a lower bound for the fixed feature approach, i.e., linear models on data-independent features.
Theorem 2. Suppose Vi is a cala-indepeedeed feature mapping of dimension N with bounded featuress i.., V X 1-1, 1jN. For B >> 0, the family of linear models on Y with bounded norm B is HB = (h(z) h(()) = (Z), w), 1|wll2 S B). If < le DDDD1 and k is odd, then there exists
D E Fs such that all E Hy have tinge-loss at least Po 1 .2NB 2
So using fixe features independent of the data cannot get loss nontrivially smaller than Po unless with exponentially large models. In contrast, viewing the neurons o ((w,, z) + b,) learned features, network learning can achieve any loss e E (0. 1) with models of polynomial sizes. We emphasize the lower bound is because the feature map V is independent of the data. Indeed, there exists small linear model on a small dimensional feature map allowing O loss for each data distribution in our problem set Fs (Lemma 5 However, this feature map V is different for different data distribution in Fg, i.e., depends on the data. On the other hand, the feature map Vi in the lower bound data- indepeeddden i.e., fixed before seeing the data. For V to work simultaneously for all distributions in F=, it needs to have exponential dimensions. Intuitively, it needs a large number of features, so that there are some features to approximate each V There are exponentially many data distributions in F=, and thus exponentially many data-dependent features V which requires to have an exponentially large dimension. Network learning updates the hidden neurons using the data and can learn move the features to the right positions approximate the ground-truth data-dependent features VV" so it does not need an exponentially large dimension feature map.
The theorem directly applies to linear models on fixed sniteeddmensionall feature maps, e.g., linear models on the input or random feature approaches (Rahimi & Recht 2008). It also implies lower bounds infinite dimensional feature maps (e.g., some kernels) that be approximated by feature maps of polynomial dimensions. For example, Claim 1 in Rahimi & Recht (2008) implies that a function f using shift-invariant kernels (e.g., RBF) can be approximated by model (V (ā), w) with the dimension N and weight norm B bounded by polynomials of the related parameters of f like its RKHS norm and the input dimension. Then our theorem implies some related parameter of needs to be exponential in k for ff to get nontrivial loss, formalized in Corollary 3 Kamath et al. (2020) has
more discussions on approximating kernels with finite dimensional maps.
Corollary For any function f using a shift- infft-invrriat kernel K with RKHS norm bounded by L, or
f(z) = Σ, K ((2,, for some data points and [|all2 S L. If3 < k < D/16 and k is odd, then there exists D E F= such that f has hinge-loss at least po (1- --poo(dd..))
Lyly(d.Lj
Lower Bound for Without Input Structure. Existing results do not exclude the possibility that some learning methods without exploiting the input structure can achieve strong performance. To show the necessity of the input structure, we consider learning Fz, with input structure removed. We obtain a lower bound for such learning problems in the classic Statistical Query (SQ) model (Kearns) 1998). In this model, the algorithm can only receive information about the data through statistical queries. A statistical query is specified by some coanomially-cooputtteo property predicate Q of labeled instances and a tolerance parameter [0. 1]. For query (Q, the algorithm receives
5

---

Published as a conference paper at ICLR 2022
response Pq -, + T|, where Po Pr(Q(zz, y) is true]. Notice that query can be simulated using the average of roughly 0(1/79) random data samples with high probability. The SQ model captures almost all common learning algorithms (exeept Gaussian elimination) including the commonly used mini- SGD, and thus is suitable for purpose.
Theorem 4. For any algorithm in the Statistical Query model that can learn over Fe, to classification 1/3
error less than 1/2 (2)s:
either the number of queries or 1//T must be at least (R)
The theorem shows that without the input structure, polynomial algorithms in the SQ model cannot get a classification error nontrivially smaller than random guessing. The comparison to the result for with input structure then shows that the input structure is crucial for network learning, particular, for achieving the advantage over fixed feature models.
PROOF SKETCHES
Here we provide the sketch of our analysis, focusing the key intuition and discussing some interesting implications. The complete proofs are included in Appendix D
5.1 PROVABLE GUARANTEES OF NEURAL NETWORKS
Overall Intuition. We first show that there is a two-layer network that can represent the target labeling function, whose neurons can be viewed as the "ground-truv truth"" features to be leamed. We then show that after the first gradient step, the hidden neurons of the trained network become close to the ground-truth: their weights contain large components along the class relevant patterns but small along the background patterns. We further show that in the second gradient step, these features get improved: the "signal-noise" ratio between the components for class relevant patterns and those for the background ones becomes larger, giving a set of good features. Finally, we show that the remaining steps learn accurate classifier on these features.
Existence of A Good Network. We show that there a two-layer network that can fit the labels.
Lemma 5. For any D E Fs, there exists a network g" (x) = Σ at ((w 2) + +b;) with y = g (x)
for any (x, y) D. Furthermore, the number of neurons = 3(k - 1), Jagl < 32k, 1/(32k) S
[b]] < 2, : = ā ΣSEA Mz/(Ak), (4k), and [w], x) + b7l S 1 for any E [r]] and (x, y) D.
In particular, the weights of the neurons are proportional to EjEa Mj. the sum of the class relevant patterns. We thus focus on analyzing how the network learns such neuron weights.
Feature Emergence in the First Gradient Step. The gradient for we (ignoring the noise) is:
ØLp(g) (a (y]])o( I (),,) b(zz) (x.)) {yzo' (wo, x) b.]} Ow:
where the last step is due to ((x) = 0 by the unbiased initialization. Let qj = (Mj, wi) denote the component along the direction of the pattern My. Then the component of the gradient on Mj is:
a M1 Ow: (L(L)))))) = -a,E o' x) + bill = -a,E yoio'
}
Σ PEID
degi + by
The key intuition is that with the randomness of de (and potentially that of the injected noise E), the random variable under o' is not significantly affected by a small subset of deqe. For example, for
class relevant patterns j E A, let UP := o' [eE[D] drese + by and __ = o' EigA deg + 6, We have T(D] R A and thus:
θ My, Ow, (oاه)) ) x E [Vo E (VoYI_A) = E (vo,) J E[ = 2 L
since y only depends on أ E A). Then the gradient has a nontrivial component along the pattern. Similarly, for background patterns j & A, the component of the gradient along M, is close to O.

---

Published as a conference paper at ICLR 2022
Lemma 6 (Informal). Assume poy k as in Theorem 1 and o'
(1) < 1/k, then with high probability
0 ( (2) -a (0) E}= M,T where for a small ex:
ifj E A. then - - & O(ee/ō) with B E [1(1),1)}
. ifj E A, then 17y1 S ((03..0).
By setting x 11(2 we have wn"h = 1 Ep M,T, R ,10aa (0)a 8y Ejes M,. For small Po. e.g., Po = Ó /D). these neurons can already allow accurate prediction. However, for such small Po. we cannot show a provable advantage of networks over fixed features. On the other hand, for larger Po meaning a significant number of background patterns in the input, the approximation eπror terms T2 (j & A) together can overwhelm the signals ТІ (j A) and lead to bad prediction, even though each term is small. Fortunately, we will show that the second gradient step can improve the weights by decreasing the ratio between (j & A) and TJ E A).
Feature Improvement in the Second Gradient Step.
We note that by setting a small v7(), after the update we still have (a E) < 1 for most (z, v) 'D and thus the gradient in the second step is:
a Lo (g: oe) ~ (a, LyrlEg [(w,, x) + b, + E.]3. Owi
We can then follow the intuition for the first step again. For j E A, the component (Mjs Jer, (D()))
roughly proportional to [ where T_ := o' EEea deee + b, 1x+6, [.) While Φege may not have large enough variance, the injected noise & makes sure that nontrivial amount of data activate the ncuron Then I- * 0, leading to a nontrivial component along My, similar to the first step. On the other hand, for j A, the approximation error term T, depends on how well o' Eeea,ey, deqe + b, + {,] approximates o' EEE(D) Φeqt + b, + & Since the qt's (the weight's component along M2) in the second step are small compared to those in the first step, we can then get a small error term T7. So the ratio between (j g A) over Ti E A) improves after the second step, giving better features allowing accurate prediction.
Classifier Learning Stage. Given the learned features, we are then ready to show the remaining gradient steps can learn accurate classifiers. Intuitively, with small hyperparameter values (r7())
1a2 10 = (!) < am. o (t) = 0 for < t S T = m4/3), the first layer's weights do not Tm373:
change too much and thus the learning is similar to convex learning using the learned features.
Formally, our proof uses the online convex optimization technique in Daniely & Malach (2020).
5.2 LOWER BOUNDS
The lower bounds are based on the following observation: our problem setup is general enough to include learning sparse parity functions. Consider an odd k. and let P {i E [k] is odd). Then y given by (z) ==
IIiEA Zj for 2, 2Φ, L, i.e., the parity function on 2) E A). Then known results for learning parity functions can be applied to prove lower bounds.
Lower Bound for Fixed Features. We show that F= contains learning problems that consist of a mixture of two distributions with weights pa and 1 Po respectively, where in the first distribution D(U), . is given by the uniform distribution over I and the label y is given by the parity function on A. On such (()) Daniely & Malach (020) shows that exponentially large models over fixed features is needed to get nontrivial loss. Intuitively, there are exponentially many labeling functions 1I. that are uncorrelated (i.e.. "orthogonal" to each other): E[[I,, [IAa] for any A and A2. Note that the best approximation of II by fixed set of features V 's is its projection on the linear span of the features. Then with polynomial size models. there always exists some II far from the linear span.
"Equivaeently, the network uses ((2) Beo + {). a Gaussian smoothed version of a, and the smoothing allows z slightly outside the activated region of a to generate gradient for the learning. Empirically it is not needed since typically sufficient data can activate the neurons. One potential reason is that the data have their own noise to achieve similar effect (a remote analog heing noisy gradients can help the optimization). Further analysis on such effect is left for future work.
7

---

Published as a conference paper at ICLR 2022
Remark. It is instructive to compare to network learning, which finds the effective weights Σ j. M, among the exponentially many candidates corresponding to different A's. This can be done efficiently by exploiting the data since the gradient is roughly proportional to E {yz} = EEE My. The network then learns data ceta-dependent features on which polynomial size linear models can achieve small loss.
Lower Bound for Learning without Input Structure. Clearly, Fe, contains the distributions ( described above. The lower bound then follows from classic SQ learning results (Blum et al.) 1994).
Remark. The SQ lower bound analysis does not apply to Fz, because in Fs the input distribution related the labeling function. This allows networks to learn with polynomial time/sample. While both the labeling function and the imput distribution affect the learning, few existing studies explicitly point out the importance of the input structure. We thus emphasize the input structure is crucial for networks to learn effective features and achieve superior performance.
EXPERIMENTS
Our experiments mainly focus feature learning and the effect of the input structure. We first perform simulations on our learning problems to (1) verify our main theorems on the benefit of feature learning and the effect of input structure; (2) verify our analysis of feature learning in networks. We then check if our insights carry over to real data: (3) whether similar feature learning is presented in real network/data; (4) whether damaging the input structure lowers the performance. The results consistent with our analysis and provide positive support for the theory. Below we present part of the results and include the complete experimental details and results in Appendix E
Verification of the Main Results. We generate data according to our problem setup, with d = 500, D = 100, k = 5, Po 1/2, randomly sampled A, and labels given by the parity function. We then train two-layer network with m = 300 following our learning process, and for comparison, we also use two fixed feature methods (the NTK and random feature methods based on the same network). Finally, we also use these three methods on the data distribution with the input structure removed (i.e., Fz, in Theorem 4
Simulation:
103
NETACIE WOS Structure
NTC. Ae
fandon
straccare
100
300
932
Dxp
Figure D shows that the results are consistent with results. Network learning gets high test accuracy while the two fixed feature methods get significantly lower accuracy. Furthermore, when the input struc- ture is removed, all three methods get test accuracy similar to random guessing.
Figure 1: Test accuracy on simulated data with or without input structure.
Simulation: Feature Learning in Networks. We compute the cosine similarities between the weights wt's 's and visualize them by Multidimensional Scaling. (Recall that our analysis is on the directions of the weights without considering their scaling, and thus is important choose cosine similarity rather than say the typical Euclidean distance.) Figure 2 shows that the results are as predicted by our analysis. After the first gradient step, some weights begin to cluster around the ground-trute Eje M, (or ΣjEa M, due to the a; in the gradient update which can be positive or negative). After the second step, the weights get improved and well-aligned with the ground-trute (with cosine similarities 0.99). Furthermore, if classifier is trained on the features after the first step, the test accuracy is about 52%; if the same is done after the second step, the test accuracy is about 100%. This demonstrates while some effective features emerge in the first step, they need be improved in the second step get accurate prediction.
Real Data: Feature Learning in Networks. We perform experiments on MNIST LeCunn et al. 1998 Deng 2012). CIFAR10 (Krizhevsky) 2012), and SVHN (Netzer et al. 2011). On MNIST, we train a two-layer network with m7 = 50 on the subset with labels 0/1 and visualize the neurons' weights as in the simulation. Figure 3 shows similar feature learning phenomenon: effective features emerge after a few steps and then get improved to form two clusters. Similar results are observed on other datasets. These suggest the insights obtained in our analysis are also applicable the real data.
8

---

Published as a conference paper at ICLR 2022
Figure 2: Visualization of the weights w; after initialization/one gradient step/two steps in network learning on the synthetic data. The red star denotes the ground-truth ΣJEA M,; the orange star is eeA My. The red/orange dots are the weights closest to the red/orange star, respectively.
4.5
4.5
Figure Visualization of the neurons' weights two-layer network trained on the subset of MNIST data with label 0/1. The weights gradually form two clusters.
11
(a)
(c)
Figure 4: Test accuracy different steps for equal mixture of Gaussian inputs with data: (a)
MNIST, (b) 10,AR10, (c) SVHN.
Real Data: The Effect of Input Structure. Since cannot directly manipulate the input distribution of real data, we perform controlled experiments by injecting different inputs. For labeled dataset L. and injected input 44 first train teacher network fitting L, then the teacher network to give labels on a mixture of inputs from L and U4 and finally train a student network on this new dataset M consisting of the mixed inputs and the teacher network's labels. Checking the student' performance on different parts of M and comparing to those by directly training the student on the original data C can reveal the impact of changing the input structure. We MNIST, CIFARIO, or SVHN as L, and use Gaussian or images in Tiny ImageNet (Le & Yang 2015) as U. The networks for MNIST are two-layer with m and those for CIFARION R0///NS ResNet- 18 convolutional neural networks (He et al. 2016).
Figure shows the results on an equal mixture of data and Gaussian. It presents the test accuracy of the student on the original data part, the Gaussian part, and the whole mixture. For example, on CIFAR1O, the network learns well over the CIFARIO part (with accuracy similar to directly training on the original data) but learns slower with worse accuracy the Gaussian part. Furthermore, the accuracy on the whole mixture lower than that of training on the original CIFAR1O. This shows that the input structure indeed has significant impact the learning. While MNIST+Gaussinn shows a less significant trend (possibly because the tasks are simpler), the other datasets show similar significant trends CIFAR 10+Gaas (the results using Tiny ImageNet in the appendix).

---

Published as a conference paper at ICLR 2022
7 ETHICS STATEMENT
Our paper is mostly theoretical in nature and thus we foresee no immediate negative ethical impact. We are of the opinion that our theoretical framework may lead to better understanding and inspire development of improved network learning methods, which may have positive impact in practice. In addition to the theoretical machine learning community, we perceive that our conceptual message that the input structure is crucial for the network learning's $ performance can be beneficial to engineering- inclined machine learning researchers.
8 REPRODUCIBILITY STATEMENT
For theoretical results in the Section a complete proof is provided in the Appendix D The theoretical results and complete proofs for a setting more general than that in the main text provided in the Appendix F For experiments in the Section[6] complete details and experimental results are provided the Appendix Section The source code with explanations and comments is provided in the supplementary material.
ACKNOWLEDGEMENT
The work is partially supported by Air Force Grant FA9550018-11 18-1-1666 the National Science Founda- tion (NSF) Grants 2008559-IIS and CCF-2046710.
REFERENCES
Zeyuan Allen-Zhu and Yuanzhi Li. What can resnet learn efficiently, going beyond kernels? In Advances in Neural Information Processing Systems, 2019.
Zeyuan Allen-Zhu and Yuanzhi Li. Backward feature correction: How deep learning performs deep learning, arXiv preprint arXiv:2001.04411 2020a.
Zeyuan Allen-Zhu and Yuanzhi Li. Feature purification: How adversarial training performs robust deep learning. arXiv preprint arXiv:2005.10190 2020b.
Zeyuan Allen Zhlu and Yuanzhi Li. Towards understanding ensemble, knowledge distillation and self-distillation in deep learning. arXiv preprint arXiv:20/2.098/6, 2020c.
Zeyuan Allen Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. In International Conference Machine Learning, 2019.
Yu Bai and Jason D Lee. Beyond linearization: On quadratic and higher-order approximation of wide neural networks. In International Conference on Learning Representations, 2019.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine-learnin practice and the classical biri-vari trade-off. Proceedings of the National Academy of Sciences, 116632):15849-15555 2019.
David M Blei, Andrew Y Ng, and Michael I Jordan. Latent dirichlet allocation. the Journal of machine Learning research, 3:993-1022. 2003.
Avrim Blum, Merrick Furst, Jeffrey Jackson, Michael Kearns, Yishay Mansour, and Steven Rudich. Weakly learning dnf and characterizing statistical query learning using fourier analysis. In Pro- ceedings of the twenty-sixth annual ACM symposium on Theory of computing, pp. 253-262, 1994.
Yuan Cao, Zhiying Fang, Yue Wu, Ding-Xuan Zhou, and Quanquan Gu. Towards understanding the spectral bias of deep learning. 2020.
Mathilde Caron, Piotr Bojanowski, Annand Joulin, and Matthijs Douze. Deep clustering for unsuper- vised learning of visual features. In European Conference Computer Vision, 2018.
10

---

Published as a conference paper at ICLR 2022
Minshuo Chen, Yu Bai, Jason D Lee, Tuo Zhao, Huan Wang, Caiming Xiong, and Richard Socher. Towards understanding hierarchical learning: Benefits of neural representations. arXiv preprint 1rXiv:2006.133366 2020a.
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In International Conference on Machine Learning, 2020b.
Lenaic Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable programming. In Advances in Neural Information Processing Systems, 2019.
Amit Daniely and Eran Malach. Learning parities with neural networks. Advances in Neural Information Processing Systems, 2020.
Li Deng. The mnist database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 29(6): 141-142, 2012.
Ilias Diakonikolas, Surbhi Goel, Sushrut Karmalkar, Adam R Klivans, and Mahdi Soltanolkotabi. Approximation schemes for relu regression. Conference on Learning Theory, 2020.
Xialiang Dou and Tengyuan Liang. Training neural networks as learning data-adaptive kernels: Prov- able representation and approximation benefits. Journal of the American Statistical Association, 2020.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In International Conference Machine Learning, 2019.
Cong Fang, Hanze Dong, and Tong Zhang. Over parameterized two-level neural networks can learn near optimal feature representations, 2019.
Cong Fang, Hanze Dong, and Tong Zhang. Mathematical models of overparameterized neural networks. Proceedings of the IEEE, (09(5)6633-703 2021.
Spencer Frei, Yuan Cao,, and Quanquan Gu. Agnostic learning of single neuron with gradient descent. In Advances in Neural Information Processing Systems, 2020.
Mario Geiger, Stefano Spigler, Arthur Jacot, and Matthieu Wyart. Disentangling feature and lazy training in deep neural networks. Journal of Statistical Mechanics: Theory and Experiment, 2020 (11):1 1133:1,331,, 2020.
Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. When do neural networks outperform kernel methods? In Advances in Neural Information Processing Systems, 2020.
Ross Girshick, Jeff Donahue, Trevor Darrell, and Jitendra Malik. Rich feature hierarchies for accurate object detection and semantic segmentation. In Computer Vision and Pattern Recognition, 2014.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Computer Vision and Pattern Recognition, 2016.
Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for unsupervised visual representation learning. In Computer Vision and Pattern Recognition, 2020.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in neural information processing systems, 2018.
Ziwei Ji and Matus Telgarsky. Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow relu networks. International Conference on Learning Representations, 2019.
Longlong Jing and Yingli Tian. Self-supervised visual feature learning with deep neural networks: A survey. JEEE Transactions on Pattern Analysis and Machine Intelligence, 2020.
Pritish Kamath, Omar Montasser, and Nathan Srebro. Approximate is good enough: Probabilistic variants of dimensional and margin complexity. In Conference Learning Theory, 2020.
11

---

Published as a conference paper at ICLR 2022
Michael Kearns. Efficient noise-tolerant learning from statistical queries. Journal of the ACM, 1998.
Frederic Koehler and Andrej Risteski. The comparative power of relu networks and polynomial kernels in the presence of sparse latent structure. In International Conference on Learning Representations, 2018.
Alex Krizhevsky. Learning multiple layers of features from tiny images. University of Toronto, 2012.
Ya Le and Xuan Yang. Tiny imagenet visual recognition challenge. CS 23/N, 2015.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient- learning applied to document recognition. Proceedings of the IEEE, 86(11))2278-2324, 1998.
Jaehoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve linear models under gradient descent. Advances in neural information processing systems, 2019.
Yuanzhi Li and Yingyu Liang. Learning overparameterized neural networks via stochastic gradient descent on structured data. Advances in Neural Information Processing Systems, 2018.
Yuanzhi Li, Colin Wei, and Tengyu Ma. Towards explaining the regularization effect of initial large learning rate in training neural networks. Advances in Neural Information Processing Systems, 2019.
Yuanzhi Li, Tengyu Ma, and Hongyang R Zhang. Learning over-parametrized two-layer neural networks beyond ntk. In Conference on Learning Theory, 2020.
Eran Malach, Pritish Kamath, Emmanuel Abbe, and Nathan Srebro. Quantifying the benefit of using differentiable learning over tangent kernels. arXiv preprint 1rXiv:2103.0/211 2021.
Christopher Manning, Kevin Clark, John Hewitt, Urvashi Khandelwal, and Omer Levy. Emergent linguistic structure in artificial neural networks trained by self-supervision. Proceedings of the National Academy of Sciences, 117(49):0046633005 2020.
Alexander G de G Matthews, Mark Rowland, Jiri Hron, Richard E Turner, and Zoubin Ghahramani. Gaussian process behaviour in wide deep neural networks, In International Conference Learning Representations, 2018.
Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and llya Sutskever. Deep double descent: Where bigger models and more data hurt. International Conference on Learning Representations, 2020.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y Ng. Reading digits in natural images with unsupervised feature learning. 2011.
Roman Novak, Lechao Xiao, Jaehoon Lee, Yasaman Bahri, Daniel A Abolafia, Jeffrey Pennington, and Jascha Sohl-Dickstein. Bayesian convolutional neural networks with many channels are gaussian processes. In International Conference on Learning Representations, 2019.
B. Olshausen and D. Field. Sparse coding with overcomplete basis set: A strategy employed by vI? Vision Research, 37:3311-3325, 1997.
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In Advances in Neural Information Processing Systems, 2008
Maria Refinetti, Sebastian Goldt, Florent Krzakala, and Lenka Zdeborová. Classifying high- dimensional gaussian mixtures: Where kernel methods fail and neural networks succeed, 2021.
William Vinje and Jack Gallant, Sparse coding and decorrelation in primary visual cortex during natural vision. Science, 287(5456) 2000.
Blake Woodworth, Suriya Gunasekar, Jason D Lee, Edward Moroshko, Pedro Savarese, Itay Golan, Daniel Soudry, and Nathan Srebro. Kernel and rich regimes in overpurametrized models. In Conference Learning Theory, 2020.
12

---

Published as a conference paper at ICLR 2022
Greg Yang. Scaling limits of wide neural networks with weight sharing: Gaussian process behavior, gradient independence, and neural tangent kernel derivation. arXiv preprint 1rXiv:1902.04700, 2019.
Gilad Yehudai and Shamir Ohad. Learning single neuron with gradient methods. In Conference on Learning Theory, 2020.
Gilad Yehudai and Ohad Shamir. On the power and limitations of random features for understanding neural networks. Advances Neural Information Processing Systems, 2019.
Matthew Zeiler and Rob Fergus. Visualizing and understanding convolutional networks. In European Conference on Computer Vision, 2014.
Chiyuan Zhang, Samy Bengio, and Yoram Singer. Are all layers created equal? arXiv preprini arXiv:1902.01996. 2019.
Mo Zhou, Rong Ge, and Chi Jin. A local convergence theory for mildly over-parameterized two-layer neural network. Conference on Learning Theory, 2021.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Gradient descent optimizes over- parameterized deep ReLU networks. Machine Learning, 109(3)4467-492, 2020. ISSN 1573-0565.
13

---

Published as a conference paper at ICLR 2022
Appendix
Section A presents more technical discussion on related work. Section provides proofs for our results in the main text. Section E provides the complete details and experimental results for our experiments.
provides the complete
Finally, Section provides the theoretical results and complete proofs a setting more general than that in the main text, allowing incoherent dictionaries, unbalanced classes, and Gaussian noise in the data.
CONTENTS
Introduction
Related Work
3
Problem Setup
3.1
Neural Network Learning
4
Main Results
Proof Sketches
Provable Guarantees of Neural Networks
6
Lower Bounds
6
Experiments
7
Ethics Statement
10
8
Reproducibility Statement
10
9
Acknowledgement
10
More Technical Discussion on Related Work
16
B
Complete Proofs for Provable Guarantees of Neural Networks
19
Existence of Good Network
19
B.2
2
Initialization]
20
B.3
Some Auxiliary Lemmas
21
B.4
Feature Emergence: First Gradient Step
................................
23
B.5
Feature Improvement: Second Gradient Step
................................
27
B.6
Classifier Learning Stage
................................
35
7
Proof of T'heore
37
Lower Bound for Linear Models on Fixed Feature Mappings
38
Lower Bound for Learning without Input Structure
39
14

---

Published as a conference paper at ICLR 2022
Complete Experimental Results
40
Simulation
40
E.1.1
Parity Labeling
40
1.2
Interval Labeling
42
E.2
More Simulation Result in Various Settings
43
E.2.1
Varying Input Data Dimension
E.2.2
Varying Class Imbalance Ratio
44
E.2.
Varying Sample Size
45
E.3
Experiments on More Data Generation Models
46
E.3.1
Hidden Representation Labeling
46
E.3.2
Two-layer Networks on Mixture of Gaussians
47
E,4
Real Data: Feature Learning Networks
47
E.4.1
CNNs on Binary Cifar10: Feature Learning in Networks
49
E,5
Real Data: The Effect of Input Structure
52
E.5.1
Experimental Methodology
52
E.5.2
Experimental Results
53
E.5.3
Larger Network on MNIST for Checking The Effect of Input Structure
55
E.5.4
Empirical Verilication of Our Method
55
Provable Guarantees for Neural Networks in A More General Setting
57
Problem Setup
57
F.1.1
Neural Network Learning
57
F2
Main Result
58
Notations
58
Existence of A Good Network
59
Inttializatinn
60
F6
Some Auxiliary Lemmas
61
Feature Emergence: First Gradient Step
62
F8
Feature Improvement: Second Gradient Step
68
Classifier Learning Stage and Main Theorem
15

---

Published as a conference paper at ICLR 2022
A MORE TECHNICAL DISCUSSION ON RELATED WORK
Advantage of Neural Networks over Linear Models on Fixed Features. recent line of work has turned to show learning settings where network learning provably has advantage over linear models on fixed features; see the nice summary in Malach et al. (202T). Here we highlight the results and focuses of the existing related studies and discuss the differences from ours.
Yehudai & Shamir (219)) shows that the random feature method fails to learn even a single ReLU neuron on Gaussian inputs unless its size is exponentially large in dimension. This points out the limitation of the random feature method (belonging to the fixed feature approach) but does not consider feature learning in networks.
Some studies show that a single ReLU neuron can be learnt by gradient descent (Yehudai & Ohad 2020; Diakonikolas et al. 2020 Frei et al. 2020). The analysis typically involves feature learning. However, their focus is different: they do not show the advantage over fixed feature methods and do not consider the effect of the input structures.
Zhou et al. (202I) shows that in a special teacher-studen setting, the student network will do exact local convergence in surprising way that all student neurons will converge to one of the teacher neurons. The work does not consider the effect of the input structure nor the advantage over fixed features.
Dou & Liang 2020) explains the advantage of network learning by constructing adaptive Reproducing Kernel Hilbert Space (RKHS) indexed by the training process of the neural network, and shows that adaptive RKHS benefits from a smaller function space containing the residue comparing to RKHS, The work shows the statistical advantage of networks over intteeindeennentt kernels, but does not consider the optimization for learning the network.
Ghorbani et al. (2020) considers data generated from hidden vector with two subsets of variables, each uniformly distributed in nigh-dimensional sphere (with different radius), while the label is determined by only the first subset of variables. shows the existence of good neural networks that can overcome the curse of dimensionality by representing the best low-dimensional hidden structure. However, it studies the approximation power of neural networks rather than the learning, i.e., it does not show how to learn the good network.
Fang et al, (2019) argues that in the infinite width limit, a two-layer neural network will learn a nearly optimal feature representation in the distribution sense, thanks to the convexity of the limit problem. is unclear how this result helps to understand the feature learning procedure for practical networks, which is usually non-convex process.
Chen et al. (2020a) considers a fixed, randomly initialized neural network as a representation function fed into another trainable network which is the quadratic Taylor model of a wide two-layer network. It shows that learning over the random representation can achieve improved sample complexities compared to learning over the raw data. However, the representation considered is not learned, which is different from our focus on feature learning.
Allen-Zhu & Li (020aa) considers Gaussian inputs with labels given by multiple-layer network with quadratic activations and skip connections (with the assumption of information gap on the weights), and studies training deep network with quadratic activation. It shows that the trained network can learn proper representations and obtain small eтrоrs while no polynomial fixed feature methods can. On the other hand, it does not focus on the influence of input structure on feature learning: note that its input distribution contains no information about the "ground-truth" features in the target network. also points out that the learned features get improved during training: higher-level layers will help lower-level layers to improve by backpropagating correction signals. Our analysis also shows feature improvement which however is by signals from the input distribution.
Allen-Zhu & Li 2019) considers PAC learning with labels given by depth-2 ResNet, and studies training an overparameterized depth-2 ResNet (using uniform inputs over Boolean hypercube as an example). It shows the trained network obtain small errors while no polynomial kernel methods can obtain as good errors. Similar to Allen- Zhu & Li (2020a). it does not focus on the influence of input structure feature learning the advantage of networks.
16

---

Published as a conference paper at ICLR 2022
Allen-Zhu & Li (2020c) studies how ensemble of deep learning models can improve test accuracy and how the ensemble can be distilled into a single model. It develops a theory which assumes the data has multi-view structure and shows that the ensemble of independently trained networks can provably improve test accuracy and the ensemble can also be provably distilled into a single model. The analysis also relies showing that the data structure can help the ensemble and the distillation. On the other hand, their focus is on ensembles and is quite different from ours: the analysis is on showing the multi-view input structure allows the ensembles of networks to improve over single ones and ensembles of fixed feature mappings do not have improvement. While our focus is on supervisedly learning one single network that outperforms the fixed feature approaches.
Daniely & Malach (2020) considers the task of learning sparse parities with two-layer networks, and the analysis suggests that the ability to learn the label-coreelatd features also seems to be critical towards the success of neural networks, although the authors did not explore much in this direction. Malach et al. (202T) also considers similar learning problems but with specifically designed models for the problems. The learning problems considered in Daniely & Malach (2020); Malach et al. (202) I) have input distributions that leak information about the target labeling function, which is similar to our setting, and their analysis also shows that the first gradient descent can learn a set of good features and later steps can learn an accurate classifier on top. Our work is inspired by their studies, while there are some important differences. First, their focuses
different from ours. Daniely & Malach (2020) focuses on showing neural networks can learn targets (i.e., k-parity functions) that are inherently non-linear. Our analysis generalizes to more general distributions, including practically motivated ones. Malach et al. (2021) focuses on strong separations between learning with gradient descent on differentiable models (including typical neural networks) and learning using the corresponding tangent kernels. The analysis is on specific differentiable models, while our work is on two-layer neural networks similar to practical ones. Second, our analysis relies on the feature improvement in the second gradient step. This is not an artifact of the analysis but comes from our problem setup. While in Daniely & Malach (2020) the data distribution allows some neurons to be sufficiently good after the first gradient step and needs no feature improvement, our setup is more general where the data distribution may not have a similar strong benign effect and thus needs feature improvement in the second gradient step.
Most related to our work is Daniely & Malach 2020). Therefore, we provide a detailed discussion to highlight the connections and differences.
1. Our problem setting is more general than that in Daniely & Malach (2220) To see this, let our dictionary be the identity matrix, the set P to be the odd numbers (i.e., the labeling function a sparse parity). Furthermore, let the distribution of the hidden representation be an equal mixture of the following two:
(a) Dj: Uniform distribution over the hypercube.
(b) D2: Irrelevant patterns أا(ة & A) have appearance probability po 1/2. And the distribution of relevant patterns 35 (j E A) is: all O's with probability 1/2, and all I's with probability 1/2.
Then our problem setting reduces to their setting (up to scaling/translation of の5 's). On the other hand, in general our setting allows for more choices for the labeling, the dictionary, and the distributions over ø.
2. Upper bound: Because of the more general setting, our upper bound proof requires technical novelty. Recall that in their work, the input distribution is essentially a mixture of D2 and D2 above. In Dz, the relevant patterns 6 A) have the specific structure of all O's or all I's with probability 1/2. This allows to show that neurons with weight satisfying EjEa W/ = will have good gradients: small components from irrelevant patterns (their Lemma 7) and large components from relevant patterns (their Lemma 8). However, in our setting, the relevant patterns do not have this specific structure, and thus their proof technique is not applicable (or can be applied only when we have an exponentially large number of hidden neurons so that some hit the good positions at random initialization). What we showed is that the gradient has some correlation with the good feature direction. So after the first gradient step, the neuron weights are not good yet but in better position for further improvement (in particular, their setting corresponds to Pa = 1/2 which means large noise in the weights after the first step; see discussion after our Lemma G in Section 5). Then
17

---

Published as a conference paper at ICLR 2022
the latter gradient steps are able to improve the weights to better "signal-to- toniull-t--iii--aatiii In summary, our proof does not rely on their specific input structure or an exponentially large number of hidden neurons for hitting some good positions. The key is that the good feature will emerge with the help of the input structure, and once in a better position, the neurons' weights can be improved to the desired quality.
3. Lower bound: On the other hand, lower bound is proved by reduction to the lower bound results in Danicly & Malach (2020). They have shown that D1 above can lead to large errors for fixed feature models of polynomial size. Our proof is essentially constructing a mixture of D2 and D2 with mixture weights po and (1 Po), and applying their lower bound for Dj. See our proof in Appendix C
4. Conceptually, our work belongs to the same line of research as Daniely & Malach 2020), to analyze how feature learning leads to the superior performance of networks. While their analysis also relies on feature learning from good gradients induced by input structure, their focus is more on separating network learning and fixed feature models and has not explicitly explored the impact of input structures (while agree that such an explicit study will not be difficult in their setting). More importantly, their input distribution is specific and atypical in practice, which allows specific type of feature learning (as explained in the above discussion on upper bounds). Our work thus considers a more general setting that is motivated by practical problems. Our results then bring theoretical insights closer for explaining the feature learning in practice and provide some positive evidence for the importance of analysis under proper models of the input distributions.
Sparse Coding and Subspace Data Models. To analyze neural networks' performance, various data models have been considered. A practical way model the underlying structure of data is by assuming that a set of hidden variables exists and the input data is a high dimensional projection of the hidden vector (possibly with noise). Along this line, the classic sparse coding model has been used in existing works for analyzing networks. Koehler & Risteski (2018) considers such a data distribution where the label given by a linear function on the hidden sparse vector, but studies the approximation power of networks and classic polynomial methods rather than the learning, AAlle-ZZhu Li (2220b considers similar data distributions, but studies the performance of networks under adversarial perturbations. Another type of related data models assumes that the label is determined by a subset of hidden variables. Ghorbani al. (2020) considers a hidden vector with two subsets of variables, each uniformly distributed in dime-dimensoonal sphere (with a different radius), while the label determined by only the first subset of variables. However, GGhorbnn et al.) (2020) studies the approximation power of neural networks rather than the learning. Compared to these studies, our work assumes the input is given by a dictionary multiplied with hidden vector (not necessarily sparse) while the label is determined by subset of the hidden vector, motivated by pattern recognition applications in practice. Furthermore, we focus on the learning ability of networks instead of approximation.
18

---

Published as a conference paper at ICLR 2022
B COMPLETE PROOFS FOR PROVABLE GUARANTEES OF NEURAL NETWORKS
We first make few remarks about the proof.
Remark. The analysis can be carried out for more gradient steps following similar intuition, while analyze two steps for simplicity.
Remark. Readers may notice that the network can be overparameterized. With sufficient overpa- rameterization and proper initialization and step sizes, network learning becomes approximately NTK. However, here our learning scheme allows going beyond this kernel regime: we use aggressive gradient updates (() = 1 (2)(())) in the first two steps, completely forgetting the old weights to learn effective features. Using proper initialization and aggressive updates early escape the kernel regime has been studied in existing work (c.g., Woodworth et al. (2020): Li ct al. (2019)). Our result thus adds another concrete example.
Notations. For vector and index set let vy denote the vector containing the entries of indexed by J, and ø- denote the vector containing the entries of e with indices outside T.
By initialization, w; (D) for i E [m]] are i.i.d. copies of the same random variable w(() NO0 o laxa:: similar for (0)) and ((t)_ Let qe == (w Mc). then (w(0), 2) = {6. g). Similarly, define q,f = (w) MMM. Let o == p1 po) denote the variance of de for l & A.
(f)
We also define the following sets to denote typical initialization. For a fixed E (0, 1), define
(d) = E R = (w, Mt), LDD k))
30
D k)
m
2
EEA
max lael S ow V logl Dm/8)
(5)
(6) = {a E R: |a| S oa v
(6)
(8) = (b E :: |b| < o. 2log(m/8)
B.1 EXISTENCE OF A GOOD NETWORK
we first show that there exists a network that can fit the data distribution.
Lemma 7, For some 8, a, E R with o, b 2 0, define a function 5z,a, : IR - IR. as
8 82,a((2) = a (2- - s + b) - -2a0, - s) + azr(z- - s b).
(8)
where 02(2) = max(2,0) is the ReLU activation function. Then
0
when when b < < 8,
b,
a(z 8) ab
(2))
(9)
a(z - 8) + ab
when S 5 + b,
when + b bb z.
That is, 0s,a,(22) linearly interpolates between (s b,0,, (s, ab), (s b, 0) when [s b, + bl. and is O elsewhere.
Proof of Lemma
This can be simply verified for the four cases of the value of z.
Lemma 8 (Restatement of Lemma 5). For any D E Fs. there exists a network g" (x) Σx a a ( 2) + 6,) with y = g" ( for any (x,z) y) ~ D. Furthermore, the number of neurons
3(k + 1), la < 32k, 1/(32k) < |6 < 1/2, w ā Ejea Mj/(Ak) and (w; x) + bil $
for any i [n] and (x, v) D.
19

---

Published as a conference paper at ICLR 2022
Proof of Lemma 5
Let 8 EEEA Mj and let μ EjEA Eldy].
We have
(w,z) 8 Σ
(M JM1 Ma) =
Σo,-
0j
Σ
μ.
(10)
jEn
jEA
JEΛ
Then by Lemma 7
gi(x)
Σ 6p 222112((11,,)
E
6p (--22212(((20x))
(11)
PEP
PEPOSPEK
Σ PEP
8 //2,1122(W,,2 x) + +1) - Σ
1,2,1/2( x)) + p))
(12)
PEP.OSSSk
8p.2.1/2
E
8p,2,1/2
Σ Ōj
(13)
PEP
JEA
PEP.OSPER
TEA
y
(14)
for any (x, v) D. Similarly,
95 (x) = Σ 8 -5p-4t1/AAa12((w....
E
(0-411/AA1/((11x20)
6p
(15)
PEP
PEPOSISK
Σ pEP
6 (w +1)
E
8 (441/AA1/2((0000)))) +1)
(16)
P.P.OSSSK
Σ PEP
6p+1/4,4.122
ΣØ
Σ
8p11/4,41/2
Σ の5
(17)
jEA
PEPROSSK
JEA
y
(18)
for any (x. v) ~ D. Note that the bias terms in gf and 92 have distance at least 1/4, then at least one of them satisfies that all its bias terms have absolute value 2 1/8. Pick that one and denote it as g(xr) = Σ a,or((w;, 2) + by). By the positive homogeneity of o,, we have
g(x)=
Σ 4ka,o, (iu,,o (4)k) (4k))
(19)
Since for any (x.v) ~ D. kw,, x)/ (4k)) + b.k()))) - 1, then
g(x) Σ 4kaio x)/ bz/(4k)
(20)
where is the truncated ReLU. Now we can set of 4k0;, wi = ws/(4k))bb b./(4k), to get our final g".
B.2 INITIALIZATION
We first show that with high probability, the initial weights are in typical positions.
Lemma 9, For any ò E (0, 1), with probubility least 1 8 2 exp (-O(D- k:) over w.)
LD k)/2 < Σ de < 30 - k2)2,
A
max|ad S T / (1)g)
With probability at least 1 8 over 6(0)
(0)) S σb 2logg(())
With probability at least 1 8 over (0)
(a) a. / 2 2og(1/8)
20

---

Published as a conference paper at ICLR 2022
Proof of Lemma
From 9 (O, o Laxa), we have:
With probability
2 11-6/2, 6/2, maxe lgel - v 20 log 5. and
For any subset S _ []. with probability 2 exp (-O(1S))), | E [| 3/5|e
2
Similar for ((0) and (0) The lemma then follows.
Lemma 10.
We have:
With probability 2 1 2m exp( over w; (0) 's for all E [2m], wi E (m.(d)
With probability 2 1 - over b, 's for all i [2m]], b (o(
With probability 2 1 - over (0) s, for all i [2m]. E (6).
Proof of Lemma
10 This follows from Lemma 9 by union bound.
The following lemma about the typical w. (0) will be useful for later analysis.
Lemma 11. Fix 8 E (0, 1). For any w ( I (6), we have
= =0(1 Ollog 3/2 (Dm/8))
Σ
(0) deg 2 -D)
(21)
( (DD-) kk)
Consequently, when p. = ( and k = 2(log 2 (Dm/8)).
= =0(1) 0(1)
Pr
deg 2 + (ww)
(0)
(22)
k1/4
Proof of Lemma 71 Note that for e & A, [E(ce] 0, E[p3] o3. and B[] O(oā/ā). Then
the statement follows from Berry-Esseen Theorem.
B.3 SOME AUXILIARY LEMMAS
The expression of the gradients will be used frequently.
Lemma 12.
Lo(g:og) -, (vTly((x; s [[s,, 2) + b, + e (0, 1))=)
(23)
Ow;
Hb Lp(g = -a, (vlly < 1] [[ x) + 6, E (0, 1)}},
(24)
Lo(g:og) -B. (vTl < 1| or ( + + +.)
(25)
da,
Proof of Lemma
12 follows from straightforward calculation.
We now show that small subset of the entries in o, q does not affect the probability distribution of (ó. q) much
Lemma 13. Suppose
NN o2), For any B 2 A and any b:
Pr (10, 9) + v b} á B.V
Pr
B, + b}
(26)
+ B.
KØB, gB)l
の² + 02 1-- 13///
0
(27)
(0" gellg-Bl1 1 + 2221/2
(a² + o² 1 12)3/2
21

---

Published as a conference paper at ICLR 2022
Similarly.
Pr {10.0) .) 2 20- - Pr ()) 2 b]
(28)
d-n
Kdb qn)l
11 n l
0
(29)
T 02119-B112
80 g- B
Proof of Lemma 13 Note that for l & A. [ddr] = 0, Blo
02. and B[|dv! = @(o3/0). Let
t = ((BB. 9B))l Then by the Berry- Esseen Theorem,
Pr (10 g) +ッ bj Pr ((0 B, n) + 2 b}
(30)
6-B
6-n
< Pr 160 B. + 1- b]}
(31)
2
0 +
(32)
( 12 + 02)1/2
02
The second statement follows from a similar argument.
We also have the following auxiliary lemma for later calculations. Lemma 14.
Ead {V) 0, B& fly/ 1,
(33)
(34)
Es, { } = 20²ā for $ A,
(35)
BØd {vb}} 8'
(36)
EΦg {luØ, | S z. for all j E [D].
(37)
Proof of Lemma 14
Eps {0} =
Σ Epi tuly = w) Prly- = v)
(38)
wEf+1]
1
Σ
Ess tuly m}
(39)
2
vE{+1}
= 0.
(40)
Eoa {vvl} = Σ
Esg flyl -y = 0) Pr(y = m)
(41)
=E(+1}
1
Σ
E Hlul by = fn
(42)
2
cE(+11}
= 1.
(43)
Es, [lo,1] = - pol
- Po) + |1 - polps 200
(44)
5) - E(ő,1
Ex [8o,} = =EOA
(45)
1
Ess {uō, - yE00;1
(46)
?
(47)
g.
flyo,1] Es floy1}
(48)
(49)
22

---

Published as a conference paper at ICLR 2022
B.4 FEATURE EMERGENCE: FIRST GRADIENT STEP
We will show that w.h.p. over the initialization, after the first gradient step, there are neurons that represent good features.
We begin with analyzing the gradients.
Lemma 15 (Full version of Lemma all i E [2m].
Fix 5 10,1) and suppose w E (o),),, 6,0h e ( for
Let
k *log 1/2 (Dm//)) + log 3/2 (Dmm/)))
c
o2 k)
Pf = D), k = (Dm/ and og < 1/k, then
0 Ow;
LD :0 (1) = -a;
(0) Σ MfT
D
(50)
where Tj satisfies:
i E A, then B1/0l S O(e//)), where 3 [((()), 1] and depends only on w 6 (
* i & A, then [Tyl S (())
Proof of Lemma [3] Consider one neuron index i and omit the subscript in the parameters. Since the unbiased initialization leads to g()) (z;g()) g()) = O, we have
0 :0 100 (
(51)
Ow
a 10) ( BOWN { (u (z:
(x: (1)) S B) (1 ,x) + 00) + (( E 1],r
(52)
aa Ba.) { [ xx) b(o) + (00) E (0.1)]z)
a
(53)
(0)
M, E (a 1 w)) + ( + (()) E (0, 1)}²,
(54)
==
First, consider j E A.
Tj = E (( {ull(w[o)) x) + (00) + + e (0, ()11))
(55)
= =ES yog Pr +6 000 g (0.1)]
(56)
Let
Ia Pr (0. + (0) +5(0 E (0.1))
(57)
0-1
12 Pr
+ ( E (0.1))
(58)
We have
|Becss (Ta - -1'1l
(59)
Pr [(0.0) + (00) + 2 0]
( +6.0 + + 2 20]
< Eg0
Pr
(60)
Φ-Λ
$-
+ Pr
(0).)) (0)) (00) + 2 1]
+ Pr
( + + (0)) 21
(61)
(0))((1)
23

---

Published as a conference paper at ICLR 2022
Then by Lemma 13
Pr (().0) + bl0) +0(0= 20 +50120-- - Pr (00 (0-A:9-A) 9-1) + +b0)) + ((1) 2 20] = O(c)).
(62)
Φ-
Note that Eeea Var(deqe) (D k)) (( and | 3. maxe lgel S
ow / log( Dm/o). Applying Bernstein's inequality for bounded distributions, we have:
Pr
2 = -xp-- = O(a)).
(63)
Φ-
We also have:
Pr [100) + 50) 2 1/4 = exp( = ( (0)
(64)
Therefore,
Pr (0.9) + b(0) + + 2 21] exp(-92(x)) = O(s)
(65)
(-4,g(1)
where the last step follows from the assumption on and k. A similar argument gives:
( + 60) + + > 1 exp(- = O
Pr ① (1
(66)
Then we have
T3 - E0 [
(67)
$ Edd {IuØyl EeW (Lo ]
(68)
(c.)) {1uo,}}
(69)
(cc//))
(70)
where the last step is from Lemma
14
Furthermore,
Es [VOrL{}
(71)
= Ess [vos} Egan [4]]
(72)
= Egs {md}}
Pr (-A.g())
(6 (0-A, + + ( (()) E (0.1))
(73)
By Lemma 11 the assumption on Po. and 63 we have
Pr Φ-1
(0 (Q-A.9-A) + (0) E (0. 1/2) 2 - (011)))(1/kk/))
(74)
(()) {0,11/2) 1/2 exp(-S((k)),
(75)
{(i)
This leads
B = Eeass [+]] = Pr (0-A. + (60) + ( e (0.1) 2 2(1).
(76)
(-1,(()
By Lemma 14 E.p {ydbr} = 7/8. Therefore,
s [T, 13-8//0/50(c/)) ((c/o))
(77)
Now, consider & A. Let B denote AU
T3 E (z.)) {uoyul (0.9) + (()) + + (0. (0.1]]
(78)
Epp Ba Ba g0 yy (0) + (()) =g {
(79)
-Bongg { (uns
(0. b + ( (0.1)
Pr 0-8
(80)
24

---

Published as a conference paper at ICLR 2022
Let
(0,g) (0)) +5(1) (0.1)]
Pr
(81)
9-n
(0 B, q- ( { (0.
13
Pr
(82)
Similar as above, have |Bqu) (Ib
11]1 s (tt)) by Lemma 13
Then by Lemma |4
T, - e0) {
(83)
- Esg {IvØ,) | (1o 1,)
(84)
< Te {bl Rs {l
(85)
- O((e) (()gö)
(86)
-(0GE0ō)
(87)
Furthermore,
E g() [00 Esa {A} Es, {or} Egor = 0.
(88)
Therefore,
[31 S 5((o
(89)
Lemma 16. Under the same assumptions as in Lemmal
15
LD Lg (0) (1)
00 -aa (T)
(90)
bb:
where [Tb] S ((e)).
Proof of Lemma 16 Consider neuron index i and omit the subscript in the parameters. Since the unbiased initialization leads to gx; = O, we have
0 ab
LD Lo :0 (1)
(91)
B yll (2; < 1 (w + ( + 5 E (0.1))
(92)
(a) BEN { (no ,x) + b + 500) E (0, (0,
(93)
Similar to the proof in Lemma
Pr (6, g) + ((0) + (2)) E (0, 1)] Pr A +000 + + E (0. = O(c.).
(94)
Then
+ Ti - Essien { Pr (60 1.0-A1,--A ( (() + (0)) E (0.111)
(95)
Φ-
= E0 (101
Pr 1r + ((0) + ())) E (0,1) Pr 1T( + 1 + e (0.
A_A
(96)
<O(cc) {1v1 <((e)).
(97)
(98)
Also,
Esi {u Pr ((0-1:9-A) + {())) (0.11
(99)
-Ros {4} )_ 160- 100) + g0) (0,
Pr
(100)
=0
(101)
Therefore, [Tb] < O(ee).
25

---

Published as a conference paper at ICLR 2022
Lemma 17. We have
Lo :o (1)) Taa
(102)
oa,
where [Tal S (maxx ) So if w 1 E (()), Tol S (0 (oog(Dm/b))
Proof of Lemma 17 Consider one neuron index i and omit the subscript in the parameters. Since the unbiased initialization leads to (x; g()) = O, we have
LD 00
(103)
da
(a, D { (x
(z: ()) s g) ((w))) + 6 +
(104)
--BAA.)DDEE { ( 2) + (l)) + {(1)}.
(105)
Let O'A be an independent copy of A. o' be the vector obtained by replacing the entries Φa with 6' and let x' M and its label is y'. Then
Eon { (WEE a.enn (w + 6:0) + +
Tal
(106)
2 Bon ((00 + b + +5 {("))y= - 1
1
(107)
-os { Es (. 12) x0) (0) + {("))| = -13
(108)
Bøn (R + t0 + +5())yy= =1
(109)
2
Eos +200) -
(110)
Since a is I-Lipschitz,
Tal -
E
10 Eo-A (1o10), .x)
(2.))((0)) - (n:(00),²') 11 = 1--==11 =-1
(111)
2
Bib {
((rol0) 10 =1 11 + Esy, { (ooom)) ( /0/ = -113)
S
E
E
(112)
2
Eg
Bp-
(u)10) xx)
(113)
E
(w)(1)
xz)
(114)
S
Ex (1o(0)
xx)2
(115)
< maxx lift
(0)
Em Σ
Σ
k
(116)
RE(D)
jeeitE
max 9 /E, (1 + 0(1))
(117)
O(max g.E))
(118)
L
With the bounds on the gradient, we now summarize the results for the weights after the first gradient step.
26

---

Published as a conference paper at ICLR 2022
Lemma 18. Set
X = (2, = = =0,0g = 1/k3/2
Fix E (0, 1) and suppose w: (0) E 9m ( (00 E (G((d) for all E [2m]. pp - S2(k2/D)
k Allgg (lm0)((Dm/)) (Dm/6)), then for all E [m]. wi (1)
-Et= Vi, Me satisfying
if E A, then qift (1)
1) ( ai 37/0| 50
(0)
[n where 3 E [0(11,, 1] and depends
only on w (0) D
if o A, then 9i, - 0 (f
(1)
and
6(1) = (0)
+ +n aa (0) To where [Tbl = 0
a a, + To where ITa = Ol 0(ou//lo((mmm/)))
(0)
Proof of Lemmal
18 This follows from Lemma 10 and Lemma 15
B.5 FEATURE IMPROVEMENT: SECOND GRADIENT STEP
We first show that with properly set ( for most x, (x; (2) ) < 1 and thus yg (x; (x:
ot
(2)
1.
Lemma 19. Fix (0,1) and suppose w0 (6), b(t) E Gb()), a; (ō( for all E [2m].
Po /2kk2 /D/ k Milog" ((log((Dm/)) (Dm/5)), oa S o² /²2((>h"),, 17 = -0 (Amoo
(2) and de S 1/k,
kmmo
then with probability 2 1 - exp(-O over v). we have
(2))
< 1. Furthermore,
for any E [2m], (w!") .2) (a () の) (()(4)//7) ((q())) &-a)
O (3000/19) /7), and
6 buti = (1) (0) lce).
(0) = in (
(0) 1 and a 00) -a - Then the gradient
(0)
Note that w for w; is the negation of that for Wmti, the gradient for b; is the negation of that for bmti, and the
Proof of Lemma 19
gradient for a, is the same as that for am+4. With probability 2 1 exxp O (max (amax(2p(())) (Dp --)=-,,.. k)), k})). )). among all j & A, we have that most 2p.(D k) + k of Φ5 are (1 po) /,, while the others are -Po/ö. 0. For data points with & satisfying this, we have:
(x: {
(119)
(1) a E Egcso (1) .x) xx) + bb" + +,5
(120)
( (q (1) .x)) + 610h + = + a o x) + (1)) + <le
(121)
a B (lo (1) xx) + (1") + ) + a E (eno (1) x))
,) + 6(00 + 5. {!?)))
(122)
a Eg xx) + (10) ((2)) + ( Egn (w 2) + (1) m + {(?))
(1)
(123)
27

---

Published as a conference paper at ICLR 2022
Then we have
m
9 11) x
(2)
- Σ
2n (, E g 2) ,2) + +
- |
(124)
@m+i
(1)
w w
(2)
25) + +10500) - 6
(125)
217 Ta (litef)) .x) + 1 + Egres (5(-)
(126)
(1)
- w
w
+ (0.00 - 0
+10050
+
0m+i
(127)
We have [Tal = O(o v log( (mm)))))) and
(wu{", ,x)
<0(1)a) ( (87/a cc/ā) ④
(128)
+ +0 10 (12p -k) a
(129)
1 =1(1/aa) () (K2/0" + cok//" + (I: PoD
(130)
S (1+ (1+po))/>) /7)
+
(131)
0,00
5 10:00 + an (
(132)
/log(m/0)
+ 1 (0) Ce
(133)
k2
E Egc0
(2!2)
3 0((
(134)
S la; + In) TTal S $|a;0) +
(0)
(135)
(1)
m (1)
i+ x)
= 2 (m0, (1) x) 01 + p/0)/7)-
(136)
1.00 m+i
(1)
1a a Tbl aa
(137)
Then we have
(
()(1)
v /og(m/88)
90 (x:0 (2))
0 (w
+
11)1
0)
+ oe
(2)
?
12
(138)
(7(1)
+ m((a,) (0) + "
ow v log(Dm/)))
(1) (0) C
(139)
7
0 mm om
log(Dm/0)
+ mlaa
11
+
11 (1) (0)
a
(140)
k
0 oo ow
(o
k + mmaa;
(0) (1))
+ +m ki
)
(141)
< 1.
(142)
Then yg (x;
of (2)) }
< 1. Finally, the statement on ((a())))A {-a)) (1)
follows from a similar
calculation on (w) ,
.>)
= (a (1) .))
We are now ready to analyze the gradients in the second gradient step.
Lemma 20. Fix d E 10 and suppose wi!) (0) E (8), b(0) E (b()), a.) E (6) for all i E [2m]]
Let 6x2 == O (" + exp(-O(k)). 1fk = (Dm)))) and k: = ODD), a. S
28

---

Published as a conference paper at ICLR 2022
82/(712), 7)) -000=0((m) -xmie. and (2)
o 11/10/2, then
0 Ow.
Lo(g :0 (20) = -a; Σ MjT
(1)
D
(143)
j=1
where Tj satisfies:
* i E A, then - S Olea/ō + 71 + aa (e)(0o where B
(Q))),, 1] and depends only on wi (0) (0))
i @ A, then [T}] S 1/ exp(- + O(ogezō)
Proof of Lemma
20
Consider one neuron index i and omit the subscript i in the parameters. By (x; > 11 S exp(-O(k)). Let ll, (> ((2)) s 1].
Lemma
19
Pr
Priyg
i LD 12 o
(2)
(144)
dw
- (aw)) Een ,x) + ((2) + g(2) E (0, 1]]z}
(145)
= aa) Σ
Mj Bly (1o x) + (( + ((2) E (0, 1)
(146)
T
Let T = R M. (UTKWi( x)) + b()) + g(2) E (0, {) We have
[Tj - Tiil
(147)
E ((. {o(L - (1)
xx) + + e E (0, 1)1,,}
(148)
0 B(..))-,EE0 11-16 Lal
(149)
1
exp(pxGr exp(-O(A))).
(150)
So it is sufficient to bound T₁1. For simplicity, we use as a shorthand for q; (1)
First, consider E A.
T3 ((aD))D)E())) (ull(wo()) 2) + b()) + g( e (0, (0,1)lo;}
(151)
-oa { fdd 2-
[(0.0) + bl)) + + e (0.11}
Pr
(152)
Let
(Ø, g) + +600 + (()) E (0. (0.1)].
La = Pr {(0)
(153)
(0-A, + ((2) - ((2) E (0. 1)]
F2 = Pr ((2)
(154)
By the property of the Gaussian ((2), that ((), O 11 (0) (e(r-te)))) (e( ), and that ((.
z²
(w .²)1 . = (2) /7) < (1/k)) and ( (.6-A.--1) = (1) /7) < ((1/k))) we have
[La - 1' <
Pr
(0, ④) + (()) + ( 0
Pr
(0-A + (1) + ( 2 20]
(155)
(
{(अ)
+ Pr ((a)
(6. g) + (()) + g(2) 2 1
+ Pr
(0-A.9-A - 10) ((2) 2 1]
(156)
((2)
77
1k(7 + Ec)
=0
+ exp( = O
(157)
02
(2)
29

---

Published as a conference paper at ICLR 2022
This leads to [2 - Ean {
(158)
< E {ooosl |Bg alla - }
(159)
BB {lvØj1}
(160)
1 (cca/))
(161)
where the last step is from Lemma
14
Furthermore,
-o [2
(162)
= E { Eo
(163)
Pr = Ep {wo
-
- E (0.
(164)
2-
By Lemma 19 have ((-_A: 50 Also, b1o1 s O(7 la 10)
lc.). By the
property of g())
Pr ((a)
(ő- (0- +00) + + =(0.1) -
Pr
(1:0) + g(²) E (0.1)]
(165)
{(0)
(0) S 0/ (1 (2)) )) + 0(7 (a; lec/08 2
(166)
On the other hand,
B
(10) +g(2) E (0. 22
Pr
Pr [<(2] E (-b60),11 b10)] g(2)
(167)
=1(1)
(168)
and B only depends on ((0) By Lemma 14
Es {uó,} = 7/3. Therefore,
T₃i B7/a| ((ca/0) + 0(7 ( + 011 (0) (00() 10/00///////000000000000000
(169)
Now, consider j E A. Let B denote AU (U].
yo (b + b + (0 E (0.1))
T₃ E (a.y)-DeeC
(170)
Eøn E ( (
I (0:9) + 600 + +g00 e
(0.1) e0.1))
}
(171)
Eon { yo,
(0.0) + + g00) E (0.1)]
Pr
(172)
Let
(0.g) q) + 6(1) + x E (0.1)). ((2)
4. = Pr
(173)
(0-B B. 9-BB)) B) 10) - ((2) E (0. 1)]
Tg = Pr
(174)
(()
Similar as above, we have 1/4
1, S 62. Then by Lemma 14
Tíi - Eggr a {uo H
(175)
< Epn {1v0, |B (To - 1313
(176)
< O(E [psl
(177)
< O(ec) x 0
(178)
=(ogre2d)
(179)
Furthermore,
Egg. (u05 Esgs {u} Ris (63)
R. a [7] 0.
(180)
Therefore,
[T51 S (00
(181)
30

---

Published as a conference paper at ICLR 2022
Lemma 21. Under the same assumptions as in Lemma 20
db :0 ( -a; Tb
(182)
where Tbl I exp(-x2(1)) + O(G2).
Proof of Lemma 21
Consider one neuron index i and omit the subscript i in the parameters. By
Lemma 19 Pr lyg
(x: (2)) > 1] cxp(-I((k)) Let I = [I s 1].
0
LD(g (1) 00
(2))
(183)
ab
aa ((aa) yI ((w (x) b(1) + +g(0) 10.
(184)
:=
Let Toi B( ge { x) + 6()) + (02) E (0, 1)]}. We have
Th - Toi
(185)
((. { (01--))[((0))) x) t + t0 {
(186)
(,y)) lxl
(187)
S expp( (xp(-S((k))
(188)
So it is sufficient to bound Tèi. For simplicity, q a shorthand for of
Toi = ((x.)))D.((1)
yI (0, q) + 600 +((0) E E0.11
(189)
Egg E
(,000) yI (0:0) + b()) + +((0) E (0. [0.1)]
(190)
(0.0)+b00 + 2 E (0.1)
EBs y/ Pr
(191)
Let
(0) 4) + ((2) +g(0) E (0.1))
Ib = Pr
(192)
((2)
Tg = Pr
(0-A. 9-1) (()) + ( e (0.
(193)
g(a)
Similar as in Lemma 20
we have II 1 s <a. Then by Lemma 14
Toi EdAPo- {81b}]
(194)
< Es, { I1]
(195)
((Ee2).
(196)
Furthermore,
Es [44}} = Eds {u} Eg_ !4] = 0.
(197)
Therefore, [Taal < (rea) and the statement follows.
Lemma 22, Under the same assumptions in Lemma
20
Lo(g (1), oo
(2) Ta
(198)
Da,
where Ta ((1(W)//)) + exp( (xp(-=((k))poly(Dm))
31

---

Published as a conference paper at ICLR 2022
Proof of Lemma
22
Consider one neuron index i and omit the subscript i in the parameters. By g
Lemma 19
Pr [yg
> 1] S exp(-I((k). Let I (x; s 1].
du LD )
(199)
- B(yy)N (( + 600) + +2))) 1
(200)
Let Tai == B(aY)D { (ulL (2) ((wll)) 22) + +00 + }. We have
To 10-1o -ail
(201)
BeaarD {u(1 - [(a + (()) + {(01)
(202)
B(o.)) exp(-S((k)).
|1 |1- Izl
(203)
(204)
So is sufficient to bound Tai For simplicity, we use q as shorthand for qi
(1)
Let o'A be an independent copy of eA, o' be the vector obtained by replacing in Φ the entries ΦA with H' and let x' Me' and its label is y'. Then
Iaal = Esa W a
(ww (1, x) + ((1) + + {
(205)
- Eda { ( x) + (()) + 50)) = 1}
(206)
Eps {Bs (1 x) 60)) +(()) -1}
(207)
$ E { (wo + b()) + g(2) by = 1}
(208)
Easa (100 xx) b(2) (/2))118/ = =-1}
(209)
2 Bonids {BOLA (w0 ,2) - (w 11 = 1. = =-1 =1
(210)
(Rau /WWRe 1/ = 1} + Eyy, (( ('' (6'==1))) -113)
< E
(211)
2
(RoOEt) x2)
I A
(212)
En (10 ,2/
(213)
(1) // )/7) + cxp(-S(((k) D x ( 1oo0
(214)
(//())))))) (t0/:)))exx(-((/// D D17 (1) (0) (7 +
(215)
(216)
where the fourth step follows from that is I-Lipschitz, the third to the last step from Lemma 19 and the second to the last step from Lemma 18
With the above lemmas about the gradients, we are now ready to show that at the end of the second
step, we get good set of features for accurate prediction.
Lemma 23. Ser
(1) = 720
km3 A = 0, (() (2 (1) 1/23/2
(217)
77 (2) = 1, (22 x2) = 12( o.
(2)
(2) = -/2
(218)
32

---

Published as a conference paper at ICLR 2022
Fix E (0,0(1/k²)) po = D(K2/D), k = a (log² Dm and m 2 max (S((K))) D). 87
then with probability at least over the initialization, there exist ā, such that g(2) == Σim ( (2) , satisfies Lp(Ø) = 0. Furthermore, |ãllo (m/k)), l|āll O(k2, /m), and || = ((k/m)). Finally, ||a = O (x.b)) [|u, 112 = O ((/kk) and 2 = 0(1/k3) for all [2m].
Proof of Lemma 23 By Lemma 5 there exists network (x) Σ 3(k+1)
E==l aj0((u7. bz)
satisfying gxx) for all (x.y) ~ D. Furthermore, |až] S 32k, 1/(2k)) I |b S 1/2, w
Esen Mş/(4k) and (w],,) + bg S for any i [n] and (z, D. Now we fix an and
show that with high probability there is neuron in g that can approximate the é-th neuron in g".
By Lemma 10 with probability 1 28 over (0) ss they all in (o); with probability 1 ó over a 's) they are all in (o(5); with probability 1 - 8 over b, ss they are all in Go()). Under these events, by Lemmal
(0)s
18 Lemma 20 and 21 for any neuron i [2m], we have
D
w;
d;
(1)
MfTJ,
(219)
/=1
(2)
b a
(1)
TT.
(220)
where
j E A, then [T, - 3///ol S ewt O(e2/ō + 11121/00 /o + 11 (ellaa//ee/((00))) (eo )) where
(2)
3 E [S(11,, 1] and depends only on wn!" (0 ((0)
j E A, then [Ty] S ew2 == exp(-O((k)) (0
[bb S + exp(= + O(Ez).
Given the initialization, with probability 22(1) over 1 we have
1b:01 E
2 sign(b (3)) sign(b;).
(221)
2 k22
Finally, since 4k|b Bo 1 <u = ((L/k2), with probability S2(E.) > 8 over a; (0)
E [ (kk0)/30)))))))))1 and depends only w (0) (0)
we have that for
4k 62 1y 16!0 (0) 822
π²
1 S cas
la (0)
0
(222)
1:2y
Let n. m/4 For the given value of m. by 219 the initialization, for each é there is different set of neurons Te S [m] with [Tel = n, and such that for each in E Te.
222p we have with probability 2 1 - 55 over
E
2
sign(b (b(bb sign(b?),
(0)
(223)
2
Ke
4k/66
(0)
S Cas
|0 (0) = 0
(224)
[02
K2ny
33

---

Published as a conference paper at ICLR 2022
We also have
0is By
(0)
(1)
(2)
x)
(M)s
(225)
JEA
(2)
1i BY
(M)+
+
BY
(Mj, x)
Lie
10) BY
(M) x)
(226)
12
jEA
jEA
DEA
(1)
0
(1)
T TU03
01
BY
$j
(1) (0)
B7
(227)
j=1
jEA
JEA
Oie
(1)
T3
BY
Σ
+
ai
(1)
Oi
(0)
By
03
(228)
jEN
jEA
We have (1)
dir
die
(0)
= 01 ow v /log(Dm/00g 00), and
D
87
By
TU
Φ3
S
Σ (T)
10s +
(229)
jEN
JEA
37A
S Okhewa /0) + 0 ((Dev2/0) =: Ep-
(230)
For the given values of parameters, we have
7
62 =
(231)
m
:
ky
Yfc
6w = 0
(232)
m²a
km2
c2 0
(233)
m²o
6 0
(234)
m²
k2y
7
7
c6 =
+
+
(235)
m2
2
m
Therefore,
0g By
(0)
(10
(2)
x)
(236)
JEA
1i
(1)
CΦ +
1ic
(1)
a
(0)
by
Ø2
(237)
( k2y
0
(1)
ro v Tog (m/0))
m222
YCc
7
(238)
12g
m²0
mō²
ky
+ 0
10 Vlog(Dm//))
(239)
02
< 0
(240)
m
We also have by Lemma 18 and 21
1 s 0 1,00 (0) Ice + 1a ( exxp(-0(A)) +62) )a)) so {)))))
10
(241)
m
34

---

Published as a conference paper at ICLR 2022
Now, construct such that aie
20, 622 16 2 mna
for each & and each It, and ā 0 elsewhere. Then
[(xr) - (x))
(242)
3(k-1)
3(++1)
Σ E= NET
Σ ãz o (1re (2) ,x) (x) +b2)
(22)
Σ
2a (1w2, x) + bs)
(243)
1=1
1)
2a² 1i a
3(k+1)
2a [b
(wr (2) x.) + ((()
{ x) + (0)
(1)
0
1bg
E=
me
t=1
Ell
bi |e
(244)
3(k+1)
1
2a 2a/1b;
((mr()) (2) .x) + (12))
20 [6
ais 37
(M x)) + (000
nh
10:00
t=1
ELL
JEA
(245)
3(k+1)
1
207
Cie
By
(M)5
1,00)
2a [6āl6
1b/c
(0)
(w) x)) + (1500
na
10:001
10:00
[b
feEle
jEA
(246)
2a |b;l < 3(k + 1) max
1
(247)
(0)
m
20 bb a
100
4ka
3(k + 1) max
(248)
1 4
82
2110 (0)
= 0 ( ba
+ h:EE Ea
(249)
m
< 1.
(250)
Here the second equation follows from that a is Saative--homogeneoon in [0, 1]. (w], x²) + b,6 S
1,
10 1/1b;| < 1. This guarantees yī(x) 2 1. Changing the scaling of ō leads to the statement.
Finally, the bounds on à follow from the above calculation. The bound on ||a!2) follows from ( ||2 and ||6 16(2)|12 follow from 219 220) and the bounds on af" and
Lemma 22 and those on llu!())
b5 in Lemma 18
B.6
CLASSIFIER LEARNING STAGE
Once we have a set of good features, we are now ready to prove that the later steps will learn an accurate classifier. The intuition is that the first layer's 's weights do not change much and the second layer's weights get updated till achieving good accuracy. particular, we will employ the online optimization technique from Daniely & Malach (020).
We begin by showing that the first layer's 's weights do not change too much.
Lemma 24. Assume the same conditions as in Lemma 23 Suppose for > 2, X(( = X = n((t) for some X, E (0, 1), and (!)) = 0. Then for any t >> 2 and i E [2m].
la." S +
(251)
km3
1 (t) -000=(2)p 1222 0
tmpoo
+
12t2 +0
t
(252)
k
km²
11(0 - ( 0
bmd
2 + 0
L. kmm
(253)
k22
35

---

Published as a conference paper at ICLR 2022
Proof of Lemma 24
First, we bound the size of |a; (1)
la [0]
(1 21/2)a (t-1) "1 8
"Ja; L.D T.D(a
(254)
(1 2112)a,t (t-1) - (D.DDD { (ullug s 1)o(((( 2)) + 0/5 1/-11)3
(255)
< | + 7
(256)
which leads
1 S 1t + 1a
(257)
where a;
(2) O 1
We are now to bound the change of w and 6,0)
(0)
[ (1) (2)
w 112
(258)
11 a
(1 2n1 (1-1)
(o(((t-1))) - m (2)
(2599
Ow.
<
(1 2n1))m{"
(260)
+ na;
(1- 1)
E ((AD)) (uTTugh s 1|][(( ((-1) x)) + b((-1) E (0. 10)1)) w (2)
(261)
< (11 2n)) (1-1) - (
(262)
+ 1) (|/55-1))
(1
E EINDDDD { { (t-l (x) S 1)]((to (1]( x)) + +ba (لعاا) = (0, 10.1))=311
(263)
< (1 (1-21/h) 21/2)
(t-1) - w
wi (2) || + 2nd2 1e.a)| 2
+ 17 1a ( (1-1))
(264)
leading to
|/0 (2) m
(2) 1l S 2012 | |3
+ + 11a
(265)
Note that ||u
(2)
112 = ((7/k).
16(0 b. 1 = (((-1)) 0
(t(g -b,²)) 6!2)
(266)
ab.
1 (t-1) {!2)
(267)
+ a; (t-1) E { (1llyn
z [][[[w x)
x) + +b6 (((-1) E 10.111
(268)
< 6/ 11 - (2
+ n a
(1-1)
(269)
leading to
1 1p² + 1
(270)
Note that
(6(0
=0(1/32).
Lemma 25. Assume the same conditions as in Lemma Then
24 Let g (x)) = -mm ā,o (1) xx)
[0,x)))))))))))) + b(0)..
16(0b (9) (x), Elgb (2) (z), S | (o
(((m)he) + r2² +0
km2 )) (271)
1
k
36

---

Published as a conference paper at ICLR 2022
Proof of Lemma
25
It follows from that
((98 00 (z). 3) Elga (z))
(272)
$ 19." (z) 9 (x))
(2)
(273)
s | ||ā||o
max o (
(1) 2)) + ((0) o((uu{) 2) + bl9))
(274)
E 22ml
(((ve)) - w 12 w)) + -1000) - 1,/0)
- | ||
E {mmm lo
max
(275)
and Lemma 24
B.7 PROOF OF THEOREM T
Based the above lemmas, following the same argument in the proof of Theorem 2 in Daniely & Malach (200)). we get our main theorem.
Theorem 26 (Full version of Theorem !|). Ser
0 720²
X! = 0, A 11(21 o. 1/k2,
(1)
(276)
km3
(2) 1, ((2 (2) 1/ 2, 0,00
(2) =1/k²
(277)
2
33
11 (1) = 17 = Tm (10 = (0 = dml 1/3 &
(1) = 0, for 2 <T
(278)
For any d E (0, if Po 22(k2 /D), k= (log²
max (S(kt)) D) S S poly(D), D), then we have for any D E Fs, with probability at least - 6, there exists t [T] such that
2
D
km2233
Pr(sign(g (x)) # v) S (g(g )
+
+
(279)
m²/3
m²
Consequently, for any e E 1). ifT = m and max ( (2212), D} S m S poly(D), then
Pr(sign (g) 1 (x:) * y) l)) Se
(280)
(*) 3) + x |a Note that the gradient update using (. is the same as the update in our learning algorithm. Then by Theorem 27 Lemma 23
Proof of Theorem 7 Consider ()) = ((
and Lemma 25
1
Σ
T
())
<
|
+
+alllavl@l allo
(T(
k )
T + +1²T2 + ( km2 (tme)) ))
(281)
T
2
1=3
|a
+
+ 110 (2)
1l + 7m
(282)
T
1 + bTT
49
<
0
+
k
+
+ 17m)
(283)
m²
mm
1.8
3T
m223 2/3
0
(284)
m2/3
m²
T
The statement follows from that 0-1 classification error is bounded by the hinge-loss.
Theorem 27 (Theorem 13 in Daniely & Malach (. Fix some n, and let fis..., ST be some sequence of convex functions. Fix some 0,, and assume we update Oet1 O, (((t.. Then for every 0* the following holds:
T
T
T 10.112 T
1 "
f((0.)
< T
f((0)) +
1010 +
[f(00))2 +
V (e..)l.
T
2n/
1
(285)
37

---

Published as a conference paper at ICLR 2022
C LOWER BOUND FOR LINEAR MODELS ON FIXED FEATURE MAPPINGS
Theorem 28 (Restatement of Theorem 2 Suppose V is data-independent feature mapping of dimension N with bounded features, ie.. V X [-1,1] Define for B O:
HB (h(a) h(z) (E), w) |wll2 S B}.
(286)
Then, i D/16 and is odd, then there exists D E F= such that all h E H. have hinge-loss at least Po (1 V2NB
Proof of Theorem 2 We first show that F= contains some distributions that are essentially sparse parity learning problems, and then we invoke the lower bound result from existing work for such problems.
Consider D defined as follows.
Let P = {i E [k] i is odd}. That is, if there are odd numbers of I's in ब... then = +1.
Let ( be distribution where all entries Φ are i.idd with Pr[ø, = Pr[Ø)
1/2. Let D be the distribution over (ž. y) induced by D and the above P.
Let D be distribution where all entries おZ for j g A are i..d. with Pr(ø; 1] Po/(2 2p,), while Pr(ğa (0, . 0)) Pr[sa (1, 1..., 1)] 1/2. Let D(1) be the distribution over (ū. y) induced by (()) and the above P.
Let D (() + (1 Po)D(1)
can be verified that such distributions are included in F= for ? O(1)
Assume for contradiction that for all D E Fz, there exists h" E HB such that h = (M, w*) loss smaller than Po (1 V2NB Then for all the distributions D defined above, we have 2*
V2NB 2
Dio (((h <
(287)
Now let D. be distribution 2 E [11, with i.i.d. entries zj and Pr(zj =-1] -1]= Pr(z, +1] = 1/2. Let fa(2) = =IIjeA 2z be the k-sparse parity functions. Let ('(2)) (M + 1).
Then we have h2(2) = (z), w*) such that for all A,
(p, fa)))) <1 VNN 2
(288)
This is contradictory to Theorem
The following theorem is implicit in the proof in Theorem 1 Daniely & Malach 2020).
Theorem 29, For subset A C [D] of size k. let the distribution D over (z. v) defined follows:
is uniform over P and y Il Zt. Fix some V [+1] - [-1, + +18,, and define:
H (= (V(2), w) ||ll| S B)-
le is odd and l S D/16, then there exists some A such that
V2NB
min ED, ((h(2)) 21 NER
2
We now prove the corollary.
38

---

Published as a conference paper at ICLR 2022
Corollary 30 (Restatement of Corollary 3 For any function f using shift-invariant kernel K
with RKHS norm bounded by L. or f(x) = E, a (2,, x) ffr some data points 2, and ||al|2 I L.
If 3
< 1. S D/16 and k is odd, then there exists D E F= such that f have hinge-loss at least
Po 2
)olv(d.L)
poly(d,T)
Proof. By Claim 1 in Rahimi & Recht (0008), for any O, there exists N poly(d, 1/v) Fourier features V that can approximate the shift-invarian kernel up to error v. For any c > 0. consider E; (V)),, ((x)))
ozV,,, ((r)).. Let w >; 04 (z;) and let = O(f). then (x), w/ approximates (() upto error and N poly(d, I., 1/e) and the norm of w bounded by B poly 1/e). The reasoning the same for f in the RKHS form, replacing sum with
integral. By Theorem 2
(v(x), w) has hinge-loss at least Pu(1 </NB Thus, the function f has loss least p0 solyid,E.1/e))
Choose poly(d,E)) we get the bound.
24
D LOWER BOUND FOR LEARNING WITHOUT INPUT STRUCTURE
First recall the Statistical Query model (Kearns) 1998). In this model, the learning algorithm can only receive information about the data through statistical queries. A statistical query is specified by some property predicate Q of labeled instances, and a tolerance parameter т E [0, 1]. When the algorithm asks a statistical query (Q, T), it receives a response Po E [PQ T, Po + r]. where Po Pr[Q((r, y) is true]. is also required be polynomially computable, i.e., for any (x, y) Q y) can be computed in polynomial time. Notice that statistical query can be simulated by empirical average of large random sample of data of size roughly O(1/7²) to assure the tolerance with high probability.
Blum al, (994)) introduces the notion of Statistical Query dimension, which is convenient for our purpose.
Definition 31 (Definition 2 in Blum et al. (1994)). For concept class C and distribution D, the statistical query dimension SQ- (Q-DIM(C,D D C1,..., Cd that are nearly pairwise uncorrelated: specifically, for all i + j.
is the largest number such that C contains concepts
Pr (c(()) = cz())) RDD
Pr (c(() & c, S 1/d8.
(289)
a~D
Theorem 32 (Theorem 12 in Blum al. 1994)). order learn C error less than 1/2 1/d in the Statistical Query model, where SQ-DiM(C, D), either the number of queries or 1/T must be at least 2 ///3
We now use the above tools to prove our lower bound.
Theorem 33 (Restatement of Theorem 4p. For any algorithm in the Statistical Query model that can either the number of queries or 1/T must be at least
learn over Fz, to error less than 2 (2)s.
(DD) 1/3 2 ((
Proof of Theorem Consider the following concept class and marginal distribution:
Let be the distribution over ā, given by = áb and oy are i.i.d. with Pr(ő, = 0]
Pr[Ø; = 1/2.
Let be the class functions y = -a( = 11,, -0a())=1__,)
σ5)) is odd] for different A S [D].
The distributions over (ā.y) induced by (C, D) are subset of Fs,- It is then sufficient to show that SQ-DIM(C, D) 2 (P).
It is easy to see that C' are essentially the sparse parity functions: if 2j 22z 1, then ( II Zj. This then implies that the ga 's are uncorrelated, SQ-DIM D) 2 (P)
39

---

Published as a conference paper at ICLR 2022
E COMPLETE EXPERIMENTAL RESULTS
Our experiments mainly focus feature learning and the effect of the input structure. We first perform simulations on our learning problems to (1) verify our main theorems on the benefit of feature learning and the effect of input structure (2) verify our analysis of feature learning in networks. We then check if our insights carry over to real data: (3) whether similar feature learning is presented in real network/data; (4) whether damaging the input structure lowers the performance. The results are consistent with our analysis and provide positive support for the theory.
The experiments were ran 5 times with different random seeds, and the average results (aceuracy) are reported. The standard deviations of the results are smaller than 0.5% and thus we do not present them for clarity. The hardware specifications are 4 Intel(R) Core(TM) i7-7700HQ CPU @ 2.80GHz, 16 GB RAM, and one NVIDIA GPU GTX1080.
E.1 SIMULATION
We train a two-layer network following our learning process. We use two fixed feature methods: the NTK (Fang al. 202T and random feature (RF) methods based on the same network and random initialization as the network learning. More precisely, in the NTK method, we randomly initialize the network and take its NTK and learn classifier on it. In the RF method, we freeze the first layer of the network, and train the second layer (on the random features given by the frozen neurons). The training step number is the same as that in network learning. We also test these three methods on the data distribution with input structure removed (i.c., Fs, in Theorem 4). For comparison, we take the representation of our two-layer network at step one/step two, named One Step/Two Step (fix the weight of the 1st layer after the first step/second step to train the weight of the second layer), and train the best classifiers on top of them.
Recall that our analysis is the directions of the weights without considering their scaling, and thus it is important to choose cosine similarity rather than the typical &g distance. Thus, we use metric Cos Similarity (ie(m]) cos(w;, Ww; İjen A Mj) in our tables, and Multidimensional Scaling to plot the weights distribution. The simulation dataset size is 50000. During training, the batch size is 1000, while for the first two steps we use the approximate full gradient (batch size is 50000). Each step is corresponding to weights update.
E.1.1 PARITY LABELING
Setting. We generate data according to the parity function data distributions used in our proof of the lower bound for fixed features (Theorem 2 with d = 500, D = 100, = 5, Po = 1/2, with a randomly sampled A. More precisely, we consider D defined follows.
Let P = {i [k] : is odd3. That is, if there are odd numbers of I's in ~.. then y = +1.
Let (()) be a distribution where all entries 36 are i.i.d. with Pr(ø,
Pr(Øj 1]
1/2. Let DD()) be the distribution over (#. y) induced by D( and the above P.
Let ((2)) be a distribution where all entries o, for j & A are i.dd with Pr 1] = P2 2p.), while Priø. (0, ......0)) 0)] = PrlőA = 1,, ......,)= 1/2. Let ((1) be the distribution over (ø. y) induced by ( and the above P.
Let DRix (() (1 Pt))(L))
The network and the training follow Section 3 where the network size is m = 300 and the training time T = 600 steps.
Verification of the Main Results. Figure 5 shows that the results are consistent with our analysis. Network learning gets high test accuracy while the two fixed feature methods get significantly lower accuracy. Furthermore, when the input structure is removed, all three methods get test accuracy similar random guessing.
40

---

Published as a conference paper at ICLR 2022
test accuroty
80-
Network, structure
Random Feature, ay structure
Netwerkk ctructure
NTK,
Handem reature, wi structure
200
400
step
Figure 5: Test accuracy on simulated data under parity labeling with or without input structure.
Maril
-33 05
Figure 6: Visualization of the weights w/ after initialization/one gradient step/two gradient steps in network learning under parity labeling. The red star denotes the ground-truth Σje My; the orange star is Ejea My. The red dots are the weights closest the red star after two steps; the orange ones are for the orange star.
Model
Network
NTK
RF
One Step
Two Step
Network w/o structure
Train Acc (%)
100.0
84.0
74.7
51.3
100.0
100.0
Test Acc (%)
100.0
86.4
76.0
52.2
100.0
52.0
Cos Similarity
0.997
NA
0.114
0.848
0.997
0.253
Table 1: Parity labeling results in six methods. The cosine similarity is computed between the ground-truth ΣJEA Mj and the closest neuron weight.
Feature Learning in Networks. Figure shows that the results are predicted by our analysis. After the first gradient step, some weights begin to cluster around the ground-truth Ejes M, (or
- EEeA My due to we have a; in the gradient update which can be positive or negative). After the second step the weights get improved and well-aligned with the ground-truth (with cosine similarity 0.99).
Table M shows the results for different methods. Recall that the Cos Similarity metric is maxfie [mm]] cos( w., ΣjeA M,), which reports the cosine value of the closest one. One Step refers to the method where we take the neurons after one gradient step, freeze their weights, and train classifier on top: similar for Two Step. One Step gets test accuracy about 52%, while Two Step gets accuracy about 100%. This demonstrates that while some effective feature emerge in the first step, they need to be improved in the second step for accurate prediction. NTK, random feature, One Step all failed, while Network and Two Step can achieve 100% test accuracy. Network w/o structure refers to training the network on data without the input structure. overfits the training dataset with 52% test accuracy.
41

---

Published as a conference paper at ICLR 2022
E.1.2 INTERVAL LABELING
100
L25t occuracy
Network, My stricture
NTK, structure
Random Feature,
Networkk, structure
NTK, wie structure
Figure 7: Test accuracy simulated data under interval labeling with without input structure.
Mep
50-
-3
-3
-18
Figure 8: Visualization of the weights wy's after initialization/one gradient step/two gradient steps in network learning under interval labeling. The red star denotes the ground-truth Σjea Mj; the orange star is jEA Mj. The red dots are the weights closest to the red star after two steps; the orange ones are for the orange star.
Model
Network
NTK
RF
One Step
Two Step
Network w/o structure
Train Acc (%)
100.0
100.0
76.4
44.1
100.0
100.0
Test Ace (%)
100.0
100.0
73.2
41.0
100.0
100.0
Cos Similarity
1.00
NA
0.153
0.901
0.994
0.965
Table 2: Interval labeling results in six methods.
Setting. We also tried interval function, where y if Σie Φ is in the range [41, (2) with 4 = 20
and to 30, otherwise y -1 We use d 500, D 100, 30. The J;'s are independent, and Pr(Ø 1] 2/3 for any i A, and Pr(ø: = 1] = 1/2 otherwise. When the input structure is removed, we set Pr(ø. = 1] = 1/2 for all i's.
The network and training again follows Section 3 with network size T= 200 steps.
100 and the training time
Verification of the Main Results. Figure 7 shows that network learning learns the fastest, NTK learns slower but reaches similar test accuracy, while random feature can only reach a decent but lower accuracy. This is because for such simpler labeling functions, fixed feature methods still achieve good performance (note that the lower bound does not hold for such case), while the performance depends what fixed features use.
Furthermore, when the input structure is removed, the methods still get similar (or only slightly worse) performance with input structure. This shows that when the labeling function is simple, the
42

---

Published as a conference paper at ICLR 2022
help of the input structure for learning may not be needed. In the experiments real data, will show that when the input structure is changed, it indeed leads to lower performance which suggests that the labeling function in practice is typically more complicated than this interval labeling setting, and the help of the input structure is significant for learning.
Feature Learning in Networks. Figure& shows the phenomenon of feature learning similar that in the parity labeling setting. Table 2 shows the test accuracy of six different methods. Random feature and One Step failed, while Network, NTK and Two Step succeed showing that interval labeling setting is simpler case than parity labeling setting.
E.2 MORE SIMULATION RESULT IN VARIOUS SETTINGS
We show the robustness of our simulation results by studying the learning behaviors variety of settings including different sample size, input data dimension and class imbalance. We reuse the same setting as the simulation in the main text (details in E...II. vary different parameters, and report the accuracy, the cosine similarities between the learned weights, and the visualization of the neuron weights.
E.2.1 VARYING INPUT DATA DIMENSION
In the simulation experiments in the main text, the input data dimension d is 500. Here change the input data dimension to 100 and 2000. All other configurations follow E.I.1
Verification of the Main Results. Figure 9 shows that our claim is robust under different input data dimensions. The performance of network learning is superior over NTK and random feature approaches on inputs with structure, and on inputs without structure, all three methods fail.
212
Retwork, SESUCTE
RTK, W mriziue
K.K W STUCTUP
Pasting
70
50-
300
200
300
400
505
500
200
300
400
502
stcp
(a) 100
(b) d 2000
Figure 9: Test accuracy simulated data under different input data dimensions.
d 100
Network
NTK
RF
One Step
Two Step
Network w/o structure
Train Acc
100.0
83.1
78.9
53.0
100.0
100.0
Test Acc
100.0
81.5
78.3
51.1
100.0
51.0
Cos Similarity
1.000
NA
0.354
0.967
1.000
0.331
d = 2000
Network
NTK
RF
One Step
Two Step
Network w/o structure
Train Acc
100.0
75.6
80.0
50.22
100.0
100.0
Test Ace
100.0
75.4
77.0
50.01
100.0
52.5
Cos Similarity 0.998
NA
0.056
0.560
0.998
0.309
Table 3: Results of six methods for different input data dimensions. The cosine similarity is computed between the ground-trum ΣjeA M, and the closest neuron weight.
Feature Learning in Networks. Figure 10 visualizes the neuron weights. shows similar results to that in E.I.T the weights gets updated to the effective feature in the first two steps, forming clusters.
43

---

Published as a conference paper at ICLR 2022
Sep
10-
50
-33
41
36
Sepp
14-
42
Figure 10: Visualization of the weights wy's in early steps under different input data dimensions. Upper row: input data dimension d = 100; lower row: d = 2000.
Table 3 shows some quantitative results. In particular, the average cosine similarities between neuron weights and the effective features after two steps are close to I, showing that they match the effective features.
E.2.2 VARYING CLASS IMBALANCE RATIO
The experiments in the main text has 25000 training samples for each class. Here we keep the total sample size 50000 but use different class imbalance ratios, which is the class -1 sample size divide by the total sample size.
Verification of the Main Results. Figure 11 shows that our claim is robust under different class imbalance ratios. The results are similar to those for balanced classes, except that NTK becomes less stable.
60
1000
Network structure couctuuee
Randorn Feature structore
Rascert Feature Srstuctton
Nelasrk NIT Aoocour
R1 STTECTI
streniane
100
220
302
400
300
120
200
302
400
500
(a) Negative class ratio = 0.8
(b) Negative class ratio 0.9
Figure 11: Test accuracy on simulated data under different negative class ratios.
Feature Learning in Networks. Figure 12 visualizes the neurons' weights. Again, the observation similar to that for balanced classes. Table shows some quantitative results which are also similar to those for balanced classes.
44

---

Published as a conference paper at ICLR 2022
Sepp
50
-35
-2
11
30
Sep
14-
42
Figure 12:
Visualization of the weights wy's in early steps under different class imbalance ratios. Upper row: negative class ratio 0.8; lower row: 0.9.
ratio 0.8
Network
NTK
RF
One Step
Two Step
Network w/o structure
Train Ace
100.0
62.9
72.7
78.3
100.0
100.0
Test Acc
100.0
82.7
70.4
75.7
100.0
61.7
Cos Similarity
0.999
NA
0.293
0.950
0.999
0.218
ratio = 0.9
Network
NTK
RF
One Step
Two Step
Network w/o structure
Train Acc
100.0
84.0
73.6
92.3
100.0
100.0
Test Ace
100.0
81.7
72.4
89.2
100.0
71.8
Cos Similarity
0.997
NA
0.296
0.956
0.997
0.286
Table Results six methods under different negative class ratios.
E.2.3 VARYING SAMPLE SIZE
Here we change the sample size 50000 in Section E.1.1 to be 25000 and 10000. For sample size 25000, we observe similar results. For sample size 10000, we observe over-fitting (test accuracy much lower than train accuracy). Therefore, for sample size 10000 we reduces the size the network (i.e., number of hidden neurons) from m 300 to 50.
Verification of the Main Results. Figure 13 shows that our claim robust under different sample sizes. In particular, the network learning still outperforms the NTK and random feature approaches on structured inputs.
= 25000
Network
NTK
RF
One Step
Two Step
Network w/o structure
Train Acc
100.0
84.0
78.6
50.6
100.0
100
Test Acc
100.0
84.1
74.7
50.0
100.0
50.2
Cos Similarity
0.997
NA
0.105
0.851
0.997
0.230
n = 10000
Network
NTK
RF
One Step
Two Step
Network w/o structure
Train Ace
100.0
73.9
71.6
50.7
100.0
100.0
Test Acc
100.0
75.0
74.3
50.3
100.0
52.2
Cos Similarity
0.995
NA
0.096
0.974
0.994
0.176
Table 5: Results of six methods for different sample size.
Feature Learning in Networks. Figure and Table show that the phenomenon feature learning for different samples is similar to that in E.I.I
45

---

Published as a conference paper at ICLR 2022
203
100
RATWOYY VN CPTLITTIRN
NTC, SESESTE
12ndom PERTUIO, W SOUCCUI
Tabwern struction
Rancom Fwature strurtire
70
structure
300
302
300
502
(a) 25000
(b)
10000
Figure 13: Test accuracy on simulated data under different sample sizes n.
Mep
3xp3
3xp
-53
2ep
Sop
2xp
-33
Figure 14: Visualization of the weights w; in early steps under different sample sizes. Upper row:
sample size 25000; lower row: 10000.
E.3 EXPERIMENTS ON MORE DATA GENERATION MODELS
In this section we consider some additional data distributions and run the simulation experiments, in particular, focusing the feature learning phenomenon. Note that our analysis is for the setting where the input distributions have structure revealing some information about the labeling function. (More precisely, the labeling function is specified by A and P, while the input distribution also depends on them.) We therefore consider two other data generation mechanisms where the labeling function also has connections the input distributions.
E.3.1 HIDDEN REPRESENTATION LABELING
Here consider the following data model: first uniformly at random select Φ from set of binary vectors, and assign label some and -1 to others; sample irrelevant patterns Φ_ uniformly random; generate the input & M.. We randomly select 50 binary vectors for each label, with 500, D 250, k = 50, Po = 1/2.
This is a generalization of the distribution D(1), a component in the distribution of our simulation experiments (see the proof of Theorem 2 for details). Recall the definition of D(!); &. is uniform only two values [+1,..., and (0...., 0), and uniform over irrelevant patterns; the value
46

---

Published as a conference paper at ICLR 2022
[+1...., +1| corresponds to one class and [O.....0] correspond to another class. Our data model here generalizes D(1) to more than 2 values.
The visualization is shown in Figure 15 We can observe similar feature learning phenomena, and the neuron weights are updated to form clusters.
400
65
0.70
600
03
619
1.5
Figure 15: Visualization of the weights wy 's after initialization/one gradient step/two gradient steps network learning under hidden representation labeling.
E.3.2 TWO-LAYER NETWORKS ON MIXTURE OF GAUSSIANS
To further support our intuition of feature learning, we run experiments on mixture of Gaussians,
Data. Let X' R be the input space, and y = [+1} } be the label space. Suppose M E ga is an dictionary with orthonormal columns. Let E,, i I...., & iid symmetric Bernoulli random variables, and g (O0 of La). Then we generate the input and class label by:
T
E Ma
+ 9:
y
E
(290)
In this case, 2* Gaussian clusters will be created. The centers of the Gaussian clusters Σ Li=1 +M; lie on the vertices of a hyper cube, and the label of each Gaussian cluster determined by the parity function the vertices of the hyper cube.
Note that the labeling function roughly equivalent to a network: y/ = Σ.n a.ReLU((C, æ)) where is are the Gaussian centers, and a, for Gaussian components with label and -1 for those with -1
Setting. We then train two-layer network with 800 hidden neurons data sets generated as above with different chosen k's 's and d's. The training follows typical practice (not the hyperparameters in our analysis). In this setting, expect the neural network to learn the effective features: the directions of Gaussian cluster centers.
Result. We experiments with different settings. The parameters shown in Table 6 From Figure 16 we can see that some neurons learn the directions of Gaussian centers, and each Gaussian center is covered by some neurons, which matches our expectation.
Parameters
k
Number of Clusters
dr
Experiment
100
4
16
Experiment
25
4
16
0.7
Experiment
100
5
32
Table 6: Gaussian mixture setting.
E.4 REAL DATA: FEATURE LEARNING IN NETWORKS
We take the subset of MNIST Deng 2012) with labels 0/1, CIFARIO (Krizhevsky) 2012) with labels airplane/automobile and SVHN Netzer al. 2011) with labels 0/1, and train two-layer network
47

---

Published as a conference paper at ICLR 2022
(a) Experiment I with epoch 0/50/80
(b) Experiment 2 with epoch 0/30/50
(c) Experiment 3 with epoch 0/50/80
Figure 16: Visualization of the weights w 's (blue dots) and Gaussian centers (red for positive labeled clusters and orange for negative labeled clusters).
Mey
5xe
Moa 20
1094
0794
435
0.0
Figure 17: Visualization of the neurons' weights in two-layer network trained on the subset of MNIST data with label 0/1. The weights gradually form two clusters.
with m 50. We use traditional weight initialization method (random Gaussian) and training method (SGD with momentum 0.95 without regularization) in this section, for our purpose of investigating the training dynamics in practice.
Then we visualize the neurons' weights following the same method in the simulation. Figure I7 Figure 18 and Figure 19 show a similar feature learning phenomenon: effective features emerge after a few steps, and then get improved to form clusters. This shows the insights obtained on our learning problems also applicable to the real data.
48

---

Published as a conference paper at ICLR 2022
Stpp
0.0
-037
-2
-000
676
Figure 18: Visualization of the neurons' weights in two-layer network trained on the subset of CIFARIO 10 data with label airplanc/automobile. The weights gradually form two clusters.
030
630-
-0.0
-220
05
Visualization of the neurons' weights in two-layer network trained on the subset of SVHN data with label 0/1. The weights gradually form four clusters.
Figure 19:
cos cos(11: (1, 7)
cos U2, 8)
cos U3, 8)
cos U1, 1/2
cos (11 03y
cos( Uz, Uts
ResNet 128) ResNet(2566
0.9727
0.8655
0.6549
0.7454
0.5083
0.6533
0.8646
0.9665
0.9121
0.7087
0.6919
0.9135
Table 7: Cosine similarities between the gradients in the early steps. We choose the neuron weight clos- est to the average weight of the green cluster at the end of the training (in Figure 20 and Figure for Res6et(256)) We record the gradients of the first 30 steps and divide them to three trunks of 10 steps evenly and sequentially. For the three trunks, we get the average gradients U1, 02 03- We calculate their cosine similarities to their average (#) + U/ + 03)/3 and those between them.
Figure20 for ResNet (28))
E.4.1 CNNS ON BINARY CIFAR 10: FEATURE LEARNING IN NETWORKS
Setting, We use (m), which is a ResNet-18 convolutional neural network (He et al. 2016
with m filters in the first residual block. is obtained by scaling the number of filters each block proportionally from the standard ResNet- 18 network which is ResNet (64t. We use ResNet 128
and ResNet (256) in this experiment. We train our model on Binary CIFAR10 (Krizhevsky 2012)
with labels airplane/automobile for 20 epochs. The final test accuracy of ResNet(1128) is 95.75% and that of (256) 93.8%.
Results. Figure 20 visualizes the filters' weights of different residual blocks in ResNet(125) at Epoch 0, 3, and 20, and Figure shows those in ResNet(256) They show that feature learning happens in the early stage, and show that there are some clusters of weights (e.g., the red and green points). These colored points selected at Epoch 20. We first visualize the weights Epoch 20, and then hand pick the points that roughly form two clusters (i.c., the points in the same cluster are close to each other while those in different clusters the two clusters at Epoch 20, and then assign these weights with the same color in Epoch 0 and 3. Finally, compute the cosine similarities and show that the hand picked points indeed roughly clusters in the high-dimension.
far away). We assign red and green colors to
In partieular, have the following three observations.
49

---

Published as a conference paper at ICLR 2022
Opann
0.
(a) Residual block (Green: 0.6152, Red: 0.6973, Two Centers: -0.7245)
200 635
140
cm
300
cdo
120
2.N
140
(b) Residual block 2: (Green: 0.5528, Red: 0.6000, Two Centers: -0. -5.75
Epuch
-25
1.0
07
(c) Residual block 3: (Green: 0.4260, Red: 0.5006, Two Centers: -0.5099)
baol
108
60
(d) Residual block (Green: 0.5584, Red: 0.5697, Two Centers: -0.9074)
Figure 20: Visualization of the normalized convolution weights in all Residual block of ResNet (128) trained on the subset CIFARIO data with labels airplane/automobile We show the weights after 0/3/20 epochs in network learning. The weights gradually form two clusters in all Residual blocks. We also report average cosine similarity between the green/red points in the clusters to their centers and cosine similarity between two cluster centers (Green, Red, Two Centers).
First, we can see that the filter weights change significantly during the early stage of the training, indicating feature learning happens in the carly stage: the change between Epoch 0 and Epoch is much more significant than that between Epoch and Epoch 20.
Second, we can also verify that the feature learning is guided by the gradients: the gradients of filter in the early gradient steps point to similar directions (and thus the updated filter will learn this direction). More precisely, for a selected filter, average the gradients every 10 gradient steps (so to reduce the variance due to mini- batch, and get U1 V2 and vy for the first 30 steps and compute their cosine similarities and those their average. Table 7 shows the results. In general the similarities
50

---

Published as a conference paper at ICLR 2022
613
(a) Residual block (Green: 0.7065, Red: 0.6551, Two Centers: -0.7875)
-00
90
000 Em
05
130
210
16
(b) Residual block 2: (Green: 0.6599, Red: 0.5299, Two Centers: -0.9004)
Excch
615
100
400
-55
1.0 em
138
(c) Residual block 3: (Green: 0,5193, Red: 0.6267, Two Centers: -0,9258)
badt
0003
Ex
100
-25
(d) Residual block (Green: 0.7386, Red: 0.6839, Two Centers: -0.9740)
Figure 21: Visualization of the normalized convolution weights in all Residual block of ResNet(256)
trained on the subset CIFARIO data with labels airplane/attomobile We show the weights after 0/3/20 epochs in network learning. The weights gradually form two clusters in all Residual blocks. We also report average cosine similarity between the green/red points in the clusters to their centers and cosine similarity between two cluster centers (Green, Red, Two Centers).
high indicating they point to similar directions. (Note that similarity of 0.6 is regarded very significant as the filters are in a high dimension x 3 x 1024 = 9216).
Third, we also observe some clustering effect of the filter weights, though not significant as in our simulations. For example, in the red and green clusters in Figure 20 a) for the first residual block, the average cosine similarity for filter weights in the red cluster is about 0.62 and that for the green is about 0.7, while the cosine similarity between the two clusters' centers is about -0.72. This shows significant similarities within the cluster while difference between clusters.
51

---

Published as a conference paper at ICLR 2022
Note that the clustering is less significant than our simulation experiments. This is because practical data have more patterns (i.e., effective feature directions) to be learned than our synthetic data, and also the practical network is not overparameterized in simulation. Then filters are likely to learn different patterns (or their mixtures) without forming significant clusters. The results of ResNet(256)) show more significant clustering than ResNet which supports our explanation. On the other hand, we emphasize that the key insight of our analysis is that the gradient guides the learning of effective features in the early stage of training (rather than the clustering), which is verified as discussed above.
E.5 REAL. DATA: THE EFFECT OF INPUT STRUCTURE
To study the influence of the input structure, we propose keep the labeling function unchanged, vary the input distributions, and exam the change of the loss surface and the training dynamics. We first describe the detailed experimental methodology, which allows us to generate data with similar labeling function but different input distributions. Then we perform experiments on the generated datasets to investigate the change of the learning due to the change in the input distributions, and present the experimental results. Finally, we also perform experiments to verify the intuition behind our experimental method.
E.5.1 EXPERIMENTAL METHODOLOGY
We consider the following experimental method. Given original dataset L = [1T,,, )- (e.g., CIFARI0) and an unlabeled dataset Ul = [ from a proposed distribution Pu (e.g., Gaussians), first extend the labeling function of L to U, giving synthetic labels ÿL to क.. Then train neural network on the union of L and the synthetic data Lu = { Te) ) By investigating the new training dynamics, in particular the difference on the original part L and the synthetic part Lu, we can see the effect of the input structure. The original dataset should be from real-world data, since one of our goals to compare them with synthetic data, and identify the properties of real-world data important for the success of learning.
natural idea is to first learn a powerful network f fxx (called the teacher) on to approximate the true labeling function, then apply f on WI to generate synthetic labels, and finally train another network (called the student) on the synthetic data and original data. However, we found that naïvely implementation of this idea fails miserably: the support of L and U/ can be typically different, and the powerful network learned over can have entirely different behavior on U. Therefore, we need to control the size of the teacher f so that the labeling on U has similar complexity as that L. For our purpose, we can define the complexity of the labeling on L as the minimum size of the teacher achieving an approximation error for chosen c, if the ground-truth data distribution of L is known. However, given only limited data, we cannot faithfully estimate the needed size of the teacher, and need take into account the variance introduced by the finite data.
Our key idea is to use the U-shaped curve of the bias-variance trade-off and select the size of the teacher at the minimum of the U-shaped curve. Since recent works (Belkin et al.] 2019 Nakkiran et al. (020)) show that neural networks can have a double descent curve for the eгror v.s. model complexity. we thus plot the double descent curve, and find the minimum in the classical regime (corresponding to the traditional U-shape curve).
Our method is designed based on the following two reasons. First, on the U-shaped curve, the complexity of the network is still roughly controlled by that of the number of parameters. The local minimum of the U-shaped curve is good measurement of the complexity of the data. the ground-truth is much more complicated than the teacher, then increasing the teacher's size leads to significant decrease in the approximation error (bias) compared to a small increase in the variance, that is, we will be the left-hand side of the U-shaped. In contrast, on the right- side of the U-shaped, increasing the teacher's 's size leads to a small decrease in the bias compared to a significant increase in the variance. That is, the complexity of the ground-trun truth is comparable to lower than the teacher. So the local minimum approximates the complexity of the ground truth labeling function.
Second, the local minimum point is chosen to get the best approximation of the true labels. This helps to maintain the labeling from the real-world data and thus helps our investigation on the input, since too drastic change in the labeling can affect the training.
52

---

Published as a conference paper at ICLR 2022
We note that the method is not perfect. First, the teacher at the local minimum of U-shape may not have very high accuracy, especially on more complicated data. To alleviate this, we also use the teacher to give synthetic labels v/ to 2; in L, and train the student network on L { v() Though this introduces some differences from the original labels, it is acceptable for our purpose of studying the inputs. Furthermore, ensuring the consistency of the labels on the original input in L and Ui is important in our experiments. Second, the measurement is an approximation due to variance. Since only limited labeled data is available, it's important and necessary calibrate the measurement w.r.t. the level of variance on the given dataset.
Method Description. Algorithm presents the details. For a fixed network architecture for the teacher f. it first varies the network size and plots the double descent curve. Then it selects the local minimum in the classic regime of U-shape and trains the teacher with the corresponding size. In practice, we observed that the teacher might have unbalanced probabilities for different classes on U if its training does not take into account U. Therefore, we propose the following heuristic regularization using U. where À is regularization weight, and f(x) is the probabilities over classes given by the teacher:
R(x) = (1(x) + (R2(z)
(291)
E, f(a)ss
In E
R1(x) Σ
(292)
R2(x) (E()),
(293)
Here, R1 (2) guarantees that each kind of label has the same average probability to be generated, and R2 (x) pushes the probability away from uniform to avoid the case that the class probabilities for each data point converge to uniform.
Algorithm 1 Learning the teacher network to generate synthetic labels for studying the effect of the input structure
Input: teacher architecture f. labeled dataset L {(x, 9:) unlabeled dataset { Let to be the size of f. ft to be the teacher of size i.
for i
do Train fi on C and let denote the test loss
end for
Plot 4 v.s. i, identify the classical regime, and the size i, corresponding the local minimum in classical regime.
Train fi, L with regularizer R(z) on U defined in 291 Output: fi,
E.5.2 EXPERIMENTAL RESULTS
Network models. Here one-hidden-layer fully-connected networks with m hidden units and quadratic activation functions. The network is denoted as FC(m). We use ResNet(m)) which is
ResNet-18 convolutional neural network (He et al. (0016) with filters in the first residual block. is obtained by scaling the number of filters in each block proportionally from the standard ResNet-18 network which R65Net(64).
Datasets. We use MNIST (Deng 2012), CIFARIO (Krizhessky 2012) and SVHN (Netzer et al.
2011) as L, and use Gaussian and images Tiny ImageNet (Le & Yang 2015) as U. We generate the mixture data, where the fraction of the unlabeled data is denoted as
Setup. We first use Algorithm on the labeled data and the unlabeled data 2/ to get a synthetic labeling function (the teacher network) and then use it to give synthetic labels on a mixture of inputs from L and U. For MNIST, the teacher network learned is FC((),, where the number of the hidden units is determined by Algorithm|] [ See empirical verification in Figure 26] For CIFARIO 10 and SVHN, the teacher networks are (csNet(5) and ResNet(2), respectively. as determined by our method. The student network for MNIST is FC(9). and those for CIFARI 10 and SVHN are ResNet(9) and ResNet(8), respectively. Finally, we train the student networks on these new datasets with perturbed input distributions.
53

---

Published as a conference paper at ICLR 2022
moo
(b)
(c)
Figure 22: Test accuracy at different steps for an equal mixture 0.5 of Gaussian inputs with data: (a) MNIST, (b) CIFARIO, (c) SVHN.
40
20
200
(a)
(b)
Figure 23: Test accuracy at different steps for an equal mixture 0.5 of Tiny ImageNet inputs with data: (a) CIFAR10, (b) SVHN.
0.25
0.50
0.75
Figure 24: Test accuracy at different steps for varying mixture a of Gaussian inputs with CIFARIO.
Figure 22 shows the results an equal mixture of data and Gaussian. presents the test accuracy of the student on the original data part, the Gaussian part, and the whole mixture. For example, for CIFARIO, the test accuracy on the whole mixture is lower than that of training on the original CIFARIO, 10, showing that the input structure indeed has significant impact on the learning. Fur- thermore, the network learns well over the CIFAR1O part (with accuracy similar that on original data) but learns slower with worse accuracy on the Gaussian part. This suggests that the CIFARIO input structure is still helping the network learn effective features. While the results on MNIST+Gaussian do not show significant trend (possibly because the tasks there simpler), the results on SVHN+Gaussian show similar significant trends as CIFARIO+Gause O+Gaassiin.
Figure 4 shows the results when vary the fraction of the Gaussian data We observe that the test accuracy curve on the original part and that on the synthetic part have roughly the same trend for different before, further verifying insights.
54

---

Published as a conference paper at ICLR 2022
shows the results when mixed with Tiny ImageNet data instead of Gaussians. It shows similar trend, while the performance on the Tiny ImageNet part is higher than that on the Gaussian part. This suggests that compared to Gaussians, the Tiny ImageNet data has helpful input structures, though not as helpful as that on the original data for learning the particular labeling.
Figure -
E.5.3 LARGER NETWORK ON MNIST FOR CHECKING THE EFFECT OF INPUT STRUCTURE
Here we perform the experiment on MNIST as in E.5.2 but for a network with m = 50 hidden neurons rather than 9. Figure 25 shows similar results those for m 9: the learning on the MNIST input part is faster and better than that on the Gaussian input part. The separation between the two is actually more significant than that for m 9. This then also supports insight about the effect of input structures.
25
50
35
306
185
350
175
209
Figure 25: Test accuracy different steps for an equal mixture a 0.5 Gaussian inputs with MNIST, where m 50.
E.5.4
EMPIRICAL VERIFICATION OF OUR METHOD
Det
te5t
38-
1.5
3
35
1.0
02-
60-
(a) Teacher's double descent curve
(b) Student's 's curve when Teacher=FC(9)
4..
tel
15.
3.0
25.
:2*
(c) Student's 's curve when (eacher=FC(50) (d) Student's curve when Teacher=FC(500)
Figure 26: Double descent curves of the students trained on data with synthetic labels (Loss v.s. Parameter number).
55

---

Published as a conference paper at ICLR 2022
We also perform experiments to verify the intuition behind our methodology. i..., the method gives synthetic labeling function with roughly the same complexity on the original inputs and the injected inputs. We first use method on MNIST and samples (of the same size as MNIST) from Gaussian to get the teacher FC( the double descent curve in Figure 26(a). a). Then we train students on the Gaussian data with synthetic labels from the teacher, and plot the double descent curve for the students in Figure b6) The local minimums of the two U-shapes are roughly the same, matching our reasoning. Then also train larger teachers and plot the double descent curve for students on Gaussian data. Figure 26 c) Teacher size 50. Figure 26(d) Teacher size 500. The local minimum of the U-shape becomes larger when the teacher gets larger, again matching our reasoning.
56

---

Published as a conference paper at ICLR 2022
F PROVABLE GUARANTEES FOR NEURAL NETWORKS IN A MORE GENERAL SETTING
This section provides the analysis in more general setting. We first describe the learning problems, and then provide the proofs following similar intuitions as for the simpler settings the main text.
F.1 PROBLEM SETUP
Let X' I2 be the input space, and y {+1} be the label space. Suppose M E Rdx is dictionary with elements, where each element M, can be regarded as pattern. We assume quite general incoherent dictionary:
(D) M is p-incoherent, i.e., the columns of M are unit vectors, and for any i 4 M,)1 S p/vd.
Note that the setting in the main text corresponds to μ = O.
Let Ø E {0, 1) be a hidden vector that indicates the presence of each pattern, and Dj a distribution for Φ. Let S [D] be a subset of size & corresponding to the class relevant patterns. Let P S [A]. We first sample e from Dj,- and then generate the input è and the class label y from o, A, P by:
== ==+ y 1-1-1, +1, if Eiead 3i P.
(994)
otherwise
where the Gaussian noise Ç ~ NO, o Laxa) is independent from ő. Note that the setting in the main text corresponds to oç- =0
We allow general Dj with the following assumptions:
(A1) The patterns in A are correlated with the labels: for any E A, for {+1} let m Elyo:ly v). then y (7+1 7-1)/ > O.
(A2) The patterns outside A are independent of the patterns in A.
Note that we allow imbalanced classes. Let Puin == min(Prip -1], Prly = +1]). If the classes are balanced, then the assumption (A1) implies the assumption (A1) in the main text, so the setting here is more general. (A2) is also more general, in particular, allowing dependence between irrelevant patterns and non-identical distributions for them.
Let D(A, P. Dz)) denote the distribution on (ž.y) corresponding to some A,P, and Dz. Given parameters E (d, D, Po: D(A, P, P3) with A C [D]. P C [k),, and Dj satisfying the above assumptions.
Po: nt ac), the family F= of distributions for learning is the set of all
One special case is the mixture of two Gaussians.
Example. Suppose M has one single column v, and y +1 30 = and y = - otherwise. Then the data distribution is simply mixture of two Gaussians: ă gn + +Nyy la
F.I.1 NEURAL NETWORK LEARNING
Again, we will normalize the data for learning: we first compute x = (i - B(a))/ā where x² = (a, B[ Σ}E(n) Var(Ø,) + do is the variance of the data, and then train on (æ, w). This is equivalent to setting ø ( E(Øl) and generating = Mό + C/ag. For (ă. y) from D and the normalized (a., y), we will simply say (xr D.
The learning will be the same as that in the main text, except the following. We will use small a2 = 62 /o2//ooy(DDm))
And we will use a weighted loss to handle the imbalanced classes in the first two steps for feature learning, and then use the unweighted loss in the remaining steps. Formally, the weighted loss is:
LB(g: σe) =
((x;
(295)
where the class weights ar P for E (+1}.
57

---

Published as a conference paper at ICLR 2022
F.2 MAIN RESULT
In this setting, we have the following theorem: Theorem 34. Set
n7 7 Punin δ
(1 0, 0, = 1/(21) (1)
8 1/h8/2
(296)
km
1/ 1, 1.212) = =x = -1/(2)/ ()) ) 06 1//2/22
(297)
2²
1 1 Tm 1 1 =>= s
om 1/3 o 0, for 2 <t
(1)
(298)
For any 8 (0, O(Lk²)) if S O(V/DD), oc S (min(11/ //Vaj/ k= St (log²
Dmnd
oryPain
m max(f((k*).. D, d}, then we have for any D E Fs, with probability least 1 6, there exists t E [T] such that
Pr(sign(g (x)) # y) < LD( = 0
kaa
KT
m2m
+
(299)
m2/3
m²²
T
Consequently, for any e E 1), ifT m m4/3, and m 2 max /2/2), D3, then
Pr[sign(g) (9) (z)) + y S ()( sc.
(300)
The rest of the section is devoted to the proof of this theorem.
F.3 NOTATIONS
Recall some notations that we will use throughout the analysis.
For vector v and an index set I, let denote the vector containing the entries of indexed by I, and v- denote the vector containing the entries of with indices outside T.
Let p = M M. Then we have PJj for any j. and l $ p/vd for any j + l.
By initialization, w; (0) for E [m]] are i.i.d. copies of the same random variable w)()) ~ NN0 o laxa;; similar for (0) and ((0), Let og Po Poy)/o² denote the variance of Φe for & A, where
Poj Pr(Ø, 1]. Let po be the value such that with probability 1 exp(-I(kk)), Ejæt Ø S PD(D- k) for some Po 1]. That is, Po is upper bound on the density of Φ, with high probability.
Let qe == (w) Mt). Similarly, define 2 = (w)) Mz).
We also define the following sets to denote typical initialization. For a fixed E (0, 1), define
a.d
30
Gv = Rdd qe = (w, Me),
S
113
S
(301)
2
2
0 (D k)
30 (D
k)
<
2
2
max lgel a / log Dm/8)
(302)
G.( = {a e R: |a| S 0a ,.v log(m/8))
(303)
(6(6) (b E :: |8| aB / llggmm/))
(304)
58

---

Published as a conference paper at ICLR 2022
F.4 EXISTENCE OF A GOOD NETWORK
We first show that there exists network that can fit the data distribution.
Lemma 35. Suppose
ku P.D Va & S 16' For any D E Fz, there exists network g (x)
E af 2) bī) which satisfies
Pr lyg (x) S exp((-2(kk) + exp -Ω- oz + k2//vaa) (x.9)/
Furthermore, the number of neurons 3(k 1), |a < 64k, 1/((k):)) 16/1 S 1/4, w.
EEEA M8k(8k), and kw?, .)) + b1 S for any i E [n] and (z, y) ~ D.
Consequently, if furthermore we have kp/ V and 0c < 1/ then
lug" (1: S - (xp((-((k))) (z.0)~
Pr
Proof of Lemma 35 Let w = " EEE Mj and let EjeA E[dz]. We have
(w,x)
Σ
MØ) (/o)
(305)
jEA
Σ Φj + Σ
Pyeae + (w, C/o)
(306)
jEN
jEA
Σ
Σ
Pjede + (w, C/ō).
(307)
JEA
jEA,ES
With probability 2 exp(-S((k)), among all j g A, we have that most po k) of Φb
- (1-Po)/ō, while the others are -Po/ō 2 and thus
Σ jEA,YY
Pjedee
kp DoD
<
1
(308)
Vd
δ 16
Furthermore, (w,<) N' [ and ||
< 52
k22 2/ Vd), have
(tlkw,C/ō)) S 1/16] 2 1 - exp
-9
(309)
0 u: 12//2
2 1 - exp
(310)
of (2p/Va)
For good data points with á and Ç satisfying the above, we have |c s 1/8. By Lemma
gī(z)
6p 6p-p.41//((w,xz))
Σ
6p-nA.1/((w,xx))
(311)
PEP
PRPPOSSS
Σ
(1,, +
Σ
6p4.1/2((w,2) + u)
(312)
PEP
PEP.USPS
Σ 6,,11/2
Σ
Øj fx
Σ
Sp.1./2
th E +
(313)
PEP
JEA
PEP.OSPSK
JEA
59

---

Published as a conference paper at ICLR 2022
Then for good data points, we have yoi (2) 2 1. Similarly,
(z(x) = Σ
6p 1/
x))
Σ
6p-x11AA.1/2((00.))
(314)
Pe P
DE PEPSSSEE
Σ
(111/ + +1)
(315)
PEP
PRP.OSPSR
p+1/1881/2
Σ JEA
Φ +
E PEP.USPS
0p1//18.122
Σ jEA
Φ5 + Ext
(316)
PEP
Then for good data points, we have vož (x) 21.
Note that the bias terms in gi and 52 have distance at least 1/4, then at least one of them satisfies that all its bias terms have absolute value 1/8. Pick that one and denote it as g(z) = Ei= aror((ws, z) + b.). By the positive homogeneity of on, we have
"
g(x) Σ ska,o, (8k()))))))))))))))))))))))))( b./(8k))
(317)
Since for any good data points, (wr,, x)/ (8k) b,/(8k) S 1, then
g(x)
Ska, ( (ww; (8k) b,/(8k)
(318)
where a is the truncated ReLU. Now we can set of = Skos, w = ws/(Bk),, by = b./(8k), to get our final g"
F.5 INITIALIZATION
We first show that with high probability, the initial weights are in typical positions.
Lemma 36. Suppose Du/ Qu/vd < 1/16. For any E (0, 1), with probability least 1 6
2 exp (-O(D- -k) over (()
d/2 < mml (0 $ 30
2 k)/2 < Σ o/ < (D) k)/2,
A4
max lgel のw (Do5)
With probability at least 1 8 over ((0),
[100] ob 2log(1/))
With probability at least 8 over (0)
(0) S o. 2loggl1
Proof of Lemma 36 The bound on (l [ follows from the property of Gaussians.
Note that g = M T (0) ~ NO p) for the matrix p = M M. We have with probability 2 1-5/2,
max; 1ael Σ / 20 log D 5-
For any subset S C [D], let Ps denote the submatrix of p containing the and columns indexed by S. Then 9s = M ()) o(0,o?,p)) By diagonalizing Ps and then apply- ing Bernstein's inequality, we have with probability 2 - 2 2exp ([((S(//(elll))) ||as| E ((lps Jo (llssll + ) By Gershgorin circle theorem, we have
||l| < 1 + (IS) 1d 17/16.
60

---

Published as a conference paper at ICLR 2022
Similarly, have
3 S||
3
15
2
17
5 |S|
|s|
les
p
S
16
16
The bounds on q then follow.
The bounds on ((0) and ())) follow from the property of Gaussians.
Lemma 37.
Suppose Du/Vd 1/16. We have:
With probability 2 1 - 2m exp(-O(D-k)) over w; (0) 's for all e [2m], w E G (0).
With probability 2 1 over 100 's for all [2m], (0) (o(
With probability 2 over a; (0) s, for all i [2m], a; E (o)
Proof of Lemma 37 This follows from Lemma 36 by union bound.
F.6 SOME AUXILIARY LEMMAS
The expression of the gradients will be used frequently.
Lemma 38.
0 Lg(g: 0g) -., (a,vliyg(a; 1] 2) + + & (0, 1)]=},
(319)
ow;
0
[g ae)) -a.Eee (a, ug(x;; {) 1| [[w,, x) + b (0, 1)]},
(320)
;b;
(g) = Ea (1 S 1| ( (wws, 2) + b + E.)
(321)
Da;
Proof of Lemma 38 It follows from straightforward calculation.
We also have the following auxiliary lemma for later calculations.
Lemma 39.
E&, {ayy] = 0,
(322)
ES {layy1) =,,
(323)
Es, [løy|] = 20% 3, G, for j & A,
(324)
ES {anyde)) 7
z. for E A,
(325)
Esg {1ynoos)} < z. for all j E (D].
for
(326)
61

---

Published as a conference paper at ICLR 2022
Proof of Lemma 39
Edd {ay =
Σ
Bøg fazuly= u Prly = w)
(327)
-E[=1}
Σ
Ess fuly= = m}
(328)
vE(+1}
=.
(329)
Bod f1ay0l
Σ
Eøg {lay8l y/ = -} Prly
(330)
Σ
Esg {lel by = =n
(331)
= 2
xE(+1}
=
(332)
BØ, floj1} = PosI(1 Poy) + 11 Pag Poj 20 8.
(333)
Es, {a,00;1= = Σ
Ess {ayuōyl y = t} Pr(y = ul
(334)
=Ef=1}
Σ
Esg {wbjly= = 2}
(335)
xE(+1}
-
Σ
Esg
(336)
2 0E(+1}
(7+1 + +-1))=
=
?
(337)
20
Bdd {
Σ Es flamydolly 0} Pr(y = v]
(338)
oE(11}
$
Σ
Es, fluool ly = 2}
(339)
2
vE(11}
$ 2
Σ
Eon {lomel wy - f}
(340)
vE(#1}
< 0
(341)
F.7 FEATURE EMERGENCE: FIRST GRADIENT STEP
We will show that w.h.p. over the initialization, after the first gradient step, there are neurons that represent good features.
We begin with analyzing the gradients.
Lemma 40. Fix 8 E (0, 1) and suppose w0 E (6),
(00)
E (
for all i E [2m]. Let
Dow v D/oo)
Vilaow / (D/5)
020 (1)
ã (1)
Cc-
If oo =0(/A)) p. 2(k2 DD. k- = =[loo" (Dmd/8)). and de (1)
O(1/k). then
D
1B60 0) : 00
(1) = aa
Σ
M,T, +
(342)
Dw.
1=1
where T3 satisfies:
62

---

Published as a conference paper at ICLR 2022
j E A, then Bn/0l= Oce//ō), where 3 E [Q(1), 1] and depends only on w; (0) ,
i E A, then [Ti] S 50(0 c,
. 10 oc @c
6v) + add ((k)
Proof of Lemma 40 Consider one neuron index i and omit the subscript in the parameters. Since the unbiased initialization leads to (x; g()) = O, we have
dw LB :00 (1)
(343)
a BINDDND B { (0; (1) S ((too)) ,x) (l0) +x(0 E (0. 1)
(344)
t0 BLaD (avoI(Ww!), x) blo) + x E (0, 10)]
(345)
D = (0)
Σ
Mj B(ED))DDE { fayyo, x)) + b()) + r(t) E (0. 1)1}
(346)
=I,
ayyC 1( x) + l0) + t (0.11)
- aa I BaaD)-DE
(347)
First, consider
E A.
Tÿ Blayy)Deg { {a,vo,I[(w()) x) + b0) + +g(0) e (0.11}
(348)
= EEsc { aawds Pr
(00.0) ( + 5 E (0.1)]3 )-1.e())
(349)
where L = (w(0),/0))
Let
La Pr (0. 9) + + 6(0) ((1)
+(0) + (0.1)].
(350)
N2 Pr g())
(10 (6-1.--1) (1) + 5 E (0. 1)]
(351)
Note that [(bA, = ( ko / (D/ and that |o| kw; (1) </²\ = O Vārga v /2ogg( D/8)
and that (k, (0- 9-A)1 are O Dow. / log( erty of the Gaussian (( we have
When ow is sufficiently small, by the prop-
d²
1 Il
(352)
<
Pr
(0, q) + 6(0) +5(1) 2 0]
Pr (0-A.T-A) + +c+ +g(0) 7 0 g(l)
(353)
((1)
())g) + ((0) + {()) g())
Pr
Pr
(0) + ((0) 2
(354)
{())
-(E.).
(355)
In summary,
(Lo - -1,) O(ec).
(356)
Then we have
Ty - Epiiioo fay
(357)
< Epg {laydosl |B,,0 (la - [
(358)
< O Es flay
(359)
< (c./0)
(360)
63

---

Published as a conference paper at ICLR 2022
where the last step is from Lemma
39
Furthermore,
Esaisid (agyd
(361)
Bea (aywo)) Eg al'al
(362)
Ess {ayyos} P-A-S.P-A ((--A =0() E = (0.1)]
Pr
(363)
When ow sufficiently small, we have
Pr ( +b00) E (0.11/2] 2 2(1),
(364)
Pr (.E))
1+ 5() E (0.11/2] = 1/2 exp(-9((M)
(365)
This leads
B= B==Re.0 [Ta] = Pr
(0-1.9-2) + + +5(h E (0.1)] 2 2(1).
(366)
0-2ifiE()
By Lemma 39 Eda {ayyoi} = n/ō. Therefore.
[T) - BByol s O(c/o).
(367)
Now, consider & A. Let B denote AU
T = ( (awnddyT (0.g) + (1) + g0) e (0.1)
(368)
[ (1. + +5th e (0.1)
= Eog E. 2.
(369)
Pr = Eso. { (oryes 0-).((1)
(0.0)) + - e [0.1)}
(370)
Let
(0) 9) + 1(0) + (()) E 10.
1o = Pr g()
(371)
(0- 9-B) + (0) + e E (0.1))
1 := Pr g(t)
(372)
Similar as above, we have (Ec,
(Tb [1] s (cc)). Then by Lemma 39
[T) Eònisò- {ay
(373)
S Eag {lanyro) || a (h - ())
(374)
s (e {layyl) Es, [l
(375)
$ 0(E)) x x1x 0
(376)
-
(377)
Furthermore,
B {ayWá, = EsSa {ayy) Rd, E [76] = 0.
(378)
Therefore,
[3I S 0000
(379)
Finally, consider Vj.
ayyK Vj (aa))
10 ())) + (00) + + E (0.
(380)
QyyCl 1100 9) + + ( ( + ( E (0.1))
(381)
= =Rous { ayyKi
Pr
(1 ②) + + + + 5 E (0.
(382)
64

---

Published as a conference paper at ICLR 2022
(0) G/ō and -- == (w(0) (//)) lj. where (j :- mn
With probability 2 1 dexp(- over S, for any j, 15yl - Ol0c (og(k)) Let Og denote this event.
Let
(0, 9) + 4 + 1- + 610) + +g(1) E (0.1)
1j == Pr {())
(383)
r Pr (0.0) + 1- (1o) + g( E (0.1) {0)
(384)
Similar as above, we have [Bc][] - 1/16cl1 ((w)) Then
[_ a (1g - 17)1 1
- Pr[-
(385)
I 50 + dcxp(-
(386)
V2 - Edacd agWCs 1/1]
(387)
ayyKs (1g |
(388)
ayyKs (1g 13) } + Epsiioa { (awWes (
EssRio- a
(1,- -1--1 11}1
&c
Prl- (389)
Pr[
The first term is bounded by
{
(QyNts (
(1₃ - -T]]10s H
Es E a
(390)
Deyosy/og((
$ Esa
ECoo 1T6 - Tlleel
(391)
T5 log(k)
< O(te) {ayyl
(392)
Φcv (colog())
< 0((o)) x x1 x
(393)
δ
oc [cVlog(())
Ev
(394)
The second term is bounded by
ayythe (1g-11) 11)] - -Cc
E EΦakio_
Gc]
(395)
ayyhi (I₃ - 13]1 96 }
< BBAiiiAA
x de (((
(396)
W Epa 0y
x Ec (1&/l - +cc x de O(k) d((A)
(397)
0c x de e(k))
(398)
and
e e(()
(399)
Furthermore,
Cj Cayyhh 11} =Ex fayyt Ec, { ④
Boaca [o
E 14,] =
(400)
Therefore,
[osvlog(A))
acd e e(k)
|p 00
Ev
+
(401)
65

---

Published as a conference paper at ICLR 2022
Lemma 41. Under the same assumptions as in Lemma 40
LB (g 10;
(402)
bb;
where [Tbl S O(e)).
Proof of Lemma 41 Consider neuron index i and omit the subscript in the parameters. Since the unbiased initialization leads to (2; (1)) O, we have
① 0b
L [g of
(403)
a
(0)
(a (x; $ 1[ x) + + + E
e (0.1))
(404)
-a (0) EE ( x) + b(0) + + (0.1))
(405)
-a (0) Esscie ayd
Pr 6_A (0, + + ( + gL) E (0.
(406)
where ::= (10l0) c//)). Similar to the proof in Lemma 40
Pr 0-
(1) 9) + (10) + g(1) (0, 1)]
(407)
Pr (.0-A.--)++ + (12) E (0.11) 0(4))
(408)
a.ga)
Then
+ +5 e (0.11)
Tb Edai ayy
Pr (6 ((0-A.9-Ak ( 0-
(409)
Essic { layell (-A-E()
Pr (6, + ( - (0.
(410)
Pr (áb 1, + + (11) E (0.11
(411)
0-1.0()
< (Ee)lEEss {lay81
(412)
< ((ee).
(413)
Also,
Egsic ayll Pr 11 A, +1-
6 + E (0,
(414)
(-1.50)
-Bd {ayH)
Pr ((0-A1-A)) +1+60) ( (0.
Pr
(415)
$-A.E.E)
O.
(416)
Therefore, [Tg| < O(c))-
Lemma 42. We have
i
Lo (0) (1) -Ta
(417)
Da,
where
Tal O(max (1)) So v
(
(8), Tal < 0(a (mm()))))
66

---

Published as a conference paper at ICLR 2022
Proof of Lemma 42 Consider one neuron index i and omit the subscript in the parameters. Since the unbiased initialization leads to (2; (1)) = O, we have
0 0a
L 10 :08)
(418)
{ (oun (x; S [[ + + + {
(419)
- B(aD)DDEE { (awoo (ww)), x) + b + g <(1))..
(420)
T
Let 6'A be an independent copy of AA, o' be the vector obtained by replacing in ø the entries Oa with S'A, and let x'= = =Mø' + +s/ō and its label is y'. Then
Tal = Esn { (awEE (, 22) + ((0) + +
(421)
< 2 Bed ((
x)) (0) + +5 ((1) y }
(422)
-Ee { (B (as.wo x0)
+ (00) + {())) = -1}
(423)
$ Ees (( 20)+ + +(()) = }}
(424)
2
Es's ( +b00 + 5(0))o/ = =-1}
(425)
Since is I-Lipschitz.
Tal <
2 Eon.d' [Bo. (w(0), (w()) - (wo'), by = 1, = =11
MMO'
(426)
[Eps { (((l0), Ma0 l = 1] + Eo' {
10/ - --1))
<
Eo_A
(427)
2
(0)
Es Σ (E(D)
of +
Σ
10,del
(428)
(0) max.
E (1 +1++00 0())
(429)
(0) O(max
(i.E)
(430)
With the bounds on the gradient, we now summarize the results for the weights after the first gradient step. Lemma 43. Set
X = 1,)0 -1000 00, = 1/k3/2
Fix 8 E (0,1) 1) and suppose w (0) E Go), (0) Co( for all [2m]. If (llo/)(Dmm6)) (Dm/6)) then all i E [m], w = Ei=1
Db li.t
Mr + satisfying
if E A, then (1)
37/0 5 9. ( (1) a (0)
(n /cc 0
where B E (9(1), 1] and depends
only on w (0);
E & A, then 1
(1
<0
(1)1)a, (0)
102
cr)):
67

---

Published as a conference paper at ICLR 2022
(oeVioothle ( cv + agee -(k)) sg4e-111))
)
and
6(00 = 6/00 + , where [Tb = (Ee):
(0) a; + + where [Tal = O / (o 0))
Proof of Lemma
43 This follows from Lemma 37 and Lemma 40
F.8 FEATURE IMPROVEMENT: SECOND GRADIENT STEP
We first show that with properly set r/(1, for most x. (1; ( ot (2)) )1 < 1 and thus (x; (2) 1.
Lemma 44. Fix d E (0, 1) and suppose w! (6), 6. E (,()) a for all E [2m]] (Dm/5)),
If Du/ Va S 1/16, σςā O(1), ozd/o² = 0(1), k (Dog)(Dmm))) aa S 8² (77k?)
(720) = 0 b and o S 1/k, then with probability 2 1 - (d + D) exp(-(((k)) over
(2)
(c,, (),y), we have yg (x; (2)) < 1. Furthermore, for any i E [2m]. [ .5/)) = 0a1()//))
( .00 = -(1(0)/77) and ) = 0/1))))1)) and for any j E [d], é E [D]
|Gr1 S OlocVTog(h and (C, Dz)1 < O log(k)).
Proof of Lemmn 44
(0) Wm++ is the negation that for Wm+ii the gradient for bm+t is the negation of that for u and the gradient for am+s is the same that for am+ii
(0) w w by (0) (00) and d; am Then the gradient for Note that w.
( (x; (
(431)
2m
(1) ((u 22) + bft1 + c!a1))
(432)
a I Besoo (wu (1) x) + 1 + ) + (1)
B (w x) + +bm + sleh.))
(433)
(1 Bu () x) + 11 + ( + a a (en 22) + +600 + k!?)))
(434)
+
E Ht
(1)
(t .x) + 11th + ( + E 2) + b + {(2))
(435)
Then we have
10 (1)
(x:0
217 (1) Egaa
(1) ,x) + +150) - {(
(436)
(1)
(((oe!)) m+ xx) + +10000 b20t))
Om+i
(437)
m
2n (1) (1 ((wu)) 2x)) + 6/:1 + Eg(e (x/2))
(438)
am++
(1)
(1 [ - m x2)/
(2)
+ ( 600)
(439)
68

---

Published as a conference paper at ICLR 2022
With probability 2 1- exp( among all j & A. we have that most Po k) of o (1 - Poj]/ō, while the others are -Poj/o /ō. With probability 2 1 (d + D) expp( over ç. for any j. lsyl O( /log(k)) and ((., Dz)l & Olocv/oo(kk)) For data points with & and satisfying these, we have:
Claim 1.
Proof of Claim
7
D
D Vift Mr +
(wu : x)
=
(1)
Σ
0yM₁ + (/ō)
(440)
j=1
D
D
H a Me. C/ö) + (v, E ( +
Li,t
Mr.
Σ
(bgMi)
+
+lu,
t=1
j=1
(441)
For each term above we bound as follows. O loloog" (Dmm))/D Let
Note that when ow is sufficiently small,
Bi = 3n10 + ce/ā,
(442)
B₂ Lg Olce/VDD
(443)
C1 o¹
(444)
C2 =
(445)
Then
(0) | /000(///////////000000/////////0 ((1)))
la:
(446)
la
(0)
|B2C2 0(ā/7),
(447)
la:
|BIC2 = + vD//)+
(448)
|a (0)
|22C O(c/(TvV)) 0(1h),
(449)
Then by the assumption on 14,
D
D Mc, Σ
Σ
(450)
5=1
Wiet Me, Modr) EEA
Σ
(1)
+
Σ EEA
Whe Mr, Medr)
+
Σ
Sal (1) Me Ms0ss)
(451)
< a
BiC + +BaC2 + H
(KBI +C2) + DB + C2))
(452)
Vd
s {0(n(a
[BC + B&C²+ + kp
BiC2+ +BaC,
(453)
Vd
s + 11/+1//////
(454)
(455)
69

---

Published as a conference paper at ICLR 2022
By the assumption on oc,
Σ E=1
1 M//5 Ri
(456)
- a0 D(kB2 + DB,) - v (lg(())
(457)
I O0(1 + DB₂) ØCV (oolog(k) 0² v log Dm/o)
(458)
yk2
)0(00)) (oc
(1+
ce +
)
log(k) log( Dm//)) /8)
(459)
7k)
yk
S 0()))//))
(460)
Also note that |151 < 50(
(
[ ((mm/))
Then by the assumption on ac
o/D
D
(v. Σ My
(461)
(
@cc (mm/)() x (01 + C2)
< <0(11(a 110 vdxx
(462)
OVD
<0(n(())))
(463)
Finally, we have
d Kv/S/ < /0
Σ 3=1
(464)
oc logg ā / (lg((k)
s 00 (01) x d x
(465)
oyD
à )0(122))))
(466)
vk
We also have:
[Tal = Ola (m)))))
(467)
b0000 S |,,01 + 11 (00 To
(468)
Vlog(m/))
(0) + aa
122
Ec
(469)
Bees
(2) < 22)
(470)
1a ml
$ la (0) + In (Ta S <10:01 + ow
(471)
(n ())
w (1)
m m x)) x²)
= 2 (uu) (1) xx) Onn
(472)
6(') b
(1)
"0 Tbl (1 (()))))) lc))
(0)
(473)
m+
70

---

Published as a conference paper at ICLR 2022
Then we have
(nfi)
+ vlog(m/0)
|9 10 (z:
=0 (m <0 (lg((m//)))) (
+ 12 10)
(2)
6
+ =
7
k2
(474)
1
+ 0 (m[la 1 1 ow vlog( (og(Dm//)))
+
17 ( of (
(475)
7
0 mn (1) Dw
log( Dm/o)
+ mmaa (0)
1116
+
11110
100 6e
(476)
k
?
(mm)))
111
(0) 1
0 mn ow
mmaa;
(0)
mla;
(477)
k
< 1.
(478)
Then yg (x;
(2) ) 1. Finally, the statement on ((o) c
x-a) (1) ((o
follows from similar
calculation on (w)) (1)
x) (q " .)
We are now ready analyze the gradients in the second gradient step.
Lemma 45. Fix 5 10 and suppose w!!) b,) Go(d), a (6) all i E [2m].
Lat :
+exp(- If Dp/vd 1/16, oęō 01). o2/ 0(1), k (Dm/0)) da 82 (?)h))) (1()) = = T and (2) og
020
= 1/R3/2 then
L (0)
:o ) aa!")) (1)
Σ j=1
M,T, +
(479)
Ow;
where T satisfies:
if A, then 31/01 Oc2a/ō + 100 + (0/////)//(000""0 where B
[S(1), 1] and depends only on w. [,00
i & A, then [Tyl S 1/4 exp(- + 0 oca);
+ exx((-
(2) 1a
Proof of Lemma
45
Consider one neuron index i and omit the subscript i in the parameters.
By Lemma
44 with probability at least 1 (d + D) exp(-I((k) = 1 exp(- over
(a. v). yg
(x: (2))
1 and furthermore, for any E [2m], (w) wーم) ((a))) = (1/))) and for any j E [d], E [D],
(1) c/a)
a//7)
| = o and
|6 < Oloev/lo(k)) (k)) and KG, D,)l < Olo, (lo(())) Let Hl be the indicator of this event.
Li (g (1) ( (2)
(480)
Ou
- B x) + b(1) + 5(2)) E (0.1))
(481)
- Σ Mj B (. (ayII.I
xx) + (() ((2) (0, 1)]Ø,
(482)
:
(1) W (a,
كلليي ue ( x) + bll) + 2 E (0.11]]
ayyl
(483)
71

---

Published as a conference paper at ICLR 2022
Let F := (, (agyl((w()) xx) + b00) +g(0) (0, We have
[T) 1リ-T, Tz1
(484)
((x.)) { (ava(1 - [K) + b()) + +g00 E (0. (),
(485)
(486)
_ [ x) + +80) + 5((0) E 10.. We have
Similarly, let v'= = E (x.))
(487)
{
agBK (1 [1)))((((())) 2x) 600) +000 E (0.
(488)
Ts (xp((_((k))..
(489)
So is sufficient to bound T31 and v'. For simplicity, we use q as a shorthand for gf "
First, consider j E A.
Tj ((o.,))D (agvil((uo(),, , + b0) + e E (0. 1)1o,}
(490)
= Eos { (aweess
(0) + + (2))) E (0. 10.1)
Pr
(491)
$ A.E(2)
where :== (C/5). Let
Ta Pr (0. + 6(0) + 50 (0. ((3)
(492)
1. Pr (0-A.--Ah + + {(² E (0. (())
(493)
By the property of the Gaussian ę(2), that K& 4A>l 0 la! (
), and that [<]
kw 1. K(. A(9.,-))) are all
< O(1kk), we have
1/e -I
(494)
<
Pr g(a)
(00 g)) + + (() +2()) 2 0] - Pr
( (b-A, (b=AA.-a)+ + +g(2) 2 20]
(495)
{(a)
(Ø.g) 9) + + 8(2) + ((2) 21] ((
(0-A.9-1) +c+ + 5(2) 21]
Pr ((2)
Pr
(496)
101 (0) 1k(7 + tc)
+exp(-O(k)) O(Ee2).
(497)
020
(2)
This leads to
[í] - Eps [ayyorTa
(498)
x Eωd {layvo,| |Bo_ (Io - {
(499)
< ( {1
(500)
s (
(501)
where the last step is from Lemma
39
Furthermore,
EgA {ayvĀ,T')
(502)
= Ess (a,wo,) 1
(503)
Pr = Bos (
(1 +.+600 + +5(0) ((0)E((.1))
(504)
72

---

Published as a conference paper at ICLR 2022
By Lemma 19 the property 22)
have K0b 9- + 0/) Also, (b(0 b(o) S la, (co). By
(c)))
Pr ((2)
( A. a) +2+ 10) + 500) E (0.
Pr {(
[10) + 5 E (0.1))
(505)
/// (2) (a) |0 (1)
ce/ le/00 )
(506)
On the other hand,
B =
Pr (,
b10) + +g(0) E (0.1))
= Pr
[500 E b(00]]
(507)
g(2)
-1(1
(508)
and / only depends on ((0). By Lemma 39
E { = Therefore,
T3i 8 s (()2/)) + /0 (2)) + 1a,"" 0 (co( ).)
(509)
Now, consider $ A. Let B denote (.}.
T₁ B(z.))/D {awee,I [10. g) + + 60) + (()
E (0.1) Egg B ( { {auardsT (0) +1+ + 1 e (0.1))
(510)
(511)
Eøs { (nnyeess
Pr B(C.E()
(0,00) +1+b0)++0++0 ( e (0.1)]
(512)
Let
(0. 9) +0++b)= + (()) 10.1))
Io Pr {(3)
(513)
I Pr ((2)
(0 (b-B. B. (-B) + ( + (0)) E (0. 1)
(514)
Similar as above, we have
1/4
131 S s22 Then by Lemma 39
Tíi Ege a. {awyor113]
(515)
$ Bøn {layoo (| n. 1/)13
(516)
< (s {lay Bo, {1or1}
(517)
S O(e2)) x 0(02a) 00000a2).
(518)
(519)
Furthermore,
Esn {ayvo,1]} Bo = Eds {ayu] Ed, {0,} Es [46] = 0.
(520)
Therefore,
T31 50(0)0Ec).
(521)
Finally, consider v'y.
ayyli 1(w00 (),)) x)) +0) - e
-+ <
1/ E (a
(522)
Gyyly Kk g) + 60) (00) E (0.11)
=E
(523)
ayyls
Pr (0, 9) + + - (0.111
(524)
(12)
73

---

Published as a conference paper at ICLR 2022
Let
(0. q) + + 60)) + E (0.1).
1 Pr {(3)
(525)
Pr 1j (())
(0. q) + bio) + t (0. 1)
(526)
Since |t| S (1) we have
11 r2] 16/00/1100 (2) )). Then
1/3 Edant are { aaylls 13)
(527)
B AiS (ayUls (Tg - 12)
(528)
< 00 (2)) ")arr aic
ay
(529)
x 00100/(110 (2)) ( |ayy1 IBx
So
(530)
0
o = (11 (21)) x x1x x
(531)
S 0(1 (2)))
(532)
Furthermore,
{ Caytsss 11)
Eda a { a/aa 11}
ayyl
B acl
Ee (cs) = 0.
(533)
Therefore,
g (2)
5
+ +ex((-S((k))
(534)
yog
Lemma 46. Under the same assumptions as in Lemma 45
8
Lo (1) of =-a
(535)
ab
where [hy S exp(-x((k)) + (
Proof of Lemma
46
Consider one neuron index i and omit the subscript i in the parameters. By
Lemma 44 Pr
(x;g(()) > 1] S exk(- Let I, (x; < 1].
0
LB (1)
0
(2)
(536)
ab
= ()) B( (n I(( x)) + ((1) + g(2) E (0. (0.
(537)
TT
Let Tai := (( a {ayDIlww() x²) + b01) + (2) E (0. We have
To Tall
(538)
( { ( (wo ,,) b(4) 500) E (0, (0.1))}
(539)
S <exp(-2(())
(540)
So it is sufficient to bound Toi. For simplicity, we use as a shorthand for (1)
Toi = (( { (ayo (0) の) + + b0) + e( E (0.1)) }
(541)
= -Eg Es 1050 fawill (0, +2+ ((0) + ( e (0. (0.1)
(542)
Pr -Rps A0 (oo
(10 + + ((2) E (0.11)
(543)
74

---

Published as a conference paper at ICLR 2022
Let
(0. + b0) + 5 E (0.1)]
1. Pr (())
(544)
(0 ( 1 + bl)) + ( e (0.1)
1g = Pr
(545)
g(t)
Similar as in Lemma 20 we have 1Ib - 1gl s Eo2. Then by Lemma 39
Toi Eda fayyIah
(546)
[Baid -a {ag 16)3
(547)
O(ee2) layyl
(548)
S 0(E2)).
(549)
Furthermore,
B {ay81h} = Eda {ayot = 0.
(550)
Therefore, [Tull & ((22) and the statement follows.
Lemma 47. Under the same assumptions as in Lemma 45
i
Lg (1) (2))) To
(551)
0a,
where Ta [T|= = 00
( + (xp(([((k))poly dD Pumin
(1 PPmin
Proof of Lemma 47
Consider one neuron index i and omit the subscript i in the parameters. By (2) > 1 exp(-O(k)). Let Il, (z: 1].
Lemma 44 Prlyg
Da LT i a
(2)
(552)
B(zD)DD Ben + (0) {(2))
(553)
Let Tai = B( { (( + ((0) + {(2))}. We have
Ta Tail
(554)
Ex (,) ((w()) ((v ,x) + (1)) + {
(555)
exp(-((k))
(556)
So it is sufficient to bound Tai. For simplicity, we use shorthand for dj ())
75

---

Published as a conference paper at ICLR 2022
Let Ø'A be an independent copy of ΦA. o' be the vector obtained by replacing in the entries ΦA with 6'A and let x' = MMd + and its label is y/. Then
22) + b0)) + +
Tal
(557)
Bod {Ep 22) + (()) + +g(0)ly 1}
(558)
Ess {Bs (( xx) t000 + +((0)ly -1}
(559)
< Bon { { ( + b()) + ((2))ly = }}
(560)
2
Eog {Es (100)))) xx)) + +B0) + { = =11-
(561)
< 2 Bo { (Bo (1002) xx - (w ااحم m1 = 1, = -11
(562)
S 1 Ba-s (Rop (Kkme) ( b1 =1] } Rays' { (1on Moo 21 =-13)
(563)
I Es A:AA (
(564)
= Eg a, (w(l), Mo)
(565)
((1(1)//7) + exp(-S((k)) x vdD
x ||0n 1oo
(566)
ā
= (
(11 +
poly (dD /Pmin))
(567)
<PPmiin
where the fourth step follows from that a is 1-Lipschitz, and the second to the last line from Lemma 46
and that (1e(1), Mo) < w Il Vd]
With the above lemmas about the gradients, we are now ready to show that at the end of the second step, we get good set of features for accurate prediction.
Lemma 48. Set
1 Punin (1 0, 1/(21) (1), (1) 1/k3//2
(568)
km3
22 1, 10) x() 1/(20) o(
(2) 1/k3/2
(569)
Fix 8 E (0, (),0(1/k))) If Du/Va & 1/16. σāã 01), o2d/02 = O(1), k = 2 (log² Drnd
JyPaiin
and 2 max (axkk))(k") D, d), then with probability at least - 8 over the initialization, there exist ā,'s such that g(x) == 22m ((o( ,x) + b(2) satisfies Lp(ğ)= S exp(-S((k)). Furthermore,
||ā||o = Omm/k), ||ā| O(k5 /m), and ||a|ß = O(k2/ Finally, ||a O |lu
kmm
for (2) 1|2 = (6ō/k), and (6(21 = O(1/k2) for all E [2m].
Proof of Lemma 48 By Lemma
35 there exists a network gx(x) Eim ajo((ut, + +b)
3((+1)
satisfying
Pr lug" (x) < 1] S exp( (kk))) (x.0)~
Furthermore, the number of neurons n 3(k: + 1), la < 64k, 1/ (64k) < 1 S 1 wt
& EeEA (Sk),,), and (ww,, 2) + 6 < 1 for any i E [m]] and v) ~ D. Now we fix an E, and
show that with high probability there is neuron in (2) that can approximate the E-th neuron in g".
With probability 2 exp(-{(mmx((2p))) (D. - k)) k))), among all j & A, we have that at most 2D.(D) k) + le of oj are (1 p.)/ā, while the others -Po/ō. With probability 2 1 (d
76

---

Published as a conference paper at ICLR 2022
D) exp(-I((k) over Ç. for any j. |c,1 & Olog / log(k)) and K(. De)l O(o log(k)). Below we consider data points with Φ and ( satisfying these.
By Lemma 37 with probability 1 - 28 over (0) they are all in (6); with probability 1 - ô over a; 10)s, they are all (6); with probability 1 - å over by "
ss they are all in (o)).. Under these events, by Lemma 43 Lemma 45 and 46 for any neuron i E [2ml], we have
w (2)
ai
(1)
Σ MJJ, +D
(570)
6/ (1)
a; TT.
(571)
where
j E A, then 17, - -3y/0l S m1 = O(1e/0 + 1 /0g +
(2)
11 "="" (c/((00 (2)))))) where
3 E [S2(1), 1] and depends only on w; :
if & A, then [T)] S Ew2 == exp(=(((k)) + O0030E22)
1uyls n a
+ exp(-s2(k))
70t (3)
Tol 56 exp(- expp-))))) O(E2).
Given the initialization, with probability (2(1) over 1 we have
2
18:0 E
sbgn(b) ( sign
(572)
2
12
Finally, since sk1b2199 [ &a = @(1/k²) with probability f2(xa) > 8 over a;
E [22
O 10²)) and depends only on w (0) (0)
b, we have that for
8k b
1
a;
(0)
S ca.
la (0) O
0²
(573)
16 (0)
Ø2
k2yy
Let na = m/4. For the given value of m, by 570 573) we have with probability 2 1 over the initialization, for each é there is different set of neurons 1 S [m]] with [Ze] n, and such that for each ig E lp.
sign(b:.) (0)) sign(b));
E
(574)
21t2
1.2
8A 8
[6:00
J²
[87
(0)
S Eas
la (0)
=
k2
(575)
242 |b2| for each l and each is It, and à; = 0 elsewhere. To show 16 In.
Now, construct à such that ā;
that it gives accurate predictions, we first consider bounding some error terms.
For the given values of parameters, have
7
622
(576)
m
by
7cc
w1
m
kmm
2
(577)
Ew
0
m²
(578)
kk
0
(579)
m3
0
(580)
m
77

---

Published as a conference paper at ICLR 2022
We also have the following useful claims.
Claim 2. EIEA 1MM, x> - 0 (7)
Proof of Claim 2
Σ
(M), x)
(581)
EEA
|oy| +
Σ 1
MP Mj
M c/al
(582)
EEA
k
0
0
KD
+0
k
(583)
dō
0
(584)
Claim 3.
(0)
(w
(2) x)
ai
B
(M ; x)
0
1
(585)
m
jEN
Proof of Claim
3
D
(2)
x²)
=
Σ
Oi
Tr + v,
(586)
1=1
41) die
MrMe, x)
+ 1
die
W) TeMe) x)
+ +1(0,z)1-
(587)
EEA
REA
Then
(0) By
{10 x))
(2)
ai
(M)
(588)
JEA
(w
(2)
x)
Oi BY
(1)
(Mz x))
+
(1) BY
(M,, x)
ai
(0) By
( , x)
(589)
jEA
JEA
DEA
(1) By
<
(10
, .))
0i
())
+ 1
(1)
dis
[0]
B7
(M
(590)
jEA
jEA
The first term is
(1) By 4r
(2)
(2)
x))
(M)sz) x))
(591)
jEA
0
(1)
Σ
Ti
By
Me,
+
T TrMe, x))
+ +1(,,0811
(592)
78

---

Published as a conference paper at ICLR 2022
By Claim 2
87) à
88
Te
Mr, x)
5 Σ
Tr
(593)
ÉEA
EEA
S Ew1
Σ KMMe
(594)
DEA
hiew!
0
(595)
Σ
x)
Σ Todj
+
Σ AEAiie
TeM, Mj0s
+
Σ
C/M
(596)
A
PEA
Dew2
+0
(DPewz
u222
1 vdō
+0
Dew
σe llg(k)
(597)
DEw2
0
(598)
(1,,2)
S
(p, Σ Mede)
+ +11,,10011
(599)
(E|D]
Σ
1 Mc)l
+ C/1
(600)
EE|D
Do +k
cvV de, (occylog(k))
0
(601)
Vd
0
PoD + vdc, v log(k)
(602)
vvd
0o
(PoD (NoD+ + o //llg(k)
(603)
PoDevvd
0
(604)
Then by (576)- (580).
Eo ==
kewl
+
Dew2
+
DoDevvd
0
m²
k:2y
m²
7Ec
m
7
33/25
k
(605)
We have
a
[0)
110 ow v Vlo (o0)))))). So the first term is bounded by
(w! 2)
(2)
aic
(0)
By
x)
$ |
(1)
(606)
ā
jEN
0
( G2
ww
v Tog( (mm/8)
(
k22 (m²02
+
m²
+
mā²
7
+
tke m3/22
)
0
m
1
(607)
By Claim
2. the second term is bounded by
(1)
(0)
By Σ M,
x)
0o
kny (a ow / Tog( Dm/007
0
(73
73
(608)
Ø²
m33
JEA
Combining the bounds on the two terms leads the claim.
79

---

Published as a conference paper at ICLR 2022
Claim 4.
10
(0)
0
1
(609)
kmm
Proof of Claim
By Lemma
43 and 46
-
16,
+ 10 bb
(610)
0
17
(0)
+
|a
((s)) + fo2))
(611)
1
1
0
s 0
(612)
km2
k.2m
k2m
We are now ready to show ÿ is close to 2y".
[ī()) - 2g" (x))
(613)
1(k-1)
3(k+1)
Σ
Σ ās, ((w) (wu x)) + (22)
Σ
20 (1w7 2) + bb)
(614)
HEle
3(k+1)
2a |b31 (1m) (2) x²) (22)
3(k+1)
2071681. fe
(0
(wi 2) (0)
10 Th
11(00 |m
107
Hele
(615)
3(k=1) 1)
1
2ajlbil
(m0! .t) + (110
2a |6,] 16!00
ai By
(0)
(M
+ Di
(0)
ni
E=1
Hele
jEA
(616)
1(k+1)
(0) 8y
(0)
Σ
2a
(b:00
ai
(M
(((0)
2a 1a
10
a
10
[b;]
(w)
x)) + b
F=1
feEle
JEA
(617)
Here the second equation follows from that is positive-homogeneouss in [0, 1). Kw] .r) 6b6 1,
| 1/1b21 < 1.
By Claim and the first term is bounded by:
20 [b2]
BY
3(k 1) max
{wi (2) x²)
(M x)
+ +1b!? (0)
(618)
JEA
2a b²]
1
< 3(k + 1) max
(619)
1b
m
61
< 0
(620)
m
80

---

Published as a conference paper at ICLR 2022
By Claim 2
the second term is bounded by:
(0) By
0i
3(k- + 1) max
(M
( x)
(621)
jEA
2a |b2| |6/01
Oie B
(0)
16 l
< 3(k + 1) max
x)
(Mi x)
(622)
8ki[b?
JEA
jEA
2a² |b S 33k + 1) max
8 0
Sku, By|b5l
Σ JEA
(M 2t
(623)
16/4 10 8ki 1621
621 0210//1 10)
S 3(k + 1) max (la}ca)
(624)
< 0 (k)
(625)
Then
(0x)) 2g" 2x)(x) =0
k-Ea - +
S 1.
(626)
This guarantees vr(x) 2 1. Changing the scaling of å leads the statement.
Finally, the bounds à follow from the above calculation. The bound on ||a(2)|2 follows from
Lemma 47 and those on ||ce 2|2 and lb6())|2 follow from 570 571 and the bounds on a!" and
B( in Lemma 43
F,9
CLASSIFIER LEARNING STAGE AND MAIN THEOREM
Once we have good set of features in Lemma 48 we can follow exactly the same argument as in Section B.6 and B.7 for the simplified setting, and arrive at the main theorem for the general setting:
Theorem 49 (Restatement of Theorem 34). Set
( Pmninn ē km3
.1 0, 0, ()) (1) 1/R3/22
(627)
(2) 1, xa2 (2) 1/(21) (2), (2)
0 -1/k3/2
(628)
1 ( = n =
2
(!) = (1 = - 3/3 0g = 0, for 2 <t
k3
(1)
(629)
Tm 1/3
For any 8 (0, O(L)3),, if D( og < O
k= s (log²
Dmnd
Sypestn
max{([(k*)) D, d}, then we have for any D E Fe, with probability least 1 - 8, there exists t E [T] such that
KT
k² m/3
(x)) # v] < (0) 0
+
+
(630)
m233
m
T
Consequently. for any e (0, 1), ifT = 4/3 and m 2 max (22)22)))))))). D}. then
( (x)) # vी - ()(g Sc.
(631)
81


Reviews:
[{"review_id": "ydnIC7YwhL", "reviewer": "Reviewer_uM4G", "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": "**Strength**:\n\n* A novel analysis of neural learning that connects the learning performance with its ability in adapting to input structure. The analysis is made accessible due to the explicit assumption on data-generation mechanism, which I believe is sufficient given the early-stage of this line of work.\n* The theoretical results are empirically verified.\n\n**Weakness**:\n\nThis work can greatly benefit from expanding the coverage of the experiments, in terms of data-generation models, sample size and data dimension, etc. Specifically\n\n* Expand the experiment coverage in terms of sample size / data dimension (and optionally other axis such as class imbalance). Since we are stating the main theorems in terms sample size / data-dimension. I wonder if author can expand the first two sections of experiments ( \"Simulation: Verification of the Main Results\" and \"Simulation: Feature Learning in Networks.\") to test the robustness of the claim and understand the learning behaviors in a variety of sample size and dimension settings. \n\n* Evaluation in \"Simulation: Feature Learning in Networks.\": This section seems to be rather crucial in supporting the theoretical claims. However, most of the results reported are qualitative (Figure 2). Please consider reporting quantitative result (e.g., in terms of certain distance measure between model features and the ground-truth $M$), and examine across different data dimensions,sample size, and optionally with respect to class imbalance, etc.\n\n* Please discuss (in problem setup or in conclusion section) the expressiveness of the function space defined in (1). In particular, what type of data generating function is not yet covered by such model? (e.g., there is a nonlinear corruption process involved in the data-generation mechanism). Correspondingly, in the experiment section (e.g., \"Simulation: Verification of the Main Results\"), it might be also extend the experiment to more flexible data-generation mechanisms (say y=NN(x) where NN is a 1-layer network) to verify if the result still holds and in what extent.\n\n\nMinor:\n\n* Clarity: \"(A1’) The patterns are independent, and ...\". Please clarify, do you mean the patterns in A is independent from the labels?", "summary_of_the_paper": "This work proves the feature learning ability of a 1-hidden-layer network (Theorem 1), under the assumption that the data is generated from a dictionary learning model. Additional result on the limitation of no feature learning and no input structure is also provided (Theorem 2-3). The proof proceeds by closed-form analysis of gradient dynamics, which is possible thanks to the simplicity of the data-generation mechanism. Authors empirically verified their claim on synthetic and semi-realistic experiments.", "summary_of_the_review": "A novel theoretical analysis that connects neural model's learning behavior to its ability in adapting to input structure. The analysis is done under a simple data-generating model and was relatively accessible. Author empirically verified their claims in simulation experiment. which slightly weakens the quality of this contribution. ", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "ue4QYUSGKFH", "reviewer": "Reviewer_bp8c", "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": "+  a simple model\n+ a positive learning result analyzing GD\n+ a relevant lower bound\n\n- the model is very specific with many assumptions ensuring that the GD analysis works out (e.g., irrelevant attribute effects are balanced out)\n- all the interesting action in the upper bound happens in the first two rounds of GD, which suggests that this particular problem can also be solved by simple combinatorial methods\n- the claimed SQ lower bound simply consists of showing that the parity function fits the model (i.e., no new lower bound insight here)\n- it is not clear that kernel based learning cannot solve this problem; the text suggests this but I could not find any proof/evidence in the paper", "summary_of_the_paper": "This paper gives results for learning a simple classification task by training a 2-layer NN with truncated ReLU activations. They also prove some lower bounds suggesting the necessity of the some of the model assumptions. From these results they try to infer that (a) their algorithm goes beyond the kernel/NTK regime and (b) the features learned are data/input specific and the task cannot be accomplished with oblivious features (such as random features).", "summary_of_the_review": "The contributions of this paper, in my view, are a simple model that seems to require learning input-specific features, and a careful detailed analysis of the first two steps of GD applied to a 2-layer network with truncated ReLU activations. I think these are interesting, but might not be sufficient to justify acceptance.", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "pc2Ze1iRTC2", "reviewer": "Reviewer_zbTh", "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": "Strengths:\n- The paper presents an interesting analysis of gradient descent under data-dependent feature distributions and the results appear to be novel.\n- The paper is well-written and provides a good summary of related work (esp. in the Appendix).\n- The experimental results, albeit limited, are encouraging.\n\nQuestions and Concerns:\n- Can the authors elaborate on the relationship between network depth and the \"emergence\" of good features under the model considered herein?\n- Can the authors provide explicit details on the improvements / differences with comparison to the results in Daniely and Malach (2020), specifically the lower bound?\n- Can the authors provide some formulations for capturing class-dependent feature distributions in real-world problems? The definition assumes such a distribution exists, however one can think of several counterexamples (e.g., occlusion in visual domains) where \"class-dependent\" nature of features is not apparent.", "summary_of_the_paper": "The problem of generalization in over-parameterized neural networks is of wide interest to the theoretical machine learning community, and this paper studies this problem from the lens of understanding structures present in feature distributions. The authors present a model for learning neural networks where the decision function can be expressed in terms of a set of correlated features and demonstrate that gradient descent recovers low generalization error under these assumptions. The authors demonstrate that in the absence of structure (i.e., when features are independent of each other), no algorithm can recover low error, which hints at how data-dependent feature learning is necessary for generalization in neural networks.", "summary_of_the_review": "Overall I like the paper, and I think there are certain interesting results that are demonstrated, however, I believe the authors should elaborate more on the nature of the feature correlations considered: currently their model assumes two types of features, i.e., ones that are correlated with labels, and the ones that aren't. It perhaps would be interesting to examine whether this assumption can be weakened to something that holds stochastically over the data distribution, as such precise models for data generating processes are hardly available in practice (and are usually substituted by generative models).", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "E5PKmkS4kQb", "reviewer": "Reviewer_Mhvy", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The primary results of the paper are theoretical. It is well-written and clearly presented. An extensive discussion of the related work together with a clean crisp and highly relevant message on the role of input structure in explaining the learning capabilities of neural networks are some of the strengths of the paper. The experiments are also interesting although not very comprehensive (which is fine as the paper’s primary contributions are theoretical).\nThe only aspect where the paper lacks is perhaps that the main results and the techniques used seem very similar in spirit to those of Daniely and Malach (2020). Firstly, the lower bound to show that in the absence of any input structure learning can’t happen follows almost directly from a similar lower bound in Daniely and Malach (2020).\nGiven this, the main contribution of the paper is in showing the power of neural nets over data-independent kernel methods. Here, the paper does go into greater detail (in the Appendix) to contrast the contributions of current work to those of Daniely and Malach (2020) but it is not clear how technically novel the current analysis is. The phrase “Input structure” is a bit vague as one can argue that Daniely and Malach (2020)’s result also shows the importance of “input structure” (since their result shows that parities are learnable only under a certain input distribution). A key technical difference seems to be that the current setup requires a second gradient step to find the right patterns to focus on. This indicates that the current setup is more challenging to learn that the parity problem Daniely and Malach (2020) focus on.\n\nQuestions and suggestions:\n1.\tIt would help to explicitly mention that the set A is fixed across inputs when describing the setup.\n2.\tCondition (A1) seems to not hold for the parity example (Example 2 in page 4)? Can you elaborate on how this condition is satisfied in the case of parities?\n\nMinor typos and comments:\n1.\tPage 9: “chaning” -> “changing”\n2.\tIn Theorem 1, k is Omega(log^2(m)) and m itself is Omega(k^12). This seems like a circular dependency. Can write this more clearly perhaps by using Theta instead of Omega in the appropriate place?\n", "summary_of_the_paper": "The paper delves deep into learning dynamics of a one-layer neural networks and presents a class of functions and input distributions on which one layer neural networks trained with gradient descent learn well while no data-independent embedding map of the input to a polynomial number of dimensions can learn these function/distribution combinations without using weights which are exponentially large.\nThe main message seems similar in spirit to the paper titled “Learning Parities with Neural Networks” by Daniely and Malach, but as opposed to the artificially created problem of parities, the current paper presents a function/input distribution combination which is closer to distributions seen in practice. An additional result they show is that in the absence of any input structure the learning problem becomes hard under the statistical query model.\nFinally the paper concludes by showing some experiments to support their claim that input structure is necessary to explain the good learning capabilities of neural networks.\n", "summary_of_the_review": "The paper studies a very central problem in developing an understanding of deep learning today. It builds on a line of literature which theoretically capture settings where neural networks trained with gradient descent are provably more powerful than data-independent kernel methods. Moreover, they authors clearly outline the mechanism by which neural nets derive their additional power. Albeit a limited novelty (due to similarity to prior work), I believe the paper’s contributions are quite significant thereby I believe it clears the bar for acceptance at ICLR.", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "1BscAXhGsV", "reviewer": "Reviewer_Jr9n", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n- The paper is well motivated and studies a question of great interest to the community (the effects and benefits of NN feature learning), and highlight the importance of input structure, which to my knowledge is often neglected in the literature.\n- The paper (to the best of my knowledge) is technically sound.\n- I appreciated section 5 which helps to provide some intuition for the results (although also see weaknesses).\n\nWeaknesses:\n- Theorem 2 seems slightly weak in that it requires a bounded feature map dimension to work to show that fixed feature models fail, so what about infinite dimensional feature maps like say kernel methods? This is not an issue with other settings to show that fixed feature models fail e.g. https://arxiv.org/abs/2012.09816 (which also should be in the related works, as they also look at input structure, a 'multi-view setting' to show the benefits of NN feature learning over feature selection methods like random features).\n- The experimental section is not very convincing to show that your theory is relevant for NNs in practice. It would be good to see Figure 3 for a larger setting, perhaps CIFAR10 with a deeper resnet/cnn. You have a nice simplified story for how NNs learn features from your theory: 1st step extracts rough features, 2nd step refines these, then finally the linear classifier is trained. I'm not convinced that this holds in practice with the provided experiments.\n- Likewise the networks for MNIST are very narrow, you have m=9? Perhaps MNIST isn't a very good dataset to depict the importance of NN feature learning, as I believe linear models can already achieve a respectable score.\n- I appreciate the efforts of the authors, but I'm still somewhat lacking in the intuition for the setup and how it is relevant to practical settings. For example, the first line of section 3 talks about circles and lines, but you make no further mention of this example. How does your 'structured' data look like in terms of circles and lines, particularly your assumption A1) which is the key assumption I believe, compared to A1')?\n\nMinor points:\n- Bottom of page 2: close not closed\n- Under lemma 5, should be j \\in [A] not j \\in [D]?\n- The setting of having a changing regularisation strength (in classifier learning stage paragraph just before sec 5.2) is quite strange/not standard. Can you provide a bit more justification for this please?", "summary_of_the_paper": "This is a theoretical paper that studies the feature learning properties of neural networks (NN) and the importance of input structure on the advantages of NN's over fixed feature models like linear or random features models. The authors create a setup motivated by real data where they can analytically show that a single hidden layer NNs can achieve good error (Theorem 1), whereas models with fixed features need to be exponentially large (in the number of relevant features) to match (Thm 2). The authors also show that without input structure, polynomial algorithms in the Statistical Query model achieve random guessing error (Thm 3). Some experimental evidence is provided to support some of the claims. ", "summary_of_the_review": "I'm recommending weak reject, because although I believe the paper is well-motivated and makes some inroads into an important question, I have concerns about some of the theoretical results, the sufficiency of the experimental results to justify the theory, and also some of the intuitive explanations for the theoretical setup.", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors theoretically analyze learning of two-layer neural
networks by gradient descent with respect to a data distribution that
exposes how useful features are learned during training.

Overall, the reviewers felt that the analysis yielded useful insight,
and was original.

During the discussion period, a reviewer recommended that the authors
look at papers providing lower bounds on statistical query learning of two-layer networks,
and consider comparing the lower-bound technique of this paper with that earlier work.
Decision: Accept (Poster)