論文の概要: High-dimensional estimation with missing data: Statistical and computational limits

• arxiv url: http://arxiv.org/abs/2603.16712v1
• Date: Tue, 17 Mar 2026 16:02:41 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-18 17:42:07.393125
• Title: High-dimensional estimation with missing data: Statistical and computational limits
• Title（参考訳）: 欠落データを用いた高次元推定:統計的・計算的限界
• Authors: Kabir Aladin Verchand, Ankit Pensia, Saminul Haque, Rohith Kuditipudi,
• Abstract要約: 我々は,観測結果が欠落したデータである場合の集団パラメータの計算効率を考察する。 平均$ell$法則で推定すると、常に汚染される$in (0, 1)$, (大まかに)$n gtrsim d e1/2$のサンプルは必要となる。 観測結果の欠如により線形回帰に転換し、そのようなギャップが持続しないことを示す。
• 参考スコア（独自算出の注目度）: 13.480462575790334
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider computationally-efficient estimation of population parameters when observations are subject to missing data. In particular, we consider estimation under the realizable contamination model of missing data in which an $ε$ fraction of the observations are subject to an arbitrary (and unknown) missing not at random (MNAR) mechanism. When the true data is Gaussian, we provide evidence towards statistical-computational gaps in several problems. For mean estimation in $\ell_2$ norm, we show that in order to obtain error at most $ρ$, for any constant contamination $ε\in (0, 1)$, (roughly) $n \gtrsim d e^{1/ρ^2}$ samples are necessary and that there is a computationally-inefficient algorithm which achieves this error. On the other hand, we show that any computationally-efficient method within certain popular families of algorithms requires a much larger sample complexity of (roughly) $n \gtrsim d^{1/ρ^2}$ and that there exists a polynomial time algorithm based on sum-of-squares which (nearly) achieves this lower bound. For covariance estimation in relative operator norm, we show that a parallel development holds. Finally, we turn to linear regression with missing observations and show that such a gap does not persist. Indeed, in this setting we show that minimizing a simple, strongly convex empirical risk nearly achieves the information-theoretic lower bound in polynomial time.
• Abstract（参考訳）: 我々は,観測結果が欠落したデータである場合の集団パラメータの計算効率を考察する。 特に, ランダム (MNAR) のメカニズムによらず, 任意の(および未知)の観測結果のε$分の1が欠損したデータに対して, 再現可能な汚染モデルに基づく推定を考察する。 真のデータがガウス的であるとき、いくつかの問題における統計的-計算的ギャップの証拠を提供する。 平均的な$\ell_2$ノルムの推定では、任意の一定の汚染に対して最大$ρ$の誤差を得るには、$ε\in (0, 1)$, (roughly) $n \gtrsim d e^{1/ρ^2}$サンプルが必要であり、この誤差を達成する計算非効率なアルゴリズムがあることが示される。 一方、一般的なアルゴリズムの族内の任意の計算効率のよい手法は、(大まかに)$n \gtrsim d^{1/ρ^2}$のより大きいサンプル複雑さを必要とし、(ほぼ)この下界を達成するような平方和に基づく多項式時間アルゴリズムが存在することを示す。 相対作用素ノルムにおける共分散推定について、並列開発が成り立つことを示す。 最後に、観測の欠如とともに線形回帰に目を向け、そのようなギャップが持続しないことを示す。 実際、この設定において、単純で強凸な経験的リスクを最小化することは、多項式時間における情報理論の下界をほぼ達成することを示した。

関連論文リスト

• High-Dimensional Gaussian Mean Estimation under Realizable Contamination [43.56842719227285]
  本研究では,$mathbbRd$における同一性共分散を持つガウス分布の平均推定を,$$$-contaminationモデルと呼ばれるデータスキームの欠如の下で行う。 このモデルでは、相手は 0 から $$ の間の関数 $r(x)$ を選択でき、各サンプル $x$ は確率 $r(x)$ で失われる。
  論文  参考訳（メタデータ） (2026-03-17T17:04:18Z)
• Efficient Multivariate Robust Mean Estimation Under Mean-Shift Contamination [35.67742880001828]
  平均シフト汚染を用いた高次元ロバスト平均推定のための計算効率のよい最初のアルゴリズムを提案する。 提案アルゴリズムは, ほぼ最適サンプルの複雑性を持ち, サンプル・ポリノミカル時間で動作し, ターゲット平均を任意の精度で近似する。
  論文  参考訳（メタデータ） (2025-02-20T17:53:13Z)
• Statistical-Computational Trade-offs for Density Estimation [60.81548752871115]
  幅広い種類のデータ構造に対して、それらの境界は著しく改善されないことを示す。 これは密度推定のための新しい統計計算トレードオフである。
  論文  参考訳（メタデータ） (2024-10-30T15:03:33Z)
• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。 我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
  論文  参考訳（メタデータ） (2024-03-08T18:50:19Z)
• Robust Sparse Mean Estimation via Sum of Squares [42.526664955704746]
  本研究では,高次元スパース平均推定の問題点を,逆数外乱の$epsilon$-fractionの存在下で検討する。 我々のアルゴリズムは、サム・オブ・スクエア(Sum-of-Squares)ベースのアルゴリズムアプローチに従う。
  論文  参考訳（メタデータ） (2022-06-07T16:49:54Z)
• Fast Projected Newton-like Method for Precision Matrix Estimation under Total Positivity [15.023842222803058]
  現在のアルゴリズムはブロック座標降下法や近点アルゴリズムを用いて設計されている。 本稿では,2次元投影法に基づく新しいアルゴリズムを提案し,慎重に設計された探索方向と変数分割方式を取り入れた。 合成および実世界のデータセットに対する実験結果から,提案アルゴリズムは最先端の手法と比較して計算効率を著しく向上させることを示した。
  論文  参考訳（メタデータ） (2021-12-03T14:39:10Z)
• List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
  高次元におけるリストデコタブル平均推定の基本的な課題について検討する。 我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。 我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
  論文  参考訳（メタデータ） (2020-11-19T17:21:37Z)
• Instability, Computational Efficiency and Statistical Accuracy [101.32305022521024]
  我々は,人口レベルでのアルゴリズムの決定論的収束率と,$n$サンプルに基づく経験的対象に適用した場合の(不安定性)の間の相互作用に基づいて,統計的精度を得るフレームワークを開発する。 本稿では,ガウス混合推定,非線形回帰モデル,情報的非応答モデルなど,いくつかの具体的なモデルに対する一般結果の応用について述べる。
  論文  参考訳（メタデータ） (2020-05-22T22:30:52Z)
• Computationally efficient sparse clustering [67.95910835079825]
  我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。 ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
  論文  参考訳（メタデータ） (2020-05-21T17:51:30Z)

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

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