Year: 2019

Abstract:
Adaptive moment methods have been remarkably successful for optimization under the presence of high dimensional or sparse gradients, in parallel to this, adaptive sampling probabilities for SGD have allowed optimizers to improve convergence rates by prioritizing examples to learn efficiently. Numerous applications in the past have implicitly combined adaptive moment methods with adaptive probabilities yet the theoretical guarantees of such procedures have not been explored. We formalize double adaptive stochastic gradient methods DASGRAD as an optimization technique and analyze its convergence improvements in a stochastic convex optimization setting, we provide empirical validation of our findings with convex and non convex objectives. We observe that the benefits of the method increase with the model complexity and variability of the gradients, and we explore the resulting utility in extensions to transfer learning.

heading: 1 INTRODUCTION AND MOTIVATION
text: Stochastic gradient descent (SGD) is a widely used optimization method, and currently through backpropagation this algorithm has propelled the success of many deep learning applications. The Deep Learning community has particularly adopted variants of adaptive moment methods for SGD that specialize in high-dimensional features and non convex objectives, examples include ADAGRAD, ADADELTA, RMSPROP, ADAM and AMSGRAD (Duchi et al. (2011); Zeiler (2012); Tieleman & Hinton (2012); Kingma & Ba (2014); Reddi et al. (2018)). All these adaptive moment methods relied on the efficient use of the information of the geometry of the problem to improve the rate of convergence.
In parallel to the previous ideas, adaptive probabilities methods for SGD, traditionally focusing on convex objectives, have shown advantages over its uniform sampling baselines, by allowing a more efficient use of the gradient information (Zhu (2018); Shen et al. (2016); Bottou et al. (2016); Csiba et al. (2015); Stich et al. (2017)).
Adaptive probabilities were introduced to the Deep Learning community by Hinton (2007) through the discriminative fine tuning procedure. The method was further explored in a range of applications like object detection, reinforcement learning and curriculum learning (Shrivastava et al. (2016); Schaul et al. (2015); Bengio et al. (2009)). In these examples the combination of adaptive moments and adaptive probabilities methods was implicit and its analysis as a pure optimization technique was still an open question.
In this paper we analyze the asymptotic convergence properties of combining adaptive probabilities and adaptive moments. To our knowledge such family has not yet been introduced as an optimization procedure. We will refer to this family of optimization algorithms as Double Adaptive Stochastic Gradient DASGRAD.
We show that the improvements of DASGRAD depend on its flexibility to control the variance of the adaptive moments methods. We prove the theoretical guarantees and improvements in a convex setting and validate these observations empirically in convex and deep learning objectives. Finally we demonstrate the generalization properties of the algorithm with a simple extension to importance weight transfer learning.

heading: 2 ADAPTIVE GRADIENT METHODS
text: Notation. In order to facilitate the proofs and reading process we introduce some simplified notation that will be common to the analyzed algorithms. Let a, b ∈ Rd andM ∈ Sd+, then the multiplication of vector a by the inverse of M will be M−1a = a/M . Let √ a be the element-wise square root of vector a, a2 the element-wise square, a/b the element-wise division, and max(a, b) the elementwise max of vector a and vector b. Finally for any natural n the set {1, . . . , n} is denoted as [n]. Let T = {(xi,yi)}ni=1 be a training set; let f : Θ ×X × Y → R be a differentiable function that represents the empirical risk of an agent over T for the parameters θ ∈ Θ, with Θ ⊆ Rd a convex feasible set of parameters; let Sd+ the set of positive definite matrices in Rd×d, for a given matrix M ∈ Sd+ and parameter θ′ ∈ Θ; let ΠΘ,M be the projection operator over the feasible domain defined by ΠΘ,M (θ′) = arg minθ∈Θ ||M1/2(θ − θ′)||. 1
For the iterative stochastic optimization algorithmA, let it be a sampled index i at step t drawn from the training set indices [n], with it ∼ pt and pt ∈ ∆n+ = {p ∈ Rn : pi > 0 Σipi = 1}. We denote the evaluated risk f(θ,xi,yi) = fi(θ), the complete gradient∇f(θt) = 1nΣit∇fit(θt) and the stochastic gradient∇fit(θt), analogous a full descent directionmt = 1nΣitmit and a stochastic descent directionmit .
Stochastic Optimization Framework. To analyze the convergence of the stochastic optimization algorithm A we use the convex optimization setting where we assume that the objective function is convex with bounded gradients, that is ||∇fi(θ)||∞ ≤ G for all i ∈ [n], θ ∈ Θ, and finally the parameter space Θ has bounded diameter, that is ||θ − θ′||∞ ≤ D for all θ,θ′ ∈ Θ. For our purposes, the algorithm A at time t chooses a distribution over the training set p̂t ∈ ∆n+, obtains a training example it ∼ p̂t and its importance weights ŵit = (1/n)/pit , then updates its parameters θt ∈ Θ using the available data at time t and the importance weights ŵit to unbias the direction of the gradients. After the update, the algorithm incurs in a loss from an unknown function f(θt). To assess the performance of the algorithm after T steps we use the expected regret, which measures the difference of the loss at time t and the loss for optimal fixed parameter, along the possible trajectories induced by the chosen probabilities.
R(A) = ∑T t=1 En [ fi(θt)−minθEn[fi(θ)] ]
The goal is to design an algorithm A that has sub linear expected regret R(A)T = O(T ), which in turn implies that the algorithm will converge on average to the optimal parameter.
Algorithm 1: Double Adaptive Methods Input: θ1 ∈ Θ, step size {αt > 0}Tt=1, functions {φt, ψt}Tt=1 for t = 1 to T do
Choose p̂t ∈ ∆n+, and sample it ∼ p̂t Calculate git = ∇fit(θt) and ŵit = (1/n)/p̂it mit = φt (gi1 , . . . , git) and V̂it = ψt (gi1 , . . . , git) θ̂t+1 = θt − αtŵit V̂ −1/2 it
mit θt+1 = ΠΘ,V̂ 1/2it (θ̂t+1)
Algorithm 1 constitutes the general family of double adaptive gradient methods. This algorithm comprehends the classical stochastic gradient descent, adaptive moment methods family Zeiler (2012); Tieleman & Hinton (2012); Kingma & Ba (2014); Reddi et al. (2018), and second order methods Duchi et al. (2011), varying the averaging functions of the past gradients with φt : Θ t → Rd, and approximating the Hessian matrix with the functions ψt : Θt → Sd+.
1The projection operator enables the algorithm to deal with constrained optimization over compact convex domains that are equivalent to common regularization techniques like ridge and LASSO.
Adaptive Probabilities Methods. The classic stochastic gradient descent algorithm is recovered with the following step size, sampling probabilities and functions:
αt = α/ √ t pit = 1/n for all t ∈ [T ], i ∈ [n]
φt(gi1 , . . . , git) = git ψt(gi1 , . . . , git) = I (SGD)
Adaptive probabilities methods can be obtained simply by allowing the algorithm to choose a different probability p̂t at any time t:
αt = α/ √ t p̂t ∈ ∆n+ for all t ∈ [T ]
φt(gi1 , . . . , git) = git ψt(gi1 , . . . , git) = I (AP-SGD)
Significant improvements in the convergence rate of the algorithm can be obtained by cleverly choosing and computing such probabilities that in turn enables the algorithm to use data in a more efficient manner Stich et al. (2017). Fixed importance sampling is the case when p̂t = p for all t ∈ [T ]. Adaptive Moments Methods. Duchi et al. propelled interest and research on adaptive algorithms. In their work they noticed that SGD lacked good convergence behavior in sparse settings, and proposed a family of algorithms that allowed the methods to dynamically incorporate information about the geometry of the data Duchi et al. (2011). Following huge gains obtained with ADAGRAD, the deep learning community proposed variants based on exponential moving average functions for ψt like ADADELTA, RMSPROP, ADAM and most recently AMSGRAD (Zeiler (2012); Tieleman & Hinton (2012); Kingma & Ba (2014); Reddi et al. (2018)).
The first algorithm ADAGRAD is obtained by the following proximal functions:
αt = 1/ √ t pit = 1/n for all t ∈ [T ], i ∈ [n]
φt(gi1 , . . . , git) = git
ψt(gi1 , . . . , git) = 1
t diag(Σtτ=1g 2 iτ )
(ADAGRAD)
The ADAM/AMSGRAD algorithm is obtained by setting:
αt = 1/ √ t pit = 1/n ∀t ∈ [T ], i ∈ [n]
φt(gi1 , . . . , git) = Σ t τ=1β1(t)τgiτ
vit = (1− β2)Σtτ=1βt−τ2 g2iτ v̂it = max(v̂it−1 ,vit) ψt(gi1 , . . . , git) = diag (v̂it)
(ADAM/AMSGRAD)
Fortunately a very simple and computationally efficient way to implement ADAM is given by a recursion. RMSPROP is the particular case of ADAM when β1 = 0 and without maximum operator for the second moments vector, while ADAM is recovered without the maximum operator.
Double Adaptive Methods. The key idea behind both the adaptive probabilities methods and adaptive moment methods is the efficient use of the information available in the training data to improve the convergence of the algorithms. In the case of adaptive moment methods the diagonal approximations of the Hessian matrix use the information about the geometry of the problem while the adaptive sampling methods, the probabilities p̂it , prioritize the examples with the highest impact on the learning progress. As these improvements rely on complementary sources of information we can combine them into a general framework described by the double adaptive methods in Algorithm 1.
To analyze the theoretical improvement guarantees of the double adaptive methods we first we extend the adaptive moments convergence guarantees to the stochastic case with uniform sampling and then we compare them to the convergence guarantees using optimal probabilities.

