Raphaël Berthier
email: raphael.berthier@inria.fr

Francis Bach
email: francis.bach@inria.fr

Pierre Gaillard
email: pierre.gaillard@inria.fr

Tight Nonparametric Convergence Rates for Stochastic Gradient Descent under the Noiseless Linear Model

In the context of statistical supervised learning, the noiseless linear model assumes that there exists a deterministic linear relation Y = θ * , Φ(U ) between the random output Y and the random feature vector Φ(U ), a potentially non-linear transformation of the inputs U . We analyze the convergence of single-pass, fixed step-size stochastic gradient descent on the least-square risk under this model. The convergence of the iterates to the optimum θ * and the decay of the generalization error follow polynomial convergence rates with exponents that both depend on the regularities of the optimum θ * and of the feature vectors Φ(U ). We interpret our result in the reproducing kernel Hilbert space framework. As a special case, we analyze an online algorithm for estimating a real function on the unit hypercube from the noiseless observation of its value at randomly sampled points; the convergence depends on the Sobolev smoothness of the function and of a chosen kernel. Finally, we apply our analysis beyond the supervised learning setting to obtain convergence rates for the averaging process (a.k.a. gossip algorithm) on a graph depending on its spectral dimension.

Introduction

Linear regression is widely used in statistical supervised learning, sometimes in the implicit form of kernel regression. A large theory describes the performance (reconstruction and generalization errors) of various algorithms (penalized least-squares, stochastic gradient descent, . . . ) under various data models (e.g., noisy or noiseless linear model) and the corresponding minimax bounds. In nonparametric estimation theory, one seeks bounds independent of the dimension of the underlying feature space [START_REF] Györfi | A distribution-free theory of nonparametric regression[END_REF][START_REF] Tsybakov | Introduction to Nonparametric Estimation[END_REF]: these bounds describe best the observed behavior in many modern linear regressions, where the data are inherently high-dimensional or where a kernel associated to a highdimensional feature map is used. In this paper, we provide nonparametric bounds for stochastic gradient descent under the noiseless linear model and under small perturbations of this model.

Under the noiseless linear model, we assume that there exists a ground-truth linear relation Y = θ * , X between the feature vector X and the output Y ∈ R. The feature vector X may be itself a non-linear transformation of the inputs U , explicitly computed through a feature map X = Φ(U ) or implicitly defined through a positive-definite kernel k(U, U ) [START_REF] Hofmann | Kernel methods in machine learning[END_REF]. The noiseless linear model assumes that there exists a linear predictor in feature space with zero generalization error. The difficulty to approximate this optimal prediction rule θ * from independent identically distributed (i.i.d.) samples (X 1 , Y 1 ), . . . , (X n , Y n ) depends on some measure of the complexity of θ * .

The noiseless assumption is relevant for some basic vision or sound recognition tasks, where there is no ambiguity of the output Y given the input U , but the rule determining the output from the input can be complex. An example from [START_REF] Jun | Kernel truncated randomized ridge regression: Optimal rates and low noise acceleration[END_REF]Section 6] is the classification of images of cats versus dogs. For typical images, the output is unambiguous; humans indeed achieve a near-zero error. In sound recognition, one could think of the recovery of the melody from a tune, an unambiguous (but tremendously complex!) task.

Note that in the noiseless model, there is still the randomness of the sampling of X 1 , . . . , X n , sometimes called multiplicative noise because algorithms end up multiplying random matrices [START_REF] Dieuleveut | Harder, better, faster, stronger convergence rates for least-squares regression[END_REF]. Given those inputs, the outputs Y 1 , . . . , Y n are deterministic: there is no additive noise, and thus the noiseless linear model we consider in this paper is a simplification of problems with low additive noise.

The large dimension and number of samples in modern datasets motivate the use of first-order online methods [START_REF] Bottou | On-line learning for very large data sets[END_REF][START_REF] Bottou | The tradeoffs of large scale learning[END_REF]. We study the archetype of these methods: single-pass, constant step-size stochastic gradient descent with no regularization, referred to as simply "SGD" in the following.

Contributions. Our theoretical results and simulation agree to the following: under the noiseless linear model, the iterates of SGD converge to the optimum θ * and the generalization error of SGD vanishes as the number of samples increases. Moreover, the convergence rate of SGD is determined by the minimum of two parameters: the regularity of the optimum θ * and the regularity of the feature vectors X, where regularities are measured in terms of power norms of the covariance matrix Σ = E[X ⊗ X], see Section 2 for precise definitions and statements. Our analysis of the convergence is tight as we prove upper and lower bounds on the performance of SGD that almost match. Thus SGD shows some adaptivity to the complexity of the problem. In Section 4, we study the robustness of our results when the noiseless linear assumption does not hold, but the generalization error of the optimal linear regression is small. We prove that the asymptotic generalization error of SGD deteriorates by a constant factor, proportional to this optimal generalization error. Two extensions of our results are studied. First, in Section 3.1, the extension to kernel regression is derived, with, as a special case, the application to the interpolation of a real function f * on the torus [0, 1] d from the observation of its value at randomly uniformly sampled points. In the latter case, we show that the rate of convergence depends on the Sobolev smoothness of the function f * and of the interpolating kernel. Second, beyond supervised learning, our abstract result can be seen as a result on products of i.i.d. linear operators on a Hilbert space. In Section 3.2, we use this result to study a linear stochastic process, the averaging process on a graph, which models a key algorithmic step in decentralized optimization, the gossip algorithm [START_REF] Shah | Gossip algorithms[END_REF][START_REF] Nedic | Constrained consensus and optimization in multi-agent networks[END_REF]. We prove polynomial convergence rates depending on the spectral dimension of the graph. Finally, in Section 3.3, a toy application instantiates our results in the special case of Gaussian features.

Comparison to the existing literature on linear / kernel regression. There is an extensive research on the performance of different estimators in nonparametric supervised learning, however almost all of them do not consider the special case of the noiseless linear model [START_REF] Györfi | A distribution-free theory of nonparametric regression[END_REF][START_REF] Caponnetto | Optimal rates for the regularized least-squares algorithm[END_REF][START_REF] Tsybakov | Introduction to Nonparametric Estimation[END_REF][START_REF] Fischer | Sobolev norm learning rates for regularized least-squares algorithm[END_REF]. The difference is significant; for instance, rates faster than O(n -1 ) for the least-square risk are impossible with additive noise, while in this paper we prove that SGD can converge with arbitrarily fast polynomial rates. Some of these works analyse the performance of SGD [START_REF] Ying | Online gradient descent learning algorithms[END_REF][START_REF] Bach | Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)[END_REF][START_REF] Tarrès | Online learning as stochastic approximation of regularization paths: Optimality and almost-sure convergence[END_REF][START_REF] Rosasco | Learning with incremental iterative regularization[END_REF][START_REF] Dieuleveut | Nonparametric stochastic approximation with large step-sizes[END_REF][START_REF] Dieuleveut | Harder, better, faster, stronger convergence rates for least-squares regression[END_REF][START_REF] Lin | Optimal convergence for distributed learning with stochastic gradient methods and spectral-regularization algorithms[END_REF][START_REF] Pillaud-Vivien | Statistical optimality of stochastic gradient descent on hard learning problems through multiple passes[END_REF][START_REF] Mücke | Beating SGD saturation with tail-averaging and minibatching[END_REF]. However, because of the additive noise of the data, convergence requires averaging or decaying step sizes. As a notable exception, [START_REF] Jun | Kernel truncated randomized ridge regression: Optimal rates and low noise acceleration[END_REF] studies a variant of kernel regularized least-squares and notices that the rate of convergence improves on noiseless data compared to noisy data. However, their rates are not directly comparable to ours as they assume that the optimal predictor is outside of the kernel space while we focus in Section 3.1 on the attainable case where the optimal predictor is in this space. We make a more precise comparison of this work with our results in Remark 2.

While our work focuses on the test error, a recent trend studies the ability of SGD to reach zero training error in the so-called "interpolation regime", that is in over-parametrized models where a perfect fit on the training data is possible [START_REF] Schmidt | Fast convergence of stochastic gradient descent under a strong growth condition[END_REF][START_REF] Ma | The power of interpolation: Understanding the effectiveness of SGD in modern over-parametrized learning[END_REF][START_REF] Cevher | On the linear convergence of the stochastic gradient method with constant step-size[END_REF]. Even with a fixed step size, SGD is shown to achieve zero-training error. However, these results are significantly different from ours: zero training error does not give any information on the generalization ability of the learned models, and the "interpolation regime" does not imply the noiseless model. The authors of [START_REF] Vaswani | Fast and faster convergence of sgd for over-parameterized models and an accelerated perceptron[END_REF] study a mixed framework that includes both the interpolation regime and the noiseless model, depending on whether SGD is seen as a stochastic algorithm minimizing the generalization error or the training error. An acceleration of SGD is studied, depending on the convexity property of the loss, but not on the nonparametric regularity of the problem.

