論文の概要: List-Decodable Subspace Recovery: Dimension Independent Error in
Polynomial Time
- arxiv url: http://arxiv.org/abs/2002.05139v3
- Date: Thu, 7 Jan 2021 17:54:57 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-01 19:46:57.951038
- Title: List-Decodable Subspace Recovery: Dimension Independent Error in
Polynomial Time
- Title（参考訳）: List-Decodable Subspace Recovery: 多項式時間における次元独立誤差
- Authors: Ainesh Bakshi and Pravesh K. Kothari
- Abstract要約: リスト化可能部分空間のリカバリにおいて、入力は$n$ポイント$alpha n$(ある$alpha ll 1/2$)の集合であり、それらは分布$mathcalD$から引き出される。
本研究は, より高速な固定ポリノミカルランニング時間を用いて, アンフェクタブルな集中防止誤差の3つの側面について, 結果を改善するものである。
- 参考スコア（独自算出の注目度）: 5.812499828391904
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In list-decodable subspace recovery, the input is a collection of $n$ points
$\alpha n$ (for some $\alpha \ll 1/2$) of which are drawn i.i.d. from a
distribution $\mathcal{D}$ with a isotropic rank $r$ covariance $\Pi_*$ (the
\emph{inliers}) and the rest are arbitrary, potential adversarial outliers. The
goal is to recover a $O(1/\alpha)$ size list of candidate covariances that
contains a $\hat{\Pi}$ close to $\Pi_*$. Two recent independent works
(Raghavendra-Yau, Bakshi-Kothari 2020) gave the first efficient algorithm for
this problem. These results, however, obtain an error that grows with the
dimension (linearly in [RY] and logarithmically in BK) at the cost of
quasi-polynomial running time) and rely on \emph{certifiable
anti-concentration} - a relatively strict condition satisfied essentially only
by the Gaussian distribution.
In this work, we improve on these results on all three fronts:
\emph{dimension-independent} error via a faster fixed-polynomial running time
under less restrictive distributional assumptions. Specifically, we give a
$poly(1/\alpha) d^{O(1)}$ time algorithm that outputs a list containing a
$\hat{\Pi}$ satisfying $\|\hat{\Pi} -\Pi_*\|_F \leq O(1/\alpha)$. Our result
only needs $\mathcal{D}$ to have \emph{certifiably hypercontractive} degree 2
polynomials. As a result, in addition to Gaussians, our algorithm applies to
the uniform distribution on the hypercube and $q$-ary cubes and arbitrary
product distributions with subgaussian marginals. Prior work (Raghavendra and
Yau, 2020) had identified such distributions as potential hard examples as such
distributions do not exhibit strong enough anti-concentration. When
$\mathcal{D}$ satisfies certifiable anti-concentration, we obtain a stronger
error guarantee of $\|\hat{\Pi}-\Pi_*\|_F \leq \eta$ for any arbitrary $\eta >
0$ in $d^{O(poly(1/\alpha) + \log (1/\eta))}$ time.
- Abstract（参考訳）: リスト化可能部分空間の回復において、入力は$n$ポイント$\alpha n$(ある$\alpha \ll 1/2$)の集合であり、これは分布$\mathcal{D}$と等方的ランク$r$ covariance$\Pi_*$(the \emph{inliers})から引き出される。
目標は、$\hat{\pi}$が$\pi_*$に近い候補共分散の$o(1/\alpha)$のサイズリストを復元することである。
最近の2つの独立した研究(Raghavendra-Yau, Bakshi-Kothari 2020)はこの問題に対する最初の効率的なアルゴリズムを与えた。
しかし、これらの結果は半多項ランニングタイムのコストで次元(線形に[ry] と bk に対数的に)で増加する誤差を得て、ガウス分布によって本質的に満たされる比較的厳密な条件である \emph{certizable anti-concentration} に依存する。
本研究は, より高速な固定ポリノミカルランニング時間による<emph{dimension-independent}エラーを, より限定的な分布仮定の下で行うことにより, これらの結果を改善するものである。
具体的には、$\hat{\Pi} -\Pi_*\|_F \leq O(1/\alpha)$を満たす$\hat{\Pi}$を含むリストを出力する$poly(1/\alpha) d^{O(1)}を出力する。
我々の結果は、次数 2 の多項式を持つために$\mathcal{D}$ しか必要としない。
その結果,gaussian に加えて,超立方体および q$-ary 立方体上の一様分布と,subgaussian marginals を持つ任意の積分布にも適用できる。
以前の研究(raghavendra and yau, 2020)は、そのような分布を潜在的なハードな例として認識しており、そのような分布は十分な反濃度を示すことができない。
任意の$\eta > 0$ in $d^{o(poly(1/\alpha) + \log (1/\eta))} $ time に対して、$\mathcal{d}$ が証明可能な反集中性を満たすと、より強いエラー保証が得られる。
関連論文リスト
- Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。
本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-11-01T17:59:53Z) - Robust Distribution Learning with Local and Global Adversarial Corruptions [17.22168727622332]
誤差を$sqrtvarepsilon k + rho + tildeO(dsqrtkn-1/(k lor2)$で有界な共分散を持つ場合、効率的な有限サンプルアルゴリズムを開発する。
我々の効率的な手順は、理想的だが難解な2-ワッサーシュタイン射影推定器の新たなトレースノルム近似に依存する。
論文 参考訳（メタデータ） (2024-06-10T17:48:36Z) - Estimation and Inference in Distributional Reinforcement Learning [28.253677740976197]
サイズ$widetilde Oleft(frac|mathcalS||mathcalA|epsilon2 (1-gamma)4right)$ suffices to ensure the Kolmogorov metric and total variation metric between $hatetapi$ and $etapi$ is below $epsilon$ with high probability。
以上の結果から,多種多様な統計的汎関数の統計的推測への統一的アプローチがもたらされた。
論文 参考訳（メタデータ） (2023-09-29T14:14:53Z) - Near Sample-Optimal Reduction-based Policy Learning for Average Reward
MDP [58.13930707612128]
この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。
我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
論文 参考訳（メタデータ） (2022-12-01T15:57:58Z) - A spectral least-squares-type method for heavy-tailed corrupted
regression with unknown covariance \& heterogeneous noise [2.019622939313173]
重み付き最小二乗線形回帰は、少なくとも$epsilon n$ arbitrary outliersの$n$のラベル特徴サンプルを破損させたと仮定して再検討する。
本稿では,$(Sigma,Xi) や $Xi$ の演算ノルムに関する知識を前提に,電力法に基づくほぼ最適に計算可能な推定器を提案する。
論文 参考訳（メタデータ） (2022-09-06T23:37:31Z) - List-Decodable Covariance Estimation [1.9290392443571387]
共分散推定アルゴリズムを初めて提案する。
この結果から,リスト復号化可能な線形回帰と部分空間復元のための初となるエンフェクサクタクティックアルゴリズムが提案された。
論文 参考訳（メタデータ） (2022-06-22T09:38:06Z) - Faster Sampling from Log-Concave Distributions over Polytopes via a
Soft-Threshold Dikin Walk [28.431572772564518]
我々は、$d$-dimensional log-concave distribution $pi(theta) propto e-f(theta)$からポリトープ$K$に制約された$m$不等式をサンプリングする問題を考える。
我々の主な成果は、少なくとも$O((md + d L2 R2) times MDomega-1) log(fracwdelta)$ arithmetic operation to sample from $pi$ の "soft-warm' variant of the Dikin walk Markov chain" である。
論文 参考訳（メタデータ） (2022-06-19T11:33:07Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳（メタデータ） (2022-06-17T17:55:43Z) - Optimal Mean Estimation without a Variance [103.26777953032537]
本研究では,データ生成分布の分散が存在しない環境での重み付き平均推定問題について検討する。
最小の信頼区間を$n,d,delta$の関数として得る推定器を設計する。
論文 参考訳（メタデータ） (2020-11-24T22:39:21Z) - Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and
ReLUs under Gaussian Marginals [49.60752558064027]
ガウス境界の下では、半空間とReLUを不可知的に学習する基本的な問題について検討する。
我々の下限は、これらのタスクの現在の上限が本質的に最良のものであるという強い証拠を与える。
論文 参考訳（メタデータ） (2020-06-29T17:10:10Z) - Curse of Dimensionality on Randomized Smoothing for Certifiable
Robustness [151.67113334248464]
我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。
我々はCIFARに関する実験結果を示し,その理論を検証した。
論文 参考訳（メタデータ） (2020-02-08T22:02:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。