Is Stochastic Gradient Descent Near Optimal?
Authors: Yifan Zhu
Hong Jun Jeon
Benjamin Van Roy
Venue: Submitted to ICLR 2023 (2023)
Keywords: sample complexity
neural networks
stochastic gradient descent

Abstract: The success of neural networks over the past decade has established them as effective models for many relevant data generating processes. Statistical theory on neural networks indicates graceful scaling of sample complexity. For example, Joen & Van Roy (An information-theoretic framework for supervised learning, 2022) demonstrate that, when data is generated by a ReLU teacher network with $W$ parameters, an optimal learner needs only $\tilde{O}(W/\epsilon)$ samples to attain expected error $\epsilon$. However, existing computational theory suggests that, even for single-hidden-layer teacher networks, to attain small error for all such teacher networks, the computation required to achieve this sample complexity is intractable. In this work, we fit single-hidden-layer neural networks to data generated by single-hidden-layer ReLU teacher networks with parameters drawn from a natural distribution. We demonstrate that stochastic gradient descent (SGD) with automated width selection attains small expected error with a number of samples and total number of queries both nearly linear in the input dimension and width. This suggests that SGD nearly achieves the information-theoretic sample complexity bounds of Joen & Van Roy (2022) in a computationally efficient manner. An important difference between our positive empirical results and the negative theoretical results is that the latter address worst-case error of deterministic algorithms, while our analysis centers on expected error of a stochastic algorithm.

