# Online Learning for DNN Training: A Stochastic Block Adaptive Gradient Algorithm

Authors: Jianghui Liu; Baozhu Li; Yangfan Zhou; Xuhui Zhao; Junlong Zhu; Mingchuan Zhang
Journal: Computational Intelligence and Neuroscience
 (2022)

---

## Abstract

Adaptive algorithms are widely used because of their fast convergence rate for training deep neural networks (DNNs). However, the training cost becomes prohibitively expensive due to the computation of the full gradient when training complicated DNN. To reduce the computational cost, we present a stochastic block adaptive gradient online training algorithm in this study, called SBAG. In this algorithm, stochastic block coordinate descent and the adaptive learning rate are utilized at each iteration. We also prove that the regret bound ofOT can be achieved via SBAG, in which T is a time horizon. In addition, we use SBAG to train ResNet-34 and DenseNet-121 on CIFAR-10, respectively. The results demonstrate that SBAG has better training speed and generalized ability than other existing training methods.


---

## Body

## 1. Introduction

Benefitting from a great many data samples and complex training model, deep learning has gained great interest in recent years and has been applied in resource allocation [1–4], signal estimation [5, 6], computer vision [7–9], and so on. However, the computing cost is very high in the training process of deep learning, which needs large amounts of training data and iteration update to obtain good model parameters. It is key to speed up model training process and improve model performance. Therefore, besides proposing new training architecture [10], designing an effective training algorithm is also important. This study focuses on the design of efficient training algorithms for deep neural networks (DNNs). In fact, many questions in practice can be modeled to be an optimization problem in general [11–13], which can be solved by employing gradient-based methods. The stochastic gradient descent (SGD) method is an effective optimization algorithm [14]. Moreover, it is easy to implement because of its simplicity and is frequently used in the training process of DNN.Although the simplicity of stochastic gradient descents, the problem of slow convergence rate always exists. The same learning rate is not suitable for all parameter updates across the training process, especially in the case of sparse training data. For this reason, a number of training methods are presented to address this issue, for instance, AdaGrad [15], RMSProp[16], AdaDelta [17], and Adam [18]. These methods are referred as Adam-type algorithms since the adaptive learning rates are employed. Further, Adam has attained the most wide application in many deep learning training tasks, such as optimization of convolutional neural networks and recurrent neural networks [19, 20]. Despite its popularity, Adam incurs the convergence issue. For this reason, AMSGrad [21] was presented by introducing a nonincreasing learning rate. Besides, the learning rates of the Adam algorithm are either too big or too small, which results in poor generalization performance. To avoid the learning rate of extreme cases, a variant of Adam, Padam [22], was presented via employing a partial adaptive parameter p. SWATS [23] used the switch method from Adam to SGD. AdaBound [24] limited the learning rate to a dynamic bound over time at each iteration.In deep learning, gradient-based methods are used to optimize the model parameter, which needs to calculate the gradients of all coordinates in decision vectors at each iteration, and a huge number of data and complex model lead to expensive computation cost. Randomized block coordinate descent is an efficient method for high-dimensional optimization problem and has been successfully utilized in the large-scale problem generated in machine learning [25]. It divides the set of variables into different blocks and carries out a gradient update step on a selected block coordinates randomly at each iteration, while holding the remaining ones fixed. In this way, the computational expense of each iteration can be effectively reduced.In this study, we propose a stochastic block adaptive gradient online learning (SBAG) algorithm to rapidly train DNN, which incorporates an adaptive learning rate and stochastic block coordinate approach to improve the generalization ability and computation cost. Our key contributions are as follows:•
We present the SBAG algorithm based on the stochastic block coordinate descent method and AdaBound optimization algorithm to solve high-dimensional optimization problems.(i)
We provide the theoretical analysis on the convergence for SBAG. Moreover, we show that SBAG is convergent in the convex setting under common assumptions and its regret is bounded byOT, where T is the time horizon.(ii)
We demonstrate the performance of SBAG on a public dataset. The simulation results show that the algorithm takes lesser time to achieve the best accuracy on the training set and test set, and it outperforms other methods.The rest of this study is arranged as follows. In the next two sections, we will review the extant literature and introduce related background. In Section4, we will present SBAG in detail. In Sections 5 and 6, we will describe our convergence analysis and performance evaluation. Finally, we present the conclusion of this paper in Section 7.


## 2. Related Work

