Last iterate convergence of SGD for Least-Squares in the Interpolation regime

Introduction

As soon as large-scale statistics and optimization need to work together, stochastic gradient descent (SGD) is the core algorithm everybody tries to build upon . Its versatility, practicability and adaptability make it the workhorse of almost every supervised machine learning problem. Yet, its outstanding efficiency remains mysterious, or at least surprising on certain aspects. Furthermore, the recent successes of deep neural networks (DNN) brought a new paradigm to the classical supervised learning setting with the ability to fit the data perfectly and to generalize well . Following this idea, the old statistical modelling where the model suffers from problem-dependent noise has to be revisited: there is a need of analyzing stochastic algorithms in this new light . Whether we call it over-parameterization to put emphasis on the large number of neurons needed in DNNs, interpolation as in approximation theory or noiseless model to stress the absence of noise in this statistical model, all these terminologies refer to the same idea. This regime brings with it new insights that reflect better the current machine learning setup.

Hence, the main question: how would SGD profit from this noiseless model? At first glance, the story seems clear: the old problem of variance at optimum making the SGD iterates oscillate asymptotically now disappears. Thus, should also disappear techniques that prevent from this, namely, averaging and decaying step sizes: one should be able to study the convergence of the SGD final iterate with constant step-size.

However, the study of the last iterate of SGD has always caused some technical problems preventing from a clear theory in this case . Indeed, the convergence of the final iterate is much more difficult to prove than the convergence of the average of the iterates . This counter-intuitive difficulty can be explained by the fact that the interactions coming from the sampling noise of SGD prevent the final iterates from forming a decreasing sequence. Therefore standard Lyapounov strategies often failed in such a setting. Besides, even if averaged SGD has shown theoretically some good convergence properties, the final iterate is commonly used in practice. Finally, averaging techniques always suffer from saturation coming from the slow forgetting of initial conditions.

To tackle these questions, we consider the simplest setting of the linear regression over features $\phi(X)$ in a Hilbert space $\mathcal{H}$. In this context, the setup corresponds to the existence of linear relationship between the output and the input: $Y=\langle\theta_{*},\phi(X)\rangle$. Note that this setting is rich as the features can be a non-linear transformation of the inputs, as it is commonly the case when they are defined through a positive-definite kernel $K(X,X^{\prime})$ . Note also that our analysis will, unless stated explicitly, be conducted in a non-parametric and dimensionless fashion, enabling the features to come from a infinite dimensional reproducing kernel Hilbert space. In this perspective, the problem we are considering is not strongly convex.

Main contributions. The aim of the present article is to answer at once the two following problems: (i) from a (stochastic) optimization perspective, the goal is to exhibit an archetypal problem where we can show explicitly the convergence of SGD final iterate for a non-strongly convex problem with constant step-size and (ii) from a statistical/machine learning perspective, the aim is to push deeper the study of the over-parameterized setting for the non-parametric least-squares problem. Contrary to the noisy setting, where (almost) everything is known, the noiseless model suffers from a certain lack of understanding. More precisely, our contributions are the following:

We show that the final iterate of constant step-size SGD achieves a convergence rate of $O(\ln(T)/T)$ under minimal assumptions. With a slightly stricter hypothesis we improve this convergence rate to $O(1/T)$.

Going further, we assume the usual non-parametric capacity and source conditions respectively on the spectrum of the covariance and the optimum, and derive bounds for this fine-grained model. In this setup, we show the SGD fast rates of $O(1/T^{1+\alpha})$.

We derive an explicit recursion on the eigenspaces of the covariance matrix that is of its own interest. Indeed, it is the cornerstone of our analysis and could be very useful in the future to understand important properties of SGD.

From a technical standpoint, going from the average to the last iterate is far from anodyne for constant step-size SGD even in the interpolation regime. Indeed, in a similar setting, D.Aldous considered it an open problem [1, Sec. $3.3$, Open problem (i)]. Prior to our result, how to directly deal with the fluctuations induced by the stochasticity of the gradients was not known. Our work presents a direct Lyapunov technique that handles them without any explicit variance reduction methods like averaging or step-size decay.

