The Generalization Error of Machine Learning Algorithms

• URL: http://arxiv.org/abs/2411.12030v1
• Date: Mon, 18 Nov 2024 20:05:51 GMT
• Title: The Generalization Error of Machine Learning Algorithms
• Authors: Samir M. Perlaza, Xinying Zou,
• Abstract summary: Method of gaps is a technique for deriving closed-form expressions in terms of information measures for the generalization error of machine learning algorithms. All existing exact expressions for the generalization error of machine learning algorithms can be obtained with the proposed method.
• Score: 0.0
• License:
• Abstract: In this paper, the method of gaps, a technique for deriving closed-form expressions in terms of information measures for the generalization error of machine learning algorithms is introduced. The method relies on two central observations: $(a)$~The generalization error is an average of the variation of the expected empirical risk with respect to changes on the probability measure (used for expectation); and~$(b)$~these variations, also referred to as gaps, exhibit closed-form expressions in terms of information measures. The expectation of the empirical risk can be either with respect to a measure on the models (with a fixed dataset) or with respect to a measure on the datasets (with a fixed model), which results in two variants of the method of gaps. The first variant, which focuses on the gaps of the expected empirical risk with respect to a measure on the models, appears to be the most general, as no assumptions are made on the distribution of the datasets. The second variant develops under the assumption that datasets are made of independent and identically distributed data points. All existing exact expressions for the generalization error of machine learning algorithms can be obtained with the proposed method. Also, this method allows obtaining numerous new exact expressions, which improves the understanding of the generalization error; establish connections with other areas in statistics, e.g., hypothesis testing; and potentially, might guide algorithm designs.

Related papers

• Collaborative Heterogeneous Causal Inference Beyond Meta-analysis [68.4474531911361]
  We propose a collaborative inverse propensity score estimator for causal inference with heterogeneous data. Our method shows significant improvements over the methods based on meta-analysis when heterogeneity increases.
  arXiv  Detail & Related papers  (2024-04-24T09:04:36Z)
• Generalization Analysis of Machine Learning Algorithms via the Worst-Case Data-Generating Probability Measure [1.773764539873123]
  Worst-case probability measure over the data is introduced as a tool for characterizing the generalization capabilities of machine learning algorithms. Fundamental generalization metrics, such as the sensitivity of the expected loss, the sensitivity of empirical risk, and the generalization gap are shown to have closed-form expressions. A novel parallel is established between the worst-case data-generating probability measure and the Gibbs algorithm.
  arXiv  Detail & Related papers  (2023-12-19T15:20:27Z)
• Anomaly Detection Under Uncertainty Using Distributionally Robust Optimization Approach [0.9217021281095907]
  Anomaly detection is defined as the problem of finding data points that do not follow the patterns of the majority. The one-class Support Vector Machines (SVM) method aims to find a decision boundary to distinguish between normal data points and anomalies. A distributionally robust chance-constrained model is proposed in which the probability of misclassification is low.
  arXiv  Detail & Related papers  (2023-12-03T06:13:22Z)
• Learning to Bound Counterfactual Inference in Structural Causal Models from Observational and Randomised Data [64.96984404868411]
  We derive a likelihood characterisation for the overall data that leads us to extend a previous EM-based algorithm. The new algorithm learns to approximate the (unidentifiability) region of model parameters from such mixed data sources. It delivers interval approximations to counterfactual results, which collapse to points in the identifiable case.
  arXiv  Detail & Related papers  (2022-12-06T12:42:11Z)
• Posterior and Computational Uncertainty in Gaussian Processes [52.26904059556759]
  Gaussian processes scale prohibitively with the size of the dataset. Many approximation methods have been developed, which inevitably introduce approximation error. This additional source of uncertainty, due to limited computation, is entirely ignored when using the approximate posterior. We develop a new class of methods that provides consistent estimation of the combined uncertainty arising from both the finite number of data observed and the finite amount of computation expended.
  arXiv  Detail & Related papers  (2022-05-30T22:16:25Z)
• Equivariance Discovery by Learned Parameter-Sharing [153.41877129746223]
  We study how to discover interpretable equivariances from data. Specifically, we formulate this discovery process as an optimization problem over a model's parameter-sharing schemes. Also, we theoretically analyze the method for Gaussian data and provide a bound on the mean squared gap between the studied discovery scheme and the oracle scheme.
  arXiv  Detail & Related papers  (2022-04-07T17:59:19Z)
• Domain Conditional Predictors for Domain Adaptation [3.951376400628575]
  We consider a conditional modeling approach in which predictions, in addition to being dependent on the input data, use information relative to the underlying data-generating distribution. We argue that such an approach is more generally applicable than current domain adaptation methods.
  arXiv  Detail & Related papers  (2021-06-25T22:15:54Z)
• Parsimonious Feature Extraction Methods: Extending Robust Probabilistic Projections with Generalized Skew-t [0.8336315962271392]
  We propose a novel generalisation to the Student-t Probabilistic Principal Component methodology. The new framework provides a more flexible approach to modelling groups of marginal tail dependence in the observation data. The applicability of the new framework is illustrated on a data set that consists of crypto currencies with the highest market capitalisation.
  arXiv  Detail & Related papers  (2020-09-24T05:53:41Z)
• Accounting for Unobserved Confounding in Domain Generalization [107.0464488046289]
  This paper investigates the problem of learning robust, generalizable prediction models from a combination of datasets. Part of the challenge of learning robust models lies in the influence of unobserved confounders. We demonstrate the empirical performance of our approach on healthcare data from different modalities.
  arXiv  Detail & Related papers  (2020-07-21T08:18:06Z)
• Good Classifiers are Abundant in the Interpolating Regime [64.72044662855612]
  We develop a methodology to compute precisely the full distribution of test errors among interpolating classifiers. We find that test errors tend to concentrate around a small typical value $varepsilon*$, which deviates substantially from the test error of worst-case interpolating model. Our results show that the usual style of analysis in statistical learning theory may not be fine-grained enough to capture the good generalization performance observed in practice.
  arXiv  Detail & Related papers  (2020-06-22T21:12:31Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.