SGD is one of the most popular algorithms used in DNN because of its implementation easily. However, it has the same learning rate for all parameters updated at each iteration across the training process, and the parameters are updated to the same extent no matter how different the feature frequencies are, which consequently results in slow convergence rate and poor performance. Hence, some variants of SGD were proposed to improve its convergence rate by either making the learning rate adaptive or using historical gradient information for descent direction. Ghadimi et al. [26] used the Heavy-ball method to combine one-order historical gradients and current gradients for updates. Sutskever et al. [27] presented Nesterov’s accelerated gradient (NAG) method. Duchi et al. [15] proposed AdaGrad that first used an adaptive learning rate, whereas AdaGrad’s performance is worse in the case of dense gradients because all historical gradients are used in the updates, and this limitation is more severe when dealing with high-dimensional data in deep learning. Hinton [16] proposed RMSProp, which utilizes an exponential moving average to solve the problem that the learning rate drops sharply in AdaGrad. Zeiler [17] proposed AdaDelta, which prevents learning rate decay and gradient disappearance over time. In fact, further research was to combine adaptive learning rate with historical gradient information, such as those used in Adam [18] and AMSGrad [21]. Moreover, Adam has a good convergence rate in many scenarios. However, it was found that Adam may not converge in the later stage of the training process on account of oscillated learning rate. Reddi et al. [21] presented AMSGrad, but the result of the experiments was not much better than Adam. In general, Adam-type algorithms have better performance on convergence, but often do not work well as SGD in out of sample. To address this issue, Keskar and Socher [23] proposed the SWATS algorithm. SWATS utilizes Adam to learn in the early part of the training and switches to SGD in the later stage of the training. In this case, it enjoys the quick convergence rate of Adam and the good performance of SGD, but the switching time is difficult to determine in practice. Huang et al. [28] presented NosAdam increasing the effect of past gradients on parameter update to avoid trapping in local or divergence. Nevertheless, it depends a lot on the initial conditions. Padam [22] introduced a parameter p making the level of adaptivity of the update process controlled. Luo et al. [24] proposed the AdaBound algorithm, which provides a dynamic bound for learning rate, and AdaBound is evaluated on a public dataset and is shown to converge as fast as Adam and perform as well as SGD. However, the aforementioned methods need to calculate all coordinates of gradients in decision vectors at each iteration, and computation cost will be aggravated due to the high-dimensional data and complex model structure.The randomized block coordinate descent method is a powerful and effective approach for the high-dimensional optimization problem. It employs randomized strategies to pick a block of variables to update per iteration. For general gradient descent algorithms, all the coordinates of gradient vector should be calculated each time. One can easily observe that this will incur significant computing cost when dealing with high-dimensional data. In contrast, the randomized block coordinate method only calculates one block coordinate of gradient vector, which is considered as the descent direction. In particular, the randomized block method selects a coordinate based on probabilityp and updates the responding decision variable according to its descent direction. In addition, other coordinates of decision vector remain the same as the last time. Although the randomized block coordinate method can save significant computing cost for the learner, especially in optimization problems with high dimension data, it uses the fixed learning rate that scales the entries of gradient equally, and an adaptive learning rate has not been applied in this method.Compared with the current work, we combine the randomized block coordinate descent method with an adaptive learning rate in this study. At each iteration, a part of gradient vectors is picked randomly, and the corresponding decision vectors are updated. In this way, the gradient is then calculated based on the chosen block coordinates instead of full gradients. Moreover, the extreme learning rates are restricted to a suitable range. Our method not only enjoys good generalization performance but also saves computation cost.


## 3. Preliminaries

In this section, we first introduce the optimization problem in detail. Then, we begin with the background about the randomized block coordinate method.


### 3.1. The Online Optimization Problem

In this work, the analysis of sequence iteration optimization problem is based on the online learning framework, which can be seen as a trade-off between a learner (the algorithm) and an opponent. In such an online convex setting, the learner selects a decision pointxt∈X produced by the algorithm per time step t,t=1,…,T, and X is a convex and compact subset of ℝn. At the same time, the opponent responds to the decision of the learner with a loss function ft, which is convex and unknown in advance, and the algorithm suffers a loss ftxt. Repeating the process, we have a sequence of loss functions f1x1,f2x2,…,ftxt where ft:X⟶ℝ, and they vary with time t. In general, the online learner’s prediction problem can be represented as follows:(1)minx∈X∑t=1Tftx.For online learning tasks, the goal is to optimize the regretRT of the online learner’s predictions against the optimal decision in hindsight, which is defined as the difference in the total sum of loss functions ∑t=1Tftxt after performing online learning over T rounds and its minimum value ∑t=1Tftx∗ in the deterministic decision point x∗. In particular, we define the regret in the following:(2)RT=∑t=1Tftxt−∑t=1Tftx∗,where x∗≔argminx∈Xftx, t=1,2,…,T. It is desired that if the regret of online optimization algorithm is a sublinear function of T, which suggests limT⟶∞RT/T=0, then, on average, the online learner executes just and the fixed optimal decision afterwards. In other words, the proposed algorithm converges when its RT is bounded. Throughout this study, the diameter of convex compact set X is assumed to be bounded and ∇ftxt is bounded for all t=1,2,…,T. Hereafter, · denotes the ℓ2 norm.


### 3.2. Relevant Definitions

Now, we will describe the relevant definitions that are used in the next sections.Definition 1.
A functionf·:X⟶ℝ is L-Lipschitz, where L is Lipschitz constant, and L>0; if ∀x,y∈X,(3)fx−fy≤Lx−y.Definition 2.
(Equation (3.2) of Section 3 in [29]) A function f·:X⟶ℝ is convex and differentiable where X is a convex set; if ∀x,y∈X,(4)fy≥fx+∇fx,y−x.Definition 3.
A functionf·:X⟶ℝ is σ-strongly convex and differentiable, σ>0, and if ∀x,y∈X,(5)fy≥fx+∇fx,y−x+σ2x−y2.


## 3.1. The Online Optimization Problem