heading: 3 CONVERGENCE ANALYSIS

heading: 3.1 CONVERGENCE OF ADAPTIVE MOMENTS METHODS
text: We first provide a regret bound of ADAM for weakly convex objectives with uniform probabilities adapting the arguments in Reddi et al. (2018) and Kingma & Ba (2014). Then we extend these results to the adaptive probabilities case.
Theorem 1. Let {θt}Tt=1 be the sequence obtained with ADAM, then the regret bound is:
R(ADAM) ≤ T∑ t=1
1 2αt(1− β1t) En [ ||V̂ 1/4it (θt − θ ∗)||2 − ||V̂ 1/4it (θt+1 − θ ∗)||2 ] +
T∑ t=1 αt 2(1− β1t) En [ ||V̂ −1/4it mit || 2 ]
+ T∑ t=1 αtβ1t 2(1− β1t) ||V̂ −1/4t mt−1||2 + T∑ t=1 β1t 2αt(1− β1t) ||V̂ 1/4t (θt − θ∗)||2
Corollary 1.1. Following the sequence {θt}Tt=1 of ADAM with step size αt = α/ √ t, averaging
parameters β1 = β11 , β1t ≤ β1 for all t ∈ [T ], γ = β1/ √ β2 < 1 and uniform probabilities pit = 1/n. If we assume that Θ has bounded diameter D, ||∇fit(θ)||∞ ≤ G for all t ∈ [T ] and θ ∈ Θ, then the expected regret bound is:
R(ADAM) ≤ D 2 √ T 2α(1− β1) En [ ||v̂1/4iT || 2 ]
+ α √ 1 + log(T )
2(1− β1)2 √ (1− β2)(1− γ) d∑ h=1 || ¯| g |1:T,h ||
+ αGd 2α(1− β1)3 √ (1− β2)(1− γ) +
D2
2α(1− β1) T∑ t=1 √ tβT−t1 ||v̂ 1/4 t ||2

heading: 3.2 CONVERGENCE OF DOUBLE ADAPTIVE METHODS
text: Theorem 2. Let {θt}Tt=1 be a DASGRAD sequence, for a trajectory pt ∈ ∆n+ the regret bound is:
R(DASGRAD) ≤ T∑ t=1
1
2αt(1− β1t) Ep1:t
[ ||V̂ 1/4it (θt − θ ∗)||2 − ||V̂ 1/4it (θt+1 − θ ∗)||2 ] +
T∑ t=1 αt 2(1− β1t) Ep1:t [ w2it ||V̂ −1/4 it mit ||2 ]
+ T∑ t=1 αtβ1t 2(1− β1t) ||V̂ −1/4t mit−1 ||2 + T∑ t=1 β1t 2αt(1− β1t) ||V̂ 1/4t (θt − θ∗)||2
Corollary 2.1. Following the sequence {θt}Tt=1 of DASGRAD, step size αt = α/ √ t, averaging
parameters β1 = β11 , β1t ≤ β1 for all t ∈ [T ], γ = β1/ √ β2 < 1 and the optimal adaptive probabilities p̂it ∝ ||V̂ −1/4 it
mit ||. If we assume that Θ has bounded diameter D and ||∇fit(θ)||∞ ≤ G for all t ∈ [T ] and θ ∈ Θ, then the expected regret bound is:
R(DASGRAD) ≤ D 2 √ T
2α(1− β1) Ep̂1:T
[ ||v̂1/4iT || 2 ]
+ α √ 1 + log(T )
2(1− β1)2 √ (1− β2)(1− γ) d∑ h=1 || ¯| g |1:T,h || − T∑ t=1 Varn ( ||V̂ 1/4it mit || ) + αGd
2α(1− β1)3 √ (1− β2)(1− γ) +
D2
2α(1− β1) T∑ t=1 √ tβT−t1 ||v̂ 1/4 t ||2

