Vivien Cabannes

F Cabannes

A Rudi Bach

Fast Rates for Structured Prediction

Keywords: Structured prediction, fast convergence rates, generalization bounds, low-density separation, margin condition, local averaging method, nearest neighbors, kernel methods, kernel ridge regression

Discrete supervised learning problems such as classification are often tackled by introducing a continuous surrogate problem akin to regression. Bounding the original error, between estimate and solution, by the surrogate error endows discrete problems with convergence rates already shown for continuous instances. Yet, current approaches do not leverage the fact that discrete problems are essentially predicting a discrete output when continuous problems are predicting a continuous value. In this paper, we tackle this issue for general structured prediction problems, opening the way to "super fast" rates, that is, convergence rates for the excess risk faster than n -1 , where n is the number of observations, with even exponential rates with the strongest assumptions. We first illustrate it for predictors based on nearest neighbors, generalizing rates known for binary classification to any discrete problem within the framework of structured prediction. We then consider kernel ridge regression where we improve known rates in n -1/4 to arbitrarily fast rates, depending on a parameter characterizing the hardness of the problem, thus allowing, under smoothness assumptions, to bypass the curse of dimensionality.

Introduction

Machine learning is raising high hopes to tackle a wide variety of prediction problems, such as language translation, fraud detection, traffic routing, speech recognition, self-driving cars, DNAbinding proteins, etc.. Its framework is appreciated as it removes humans from the burden to come up with a set of precise rules to accomplish a complex task, such as recognizing a cat on an array of pixels. Yet, it comes at a price, which is of forgetting about algorithm correctness, meaning that machine learning algorithms can make mistakes, i.e., wrong predictions, which can have dramatic implications, e.g., in medical applications. This motivates work on generalization error bounds, quantifying how often one should expect errors.

Many of the problems discussed above are of discrete nature, in the sense that the number of potential outputs is finite, or infinite countable. To learn such problems, a classical technique consists in defining a continuous surrogate problem, which is easier to solve, and such that:

(1) an algorithm on the surrogate problem translates into an algorithm on the original problem;

(2) errors on the original problem are bounded by errors on the surrogate problem. The first point refers to the concept of plug-in algorithms, while the second point to the notion of calibration inequalities. For example, binary classification can be approached through regression by estimating the conditional expectation of the output Y given an input X (Bartlett et al., 2006).

On the one hand, continuous surrogates for discrete problems are interesting, as they benefit from functional analysis knowledge, when discrete problems are more combinatorial in nature. On the F R S P [START_REF] Caponnetto | Optimal rates for the regularized least-squares algorithm[END_REF], allowing to control convergence through concentration inequalities in Hilbert spaces [START_REF] Vladimirovich | On an infinite-dimensional version of S. N. Bernstein's inequalities[END_REF][START_REF] Pinelis | Remarks on inequalities for large deviation probabilities[END_REF] and on self-adjoint operating on Hilbert spaces [START_REF] Minsker | On some extensions of Bernstein's inequality for self-adjoint operators[END_REF]. First derived in L 2 -norm, rates were cast in L ∞ -norm through interpolation inequalities (e.g., [START_REF] Fischer | Sobolev norm learning rates for regularized least-squares algorithms[END_REF][START_REF] Lin | Optimal rates for spectral algorithms with least-squares regression over Hilbert spaces[END_REF].

Tsybakov margin condition. Learning a mapping into a discrete output space is indeed easier than learning a continuous mapping, as, for binary classification for example, one typically only has to predict the sign of E[Y |X] rather than its precise value. As such, calibration inequalities that relate the error on a discrete structured prediction problem to an error on a smooth surrogate problem are often suboptimal. This phenomenon was exploited for density discrimination, a problem consisting of testing if samples were drawn from one or the other of two potential distributions, by [START_REF] Mammen | Smooth discrimination analysis[END_REF], and for binary classification by [START_REF] Audibert | Fast learning rates for plug-in classifiers[END_REF].

Those works introduce a parameter α ∈ [0, ∞) characterizing the hardness of the discrete problem, and leverage concentration inequalities to accelerate rates known for regression by a power α + 1 [START_REF] Audibert | Fast learning rates for plug-in classifiers[END_REF], while rates plugged-in directly through calibration inequalities only present an acceleration by a power 2(α + 1) /(α + 2) (see, e.g., [START_REF] Boucheron | Theory of classificatoin: A survey of some recent advances[END_REF]Bartlett et al., 2006;[START_REF] Bartlett | Empirical minimization[END_REF][START_REF] Van Erven | Fast rates in statistical and online learning[END_REF][START_REF] Nowak-Vila | Sharp analysis of learning with discrete losses[END_REF].

Structured Prediction with Surrogate Control

In this section, we introduce the classical supervised learning problem, and a surrogate problem that consists of conditional mean estimation. We recall a calibration inequality relating the original problem to the surrogate one. We mention how empirical estimations of the conditional means usually deviate from the real means following a sub-exponential tail bound, similarly to bounds obtained through Bernstein inequality. We end this section by providing refined surrogate control, that is the key towards "super fast" rates, that is, rates faster than 1/n.

Surrogate mean estimation

Consider a classic supervised learning problem, where given an input space X , an observation space Y, a prediction space Z, a joint distribution ρ ∈ ∆ X ×Y and a loss function ℓ : Z × Y → R + , one would like to retrieve f * : X → Z minimizing the risk R.

f * ∈ arg min f :X →Z R(f ) with R(f ) = E (X,Y )∼ρ [ℓ(f (X), Y )] .
In practice, X , Y, Z and ℓ are givens of the problem, while ρ is unknown, yet partially observed thanks to a dataset D n = (X i , Y i ) i≤n ∼ ρ ⊗n , with data (X i , Y i ) sampled independently from ρ. Note that in fully supervised learning, the observation space is the same as the prediction space Y = Z, yet we distinguish the two for our results to stand in more generic settings, such as instances of weak supervision [START_REF] Cabannes | Structured prediction with partial labelling through the infimum loss[END_REF]. In the following, we consider Z finite. In several cases, solving the supervised learning problem can be done through solving a surrogate problem that is easier to handle. [START_REF] Ciliberto | A consistent regularization approach for structured prediction[END_REF] provide a setup that reduces a wide variety of structured prediction problems (ℓ, ρ) to a problem of mean estimation. It works under the following assumption.

Assumption 1 (Bilinear loss decomposition)

There exists an Hilbert space H and two mappings ψ : Z → H, ϕ : Y → H such that ℓ(z, y) = ψ(z), ϕ(y) .

C B R

We will also assume that ψ is bounded (in norm) by a constant c ψ .

This assumption is not really restrictive [START_REF] Ciliberto | A general framework for consistent structured prediction with implicit loss embeddings[END_REF]. Among others, it works for any losses on finite spaces, usually with spaces H whose dimensionality is only polylogarithmic with respect to the cardinality of Z [START_REF] Nowak-Vila | Sharp analysis of learning with discrete losses[END_REF]. Under Assumption 1, solving the supervised learning problem can be done through estimating the surrogate conditional mean g * : supp ρ X → H, defined as

g * (x) = E Y ∼ρ|x [ϕ(Y )] , (1)
where we denote ρ| x the conditional law of (Y | X) under (X, Y ) ∼ ρ.

Lemma 1 (Ciliberto et al. ( 2016)) Given an estimate g n of g * in Eq. (1), consider the estimate f n : X → Z of f * , which is obtained from "decoding" g n as f n (x) = arg min z∈Z ψ(z), g n (x) .

(2)

Then the excess risk is controlled through the surrogate error as

R(f n ) -R(f * ) ≤ 2c ψ g n -g * L 1 (X ,H,ρ) . (3)
Inequalities relating the original excess risk R(f n ) -R(f * ) with a measure of error on a surrogate problem are called calibration inequalities. They are useful when the measure of error between g n and g * is easier to control than the one between f n and f * .

Example 1 (Binary classification) Binary classification corresponds to Y = Z = {-1, 1} and ℓ(z, y) = 1 z =y (or equivalently ℓ(z, y) = 21 z =y -1). The classical surrogate consists of taking H = R, with ϕ = id and ψ = -id. In this setting, we have g * (x) = E ρ [Y |X = x], and the decoding f n (x) := sign g n (x), for any g n (x) ∈ H. In this case R(f n ) -R(f * ) = E X 1 fn(X) =f * (X) |g * (X)| ≤ 2 g ng * L 1 ≤ 2 g ng * L 2 . Note that in regression the excess risk reads as the square of the L 2 norm, explaining a loss of a power one half in convergence rates, when going from regression to classification (e.g. [START_REF] Chen | Explaining the Success of Nearest Neighbor Methods in Prediction[END_REF].

Differences between an empirical estimate and its population version are generally handled through concentration inequalities. In this work, we will leverage concentration on g n (x)g(x) that is uniform for x ∈ supp ρ X , motivating the introduction of Assumption 2.

Assumption 2 (Exponential concentration inequality) Suppose that for n ∈ N, there exists two reals L n and M n , such that the tails of g n (x)g(x) can be controlled for any t > 0 as

sup x∈supp ρ X P Dn ( g n (x) -g(x) > t) ≤ exp - L n t 2 1 + M n t . ( 4
)
Note that to satisfy Assumption 2, it is sufficient, yet not necessary, to have a uniform control on g ng * , i.e., a control on the tail of

g n -g * L ∞ , since sup x P (A x > t) ≤ P (∪ x {A x > t}) = P (sup x A x > t) , with (A x ) a family of random variables indexed by x ∈ X .
Usually, in bounds like Eq. ( 4), M n is a constant of the problem, while L n depends on the number of samples, therefore, we would like to give rates depending on L n . Typically in Bernstein inequalities (see Theorem 32 in Appendix), L n = nσ -2 with σ 2 a variance parameter and M n = cσ -2 with c a constant of the problem that does not depend on n.

Refined Calibration

While it is sufficient to control the excess risk through a L 1 -norm control on g from Eq.

(3), it is not always necessary. In other words, the calibration bound in Lemma 1 is not always tight. Indeed, we do not predict optimally, that is, {f n (x) = f * (x)} only if g n (x) and g * (x) do not lead to the same decoding f n (x) and f * (x). When Z is finite, this is characterized by g n (x) and g * (x) not falling in the same region R z of H, where

R z = ξ ∈ H z ∈ arg min z ′ ∈Z ψ(z ′ ), ξ .
To ensure that g n (x) and g * (x) fall in the same region, one can ensure that g n (x) is closer to g * (x) than g * (x) is of the frontier of those regions. Those frontiers are defined by points leading to at least two minimizers in Eq. ( 2):

F = ξ ∈ H arg min z∈Z ψ(z), ξ > 1 .
The introduction of F is motivated by the following geometric results.

Lemma 2 (Refined surrogate control) When Z is finite, for any x ∈ supp ρ X ,

g n (x) -g * (x) < d(g * (x), F ) ⇒ f n (x) = f * (x),
with d the extension of the norm distance to sets as d(g * (x), F ) = inf ξ∈F g * (x)ξ . This result allows to refine the calibration control from Lemma 1 as

R(f n ) -R(f * ) ≤ 2c ψ E X 1 gn(X)-g * (X) ≥d(g * (X),F ) g n (X) -g * (X) . ( 5
)
Example 2 (Binary classification) In binary classification (cf. Example 1), F = {0}, and, for any

x ∈ supp ρ X , d(g * (x), F ) = |g * (x)|. Lemma 2 is based on the fact that f * (x) = f n (x) implies that sign g * (x) = sign g n (x) which itself implies that |g * (x) -g n (x)| = |g * (x)| + |g n (x)| ≥ |g * (x)|.
To leverage Eq. ( 5), we need to control d(g * (x), F ) below and g n (x)g * (x) above. While upper bounds on g n (x)g * (x) are assumed to have been derived through concentration inequalities, lower bounds on d(g * (x), F ) will be assumed as a given parameter of the problem, see Eqs. ( 6) and (7).

Remark 3 (Scope of our work) While we derived the refined calibration inequality Eq. (5) for the surrogate conditional mean g * and the associated pointwise metric • H , similar inequality could be obtained for other type of surrogate methods. This suggests that our work could be extended to any smooth surrogate such as the ones considered by [START_REF] Nowak-Vila | A general theory for structured prediction with smooth convex surrogates[END_REF], as well as Fenchel-Young losses [START_REF] Blondel | Learning with Fenchel-Young losses[END_REF].

Geometric understanding

In this subsection, we detail how to understand geometrically Lemma 2. While the introduction of ϕ and ψ could seem arbitrary, it can be thought in a more intrinsic manner by considering the embedding ϕ(y) = δ y belonging to the Banach space H of signed measured, g * (x) = ρ| x , with the

C B R
bracket operator, for µ ∈ H and z ∈ Z, z, µ = Y ℓ(z, y)µ(dy), and the distance between signed measures being d(µ 1 , µ 2 ) = sup z∈Z z, µ 1µ 2 . Note that Lemma 2 is a pointwise result, holding for any x ∈ X , that is integrated over X afterwards. Therefore, it is enough to consider X = {x} and remove the dependency in X to understand it. The simplex ∆ Y naturally splits into decision region R z for z ∈ Z as illustrated on Figure 1. The main idea of Lemma 2 is that one does not have to precisely estimate g * (x) = ρ| x but only has to make sure that g n (x) falls in the same region on Figure 1.

a b c F R a R b R c a b c µ ⋆ µ n

Rate acceleration under margin condition

In this section, we introduce a condition that g * is not too often close to the decision frontier F . It generalizes the so-called "Tsybakov margin condition" known for classification. Under this condition, we proves rates that generalize the results of [START_REF] Audibert | Fast learning rates for plug-in classifiers[END_REF] from binary classification to generic structured prediction problems, which opens the way to "super fast" rates in structured prediction.

No density separation

To get fast convergence rates, one has to make assumptions on the problem. A classical assumption is that g * is smooth enough in order to get concentration bounds similar to Assumption 2 when considering a specific class of estimates g n . In our decoding setting (Lemma 1), learning is made easy when it is easy to estimate in which region R z the optimal g * will fall in. This is in particular the case, when there is a margin t 0 > 0, for which, for no point x ∈ supp ρ X , g * (x) falls at distance t 0 of the decision frontier F , motivating the following definition.

Assumption 3 (No-density separation)

A surrogate solution g * will be said to satisfy the nodensity separation, if there exists a t 0 > 0, such that

P X (d(g * (X), F ) < t 0 ) = 0. ( 6
)
This condition is alternatively called the hard margin condition, or sometimes "Massart's noise condition" for binary classification [START_REF] Massart | Risk bounds for statistical learning[END_REF]. and2). On the left example, when ρ X is such that there is no mass where the sign of g * changes, classes are separated in X , yet the no-density separation is not verified. On the right, classes are not separated in X , but the problem satisfies the no-density separation as there is no x such that d(g

F R S P x E[Y |X = x] -1 1 g * (x) f * (x) x E[Y |X = x] -1 1 f * (x) g * (x) t 0
* (x), F ) = |g * (x)| < t 0 .
Note that when ρ X is uniform, the left problem satisfies a milder separation condition, introduced thereafter and called the 1-low-density separation.

Remark 4 (Separation in Y and separation in X ) It is important to realize that Eq. ( 6) is a condition of separation in ∆ Y that should hold for all x ∈ X , but it does not state any separation between classes in X for f * : X → Z. To visualize it, consider the classification problem where

X = [-1, 1], Y = Z = {-1, 1} and ℓ(z, y) = 1 z =y . • A situation where ρ X is uniform on X and E[Y |X = x] = 2 • 1 x∈pN+{a | |a|<p/4} -1, for p = 1/50, satisfies separation in ∆ Y (Eq. (6)), but classes are not separated in X . • A situation where ρ is uniform on [-1, -.5] ∪ [.5, 1], with E[Y |X = x] = sign(x)(1 -|x|) p ,
for p > 0, satisfies a separation of classes in X but does not satisfy Eq. (6). Note that continuity of g * and the no-density separation in Eq. (6) imply separation of classes in X . Note also that to get concentration inequality such as Eq. (4), one usually supposes that g * is smooth. We refer the curious reader to Section 2.4 in [START_REF] Steinwart | Fast rates for support vector machines using Gaussian kernels[END_REF] for separation in X .

The introduction of Assumption 3 is motivated by the following result.

Theorem 5 (Rates under no-density separation) When ℓ is bounded by ℓ ∞ (i.e., ℓ(z, y) ≤ ℓ ∞ for any (z, y) ∈ Z × Y) and satisfies Assumption 1, and Z is finite, under the no-density separation Assumption 3, and the concentration Assumption 2, the excess risk is controlled

E Dn R(f n ) -R(f * ) ≤ ℓ ∞ exp - L n t 2 0 1 + M n t 0 .
Proof Because we make a mistake only when d(g * (x), F ) ≥ g n (x)g * (x) , we make no mistake when g n (x)g * (x) < t 0 ; otherwise we can consider the worse error we are going to pay, that is ℓ ∞ , leading to

R(f n ) -R(f * ) ≤ ℓ ∞ P X ( g n (x) -g * (x) > t 0 ).
Taking the expectation with respect to D n and using the fact that

E A P B (Z) = E A E B [1 Z ] = E B E A [1 Z ] = E B P A (Z)
, and plug-in the concentration inequality Eq. (4), we get the result.

Example 3 (Image classification)

In image classification, one can arguably assume that the class of an image is a deterministic function of this image. With the 0-1 loss, it implies that the image classification problem verifies the no-density separation. The same holds for any discrete problem where the label is a deterministic function of the input. Based on Theorem 5 and Eq. (4) in which M is generally a constant when L is proportional to the number of data, it is reasonable to ask for exponential convergences rates on such problems.

Low density separation

While we presented the no-density separation first for readability, it is a strong assumption. Recall our example, Remark 4, with E[Y |X = x] = sign(x)(1 -|x|) p , only around x = 1 and x = -1 is d(g * (x), F ) not bounded away from zero. While the neighborhood of those points should be studied carefully, the error on all other points x ∈ [-1 + t, 1t] can be controlled with exponential rates. The low-density separation, also known as the Tsybakov margin condition in binary classification, will allow a refined control to get fast rates in such a setting.

Assumption 4 (Low-density separation) A surrogate solution g * is said to satisfy the low-density separation, if there exists c α > 0, and α > 0, such that for any t > 0

P X (d(g * (X), F ) < t) ≤ c α t α . ( 7
)
This condition is alternatively called the margin condition.

The low-density separation spans all situations from the hard margin condition, that can be seen as α = +∞, to situations without any margin assumption corresponding to α = 0. The coefficient α is an intrinsic measure of the easiness of finding f * in the problem (ℓ, ρ). For example, the setting described in the last paragraph corresponds to the case α = 1/p. We discuss the equivalence of Assumption 4 to definitions appearing in the literature in Remark 7.

Theorem 6 (Optimal rates under low density separation) Under refined calibration in Eq. (5), concentration (Assumption 2), and low-density separation (Assumption 4), the risk is controlled as

E Dn R(f n ) -R(f * ) ≤ 2c ψ c α c M α+1 n L -(α+1) n + L -α+1 2 n
, for c a constant that only depends on α, that can be expressed through the Gamma function evaluated in quantity depending on α, meaning that when α is big, c behaves like α α . Note that it is not possible to derive a better bound only given Eqs. (4), ( 5) and (7).

Proof [Sketch for Theorem 6, details in Appendix A.5] Based on the refined calibration inequality in Eq. ( 5), and using that E[X] = ∞ 0 P(X > t) dt, it is possible to show that the expectation of the excess risk behave like

∞ 0 P X (d(g * (x), F ) < t) sup x P Dn ( g n (x) -g * (x) > t) dt.
Based on Assumptions 2 and 4, the integrand behaves like t α exp(-L n t 2 /(1 + M n t)). A change of variable and the study of the Gamma function leads to the result. We provide all the details in Appendix A.5. Note that while we stated Theorem 6 under an exponential inequality of Bernstein type (Assumption 2), similar theorems can be derived for any type of exponential concentration inequality, as stated in Lemma 19 in Appendix A.6.

Theorem 6 is to put in perspective with the work of [START_REF] Nowak-Vila | Sharp analysis of learning with discrete losses[END_REF] which considers the same setup as ours, yet only succeeds to derive acceleration by a power 2(α + 1)/(α + 2), while we got an acceleration by a power (α + 1)/2 as already mentioned in the related work section. This gain will appear more clearly in Theorem 15. [START_REF] Steinwart | Fast rates for support vector machines using Gaussian kernels[END_REF] for a margin condition designed for the Hinge loss). Note that L 2 concentration on g n towards g * (such as the one derived by [START_REF] Marteau-Ferey | Beyond least-squares: Fast rates for regularized empirical risk minimization through self-concordance[END_REF] for logistic regression) could also be turned into fast convergence of f n towards f * , since, in essence, for points x ∈ X where ρ(dx) is high, the quantity g * (x)g n (x) will have a non-negligible contribution to g *g n L 2 -allowing to cast concentration in L 2 to concentration pointwise in x -and for points x ∈ X where ρ(dx) is negligible, it is acceptable to pay the worst error, since it will have a small contribution on the excess of risk. Finally, note that it is also possible to let the right hand-side term in Eq. (4) depends on x, and to modify Theorem 5 with L = E[L(X)].

The importance of constants

In this subsection, we discuss on the importance of constants when providing learning rates. Assumption 3 corresponds to asking for g * (x) never to enter a neighborhood of F defined through t 0 .

Similarly, when X is parameterized such that ρ X is uniform, the parameter α in Assumption 4 corresponds to the speed at which g * (x) "get through" the decision frontier F . In order to have a higher α and optimize the dependency in n in the bound of Theorem 6, it is natural to think of infinitesimal perturbations of g * to make it cross the boundary orthogonally (or even jump over it and satisfy the no-density seperation). To give a precise example, in binary classification, let us artificially add smoothness to the function g * (x) = x q when approaching zero. Consider

g * : [0, 1] → [-1, 1],
x → c q-p x p 1 x<c + x q 1 x≥c , and x uniform, and p < q. In this setting, α can be taken anywhere in [0, p -1 ). Naively, we could ask for the biggest possible α in order to have the best dependency in n in the learning rates given by Theorem 6. While this approach will higher α, it will also higher c α , compensating the gain one could expect from such a strategy. Indeed, for α ∈ [0, p -1 ], at best, we can take c α = 1 α<q -1 + c 1-qα 1 α≥q -1 . This shows the importance to optimize both α and c α c to minimize the lower bound appearing in Theorem 6 when given a fixed number of sample n.

In a word, while we only give results that are optimized in n, when n is fixed, better bounds could be given by optimizing parameters and constants simultaneously. For example, when X = R d and g * belongs to the Sobolev space H m for all m ∈ [0, m * ], and satisfies Assumption 4 for all α ∈ [0, α * ], we expect the best bound, that could be derived from our proof technique, to be of form

E Dn R(f n ) -R(f * ) ≤ min m≤m * ,α<α * α α c α c ψ g * H m n -m(α+1)
2d .

Yet, for simplicity, we will express those bounds as bn -m * (α * +1)

2d

, for b a big constant.

C B R

Application to nearest neighbors

In this section, we consider the Bayes approximate risk estimator proposed by [START_REF] Stone | Consistent nonparametric regression[END_REF], with weights given by nearest neighbors [START_REF] Cover | Nearest neighbor pattern classification[END_REF]. We prove, under regularity assumptions, concentration inequalities similar to Eq. ( 4), which allow us to derive exponential and polynomial rates. Given samples (X i , Y i ) ∼ ρ ⊗n , k ∈ N and a metric d on X , the estimator is

g n (x) = n i=1 α i (x)ϕ(Y i ), with α i (x) =    k -1 if n j=1 1 d(x,X j )≤d(x,X i ) < k 0 if n j=1 1 d(x,X j )<d(x,X i ) ≥ k (pk) -1 else, with p = n j=1 1 d(x,X j )=d(x,X i ) . (8)
To study the convergence of g n , we introduce the noise free estimator g * n = n i=1 α i (x)g * (X i ). This will allow to separate the error due to the randomness of the labels Y i ∼ ρ| X i , and the error due to the difference between g * (x) and the averaging of g * on the neighbors of x defining g n . To control the fist error, we need a bounded moment condition on ϕ(Y ). We reuse an assumption from [START_REF] Bernstein | Sur une modification de l'inéqualite de Tchebychev[END_REF], that is classic in machine learning (e.g., [START_REF] Caponnetto | Optimal rates for the regularized least-squares algorithm[END_REF][START_REF] Lin | Optimal rates for spectral algorithms with least-squares regression over Hilbert spaces[END_REF].

Assumption 5 (Sub-exponential moment of ρ| x ) Suppose that there exists σ 2 , M > 0 such that for any x ∈ supp ρ X , for any m ≥ 2, we have

E Y ∼ρ|x [ ϕ(Y ) -g * (x) m ] ≤ 1 2 m!σ 2 M m-2 .
Example 4 (Moment bound on ϕ(Y )) Assumption 5 is a classical assumption that is notably satisfied when ϕ(Y ) is bounded by M , with σ 2 its variance, or when (ϕ(Y ) | X) is Gaussian with covariance bounded by a constant independent of X (see a proof of this standard result by [START_REF] Fischer | Sobolev norm learning rates for regularized least-squares algorithms[END_REF].

To control the second error, we notice, for x ∈ supp ρ X , that the quantity g * (x)g * n (x) behaves like sup x ′ ∈B(x,r) g * (x)g * (x ′ ) , with r such that ρ X (B(x, r)) ≈ k/n, such a r modeling the distance between x and its k-th neighbor. This motivates the following assumption.

Assumption 6 (Modified Lipschitz condition (Chaudhuri and Dasgupta, 2014)) g * is said to verify the β-Modified Lispchitz condition if there exists c β > 0 such that for any

x, x ′ ∈ supp ρ X g * (x) -g * (x ′ ) ≤ c β ρ X (B(x, d(x, x ′ ))) β ,
where d is the distance on X , and B(x, t) ⊂ X the ball of center x and radius t.

Typically the β that appears in Assumption 6 is linked with the dimension of a subset of X containing most the mass of ρ X (see below). This will slow the rates accordingly to this dimension parameter, a property referred to as the curse of dimensionality.

Example 5 (Classical assumptions) When X = R d , if g is β ′ -Hölder continuous, and ρ X is regular in the sense that, there exists a constant c and t * > 0 such that for x ∈ supp ρ X and any t ∈ [0, t * ], ρ X (B(x, t)) ≥ cλ(B(x, t)), with λ the Lebesgue measure on X , then g satisfies the modified Lipschitz condition with β = β ′ /d. The condition on ρ X is usually split in a condition of minimal mass of ρ X , and a condition of regular boundaries of supp ρ X (e.g., [START_REF] Audibert | Fast learning rates for plug-in classifiers[END_REF]. We provide more details in Appendix B.1. We now state convergence results, respectively proven in Appendices B.2, B.3 and B.4, in which the constant values b 1 to b 6 appear explicitly. Note that results provided by Lemma 9 are already known in the literature [START_REF] Györfi | A Distribution-Free Theory of Nonparametric Regression[END_REF], while Theorems 10 and 11 were only known in binary classification, but we generalize them to any discrete structured prediction problem. It should be noted that rates in Theorem 11 match the minimax rates derived by [START_REF] Audibert | Fast learning rates for plug-in classifiers[END_REF] in the case of binary classification.

Lemma 9 (Nearest neighbors concentration) Under Assumptions 5 and 6, there exist constants b 1 , b 2 , b 3 > 0, such that for any x ∈ supp ρ X and any t > 0,

P Dn ( g n (x) -g * n (x) > t) ≤ 2 exp - b 1 kt 2 1 + b 2 t .
And for t > (k/2n) β , when ρ X is continuous

P Dn ( g * n (x) -g * (x) > t) ≤ exp -b 3 nt 1 β
.

Theorem 10 (Nearest neighbors fast rates under no-density assumption) When ℓ is bounded by ℓ ∞ , satisfies Assumption 1, and Z is finite, under the no-density separation, Assumption 3, and Assumptions 5 and 6, there exist two constants b 4 , b 5 > 0 that do not depend on n or k such that for any n ∈ N * and any k such that (k/2n) β < t 0 , we have

E Dn R(f n ) -R(f * ) ≤ 2ℓ ∞ exp(-b 4 k) + ℓ ∞ exp(-b 5 n). (9)
Theorem 11 (Nearest neighbors fast rates under low-density assumption) When ℓ satisfies Assumption 1, and Z is finite, under the low-density separation, Assumption 4, and Assumptions 5 and 6, considering the scheme

k n = k 0 n 2β 2β+1
, for any k 0 > 0, there exists a constant b 6 > 0 that does not depend on n such that for any n ∈ N * ,

E Dn R(f n ) -R(f * ) ≤ b 6 n -β(α+1) 2β+1 . ( 10
)
Remark 12 (Scope of our work) The same type of argument works for other local averaging methods, such as Nadaraya-Watson (Nadaraya, 1964;[START_REF] Watson | Smooth regression analysis[END_REF], local polynomials [START_REF] Cleveland | Robust locally weighted regression and smoothing scatterplots[END_REF][START_REF] Audibert | Fast learning rates for plug-in classifiers[END_REF] or decision trees [START_REF] Breiman | Classification and Regression Trees[END_REF].

Application to reproducing kernel ridge regression

In this section, we consider the kernel ridge regression estimate g n of g * first proposed by [START_REF] Ciliberto | A consistent regularization approach for structured prediction[END_REF], and we prove, under regularity assumptions, uniform concentration inequalities similar to Eq. ( 4), which allow us to derive super fast rates at the end of the section. Given a symmetric, positive semi-definite kernel k : X × X → R + , the kernel ridge regression estimation g n of g * is defined similarly to Eq. ( 8) yet with weights α(x) ∈ R n defined as

α(x) = ( K + λ) -1 Kx , K = 1 n k(X i , X j ) i,j≤n ∈ R n×n , Kx = 1 n k(x, X i ) i≤n ∈ R n .
= [-1, 1], g * (x) = sign(x) * |x| 1 α , for α ∈ {.1, 1}
and ρ X uniform. We plot in solid the logarithm of the excess risk averaged over 100 trials against the logarithm of the number of samples for n ∈ [10, 10 6 ], and plot in dashed the expected slope of those curves due to Theorem 11 (i.e., we fit the constant C in the rate Cn -γ with γ obtained from the bound in Eq. ( 10)).

To state regularity assumptions, we introduce a minimal setup linked to the reproducing kernel k.

To keep the exposition clear, we relegate technicalities in Appendix C. We define the operator K operating on functions f ∈ L 2 (X , H, ρ X ) and K X operating on f ∈ L 2 (X , R, ρ X ), both defined as

(Kf )(x ′ ) = X k(x ′ , x)f (x) dρ X (x).
Inheriting from the symmetry and positive semi-definiteness of k, K is self-adjoint with spectrum in R + . To study the convergence of g n to g * , it is useful to introduce the approximate orthogonal projection on im K 1 2 , defined for λ > 0 as

g λ = K(K + λ) -1 g * .
We introduce three assumptions linked with the regularity of the problem, referred to as the capacity condition, interpolation inequality and source condition. Those are classical assumption to prove uniform rates of the kernel ridge regression estimates. They could be found, in particular, by [START_REF] Fischer | Sobolev norm learning rates for regularized least-squares algorithms[END_REF] under the respective names of (EVD), (EMB) and (SRC), but also by [START_REF] Pillaud-Vivien | Statistical optimality of stochastic gradient descent on hard learning problems through multiple passes[END_REF]; [START_REF] Lin | Optimal rates for spectral algorithms with least-squares regression over Hilbert spaces[END_REF]. Our assumptions differ in that they are expressed for vector-valued functions, which usually generate compactness issues [START_REF] Caponnetto | Optimal rates for the regularized least-squares algorithm[END_REF]. However, when Z is finite, H is finite dimensional, and K can be shown to be a compact operator, thus allowing to consider fractional power without definition issues.

Assumption 7 (Capacity condition) Suppose

Tr (K σ X ) < +∞ for σ ∈ [0, 1]. Assumption 8 (Interpolation inequality) Assume the existence of p ∈ [0, 1 2 ], c p > 0 such that ∀ g ∈ (ker K) ⊥ , K p g L ∞ ≤ c p g L 2 .
Assumption 9 (Source condition) Suppose g * ∈ im K q for q ∈ (p, 1].

F R S P

When q = 1 /2, the source condition is often expressed as g * belonging to the reproducing kernel Hilbert space associated to the kernel k. Note that when k is bounded, Assumptions 7 and 8 hold with σ = 1 and p = 1 /2. In those assumptions, for p and σ the smaller, and for q the bigger, the faster the convergence rates will be.

Example 6 (Classical assumptions) For Assumption 8 to hold, minimal mass and regular support of ρ, similarly to Example 5, are often assumed, as well as regularity of functions in im K p , in coherence with Remark 8. For Assumption 9 to hold, it is classical to assume regularity of g * , matching the regularity of function spaces derived from the kernel k. The value of σ in Assumption 7 often comes has a bonus of regularity assumptions on ρ and specificity of the RKHS implied by k. See Example 2 by [START_REF] Pillaud-Vivien | Statistical optimality of stochastic gradient descent on hard learning problems through multiple passes[END_REF] and Section 4 by [START_REF] Fischer | Sobolev norm learning rates for regularized least-squares algorithms[END_REF] as well as references therein for concrete examples.

We now state convergence results respectively proven in Appendices C.5 and C.6, C.7, and C.8. Lemma 13 is a generalization to vector-valued functions of kernel ridge regression uniform convergence rates known for real-valued function (see [START_REF] Fischer | Sobolev norm learning rates for regularized least-squares algorithms[END_REF]. Note that a similar result to Theorem 14 was provided for binary classification by [START_REF] Koltchinskii | Exponential convergence rates in classification[END_REF], but we generalize exponential rates with kernel ridge regression to any discrete structured prediction problem. Theorem 15 is new, even in the context of binary classification. It states that, while, up to now, only rates in n -1/4 were known for f n [START_REF] Ciliberto | A general framework for consistent structured prediction with implicit loss embeddings[END_REF], one can indeed hope for arbitrarily fast rates, depending on the hardness of the problem, read in the value of α ∈ [0, ∞).

Lemma 13 (Reproducing kernel concentration) Under Assumptions 7, 8 and 9, for any λ > 0,

g λ -g * L ∞ ≤ b 1 λ q-p . With b 1 = c p K -q g * L 2
. Moreover, when the kernel k is bounded and under Assumption 5, there exists three constants b 2 , b 3 , b 4 , b 5 > 0 that does not depend nor on λ nor on n such that

P ( g n -g λ ∞ > t) ≤ b 2 λ -σ exp -b 3 nλ 2p + 4 exp - nλ 2p+σ t 2 b 4 + b 5 t .
As long as b 3 n ≥ λ -p , and λ ≤ min K op , 1 .

Theorem 14 (Kernel ridge regression fast rates under no-density assumption) When the loss ℓ is bounded, satisfies Assumption 1 and Z is finite, under the t 0 -no-density separation condition, and Assumptions 5, when k is bounded, if λ n = λ, for any λ > 0 such that g *g λ L ∞ < t 0 , then there exist two constants b 6 , b 7 > 0 such that, for any n ∈ N * ,

E Dn R(f n ) -R(f * ) ≤ b 6 exp(-b 7 n), ( 11
)
with f n given by the kernel ridge regression surrogate estimate.

Theorem 15 (Kernel ridge regression fast rates under low-density assumption) When ℓ satisfies Assumption 1, is bounded and Z is finite, under the α-low-density separation condition, and Assumptions 5, 7, 8 and 9, if

λ n = λ 0 n -1
2q+σ , for any λ 0 > 0, there exists b 8 > 0, such that for any

n ∈ N * , E Dn R(f n ) -R(f * ) ≤ b 8 n -(q-p)(1+α) 2q+σ . ( 12
) C B R

Conclusion

In this paper, we have shown how, for discrete problems, to leverage exponential concentration inequalities derived on continuous surrogate problems, in order to derive faster rates than rates directly obtained through calibration inequalities. Those rates are arbitrarily fast, depending on a parameter characterizing the hardness of the discrete problem. We have shown how this method directly applies to local averaging methods and to kernel ridge regression, which allowed us to derive "super fast" rates for any discrete structured prediction problem. This opens the way to several follow-up, such as • Applicative follow-up, consisting of tackling concrete problem instances, such as predicting properties of DNA-sequence [START_REF] Jaakkola | A discriminative framework for detecting remote protein homologies[END_REF], e.g., gene mutations responsible for diseases, with well-designed kernels on DNA in order to higher the exponent appearing in Theorem 15. • Computational follow-up, pushing our analysis further to understand how to design better algorithms on discrete problems. For example, by adding a regularization pushing g n away from the decision frontier F , and adding a term in 1 gn(x)-g * (x) >d(gn(x),F ) in Eq. ( 5) for the analysis.

• Theoretical follow-up, to widen our analysis to other types of smooth surrogates, and to parametric methods, such as deep learning models, assuming that functions are parameterized by a parameter θ, that some analysis gives concentration on θ nθ * similar to Eq. ( 4) and that calibration inequalities relate the error on θ with the error between

f n = f θn and f * = f θ * . F R S P F R S P C B R

Appendix A. Fast rates

In the following, we consider X and Y to be Polish spaces, i.e., separable completely metrizable topological spaces, in order to define the distribution ρ. We also consider Z endowed with a topology that makes it compact, and that makes z → E Y ∼µ ℓ(z, Y ) continuous for any µ ∈ ∆ Y , in order to have minimizer well defined. For a Polish space A, we denote by ∆ A the simplex formed by the set of Borel probability measures on this space. For ρ ∈ ∆ X ×Y , we denote by ρ| x the conditional distribution of Y given x, and by ρ X the marginal distribution over X . We suppose H separable Hilbert and that the mapping ϕ is measurable in order to define the pushforward measure ϕ * ρ| x . We assume that, for ρ X -almost every x, (ϕ(Y )|X = x) has a second moment, in order to consider the conditional mean g * (x) as the solution of the well defined problem consisting of minimizing ξϕ(Y ) 2 for ξ ∈ H. We consider ψ to be continuous, in order to have the decoding problem well posed.

A.1. Proof of Lemma 1

With the notation of Lemma 1, for

x ∈ supp ρ X E Y ∼ρ|x [ℓ(f n (x), Y ) -ℓ(f * (x), Y )] = ψ(f n (x)) -ψ(f * (x)), g * (x) H = ψ(f n (x)), g n (x) + ψ(f n (x)), g * (x) -g n (x) -ψ(f * (x)), g * (x) ≤ ψ(f * (x)), g n (x) + ψ(f n (x)), g * (x) -g n (x) -ψ(f * (x)), g * (x) = ψ(f n (x)) -ψ(f * (x)), g * (x) -g n (x) ≤ ψ(f n (x)) -ψ(f * (x)) H g * (x) -g n (x) H ≤ 2c ψ g * (x) -g n (x) H ,
where the inequality ψ(f n (x)), g n (x) ≤ ψ(f * (x)), g n (x) is due to the fact that f n (x) minimizes the functional z → ψ(z), g n (x) . Integrating over X leads to the results in Lemma 1.

A.2. Proof of Lemma 2

The first part of the lemma is a geometrical result stating that to go from two elements ξ 1 and ξ 2 in ∆ ϕ(Y) , leading to two different decoding, one has to pass by a point ξ 1/2 ∈ F , where there is at least two possible decodings. Let make it clearer. Consider x ∈ supp ρ X and suppose that

f n (x) = f * (x), define the path ζ : [0, 1] → ∆ ϕ(Y) λ → λg n (x) + (1 -λ)g * (x).
Consider d : ∆ ϕ(Y) → Z the decoding function used to retrieve f * and f n , from g * and g n , satisfying

d(ξ) ∈ arg min z∈Z ψ(z), ξ . Consider the path d • ζ : [0, 1] → Z, it goes from ζ(0) = f * (x) to ζ(1) = f n (x). Consider λ ∞ the supremum of (d • ζ) -1 (f * (x)
). We will show that ζ(λ ∞ ) ∈ F , this will lead to

g n (x) -g * (x) = g n (x) -ζ(λ ∞ ) + ζ(λ ∞ ) -g * (x) ≥ ζ(λ ∞ ) -g * (x) ≥ d(g * (x), F ),
and to Lemma 2 by contraposition.

F R S P To show that ζ(λ ∞ ) ∈ F , we will show that f * (x) ∈ arg min z ψ(z), ζ(λ ∞ ) ⊂ {f * (x)}
. By definition of the supremum, there exists a sequence (λ p ) p∈N converging to λ ∞ such that

f * (x) ∈ arg min z ψ(z), λ p g n (x) + (1 -λ p )g * (x) ,
meaning that for all z = f * (x)

ψ(f * (x)), λ p g n (x) + (1 -λ p )g * (x) ≤ ψ(z), λ p g n (x) + (1 -λ p )g * (x) .
By continuity of the scalar product, it means that it holds for p = ∞, which means

f * (x) ∈ arg min z ψ(z), ζ(λ ∞ ) . Now, suppose that arg min z ψ(z), ζ(λ ∞ ) = {f * (x)}, this means that for all z = f * (x), ψ(f * (x)), λ ∞ g n (x) + (1 -λ ∞ )g * (x) < ψ(z), λ ∞ g n (x) + (1 -λ ∞ )g * (x) .
By continuity of this function accordingly to λ, this means that this still holds for λ ∞ + ε z for ε z > 0.

Taking ε = inf z∈Z ε z , it means that λ ∞ + ε ∈ (d • ζ) -1 (f * (x)). When Z is finite, ε > 0, which contradict the definition of λ ∞ . Therefore ζ(λ ∞ ) ∈ F .
The second part of Lemma 2 follows from derivations in Appendix A.1.

Remark 16 (Extension to discrete cases) Note that the same argument can be generalized to discrete problems -which could be defined as Z endowed with a topology that makes z → E Y ∼µ [ℓ(z, Y )] continuous with respect to z, and Z\ {z} locally compact for any z ∈ Z -that are not degenerate, in the sense that ρ X almost all x ∈ X , there exists t > 0 such that the cardinality of the set defined as z

E Y ∼ρ|x [ℓ(z, Y )] -inf z ′ ∈Y E Y ∼ρ|x [ℓ(z ′ , Y )] < t if finite.
This holds for classification with infinite countable classes, but it does not for regression on the set of rational numbers.

Remark 17 (Extension to general cases)

To remove the condition Z finite, one can change the definition of d(g * (x), F ) to inf ξ∈H;{f * (x)} =arg min ψ(z),ξ ξg * (x) , in order to make Lemma 2 hold for any Z.

A.3. Equivalence between generalizations of the Tsybakov margin condition

While we state the margin condition with d(g * (x), F ), it could also be stated with d(g * (x), F ∩ Conv(ϕ(Y))) or with, which is the quantity considered by [START_REF] Nowak-Vila | Sharp analysis of learning with discrete losses[END_REF],

γ(x) = inf z =z * E Y ∼ρ|x ℓ(z, Y ) -E Y ∼ρ|x ℓ(z * , Y ) = inf z =z * ψ(z) -ψ(z * ), g * (x) .
Indeed, when Z is finite and ℓ is proper in the sense that ℓ(•, y) = ℓ(•, z) implies z = y, and that there is no z that minimizes a linear combination of (ℓ(•, y)) y∈Y without minimizing a convex combination of the same family, we have the existence of two constants such that

cγ(x) ≤ d(g * (x), F ∩ Conv(ϕ(Y))) ≤ d(g * (x), F ) ≤ c ′ γ(x). C B R A.3.1. M
Let z ′ be the argmin defining γ, geometric properties of the scalar product imply the existence of a

ξ ∈ (ϕ(z ′ ) -ϕ(z * )) ⊥ such that ϕ(z ′ ) -ϕ(z * ), g * (x) = ϕ(z ′ ) -ϕ(z * ) g * (x) -ξ . Therefore ϕ(z ′ ) -ϕ(z * ), g * (x) ≥ min y,y ′ ϕ(y) -ϕ(y ′ ) g * (x) -ξ .
Note that, by definition of ξ, ξ, ϕ(z

′ ) = ξ, ϕ(z * ) . If ξ ∈ R z * then ξ ∈ F , otherwise ξ / ∈ R z *
and then, there exists a point between ξ and g * (x) that belongs to the decision frontier (see Appendix A.2 for a proof -for which we need some regularity assumption such as Z finite). In every case,

g * (x) -ξ ≥ d(g * (x), F ).
This implies the existence of c ′ .

A.3.2. S

For any g n such that f n (x) = z, we have

ψ(z) -ψ(z * ), g * (x) = ψ(z), g * (x) -g n (x) + ψ(z), g n (x) -ψ(z * ), g * (x) ≤ ψ(z), g * (x) -g n (x) + ψ(z * ), g n (x) -ψ(z * ), g * (x) ≤ 2c ψ g * (x) -g n (x) .
If we take the infimum on both sides we have

d(g * (x), F ) = inf gn(x) / ∈R f * (x) g n (x) -g * (x) ≥ 1 2c ψ inf z =z * ψ(z) -ψ(z * ), g * (x) ,
where the left equality is provided, when Z is finite, by a similar reasoning to the one in Appendix A.2. This implies the existence of c. Note also that if the loss is proper in the sense that if z minimizes ψ(z), ξ for a ξ ∈ H, there exists a ξ ∈ Conv ϕ(Y) such that z minimizes ψ(z), ξ , we can consider g n (x) ∈ Conv(ϕ(Y)), and therefore restrict F to F ∩ Conv ϕ(Y). Finally we have shown that, when Z finite and ℓ proper

cγ(x) ≤ d(g * (x), F ∩ Conv(ϕ(Y))) ≤ d(g * (x), F ) ≤ c ′ γ(x).
This explains why we would consider γ(x), d(g * (x), F ∩ Conv(ϕ(Y))) or d(g * (x), F ) to define the margin condition, it will only change the value of constants in Assumptions 3 and 4.

A.4. Refinement of Theorem 5

It is possible to refine Theorem 5 to remove the condition that the loss ℓ is bounded. In the following, we omit the dependency of L n and M n to n. Lemma 18 (Refinement of Theorem 5) Under refined calibration (5), concentration, Assumption 2, and no-density separation, Assumption 3, the risk is controlled as

E Dn R(f n ) -R(f * ) ≤ 4c ψ L -1/2 exp - t 2 0 L 2 1/2 + 4c ψ M L -1 exp - t 0 L 2M .
Note that it is not possible to derive a better bound only given Eqs. (4), ( 5) and ( 6). Yet when ℓ is bounded by ℓ ∞ , we have

E Dn R(f n ) -R(f * ) ≤ ℓ ∞ exp - Lt 2 0 1 + M t 0 .
Proof Using the calibration inequality along with the no-density separation one, we get

R(f n ) -R(f * ) ≤ 2c ψ E X 1 gn(X)-g * (X) ≥t 0 g n (X) -g * (X) = 2c ψ ∞ t 0 P X ( g n (X) -g * (X) ≥ t) dt.
Taking the expectation over D n and using concentration inequality we have

E Dn R(f n ) -R(f * ) ≤ 2c ψ ∞ t 0 P X,Dn ( g n (X) -g * (X) ≥ t) dt ≤ 2c ψ ∞ t 0 exp - Lt 2 1 + M t dt.
We only need to study the integral

∞ t 0 exp -Lt 2 1+M t dt.
We first clean the dependency on t insider the exponential using that

1 2 exp(-Lt 2 ) + exp - Lt M ≤ exp - Lt 2 1 + M t ≤ exp - Lt 2 2 + exp - Lt 2M .
We are left with the study of ∞ t 0 exp(-At p ) dt, for p ∈ {1, 2} and A > 0. The case p = 1, directly leads to A -1 exp(-At 0 ), explaining the part in L/M . The case p = 2 is similar to the Gaussian integral, and can be handle with the following tricks

∞ t 0 exp(-At 2 ) dt = 1 2 (-∞,-t 0 ]∪[t 0 ,∞) exp(-At 2 ) dt = 1 2 ((-∞,-t 0 ]∪[t 0 ,∞)) 2 exp(-A x 2 )) dx 1/2
. This last integral corresponds to integrate the function x → exp(-A x 2 ) for x ∈ R 2 on the domain ((-∞, -t 0 ] ∪ [t 0 , ∞)) 2 . This function being positive and the domain being included in the domain { x ≥ t 0 } and containing the domain x ≥ √ 2t 0 , we get

∞ { x ≥ √ 2t 0} exp(-A x 2 ) dx ≤ 2 ∞ t 0 exp(-At 2 ) dt 2 ≤ ∞ { x ≥t 0 } exp(-A x 2 ) dx. C B R
Using polar coordinate we get

∞ { x ≥t 0 } exp(-A x 2 ) dx = 2π ∞ t 0 r exp(-Ar 2 ) dr = πA -1 exp(-At 2 0 ). Therefore 2 -1 √ πA -1/2 exp(-A2t 2 0 ) 1/2 ≤ ∞ t 0 exp(-At 2 ) dt ≤ 2 -1 √ πA -1/2 exp(-At 2 0 ) 1/2 .
This explain the rates in L.

A.5. Proof of Theorem 6

Using the calibration and Bernstein inequalities we get, omitting the dependency of L n and M n to n,

E Dn R(f n ) -R(f * ) ≤ 2c ψ E Dn,X 1 d(gn(X),g * (X))≥d(g * (X),F ) g n (X) -g * (X) = 2c ψ ∞ 0 P Dn,X 1 d(gn(X),g * (X))≥d(g * (X),F ) g n (X) -g * (X) ≥ t dt = 2c ψ ∞ 0 E X P Dn ( g n (X) -g * (X) ≥ max {t, d(g * (X), F )}) dt ≤ 2c ψ ∞ 0 E X exp - L max {t, d(g * (X), F )} 2 1 + M max {t, d(g * (X), F )} 2 dt = 2c ψ ∞ 0 E X 1 d(g * (X),F )<t exp - Lt 2 1 + M t dt + 2c ψ ∞ 0 E X 1 d(g * (X),F )≥t exp -L d(g * (X), F ) 2 1 + M d(g * (X), F ) dt = 2c ψ ∞ 0 P X (d(g * (X), F ) < t) exp - Lt 2 1 + M t dt + 2c ψ E X d(g * (X), F ) exp - Ld(g * (X), F ) 2 1 + M d(g * (X), F )
.

Let begin by working on the first term. We have, using the low-density separation hypothesis

∞ 0 P X (d(g * (X), F ) < t) exp - Lt 2 1 + M t dt ≤ c α ∞ 0 t α exp(- Lt 2 1 + M t ) dt.
Recall the expression of the Gamma integral

∞ 0 t α exp(-Lt) dt = Γ(α + 1) L α+1 and ∞ 0 t α exp(-Lt 2 ) dt = Γ α+1 2 2L α+1 2
.

Let briefly talk about optimality. Up to now, we have only used three inequality: calibration, concentration exponential inequality and low-density separation. Therefore, when those inequalities F R S P hold as equalities, we get an lower bound of order on the excess of risk as α+1) .

E Dn R(f n ) -R(f * ) ≥ 2c ψ c α ∞ 0 t α exp(- Lt 2 1 + M t ) dt ≥ 2c ψ c α ∞ 0 1 2 t α exp(-Lt 2 ) + exp - Lt M dt = 2c ψ c α Γ α+1 2 4 L -α+1 2 + Γ(α + 1) 2 M α+1 L -(
For the upper bound, using that exp(-a/1 + b) ≤ exp(-a/2) + exp(-a/2b), we get α+1) .

∞ 0 t α exp(- Lt 2 1 + M t ) dt ≤ ∞ 0 t α exp(- Lt 2 2 ) dt + ∞ 0 t α exp(- Lt 2M ) dt = 2 α-1 2 Γ α + 1 2 L -α+1 2 + 2 α+1 Γ(α + 1)M α+1 L -(
Let study the second term in the excess of risk inequality. To enhance readability, write η(X) = d(g * (X), F ). We will first dissociate the two parts in the exponential with

E X η(X) exp - Lη(X) 2 1 + M η(X) ≤ E X η(X) exp - Lη(X) 2 2 + exp - Lη(X) 2M .
We are left with studying E[η(X) exp(-Aη(X) p )], for A > 0 and p ∈ {1, 2}. The function t → t exp(-At p ) achieves its maximum in t 0 = (pA) -1/p , it is increasing before and decreasing after. Notice that the quantity

P(η(X) < t 0 ) E X [η(X) exp(-Aη(X) p ) | η(X) < t 0 ] ≤ c α t α+1 0 exp(-At p 0 ) = c α p -α+1 p exp(-p -1/p )A -α+1
p , is exactly of the same order as the control we had on the first term in the excess of risk decomposition. This suggests to consider the following decomposition

E X [η(X) exp(-Aη(X) p )] = P(η(X) < t 0 ) E X [η(X) exp(-Aη(X) p ) | η(X) < t 0 ] + ∞ i=0 P(2 i t 0 ≤ η(X) < 2 i+1 t 0 ) E X η(X) exp(-Aη(X) p ) 2 i t 0 ≤ η(X) < 2 i+1 t 0 ≤ c α t α+1 o exp(-At p 0 ) + ∞ i=0 c α 2 α (2 i t 0 ) α+1 exp(-At p 0 (2 i ) p ) = c α t α+1 o exp(-p -1/p ) + ∞ i=0 2 α 2 i(α+1) exp(-p -1/p 2 ip ) .
The convergence of the last series, ensures the existence of a constant c such that

E X η(X) exp - Lη(X) 2 1 + M η(X) ≤ c L 2M -(α+1) + L 2 -α+1 2 .
Adding everything together, we get the existence of two constants c ′ , c ′′ , such that

E Dn R(f n ) -R(f * ) ≤ 2c ψ c α c ′ M α+1 L -(α+1) + c ′′ L -α+1 2 .
This ends the proof by considering c = max (c ′ , c ′′ ).

A.6. Refinement of Theorem 6

Some convergence analyses lead to exponential inequalities that are not of Bernstein type, indeed, our result still holds in those settings, as mentioned by the following lemma. In the following, we omit the dependency of L n and M n to n.

Lemma 19 (Refinement of Theorem 6) Under the assumptions of Theorem 6, if the concentration is not given by Assumption 2 but given, for some positive constants (a i , b i , p i ) i≤m , by, for all x ∈ supp ρ X and t > 0,

P Dn ( g n (x) -g * (x) > t) ≤ n i=1 a i exp(-b i t p i ).
Then the excess of risk is controlled by

E Dn R(f n ) -R(f * ) ≤ c n i=1 a i b -α+1 p i i ,
for a constant c that does not depend on (a i , b i ) i≤m .

Proof First of all, remark that the proof of Theorem 6 is linear in P Dn ( g n (x)g * (x) > t), therefore we only need to prove this lemma for (a, b, p), for which we proceed as in Theorem 6

E Dn R(f n ) -R(f * ) ≤ 2c ψ E Dn,X 1 gn(X)-g(X) ≥d(g(X),F ) g n (X) -g(X) = 2c ψ ∞ 0 P Dn,X 1 gn(X)-g(X) ≥d(g(X),F ) g n (X) -g(X) ≥ t dt = 2c ψ ∞ 0 E X P Dn ( g n (X) -g(X) ≥ max {t, d(g(X), F )}) dt ≤ 2c ψ a ∞ 0 E X exp (-b max {t, d(g(X), F )} p ) dt = 2c ψ a ∞ 0 E X 1 d(g(X),F )<t exp (-bt p ) dt + 2c ψ a ∞ 0 E X 1 d(g(X),F )≥t exp (-bd(g(X), F ) p ) dt = 2c ψ a ∞ 0 P X (d(g(X), F ) < t) exp (-bt p ) dt + 2c ψ a E X [d(g(X), F ) exp (-bd(g(X), F ) p )] .
Let begin by working on the first term. We have, using the low-density separation hypothesis

∞ 0 P X (d(g(X), F ) < t) exp -bt 2 dt ≤ c α ∞ 0 t β exp(-bt p ) dt. = b -1+β p c α ∞ 0 (b 1/p t) β exp(-(b 1/p t) p ) d(b 1/p t). = b -1+β p c α ∞ 0 t β exp(-t p ) dt = c α Γ(β, p)b -1+β p . F R S P
Let study the second term in the excess of risk inequality. To enhance readability, write η(X) = d(g(X), F ). We are left with studying E[η(X) exp(-bη(X) p )]. The function t → t exp(-bt p ) achieves it maximum in t 0 = (pb) -1/p , it is increasing before and decreasing after. Notice that the quantity

P(η(X) < t 0 ) E X [η(X) exp(-bη(X) p ) | η(X) < t 0 ] ≤ c α t β+1 0 exp(-bt p 0 ) = c α p -β+1
p exp(-p -1/p )b -β+1 p , is exactly of the same order as the control we had on the first term in the excess of risk decomposition. This suggests to consider the following decomposition

E X [η(X) exp(-bη(X) p )] = P(η(X) < t 0 ) E X [η(X) exp(-bη(X) p ) | η(X) < t 0 ] + ∞ i=0 P(2 i t 0 ≤ η(X) < 2 i+1 t 0 ) E X η(X) exp(-bη(X) p ) 2 i t 0 ≤ η(X) < 2 i+1 t 0 ≤ c α t β+1 o exp(-bt p 0 ) + ∞ i=0 c α 2 β (2 i t 0 ) β+1 exp(-bt p 0 (2 i ) p ) = c α t β+1 o exp(-p -1/p ) + ∞ i=0 2 β 2 i(β+1) exp(-p -1/p 2 ip ) .
The convergence of the last series ensures the existence of a constant c ′ such that

E X [η(X) exp(-bη(X) p )] ≤ c ′ b -β+1
p . Adding everything together ends the proof of this lemma. Note that we have the same type of optimality as the one stated in Theorem 6.

Because we use concentration inequalities for terms that are not necessarily centered, we usually get that Eq. ( 4) only holds for t > ε 0 where, typically ε 0 = E Dn g n (x)g * (x) , we can bypass this problem by adding in 1 t<ε 0 in the probability, motivating the study leading to the following lemma.

Lemma 20 (Handling bias in concentration inequality) Under the assumptions of Theorem 6, if the concentration is not given by Assumption 2 but given, for a ε 0 > 0, by, for all x ∈ supp ρ X and t > 0,

P Dn ( g n (x) -g * (x) > t) ≤ 1 t<ε 0 .
Then the excess of risk is controlled by

E Dn R(f n ) -R(f * ) ≤ 2c ψ c α ε α+1 0 .
Proof We retake the beginning of the proof of Theorem 6, and change its ending with

E Dn R(f n ) -R(f * ) ≤ 2c ψ E Dn,X 1 gn(X)-g(X) ≥d(g(X),F ) g n (X) -g(X) = 2c ψ ∞ 0 P Dn,X 1 gn(X)-g(X) ≥d(g(X),F ) g n (X) -g(X) ≥ t dt = 2c ψ ∞ 0 E X P Dn ( g n (X) -g(X) ≥ max {t, d(g(X), F )}) dt ≤ 2c ψ ∞ 0 E X 1 t<ε 0 1 d(g(X),F )<ε 0 dt = 2c ψ ε 0 P X (d(g(X), F ) < ε 0 ) dt. C B R
This leads to the result after applying the α-margin condition.

Appendix B. Nearest neighbors B.1. Usual assumptions to derive nearest neighbors convergence rates

Assumption 6 can be seen as the backbone that allow to control g * n (x)g * (x) in a uniform manner. This assumption that relates the regularity of g * with the density of ρ X has been historically approached in the following manner. Assume that g * is β ′ -Hölder, that is, for any

x, x ′ ∈ supp ρ X g * (x) -g * (x ′ ) ≤ a 1 d(x, x ′ ) β ′ .
Suppose that X = R d , that ρ X is continuous against λ, the Lebesgue measure, with minimal mass in the sense that there exists a p min > 0 such that dρ X dλ (X ) does not intersect (0, p min ), and that supp ρ X has regular boundaries in the sense that there exist a 2 , t 0 > 0 such that for any x ∈ supp ρ X and t ∈ (0, t 0 ) λ (B(x, t) ∩ supp ρ X ) ≥ a 2 λ (B(x, t)) .

For example an orthant satisfies this property with a 2 = 2 -d and t 0 = ∞, and B(0, 1) satisfies this property with a 2 = λ (B(0, 1) ∩ B(1, 1)) /λ (B(0, 1)) and t 0 = 1. In such a setting, we get

g * (x) -g * (x ′ ) ≤ a 1 d(x, x ′ ) β ′ = a 1 λ(B(x, d(x, x ′ ))) λ(B(0, 1)) β ′ d .
Where d(x, x ′ ) < t 0 , we have

λ(B(x, d(x, x ′ ))) ≤ a -1 2 λ B(x, d(x, x ′ )) ∩ supp ρ X ≤ a -1 2 p -1 min ρ X (B(x, d(x, x ′ ))) β .
This means that for any x ∈ supp ρ X and x ′ ∈ B(x, t 0 ) we have, with β = β ′ d and the constant

a 3 = a 1 a -β 2 p -β min λ(B(0, 1)) -β g * (x) -g * (x ′ ) ≤ a 3 ρ X (B(x, d(x, x ′ ))) β .
While, we actually do not need the bound to hold for d(x, x ′ ) > t 0 in the following proof, to check the veracity of our remark on Assumption 6, one can verify that under our assumptions on ρ X , supp ρ X is bounded, and therefore g * is too. And if g * is bounded by c ϕ , by considering

a ′ 3 = max 2c ϕ a -β 2 p -β min t -β ′ 0 , a 3 , this bound holds for any x, x ′ ∈ supp ρ X .

B.2. Proof of Lemma 9

Control of the variance term. For x ∈ ρ X , the variance term can be written

g n (x) -g * n (x) = 1 k k i=1 ϕ(Y (i) ) -E Y (i) X (i) .
Where the index (i) is such that X (i) is the i-th nearest neighbor of x in (X i ) i≤n . Since, given (X i ) i≤n , the (Y i ) i =n are independent, distributed according to ⊗ i≤n ρ| X i , we can use a concentration inequality to control it. We recall Bernstein concentration inequality in such spaces, derived by Yurinskii (1970), we will use the formulation of Corollary 1 from [START_REF] Pinelis | Remarks on inequalities for large deviation probabilities[END_REF]. Theorem 21 (Concentration in Hilbert space [START_REF] Pinelis | Remarks on inequalities for large deviation probabilities[END_REF])) Let denote by A a Hilbert space and by (ξ i ) a sequence of independent random vectors on A such that E[ξ i ] = 0, and that there exists M, σ 2 > 0 such that for any m ≥ 2

n i=1 E [ ξ i m ] ≤ 1 2 m!σ 2 M m-2 .
Then for any t > 0

P( n i=1 ξ i ≥ t) ≤ 2 exp - t 2 2σ 2 + 2tM
.

This explain Assumption 5, allowing, because there is only k ξ i active in n i=1 α i (x)ξ i , to get

P Dn ( g n (x) -g * n (x) > t) ≤ 2 exp - kt 2 2σ 2 + 2M t .
Control of the bias term. Under the Modified Lipschitz condition, Assumption 6,

g * n (x) -g n (x) = n i=1 α i (x) (g n (x) -g * (X i )) ≤ n i=1 α i (x) g n (x) -g * (X i ) ≤ c β n i=1 α i (x)ρ X (B(x, d(x, X i ))) β ≤ c β ρ X (B(x, d(x, X k (x)))) β .
When ρ X is continuous, it follows from the probability integral transform (also known as universality of the uniform) that ρ X (B(x, d(x, X k (x)))) behaves like the k-th order statistics of a sample (U i ) i≤n of n uniform distributions on [0, 1]. Therefore, for any s ∈ [0, 1]

P Dn (ρ X (B(x, d(x, X k (x)))) > s) = P n i=1 1 U i <s ≤ k .
Recall the multiplicative Chernoff bound, stating that for (Z i ) i≤n n independent random variables in {0, 1}, if Z = n i=1 Z i , and µ = E[Z], for any δ > 0

P (Z ≤ (1 -δ)µ) ≤ exp - δ 2 µ 2 . Since, for s ∈ [0, 1], E[1 U i <s ] = P(U i < s) = s, we get, when k ≤ ns/2 P n i=1 1 U i <s ≤ k ≤ exp - (ns -k) 2 2ns ≤ exp - ns 8 . With s = c -1 β t 1 β , we get P Dn ( g * n (x) -g n (x) > t) ≤ exp - nt 1 β 8c β .
Remark that when g * is β ′ Hölder, we get the same result with ρ X (B(x, t)) instead of t 1 β by considering 1 X i ∈B(x,t) instead of 1 U i ≤t . Note that there is way to bound a Binomial distribution with a Gaussian for t smaller than the mean of the binomial distribution, which would allow to get a bound that holds for any t > 0 [START_REF] Slud | Distribution inequalities for the binomial law[END_REF].

B.3. Proof of Theorem 10

Using the proof of Theorem 5, we get

E Dn R(f n ) -R(f * ) ≤ ℓ ∞ P Dn ( g(x) -g * n (x) > t 0 ) .
Because g n (x)g * (x) > t 0 implies that either g n (x)g * n (x) > t 0 /2 or g * n (x)g * (x) > t 0 /2, we get using Lemma 9

P Dn ( g(x) -g * n (x) > t 0 ) ≤ 2 exp - b 1 kt 2 0 4 + 2b 2 t 0 + exp -2 -1 β b 3 nt 1 β 0 + 1 t 0 >(k/2n) β .
This explains the result of Theorem 10.

B.4. Proof of Theorem 11

First of all for t > 0, and x ∈ supp ρ X , because g n (x)g * (x) > t implies that either g n (x)g * n (x) > t/2 or g * n (x)g * (x) > t/2, we have the inclusion of events:

{D n | g n (x) -g * (x) > t} ⊂ {D n | g n (x) -g * (x) > t/2} ∪ {D n | g n (x) -g * (x) > t/2} ,
which translates in term of probability as

P Dn ( g n (x) -g * (x) > 2t) ≤ P Dn ( g n (x) -g * (x) > t) + P Dn ( g n (x) -g * (x) > t) . ≤ 2 exp - b 1 kt 2 1 + b 2 t + exp -b 3 nt 1 β + 1 t<( k 2n ) β .
Using the refinements of Theorem 6 exposed in Appendix A.6, we get that there exists a constant c > 0 that does not depend on k or n such that α+1) .

E Dn Rf n -R(f * ) ≤ c k -α+1 2 + n -β(α+1) + (nk -1 ) β(
We optimize this last quantity with respect to k by taking k = n γ , and choosing γ such that γ = 2(1γ)β leading to γ = 2β/(2β + 1) and to rates in n to the power minus β(α + 1)/(2β + 1).

B.5. Numerical Experiments

Interestingly, on numerical simulations such as the one presented on Figure 3, we observed two regimes. A first regime where bound are meaningless because of constants being too big, and where the error decreases independently of the exponent expected through Theorem 11, and a final regime where rates corresponds to the bond given by the theorem. Note that when α >> 1, with our computation parameter, we do not get to really illustrate convergence rates, as this final regime get place for bigger n than what we have considered (n max = 10 6 ), this being partly due to the constant c β in Assumption 6 being big for the g * we considered. Furthermore, note that, for example, if a problem satisfied Assumption 3 with a really small t 0 , we expect that exponential convergence rates are only going to be observed for n > N , with N really big, and for which the excess of risk is already really small. 3. We precise the error is evaluated on 100 points forming a regular partition of X = [-1, 1], and the expectation E Dn is approximated by considering 100 datasets. The violet curve is cropped at n ≈ 10 5 , because the error was null afterwards with our evaluation parameters (only 100 points to evaluate the error), forbidding us to consider the logarithm of the excess of risk.

C B R k(•, x)ξ in L 2 , defined formally as S : G → L 2 γ → x → k ⋆ x γ.
While intrinsically similar, it is useful to distinguish between G and im S ⊂ L 2 . Note that S is continuous, since on atom

k x ξ, Sk x ξ L 2 ≤ k x (•) L 2 ξ H ≤ k(x, x) ξ H = k x ξ G .
The fact that S is a bounded operator justifies the introduction of the following operators.

Central operators. In the following, we will make an extensive use of

S ⋆ : L 2 (X , H, ρ X ) → G the adjoint of S, defined as S ⋆ g = E ρ X [k X g(X)]; the covariance operator Σ : G → G, defined as Σ := S ⋆ S = E ρ X [k X k ⋆ X ]; and its action on L 2 , K : L 2 (X , H, ρ X ) → L 2 (X , H, ρ X ), defined as Kg := SS ⋆ g = E X [k(•, X)g(X)
]. Finally, we have define the four central operators

Sγ = k ⋆ (•) γ, S ⋆ g = E ρ X [k X g(X)] Σ := S ⋆ S = E ρ X [k X k ⋆ X ], Kg := SS ⋆ g = E X [k(•, X)g(X)]. (13)
It should be noted that this construction is usually avoided since, based on the fact that the Frobenius norm of K behave like dim(H), meaning that when H is infinite dimensional, K is not a compact operator. However, since we consider Z finite, we can always consider H = R #Z with ϕ(y) = (ℓ(z, y) z∈Z and ψ(z) = (1 z=z ′ ) z ′ ∈Z , and moreover, we will see that a way can be worked out, even when H is infinite dimensional, which was already shown by [START_REF] Ciliberto | A consistent regularization approach for structured prediction[END_REF].

R - - RKHS.
Usually convergence in RKHS are studied for real-valued function. We need convergence results for vector-valued function. As mentioned above, we only need the results for Euclidean space, however, we will do it for function that are maps going into potentially infinite dimensional Hilbert space. Indeed, this does not lead to major complication. We provide here one way to get around this issue. An alternative formal way to proceed can be found [START_REF] Ciliberto | A consistent regularization approach for structured prediction[END_REF].

Real-valued RKHS. We build the real-valued RKHS G X as the closure of the span of the atoms kx for x ∈ X , under the metric induced by the scalar product kx , kx ′ = k(x, x ′ ). Similarly, we build S, S⋆ , Σ and K. We shall see that the action of Σ on G can be factorized through its actions Σ on G X .

Algebraic equivalences.

Based on the fact that kx G X = k x op = k(x, x), it is possible to build an isometry that match kx in G X to k x in the space of continuous linear operator from H to G. With (ē i ) i∈N an orthogonal basis of G X , and (f j ) j∈N an orthogonal basis of H, we get an orthogonal basis (e i f j ) i,j∈N of G. This is exaclty the construction G = G X ⊗ H of [START_REF] Ciliberto | A consistent regularization approach for structured prediction[END_REF].

Note that for µ 1 , µ 2 two measures on X , we can check that

E X∼µ 1 [k X k ⋆ X ] E X 0 ∼µ 2 [k X 0 ] 2 op = E X∼µ 1 [ kX k⋆ X ] E X 0 ∼µ 2 [ kX 0 ] 2 G X = E X,X ′ ∼µ 1 ;X,X ′ ∼µ 2 [k(X 0 , X)k(X, X ′ )k(X ′ , X ′ 0 )].
This explains that we will allow ourselves to write derivations of the type

(Σ + λ) -1 2 k x g n (x) G ≤ ( Σ + λ) -1 2 kx G X g n (x) H . F R S P
Note also that for g

:= ij c ij e i f j ∈ G, with ij c 2 ij = 1, ci := (c ij ) j∈N ∈ ℓ 2 , Ā an self-adjoint operator on G X and A its version on G, we have Ag 2 G = ijk c ij c kj Āē i , Āē k G = ij ci , cj ℓ 2 Āē i , Āē k G X ≤ ij ci ℓ 2 cj ℓ 2 Āē i , Āē k G X = Ā i ci ℓ 2 ēi 2 G X ≤ Ā 2 op ,
which explains why we will consider derivations of the type

(Σ + λ) 1 2 ( Σ + λ) -1 (Σ + λ) 1 2 op ≤ ( Σ + λ) 1 2 ( Σ + λ) -1 ( Σ + λ) 1 2 op .
Finally, notice that because of the same consideration, if

(ū i ) i∈N ∈ G N X diagonalize Ā, (u i f j ) i,j≤N ∈ G N×N G N diagonalize A in G.
This justifies the consideration of fractional operators A p for p ∈ R + , such as in Assumptions 8 and 9. Based on those equivalence, we will forget the bar notations, we incite the careful and attentive reader to recover them.

C.2. Estimate g n as an empirical approximate projection on RKHS

To obtain bounds like Eq. ( 4), it is sufficient to control the convergence of g n to g * in L ∞ . Assumption 8 allow us to cast in L 2 the study of the convergence in L ∞ . The convergence of g n towards g * can be split in two terms, a term expressing the convergence of g λ towards g * that is based on geometrical properties and a term expressing the convergence of g n towards g λ , that is based on concentration inequalities in G, such as the ones given by [START_REF] Pinelis | Remarks on inequalities for large deviation probabilities[END_REF]; [START_REF] Minsker | On some extensions of Bernstein's inequality for self-adjoint operators[END_REF]. For this last term, we need to characterize g n and g λ with the following lemma.

Lemma 22 (Approximation of integral operators) g n can be understood as the empirical approximation of g λ since

g n = S(E ρ[k X k ⋆ X ] + λ) -1 E ρ[k X ϕ(Y )], g λ = S(E ρ [k X k ⋆ X ] + λ) -1 E ρ [k X ϕ(Y )], with ρ = 1 n n i=1 δ X i ⊗ δ Y i ,
Proof Indeed, the expression of g n and its convergences towards g * will be understood thanks to the operator S and its derivatives. When im S is closed in L 2 , on can defined the orthogonal projection of g * to im S, with the L 2 metric as π im S (g * ) = S(S ⋆ S) † S ⋆ g * . When im S is not closed, or equivalently when Σ has positive eigen values converging to zero, one can define approximate orthogonal projection, through eigen value thresholding or Tikhonov regularization. This last choice leads to the estimate

g λ = S(Σ + λ) -1 S ⋆ g * = S(S ⋆ S + λ) -1 S ⋆ g * = SS ⋆ (SS ⋆ + λ) -1 g * = K(K + λ) -1 g * .
Note that, because of the Bayes optimum characterization of g * , S

⋆ g * = E ρ [k X ϕ(Y )]. This explains the characterization of g λ .
Interestingly, the approximation of ρ by ρ can be thought with the approximation of

L 2 (X , H, ρ X ) by ℓ 2 (H n ) ≃ L 2 (X , H, ρX ) where for Ξ = (ξ i ), Z = (ζ i ) ∈ H n , Ξ, Z ℓ 2 = 1 n n i=1 ξ i , ζ i H , C B R
and with the empirical probability measure ρ = 1

n n i=1 δ x i ⊗ δ y i . We redefine the natural homo- morphism of G into ℓ 2 with Ŝ : G → ℓ 2 γ → k ⋆ x i γ i≤n . We check that its adjoint is, for Ξ ∈ H n and γ ∈ G Ŝ⋆ Ξ, γ G = Ξ, Ŝγ ℓ 2 = 1 n n i=1 ξ i , k ⋆ x i γ H = 1 n n i=1 k x i ξ i , γ G .
Similarly we define K :

H n → H n and Σ : G → G, with KΞ = Ŝ Ŝ⋆ Ξ = 1 n n i=1 k(x j , x i )ξ i j≤n , Σ = 1 n n i=1 k x i ⊗ k x i = E ρX [k X k ⋆ X ].
Finally we define Φ = (ϕ(y) i ) i≤n ∈ H n , so that

S ⋆ g * := E ρ[ϕ(Y ) • k X ] = Ŝ⋆ Φ.
Finally we can express g n as

g n = S( Σ + λ) -1 Ŝ⋆ Φ = S( Ŝ⋆ Ŝ + λ) -1 Ŝ⋆ Φ = S Ŝ⋆ ( Ŝ Ŝ⋆ + λ) -1 Φ = S Ŝ⋆ ( K + λ) -1 Φ.
This explains the equivalence between g n defined at the beginning of Section 5 and the g n expressed in the lemma, that will be used for derivations of theorems.

C.3. Linear algebra and equivalent assumptions to Assumptions 7, 8

To proceed with the study of the convergence of g n towards g λ in L 2 , it is helpful to pass by G. To do so, we need to express Assumptions 7 and 8 in G, which we can do using the following linear algebra property.

Lemma 23 (Linear algebra on compact operators) There exist (u i ) i∈N an orthogonal basis of G X , (v i ) i∈N an orthogonal basis of L 2 (X , R, ρ X ), and (λ i ) i∈N a decreasing sequence of positive real number such that

S = i∈N λ 1/2 i u i v ⋆ i , S ⋆ = i∈N λ 1/2 i v i u ⋆ i , Σ = i∈N λ i u i u ⋆ i , K = i∈N λ i v i v ⋆ i , ( 14
)
where the convergence of series as to be understood with the operator norms. Moreover, we have that, if the kernel k is bounded by κ 2 , i∈N λ i ≤ κ 2 < +∞.

Therefore, K and Σ are trace-class, and S and S ⋆ are Hilbert-Schmidt.

F R S P Proof First of all notice that Σ = E X [k X ⊗ k X ] and that k x ⊗ k x op(G X ) = k x G X = k(x, x) ≤ κ 2 .
Therefore Σ is a nuclear operator, so it is trace class and so it is compact. The first point results from diagonalization of kernel operator, known as Mercer's Theorem [START_REF] Mercer | Functions of positive and negative type and their connection with the theory of integral equations[END_REF][START_REF] Steinwart | Mercer's theorem on general domains: On the interaction between measures, kernels, and RKHSs[END_REF]. Σ is a compact operator, therefore, the Spectral Theorem gives the existence of a sequence (λ i ) ∈ R N and a orthonormal basis

(u i ) ∈ G N X of G X such that Σ = i∈N λ i u i u ⋆ i ,
where the convergence has to be understood with the operator norm. Because Σ is of the form S ⋆ S, one can consider (λ i ) a decreasing sequence of positive eigen value. Then, by defining, for all i ∈ N with λ i > 0,

v i = λ -1/2 i Su i
we check that (v i ) are orthonormal, and we complete them to form an orthonormal basis of (L 2 (X , R, ρ X )). Finally we check that

S = i∈N λ 1/2 i v i u ⋆ i ,
and that the other equalities hold too.

To check the second assertion, we use that k x k ⋆ x is rank one when operating on G X and therefore

Tr Σ = Tr (E X [k X k ⋆ X ]) = E X [Tr (k X k ⋆ X )] = E X k X k ⋆ X op(G X ) = E X k X G X = E X [k(x, x)] ≤ κ 2 .
This shows that S and S ⋆ are Hilbert-Schmidt operators and that K is also trace class.

This allow us to cast in G X the assumptions expressed in L 2 .

Lemma 24 (Equivalence of capacity condition) For σ ∈ (0, 1], it is equivalent to suppose that • Tr L 2 (X ,H,ρ X ) (K σ ) < +∞.

• Tr G X (Σ σ ) < +∞.

• i∈N λ σ i < +∞. In Assumption 7, the smaller σ, the faster the λ i decrease, the easier is will be to approximate Σ based on approximation of ρ. This appears explicitly in Theorem 31. Indeed, for σ = 0, the condition should be defined as Σ of finite rank. Note that when k is bounded, we know that Σ is trace class, and therefore, Assumption 7 holds with σ = 1.

Lemma 25 (Interpolation inequality in RKHS) Assumption 8 implies that

∀ γ ∈ G, Sγ L ∞ ≤ c p Σ 1 2 -p γ G . ( 15
)
Proof We begin by showing the property for γ ∈ G X . When γ = i∈N c i v i with i∈N c 2 i < +∞, denote g = i∈N λ 1 2 -p i c i u i , we have g ∈ L 2 , therefore, using Assumption 8,

Sγ L ∞ = K p g L ∞ ≤ c p g L 2 = c p Σ 1 2 -p γ G X . C B R
This ends the proof for G X . Note also that when the result of the Lemma holds, then Assumption 8 holds for any g ∈ im L 2 (X ,R,ρ X ) K 1 2 -p . Let switch to G now. Let γ ∈ G, and denote g = Sγ. Suppose that g achieve it maximum in x ∞ , define the direction ξ = g(x∞) / g(x∞) H , and define g ξ : x → g(x), ξ H ∈ L 2 (X , R, ρ X ), and

γ ξ = j∈N g ξ , v i L 2 u i ∈ G X . We have Sγ L ∞ = Sγ ξ L ∞ ≤ c p Σ 1 2 -p γ ξ G X ≤ c p Σ 1 2 -p γ G .
When g does not achieve its maximum, one can do a similar reasoning by considering a basis (f i ) i∈N of H and decomposition γ on the basis (u i f j ) i,j∈N , before summing the directions.

In Assumption 8, the bigger 1 /2p the more we are able to control our problem in G, the better. Note that this reformulation of the interpolation inequality allow to generalized it for p smaller than zero. Note that when k is bounded,

(Sγ)(x) H = k ⋆ X γ H ≤ k X op γ G = k(x, x) γ G , hence Assumption 8 holds with p = 1 /2.

C.4. Linear algebra with atoms k x and useful inequalities

From the study of the convergence of g n to g λ will emerge two quantities linked to eigen values of Σ and the position of k x regarding eigen spaces, that are

N (λ) = Tr (Σ + λ) -1 Σ , N ∞ (λ) = sup x∈supp ρ X (Σ + λ) -1 2 k x op . (16)
While those quantity could be bounded with brute force consideration, Assumptions 7 and 8 will help to control them more subtly.

Proposition 26 (Characterization of capacity condition) The property i∈N λ σ i < +∞, can be rephrased in term of eigen values of Σ as the existence of a a 1 > 0 such that, for all i > 0,

λ i ≤ a 1 (i + 1) -1 σ . ( 17
)
Proof Denote by u i and S n the respective quantities λ σ i and n i=1 u i . Because S n converge, it is a Cauchy sequence, so there exits N such that for any p > q > N , S p -S q = p i=q+1 u i ≤ 1. In particular, considering p = 2q, and because (λ i ) is decreasing, we have qu 2q ≤ 2q i=q+1 u i ≤ 1. Therefore, we have that for all i > 2N , u i ≤ 3(i + 1) -1 , considering (a 1 ) σ = 3 + max i≤2N {(i + 1)u i }, we get the desired result.

Proposition 27 (Characterization of

N ) When Tr (K σ ) < +∞, with a 2 = ∞ 0 a 1 a 1 +t 1 σ dt, ∀ λ > 0, N (λ, r) ≤ a 2 λ -σ . ( 18
)
Proof Expressed with eigenvalues, we have

N (λ) = Tr (Σ + λ) -1 Σ = i∈N λ i λ i + λ . F R S P
Using that λ i ≤ a 1 (i + 1) -1 σ , that x → x x+a is increasing with respect to x for any a > 0 and the series-integral comparison, we get for σ ∈ (0, 1]

N (λ) ≤ i∈N a 1 (i + 1) -1 σ a 1 (i + 1) -σ + λ ≤ ∞ 0 a 1 t -1 σ a 1 t -1 σ + λ dt = ∞ 0 a 1 a 1 + λt 1 σ dt = λ -σ ∞ 0 a 1 a 1 + (λ σ t) 1 σ d(λ σ t) = a 2 λ -σ ,
where we check the convergence of the integral.

Indeed, Assumption 8 has a profound linear algebra meaning, it is a condition on ρ X -almost all the vector k x ∈ G X not to be excessively supported on the eigenvector corresponding to small eigenvalue of Σ.

Proposition 28 (Characterization of interpolation condition) The interpolation Assumption 8 implies that, for all

i ∈ N sup x∈ρ X k x , u i G X ≤ c p λ 1 2 -p i . ( 19
)
Proof Consider the decomposition of k x ∈ G X according to the eigen vectors of Σ, with a i (x) = k x , u i . The interpolation condition Assumption 8, expressed in G X with Lemma 25, leads to for any γ X ∈ G X , and Sγ X : X → R,

|(Sγ X )(x)| = k x , γ X G X ≤ Sγ X L ∞ ≤ c p Σ 1 2 -p γ X G X This implies that k x , γ X 2 G X = i∈N k x , u i γ X , u i 2 ≤ c 2 p Σ 1 2 -p γ X 2 G X = c 2 p i∈N λ 1-2p i γ X , u i 2 .
Taking γ X = u i , we get that

| k x , u i | ≤ c p λ 1 2 -p i .
This result relates the interpolation condition to the fact that k x is not excessively supported on the eigenvectors corresponding to vanishing eigenvalues of Σ.

Proposition 29 (Characterization of N ∞ (λ, r)) Under the interpolation condition, Assumption 8, we have with

a 3 = c p (2p) -p (1 -2p) 1 2 -p , or a 3 = c p when p = 1 /2, N ∞ (λ) ≤ a 3 λ -p . ( 20
)
Proof First of all, notice that

(Σ + λ) -1 2 k x G X = sup γ X X =1 γ X , (Σ + λ) -1 2 k x G X = sup c; i∈N c 2 i =1 i∈N c i k x , u i (λ + λ i ) 1 2 ≤ c p sup c; i∈Nc 2 i =1 i∈N c i λ 1 2 -p i (λ + λ i ) 1 2 ≤ sup t∈R + c p t 1 2 -p (λ + t) 1 2 . C B R
When p ∈ (0, 1 /2), this last function is zero in zero and in infinity, therefore its maximum t 0 verifies, taking the derivative of its logarithm,

1 /2 -p t 0 = 1 2(t 0 + λ) ⇒ t 0 = (1 -2p)λ 2p ⇒ sup t∈R + t 1 2 -p (λ + t) 1 2 = (2p) -p (1 -2p) 1 2 -p λ -p .
The cases p ∈ {0, 1} are easy to treat.

In the previous analysis, one fact does not appear, it is that Σ and k x are linked to one another, since

Σ = E X [k X k ⋆ X ].
The following remark builds on it to relates N and N ∞ .

Remark 30 (Relation between interpolation and capacity condition)

The capacity and interpolation condition are related by the fact that it unreasonable not to consider that p ≤ σ /2.

Proof Because k x k ⋆ x is of rank one in G X , we have N (λ) = Tr (Σ + λ) -1 Σ = E X Tr (Σ + λ) -1 k X k ⋆ X = E X Tr k ⋆ X (Σ + λ) -1 k X = E X k ⋆ X (Σ + λ) -1 k X op = E X (Σ + λ) -1 2 k X 2 G X . So indeed, N (λ) is the expectation of the square (Σ + λ) -1 2 k X G X , when N ∞ (λ) is the supremum of this last quantity. Therefore N (λ) ≤ N ∞ (λ) 2
Supposing that the dependency in λ proved above are tight, we should have σ ≥ 2p, which is the statement of this remark. We refer the reader to Lemma 6.2. of [START_REF] Fischer | Sobolev norm learning rates for regularized least-squares algorithms[END_REF] for more consideration to relates σ and p (reading p and α /2 with their notations)

C.5. Geometrical control of the residual g

λ -g * L ∞
The proof of the first assertion in Lemma 13 follows from, using Assumption 9, with g 0 ∈ K -q g * ,

g λ -g * = (K(K + λ) -1 -I)g * = -λ(K + λ) -1 g * = -λ(K + λ) -1 K q g 0 = -λK p (K + λ) -1 K q-p g 0 .
Then using Assumption 8,

g * -g λ ∞ ≤ c p λ K q-p (K + λ) -1 op g 0 L 2 ≤ c p λ K(K + λ) -1 q-p op (K + λ) -1 1+p-q op g 0 L 2 ≤ c p λ1 q-p λ -(1+p-q) g 0 L 2 = b 1 λ q-p ,
where we have used that

K(K + λ) -1 op = K op/( K op + λ) ≤ 1 and that (K + λ) -1 ≤ λ -1 . F R S P
C.6. Convergence of g ng λ through concentration inequality

For the proof of the second assertion in Lemma 13, we will put ourselves in G. For this, we define in G

γ = E ρ [k X ϕ(Y )], γ λ = (Σ + λ) -1 γ, γ = E ρ[k X ϕ(Y )], (21)
so that g λ = Sγ λ , and g n = S( Σ + λ) -1 γ.

C.6.1. D

We begin by expressing g ng λ in G with

g n -g λ = S ( Σ + λ) -1 γ -(Σ + λ) -1 γ = S ( Σ + λ) -1 (γ -γ) + (( Σ + λ) -1 -(Σ + λ) -1 )γ) = S ( Σ + λ) -1 (γ -γ) + ( Σ + λ) -1 (Σ -Σ)(Σ + λ) -1 γ) = S ( Σ + λ) -1 ((γ -Σγ λ ) -(γ -Σγ λ )) ,
where we have used that A -1 -B -1 = A -1 (B -A)B -1 . Therefore, using the expression, Lemma 25, of Assumption 8 in G, we get

g n -g λ L ∞ ≤ c p Σ 1 2 -p ( Σ + λ) -1 (Σ + λ) 1 2 +p op × • • • (Σ + λ) -( 1 2 +p) ((γ -Σγ λ ) -(γ -Σγ λ )) G .
On the one hand, we have concentration of matrix term towards Σ I. On the other hand, we have concentration of the vector γ -Σγ λ towards γ -Σγ λ . Indeed the concentration of the matrix term is hard to prove (it is only a conjecture), therefore we will go for an other decomposition, that will result in similar rates when p ≥ 0, that is

g n -g λ L ∞ ≤ c p Σ 1 2 -p (Σ + λ) -1 2 op A(λ)B(λ) A(λ) = (Σ + λ) 1 2 ( Σ + λ) -1 (Σ + λ) 1 2 op , B(λ) = (Σ + λ) -1 2 ((γ -Σγ λ ) -(γ -Σγ λ )) G . (22)
Recall the definition of the following important quantity that are going to pop up from the analysis

N (λ) = Tr (Σ + λ) -1 Σ , N ∞ (λ) = sup x∈supp ρ X (Σ + λ) -1 2 k x op . (16)

C.6.2. E

We control the extra matrix term with

Σ 1 2 -p (Σ + λ) -1 2 op = Σ 1 2 -p (Σ + λ) -( 1 2 -p) op (Σ + λ) -p op ≤ λ -p . Using that (Σ + λ) -1 op ≤ λ -1 and that (Σ + λ) -1 Σ op ≤ Σ op/( Σ op + λ) ≤ 1. C B R C.6.3. M
Let us make explicit the concentration in the matrix term with

(Σ + λ) 1 2 ( Σ + λ) -1 (Σ + λ) 1 2 = I + (Σ + λ) 1 2 ( Σ + λ) -1 -(Σ + λ) -1 (Σ + λ) 1 2 = I + (Σ + λ) 1 2 ( Σ + λ) -1 Σ -Σ (Σ + λ) -1 (Σ + λ) 1 2 .
From here, notice the following implications (that are actually equivalence)

Σ -Σ t(Σ + λ) ⇒ Σ + λ (1 -t)(Σ + λ) ⇒ ( Σ + λ) -1 (1 -t) -1 (Σ + λ) -1 . ⇒ ( Σ + λ) -1 -(Σ + λ) -1 t(1 -t) -1 (Σ + λ) -1 . ⇒ (Σ + λ) 1 2 ( Σ + λ) -1 -(Σ + λ) -1 (Σ + λ) 1 2 t(1 -t) -1 ⇒ (Σ + λ) 1 2 ( Σ + λ) -1 (Σ + λ) 1 2 (1 -t) -1 .
The probability of the event Σ -Σ t(Σ + λ), can be studied through the probability of the event

(Σ + λ) -1 2 (Σ -Σ)(Σ + λ) -1 2
t, which can be studied through concentration of self adjoint operators. Finally, we have shown that

(Σ + λ) -1 2 (Σ -Σ)(Σ + λ) -1 2 op ≤ t ⇒ A(λ) ≤ 1 1 -t . (23)
The best result that we are aware of, for covariance matrix inequality, is the extension to self-adjoint Hilbert-Schmidt operators provided by [START_REF] Minsker | On some extensions of Bernstein's inequality for self-adjoint operators[END_REF] in Section 3.2 of its concentration inequality on random matrices Theorem 3.1. It can be formulated as the following.

Theorem 31 (Concentration of self-adjoint operators (Minsker, 2017)) Let denote by (ξ i ) i≤n a sequence of independent self-adjoint operator acting on an separable Hilbert space A, such that ker(E[ξ i ]) = A, that are bounded by a constant M ∈ R, in the sense ξ i op ≤ M , with finite variance σ 2 = E n i=1 ξ 2 i op . For any t > 0 such that 6t 2 ≥ (σ 2 + M t /3),

P   n i=1 ξ i op > t   ≤ 14 r n i=1 E ξ 2 i exp - t 2 2σ 2 + 2tM/3 , with r(ξ) = Tr ξ / ξ op .
Let us define ξ that goes from X to the space of self-adjoint operator action on G X as

ξ(x) = (Σ + λ) -1 2 k x k ⋆ x (Σ + λ) -1 2 . ( 24
)
We have that

(Σ + λ) -1 2 (Σ -Σ)(Σ + λ) -1 2 = E ρ [ξ(X)] -1 n n i=1 ξ(x i ).
To apply operator concentration, we need to bound ξ and its variance. Bound on ξ. To bound ξ we proceed with, because k

x k ⋆ x is of rank one, ξ(x) op = (Σ + λ) -1 2 k x k ⋆ x (Σ + λ) -1 2 op = Tr (Σ + λ) -1 2 k x k ⋆ x (Σ + λ) -1 2 = Tr k ⋆ x (Σ + λ) -1 k x = (Σ + λ) -1 2 k x 2 G X ≤ N ∞ (λ) 2 .
Variance of ξ. For the variance of ξ we proceed by noticing that

E ξ(X) = E X (Σ + λ) -1 2 k X k ⋆ X (Σ + λ) -1 2 = (Σ + λ) -1 2 E X [k X k ⋆ X ] (Σ + λ) -1 2 = (Σ + λ) -1 2 Σ(Σ + λ) -1 2 = (Σ + λ) -1 Σ. Hence E ξ(X) 2 sup x∈X ξ(x) op E[ξ(X)] N ∞ (λ) 2 (Σ + λ) -1 Σ.
And as a consequence

E ξ(x) 2 ≤ N ∞ (λ) 2 ,
where we have used that

(Σ + λ) -1 Σ op = Σ op/( Σ op + λ) ≤ 1.
Concentration bound on ξ. Using the self-adjoint concentration theorem, we get for any t > 0, such that 6nt 2 ≥ N ∞ (λ) 2 (1 + t /3),

P Dn E ρ[ξ] -E ρ [ξ] op > t ≤ 14 Σ op + λ Σ op N (λ) exp - nt 2 2N ∞ (λ) 2 (1 + t/3) .
Therefore, using the contraposition of the prior implication, we get

P Dn A(λ) > 1 1 -t ≤ 14 Σ op + λ Σ op N (λ) exp - nt 2 2N ∞ (λ) 2 (1 + t/3) . (25)
C.6.4. D Let switch to the vector term, consider ξ : X × Y → G, defined as

ξ = (Σ + λ) -1 2 k x (ϕ(y) -k ⋆ x γ λ ).
It allows to express in simple form the vector term as

B(λ) = 1 n n i=1 ξ(X i , Y i ) -E (X,Y )∼ρ [ξ(X, Y )] .
We can study this term through concentration inequality in G. To proceed we will dissociate the variability due to Y to the one due to X, recalling that g λ (x) = k ⋆ x γ λ and going for the following decomposition

B v (λ) = E ρ[ξ v (X, Y )] -E ρ [ξ v (X, Y )] B b (λ) = E ρ[ξ b (X, Y )] -E ρ [ξ b (X, Y )] . (27)
The first term is due to the error because of having observed ϕ(y) rather than g * (x), often called "variance", and the second term is due to the aiming for g λ instead of g * often called "bias".

C.6.5. C

To control the variance term, we will use the Bernstein inequality stated Theorem 21.

Bound on the moment of ξ v . First of all notice that ξ v (x, y) G ≤ (Σ + λ) -1 2 k x op ϕ(y)g * (x) H .

Therefore, under Assumption 5, for m ≥ 2:

E (X,Y )∼ρ [ ξ v (X, Y ) m ] ≤ E X∼ρ X (Σ + λ) -1 2 k x m op E Y ∼ρ| X [ ϕ(y) -g * (x) m H ] ≤ 1 2 m!σ 2 M m-2 E X∼ρ X (Σ + λ) -1 2 k x m op .
We bound the last term with

E X∼ρ X (Σ + λ) -1 2 k x m op ≤ sup x∈supp ρ X (Σ + λ) -1 2 k x m-2 op E X∼ρ X (Σ + λ) -1 2 k x 2 op = N ∞ (λ) (m-2) N (λ).
Concentration on ξ v . Applying Theorem 21, we get, for any t > 0, that Bound on ξ b . We have

P (B v (λ) > t) ≤ 2 exp - nt 2 2σ 2 N (λ) + 2M N ∞ (λ)t . ( 28
ξ b (x) G ≤ sup x∈supp ρ X (Σ + λ) -1 2 k x op g λ (x) -g * (x) H ≤ N ∞ (λ) g λ -g * ∞ .
Therefore, with Appendix C.5, we get

ξ b (x) G ≤ b 1 λ q-p N ∞ (λ).
Variance of ξ b . For the variance we proceed with

ξ b (x) 2 G ≤ N ∞ (λ) 2 g λ (x) -g * (x) 2 H . Therefore E[ ξ b (X) 2 ] ≤ N ∞ (λ) 2 g λ -g * 2 L 2 .
Using the derivations made in Appendix C.5, we have, using that q ≤ 1, g λg * L 2 = λ (K + λ) -1 K q g 0 L 2 ≤ λ (K + λ) -(1-q) op (K + λ) -q K q op g 0 L 2 ≤ λ q g 0 L 2 .

Concentration on ξ b . Adding everything together, we get

P (B b (λ) > t) ≤ 2 exp   - nt 2 2 λ 2q N ∞ (λ) 2 g 0 2 L 2 + b 1 λ q-p N ∞ (λ)t/3   . ( 29
)
Note that based on the bound on the variance, we would like N ∞ (λ) 2 λ 2q ≈ λ 2(q-p) to be smaller than N (λ) ≈ λ -σ . It is the case since q > p.

C.6.7. U

To control g ng λ L ∞ ≤ c p λ -p A(λ)(B v (λ) + B b (λ)), we need to perform a union bound on the control of A and the control of B := B v + B b , we use that for any t > 0 and 0 < s < 1, c p λ -p AB > t implies A > 1 /(1 -s) or B > (1 -s)tλ p /cp. Similarly B v + B b > t, implies that either B v > t /2, either B b > t /2. Therefore, we have, the following inclusion of events (with respect to D n )

{ g n -g λ L ∞ > t} ⊂ A > 1 1 -s ∪ B v > (1 -s)tλ p 2c p ∪ B b > (1 -s)tλ p 2c p .
In term of probability this leads to

P Dn ( g n -g λ L ∞ > t) ≤ P Dn A > 1 1 -s + P Dn B > (1 -s)tλ p c p . ( 30
)
Looking closer it is the term in B that will be the more problematic, therefore we would like s to be small. It we take s to be a constant with respect to t, we will get something that behaves like P(B > tλ p ), which is the best we can hope for (this also explain why we divide

B > t in B v > t /2 C B R
or B b > t /2). We will consider s = 1 /2. We express concentration based on the expression of N and N ∞ , assuming λ ≤ Σ op , and n > a 2 3 λ -2p P Dn (A > 2) ≤ 28a 2 λ -σ exp(-nλ 2p 10a 2

3

).

Similarly we get, when λ ≤ 1, using that λ -σ ≥ 1 P Dn (B v > t /4) ≤ 2 exp -nλ σ t 2 32σ 2 a 2 + 8M a 3 λ -p t .

For the bias term, we can proceed at a brutal bounding, based on the fact that for λ ≤ 1, λ q-p ≤ 1 ≤ λ -σ , to get P Dn (B b > t /4) ≤ 2 exp -nλ σ t 2 32a 2 3 g 0 L 2 + 8b 1 a 3 λ -p t/3

.

With b 4 = max(32σ 2 a 2 , 32a 2 3 g 0 L 2 ) and b 5 = max(8M a 3 , 8b 1 a 3 /3), we get the following union bound

P Dn B > tλ p 2 ≤ 4 exp - nλ 2p+σ t 2 b 4 + b 5 t .
We proceed with the union bound on g ng λ L ∞ as C.6.8. R L 13

P
Remark that the uniform control in Lemma 13 is more than we need, we only need control for each x as described in Assumption 2. Indeed, if p(x) is such that there exists a constant cp (that does not depend on x or λ), such that for any i ∈ N

k x , u i G X ≤ cp λ p(x) i
, then considering that

g n (x) -g λ (x) = k ⋆ x (γ n -γ λ ) = k ⋆ x (Σ + λ) -1 2 (Σ + λ) 1 2 (γ n -γ λ ) ,
we can get improve the results of Lemma 13 by replacing p by p(x). While we considered p = sup x∈ρ X p(x) as a consequence of our proof scheme, one can expect to end up with the E X [λ p(X) ] instead of λ p when deriving the proof of Theorems 14 and 15 (for which one has to refine Theorem Theorem 6 in order to integrate dependency of L to x, similarly to what is done in Lemma 18), which will lead to better rates. Yet, because of complexity of expressing a quantity of the type E X [ϕ(p(X))], for some function ϕ, we decided not to present this improved version in the paper.

C.7. Proof of Theorem 14

Based on on the proof of Theorem 5, we know that

E Dn R(f n ) -R(f * ) ≤ ℓ ∞ P Dn ( g n -g * ∞ > t 0 ) .
Now we use that P Dn ( g ng * ∞ > t 0 ) ≤ P Dn ( g ng λ ∞ > t 0g λg * ∞ ) .

The result follows from derivations in Appendix C.6, where we used that when k is bounded, Assumptions 7 and 8 are verified with σ = 1 and p = 1 /2. Note that we do not need the source assumption, since we can bound directly g λg * L 2 ≤ g λg * L ∞ < t 0 while retaking the proof in Appendix C.6. Moreover, the results of this last proof holds under the condition nλb 3 > 1, but, since E Dn R(f n ) -R(f * ) ≤ ℓ ∞ , we can augment the constant b 6 so that the result in Theorem 14 still holds for any n ∈ N * .

C.8. Proof of Theorem 15

We can rephrase Lemma 13, using a union bound P Dn ( g ng * > t) ≤ P Dn ( g ng λ > t /2) + P Dn ( g λg * > t /2) ≤ b 2 λ -σ exp -b 3 nλ 2p + 4 exp -nλ 2p+σ t 2 4b 4 + 2b 5 t + 1 t≤2λ q-p . As long as λ ≤ max( K op , 1) and n ≥ (b 3 λ 2p ) -1 . We optimize those rates with λ = λ 0 n -γ , and γ satisfying 2γ(qp) = 1γ(2p + σ) ⇒ γ = (2q + σ) -1 .

Using variant of

This leads to, for n after a certain

N ∈ N * R(f n ) -R(f * ) ≤ ℓ ∞ b 2 λ -σ 0 n σ 2q+σ exp -b 3 nλ 2p 0 n
2(q-p)+σ 2q+σ

+ 2c ψ c α 2 α+1 λ (q-p)(α+1) 0 n -2(q-p)(α+1) 2q+σ ≤ b 8 n -2(q-p)(α+1) 2q+σ .

Since ℓ is bounded, R(f n ) -R(f * ) ≤ ℓ ∞ , and we can always higher b 8 , in order to have the inequality for any n ∈ N * .

Figure 1 :

 1 Figure 1: Illustration of Lemma 2. Simplex ∆ Y , for Y = Z = {a, b, c} and ℓ a symmetric loss defined as ℓ(a, b) = ℓ(a, c) = 1 and ℓ(b, c) = 2, while ℓ(z, z) = 0. This leads to the decision regions R z represented in colors. Given x ∈ X , if g * (x) corresponds to a distribution µ * := ρ| x falling in R a , and if g n (x) represented by μ falls closer to µ * than the distance between µ * and the decision frontier F (represented by a circle on the right figure), then μ is also in R a , and therefore f * (x) = f n (x) = a.

Figure 2 :

 2 Figure 2: Illustration of Remark 4. We represent two instances of binary classification (see Examples 1and 2). On the left example, when ρ X is such that there is no mass where the sign of g * changes, classes are separated in X , yet the no-density separation is not verified. On the right, classes are not separated in X , but the problem satisfies the no-density separation as there is no x such that d(g * (x), F ) = |g * (x)| < t 0 . Note that when ρ X is uniform, the left problem satisfies a milder separation condition, introduced thereafter and called the 1-low-density separation.

Figure 3 :

 3 Figure 3: Empirical convergence rates. We consider binary classification, with X = [-1, 1], g * (x) = sign(x) * |x|

Figure 4 :

 4 Figure 4: Supplement to Figure3. We precise the error is evaluated on 100 points forming a regular partition of X = [-1, 1], and the expectation E Dn is approximated by considering 100 datasets. The violet curve is cropped at n ≈ 10 5 , because the error was null afterwards with our evaluation parameters (only 100 points to evaluate the error), forbidding us to consider the logarithm of the excess of risk.

  ξ(x, y) = ξ v (x, y) + ξ b (x) ξ v (x, y) = (Σ + λ) -1 2 k x (ϕ(y)g * (x)), ξ b (x) = (Σ + λ) -1 2 k x (g * (x)g λ (x)), ≤ B v (λ) + B b (λ)

  Dn ( g ng λ L ∞ > t) ≤ b 2 λ -σ exp(-b 3 nλ 2p ) + 4 exp -nλ 2p+σ t 2 b 4 + b 5 t ,with b 2 = 28a 2 and b -1 3 = 10a 2 3 , as long as b 3 n > λ -2p , and λ ≤ max(1, K op ).

  Theorem 6 presented in Appendix A.6, we getR(f n ) -R(f * ) ≤ ℓ ∞ b 2 λ -σ exp -b 3 nλ 2p + 2c ψ c α 2 α+1 λ (q-p)(α+1)

Remark 7 (Independence to the decomposition of ℓ

  ) While we have stated results based on the quantity d(g * (x), F ), generalization of the Tsybakov margin condition has also been expressed through the quantity infz =z * E Y ∼ρ|x ℓ(z, Y )-E Y ∼ρ|x ℓ(z * , Y ) instead of d(g * (x), F ) (Nowak[START_REF] Nowak-Vila | Sharp analysis of learning with discrete losses[END_REF]. We show in Appendix A.3 that the two definitions of the margin condition are equivalent.

	F	R	S	P
	Remark 8 (Scope of our work) Our work relies on pointwise exponential concentration inequali-
	ties (Assumption 2) which are specially designed to work well with the Tsybakov margin condition.
	It is natural for localized averaging method such as nearest neighbors, or for surrogate methods
	leading to L ∞ concentration. For surrogate methods leading to concentration of other quantities,
	it is possible to use similar tricks under different "margin" conditions (e.g.

Concentration in Hilbert space (Pinelis and Sakhanenko, 1986))

  To control the bias, we recall a simpler version of Bernstein concentration inequality, that is a corollary of Theorem 21. Let denote by A a Hilbert space and by (ξ i ) a sequence of independent random vectors on A such that E[ξ i ] = 0, that are bounded by a constant M , with finite variance σ 2 = E[ n i=1 ξ i 2 ]. For any t > 0,

		F	R	S	P
						)
	C.6.6. C
	Theorem 32 (P(	n i=1	ξ i ≥ t) ≤ 2 exp -	t 2 2σ 2 + 2tM/3	.

Note that this topological assumption ease derivations but is not fundamental for such non-asymptotic results.

Acknowledgments

We would like to thanks Alex Nowak for useful discussions, as well as anonymous referees for helpful comments. 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 (grants SEQUOIA 724063 and REAL 947908).

Appendix C. Kernel proofs

In this section, we study L ∞ convergence rates of the kernel ridge regression estimate. We use the L 2 -proof scheme of [START_REF] Caponnetto | Optimal rates for the regularized least-squares algorithm[END_REF] with the remark of [START_REF] Ciliberto | A consistent regularization approach for structured prediction[END_REF] to factorize the action of K on L 2 (X , H, ρ X ) through its action on L 2 (X , R, ρ X ). We retake the work of [START_REF] Pillaud-Vivien | Statistical optimality of stochastic gradient descent on hard learning problems through multiple passes[END_REF] to relax the source condition, and use [START_REF] Fischer | Sobolev norm learning rates for regularized least-squares algorithms[END_REF] to cast in L ∞ thanks to interpolation inequality. While those results, leading to Lemma 13, are not new, we present them entirely to provide the reader with self-contained materials.

C.1. Construction of reproducing kernel Hilbert space (RKHS)

In the following, we suppose k bounded by κ 2 .

Vector-valued RKHS. To study the estimator g n , it is useful to introduce the reproducing kernel Hilbert space G associated with k and H [START_REF] Aronszajn | Theory of reproducing kernels[END_REF]. To define G, define the atoms k x : H → G and the scalar product, for x, x ′ ∈ X and ξ, ξ ′ ∈ H as

Where Γ is the vector valued kernel inherit from k as Γ(x, x ′ ) = k(x, x ′ )I H [START_REF] Schwartz | Sous-espaces Hilbertiens d'espaces vectoriels topologiques et noyaux associés (noyaux reproduisants)[END_REF]. G is defined as the closure, under the metric induced by this scalar product, of the span of the atoms k x ξ for x ∈ X and ξ ∈ H. Note that k x is linear, and continuous of norm k x op = k(x, x).

When k(•, x) is square integrable for all x ∈ supp ρ X , G is homomorphic to a functional space in L 2 (X , H, ρ X ) through the linear mapping S that associates the atom k x ξ in G to the function