# A Projection-Free Adaptive Momentum Optimization Algorithm for Mobile Multimedia Computing

Authors: Lin Wang; Yangfan Zhou; Xin Wang; Zhihang Ji; Xin Liu
Journal: Wireless Communications and Mobile Computing
 (2022)

---

## Abstract

In mobile multimedia applications, deep learning has received significant interest. Due to the limited computation and storage resources of mobile devices, however, general training methods are hardly suited for mobile multimedia computing. For this reason, we propose an adaptive momentum training (FWAdaBound) algorithm to reduce computation and storage cost, where the Frank-Wolfe method is employed. Furthermore, we rigorously prove the regret bound in order thatOT3/4 can be achieved, where T is a time horizon. Finally, the convergence, cost-reduction, and generalization ability of FWAdaBound are validated through various experiments on public datasets.


---

## Body

## 1. Introduction

In mobile multimedia applications [1, 2], deep learning is a significant method for multimedia computing [3]. Meanwhile, various deep learning models have been successfully implemented in many important fields, such as convolutional neural network [4, 5], recurrent neural network [6, 7], deep belief networks [8, 9], and industrial internet applications [10]. In order to implement deep learning models in mobile multimedia, the training of deep neural networks is a crucial technology. Moreover, because the computation and storage resources of each mobile device is limited, general training methods of deep neural networks are hardly adapted to mobile multimedia computing. For this reason, how to train rapidly deep learning models with lower computational cost is one of challenging tasks in mobile multimedia applications.In fact, the training process of deep neural networks can be regarded as an optimization process. For this reason, the design of optimization algorithms is necessary in the training process. Currently, stochastic gradient descent (SGD) is a dominative algorithm for training deep networks. SGD is applied widely over the past years since its good generalization ability and could be implemented easily. Despite SGD having performed well in some applications, however, it converges slowly. To accelerate the convergence of SGD, many researchers have proposed various adaptive momentum algorithms based on gradient descent. Generally, optimizing step size and gradient direction of SGD are two main directions that have been studied by researchers.SGD often oscillates around the optimal solution when step sizes are fixed. To address this issue, some novel algorithms with adaptive step size have been proposed. AdaGrad [11], RMSProp [12], and Adadelta [13] make step sizes changed adaptively as training process goes on. Besides, the current gradient direction in each iteration is randomly selected, thereby it cannot find the direction to reach the optimal solution in the shortest time. For this reason, historical gradient information has been used to adjust the current gradient direction in many novel algorithms. Moreover, these algorithms often use the first-order momentum to maintain historical gradient information and the second-order momentum to adaptive step size at the same time (Adam [14], AMSGrad [15], and AdaBound [16]). It is generally believed that algorithms combining first-order and second-order momentum originated from Adam and are Adam-type algorithms.Being an Adam-type algorithms, AdaBound not only inherits good generalization ability of SGD but also maintains fast convergence rate of Adam. However, like other Adam-type algorithm else, AdaBound also uses higher-order projection operators to handle the case where the iteration point is not within the feasible region. Since the projection operation includes the second-order Euclidean distance calculation or higher-order methods measurement, it has a large computational cost in each iteration. Therefore, algorithms with projection operations like AdaBound become prohibitive when dealing with large-scale problems including massive high-dimensional data. To tackle this problem, we focus on proposing a projection-free algorithm based on AdaBound. In the field of optimization, the Frank-Wolfe method is one of the projection-free technologies, which is commonly used in replacing high-order projection operators with linear searches. Therefore, in this paper, we redesign AdaBound algorithm, which is called FWAdaBound by using the Frank-Wolfe method to reduce computation cost of AdaBound. Moreover, we prove that the FWAdaBound algorithm converges under convex conditions and attain a guaranteed regret bound related to the sublinear correlation of time horizon. In addition, FWAdaBound successfully retains AdaBound’s performance on convergence and generalization ability.In this paper, the summary of our contributions is presented as follows:(i)
We propose the FWAdaBound algorithm based on the Frank-Wolfe method and AdaBound optimization algorithm to eliminate costly projection steps in large-scale problems(ii)
We prove the convergence of FWAdaBound under the online learning framework. Moreover, we also show that the regret of FWAdaBound isOT3/4, where T is a time horizon(iii)
We present various of experiments to validate computation cost reduction of FWAdaBound and show good generalization ability of FWAdaBound on public datasetThe rest of this paper is organized as follows: in Section2, we review some important related work of FWAdaBound. In Section 3, we introduce preliminary knowledge about optimization object and online learning. In Sections 4, we present some frequently used assumptions and detailed design of FWAdaBound. In Section 5, we prove the convergence of FWAdaBound in theory and obtain the regret bound. In Section 6, we conduct various experiments in detail on public datasets. Finally, we present the conclusion of this paper in Section 7.


## 2. Related Work

SGD performs linear iteration of decision variables based on gradient. Therefore, SGD is one of the simplest and easiest implemented algorithms in deep learning. It has good generalization ability if labeled training samples are sufficient. However, the slow convergence rate of SGD always makes it difficult to converge to optima under limited labeled training samples. To speed up convergence rate of SGD, the first-order momentum and the second-order momentum based on the gradient are used in optimization algorithms. More specifically, the fist-order momentum of the gradient is used to retain historical information of gradient, and the second-order momentum of gradient is used to make the step size adaptive. The first algorithm combining these two momentums of gradient is Adam, which obtains a faster convergence rate than SGD [14]. However, Reddi et al. found that the convergence proof of Adam was problematic and proposed an improved variant of Adam, called AMSGrad [15]. Moreover, [17] advocated that it is beneficial to consider more past gradients when designing adaptive learning rates, and thereby, they proposed NosAdam.Despite Adam, AMSGrad, and NosAdam both improving the convergence rate, however, these three algorithms all have lower generalization ability than SGD under sufficient training samples. For this reason, [18] proposed SWATS to improve generalization performance by switching from Adam to SGD in the later stages of training. Although SWATS improves generalization ability for adaptive momentum algorithms, its switching time is difficult to be accurately controlled. Based on works mentioned above, [16] analyzed that unstable and extreme learning rates may lead to the lack of generalization performance of adaptive methods. Moreover, [16] used a dynamic boundary of the learning rate, where the upper and lower limits can smoothly converge to a constant final step size, respectively. Furthermore, the algorithm proposed is called AdaBound. Therefore, AdaBound currently performs better in terms of convergence speed and generalization ability compared with other algorithms.Although AdaBound performs well in the convergence rate and generalization ability, projection steps in AdaBound produce numbers of computation cost and make training process prohibit when dealing with large-scale problems. To be specific, the projection operator defined asΠF,M can be formed as follows:
(1)ΠF,My=argminx∈FM1/2x−y,where F is a convex feasible set, x is a decision variable in the feasible domain, and y is an unknown variable.Equation (1) shows the high-order calculation method of a projection operation, which brings a lot of calculation cost to the algorithm. The efficiency of algorithms like AdaBound are highly dependent on time and hardware. Therefore, it is necessary to eliminate projection steps of AdaBound in order to improve its efficiency. However, this much needed algorithm has not yet been proposed. For this reason, we propose a projection-free algorithm based on AdaBound, which uses the Frank-Wolfe method to replace high-order projection steps with one-dimensional linear searches.