The field of scattered data approximation [START_REF] Wendland | Scattered Data Approximation[END_REF] studies the estimation of a function from the observation of its values at (possibly random) points, considered in Section 3.1. Again, most of the work focuses on the case where the observation of the values is noisy. We found two exceptions that consider the noiseless case. In [START_REF] Bauer | Nonparametric estimation of a function from noiseless observations at random points[END_REF], a minimax rate of Ω((log n/n) p/d ) is shown for estimating a p-smooth function on [0, 1] d in L ∞ norm using n independent uniformly distributed points; the minimax rate is reached with a spline estimate. In [START_REF] Kohler | Optimal global rates of convergence for interpolation problems with random design[END_REF], a minimax rate of Ω(1/n p ) in shown for the same problem, but in the special case of d = 1 and estimation in L 1 norm; the minimax rate is reached with some nearest neighbor polynomial interpolation. Our results are not rigorously comparable with these as we consider the approximation in L 2 norm and a definition of smoothness different from theirs. However, roughly speaking, our convergence rate in Section 3.1 of Ω(1/n 1-d/(2p+d) ) when p > d/2 is much slower than theirs. Note that previous estimators could not be computed in an online fashion, and thus have a significantly larger running time. But in general, this suggests that SGD might not achieve the nonparametric minimax rates under the noiseless linear model.

Linear regression

Setting and main results

We consider the regression problem of learning the linear relationship between a random feature variable X ∈ H and a random output variable Y ∈ R. The feature space H is assumed to be a Hilbert space with scalar product ., . and norm . . We assume a noiseless linear model: there exists θ * ∈ H such that Y = θ * , X almost surely (a.s.). In the online regression setting, we learn θ * from i.i.d. observations (X 1 , Y 1 ), (X 2 , Y 2 ), . . . of (X, Y ). SGD proceeds as follows: it starts with the non-informative initialization θ 0 = 0 and at iteration n, with current estimate θ n-1 , it estimates the risk function on the observation

(X n , Y n ), R n (θ) = ( θ, X n -Y n )
2 /2 and it performs one step of gradient descent on R n :

θ n = θ n-1 -γ∇R n (θ n-1 ) = θ n-1 -γ ( θ n-1 , X n -Y n ) X n = θ n-1 -γ θ n-1 -θ * , X n X n . (1)
The risk R n (θ) is an unbiased estimate of the population risk, also called generalization error,

R(θ) = 1 2 E ( θ, X -Y ) 2 = 1 2 E θ -θ * , X 2 .
We assume the feature variable to be uniformly bounded, namely that there exists a constant R 0 < ∞ such that X 2 R 0 a.s.

(2) We can then define the covariance operator

Σ = E [X ⊗ X] of X, where if x ∈ H, x ⊗ x is the bounded linear operator θ ∈ H → θ, x x. Finally, note that, R(θ) = 1 2 θ -θ * , Σ (θ -θ * ) .
We do not assume that the linear operator Σ is inversible as this is incompatible in infinite dimension with the boundedness assumption in Eq. [START_REF] Aldous | A lecture on the averaging process[END_REF]. Throughout this paper, we use the following convenient notation: if α is a positive real and θ a vector, Σ -α/2 θ 2 = θ, Σ -α θ := inf θ 2 θ such that θ = Σ α/2 θ , with the convention that it is equal to ∞ when θ / ∈ Σ α/2 (H). We have two theorems (upper and lower bounds) showing tight convergence rates for SGD. Theorem 1 (upper bound). Assume that there exists a non-negative real number α such that (a) (regularity of the optimum) θ * ∈ Σ α/2 (H), i.e., Σ -α/2 θ * < ∞, and (b) (regularity of the feature vector) X ∈ Σ α/2 (H) a.s., and there exists a constant R α < ∞ such that Σ -α/2 X 2 R α a.s.

E [R(θ k )] C n α+1 , where C = α α γ α Σ -α/2 θ * 2 + R α R 0 θ * 2 and C = 2 α α α γ α+1 Σ -α/2 θ * 2 + R α R 0 θ * 2 .
Assumption (a) is classical in the non-parametric kernel literature [START_REF] Caponnetto | Optimal rates for the regularized least-squares algorithm[END_REF]: it is often called complexity of the optimum, or source condition. Assumption (b) is made in [START_REF] Pillaud-Vivien | Statistical optimality of stochastic gradient descent on hard learning problems through multiple passes[END_REF]. It implies that

Tr(Σ 1-α ) = E[Tr(XX T Σ -α )] = E[X T Σ -α X] R α .
This last condition, called capacity condition [START_REF] Pillaud-Vivien | Statistical optimality of stochastic gradient descent on hard learning problems through multiple passes[END_REF], is sometimes stated under the form of a given decay of the eigenvalues of Σ; it is related to the effective dimension of the problem [START_REF] Caponnetto | Optimal rates for the regularized least-squares algorithm[END_REF]. Theorem 2 (lower bound). Assume that there exists a positive real number α such that one of the two following conditions holds:

(a) (irregularity of the optimum) θ * / ∈ Σ α/2 (H), i.e., Σ -α/2 θ * = ∞, or (b) (irregularity of the feature vector) with positive probability, X / ∈ Σ α/2 (H) and X, θ * = 0.

Assume further 0 < γ 1/R 0 . The iterates θ n of SGD with step-size γ satisfy for all ε > 0,

1. (reconstruction error) E θ n -θ * 2 is not asymptotically dominated by 1/n α+ε , 2. (generalization error) E [R(θ n )] is not asymptotically dominated by 1/n α+1+ε .
The take-home message of Theorems 1, 2 is that the convergence rate of SGD is governed by two real numbers: the regularity α 1 of the optimum, that is the supremum of all α such that θ * ∈ Σ α/2 (H), and the regularity α 2 of the features, that is the supremum of all α such that X ∈ Σ α/2 (H) almost surely. The polynomial convergence rate of SGD is roughly of the order of n -α for the reconstruction error and n -α-1 for the generalization error with α = min(α 1 , α 2 ): one of the two regularities is a bottleneck for fast convergence. See Section 3.1 for an application to the optimal choice of a reproducing kernel Hilbert space. The exponent α 1 corresponds to the decay of the errors of the gradient descent on the population risk R. However, due to the multiplicative noise, the convergence of SGD is slowed down by the irregularity of the feature vectors if α 2 < α 1 .

In the theorems, the constraint on the step-size 0 < γ 1/R 0 is independent of the time horizon n and of the regularities α 1 , α 2 . Thus fixed step-size SGD shows some adaptivity to the regularity of the problem.

In Section 3, we give extensive numerical evidence that the polynomial rates n -α and n -(α+1) in the bounds are indeed sharp in describing convergence rate of SGD. We end this section with a few remarks on Theorems 1, 2. They articulate the significance of the results, but are non-essential to the rest of this paper. Remark 1. Our upper bound and lower bound on the generalization errors do not match exactly. Indeed, we prove an upper bound on the minimum risk of the past iterates, where we prove a lower bound on a larger quantity, the risk of the last iterate. To the best of our knowledge, it is an open question whether one can prove an upper bound for the last iterate under our assumptions: more precisely, does E [R(θ n )] C /n α+1 hold for some constant C ? Remark 2 (related literature). In the case α = 0, where no regularity assumption is made on the optimum or the features (apart from being bounded), we upper-bound min k=1,...,n E [R(θ k )] by O(n -1 ). A similar result was shown in [START_REF] Bach | Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)[END_REF]: the excess risk for averaged constant-step size SGD is asymptotically dominated by n -1 on any least-squares problem-not necessarily a noiseless one. It is remarkable that under the noiseless linear setting, no averaging or decay of the step-size is needed to obtain the same convergence rate.

The article [START_REF] Jun | Kernel truncated randomized ridge regression: Optimal rates and low noise acceleration[END_REF] also studies the performance of an algorithm, a variant of kernel regularized leastsquares, in the noiseless non-parametric setting. However, they do not exploit when the function is more regular than being in the kernel space, i.e., when α 1 > 0 with our notation, β > 1/2 with theirs. In fact, they leave this case as an open problem in their Section 6. Thus, a fair comparison can only be made when α 1 = 0, β = 1/2. In this case, SGD and the algorithm of [START_REF] Jun | Kernel truncated randomized ridge regression: Optimal rates and low noise acceleration[END_REF] both achieve the same rate O(n -1 ). Remark 3. The theorems stated above stay true if one weakens the assumptions in the following way, where denotes the semi-definite order:

• assume E X 2 X ⊗ X R 0 Σ instead of X 2 R 0 a.s.
, and

