Research map / Learning theory and algorithms / Prediction and decision losses

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

AAAI 2024 · Learning theory and algorithms › Prediction and decision losses · approach: Distributionally robust optimization · 10 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Introduces the worst-case data-generating probability measure, a Gibbs measure maximizing expected loss under a relative-entropy constraint around a reference measure, and uses it to derive closed-form sensitivity, empirical-risk, and generalization-gap expressions, recovering known Gibbs-algorithm results.

Problem

Characterizing the expected generalization error of machine learning algorithms in a way that makes its dependence on the training dataset and chosen model explicit, rather than relying on worst-case dataset bounds.

Approach

Define the worst-case data-generating measure as the maximizer of expected loss subject to a KL-divergence ball around a reference measure; it is a Gibbs measure, so sensitivities and generalization gaps admit closed forms in terms of KL divergences to it and to the reference, with Gibbs-algorithm mutual/lautum information results recovered as a special case.

Key results

• The sensitivity of the expected loss from the worst-case measure to any alternative P equals beta(KL(P||P_S) - KL(P||Q*) - KL(Q*||P_S)), giving closed forms for generalization metrics.
• The doubly-expected generalization gap of the Gibbs algorithm is shown to equal lambda times the sum of mutual information and lautum information, recovering a known result under the i.i.d. assumption.
• The worst-case measure is shown to be mutually absolutely continuous with the reference measure P_S, and the expected loss under it is at least that under P_S.

Limitations

• Alternative proof of the Gibbs-algorithm result relies on i.i.d. data assumption, since the method of types fails to capture correlations between datapoints.
• Existence of the worst-case measure solution is assumed rather than guaranteed in general.
• No empirical experiments are reported to validate the theoretical expressions.

Experimental setup

Builds on: Gibbs algorithm method of types

Closest papers by meaning

• A Survey of Learning Criteria Going beyond the Usual Risk (Abstract Reprint) (AAAI 2024 · similarity 0.85)
• Exactly Tight Information-theoretic Generalization Bounds via Binary Jensen-Shannon Divergence (ICML 2025 · similarity 0.85)
• Generalization of Hamiltonian algorithms (NeurIPS 2024 · similarity 0.85)
• Sequential Probability Assignment with Contexts: Minimax Regret, Contextual Shtarkov Sums, and Contextual Normalized Maximum Likelihood (NeurIPS 2024 · similarity 0.84)
• Towards Generalization beyond Pointwise Learning: A Unified Information-theoretic Perspective (ICML 2024 · similarity 0.84)
• Understanding Domain Generalization: A Noise Robustness Perspective (ICLR 2024 · similarity 0.84)