Non-Convex and Disjoint Prediction Regions

92 concepts62 papers1 proposal

When quantifying machine learning uncertainty, we want our "safety nets" to be as tight as possible. If a model predicts a house price or a vehicle trajectory, a guarantee like "the true value will be within this region 95% of the time" is only useful if the region isn't unnecessarily massive.

Traditionally, uncertainty quantification frameworks—such as Conformal Prediction (CP) and Robust Optimization (RO)—have relied on rigid, predefined geometric shapes like hyper-rectangles, ellipsoids, or single continuous intervals to bound this uncertainty. While mathematically convenient, these convex shapes suffer from a severe flaw: they are highly inefficient when dealing with complex, real-world data distributions.

Imagine trying to pack a delicate, curved glass vase into a rigid rectangular wooden crate. The crate will inevitably contain a vast amount of empty, wasted space. In uncertainty modeling, this wasted space translates to bloated prediction volumes that include highly improbable or even physically impossible outcomes. To solve this, a major research direction focuses on constructing flexible, non-convex, and disjoint prediction regions that adapt precisely to the underlying geometry of the data.


The Inefficiency of Geometric Rigidity

Why do traditional methods produce such bloated regions? As noted by Michal Klein et al. in Multivariate Conformal Prediction using Optimal Transport (arxiv 2025), standard multivariate uncertainty methods often rely on simple aggregations like maximum norms or Euclidean distances. These metrics inherently force prediction regions into symmetric, rigid geometries like hyper-rectangles or spheres.

When the underlying error distribution is asymmetric, multi-modal, or lies on a curved manifold, these rigid shapes fail completely. They are forced to stretch across low-density spaces to maintain their required statistical coverage. As highlighted by Shai Feldman et al. in Calibrated Multiple-Output Quantile Regression with Representation Learning (arxiv 2021), forcing a convex hull over a curved or disjoint distribution results in overly conservative predictive regions. By contrast, allowing for non-convex shapes can yield uncertainty regions that are orders of magnitude smaller while maintaining identical statistical coverage guarantees.


Mechanism 1: Unwarping Space via Latent Transformations

The core challenge of non-convex uncertainty quantification is mathematical: how do you define a valid, mathematically rigorous boundary around an arbitrary, highly irregular shape?

The solution discovered by researchers is to avoid defining the shape in the messy original data space altogether. Instead, they learn a bijective (reversible) non-linear mapping that "unwarps" the complex data distribution into a simple, well-behaved latent space—such as a standard isotropic Gaussian distribution.

[Complex Data Space]  ---(Bijective Mapping)--->  [Simple Latent Space]
  (Non-convex, curved)                              (Isotropic Gaussian)
           ^                                                 |
           |                                                 v
   [Pullback Region]  <---(Inverse Mapping)----   [Perfect Hypersphere]

In this latent space, drawing an optimal uncertainty boundary is trivial: it is simply a standard hypersphere. Because the mapping is bijective, we can take this perfect latent sphere and project it back through the inverse mapping into the original data space. This process is called a pullback. Because the transformation is highly non-linear, the pulled-back boundary in the original data space warps, bends, and stretches, perfectly conforming to the true data manifold.

Two primary generative architectures make this possible:


Mechanism 2: Density Thresholding and Disjoint Unions

What happens when a distribution is not just curved, but completely split into separate clusters? Consider a autonomous vehicle approaching a fork in the road; the future trajectory distribution is fundamentally bimodal.

A traditional continuous interval or convex region is forced to span the entire "valley" between the two choices, including a massive, low-probability middle region where the car will never actually go.

Traditional Continuous Interval (Bloated):
[====== Mode A ======]--------------------------------[====== Mode B ======]
|_______________________ Included Wasted Space _______________________|

Disjoint Prediction Sets (Optimal Volume):
[====== Mode A ======]                                [====== Mode B ======]

To achieve true efficiency, the prediction set must be allowed to fracture into a union of disjoint regions. Instead of calculating a single distance metric from a central point estimate, these methods estimate the conditional density or individual bin probabilities directly and apply a threshold.

Rafael Izbicki et al. show in Flexible distribution-free conditional predictive bands using density estimators (aistats 2020) that thresholding conditional density estimators naturally produces fragmented, non-contiguous sets for multi-modal data. While this introduces a trade-off—single continuous intervals are often easier for humans to interpret—allowing disjoint regions drastically minimizes the total size of the prediction set by bypassing low-probability gaps.

To make this mathematically rigorous, Chao Gao et al. in Volume Optimality in Conformal Prediction with Structured Prediction Sets (icml 2025) developed dynamic programming algorithms to find the absolute smallest union of $k$ intervals, providing the first formal volume optimality guarantees. By isolating distinct high-probability modes, frameworks like the one proposed by Vincent Plassier et al. in Probabilistic Conformal Prediction with Approximate Conditional Validity (iclr 2025) ensure that uncertainty regions adapt to local data structures, providing tighter, more meaningful guarantees for highly heteroscedastic or multi-modal scenarios.


Application to Robust Optimization

This paradigm shift extends beyond Conformal Prediction into Robust Optimization (RO). In RO, decision-makers optimize against the worst-case scenario within a defined "uncertainty set."

Historically, practitioners used simple boxes or ellipsoids to keep the optimization computationally tractable. However, as argued by Aron Brenner et al. in A Deep Generative Learning Approach for Two-stage Adaptive Robust Optimization (iclr 2025), these simple geometric shapes include physically impossible scenarios, forcing models to prepare for "worst-case" events that could never actually happen. This results in overly conservative and expensive operational decisions.

By utilizing deep generative models like Variational Autoencoders (VAEs) to learn data-driven, non-convex uncertainty boundaries directly from historical samples, the authors demonstrate that optimization frameworks can ignore these impossible outliers. The result is a dramatic reduction in optimization costs while fully preserving real-world safety and robustness guarantees.

History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_disjoint_prediction_sets_32820933,
  title = {disjoint prediction sets},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/disjoint-prediction-sets/rdr_32820933807b4d9eb7320bd2633404dc},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_disjoint_prediction_sets_32820933_v1,
  title = {disjoint prediction sets},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/disjoint-prediction-sets/rdr_32820933807b4d9eb7320bd2633404dc/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake