Year: 2021

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.

heading: 1 INTRODUCTION
text: 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.

heading: 2 STOCHASTIC MODEL BUILDING
text: We introduce a new stochastic unconstrained optimization algorithm in order to approximately solve problems of the form
min x2<n
f(x) = E[F (x, ⇠)], (1)
where F : Rn ⇥ Rd ! R is continuously differentiable and possibly nonconvex, ⇠ 2 Rd 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
NX
i=1
fi(x), (2)
where fi : Rn ! 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 = 1
mk
Pmk i=1 g(xk, ⇠k,i) at xk, where mk is the batch size and ⇠k = (⇠k,1, . . . , ⇠k,mk) is the
realization of the random vector ⇠. Then, we apply the SGD update to calculate the trial step stk = ↵kgk, where {↵k}k is a sequence of learning rates. With this trial step, we also calculate the function and gradient values f tk = f(x t k, ⇠k) and g t k = g(x t k, ⇠k) at x t k = xk + s t k. Then, we check the stochastic Armijo condition
f tk  fk c ↵kkgkk 2, (3)
where c > 0 is a hyper-parameter. If the condition is satisfied and we achieve sufficient decrease, then we set xk+1 = xtk 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 xtk,p for each parameter group p and find the step sk,p to reach its minimum point. Here, xk,p and xtk,p denote respectively the coordinates of xk and xtk that corresponds to the parameter group p. We calculate the next iterate xk+1 = xk + sk, 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 xtk,p, given by
l0k,p(s) := fk,p + g > k,ps and l t k,p(s s t k,p) := f t k,p + (g t k,p) >(s stk,p),
respectively. Then, the quadratic model becomes
mtk,p(s) := ↵ 0 k,p(s)l 0 k,p(s) + ↵ t k,p(s)l t k,p(s s t k,p),
where
↵0k,p(s) = (s stk,p) >( stk,p)
( stk,p) >( stk,p)
and ↵tk,p(s) = s>stk,p
(stk,p) >stk,p
.
The constraint
ksk2 + ks stk,pk 2  kstk,pk 2,
is also imposed so that the minimum is attained in the region bounded by xk,p and xtk,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 := gtk,p gk,p. Here, the coefficients are given as
cg,p( ) = kstk,pk 2
2 , cy,p( ) =
kstk,pk 2
2 ✓ [ (y>k,ps t k,p + 2 )(s t k,p) >gk,p + ks t k,pk 2y>k,pgk,p],
cs,p( ) = kstk,pk 2
2 ✓ [ (y>k,ps t k,p + 2 )y > k,pgk,p + kyk,pk 2(stk,p) >gk,p],
with
✓ = ⇣ y>k,ps t k,p + 2 ⌘2 kstk,pk2kyk,pk2 and =
1 2
✓ kstk,pk ✓ kyk,pk+
1 ⌘ kgk,pk
◆ y>k,pstk,p ◆ , (5)
where 0 < ⌘ < 1 is a constant which controls the size of sk,p by imposing the condition ksk,pk  ⌘kstk,pk. Then, the adaptive model step becomes sk = (sk,p1 , . . . , sk,pn). We note that our construction in terms of different parameter groups lends itself to constructing a different model for each parameter subspace.
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 Rn, stepsizes {↵k}Tk=1, mini-batch sizes {mk}Tk=1,c > 0, and ↵max satisfying (8) 2 for k = 1, . . . , T do 3 fk = f(xk, ⇠k), gk = 1mk Pmk i=1 g(xk, ⇠k,i); 4 stk = ↵kgk; 5 xtk = xk + s t k; 6 f tk = f(x t k, ⇠k), g t k = 1 mk Pmk i=1 g(x t k, ⇠k,i); 7 if f tk  fk c ↵kkgkk2 then 8 xk+1 = xtk ; 9 else
10 for p = 1, . . . , n do 11 yk,p = gtk,p gk,p; 12 sk,p = cg,p( )gk,p + cy,p( )yk,p + cs,p( )stk,p;
13 xk+1 = xk + sk with sk = (sk,p1 , . . . , sk,pn);

