Loss Landscapes are All You Need: Neural Network Generalization Can Be Explained Without the Implicit Bias of Gradient Descent
Authors: Ping-yeh Chiang
Renkun Ni
David Yu Miller
Arpit Bansal
Jonas Geiping
Micah Goldblum
Tom Goldstein
Venue: ICLR 2023 notable top 25% (2023)
Keywords: generalization
regularization

Abstract: It is commonly believed that the implicit regularization of optimizers is needed for neural networks to generalize in the overparameterized regime. In this paper, we observe experimentally that this implicit regularization behavior is {\em generic}, i.e. it does not depend strongly on the choice of optimizer. We demonstrate this by training neural networks using several gradient-free optimizers, which do not benefit from properties that are often attributed to gradient-based optimizers.   This includes a guess-and-check optimizer that generates uniformly random parameter vectors until finding one that happens to achieve perfect train accuracy, and a zeroth-order Pattern Search optimizer that uses no gradient computations. In the low sample and few-shot regimes, where zeroth order optimizers are most computationally tractable, we find that these non-gradient optimizers achieve test accuracy comparable to SGD. The code to reproduce results can be found at https://github.com/Ping-C/optimizer .

Published as a conference paper at ICLR 2023
Loss LANDSCAPES ARE ALL YOU NEED: NEURAL NETWORK GENERALIZATION CAN BE EXPLAINED WITHOUT THE IMPLICIT BIAS OF GRADIENT DE- SCENT
Ping-yeh Chiang', Renkun Ni', David Yu Miller Arpit Bansal', Jonas Geiping', Micah Goldblum² & Tom Goldstein
University of Maryland, College Park, (pchiang, zn9 zm, dym, bansal01, jgeiping, iigiiing tomg] } (eumd. edu
New York University goldblum@nyu. edu
Max Planck Institute for Software Systems
ABSTRACT
It is commonly believed that the implicit regularization of optimizers needed for neural networks to generalize in the overparameterized regime. In this paper, we observe experimentally that this implicit regularization behavior is generic, i.e does not depend strongly on the choice of optimizer. We demonstrate this by training neural networks using several gradient-free optimizers, which do not benefit from properties that often attributed to gradient-bard optimizers. This includes guess-and-check optimizer that generates uniformly random parame- ter vectors until finding one that happens to achieve perfect train accuracy, and aeroth-order Pattern Search optimizer that uses no gradient computations. In the low sample and few-shot regimes, where zeroth order optimizers are most computationally tractable, find that these non non-gra -rndrrrdiett optimizers achieve test accuracy comparable to SGD. The code to reproduce results can be found btttp:://itthue com wttp:a/occoo/inn//g/eee imiiettiiieeee
INTRODUCTION
The impressive generalization of deep neural networks continues to defy prior wisdom, where over- parameterization relative to the number of data points is thought to hurt model performance. From the perspective of classical learning theory, using measures such Rademacher complexity and VC dimension, as one increases the complexity of a model class, the generalization performance of learned models should eventually deteriorate. However, in the case of deep learning models, we observe the exact opposite phenomenon as one increases the number of model parameters, the performance continues to improve. This is particularly surprising since deep neural networks were shown to easily fit random labels in the overparameterized regime (Zhang et al. 2017). This combi- nation of empirical and theoretical pointers shows large gap in our understanding of deep learning, which has sparked significant interest in studying various forms of implicit bias which could explain generalization phenomena.
Perhaps the most widely-held hypothesis posits that gradient- optimization gives rise to im- plicit bias in the final learned parameters, leading to better generalization (Arora et al., 2019 Advani
al. 2020 Liu al. 2020 Galanti & Poggio 2022). For example, (Arora et al. 2019) showed that deep matrix factorization, which can be viewed as a highly simplified neural network, is biased towards solutions with low rank when trained with gradient flow. Indeed, (Galanti & Poggio 2022) shows theoretically and empirically that stochastic gradient descent (SGD) with a small batch size can implicitly bias neural networks towards matrices of low rank. A related concept was used by (Liu et al. 2020) to show that gradient agreement between examples is indicative of generalization in the learned model.
In this paper. we empirically examine the hypothesis that gradient dynamics is a necessary source of implicit bias for neural networks. Our investigation is based a comparison of several zeroth

---

Published as a conference paper at ICLR 2023
order optimizers, which require gradient computations, with the performance of SGD. We focus our studies on the small sample regime where zeroth order optimizations are tractable. Interestingly. we find that all the gradient-free optimizers we try generalize well compared to SGD in a variety of settings. including MNIST (LeCun et al.) 2010), CIFAR-10 (Krizhevsky 2009), and few-shot problems (Bertinetto et al. 2019; Vinyals et al. 2016).
Even though we use fewer samples in our experiments compared to standard settings, this low-data regime highlights the role of model bias, where the generalization behavior of neural networks is particularly intriguing. The model we test has more than 10, .00 parameters, but it has to generalize with fewer than 1, 000 training samples. Without implicit bias, such feat is nearly impossible in realistic use cases like the ones we consider. Our work shows empirically that generalization does not require the implicit regularization of gradient dynamics, at least in the low-data regime. It is still open question whether gradient dynamics play larger role in other regimes, namely, where more data is available.
We need to caution that we are not claiming that gradient dynamics have no effect on generalization, as has been clearly shown both theoretically and empirically that it has a regularizing effect (Arora jet al. 2019; Galanti & Poggio 2022). Instead, we argue that the implicit regularization of gradient dynamics only secondary to the observed generalization performance of neural networks, at least in the low-data regimes we study.
The observations in this paper support the idea that implicit bias can come from properties of the loss landscape rather than the optimizer. In particular, they support the volume hypothesis for generaliza- tion: The implicit bias of neural networks may arise from the volume disparity of different basins in the loss landscape, with good hypothesis classes occupying larger volumes. The conjecture is empir- ically supported by the observation that even a "guess & check" algorithm, which randomly samples solutions from parameter space until one is found with low training error, can generalize well. The success of this optimizer strongly suggests that generalizing minima occupy a much larger volume than poorly generalizing minima in neural loss functions, and that this volume disparity alone is enough to explain generalization in the low-shot regime.
Finally, show in a previously studied toy example that volume implicitly biases the learned function towards good minima, regardless of the choice of optimizer.
RELATED WORK
The capability of highly overparametrized neural networks to generalize remains a puzzling topic of theoretical investigations. Despite their high model complexity and lack of strong regularization, neural networks do not overfit to badly generalizing solutions. From a classical perspective, this is surprising. Bad global solutions do exist (Zhang et al., 2017; Huang et al.) 2020b), yet usual training routines which optimize neural networks with stochastic gradient descent never find such worst-case solutions. This has led flurry of work re-characterizing and investigating the source of the generalization ability of neural networks. In the following we highlight few angles.
Higg-dimennional optimization Before reviewing the literature on gradient dynamics, we want to review the underlying reasons why gradient- based (first-order) optimization is so central to deep neural networks: The core reasons for this is often dubbed the curse of dimensionality: For arbi- trary optimization problems (with minimal conditions, i.c. (Noll 2014)) a first-order optimizer will converge to local minimal solution in polynomial time in the worst-case, independent of the dimen- sionality of the problem. However, a zeroth order algorithm without gradient information will have to, in the worst-case, evaluate a number of queries that increases exponentially with the dimension- ality of the problem, even for smooth, convex optimization problems (Nesterov) 2004). However as will discuss, neural networks are far from worst-case scenario, given that many solutions exist due to the flatness of basins and the inter-connectedness of minima neural networks.
Gradient dynamics Here we briefly review literature that argues for gradient descent as the main implicit bias for generalization of neural networks. In Liu et al. (2020), they argue that deep net- works generalize well because of the large agreement of gradients among training examples using a quantity called gradient signal-to-noiss ratio (GSNR). They found both empirically and theoreti- cally that a large GSNR would lead to better generalization and that deep networks induce a large GSNR during training, leading to better generalization. Arora al. (2099) show that the dynamics of gradient-based optimization induce implicit bias that is stronger than typical norm- norm-based bias in the setting of deep matrix factorization, and raise the question whether implicit biases can be induced from first-order optimization that cannot be captured by any explicit regularization. Advani et al.
2

