Regularized least squares learning with heavy-tailed noise is minimax optimal
Authors: Mattes Mollenhauer
Nicole Mücke
Dimitri Meunier
Arthur Gretton
Venue: NeurIPS 2025 spotlight ()
Keywords: kernel methods
nonparametric regression
kernel ridge regression
Primary area: theory

Abstract: This paper examines the performance of ridge regression in reproducing kernel Hilbert spaces 
in the presence of noise that exhibits a finite number of higher moments. We establish excess
risk bounds consisting of subgaussian and polynomial terms based on the well known integral
operator framework. The dominant subgaussian component allows to achieve convergence rates
that have previously only been derived under subexponential noise—a prevalent assumption in
related work from the last two decades. These rates are optimal under standard eigenvalue decay
conditions, demonstrating the asymptotic robustness of regularized least squares against heavy-
tailed noise. Our derivations are based on a Fuk–Nagaev inequality for Hilbert-space valued
random variables.

Regularized least squares learning with heavy-tailed noise is minimax optimal
Mattes Mollenhauer
Merantix Momentum
mattes www.mmmme..auueemmeraaaat/.aaa.. www.ttiiimmmmmmmmmmmmmmmmm com
Nicole Mücke Technische Universität Braunschweig nicole. muecke@tu seatieettu--baasschheeee de
Dimitri Meunier
Gatsby Computational Neuroscience Unit, UCL dimitri meunier. 21 21@ucl.ac ac. uk
Arthur Gretton Gatsby Computational Neuroscience Unit, UCL arthur metaurggretton@maal.ccom com
Abstract
This paper examines the performance of ridge regression in reproducing kernel Hilbert spaces in the presence of noise that exhibits finite number of higher moments. We establish excess risk bounds consisting of subgaussian and polyno- mial terms based the well known integral operator framework. The dominant subgaussian component allows to achieve convergence rates that have previously only been derived under subexponential noise-a prevalent assumption in related work from the last two decades. These rates are optimal under standard eigenvalue decay conditions, demonstrating the asymptotic robustness of regularized least squares against heavy-tailed noise. Our derivations are based on Fuk-Nagaev inequality for Hilbert-space valued random variables.
Introduction
Given two random variables X and Y, seek to empirically minimize the expected squared error R( = [ [(X))
over functions f in reproducing kernel Hilbert space H. consisting of functions from topological space X' to TR. We consider the standard model
Y = f.(X) +
with the regression function f. X + R and noise variable satisfying Eie|X] 0. Given
independent sample pairs (X,, Y.) drawn from the joint distribution of and Y, we investigate the classical ridge regression estimate
8. arg min JEH
Σ (Y: ((X.))
(I)
n
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

with regularization parameter a > 0. We adopt the well-known perspective going back to the pathbreaking work [1-4], which characterizes fa the solution of a linear inverse problem in H obtained by performing Tikhonov regularization [5] on a stochastic discretization of the integral operator induced by the kernel of H and the marginal distribution of X. Since its inception, this approach has been refined and generalized in a multitude of ways, including more general learning settings and alternative algorithms and applications. We refer the reader to [6-23] and the references therein for an overview. A common theme in the above line of work is the derivation of confidence bounds of the excess risk
R(fa) - R((.) = (X) - fx
i.e. with high probability over the draw of the sample pairs under appropriate regularity assumptions about the regression function fa and distributional assumptions about e.
Heavy-tailed noise. In this work, we assume that the real-valued random variable e has only a finite number of higher conditional absolute moments, i.e., there exists some q E N, q 2 3 such that
|||=||XX] < Q < oo almost surely.
(2)
This setting covers noise associated with distributions without a moment generating function-for example the t-distribution, Fréchet distribution, Pareto distribution and Burr distribution (correspond- ingly centered). In such a setting, the family of Fuk-Nagaev inequalities [24, 25] provides sharp nontrivial tail bounds beyond Markov's inequality for sums of heavy-tailed real random variables. These results show that the tail is dominated by a subgaussian term [26] in small deviation regime (reflecting the central limit theorem) and polynomial term in a large deviation regime. In order to ap- ply this fact the integral operator approach, we modify vector-valued version of the Fuk Fuk-Nagad -agaey inequality going back to [27] for random variables taking values in Hilbert spaces. In practical context, heavy-tailed noise satisfying the moment condition (2) plays a role in fields such as finance, insurance, communication networks and atmospherical sciences [28, 29].
Prior work: Bernstein condition. In the aforementioned context of spectral regularization algo- rithms in kernel learning, existing work generally assumes that is subexponential. In particular, the so-called Bernstein condition requires the existence of constants a, Q >> 0 almost surely satisfying
E| S 2 2 almost surely
(3)
for all q 2 2. This condition allows to apply a Hilbert space Bernstein inequality [31] to the well- known integral operator framework in order obtain convergence results. We refer the reader to [3, 6-11, 13] for a selection of results in this setting. To our knowledge, all results obtaining optimal rates in this setting rely on the Bernstein tail bound. The importance of the Bernstein inequality in the context of this work is emphasized by the effective dimension [3, 32], which measures the capacity of the hypothesis space 'H relative the choice of the regularization parameter a and the marginal distribution of X in terms of the eigenvalues of the integral operator. When used as a variance proxy in the Bernstein inequality, the effective dimension is the central tool that allows to derive minimax optimal rates under assumptions about the eigenvalue decay, as first shown by [3] and subsequently refined in the aforementioned work. Due this elegant connection between eigenvalue decay and concentration, the integral operator formalism has been predominantly focused around the assumption (3) over the last two decades. Similar approaches based on the Bernstein inequality with suitable variance proxies are commonly applied across a variety of estimation techniques in order to obtain fast rates [e.g. 33, 34].
Overview of contributions. In this work, we show that the rates derived under the Bernstein condition (3) in the mentioned literature can equivalently be obtained with the significantly less restrictive higher moment assumption (2) with the same regularization parameter schedules. We consider both the capacity independent setting (i.e., without assumptions about the eigenvalue decay of the integral operator [4, 6)) and the more common capacity dependent setting involving
'The term subexponential in this work refers to light-tailed distributions in the Orlicz sense [26] in contrast to alternative definitions for heavy-tailed distributions found in the literature [28].
*Condition (3) is in fact related to the slightly stronger subganma property. see [30]. Applying Stirling's 's approximation to the right hand side of (3) gives the typical subexponential bound for L norms of see [26].

---

the effective dimension [e.g. 3, 11, 35]. Even though the capacity dependent results are sharper, we dedicate separate discussion to the capacity independent setting, as it allows a less technical presentation and a simplified and insightful asymptotic dicussion. In both settings, we base our analysis on a Hillert space version of the Fuk-Nagaev inequality, providing excess risk bounds that exhibit both subgaussian and polynomial tail components. The dominant subgaussian term allows to asymptotically recover the familiar bounds known from the subexponential noise scenario. In the capacity dependent setting, we use the effective dimension not only as variance proxy, but also as a proxy for the higher moments occurring in the Fuk-Nagaev inequality- resulting bound is sharp enough so that standard assumptions about the eigenvalue decay lead to known optimal convergence rates. This technique directly generalizes the aforementioned approach based on the Bernstein inequality.
Practical implications, future work and limitations. The square loss is often not used in practice when one expects heavy-tailed noise, as is sensitive to outliers when used without regularization [36]. However, when used with regularization in the presence of noise of the form (2), we show that it exhibits certain degree of robustness. In particular,
(i) it asymptotically achieves the optimal rates with high probability known from the light- tailed setting with the same regularization schedule,
(ii) in a large sample setting, the confidence behavior of the excess risk is essentially subexpo- nential,
(iii) in a small sample setting, the confidence behavior is polynomial and stronger regularization is required due to the impact of the heavy tails.
We focus on the original well-specified kernel ridge regression setting as investigated by [3] in order to simplify the presentation and highlight the key arguments. However, we expect our approach to transfer to other settings, for example involving more general source conditions [6, 37], general spectral filter methods [9, 20], misspecified models [11, 38], the kernel conditional mean embedding with unbounded kernels on the target space [17], high- and infinte-dimensionall output spaces [15. 16] and many other settings allowing for the application of the integral operator formalism. We believe that kernel regression with unbounded kernels admitting a finite higher moment can be analyzed with a similar technical approach as the one presented here. Let us mention some limitations of the present work. While our results show certain degree of robustness of regularized least squares against heavy-tailed noise for 2 3, q E N, we expect our results to directly transfer to all real q 2, versions of the real-valued Fuk-Nagaev bound cover this case [39, 40J. Currently, this restriction of our results exclusively depends on the validity of the Fuk-Nagaev bound in Hilbert spaces for these q an artefact of the proof technique by [27]. which we modify. Furthermore, for q < 2, it is clear that the square loss is not necessarily well-defined and a different loss such as the Cauchy loss should be used [41]. Our results demonstrate that, when operating in high confidence setting, heavy-tailed noise may require a significantly higher level of regularization than light-tailed noise, making empirical regularization parameter choice rules as a function of the confidence level very important. Extending the analysis of classical parameter choice rules for deterministic inverse problems [42] to the stochastic setting based on heavy-tailed noise may therefore be an interesting future direction.
Other related work. We are not aware of any specific analysis of kernel ridge regression and the integral operator formalism in the heavy-tailed scenario given by (2) in the literature. However, there exists wide variety of related results for regression with heavy-tailed noise and robust estimation- we put our results in the context of the most important related work. Optimal rates for (unpenalized) least squares regression over nonparametric hypothesis spaces can generally only be derived in the empirical process context when q in condition (2) is large enough with respect to suitable metric entropy requirements, see [43-46]. In comparison, our setting allows to recover optimal rates for the reproducing kernel Hilbert space scenario with a regularization schedule which is independent of q. For linear models over finite basis functions, [47] derives exponential concentration of the ridge estimator under finite variance on the noise for fixed a. We also highlight the field of robust estimation techniques outside of the standard least squares context, see e.g. [36, 47-51] and the references therein. While the analysis of robust finiteddimensional linear regression under heavy- tailed noise requires discussions of the distribution of the covariates and their covariance matrix (often under striance-kurtosi equivalence [52-54]), we impose the typical assumption that the kernel is
3

---

bounded, leading to subgaussian concentration of the embedded covariates in the potentially infinite- dimensional feature space. Recently, [41] derived nearly optimal rates for kernel ridge regression with Cauchy loss under (2) with q > O depending on the Hölder continuity parameter of the target function using more classical arguments. Finally, from more technical perspective, the approach by [55] shares similarities with the methods applied in our paper: The authors use real-valued Fuk-Nagaev inequality to bound the stopping time complexity of stochastic gradient descent for ordinary least squares regression. However, [55] provides results only for the finite-dimensional setting based martingale decomposition by assuming a lower bound on the minimal eigenvalue of the covariance matrix. In contrast, work targets the without such a lower bound and explicitly proves minimax optimality.
setting based on inverse problem theory
Structure of this paper. We introduce notation and basic preliminaries in Section 2. In Sec- tion 3, we provide the excess risk bound for the capacity independent setting and derive corresponding rates. Section 4 contains excess risk bound based on the effective dimension and recovers rates which are known to be minimax optimal also in the subexponential noise setting. Finally, in Section 5, results. Appendix A contains
we briefly discuss the Fuk-Nagaev inequality used to derive numerical experiment which confirms the behavior of the excess risk described by our theoretical results. We report all proofs for the results in the main text in Appendix B and provide additional technical results as individual appendices.
2 Preliminaries
We assume that the reader is familiar with the analysis of linear Hilbert space operators [56, 57] and the basic theory of reproducing kernel Hilbert spaces [34, 58). Let π denote the marginal distribution of X and (T) denote the space of real-valued Lebesgue square integrable functions with respect to æ. We write L(H,, HH) for the space of bounded linear operators between Hilbert spaces Hi and H2 with operator norm ||-I| and abbreviate L(Hi) = L(Hl, H1). We additionally consider the space of Hilbert-Schmidt operators S₂ (H1, H2) C L(H,, H22) and the space of trace class operators SiHH, H2) C (2 H2) with norms Illss, and [I,Iss.(H,, and the trace tr(-). The adjoint of A E L(H1, H2) written as A E C(2,, H1).
2.1 Reproducing kernel Hilbert space
We consider the reproducing kernel Hilbert space (RKHS) Ht consisting of functions from X' to IR induced by the symmetric positive semidefinite kernel k: X x X + R. with canonical feature map
<(x) :' + H. x + k(,,z),
i.e. we have the reproducing property f(x) = (f, ( for all x X' and f H.
Assumption 2.1 (Domain and kernel). We impose the following standard assumptions throughout this paper in order to avoid issues related to measurability and integrability [34, Section 4.3]:
ii) X is second-countable locally compact Hausdorff space, H. is separable (this satisfied if k is continuous, given that X' is separable),
(ii) k(,, X) is almost surely measurable in its first argument, (iii) & X) & ?:? almost surely for some finite constant τ.
All assumptions above hold for commonly used continuous radial kernels on Rd such as the Gaussian kernel and the Matern kernel. However, the boundedness assumption is violated for polynomial kernels unless X is bounded almost surely.
Integral and covariance operators. Under Assumption 2.1, may consider the typical linear operators associated with æ and k. We consider the embedding operator
I H + [m),m),
+ [f]

---

identifying f E H. with its equivalence class [f E (TT) The adjoint 1 (T) + H. is given by
=== (())f(z) e H, (E)
We obtain the self-adjoint integral operator T I= (m))) [2((T) induced by k and x as
T=J / (() (T))) f E (m).
The self-adjoint kernel covariance operator :=:=1144 H - H. is given by
C - f= ((x) @ ((x) dT(z).
Assumption 2. ((ii) ensures that we have ||=||= || < K. as well as -C x². Moreover, the operators T and T SelbeettSchhiit and both Tn and C are therefore self-adjoint positive semidefinite and trace class. By the polar decomposition of I and T there exist partial isometries U.H. (T)) and Ü (T) + H such that
I U( /C and I = U(T,T))) UT -
In particular, we have [[ff)<ll><>)) [14*fllePMm) ||e f| for all f H. We will also frequently use the fact that Assumption 2. (iii) implies supaex [f(x)] S k||f||H.
2.2 Ridge regression
We introduce the standard integral operator formalism for ridge regression in RKHSs, see e.g. [3]. We consider the standard (orthootooan decomposition of Y with respect to the closed subspace (P, C. L2P) of (X)-measurabbl functions given by
Y = fx() +
with the regression function fX) X E (PP)) and noise variable LP( satisfying
X] = Based on the representation (5), we have R(f) = |lf f.ll22()) + [|=|l2200 for all
L (T) and hence the excess risk satisfies R(f) R(f-) = |lf fel12207)
Regularized population solution. We define the regularized population solution
fa arg min B[YY - f(x)) + all JEH
arg min| I=f - f-ll2(()) + all FEH
with >> 0, which is alternatively expressed
fa = (C, + Ia E H
(6)
with the identity operator Idx on H.
Regularized empirical solution. We consider sample pairs (X1, Yi).... (Xn, L(X, Y) independently obtained from the joint distribution of and Y. We define the empirical versions of the operators above in terms of
i=f = ((X)f((X) E H. fEL((T)
as well
1 é : n Σ (Xx) ((x))
The empirical solution of the learning problem in H with regularization parameter > is given by the empirical analogue of (6), which we obtain in terms of
fa CC. ldxx) 'f H.
(7)
5

---

where the empirical right hand side î E H of the inverse problem is given by
a (X,) T:J. +
(X,)),
(8)
Here, we use the orthogonal decomposition Y, = (X,)) (x.)))+E + in the second equivalence. We note that f directly serves as an empirically evaluable unbiased estimate of f as f= itself cannot be empirically evaluated because f. is unknown. As usual, we interpret the above objects as random variables depending on the product measure 1pa through their definition based on the observation pairs (X,, Y.). In practice, the empirical solution fa can be evaluated in terms of the classical representer theorem, see e.g. [1, Proposition 8].
2.3
Distributional assumptions
We list the assumptions we impose upon the distributions of Y, X and 6. Assumption 2.2 (Moment condition). almost surely
We consider the model given by (5) and assume that we have
E|s] X] - 0, E |[s"|x] < o² and B|| < Q.
(MOM)
for some constants 0² > 0, Q > 0 and q N, 2 3.
We now introduce classical smoothness assumption in terms of a Hölder source condition [59]. Assumption 2.3 (Source condition). We define the set Si(,, R) == (T [I S R] c (x) and assume
f. E Svv, R)
(SRC)
for some smoothness parameter v 2 1/2 and R >> 0.
We give the definition of the source set S2(,, Rt) with respect to (m) and not with respect to H. which also commonly found in the literature. Furthermore, the source condition is sometimes described in terms of so-called interpolation spaces or Hilbert scales. Our definition can equivalently be expressed in terms of these concepts by appropriately reparametrizing v/ see e.g. [6. 11, 59] for more details.
Remark 2.4 (Well-specified case). In this work, we explicitly consider the condition v > 1/2, which implies the well-specified setting in which we have Q2v, R) C (?L). We note the case 0 < < 1/2 covers the misspecified setting, which Q(v, R) is allowed to contain elements from L² I (H). We expect our approach to transfer to the misspecified setting by combining it with recent technical arguments from the literature which are outside the scope of this work [11, 15, 16, 38, 60).
3 Capacity-free excess risk bound
We now provide an excess risk bound and corresponding rates for kernel ridge regression in the heavy-tailed noise setting without additional assumptions about the eigenvalue decay of Tr. We present this setting separately from the capacity- results in the next section, as allows for clearer comparison with bounds based on subexponential noise and simplified asymptotic discussion.
Proposition 3.1 (Main excess risk bound). Let (MOM) and (SRC) be satisfied. For all 8 (0,1) and n. E N such that
CR log(6/0) S avn,
CR == 2(1 + VR) max [1,
(9)
we have
Co Va
log(6/))
a 2min log (6/8) + n(6, n) )
IT - Salleass) S min
n
n
with confidence 1 8, with
1/4
log (og(6c1//)
n(6, n) max
8nu
where 0 < Co is given in (29) and 2 1 is the constant from Proposition 5.1 depending only q.

---

Just as in the light-tailed setting. Proposition 3.1 shows that the optimal excess risk is achieved by balancing the contributions of the approximation error (e.g. the model bias) and sample error (e.g. the model variance) by choosing suitable regularization parameter a depending Ro min(r,11 quantifies the approximation eπгог based on the smoothness of f. and exhibits the typical saturation effect of ridge regression: the fact that the convergence speed cannot be improved beyond a smoothness level y 1 [e.g. 61, 62]. The key difference to known results for subexponential noise in this setting [4, 6] is the Fuk-Nagae term 17 n) appearing in the sample error, which introduces an additional polynomial dependence on 8 and n. We now investigate the consequences of this term.
n and ô. 'The term
Confidence regimes. We split the confidence scale into two disjoint intervals depending on whether the subgaussian component or the polynomial component dominates the term s7(ó, n). For n E N, q 2 3 we define
1og(661/ /
Di(n,g) = 8 (0,1) n(o,n) = oo
Q2
8 (0, n>
8 o
log(6c1/00g
(10)
22
D2 g) = (0, (in,g)))
(11)
In what follows, will refer to D1 (n, 9) as the subgaussian confidence regime and (2 q) the polynomial confidence regime. The effective sample size ny ensuring subgaussian behavior 17 6) for all n 2 ng hence
Q2 22
10g =
8 4
log(661 /6) / -
(12)
30
25
effective sample sizeen 70
20
15
10
0.90
0.92
0.94
0.96
0.98
1.00
confirience
Figure 1: Illustration of the the effective sample size no ensuring subgaussian behavior of the term 766, n) defined in (12) for different choices of q. For simplicity, we set e₁ = a and Q = 10.
We illustrate the behavior of ni depending that the involved constant ej stems from the Fuk-Nagaev inequality given in Proposition 5.1 and generally depends on q). We choose c I for simplicity to provide basic intuition note that cj only affects no logarithmically. We refer the reader to [40] for detailed discussion based on the bound for real-valued random variables.
5 for different choices of g in Figure (we note
Subgaussian confidence regime and convergence rates. We now give an excess risk bound which similar to the setting with bounded subexponential noise: it exhibits a logarithmic dependence of the confidence parameter 8 and dependence of the sample size up to n -1/3 depending on the level of smoothness given by v [4, 6]. the asymptotic large sample context, this bound dominant and allows to recover convergence rates.
7

---

Corollary 3.2 (Subgaussian confidence regime), Let (MOM) and (SRC) be satisfied. Then there exist constants č O2 O such that with the regularization schedule
log (log(Ger/0) /6)
2mim
01 (1 82
n
have
(log(6e100)
| [an 1o f.llep(s)) s ERR
(13)
with confidence 6 for all å Di(n, q) and such that an (n, (),6)_ k².
The constants é and 02 in Corollary 3.2 only depend on R, a, c1, and can be made explicit, but we omit their closed form here for the sake of more accessible presentation. We refer the reader to the proof for more details.
Remark 3.3 (Convergence rates). We directly obtain convergence rates from the above consideration. For fixed confidence parameter ó E (0, 1), we see that for all n пo. where no is the effective sample size given in (12), we have 8 E (n, q). Furthermore, there exists some no E N such that a1 (n, 6) n² for all ñg. Combining these two insights, from Corollary 3.2, we obtain
minfu.11
(log(6c1/0)
- f f.lles()) | - S Z
with confidence 1 for all n max noo. We explicitly note that the convergence rates well as the regularization schedule 01 (n, 5) match exactly the known results for the capacity- -ndeeitddnneeeenentt setting that have been derived under the assumption of bounded subexponential noise [4, 6].
Polynomial confidence regime. By definition (10), the polynomial confidence regime E D2 (n, q) relevant in the nonasymptotic investigation whenever n < nin For completeness, address this setting in Appendix C and show that Proposition 3.1 can yield simplified risk bounds with suitable regularization schedules for based on ō and Depending on 6, these bounds may require stronger regularization a22n,, 6) than the subgaussian confidence setting, In fact, the resulting bound exhibits polynomial worst-case dependence on 8, which is compensated by better dependence on the sample size before transitioning to the behavior from the subgaussian confidence regime given by Corollary 3.2. This behavior can be observed in practice, which we confirm in a basic numerical experiment provided in Appendix A.
4 Capacity dependent bound and optimal rates
now improve the results from the previous section and give an excess risk bound that involves effective dimension, which has been established as central tool to quantify the algorithm-dependee capacity of the hypothesis space H. relative to the distribution æ and regularization parameter a in order to derive risk bounds in regularized kemel-based learning under the assumptions of an eigenvalue decay of C, [3, 10, 32].
Definition 4.1 (Effective dimension). For a O, we define
A((a) == tr (r(C, (C,, + a (dd)) < sc.
We now assume the standard polynomial eigenvalue decay of C, [3, 9, 11]. Assumption 4.2 (Eigenvalue decay). We assume that the nonincreasingly ordered sequence of nonzero eigenvalues (44)221 of Tú satisfies the decay
#4 S Di-1/2 iEN
(EVD)
for a constant and some p E (0, 1).
Under the additional assumption (EVD), sharpen Proposition 3.1.

---

Proposition 4.3 Suppose that (0, 1) and
excess risk bound). Ler (MOM), (SRC) and (EVD) be satisfied.
2k²
2V DR
log(2/6)
S 1.
(14)
Vnaal (1+(/2+)/22
na
Then there exists a constant e not depending on and such that with confidence 6, we have
I| (elleP(n) so (mmin(u.1) +
log(8/6) Van
[Naa)
VN(a) n6, (.).
12
where we set
1/9
9-2 (og(Sc1/1 /0)
n1 a)) max
ònv-1
(N((a)
The constant è is made explicit in the proof. The key idea builds upon the original work of [3]. In particular, we incorporate the effective dimension into the Fuk-Nagaev inequality as a proxy for the q-th absolute moment appearing in the term 17(6, at), thereby generalizing the idea to use the effective dimension as a variance proxy in the Bernstein incquality.
Corollary 4.4 (Convergence rates). Let (MOM), (SRC) and (EVD) be satisfied. Then for every E (0, 1), there exists some no E N such that with the regularization schedule
a(n,8) (log(8c1/0) n
2min(c.))-p
we have
log( [c|
11 [a - fAlLe S
(15)
with confidence 1 8 for all n 2 ng with constant independent of and 6.
Remark 4.5 (Optimality of rates). The rates provided by Corollary 4.4 match the rates from the literature derived for well-specified kernel ridge regression under the assumption of subexponential noise [3, 35J. In particular, these rates are known to be minimax optimal over the class of distributions satisfying (SRC), (EVD) and the Bernstein condition (3). Corollary 4.4 now proves that can significantly relax the assumption of subexponential noise (3), as rate optimality is already achieved under the condition (MOM), Furthermore, the regularization schedule (n1 6) the same as in the light-tailed setting-in in particular, it does not depend on g.
5 Fuk-Nagaev inequality in Hilbert spaces
We discuss the central ingredient for the derivation of the previous results in more detail for con- venience. We refer the reader to [24, 25] for the original work in the setting of real-valued random variables and [40] for discussion of the involved constants. We present sharpened version of result due to [27, Theorem 3.5.1]. which is formulated more generally in normed spaces, but exhibits an excess term that can be removed in the Hilbert space case. We provide the proof in Appendix D. We also note that the proof of the result in [27] is incomplete due to an inconsistent exponential moment bound. We address this issue by deriving an alternative bound.
Proposition 5.1 (Fuk-Nagace inequality; Hilbert space version). Let E,,,,... En be independent and identically distributed random variables taking values in a separable Hilbert space such that
[E|]] 0,
[[
< <²² and E[[E|11] <
for some constants 0² > 0. Q > 0 and E N. q 2 3. Write Sn := ==E=1 &v. Then there exist two constants C1 0 and 02 depending only such that for every 1> 0, we have
Q
12
P
Sn
>1
<
19n9-1 + exp
-022 o²
(16)
x
Remark 5.2. For simplicity, may assume that 1 I when apply Proposition 5.1.

---

Confidence regimes. Directly rearranging (16) from tail bound to a confidence interval bound requires solve transcendental equation which does not admit a simple closed form solution. However, we can still derive an upper bound on the confidence intervals that reflects the superposition of polynomial and sub-gaussian tail (16). By introducing
QQ
n 02
i 2 max
1919-1 exp -02
(17)
we have P(n P|n I 2 ô by (16). Rearranging (17), we have
2c Q
1/4
log(2c1/0)
and t 1
V
(18)
ôn
o
immediately leading to the following confidence bound. Corollary 5.3 (Confidence bound). Under the assumptions of Proposition for all E (0, 1), we have
1
( 8ng-11
(201
1/9
log (2c1/
Sn
I max
(19)
C2n
with probability at least
For every fixed 8 and n co, this shows the typical subgaussian behavior and a convergence rate of S, of the order n -1/2 with high probability. Interpreting the right hand side as function of ē for fixed sample size n however, the above bound characterizes confidence regime change at 8(n), which we define as the solution to the equation
201
1/4
log(2c1/5(n))
V
(20)
8(n) n2-1
C2fl
In fact, in the polynomial confidence regime 5 < 5(n),, the dependence of the upper bound given in Corollary 5.3 on is clearly worse than the subgaussian regime 8(n) which is characterized by a logarithmic dependence on 5. In contrast, the polynomial confidence regime allows for better sample dependence of n (q-1)/a.
Sharpness of the tail bound. Both the subgaussian term and the polynomial term in the right hand side of the bound given by Proposition 5.1 can generally not be improved without additional assumptions. We repeat similar argument the one given in [63, Proposition 9]. which is given in the context of linear processes. Let Ei...... En be independent real-valued random variables drawn from centered t-distribution with q degrees of freedom, i.c. B[{--9] < oo for all S q and let o² E[(") = q/(q - - 2). Then [25, Theorem 1.9] shows that we have
P[S,/n t] = P(Sn// > nt/oa ~ - o(n 6(n//t/o) + +n(11 F (ntio())/o)) as + 8O
for nt/o 2 n/2 where & is the standard normal cumulative distribution function and Fa is the cumulative distribution function of o o'.. We now note that we have the basic property Fg (nt//() = (ntt)) and we can show that the distribution & satisfies 1- F(nt) ~ C (nt)² as nt + c0. where Cg is a constant depending exclusively on In total, we obtain
C
F[Sa/n > 1- ~ 1- D(n
as
[9n8-1
for nl/a 2 n/2 showing that Proposition 5.1 asymptotically optimal.
Acknowledgements
Dimitri Meunier and Arthur Gretton are supported by the Gatsby Charitable Foundation. This work was partially funded by the German Federal Ministry of Research, Technology and Space as part of the 6G-CAMPUS project (grant no. 16KISK 194). The authors express their gratitude to Christian Fiedler for pointing out inconsistensies the proof of [27, Lemma 3.5.1] and for his contribution to the corresponding conrections in Appendix D and Appendix D.3.3.
10

---

References
[1] Felipe Cucker and Steve Smale. On the mathematical foundations of learning. Bulletin of the American Mathematical Society, 39:1-49, 2002.
[2] E. De Vito, L., Rosasco, A. Caponetto, U. De Giovannini, and F. Odone. Learning from examples as an inverse problem. Journal of Machine Learning Research, 6:883-904, 2005.
[3] A. Caponnetto and E. De Vito. Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematiccs, 733):311-366 2007.
[4] Steve Smale and Ding-Xuan Zhou. Learning theory estimates via integral operators and their approximations. Constructive Approximation, 26(2):153-17,, 2007.
[5] A. N. Tikhonov and V. Y. Arsenin. Solutions of III Posed Problems. W. H. Winston, 1977.
[6] Frank Bauer, Sergei Pereverzev, and Lorenzo Rosasco. On regularization algorithms in learning theory. Journal of Complexity,
2007.
[7] Y. Yao, L. Rosasco, and A. Caponnetto. On Early Stopping in Gradient Descent Learning. Constructive Approximation, 26:289-315 315, 2007.
[8] Lee H. Dicker, Dean P. Foster, and Daniel Hsu. Kernel ridge vs. principal component regression: Minimax bounds and the qualification of regularization operators. Electronic Journal of Statistics, 11(1):1022-1047 2017.
[9] Gilles Blanchard and Nicole Mücke. Optimal rates for regularization of statistical inverse learning problems. Foundations of Computational Mathematics, 18:971-1013, 2018.
[10] Junhong Lin, Alessandro Rudi, Lorenzo Rosasco, and Volkan Cevher. Optimal rates for spectral algorithms with least-squares regression over Hilbert spaces. Applied and Computational Harmonic Analysis, 48(3):868-88) 890, 2020.
[11] Simon Fischer and Ingo Steinwart. Sobolev norm learning rates for regularized least-squares algorithms. Journal Of Machine Learning Research, 21:205-1, 2020.
[12] Nicole Mücke and Gilles Blanchard. Parallelizing spectrally regularized kernel algorithms. The Journal of Machine Leurning Research, 1991)1006,,097, 2018.
[13] Zoltán Szabó, Bharath K. Sriperumbudur, Barnabás Póczos, and Arthur Gretton. Learning theory for distribution regression. Journal of Machine Learning Research, 17(152):1-40, 2016.
[14] Alessandro Rudi and Lorenzo Rosasco. Generalization properties of learning with random features. In Advances in Neural Information Processing Systems 30, pages 3215-3225. 2017.
[15] Dimitri Meunier, Zikai Shen, Mattes Mollenhauer, Arthur Gretton, and Zhu Li. Optimal rates for vector-valued spectral regularization learning algorithms. In Advances in Neural Information Processing Systems, volume 37, pages 82514-82551 2024.
[16] Zhu Li, Dimitri Meunier, Mattes Mollenhauer, and Arthur Gretton. Towards optimal Sobolev norm rates for the vector-valued regularized least-squares algorithm. Journal of Machine Learning Research, 25(181):1-51, 2024.
[17] Zhu Li, Dimitri Meunier, Mattes Mollenhauer, and Arthur Gretton. Optimal rates for regularized conditional mean embedding learning. In Advances in Neural Information Processing Systems, volume 35, pages 4433 4445, 2022.
[18] Shao-Bo Lin, Yunwen Lei, and Ding-Xuan Zhou. Boosted kernel ridge regression: Optimal learning rates and early stopping. Journal of Machine Learning Research, 20(46):1-36, 2019.
[19] Shao-Bo Lin and Ding-Xuan Zhou. Distributed kernel-based gradient descent algorithms. Constructive Approximation, 47(2):249-22) 276, 2018
[20] I.. Lo Gerfo, Rosasco, F. Odone, F. De Vito, and Verri. Spectral algorithms for supervised learning. Neural Computation, 10(7):1873-189) 2008.

---

[21] Mattes Mollenhauer, Nicole Mücke, and TJ Sullivan. Learning linear operators: Infinite- dimensional regression as well-behaved non-compact inverse problem. arXiv preprint arXiv:2211 1.08875 2022.
[22] Rahul Singh, Maneesh Sahani, and Arthur Gretton. Kernel instrumental variable regression. Advances in Neural Information Processing Systems, 32, 2019.
[23] Dimitri Meunier, Zhu Li, Tim Christensen, and Arthur Gretton. Nonparametric instrumental regression via kernel methods is minimax optimal. arXiv preprint arXiv:2411. 2024.
[24] D. H. Fuk. Some probabilistic inequalities for martingales. Siberian Mathematical Journal, 14: 131-137, 1973.
[25] S. V. Nagaev. Large Deviations of Sums of Independent Random Variables. The Annals of Probability, 7(5):745-789, 1979.
[26] Roman Vershynin. Hiigh-iiensional Probability; An Introduction with Applications in Data Science. Cambridge University Press, 2018.
[27] Vadim Yurinsky. Sums and Gaussian vectors, volume 1617 of Lecture Notes in Mathematics. Springer, 1995.
[28] Jayakrishnan Nair, Adam Wierman, and Bert Zwart. The fundamentals of heavy tails. Properties, emergence, and estimation, volume 53 of Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2022.
[29] Paul Embrechts, Claudia Klüppelberg, and Thomas Mikosch. Modelling extremal events for insurance and finance. Springer, 1997.
[30] Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration inequalities. A nonasymptotic theory of independence. Oxford University Press, 2016.
[31] I. F. Pinelis and A. I. Sakhanenko. Remarks inequalities for large deviation probabilities. Theory of Probability & Its Applications, (0(1):1433145 1986.
[32] Tong Zhang, Learning bounds for kernel regression using effective data dimensionality. Neural Computation, 1709)20077-2098 2005.
[33] Lászłó Györfi, Michael Kohler, Adam Krzyžak, and Harro Walk. A Distributtin-Free Theory of Nonparametric Regression. Springer, 2002.
[34] I. Steinwart and A. Christmann. Support Vector Machines. Springer, 2008
[35] Ingo Steinwart, Don Hush, Clint Scovel, et al. Optimal rates for regularized least squares regression. In Proceedings of the 22nd Annual Conference on Learning Theory, pages 79-93, 2009.
[36] Peter J. Huber. Robust statistics. Wiley Series in Probability and Mathematical Statistics. John Wiley & Sons, 1981.
[37] Abhishake Rastogi and Sivananthan Sampath. Optimal rates for the regularized learning algorithms under general source condition. Frontiers in Applied Mathematics and Statistics, 3, 2017.
[38] Haobo Zhang, Yicheng Li, Weihao Lu, and Qian Lin. On the optimality of misspecified kernel ridge regression. In Proceedings of the 40th International Conference on Machine Learning. volume 202, pages
2023.
[39] Dao Ha Fuk and V. Nagaev. Probability inequalities for sums of independent random variables. Theory of Probability and its Applications, 16:643-666 -600, 1971.
[40] Emmanuel Rio. About the constants the Fuk-Nagaev inequalities. Electronic Communications in Probability, 22:1-12, 2017.
12

---

[41] Hongwei Wen, Annika Betken, and Wouter Koolen. On the Robustness of Kernel Ridge Regression Using the Cauchy Loss Function, 2025. URL https://arxiv.orrg org/ org..///503....... 20120.
[42] Heinz W. Engl, Martin Hanke, and Andreas Neubauer. Regularization of Inverse Problems, volume 375 of Mathematics and its Applications. Kluwer Academic Publishers Group, 1996.
[43] Qiyang Han and Jon A Wellner. Convergence rates least squares regression estimators with heavy-tailed errors. The Annals of Statistics, 27(4):2286-211,, 2019.
[44] Arun K. Kuchibhotla and Rohit Patra. On least squares estimation under heteroscedastic and heavy-tailed errors. The Annals of Statistics, 50(1 (0(1):2773002, 2022.
[45] Shahar Mendelson. Upper bounds on product and multiplier empirical processes. Stochastic Processes and their Applications, 126(12)3355-3666 2016.
[46] Shahar Mendelson. Learning Bounded Subsets of Lp. IEEE Transactions on Information Theory, 67(8):5269-5282, 2021.
[47] Jvan-Yves Audibert and Olivier Catoni. Robust linear least squares regression. The Annals of Statistics, (9(5):27662779) 2011.
[48] Daniel Hsu and Sivan Sabato. Loss minimization and parameter estimation with heavy tails. Journal of Machine Learning Research, 17(18):1 -00, 2016.
[49] Christian Brownlees, Emilien Joly, and Gábor Lugosi. Empirical risk minimization for heavy- tailed losses. The Annals of Statistics, 4366):2507-2536 2015.
[50] Gábor Lugosi and Shahar Mendelson. Mean estimation and regression under heavy-tailed distributions: A survey. Foundations of Computational Mathematics, (055):1455111 190, 2019.
[51] Olivier Catoni. Challenging the empirical mean and empirical variance: A deviation study. Annales de I' I'Institut Henri Poincaré, Probabilités Statistiques, 48(4): 1 148 1185, 2012.
[52] Gábor Lugosi and Shahar Mendelson. Sub-Gaussian estimators of the mean of random vector. The Annals of Statistics, 47(2):783 794, 2019.
[53] Shahar Mendelson and Nikita Zhivotovskiy. Robust covariance estimation under T4-T-2 norm equivalence. The Annals of Statisties,
2020.
[54] Jaouad Mourtada, Tomas Vaškevičius, and Nikita Zhivotovskiy, Distribution- free robust linear regression. Mathematical Statistics and Learning, 4(3-4)::53-292, 2021.
[55] Wanrong Zhu, Zhipeng Lou, and Wei Biao Wu. Beyond sub-gaussian noises: Sharp concentra- tion analysis for stochastic gradient descent. Journal of Machine Learning Research, 23(46): 1-22, 2022.
[56] Joachim Weidmann. Linear Operators in Hilbert Spaces. Springer, 1980.
[57] Michael Reed and Barry Simon. Methods of Mathematical Physics I: Functional Analysis. Academic Press Inc., 2nd edition, 1980.
[58] A. Berlinet and C. Thomas-Agnan. Reproducing Kernel Hilbert Spaces Probability and Statistics. Kluwer Academic Publishers, 2004.
[59] H. Engl. M. Hanke, and A. Neubauer. Regularization of Inverse Problems. Kluwer, 1996.
[60] Haobo Zhang, Yicheng Li, and Qian Lin. On the optimality of misspecified spectral algorithms. Journal of Machine Learning Research, 25(188):1-50, 2024.
[61] Andreas Neubauer. On converse and saturation results for Tikhonov regularization of linear ill- ill-posed problems. SIAM Journal On Numerical Analysis, 34(2):517-527, 1997.
[62] Yicheng Li, Haobo Zhang, and Qian Lin. On the saturation effect of kernel ridge regression. In The Eleventh International Conference on Learning Representations, 2023.
13

---

[63] Wanrong Zhu, Zhipeng Lou, and Wei Biao Wu. Beyond sub- Gaussian noises: Sharp concentra- tion analysis for stochastic gradient descent. Journal of Machine Learning Research, 23(46):
1 1-22, 2022.
[64] E. De Vito, L. Rosasco, and A. Caponnetto. Discretization error analysis for Tikhonov regular- ization. Analysis and Applications, 04(01):81-99)) 2006.
[65] Nicole Mücke, Gergely Neu, and Lorenzo Rosasco. Beating SGD saturation with tail-averaging and minibatching. Advances in Neural Information Processing Systems, 32, 2019.
[66] losif Pinelis. Optimum bounds for the distributions of martingales in Banach spaces, The Annals of Probubility, 22(4):177-11766 1994.
[67] Mattes Mollenhauer. On the Statistical Approximation of Conditional Expectation Operators. Phd thesis, Freie Universität Berlin, 2022.
[68] Christian Fiedler. Personal communication, September 2025,
[69] Zheng-Chir Guo, Shao-Bo Lin, and Sing-Xuan Zhou. Learning theory distributed spectral algorithms. Inverse Problems, 33(7):074009, 2017.
[70] Takayuki Furuta. Norm inequalities equivalent to Heinz-Löwner theorem. Reviews in Mathe- matical Physics, 01(01):135-137, 1989.
Appendices
The appendices are organized as follows.
Appendix A contains numerical experiment which confirms the behavior of the excess risk as described by the bounds provided in the main text in very basic setting. In Appendix B, we report proofs of the results in the main text of this paper. In Appendix C, we provide an additional excess risk bound for the polynomial confidence regime based on Proposition 3.1. We collect some tail bounds and concentration results in Appendix D. In particular, Appendix D.3 contains a proof of Proposition 5.1. In Appendix E, recall additional miscellancous inequalities required for our proofs.
A Numerical experiment
We provide basic numerical experiment showing that the confidence regimes only occurring in the upper bound on the excess risk given by Proposition 3.1, but are effectively reflected in the distribution of the excess risk in practice, even for very simple models.
We consider the input space X' := R equipped with the RKHS H induced by the radial basis kernel ((I1.T2) exp( -lx; =x,1 and define the target function fx) : = x,)(z,, H. X for vectors a = 12, -1, -, 1, 1,2) and x == (-4, -2 - 0,3, 7). We define the covariate distribution X π \/ 1) X' and generate independent observation pairs with light-tailed noise distribution and a heavy-tailed distribution with identical variance based on
(i) the light-tailed noise model given by
YOu = f+()) + E(A);
(21)
where the noise ((N) ~ (0, 22) follows centered Gaussian distribution with variance
'We provide the source code on GitHub: https: //gt thub. www.///wleeehaaaeeeerrrrrerereee heavaaaeeeeeeeerr---e--------eee tailed. The experiment be the CPU of any consumer laptop.
14

---

ii the heavy-tailed noise model with a finite number of higher moments given by
( fx(X) E())
(22)
where the noise E() t(0, v) follows centered t-distribution with -3 degrees of freedom and B| 3.
0.3
1.8
0.1
0.5
quantile Q
1.6
1.4
1.2
0.6
confidence 1-6
(a) Light-tailed noise
0.01
0.3
1.8
0.1
1.6
quantile Q
1.4
1.2
0.6
coufidence
(b) Heavy-tailed noise
Figure 2: Empirical approximations of the quantile function of the excess risk Ia (l) for (a) the light-tailed noise model given in (21) and (b) the /-distributed noise model given by (22) for different choices of the regularization parameter and fixed sample size 20.
For both models, compute fa based the generated sample pairs for sample size 20 and record the error || fo ( which we approximate through Monte Carlo simulation by drawing samples from π. We perform the above computation for a selection of different regularization parameters a, repeating each experiment across 10000 random seeds (per model and choice of a). Based on the recorded errors, we empirically approximate the quantile function of the distributions of [a fall given by
Q(1 - 8) inf IP [ fAlle?G) st 21/21-6}. 8 [0.1]
The resulting approximated quantile functions are visualized in Figure for choices and both models.
15

---

While the excess risk quantiles exhibit the same qualitative behaviour and are of the same order in both models for moderate confidence levels, the excess risk quantiles of the heavy-tailed model increase rapidly for small regularization parameter beyond high confidence level of 1 å R 0.95. Consequently, the heavy-tailed model requires a stronger regularization than the light-tailed model in high confidence settings, explained by the transition of the excess risk from a subgaussian confidence regime to a polynomial confidence regime Section 3.
B Proofs
We provide the proofs for the results presented in the main text of this work.
B.1 Proof of Proposition 3.1
We investigate the classical bias-variance decomposition
Iffa- - f. = Ixfa -Ifa + Izfa f.
and bound both terms individually.
B.1.1 Bounding the variance L - Lafa.
We first collect some generic properties of fa. The identity fa = (C, + a gives
E [=fff--i,ff)l = (f+ I+fa) afa.
(23)
Based on (6), (7) and (8), we decompose the variance in H. as
Fa - fa = (C, + aalx)
[r. - -xfa) afa + Σ ((X))=
1=1
= (Ōx a
[f - - - Iafa) )= + x(x))ss
by (23)
=C² + a Idx)
-1 + +22,
where we introduce the H-valued random variables
A2 1 o(X))s
- A Inf - - Iafa)),
(24)
We now obtain an L (2(TT)-orm) noom bound the variance
[Fa fa))l
(fc fa)lH 1C llxx) + A2)llH
22 B(n, a) 1/2 [ + a ldd)) 1/2(( (alld))-(A4 + 423
s <2v2l + aald)) 1/2 11/2 + +2 7
/2 / (1 (1
(25)
with probability at least 1 - 6, where B(n, ō, a)) is defined in (57) and where we apply Lemma D.10 in the first inequality, Corollary D.7 in the second inequality, and additionally the fact that have IIC,= + Idx) -1/2|l(ccn I -1/2 in the last inequality.
We now provide individual confidence bounds for A and 22.
Bounding Ai: Bennett inequality. We introduce the independent and identically distributed random variables & == (f+(X,) - Sa (X:)))(((X) E H and note that A := 1 Ei (E: -R(G]) and proceed similarly as in the proof of [4, Theorem I & Theorem 5].
16

---

To apply Bennett's inequality, we need to bound the norm of the E,. First, note that almost surely, we have by (SRC), for some f (T). such that (=7=) S R
(lla(x))(( - (1
I fall
x²1 (C₂ + +a (,5d))
TT + addx)) -TT= f(
short calculation shows that for v 2 1/2, the map h(t) = t/2 + a)- is increasing on the spectrum of T with
sup (0,x) tE(0,x2)
[4(1)] = sup
12-1/2 1/2
S 1222)
1
for or > Hence,
(T + t Idx) TT= S.s.R S. sup
[n(t) S R. (22221122
1E(0,x²
and therefore
I1.(X.)6(xi)la) S R. 20+1 20t1
This gives
|& k.lfflll + IIfa(X;))XX) 1
<x|lfAll<>><T) + R x 2
Furthermore, by [64, Proposition 3.3] and [11, Lemma 25J see
E| <
// (x2 fn = =x² (1dx Tx (Tx + a Idx) "TT=""""" fl(22())
S 2² min mmnnee) (w.1)
Applying Proposition D.2 to A = 1 Σm (5: E(gil), with probability at least - 8 for for any
1 > 8 0, we have
2(m1l.fall + R x 2 log(2/0)
2x² R2 2innfu1)) log(2/8)
|
5
n
n
$ C. (lo((2/))
2 mimin( log(2/8)
(26)
7
n
where 2ogg (2/8) log (2g6) and with
C. = 2x fl
R 2" R}.
(27)
Bounding A2: Fuk-Nagaev inequality. We introduce the independent and identically distributed
random variables G = o(X 6(X;)); and note that A₂ E G. By Assumption 2.2, clearly have E[G] = E[o( X B[c X] as well as
E| < 022
and B|| < RQQ.
can therefore apply Corollary 5.3 to A2 1 I Çi and obtain
(201120) 1/4 (om--1))
log (2g(2c1/0) C2n
||lllx S max
(28)
with probability at least 8. 8.
17

---

Collecting the terms. By the union bound, the three individual confidence bounds (25), (26) and (28) and hold simultaneously with probability least 1 1 8. We have
Co Va
log(6/6)
2 mi,( log(6/0) + =((8,n)
|1 Sa))l -
n
Here, we set
Q
1/0
log(6c, /8)
1)66, n) == max
8ng-1
,0
72
and
Co = 222 maxt max 1/ vo2)).
(29)
B.1.2 Bounding the bias fa f- f.
We apply the standard theory of source conditions in inverse problems discussed for example by [59]. In particular, under the (T² condition given by (SRC), we have
1/ fa (=) Ramin
e.g. [64, Proposition 3.3]. Combining the variance bound and the bias bound yields the result.
B.2 Proof of Corollary 3.2
Let 8 E Di(n,)), Using that S x² and recalling that 2 find by Proposition 3.1 for any E (2 9) with confidence 8
Co Va
log(6/0)
(2min(u,1) log (6/6) + o log(be1/ /0)
|| - (2)) & min
+
+
n2
Assuming
a
min(u,1)
vn 2
v /log(6/8)
(30)
gives
log(6/8) n
(2min log(6/0)
log(Bes/00 (8)
s 2 min
n
n
Hence,
log log(6ea/8)
UI 2 falle2(7) S Ra min + 03
am
with c3 = 3C, 2 o). Ensuring that the remaining estimation error contribution will not be dominated by the approximation error, we see that the regularization parameter has to satisfy
[log(6es/0) /5)
2
a c1
(31)
71
with c4 = (ea/R) m177 We therefore obtain
min(a.13 2min (v,))++
(log(6es/0) /0)
| f+lle2(0) S E1
n
with confidence 1 - 8 and ē₁ 2c, 2c.min(u.1) In order for this bound to hold, the regularization strength has to fulfill condition (9), (30) and (31), that is,
(log(6e//))
2mb
(1og(6/6)
2 2minfu,33
log(6/5)
a N max
Ca
Cr
(32)
72
Vn
in addition to the restriction a S x As we always have n Imm[taa S n
for 2 1/2 and log( (c;/ (8) 2 (6))),), there exists constant y such that
1/2 < n im)
on (n, 8) dz (log(bez/0)
minn
1
satisfies (32).
18

---

B.3 Proof of Proposition 4.3
We split again into variance and bias:
L f. = La - fa) Lxfa f.
B.3.1 Bounding the variance Iafa - InJa
Following [65, Appendix CJ. we further decompose the variance term in L² as
T.fa -a=a = I=fa- - 1Cr + +ald)) Sa + Crr + +IIx)) Sa IJaa
= [Cx + allx)) (1 EnJaa + +ll + a
(33)
=:h
where we use the definition of fa in (7) for the first term and the identity
(Cx + a ldx) Idx = a(Ca + ldx)
for the second summand.
B.3.2 Bounding the first term I
We introduce the shorthand notation C. == Cr + a Idx C2 == Ex + a Idz. We note that we may write
/ + a = 1/2 C/2 /
1/2 leee I and that by Corollary D.9 and Lemma E.2, with confidence 6, Recall that ||C\/2 CT we have
(Cl/2/21/3lll provided (14) is satisfied. Hence, by (4), with confidence 8
C/ [l)())) 2,
|1 (z))) [[ + ald)) (f Cnfa)lle) I [[(, + a ldx) -/2(f fafa)lnn
(34)
We proceed by further splitting
(C, + a ldx) Exla) = (Ca + Idz) ( -C,fa) (17 Cx
+ (Cx -l1 -C.f))
(I,
Note that by (8), we have
T= i f= + Σ o(X)e.
71
im
Introducing
A = (i34 - -(,
- CxJa):
A
o ((X))a
obtain
(Cr aald) - -Crfa) In + I12 + I1s.
where we set
In (C. +ald))
41 == (C,, +aldx) 11/2
Ja3 = (C, + +al -1/2 - C-Ja)-
Thus, with (34), we have
(Tll22(0)) S 1411 + |1 + hall
(35)
We proceed to bound the terms on the right hand side individually.
19

---

N(a) log(2/8) Bounding 1ull To bound the norm of /11, we apply Bennett's inequality Proposition D.2 to the
independent and identically distributed random variables
:= (C* - a -xxx)) - (x.)))))
Then
1 Σ & -[G]]- I1
1=1
Furthermore,
E E H
S sup [f((X) fa(x) B[l[(C, + (/xx))13
Xex
since fa H. and by (SRC), we have for 2 1/2
[x((X]
Kfa: (X)))²l
K(C, + a (dd)
KV.T," + ( (P(7]
S kR]] (T= + (d) (1)
kR sup
|t a
0C15#²
< k R.
(36)
We proceed with writing
(C, + a ( E[tr((C, + Idlx)) @ o(x)))
-aaa).
Hence,
E| s 2( + R()() =: 0²
Moreover,
||
[I(C, +
S (X,, + - II (ddd))11122/ -1))))11/((Xl
kilffllbo + kfa(X,)
Va
Va
(llfalloo + R R) L.
In the last step (36). From Proposition D.2, obtain with confidence 1
2L log(2//)
28 log(2/8)
n
(2/0) Van
S <n
(37)
n
with C11 = 2(I.foloo + 2 R) max(1,
Bounding || The idea is to apply the Fuk-Nagaev inequality Corollary 5.3 the independent and identically distributed random variables
G = (c + Idw) -122
We repeatedly apply Assumption 2.2 to bound the expectation and moments of the G. We get
E(G]] = E + a -dx) = 0.
20

---

Moreover,
B E[ [I(, + + 1/2 (X;) [+]
<o + +aldx) @ ((x)))
= Noa((a)
=: =.
Since q > we find
| = | [|1; I[(c + Idx) -1/2 -122(()111
< Q [C + a ((x,)))'(((((x))))))))) + Idx) 12xx))
$ S k8-2
N(a)
Q
Since
Ei= Si = 112 applying Corollary 5.3 gives with confidence
1/9
201
log(2c1/0)
1221 & max
8n
C2n
12 2Q
1/8
S=2
loglo/ /0)
N(a)
max
8ng-1
C2n
ông-1 (11
1/4
8-2
log 201 25)
S122 ((2) max
(38)
(N((a)
with C12 max -Q) //////////e v22)
Bounding 1/ll|
Using the definition of fa from (6), we see that by (SRC), we have
113 = (C, + a Idx) ( - C₂ (Cx + a (dd))=112
(C= + adx) 11d CC= + Idx) 1)
(1d (C, + aldx) 1==T""
[T + a 1/2 (Id,, - (T= + Id1,)) -1)
/T a Id22) 112 (Id - (T + a Id -
for some (T) satisfying [[fll R and the partial isometry Ú L L²( given by (4).
This gives
|1l1| S R sup UCtSK²
lat |at2+1/2 3/2
3/2
< R sup 0<t5^²
lat" (t + a)
sup OcTEu2
1 (t + +1)
< R sup OctSR?
lat" (1 + aa-11
S R maxx 212 a min[u,1] 613 a min1
(39)
where we use Lemma E. for the last inequality and set C13 == It max x 1)..
Collecting all terms. Collecting the bounds (37), (38), (39), together with (35) and taking union bound gives with confidence
| ( 4(11/1ll + ||42||æ + [{41)11))
@min(eul)
log(4/5)
((a) log(4/6)
VN(a) ((0,n,a))
CR.ng.
Van
n
(40)
21

---

where we set
((,, 0) = max
(
1/9
20
llog(4er
1og(4c1/8)
Ōno-1
(N((a)
n
and with Ct = max 012; C13).
B.3.3 Bounding the second term 12
write again C. = Cr + a ald2,, C, := E5 + a Idz and find with Lemma E.2 and Corollary D.9 with confidence -
[11 = Ilad [C, + Id ldd))
=alliac, 1/2 1 (a)l((()) = =a /1 C/ 1/ 1/2 C SallH
I 4a 1|c 1/2 fallH.
where we again use (4) and have with confidence δ
1/2 [1c())) I Hence, by (SRC) and the definition of far Co
[1 S 4a ||Ca1/35al1 Sallx
s 4R sup Ja(t a)- 3/222/11222
0C1S"²
< 4 2(v-1)) min(u.1) = 4c1s min[u.1)
(41)
where we repeat the computation from (39).
B.3.4 Final variance bound
Collecting (33), (40) and (41) and taking union bound gives the final bound for the variance. With confidence 1 5, we obtain
[|T fa))l I Eaaaal minn(e.)) +
log(8/8) Van
N(a) log(8/)
VN(a) ((aa))m(.,,,))
where we set
n(ō,n n. = max (1
(1
1/4
2a
log (8c1 18)
Ōnd-1
[Na(a)
n2
and with &. = max C11, G12; C13)-
B.3.5 Bounding the bias fa - f-
The bias can be bounded in the same way as in Section B.1.2:
| f+1le0(0) min.v.)
Combining the variance bound and the bias bound yields the result.
B.4 Proof of Corollary 4.4
We first need standard lemma that allows to bound the effective dimension based on the eigenvalue decay of Tx due to [11, Lemma 11].
Lemma B.1 (Eigenvalue decay). Assume (EVD). Then there exists constant D such that
((aa) s Da > 0.
22

---

For simplicity, we will use the symbols X for inequalities which hold up to nonnegative multiplica- tive constant that does not depend on n and 6.
We first note that for every fixed ő E (0, 1), short calculation shows that there exists an in E N such that with the choice
a<n, 6) == [oog(8n ())=)(00(8/////1)) (801/))) min
the condition (14) is satisfied (since we have na(n. 6) + oo and (na(n, (onn)nn,.+)))) 8)(1+)//2 - oo for + oc). We may hence apply Proposition 4.3 and with confidence 1 - 6, we have
|| falle((s) c miin((.)) + log(8/6) Van
N(a)
+ VN(a) - (W(a)-n6,n,.0 ((6,n,a)
n2
(42)
with
(6 n, a) = max (0re)=) 1/9
(
2x
log(Ser /5)
(Na(a)
71
for all n 2 nn with a constant > 0 not depending on ō and n.
We now show there exists Vin E N such that
VN(a(n,8) n1ō, a(n, 8)) $
(43)
ma(n, 6)²
for all 2 Tlg i... the subgaussian term asymptotically dominates the regularized Fuk-Nagaev term under the choice o(n,,) 8). In fact, note that under N(aa) < Do ensured by Lemma B.1, have
2
2 N(a)p/a <
1 α
2
p/q
Vi(a)
aN((a)
and we hence have
1/9
D
p/q
log(8cr/8) /8)
(N(()) n(),n,)) Smax max
(44)
Óng-1
We insert the definition of a an, 5) into (44) and isolate the exponents corresponding to 1/n in both expressions inside of the above maximum. We obtain the exponent
8-1 1
(9-2 2
2(g - 1)(2 min (v. 1) + +p) - (g 2 2p)
2 mi 13 +p
2q
+
=
2g(2 min 1] +
(45)
for the first expression and
1
p/2
min 13 min (v. 1}
(46)
2
2 min 1)
2 min 1) 22(2min (v. 1) + p)
for the second expression. We show that the difference between the numerator of (45) and the numerator of (46) is nonnegative. We have
2(g - (2 min min 1) + +) + 2p- 29 min 1] = (4g - 4) mnin(v11] + 2p(g - 22) 2)
21/2
20
2 q - q == 0,
where we use
2, q and 1), hence proving (43).
23

---

log(6/8) Consequently, for n 2 max )ot and with Lemma B.1 and (43), the bound provided by (42) now reduces
log(8c1/0)
log 8c1 (81()/1/)
[a fL) a(n, 8)
+
Va 6)
na(n1,
minfu.1) 2min(uil)
(min(u.1))pp 2min(u,3)
log(S 8cy /0)
1og(Scr/0)
min(e,])
log(8c2/0)
min(v.1) minn m1
log log(Be1/ Sea /6)
72
with confidence 1 - 8, where we use /lo((8/)) < log(8/8) S log(8c1/0) since ej 2 1, and bound the exponent of the middle term the second step using v 2 1/2.
C Excess risk bound for polynomial confidence regime
We now prove simplified capacity- free excess risk bound based on Proposition 3.1 for the polynomial confidence regime D2(n, q).
Corollary C.1 (Polynomial confidence regime). Let (MOM) and (SRC) be satisfied. There exists constant с and a subset D2(n, q) S D2(n, q). defined in the proof, such that for all 8 E D2(n, g). have
| [ fo [x)( S c- azznn, 8)mmmii)(
(47)
with confidence 8, where
log(6/8)
a2(n, = max
x2
On
Vn
Proof. Let D2(n, 9). We have from Proposition 3.1 with confidence 8
[T fullep(s) I Ra min +
C. Va
2 min log(6/6)
Q
1/4
n
n
8n
Note that E D2(n, q) and ei ensure that
1og(6/8)
log (og(6e1/0)
1/9
8n
Hence, since (n 8) s x we find
min log(6/0)
R mi.((
Q 8n9-1
1/9
This leads to the bound
1 JAllea(s) S min
Co
log(6/0)
1
1/4
Va
n
07
5nu-1
holding with confidence and where we set e7 = Q1/9 (1+
2 min(
Next, we observe that condition (9) implies
log(6/8) <
Cr vn
24

---

Further assuming
1
Zmin 1.,))
(48)
n
then
Co
a
C
minfv.3}
CR
Vn
C
a
The upper bound for the excess risk reduces then to
II - f- cs miinf,
( 6nn-1
1
1/9
+
va
where we introduce R + Co and 0g 07Co.
Cx
To ensure that the remaining variance part is the same order as the approximation error part, we need choose
2 C10
(49)
óng-1
2mi 19)+
with C10 =
On
This finally gives with confidence 6
|T f-1le>(m) I 2ng a min(1
provided conditions 5 E D2(n, 9) (9), (48), (49) and a < x² hold. To simplify the conditions for a, observe that for all 3, 1 and 8 (0, 1) we have
of2 m12m
8ng-I
As result, condition (49) implies (48) with appropriate constant. To sum up. the regularization parameter needs to satisfy
1
log(6/0)
C11 max
8nn-1
Vn
with C11 max (1 c10, Cx).
To ensure that a remains bounded by x² it is sufficient to choose n sufficiently large:
n 2 (5) = cn max -2 (6g)
with y 2q(2 2q(2 min
Recall that 5 D2(n, 4) requires
q-1
Q22
n S Rmma (d) =
log(bc1/0)) 18)- gーz
24
so we need to restrict D2(n, q) such that both conditions for n are met. Letting now E (2(
with
(2 q) {8 D2(n,g) no(d) S Plyan (5))
then (47) holds with confidence 8.
D Concentration bounds
We collect the concentration bounds used in the main text of this work and prove Proposition 5.1.
25

---

D.1 Hoeffding inequality in Hilbert spaces
The following bound is classical and follows as a special case [66, Theorem 3.5], see also [67, Section A.5.1].
Proposition D.1 (Hoeffding inequality). Let E, S1............................ ... ... be independent random variables taking values in Hilbert space X such that [E[{] = 0 and llEllx S L almost surely. Then for all t > 0. we have
n
nl22
21
S 2 exp
2L
X
D.2 Bennett inequality in Hilbert spaces
We now give a version of Bennett- type inequality going back to [66, Theorem 3,4]. We use the confidence bound version as derived by [4, Lemma 2}.
Proposition D.2 (Bennett inequality). Let E. En be independent and identically distributed
random variables taking values in a Hilbert space X such that ||E||x S L almost surely and
x² : ) Then for any 8 E (0, 1), we have
n
2L logo(()/0)
20 log (2/6)
3
E[{]
n
n
x
with probability at least -
D.3 Fuk-Nagaev inequality in Hilbert spaces
The bound in Proposition 5.1 given in the main text is sharper version of more general bound given by [27] for general normed spaces, which we state here for completeness.
The original proof of the result below relies on an inconsistent exponential moment bound, which we address by providing an alternative bound alongside a detailed proof. We were made aware of this fact by Christian Fiedler [68], who contributed to the alternative proof presented here.
Proposition D.3 (Fuk- Paaa-e inequality, [27], Theorem 3.5.1). Let f1....E, En be independent and identically distributed random variables taking values in normed space X with measurable norm such that
Eig.J O,
Σ
< B and EBTEEN <A
(50)
for some constants B > 0, A> 0 and E N, 2 3.
Then there exist two universal constants
C1 > and 02 depending only on q. such that with Sn = Σi= 1 &s we have for every t >> that
A
P |[ - SIII |x] 2 tB < C1
+ exp((c2(?)
B419
Compared to the result above, Proposition 5.1 removes the excess term ||||,,]|x]] the left hand side by making use of the geometry of the Hilbert space norm (see [31, 66)).
We now prove Proposition 5.1 and emphasize that it can be directly extended to random variables in (2, D) D)-smooth Banach spaces by incorporating arguments from [66] with adjusted constants. We provide the proof in three parts: In Appendix D.3.1, give exponential moment bound. Appendix D.3.2 contains the core proof of Proposition 5.1 and incorporates the exponential moment bound into Chernoff bound that is obtained via truncation argument. Appendix D.3.3 provides the final optimization the Chernoff bound.
D.3.1 Exponential moment bound
We now provide a sharpened version of [27, Lemma 3.5.1] that allows to bound the exponential
moments of sums random variables in Hilbert spaces. The proof of [27, Lemma 3.5. is lacking details and is inconsistent, as it generally seems to require bounded scaling factors h >> 0 in the exponent, but the result stated for all h > Our proof holds for all h > and gives a slightly adjusted bound.
26

---

Lemma D.A. Let Ei....E, En be independent random variables taking values in separable Hilbert space X such that the conditions (50) are satisfied and additionally [Eillx S holds almost surely for some I, >> O and all 1 S S Then for all h. > 0, we have
E[[osh(h]] x[)] S exp(izh2 B² + Eq Ah.hee
where the positive multiplicatiie constants 02 and En only depend on q.
The upper bound of Lemma D.4 differs from [27. Lemma 3.5.1] in the sense that it removes an additive constant in the exponent. Furthermore, our constant č2 of the quadratic term depends on while 62 1/2 for all q in [27, Lemma 3.5.1J, which seems conflict with unbounded 0.
Proof. We have
B B/oosh(A||S,,
[x)] -
T Mleillx 1l[lillx
i=1
I exp
E Melllx -1 h||[:|1x]]
where the first inequality is due to [31, Theorem 3], the second inequality follows from the fact that have exp(x 1) for all x E RR We hence need to show
E Mieilla
M|]l[x] S 2 + Al
We start by expanding the term on the left hand side as
1 1111
Σ Misill 1- &
jl
The term for the index j 2 is immediately bounded
1.
1
1
22
2!
2
Hence, the claim now reduces to showing
E
SHBB² + Mr
j!
with constants only depending on g. We split the inner sum over the index q and obtain
h
E
=
+E
5!
j!
jl
We now proceed to bound both terms the right hand side individually. Bounding the first summand.
We address the first term as
lel
1 12 3
11115:11
< E
j!
j!
h
+ -
11 122
1=1 q
9
i 2
h9 + q-1 12
9-2
$ A + 1²B² < Ar 2²²
where we apply Lemma E.3 with æ = -1 a= 1 and p= each individual term in the sum and use that h 0 and L > 0 ensure CL'L 1. Note that the unspecified constants only depend on g.
27

---

Bounding the second summand. It remains to bound the second sum. Almost surely, we have
h2 ||:
h 1
19
11
j!
g!
(q + 1}!
h 11 11
11 13
g!
(q + 1)
(q + () +
ht I1 11'x
h
1221.
I+
+
g!
(1+1)
(q +)(++2
48
h h A,
B [2]
9!
q!
proving the claim.
D.3.2 Core proof of Proposition 5.1
We now prove Proposition 5.1 by modifying the truncation argument and Chernoff bound given by [27, Section 3.5.2] in combination with Lemma D.4. Let us assume that (50) holds. For L > 0, introduce the truncated random variables
E = & [[G
S,
In contrast Sn, the truncated sum S,, is not necessarily centered. Here, our version of the proof differs from the proof of [27, Theorem 3.5. J.. The original proof approximates the centered norm ||S, Ilx S.,lxx] with the truncated centered norm ||S,,]lx - E llx leading to the excess term S, [x] in the event for which the tail is bounded. In contrast, we perform the centering directly in the norm: we approximate ||S with ||S,, EiS,lllx.
We first note that the difference between ||S, and its centered version ||$,, E|[S]]l x can be bounded conveniently:
|| |1S.11x - 1|S,- - 1B13,IIIx s [[B[S,]]|x [[B[S,] - [[S,]Ilx
E [ié: &allx
E [1 [1l. > ||Sillæ ]
||5 ||E:|lx
Σ E 1 [1
||5:113==1
(51)
T--1
We now verify the conditions (50) for the centered sum 3,, - E[[S]. We obviously have
Ell. - EESJE Σ E
E S B².
28

---

Furthermore, from Minkowski's inequality followed by (a + by - 25-1(aa + 69) for a. b 2 0 and Jensen's inequality, we analogously obtain
by
Bllk: - 1
S
Bille 1/4 =IIl)
2 2
[ B[1E))))))
$ 29
ElI & - 29
Bills 1 2 =: Á.
We now provide the final tail bound for the norm of S by approximating it with the centered truncated sum S. E. For every and h > we have
Slll5, 2 (B) s p(s.. * S, + PP[| 8, LB)
A
<
+ PIIS 11x 2 LB)
(Markov's inequality)
L
A
<
+
PÍ1S, E[i,I]llx 2 tB - A/L
(by (51))
L
A
hA
+
exp
-IBB + T8-I
Elexp(//) S, E[S,]11x)]
(Chernoff bound)
LA
A
hA
+
htBB +
2E(cosh(AA]5, -[(,,]l+))
(cosh(x) = (E" + -)//2/2)
L
L
A
+
exp
-ttB + L
hA
+ O2 B2 + tzgAneehL)
(Lemma D.4)
La
Á
-htB + La-I + 2z 1²2 + EyAlie/L))
2
+
exp
L
We derive an upper bound of the last expression in the parentheses over all choices of L >> 0 and shown in detail in Appendix D.3.3, giving
Á
P P x 2 BB] S e1
+ exp(-e22l
(52)
Bot9
for some positive constants ej and 02 only depending on q. Note that we absorb the factor 2 from Á A into the generie constant ej in the resulting bound.
Whenever the & satisfy [ = x² and 11 = Q for some constants 0², o2,Q= > 0, we may substitute B no² and = nQ in (52). Rearranging proves the bound given in Proposition 5.1.
D.3.3 Chernoff bound optimization
The final bound we want to obtain is of the form
À
hÅ
À Bats
min h.
+ exp
-htB++ 1 + 22h B²
ci
+ exp(-o2t²)
(53)
L
with positive constants et and 02 only depending g. We now adapt the idea of the original optimization argument by [27, pp. 105] to the setting of our Lemma D.4. We first introduce the shorthand notation
A(t) = Af(B9t and A(t) = L/(tB).
With this notation, rewrite the term the left hand side of (53)
A(t)
exp
-tt (BBA(t) + & (
A(t)
A(t)
+
(54)
A(()9
29

---

Note that for all t > 0. A(t) can be chosen independently of (t) by adjusting the truncation level L in our optimization. Note also that (t) is exactly the first summand in the right hand side of the final desired bound (53). We will check the validity of the bound of the type (53) based on a case distinction.
Large ((t). We assume A(t) 1. For every t O, may choose L such that A(t) 1 and proceed to bound (54) as
(t)
A(t) + exp (BBBB(((0)//000 02h2 +c((MB))((t)))
s S((1+ + (M)LL))
1)) 22 (
$ (t) +2 (t) exp(-c21*
for any 02 > 0, if we choose h small enough such that
exp(hIB (1) ()()) +C((MR))(())000)) 2.
20
This establishes (53).
Small A(t). We therefore need to consider the case where (t)) < 1. Without loss of generality. in this setting we again assume that we are choosing appropriately to ensure that A(t) > This gives us
(t) A(19
I A()),
and hence we only need to bound the exponential term (54), as the polynomial term satisfies the final bound (53). We distinguish two cases, as the exponential term in (54) behaves differently for different ratios of t (ot()
Small At),, case 1: We assume A(t) < 1, A(f) > 1 and 12 s 662 log(1/ We will show that in this case, the exponential term in (54) can be bounded by 01 exp(-c2tt))
We choose the optimization parameter h := zt/B with some 2 > 0, which we will determine later. The exponent in the right hand side of (54) can now be written as
=\(0)//())--11 - 22 2, A())
02 + + 2
<f(=A(t) -2 2+222 + +0,229(62
log
L- + 2 1
(55)
where we invoke Lemma E.4 in the last step and choose z small enough such that we have
At) + 2 ei 0 and 1 6o2A(t)= C2 0,
in which case the exponent estimate (55) is bounded by -cit² + č, yielding the claim.
Small A(),, case We assume A(I) < <1, 1, A(L) > and 12 672 log(1/((1). We will show that in this case, the exponential term in (54) can be bounded by At).
30

---

In this regime, we choose the optimization parameter h := 2ogg(1/A(t)/(tt)) > 0 with some > 0 which we will determine later. The exponent (54) with this choice becomes
log( (0)((/)())(11----0 A(1)/A())=)) 6 log(1/A(1)2
log(1/A(0))((6e)
+ē (ogl/))))( (t)) (0
S log (())() (1))
+ log(1/A(1)) + 2
log - 622
6
2² + 2 2d (1 ( A62)))
S slg(A(()) +ōgz
(56)
where in the last step we apply Lemma E.4 and choose & small enough such that
(1)=
2 and 1- (-622A(() > & 0.
We finally obtain upper bound of the exponent (56) log( (t)) غ, yielding the claim.
Final bound: The final bound (53) results from considering all of the the above cases and choosing the individual constants and large enough such that all cases are satisfied simultaneously (for example by choosing the maximum the individual constants obtained above).
D.4 Concentration of empirical covariance operators
We have the following classical bound on the estimation error of the empirical covariance operators when Proposition D.1 is applied to the centered random operators & <(X,) @ o(X,) Cn which are bounded by 2x² can be bounded by the Hilbert-Schmidt norm.
Tillbert-Schmnn norm under Assumption 2.1. Note that the operator norm
Corollary D.5 (Sample error of empirical covariance operator), Under Assumption 2.1, we have
(2/8
C C. S2(H)
S 22n²
7
with probability at least 1 5.
We now recall result by [69, Proposition 1]. Proposition D.6 (Empirical inverse, [69], Proposition 1). Let Assumption 2.1 hold. For all 8 e (0, 1),n n N, a denote
2x²
An2N(a)
2
:= 1
+
(57)
na
na
With probability at least 1 -
[ + a aldd) + aldz)
$ 2B(nn, a,).
(58)
C(H)
In particular, if
N(a) S n
na < N(a),
16 16 x (2/8)
(59)
a
then CCx + Idx)) (C, aldx) (000 54
Proof. We prove the particular case. Note that if (nax) S N(a).
B(n, 8, a) 1 + log² + 1)2 4k ((()
log2 (2/8) M(a)
16 1ax (1,x(1,1*)) v²)
na
na
Therefore, if 16 maxxx1, log" (2))(2/)) < no, then B(n, 8, 2 2.
31

---

We next give a Corollary, providing simplified bound under worst case assumption for the effective dimension that can be applied without information about the eigenvalue decay.
Corollary D.7 (Empirical inverse, worst scenario). Let Assumption 2.1 hold. Assume that (a) S ca ca- for some e > 0. Then, with confidence 1 - ò, we have
| + TT + a Idzz L(H)
4,
provided that
log(2/6) C₂
S TT,
== 2(1 vc) max (L, R²
a
Proof. Using ((a) & ca and plugging it into (57), we obtain
2x²
2/ex" 2
1 11+ log (2/5)
na
Vna
Note that
2k²
2/CK
max 11 mmx x2 2(1 + Vc)
Cx
Vna
Via
Vña
Therefore,
C
B(n, 8, 0, 11+ log (2/8). na?
To ensure 6(n,0,0) & 2, it suffices that
C na
C₂ log(2/0) vn.
log2
Under this condition, we obtain (n,, 5, a)) < 2, and hence
|| [C + al) -1 (C= + aT) $4,
as claimed.
Remark D.8 (Worst case scenario). Note that, by Assumption 2.1, we always have
((a)= S tr )a ( <k2a-= x2
We therefore see that the constant in the above assumption always exists and satisfies x².
Under the eigenvalue decay assumption (EVD), the conditions of Proposition D.6 can be simplified. Corollary D.9 (Empirical inverse under (EVD)). Let Assumption 2.1 and (EVD) hold. Then, with confidence 1 5, we have
C1C. + IId Idz)
54,
((H)
provided that
2k
2v DR. (1t(1+p)/2
log(2/5)
+
S 1,
where Đ defined in Lemma B.I.
Proof. By Lemma B.I, under (EVD), there exists a constant ò > 0 such that N(aa) S Da-P. Inserting this bound into (57) leads
2x² na
2V 2V Dr
B(n, a) $ 1+ (2/6)
Vna (pp)/2
32

---

We can use Proposition D.6 to bound the weighted norm of function in H. by an empirically weighted and regularized norm.
Lemma D.10 (Concentration of weighted regularized norm). Under Assumption 2.1,for all I H
and all o > and E [0, 1}, we have
1l s 2n, 8.a)" [[C, + adx))
(60)
with probability at least 1 1-60
Proof. We have
fl I [Cx + a Idx) cccn (C, a aadd)) + adld)) 1ccoo) [Cx + a [dd))*
(61)
We bound the terms the right hand side individually. Applying Lemma E.2 the first term on the right hand side of (61), we have
(C + a $ ||cr + a adx) S 1.
The second term can be bounded with Proposition D.6.
E Miscellaneous results
We recall a standard result that addresses the saturation property of Tikhonov regularization, e.g. [59, Example 4.15). Lemma E.1. Let 0 and v > We have
al"
sup xE(0.x2] t tta S max(1 1, 213-1) a min(r.1)
We will also frequently use the following classical bound for products of fractional operators. Lemma F.2 (Cordes inequality, [70]). Let & E [0, 1] and A, B L(H) be positive-semideeniie selfadjoint. Then we have A Ba lccoo S ||AB]] 200
The next result is part of [40, Proposition 3.5]. It allows us to bound moments between 2 and q. For convenience, we provide a detailed, self-contained proof.
Lemma E.3. Let > For all p E [2, 4). a Ryo, and R>0 we have
( 2) s (p - 2)a² 2x
a + (g - p)a 222
(62)
Proof. We first show that
( () p-2 ( (0--))
())
+ + (q-1i) p)- p)-
(63)
For this, define for some E Ry0 and t E Ryo the function f 10, + R by f(s) = exp(In(y)s))
Note that is convex (since ('(s) = f() In(y), f"(s) f(s) In(y) 0). For E [0. t) we then get
yf s/(
t)
(1-s/1)(() + s/t f(1) = (1 + s/t.
and multiplying both sides by leads to
ty sy" + (t 8).
Setting t - - p- and x/a then shows (63). Finally, multiplying both sides of this with 2² 2222--0 establishes the result.
Finally, require the following basic inequality.
33

---

Lemma E.4. Consider the function f (0, + R++ given by f(a) log(1/a)"a" for some > 0
and q O. Then we have
sup M(a (E(0.1)
Proof. We may substitute the transformation x == log(1/ /a) E (0, oo) and consider f(x) x9 exp(-sx) instead. Note that is nonnegative (0, 00) and that f(0) - f(x) lim f(z) = 0. The derivative f'(x) = exp((=s -x))(x sx9) has the unique root 2, q/s
and hence obtain f(x.) exp(-g) s)9 the maximal value.
34

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We specifically point the settings and detailed contributions of our work in both abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: In describing our assumptions well as discussing our theoretical results, we specifically list our limitations.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sellsspeciiiationn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
35

---

Answer: [Yes]
Justification: We specifically list assumptions in the main text and refer to each as- sumption individually for every theoretical result we obtain. All proofs reported in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof's provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: All details (including parameter settings) required to perform and reproduce our experiment are reported in the paper and can also be found in the GitHub repository. which we provide for the reader.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should be possible for other researchers to have some path to reproducing verifying the results.
36

---

reproducible, they 5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [Yes]
Justification: We provide a GitHub link containing the source code which covers the synthetic data generation well as the computations and plots reported in the paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips) cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: / /nips. sec/public/guu
wtt.uubmisssooooooooooooooo for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All required details and parameter settings are reported in the paper and can also be found in the source code GitHub.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We plot quantile functions of the excess risks and thereby capture the full distribution of the random quantities of interest.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoo bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
37

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We explicitly state that the experiments can be run on any consumer laptop.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: / http///eeuur..eeeee//ee// http://wwrip....ppcttic/ee/eeeee wtw.iiiielneeeeeeee
Answer: [Yes]
Justification:
We have reviewed the Code of Ethics-thh this paper conforms with the Code.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. g.. if there is special consid- eration due to laws or regulations their jurisdiction).
Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Our paper mainly focuses on investigating the learning efficiency of ridge regression. We therefore believe paper does not have any negative societal impacts. We cxplain how our theory can improve our understanding of various learning algorithms the introduction which could be potential positive societal impacts.
Guidelines:
38

---

The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g.. gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
39

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/dataseta has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: the paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
40

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy (https: httpaa/://eepps./.eeee http://errpp..c/oooeeeeeeeeeeeee / for what should or should not be described.
41


Reviews:
[{"review_id": "Hwk63rChKl", "reviewer": "Reviewer_AM9J", "summary": "The paper analyzes the behavior of ridge regression in reproducing kernel Hilbert spaces when the noise is heavy-tailed (only finite qth moment for q>= 3). They discuss the excess risk bound by using vectorized version of standard Fuk-Nagaev inequality used for heavy tails. Further the authors claim that ridge regression achieves minimax optimal sample complexity. Hence, as compared to existing methods, the paper is giving theoretical guarantees for minimax optimal results for heavy tailed noise which was assumed to be sub-exponential before.", "questions": "1) Is the computational complexity affected by heavy tailed noise? If yes, what is the specific relation?\n2) What will be the performance of other regularization methods such as Lasso for heavy tailed noise? Can the minimax results be claimed for other regularization methods?  \n3) In Assumption 2.2, the authors assume q >= 3. Can the analysis be extended for q >=2? The authors discuss existing works in line 93 to have results for q > 0. \n4) Can the authors clarify their contributions as compared to [51]? In line 94, the authors say that [51] follows a similar approach.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strengths: \n- Achieving the minimax optimal guarantees \n- Generalizing the assumption to heavy tailed noise instead of sub-exponential  distribution. \n- The generalized extension of Fuk-Nagaev inequality with decomposition of tail behavior into sub-Gaussian and polynomial term is novel. It can be used for other works. \n\n## Weakness: \n- There is no empirical evidence of the proposed theoretical claims. \n- Heavy tailed noise can be motivated more in the introduction section. \n- What specific kernels follow assumption 2.1 or can you examples of kernels which do not follow assumption 2.1? Do the polynomial kernels in https://proceedings.neurips.cc/paper_files/paper/2015/file/f7f580e11d00a75814d2ded41fe8e8fe-Paper.pdf follow Assumption 2.1?", "was_revised": true, "final_justification": "Overall, this is a good paper. I mentioned the strengths of the paper. Most of my comments/questions or potential weaknesses were addressed by the authors in the rebuttal phase. The authors also did the required empirical study, which makes the paper strong. Hence, I recommend acceptance of the paper.", "rebuttal": "We thank the reviewer for their positive feedback and constructive comments and questions. We have addressed all points of criticism and made appropriate edits to the manuscript. We elaborate on the details below. \nWe would be grateful if the reviewer might consider increasing their score in case they are satisfied with the proposed changes.\n\n**Empirical evaluations**\n\nWe agree with the reviewer that empirical experiments improve the quality of the paper.\nIn fact, just after the submission, we completed a series of numerical evaluations which exactly confirm the behavior described by our theory. We intend to include these experiments in the final paper using the additional space.\n\nWe simulate iid $(X,Y)$ data pairs with $Y = f_\\star(X) + \\varepsilon$ with fixed $f_\\star$ in a Gaussian RKHS and consider a heavy tailed case in wich $\\varepsilon$ is $t$-distributed, and a light-tailed case in which $\\varepsilon$ is normal distributed (both with the same variance).\n\nFor several parameter configurations (distributional assumptions, regularization parameters, number of samples), we compute $\\hat{f}_\\alpha$ across series of realizations with different random seeds for both noise types and approximate the $L^2$-excess risk \n$\n\\lVert \\hat{f}\\_{\\alpha} - f\\_{\\star}\\rVert\n$ \nby sampling from $\\pi$.\n\nGiven the different realizations for all parameter configurations, we compute the empirical distribution of the excess risks and approximate the quantile function \n$$\n    Q(1-\\delta) := \n\\inf_t \\left(\n    P\\\\left[ \\left\\lVert \\hat{f}\\_{\\alpha} - f\\_{\\star} \\right\\rVert  \\leq t \\right] \n \\geq 1-\\delta \\right).\n$$\n\nAs reflected by our theory, the quantile behaviour of both noise models for larger $\\delta$ overlaps almost exactly (subgaussian confidence regime). For small $\\delta$ however, the heavy-tailed model exhibits much larger error quantiles than the Gaussian model (polynomial confidence regime). The transition threshold between these two cases is affected by the number of samples and the regularization parameter choice exactly as described by our theory.\n\n**Highlighting motivation to consider heavy-tailed noise**\n\nWe agree. We added a paragraph to the introduction that highlights the practical relevance and applications of heavy-tailed noise models (finance/actuarial science [7], communication networks, biology and atmospherical sciences [8]) as well as the investigation of the robustness of ridge regression when standard noise models are violated.\n\n**Assumption 2.1 and relevant kernels**\n\nAssumption 2.1 is quite standard in the sense that it is fundamental in \nclassical work for kernel ridge regression that we build upon [3] and subsequent analyses in the literature (see e.g. [2] and references therein).\nIn particular, it applies to commonly used continuous radial kernels on $R^d$ such as the Gaussian kernel and the Matèrn kernel. However, it is noteworthy that it only applies to the mentioned polynomial kernels when the input domain is bounded (or more generally when the distribution of $X$ has compact support). For unbounded covariate distributions, the boundedness assumption is *generally violated for polynomial kernels*. We added a remark to the paper that clarifies the applicability of Assumption 2.1. \n\n**Computational complexity**\n\nThe computational complexity of the ridge regression estimate is *entirely unaffected by the distribution of the data*, in particular by the assumption of heavy-tailed noise.\nIt is dictated by a convex program in dual form [1, Example 11.8] which is often solved by inverting the regularized kernel matrix [3, Prop. 8]. We added a sentence highlighting the numerical evaluation of the empirical estimate after line 156 for completeness.\n\n**Other regularization methods**\n\nCurrently, the approach only applies to the Tikhonov regularization method. We are working on a direct extension to the family of *spectral regularization methods*, which includes for example truncated SVD and Landweber iteration (which translates to a fixed learning rate gradient descent in this case) [9]. This requires some modifications of our proofs, but allows to work in the same framework. The LASSO penalty seems to require more work and a slightly adjusted framework, but this is definitely an interesting direction for future research.\n\n**Extension of the results to $q \\leq 3$**\n\nWe believe this is an important point. The answer is split into two distinct cases.\n\n*First case:* $2 \\leq q \\leq 3$. The real-valued Fuk-Nagaev inequality is valid for $q >2$. We hence believe that our Hilbert space version uses suboptimal truncation arguments and can be extended to $q>2$ by adopting more precise arguments [5] to the infinite-dimensional setting. The remaining parts of our proofs (i.e. balancing the bias and variance) allow for the case $q>2$, leading directly to the desired results in if the concentration bound can be generalized. We further believe that the value of the constants $c_1$ and $c_2$ can be made more precise. We are currently working on this.\n\n*Second case:* $q < 2$. When $\\varepsilon$ does not admit a second moment, the response $Y = f_\\star(X) + \\varepsilon$ does also not necessarily admit a second moment and the squared loss is not guaranteed to be well defined. In such a case, our approach and the Fuk-Nagaev inequality would not apply and other losses such as the Huber loss or Cauchy loss would be required to ensure finiteness of the loss, leading to a different type of analysis [4]. In this setting however, exact optimality is still unclear as far as we are aware. Also note that our rates are faster than the rates in [4] whenever $q>3$.\n\nWe added a “Extensions and Limitations” paragraph to end of the introduction to highlight these facts for the reader.\n\n**Technical comparison to Zhu et al. (2022)**\n\nThe authors of the above paper use a *real-valued* Fuk-Nagaev inequality to bound the complexity of stochastic gradient descent for ordinary (e.g. linear and unregularized) least squares in finite dimensions. The only technical similarity to our paper is the application of a Fuk-Nagaev type inequality to provide tail estimates for the noise.\n\nIn particular, our technique differs from their analysis in the following ways:\n\n(i) We combine concentration arguments with operator perturbation theory in the context of a linear inverse problem, while Zhu et al. perform an analysis of the SGD iteration via a martingale decomposition.\n\n(ii) Zhu et al. operate in a strongly convex setting with a nonzero lower bound on the smallest eigenvalue of the covariance matrix (see their Assumption 2). Our covariance operator is compact and infinite-dimensional and hence not allowing for such a bound. Consequently, we need to express the hardness of the learning problem as a source condition to obtain rates. \n\n(iii) We derive minimax optimal rates while Zhu et al. focus on the general sample complexity and the transition between subgaussian and polynomial confidence, not explicitly discussing details related to optimality.\n\n**References**\n\n[1] I. Steinwart and A. Christmann. Support Vector Machines (2008).\n\n[2] S. Fischer and I. Steinwart. Sobolev norm learning rates for regularized least-squares\nalgorithms. JMLR (2020).\n\n[3]  F. Cucker and S. Smale. On the Mathematical Foundations of Learning. Bulletin of the AMS (2001).\n\n[4] H. Wen, A. Betken, and W. Koolen. On the robustness of kernel ridge regression\nusing the Cauchy loss function, arxiv.org/abs/2503.20120 (2025).\n\n[5] E. Rio. About the constants in the Fuk-Nagaev inequalities. Electronic Communications in Probability (2017).\n\n[6] V. Yurinsky. Sums and Gaussian vectors (1995).\n\n[7] P. Embrechts, C. Klüppelberg, and T. Mikosch. Modelling extremal events: for insurance and finance (1997).\n\n[8] J. Nair, A. Wierman, and B. Zwart. The fundamentals of heavy tails. Properties,\nemergence, and estimation (2022).\n\n[9] H. W. Engl, M. Hanke, A. Neubauer. Regularization of Inverse Problems (1996)."}, {"review_id": "SPioWlinmf", "reviewer": "Reviewer_JkXL", "summary": "This paper investigates the performance of ridge regression in reproducing kernel Hilbert spaces under heavy-tailed noise conditions, where the noise has only finite higher moments. The authors derive excess risk bounds for ridge regression consisting of subgaussian and polynomial terms, demonstrating that the dominant subgaussian term allows for convergence rates previously only achieved under subexponential noise assumptions. The results show that the derived rates are minimax optimal under standard eigenvalue decay conditions, proving the robustness of regularized least squares against heavy-tailed noise. The analysis relies on a Fuk-Nagaev inequality for Hilbert-space valued random variables.", "questions": "1.\tWhy isn’t least squares commonly used in practice under heavy-tailed conditions? Providing some insightful remarks would be beneficial.\n\n2.\tHow do the derived rates compare to those of robust regression methods (e.g., Huber loss) under the same noise conditions? \n\n3.\tThe distinction between subgaussian and polynomial regimes is insightful. Are there practical guidelines for choosing the regularization parameter in each regime?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Strengths\n\n1. The use of the Fuk-Nagaev inequality is innovative and well-justified.\n\n2. The results cover both capacity-independent and capacity-dependent settings, offering a comprehensive view of the problem.\n\n3. The work has significant implications for robust statistical learning, as it shows that optimal rates can be achieved even with heavy-tailed noise.\n\nWeaknesses\n\n1. While the theoretical contributions are strong, the paper lacks empirical validation. \n\n2. The comparison to related work may lack sufficient detail (e.g. [37-38]) and may be unclear to non-experts.\n\n3. A discussion of practical implications is absent. How do the results inform the choice of loss functions in the presence of heavy-tailed noise?", "was_revised": true, "final_justification": "I thank the authors for addressing my previous concerns. This paper offers valuable insights and contributes significantly to the field of robust learning, and I suggest its acceptance.", "rebuttal": "Thank you very much for the review of our manuscript, the insightful comments and the encouraging endorsement of our work.\n\nWe have addressed all of your points and edited the manuscript accordingly. We comment on each individual point below.\nPlease note that we also refer to our replies to the other reviewers, as we did not want to redundantly list details and references to existing work regarding similar questions.\n\n**Empirical validation**\n\nWe agree. Just after the submission of this paper, we completed numerical evaluations which compare heavy-tailed and light-tailed models in terms of their quantile functions of the excess risks.\nThe results fully align with the excess risk distributions described by our upper bounds and confidence regimes. Please refer to our answer to **Reviewer AM9J** for the details and the setup of the empirical experiments.\nThe experiments will be included in the final paper using the additional space.\n\n**Comparison to other results, rates and losses**\n\nWe added an extended discussion of kernel machines with other losses in the introduction. We already briefly touched upon robust kernel regression with the Cauchy loss [1], for which slower rates than ours have been derived. However, it is very important to note that the Cauchy loss can be applied to the scenario $q<2$, in which case the squared loss is undefined and the general integral operator approach with squared loss does not apply.\n\nFor general convex and Lipschitz losses (including Huber loss), we are aware of the family of results described in Chapters 6 & 7\nof [2], which derive rates under boundedness/loss clipping assumptions *not covering heavy-tailedness of the losses*. These rates are are generally not optimal (see the discussion of the rates [2, p. 268] and a related the derivation of optimal rates for squared loss with bounded noise [3]). Please note that the so-called *approximation function* used in this context can be directly related to our source condition [3]. Additionally, the rates in the capacity-independent setting are generally slower than ours either by a factor in the exponent or a logarithmic term in $n$. From our viewpoint, our work motivates the derivation of optimal rates for these losses *without clipping or bounded noise assumptions* by combining the above approaches with similar applications of a Fuk-Nagaev type inequality, as no results seem to be available for these cases.\n\nWe also explain the connection between our capacity assumptions and the mentioned work on heavy-tailed empirical risk minimization and the entropy conditions [37-38] in more detail for the non-expert, as the eigenvalue decay in our work is directly linked to the entropy numbers [3].\nPlease also refer to our reply to **Reviewer rSYV** for the extension of our results to other loss functions.\n\n**Practical implications and usage of squared loss**\n\nWhile our work is of course of theoretical nature, we fully agree that the practitioner requires a presentation of the main insights created by our work. We add a paragraph summing these insights up:\n\n- squared loss is often not used in practice when one expects heavy-tailed noise as it is (i) sensitive to outliers when used *without regularization* (see related work section in the manuscript), and (ii) the population loss is generally undefined when the response only admits moments of order $q<2$ (\"very-heavy-tailed\")\n\n- however, *with regularization* and in the setting $q \\geq 3$, we show that it is (i) asymptotically optimal with the same regularization schedule as in the light-tailed setting, (ii) the achievable rates with optimal regularization are the fastest available as far as we are aware, (iii) in a *large sample setting*, the confidence behaviour is essentially subgaussian and allows to treat the problem like a light-tailed problem, (iv) in a *small sample setting*, stronger regularization is to be performed due to the impact of outliers.\n\nWe want to stress that deriving empirical parameter choice rules and more practical insights are very important and can be investigated in future work based on the theoretical foundation we aim to provide; see below.\n\n**Practical guidelines for choosing $\\alpha$ (empirical parameter choice rules)**\n\nWe agree that the practitioner requires consistent empirical choices of regularization parameters. \nWe see our current work as the theoretical foundation and a starting point for the derivation of these results. In fact, analogously to similar work for the light-tailed case, empirical parameter choice rules can be derived for example based on the so-called *discrepancy principle* (see e.g. [4,5]). Our upper bounds allow to insert various parameter choices rules constructed from data in order to investigate their efficiency. It is now of importance to understand how heavy-tailed noise affects the estimation of these parameter choices, potentially again by making use of a Fuk-Nagaev inequality.\n\n**References**\n\n[1] H. Wen, A. Betken, and W. Koolen. On the robustness of kernel ridge regression using the Cauchy loss function, arxiv.org/abs/2503.20120 (2025).\n\n[2] [1] I. Steinwart and A. Christmann. Support Vector Machines (2008).\n\n[3] I. Steinwart, D.R. Hush, C. Scovel. Optimal rates for regularized least squares regression. COLT (2009).\n\n[4] H. W. Engl, M. Hanke, A. Neubauer. Regularization of Inverse Problems (1996).\n\n[5] A. Celisse, M. Wahl. Analyzing the discrepancy principle for kernelized spectral filter learning algorithms. JMLR (2021)."}, {"review_id": "aTniPgXHO6", "reviewer": "Reviewer_rSYV", "summary": "The paper analyzes the performance of ridge regression in reproducing kernel Hilbert spaces (RKHS) when the observational noise has heavy tails, meaning it lacks exponential tail decay. Unlike prior work assuming subexponential noise (e.g., satisfying a Bernstein condition), the authors only require a finite number of conditional moments. They prove that ridge regression remains statistically robust under these weaker assumptions by using a Hilbert-space version of the Fuk–Nagaev inequality. They show that the convergence rates match known optimal rates under standard eigenvalue decay assumptions, thereby establishing that regularized least squares is minimax optimal even under heavy-tailed noise. The work generalizes existing theory and demonstrates that tight learning guarantees are achievable without strong tail assumptions, making kernel methods more broadly applicable in practice.", "questions": "- Have you considered or do you plan to validate your theoretical results with empirical experiments — particularly comparing performance under subgaussian vs. heavy-tailed noise?\n\n- The choice of the squared loss is not deeply discussed in the paper. Do you think your analysis—particularly the use of Fuk–Nagaev inequalities in Hilbert spaces—can be extended to learning problems with general convex loss functions? For instance, would similar results be attainable for regularized learning algorithms such as SVMs or other kernel-based methods involving Lipschitz or piecewise-linear losses?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: the paper is clear and well structured, results are explained and motivated precisely. The assumed setting is meaningful and tries to solve an interesting problem. The paper brings technical novelty to widespread ridge regression and the level of technical sophistication of the tools and analysis is high.\n\nWeaknesses: no important ones. Despite the paper being clearly theoretical, it would have been interesting to see some practical application or simulation under this heavy-tailed noise.", "was_revised": true, "final_justification": "I confirm, even more after the rebuttal, that this paper deserve in my opinion to be accepted.", "rebuttal": "We thank the reviewer for their for their positive and encouraging evaluation of our work, their time spent in reviewing our manuscripts well as their helpful feedback. We comment on your two questions below. \n\n**Empirical experiments**\n\nWe evaluated a series of numerical simulations shortly after the submission as pointed out in full detail in the reply to **Reviewer AM9J**. In particular, we compare the empirical distributions of the excess risks for different parameter combinations (sample size, regularization parameter, distributional assumptions) in a light-tailed setting and a heavy-tailed setting. Our theoretical results are fully confirmed by these experiments: one can clearly distinguish the subgaussian confidence regime (corresponding quantiles of excess risk distributions of light-tailed and heavy-tailed models overlap) and the polynomial regime (quantiles of the excess risk distributions of the heavy-tailed model are larger). We present experiments in the final version of the manuscript using the additional space.\n\n**Other loss functions**\n\nWe agree with the reviewer that the implications of the choice of squared loss and the extension to other losses should be highlighted. We also see that this may lead to important future work. We added a remark to the manuscript that outlines the potential application of our ideas to other loss functions (also see the reply to **Reviewer JkXL** for a more detailed comparion of results based on bounded noise) and outline a potential direction below.\n\nAs an alternative to the integral operator approach, an *empirical process approach* has been proposed (see e.g. [1] for an overview) for kernel machines with more general losses. This approach can incorporate the eigenvalue decay to derive optimal rates [2], usually relying on boundedness or Lipschitz assumptions of the loss under the noise. In order to obtain optimal rates with unbounded (and in particular heavy-tailed) noise, these arguments might need to be combined with a (uniform) Fuk-Nagaev inequality over a ball of RKHS functions (potentially with a truncated loss, as demonstrated in the proof of the FN-inequality). As the empirical process combines the eigenvalue decay of the integral operator with an entropy argument, we believe that *repeating the trick for the polynomial excess risk component* as presented in our paper might generally be possible by replacing the effective dimension with a suitable entropy proxy. We hope that our work motivates the extension of the empirical process approach to unbounded and heavy-tailed losses in the future.\n\n[1] I. Steinwart and A. Christmann. Support Vector Machines (2008).\n\n[2] I. Steinwart, D.R. Hush, C. Scovel. Optimal rates for regularized least squares regression. COLT (2009)."}, {"review_id": "LbdyrUfEYl", "reviewer": "Reviewer_2L1C", "summary": "This paper studies the generalization performance of ridge regression under heavy-tailed noises,\nshowing optimal rates similar to that derived unde subexponential noises in the literature.", "questions": "1. Can you discuss the requirement of $q \\geq 3$ in Assumption 2.2? Can it be improved to $q > 2$?\n\n2. As mentioned in the paper, the typical assumption that the kernel is bounded leads to subgaussian concentration of the embedded covariates. Can the techiques in this paper be further applied to \"heavy-tailed\" kernels that is unbounded?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "## Strengths\n\n* This paper is well written and easy to read.\n* This paper extends the analysis of kernel ridge regression under general heavy-tailed noise, which is novel.  By showing the same optimal convergence rate as the sub-Gaussian noise case, the paper also shows the robustness of regularized least squares against heavy-tailed noise.\n* In terms of technical contribution, the application of Fuk–Nagaev inequality in this paper can also be useful in other kernel-related problems.\n\n## Weakness\n\n* Numerical simulations could be provided to validate the theoretical results and further demonstrate the methods robustedness, particularly for noises with different tail behaviors.\n\n* This paper does not provide practical ways of choosing the hyperparameter $\\alpha$ under different confidence levels, limiting the paper's real-world implications.", "was_revised": true, "final_justification": "The theory in this paper is solid and additional improvements are made during revision.\nI would like keep my opinion to accept this paper.", "rebuttal": "Thank you for the effort in reviewing our manuscript and the very encouraging feedback. We incorporated insights based on your questions and comments into our manuscript. \n\nAdditionally, we believe you pointed out *two important directions for future work* (empirical parameter choice rules and learning rates for unbounded kernels), which we think are now within reach based on the theory and tools we provide in the paper. In fact, we spent some time thinking about these ideas during the writing of this manuscript and highlight some of our ideas alongside general answers to your questions below.\n\n**Empirical experiments** (as highlighted by the other reviewers)\n\nWe definitely agree that basic numerical simulations confirming the behavior of our upper bounds will improve the paper.\nIn fact, as outlined in detail in our reply to **Reviewer AM9J**, we have completed a series of experiments shortly after the submission and compared the empirical distributions of the excess risks of the heavy-tailed and the light-tailed setting. Our theoretical results are fully confirmed by these experiments and we present them in the final version of the manuscript using the additional space.\n\n**Hyperparameter choice $\\alpha(n, \\delta)$**\n\nWe agree with the reviewer again. However, we see our work as a starting point for more practical results for kernel regression with heavy-tailed noise in the sense that we first answer the fundamental question *\"What is the optimal rate and how does the optimal (theoretical) parameter choice look like\"?*\n\nBased on our results, empirical parameter choice rules can now be derived analogously to the light-tailed setting based on the results and approach presented in the paper. \nA specific empirical parameter choice rule stemming from inverse problems is *Morozov's discrepancy principle* (e.g. [1]),\nwhich can be adapted to the noisy learning setting [2]. We plan to investigate this in future work, specifically also in the context of the polynomial confidence regime, which differs from the light-tailed setting. We added a corresponding remark on empirical parameter choice rules to the manuscript after the we introduce the optimal parameter choice for the capacity-free setting to make the reader aware of this fact. In particular, asymptotically as $n \\to \\infty$, rate optimal rules for the light-tailed setting are optimal for the heavy-tailed setting as well as demonstrated by our results. However, the empirical estimation of the involved quantities for the practical construction of these rules might be impacted by heavy-tailed noise, which is yet to be investigated. \n\n**Extension to $q> 2$**\n\nCurrently, the restriction $q \\geq 3$ stems from the assumption of the Fuk-Nagaev inequality, the rest of our proofs is compatible with the case $q> 2$. In particular, we believe that the original truncation argument used by [3] for the bound in normed spaces is suboptimal and the bound can be improved to $q > 2$ (as is the case for the original real-valued bound due to Fuk and Nagaev). We refer the reviewer also to our more detailed reply to **Reviewer AM9J**, who asked the same important question.\n\n**Unbounded kernels**\n\nThis is another good point which we believe can be tackled with our approach. Currently, our results rely on the fact that due to boundedness of the kernel, the concentration of the empirical covariance operator can be bounded conveniently based on the Bennett inequality. However, only assuming $E [k(X,X)^{s}] < \\infty$ for $s \\geq 3$ (or $s > 2$ given the discussion above) and applying the Fuk-Nagaev bound a second time seems possible as well. This step leads to a final bound with *two polynomial terms*, one based on $s$ (operator perturbation) and one based on $q$ (model noise). Incorporating similar arguments as in our current proofs to the additional polynomial term might lead to optimal rates as well. We believe this could be a promising first step towards general learning rates for unbounded kernels.\n\n\n**References**\n\n[1] H. W. Engl, M. Hanke, A. Neubauer. Regularization of Inverse Problems (1996).\n\n[2] A. Celisse, M. Wahl. Analyzing the discrepancy principle for kernelized spectral filter learning algorithms. JMLR (2021).\n\n[3] V. Yurinsky. Sums and Gaussian vectors (1995)."}]

Author rebuttal:

Meta-review: This work derives excess risk bounds of ridge kernel regression with Tikhonov regularization in a heavy-tailed noise setting with bounded first three moments. Notably, the analysis shows that in the large sample regime, the convergence rate behaves similarly in this heavy-tailed setting and in the light-tailed setting with bounded or subexponential noise. This implies a certain level of robustness of square loss to heavy-tailed noise, despite it not being a predominant choice to learn from heavy-tailed data. 

The provided analysis constitutes a significant advance from the previous results restricted to subexponential noise. The technical approach using Fuk-Nagaev inequality has the potential of being applied to future works, some of which were outlined during discussion with the reviewers and would be interesting to include in the final version. It was also suggested to provide a discussion on the practical implications of the analysis, to which the authors have responded with some remarks on the use of square loss in heavy-tailed noise setting and the choice of regularization parameter. A shared concern among the reviewers is the lack of empirical validation, in response to which the authors claimed to have obtained numerical results that match the behavior predicted by the analysis.
Decision: Accept (spotlight)