On Empirical Risk Minimization with Dependent and Heavy-Tailed Data
Authors: Abhishek Roy
Krishna Balasubramanian
Murat A Erdogdu
Venue: NeurIPS 2021 Poster (2021)
Keywords: non-iid learning
risk bounds
empirical risk minimization
concentration inequalities
small-ball method

Abstract: In this work, we establish risk bounds for Empirical Risk Minimization (ERM) with both dependent and heavy-tailed data-generating processes. We do so by extending the seminal works~\cite{pmlr-v35-mendelson14, mendelson2018learning} on the analysis of ERM with heavy-tailed but independent and identically distributed observations, to the strictly stationary exponentially $\beta$-mixing case. We allow for the interaction between the noise and inputs to be even polynomially heavy-tailed, which covers a significantly large class of heavy-tailed models beyond what is analyzed in the learning theory literature. We illustrate our theoretical results by obtaining rates of convergence for high-dimensional linear regression with dependent and heavy-tailed data.


On Empirical Risk Minimization with Dependent and Heavy-Tailed Data
Abhishek Roy"
Krishnakumar Balasubramanian'
Murat Erdogdu
Abstract
In this work, we establish risk bounds for the Empirical Risk Minimization (ERM) with both dependent and heavy-tailed data-generating processes. We do so by extending the seminal works [Men15, Men 18] on the analysis of ERM with heavy- tailed but independent and identically distributed observations, to the strictly sta- tionary exponentially β-mixing case. Our analysis is based on explicitly controlling the multiplier process arising from the interaction between the noise and the func- tion evaluations on inputs. It allows for the interaction to be even polynomially heavy-tailed, which covers significantly large class of heavy-tailed models be- yond what is analyzed in the learning theory literature. We illustrate our results by deriving rates of convergence for the high-dimensional linear regression problem with dependent and heavy-tailes data.
Introduction
Given random vector (X, Y) Fd x R. with joint distribution (X,Y) and class of closed, convex set of functions C L2(x), the objective in statistical learning theory is to find the best function in the set JF that maps the input X to the target Y. The quality of this mapping is measured by a user-defined loss function IR + R+ (0). The most well-studied approach for the above task is that of risk minimization, where the best function is defined as the that minimizes the expected loss over the set F:
argmin Plf = argmin E,, (x()) - FEF
JEF
The above problem requires the knowledge of the distribution which is typically unknown in practice. However, we are usually given observations Z, (X,, Y2) for i I,...,N. from the distribution ı which leads to the Empirical Risk Minimization (ERM) procedure defined as
argmin Puly argmin JEF
JEF N e(f(x) -
The convergence of the empirical risk minimizer f to the true risk minimizer f" is typically analyzed by considering the underlying empirical process, a topie which dates back to the seminal work of [VC71]; see also [VDVW96, vdGo0, BBM05, Ko106, Kol11]. In representative analysis in this
"Department of Statistics, University of California, Davis.abroy@ucdaviie edu. edu. Research of this author supported in part by NSFTRIPODS grant 19345194568
'Department Statistics, University of California, Davis. kbala@ucdavis, edu. Research of this author was supported in part by UC Davis CeDAR (Center for Data Science and Artificial Intelligence Research) Innovative Data Science Seed Funding Program.
Depaarmennt of Computer Science and Department of Statistical Sciences at the University of Toronto, and Vector Institute, erdogduëcs. toronto. edu. Research of this author was supported in part by NSERC Grant (2019-06167), Connaught New Researcher Award, CIFAR AI Chairs program, and CIFAR AI Catalyst grant
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

setting, a majority of the works assume the observations Z; are generated independent and identically distributed (iid) from म, and the analysis based on uniform concentration. However, there are important limitations associated with this approach, particularly due to the (Talagrand's s) contraction principle which naturally requires a Lipschitz loss function (see, for example, [L.T13, Corollary 3.17] or [Kol11 1, Theorem 2.3]). As a result, in order to work with standard (unbounded) loss functions such as squared-error loss or Huber loss, it is generally assumed that the range of f E F is uniformly bounded and/or the noise == Y f(X) is also uniformly bounded r-almost surely.
Several attempts have been made the literature to overcome the limitations of the standard ERM analysis. A significant progress was made by Mendelson [Men15, Men18], who proposed the so- called learning without concentration framework for analyzing ERM procedures with unbounded noise or loss functions. The approach is based on combination of small- -all type assumption on the input samples X,, along with developing multiplier empirical process inequalities under weaker moment assumptions. We refer the interested reader, for example, to [Men 7b, Men17a LM18, LRS15, GM20] for details. The aforementioned works, while relaxing the prior analysis of ERM to handle heavy-tailed data-generating process (DGP), still require the more stringent iid assumption for their analysis. This restricts the practical applicability of the developed theoretical results significantly. Indeed, heavy-tailed and dependent data appear naturally in various practical learning scenarios [BF89, JM01, DKBRO7]; however, theoretical guarantees are still missing.
Aiming to fill the above gap, we analyze ERM with convex loss functions (that are locally strongly-conve around the origin) when the DGP is both heavy-tailed and non-iid. We do so by extending the small-ball technique of [Men15, Men 88] to the strictly stationary exponentially B-mixing data. In the iid case, the interaction between the noise and the inputs is handled by an analysis based on multiplier empirical process. However, developing similar techniques in the non- iid case is fundamentally restrictive due to the limitations of the analysis based on empirical process. We side-step this issue for the non-iid case by directly making assumptions on the interaction, which allows for it to be either exponentially or polynomially heavy-tailed. For the exponentially heavy-tailed interactions, we leverage the concentration inequalities developed by [MPR1]] I]. For the polynomially heavy-tailed case, we develop new concentration inequalities extending the recent work [BMdIP20] to 3-mixing random variables. We illustrate our results in the context of ERM with sparse linear function class and stationary 3-mixing DGP under both squared and Huber loss.
Our Contributions:
Motivation: A natural question arises in this context: Why study ERM with convex loss functions when the DGP heavy-tailed? Firstly, convex loss functions cover large class of robust loss function that are tailored to deal with the heavy-tailed behavior present in the noise and/or input data. Some examples include the Huber loss [Hub92], conditional value-at-risk [RU02, RS06, MGW20, SY20] and the so-called spectral risk measures [Ace02, HH21]. While there exist studies for nonconvex loss functions suited for heavy-tailed input data (for example, [Loh such analyses are mostly in a model- based setting and focus estimation error. Secondly, while alternatives to ERM have also been proposed and analyzed in the literature for the i iid case (with the most prominent one being the median-of m-mnans framework and its variants [MM19, LM19, LL20, BM21J). it is not immediately clear how to extend such methods to the dependent DGP that we consider in this paper. We view our work as taking the first step in developing risk bounds for statistical learning when the DGP is both heavy-tailed and dependent.
The seminal work [Yu94] extended the analysis based on empirical process to the stationary mixing process using a blocking technique. [lr197] and [BR97] studied consistency of non-parametric regression methods under mixing and exchangeability conditions on the DGP, respec- tively. [Nob99] established lower bounds to achieving consistency when learning from dependent data. [SHS09] studied consistency of ERM with Z, being a-mixing (not necessarily stationary) process, when F is a reproducing kernel Hilbert space. More recently, [Han21] and [DT20] studied learnability under a general stochastic process setup. The works [AV90, BL99,, 1es Gam03] extend Valiant's 's Probably Approximately Correct (PAC) learning model to Markovian and related drifting DGP, assuming bounded loss function and/or noise to obtain rates of convergence. Furthermore, [ZCY12] and [HS14] analyzed ERM for least-squares regression (with bounded noise) with clipped loss functions and an a-mixing DGP. Rademacher complexity results for predominantly stationary dependent processes were developed by [MS1] 1] and [MRO8]. [RSS10] and [ALW13) 13] developed PAC- Bayes bounds in the non-iid setting. [RST15, RS developed notions of sequential Rademacher complexity to characterize the complexity in online nonparametric learning in the worst-case. More recently [DDDJ19, KDD+t 21] considered learning under deeendd data for specific models.
Related Works:

---

However, such works mainly rely on bounded loss functions in their analysis. Furthermore, [Mei00] and [AW 12] studied model selection for time series forecasting a possibly unbounded setup but do not consider conditional prediction and is limited to light-tailed cases.
Apart from the aforementioned works, the recent works [KM17, HW19, WL.220] are closely related to our setup as they consider rates of convergence of ERM under heavy-tailed and dependent DGP. In [KM17, Section 8]. generalization bounds are developed when Z, is an asymptotically stationary 9-mixing sequence. However, their conditions on the function class F are rather opaque and it is not clear if their method actually handles the heavy-tailed DGP that we focus on. [HW]9] considered a setup based on statistical model: for i = 1..... N. Y, fXX,,) +G,, with the following conditions: (i) e being independent of X,, (ii) X, is iid, and (iii) 6, is iid. For this setting, they assumed that the noise has a bounded p-th moment (with p 2 2) and F satisfies the standard entropy condition (see, for example [Ko106, Example 4)) with exponent a E (0,2) 2) and obtained convergence rates of the order ONN शंक + N 2+ .). Finally, [WLT20] provides an analysis of L1 L1-regularized ERM with quadratic loss and linear function class where the heavy-tailed behavior is induced by sub-Weibull assumption, and data dependency is characterized by a stationary 3-mixing condition. However, their analysis specializes to sparse linear function classes and their focus on parameter estimation error and ia-sam prediction accuracy.
2 Assumptions and Preliminaries
We assume that there exists a function S" E F that minimizes the population risk [[((J(X) Y) In what follows, we provide the conditions that require on the DGP, specifically, the exponentially 3-mixing condition, for characterizing the dependency among data points.
Definition ([Yu94]). Suppose that {Z=] is a strictly stationary sequence of random variables. For any i,j E Z U f-00, )0), let of denote the o-algebra generated by {Zo) Then for any posilive integer b, the B-mixing coefficient of the stochastic process {2:} 2 is defined as
B(b) sup E
sup AEO
B) B)
BE
The sequence {2,};- is said to be 3-mixing if ((b) + 0 as b + co. Furthermore, is said to be exponentially 3-mixing if there exist Po, $1, r 0 such that ((b) I Boexp(-B1b")) for all b.
The B-mixing condition is frequently used when studying non-iid DGP, and imposes a dependence structure between data samples that weakens over time. The coefficient 3(b) is a measure of the dependence between events that occur within b units in time. Indeed, 3-mixing is often used in the analysis of non-iid data in statistics and machine learning, [Vid13]. Before stating our assumptions formally, we present the following decomposition of empirical risk for a convex loss using Taylor's expansion:
N
N Σ
Pxly 2 16N
(1)
N
where & is a suitably chosen midpoint between f(X)) Y, and (X) & For quadratic loss functions ((t) = t², (E,) 2E, and (5) 2, Vi. At high level, establishing risk bounds boils down to proving a positive lower bound on the second term on the Right Hand Side (RHS) of (I), and a concentration result for the first term the RHS with high probability. We now introduce the precise assumptions we make on the DGP and the function class to formalize the above strategy. For the sake of clearer exposition, and then indicate the changes required to handle more general locally strongly-conve loss functions.
first introduce our assumptions in the context of quadratic loss
Assumption 2.1 (Squared loss). The DGP {2 and the function class F satisfy the following:
(a) S-mixing data. The process (2 is a strictly stationary exponentially 3-mixing sequence, ie.. 3(k) S exp(-ck"") ), for some c, > O, with strict stationary distribution n.
(b) Small ball condition. Let F C I2(T)) be closed, convex class of functions and define F - F = ( h : S. E F). Then, the function class F is such that there is T > 0 for which QF-=(2T) (2T) > O, where Qu(u)= infrem P (1/1) 2 ul[hllzaa.
3

---

(c) Deviations of interaction. The stationary noise E1 and the error (f (X1) satisfy either:
(i) For all f E F.an and Z1 n, for some 7/2 0 we have
TP (J (() E (G
--) 2 exp(1 1.)).
(2)
OR
(ii) For all f E FF, and Z₁ ~ n, for some 1/2 > 2, and > 0 we have
(I - --)(()))
- Es 100---) (xx)) 2 2) S at "2 92
(d) Heavy-tailddate-mizee trade-off. Under condition (c)-(i, 1/n = 1/m + 1/12 > 1.
Condition (a) above, exponentially 3-mixing data, has been assumed in various works, see for exam- ple [Vid13, WLT20, KM171, to obtain rates of convergence for ERM procedures in general. Indeed, (exponential) mixing assumption holds in several time-series applications. For example, [Mok88] showed that certain ARMA processes can be modeled as an exponentially 8-mixing stochastic process. Furthermore [VK06] showed that globally exponentially stable unforced dynamical systems subjected to vinite-variance continuous density input noise give rise exponentially mixing stochastic process; see also [FS12]. Condition (b), referred to as the well-known small-ball condition, has been previously employed in the iid case [Men15]. Intuitively, it models saaledsaisssssss by restricting the mass allowed near any small neighborhoods of zero; thus, forcing the tails to be necessarily heavy. To our knowledge, the small-ball condition has not been used under dependent DGP assumptions. Condition (c) is proposed in this work as a way to model the interaction between the stationary noise & and the stationary error (f (X)) For the iid setting, [Men15] modeled the interaction between & and (f (fff (X,) uniformly over the class of F via the multiplier empirical process and captured the complexity through parameter v (see (108) for the definition). This requires using symmetrization argument in the proof which is not applicable in the non-iid setting that we consider in this work. In addition, how different tail conditions on the data and noise affect the high-probability statement on the learning rate is not apparent from the parameter ON-- We revisit the relationship between our condition (in the context of iid observations) and the multiplier empirical process approach used in [Men15] in Section F. Finally, condition (d) models the relationship between the allowed degree of dependency and the allowed degree of interaction between & and (f (X1).
Next, we modify condition (c) in Assumption 2.1 for the case of general locally strongly-conve loss functions because now the interaction part involves (E) instead of & (recall the decomposition (1)).
Assumption 2.2 (Convex loss). When the loss function is locally strongly-conver around the origin and globally convex, condition (c) in Assumption 2.1 is modified as:
(c) Deviations of interaction. The stationary noise &1 and the error (f - (X1) satisfy either.
(i) For all f E F. and Z1 n, for some 1/2 we have
2 21) 2) PP P(((E))--)(( ((((E -
exp(1 - eexp1=1"m )m
(4)
or,
(ii) For all f feF. F.and Za n,, for some 7/2 2, and 0 we have ((C((E)) - -LV (1X s cl
(5)
Complexity Measures: We now introduce the complexity measures that play crucial role in characterizing the rates of convergence. The use of 3-mixing assumption enables us to define complexity measures based the blocking technique proposed by [Yu94], also utilized by the works of [MR08, KM17, WLT20J. We partition the training sample of size N, S = {2,} into two sequences of blocks S₂ and S.. Each block in S., and S, is of length a, and 6 respectively. S, and Sy. both are of length 14, i.e., plaa + b) = N. Formally, S, and Sp are given by
S. ( (0)
Z (a)
with z((") { (2)=11o+0)+1,- 1(t
S
7 7
(b)
(b)
7 (b)
with n000 (=((11(0+0)+at1) Z(1-1)( ((0 (6)
Based on this blocking technique, we require the following definition of Rademacher complexity.

---

Definition 2. Let {Xi]==1 be an itd sample from the strict stationary distribution т. Let DD be the (nit-L ball centered at f³. For every ? O, define
s m
W/(F MM(F-FF71) FF7) inf O:
sup
(x))
ST]]
hE(T
where {a are itd Rademacher variables taking values #1 with probability 1/2.
The quantity wy (H,,)) 7) provides a localized complexity measure for the function class F, and serves as a generalization of the standard Rademacher complexity in the non-i onn setting. For the case of locally strongly-convex losses, we need the following related measures of complexity.
Definition 3. For a function class H C (T) a sample of size N from a strictly stationary 3-mixing sequence with stationary distribution क satisfying Assumption 2.1-(a), and Cis S2 > 0, we define:
W1 (H, N. (1) = -inf {r > 0: E [|]G|| & STTN a0+ } and w2 w2 μ. (2) = (HL,
where μl Nut ||G]| suPhEh Gh, and {G₁, h E H) is the canonical Gaussian process indexed by H. with a covariance induced by (T(T). Moreover, we let
w - F, SI, (2) = max(wi (H, N, (1), we (2),
Note that in Definitions 2 and 3, the scaling is in terms of number of blocks μ instead of N. The number of blocks μ can be thought of as the effective sample size under dependency, and 7h oc, one has μ -> N. The term E [||c]] anrd] appearing in Definition 3 is termed as the localized Gaussian width and is also widely used complexity measure in the literature. Note that while in the case of quadratic loss function, the bound is in terms of local Raademacher-basee complexity measure, whereas in the convex case, we require both Gaussian and Rademacher-batee complexity measures to establish the bound, mostly due to technical reasons in the proof. An intuitive explanation for this has eluded thus far; see also [Men18, Lemma 4.2].
Concentration Inequalities for Heavy-tails: We now restate [MPRI1, Theorem 1]. in a form adapted to our setting below. This result is required to handle interactions of noise and input that satisfy condition (c)-(i of Assumption 2.1. is straightforward to check that the conditions required by [MPR11] are immediately satisfied under our Assumption 2. Indeed, while the results in [MPR11] ]] are stated for r-mixing sequences, condition (a) in Assumption 2.1 implies that the process [ is exponentially r-mixing [CG14], i.e., for a constant è' >> Okk) S e Lemma 2.1 ([MPRIIJ. Let [W1] be a sequence of zero-mean real-valued random variables satisfying conditions (a), (c)-(i), and (d) of Assumption 2. Define xM(x)) = (x A M) V (-M), for some M, where (r A y) min(x, y). and (x V 8) max(æ, y), and set,
V= sup sup (VA((*M(W.)) + > M21 i>0
|cov (ze (W.), 2M 2M (W)))).
(8)
Note that V is finite. Then, for any N 2 4, there exist positive constants C1 C2, Cs. and Ca depending only on c, m, T2 such that, for any t > O, we have
enll mn 04 E77
IP
sup
W 2 <
Ne ट
2aNV +e Ug exp
To deal with polynomially tailed interactions, i.e., under condition (c)-(ii of Assumption 2.1, we prove a concentration inequality for the sum of exponentially ß-mixing random variables with polynomially heavy-tails, which may be of independent interest.
Lemma 2.2 (Concentration for heavy-tailed (3mixxig sum). Let (W5b22 be sequence of zero- mean real valued random variables satisfying conditions (a) and (c)-(i)) of Assumption 2.1, for some m2 > 2. Then for any positive integer N, 0 I d1 < 1, and d2 2 0, and for any t > 1, we have,
20
N
N
22 261 Ing 1/2
sup JEN
W.
21
5
1-72 "
11+4d (ma-))
+ [2+
2e
(d2 log 1)
(10)
where c' 0 is constant.
5

---

Note that we do not need condition (d) of Assumption 2.1 for Lemma 2.2. Since the tail probabilities decay polynomially and the mixing coefficients decay exponentially fast, the effect of heavy-tail dominates and hence, there is no trade-off between ?/1 and 1/2- Lemma 2.2 extends the results of [BMdIP20] (on iid heavy-tailed random variables) to the exponentially f-mixing setting. The results of [BMdIP20] show that even for the iid case, the tail probability of the sum decays polyno- mially with t. We show that similar polynomial tail bounds can be obtained (up to log factors) even in the dependent setting. Furthermore, when B(k) 0, k >> O, the sequence is iid, in which case we recover the result of [BMdIP20]. We also remark that the above two results are crucial to derive our convergence rates for ERM. As a preview, when the DGP has only (2 + 5) -)-momnts, 6 > 0, Lemma 2.2 leads to risk bounds that hold with polynomial probability, whereas for sub- Weibull DGP (see Definition 4), Lemma 2.1 would lead to risk bounds that hold with exponential probability.
3 Main Results
In this section, we state our main results on the rates of convergence of ERM for both squared and convex loss functions. First, we consider the squared loss.
Theorem 3.1 (Rates of ERM with squared loss). Consider the ERM procedure with the squared error loss. For To < QQ((22)/8 setting μ = N" (H*Q((2)ee)) /4, for some constants c, d > and 0 < r < 1, we have, for sufficiently large N, and some positive constants C2 Cz. the following:
1. Under conditions (a). (b), (c)-(i), and (d) of Assumption 2.1, 0 0<10 1/41/44
- = (f
-N-ite, wwp wp F- -500-(((2)
)}
S max
(11)
16
with probability at least (for V as defined in (8))
1 1- 1= exp( exp(- - Ü2Nexp (-(N++2(70)))
(12)
2. Under conditions (a), (b), and (c)-(ti) of Assumption for 0 0<6 (1 1/ 1/12)/4
f S max { N (1- w F F- TQ PQ
(13)
16
with probability at least
2ng T+92
1 (1 exp(- -2
N
(14)
The detailed expression of the probabilities are provided in the Appendix (Theorem B.I).
Remark 1. To the best of our knowledge. the above result is the first result understanding rates of convergence of ERM with squared error loss functions with unbounded noise (as well as the loss) for heavy-tailed dependent data. For wide range of function classes F used in practice (see Section 4), the dominant term in the rate of convergence is - for < L <. 1/4. Furthermore, under the stronger condition (c)-(i) of Assumption 2.1, the risk bound holds with exponential probability, whereas under the weaker condition (c)-(ii), it holds only with polynomial probability.
We now show that when the small-ball condition in Assumption 2.1 is replaced with the stronger norm- equivalence assumption, also considered in [MZ20]. one could obtain improved rates. Examples of random vectors that satisfy the corm-equivalence conditions include multivariate student t-distribution and sub-exponentic random variables. We refer to Section 4 for illustrative examples.
Assumption 3.1 (Lp - L2 norm-equuivalence). Let F C LT( be a class of functions for some q 2 3. The function class J F- (f h: f.h E F} is Lp - L2 norm-equivalent for some > 2, if there exists an M1 > 0 such that, |/ |1, = (f hP dr) 1/2 < M/ Vh E F-F. Corollary 3.1. For the ERM procedure with squared error loss, under Assumptions 2.1, with condition (b) replaced by Assumption 3.1 with p = 8, for some 0 < 1 < 1/2 and r, p and To same as in Theorem for sufficiently large N, we have
| - 1" S max {N- (N 5,
(15)
with probability at least (for some constants T, and Ō2)
1- L- (2 expl exp(-N(1-r))n) Ü2Nexp (-(N21

---

Remark 2. In the model-based nonparametric regression setting (as discussed in Related Works) with X; allowed to be dependent on &, for all I...., n, but (X,, E.) being itd, in [HWI9, Proposition 3/ authors show a lower bound of N for some > 0, for sufficiently heavy-tailed input X, The above result provides an upper bound of similar order, for a more general setting in comparison to [HWI9]. We also remark that for Corollary 3.1, in the model-based setting. if we assume that &, is independent of X;, we have the same conclusion with just p instead of p = 8. Furthermore, note that in part 2 of Theorem 3. Lgg norm does not exist for 1/2 S 8. We have elaborated more on how this result compares Theorem 3. [Men later in Section F.
We now present our results for the class of convex loss functions that are locally strongly-convex.
Assumption 3.2 (Convex loss). The loss function é: IR + R+ (00 is a convex loss function which is strongly convex in the neighborhood of 0, i.e., there exists a l2 > O such that for any x, E [-|2, 12] E(y) 2 {2)) + ((x)((y x) + Pely x²) f2 some constant pe > O.
Theorem 3.2 (Rates of ERM with convex loss). Consider ERM with loss functions that satisfy Assumption 3.2. For To < c2Qr=> ty) t2 = ((Ko + 1/ (2)(()) setting
J Nmm/(+m)), for some constants c, c' > O, we for any N 2 4. the following:
1. Under conditions (a), (b). (c)-(i), and (d) of Assumption 2.1, for <<6 <
If 1' S &max/ {N {N~ 4+ 2wq(F F, F,N. 62) }
(16)
with probability at least (for V is defined in (8) and some positive co. c20, Czs)
- 1=C))=(27))~ www -coQu((27)) V. N Tー - -xNNexp (- -(N
2. Under conditions (a), (b), and (c)-(ii) of Assumption for 0 <<<< (1 - 1/m2)/4.
- f S max N (-1/mm) to (F F, S1,
(17)
with probability at least (for constants cy, C10, C2 > 0)
1 (xc)Q
1- Nm/0((m))) (onm/(0+m)))=000(((()))) ' /m1/0-m)) C15
2xy 1-72
N 11
(18)
To the best of our knowledge, the above result is the first result on understanding rates of convergence of ERM with convex loss functions with unbounded noise (as well as the loss) for heavy-tailed dependent data. The above result highlights the advantage of using robust loss function, e.g. Huber loss, over a quadratic loss function. For example, if (f - (X) has a sub-Weibull tail and the noise & has polynomial tail, one can still obtain risk bounds with exponential probability. This is because in this case E' (f()) (offf-f' (XX) can still be sub-Weibull for a suitable chosen ('(). Such a situation arises, for example, when there are outliers even if the data is light-tailed. With squared error loss, one won't be able to obtain a risk bound with exponential probability in this scenario. We will illustrate this in Section 4.3 through Huber loss, popular choice of robust loss function in robust statistics. Similar to the quadratic case, we also have an improved result when the small-ball condition is replaced with the norm-equivalence condition. Due to space constraints, we state and prove it in the Appendix B.2.
4
Illustrative Examples
We illustrate the results of Section 3 with three examples, based on sub- Weibull random variables and Pareto random variables, that are canonical models of heavy-tailed data in the literature.
4.1 Example 1:33miixnng Bub-Weibull DGP with Squared Error Loss
Here, we consider sub- Weibull random variables to model the heavy-tailed behavior in the DGP.
Definition 4 Bei-Weibull random vectors). A real-valued random variable X is said to be sub- Weibull with parameter 1) > O. if there are constants K₁, K₂ 0, such that we have IP ([X) t) S 2exp (-(t/Ki")), or equivalently ||X 1p = E // < Kap Based on this, a random vector X E Rd is said to be marginally sub- Weibull with parameter 1j > if each coordinate of X is sub- Weibull with n. We use X ~ sw(n) to represent this fact.
7

---

The above family of distributions define a rich class of random variables, allowing for heavier tails than cab-Gaussian tails (17 2) or sub-exponential tails (1) 1). Let (ór)iez+ be an iid sequence of d-dimensional random vectors with independent coordinates with 6; ~ SW(ns) Assume that the dependent input vectors are generated according to the model
X; = - + 8,.
(19)
where A E Rdxd with spectral radius less than 1. For simplicity, let A = ogla where og < 1, and {Yi liiz be a univariate response sequence given by Y; 0" Xx; + &. where 0 (R) belongs to the -n-orrm ball in R& with the radius Rt and {E: is an i.i.d sequence independent of X; Vi, and & ~ sw (Ti)) for < T < has independent coordinates. To proceed with learning framework, we consider ERM with squared loss and the function class F == FR (0.-) 0 denote the difference function class FR FR by HR. We verify conditions (a), (b), (c). and (d) of Assumption 2.1, and Assumption 3.1, provide the rate of ERM in this setting, and compare our result to that of [WLT20] in similar setting in Appendix C.
(R)). We
4.2 Example 2: f-mixing Pareto DGP with Squared Error Loss
Let Xx, denote the i-th coordinate of the vector X, Rd, We consider the process given in [Pi191]: For 1,2, ... dd 133 > 2 21, where i > 0 a small number, and 0, ,,,,, define
2 Xt-15
with probability 1/2
(20)
min 2 Xt- 813)
with probability 1/2
d,1=12,,.. is a sequence of iid Pareto random variables with the distribution L, (6; 13, d.) = 7/5 (1.0))))=--///01 (1 (d for 8 > 0, > 2 + 2t, and we write X ~ L, (1, a) to denote that X is Pareto random variable with parameters 17 and a. The survival function of ~ (1 d) is given by, P(6 > t) = (1 (dt)"a) for t > 0. Let X1, and X2, be two independent trails of the process in (20). Let (U,). be sequence of iid U|0,, 1] random variables. Now consider the process X = I S 1/2) X2.. 10, > 1/2). The marginal distribution of Xt,, is given by symmetric Pareto distribution, i.e.,
where
L( n5. d:) = 77s (s((118))
00 000 00, > 2 2t.
(21)
2 21 + (d)
Now, let {Yihezz is given by Y, = 0- T X; + uú where 0 E (R), R). as before. Let [u be an iid sequence of mean random variables independent of X; for all with heavy tails such that for all & > 0, IP (Iog) 2 t) S 1/(11 + -,4), 7/4 > 2 + 2t. Like in Example 4.1, we consider ERM with squared loss and the function class F = FR { (00,)) : 0 E (R)). where ( denotes the d-dimensional balball with radius R. We denote the difference function class FR FR by HR. We
show that conditions (a), (b), and (3)- of Assumption 2.1 hold here in the following section.
4.2.1 Verification of Assumption 2.1 for Example 4.2
[Pi191] shows that the AR(1) process given by (20) is strictly stationary if Xo,; (18. di), and Xo,: independent of each other for i 1,2, ...,.... d. The stationary distribution is given by (1s, d.). Let ग Xt, Xt..... ... Xx,)) be the joint distribution of Xe, .X,, for a set of time points &1, t2, ,,t, Now for any positive integer
+ ((Xett+) = =T((XI,, (U,, < 1/2) N2., 1(U,, > 1/2)}==) T ((X,,)E)))
(U, 1/2) - 82 1 > 1/2)
(22)
The second equality above follows from the fact XI, and X2,t are strictly stationary process and {U;} iid. So X, is a strictly stationary process with marginal distribution of X,,, given by symmetric Pareto distribution
77s (d(((18))==
[ax; 13. d,)
- 00 < 00, 13 2t.
(23)
2 + (d. md))
8

---

1/d, Without loss of generality we will assume that d1 S d2 S ... S da 1 Ko. and d1 2 C. for some constants Kn. C% > 0. is shown in Lemma 1 of [Ris08], that the AR(1) process in (20) is o-mixing with ((k) = k log (2 1), k = 2....... where c-mixing coefficients are defined as in [Bra0S]. We also have B(k) I d(k) S e- Since X, depends only on X1, X2,1, and U,, X12, and X2, are independent and exponentially B-mixing, and U, is iid, X₁ is also exponentially 8-mixing.
Since Y, depends only on X,, and U are iid, {(x, Y)) is a strictly stationary B-mixing
sequence with (kk S e- So condition (a) of Assumption 2.1 is true here.
Now we will verify condition (b) of Assumption 2.1. Let xxp denote || for p > 0. Then
d
E
00
(24)
im
where do = min; ox = 1.2...., d. Since X, ~ L(TS), for any 0g E IR we have 10.Xillm-o.s. I K1 K1 xx.; 0..../.....-- So.
d
10,1
K10x.m- 0.5. Di=1 di
10.1
110 x Xl1m 0.50 S K 0.5
x
(25)
di
07 σuy
Σi de
K.s
100 X 2-
(26)
00
Then from Lemma 4.1 of [Men15] we have that the condition (b) of Assumption 2.1 is true here.
Since v, and X; are independent, and [us] O. we have E [1,t X.] 0. Let 7/2 min(ns, 74). Then using Markov's inequality, for any E Hi and Vi, we have,
|1 me
( | (issas)
92
P ([1tt X, [ust xx]
T22
T
where dH = Ei=1 d. and for all i,j. ||u:ll oue and || Ila implies that condition (c)- of Assumption 2. is true in this setting.
xxmz/dj. This
Proposition 4.1. Consider the learning problem described in Section 4.2. Then with probability at least (14), we have,
If - 1" & max { (N (1-
d +.58) -1/22c (27) (2
CrR
1/2te]
The proof of Proposition 4.1 could be found in the Appendix D.
Remark 3. Note that the heaviness of the tail dominates the exponential f-mixing rate Tn in determining the rates of convergence. Observe that T22 - oo all the moments exist, and N-0-1/m3/444 - N -1/4++, This rate is the same as the one that we obtain under condition (c)-(i), although with weaker polynomial probability. Furthermore, the dimension dependency is polynomial here. On a related note, [2Z18] analyzes fr-regression with a truncated loss in the iid setting with the assumption T/2 > and gets /d/N rate with exponential probability. We point out that in the iid setting Medians Medians-of-mean of-mean method achieves the optimal rate with exponential probability under the stronger assumption that log d moments exist [LM19].
4.3 Example 3: B-mixing sub-Gaussian data and Pareto noise with Huber Loss
In this example, we consider Huber loss which satisfies Assumption 3.2:
12/2
if < Tn Th [t| TR//2
Ln, (1)
if 2 TT.
We now formally establish the benefits of using Huber loss when the noise & has a polynomial tail but (f (X) has sub-Weibull tail. Let fizz be an iid sequence of d-dimensional standard

---

Gaussian random vectors ó; (0, Ia). To compare the performance of ERM under Huber loss to that of squared loss, for simplicity, we allow X be Gaussian; but similar result will hold for sub-Weibull 5, Assume that the input vectors are generated according to (19) where A is d x d matrix with spectral radius less than 1. For simplicity, let A of la where of < [WZLL120] showed that this time series is stable, strict sense stationary. with X; ~ N(0, 1/(1 Ta) Let {Y. , be the response sequence given by Y; 0" X; + where 8 (R), -norm ball in Rd. Let (5:)__ be independent of X; for all i, and be an iid sequence of 0 mean random variables with heavy tails such that for all 1. > 0, P (IS.) 2 t) s 1 1/(1 + (*M), 7i > 2 + 2, and VAR(E) (E) S ag.
Set Th 30g. We verify the required assumptions for this example in the following section.
4.3.1 Verification of Assumptions for Example 4.3
Condition (a) of Assumption 2.1 and condition (b) of Assumption 2.2 are true here by the same
argument as in Example 4. 1. This also implies that Assumption 3.1 is true in this case for p = 8. Since we consider Huber loss, a lipschitz continuous loss, we have (E()) < min(({/2),, Th). Set Th = c11 (No + (a + 2R). As an immediate consequence of [VGNA20, Proposition 2.3], we have that condition (i)-(i) in Assumption 2.2 is valid here with 1/2 = 2. Note that if a sequence is exponentially 3 3-mixing, i.e., satisfies condition (a) of Assumption 2.1 with coefficient 1/2 > 0, then the same condition true for all lj < 1/1- So choosing 1/1 < 1/2 (112 - 1) we get Condition (d) of Assumption 2.1 is true.
Proposition 4.2. Consider the learning problem described in Section 4.3. Then, for some constant C1 > O, with probability at least
Cye 1- "T Nm/(U-mi)e cooe MI N C2NNex (- (NNN"))))
we have
Ilf 1f--flll, S max { (N- b+ Roo.///og/////// $
The proof of Proposition 4.2 could be found in the Appendix E.
Remark 4. In this setting, using squared loss would mean that condition (C)-fii) of Assumption 2.1 true. So, by part of Theorem 3.1, the obtained rate would be of order N-1/8 with polynomial probability given by (14), which is significantly worse than that of Proposition 4.2 with Huber loss.
5 Proof Sketch of Theorem 3.1 and 3.2
Recall the decomposition (I). The first and the last terms in the RHS of (1) are handled respectively by condition (b) and (c) of Assumption 2.1. The idea is to show that if for some f E F, llf - ll, is large, then with high probability Tj
(x,) 2 B (Lemmaa B. and Th := 2N 2N-1 EN Ef(f f - (X,) 2 B (see (67)) where B + > O. But since ff minimizes PxLf and f E PNLy S 0. So with high probability Ilf fl is small. In contrast to [Men15], we face two major challenges: 1- For the lower bound on Ti, the symmetrization argument used in the iid case (e.g. [Men15, Men18)) is not applicable under our dependency structure. 2- For the term T2. [Men15, Men18] use the complexity measure a (7, 5) (see (108)) in the iid case to control the noise-input interactions, which is not possible to do in setting; analysis to control T3 is different, through which we can show how different tail conditions on the data and noise affect the high-probability statements on the learning rate. The proof of Theorem 3.2 for the locally strongly-conve loss functions, follows a similar strategy although the technical details are more involved.
N E.
6 Conclusion
In this work, we analyzed the performance of ERM with squared and convex loss functions, when the DGP is both dependent (specifically, exponentially f-mixing) and heavy-tailed. We derived explicit rates using combination of small-ball method and concentration inequalities. We demon- strated the applicability of our results on a high-dimensional linear regression problem, and showed that our assumptions are easily verified for certain classes of sub-Weibull and Pareto DGP, Our results clearly show the benefits of using Huber loss over the squared error loss for ERM with heavy-tailed data in setting. For future work, we plan to study median-off of-nn based techniques and examine establishing similar rates of convergence for dependent heavy-tailed data.
10

---

References
[Ace02]
Carlo Acerbi, Spectral measures of risk: A coherent representation of subjective risk aversion, Journal of Banking & Finance 26 (2002), no. 7, 1505-1518. (Cited on page 2.)
[ALW13] Pierre Alquier, Xiaoyin Li, and Olivier Wintenberger, Prediction of time series by statistical learning: General losses and fast rates, Dependence Modeling (2013), no. 2013, 65-93, (Cited on page 2.)
[AV90] David Aldous and Umesh Vazirani, A Markovian extension of Valiant's learning model, Proceedings [1990] s1 Annual Symposium on Foundations of Computer Science, IEEE, 1990, pp. 392-396. (Cited on page 2.)
[AW12] Pierre Alquier and Olivier Wintenberger, Model selection for weakly dependent time series forecasting. Berouuli 18 (2012), no. 3, 883-913 (Cited page
[BBM05]
Peter L Bartlett, Olivier Bousquet, and Shahar Mendelson, Local Rademacher complexi- lies, The Annals of Statistics 33 (2005), no. 4, 1497-1537. (Cited on page 1.)
[BF89]
Graciela Boente and Ricardo Fraiman, Robust nonparametrie regression estimation for dependent observations, The Annals of Statistics (1989), 1242-1256. (Cited on page 2.)
[BL97]
Rakesh Barve and Philip M Long, On the complexity of learning from drifting distributions, Information and Computation 138 (1997), no. 2, 170-193. (Cited on
page 2.)
[BM21]
Daniel Bartl and Shahar Mendelson, On Monte-Carlo methods in convex stochastic optimization, arXiv preprint arXiv:2101.0799 (2021). (Cited on page 2.)
[BMdIP20]
Milad Bakhshizadeh, Arian Maleki, and Victor H de Pena, Sharp concentration results for heavy-tailed distributions, arXiv preprint arXiv:2003. (2020), (Cited on pages and 6.)
[BR97]
Patrizia Berti and Pietro Rigo, A Glivenko-Cantell Cantelli theorem for exchangeable random variables, Statistics & probability letters 32 (1997), no. 4, 385-391. (Cited on page 2.)
[Bra05]
Richard C Bradley, Basic properties of strong mixing conditions. survey and some open questions, arXiv preprint math/0511077 (2005). (Cited on page 9.)
[CG14]
Kacper Chwialkowski and Arthur Gretton, A kernel independence test for random processes, International Conference on Machine Learning. PMLR, 2014, pp. 1422- 1430. (Cited on pages 5 and 16.)
[Che07] Christophe Chesneau, A tail bound for sums of independent random variables: applica- tion to the symmetric pareto distribution. (Cited on page 36.)
[DDDJ19] Yuval Dagan, Constantinos Daskalakis, Nishanth Dikkala, and Siddhartha Jayanti, Learning from weakly dependent data under Dobrushin's 's condition, Conference on Learning Theory, PMLR, 2019, pp. 914-928. (Cited on page 2.)
[DKBR07] Murat Dundar, Balaji Krishnapuram, Jinbo Bi, and R Bharat Rao, Learning classifiers when the training data is not IID., IJCAI, vol. 2007, 2007, pp. 756-61. (Cited on page 2.)
[DP04]
Jérôme Dedecker and Clémentine Pricur, Coupling for r-dependent sequences and applications, Journal of Theoretical Probability 17 (2004), no. 4, 861-885 (Cited on page 15.)
[DT20]
A Philip Dawid and Ambuj Tewari, On learnability under general stochastic processes, arXiv preprint arXiv:2005. .07605 (2020). (Cited page 2.)
[FS12]
Amir-massoud Farahmand and Csaba Szepesvári, Regularized least-squares regression:
Learning from a B-mixing sequence, Journal of Statistical Planning and Inference 142 (2012), no. 2, 493-505. (Cited on page 4.)
[Gam03] David Gamarnik, Extension of the PAC framework to finite and countable markov chains, IEEE Transactions on Information Theory 49 (2003), no. 1, 338-345. (Cited on page 2.)
[GM20] Peter D Grünwald and Nishant A Mehta, Fast rates for general unbounded loss functions: From ERM to Generalized Bayes., Journal of Machine Learning Research 21 (2020), no. 56, 1-80. (Cited on page 2.)

---

[Han21]
Steve Hanneke, Learning whenever learning is possible: Universal learning under general stochastic processes, Journal Machine Learning Research (to appear) (2021).
(Cited on page 2.)
[HH21]
Matthew Holland and EI Mehdi Haress, Spectral risk-based learning using unbounded losses, arXiv preprint arXiv:2 2002100550416 (2021). (Cited on page 2.)
[HS14]
Hanyuan Hang and Ingo Steinwart, Fast learning from a-mixing observations, Journal
of Multivariate Analysis 127 (2014), 184-199. (Cited on page 2.)
[Hub92]
Peter Huber, Robust estimation of a location paraneter, Breakthroughs in statisties, Springer, 1992, pp. 492-518. (Cited on page 2.)
[9W19]
Qiyang Han and Jon Wellner, Convergence rates of least squares regression estimators with heavy-tailed errors, Annals of Statistics 47 (2019), no. 4, 2286 2319.. (Cited on pages and 7.)
[Ir197]
A Irle, On consistency in nonparametric estimation under mixing conditions, Journal of multivariate analysis 60 (1997), no. 1, 123-147. (Cited on page 2.)
[JM01]
Jiancheng Jiang and YP Mack, Robust local polynomial regression for dependent data, Statistica Sinica (2001), 705-722. (Cited page 2.)
[KDD*21] Vardis Kandiros, Yuval Dagan, Nishanth Dikkala, Surbhi Goel, and Constantinos Daskalakis, Statistical estimation from dependent data, International Conference on Machine Learning, PMLR, 2021, pp. 5269-5278. (Cited on page 2.)
[KM17]
Vitaly Kuznetsov and Mehryar Mohri, Generalization bounds for non- stationary mixing processes, Machine Learning 106 (2017), no. 1, 93-117. (Cited pages 3 and 4.)
[Ko16]]
Vladimir Koltchinskii, Local Rademacher complexities and oracle inequalities in risk minimization, Annals of Statisties 34 (2006), no. 6, 2593-2656. (Cited on pages and 3.)
[Ko111]
Oracle inequalities in empirical risk minimization and sparse recovery prob- lems, vol. 2033, Springer Science Business Media, 2011. 1. (Cited on pages and 2.)
[LL20]
Guillaume Lecué and Matthieu Lerasle, Robust machine learning by median-of-meann theory and practice, Annals of Statistics 48 (2020), no. 2, 906-931. (Cited on page 2.)
[LM18]
Guillaume Lecué and Shahar Mendelson, Regularization and the small-ball method I: Sparse recovery, The Annals of Statistics 46 (2018), no. 2, 611-641. (Cited on page 2.) Gábor Lugosi and Shahar Mendelson, Regularization, sparse recovery, and median-of- means tournaments, Bernoulli 25 (2019), no. 3, 2075-2106 (Cited on pages and 9.)
[LM19]
[Loh17]
Po-Ling Loh, Statistical consistency and asymptotic normality for high-dimensional robust m-estimators, The Annals of Statistics 45 (2017), no. 166-8896 (Cited on page 2.)
[LRS15]
Tengyuan Liang, Alexander Rakhlin, and Karthik Sridharan, Learning with square loss: Localization through offset Rademacher complexity, Conference Learning Theory, PMLR, 2015, pp. 1260-1285. (Cited on page 2.)
[LT13]
Michel Ledoux and Michel Talagrand, Probability in banach spaces: isoperimetry and processes, Springer Science & Business Media, 2013. (Cited on page 2.)
[Mei00]
Ron Meir, Nomparametric time series prediction through adaptive model selection, Machine learning 39 (2000), no. 1, 5-34. (Cited on page 3.)
[Men15]
Shahar Mendelson, Learning without concentration, Journal of the ACM (JACM) 62 (2015), no. 3, 1-25. (Cited on pages 1, 2, 4, 7, 9, 10, 24, 34, 35, and 39.)
[Men17a]
Local global parameters: Breaking the Gaussian complexity barrier, Annals of statistics 45 (2017), no. 5, 1835-1862. (Cited on page 2.)
[Men 7b]
On multiplier processes under weak moment assumptions, Geometric aspects of functional analysis, Springer, 2017, pp. 301-318. (Cited on page 2.)
[Men18]
Learning without concentration for general loss functions, Probability Theory and Related Fields 171 (2018), no. 1, 459-502. (Cited pages 1, 5, 10, 29, and 33.)
[MGW20]
Zakaria Mhammedi, Benjamin Guedj, and Robert C Williamson, Pac-buyesian bound for the conditional value at risk, arXiv preprint arXiv:2006. 14763 (2020). (Cited on page 2.)
12

---

[MM19]
Stanislav Minsker and Timothée Mathieu, Excess risk bounds in robust empirical risk minimization, arXiv preprint urXiv:1910.07485 (2019). (Cited on page 2.)
[Mok88]
Abdelkader Mokkadem, Mixing properties of arma processes, Stochastic processes and their applications 29 (1988), no. 2, 309-315. (Cited on page 4.)
[MPRI1]
Florence Merlevède, Magda Peligrad, and Emmanuel Rio, A Bernstein type inequality and moderate deviations for weakly dependent sequences, Probability Theory and Related Fields 151 (2011), no. 3-4, 435-474. (Cited on pages 2 and 5.)
[MR08]
Mehryar Mohri and Afshin Rostamizadeh. Rademacher complexity bounds for Non-IID processes, Proceedings of the 21st International Conference on Neural Information Processing Systems, 2008, pp. 1097-1104. (Cited on pages and 4.)
[MS11]
Daniel J McDonald and Cosma Rohilla Shalizi, Rademacher complexity of stationary sequences, arXiv preprint aiv: I 106.0730 (2011) 1). (Cited on page 2.)
[MZ20]
Shahar Mendelson and Nikita Zhivotovskiy, Robust covariance estimation under 14-12 norm equivalence, Annals of Statistics 48 (2020), no. 3, 1648-1664. (Cited on page 6.) Andrew B Nobel, Limits to classification and regression estimation from ergodic pro- cesses, The Annals of Statistics 27 (1999), no. 1, 262-273. (Cited on page 2.)
[Nob99]
[Pes10]
Vladimir Pestov, Predictive PAC learnability: A paradigm for learning from exchange- able input data, 2010 IEEE International Conference on Granular Computing, IEEE, 2010. pp. 387-391. (Cited on page 2.)
[Pi191]
RN Pillai, Semi processes, Journal of applied probability (1991), 461-465, (Cited on page 8.)
[Ris08]
Miroslav M Ristić, A generalized semi-pareto minification process, Statistical Papers 49 (2008), no. 2, 343-351. (Cited on page 9.)
[RS06]
Andrzej Ruszezyúski and Alexander Shapiro, Optimization of convex risk functions, Mathematics of operations research 31 (2006), no. 3, 433-452. (Cited on page 2.)
[RS14]
Alexander Rakhlin and Karthik Sridharan, Online non-paraettiic regression, Confer- ence on Learning Theory, PMLR, 2014, pp. 1232-1264 (Cited on page 2.)
[RSS10]
Liva Ralaivola, Marie Szafranski, and Guillaume Stempfel, Chromatic PAC-Bayes bounds for non-IID data: Applications to ranking and stationary 3-mixing processes, The Journal of Machine Learning Research 11 (2010), 1927-1956. (Cited on page 2.)
[RSTI5]
Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari, Sequential complexities and uniform martingale laws of large numbers, Probability Theory and Related Fields 161 (2015), no. 1-2, 111-153. (Cited on page
[RU02]
R Tyrrell Rockafellar and Stanislav Uryasev, Conditional value-at-risk for general loss distributions, Journal of banking & finance 26 (2002), no. 7, 1443-1471. (Cited on page 2.)
[SHS09]
Ingo Steinwart, Don Hush, and Clint Scovel, Learning from dependent observations, Journal of Multivariate Analysis 100 (2009), no. 1, 175-194. (Cited on page 2.)
[SY20]
Tasuku Soma and Yuichi Yoshida, Statistical learning with conditional value at risk, arXiv preprint arXiv:2002.08: 000022 (2020). (Cited on page 2.)
[VC71] Vladimir Vapnik and Aleksei Chervonenkis, On uniform convergence of the frequencies of events to their probabilities, Teoriya Veroyatnostei i ee Primeneniya 16 (1971), no. 2, 264-279 (Cited on page 1.)
[vdGoo] Sara van de Geer, Empirical processes in m-estimation, vol. 6, Cambridge university press, 2000. (Cited on page 1.)
[VDVW96] Aad W Van Der Vaart and Jon A Wellner, Weak convergence, Weak convergence and empirical processes, Springer, 1996, pp. 16-28. (Cited on page 1.)
[VGNA20] Mariia Vladimirova, Stéphane Girard, Hien Nguyen, and Julyan Arbel, Sub-Warr Weibull distributions: Generalizing sub-Gaussien and sub- sub-Exponential properties heavier tailed distributions, Stat 9 (2020), no. 1, e318. (Cited on pages 10 and 34.)
[Vid13] Mathukumalli Vidyasagar, Learning and generalisation: With applications to neural networks. Springer Science & Business Media, 2013. (Cited pages 3 and 4.)
13

---

[VK06]
Mathukumalli Vidyasagar and Rajeeva L Karandikar, A learning theory approach to system identification and stochastie adaptive control. Probabilistic and randomized methods for design under uncertainty, Springer, 2006, pp- 265-302. (Cited on page 4.)
[WLT20]
Kam Chung Wong, Zifan Li, and Ambuj Tewari, Lasso guarantees for B-mixing heavy- tailed time series, Annals of Statisties 48 (2020),
1124-1142 142.. (Cited on pages 3,
8, and 34.)
[WZLL20] Di Wang, Yao Zheng, Heng Lian, and Guodong Li, Higl--iiensionnl vector autore- gressive time series modeling via tensor decomposition, 2020. (Cited pages 10 and 34.)
[Yu94]
Bin Yu, Rates of convergence for empirical processes of stationary mixing sequences, The Annals of Probability (1994), 94-116. (Cited on pages 2, 3, 4, 18, and 25.)
[2CY12] Yongquan Zhang, Feilong Cao, and Canwei Yan, Learning rates of least-square regu- larized regression with strongly mixing observation, International Journal of Machine Learning and Cybernetics 3 (2012), no. 4, 277-283. (Cited on page 2.)
[ZZ18]
Lijun Zhang and Zhi-Hua Zhou, -rrrgesssion with heavy-tailed distributions, Proceed- ings of the 32nd International Conference on Neural Information Processing Systems, 2018, pp. 0884-10941 (Cited on page 9.)
14


Reviews:
[{"review_id": "jjvKFFGpSJ3", "reviewer": "Reviewer_ynYv", "summary": "The authors derive risk bounds for empirical risk minimization under heavy-tailed $\\beta$-mixing observations. They provide general bounds for convex, locally strongly convex, loss functions and tighter bounds for the squared loss. They give three illustrative models for which they provide explicit bounds, the most important one being the Huber loss for which they find a justification of its usage as a robust lost in presence of sub-Weibull noise distributions.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The contribution is timely and novel. The high level of technicalities makes the paper a though read, especially for a venue such as NeurIPS where the space is limited; a large portion of the bibliography refers to work published in Annals of Statistics, which could be a better fit for this kind of work.\n\nApart from the above point, there a few minor typos/presentation issues:\n* p.2 l.39: could you provide real world/practical examples of dependent GDP? You are here mostly referring to theoretical work.\n* p.2 l.42 and so on: you are using \"non-iid\" everywhere in the paper to refer to not independent but the the $Z_i$ are still identically distributed (as the DGP is supposed stationary). You thus shouldn't use \"non-iid\" instead of non independent DGP as \"non-iid\" could mean non-independent, non id or both.\n* p.2 l.44: the distribution is $\\beta$-mixing not the data.\n* p.2 l.70: PAC is not defined.\n* p.3 l.87: which $p^{th}$ moment? Any?\n* p.3 l.88: what is $\\alpha$?\n* p.3 Def 1: the notion of stationarity considered here should be made explicit.\n* p.3 eq. (1): shouldn't it be $P_N\\ell_f$?\n* p.3 l.106: $\\xi_i$ is nowhere defined in the paper.\n* p.3 l.108: RHS is not defined.\n* p.3 l.119: what is $\\xi_\\infty$?\n* p.3 Assumption 2.1: it is not clear that you will require either (c)-(i) or (c)-(ii), maybe add either after \"satisfy''?\n* p.5 l.165: \"we only require local ...' what do you require exactly? For them to exists? To be finite?\n* p.6 l.203: it should be (c)-(i) and not (3)-(i).\n* p.6 Corollary 3.1: does this hold for both (c)-(i) and (c)-(ii)?\n* p.6 l.233: \"our result''.\n* p.7 l.234: why introducing the notion of local convexity only now when it has been already used multiple time? This should be introduced the first time the notion is used.\n* p.7 l.246: what is a \"robust loss'' in this context? I guess that the authors have in mind the Huber loss studied later but this unclear at that stage.\n* p.9 l.316: \"similar result will hold''. Does it hold or will you prove it in future work? If the proof is not provided (I couldn't find it in Appendices) this significantly limits the claims of the authors and their capacity to prove the \"robustness\" of the Huber loss.\n* p.9 l.350: it is not clear how the results currently show the advantage of the Huber loss as Example 3 is limited to Gaussian (sw?) case. Please, modify the sentence to better reflect the precise contribution of the paper.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The main motivation, i.e., explaining the role of Huber loss as a robust loss for heavy tailed data, is not fully achieved as derivations are limited to Gaussian noise (which is restrictive, if relevant at all).", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "UhGOGtwjYzk", "reviewer": "Reviewer_MgVF", "summary": "The paper analyses empirical risk minimization over a locally strongly convex function class in the context where the data generating process returned non-IID data, and can be potentially heavy-tailed. The authors give specific realizations of their analysis to sparse linear function class.\n\nThis work aims to bridge the gap between analyses that handle IID data and heavy-tailed data separately.", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### Originality\nThe work extends previously known analyses in non-trivial directions.\n\n### Quality\nI believe the submission is technically sound to the best of my understanding. The authors don't discuss any apparent weakness in their analyses, or any scope of improvement. The work is a complete in the sense that the authors have studied a very specific problem (combination of heavy-tailed and non-IID data for locally convex losses) and address it.\n\n### Clarity\nThe submission is well organized, and is clearly written. However, the reader would benefit from the main messages of the propositions in this work. For instance, while the precision of the theorem statement in Theorem 3.1 is appreciated, but the presence of too many symbols somewhat obscures the essence of the theorem. A similar statement could be made with regard to the readability of Theorem 3.2; perhaps it would have been beneficial to add some remarks distilling the statement of the theorem (as done for Theorem 3.1). I definitely don't view this as grounds to rejecting the work, but this can immensely help with how accessible such results can be.\n\n### Significance\nDue to the non-triviality of this analysis, I believe it is significant to members of the statistical learning community. However, there is no apparent practical significance, as the authors analyse a commonly used and known methodology.\n\n-----\n\nAdditional detailed comments below:\n\n- Line 106: what is $\\xi\\_{i}$? Is it $Y\\_{i} - f^{*}(X\\_{i})$?\n\n- Is Assumption 2.1b equivalent to saying that there exists a function in $f \\in \\mathcal{F} - \\mathcal{F}$ such that $|f| \\geq 2\\tau ||f||\\_{L\\_{2}}$? I am confused about the probability of this event.\n\n- Is Assumption 2.1c roughly stating that probability of \"small\" deviations (exponentially) decreases faster than probability of \"large\" deviations (polynomially)? Could the authors give an example of a simple random variable that satisfies this specific condition for better intuition of the assumption?\n\n- In Assumption 2.1d, is it the case that $\\eta$ is fixed; in which case it is clear why that condition can be referred to as a \"tradeoff\".\n\n- In Definition 2 of the Generalized Rademacher complexity, could the authors elaborate about how this is an extension of the Rademacher complexity to non-IID  setting, as the definition states that $\\{\\tilde{X}\\_{i}\\}\\_{i=1}^{\\mu}$ is an IID dataset? Also could the authors comment on how one could expect $\\omega\\_{\\mu}(\\mathcal{F} - \\mathcal{F}, \\gamma)$ to vary with $\\mu$, or point to some results that discuss this?\n\n- In Definition 3: how do you define the supremum over Gaussian processes $G_{h}$?\n\n- In Lemma 2.1: what is the $\\vee, \\wedge$ notation? Is it is the minimum, maximum shorthand?\n\n- As the authors remark, the speciality of Lemma 2.2 lies in its generality, as setting one can recover existing results for the IID case from the statement of the lemma.\n\n- Based on my understanding, Theorem 3.1 tells us that for the the squared loss, the error between ERM and the true risk minimizer is atmost a constant (or decays with N, albeit slowly) with probability at least 1 - $\\delta$, where $\\delta$ is at most $O(N^r \\exp(-N^{1-r}) + N \\exp(-N^\\text{cons}\\_{1}))$ (when 2.1c-i is satisfied), and $O(N^r \\exp(-N^{1-r}) + N^{-\\text{cons}\\_{2}})$ (when 2.1c-ii is satisfied). Is this correct?\n\n- There is a typo on lines 203, 205: it should read \"conditions (a), (b), (c)-(i)\" (and \"(c)-(ii)\") respectively.\n\n- Example 4.1 is a very simple and interesting example, whereas example 4.2 seems to be slightly contrived. Could the authors provide some motivation to study either example: are they merely provided to show the generality of the proven results?\nIf so, the authors could have included some proof sketches for these examples and show how the original theorem have been directly utilized.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This is a primarily theoretical work, and there is no immediate potential negative societal impact arising from this work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5"}, "extra_text": {}}, {"review_id": "TUKzbO9xirW", "reviewer": "Reviewer_9G9p", "summary": "This submission is a technical paper, which is concerned with obtaining bounds for the Empirical Risk Minimization (ERM) procedure for regression, when the data is both heavy-tailed and dependent (non-iid).\nThe performance of ERM in the heavy-tailed context is by now fairly well-understood, in part thanks to the observation that two-sided concentration for the empirical risk is not needed to establish excess risk bounds for ERM, and that one-sided guarantee suffice (functions with large population risk have large empirical risk).\nThe authors' contribution is to extend previous results in the iid setting to the dependent (specifically, mixing or exponentially-mixing) setting.\nWhile both the heavy-tailed and dependent settings have been considered separately, this works combines these two cases.\n\nAs in the iid case, the analysis involves both obtaining lower isomorphic (small ball) estimates for the function class, and controlling the interaction between the noise and the functions in the class (the so-called multiplier inequality).\n\nThe main applications of the generic results obtained for square and convex loss (Section 3) are described in Section 4.\nFor regression over L^1 balls, the authors obtain bounds under square loss for both exponential and polynomial tails of the noise, as well as bounds for Huber loss under polynomially-tailed noise (but sub-Gaussian data).", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "In terms of quality, this seems to be a technically sound and reasonable paper. Due to a high number of papers to review, I did not check the proofs in the 30 pages of seemingly dense and technical appendix, but I did read the main text. \n\nThe authors could do a better job in terms of clarity, for instance in the way their bounds are stated. For instance, essentially all bounds are stated in the following way (simplifying a bit):\n\"with probability 1 - f(N) - exp (-N^{2i})\", the risk is bounded by max(g(N), N^{-1/2 + i})...\"\nwhich is a somewhat convoluted way of writing the bound (the dependence on the confidence is in the exponent 2i of the sample size N in the bound); it would be much more readable to write e.g. \"for delta < h(N), with probability 1-delta, the risk is bounded by max( {log(1/delta)/N}^{1/2}, l(N) )\".\n\nIn terms of significance, the motivation for studying the dependent case is not completely clear in the present version, and without some justification it could seem like a somewhat arbitrary extension of heavy-tailed statistical learning. However, this may be due to the fact that I am not familiar with the dependent setting. Perhaps this could be motivated by arguing that the (exponential) mixing assumptions hold for time series, when covariates are moving windows of present and recent variables, if this is true? If not, I feel some reasonable example or motivation would help.\n\nAlthough the paper seems to be mainly about combining techniques of the dependent case with those of the heavy-tailed setting, one aspect I did appreciate is that the authors provided an explicit control of the multiplier process under some precise assumptions on the noise-function interaction, a step which is not done in Mendelson's JACM paper.\n\nI wonder whether Neurips really is the right venue for such a paper. This is a technical contribution, combining techniques from different settings to obtain results when data is both heavy-tailed and dependent.\nIt is 40 pages long, with fairly technical proofs. Given ML conferences' reviewing model, it seems unlikely that this submission will be properly checked and reviewed. \nFrom the authors' perspective, this means that acceptance to Neurips would be meaningless for such a paper. From the perspective of the conference, it could be that this technical extension/combination paper would mainly appeal to a small fraction of the Neurips audience, given the nature of the contribution, the topic and the way the results are presented (although the latter can be remedied, e.g. by highlighting the results of Section 4 and simplifying their formulation).\n\nThis being said, I do think this work could be presented at Neurips, in spite of the seemingly less-than-ideal fit. I hesitated to put a higher recommendation (in spite of some reservations on the motivation and clarity), but prefer to first see how this submission is received by other referees.\n\nMinor comments:\n\n* The fact that the rates for square loss are worse under the small-ball than the moment equivalence (n^{-1/4} vs n^{-1/2}) is strange. Indeed, both conditions typically serve to obtain small ball estimates on the class, which they both provide (though the small-ball assumption should lead to a worse leading constant, involving the Q function). What is this worse rate due to? (the control of the multiplier term?)\n\n* The (polynomial) dependence on d in the sparsity bound of Proposition 4.2 is not very readable (is the exponent small or large?).\n\n* It should be clarified in Assumption 2.1 that conditions (2) and (3) are separate conditions (\"or\" rather than \"and\", with the understanding that 2 is stronger than 3).\n\n* Line 256: \"... sub-Weibull random variables and Pareto random variables, that are canonical models of heavy-tailed data in the literature.\"\nCalling sub-Weibull distributions heavy-tailed is a stretch, since they exhibit tails decaying exponentially in t. While the term 'heavy tails' does not have a formal definition, it is more suitable to describe heavier (e.g. polynomial) tails.\n\n# Update\n\nI thank the authors for their detailed response. Overall, I would maintain my initial evaluation: I think the paper can certainly be accepted, but also that it would substantially benefit from a significant revision, in particular in how the results are stated. In my opinion it would be in the authors' interest to do this for the sake of readability, regardless of whether the paper is accepted for presentation. This should not be interpreted as a strong criticism or reservation; in fact, I did hesitate to raise my score, but decided to stand by my initial evaluation after taking another look at the paper.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"ethical_concerns": "no", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "LDUgmitBknC", "reviewer": "Reviewer_v9BD", "summary": "The paper considers the performance of ERM on heavy-tailed and dependent data. It proves general convergence rates with a few illustrative examples.\n\nUpdate \n----\nI have read the author(s)' response to my review and maintain my rating. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality\n---\nThe problem considered by the paper is new. The setting of dealing with heavy-tailed *and* dependent data has not been studied in the literature. \n\n\nQuality\n---\nThis is a complete work with full set of theoretical results. I've read the main paper and some proofs in the appendix and do not notice any major issue.\n\nThe author(s) has acknowledged the assumptions and potential weaknesses of the work.\n\nClarity\n---\nThe writing is generally clear. However, I find some of the exposition in the main paper reads overly technical. It makes sense to provide more intuitions when applicable.\n\nA missing reference might be \"Learning from Weakly Dependent Data under Dobrushin’s Condition\" (COLT 19), where the dependence is modeled by graphical model assumptions. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "It would be nice if the author(s) could provide lower bound to complement their results. This is generally doable in the heavy-tailed statistics and small-ball method literature. I wonder if the author(s) have given any thought.\n\nAs this is a theory work, I believe it will not lead to negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper focuses on obtaining bounds for the Empirical Risk Minimization (ERM) procedure for regression, when the data is both heavy-tailed and non-iid/dependent.  This work combined both the heavy-tailed and non-iid case.  Reviewers were positive.  However, the work is rather technical, and they correctly point out that the authors would make the paper substantially more accessible to the typical NeurIPS reader if they spend time on incorporating reviewer suggestions for improving the presentation.
Decision: Accept (Poster)