Generalization  and Robustness of the Tilted Empirical Risk
Authors: Gholamali Aminian
Amir R. Asadi
Tian Li
Ahmad Beirami
Gesine Reinert
Samuel N. Cohen
Venue: ICML 2025 poster (2025)
Keywords: Tilted Empirical Risk
Generalization error
uniform bound
information theoretical bounds. unbounded loss function
heavy-tailed loss function
Primary area: theory->learning_theory
TL;DR: We provide generalization error upper bound on the tilted empirical risk with convergence rate $O(n^{-\epsilon/(1+\epsilon)})$ for unbounded loss functions under bounded $(1+\epsilon)$-th moment of loss function for some $\epsilon\in(0,1]$.

Abstract: The generalization error (risk) of a supervised statistical learning algorithm quantifies its prediction ability on previously unseen data. Inspired by exponential tilting, Li et al. (2021) proposed the {\it tilted empirical risk} (TER)  as a non-linear risk metric for machine learning applications such as classification and regression problems. In this work, we examine the generalization error of the tilted empirical risk in the robustness regime under \textit{negative tilt}. Our first contribution is to provide uniform and information-theoretic bounds on the {\it tilted generalization error}, defined as the difference between the population risk and the tilted empirical risk, under negative tilt for unbounded loss function under bounded $(1+\epsilon)$-th moment of loss function for some $\epsilon\in(0,1]$ with a convergence rate of $O(n^{-\epsilon/(1+\epsilon)})$ where $n$ is the number of training samples, revealing a novel application for TER under no distribution shift. Secondly, we study the robustness of the tilted empirical risk with respect to noisy outliers at training time and provide theoretical guarantees under distribution shift for the tilted empirical risk. We empirically corroborate our findings in simple experimental setups where we evaluate our bounds to select the value of tilt in a data-driven manner.

