Generalization and Robustness of the Tilted Empirical Risk

We thank the reviewer for their comments, and generally positive assessment of the paper. We will address their concerns as detailed below.

Distribution shift and domain adaptation literature

R1: Thank you for introducing the works on generalization bounds under distribution shift and domain adaptation.

• 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.
• 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.

Finally, thanks for mentioning [5]. We will include it in the discussion of the related work.

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?

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:

• Employ tilted empirical risk as an objective in training robust classifiers or regressors,
• 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.
• 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.

TV distance and other divergences

R4: Thanks for raising this point. For this purpose, we use Definition C.4 in [1]: $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|$

where $\\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))$.

Then, applying Corollary C.7 in [1] to proof of Proposition 4.2, we have,

$\\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}$

where $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.

References:

• [1]: Zou, et al, Towards Robust Out-of-Distribution Generalization Bounds via Sharpness.
• [2]: Wang and Mao, On f-Divergence Principled Domain Adaptation: An Improved Framework.
• [3]: Ye et al, Towards a Theoretical Framework of Out-of-Distribution Generalization.
• [4]: Tian Li, et al. On tilted losses in machine learning: Theory and applications.
• [5]: Hellstrom, et al, Generalization Bounds: Perspectives from Information Theory and PAC-Bayes,

We thank the reviewer for their comments, and generally positive assessment of the paper. We will address their concerns as detailed below.

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.

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.

What is the proper interpretation of the cases in Thm. 3.11 and the $\\zeta$ parameter?

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)})$.

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?

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.

Finally, thanks for pointing out some typos in the draft. They are fixed now.

We thank the reviewer for their comments and generally positive assessment of the paper. We will address their concerns as detailed below.

finite hypothesis class

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.

For 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.

Alternatively, one may also derive infinite hypothesis space results using VC-dimension arguments in binary classification:

First, 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.

Furthermore, we can also apply the similar approach to derive upper bounds based on covering numbers as introduced in $1$ .

We will clarify this discussion in the Appendix of the revised manuscript.

negative and positive tilt

The 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.

Improvement of TER under distribution shift

Under 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.

References:

[1]: ​​Bousquet, Olivier, Stéphane Boucheron, and Gábor Lugosi. "Introduction to statistical learning theory."
[2]: A. Xu and M. Raginsky. Information-theoretic analysis of generalization capability of learning
algorithms.
[3]: R. van Handel. Probability in high dimension.

We thank the reviewer for their comments, and generally positive assessment of the paper. We will address their concerns as detailed below.

Comparison between TERM and ERM

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

\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)}, \end{aligned}