論文の概要: Higher degree sum-of-squares relaxations robust against oblivious
outliers
- arxiv url: http://arxiv.org/abs/2211.07327v1
- Date: Mon, 14 Nov 2022 13:09:12 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-15 16:36:51.764407
- Title: Higher degree sum-of-squares relaxations robust against oblivious
outliers
- Title(参考訳): 斜め外乱に対してロバストな高次2乗和緩和
- Authors: Tommaso d'Orsi, Rajai Nasser, Gleb Novikov, David Steurer
- Abstract要約: 我々は、$Y=X*+N$という形の推定モデルを考える。
本稿では,2乗推定アルゴリズムが存在するすべての推定問題において,軽度仮定の下で信号が$X*$に回復するアルゴリズム群を紹介する。
- 参考スコア(独自算出の注目度): 14.58610686291355
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider estimation models of the form $Y=X^*+N$, where $X^*$ is some
$m$-dimensional signal we wish to recover, and $N$ is symmetrically distributed
noise that may be unbounded in all but a small $\alpha$ fraction of the
entries. We introduce a family of algorithms that under mild assumptions
recover the signal $X^*$ in all estimation problems for which there exists a
sum-of-squares algorithm that succeeds in recovering the signal $X^*$ when the
noise $N$ is Gaussian. This essentially shows that it is enough to design a
sum-of-squares algorithm for an estimation problem with Gaussian noise in order
to get the algorithm that works with the symmetric noise model. Our framework
extends far beyond previous results on symmetric noise models and is even
robust to adversarial perturbations.
As concrete examples, we investigate two problems for which no efficient
algorithms were known to work for heavy-tailed noise: tensor PCA and sparse
PCA. For the former, our algorithm recovers the principal component in
polynomial time when the signal-to-noise ratio is at least
$\tilde{O}(n^{p/4}/\alpha)$, that matches (up to logarithmic factors) current
best known algorithmic guarantees for Gaussian noise. For the latter, our
algorithm runs in quasipolynomial time and matches the state-of-the-art
guarantees for quasipolynomial time algorithms in the case of Gaussian noise.
Using a reduction from the planted clique problem, we provide evidence that the
quasipolynomial time is likely to be necessary for sparse PCA with symmetric
noise.
In our proofs we use bounds on the covering numbers of sets of
pseudo-expectations, which we obtain by certifying in sum-of-squares upper
bounds on the Gaussian complexities of sets of solutions. This approach for
bounding the covering numbers of sets of pseudo-expectations may be interesting
in its own right and may find other application in future works.
- Abstract(参考訳): 我々は、$Y=X^*+N$という形の推定モデルを考える。ここでは、$X^*$は回復したい$m$次元の信号であり、$N$は対称分布ノイズであり、エントリの小さな$\alpha$分しか有界でないかもしれない。
我々は,ノイズ$n$ がガウス的である場合の信号$x^*$ の回復に成功する2乗和アルゴリズムが存在するすべての推定問題において,軽度な仮定の下で信号 $x^*$ を回復するアルゴリズムのファミリを導入する。
これは本質的には、対称雑音モデルで動作するアルゴリズムを得るために、ガウス雑音を伴う推定問題に対する2乗和アルゴリズムを設計するのに十分であることを示している。
我々のフレームワークは、対称ノイズモデルに関するこれまでの結果を大きく超え、逆摂動に対しても頑健である。
具体的な例として,重み付き雑音に対して効率的なアルゴリズムが動作しない2つの問題,すなわちテンソルpcaとスパースpcaについて検討した。
前者の場合、信号対雑音比が少なくとも$\tilde{o}(n^{p/4}/\alpha)$であるとき、アルゴリズムは多項式時間で主成分を回復する。
後者の場合,我々のアルゴリズムは準ポリノミカル時間で動作し,ガウス雑音の場合の準ポリノミカル時間アルゴリズムの最先端保証と一致する。
プラントクレーク問題からの低減を用いて, 対称雑音を持つpcaのスパースに対して, 準多項時間が必要である可能性が示唆された。
この証明では、疑似予想の集合の被覆数上の境界を使い、解の集合のガウス複素数上の2乗の和の上界を証明して得られる。
擬似予想の集合の被覆数を境界とするこのアプローチは、それ自体が興味深く、将来の研究で他の応用を見出すかもしれない。
関連論文リスト
- A Sub-Quadratic Time Algorithm for Robust Sparse Mean Estimation [6.853165736531941]
逆数外乱の存在下でのスパース平均推定のアルゴリズム的問題について検討する。
我々の主な貢献は、$mathrmpoly(k,log d,1/epsilon)$サンプルを用いて、エフェサブクアクラティック時間で実行される頑健なスパース平均推定アルゴリズムである。
論文 参考訳(メタデータ) (2024-03-07T18:23:51Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳(メタデータ) (2023-07-13T18:59:28Z) - Private estimation algorithms for stochastic block models and mixture
models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。
最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文 参考訳(メタデータ) (2023-01-11T09:12:28Z) - Sample Complexity Bounds for Learning High-dimensional Simplices in
Noisy Regimes [5.526935605535376]
ノイズの多いサンプルから単純さを学習するために、サンプルの複雑さが結びついているのがわかります。
我々は、$mathrmSNRgeOmegaleft(K1/2right)$ である限り、ノイズのないシステムのサンプルの複雑さは、ノイズのないケースのそれと同じ順序であることを示す。
論文 参考訳(メタデータ) (2022-09-09T23:35:25Z) - Robust Sparse Mean Estimation via Sum of Squares [48.07596965953344]
本研究では,高次元スパース平均推定の問題点を,逆数外乱の$epsilon$-fractionの存在下で検討する。
我々のアルゴリズムは、サム・オブ・スクエア(Sum-of-Squares)ベースのアルゴリズムアプローチに従う。
論文 参考訳(メタデータ) (2022-06-07T16:49:54Z) - Gaussian Process Bandit Optimization with Few Batches [49.896920704012395]
有限腕バンディットアルゴリズムにインスパイアされたバッチアルゴリズムを導入する。
O(log T)$ batches in time horizon $T$.sqrtTgamma_T)$ using $O(log T)$ batches in time horizon。
さらに,アルゴリズムの修正版を提案し,バッチ数によって後悔がどう影響するかを特徴付ける。
論文 参考訳(メタデータ) (2021-10-15T00:54:04Z) - Sample-Optimal PAC Learning of Halfspaces with Malicious Noise [4.8728183994912415]
Valiant(1985)の悪意のあるノイズの存在下で$mathRd$の半空間の効率的なPAC学習を研究します。
Awasthi et alのアルゴリズムのための新しい分析を提示します。
そして、ほぼ最適に近いサンプル複雑性を$tildeo(d)$という値で達成できることを示します。
Bbbshoutyetal (2002) のより一般的で強力なノイズモデルにアルゴリズムと解析を拡張し、ほぼ最適なノイズ耐性とサンプルの複雑さを時間内に達成可能であることを示す。
論文 参考訳(メタデータ) (2021-02-11T20:18:20Z) - A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise [55.45544638410858]
本研究では,Tsybakovノイズの存在下でのPAC学習の相同性半空間の問題について検討する。
我々のアルゴリズムは、任意の精度$epsilon$で真のハーフスペースを学習する。
論文 参考訳(メタデータ) (2020-10-04T22:19:06Z) - Learning Halfspaces with Tsybakov Noise [50.659479930171585]
テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。
真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
論文 参考訳(メタデータ) (2020-06-11T14:25:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。