Title: ACUTUM: WHEN GENERALIZATION MEETS ADAPT-ABILITY

Abstract: In spite of the slow convergence, stochastic gradient descent (SGD) is still the most widely used optimization method due to its outstanding generalization ability and simplicity. On the other hand, adaptive methods have attracted much more attention of optimization and machine learning communities, both for the leverage of life-long information and for the deep and fundamental mathematical theory. Taking the best of both worlds is the most exciting and challenging question in the field of optimization for machine learning. In this paper, we revisit existing adaptive gradient methods from a novel point of view, which reveals a fresh understanding of momentum. Our new intuition empowers us to remove the second moment in Adam without the loss of performance. Based on our view, we propose a novel optimization method, the acute adaptive momentum (Acutum). To the best of our knowledge, Acutum is the first adaptive gradient method without second moments. Experimentally, we demonstrate that our method has a faster convergence rate than Adam/Amsgrad, and generalizes as well as SGD with momentum. We also provide a convergence analysis of our proposed method to complement our intuition.

1. INTRODUCTION:

With the rapid development of neural network architectures (Goodfellow et al., 2016) , training algorithms have attracted much more attention in the modern machine learning community. Due to the network size and data amount increasing dramatically, calculating the full gradient of data and implementing the full gradient descent (GD) become computationally expensive. Therefore, stochastic gradient descent (SGD) (Robbins & Monro, 1951) becomes the most practical optimization method for training deep neural networks (DNNs). In each iteration, SGD samples mini-batch data and computes the gradient corresponding to the mini-batch. Although SGD is computationally affordable, it needs a mechanism of fine-tune the learning rate, e.g., linear decay or exponential decay, to converge efficiently. In fact, it is pretty brittle to tune the learning rate dynamically with SGD.

To release the learning rate tuning burden of SGD and accelerate its convergence, several adaptive variants of SGD were proposed, including Adagrad (Duchi et al., 2011) , Adadelta (Zeiler, 2012) , RMSProp (Hinton et al., 2012) , Adam (Kingma & Ba, 2014) , etc. The descent direction is elementwise automatically adapted by the first moment and the second moment with an exponential average of gradients. Such a descent direction has achieved great improvements in practice, while the fundamental interpretation is still unclear. Besides, the theoretical regret analysis of these online learning algorithms has become completed gradually in convex objective settings. Due to the fast decay of exponential moving average, Adam cannot converge even in simple convex cases as shown in (Reddi et al., 2019) . Amsgrad (Reddi et al., 2019) addressed this issue by keeping an extra non-decreasing sequence to buffer the fast decay.

On the other hand, although adaptive methods are easy to use and fast to converge, the generalization results cannot be as good as SGD (Wilson et al., 2017) . Various works (Chen & Gu, 2018; Luo et al., 2019) have been proposed to make algorithms not only converge faster but also has good generalization. However, these algorithms still inherit the second moment following Adam. Different from existing works, we provide a novel view for this problem by revisiting adaptive algorithms Through the view of direction angle between the descent direction and the momentum, we are able to demonstrate a fresh understanding of momentum.

In summary, we propose a new algorithm, called acute adaptive momentum (Acutum), to find adaptive gradients with only the first moment. To remove the second moments safely, we investigate their properties by reformulating the proximal subproblem of Adagrad. The main observation is that second moments essentially penalize the projection of the current descent direction on the exponential moving average of previous gradients. The new intuition allows us to remove second moments in Adam without any loss of performance. To the best of our knowledge, it is the first time to remove the second moments for adaptive gradient methods. As shown by our experiment, the proposed algorithm (Acutum) outperforms Adam/Amsgrad in wall-clock time while almost preserving the generalization ability of SGD.

In particular, we make the following contributions:

