Generalization Analysis of Machine Learning Algorithms via the Worst-Case Data-Generating Probability Measure
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 specifically, 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. Specifically, the Gibbs probability measure is identified as a fundamental commonality of the model space and the data space for machine learning algorithms.
Code (0)
등록된 구현이 없습니다.
Tasks
SensitivitySimilar Papers 제목 키워드 기반
Beyond the Worst-Case Analysis of Algorithms (Introduction)
One of the primary goals of the mathematical analysis of algorithms is to provide guidance about which algorithm is the "best" for solving a given computational problem. Worst-case analysis summarizes the performance pro…
The Two Dimensions of Worst-case Training and the Integrated Effect for Out-of-domain Generalization
Training with an emphasis on "hard-to-learn" components of the data has been proven as an effective method to improve the generalization of machine learning models, especially in the settings where robustness (e.g., gene…
BIG-bench Machine LearningDomain GeneralizationThe Two Dimensions of Worst-Case Training and Their Integrated Effect for Out-of-Domain Generalization
Training with an emphasis on "hard-to-learn" components of the data has been proven as an effective method to improve the generalization of machine learning models, especially in the settings where robustness (e.g., …
BIG-bench Machine LearningDomain GeneralizationStability, Complexity and Data-Dependent Worst-Case Generalization Bounds
Providing generalization guarantees for stochastic optimization algorithms remains a key challenge in learning theory. Recently, numerous works demonstrated the impact of the geometric properties of optimization trajecto…
Stochastic OptimizationLearning-to-Optimize with PAC-Bayesian Guarantees: Theoretical Considerations and Practical Implementation
We use the PAC-Bayesian theory for the setting of learning-to-optimize. To the best of our knowledge, we present the first framework to learn optimization algorithms with provable generalization guarantees (PAC-Bayesian …