In this work, the analysis of sequence iteration optimization problem is based on the online learning framework, which can be seen as a trade-off between a learner (the algorithm) and an opponent. In such an online convex setting, the learner selects a decision pointxt∈X produced by the algorithm per time step t,t=1,…,T, and X is a convex and compact subset of ℝn. At the same time, the opponent responds to the decision of the learner with a loss function ft, which is convex and unknown in advance, and the algorithm suffers a loss ftxt. Repeating the process, we have a sequence of loss functions f1x1,f2x2,…,ftxt where ft:X⟶ℝ, and they vary with time t. In general, the online learner’s prediction problem can be represented as follows:(1)minx∈X∑t=1Tftx.For online learning tasks, the goal is to optimize the regretRT of the online learner’s predictions against the optimal decision in hindsight, which is defined as the difference in the total sum of loss functions ∑t=1Tftxt after performing online learning over T rounds and its minimum value ∑t=1Tftx∗ in the deterministic decision point x∗. In particular, we define the regret in the following:(2)RT=∑t=1Tftxt−∑t=1Tftx∗,where x∗≔argminx∈Xftx, t=1,2,…,T. It is desired that if the regret of online optimization algorithm is a sublinear function of T, which suggests limT⟶∞RT/T=0, then, on average, the online learner executes just and the fixed optimal decision afterwards. In other words, the proposed algorithm converges when its RT is bounded. Throughout this study, the diameter of convex compact set X is assumed to be bounded and ∇ftxt is bounded for all t=1,2,…,T. Hereafter, · denotes the ℓ2 norm.


## 3.2. Relevant Definitions

Now, we will describe the relevant definitions that are used in the next sections.Definition 1.
A functionf·:X⟶ℝ is L-Lipschitz, where L is Lipschitz constant, and L>0; if ∀x,y∈X,(3)fx−fy≤Lx−y.Definition 2.
(Equation (3.2) of Section 3 in [29]) A function f·:X⟶ℝ is convex and differentiable where X is a convex set; if ∀x,y∈X,(4)fy≥fx+∇fx,y−x.Definition 3.
A functionf·:X⟶ℝ is σ-strongly convex and differentiable, σ>0, and if ∀x,y∈X,(5)fy≥fx+∇fx,y−x+σ2x−y2.


## 4. SBAG Algorithm and Assumptions

This section presents the proposed algorithm, followed by the common assumptions for convergence analysis of the algorithm.


### 4.1. Algorithm Design

In this study, we develop the high-dimensional online learning problems and aim to solve the optimization problem (1) by incorporating the stochastic block coordination method and adaptive learning rate. Because the dimensionality n of the decision variable x is high, the computing cost of the gradients is prohibitive. In addition, the tuning of the learning rate is challenging. For these reasons, a stochastic block coordinate adaptive optimization algorithm, dubbed SBAG, is proposed for settling the online problem (1). In our algorithm, the objective functions at different times satisfy some conditions, which are displayed in Assumption 1.SBAG is described in Algorithm 1, whose input includesx1=0, m1=0, and v1=0. The parameters of SBAG are β1t∈0,1, β1≜β11, β2∈0,1, and αt=1/t, where t=1,2,…,T. At each round t, a n order diagonal matrix Mt is generated and includes random variables wt,i with ℙwt,i=0≔1−pt and ℙwt,i=1≔pt, for t=0,1,…,T and i=1,…,n. In particular, the gradient dt is computed as follows.(6)dt=Mt∇ftxt,where Mt≜diagwt=diagwt,1,wt,2,…,wt,n, and elements of wt consist of 0 and 1. When wt,i=1, it means that the ith coordinate of decision vector is selected to calculate the gradient at time t. From (6), one can observe that the computation cost is greatly reduced at each iteration. In addition, let ℋt denotes the σ− algebra, which means ℋt consists of all variables before time t. More explicitly, ℋt=M1,M2,…,Mt−1.Algorithm 1: SBAG.
Input: x1Parameter: x1∈X, and β1t∈0,1 where β11=β1 and β2∈0,1. pt denotes coordinate selection probability at time t. Moreover, β1t=β1λt where λ∈0,1 and t=1,2,…,T.Initially Set: m1=0 and v1=0.Output: xt+1(1)
fort=1,2,3,…do(2)
t←t+1(3)
Generating diagonal matrix Mt=diagwt with probability pt(4)
dt,i=∇iftxt,wt,i=10,wt,i=0(5)
Generating gradientdt=dt,1dt,2…dt,n(6)
mt=β1tmt−1+1−β1tdt(7)
vt=β2vt−1+1−β2dt2(8)
v^t=maxvt,vt−1 and Vt=diagv^t(9)
μ˜t= Clip α/Vt,μlowt,μuppt(10)
μt=μ˜t/t(11)
xt+1=ΠX,diagμt−1xt−μt°mt(12)
end for(13)
returnxt+1By Usingdt, one and second momentum terms mt and vt are obtained as follows, respectively.(7)mt=β1tmt−1+1−β1tdt,(8)vt=β2vt−1+1−β2dt2.Furthermore, SBAG introduces a bound of learning rate as follows:(9)μ˜t=ClipαVt,μlowt,μuppt,where each element of the learning rate α/Vt is clipped to constrain in an internal at time t, and the upper and lower bounds of the interval are μlowt and μuppt, respectively. That is, the output of equation (9) is constrained in μlowt,μuppt, and the technique was also used in [23, 24]. Moreover, let(10)μt=μ˜tt.Then, SBAG updatesxt+1 as follows:(11)xt+1=ΠX,diagμt−1xt−μt°mt,where ° is the coordinate-wise product operator. Furthermore, the projection step of equation (11) is equivalent to the following:(12)xt+1=argminx∈Xμt−1/2°x−xt−μt°mt.


### 4.2. Assumptions

Before presenting the convergence analysis of SBAG, we will now introduce the below common assumptions.Assumption 1.
Loss functionsf1x,f2x,…,ftx, where t=1,2,…,T, are convex, differentiable, and L-Lipschitz over X.Assumption 2.
In this study,X is a bounded feasible set; i.e., xi−xj≤B∞, where i,j∈1,2,…,T and B∞>0.Assumption 3.
In this study,∇ftxt is bounded for all t=1,2,…,T over X; i.e., ∇ftxt≤C∞, where C∞>0.
Assumptions1–3 are some standard assumptions in the literature, for example [18, 21, 24]. In addition, the convergence of SBAG is analyzed based on these assumptions in the following.