• assume E [ X, Σ -α X X ⊗ X] R α Σ instead of X, Σ -α X R α a.s.
This weaker set of assumptions is useful in the case of non-bounded features, like the Gaussian features of Appendix 3.3. We thus take special care in using only these weaker assumptions in the proofs of Theorems 1, 2, 3 and 4. However we prefer stating results with the stronger assumptions for the sake of clarity. Remark 4 (Application of Theorem 1 in finite dimension). If H is finite-dimensional and Σ is of full rank, the assumptions of Theorem 1 hold for any α 0. Thus SGD converges faster than any polynomial; in fact one can check that an exponential upper bounds on the reconstruction and generalization errors of the form C exp(-λ min (Σ)t) hold, where λ min (Σ) is the smallest eigenvalue of Σ. Although the latter bound is asymptotically better than polynomial rates, for moderate time scales the polynomial rates may describe best the observed behavior; for an illustration of this fact on the averaging process, see Section 3.2 and in particular the discussion following Corollary 1.

Theorems 1 and 2 are extended in the next section and proved in Appendices A and B respectively. The generalization of Theorem 1 beyond the noiseless linear model is exposed in Section 4. The reader interested mostly by applications of Theorems 1 and 2 can jump directly to Section 3.

Regularity functions and general results

The main difficulty in the proof of Theorems 1 and 2 is that deriving closed recurrence relations for the expected reconstruction and generalization errors is not straightforward. In this paper, we propose to study the norm of θ n -θ * associated to different powers of the covariance Σ. More precisely, define

ϕ n (β) = E θ n -θ * , Σ -β (θ n -θ * ) ∈ [0, ∞] , β ∈ R . (3)
We call ϕ n the regularity function at iteration n. In particular,

ϕ n (0) = E[ θ n -θ * 2 ] and ϕ n (-1) = 2E[R(θ n )] .
The sequence of regularity functions ϕ n , n 1 satisfies a closed recurrence inequality (Property 2 in Appendix A) which is central to our proof strategy. Theorems 1 and 2 can be extended to the following estimates on the regularity functions ϕ n (β) on the full interval β ∈ [-1, α] (see proofs in Appendices A and B respectively). . Theorem 3 (upper bound). Under the assumptions of Theorem 1, we have for all n 1,

1. for all β ∈ [0, α], ϕ n (β) C n α-β , 2. for all β ∈ [-1, 0), min k=0,...,n ϕ k (β) C n α-β , where C = α α-β γ α-β Σ -α/2 θ * 2 + R α R 0 θ * 2 , C = 2 α-β α α γ α-β Σ -α/2 θ * 2 + R α R 0 θ * 2 .
Theorem 4 (lower bound). Under the assumptions of Theorem 2, for all β ∈ [-1, α], for all ε > 0, ϕ n (β) is not asymptotically dominated by 1/n α-β+ε .

3 Applications

Kernel methods and interpolation in Sobolev spaces

A main case of application of our results is the reproducing kernel Hilbert space (RKHS) setting [START_REF] Hofmann | Kernel methods in machine learning[END_REF].

In this setting, the space H is typically large or infinite-dimensional, and we do not have a direct access to the feature variable X ∈ H. Instead, we have access to some random input variable U ∈ U such that X = Φ(U ) for some fixed feature map Φ : U → H. It is then natural to associate a vector θ ∈ H with the function f θ ∈ L 2 (U) defined by

f θ (u) = θ, Φ(u) .
If the positive-definite kernel k(u, u ) = Φ(u), Φ(u ) can be computed efficiently, SGD can be "kernelized" [START_REF] Ying | Online gradient descent learning algorithms[END_REF][START_REF] Tarrès | Online learning as stochastic approximation of regularization paths: Optimality and almost-sure convergence[END_REF][START_REF] Rosasco | Learning with incremental iterative regularization[END_REF][START_REF] Dieuleveut | Nonparametric stochastic approximation with large step-sizes[END_REF], i.e., the iteration can be written directly in terms of f n := f θn :

f n = f n-1 -γ(f n-1 (U n ) -Y n )k(U n , .) = f n-1 -γ(f n-1 -f * )(U n )k(U n , .)
where

X n = Φ(U n ) and f * (u) := f θ * (u) = θ * , Φ(u) . Note that in the kernel literature, the mapping θ → f θ is used to identify H with a subspace of L 2 (U); indeed, if Σ = E [Φ(U ) ⊗ Φ(U )]
has dense range, the mapping is injective. Using this identification, Theorems 1 and 2 can be applied to obtain bounds in the "attainable" case, meaning that the optimal predictor f * ∈ L 2 (U) is in the RKHS H. This gives decay rates for the RKHS norm f n -f * := θ n -θ * which is inherited from H, but also for the population risk R(θ n ) which is reinterpreted as the half squared L 2 -distance between the associated f n and the optimal predictor f * . Indeed,

R(θ n ) = 1 2 E θ n -θ * , Φ(U ) 2 = 1 2 E (f n (U ) -f * (U )) 2 = 1 2 f n -f 2 L 2 (U ) .
Application: interpolation in Sobolev spaces. To illustrate our results, we consider the case where U is the torus [0, 1] d , U is uniformly distributed on U and k is a translation-invariant kernel: k(u, u ) = t(u -u ) where t is a square-integrable 1-periodic function on [0, 1] d . The kernel k is positive-definite if and only if the Fourier transform of t is positive [START_REF] Wahba | Spline Models for Observational Data[END_REF]. This imposes, in particular, that t is maximal at 0. Thus the update rule

f n = f n-1 -γ (f n-1 (U n ) -f * (U n )) t(. -U n ) (4) corrects f n so that the value f n (U n ) is closer to the observed value f * (U n ) than f n-1 (U n ).
f 2 H s per = k∈Z d | f (k)| 2 1 + |k| 2 s < ∞ .
Assume that the Fourier serie of t satisfies a power-law decay: there exists c, C > 0 such that:

c 1 + |k| 2 -s/2-d/4 t(k) C 1 + |k| 2 -s/2-d/4 , k ∈ Z d .
This condition does not cover C ∞ kernel, including the Gaussian kernel; it is relevant for less regular kernel, that have a power decay in Fourier. This condition is satisfied, for instance, by the Wendland functions [33, Theorem 10.35], or in dimension d = 1 by the kernels corresponding to splines of order s, see [START_REF] Wahba | Spline Models for Observational Data[END_REF] or [START_REF] Pillaud-Vivien | Statistical optimality of stochastic gradient descent on hard learning problems through multiple passes[END_REF]. The latter can be computed using the polylogarithm or-for special values of s-the Bernoulli polynomials.

We have t ∈ H s per if and only if s < s, thus s measures the Sobolev smoothness of k. The operator Σ is the convolution with t and thus

f 2 = f, Σ -1 f L 2 k∈Z d | f (k)| 2 1 + |k| 2 s/2+d/4 = f 2 H s/2+d/4 per , (5)
where denotes the equality up to positive multiplicative constants. To predict the convergence rate of (4), we check the assumptions of Theorems 1, 2. Computations similar to (5) give (a) (regularity of the optimum)

f * , Σ -α f * f * , Σ -α-1 f * L 2 f * 2 H (s/2+d/4)(α+1) per Assume f * ∈ H r per . We have f * , Σ -α f * < ∞ if α 2r s+d/2 -1.
k(u, .), Σ -α k(u, .) = k(u, .) 2 H (s/2+d/4)(α+1) per = t s 2 H (s/2+d/4)(α+1) per = k∈Z d (1 + k 2 ) (s/2+d/4)(α-1) . Thus k(u, .), Σ -α k(u, .) < ∞ if and only if α < 1 -d s+d/2
. The regularities of the optimum and of the feature vector are non-negative if the smoothness s of the kernel t satisfies d/2 < s 2r -d/2, where r is the smoothness of f * . In this case the polynomial rate of decay of the algorithm is given by the exponent

α * = min 2r s + d/2 -1, 1 - d s + d/2 . (6)
Note that, given a function f * , this rate is maximal when s = r, i.e., the smoothness of the kernel coincides with the smoothness of the function, in which case α * = 1 -d r+d/2 . Theorems 1, 2 give the convergence rates in terms of L 2 norm and RKHS norm, which happens to be a Sobolev norm. The more general Theorems 3 and 4 gives convergence rates in terms of a continuity of fractional Sobolev norms, some weaker and some stronger than the RKHS norm.

In Figure 1, we show the decay of the L 2 norm in the interpolation of a function f * on [0, 1] of smoothness 2 using kernels of smaller, matching and larger smoothness. In each case, the rate predicted by ( 6) is sharp, and the convergence is indeed fastest when the smoothnesses match.

Decay rate of the averaging process

The averaging process is a stochastic process on a graph, mostly studied as a model for asynchronous gossip algorithms on networks. Gossip algorithms are subroutines used to diffuse information throughout networks in distributed algorithms [START_REF] Shah | Gossip algorithms[END_REF], in particular in distributed optimization [START_REF] Nedic | Constrained consensus and optimization in multi-agent networks[END_REF].