## 3. Preliminaries

In this section, we first introduce some notations for convenience. Throughout this paper, we let a boldtype letter, likex, denote a vector. For operative symbol, we let x/y denote the element-wise division, x2 denotes the element-wise square, and x denotes the element-wise square root. For the tth iteration, we let xt denote the decision vector, ft denote the cost function, and xt,i denote the ith coordinate of xt. Moreover, diagx denotes a diagonal matrix generated by the elements of x in order, max·,· represents element-wise maximum, and ·,· denotes the scalar inner product. In addition, we let R denote the real number set and ΠF,M· denotes the weighted projection operation, where F is a feasible set and M represents a positive definite matrix.In this paper, we consider an online convex optimization problem, in which the cost function changes over the time or iteration. IfF⊂R is a convex and compact set, the decision vector x∈F, and the cost function at time t is ft; then, we focus on the following optimization objective:
(2)minx∈F∑t=1Tftx.In order to solve the online optimization problem, i.e., Equation (2), an online optimization algorithm is required. In addition, to measure the performance of an online optimization algorithm, one of standard approaches is regret. Moreover, if we let x∗ denote the theoretical optimal solution, then the definition of regret is as follows:
(3)RT=∑t=1Tftxt−∑t=1Tftx∗,where t=1,⋯,T, and x∗=argminx∈Ffx.


## 4. Algorithm Design and Assumptions

In this section, the proposed algorithm design will be firstly introduced in detail. Then, to analyze the convergence of the proposed algorithm, we present some reasonable assumptions.


### 4.1. Algorithm Design

The input of FWAdaBound isx1∈F, where F is a convex and compact set. The parameter β1t∈0,1 and let β11=β1. Moreover, the parameter β2∈0,1. In addition, the parameters α,η∈0,1. Let gt denote the gradient at time t∈1,⋯,T; thus, gt=∇ftxt. The overall idea of our algorithm is as follows:At first, we use the first-order momentum of the gradientut to define the sum function for time t: Stx=η∑τ=1tuτ,x+x−x12; then, we use this function to implement one-dimensional linear search wt=argminx∈F∇Stxt,x, which can accelerate convergence and avoid projection operators, so it is the key of FWAdaBound to reduce the computational cost. Next, we introduce second-order momentum dt and use it to generate the dynamic upper bound of learning rate ϖt adaptively. Finally, we apply ϖt to update the decision variable as xt+1=xt+ϖtewt−xt. The specific algorithm is shown in Algorithm 1.The first-order momentum of the gradient,ut, is computed by FWAdaBound for time t as follows:
(4)ut=β1tut−1+1−β1tgt.The first-order momentum is generated by weighted average of the current gradient and the historical gradient, which speed up convergence rate for optimization algorithms. Next, to implement one-dimensional linear search which replaces of the projection operators, we define the following sum function for timet:
(5)Stx=η∑τ=1tuτ,x+x−x12.To reduce the computational cost of the projection operation, FWAdaBound searches the feasible variable,wt, through one-dimensional linear as follows:
(6)wt=argminx∈F∇Stxt,x.Moreover, to realize the adaptive learning rate, FWAdaBound computes the second-order momentum of the gradient,dt, for time t as follows:
(7)dt=β2dt−1+1−β2gt2.To ensure the convergence of the proposed algorithm, FWAdaBound chooses the bigger value fromdt,dt−1 for time t, i.e. d^t=maxdt,dt−1. In addition, the diagonal matrix, Dt, based on d^t is defined as Dt=diagd^t. Next, FWAdaBound generates a dynamic bound for learning rate at time t:
(8)ϖt=ClipαtDt,ϖlowtt,ϖupptt,where ϖlowt is the lower bound and ϖuppt is the upper bound. Therefore, Equation (5) clips the output of αt/Dt between the low bound and the upper bound. Finally, FWAdaBound updates the decision variable for time t+1 as follows:
(9)xt+1=xt+ϖt⨀wt−xt.Algorithm 1: FWAdaBound
Input: x1Parameter: x1∈F, and β1t∈0,1 where β11=β1, β2∈0,1. Moreover, α,η∈0,1.Initially set: m1=0 and v1=0.Output: xt+11:fort=1,2,3,⋯do2:t⟵t+13: Compute gradient of decision variables at timet:4:gt=∇ftxt5: Compute the first-order momentum at timet:6:ut=β1tut−1+1−β1tgt7: Generate a new sum function:8:Stx=η∑τ=1t‍uτ,x+∥x−x1∥29: Searchwt by one-dimensional linearly:10:wt=argminx∈F∇Stxt,x11: Compute the second-order momentum at timet:12:dt=β2dt−1+1−β2gt213: Select a bigger value for the second-order momentum:14:d^t=maxdt,dt−1 and Dt=diagd^t15: Compute the dynamic bound for learning rate at timet:16:ϖt=Clipαt/Dt,ϖlowt/t,ϖuppt/t17: Update the decision variables for timet+1:18:xt+1=xt+ϖtewt−xt19:end for20:returnxt+1Therefore, the design of the proposed algorithm is introduced completely. And we present some following common assumptions, which are the premises of the convergence of the algorithm.