As recalled earlier, it is often easier to show convergence for the averaged iterates of SGD than for the final one. However, there has been a huge effort by the optimization and machine learning communities to work on the final iterate. We report here the different works and contexts for which such results are shown. All the results stated below are for convergence in function value.

Over-parameterized setting. As recalled earlier, SGD in the over-parameterization regime corresponds to the assumption that all the function gradients vanish at optimum. It has been first studied by who assumed furthermore a strong growth condition (SGC) (first introduced by ) but often too stringent to match the machine learning practical set-up. Up to our knowledge, was the first to point out that this interpolation regime was particularly relevant in the recent deep learning framework and to show linear convergence in the strongly-convex setting. In the non-strongly convex case, $O(1/T)$-convergence has been shown by for the averaged iterates. Consequently, there has been many papers discussing this setting, proving convergence rates in different contexts: Polyak-Lojasiewicz , accelerated , second-order , line-search . However, no rate for the final iterate has been shown in the non-strongly convex setting for the last iterate as the only convergence rates achieved, $O(1/T)$, corresponds in all these works to the averaged iterates.

Set-up: Stochastic Gradient Descent on the Least-squares Problem

The setting is classical for stochastic gradient descent for linear least-squares in a Hilbert space $\mathcal{H}$. The function we would like to minimize over $\theta\in\mathcal{H}$ is

Noiseless model. We assume that the model does not suffer from any noise: there exists $\theta_{*}\in\mathcal{H}$ such that, $\rho$-almost surely, $\langle\theta_{*},x\rangle=y$. This means that the model is well specified and that there is no noise at optimum. Due to this noiseless condition, we expect our iterates to go to the optimum without decaying step-sizes or averaging. We can also rewrite the Risk in Eq. (1):

SGD with constant step-size. To minimize the function $\mathcal{R}$ defined in Eq. (1), we do not have access to the distribution $\rho$ but to a stream of i.i.d. observations $(x_{t},y_{t})_{t\geqslant 1}$ sampled from it. We hence perform a gradient descent in the direction given by one sample at a time with constant stepsize $\gamma>0$. Throughout all this paper, the initial condition is always set to $\theta_{0}=0$ and for $t\geqslant 1$,

The impossibility of linear rates. We stress that the least-squares setup we consider is a non-strongly convex problem. Indeed, in finite dimension $d$, $\lambda_{\textrm{min}}>0$, and SGD converges at linear rate $\sim e^{-\gamma\lambda_{\textrm{min}}T}$ [18, Theorem 1], this asymptotic regime occurring after a time scale $\tau\sim 1/(\gamma\lambda_{\textrm{min}})$. However, this apparent strong convexity is a lure, since the large (or infinite) dimension makes this convergence rate vacuous for a arbitrarily small $\lambda_{\textrm{min}}$. Hence we focus on the non-parametric non-strongly convex setup where we prove non-asymptotic polynomial rates. Yet in finite dimension, it is always possible to see the linear regime after time $1/(\gamma\lambda_{\textrm{min}})$ as shown in Figure 1, even if this time can be arbitrarily long.

Convergence rates of the final iterate of SGD

In large dimension, two quantities govern principally the rates of convergence of least-squares estimators: (i) the spectrum of the covariance matrix, and (ii) how the solution, $\theta_{*}$, projects on the eigenbasis of the covariance matrix. In this section, we state refined assumptions on the spectrum of the covariance matrix and the decomposition of $\theta_{*}$ over its eigenbasis. Note that in finite-dimension, all these quantities are always finite, but can be extremely large compared to the sample size $T$. This is why the reader can see these more as a fine-grained parameterization of the problem rather than restrictive assumptions. The assumptions we make always go in pairs, (i) one for the features through the covariance matrix (Assumptions 1, 3 and 5) and (ii) one for the target solution (Assumptions 2, 4 and 6).

Summary on the results. As assumptions go stricter, the convergence rates go faster. Every theorem is a bound on the expected risk given by the last iterate of the SGD recursion with constant step size $\gamma$, started at $\theta_{0}=0$. Only for Theorem 1, for which the assumptions are the weakest, we allow the step-size to depend on the finite horizon $T$ (through its logarithm). All the theorems are stated with respect to finite constants defined thanks to the different assumptions. The reader can refer to Table 1 for a concise summary of them. Note also that we put a particular effort for the clarity of the bounds, and hence, some numerical constants might appear large. These are simple artifacts on the proofs and could be lowered, but at the price of less clear results. A more detailed summary of our results can be found in Appendix A. All the proofs are deferred to Appendix C.

As often, when we analyze SGD, we make an $4$-th order assumption on the distribution of the features.

There exists a finite constant $R\geq 0$, such that

The assumption holds in the case of bounded features, i.e. when $\left\lVert X\right\rVert^{2}\leqslant R$, $\rho_{X}$-almost surely. It also holds more generally for features with infinite supports, such as sub-Gaussian data, and canonical basis distributions (i.e. $x=e_{i}$ with probability $p_{i}$). This is a standard assumption when analysing SGD for least squares which is weaker than what is assumed in .

The target solution $\theta_{*}$ lies in the space $\mathcal{H}$. This ensures that it has a finite norm $\displaystyle\|\theta_{*}\|_{\mathcal{H}}<+\infty$.

While this is always true in finite dimension, this assumption draws the attention on the fact that the norm of the optimum $\theta_{*}$ could be very large in high-dimension. As a limit, in infinite-dimensional spaces, $\theta_{*}$ could not belong to $\mathcal{H}$ and hence would have an infinite norm. This is why we refer to this assumption as the attainable case. Under these two assumptions we have the following result.

Assume Assumptions 1, 2. Then, for $\ T\geqslant 2$, if we set $\gamma=(4R\ln(T))^{-1}$, we have the following bound for the expected risk of the estimator given by the $T^{th}$ iterate of SGD:

Let us comments upon this result proven in Appendix C.1. The theorem above states that, under mild assumptions, if we allow the step-size to depend on the time horizon, we have a $O(\ln(T)/T)$ convergence rate for the final iterate. First, removing the dependence on finite horizon $T$ for the step-size by considering decaying step-sizes $\gamma_{t}\propto 1/\ln(t)$ could be done, but we decided to keep this way as we have focused on constant step-size in this paper. Furthermore, Theorem 2 of shows that this bound is optimal up to $\log(T)$ for a SGD. This rate can also be compared to the classical optimization results for the non-strongly convex objective (our case). It is well known that gradient descent and averaged SGD (even for non-quadratic objectives) achieve a $O(1/T)$ rate with constant step size. Similarly achieves a convergence rate of $O(1/T)$ rate with constant step size for the $\min$ of the function value along the iterates. However, the rate of convergence of SGD last iterate was an open problem [see 6, Remark 1]. Note however that our bound suffers from a $\log(T)$ both in function value and for the step-size. Whether this term is necessary is an open question for us. The purpose of the following development is to first remove these $\log(T)$ dependence at the price of a $\log$-scale refinement of the assumptions.

2 A logarithm-scale refinement

This second sequence of assumptions is slightly stronger. They reinforce assumptions 1 and 2 at the log-scale. Once again, there is one on the features and the other one is on the target.

The covariance matrix at optimum $M_{0}=\theta_{*}\theta_{*}^{\top}$ satisfies the following condition:

This theorem, proven in Appendix C.2, states that at the price of a $\log$-scale refinement on the features and optimum, the SGD-convergence rate is $O(1/T)$. This naturally restricts the class of problems that suffers from a $\log(T)$ (see Theorem 1) to a very small class: roughly speaking, it is the class of problems for which the eigenvalue decreasing rate is strictly squeezed between: $O(1/(i\ln i))<\lambda_{i}<O(1/i)$. The role of the assumptions is fundamental here: Assumption 3 allows to remove the $\ln(T)$ for the step-size and Assumption 4 allows to remove the $\ln(T)$ for the convergence rate. The proof technique is the same as for the previous theorem, the only difference is that the assumptions allow to control more precisely the bias and the variance in the SGD recursion.

3 A fine-grained parameterization of the problem: capacity and source conditions

The final set of assumptions have been introduced by . They are in the same vein as above assumptions and are often called capacity and source conditions in the reproducing kernel Hilbert spaces community.

The covariance matrix $H$ is such that there exists $\alpha>0$ and a finite constant $R_{\alpha}>0$ verifying

Here are important remarks on this assumption. First note that

Hence, $\beta=0$ corresponds to Assumption 2 which is the attainable case. It is worth noting that for $\beta\in(-1,0)$, this assumption takes into account the fact that $\theta_{*}$ does not necessarily belong to $\mathcal{H}$. In such a case, it is still possible to define properly $\theta_{*}$ as the infimum over $\mathcal{H}$ of the risk $R$ defined in Eq.(1). However, for sake of clarity and to avoid cumbersome technicalities, we refer to [9, p.1395] for the extension of the analysis is this case. As before, the larger the $\beta$ the stricter the assumption is. Finally as a limiting case, $\beta\to+\infty$ corresponds to the fact that $\theta_{*}$ belongs to a finite dimensional space. This hypothesis is often called the source condition in the literature because it quantifies the complexity of the optimum [see 8, 29, 20, for further details]. Once again, parameterization has not yet been fixed by the literature and one often uses the parameter $r$ that corresponds to $r=\frac{\beta+1}{2}$. We have the following theorem under these capacity and source conditions.

Assume Assumptions 5, 6 with constants $\alpha\in(0,1)$ and $\beta>-1$ respectively. Then, for $\ T\geqslant 3$, we have the following bound for the expected risk of the $T^{th}$ iterate of SGD:

where $\gamma^{1-\alpha}\leqslant(32\xi_{\alpha}R_{\alpha})^{-1}$ and $\displaystyle\xi_{\alpha}=\sum_{n\geqslant 1}\frac{1}{n^{1+\alpha}}$.

Let us comment this result. Its proof can be found in Appendix C.3.

Discussion on the limit cases for $\alpha$ and $\beta$. Let us note a few observations on the two parameters $\alpha$ and $\beta$. Firstly, it is observed in that the rate $1/T^{1+\alpha\wedge\beta}$ is optimal in terms of power law for SGD. Second, the convergence rate depends on the minimum of the two. It implies that either the regularity of the features, or the one of the optimum, is a bottleneck for the convergence of SGD. More precisely if $\alpha<\beta$, the features are not regular enough to counter the multiplicative noise of SGD. Conversely, when the optimum is the bottleneck, there is no difference between SGD and Gradient Descent (GD), as $T^{1+\beta}$ is the rate of convergence of GD. Note that $\alpha\to 0$ corresponds to the setting of Theorem 1 where a $\log(T)$ appears. Hence, it is normal that our bound does not hold in this limit: indeed, we remark that the step-size shrinks to $0$ as $\xi_{\alpha}$ goes to infinity. Another interesting limit is the case where $\alpha\to 1$: as said before this cannot occur in infinite (or large) dimension as $R_{\alpha}\to$“$d$ ”. Therefore the bound blows up in this limit also. The fact that the step-size depends on $\alpha$ is a weakness of our result and is due to the mixing power of the covariance eigenspaces. This dependence could be eliminated with an extra assumption on a lower bound on the decrease rate of the spectrum of the covariance matrix as made by . Finally note that the rate of convergence is always strictly better than $1/T$ for $\beta>0$ and is remarkably adaptive to the possible misspecification of the problem $\beta\in(-1,0)$.