Under review as a conference paper at ICLR 2022
Is STOCHASTIC GRADIENT DESCENT NEAR OPTIMAL?
Anonymous authors Paper under double-blind review
ABSTRACT
The success of neural networks over the past decade has established them as effec- tive models for many relevant data generating processes. Statistical theory on neu- ral networks indicates graceful scaling of sample complexity. For example, Jcon & Van Roy (2022) demonstrate that, when data is generated by a ReLU teacher network with W parameters, an optimal learner needs only ((W/c) samples to attain expected error However, existing computational theory suggests that, even for single-hidden-layer teacher networks, to attain small error for all such teacher networks, the computation required to achieve this sample complexity is intractable. In this work, we fit Lungle-hideen ated by higle-hidden-layer ReLU teacher networks with parameters drawn from a natural distribution. We demonstrate that stochastic gradient descent (SGD) with automated width selection attains small expected error with a number of samples and total number of queries both nearly linear in the input dimension and width. This suggests that SGD nearly achieves the information -hormation-tthoreticc theoretic sample com- plexity bounds of Jeon & Van Roy (2022) in computationally efficient manner. An important difference between our positive empirical results and the negative theoretical results is that the latter address worst-case error of deterministic algo- rithms, while our analysis centers on expected error of a stochastic algorithm.
neural networks to data gener-
INTRODUCTION
Over the past decade, deep neural networks have produced groundbreaking results. To name few, they have demonstrated impressive performance on visual classification tasks (He et al., 2016), parsing and synthesizing natural language (Devlin et al., 2018; Brown et al., 2020), and super-human performance in various games (Mnih et al., 2013). These achievements establish neural networks as effective models for many relevant data generating processes.
Statistical theory on neural networks indicate graceful scaling of sample complexity. For example, when the data is generated by a ReLU teacher network with W parameters, Jeon & Van Roy (2022) demonstrate that the sample complexity of optimal leamnr is Ö(W).
However, existing computational theory suggests that, even for single- lingle-hiddennllyerr teacher net- works, the computation required to achieve this sample complexity intractable. For example, Goel et al. (2020); Diakonikolas et al. (2020) establish that, for batched stochastic gradient descent with respect to squared logistic loss achieve small generalization error for all single-hidden-llyee teacher networks, the number of samples or number of gradient steps must be superpolynomial in input dimension or network width. Furthermore, current theoretical guarantees for all computation- ally tractable algorithms proposed for fitting single-hidden-laye teacher networks with parameters drawn from natural distributions only bound sample complexity by high-order polynomial (Janza- min et al., 2015; Ge et al., 2017) or exponential (Zhong et al., 2017; Fu et al., 2020) functions of input dimension or width.
In this work, we aim to reconcile the gap between these negative theoretical results and the apparent practical success of stochastic gradient descent (SGD) in training performant neural networks. To neural networks data generated by mangle-hidde--e teacher networks with parameters drawn from a natural distribution. We demonstrate that SGD with automated width selection attains small expected error with number of samples and total number of
do so, fit hinglehhideen-le
ReLU

---

Under review as a conference paper at ICLR 2022
queries both nearly linear in the input dimension and width. This suggests that SGD nearly achieves the ceemmation-thoortti sample complexity bounds established in Jcon & Van Roy (2022); Bartlett et al. (2019) in a computationally efficient manner.
An important difference between our empirical results and the negative theoretical results of Goel et al. (2020); Diakonikolas et al. (2020) is that the latter address worst-case error of deterministic algorithms, while our analysis centers on expected error. The focus on expected error is more in line with the information-theorell results suggest that such expected-error analyses may be better-suited for understanding empirical properties of neural network learning.
sample complexity bounds of Jeon & Van Roy (2022). Our
2 RELATED WORK
Our work contributes to the literature on the sample and computational complexity of single-hidden- layer networks. To put our work in context, we review related work in this area, grouped into several categories.
2.1 STOCHASTIC QUERY LOWER BOUNDS
Most lower bounds on the sample and computational complexity of Lingle-hidden-lye neural net- works have been established through the stochastic query framework (Goel et al., 2020; Diakoniko- las et al., 2020; Song et al., 2017). A stochastic query algorithm accesses an oracle that returns the expectation of a query function within some tolerance. The literature focuses on query functions that enable gradient descent with respect to common loss functions, with one query per gradient descent step.
Aside from the results of Goel et al. (2020); Diakonikolas et al. (2020), which were discussed in the introduction, Song al. (2017) show that setting where the number of samples less than the product of the input dimension and the width, exponentially many stochastic queries are required.
2.2 SAMPLE COMPLEXITY UPPER BOUNDS
Jeon & Van Roy (2022); Bartlett et al. (2019) study the sample complexity of optimal learning from data generated by teacher networks, without addressing algorithms or computational complexity.
Bartlett et al. (2019) establish upper and lower bounds on the VC dimension (see Vapnik & Chervo- nenkis (1971)) of noiseless neural networks. For piece-wise linear activation functions, their work shows that the VC dimension of network with W parameters and L layers is upper bounded by O(WL log W) and that there exist networks with W parameters and L layers with VC dimension lower bounded by Q(W L lo)(W/L)) These bounds on the VC dimension translate to both upper and lower bounds on the sample complexity of any probably approximately correct (PAC) learning algorithm (Valiant, 1984). Results in Hanneke (2016) show that for PAC algorithm that learns up to within tolerance e and failure rate at most 8, the sample complexity is θ (1 (VC + log })). . In our context, this implies O (L(W L log W + log 4)) sample complexity for all teacher networks with W weights and T. layers and Ω (og.l///// + log !)) for some of these teacher networks.
Jeon & Van Roy (2022) use information theory to study the number of samples required to learn from noisy teacher network such that the expected error is small. Instead of relying on VC dimension, their bounds scale linearly in the rate-distortion function of the neural network. For networks with ReLU or sign activations, their results imply an Ö(W/e) sample complexity bound, where W the total number of parameters, and is the expected error.
For single-hidden--lyee ReLU teacher networks, both works suggest an upper bound on sample complexity that is linear in the number of parameters, up to logarithmic factors. However, no prac- tical algorithm is given. The VC dimension upper bound implies PAC-learnabilitty and Jeon & Van Roy studies the expected performance of an optimal Bayesian learner. An important difference between these results and the negative stochastic query results is that the latter analyze worst-case performance.
2

---

Under review as a conference paper at ICLR 2022
2.3 CONCRETE ALGORITHM
A segment of the literature offers concrete algorithms for learning from single-hidden-layer teacher networks (Zhong al., 2017; Fu et al., 2020; Janzamin al., 2015; Ge et al., 2017).
In Zhong et al. (2017), to fit the data generated by a noiseless single-hidden-layer ReL.U network, the weights are first initialized by a tensor method, which guarantees linear convergence under gradient descent with high probability. However, the sample complexity is exponential in the input dimension and the number of hidden neurons when the weights are i.i.d. Gaussians, as we assume in this paper (see Appendix D for details). Fu et al. (2020) adapts the tensor initialization of Zhong et al. (2017) and provides similar results for cross entropy loss, instead of L2 loss.
Ge et al. (2017) design an alternate objective function G such that using SGD to minimize G can recover the parameters of the wangle-hidde-llyerr teacher network with high probability. The sample and computational complexity are high-order polynomials in the input dimension and width.
Janzamin al. (2015) use tensor factorization, Fourier analysis, and ridge regression fit the data generated by single-hidden-laye teacher networks with high probability. In the case of Gaussian inputs, the sample and computational complexity are high-order polynomial in input dimension and width. Note that the results in Ge et al. (2017); Janzamin et al. (2015) do not contradict the results of Goel et al. (2020); Diakonikolas et al. (2020), since the former construct algorithms that work with high probability.
Results from a couple papers that focus on networks with multiple hidden layers bear additional im- plications if specialized to single-hidden-layer networks. Arora et al. (2014) propose algorithm that learns a distribution generated by a sparse neural network with sign activation units and random edge weights. When specialized to single hidden layer this gives rise to an Ö( sample com- plexity bound, where M is the width. Zhang al. (2016) propose algorithm for which sample complexity depends exponentially on maximum among neurons of LI norms of incoming weights for particular activation units.
PRELIMINARIES
In this section we give necessary definitions for our experiments, much of which is directly adapted from Jeon Van Roy (2022).
3.1 TEACHER NETWORK
We assume that the training algorithm is given a set S of N i.i.d samples
S = ((11,11))....
Rd x R.
The input X (0, Ta), and the output Y is produced by random single-hidden-layrr teacher network g with noise W:
y x) W Rd - RR The random single-hidden-layer teacher network y is parametrized by (a, b, O):
M
x(X) Σ O.ell( X + bz),
where M is the width of the hidden layer and relu(x) = max(0, x). For the learnable parameters, sid No d+1). and 0, iid _N(0, 1.) The choice of variances keeps the variance of g(x) relatively fixed across different and M. We further assume that the noise W ~ (N(0, We denote the hyperparameters for this teacher network by y := (d, a.). Note that this is a special case the ReLU data generating process from Jeon & Van Roy (2022).
we assume that for all E [M],a, rid NO0 d+1 Ta), by
3.2 ERROR
We define test error as dx (Pr()p)), the KL-divergence from the predictive distribution of Y (Py) to its true distribution Py. We assume that the predictive distribution of Y is Gaussian with the same
3

---

