Learning With Multi-Group Guarantees For Clusterable Subpopulations
Authors: Jessica Dai
Nika Haghtalab
Eric Zhao
Venue: ICML 2025 poster (2025)
Keywords: per-subpopulation guarantees
clustering
fairness
online prediction
multicalibration
Primary area: theory->everything_else
TL;DR: An alternative perspective on providing per-subgroup guarantees in the context of the overall population.

Abstract: A canonical desideratum for prediction problems is that performance guarantees should hold not just on average over the population, but also for meaningful subpopulations within the overall population. But what constitutes a meaningful subpopulation? In this work, we take the perspective that relevant subpopulations should be defined with respect to the clusters that naturally emerge from the distribution of individuals for which predictions are being made. In this view, a population refers to a mixture model whose components constitute the relevant subpopulations. We suggest two formalisms for capturing per-subgroup guarantees: first, by attributing each individual to the component from which they were most likely drawn, given their features; and second, by attributing each individual to all components in proportion to their relative likelihood of having been drawn from each component. Using online calibration as a case study, we study a multi-objective algorithm that provides guarantees for each of these formalisms by handling all plausible underlying subpopulation structures simultaneously, and achieve an $O(T^{1/2})$ rate even when the subpopulations are not well-separated. In comparison, the more natural cluster-then-predict approach that first recovers the structure of the subpopulations and then makes predictions suffers from a $O(T^{2/3})$ rate and requires the subpopulations to be separable. Along the way, we prove that providing per-subgroup calibration guarantees for underlying clusters can be easier than learning the clusters: separation between median subgroup features is required for the latter but not the former.

Learning With Multi-Group Guarantees For Clusterable Subpopulations
Jessica Dai Nika Haghtalab Eric Zhao
Abstract
1. Introduction
For systems that make predictions about individuals, is well-understood that good performance on average across the population may not imply good performance at indi- vidual level. On the other hand, while the ideal system might be one that can provide per-individual performance guaran- tees, such system may be intractable to learn from data, if it exists at all. To address these challenges, per-subpopuuaatin guarantees have emerged as a widely-accepted approach that balances tractability with ensuring good performance across subpopulations (e.g., Blum et al. (2017); Hébert-Johnson et al. (2018); Hashimoto al. (2018); Lahoti et al. (2020); Wang et al. (2020); Haghtalab et al. (2022)). Such guar- antees may also be desirable for normative or regulatory reasons to capture notions of fairness, or because domain shift often involves changes in the proportions of subgroups. Therefore, the subpopulations for which guarantees are pro- vided should be those that are deemed especially significant, salient, or relevant.
A canonical desideratum for prediction problems is that performance guarantees should hold not just on average over the population, but also for meaningful subpopulations within the overall pop- ulation. But what constitutes a meaningful sub- population? In this work, we take the perspective that relevant subpopulations should be defined with respect to the clusters that naturally emerge from the distribution of individuals for which pre- dictions are being made. In this view, popula- tion refers to mixture model whose components constitute the relevant subpopulations. We sug- gest two formalisms for capturing per-subgroup guarantees: first, by attributing each individual to the component from which they were most likely drawn, given their features; and second, by attributing each individual to all components in proportion to their relative likelihood of having been drawn from each component. Using on- line calibration as a case study, we study a multi- objective algorithm that provides guarantees for each of these formalisms by handling all plausi- ble underlying subpopulation structures simulta- neously, and achieve (/T1/2) rate even when the subpopulations are not well-separated. In com- parison, the more natural dluster-then-prediie ap- proach that first recovers the structure of the sub- populations and then makes predictions suffers from a ( rate and requires the subpopula- tions be separable. Along the way, we prove that providing per-subgroup calibration guaran- tees for underlying clusters can be easier than learning the clusters: separation between median subgroup features is required for the latter but not the former.
What, then, defines relevant subpopulation? One influen- tial perspective considers a subpopulation as a predefined combination of feature values, where individuals are repre- sented as feature vectors (c.g.. JJōbert-Johnson et al. (2018)). In our work, we take an alternative view on what constitutes subpopulation of interest. We propose that the relevant subgroups for a particular prediction task should be exactly those subgroups that emerge endogenously within the distri- bution of the individuals being considered for that task. This means that the group membership(s) of any individual can- not be determined through their features alone; instead, their group identity can be understood only by placing their indi- vidual features in the context of the rest of the population. In effect, rather than being defined priori, these subgroups must be learned about from data in unsupervised sense.
1.1. Defining subpopulations via statistical identifiability
One reason think of group membership in context of the population rather than as deterministic functions of in- dividual features is a normative perspective. A common critique of standard practice in modeling subgroups is that observable (demographic) features are only approximations of more complex phenomena that are related to-but not directly causal of-shhred life experience. Therefore, de-
Alphabbetica order. 'Department of Electrial Engineering and Computer Science, U.C. Berkeley, Berkeley, CA, USA. Correspon- dence to: Jessica Dai <jessicadai berkeley.edu>>.
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Learning With Multi-Group Guarantees For Clusterable Subpopulations
manding "equal performance" across rigid (demographic) categories does not necessarily imply "fairness" in nor- mative sense (see, e.g., Benthall & Haynes (2019); Hu & Kohler-Hausman (2020); Hu (2023) for more extended dis- cussion). In some sense, our approach can be seen as an at- tempt to develop a more constructivist perspective on defin- ing subpopulations-
1.2. Our approach
To operationalize our approach, our measures of per-group performance must handle the fact that any individual's 's group membership can be at best approximately inferred, e.g. as probabilities representing the likelihood that that individual belonged to each group. Accordingly, we study two natural approaches to measuring per-group error. The first, which we refer to as discriminant error, attributes the error an indi- vidual experiences only to the group that the individual most likely belongs to. This corresponds typical notions of clustering error and is often used in existing approaches to handling uncertainty in group membership, which is effec- tively to ignore it (see, e.g., discussion in Dong et al. (2024)), We also study a probabilistic alternative, which we term likelihood error, where we attribute the error an individual experiences to every group, but weighted according to the likelihoods of membership in each group. This likelihood- based notion of per-group error explicitly acknowledger the existence of meaningful uncertainty in group member- ship. As a consequence, likelihood error also provides some reasonable robustness properties (e.g.. to changes in the rela- tive proportions of subgroups), and, relative to discriminant error, improves guarantees for subgroups that comprise a smaller proportion of the total population.
individuals in context with others for whom those predictions are made, and allowing group definitions vary based on the partieular prediction task-as opposed to an essentialist one. Of course, we can- not claim to fully resolve these normative challenges or realize these goals; however, we think of them as a reason to explore different ways of understanding the relationship between groups and individuals.
Because we cannot determine group membership solely based on an individual's feature vector, our problem setting requires some structure on the domain; in particular, fea- tures must be clusterable. Then, if all one initially knows about the population is that it is comprised of multiple sub- populations where group membership affects feature real- izations, determining subgroup membership based only on those realizations is the best one can expect to do. Our focus on statistically identifiable groups is in contrast with the identifiable groups studied when subpop- ulations are defined as combinations of feature values. In those settings, it is necessary to ensure that membership can be distinguished as efficiently as possible (c.g., through low circuit complexity, as multicalibration was initially de- scribed in Hébert-Johnson et al. (2018)); in our setting, the key challenge is instead identify membership as ac- curately possible, because group membership itself is uncertain.
computationally- iatiraationnlly-ddnnfibbblle
Both of these measures, however, require knowledge of the subgroup distributions- is, the likelihood that any par- ticular individual (feature vector) belongs to (was drawn from) any particular group group-which which depends on the pop- ulation distribution for the prediction task, and are there- fore initially unknown. The natural strategy for addressing the problems of unknown subgroups and unknown labels is to first complete the unsupervised task of learning the subgroups, then for each of the learned distributions com- plete the supervised task of learning to predict; we call this the cluster-then-predic approach. The overall prediction quality of this approach critically depends on how well the "clustering" stage can be performed task that often requires a large number of observations and separation be- tween subpopulations. We circumvent this problem through multi-objectiin approach (e.g.. Haghtalab et al. (2022; 2023)) where, instead of learning the exact underlying clus- tering, we construct a class of plausible clusterings and provide high-quality per-group predictions for all of them simultaneously. What clusterings are "plausible," " and how can we provide a solution that works for all of them? These constitute the central technical thrusts of our work.
We also note that finding statistically identifiable subpop- ulations from data (in the sense of learning membership likelihoods), and using those subgroups downstream, is common in audit settings when true subgroup labels are unknown. In these cases, inferring or estimating group membership is natural (and sometimes even necessary) approach. For example, it is well-known that names are often associated with demographic identity (Elder & Hayes, 2023), and audits of resume screening systems in practice often use those assumed associations rather than explicitly- stated demographic identity (c.g., Kang et al. (2016); Wilson & Caliskan (2024)). More generally, an extensive literature discusses how demographic labels might be imputed from data-e.g., name and census tract, in the well-known "BISG" (Bayesian Improved Surname Geocoding) approach (Elliott et al., 2009) and its variants; how those labels might be used for downstream purposes (c.g. auditing lending decisions (Zhang, 2018)); and how those estimates ought to be in- corporated in a mathematical sense to those downstream applications (c.g., Dong et al. (2024)).
1) Understanding the structure of subpopulations. We consider the class of all plausible group membership func- tions corresponding to the two formalisms of discriminant and likelihood error. We show that for both formalisms, the complexity of the appropriate class characterized by the pseudodimension of possible likelihood ratios. Furthermore,
2

---

