Learning With Multi-Group Guarantees For Clusterable Subpopulations

Thanks for your detailed review and suggestions! To briefly address your questions:

Q1: Online-to-batch.

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?

Yes, 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.

Q2: Group-dependent rates.

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?

This 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.

[1] Noarav et.al. High-Dimensional Prediction for Sequential Decision Making

[2] Haghtalab et.al. A Unifying Perspective on Multicalibration: Game Dynamics for Multi-Objective Learning

Thanks for your review and suggestions! We will incorporate your presentation recommendations in the next versions.

Q1: Covering of H

To obtain theorem 4.4, we need to run algorithm 2 with G=H, correct?

For 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.

Q2: DCE vs LCE

Is there a natural, intuitive interpretation of DCE / LCE and the difference between the two?

The difference between DCE and LCE as (per-subgroup) performance measures is critical when subgroups are overlapping.

As 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.

Now 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.

Q3: Computational Efficiency

Is the proposed algorithm 2 computationally tractable?

Multicalibration 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.

On Gopalan et.al. 2021:

Thank 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.

[1] Garg et.al. Oracle Efficient Online Multicalibration and Omniprediction

[2] Globus-Harris et.al. Multicalibration as Boosting for Regression

Thanks for your review and questions!

Q1: On empirical results

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?

We 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.

Q2: On misspecification.

Given the potential for model misspecification, would this method still hold?

We 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.

It 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.

Could you provide high-level comparison between the method proposed here versus the power posterior proposed in Miller et.al. from the methodology perspective?

Miller 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.

Perhaps 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.

Q3: Knowing the number of clusters k.

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.

While 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.

All 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.

[1] Hebert-Johnson et.al., Multicalibration: Calibration for the (computationally-identifiable) masses

[2] Dwork et.al., Outcome Indistinguishability

[3] Gopalan et.al., Ominpredictors

[4] Azizyan et.al., Minimax theory for high-dimensional gaussian mixtures with sparse mean separation

[5] Hardt and Price, Tight bounds for learning a mixture of two gaussians.