Minimum Volume Conformal Sets for Multivariate Regression

1. Problem Statement

In multivariate regression, the goal is to predict a vector-valued response $Y \in \mathbb{R}^k$ given a covariate $X \in \mathbb{R}^d$. While point estimates are common, conformal prediction offers a framework to construct prediction sets $C(X)$ that contain the true response with a guaranteed probability $1-\alpha$ (finite-sample validity).

Existing methods for multivariate conformal prediction face significant trade-offs:

• Hyperrectangles (Cartesian products of marginal intervals): Computationally efficient but fail to capture dependencies between dimensions, leading to overly conservative (large) sets.
• Ellipsoidal sets: Capture covariance but assume elliptical symmetry, limiting adaptability to complex, non-Gaussian distributions.
• Flexible methods (Copulas, Density Estimation, Optimal Transport): Can model complex dependencies but often suffer from high computational costs, high estimation variance in high dimensions, or lack an explicit criterion for minimizing the volume of the prediction set.

The Core Challenge: How to construct multivariate prediction sets that are valid (guaranteed coverage), adaptive (fit the specific geometry of the residual distribution), and efficient (minimize volume to provide tight, informative bounds) without relying on rigid geometric assumptions or expensive density estimation.

2. Methodology

The authors propose an optimization-driven framework that learns minimum-volume covering sets (MVCS) directly from data, integrating this with conformal prediction to ensure validity.

A. Minimum-Volume Covering Sets (MVCS)

The core of the method is solving an optimization problem to find the smallest set containing a fraction $1-\alpha$ of the data points.

• Geometric Representation: Instead of fixed shapes, the method defines prediction sets using arbitrary norm balls:
  $$B(\|\cdot\|, M, \mu) = \{y \in \mathbb{R}^k \mid \|M(y - \mu)\| \leq 1\}$$
  where $M$ is a shape matrix and $\mu$ is the center.
• Optimization Objective: Minimize the volume of the set subject to a coverage constraint (containing at least $n-r+1$ points).
  • Single-Norm Learning: The framework extends beyond fixed norms (like Euclidean) by learning the $p$-norm parameter ($p \in (0, \infty)$) jointly with $M$ and $\mu$. This allows the set shape to adapt to the data's geometry (e.g., elongated for anisotropic data, axis-aligned for exponential distributions).
  • Multi-Norm Formulation: To handle asymmetric uncertainty, the space is partitioned into regions (e.g., quadrants), each with its own learned norm $p_j$ and scaling matrix $D_j$. This creates a flexible, piecewise-defined prediction set.
• Optimization Strategy:
  • The problem is non-convex due to the cardinality constraint (counting points inside the set).
  • The authors reformulate the problem using a Difference-of-Convex (DC) decomposition, allowing the use of the DC Algorithm (DCA) for efficient local optimization.
  • For learning the $p$-norm, they employ first-order optimization (e.g., Adam optimizer) by parameterizing the shape matrix $M$ as $AA^\top$ to ensure positive semi-definiteness and reparameterizing $p$ as $|p|$ for unconstrained optimization.

B. Integration with Supervised Learning

The framework is extended to regression by jointly optimizing the predictive model $f_\theta$ and the uncertainty set.

• Joint Optimization: Instead of fitting a model first and then constructing sets around residuals, the method minimizes the volume of the covering set over the residuals $\{y_i - f_\theta(x_i)\}$ simultaneously with the model parameters $\theta$.
• Local Adaptivity: The method introduces a covariate-dependent transformation $M(x)$. This allows the prediction set to change shape and size based on the input $X$, effectively capturing heteroskedasticity (where uncertainty varies across the feature space).

C. Conformalization for Finite-Sample Validity

To guarantee finite-sample coverage on unseen data, the learned sets are integrated into a split conformal prediction framework:

1. Training: Learn the model $f_\theta$, the transformation $M(x)$, and the norm $p$ on a training set.
2. Calibration: Compute nonconformity scores $s(x, y) = \|M(x)(y - f_\theta(x))\|_p$ on a separate calibration set.
3. Thresholding: Determine a threshold $\hat{q}_\alpha$ as the empirical $(1-\alpha)$-quantile of the calibration scores.
4. Prediction: The final prediction set for a new $X_{new}$ is $\{y \mid \|M(X_{new})(y - f_\theta(X_{new}))\|_p \leq \hat{q}_\alpha\}$.

This ensures the set satisfies $\text{Prob}(Y \in C(X)) \geq 1-\alpha$ without assuming a specific distribution for the residuals.

3. Key Contributions

1. Minimum-Volume Covering Sets (MVCS): A general optimization framework for finding the smallest volume set covering a fraction of data in $\mathbb{R}^k$, supporting arbitrary norm balls and multi-norm formulations.
2. Adaptive Norm Learning: The ability to learn the optimal $p$-norm (and multiple norms) from data, allowing prediction sets to adapt to complex, non-elliptical residual distributions (e.g., exponential, uniform, anisotropic).
3. Joint Optimization: An integrated scheme that learns the predictor, the uncertainty structure, and the norm simultaneously, resulting in tighter sets than post-hoc methods.
4. Local Adaptivity: A formulation that allows the prediction set geometry to vary with the input covariate $X$, capturing heteroskedastic uncertainty.
5. Conformal Validity: A rigorous integration with split conformal prediction to provide finite-sample coverage guarantees for these optimized, adaptive sets.

4. Experimental Results

The authors evaluated their method on synthetic and real-world datasets, comparing against baselines like Naïve Quantile Regression, Empirical Covariance (Ellipsoidal), and Local Empirical Covariance.

• Synthetic Data:
  • In settings with anisotropic or non-Gaussian noise (e.g., exponential distributions), the learned MVCS significantly outperformed fixed-shape baselines (ellipsoids) and Cartesian products.
  • The learned $p$-norms automatically adjusted to the data geometry (e.g., $p \approx 0.5$ for highly anisotropic data, $p \approx 8$ for axis-aligned exponential data).
  • Volume Reduction: The proposed method achieved the smallest average volume across all synthetic scenarios while maintaining the target coverage (e.g., 90% or 99%).
• Real-World Datasets:
  • Tested on 9 benchmark datasets (e.g., Energy, House, Taxi, CASP).
  • The method consistently achieved the lowest normalized volume in 16 out of 18 experiments (for $\alpha=0.1$ and $\alpha=0.01$) compared to Naïve QR, Empirical Covariance, and Local Empirical Covariance.
  • Coverage: The method maintained valid marginal coverage close to the target level (e.g., ~90% for target 0.9), demonstrating robustness and lack of overfitting.
  • Robustness: The method showed resilience to outliers, whereas quantile-based baselines suffered from coverage degradation when outliers shifted the quantile estimates.

5. Significance and Impact

This paper bridges the gap between geometric flexibility and statistical validity in multivariate uncertainty quantification.

• Efficiency: By explicitly minimizing volume, the method provides more informative predictions than conservative baselines (like hyperrectangles) without the computational intractability of density estimation.
• Adaptivity: The ability to learn the shape (norm) and size of the prediction set from data allows it to handle complex, real-world distributions that violate standard Gaussian assumptions.
• Scalability: The use of first-order optimization and split conformal prediction makes the approach scalable to high-dimensional data and large datasets.
• Theoretical Guarantee: Unlike many flexible machine learning approaches that lack rigorous bounds, this method retains the finite-sample coverage guarantee of conformal prediction, making it reliable for safety-critical applications.

In summary, the proposed Minimum-Volume Conformal Sets framework offers a principled, data-driven solution for multivariate regression that is simultaneously valid, adaptive, and efficient.