Comparison with the literature. We can first compare to the results on the noisy setting studied by . Naturally, when some additive noise is assumed, averaging is necessary, and the results are weaker: $\gamma$ is not adaptive to the problem, depends on the time-horizon and the rates are always slower than $O(1/T)$. However, when the noise is $0$, the averaged iterates achieves the exact same convergence rate as in our theorem. The closest results to our theorem are in , where the same rates are shown. The important difference is that their results are given for the $\min$ of the function value and not the final iterate: our theorem solves an open problem stated in the aforementioned paper. Remark however that one superiority of is that the step-size does not depend on $\alpha$ showing some adaptivity with this parameter. As noted in the previous paragraph, we could fix this difference with an extra assumption on the spectrum of the covariance matrix. Finally, rates of convergence for the noiseless setting have been addressed by with some truncated version of the kernel ridge estimator. It was an open problem stated by the author to understand whether SGD could achieve these non-parametric rates. As for the $\min$, this problem seems to be properly solved now. A main difference is that the bounds of suffer from some saturation in the well specified setting, when $\beta>0$, whereas our estimator does not. When $\alpha-1\leqslant\beta\leqslant 0$, then the bounds match, but when the problem is really misspecified, for $\beta\leqslant\alpha-1$, the bound of is strictly better than ours. As we know that our result is optimal for SGD, it raises the interesting question whether some form of acceleration or multiple passes over the data could reach these rates.

Link with kernel regression. These capacity and source conditions are classical in the reproducing kernel Hilbert spaces community. For sake of clearness, we did not mention any specificity on the features. However, as it has been done in , SGD can be “kernelized” and the descent becomes an optimization algorithm in the RKHS space of functions. In this context, the capacity and source conditions take on their full meaning: when RKHS are Sobolev spaces, they represent a smoothness condition on the features and the optimum respectively. The coefficient $\alpha$ would be the degree of regularity that we choose for the kernel, and $\beta$ the prior we have on the optimum solution. For more details, we refer to section 4 of or section 3.1 of .

Development of the SGD recursions and proof outline

In this section we provide an overview of the arguments that comprise the proof of our results.

Recursions for multiplicative noise. We can rewrite the SGD recursion Eq. (3) for the deviation to the optimum $\eta_{t}:=\theta_{t}-\theta_{*}$ as a descent on the risk plus a multiplicative noise term. For $t\geqslant 1$,

Note a main difference between the two recursions, Eq. (9) is a deterministic recursion over operators whereas Eq. (8) is a stochastic recursion on vectors.

Deviations sequence and initial conditions. We emphasis that $\eta_{t}$ and $M_{t}$ represent deviations to the optimum $\theta_{*}$. This is why proving that $\theta_{t}$ goes to $\theta_{*}$ corresponds to $\eta_{t}$ and $M_{t}$ going to $0$. As the initial point of the SGD recursion is $\theta_{0}=0$, the initial conditions $\eta_{t=0}$ and $M_{t=0}$ represent, in fact, respectively the optimum and the covariance at optimum.

Eigenspaces of the covariance. The core of the analysis rests on a reformulation of our problem in the eigenspaces of the covariance operator. Recall that $(\lambda_{i},v_{i})_{i}$ are the sorted eigenelements of $H$ and define the decomposition of $M_{t}$ in the basis of $v_{i}v_{j}^{\top}$, $M_{t}:=\sum_{i}m^{t}_{i}v_{i}v_{i}^{\top}+\sum_{i\neq j}m_{ij}^{t}v_{i}v_{j}^{\top}.$ We can write the expected risk of the estimator given by the $t$-th iterate of SGD, that we denote by $\mathsf{f}_{t}$:

