# BOLSTERING STOCHASTIC GRADIENT DESCENT WITH MODEL BUILDING

**Anonymous authors**
Paper under double-blind review

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 finetuned 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.

1 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 (Asi & 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; Bollapragada et al., 2018) improve the direction by reducing its variance
around the negative gradient of the empirical loss function, while stochastic 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 as a component of the proposed line search algorithms (Balles et al., 2016; Paquette &
Scheinberg, 2020).

The Stochastic Model Building (SMB) algorithm proposed in this paper is not designed as a stochastic
quasi-Newton algorithm in the sense explained by Bottou et al. (2018). However, it still produces a
scaling matrix in the process of generating trial points, and its overall step at 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 in those iterations. In other
words, the scaling matrix and the incumbent random gradient vector are dependent.

Vaswani et al. (2019) 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 a 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 a minimizer of the empirical loss. Mutschler & Zell (2020) assume that the


-----

optimal learning rate along the negative batch gradient is a 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 a different approach to translate deterministic line search procedures into a stochastic setting, and they do not employ fixed samples. In Mahsereci & 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 a 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 as 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 use the information from
the previous steps. Capitalizing our discussion on the independence of the sample batches, we also
give a convergence analysis for SMB. Finally, we 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.

2 STOCHASTIC MODEL BUILDING

We introduce a new stochastic unconstrained optimization algorithm in order to approximately solve
problems of the form

min (1)

_x2<[n][ f]_ [(][x][) =][ E][[][F] [(][x, ⇠][)]][,]

where F : R[n] _⇥_ R[d] _! R is continuously differentiable and possibly nonconvex, ⇠_ _2 R[d]_ denotes a
random variable, and E[.] denotes the expectation taken with respect to ⇠. We assume the existence
of a stochastic first-order oracle which outputs a stochastic gradient g(x, ⇠) of f for a given x. A
common approach to tackle (1) is to solve the empirical risk problem


min

_x2<[n][ f]_ [(][x][) = 1]N


_fi(x),_ (2)


_i=1_


where fi : R[n] _! R 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 a 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 to the performance, and
its cost to the run time can be extremely high in deep learning problems. Therefore, if the sufficient
decent is 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-Newton 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 xk, we
calculate the stochastic function value fk = f (xk, ⇠k) and the mini-batch stochastic gradient


-----

_gk =_ _m1k_ _mi=1k_ _[g][(][x][k][, ⇠][k,i][)][ at][ x][k][, where][ m][k][ is the batch size and][ ⇠][k][ = (][⇠][k,][1][, . . ., ⇠][k,m]k_ [)][ is the]

realization of the random vector ⇠. Then, we apply the SGD update to calculate the trial step

P

_s[t]k_ [=][ −][↵][k][g][k][, where][ {][↵][k][}][k][ is a sequence of learning rates. With this trial step, we also calculate the]

function and gradient values fk[t] [=][ f] [(][x]k[t] _[, ⇠][k][)][ and][ g]k[t]_ [=][ g][(][x]k[t] _[, ⇠][k][)][ at][ x][t]k_ [=][ x][k][ +][ s]k[t] [. Then, we check]

the stochastic Armijo condition

_fk[t]_ (3)

_[]_ _[f][k]_ _[−]_ _[c ↵][k][k][g][k][k][2][,]_

where c > 0 is a hyper-parameter. If the condition is satisfied and we achieve sufficient decrease, then
we set xk+1 = x[t]k [as the next step. If the Armijo condition is not satisfied, then we build a quadratic]

model using the linear models at the points xk,p and x[t]k,p [for each parameter group][ p][ and find the]

step sk,p to reach its minimum point. Here, xk,p and x[t]k,p [denote respectively the coordinates of][ x][k]

and x[t]k [that corresponds to the parameter group][ p][. We calculate the next iterate][ x][k][+1][ =][ x][k][ +][ s][k][,]

