Bolstering Stochastic Gradient Descent with Model Building
Authors: Ilker Birbil
Özgür Martin
Gönenc Onay
Figen Öztoprak
Venue: ICLR 2022 Submitted (2022)
Keywords: Stochastic Line Search
Stochastic Model Building
Non-convex Stochastic Optimization
Unconstrained Optimization

Abstract: Stochastic gradient descent method and its variants constitute the core optimization algorithms that achieve good convergence rates for solving machine learning problems. These rates are obtained especially when these algorithms are fine-tuned for the application at hand. Although this tuning process can require large computational costs, recent work has shown that these costs can be reduced by line search methods that iteratively adjust the stepsize. We propose an alternative approach to stochastic line search by using a new algorithm based on forward step model building. This model building step incorporates a second-order information that allows adjusting not only the stepsize but also the search direction. Noting that deep learning model parameters come in groups (layers of tensors), our method builds its model and calculates a new step for each parameter group.  This novel diagonalization approach makes the selected step lengths adaptive. We provide convergence rate analysis, and experimentally show that the proposed algorithm achieves faster convergence and better generalization in most problems. Moreover, our experiments show that the proposed method is quite robust as it converges for a wide range of initial stepsizes.

Under review as a conference paper at ICLR 2022
BOLSTERING STOCHASTIC GRADIENT DESCENT WITH MODEL BUILDING
Anonymous authors Paper under double-blind review
ABSTRACT
Stochastic gradient descent method and its variants constitute the optimization algorithms that achieve good convergence rates for solving machine learning problems. These rates are obtained especially when these algorithms are fine- tuned for the application at hand. Although this tuning process can require large computational costs, recent work has shown that these costs can be reduced by line search methods that iteratively adjust the stepsize. We propose an alternative approach to stochastic line search by using a new algorithm based on forward step model building. This model building step incorporates a second-order information that allows adjusting not only the stepsize but also the search direction, Noting that deep learning model parameters come in groups (layers of tensors), our method builds its model and calculates a new step for each parameter group. This novel diagonalization approach makes the selected step lengths adaptive. We provide convergence rate analysis, and experimentally show that the proposed algorithm achieves faster convergence and better generalization in most problems. Moreover, our experiments show that the proposed method is quite robust as it converges for a wide range of initial stepsizes.
INTRODUCTION
Stochastic gradient descent (SGD) is a popular optimization algorithm for machine learning problems which can achieve very fast convergence rates when its stepsize and its scheduling are tuned well for the specific application at hand. This tuning procedure can take up to thousands of CPU/GPU days resulting in big energy costs AAi & Duchi 2019).
A number of researchers have studied adaptive strategies for improving the direction and the stepsize choices of the stochastic gradient descent algorithm. Adaptive sample size selection ideas (Byrd et al. 2012 Balles et al. 2016 [Bolaapragada et al., 2018) improve the direction by reducing its variance around the negative gradient of the empirical loss function, while stochastic quasi- quasi-Newton algorithms (Byrd et al. 2016 Wang et al., 2017)) provide adaptive preconditioning. Recently, several stochastic
line search approaches have been proposed. Not surprisingly, some of these work cover sample size
selection component of the proposed line search algorithms (Balles al., 2016
Paquette &
Scheinberg 2020).
The Stochastic Model Building (SMB) algorithm proposed in this paper is not designed as stochastic quasi-Newton algorithm in the sense explained by Bottou et al. (018). However, it still produces a scaling matrix the process of generating trial points, and overall step each outer iteration can be written in the form of matrix-vector multiplication. Unlike the algorithms proposed by Mokhtari & Ribeiro (2014) and (Schraudolph et al. (2007). we have no accumulation of curvature pairs throughout several iterations. Since there is no memory carried from earlier iterations, the scaling matrices in individual past iterations are based only on the data samples employed those iterations. other words, the scaling matrix and the incumbent random gradient vector are dependent.
Vaswani et al, (219)) apply a deterministic globalization procedure on mini-batch loss functions. That is, the same sample is used in all function and gradient evaluations needed to apply the line search procedure at given iteration. However, unlike our case, they employ a standard line search procedure that does not alter the search direction. They establish convergence guarantees for the empirical loss function under the interpolation assumption, which requires each component loss function to have zero gradient at minimizer of the empirical loss. Mutschler & Zell (002)) assume that the

---