### 4.2. Assumptions

Next, three assumptions are presented for the proposed algorithm as follows.Assumption 1.
The constraint setF is convex and compact. Moreover, the set F is bounded, i.e., x−y∞≤B∞ for all x,y∈F, where B∞>0.Assumption 2.
The cost functionft of FWAdaBound is convex and differentiable on F for all t∈1,⋯,T. In addition, all the cost functions, f1,⋯,ft, are Lipschitz functions with L constant, where L>0.Assumption 3.
The gradient of decision variablext is bounded for all t∈1,2,⋯,T over F, i.e., gt=∇ftxt≤G∞, where G∞>0.Assumption1 is one of the most basic assumptions of projection-free method, and almost all projection-free related articles use it, such as these classic articles [19, 20]. Assumption 2–3 are supposed commonly and reasonably for analyzing convergence of optimization algorithms such as these research works [14–16]. Next, we present the convergence analysis of the proposed algorithms based on Assumptions 1–3.In many research works [14–16], Assumptions 1–3 were supposed commonly and reasonably for analyzing convergence of proposed algorithms. Next, we present the convergence analysis of the proposed algorithms based on Assumptions 1–3.


## 4.1. Algorithm Design

The input of FWAdaBound isx1∈F, where F is a convex and compact set. The parameter β1t∈0,1 and let β11=β1. Moreover, the parameter β2∈0,1. In addition, the parameters α,η∈0,1. Let gt denote the gradient at time t∈1,⋯,T; thus, gt=∇ftxt. The overall idea of our algorithm is as follows:At first, we use the first-order momentum of the gradientut to define the sum function for time t: Stx=η∑τ=1tuτ,x+x−x12; then, we use this function to implement one-dimensional linear search wt=argminx∈F∇Stxt,x, which can accelerate convergence and avoid projection operators, so it is the key of FWAdaBound to reduce the computational cost. Next, we introduce second-order momentum dt and use it to generate the dynamic upper bound of learning rate ϖt adaptively. Finally, we apply ϖt to update the decision variable as xt+1=xt+ϖtewt−xt. The specific algorithm is shown in Algorithm 1.The first-order momentum of the gradient,ut, is computed by FWAdaBound for time t as follows:
(4)ut=β1tut−1+1−β1tgt.The first-order momentum is generated by weighted average of the current gradient and the historical gradient, which speed up convergence rate for optimization algorithms. Next, to implement one-dimensional linear search which replaces of the projection operators, we define the following sum function for timet:
(5)Stx=η∑τ=1tuτ,x+x−x12.To reduce the computational cost of the projection operation, FWAdaBound searches the feasible variable,wt, through one-dimensional linear as follows:
(6)wt=argminx∈F∇Stxt,x.Moreover, to realize the adaptive learning rate, FWAdaBound computes the second-order momentum of the gradient,dt, for time t as follows:
(7)dt=β2dt−1+1−β2gt2.To ensure the convergence of the proposed algorithm, FWAdaBound chooses the bigger value fromdt,dt−1 for time t, i.e. d^t=maxdt,dt−1. In addition, the diagonal matrix, Dt, based on d^t is defined as Dt=diagd^t. Next, FWAdaBound generates a dynamic bound for learning rate at time t:
(8)ϖt=ClipαtDt,ϖlowtt,ϖupptt,where ϖlowt is the lower bound and ϖuppt is the upper bound. Therefore, Equation (5) clips the output of αt/Dt between the low bound and the upper bound. Finally, FWAdaBound updates the decision variable for time t+1 as follows:
(9)xt+1=xt+ϖt⨀wt−xt.Algorithm 1: FWAdaBound
Input: x1Parameter: x1∈F, and β1t∈0,1 where β11=β1, β2∈0,1. Moreover, α,η∈0,1.Initially set: m1=0 and v1=0.Output: xt+11:fort=1,2,3,⋯do2:t⟵t+13: Compute gradient of decision variables at timet:4:gt=∇ftxt5: Compute the first-order momentum at timet:6:ut=β1tut−1+1−β1tgt7: Generate a new sum function:8:Stx=η∑τ=1t‍uτ,x+∥x−x1∥29: Searchwt by one-dimensional linearly:10:wt=argminx∈F∇Stxt,x11: Compute the second-order momentum at timet:12:dt=β2dt−1+1−β2gt213: Select a bigger value for the second-order momentum:14:d^t=maxdt,dt−1 and Dt=diagd^t15: Compute the dynamic bound for learning rate at timet:16:ϖt=Clipαt/Dt,ϖlowt/t,ϖuppt/t17: Update the decision variables for timet+1:18:xt+1=xt+ϖtewt−xt19:end for20:returnxt+1Therefore, the design of the proposed algorithm is introduced completely. And we present some following common assumptions, which are the premises of the convergence of the algorithm.


## 4.2. Assumptions

Next, three assumptions are presented for the proposed algorithm as follows.Assumption 1.
The constraint setF is convex and compact. Moreover, the set F is bounded, i.e., x−y∞≤B∞ for all x,y∈F, where B∞>0.Assumption 2.
The cost functionft of FWAdaBound is convex and differentiable on F for all t∈1,⋯,T. In addition, all the cost functions, f1,⋯,ft, are Lipschitz functions with L constant, where L>0.Assumption 3.
The gradient of decision variablext is bounded for all t∈1,2,⋯,T over F, i.e., gt=∇ftxt≤G∞, where G∞>0.Assumption1 is one of the most basic assumptions of projection-free method, and almost all projection-free related articles use it, such as these classic articles [19, 20]. Assumption 2–3 are supposed commonly and reasonably for analyzing convergence of optimization algorithms such as these research works [14–16]. Next, we present the convergence analysis of the proposed algorithms based on Assumptions 1–3.In many research works [14–16], Assumptions 1–3 were supposed commonly and reasonably for analyzing convergence of proposed algorithms. Next, we present the convergence analysis of the proposed algorithms based on Assumptions 1–3.