where sk = (sk,p1 _, . . ., sk,pn_ ) and n is the number of parameter groups, and proceed to the next step
with xk+1 . This model step, if 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 is built by combining the linear models at xk,p and
_x[t]k,p[, given by]_

_lk,p[0]_ [(][s][) :=][ f][k,p] [+][ g]k,p[>] _[s]_ and _lk,p[t]_ [(][s][ −] _[s][t]k,p[) :=][ f][ t]k,p_ [+ (][g]k,p[t] [)][>][(][s][ −] _[s][t]k,p[)][,]_


respectively. Then, the quadratic model becomes

_m[t]k,p[(][s][) :=][ ↵]k,p[0]_ [(][s][)][l]k,p[0] [(][s][) +][ ↵]k,p[t] [(][s][)][l]k,p[t] [(][s][ −] _[s][t]k,p[)][,]_


where

The constraint


(s − _s[t]k,p[)][>][(][−][s][t]k,p[)]_ and ↵k,p[t] [(][s][) =]

(−s[t]k,p[)][>][(][−][s][t]k,p[)]


_s[>]s[t]k,p_

(s[t]k,p[)][>][s][t]k,p


_↵k,p[0]_ [(][s][) =]


_ksk[2]_ + ks − _s[t]k,p[k][2][ k][s][t]k,p[k][2][,]_

is also imposed so that the minimum is attained in the region bounded by xk,p and x[t]k,p[. This]

constraint acts like a trust region. Figure 1 shows the steps of this construction.

In this work, we solve a relaxation of this constrained model as explained in (Öztoprak & Birbil,
2018, Section 2.2). The minimum value of the relaxed model is attained at the point xk,p + sk,p with


_sk,p = cg,p(δ)gk,p + cy,p(δ)yk,p + cs,p(δ)s[t]k,p[,]_ (4)

where yk,p := gk,p[t]

_[−]_ _[g][k,p][. Here, the coefficients are given as]_


_ks[t]k,p[k][2]_ _,_ _cy,p(δ) =_

2δ _−_


_ks[t]k,p[k][2]_ [ (yk,p[>] _[s][t]k,p_ [+ 2][δ][)(][s]k,p[t] [)][>][g][k,p] [+][ k][s][t]k,p[k][2][y]k,p[>] _[g][k,p][]][,]_

2δ✓ _−_


_cg,p(δ) =_ _k_ _k,p[k]_ _,_
_−_ 2δ

_cs,p(δ) =_
_−_

with


_ks[t]k,p[k][2]_ [ (yk,p[>] _[s][t]k,p_ [+ 2][δ][)][y]k,p[>] _[g][k,p]_ [+][ k][y][k,p][k][2][(][s][t]k,p[)][>][g][k,p][]][,]

2δ✓ _−_


2
⌘


_s[t]k,p[k][2][k][y]k,p[k][2][ and][ δ][ = 1]_
_−k_ 2


_kyk,pk + ⌘[1]_ _[k][g][k,p][k]_


_yk,p[>]_ _[s][t]k,p_ [+ 2][δ]


_ks[t]k,p[k]_


_yk,p[>]_ _[s][t]k,p_
_−_


(5)


_✓_ =


where 0 < ⌘< 1 is a constant which controls the size of sk,p by imposing the condition
_sk,p_ _⌘_ _s[t]k,p[k][. Then, the adaptive model step becomes][ s][k][ = (][s][k,p]1_ _[, . . ., s][k,p]n_ [)][. We note]
_k_ _k _ _k_

that our construction in terms of different parameter groups lends itself to constructing a different
model for each parameter subspace.


-----

Figure 1: An iteration of SMB on a simple quadratic function. For simplicity we assume that there
is only one parameter group, and hence, we drop the subscript p . The algorithm first computes the
trial point x[t]k [by taking the stochastic gradient step][ s]k[t] [. If this point is not acceptable, then it builds]

a model using the information at xk and x[t]k[, and computes the next iterate][ x][k][+1][ =][ x][k][ +][ s][k][. Note]

