ACUTUM: WHEN GENERALIZATION MEETS ADAPT-
Year: 2019

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.

heading: 1 INTRODUCTION
text: 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.
• 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.
Notations. In the rest of this paper, we assume any decision variables θ ∈ Rd where d denotes the dimension of parameters. We denote the l2 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., a2 = [a21, a 2 2, . . .]
T ,a/b = [a1/b1, a2/b2, . . .]T . We denote by bxc the greatest integer less than or equal to the real number x. Given any integers x, y, where y 6= 0, we denote by x (mod y) the remainder of the Euclidean division of x by y. In the optimization setting, we denote by fi(·) the loss function when we feed the i-th training data into our model, we also denote fS(·) when we feed a collection of samples, i.e., fS(·) := ∑ i∈S fi(·). Given any point θ ∈ Rd and any convex set X ⊆ Rd, we denote by ΠX (θ) the projection of θ onto X , i.e., arg minµ∈X ‖µ− θ‖.

heading: 2 RELATED WORK
text: 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 gt√ vt ,
where gt denotes the stochastic gradient, vt is the accumulation of gradient’s second moments, i.e., vt = 1 t ∑t τ=1 g 2 τ , and αt is the decreasing learning rate with αt = O(1/ √ t). Theoretically, Ada-
grad 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., gt/ √ vt goes to zero very quickly due to vt 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:
θt+1 = θt − αt mt√ vt , (1)
where mt is the exponential decay of momentum, i.e., mt = ∑t τ=1(1 − β1)β t−τ 1 gτ , and vt is the
exponential decay of second moment, i.e., vt = ∑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.

