{'fraction_non_alphanumeric': 0.05048496160083224, 'fraction_numerical': 0.01851115258697182, 'mean_word_length': 4.049281631391936, 'pattern_counts': {'":': 0, '<': 15, '<?xml version=': 0, '>': 13, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 11, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Dynamic Regret Analysis for Online Meta-Learning

The online meta-learning framework has arisen as a powerful tool for the continual lifelong learning setting. The goal for an agent is to quickly learn new tasks by drawing on prior experience, while it faces with tasks one after another. This formulation involves two levels: outer level which learns meta-learners and inner level which learns task-specific models, with only a small amount of data from the current task. While existing methods provide static regret analysis for the online meta-learning framework, we establish performance in terms of dynamic regret which handles changing environments from a global prospective. We also build off of a generalized version of the adaptive gradient methods that covers both ADAM and ADAGRAD to learn meta-learners in the outer level. We carry out our analyses in a stochastic setting, and in expectation prove a logarithmic local dynamic regret which depends explicitly on the total number of iterations T and parameters of the learner. Apart from, we also indicate high probability bounds on the convergence rates of proposed algorithm with appropriate selection of parameters, which have not been argued before.


Introduction
The ability to design systems that use prior experience to learn new skills quickly is a critical aspect of artificial intelligence problems, from robotics to pattern recognition and image classification. Meta-learning casts this as the problem of learning to learn, in which observed tasks is exploited to obtain common knowledge improving adaptation to unseen tasks. Meta-learning methods include optimization-based [1], model-based [2] and metric [3] approaches. The standard gradient-based meta-learning framework, one of the optimization-based methods, is identified as the Model-Agnostic Meta-Learning (MAML) [1], which can be widely used [4] on account of its simplicity and effectiveness. However, it presumes that the set of tasks are available together as a batch, which thereby doesn't consider the sequential setting in which the new tasks are revealed one after the other.
The online learning algorithm [5] has been shown to be a powerful tool in sequential setting in which at each round t, a learner selects a decision x t ∈ X ⊆ R d , and an adversary replies with a loss function ℓ t : X → R. The losses ℓ t are convex functions over X which is also convex and typically employed to as the decision set. Each round suffers a loss of ℓ t (x t ) against the learner, whose goal is to minimize regret described as (1) The above regret is usually viewed as static regret to highlight that the comparator is static. On the downside, the static regret may not be a suitable measure in changing environments [6], leading to growing interest in the dynamic regret [6,7,8], in which the performance of online learning is compared to a sequence of optimal solutions. The dynamic regret is recognized as where x * t ∈ argmin x∈X ℓ t (x) is an optimal solution of ℓ t (x). All aforementioned works have focused on convex loss functions to upper bound the dynamic regret in terms of certain regularity of the comparator sequence or the function sequence. Since the standard notion of regret is not a suitable measure of performance for nonconvex loss functions, the local regret are designed through the time window to smoothen the gradient of loss suffered [9]. Due to the limitation of this work to the static environments, the work of [10] introduced the notion of dynamic local regret to investigate the non-stationary environment for nonconvex loss functions using rolling weighted average of past gradients.
Nevertheless, online learning treats the entire process as a single task without any task-specific adaptation. As such, neither Meta-Learning nor Online Learning procedure alone is desirable for the continual lifelong learning scheme. To mitigate this deficiency, several methods have been proposed to merge these two approaches [11,12], in which the agent simultaneously utilizes past experiences in a sequential setting so as to learn good priors, and also adapt quickly to the current task at hand. In a follow-up work, [13] introduced a notion of local regret as the performance measure to provide the first theoretical regret analysis for online meta-learning algorithms in the nonconvex setting. While its definition of local regret makes sense for learning in the stationary environments, it is not appropriate for dynamic environments in which the properties of the predicted variable change over time in an arbitrary way due to concept drift [14]. To alleviate this issue, we extend the regret analysis of [13] to the non-stationary setting.
Choosing an ideal learning rate is pivotal issue in the nice performance of the first and second order optimization procedures. Amongst variants of stochastic gradient descent (SGD) methods, adaptive gradient methods that scale the gradient elementwise by some form of averaging of the past gradients are particularly successful in increasing the convergence speed of the algorithms. ADAGRAD [15] is the first popular method in this area. Subsequent adaptive methods, such as ADADELTA [16], RMSPROP [17], ADAM [18], and DADAM [19], preclude continual decaying of the learning rates in ADAGRAD by using the exponential moving averages of squared past gradients as the denominator of the adaptive learning rates in lieu of the arithmetic average.
Recently, a few attempts have been made on high probability results. [20] demonstrated high probability bounds for PEGASOS algorithm by virtue of Freeman's inequality. A recent study by [21] indicated a high probability analysis for Delayed ADAGRAD with momentum applied to smooth nonconvex objective functions. Different from recently developed theoretical analysis of [13], which has been focused on bounds in expectation for online meta-learning framework, we also propound high probability convergence rates to describe the performance of the proposed algorithm on single runs.
In this paper, we develop an online meta-learning algorithm which copes up with non-stationary environments where the task-environment changes dynamically. Existing online meta-learning methods have been mostly analyzed [11,13] driven by a static regret that may not be optimal in changing environments where data are evolving and the optimal decision is drifting over time. To circumvent this issue, we accomplish dynamic regret analysis for online meta-learning algorithm in the nonconvex setting. The first main result (Theorem 1) sheds the light of dynamic regret bound of the proposed online meta-learning framework, in which the first prominent adaptive gradient method, namely, ADAGRAD, are used to adjust automatically the learning rate. We establish that the regret bound is of explicit reliance on the total number of iterations T and parameters of the learner. This bound acquires a logarithmic rate under a mild regularity condition of adaptive gradient methods which matches with that of existing online meta-learning algorithms in the static environment. For the sake of generality, we extend these results to the commonly used adaptive gradient method, namely, ADAM (Theorem 2). These results postulate bounds that hold in expectation, arguably a weak guarantee in the sense that it does not rule out the error of the algorithm from bearing large variance. Besides this, it is often impossible to perform many runs of algorithm and select the best one. Thereby, it is essential to be confident that the output of a single run of the algorithm is extremely likely to characterize the guaranteed convergence rate. To this end, Theorems 3 and 4 display bounds of dynamic regret that hold with high probability for the online meta-learning framework using ADAGRAD and ADAM optimizer, respectively. To the best of our knowledge, it is the first high probability convergence guarantees for the online meta-learning framework in the nonconvex setting.
Outline. The remainder of the paper is organized as follows. Section 2 expounds the concepts of the online meta-learning framework and adaptive gradient methods. Section 3 states a detailed description of the proposed online meta-learning algorithm. Section 4 establishes theoretical guarantees with a notion of dynamic local regret in the non-stationary and nonconvex setting. Section 5 shows a high probability analysis of online meta-learning framework under assumptions on function and stochastic gradients. Section 6 presents some concluding remarks. In the supplementary material, we provide proofs for our results.

Notation
Throughout, R + and R d denote the sets of nonnegative real numbers and real coordinate space of d dimensions, respectively. For any vectors a, b ∈ R d , we use √ a to denote element-wise square root, a 2 to denote element-wise square, a/b to denote element-wise division, max(a, b) to denote element-wise maximum and a, b to denote the standard Euclidean inner product. We use · to denote the L 2 -norm. For any positive integer d, we set [d] {1, . . . , d}. Further, for any vector x t ∈ R d , x t,i denotes its i th coordinate where i ∈ [d]. Given a function ℓ : R d → R, we note ∇ℓ its gradient and ∇ i ℓ the i th component of the gradient. We assume everywhere our loss function ℓ is bounded from below and denote the infimum by ℓ * > −∞. We also let 1 denote all-ones vector. We denote by E[·] the expectation with respect to the underlying probability space. If a n and b n are positive sequences, then a n = O(b n ) means that lim sup n a n /b n < ∞, whereas a n = Ω(b n ) means that lim inf n a n /b n > 0. We write a n = Θ(b n ) if a n = O(b n ) and a n = Ω(b n ).

Preliminaries
In this section, we briefly summarize concepts of online meta-learning setting as well as adaptive gradient methods and discuss some their important properties. This section consists of two subsections.

Online Meta-Learning Framework
In Algorithm 1, each task is presented sequentially to a round, denoted by t. Then, the update of this algorithm is executed as a bi-level learning: (i) inner level and (ii) outer level (meta-learner).
In the inner level, for each new task T t , we use training data D tr t corresponding to this task to adapt metalearner x t to the current task by following some strategy U (·). Accordingly, the task-specific parameterx t is learned iteratively using D tr t based on the rule [11] x t U (x t , D tr t ) = x t − θ∇E p,q∼D tr t [ℓ(x t , p; q)], Algorithm 1 Online Meta-Learning Setup [11] 1: Input: An initial meta-learner x 1 , a loss function ℓ(·), a local adapter U (·), an online learning algorithm A 2: for t = 1, 2, . . . do 3: Encounter a new task: T t . 4: Receive training data for current task: D tr t .

5:
Adapt x t to current task:x t = U (x t , D tr t ).

6:
Receive test data for current task: D ts t . 7: where θ is the stepsize. The object of the online meta-learning algorithm is to sequentially learn metalearners that generate good task-specific parameters after adaptation. In the outer level, all task-specific adaptations gather to update the meta-learners by using the loss function. To this end, the test data D ts t will be disclosed for assessing the performance of the adapted learnerx t . The loss suffered at this round ℓ t (x t ) can then be embedded in an online learning algorithm A to update meta-learner x t . A meta-learner x t is maintained to preserve the prior knowledge learned from past rounds.
The original notion of regret in (1) enforces the learner to compete with a fixed learner across all tasks which is not meaningful as tasks are very different. To resolve this issue, [11] took into account regret of the form: which competes with any fixed meta-learner. They set forth the Follow the Meta Leader algorithm, achieving a logarithmic regret under assumption that ℓ is strongly convex function. The analysis of this work has been studied in the strongly convex case, while many problems of the current interest have a nonconvex nature. In a subsequent work, [13] developed an efficient algorithm for nonconvex online meta-learning in which the steps of the norm version of the adaptive stochastic gradient method (ADAGRAD-Norm) [22] are used to update the meta-learner at the outer level. After briefly demonstrating why the regret of the form (1) is not a feasible metric of performance to the nonconvex world, they assessed the performance via the notion of the local regret proposed by [9] as: which is an appropriate measure of stationarity (as opposed to optimality). The motivation of using slidingwindow in F , especially a large window, follows from Theorem 2.7 in [9]. On the other hand, the statistical properties of the predicted variable can be changed over time in an arbitrary way [14] by a phenomenon called concept drift. This notion, too, has recently drawn much attention, mainly owing to the need for online classification of very large, constantly changing data streams [23,24] etc. The online meta-learning framework can be utilized to sequentially learn the initial parameters of a model such that optimizing from this initialization results in fast adaptation and generalization. In the setting of non-stationary environment of the online meta-learning framework, the task T t i) varies over time, and ii) there is no prior information as for the dynamics of the task T t which in turn the optimal initialization varies over time due to a changing environment. Although non-stationary environment of the online metalearning framework has been considered in some recent works [25,26,27], its theoretical understanding in nonconvex setting is largely missing.

ADAGRAD AND ADAM FOR MINIMIZATION PROBLEMS
We deal with a unified formulation of Adagrad [15] and Adam [18], which adjusts the step size for every dimension in accordance with the geometry of the past gradients. The main objective in these methods is to solve the following minimization problem: where x is the model parameter, and ζ is an random variable following distribution P. We assume we have 0 < β 2 ≤ 1, 0 ≤ β 1 < β 2 and a non negative sequence η t+1 . We define three vectors m t+1 , v t+1 , x t+1 ∈ R d iteratively. For start points x 1 ∈ R d , m 1 = 0, and v 1 = 0, the update is [28] with g t = ∇f (x t ; ζ t ) and updates with a small constant ǫ > 0 preventing division by zero, m t+1 and v t+1 are estimates of the mean and variance of g, respectively. In practice ǫ is usually chosen sufficiently small. Taking β 1 = 0, β 2 = 1 and η t+1 = η gives the first known adaptive gradient method in machine learning, namely, ADAGRAD, which is also reduced to plain stochastic gradient descent (SGD) method when we set v t+1 = 1. Comparing with the SGD method, ADAGRAD dynamically interpolates knowledge of history gradients to adaptively change the learning rate, thereby achieving significantly better performance when the gradients are sparse, or in general small. Another state-of-the-art algorithm for training deep learning models is known as ADAM [18,29], which is a variant of the general class of ADAGRAD-type algorithms. When 0 < β 2 < 1, 0 ≤ β 1 < β 2 , and η t+1 = η(1 − β 1 ) (1 − β t+1 2 )/(1 − β 2 ), the algorithm becomes an algorithm close to ADAM. However, ADAM would be exactly recovered by setting η t+1 = η (1−β 1 ) , which complicates the proof. Recently, there has been a surge of interest to approach the analysis of these methods for nonconvex and weakly-convex optimization [30,31]. In particular, [30] argued the convergence of Adam in certain nonconvex settings and verified the effect of the mini-batch size in its convergence. Later, [31] concluded non-asymptotic rates of convergence of first and zeroth-order adaptive methods and their proximal variants for a reasonably broad class of nonsmooth and nonconvex optimization problems. More recently, [28] established a simplified and unified proof of convergence for nonconvex ADAGRAD and ADAM, improving the dependence of the iteration complexity on the momentum parameter.

5:
7: √ ǫ+v t+1 . 8: end for at each time step are calculated at their corresponding parameters and average the past w, rather than to execute w gradient calculations at their most recent parameter (x t , ξ t,t−r ); second, we exploit adaptive gradient methods that adapt a vector of per-coefficient stepsizes rather than a single stepsize depending on the norm of the gradient; third, we make use of factor α which gives a higher weight to the recent gradients so as to control time weighting and track a dynamic function; fourth, our approach builds on a generalized version of the adaptive gradient methods [28] that covers both ADAGRAD and ADAM as special cases as opposed to [13] which is largely restricted to using ADAGRAD-NORM method for achieving state-of-the-art performance.
In Algorithm 2, we also need to stipulate the stepsizes {η t+1 }, which will be discussed later. Moreover, thanks to the randomness of D ts t of the whole test-set, we focus on the stochastic setting where we can only access (unbiased) estimates of the true losses and gradients at each round. In this setting, we assume that at each round t, each call to any stochastic gradient oracle g j , j ∈ {t − w + 1, . . . , t}, brings about an i.i.d. random vector g j (x t , ξ t,j ).
We make the following additional assumption.
Assumption 2. There is σ > 0 such that for each t ∈ [T ], j ∈ {t − w + 1, . . . , t} and random variable ξ t,j ∼ P the variance of the stochastic gradient is bounded by If σ = 0, the stochastic gradient g j (x t , ξ t,j ) is identified as the exact gradient at point x t , i.e., g j (x t , ξ t,j ) = ∇ℓ j (x t ).

Convergence Analysis in Expectation
In this section, we assert our theoretical results and their consequences. The proofs are given later in the supplementary material. To evaluate the performance of online meta-learning algorithms in non-stationary environments in which the optimal meta-learners of each online loss function ℓ t corresponding to task T t can be drifted over tasks, we exploit the notion of dynamic regret introduced in [10] as Here where W w−1 r=0 α r , and ℓ t (x t ) = 0 for t ≤ 0. This can be viewed as the exponential averaging of the gradients ∇ℓ t−r at their corresponding meta-learners x t−r in lieu of the most recent meta-learner x t over a window on each task t ∈ [T ], which thereby are adapted for non-stationary environments. Indeed, this regret quantifies the objective of predicting meta-learners with small exponential averaging of the gradients. Our main results in this section (Theorems 1 and 2) prove, to the best of our knowledge, the dynamic regret bounds in expectation for online meta-learning Algorithm 1 in which the extremely popular algorithms ADAGRAD and ADAM are used as the online learning algorithm A. Having stated our theorems, we show that our results recover previous rate of the online meta-learning algorithm in stationary setting [13], which is restricted only to ADAGRAD-NORM version of adaptive gradient methods.
Our theoretical analysis is based on several assumptions regarding ℓ.
Henceforth, the symbol E t represents expectation with respect to ξ t,t−w+1 , . . . , ξ t,t conditioned on ξ 1:t−1 . It is worth noting that each∇S t,w,α (x t ) is a weighted average of w independently sampled unbiased gradient estimates with a bounded variance σ 2 . Hence, the following Lemma is made for the functioñ ∇S t,w,α (x t ). We leave proofs of the rest lemmas in the supplementary material.

Lemma 2. Suppose Assumptions 1 and 2 hold. Then for∇S
The succeeding lemma presents a bound for the size of∇ i St,w,α(xt) √ ǫ+υ t+1,i . Lemma 3. Suppose Assumptions 1 and 2 hold. Let∇ i S t,w,α (x t ) and υ t+1,i be the sequences defined in the Algorithm DTS-AG. Then, for any Equipped with these lemmas, we now state the main result.

Theorem 1. (ADAGRAD) Suppose Assumptions 1, 2 and 3 hold. Let DTS-AG be the algorithm
Here, Note that, theoretical guarantee of Theorem 1 is a bound in expectation over the randomness of stochastic gradients, and is therefore only on-average convergence guarantee.
Corollary 1. Under the same conditions stated in Theorem 1, using w ∈ Θ(T ) and α → 1 − yields a regret bound of order Corollary 1 showed that the algorithm achieved a logarithmic bound on dynamic regret with respect to any parameters v 1 , η > 0, ǫ > 0 with a choice of w ∈ Θ(T ), which in turn recovers the result of [13] on the online meta-learning in static environments.
In the sequel, we extend our results to the ADAM optimizer, while no such result is considered in previous works. To this end, we need the following lemma.
Having proven Lemma 4, we can now characterize convergence guarantees of the online meta-learning algorithm 1 in full generality.

Theorem 2. (ADAM) Suppose Assumptions 1, 2 and 3 hold. Let DTS-AG be the algorithm
for some ς > 0 and t ∈ [T ]. Then, for any δ ∈ (0, 1) and S t,w,α (x t ) in (3), with probability at least 1 − δ, the iterates x t satisfy the following bound Corollary 2. Under the same conditions stated in Theorem 2, using The theorem indicates that when leveraging ADAM optimizer, the result of Theorem 1 holds true.

Convergence Analysis with High Probability
Theorems 1 and 2 bound the expectation of a weighted average of w gradients over the randomness of stochastic gradients. Whilst these bounds can guarantee the average performance of a large number of trials of the algorithm, they cannot preclude extremely bad solutions. Aside from, towards practical applications, usually we only perform one single run of the algorithm since that the training process may take long time. Subsequently, it is crucial to acquire high probability bounds which guarantee the performance of the algorithm on single runs. To circumvent this difficulty, in this section, we in addition show high probability bounds of the convergence rate for the online meta-learning algorithm. The following further assumptions are allowed for.
[32] and [33] and [21] gave the high probability convergence guarantees under the Assumption 4. Intuitively, it results in that the tails of the noise distribution are dominated by tails of a Gaussian distribution.

Lemma 5. Suppose Assumptions 1 and 4 hold. Then, for∇S
Lemma 6. Suppose Assumptions 1 and 4 hold. Let∇ i S t,w,α (x t ) and υ t+1,i be the sequences defined in the Algorithm DTS-AG. Then, for any δ ∈ (0, 1), 0 < α < 1, w, ǫ > 0 and S t,w,α (x t ) in (3), with probability at least 1 − δ, we have With the results of Lemmas 5 and 6 in hand, we can now prove for the first time convergence of the online meta-learning framework in high probability.

Corollary 3. Under the same conditions stated in Theorem 3, using w ∈ Θ(T ) yields a regret bound of order
We next move on to prove high probability bound on the convergence rate of Algorithm 1 in full generality. To this end, we will need to establish the following lemma.
for some ς > 0 and t ∈ [T ]. Then, for any δ ∈ (0, 1) and S t,w,α (x t ) in (3), with probability at least 1 − δ, the iterates x t satisfy the following bound Here, The theorem reports that when using ADAM optimizer, the result of Theorem 3 maintains true.

Conclusion
In this paper, we extended the static regret analysis of the online meta-learning framework to the nonstationary environments in the nonconvex setting. We also propose to use a generalized version of the adaptive gradient methods that covers both ADAGRAD and ADAM to learn meta-learners in the outer level of the online meta-learning framework. Our approach enjoyed a logarithmic dynamic local regret under some mild conditions. What's more, we proved high probability bounds on the convergence rates of the online meta-learning framework, which have not been concluded before.

Supplementary Material
This supplementary material establishes the missing proofs in the paper.

Details of Section 4 PROOF OF LEMMA 2
Lemma. Suppose Assumptions 1 and 2 hold.
Proof. The techniques used in this proof are similar to the ones in [10]. We first prove (a). Recall that E t denotes conditioning on ξ 1:t−1 and take expectation w.r.t. ξ t,t−w+1 , . . . , ξ t,t . In view of Assumption 1(i) The first term of RHS of (11) is upper bounded by σ 2 (1−α 2w ) W 2 (1−α 2 ) under Assumption 2. Then for the second term of RHS of (11), according to the Mutual Independence assumption (namely Assumption 1(ii)), we have which is equal to 0, due to Assumption 1(i). Plugging these two results back into (11), proves part (b) of this lemma.

PROOF OF LEMMA 3
Lemma. Suppose Assumptions 1 and 2 hold. Let∇ i S t,w,α (x t ) and υ t+1,i be the sequences defined in the Algorithm DTS-AG. Then, for any 0 < α < 1, w, ǫ > 0 and S t,w, Proof. We use LHS of Lemma 2(a) and obtain that: where Next, we need to upper bound the term I 1 . To this end, we observe that from the definition of υ t+1 and υ t+1 , we have Utilizing this result together with the Jensen's inequality on | · | which is a convex function, we conclude that By regarding the first term of (13) and applying inequality ab ≤ ℏ , we obtain an upper bound as where we used that , yields an upper bound on the second term of (13) by Then, by plugging the above bounds in (14) and (15) into equation (13) we get which implies After plugging (16) into (12), we get which finishes the proof of the claim.
Therefore, plugging (19) into (18), we get Using Lemmas 12 and 13, we get Now, by Markov's inequality, we have with probability at least 1 − δ 1 , Additionally, it follows from Markov's inequality and Lemma 2(b) that with probability at least 1 − δ 2 , holds. Using the above inequality along with the bound a + b 2 ≤ 2 a 2 + 2 b 2 , we also have where Z T t=1 ∇S t,w,α (x t ) 2 . Based on this notation, with probability at least 1 − δ 2 , we have where in the last inequality we used (21). From (22) and (20), with probability at least 1 − δ 1 − δ 2 , we obtain From Lemma 11 and setting δ 1 = δ 2 = δ 2 , we have Here, C ν + ud ln 1 Then, we can bound ν as As α → 1 − , we have Plugging these bounds back to (23), we get the stated bound.

PROOF OF COROLLARY 1
Corollary. Under the same conditions stated in Theorem 1, using w ∈ Θ(T ) and α → 1 − yields a regret bound of order T t=1 E ∇S t,w,α (x t ) 2 ≤ O(ln T ).

Proof. By Theorem 1, we have
, and ζ = σ 2 W . Recall that W = w−1 r=0 α r . As α → 1 − and w ∈ Θ(T ), we get the following equalities: Combine the above results we can easily have the desired result.

PROOF OF LEMMA 4
The proof relies on the following lemma. For the sake of concision, we use the notations below.
Lemma 8. Suppose Assumption 3 holds. Then, for any 0 < α < 1, w, 1 ≤ k ≤ t and S t,w,α (x t ) in (3), we have Proof. By the definition of S t,w,α (x t ) in (3), we have where the last inequality follows from the following argument: where (i) is valid by considering a + b 2 ≤ 2 a 2 + 2 b 2 , and (ii) is due to Lemma 1. Note that where (i) is due to a, b ≤ 1 2 ( a 2 + b 2 ), (ii) is due to symmetry of r and j in summation, and (iii) is due to Lemma 1.
Applying ab ≤ ℏ we can upper bound I 2 term as Following the notations of (25) and (26), the first term in (28) can be bounded as where the first inequality uses a + b 2 ≤ 2 a 2 + 2 b 2 , and the second inequality is from γ ′smoothness of S t,w,α given by Lemma 1 and Lemma 8. For the second term in (28), notice that for any dimension i ∈ [d], we have Injecting (30) and (29) into (28), we obtain where A t+1−k is defined as in (25).
• Bound for I 1 . Let us denoteυ t+1,i β 2 υ t,i + (∇ i S t,w,α (x t )) 2 + µ for all i ∈ [d]. With our new notation, we have where First, we give an upper bound on I 11 term in (32).
By using Lemma 2(a), we have We next bound the I 12 in (32). To this end, we first observe that by the definition of υ t+1,i andυ t+1,i , we have for all i ∈ [d]. Since as Jensen's inequality on | · | and (34), we can find that Now, in order to obtain a bound on the first term in the RHS of (35), we invoke inequality ab ≤ , which leads to the bound To upper bound the second term on the RHS of (35), using inequality ab ≤ ℏ gives us the bound Together from the above two inequalities, it follows that where the second inequality is by Therefore, substituting (33) and (36) into (32), we then obtain Finally, injecting (37) and (31) into (27) gives the desired result.
for some ς > 0 and t ∈ [T ]. Then, for any δ ∈ (0, 1) and S t,w,α (x t ) in (3), with probability at least 1 − δ, the iterates x t satisfy the following bound Proof. By the γ ′ -smoothness of ℓ t functions, S t is γ ′ -smooth as well. Hence, we have Taking expectation on both sides of the above inequality, and using Lemma 4, we can get where A t , B t , and ϑ t are defined as in (25) and (26) andυ t+1,i β 2 υ t,i + (∇ i S t,w,α (x t )) 2 + µ. Hence, rearranging the above inequality, and using the fact that η t+1 is non-decreasing, we obtain: We bound the term I 1 in the following manner: where the inequality follows from Lemmas 12 and 13. We next bound the term I 2 , by the change of index j = t + 1 − k as follows: , the first inequality is by Lemma 16 and the second inequality follows from Lemma 15 with υ t+1,i = t j=1 β t−j 2 (∇ i S j,w,α (x j )) 2 , υ 1,i = 0 and β 1 = 0. Using Lemma 15, we have the following bound on I 3 in (39): Based on Lemma 10, for the term I 4 in (39) we have where the last inequality holds since by changing index j = t − k, we have where (i) follows from Lemma 10 and (ii) follows from Lemma 15. According to the change of index j = t + 1 − k, we bound the term I 5 as follows: where the first inequality is due to the Lemma 17 and the second inequality holds due to Lemma 15.
What's more, we have where (i) is due to the convex inequality 1 , for any positive random variable A, (iii) follows from a + b 2 ≤ 2 a 2 + 2 b 2 , (iv) follows from Lemmas 1 and 2(b).

Now use a similar argument as in equation
Then plugging (53) into (52) yields As α → 1 − , we get The desired result then follows by inserting (54) to (51).

Details of Section 5 PROOF OF LEMMA 5
Lemma. Suppose Assumptions 1 and 4 hold. Then, for∇S t,w,α (x t ) in the Algorithm DTS-AG, any δ ∈ (0, 1), and S t,w,α (x t ) in (3), with probability at least 1 − δ, we have Proof. Similar to the proof for Lemma 2(a), we can show that part (a) of the Lemma. For part (b), for any Γ > 0, we observe that where the first inequality is obtained by Markov's inequality, the second inequality holds because (3), and the third inequality follows from n i=1 a i 2 ≤ n n i=1 a i 2 . Then, we can write where the last inequality is due to Assumption 4. We obtain from the above inequality that: That completes the proof.

PROOF OF LEMMA 6
The proof relies on the following lemma.

PROOF OF THEOREM 3
Theorem. (ADAGRAD) Suppose Assumptions 1, 3 and 4 hold. Let DTS-AG be the algorithm A in Algorithm 1 with parameters β 1 = 0, β 2 = 1, η t+1 = η with η > 0 and α → 1 − . Then, for any δ ∈ (0, 1) and S t,w,α (x t ) in (3), with probability at least 1 − δ, the iterates x t satisfy the following bound Here, Proof. The proof follows along similar lines as Theorem 1 with some important differences. We start with the following observation: where the first inequality follows from the γ ′ -smoothness of the function S t,w,α due to Lemma 1 and the second step is by the definition of x t+1 . Then, summing over t = 1 to T gives Using Lemmas 12 and 13, we get Next, by applying Lemma 11 to the above quadratic inequality, we get that Here, C ν + ud ln 1 Following the same argument as in (24), we also obtain ν ≤ 4DT Plugging (69) into (68), we get the stated bound.

PROOF OF Corollary 3
Corollary. Under the same conditions stated in Theorem 3, using w ∈ Θ(T ) and α → 1 − yields a regret bound of order T t=1 ∇S t,w,α (x t ) 2 ≤ O(ln T ).

Proof. By Theorem 3, we have
W , and ζ κ 2 ln e δ . Recall that W w−1 r=0 α r . As α → 1 − , we get the following equalities: Combine the above results we can easily have the desired result.
where A t+1−k has been defined in (70).
• Bound for I 1 .
Recallingυ t+1,i for all i ∈ [d] we have that where First, we give an upper bound on I 11 term in (73). Observe that where the last inequality follows from the same argument for (60).
We next bound the I 12 in (73). Similar to the arguments for (36), we have where the last inequality follows from (57).
As a result, T = O(ln T ), Combine the above results we can easily have the desired result.
Lemma 10. Given 0 < a < 1 and Q ∈ N, we have, Proof. Observe that x + 1 dx = where the last inequality is by the fact that √ 1 − a ≤ − ln(a).
[28, Lemma 6.2] We assume we have 0 < β 2 ≤ 1 and a non-negative sequence {a n } n∈N . We define b n = n j=1 β n−j 2 a j with the convention b 0 = 0. Then, we have: