DEAM: Adaptive Momentum with Discriminative Weight for Stochastic Optimization
Jiyang Bai Yuxiang Ren Jiawei Zhang
cs.LG math.OC stat.ML

	


	



DEAM: Adaptive Momentum with Discriminative Weight for Stochastic Optimization
    
Jiyang BaiYuxiang RenJiawei Zhang
IFM Lab, Florida State University

{jiyang, yuxiang, jiawei}@ifmlab.org	

    April 2019
================================================================================================================




Optimization algorithms with momentum, e.g., (), have been widely used for building deep learning models due to the faster convergence rates compared with stochastic gradient descent (SGD). Momentum helps accelerate SGD in the relevant directions in parameter updating, which can minify the oscillations of parameters update route. However, there exist errors in some update steps in optimization algorithms with momentum like . The fixed momentum weight (e.g., β_1 in ) will propagate errors in momentum computing.



In this paper, we introduce a novel optimization algorithm, namely Discriminative wEight on Adaptive Momentum (). Instead of assigning the momentum term weight with a fixed hyperparameter,  proposes to compute the momentum weight automatically based on the discriminative angle. 
In this way,  involves fewer hyperparameters.  also contains a novel backtrack term, which restricts redundant updates when the correction of the last step is needed. 
Extensive experiments demonstrate that  can achieve a faster convergence rate than the existing optimization algorithms in training the deep learning models of both convex and non-convex situations.








§ INTRODUCTION

Deep learning methods can achieve outstanding performance in multiple fields including computer vision <cit.>, natural language processing <cit.>, speech and audio processing <cit.>, and graph analysis <cit.>. Training deep learning models involves an optimization process to find the parameters in the model that minimize the loss function. At the same time, the number of parameters commonly used in deep learning methods can be very huge.

Therefore, optimization algorithms are critical for deep learning methods: not only the model performance, but also training efficiency are greatly affected. 
In order to cope with the high computational complexity of training deep learning methods, stochastic gradient descent (SGD) <cit.> is utilized to update parameters based on the gradient of each training sample instead. The idea of momentum <cit.>, inspired by Newton's first law of motion, is used to handle the oscillations of SGD. SGD with momentum <cit.> achieves the faster convergence rate and better optimization results compared with the original SGD. In gradient descent based optimization, training efficiency is also greatly affected by the learning rate. 
AdaGrad <cit.> is the first optimization algorithm with adaptive learning rates, which makes use of the learning rate decay. AdaDelta <cit.> subsequently improves AdaGrad to avoid the extremely small learning rates.  <cit.> involves both adaptive learning <cit.> and momentum <cit.> and utilizes the exponential decay rate β_1 (momentum weight) to accelerate the convergence in the relevant directions and dampen oscillations. However, the decay rate β_1 of the first-order momentum m_t in  is a fixed number, and the selection of the hyperparameter β_1 may affect the performance of  greatly. Commonly, β_1 = 0.9 is the most widely used parameter as introduced in <cit.>, but there is still no theoretical evidence proving its advantages. 


During the optimization process, it is common that there exist errors in some update steps. These errors can be caused by the inappropriate momentum calculation, and then lead to slower convergence or oscillations. For each parameter updates, using the fixed momentum weight fails to take the different influence of the current gradient into consideration, which will render errors in momentum computing. For example, when there exist parts of opposite eigen components <cit.> between the continuous two parameter updates (we regard this situation as an error), the current gradient should be assigned a larger weight to correct the momentum in the last update, instead of being placed with a fixed influence. 
We will illustrate this problem through cases in Section <ref> where  with a fixed weight β_1 cannot handle some simple but intuitive convex optimization problems. Based on this situation, we need to control the influence of momentum by an adaptive weight. What's more, designing hyperparameter-free optimization algorithms has been a very important research problem in recent years, controlling the number of hyperparameters will not only stabilize the performance of the optimization algorithm, but also release the workload of hyperparameters tuning. 

In this paper, we introduce a novel optimization algorithm, namely  (Discriminative wEight on Adaptive Momentum) to deal with the aforementioned problems.  proposes an adaptive momentum weight β_1,t, which will be learned and updated in each training iteration automatically. 
Besides,  employs a novel backtrack term d_t, which will restrict redundant updates when  decides that the correction of the previous step is needed.
We also provide the theoretic analyses about the adaptive momentum weight along with extensive experiments. Based on them, we verify that the adaptive momentum term weight β_1,t and the operation of backtrack term d_t can be crucial for the performance of the learning algorithms.

