# Computing High-dimensional Confidence Sets for Arbitrary Distributions

arXiv: https://arxiv.org/abs/2504.02723 · HTML: https://mlsanity.com/paper/2504.02723/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 62 references that are in the map.
- First posted on arXiv 3 Apr 2025.

## Builds on (most cited first, 12 of 12)

- [A Unifying Review of Deep and Shallow Anomaly Detection](https://mlsanity.com/paper/2009.11732/) (2020)
- [Robust Estimators in High Dimensions without the Computational Intractability](https://mlsanity.com/paper/1604.06443/) (2016)
- [Agnostic Estimation of Mean and Covariance](https://mlsanity.com/paper/1604.06968/) (2016)
- [Learning by Transduction](https://mlsanity.com/paper/1301.7375/) (2013)
- [Theoretical Foundations of Conformal Prediction](https://mlsanity.com/paper/2411.11824/) (2024)
- [Learning from Untrusted Data](https://mlsanity.com/paper/1611.02315/) (2016)
- [Nested conformal prediction and quantile out-of-bag ensemble methods](https://mlsanity.com/paper/1910.10562/) (2019)
- [Probabilistic Conformal Prediction Using Conditional Random Samples](https://mlsanity.com/paper/2206.06584/) (2022)
- [List-Decodable Mean Estimation in Nearly-PCA Time](https://mlsanity.com/paper/2011.09973/) (2020)
- [Volume Optimality in Conformal Prediction with Structured Prediction Sets](https://mlsanity.com/paper/2502.16658/) (2025)
- [Generative Conformal Prediction with Optimized Coverage Allocation](https://mlsanity.com/paper/2410.13735/) (2024)
- [A Sub-linear Time Framework for Geometric Optimization with Outliers in High Dimensions](https://mlsanity.com/paper/2004.10090/) (2020)

## Built on by (most cited first, 2 of 2)

- [Learning Confidence Ellipsoids and Applications to Robust Subspace Recovery](https://mlsanity.com/paper/2512.16875/) (2025)
- [Compact Conformal Subgraphs](https://mlsanity.com/paper/2602.07530/) (2026)

## Abstract (arXiv)

We study the problem of learning a high-density region of an arbitrary distribution over ℝd. Given a target coverage parameter δ, and sample access to an arbitrary distribution D, we want to output a confidence set S subset ℝd such that S achieves δ coverage of D, i.e., mathbbPy ~ D left[ y ∈ S right] ≥ δ, and the volume of S is as small as possible. This is a central problem in high-dimensional statistics with applications in finding confidence sets, uncertainty quantification, and support estimation. In the most general setting, this problem is statistically intractable, so we restrict our attention to competing with sets from a concept class C with bounded VC-dimension. An algorithm is competitive with class C if, given samples from an arbitrary distribution D, it outputs in polynomial time a set that achieves δ coverage of D, and whose volume is competitive with the smallest set in C with the required coverage δ. This problem is computationally challenging even in the basic setting when C is the set of all Euclidean balls. Existing algorithms based on coresets find in polynomial time a ball whose volume is exp(tildeO( d/ log d))-factor competitive with the volume of the best ball. Our main result is an algorithm that finds a confidence set whose volume is exp(tildeO(d1/2)) factor competitive with the optimal ball having the desired coverage. The algorithm is improper (it outputs an ellipsoid). Combined with our computational intractability result for proper learning balls within an exp(tildeO(d1-o(1))) approximation factor in volume, our results provide an interesting separation between proper and (improper) learning of confidence sets.