Title: DASGRAD: DOUBLE ADAPTIVE STOCHASTIC GRADIENT

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.

1. INTRODUCTION AND MOTIVATION:

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 ADA-GRAD, 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.

2. ADAPTIVE GRADIENT METHODS:

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 ∈ R d and M ∈ S d + , then the multiplication of vector a by the inverse of M will be M -1 a = a/M . Let √ a be the element-wise square root of vector a, a 2 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] . For the iterative stochastic optimization algorithm A, let i t be a sampled index i at step t drawn from the training set indices [n], with i t ∼ p t and

Let T = {(x i , y i )} n i=1 be a training set; let f : Θ × X × Y → R be a differentiable

p t ∈ ∆ n + = {p ∈ R n : p i > 0 Σ i p i = 1}. We denote the evaluated risk f (θ, x i , y i ) = f i (θ), the complete gradient ∇f (θ t ) = 1 n Σ it ∇f it (θ t

) and the stochastic gradient ∇f it (θ t ), analogous a full descent direction m t = 1 n Σ it m it and a stochastic descent direction m it .

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

||∇f i (θ)|| ∞ ≤ 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 pt ∈ ∆ n + , obtains a training example i t ∼ pt and its importance weights ŵit = (1/n)/p it , then updates its parameters θ t ∈ Θ using the available data at time t and the importance weights ŵ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 E n [ f i (θ t ) -min θ E n [f i (θ)] ]

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} T t=1 , functions {φt, ψt} T t=1 for t = 1 to T do Choose pt ∈ ∆ n + , and sample it ∼ pt Calculate gi t = ∇fi t (θt) and ŵi t = (1/n)/pi t mi t = φt (gi 1 , . . . , gi t ) and Vi t = ψt (gi 1 , . . . , gi t ) θt+1 = θt -αt ŵi t V -1/2 i t mi t θt+1 = Π Θ, V 1/2 i t ( θ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 → R d , and approximating the Hessian matrix with the functions ψ t : Θ t → S d + .

Adaptive Probabilities Methods. The classic stochastic gradient descent algorithm is recovered with the following step size, sampling probabilities and functions:

α t = α/ √ t p it = 1/n for all t ∈ [T ], i ∈ [n] φ t (g i1 , . . . , g it ) = g it ψ t (g i1 , . . . , g it ) = I (SGD)

Adaptive probabilities methods can be obtained simply by allowing the algorithm to choose a different probability pt at any time t:

α t = α/ √ t pt ∈ ∆ n + for all t ∈ [T ] φ t (g i1 , . . . , g it ) = g it ψ t (g i1 , . . . , g it ) = 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 pt = p for all t ∈ [T ].

Adaptive Moments Methods. The first algorithm ADAGRAD is obtained by the following proximal functions:

α t = 1/ √ t p it = 1/n for all t ∈ [T ], i ∈ [n] φ t (g i1 , . . . , g it ) = g it ψ t (g i1 , . . . , g it ) = 1 t diag(Σ t τ =1 g 2 iτ ) (ADAGRAD)

The ADAM/AMSGRAD algorithm is obtained by setting:

α t = 1/ √ t p it = 1/n ∀t ∈ [T ], i ∈ [n] φ t (g i1 , . . . , g it ) = Σ t τ =1 β1(t)τ g iτ v it = (1 -β2)Σ t τ =1 β t-τ 2 g 2 iτ vit = max(v it-1 , v it ) ψ t (g i1 , . . . , g it ) = 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 pit , 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.

3. CONVERGENCE ANALYSIS:



3.1. CONVERGENCE OF ADAPTIVE MOMENTS METHODS:

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 } T t=1 be the sequence obtained with ADAM, then the regret bound is:

R(ADAM) ≤ T t=1 1 2α t (1 -β 1t ) E n || V 1/4 it (θ t -θ * )|| 2 -|| V 1/4 it (θ t+1 -θ * )|| 2 + T t=1 α t 2(1 -β 1t ) E n || V -1/4 it m it || 2 + T t=1 α t β 1t 2(1 -β 1t ) || V -1/4 t m t-1 || 2 + T t=1 β 1t 2α t (1 -β 1t ) || V 1/4 t (θ t -θ * )|| 2 Corollary 1.1. Following the sequence {θ t } T t=1 of ADAM with step size α t = α/ √ t, averaging parameters β 1 = β 11 , β 1t ≤ β 1 for all t ∈ [T ], γ = β 1 / √ β 2 < 1 and uniform probabilities p it = 1/n. If we assume that Θ has bounded diameter D, ||∇f it (θ)|| ∞ ≤ G for all t ∈ [T ] and θ ∈ Θ, then the expected regret bound is: R(ADAM) ≤ D 2 √ T 2α(1 -β 1 ) E n ||v 1/4 i T || 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 -γ) + D 2 2α(1 -β 1 ) T t=1 √ tβ T -t 1 ||v 1/4 t || 2

3.2. CONVERGENCE OF DOUBLE ADAPTIVE METHODS:

Theorem 2. Let {θ t } T t=1 be a DASGRAD sequence, for a trajectory p t ∈ ∆ n + the regret bound is:

R(DASGRAD) ≤ T t=1 1 2α t (1 -β 1t ) E p1:t || V 1/4 it (θ t -θ * )|| 2 -|| V 1/4 it (θ t+1 -θ * )|| 2 + T t=1 α t 2(1 -β 1t ) E p1:t w 2 it || V -1/4 it m it || 2 + T t=1 α t β 1t 2(1 -β 1t ) || V -1/4 t m it-1 || 2 + T t=1 β 1t 2α t (1 -β 1t ) || V 1/4 t (θ t -θ * )|| 2 Corollary 2.1. Following the sequence {θ t } T t=1 of DASGRAD, step size α t = α/ √ t, averaging parameters β 1 = β 11 , β 1t ≤ β 1 for all t ∈ [T ], γ = β 1 / √ β 2 < 1 and the optimal adaptive proba- bilities pit ∝ || V -1/4 it m it ||.

If we assume that Θ has bounded diameter D and ||∇f it (θ)|| ∞ ≤ G for all t ∈ [T ] and θ ∈ Θ, then the expected regret bound is:

R(DASGRAD) ≤ D 2 √ T 2α(1 -β 1 ) E p1:T ||v 1/4 i T || 2 + α 1 + log(T ) 2(1 -β 1 ) 2 (1 -β 2 )(1 -γ) d h=1 || | g | 1:T,h || - T t=1 Var n || V 1/4 it m it || + αGd 2α(1 -β 1 ) 3 (1 -β 2 )(1 -γ) + D 2 2α(1 -β 1 ) T t=1 √ tβ T -t 1 ||v 1/4 t || 2

3.3. CONVERGENCE COMPARISON:

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:

E p 1:T ||v 1/4 i T || 2 = E p 1:T d h=1 v1/2 i T ,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 Var n || V 1/4 it m it || 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.

4. DASGRAD IMPLEMENTATION:

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 applications2 . 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} T t=1 , frequency J for t = 1 to T do if t mod J = 0 then Compute pt ∈ ∆ n + setting pi t ∝ || V -1/4 i t mi t || + Sample it ∼ pt using the segment tree Calculate gi t = ∇fi t (θt) and ŵi t = (1/n)/pi t mt = β1tmt-1 + (1 -β1t)gt and vt = β2vt-1 + (1 -β2)g 2 t vt = max(vt-1, vt) and Vt = diag(vt) θt+1 = θt -αt ŵi t V -1/2 i t mi t θt+1 = Π Θ, V 1/2 i t ( θt+1)

5. EMPIRICAL RESULTS:

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 SMALL-CIFARNET 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 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.

6. DISCUSSION:



6.1. CONVERGENCE IMPROVEMENTS AND VARIANCE OF GRADIENTS:

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

R n (θ) = 1 2n n i=1 ||θ -x i || 2 and ∇f (θ, x i ) = θ -x i .

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.

Figure 2 : Trajectories of 100 random seeds, for the online centroid learning problem with different variance for the features. Enhanced improvements of adaptive methods with higher variance of the gradients.