## 4.1. Algorithm Design

In this study, we develop the high-dimensional online learning problems and aim to solve the optimization problem (1) by incorporating the stochastic block coordination method and adaptive learning rate. Because the dimensionality n of the decision variable x is high, the computing cost of the gradients is prohibitive. In addition, the tuning of the learning rate is challenging. For these reasons, a stochastic block coordinate adaptive optimization algorithm, dubbed SBAG, is proposed for settling the online problem (1). In our algorithm, the objective functions at different times satisfy some conditions, which are displayed in Assumption 1.SBAG is described in Algorithm 1, whose input includesx1=0, m1=0, and v1=0. The parameters of SBAG are β1t∈0,1, β1≜β11, β2∈0,1, and αt=1/t, where t=1,2,…,T. At each round t, a n order diagonal matrix Mt is generated and includes random variables wt,i with ℙwt,i=0≔1−pt and ℙwt,i=1≔pt, for t=0,1,…,T and i=1,…,n. In particular, the gradient dt is computed as follows.(6)dt=Mt∇ftxt,where Mt≜diagwt=diagwt,1,wt,2,…,wt,n, and elements of wt consist of 0 and 1. When wt,i=1, it means that the ith coordinate of decision vector is selected to calculate the gradient at time t. From (6), one can observe that the computation cost is greatly reduced at each iteration. In addition, let ℋt denotes the σ− algebra, which means ℋt consists of all variables before time t. More explicitly, ℋt=M1,M2,…,Mt−1.Algorithm 1: SBAG.
Input: x1Parameter: x1∈X, and β1t∈0,1 where β11=β1 and β2∈0,1. pt denotes coordinate selection probability at time t. Moreover, β1t=β1λt where λ∈0,1 and t=1,2,…,T.Initially Set: m1=0 and v1=0.Output: xt+1(1)
fort=1,2,3,…do(2)
t←t+1(3)
Generating diagonal matrix Mt=diagwt with probability pt(4)
dt,i=∇iftxt,wt,i=10,wt,i=0(5)
Generating gradientdt=dt,1dt,2…dt,n(6)
mt=β1tmt−1+1−β1tdt(7)
vt=β2vt−1+1−β2dt2(8)
v^t=maxvt,vt−1 and Vt=diagv^t(9)
μ˜t= Clip α/Vt,μlowt,μuppt(10)
μt=μ˜t/t(11)
xt+1=ΠX,diagμt−1xt−μt°mt(12)
end for(13)
returnxt+1By Usingdt, one and second momentum terms mt and vt are obtained as follows, respectively.(7)mt=β1tmt−1+1−β1tdt,(8)vt=β2vt−1+1−β2dt2.Furthermore, SBAG introduces a bound of learning rate as follows:(9)μ˜t=ClipαVt,μlowt,μuppt,where each element of the learning rate α/Vt is clipped to constrain in an internal at time t, and the upper and lower bounds of the interval are μlowt and μuppt, respectively. That is, the output of equation (9) is constrained in μlowt,μuppt, and the technique was also used in [23, 24]. Moreover, let(10)μt=μ˜tt.Then, SBAG updatesxt+1 as follows:(11)xt+1=ΠX,diagμt−1xt−μt°mt,where ° is the coordinate-wise product operator. Furthermore, the projection step of equation (11) is equivalent to the following:(12)xt+1=argminx∈Xμt−1/2°x−xt−μt°mt.


## 4.2. Assumptions

Before presenting the convergence analysis of SBAG, we will now introduce the below common assumptions.Assumption 1.
Loss functionsf1x,f2x,…,ftx, where t=1,2,…,T, are convex, differentiable, and L-Lipschitz over X.Assumption 2.
In this study,X is a bounded feasible set; i.e., xi−xj≤B∞, where i,j∈1,2,…,T and B∞>0.Assumption 3.
In this study,∇ftxt is bounded for all t=1,2,…,T over X; i.e., ∇ftxt≤C∞, where C∞>0.
Assumptions1–3 are some standard assumptions in the literature, for example [18, 21, 24]. In addition, the convergence of SBAG is analyzed based on these assumptions in the following.


## 5. Convergence Analysis

