Group-realizable multi-group learning by minimizing empirical risk

Navid Ardeshir, Samuel Deng, Daniel Hsu, Jingwen Liu · 2026

Read Group-realizable multi-group learning by minimizing empirical risk by Navid Ardeshir, Samuel Deng, Daniel Hsu, Jingwen Liu (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-2601-16922.txt.

Introduction

Navid Ardeshir, Samuel Deng, Daniel Hsu, and Jingwen Liu sharpen how much data group learning needs. Group learning must do well for each crowd in a pool. Crowds may overlap, and their count can be vast. Their 2026 preprint studies a case where each crowd's aim can be hit in full. In that case, less data is needed than in the loose case.

Plain risk cuts over the right class give the gain. The gain holds though crowd count is not fin. It needs just a fin gauge of crowd shape. Less data per task cuts cost in fair AI work. Such work spans loans, health, and school tools.

Catalog record

CREATORNavid Ardeshir, Samuel Deng, Daniel Hsu, Jingwen Liu
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE37 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-16922

Browse the full library · About the Tower of Babel

Full text

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

Group-realizable multi-group learning by minimizing empirical risk Navid Ardeshir, Samuel Deng, Daniel Hsu, Jingwen Liu Abstract The sample complexity of multi-group learning is shown to improve in the group-realizable setting over the agnostic setting, even when the family of groups is infinite so long as it has finite VC dimension. The improved sample complexity is obtained by empirical risk minimization over the class of group-realizable concepts, which itself could have infinite VC dimension. Implementing this approach is also shown to be computationally intractable, and an alternative approach is suggested based on improper learning. \altauthor Columbia University and Columbia University and Columbia University and Columbia University \Crefformat equation#2(#1)#3 \crefformat equation#2(#1)#3 \Crefrangeformat equation#3(#1)#4–#5(#2)#6 \crefrangeformat equation#3(#1)#4–#5(#2)#6 \Crefmultiformat equation#2(#1)#3 and #2(#1)#3, #2(#1)#3 and #2(#1)#3 \crefmultiformat equation#2(#1)#3 and #2(#1)#3, #2(#1)#3 and #2(#1)#3 keywords Multi-group learning, group-realizability, empirical risk minimization, sample complexity, computational complexity 1 Introduction Multi-group learning ( Rothblum and Yona 2021 ) extends the basic framework of statistical learning to study the performance of predictive models within families of subpopulations. Although multi-group learning can be cast as a special case of other learning frameworks that address subpopulation-level criteria ( Hebert-Johnson et al. 2018 ; Kim et al. 2019 ; Dwork et al. 2021 ; Haghtalab et al. 2023 , e.g.,) , the goal of this work is to study a natural assumption within multi-group learning— group-realizability —under which one might expect improved statistical efficiency and/or computational efficiency as compared to the general case. In multi-group learning (for binary classification), subpopulations are specified by subsets of the input domain \mathcal{X} , and the learning objective concerns a family of (possibly overlapping) subpopulations \mathcal{G}\subseteq 2^{\mathcal{X}} . In particular, for a given collection of benchmark classifiers \mathcal{H}\subseteq\{-1,1\}^{\mathcal{X}} and an excess error rate bound \epsilon\in\lparen 0,1\rparen , the learner seeks to construct a classifier f\colon\mathcal{X}\to\{-1,1\} using an i.i.d. sample from a probability distribution D over \mathcal{X}\times\{-1,1\} so that, with high probability, \err\lparen f\nonscript\>|\nonscript\>\mathopen{}g\rparen\leq\inf_{h\in\mathcal{H}}\err\lparen h\nonscript\>|\nonscript\>\mathopen{}g\rparen+\epsilon\quad\text{for each subpopulation $g\in\mathcal{G}$}. (1) Above, \err\lparen f\nonscript\>|\nonscript\>\mathopen{}g\rparen:=\Pr_{(\mathbf{x},\mathbf{y})\sim D}[f(\mathbf{x})\neq\mathbf{y}\nonscript\>|\nonscript\>\mathopen{}\mathbf{x}\in g] is the conditional error rate of a classifier f given g (defined whenever g has non-zero mass under the marginal of D over \mathcal{X} ). Importantly, each subpopulation g may have a different optimal benchmark classifier h_{g}^{*}\in\mathcal{H} , and it is possible that these per-group optimal classifiers have disagreements h_{g}^{*}(x)\neq h_{g^{\prime}}^{*}(x) at points of intersection x\in g\cap g^{\prime} . Because of this, it is possible that no f\in\mathcal{H} can satisfy \Cref eq:multigroup, and existing multi-group learning algorithms instead construct f as an ensemble classifier involving functions from \mathcal{H} and \mathcal{G} . Group-realizability is the assumption on (\mathcal{G},\mathcal{H},D) that, for each g\in\mathcal{G} , there is a benchmark classifier h_{g}^{*}\in\mathcal{G} such that \err\lparen h_{g}^{*}\nonscript\>|\nonscript\>\mathopen{}g\rparen=0 . Under this assumption, the goal in multi-group learning is to construct a classifier f such that \err\lparen f\nonscript\>|\nonscript\>\mathopen{}g\rparen\leq\epsilon for each g\in\mathcal{G} . Group-realizability should be contrasted with the standard realizability (or separability ) assumption on (\mathcal{H},D) , i.e., the existence of h^{*}\in\mathcal{H} such that \Pr_{(\mathbf{x},\mathbf{y})\sim D}[h^{*}(\mathbf{x})\neq\mathbf{y}]=0 . Realizability implies group-realizability, but the reverse implication need not hold (unless, e.g., \mathcal{X}\in\mathcal{G} ). A marked difference between the ”realizable” and ”agnostic” (i.e., non-realizable) settings in (single-group) statistical learning comes in the worst-case dependence on \epsilon in the sample complexity: roughly 1/\epsilon versus 1/\epsilon^{2} (ignoring the dependence on \mathcal{H} ). A similar sample complexity difference also manifests in multi-group learning with and without the group-realizability assumption, as shown by Tosh and Hsu 2021 for the case where the family of subpopulations \mathcal{G} is finite. Moreover, the computational complexity is, roughly speaking, no worse than that of finding a consistent classifier in \mathcal{H} for each subpopulation g\in\mathcal{G} . This is notable since, for some classes such as half-spaces, finding a consistent classifier can be done in polynomial-time, whereas finding a classifier in the class with approximately-minimal error rate on a sample may be computationally intractable ( Feldman et al. 2009 ; Guruswami and Raghavendra 2009 ) . In this work, we show that the improved sample complexity (up to a logarithmic factor in 1/\epsilon ) for multi-group learning under group-realizability extends to the case where \mathcal{G} is infinite but has finite VC dimension. To achieve this sample complexity guarantee, we introduce the class \mathcal{C}_{\mathcal{G},\mathcal{H}}\subseteq\{-1,1\}^{\mathcal{X}} of group-realizable concepts : the set of functions c\colon\mathcal{X}\to\{-1,1\} consistent with the group-realizability assumption. With this definition in hand, our main result follows simply from empirical risk minimization (ERM) over \mathcal{C}_{\mathcal{G},\mathcal{H}}. In particular, there is no explicit or algorithmic regularization (in contrast to the algorithm of Tosh and Hsu 2021 , which involves a form of aggregation). Remarkably, it is possible for this class \mathcal{C}_{\mathcal{G},\mathcal{H}} to have infinite VC dimension, even when both \mathcal{G} and \mathcal{H} have finite VC dimension. ERM with infinite VC dimension classes is not generally an effective learning procedure in the standard statistical learning setup. However, in our setup, the efficacy of ERM with such a class comes from the restricted sense in which the learned classifier is evaluated. This is very simply captured using shattering coefficients. The statistical efficiency of the \mathcal{C}_{\mathcal{G},\mathcal{H}} class is reminiscent of the near-optimality of ERM in realizable (single-group) statistical learning, where search over \mathcal{H} itself is sufficient for similar sample complexity guarantees. Unfortunately, the rub with using ERM—which ultimately boils down to just finding a function c\in\mathcal{C}_{\mathcal{G},\mathcal{H}} consistent with the training data—is computational intractability: it generally involves solving an \mathsf{NP} -hard problem. The hardness does not come from any potential intractability of optimizing over \mathcal{H} or even enumerating \mathcal{G} : our proof of hardness in \Cref sec:computation goes via a reduction to instances where \mathcal{G} has polynomial-size and optimization over \mathcal{H} can be performed in polynomial-time. Rather, the difficulty appears to come from even specifying a classifier in \mathcal{C}_{\mathcal{G},\mathcal{H}} when one can only refer to classifiers from \mathcal{H} and subpopulations from \mathcal{G} . We show, in \Cref sec:improper, how ”improper learning” can get around this intractability in certain cases. Relation to prior works The literature on multi-group learning has focused primarily on the general (agnostic) setting, whether in the online setting ( Blum and Lykouris 2020 ; Deng et al. 2024 ) or the batch setting ( Rothblum and Yona 2021 ; Tosh and Hsu 2021 ; Rittler and Chaudhuri 2023 ; Deng and Hsu 2024 ) . The work of Tosh and Hsu 2021 provides a (batch) multi-group learning algorithm, called ”Prepend”, for families of subpopulations \mathcal{G} that may be infinite but have finite VC dimension. Prepend—which is nearly identical to an algorithm proposed by Globus-Harris et al. 2022 in a somewhat related context—is efficient as long as it has access to an oracle for solving ERM-type optimization problems over \mathcal{H}\times\mathcal{G} . Such ”oracle efficient” algorithms have a long history in many areas of learning theory ( Kalai and Vempala 2005 ; Kakade and Kalai 2005 ; Dasgupta et al. 2007 ; Dudík et al. 2011 ; Dann et al. 2018 ; Foster and Rakhlin 2020 ; Haghtalab et al. 2022 ; Wang et al. 2022 ; Garg et al. 2024 , e.g.,) , including the closely related subject of subgroup fairness ( Kearns et al. 2018 ) . An important drawback of Prepend, however, is that its sample complexity is suboptimal: thr dependence on \epsilon is roughly 1/\epsilon^{3} . (Here, for simplicity, we are omitting the dependence on \mathcal{G} ,

Read the complete text