6.2. FLEXIBLE CONTROL OF VARIANCE:

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.

Under review as a conference paper at ICLR 2020

6.3. IMPORTANCE WEIGHT TRANSFER LEARNING:

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 w t for any trajectory of distributions p t , to unbias the gradients for the test distribution instead of the training.

R(DASGRAD):

T = T t=1 E p T f i (θ t ) -min θ E p T [f i (θ)] = T t=1 E p1:t w it f i (θ t ) -min θ E p T [f i (θ)]

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 w it = (|L i |/m)/p it , where |L i | 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. 

7. CONCLUSION:

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.

A APPENDIX 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 p t ∈ ∆ n + .

Proof. We build an upper bound of the expected regret using the convexity of the loss:

f (θ t ) -f (θ * ) ≤ g t , θ t -θ * = E n [ g it , θ t -θ * ]

While using DASGRAD the update of the parameter will be given by the stochastic update dependent on the training example i t and the current parameter θ t :

θ t+1 = Π Θ, V 1/2 i t ( θt+1 ) = Π Θ, V 1/2 i t (θ t -α t w it V -1/2 it m it ) = arg min θ∈Θ || V 1/4 it (θ t -α t w it V -1/2 it m it ) ||

To bound the expected regret of the algorithm, we use the fact that:

θt+1 -θ * = (θ t -θ * ) -α t w it m it / Vit || V 1/4 it ( θt+1 -θ * )|| 2 = || V 1/4 it (θ t -θ * )|| 2 -2α t w it m it , θ t -θ * + α 2 t w 2 it || V -1/4 it m it || 2 = || V 1/4 it (θ t -θ * )|| 2 -2α t w it β 1t m it-1 + (1 -β 1t )g it , θ t -θ * + α 2 t w 2 it || V -1/4 it m it || 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 ∈ S d + and convex feasible set Θ ⊆ R d with the projection operator Π Θ,M let u 1 = Π Θ,M (z 1 ) and u 2 = Π Θ,M (z 2 ) then:

||M 1/2 (u 1 -u 2 ) || ≤ ||M 1/2 (z 1 -z 2 ) ||

Taking the expectation at time t, and using the extended norm reduction property of the projections from Lemma 1 we obtain the following inequality:

E pt || V 1/4 it (θ t+1 -θ)|| 2 θ t ≤ E pt || V 1/4 it (θ t -θ * )|| 2 θ t -E pt 2α t w it β 1t m it-1 + (1 -β 1t )g it , θ t -θ * θ t + α 2 t E pt w 2 it || V 1/4 it m it || 2 θ t

Since w t is such that the interior product will be unbiased, then:

E pt || V 1/4 it (θ t+1 -θ)|| 2 θ t ≤ E pt || V 1/4 it (θ t -θ * )|| 2 θ t -2α t β 1t m t-1 + (1 -β 1t )g t , θ t -θ * + α 2 t E pt w 2 it || V 1/4 it m it || 2 θ t

Finally rearranging the terms, summing until time T and taking expectations:

R(DASGRAD) T ≤ T t=1 1 2α t (1 -β 1t ) E p1:t || V 1/4 it (θ t -θ * )|| 2 -|| V 1/4 it (θ t+1 -θ * )|| 2 + T t=1 α t 2(1 -β 1t ) E p1:t w 2 it || V -1/4 it m it || 2 + T t=1 β 1t 2(1 -β 1t ) α t || V -1/4 t m t-1 || 2 + T t=1 β 1t 2α t (1 -β 1t ) || V 1/4 t (θ 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 } T t=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 ||∇f it (θ)|| ∞ ≤ G for all t ∈ [T ] and θ ∈ Θ.

Lemma 2. From Equation 1 the potential component will satisfy:

T t=1 1 2α t (1 -β 1t ) E p1:t || V 1/4 it (θ t -θ * )|| 2 -|| V 1/4 it (θ t+1 -θ * )|| 2 ≤ D 2 √ T 2α(1 -β 1 ) E p 1:T ||v 1/4 i T || 2

Proof One can decompose the potential in the following manner:

