論文の概要: 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乗の和の上界を証明して得られる。
擬似予想の集合の被覆数を境界とするこのアプローチは、それ自体が興味深く、将来の研究で他の応用を見出すかもしれない。
関連論文リスト
- Robust Sparse Regression with Non-Isotropic Designs [4.964650614497048]
2つの敵が同時に存在するときの疎線形回帰を効率的に計算可能な推定器を設計する手法を開発した。
2つの敵が存在する場合の重み付き設計に適した重み付きハマー損失の新しい解析法を提案する。
論文 参考訳（メタデータ） (2024-10-31T13:51:59Z) - Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。
まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。
我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
論文 参考訳（メタデータ） (2024-06-07T12:07:16Z) - Already Moderate Population Sizes Provably Yield Strong Robustness to Noise [53.27802701790209]
2つの進化的アルゴリズムは、OneMaxベンチマークのランタイムを増大させることなく、一定のノイズ確率を許容できることを示す。
この結果は、ノイズのない子孫は親と騒々しい子孫の間に偏りのある均一な交叉と見なすことができるという、新しい証明の議論に基づいている。
論文 参考訳（メタデータ） (2024-04-02T16:35:52Z) - Robust Sparse Estimation for Gaussians with Optimal Error under Huber Contamination [42.526664955704746]
本研究では,平均推定,PCA,線形回帰に着目したハマー汚染モデルにおけるスパース推定タスクについて検討する。
それぞれのタスクに対して、最適なエラー保証を備えた最初のサンプルと計算効率の良い頑健な推定器を与える。
技術レベルでは、スパース方式における新しい多次元フィルタリング法を開発し、他の応用を見出すことができる。
論文 参考訳（メタデータ） (2024-03-15T15:51:27Z) - A Sub-Quadratic Time Algorithm for Robust Sparse Mean Estimation [6.853165736531941]
逆数外乱の存在下でのスパース平均推定のアルゴリズム的問題について検討する。
我々の主な貢献は、$mathrmpoly(k,log d,1/epsilon)$サンプルを用いて、エフェサブクアクラティック時間で実行される頑健なスパース平均推定アルゴリズムである。
論文 参考訳（メタデータ） (2024-03-07T18:23:51Z) - Error-mitigated fermionic classical shadows on noisy quantum devices [0.3775283002059579]
古典的シャドウ (CS) アルゴリズムは、必要な量子状態コピー数を減らして解を提供する。
本稿では,ゲート独立性,時間定常性,マルコフ雑音(GTM)を仮定した誤り緩和型CSアルゴリズムを提案する。
提案アルゴリズムは,GTMノイズに対する$widetildemathcal O(knk)$状態コピーと$widetildemathcal O(sqrtn)$キャリブレーションによる$k$-RDMを効率的に推定する。
論文 参考訳（メタデータ） (2023-10-19T13:27:19Z) - 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) - Robust Sparse Mean Estimation via Sum of Squares [42.526664955704746]
本研究では,高次元スパース平均推定の問題点を,逆数外乱の$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) - Learning Halfspaces with Tsybakov Noise [50.659479930171585]
テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。
真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
論文 参考訳（メタデータ） (2020-06-11T14:25:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。