---

Published as a conference paper at ICLR 2023
2020) argues that in the overparameterized regime, the gradient dynamics prevent learning from happening in a certain subspace of the weights, which effectively works as implicit regularization. A recent paper by (Galanti & Poggio (022) proves that SGD trained networks have a low-rank im- plicit bias and hypothesizes that such an implicit bias may be the source of superior generalization for deep neural networks.
Non-gradient based explanation of implicit bias Several works have tried to explain the gener- alization behavior of neural networks with other forms of implicit regularization. Neeshabur et al. (215)) argues weight norms to be the main measure of capacity control that allows neural networks to generalize. Keskar et al. (2016) suggests that flatness in the parameter space corresponds to sim- pler functions, thus allowing neural networks to generalize. However, Dinh et al. (2017) later show that when the flatness measure is not scale-invariant, sharp solutions can generalize just as well with appropriate rescaling of the network parameters. Valle-Perez et al. (2018) argue that the parameter- function map is exponentially biased towards simple functions. [aaaaan et al. (2019) shows that neural networks are biased toward low frequency functions that vary globally without local fluctu- ation. Among all works that try to explain neural network generalization, most recent works argue gradient descent or stochastic gradient descent as the main implicit bias of neural network training that allows deep overparameterized networks to generalize.
Volume and Bayesian modeling From a Bayesian perspective, flat minima of the loss surface highly represented in the Bayesian model average, especially when they contain functional diversity (Wilson & Izmailov| (020). The size of posterior peak has also been connected to Occam factors indicating that they represent simpler solutions which are more compressible and generalize well (MacKay et al., 2003). Smith & Le (2017) studies generalization behavior of overparameterized linear models where they find that the Bayesian evidence marginal likelihood, which is connected to generalization, strongly favors flat minima. A line of work on PAC-Bayes generalization bounds, which is related to compressibility and the Bayesian evidence, uses compressibility to guarantee generalization and finds the flat minima more compressible
they yield more bits back from the KL-divergence term in the bound (Dziugaite & Roy| 2017). In contrast to these works, our findings focus not on why flat minima generalize well but rather how their large volume makes them likely to be found by optimizers.
Similar Lines of Inquiry Mingard et al. 2202 empirically show that when sampling from wide networks conditioned on the training set, the sampled models behave similarly to finite width net- works trained with SGD. They approximate the posterior with Neural Network Gaussian Process, which is not exact in finite width networks. Geiping et al. (2022) show that full batch gradient descent, when coupled with explicit regularization can perform comparably to model trained with SGD, thus bringing into question the importance of SGD for generalization. Similar in spirit, we argue that SGD and all gradient-based optimizers are not the main source of generalization behavior of neural networks. Huang et al. (2020a) provide intuitive explanations for the volume hypothesis, and empirically measure the volume of both good and bad minima. While they show that individual good minima tend have much larger volume than individual bad ones, their experiments do not show that the total volume of all good minima is large. Experiments below address this weakness.
3 THE MYSTERY OF GENERALIZATION WITH OVERPARAMETERRIATION
In this section, we illustrate how the complexity of a hy- pothesis class increases with the number of parameters in the context of a simple classification problem. Specifi- cally, increase the number of hidden units of two layer neural network and showcase the increasing com- plexity of the model class. Despite this increased com- plexity, SGD often consistently finds good classifiers. Then, we proceed to show that a similar generalization behavior can be achieved without any gradient dynamics.
We begin with a toy classification problem defined over two classes where the data distribution is a wedge "A" with vertical margin separating the two classes (see Fig- ure D. Throughout this section, our training and testing data consist of 11 points and 5 points, respectively, each sampled uniformly at random.
Figure 1: On the left, we have the true underlying distribution of the toy prob- lem. On the left, we have the sampled training data.
3

---

Published as a conference paper at ICLR 2023
In this figure, show that even though the model becomes much more expressive increase the number of parameters, as shown in the possible decision boundaries the poisoned net- work of various sizes, both SGD) and Guess & Check produce decision boundaries that are relatively stable as we increase the number parameters. From left to right, have decision boundaries pro- duced by 2, 4, 10, 15, 20 hidden units single layer neural networks with different training methods. For each (training method, model size) pair, show 9 randomly sampled decision boundaries of the trained network. showed even more samples the decision boundaries in Appendix A
Figure 2:
(a) Decision boundaries of poisoned neural network
(b) Decision boundaries SGD trained models
(c) Decision boundaries Guess & Check trained models
3.1 OVERPARAAEETERIZATIO INCREASES MODEL COMPLEXITY
To illustrate how the model complexity increases with number parameters, we first poison a model by minimizing the loss on the training data while maximizing the loss on the testing data. Given only examine cases where the model (trained by SGD) achieves 100% training accuracy, this represents the worst-case decision boundary for the unpoisoned loss. As we increase the number of hidden units from 2 to 20, the decision boundary becomes much more ill-behaved (see Figure (2a) When the hypothesis class is restricted to hidden units (the left most plots in Figure 2ah, the model can only fit the data by using a single kink in the decision boundary, so it has to trade off either fitting the training examples to 100% accuracy or performing badly on the poison objective. Given that the model fits training data, it has perform well on testing data. This is consistent with the mnder-parameterizer regime and with classical learning theory.
As increase the model size, the model class contains strange decision boundaries that fit the training data while performing poorly on the testing data. From the perspective of classical learning theory, we would expect models with 20 hidden units to perform much worse than the model with 2 hidden units. Surprisingly, even though as we increase the model size. we never see such boundaries when optimizing the (unpoisoned) training objective with SGD. For example, in Figure 2b as we increase the number of hidden units, the decision boundary remains relatively consistent. Given that both the weird and nice decision boundaries exist in the model class, it is natural to ask what biases the learned network towards good bad optima.
complicated decision boundaries are available
Due to the consistent behavior of SGD trained networks in the overparameterized regime, it only reasonable that people started investigating gradient dynamics as source of implicit regularization (Galanti & Poggio 2022 Arora al. 2019 Advani et al. 2020 Liu et al. 2020). However, show
4

---

Published as a conference paper at ICLR 2023
below that, rather surprisingly. obtain similar generalization behavior the toy problem by using a Guess & Check algorithm that completely free of gradient dynamics.
3.2 GENERALIZING ON TOY PROBLEM WITHOUT GRADIENTS
In our toy setting, we find that generalization is surprisingly generic with respect to the dynamics of optimizers. To avoid using optimizers with the same inductive biases as gradient methods, we experiment with Guess & Check: we repeatedly sample parameters until a model achieves 100% training accuracy with train loss below certain threshold. Unlike other optimizers, we do not use any gradient information, and we also do not take any iterative steps. Surprisingly, even with Guess & Check, we often end up with a well-behaving decision boundary like the one that we trained with regular SGD, see Figure 2c
From the simple two class toy problem, we can see clearly that Guess & Check solutions already endow the learned model with a very strong implicit bias that does not originate from gradient dynamics. In the next section, extend similar analysis common datasets such as MNIST & CIFARIO to see whether this observation continues to hold in more practical settings.
EXPERIMENTS
4.1
NON-GRADIENT BASED OPTIMIZERS
In our experiments, we test three different non-gradient based optimizers: Guess & Check, Pattern Search, and Greedy Random Search varying scales of MNIST & CIFAR-10 and different architectures. Here, we explain each optimizer.
4.1.1 GUESS & CHECK
The Guess & Check algorithm optimizer randomly generates parameter vectors with entries sampled independently and uniformly from [-1, If the randomly sampled model achieves 100% training accuracy and has training loss below a chosen threshold, then the model is kept and the optimizer terminates. If not, the vector is thrown away and we keep guessing new vectors until our conditions are met.
Guess & Check is of theoretical value because its only implicit bias comes from the geometry of the loss landscape, and its success implies the volume hypothesis. With this optimizer, the likelihood that set of solutions are selected is exactly proportional to the volume of the set in parameter space. If a model consistently generalizes well when trained with Guess & Check, then this means the set of " "good"" minima has large volume among low-loss parameters. We do want to make a distinction between flat solutions (Keskar et al. 2016) and solutions with large volumes. It is possible that collection of solutions has a very large volume but is not itself flat basin but rather a collection of many small volume regions that have large volume in aggregate.
When train with Guess & Check, we can be confident that gradient- based implicit regularization plays no role in the final performance - the volume hypothesis is the only source of implicit regular- ization. Unfortunately, Naive guess-anddcheck suffers from the problem that the cost of interpolating the training data grows exponentially the number of training examples or classes increase, so we have restricted experiments with Guess & Check to few-shot problems with smaller sample sizes.
4.1.2 LOCAL NON-GRADIENT BASED OPTIMIZER
Due to the difficulty of scaling Guess & Check to large problems, we explore two alternative non- gradient based optimizers, Pattern Search and Random Greedy Search, that work for bigger datasets. Like SGD, both approaches update the model using local search and may have biases that originate from factors other than volume alone. The success of Pattern Search and Random Greedy demon- strates that gradient optimization is not strictly needed to observe implicit regularization, but they may exploit regularization properties of local search that are also exploited by SGD.
Pattern Search Pattern Search randomly selects a parameter in the model and takes a step of fixed size that is randomly chosen to be either positive or negative, if the model achieves lower loss after
See Appendix C for experiments with other sampling intervals.
5

---

Published as a conference paper at ICLR 2023
Table 2: On the two class MNIST problem, G&C performs comparably to SGD across different train loss level and number of samples. This shows us that despite the large number of parameters, G&C solutions are implicitly regularized. To show that the degree of generalization of G&C is indeed substantial, we train an additional linear model, which has a much more restricted hypothesis class, but has on average 10% worse generalization performance. The empty cells correspond to linear models where we could not find solutions with 100% training accuracy. We also show the estimated standard deviations of the averages computed over 175 random data split and training seeds. For most cells, the standard deviation is less than 1 %.
Sample
Optimiter
Best
(..35.04)
10.5
(0.55
(066
32
LoNet
G&C
95 06.025.66.27%
95.029900.27%
92 92.99
00.5P 34R
BOL1BREBO 58%
87 47.225500.45%
LeNet
5K30
94.008-11
V1.095-0 2916
92 545500 2W9
91 M1.8590 3MS
M1.200--0
LeNei GBC
60.4%%
R0 40.2/9900.4%
$7.015.0 50%
85 B..88 50%
64699A0 54%
$1 91560
76.61 655
LoNei SCID
10.44
91 11344310400 40%
90875
M0.BA 3850
777 48%
RK BL.05LL...00 4.75
60,000 40%
Lineer
5030
M0.655
50.55%
60.55%
7K 78.0095.90.000 506
75, 10.001
72
67 105
69.51
A05
GBC
K305
7756 1999
8198
76
LoNai SCED
64825 10.35
94. 6255 60.6
87.62940
3466
399 72%
79 705 70%
70 70:7450-000 175
7e.55 Mo.519-18 71.5
Lincer
SCID
14.20% 10, 72%
10.772
71 7254 1999
67. 67.799 699
Ter2 765
65 4654 10.79%
$4.655 7.70
54.97% 10.5%%
LaNat
40.05%
72.63 86R
70
27%
65
9258
62.38%
Finar SCED
66 135 40.81%
61 4055-0
67. 07.109--070 PASs
58. 15:154400000 68%
57 211440.911
55, 189 SA1
$1,415-4 8514
2
LeNei G&C
66 66.5%
$6.99811.08 D8%
65 (5.875a11 06%
64.08% 9255
60.91 00%
61 025
59 00
56.8 56.8294n 955
LeNal
(0.77
67. 11.00.99
61.96 95%
877
389
8018
62.33
211400877
51.599831
taking the step, then the parameter is accepted as the new starting point. If Pattern Search fails to find a step that decreases the loss after going through all the parameters, then the step size is decreased by constant factor. We repeat this procedure until solution is found that achieves 100% training accuracy. In our experiments, we use a starting radius of 1, and we decrease the radius by a factor of 2 when it fails to find a descent direction.
Random Greedy Search Random Greedy Search adds Gaussian noise the initial parameter vector with standard deviation of o.. If the noised solution improves training loss, then the noised solution is accepted as new starting point. If no solution is found after fixed number of steps, then o is decreased by a chosen factor before the search continues. Again, we repeat this procedure until a parameter is found that achieves 100% training accuracy. In our experiment, we start the procedure with 1. If we fail to find perturbation that decreases loss after 30000 random steps, then we decrease a by a factor of 2.
4.2 RESULTS ON 2-CLASS CIFAR-10/MNIST
MNIST Samples
CIFAR Samples
Val, Acc.
Val. Acc.
In this section, we apply the Guess & Check algorithm on a conventional LeNet model on MNIST (LeCun et al.) 2010) and CIFAR-10 (Krizhevsky) 2009). Due to the ex- ponential time complexity of the Guess & Check algo- rithm, we stick with 2-class problems with fewer than 32 total training samples. To enable fair comparisons be- tween G&C and SGD optimized models, we compare the performance of the models across different train loss lev- els after the model's weights have been normalized. This crucial for fair comparison because it has been ob- served that lower loss levels corresponds to better gener- alization even after train accuracy has reached 100%.
32
0%
24
0%
16
0%
16
0%
8
0%
8
0%
0%
0%
2
0%
0%
Table 1: Comparing poisoned valida- tion error. In this table, we attempt to fit the training data of various sizes while poisoning LeNet with the wrong vali- dation labels. We find that the LeNet we use is of sufficient capacity that it can completely fit the training data while failing to classify the validation set.
We find that given the same loss level and number of sam- ples, Guess & Check performs comparably to SGD, espe- cially at lower loss levels. In the case of CIFAR-10, Guess & Check even outperforms SGD solutions by a substantial margin. This result is made even more interesting given that the models are capable of pathological overfitting: they are able to completely misclassify the validation set while achieving 100% training accuracy (see Table I..
To illustrate how well G&C performs, we also train a linear model on MNIST for comparison. Even though the hypothesis class is now restricted to only linear solutions, a significantly smaller hypoth- esis class compared to LeNet, the linear model still underperforms the Guess & Check solution on LeNet by more than 10% in many cases. Note that, despite being convex, solutions of the linear problem vary because we use SGD and apply early stopping when the desired loss level is achieved.
6

---

Published as a conference paper at ICLR 2023
Table 3: On the class CIFAR1O problem, G&C performs comparably to SGID across different training losses and numbers of samples. This shows us that, despite the large number of parameters, G&C solutions are implicitly regularized. We do note that G&C in this low data regime consistently performs better than SGD though. We computed the standard deviation over 75 random data splits and training seeds.
Sample Count
Optimizer
Best Test Ace
Train Loes (0.55, 0.57)
(0.57,0.59) 0.59)
(0.59.0.61)
(0.61,0.63
(0.63,0.55)
(0.63, 0.67)
24
G&C
66.59% 7
66.5996 744%
65.91%+40 80%
64.099 64.09% 96%
61 61.08%=00.8%
59.33%%=0.888%
57.18% 89%
SGD
63.169:40.87%
83.76%
62.02%:4 84%
60.74%:+9.73%%
58.21%=a0.75%
67.62%
56.24%
61.10%
61.10%
59.54%
59.21%%=4..0
57.53% 86%
$0.71
55,06% 70%
SGD
58.98%
58.589240.77%
38.98/640.699
57.86%%400.99%
57.11%
56.77% 62%
53.90%:4.550%
8 G&C
57.17%: 9%%
54.39% 80%
53.99% 76%
57.17%:4.. 94%
54.61% 68%
52.66%
60.66%
52.82% 62%
SGD
56.76%:10.115 1%
56.76%k:0.711%
35.02%81.622 62%
54.79%:1..729
54.62% 20.2 68%
53.39% 66%
53.53%
G&C
55.51%:
53.59% 969
52.78%
63%
72%
SGD
13.65%
53.49%%3066885
52. 144500551
53.75%
51.53%% 63%
52.18% 66%
50.44%:10.559
2 G&C
52.39%
51.66%:. 74%%
52, 0..399006775
52.00% 60%
51.37% 56%%
50.01%%:10.715
50.666% 62%
SGD
51, 1995995--005995
+1.93%%-+0.666%
11.399%60004777
51. 9899
51. 10895
50.05%%++0
Table 4: In this table. we trained the same LeNet, but with more examples and more classes. We found that the generalization performance still fairly similar between SGD and alternative zeroth order optimizers that do has timed out, and we failed to find models achieving 100% training accuracy within a reasonable time limit.
any gradient information. The empty cells indicate the experiment
Sample Count
1000
500
300
100
MNIST
SGD
93,46% 11%
90.15% 22%
87.48 % +0.26 %
78.67 % #0.51 %
Pattern Search
93.68 #0.12
90.33% 12%
57.26%%4..30%%
78. 13..43%==044444 46%
Random Greedy
93.34%%+4.08$
90.35%=4.110 %
87.33%:+0.2199
78.51 78.51%%+0.50%
CIFAR-10
SGD
36.01 40.255%
29,91 40.311
25.88 30.34%
19.86%+40.27% %
Pattern Search
30.00%+0.699 %
25.04%:40.66
18.70% 1.22%
Random Greedy
34.44%:+0.54%%
27.06%:+0.75%
24.04%
100%
Even though the number of samples is small, we do note that this regime highlights the effects of overparametrization. For example, in our LeNet for MNIST, we have 11074 parameters, which is orders of magnitude larger than the number of examples. Yet the model continues to generalize well relative SGD, showing that the large volume of the good solution set is its own enough to bias the optimizer towards favorable generalization.
Even though the generalization performance is similar between the SGD and G&C solutions, we do note that the test accuracies are not exactly the same between models trained with both methods, im- plying that SGD may have additional bias that G&C does not take into account. However, our main argument is that optimizer-specinn be the primary cause of generalization behavior; our experiments here, the bulk of generalization can be explained by the geometry of the loss landscape.
bias is not needed to explain generalization, and may not even
4.3 RESULTS ON 10-CLASS CIFAR-IO/MNIST
In this section, we evaluate the importance of gradient-based optimizers in the setting where more classes are involved. However, the Guess & Check algorithm is no longer feasible due to the expo- nential time complexity. Instead of Guess & Check, we employ Pattern Search and Greedy Random Search to evaluate the dependence of generalization on gradient based optimizers. Again, we find that these non-gradient based optimizers offer similar levels of generalization benefits SGD de- spite not using any gradient information at all.
In Table we see that Greedy Random Search and Pattern Search both generalize comparably SGD. The average performance difference only 0.9% across different sample sizes, datasets, and optimizer combinations. In several cases, Pattern Search even performs better than SGD. Even though 0.9% may seem large when viewed from the perspective of achieving oftee-of-the-rr accu- racy, we note that a performance difference of 0.9% within the margin that can be expected from hyperparameter tuming, and that we have not tuned either of the zeroth order optimizers, and yet they still achieve comparable level of generalization to SGD.
7

---

Published as a conference paper at ICLR 2023
Loss Level
width
0.35)
(0.35, 0.4)
(0.4, 0.45)
(0.45, 0.5)
(0.5, 0.55)
(0.55, 0.6)
(0.6. 0.65)
Ia
n/a
92.11%
93.44%8anaa
0.9
n/a
m/a
m/a
m/a
90.89%
86.33%%
90.9009=::3033%
0.8
Iiaa
m/a
93.34%
33.89%8889977
93. 33.29%
81.94%=77335%
0.7
97.73%
95. 05.20%==04425
02.30%==1122
80.5996422.90
877.37%
0.6
91 20% 40%
89 66%66 88%
87. 87.76% 222
14.4%%=2.07775 07%
83.64 78%
82. 82.76% 33%
79.4 79.43% 3.6%%
0.5
89.21 -9.211%-044775 47%
87.01%%=0.500
15.18%6=0
64.69%
81.91%:=0
78 78.615:
15.3755==06334
0.4
82% 53%
83.78%%00.61 61
81.43%=00.614
79.63%=00.65%
57,50% 64%
75 75.98%%=0.66 66%
72.30%++ 77%
0.3
79.55%
60%
79.13%=20.60%
76.63%%=00.22%
75.43%%20.63%%
74, 74.22%
0.72%%
71.75%
0.2
77. 17.39%:=0.56%%
76.08%::0.33%
74.70%==0.56%
73.40%22.660%
71.84%
69 60.66%%=0.644
68. 68.49%%=00588%
Table 6: Performance of G&C on MNIST with 16 samples as we scale up the model. The n/a indicates that a model has not been found for the cell.
4.4 FEW-SHOT LEARNING WITH RESNETS
In this section, we evaluate the importance of gradient-basee optimizers in the few-shot setting. This setting enables us to compare gradient methods to zeroeth order optimization using industrial- scale models. For the most part, we find that the gradient-free Pattern Search optimizer performs comparably to SGD in the 1-shot setting.
Few-shot learning is usually used to test the ability of models to generalize to unseen tasks given limited training examples. This is a perfect evaluation task for our hypothesis for the following reasons: First, in few-shot learning, we only use or 5 training images per class during the evaluation stage, which makes zeroth order optimization possible. Second, few-shot learners usually utilize pre-trained feature extractor on the base classes, and only learn a new classification head by SGD or other solvers such as SVM and ridge regression (Lee et al. 2019; |ertinetto et al., (2019) given the unseen tasks. This setting limits the dimension of learnable parameters, thus making training deeper networks such as ResNet possible with these non con-gradient based optimizers. Finally, although we only attempt to learn a single layer, due to the few training examples (1 or 5 per class), we will still have an overparameteriiee model, which is the setting we are interested in.
We evaluate the effectiveness of non-gradient CIFAR-FS (Bertinetto ct al. 2019) and mini-ImageNNet (Vinyals et al.) 2016 with ResNet-12, a commonly used archi- tecture in the few-shot classification literature. During the training stage, we pre-train a fea- ture extractor on the base classes and evaluate the generalization on unseen tasks via 1-shot- 5 5-way episodes, where each episode is a 5-way classification problem and each class contains training image. During the evaluation stage, given the unseen episodes and pre-trained fea- ture extractor, we learn new classification head with a specific optimizer and evaluate the performance on the testing images. We compare the testing accuracy on 600 different episodes be- tween SGD, and Pattern Search in Table 5] For Pattern Search, instead of stopping optimization immediately after fitting all the training examples, we keep updating the model until / steps, where set 3000 for both CIFAR-FS FS and mini- mine-lmageNNe. As showed in Table 5] Pattern Search always outperforms SGD by a large margin, i.e., over 2% for both CIFAR-FS and mini-ImageNNt, which suggests that gradient-based optimizers are not necessary in the few-shot setting.
based optimizers
Table 5: 1-shot-5-way classification performance on both CIFAR-FS and mini-ImageNet with ResNet-12 backbone. We provide mean test ac- curacy over 600 episodes and the one standard er- ror. Compared to SGD, Pattern Search can always achieve better performance by a large margin.
Optimizer
CIFAR-FS
mini-ImageNNt
SGD Pattern Search
68.35 + 0.46
55.76 + 0.42
70.25 + 0.45
58.53 + 0.41
5
HOW DOES G&C BEHAVE AS WE SCALE UP THE MODEL?
People have observed that increasing the size of neural networks trained with SGD can lead to either double descent behavior Nakkiran et al. (202T) or increasing performance| (arrmanne/KKalann et al. (2020). This phenomenon has been previously attributed to the regularization effect of SGD. However, given the similarity of performance between G&C models and SGD-trained models,
natural to ask whether we observe similar behaviors in G&C models as we increase the number of parameters. Here, we show that G&C models continue to improve
increase their size, without using SGD.
8

---

Published as a conference paper at ICLR 2023
To investigate this further, conducted experiments 2-class MNIST using G&C with varying widths of LeNet (Table Surprisingly, we found that as we increased the width the model, its validation accuracy also incressed. This observation contradicts generalization theories based on model capacity, which suggest that increasing model size beyond certain point leads to overfitting and reduced generalization performance.
The observation points to the hypothesis that increasing the width of neural network can expand the volume of the good function class. If we can identify the specific function within this class that experiences an increase in volume with more parameters, it may be possible to achieve similar benefits with smaller model that captures the favorable properties of the function. This could lead to more efficient and effective deep learning models that perform better without unnecessary parameter bloat. However, further research is required to investigate this hypothesis and identify the specific functions that contribute the observed increase in volume.
A TOY EXAMPLE: SIMPLICITY BIAS MAY ORIGINATE FROM THE VOLUME BIAS AS OPPOSED TO SGD
In this section, we study whether volume may explain the simplicity bias previously observed in
Shah et al. (2020).
While we have mostly measured bias terms of generalization in this paper, we think it is promising future direction to quantify whether other forms of bias can be attributed to the volume hypothesis instead. One example is simplicity bias, where trained neural networks strongly prefer linear decision boundaries com- pared to robust ones. We provide toy illus- tration on why this may be attributed to the vol- ume hypothesis, but leave further exploration of this as future work.
Consider the following example: a trained neu- ral network the slab dataset ignores the more complex y-axis, as shown on the left of Figure 3. and uses linear decision boundary drawn along the x-axis only opposed to the robust decision boundary shown on the right of Fig- ure 3 While Shah et al. (200)) has attributed the simplicity bias in this example to SGD, we found that the simplicity bias may simply orig-
Figure 3: The volume of the decision boundary on the left measured by G&C is 10-4 whereas the volume of the robust/complex decision bound- ary has volume smaller than 10 10-10, The large volume disparity may explain trained network's strong preference for the linear solution.
inate from the large disparity in volumes between the linear and robust functions in the loss land- scape. In fact, when we used G&C to measure the volume of the two respective decision boundaries in the parameter space, we found that the linear decision boundary has volume that is 6 orders of magnitude larger than that of the robust decision boundary. Specifically, of the solution by taking the reciprocal of the number of guesses before solution obtained. The volume disparity may explain why the simple decision boundary is strongly preferred compared to the alternative.
estimate the volume
7 CONCLUSION
In this paper, we empirically show that srudient-based implicit regularization of training dynamics not required for generalization. Instead, we consider non-gradient optimizers that lack gradient dynamics, yet still perform well. The strong performance of gradient-free optimizers, in particular Guess & Check, strongly suggests that the disparate volume of good and bad hypothesis classes is the main implicit bias that enables these optimizers to succeed. For future work, we think more critically examining the role of volume as implicit bias in neural networks will be fruitful and interesting direction.

---

Published as a conference paper at ICLR 2023
8 REPRODUCIBILITY STATEMENT
We ran all the experiments with prespecified random seeds, so all of the tables will be reproducible by running the respective scripts in our included code base.
ACKNOWLEDGEMENTS
This work was supported by the ONR MURI program, the National Science Foundation (IIS- 2212182), the AFOSR MURÍ Program, DARPA GARD (HR00112020007), and the Office of Naval Research. Further support was provided by Capital One Bank.
REFERENCES
Madhu S. Advani, Andrew M. Saxe, and Haim Sompolinsky. High-dimensional dynamics of gener- alization enror in neural networks. Neural Networks, 132:428 2020. ISSN 0893-6080. doi:
https://doi.org/10..n h1wp::00000000mmmueee0.........0 022. URL httpt:ttt///tt ttttsspsss /www. scwensedieeeccccte.cee.ce.. com/
Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep ma- trix factorization. In H. Wallach, Larochelle, Beygelzimer, d'Alché-Buss Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32, Curran As- sociates, Inc., 2019. URL E0079bbFcccrT8001111166662222222 Pappaaadee.aaeeeeeeeeeeeee...eer
wew.:eeeeediinnnnnnee.eeee...eee neurips http:/ccc.//pppe///1///eee
Luca Bertinetto, Joao Henriques, Philip Torr, and Andrea Vedaldi. Meta-learning with differen- tiable closed-form solvers. In International Conference on Learning Representations, 2019, URL
https: http:///pppreeee.../mmmm net/ forum? iid- Hyxnhhocthhccc
Laurent Dinh, Razvan Pascanu, Samy Bengio, and Yoshua Bengio. Sharp minima can generalize for deep nets. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Muchine Leurning Reseurch, pp. 1019-1028. PMLR, 06-11 Aug 2017. URL https: pttpps://proceecing: mlr wtt.
dinhl 7b. html
Gintare Karolina Dziugaite and Daniel M. Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. CoRR, abs/1703.11008. 2017, URL
/ttpss///axxv..rrg// abs / 0///17733.111 11008
Tomer Galanti and Tomaso Poggio. Sgd noise and implicit low-rank bias in deep neu-
ral networks. 03/2022 2022. URL https: cttp//cccmmcmcc/m////// mit http://tttmmm...u....ta.aaaatttt wwwpbbll.l.bbl.at...to cwwpiiicciins//////c
sgd www.noniieeeaeee and implimciiii low rank bias deep neural neural-networkss networks
Jonas Geiping, Micah Goldblum, Phil Pope, Michael Moeller, and Tom Goldstein.
Stochastic train-
ing is not necessary for generalization. In International Conference on Learning Representations, 2022. URL htllattts//opeeeeiiieet
Seriidz-BB-S-e ZBESe IUB5K
W Ronny Huang, Zeyad Emam, Micah Goldblum, Liam Fowl, Justin K Terry, Furong Huang, and Tom Goldstein. Understanding generalization through visualizations. 2020a.
W. Ronny Huang, Zeyad Emam, Micah Goldblum, Liam Fowl, Justin K. Temry Furong Huang, and Tom Goldstein. Understanding Generalization through Visualizations. 11X.v21906.03297 [cs, stat], November 2020b. http://///aa
org/ 1966.777 03291
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprint arXiv:2001.0836/ 2020.
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Pe- ter Tang. On large-batch training for deep learning: Generalization gap and sharp minima. CoRR, abs/1 Abs/1600.048338 2016. URL htt.htt::/// /ttp://axvvvv//am wrg./oorrrrooooooo (0obs/1169.... 00096043666606 04836
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, 2009.
10

---

Published as a conference paper at ICLR 2023
Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. ATT Labs [Online). Available: htlp://yann.lecee lecun. wwt./xdd////isst........ 2, 2010.
Kwonjoon Lee, Subhransu Maji, Avinash Ravichandran, and Stefano Soatto. Meta-learning with differentiable convex optimization. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 10657-10665, 2019.
Jinlong Liu, Yunzhi Bai, Guoqing Jiang, Ting Chen, and Huayan Wang. Understanding why neural networks generalize well through gsnr of parameters. International Conference on Learning Representationss 2020. URL http::ttttpppssteeeeeeeee http:///ppp.e....///mm net Eorum?ic-Hyev
David IC MacKay, David JC Mac Kay, et al. Information theory, inference and learning algorithms. Cambridge university press, 2003.
Chris Mingard, Guillermo Valle-Pérez, Joar Skalse, and Ard A. Louis. Is sgd a bayesian sampler? well, almost. Journal of Machine Learning Research, 22(79):1-64, 2021. URLhttpp://mml:
org/ paapassww2//00-m ht.ll
Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and Ilya Sutskever. Deep double descent: Where bigger models and more data hurt. Journal of Statistical Mechanics; Theory and Experiment, 2021(12) 2021.
Yurii Nesterov. Introductory Lectures on Convex Optimization, volume 87 of Applied Optimization. Springer US, Boston, MA. 2004. ISBN 978-1-4613-46911 978-1-4419-8853- URL httt::
Srinnkssrringer com/ 10. 1117777778--444--85--
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks. In Conference on Learning Theory, pp. 1376-1401. PMLR, 2015.
Dominikus Noll. Convergence of non-smooth descent methods using the Kurdyka- Hurddya->Lojasiewiike Lojasiewicz inequality. Journal of Optimization Theory and Applications, 160(2):553-572, 2014. URL http:://ima http:///inkk.sringrrr..... com/ wwt.a//eeee...1////11.00..
Nasim Rahaman, Aristide Baratin, Devansh Arpit, Felix Draxler, Min Lin, Fred Hamprecht, Yoshua Bengio, and Aaron Courville. On the spectral bias of neural networks. In International Confer- ence on Machine Learning, pp. 5301-5310 PMLR, 2019.
Harshay Shah, Kaustav Tamuly, Aditi Raghunathan, Prateek Jain, and Praneeth Netrapalli. The pitfalls simplicity bias in neural networks. Advances in Neural Information Processing Systems, 33:9573-9588 9585, 2020.
Samuel L Smith and Quoc V Le. A bayesian perspective on generalization and stochastic gradient descent. arXiv preprint 17xiv:/700066455 2017.
Guillermo Valle-Perez, Chico Camargo, and Ard A Louis. Deep learning generalizes because the parameter-function map is biased towards simple functions. arXiv preprint 2018.
Oriol Vinyals, Charles Blundell, Timothy P. Lillicrap, Koray Kavukcuoglu, and Daan Wierstra.
Matching networks for one shot learning. CoRR, abs/1606. (tls/1606004000, 2016. Uttp:t/://arxi:
orq/abs/1605, 04080
Andrew G Wilson and Pavel Izmailov. Bayesian deep learning and a probabilistic perspective of generalization. Advances in neural information processing systems, 33:4697747708 2020.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. International Conference on Learning Represen- tations (ICLR) 2017, 2017. URL https: attips://penrevieew..ee hot.://ww.eetttooommmmmoooysssga
11

---

Published as a conference paper at ICLR 2023
A
ADDITIONAL EXPERIMENTS FOR TOY EXAMPLES
(a) Decision boundaries of poisoned neural network
(b) Decision boundaries of SGD trained models seed 0
(c) Decision boundaries of Guess & Check trained models seed 0
12

---

Published as a conference paper at ICLR 2023
(a) Decision boundaries of poisoned neural network seed
(b) Decision boundaries of SGD trained models seed
(c) Decision boundaries Guess & Check trained models seed
(a) Decision boundaries of poisoned neural network sced
(b) Decision boundaries of SGD trained models seed 2
(c) Decision boundaries Guess Check trained models seed
13

---

Published as a conference paper at ICLR 2023
(a) Decision boundaries of poisoned neural network seed
(b) Decision boundaries of SGD trained models seed 3
(c) Decision boundaries Guess & Check trained models seed
14

---

Published as a conference paper at ICLR 2023
(a) Decision boundaries of poisoned neural network 32 samples
(b) Decision boundaries of poisoned neural network 64 samples
(c) Decision boundaries of SGD trained models 32 samples
(d) Decision boundaries of SGD trained models samples
(e) Decision boundaries of Guess & Check trained models 32 samples
(I) Decision boundaries of Guess & Check trained models 64 samples
Figure Decision boundaries as we increase the number of samples
15

---

Published as a conference paper at ICLR 2023
B INFLUENCE OF SAMPLING RANGE FOR GUESS & CHECK OPTIMIZER
Loss Level
L. Norm
(0.3, 0.35)
(0.35. 0.4)
0.44.
0.45)
(0.45, 0.5)
(0.5, 0.55)
(0.55, 0.6)
(0.6. 0.65)
Uniform (-1.1)
93.02%
92.39 %
90.59%
89.18%
87.22%
86.23%
83.15%
Uniform (-2.2) 120
92.52%
90.16%
89.06%
89.89%
87.89%
85.17%
82.17%
Unilurm (-5,5)
300
92.79%
92.04%
91.18% %
87.59%
87.16%
86,42%
82.40%
Sphere
100
92.87%
92.20%
89.79%
89.84%
87.91
86.70%
82.81 %
Table 7: Comparing performance of models given different sampling methods on MNIST with 24 samples. We tested uniform sampling between (-2, 2) and (-5, 5). We also tested sampling from sphere with L2 norm of 100. For the most part, we found that the sampling range does materially change the performance the model.
Loss Level (0.55, 0.57)
L. Norm
(0.57, 0.59)
(0.59, 0.61)
(0.61, 0.63)
(0.63, 0.65)
(0.65, 0.67)
Uniform (-1.1)
60
66.59%
65.91 %
64.09%
61.08%
59.33%
57.18%
Unifarm (-2,2) 120
65.93%
65. 14%
64.93%
61.31%
61.85% %
57.22%
Uniform (-5,5)
300
67.63%
61.69%
63.63%
62.19%
60.33%
58.41%
Sphere
100
61.81%
64.31%
59.30%
62.01%
56.72%
60.77% %
Table 8: Comparing performance of models given different sampling methods on CIFAR with 36 samples. We tested uniform sampling between (-2, 2) and (-5, 5). We also tested sampling from sphere with C2 norm of 100. For the most part, we found that the sampling range does not materially change the performance of the model.
16


Reviews:
[{"review_id": "nRDoRihfPW", "reviewer": "Reviewer_qbak", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper challenges the folk wisdom shared by many works in the deep learning literature that neural networks generalize well due to the bias induced by the optimization algorithms we use to train them. It argues instead that the mapping between parameters and functions in neural networks is biased such that the set of solutions which generalize well has greater volume than the set of those which generalize poorly. The paper evaluates this hypothesis by comparing the performance and qualitative simplicity of solutions found by gradient descent with a number of zeroth-order optimizers, finding minimal difference between the two sets of solutions.", "summary_of_the_review": "This paper presents an intriguing investigation into whether the good generalization properties of neural networks can be attributed solely to the implicit bias of SGD, or whether it might come from the bias of the network architecture itself towards simple functions. The experiments are clearly described and provide surprising and compelling results. While the paper could position itself better relative to prior work which also discusses the bias of the parameter-function map of neural networks, the contribution presented here is still of interest in its own right. ", "strength_and_weaknesses": "I thoroughly enjoyed reading this paper. It is well-written, the hypothesis and evaluation methods are clear, and it questions a widely-held belief that had previously not been rigorously tested (at least, not to my knowledge). \n\nI think the principal strength in the paper comes from its evaluation of zeroth-order optimizers, both in terms of the decision boundary they induce and in terms of the generalization performance of the solutions found by these optimizers. The set of algorithms considered provide a spectrum between brute force search and gradient descent, meaning that if there had been a bias induced by gradient descent in these settings we might have expected to see a dose-response effect wherein the more gradient-like zeroth-order optimizers might exhibit better generalization or a stronger inductive bias than the guess-and-check approach. \n\nGiven the computational complexity of training larger networks with zeroth-order optimizers, I thought the paper did a good job of constructing a set of evaluation benchmarks of varying complexity in both the network and dataset size. For example, the paper evaluates the (relatively, compared to the 20-hidden unit models of section 3.2) large LeNet architecture on a significantly reduced MNIST task in order to be able to evaluate the guess and check algorithm on a high-dimensional parameter set.\n\n\nThe paper has two main weaknesses that I would like to see addressed. \n\n1. The story told by the related work section is somewhat over-simplified. While much of the deep learning literature focuses on inductive bias of gradient descent and its influence on the flatness of minima, the Bayesian machine learning literature has historically taken the perspective that flat minima are good _because_ they correspond to a larger volume of parameter space. See, for example, the work of Smith et al. [1] which illustrates the connection between the existence of flat minima and the Bayesian model evidence. Further, prior works [2, 3] have studied the bias of the mapping between parameters and functions in neural networks in order to explain generalization. This somewhat reduces the novelty of the perspective taken by this paper, though I still think the analysis and experiments provided here are compelling in their own right. I recommend the authors include this discussion in the related work section to accurately position the contribution of this paper.\n\n2. The main limitation of this work is that, understandably due to the computational complexity of zeroth-order optimization, it is not able to study the scaling behaviour of neural networks. As a result it is difficult to be confident that the findings on the bias towards simple functions observed in the small networks studied in this paper is replicated in the larger networks seen in practice. For example, it might be the case that larger networks exhibit a greater volume of poorly-generalizing minima, but that the inductive bias of SGD in these networks is enough to avoid finding them. I would be interested in seeing, potentially in the LeNet architecture on the small subset of MNIST, whether scaling the width improves or reduces generalization performance. It would be particularly interesting to me to see whether Guess & Check exhibits a similar double descent phenomenon as SGD\n\n\n[1] “A Bayesian Perspective on Generalization and Stochastic Gradient Descent” Smith et al., ICLR 2018.\n\n[2] “On the Spectral Bias of Neural Networks.” Rahaman et al., NeurIPS 2019.\n\n[3] “Deep learning generalizes because the parameter-function map is biased towards simple functions” Guillermo Valle-Perez, et al., ICLR 2019.", "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": "Jq7d_Mc_S-", "reviewer": "Reviewer_rv2f", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes empirical results showing that, when training neural networks, gradient-free optimization methods lead to generalization results comparable to the SGD. So, the \"implicit bias\" effect, supposed to be specific to the SGD method, should be reconsidered.\n\nSpecifically, the authors propose to compare the SGD with 3 other methods:\n1. *Guess & Check*: sample randomly the vector of parameters $\\theta$, then select the best-performing one (in terms of training loss);\n2. *Pattern Search*: at each training step $\\theta_t$, select a random direction in the space of parameters, make a step $\\delta$ (with given size) in this direction, measure the training loss at this new point $\\theta_t + \\delta$, then let $\\theta_{t+1} = \\theta_t + \\delta$ if the loss decreases else let $\\theta_{t+1} = \\theta_t$;\n3. *Random Greedy Search*: same as 2, but with random step norm: $||\\delta|| \\sim |\\mathcal{N}(0, \\sigma^2)|$.\n\nIn methods 2 and 3, the step size decreases when too many steps have been attempted without decreasing the training loss. ", "summary_of_the_review": "This paper sheds new lights to the \"implicit bias\" phenomenon: the authors have obtained similar generalization results for their gradient-free algorithm and for the SGD. This result should help researchers to understand how generalization works in NNs. But the use of methods 2 and 3 (close to the SGD) is not convincing or even discussed. Section 5 could be largely improved.\n\nEDIT: I acknowledge the improvements done by the authors (mainly in Section 5), so I raise my score.", "strength_and_weaknesses": "## Strengths\n\n* This paper challenges a widely spread hypothesis: the generalization power of NNs is due to the \"implicit bias\" of gradient based methods (e.g., the SGD).\n* The comparison between NNs trained by SGD and generated by \"Guess & Check\", is convincing. \n* More specifically, the \"Guess & Check\" method is non-local, that is, the best vector of parameters is generated by random sampling over the parameter space, and not by refinement of a candidate vector of parameters.\n\n## Weaknesses\n\n* Methods 2 and 3 are very close to the SGD. So, in order to make claims in these cases, it is necessary to have a discussion about this closeness.\n* The argument about the volume of a subset of models in the whole model space (see Section 5) is not convincing. Some properties should have been added to the proposed model to make the analogy with NNs more credible.\n* Some figures are heavy (slow to load in a PDF reader), and some are unusable when printed in black and white.", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "DhSeB2FW9K", "reviewer": "Reviewer_Qs6Q", "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": "", "summary_of_the_paper": "This paper considers the hypothesis that the good empirical generalization of overparameterized models (neural networks in particular) may not be primarily due to an implicit bias of the optimizer (e.g. SGD), as proposed previously. \nInstead, it argues that the volume in parameter space of good solutions (generalizing well) is much larger than the volume of bad solutions (generalizing poorly).\nThe hypothesis is tested by using three optimization algorithms: \"Guess and Check\", \"Patern Search\", \"Random Greedy Search\".\nIt is shown that those algorithms do not perform significantly worse than SGD on some toy datasets, MNIST and CIFAR.\n\n", "summary_of_the_review": "The hypothesis stated in this paper is very interesting and deserves attention. \nHowever, this paper falls short in properly testing it.\n", "strength_and_weaknesses": "Strengths:\n- New and interesting hypothesis that, when properly tested, may attract several investigators towards more useful research directions.\n\nWeaknesses:\nUnfortunately the hypothesis has not been tested properly, in my opinion.\n\n- Of the three algorithms, only \"Guess and Check\" is appropriate for testing the hypothesis. \nThe other two algorithms (\"Patern Search\" and \"Random Greedy Search\"), while they do not require gradient computation, are not fundamentally different from gradient descent since they seek to minimize the loss in a local neighborhood at every step.\nTherefore, for the purpose of testing the hypothesis, the results of those two algorithms are irrelevant.\n\n- About the \"Guess and Check\" algorithm, I consider it strongly limitated by the bounded interval [-1,1] on which values are sampled.\nOnly small values of parameters are sampled, therefore the resulting solutions are implicitely regularized by the scale of parameters.\nIn other words, the results shown in this paper can be easily explained by noting that smaller values of parameters tend to generalize better, an observation that is well known.\n(THIS POINT WAS FULLY ADDRESSED DURING REBUTTAL)\n\n- Section 5 is trivial.\nThe quadratic problem does not contribute in testing the hypothesis of this paper, it is constructed artificially to have larger volume for linear models, but we cannot say anything about whether other, more interesting problems display similar phenomena.\nThe slab dataset is slightly more interesting but it is not explained how to compute the volume of solutions in that case.\n\nMinor:\n- Linear models usually have unique solutions, however table 1 suggests that multiple solutions can be found with different train loss.\nHow can that be?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "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: Accept: notable-top-25%