Let G be a finite undirected connected graph with vertex set V of cardinality N and edge set E of cardinality M . The averaging process is a discrete process on functions x : V → R defined as follows. The initial configuration x 0 = e v : V → R is the indicator function of some distinguished vertex v ∈ V, i.e., x 0 (v ) = 1 and x 0 (v) = 0 if v = v . At each iteration, we choose a random edge and replace the values at the ends of the edge by the average of the two current values. In equations, at iterations n, given x n-1 , sample an edge e n = {v n , w n } uniformly at random from E and independently from the past, and define

x n (v n ) = x n (w n ) = x n-1 (v n ) + x n-1 (w n ) 2 , x n (v) = x n-1 (v) , v = v n , w n . ( 7
)
As the graph is connected, all functions values x n (v), v ∈ V converge to 1/N as n → ∞. The study of the averaging process aims at describing how the speed of convergence depends on the graph G.

The averaging process can be seen as a prototype interacting particle system, or finite markov information-exchange process according to Aldous's terminology [START_REF] Aldous | Interacting particle systems as stochastic social dynamics[END_REF]. However, the linear structure of the updates of the averaging process makes the analysis simpler than in other interacting particle systems; this property is key in applying the results of Section 2.

In this section, we introduce a quantitive version of the notion of spectral dimension of a graph (see [START_REF] Avrachenkov | Eigenvalues and spectral dimension of random geometric graphs in thermodynamic regime[END_REF] and references therein for other definitions). We use this quantity to build polynomial convergence rates for the expected squared 2 -distance to optimum E v∈V (x n (v) -1/N )

2
and for the expected energy E 1 2 {v,w}∈E (x n (v) -x n (w)) 2 . The comparison with other known convergence bounds is made. We add numerical experiments showing that our bounds describe the observed behavior in some classical large graphs, for an intermediate number of iterations.

Let L = {v,w}∈E (e v -e w )(e v -e w ) be the Laplacian of the graph. It is a positive semi-definite operator. The spectral measure of L at a vertex v ∈ V is the unique measure σ v such that for all continuous real function f ,

e v , f (L)e v = dσ v (λ)f (λ) . If 0 = λ 0 < λ 1 . . . λ N -1
are the eigenvalues of L and u 0 = 1, u 1 , . . . , u N -1 are the corresponding normalized eigenvectors, then

σ v (dλ) = N -1 i=0 (u i (v)) 2 δ λi (dλ) . We say that G is of spectral dimension d 0 with constant V > 0 if ∀v ∈ V , ∀E ∈ (0, ∞) , σ v ((0, E]) V -1 E d/2 .
A typical example motivating this definition is the following. This result is proved in Appendix D. Similar results were proved for supercritical percolation bonds in [START_REF] Mathieu | Isoperimetry and heat kernel decay on percolation clusters[END_REF] and for the random geometric graphs in [START_REF] Avrachenkov | Eigenvalues and spectral dimension of random geometric graphs in thermodynamic regime[END_REF].

When the graph is large, the probability of sampling a given edge decays to 0. It is natural to define a rescaled time t = n/M so that the expected number of times a given edge is sampled during a unit time interval does not depend on M (and is equal to 1). Corollary 1 (of Theorem 1). Assume that G is of spectral dimension d with constant V , and denote δ max the maximal degree of the nodes in the graph. Then, for all t = n/M 2,

1. E v∈V x M t (v) - 1 N 2 D(d, V, δ max ) log t t d/2 ,

min

0 s t E   1 2 {v,w}∈E (x M s (v) -x M s (w)) 2   D (d, V, δ max ) log t t d/2+1 , where D(d, V, δ max ) = 2 log 2 d d/2+1 V -1 δ max and D (d, V, δ max ) = 2 d/2+2 log 2 d d/2+1 V -1 δ max .
See Appendix C for the proof. Note that as G is a finite graph, G can be of any spectral dimension d for some potentially large constant V . However, for many families of graphs of increasing size, such as the toruses T d Λ , Λ 1, the spectral dimension constant V corresponding to the dimension d and the maximum degree δ max remain bounded independently of the size of the graph. In that case, the bounds of Corollary 1 are independent of the size of the graph. These bounds should be compared to the known exponential convergence bounds of [START_REF] Aldous | A lecture on the averaging process[END_REF] or [START_REF] Shah | Gossip algorithms[END_REF]: they are of the form O(exp(-γt)) where γ is the spectral gap of the Laplacian of the graph, the distance between the two minimal eigenvalues of the Laplacian. Although asymptotically faster, these bounds are only relevant on the typical scale t 1/γ. In many graphs of interests, the spectral gap γ vanishes as the size of the graph increases; for instance, when G = T d Λ , γ is of the order of 1/Λ 2 . As a consequence, for large graphs and moderate number of iterations, the spectral dimension based where C and C are constants chosen to match best the empirical observations for each plot. bounds describe the observed behavior where spectral gap based bounds do not apply. Indeed, in Figure 2, simulations on a large circle T 1 300 and on a large torus T 2 40 display polynomial decay rates, with polynomial exponents coinciding with those of the corresponding bounds of Corollary 1. Note that, if pushed on a longer time scale, the simulations would have shown the exponential convergence due to finite graph effects. This incapacity of spectral gap to describe the transient behavior had already motivated the authors of [START_REF] Berthier | Accelerated gossip in networks of given dimension using Jacobi polynomial iterations[END_REF] to use the spectral dimension to describe the behavior and to design accelerations of the gossip algorithm. However, the analyses of this paper control only the expected process E[x n ]: the random sampling of the edges is averaged out.

While the polynomial exponents are sharp, we expect the logarithmic factors to be an artifact of the method of proof.

In the case d = 0 and V = 1, where no assumption on the structure of the graph is made, the fact that the minimal past energy is O(n -1 ) (neglecting the logarithmic factor) has been noticed by Aldous in [2, Proposition 4]. Aldous leaves as an open problem whether one can prove a bound without taking a minimum; this is a special case of our Remark 1.

Linear regression with Gaussian features

In the setting of Section 2.1, we assume X to be centered Gaussian process of covariance Σ where Σ is a bounded symmetric semidefinite operator. As X is not bounded a.s., we need to use the weaker set of assumptions given in Remark 3. We thus need to compute R 0 such that E X 2 X ⊗ X R 0 Σ and α, R α such that E [ X, Σ -α X X ⊗ X] R α Σ. We show here that these conditions are in fact simple trace conditions on Σ, sometimes called capacity conditions [START_REF] Pillaud-Vivien | Statistical optimality of stochastic gradient descent on hard learning problems through multiple passes[END_REF]. Lemma 1. If X ∼ N (0, Σ) and A is a bounded symmetric operator such that Tr(ΣA) < ∞,

E [ X, AX X ⊗ X] = 2ΣAΣ + Tr(ΣA)Σ 2 Σ 1/2 AΣ 1/2 H→H + Tr(ΣA) Σ .
Proof. Diagonalize Σ = i 1 λ i e i ⊗ e i . Then there exists independent standard Gaussian random variables X i , i 0 such that

X = i λ 1/2 i X i e i . Let i, j 1. e i , E [ X, AX X ⊗ X] e j = E [ X, AX e i , X ⊗ Xe j ] = E X, AX λ 1/2 i X i λ 1/2 j X j = λ 1/2 i λ 1/2 j k,l A k,l λ 1/2 k λ 1/2 l E [X i X j X k X l ] .
As X i , i 1 are centered independent random variables, the quantity E [X i X j X k X l ] is 0 in many cases. More precisely,

• if i = j, the general term of the sum in non-zero only when k = i and l = j or k = j and l = i. This gives e i , E [ X, AX X ⊗ X] e j = 2A i,j λ i λ j .

• if i = j, the general term of the sum is non-zero only when k = l. This gives

e i , E [ X, AX X ⊗ X] e i = λ i k A k,k λ k E X 2 i X 2 k = λ i k =i A k,k λ k + 3λ 2 i A i,i = λ i k A k,k λ k + 2λ 2 i A i,i .
In both cases,

e i , E [ X, AX X ⊗ X] e j = 2λ i λ j A i,j + k A k,k λ k λ i 1 i=j .

Note that

Tr(AΣ) = k e k , ΣAe k = k λ k A k,k .
Thus we get e i , E [ X, AX X ⊗ X] e j = 2λ i λ j A i,j + Tr(AΣ)λ i 1 i=j = 2 e i , ΣAΣe j + Tr(AΣ) e i , Σe j = e i , [2ΣAΣ + Tr(ΣA)Σ] e j .

