Universal Rates of Empirical Risk Minimization

• URL: http://arxiv.org/abs/2412.02810v2
• Date: Thu, 30 Jan 2025 15:36:39 GMT
• Title: Universal Rates of Empirical Risk Minimization
• Authors: Steve Hanneke, Mingyue Xu,
• Abstract summary: We study the problem of universal learning by empirical risk (ERM) in the realizable case. There are only four possible universal learning rates by ERM, namely, the learning curves of any concept class learnable by ERM decay either at $e-n$, $1/n$, $log(n)/n$, or arbitrarily slow rates.
• Score: 15.001378595582269
• License:
• Abstract: The well-known empirical risk minimization (ERM) principle is the basis of many widely used machine learning algorithms, and plays an essential role in the classical PAC theory. A common description of a learning algorithm's performance is its so-called "learning curve", that is, the decay of the expected error as a function of the input sample size. As the PAC model fails to explain the behavior of learning curves, recent research has explored an alternative universal learning model and has ultimately revealed a distinction between optimal universal and uniform learning rates (Bousquet et al., 2021). However, a basic understanding of such differences with a particular focus on the ERM principle has yet to be developed. In this paper, we consider the problem of universal learning by ERM in the realizable case and study the possible universal rates. Our main result is a fundamental tetrachotomy: there are only four possible universal learning rates by ERM, namely, the learning curves of any concept class learnable by ERM decay either at $e^{-n}$, $1/n$, $\log(n)/n$, or arbitrarily slow rates. Moreover, we provide a complete characterization of which concept classes fall into each of these categories, via new complexity structures. We also develop new combinatorial dimensions which supply sharp asymptotically-valid constant factors for these rates, whenever possible.

Related papers

• Balancing the Scales: A Theoretical and Algorithmic Framework for Learning from Imbalanced Data [35.03888101803088]
  This paper introduces a novel theoretical framework for analyzing generalization in imbalanced classification. We propose a new class-imbalanced margin loss function for both binary and multi-class settings, prove its strong $H$-consistency, and derive corresponding learning guarantees. We devise novel and general learning algorithms, IMMAX, which incorporate confidence margins and are applicable to various hypothesis sets.
  arXiv  Detail & Related papers  (2025-02-14T18:57:16Z)
• Proper Learnability and the Role of Unlabeled Data [10.168670899305232]
  We show that there are problems whose proper learnability is logically undecidable, i.e., independent of the ZFC axioms. We then show all impossibility results which obstruct any characterization of proper learnability in the realizable PAC model.
  arXiv  Detail & Related papers  (2025-02-14T18:41:53Z)
• Collaborative Learning with Different Labeling Functions [7.228285747845779]
  We study a variant of Collaborative PAC Learning, in which we aim to learn an accurate classifier for each of the $n$ data distributions. We show that, when the data distributions satisfy a weaker realizability assumption, sample-efficient learning is still feasible.
  arXiv  Detail & Related papers  (2024-02-16T04:32:22Z)
• A Unified Generalization Analysis of Re-Weighting and Logit-Adjustment for Imbalanced Learning [129.63326990812234]
  We propose a technique named data-dependent contraction to capture how modified losses handle different classes. On top of this technique, a fine-grained generalization bound is established for imbalanced learning, which helps reveal the mystery of re-weighting and logit-adjustment.
  arXiv  Detail & Related papers  (2023-10-07T09:15:08Z)
• Regularization and Optimal Multiclass Learning [10.168670899305232]
  This work is to characterize the role of regularization in perhaps the simplest setting for which empirical risk minimization fails: multiclass learning with arbitrary label sets. Using one-inclusion graphs (OIGs), we exhibit optimal learning algorithms that dovetail with tried-and-true algorithmic principles.
  arXiv  Detail & Related papers  (2023-09-24T16:49:55Z)
• On the Stability and Generalization of Triplet Learning [55.75784102837832]
  Triplet learning, i.e. learning from triplet data, has attracted much attention in computer vision tasks. This paper investigates the generalization guarantees of triplet learning by leveraging the stability analysis.
  arXiv  Detail & Related papers  (2023-02-20T07:32:50Z)
• GEC: A Unified Framework for Interactive Decision Making in MDP, POMDP, and Beyond [101.5329678997916]
  We study sample efficient reinforcement learning (RL) under the general framework of interactive decision making. We propose a novel complexity measure, generalized eluder coefficient (GEC), which characterizes the fundamental tradeoff between exploration and exploitation. We show that RL problems with low GEC form a remarkably rich class, which subsumes low Bellman eluder dimension problems, bilinear class, low witness rank problems, PO-bilinear class, and generalized regular PSR.
  arXiv  Detail & Related papers  (2022-11-03T16:42:40Z)
• Constrained Learning with Non-Convex Losses [119.8736858597118]
  Though learning has become a core technology of modern information processing, there is now ample evidence that it can lead to biased, unsafe, and prejudiced solutions.
  arXiv  Detail & Related papers  (2021-03-08T23:10:33Z)
• Nonparametric Estimation of Heterogeneous Treatment Effects: From Theory to Learning Algorithms [91.3755431537592]
  We analyze four broad meta-learning strategies which rely on plug-in estimation and pseudo-outcome regression. We highlight how this theoretical reasoning can be used to guide principled algorithm design and translate our analyses into practice.
  arXiv  Detail & Related papers  (2021-01-26T17:11:40Z)
• A Theory of Universal Learning [26.51949485387526]
  We show that there are only three possible rates of universal learning. We show that the learning curves of any given concept class decay either at an exponential, or arbitrarily slow rates.
  arXiv  Detail & Related papers  (2020-11-09T15:10:32Z)
• Probably Approximately Correct Constrained Learning [135.48447120228658]
  We develop a generalization theory based on the probably approximately correct (PAC) learning framework. We show that imposing a learner does not make a learning problem harder in the sense that any PAC learnable class is also a constrained learner. We analyze the properties of this solution and use it to illustrate how constrained learning can address problems in fair and robust classification.
  arXiv  Detail & Related papers  (2020-06-09T19:59:29Z)

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.