Learning With Multi-Group Guarantees For Clusterable Subpopulations
when our model is instantiated with mixture of exponential families (e.g. Gaussian mixture models), we show that the pseudodimension of group membership functions is linearly bounded by the dimension of the sufficient statistic.
et al., 2018; Lahoti et al., 2020). A separate line of work considers learning when demographie labels are available but noisy (Awasthi et al., 2020; Wang et al., 2020). Yet another approach is to use separate estimator for group membership (Awasthi et al., 2021; Chen et al., 2019; Kallus et al., 2022); we note that our notions of per-group perfor- mance could be applicable to these methods as well, even if our definitions of "group" are different. Liu et al. (2023) also propose means of understanding group identity in context with the rest of the population, in this case through social networks.
2) Multi-objecttiv algorithms for per-subgroup guaran- tees. We leverage recent results in multi-objective learning to minimize error simultaneously over all possible clus- terings of the data. Using calibration as a case study, we show how to extend recent online multicalibration algo- rithms (Haghtalab et al., 2023) so that they provide per- subpopulation guarantees for classes of real-valued distin- guisher functions of low complexity, and by extension, fam- ilies of clustering functions. For both discriminant and likelihood calibration error, our multi-objective approach achieves O(71/2) online error without requiring separabil- ity in the underlying clusters. This is in contrast to the cluster-then-preed approach, for which we demonstrate ((32/3) error rates even under separability assumptions.
Finally, though intersectionality is not the focus of our work, our model of subpopulations is one approach to providing guarantees for unobservable marginalized subgroups. In particular, we see our model as an alternative to the practice of enumerating all prossibly-overlappiin by intersections of feature values, as in Hébert-Johnson et al. (201 8), which assumes that unobservable marginalized subgroups can be approximated through such feature sets, We seek to to explicitly incorporate intrinsic structure in covariates across groups, as suggested in Wang et al. (2020); more generally, the extent that power is central to what "defines" a group (Ovalle et al., 2023), our model gives an ioplication-speciiie way to discuss it (i.e., in terms of how subgroup distributions appear).
subgroups defined
3) Towards aeriistiialll-deentffaaaal subpopulations. Be- yond the technical approach, we view our work as an im- portant step towards reasoning about group membership in context of the actual population on which predictions are being made. We argue that subpopulations should be defined endogenously, rather than characterized by explicit combinations of feature values. Our framework also pro- vides a language for formalizing the relationship between explicitly learning subgroups, as opposed to providing high quality predictions for them: in fact, the former (which often requires separation between subpopulation means) is not necessary for the latter.
2. Preliminaries
Our generative model. Let X' E Rd denote a d- dimensional instance space and y [0 denote the label or outcome space. We consider a generative model over X' x y, where instances are generated from a mixture of k distributions and the conditional outcome distribution is independent of the component from which the instance is generated. Formally, we define a discrete hidden-state endogenous subgroups generative model J, such that
1.3. Related work
Multicalibration. Calibration is a well-studied objective in online forecasting (Dawid, 1982; Hart, 2022), with clas- sical literature having studied calibration across multiple sub-populations (Foster & Kakade, 2006) and recent lit- erature having studied calibration across computationally- identifiable feature groups JHébert-Johnson et al., 2018). The latter thread of work, known as multicalibration, has found wide range of connections Bayes optimality, conformal predictions, and computational indistinguishabil- ity (Dwork et al., 2021; Gopalan et al., 2022; Gupta et al., 2022; Hébert-Johnson et al., 2018; Jung et al., 2021; 2023). We use online multicalibration algorithms (Gupta et al., 2022; Haghtalab et al., 2023) as a building block for effi- ciently obtaining per-group guarantees in our model.
f(z,8) v) x fly (x) 19)()),
where f(g) = w. is the distribution over [k]] corresponding to mixing weights wy E [o. 1] with Ege [k] "'y = 1: f(x g) is the density of component g, and f 2) is a conditional label distribution that is independent of g. In this work. we assume that f(r I g) belongs to a class of densities F. For example, F could indicate the class of Gaussian mixture models (as we study in Section 3), or an exponential family (as we discuss in Section 4). Then, each pair (z, y) is generated by first sampling integer g E [k] according to weights (wi,..., wa);; then sampling x [(x 9). and finally sampling y according to f(y x). For clarity, we will often suppress wy in the following exposition, but our results follow without loss of generality as long as all w are bounded below by a constant.
Fair machine learning. The fair machine literature has developed various approaches to handling uncertainty in group membership. One strategy is to avoid enumerating subgroups entirely, and instead focus on identifying subsets of the domain where prediction error is high (Hashimoto
3

---

Learning With Multi-Group Guarantees For Clusterable Subpopulations
Online prediction. Our high level goal is to take high- quality actions for instances that are generated from unknown endogenous subgroups model. Let A denote the action space. Examples of action spaces for prediction tasks include A = {0, } where an action refers to a predicted label, or A = [o, 1] where an action refers to predicting the probability that the label is 1. We consider an online prediction problem where sequence of outeenee pairs (11, 91), (fr,yr) is generated i.i.d. from an known generative model f supported on X x V. At time I, the learner must take an irrevocable action d, E AA having seen only F1:t and 91:t-1. Equivalently, learner can be thought of as choosing a function ps : X + A that maps any feature æ to an action a. From this perspective, at time t the learner chooses pt having only observed 1 and Vi after which (Ire 3/3) is observed and the learner takes action pi (.).
individual's "group membership." Additionally, note that this objective is robust reweightings of subpopulations, as E [f(g] Tt, w.)e(at, w:]] = f(g) E [(( [g].
2.1. Model instantiation for calibration loss
For concreteness, this paper instantiates our model for the task of producing predictions that are calibrated with respect to clusterable subpopulations. However, our endogenous subgroups model extends beyond calibration to a number of other settings that can be studied under online approacha- bility, such as online conformal prediction and calibeating (Jung et al., 2023; Lee et al., 2022).
For studying calibrated predictions, we work with action space A A= [0. 1| and let ÿ E A correspond to the predicted probability that y = 1. Calibration is common require- ment on predictors, necessitating their predictions to be unbiased conditioned on the predicted value. For technical reasons such as dealing with the fact that predicted values can take any real values, calibration is more conveniently defined by considering buckets of predicted values. For- mally, we define set of buckets Va3 = 1/,, 2/x,..., 1} and say that prediction y belongs to bucket v (denoted by ÿ E v) when 10 - vl S 1/2A. Then, the cali- bration error of a sequence of predictors Pr.....Pr on instance-outeome pairs (æ1, vi)..... .., (FT, yr) defined by max Σ 1 [Pe(ze) E u] (px(x)) - -w)] In other words, calibration loss is the cumulative fx norm of the objective {(a. y) = [1 E e (a 1 v)
Performance on subpopulations. We evaluate the quality of the learner's actions using vector-valued loss function :: AA)] 3/ + E where & is some Euclidean space. Examples of loss functions include the scalar binary loss function f(a, y) == 11 la * y] and the vector-based calibration loss ((a,)) y), = 1 [a- = ua(a- 10a0-91 y).
In the style of Blackwell approachability (Blackwell, 1956), the learner's 's overall goal is to produce actions that lead to small cumulative loss on all the relevant subpopulations in the sequence (I1, .i...... (FT, as measured by a norm Il-ll. We envision relevant subpopulations to be exactly the mixture components of our generative model. However, it is not possible to determine the component that generates an instance (r., y) in a mixture model. Instead, we consider two notions of performing well on subpopulations. In the first, we purely attribute each (Ir, y) to the component g arg jajj [(j x. v) that was most likely responsible for producing (zr, y); that is, we aim to minimize
We can accordingly define two variants of the calibration error that account for miscalibration experienced by each component. In these definitions, we take À >> 0 to be fixed and clear from the context and suppress it in the notations.
In our first definition, called the discriminant calibration error, an instance (I, is purely attributed to the com- ponent g = arg max) f(j [x. that was most likely responsible for producing (1., y)-
T
arg max fú Ze, 21) Ela, mim JE[M]
1 Σ
max sE[R]
Definition 2.1 (Discriminant Calibration Error). Given a sequence of instance- pairs (I1, B1), , (IT, yr), the discriminant calibration error of predicted probabilities Vi- Vi..... Tr with respect to the endogenous subgroups model f f-as as specified by distributions f(ulx)) f()g)). and f(g) is defined as
The attribution of (x. y) to the most likely component corre- sponds to the usual task of clustering as is done practice.
In the second, we attribute each (z, 3) to a subpopulation g with probability f(g x. y); that is, we aim to minimize
DCE, (01:T FI:T. (T.T.V1:T)>
T Σ f(g Fes xe. laa, mill
T Σ
1 g = arg max f(i I v0)
max SEIR
max max gE(k] VEV,
JE(M]
[T+ E
(Tr v1
flr givlg Note that by definition, f(g x, = Eye(s) [x]s)ey is the probability was indeed responsible for producing (æ, y)-
When predictors PI...., Pr are used for making predictions dt = (x())) we denote the corresponding discriminant calibration error by DCE (r:)).
This objective considers the contribution of an individual to subgroup error in proportion to the uncertainty of that
4

---

Learning With Multi-Group Guarantees For Clusterable Subpopulations
In our second approach, likelihood calibration error, (2r y)
group structure, and then provide guarantees for the esti- mated groups. We will focus minimizing discriminant calibration error for simplified problem setting, then high- light some challenges involved in extending the approach to (a) more general problem settings and (b) to minimizing likelihood calibration error.
is attributed any component g with likelihood [g 2; y)-
Definition 2.2 (Likelihood Calibration Error). Given a se-
quence of instance-outcooee pairs V1), (or, yr),
the likelihood calibration error of predicted probabilities y1. yi..... Dr with respect to the endogenous subgroups model f as specified by distributions I (u) (x]gg) and f())-
is defined as
Minimizing discriminant calibration error via cluster- then-predict. To instantiate huuster-then-predic for dis- criminant calibration error, we leverage two common types of algorithms. For the first phase, we use a clustering algo- rithm that, given Gaussian mixture model, outputs a map- ping F : X - {1.2] indicating the group memberships. In particular, we use the algorithm of Azizyan et al. (2013) to obtain F for which F(z) = arg e f(j x) for all but an & fraction of the underlying distribution, after having made O(1/=²) observations. For the second phase, we can instantiate one (online) calibration algorithm that provides marginal calibration guarantees for its predictions on each of the two clusters. For example, Foster & Vohra (1998) guarantees at most T calibration error.'
LCE,(DirT FLT, (i:T) =
Σ [gg I Fe vc)
[oe E E. (0r ve)
max max gE[k] VEVA
When predictors P PT are used for making predic- tions 9. = (zt), we denote the corresponding likelihood calibration error by LCE, (PL,T, (1: (1:1,91:1)
2.2. Additional notation
Finally, we provide definitions for the following tools we will use in our analysis.
Pseudodimension is a generalization of the Vapnik- Chervonenkis (VC) dimension for real-valued functions.
Algorithm 1: Cluster-hhen-Predice Algorithm for Mini- mizing DCE
Definition 2.3 (Anthony & Bartlett (1999), Chapter 11), Let F:: x + R be a set of real-valued functions. Then, the pseudodimension of F, notated Pdim(FF) is the VC- dimension of the class (sgn(f(z) - y) : f F,y E R).
For the first T < T timesteps, make arbitrary predictions and collect observed features 31,..., TT Apply a clustering algorithm, such as the Azizyan et al. (2013) estimator, the observed features to partition the domain into cluster assignments F X + {1,
Exponential families are a class of statistical models where densities have common structure (see, e.g., Fithian (2023)). Examples include Poisson, Beta, and Gaussian distributions.
Then, instantiate two calibrated prediction algo- rithms (e.g.. the Foster & Vohra (1998) algorithm), one for each cluster. For every subsequent timestep T' + +1..... T, observe xa and predict Te by apply- ing a calibrated online forecasting algorithm to the transcript {(z,, v+) T < T t, F(z,) F(z,)} consisting only of datapoints with the same predicted cluster assignment.
Definition 2.4. A statistical model F= {ffe θ} is exponential family if it can be defined by family of den- sities of form fo(x)= = h(x) exp( (0, [x)) - A())), where 0 E θ is the parameter that uniquely specifies each density. The quantity Txx) is known as the sufficient statistic.
In partieular, note that multivariate Gaussian density with mean i and covariance E can be written
(x) = (2.)"/"|p117 exp( ( (x 11) T (x (p))
We formalize the guarantees of this approach in Prop. 3.1.
Σ Σー # exx [
- _ 20
veo(xx)) T) AA(,,)) E)
Proposition 3.1. Let f be an unknown endogenous sub- groups model whose Gaussian components are isotropic with || - Hell Z 7. Then, with probability 1 - 8, the Cluster-Then Then-Predict algorithm attains discriminant calibra- tion error of (/a/3/22/3--41 run with an appropriate choice of T" /3//3332//3 4/3).
with A(p, Σ) = +/44 TT-TIpp 11 + 1 log [Σ| + log((2), and dim(T(x)) = dim ((ve(((tT)) = d(d 1)/2.
/Toog(1 log(1/5)), when it is
3. A first attempt: Gaussian mixtures
Cluster-then-predic for
'The guarantecs of Foster & Vohra (1998) hold even when x: are adversarial; an even simpler algorithm would suffice for our i.i.d. case. For example, one could take the naive approach of using some additional timesteps estimate Ely g] to sufficient accuracy and use those estimated means for the remainder of time.
As a warmup, we consider the natural algorithmic approach: to first spend some timesteps to estimate the underlying
5

---

Learning With Multi-Group Guarantees For Clusterable Subpopulations
Sketch. This T2/3 rate is typical for two-stage online algorithms, such seplore-then-comeee
In the first phase, we must learn a good likelihood func- tion for each cluster (i.e., [[g x)), rather than a cluster assignment function. This can be done by estimating the parameters of each component, then using those estimates to construct likelihood functions; to that end, we can apply existing parameter learning algorithms (e.g. Hardt & Price (2015)). A more significant challenge is that even if good estimator [(g x)) is known, the fact that group member- ship is real-valued means that we can no longer partition the space and independently calibrate predictions in each partition. Instead, our predictions must handle the fact that each Te belongs to multiple groups; this motivates the use of online calibration algorithms with multi-group guaran- tees, called multicalibration. For similar reasons, we apply multicalibration algorithms in our multi-objective approach, which we discuss in the following section.
and its proof is also similar. By Azizyan et al. (2013) (see Theorem B.I), learning cluster assignment F that has E error takes T" = (d/rve) samples. Note that, the DCF of this algo- rithm is at most T" + aTT + /TInn1////
where the second term accounts for the clustering mistakes and the third term accounts for the calibration eπror of the "predict" stage, Set- gives the desired bound. L
ting T (2313322/3
Remark 3.2. In addition to the upper bound, the result of Azizyan et al. (2013) also implies that, for this class of cluster-then-prediit algorithms, the O(72/3) rate is in fact minimax optimal: it is impossible to learn F to any higher accuracy with any fewer samples.
Remark 3.3. Another consequence of the cluster-then- predict approach is that any hardness in learning cluster membership is inherited. For example, the 7-separation dependence of Proposition 3.1 is unavoidable in the task of learning cluster assignments, and by extension any instanti- ation of the cluster-then- thwe-tteeeeeeeeee then-ct approach.
4. Improved bounds: A multi-objective approach
The cluster-then-prede predict approach studied in Section 3 ne- cessitates learning the exact cluster structure underlying the data distribution that is, learning the binary functions I + arg max, f(g I x)) or the conditional likelihoods Jl | x) to high accuracy. As an alternative to resolv- ing the structure explicitly, we consider a multi-objective approach where we aim to simultaneously provide subgroup guarantees for a representative uncertainty set (specifically, covering) of all possible subpopulation structures.
Beyond 2-component isotropic mixtures. For discrim- inant calibration error, extending these results beyond 2 components to general k-component mixtures complicates the analysis in two ways. First, the ground truth cluster as- signment functions x + arg [aX] [i æz) are no longer halfspaces but rather Voronoi diagrams for l: > 2. Second, the minimax optimal accuracy rate for estimating the cluster assignment function of a k-component isotropic Gaussian mixture model is not known exactly, aside from being poly- nomial (Belkin & Sinha, 2015). Extending these results to mixtures of non-isotropic Gaussians or non-uniform mixtures is also non-trivial, even for k- 2; minimax opti- mal rates are similarly unknown for these generalizations. One challenge for proving such a result is that the cluster assignment functions are no longer halfspaces, but rather non-linear boundaries, as illustrated in Figure I.
Building a covering of possible underlying cluster structures is significantly easier in statistical sense than learning the true structure directly, which offers three benefits. First, rather than paying the T2/3 error rate typical of cluster-then- predict methods, the multi-objective approach provides an optimal 1 error rate. Second, the multi-objective learn- ing approach can obtain faster convergence rate than is possible when learning the underlying clusters. For ex- ample, rather than paying the inevitable mean separation dependence involved in learning discriminant likelihood functions, the mujti-objecctve approach provides error rates independent of separation. Third, while both the cluster- then then-predict and multi-objective approaches can generalize beyond Gaussian mixture models, the latter does so without requiring distribution- specific clustering algorithms, which would have been necessary for the former; instead, the multi- objective approach only needs to consider the combinatorial structure of the likelihood functions. We provide tools for analyzing this structure in general (Lemma 4.6), and for exponential families in particular (Lemma 4.7).
Extension to likelihood calibration error. Applying the mustee--henn-preee approach to minimize likelihood cali- bration error again provides a T2/3 rate.
Proposition 3.4. Let f be an unknown endogenous sub- groups model whose Gaussian components are isotropic, and where μ1 and #2 are separated by a constant in ev- ery dimension. Then, with probability 1-6 6, a Cluster- Then-Predict Algorithm for Minimizing LCE, setting T' -O(T2/3), incurs likelihood culibration error of δ /dlog///())
In Section 4.1, we introduce multicalibration as a technical tool for our problem setting; in Section 4.2, we give an algorithm that provides guarantees for discriminant calibra- tion error and likelihood calibration error by constructing a
We defer the proof of Proposition 3.4, and the statement of the corresponding algorithm, to Appendix B.
Implementing this approach requires some additional care.
6

---

Learning With Multi-Group Guarantees For Clusterable Subpopulations
Non iscoropic unitem
Non loccoooccicccc &ooo-unnoon
Figure 1: Illustration of the non-lineat boundaries that arise in the cluster assignment functions of non-isotropic Gaussian mixtures for & = 2. Means of each component are marked with red stars.
cover of plausible subpopulation structures. In Section 4.3, we show that, for the endogenous subgroups model, the key quantity to bound is the pseudodimension of likelihood ratios of the densities in F, and that for exponential families, it in fact suffices to bound the dimension of the sufficient statistic. Finally, in Section 4.4, we provide concrete bounds on discriminant calibration error and likelihood calibration error in mixtures of exponential familics. These results are summarized in Theorem 4.1.
When predictors Pi.....Pr are used for making predictions Tt = pt (x+), we denote the corresponding multicalibration error by MCE(pI.T, $1..:,, U1:T;
To show how multicalibration be useful, note that can upper bound likelihood calibration error and discrimi- nant calibration error in terms of multicalibration error for carefully-designed classes of distinguishers.
Fact 4.3. Let JF be the class of densities considered in an instantiation of the endogenous subgroups model. Take f E F to be one such density and let H := P1:T, 21-7; Vi:r be any transcript of predictors, instances, and labels. Then, DCE,(H), S MCE(H; H; 9) defined for any set of distin- guishers & where g 2 fa + 1[g arg max, f(j x)]] g [k:]]. One such choice of G is
Theorem 4.1. Consider endogenous subgroups model with & exponential family mixture components and suffi- cient statistic dimension of di)(T(z)) = d. With proba- bility 1 - 5, Algorithm 2, run with G as defined in Eq. I, attains discriminant calibration error of
O(T((dk lT) log(k) + (X/8)))
= ( 1lg arg max fli x)] g E [K] f FJ.
If Algorithm 2 is instead run with G as in Eq. with probability 1 - 5, it attains likelihood calibration error of
(1)
O Tidk: (Tg(T) log2 (dk) log(A/8)))
Similarly, we have ,CE,(H) MCE(H; for any set of distinguishers g where 2 {x f(g x)) g E [k]]. One such choice of G is
4.1. Multicalibration as a tool for bounding discriminant and likelihood calibration error
g = (z + flg x)
l (M)
(2)
Multicalibration is refinement of calibration that requires unbiasedness of predictions not only on distinguishers re- solving the level sets of one's predictors, i.c. [1(p((xr) E vll, but also on distinguishers that identify parts of the domain. We use an adaptation of the original multicalibra- tion definition for real-valued distinguishers of the domain.
4.2. Multicalibration algorithms for distinguisher classes of finite pseudodimension
In this section, we use multicalibration algorithms to si- multancously provide per-subgroup guarantees for multiple hypothetical clustering schemes, multi-objective approach that does not require resolving the underlying clustering.
Definition 4.2 (Multicalibration Error). Given sequence of instance-outcome pairs Vi),.., (Er, yr) and class of distinguishers 9 c [0, 1]x the multicalibration error of predicted probabilitics 01 .i..... .. Ør with respect to
For any (potentially infinite) set of real-valued distinguish- ers with finite pseudodimension, the following algorithm achieves O(VT) multicalibration error (Theorem 4.4): effi- ciently cover the space of distinguishers and run a standard online multicalibration algorithm on the cover. In Appendix C, we give explicit example algorithms for each stage-the the covering stage (Algorithm 3) and the calibration stage (Al- gorithm 4).
MCE( F1.T, (1:T:
Σ g(x)) 18 E u) (+e y1) KE|T
max max
gE9 VEVi

---

Learning With Multi-Group Guarantees For Clusterable Subpopulations
then bound its pseudodimension. In this section, we show that for endogenous subgroups model instantiated with density class F, a bound on the pseudodimension of the set of possible likelihood ratios,
Algorithm 2: Online Multicalibration Algorit for Coverable Distinguishers
For the first T ((diii(( log + log((/0)) timesteps, make arbitrary predictions and collect observed features Il,....;TT and compute a small T -overinng G' of the set G on "1,..,, e.g. using Algorithm 3.
5(1 501 10 f0 1 101
H =
(3)
is the key ingredient for bounding (g) for both dis- criminant calibration error (i.e., with g as defined (I)) and likelihood calibration error (i.e., with G as defined in (2)). We formalize this in Lemma 4.6.
For the remaining timesteps 1 = T" + I,...,T. T, observe It and predict yt by applying any on- line multicalibration algorithm, e.g. Algorithm 4, to the transcript of previously seen datapoints ((+,, < /) and distinguishers
Lemma 4.6. Let D = (c) where H is defined as in (3). Then, the binary-valued distinguisher class {xr + 1g = arg g f(g' =)] g E [k]. E F} has pseudodimension (equivalently VC dimension) of at most (og(log())) and the real-valued distinguisher class {a + f(g x) g [.), E FF has pseudodimensioo at most Okk log" (kD)).
Theorem 4.4 bounds the error incurred by Algorithm 2.
Theorem 444. For any real-valued function class with finite pseudodimension Pd)m(g), with probability 1 8, the predictions PiT made by Algorithm 2 satisfy MCE(PI.T. Zu.T (u:T:))
Note that Lemma 4.6 holds for any class of densities F. In the following section, we show how to bound Pdim(H) for exponential families and Gaussian mixture models.
δ (((ddim(G)) + log(\/01))
The proof of Theorem 4.4 requires two main ingredients. First, standard analysis of multicalibration algorithms (e.g. Haghtalab et al. (2023) Theorem 4.3-see Theorem C.I) suggests that a V rate possible when the algorithm is run with a finite set of distinguishers. To obtain such set, Algorithm 2 first spends T' steps to compute } -coverin of the (infinite) G. The second ingredient, therefore, is to show that such a finite covering G' of the (infinite) G can be computed using a small number of observations, so that the error incurred by this approximation in steps T" + ...... T...Tin is sufficiently small. To that end, we give the following lemma, finite
4.4. Conerete bounds for endogenous subgroups models with exponential families
We now prove Theorem 4.1, and discuss some of its implica- tions. As suggested in Section 4.3, a key step in the proofs of Theorem 4.1 is to bound the pseudodimension of H. When F is exponential family, we can bound the pseudodimen- sion of likelihood ratios, and by extension Pdim by bounding the dimension of its sufficient statistic T(x).
Lemma 4.7. When F is an exponential family (Desiittion 2.4), the pseudodimension of H (with H defined as in (3)) is bounded by the dimension of the sufficient statistic, i.e.
which states that an empirical cover computed number of samples is true E-cover with high probability.
Pdim(H) < ddim(((x)) +1
Lemma 4.5. Given e, 8, T > 0 and a veal-valued function class G with finite pseudodimension Pdim(G), consider any E-cover G' of G computed on T randomly sampled datapoints. Then G' is 4c-cover of G with probability at least 1 - (())im((())(())))))))))))) ((P)imm))))) exp(-Te))
Proof of Theorem 4.1. Lemma 4.7 upper bounds the pseu- dodimension of 7 (3) for exponential families, and thus also provides bound on the pscudodimension of distinguisher classes G and G' in Lemma 4.6. Theorem 4.1 then follows by Theorem 4.4's upper bound on multicalibration error, and therefore discriminant calibration error and likelihood calibration error (Fact 4.3).
We prove Theorem 4.4 and Lemma 4.5 in Appendices C.2 and C.3, respectively.
4.3. Bounding the pseudodimension of DCE and LCE distinguishers
As a consequence of Theorem 4.1, we can explicitly bound discriminant calibration error and likelihood calibration er- ror when the underlying mixture components are Gaussian, in light of the following observation about the dimension of the sufficient statistic for Gaussian densities.
We now turn to instantiating our multi-objective approach for minimizing both discriminant calibration error and like- lihood calibration error. Fact 4.3 and Theorem 4.4 suggest that it suffices to construct a class of distinguishers & that includes the relevant likelihood or discriminant functions,
Fact 4.8. For Gaussian densities, dim(T(x)) < d(d-1) + d.
In the isotropic case, dim(T(x:)) S 2d. 2
8