that sk not only have a smaller length compared to the trial step s[t]k[, but it also lies along a direction]

decreasing the function value.


We summarize the steps of SMB in Algorithm 1. Line 5 shows the trial point, which is obtained with
the standard stochastic gradient step. If this step satisfies the stochastic Armijo condition, then we
proceed with the next iteration (line 8). Otherwise, we continue with bulding the models for each
parameter group (lines 10- 12), and move to the next iteration with the model building step in line 13.

**Algorithm 1: SMB: Stochastic Model Building**

**1 Input: x1 2 R[n], stepsizes {↵k}k[T]=1[, mini-batch sizes][ {][m][k][}][T]k=1[,][c >][ 0][, and][ ↵][max][ satisfying (8)]**

**2 for k = 1, . . ., T do**

1 _mk_
**3** _fk = f_ (xk, ⇠k), gk = _mk_ _i=1_ _[g][(][x][k][, ⇠][k,i][)][;]_

**4** _s[t]k_ [=][ −][↵][k][g][k][;] P

**5** _x[t]k_ [=][ x][k][ +][ s]k[t] [;]

**6** _fk[t]_ [=][ f] [(][x]k[t] _[, ⇠][k][)][,][ g]k[t]_ [=] _m1k_ _mi=1k_ _[g][(][x]k[t]_ _[, ⇠][k,i][)][;]_

**7** **if fk[t]** P

**8** _xk[]+1[f] =[k][ −] x[c ↵][t]k_ [;] _[k][k][g][k][k][2][ then]_

**9** **else**

**10** **for p = 1, . . ., n do**


**11** _yk,p = gk,p[t]_

_[−]_ _[g][k,p][;]_

**12** _sk,p = cg,p(δ)gk,p + cy,p(δ)yk,p + cs,p(δ)s[t]k,p[;]_

**13** _xk+1 = xk + sk with sk = (sk,p1_ _, . . ., sk,pn_ );

3 CONVERGENCE ANALYSIS

The steps of SMB can be considered as a special quasi-Newton update:


_xk+1 = xk −_ _↵kHkgk,_ (6)

where Hk is a symmetric positive definite matrix as an approximation to the inverse Hessian matrix.
In Appendix A.1, we explain this connection and give an explicit formula for the matrix Hk. We also
prove that there exists , > 0 such that for all k the matrix Hk satisfies

_I_ _Hk_ _I,_ (7)
_⪯_ _⪯_


-----

where for two matrices A and B, A ⪯ _B means B −_ _A is positive semidefinite. It is important to_
note that Hk is built with the information collected around xk, particularly, gk. Therefore, unlike
stochastic quasi-Newton methods, Hk is correlated with gk, and hence, E[Hkgk] is very difficult to
analyze. Unfortunately, this difficulty prevents us from using the general framework given by Wang
et al. (2017).

To overcome this difficulty and carry on with the convergence analysis, we modify Algorithm 1 such
that Hk is calculated with a new independent mini batch, and therefore, it is independent of gk. By
doing so, we still build a model using the information around xk. Assuming that gk is an unbiased
estimator of rf, we conclude that E[Hkgk] = Hkrf . In the rest of this section, we provide a
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. As Step 11 shows, we obtain the model building
step with a new random batch.

**Algorithm 2: SMBi: Hk with an independent batch**

**1 Input: x1 2 R[n], stepsizes {↵k}k[T]=1[, mini-batch sizes][ {][m][k][}][T]k=1[,][c >][ 0][, and][ ↵][max][ satisfying (8)]**

**2 for k = 1, . . ., T do**

1 _mk_
**3** _fk = f_ (xk, ⇠k), gk = _mk_ _i=1_ _[g][(][x][k][, ⇠][k,i][)][;]_

**4** _s[t]k_ [=][ −][↵][k][g][k][;] P