Here, we summarize the detailed learning mechanism of  as follows:

	
  *  computes adaptive momentum weight β_1,t based on the “discriminative angle" θ between the historical momentum and the newly calculated gradient.
	
  *  introduces a novel backtrack term, i.e., d_t, which is proposed to correct the redundant update of the previous training epoch if it is necessary. 
	The calculation of d_t is also based on the discriminative angle θ.
	
  *  involves fewer hyperparameters than the  during the training process, which can decrease the workload of hyperparameter tuning.


Detailed information about the learning mechanism and the concepts mentioned above will be described in the following sections. This paper will be organized as follows. In Section 2, we will cover some related works about widely used optimization algorithms. In Section 3, we will analyze more detail of our proposed algorithm, whose theoretic convergence rate will also be studied. Extensive experiments will be exhibited in Section 4. Finally, we will give a conclusion of this paper in Section 5.



§ RELATED WORKS
 
Stochastic Gradient Descent: Stochastic gradient descent (SGD) <cit.> performs parameter updating for each training example and label. The advantages of SGD include fast converging speed compared with gradient descent and preventing redundancy <cit.>. <cit.> use the variance reduction methods to accelerate the training process of SGD.

Adaptive Learning Rates: To overcome the problems brought by the unified learning rate, some variant algorithms applying adaptive learning rate <cit.> have been proposed, such as AdaGrad <cit.>,  <cit.>, RMSProp <cit.>,  <cit.> and recent ESGD <cit.>, AdaBound <cit.>.  adopts different learning rates to different variables. One drawback of AdaGrad is that with the increasing of iteration number t, the adaptive term may inflate continuously, which leads to a very slow convergence rate in the later stage of the training process.  can solve this problem by using the moving average of historical gradients.

Momentum: Momentum <cit.> is a method that helps accelerate SGD in the relevant direction and prevent oscillations on the descent route. The momentum accelerates updates for dimensions whose gradients are in the same direction as historical gradients, and decelerates updates for dimensions whose gradients are the opposite. Momentum is also applied to Nesterov accelerated gradient (NAG) <cit.>, which provides the momentum term with the estimating next position capability. Instead of using the current location to calculate the gradient, NAG first approximates the next position of the variables, then uses the approximated future position to compute the gradient.








 <cit.> is proposed based on momentum and adaptive learning rates for different variables.  records the first-order momentum and the second-order momentum of the gradients using the moving average, and further computes the bias-corrected version of them. Based on , Keskar et al. <cit.> proposes to switch from  to SGD during the training process.  <cit.> is a modified version of , which redefines second-order momentum by a maximum function. 









§ PROPOSED ALGORITHM
 
Our proposed algorithm  is presented in Algorithm <ref>. In the algorithm, f_1, f_2,…, f_T is a sequence of loss functions computed with the training mini-batches in different iterations (or epochs). 



 introduces two new terms in the learning process: (1) the adaptive momentum weight β_1,t
, and (2) the“backtrack term" d_t. In the t_th training iteration, both β_1,t and d_t are calculated based on the “discriminative angle" θ, which is the angle between previous m_t-1/√(v̂_t-1) and current gradient g_t (since essentially both m_t-1/√(v̂_t-1) and g_t are vectors, there exists an angle between them). Here, m is the first-order momentum that records the exponential moving average of historical gradients; v is the exponential moving average of the squared gradients, which is called the second-order momentum. In the following parts of this paper, we will denote m_t-1/√(v̂_t-1) as the “update volume” in the (t-1)_th iteration. 
Formally, β_1,t determines the weights of previous first-order momentum m_t-1 and current gradient g_t when calculation the present m_t. Meanwhile, the backtrack term d_t represents the returning step of the previous update on parameters. We can notice that in each iteration, after the θ has been calculated, the β_1,t and d_t are directly obtained according to the θ. 
In this way, we can calculate appropriate β_1,t as the discriminative angle changes. The d_t term balances between the historical update term Δ_t-1 (defiend in Algorithm <ref>) and the current update volume m_t /√(v̂_t) when computing Δ_t. In the proposed , β_1,t and d_t terms can collaborate with each other and achieve faster convergence.




 §.§ Adaptive Momentum Weight β_1,t





  §.§.§ Motivation

