A Theory of Universal Agnostic Learning

• URL: http://arxiv.org/abs/2601.20961v1
• Date: Wed, 28 Jan 2026 19:03:26 GMT
• Title: A Theory of Universal Agnostic Learning
• Authors: Steve Hanneke, Shay Moran,
• Abstract summary: We provide a complete theory of optimal universal rates for binary classification in the setting.<n>For every concept class, the optimal universal rate of convergence of the excess error rate is one of $e-n$, $e-o(n)$, $o(n-1/2$)$, or arbitrarily slow.
• Score: 52.1555858290493
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We provide a complete theory of optimal universal rates for binary classification in the agnostic setting. This extends the realizable-case theory of Bousquet, Hanneke, Moran, van Handel, and Yehudayoff (2021) by removing the realizability assumption on the distribution. We identify a fundamental tetrachotomy of optimal rates: for every concept class, the optimal universal rate of convergence of the excess error rate is one of $e^{-n}$, $e^{-o(n)}$, $o(n^{-1/2})$, or arbitrarily slow. We further identify simple combinatorial structures which determine which of these categories any given concept class falls into.

Related papers

• Almost Asymptotically Optimal Active Clustering Through Pairwise Observations [59.20614082241528]
  We propose a new analysis framework for clustering $M$ items into an unknown number of $K$ distinct groups using noisy and actively collected responses.<n>We establish a fundamental lower bound on the expected number of queries needed to achieve a desired confidence in the accuracy of the clustering.<n>We develop a computationally feasible variant of the Generalized Likelihood Ratio statistic and show that its performance gap to the lower bound can be accurately empirically estimated.
  arXiv  Detail & Related papers  (2026-02-05T14:16:47Z)
• Universal rates of ERM for agnostic learning [15.001378595582269]
  Empirical Risk Minimization principle being fundamental in the PAC theory and ubiquitous in practical machine learning.<n>We explore the possibilities of agnostic universal rates, being either $e-n$, $o(n-1/2)$, or arbitrarily slow.
  arXiv  Detail & Related papers  (2025-06-17T02:02:11Z)
• Generalization Performance of Ensemble Clustering: From Theory to Algorithm [57.176040163699554]
  This paper focuses on generalization error, excess risk and consistency in ensemble clustering.<n>By assigning varying weights to finite clusterings, we minimize the error between the empirical average clusterings and their expectation.<n>We instantiate our theory to develop a new ensemble clustering algorithm.
  arXiv  Detail & Related papers  (2025-06-01T09:34:52Z)
• Universal Rates of Empirical Risk Minimization [15.001378595582269]
  We study the problem of universal learning by empirical risk (ERM) in the realizable case.<n>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.
  arXiv  Detail & Related papers  (2024-12-03T20:20:39Z)
• Optimal Multi-Distribution Learning [88.3008613028333]
  Multi-distribution learning seeks to learn a shared model that minimizes the worst-case risk across $k$ distinct data distributions.<n>We propose a novel algorithm that yields an varepsilon-optimal randomized hypothesis with a sample complexity on the order of (d+k)/varepsilon2.
  arXiv  Detail & Related papers  (2023-12-08T16:06:29Z)
• Federated Learning as Variational Inference: A Scalable Expectation Propagation Approach [66.9033666087719]
  This paper extends the inference view and describes a variational inference formulation of federated learning. We apply FedEP on standard federated learning benchmarks and find that it outperforms strong baselines in terms of both convergence speed and accuracy.
  arXiv  Detail & Related papers  (2023-02-08T17:58:11Z)
• Multiclass Learnability Beyond the PAC Framework: Universal Rates and Partial Concept Classes [31.2676304636432]
  We study the problem of multiclass classification with a bounded number of different labels $k$, in the realizable setting. We extend the traditional PAC model to a) distribution-dependent learning rates, and b) learning rates under data-dependent assumptions.
  arXiv  Detail & Related papers  (2022-10-05T14:36:27Z)
• Robust Linear Predictions: Analyses of Uniform Concentration, Fast Rates and Model Misspecification [16.0817847880416]
  We offer a unified framework that includes a broad variety of linear prediction problems on a Hilbert space. We show that for misspecification level $epsilon$, these estimators achieve an error rate of $O(maxleft|mathcalO|1/2n-1/2, |mathcalI|1/2n-1 right+epsilon)$, matching the best-known rates in literature.
  arXiv  Detail & Related papers  (2022-01-06T08:51:08Z)
• Linear Speedup in Personalized Collaborative Learning [69.45124829480106]
  Personalization in federated learning can improve the accuracy of a model for a user by trading off the model's bias. We formalize the personalized collaborative learning problem as optimization of a user's objective. We explore conditions under which we can optimally trade-off their bias for a reduction in variance.
  arXiv  Detail & Related papers  (2021-11-10T22:12:52Z)
• Permutation Compressors for Provably Faster Distributed Nonconvex Optimization [68.8204255655161]
  We show that the MARINA method of Gorbunov et al (2021) can be considered as a state-of-the-art method in terms of theoretical communication complexity. Theory of MARINA to support the theory of potentially em correlated compressors, extends to the method beyond the classical independent compressors setting.
  arXiv  Detail & Related papers  (2021-10-07T09:38:15Z)
• Beyond $\mathcal{H}$-Divergence: Domain Adaptation Theory With Jensen-Shannon Divergence [21.295136514836788]
  We reveal the incoherence between the widely-adopted empirical domain adversarial training and its generally-assumed theoretical counterpart based on $mathcalH$-divergence. We establish a new theoretical framework by directly proving the upper and lower target risk bounds based on joint distributional Jensen-Shannon divergence.
  arXiv  Detail & Related papers  (2020-07-30T16:19:59Z)

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.