A One-Inclusion Graph Approach to Multi-Group Learning

Noah Bergam, Samuel Deng, Daniel Hsu · 2026

Read A One-Inclusion Graph Approach to Multi-Group Learning by Noah Bergam, Samuel Deng, Daniel Hsu (2026) 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-2603-23208.txt.

Introduction

Bergam, Deng, and Hsu prove new bounds on the sample complexity of multi-group learning. Their algorithm extends the one-inclusion graph method with a generalized form of bipartite matching. In the group-realizable setting, a matching lower bound shows their log n over n rate cannot be improved in general. A relaxed version of the goal yields more. When the test group is picked without seeing the sample, their method reaches the optimal 1 over n rate.

Catalog record

CREATORNoah Bergam, Samuel Deng, Daniel Hsu
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE123278
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.23208

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A One-Inclusion Graph Approach to Multi-Group Learning Noah Bergam, Samuel Deng, Daniel Hsu Abstract We prove the tightest-known upper bounds on the sample complexity of multi-group learning. Our algorithm extends the one-inclusion graph prediction strategy using a generalization of bipartite b b -matching. In the group-realizable setting, we provide a lower bound confirming that our algorithm’s log ⁡ n / n \log n/n convergence rate is optimal in general. If one relaxes the learning objective such that the group on which we are evaluated is chosen obliviously of the sample, then our algorithm achieves the optimal 1 / n 1/n convergence rate under group-realizability. 1 Introduction Multi-group learning is a natural extension of statistical learning formalized by Rothblum and Yona 2021 that seeks to address learnability on subpopulations. As in standard statistical learning (for binary classification), for an input space \mathcal{X} , label space \mathcal{Y}=\{0,1\} , and a hypothesis class \mathcal{H}\subseteq\{0,1\}^{\mathcal{X}} , the goal is to use an i.i.d. sample of n labeled training examples S\in(\mathcal{X}\times\{0,1\})^{n} from a probability distribution P to construct a classifier A(S)(\cdot) that can make accurate predictions on new points drawn from P . Multi-group learning introduces an additional consideration: a (potentially infinite) family of (possibly overlapping) subsets of the input space \mathcal{G}\subseteq\{0,1\}^{\mathcal{X}} , or groups . Instead of seeking a classifier that is accurate on the entire domain \mathcal{X} , multi-group learning asks for accuracy guarantees on the groups in \mathcal{G} (either simultaneously for all g\in\mathcal{G} , or downstream on an a priori unknown target g\in\mathcal{G} ). A natural error measure on group g\in\mathcal{G} is the group-conditional error rate \Pr_{(x,y)\sim P}[A(S)(x)\not=y\mid x\in g]. Our benchmark on a group g\in\mathcal{G} is the minimum group-conditional error rate achievable by some ( g -specific) hypothesis h^{*}_{g}\in\mathcal{H} . The difficulty, of course, is that for different g,g^{\prime}\in\mathcal{G} , the best benchmark predictors h^{*}_{g} and h^{*}_{g^{\prime}} may be quite different. We focus on the group-realizable setting of multi-group learning, introduced in Tosh and Hsu 2022 and extended by Ardeshir et al. 2026 . Recall that classical realizable PAC learning assumes there exists some h^{*}\in\mathcal{H} that perfectly labels all points, i.e., \Pr_{(x,y)\sim P}[h^{*}(x)\not=y]=0. Group-realizability is the extension of this assumption to multi-group learning where, for each g\in\mathcal{G} , there are (potentially different) hypotheses h^{*}_{g}\in\mathcal{H} , such that \Pr_{(x,y)\sim P}[h^{*}_{g}(x)\not=y\mid x\in g]=0. Classical realizability implies group-realizability, but the converse need not hold. When \mathcal{X}\in\mathcal{G} , group-realizability reduces back to realizability, so one may view group-realizability as a natural generalization of the realizability assumption. From this perspective, a natural question is whether comparable rates for learning obtained in classical (single-group) statistical learning models can be obtained in their multi-group extensions. In the prediction model of learning , Haussler et al. 1994 showed that the one-inclusion graph (OIG) prediction strategy achieves the optimal expected error rate guarantee of \E_{S\sim P^{n}}\left[\Pr_{(x,y)\sim P}\left[A_{\mathrm{OIG}}(S)(x)\not=y\right]\right]\leq\frac{d_{\mathcal{H}}}{n}, (1) where d_{\mathcal{H}} denotes the VC dimension of \mathcal{H} . Empirical risk minimization (ERM) , on the other hand, introduces a suboptimal multiplicative \log(n/d_{\mathcal{H}}) factor to ( 1 ). Similarly, in the well-known PAC model of learning , Aden-Ali et al. 2023b show that a simple online-to-batch aggregation atop the one-inclusion graph achieves optimal rates, while ERM picks up a suboptimal \log(n/d_{\mathcal{H}}) factor. The best-known results in the multi-group setting exhibit a comparable state of affairs. To analyze group-realizable multi-group learning, Ardeshir et al. 2026 introduced the class of group-realizable concepts , the set of binary-valued functions on \mathcal{X} compatible with the group-realizability assumption. They show that ERM over this class is indeed a multi-group learner, but their rates suffer a similar \log n dependency. Though their results were originally stated for the multi-group extension of the PAC model, the same suboptimality can be found in the multi-group prediction model through simply integrating the tails of their high probability results. In view of the applicability of the one-inclusion graph algorithm in shaving the \log n to achieve optimal rates in ( 1 ), a natural question is whether one can generalize the one-inclusion graph algorithm to our setting. Of course, a naïve application of the one-inclusion graph algorithm using \mathcal{H} cannot hope to provide group-wise guarantees. The challenge is how to extend this algorithm to address the (possibly infinite) collection of groups \mathcal{G}. Main results. Our main result is a novel generalization of the one-inclusion graph algorithm to the multi-group setting that achieves a suite of optimal and near-optimal guarantees. Our learner obtains optimal guarantees when evaluation involves a single downstream g\in\mathcal{G} . In the prediction model, we guarantee \E_{S\sim P^{n}}\left[\Pr_{(x,y)\sim P}[A_{\mathrm{MgOIG}}(S)(x)\neq y\land x\in g]\right]\leq\frac{d_{\mathcal{H}|g}}{n}\quad\forall g\in\mathcal{G}, where d_{\mathcal{H}|g} is the VC dimension of \mathcal{H} restricted to group g. (To get a conditional error rate bound, divide both sides by the probability mass of g under P .) When evaluation requires a simultaneous guarantee over all g\in\mathcal{G} (as previous work considers), we achieve the near-optimal guarantee \E_{S\sim P^{n}}\left[\sup_{g\in\mathcal{G}}\Pr_{(x,y)\sim P}[A_{\mathrm{MgOIG}}(S)(x)\neq y\land x\in g]\right]\leq O\left(\frac{d_{\mathcal{H}|\mathcal{G}}}{n}+\frac{d_{\mathcal{G}}\log(n/d_{\mathcal{H}|\mathcal{G}})}{n}\right), where d_{\mathcal{H}|\mathcal{G}}=\sup_{g\in\mathcal{G}}d_{\mathcal{H}|g} , and d_{\mathcal{G}} is the VC dimension of \mathcal{G} . Note that the two types of guarantees above (single downstream group vs. simultaneous) can be distinguished by whether the learner’s classifier is evaluated on a group chosen obliviously of the sample, or on a group chosen adversarially based on the sample. In comparison to the previously best-known rates of Ardeshir et al. 2026 , our result removes the \log n factor from the d_{\mathcal{H}|\mathcal{G}} term. For the second term, our lower bound in Theorem 2 demonstrates that the dependence on \log n/n cannot in general be improved. Applying the recently developed machinery of Aden-Ali et al. 2023b , Asilis et al. 2024 , and Dughmi et al. 2025 , we extend our algorithm’s guarantees to the multi-group PAC model in both the group-realizable and agnostic settings. Together, these results give the tightest known upper bounds for multi-group learning. For clarity, we only state the results for the prediction model in Theorem 1 , our main theorem. We defer the guarantees for the PAC model to Appendix B (for the group-realizable case) and Appendix C (for the agnostic case). Our paper is organized as follows: • Section 2.1 defines multi-group transductive error and multi-group prediction error , which generalize the relevant notions of Haussler et al. 1994 in the analysis of the one-inclusion graph, reviewed in Section 2.2 . Of particular importance is the multi-group transductive error, the main quantity we control to obtain the in-expectation and high probability results. • Section 3 introduces our generalization of the one-inclusion graph algorithm applied to the group-realizable concepts. The algorithm requires introducing a multi-group variant of the maximum bipartite matching problem in Section 3.1 that may be of independent interest. Section 3.2 demonstrates that an optimal solution to this “multi-group matching problem” results in a well-defined learner with guarantees on the multi-group transductive error. Section 3.3 shows that the optimal solution can indeed be found through a duality argument. • Section 4 provides a novel lower bound for group-realizable multi-group learning. In particular, it shows that the simultaneous guarantee may require the slower \log n/n rate that is avoided when one only seeks a guarantee for a single downstream group. Related work. Rothblum and Yona 2021 initiated the study of multi-group learning in the agnostic (batch) setting, in which the best benchmark

Read the complete text