Now, we will analyze the convergence of SBAG. We consider the regret, equation (2), in the online optimization problem (a typical scenario). The proposed algorithm generates the gradient dt with probability pt at time t. Therefore, dt is a random variable. Moreover, xt is calculated by dt and xt−1 at time t. According to the knowledge of probability and statistics, the expectation should be considered when the variable is randomized. Therefore, we define the regret of SBAG as follows:(13)R^T=∑t=1TEftxt−ftx∗.From the convexity offt, it follows that(14)ftxt−ftx∗≤∇ftxt⊤xt−x∗.Moreover, by the definition of matrixMt, we know that Mt is a sparse matrix. Therefore, applying equation (14) leads to(15)ftxt−ftx∗≤Mt∇ftxt⊤xt−x∗+∇ftxt⊤xt−x∗=dt⊤xt−x∗+∇ftxt⊤xt−x∗.Taking conditional expectation (conditioned onℋt) on both sides of equation (15), it implies that(16)Eftxt|ℋt−Eftx∗|ℋt≤Edt⊤xt−x∗|ℋt+E∇ftxt⊤xt−x∗|ℋt.By equation (1.1f) of Section 4 in [30], and taking unconditional expectation for equation (16), it follows that(17)Eftxt−ftx∗≤Edt⊤xt−x∗+E∇ftxt⊤xt−x∗.From equations (13) and (17), the following equation holds(18)R^T=∑t=1TEdt⊤xt−x∗+∑t=1TE∇ftxt⊤xt−x∗.To get the bound ofR^T, we should consider the two terms on the right side of equation (18). Thus, we first propose the following lemmata to estimate term ∑t=1TEdt⊤xt−x∗.Lemma 1.
If Assumptions1 to 3 are satisfied, sequences xt,mt, and vt are generated by SBAG with t∈1,2,…,T. Moreover, X is a convex and compact set. β1≔β11,β1t≤β1t−1≤β1, and β1/β2≤1 for t=1,…,T. In addition, suppose μlowt+1≥μlowt≥0,μuppt+1≤μuppt, and limt⟶∞μlowt=limt⟶∞μuppt=α, where α>0. Let L∞≔μlow1, U∞≔μupp1, and pt∈pmin,pmax. Then, we have the following relation:(19)∑t=1TEμt1/2°mt2≤pmaxβ1U∞2T−11−β1∑i=1nd1:T,i2.Proof.
From equations (9) and (10), it follows that(20)tμt∞≤μuppt≤μupp1≔U∞,and(21)tμt∞≥μlowt≥μlow1≔L∞.
From equations (20) and (21), and by property of expectation, it can be verified that(22)∑t=1TEμt1/2°mt2≤∑t=1TEmt2U∞t=U∞∑t=1Tptmt2t≤pmaxU∞∑t=1Tmt2t,=pmaxU∞∑t=1T−1mt2t+pmaxU∞∑i=1nmT,i2T.
Plugging equation (7) into equation (22), it yields(23)∑t=1TEμt1/2°mt2≤pmaxU∞∑t=1T−1mt2t+pmaxU∞T∑i=1n∑j=1T1−β1j∏k=1T−jβ1T−k+1dj,i2︸a.
By Cauchy–Schwarz inequality, we further bound the term (a) of equation (23) and have(24)a≤∑i=1n∑j=1T∏k=1T−jβ1T−k+1∑j=1T∏k=1T−jβ1T−k+1dj,i2≤∑i=1n∑j=1Tβ1T−j∑j=1Tβ1T−jdj,i2≤11−β1∑i=1n∑j=1Tβ1T−jdj,i2.
The second inequality of equation (24) follows from the fact β1k≤β1 for all k∈1,…,T. In addition, the third inequality of equation (24) is due to the inequality ∑j=1Tβ1T−j≤1/1−β1. Moreover, plugging equation (24) into equation (23) leads to(25)∑t=1TEμt1/2°mt2≤pmaxU∞∑t=1T−1mt2t+pmaxU∞1−β1T∑i=1n∑j=1Tβ1T−jdj,i2≤pmaxU∞1−β1∑t−1T1t∑i=1n∑j=1tβ1t−jdj,i2≤pmaxU∞1−β1∑i=1n∑t−1T1t∑j=1tβ1t−jdj,i2≤pmaxU∞1−β1∑i=1n∑t−1Tdt,i2∑j=1tβ1t−jj≤pmaxβ1U∞1−β1∑i=1n∑t−1Tdt,i2∑j=1t1j.
Moreover, since∑t=1T1/t≤1+∫1T1/tdt=2T−1, and by equation (25), it follows that(26)∑t=1TEμt1/2°mt2≤pmaxβ1U∞2T−11−β1∑i=1n∑t−1Tdt,i2≤pmaxβ1U∞2T−11−β1∑i=1nd1:T,i2.
Therefore, the proof of Lemma1 is completed. Next, we introduce Lemma 2 to estimate the term ∑t=1TEdt⊤xt−x∗.Lemma 2.
If Assumptions1 to 3 are satisfied, sequences xt,mt, and vt are generated by SBAG with t∈1,2,…,T. Moreover, X is a convex and compact set. β1≔β11,β1t≤β1t−1≤β1, and β1/β2≤1, for t=1,…,T. In addition, suppose μlowt+1≥μlowt≥0,μuppt+1≤μuppt, and limt⟶∞μlowt=limt⟶∞μuppt=α, where α>0. Let L∞≔μlow1, U∞≔μupp1, and pt∈pmin,pmax. Then, we have the following:(27)∑t=1TEdt⊤xt−x∗≤B∞2L∞T21−β1pmin+β1B∞2L∞21−β11−λpmin+pmaxβ1U∞2T−11−β12∑i=1nd1:T,i2.Proof.
Letx∗≔argminx∈Xftx with t=1,2,…,T. By equations (11) and (12), the following equation holds(28)xt+1=ΠX,diagμt−1xt−μt°mt=argminx∈Xμt−1/2°x−xt−μt°mt.
Using Lemma 3 of [31], it can be proved that(29)μt−1/2°xt+1−x∗2≤μt−1/2°xt−μt°mt−x∗2=μt−1/2°xt−x∗2−2mt⊤xt−x∗+μt1/2°mt2.
Substituting equation (7) into equation (29) yields(30)μt−1/2°xt+1−x∗2≤μt−1/2°xt−x∗2+μt1/2°mt2−2β1tmt−1+1−β1tdt⊤xt−x∗,=μt−1/2°xt−x∗2+μt1/2°mt2−2β1tmt−1⊤xt−x∗−21−β1tdt⊤xt−x∗.
Rearranging the terms of equation (30), and by β1t≤β1t−1, it follows that(31)dt⊤xt−x∗≤μt−1/2°xt−x∗221−β1t+μt1/2°mt221−β1t−β1tmt−1⊤xt−x∗1−β1t−μt−1/2°xt+1−x∗221−β1t≤μt−1/2°xt−x∗2−μt−1/2°xt+1−x∗221−β1t+μt1/2°mt221−β1t+β1tmt−1⊤xt−x∗1−β1t.
Applying Young’s inequality and the Cauchy–Schwarz inequality into equation (31) leads to(32)dt⊤xt−x∗≤μt−1/2°xt−x∗2−μt−1/2°xt+1−x∗221−β1t+μt1/2°mt221−β1t+β1t21−β1tμt1/2°mt−12+β1t21−β1tμt−1/2°xt−x∗2.
Summing equation (32) over t∈1,2,…,T and taking expectation on the obtained relation imply that(33)∑t=1TEdt⊤xt−x∗≤Eμt−1/2°xt−x∗2−μt−1/2°xt+1−x∗221−β1t+121−β1tEμt1/2°mt2+μt1/2°mt−12+121−β1tEβ1tμt−1/2°xt−x∗2≤Eμt−1/2°xt−x∗2−μt−1/2°xt+1−x∗221−β1+121−β1Eμt1/2°mt2+μt1/2°mt−12+121−β1Eβ1tμt−1/2°xt−x∗2.
By Lemma1 and equation (33), it follows from that(34)∑t=1TEdt⊤xt−x∗≤∑t=1TEμt−1/2°xt−x∗221−β1≤−∑t=1TEμt−1/2°xt+1−x∗221−β1+∑t=1TEβ1tμt−1/2°xt−x∗221−β1+pmaxβ1U∞2T−11−β12∑i=1nd1:T,i2≤E∑i=1nμ1,i−1x1,i−xi∗221−β1+E∑t=2T∑i=1nμt,i−1xt,i−xi∗2−μt−1,i−1xt,i−xi∗221−β1+∑t=1T∑i=1nEβ1tμt,i−1xt,i−xi∗221−β1+pmaxβ1U∞2T−11−β12∑i=1nd1:T,i2.
Sinceμt=μ˜t/t=α/tv^t and v^t=maxvt,vt−1, we have 0<μt≤μt−1. Therefore, we further obtain μt−1≥μt−1−1. Then, from equation (34), it can be proved that(35)∑t=1TEdt⊤xt−x∗≤E∑i=1nμ1,i−1x1,i−xi∗221−β1+E∑t=2T∑i=1nμt,i−1xt,i−xi∗2−μt−1,i−1xt,i−xi∗221−β1+∑t=1T∑i=1nEβ1tμt,i−1xt,i−xi∗221−β1+2T−1pmax2U∞C∞21−β1≤E∑i=1nμT,i−1xT,i−xi∗221−β1+∑t=1T∑i=1nEβ1tμt,i−1xt,i−xi∗221−β1+pmaxβ1U∞2T−11−β12∑i=1nd1:T,i2.
Applying Assumption2 and property of expectation yields(36)∑t=1TEdt⊤xt−x∗≤B∞221−β1pmin∑i=1nμT,i−1+B∞221−β1pmin∑t=1T∑i=1nβ1tμt,i−1+pmaxβ1U∞2T−11−β12∑i=1nd1:T,i2≤B∞2L∞T21−β1pmin+β1B∞2L∞21−β11−λpmin+pmaxβ1U∞2T−11−β12∑i=1nd1:T,i2.
Therefore, the proof of Lemma2 is completed. Next, we estimate the last term in (18).Lemma 3.
If Assumptions1 to 3 are satisfied, sequences xt,mt, and vt are generated by SBAG with t∈1,2,…,T. Moreover, X is a convex and compact set. β1≔β11,β1t≤β1 and β1/β2≤1, for t=1,…,T. In addition, suppose μlowt+1≥μlowt≥0,μuppt+1≤μuppt, and limt⟶∞μlowt=limt⟶∞μuppt=α, where α>0. Let L∞≔μlow1 and U∞≔μupp1. Then, we attain the following inequality:(37)∑t=1TE∇ftxt⊤xt−x∗≤B∞2L∞T21−β1+β1B∞2L∞21−β11−λ+β1U∞2T−11−β12∑i=1nd1:T,i2.Proof.
For the original full gradient, we haveE∇ftxt=∇ftxt. Let mt′≔β1tmt−1′+1−β1t∇ftxt, vt′=β2vt−1′+1−β2∇ft2xt, and μt′=μ˜t′/t, which are generated by AdaBound [24].
The proof of Lemma3 is similar to that of Theorem 4 in [24]. Starting with the following inequality implies(38)∑t=1TE∇ftxt⊤xt−x∗≤μ′t−1/2°xt−x∗2−μ′t−1/2°xt+1−x∗221−β1+μ′t1/2°mt′2+μ′t1/2°mt−1′221−β1+β1tμ′t−1/2°xt−x∗221−β1≤μ′t−1/2°xt−x∗2−μ′t−1/2°xt+1−x∗221−β1+β1tμ′t−1/2°xt−x∗221−β1+β1U∞2T−11−β12∑i=1nd1:T,i2≤B∞2L∞T21−β1+β1B∞2L∞21−β11−λ+β1U∞2T−11−β12∑i=1nd1:T,i2.
Therefore, the proof of Lemma3 is finished.
To attain the bound of regretR^T in equation (18), we establish Theorem 1 as follows.Theorem 1.
Suppose that Assumptions1 to 3 are satisfied, and sequences xt,mt, and vt are generated by SBAG with t∈1,2,…,T. Moreover, X is a convex and compact set. β1≔β11,β1t≤β1, and β1/β2≤1 for t=1,…,T. In addition, suppose μlowt+1≥μlowt≥0,μuppt+1≤μuppt, and limt⟶∞μlowt=limt⟶∞μuppt=α, where α>0. Let L∞≔μlow1, U∞≔μupp1, and pt∈pmin,pmax. We obtain the bound of regret as follows:(39)R^T≤1+pminB∞2L∞T21−β1pmin+β11+pminB∞2L∞21−β11−λpmin+1+pmaxβ1U∞2T−11−β12∑i=1nd1:T,i2.Proof.
Applying lemmata 1, 2, and 3 into (18) yields(40)R^T≤B∞2L∞T21−β1pmin+β1B∞2L∞21−β11−λpmin+pmaxβ1U∞2T−11−β12∑i=1nd1:T,i2+B∞2L∞T21−β1+β1B∞2L∞21−β11−λ+β1U∞2T−11−β12∑i=1nd1:T,i2=1+pminB∞2L∞T21−β1pmin+β11+pminB∞2L∞21−β11−λpmin+1+pmaxβ1U∞2T−11−β12∑i=1nd1:T,i2.
Therefore, we complete the proof of Theorem1.
From Theorem1, we obtain limT⟶∞R^T/T=0. This suggests that SBAG is convergent. In addition, the bound of regret R^T is OT; i.e., given some accuracy ε, it requires an order of O1/ε2 iterations at least to achieve the given accuracy.


