Group conditional validity via multi-group learning
This work addresses distribution-free conformal prediction for group fairness, offering a solution that overcomes limitations of existing methods, though it appears incremental as it builds on multi-group learning techniques.
The paper tackles the problem of achieving group conditional validity in conformal prediction, which is important for hidden stratification and fairness, by proposing a reduction to multi-group learning and a new hierarchical algorithm, resulting in improved sample complexity guarantees and simpler predictors.
We consider the problem of distribution-free conformal prediction and the criterion of group conditional validity. This criterion is motivated by many practical scenarios including hidden stratification and group fairness. Existing methods achieve such guarantees under either restrictive grouping structure or distributional assumptions, or they are overly-conservative under heteroskedastic noise. We propose a simple reduction to the problem of achieving validity guarantees for individual populations by leveraging algorithms for a problem called multi-group learning. This allows us to port theoretical guarantees from multi-group learning to obtain obtain sample complexity guarantees for conformal prediction. We also provide a new algorithm for multi-group learning for groups with hierarchical structure. Using this algorithm in our reduction leads to improved sample complexity guarantees with a simpler predictor structure.