Generalization Analysis of Machine Learning Algorithms via the Worst-Case Data-Generating Probability Measure

Aug 4, 2026

Upload by Ivy

Worst-case probability measure over the data is introduced as a tool to characterize how machine learning algorithms generalize beyond training. The measure is defined as a Gibbs distribution obtained as the unique maximizer of expected loss under a relative-entropy constraint to a reference probability measure. Closed-form expressions are derived for key metrics including sensitivity of expected loss, sensitivity of empirical risk, and the generalization gap. Results for the Gibbs algorithm are recovered, including a link to mutual information and lautum information, and a parallel between the worst-case measure and the Gibbs algorithm is established.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages9

Reading Time23 min

AccessFree to download

Abstract

Introduction

Related Works

arXiv :2312 . 12236v1 [ cs .LG] 19 Dec 2023 Generalization Analysis of Machine Learning Algorithms via the Worst-Case Data-Generating Probability Measure Xinying Zou 1 , Samir M. Perlaza 1, 2, 3 , I˜naki Esnaola2, 4 , and Eitan Altman 1, 5 1 INRIA, Centre Inria d’Universit´e Cˆote d’Azur, Sophia Antipolis 06902, France 2Department of Electrical and Computer Engineering, Princeton University, Princeton NJ 08544, USA 3 GAATI Laboratory, Universit´e de la Polyn´esie Franc¸aise, Faaa 98702, French Polynesia 4Department of Automatic Control and Systems Engineering, University of Shef􀀂eld, Shef􀀂eld S1 3JD, UK 5Laboratoire d’Informatique d’Avignon, Universit´e d’Avignon, France xinying.zou@inria.fr, samir.perlaza@inria.fr, esnaola@shef􀀂eld.ac.uk, eitan.altman@inria.fr 1 Abstract In this paper, the worst-case probability measure over the data is introduced as a tool for characterizing the generalization capabilities of machine learning algorithms. More speci􀀂cally, the worst-case probability measure is a Gibbs probability measure and the unique solution to the maximization of the expected loss under a relative entropy constraint with respect to a reference probability measure. Fundamental generalization metrics, such as the sensitivity of the expected loss, the sensitivity of the empirical risk, and the generalization gap are shown to have closed-form expressions involving the worst-case data-generating probability measure. Existing results for the Gibbs algorithm, such as characterizing the generalization gap as a sum of mutual information and lautum information, up to a constant factor, are recovered. A novel parallel is established between the worst-case data-generating probability measure and the Gibbs algorithm. Speci􀀂cally, the Gibbs probability measure is identi􀀂ed as a fundamental commonality of the model space and the data space for machine learning algorithms. 2 Introduction The expected generalization error (GE) is a central workhorse for the analysis of generalization capabilities of machine learning algorithms, see for instance (Aminian et al. 2021, 2022; Chu and Raginsky 2023; Xu and Raginsky 2017) and (Perlaza et al. 2023) . In a nutshell, the GE characterizes the ability of the learning algorithm to correctly 􀀂nd patterns in datasets that are not available during the training stage. Speci􀀂cally, it is de􀀂ned for a 􀀂xed training dataset and a speci􀀂c model instance, as the difference between the population risk induced by the model and the empirical risk with respect to the training dataset. When the choice of models is governed by a stochastic kernel, the expected GE (EGE) is the expectation of the GE with respect to the joint-measure of the models and the datasets. Closed-form expressions for the EGE are only known for the Gibbs algorithm in the case in which the reference measure is a probability measure (Aminian et al. 2021); and for the case in which the reference measure is a σ-􀀂nite measure (Perlaza et al. 2022a) . Copyright © 2024, Association for the Advancement of Arti􀀂cial Intelligence ([www.aaai.org](www.aaai.org)). All rights reserved. 2.1 Related Works In general, the EGE of machine learning algorithms is characterized by various upper-bounds leveraging different techniques. The metric of mutual information was 􀀂rst proposed in (Russo and Zou 2016), further developed in (Xu and Raginsky 2017) and combined with chaining methods in (Asadi, Abbe, and Verd´u 2018; Asadi and Abbe 2020) for deriving upper bounds on the EGE. Similar bounds on the EGE were obtained in (Bu, Zou, and Veeravalli 2020; Chu and Raginsky 2023; Hafez-Kolahi et al. 2020; Hellstr¨om and Durisi 2020) and references therein. Other information measures such as the Wasserstein distance (Aminian et al. 2022; Lopez and Jog 2018; Wang et al. 2019), maximal leakage (Esposito, Gastpar, and Issa 2020; Issa, Esposito, and Gastpar 2019), mutual f-information (Masiha, Gohari, and Yassaee 2023), and Jensen-Shannon diver

FAQs

What is the worst-case probability measure used for in this work?

It is introduced to characterize the generalization capabilities of machine learning algorithms by analyzing how performance changes from training to unseen data.

How is the worst-case probability measure defined?

It is defined as a Gibbs probability measure, uniquely obtained by maximizing the expected loss under a relative-entropy constraint relative to a reference probability measure.

Which generalization metrics are shown to admit closed-form expressions?

The paper derives closed-form expressions for metrics such as the sensitivity of the expected loss, the sensitivity of the empirical risk, and the generalization gap.

Aug 4, 2026

Upload by Ivy