Under review as a conference paper at ICLR 2022
optimal learning rate along the negative batch gradient is good estimator for the optimal learning rate with respect to the empirical loss along the same direction. They test validity of this assumption empirically on deep neural networks (DNNs). Rather than making such strong assumptions, we stick to the general theory for stochastic quasi-Newton methods.
Other work follow different approach translate deterministic line search procedures into stochas- tic setting, and they do not employ fixed samples. In |Mhserecc Hennig (2017). a probabilistic model along the search direction is constructed via techniques from Bayesian optimization. Learning rates are chosen to maximize the expected improvement with respect to this model and the probability of satisfying Wolfe conditions. Paquette & Scheinberg (2020) suggest an algorithm closer to the deterministic counterpart where the convergence is based on the requirement that the stochastic function and gradient evaluations approximate their true values with a high enough probability.
With our current work, we make the following contributions. We use model building strategy for adjusting the stepsize and the direction of a stochastic gradient vector. This approach also permits us to work on subsets of parameters. This feature makes our model steps not only adaptive, but also suitable to incorporate into the existing implementations of deep learning networks. Our method changes the direction of the step well as its size which separates our approach from the backtracking line search algorithms. It also incorporates the most recent curvature information from the current point. This is in contrast with the stochastic quasi-Newton methods which the information from the previous steps. Capitalizing our discussion on the independence of the sample batches, we also give convergence analysis for SMB. Finally, illustrate the computational performance of our method with a set of numerical experiments and compare the results against those obtained with other well-known methods.
STOCHASTIC MODEL BUILDING
We introduce new stochastic unconstrained optimization algorithm in order approximately solve problems of the form
(x))=BFF(( JF
min
where F: R" x R + R is continuously differentiable and possibly nonconvex, & Rd denotes a random variable, and [[[] denotes the expectation taken with respect to E. We assume the existence of a stochastic first-order oracle which outputs stochastic gradient g(v, g) of for given x. A common approach to tackle (T) to solve the empirical risk problem
min =
f(x) f(x)
Σ f(x).
where fi R -> IR is the loss function corresponding to the ith data sample, and N denotes the data sample size which can be very large in modern applications.
As an alternative approach to line search for SGD, we propose a stochastic model building strategy inspired by the work of Öztoprak & Birbil 2018). Unlike core SGD methods, our approach aims at including curvature information that adjusts not only the stepsize but also the search direction. Öztoprak& Birbil 2018) consider only the deterministic setting and they apply the model building strategy repetitively until a sufficient decent is achieved. In our stochastic setting, however, we have observed experimentally that multiple model steps does not benefit much the performance, and its cost to the run time can be extremely high in deep learning problems. Therefore, if the sufficient decent not achieved by the stochastic gradient step, then we construct only one model to adjust the size and the direction of the step.
Conventional stochastic quasi-Newar methods adjust the gradient direction by a scaling matrix that is constructed by the information from the previous steps. Our model building approach, however, uses the most recent curvature information around the latest iteration. In the popular deep learning model implementations, model parameters come in groups and updates are applied to each parameter group separately. Therefore, we also propose to build a model for each parameter group separately making the step lengths adaptive.
The proposed iterative algorithm SMB works as follows: At step k, given the iterate Zg. we calculate the stochastic function value fs f(xx, Ex) and the mini-batch stochastic gradient
2

---