## 5. Convergence Analysis

We first introduce the following definitions as the beginning of this section. Moreover, the introduced definitions are standard and common in convex optimization.(10)fx−fy≤Lx−y,Definition 4.
A functionf:F↦R is called L-Lipchitz if for any two points x,y∈F we havewhereL is a positive constant.Definition 5.
A functionf:F↦R is convex and differentiable if for all x,y∈F, we have
(11)fx−fy≤∇fxΤx−y.Definition 6.
Letf:F↦R be an arbitrary convex function. Then, the function f is also called μ-smooth if for any two points x,y∈F, we have
(12)fx−fy≥∇fxΤx−y−μ2y−x2,where μ>0.Definition 7.
Letf:F↦R be an arbitrary convex function. Then, the function f is δ-strongly convex if for all x,y∈F, we have
(13)fx−fy≤∇fxΤx−y−δ2y−x2,where δ>0.In addition, if a functionf is δ-strongly convex and let x∗=argminx∈Ffx, then we have
(14)fx−fx∗≥δ2x−x∗2.Moreover, from Definition6, we obtain the following equivalent relation:
(15)∇fx−∇fy≤μx−y,where x,y∈F.In order to simplify the process of convergence analysis, we define some intermediate variables. Letxt∗=argminx∈FStx for any t∈1,⋯,T. Moreover, we define S0x=∥x−x1∥2 at time t=0. In addition, we present the following relation for St:
(16)ztx=Stx−Stxt∗.Whenx=xt, for brevity, denoting zt=ztxt. Next, we present the following Lemma 8 to bound zt+1.Lemma 8.
If Assumptions1–3 are satisfied, and variables xt,ut,anddt are generated by Algorithm 1 for t∈1,⋯,T, and β1t=β1λt−1≤β1t−1≤β1, where λ∈0,1. In addition, suppose that 0≤ϖlowt≤ϖlowt+1, and 0≤ϖuppt+1≤ϖuppt, denoting B∞=ϖupp1 and C∞=ϖlow1. Then, we have
(17)zt+1≤1−B∞2tzt+nηG∞1−β1zt+1+B∞4t.Proof.
By Definition6, we know that Stx is a 2-smooth function. Moreover, using the definition of ztx (i.e., Equation (16)) and xt, we obtain the following relation:
(18)ztxt+1=Stxt+1−Stxt∗=Stxt+ϖtewt−xt−Stxt∗.From the bounds ofϖlowt and ϖuppt, we have the following:
(19)ztxt+1≤Stxt+ϖupp1tewt−xt−Stxt∗≤Stxt+B∞tewt−xt−Stxt∗.In addition, from the Definition7 and the strong-convexity of Stx, we obtain the following:
(20)ztxt+1≤Stxt−Stxt∗+B∞2twt−xt2+B∞2t∇Stxt,wt−xt.From the definition ofwt, we attain the following relation:
(21)∇Stxt,wt≤∇Stxt,xt∗.Moreover, from Equation (21), we have the following:
(22)∇Stxt,wt−xt≤∇Stxt,xt∗−xt.Plugging Equation (22) into Equation (20), we attain the following relation:
(23)ztxt+1≤Stxt−Stxt∗+B∞2twt−xt2+B∞2t∇Stxt,xt∗−xt.According to Definition5 and the convexity of Stx, we obtain the following relation:
(24)∇Stxt,xt∗−xt≤Stx∗−Stxt.Furthermore, plugging Equation (24) into Equation (23), we get the following relation:
(25)ztxt+1≤Stxt−Stxt∗+B∞2twt−xt2+B∞2tStx∗−Stxt≤1−B∞2tStxt−Stxt∗+B∞2twt−xt2.Next, we consider the termztxt+1 in Equation (25). By the definition of ztx, we first obtain the following relation:
(26)zt+1xt+1≤St+1xt+1−St+1xt+1∗.Then, transforming Equation (26), and we attain the following relation:
(27)zt+1xt+1≤Stxt+1−Stxt+1∗+St+1xt+1−Stxt+1+St+1xt+1∗−Stxt+1∗.In addition, due to the fact thatxt∗=argminx∈FStx, we have Stxt∗≤Stxt+1∗. For this reason, we obtain the following relation from Equation (27):
(28)zt+1xt+1≤Stxt+1−Stxt∗+St+1xt+1−Stxt+1+St+1xt+1∗−Stxt+1∗=ztxt+1+St+1xt+1−Stxt+1+St+1xt+1∗−Stxt+1∗.Next, we consider the termsSt+1xt+1−Stxt+1 and St+1xt+1∗−Stxt+1∗ in Equation (28). From the definition of Stx, we have the following relation:
(29)Stx−Stx=η∑τ=1t+1uτΤx+x−x12−η∑τ=1tuτΤx−x−x12=ηut+1Τx.Letx=xt+1 in Equation (29), we obtain
(30)Stxt+1−Stxt+1=ηut+1Τxt+1.In addition, letx=xt+1∗ in Equationss (29), we attain
(31)Stxt+1∗−Stxt+1∗=ηut+1Τxt+1∗.Combining Equations (28), (30), and (31), we have the following:
(32)zt+1xt+1≤ztxt+1+ηut+1Τxt+1+ηut+1Τxt+1∗=ztxt+1+ηut+1Τxt+1−xt+1∗≤ztxt+1+ηut+1Τxt+1−xt+1∗.The second inequality in Equation (32) follows from Cauchy-Schwarz inequality. Besides, plugging Equation (23) into Equation (32), we obtain
(33)zt+1xt+1≤1−B∞2tStxt−Stxt∗+B∞2twt−xt2+ηut+1Τxt+1−xt+1∗.Sinceztxt=Stxt−Stxt∗, we attain the following relation from Equation ((33))
(34)zt+1xt+1≤1−B∞2tztxt+B∞2twt−xt2+ηut+1Τxt+1−xt+1∗≤1−B∞2tzt+B∞2twt−xt2+ηut+1Τxt+1−xt+1∗.The second inequality in Equation (34) follows the definition of zt=ztxt.Before estimating the bound ofzt+1xt+1, we consider the bound of ∥ut+1∥. To this end, applying the recursive algorithm on ut, we have
(35)ut=∑j=1t1−β1j∏k=1t−jβ1t−k+1gj.From Assumption3 and Equation (35), we attain
(36)ut≤∑j=1t1−β1j∏k=1t−jβ1t−k+1∑σ=1ngj,σ≤nG∞∑j=1t1−β1j∏k=1t−jβ1t−k+1≤nG∞∑j=1t∏k=1t−jβ1t−k+1.In addition, becauseβ1t=β1λt−1, we obtain the following relation from Equation (36):
(37)ut≤nG∞∑j=1tβ1t−j≤nG∞1−β1.Plugging Equation (37) into Equation (34), we attain
(38)zt+1≤1−B∞2tzt+B∞2twt−xt2+nηG∞1−β1xt+1−xt+1∗.Sincewt=argminx∈F∇Stxt,x, we have wt∈F. Moreover, from Assumption 1, we have
(39)wt−xt≤B∞.Hence, combining Equations (38) and (40), we obtain
(40)zt+1≤1−B∞2tzt+nηG∞1−β1xt+1−xt+1∗+B∞4t.Applyingδ=2 on Definition 7, we attain that the function Stx is 2-strongly convex. In addition, from Equation (14), we have
(41)xt+1−xt+1∗≤St+1xt+1−St+1xt+1∗=zt+1.Moreover, substituting Equation (41) into Equation (40), and we can obtain the following:
(42)zt+1≤1−B∞2tzt+nηG∞1−β1zt+1+B∞4t.Therefore, the proof of Lemma8 is completed.Now, we get the iterative relations betweenzt and zt+1 from Lemma 8. In order to attain the final bound of zt, we should present the following two lemmas. First of all, we introduce the first lemma of the two lemmas.Lemma 9.
For allt=1,2,⋯, we can obtain the following relation:
(43)1t1−12t≤1t+1.Proof.
We first square both sides of Equation (43) and take the difference; then, we have the following relation:
(44)1t1−12t2−1t+12=1t−1tt+14t2−1t+1=1t−1tt+14t2−1t+1tt+1tt+1=t+1+t+1/4t−t+1/t−ttt+1=t+t+1/4−t+1tt2t+1=5t+1−4tt+1tt2t+1.Observing terms5t+1 and 4tt+1t, we can know that they all increase with t, and the latter grows faster than the former. Therefore, we can further attain the following relation from Equation (44):
(45)1t1−12t2−1t+12=5t+1−4tt+1tt2t+1≤0.In addition, combining Equations (44) and (43), we obtain the following relation:
(46)1t1−12t2≤1t+12.From Equation (46), we have the following relation:
(47)1t1−12t≤1t+1.Therefore, the proof of Lemma9 is completed.Next, we introduce the last lemma about the final bound ofzt as follows.Lemma 10.
If Assumptions1–3 are satisfied, and variables xt,ut,dt are generated by Algorithm 4.1 for t=1,⋯,T, and β1t=β1λt−1≤β1t−1≤β1, where λ∈0,1. In addition, suppose that 0≤ϖlowt≤ϖlowt+1, and 0≤ϖuppt+1≤ϖuppt. Denoting B∞=ϖupp1, and C∞=ϖlow1. Moreover, as the parameters n, η, and β1 are chosen such that nηG∞/1−β11−β1zt+1≤3B∞4−2B∞2/t by Algorithm 1, we then have
(48)zt+1≤4B∞2t+1.Proof.
By Equation (42), we have the following relation:
(49)zt+1≤1−B∞2tzt+4B∞4−2B∞2t.Now, we can use mathematical induction to get the bound ofzt. First, when t=1, from definition of zt, we attain
(50)z1≤S1x1−S1x1∗≤x1−x12−x1∗−x12=−x1∗−x12≤4B∞2.Therefore, the base of mathematical induction is true fort=1. Second, supposing that the mathematical induction is also true for t, and we present that it also true for t+1 as follows:
(51)zt+1≤1−B∞2t4B∞2t+4B∞4−2B∞2t≤4B∞2t−4B∞4t+4B∞4t−2B∞2t≤4B∞2t1−12t.Applying Lemma9 into Equation (51), we obtain
(52)zt+1≤4B∞2t+1.Therefore, the proof of Lemma10 is completed.Next, we present the following result to attain the bound ofRT.Theorem 11.
If the Assumptions1–3 are satisfied. Moreover, the sequences ut, wt, and dt are all generated by our proposed algorithm, which t∈1,2,⋯,T. Then, we obtain that
(53)RT≤8LB∞3T3/4+B∞2η1−β1β1T.Proof.
From Lemma10 and Equation (41), we have the following:
(54)xt−xt∗≤zt≤4B∞2t=2B∞t−1/4.Summing over Equation (54) for t=1,⋯,T, we attain the following relation:
(55)∑t=1Txt−xt∗≤∑t=1T2B∞t−1/4≤8B∞3T3/4.By Assumption2, we know that ft is a Lipschitz function. In addition, applying Definition 4, we have
(56)ftxt−ftxt∗≤Lxt−xt∗.In addition, combining Equation (55) and (56), we obtain
(57)∑t=1Tftxt−ftxt∗≤∑t=1TLxt−xt∗≤8LB∞3T3/4.Moreover, from the definition ofRT, we have
(58)RT=∑t=1Tftxt−ftx∗=∑t=1Tftxt−ftxt∗+∑t=1Tftxt∗−ftx∗.SinceS0x=∥x−x1∥2, we attain the following relation:
(59)STxt∗−STx∗≤η∑t=1Tutxt∗+xt∗−x12−η∑t=1Tutxt∗+x∗−x12≤η∑t=1Tutxt∗−x∗+xt∗−x12−x∗−x12≤0.Sincex∗,x1∈F, and by Assumption 1, we have x∗−x1≤B∞. Moreover, according to Equation (59), we obtain the following relation:
(60)∑t=1Tutxt∗−x∗≤1ηx∗−x12−xt∗−x12≤B∞2η.Then, combining Equations (35) and (60), we have the following relation:
(61)∑t=1Tutxt∗−x∗=∑t=1T∑j=1t1−β1j∏k=1t−jβ1t−k+1gj×xt∗−x∗≥∑t=1T∑j=1t1−β1jβ1tgjxt∗−x∗≥1−β1β1T∑t=1Tgtxt∗−x∗.Therefore, from Equations (60) and (61), we attain the following relation:
(62)∑t=1Tgtxt∗−x∗≤B∞2η1−β1β1T.Applying Definition5 and Equation (58), we obtain
(63)RT≤∑t=1Tftxt−ftxt∗+∑t=1Tgtxt∗−x∗.Finally, substituting Equations (57) and (62) into Equation (63), we have
(64)RT≤8LB∞3T3/4+B∞2η1−β1β1T.Therefore, the proof of Theorem11 is completed.From Theorem11, we get that limT⟶∞RT/T=0, which indicates that our proposed algorithm is convergent. In addition, by Equation (64), we know that the regret bound of our proposed algorithm is OT3/4.Remark 12.
This work is closed to the previous works [14–16]. Our regret bound OT3/4 is worse than the regret bound OT, which is obtained by [15, 16], but the number of iterations is increased within the same amount of time due to the lower computational cost per iteration. Hence, the overall convergent rate of the proposed algorithm is faster than the Adam-type algorithms such as Adam [14] and AdaBound [16].Next, we will validate the performance of our proposed algorithm by simulation experiments.