• We propose a new optimization algorithm called Acutum, which doesn't need to compute the second moments. To the best of our knowledge, it is the first time to obtain the adaptive gradients with only the first moments. The intuition behind our algorithm is to remove second moments by attaching their purpose to the first moment through Adagrad's proximal subproblem inspiration. • We provide a regret convergence analysis of Acutum on the convex setting, based on the analysis of (Kingma & Ba, 2014; Reddi et al., 2019; Chen & Gu, 2018) , and prove a datadependent regret bound, complementing our intuition. Notations. In the rest of this paper, we assume any decision variables θ ∈ R d where d denotes the dimension of parameters. We denote the l 2 norm of a given vector θ by θ = d i=1 θ 2 i . With slightly abuse of notation, we write arithmetic symbols as element-wise operations for vectors, e.g.,

a 2 = [a 2 1 , a 2 2 , . . .] T , a/b = [a 1 /b 1 , a 2 /b 2 , .

. .] T . We denote by x the greatest integer less than or equal to the real number x. Given any integers x, y, where y = 0, we denote by x (mod y) the remainder of the Euclidean division of x by y. In the optimization setting, we denote by f i (•) the loss function when we feed the i-th training data into our model, we also denote f S (•) when we feed a collection of samples, i.e., f S (•) := i∈S f i (•). Given any point θ ∈ R d and any convex set X ⊆ R d , we denote by Π X (θ) the projection of θ onto X , i.e., arg min µ∈X µθ .

2. RELATED WORK:

The increasing size of deep neural networks and the amount of train data have dramatically induced the difficulty of training neural networks. The huge parameter size makes the landscape of neural networks more non-convex, and the amount of train data requires more computation resources to calculate the gradient. Therefore, all the facts urge researchers to design faster optimization algorithms for deep neural networks, while maintaining a reasonable generalization ability. SGD-momentum is widely used in training large-scale neural networks while the excellent generalization ability of SGD is vulnerable to its learning rate. Meanwhile, researchers began to focus on the design of adaptive gradient methods for a fast and simple optimizer. Adagrad proposed in (Duchi et al., 2011) introduced the second moment to obtain a self-adaptive learning rate, and hence freed researchers' hands of parameter tuning. The update rules of Adagrad can be formulated as follows:

θ t+1 = θ t -α t g t √ v t ,

where g t denotes the stochastic gradient, v t is the accumulation of gradient's second moments, i.e., v t = 1 t t τ =1 g 2 τ , and α t is the decreasing learning rate with α t = O(1/ √ t). Theoretically, Adagrad improves the convergence of regret from O(

√ d/ √ T ) to O(1/ √ T )

for the convex objectives with sparse gradients. However, in practice, people realize that adaptive gradient of Adagrad, i.e., g t / √ v t goes to zero very quickly due to v t accumulating to large number quickly as the algorithm proceeds. To make it through, RMSProp (Hinton et al., 2012) introduced the exponential decay in the second moment to control the accumulation speed of second moment in Adagrad. Furthermore, (Kingma & Ba, 2014) incorporated the momentum into RMSProp and proposed Adam. The detailed procedure of Adam can be formulated as:

EQUATION

where m t is the exponential decay of momentum, i.e., m t = t τ =1 (1 -β 1 )β t-τ 1 g τ , and v t is the exponential decay of second moment, i.e., v t =

t τ =1 (1 -β 2 )β t-τ 2 g 2 τ .

The faster convergence, robust hyper-parameters and good performance on CV and NLP's tasks make Adam become one of the most successful optimizers these years. However, (Reddi et al., 2019) showed Adam does not converge in certain convex cases, and proposed Amsgrad to correct the direction of Adam with imposing an increasing sequence of the second moment.