## 6. Performance Evaluation

In this section, we perform our experiments on a public dataset to evaluate the performance of algorithm objectively. We consider the machine learning problem, multi-classification tasks taking advantage of the DNN for the experiments.


### 6.1. Setup

To assess our SBAG algorithm, we research the performance on the classification task problem. We use the CIFAR-10 [32] dataset for our experiments, which is widely used for classification problem. It consists of 10 classes and 50000 training samples and 10000 test samples.For the experiments, we use the convolutional neural network to solve classification tasks on the CIFAR-10 image dataset, which has a good effect on image classification and object recognition, and specifically implement ResNet-34 [33] and DenseNet-121 [34].


### 6.2. Parameters

To study the performance of our proposed algorithm, we compare SBAG with SGD [14], AdaGrad [15], and AdaBound [24]. The hyper-parameters of these algorithms are initialized as follows.For SGD, the scale of the learning rate is selected from the set100,10,1,0.1,0.01. AdaGrad uses the initialized learning rate set 5e−2,1e−2,5e−3,1e−3,5e−4, and the value 0 is set for the initial accumulator value of AdaGrad. The value of hyper-parameters of AdaBound is set the same as Adam. We directly use the initialized hyper-parameter values of AdaBound in our algorithm. In addition, we set the probability of choosing a coordinate from these values in the set 0.10%,0.50%,1.00%,5.00%,10.00%,50.00%.In addition, we define the dynamic bound functions following with [24] for our simulation experiments, i.e.,(41)μlowt=0.1−0.11−β2t+1,and(42)μuppt=0.1+0.11−β2t.