heading: 3 THE ACUTE ADAPTIVE MOMENTUM ALGORITHM
text: 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:
θt+1 = θt − αtG−1/2t gt, (2) where Gt = ∑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
θt+1 = arg min θ (θ − θt)T gt︸ ︷︷ ︸ T1 + 1 2αt (θ − θt)T G1/2t (θ − θt)︸ ︷︷ ︸
T2
(3)
where the first-order penalty T1 leads the parameter θt to the opposite direction to the current gradient gt. Note that Adagrad can adaptively adjust each individual dimension of θt through introducing
Gt in the quadratic term T2, while SGD cannot. If we substitute the definition of Gt back into Equation (3), T2 can be formulated as:
T2 = 1
2αt (θ − θt)T G1/2t (θ − θt) =
1
2αt (θ − θt)T
( t∑
τ=1
gτg T τ )1/2 (θ − θt) . (4)
By Young’s inequality (Young, 1912), we can obtain an upper bound of T2 as follows:
T2 ≤ 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 gt︸ ︷︷ ︸ 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 T1 and T3, with a penalty for the projections of current descent θ − θt on the previous gradients gτ , i.e., T4.
With these observations in mind, a natural question comes out: how can we understand T4 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 {A0,A1, . . . ,Ap−1}, then the algorithm is fed with the sample in a fixed order, say, first A0, then A1, 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 ∇fAt(θt) be the gradient calculated on iteration t by using the sample in subset At, where 0 ≤ t < p due to the first pass. Note that the loss function is the sum of whole samples, e.g., 1n ∑n i=1 fi(θ), if we utilize
∇fAi(θt) to directly update parameters like SGD, e.g., θt+1 = θt − α∇fAt(θt), the batch loss∑ i∈At fi(θ) will decrease since it aligns with the opposite direction of its gradient, e.g., (θt+1 − θt) T∇fAt(θt) = −‖∇fAt(θt)‖2 < 0. However, for loss corresponding to the sample not in At, it is highly possible that (θt+1 − θt)T∇fAi(θt) > 0. On other words, only using −∇fAi(θt) as update direction will decrease the loss function corresponding to At but increase the total loss function except At.
Ideally, if there exists a direction θt+1−θt which is orthogonal to∇fAi(θt) for any i 6= t (mod p), and forms an acute angle with ∇fAt(θt), then θt+1 can guarantee a sufficient descent for the loss function corresponding to At while not increase the loss function outside At.
Then a natural update of θt+1 to achieve the above goal can be obtained by solving the following sub-problem:
arg min θ
c2 ‖θ − θt‖2 + c1 (θ − θt)T gt
s.t. (θ − θt)T ∇fAi(θt) = 0, i 6= t (mod p), (6)
In practice, however, the computational cost of computing ∇fAi(θt) for all i is expensive in each iteration. As a natural solution, we can approximate ∇fAi(θt) with previous gradients fAi(θi), which is exactly gi calculated in Adagrad in iteration i before iteration t, where i 6= t (mod p). Hence a soft margin variant of Equation (6) can be formulated as
θt+1 = arg min θ
c2,0 ‖θ − θt‖2 + c2,1 t∑
τ=1
∥∥∥(θ − θt)T gτ∥∥∥2 + c1 (θ − θt)T gt, (7)
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 ∇fAi(θt) using previous gradients gi in Adagrad performs well in practice, there is still a large accuracy gap. For example, let gt−1 and gt−2 denote the gradients ∇fAi−1(θt−1) and ∇fAi−2(θt−2), respectively. It is often the case that the approximation error between∇fAi−1(θt) and gt−1 is smaller than that between∇fAi−2(θt) and gt−2, assuming the objective is local smoothness1. In other words, the approximation accuracy of gτ to ∇fAi(θ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 θ
c2,0 ‖θ − θt‖2 + c2,1 t∑
τ=1 ∥∥∥(1− β)βt−τ (θ − θt)T gτ∥∥∥2 + c1 (θ − θt)T gt. This is what RMSProp actually does. Therefore, we obtain the same optimization intuition of RMSProp 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 mt 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 gt and mt, 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 mt is not accurate, we expect the current gradient gt to dominate the descent direction, which is denoted as m̂t. It can be guaranteed by requiring the projection length of m̂t on gt is less than the length of gt if properly regularizing mt. Then, we propose a new iterative subproblem in the following:
θt+1 = arg min θ
c2,0 ‖θ − θt‖2 + c1 (θ − θt)T ( gt + ‖gt‖
m̂t ‖m̂t‖
) ,
where m̂t+1 = gt + ‖gt‖ m̂t ‖m̂t‖ .
(8)
With such formulation, the following properties hold:
• We ensure the above two observations, specifically, with the update of momentum m̂t, we can guarantee that ‖m̂t+1‖ = O(‖gt‖).
• 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 m̂0 = 0 3: for t = 1 to T do 4: gt = ∇ft(θt) 5: m̂t = gt + β1,t ‖gt‖ / (‖m̂t−1‖+ ) · m̂t−1
6: θt+1 = ΠX (θt − αt · m̂t) 7: end for 8: Return: xT+1
Note that, at step 5 we use to prevent precision overflow caused by a tiny ‖m̂t−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.
1The local smoothness assumption is widely used in the convergence analysis for convex and non-convex objectives, see (Nesterov, 1998; Johnson & Zhang, 2013).

heading: 4 CONVERGENCE ANALYSIS
text: 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 f1, f2, . . . , fT , as shown in the following: Assumption 4.1 (Convexity Assumption). For each loss function ft(θ) where 1 ≤ t ≤ T , we assume it is convex. That is, for any x,y ∈ X , we have
ft(y) ≥ ft(x) +∇ft(x)T (y − x),
where X is the feasible set of function f1, f2, . . . , fT . 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 ft(θt)−min θ∈X T∑ t=1 ft(θ),
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 ft has bounded gradients, i.e., ‖∇ft(θ)‖∞ ≤ G∞ for all θ ∈ X , 1 ≤ t ≤ T , then the regret of Algorithm 1 satisfies:
R(T ) ≤ D 2 ∞
2α
√ dT + 3G∞α √ (1 + log T ) d d∑ i=1 ‖g1:T,i‖2 + √ dβD2∞ 2α (1− λ)2 . (9)
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 Õ( √ 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 ) = Õ( √ T ).
Corollary 4.3 illustrates that Acutum obtains RT = o(T ) for all situations which is independent of the sparsity of the data features. Besides, since limT→∞RT /T → 0, Acutum will converge to the optimal solution when the objectives are convex.

heading: 5 EXPERIMENTS
text: 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 l2 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
the convergence of training loss and the test accuracy of all optimizers with fixed weight decays (they optimize the same objective function). (ii) In Section 5.2, we adopt the optimal weight decays for all optimizers, then investigate their generalization ability based on the test accuracy.
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.

heading: 5.1 EXPERIMENT WITH FIXED WEIGHT DECAY
text: 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.

heading: 5.2 EXPERIMENT WITH OPTIMAL WEIGHT DECAY
text: 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.
As shown in Figure 2, Adam, AdamW and Amsgrad perform worse than the other optimizers in the plots of test accuracy. In this optimal weight decay setting, Padam, Adabound and Acutum can even have better test performance than SGD-momentum on VGGNet if sacrificing some convergence rate. Besides, they outperform Adam by more than 2 percentage points for the test accuracy. The experimental results demonstrate that optimizers which converge faster than Acutum generalize worse. Similar to results in previous section, Acutum can effectively bridge the generalization gap, and has a comparable performance with the state-of-the-art Adam’s variants while only requiring first moments.

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

heading: A PROOF OF THE MAIN RESULTS
text: 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 ⊂ Rd, 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 ‖m̂t‖ ≤ 2 ‖gt‖ at each iteration t if the momentum parameter satisfies β1,t ≤ 1.
Proof. With the definition of m̂t, we have ‖m̂t‖2 = ∥∥∥∥gt + β1,t ‖gt‖‖m̂t−1‖+ m̂t−1 ∥∥∥∥2 ≤ ‖gt‖2 + β21,t ‖gt‖ 2 +
2β1,t ‖gt‖ ‖m̂t−1‖ · ‖gt‖ · ‖m̂t−1‖
= (1 + β1,t) 2 ‖gt‖2 .
With the condition that β1,t ≤ 1, we have ‖m̂t‖ ≤ 2 ‖gt‖.
A.2 PROOF OF THEOREM 4.2
Proof. Consider the update rule of Algorithm 1, parameters θ∗ and θt satisfy ΠX (θ
∗) = θ∗ and ΠX (θt − αtm̂t) = θt+1. With Lemma A.1, we have
‖θt+1 − θ∗‖2 ≤‖θt − αtm̂t − θ∗‖2
= ‖θt − θ∗‖2 − 2αtm̂Tt (θt − θ∗) + α2t ‖m̂t‖ 2
1 = ‖θt − θ∗‖2 + α2t ‖m̂t‖ 2 − 2αt ( gt +
β1,t ‖gt‖ ‖m̂t−1‖+ m̂t−1
)T (θt − θ∗) , (10)
where 1 follows from the definition of m̂t. Rearrange the items in Equation (10), we obtain
gTt (θt − θ∗) ≤ 1
2αt
( ‖θt − θ∗‖2 − ‖θt+1 − θ∗‖2 ) + αt 2 ‖m̂t‖2 − β1,t ‖gt‖ ‖m̂t−1‖+ m̂Tt−1 (θt − θ∗)
1
≤ 1 2αt
( ‖θt − θ∗‖2 − ‖θt+1 − θ∗‖2 ) + αt 2 ‖m̂t‖2 + β1,t [ ‖θt − θ∗‖2 2αt + αt ‖gt‖2 ‖m̂t−1‖2 2 (‖m̂t−1‖+ )2 ]
≤ 1 2αt
( ‖θt − θ∗‖2 − ‖θt+1 − θ∗‖2 ) + αt 2 ‖m̂t‖2 + β1,t ( ‖θt − θ∗‖2 2αt + αt ‖gt‖2 2 ) ,
where 1 holds by the Young’s inequality. By Assumption 4.1, with the convexity of all fi, we have T∑ t=1 [ft(θt)− ft(θ∗)] ≤ T∑ t=1 gTt (θt − θ∗) .
Submit Equation (A.2) to the above inequalities, we obtain T∑ t=1 [ft(θt)− ft(θ∗)] ≤ T∑ t=1 d∑ i=1 1 2αt [ (θt,i − θ∗i ) 2 − (θt+1,i − θ∗i ) 2 ]
︸ ︷︷ ︸ T1
+
T∑ t=1 d∑ i=1 αt 2 m̂2t,i︸ ︷︷ ︸
T2
+ T∑ t=1 d∑ i=1 αtβ1,t 2
g2t,i︸ ︷︷ ︸ T3 +
T∑ t=1 d∑ i=1 β1,t 2αt (θt,i − θ∗i ) 2
︸ ︷︷ ︸ T4
,
(11)
where β1,t = βλt−1 is monotonically decreasing with t. For T1, we have
1
2 T∑ t=1 d∑ i=1 1 αt [ (θt,i − θ∗i ) 2 − (θt+1,i − θ∗i ) 2 ]
= 1
2
[ 1
α1 d∑ i=1 (θ1,i − θ∗i ) 2 + T∑ t=2 d∑ i=1 ( 1 αt − 1 αt−1 ) (θt,i − θ∗i ) 2 ]
≤D 2 ∞ 2 [ d∑ i=1 1 α1 + T∑ t=2 d∑ i=1 ( 1 αt − 1 αt−1 )]
= D2∞
2 d∑ i=1 1 αT = D2∞ 2α √ dT ,
(12)
where we set αt = α √ d/t. For T2 in Equation (11), we obtain
1
2 T∑ t=1 d∑ i=1 αtm̂ 2 t,i = 1 2 [ T−1∑ t=1 d∑ i=1 αtm̂ 2 t,i + d∑ i=1 αT m̂ 2 T,i ] 1
≤1 2 [ T−1∑ t=1 d∑ i=1 αtm̂ 2 t,i + 4α √ d√ T d∑ i=1 g2T,i ] ≤ 1 2 [ T−1∑ t=1 d∑ i=1 αtm̂ 2 t,i + 4G∞α √ d√ T d∑ i=1 |gT,i| ]
=2G∞α √ d T∑ t=1 1√ t d∑ i=1 |gt,i| = 2G∞α √ d d∑ i=1 T∑ t=1 |gt,i|√ t
2 ≤2G∞α √ d d∑ i=1 ‖g1:T,i‖2 √√√√ T∑ t=1 1 t ≤ 2G∞α √ (1 + log T ) d d∑ i=1 ‖g1:T,i‖2 ,
(13)
where we introduce Lemma A.2 in inequality 1 . Besides, we get 2 through Cauchy-Schwarz inequality. With similar proof techniques, we have T3 satisfied T∑ t=1 d∑ i=1 αtβ1,t 2 g2t,i ≤ T−1∑ t=1 d∑ i=1 αtβ1,t 2 g2t,i + αβ √ d 2 √ T d∑ i=1 g2T,i ≤ T−1∑ t=1 d∑ i=1 αtβ1,t 2 g2t,i + G∞αβ √ d 2 √ T d∑ i=1 |gT,i|
= G∞αβ
√ d
2
T∑ i=1 1√ t d∑ i=1 |gt,i| = G∞αβ √ d 2 d∑ i=1 T∑ t=1 |gt,i|√ t
≤G∞αβ √ d
2
d∑ i=1 ‖g1:T,i‖2 √√√√ T∑ t=1 1 t ≤ G∞αβ 2 √ (1 + log T )d d∑ i=1 ‖g1:T,i‖2 .
(14)
Since Equation (14) is sufficient for our regret convergence analysis, we have not tried to optimize it further. Then, for T4, we have
T∑ t=1 d∑ i=1 β1,t 2αt (θt,i − θ∗i ) 2 = T∑ t=1 β1,t 2αt d∑ i=1 (θt,i − θ∗i ) 2 1 = β1,t 2α √ d T∑ t=1 √ tλt−1 d∑ i=1 (θt,i − θ∗i ) 2
≤ √ dβD2∞ 2α T∑ t=1 √ tλt−1 ≤ √ dβD2∞ 2α T∑ t=1 tλt−1 2 ≤ √ dβD2∞ 2α (1− λ)2 , (15)
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
R(T ) ≤ D 2 ∞
2α
√ dT + 3G∞α √ (1 + log T ) d d∑ i=1 ‖g1:T,i‖2 + √ dβD2∞ 2α (1− λ)2 . (16)
This completes the proof.
A.3 PROOF OF COROLLARY 4.3
Proof. From Theorem 4.2, we have
R(T ) ≤ D 2 ∞
2α
√ dT + 3G∞α √ (1 + log T ) d d∑ i=1 ‖g1:T,i‖2 + √ dβD2∞ 2α (1− λ)2 . (17)
For the second term, we have
d∑ i=1 ‖g1:T,i‖2 ≤ d∑ i=1 √√√√ T∑ t=1 g2t,i ≤ dG∞ √ T (18)
Combining the above inequality with Equation (17), we obtain
R(T ) = Õ( √ T )

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