## 6. Experiments

Our algorithm is mainly used in the field of multimedia communication. Specifically, through modeling and analysis, it is proved that the algorithm can reduce the calculation and storage cost of text, voice, picture, and other information in multimedia information transmission.So, in this section, we, respectively, apply and compare the proposed algorithm on different dataset to validate the convergence and performance of the proposed algorithm. One application is the image classification on CIFAR-10 [21] dataset, and another one is the language modeling on the Penn Treebank dataset [22]. The experiments are executed on the equipment with 1080Ti GPU and CUDA 0.4.0, and written in Python 3.7 with Torch 1.0.1 framework. The details of experiment settings and results are described in the content below.


### 6.1. Experiment Settings

The CIFAR-10 is a famous and standard dataset for image classification, which consists of 60,00032×32 color images in 10 classes, and with 6,000 images per class. Moreover, the dataset has 50,000 training images and 10,000 test images, respectively. We use deep models, ResNet-34 and DenseNet-121, to finish the classification tasks on CIFAR-10. The model ResNet-34, a popular model in deep learning, is a deep residual networks with 34 layers. In addition, DenseNet-121 is a dense convolutional network with 121 layers, in which each layer accepts all preceding layers as its additional input.The Penn Treebank is a popular and classical dataset for language modeling. The corpus of this dataset comes from the Wall Street Journal. Moreover, this dataset contains 2,499 articles with a total of 1M words. In this experiments, we use three LSTM models, including 1-layer, 2-layer and 3-layer, to train this dataset.In our experiments, we compare our proposed algorithm, FWAdaBound, with classical and latest proposed algorithms including OGD, Adam [14], and AdaBound [16]. Furthermore, the setting of parameters of all algorithms are shown as follows.
(i)
OGD, the initial step sizeα is chosen from(65)1e−2,5e−3,1e−3,5e−4,1e−4(ii)
Adam [14], with β1=0.9,β2=0.999,αt=α/t, in which the initial step size α is chosen from(66)1e−2,5e−3,1e−3,5e−4,1e−4Moreover, we use for the perturbation valueε=1e−8.
(iii)
AdaBound [16], with β1=0.9,β2=0.999,αt=α/t, in which the initial step size α is chosen from(67)1e−2,5e−3,1e−3,5e−4,1e−4Moreover,ε=1e−8.
(iv)
FWAdaBound, our proposed algorithm, we directly applied the default hyperparameters of AdaBound (a learning rate of 0.001,β1=0.9, β2=0.999, and ε=1e−8)Next, we show the results of our experiments on CIFAR-10 and present the related analysis of the experimental results.