In the  <cit.> paper, (the first-order) momentum's weight (i.e., β_1) is a pre-specified fixed value, and commonly β_1 = 0.9. It has been used in many applications and the performance can usually meet the expectations. However, this setting is not applicable in some situations. For example, for the case 

    f(x,y) = x^2 + 4y^2 ,

where x and y are two variables, it is obvious that f is a convex function. If f(x,y) is the objective function to optimize, we try to use  to find its global optima.







Let's assume ADAM starts the variable search from (-4,-1) (i.e., the initial variable vector is w_0 = (-4,-1)^⊤) and the initial learning rate is η_1 = 1. Different choices of β_1 will lead to very different performance of ADAM. For instance, in Figure <ref>, we illustrate the update routes of ADAM with β_1 = 0.9 and β_1 = 0.0 as the blue and red lines, respectively. In Figure <ref>, the ellipse lines are the contour lines of f(x,y), and points on the same line share the same function value. We can observe that after the first updating, both of the two approaches will update variables to (-3, 0) point (i.e., the updated variable vector will be w_1 = (-3, 0)^⊤). In the second step, since the current gradient g_2 = (-6, 0)^⊤, the  with β_1 = 0.0 will update variables in the (1, 0) direction. Meanwhile, for the  with β_1 = 0.9, its m_2 is computed by integrating m_1 and g_2 together (whose weights are β_1 and 1-β_1, respectively). Therefore the updating direction of it will be more inclined to the previous direction instead. Compared with ADAM with β_1 = 0.0, the ADAM with β_1 = 0.9 takes much more iterations until converging.

From the analysis above, we can observe that, a careful tuning and updating of β_1 in the learning process can be crucial for the performance of . However, by this context so far, there still exist no effective approaches for guiding the parameter tuning yet. To deal with this problem,  introduces the concept of discriminative angle θ for computing β_1 automatically as follows.



  §.§.§ Mechanism

The momentum weight β_1 will be updated in each iteration in , and we can denote its value computed in the t_th iteration as β_1,t formally.


Essentially, in the t_th iteration of the training process, both the previous update volume 
and g_t are vectors (or directions), and these directions directly decide the updating process. Thus we try to extract their relation with the help of angle, and subsequently determine the weight β_1,t (or 1 - β_1,t) by the angle. 

In Algorithm <ref>, the discriminative angle θ in the t_th iteration is calculated by

	
    θ = ⟨ -m_t-1/√(v̂_t-1), -g_t ⟩ = ⟨m_t-1/√(v̂_t-1), g_t⟩


Here, the operator ⟨·, ·⟩ denotes the angle between two vectors. This expression is easy to understand, since the -m_t-1 / √(v̂_t-1) can represent the updating direction of (t-1)_th iteration in , meanwhile -g_t is the reverse of the present gradient. So we can simplify it as θ = <m_t-1/√(v̂_t-1), g_t>. If θ is close to zero (denoted by θ→ 0^∘), the m_t-1 / √(v̂_t-1) (previous update volume) and g_t are almost in the same direction, and the weights for them will not be very important. Meanwhile, if θ approaches 180^∘ (denoted by θ→ 180^∘), the previous update volume and g_t will be in totally reverse directions. This means in the current step, the previous momentum term is already in a wrong direction. Therefore, to rectify this error of the last momentum,  proposes to assign the current gradient's weight (i.e., β_1,t in our paper) with a larger value instead. As the β_1,t varies when θ changes from 0^∘ to 180^∘, we intend to define β_1,t with the following equation:

	
    β_1,t =  sin K + ϵ   
    
    	1 / K


where K = 10(2+π)/2π and ϵ is a very small value (e.g., ϵ = 0.001). 

