Technical Summary: Conditional Predictive Inference for General Structured Data with Group Symmetries

Problem Statement

The paper addresses a fundamental limitation in distribution-free predictive inference: the reliance on marginal coverage guarantees versus the practical need for conditional coverage. While standard conformal prediction (Vovk et al., 2005) ensures that a prediction set covers the true target with probability $1-\alpha$ on average over all data realizations (marginal coverage), it often fails to provide valid uncertainty quantification for specific subgroups or local realizations of the data, particularly in heterogeneous settings.

Existing methods attempting to achieve near-conditional coverage (e.g., Gibbs et al., 2025; Hore and Barber, 2024) typically rely on the assumption of exchangeability (or i.i.d. data). However, many real-world structured datasets—such as networks, clustered data, and hierarchical models—violate global exchangeability. While recent work by Dobriban and Yu (2024) introduced the SymmPI framework to handle general group symmetries beyond exchangeability, it only provides marginal coverage guarantees. This leaves a gap: there is no method that simultaneously handles complex group-symmetric structures (like networks or clusters) and provides conditional coverage guarantees that adapt to local heterogeneity.

Methodology: C-SymmPI

The authors propose C-SymmPI (Conditional Symmetric Predictive Inference), a unified framework that extends the SymmPI approach to achieve near-conditional coverage under general group symmetries.

Core Framework

1. Group-Theoretic Setup: The data $Z$ is assumed to be distributionally invariant under a group action $\rho$ of a group $G$ (i.e., $Z \stackrel{d}{=} \rho(G)Z$ where $G \sim U$, the Haar measure). This generalizes exchangeability (where $G$ is the symmetric group $S_n$) to structures like networks (automorphism groups) and hierarchical data (nested permutation groups).
2. Adaptive Threshold Learning: Unlike SymmPI, which computes a single global quantile threshold over the group orbit, C-SymmPI learns an adaptive threshold function $t_z(\cdot)$. This function maps observed data features to a threshold, allowing the prediction set to adapt to local heterogeneity.
3. Relaxed Multi-Accuracy Perspective: The method reformulates the conditional coverage requirement using the multi-accuracy perspective (Hébert-Johnson et al., 2018). Instead of requiring exact conditional coverage for every realization (which is often impossible without distributional assumptions), C-SymmPI minimizes the miscoverage error over a user-specified function class $\mathcal{F}$. Specifically, it ensures:
   $$\left| \mathbb{E}_Z \left[ f(Z_{\text{obs}}) \left( \mathbb{1}\{Z \in \hat{C}(Z_{\text{obs}})\} - (1-\alpha) \right) \right] \right| \leq \varepsilon$$
   for all $f \in \mathcal{F}$. This is achieved by solving a regularized quantile regression problem over the group orbit.

Algorithmic Variants for Efficiency

To address computational challenges in high-dimensional spaces and large groups, two variants are introduced:

• Projected C-SymmPI: Projects the high-dimensional observed data $Z_{\text{obs}}$ onto a lower-dimensional embedding $\eta(Z_{\text{obs}})$ before learning the threshold. This reduces the complexity of the function learning problem.
• Sampled C-SymmPI: Approximates the Haar expectation (group averaging) using a finite Monte Carlo sample of group elements. This is crucial for infinite or very large groups (e.g., rotation groups).

Theoretical Guarantees

The paper establishes near-conditional coverage bounds under two settings:

1. Distributional Invariance: When the data strictly satisfies the group invariance assumption.
2. Distribution Shift: When the invariance is violated, the bound includes an additional term proportional to the Total Variation (TV) distance between the true distribution and the permuted distribution.

Convergence rates are derived for specific function classes:

• Linear Function Classes: The error decays at a rate of $O(d |H| / |G|)$, where $d$ is the dimension, $|G|$ is the group size, and $|H|$ is the size of the stabilizer subgroup.
• RKHS (Reproducing Kernel Hilbert Space): The error decays at a rate of $O(1/\sqrt{|G|/|H|})$.

Key Contributions

1. Unified Framework for Near-Conditional Inference: C-SymmPI is the first framework to extend near-conditional coverage guarantees beyond the i.i.d./exchangeable setting to general data structures with group symmetries (e.g., networks, hierarchical clusters).
2. Theoretical Generalization: It recovers existing state-of-the-art results for i.i.d. data (Gibbs et al., 2025) as special cases while providing new guarantees for non-exchangeable structures.
3. Computational Scalability: The development of Projected and Sampled variants enables the application of conditional inference to high-dimensional observations and large/infinite symmetry groups.
4. Broad Applicability: The framework is instantiated for:
   • Exchangeable Data: Recovering conditional conformal prediction.
   • Two-Layer Hierarchical Models: Including cluster randomized trials (CRTs), providing conditional guarantees at both cluster and individual levels.
   • Network-Structured Data: Adapting to network topology for node-level inference.

Empirical Results

The authors validate C-SymmPI through numerical simulations and real-world applications:

• Simulations (Hierarchical Data): In a two-layer hierarchical model with heterogeneous noise, C-SymmPI produces prediction intervals that adapt to local variance (narrower in low-variance regions, wider in high-variance regions). Competing methods (standard SymmPI, standard conditional CP, single-tree methods) either fail to cover high-variance regions (under-coverage) or produce overly conservative wide intervals.
• PPACT Cluster Randomized Trial: Applied to a real-world trial on pain management. C-SymmPI outperforms the Split-CCI method (Wang et al., 2024) by producing shorter prediction intervals for treatment effects while maintaining valid coverage and achieving a higher fraction of identified beneficial treatments (negative intervals).
• Cora Citation Network: In a network-assisted classification task, C-SymmPI yields shorter prediction sets compared to standard split conformal prediction while maintaining valid coverage, demonstrating adaptivity to prediction uncertainty (shorter intervals for high-confidence predictions).

Significance and Claims

The paper claims that C-SymmPI bridges a critical gap in uncertainty quantification for structured data. By moving from marginal to near-conditional coverage under group symmetries, the method provides more informative and stable prediction sets that respect the inherent heterogeneity of complex data structures (networks, clusters).

The authors emphasize that their approach does not require strong distributional assumptions, remaining distribution-free while leveraging the structural symmetries of the data. The results suggest that for practitioners dealing with hierarchical or networked data, C-SymmPI offers a robust alternative to existing marginal methods, preventing the masking of local heterogeneity that often occurs when averaging over the entire dataset. The framework is presented as a general tool that can be adapted to other structured settings (e.g., trees, images) where group symmetries are present.