Kandinsky Conformal Prediction: Beyond Class- and Covariate-Conditional Coverage

Conformal prediction is a powerful distribution-free framework for constructing prediction sets with coverage guarantees. Classical methods, such as split conformal prediction, provide marginal coverage, ensuring that the prediction set contains the label of a random test point with a target probability. However, these guarantees may not hold uniformly across different subpopulations, leading to disparities in coverage. Prior work has explored coverage guarantees conditioned on events related to the covariates and label of the test point. We present Kandinsky conformal prediction, a framework that significantly expands the scope of conditional coverage guarantees. In contrast to Mondrian conformal prediction, which restricts its coverage guarantees to disjoint groups—reminiscent of the rigid, structured grids of Piet Mondrian’s art—our framework flexibly handles overlapping and fractional group memberships defined jointly on covariates and labels, reflecting the layered, intersecting forms in Wassily Kandinsky’s compositions. Our algorithm unifies and extends existing methods, encompassing covariate-based group conditional, class conditional, and Mondrian conformal prediction as special cases, while achieving a minimax-optimal high-probability conditional coverage bound. Finally, we demonstrate the practicality of our approach through empirical evaluation on real-world datasets.

Conformal prediction is a powerful technique for making predictions with guaranteed reliability, ensuring that a prediction set will contain the true answer a certain percentage of the time. Imagine an AI system that predicts income for loan applications. While it might cover the correct answer 90% of the time overall, what if this coverage drops to 70% for a specific racial group or gender, while being 95% for another? This creates a serious issue, especially when individuals belong to multiple, overlapping groups—for example, a person can be both "female" and "of a certain ethnicity."We've developed a new technique called "Kandinsky Conformal Prediction," named after the artist Wassily Kandinsky, whose paintings feature layered and intersecting shapes. Much like his art, our method is designed to handle the complexity of overlapping groups and even "fractional" group memberships, where belonging to an unobserved group is a matter of probability rather than a strict yes/no. This technique ensures that the promised level of coverage holds true for these specific communities, not just for an overall average.Our method effectively ensured fair and reliable detection of toxic online comments across 16 different overlapping demographic groups, and achieved consistent income prediction coverage across U.S. states. Despite its advanced capabilities, our algorithm is computationally efficient and statistically optimal, requiring as few samples as possible in a single training pass. In essence, this practical research leads to more trustworthy and equitable AI systems.