It is quite remarkable that the $(m_{ij})_{i\neq j}$ do not play any role in the recursions. The aim now is to write a recursion for $(m_{i}^{t})_{i}$ that leads to a recursion for the function value $\mathsf{f}_{t}$ through Eq. (10). This is the purpose of the following and central lemma, whose proof can be found in Appendix B.1.

Let us make comments on this important lemma. First, note that the only difference with the deterministic recursion (gradient descent) is the presence of the “mixing terms” $(\mathsf{f}^{t}_{i})_{i}$. In fact, these terms affect dramatically the dynamics. Indeed, there is no reason that the iterates decrease along the iterations: this is what makes the analysis more tedious for the final iterate. On the contrary, the usual convergence rate for the averaged iterates is easily obtained by summing Eq. (11) and comparing the terms. Note finally that the strength of Eq. (11) lies in the fact that the different eigenspaces (e.g. $m_{i}^{t}$ and $m_{j}^{t}$ for $i\neq j$) interact only through $\mathsf{f}^{t}_{i}$ and $\mathsf{f}^{t}_{j}$. By summing Eq. (12), and appropriately controlling sums of $\mathsf{f}^{t}_{i}$’s with Assumptions 1, 3 or 5, we can get recursive inequalities on $\mathsf{f}_{t}$. These show that $\mathsf{f}_{t}$ is in fact a Lyapunov function ; going further, we use discrete versions of Gronwall-type inequalities to finally upper-bound it. To exemplify this reasoning, we present, in the following lemma, a Lyapunov control on $\mathsf{f}_{t}$ using Assumptions 1. Its proof can be found in Appendix B.2.

Under Assumption 1, assume $\gamma\leqslant\left(4\lambda_{\max}\right)^{-1}$. For $t\geqslant 1$ we have the following recursion on the function value $\mathsf{f}_{t}$. For all $i$,

The decrease of the function value $f_{t}$ is controlled by the sum of a bias term –characterizing how fast the initial conditions $m^{0}_{i}$ are forgotten–, and a variance term –characterizing how the noise reverberates through the iterates. All the theorems are proven using the same technique: the aim is to use the inequality recursively to control the variance term. The different Assumptions 1, 3, 5 lead to different variance term. Trying to factorize the proofs in one general bound does not allow for a clear presentation of the results. This is why, despite the apparent redundancy of the proof technique, for the sake of clarity and easy reading, we preferred to split the different proofs of the theorem and factorize only certain technical lemmas. All the proofs of Theorems 1, 2, 3 can be found in Appendix C, respectively in Sections C.1, C.2, C.3.

Experiments

First note that the bound of Theorem 3 is perfectly matched by these two examples. Second, we can see that, the averaged SGD and the final iterate show the same behavior quite accordingly to the theory (see comments on Theorem 3) even if we can notice a slight -but real- better performance (result are shown in $\log$-scale) from the final iterate. However, the main difference is that, as the averaged iterates show some saturation, the final iterate meets a point where it changes to a linear convergence regime (left plot in Figure 1). This adaptivity of the final iterate appearing after time scale $\tau\sim 1/(\gamma\lambda_{\min})$ represents a true asset in choosing the final iterate versus the averaged one. Finally notice that the linear rate regime cannot be seen in the right plot as the maximum number of iterations shown, $n=10^{6}$, is negligible when compared to $\tau\sim d^{1/(1-\alpha)}=300^{1/(1-0.75)}\sim 10^{10}$.

Conclusion and Perspectives

In this paper, we proceed to a detailed analysis of the convergence rates of SGD in the noiseless least-squares setting. We derive a systematic study of the SGD last iterate that leverages a sequence of fine-grained assumptions allowing us to exhibit fast polynomial rates. The absence of additive noise changes dramatically the behavior of SGD: no decaying step sizes or averaging are needed for convergence as constant step-size SGD naturally adapts to the problem. The development of the SGD recursion as an interacting particle systems open many perspectives: can it be used to analyze SGD accelerations? multiple passes over the data? Another significant result is that, from an optimization perspective, we give a prototypal example where the last iterate of constant step-size SGD provably converges in the non-strongly convex case. This raises the following fundamental question: can we extend our method to show the convergence of SGD last iterate in the general non-strongly convex case?