**5** _x[t]k_ [=][ x][k][ +][ s]k[t] [;]

**6** _fk[t]_ [=][ f] [(][x]k[t] _[, ⇠][k][)][,][ g]k[t]_ [=] _m1k_ _mi=1k_ _[g][(][x]k[t]_ _[, ⇠][k,i][)][;]_

**7** **if fk[t]** P

**8** _xk[]+1[f] =[k][ −] x[c ↵][t]k_ [;] _[k][k][g][k][k][2][ then]_

**9** **else**

**10** **for p = 1, . . ., n do**

**11** Choose a new independent random batch ⇠k[0] [;]

1 _mk_

**12** _gk[0]_ [=] _mk_ _i=1_ _[g][(][x][k][, ⇠]k,i[0]_ [)][;]

**13** (s[t]k[)][0][ =][ −]P[↵][k][g]k[0] [,][ (][x][t]k[)][0][ =][ x][k][ + (][s][t]k[)][0][;]

1 _mk_

**14** (gk[t] [)][0][ =] _mk_ _i=1_ _[g][((][x]k[t]_ [)][0][, ⇠]k,i[0] [)][,][ y]k,p[0] [= (][g]k,p[t] [)][0][ −] _[g]k,p[0]_ [;]

**15** _sk,p = −↵kHPk,p[0]_ _[g][k][, where][ H]k,p[0]_ [is calculated using][ g]k[0] [and][ y]k[0] [as defined in]

Appendix A.1;


**16** _xk+1 = xk + sk with sk = (sk,1, . . ., sk,n);_

**Assumptions: Before providing the analysis, let us assume that f : R[n]** _! R is continuously_
differentiable, lower bounded by f _[low], and there exists L > 0 such that for any x, y 2 R[n], krf_ (x) _−_
_f_ (y) _L_ _x_ _y_ . We also assume that ⇠k, k 1, are independent samples and for any iteration
_r_ _k _ _k_ _−_ _k_ _≥_
_k, ⇠k is independent of_ _xj_ _j=1[,][ E][⇠]k_ [[][g][(][x][k][, ⇠][k][)] =][ r][f] [(][x][k][)][ and][ E][⇠]k [[][k][g][(][x][k][, ⇠][k][)][ −r][f] [(][x][k][)][k][2][]][ ] _[σ][2][,]_
_{_ _}[k]_

for some σ > 0.

In order to be in line with practical implementations and with our experiments, we first provide an
analysis covering the constant stepsize case for (possibly) non-convex objective functions.

Below, we denote by ⇠[T ] = (⇠1, . . ., ⇠T ) the random samplings in the first T iterations. Let ↵max be
the maximum stepsize that is allowed in the implementation of SMBi with


_↵max_
_≥_ _[−][1 +]_


1 + 16⌘[2]

_._ (8)
4L⌘

p


This hyper-parameter of maximum stepsize is needed in the theoretical results. The same parameter
can also be used to apply automatic stepsize adjustment (see our numerical experiments with stepsize
auto-scheduling in Section 4.2). Observe that since ⌘[−][1] _> 1, assuming L ≥_ 1 implies that it suffices
to choose ↵max 1 to satisfy (8). The proof of the following convergence result is given in Appendix
A.1 _≥_
**Theorem 1. Suppose that our assumptions above hold and {xk} is generated by SMBi as given in**
_Algorithm 2. Suppose also that {↵k} in Algorithm 2 satisfies that 0 < ↵k < 2/(L⌘[−][1]_ +2L[2]↵max) 


-----

_↵max for all k. For given T_ _, R be a random variable with the probability mass function_

_↵k/(⌘[−][1]_ + 2L↵max) _↵k[2][L/][2]_
PR(k) := P _R = k_ = _T_ _−_ _,_
_{_ _}_

_k=1[(][↵][k][/][(][⌘][−][1][ + 2][L↵][max][)][ −]_ _[↵]k[2][L/][2)]_

_for k = 1, . . ., T_ _. Then, we have_ P