Under review as a conference paper at ICLR 2022
variance the real distribution Y, i.e., Y (X) o²). where is the model trained on S. Then, the KL-divergence simplifies to L2 error with respect to the noiseless teacher network scaled inversely by the noise (see section 2.6 of Jeon & Van Roy (2022)):
(gs(X) -(X))) $
dx
20
3.3 SAMPLE COMPLEXITY
Our definition of sample complexity is adapted from Definition 4. in Jeon & Van Roy (2022). For any 6 > 0, we defined the sample complexity N, of a training procedure as the minimal number of samples N such that after training N samples, the expected error is at most e:
E (xs -
N, min N
S
20
where S is an iid set of N training samples, and OS is the model trained on this set. Here the expectation is taken over both X and gi this definition of sample complexity captures the expected performance of a training algorithm.
3.4 COMPUTATIONAL COMPLEXITY
We use the total number of queries to the training data points as a proxy for computational com- plexity, which we denote by T. More concretely, if the algorithm is trained n, then the number of queries to training data points would mm. When each data point is queried, it generates forward pass and backward pass. So the actual computation complexity of the algorithm a product of T and a scaling factor that depends on the fitting model size.
batches of size
EXPERIMENT SETUP
In this section we describe how the experiments are conducted. We first describe the experiment pipeline and then discuss the various components.
4.1 EXPERIMENT PIPELINE
The experiment pipeline is outlined in Algorithm 1, and the corresponding code is available on- line (Appendix A). The definition of various parameters and the respective values chosen for the experiments are summarized in Table 1.
Table 1: Summary of Parameters in Experiment
Parameter
Descriptions
Values Chosen
== (d, M, e
Hyperparameters of Teacher
Network
d
Input Dimension Number of Hidden Neurons
{1,2,4, .... 27 128) 21.,,...... = 128]
M
Standard Deviation of Noise
(0.1,0.2)
1 to 0.01 for d, M < 2 =
Target Test Eror
1 to 0.1 for max (d, M) 2 128
N NEW
Number of Samples
Successive powers of two to reach
all target
num trials
Number of trials to run for each configuration
At least 32
To experimentally verify the the dependence of sample and computational complexity on d and
M. generate teacher-networks where d and M increasing powers of two: (d, M)
4

---

end for Under review as a conference paper at ICLR 2022
Algorithm Experimental Data Generation Algorithm
1:
for each data generation hyperparameter y E do for each sample number N E E do
2:
3:
for i [num trials] do
4:
g f ssample_gn))
5:
Sample N i..d. (I1, 22, ..... IN) according to [(,0 La)
6:
vj E [N]. calculate noiseless t g(x;)
Vj E [NV], calculate y/ + f/ noiseless + w/, where wj std N(0
7:
8:
Set S < {xry y;)lā [N])
9:
Ús < train(y, S), logging the number of queries to data points T N,,
Evaluate error according equation
I
(ūs(X) - (x()) Ig.
error
20²
11:
12:
Average experiments: let
Σ 16 [num trials]
error,,, +
error y,NV
num trials
and
Ty, f
Σ
TyN
num trials
<E(num trials]
13:
end for
14:
Calculate Ny.e!
Ny. < min(N E W enror, S {c}
15: end for
21,2,4, .... 128J2. Then, estimate the sample complexity N, for target erro spanning two ders of magnitude (e E 0.1, 0.013) with a training algorithm that automatically tunes the width. samples S of increasing size N until the test error is below the
We run the training algorithm specified c, and set the smallest such as N.. By choosing N to double each time, we estimate N. within factor of 2. The above procedure is performed for noise 0.1 and 0.2; and for each configuration, at least 32 trials are performed to reduce the noise gathered data.
4.2 TRAINING
We split the samples S into internal training set S; and validation set S, using 80/20 ratio. We train sinle-hidden-ii neural networks different widths on S, using golden-section search, and select the model with the best performance the validation set S., Various details are described below.
4.2.1 ARCHITECTURE OF FITTING NETWORK
The fitting network is single-hidden-laye ReLU network. the same the teacher network, but with different widths (number of hidden neurons). No explicit form regularization like dropout weight decay is used.
ze. golden) on widths ranging from 2 to 32 - 8 max(N, vdM + max(d, M)). This maximum width chosen to allow ample over-fitting, considering either the number of provided samples, the architecture of the teacher network. Golden-section search is performed on the logarithm (base 2) of the width, with tolerance set to 0.25. The motivation behind this scheme is get close good width by searching few points. For example, at most 8 steps are needed to search through widths from 2 to 1000 in this scheme (the number of steps is most Infinitial range /toterance) ). We believe that model In(*)
To find the best width, we perform golden-section search
5

---

Under review as a conference paper at ICLR 2022
performance should roughly be unimodal function of width. So golden-section search should find widths near the optimum. The number of queries is the sum of the number of queries for each searched width.
4.2.2 OPTIMIZATION
To train the network, we use Adam (Kingma & Ba, 2015) with respect to L2 loss. Aside from the learning rate, We use the default parameters from the PyTorch implementation (3) = 0.9, B2 = 0.999). As empirical evidence suggests that small batch sizes generalize better (for example, see Keskar et al. (2017)), we set the batch size to 64 for balance between model performance and training speed.
To automatically set the imitial learning rate, we adapt the method first proposed in Smith (2017). We start with a very small learning rate (1e-8) and exponentially increase until the model starts to diverge. We adapt three methods implemented in the fastai library' to estimate the best learning rate 2, and use their medium as the initial learning rate. The queries to the data points in the phase are included in the calculation of T.
During training, we reduce the learning rate by factor of when the validation loss plateaus using ReduceLROnPIate eau from PyTorch (mode='min and patience=12).
We stop training whenever the best validation loss fails to decrease relatively by more than 1% in 24 epochs, and use the model corresponding to the best validation loss. For each fitting network, there a hard cap of 1500 epochs of training, which is typically never reached.
5 RESULTS AND DISCUSSION
5.1 SAMPLE COMPLEXITY
N. against el (right) for the different choices of In Figure 1, we plot eN, against dM (left) and aM noise (a 0.1, 0.2). In these plots, e is the average test error, and N, is the corresponding number of samples provided. Both the horizontal axis and the vertical axis are drawn in log scale, with equal aspect ratio. In all plots, we included scatter plot of the points, and reference line of unit slope in the log plot, which corresponds to linear fit of the data. In the plots on the left, we also plotted lines corresponding to the median, the mean, and the 95 and 5 percentiles. In the plots on the right, we use locally weighted smoothing (Cleveland, 1979) to estimate the trend, and the 95% confidence interval is produced by bootstrap resampling two-thirds of the data.
As we can see in the plots, eN,, is almost proportional to d.M for wide range of d. M. and e. Both Bartlett al. (2019) and Jeon & Van Roy (2022) predict the theoretical sample complexity to be proportional to dMM. up to log factors. So our results indicate that SGI) on neural networks (with automatic width selection) can achieve the theoretical sample complexity of "optimal" learners in the case of single-hidden-laye teacher network.
We note that while the dependence N, on dM is very close to linear for big dMM, the dependence of N. on e -1 is noticeably worse than linear for very small Additional plots of the dependence of Ne on d and M for fixed e can be found in Appendix B.
5.2 COMPUTATIONAL COMPLEXITY
We plot the number of queries T against the number of samples N Figure 2. As the previous plots, both the horizontal and vertical axis are in log scale and have equal aspect ratio. We include reference line of unit slope in the log plot, which corresponds to a linear of the data.
From Figure 2 can see that the dependence of ''' N is slightly less than linear and so T O(N). In the previous section, we demonstrated that Nr, the number of samples necessary to achieve test error within e tolerance, appears to be O dMd) Therefore, Te, the total number of
hhtpp://docs.faa fis
steep,, where the loss as the steepest descent; minimum, for a learning rate 1/20 of where the loss is the smallest; and valley, when the loss is in the middle of its longest valley

---

Under review as a conference paper at ICLR 2022
Unit skppe reference
EN scante
10a
EN mosn
locelyy Weighted Smoothnng
perrentie mecian
80% Corricncce reeeval
Une skope utternce
10"
EN..
101-
10
100.0
1000.0
21
2
2'
28
27
21
21
(a) Sample complexity when 0.1
slope referance
scatter
Locally Waighted Smoothing
95% Confidence Interval Unit slope reforence
AN) percantile
E/V.
00
010
00000 1B0
10
0000
2"
24
21
2
2
0.1 1.0
10.0
100.0
1000.0
6M
c-1
(b) Sample complexity when
Figure 1: Sample complexity is almost linear in dM for wide range of d, M, and is the average test error, and N, is the corresponding sample size. All vertical and horizontal axises are in the log scale, with equal aspect ratio. A unit slope reference provided to indicate a linear relationship in the log scale. For a 0.1 (top), the reference lines correspond to eN, = 1.79dM; for a = 0.2 (bottom), the reference lines correspond to <N. 1.11 The confidence intervals on the right are generated by bootstrap resampling of two-thirds of the data.
queries to datapoints to achieve tolerance, is also approximately proportional to dM This implies that for all N, the average number of times each single data point is queried is bounded above by constant.
In our experiments, the width of the fitting network is O(d + M). Since each query of a data point corresponds to most forward pass and backward pass, the overall computational complexity is O(Nd(d + M)) Od + M)) for fixed e. We hypothesize that by tightening
7

---

Under review as a conference paper at ICLR 2022
the upper bound the fitting network's width to O(M), the current results would still hold, and the corresponding computational complexity could be improved to M2).
sope reforance
siope reference
Tacetter
moan
109
10
100
10.-
107
30
10"
10a
365
161
3 29
27 20
(a) Computational complexity when 0.1
(b) Computational complexity when 0.2
Total number of queries to datapoints is sublinear in sample size. All vertical and hor- izontal axises are in the log scale, with equal aspect ratio. A unit slope reference is provided to indicate a linear relationship in the log scale. For = 0.1 (left), the reference line corresponds to 1940N; for a = 0.2 (right), the reference line corresponds T 1622N. The sublinear relationship indicates that the average number of times each single data point is queried is ((1) for all N.
Figure 2:
COMPARISON WITH EXISTING RESULTS
6.1 COMPARISON WITH THEORETICAL RESULTS
In the case of single- hidden-laye neural networks, both Bartlett et al. (2019) and Jeon & Van Roy (2022) give theoretical upper bounds on the sample complexity that is Ô (N..) ). As for lower bounds on sample complexity, the result in Bartlett et al. (1998) implies the existence of single-hidden-llyer neural networks with sample complexity at least linear the total number weights. However, to the best of our knowledge, there is no tight theoretical lower bound sample complexity when the teacher network is assumed to be drawn from a distribution, and even for single-hidden-lay teacher networks this seems remain open problem.
We empirically demonstrate that for single-hidden-lee teacher networks, running SGD on neural networks with adequate complexity, with very manageable run time the average number of queries per datapoint con- stant. SGD empirically works well in terms of sample and computational complexity in spite of negative theoretical results in the stochastic query framework (Goel et al., 2020; Diakonikolas et al., 2020). The discrepancy between theory and practice best explained by the analysis framework. While Goel et al. (2020); Diakonikolas et al. (2020) analyze the worst case performance of algo- rithms and prove that either sample or computational complexity must be super-poly super-polynomial, our empirical work studies the average performance of SGD. The focus on average case performance also more line with the actual uses of neural networks in practice, people don't necessarily need guarantees that SGD on neural networks works for all datasets, long practical algorithms succeed with high probability.
achieves the best known theoretical bounds sample
Mild constraints imposed the activation functions, Sigmoid, for example, satisfies the constraints.
8

---

Under review as a conference paper at ICLR 2022
6.2 COMPARISON WITH OTHER ALGORITHMS
Zhong et al. (2017); Fu et al. (2020); Janzamin et al. (2015); Ge et al. (2017) all construct algo- rithms to fit single-hidden-layer teacher networks with provable guarantees sample complexity, computational complexity. and emror Here we highlight some differences between their works and ours:
While our results indicate sample complexity linear in number of parameters, the men- tioned works either have high-order polynomial (Janzamin et al., 2015; Ge et al., 2017) or exponential (Zhong et al. (2017); Fu al. (2020), see Appendix D for details) sample complexity.
Our work uses standard machine learning tools (Adam, random weight initialization, early stopping, learning rate decay), while the mentioned works use algorithms not commonly found in practice. Zhong et al. (2017); Fu et al. (2020) uses tensor method to initialize the weights before applying SGD; Janzamin et al. (2015) use tensor factorization, Fourier analysis, and ridge regression instead of SGD; and Ge et al. (2017) designs alternate objective function.
7 CONCLUSIONS
In this work, we empirically demonstrate that to reach a small expected error for single-hiddden-laer teacher networks, SGD with automatic width tuning can nearly achieve theoretic sample complex- ity bounds in computationally efficient manner. This helps bridge gap that previously existed between theoretic sample complexity upper bounds and the absence of algorithms that achieve this upper bound computationally efficiently. In addition, the near optimal sample and computa- tion complexity of SGD on neural networks opens up the possibility of modelling it as an optimal Bayesian learner. We hope that this perspective contributes to the general understanding of performance of SGD on neural networks. Investigating whether our results extend to multiple- hidden-layer teacher networks remains interesting question for future research.
Reproducibility Statement We provide the source code for reproducing the experiments (Ap- pendix A).
REFERENCES
Sanjeev Arora, Aditya Bhaskara, Rong Ge, and Tengyu Ma. Provable bounds for learning some deep representations. In Proceedings of the s1 International Conference International Conference on Machine Learning Volume 32, ICML' 14, pp. 1-584-1-592. JMLR.org, 2014.
Peter Bartlett, Vitaly Maiorov, and Ron Meir. Almost linear ve dimension bounds for piecewise polynomial networks. Advances in neural information processing systems, 11, 1998.
Peter L. Bartlett, Nick Harvey, Christopher Liaw, and Abbas Mchrabian. Nearly-tight ve-dimension and pseudodimension bounds for piecewise linear neural networks. Journal of Machine Learning Research, 20(63):1 2019. URL http: http::/t:pl/../.e/e///m worg/oorrroorrooo/oo/oo//oo http://rrrrrpapppe/eeeeee pwpppss/w.//1-aaapppppp//p
html.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33:1877-1901, 2020.
William Cleveland. Robust locally weighted regression and smoothing scatterplots. Journal of the American statistical association. 74(368):829 829-836. 1979.
Jacob Devlin, Ming- Ming-Wei Chang. Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04805. 2018.
Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, and Nikos Zarifis. Algorithms and SQ lower bounds for PAC learning one- hidden-layer relu networks. CoRR, abs/2006. 12476, 2020. URL
https:/ /ttps: wttp//wwwww.o.a.aaaa/o//ea/aaaae 2006 12476.

---

Under review as a conference paper at ICLR 2022
Haoyu Fu, Yuejie Chi, and Yingbin Liang. Guaranteed recovery of Sone-hidden-laeee neural networks via cross entropy. IEEE Transactions on Signal Processing, 68:3225 -3255, 2020. doi: 10.1 TSP.2020.2993153.
Rong Ge, Jason Lee, and Tengyu Ma. Learning mue-hidden-laye neural networks with landscape design. arXiv preprint arXiv:1711.00 1.00501, 2017.
Surbhi Goel, Aravind Gollakota, Zhihan Jin, Sushrut Karmalkar, and Adam Klivans. Superpoly-
nomial lower bounds for learning one-layer neural networks using gradient descent, 2020. URL https: //ax:iv///vvvv//
org/ abs/ /200 12011.
Steve Hanneke, The optimal sample complexity of pac learning. The Journal of Machine Learning Research, 17(1:1111-1333, 2016.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Majid Janzamin, Hanie Sedghi, and Anima Anandkumar, Generalization bounds for neural networks through tensor factorization. CoRR, abs/1506.084773, 2015. URL htttth//aaaiiiii org/ abs/ 1506. 08473.
Hong Jun Jeon and Benjamin Van Roy. An ihormttnnii framework for supervised learning, 2022. URL https: / arxiv. org/abs/22033 00246.
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Pe- Tang. On large-batch training for deep learning: Generalization gap and sharp minima. In International Conference on Learning Representations, 2017. URL htt tttttt///ppeeeee///// /oppnreview....
net/ forum?oomm Lorpmmmmdddooooooooeooo
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. ICLR (Poster), 2015. URL http:: org/ abs /1e...1111.. 1980..680......
Roi Livni, Shai Shalev-Shwarzz and Ohad Shamir. On the computational efficiency of training neural networks. Advances in neural information processing systems, 27, 2014.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wier- stra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint 13 2013.
Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LeCun, and Nathan Srebro. To- wards understanding the role of ver-paramettriztton in generalization of neural networks. arXiv preprint
2018
Leslie N. Smith. Cyclical learning rates for training neural networks. In 2017 IEEE Winter Con- ference on Applications of Computer Vision (WACV), pp. 464-472, 2017. doi: 10.1109/WACV. 2017.58.
Le Song, Santosh Vempala, John Wilmes, and Bo Xie. On the complexity of learning neural net- works. In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Gamett (eds.), Advances in Neural Information Processing Systems, volume 30. Curran As- sociates, Inc., 2017. URL httttp::///pccceedding htwpreeeeeiinn...eii...eeesee..e httpppp.cc//ppprr/////ieeee a78482ce 7 64 wwf.fff9055555 www9998822900666990 Pape:. pdf.
Leslic G Valiant. A theory of the learnable. Communications of the ACM, (71(): 1984.
V. N. Vapnik and A. Ya. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability Its Applications, 16(2):264-280, 1971. doi: 10.1137/111602. URL https:
Yuchen Zhang, Jason D Lee, and Michael Jordan. 11-regularized neural networks are improperly learnable in polynomial time. International Conference on Machine Learning, pp. 993-1001. PMLR, 2016.
10

---

Under review as a conference paper at ICLR 2022
Table 2: Maximum widths for different number of hidden layers.
Number of hidden layers Maximum width
32 min
Т, VdM + max M))
2
32 + 2 min
2vT, 2/TM + max(d, M)
3
16 + 2 min
2vT,2VdM + max(d, M)
Kai Zhong, Zhao Song, Prateek Jain, Peter L Bartlett, and Inderjit Dhillon. Recovery guaran- tees for one-hidden-layer neural networks. In International conference on machine learning, pp- 4140-4149. PMLR, 2017.
A CODE FOR RUNNING EXPERIMENTS
We anonymously uploaded the source code to https: https::/anonymenr /anonymoonn.o.oooo 4open. sci science// / sample-
md, and will share the git repository upon publication.
B ADDITIONAL PLOTS ON SAMPLE COMPLEXITY
For = 0.1 and = 0.2, we plotted the dependence of N, on d and M for c 1, 0.1, 0.01 (see Figure and Figure 4, respectively). Both the horizontal axis and the vertical axis are drawn in log scale, with equal aspect ratio. The dependence M for different d is shown on the left, and the dependence on for different is shown on the right. use error bars to indicate the range
from max . E -()x 2n
Since only to min N o((x)))) Se}- 20
experiments where the sample size N is power of 2, these two different Ns always differ by factor of
From the plots we can see that the dependence of N, on d eventually becomes linear (unit slope in our plots) for big M. For big the dependence of N, on M eventually becomes slightly worse than linear, but no worse than quadratic (corresponds to slope being 2 in our plots). In addition, these observations hold for that spans more than two orders of magnitude.
C ARCHITECTURE OF FITTING NETWORK
In this section we study how different fitting network architectures influence performance.
C.0.1 NUMBER LAYERS
We study the performance of the fitting algorithm when the number of hidden layers in the fitting network is 1, 2, and When the number of hidden layers is 2 or 3, we the number of neurons in each hidden layer to be the same. In all cases, we use golden-section search to find the best width. The minimal width is 2, and the maximum widths are given Table Again, the maximum width chosen to allow ample over-fitting, considering either the number of provided samples, the architecture of the teacher network.
The results are plotted in Figure 5, and summary statisties shown in Table 3. We see that on average, having only one hidden layer in the fitting network has slightly better performance than having two hidden layers, which in turn has slightly better performance than having three hidden layers. This corresponds well with the idea that the fitting network should have similar architecture the teacher network.
11

---

Under review as a conference paper at ICLR 2022
21
6-1
2
M-]
25
220
d-16
2
M-16
2
17
2
44 17
20
d-64
2
M-54
200
200
2
21
2
20
2
27 27
21
20
27 27
Dependence of N₁ on different
Dependence of Ni on for different
(a) Sample complexity when
2
d=1
2
2
44-2
2
d=16
23h
235
d-12
215
54-32
2
d-64
2
M-54
M-120
2
2
21
230
28
2
20
2
27
27. 21
27
29.29 29
27
Dependence of No.1 on different Dependence No.1 on for different
(b) Sample complexity when 0.1
94-1
275
270
2.0
220
de15
230
56-16
21
d-32
217
M4-2
d-64
M.-44
230
23
$
215
244
21
213
213
212
21
211
210
21
29
21
20
22
2a
2F
Dependence No.01 on M for different d Dependence No.oz on for different M
(c) Sample complexity when 0.01
Sample complexity N. is almost linear d and M for different when 0.1. All vertical and horizontal axises are in log scale, with equal aspect ratio. The error bars indicate that the estimate of the sample complexity N, is within factor of 2.
Figure 3:
C.0.2 WIDTH OF HIDDEN LAYER
In this part, fix the fitting network to have only hidden layer and study the performance of the fitting algorithm for different widths (number of hidden neurons). We use four different schemes select the width of the fitting network, which we describe in Table 4.
12

---

Under review as a conference paper at ICLR 2022
2
d-1
2
Ne1
2
21
21
d-16
200
20
Mm
MmB4
2 2
21
2"
2-
20
22
20
2
2
27
2
27
Dependence of N₂ on different
Dependence of Ni on for different
(a) Sample complexity when
2
d=1
2
Mi
2
54-2
2
d=16
23h
235
d-12
215
94-32
2
d-64
2
M-54
2
2
2
230
28
2
20
2
27
2
2
29.29
27
2
Dependence of No.1 on different Dependence No.1 on for different
(b) Sample complexity when 0.1
94-1
275
270
2.0
220
de1b
14-16
21
d-32
21
M4-2
d-64
M.-44
230
21
$
244
21
233
213
21
211
210
21
29
21
2
2
27
20
21
22
29
Dependence No.01 on M for different d Dependence No.oz on for different M
(c) Sample complexity when 0.01
Sample complexity N. is almost linear d and M for different when 0.2. All vertical and horizontal axises are in log scale, with equal aspect ratio. The error bars indicate that estimate of the sample complexity N, is within factor of 2.
Figure 4:
We set the width tuning scheme the baseline, and plot the relative performance of the other schemes Figure 6, with summary statistics given in Table 5.
The width tuning scheme consistently has the best performance, followed by the 4M and best schemes. The same scheme has the worst performance. These results are consistent with empir- ical observations that preatttrmetinnnooonnn essential in training neural networks (Ge et al., 2017;
13

---

Under review as a conference paper at ICLR 2022
Table 3: Geometric mean and median of test error ratio
Noise
Value
Geometric mean
Median
c
1.22
1.21
σ = 0.1
63/61
1.38
1.39
62/E1
1.14
1.16
0.2
c3/C (1
1.25
1.25
Table 4: Different schemes of selecting the fitting network width.
Name
Description
same
The width of the fitting network is M, same as in the teacher network. The width of the fitting network is 4M, corresponding to 4x over- parametrization.
4M
tune
The width the fitting network is tuned using golden-section search on the logarithm of the width. The range of widths searched is
2, 32 + 8 max(N, VdM + max (d, M))].
best
Use the median of the widths found by the tune method across trials.
Table 5: Effect of different width tuning schemes
Noise
Value
Geometric mean
Median
Esame
Exune
2.77
1.51
σ 0.1
C4M Cuune
1.48
1.38
Cbest/ Cuune
1.59
1.21
Csame Exune
1.97
1.23
0.2
E1M Etunc
1.26
1.18
Cbest/
(tune
1.28
1.10
14

---

Under review as a conference paper at ICLR 2022
6 scattor plot
E5 scatter
Weighted Smoothing
Locally Weighted Smoothing
95% Confidence interval
95% Confidenca
10a
10a
" reference
10
10a
10a
10a
10
102
10
10"
10
10a
G7
2-hidden-lan layer test error.
3-hidden-layer test error.
(a) Effect of number of hidden layers in fitting network when 0.1.
s5' scatter plot
eç' scatter plot
Locally Weighted Smoothing
Locally Weighted Smoothing 95% Confidence interval
95% Confidence interval
10a
62 =21mp(" reference
10a
=2"=et" reference
10a
10:
109
10a
10
10
10P
10
102
10
10P
10"
102
2-hidden-layy test error.
3-hidden layer test error.
(b) Effect number of hidden layers fitting network when a = 0.2.
Fitting networks with single hidden layer perform better than those with multiple hidden layers. We plot the inverse of the test error when fitting network has multiple hidden layers (c," for hidden layers, and Eg for 3) against the inverse of the test error when fitting network has one hidden layer (cT ). All axises are in log scale, with equal aspect ratio. reference line corresponding to equal error is plotted. The region below the line corresponds to single-hidde saggle-hddennllyerr fitting networks having superior performance. The confidence intervals are generated by bootstrap resampling of two-thirds of the data. In all cases multiple-hidden-layee fitting networks perform slightly worse than single-hidders -ideen-layer fitting networks, especially when the test error is small.
Figure 5:
Livni et al., 2014; Neyshabur et al., 2018). Perhaps surprisingly, the performance difference between tune and best also indicates that for optimal performance, the architecture of the fitting networks needs to be tuned to the particular instantiation of the teacher network, not just to its architecture and number of samples.
15

---

Under review as a conference paper at ICLR 2022
Go scatre
Fil sotter
Wenglied broxing (aumoll
55% Corfidene trave
card cance iroea #Camell, reteance
104
12 Kaw
10
06
3
107
10
10
107
10"
100
12
301
same scheme test error.
4M scheme test error.
best scheme test error.
(a) Effect of width of fitting network when 0.1.
Gin sceter 99% Cortiberee maane Gountil vinence
G Molte
Tue scnter Kra co senicc inaval Ggunrg, relernce
05% Cur fidencs Intarva 42) full ratererie
10'
19'
10
L0-
10a-
13
3
300
101
12"1
10-1 15x
10a1
101
10'
10.1
107
same scheme test error.
4M scheme test error.
best scheme test error.
(b) Effect of width of fitting network when 0.2.
Figure 6: The tune scheme has best performance, followed by the best and 4M schemes. The same scheme has worst performance. We plot the inverse of the test error when using different schemes to select the width of the fitting network (cammee e-1 1MM: best) against the inverse of the test error when fitting network automatically tunes its width (Gune). All axises are in log scale, with equal aspect ratio. A reference line corresponding equal error is plotted. The region below the line corresponds to the width tuning scheme having superior performance. The confidence intervals are generated by bootstrap resampling of two-thirds of the data.
D SAMPLE COMPLEXITY IN ZHONG ET AL. (2017); FU ET AL. (2020) FOR IID GAUSSIAN WEIGHTS
The sample and computational complexity of the algorithms in Zhong al. (2017); Fu et al. (2020)
all have a polynomial dependence on a parameter X, which depends exponentially on d and M in our setup.
defined as (TI* o.)/ where (W) is the i-th singular value of the weight matrix W d of the teacher network. Since Zhong et al. (2017) considers teacher networks where the outer coefficients (our 0.) are either 1 or -1, we need to multiply the outer coefficients inside the activation functions. So with our teacher network, W would be d x Gaussian, with variance 1/d, multiplied (with broadcasting) with x M Gaussian, with variance 1/M.
We set d = 2M and plot À versus M for 1000 trials in Figure 7. The vertical axis in log scale, and we can clearly see that À depends exponentially M.
'Zhong et al. (2017) mentions that in the worst case À depends exponentially on the number of hidden units in Remark 4.3.
16

---

Under review as a conference paper at ICLR 2022
median
10
10
1010
10
109
15
20
M
Figure 7: depends exponentially on M when d 2M.
17


Reviews:
[{"review_id": "ox94-byhyLi", "reviewer": "Reviewer_nw89", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper empirically demonstrates that SGD learns single-hidden-layer neural networks with near-optimal sample complexity efficiently which matches the theoretical bound of an optimal learner in JV22, while according to theoretically lower bounds achieving the optimal sample complexity is intractable in the worst case. ", "summary_of_the_review": "The empirically results are solid but not significant enough in my opinion, thus I lean to rejection.", "strength_and_weaknesses": "Strength:\nThe experimental results are solid with adequate details.\n\nWeaknesses:\n1, the title is somewhat ambiguous and over-selling. The scope of experiements is focused on learning single-hidden-layer neural networks, I suggest changing the title to be more specific, for example \"SGD learns single-hidden-layer neural networks efficiently\".\n2, the main result of this paper is empirically showing that SGD learns single-hidden-layer neural networks efficiently. However, this is not surprising because SGD is known to generalize well on large-scale neural networks. Re-showing this phenomenon empirically on toy models doesn't feel interesting to me. It would be interersting to prove it theoretically though.\n\nQuestion:\nCan you give more details on how you generate the parameters of teacher networks? If all the weights are iid Gaussian, is the resulting teacher network still \"random\"? In particular, in the single-hidden-layer setting, there are works on the infinite width limit of such random neural networks. I'm concerned that the empirical results only applies to the class of fucntions \"favored\" by random neural networks, which might be very different from practical fucntions we care about.", "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": "hP3BYjP3m1", "reviewer": "Reviewer_SPUX", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper tries to show that SGD is effective in learning a ReLU teacher network. The results seem to suggest that the sample complexity is linear in input dimension and width. ", "summary_of_the_review": "See above. \n\n\n-----------------------------------------------------------------\nI read authors' response and I will keep my score.", "strength_and_weaknesses": "strength:\n\na) The goal of the paper is well-motived.\n\nweaknesses:\n\na) The title of the paper over claims the purpose of the paper. It only focuses on learning a ReLU teacher network, rather than provides general validation for SGD\n\nb) Even though the current theoretical results only provide worse-case guarantees, I am not fully convinced that the experiments in this paper can illustrate the expected error of an algorithm for the following reasons: i) experiments can only validates some cases and the experiments in the paper are not extensive; ii) there are many versions of SGD, which can hugely affect the results. For example, the paper uses Adam stepsizes, and other stepsize schemes may lead to totally different observationsi. \n\nc)  I also suggest to try networks with more layers.\n\nd) The writing needs improvement. There are same sentences in the abstract and introduction. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "VUsJXIp3bJP", "reviewer": "Reviewer_7vtM", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work fits the single-hidden-layer neural network to data generated by a teacher network with Gaussian parameters. Conclusion is drawn from experimental results that SGD with automated width selection has both sample and query complexity scaling linearly with the input dimension and width, which complies with the information-theoretic sample complexity bounds and is significantly more computationally efficient than the worst-case query lower bound suggests.\n", "summary_of_the_review": "This work focuses on a the open question that how well SGD trains NNs in terms of its sample and query complexity and draws a conclusion matching our expectiaion on empirical performance v.s. theoretical bounds . However, it's heavily limited by the overly simplified NN sturcture and the insufficient insight that could be drawn from the experimets. So I recommand a reject/weak reject.\n", "strength_and_weaknesses": "**Strength**\n- It’s of value to empirically measure both the sample complexity and the iteration complexity for learning with neural network of algorithms as simple as SGD. This work further simplifies the dynamic by running simulations on the data generated from a teacher single-hidden-layer Relu network and learning with a student single-hidden-layer Relu network whose width is automatically chosen. The motivation for this setup is straightforward to bring up the gap between the theoretical worst-case guarantees and the empirical performance in expectation. \n- The results also showcase the efficiency of SGD in training single-hidden-layer NNs, which may applies to NNs with more advanced structures. The experiments are designed in a well-organized way, and so are the results shown.\n\n**Weakness**\nThough many theoretical results were established for single-hidden-layer NNs, and it may be the reason why this work focuses on this simple structure: to directly contrast the results from the theory side and the practice side, results in this work may not bring sufficient insight why SGD trains NNs well  to the deep learning community.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "BDoM1l3GNpd", "reviewer": "Reviewer_CY12", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper empirically studies fitting single-hidden-layer neural networks where data is also generated by single-hidden-layer ReLU teacher networks. This paper demonstrates that stochastic gradient descent (SGD) with automated width selection attains small expected errors for a specific experiment setting.   They finally claim that this result further suggests that SGD nearly achieves the information-theoretic sample complexity bounds.", "summary_of_the_review": "This paper empirically studies fitting single-hidden-layer neural networks where data is also generated by single-hidden-layer ReLU teacher networks. Since there are only some simple experiments for two-layer NN on the synthetic data, this paper would better be viewed as an extended appendix of Jeon &Van Roy (2022). I highly recommend the authors add some theoretical results, even for some special cases.", "strength_and_weaknesses": "Strength:\n1. Well organized, and the message is clear\n2. the explanation of synthetic experiments is comprehensive. I believe that the result is reproducible.\n\nWeakness:\n1. This paper only conducts experiments for a specific case. In particular, they assume that the teacher network has independent Gaussian weights. Therefore, this is only a special case of the ReLU data-generating process.\n\n2. There are no theoretical results. If one wants to claim that SGD can nearly achieve the information-theoretic sample complexity bounds under a certain condition, one would better derive some rigorous upper bound for the proposed algorithm. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject