Stability and List-Replicability for Agnostic Learners
Ari Blondal, Shan Gao, Hamed Hatami, Pooya Hatami · 2025
Read Stability and List-Replicability for Agnostic Learners by Ari Blondal, Shan Gao, Hamed Hatami, Pooya Hatami (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-05333.txt.
Introduction
Ari Blondal and three co-authors resolve open problems in learning theory in twenty twenty-five. Online learnability and globally stable PAC learnability were known to coincide for binary classification. Recent work showed that equivalence fails in the agnostic setting. There, only finite hypothesis classes turned out to be globally stable learnable.
That verdict made agnostic stability too restrictive to be useful. Two relaxations of the stability demand were proposed to rescue it. This paper characterizes exactly which classes are learnable under those relaxed conditions. Both open problems from the earlier work are resolved. In one relaxation, the stability parameter may depend on the excess error. Readers get a fuller map of what stable learning can mean when data need not fit the class.
Catalog record
| CREATOR | Ari Blondal, Shan Gao, Hamed Hatami, Pooya Hatami |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 50 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-05333
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Stability and List-Replicability for Agnostic Learners Ari Blondal, Shan Gao, Hamed Hatami, Pooya Hatami 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. 1 Introduction We follow the standard PAC learning framework for binary classification as, for example, described in [ SSBD14 ] . In this model, a learner receives a sample of i.i.d. examples from an unknown distribution \mathcal{D} over X\times\{0,1\} , where X is the domain set, and \{0,1\} represents the two possible labels in binary classification. The learner’s goal is to produce a hypothesis h:X\to\{0,1\} that minimizes the population loss \mathcal{L}_{\mathcal{D}}(h)\coloneqq\Pr_{(\bm{x},\bm{y})\sim\mathcal{D}}[h(\bm{x})\neq\bm{y}]. Here, and throughout the paper, we use boldface letters to denote random variables and use the notation (\bm{x},\bm{y})\sim\mathcal{D} to express that (\bm{x},\bm{y}) is a random variable distributed according to \mathcal{D} . Formally, a learning rule is a (randomized) function \bm{\mathcal{A}} that maps any sample S\in(X\times\{0,1\})^{*}\coloneqq\bigcup_{n=0}^{\infty}(X\times\{0,1\})^{n} to a hypothesis \bm{\mathcal{A}}(S)\in\{0,1\}^{X} . Thus, for any given sample S , \bm{\mathcal{A}}(S) is a random variable taking values in \{0,1\}^{X} . Throughout this paper, all learning rules are assumed to be randomized. We consistently use X to denote the domain, \{0,1\} to represent the two possible labels, and \mathcal{D} always refers to a distribution over X\times\{0,1\} . For an integer n>0 , we use [n] to denote the set \{1,\dots,n\} . Given a hypothesis class \mathcal{H}\subseteq\{0,1\}^{X} , the goal of PAC (Probably Approximately Correct) learning is for the learner to produce, with high probability, a hypothesis whose population loss is close to the best achievable within \mathcal{H} , defined as \mathcal{L}_{\mathcal{D}}(\mathcal{H})\coloneqq\inf_{h\in\mathcal{H}}\mathcal{L}_{\mathcal{D}}(h). A class \mathcal{H} is PAC learnable if there is a learning rule \bm{\mathcal{A}} and a function n(\epsilon,\delta) such that for any \epsilon,\delta>0 , \Pr_{\bm{S}\sim\mathcal{D}^{n}}[\mathcal{L}_{\mathcal{D}}(\bm{\mathcal{A}}(\bm{S}))\leq\mathcal{L}_{\mathcal{D}}(\mathcal{H})+\epsilon]\geq 1-\delta\ \text{ where }n=n(\epsilon,\delta). PAC learning is studied in the realizable case , where we assume \mathcal{L}_{\mathcal{D}}(\mathcal{H})=0 , and the agnostic case , where \mathcal{L}_{\mathcal{D}}(\mathcal{H})>0 . Stability. Replicability is a fundamental principle of the scientific method. A study is replicable if it consistently yields the same results when repeated with new data drawn from the same distribution or source. In recent years, machine learning has seen a growing need to address the replication crisis [ Bal23 , Bak16 ] . Impagliazzo, Lei, Pitassi, and Sorrel [ ILPS22 ] initiated a formal theoretical framework for studying replicability in machine learning. Since their work, a rapidly growing body of research has emerged that introduced various notions of replicability. These works and subsequent research showed that many of these notions of replicability are essentially equivalent. Furthermore, they established deep connections to other foundational concepts in learning theory, such as differential privacy [ CMY23 , BGH+23 , KKMV23 , GKM21a , GKM21b , CCMY24 ] . Additionally, a growing body of work has explored replicability in many data analysis and learning settings [ ILPS22 , BGH+23 , KVYZ23 , EKK+23 , EKM+23 , EHKS24 , KKL+24 , KKMV23 ] . In this paper, we focus on the notion of replicability where the learning algorithm is expected to often produce the same predictor when applied to two independent and identically distributed inputs. This concept was first introduced under the term global stability in [ BLM20 ] and has since been refined and explored in subsequent works [ GKM21a , KKMV23 , CMY23 , CCMY24 ] . We start by defining stability and global stability. Definition 1.1 (Stability) . Given a function \rho:(0,1)\rightarrow(0,1) , a learning rule \bm{\mathcal{A}} is a \rho -stable learner for a hypothesis class \mathcal{H} if the following holds. For every \epsilon>0 , there exists n=n(\epsilon) such that for every realizable distribution \mathcal{D} , there exists a hypothesis h satisfying \mathcal{L}_{\mathcal{D}}(h)\leq\epsilon and \Pr_{\begin{subarray}{c}\bm{S}\sim\mathcal{D}^{n}\end{subarray}}[\bm{\mathcal{A}}(\bm{S})=h]\geq\rho(\epsilon). (1) Similarly, we call \bm{\mathcal{A}} a \rho -stable agnostic learner for \mathcal{H} , if there exists n=n(\epsilon) such that for every distribution \mathcal{D} on X\times\{0,1\} , there exists a hypothesis h\in\{0,1\}^{X} that satisfies ( 1 ) and \mathcal{L}_{\mathcal{D}}(h)\leq\mathcal{L}_{\mathcal{D}}(\mathcal{H})+\epsilon. (2) To simplify terminology, we use the term \rho -stable to describe a hypothesis class \mathcal{H} with a \rho -stable learner . Likewise, we call \mathcal{H} agnostically \rho -stable if it has a \rho -stable agnostic learner. Definition 1.2 (Global Stability) . We say that a hypothesis class \mathcal{H} is globally stable if it is \rho -stable for a fixed constant \rho\in(0,1) . Similarly, a hypothesis class \mathcal{H} is agnostically globally stable if it is agnostically \rho -stable for such a constant. In short, global stability requires the stability parameter in Equation 1 to be uniform, meaning it must not depend on \epsilon . Bun, Livni, and Moran [ BLM20 ] showed that in the realizable setting, global stability is fully characterized by bounded Littlestone dimension ( Definition 1.12 ). This result, combined with the seminal works of [ Lit88 , ABL+22 ] , shows that global stability is equivalent to online learnability and approximately private learnability, as well as, some other notions of replicability [ KKMV23 , GKM21a , BGH+23 ] . In contrast, the agnostic setting reveals a different picture. Chase, Chornomaz, Moran, and Yehudayoff [ CCMY24 ] proved the following characterization using a topological approach. Theorem 1.3 ( [ CCMY24 ] ) . A hypothesis class \mathcal{H} is agnostically globally stable if and only if \mathcal{H} is finite. This striking result shows that agnostic global stability is far more restrictive than its realizable counterpart. Since finite classes are trivially stable, Theorem 1.3 shows that agnostic global stability is too restrictive to lead to interesting learnability phenomena. To remedy this, Chase et al. [ CCMY24 ] introduced two relaxations of agnostic global stability and proposed a study of which hypothesis classes can be learned under these relaxed notions of stability. Excess-error dependent stability. The first suggested relaxation, coincides with our definition of \rho -stability in Definition 1.1 . A hypothesis class \mathcal{H} is called excess-error dependent stable if it is agnostically \rho -stable for some \rho:(0,1)\to(0,1)