Although convergence, in theory, is fixed and the training speed is still fast, the generalization ability of adaptive algorithms is still worse than SGD with momentum. Thus, there are a lot of studies to improve the generalization performance of Adam types algorithms. Almost all of these works try to make some connections between Adam and SGD-momentum such that the proposed algorithm converges faster like Adam while generalizing better as SGD. For example, (Zhang et al., 2017) proposed a normalized direction-preserving Adam (ND-Adam). To make the direction of the gradients preserved, the authors adjusted the learning rate to each weight vector as a whole, instead of each individual weight. It could be thought as an adjustment of learning rate dynamically in each iteration, instead of the learning rate decay. (Loshchilov & Hutter, 2017) proposed to modify Adam to decay all weights the same regardless of the gradient variances. (Keskar & Socher, 2017) proposed to improve the generalization performance by investigating a hybrid strategy that begins training with an adaptive method and switches to SGD when appropriate. The experimental results show that it obtains a better generalization with the convergence speed sacrificing. With a similar insight, (Luo et al., 2019) introduced the element-wise clipping technique to the second moment and proposed AdaBound, which allows the algorithm behavior switched from a clipped Adam to SGD-momentum as the algorithm proceeds. Besides, (Chen & Gu, 2018) proposed Padam which tried to find the balanced state between Adam and SGD-momentum through tuning the order of the second moment in the update paradigm.

All the aforementioned methods try to find the connection between Adam and SGD-momentum, thus all these algorithms take the second moment adaptation as a grant. The difference between previous works and ours is that we suggest to remove the second moment and propose an angle based algorithm, by revisiting the original idea of second moment adaptation. Such intuition could be of independent interest in the field of the optimization community.

3. THE ACUTE ADAPTIVE MOMENTUM ALGORITHM:

In this section, we first revisit existing adaptive algorithms from a novel point of view, then introduce the intuition and provide the algorithm procedure of our method Acutum. The performance guarantees established in Section 4 and evaluation results in Section 5 validate our insights.

From the above section, one may notice that almost all the adaptive methods utilize second moments to adjust the individual magnitude of the updates. However, the efficient calculation of second moments, see Equation ( 1), is only proposed in Adagrad (Duchi et al., 2011 ). Let's take a look at the original update paradigm of Adagrad:

EQUATION

where G t = t τ =1 g τ g T τ , and g τ denotes the stochastic gradient calculated at iteration τ . Recall that in each iteration, SGD seeks the optimal solution of a subproblem constructed from a quadratic approximation of the objective. Similarly, we can write the update procedure of Adagrad in Equation (2) as

EQUATION

where the first-order penalty T 1 leads the parameter θ t to the opposite direction to the current gradient g t . Note that Adagrad can adaptively adjust each individual dimension of θ t through introducing G t in the quadratic term T 2 , while SGD cannot. If we substitute the definition of G t back into Equation (3), T 2 can be formulated as:

EQUATION

By Young's inequality (Young, 1912) , we can obtain an upper bound of T 2 as follows:

T 2 ≤ 1 8α t θ -θ t 2 T3 + 1 2α t t τ =1 (θ -θ t ) T g τ 2 T4

.

(5)

Combining Equation ( 5) and Equation (3), we can approximate the update rule of Adagrad as follows:

θ t+1 ≈ arg min θ (θ -θ t ) T g t T1 + 1 8α t θ -θ t 2 T3 + 1 2α t t τ =1 (θ -θ t ) T g τ 2 T4

.

We can think the upper bound of the Adagrad subproblem as the combination of the standard first and second order penalty as T 1 and T 3 , with a penalty for the projections of current descent θθ t on the previous gradients g τ , i.e., T 4 .

With these observations in mind, a natural question comes out: how can we understand T 4 in neural network training tasks or in general online learning tasks?

Before answering this question, we first describe the practical usage of training samples. The training procedure of DNNs can be stated as follows. The algorithm randomly shuffles the whole training dataset A and partitions A into mini-batch of equal size {A 0 , A 1 , . . . , A p-1 }, then the algorithm is fed with the sample in a fixed order, say, first A 0 , then A 1 , and so on. The whole procedure repeats after each pass of the whole dataset.

To make our description more clear, we take the first pass as an example. Let ∇f At (θ t ) be the gradient calculated on iteration t by using the sample in subset A t , where 0 ≤ t < p due to the first pass. Note that the loss function is the sum of whole samples, e.g., 1