_Df + (σ[2]L/2)_ _k=1[(][↵]k[2][/m][k][)]_
E[ _f_ (xR) ] _T_ _,_
_kr_ _k[2]_ __

_k=1[(][↵][k][/][(][⌘][−][1][ + 2][L↵][max][)][ −]_ _[↵]k[2][L/][2)]_

[P][T]

_where Df := f_ (x1) − _f_ _[low]_ _and the expectation is taken with respect toP_ _R and ⇠[T ]. Moreover, if we_
_choose ↵k = 1/(L⌘[−][1]_ + 2L[2]↵max) and mk = m for all k = 1, . . ., T _, then this reduces to_


E[ _f_ (xR) ]
_kr_ _k[2]_ __ [2][L][(][⌘][−][1][ + 2]T[L↵][max][)][2][D][f]


+ _[σ][2]_

_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(✏[−][2]) (Wang et al., 2017, Corollary 2.12).

In (Wang et al., 2017, Theorem 2.5), it is shown that under our assumptions above and the extra
assumption of 0 < ↵k _L(⌘[−][1]+21L↵max)_

method (when Hk is calculated by an independent batch in each step) with batch size  _[]_ _[↵][max][, if the point sequence][ {][x][k][}][ is generated by SMBi] mk = m for_
all k, then there exists a positive constant Mf such that E[f (xk)]  _Mf_ . Using this observation,
the proof of Theorem 1, and Theorem 2.8 in (Wang et al., 2017), we 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 ↵k =** _L(⌘[−][1]+21L↵max)_ _[k][−][φ][ with][ φ][ 2][ (0][.][5][,][ 1)]_

_for all k. Then_ _xk_ _generated by SMBi satisfies that_
_{_ _}_