heading: 3.3 CONVERGENCE COMPARISON
text: Adaptive moment methods can improve classical gradient descent by integrating the geometry of the problem with a diagonal approximation of the Hessian an may achieve an exponentially smaller bound for the expected regret with respect to the dimensions of the input data d, when dealing with sparse features or small gradients in general. As shown by Duchi et al. (2011) for the adaptive moment methods in the sparse setting, the potential component and error component of the expected regret of Corollary 1.1 each will satisfy:
Ep1:T [ ||v̂1/4iT || 2 ] = Ep1:T
[ d∑
h=1
v̂ 1/2 iT ,h
] √ d and
d∑ h=1 || ¯| g |1:T,h || √ dT
which in turn translates to a much better expected regret bound than O( √ dT ) for classic SGD on weakly convex objectives and sparse inputs.
In parallel to the previous improvements, the adaptive probabilities methods can further speed the convergence by allowing the algorithm to evaluate the relative importance of each data point to maximize the expected learning progress, and minimize the variance of the stochastic gradient at each step. Given the optimal adaptive probabilities the error component of the expected regret in Corollary 2.1 satisfies:
d∑ h=1 || ¯| g |1:T,h || − T∑ t=1 Varn ( ||V̂ 1/4it mit || )
d∑ h=1 || ¯| g |1:T,h ||
This shows how the optimal adaptive sampling probabilities on a convex setting can further improve the convergence rate by allowing to flexibly control the variance of the gradients.

heading: 4 DASGRAD IMPLEMENTATION
text: To obtain the optimal probabilities it is necessary to compute the norm of the gradient for each training sample at each step. Given the deep learning libraries today, this calculation renders optimal adaptive probabilities methods impractical for real applications 2. Still, for completeness of the exposition of the theoretical results we provide empirical evidence of the convergence improvements, to do it we use an approximation of the optimal algorithm from the double adaptive methods, following Algorithm 2.
Algorithm 2: DASGRAD approximation Input: θ1 ∈ Θ, functions {φt, ψt}Tt=1, frequency J for t = 1 to T do
if t mod J = 0 then Compute p̂t ∈ ∆n+ setting p̂it ∝ ||V̂ −1/4 it
mit ||+ Sample it ∼ p̂t using the segment tree Calculate git = ∇fit(θt) and ŵit = (1/n)/p̂it mt = β1tmt−1 + (1− β1t)gt and vt = β2vt−1 + (1− β2)g2t v̂t = max(v̂t−1,vt) and V̂t = diag(v̂t) θ̂t+1 = θt − αtŵit V̂ −1/2 it
mit θt+1 = ΠΘ,V̂ 1/2it (θ̂t+1)
2Current dynamical computational graph libraries compute the average gradient batches by default and available workarounds are still slow. See https://github.com/pytorch/pytorch/issues/7786 and https://github.com/tensorflow/tensorflow/issues/4897.

heading: 5 EMPIRICAL RESULTS
text: In this section we provide empirical evidence of the convergence rates on classification problems using logistic regression and deep neural networks, using ADAM, AMSGRAD, and DASGRAD.
Logistic Regression: For the convex setting we solve two classification problems with L2 regularization. For the non sparse feature experiment we use the MNIST digit dataset, which is composed of 60, 000 images of 28×28 hand written digits. For the sparse feature experiment we use the IMDB movie rating dataset which is composed of 25, 000 highly polar movie reviews and the sentiment label for the review Maas et al. (2011).3
Neural Networks: For the non convex setting we perform one experiment, we use the CIFAR10 dataset, which is composed of 60, 000 colour images of 32 × 32 pixels labeled in 10 classes. For this multiclass classification problem we use a convolutional neural network following the SMALLCIFARNET architecture, consisting of two convolution filters combined with max pooling and local response normalization, followed by two fully connected layers of rectified linear units Krizhevsky et al. (2012). 4
3For both experiments, we use a batch of size 32, with a probability update every 10 steps, and the step size αt = α/ √ t. We set β1 = 0.9, β2 = 0.99, and choose α through a grid search. For the MNIST dataset, for all three optimizers, the optimal learning rates are α = 0.01. For the IMDB dataset, we find the optimal learning rates to be α = 0.005 for ADAM, α = 0.006 for AMSGRAD, and α = 0.02 for DASGRAD.
4For the experiment we use a batch size of 32, with a probability update every 300 steps, and step size of αt = α/ √ t. We set β1 = 0.9, β2 = 0.99, and choose α through a grid search, for which the optimal learning rate for all optimizers is α = 0.001.
From the comparison in Figure 1, we observe that in all cases the DASGRAD optimization algorithm outperforms its adaptive moment counterparts represented by ADAM and AMSGRAD, as predicted by the theoretical analysis. The improvement is more significant for the IMDB dataset than it is for the MNIST dataset. From Figure 1 we can see that DASGRAD continues to outperform ADAM and AMSGRAD in the deep learning setting. These results reinforce the previous statement that the benefits from DASGrad increase with the complexity of the data and the models.

heading: 6 DISCUSSION

