A Theoretical and Empirical Model of the Generalization Error under Time-Varying Learning Rate
Authors: Toru Makuuchi
YUSUKE Mukuta
Tatsuya Harada
Venue: ICLR 2022 Submitted (2022)
Keywords: deep learning
generalization error
stochastic gradient descent
functional form
hyperparameter
batch size
learning rate

Abstract: Stochastic gradient descent is commonly employed as the most principled optimization algorithm for deep learning, and the dependence of the generalization error of neural networks on the given hyperparameters is crucial. 
However, the case in which the batch size and learning rate vary with time has not yet been analyzed, nor the dependence of them on the generalization error as a functional form for both the constant and time-varying cases has been expressed. 
In this study, we analyze the generalization bound for the time-varying case by applying PAC-Bayes and experimentally show that the theoretical functional form for the batch size and learning rate approximates the generalization error well for both cases. 
We also experimentally show that hyperparameter optimization based on the proposed model outperforms the existing libraries.

Under review as a conference paper at ICLR 2022
A THEORETICAL AND EMPIRICAL MODEL OF THE GENERALIZATION ERROR UNDER TIME- VARYING LEARNING RATE
Anonymous authors Paper under double-blind review
ABSTRACT
Stochastic gradient descent is commonly employed as the most principled opti- mization algorithm for deep learning, and the dependence of the generalization error of neural networks on the given hyperparameters is crucial. However, the case in which the batch size and learning rate vary with time has not yet been analyzed, nor the dependence of them on the generalization error as a functional form for both the constant and time- varyyng cases has been expressed. In this study, we analyze the generalization bound for the time-varying case by applying PAC-Bayes and experimentally show that the theoretical functional form for the batch size and learning rate approximates the generalization error well for both cases. We also experimentally show that hyperparameter optimization based on the proposed model outperforms the existing libraries.
INTRODUCTION
While deep learning addresses a variety of practical tasks, the reason deep learning generalizes well not fully understood. is hoped that the performance of deep learning methods can be improved by understanding deep learning. Consequently, deep learning will become cornerstone for the next generation technology. Stochastic gradient descent (SGD) a principled learning algorithm for deep learning, and because most deep learning algorithms are developed based on SGD, its theoretical analysis crucial. He et al. (2019) modeled the generalization bounds when both the batch size and learning rate constant in SGD; however, they did not model the generalization error. Furthermore, it is crucial to decrease the learning rate as the training progresses to make SGD converge (Robbins & Monro 1951), which results in good performance (You et al. 2020), but He et al. (2019) did not consider the case in which these parameters are time-varying. We analyze the vareina case SGD and propose a generalization error model for both constant and time-varying cases. Based on these models, we also propose a novel hyperparameter search method. this study, we utilized PAC-Bayes-bar the generalization error. To validate the proposed model, we trained approximately 300 networks on both practical networks (VGG16 (Simonyan & Zisserman) 2015). Wide-ResNet 28-10 (Zagoruyko) & Komodakis) (0166) and data (CIFARTO. CIFAR 100 (Krizhevsky et al. (009)). We also showed that the proposed model can approximate the experimental results well. We also show that the proposed model can be used for hyperparameter search via Bayesian optimization and yield better results, compared with the previous method for searching in the uniform distribution, and comparable results for searching in the logarithmic uniform distribution.
generalization bound generate a model of
The contributions of the present study are summarized as follows:
We analyzed the generalization bound using PAC-Bayes with the time- varying batch size and learning rate.
We directly modeled the generalization error on the batch size and learning rate and proposed its functional form.
We experimentally showed that it is possible model the generalization error with high accuracy for practical data.
Our experimental results demonstrated that the hyperparameter search method built the proposed model can outperform current libraries when

---

Under review as a conference paper at ICLR 2022
searching uniform distributions and has comparable performance when searching over logarithmic uniform distributions.
2
RELATED WORK
In this section, present related work on SGD modeling, generalization bounds, prediction of model performance, and hyperparameter optimization.
Theoretical analysis of SGD: SGD is often treated a continuous-time stochastic differential equation (SDE) by modeling the noise of the gradient and the loss function and applying the Euler- Maruyama approximation (Lin et al. 20188, Mandt et al., 2017 Li et al., 2017; Jastrzębski et al., 2017). This approximation can be solved analytically as an Ornstein- Uhlenbeck process (Uhlenbeck) & Ornstein 1930). In this study, we also analyzed SGD using the same process as the previously mentioned studies. However, in most previous studies, the batch size and learning rate in SGD were treated as constants. Hence, in this study, we treat them as time-varying and seek an analytic solution.
Theoretical error bounds: There is a large body of research on theoretical explanations for the generalization capability of deep neural networks (Negrea et al. 2019 Arora et al. 2018 Cao & Gu 2019 Deng et al.) 2021). . He et al. (2019). building on their analysis of SGD, provided a theoretical explanation of the effects of the batch size and learning rate on the generalization error. However, this research only handles the case of constant batch size and learning rate and does not model the generalization error in the function form. In this study, an analytic solution for the time-varying case and derive a model of the generalization error.
derive generalization bound based on
Predicting model performance: Most studies are based on the results from training networks, assuming hyperparameters as inputs, and searching for the best parameters without training the networks. In neural architecture search, the performance of a model was predicted for given model on a given dataset (Istrate et al. 2019). small data (Klein et al.) (017)), and model size (Real al., 2019), respectively. Several studies predict the performance of a model in functional form by treating both the dataset and model sizes input (Rosenfeld et al. (2020), or the pruning scale as input (Rosenfeld et al., 202I). In this study, we exploit the findings the above studies to predict the performance of model in a functional form, based on theoretically derived generalization bound to the batch size and learning rate.
Hyperparameter optimization algorithms are mainly catego- rized into two types: nonadaptive and adaptive. Nonadaptive algorithms search for the best hy- perparameters without using any past search results and, thus, have the advantage of being easily parallelizable. Grid search and random search fall into this category, and many studies have shown that random search is more useful (Bergstra & Bengio, 2012 Li & Talwalkar (020). Adaptive al- gorithms search for the best hyperparameters by exploiting past search results and can obtain better hyperparameters with fewer searches. Adaptive algorithms include specific algorithms, such as the evolutionary algorithm (Young et al. 2015) and Bayesian optimization (Wu et al.) 2019), and prac- tical tools, such as Hyperopt (Bergstra al. 2015) and Optuna (Akiba et al.] 2019). These methods are flexible enough to be optimized for arbitrary functions. However, there is still room for more efficient search when searching only for specific hyperparameters. In this study, we aim further improve the search efficiency of both the batch size and learning rate by employing a hyperparameter search based on the proposed generalization error model.
Hyperparameter optimization:
In the following sections, we will analyze the influence of the batch size and learning rate on the generalization error in SGD, based on assumptions about the distribution of the gradients and the shape of the risk function near minima, approximation to SDE, and the PAC-Bayee method.
PRELIMINARIES
In this section, we describe the preliminary knowledge used to model the learning process of SGD.
Generalization error of stochastic algorithms. In general, machine learning algorithms de- signed to select a hypothesis function Fg from a hypothesis class [Fy]e e C Rd) such that the expected value of the risk function R computed from the loss function / is minimized. In proba-
2

---

