提出高效算法求高维分布的置信椭球，兼顾体积精度与鲁棒性。
Learning Confidence Ellipsoids and Applications to Robust Subspace Recovery
- 基于最小体积椭球的对偶结构与几何不等式设计算法
- 体积逼近因子为 $O(β)^{γd}$，覆盖概率不低于 $1-O(α/γ)$
- 首次实现鲁棒子空间恢复问题的多项式时间近似保证
本文研究高维任意分布下置信椭球的构造问题。给定分布 $D$ 的样本和置信参数 $α$，目标是找到最小体积椭球 $E$，使得其包含的概率质量满足 $\mathbb{P}_{D}[E] \ge 1-α$。椭球能捕捉分布相关性并逼近任意凸集，在统计中为鲁棒非参数位置与散度估计器。然而在高维下，当椭球条件数 $β$（长轴与短轴比值）趋于无穷时，求解任何非平凡体积近似变为 NP 难。本文提出多项式时间算法，可找到体积在 $O(β)^{γd}$ 倍内的椭球，且覆盖至少 $1-O(α/γ)$ 的概率质量，适用于任意 $γ\in (0,1)$。特别地，取 $γ= o(1)$ 可得 $O(β)^{o(d)}$ 体积近似，伴随可接受的误覆盖损失。同时给出计算下界，表明 $β$ 的依赖性不可避免。算法利用最小体积包围椭球的对偶结构及几何 Brascamp-Lieb 不等式。作为应用，首次获得鲁棒子空间恢复问题在最坏情况下的多项式时间近似算法。
原文摘要 · Abstract (English)
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 $\mathbb{P}_{D}[E] \ge 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 $\infty$. 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 $γ\in (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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。