### 6.3. Results

We take account of the image multi-class classification problem on the CIFAR-10 dataset using ResNet-34 and DenseNet-121 and run 200 epoch in this experiment. First, we operate a group of experiments with epochs and runtime for ResNet-34 and DenseNet-121 on CIFAR-10. The findings of experiments are reported in Figure1, and when completing the same number of iterations of 200 epochs, our method takes the least time, and the AdaBound spends the most time. The main reason is that only several blocks of coordinates are calculated in the gradient descent process for our algorithm at each iteration t, while the compared algorithms calculate the full gradients at each iteration. Moreover, AdaBound combines the first- and second-order momentum, while SGD and AdaGrad only use first-order gradients; thus, SGD and AdaGrad incur less time than AdaBound. The same results can be seen for the DenseNet-121 in Figure 1(b).Figure 1
Running time with epochs for ResNet-34 and DenseNet-121 on CIFAR-10: a comparative summary. (a) Runtime for ResNet-34. (b) Runtime for DenseNet-121.
(a)(b)We present another group of experiments with average loss and running time, which are executed for ResNet-34 and DenseNet-121 on CIFAR-10. The findings are shown in Figure2. At about 150 epochs, SGD has the biggest average loss than others and decreases sharply after that time, while the average loss of SBAG is smaller compared with others and reaches the minimum value in the shortest running time finally. The reason for fast descent rate of SBAG is due to the randomized block method, which chooses one block coordinate of decision vector to calculate the gradient. In other words, SBAG calculates more samples than other compared algorithms in the same running time. Therefore, the convergence of SBAG is verified by the findings presented in Figure 2.Figure 2
Loss with running time for ResNet-34 and DenseNet-121 on CIFAR-10: a comparative summary. (a) Loss for ResNet-34. (b) Loss for DenseNet-121.
(a)(b)In Figures3 and 4, the training and test accuracy with running time of four algorithms are evaluated. As we can see, in about 150 epochs, AdaBound achieves the highest accuracy, and AdaGrad and our algorithm almost have the same accuracy of 92.36% and 93.99%. As the running time goes, the AdaBound and SBAG have the accuracy of 99.96% and 99.93%, respectively. The similar results can be seen on the DenseNet-121. In a word, SBAG works well on training or test set, and at the same time, it has the good generalization ability on both ResNet-34 and DenseNet-121.Figure 3
Training accuracy with running time for ResNet-34 and DenseNet-121 on CIFAR-10: a comparative summary. (a) Training accuracy for ResNet-34. (b) Training accuracy for DenseNet-121.
(a)(b)Figure 4
Test accuracy with running time for ResNet-34 and DenseNet-121 on CIFAR-10: a comparative summary. (a) Test accuracy for ResNet-34. (b) Test accuracy for DenseNet-121.
(a)(b)From the experiments above, we observe that the SBAG shows a very good performance on both ResNet-34 and DenseNet-121. It incurs less computation cost for each iteration in experiments, which is consistent with theory.