T t=1 1 2α t (1 -β 1t ) E p1:t || V 1/4 it (θ t -θ * )|| 2 -|| V 1/4 it (θ t+1 -θ * )|| 2 ≤ 1 2α 1 (1 -β 1 ) E p1 || V 1/4 i1 (θ 1 -θ * )|| 2 - 1 2α T (1 -β 1 ) E p 1:T || V 1/4 i T (θ T +1 -θ * )|| 2 + 1 2(1 -β 1 ) T t=2 1 α t E p1:t || V 1/4 it (θ t -θ * )|| 2 - 1 α t-1 E p1:t-1 || V 1/4 it-1 (θ t-1 -θ * )|| 2 ≤ 1 2α 1 (1 -β 1 ) E p1 ||v 1/4 i1 D 1|| 2 + 1 2(1 -β 1 ) T t=2 1 α t E p1:t ||v 1/4 it D 1|| 2 - 1 α t-1 E p1:t-1 ||v 1/4 it-1 D 1|| 2 ≤ D 2 2(1 -β 1 ) 1 α 1 E p1 ||v i1 || 2 + T t=2 1 α t - 1 α t-1 E pt ||v it || 2 = D 2 2α T (1 -β 1 ) E p 1:T ||v 1/4 i T || 2 = D 2 √ T 2α(1 -β 1 ) E p 1:T ||v 1/4 i T || 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 vit = max(v it-1 , v it ), the last equality comes from the property of the telescopic sequence. This completes the proof of Lemma 2.

Lemma 3. From Equation 1 the error component, once evaluated in the optimal probabilities pt will satisfy:

E pt ŵ2 it || V 1/4 it m it || 2 θ t = E n || V 1/4 it m it || 2 θ t -Var n || V 1/4 it m it ||

Proof:

Creating a lower bound with Cauchy-Schwarz and showing that it is achievable with the optimal probabilities pit ∝ || V 1/4 it m it ||. Lemma 4. The first component of the extra terms associated with the moving average in Equation 1will satisfy:

T t=1 α t β 1t 2α t (1 -β 1t ) || V -1/4 t m t-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/4 t m t-1 || 2 ≤ α 2(1 -β 1 ) 2 (1β 2 )(1 -γ) T t=1 β T -t 1 ||g t || 1 ≤ α 2(1 -β 1 ) 2 (1β 2 )(1 -γ) T t=1 β T -t 1 ||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/4 t (θ t -θ * )|| 2 ≤ D 2 2α(1 -β 1 ) T t=1 √ tβ T -t 1 ||v 1/4 t || 2 Proof T t=1 β 1t 2α t (1 -β 1t ) || V 1/4 t (θ t -θ * )|| 2 ≤ T t=1 β 1t 2α t (1 -β 1t ) ||v 1/4 t D 1|| 2 = D 2 2α T t=1 √ t β 1t (1 -β 1t ) ||v 1/4 t || 2 ≤ D 2 2α(1 -β 1 ) T t=1 √ tβ T -t 1 ||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 pt , and the total error will satisfy that:

T t=1 α t 2(1 -β 1t ) E pt ŵ2 it || V 1/4 it m it || 2 θ t ≤ α 1 + log(T ) 2(1 -β 1 ) 2 (1 -β 2 )(1 -γ) d h=1 || | g | 1:T,h || - T t=1 Var n || V 1/4 it m it ||

For Lemma 6 we follow Kingma & Ba, for every element at time t of the error component:

α t 2(1-β 1t ) E n || V -1/4 it m it || 2 ≤ α t 2(1-β 1t ) E n ||V -1/4 it m it || 2 = α t 2(1-β 1t ) E n ||Σ t τ =1 β1(t)τ g iτ || 2 √ v it = α t 2(1-β 1t ) E n ||Σ t τ =1 β1(t) 1/2 τ β1(t) 1/2 τ g iτ || 2 √ v iτ ≤ α t 2(1-β 1t ) E n t τ =1 β 1 (t) τ t τ =1 β 1 (t) τ ||g iτ || 2 √ v iτ ≤ α t 2(1 -β 1 ) E n t τ =1 β t-τ 1 t τ =1 β t-τ 1 ||g iτ || 2 √ v iτ ≤ α t 2(1 -β 1 ) 2 E n     t τ =1 β t-τ 1 ||g iτ || 2 (1 -β2)Σ t τ =1 β t-τ 2 g 2 iτ     ≤ α t 2(1 -β 1 ) 2 (1 -β 2 ) E n     t τ =1 β t-τ 1 β t-τ 2 ||g iτ || 2 |g iτ |     = α 2(1 -β 1 ) 2 (1 -β 2 ) E n 1 √ t t τ =1 γ t-τ ||g iτ || 1

The first inequality follows the definition of the auxiliary vectors vt = max(v t-1 , v t ), 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 ||g iτ || 2 , the last equality uses the definition of the step size. Using induction one can show that:

T t=1 α t 2(1 -β 1t ) E n || V 1/4 it m it || 2 ≤ T t=1 α 2(1 -β 1 ) 2 (1 -β 2 ) E n T τ =t γ t-τ √ τ ||g iτ || 1 (2)

Continuing the proof of Lemma 6, let k = α 2(1-β1) 2 √

(1-β2)

, from Equation 2we have that:

T t=1 α t 2(1 -β 1t ) E n ||V 1/4 it m it || 2 ≤ T t=1 k E n 1 √ t T τ =t γ t-τ ||g iτ || 1 = k T t=1 n it=1 1 n ||g it || 1 T τ =t γ t-τ √ τ ≤ k T t=1 n it=1 1 n ||g it || 1 T τ =t γ t-τ √ t = k T t=1 n it=1 1 n ||g it || 1 1 √ t T τ =t γ t-τ ≤ k (1 -γ) T t=1 n it=1 1 n ||g it || 1 1 √ t = k (1 -γ) d h=1 T t=1 n it=1 1 n |g it,h | 1 √ t ≤ k (1 -γ) d h=1   T t=1 n it=1 1 n |g it,h | 2 T t 1 t   ≤ k 1 + log(T ) (1 -γ) d h=1 T t=1 n it=1 1 n |g it,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

E pt ŵ2 it || V 1/4 it m it || 2 θ t = T t=1 E n || V 1/4 it m it || 2 θ t - T t=1 Var n || V 1/4 it m it || ≤ α 1 + log(T ) 2(1 -β 1 ) 2 (1 -β 2 )(1 -γ) d h=1 || | g | 1:T,h || - T t=1 Var n || V 1/4 it m it ||

With the optimal probabilities pit , 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 ) E p1:T ||v 1/4 i T || 2 + α 1 + log(T ) 2(1 -β 1 ) 2 (1 -β 2 )(1 -γ) d h=1 || | g | 1:T,h || - T t=1 Var n || V 1/4 it m it || + αGd 2α(1 -β 1 ) 3 (1 -β 2 )(1 -γ) + D 2 2α(1 -β 1 ) T t=1 √ tβ T -t 1 ||v 1/4 t || 2

:

The 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.

Current 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.

For 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.

For 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.

The 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.

Figures and Tables:

function that represents the empirical risk of an agent over T for the parameters θ ∈ Θ, with Θ ⊆ R d a convex feasible set of parameters; let S d + the set of positive definite matrices in R d×d , for a given matrix M ∈ S d + and parameter θ ∈ Θ; let Π Θ,M be the projection operator over the feasible domain defined by Π Θ,M (θ ) = arg min θ∈Θ ||M 1/2 (θ -θ )||. 1

Figure 1: Trajectories in convex and deep learning settings. First row 100 logistic regressions on MNIST, second row 100 logistic regressions on IMDB, third row 10 convolutional neural networks on CIFAR10. We show the mean over the trajectories for training loss (left), training accuracy (center), and the accuracy improvement of DASGRAD with respect to AMSGRAD and ADAM with 95% confidence intervals (right).

Figure 3: Trajectories of 20 random seeds for 2,000 iterations in convex optimization settings. Multiclass logistic regression on unbalanced MNIST dataset. We show the mean over 20 trajectories of training loss (left), training accuracy (center), and the improvement in accuracy of DASGrad with respect to AMSGRAD and ADAM with a 95% confidence interval (right)

Duchi et al. propelled interest and research on adaptive algorithms.

Table content: <table><tr><td>In their work they noticed that SGD lacked good convergence behavior in sparse settings, and pro-</td></tr><tr><td>posed a family of algorithms that allowed the methods to dynamically incorporate information about</td></tr><tr><td>the geometry of the data Duchi et al. (2011). Following huge gains obtained with ADAGRAD, the</td></tr><tr><td>deep learning community proposed variants based on exponential moving average functions for ψ t</td></tr><tr><td>like ADADELTA, RMSPROP, ADAM and most recently AMSGRAD (Zeiler (2012); Tieleman &amp;</td></tr><tr><td>Hinton (2012); Kingma &amp; Ba (2014); Reddi et al. (2018)).</td></tr></table>

Peer review (iclr2020):
Summary: This paper explores the combination of adaptive moment methods and adaptive data sampling procedures for stochastic optimization. The paper presents standard analysis in the stochastic convex setting which raised some question for me (presented below). The empirical results are promising but in my opinion can be further improved through minor changes to experimental procedure. Overall: 1) There are a few instances of undefined notation. For example, in the definition of Adam/AMSGrad or (the latter I assume is the average over all datapoints?). 2) Theorem 1 is stated very informally with some notation left unexplained (e.g. V_t above or E_n[...]). Further, it is not clear to me whether the authors are proving results in the online convex optimization setting or the stochastic convex optimization setting (though, there is some equivalence between them). Finally, I am concerned by the presentation of Theorem 1 and Corollary 1.1 as it has been shown by Reddi et al. that Adam does not have bounded regret in general without algorithmic changes. In particular, bimodal gradient noise distributions can be designed such that the average Regret is unbounded (see Reddi et al. for details). While these issues can be addressed through modifications to the standard Adam algorithm I am unable to find a suitable discussion within the paper. 3) Theorem 2 introduces DASGrad which has not yet been clearly defined (Algorithm 1 depends on averaging functions of the past gradients for flexibility --- which averaging functions are being used here?). Once again, the notation Var_n appears whose definition is not clear to me. Additionally, could you provide a citation for the optimal adaptive probabilities and clearly state under which conditions these adaptive probabilities are optimal? The crux of Theorem 2 depends on the informal statements present in Section 3.3, in which it is claimed that the variance of the second order moments are sufficiently large to dominate the sum of gradient histories. I am having a hard time seeing how this would be true generally and I believe that further theoretical analysis is necessary to justify this discussion. 4) The introduction of Algorithm 2 felt like a bait-and-switch. This algorithm seems intuitively sensible and uses the same check-pointing ideas that have been introduced in recent variance reduction methods (e.g. [1]). However, this is a different algorithm which is not analyzed in this paper. Additionally, the fourth line of Algorithm 2 says to compute p_t lying in the simplex --- I believe this is a typo? Further, could you explain the introduction of epsilon in line 4. This seems unnecessary given the propto symbol but I am worried I am missing something. 5) The empirical results introduce an additional deviation from the proposed algorithm by using batch sizes of 32. Could the authors please explain how the adaptive sampling probabilities are used in this setting? (My apologies if this is obvious, I am not overly familiar with such methods). Overall I felt that the empirical results were fairly promising but some questions remained for me. The toy experiments in section 6.1 were illustrative but seem to only consider adaptive probabilities without the adaptive moments? Section 6.3 was also an interesting experimental setup which is well suited to DASGrad but I felt that the baseline comparison was unfair. DASGrad was provided with the ground-truth balance statistics in the importance weights while the baselines were trained without any correction. I would recommend that the authors explore combinations of enabling balance correction in the baseline methods (possibly through reweighting the loss according to the balance statistics) or requiring DASGrad to compute the optimal probabilities through the adaptive moments as suggested throughout the rest of the paper. Minor: - Pg 3, typo *we first we extend* References [1] Accelerating Stochastic Gradient Descent using Predictive Variance Reduction, Rie Johnson and Tong Zhang