heading: 6.1 CONVERGENCE IMPROVEMENTS AND VARIANCE OF GRADIENTS
text: To further explore the relationship between variance and the improvements to the convergence rate of the DASGRAD algorithm, we implemented an online centroid learning experiment. Because of the linear relationship between the features and the gradients, we are able to explicitly control their variance. For this experiment, the empirical risk and gradients will be given by Rn(θ) = 1 2n ∑n i=1 ||θ − xi||2 and ∇f(θ,xi) = θ − xi.
As we can see from Figure 2 the greater the variance of the gradients, the greater the benefit that one can obtain from an adaptive probabilities method such as DASGRAD in convex objectives, since those probabilities will prioritize the data points with the most learning potential.

heading: 6.2 FLEXIBLE CONTROL OF VARIANCE
text: Recent insights on the generalization properties of minibatch SGD for non convex objectives suggest that higher variance gradients tend to converge to flatter regions of the loss surfaces (Keskar et al. (2016)). Applications like curriculum learning that shape the learning procedure, by gradually making the task more difficult through importance sampling, may allow to maintain a higher variance of the gradients for longer steps, this combined with the previous intuitions offers an explanation of the mathematical basis of its success.
While curriculum learning is contrary to the optimal probabilities of the double adaptive methods for convex settings, the underlying principle of flexible control of the variance of the gradients operates as the mechanism behind both procedures. This observations strengthens the argument that improving our understanding of the implicit optimization techniques in this algorithms can also improve our understanding that so far has relied mostly on intuitive explanations of their success.

heading: 6.3 IMPORTANCE WEIGHT TRANSFER LEARNING
text: When the training T and test T ′ set do not share the same distribution, we may face a distribution mismatch problem. The DASGRAD algorithm is compatible with the cost re-weighting correction technique Elkan (2001); Bowyer et al. (2011) as we can set the importance weights wt for any trajectory of distributions pt, to unbias the gradients for the test distribution instead of the training.
R(DASGRAD)T ′ = T∑ t=1 EpT ′ [ fi(θt)−minθEpT ′ [fi(θ)] ] =
T∑ t=1 Ep1:t [ witfi(θt)−minθEpT ′ [fi(θ)] ] To test the generalization properties of the DASGRAD algorithm empirically, we unbalanced the MNIST training data set by reducing ninety percent the observations from the 1 and 3 digit. We set the importance weights to wit = (|Li|/m)/pit , where |Li| is the count of the label L associated with index i in test over m, the number of test samples. As we see in Figure 3 using DASGRAD with the correct importance weights has the desired generalization properties when facing a domain shift.

heading: 7 CONCLUSION
text: Capability of learning from data efficiently is a prerequisite for practical success of complex learning models across various problem settings and application contexts. We have shown how double adaptive stochastic gradient descent methods enable efficient learning in a generalizable manner, while ensuring convergence improvement. We observed that DASGRAD algorithm outperforms currently prevalent variants of adaptive moment algorithms such as ADAM and AMSGRAD overall, in the context of the number of iterations required to achieve comparable performance, under the theoretical convergence guarantees in a stochastic convex optimization setting. With empirical validation in convex and non convex settings, we have shown that the advantages of DASGrad become more prominent with the increasing complexity of data and models, and with more variance in the gradients. We have also broadened our results to demonstrate generalization properties of our approach and its extensions to transfer learning, as well as intuitive connections to other learning scenarios.