### 6.2. Experiment Results and Analysis

#### 6.2.1. Image Classification

In the first experiment, we run the algorithms on CIFAR-10 for 200 epochs and measure the relationship between running time and average loss. It can be concluded from the first experiment that with the same epoch number, FWAdaBound spends the shortest time to complete the iterative task. It also confirms that FWAdaBound takes the least computation cost among all the experimental algorithms. The reason is that FWAdaBound uses linear search instead of the high-order projection steps in Adam and AdaBound. Moreover, Figure1 shows the results for each algorithm on both ResNet-34 and DenseNet-121. In the part (a) of Figure 1, the average loss of our proposed algorithm FWAdaBound reaches the expected stable value in the shortest time in model ResNet-34. Similarly, in part (b) of Figure 1, FWAdaBound also takes the least time to reduce the average loss in model DenseNet-121. This suggests that with the same number of epochs, FWAdaBound spends the least time to complete the iteration task. Moreover, this validates that FWAdaBound takes the least computation cost among all the experimental algorithms. The reason is that FWAdaBound uses linear search instead of the high-order projection steps in Adam and AdaBound. Therefore, FWAdaBound can iterates much faster than Adam and AdaBound in each epoch.Figure 1
Comparison of the relationship between the average loss and the running time of each algorithm.
(a)
news20(b)
aloiThen, we execute the second experiment to verify the generalization ability of training accuracy. The results of the second experiment are shown in Figure2. This figure shows that the training accuracy of FWAdaBound rises rapidly in the early stage of training and finally reaches the same height as AdaBound, which validates the generalization ability of training accuracy of FWAdaBound is better. Moreover, the figure also shows that the training accuracy of FWAdaBound is higher than that of Adam and AdaBound at each moment, which further indicates that the iteration cost of FWAdaBound is the lowest.Figure 2
Comparison of the relationship between the training accuracy and the running time of each algorithm.
(a)
news20(b)
aloiFinally, the last experiment verify the generalization ability of test accuracy of our proposed algorithm. And the results of this experiment are presented in Figure3. Likewise, the test accuracy of FWAdaBound performs well in the early stage of iteration process and achieves the same performance as AdaBound in the final stage. Therefore, FWAdaBound also has a good generalization ability on test accuracy. In general, the generalization ability of FWAdaBound is the same as that of AdaBound but takes much less computation cost than AdaBound and Adam.Figure 3
Comparison of the relationship between the test accuracy and the running time of each algorithm.
(a)
news20(b)
aloi