heading: 3 CONVERGENCE ANALYSIS
text: 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 Rn, stepsizes {↵k}Tk=1, mini-batch sizes {mk}Tk=1,c > 0, and ↵max satisfying (8) 2 for k = 1, . . . , T do 3 fk = f(xk, ⇠k), gk = 1mk Pmk i=1 g(xk, ⇠k,i); 4 stk = ↵kgk; 5 xtk = xk + s t k; 6 f tk = f(x t k, ⇠k), g t k = 1 mk Pmk i=1 g(x t k, ⇠k,i); 7 if f tk  fk c ↵kkgkk2 then 8 xk+1 = xtk ; 9 else
10 for p = 1, . . . , n do 11 Choose a new independent random batch ⇠0k; 12 g0k = 1 mk Pmk i=1 g(xk, ⇠ 0 k,i); 13 (stk) 0 = ↵kg0k, (x t k) 0 = xk + (stk) 0; 14 (gtk) 0 = 1mk Pmk i=1 g((x t k) 0, ⇠0k,i), y 0 k,p = (g t k,p) 0 g0k,p; 15 sk,p = ↵kH 0k,pgk, where H 0 k,p is calculated using g 0 k and y 0 k 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 : Rn ! R is continuously differentiable, lower bounded by f low, and there exists L > 0 such that for any x, y 2 Rn, krf(x) rf(y)k  Lkx yk. We also assume that ⇠k, k 1, are independent samples and for any iteration k, ⇠k is independent of {xj}kj=1, E⇠k [g(xk, ⇠k)] = rf(xk) and E⇠k [kg(xk, ⇠k) rf(xk)k2]  2, 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 +
p 1 + 16⌘2
4L⌘ . (8)
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+2L2↵max) 
↵max for all k. For given T , R be a random variable with the probability mass function
PR(k) := P{R = k} = ↵k/(⌘ 1 + 2L↵max) ↵2kL/2PT
k=1(↵k/(⌘ 1 + 2L↵max) ↵2kL/2)
,
for k = 1, . . . , T . Then, we have
E[krf(xR)k2]  Df + ( 2L/2)
PT k=1(↵
2 k/mk)PT
k=1(↵k/(⌘ 1 + 2L↵max) ↵2kL/2)
,
where Df := f(x1) f low and the expectation is taken with respect to R and ⇠[T ]. Moreover, if we choose ↵k = 1/(L⌘ 1 + 2L2↵max) and mk = m for all k = 1, . . . , T , then this reduces to
E[krf(xR)k2]  2L(⌘ 1 + 2L↵max)2Df
T +
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  1L(⌘ 1+2L↵max)  ↵max, if the point sequence {xk} is generated by SMBi method (when Hk is calculated by an independent batch in each step) with batch size 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 = 1L(⌘ 1+2L↵max)k with 2 (0.5, 1) for all k. Then {xk} generated by SMBi satisfies that
1
T
TX
k=1
E[krf(xk)k2  2L(⌘ 1 + 2L↵max)(Mf f low)T 1 + 2
(1 )m (T T 1)
for some Mf > 0, where T denotes the iteration number. Moreover, for a given ✏ 2 (0, 1), to
guarantee that 1 T PT k=1 E[krf(xk)k2 < ✏, the number of iterations T needed is at most O ⇣ ✏ 1 1 ⌘ .
We are now ready to assess the performance of SMB and SMBi with some numerical experiments.

heading: 4 NUMERICAL EXPERIMENTS
text: 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 models1. The codes to conduct our experiments are given in the supplementary file.

heading: 4.1 CONSTANT STEPSIZE
text: 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
used the default hyper-parameter value c = 0.1 of SLS that appears in the Armijo condition (also recommended by the authors of SLS)
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.
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.
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.

heading: 4.2 STEPSIZE AUTO-SCHEDULING
text: 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.

heading: 4.3 ROBUSTNESS WITH RESPECT TO STEPSIZE
text: 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.

heading: 5 CONCLUSION
text: 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.

Review summaries:
 This 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.   

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.