heading: A APPENDIX
text: A.1 PROOF OF THEOREM 2
The proof of Theorem 2 assumes a convex differentiable objective function f , bounded diameter for the parameters, and bounded norm of the gradients for any trajectory of probabilities pt ∈ ∆n+.
Proof. We build an upper bound of the expected regret using the convexity of the loss: f(θt)− f(θ∗) ≤ 〈 gt, θt − θ∗〉 = En [〈 git , θt − θ∗〉]
While using DASGRAD the update of the parameter will be given by the stochastic update dependent on the training example it and the current parameter θt:
θt+1 = ΠΘ,V̂ 1/2it (θ̂t+1) = ΠΘ,V̂ 1/2it
(θt − αtwitV̂ −1/2 it
mit) = arg min θ∈Θ
|| V̂ 1/4it (θt − αtwitV̂ −1/2 it mit) ||
To bound the expected regret of the algorithm, we use the fact that: θ̂t+1 − θ∗ = (θt − θ∗)− αtwitmit/ √ V̂it
||V̂ 1/4it (θ̂t+1 − θ ∗)||2 = ||V̂ 1/4it (θt − θ ∗)||2 − 2αtwit〈mit , θt − θ∗〉+ α2tw2it ||V̂ −1/4 it mit ||2
= ||V̂ 1/4it (θt − θ ∗)||2 − 2αtwit〈β1tmit−1 + (1− β1t)git , θt − θ∗〉+ α2tw2it ||V̂ −1/4 it mit ||2
We identify the first three components as the potential, the immediate cost, now with extra terms associated to the moving average, and the error.
Lemma 1. For any M ∈ Sd+ and convex feasible set Θ ⊆ Rd with the projection operator ΠΘ,M let u1 = ΠΘ,M (z1) and u2 = ΠΘ,M (z2) then:
||M1/2 (u1 − u2) || ≤ ||M1/2 (z1 − z2) ||
Taking the expectation at time t, and using the extended norm reduction property of the projections from Lemma 1 we obtain the following inequality:
Ept [ ||V̂ 1/4it (θt+1 − θ)|| 2 ∣∣∣θt ] ≤ Ept [ ||V̂ 1/4it (θt − θ∗)||2 ∣∣∣θt ]
− Ept [ 2αtwit〈β1tmit−1 + (1− β1t)git , θt − θ∗〉 ∣∣∣θt ]
+ α2tEpt [ w2it ||V̂ 1/4 it mit ||2 ∣∣∣θt ] Since wt is such that the interior product will be unbiased, then:
Ept [ ||V̂ 1/4it (θt+1 − θ)|| 2 ∣∣∣θt ] ≤ Ept [ ||V̂ 1/4it (θt − θ∗)||2 ∣∣∣θt ]
− 2αt〈β1tmt−1 + (1− β1t)gt, θt − θ∗〉 + α2tEpt [ w2it ||V̂ 1/4 it mit ||2 ∣∣∣θt ] Finally rearranging the terms, summing until time T and taking expectations:
R(DASGRAD)T ≤ T∑ t=1
1
2αt(1− β1t) Ep1:t
[ ||V̂ 1/4it (θt − θ ∗)||2 − ||V̂ 1/4it (θt+1 − θ ∗)||2 ] +
T∑ t=1 αt 2(1− β1t) Ep1:t [ w2it ||V̂ −1/4 it mit ||2 ]
+ T∑ t=1 β1t 2(1− β1t) αt||V̂ −1/4t mt−1||2 + T∑ t=1 β1t 2αt(1− β1t) ||V̂ 1/4t (θt − θ∗)||2
(1)
Last line is Cauchy-Schwarz and Young’s inequality applied to the inner product of the extra terms associated with the moving average in the immediate cost.
A.2 PROOF OF COROLLARY 2.1
Proof. The proof of Corollary 2 is in the line of the improvements provided by Reddi et al. to the convergence proof of Kingma & Ba for ADAM, we adapt the arguments to the stochastic case. We assess separately each component of the expected regret from Equation 1.
Lemma 2 addresses the potential, Lemma 3 the error, and Lemma 6 and Lemma 4 the moving average terms. The proof of Corollary 2.1 is a consequence of all the previous Lemmas using the optimal probabilities while Corollary 1.1 is the case with uniform probabilities. Following the sequence {θt}Tt=1 of DASGRAD, with step size αt = α/ √ t, averaging parameters
β1 = β11 and β1t ≤ β1 for all t ∈ [T ] and γ = β1/ √ β2 < 1. and bounded diameter D for Θ and ||∇fit(θ)||∞ ≤ G for all t ∈ [T ] and θ ∈ Θ. Lemma 2. From Equation 1 the potential component will satisfy: T∑ t=1 1 2αt(1− β1t) Ep1:t [ ||V̂ 1/4it (θt − θ ∗)||2 − ||V̂ 1/4it (θt+1 − θ ∗)||2 ] ≤ D 2 √ T 2α(1− β1) Ep1:T [ ||v̂1/4iT || 2 ]
Proof One can decompose the potential in the following manner: T∑ t=1 1 2αt(1− β1t) Ep1:t [ ||V̂ 1/4it (θt − θ ∗)||2 − ||V̂ 1/4it (θt+1 − θ ∗)||2 ] ≤
1
2α1(1− β1) Ep1
[ ||V̂ 1/4i1 (θ1 − θ ∗)||2 ] − 1
2αT (1− β1) Ep1:T
[ ||V̂ 1/4iT (θT+1 − θ ∗)||2 ]
+ 1
2(1− β1) T∑ t=2 ( 1 αt Ep1:t [ ||V̂ 1/4it (θt − θ ∗)||2 ] − 1 αt−1 Ep1:t−1 [ ||V̂ 1/4it−1(θt−1 − θ ∗)||2 ])
≤ 1 2α1(1− β1)
Ep1 [ ||v̂1/4i1 D 1|| 2 ]
+ 1
2(1− β1) T∑ t=2 ( 1 αt Ep1:t [ ||v̂1/4it D 1|| 2 ] − 1 αt−1 Ep1:t−1 [ ||v̂1/4it−1 D 1|| 2 ])
≤ D 2
2(1− β1)
( 1
α1 Ep1
[ ||v̂i1 ||2 ] + T∑ t=2 ( 1 αt − 1 αt−1 ) Ept [ ||v̂it ||2 ])
= D2
2αT (1− β1) Ep1:T
[ ||v̂1/4iT || 2 ] = D2 √ T
2α(1− β1) Ep1:T
[ ||v̂1/4iT || 2 ]
The first inequality comes from rearranging and the definition of β1t , the second inequality comes from the bounded diameter assumption applied to each entry of θt − θ∗ and using the Hadamard’s product to represent the original matrix multiplication, the third inequality5 comes from the definition of v̂it = max(v̂it−1 ,vit), the last equality comes from the property of the telescopic sequence. This completes the proof of Lemma 2.
5The third inequality is of particular importance since Reddi et al. showed that it is one of the main flaws in the convergence analysis of ADAM and RMSPROP, and provided a simple fix to the adaptive moment methods that guarantees the non increasing property needed to achieve the telescopic sequence upper bound.
Lemma 3. From Equation 1 the error component, once evaluated in the optimal probabilities p̂t will satisfy:
Ep̂t [ ŵ2it ||V̂ 1/4 it mit ||2 ∣∣∣θt ] = En [ ||V̂ 1/4it mit ||2 ∣∣∣θt ]− Varn (||V̂ 1/4it mit ||) Proof Creating a lower bound with Cauchy-Schwarz and showing that it is achievable with the optimal probabilities p̂it ∝ ||V̂ 1/4 it mit ||.
Lemma 4. The first component of the extra terms associated with the moving average in Equation 1 will satisfy:
T∑ t=1 αtβ1t 2αt(1− β1t) ||V̂ −1/4t mt−1||2 ≤ αGd 2α(1− β1)3 √ (1− β2)(1− γ)
Proof Following very similar arguments as those from Lemma 6, we can get:
T∑ t=1 αtβ1t 2αt(1− β1t) ||V̂ −1/4t mt−1||2 ≤ α 2(1− β1)2 √ (1β2)(1− γ) T∑ t=1 βT−t1 ||gt||1
≤ α 2(1− β1)2 √ (1β2)(1− γ) T∑ t=1 βT−t1 ||G 1||1 ≤ αGd 2α(1− β1)3 √ (1− β2)(1− γ)
This completes the proof of Lemma 4.
Lemma 5. To finish the second component of the extra terms associated with the moving average in Equation 1, will satisfy:
T∑ t=1 β1t 2αt(1− β1t) ||V̂ 1/4t (θt − θ∗)||2 ≤ D2 2α(1− β1) T∑ t=1 √ tβT−t1 ||v̂ 1/4 t ||2
Proof
T∑ t=1 β1t 2αt(1− β1t) ||V̂ 1/4t (θt − θ∗)||2 ≤ T∑ t=1 β1t 2αt(1− β1t) ||v̂1/4t D 1||2
= D2
2α T∑ t=1 √ t β1t (1− β1t) ||v̂1/4t ||2
≤ D 2
2α(1− β1) T∑ t=1 √ tβT−t1 ||v̂ 1/4 t ||2
This completes the proof of Lemma 5.
Lemma 6. From Equation 1 the error component, once evaluated in the optimal probabilities p̂t, and the total error will satisfy that:
T∑ t=1 αt 2(1− β1t) Ep̂t [ ŵ2it ||V̂ 1/4 it mit ||2 ∣∣∣θt ] ≤ α √ 1 + log(T )
2(1− β1)2 √ (1− β2)(1− γ) d∑ h=1 || ¯| g |1:T,h || − T∑ t=1 Varn ( ||V̂ 1/4it mit || )
Proof For Lemma 6 we follow Kingma & Ba, for every element at time t of the error component:
αt 2(1-β1t)
En [ ||V̂ −1/4it mit || 2 ] ≤ αt 2(1-β1t) En [ ||V −1/4it mit || 2 ]
= αt 2(1-β1t) En [ ||Σtτ=1β1(t)τgiτ ||2√ vit ] =
αt 2(1-β1t)
En [ ||Σtτ=1β1(t)1/2τ β1(t)1/2τ giτ ||2√
viτ ] ≤ αt
2(1-β1t) En
[( t∑
τ=1
β1(t)τ
)( t∑
τ=1
β1(t)τ ||giτ ||2√ viτ
)]
≤ αt 2(1− β1) En
[( t∑
τ=1
βt−τ1
)( t∑
τ=1
βt−τ1 ||giτ ||2√ viτ
)]
≤ αt 2(1− β1)2 En  t∑ τ=1 βt−τ1 ||giτ ||2√
(1− β2)Σtτ=1βt−τ2 g2iτ  ≤ αt
2(1− β1)2 √ (1− β2) En  t∑ τ=1 βt−τ1√ βt−τ2 ||giτ ||2 |giτ |  = α
2(1− β1)2 √ (1− β2) En [ 1√ t ( t∑
τ=1
γt−τ ||giτ ||1
)]
The first inequality follows the definition of the auxiliary vectors v̂t = max(v̂t−1, vt), the second inequality comes from the non negativity of β1(t)τ . The third and fourth inequality comes from the decreasing property β1 ≤ β11 and β1t ≤ β11 and the property of the geometric sequence. The fifth inequality comes from the non negativity of β2 and ||giτ ||2, the last equality uses the definition of the step size. Using induction one can show that:
T∑ t=1 αt 2(1− β1t) En [ ||V̂ 1/4it mit || 2 ] ≤ T∑ t=1
α 2(1− β1)2 √ (1− β2) En [( T∑ τ=t γt−τ√ τ ||giτ ||1 )] (2)
Continuing the proof of Lemma 6, let k = α 2(1−β1)2 √ (1−β2) , from Equation 2 we have that: T∑ t=1 αt 2(1− β1t) En [ ||V 1/4it mit || 2 ] ≤ T∑ t=1 k En [ 1√ t ( T∑ τ=t γt−τ ||giτ ||1 )]
= k ( T∑ t=1 n∑ it=1 1 n ||git ||1 ( T∑ τ=t γt−τ√ τ ))
≤ k ( T∑ t=1 n∑ it=1 1 n ||git ||1 ( T∑ τ=t γt−τ√ t ))
= k ( T∑ t=1 n∑ it=1 1 n ||git ||1 1√ t ( T∑ τ=t γt−τ ))
≤ k (1− γ) ( T∑ t=1 ( n∑
it=1
1 n ||git ||1 )( 1√ t ))
= k
(1− γ) d∑ h=1 ( T∑ t=1 ( n∑ it=1 1 n |git,h| )( 1√ t ))
≤ k (1− γ) d∑ h=1
 √√√√ T∑