In the equation above, the threshold of the piecewise function is θ = π/2, because sinθ comes to the maximum at this point and goes down when θ > π/2. If π/2≤θ≤π, which is exactly the situation θ→ 180^∘ we discussed above, we intend to keep β_1,t in a relatively large value. The reason we rescale sinθ by 1/K is that directly applying β_1,t= sinθ will overweight g_t, which may cause fluctuations on the update routes. The value of K is determined by:

	
    K = 10(∫_0^π/2sinθ dθ + ∫_π/2^π 1 dθ) = 10(2+π)/2π


In the equation above, assume θ is randomly distributed on [0, π], in this calculation we can get 

	
    𝔼[β_1,t] = 1/π∫_0^πβ_1,t(θ) dθ = 0.1


In other words, the expectation of β_1,t (i.e., 𝔼(β_1,t)) will be identical to the β_1 used in  <cit.>. 
After obtaining β_1,t, it will be applied to calculating m_t as shown in Algorithm <ref>. In this way, we have achieved momentum with adaptive weights, and this weight is automatically computed during the training process, fewer hyperparameters will be involved.




 §.§ Backtrack Term d_t

To further speed up the convergence rate, we employ a novel backtrack mechanism for . As a mechanism computed based on the discriminative angle θ, the backtrack term allows  to eliminate redundant update in each iteration.

Besides, according to our following analysis, the backtrack term d_t virtually collaborates with the β_1,t term to further accelerate the convergence of the training process. 




  §.§.§ Motivation

When optimizer (e.g., ) updates variables of the loss function (e.g., f(x, y)), some update routes will look like the black arrow lines shown in Figure <ref>, especially when the discriminative angle θ is larger than 90^∘. We call this phenomenon the "zig-zag" route. In Figure <ref>, it shows the update routes of a 2-dimension function. Each black arrow line in the figure represents the variables' update in each epoch; the red dashed line is the direction of the update routes; the θ is the discriminative angle. If θ≥ 90^∘, the "zig-zag" phenomenon will appear severely, which may lead to slower convergence speed. The main reason is when θ≥ 90^∘, if we map two neighboring update directions onto the coordinate axes, there will be at least one axis of the directions being opposite. This situation is shown in Figure <ref>. For the example of a function with 2-dimension variables, the update volume m_1/√(v_1) can be decomposed into (x_1, y_1)^⊤ in Figure <ref>, and the same with m_2/√(v_2). We can notice that y_1 and y_2 are in the opposite directions, so the first and second steps practically have inverse updates subject to the y axis. We attribute this situation to the over update (or redundant update) of the first step. Therefore the backtrack term d_t is proposed to restrict this situation.



  §.§.§ Mechanism

Since the redundant update situation is caused by over updating of the previous iteration, simply we intend to deal with it through a backward step. Meanwhile, during the updating process of variables, not every step will suffer from the redundant update: if θ→ 0^∘, the updating process becomes smooth, not like the situation shown in Figure <ref>. Besides, from the analysis above we conclude that if θ≥ 90^∘, there will be at least one dimension involves the redundant update. Thus, in the t_th iteration we quantify d_t as the following equation:

	
    d_t = min{0.5cosθ, 0}


and we rewrite the updating term with backtrack in  as

	
    Δ_t = d_t·Δ_t-1 - η_t·m_t/√(v̂_t)


where θ is the discriminative angle and Δ_t is the updating term in Algorithm <ref>. By designing d_t in this way, when θ→ 0^∘, d_t = 0 and there is no backward step, the updating term Δ_t = -η_t·m_t/√(v̂_t) is similar to ; when θ→ 180^∘, d_t = 0.5cosθ and comes to the maximum value when θ = 180^∘. The reason that cosθ is rescaled by 0.5 is that: in Figure <ref>, w_t-1 and w_t are the variables updated by  without d_t term in the (t-1)_th and t_th iterations respectively. If the backtrack mechanism is implemented, in the (t+1)_th iteration, since θ = 180^∘, firstly d_t = 0.5cosθ→ -0.5 makes the backtrack to the w'_t point (the middle point of w_t-1 and w_t). Thus, this backtrack step allows the variable to further approach the optima.

By implementing the backtrack term d_t,  can combine it with the adaptive momentum weight β_1,t to achieve the collaborating of them. For the situation of large discriminative angle (θ > 90^∘), both β_1,t and d_t in the current step can make corrections to the last update. Since when θ > 90^∘, the last update is in conflict direction compared with the current gradient, and  β_1,t will increase to allocate a large weight for the present gradient, which subsequently corrects the previous step. Meanwhile, the d_t will also conduct a backward step of to further rectify the last update.























 §.§ Theoretical Analysis