bounds on Generalization and Robustness of the Tilted Empirical Risk
Gholamali Aminian'
Amir R. Asadi Tian Li
Ahmad Beirami Gesine Reinert 15 Samuel N. Cohen 16
Abstract
mial linear regression and naive Bayes classifiers (Calafiore
et al., 2019; Murphy, 2012; Williams & Barber, 1998), Li et al. (2021) propose the tilted empirical risk (TER) for su- pervised learning applications, such as classification and regression problems. Li et al. (2021; 2023a) showed that tilted empirical risk minimization (TERM) can handle class imbalance, mitigate the effect of outliers, and enable fair- ness between subgroups. Different applications of TERM have been explored, e.g., differential privacy (Lowy & Raza- viyayn, 2021), semantic segmentation (Szabó et al., 2021), noisy label self-correction (Zhou et al., 2020), and off-policy learning and evaluation (Behnamnia al., 2025). In this paper, we corroborate the empirical success of the TERM framework through statistical learning theory.
The generalization error (risk) of a supervised sta- tistical learning algorithm quantifies its prediction ability on previously unseen data. Inspired by exponential tilting, Li al. (2021) proposed the tilted empirical risk (TER) as non-linear risk metric for machine learning applications such as classification and regression problems. In this work, we examine the generalization error of the tilted empirical risk in the robustness regime un- der negutive tilt. Our first contribution is to pro- vide uniform and information-theome the filted generalization error, defined the dif- ference between the population risk and the tilted empirical risk, under negative tilt for unbounded loss function under bounded (1 + e)-th moment of loss function for some e E (0, 1] with a conver- gence rate of O(n where n is the number of training samples, revealing a novel application for TER under no distribution shift. Secondly, we study the robustness of the tilted empirical risk with respect to noisy outliers at training time and provide theoretical guarantees under distribution shift for the tilted empirical risk. We empirically corroborate our findings in simple experimental setups where we evaluate our bounds to select the value of tilt in data-driven manner.
A central concern in statistical learning theory is under- standing the efficacy of a learning algorithm when applied to test data. This evaluation is typically carried out by in- vestigating the gemeralization error, which quantifies the disparity between the performance of the algorithm on the training dataset and its performance on previously unseen data, drawn from the same underlying distribution, via a risk function. Understanding the generalization behaviour of learning algorithms is one of the most important ob- jectives in statistical learning theory. Various approaches have been developed for empirical risk (Rodrigues & EI- dar, 2021), including VC dimension-based bounds (Vap- nik, 1999), tability-based bounds (Bousquet & Elisseeff, 2002b), PAC Bayesian bounds (McAllester, 2003), and information-thherees bounds (Russo & Zou, 2019; Xu & Raginsky, 2017). This paper focuses on the generalization and robustness of the tilted empirical risk (tilted generaliza- tion error) of learning algorithms. Our contributions are:
1. Introduction
Empirical risk minimization (ERM) is popular framework in machine learning. The performance of the empirical risk (ER) is affected when the data set is strongly imbalanced or contains outliers. For these scenarios, inspired by the log seg-sum-expponntiall operator with applications in multino-
In Section 3, we provide upper and lower bounds on the tilted generalization error under unbounded loss functions for the negative tilt with bound via uniform and celemmation-thhoetttie approaches and establish the convergence rate of O(n ((==/((++e)) for some E (0, 1].
'The Alan Turing Institute, London, UK SStatsstical Laboratory, University of Cambridge, Cambridge, UK* Computer Science Department, University of Chicago, USA 'Google DeepMind, USA 'Department of Statistics, University of Oxford, Oxford, UK 'Mathematical Institute, University Oxford, Oxford, UK. Corre- spondence to: Gholamali Aminian <gaminian @ ttrring.a..uk
In Section 4, we study the robustness of the tilted em- pirical risk under distribution shift induced by noise or outliers for unbounded loss functions with bounded
Proceedings of the nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
Behhaamii al. (2025) use the term log-sum-exponential, which the same as the tilted empirical risk studied herein.

---

Generalization and Robustness of the Tilted Empirical Risk
(1 (1+ moment assumption, for some E (0,1) and negative tilt, and derive generalization bounds.
In order to measure the performance of the hypothesis h, we a non-negative loss function e: H x 2 - RT.
We apply different methods to study the performance of our algorithms,, including uniform and cntrmaation-hheortttn ap- proaches. In uniform approaches, such as the VC-dimension and the Rademacher complexity approach (Vapnik, 1999; Bartlett & Mendelson, 2002). the hypothesis space H. is independent of the learning algorithm. Therefore, these methods are besorithmm-nndeeendenn
In Section 5, we provide data-driven approach to selecting the value of tilt for regression problems, with observed test errors corroborating the theoreti- cal bounds.
In Section 6, we study the KL-regularized TERM prob- lem under unbounded loss function with bounded sec- ond moment assumption and provide an upper bound the expected tilted generalization error with con- vergence rate ((n -) under unbounded loss function with bounded (1 + e)-th moment for some E (0, 1].
our results for these methods do not specify the learning algorithms.
Learning Algorithms: For cnpormation-thooeetiie ap- proaches in supervised learning, following Xu & Raginsky (2017), we consider learning algorithms that are character- ized by a Markov kernel (a conditional distribution) PH ss Such learning algorithm maps data set S to hypothesis in H. which is chosen according to PHis- This concept thus includes randomized learning algorithms.
2. Preliminaries
Upper-case letters denote random variables (e.g.. Z), lower-case letters denote the realizations of ran- dom variables (c.g., 2). and calligraphic letters denote sets (e.g., 2). All logarithms are in the natural base. The tilted expectation of a random variable X with tilting 7 is defined The set of probability distributions (measures) over a space X' with finite variance is denoted by P.)))
Notations:
2.2. Risk Functions
The main quantity are interested in is the population risk, defined by
as 1 log (og(((/x(((7)))
y
R(h, pb) :- E5 Z)}, h H.
Information measures: For two probability measures P and Q defined on the space X, such that P is abso- lutely continuous with respect to Q, the Kullback-Leible (KI.) divergence between P and Q is (T((Pl)) fx log (dP/dQ) dP.. If Q is also absolutely continuous with respect to P. then the symmetrized KL divergence is (P)lQ) == KL(PIIQ) + P). The mutual information between two random variables X and Y is defined as the KL divergence between the joint distribu- tion and the product-offmarginn distribution [(X;Y) == Xlx, @ Py), where Px & Py is the product of the marginal distributions. The conditional KL divergence between Py Py|x and Py over Px is KL(Pr|x Py IPx) ==
As the distribution μ is unknown, in classical statistical learning, the (true) population risk for E H is estimated by the (linear) empirical risk
R(h, S) = Σ E(h, Z.).
(1)
The generalization error for the linear empirical risk is given by
gen(h, R(h, pd) RR,,,S)-
(2)
This is the difference between the true risk and the linear empirical risk. The TER, non-linear empirical risk with tilt y (Li et al., 202 1), a.k.a. log-sum-exponentia estimates the population risk by
5x (L(PP|x==ll PPy (dPxdxxx)... The symmetrized KL infor- mation between X and Y is given by IsKL (X;Y) := (axy @ Py): see Aminian et al. (2015). The total variation distance between two densities P and Q is defined as TV(P, Q) = fx
log 1 (h, S) = 7 n Σ exp (7e(1, z.)))
2.1. Problem Formulation
The TER is an increasing function in the tilt parameter y (Li et al., 2023a, Theorem 1), and as ry -> O, the TER converges to the linear empirical risk in (1). In this work, we focus on negative tilt y 0. Inspired by Li et al. (2021), the primary objective is to optimize the population risk; the TERM is used in order to help the learning dynamics. For our analysis, we decompose the population risk as follows:
Let 5 = {2 be the training set, where each sample Z, = (X,, YY) belongs to the instance space Z == X x y: here X' is the input (feature) space and ) is the output (label) space. We assume that Z, are i.i.d. generated from the same data-generating distribution js. We also assume 7 ~ as an i.i.d. sample with respect to the training set.
A set of hypotheses H. has elements X + y E H. When Hi is finite, then its cardinality is denoted by card(H).
R(h, = R(h, (1, + (h,
(3)
tilted generalization error
tilted empirical risk
2

---

Generalization and Robustness of the Tilted Empirical Risk
where we define the tilted generalization error
entropic risk, and expected tilted generalization error by
gen == R(h,, RR S).
(4)
R(H, Pn (1) E Su (H, 2)},
(H,H,QHH.) := EQn.s s (.H,QHH)) :=
In learning theory, for uniform approaches, most works focus on bounding the linear generalization error gen(h, S) from (2) such that under the distribution of the dataset S, with probability at least (1 - 6), holds that for all h E H.
(11)
Σ exp( exp(y)((,, log (EQn.s! n - n ?
1
1 n
gen, (H,5) ( := EPH.s (gen, (H, (H,
genn(h, S)ll s g(),n)
(5)
where UHS E (PH @ pren P...s. In addition to bounds of the form (6), we provide upper bounds on the absolute value of expected tilted generalization error with respect to the joint distribution of and H, of the form
where g is real function dependent on 8 (0, and is the number of data samples. Similarly, for the tilted generalization error from (4), we are interested in finding bound ge 7) such that with probability at least 1 - 8, under the distribution of S,
gen, (H, S) S ge (n, 7),
gen, (h, S)] S 9e n, n,,,,
(6)
where Je is real function. We also introduce the non-linear expected generalization error, which plays an important role in deriving our bounds, as
where gr is a real function. We set h² h²( ==
arg minkeH R(h, (4) and (S) arg minnew R2 (h, S)- We use the following notations. The excess risk under the tilted empirical risk is
gen, (H, RH, 1 ((0) (, RR, (H, (12)
3. Generalization Bounds for Unbounded Loss Functions
C. (M) == R(NC((S) ( (R)R(((())))))))))))))) (p).
(7)
The expected TER with respect to the distribution of S is
In this section, we derive upper bounds on the tilted gen- eralization error via uniform and
approaches for negative tilt (y 0) under bounded (1 e)- th moment of loss function, for some E (0, 1]. with con- vergence rate of O(n ())+))) Regarding the bounded loss function, we also provide the tilted generalization error bounds via uniform and information-theorrtiooe approaches in Appendix H. Note that, with a bounded loss function, we can exploit the Lipschitz property of the logarithmic function. However, when dealing with unbounded losses, the loss function lacks the Lipschitz property, making it im- possible apply the same techniques used in the bounded case (see Appendix H).
Sn) = E sm (h, S)],
(8)
and the tilted (true) population risk is
Ry (h, 1 )n)
1 log E2
exp(( [xxp(>(()+22)))
(9)
Under the i.i.d. assumption, the tilted population risk is equal to an entropic risk function (Howard & Matheson, 1972). We also introduce the non-linear generalization er- ror?,a. as
Several works have already proposed some solutions to overcome the boundedness assumption under linear em- pirical risk (Haddouche & Guedj, 2022; Alquier & Guedj, 2018; Holland, 2019) via a PAC-Bayesian approach un- assumption. Furthermore,
gen (h, = (R,( -
(h,
(10)
der the bounded second- an upper bound on generalization error via VC-dimension and growth function is proposed in Cortes et al. (2019, Corollary 12) with convergence rate of ((lo((n) (((00)))==<((+0))
For ease of notation, we consider R., (h, 8n) ) = R, u).
Information-theerrtic Approach: For the information- theoretic approach, the hypothesis H is random variable under learning algorithm Markov kernel, i.c., Pris+ we take expectations over the hypothesis H. We denote the expected true risk, expected empirical risk. expected
In contrast, we derive bounds with a convergence rate of On -e(()e))). more detailed comparison provided in Section
"W refer to this as non-linear generalization emorr since non-linear transformation of the population risk, instead of the population risk, is used.
3.1. Uniform Bounds
The following assumption is made for the uniform analysis.
3

---

Generalization and Robustness of the Tilted Empirical Risk
Assumption 3.1 (Uniform bounded (1 + e>-th moment'). There is constant Ku E IR+ such that the loss function (H, Z) + ((H, 2) satisfies (h, 2)] S xite uni- formly for all h E H. and some é E (0, 1].
Combining Proposition 3.3 and Proposition 3.4, we derive upper bound the absolute value of the tilted general- ization error.
Theorem 3.5. Under the same assumptions in Propo- sition 3.4 and finite hypothesis space, then for n Z (4/r)' (1>>''<w'' "x+ +8/3{) log/2/6)) for 7 < O and with probability (xx((2)
The assumption on the (1 e)-th moment, Assumption 3.1, satisfied for example if the loss function is sub-Gaussiaa or sub-Exponential under the distribution f for all h E H. see Boucheron et al. (2013). Inspired by the approach of Behnamnia et al. (2025), which provides regret bound based on a tilted operator, we aim to analyze the generaliza- tion error of tilted empirical risk within a uniform approach. All proof details for the results in this section are deferred to Appendix D.
at least (1 (1-6), the absolute value of the titled generalization error satisfies
sup Igen, (h. S) NEH
(15)
2 2exp(11 (in)
2 2 1+r B())
4 4exp(11])
+
(1-61 1)l
3rl
For uniform bounds of the type (6), we decompose the tilted generalization error (4) follows,
+ +h/ ///m
where B(ö) log(card + log(2/5).
ghn S) = R(h, p)) Ry (h, (h +gen, (h, (h,S); S), (13)
Remark 3.6. For y x n -111(t++), n 2 (4x) +8/30) 1og(2/8)
_ <=exp( 2xx. and -1 < Y < 0, the upper bound in Theorem 3.5 gives theoretical guarantee on the convergence rate of (nn-s(11+)) Using TER with negative tilt can help to derive an upper bound on the absolute value of the tilted generalization error under the bounded (1 + e)-th moment assumption.
We first derive an upper bound on term 1 in the following Proposition.
Proposition 3.2. Under Assumption 3.1, for y < 0 and some 10, the difference between the population risk and the tilted population risk satisfies
The following Lemma establishes an upper bound on the excess risk of tilted empirical risk, expressed in terms of suPдEи (h,
0 S (1) - Ry (h, 80)) I ln 1t
(14)
Then, using Bernstein's 's inequality (Boucheron et al., 2013) and properties of the logarithm, we can provide upper and lower bounds on the tilted generalization error.
Lemma 3.7. The excess risk of the tilted empirical risk satisfies,
(,) S 2 sup Igen, S)].
(16)
Proposition 3.3. Given Assumption 3.1 for some E (0, 1], for any fixed h E H with probability at least (1 5), then the following upper bound holds on the tilted generalization error for y < and some e E (0, 1].
heH
Combining Lemma 3.7 with Theorem 3.5, an upper bound the excess risk of the tilted empirical risk can be derived (See Appendix D.1).
gen, S) < 2exp(1%1(s)) hyl
2p/114te2k +1 1og(2/8)
The theorems in this section assume that the hypothesis space is finite; this is, for example, the case in classification problems with a finite number of classes. If this assumption is violated, we can apply the growth function technique from Bousquet al. (2003); Vapnik ( (1999). In particular, the growth function can be bounded by VC-dimension in binary classification (Vapnik, 1999) or Natarajan dimension (Holden & Niranjan, 1995) for multi-class classification sce- narios. Note that the VC-dimension and Rademacher com- plexity bounds are uniform bounds and are independent of the learning algorithms. Furthermore, one can construct an e- net over the hypothesis space, thereby discretizing the space, In this construction, we select finite subset H' C R. such that for every h. E H, there exists a h/' E H' with | < r. By applying our finite hypothesis result to this discretized set and controlling the approximation error through the Lipschitz property of the loss function, we ef- fectively generalize our bounds to the continuous case. This
V
n
+ 4 eex((1/lng (ww) 12g(2/8) + |//s
3n/7l
Proposition 3.4. Given Assumption 3.1 for some e E (0, 1). there exists a Ç E (0,1) such that for n 2 (1) for any fixed h E H with probabil- (2 (2exp(2)Nu)
ity at least (1 - 5), and 7 < O, the following lower bound on the tilted generalization error holds,
gen, (h, 2 (xp(1t/kku)
1te log(2/0)
(1 - 5)
n
4 expp(1/ kmn. (log((18)) 311171(1- ()
NNte that we assume that higher order moments, larger than (1 + <), are unbounded.
4

---

Generalization and Robustness of the Tilted Empirical Risk
method is exemplified in (Xu & Raginsky, 2017), which demonstrates that "for uncountable hypothesis space, we can always convert it to finite one by quantizing the output of the smallest set H' such that for all h E H there is a h E H' with || - WIll S r, where the Lipschitz, maxi- mal inequality (Lemma 5.7 in (Vershynin, 2010)) is derived using a similar quantization technique.
(b) Ç 2 we exp((nle)) and n 2
21(H:S)
2 te
(c) <> 21 2111'- exp((1lm) and
21(H; 2 [
21(1:
> n
2 2(exp(7mm) - 2 [e
Then, the following lower bounds on non-linear expected generalization error hold,
3.2. Information- Bounds
In the information- -hommation-thcoreticc approach for the unbounded loss function, we relax the uniform assumption, Assump- tion 3.1, as follows.
-exp(h)(m)) / 1/ In((-())
if or (b) hold,
gen (H,S)
-xp([p]me) [(H:S) + 29/1ttt
Assumption 3.8 (Bounded (1 + e)-th moment). The learning algorithm PHIS, loss function E, and / such that there is constant Re E R+ with which the loss function 2H + {(H, 2) satisfies max (H, ()) Epssal t 2)) s Kg lt for some c E (0, 1].
(1-()
(c holds.
Using Proposition 3.9 and Proposition 3.10, we can obtain upper bound and lower bounds on the expected tilted gen- eralization error, respectively. Then, combining upper and lower bounds on expected tilted generalization error, we can derive the upper bound on the absolute value of the expected tilted generalization error in the following.
For our tefermation-theorrttiall analysis, we use the follow- ing decomposition;
gen gen, R(H, Pn p1) (H, PH 3
Theorem 3.11. Under the same assumptions as in Proposi- tion 3. 3.10, the following upper bounds on absolute expected tilted generalization error hold,
+ gen, (H,
(17)
+ (H, PH,s) EpH.s (H.
D 2n 11 CC()),
" if or (b) hold, D(M) ((HS)) + 24 ) C(1),
gen, (H,))
We can derive bounds on I3 and 14 in a similar approach to Proposition 3.2.
if(c) holds.
Then, we provide upper and lower bounds on the non-linear expected generalization error of the tilted empirical risk, gen, (H, under negative tilt. These results are helpful in deriving an upper bound on the absolute expected tilted generalization error.
where C(r) =hl""k te and D(7) exp(11lme) hi((-())
Convergence rate: Assuming 7 = O(n ((==))(++))) and n 2
(MP() then the upper bound in Theo- rem 3.11 has the convergence rate O(n ((n=</(++)). Note that the result in Theorem 3.11 holds for unbounded loss functions, provided that the (1 e)-th moment of the loss function exists for some E (0, 1].
Proposition 3.9. Given Assumption 3.8 and assuming that 2((H:S) S n holds, then the following inequality holds,
gen (H, exp(1)lme) h
2 20/ +e ((H;
n
The results in this section are non-vacuous for bounded (H: If this assumption violated, we can apply the individual sample method (Bu et al., 2020), chaining meth- ods (Asadi et al., 2018), or conditional mutual informa- tion frameworks (Steinke & Zakynthinou. 2020) to derive tighter upper bound for the expected tilted generalization error.
and if
21 1b
:z holds, then following inequality
holds,
exp(himm) (T(H; gen, (H.S) S
28/7|Lte
hl
n
2
Proposition 3.10. Under Assumption 3.8 for some E (0. 1), assume further that there exists E (0. 1) such that one of the following cases holds,
4. Robustness of TER
Previous experimental work by Li et al. (2021; 2023a) has demonstrated that tilted empirical risk with negative tilt
(a) ç S 2 2e uttt exp(lals)) and > 2 (/|(tss(-
( exp((2mm))
5

---

Generalization and Robustness of the Tilted Empirical Risk
(7 0) exhibits robustness against noisy samples and out- liers during training- In this section, we investigate the robustness of TER under distributional shift scenarios. In- spired by the concept of influence functions (Marceau & Rioux, 2001; Christmann & Steinwart, 2004; Ronchetti & Huber, 2009), we model distributional shift through distri- bution j E P(Z), which represents the effect of outliers or noise in the noisy training dataset S.
where B()) log(card(HH) log(2/6).
Using Lemma 3.7, we can derive an upper bound on excess risk under distribution shift.
Our approach can be extended to incor- porate other divergence measures that quantify distribution shift based on training and testing samples directly, rather than their underlying distributions. This is in line with meth- ods commonly explored in the domain adaptation literature (e.g., (Ben-David et al., 2006; Zou et al., 2024; Ye et al., 2021)).
Other Divergences:
Uniform Approach: Our robustness analysis of TER is based on the following assumption.
Assumption 4.1 (Uniform bounded second moment under pt. There is a constant K₂ E R+ such that the loss func- tion (H, 2) + {HH, Z) satisfies Ep [e (h, Z)] S xltc uniformly for all h H.
Comparison with ERM: Theorem 4.3 gives an upper bound on the tilted generalization error of TERM under distribution shifts, which is valid for all distribution shifts, Specifically, this upper bound depends on the total variation distance TV(p, ji), which is bounded for any distributions I and p. This robustness is attributed to the negative tilt and properties of the exponential function. In contrast, for ERM, we need derive an upper bound on the following term,
For our robustness analysis, we employ the following de- composition of the tilted generalization error,
gen, ch, (h, 9) R(h, pO) (h, p)) +gen, (h.
In + (h u) R2 (h,
(18)
Dif (i) == ( 2)] - 111--22-10 Bz 11(h, Z)
(21)
14
For unbounded loss functions, deriving an upper bound on Dif(u, (ú) in terms of total variation distance not feasible. While such bounds can be established using KL-divvegencc (L(ullĀ) under specific conditions (e.g., when the loss function is sub- Gab-saassian under the data lata-generating distribu- tion), these bounds may become unbounded for certain ju. In this context, TERM with negative tilt emerges as a robust solution, providing theoretical performance guarantees for distribution-shi shift under unbounded loss functions.
Using the functional derivative (Cardaliaguet et al., 2019), see also Appendix C, we can bound 14 as follows.
Proposition 4.2. Given Assumption 4. and Assumption 3.1, then the difference of tilted population risk under, (9), be- tween μ and jı is bounded as follows for all h E H.
[C(h, log Tog(Ezznl((() 2))) - (og (-
|)D| [C)
(19)
hl
(exp(I)(mx)) -xxp((()))))
TV( A))
Robustness vs Generalization: The term TV(U,)) sents the distributional shift cost (or robustness) associated with the TER. This cost can be reduced by increasing hy] However, increasing hy| also amplifies other terms in the upper bound of the tilted generalization error. Therefore, there is a trade-off between robustness and generalization, particularly for y < in the TER. Li al. (2021) also empirically observed this trade-off for negative tilt.
32 repre-
72
(Ku -Ka) Ks))
where C(h, 2) = exp(re(h, =xxp(()()))) Z)).
Using Proposition 4.2, we can provide upper and lower bounds on the tilted generalization error under distributional shift. Then, combining upper and lower bounds, we can derive an upper bound on the absolute value of the tilted generalization error under distribution shift.
Information-theerrtie Approach: Using a similar ap- proach, we can derive an upper bound on expected tilted generalization error under distribution shift. We make the following assumption.
Theorem 4.3. Under the same assumptions in Theorem 3.5
for some e E (0, 11, then for n 2 [41>)*+*<)++ +1)+++++++++)) log(2/8) expp(2ye_)
and y < O, and with probability at least (1- the absolute value of the tilted generalization error under distributional
Assumption 4.4. The learning algorithm P PHiis loss func- tion l, and μ are such that there is a constant Na e R+ with which the loss function (11, Z) + 2(H, 2) satisfies max (Er,, a [el+ (H, Eprop (H, Z))) I K for some e (0, 1].
shift satisfies
sup ggen, (h, S) NEH
(20)
lite
2 2exp(1)lms)
2 2c/ 1+ B(8)
4 exxp( (1)(),))))))))))))) B())
+ 3n/ 3///1(1 (1 - ()
(1 -c)m
Using Theorem 3.11 and similar results to Proposition 4.2, we derive an upper bound on absolute expected tilted gener- alization error under distribution shift.
TV ()) (cx((h)l(s)) -exp(171155)
+ +111sk2 1t te +
72
(NEu Ke)
6

---

Generalization and Robustness of the Tilted Empirical Risk
Theorem 4.5. Under the same assumptions as in Theo-
Idata The data-driven tilt based on optimization of (22).
rem 3. I and Assumption 4.4, the following upper bounds
R(haan (S). 1d): The population risk under the data-driven tilt solution where hyy (5) == arg milMneH A (h. 8).
on absolute expected tilted generalization error hold under distributional shift, if (a) or (b) hold,
The training dataset consists of 1,000 samples. The results for Gaussian and Pareto outliers reported in Table and Table 2, respectively. For the Pareto-outlier as distribu- tion with unbounded second moment, we observe better performance for the data-driven approach in comparison with ERM. Note that the variance of TERM and data-driven
exp(Iy/re) G(I(H: + +171K 17:(1 - () (x - -ex((11(x))
[H, (H, gen,
+ TV(,, it)
72
(Re kiat)
TERM in comparison with ERM has less variance as ex- pected. The details of the experiments are provided in Appendix G. More experiments for Linear regression as proposed in (Li et al., 2021) is provided in Appendix G.
Hist if (a) or (b) hold have ()) = 2002 2xitthl have, G(I(H; (( " Lic
where K Hit
/ + and if (c) holds, we
"
We can observe the same robustness and generalization in Theorem 4.5.
Table I: Logistic Regression with Gaussian Outliers: Re- sults averaged over three runs (n = 1, 000 samples), show- ing mean + standard deviation.
5. Data-driven Choice of Tilt
(()
R( ($). ja)
R( (S). ())
0.1%
0.00200
0.05
-14000
0.00
In this section, we provide a data-driven approach for choos- ing the tilt (7) based on theoretical results. It is noteworthy that the upper bound in Theorem 4.3 can be infinite for
17.8%
2.98
0. 05
0.22_..mm
4.91.0.00
0.16
35.0%
-3. 3..860ooco
0.30==o.0
0.20=0.002
52.555
2...co
0:1
0.28_0000
-1 11.03 aso
0.14__000
70.0%
- 1.233ac.co
0. 0.100000
0.18
-2 2.28 20.000
0.15..0.002
+ -oo and = 0 and a fixed n. Consequently, there must exist a E (-o0, 0) that minimizes this upper bound. To illustrate this point, consider the case where n - oo; here, the first and second terms in the upper bound, (20), would vanish. Thus, we are led to the following minimiza- tion problem:
Table 2: Logistic Regression with Pareto Outliers: Results
averaged over three runs (n 1, 000 samples), showing mean + standard deviation.
P
7"
REA,,(()).
R(heew(5))))
R(h
Yidat arg min [1t///2tt
0.1%
17.58%
- -1.40u0..c0
3.33
1.000ac.co
0.00
0.02:4.00
-0.70a0.000
-0.8820
0.0110
>E(-00.0) TV (i) k))) - exp((1/mx)) [na))
35.05%
-1.06
0.00ucc.co
0.01
-0.20.0.000
0.01 003
(22)
52.53%
- 1100 sco
0.01 1:
-1 1.0882
0.01
70.00%
0.800
6.00
0.02.4.000
-0.70...000
0.0110 000
72
(Ni Kia)
for which a solution Yd exists. As 7* decreases when TV(,, (1) increases, practically, this implies that if the train- ing distribution becomes more adversarial (i.e., further away from the benign test distribution), we would use smaller negative 7's to bypass outliers. Therefore, we can consider Yatta data-driven choice for the TERM problem. We consider a simple experiment to show the effectiveness of data-driven tilt, Taata-
6. The KL-Regularized TERM Problem for Unbounded Loss Functions
Our upper bound in Theorem 3.11 on the absolute value of the expected tilted generalization error depends on the mutual information between / and S. Therefore, it is of interest to investigate an algorithm that minimizes the regu- larized expected TERM via mutual information.
In this experiment, we consider the logistic regression setup described in Li et al. (2023a), adding a Gaussian or Pareto outlier dataset to the training dataset at different ratios (p) relative the training dataset. We evaluate the following values:
PHIS arg inf (H, (H,SH)) + S(H:S), (23) PHIS
where a the inverse temperature. As discussed by Xu & Raginsky (2017); Aminian al. (2023), the regularization problem in (23) is dependent on the data distribution, Ps. Therefore, we relax the problem in (23) by considering the following regularized version via KL divergence,
y*: The optimal tilt based on grid search
The population risk under the optimal TERM solution where hn, ky)(
R(h,,- (S),
P PAs = arg inf R. PH.s) PRis
(24)
arg minneH R2 (h,
R(hers ($), n): The population risk under the ERM solu- tion where h (5) == arg minkeR R(h, S).
1
KL Ps))
7

---

Generalization and Robustness of the Tilted Empirical Risk
|Ps) and TH is a prior distribution over hypothesis space H. All proof details are deferred to Appendix F.
where 5( S KL(PHIS|TTH Ps))
error of the Gibbs posterior, it requires the strong assump- tion of sub-Gaussian loss functions. In contrast, we achieve the same (11/n) convergence rate under the weaker con- dition of bounded second moments (when = 1) for the tilted Gibbs posterior. Additionally, our analysis extends to loss functions with bounded (1 + e)-th moments for some E (0, 1], a scenario not addressed in the Gibbs posterior framework.
Proposition 6.1. The solution to the expected TERM regu- larized via KL divergence, (24), is the tilted Gibbs Posterior (a.ka. Gibbs Algorithm),,
expl exp(y)((, -077
P7 = HIS
TH
(25)
(S)
7. Related Works
where Fa is a normalization factor. Note that the Gibbs posterior.
In this section, we discuss related works on tilted empir- ical risk minimization and generalization error under an unbounded loss function. More related works for general- ization error analysis are discussed in Appendix B.
H1S == JH exp ( (-a (S)
( I E(H, 2i)), (26)
Tilted Empirical Risk Minimization: The TERM algo- rithm for machine learning is proposed by Li et al. (2021), where good performance of the TERM under outlier and noisy label scenarios for negative tilting (? < 0), and, un- der imbalance and faimesss constraints, for positive tilting (y > 0), is demonstrated. Zhang et al. (2023) study the TERM as a target function to improve the robustness of estimators. The application of TERM in federated learning is also studied, in Li et al. (2023b); Zhang et al. (2022).
is the solution to the KL-regularized ERM minimization problem, where Fa (5) is the normalization factor. There- fore, the tilted Gibbs posterior is different from the Gibbs posterior. (26). It can be shown that for y - 0, the tilted Gibbs posterior converges the Gibbs posterior. Therefore, it is interesting to study the expected tilted generalization error of the tilted Gibbs posterior. For this purpose, we give an exact characterization of the difference between the expected TER under the joint and the product of marginal distributions of H and
Inspired by TERM, Wang et al. (2023) propose a class of new tilted sparse additive models based on the Tikhonov regularization scheme. Their results have some limitations. First, in (Wang et al., 2023, Theorem 3.3) the authors derive an upper bound for À n -C where Ç -1/2 and À are the regularization parameters in (Wang et al., 2023, Eq.4). This implies X +
Proposition 6.2. The difference between the expected TER under the joint and product of marginal distributions of H and S can be expressed as,
- +00, which is impractical. As the analysis in (Wang et al., 2023) assumes that both the loss function and its derivative are bounded, it can not be ap- plied to the unbounded loss function scenario. Furthermore, we consider KL regularization, which is different from the Tikhonov regularization scheme with the sparsity-induced l f,2-norm regularizer as introduced Wang et al. (2023). Therefore,
RH PH 3 p)) - RH,,, PH.s) ISKI
(27)
We next provide parametric upper bound on the tilted generalization error of the tilted Gibbs posterior.
Theorem 6.3. Under the same Assumptions, cases (a) and (b) in Theorem 3.11, the expected tilted generalization error of the tilted Gibbs posterior satisfies
results do not cover the learning algorithm in Wang et al. (2023). Lee et al. (2020) propose an upper bound on the entropic risk function generalization error via a representation of a coherent risk function and using the Rademacher complexity approach. However, their approach is limited to bounded loss functions.
20 cxp(222/11 ) ++
S gen, S) <
(1 - 5)2
(28)
exp(1)/me)))) 1 | 2/2te
2a
V n
+ 2//1mm
1+c.
(1-5)ll
Tilted risk for off-policy learning and evaluation is pro- posed in concureent work by Behnamnia et al. (2025) where a regret bound analysis of this estimator under heavy- tailed weighted reward assumption is proposed. More de- tails about similarities and differences with this work are provided in Appendix B.
Convergence rafe: I OL1/n), then we obtain a con- vergence rate of On-=f) for the upper bound on the tilted generalization error of the tilted Gibbs posterior.
Comparison with the Gibbs posterior: Our results offer several advantages over the prior work in Aminian et al. (2021a). While Theorem 3 in their work establishes an (11/n) upper bound on the expected tilted generalization
Although rich experiments are given by Li al. (2021) for the TERM algorithm in different applications, the general- ization error of the TERM has not yet been addressed for
8

---

Generalization and Robustness of the Tilted Empirical Risk
unbounded loss functions with bounded (1 + e)-th moment for some E (0, I].
9. Future Works
Building on our current results, we highlight several promis- ing directions for future work:
Generalization error under unbounded loss functions: Several studies have investigated the generalization error of linear empirical risk under unbounded loss functions. Some works studied the generalization error under unbounded loss functions via the PAC-Bayesian approach. Losses with heavier tails are studied by Alquier & Guedj (2018) where probability bounds are developed. Using a different esti- mator than empirical risk, PAC-Bayes bounds for losses with bounded second and third moments are developed by Holland (2019). Notably, their bounds include a term that can increase with the number of samples n. Kuzborskij & Szepesvári (2019) and Haddouche Guedj (2022) also provide bounds for losses with a bounded second moment. The bounds in Haddouche & Guedj (2022) rely on pa- rameter that must be selected before the training data is drawn. Information-theoretii bounds based on the second moment of SUPNEæ ((h, Z) - E[((h,, 2)]l are derived in Lu- gosi & Neu (2022: 2023). In contrast, our second moment assumption more relaxed, being based on the expected ver- sion with respect the distribution over the hypothesis set and the data- generating distribution. Furthermore, an upper bound on generalization error via VC-dimension and growth function under bounded (1 + -)-th moment for c E (0, 1] is proposed in (Cortes et al., 2019, Corollary 12) which is mo- tivated by relative deviation generalization bounds in binary classification. In addition, the final convergence rate for unbounded loss is (1og(m)) based on (Cortes et al., 2019, Corollary 12). In contrast, we derive the results for a multi-Classification scenario with a convergence rate of O(n ( ). Our work focuses on tilted empirical risk, which is overlooked in the literature on unbounded loss functions.
An interesting avenue is to explore generalization bounds for tilted empirical risk in overparameterized models, particularly in the mean-field regime. Techniques from recent works, such as Aminian et al. (2023), may offer valuable insights for extending our results in this setting.
Overparameterization Regime:
Removing Sample Size Assumptions for Unbounded Losses: For unbounded loss functions, we currently re- quire a lower bound on the number of training samples to establish generalization guarantees, While we relaxed this assumption for the bounded loss case (see Appendix H), extending the analysis to the unbounded case without any sample size constraints would be a valuable extension.
Positive Tilt (1 0): Our analysis focuses on the case of negative tilting (7 < 0), assuming that the unbounded loss function has a bounded +1+ (1+h)-th moment for some c E (0, 1]. Extending the generalization analysis to positive tilting scenarios with unbounded losses remains an open and important direction.
Alternative Generalization Frameworks: Our current bounds rely on uniform and information-theoreiic frame- works. However, other frameworks- as PAC-Bayesian analysis (Catoni, 2003), algorithmic stability (Bousquet & Elisseeff, 2002b). and Rademacher complexity (Bartlett & Mendelson, 2002) complementary perspectives on generalization. We derived results using these frameworks under the bounded loss function assumption in Appendix H. Investigating the applicability of these methods to tilted em- pirical risk under an unbounded loss function could yield deeper theoretical insights.
8. Conclusion
In this paper, we study the tilted empirical risk minimization, as proposed by Li et al. (2021). In particular, we established an upper and lower bound on the tilted generalization error of the tilted empirical risk through uniform and information- theoretic approaches, obtaining theoretical guarantees that the convergence rate is O(n -(n+<l()+) under unbounded loss functions for negative tilt provided that (1 (1+))- moment of loss function is bounded for some E E (0, 1]. We also study the tilted generalization error under distribution shift in the training dataset due to noise or outliers, where we discussed the generalization and robustness trade-off. We also explore the KL-regularized tilted empirical risk minimization, where the solution involves the tilted Gibbs posterior, and we de- rive a parametric upper bound on this minimization with a convergence rate of O(n under some conditions and unbounded loss function provided that (1 + e)-th moment of loss functions is bounded for some e e (0, 1].
Acknowledgment
Gholamali Aminian, Gesine Reinert and Samuel N. Cohen acknowledge the support of the UKRI Prosperity Partner- ship Scheme (FAIR) under EPSRC Grant EP/V056883/1 and the Alan Turing Institute. Gesine Reinert is also supported in part by EPSRC grants EP/W03721 1/1 and 0V7R01847/11 Amir R. Asadi is supported by Leverhulme Trust grant ECF-2023-189 and Isaac Newton Trust grant 23.08 (b).. The authors thank the anonymous referees and the area chair for their insightful and constructive comments, which have led to an improved version of the paper. For the purpose of Open Access, the authors note that CC BY public copyright license applies to any Author Accepted Manuscript version arising from this submission.
9

---

Generalization and Robustness of the Tilted Empirical Risk
Impact Statement
Bartlett, P. L. and Mendelson, S. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463-482, 2002.
The goal this work is to improve our understanding of tilted empirical risk (TER) and to enhance its practical ap- plicability by introducing data-driven approach for hy- perparameter tuning. However, we acknowledge that our current theoretical analysis, which focuses on the negative tilt regime for understanding the robustness of TER, does not capture all aspects of TER-particulare its behavior under positive tilt for biases and imbalance scenarios.
Bartlett, P. L., Maiorov, V., and Meir, R. Almost linear vc-dimension bounds for piecewise polynomial networks. Neural Comput., 1508):259--113,,, 1998. doi: 10.1162/ 08997669833000110066 URL httpt:tp///// //oii org/10. 1162/08997660
Bartlett, P. L., Harvey, N., Liaw, C., and Mehrabian, A. Nearly-tight vc-dimension and pseudodimension bounds for piecewise linear neural networks. Journal of Machine Learning Research, 20(63):1-17, 2019. URL http: html.
References
Alquier, P. User-friendly introduction to -ayye bounds. arXiv preprint arXiv:21 10. 1216, 2021.
Alquier, P. and Guedj, B. Simpler PAC-Bayesial bounds for hostile data. Machine Learning, 107(5))887-902. 2018.
Bégin, L., Germain, P., Laviolette, F., and Roy, J.-F. PAC- Bayesian bounds based on the Rényi divergence. In Ar- tificial Intelligence and Statistics, pp. 435-444. PMLR, 2016.
Ambroladze, A.,
E.,, and Slawe-Taylor J. Tighter PAC-Bayes bounds. Advances in neural infor- mation processing systems, 19:9, 2007.
Behnamnia, A., Aminian, G., Aghaei, A., Shi, C., Tan, V. Y., and Rabiee, H. R. Log-sum-exponential estimator for off off-policy evaluation and learning. Proceedings of the International Conference on Machine Learning (ICML), 2025.
Aminian, G., Arjmandi, H., Gohari, A., Nasiri Kenari, M., and Mitra, U. Capacity of diffusion-basee based molecular com- munication networks over LTTI -Tl-Poisson channels. IEEE Transactions on Molecular, Biological and Multi-Scale Communications, 12):188-2000 2015.
Ben- David, S., Blitzer, J., Crammer, K., and Pereira, F. Anal- ysis of representations for domain adaptation. Advances in neural information processing systems, 19, 2006.
Aminian, G., Toni, L., and Rodrigues, M. R. Jensen- Shannon information based characterization of the gen- eralization error of learning algorithms. In 2020 IEEE Information Theory Workshop (ITW). IEEE, 2020.
Boucheron, S., Lugosi, G., and Massart, P. Concentration inequalities: A nonasymptotic theory of independence. Oxford University Press, 2013.
Aminian, G., Bu, Y., Toni, L., Rodrigues, M., and Wornell, G. An exact characterization of the generalization error for the gibbs algorithm. Advances in Neural Information Processing Systems, 34:8106-88 8118, 2021a.
Bousquet, O. and Elisseeff, A. Stability and gen-
eralization. J. Mach. Learn Res., 2:499-526,
March 2002a. ISSN 1532-4435.
doi: 10.1162/
Aminian, G., Toni, I.,, and Rodrigues, M. R. Information- theoretic bounds on the moments of the generalization error of learning algorithms. In 2021 IEEE International Symposium on Information Theory (ISIT). pp. 682-687. IEEE, 2021b.
153244302760200004 URL ptttps::/doi..rgg// 11 1162/1 1162/1552443227600000
Bousquet, O. and Elisseeff, A. Stability and generalization.
Journal of Machine Learning Research, 2(Mar):499 526, 2002b.
Aminian, G., Cohen, S. N., and Szpruch, E.. Mean- field analysis of generalization errors. arXiv preprint arXiv:2306. 1 1623, 2023.
Bousquet, O.,, Boucheron, S., and Lugosi, G. Introduction to statistical learning theory. In Summer school on machine learning, pp. 169-207. Springer, 2003.
Asadi, A. R. and Abbe, E. Chaining meets chain rule: Multilevel entropic regularization and training of neural networks. Journal of Machine Learning Research, 21 (139):1-32, 2020.
Bousquet, O., Klochkov, Y., and Zhivotovskiy, N. Sharper bounds for uniformly stable algorithms. In Conference Learning Theory, pp. 610-626, 2020.
Asadi, A. R., Abbe, E., and Verdú, S. Chaining mutual information and tightening generalization bounds. In Advances in Neural Information Processing Systems. pp- 7243,, 2018
Bu, Y., Zou, S., and Veeravalli, V. V. Tightening mutual information-basse bounds on generalization error. IEEE Journal on Selected Areas in Information Theory, 1(1):
121-130, 2020.
10

---

Generalization and Robustness of the Tilted Empirical Risk
Calafiore, G. C., Gaubert, S., and Possieri, C. Log-sum- exp neural networks and posynomial models for convex and log-log-conver data. IEEE transactions on neural networks and learning systems, 31(3):827-8838 2019.
Hellström, F. and Durisi, G. Generalization bounds via information density and conditional information density. IEEE Journal Selected Areas in Information Theory, 2020.
Cardaliaguet, P., Delarue, F., Lasry, J.-M., and Lions, P.- L. The master equation and the convergence problem in mean field games. Princeton University Press, 2019.
Holden, S. B. and Niranjan, M. On the practical applicability of ve dimension bounds. Neural Computation, 7(6):1265- 1288, 1995.
Holland. M. Pac-bayes under potentially heavy tails. Ad- vances in Neural Information Processing Systems, 32, 2019.
Catoni, O. A pac-bayesian approach to adaptive classifica- tion. preprint, 840:2, 2003.
Catoni, O. PAC-Bayesian supervised classification: the thermodynamics of statistical learning. arXiv preprint vrXiv:07/2.02444 2007.
Howard, R. A. and Matheson, E. Risk-sensitive markov decision processes. Management science, 18(7):356-369, 1972.
Chen, Y., Jin, C., and Yu, B. Stability and convergence trade- off of iterative optimization algorithms. arXiv preprint XXiv:1804.01619, 2018.
Kakade, M., Sridharan, K., and Tewari, A. On the com- plexity of linear prediction: Risk bounds, margin bounds, and regularization. Advances in neural information pro- cessing systems, 21, 2008.
Christmann, A. and Steinwart, I. On robustness properties of convex risk minimization methods for pattern recog- nition. The Journal of Machine Learning Research, 5: 1007-1034, 2004.
Kuzborskij, and Szepesvári, C. Efron- stronn pac-bayesian inequalities. arXiv preprini arXiv: 1909.0191, 2019.
Lee, J., Park, S., and Shin, J. Learning bounds for risk- sensitive learning. Advances in Neural Information Pro- cessing Systems, 33:13867-13879, 2020.
Cortes, C., Greenberg, S., and Mohri, M. Relative deviation learning bounds and generalization with unbounded loss functions. Annals of Mathematics and Artificial Intelli- gence, 85:45-70, 2019.
Li, T., Beirami, A., Sanjabi, M., and Smith, V. Tilted em- pirical risk minimization. International Conference on Learning Representations, 2021.
Dvijotham, K. and Todorov, E. A unifying framework for linearly solvable control. arXiv preprint arXiv: 120..3135, 2012.
Li, T., Beirami, A., Sanjabi, M., and Smith, V. On tilted losses machine learning: Theory and applications. Journal of Machine Learning Research, 24(142):1-79, 2023a.
Dziugaite, G. K. and Roy, D. Entropy-SGD optimizes the prior of a PAC-Bayes bound: Generalization properties of entropy-SGD and data-dependent priors. In Interna- tional Conference on Machine Learning, pp. 1377-1386. PMLR, 2018.
Li, X., Zhao, S., Chen, C., and Zheng, Z. Heterogeneity- aware fair federated learning. Information Sciences, 619: 968-986, 2023b.
Golowich, N., Rakhlin, A., and Shamir, O. Size-independent sample complexity of neural networks. In Bubeck, S., Perchet, V., and Rigollet, (eds.). Proceedings of the 31st Conference On Learning Theory, volume 75 of Proceed- ings of Machine Learning Research, pp. 297-299, PMLR, 06-09 Jul 2018. URL https: pttp://dccceeeecccoooo mlr. wtt.:ppesss/s///sseppp html..
Lowy, A. and Razaviyayn, M. Output perturbation for differ- entially private convex optimization with improved popu- lation loss bounds, runtimes and applications to private adversarial training. arXiv preprint arXiv:2102.044 047044 2021.
Lugosi, G. and Neu, G. Generalization bounds via convex analysis. In Conference on Learning Theory, pp. 3524 3546. PMLR, 2022.
Haddouche, M. and Guedj, B. Pac-bayes generalisation bounds for heavy-tailed losses through supermartingales. arXiv preprint 2t..i::2210000990 2022.
Lugosi, G. and Neu, G. Online-to-par conversions: Gen- eralization bounds via regret analysis. arXiv preprint arXiv:2305.1 19674, 2023.
Kolah- H., Golgooni, Z., Kasaei, S., and Soleymani, M. Conditioning and processing: Techniques to improve information- theoretic generalization bounds. Advances in Neural Information Processing Systems, 33, 2020.
Marceau, É. and Rioux, J. On robustness risk theory. Insurance: Mathematics and Economics, 2982).167-185, 2001.

---

Generalization and Robustness of the Tilted Empirical Risk
Massart, P. Some applications of concentration inequalities to statistics. In Annales de la Faculté des sciences de Toulouse: Mathématiques, volume 9, pp. 245-303, 2000.
Szabó, A., Jamali-Rad, H., and Mannava, S.-D. Tilted cross-entropy (tce): Promoting faimess in semantic seg- mentation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 2305- 2310, 2021.
McAllester, D. A. Some PAC-Bayesian theorems. Machine Learning, 37(3):355-3333 1999.
Talagrand, M. New concentration inequalities in prod- uct spaces. Inventiones mathematicae, 1eeen,2263330 126(3):505-563, 1996.
McAllester, D. A. PAC-Bayesian stochastic model selection. Machine Learning, 51(1):5-21, 2003.
Mohri, M., Rostamizadeh, A., and Talwalkar, A. Founda- fions of machine learning. MIT press, 2018.
Vapnik, V. An overview statistical learning theory. IEEE transactions on neural networks, 10(5):988-999 1999.
Mou, W., Wang, L., Zhai, X., and Zheng, K. Generalization bounds of SGLD for non-convex learning: Two theoreti- cal viewpoints. arXiv preprint arXiv: AXXvv:7707.05447 2017.
Vapnik, V. N. and Chervonenkis, A. Y. On the uniform con- vergence of relative frequencies events to their proba- bilities. In Theory of probability and its applications, pp. 11-30. Springer, 1971.
Murphy, K. Machine learning: probabilistic perspective...
MIT press, 2012.
Polyanskiy, Y. and Wu, Y. Information theory: From coding to learning, 2022.
Vershynin, R. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint arXiv:1011.3027, 2010.
Resnick, S. I. Heavy-tail phenomena: probabilistic and statistical modeling, volume 10. Springer Science & Business Media, 2007.
Wang, Y., Chen, H., Liu, W., He, F., Gong, T., Fu, Y., and Tao, D. Tilted sparse additive models. In Inter- national Conference Machine Learning, pp. 35579 35604. PMLR, 2023.
Rivasplata, O., Kuzborskij, I., Szepesvári, C., and Shawe- Taylor, J. PAC-Bayes analysis beyond the usual bounds. Advances in Neural Information Processing Systems, 33: 16833-16845, 2020.
Williams, C. K. and Barber, D. Bayesian classification with gaussian processes. IEEE Transactions on pattern analysis and machine intelligence, 20(1)):1342 1351, 1998.
Rodrigues, M. R. and Eldar, C. Information -heeoreticc methods in data science. Cambridge University Press, 2021.
Xu, A. and Raginsky, M. iolommttion-thoorete analysis of generalization capability of learning algorithms. Ad- vances in Neural Information Processing Systems, 30,
Ronchetti, E. M. and Huber, P. J. Robust statistics. John Wiley & Sons Hoboken, NJ, USA, 2009.
Russo, D. and Zou, J. How much does your data explo- ration overfit? controlling bias via information usage. IEEE Transactions on Information Theory, 66(1):302- 323, 2019.
2017.
Xu, H. and Mannor, S. Robustness and generalization. Machine learning, 86(3):391-423, 2012.
Ye, H., Xie, C., Cai, T., Li, R., Li, Z., and Wang. L. Towards theoretical framework of nut-of-distribution generaliza- tion. Advances in Neural Information Processing Systems, 34:2351 1115519-23355 23531, 2021.
Shalev-Shwartz, S. and Ben-David, S. Understanding ma- chine learning: From theory to algorithms. Cambridge university press, 2014.
Shawe-Taylor, J. and Williamson, R. C. A PAC analysis of Bayesian estimator. In Proceedings of the tenth annual conference Computational learning theory, pp. 2-9, 1997.
Zhang. G., Malekmohammadi. S., Chen, X., and Yu, Y. Proportional fairness in federated learning, arXiv preprint arXiv:2202.01666, 2022.
Steinke, T. and Zakynthinou, L. Reasoning about general- ization via conditional mutual information. In Conference on Learning Theory, pp. 3437-3452, 2020.
Zhang, T. Information-theerrtie upper and lower bounds for statistical estimation. IEEE Transactions on Information Theory, 52(4):1307-1321 2006.
Swaminathan, A. and Joachims, T. Batch learning from logged bandit feedback through counterfactual risk min- imization. The Journal of Machine Learning Research, 1631):173 2015.
Zhang, X., Wang, Y., Zhu, L., Chen, H., Li, H., and Wu, L. Robust variable structure discovery based on tilted empirical risk minimization. Applied Intelligence, 53(14): 17865-17886, 2023.
12

---

Generalization and Robustness of the Tilted Empirical Risk
Zhou, T., Wang, S., and Bilmes, Robust curriculum learning: from clean label detection noisy label self- correction. In International Conference on Learning Representations, 2020.
Zou, Y., Kawaguchi, K., Liu, Y., Liu, Lee, M.-L., and Hsu, W. Towards robust -uitt--dittiiuuttinn generalization bounds via sharpness. arXiv preprint vrXiv:2403.06392 2024.
13

---

Generalization and Robustness of the Tilted Empirical Risk
Appendix
Table of Contents
Summary of Notations
B Other Related Works
15
Technical Tools
D Proofs and Details of Section
19
D.1 Proofs and Details of Uniform bounds under Unbounded Loss
D.2 Proofs and Details of Information-thhorriicc Bounds under Unbounded Loss
22
E Proof and details of Section 4
26
E.1 Convergence rate under distribution shift
28
F Proof and details of Section 6
28
Experiment Details
H Generalization Bounds for Bounded Loss Functions
32
Uniform bounds bounded loss
H.2
theeret bounds for bounded loss functions
35
The KL- Regularizz TERM Problem
H.4 Other Bounds
40
14

---

Generalization and Robustness of the Tilted Empirical Risk
A. Summary of Notations
All notations are summarized Table
Table 3: Summary of notations in the paper
Notation
Definition
Notation
Definition
S
Training set
Zi )
i-th sample
X'
Input (feature) space
Output (label) space
Data Data-generating distribution
j (L()II)
Data eataa-enerating distribution under distributional shift
Tilt parameter
KL-divergence between P and Q
I(X;))
Mutual information
(skl(PIIQ)
Symmetrized KL divergence
TV(,,Q)
Total variation distance
Ku
Bound on second moment Hypothesis space
h
Hypothesis
H R(h, 11)
2)
Loss function
Population (true) risk
R (h, S)
Tilted empirical risk
gen, (h, (1)
Tilted generalization error Excess risk
Ry (8))
Tilted population risk
B. Other Related Works
This section details related works about tilted empirical risk minimization, the Rademacher complexity and stability and ACC-Bayesian bounds. We also compare our work with Behnamnia et al. (2025) in more details.
Generalization Error Analysis: Different approaches have been applied study the generalization error of general learning problems under empirical risk minimization, including VC dimension-based, Rademacher complexity, PAC-Bayesian, stability and inforoition-theerrtii bounds.
Uniform Bounds: Uniform bounds (or VC bounds) are proposed by Vapnik & Chervonenkis (1971); Bartlett et al. ( (1998; 2019). For any class of functions F of VC dimension d, with probability at least - 8 the generalization error is O(d log(1
This bound depends solely on the VC dimension of the function class and on the sample size; in particular, is independent of the learning algorithm.
Information- thhorrttic bounds: Russo & Zou (2019); Xu & Raginsky (2017) propose using the mutual information between the input training set and the output hypothesis upper bound the expected generalization error. Multiple approaches have been proposed to tighten the mutual information- based bound: Bu et al. (2020) provide tighter bounds by considering the individual sample mutual information; Asadi et al. (201 8); Asadi & Abbe (2020) propose using chaining mutual information; and Steinke & Zakynthinou (2020); Hafez-Kolas et al. (2020); Aminian et al. (2020; 2021b) provide different upper bounds on the expected generalization error based on the linear empirical risk framework.
Rademacher Complexity Bounds: This approach is a data-dependent method to provide an upper bound on the generalization error based on the Rademacher complexity of the function class H. see (Bartlett Mendelson, 2002; Golowich et al., 2018). Bounding the Rademacher complexity involves the model parameters. Typically, in Rademacher complexity analysis, symmetrization technique is used which can be applied to the empirical risk, but not directly to the TER.
Stability Bounds: Stability bounds for generulization error are given in Bousquet & Elisseeff (2002a); Bousquet et al. (2020); Mou et al. (2017); Chen et al. (2018); Aminian et al. (2023). For stability analysis, the key tool is Lemma 7 in Bousquet & Elisseeff (2002b), which based on ERM linearity. Therefore, we can not apply stability analysis to TER directly.
PAC-Bayesian bounds: First proposed by Shawe-Taylor & Williamson (1997); McAllester (1999) and McAllester (2003), PAC- MAC-Bayesian analysis provides high probability bounds on the generalization error in terms of the KL divergence between the data data-dependent posterior induced by the learning algorithm and a data-free prior that can be chosen arbitrarily (Alquier, 2021). There are multiple ways to generalize the standard PAC-Bayesian bounds, including using information measures other than KL divergence (Alquier & Guedj, 2018; Bégin et al., 2016; Hellström & Durisi, 2020; Aminian et al., 2021b) and considering data- dete-deenndent priors (Rivasplata et al., 2020; Catoni, 2007; Dziugaite & Roy, 2018; Ambroladze et al., 2007). However, this method has not been applied to TER to provide generalization error bounds.
15

---

Generalization and Robustness of the Tilted Empirical Risk
The aforementioned approaches applied to study the generalization error in the linear empirical risk framework. To knowledge, the generalization error of the tilted empirical risk minimization from information-theerrtica. and uniform approach perspectives has not been explored.
Comparison with Behnamnia et al. (2025): In a concurrent work in reinforcement learning, Behnamnia et al. (2025) introduce an estimator for off-policy evaluation and learning based on the log-sum-exponential (LSE) operator applied to weighted rewards. This estimator can be viewed as a negatively tilted risk function. Their focus lies in bounding the regret, defined as the gap between the value of the optimal policy and that induced by the estimator, and in deriving concentration inequalities under heavy-tailed reward distributions. We compare our work with theirs from several perspectives:
Objective Functions:
Our study targets supervised learning, where the goal is to minimize a risk function such as empirical or tilted risk. In contrast, Behnamnia et al. (2025) addresses off-policy learning, aiming to maximize expected reward for a given logged data with respect to a policy, conditional distribution over actions for a given context. Furthermore, in a supervised learning scenario, the loss function is given. In contrast, in off aff-policy learning, the reward function is not known, and some samples of reward are given. Therefore, the learning paradigms and optimization targets differ. For more details, comparison of these scenarios see (Swaminathan Joachims, 2015, Table 1).
Assumptions: We assume bounded hypothesis class and heavy-tailed loss functions. In contrast, (Behnamnia et al., 2025, Assumption 5.1) considers a bounded policy class and assume heavy-tailed weighted rewards. These differences reflect the distinct nature of these tasks: off-policy and supervised learning scenarios. Note that the definition of heavy-tailed random variable is general in statistical learning theory (Resnick, 2007) and can be applied in different contexts, e.g., bandit, off off-policy learning, and supervised learning.
Methodology: Despite differing goals, both works employ some common statistical tools, such as concentration inequalities. We build on analytical techniques similar to theirs, including lemmas concerning variance bounds under heavy-tailed distributions. However, our uniform bounds operate under different assumptions and are adapted to the supervised learning setting. In particular, we used Lemma C.2 and Lemma C.3- where a different proof of Lemma C.3 is proposed in (Behnamnia et al., 2025, Theorem 5.3)- to derive our upper bounds on absolute value of generalization error (Theorem 3.5) using uniform approach under heavy-tailed assumption. However, as discussed in Section 1. the uniform approach has inherent limitations, c.g., assuming bounded hypothesis sets which is a complexity measure in the supervised learning scenario. The limitations also apply to results in (Behnamnia al., 2025, Theorem 5.3) with finite policy set as a complexity measure in off-policy learning. To overcome the limitations of finiteness of sets assumptions, we further develop new bounds using informationn-hheortiicc techniques.
Bounded Scenario: Both works note limitations sample complexity under heavy-tailed assumptions. We show in Appendix H that such constraints can be lifted by assuming bounded loss functions leaddigg to generalization guarantees for all number of training samples.
Robustness: A key contribution of our work the analysis of tilted empirical risk under distribution shift, a direction not explored in earlier literature our knowledge. Our results highlight the distinct value of TER in handling training-test distribution discrepancies.
Regularization: We also explored the KL-regularized problem for tilted empirical risk, where a tighter convergence rate of O(n 9) for tilted empirical risk was derived under a heavy-tailed assumption.
C. Technical Tools
We first define the functional linear derivative as in (Cardaliaguet et al., 2019).
Definition C.1. (Cardaliaguet et al., 2019) A functional U : P(R") + R admits a functional linear derivative if there is a
SU, P(R") x R² + R which is continuous on P(R"), such that for all m, m,m' e P(R"), it holds that
map 5m
U(m') - U(m) = [(" S
8U 3m (m,, a) (m' m))(d) dA,
where my m 1(m' m).
The following lemmas are used in our proofs.
16

---

Generalization and Robustness of the Tilted Empirical Risk
Lemma C.2 (Lemma 28 in (Lugosi & Neu, 2023)). For x O, the following inequality holds for e (0, 11.
exp(-n)
x0+0)
(29)
The following lemma also appears in the concurrent work by Behnamnia et al. (2025). For the sake of completeness, we provide an alternative proof below.
Lemma C.3. Suppose that X > O and < O, then we have for E (0, 1).
( Var(exp(>>X)) - 2/ |+ (t)].
(30)
Proof. From the variance definition, we have,
Var(cxp(7:X)) = E (xx((xX) - Efexp(>>x)) ']
(31)
(
Ex (
exp(>x))) (exp(>X) exp(>x))) lti
[exp()X) -xxx)>x))x)x)) |
(32)
2
(6)
Ex,x
(33)
(9)
1//|
++
Ex,xXIX - x'1tt]
(34)
(4)
2/ 1/1 +1 IIX + X11ttj
(35)
W 2/ 1+ Ex
(36)
where (a) follows from variance representation for i.i.d copy X and X', (b) follows from the fact that |exp(>X)
exp(>X')] < 1, (c) follows from the fact that exp(yz) is Lipschitz for y < 0, with parameter lr]. therefore, we have (exp()x) - exp()x')] S h1|l z'1. (d) follows the positiveness X and X' and (e) follows from Jensen-inequality.
Lemma C.4. Suppose that 0 < a < X < <b<a <o<00 co. Then the following inequality holds,
Varrx (X)
Var (X)
S [og(E[ [[log(X)]
262
2a²
where Varps (X) is the variance of X under the distribution Px-
d² Proof. As dzz (log(z) + 3z Hence, by Jensen's 's inequality,
+ 28, the function log(z) + Bx is concave for B 25 and convex for 8
1
2n
X²
X²
E log X)] E log( (X)
262
262
1
< log(LB[XX) +
21
21F
212
log(E[X))
Varpx (X):
262
which completes the proof of the lower bound. similar approach can be applied to derive the upper bound.
Lemma C.5. Suppose that 0 < < X <b < co. Then the following inequality holds,
-Varpx (X) exp(b)
exp(E(X]) El(expXX)] < -Var (X) exp(a)
2
2
where Varpx (X) is the variance of X under the distribution Px- In the next results, Ps is the distribution S.
17

---

Generalization and Robustness of the Tilted Empirical Risk
Lemma C.6 (Hoeffding Inequality, Boucheron al., 2013). Suppose that (Z,)==1 are bounded independent random variables such that a I Z4 b,i= , nr. Ps.
Then the following inequality holds with probability least (1 -) under
n
(2/0)
B|Z
Σ
2 S (6
(b-)))
(37)
2n
Lemma C.7 (Bernstein's Inequality, Boucheron et al., 2013). Suppose that 5 {z.): are i.i.d. random variable such that Z2- E[Z]] < R almost surely for all i, and Var [) o². Then the following inequality holds with probability at
least (1 8) under Ps.
4 log(2/6)
4Rlog(2/0)
E
Z
(38)
71 i=1
n
3n
Lemma C.8. For a positive random variable, > and c E (0, 1), suppose E|Z holds,
S 1). Then, the following inequality
E|Z S g//1=
Lemma C.9. Suppose B|[x|+++] co. Then, for X and 7 < 0 the following inequality holds,
0 $ B|x]
log Ele ] $ |11'[[x!']]
Proof. The left inequality follows from Jensen's inequality applied to f(x) = log (xr). For the right inequality, from Lemma C.2 for e (0,1]
xxx + 7 + 11
(39)
Therefore, we have,
1
log E le
log [1 +1++10 > + 1/ [||"+(||"" [x|
1 log (1 7B X + h1 (((x
7
1 (y|[[} +
?
E[X]
|/ ||
Lemma C.10. Suppose that < and f(x) is an increasing and concave function.. Then the following holds,
(((b((b a) S f(b f(a) s (a)(bb-)))
(40)
Lemma C.11 (Uniform bound (Mohri et al., 2018)). Let F be the set of functions f Z + (0, M] and μ be a distribution
over Let S {z be a set of size n. ii.dd drawn from Z. Then, for any å E (0, 1), with probability at least 1 over the choice of S, we have
sup fE
B2=nI[(2)
1(a)) 2Ft 3M
log
2
2n
We use the next two results, namely Talagrand's contraction lemma and Massart's Lemma, to estimate the Rademacher complexity.
Lemma C.12 (Talagrand's contraction lemma (Shalev-Shwartz & Ben-David, 2014)). Let di R + R2 (i { n1]
n2) be
finntichit, and F, be set of functions from Z to R. Then it follows that for any {zr ) C 2,
E2
sup Σ (f(o)(())))
< LE,
sup
Σ oaf(ei)
feF, i=1
fer, t=l
18

---

Generalization and Robustness of the Tilted Empirical Risk
Lemma C.13 (Massart's lemma (Massart, 2000)), Assume that the hypothesis space H. is finite. Let B
Σ (=)))) Then
max
Rs( (Vgooo(ccrd((H))
Lemma C.14 (Lemma
(Xu Raginsky, 2017)), For any measureable functiin f: - [0,
I()
Bxx,y -Bx ([X, M 2
Lemma C.15 (Coupling Lemma), Assume the function f: : 2 - M] and the function RR+ b RR are L-Lipschitz. Then the following upper bound holds,
I(XYY
Exxy ((X,)) (xxx & LM
2
We recall that the notation TV denotes the total variation distance between probability distributions.
Lemma C.16 (Kantorovich Rubenstein innbentvicc-Ruuenseeeen duality of total variation distance, see (Polyanskiy & Wu, 2022)). The Kantorovich-
Rubenstein duality (variational representation) of the total variation distance is as follows:
TV(m,,
sup (Bz-m, [g(Z)) - Ez (2)))
(41)
2T ged2
where Gr. = {g: 2 R. l1g1 < LJ.
D. Proofs and Details of Section 3
D.1. Proofs and Details of Uniform bounds under Unbounded Loss
Proposition 3.2 (Restated). Under Assumption for, 7 < 0, the difference between the population risk and the tilted population risk satisfies
0 < R(h, (h, S 1=/
(42)
Proof. The proof follows from Lemma C.9.
Proposition 3.3 (Restated). Güven Assumption 3.1, for any fixed h E with probability at least (1 8), then the following upper bound holds on the tilted generalization error for y < 0 and some E (0, 1),
2 2exp(->Ra gen, (h S
log(2/8)
4exp(- (k)),))))))))) 1og(2/8) + In/tt
(43)
hyl
n
3n/7l
Proof. Using Bernstein's 's inequality, Lemma C.7, for X, exp(re(h, Z.)) and considering 0 < X, < we have
(Vrr(cxp(77(1, 2))) l2g(2/8) 4 log(2/8)
n Σ
exp E(h, 24) < Elexp(((((, 2)) +
+
n
3n
where we also used that
log(x + v) = -log(v) + log(1
2) $) log(v) for forg>>>>> 0. y
(44)
y
19

---

Generalization and Robustness of the Tilted Empirical Risk
Thus,
1 Σ exp 7e(h, Zi) log
1=1
< log
[lexxp(r((h, 2]1l
(Var(exp(>E(1,, 2))) log(2/0)
4 llg(2/8)
+
Ejcxp(>y(h, 2))l
F(exp(>((h) 2))l
3n
log [Elexp(r((h)) Z])1
(Vr(e Z))) l2g(2/6) + exp(->76..) 1208(2
exp( exp(->Kk))
n
3n
Therefore, for y < we have
1
1 log (Elexp(7e(1, 201) log ( (+ exp ,e(h, Zi)
7
exp(-7ku)
4Var(exp(7e(h,, Z))) log(2/0) exp(-yrs.
4log(2/0) 3n/yl
hl
Using Lemma C.3, completes the proof.
Proposition 3.4 (Restated). Given Assumption 3.1, there exists Ç E (0, such that for 2 [47 -8 log()//2//8//
exp(
for any fixed H with probability least (1-6), and y < the following lower bound on the tilted generalization error holds,
2 [exp([7/ku)
1+c 20/ 2ee Ku
log(2/8)
4 4exp(12/<<m) ((og(2
gen Sh. 2-
(45)
(1-5)l7
3n/1((1 -() ()
Proof. Recall that Z a and
1 (og(Elexp(><((h 2111)
gen (), (h, R(h, u)
Σ expl exp(>e(h, 2:))
+ log(E(exp(7((1,, B))1 - logg 7
First, we apply Lemma C.9 to yield R(h, u1) 1og( 2))) 2 0. Next we focus on the second line of this display. Bernstein's inequality, Lemma C.7, for X; exp(7((h, Z,)), so that 0 < X, < 1, gives that with probability at least (1 5),, 5),
(ar(exp(>7(),, 2))) log(2/5) 4 4lg((2/0)
Σ exp A(h,, Z,) 2 Elexp(r((h, Z))
(46)
3n
Assume for now that there is a Ç (0, 1) such that
Var(exp(7((h,, 2))) log(2/8) 4 log(2/8)
< (1)exp((7((h 2))]
(47)
7
3n
20

---

Generalization and Robustness of the Tilted Empirical Risk
As log(y 2) log(y) log(1 ) log(y) بير for y x 0. then by taking Elexp(>e(h) 2))l and yーΣ
I / Verlexp((<((h.2)) (2/6) log(2/6) so that with (47) we have y - x 2 (1 - C)y > 0, taking logarithms on both
3n
sides of (46) gives that with probability at least (1 -),
log (1
Σ n 1=1
exp xxp, Zi))
2 log (Elexp(>e(h, 2)11)
1
Var(exp(7e(h, Z))) log(2/5)
4 (2/6)
E(exp(>e(h, 2))]
n
3n
4 Var(exp(7((h,, Z))) log()/)) ())(exp(7((h, 2))
2 log (Elexp(7e(h,2) 21)1
(1
(48)
(2/(2
(1 (1-<) El(x)p(xxp(rE(1, 2))]
3n
2 log [Blexp(>((h,, 2))1
exp(-7(Ki))
Var(exp(7e(1,, 2))) log(2/8)
exp(-7Ku)) llo(22/))
(1 - ()
n
(1 (1-5)
3n
h 12 cxp(-</tp
log(2/8) exp(->Huu) 41og(2/6)
2 log (Elcxp(yy((h,)) 2))1
(1 (-() ()
n
(1-5)
3n
Here used that by Assumption 3.1 and Lemma C.8.
Elexp(r((h, ())] S exp|E(><((,, (2)) s exp(11iu) and by Assumption 3.1 and Lemma C.3,
Var(exp(7((h,, 2))) < h1 2) < +r
This gives the stated bound assuming that (47) holds. In order to satisfy (47), viewing (47) quadratic incquality in v and using that (a b)2 2a² 2b yields
(4 Var(exp(><((,, + 8/33///xp///t 2))) log(2/8)
((E(exp(>((h,, 2))]}²
Now applying exp()к..) < Elexp(r<((h, 2))] < and Var(exp(><(h,, Z)) s / ++ completes the proof.
Theorem 3.5 (Restated). Under the same assumptions in Proposition 3.4 and a finite hypothesis space, then for 2 (1b)) w. 1++ +8/3())(B)))))) log(2/6) for < O and with probability at least (1 5), the absolute value of the titled
ę exp(22 (2
generalization error satisfies
sup Igen, (1, (,, 2exp(h)(mm)) NEW
20/ 1+ B(5)
4exp(1 (w,)
+ 3n 11(1 -)) + ln/5x
(49)
-1- (1-
where B(8) = log(card( + 12g(2/)). (og(2//))))
Proof. Combining the upper and lower bounds, Proposition 3.3 and Proposition 3.4, we can derive the following bound for a fixed h H.
2 2exp( (exp(-76.))
2 1+ + 1e (log(2/5))
+ 4 (exp(->rr.)log(2/0) + 11
gen. (h, (1)
(50)
(1 (1-5)
n
3n/ - -()
Then, using the union bound completes the proof.
21

---

Generalization and Robustness of the Tilted Empirical Risk
Lemma 3.7. The excess risk of the tilted empirical risk satisfies,
( S 2 sup Igen, (cnn,(h,5)) (h,
GEH
Proof. It can be proved that,
( S 2 sup gen, (h, Sh) kEH
and
(S))())) & (K, S (M) UU I R(( 2U,
where U suPheи [R,,, p) (h, S)I suPлeи gen, S)).
Corollary D.I. Under the same assumption in Proposition 3.4 and a finite hypothesis space, then for n 2 (44 (4n*"" +8/3() log(2/5) with probability least (1 - 8) and 7 O, the excess risk of tilted empirical risk satisfies,
5 exp(2
4 4exp(hy(mx)
20 1y ten B(6)
8 8exp((7(kx.)B(0)
(x) S
+ 2/7/" N
(51)
(1 - 1/
n
3n/ -
where (6) log(card(H)) + (2/6) and (p(p) is defined in (7).
Proof. Combining Theorem 3.5 with Lemma 3.7 completes the proof.
D.2. Proofs and Details of Informatiin--hhooreiicc Bounds under Unbounded Loss Proposition D.2. Under Assumption 3.8, 7 < holds for some E (0, 1] that,
$ R(H, PH 2 ()) - R, & 14) S hr| Ki lte
(52)
h| s R2 (H, PH.s) EpH.s Ry (HI S)] S.
Proof. The proof follows from Lemma C.9.
Proposition 3.9. Given Assumption 3.8, the following inequality holds for y
exp((
2/y/1 1+ I(H;S)
if (1H:9)
< 2 tts
RH PH @ pd R,HH, PH.s)
exp (x))) hn
I(H:S)
2 1r/ 1e
11H:8)
2 by 12
2
Proof. For 0, we use that 0 < exp(n)(H), 2) < 1 and Var(exp(>?(11,2)) 2))) < | 2) < t/|2tent Note that the variable exp(yl(H, Z)) is sub-exponential with parameters (h|"*<<?) x 1) under the distribution Pn @ Using the approach in (Bu et al., 2020; Aminian et al., 2021a) for the sub-exponential case, we have
E Err (exp(7((H, 2)) E E.n. exp(>e((., ZJ)]
(53)
2// +ex] 1+c ((N:8)
((1:8) I(H:8)
2
n
((H:S) + 1
2 tt
2
Therefore, we have for I(H:8)
21/ ++
exp(>((H, 2.))] - <BPrwuu [oxp(T((H, + rrd I(H;
Ep
(54)
22

---

Generalization and Robustness of the Tilted Empirical Risk
Using (44) gives
1
log
EPn. n
(H,()((H,2))1)
log (ox(EP), 2)))
7
(55)
2/ 1+c (H:
y1 PM NH (xxp((
For 1(H;5)
2/ 2// +
t+e
have
[ErnSy exp(>>(H, (Erxsu(xx(()((FF2)) 2)) + I(H:5)
20/ 1+8
Erss Σ
exp(re(H. (.)))
+
(56)
2
1=1
Using (44) again, we obtain,
1 (exp)) 2))1)
log E.p. exp(> (x)))
(57)
I(H:5)
2 |/| + + 1tc
71E son (exp(1((H, 2))]
7
As under Assumption 3.8 and Lemma C.8, we have exp(7<t) S Ep on (expl (exp(>)(H, ())] the final result follows.
Proposition 3.10. Under Assumption 3.8, there exists Ç (0. 1) such that one of the following cases holds,
(a) 5 2'yy 1+* w exp(1)]e)) and n 2 21bl't'x ((H.))
( (epp(2yxr)
(b) > 27> +tr exp(1)le) and n Z 2
21(HSS)
(c) Ç >
2'171"+e exp((n((s.) and 2I(H:S)
21 IFF > n 2 2[cxp(Tx)) -bll
2I(H:S)
Then, the following lower bounds on non-linear expected tilted generalization error hold,
-ex((1]lx)
2/ Up| if (a) (b) hold,
gen, (H, 2
hi(l-5)
exp((r)ne)
I(H:S)
2 +++++
if holds.
(1 (1b))
2
Proof. Note that, we have,
E Ernenlexp(7e[[) (exp(y)(H, 2))1 Ern.
expl
exp(> ( H, Z.)i
(58)
t2x 1+e I(H:S)
[(H:S)
2 ++
(H:S)
2 ////211 t 1 +
I(H:S)
2
2
For 1(H:9) n
have,
exp( exp())((H,z)) > (BPnon exp((r((H,)) 2))] -n/
1tr I(H;S)
E Eps.
(59)
Assume for now that there is a E (0, 1) such that
22
1(115))
n < <EPn@n exp(()((, (CpreeLexp(/(HH.. 2))
(60)
23

---

Generalization and Robustness of the Tilted Empirical Risk
As log(y - x) = log(y) + log(1 5) 2 log(v) _ for > I > 0, then by taking = P2 @w
exp(> 2)) and
J / ///1 // + ((H:))
so that with (47) we have y x 2 y > 0, taking logarithms on both sides of (59) gives
"
that
log E Tr (exp()))) 2))))
log
Ern, n
exp(>e(H, Zi))
(61)
2|7|2 K
[ IH;S)
71
Z))]
n
where it holds for n 2 ((
2/7 11 (
As we also have ((N:8)
we consider the condition n 2
ç exp(2
2
2((H:S)
max 2 (xp())))))
For 21(1:8) to
n, we have
E 1 Σ exp(>e(H, 2.1)
EEaSy (x)()((H,2))
I(H;5)
29/
1tc
(62)
n
2
As log(y- - 2) = logg()) + log(1 - 5) 2 log(y) z w-E- we obtain,
log EEHS - exp(>e(H, 2011) 1 (oxppoooeexx((7 2))))
(63)
I(H;S) 2971 2te
7(1 (') xu (exp(><(11 2))]
Assume for now that there is a 5" E (0, 1) such that
T(H:S) 2t/
E'Epne @μ exp()e(H,
+
(64)
n
2
where it holds for 20' =x S Therefore, the final condition is
(H(:SS)
2T(H; S) 2 exp(())) - h +c 2 t +
S)
1+c In S
Note that, we also have due to 2ab < a² + +
2/1 1 + K (H:
I(H:S)
t* 1
(65)
+ 2
n
n
Therefore, choose Ç C', Furthermore, we can also discuss the following cases.
If (exp(())))) < 2' 1s holds, then for n 5² exp((2mm)
(et we have,
-exp(1y1k))
Ry (H, R (H,
h:((1 -)( V
(exp((())))) 2 2t 1tc
holds, then have,
(H, PH & 11) R. (H, PH.s)
exp((1(me) hl(1-()
2/-|1-ew/ (()
if 21(H:S)
< n
2 2
exp(1//k1)
I(H:S) + 21/1/2
if 21(H9
2
21(H:9)
(1-))=l
2
2 2hi
2 exp(xxx, -
24

---

Generalization and Robustness of the Tilted Empirical Risk
Using Proposition 3.9, we can obtain the following upper bound the expected tilted generalization error.
Proposition D.3. Given Assumption 3.8, the following upper bound holds on the expected tilted generalization error for <<< 0,
exp(I)]<x) b
((H:8)
+ (//(mn
if ((
2
gen (HS))
S
n
exp(Ia]<e)
((HS))
2 +
2 + +11 mt
if (1H.9)
2 7
by]
2
Proof. We use the following decomposition.
E PHss Igen, ()] EpH.s [R(H, [J] R,, PH Pa @ μ)) + (H, @ n) (H, PH.s)
(66)
+ RR, (H, PH.s)
Epn. [R, (H, (H. S)].
Then, using Lemma C.9, we have
Ern.s [R(H. (H, PH 8 < ( Erwsul (f (H,, [H] $ ln/5x/
(67)
and now Jensen's inequality for 7 0 yields
(H,,,,H.H) PH.s) - EHH. (H, (H, S)] 0.
(68)
Applying Proposition 3.9, we obtain
exp(1>lme) hrl
2/112ten +(H:S
if I(H:S)
2 2hh ++
R, 8 11 - R, PH,s) <
exp (v))))
I(H.S)
21
if I(H:S)
+
2
Combining (68), (69) and (67) with (66) completes the proof.
Proposition D.4. Under Assumption 3.8, there exists Ç E (0, 1) such that one of the following cases holds,
(a) Ç + exp())(e) and n 2 5² expp(2mm))
(b) <> 2/b/1 (n exp(1a(e) and n 2 11
21(H:S)
(c) < 2'17 t exp(1)le) and 21(H:9) 2b
2T(H:S)
24 <x
+*
Then, the following lower bounds on expected tilted generalization error hold,
exp((1]ke) h((-(()
2/ h/ 1+c, (f or (b) hold,
gen (H, 2
exp((alas)
I(H:S)
2o ///s, (c) holds.
(1-C))
2
Proof. The proof is similar Proposition D.3 and using Proposition 3.10.
Theorem 3.11. Under Assumption 3.8, there exists Ç E (0, 1) such that one of the same cases in (5 25yy 1ts, exp(1)le)) and > 21 (
( exp(2)mm)
(b) 21y te exp(1)(e)) and 21/
21(H:8)
(c) <> 211/"1s exp(1alm)) and 2I(H:S)
2I(H:S)
20/y)= !r > n1 -xxp(rm))-bapll"""
Then, the following lower bounds non-linear expected generalization error hold,
exp(1xie) TII(-
2x2I(H;S)
1y mx (a) or (b) hold,
gen. S)
exp(1x/se) (1-Oml
I(H:S)
2
11
1tc (c) holds.
n
2
25

---

Generalization and Robustness of the Tilted Empirical Risk
Proof. This result follows by combining the upper bound from Proposition D.3 with the lower bound from Proposition D.4.
Remank D.5 (Individual Sample Bound Discussion). We derive the results based individual sample approach (Bu al., 2020), replacing the following incquality with (53), which is based on individual sample,
E P (exp(r Z - Eps.s
Σ
exp() Z))1
n
(69)
2 1tc - Ei I(11;)) Z.)
if maxiejo] [(H; < 21/ll
2
E T(H: Zi) + 1
if minkej)) T(H; 7.) > 29/1 2/ "n +
E. Proof and details of Section 4
Proposition 4.2 (Restated). Given Assumption 4.1 and Assumption 3.1, then the difference of tilted population risk under, (9), between y and ju is bounded as follows for all E H.
(exp(I)lmw)) exp((T/kas))
TV(,,)) (b)
? 2xx 2))) log 1og(E22,l 21)1) -
(70)
72
(Kiu Ks)
Proof.
We have for a fixed H that
log [E Zmp (oxp(1((h, 2]]]) log( (exp(>e(h, [ox(22,,ooxp(7((.. 2))))
7
7
exp(?e(h, 2))
1/ Z~N0 (exp(>e(h, 21)]] (i2 (d)
(71)
(b) Tu ()) exp(())m.))
exp(I:/A(HH) - -Ka)A ka))dA
ly]
TV(n, M)) exp(I)mm)) exp(h1(ta))
ly|
(1 (Ka) Ks)
where (a) and (b) follow from the functional derivative with μa j + A(p= ju) and Lemma C.16. The same approach can be applied for the lower bound.
Remark E.1. For positive 7, the result in Proposition 4.2 does not hold and can be unbounded.
Proposition E.2 (Upper Bound). Given Assumptions 3.1 and 4. for any fixed h H and with probability least (1 - 5) for 7 < O, then the following upper bound holds on the tilted generalization error
2 2exp(h1lxa) gen, (1, <
2 11t log(2/6)
V
h
n
4 (exp()))kx))loo(2)))) (2/6))
TV (i) (exp(I)<ku) - exp((v\1se) (xx((1/))))))(((() (Kir - K.a)
+ m
3n/rl
y/2
where $ is the training dataset under the distributional shift.
The proof follows directly from the following decomposition of the tilted generalization error under distribution shift,
Proof.
gen, (h, $) RRh, p) R2 R2, 8n (h, 4) R., (h, Rh (h, (h, $).
1s
I
where Js. To and I can be bounded using Lemma C.9, Proposition 4.2 and Proposition 3.3, respectively.
26

---

Generalization and Robustness of the Tilted Empirical Risk
Proposition E.3 (Lower Bound). Given Assumptions 3.1 and 4.1, for any fixed E H and with probability least (1 - 8). there exists Ç & (0, 1) such that for n (4-2 +-8/3483)))) 1og(2/6) and y 0, such that the following upper bound holds the tilted generalization error
exp((2kk)
(h, 2 (x
27/ +e log(2/5) 4cxp(hlls.)00g((200) 3n/ 5)
(1 5)hl
(V) (exp(h)lsu) -xx((((s)))
7/2
(Neu - K2)
where & is the training dataset under the distributional shift.
Proof.
The proof follows directly from the following decomposition of the tilted generalization error under distribution
shift,
gen, (h, $) = (4,, Ry (h, / sn) Ry (h, H) - (h, (h, ()) (h, S)
Is
16
17
where Is, Is and I7 be bounded using Lemma C.9, Proposition 4.2 and Proposition 3.4, respectively.
Theorem 4.3 (Restated). Under the same assumptions in Theorem 3.5, then for (4> 4883/24//33
C exp((2mka) and
Y O, and with probability at least (1 - 5), the absolute value of the tilted generalization error under distributional shift satisfies
sup NCW
Igen, (h, $)1
(72)
s 2exp(1>) ( kin)
2+ B(8) +
4exp(/=|k.)B(0) 3n/11(1 -C)
(1 - 5)
TV(, Di) (exp(1/(k)))
- exp((1/xaa)
+ 11/lsx/+e +
72
(Niu Ks)
where (()) log(card(HI) + log(2/8).
Proof. The result follows from combining the results Proposition E.2, Proposition E.3, and applying the union bound.
Theorem 4.5. Under the same assumptions as in Theorem 3.11 and Assumption 4.4, the following upper bounds on absolute expected tilted generalization error hold under distributional shift,, if (a) or (b) hold,
gen, ge, (H, - exp(I)((a)) G(I(H:;)) + 1n1 tte + m--e)
1/1(1 () (exp(1>/xx)) - exp(1>\1aat)
TV(, (i)
+
22
(Kr (Kee)
where if (a) and (b) hold we have G(T(H; = / 22x ((HH) and if (c) holds, we have, G(I(H:S)) + 2
I(H:8) +
Proof. The proof follows from Theorem 3.11 and Assumption 4.4. Note that, we have,
0 s PH @ - R, PH & 1) - h/*x!tt. ltc
(73)
- h1 s RH,H, PH.S) -Er, RH, < 0.
27

---

Generalization and Robustness of the Tilted Empirical Risk
We also have in similar approach Proposition 4.2,
log log(Eprsulexp(>)(H)) Z))) -
Z)1)
(74)
(ex((1)lxa)) exp((2|(ist)
TV(Pи @ H1 PH @
7/
(Kr Kott)
Note that TV ,b, PH X (V Combining Theorem 3.1 with (74) and (73) completes the proof.
E.1. Convergence rate under distribution shift
In this section, we study the convergence rate under distribution shift. Suppose that we have some outlier samples in training dataset with distribution v. Then, we can assume that jú - T) + for some [0, 1]. We analysis the following term in Theorem 4.3,
TV (i) ( (exp(I)<ru)) -ex((p(xx)) ?/
(75)
(Nir Kis)
(xpphh11sa)-cxp(//sss 0(7). Furthermore, we have,
Using Taylor's expansion, we can show that
(Ku)
[[ 112 lu- i2/dz
TV(,
11 - v/dz
(76)
< (
S 2T.
Therefore, we have,
TV(4 (i) (exp(h)lsu) -xxp((/)s))-xp(((pp))))))))))))) = (-)
(77)
72
(Ku ks)
In general, choosing 7 = On ((n=1/(++e) for n 2 [dn. d +8/35) log(2/6) we have the overall convergence rate on absolute (2 expll 2na)
titled generalization error, max (0 (0(rl/(Ct)) .0 (n-o/((+=))
Note that choosing O(1/n), we can have the convergence rate of O(n (n-=/((+e)) For example, we have one outlier sample, we can choose T n+11
F. Proof and details of Section
Proposition 6.1. The solution the expected TERM regularized via KL divergence, (24), is the tilted Gibbs Posterior (a.k.a. Gibbs Algorithm).
P H
TH
n exp() 2.))
-a/7
(78)
S
(())
n 1=1
where (S) normalization factor.
Proof. From (Zhang, 2006), we know that,
p
min Epy [f())++ KLLPx Px
(xx),
(79)
a
where PX- Qx exp(-af(X)) Using (79), it can be shown that the tilted Gibbs posterior is the solution to (25).
Lox (xx]]
28

---

Generalization and Robustness of the Tilted Empirical Risk
Proposition 6.2 (Restated). The difference between the expected TER under the joint and product of marginal distributions of and S can be characterized as,
[H;
R, Pa 2 p)) (H,
(80)
a
Proof. As Aminian et al. (2015), the symmetrized KL information between two random variables (S, H) can be written
ISKL (H: S) Pp Sp [log( Pn s)l En (og((P)s))]
(81)
The results follows by substituting the tilted Gibbs posterior in (81).
Theorem 6.3 (Restated). Under the same Assumptions in Theorem 3. 1. for some E (0, 1). the expected tilted generalization error of the tilted Gibbs posterior satisfies
2a cxp((277(ka)rr, l+ 0 S gen. (H,
1111
a + 2/7/' 10 1tc
(82)
(1 ()2n1112--
(1 9-h
Proof. We expand
gen, (H, R(H, - @ nm)
+ (, Pn 0p00) - R. (H, PH @H)
(83)
+ R. (H, Pn @ -R,
+ (H, Pn.s) (H,
From Proposition 6.2, have,
R, PH @ p) PH.s) ISKL (H:;
(84)
a
We also have,
17/-m00
0 0 R(H, Pb ² - RH, PH @ p S
2
(85)
0 5 R, PH 8 8n) (H, PH p1) - 1//5x( (1+e)
- -h m (1+))
< R, PH.s) (H, I 0.
(0,1) such the following upper bound absolute value of non-linear expected generalization error holds provided that 1 < tr e exp(1)kn) and 2" +1 + ((H:))
From Theorem 3.11, there exist Ç
exp(2))s))
RH, Pn p.) R,,H, PH.s)) exp(17/mm)
2x 1 | h/
(86)
(1 -hi V
Using the fact that ((H:S) < ISKL. (H; we have the following inequality by considering (84) and (86).
I(H; S)
exp(1t(me)
2x t h
<
+11 1+c
(87)
a
where results in ST( & A+VA44B have,
2
< A + VB, where A= =
11-00mm V
aexp((>/me)
(1-C)ll
oftie and = a// We
a eep((1/151)
2 2x|+t/7/2+e
alrl=ntte 1tc
T(H:S)
V
(1 5)
29

---

Generalization and Robustness of the Tilted Empirical Risk
where C' is constant independent from n. Therefore.
2a expp exp(hy)ka))x:* //l
2a V n
[H, @ p) (H,
2///5*/
(88)
(1 (1- (1-6) 2)2n/1/--
- (1-
Combining (88) with (85) completes the proof.
G. Experiment Details
Data-Drived choice of Tilt: A similar discussion in Section 4 applies the upper bound on the expected tilted generalization error under distribution shift in Theorem 4.5. However, in the large regime, the results remain the same.
Logistic Regression: For logistic regression, we consider 500 samples from 2d Gaussian distributions, WV 1) x (1, 1) and (V(10,,) 1) x (M,,, 1). For logistic regression, we consider 0.01 as learning rate and 10000 iterations. Our loss function is (hh, 2) log(1 + exp(-yt yh"x))) for h E H. R.?.
Gaussian Outlier: We add outlier samples p x 1000 from Gaussian distribution (-400,5) (-440, 5).
Pareto Outlier: Note that for ~ Pareto(L, a) as a heavy-tailed distribution, we have fz(z) Z0rT. We consider a 1.5 to have unbounded variance (heavy-tailee tailed distribution). We add outlier samples p X 1000 from Pareto distribution to Gaussian true sample dataset.
ddata computation: suppose that have samples as outlier, {īg}ā=1 We model the distribution shift follows,
n
m n +
E j=1
P(Z = 8j) ΣE P(Z 2x)) k==
N(()),.00))
(89)
m
where P(Z 2j) is the probability of j-th outlier data sampled from Gaussian or Pareto distribution. Then, we have,
/
TV(,
fz|dz -uddd
< 17
P(Z = 2,) (23
(90)
m
m km P(Z = 2x)
2m
n
where z is Gaussian distribution as data generating distribution. We calculate the empirical values of k., using the true dataset and K2 using the training dataset containing outliers. Then, we consider the Hypothesis space as the set of parameters where the (1 <)-th moment of loss is bounded by empirical st.+e For Gaussian, consider distribution with 1.5 consider 0.5. The Logistic regression scenario under Gaussian and Pareto outliers with 10 and 5 number of samples, respectively, are shown in Fig. 1.
and for Pareto
Logistic Regression without outlier: Similar to the distribution shift scenario, we can propose a data-driven inspired by Corollary D.I. For this purpose, we assume that n large enough and y is a small negative value close to zero. Additionally, we assume that the first term in the upper bound of Corollary D. is zero due to large n. For simplicity in computation, we consider exp(-7x..) for small ?. Under these assumptions, we define:
1>d 2
4B(6) 3n 3m/ {)
Ydata := arg min
(91)
(-(00))) 2
where B()) is defined in Corollary D.I. Note that the term B(8) can be large due to the cardinality of the hypothesis space, resulting in very small In this scenario, we expect that near zero would have better performance.
Now, we conduct an experiment for logistic regression problem by sampling from a Pareto distribution as a heavy- tailed distribution without outlier. We observed that TERM achieves better population risk with an optimal negative
30

---

Generalization and Robustness of the Tilted Empirical Risk
Logiss sugresden wis Gausi Outker
Logisli Pegresion a with Purci oudier
Clack
Class 2
10
Cort
-10
-3
(a) Logistic Regression with Gaussian Outlier
(b) Logistic Regression with Pareto Outlier
Figure 1: Logistic Regression Experiments with Outlier
tilt near zero. In this scenario, the data-driven performed similarly to the ERM solution. However, the optimal solution based on grid search outperformed the ERM solution. The experiment was conducted with 1,000 training samples and we have 7 0..263 = 0.0001, R(h,- (5), p)= 0.05220 + 0.00001, ((hurs(S)) p1) = 0.05249 0.00002, Ydata -0.0001 + 0.0000 and R (R ($). -)= 0.05249 + 0.00001.
Linear Regression: We also consider the Linear Regression toy example as mentioned in (Li et al., 2021) where the loss function is square loss function E(h, 2) 1 (h² x y) for h H c RR2. Similar to logistic regression, we consider two scenario. One, the outlier is Gaussian, and another case where the outlier is Pareto, where consider 2000. For true data, consider X ~ (1, and y
0.5 (10, 0.5). For outlier, consider
Gaussian outlier: Xouther (M-10, 0.5) and Youtlier (2,20.5))
Pareto outlier: Xoutlier ~ 21 1) and Youtlier ~ P(1.5, 1), where P(1.5, 1) is Pareto distribution with shape and scale equal to 1.5 and 1, respectively.
The results are reported in Table 5 and Table 4. The linear regression scenario under Gaussian and Pareto outliers with 10 number samples are shown in Fig. 2.
Table 4: Linear Regression with Pareto Outliers: Results averaged over three runs (n = 2, 000 samples), showing mean + standard deviation.
P
7*
(Sh,,-()).
R(hers ($).
Ydata
R(h ($). (4)
0.049%
-0.26667 + 0.0555
0.12530 + 0.0001
0.25795 + 0.0001
-0.1000 + 0.0000
0.12530 + 0.0002
9.13%
-0.7000
0.0000
0.12183 + 0.001
0.6731 + 0.0045
-0.3333 + 0.04222
0.1700 + 0.0005
16.70%
-1.43333 + 0.1155
0.1238 0.0002
0.7580 + 0.0006
-0.5333 = 0.01555
0.2755 = 0.0001
33.35%
-1.8000 0.0200
0.1275 0.0001
1.5096 + 0.0050
-0.2333 + 0.0022
0.3972 + 0.0002
44.45%
-2.43333 + 0.0088
0.1229 + 0.0001
2.2190 + 0.0011
-0.1000 + 0.0000
0.4908 + 0.0001
Linear Regression without outlier: In this scenario, we consider linear regression based on training samples from a Pareto distribution with shift parameter equal to 1.5. We observe that f 0.0000, R(h,- (S), / 6..4924 R(BERSd ($), (.) 20. 73892 + 12.9752 and "itta 0.000 0.0000 and R(h ($), 1)) 19. 0.005249 + 10.4675.
31

---

Generalization and Robustness of the Tilted Empirical Risk
Table 5: Linear Regression with Gaussian Outliers: Results averaged over three runs (n = 2, 000 samples), showing mean - standard deviation.
R(hy.(S), pc)
(S)
R( (S), p))
P
TYata
0.049%
-10.0000 + 0.0000
0.7555 + 0.0000
1.19923 + 0.0001
-3.6333 + 0.0288
0.75617 + 0.0001
9.13%
-0.1000 + 0.0000
0.16095 + 0.0001
0.3215 = 0.0005
-3.8000 + 0.3466
0.17083 = 0.0009
16.70%
-3.4000 + 0.1000
0.15515 + 0.0000
0.31122 + 0.0002
-3.9000 + 0.0001
0.15796 + 0.0001
33.35%
-0.1000 = 0.0200
0.1564 = 0.0000
0.3127 + 0.0001
-5.0666 + 0.0022
0.15858 + 0.0000
44.45%
-3.43333
0.0001
0.1530 + 0.0001
0.3070 + 0.0001
-5.8000 + 0.0080
0.15399 + 0.0001
Livear regeeiiiin (Caumten Outd
Uiear Regresato Oha Pareto Dutler)
125
ground cus
TSMM Optnaalt:
202-
15
eapr caste
-24
-50
1999 Den pope
32.
(a) Linear Regression with Gaussian Outlier
(b) Linear Regression with Pareto Outlier
Figure Linear Regression Experiments with Outlier
H. Generalization Bounds for Bounded Loss Functions
Upper bounds under linear empirical risk for bounded loss functions via information theoretic and uniform bounds are studied by Shalev-Shwartz & Ben-David (2014) and Xu & Mannor (2012), respectively. Inspired by these works, in this section, we provide upper bounds on the tilted generalization error via uniform and information-theone bounded loss functions with the convergence rate of O(1/ which is similar to generalization error under linear empirical risk. The following results are derived for bounded loss function scenario,
approaches for
Uniform bounds
Information-theoreee bounds
KL-regularized TERM under bounded loss function
Rademacher Complexity bounds
Stability bounds
PAC-Bayesian bounds
The theoretical analysis in this section hinges on two fundamental properties: the Lipschitz continuity of the logarithmic function on a bounded interval and the boundedness of the loss function. When working with bounded loss functions, we can analyze the positive tilt scenario. Furthermore, the bounded case does not restrict us on sample size n that would otherwise be necessary in the unbounded scenario.
32

---

Generalization and Robustness of the Tilted Empirical Risk
H.I. Uniform bounds for bounded loss
In this section the following assumption is made.
Assumption H.1 (Bounded loss function). There is constant M such that the loss function, (h2 ((b,2) satisfies 0 S E(h, z) S M uniformly for all h H, E Z.
For uniform bounds of the type (6), we decompose the tilted generalization error (4) as follows,
gen, (1, R(h,, n1) R2 1 00) + Ry (b, & Ry (h S);
(92)
where / is the difference between the population risk and the tilted population risk, and I2 is the non-linear generalization егror
We first derive an upper bound on term 1 in the following Proposition.
Proposition H.2. Under Assumption H.I, for, r R. the difference between the population risk and the tilted population
risk satisfies
Var Var (ex)(()(())))) & R(h, - (1)) -exp(-27AM)
(exp(r(((), Z))).
(93)
27
2-
Proof. For any
H we have
()
B[e(h, Z)1
log (ex(()((b, 2)))
1
exp(-2yM1 exp(2re(h, 2))
Ez~n -log lllo@(epp//) (exp(77(h, 2)))
1>/
2
exp(- exp(-277M
exp(27e(1, 2))]
(94)
1
log(E(exp(7<(hh))]]]
Var(exp(7ell) Z)))
2/71
exp(-2y.M) Var(exp(>((h, 2)))-
R2 1,, +
2/1
A similar approach can be applied for y > 0 by using Lemma C.4 and the final result holds.
Note that for y + the upper and lower bounds in Proposition H.2 are zero. the log function is Lipschitz on a bounded interval, applying the Hoeffding inequality to term Ln and Proposition H.2 term 1 in (13), we obtain the following upper bound on the tilted generalization error.
Theorem H.3. Given Assumption for, for any fixed h E H with probability least (1 6) the tilted generalization error satisfies the upper bound,
(h. -exp(-2y.0 Var (exp(r((h,2)) + (exp(I>)M) M) MM-1) -1)
log(2/6)
(95)
27
hy
2n
33

---

Generalization and Robustness of the Tilted Empirical Risk
Proof. We can apply the Proposition H.2 provide upper bound term /1. Regarding the term Is. have for 7
Ry (h, 11 (n) - S)
1
(og (
Σ
n
exp(7e(h, Z))l)
log(
exp exp(7e(h, 2.)))
7
n1
exp( -M
LE Im (exp())((, 2))]
Σ exp(1 2:))
(96)
1y/
- 1og((/0)
2n
Similarly, for > 0, we have
(exp(rM) 1)
log(2/8)
Rg (h, (h, I
(97)
hy
2n
Combining this bound with Proposition H.2 completes the proof.
Theorem H.4. Under the same assumptions of Theorem H.3, for a fixed H. with probability least (1 8), the tilted generalization error satisfies the lower bound
-1
Var (exp(re(h,2)) (cxp(h)MM) - 1) 1og(2/5)
gen (h,
(98)
27
hy]
2n
Proof. The proof is similar to that of Theorem H.3, by using the lower bound in Proposition H.2.
Combining Theorem H.3 and Theorem H.4, we derive an upper bound on the absolute value of the titled generalization error.
Corollary H.5. Let A(r) (1 - exp(7 Under the same assumptions in Theorem H.3, with probability at least (1 - 8), and a finite hypothesis space, the absolute value of the titled generalization error satisfies
(exp(I>iM) 1)
log(card(H() + 1og(2/5) max(1, exp(-2x))())))))
sup Igen, S)) N bEH
hyl
2n
8/71
where A(r) = (1 exp((>)))
Proof. We can derive the following upper bound on the absolute of tilted generalization error by combining Theorem H.3 and Theorem H.4 for any fixed h E H
igen, (h, S)] (exp(I>\M) (M) 1) log(card(H)) + log(2/8) max(1, exx(2())xp(222
(99)
hl
2n
8/7]
where A(7) = (1 (1-cx(())))) Then, the final result follow by applying the uniform bound for all H. using (99).
Corollary H.6. Under the same Assumptions as in Theorem H.3 and assuming y is of order ( for 3 > 0, the upper bound on the tilted generalization error Theorem H.3 has a convergence rate of max (O(1/ /n). O(n -B)) as n + co.
Proof. Using the inequality
< log(1 + +:) S x and Taylor expansion for the exponential function,
1r
333
exp(h/MM = 1 + by M +
+
+ +0
(100)
2
34

---

Generalization and Robustness of the Tilted Empirical Risk
it follows that
(cxp(|>lM)- 11
h|/2²
h
h7| 2 M
+ 0
(101)
2
6
This results in a convergence rate O(1/ for [exp()>\M)-1)
(og(card(()))))) (l) under y ->
Ir]
2n
For the term max(1,exp(-- ( using Taylor expansion, we have the convergence rate of O(hl) for the first term; this completes the proof.
8/ry
Remark H.7. Choosing 3 2 1/2 in Corollary H.6 gives convergence rate of O(I/vR) for the tilted generalization error.
Remark H.8 (The influence of y). As + the upper bound in Corollary H.5 on the absolute value of tilted generalization converges to the upper bound absolute value of the generalization error under the ERM algorithm obtained by Shalev-Shwartz & Ben-David (2014),
sup (g, S) & My log(card + log(2/6) NER
(102)
2n
In particular, (exp(I7) 1)/17l M and the first term in Corollary H.5 vanishes. Therefore, the upper bound converges uniform bound on the linear empirical risk.
Using Corollary H.6, we derive an upper bound on the excess risk.
Corollary H.9. Under the same assumptions in Theorem H.3, and a finite hypothesis space, with probability at least (1 - 8), the excess risk of tilted empirical risk satisfies
C,(1) 2(exp(h)lM) 1) log(card (H)) ) 1og(2/5) Iyd
+
2n
8/1l
where A(r) = =(1 (1- ex)
Proof.
It can be proved that,
(H) < 2 sup (h,
bEH
and
((K)(S). < (,, +U <R +U S &R(N (H), +U, where U = SuPлEи [R(h, p)) - R,, 5) = SuPлEи gen, S).
Note that supлEH ggen, (h, Sh) can bounded using Corollary H.5.
H.2. Information--therrete bounds for bounded loss functions
Next, we provide an upper bound on the expected tilted generalization error. For information--hhorree bounds, we employ the following decomposition of the expected tilted generalization error,
gen (H, (R(H, @ μ) - R,, @ 4 [0)) + (H, & (H,
(103)
The following is helpful deriving the upper bound. Proposition H.10. Under Assumption H.l, the following inequality holds,
(H, (H, PH s n an) - R,, PH.s) (exp(l>lM) - 1)
I(H;
I
ly|
2n
Proof. The proof follows directly from applying Lemma C.15 the log(.) function and then applying Lemma C.14.
35

---

Generalization and Robustness of the Tilted Empirical Risk
Using Proposition H.10, derive the following upper and lower bounds the expected tilted generalization error.
Theorem H.11. Under Assumption H.1, the expected tilted generalization enror satisfies
(cxp(1?|M) - 1)
[(H:5)
(xxp(->M)
(1 1 ) [ar Zarzzall (((H, 2))
gen, (H,
[7]
2n
Proof. We expand
gen, (H,S) ge, = Rn PM 0)) (H,
H, Pnr 2 0n) (H, Prr & p - R, Pn.s).
(104)
Using Proposition H.10, it follows that
(exp(17|M) - 1)
I(H;S)
PH @ @n)
(H,
|y| V
(105)
2n
Using the Lipschitz property of the log(.) function under Assumption H.1, we have for >> 0,
R(H, & μ²) (H, PH & ))))
=Erropan _ log(exp(
(H, (.))) - EruSa log(
exp(>7(H, 2))))
1=1
1=1
exp(-7M
EPr@Ntn E
exp(
2 Σ 8(H, E.))
1 Σ
exp(1e(HH, Zi))
11
71
(106)
-exp(
M RPM
(-
n
72 2H,, 2,)2)
n
7((H, Z:))
27
exp(->M) (1 I/ Var a~n (HH,2)))
27
eep( cxxp->>M> 1/n)Err [Var Za (C(H, 2
2
where 2 ~ μ. A similar results also holds for < 0. Combining (105), (106) with (104) completes the proof.
We now give lower bound via the information cieemattoo--hhoretiic approach.
Theorem H.12. Under the same assumptions in Theorem H.1 the expected tilted generulization error satisfies
(exp(I>lM) - 1) I(1;5)
yexp(>M)
1 )) [Var [Varz,, (E(H, ((),
gen gen, (H.
(1
hy]
2n 2
n
Proof. Similarly as in the proof of Theorem H.11, we can prove the lower bound. Using the Lipschitz property of the log(.)
36

---

Generalization and Robustness of the Tilted Empirical Risk
function under Assumption H.I, we have for y 0,
R(H, Pa @ p
Ry H. PH @ 4 ))
R
BPH on - log( Σ a
1
E P
lox(
(H, Z()))]
exp(>e(H) 2)))
72
n
1 EPHRNON
exp(
(HH
Σ exp(> Z:))
7
i=1
(107)
-)
( Σ EH, Zi)²)
(np Σ (H, 2.))²)
E EPreS
24
-)
(1 - PE Var Varzmp (,, (H,
24
-7exp(? (1 EP 2~ (((H, 2))
2
Similar results also holds for < 0. Combining (105), (107) with (104) completes the proof.
Combining Theorem H.ll and Theorem H.12, we derive upper bound on the absolute value of the expected tilted generalization error.
Corollary H.13. Under the same assumptions Theorem H.11, the absolute value of the expected titled generaliza- tion error satisfies
gen (H, ح
(exp(h)MM - 1)
V
T(H:S)
2n +
h|M² (xT(exp(h)M)
(
(108)
h
8
Proof. We can derive the upper bound on absolute value of the expected tilted generalization error by combining Theo- rem H.ll and Theorem H.
Remark H.14, In Corollary H.13, we observe that by choosing 7 = O( (),, the overall convergence rate of the generaliza- tion error upper bound is max / /n), ((=2)) for bounded S). For / 2 1/2, the convergence rate of (108) is the same as the convergence rate of the expected upper bound (Xu Raginsky, 2017). In addition, for 7 - 0, the upper bound Corollary H.13 converges to the expected upper bound in (Xu & Raginsky, 2017).
Similar to unbounded loss function, the results in this section are non-vacuous for bounded ((: this assumption is violated, we can apply the individual sample method (Bu et al., 2020), chaining methods (Asadi et al., 2018), or conditional mutual information frameworks (Steinke & Zakynthinou, 2020) to derive tighter upper bound for the tilted generalization error.
1.2.1. INDIVIDUAL. SAMPLE BOUND DISCUSSTON
We can apply previous information-theoret bounding techniques (e.g., (Bu et al., 2020), (Asadi et al., 2018), and (Steinke & Zakynthinou, 2020)), exploiting the Lipschitz property of the logarithm function (or Lemma C.10) over bounded support. For example, to derive an upper bound based on the individual sample (Bu et al., 2020), using the approach for Proposition H.10 and Lemma 10 we have for 7 > O, we have
1
n exp (pp(((H,,)))
n Σ exp exp(7)((, 2.))) n
(,, PH 2 T²) Ry (H, PH.s) S Epagpen
Epn.s
n
(exp(>M) - 7 1
[(H:Z.)
(109)
72
2
where for the first equality, we applied the Lemma C.10 and for the second inequality, we use that S exp(>y(H, Z,)) < exp(yMM for 7 > and the approach in (Bu al., 2020) for bounding via individual samples. A similar approach also can
37

---

Generalization and Robustness of the Tilted Empirical Risk
be applied to y < 0. Therefore, the following upper bound holds the absolute value of the expected tilted generalization error,
(H, (exp(hy|M) - 1) n
T(H; Z+)
1 exp((>|M)
(1- ) 12
gen, (H,
17/12
2n
H.3. The KL-Regularized TERM Problem
In this section, similar to unbounded case (Section 6), we study the KL--regularized under bounded loss function for both negative and positive tilts. We consider the same definitions in Section 6. We next provide parametric upper bound on the tilted generalization error of the tilted Gibbs posterior under bounded loss function.
Theorem H.15. Under Assumption H.I, the expected tilted generalization error of the tilted Gibbs posterior satisfies,
alexp(1>)M) 1)²
Var(exp(7e(H, ())) (1/n- exp(- (xp(--yyM).
gen gen, (H,
(110)
272n
24
Proof. Note that, have
S (H;
RR, (H, PH μ) - (H, (H, PH.s)
(111)
(H, PH 11 S*)) RH, PH.s)
(exp(I>|M - (H
2n
Therefore, we have
I(H;5)
(exp(1/IM) 1)
IHH
(112)
2n
Solving (112), results in,
VIHHSS) a (exp(I>|M) - 1)
|m|
V
2n'
(113)
Therefore, we obtain,
(exp(I>|M) 1)²
RH, 2 Tr) (H, PH,s)
(114)
272n
Using Theorem H.11, the final result follows.
Similar to Corollary H.13, we derive the following upper bound on the absolute value of the expected tilted generalization error of the tilted generalization error.
Corollary H.16. Under the same assumptions in Theorem H.15, the absolute value of the expected tilted generalization error of the tilted Gibby posterior satisfies
gen (H, a(exp(/7lM) - 1)2 h|/2 exp(lr))( (1 (1-2) 1)
(115)
2r2n
Remark H.17 (Convergence rate). = O(1nn) then we obtain theoretical bound on the convergence rate of O(1/n) for the upper bound on the tilted generalization error of the tilted Gibbs posterior.
Remark H.18 (Discussion of 7). From the upper bound in Theorem H. H.15, we can observe that under y + 0 and Assumption H.1, the upper bound converges to the upper bound on the Gibbs posterior (Aminian et al., 2021a). For positive tilt (y > 0), and sufficient large value of n, the upper bound in Theorem H.15, can be tighter than the upper bound on the Gibbs posterior.
38

---

Generalization and Robustness of the Tilted Empirical Risk
In addition KL-regularized linear risk minimization, the Gibbs posterior is also the solution another problem. For this formulation recall that the a-Rényi divergence between P and Q is given by R. (PII) - log
dQ), for a (0, (1, oo). We also define the conditional Rényi divergence between Pxiy and Qx R., (Pxly Qxxy Pr) (r) :=
Sx
dP aq
a dQ
a-1 Ep log (Ix ( dQxxr)) for E (0,1) U (1, Here, Pxjy denotes the conditional distribution of X given Y.
Proposition H.19 (Gibbs posterior). Suppose that y 1 - and a (1,,))(1,oo) Then the solution the minimization problem
log EEPas cxp (TR(H, + Ra (P
Piis = arg inf
Eps
(116)
PHis
l
with R(H,S) S) the linear empirical risk (1), and the Gibbs posterior,
TH (exp( (R
Pis
Ex (exp(- (xp(->)R(H,S))
where Hh is the prior distribution on the space H of hypotheses.
Proof. Let us consider the following minimization problem.
{ (ex(( (R
find arg min Py
(117)
where 7 = - 1. As shown by Dvijotham & Todorov (2012), the solution to (117) is the Gibbs posterior,
Qr exp(-af(()))
Py Egy [exp(=oo(((]]
If -> 1, then 7 + 0 and (116) converges to the KL-regularized ERM problem.
The tilted generalization error under the Gibbs posterior can be bounded as follows.
Proposition H.20. Under Assumption H.l when training with the Gibbs posterior, (26), the following upper bound holds on the expected tilted generalization error,
Maa Var(exp(7((H1, Z)))
gen (H,
<
exp(-27.M
(118)
2n
27
Proof. Let consider the following decomposition,
gen (H = RHH, PH & p))
Ep
((H + Epn.
E(H, - RHH
(119)
From Aminian et al. (2021a), for the Gibbs posterior we have
R(H, Pr p) - Epn. 1 Σ E(H, ((H,
1
aM2
<
2n
In addition, using Lemma C.4 for uniform distribution, we have
Σ log (H)) log H exp(?t((,,
Var(exp(>1(EE) Z)))
27
This completes the proof.
39

---

Generalization and Robustness of the Tilted Empirical Risk
Furthermore, provide upper bound the absolute value of the expected tilted generalization emoor under the Gibbs posterior,
Ma 2n
gen (H,5)
8y (1 - exp(r>())
(120)
In (120), choosing 7 = ((1/n) we obtain a proof of convergence rate of ((1/n) for the upper bound on the absolute value of the expected tilted generalization error of the Gibbs posterior.
H.4. Other Bounds
In this section, we provide upper bounds via Rademacher complexity (Bartlett & Mendelson, 2002) and PAC-Bayesian approaches (Alquier, 2021) under bounded loss functions assumption. The results are based on the assumption of bounded loss functions (Assumption H.I).
H.4.1. RADEMACHER COMPLEXITY
Inspired by the work (Bartlett & Mendelson, 2002), we provide upper bound on the tilted generalization error via Rademacher complexity analysis. For this purpose, we need to define the Rademacher complexity
As in Bartlett & Mendelson (2002), for a hypothesis set of functions h X' + V. the Rademacher complexity with respect to the dataset
Rs(H) == Es,or NEW
sup
Σ oxh(X.))
where = {o are i..d Rademacher random variables; E {-1,1) and 1 or or -1 with probability 1/2, for i [n]. The empirical Rademacher complexity RHH with respect to S is defined by
(H)) = E.
sup bEH
Σ (x))
(121)
To provide upper bound the tilted generalization error, first, apply the uniform bound, Lemma C.11, and Talagrand's contraction lemma (Talagrand, 1996) in order to derive high-probability upper bound on the tilted generalization error; we employ the notation (121).
Given Assumptions H.1 and assuming the loss function is My Me-LLipschitz-conimuon in binary classification problem, the tilted generalization error satisfies with probability at least (1 5) that
Proposition H.21.
(h, < 2exp(h))M)M,,RR((H)) + 3(exp(1>|MM - 1) log (1/6)
|y]
2n
Proof. Note that exp(>M) < x < 1 for < 0 and < x & exp(yM) for > 0. Therefore, we have the Lipschitz
constant exp(->M) and for negative and positive 7, respectively. Similarly, for exp(yx) and < x < M, we have the
40

---

Generalization and Robustness of the Tilted Empirical Risk
Lipschitz constants 7 and eep(ryM), for 0 and 7 0, respectively. For < 0, have
gen, (h, S) = ?
log 2)1l log
exp (7é(h, 2,))
log (B2=)(oxp(><(hh, Z]]l) log
exp (ye(h, Z.))
log (Bzmzlexp(> 2))1) log
exp (n Zi))
IAB
exp( (-M)
BZ 2T)
Σ exp (re(h, ()((h,Z)))
(122)
17/
exp(->MM
RR L H) 3exp(->-M exp(>MM)
log(1/6)
2n
2exp(=>>)))pppp H) + 3exp(->MM[ exp(yM))
(o/()
2n
(4) 2exp(~>M)MM,-9 + 3(exp(->M) - 1)
log( 1/8)
h
2n
where (a) holds due to the Lipschitzness log(z) in bounded interval, (b) holds due the uniform bound Lemma C.111 (c) and (d) hold due to Talagrand's contraction Lemma C.12).
Similarly, prove for y O, have
gen. < s 2esp(? + 3(exp(>M) 1). -1)
log(1/6)
(123)
?
2n
Then, obtain an upper bound the generalization error by combining Proposition H.21, Massart's lemma (Massart, 2000) and Lemma C.4.
Theorem H.22. Under the same assumptions as in Proposition H.21, assuming a finte hypothesis space, the tilted generalization error satisfies with probability at least (1 8) that
gen S) max(1, (1, cxp(-27MD)
(exp(> 1)2 + 2AMr B V 2 llgrrc (())))))))) (H)
87
+ 3(A(7) 1)
1og(1/5)
hl
2n
where A(r) = ex)(h)lM and B maxNER
(Einh?(2))) (2)))
Proof. We consider the following decomposition for the Rademacher complexitt.
gen. (h, S) R(h, (1) (h, " + (h,
(h, / Sn) ) (h,
where R(h, - (h, S") can be bounded using Proposition H.2. The second term can be bounded by using Proposi- tion H.21 and Massart's 's lemma (Lemma C.13).
Similar to Remark H.7, assuming = 0(1/ we have the convergence rate of O(L/Vn) for the tilted generalization error. For an infinite hypothesis space, covering number bounds can be applied to the empirical Rademacher complexity, see, e.g., (Kakade et al., 2008). We note that the VC-dimension and Rademacher complexity bounds are uniform bounds and are independent of the learning algorithms.

---

Generalization and Robustness of the Tilted Empirical Risk
H.4.2. A STABILITY BOUND
In this section, we also study the upper bound on the tilted generalization error from the stability perspective (Bousquet Elisseeff, 2002b). In the stability approach, (Bousquet & Elisseeff, 2002b), the learning algorithm is deterministic function of S.
For stability analysis, we define the replace-one sample dataset as
(() = Lz. .. Z,..... ................................ Zn
where the sample Z; is replaced by an i..dd data sample 2, sampled from p. To distinguish the hypothesis in the stability approach from the uniform approaches, we consider h, - -> H as the learning algorithm. In the stability approach, the hypothesis is a deterministic function (S) of the dataset. We are interested in providing an upper bound on the expected tilted generalization error Eps [gen,,
Theorem H.23. Under Assumption H.1, the following upper bound holds with probability least (1 under distribution Ps.
Ps gen, (h,
(1 - exp( (1 (1+ (1+ + exp(H))M)),, ((),
(124)
8y
Proof. We use the following decomposition of the tilted generalization error;
Eps [p
Epg
(S),
(os(Cerguueep((((hbs5s5111111111 7
Σ Bog(Ers on (e), 2))) - log Ers n 1=1
exp() 2))
(125)
+ Eps
1 (s)) R. (ha))),
Eps
log
Eps
n
Using Lemma C.4, we have
1
Ep [(ha(S),,))
B.. (es 2)))]
24
and
n1 Σ Ers n
Eps
log
exp()((h,(S)) R. (h,)
1
(1 Σ
1 (x))(1((h,(S),.) 2)1)
log
Eps (sp()((h,(S)), - Erg
log
7
?
Var exp(>)(h, Z)))
27
Using the Lipschitz property of the log and exponential functions on a closed interval, we have
1
log log(Er, E H
(xxp(>((,.(5)) (ce(EE_s.<xp((((((()))....
7 log Eps n cxp()(((,(33),
= - Log((Brs//exp//((t.tc
log EEs exp(>e(h, 2,1))
s 15 ((h, 2)1l-
42

---

Generalization and Robustness of the Tilted Empirical Risk
Finally, we have
Ep ggnn (S),
< Var (exp(r((h.(S), 2,))) exp(-22 (xp(-2yM)
Var Va (exp))(((s( Z)))
27
+ exp(1/ (oooll/)MMPpssrlllll (((h,) 2) - ((0))
(1 (xp(7))1)) (1 ex=xx((-2xM)) (l ((h,((())) Z)
8y
We also consider the uniform stability as in (Bousquet & Elisseeff, 2002b).
Definition H.24 (Uniform Stability). learning algorithm is uniform B-stable with respect to the loss function the following holds for all S z" and & 2, (S),, 2, (S)). - B, i [
Remark H.25 (Uniform Stability). Suppose that the learning algorithm is f-unnform stable with respect to given loss function. Then, using Theorem H.23, we have
Bps (h. < (1 - (x-exp(>M))²
(x+exp(-27A)) exp(Iy|M)
(126)
8/7
Note that for learning algorithm with uniform 3-stability, where 3 O(1/n), then with y of order (11/n), obtain guarantee the convergence rate of (L/nn).
H.4.3. A PAC-BAYESIAN BOUND
Inspired by previous works on DAC--aaesian theory, see, e.g.((lluiir, 2021; Catoni, 2003), we derive high probability bound on the expectation of the tilted generalization error with respect to the posterior distribution over the hypothesis space.
In the PAC-Bayesian approach, we fix a probability distribution over the hypothesis (parameter) space as prior distribution, denoted as Qh- Then, we are interested in the generalization performance under data-dependent distribution over the hypothesis space, known posterior distribution, denoted Ph.
Theorem H.26. Under Assumption H.l, the following upper bound holds on the conditional expected tilted generalization error with probability at least (1 5) under the distribution Ps: for any 1j > 0,
max(1, (x) -xxp))()exp()MM)))
E
gggg,, (H, (H, 1
8/1l
(127)
n)²(7) (KL(pa Qn)) + log(1/5))
8n
where A(7) = exp(h)]M), Qs and ph are prior and posterior distributions over the hypothesis space, respectively.
Proof.
We use the following decomposition of the generalization error,
Ep [gen,, (H, S)) Ep., (R) R, RH, (H,
The term Ep, ()) R., (H, 44] can be bounded using Lemma C.4. The second term (H, 11) - R,H can be bounded using the Lipschitz property of the log function and Catoni's bound (Catoni, 2003).
Remark H.27. Choosing 77 and y such that 17 1/vn and 7 ((1/vn) results theoretical guarantee on the convergence rate of ((1//m).
43


Reviews:
[{"review_id": "KyGYHM3Ra0", "reviewer": "Reviewer_8SUL", "summary": "This paper studies the generalization error of tilted empirical risk (TERM), a method for fair and robust learning in empirical studies. The paper first studies in-distribution generalization, considering unbounded loss, negative tilt parameters, and finite hypothesis spaces, and gives a convergence rate of $O(1\\sqrt n)$ if the second moment of the loss is finite. Subsequently, the analysis is expanded to distribution shifts. The derived bounds include two bias terms: one arising from the use of tilted loss and the other from the total variation between train and test distributions. A data driven approach is proposed to optimize for the tilt to trade-off between in-distribution and out-of-distribution generalization. Finally, the paper examines mutual-information regularized tilted empirical risk minimization, achieving a 1/n convergence rate, which aligns with findings for the Gibbs posterior, but gets rid of their sub-Gaussian assumption.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "We thank the reviewer for their comments, and generally positive assessment of the paper. We will address their concerns as detailed below. \n\n>Comparison between TERM and ERM \n\n**R1:** We should clarify that we cannot derive an upper bound for ERM in terms of total variation distance if the loss function is unbounded as it would require bounding  the quantity   \n$$\\\\sup\\_{\\\\ell(h,Z)\\\\in\\\\mathcal{L}\\_{\\\\epsilon}}|\\\\mathbb{E}\\_{Z\\\\sim \\\\mu}\\[\\\\ell(h,Z)\\]-\\\\mathbb{E}\\_{\\\\tilde Z\\\\sim \\\\tilde \\\\mu}\\[\\\\ell(h,\\\\tilde Z)\\]| $$\n\nwhere $\\\\mathcal{L}\\_{\\\\epsilon}$ is the set of loss functions with bounded $(1+\\\\epsilon)$-th moment.  \nNote that if the loss function can take arbitrarily large values, then small differences in distributions ($\\\\mu$ an $\\\\tilde \\\\mu$) can lead to potentially unbounded differences in expected risk.\n\n>Total excess risk \n\n**R2**: Due to space limitations, we only briefly mentioned in Lines 290–292 that *\"Using Lemma 3.7, we can derive an upper bound on the excess risk under distribution shift.\"* Specifically, this upper bound on excess risk is twice the generalization error bound obtained via the uniform convergence approach. As a result, we are able to compare the excess risk bounds for both TER and ER. The upper bound is as follows,\n\n$$\n\\begin{aligned}\\\\mathfrak{E}\\_{\\\\gamma}(\\\\mu)&\\\\leq \\\\frac{4\\\\exp(|\\\\gamma| \\\\kappa\\_s)}{(1-\\\\zeta)|\\\\gamma|}\\\\sqrt{\\\\frac{|\\\\gamma|^{1+\\\\epsilon}\\\\kappa\\_s^{1+\\\\epsilon}B(\\\\delta)}{n}} \\+\\\\frac{8\\\\exp(|\\\\gamma| \\\\kappa\\_s)B(\\\\delta)}{3n|\\\\gamma|(1-\\\\zeta)} \\+\\\\frac{2|\\\\gamma|^{\\\\epsilon}}{1+\\\\epsilon}\\\\kappa\\_u^{1+\\\\epsilon}+\\\\frac{2\\\\mathbb{TV}(\\\\mu,\\\\tilde{\\\\mu})}{\\\\gamma^2 }\\\\frac{\\\\big(\\\\exp(|\\\\gamma|\\\\kappa\\_u)-\\\\exp(|\\\\gamma|\\\\kappa\\_s)\\\\big)}{(\\\\kappa\\_u-\\\\kappa\\_s)},\n\\end{aligned}\n$$\n\n where  $B(\\delta)= \\log(\\mathrm{card}(\\mathcal{H}))+\\\\log(2/\\delta)$. Note that, under out-of-distribution, our bound on excess risk for TER is in terms of total variation distance. In contrast, we can not derive an upper bound on excess risk of linear empirical risk with unbounded loss function in terms of total variation distance.\n\n> In-distribution generalization of TERM \n\n**R3:** Thank you for your comment. For TERM under no-distribution shift, we conducted experiments in the Appendix using data driven $\\\\gamma\\_{data}$ derived from Theorem 3.5. In particular, in lines 1519-1536 (Appendix G), we provide experiments for logistic regression without outliers. Furthermore, in lines 1616-1619, we provide experiments to show a data-driven approach for linear regression without outliers (no distribution shift). We thus observe that TERM has an application in the no-distribution shift scenario under heavy-tailed distributions.\n\n> Positive tilt\n\n**R4:** Characterizing the generalization of TERM with a positive tilt is not a goal of our paper. We would like to clarify the main challenges of deriving results for TERM performance with positive tilt ($\\\\gamma\\>0$) under unbounded loss functions (\\*\\*Assumption 4.1\\*\\*). Certain results and theoretical tools in our work are specific to negative tilt and do not extend to positive tilt under unbounded loss function assumption. Specifically:\n\n- **Bernstein inequality** and **the exponential term $\\\\exp(\\\\gamma\\\\ell(h,z))$**: For positive tilt, the exponential term $$\\\\exp(\\\\gamma\\\\ell(h,z))$$ becomes unbounded under Assumption 4.1. As a result, the Bernstein inequality, as utilized in Theorems 4.2 and 4.3 for negative tilt, cannot be applied to positive tilt. In contrast, for negative tilt, $$\\\\exp(\\\\gamma \\\\ell(h, z))$$ remains bounded even for unbounded loss functions. \n\n- **Lemma C.9:** The inequality \n\n$$\\\\begin{aligned}\\\\mathbb{E}\\[X\\]-\\\\frac{1}{\\\\gamma}\\\\mathbb{E}\\[e^{\\\\gamma X}\\]\\\\leq \\\\frac{|\\\\gamma|^{1+\\\\epsilon}}{1+\\\\epsilon}\\\\mathbb{E}\\[|X|^{1+\\\\epsilon}\\],\\\\end{aligned}$$\n\n which holds for $0\\\\leq X$ and $\\\\gamma \\< 0$, is not applicable to positive tilt. Notably, the proof of Lemma C.9 relies on the inequality $e^{\\\\gamma X} \\\\leq 1 \\+ \\\\gamma X \\+ \\\\frac{|\\\\gamma X|^{1+\\\\epsilon}}{1+\\\\epsilon} $, which is valid only for $\\\\gamma X \\\\leq 0.$\n\nTherefore, the theoretical guarantees developed for negative tilt cannot be directly extended to the positive tilt scenario. Addressing this limitation and exploring positive tilt in TERM is an avenue for future work, as mentioned in the Conclusion section.\n\n> analytical form for the $\\\\gamma$\n\n**R5**: The bound in Theorem 4.3 involves **exponential**, **polynomial**, and **inverse powers** of $\\\\gamma$. There may be a numerical minimizer for this upper bound, but the complexity of the expression prevents us from solving analytically in a tractable way. For this purpose, we analyzed the behavior of the bound in the asymptotic regime $\\\\gamma=0$ and $\\\\gamma\\\\rightarrow \\-\\\\infty$.", "claims_and_evidence": "The comparison between TERM and ERM is not sufficiently addressed. L292-L312 in section 4 claims that an upper bound for ERM in terms of total variation is not feasible. A lower bound for ERM's generalization error would have supported this argument. Additionally, the comparison between generalization gaps are insufficient, because the total excess risk is the sum of the empirical risk and the generalization gap. An upper bound for the total excess risk would consolidate the result.", "methods_and_evaluation_criteria": "The insights are not fully addressed for the in-distribution generalization of TERM (section 3). How does its excess risk compare to that of ERM? It is stated in the abstract that TERM has a novel application under no distribution shift. However, its advantage over ERM is not revealed in this case.", "theoretical_claims": "I did not observe obvious errors throughout the theory though I have not checked the proofs. The results are built on finite hypothesis class and negative tilts.", "experimental_designs_or_analyses": "Simulation studies are conducted to validate the data-driven selection of the tilt.", "relation_to_broader_scientific_literature": "This paper is the first to establish generalization bounds for TERM, as claimed in the Related Work section. Notably, TERM improves robustness against outliers with negative tilt and improves robustness under subpopulation shift with positive tilt. However, this paper only addresses the negative tilt, thereby somewhat limiting its significance.", "essential_references_not_discussed": "Related works are clearly discussed.", "other_strengths_and_weaknesses": "This paper is well-written, with coherent logical flow. Propositions serve as proof sketches.", "other_comments_or_suggestions": "NA", "questions_for_authors": "Is there an analytical form for the $\\gamma$ that minimizes the upper bound in Theorem 4.3?", "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": "", "extra_scores": {}}, {"review_id": "AiKZwRZ7De", "reviewer": "Reviewer_wDGv", "summary": "This paper investigates the generalization error of the tilted empirical risk (TER), a non-linear risk metric for supervised learning introduced by Li et al. (2020). The study focuses on the robustness regime under negative tilt, where TER is used to mitigate the impact of noisy outliers.\nThe paper provides uniform convergence and information-theoretic bounds on the tilted generalization error (the difference between population risk and tilted empirical risk) for unbounded loss functions with a finite 1+\\epsilon-th moment. The paper extends TER’s applicability by analyzing its robustness against noisy training outliers. Theoretical guarantees for TER are provided under distribution shift, showcasing its stability compared to traditional empirical risk minimization. The paper includes experimental evaluations that validate the theoretical bounds.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "We thank the reviewer for their comments and generally positive assessment of the paper. We will address their concerns as detailed below. \n\n> finite hypothesis class \n\n**R1:** We thank the reviewer for this valuable comment. Indeed, while Section 3.1 focuses on finite hypothesis class bounds, the approach can be naturally extended to continuous hypothesis classes using well-established techniques.\n\nFor example, one can construct an $\\\\epsilon$-net over the hypothesis space, thereby discretizing the space. In this construction, we select a finite subset $ H' \\\\subset \\\\mathbb{R}^m $ such that for every $ h \\\\in H $, there exists a $ h' \\\\in H' $ with $ \\\\|h \\- h'\\\\| \\\\leq r $. By applying our finite hypothesis result to this discretized set and controlling the approximation error through the Lipschitz property of the loss function, we effectively generalize our bounds to the continuous case. This method is exemplified in \\[2\\], which demonstrates that “for an uncountable hypothesis space, we can always convert it to a finite one by quantizing the output of the smallest set $ H' $ such that for all $ h \\\\in H $ there is a $ h' \\\\in H' $ with $ \\\\|h \\- h'\\\\| \\\\leq r $, where the Lipschitz maximal inequality (Lemma 5.7 in \\[3\\]) is derived using a similar quantization technique.\n\nAlternatively, one may also derive infinite hypothesis space results using VC-dimension arguments in binary classification:\n\nFirst, we observe that Lemma 2 in \\[1\\]—a symmetrization lemma—applies to functions of the form $f(Z)=\\\\exp(\\\\gamma \\\\ell(h,Z))\\\\in\\[0,1\\]$. Using this lemma, we replace the expected value $E\\[f(Z)\\]$ with its empirical average over an independent ghost sample. Next, we apply Bernstein's inequality to bound the deviation of the empirical average from the true expectation. In doing so, we substitute the variance term $Var(\\\\exp(\\\\gamma \\\\ell(h,Z)))$ by $|\\\\gamma|^{1+\\\\epsilon}E\\[|\\\\ell(h,Z)|^{1+\\\\epsilon}\\]$. The VC-dimension of the hypothesis class appears when we apply a union bound over a finite cover of the function class induced by the hypotheses using Sauer’s lemma to bound the growth function via the VC-dimension. Finally, as in the proofs of Propositions 3.3 and 3.4, we take the logarithm of both sides of the resulting inequality and rearrange the terms to derive the final generalization bound.\n\nFurthermore, we can also apply the similar approach to derive upper bounds based on covering numbers as introduced in \\[1\\].\n\nWe will clarify this discussion in the Appendix of the revised manuscript. \n\n> negative and positive tilt\n\nThe theoretical guarantees developed for negative tilt cannot be directly extended to the positive tilt scenario. For more details please check **R4** in response to **Reviewer 8SUL**. Addressing this limitation and exploring positive tilt in TERM is an avenue for future work, as mentioned in the Conclusion section. The primary application of tilted empirical risk for negative tilt is enhancing robustness to outliers. We have expressed the bounds in terms of $|\\gamma|$ to facilitate a more intuitive understanding of the results. We will add a remark on positive tilt theoretical challenges. \n\n>  Improvement of TER under distribution shift\n\nUnder an unbounded loss function assumption with a bounded $(1+\\\\epsilon)$-moment for $\\\\epsilon\\\\in(0,1\\]$, we can derive an upper bound on generalization error using the Tilted Empirical Risk (TER) with a negative tilt. Specifically, by leveraging the negative tilt parameter $\\\\gamma \\< 0$, we ensure the boundedness of $\\\\exp(\\\\gamma \\\\ell(h,Z))$, which allows us to establish an upper bound in terms of total variation distance. The total variation distance is bounded for all outlier distributions. However, the KL divergence can be unbounded. Therefore, the upper bound on TER is bounded for all outlier distributions. In contrast, for linear empirical risk, while can derive an expression for an upper bound in terms of the KL divergence, this expression can be unbounded for some outlier distributions, due to the unboundedness of the KL divergence.\n\n---\n\n**References:**\n\n[1]: ​​Bousquet, Olivier, Stéphane Boucheron, and Gábor Lugosi. \"Introduction to statistical learning theory.\"   \n[2]: A. Xu and M. Raginsky. Information-theoretic analysis of generalization capability of learning  \nalgorithms.  \n[3]: R. van Handel. Probability in high dimension.", "claims_and_evidence": "This paper is primarily theoretical, with detailed proofs provided to support the claims.", "methods_and_evaluation_criteria": "The evaluation in Section 5 appears solid. The achieved population risk using the data-driven approach for selecting gamma outperforms ERM in the presence of outlier noise.", "theoretical_claims": "I did not verify all the proofs of the theoretical results in detail, but I reviewed the main steps for Proposition 3.2, Lemma 3.7, and Proposition 3.9, and they appear reasonable to me.", "experimental_designs_or_analyses": "The experiments serve more as a sanity check and are limited to logistic regression and simple linear regression. This is OK, as the primary contribution of the paper is theoretical.", "relation_to_broader_scientific_literature": "The paper extends prior work on tilted empirical risk (Li et al., 2020) by establishing theoretical generalization bounds under negative tilt, connecting to broader studies on robust learning, generalization error analysis, and risk minimization in the presence of outliers and distribution shifts.", "essential_references_not_discussed": "Not I am aware of.", "other_strengths_and_weaknesses": "Strength: The results hold under more general conditions of bounded moments, rather than relying on the sub-Gaussian assumption or a bounded loss function.\n\nWeakness: In Section 3.1, only finite hypothesis class bounds are provided, with limited discussion on how to generalize to a continuous hypothesis class.", "other_comments_or_suggestions": "Strength: The results hold under more general conditions of bounded moments, rather than relying on the sub-Gaussian assumption or a bounded loss function.\n\nWeakness: In Section 3.1, only finite hypothesis class bounds are provided, with limited discussion on how to generalize to a continuous hypothesis class.", "questions_for_authors": "The authors keep emphasizing negative gamma, which I understand is due to the inequality direction, requiring negative gamma to provide a valid upper bound. However, since all the bounds depend on the absolute value of gamma, what is the practical benefit of using a negative gamma? Is there any intuitive theoretical explanation?\n\n\nFor the discussion after Theorem 4.3, does the improvement of TER under distribution shift stem from its performance bound depending on total variation rather than KL divergence? Could the authors elaborate further on why TER with negative tilting is essential for achieving this improvement?\n\n## update after rebuttal\nThanks for the rebuttal. I believe this is a solid paper, and I am maintaining my original score.", "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": "", "extra_scores": {}}, {"review_id": "YWeS0srrK8", "reviewer": "Reviewer_HKuD", "summary": "This paper gives a detailed and extensive study of the tilted empirical risk, focusing on particular on generalization bounds. Both uniform convergence bounds and algorithm-dependent information-theoretic bounds are provided, and robustness guarantees under distribution shifts are analyzed. On the basis of the theoretical results, a data-driven approach for determining the level of tilt is proposed and evaluated experimentally. Finally, inspired by the information-theoretic bounds, a KL-regularized version is studied and the optimal posterior is determined and analyzed.\n\n## update after rebuttal\n\nI thank the authors for their response. I retain my positive evaluation.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "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": "We thank the reviewer for their comments, and generally positive assessment of the paper. We will address their concerns as detailed below. \n\n> Also, the experiments on linear regression indicate a sizeable gap between the data-driven tilt parameter and the optimal one. Some further discussion of this, and the potential sources of looseness, could be useful. \n\n**R1:** In deriving $\\\\gamma\\_{data}$, we employ an asymptotic approach assuming $n \\\\to \\\\infty$ ( the sample size approaches infinity). Consequently, this introduces a theoretical gap between the data-driven and the optimal parameter selection. Nonetheless, the data-driven tuned tilt demonstrates superior performance compared to the Empirical Risk Minimization (ERM) approach. Therefore, TERM with data-driven tilt  can be helpful in practice. We will mention in the section on conclusion and limitations that a better and more realistic data-driven approach to selecting $\\\\gamma$ could be an area for future work.\n\n> What is the proper interpretation of the cases in Thm. 3.11 and the $\\\\zeta$ parameter?\n\n**R2:** Theorem 3.11 is derived by using the upper and lower bounds on the expected non-linear generalization error (Proposition 3.9 and 3.10). Note that, for the upper bound in Proposition 3.9, due to the sub-exponential assumption, we have two cases. Then, for small values of $\\\\kappa\\_t$ and assuming $\\\\frac{2I(H;S)}{|\\\\gamma|^{1+\\\\epsilon}\\\\kappa\\_t^{1+\\\\epsilon}}\\>n$, we can achieve the convergence rate of $O(1/n^{-\\\\epsilon/(1+\\\\epsilon)})$. However, for the lower bound, we introduced the $\\\\zeta$ parameter to handle the logarithm function as shown in the proof of Proposition 3.10. Similarly to the upper bound, for small values of $\\\\kappa\\_t$ and $\\\\zeta$, we can expect to achieve again the rate of $O(1/n^{-\\\\epsilon/(1+\\\\epsilon)})$.\n\n> Can you elaborate on when the proposed $\\\\gamma\\_{data}$ is expected to work well or not? Can the approach be altered for finite-data settings?\n\n**R3:** To address the finite-data setting, we need to focus on minimizing the bound presented in Theorem 4.3, which involves a complex interplay of exponential, polynomial, and inverse power terms of $\\\\gamma$. This complexity motivates our consideration of the asymptotic regime, which provides better theoretical insights into the parameter behavior. Empirically, our experiments validate this approach, showing that the data-driven tilt consistently outperforms the Empirical Risk Minimization (ERM) solution—which is desired.\n\nFinally, thanks for pointing out some typos in the draft. They are fixed now.", "claims_and_evidence": "Yes. The experimental results do not necessarily support making strong claims, but the paper does not overstate them either.", "methods_and_evaluation_criteria": "Overall, yes. It is not clear whether the results reported in Table 2 are particularly informative, though, as the risk is very low already for normal ERM. Some applications to real-world datasets could be interesting, but the current approach makes sense in order to illustrate the results. Also, the experiments on linear regression indicate a sizeable gap between the data-driven tilt parameter and the optimal one. Some further discussion of this, and the potential sources of looseness, could be useful. (Presumably related to $n\\rightarrow\\infty$ step).", "theoretical_claims": "I checked up to App. E in some detail and did not identify any issues.", "experimental_designs_or_analyses": "See above", "relation_to_broader_scientific_literature": "This paper is nicely positioned in the literature, and covers a lot of previously unaddressed questions in the use of tilted empirical risk minimization. The inclusion of practical guidelines for e.g. parameter selection strengthens this further.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "The theoretical and algorithmic contributions of this paper are strong. However, the presentation could be improved. The main body of the paper consists of dense mathematical statements with various conditions and parameters, and not much intuition or analysis is provided. For example, providing the reader with some interpretation of the various cases in Thm 3.11 and the effect on the bound could be beneficial—at present, several shorthand notations need to be unpacked and cases with nested conditions need to be interpreted without hints.", "other_comments_or_suggestions": "The content of the tables and figures is often small and somewhat blurry. The term “non-linear generalization error” is not particularly specific—using an alternative term could be good if possible.\n\n1. $I_1$, $I_3$, and $I_4$ are used but seemingly no $I_2$.\n2. In Thm. 4.5, “if (a) or (b) hold” before the equation is superfluous?\n3. $P^*_{H|S}$ doubly defined in Eqs. (23) and (24)\n4. Line 419 right column: “boudned”", "questions_for_authors": "1. What is the proper interpretation of the cases in Thm. 3.11 and the $\\zeta$ parameter?\n2. Can you elaborate on when the proposed $\\gamma_{\\text{data}}$ is expected to work well or not? Can the approach be altered for finite-data settings?", "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": "", "extra_scores": {}}, {"review_id": "tsvHfJVHqk", "reviewer": "Reviewer_Z1pS", "summary": "Building on the notion of tilted empirical risk, this paper develops upper bounds of generalization error for tilted empirical risk (defined as tilted empirical risk minus the regular population risk) under negative tilt and moment-bounded loss.  The first set of results (Theorems 3.5 and 3.11) are for the case where there is no distribution shift, where both uniform convergence bounds and information-theoretic bounds are derived. The second set of results (Theorems 4.3 and 4.5) extend the first set to the case with distribution shift. Under distribution shift, the TV distance between the training and testing distribution arises in the upper bound.  The paper then proceeds to discuss the optimized choice of the tilt value for a given pair of training and testing distributions and experimentally investigate the gain of TERM under optimal tilt with respect to ERM (from Appendix G, the optimal tilt seems to have been obtained via grid search). Finally, the paper studies TERM with KL regularization, deriving Gibbs posterior as the optimal solution (resembling its classical counterpart) and an information-theoretic generalization bound thereof. \nSimilar results for bounded losses are provided in Appendix H together with PAC-Bayes, Rademacher complexity and stability bounds.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "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": "We thank the reviewer for their comments, and generally positive assessment of the paper. We will address their concerns as detailed below. \n\n> Distribution shift and domain adaptation literature \n\n**R1:** Thank you for introducing the works on generalization bounds under distribution shift and domain adaptation.\n- Our focus in this work is on tilted empirical risk in supervised learning scenarios with clean or noisy training samples. In contrast, domain adaptation typically involves unlabeled samples, which differs from our setting. The type of distribution shift we consider primarily arises from noisy labels or outliers. Nevertheless, we will include the aforementioned references and others to expand the discussion on related work in this space and better contextualize our contributions.  \n- One of the key contributions of our work is the study of tilted empirical risk under unbounded loss functions, assuming only a bounded $(1+\\\\epsilon)$-th moment of the loss. In contrast, works such as [1], [2], and [3] assume bounded loss functions. We hope that our results can be combined with those in [1–3] to extend their applicability to heavy-tailed scenarios. We will include these references in our revision to better situate our work within the existing literature.\n\nFinally, thanks for mentioning [5]. We will include it  in the discussion of the related work.\n\n>What benefit can one exploit from this work? Is there any algorithmic improvement that can be derived or inspired from the theoretical results of this paper?\n\n**R2:** The main aim of this work is to provide a theoretical foundation for the tilted empirical risk which is introduced in [4]. Furthermore, our results help to **bridge a theoretical gap** by showing how tilting affects generalization bounds and excess risks, beyond intuition or heuristics. This can be particularly useful for practitioners designing robust models in supervised learning tasks, including classification, regression, and robustness-aware optimization. For instance, algorithms could:\n- Employ tilted empirical risk as an objective in training robust classifiers or regressors,  \n- Use our generalization guarantees to guide regularization schemes. In particular, a tilted Gibbs posterior as a learning algorithm is novel. We consider it as future work to study this algorithm in practice.  \n- Tuning $\\\\gamma$ is a main bottleneck for deploying the tilted loss framework (for example automatic tuning of tilt parameters). We can observe that in many cases  the data-driven $\\\\gamma$ performs better than the ERM solution in the distribution shift scenario for both Gaussian and Pareto outliers. The data-driven approach for selection of tilt under distribution shift scenario is not proposed in [4]. In the no-distribution shift scenario, we would like to emphasize that TERM with a small negative tilt value for the case of i.i.d. samples had not been explored in prior work including [4], and the usefulness of TERM in this scenario is actually uncovered by the theoretical developments.\n\n> TV distance and other divergences\n\n**R4:** Thanks for raising this point. For this purpose, we use Definition C.4 in [1]:\n$$d\\_{\\\\mathcal{H} \\\\Delta \\\\mathcal{H}}(\\\\mu;\\\\tilde\\\\mu)  := 2 \\\\sup\\_{\\\\mathcal{A}(h) \\\\in \\\\mathcal{A}\\_{\\\\mathcal{H} \\\\Delta\\\\mathcal{H}}} \\\\Big| Pr\\_{\\\\mu}(\\\\mathcal{A}(h)) \\- Pr\\_{\\\\tilde \\\\mu}(\\\\mathcal{A}(h)) \\\\Big|$$\n\nwhere $\\\\mathcal{H} \\\\Delta \\\\mathcal{H}$ is defined as $\\\\mathcal{H} \\\\Delta \\\\mathcal{H} := \\\\{ h(x) \\\\oplus h'(x) : h, h' \\\\in \\\\mathcal{H} \\\\}$, $\\\\mathcal{A}\\_{\\\\mathcal{H} \\\\Delta \\\\mathcal{H}}$ represents the  learning algorithm space under the hypothesis $\\\\mathcal{H} \\\\Delta \\\\mathcal{H}$ and $\\\\oplus$ is the XOR operator, e.g., $\\\\mathbb{I}(h'(x) \\\\ne h(x))$.\n\nThen, applying Corollary C.7 in [1] to proof of Proposition 4.2, we have,\n\n$$\\\\frac{1}{|\\\\gamma|}\\\\Big|\\\\log(E\\_{\\\\mu} \\\\exp(\\\\gamma\\\\ell(h,Z))) \\- \\\\log(E\\_{Z\\\\tilde \\\\mu}\\\\exp(\\\\gamma\\\\ell(h,Z))) \\\\Big|\\\\leq \\\\frac{d\\_{\\\\mathcal{H} \\\\Delta \\\\mathcal{H}}(\\\\mu; \\\\tilde \\\\mu)}{\\\\gamma^2} \\\\frac{\\\\exp(|\\\\gamma|\\\\kappa\\_u)-\\\\exp(|\\\\gamma|\\\\kappa\\_s)}{\\\\kappa\\_u-\\\\kappa\\_s}$$\n\nwhere $d\\_{\\\\mathcal{H} \\\\Delta \\\\mathcal{H}}(\\\\mu; \\\\tilde \\\\mu)$ can be estimated using training and test data samples.  Note that, for linear empirical risk, we cannot derive the result in terms of $d\\_{\\\\mathcal{H} \\\\Delta \\\\mathcal{H}}(\\\\mu; \\\\tilde \\\\mu)$ for unbounded loss functions.  We clarify this discussion in the revised manuscript. \n\n---\n**References:**\n- [1]: Zou, et al, Towards Robust Out-of-Distribution Generalization Bounds via Sharpness.\n- [2]: Wang and Mao, On f-Divergence Principled Domain Adaptation: An Improved Framework.\n- [3]: Ye et al, Towards a Theoretical Framework of Out-of-Distribution Generalization.\n- [4]: Tian Li, et al. On tilted losses in machine learning: Theory and applications. \n- [5]: Hellstrom, et al, Generalization Bounds: Perspectives from Information Theory and PAC-Bayes,", "claims_and_evidence": "I did not fully verify the proofs, but the proof techniques appear standard and the theoretical results look correct. The experimental results look convincing.", "methods_and_evaluation_criteria": "Methods and evaluation protocols and criteria look sound to this reviewer.", "theoretical_claims": "I went through all proofs but without tracing every step. The results make sense to me.", "experimental_designs_or_analyses": "The experimental designs and results are valid.", "relation_to_broader_scientific_literature": "The paper falls into the broad category of learning theory. It builds upon the work of Li et al, which introduces tilted empirical risk, and serves as its natural and necessary extensions.", "essential_references_not_discussed": "The coverage of existing generalization bounds on distribution shift and domain adaptation (BTW, when you want to measure distribution shift, in practice you pretty much deal with the scenario where you are given a labelled training set and an unlabelled testing set with shifted distribution, then you are entering the regime of unsupervised domain adaptation) is not adequate. In fact, there is a large volume of literature in this context, all missing from discussion. Below is a tiny sample and I encourage the authors to dig more.\n\n1. Zou, et al, Towards Robust Out-of-Distribution Generalization Bounds via Sharpness, ICLR2024.\n\n2. Wang and Mao, On f-Divergence Principled Domain Adaptation: An Improved Framework,  NeurIPS2024.\n\n3.  Ye et al, Towards a Theoretical Framework of Out-of-Distribution Generalization, NeurIPS2021\n\nRegarding (in-distribution) information-theoretic and PAC-Bayes generalization bounds,  the paper covers some early references, but more recent developments are largely left out. The authors may wish to consult a recent review article \n Hellstrom, et al, Generalization Bounds: Perspectives from Information Theory and PAC-Bayes, Foundations and Trends in Machine Learning, 2025.", "other_strengths_and_weaknesses": "The work is comprehensive in its theoretical development on generalization upper bounds related to tilted empirical risk, but somewhat weak in terms of the application and usefulness of their results. Specifically,\n\n1. What benefit can one exploit from this work? \n\n2. Is there any algorithmic improvement that can be derived or inspired from the theoretical results of this paper? \n\nThe paper will be greatly improved if results along this line are adequately developed, and I am open to increase my score if these questions are appropriately addressed.", "other_comments_or_suggestions": "The bounds on distribution shift all involve the TV distance of the training and testing distributions.  Without knowing these distributions, the bounds cannot be computed or estimated. It would be much more useful if the authors could derive such bounds where the distribution shift is measured by the training and testing samples (rather than by their distributions), much like those developed in domain adaptation literature, e.g. in the flavor of Theorem 3 in Ben-David and Blitzer ''A theory of learning from different domains'', 2009. If this can be done, one can exploit the optimal choice of the tilt value for the given training and testing samples (rather than for the two distributions, to which we do not have access in practice).", "questions_for_authors": "See Other Strengths And Weaknesses and Other Comments Or Suggestions.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper contributes to the analysis of generalization error of tilted empirical risk (TERM). In particular, the paper presents new results with applications to robust learning and learning under distribution shift. 

All the reviewers agree of the general merits of the paper and the solid theoretical results presented. I suggest the authors to update the manuscript based on the reviewers' comments. For instance, it would be useful for the readers if the authors discuss cases with infinite hypothesis classes. It would be also good if the authors improve the paper's presentation including interpretations of the main messages offered by the theoretical results.
Decision: Accept (poster)