n n i=1 f i (θ), if we utilize ∇f Ai (θ t ) to directly update parameters like SGD, e.g., θ t+1 = θ t -α∇f At (θ t ), the batch loss i∈At f i (θ) will decrease since it aligns with the opposite direction of its gradient, e.g., (θ t+1θ t ) T ∇f At (θ t ) = -∇f At (θ t ) 2 < 0. However, for loss corresponding to the sample not in A t , it is highly possible that (θ t+1 -θ t ) T ∇f Ai (θ t ) > 0. On other words, only using -∇f Ai (θ t ) as update direction will decrease the loss function corresponding to A t but increase the total loss function except A t .

Ideally, if there exists a direction θ t+1 -θ t which is orthogonal to ∇f Ai (θ t ) for any i = t (mod p), and forms an acute angle with ∇f At (θ t ), then θ t+1 can guarantee a sufficient descent for the loss function corresponding to A t while not increase the loss function outside A t .

Then a natural update of θ t+1 to achieve the above goal can be obtained by solving the following sub-problem:

EQUATION

In practice, however, the computational cost of computing ∇f Ai (θ t ) for all i is expensive in each iteration. As a natural solution, we can approximate ∇f Ai (θ t ) with previous gradients f Ai (θ i ), which is exactly g i calculated in Adagrad in iteration i before iteration t, where i = t (mod p). Hence a soft margin variant of Equation ( 6) can be formulated as

EQUATION

which is exactly the formulation in Equation ( 5) and Equation ( 3)! Thus, one can reasonably consider that Adagrad decreases the cumulative loss by guaranteeing a descent on the current batch loss while does not increase previous batch loss.

Although the approximation of ∇f Ai (θ t ) using previous gradients g i in Adagrad performs well in practice, there is still a large accuracy gap. For example, let g t-1 and g t-2 denote the gradients ∇f Ai-1 (θ t-1 ) and ∇f Ai-2 (θ t-2 ), respectively. It is often the case that the approximation error between ∇f Ai-1 (θ t ) and g t-1 is smaller than that between ∇f Ai-2 (θ t ) and g t-2 , assuming the objective is local smoothness1 . In other words, the approximation accuracy of g τ to ∇f Ai (θ t ) decays as τ decreases. Inspired by this observation, we substitute the arithmetic average in Equation ( 7) to exponential moving average and reassign the coefficients of g τ like Adam/momentum methods, then Equation ( 7) becomes

θ t+1 = arg min θ c 2,0 θ -θ t 2 + c 2,1 t τ =1 (1 -β) β t-τ (θ -θ t ) T g τ 2 + c 1 (θ -θ t ) T g t .

This is what RMSProp actually does. Therefore, we obtain the same optimization intuition of RM-SProp as Adagrad but add weight of the approximate gradient according to its approximation accuracy.

Enlightened by the above analysis, we are ready to propose a new adaptive momentum method. Let m t denote the approximated gradient of the previous batch loss at current parameters. With the following observation: (i) if θ t -θ t+1 forms acute angles with both g t and m t , rather than penalizing the projection like what Adagrad and RMSProp do, we can obtain both descent on current and previous batches; (ii) to handle the case when the estimation of previous gradients using m t is not accurate, we expect the current gradient g t to dominate the descent direction, which is denoted as mt . It can be guaranteed by requiring the projection length of mt on g t is less than the length of g t if properly regularizing m t . Then, we propose a new iterative subproblem in the following:

θ t+1 = arg min θ c 2,0 θ -θ t 2 + c 1 (θ -θ t ) T g t + g t mt mt ,

where mt+1 = g t + g t mt mt .