Under review as a conference paper at ICLR 2022
bilistic algorithm such as SGD, the parameter I after learning is considered to lie the distribution Q. The risk function for parameter / is defined as follows:
(()) = E(XY)= (aciii/D(((oll (X), Y)].
(1)
Therefore, R(Q)- = 1 [R] However, one cannot compute the risk function, and in practice, the empirical risk R(()) from the data upproximated as the risk function R(6).
1 R(0) N
((Fo(X.),
(2)
where (X,, Yi) is the N training data consisting of the input data and label pairs. Thus, R(Q) o [R()).
Stochastic gradient descent. Gradient descent is an algorithm that computes the gradient of the risk function defined in Eq 1 and updates the parameter & based on the gradient. The gradient g(f(t)) is defined as (((()) Veto R(0(L)) = VeccyBxx.y [L(Face (X), We update the parameter
0 by (t + 1) f() ng((())), where v is the learning rate. In practice, the true gradient of
gg ((((()) is approximated by the gradient of (o())) computed from the empirical risk (0) defined
in Eq and the parameter 0 is updated with (B(t)). Thus, the gradient ğs (f(t)) is defined as
Gs (O(t))
Voc R(((t))
उ Eies Voter (X,), Yi), and the parameter 0 is updated by
O(L 1) = ((1) - (0(()) We use a mini-batch S to train the model in parallel, and |S| represents its size. Then, we treat (0) = (X.), Y.).
Analysis of the learning process. The loss function (0) and its mean R(0)) is an unbiased estima- tor of the risk function R0), and the gradient of the loss function (ol( and its mean 9s (0) is an unbiased estimator of the gradient g(0) (&)( Hence, e
have (f)] E[R(()) = R(0)
and (e) = Elğs (f)] = g = ((). where the expectations are computed from the
data distribution (X, Y). Here, in Mandt et al. (2017), we assume that (0)} is independently and identically sampled from a Gaussian distribution with mean g(0) = (O). We can express (0); ~ (N)g))) C), where is the covariance matrix, which assumed be a constant matrix for all 0. Then the gradient of (0) computed for mini-batch follows the following Gaussian distribution:
(0)
1 S
Σ Vol(O) ~ iES
g(0), S C
Because the covariance matrix is symmetric and (semi) positive definite, we suppose that C can be factorized as C' BBT, T. In an actual SGD algorithm, the parameters are iteratively updated using 3 to minimize the risk function R(6):
(I = O(t + 1) - ((t) = (0)((((()) ng(
" BAW, AW N(O, T). (4) VIS
Analytical solution of the stochastic differential equation. When the learning rate 77 is small, Eq/4 can be approximated by SDE, which is known as Ornstein-Uhlenbeed process (Uhlenbeck & Ornstein 1930). Here, we assume that the risk function is convex and second-order differentiable in the neighborhood of the minimum (He et al. 2019). In addition, when the risk function R(0) is minimized at 0 0*, it shifted that is minimized at 0. Thus, the risk function R0)) can be approximated by second-order statistic on the distribution Q as follows:
R(0)) = AT A0,
(5)
where A is the Hessian matrix around the minimum of the risk function and is assumed to be positive definite. This assumption was experimentally demonstrated by [i et al.] (2018), and other studies have made similar assumptions (Jastrzebski et al. 2017 Poggio et al. 2017). Because E(ī(()) =
R()), we further assume that the empirical risk R()) is in the following quadratic form:
R(()) 2 ( - 06) T A( 0b)
(6)
3

---

Under review as a conference paper at ICLR 2022
where 0g is the bias term, Á is the Hessian matrix, and [B[,]] = [[A] = A.
is well known that Eq has an analytic solution (Gardiner 2004).
(() - - V [Ss e A(t-() B(W((),
where W (t'') is white noise and follows, (N /0, I) and the distribution of 0 in Eq 7 and Gaussian.
THEORETICAL GENERALIZATION BOUND
In this section, we derive the generalization bounds for both constant and time-varying cases.
4.1 CONSTANT CASE
Using Eq and PAC-Bayes, we obtain a generalization bound for SGD as follows (see Appendix B.I B.Ifor for the derivation).
Theorem 1 (extension of of et al. 2019), Theorem 2). We treat A as the Hessian of the risk function around the local minimum, C as the covariance matrix of the gradients calculated by single sample points, Q the distribution of the output hypothesis function of SGD, E is the covariance matrix of the distribution Q, d is the dimension of the parameter 0 (network size), and R is the search radius of the parameter 0.
When A and E commute, for any positive real E (0,1), with probability 1 - 5 over a training sample set of size N, we have the following inequality for the distribution Q:
R(Q) & R())
ZJS (r(CA-)))) d log
2|S] "
log (det (CA-1)) R d 2 log (7) 2 log N +
4N - 2
This generalization bound incorporates new scale factor for the parameter search, R², into Theo- rem 2 of et al. (2019). Although similar results can be derived without assuming that and Σ commute, we used the above assumption for simplicity. It represents the radius of the hypersphere the parameter search, and ||0 0ul < R², We also show that this generalization bound also has network initialization factor. A detailed description is provided in Appendix B.2
4.2 TIME- VARYING CASE
It should be noted that, when solving Eq the hyperparameters in SGD such the batch size [S] and the learning rate 77 can be time-varying. While He et al. (2019) derived a generalization bound for the case in which these constant, we further analyze the time-varying case. In the vime-varying case, the solution takes the form of a hyperparameter term in Eq Jettering the integral (Gardiner 2004).
((t) = c(t)=c-A0(0)) + L. Vn((Fe--At-- A(t-1") BdW(
where nut))
[S((]] Then, we treat the time-varying batch size and learning rate as a univariate
m(t)
function v1). This allows us to treat changes in the learning rate (Robbins & Monro 1951 You al. 2020) and batch size (Smith et al. 2018) in unified manner. In general, if (z) is allowed be an arbitrary function, this integral cannot be solved analytically. However, because the learning rate generally decreases and the batch size generally increases the learning progresses, we assume m(l) to be a monotonically decreasing function and apply the mean value theorem for integrals (t (())F(()d ni()) J. F(I)dI, [lo, 41], then obtain generalization bound for the time- varying case follows (see Appendix B.3 for the detailed derivation).
4

---

Under review as a conference paper at ICLR 2022
Theorem 2. We treat D - e- Ce- Ce Using the same settings theorem I and
when A and E commute and and D commute, we have the following inequality for the time- varying case:
R(Q) R(Q)
Rinter tr(CA-1) doo
2 ) log (det (CA-1)) + R - d 2log (3) + 2og N + Renter
4N 2
(10)
and
ninter = (1 - X) min (n(()) + Amax (n(()), Ae [0,
(11)
5 FUNCTIONAL. APPROXIMATION OF THE GENERALIZATION ERROR
Based on the theoretical analysis thus far, we consider approximating R(Q) in functional form. From 8 and Eq 10 we have already modeled the generalization bound (R(Q) R(Q)). We can also design a empirical functional form based on He et al. (2019)' ' experimental results on the effect of ratio of the batch size to learning rate on the generalization error. Thus, if we can model the training error R(Q),, we can derive the functional form of the generalization error. We model the training error by substituting Eqs and 9 into Eq 6 Subsequently, we show the specific functional form of the generalized error model for constant and time-varying cases.
and
5.1 CONSTANT CASE
First, we organize Eq with respect to the batch size |S| and learning rate ry and the learned param- eter (t) is as follows:
0(t) ao V [S] a1
(12)
where do a1 are vectors that do not depend on [S], 17. By substituting this into 6 the functional form of the training error R(Q) is as follows. The detailed derivation in Appendix B.4.1
1 | )
1 1 (0- (0-0) (-O))T(C) - -0,) = EE
R(Q)= = E
2
00
+
V
S
a1
À
a
+
ag +
a1
02
(13)
|S|
where ab = ag 0,. and ap, Q1, are constants. Although we can model R(Q) directly by substituting into
into 5 this cannot treated as practical functional form as it does not model the experimental increase of the generalization bound with respect to the decrease of [3] (He et al.,
2019). Thus, address this problem by modeling the training error R(Q) and the generalization bound (R(Q) R(Q)) separately. To model the generalization bound, we propose the following He functional form based on the model derived in Eq [|dd He et al. (2019'ss experimental results. The
detailed derivation is given in Appendix B.5.
IS
R(Q) R(()) = + a4l 1
(14)
Here, ag dg constants. By combining Eq 13 and Eq
propose the following functional
form as a model the generalization error R (Q).
R(Q) 2(S. m)
17 co +
+
22 n
| +
Cs
(15)
S
S
5

---

Under review as a conference paper at ICLR 2022
1.0
GMd 10127% AILAS
0.-
0.9
0.6
curve
0.5
fisdd
0.5
10"
10:3
10-3
10
10'
10:3
10-3
10
Botch
(a) CIFARIO
(b) CIFAR100
(c) Estimated vs. actual error.
10-
casnts p- w0uae
1.
16
0.4
18:5 10.a.
Baach
(d) CIFARIO
(c) CIFARIOD
(1) Estimated vs. actual error.
Figure 1: Experimental results of the proposed model for both (a. e) constant and (d, time-varying cases, (a, b) For constant case, we plotted points with the ratio of learning rate to batch size on the horizontal axis of a log scale and the generalization emorr on the vertical axis. (d, e) For the time-varying case, we plotted points with the ratio of the initial learning rate to the batch size and the ratio of the final learning rate to the batch size the horizontal axis of the log scale, and the generalization error on the vertical axis. (a, b, For all cases, also show the results fitted by the proposed model as green lines surfaces, respectively. (c, The true generalization error and estimation error are plotted, and the mean and standard deviation of the relative error are represented by μ and σ, respectively.
where Co C3 are constants. The first term models the training error R(Q), and the second term models the generalization bound (R(Q) R(Q)). Thus, the first term denotes that the training error monotonically increases with respect to the hyperparameter TST and the second term denotes that the generalization bound inversely decreases.
5.2 TIME-VARYING CASE
As discussed in Section we approximate 9 to a simple form similar to Eq 12 using an ap- proximation of the mean value theorem for integrals. Based on the functional form obtained by sub- stituting Eq into 6 the model of generalization bounds derived in [q and He et al. (2019)'s experimental results, we propose the following functional form as the model of the generalization error e(S, 7). A detailed derivation is given in Appendix B.4.2 and B.5.2
E(S, (con + cmm)
+
c2 n2
C3
(16)
n1 (1 A1) min (Vn(t) + d max (vn(t)
(17)
n2 = Xa) min (n(t)) + X max (n()))
(18)
where Cp A1.2 are constants and Å A2 E [0, Note that, for in the first term, the intermediate value computed after taking the square root n(l), and for ng in the second term, the linear interpolation is computed.
5.3 PRACTICAL FUNCTIONAL FORM
In the discussion above, we constructed a rough model of the generalization error. However, the models in Eqs 15 and 16 have upper bounds, and they don't model the fact that the loss function

---

Under review as a conference paper at ICLR 2022
30
15
20
15
20-
10
& 10
5-
10
0-
40 sample
60
50
100
150
-5
20 sample
40
60
-5
50
100
150
sample
sample size
(a) Constant case
(b) Tare-narying case
(c) Constant case
(d) Time-varying case
Figure Experimental results on the stability of the generalization error model for (a, b) CIFARIO and d) CIFAR100, the (a, e) constant case and (b, d) time-varying case. The horizontal axis shows the number of networks randomly selected to estimate the generalization error, whereas the vertical axis shows the mean value and standard deviation of the relative error 8. The shaded areas represent one standard deviation from the mean in each direction.
hits its head the random guess level. Therefore, it is necessary to model the transition from the initial random guess level to the proposed model E(S,n) Thus, we propose the model É(S, 17) using a soft-min function based on the LogSumExp function.
1 ( (-log (e- (e-or((s.)) +e e eerrr)) C4
1
é(S, n)) softmin(?(S,n)) co: c1)
(19)
where 04 is constant that controls the shape (sharpness) of the soft-min function (softmin(r: y) log (exp (-z) + exp (-y))). co is the value of the loss function at the random guess level, which statistically determined and not explored. (e.g., for balanced dataset image classification, we can treat it as 6o 1 - (1/Netsses))
6 EXPERIMENT
To validate the proposed model E(S, 11), we trained a practical network (VGG16 (Simonyan & Zis- serman 2015), Wide-ResNet 28-10 (Zagoruyko & Komodakis 2016)) on the image classification
tasks (CIFAR10, CIFARI00 KKrzhevsky et al. 2009)).
6.1 EXPERIMENTAL SETTINGS AND RESULT
In the constant case, the batch size and learning rate were fixed throughout the training pro- cess. To evaluate the generalization error, we trained 60 VGG models with batch size |S| E {16, 32, 64, 128, 256, 512] and learning rate E {1/22li = 3, ..., 12} for CIFARIO, as well as 66 Wide-ResNet models with the same batch size |S| and learning rate n (1/2'ji 2, 12) for CIFARION over a total of 200 epochs. The experimental results for the constant case are shown in Figures Ta and 1b We plotted the log scale of on the horizontal axis and the generalization error on the vertical axis. We found both decreasing and an increasing property of the generaliza- tion eтror before and after TST ~ 10-4, which we discussed in Eq 15 Although He et al. (2019) claimed that increasing Y decreases the generalization error, the experimental results show that the generalization error increases when 13 exceeds certain value. This implies that, in addition to the
generalization bound, the training error R(Q) must be modeled.
In the time-varying case, only the learning rate is be time-varying, and we use an exponential step function. We chose Mimit and Mrinat and trained over 200 epochs, starting with learning rate of Mmnst decaying with decay rate of 7 60, 120, and 160 epochs, and finally reached learning rate i/aa = T at 160 epochs.
In addition
the constant case, we trained case in which the batch size | {16, 32, 64, 128, 256], the learning rate of Tinit E {1/2i i 3.... 4} and Afrinal E {0.1/2') i = 0,....4} for CIFAR 10, the same batch size (S], the learning rate of Mamis E {1/2 2,.., 4) and the same Tifinal for CIFAR100, well case in which the batch size [S| {128, 256). the learning rate of Minit (1/2*)i 5.... 9) and Affnnt (0.1/2% 5, 5...,9 9) for both datasets. In
7

---

Under review as a conference paper at ICLR 2022
0.50
0.90
maa sccurayy
798 acurary
0.83
0.83
0.05
0.05
0.80
0.50
0.60
0.60
Kidan
0.75
0.75
0.55
0.95
Aapusee
Fropised cara
20
0.70
30
20
0.50
10
30
0.50
Sample
semple
(a) CIFARIO, uniform
(b) CIFARIO, log
(c) CIFARIOO, uniform
(d) CIFARIOO, log
0.8
0.8
POX nor33cuuccy
0.9
20.9
0.8
100
10F
0..5
0.6
EST
0.7
1.0
20
0.7
10
20
0.5
20 sample size
30
0.5
10
sample size
sample
size
sample size
(e) CIFARIO, uniform
(f) CIFARIO, log
(g) CIFARIOO, uniform
(h) CIFARIOO, log
Figure 3: Hyperparameter optimization results of several methods. The number of trained models is plotted on the horizontal axis, and the maximum accuracy achieved among the trained models is plotted on the vertical axis for the (a, b, c, d) constant and (e, f, h) time-varying cases. The 95% confi- dence intervals shaded. The proposed method always searches for uniform range, whereas the comparison method searches the range written the caption (uniform or log-uniform)
total, we measured the generalization error for the 153 models for CIFARIO and 184 models for CI- FAR100. More implementation details can be found in Appendix C.I
The experimental results for S are plotted on the horizontal
the time-varying case are shown in Figures and le
Vimas and Mime
[ST
axis, whereas the generalization error c(S, 7) plotted on the vertical axis. We also plot the results
of projecting the generalization error onto Menit and Miinni respectively. As in the constant case, we
[s n(t) is not in the appropriate range (either quite large
[S]
can observe that, when the value of ntt) = [s(t)
or quite small), the generalization error becomes large.
6.2 ERROR LANDSCAPE ESTIMATION
We estimate the obtained generalization error c(S, n) using parametric family, E(S, 77; ②). Here, we treat the parameter Φ as Φ = {Co, C1, C2 Ca. Ca for the constant case, and then {2) is added the time-varying case. As in Rosenfeld al. (202I), we search for & such that the squared error of 5(S, 17; Φ)- #(S.m. e(S.m) is minimized. Implementation details are provided in Appendix C.2 <(S.n)
Figure Tc plots our results for the constant case. The mean jl and standard deviation o of the relative error 5 are |u|] 2% and 12%, respectively. Considering the small number of parameters used to estimate the generalization error ((Φb = 5), the proposed functional model can accurately estimate the complex generalization error landscape (60 and 66 models, respectively). In Figure [T] plot the results for the time-varying case. We achieved |p|] < 3% and a < 17% respectively. Although the relative eиror is larger than the constant case, we can still declare that the proposed functional model can estimate the generalization error sufficiently, considering that the generalization error of 153 or 184 models is modeled with a small number of parameters (Φ0) = 7). Appendix C.2.3 we provide comparison between the proposed model, model that analytically solves the time-varying case of the step function, and a model that uses only the final learning rate.
In addition, we verified the stability of the proposed model with respect to the number of networks. We randomly sampled a certain number of generalization errors obtained by training the networks, estimated the parameter & from them only, and computed the relative error 8. We performed this procedure 100 times and computed μ and a of the relative error. Details of the experimental setup presented in Appendix C.3.1
In Figure 2 we show the experimental results. Figures 2a and 2c show that, for the constant case of CIFARTO and CIFAR100. domly training about 30 models. In contrast, Figures gggures{bbanna show that, for the time-varying case, need to train about 75 models for the estimation.
accurately estimate the generalization error landscape by ran-
8

---

Under review as a conference paper at ICLR 2022
7 HYPERPARAMETER OPTIMIZATION
In this section, we show that the proposed model is useful for applications such as hyperparameter optimization. In this study, we used Bayesian optimization.
Bayesian optimization can compute a function = (() that can be fitted to any sequence of data points { (15, 3- Nogueira (2014) achieved this by using a Gaussian process with a Matern kernel, and many Bayesian optimization methods use generic kernel functions which can be fitted to any function. While this is practical for fitting unknown functions, ideally, the most accurate Bayesian optimization can be achieved by employing kernel function constructed from a feature extraction function (xx that can compute the unknown function with a linear combination of y w (/x). Therefore, for the constant case, we propose a kernel function k(z,, Iz)) for the input z = [s] based on Eq 15 for hyperparameter optimization.
k() = (xx)) (b2,) = VaLz + Taay +
V 1.
(20)
Details are in Appendix C.4.1 In contrast, the time-varying case cannot be represented by linear combination of y w (5))), because the product term of the parameters (c and A) appears. There-
fore, we employ hyperparameter search by sequential model-based global optimization (SMBO)
[Bergstra et al. 2011) with the proposed model in [q using Eq [6] For SMBO, we use the
Levenberg-Marquarte algorithm (Moré 1978) and Thompson Sampling (Thompson 1933 Russo
et al.. 2017). More details are provided in Appendix C.4.2 2 using the fitted generalization error model
To validate the proposed method, we explored
é(S, m 6) as the training result of the network. The details are given in Appendix C.4.3 Figure shows the experimental results. The horizontal axis plots the number of training networks, and the vertical axis plots the maximum test accuracy among the networks trained to date. A total of 100 experiments were conducted, and the 95% confidence interval was shaded. The methods used for comparison were Bayesian optimization using the Matern kernel and RBF kernel (Nogueira 2014), Hyperopt (Bergstra et al. 2015), and Optuna (Akiba et al. 2019).
As shown in the Figure 3 in almost all cases, the proposed method achieves the highest accuracy with the least number models in the search method with uniform distribution. This indicates that the proposed model represents good feature extractor, and the proposed kernel function is useful for hyperparameter optimization. In addition, in the constant case, the proposed method achieved the highest accuracy with the same number of models the comparison method, which searches for logarithmic uniform distributions. indicates that theoretical model-based hyperparameter opti- mization can be applied practically. In practice, it is generally believed that it is better to search for hyperparameters S. y in the logarithmic uniform range (Rasmussen, 1997 Sundararajan & Keerthi 2001]. However, there is no theoretical foundation for this (this is confirmed by the fact that in Hy- peropt, the results are not improved by exploring the logarithmic range). These results suggest that the proposed model-based hyperparameter optimization is both theoretically sound and practically useful when performing a hyperparameter search on the batch size and learning rate.
8 DISCUSSION AND CONCLUSION
In this paper, we presented a theoretical analysis and a model of the generalization error for the batch size and learning rate in SGD. We analyzed the case in which these parameters are constant during training and the more challenging and practical case when they vary with time. Through experiments for both cases, we show that the proposed generalization error model is practical, and we test the number of networks required to estimate the generalization error landscape (= stability of the generalization error model). In addition, we demonstrate that hyperparameter search based on the proposed model outperform the conventional Bayesian optimization and hyperparameter op- timization libraries, such as Hyperopt and Optuna. To the best of our knowledge, this is the first study that explores the batch size and learning rate based on the generalization error model. From the discussion, we conclude that this theoretical model is a practical and useful model for under- standing the effects of the batch size and learning rate on the generalization error. We hope that this work will provide further theoretical insights into deep learning and new research directions for hyperparameter search based theoretical models.
9

---

Under review as a conference paper at ICLR 2022
REFERENCES
Hirotogu Akaike. Information theory and an extension of the maximum likelihood principle. In Selected papers of hirotugu akaike, pp. 199-213. Springer, 1998.
Takuya Akiba, Shotaro Sano, Toshihiko Yanase, Takeru Ohta, and Masanori Koyama, Optuna: A next-generation hyperparameter optimization framework. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 2623-2631, 2019.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. convergence theory for deep learning via over- parameterization. In International Conference Machine Learning, pp. 242-252. PMLR, 2019.
Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via compression approach. In International Conference Machine Learning, pp- 254 263. PMLR, 2018.
James Bergstra and Yoshua Bengio. Random search for hyper-parameter optimization. Journal of machine learning research, 13(2), 2012.
James Bergstra, Rémi Bardenet, Yoshua Bengio, and Balázs Kégl. Algorithms for hyper-parameter optimization. Advances in neural information processing systems, 24, 2011.
James Bergstra, Brent Komer, Chris Eliasmith, Dan Yamins, and David D Cox. Hyperopt: a python library for model selection and hyperparameter optimization. Computational Science Discovery, 8(1):014088, 2015. URL http:: htt.a//.........o/ooooooo///////
Alon Brutzkus, Amir Globerson, Eran Malach, and Shai Shalev-Shwartz. SGD learns over- parameterized networks that provably generalize on linearly separable data. In International Conference on Learning Representations, 2018.
net forum?
1d=rJ33wwxRbb
Yuan Cao and Quanquan Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. Advances in Neural Information Processing Systems, 32:10836-10846, 2019.
Zhun Deng, Hangfeng He, and Weijie Su. Toward better generalization bounds with locally clastic stability. In International Conference on Machine Learning, pp. 2590-2600, PMLR, 2021.
Simon S. Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes wwer-parameteriiee neural networks. In International Conference Learning Representations, 2019. http://tpp.//ogeeeeeeeeeeeeeeeee
C. W. Gardiner. Handbook of stochastic methods for physies, chemistry and the natural sciences, volume 13 of Springer Series in Synergetics. Springer-Vette Berlin, third edition, 2004. ISBN 3-540-20882-8.
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pp. 249-256, 256. JMLR Workshop and Conference Proceedings, 2010.
Fengxiang He, Tongliang Liu, and Dacheng Tao. Control batch size and learning rate to generalize well: Theoretical and empirical evidence. Advances in Neural Information Processing Systems, 32:1143-1152, 2019.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. In Proceedings of the IEEE international conference on computer vision, pp. 1026- 1034,,00,,200 2015.
Roxana Istrate, Florian Scheidegger, Giovanni Mariani, Dimitrios Nikolopoulos, Constantine Bekas, and Adelmo Cristiano Innocenza Malossi. Tapas: Train-less accuracy predictor for architecture search. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 3927- 3934, 2019.
10

---

Under review as a conference paper at ICLR 2022
Stanistaw Jastrzębski, Zachary Kenton, Devansh Arpit, Nicolas Ballas, Asja Fischer, Yoshua Bengio, and Amos Storkey. Three factors influencing minima in sgd. arXiv preprint
arXi::1711.0422,, 2017.
Bumsoo Kim. wide-resnet.pytorchh 2018.
URL https://giihbb..cmm//ell///
w pytorch
Aaron Klein, Stefan Falkner, Simon Bartels, Philipp Hennig, and Frank Hutter. Fast bayesian op- timization of machine learning hyperparameters on large datasets. In Artificial Intelligence and Statistics, pp. 528 536. PMLR, 2017.
Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. Cifar-10 and cifar-100 (canadian institute for advanced research). 2009, URL http::/www.cc..oroottoo. www.ontto.dd///kii.... cifar html
Cs
Hao Li, Zheng Xu, Gavin Taylor, Christoph Studer, and Tom Goldstein. Visualizing the loss land- scape of neural nets. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran As- sociates, Inc., 2018. URL/tcps.//ppoceeddgg.... wttpa///p.....ppppp//////////...
10113bb6ee00bbbb0000077666333333 Paper. pdf
Liam Li and Ameet Talwalkar. Random search and reproducibility for neural architecture search. In Uncertainty in artificial intelligence, pp. 367-377. PMLR, 2020.
Qianxiao Li, Cheng Tai, and Weinan E. Stochastic modified equations and adaptive stochastic gradi- ent algorithms. In Doina Precup and Yee Whye Tch (eds.), Proceedings of the 34th International Conference on Machine Learning. volume of Proceedings of Machine Learning Research, pp. 2101-2110. PMLR, 06-11 Aug 2017. URL http: http:::/ppoceeediingg ml wttpsssss.r....e////ooo
1117E 1117E.html
Tao Lin, Sebastian U Stich, Kumar Kshitij Patel, and Martin Jaggi. Don't use large mini-batches, use local sgd. arXiv preprint arXiv:1808.077 072117 2018.
Kangqiao Liu, Liu Ziyin, and Masahito Ueda. Noise and fluctuation of finite learning rate stochastic gradient descent. In International Conference on Machine Learning, pp. 7045-7056. PMLR, 2021.
Stephan Mandt, Matthew Hoffman, and David Blei. Stochastic gradient descent as approximate bayesian inference. arXiv preprint drXiv:1704.04220 2017.
David A McAllester. Pac-bayesian model averaging. In Proceedings of the twelfth annual confer- ence on Computational learning theory, pp. 164-170, 1999a.
David A McAllester. Some pac-bayesian theorems. Machine Learning. 37(3):355-363, 1999b.
Jorge J Moré. The levenberg-marquard algorithm: implementation and theory. In Numerical anal- ysis, pp. 105-116. Springer, 1978.
Jeffrey Negrea, Mahdi Haghifam, Gintare Karolina Dziugaite, Ashish Khisti, and Daniel M Roy. Information-theorette generalization bounds for sgld via data-dependent estimates. arXiv preprint arXiv:1911.02151. 2019.
Fernando Nogueira. Bayesian Optimization: Open source constrained global optimization tool for Python, 2014. WRRLhhtps:///itttii wttp:////...tttt//eeeeeeeeeeeeee antp imi
Tomaso Poggio. Kenji Kawaguchi, Qianli Liao, Brando Miranda, Lorenzo Rosasco, Xavier Boix, Jack Hidary, and Hrushikesh Mhaskar. Theory of deep learning ii:: explaining the non-overfitting puzzle. arXiv preprint 180iv: 1033,3 2017.
Carl Edward Rasmussen. Evaluation of Gaussian processes and other methods for non-linear re- gression. PhD thesis, University of Toronto Toronto, Canada, 1997.
Esteban Real, Alok Aggarwal, Yanping Huang, and Quoe V Le. Regularized evolution for image classifier architecture search. Proceedings of the aaai conference on artificial intelligence, volume 33, pp. 4780-4789, 2019.
11

---

Under review as a conference paper at ICLR 2022
Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathemati- cal statistics, pp. 400 407, 1951.
Jonathan S. Rosenfeld, Amir Rosenfeld, Yonatan Belinkov, and Nir Shavit. A constructive prediction of the generalization error across scales. In International Conference Learning Representa- lions, 2020. URL hhttps://openrevv.l.
net htt/:/oommmmmmrrmreeee
Jonathan S Rosenfeld, Jonathan Frankle, Michael Carbin, and Nir Shavit. On the predictability of pruning across scales. In International Conference on Machine Learning, pp. 9075 9783- PMLR, 2021.
Daniel Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Osband, and Zheng Wen. A tutorial on thompson sampling. arXiv preprint arXiv:1707.02038, 2017.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. In Yoshua Bengio and Yann LeCun (eds.), 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceed- ings, 2015.
org/ htt.sb/ss440. 1556
Samuel Smith, Pieter-Jan Kindermans, and Quoe V. Le.. Don't decay the learning rate, increase the batch size. In International Conference Learning Representations, 2018. URL https:
//openreview. www. http://wwnne//tommmiii------
Sellamanickam Sundararajan and S. Sathiya Keerthi. Predictive approaches for choosing hyperpa- rameters in gaussian processes. Neural computation, 13(5): 103-11188 2001.
William R Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4):285-22 2944, 1933.
George E Uhlenbeck and Leonard S Ornstein. On the theory of the brownian motion. Physical review, 36(5):823, 1930.
Jia Wu, Xiu-Yun Yun Chen, Hao Zhang, Li-Dong Xiong, Hang Lei, and Si-Hao Deng. Hyperparameter optimization for machine learning models based bayesian optimization. Journal of Electronic Science and Technology, 17(1):26-40, 2019.
Kaichao You, Mingsheng Long, Jianmin Wang, and Michael I. Jordan. How does learning rate decay help modern neural networks?, 2020. URL https:://penreeview. net forum?
1d=r1e@nh4YPB
Steven R Young, Derek C Rose, Thomas P Karnowski, Seung-Hwan Lim, and Robert M Patton. Optimizing deep learning paperpparameters through an evolutionary algorithm. In Proceedings of the workshop machine learning in high-performance computing environments, pp. 1-5, 2015.
Sergey Zagoruyko and Nikos Komodakis, 1rXiv:1605.07146, 2016.
Wide residual networks.
arXiv preprint
12

---

Under review as a conference paper at ICLR 2022
A BACKGROUND
A.1 PAC-BAYESIAN FRAMEWORK
The PAC-Bayesian framework originates from McAllester 1999a bX 's work. In the PAC-Bayesian perspective, the hypothesis functions learned by probabilistic machine learning algorithms are drawn random from the hypothesis classes based on some "rules." " The generalization ability of an algo- rithm is negatively correlated with the distance (often measured by the Cullback-Leibes (KL) diver- gence) between the output hypothesis distribution and the a priori distribution (typically a Gaussian or uniform distribution). The above results suggest that there is tradeoff between minimizing the empirical risk and exploring further regions of the hypothesis space from the beginning (a priori).
Let P be the initial priori distribution in the parameter space θ and let Q be the distribution in θ after learning. We can now define the expected value of the risk function under distribution Q as follows:
R(Q) = Ex))(R(()).
Similarly, the empirical risk function under distribution Q can be defined follows:
Q())= Ee [R())).
Based on these, we obtain the classical result in that the expected value of the risk function R(Q) is uniformly bounded by the expected value of the empirical risk function R(Q) and KL--divergecce P).
Lemma (See McAllester (1999)), Theoreml). For any positive real 8 (0, 1) with a probability of at least 1 à over sample of size N, we have the following inequality for all distributions Q:
R(Q) - R(Q)+ + D(QIIP) + log ( + log N +2
(21)
2N -1
where P) is the KL divergence between the distributions Q and P and is defined as
D(QIIP) = Ea-q (1og Q(0)
(22)
P(0))
B SUPPLEMENTAL PROOFS FOR THE PROPOSED METHOD
In this section, we describe the details of the proof, which we omitted in the proposed method.
B.1 GENERALIZATION BOUND FOR THE CONSTANT CASE
To prove Theorem [ we use an existing proof method that approximates the SGD update of the model to a stochastic differential equation (see, e.g., (Mandt et al., 2017)). With appropriate process
sumptions, the learning process of SGD can be approximated by the Ornstein- (Uhlenbeck & Ornstein 1930). Because the Urnstein-Uhlenbeck process has analytic solution, we can use the distribution Q of the analytic solution 0 to derive the Kl-divergence, which used derive generalization error bound from Eq Here, we modify and extend He al. 2211)'s Theorems I and 2 to derive the generalization error bound for the constant case.
Lemma (cf. Gardiner (2004), pp. 1001-199-........ Under second-orded differentiable assumption (Eq if is sufficiently large, the Ornstein Uhleebeek process (Eq44y's distribution
q()) = M exp
TT - AT Σ
(23)
2
has the following property:
A + ΣA-
C.
(24)
[S]
13

---

Under review as a conference paper at ICLR 2022
This lemma is similar that of Gardiner (2004).
Proof of Lemma 2 From the analytical solution of the OrntteinUUhleneec process
(Uhlenbeck &
Ornstein 1930), the parameter can be expressed as follows:
((t) = =c-
Alt- (t),
(25)
V
where W W('') is white noise and follows (0, From Eq 23
obtain
= B [00
(26)
Thus, obtain the following equation:
AΣ + EA Ae (0(0), TT (0)) (e (0))
||| Ae A(t-t)) Ce- A(-0-)))
+
[S J - Ce - C- Adt'
+
Ae (8(0), T (0))E M
(0))E-A +e e (0(0))
S I de
"
Alt-r) Ce A(t A di!
+
= Ae (0(0), T (0)} At + e At (0(0), ((())) AA
+ 17 C
Al ACC Ce- -At
[S]
S
C,
(27)
S
where A is the Hessian matrix and symmetric. The last transformation is guided by the assumption that A a positive definite matrix and all its eigenvalues are positive and by the approximation of the term multiplied by -At twice with zero, because is sufficiently large.
The proof's is completed.
Lemma 3 (extension of He et al. 2019). Appendix B.1). For any positive real ô E (0, 1), with probability 1 - 8 over training sample set of size N, have the following inequality for the distribution Q of the output hypothesis function of SGD:
(r(CCA-1) - 2og (det(E)) + 2R + 4log (3) + 4log N + 8
R(Q)= S xR(Q)+
(28)
8N
where A is the Hessian of the risk function around the local minimum, C is the covariance matrix of the gradients calculated by single sample points, Σ is the covariance matrix of the distribution Q, is the dimension the parameter 6(network size), and R is the search radius of the parameter A.
Proof of Lemma 3 In the PAC-Bayesian framework ((Lemma) D it is crucial to compute the KL- divergence between the parameter distribution of the output hypothesis function and the prior pa- rameter distribution in the hypothesis space. The prior distribution can be interpreted parameter distribution, and in most cases, either uniform distribution or a Gaussian distribution used. In this study, we assume that the prior distribution is Gaussian A/(0*, I). 0* is param- eter for which the risk function R(Ø) is minimized. The mean value -0" of the prior distribution corresponds to the shift in 0 in Eq which actually eliminates prior knowledge of the posterior distribution. He et al. (019)) uses N IO, for the prior distribution. However, it is unnatural be- cause the prior distribution has prior knowledge of the posterior distribution. Conversely, our setting
an initial
14

---

Under review as a conference paper at ICLR 2022
becomes more natural. The posterior distribution Q and prior distribution P are represented by p(0) and q()) with respect to the parameter 8, given by the following equation:
p(0) = ((2T) det(I)
exp
- (-2
1 (0 + 0-)
07)
(29)
2
1 0 -
(0) ((z) (z)
exp
(30)
Here, represents the dimension of the parameter 0, and Eq M in 23
30 computed the normalization term
Thus, we obtain
g
log
p(0)
- (0) - 0)
-
log
(V (2 det(E)
exp
log
+ (10+0) 1(0 + 0*) - -0)
(31)
2
dot(E)
Substituting Eq 3 into Eq
22
we can compute the KL divergence between Q and P as follows.
Here, we assume +
Rd.
D(Q1IP)
Q(0)
P(0)
(())
log
((0)de
Jage
p(0)
log
1
(10 0-) 1(0 +00 0-) (1+00)]((000000
-0T-100 o(0)d0
2
del(E)
Bee
1
0t 10" "0' (0))d + 11 0t (8T))g)))
log
+
T 10)(0)
2
det(2))
2
Bee
Jee
0 -T-- (g))d
2
J
1
log
+ Bon [0_10] + Be.N((O,E) [0TT10]] + Be [o-T10 10]
2
det(E))
10T (-'10
2
1
log
+
2 (r())) + 110011 110011---1011 (rl)
2
det(E))
2
log
+ ir(E) + R2 (r()).
(32)
2
det(E))
2
The last transformation is obtained because 1 < R2 always holds when the search range of the
parameter ( hypersphere of radius From Eq we obtain
AΣ EA "
[S]
Therefore, obtain
AΣA +
77
CA-1
(33)
S
By computing the trace on both sides, the equation becomes
tr (AEA-L + Σ) =
CA
(34)
S
15

---

Under review as a conference paper at ICLR 2022
The left-hand side (LHS) can be transformed follows:
LHS [AEA-++>>
tr (AEA- + tr (2)
ir (EA-1A) A) + (r
= =tr (E) +tr
2tr (E).
(35)
Thus, can derive the following:
1 17
tr (Σ)
= 2 S|
CA-1
tr (CA-1). 2 S
(36)
We can also compute the following:
Ir(T)= d
(37)
because the dimension of parameters and I E IRdxd Therefore, by substituting Eq 36 and
Eq 37 into Eq 32 we obtain
77 (r(CA))) log (det(E)) 1 R² 4|s
1
1 d. 2
D(QIP))
(38)
Eq an upper bound on the distance between the distribution Q learned by SGD and the priori distribution P. Therefore, by substituting Eq into Eq 21 we can obtain a PAC-Bayesian generalization bound for SGD.
The proof is completed.
Lemma (extension He al. (2019), Appendix B.2). Assuming that A and commute, the KL divergence between the distribution Q of SGD and the prior distribution P satisfies the following inequality:
D(QIP)S
" tr((AA-)) + d dog 4
log (det(CA-1)) + RR² d.
(39)
2
Lemma 4 provides the distance between the distribution Q obtained by SGD and the prior distribu- tion of the parameters. The assumption that A and Σ commute implics that matrices and are simultaneously diagonalizable, and similar assumptions have been used in the work of Jastrzbskki et al. (2017) and et al. (202T). Although similar results can be derived without assuming that A and Σ commute, we used the above assumption for simplicity. Based on this assumption, we can compute a generalization bound for a constant case.
Proof of Lemma 4 Because A and Σ commute by assumption, the following equation be ob- tained by transforming Eq 24
AΣ + EA EA+ = C
[S|
2ΣA = 7 C
[S]
Σ 2|5|
CA-1
(40)
Thus,
d
det(E)) = det
2
CA-1)
=
2
det(CCA
(41)
16

---

Under review as a conference paper at ICLR 2022
and we compute
(
log (det(E)) (E)) = log
2| det det(CA-1)
(2|S²
-d
+ log (det(CA-")).
(42)
17
Therefore, can be obtained by substituting Eq 42 into Eq 38
The proof is completed.
Thus, we can easily prove Theorem !
Proof of Theorem
!
It obtained by substituting Eq 39 into Eq
The proof is completed.
B.2 ADDITIONAL TWO FACTORS IN THE PROPOSED GENERALIZATION BOUND
In addition the three factors discussed in He et al. (2019'ss Theorem 2, the local geometry around minima, gradient fluctuations, and hyperparameters, the generalization bound derived in this study incorporates a factor for the range of parameter search and a factor for network initialization.
Parameter search space The norm of 0 after learning appears the third term R2 in Eq 32 Hence, the parameter search range and weight decay are naturally incorporated into the generaliza- tion bound.
Network initialization. Morcover, this generalization bound naturally incorporates the network initialization factor. Assuming that the prior distribution is N(-0", AT), 0 < X, we obtain the following:
(0)) dett)) exp (- (-2x (0 0.) T(++0))) (0++0)00++)))
O<
(43)
Eq is as follows.
D') < log det(E))
+
tr(E) +
R²
tr(7).
(44)
2X
2X
2
By differentiating the right-hand hand side (RHS) by we can observe that RHS is minimized by RHS log tr(E)+R² 1 log (det (E)). when À tr(E)RR² Assuming that d is sufficiently large and
tr(E)
R < d is valid (this property is also called overparaaeetriization (Allen-Zhu et al. 2019 Brutzkus et al. 2018 Du et al. 2019),, we can theoretically guarantee that the generalization bound
will be tighter when change the covariance matrix of the prior distribution to diagonal matrix with even smaller eigenvalues, such as He's initialization (He et al. (213)) or Xavier's initialization
GGlooot & Bengio 2010). Therefore. the generalization bound proposed in this study, which is an
extended version ol He et al. (2019), also naturally incorporates factors related to the initialization
of the network.
B.3 GENERALIZATION BOUND FOR THE TIME- VARYING CASE
To prove Theorem 2 we only need to describe how the time-varying batch size and learning rate change Eq 24 in Lemmal) 2] To do so, we solve following Lemma
Lemma (extension of Gardiner (2004), pp. 115-116.. Under second-order differentiable assump-
tion (Eq , if is sufficiently large and hyperparameter S| is time-varying, the Ornstein-Uhlenberr
process E distribution
1 ---0
( = M Mexp
(45)
17

---

Under review as a conference paper at ICLR 2022
has the following property:
AE + n(E)C, [0,t].
(46)
Here,
ntt)
ne(t)
(47)
|t())
Proof of Lemmn 5
From the analytical solution of the OmnsteinUUllenbek process (Uhlenbeck & the time-varying case (Gardiner 2004). the parameter 0 can be expressed as
Ornstein 1930
follows:
((t) - c()0=))))(0)) + f Vn(t")e (a(t))e-A(-1)) A(t-1') (dW(+)),
(48)
where ((!) is white noise and follows (0, 7). From Eq 45 we obtain
Be~q [00
(49)
Thus, we obtain the following equation:
AΣ ΣA Ae (0(0), 0 (0)} te - (0(0), A
+ % m(t))cc A(t-A)) Ce - A(t-
[[ -((t)--A Ce Adt
(50)
where A is the Hessian matrix and symmetric, We use the mean-value theorem of integrals to obtain the following equation: For some {1, [0, tl.
I, Ae Al Ce Alt Alt-r)) = n(Ei) ( Ae Ac- Ce- -
(51)
[( [n(tte (((t)e-A0--11 Adt''
Adt' = =((e) (( Co Adt'
(52)
Here, we assume that the matrix D
D 10 e Ce
(53)
and that A and D commute, Then, because AD = DA,
= E2
(54)
holds for Eq 51 and Eq 52 Thus, by substituting Eq into Eqs 51 and 52 and then substituting
the result into Eq 50 we derive
AE + ΣA
Ae Al (8((), AT (0))e- +e ((((0), 8T (0))e ((0)) "A
+ n(E) /' Ae -e-
+ n(E)) 1'' c-A(s--)) Ce - A(t-t() Adt'
Ae M ((((0), OJ (0))e M + E -A (())e AA
+ n(()) '' d A(t-t') Ce- ('- CCce--ltt)) Alt-t')
de
(000) AT (0)) A (0(0), (0)) A Ae Ae A0-AA/00
+n(E)C n(E)e -A AAt C(E)C.
(55)
18

---

Under review as a conference paper at ICLR 2022
The last transformation is guided by the assumption that A is positive definite matrix and all its eigenvalues are positive and by the approximation of the term multiplied by e AAt twice with zero, because t is sufficiently large.
The proof is completed.
Proof of Theorem Using Eq[55] rather than 2q in the proof of Theorem leads to Eq 10 Furthermore, exactly
min(n(t)) S m²() s max(n(t)),
(56)
by applying a certain E [0, 1], we can express
n({) = (1 >) min(n(()) + A max(n(()).
Therefore, Eq 11 was derived simultaneously.
The proof is completed.
B.4
FUNCTIONAL MODEL OF THE TRAINING ERROR
B.4.1 CONSTANT CASE
We derive training error model for the constant case. We approximate the training error R())
by substituting Eq into 6 and then approximate R(Q) by computing the expected value in the parameter distribution Q. In the constant case, we can compute
R(0)= = (0 0)) A(O - 06) = 2 2
e --At((0) - 0 +
V |S| l' C -(( BaW(())
T
(00(()) 0b V [S]
"
-a BdW('))
(00)) Te- -At -----0 00 Ad( A0)( - -0b)
1 A(t BAW(")) À (f: (A((t-t)) Bdw((") -all-))
77
2
[s]
T c-A(L-()
A(e-A10(0) Bat()))aw()))) Baw
0b))
17
(57)
S1
Therefore, by taking the expected value with the distribution Q, we obtain
R(Q)) Eana [((0]
(00-0)) Á(O 0,)]
~ Eawe
(0000 T- -0,)) A5) (0k00-)000000 -mb)
=E
2 S A((--1 Baw(H)) A (f% ((--lt-03Baw
"
E
[s]
A(t-()) (') Baw())) MeeAA)0(0) - -b6)
E
v
1
1
0g
ai
|
a2
V
|S|
(58)
This allows to model R(Q), shown in Eq
13
19

---

Under review as a conference paper at ICLR 2022
B.4.2 TIME- VARYING CASE
To compute the training error model for the time-varying case, we only need to consider how time-varying batch size and learning rate change Eq Thus, we use the mean value theorem of integrals Eq to obtain the following equation:
((t) 0(0)) + L. Vn(e)e-Ate A(L-t)) BdW
0(0) + vn(() S cAll-t
BdW(()) (t)
(59)
Here, ç E [0, and as exactly
min( min(vn((). S vn(() S max (vn()))
(60)
for some À E [0, 1J. obtain
vn(E) (in-))mmnn/((())( A Amax max)(Vn()).
(61)
Thus, we can compute the first term Eq T6 which the training error model the time-varying case, by substituting Eq into Eq 59 and then performing the same transformation in Appendix
B.4.1
B.5
FUNCTIONAL MODEL OF GENERALIZATION BOUND
B.5.1 CONSTANT CASE
In this section, under appropriate assumptions, we show that Eq monotonically decreases with respect to =i basis for deriving Eq 14 based on Eq 8 We He et al. (2019)'s 's proof to make our paper complete. We first make the tollowing assumptions about dimension of the parameter space e.
Assumption (See He et al. 2019), Assumption 2). The network size is large enough:
d tr(CA-
(62)
2.5
where d is the number of parameters, C is the magnitude of the individual gradient noise, A is the Hessian matrix around the global minima, 1j the learning rate, and [S] is the batch size.
This assumption can be justified by the fact that network sizes of neural networks are often extremely large. This property is also called overparameterization (Allen-Zih Zhu et al.) 20199] Brutzkus et al.)
2018
Du al. 2019). We can obtain the following corollary by combining Eq and Assumption
Corollary (See He al. (2019), Appendix B.3). When all conditions of Theorem Had Assump- tion 1 hold, the generalization bound of the network negatively correlated with the ratio of the learning rate the batch size.
Proof of Corollary 7
We first define
1 - "
2 +
[|SS]
log (det (CA-1)) R² - -d+2log { + 2log N +4. (63)
Then, Eq becomes
R(Q) < R(Q) +
(64)
-
20

---

Under review as a conference paper at ICLR 2022
We calculate the derivative of I with respect to the ratio to check whether the generalization bound has a negative correlation with the ratio. For brevity, we set T
ar Ø k (r((AA dllog(2k) log (det (CA-1)) R + 2log (6) 2 2log N Oh dh 2 tr(CA- 2 k
(65)
Therefore, when Assumption holds, we have
tr(CA- ')
d
str(CA-)).
(66)
2|5|
Thus,
01
(67)
ak
Then, and the generalization bound have negative correlation with the ratio of the learning rate to the batch size.
The proof is competed.
B.5.2 TIME- VARYING CASE
In this section, the basis for deriving the second term in Bq based on Eq TO we will show that T monotonically decreases with respect to ne in Eq
I8 under appropriate assumptions. First, we make the following assumptions about the dimension d of the parameter space θ.
Assumption (cf.
He et al. (2019), Assumption 2). The network size is large enough:
d tr(CA-1) T12
(68)
where d is the number of parameters, C the magnitude of the individual gradient noise, the 19(t) Hessian matrix around the global minima, and n2 the intermediate value of |S(0)] is the learning rate, and SS(t) is the batch size.
Eq
18
n(()
This assumption can also be justified as Assumption[]ye Tween the network sizes of neural networks are often extremely large. We obtain the following corollary by combining Eq 10 and Assumption
Corollary (extension of He et al. 2019), Appendix B.3). When all conditions of Theorem 2 and Assumption 2 hold, the generalization bound of the network is negatively correlated with the ratio of the learning rate to the batch size.
Along the proof of Corollary we use Eq 10 k n2 and Assumption Proof of Corollary 2
rather than Eq
and Assumption [
Then, we can obtain
01
(69)
0k
The proof is competed.
21

---

Under review as a conference paper at ICLR 2022
C IMPLEMENTATION DETAIL
C.I DATASETS AND MODELS
C.1.1 DATASETS
We tested the proposed model on two popular image datasets. CIFARIO and CIFARIO0 (Krizhessky et al.) 2009): 60 K natural RGB images of 10 classes for CIFARIO and 100 classes for CIFARTO0 with a train/test split of 50K/10 K. For both datasets, we use PyTorch versior
C.1.2 MODELS
We tested the proposed model using two popular model networks. For CIFARIO, we used VGG16 (Simonyan & Zisserman 2013), and for CIFARION 100, we use WRN28-10 Zaaorrykoo & Komodakis, 2016). For both model networks, we build on the code from the implementation of Kim (2018).
C.1.3 TRAINING
We modified the implementation of Kim 2018). Both datasets are normalized by mean and standard deviation. In the main experiments, training was performed via SGD with momentum of 0.9, and weight decay of 5e-4 for 200 epochs. We began training with a learning rate of Manits run for 200 epochs, and reduced by multiplicative factor of 7 after 60, 120, and 160 epochs to make [finnll Minst.
C.2 ERROR ESTIMATION EXPERIMENT
C.2.1 EXPERIMENTAL DETAILS
As described in Section 6.2 we fit the parameters of Φ to minimize 8(S, r, Φ), using least squares The optimal parameter o²
regression. In doing so, we used scipy.optimme optimize. curve_ 7 is given by
arg min Σ 18(5, (F))
(70)
To measure the performance of the proposed model, the mean μ and standard deviation of the relative error ö(S, 77; x²) are computed based on the fitted parameter d², To evaluate the stability of the model, we a parameter & based on a randomly sampled generalization error e and compute y and from the relative error 8(S, 7/; Φ). The values of and obtained after 100 repetitions shaded within one standard deviation, as shown in Figure
C.2.2 FOUND PHI VALUES
Table 1: The optimal value d' is determined by the least squares regression of relative error.
(a) Constant case
CD
C1
C2
CI
81.92
-7.87
10
1.00
10-4
10
8.20 - 10
301
CIFAR100
8.97
6.45
7.66
10-4
1.50
10-1
7.69
(b) Time- varying case
Co
C1
C2
C3
C4
A
A2
CIFARIO
57.68
1.17
1.56
10
5.23
10
709
8.35
10
1
8.89
CIFAR100
34.77
6.91
9.52
10-4
1.21
10-1
4.03
6.00
10-1
1.63
10
https://githhb..oo////////////
22

---

Under review as a conference paper at ICLR 2022
C.2.3 COMPARISON MODELS FOR THE TIME- VARYING CASE
For the time- varying case in this study, used step decay for the learning rate. Thus, rather than using the mean value theorem of integrals to make approximations, as in En we can obtain a more accurate model by treating the integral value as a constant for each interval as follows:
L n(tt) = =n(0) S/"' F(t')at' + noto) [ F(t')at' = (0) + (tt))
(71)
We call this the analytical solution model. We call the model using only the final learning rate as the stationary model and fit these two models to the generalization error. The comparison results can be found in 2
Table 2: Fitting results of the proposed model and the comparison models for the time-varying case.
CIFARIO
Jl (% 4)
σ (% ()
AIC (L)
stationary model
5
-6.03
23.89
5.08
analytical solution model
13
-2.66
16.15
-98.79 79
proposed model
7
-2.71
16.28
-108.21
(b) CIFARI00
Φ
1 (% {)
(% L)
AIC (L)
stationary model
-4.88
21.88
-27.97
analytical solution model
13
-0.86
9.57
-316.23
proposed model
7
-0.88
9.69
-323.80
Here, the analytical solution model uses step decay and can divide the integration interval into four, and then [Φb = 13. Meanwhile, the stationary model has the same number of parameters as the constant case, |Φb
As shown these results, the analytical solution model obtains the smallest relative error, and the proposed model has almost the same performance with a smaller number of parameters. Assuming that the relative error 5 follows normal distribution (u, o) for the mean and standard deviation a of the relative eтror 8 in the fitted model, we can observe that Akaike's information criterion (AIC) (Akaike 1998) is minimized by the proposed model. Thus, the integral in the proposed model can be approximated sufficiently using the mean value theorem.
C.3 STABILITY EXPERIMENT
C.3.1 EXPERIMENTAL DETAILS
However, there is instability in scipy opt intiimi2 ze. curve_ fit with respect to the initial value of the search parameter $. Thus, we sampled an initial value of Φ from uniform distribution [o, 1] and fitted it several times (10 and 5 times for the constant and time-varying cases, respectively). Then, we used parameter that best fit the sampled data for the stability experiment.
We use the same experimental setup in Appendix
C2.1
23

---

Under review as a conference paper at ICLR 2022
C.4 HYPERPARAMETER OPTIMIZATION EXPERIMENT
C.4.1 BAYESIAN OPTIMIZATION MODEL FOR THE CONSTANT CASE
In this section, we describe the implementation details of the original kernel function proposed in Eq 20 To construct the proposed kernel function, we implemented the following kernel function using sklearn. we..earn.gassee.e.....
www.roocssssesse.......... kernels
from sklearn. gwwssion_precessssseeeeeeeeesese .ee......ecesss...eeeee. kernels import DetProduct, ConstantRernei
tigma_____aae 1att____buuu o_bounds (1e-10, 1e10)
equat wwo.onoopsseeeeeeoooooooooooooee aeppsseeeeeeeeeeeeeeeeeeee
www.soottttttcccccccccoocooe paanstatt_cceeeeeee - PDtPPoduuct (aigma_ "_bounda-aal Boounda-aigma___oooo (_bounde) xv 0.5
roduct (sigme_0 bio b_uunds)
+ UotFroduct (sigma_ t__oooddemssgmaa... h_cuudd ** -0.5
tonstontKermel (1)
sigma_0 Sacla___buuuu bounds decides the range of the σ, which controls the inhomogenity of the kernel.
C.4.2 ALGORITHM FOR THE TIME- VARYING CASE
The proposed model Eq 16 for the time-varying of y = w (b()). as the product term of the parameters of c, À appears. Thus, we employed hy- perparameter search by sequential model-based global optimization (Bergstra al. 2011) T combin- ing the Levenberg-NMeee Gevenberg-Marquuadee Marquardt algorithm (LM) (Moré 1978) and Thompson Sampling (Thompson) 1933 Russo et al.) 2017), directly using the proposed model. The LM is used to solve non-linear least squares problems. It interpolates between the Gauss -eetton algorithm (GNA) and the GD method. It more robust than the GNA, which implies that, in many cases, it finds solution even if it starts very far from the final minimum. It can also be regarded as the GNA using trust re- gion approach. The distribution of the parameter & obtained by minimizing the relative error of 6(S, m 6) =(8.p)))<($S.n) with respect to the parameter & by the LM. The algorithm is as follows. <(Smm)
cannot be represented by linear combination
Algorithm Hyperparameter search algorithm for the time-varying case
H + Ø
sample Φn from U(0,1) 1) for t + to do
max' [ST min arg min Evaluate f( f
mmn 8(S, 17; 11
mar
Expensive step
maz" 2 [S] min
H H U
f( [S] maz"
[ST man
[S] min
μ. Σ + LM H.
sample Φ from trunc-norm(J,, /diag E), blower, Dupper) end for return H
Here, H represents the history of observations, and J' (SS max" TST min represents the evaluation of
the network for hyperparameter (1S) mar' [ST min ). To keep the parameter & in this range, Thomp- son sampling is performed for each parameter from the following truncated normal distribution using the lower bound blower and upper bound bupper.
fx: H. Gr Dlowers Dupper)
(72)
o (00((mun Rupper
Df Nower
where (fxx) is the probability density function of the standard normal distribution as follows:
(xx)
exp
--22
(73)
22
24

---

Under review as a conference paper at ICLR 2022
and ((x) is its cumulative distribution function:
((x) (1 + erf (12))
(74)
C.4.3 EXPERIMENTAL DETAILS
In this section, present the implementation details of the hyperparameter optimization experi- ments for comparison. both constant and time-varying cases, [S]
2 was allowed to explore in the
range of [10-7 10 for CIFARIO and in the range of [10-6 10-2 2] for CIFAR100. These were determined based on the experimental results for each dataset (Figures Ta and lbp. We computed accuracy obtained over 30 rounds of hyperparameter search. By performing this for a total of 100 times, we computed a 95% confidence interval of the maximum accuracy. The proposed method uses uniform distribution search, whereas the comparison method uses uni- form distribution search and log-uniform search. For comparison, we used Bayesian optimization" 4 (Nogueira 2014) using the Matern kernel and RBF kemel, Hyperop (Bergstra et al., 2015), and Optuna (Akiba et al. 2019).
the maximum
25


Reviews:
[{"review_id": "omzQ-uCj9j6", "reviewer": "Reviewer_GHoM", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This looked on the face of it like a strong theoretical paper building on some interesting work to solve a hard problem.  The originality seems to be using PAC-Bayes bounds to model the generalisation performance and to extend previous work by He et al. (2019) to time varying parameters.\n\nUnfortunately, the analysis was not very convincing on both of these aspects.  Having obtained a PAC-Bayes bounds the authors show under a reasonable assumption that it is negatively correlated with the ratio of the learning rate to the mini-batch size (a ratio they call k).  They then propose to model this by equation (14).  Given the infinity of functions that are negatively correlated to choose this function with no justification (it certainly didn't come from their PAC-Bayes bound) is puzzling and rather suggests that the PAC-Bayes bound is not really used.  On the time vary-case the authors don't seem to have noticed that in solving the Stochastic Differential Equation they have scaled the time with the learning rate.  Thus technically equation (9) is wrong (A is a function of time and their should be an integral in the exponent), but there whole analysis doesn't make much sense because they haven't really capture the dynamics.  The model completely ignores the fact that the time changes with the learning rate (which is very important when using a fixed number of epochs).  There are a number of other strange assumptions in their model.  For example, Equation (7) suggests that for sufficiently long time and small learning rate \\theta would go to 0, thus minimising the true risk and not the empirical risk.  This is clearly wrong.  Because you have a limited dataset your gradients of  mini-batch have a bias that means they will minimise the empirical risk, Equation (6).\n\nThe reason the authors get away with half models that don't make much sense is because ultimately they are just fitting rather simple empirical data to some function form. (e.g. Equations (15) and (16)).  This is not really a test of any of the analysis being carried out.  The authors start out with what looks like a reasonably principled approach, but then make unjustified assumption and uncontrolled approximations to obtain what they call the functional form.  Another example of this is the use of the mean-valued theorem.  This provides a bound, but that bound could dramatically change the function form.  That is, you can't assume that \\lambda does not depend on n(t).\n\nI am not sure whether this paper really tells us much.  It contains a lot of algebra, but on close examination none of its seems to hold up.  Of course, the authors are trying to solve a very hard question and they should be commended for this, but they need to show that their modelling assumptions make sense.  Throwing away almost everything to come up with some a functional form really isn't informative.", "summary_of_the_paper": "This paper approximates the learning dynamics by an Ornstein-Uhlenbeck process and uses some PAC-Bayes results to obtain a functional form for the generalisation behaviour as a function of the ration of the learning rate to the batch size.  It obtains results for both constant and time-varying parameters.  It then uses these to develop a kernel function for hyper-parameter optimisation using Gaussian Processes modelling.", "summary_of_the_review": "Superficially this paper looks like a rigorous analysis, but it makes so many dubious assumptions and approximations to ultimately obtaining some rather unconvincing functional forms with enough free parameters to fit almost anything.  This kind of analysis requires far more care, attention to detail and empirical validation than the current paper provides.", "strength_and_weaknesses": "", "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": {}}, {"review_id": "f6Xv0t1NdJE", "reviewer": "Reviewer_sp7W", "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": "Strengths:\n* Derives novel generalization bound for time-varying (learning rate / batch size) ratio.\n* Proposes a novel functional form for the generalization error w.r.t. the (learning rate / batch size) ratio, and empirically show that it is empirically realistic for image classification tasks.\n* Proposes a novel model-based hyperparameter optimization method, which outperforms Bayes optimization baselines that search over the uniform range.\n\nWeaknesses:\n* The proposed model-based hyperparameter optimization searches in uniform range --- I find the argument for using this rather than the logarithmic range baselines not convincing. I don’t see how searching in the uniform range is **more theoretically sound** than the logarithmic range. As for practical usefulness, the proposed method can only match the logarithmic-range baselines in final accuracy with slower convergence.\n\nQuestions:\n* To approximate the learning dynamics as an SDE, the learning rate needs to be small. However, in the experiments, the learning rates aren’t necessarily always small throughout training (e.g. 1/(2^i) i=2,..., 12). Also, larger learning rate corresponds to poorly fitted parts of the models (figure 1). This seems to suggest the proposed hyperparameter optimization method won’t work very well for larger learning rate. Does that agree with your experiment results, and any ideas on how to solve this issue?\n* The model treats terms that contain t as constants (e.g. a0, a1, …, a4). This seems to assume the total number of training epochs to be fixed. However, in practice, early stopping is often needed for better generalization. How would the proposed method deal with potential early stopping?\n", "summary_of_the_paper": "The paper considers the functional relationship between (time-varying) learning rate & batch size and the generalization error. The contributions are summarized below:\n* Assuming quadratic risk function and the SDE limit, the authors derive a novel theoretical generalization bound when the (learning rate / batch size) ratio monotonically decreases.\n* Inspired by the generalization bound, the authors propose a heuristic functional form of the generalization error w.r.t. the (learning rate / batch size) ratio.\n* The authors conduct experiments on CIFAR10 and CIFAR100 datasets, and show that the heuristic generalization error model can fit the actual generalization curve relatively well.\n* The authors propose a novel kernel function for Bayesian optimization in hyperparameter optimization. The kernel function is inspired by the heuristic generalization error model. Empirical results show that the proposed kernel can match or outperform existing Bayes optimization baselines.\n", "summary_of_the_review": "For now, I recommend weak rejection.\n\nI think it is very interesting work that yields novel insights. However the main concerns I have is the limited scope and practical usefulness of the proposed theory / method (seems that it’s limited to a fixed # of epochs and performance isn’t better compared to log-scale Bayes opt methods). I will consider raising my score if my questions are satisfyingly addressed.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "_34-fg9sVCI", "reviewer": "Reviewer_8e8R", "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": "\n-> My main concern is that I am afraid the authors analysis only applies to convex optimization. The main reason is that the eigenvalues of the Hessian at the quadratic minimum also depend in the hyperparameter like learning rate (see for example https://arxiv.org/abs/2003.02218).\n\n-> While one might be able to fit the generalization error to this formula, it does not mean that this formula was actually use by the model, because without a no microscopic understanding of the coefficients. \n\n-> The generalization bound seems to depend only on min and max learning rates. This seems rather weak for hyperparameter tuning because there are many possible learning rate functions with same min and max lr and different generalization. Furthermore, the dependence on the batch size is only through eta/S and it has been shown that generalization is more nuanced (see for example https://arxiv.org/abs/1811.03600).\n\n-> For the hyperparameter tuning comparison to be meaningful, I would recommend comparing with a grid search over parameters. Also, as one changes the learning rate/ batch_size the time to convergence might vary.\n\n-> Some experiments use momentum while the theory uses SGD.", "summary_of_the_paper": "The authors study the learning rate over batch size dependence of generalization bounds and try to use them for hyperparameter tuning.\n\nIn section 4, the authors study generalization bounds for convex optimization with the motivation that this helps understand neural networks. In section 5, the authors use the bounds to propose a functional approximation for the generalization based as a function of the n=eta/|S| scaling of the fluctuations around the minimum, including for the possibility that n is time dependent. The generalization error is roughly a sum of integer powers of sqrt(n). In section 6, the authors the authors fit a set of points to the generalization formula they found. In section 7, the authors use this expression to look for optimal hyperparameters and compare them with other hyperparameter tuning methods.", "summary_of_the_review": "The simplifications of the paper are too big to make any of the claims relevant for real networks. \n\nMain concern is that their functional form only applies to linear regression with SGD.\n\n The functional form that they obtain has very limited predictive power and can be seen as a taylor approximation in sqrt{eta/B}. ", "strength_and_weaknesses": "", "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": {}}, {"review_id": "0yKnMouCJpJ", "reviewer": "Reviewer_P32Z", "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": "The primary strength of the paper lies in the simplicity of the strategy used in deriving the functional form. The extensive study involving overparametrized neural networks and large-scale vision datasets to show that the functional form approximates the generalization error is quite interesting. The authors also showcase the strength of their proposed model in hyperparameter optimization.\n\n\nQuestions:\n\n1) The covariance matrix $C$ being assumed a constant for all $\\theta$ is a very strong assumption, which is very unlikely to hold true for the overparametrized neural networks in practice. Can the authors somehow loosen the assumption by using some form of average covariance matrix over the trajectory?\n \n2) PP 109-110 in Gardiner, 2004 shows the analytic solution to eq. (4) when $g(\\theta) = A \\theta$. Are the authors assuming the risk as $\\frac{1}{2} \\theta^T A \\theta$ throughout the trajectory starting from some random initialization $\\theta(0)$? That will imply, the authors are only considering a quadratic loss function, which has a single global minimum.\n\nOne way to handle the issues mentioned in (1) and (2) can be the following:\nAssume that after several iterations of SGD, the parameters finally converge close to an attractor local minimum $\\theta^{\\star}$ with hessian $A$. Then, with $\\theta(0)$ starting in a neighborhood around $\\theta^{\\star}$, assuming that the covariance matrix $C$ is nearly a constant in the neighborhood, the authors can get eq. (7) as the analytic solution of the final distribution around the local minimum.\n\n\n3) [Experiments] How were the models initialized in the 60 VGG experiments? Was the initialization the same in all the cases? For each LR / batch size ratio, how does the generalization change across multiple initializations? Does the fitted curve change drastically when one considers multiple initializations for different LR / batch size ratios?\n\n", "summary_of_the_paper": "The authors study the dependence of generalization error of trained neural networks on the batch size and the learning rate used in SGD. The primary motivation is to extend the previous works to the case where batch size and learning rate change over the trajectory. The authors present a functional form using PAC-based generalization bounds to model the desired dependence. They conduct extensive experimentation to show that the functional form approximates the generalization error well. In addition, the authors show that a hyperparameter search based on the proposed model outperforms existing hyperparameter optimization libraries like Hyperopt and Optuna.", "summary_of_the_review": "Overall, I believe the primary strength of the paper lies in the extensive experimental study to corroborate their claim. The major theorems need some restructuring to remove the confusions that may arise (e.g., see (1) and (2) in my review) from the current state. Hence, my scores are currently on the borderline. I am happy to increase my scores after discussing with the authors and other reviewers in the discussion period.", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper derives a PAC-Bayes generalization bound for SGD and uses the results to postulate a functional form for the generalization error as a function of the ratio of the learning rate to the batch size. This functional form is then leveraged to develop a kernel function GP hyperparameter optimization.

The reviewers favorably viewed the novel PAC-Bayes bound, but were not convinced by the subsequent analysis. In particular, the reviewers expressed some skepticism about the soundness and generality of the proposed functional form, and were unconvinced that the method would be useful in practice. As such, I cannot recommend the paper for acceptance.
Decision: Reject