Under review as a conference paper at ICLR 2022
Os 1 Ex= ( Tk. where my is the batch size and fa (5x, 1: ................................ Ek,me) is the realization of the random vector &. Then, apply the SGD update to calculate the trial step si = -k where {a+}& a sequence of learning rates. With this trial step, we also calculate the function and gradient values f f ( [x) and of g( Ek) at ot I + sk. Then, we check the stochastic Armijo condition
ma
f S - cap 19
where с > O is hhpphy-pppaaat nnpper-aarameter. the condition satisfied and we achieve sufficient decrease, then 1 1 = . the step. If the Armijo condition is satisfied, then build a quadratic model using the linear models at the points Fx,p and k. for each parameter group p and find the step SR,y to reach its minimum point. Here, ZR,p and ark.p denote respectively the coordinates of and #'e that corresponds to the parameter group p. We caleulate the next iterate #x++1 2i 8k. where 8 = ($ Sk.p.. and n is the number of parameter groups, and proceed to the next step with zx+11 This model step, needed, requires extra mini-batch function and gradient evaluations (forward and backward pass in deep neural networks).
For each parameter group p, the quadratic model built by combining the linear models Tk,p and rk k.pp given by
(s) = fkip + Dk.ps and (s - skpp)= = Sh + (okkp) sk
respectively. Then, the quadratic model becomes
(s) = (s)p(()( + (s) skpp)
where
(s - sk.pp) T ( and alp
8 Tohk (sk skpppp Ts
(- kkppp) ) (
The constraint
|| + ||s
k 1 S 1l
is also imposed so that the minimum is attained in the region bounded by 2k,y and xh.p This constraint acts like a trust region. Figure I shows the steps of this construction.
In this work, solve relaxation of this constrained model as explained in Oztoprak & Birbil 2018 Section 2.2). The minimum value of the relaxed model attained at the point Tk,p + 8k,p with
Cg.pp()) Cy.p (o))kk) + Ca.p (5)s())
Sk.p
where yk.pp = sh.p Dh.pp Here, the coefficients are given as
||shpp1
|| 1|2
(6)
(0)
|- (Vk, sk.p + 20) T 9k. + 11sh.pl12v..pp...m pk.pp...ppp
28
280
|s 11?
(o.
[- (yh 28) 22)) + (s gr.pl.
280
with
0= (ITpshh 28) || and = 2 [|sk (IEAaall + [119..01]] (oppll)-mhppe whpsii (5)
where < < 1 is a constant which controls the size of sk,p by imposing the condition ||skppll n Then, the adaptive model step becomes 8y (sk.p....., sk.p.). We note that our construction in terms of different parameter groups lends itself to constructing a different model for each parameter subspace.
3

---

Under review as a conference paper at ICLR 2022
125
7.0
100
30
0,50
0.59
-0.25
-0.00
3.2 0.4
1.0 200
An iteration of SMB on a simple quadratic function. For simplicity we assume that there only parameter group, and hence, we drop the subscript p. The algorithm first computes the trial point r by taking the stochastic gradient step s If this point is not acceptable, then it builds model using the information at 2& and o/t and computes the next iterate Fk++1 2 + 8g- Note that 8 not only have a smaller length compared to the trial step s but also lies along a direction decreasing the function value.
Figure I:
We summarize the steps of SMB in Algorithm ! Line 5 shows the trial point, which is obtained with the standard stochastic gradient step. If this step satisfies the stochastic Armijo condition, then
proceed with the next iteration (line 8 Otherwise, we continue with bulding the models for each parameter group (lines I0 and move to the next iteration with the model building step in line
Algorithm 1: SMB: Stochastic Model Building
Input: 21 E R", stepsizes {ax {a mini-batch sizes {mx | > 0, and amar satisfying
for k = ,,...,Tdo do
fa = f(rx, Ex), 9k = Ei g(oxx En.i);
o -akgRi
o 3k + s/;
S 5(12 (x), g = Em oxth.
me
ft f& C az 11 then
Fx+1= = x//
else
10
for p = 1, L..... n2 do
sk.p Dhp gk.ps
sk.p cg.p 1k.p Cy.p (6)p(0))kk. Ca.p (O)s
13
Øk+1 = Ib + Sy with (sk.p..... sk,p,);
CONVERGENCE ANALYSIS
The steps of SMB can be considered as special quasi-Newton update:
Fk++ = Tx or Hegh.
(6)
where Hy is symmetric positive definite matrix as an approximation to the inverse Hessian matrix. In Appendix I we explain this connection and give an explicit formula for the matrix H4, We also prove that there exists n, > such that for all & the matrix H₃ satisfies
KT Hg 2 kT.
4

---

Under review as a conference paper at ICLR 2022
where for two matrices A and B, A means B - A is positive semidefinite. It is important to note that H3 is built with the information collected around 2y. particularly, 9k. Therefore, unlike stochastic neasi- methods. H3 is correlated with Jk. and hence, [[ is very difficult to analyze. Unfortunately, this difficulty prevents us from using the general framework given by Wang al. (2017).
To overcome this difficulty and carry on with the convergence analysis, we modify Algorithm | such that H& is calculated with new independent mini batch, and therefore, it is independent of gk- By doing so, we still build a model using the information around zy. Assuming that Oh is an unbiased estimator of ff, we conclude that E H H₁ f. In the rest of this section, we provide convergence analysis for this modified algorithm which we will call as SMBi (i for independent batch). The steps of SMBi are given in Algorithm 2 step with new random batch.
As Step 11 shows, we obtain the model building
Algorithm 2: SMBi: H₁ with independent batch
Input: 21 E R", stepsizes {a mini-batch sizes {mx 1 > O, and amaz satisfying
for k = 1..... do
fa = f(rx, Ex), 9h = L Di gx En.i):
K -UNgRi
2 = 0k + t
fh 5( g
- EM g( E):
me
ft fk aa g then
Tk+1 2t/
else
10
for p = I,... do
11
Choose new independent random batch c/=
gh 1 Em ( Ch
my
(ot) -akK (xh) 3k (8k)':
(of)) = 1 Ei (x , Ek,)) veep (okep) - Ik.pi
me
Sk.p -0g pooks where Hkppp is calculated using d and 1/2 as defined in
Appendix A.1
16
0k+1
23 + 8y with Sy (sk.1...... sk.n):
Assumptions: Before providing the analysis, let us assume that f : R" > R is continuously differentiable, lower bounded by flow and there exists L >> O such that for any æ, y R" [ fy(y)) < L|| - y|l. We also assume that &v. & 2 1, are independent samples and for any iteration k. & is independent of { [g(2,, [x)] V (лx) and REg [llg(*,, Ex) fxxx)) o² for some > 0.
In order to be in line with practical implementations and with experiments, we first provide an analysis covering the constant stepsize case for (possibly) non-convex objective functions.
Below, we denote by Eạz (EI .c....., (T) the random samplings in the first T iterations. Let Omaa be the maximum stepsize that is allowed in the implementation of SMBi with
-1 + /1 + 1672
Omaa
4Lm
This hyper- parameter of maximum stepsize is needed in the theoretical results. The same parameter also be used to apply automatic stepsize adjustment (see numerical experiments with stepsize auto-scheduling in Section 4.2). Observe that since 1 >>>>>> 1, assuming L 2 1 implies that it suffices choose amaz to satisfy The proof of the following convergence result given in Appendix
Theorem 1. Suppose that our assumptions above hold and {xx} } is generated by SMBi as given in
Al Algorithm Suppose also that {ag) in Algorithm 2 satisfies that O ax. 2/m -1 2T2 amaa)) S
5

---

Under review as a conference paper at ICLR 2022
Omax for all k. For given T, R be random variable with the probability mass function
ax/(n + 2Lamaa) az.
PR(K) = P( k= (1) + 2Lammax) 112
for k 1, 1,.... T. Then, we have
D,+ (6 (af
E [
Σ Ek= 2Lx 0z L/2)
where Dj = f(z1) frow and the expectation is taken with respect to R and Eir- Moreover, if we choose Og = (Im + (mm3))) and my m. -oror all l- = -..... then this reduces to
B |[[V)()))] 2L( + 2La D o²
T
m
Using this theorem, it is possible to deduce that stochastic first-order oracle complexity of SMB with random output and constant stepsize is O(e-²) (Wang et al. 2017 Corollary 22).
In (Wang et al. 2017 Theorem 2.5), it is shown that under our assumptions above and the extra assumption of 0 < ag S Lín 142Lamas] S Ommo if the point sequence {z is generated by SMBi method (when He is calculated by independent batch in each step) with batch size my
for all k; then there exists positive constant M, such that E fxxx )] S My.. Using this observation,
the proof of Theorem I and Theorem 2.8 in (Wang al. (017). can also give the following complexity result when the stepsize sequence is diminishing for non-convex objective functions.
Theorem 2. Let the batch size be m and assume that Oi Ll +2l0mar)
with Φ E (0.5, 1)
for all k. Then {xx} generated by SMBi satisfies that
0²
Σ ElIVS(>W)11 s 2 - + 2Lommo) flow y
(T T-1)
(1 - 6)
for some M, > O, where T denotes the iteration number. Moreover, for a given e E (0, 1), to guarantee that + ET [[[V/(<>>]] < e, the number of iterations needed is at most O T-0))
We are now ready assess the performance SMB and SMBi with some numerical experiments.
NUMERICAL EXPERIMENTS
In this section, we compare SMB and SMBi against SGD, Adam Kingma & Ba (015).. and SLS (SGD+Armijo) Vaswani al. (019). We have chosen SLS since it recent method that stochastic line search with backtracking. We have conducted experiments on multi-class classification problems using neural network modelş The codes conduct experiments are given in the supplementary file.
4.1 CONSTANT STEPSIZE
We start our experiments with constant stepsizes for all methods. We should point out that SLS method adjusts the stepsize after each backtracking process and also uses stepsize reset algorithm between epochs. We refer to this routine as stepsize auto-scheduling. Therefore, we find it unfair compare SLS with other methods with constant stepsize. Please, see Section 4.2 for discussion about stepsize auto-scheduling using SMB.
MNIST dataset. On the MNIST dataset, we have used the one hidden-layer multi-layer perceptron (MIP) of width 1,000. We compare all methods after cross-validate validating their best performances from the set of learning rates, {0.001, 0.000,,001,,,,1 0.1, 0.25, 0.5, 0. 75, 1.0). For SMB and SI.S, we have
The implementations of the models taken from bctps://githhie
ssaa radji /s1s

---

Under review as a conference paper at ICLR 2022
used the default hyper-parameter value 0.1 of SLS that appears in the Armijo condition (also recommended by the authors of SLS)
VIASE MIP
V8.5T MP
VIIST MIP
01857
Cor
to
5.00
5.000
vitel trad
6M2
sitel fred
m
190
252
Tr0m
1750
Thn 1000 1250
Sooch
Timm
(a) Epochs
(b) Run Time
Figure 2: Classification on MNIST with an MLP model.
In Figure 2
see the best performances of all five methods the MNIST dataset with respect to epochs and run time. The reported experiments consist of five independent runs where results are averaged. Even though SMB and SMBi may calculate an extra function value (forward pass) and a gradient (backward pass), we see in this problem that SMB and SMBi achieve the best performance with respect to the run time as well as the number of epochs. More importantly, the generalization performances of SMB and SMBi are also better than the remaining three methods.
should be pointed out that, in practice, choosing new independent batch means the SMBi method can construct model step in two iteration using two batches. This way the computation cost for each iteration is reduced but the model steps can only be taken half of the iterations in the epoch. As seen in Figure 2 this does not seem to effect the performance significantly.
CIFAR10 and CIFAR100 datasets. For the CIFAR1O and CIFAR100 datasets, we have used the standard imag--laassiicee
architectures ResNet-34 (He et al. 2016 and DenseNet- 121 (Huang
jet al. 2017) Due to the high computational costs of these architectures, we report the results of a single run of each method. For, Adam have used the default learning rate 0.001, and for SGD, have set the tuned learning rate to 0.1 as reported in Vaswani et al. 2019). For SMB and SLS, we
have again used the default learning rate of 1.0 and Armijo constant 0.1 of SLS.
CEARIO ResNet33
CITAR1O ResNei:34
CITARIC Reshet33
ATARID ResNe:33
Traiing Sontha Loss (lg)
w
2M24
24E F-1
SMB: I--1
0,05
0,355
4M Wi!!
com
fradi 1011
15"1
frai
0325
0.915
0.555
0,005
Adam
0.000
0.90
Adam 2001
0,00
300
Epochs
Time
Time
(a) Training Loss
(b) Test Accuracy
CIFAR100 ResNeL34
OFAR1OO Re34Ne34
CIFARIO3-ReS
Taning Sobmec Loss (log)
SM45 tnd
SMB bio
Stedi low)
10P
Iivd nol Sob, In-0.
200, I--03
241 P-11
24-
248. I-11
S4B: I--1
0.2
5.55
SLD bwiL
1453
Epochs
(c) Training Loss
(d) Test Accuracy
Figure 3: Classification on CIFARIO (a. b) and CIFARIO0 (c. d) with ResNet-34 model.
we see that CIFARIO- and Reenet,,,, SMB performs better than Adam and SGD algorithms. However, its performance is only comparable to SLS. Even though SMB reaches a lower loss function value in CIFAR 100-Resnet34, this advantage does not show in test.
In Figure g
7