(

EQUATION

With such formulation, the following properties hold:

• We ensure the above two observations, specifically, with the update of momentum mt , we can guarantee that mt+1 = O( g t ).

• We attach the properties of the second moment to the first-order operation, inspired by Adagrad proximal subproblem.

The proposed algorithm Acutum is summarized in Algorithm 1.

Algorithm 1 Acute Adaptive Momentum method (Acutum) 1: Input: initial point θ 0 ∈ X ; step size {α t }, momentum parameters {β t } 2: set m0 = 0 3: for t = 1 to T do 4:

g t = ∇f t (θ t ) 5: mt = g t + β 1,t g t ( mt-1 + ) • mt-1 6: θ t+1 = Π X (θ t -α t • mt ) 7: end for 8: Return: x T +1

Note that, at step 5 we use to prevent precision overflow caused by a tiny mt-1 . β 1,t is the momentum weight. We specify its value in the theoretical analysis in Section 4. In practice, we can simply set β 1,t to be 1. Compared with other adaptive gradient methods, Acutum has fewer hyper-parameters, and is much easier to tune deep models. Besides, it is also computation-friendly (for both time and space complexities) since the algorithm does not need second moments.

4. CONVERGENCE ANALYSIS:

In this section, we analyze the convergence rate of our proposed algorithm Acutum in an online convex setting, i.e., we assume the convexity of a sequence of loss functions f 1 , f 2 , . . . , f T , as shown in the following: Assumption 4.1 (Convexity Assumption). For each loss function f t (θ) where 1 ≤ t ≤ T , we assume it is convex. That is, for any x, y ∈ X , we have

f t (y) ≥ f t (x) + ∇f t (x) T (y -x),

where X is the feasible set of function f 1 , f 2 , . . . , f T .

Notice that this assumption is widely used for theoretical analysis, in both stochastic optimization methods (Johnson & Zhang, 2013; Defazio et al., 2014; Shalev-Shwartz & Zhang, 2013) and online learning methods (Duchi et al., 2011; Kingma & Ba, 2014; Reddi et al., 2019) . Rather than consider the objective as a finite-sum function, here we analyze the regret from a online learning perspective. That is to say, at each time step t, we are given the loss f (θ t ) after selecting some feasible solution θ t . Then we continue to pick the next point θ t+1 based on the previous losses.

We adopt online regret as the convergence metric, which equals to the relative difference between the algorithm's cumulative loss and the offline minimum value. The definition of regret is straightforward, i.e.,

R(T:

) := T t=1 f t (θ t ) -min θ∈X T t=1 f t (θ),

where X is the feasible set over all steps. Our purpose is to find a sequence of points {θ t } 1≤t≤T to minimize the overall regret R(T ). We state the main theoretical results in the following theorem.

Theorem 4.2. Suppose Assumption 4.1 holds. We set > 0, α t = α d/t, β 1,t = βλ t-1 , where β, λ ∈ (0, 1). If the diameter of the convex feasible set X are bounded, i.e., θθ * ∞ ≤ D ∞ for all θ ∈ X , and f t has bounded gradients, i.e., ∇f t (θ) ∞ ≤ G ∞ for all θ ∈ X , 1 ≤ t ≤ T , then the regret of Algorithm 1 satisfies:

EQUATION

)

Theorem 4.2 shows that our proposed algorithm has a similar order of step size to online gradient descent, i.e., O( d/t), because of removing the second moments. In this situation, weight decay and appropriate learning rate decay strategies have much more influence on Acutum than Adamtype optimizers. Also, from the proof of Theorem 4.2 in appendix A.2, we find that the same order of regret bound can also be obtained even with a more modest momentum decay β 1,t = β/t. Furthermore, we show in the following corollary that our Acutum enjoys a regret bound of Õ( √ T ), which is comparable to the best of known bound for general convex online learning problems. Corollary 4.3. Frame the hypotheses of Theorem 4.2, for all T ≥ 1, the regret of Algorithm 1 satisfies R(T ) = Õ( √ T ).

Corollary 4.3 illustrates that Acutum obtains R T = o(T ) for all situations which is independent of the sparsity of the data features. Besides, since lim T →∞ R T /T → 0, Acutum will converge to the optimal solution when the objectives are convex.

5. EXPERIMENTS:

In this section, we conduct extensive experiments on image classification tasks. We want to validate that Acutum with only first moments can not only obtain a better generalization performance than adaptive gradient methods, but also converges faster than SGD-momentum.