From this lemma with A = Id, we compute R 0 = 2 Σ H→H + Tr(Σ), and with A = Σ -α , we compute R α = 2 Σ 1-α H→H +Tr(Σ 1-α ). Thus in the Gaussian case, the condition of (weak) regularity of the features is given by Tr(Σ 1-α ) < ∞.

Simulations. We present simulations in finite but large dimension d = 10 5 , and we check that dimension-independent bounds describe the observed behavior. We artificially generate regression problems with different regularities by varying the decay of the eigenvalues of the covariance Σ and varying the decay of the coefficients of θ * .

Choose an orthonormal basis e 1 , . . . , e d of H. We define Σ = d i=1 i -β e i ⊗ e i for some β 1 and θ * = d i=1 i -δ e i for some δ 1/2. We now check the condition on α such that the assumptions (a) and (b) are satisfied.

(a) θ * , Σ -α θ * = d i=1 θ * , e i 2 i βα = d i=1 i -2δ+αβ
, which is bounded independently of the dimension d if and only if

∞ i=1 i -2δ+αβ < ∞ ⇔ -2δ + αβ < -1 ⇔ α < 2δ-1 β . (b) Tr(Σ 1-α ) = d i=1 i -β(1-α) , which is bounded independently of the dimension d if and only if ∞ i=1 i -β(1-α) < ∞ ⇔ -β(1 -α) < -1 ⇔ α < 1 -1/β.
Thus the corollary gives dimension-independent convergence rates for all α < α * = min 1 -1 β , 2δ-1 β .

In Figure 3, we show the evolution of θ n -θ * 2 and R(θ n ) for two realizations of SGD. We chose the stepsize γ = 1/R 0 = 1/(2 Σ H→H + Tr(Σ)). The two realizations represent two possible different regimes: We compare with the curves D/n α * and D /n α * +1 with hand-tuned constants D and D to fit best the data for each plot. In both regimes, our theory is sharp in predicting the exponents in the polynomial rates of convergence of θ n -θ * 2 and R(θ n ).

Robustness to model mispecification

In this section, we describe how the results of Section 2 are perturbed in the case where a linear relation Y = θ * , X a.s. does not hold. Following the statistical learning framework, we assume a joint law on (X, Y ). We further assume that there exists a minimizer θ * ∈ H of the population risk R(θ):

θ * ∈ argmin θ∈H R(θ) = 1 2 E (Y -θ, X ) 2 .
This general framework encapsulates two types of perturbations of the noiseless linear model:

• (variance) The output Y can be uncertain given X. For instance, under the noisy linear model, Y = θ * , X + Z, where Z is centered and independent of X. In this case,

R(θ * ) = E[Z 2 ] = E[var (Y |X)].
• (bias) Even if Y is deterministic given X, this dependence can be non-linear: Y = ψ(X) for some non-linear function ψ. Then R(θ * ) is the squared L 2 distance of the best linear approximation to ψ: R(θ

* ) = 1 2 E (ψ(X) -θ * , X ) 2 .
In the general framework, the optimal population risk is a combination of both sources

R(θ * ) = 1 2 E [var (Y |X)] + 1 2 E (E[Y |X] -θ * , X ) 2 .
Given i.i.d. realizations (X 1 , Y 1 ), (X 2 , Y 2 ), . . . of (X, Y ), the SGD iterates are defined as

θ 0 = 0 , θ n = θ n-1 -γ ( θ n-1 , X n -Y n ) X n . (8)
Apart from the new definition of θ * , we repeat the same assumptions as in Section 2: let R 0 < ∞ be such that X 2 R 0 a.s., denote

Σ = E[X ⊗ X] and ϕ n (β) = E θ n -θ * , Σ -β (θ n -θ * ) . Theorem 5.
Under the assumptions of Theorem 1,

min k=0,...,n E [R(θ k ) -R(θ * )] 2 C n α+1 + 2R 0 γR(θ * ) ,
where C is the same constant as in Theorem 1.

The take-home message is that if we consider the excess risk R(θ k ) -R(θ * ), we get the upper bound of the form 2C n -(α+1) , analog to Theorem 1, but with an additional constant term 2R 0 γR(θ * ). This term can be small if R(θ * ) is small, that is if the problem is close to the noiseless linear model, or if the step-size γ is small. In the finite horizon setting setting, one can optimize γ as a function of the scheduled number of steps n in order to balance both terms in the upper bound. As C ∝ γ -(α+1) , the optimal choice is γ ∝ n -(α+1)/(α+2) which gives a rate min k=0,...

,n E [R(θ k ) -R(θ * )] = O n -(α+1)/(α+2) .
In the theorem below, we study the SGD iterates θ n in terms of the power norms

ϕ n (β), β ∈ [-1, α -1], in particular in term of the reconstruction error ϕ n (0) = E[ θ n -θ * 2 ] if α 1. Note that the population risk R(θ) is a quadratic with Hessian Σ, minimized at θ * , thus E [R(θ n ) -R(θ * )] = 1 2 E [ θ n -θ * , Σ(θ n -θ * ) ] = 1 2 ϕ n (-1) .
Thus the theorem below extends Theorem 5. Theorem 6. Under the assumptions of Theorem 1, 1. for all β 0, β α -1,

ϕ n (β) 2 C(β) n α-β + 4R 1-(β+1)/α 0 R (β+1)/α α γR(θ * ) , 2. for all β ∈ [-1, 0), β α -1, min k01,...,n ϕ k (β) 2 C (β) n α-β + 4R 1-(β+1)/α 0 R (β+1)/α α γR(θ * ) ,
where C, C are the same constants as in Theorem 3.

This theorem is proved in Appendix E. We expect the condition β α -1 to be necessary. More precisely, when R(θ * ) is positive, we expect the error θ n -θ * to diverge under the norm

Σ -β/2 . if β > α -1.
In particular, this would imply that the reconstruction error diverges when α < 1.

In Figure 4, we show how the simulations of Section 3.3 are perturbed in the presence of additive noise. We consider the noisy linear model Y = θ * , X + σ 2 Z, where X ∼ N (0, Σ) and Z ∼ N (0, 1) are independent. As in the previous simulations, we consider the case Σ = d i=1 i -β e i ⊗ e i and θ * = d i=1 i -δ e i with here d = 10 5 , β = 1.4, δ = 1.2. In the noiseless case σ 2 = 0, we have shown that the rate of convergence was given by the polynomial exponent α * = min 1 -1 β , 2δ-1 β . These predicted rates are represented by the orange lines in the plots. In blue, we show the results of our simulations with some additive noise with variance σ 2 = 2 × 10 -4 . The exponent α * still describes the behavior of SGD in the initial phase, but in the large n asymptotic the population risk R(θ n ) stagnates around the order of σ 2 . Both of these qualitative behaviors are predicted by Theorem 5. Moreover, the reconstruction error θ n -θ * diverges for large n.

Conclusion and research directions

In this paper, we give a sharp description of the convergence of SGD under the noiseless linear model and made connexions with the interpolation of a real function and the averaging process. The behavior of SGD is surprisingly different in the absence of additive noise: it converges without any averaging or decay of the step-sizes. To some extent, SGD adapts to the regularity of the problem thanks to the implicit regularization ensured by the initialization at zero and the single pass on the data. However, by comparing with some known estimators for the interpolation of functions [START_REF] Bauer | Nonparametric estimation of a function from noiseless observations at random points[END_REF][START_REF] Kohler | Optimal global rates of convergence for interpolation problems with random design[END_REF] (see the end of Section 1), we conjecture that the convergence rate of SGD is suboptimal. What are the minimax rates under the noiseless linear model? Can they be reached with some accelerated online algorithm?

A Proof of Theorems 1 and 3

We recall here the definition of the regularity functions

ϕ n (β) = E θ n -θ * , Σ -β (θ n -θ * ) ∈ [0, ∞] , β ∈ R .

A.1 Properties of the regularity functions

We derive here two properties of the sequence of regularity functions ϕ n , n 1 that are useful for the proof of Theorem 3. The first one is a simple consequence of the above definition of the regularity function. The second property is the closed recurrence relation of the regularity functions ϕ n , n 0 associated to the iterates of SGD. Property 1. For all n, the function ϕ n is log-convex, i.e., for all β 1 , β 2 ∈ R, for all λ ∈ [0, 1],

ϕ n ((1 -λ)β 1 + λβ 2 ) ϕ n (β 1 ) 1-λ ϕ n (β 2 ) λ .
Proof. The proof is based on the following lemma, that we state clearly for another use below.

Lemma 2. Let θ ∈ H. Then for all β 1 , β 2 ∈ R, λ ∈ [0, 1], θ, Σ -[(1-λ)β1+λβ2] θ θ, Σ -β1 θ 1-λ θ, Σ -β2 θ λ .
This lemma follows from Hölder's inequality with p = (1 -λ) -1 and q = λ -1 . Indeed, diagonalize