---

Under review as a conference paper at ICLR 2022
accuracy. As mentioned in the beginning of this section, SLS method adjusts the stepsize after each backtracking process and, in order to prevent diminishing stepsizes, it uses a stepsize reset algorithm between epochs. SMB does not benefit from this kind of stepsize auto-scheduling. We will define an auto-scheduling for SMB stepsizes in Section so that we obtain a fairer comparison between SMB and SLS..
CIRAR1OD Ven
CIFAR100
CIFAR1OD DenseNet
DenseNet
Thaiiing Softr ax Loos tegi
2.5 1-1
R5S. Po1
Teal- AEEurAcy
1.b
1.5
14
11-1
0.5
52
F-1
9.5:1-1
I-1
20
150
150
250
2000
32300
13300
30
320
350
3006
33X3
1900
(a) Training Loss
(b) Test Accuracy
Figure 4: Classification on CIFARI00 with DenseNet- 121 model.
In Figure 4
21. SMB with a constant stepsize outperforms SLS on train loss and reaches to high test accuracy before SLS. Vaswani et al. (2019) show that SLS with these settings outperforms Adam and SGD on this problem both in terms of traning loss and test accuracy.
comparison of performances of SMB and SLS
4.2 STEPSIZE GUTO-SCHEDULING
As expected SMB can take many model steps, when learning rate is too large. Then, extra mini-batch function and gradient evaluations can slow down the algorithm (c.f., Figure B We believe that the number of model steps taken in an epoch (when the Armijo condition is not satisfied) can be good measure to adjust the learning rate in the next epoch. This can lead to an automatic learning rate scheduling algorithm. We did preliminary experiments with simple stepsize auto-scheduling routine, The results are given in Figure 5 At the end of each epoch, we multiply the stepsize by 0.9 when the model steps taken in an epoch is more than 5% of the total steps taken. Otherwise, we divide the stepsize by 0.9, unless the division ends up with a stepsize greater than the maximum stepsize allowed, Omaz. The value 0.9 the backtracking ratio of SLS and we consider 5% a hyper-parameter. Figure shows, on the training loss, that both SMB and SMBi perform better than the other methods. For the test accuracy, SMB performs better than all other methods, and SMBi performs comparable to SLS.
OFAR1O
0,500 CIFARCC- OFARIC-ResMet34
QFAR1D-ResNe-34 ResNe:34
Traiiing Sontrox Loss 00g)
0.400
10-
SHB AutSeh:
SLic 1
5.0000
SCD
usto
G.C: indl
0330
GLC. Indl
56.1
SGD In
100 Procchs
350
202
200C
8000
0,000
122 Ppachs
230
2004
4300
5300
Time
Time
(a) Training Loss
(b) Test Accuracy
Figure 5: Performances of SMB and SMBi with auto-scheduled stepsizes on CIFARIO.
4.3 ROBUSTNESS WITH RESPECT TO STEPSIZE
Our last set of experiments are devoted to demonstrating the robustness of SMB. The preliminary results in Figure 0 show that SMB is more robust to the choice of the learning rate than Adam and SGD, especially in deep neural networks. This aspect of SMB needs more attention theoretically and experimentally.
8