---

Learning With Multi-Group Guarantees For Clusterable Subpopulations
Fact 4.8 and Theorem 4.1 immediately imply the follow- ing bounds on discriminant calibration error and likelihood calibration error for Gaussian mixtures.
5. Discussion
This work has focused on a particular instantiation of our model-for (online) calibration as the objective, and mix- tures of exponential families as the subgroup structure un- derlying our endogenous subgroups model. However, as discussed in Section 2, the results presented in this paper for calibration extend to other problems that can be formalized in the language of Blackwell approachability, such as online conformal prediction. Another extension is to handle other subgroup structures beyond exponential families. While Lemma 4.7 is specific to exponential families, Lemma 4.6 is more general; in principle, we expect that similar technical analysis can be performed for other unsupervised learning models of bounded combinatorial complexity. In fact, our approaches- notions of discriminant calibration error and likelihood calibration error- can apply to any setting where group membership can at best be estimated.
Corollary 4.9. Consider an endogenous subgroups model with l Gaussian mixture components. With probability 1 8, Algorithm 2, run with 9 as de-
fined in Eq. I. attains discriminant calibration +og assumptions,
error of O(VT(dPklog) or,
under
isotropic
TTTk (og(T))og( + log(A/))))
On the other hand, when run with 9 as defined Eq. 2. Algorithm 2 instead attains likelihood calibration
error of T(TT(Pkklog [dg((d))++ or,
assumptions, O( T(dk (og(T) log (dk) + log(\/6)))
under isotropic
More generally, our formalization of an unsupervised notion of multi-group guarantees provides language for under- standing important downstream application of cluster- ing. Our results demonstrate that being intentional about how learned clusters will be used, rather than treating clustering and learning as distinct stages, is significant both conceptually and for attaining optimal theoretical rates. First, resolving the exact clustering structure of one's ' data is inefficient, and results in the same theoretical sub- optimality as explore-then-commii algorithms in bandit and RL literature- tieretuue-nammlly ((32/3) rather than O(T rates. Second, the task of learning with guarantees for subgroups can be surprisingly easier than learning the subgroups them- selves. The most striking example of this appears in our results for discriminant calibration error, for which we show that learning cluster assignment functions has inevitable dependence on cluster separation, whereas separation can be ignored when pursuing per-cluster guarantees. Moreover, as our improved rates for the multi-objective approach suggest, it is not just that learning subgroups may be harder: it is also not necessary to learn the subgroups exactly the ultimate goal is to provide guarantees across them.
A gap between learning subgroups and providing per- subgroup guarantees. In contrast the Cluster-then- Predict guarantees of Section 3 (Propositions 3,1 and 3.4), Corollary 4.9 achieves an improved error rate of Ö(VT) ver- sus (TT23)), while also avoiding separation dependence- for both discriminant calibration error and likelihood cali- bration error.
For discriminant calibration error, Corollary 4.9 is especially notable because learning the subgroup discriminator func- tion requires sample complexity that scales with component mean separation.
Theorem 4.10 (Azizyan et al. (2013), Theorem 2). Let ff be an unknown endogenous subgroups model with two isotropic Gaussian components with d 2 9. The sample complexity of learning the cluster assignment function is 0
Notably, this lower bound holds even for the case of having two equal-weight isotropic Gaussians. This sample com- plexity is paid for, for example, in the first stage of the Cluster-then-Prediic approach.
A Acknowledgments
Similarly, the likelihood calibration error rate in Corollary 4.9 is also significantly better than the best known rates for learning multivariate Gaussian likelihood functions: Hardt & Price (2015) prove an E 12 lower bound for learning parameters in a mixture of two Gaussians, which would suggest a corresponding 122113 rate; a T rate would have only been achievable under the separation assumption of Proposition 3.4.
This work was supported in part by the National Science Foundation under grant CCF-2145899 by the Office of Naval Research under grant N00014-24-1-2155 a C3.AI Digital Transformation Institute grant, and Alfred P. Sloan fellowship, and a Schmidt Science AI2050 fellowship. This material is based upon work supported by the National Sci- ence Foundation Graduate Research Fellowship Program under Grant No. DGE 2146752 (EZ and JD). Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.
That Corollary 4.9 obtains a better bound highlights the surprising fact that providing clusterable group guarantees can be easier than clustering, lending further motivation to -ojti-obeective approaches over cluster-then thent-reeiice

---

Learning With Multi-Group Guarantees For Clusterable Subpopulations
Impact Statement
Chen, J., Kallus, N., Mao, X., Svacha, G., and Udell, M. Fairesss under unawareness: Assessing disparity when protected class is unobserved. In Proceedings of the conference on fairness, accountability, and transparency, pp. 339-348, 2019.
This work seeks to provide a new perspective on how sub- populations should be understood. We do not feel that the potential societal impacts of this work merit additional com- mentary beyond what is already discussed in the paper and appendices.
Dawid, A. P. The well-calibrated Bayesian. Journal of the American Statistical Association, 77(379):605-610, 1982.
References
Anthony, M. and Bartlett, P. L. Neural Network Learning: Theoretical Foundations. Cambridge University Press, 1999.
Devroye, L., Györfi, L., and Lugosi, G. A probabilistic the- ory of pattern recognition, volume 31. Springer Science & Business Media, 2013.
Arbas, J., Ashtiani, H., and Liaw, C. Polynomial time and private learning of unbounded gaussian mixture models. In International Conference on Machine Learning, pp- 1018-1040. PMLR, 2023.
Dong, E., Schein, A., Wang, Y., and Garg, N. Addressing Discretization Induced Bias in Demographic Prediction, May 2024.
Attias, I. and Kontorovich, A. Fat-shattering dimension of k-fold aggregations. Journal of Machine Learning Research, 25(144):1-29, 2024.
Dwork, C., Kim, M. P., Reingold, O., Rothblum, G. N., and Yona, G. Outcome indistiguuishability In Proceedings of the Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 1095-1108. ACM, 2021.
Awasthi, P., Kleindessner, M., and Morgenstern, Equal- ized odds postprocessing under imperfect group informa- tion. In International conference artificial intelligence and statistics, pp. 1770-1780. PMLR, 2020.
Elder, E. M. and Hayes, M. Signaling race, ethnicity, and gender with names: Challenges and recommendations. The Journal of Politics, 85(2):764-770, 2023.
Awasthi, P., Beutel, A., Kleindessner, M., Morgenstern, J., and Wang, X. Evaluating fairness of machine learning models under uncertain and incomplete information. In Proceedings of the 2021 ACM conference on fairness, accountability, and transparency. pp. 206 214, 2021.
Elliott, M. N., Morrison, P. A., Fremont, A., McCaffrey, D. F., Pantoja, P., and Lurie, N. Using the census bureau's surname list to improve estimates of race/ethnicity and associated disparities. Health Services and Outcomes Research Methodology, 9:69-83, 2009.
Azizyan, M., Singh, A., and Wasserman, L. Minimax The- ory for sigh-dimensional Gaussian Mixtures with Sparse Mean Separation, June 2013.
Fithian, W. Stat 210a lecture notes, exponen- tial families, August 2023. URL https: / //stat210a 2al.kkeleey.dd/all-2222222 sandde//epppeeniaa--faimiiii
Belkin, M. and Sinha, K. Polynomial learning of distribution families. SIAM J. Comput., 44(4):889-911 2015. doi: 10.1137/11000811XX URL https: //t.:////.........//. 1137/13090818X,
Foster, D. and Kakade, M. Calibration via regression.
In Seroussi, G. and Viola, A. (eds.), Proceedings of 2006 IEEE Information Theory Workshop, pp. 82-86 86. IEEE, 2006.
Benthall, S. and Haynes, B. D. Racial categories in machine learning. In Proceedings of the conference fairness, accountability, and transparency, pp. 289-298, 2019.
Foster, D. P. and Vohra, R. V. Asymptotic cali- bration. Biometrika, 85(2):379-390) 1998. ISSN 00063444, 14643510. URL http:////// jwwor.torr. org/staabee/233335
Blackwell, D. An analog of the minimax theorem for vector payoffs. Pucific Journal of Mathematics, 6(1):1 - 8, 1956.
Blum, A., Haghtalab, N., Procaccia, A. D., and Qiao, M. Collaborative PAC learning. Advances in Neural Infor- mation Processing Systems, 30, 2017.
Gopalan, P., Kalai, A. T., Reingold, O., Sharan, V., and Wieder, U. Omnipredictors. In Braverman, M. (ed.), Proceedings of the ACM Conference on Innovations in Theoretical Computer Science Conference (ITCS), pp. 79:1-79:21, 2022.
Blumer, A., Ehrenfeucht, A., Haussler, D., and Warmuth, M. K. Learnability and the vapmik-chervonenkis dimen-
sion. J. ACM, 36(4):929-966 965, October 1989. ISSN 0004-5411. doi: 10.11457773999.66377 URL https: //doi. h/doii.or/1..1111111
Gupta, V., Jung, C., Noarov, G., Pai, M. M., and Roth, Online multivalid learning: Means, moments, and
10

---

Learning With Multi-Group Guarantees For Clusterable Subpopulations
prediction intervals. In Braverman, M. (ed.), Proceed- ings of the ACM Conference Innovations in Theo- retical Computer Science Conference (ITCS), pp. 82:1- 82:24. Schloss Dagstuhl Leibniz-Zentrum für Infor- matik, 2022.
Kallus, N., Mao, X., and Zhou, A. Assessing algorithmic faimess with unobserved protected class using data com- bination. Management Science, 68(3):1959-1981, 2022.
Kang. K., DeCelles, K. A., Tilesik, A., and Jun, S. Whitened résumés: Race and self-presentation in the labor market. Administrative science quarterly, 61)):
Haghtalab. N.. Jordan, M., and Zhao, E. On-demand sam- pling: Learning optimally from multiple distributions. Advances in Neural Information Processing Systems, 35: 009-419,220 2022.
469-502, 2016.
Lahoti, P., Beutel, A., Chen, J., Lee, K., Prost, F,, Thain, N., Wang, X., and Chi, E. Fairness without demograph- ies through adversarially reweighted learning. Advances in neural information processing systems, 33:728-740, 2020.
Haghtalab, N., Jordan, M., and Zhao, E. A unifying per- Game dynamics for multi- objective learning. Advances in Neural Information Pro- cessing Systems, 36, 2023.
spective on
Lee, D., Noarov, G., Pai, M. M., and Roth, A. Online min- imax multiobjective optimization: Multicalibeating and other applications. In Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems, 2022.
Hardt, M. and Price, E. Tight bounds for learning mixture of two gaussians. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pp- 753-760, 2015.
Hart, S. Calibrated forecasts: The minimax proof, 2022.
Liu, D., Do, V., Usunier, N., and Nickel, M. Group fair- ness without demographies using social networks. In Proceedings of the 2023 ACM Conference Fairness, Accountability, and Transparency, pp. 1432-1449, 2023,
Hashimoto, T., Srivastava, M., Namkoong, H., and Liang, P. Fairness without demographics in repeated loss minimiza- tion. In International Conference on Machine Learning, pp. 1929-1938. PMLR, 2018.
Ovalle, A., Subramonian, A., Gautam, V., Gee, G., and Chang, K.-W. Factoring the matrix of domination: A critical review and reimagination of intersectionality in Al fairness. In Proceedings of the 2023 AAAI/ACM Con- ference on AI, Ethics, and Society, pp. 496-511, 2023.
Haussler, D. and Welzl, E. Epsilon-new nets and simplex range queries. In Proceedings of the second annual symposium on Computational geometry, pp. 61-71, 1986.
Héhert-Johnson, Ú., Kim, M. P., Reingold, O., and Roth- blum, G. N. Calibration for the (Computationallyy Identifiable) Masses, March 2018
Wang. S., Guo, W., Narasimhan, H., Cotter, A., Gupta, M., and Jordan, M. Robust optimization for fairness with noisy protected groups. Advances in neural information processing systems, 0:l:1190-503,, 2020.
Hu, L. What is "race" in algorithmic discrimination on the basis of race? Journal of Moral Philosophy, 1(aop):1-26, 2023.
Wilson, K. and Caliskan, A. Gender, race, and intersectional bias in resume screening via language model retrieval. 2024.
Hu, L. and
I. What's Sex Got To Do With Fair Machine Learning? In Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency, pp. 513-513, January 2020. doi: 10.1 021144//35100533355677
arXiv preprint
Zhang, Y. Assessing fair lending risks using race/ethnicity
proxies. Management Science, 64(1):178-197, 2018.
Jung, C., Lee, C., Pai, M. M., Roth, A., and Vohra, R. Moment multicalibration for uncertainty estimation. Belkin, M. and Kpotufe, S. (eds.), Proceedings of the Conference on Learning Theory (COLT), Proceedings of Machine Learning Research, pp. 2634 2678. PMLR, 2021.
Jung, C., Noarov, G., Ramalingam, R., and Roth, A. Batch multivalid conformal prediction. In The Eleventh Inter- national Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023. URL http::://ppereviiiii net forum? dd= 700p8 jj

---

Learning With Multi-Group Guarantees For Clusterable Subpopulations
A. Facts, references, and restatements
Fact A.l (Anthony Bartlett (1999), Theorem 18.4). Let & be a real-valued function class. Then (e, m) 2 If a binary function, the bound holds for VC(g).
O (1)= Fact A.2 (Anthony & Bartlett (1999), Theorem 11.4). The pseudodimension of a k-dimensional vector space of real valued functions is k + 1.
Fact A.3 (Anthony & Bartlett (1999), Theorem 11.3). Let f be monotonic function and & be real-valued function class with pseudodimension d. Then the pseudodimension of {f g 9} is d. Fact A.4 (Attias & Kontorovich (2024), Theorem 1). Let
Gg be realevalued function classes each with a pseudodimen- sion of d. Then the pseudodimension of the classes {Σ fo fi II...., fk E G&} and {max, fa fi E .......fa f. g&
is OOd log" (kd))
Fact A.5 (Devroye et al. (2013), Theorem 21.5). The VC dimension of the class of k-cell Voronoi diagrams in Rd is upper bounded by k + (d + 1)62 log k. Fact A.6 (Blumer et al. (1989), Lemma 3.2.3). The intersection of k concept classes with VC dimension D has VC dimension at most (kg))..
B. Proofs for Section 3
B.1. Proposition 3.1
Let V,-- {PI.A4 P22 E X I|ll μ2l 2 2 denote the space of possible component means with at least y separation. Let Fn be the class of all mixture model estimators; formally, we define Fn the set of all functions mapping from n-length datasets (2')" to functions 21, Azizyan et al. (2013) provides an estimator for the Gaussian mixture model that achieves the minimax optimal error rate, with guarantee as follows.
Theorem B.1 (Minimax Gaussian clustering rates (Azizyan et al., 2013)). For n 2 max 4d), the minimax optimal accuracy for the estimator of two-component isotropic Gaussian mixture model with separation is
d
inf sup FEFw BEV, J..
Pr [F(I,,..,,,,) # arg max f(g= = i [10)] iE(1.2)
E
DNDD
72
where θ suppresses logarithmic factors, D Paiing denotes the uniform mixture of N N(1,, Ta) and N Ia), and D denotes n i..dd samples from D DuL-pr
We instantiate the cluster-then theeper-teenprrediett algorithm with the Gaussian mixture model estimator of (Azizyan et al., 2013) for the first phase. For the second phase, we use the multicalibration algorithm of Algorithm 4; we will instantiate Algorithm 4 with the trivial distinguisher set 91 = fa + 1} because we only need calibration with marginal guarantees within each bucket. By Theorem B.I, the expected clustering error attained by the (Azizyan et al.,
Proof of Proposition 3.1.
2013) estimator learned with T' samples is ( / ()). Let the resulting cluster assignment function be denoted F. Using Hoeffding's 's inequality, this implies that with probability at least 1 - 6,
T
T
Σ
1 [((x)) # arg max f(i Ze, mi)
< E
Σ 1
F(
# arg max fax 24, 20) jE[k]
+ VTT - T") log(1/))
je(k)
T
< 4
-T- log(1/))
(4)
With a slight abuse of notation, let us define the quantity DCEP (uT TT. (T&T) as the discriminant calibration error that would have been incurred had F : X > {1,2} been the true discriminant with respect to f. that is,
T
Σ1(== t=1
F(1)] [Mreu] (Te v1)
(Fr OCEE(Gre Pr. V = max max
g BEVA
"Note that the in the usual definition of DCE, the only information needed about the endogenous subgroups model f is the corresponding discriminant function arg max, f(j/,, y), and f(j jz, y) is independent of y given z.
12

---

Learning With Multi-Group Guarantees For Clusterable Subpopulations
By Theorem C.I, the calibration error timesteps / 7" where cluster is predicted, i.e. F(w,) is bounded with probability at least 1 - by O log(1/ where Ti = -- [F((),) = 1] is the number of timesteps where cluster predicted. With a similar bound holding cluster 2, by union bound, we have that
DCEF (yrer, r vrer) E O(V(T log((1))))
(5)
By triangle inequality and an additional union bound, combining (4) and (5) gives
(hr,, FIT V.r) & 5 ( + (T + V(T (T--T) -T) log log(1
Choosing T' T' = 0 1/3) gives the desired upper bound of
4/3 + /Tlog(1/0) (CE FIT. vir) S (dd1)33113,, 4/3
B.2, Proposition 3.4
In this section, we prove generalization of Proposition 3.4: Theorem B.2.
Algorithm for Minimizing LCE
For the first T <n T timesteps, make arbitrary predictions and collect observed features ..,.... TT. Apply a parameter- learning algorithm, such as the (Hardt Price, 2015) method, to the observed features to obtain estimates of the per-component likelihoods [sx g) for each g E [k]]
Then, instantiate Algorithm 4 with distinguishers G = = f- Mi x)) 11g [k]]. For each timestep / T' + 1,.... ........... T, observe ia and predict ye by applying Algorithm to the transcript of previously seen datapoints ((+,,++) T' < < <(.
While the algorithm is written for general k and f. we focus on the case where k: 2 and wi w2 1/2.
Theorem B.2. Let k and wi we 1/2. Define || - pell3. || loo + ||E2locc If we have that minje(d] ||1j |2.1 2 M()). then, with probability 5, the Cluster-Thenn-Prediett Algorithm for Minimizing LCE, setting T (TT/33), incurs
LCE,(PE:: Fr., Fir.brr) S ( (Tl0)/
On the other hand, without separation, we must set = O(T12/13) and incur
LCE,(PIT,P < 2 /alog
To prove Theorem B.2, we will need some facts relating parameter estimation to errors in estimating group membership are bounded by (E)). Fact B.3. When parameters (mi, Eg) of mixture component are e, d-lammed in the sense of (Hardt & Price, 2015), we have that with probability 8 8. TV (f(z | 9.) f(x 9i) < Olsvd).
Proof of Fact B.3. To see this, note that 8-learrnin in (Hardt & Price, 2015) is defined in terms of lo -norm on the estimated parameters relative to the variance of the mixture, i.e.
max max (11s- 7.113.. | Eilloo < (1lmz 12ll3 + + lll + [E2ll0)) (1,2)
13

---

Learning With Multi-Group Guarantees For Clusterable Subpopulations
Theorem 1.8 of (Arbas et al., 2023) shows that TV 2), 2) @(A) where A is parameter distance in E2; specifically,
A max [ 115-1/335-11 La LFlFF, | 1/2 (1)11))11)) m)1la)
Translating between the & and &o norms incurs a O(vd) penalty.
Fact B.4. Suppose that for each component gs. we have estimates of the density of z conditioned on membership in Jis i.e.
[ar 9t), such that TV (f(z (a: g.), f(r x:)) Then, mistakes in estimating group membership be bounded as E f | x)) 7 x)) < 3e, and the overall TV distance between the true mixture and the estimated mixture can be bounded as [V( E.
Proof of Fact B.4. By the definition of conditional probability, we have f x)
f(zgg)
for every Then, we can write f(x)
=[100 x) - -(s x)) / f(9x - - -(9s 20) f(x)dr
/ f(a, ((x.g.) f(o,
f(x)
-1) F(z, (e) dx
f(x)
/ [1( Mac dot (A)
do+ /
f(x)) -1 -1) Na,gi dr.
f(x)
(B)
Again by the definition of conditional probability, [(x = J(x I 9b) [(g,, and likewise for the estimated
quantity. Recall that the marginal likelihood of gs (i.e. its mixing weight) is f() 2. Then, (A) reduces to
2 TVV (f(x) g.), flz ) < e. For (B), noting that flg, x) s 1 for all x, we have
/ (1(e)
[(0) -1) -1) f(.,9)) dr dr= = ||(()) [(x)
[a, dr fxx)
((o)
= -/ |F(x) f(0)
flai x)
/ [(xx) F(x) dx.
Recalling that f(x)) Eierk) f( gi) f(:) and le 2, we can bound the final quantity in the above display by 2s.
A direct consequence of Fact B.4 is that the LCE incurred by sequence of predictors p1.... Pr samples (a, y) from the true distribution is close to the LCE that would have been incurred had each (x. y) been sampled from the estimated distribution.
Lemma B.S. Suppose that for each component gi, we have estimates of the density of x conditioned on membership in g iee. f(x gi), such that TV (f(z) f 9:) S Then, with probability 5, the LCE incurred by a fixed sequence of predictors Pi....,pP Pr on datapoints (x,y) can be bounded as
LCE < (l
5Te.
Proof. First, by definition, we have
LCE.,I........ ........ max max
Σ f(g xz) ((p((a))) E e) (p. yt) EE
gE VEVA
14

---

Learning With Multi-Group Guarantees For Clusterable Subpopulations
Note that at each timestep and for every g and v, the quantity fig xạ) [pp((z)) v] (p) y1) is random variable bounded in [0, 1]. Therefore, for any g and e, relate the realized to its expected sum; in particular, with probability 1 8,
S0 24) 1 l E c.] (Tx vt) [E[T]
Σ
LO(v)) +
E
Σ [E(T]
[i I mx) 1(p((z)) E c] (pe(xT)) ye)
(O(vT)in(1/0)) +
Σ [E[2]
flo I a) 1(p((x)) E 2] (p((x) - f2)))
<(VV)) in(10))
+ M|s x)) 1x)- -f |)| (p)( el wlf (x)
Σ / Aa (2) x)) [E
+
(p)())) c) (pi(1) - y) f(x)do
(6)
where Eq. 6 due to the triangle inequality. Now, we can express the first term in terms of the TV distance between the true and the estimated group-conditional densities. Combining Fact B.4 (for the first term of (6)) and the triangle inequality (for the second term of (6)), have
(6) S ( (n(1/))(((1)))))))))) 3T (E(T]
Σ
/ flg x) (pp((x) u) (p((x) v) f(x)dx
/ flog æ) (x) E (p((2)) yl [(x) - f(x) dx
+ Σ
1E[T]
$ (0(vT)ln(1/0)) + 5T +
Σ
/
flg x)) [pp(()) E v/ (p((x) - 4) (xx)dx
KE|2]
I(1T)) +5 + R
Σ [E(T]
f(g x) (pp.(x) e) (pe(x) -v)
s (O(V))in(100) 5TE + By
Σ FE(T]
- e e] (pe(x) -
where Eq. (7) again comes from combining Fact B.4 with the triangle inequality and Eq. (8) is due to Jensen's 'ss inequality.
The statement of the lemma follows by noting that, because this held for any g and v, it also holds for the max g and furthermore, by another application of Jensen's 's inequality,
max max B gElk] VeV,
Σ AE(T]
flg v1 1 E u] (it - ye)
SEy max max (E(R] DEVA
Σ
/ flg x2,31) 1 w] (Ø. vo)
rE|T]
LCE
We conclude this section with the proof of Theorem B.2.
15