First, note that introducing weight decay is equivalent to adding l 2 regularization to the objectives, and has a significant impact on the generalization ability of optimizers. To better characterize generalization performance, we conduct experiments from two perspectives: (i) In Section 5.1, we record Now we introduce the experimental settings of our experiments, which are general and commonly used. Specifically, we implement all of our codes in Pytorch platform version 1.0+ within Python 3.6+. To obtain sufficient comparisons with adaptive gradient variants, we choose various baselines, including SGD-momentum, Adam (Kingma & Ba, 2014), Amsgrad (Reddi et al., 2019) , Adamw (Loshchilov & Hutter, 2017) , Yogi (Zaheer et al., 2018) , Padam (Chen & Gu, 2018) , Radam (Liu et al., 2019) and Adabound (Luo et al., 2019) . For the image classification tasks, we use two datasets CIFAR-10, CIFAR-100 (Krizhevsky et al., 2009) , and test three different CNN architectures including VGGNet (Simonyan & Zisserman, 2014) , ResNet (He et al., 2016) and DenseNet (Huang et al., 2017) . To obtain stable convergence, we run 200 epochs, and decay the learning rate by 0.1 every 50 epochs. We perform cross-validation to choose the best learning rates for all optimizers and second moment parameters β 2 for all adaptive gradient methods.

5.1. EXPERIMENT WITH FIXED WEIGHT DECAY:

We first evaluate CIFAR-100 dataset. In this experiment, the values of weight decay in all optimizers are fixed, and are chosen to be the weight decay in SGD-momentum when it achieves the maximum test accuracy.

From the first row of Figure 1 , i.e, the training curves of three tests, we observe that our proposed Acutum significantly outperforms Adam, and has comparable rate with Padam and Adabound when we fix the weight decay. Also, in the second row of Figure 1 , i,e, the test accuracy, our Acutum outperforms all benchmarks except only SGD-momentum. However, the training loss converges much slower when implemented with SGD-momentum which is also recorded in other literature.

The above evaluation results validate that our method achieves both fast convergence and good generalization when the weight decay is fixed. Note that the AdamW method reduces training loss quickly, however, there is a large generalization gap between it and other optimizers, including SGD-momentum, Acutum, Padam.

5.2. EXPERIMENT WITH OPTIMAL WEIGHT DECAY:

In this section, we conduct experiments on CIFAR-10 dataset. Specifically, we find the optimal weight decay for each optimizer which can obtain the maximum test accuracy. 

6. CONCLUSION:

In this paper, we revisited the existing adaptive optimization methods from a novel point of view. We found that the widely used second moments essentially penalize the projection of the current descent direction on the exponential moving average of previous gradients. In other words, it aims to decrease the current batch loss while does not increase previous batch loss. Following such new idea, we investigate how to obtain descent on both current and previous batches. Specifically, we proposed a new method, acute adaptive momentum (Acutum). It removes the computationcomplicated second moments and constructed a decent direction by forming acute angles with both current and (approximated) previous gradients. We analyzed its convergence property in the online convex setting. The extensive evaluations demonstrate that our Acutum can effectively bridge the gap between fast convergence and good generalization, i.e., the advantages of both adaptive gradient methods and SGD-momentum.

For future work, it would be interesting to evaluate our method in other types of tasks and deep models, especially NLP and GAN problems. Besides, explaining the generalization ability of SGD is one of the most significant open problems in this field. We also hope that one could improve the convergence rate of SGD by only scheduling the learning rate carefully and dynamically.

A PROOF OF THE MAIN RESULTS:

A.1 SOME IMPORTANT LEMMAS

In this section, we give several important definitions and lemmas which will be used in the proof of the regret convergence. Lemma A.1. For some convex feasible set X ⊂ R d , suppose θ1 = min θ∈X θθ 1 and θ2 = min θ∈X θθ 2 then we have θ1 -θ2 ≤ θ 1 -θ 2 .

Proof. Here, we only provide the proof for completeness. Combining the definition θ1 = min θ∈X θθ 1 , θ2 = min θ∈X θθ 2 with the properties of projection operator, we have