Σ = i µ i e i ⊗ e i . Then θ, Σ -[(1-λ)β1+λβ2] θ = i µ -[(1-λ)β1+λβ2] i θ, e i 2 = i µ -β1 i θ, e i 2 1-λ µ -β2 i θ, e i 2 λ i µ -β1 i θ, e i 2 1-λ i µ -β2 i θ, e i 2 λ = θ, Σ -β1 θ 1-λ θ, Σ -β2 θ λ .
We now apply this lemma to prove Property 1.

ϕ n ((1 -λ)β 1 + λβ 2 ) = E θ n -θ * , Σ -[(1-λ)β1+λβ2] (θ n -θ * ) E θ n -θ * , Σ -β1 (θ n -θ * ) 1-λ θ n -θ * , Σ -β2 (θ n -θ * ) λ .
Using again Hölder's inequality, we get

ϕ n ((1 -λ)β 1 + λβ 2 ) E θ n -θ * , Σ -β1 (θ n -θ * ) 1-λ E θ n -θ * , Σ -β2 (θ n -θ * ) λ = ϕ n (β 1 ) 1-λ ϕ n (β 2 ) λ .
Property 2. Under the assumptions of Theorem 3, for all n, the function ϕ n is finite on (-∞, α], and if 0 β α,

ϕ n (β) ϕ n-1 (β) -2γϕ n-1 (β -1) + γ 2 R 1-β/α 0 R β/α α ϕ n-1 (-1) .
Proof. By assumption (a), ϕ 0 (α) = Σ -α/2 θ * 2 is finite, i.e., there exists θ ∈ H such that θ * = Σ α/2 θ. Then for any β α, θ * = Σ β/2 Σ (α-β)/2 θ thus ϕ 0 (β) = Σ -β/2 θ * 2 is finite.

Further, assume that for some n, the function ϕ n-1 is finite on (∞, α]. Then we can rewrite the stochastic gradient iteration (1) as

θ n -θ * = (Id -γX n ⊗ X n )(θ n-1 -θ * ) .
Substituting this expression in the definition of ϕ n and expanding the formula, we get

ϕ n (β) = E θ n -θ * , Σ -β (θ n -θ * ) = E (Id -γX n ⊗ X n )(θ n-1 -θ * ), Σ -β (Id -γX n ⊗ X n )(θ n-1 -θ * ) = E θ n-1 -θ * , Σ -β (θ n-1 -θ * ) (9)
-2γE θ n-1 -θ * , Σ -β X n ⊗ X n (θ n-1 -θ * ) (10)
+ γ 2 E θ n-1 -θ * , X n ⊗ X n Σ -β X n ⊗ X n (θ n-1 -θ * ) . (11)
Note that the first term of this sum is ϕ n-1 (β). Further, θ n-1 is computed using only (X 1 , Y 1 ), . . . , (X n-1 , Y n-1 ), thus it is independent of X n . It follows that

E θ n-1 -θ * , Σ -β X n ⊗ X n (θ n-1 -θ * ) = E θ n-1 -θ * , Σ -β E [X n ⊗ X n ] (θ n-1 -θ * ) = E θ n-1 -θ * , Σ -β+1 (θ n-1 -θ * ) = ϕ n-1 (β -1) . (12)
Finally,

E θ n-1 -θ * , X n ⊗ X n Σ -β X n ⊗ X n (θ n-1 -θ * ) (13)
= E θ n-1 -θ * , X n 2 X n , Σ -β X n (14)
We now assume that 0 β α. We apply Lemma 2 with

β 1 = 0, β 2 = α, λ = β/α: X n , Σ -β X n X n 2(1-β/α) X n , Σ -α X n β/α
Let E Xn denote the expectation with respect to X n only, while keeping X 0 , . . . , X n-1 random. Applying Hölder's inequality, we get

E Xn X n , Σ -β X n θ n-1 -θ * , X n 2 E Xn X n 2(1-β/α) X n , Σ -α X n β/α θ n-1 -θ * , X n 2 E Xn X n 2 θ n-1 -θ * , X n 2 1-β/α E X n , Σ -α X n θ n-1 -θ * , X n 2 β/α = θ n-1 -θ * , E X n 2 X n ⊗ X n (θ n-1 -θ * ) 1-β/α × θ n-1 -θ * , E X n , Σ -α X n X n ⊗ X n (θ n-1 -θ * ) β/α R 1-β/α 0 R β/α α θ n-1 -θ * , Σ(θ n-1 -θ * ) ,
where in this last step, we use the assumptions that the features X are bounded and regular, in their weak formulation of Remark 3. Returning to the computation of ( 13)-( 14), we get

E θ n-1 -θ * , X n ⊗ X n Σ -β X n ⊗ X n (θ n-1 -θ * ) = E E Xn θ n-1 -θ * , X n 2 X n , Σ -β X n (15) R 1-β/α 0 R β/α α E [ θ n-1 -θ * , Σ(θ n-1 -θ * ) ] = R 1-β/α 0 R β/α α ϕ n-1 (-1) . ( 16
)
The result is obtained by putting together Equations ( 9)-( 11), ( 12) and [START_REF] Györfi | A distribution-free theory of nonparametric regression[END_REF].

A.2 Proof of Theorem 1

A remarkable feature of the proof that follows is that only Properties 1 and 2 of the regularity functions are used to derive the theorem. In particular, we do not use the definition of the regularity functions ϕ n in this section.

We start with a few preliminary remarks. Using the recurrence Property 2 and that γR 0 1,

ϕ k (0) ϕ k-1 (0) -γ (2 -γR 0 ) ϕ k-1 (-1) ϕ k-1 (0) -γϕ k-1 (-1) .
Thus the sequence ϕ k (0), k 0 decreases, and γϕ k-1 (-1) ϕ k-1 (0) -ϕ k (0) . (17) By summing this inequality over k 1, we get

γ ∞ k=0 ϕ k (-1) ϕ 0 (0) . (18)
Using again the recurrence Property 2,

ϕ k (α) ϕ k-1 (α) -2γϕ k-1 (α -1) + γ 2 R α ϕ k-1 (-1) (19)
ϕ k-1 (α) + γ 2 R α ϕ k-1 (-1)
.

By summing for k = 1, . . . , n and using the bound [START_REF] Jun | Kernel truncated randomized ridge regression: Optimal rates and low noise acceleration[END_REF],

ϕ n (α) ϕ 0 (α) + γ 2 R α n-1 k=0 ϕ k (-1)
ϕ 0 (α) + γR α ϕ 0 (0)

ϕ 0 (α) + R α R 0 ϕ 0 (0) . (20)
In words, the sequence ϕ n (α), n 0 is bounded by D := ϕ 0 (α) + Rα R0 ϕ 0 (0). As a side note, this proves Theorem 3 for β = α.

We can now give a closed recurrence relation ϕ k (0), k 0. Using the log-convexity Property 1,

ϕ k-1 (0) ϕ k-1 (-1) α/(α+1) ϕ k-1 (α) 1/(α+1) ϕ k-1 (-1) α/(α+1) D 1/(α+1) .
Substituting in [START_REF] Hofmann | Kernel methods in machine learning[END_REF], we obtain

ϕ k-1 (0) -ϕ k (0) γϕ k-1 (-1) γD -1/α ϕ k-1 (0) 1+1/α .
This gives the wanted closed recurrence relation for ϕ k (0), k 0. It implies a decay of ϕ k (0) as follows: consider the real function f (ϕ) = 1 ϕ 1/α . It is a convex function on the positive reals, with derivative f (ϕ) = -1 α 1 ϕ 1+1/α . Using that a convex function is above its tangents, we obtain

f (ϕ k (0)) -f (ϕ k-1 (0)) f (ϕ k-1 (0)) (ϕ k (0) -ϕ k-1 (0)) = - 1 α 1 ϕ k-1 (0) 1+1/α (ϕ k (0) -ϕ k-1 (0)) 1 α γD -1/α .
By summing this inequality for k = 1, . . . , n, we obtain

1 ϕ n (0) 1/α = f (ϕ n (0)) f (ϕ 0 (0)) + 1 α γD -1/α n 1 α γD -1/α n .
This implies conclusion 1 of Theorem 1:

E θ n -θ * 2 = ϕ n (0) α α γ α D 1 n α . (21)
Further,

min 0 k n ϕ k (-1) min n/2 k n ϕ k (-1) 2 n n k= n/2 ϕ k (-1) 2 n 1 γ n k= n/2 (ϕ k (0) -ϕ k+1 (0)) ,
where in the last step we used [START_REF] Hofmann | Kernel methods in machine learning[END_REF]. Telescoping the sum, we obtain

min 0 k n ϕ k (-1) min n/2 k n ϕ k (-1) 2 n 1 γ ϕ n/2 (0) (22)
2 n

