論文の概要: Learning Confidence Ellipsoids and Applications to Robust Subspace Recovery

• arxiv url: http://arxiv.org/abs/2512.16875v1
• Date: Thu, 18 Dec 2025 18:42:20 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-12-19 18:10:32.220217
• Title: Learning Confidence Ellipsoids and Applications to Robust Subspace Recovery
• Title（参考訳）: 信頼度楕円体学習とロバスト部分空間復元への応用
• Authors: Chao Gao, Liren Shan, Vaidehi Srinivas, Aravindan Vijayaraghavan,
• Abstract要約: 高次元の任意の分布に対する信頼楕円体を求める問題について検討する。 最小体積楕円体の豊富な原始双対構造と幾何学的ブラスカン・リーブ不等式を用いる。
• 参考スコア（独自算出の注目度）: 32.62523627269506
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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 $\Pr_{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. This problem has been studied in many different communities. 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 $γ< α$. We complement this with a computational hardness result that shows that such a dependence seems necessary up to constants in the exponent. 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.
• Abstract（参考訳）: 高次元の任意の分布に対する信頼楕円体を求める問題について検討する。 分布 $D$ と信頼パラメータ $α$ のサンプルが与えられた場合、その目標は、確率質量 $\Pr_{D}[E] \ge 1-α$ を持つ最小の体積楕円体 $E$ を見つけることである。 楕円体(英: Ellipsoids)は、分布の相関を捉えることができ、任意の凸集合を近似できる、非常に表現力のある信頼集合のクラスである。 この問題は多くの異なるコミュニティで研究されている。 統計学において、これはルセフがロバストな位置と散乱の非パラメトリック推定器として導入した古典的な最小体積推定器である。 しかし、高次元では、楕円体(最も大きい軸長の比)の条件数$β$が$\infty$となると、体積の非自明な近似係数を得るのがNPハードになる。 これは、有界条件数$β$の楕円体と比較して、体積近似保証付き信頼楕円体を効率的に見つけることができるか? 我々の主な結果は多項式時間アルゴリズムで、任意の$γ<α$に対して少なくとも1-O(α/γ)$確率質量を被覆しながら、その体積が$O(β^{γd})$β$条件楕円体体積の乗算係数である楕円体$E$を求める。 我々はこれを計算硬度の結果と補完し、そのような依存が指数の定数まで必要であることを示す。 このアルゴリズムと解析は、最小体積を囲む楕円体と幾何学的ブラスカン・リーブ不等式からなる豊富な原始双対構造を用いる。 その結果、ロバストな部分空間回復問題の最悪の事例に対して近似保証付き多項式時間アルゴリズムが得られた。

関連論文リスト

• Computing High-dimensional Confidence Sets for Arbitrary Distributions [22.923139209762788]
  最良球の体積と競合する$exp(tildeO(d1/2)$因子を持つ信頼集合を求めるアルゴリズムが見つかる。 我々の結果は、信頼セットの適切な(不適切な)学習と適切な(不適切な)学習を、興味深い分離を提供する。
  論文  参考訳（メタデータ） (2025-04-03T16:05:10Z)
• A Nearly Tight Bound for Fitting an Ellipsoid to Gaussian Random Points [50.90125395570797]
  このことは対数的因子の中でのciteSaundersonCPW12 の予想をほぼ成立させる。 後者の予想は、機械学習とある種の統計上の問題に対する2乗下界との結びつきから、過去10年間で大きな注目を集めている。
  論文  参考訳（メタデータ） (2022-12-21T17:48:01Z)
• Near-optimal fitting of ellipsoids to random points [68.12685213894112]
  楕円体をランダムな点に合わせるという基本的な問題は、低ランク行列分解、独立成分分析、主成分分析に関係している。 我々はこの予想を、ある$n = Omega(, d2/mathrmpolylog(d))$ に対する適合楕円体を構成することで対数的因子まで解決する。 我々の証明は、ある非標準確率行列の便利な分解を用いて、サンダーソン等最小二乗構成の実現可能性を示す。
  論文  参考訳（メタデータ） (2022-08-19T18:00:34Z)
• A Law of Robustness beyond Isoperimetry [84.33752026418045]
  我々は、任意の分布上でニューラルネットワークパラメータを補間する頑健性の低い$Omega(sqrtn/p)$を証明した。 次に、$n=mathrmpoly(d)$のとき、スムーズなデータに対する過度なパラメータ化の利点を示す。 我々は、$n=exp(omega(d))$ のとき、$O(1)$-Lipschitz の頑健な補間関数の存在を否定する。
  論文  参考訳（メタデータ） (2022-02-23T16:10:23Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。 構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
  論文  参考訳（メタデータ） (2020-12-14T18:14:08Z)
• Maximizing Determinants under Matroid Constraints [69.25768526213689]
  我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。 この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
  論文  参考訳（メタデータ） (2020-04-16T19:16:38Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。