# Learning Confidence Ellipsoids and Applications to Robust Subspace Recovery

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 49 references that are in the map.
- First posted on arXiv 18 Dec 2025.

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

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Least Ambiguous Set-Valued Classifiers with Bounded Error Levels](https://mlsanity.com/paper/1609.00451/) (2016)
- [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)
- [Conformal prediction for multi-dimensional time series by ellipsoidal sets](https://mlsanity.com/paper/2403.03850/) (2024)
- [An Overview of Robust Subspace Recovery](https://mlsanity.com/paper/1803.01013/) (2018)
- [Minimum Volume Conformal Sets for Multivariate Regression](https://mlsanity.com/paper/2503.19068/) (2025)
- [A near-optimal algorithm for approximating the John Ellipsoid](https://mlsanity.com/paper/1905.11580/) (2019)
- [Point Location and Active Learning: Learning Halfspaces Almost Optimally](https://mlsanity.com/paper/2004.11380/) (2020)
- [A Strongly Polynomial Algorithm for Approximate Forster Transforms and its Application to Halfspace Learning](https://mlsanity.com/paper/2212.03008/) (2022)
- [Randomized Rounding for the Largest Simplex Problem](https://mlsanity.com/paper/1412.0036/) (2014)
- [Volume Optimality in Conformal Prediction with Structured Prediction Sets](https://mlsanity.com/paper/2502.16658/) (2025)
- [Smoothed Analysis in Unsupervised Learning via Decoupling](https://mlsanity.com/paper/1811.12361/) (2018)
- [Conformal Prediction for Distribution-free Optimal Control of Linear Stochastic Systems](https://mlsanity.com/paper/2411.19132/) (2024)
- [Online Conformal Prediction with Efficiency Guarantees](https://mlsanity.com/paper/2507.02496/) (2025)
- [Computing High-dimensional Confidence Sets for Arbitrary Distributions](https://mlsanity.com/paper/2504.02723/) (2025)

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

- [Low-Degree Method Fails to Predict Robust Subspace Recovery](https://mlsanity.com/paper/2603.02594/) (2026)
- [Compact Conformal Subgraphs](https://mlsanity.com/paper/2602.07530/) (2026)

## Abstract (arXiv)

We study the problem of finding confidence ellipsoids for an arbitrary distribution in high dimensions. Given samples from a distribution D and a confidence parameter α, the goal is to find the smallest volume ellipsoid E which has probability mass mathbbPD[E] ≥ 1-α. Ellipsoids are a highly expressive class of confidence sets as they can capture correlations in the distribution, and can approximate any convex set. In statistics, this is the classic minimum volume estimator introduced by Rousseeuw as a robust non-parametric estimator of location and scatter. However in high dimensions, it becomes NP-hard to obtain any non-trivial approximation factor in volume when the condition number β of the ellipsoid (ratio of the largest to the smallest axis length) goes to ∞. This motivates the focus of our paper: can we efficiently find confidence ellipsoids with volume approximation guarantees when compared to ellipsoids of bounded condition number β? Our main result is a polynomial time algorithm that finds an ellipsoid E whose volume is within a O(β)γ d multiplicative factor of the volume of best β-conditioned ellipsoid while covering at least 1-O(α/γ) probability mass for any γ ∈ (0,1). In particular, setting γ = o(1), this gives a O(β)o(d) volume approximation, with a multiplicative loss in miscoverage. We complement this with a computational hardness result that shows that such a dependence on β seems necessary, even with some slack in coverage. The algorithm and analysis uses the rich primal-dual structure of the minimum volume enclosing ellipsoid and the geometric Brascamp-Lieb inequality. As a consequence, we obtain the first polynomial time algorithm with approximation guarantees on worst-case instances of the robust subspace recovery problem.