---

Under review as a conference paper at ICLR 2022
Training Softmax Loss (log)
CIFAR10-ResNet33
MNIST-MLP
10a
10-1
SMB: 1r=0.1 0.1
SMB: 0.25
10-1
10-2
SMB: 0r5
SMB: Ir= 0.75
10-2
10-3
10-3
10
100 Epochs
200
50
100
Epochs
Figure 6: Robustness of SMB under different choices of the learning rate.
CONCLUSION
SMB is a fast alternative to stochastic gradient method. The algorithm provides model building approach that replaces the one-step backtracking in stochastic line search methods. We have analyzed the convergence properties of modification of SMB by rewriting its model building step quasi- Newton update and constructing the scaling matrix with new independent batch. Our numerical results have shown that SMB converges fast and its performance is much more insensitive to the selected stepsize than Adam and SGD algorithms. In its current state, SMB lacks any internal learning rate adjusting mechanism that could reset the learning rate depending on the progression of the iterations. As shown in Section 3 SMB can greatly benefit from stepsize auto-scheduling routine. This is future work that will consider.
Limitations. Our convergence rate analysis is given for the alternative algorithm SMBi which can perform well agains other methods but consistently underperforms the original SMB method. This begs for convergence analysis for the SMB method.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Hilal Asi and John C. Duchi. The importance of better models in stochastic optimization. Proceedings of the National Academy of Sciences, 116(46):22224222933) 2019. ISSN 0027-8424. doi:
10.1073/pnas. 19tp///ass11001811111 1908018116 16. URthttps: www..wpppaa...omm
Lukas Balles, Javier Romero, and Philipp Hennig. Coupling adaptive batch sizes with learning rates.
arXiv preprint arXiv: 1612.0500, 2016. URL (KLLtttts///zzzi..rorr/
05086
Raghu Bollapragada, Richard Byrd, and Jorge Nocedal. Adaptive sampling strategies for stochastic optimization. SIAM Journal Optimization, 28(4):3312-3345 2018.
Léon Bottou, Frank Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM Review, 60(2):223-3 311, 2018.
Richard H Byrd, Gillian M Chin, Jorge Nocedal, and Yuchen Wu. Sample size selection in optimiza- tion methods for machine learning. Mathematical Programming, 134(1):127-155, 2012.
Richard Byrd, Samantha L Hansen, Jorge Nocedal, and Yoram Singer. A stochastic quasi-newton method for large-scale optimization. SIAM Journal on Optimization, 26(2):1008-10) 2016.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image
recognition. CVPR, 2016.
Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. Densely connected convolutional networks. CVPR, 2017.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Yoshua Bengio and Yann LeCun (eds.), 3rd International Conference Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings. 2015. http? //axxivorra/a
1112 6980
Maren Mahsereci and Philipp Hennig. Probabilistic line searches for stochastic optimization. The Journal of Machine Learning Research, 18(1):4262 -42222222432,,,, 2017.
Aryan Mokhtari and Alejandro Ribeiro. Res: Regularized stochastic bfgs algorithm. IEEE Transac- tions on Signal Processing, 62(23):6089-6104, 2014.
Maximus Mutschler and Andreas Zell. Parabolic approximation line search for duns. arXiv preprint arXiv: 1991, 2020.
11991
Figen Öztoprak and ilker Birbil. An alternative globalization strategy for unconstrained optimization. Optimization, 67(3):377-392, 2018. 2018.
Courtney Paquette and Katya Scheinberg. A stochastic line search method with expected complexity analysis. SIAM Journal on Optimization, 30(1):349-376, 2020.
Nicol N Schraudolph, Jin Yu, and Simon Günter. A stochastic quasi-newton method for online convex optimization. In Artificial Intelligence and Statistics, pp. 436 443. PMLR, 2007.
Sharan Vaswani, Aaron Mishkin, Issam Laradji, Mark Schmidt, Gauthier Gidel, and Simon Lacoste- Julien. Painless stochastic gradient: Interpolation, line-search, and convergence rates. arXiv preprint arXiv:995.009997 2019.
09997
Xiao Wang, Shiqian Ma, Donald Goldfarb, and Wei Liu. Stochastic quasi-newton methods for nonconvex stochastic optimization. SIAM Journal on Optimization, 27(2):927-955 2017.
10