1 γ α α γ α D 1 n/2 α 2 α+1 α α γ α+1 D 1 n α+1 .
Using that ϕ n (-1) = 2E[R(θ n )], this gives conclusion 2 of Theorem 1.

A.3 Proof of Theorem 3

We continue the proof of Theorem 1 to prove Theorem 3. By the log-convexity Property 1, for all β ∈ [0, α],

ϕ n (β) ϕ n (0) 1-β/α ϕ n (α) β/α . Using Equations ( 21) and [START_REF] Lin | Optimal convergence for distributed learning with stochastic gradient methods and spectral-regularization algorithms[END_REF], we obtain

ϕ n (β) α α-β γ α-β D 1 n α-β .
This proves conclusion 1 of the theorem. We now consider the case β ∈ [-1, 0). By the log-convexity Property 1,

min 0 k n ϕ k (β) min n/2 k n ϕ k (β) min n/2 k n ϕ k (-1) -β ϕ k (0) 1+β
Using that ϕ k (0), k 0 is decreasing and the inequality [START_REF] Mathieu | Isoperimetry and heat kernel decay on percolation clusters[END_REF], we obtain

min n/2 k n ϕ k (-1) -β ϕ k (0) 1+β ϕ n/2 (0) 1+β min n/2 k n ϕ k (-1) -β ϕ n/2 (0) 1+β 2 n 1 γ ϕ n/2 (0) -β 2 -β n -β 1 γ -β ϕ n/2 (0) .
Using finally [START_REF] Ma | The power of interpolation: Understanding the effectiveness of SGD in modern over-parametrized learning[END_REF], we obtain conclusion 2 of the theorem

min 0 k n ϕ k (β) 2 -β n -β 1 γ -β α α γ α D 1 n/2 α 2 α-β α α γ α-β D 1 n α-β .

B Proof of Theorems 2 and 4

We start in the case (a) where the optimum is irregular: θ * / ∈ Σ -α/2 (H). In that case, we give a lower bound in the convergence rate by studying the expected process θ n := E[θ n ]. Indeed, by Jensen's inequality,

ϕ n (β) = E θ n -θ * , Σ -β (θ n -θ * ) θ n -θ * , Σ -β θ n -θ * . (23)
The expectation θ n can be interpreted as the (non-stochastic) gradient descent on the population risk R(θ). Indeed, by taking the expectation in (1), we obtain

θ n -θ * = (Id -γΣ)(θ n-1 -θ * ) = -(Id -γΣ) n θ * . (24)
Note that as γ 1/R 0 , I -γΣ is a positive definite matrix. Indeed, by the weak definition of R 0 in Remark 3,

R 0 Σ E X 2 X ⊗ X = E [(X ⊗ X)(X ⊗ X)] E[X ⊗ X] 2 = Σ 2 , thus R 0 is larger than the operator norm of Σ. Thus γΣ 1 R0 Σ Id. In the following, if α ∈ R and k ∈ N, α k denotes the generalized binomial coefficient: α k = α(α-1)•••(α-k+1) k!
. Fix now α 0. We have the (formal) power series

(1 + x) -α = ∞ k=0 -α k x k (1 -x) -α = ∞ k=0 -α k (-1) k x k = ∞ k=0 α + k -1 k x k y -α = ∞ k=0 α + k -1 k (1 -y) k .
This last equality holds in [0, ∞] for y ∈ [0, 1]. In that case, all terms of the serie are positive, thus the meaning of the sum is unambiguous.

Note that 0 γΣ Id, thus we have, formally,

γ -α Σ -α = ∞ k=0 α + k -1 k (Id -γΣ) k .
The rigorous meaning of this equality is that for all θ ∈ H,

γ -α θ, Σ -α θ = ∞ k=0 α + k -1 k θ, (Id -γΣ) k θ .
Both terms of the equality can be infinite: here we are using the convention stated in Section 2.1 that implies that θ, Σ -α θ = ∞ ⇔ θ / ∈ Σ α/2 (H). In particular, take α = α -β and θ = Σ -β/2 θ * :

∞ = γ β-α θ * , Σ -α θ * = ∞ k=0 α -β + k -1 k θ * , Σ -β (Id -γΣ) k θ * = ∞ n=0 α -β + 2n -1 2n θ * , Σ -β (Id -γΣ) 2n θ * + α -β + 2n 2n + 1 θ * , Σ -β (Id -γΣ) 2n+1 θ * . Using that α-β+2n-1 2n α-β+2n 2n+1 and θ * , Σ -β (Id -γΣ) 2n θ * θ * , Σ -β (Id -γΣ) 2n+1 θ * and then (24), (23), ∞ 2 ∞ n=0 α -β + 2n 2n + 1 θ * , Σ -β (Id -γΣ) 2n θ * = 2 ∞ n=0 α -β + 2n 2n + 1 θ n -θ * , Σ -β (θ n -θ * ) 2 ∞ n=0 α -β + 2n 2n + 1 ϕ n (β) .
From [14, Equation 5.8.1], we have the formula

Γ(z) = lim k→∞ k!k z z(z+1)•••(z+k) where Γ denotes the Gamma function. Thus as n → ∞ α -β + 2n 2n + 1 = (α -β)(α -β + 1) • • • (α -β + 2n) (2n + 1)(2n)! ∼ (2n) α-β (2n + 1)Γ(α -β) .
As a consequence, the serie n n α-β-1 ϕ n (β) diverges. The criteria for the convergence of Riemann series implies that ϕ n (β) can not be asymptotically dominated by 1/n α-β+ε for ε > 0.

We now turn to the case (b) where the features are irregular: with positive probability p > 0, X / ∈ Σ α/2 (H) and X, θ * = 0. With probability p, the second iterate θ

1 = -γ X 1 , θ * X 1 is irregular, i.e., θ 1 / ∈ Σ α/2 (H).
By a simple shift of the iterates, we show that the effect of the irregularity of the initial condition for this iteration started from θ 1 has an effect equivalent to the irregularity of the optimum, thus we can apply the result above to lower bound the convergence rate. More precisely, consider the iterates θn = θ n+1 -θ 1 and θ * = θ * -θ 1 . The iteration (1) can be rewritten as θn = θn-1 -γ θn-1 -θ * , X n X n and θ0 = 0, thus the new sequence θn satisfies our framework. We can assume that (a) is satisfied, i.e., θ * ∈ Σ α/2 (H). In that case, with probability p, θ * = θ * -θ 1 / ∈ Σ α/2 (H). Thus by the case above,

ϕ n (β) = E θ n -θ * , Σ -β (θ n -θ * ) = E θn-1 -θ * , Σ -β θn-1 -θ *
is not asymptotically dominated by 1/n α-β+ε , for ε > 0.

We bound the two quantities as above. We obtain

R α = sup v,w∈E Σ -α/2 (e v -e w ) 2 2M α V -1 δ d/2-α max d d -2α
.

Theorem 1 gives

E x n -x * 2 = E θ n -θ * 2 α α γ α Σ -α/2 θ * 2 + R α R 0 θ * 2 1 n α (d/2) α (1/2) α M α V -1 δ d/2-α max d d -2α + M α V -1 δ d/2-α max d d -2α θ * 2 1 n α Note that θ * 2 2
1 and recall the scaling t = n/M :

E x n -x * 2 d d/2+1 V -1 δ d/2-
(x k (v) -x k (w)) 2   = min 0 k n E 1 2 x k -x * , L(x k -x * ) = M min 0 k n E 1 2 θ k -θ * , Σ(θ k -θ * ) 2 α α α γ α+1 Σ -α/2 θ * 2 + R α R 0 θ * 2 1 n α 2 α+1 d α V -1 δ d/
(x k (v) -x k (w)) 2   2 d/2+1 d d/2 V -1 δ max d log t log 2 2 t d/2+1
This gives conclusion 2 of the corollary.

D Proof of Proposition 1

The graph T d Λ is invariant by translation, thus the spectral measure σ v is the same for all vertices v ∈ V. Thus We need to bound the number of eigenvalues of the Laplacian of T d Λ below some fixed value E. The eigenvalues of the Laplacian of the circle T For y ∈ [-π, π], 1 -cos(y) 2 π 2 y 2 . Thus

1 -cos 2πi 1 Λ + • • • + 1 -cos 2πi d Λ E ⇒ 2 π 2 2πi 1 Λ 2 + • • • + 2πi d Λ 2 E ⇔ i 2 1 + • • • + i 2 d EΛ 2 8 .
We need to count the number of integer points in the Euclidean ball centered at 0 and of radius E/8Λ in R d . This problem is famously known as Gauss circle problem. For our purposes, a crude estimate suffices: there exists a constant C(d), depending only on the dimension d, such that for all radius R, the number of integer points in the ball of radius R is smaller than 1 + C(d)R d . This leads to the final estimate