---

Learning With Multi-Group Guarantees For Clusterable Subpopulations
Proof of Theorem B.2. The proof of Theorem B.2 proceeds in three steps. In Step 1, analyze the estimation phase and show that spending T" samples allows us to estimate f(-) with sufficiently small error. Step 2, we analyze the calibration phase and relate the error incurred when using (() to the true error. Step 3 completes the argument.
Step 1: Analyzing the estimation phase. the clustering phase of Cluster-Then Siche--redicttt Algorithm for Minimizing LCE, T" samples are used to learn [(x 9s) for i E (1,2). Let ón be the likelihood that parameters are successfully learned in this step.
Let a 1| - p2lla + |E + |2 we have that minje(d] |Mi, - Ma,j sufficiently separated in all dimensions, then set T" = [22/31 and the algorithm of (Hardt & Price, 2015) will e, -leaam the parameters (,, and (12, Σ2) with Oss log(d/0)) samples (where the Ô suppresses log log(1/e) term). Setting T2/3 = Ōō log_lo/(d//))) we have = (T- log (d/61))
2(o). i.e., that μ and #2 are
On the other hand, when μ1 and μ22 are not separated, we need 0(5-12 1(5-121og(d)) log(d/ō1)) samples learn parameters. We set T = 2 and instead have = 1/13 (dd6/1)(//61))
Finally, to analyze the error incurred this phase, note that since the predictor pe (xtt) = ] for each Tı,
Σ (E
f(gs 24) (pp(( E o] (pe(at) y1) S 1
for any i and U.
Step 2: Analyzing error incurred in the calibration phase when using f(.). In the calibration phase of Cluster-Then Predict Algorithm for Minimizing LCE, the predictor Pt is updated using the estimated densities f(-). Note that error in parameter learning translates to E evd error in TV distance between the estimated f(x gi) and the true f(z g.). by Fact 81),
B.3. Therefore, in the event that all parameters are learned within additive error of (which occurs with probability Lemma B.5 combined with Fact B.3 gives us that, with probability -2, the error incurred from T T is at most
[iee E u) (De - [1) S (LLCEE/(mmrrrrrrm...rr..). //0p:////hh/mmoo//-/-/7////////- -T). Σ [gl !=.I.....
Recall that we have defined G = x+ Mo x) g E [k]]: note that |9] k. Then, by definition, ([LCEE(PT: IT. UT:: E|MCEEPP:
IT' NT:::)
We will now extend Theorem C.1 to hold for expected multicalibration error, i.c E'MME((PT: IT :r: 9)}, rather than for specific realizations of Vt. In particular, integrating over 5 E (0,1), we have that "T. Clogg 122 (K188))TT-112 Therefore, TT .rr..yrrr))) O(T (k2//6)))) and when μr and μ2 are sufficiently separated.
& O(nyT Tog(()) for T - T" Z Cn log(k)). Solving for n gives y s
Σ M9g xx) 11 pppe( E v) (pr(x.) vz) <ō ( + log ==
Otherwise, without separation, we have
Σ flg. 21) (1)e v] (pr(s)) - ve) <ō ( + +log log"/2 1/2 (k22/)))
(TT12//3//100 1/2 (22 (d/61))
16

---

Learning With Multi-Group Guarantees For Clusterable Subpopulations
We now have that with probability d1. all parameters are learned within additive error (from step 1); and conditioning on that event, with probability 1 82 that the emoo incurred in the prediction phase be bounded as argued in Step 2. We can therefore write the total error incurred over all I' samples for any gi and when means are separated as, with probability (1 - -1)1 - 52) 2 1 - 61 62.
Step 3: Combining Steps and 2.
Σ flg xx)) 1 v] (pr()r)) ue) 5 AE(T]
Σ 1E(TY
Sas xx) (lpe(se) E o] (pe(xe) -ve)
Σ flg 2Z) 1[pc(x)) E u] (po(xe) me)
0 T2/3)
+ +0 (0
(3 (d/01))
and without separation as
Σ KE|T]
Mo: I x4) (xx( E o] (p.(xs) - ve) = =o + Saapis/aloo Valog (2
(TIznS
The statement of the theorem follows from noting that this holds for any and and therefore also holds for the maximum and v.
C. Supplemental Material for Section 4
C.I. Algorithms 3 and
Here, give example algorithms that can be used instantiate version of the Online Multicalibration Algorithm for Coverable Distinguishers.
Algorithm 3 computes empirical cover on samples Tı, "1,-.., Tr, inspired by the classical approach (for binary-valued functions) of Haussler & Welzl (1986).
Algorithm Algorithm for computing a cover
1: Input: function class G C [0, E (0, 1), samples Z1.7;
2: Initialize empty class g':
3: For every possible labeling y1.r e V?T, add to g' any g E G where g(xx) E yt for all f e [T]: gr
We also give Algorithm 4, the online multicalibration algorithm of Haghtalab et al. (2023).
Algorithm 4 Online multicalibration algorithm
1: Input: G c (0, 1|x, E (0, 1), X, T E Z4:
2: Initialize Hedge iterate ((1) Uniform [11} x G x VA);
3: for 1 to 7 do
[i. g(() 1ly E o| (7 w)]
min 4: Compute (x) x" (O./A.0 (II vE jr-p"(a) (a) Ee
max
5: Announce predictor p( to Nature and observe Nature's 's choice (zf(1) (
6: Update ((++1) ((lg)(((1:() where (i, = 1 - 1 E
(+tig((z)
1/y v] (ū ye)]
gupp((t)
7: end for
Algorithm 4 enjoys the following guarantee on multicalibration error.
Theorem C.1 (Haghtalab et al. (2023) Theorem 4.3), Fix 0, À E Z4, and distinguishers & c [0, 1 With probability
1 5, Algorithm guarantees MCE(pLr, 31.r, (urr: S ET for 2 O( In(1g)
17

---

Learning With Multi-Group Guarantees For Clusterable Subpopulations
C.2. Proof of Theorem 4.4
We prove Theorem 4.4, restated here.
Theorem 4.4. For any real-valued function class 9 with finite pseudodimennsion Pdimi(),, with probability 1 6, the predictions purr made by Algorithm satisfy MCE(p Fu.r, v1:r; 9) S (og(Pd/m())+
Proof of Theorem 4.4. We will begin by analyzing the multicalibration enror incurred timesteps T + 1... Т. Abusing I
notation, for any 9 E G, let g' == arg infzeg Trl EiErry (0xx) g(zx)). Such y always exists, because G' was computed using TIT Then, by the triangle inequality, have that for transcript
1 4T +1:T):
MCE(H:9)
sup max DEg VEVA tE[T"]]]
Σ
(g(o)) - o' (x))) [ E u 17 vel (CE(H;9)) (B)
(9)
(4)
For (B), G is of bounded pseudodimension and thus | multicalibration algorithm analysis (Haghtalab et al. (2023) Theorem 4.3; see Theorem C.I) thus gives that with probability 1 1 81, we have
Pdim(()) (O(Pdim(9)) (see Theorem A.1). Standard
(B) S (Pdim(())og( log(A//))(
To bound (A), we would like to apply Lemma 4.5. To do so, we will first apply Hoeffding's inequality on the random
variables (x(xz) o' (xx)). In particular, note that we can trivially bound 1 [ee E v] 1 yr1 s 1 for all t; therefore. (A) S supres Ererrery (9(x+) - g (xz)), and Hoeffding's inequality gives us that with probability 1 82.
1g(x)) of (aol s (T T') sup Elg(() o' (=)1) log////111) gE9 [E(T:T]
Σ
sup
gEg
Now, by Lemma 4.5, we have that with probability 82.
sup B[lg(x) g'(x)]l S + (Pdim())log(T)) + log(1/5.)) sEg
Therefore, with probability 1 1 82 83.
sup 9E9 TT
g'xx=))
4/T-T"
+ log(1/65)) log(T)
(T (og]lg(1//) log(1/82))
Combining this with (9) and choosing 81, 52, 63 O()), we have with probability 1-
MC yT::: o (P)im(9) log(T) + log(1/5)) ( ((Pddin(S))ogg) + log(l)// (og()))))
The claim then follows from noting that MC S T" and plugging the algorithm's choice of T" (TPPdim()) log(T) log(1/6)).
C.3. Proof of Lemma 4.5
We prove Lemma 4.5, restated here.
Lemma 4.5. Given e, S, >> 0 and a real-valued function functioonn class G with finite pseudodimension Pdim(g), consider any E-COver g' of 9 computed on randomly sampled datapoints. Then G' is 4g-cover of G with probability at least (1 (PPdmm(())))) exp(-Te))-
Lemma 4.5 follows from the following more general presentation stated for any real-valued function class whose covering number grows at a wuub-square-eece square-root-expomeee cot.-roooo---ttiialll rate in the number of datapoints. The result follows a similar approach to Haussler & Welzl (1986).
18

---

Learning With Multi-Group Guarantees For Clusterable Subpopulations
Lemma C.2. Given e, 6, O and real-valued function class & where (1 (T) S V (exp(T=2/32) consider any 8-cover g' of 9 computed on T random datapoints. Then G' is a 4g-cover of 9 with probability at least 1 O(N 9T)) exp(-Te))-
Given Lemma C.2,
prove Lemma 4.5 fairly directly.
Lemma 4.5. Given e, T O and real-valued function class 9 with finite pseudodimension Pdim(()) consider any E-cover G' of G computed on T randomly sampled datapoints. Then G' is 45-cover of 9 with probability at least 1 1- (-O(P)in())) (1/))0(Pdim(())
Proof. Given that G is of bounded pseudodimension, we have that the covering number is bounded by (i G, s O (Pdim ( (1/z) ( (Anthony & Bartlett (1999) Thm. 18.4; see Fact A.1). We also can observe that our upper bound on (e, 9, T) is independent of T. Thus, we can apply Lemma C.2 to note that G' a 45-cover of g with probability ((Pdin(S)) at least - O ((d (10))(((())((((((())) exp(-Te)).
To prove Lemma C.2, we first recall the following one-sided testing form of Bernstein's inequality. Fact C.3. Let XI,..., Xr be i.i.d. random variables supported on [0, 1] with mean E(X;), and let ğt 7 E X, be the sample mean. Then, for any & > O, we have:
Te (-8) 8
If p > 3e, then Pr(fi S 2s) S exp
Proof of Fact C.3. Applying Bernstein's 's inequality with deviation / = 11- - 2s 2 p/3 2 8 gives:
-Tt 2(μ + 5)
I
-HHE
Te
Pr(β < 2²) = Pr(u - f 2 t) S exp
S exp
2 (z)
= exp
4(2 - 5)
S exp
(-8
We next proceed to the main proof.
Proof of Lemma C.2. Existence of covering points.
First, note that for any and m, Ni (f(x) - g(x) 1 [.g E m), s N)) Then, recalling that bounded covering number implies uniform convergence,
T
Pr sup [[](())- - g(())l f.eE
< <4Ni(E/(16-8)) 9)) (ssp--Te/332 -((x)) ( e/8 -
t=1
Since (e/(e/(16 20,0,,) & 2
T
Pr
sup E [1f(2)) - 9(x)g| - 1 Σ (f( g(x4)) 2 E/8 S
f.ges
Thus, by the probabilistic method, there exists some sequence of datapoints 21, T1,..., ziy such that
T - Σ E
sup B[f(x) - -[()()))(()]1 f.e5
(f(()) g(+()) s $//8.
(10)
Covering failure events. Let 21, Iy denote i.i.d. samples from distribution D. By definition, there is a subset g' C g of size N1 G) such that for all f e G, there is a f E g' such th Σ (zx) - f((x)) < E. Note that this subset g' is not dependent on and can be computed from Fı,.. TT-
19

---

Learning With Multi-Group Guarantees For Clusterable Subpopulations We define, for any Sig g. the event Egg be the event that both [1] 9-))] 4s and I T 1)(x)) - g(x+)) c.
Condition on none of the events in {Frgg J.g g occurring. Fix any / g. Since we covered on ;1,...; 2T with tolerance of E, there is a E G' such that Ei= [f(x)) - ((x)) S E. Since Es.g did not occur, we know that E [1)(x) s())l v 4e. This implies that g' a 4e-net as desired.
thus suffices to upper bound Pr Pr[Unnes F5.
Bounding s ml by covering G. We now define, for any fig E G, the event Es to be the event that both [lf(z) g(=)ll 2 and + Ei= If(z)) g(x+)l S 2E.
ETLM. Therefore, & is cover of size N1 G, 2T). Let 9 be coveriig of G on the datapoints 2f....,, T'y, [I1,
This means for every f E 9 there a e 9 such that
T
T f(zt) - Flat)
f(x)) - Roil + +
Σ
27
We now proceed to show that Useeg Esa S Uügeeö Fi First, by the triangle inequality.
f(xx)) - -(xz)
1
Σ
lf(x)) - g(x1)1 + g(x:)) - Σ
f((x)) F(az))
t=1
t=1
T
$
+
[f(x)) - g(xxa) +e.
Therefore, Eh (zx)) - g(xx)1 S only if ( ΣT= |
f(xx) - Hoxi) 2
Next, by the definition of G. we have
T f(x() - f(a/))
T - -((x)) < s//4.
s se/4
and
T
Σ [=1
f(xz)
By the triangle inequality, for every f.g E G and their matching f.g E G. we have
+ -(()) - + Σ f(o!) {(xb)
S and + Σ (x -(xx))
Σ
i(x)) g(os)
5 5.
(1I)
20

---

Learning With Multi-Group Guarantees For Clusterable Subpopulations
Thus, repeatedly applying the triangle inequality (first, third, and fifth transitions below).
T 1f(xz)
- -
S T
(f(x)) - [1f(2)) -(x) Σ
-(x1))
< ff(x)) s(x1)) +
T + f(a') g(1i))
$
F(al)) o(ab)) + Σ -((0)))())))))
Σ
+
S Σ F(xt)) - 3(0/)) +
T
< E F(x) ((xx) || + E -
-
Σ
[(a)) - g(x())
+ +
Se+B E f(()) - [(x)
where the second and final transitions due to (10) and the fourth is due to (11).
Thus, for any f.g& E G, [1f(()) - 9(x)]] 2 4s only if the corresponding f.ğ E G satisfies
F(x)) - ](x) 2 3c.
follows that Pr (US E1 & Pr(UFae Ff.3)
Finally, for any fixed choice of f and we have by Fact C.3 that Pr [B,o] S Eex(-12s). pairs F, G. we have
Tt.. Thus, union bounding over all
Pr
U Esg S.9E
UF
s $
2
exp(- TT)) < SO(NI($,9,,7)) exp(-Te)
C.4. Proofs of pseudodimension bounds (Lemmas 4.6 and 4.7
We begin by proving Lemma 4.6, restated below.
Lemma 4.6. Let D Pdim (H) where H is defined as (3). Then, the binary-valued distinguisher class G {i + 1[g arg m F(g') [x] g E [ F} has pseudodimension (equivalently VC dimension) of at most (kk log(k)) and the real-valued distinguisher class g' = {ar + J(g x) g E [K], E FF has pseudodimension most O(k log 2 (k:)))
Proof. For the first claim, consider the class ğ that consists of comparisons of two groups' likelihoods, rather than an argmax over all l groups as in G:
G == 1[3(x 1 1 F(x g'il g.96 E [M)
We can verify that & C + 11((z) > 1 1 H}. Note that VC(f 1[((x) > 1] h H}} Pdim by defi- nition. Since the k-fold intersection VC class increases VC dimension by at most a factor of & log(k)) (Blumer et al. (1989), Lemma 3.2.3; see Fact A.6), we have VC(f# + [[))(x) > 1 h..)),(())] hy...., h2 E H}) < O(KD log())). Finally, we can verify that
hx(2)) g 5 (r (()( > 1 (1....haxx)) hy.... h E H}.
(12)
concluding our first claim.
21

---

Learning With Multi-Group Guarantees For Clusterable Subpopulations
For the second claim, fix g 1 without loss of generality. Note that for any F, write S(1 xr)
W1 f(x 1) f(1 2(112)= ΣjE( Wj f(x ())
1
ΣSENh
[(
Σ SE(K] f(1z)
(((l)
Thus, Pdlmm(")) Pdim
((x 2 Eic(())
f x Pdim (fx+ Ejen h(rr)
1 E H))
Heli T(1l)
The sum of bounded pseudodimension classes enjoy an almost linear bound in pseudodimension (Attias & Kontorovich (2024) Theorem I; see Fact A.4), Pdim [<==Ene Ejets by hi...., H)) S kD Ikg", Finally, + 1/2
monotonic, and therefore preserves pseudodimension (Fact A.3).
Finally, we prove Lemma 4.7.
Lemma 4.7. When F is exponential family (Definition 2.4), the pseudodimension of H (with H. defined as in (3)) is bounded by the dimension of the sufficient statistic, i.e. Pdim(H) & dim + 1.
Proof of Lemma 4.7. Because F is an exponential family, we can write
S(1 [1]x) x) W1 [fx 11) 11 9(0 (x( exp (0), T(x))) w..0((0) exp((0) ((x)))
8( x)) Wj (5 Wj 90, (x) (xp( (0,,T(x)) (y
Note that (0) -0- fj. (x)) is vector space of size dim (xx)): by Fact A.2, Pdim( fj. T(x))) I (im(T(x)) + 1. The claim follows from noting that exp(-) is monotonic and thus preserves pseudodimension (Fact A.3).
22


Reviews:
[{"review_id": "MPK8vMqJHJ", "reviewer": "Reviewer_DK2e", "summary": "This paper focuses on evaluating prediction performance on meaningful subpopulations rather than the overall population in a clustering problem. It proposes two levels of guarantees for capturing performance per subgroup: (1) evaluating the performance if assigning an individual to the most likely cluster, and (2) evaluating the performance if assigning each individual to all clusters weighted by their relative likelihood. The paper introduces a multi-objective algorithm to simultaneously handle both formalisms for all plausible underlying subpopulation structures, and evaluates the proposed algorithm in the context of online calibration as a case study.", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your review and questions! \n\n**Q1: On empirical results**\n\n> I don't see any empirical studies nor experiments to justify your theory and your algorithm in both main text and supplementary. Can you provide empirical results to justify the effectiveness of your method?\n\nWe emphasize that the main contributions of our work are theoretical in nature. This paper contributes to the multicalibration literature which is a well-established field of theoretical research (e.g. [1-3]). The literature we draw from (such as learning algorithms and guarantees for Gaussian mixture models) are similarly in well-established theoretical fields (e.g. [4-5]). Given that our paper’s primary subject area is also Theory, we believe that a fully theoretical treatment is an appropriate and meaningful way to advance understanding and make foundational contributions to these theoretically rich fields.\n\n**Q2: On misspecification.**\n\n> Given the potential for model misspecification, would this method still hold?\n\nWe believe that our multi-objective approach (Alg 2) is indeed useful for reducing the impact of misspecification of the generative model. This is because we never commit to learning a specific mixture distribution explicitly; instead, we are “robust” to any likelihood that could have been modeled by one's hypothesis class of clustering functions. Thus, even under misspecification, our method succeeds with provable guarantees as long as the “true” likelihood function is reasonably well-approximated by some function in a large empirical cover we construct.\n\nIt is also important to note that the consequences of model misspecification in multicalibration are significantly more benign than misspecification in many other empirical settings. Multicalibration seeks to refine the average prediction accuracy of a classifier to hold also on a per-subgroup level. If the subpopulations are misspecified, the model still outputs a well-calibrated highly accurate predictor, but with a potentially coarsened per-subpopulation guarantee.\n\n> Could you provide high-level comparison between the method proposed here versus the power posterior proposed in Miller et.al. from the methodology perspective?\n\nMiller et al. studies robustness to uncertainty around identifying the clustering parameters of one’s data. In contrast, our goal is to make predictions that are high-quality across clusters; we are not focused on learning model parameters or densities directly. In fact, one of our paper’s main messages is that—for the purpose of providing subgroup guarantees—it is not necessary to identify the clustering parameters of your data. This is why we are able to get learning rates that are independent of cluster separation. That is, the robustness that Miller et al. studies is robustness that we show can be enjoyed entirely for free.\n\nPerhaps the methodological similarity between our multi-objective algorithm (Algorithm 2) and the “coarsening” idea in Miller can be understood as, essentially, improved performance arising from simultaneously considering many true underlying “likelihoods” — in our case, all possible likelihood functions consistent with the original function class, and in Miller et.al.’s, all possibilities within a perturbed neighborhood of a particular radius. We think a valuable direction for future work is to study whether methods for robustly learning likelihoods (such as Miller’s) could be useful as an alternative to our covering approach. \n\n**Q3: Knowing the number of clusters k.**\n\n> The paper assumes the data is generated from a mixture of distributions with a fixed number of subpopulations k. However, k  is typically unknown in clustering problems, and different choices of k can significantly impact the structures and the number of subpopulations on which this paper relies.\n\nWhile setting k is generally a sensitive parameter choice for clustering algorithms, it is *not* a sensitive parameter for our algorithm. Our algorithm doesn’t hinge on the data being exactly described by k clusters: instead, it provides guarantees for all plausible ways of clustering the data into *up to* k clusters. Thus, it suffices to just set k to be a generous upper bound on the number of clusters that you might expect in your data. \n\nAll this said, we think that dealing with misspecification of the likelihood function class $\\mathcal{F}$ and/or of $k$ would also be worthy avenues for study. As discussed above, we believe our multi-objective approach has potential in terms of providing such robustness guarantees, though we leave explicit development of these arguments to future work. \n\n[1] Hebert-Johnson et.al., Multicalibration: Calibration for the (computationally-identifiable) masses\n\n[2] Dwork et.al., Outcome Indistinguishability\n\n[3] Gopalan et.al., Ominpredictors\n\n[4] Azizyan et.al., Minimax theory for high-dimensional gaussian mixtures with sparse mean separation \n\n[5] Hardt and Price, Tight bounds for learning a mixture of two gaussians.", "claims_and_evidence": "This paper provides extensive theoretical proofs on different scenarios. However, the method is not evaluated properly empirically.", "methods_and_evaluation_criteria": "There are no evaluations on either simulated datasets or benchmark datasets.", "theoretical_claims": "I did not review every detail of the proofs. Please refer more to the other reviewers' comments regarding the correctness of the theory.", "experimental_designs_or_analyses": "This paper didn't provide any empirical studies nor experiments on real data.", "relation_to_broader_scientific_literature": "n/a", "essential_references_not_discussed": "n/a", "other_strengths_and_weaknesses": "The paper is well-presented and the motivation is clearly presented. \n\nHowever, the assumptions can limit its applicability to common scenarios in practice. There's no empirical justification of the method with simulated data or real data.\n\nSee Questions Section for more discussion.", "other_comments_or_suggestions": "n/a", "questions_for_authors": "I have the following key concerns:\n\n(1) I don't see any empirical studies nor experiments to justify your theory and your algorithm in both main text and supplementary. Can you provide empirical results to justify the effectiveness of your method?\n\n(2) I wonder how much we can trust the underlying \"naturally emerging\" distributions. For example, in mixture models, we make assumptions about the structure of each subpopulation. However, these assumptions can often be incorrect, leading to problematic results [1]. Given the potential for model misspecification, would this method still hold? In comparison, the method proposed by [2] considers both subgroup clustering performance and model robustness when evaluating and making predictions. Could you provide some high-level comparison between the method proposed here versus the power posterior proposed in [2] from the methodology perspective?\n\n(3) The framework of this paper is based on assumptions that may be challenging to scale to real-world applications. For instance, the paper assumes the data is generated from a mixture of distributions with a fixed number of subpopulations $k$. However, $k$ is typically unknown in clustering problems, and different choices of $k$ can significantly impact the structures and the number of subpopulations on which this paper relies.\n\n[1] Cai et al (2020). Finite mixture models do not reliably learn the number of components. In Int. Conf. on Machine Learning, Online, 18–24 July 2021, pp. 1158–1169.\n\n[2] Miller, J. W., & Dunson, D. B. (2019). Robust Bayesian inference via coarsening. Journal of the American Statistical Association.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "n/a"}}, {"review_id": "snLgnlLSuw", "reviewer": "Reviewer_iw9y", "summary": "The paper considers a multi-group online learning problem with instances $(x_t, y_t)$ arriving in sequence. In contrast to prior work in online multi-group learning, the groups themselves are not known at each instance. Instead, the paper assumes that there is an endogenous unknown subgroup model, such as, e.g.,  a mixture of Gaussians. We can think of this model as first sampling a mixture component (based on a distribution components), then sampling an $x_t$ from this mixture, and then finally sampling a label from some unknown distribution $f(y_t | x_t)$. At each time step $t$, the learner should produce some action $a_t$.\n\nGiven a datapoint $x_t$, it is impossible to identify which “group” (or mixture component) generated it. Therefore, two types of errors are considered. The first, discriminant error, takes into account only the most likely group that $x_t$ belongs to. The second, likelihood error, weighs each group that $x_t$ could have been generated from by the likelihood that it was generated by that group (mixture component).\n\nThe main concern of the paper is to generate calibrated predictions which have bounded worst group discriminant and likelihood error. First, the authors utilize the common technique of discretizing the outputs of the model into “buckets” when considering calibration errors. Then, they introduce two calibration variants to the aforementioned errors: discriminant calibration error (DCE) and likelihood calibration error (LCE). DCE can be thought of as minimizing the discriminant error over the worst “group intersect calibration bucket” in the sequence $x_t, y_t$. That is, for each mixture component and each prediction bucket (for example all predictions in $[0, 0.2]$ or $[0.2, 0.4]$), sum up the error of all predictions / actions taken by the learner in the sequence which belong to that group and that bucket. “Belong” here is defined in the discriminant way. LCE is the identical concept, but “Belong” is instead a probabilistic notion, since one $x_t$ can contribute to the error of multiple groups (depending on the probability of that “group” / mixture component generating $x_t$).\n\nWith DCE and LCE in hand, the paper then proposes some algorithms to achieve bounded error. To start with, a standard “cluster-then-predict” algorithm is proposed for Gaussian mixtures. This algorithm first learns the underlying groups (mixture components), then learns calibrated predictors for each group independently (a la Foster and Vohra.). The paper shows that this family of algorithms can achieve a $O(T^{⅔})$ error rate on DCE and LCE, and indeed, that this is tight due to the difficulty in determining underlying mixtures. In addition, the bound has a necessary dependence on a separation parameter $\\gamma$ for the underlying mixtures.\n\nThe paper then considers a new family of algorithms which _do not_ actually learn the underlying groups. In particular, if one can provide multicalibrated predictions for a suitable cover of all possible groups, this should be sufficient to obtain good worst-group performance guarantees. The main result of the paper, Theorem 4.1, shows that such an approach is feasible and enjoys the better DCE/LCE error rate of $O(\\sqrt{T})$ over the cluster-then-predict family of algorithms. Furthermore, no “separation” parameter dependence on $\\gamma$ is necessary. This new family of algorithms works by efficiently multicalibrating over a finite cover of the likelihood ratios of the underlying density class.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your review and suggestions! We will incorporate your presentation recommendations in the next versions. \n\n**Q1: Covering of H**\n\n> To obtain theorem 4.4, we need to run algorithm 2 with G=H, correct?\n\nFor Theorem 4.4, we run Algorithm 2 with $\\mathcal{G}$ defined according to eq. 1 (for DCE) or eq. 2 (for LCE) — essentially, $\\mathcal{G}$ corresponds to whatever the proper notion of “group membership” should be (for either DCE/LCE). Thus, the cover computed in the first phase of Algorithm 2 is a cover on the function classes corresponding to the group membership functions, but it turns out that the size of those covers only needs to depend on the pseudodimension of the class of likelihood ratios.\n\n**Q2: DCE vs LCE**\n\n> Is there a natural, intuitive interpretation of DCE / LCE and the difference between the two? \n\nThe difference between DCE and LCE as (per-subgroup) performance measures is critical when subgroups are overlapping.\n\nAs one example, first consider two well-separated standard Gaussians supported on a number line; for example, suppose their centers are at x=-1000 and x=1000 respectively. For any given candidate predictor, LCE and DCE will be nearly identical since $f(g_1 \\mid x) \\approx 1[ f(g_1 \\mid x) > f(g_2 \\mid x)$. In particular, both LCE and DCE can be understood as enforcing that a predictor is calibrated on the part of the data distribution where x<0 and calibrated on the part where x>0.\n\nNow suppose we reduced the separation between the two Gaussians so that their centers are x=-0.01 and x=0.01 respectively. LCE and DCE will now differ significantly. LCE measures calibration error on two groups whose likelihood ratio is ~50/50 across the entire domain, which means the LCE of any predictor is just an approximation of the predictor’s overall calibration error. In contrast, DCE measures calibration error on disjoint two groups: x<0 and x>0. That is, DCE still measures the same quantity as before, enforcing that a predictor is both calibrated on x<0 and calibrated on x>0. It’s less clear whether DCE’s treatment of x>0 and x<0 as disjoint groups makes sense in this case where the clusters are nearly indistinguishable. \n\n**Q3: Computational Efficiency**\n\n> Is the proposed algorithm 2 computationally tractable?\n\nMulticalibration algorithms including Algorithm 2 are generally not computationally efficient. However, there’s been recent progress towards oracle-efficient algorithms for multicalibration, which our results would directly benefit from (e.g., [1]). It’s also worth noting that in practice multicalibration can be approximately implemented as efficient boosting algorithms (e.g. [2]); we see these potential extensions as exciting directions for future work.\n\n**On Gopalan et.al. 2021:**\n\nThank you for the pointer. We will add an extended form of the following discussion to our revision: While Gopalan et al. 2021 also studies likelihood ratios, we take very different perspectives on how multicalibration relates to the likelihood ratio. In Gopalan et.al., the goal is to approximate the likelihood ratio as accurately as possible; their perspective is that multicalibration can be useful as a tool to relax pointwise to setwise accuracy. In our setting, our goal is not to approximate the likelihood ratios, but rather to make predictions that are multicalibrated with respect to the class of all plausible likelihoods consistent with our generative model. \n\n[1] Garg et.al. Oracle Efficient Online Multicalibration and Omniprediction\n\n[2] Globus-Harris et.al. Multicalibration as Boosting for Regression", "claims_and_evidence": "Yes, all proofs are present.", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "I did not check the correctness of any proof. Nonetheless, the main technical insight seems to be a combination of the following two facts 1) we should apply online multicalibration algorithms with the “right” groups (here, using $\\mathcal{H}$, the likelihood ratios of the underlying density function class); and 2) An approximate covering can be computed efficiently in the first phase of the algorithm.\n\nBoth facts seem reasonable as someone who has not checked the proofs carefully. Fact 2) is especially interesting, since one can apparently learn a good covering with less data than one can actually identify the underlying groups (see, for example, the similarity between phase 1 of algorithm 1 (cluster-then-predict) and algorithm 2 (online multicalibration approach)).", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "This paper relates to a line of work on online multicalibration. Importantly, the paper does not assume that group membership is known (or even that it is deterministic). To the best of my knowledge, this sets it apart from previous work in the area (although I do not work in online multicalibration, and may not be totally up to date with the literature).", "essential_references_not_discussed": "Given the technique of multicalibrating w.r.t. likelihood ratios of the underlying function class, it may be useful to discuss [1], which study the problem of (offline) learning multicalibrated partitions via a likelihood ratio / importance weight approach. I am not an expert in this area, but at a surface level the technique seems to be similar. However, in the submitted paper, concrete bounds on the pseudo-dimension of the derived likelihood ratio are discussed and utilized, whereas this doesn’t seem to be discussed in [1].\n\n[1]: Multicalibrated Partitions for Importance Weights. Gopalan et al. 2021.", "other_strengths_and_weaknesses": "I think this is a technically strong paper on an interesting (and to my knowledge, previously unexplored) problem: online multicalibration with unknown groups. \n\nI would suggest increasing the amount of discussion and removing most proofs from the main paper. For example, the proof of lemma 4.5 is a fairly straightforward argument to bound the pseudodimension of a derived function class — this could be replaced with a more detailed proof sketch of Theorem 4.4..", "other_comments_or_suggestions": "I enjoyed the extended discussion in Appendix A. Defining subpopulations via statistical identifiability. I think this discussion represents an important dilemma in the multicalibration literature, namely that groups are known / deterministic. Algorithms like the proposed one which allow for partial / probabilistic and _unknown_ group membership may represent an important development in the literature. I would suggest this discussion be included in the main paper somehow (or at least an abridged version of it), perhaps possible with the increased final paper page count.", "questions_for_authors": "1. Since $\\mathcal{F}$ is the underlying density class with bounded pseudo-dimension, I understand that we can bound the pseudo dimension of $\\mathcal{H}$, the class of density ratios on $\\mathcal{F}$. To obtain theorem 4.4, we need to run algorithm 2 with $\\mathcal{G} = \\mathcal{H}$, correct? So when we are computing our approximate cover (a la appendix D.2), I should think of computing a cover on the likelihood ratios of the original function class?\n\n2. Is there a natural, intuitive interpretation of DCE / LCE and the difference between the two? Maybe a simple two cluster example may help distinguish what the different error rates may signify?\n\n3. Is the proposed algorithm 2 computationally tractable?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2PARxcLD87", "reviewer": "Reviewer_U4DR", "summary": "This paper focuses on providing *multigroup* guarantees (with a focus on multicalibration, though the techniques are more general) in a stochastic online prediction game in the novel setting where the groups of interest are not provided beforehand as functions of the feature values, but, rather, as unknown endogeneous subpopulations that emerge from the distribution of individuals. This provides an alternative view of recent \"multigroup\" guarantees that has an unsupervised flavor; instead of *predefining* a collection of groups (typically a collection of indicator functions on the input space), this paper seeks to argue that another perspective is where groups arise naturally from the true distribution generating the input individuals.\n\nThe authors provide two main algorithms/approaches for providing multi-group calibration guarantees for this model. The first \"warmup algorithm,\" denoted \"Cluster-then-Predict,\" provides suboptimal $O(T^{2/3})$ rates under rather restrictive assumptions. The algorithm is simple: (1) take some tuned number of timesteps to learn the underlying group clusters and then (2) run a marginal calibration algorithm for each group for the remaining timesteps. The second algorithm uses a multicalibration approach to provide a better $O(T^{1/2})$ rate under more general assumptions (that the clusters are drawn from exponential families). The key algorithmic idea here is to use multicalibration on a pre-defined collection of groups/distinguishers; specifically, the collection that is defined by the possible family of density ratios under consideration. Because this collection is not too large combinatorially, the main algorithm proceeds by (i) constructing a cover and then (ii) running a multicalibration algorithm over the cover.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your detailed review and suggestions! To briefly address your questions:  \n\n**Q1: Online-to-batch.**\n\n> This is not a huge weakness, but it might make the paper more complete to have a corresponding batch setup, with results for the batch case. I wonder if the authors have already considered this and ran into a snag with, say, a boilerplate online-to-batch conversion of their algorithm?\n\nYes, the boilerplate online-to-batch conversion works fine to extend our guarantees to the batch setting. Indeed in  the batch setting, even an algorithm that is similar in style to our cluster-then-predict is slightly less egregious. That is, because there would be no “explore-then-commit” penalty—all $T$ points could be reused to first learn the likelihoods $f(g | x)$ and then learn to make predictions $f (y | x)$ )—achieves near-optimal rate in T but still suffers from a dependence on the separation between clusters ($\\gamma$). Our multi-objective algorithm entirely avoids the dependence as well. We agree this is an interesting point worth making, especially since it already follows directly from our online result—we will add a discussion on this.\n\n**Q2: Group-dependent rates.**\n\n> The rates presented all depend on T indiscriminately for every group… Is it possible to obtain more fine-grained guarantees for each group for DCE corresponding to the number of rounds for which the group was active?\n\nThis is an interesting question! Group-dependent rates are indeed attainable through our reduction to multicalibration, where one can attain rates that scale with $\\sqrt{T \\Pr(x \\in g)}$ “for free” (see e.g. Theorem 3.1 [1], Theorem 5.7 in [2]). This is in a sense optimal; the right concentration rate for a group of probability mass P is $1/\\sqrt{T P}$. Group-dependent rates are not the focus of our paper, but we agree it will be nice to highlight that it comes for free with our reduction.\n\n[1] Noarav et.al. High-Dimensional Prediction for Sequential Decision Making\n\n[2] Haghtalab et.al. A Unifying Perspective on Multicalibration: Game Dynamics for Multi-Objective Learning", "claims_and_evidence": "Yes, I believe all the claims are supported with clear and convincing evidence. The main claims are the guarantees for the \"Cluster-then-Predict\" warmup algorithm, in **Proposition 3.1** and **Proposition 3.4**, and the guarantee for the cover + multicalibrate algorithm in **Theorem 4.1.** I have verified the proofs for all these claims, and the proofs are correct to my verification.\n\nAn additional, more normative claim of the paper is present in Appendix A, which provides an argument for the endogeneous subgroup model of the paper. I found this argument persuasive (and refreshing! I believe more papers in this space should grapple with the implications of their mathematical assumptions), particularly in that this model \"contextualizes\" individuals with others whom predictions are being made. The authors make an interesting distinction in this Appendix article on how their model differs from the model accepted in most multicalibration/multigroup learning literature -- rather than viewing subgroup membership as \"computationally-identifiable\" groups, this clustering viewpoint views subgroups as \"statistically identifiable.\"", "methods_and_evaluation_criteria": "Yes, the main methods and evaluation criteria were proofs that the authors' two main desiderata (denoted as Discriminant Calibration Error and Likelihood Calibration Error) indeed decay sublinearly in the stochastic online model for both their algorithms. The desiderata themselves are natural and are well-accepted notions of prediction quality in the multicalibration literature.\n\nIn particular, DCE measures the $\\ell_{\\infty}$ norm of the calibration error over all groups on all the rounds for which a particular group is the \"most likely.\" LCE measures the $\\ell_{\\infty}$ norm of the calibration error over all groups, but the rounds are weighted according to the generative model for the groups. These are the natural definitions of prediction quality that arise if one is concerned about the model the authors pose for their problem (the *endogeneous subgroups generative model*) and calibration as a measure of prediction quality.", "theoretical_claims": "I checked all the main claims for the algorithms' correctness (Prop 3.1, Prop 3.4, Theorem 4.1 and its corresponding lemmas). I carefully went through the proof sketches or proofs that were in the main body, and I read over the Appendix C and D arguments, though less carefully than when I checked claims in the main body. These theoretical claims all seem to check out.", "experimental_designs_or_analyses": "This is a theory paper, so no experiments to check.", "relation_to_broader_scientific_literature": "This work can be situated squarely in the literature on multicalibration initialized by [HKRR18], and, more broadly, the literature concerned with obtaining multigroup guarantees over computationally-identifiable subpopulations. The authors provide a different perspective, however, than the model where groups are computationally-identifiable collections of indicator functions (typically finite or in a VC class). Instead, they consider clusterable groups coming from a natural generative model. The main tool used in this work draws from an algorithm of [HJZ23] instantiated with an appropriate collection of groups/distinguishers. The work also touches on clustering and unsupervised learning; their first algorithm relies on black-box access to a clustering algorithm, specifically the algorithm for Gaussian clustering of [AAW13].\n\n[HKRR18] Hébert-Johnson, Ursula, et al. \"Multicalibration: Calibration for the (computationally-identifiable) masses.\" International Conference on Machine Learning. PMLR, 2018.\n[HJZ23] Nika Haghtalab, Michael Jordan, and Eric Zhao. \"A unifying perspective on multi-calibration: Game dynamics for multi-objective learning.\" Advances in Neural Information Processing Systems 36 (2023): 72464-72506.\n[AAW13] Azizyan, Martin, Aarti Singh, and Larry Wasserman. \"Minimax theory for high-dimensional gaussian mixtures with sparse mean separation.\" Advances in Neural Information Processing Systems 26 (2013).", "essential_references_not_discussed": "I believe that the authors have cited all relevant work. It doesn't seem to me that there are any references missing (though I am less familiar with the unsupervised learning/clustering literature).", "other_strengths_and_weaknesses": "**Strengths**\n- The work is *extremely* well-written and clear. I had no trouble following the arguments, the overall flow of the paper, and the claims and model are well-motivated. The paper was a pleasure to read.\n- This alternative view of subpopulations is an interesting and novel alternative to the typical view of group structure in this literature, and I believe that it is quite worth disseminating. In particular, the model is natural, and I believe that it should be further studied.\n- The algorithmic results are interesting -- I particularly liked the key idea of cleverly choosing the class of distinguishers for multicalibration to be the class of possible density ratios, which are combinatorially bounded. This highlights how far multicalibration algorithms can go with a well-defined class of distinguishers for the problem at hand.\n- Though \"fuzzier,\" I believe that this a key strength that should not be overlooked is the focus the authors give on the model and the normative assumptions underlying the model. Reading Appendix A was a pleasure, and it is rare to find authors giving the requisite thought to the assumptions underlying their model/problem of choice. I believe that this is particularly lacking (though very warranted) in subfields where the algorithms concern predictions with a human dimension, where this paper is clearly situated. \n\n**Weaknesses*\nThe following are more questions than glaring weaknesses. The following contributions might make the paper more complete, but I believe that their omission does not detract from the overall quality of the paper (they seem to me to be more \"next steps\" or ways to round out the story). \n\n- This is not a huge weakness, but it might make the paper more complete to have a corresponding batch setup, with results for the batch case. I wonder if the authors have already considered this and ran into a snag with, say, a boilerplate online-to-batch conversion of their algorithm? I imagine this is straightforward, though I might be missing something.\n- The rates presented all depend on $T$ indiscriminately for *every* group, which I understand is part of the definition of DCE and LCE (as both definitions take a max over the groups). However, is it possible to obtain more fine-grained guarantees for each group for DCE corresponding to the number of rounds for which the group was active? If $T_g := \\sum_{t = 1}^T \\mathbf{1}\\{ g = \\mathrm{argmax}_{j \\in [k]} f( j \\mid x_t, y_t) \\}$, is it possible to achieve a more fine-grained bound where DCE depends on $T_g$ for each group?", "other_comments_or_suggestions": "Here are some other minor suggestions that might improve the presentation of the paper:\n\n- Page 4: I would suggest introducing the Section in the paragraph before **Minimizing discriminant calibration error...** with a disclaimer and motivation that the section only deals with two groups that are Gaussian. I understand that it is a warmup, but it may slightly clarify the presentation to introduce the section as dealing with this special case first.\n- Page 5: A nitpick for Propositions 3.1 and 3.4 is to define $d$ in the prop statements.\n- Page 6: It may clarify presentation for readers less familiar with online prediction to mention that $O(T^{1/2})$ is often minimax optimal.", "questions_for_authors": "See \"Weaknesses\" above. I will just paste the same questions I had above here:\n\n1. This is not a huge weakness, but it might make the paper more complete to have a corresponding batch setup, with results for the batch case. I wonder if the authors have already considered this and ran into a snag with, say, a boilerplate online-to-batch conversion of their algorithm? I imagine this is straightforward, though I might be missing something.\n2. The rates presented all depend on $T$ indiscriminately for *every* group, which I understand is part of the definition of DCE and LCE (as both definitions take a max over the groups). However, is it possible to obtain more fine-grained guarantees for each group for DCE corresponding to the number of rounds for which the group was active? If $T_g := \\sum_{t = 1}^T \\mathbf{1}\\{ g = \\mathrm{argmax}_{j \\in [k]} f( j \\mid x_t, y_t) \\}$, is it possible to achieve a more fine-grained bound where DCE depends on $T_g$ for each group?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper proposes a new perspective for multi-group guarantees in learning. A common viewpoint currently is to define groups as being identifiable by some (simple) function of the features. The paper suggests that groups can instead of identified by some natural clustering present in the feature space. An issue that arises then is that this clustering may not be known, and the paper shows that an approach which first clusters and then predicts gets a sub-optimal T^(2/3) rate on an online calibration task (and this might be a barrier for such direct unsupervised learning approaches). In contrast, the paper shows that T^(1/2) regret is possible, using a multicalibration algorithm on some cover over likelihood ratios.

Overall, I think the new statistical indistinguishability perspective on multi-group fairness (instead of defining it using a fixed function class), and also the results which get around barriers in unsupervised learning, are both interesting and relevant to the ICML community. Therefore, I recommend acceptance.
Decision: Accept (poster)