Stability and List-Replicability for Agnostic Learners

• URL: http://arxiv.org/abs/2501.05333v2
• Date: Fri, 21 Mar 2025 20:27:28 GMT
• Title: Stability and List-Replicability for Agnostic Learners
• Abstract summary: We prove that classes with infinite Littlestone dimension are not stably PAC learnable, even if we allow the stability parameter to depend on the excess error.<n>We also prove that only finite hypothesis classes are globally stable learnable, even if we restrict the agnostic setting to distributions with small population loss.
• Score: 2.061173670995696
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Two seminal papers--Alon, Livni, Malliaris, Moran (STOC 2019) and Bun, Livni, and Moran (FOCS 2020)--established the equivalence between online learnability and globally stable PAC learnability in binary classification. However, Chase, Chornomaz, Moran, and Yehudayoff (STOC 2024) recently showed that this equivalence does not hold in the agnostic setting. Specifically, they proved that in the agnostic setting, only finite hypothesis classes are globally stable learnable. Therefore, agnostic global stability is too restrictive to capture interesting hypothesis classes. To address this limitation, Chase et al. introduced two relaxations of agnostic global stability. In this paper, we characterize the classes that are learnable under their proposed relaxed conditions, resolving the two open problems raised in their work. First, we prove that in the setting where the stability parameter can depend on the excess error (the gap between the learner's error and the best achievable error by the hypothesis class), agnostic stability is fully characterized by the Littlestone dimension. Consequently, as in the realizable case, this form of learnability is equivalent to online learnability. As part of the proof of this theorem, we strengthen the celebrated result of Bun et al. by showing that classes with infinite Littlestone dimension are not stably PAC learnable, even if we allow the stability parameter to depend on the excess error. For the second relaxation proposed by Chase et al., we prove that only finite hypothesis classes are globally stable learnable, even if we restrict the agnostic setting to distributions with small population loss.

Related papers

• Null Measurability at the Symmetrization Interface in VC Learning [0.15229257192293197]
  Recent revisiting of measurability in the fundamental theorem of statistical learning imposes Borel measurability of ghost-gap suprema.<n>We show that, at the one-sided ghost-gap interface actually used by the standard symmetrization proof, this requirement is stronger than necessary.<n>Results weaken the measurability hypothesis needed by the symmetrization route from finite VC to PAC learnability.
  arXiv  Detail & Related papers  (2026-04-27T22:10:34Z)
• The Attribution Impossibility: No Feature Ranking Is Faithful, Stable, and Complete Under Collinearity [0.0]
  No feature ranking can be simultaneously faithful, stable, and complete when features are collinear.<n>We prove this impossibility, quantify it for four model classes, resolve it via ensemble averaging (DASH), and machine-verify it with 305 Lean 4 theorems.<n>The design space theorem, diagnostics, and impossibility are mechanically verified in Lean 4 (305 theorems from 16 axioms, 0 sorry) -- to our knowledge, the first formally verified impossibility in explainable AI.
  arXiv  Detail & Related papers  (2026-04-08T10:11:45Z)
• Characterizing Online and Private Learnability under Distributional Constraints via Generalized Smoothness [63.833913892018536]
  We study sequential decision making under distributional adversaries that can adaptively choose data-generating distributions from a fixed family $U$.<n>We provide a near complete characterization of families $U$ that admit learnability in terms of a notion known as generalized smoothness.<n>We show that the generalized smoothness also characterizes private learnability under distributional constraints.
  arXiv  Detail & Related papers  (2026-02-24T06:15:59Z)
• Robust Online Learning [0.0]
  We study the problem of learning robust classifiers where the classifier will receive a perturbed input.<n>We consider both the realizable and learnability of hypothesis classes.<n>We show it controls the mistake bounds in the realizable setting and the regret bounds in the agnostic setting.
  arXiv  Detail & Related papers  (2026-02-06T15:30:52Z)
• Partial Feedback Online Learning [88.27143767009376]
  We study a new learning protocol, termed partial-feedback online learning.<n>Each instance admits a set of acceptable labels, but the learner observes only one acceptable label per round.
  arXiv  Detail & Related papers  (2026-01-29T09:39:11Z)
• 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)
• Stabilizing Extreme Q-learning by Maclaurin Expansion [51.041889588036895]
  Extreme Q-learning (XQL) employs a loss function based on the assumption that Bellman error follows a Gumbel distribution. It has demonstrated strong performance in both offline and online reinforcement learning settings. We propose Maclaurin Expanded Extreme Q-learning to enhance stability.
  arXiv  Detail & Related papers  (2024-06-07T12:43:17Z)
• The Implicit Bias of Minima Stability in Multivariate Shallow ReLU Networks [53.95175206863992]
  We study the type of solutions to which gradient descent converges when used to train a single hidden-layer multivariate ReLU network with the quadratic loss. We prove that although shallow ReLU networks are universal approximators, stable shallow networks are not.
  arXiv  Detail & Related papers  (2023-06-30T09:17:39Z)
• Type-II Saddles and Probabilistic Stability of Stochastic Gradient Descent [16.849376037005452]
  We show that saddle points in neural networks can be divided into two types, among which the Type-II saddles are especially difficult to escape from because the gradient noise vanishes at the saddle. The dynamics of SGD around these saddles are thus to leading order described by a random matrix product process. We leverage to show that saddle points can be either attractive or repulsive for SGD, and its dynamics can be classified into four different phases, depending on the signal-to-noise ratio in the gradient close to the saddle.
  arXiv  Detail & Related papers  (2023-03-23T08:17:10Z)
• Beyond the Edge of Stability via Two-step Gradient Updates [49.03389279816152]
  Gradient Descent (GD) is a powerful workhorse of modern machine learning. GD's ability to find local minimisers is only guaranteed for losses with Lipschitz gradients. This work focuses on simple, yet representative, learning problems via analysis of two-step gradient updates.
  arXiv  Detail & Related papers  (2022-06-08T21:32:50Z)
• Multi-fidelity Stability for Graph Representation Learning [38.31487722188051]
  We introduce a weaker uniform generalization termed emphmulti-fidelity stability and give an example. We present lower bounds for the discrepancy between the two types of stability, which justified the multi-fidelity design.
  arXiv  Detail & Related papers  (2021-11-25T01:33:41Z)
• Super-Convergence with an Unstable Learning Rate [20.13887962999915]
  Conventional wisdom dictates that learning rate should be in the stable regime so that gradient-based algorithms don't blow up. This note introduces a simple scenario where an unstable learning rate scheme leads to a super fast convergence. Our scheme uses a Cyclical Learning Rate where we periodically take one large unstable step and several small stable steps to compensate for the instability.
  arXiv  Detail & Related papers  (2021-02-22T02:05:47Z)
• A Weaker Faithfulness Assumption based on Triple Interactions [89.59955143854556]
  We propose a weaker assumption that we call $2$-adjacency faithfulness. We propose a sound orientation rule for causal discovery that applies under weaker assumptions.
  arXiv  Detail & Related papers  (2020-10-27T13:04:08Z)
• Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent [55.85456985750134]
  We introduce a new stability measure called on-average model stability, for which we develop novel bounds controlled by the risks of SGD iterates. This yields generalization bounds depending on the behavior of the best model, and leads to the first-ever-known fast bounds in the low-noise setting. To our best knowledge, this gives the firstever-known stability and generalization for SGD with even non-differentiable loss functions.
  arXiv  Detail & Related papers  (2020-06-15T06:30:19Z)
• The Curse of Performance Instability in Analysis Datasets: Consequences, Source, and Suggestions [93.62888099134028]
  We find that the performance of state-of-the-art models on Natural Language Inference (NLI) and Reading (RC) analysis/stress sets can be highly unstable. This raises three questions: (1) How will the instability affect the reliability of the conclusions drawn based on these analysis sets? We give both theoretical explanations and empirical evidence regarding the source of the instability.
  arXiv  Detail & Related papers  (2020-04-28T15:41:12Z)
• An Equivalence Between Private Classification and Online Prediction [43.37646702577754]
  We prove that every concept class with finite Littlestone dimension can be learned by an (approximate) differentially-private algorithm. We introduce a new notion of stability called "global stability" which is essential to our proof and may be of independent interest.
  arXiv  Detail & Related papers  (2020-03-01T19:20:37Z)

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.