σ v ((0, E]) = 1 Λ d (i 1 , . . . , i d ) ∈ Z ∩ - Λ 2 , Λ 2 d \ {0} such that 1 -cos 2πi 1 Λ + • • • + 1 -cos 2πi d Λ E 1 Λ d (i 1 , . . . , i d ) ∈ Z d \ {0} i 2 1 + • • • + i 2 d EΛ 2 8 1 Λ d C(d) EΛ 2 8 d/2 = C(d) 8 d/2 E d/2 .
This proves the proposition with V (d) = 8 d/2 /C(d).

E Proof of Theorems 5 and 6

Note that in this proof, we use the strong assumptions of regularity of the feature vector X. We do not know whether it is possible to prove the same result under the weak assumptions of Remark 3.

Our proof stategy is the following: we decompose the SGD iterates sequence θ n as a sum of sequences

θ n = ν n + n l=1 η (l)
n , where each of the auxiliary sequences is interpreted as the iterates of some SGD iteration under a noiseless linear model. We thus apply the results of Section 2 to control these auxiliary sequences and obtain the presented bound.

Define ε n = Y n -θ * , X n , the error of the best linear estimator. Then Equation ( 8) can be rewritten as

θ 0 = 0 , θ n = θ n-1 -γ θ n-1 -θ * , X n X n + γε n X n .
We see this iteration as an additively perturbed version of the iteration

ν 0 = 0 , ν n = ν n-1 -γ ν n-1 -θ * , X n X n ,
studied in Section 2. To understand the effect of the additive noise, define for all l 1,

η (l) l = γε l X l , η (l) n = η (l) n-1 -γ η (l)
n-1 , X n X n , n > l .

Then

θ n = ν n + n l=1 η (l) n . (25)

6

 6

2 Figure 1 : 2 L 2

 2122 Figure 1: Interpolation of a function of smoothness r = 2 using SGD with kernels of smoothness s = 1 (left), s = 2 (middle) and s = 3 (right). Each plot represents one realization of the algorithm (4). The blue crosses represent the square L 2 norms f n -f * 2 L 2 as a function of the number of iterations n and the orange lines represent the predicted polynomials rates C/n α * +1 , where C is chosen to match best the empirical observations for each plot.

Proposition 1 .

 1 Let T d Λ denote the d-dimensional torus of side length Λ, i.e., the graph with vertex set V = (Z/ΛZ) d and edge set E = {{v, w} | v, w ∈ E, v -w 2 = 1}. The torus T d Λ is of spectral dimension d with some constant V (d) that depends on the dimension d but not on the side length Λ.

Figure 2 :

 2 Figure 2: Convergence rates on the circle T 1 300 (up) and on the two dimensional torus T 2 40 (bottom). The convergence is measured in terms of squared 2 -distance to 1 N 1 (left) and sum of the squared differences along the edges (right). In orange are the curves of the form C/n d/2 and C /n d/2+1where C and C are constants chosen to match best the empirical observations for each plot.

Figure 3 : 1 β≈ 1 β≈

 311 Figure 3: In blue +, evolution of θ n -θ * 2 (left) and R(θ n ) (right) as functions of n, for the problems with parameters β = 1.4, δ = 1.2 (up) and β = 3.5, δ = 1.5. The orange lines represent the curves D/n α * (left) and D /n α * +1 (right).

Figure 4 :

 4 Figure 4: In blue +, evolution of θ n -θ * 2 (left) and R(θ n ) (right) as functions of n, for the problems with parameters d = 10 5 , β = 1.4, δ = 1.2. The orange lines represent the curves D/n α * (left) and D /n α * +1 (right).

  Thusσ v ((0, E]) = 1 Λ d |{0 < i N -1|λ i E}| .

  Assume further 0 < γ 1/R 0 . The iterates θ n of SGD with step-size γ satisfy for all n 1,

	1. (reconstruction error)	E θ n -θ *	2	C n α ,
	2. (generalization error)	min k=0,...,n

  This bound is valid for allα < d 2 . Choose α = d 2 -log 2 log t . E x n -x * 2 d d/2+1 V -1 δ log 2/ log tAs we assume t 2, δ log 2/ log t max δ max . Thus we obtain conclusion 1.

				max	α	1 d/2 -α	1 t α .
					log t	2
				max	log 2	t d/2
	The proof of 2 is similar. Theorem 1 gives
			
	min 0 k n	E	 1 2	{v,w}∈E

  Example 1.5]. As T d Λ is the Cartesian product T 1 Λ × • • • × T 1 Λ (with d terms), the eigenvalues of the Laplacian of the torus T d Λ are the

	1 -cos	2πi 1 Λ	+ • • • + 1 -cos	2πi d Λ	,	i 1 , . . . i d ∈ Z, -	Λ 2	< i 1 , . . . , i d	Λ 2	.

1 Λ are 1 -cos 2πi Λ , i ∈ Z, -Λ/2 < i Λ/2 [11,

34th Conference on Neural Information Processing Systems (NeurIPS 2020), Vancouver, Canada.

Acknowledgments

This work was greatly improved by detailed comments from Loucas Pillaud-Vivien on earlier versions of the manuscript. We also thank Alessandro Rudi, Nicolas Flammarion and anonymous reviewers for useful discussions. This work was funded in part by the French government under management of Agence Nationale de la Recherche as part of the "Investissements d'avenir" program, reference ANR-19-P3IA-0001 (PRAIRIE 3IA Institute). We also acknowledge support from the European Research Council (grant SEQUOIA 724063) and from the DGA.

C Proof of Corollary 1

We apply Theorem 1 in the following way. Denote θ n = x n -x 0 , θ * = x * -x 0 , where x * = 1 N 1 is the function identically equal to 1 N . These vectors belong to the Hilbert space H = 2 (V). Denote ., . and . the 2 (V) scalar product and norm. Denote also X n = e vn -e wn ∈ H and γ = 1/2. Note that Σ = E[X n X n ] = 1 M L. The graph is connected thus λ 0 = 0 is the unique zero eigenvalue of L [START_REF] Chung | Spectral Graph Theory[END_REF]Lemma 1.7]. The corresponding eigenspace is the space of constant functions. The vectors θ n , X n , θ * are orthogonal to the null space of Σ, thus the quantities of the form θ n , Σ -α θ n , X n , Σ -α X n , θ * , Σ -α θ * are finite.

We have θ 0 = 0 and the averaging update step [START_REF] Bottou | The tradeoffs of large scale learning[END_REF] can be written as

The last form makes explicit the parallel with Equation (1). To apply Theorem 1, we check that its assumptions are satisfied. First, X n 2 = 2 a.s. thus can take R 0 = 2 and then γ = 1/R 0 . Second, we seek α > 0 such that Σ -α/2 θ * < ∞ and R α = sup {v,w}∈E e v -e w , Σ -α (e v -e w ) < ∞.

In the following, we bound these constants for all α < d/2, thus giving decay rates for the expected squared distance to optimum of the form n -α for all α < d/2. However, our bounds of the constants Σ -α/2 θ * and R α diverge as α → d/2. Nevertheless, by estimating how fast the bounds diverge as α → d/2, we obtain a decay rate of n -d/2 by paying an additional logarithmic factor. Fix 0 < α < d/2. We check assumptions (a) and (b).

(a)

First, as x * is a constant vector, x * , u i is zero for all i 1. Second, x 0 = e v . Thus

max , it is better to use a more naive bound. As all eigenvalues of L are smaller or equal than

. is a norm, by the triangle inequality,

Indeed, this last equation is checked by induction: θ 0 = 0 = ν 0 , and if the equation is satisfied for some n 0,

We use the decomposition [START_REF] Pillaud-Vivien | Statistical optimality of stochastic gradient descent on hard learning problems through multiple passes[END_REF] to study ϕ n (β). Using the triangle inequality,

The first term is studied in Section 2. We detail the analysis of the second term. Note that

are zero. This gives

Note that from Equation ( 27), η

n and η

n-l+1 are equal in law. Thus

This last quantity is the sum of the expected squared power norms

l , l 1 on a noiseless linear model, with initialization η

(1) 1 = γε 1 X 1 . When β = -1, this control is given by ( 18): with our notation here, this gives

When β = α -1, a similar control can be obtained from [START_REF] Kohler | Optimal global rates of convergence for interpolation problems with random design[END_REF] which gives:

.

By summing these inequalities for l = 2, 3, . . . , we obtain,

Note that using the strong assumption of regularity of the feature vectors,

We use these expressions to simply further ( 29) and [START_REF] Tsybakov | Introduction to Nonparametric Estimation[END_REF]:

Putting back together Equations ( 26), ( 28) and [START_REF] Vaswani | Fast and faster convergence of sgd for over-parameterized models and an accelerated perceptron[END_REF], we obtain

The theorem follows the application of Theorem 3 to the sequence ν n in order to control the first term.