#### 6.2.2. Language Modeling

In this group of experiments, we implement all the algorithms in 1-, 2-, and 3-layer LSTM models on the Penn Treebank dataset. The results of the experiments are shown in Figure4 which presents the relationship between the perplexity and the running time of each algorithm. Note that the lower perplexity the better.Figure 4
Comparison of the relationship between the perplexity and the running time of each algorithm. Lower is better.
(a)
news20 (4 nodes)(b)
news20 (64 nodes)(c)
news20 (128 nodes)(d)
aloi (4 nodes)(e)
aloi (64 nodes)(f)
aloi (128 nodes)The experiment results of 1-layer LSTM show that FWAdaBound takes the least time to minimize the perplexity. On 1-layer LSTM model, FWAdaBound performs best in all algorithms, and Adam performs better than AdaBound.In addition, in the experiments executed on 2-layer LSTM model, FWAdaBound has the quickest convergence rate among all the algorithms. Moreover, FWAdaBound takes 16.67% and 17.65% less running time than Adam and AdaBound, respectively. In this experiment, AdaBound performs better than Adam on the perplexity.Finally, all the three algorithms are executed on the 3-layer LSTM model. The results show that FWAdaBound takes the least time to minimize the perplexity on Penn Treebank. In addition, FWAdaBound takes 11.83% and 14.05% less time than Adam and AdaBound, respectively. Moreover, AdaBound also performs better than Adam on the perplexity in this experiments.


## 6.1. Experiment Settings

The CIFAR-10 is a famous and standard dataset for image classification, which consists of 60,00032×32 color images in 10 classes, and with 6,000 images per class. Moreover, the dataset has 50,000 training images and 10,000 test images, respectively. We use deep models, ResNet-34 and DenseNet-121, to finish the classification tasks on CIFAR-10. The model ResNet-34, a popular model in deep learning, is a deep residual networks with 34 layers. In addition, DenseNet-121 is a dense convolutional network with 121 layers, in which each layer accepts all preceding layers as its additional input.The Penn Treebank is a popular and classical dataset for language modeling. The corpus of this dataset comes from the Wall Street Journal. Moreover, this dataset contains 2,499 articles with a total of 1M words. In this experiments, we use three LSTM models, including 1-layer, 2-layer and 3-layer, to train this dataset.In our experiments, we compare our proposed algorithm, FWAdaBound, with classical and latest proposed algorithms including OGD, Adam [14], and AdaBound [16]. Furthermore, the setting of parameters of all algorithms are shown as follows.
(i)
OGD, the initial step sizeα is chosen from(65)1e−2,5e−3,1e−3,5e−4,1e−4(ii)
Adam [14], with β1=0.9,β2=0.999,αt=α/t, in which the initial step size α is chosen from(66)1e−2,5e−3,1e−3,5e−4,1e−4Moreover, we use for the perturbation valueε=1e−8.
(iii)
AdaBound [16], with β1=0.9,β2=0.999,αt=α/t, in which the initial step size α is chosen from(67)1e−2,5e−3,1e−3,5e−4,1e−4Moreover,ε=1e−8.
(iv)
FWAdaBound, our proposed algorithm, we directly applied the default hyperparameters of AdaBound (a learning rate of 0.001,β1=0.9, β2=0.999, and ε=1e−8)Next, we show the results of our experiments on CIFAR-10 and present the related analysis of the experimental results.


## 6.2. Experiment Results and Analysis

### 6.2.1. Image Classification

In the first experiment, we run the algorithms on CIFAR-10 for 200 epochs and measure the relationship between running time and average loss. It can be concluded from the first experiment that with the same epoch number, FWAdaBound spends the shortest time to complete the iterative task. It also confirms that FWAdaBound takes the least computation cost among all the experimental algorithms. The reason is that FWAdaBound uses linear search instead of the high-order projection steps in Adam and AdaBound. Moreover, Figure1 shows the results for each algorithm on both ResNet-34 and DenseNet-121. In the part (a) of Figure 1, the average loss of our proposed algorithm FWAdaBound reaches the expected stable value in the shortest time in model ResNet-34. Similarly, in part (b) of Figure 1, FWAdaBound also takes the least time to reduce the average loss in model DenseNet-121. This suggests that with the same number of epochs, FWAdaBound spends the least time to complete the iteration task. Moreover, this validates that FWAdaBound takes the least computation cost among all the experimental algorithms. The reason is that FWAdaBound uses linear search instead of the high-order projection steps in Adam and AdaBound. Therefore, FWAdaBound can iterates much faster than Adam and AdaBound in each epoch.Figure 1
Comparison of the relationship between the average loss and the running time of each algorithm.
(a)
news20(b)
aloiThen, we execute the second experiment to verify the generalization ability of training accuracy. The results of the second experiment are shown in Figure2. This figure shows that the training accuracy of FWAdaBound rises rapidly in the early stage of training and finally reaches the same height as AdaBound, which validates the generalization ability of training accuracy of FWAdaBound is better. Moreover, the figure also shows that the training accuracy of FWAdaBound is higher than that of Adam and AdaBound at each moment, which further indicates that the iteration cost of FWAdaBound is the lowest.Figure 2
Comparison of the relationship between the training accuracy and the running time of each algorithm.
(a)
news20(b)
aloiFinally, the last experiment verify the generalization ability of test accuracy of our proposed algorithm. And the results of this experiment are presented in Figure3. Likewise, the test accuracy of FWAdaBound performs well in the early stage of iteration process and achieves the same performance as AdaBound in the final stage. Therefore, FWAdaBound also has a good generalization ability on test accuracy. In general, the generalization ability of FWAdaBound is the same as that of AdaBound but takes much less computation cost than AdaBound and Adam.Figure 3
Comparison of the relationship between the test accuracy and the running time of each algorithm.
(a)
news20(b)
aloi