In this part, we give the detailed analysis on the convergence of our   algorithm. According to <cit.>, given an arbitrary sequence of convex objective functions f_1(w), f_2(w),…, f_T(w), we intend to evaluate our algorithm using the regret function, which is denoted as:

	
    R(T) = ∑_t=1^T[f_t(w_t) - f_t(w^*)]


where w^* is the globally optimal point. In the following Theorem <ref>, we will show that the above regret function is bounded. Before proving the Theorem <ref>, there are some definitions and lemmas as the pre-requisites.
 
	
	If a function f: ℝ^d →ℝ is convex, then ∀ x, y∈ℝ^d, ∀ϕ∈[0,1], we have
	
    f(ϕ x + (1-ϕ)y)≤ϕ f(x) + (1-ϕ)f(y)



	If a function f: ℝ^d→ℝ is convex, then ∀ x, y∈ℝ^d we have
	
    f(y)≥ f(x) + ∇ f(x)^⊤ (y-x)




	Assume that the function f_t has bounded gradients, ∇ f_t(w)_∞≤ G_∞. Let  m_t, i represents the i_th element of m_t in , then the m_t, i is bounded by
	
    m_t,i≤(1-ϵ_0)G_∞/K(1-λ)



	Let g_t = ∇ f_t(w).
	According to the definition of m_t,i in our algorithm,
	
    m_t,i   = ∑_j=1^tβ_1,j∏_l=1^t-j(1-β_1,t-l+1)g_j,i
       ≤G_∞/K∑_j=1^t∏_l=1^t-j(1-ϵ)
    		≤G_∞/K∑_j=1^t(1-ϵ_0)λ^t-j≤(1-ϵ_0)G_∞/K(1-λ)

	
	where K and ϵ are the terms in Algorithm <ref>.

For the following proof, g_t := ∇ f_t(w_t) and g_t, i will represent the i_th element of g_t∈ℝ^d, and g_1:t, i = [g_1,i,g_2,i,… ,g_t,i].

	Assume {f_t}_t=1^T have bounded gradients ∇ f_t(w)_∞≤ G_∞ for all w∈ℝ^d, all variables are bounded by w_p - w_q_2≤ D and w_p - w_q_∞≤ D_∞, ∀ p,q ∈{1,2,…,T}, η_t = η/√(t), γ_1 = (1-ϵ_0) / √(β_2) and satisfies γ_1<1, ϵ = 1-(1-ϵ_0)λ^t-1, λ∈(0,1). Our proposed algorithm can achieve the following bound on regret:
	
    R(t)   ≤D^2/ϵ_0η∑_i=1^d√(Tv̂_T,i)
    		+ (1-ϵ_0)^2G_∞ D_∞ d/K(1-λ)^2ϵ_0
       + η√(1+log T)/2ϵ^2_0(1-γ_1)√(1-β_2)∑_i=1^dg_1:T,i_2

	
	


	According to Definition <ref>, for ∀ t ∈{1,2,…,T}, we have
	
    f_t(w_t) - f_t(w^*) ≤∇ f_t(w_t)^⊤ (w_t - w^*)
    		
    		= ∑_i=1^dg_t, i(w_t,i - w_i^*)

	
	
	
	From the definition of Δ_t in the updating rule of , we know it is equal to multiplying the learning rate η_t in some iterations by a number in [0.5, 1], which means w_t+1 = w_t - η̂_t·m_t/√(v̂_t);η̂_t = μ_t·η_t, where μ_t∈ [0.5, 1]. 
	If we first focus on the i_th element of w_t, we can get
	
    (w_t+1,i - w^*_i)^2= (w_t,i - w^*_i - η̂_t·m_t/√(v̂_t))^2 =(w_t,i - w^*_i)^2 
    
    		
    		-    2η̂_t((1 - β_1,t)/√(v̂_t,i)m_t-1,i + β_1,t/√(v̂_t,i)g_t,i)·(w_t,i - w^*_i)+ (η̂_t·m_t/√(v̂_t))^2

	
	Then,
	
    2η̂_t·β_1,t/√(v̂_t,i)g_t,i (w_t,i - w^*_i) = (w_t,i -w^*_i)^2 - (w_t+1,i -w_i^*)^2
       - 2η̂_t·(1 - β_1,t)/√(v̂_t,i)m_t-1,i·(w_t,i - w^*_i) + η̂^2_t·m^2_t,i/v̂_t,i

	
	So we can obtain
	
    g_t,i (w_t,i - w^*_i)    = √(v̂_t,i)/2η̂_tβ_1,t [(w_t,i - w^*_i)^2 - (w_t+1,i - w^*_i)^2]
            + (1-β_1,t)/β_1,tm_t-1,i(w^*_i - w_t,i)
            +η̂_t/2β_1,t·m^2_t,i/√(v̂_t,i)

	
	For the right part of (9) in the above formula, if we sum it from t=1 to t = T,
	
    ∑_t=1^T√(v̂_t,i)/2η̂_tβ_1,t[(w_t,i - w^*_i)^2 - (w_t+1,i - w^*_i)^2]
    ≤   1/ϵ_0{(w_1,i - w^*_i)^2·√(v̂_1,i)/η_1
    		
    		+… + (w_T,i - w^*_i)^2(√(v̂_T,i)/η_T - √(v̂_T-1,i)/η_T-1)}
    ≤   D^2/ϵ_0η√(Tv̂_T,i)

	
	The first inequality is satisfied because of the line 13 in Algorithm <ref>. For the (10) in the formula, if we sum it from t=1 to t = T,
	
    ∑_t=1^T(1-β_1,t)/β_1,tm_t-1,i(w^*_i - w_t,i)
    		≤(1-ϵ_0)G_∞ D_∞/K(1-λ)ϵ_0∑_t=1^T(1-β_1,t)
    ≤   (1-ϵ_0)G_∞ D_∞/K(1-λ)ϵ_0∑_t=1^T(1 - ϵ)
    		= (1-ϵ_0)G_∞ D_∞/K(1-λ)ϵ_0∑_t=1^T(1 - ϵ_0)λ^t-1
    ≤   (1-ϵ_0)^2G_∞ D_∞/K(1-λ)^2ϵ_0

	
	
	
	
	
	
	
	The first inequality is according to Lemma <ref>.	Finally, we will infer the (11) in previous formula. According to the Lemma 2 of <cit.>, we have
	
    ∑_t=1^Tη̂_t/2β_1,t·m^2_t,i/√(v̂_t,i)≤1/2ϵ_0∑_t=1^Tη_tm^2_t,i/√(v_t,i)≤η/2ϵ_0∑_t=1^T1/√(t)·m^2_t,i/√(v_t,i)
    ≤   η/2ϵ_0∑_t=1^T(∑_j=1^t(1-ϵ_0)^t-j)(∑_j=1^t(1-ϵ_0)^t-jg^2_j,i)/√(t((1-β_2)∑_j=1^tβ_2^t-jg^2_j,i))
    ≤   η/2ϵ^2_0√(1-β_2)∑_t=1^T1/√(t)∑_j=1^t(1-ϵ_0)^t-jg^2_j,i/√(β_2^t-jg^2_j,i)
    ≤   η/2ϵ^2_0√(1-β_2)∑_t=1^T|g_t,i|∑_j=t^Tγ_1^j-t/√(t)≤η√(1+log T)/2ϵ^2_0(1-γ_1)√(1-β_2)g_1:T,i_2

	
	In the above inequalities, some inferences are based on Cauchy-Schwarz Inequality. Therefore, the final bound of R(T) can be expressed as
	
    R(T)    ≤D^2/ϵ_0η∑_i=1^d√(Tv̂_T,i) + (1-ϵ_0)^2G_∞ D_∞ d/K(1-λ)^2ϵ_0
       + η√(1+log T)/2ϵ^2_0(1-γ_1)√(1-β_2)∑_i=1^dg_1:T,i_2

	
	

For the bound term, as T→ +∞, R(T)/T→ 0 and we can infer that lim_T→∞ [f_t(w_t) - f_t(w^*)] = 0, which means the proposed algorithm can finally converge. 









§ EXPERIMENTS

We have applied the  algorithm on multiple popular machine learning and deep learning structures, both convex and non-convex situations. To show the advantages of the algorithm, we compare it with various popular optimization algorithms, including  <cit.>, RMSProp <cit.>, AdaGrad <cit.> and SGD. For all the experiments, the loss function (objective function) we have selected is the cross-entropy loss function, and the size of the minibatch is 128. Besides, the learning rate is 0.0001.



 §.§ Experiment Settings and Results


Logistic Regression: We firstly evaluate our algorithm on the multi-class logistic regression model, since it is widely used and owns a convex objective function. We conduct logistic regression on the ORL dataset <cit.>. ORL dataset consists of face images of 40 people, each person has ten images and each image is in the size of 112× 92. The loss of objective functions on both training set and testing set are shown in Figure <ref>, <ref>.

Deep Neural Network: We use deep neural network (DNN) with two fully connected layers of 1,000 hidden units and the Relu <cit.> activation function. The dataset we use is MNIST <cit.>. The MNIST dataset includes 60,000 training samples and 10,000 testing samples, where each sample is a 28× 28 image of hand-written numbers from 0 to 9. Result are exhibited in Figure <ref>, <ref>.

Convolutional Neural Network: The CNN models in our experiments are based on the LeNet-5 <cit.>, and it is implemented on multiple datasets: ORL, MNIST and CIFAR-10 <cit.>. The CIFAR-10 dataset consists of 60,000 32× 32 images in 10 classes, with 6,000 images per class. For different datatsets, the structures of CNN models are modified: for the ORL dataset, the CNN model has two convolutional layers with 16 and 36 feature maps of 5 5 kernels and 2 max-pooling layers, and a fully connected layer with 1024 neurons; for the MNIST dataset, the CNN structure follows the LeNet-5 structure in <cit.>; for CIFAR-10 dataset, the CNN model consists of three convolutional layers with 64, 128, 256 kernels respectively, and a fully connected layer having 1024 neurons. All experiments apply Relu <cit.> activation function. The results are shown in Figure <ref>.


We can observe that  converges faster than other widely used optimization algorithms in all the cases. Within the same number of epoches,  can converge to the lowest loss on both the training set and test set.











 §.§ Analysis of the Backtrack Mechanism


To show the effectiveness of the backtrack term d_t, we also carry out the experiments of  without d_t term, and exhibit the results in Figures <ref>, <ref>. The results indicate that after applying d_t term, the converging speed will become slightly faster. To thoroughly prove the effectiveness of our proposed d_t term, we also compare it with other definitions of backtrack terms e.g., d_t = 0.5cosθ, and exhibit the results in Figure <ref>. In Figure <ref>, d_t = sigmoid _ based represents that d_t = -1/(1+ e^-(θ - 1/2π)) + 1/2, and d_t = tanh _ based means that d_t = -2/(1 + e^-2(x - 1/2π)) + 1. 


Due to the limited sapce, here we only exhibit the results on ORL dataset. From the results we can observe that the d_t definnition in  achieves the best congerging performance, which means our setting of d_t in  is effective.



 §.§ Time-consuming Analysis


We have recorded the running time of  and other comparison algorithms in every experiment, and list them in the Table <ref>. The running time shown in Table <ref> contains “>”, which means the model still does not converge at the specific time. From the results we can observe that in all of our experiments,  finally converges within the smallest mount of time. From the results in Figures <ref>,<ref> and Table <ref>, we can conclude that  can converge not only in fewer epochs, but using less running time. The device we used is the Dell PowerEdge T630 Tower Server, with 80 cores 64-bit Intel Xeon CPU E5-2698 v4@2.2GHz. The total memory is 256 GB, with an extra (SSD) swap of 250 GB.





§ CONCLUSION

In this paper, we have introduced a novel optimization algorithm, the , which implements the momentum with discriminative weights and the backtrack term. We have analyzed the advantages of the proposed algorithm and proved it by theoretical inference. Extensive experiments have shown that the proposed algorithm can converge faster than existing methods on both convex and non-convex situations, and the time consuming is better than existing methods. Not only the proposed algorithm can outperform other popular optimization algorithms, but fewer hyperparameters will be introduced, which makes the  much more applicable. 





named