Reviews:
[{"review_id": "jBN0St3PyAx", "reviewer": "Reviewer_hEnG", "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": "Strengths  \nThere is some novelty in the proposed algorithm, and the paper has made some efforts to extend the model building approach to the stochastic setting. \n\nWeakness\n\n1. From theoretical side, by enforcing a relatively strong independence batch assumption, the convergence analysis is not a surprise given the reference Wang 2017. However, the experiments shows that SMB  consistently outperforms SMBi, it seems to me that dependence is the key for getting better performance.  Hence, it is unsatisfactory if the convergence property of SMB is not demystified and completely ignored.\n\n2. Since the paper has targeted its proposed algorithm a special case of quasi-newton method (e.g. (6)), it would be unsatisfactory if comparison with SQN is not made. \n\n3. The experiment conclusion is based on a single run, it is not convicing to me that the reported advantage of SMB is as reliable as described. I would recommend spending more time effort in the experiments before submission.\n\n4 Figure 3 shows that SLS outperforms SGD and ADAM while SGD and ADAM outperform SMB and SMBi. The last figure shows that SMB with Auto-scheduled stepsize performs slightly better than SLS. What is the most important factor in getting good performance? Would the benefits mainly come from the Auto-scheduled stepsize? Can we equip SGD or ADAM with similar scheduled stepsize? This appears to be very promising. \n\n\nSome minor issues.\n1. \\mathbb{E}[F(x; \\xi )] is deﬁned at the beginning but never used.\n\n2. It is confusing that $n$ is used to deﬁne both the number of parameter blocks and the dimension of X.\n\n3. What is  $f_{k,p}$ defined in page 3?\n\n", "summary_of_the_paper": "The paper presents a stochastic version of the model building algorithm (SMB)  by taking the subsequent iterate to be the minimizer of a quadratic model build from two iterates (the current and the one based on conventional SGD). Empirical results suggest that the proposed SMB has some great generalization performance.", "summary_of_the_review": "While this paper makes some interesting contribution of a new stochastic algorithm for deep learning, it appears to be far from a complete work. I think the paper needs to be substantially improved in both theory and empirical study.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "c8DXxlwh7ZD", "reviewer": "Reviewer_4z74", "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**\nThe proposed method SMB/SMBi has several advantages. First of all, unlike general preconditioned stochastic gradient methods, the preconditioner here is a blockwise diagonal matrix where each block corresponds to a parameter group in the deep neural network. In addition, because the preconditioned update is only expressed so to facilitate theoretical analysis, the actual implementation itself does not involve computing or storing matrices at all --- only vector inner products are involved in each parameter group update. This is particularly suitable for implementation in popular deep learning libraries like PyTorch where parameters are stored in groups. \n\nSMB also does not use backtracking as is typical in line search with the Armijo condition. When the condition is failed for the stochastic gradient direction, SMB simply computes a new direction based on a stochastic \"quasi-Newton\" update, and take a step along this direction instead. This lets SMB avoid potentially doing many additional forward passes which can be expensive. \n\nFinally, the empirical results show that by using additional simple heuristics to adjust the step size based on how often the Armijo condition has failed in the previous epoch, SMB can achieve state-of-the-art performance on CIFAR10 with a ResNet34 architecture, both in terms of the training loss and test accuracy. \n\n\n**Weaknesses**\nThe main concerns I have with this paper are:\n1. Although convergence results are given in the non-convex setting, the analysis is rather trivial. The crux of the proofs for the theorems is to first re-write the SMB/SMBi update as a preconditioned stochastic gradient step $x_{k+1} = x_k - \\alpha_k H_k g_k$, and this part comes directly from the work of Oztoprak and Birbil (2018) except here the deterministic gradients are replaced with their stochastic counterparts. Then the proof boils down to bounding the extreme eigenvalues of each of the diagonal blocks in $H_k$. This part of the analysis is also nearly identical to what's in Oztoprak and Birbil (2018). Finally, with the extreme eigenvalues at hand, the non-convex results given by Wang et al. (2017) can be directly invoked to obtain Theorem 1 and 2 in this paper. The theoretical analysis therefore is simple as previous works have done all the heavy-lifting,  but at the same time I consider the contribution to be neither novel nor significant.\n2. Because the algorithm is directly adapted from that of Oztoprak and Birbil (2018), the preconditioner $H_k$ would be correlated with the stochastic gradient. This would not fit into the analysis of Wang et al. (2017) as their theory requires $H_k$ to be independent of $\\nabla f(x_k,\\xi_k)$ conditioned on the past. The algorithm in Wang et al. (2017) constructs $H_k$  based on a truncated history of the past stochastic gradients and therefore is independent of the randomness in iteration $k$. To circumvent this issue, the authors here suggest to analyze a different version of SMB, which uses an independent minibatch to compute $H_k$, and the variant is named SMBi. Although this lets the analysis go through, it inevitably introduces a *gap between theory and practice*, since the experiments demonstrate that SMB almost always perform better than SMBi. This observation makes sense as although we are using stochastic quantities to construct the model, the model can be seen as a locally approximation to the minibatch objective, while using independent batches to compute the model does not seem to make a lot of sense. \n3. Figure 1: Although it is true that in this particular case (seed, rather), \"$s_k$  has a smaller length compared to the trial step $s_k^t$, the step we would have taken with $s_k^t$ is usually scaled with a step size instead of the unit step size taken by $s_k$ in SMB. More importantly, the direction obtained in $s_k^t$, the stochastic gradient step depends on which feature vector $\\xi_k$ is sampled, and so it shouldn't always be the case that $s_k^t$ \"lies along a direction decreasing the function value\" while $s_k$ does not, unless this can be proven otherwise. For these reasons I find this illustration slightly misleading. \n4. Robustness to step size: assuming the experiments in Figure 6 are using constant step sizes, it is unclear to me what the point of robustness to step size means given that SMB/SMBi only works well in general when step size auto-scheduling is required. If the authors indeed recommend the step size heuristic in Section 4 to be adopted in practice, then I see little value in this robustness experiment, but I could be interpreting the experiment incorrectly. Instead, I would recommend a robustness experiment on the other hyperparameters such as the percentage threshold mentioned in Section 4 and the step size multiplication factor. The last issue I have with Figure 6 is it seems like for MNIST-MLP, different step size can lead to an order of magnitude difference in the final training loss. Does that imply SMB isn't very robust to the step size on this dataset/model combination?\n5. It would be great to see a replication of the auto-scheduling experiment on CIFAR100-ResNet34 as well, especially to see whether with the auto-scheduling, the \"converge fast but generalize worse\" observation in Figure 3 (c,d) can be mitigated.\n\n**Minor concerns / typos**\n- In the objective (Equations (1) and (2)), the dimensionality of the problem is $n$; however, $n$ is later also used to denote the number of parameter groups at the top of page 3. The latter implies the overall dimensionality of the problem should be $\\sum_{j=1}^n p_j$ where $p_j$ is the number of parameters in group $j$. \n- It's unclear to me why $f_k=f(x_k,\\xi_k)$ is not expressed as the sum of individual function values of a mini-batch, as you do for the stochastic gradients $g_k$. I suppose it should be and this is just to avoid cluttering, or are the $f_k$'s computed in some other way?\n- Top of page 5: when concluding that $\\mathbb{E}[H_kg_k] = H_k\\nabla f$, one should be more explicit that the expectation is taken over $\\xi_k$, the first minibatch sampled at that iteration, excluding the randomness in $H_k$, since $H_k$ is also a random quantity it's just that its randomness comes from a separate, independent minibatch. \n- Top of page 6: \"For given $T$, $R$ be a random variable\" -> \"For *a* given $T$, *let* $R$ be a random variable\"\n- Proof of Theorem 1 (page 11, section A.1):\n\t- First line: \"can be expressed a special\" -> \"can be expressed *as* a special\"\n\t- Please use a different notation for $\\sigma=(y_k^\\top s_k^t + 2\\delta)^2 - \\|s_k^t\\|^2 \\|y_k\\|^2$ as $\\sigma$ is already used in Assumption $\\mathbb{E}_{\\xi_k}[\\|g(x_k,\\xi_k)-\\nabla f(x_k)\\|^2] \\leq \\sigma^2$.\n- Proof of Theorem 1 (page 12, section A.1):\n\t- Second equality in upper bounding $\\lambda_{\\max}$: the last $+y_{k,p}^\\top g_{k,p}$ should be a minus instead. (typo)\n- It would be helpful to further explain the motivation behind the *stochastic model building* part of the algorithm, rather than just citing away Oztoprak and Birbil (2018). In particular, a justification of why their globalization strategy should also work well in the stochastic setting would significantly strengthen the paper.\n\n---\n**References mentioned**:\nOztoprak and Birbil (2018): An alternative globalization strategy for unconstrained optimization\nWang et al. (2017): Stochastic Quasi-Newton Methods for Nonconvex Stochastic Optimization \nNocedal and Wright (2006): Numerical Optimization\nVaswani et al. (2019) : Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates\n", "summary_of_the_paper": "The authors proposed a method called stochastic model building (SMB) that uses a combination of existing techniques to get faster convergence in stochastic non-convex optimization. In particular, they use a stochastic adaptation of the model-building globalization strategy from Oztoprak and Birbil (2018), in which the deterministic Armijo condition check is also computed using stochastic gradients. By re-writing their update as a preconditioned SGD step, they are able to bound the spectrum of the preconditioner. This allows them to obtain convergence results for smooth and non-convex objectives by directly invoking the analysis of Wang et al. (2017). Experiments demonstrate that with additional heuristics, their proposed method can outperform state-of-the-art optimizers on common deep learning benchmarks.", "summary_of_the_review": "Although the paper proposes an interesting, easy-to-implement algorithm for non-convex stochastic optimization, I am hesitant to recommend for acceptance at this point for its lack of significantly novel contribution and some confusing aspects of the experiments. I am willing to increase my score if my concerns are well addressed.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "aJS9na2o5rR", "reviewer": "Reviewer_8Xqy", "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": "1- The paper is an incremental work and is mainly a stochastic variant of Öztoprak et al 2018. This paper doesn't offer anything technical since all the theoretical results are just slight modifications of already existing results. On the other hand, the empirical results also don't show a big advancement. \n\n2-  Generally tuning both direction and step size is not a new approach. For example, the diagonal variant of AdaGrad has a similar approach. Also in the proposed algorithm in each step, it can require a matrix-vector multiplication and it cannot be relaxed. Parameter partitioning is a way to make the matrix block-diagonal and to reduce the matrix-vector multiplication. However, in the paper, it is not clarified why partitioning is useful. \n\n3- The paper claims that unlike line search there is no backtracking step. However, to set \\eta their proposed algorithm needs backtracking. \n\n4- It hasn’t been mentioned in the paper how many times each experiment ran? It would be more reliable if each experiment runs several times and the average of them is plotted. \n", "summary_of_the_paper": "\nThis paper proposes an alternative to stochastic line search which is based on forwarding step model building which corrects the direction of move and its magnitude at the same time. In its proposed algorithm it first checks if the given step size satisfies the stochastic line search. If yes then just use the step size and do the SGD update. Otherwise, it builds linear models around two points and combines these two models and minimizes this new model and this becomes the new iterate value. \n\n", "summary_of_the_review": "The paper is an incremental work and is mainly a stochastic variant of Öztoprak et al 2018. This paper doesn't offer anything technical since all the theoretical results are just slight modifications of already existing results. On the other hand, the empirical results also don't show a big advancement. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "2cinxn3g7pr", "reviewer": "Reviewer_xM1f", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "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": "1- The majority of the manuscript is well-written and easy to understand. However, some parts require further explanation and clarification that the reviewer explains in the following comments.\n\n2- The literature part needs to be strengthened. \n\n3- The point that is mentioned in Page 2 \"It also incorporates the most recent curvature information from the current point. This is in contrast with the stochastic quasi-Newton methods which use the information from the previous steps\" is $\\textbf{not}$ novel! The studies [1] and [2] (to name a few) introduced this concept earlier.\n\n4- Does the inequality (3) guarantee a decrease in the main objective function or just the stochastic objective function? If just the stochastic objective function, how can we trust the step length?\n\n5- In Page 3 (line 3 in the second paragraph) the authors mentioned group $p$ which is not introduced before. The text needs to be more clear and readable.\n\n6- One of the main goals of this paper is related to reducing the computational costs of tuning. However, in the proposed algorithms 1 and 2, there are many hyper-parameters that still requires tuning. The authors need to exactly mention how they claim the idea of reducing tuning attempts.\n\n7- The theoretical results are quite basic and more stronger results are expected. Theorem 1 does not guarantee any convergence, it just shows that the norm of gradient (in expectation) is bounded above by some terms that are NOT diminishing as the algorithm progresses. If $\\alpha_k = \\mathcal{O}(L^{-2})$ (which is super tiny), the proposed method converges to the neighborhood of stationary point. Even with diminishing step sizes, the proved convergence result does not guarantee any convergence to a stationary point (just the neighborhood around a stationary point). All in all, the theoretical results definitely require modification.\n\n8- Do the authors consider the extra cost per each iteration in the plots with $x$-axis as $\\textbf{Epochs}$? Also, instead of averaging over 5 runs, it is better to show the error band. The mini-batch size is not reported for the experiments, it is very important hyper-parameter as well.\n\n9- That is good that the authors provided some results regarding the robustness of their method.\n\n10- In the abstract, it is mentioned that $\\textbf{This novel\ndiagonalization approach makes the selected step lengths adaptive.}$ The proposed method is not adaptive in terms of step size! In both algorithms 1 and 2, there is not any adaptive rule for the step size.\n\n\n[1] Gao, W., & Goldfarb, D. (2018). Block BFGS methods. SIAM Journal on Optimization, 28(2), 1205-1231.\n\n[2] Berahas, A. S., Jahani, M., Richtárik, P., & Takáč, M. (2020). Quasi-newton methods for deep learning: Forget the past, just sample.", "summary_of_the_paper": "This paper presents a model building approach that replaces the one-step backtracking in stochastic line search methods. The authors provided some convergence guarantees for their proposed method and evaluated their approach on some image classification tasks.", "summary_of_the_review": "The theoretical results needs to be more strengthened. The contribution is ok but not good enough.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: There was a consensus among the reviewers to reject the paper. While they noted that the paper proposed a new interesting stochastic algorithm for deep learning, they think the paper needs to be substantially improved in both theory and empirical study. The paper was judged quite incremental in comparison to the work of Öztoprak et al 2018 (where most of the theory was developed), while not showing improved empirical performance on the benchmarks.
Decision: Reject