## 6.1. Setup

To assess our SBAG algorithm, we research the performance on the classification task problem. We use the CIFAR-10 [32] dataset for our experiments, which is widely used for classification problem. It consists of 10 classes and 50000 training samples and 10000 test samples.For the experiments, we use the convolutional neural network to solve classification tasks on the CIFAR-10 image dataset, which has a good effect on image classification and object recognition, and specifically implement ResNet-34 [33] and DenseNet-121 [34].


## 6.2. Parameters

To study the performance of our proposed algorithm, we compare SBAG with SGD [14], AdaGrad [15], and AdaBound [24]. The hyper-parameters of these algorithms are initialized as follows.For SGD, the scale of the learning rate is selected from the set100,10,1,0.1,0.01. AdaGrad uses the initialized learning rate set 5e−2,1e−2,5e−3,1e−3,5e−4, and the value 0 is set for the initial accumulator value of AdaGrad. The value of hyper-parameters of AdaBound is set the same as Adam. We directly use the initialized hyper-parameter values of AdaBound in our algorithm. In addition, we set the probability of choosing a coordinate from these values in the set 0.10%,0.50%,1.00%,5.00%,10.00%,50.00%.In addition, we define the dynamic bound functions following with [24] for our simulation experiments, i.e.,(41)μlowt=0.1−0.11−β2t+1,and(42)μuppt=0.1+0.11−β2t.


## 6.3. Results

We take account of the image multi-class classification problem on the CIFAR-10 dataset using ResNet-34 and DenseNet-121 and run 200 epoch in this experiment. First, we operate a group of experiments with epochs and runtime for ResNet-34 and DenseNet-121 on CIFAR-10. The findings of experiments are reported in Figure1, and when completing the same number of iterations of 200 epochs, our method takes the least time, and the AdaBound spends the most time. The main reason is that only several blocks of coordinates are calculated in the gradient descent process for our algorithm at each iteration t, while the compared algorithms calculate the full gradients at each iteration. Moreover, AdaBound combines the first- and second-order momentum, while SGD and AdaGrad only use first-order gradients; thus, SGD and AdaGrad incur less time than AdaBound. The same results can be seen for the DenseNet-121 in Figure 1(b).Figure 1
Running time with epochs for ResNet-34 and DenseNet-121 on CIFAR-10: a comparative summary. (a) Runtime for ResNet-34. (b) Runtime for DenseNet-121.
(a)(b)We present another group of experiments with average loss and running time, which are executed for ResNet-34 and DenseNet-121 on CIFAR-10. The findings are shown in Figure2. At about 150 epochs, SGD has the biggest average loss than others and decreases sharply after that time, while the average loss of SBAG is smaller compared with others and reaches the minimum value in the shortest running time finally. The reason for fast descent rate of SBAG is due to the randomized block method, which chooses one block coordinate of decision vector to calculate the gradient. In other words, SBAG calculates more samples than other compared algorithms in the same running time. Therefore, the convergence of SBAG is verified by the findings presented in Figure 2.Figure 2
Loss with running time for ResNet-34 and DenseNet-121 on CIFAR-10: a comparative summary. (a) Loss for ResNet-34. (b) Loss for DenseNet-121.
(a)(b)In Figures3 and 4, the training and test accuracy with running time of four algorithms are evaluated. As we can see, in about 150 epochs, AdaBound achieves the highest accuracy, and AdaGrad and our algorithm almost have the same accuracy of 92.36% and 93.99%. As the running time goes, the AdaBound and SBAG have the accuracy of 99.96% and 99.93%, respectively. The similar results can be seen on the DenseNet-121. In a word, SBAG works well on training or test set, and at the same time, it has the good generalization ability on both ResNet-34 and DenseNet-121.Figure 3
Training accuracy with running time for ResNet-34 and DenseNet-121 on CIFAR-10: a comparative summary. (a) Training accuracy for ResNet-34. (b) Training accuracy for DenseNet-121.
(a)(b)Figure 4
Test accuracy with running time for ResNet-34 and DenseNet-121 on CIFAR-10: a comparative summary. (a) Test accuracy for ResNet-34. (b) Test accuracy for DenseNet-121.
(a)(b)From the experiments above, we observe that the SBAG shows a very good performance on both ResNet-34 and DenseNet-121. It incurs less computation cost for each iteration in experiments, which is consistent with theory.


## 7. Conclusion

In this study, we proposed a randomized block adaptive gradient online learning algorithm. The proposed algorithm, SBAG, is designed to reduce the gradient computation cost of high-dimensional decision vector. The convergence analysis of SBAG and evaluations on CIFAR-10 demonstrated that the regret bound of SBAG isOT when loss functions are convex and achieved significant computation cost savings, without adversely affecting the performance of the optimizer. In the same 200 epochs, the proposed algorithm has the least running time and tightly less in average loss in the end. The accuracy of training sample for ResNet-34 and DenseNet-121 is 99.93% and 99.72%, slightly less compared with that of 99.96% of AdaBound, but our method reaches the highest accuracy on the test sample than AdaBound, SGD, and AdaGrad; i.e., SBAG is the fastest in four methods, and the curves are milder than SGD.



---

*Source: 9337209-2022-06-02.xml*