References

Appendix

In Appendix A we present a detailed summary of our results and of the different assumptions. In Appendix B we prove Lemma 4 and 5 which enable to obtain the main SGD recursions. Then in Appendix C we prove our main results: Theorems 1, 2 and 3.

Appendix A Detailed summary of the results and of the different assumptions

Summary on the assumptions. All the assumptions we discussed in the article are summarized in Tables 2 and 3. It clearly shows that the assumptions go stricter and stricter revealing a finer description of the problem. Note also that they can be paired two by two, one sequence corresponding to the features and the other one to the optimum: Assumption 1 with 2, Assumption 3 with 4 and Assumption 5 with 6. The case $\beta\in(-1,0)$, when the optimum is non-attainable, is left aside in the panels for the sake of clarity.

Capacity condition and eigenvalue decay.

In our comments on Assumptions 1,3,5, we make a few observations about the connection between the capacity conditions and the eigenvalue decay. Here, we give a detailed description between them. For example, let us assume Assumption 5,

Appendix B Proofs of the SGD recursions: Lemma 4 and 5

First recall that for $t\geqslant 1$, Eq. (9) gives that

Now we project the above term on $v_{i}v_{i}^{\top}$

For the second part, we prove the recursion Eq. (12) using an induction argument. For the base case $t=1$ we can see that the Lemma holds directly from Eq. (11). Assume that the Lemma holds for $k=t-1$. We know from Eq. (11) that

Merging these above two equalities we have,

B.2 Proof of Lemma 5

Here we prove the Lemma 5. First note that from Eq. (12) of Lemma 4 we have the following recursion,

For $x\in\left(0,1\right)$, we have $x(1-x)^{t}\leq xe^{-xt}\leq 1/t$. Now using the following natural bounds, we get

Appendix C Proofs of the main results

From Lemma 5, we have for all $t\geqslant 1$,

And then, the technique we use throughout all the proofs of this section rest on a control of the second term $\sum_{k=0}^{t-1}\frac{\mathsf{f}_{k}}{(t-k)}$ using the recursion. Indeed, by summing,

Hence, for $\gamma=(4R\ln(T))^{-1}$, we have

C.2 Proof of Theorem 2

The proof of this theorem follows the same principle but uses slightly better estimations. Indeed, we replace the previous $1/n$ bound by a finer bound. This is the statement of the following lemma. For this, we define the following summation $S_{n}(x)$ for some $x\in(0,1/4]$ and $n\geq 2$,

For any $x\in(0,1/4]$, $n\geq 1$, we have the following bound

In the first step, we slightly reformulate this expression, then try to bound that expression by a continuous integral which gives the desired result. From Eq. (18), we have

We compute $(1-x)^{-n}S_{n}(x)$. Note that $g(y)=(1-x)^{-y}/y$ is convex for $y>0$. For any convex function $g$, we have that for any integer $k\geq 2$, $y\in\left[k,k+1\right]$ we have that $g(k)\leq g(y)+g(y-1)$. Indeed, if $g$ is in the increasing phase then $g(y)$ dominates $g(k)$, else $g(y-1)$ dominates in the decreasing phase. Using this we can see that for $k=2\cdots n$,

This leads us to try to bound the integral $\int_{1}^{n+1}\frac{(1-x)^{-y}}{y}$. Using the change of variable $(1-x)^{-y}=e^{t}$. We can rewrite the above integral as follows:

For the sake of clearer notations, let us define $a:=-\ln{\left(1-x\right)}$ such that as $0<x<1$, we have $a>0$. The equation simplifies to the following

For $t\leq 1$, we can see that $e^{t}/t\leq e/t$, where as for $t\geq 2$ we use the bound $e^{t}/t\leq 2e^{t}(t-1)/t^{2}$. Using these bounds,