### 6.2.2. Language Modeling

In this group of experiments, we implement all the algorithms in 1-, 2-, and 3-layer LSTM models on the Penn Treebank dataset. The results of the experiments are shown in Figure4 which presents the relationship between the perplexity and the running time of each algorithm. Note that the lower perplexity the better.Figure 4
Comparison of the relationship between the perplexity and the running time of each algorithm. Lower is better.
(a)
news20 (4 nodes)(b)
news20 (64 nodes)(c)
news20 (128 nodes)(d)
aloi (4 nodes)(e)
aloi (64 nodes)(f)
aloi (128 nodes)The experiment results of 1-layer LSTM show that FWAdaBound takes the least time to minimize the perplexity. On 1-layer LSTM model, FWAdaBound performs best in all algorithms, and Adam performs better than AdaBound.In addition, in the experiments executed on 2-layer LSTM model, FWAdaBound has the quickest convergence rate among all the algorithms. Moreover, FWAdaBound takes 16.67% and 17.65% less running time than Adam and AdaBound, respectively. In this experiment, AdaBound performs better than Adam on the perplexity.Finally, all the three algorithms are executed on the 3-layer LSTM model. The results show that FWAdaBound takes the least time to minimize the perplexity on Penn Treebank. In addition, FWAdaBound takes 11.83% and 14.05% less time than Adam and AdaBound, respectively. Moreover, AdaBound also performs better than Adam on the perplexity in this experiments.


## 6.2.1. Image Classification

In the first experiment, we run the algorithms on CIFAR-10 for 200 epochs and measure the relationship between running time and average loss. It can be concluded from the first experiment that with the same epoch number, FWAdaBound spends the shortest time to complete the iterative task. It also confirms that FWAdaBound takes the least computation cost among all the experimental algorithms. The reason is that FWAdaBound uses linear search instead of the high-order projection steps in Adam and AdaBound. Moreover, Figure1 shows the results for each algorithm on both ResNet-34 and DenseNet-121. In the part (a) of Figure 1, the average loss of our proposed algorithm FWAdaBound reaches the expected stable value in the shortest time in model ResNet-34. Similarly, in part (b) of Figure 1, FWAdaBound also takes the least time to reduce the average loss in model DenseNet-121. This suggests that with the same number of epochs, FWAdaBound spends the least time to complete the iteration task. Moreover, this validates that FWAdaBound takes the least computation cost among all the experimental algorithms. The reason is that FWAdaBound uses linear search instead of the high-order projection steps in Adam and AdaBound. Therefore, FWAdaBound can iterates much faster than Adam and AdaBound in each epoch.Figure 1
Comparison of the relationship between the average loss and the running time of each algorithm.
(a)
news20(b)
aloiThen, we execute the second experiment to verify the generalization ability of training accuracy. The results of the second experiment are shown in Figure2. This figure shows that the training accuracy of FWAdaBound rises rapidly in the early stage of training and finally reaches the same height as AdaBound, which validates the generalization ability of training accuracy of FWAdaBound is better. Moreover, the figure also shows that the training accuracy of FWAdaBound is higher than that of Adam and AdaBound at each moment, which further indicates that the iteration cost of FWAdaBound is the lowest.Figure 2
Comparison of the relationship between the training accuracy and the running time of each algorithm.
(a)
news20(b)
aloiFinally, the last experiment verify the generalization ability of test accuracy of our proposed algorithm. And the results of this experiment are presented in Figure3. Likewise, the test accuracy of FWAdaBound performs well in the early stage of iteration process and achieves the same performance as AdaBound in the final stage. Therefore, FWAdaBound also has a good generalization ability on test accuracy. In general, the generalization ability of FWAdaBound is the same as that of AdaBound but takes much less computation cost than AdaBound and Adam.Figure 3
Comparison of the relationship between the test accuracy and the running time of each algorithm.
(a)
news20(b)
aloi


## 6.2.2. Language Modeling

In this group of experiments, we implement all the algorithms in 1-, 2-, and 3-layer LSTM models on the Penn Treebank dataset. The results of the experiments are shown in Figure4 which presents the relationship between the perplexity and the running time of each algorithm. Note that the lower perplexity the better.Figure 4
Comparison of the relationship between the perplexity and the running time of each algorithm. Lower is better.
(a)
news20 (4 nodes)(b)
news20 (64 nodes)(c)
news20 (128 nodes)(d)
aloi (4 nodes)(e)
aloi (64 nodes)(f)
aloi (128 nodes)The experiment results of 1-layer LSTM show that FWAdaBound takes the least time to minimize the perplexity. On 1-layer LSTM model, FWAdaBound performs best in all algorithms, and Adam performs better than AdaBound.In addition, in the experiments executed on 2-layer LSTM model, FWAdaBound has the quickest convergence rate among all the algorithms. Moreover, FWAdaBound takes 16.67% and 17.65% less running time than Adam and AdaBound, respectively. In this experiment, AdaBound performs better than Adam on the perplexity.Finally, all the three algorithms are executed on the 3-layer LSTM model. The results show that FWAdaBound takes the least time to minimize the perplexity on Penn Treebank. In addition, FWAdaBound takes 11.83% and 14.05% less time than Adam and AdaBound, respectively. Moreover, AdaBound also performs better than Adam on the perplexity in this experiments.


## 7. Conclusion

In this paper, we proposed a Frank-Wolfe adaptive momentum online algorithm named FWAdaBound, which uses the Frank-Wolfe technique to avoid the projection operation. Moreover, our convergence analysis showed that the regret bound of FWAdaBound achieves toOT3/4, where T is a time horizon. In order to validate the performance of FWAdaBound in applications, we execute three groups of experiments for image classification and language modeling. The results show that FWAdaBound has good performance in the generalization ability of training and test accuracy.



---

*Source: 8533687-2022-04-20.xml*