_σ[2]_
E[ _f_ (xk) 2L(⌘[−][1] + 2L↵max)(Mf _f_ _[low])T_ _[φ][−][1]_ +
_kr_ _k[2]_ __ _−_ (1 _φ)m_ [(][T][ −][φ][ −] _[T][ −][1][)]_

_−_


_k=1_


_for some Mf > 0, where T denotes the iteration number. Moreover, for a given ✏_ (0, 1), to

_guarantee that_ _T[1]_ _Tk=1_ [E][[][kr][f] [(][x][k][)][k][2][ < ✏][, the number of iterations][ T][ needed is at most][ O]2 _✏[−]_ 1−1 _φ_ _._

⇣ ⌘

P

We are now ready to assess the performance of SMB and SMBi with some numerical experiments.

4 NUMERICAL EXPERIMENTS

In this section, we compare SMB and SMBi against SGD, Adam Kingma & Ba (2015), and SLS
(SGD+Armijo) Vaswani et al. (2019). We have chosen SLS since it is a recent method that uses
stochastic line search with backtracking. We have conducted experiments on multi-class classification
problems using neural network models[1]. The codes to conduct our 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 a stepsize reset algorithm
between epochs. We refer to this routine as stepsize auto-scheduling. Therefore, we find it unfair
to compare SLS with other methods with constant stepsize. Please, see Section 4.2 for a discussion
about stepsize auto-scheduling using SMB.

**MNIST dataset.** On the MNIST dataset, we have used the one hidden-layer multi-layer perceptron

(MLP) of width 1,000. We compare all methods after cross-validating their best performances
from the set of learning rates, {0.001, 0.01, 0.1, 0.25, 0.5, 0.75, 1.0}. For SMB and SLS, we have

[1The implementations of the models are taken from https://github.com/IssamLaradji/sls](https://github.com/IssamLaradji/sls)


-----

used the default hyper-parameter value c = 0.1 of SLS that appears in the Armijo condition (also
recommended by the authors of SLS)

(a) Epochs (b) Run Time

Figure 2: Classification on MNIST with an MLP model.

In Figure 2, we see the best performances of all five methods on 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.

It should be pointed out that, in practice, choosing a new independent batch means the SMBi method
can construct a 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 in 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 CIFAR10 and CIFAR100 datasets, we have used the

standard image-classification architectures ResNet-34 (He et al., 2016) and DenseNet-121 (Huang
et al., 2017) . Due to the high computational costs of these architectures, we report the results of a
single run of each method. For, Adam we have used the default learning rate 0.001, and for SGD, we
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 c = 0.1 of SLS.

(a) Training Loss (b) Test Accuracy

(c) Training Loss (d) Test Accuracy

Figure 3: Classification on CIFAR10 (a, b) and CIFAR100 (c, d) with ResNet-34 model.

In Figure 3, we see that on CIFAR10-Resnet34 and CIFAR100-Resnet34, 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 CIFAR100-Resnet34, this advantage does not show in test


-----

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 4.3 so that we obtain a fairer comparison between
SMB and SLS.

(a) Training Loss (b) Test Accuracy

Figure 4: Classification on CIFAR100 with DenseNet-121 model.

In Figure 4, we see a comparison of performances of SMB and SLS on CIFAR100-DenseNet121.
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.

4.2 STEPSIZE AUTO-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 3). We believe that
the number of model steps taken in an epoch (when the Armijo condition is not satisfied) can be a
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 a 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, ↵max. The value 0.9 is the backtracking ratio of SLS and we consider 5% as a
hyper-parameter. Figure 5 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.

(a) Training Loss (b) Test Accuracy

Figure 5: Performances of SMB and SMBi with auto-scheduled stepsizes on CIFAR10.

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 6 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.


-----

Figure 6: Robustness of SMB under different choices of the learning rate.

5 CONCLUSION

SMB is a fast alternative to stochastic gradient method. The algorithm provides a model building
approach that replaces the one-step backtracking in stochastic line search methods. We have analyzed
the convergence properties of a modification of SMB by rewriting its model building step as a quasiNewton update and constructing the scaling matrix with a 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 4.3, SMB can greatly benefit from a stepsize auto-scheduling
routine. This is a future work that we 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 a convergence analysis for the SMB method.


-----

REFERENCES

Hilal Asi and John C. Duchi. The importance of better models in stochastic optimization. Proceedings

_of the National Academy of Sciences, 116(46):22924–22930, 2019._ ISSN 0027-8424. doi:

[10.1073/pnas.1908018116. URL https://www.pnas.org/content/116/46/22924.](https://www.pnas.org/content/116/46/22924)

Lukas Balles, Javier Romero, and Philipp Hennig. Coupling adaptive batch sizes with learning rates.

_[arXiv preprint arXiv:1612.05086, 2016. URL https://arxiv.org/abs/1612.05086.](https://arxiv.org/abs/1612.05086)_

Raghu Bollapragada, Richard Byrd, and Jorge Nocedal. Adaptive sampling strategies for stochastic

optimization. SIAM Journal on Optimization, 28(4):3312–3343, 2018.

Léon Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for large-scale machine

learning. SIAM Review, 60(2):223–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 H 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–1031, 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 on Learning Representations, ICLR
_[2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015. URL http:](http://arxiv.org/abs/1412.6980)_
[//arxiv.org/abs/1412.6980.](http://arxiv.org/abs/1412.6980)

Maren Mahsereci and Philipp Hennig. Probabilistic line searches for stochastic optimization. The

_Journal of Machine Learning Research, 18(1):4262–4320, 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 dnns. arXiv preprint

_[arXiv:1903.11991, 2020. URL https://arxiv.org/abs/1903.11991.](https://arxiv.org/abs/1903.11991)_

Figen Öztoprak and ¸S [˙]Ilker Birbil. An alternative globalization strategy for unconstrained optimization.

_Optimization, 67(3):377–392, 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:1905.09997, 2019. URL https://arxiv.org/abs/1905.09997.](https://arxiv.org/abs/1905.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–956, 2017.


-----