Re-substituting, $a=-\ln{\left(1-x\right)}$, we can see the $a\geqslant x$ and hence,

Now we use the fact that $x(1-x)^{n}\leq xe^{-nx}\leq 1/(en)$. Leveraging also that $x\leq 1/4$, so that $\ln{\frac{1}{x}}>1$ and $(1-x)^{-1}\leq 4/3$. We can finally bound,

Using the above we prove Theorem 2. Recall that for all $t\geqslant 1$, from Eq.(12) and $\gamma\leq(4\lambda_{max})^{-1}$

The technique we use in this section rests on a control of the second term using the recursion. For this, we will use carefully the bound in Lemma 6. As said before, the only difference with the proof of the previous theorem is the special care in estimations to avoid the logarithm at the price of a slightly more stringent assumption. Indeed, $\forall i$,

Note from Eq.(10), we have $\sum_{i}\lambda_{i}m_{i}^{t}=2\mathsf{f}_{t}$. Lets calculate the remaining terms

C.3 Proof of Theorem 3

Once again we proceed with the same technique as above. The aim here is to tighten the estimation for both the first and the second term with the capacity and source assumptions of the problem (Assumptions 5 and 6).

This estimation rests on the inequality stated in the following Lemma.

For $x\in(0,1)$ and $t\geqslant 1$, for $r>0$ we have the following inequality

Proof Let $x\in(0,1)$, $t\geqslant 1$ and $r>0$. It is standard to note that $(1-x)^{t}\leqslant e^{-tx}$. Hence,

Now, a rapid look at the maximum of the function $x\to x^{r}e^{-tx}$ gives us that it attains its maximum for $x=r/t$. Hence

Again, recall that for all $t\geqslant 1$, from Eq.(12) and $\gamma\leq(4\lambda_{max})^{-1}$, $\forall i$,

Thanks to Lemma 7, we can bound the above expression as,

Note from Eq.(10), we have $\sum_{i}\lambda_{i}m_{i}^{t}=2\mathsf{f}_{t}$. Lets calculate the remaining terms

And from this, we use the same technique as for the previous theorems to bound the second term of the right side of the inequality. To accomplish this we need a bound on the following sum. For $\beta>-1$, $\alpha\in(0,1)$, $T\geqslant 2$,

For $\beta>-1$, $\alpha\in(0,1)$, $T\geqslant 2$, we have the following upper-bound,

where, for $u>0$, $\xi_{u}:=\sum_{k\geqslant 1}\frac{1}{k^{1+u}}$ and we use the following classical notations: $\alpha\wedge\beta=\min(\alpha,\beta)$ and $\alpha\vee\beta=\max(\alpha,\beta)>0$.

Proof Let us assume that $\beta\leqslant\alpha$, we have,

Now the second term is trivially upper bounded by $\xi_{\alpha}$. And for the first term, we use Young’s inequality with coefficient $(p,q)=(\frac{1+\alpha}{\alpha-\beta},\frac{1+\alpha}{1+\beta})$:

This concludes the proof is the case where $\beta\leqslant\alpha$.

Symmetrically, if $\alpha\leqslant\beta$, by a change of variable $t\to T-t$,

Thanks to the Lemma we continue the proof of Theorem 3. Recall Eq. (23): for $T\geqslant 2$,

And applying Lemma 8, and the fact that $\frac{\mathsf{f}_{0}}{T^{1+\alpha}}\leqslant\frac{C_{\beta}}{\gamma^{\beta}T^{1+\alpha\wedge\beta}}$,

Now, for $\gamma$ such that $4(1+\alpha)^{1+\alpha}\xi_{\alpha}\gamma^{1-\alpha}R_{\alpha}\leqslant 1/2$, i.e., for simplicity,

and, hence, we conclude like for the previous theorems. Indeed, for all $T\geqslant$ 1, recalling Eq. (23): for $T\geqslant 2$,