θ1 -θ 1 T θ2 -θ1 ≥ 0 and θ2 -θ 2 T θ1 -θ2 ≥ 0.

From the above inequalities, we can obtain

θ1 -θ 1 T θ2 -θ1 + θ 2 -θ2 T θ2 -θ1 ≥ 0 ⇔ (θ 2 -θ 1 ) T θ2 -θ1 ≥ θ2 -θ1 2 .

With the property that (θ 2 -θ 1 ) -θ2 -θ1 2 ≥ 0, we have

θ 2 -θ 1 2 ≥ -θ2 -θ1 2 + 2 (θ 2 -θ 1 ) T θ2 -θ1 ≥ θ2 -θ1 2 .

Thus, the proof has been completed.

Lemma A.2. In the Algorithm 1, we have mt ≤ 2 g t at each iteration t if the momentum parameter satisfies β 1,t ≤ 1.

Proof. With the definition of mt , we have

mt 2 = g t + β 1,t g t mt-1 + mt-1 2 ≤ g t 2 + β 2 1,t g t 2 + 2β 1,t g t mt-1 • g t • mt-1 = (1 + β 1,t ) 2 g t 2 .

With the condition that β 1,t ≤ 1, we have mt ≤ 2 g t .

A.2 PROOF OF THEOREM 4.2

Proof. Consider the update rule of Algorithm 1, parameters θ * and θ t satisfy

EQUATION

where 1 follows from the definition of mt . Rearrange the items in Equation (10), we obtain

g T t (θ t -θ * ) ≤ 1 2α t θ t -θ * 2 -θ t+1 -θ * 2 + α t 2 mt 2 - β 1,t g t mt-1 + mT t-1 (θ t -θ * ) 1 ≤ 1 2α t θ t -θ * 2 -θ t+1 -θ * 2 + α t 2 mt 2 + β 1,t θ t -θ * 2 2α t + α t g t 2 mt-1 2 2 ( mt-1 + ) 2 ≤ 1 2α t θ t -θ * 2 -θ t+1 -θ * 2 + α t 2 mt 2 + β 1,t θ t -θ * 2 2α t + α t g t 2 2 ,

where 1 holds by the Young's inequality. By Assumption 4.1, with the convexity of all f i , we have

T t=1 [f t (θ t ) -f t (θ * )] ≤ T t=1 g T t (θ t -θ * ) .

Submit Equation (A.2) to the above inequalities, we obtain

EQUATION

where β 1,t = βλ t-1 is monotonically decreasing with t. For T 1 , we have

EQUATION

where we set α t = α d/t. For T 2 in Equation ( 11 (θ t,i -θ * i )

EQUATION

where 1 follows from the definition of β 1,t and α t , and 2 establishes because of the geometric series summation rule. As a result, submitting Equation ( 12), Equation (13), Equation ( 14) and Equation ( 15) back into Equation ( 11), we have

EQUATION

)

This completes the proof.

A.3 PROOF OF COROLLARY 4.3

Proof. From Theorem 4.2, we have

EQUATION

For the second term, we have 

:

The local smoothness assumption is widely used in the convergence analysis for convex and non-convex objectives, see(Nesterov, 1998;Johnson & Zhang,

2013).

Figures and Tables:

Figure 1: With a same weight decay, train loss and test accuracy of different optimizers for VGGNet, ResNet and DenseNet on CIFAR-100.

Figure 2: With different weight decays, train loss and test accuracy of different optimizers for VG-GNet, ResNet and DenseNet on CIFAR-10.

We also provide various experiments about our proposed Acutum on training modern deep models. The experimental results empirically show that Acutum takes the best from both Adam-type methods and SGD.

Table content: <table/>

where we introduce Lemma A.2 in inequality 1 . Besides, we get 2 through Cauchy-Schwarz inequality. With similar proof techniques, we have T 3 satisfied Since Equation (14) is sufficient for our regret convergence analysis, we have not tried to optimize it further. Then, for T 4 , we have

Table content: <table><tr><td/><td colspan="2">T t=1</td><td colspan="2">d i=1</td><td colspan="2">β 1,t 2α t</td><td colspan="8">(θ t,i -θ  *  i ) 2 =</td><td colspan="3">T t=1</td><td colspan="3">β 1,t 2α t</td><td>d i=1</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td>), we obtain</td></tr><tr><td>1 2</td><td colspan="2">T t=1</td><td colspan="2">d i=1</td><td>α t</td><td colspan="2">m2 t,i = 1 ≤</td><td colspan="2">1 2 1 2</td><td colspan="2">T -1 t=1 T -1 t=1</td><td colspan="5">d i=1 d i=1</td><td colspan="2">α t α t</td><td colspan="3">m2 t,i + m2 t,i +</td><td>d i=1 4α √ α T d √ T</td><td>m2 T,i d i=1 g 2 T,i ≤</td><td>1 2</td><td>T -1 t=1</td><td>d i=1</td><td>α t</td><td>m2 t,i +</td><td>4G ∞ α √ T</td><td>√</td><td>d</td><td>d i=1</td><td>|g T,i |</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td colspan="4">=2G ∞ α</td><td colspan="3">√</td><td colspan="2">d</td><td colspan="3">T t=1</td><td colspan="2">1 √ t</td><td>d i=1</td><td>|g t,i | = 2G ∞ α</td><td>√</td><td>d</td><td>d i=1</td><td>T t=1</td><td>|g t,i | √ t</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td colspan="4">2 ≤2G ∞ α</td><td colspan="3">√</td><td colspan="2">d</td><td colspan="2">d i=1</td><td/><td colspan="4">g 1:T,i 2</td><td>T t=1</td><td>1 t</td><td>≤ 2G ∞ α (1 + log T ) d</td><td>d i=1</td><td>g 1:T,i 2 ,</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td>(13)</td></tr><tr><td colspan="2">T t=1</td><td colspan="2">d i=1</td><td colspan="3">α t β 1,t 2</td><td colspan="2">g 2 t,i ≤ =</td><td colspan="11">T -1 t=1 G ∞ αβ d i=1 √ α t β 1,t 2 d 2 T i=1</td><td colspan="3">g 2 t,i + 1 √ t d i=1 αβ 2 √ √ T d |g t,i | = i=1 d G ∞ αβ g 2 T,i ≤ √ T -1 t=1 d 2 d i=1 d i=1 T t=1 α t β 1,t 2 |g t,i | √ t</td><td>g 2 t,i +</td><td>G ∞ αβ 2 √ T √</td><td>d</td><td>d i=1</td><td>|g T,i |</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td colspan="2">≤</td><td colspan="4">G ∞ αβ 2</td><td colspan="3">√</td><td>d</td><td colspan="3">d i=1</td><td/><td colspan="2">g 1:T,i 2</td><td>T t=1</td><td>1 t</td><td>≤</td><td>G ∞ αβ 2</td><td>(1 + log T )d</td><td>d i=1</td><td>g 1:T,i 2 .</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td>(14)</td></tr></table>

Peer review (iclr2020):
This paper proposes new stochastic optimization methods to achieve a fast convergence of adaptive SGD and preserve the generalization ability of SGD. The idea is to let the search direction opposite to the gradient at the current batch of examples and a bit orthogonal to previous batch of examples. The algorithm is easy to implement and backed up with regret bounds. Several experimental results are also reported to verify the effectiveness of the algorithm. The regret bound in Theorem 4.2. is not quite satisfactory. For example, Adagrad in Duchi et al (2011) can achieve the regret bound . However, there is an additional factor of in the regret boun in Theorem 4.2, which is not appealing in high dimensional problems. The regret analysis follows largely from standard arguments. I can not follow the last identity of (10). It should not hold since there is a missing there. In both eq (14) and (15), it is not clear to me why the authors divided the summation into two parts. Also, should be there. ---------------------- After rebuttal: I have read the author response. Unlike AdaGrad, the proposed algorithm does not show an advantage over standard OGD. I would like to keep my original score.