t=1
( n∑
it=1
1 n |git,h| )2√√√√ T∑ t 1 t  ≤ k √ 1 + log(T )
(1− γ)
d∑ h=1 √√√√ T∑ t=1 ( n∑ it=1 1 n |git,h| )2 The first equality comes from a change of indexes, the second inequality is an upper bound for the arithmetic sequence that begins at t, the third inequality is an upper bound for the geometric sequence, the fourth inequality comes is an application of Cauchy-Schwarz inequality, finally the fifth inequality is an upper bound for the arithmetic sequence.
T∑ t=1 Ep̂t [ ŵ2it ||V̂ 1/4 it mit ||2 ∣∣∣θt ] = T∑ t=1 En [ ||V̂ 1/4it mit || 2 ∣∣∣θt ]− T∑ t=1 Varn ( ||V̂ 1/4it mit || ) ≤ α √ 1 + log(T )
2(1− β1)2 √ (1− β2)(1− γ) d∑ h=1 || ¯| g |1:T,h || − T∑ t=1 Varn ( ||V̂ 1/4it mit || ) With the optimal probabilities p̂it , we complete the proof of Lemma 6.
Finally we can combine the results from Lemma 2 to 5 and obtain the following bound for the expected regret of the general double adaptive algorithms:
Corollary 2.1
R(DASGRAD) ≤ D 2 √ T
2α(1− β1) Ep̂1:T
[ ||v̂1/4iT || 2 ]
+ α √ 1 + log(T )
2(1− β1)2 √ (1− β2)(1− γ) d∑ h=1 || ¯| g |1:T,h || − T∑ t=1 Varn ( ||V̂ 1/4it mit || ) + αGd
2α(1− β1)3 √ (1− β2)(1− γ) +
D2
2α(1− β1) T∑ t=1 √ tβT−t1 ||v̂ 1/4 t ||2

Review summaries:
In this paper, the doubly adaptive stochastic gradient method (DASGrad) is introduced via augmenting adaptive moment methods with adaptive (as opposed to uniform) probabilities for data sampling. The convergence of the proposed method is analyzed in terms of regret bound and is compared to similar results for ADAM. The method is validated with experiments on both convex and non-convex objectives as well as in applications to transfer learning.

In the paper, the authors propose a general form that covers most stochastic gradient methods so far, e.g. stochastic gradient descent, Adam,  or adaptive probabilities methods. Then, they also provide a convergence analysis of convex problems.  In the experiments, they compared the proposed DASGRAD method with Adam, AMSGrad or SGD. Experimental results show that the proposed method converges faster than compared methods.  Following are my concerns: