{'fraction_non_alphanumeric': 0.061791174601050484, 'fraction_numerical': 0.020742029373389984, 'mean_word_length': 3.848661800486618, 'pattern_counts': {'":': 0, '<': 14, '<?xml version=': 0, '>': 8, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 15, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Non-Asymptotic Analysis of Stochastic Approximation Algorithms for Streaming Data

We consider the stochastic approximation problem in a streaming framework where an objective is minimized through unbiased estimates of its gradients. In this streaming framework, we consider time-varying data streams that must be processed sequentially. Our methods are Stochastic Gradient (SG) based due to their applicability and computational advantages. We provide a non-asymptotic analysis of the convergence of various SG-based methods; this includes the famous SG descent (a.k.a. Robbins-Monro algorithm), constant and time-varying mini-batch SG methods, and their averaged estimates (a.k.a. Polyak-Ruppert averaging). Our analysis suggests choosing the learning rate according to the expected data streams, which can speed up the convergence. In addition, we show how the averaged estimate can achieve optimal convergence in terms of attaining Cramer-Rao's lower bound while being robust to any data stream rate. In particular, our analysis shows how Polyak-Ruppert averaging of time-varying mini-batches can provide variance reduction and accelerate convergence simultaneously, which is advantageous for large-scale learning problems. These theoretical results are illustrated for various data streams, showing the effectiveness of the proposed algorithms.


Introduction
Machine learning and artificial intelligence have become an integral part of modern society. This massive utilization of intelligent systems generates an endless sequence of data, many of which come as streaming data such as weather, traffic, stock trade, or other real-time sensor data. These continuously generated data should be processed sequentially with the property that the data stream may change over time. Such a streaming framework requires computationally efficient and robust algorithms that can quickly update the model as more data arrives.
Stochastic approximation algorithms have proven effective in handling large amounts of data; Bottou et al. [3] reviews such stochastic algorithms for large-scale machine learning, including noise reduction and second-order methods, among others. Among these, the most well-known is presumably the Stochastic Gradient (SG) descent proposed by [27], which is used for many models within machine learning. Since its introduction, much work has been spent on analyzing, developing, and improving various SG-based methods, e.g., see Kushner and Yin [16], Lan [17], Shalev-Shwartz et al. [30]. An essential extension is the Polyak-Ruppert procedure (ASG) proposed by Polyak and Juditsky [26], Ruppert [28], which guarantees optimal statistical efficiency without jeopardizing the computational complexity; this average aggregates the estimates sequentially, which reduces the estimate variance while accelerating convergence [26].
Contributions. A fundamental aspect of this paper is to explore how changing data streams affect these stochastic algorithms. Our analysis extends the work of Moulines and Bach [21] to a streaming framework. We investigate several kinds of data streams, from vanilla SG descent and ASG to more exotic learning designs such as time-varying mini-batch SG and ASG. Our main theoretical contribution is the non-asymptotic analysis of SG-based methods in this streaming framework. Our results show a noticeable improvement in convergence rates by having learning rates that adapt to the expected data streams. In particular, we show how to obtain optimal convergence rates robust to any data streaming rate.
Organization. Section 2 presents the streaming framework on which the non-asymptotic analysis relies. Our convergence results are presented in Sections 3 and 4, with and without averaging. Both sections includes analysis of unbounded and uniform bounded gradients. These theoretical results are illustrated in Section 5 for a variety of data streams. At last, some final remarks are done in Section 6.

Problem Formulation
The analysis of statistical and machine learning models often involves some form of optimization [3,11,18]. Many of these optimization problems aim to minimize functions of the form, with respect to θ ∈ Θ, where Θ ⊆ R d is a convex body; a convex body in R d is a compact convex set with nonempty interior. For streaming (or large-scale) problems, it would be too expensive to compute the full gradient ∇ θ L(θ). Instead, the minimization of L in (1) is achieved without evaluating it directly but by unbiased estimates of its gradients, namely, through ∇ θ l t : Θ → R. Observe that the principles for biased functions (l t ) are rather different [6,29]. Thus, we let (l t ) constitute a sequence of independent differentiable random (possibly non-convex) functions and their gradients unbiased estimates of ∇ θ L, e.g., see Nesterov et al. [24] for definitions and properties of such functions. Many problems, from classification, and regression to ranking, can be written on this form (1), e.g., see Teo et al. [33] for examples of scalar and vectorial loss functions and their derivatives. For example, consider the simple case where we have some samples {(X t , Y t )}, t = 1, . . . , n. Our interest is to find predictor h θ over some parameterization {h θ } θ∈Θ , by minimizing (1) with l t (θ) = l(h θ (X t ), Y t )+λΩ(θ), where l is some loss function, λ > 0 a regulizer parameter, and Ω : Θ → R some regularizer, e.g., the l 1 or l 2 regularization; here the loss l could be the quadratic, logistic, (squared) hinge, or Huber's (robust) loss, but it depends on the experiments that one wants to perform [3,17,24].
Streaming framework. Let us now describe our streaming framework in which we will solve our problem in (1): at each time t ∈ N, a block consisting of n t ∈ N random functions l t = (l t,1 , . . . , l t,n t ) arrive. To solve this, we introduce the Stochastic Streaming Gradient (SSG), defined as where (γ t ) is a decreasing sequence of positive numbers also referred to as the learning rate, satisfying t i=1 γ i = ∞ and t i=1 γ 2 i < ∞ for t → ∞ [27]. In the same way, we introduce the Projected SSG (PSSG), defined by where P Θ denotes the Euclidean projection onto the convex body Θ ⊆ R d , i.e., P Θ (θ) = arg min θ ∈Θ θ − θ 2 . The PSSG estimate in (3) is very convenient for models with conditions on the parameters space, and thereby, requires a projection of the parameters. Next, to guarantee optimal convergence properties [26,28], we introduce the Polyak-Ruppert average of (2), called Averaged SSG (ASSG), given as where N t = t i=1 n i denotes the accumulated sum of observations. Similarly, we define the (Polyak-Ruppert) Average PSSG (APSSG) estimate as when (θ t ) (in (4)) is derived using (3).

Stochastic Streaming Gradients
This section considers the SSG and PSSG methods with streaming batches arriving in constant and time-varying streams. Our aim is to provide bounds on the quadratic mean E[ θ t − θ * 2 ], which depends explicitly upon the problem's parameters. In order to do this, we assume the following about the function l t,i for each t ∈ N with i = 1, . . . , n t : Assumption 1. For each θ ∈ Θ, the random variable ∇ θ l t,i (θ) is square-integrable and ∀θ ∈ Θ, E[∇ θ l t,i (θ)] = ∇ θ L(θ).
Assumption 2-p (C l -expected smoothness). There exists a positive integer p such that ∀θ, These assumptions are modified versions of the standard assumptions for stochastic approximations [2,16] as they hold for any i = 1, . . . , n t . Note that Assumption 2-p only needs to hold for θ = θ * . By the smoothness assumption (Assumption 2-p), we avoid the unfavorable uniformly bounded gradients assumption, which is too restrictive and only holds for a few losses. Assumption 3-p is a weak assumption that should be seen as an assumption on Θ rather than on (l t,i ). For SSG and PSSG, we only need Assumptions 2-p and 3-p to hold for p = 2, whereas, for ASSG and APSSG, we need p = 4 in order to bound the fourth-order moment.
In the following theorem, we derive an explicit upper bound on the t-th estimate of (2) and (3) for any learning rate (γ t ) using classical techniques from stochastic approximations [2,16].
. Under Assumption 1, Assumptions 2-p and 3-p with p = 2, we have for any learning rate (γ t ) that Sketch of proof. Under Assumption 1, Assumptions 2-p and 3-p with p = 2, we derive from (2) that (δ t ) satisfies the recursive relation for any (n t ) and (γ t ) fulfilling the conditions imposed on the learning rate [27]. This recursive relation is then bounded in a non-asymptotic manner using Proposition 5. Bounding the projected estimate in (3) follows directly from the fact that , ∀θ ∈ Θ [35]. Alternatively, the projected estimate can also be shown without Assumptions 2-p and 3-p but instead with a bounded gradient assumption (Assumption 5), e.g., see Moulines and Bach [21]. Related work. When n t = 1 in (8), we obtain the usual SG descent studied in Moulines and Bach [21]. Similarly, Theorem 1 provides an upper bound on the function values, E[L(θ t )−L(θ * )] ≤ C l δ t /2; this follows by Cauchy-Schwarz inequality and Assumption 2-p.
Natural decay imposed by Robbins and Monro [27]. The learning rate (γ t ) should satisfy the following re- These conditions directly imply that π δ t < ∞ as t → ∞. Thus, our attention is on reducing the noise term max t/2≤i≤t γ i /n i without damaging the natural decay of the sub-exponential term exp(−µ t i=t/2 γ i ). In particular, this non-asymptotic bound shows convergence in quadratic mean for any learning rate, fulfilling these conditions. In addition, the scaling with (n t ) in the noise term shows an apparent variance reduction when we increase the streaming batches (n t ).
Throughout this paper, we will consider learning rates on the form γ t = C γ n β t t −α with hyper-parameters C γ > 0, β ∈ [0, 1], and α chosen accordingly to the expected streaming batches denoted by n t . We start by considering constant streaming batches (i.e., mini-batch SG), where n t follows the constant streaming batch size C ρ ∈ N: . Under Assumption 1, Assumptions 2-p and 3-p with p = 2, we have where π c ∞ = exp(4αC 2 γ (2C 2 Decay of the initial conditions. The bound in Corollary 1 depends on the initial condition δ 0 = θ 0 − θ * 2 and the variance σ 2 in the noise term. The initial condition δ 0 vanish sub-exponentially fast for α ∈ (1/2, 1). Thus, the asymptotic term is 2 1+α σ 2 C γ /µC 1−α−β ρ N α t , i.e., δ t = O(N −α t ). Moreover, the bound in (10) is optimal (up to some constants) for quadratic functions (l t,i ), since the deterministic recursion in (9) would be with equality. It is worth noting that if C γ C l or C γ C ∇ is chosen too large, they may produce a large π c ∞ constant. In addition, π c ∞ is positively affected by C ρ when β < 1/2. Obviously, the hyper-parameter β only comes into play if the streaming batch size is larger than one, i.e., C ρ > 1. Nonetheless, the effect of π c ∞ will decrease exponentially fast due to the sub-exponentially decaying factor in front.
Variance reduction. The asymptotic term is divided by C 1−α−β ρ , implying we could achieve variance reduction by taking α + β ≤ 1 when C ρ is large. Taking a large streaming batch size, e.g., C ρ = t, one accelerates the vanilla SG descent convergence rate to O(N 1−β t ). However, this large streaming batch size would be unsuitable in practice, and it would mean that we would take few steps until convergence is achieved.
The safe choice of having β = 0 functions well for the SSG method for any streaming batch size C ρ , but fixed-sized streaming batches are not the most realistic streaming setting. These streaming batches are far more likely to vary in size depending on the data streams. For the sake of simplicity, we consider time-varying streaming batches where n t are on the form C ρ t ρ with C ρ ∈ N and ρ ∈ (−1, 1) such that n t ≥ 1 for all t. We will refer to ρ as the streaming rate. For the convenience of notation, letρ = ρ1 {ρ≥0} .
The reasoning in Corollary 2 could be expanded to include random streaming batches where n t is given such that C L t ρ L ≤ n t ≤ C H t ρ H with ρ L , ρ H ∈ (−1, 1) and C L , C H ≥ 1. This yields the modified rate φ = ((1 − β)ρ L + α)/(1 + ρ H ); nevertheless, we will leave the proof to the reader.

Averaged Stochastic Streaming Gradients
In what follows, we consider the averaging estimate (θ n ) given in (4) derived with use of (θ t ) from (2) (Section 4.1) or (3) (Section 4.2). Besides having Assumptions 2-p and 3-p to hold for p = 4, an additional assumption is needed for bounding the rest term of the averaging estimate.
Note that the operator Σ always exists when σ is finite for order p = 4 in Assumption 3-p.

Unbounded Gradients
As in Section 3, we conduct a general study for any learning rate (γ t ) when applying the Polyak-Ruppert averaging estimate from (4): with (θ t ) given by (4), where (θ t ) follows (2). Under Assumption 1, Assumptions 2-p and 3-p with p = 4, and Assumption 4, we have for any learning rate (γ t ) that for some ∆ 0 ≥ 0. As noticed in Polyak and Juditsky [26], the leading term Λ/N t achieves the Cramer-Rao lower bound [7,22]. Note that the leading term Λ/N t is invariant of the learning rate (γ t ). Moreover, this bound of O(N −1 t ) is achieved without inverting the Hessian. Next, the processes (δ t ) and (∆ t ) can be bounded by the recursive relations in (8) and (22). There are no sub-exponential decaying terms for the initial conditions in Theorem 2, which is a common problem for averaging. However, as mentioned previously, we are more interested in advancing the decay of the asymptotic terms. To ease notation, we make use of the functions ψ y x (t) : R → R, given as Hence, for any x, y ∈ R + , ψ y x (t)/t =Õ(t −(x+y)/(1+y) ), where theÕ(·) notation hides logarithmic factors.
Corollary 3 (ASSG, constant streaming batches). Denoteδ t = E[ θ t − θ * 2 ] with (θ t ) given by (4), where (θ t ) follows (2). Suppose γ t = C γ n β t t −α with n t = C ρ for C ρ ∈ N, such that α ∈ (1/2, 1). Under Assumption 1, Assumptions 2-p and 3-p with p = 4, and Assumption 4, we havē with Γ c given by Accelerated decay the initial conditions. By averaging, we have increased the rate of convergence from O(N −α t ) to the optimal rate O(N −1 t ). The two subsequent terms are the main remaining terms decaying at the rate O(N α−2 t ) and O(N −2α t ), which suggests setting α = 2/3 would be optimal. The remaining terms are negligible. Next, it is worth noting that having α + β = 1 in Corollary 3, we would give no impact in the main remaining terms from the streaming batch size C ρ . Moreover, taking α = 2/3 and β ≤ 1/3 would be an optimal choice of hyper-parameters such that the streaming batch size C ρ have a positive or no impact. At last, as we do not rely on sub-exponentially decaying terms, we need to be more careful when picking our hyper-parameters, e.g., taking C γ C l too large may cause Γ c to be significant. Nevertheless, the term consisting of Γ c decay at a rate of at least O(N −2 t ).

Bounded Gradients
In what follows, we consider the averaging estimateθ n given in (4) but with the use of the projected estimate PSSG from (3). To avoid calculating the six-order moment, we make the unnecessary assumption that ∇ θ l t,i (θ) is uniformly bounded for any θ ∈ Θ; the derivation of the six-order moment can be found in Godichon-Baggioni [9].

Experiments
In this section, we demonstrate the theoretical results presented in Sections 3 and 4 for various data streams. In Section 5.1, we illustrate the unbounded gradient case (Sections 3 and 4.1) using linear regression. Where in Section 5.2, we present the bounded gradient case (Sections 3 and 4.2) by considering the geometric median. To measure the performance, we use the quadratic mean error of the parameter estimates over one-hundred replications, given by (E[ θ N t − θ * 2 ]) t≥1 . Note that averaging over several iterations gives a reduction in variability, which mainly benefits the SSG and PSSG.

Linear Regression
Consider the linear regression defined by y t = X T t θ + t , where X t ∈ R d is a random features vector, θ ∈ R d is the parameters vector, and t is a random variable with zero mean, independent from X t . Moreover, (X t , t ) t≥1 are independent and identically distributed. Thus, θ * is the minimizer of In this example, we fix d = 10, set θ = (−4, −3, 2, 1, 0, 1, 2, 3, 4, 5) T ∈ R 10 , and let (X t ) and ( t ) be standard Gaussian. It is well-known that C γ can substantially impact convergence; when C γ is too large, instability can occur, leading to an explosion during the first iterations. If C γ is too small, the convergence can become very slow and destroy the desired rate α. To focus on the various data streams, we set C γ = 1/2 and α = 2/3.
In Figure 1a, we consider constant data streams to illustrate the results in Corollaries 1 and 3. The figures show a solid decay rate proportional to α = 2/3 for any streaming batch size C ρ ∈ {1, 8, 64, 128} with β = 0, as shown in Corollary 1. In addition, we see an acceleration in decay by averaging, as explained in Corollary 3. Both methods show a noticeable reduction in variance when C ρ increases which are particularly beneficial in the beginning. Moreover, as mentioned in Remark 1, the stationary phase may also commence earlier when we raise the streaming batch size C ρ . Next, in Figures 1b to 1e, we vary the streaming rate ρ for streaming batch sizes C ρ = 1, 8, 64, and 128, respectively, with β = 0. These figures shows an increase in decay of the SSG when the streaming rate ρ increase. Despite this, we still achieve better convergence for the ASSG method, which seems more immune to the different choices of 8 streaming rate ρ, e.g., see the discussion after Corollary 4. We know this from Corollary 2, as φ = (ρ + α)/(1 +ρ) ≥ α for β = 0. In addition, we see that C ρ has a positive effect on the noise (i.e, variance reduction), but if C ρ becomes too large, it may slow down convergence (as seen in Figure 1e). Alternatively, we could think around the problem in another way: how can we choose α and β such that we have optimal decay of φ = 2/3 for any ρ. In other words, for any arrival schedule that may occur, how should we choose our hyper-parameters such that we achieve optimal decay of φ = 2/3. As discussed after Corollary 4, one example of this could be achieved by setting α = 2/3 and β = 1/3 such that φ = 2/3 for any ρ. Figure 1f shows an example of this where we (indeed) achieve the same decay rate for any streaming rate ρ.

Geometric Median
The geometric median is a generalization of the real median introduced by Haldane [12]. Robust estimators such as the geometric median may be preferred over the mean when the data is noisy. Moreover, in our streaming framework, stochastic algorithms are preferred as they efficiently handle large samples of high-dimensional data [5,9]. The geometric median of X ∈ R d is defined by θ * ∈ R d which minimizes the convex function L(θ) = E[ X − θ − X ], e.g., see Gervini [8], Kemperman [14] for properties such as existence, uniqueness, and robustness (breakdown point).
As discussed in Gadat and Panloup [7], this boundedness implies that it is not necessary to project our estimates explicitly. Similarly to above, we fix d = 10 and let (X t ) be standard Gaussian centered at θ = (−4, −3, 2, 1, 0, 1, 2, 3, 4, 5) T ∈ R 10 . Moreover, following the reasoning of Cardot et al. [5], we set C γ = √ d = √ 10, and let α = 2/3. Figure 2a shows the variance reduction effect for different constant streaming batches C ρ with β = 0. However, the robustness of the geometric median leaves only a small positive impact for further variance reduction. Thus, too large (constant) streaming batch sizes C ρ hinders the convergence as we make too few iterations. These findings can be extended to Figures 2b to 2e, where we vary the streaming rate ρ for streaming batch sizes C ρ = 1, 8, 64, and 128, respectively, with β = 0. The lack of convergence improvements comes from β = 0, which means we do not exploit the potential of using more observations to accelerate convergence. As shown in Figure 2f, we can achieve this acceleration by simply taking β = 1/3. In addition, β = 1/3 provides optimal convergence robust to any streaming rate ρ. Choosing a proper β > 0 is particularly important when C ρ is large, as robustness is an integral part of the geometric median method.

Conclusions
We considered the stochastic approximation problem in a streaming framework where we had to minimize convex objectives using only unbiased estimates of its gradients. We introduced and studied the convergence rates of the stochastic streaming algorithms in a non-asymptotic manner. This investigation was derived using learning rates of the form γ t = C γ n β t t −α under time-varying data streams (n t ). The theoretical results and our experiments showed a noticeable improvement in the convergence rate by choosing the learning rate (hyper-parameters) according to the expected data streams. For ASSG and APSSG, we showed that this choice of learning rate led to optimal convergence rates and was robust to any data stream rate we may encounter. Moreover, in large-scale learning problems, we know how to accelerate convergence and reduce variance through the learning rate and the treatment pattern of the data.
There are several ways to expand our work but let us give some examples: first, we can extend our analysis to include streaming batches of any size in the spirit of the discussion after Corollary 2. Second, many machine learning problems encounter correlated variables and high-dimensional data, making an extension to non-strongly convex objectives advantageous Bach and Moulines [1], e.g, in Werge and Wintenberger [34], they use SG-based optimization methods for volatility prediction through GARCH modeling. Third, Assumption 1 requires unbiased (and independent) gradient estimates, thus, an obvious extension could incorporate a more realistic dependency assumption, thereby increasing the applicability for more models. Moreover, studying dependence may give insight into how to process dependent information optimally. Next, a natural extension would be to modify our averaging estimate from (4) to a weighted averaged version (WASSG) proposed by Mokkadem and Pelletier [20] and Boyer and Godichon-Baggioni [4], given as for λ > 0 with (θ t ) following (2) or (3). We can limit the effect of bad initializations by placing more weight on the newest estimates. Following the demonstrations in Section 5, an example of this WASSG estimate (θ t,λ ) can be found in Figure 3 with use of λ = 2. Here we see that although the WASSG estimate in (13) may not achieve a better final error (compared to the ASSG and APSSG estimates in Figures 1f and 2f), but it still achieves a better decay along the way, often referred to as parameter tracking.

Proofs for Section 3
The section is structured such that we start by analyzing the recursive relations and bounding them for every choice of learning rate. Next, we look at specific choices of learning rates.
Proof of Theorem 1. Taking the quadratic norm on both sides of (2), expanding it, and take the conditional expectation, yields To bound the second term (on the right-hand side) of (14), we first expand it as follows, For first term of (15), we utilize the Lipschitz continuity of ∇ θ l t,i , together with Assumptions 1 to 3-p, to obtain using x + y 2 ≤ 2( x 2 + y 2 ). Next, for the second term in (15): since θ t−1 and l t,i are F t−1, j−1 -measurable for all 0 ≤ i < j, and similarly, as θ t−1 is F t−1 -measurable and F t−1,i−1measurable for all i ≥ 0, we also have Thus, we obtained a bound for the second term (on the right-hand side) of (14) using the bounds of the two terms in (15): For the third term (on the right-hand side) of (14) we use that L is µ-quasi-strong convex and θ t−1 is F t−1 -measurable, by Assumption 1. Combining inequalities from (17) and (18) into (14) and taking the expectation on both sides of the inequality, yields the recursive relation (9): with some δ 0 ≥ 0. At last, by Proposition 5, we obtain the desired inequality in (8), namely using that (n t − 1)n −1 t ≤ 1 {nt >1} , n t ≥ 1, and that max 1≤i≤t 2σ 2 /(2C 2 l + (n i − 1)C 2 ∇ ) ≤ max 1≤i≤t 2σ 2 /2C 2 l = σ 2 /C 2 l . Remark 1. The decrease of (2C 2 l + (n t − 1)C 2 ∇ )n −1 t γ t determines when the stationary phase occurs. This is more clearly seen in Proposition 4, where the inner terms directly depend on the inception of the stationary phase. Thus, by increasing n t , we decrease (2C 2 l + (n t − 1)C 2 ∇ )n −1 t γ t , and especially it dominates the constant C l . Proof of Corollary 1. By Theorem 1, we have the upper bound giving as using the integral test for convergence. Next, as (γ t ) t≥1 is decreasing, then max t/2≤i≤t γ t = γ t/2 . Combining all these findings into (19), gives us with π c ∞ = exp(4αC 2 γ (2C 2 . At last, converting (20) into terms of N t using N t = C ρ t, yields the desired.

Proofs for Section 4
Lemma 1 (ASSG/APSSG). Denote ∆ t = E[ θ t − θ * 4 ] for some ∆ 0 ≥ 0, where (θ t ) follows (2) or (3). Under Assumption 1, Assumptions 2-p and 3-p with p = 4 and Assumption 4, we have for any learning rate (γ t ) that with Π ∆ t given in (30). Proof of Lemma 1. We will now derive the recursive step sequence for the fourth-order moment using the same arguments as in proof for Theorem 1. Thus, one can show that as L is µ-quasi-strong convex. Combining this with the Cauchy-Schwarz inequality x, y ≤ x y , we obtain the simplified expression: Next, recall Young's Inequality, i.e., for any a t , b t , c t > 0 we have a t b t ≤ a 2 t c 2 giving us To bound the second and fourth-order terms in (23), we would need to study the recursive sequences: firstly, utilizing the Lipschitz continuity of ∇ θ l t,i , together with Assumptions 2-p and 3-p, and that θ t−1 is F t−1 -measurable (Assumption 1), we obtain for any p ∈ [1, 4] using the bound x + y p ≤ 2 p−1 ( x p + y p ). Thus, we can bound the second-order term in (23) by following the same steps in the proof of Theorem 1, but with use of (24). Bounding the fourth-order term is a bit heavier computationally, but let us recall that i x i as (x + y) 2 ≤ 2x 2 + 2y 2 . For the first term of (26), we have ≤8n t [C 4 l θ t−1 − θ * 4 + σ 4 ] + 4n 2 using the bound from (24), n t (n t − 1) ≤ n 2 t 1 {nt >1} , and that F t−1 ⊆ F t−1,i ⊂ F t−1, j for all 0 ≤ i < j. To bound the second term of (26), we ease notation by denoting ∇ θ l t,i (θ t−1 ) by υ i , giving us By Cauchy-Schwarz inequality, we can bound the first term A, by using the Cauchy-Schwarz inequality and the bound in (24). In the same way, as j l includes (i, j) (k, l), we can rewrite C as C = n t i< j,k<l, j l υ i , υ j υ k , υ l = n t i< j,k<l,i=k, j l . Finally, we can rewrite C 2 as C 2 = n t i< j,k<l,i k, j l,i=l, j k υ i υ j υ k υ l C 2,1 + n t i< j,k<l,i k, j l,i l, j=k Thus, the fourth-order term of (23), is bounded by l n t + 16C 4 l n 2 Combining the bound from (25) and (27) into (23), we obtain the recursive relation for the fourth-order moment: Using the Young's inequalities, 2C 2 for some ∆ 0 ≥ 0. By Proposition 5, we achieve the (upper) bound of ∆ t in (29), given as where Π ∆ t is given by with use of At last, bounding the projected estimate (3) follows from that where ∇ θ l t (θ t−1 ) denotes n −1 , and that ∇ θ l t (θ * ) and ∇ θ l t (θ)−∇ θ L(θ) behaves almost like an i.i.d. sequences with zero mean. Thus, where ∇ 2 θ L(θ * ) is invertible with lowest eigenvalue greater than µ, i.e., ∇ 2 θ L(θ * ) ≥ µ. Thus, summing the parts and using the Minkowski's inequality, we obtain the inequality: As (∇ θ l t,i (θ * )) is a square-integrable martingale increment sequences on R d (Assumption 1), we have using Assumption 4. To ease notation, we denote Tr[∇ 2 θ L(θ * ) −1 Σ∇ 2 θ L(θ * ) −1 ] by Λ. Next, note that for all t ≥ 1, we have the relation in (31), giving us Hence, with the notion of δ t = E[ θ t − θ * 2 ] this expression can be simplified to For the martingale term, we have by the Cauchy-Schwarz inequality and Assumption 2-p. For all t ≥ 1, the rest term is directly bounded by (7): with the notion ∆ t = E[ θ t − θ * 4 ]. Finally, combining the terms from (32) to (35), gives us whereδ t = E[ θ t − θ * 2 ], which can be simplified into (12) by shifting the indices and collecting the δ 0 terms. Proof of Corollary 3. As n t = C ρ for all t ≥ 1, we simplify the bound forδ t in (12) tō The second-order moment δ t is bounded by Corollary 1 but with use of (20) as we work in terms of t. The fourth-order moment ∆ t from Lemma 1 can be simplified to: using that γ t = C γ C β ρ t −α is decreasing as α ∈ (1/2, 1). Regarding Π ∆ t defined in (30), we can bound it by To bound the first term of (37), namely For simplicity, let us denote as α < 1. Thus, the first part of (38) is bounded as follows: Furthermore, with the help of an integral test for convergence, one has t i=1 i α/2−1 ≤ 1 + t 1 s α/2−1 ds = 1 + (2/α)t α/2 − (2/α) ≤ (2/α)t α/2 , such that the second part of (38) can be bounded by By combining this, we get 18 Similarly, second term of (37), can be bounded by In a same way, one has Bound the last term of (37), is done as follows, Thus, by collecting the terms above, we obtain: Proof of Corollary 4. The steps of the proof follows the ones of Corollary 3 with the smart notation of φ andρ: The bound forδ t in (12) is given bȳ where the learning rate is on the form γ t = C γ n β t t −α with n t = C ρ t ρ . The second-order moment δ t is upper bounded by (21) from Corollary 2. The fourth-order moment ∆ t from Lemma 1 can be simplified as follows, as n t ≥ 1 for any t ≥ 1 and β ≤ 1, and
Proof of Corollary 5. The proof follows directly from Corollary 3 but with use of Theorem 3.
Proof of Corollary 6. The proof follows directly from Corollary 4 but with use of Theorem 3.