Fugu-MT 論文翻訳(概要): Learning Sparse Parity with Noise in Linear Samples

論文の概要: Learning Sparse Parity with Noise in Linear Samples

arxiv url: http://arxiv.org/abs/2407.19215v1
Date: Sat, 27 Jul 2024 08:57:04 GMT
ステータス: 処理完了
システム内更新日: 2024-07-30 19:21:07.430225
Title: Learning Sparse Parity with Noise in Linear Samples
Title（参考訳）: 線形サンプルにおける雑音によるスパースパリティの学習
Authors: Xue Chen, Wenxuan Shu, Zhaienhe Zhou,
Abstract要約: 低雑音設定と高雑音設定のアルゴリズムを別々に示す。我々は、任意の$eta$に対して$O(eta cdot n/k)k$を実行し、$k$が$n>k/eta$を満たすアルゴリズムを示す。
参考スコア（独自算出の注目度）: 1.2143710013809321
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We revisit the learning parity with noise problem with a sparse secret that involves at most $k$ out of $n$ variables. Let $\eta$ denote the noise rate such that each label gets flipped with probability $\eta$. In this work, we show algorithms in the low-noise setting and high-noise setting separately. We present an algorithm of running time $O(\eta \cdot n/k)^k$ for any $\eta$ and $k$ satisfying $n>k/\eta$. This improves the state-of-the-art for learning sparse parity in a wide range of parameters like $k\le n^{0.99}$ and $\eta < \sqrt{k/n}$, where the best known algorithm had running time at least ${\binom{n}{k/2}} \ge (n/k)^{k/2}$ . Different from previous approaches based on generating biased samples , our new idea is to combine subset sampling and Gaussian elimination. The resulting algorithm just needs $O(k/\eta + k \log \frac{n}{k})$ samples and is structurally simpler than previous algorithms. In the high-noise setting, we present an improvement on Valiant's classical algorithm using $n^{\frac{\omega+o(1)}{3}\cdot k}$ time (with the matrix multiplication constant $\omega$) and $\tilde{O}(k^2)$ samples. For any $\eta<1/2$, our algorithm has time complexity $(n/k)^{\frac{\omega+o(1)}{3}\cdot k}$ and sample complexity $\tilde{O}(k)$. Hence it improves Valiant's algorithm in terms of both time complexity and sample complexity and generalizes Valiant's framework to give the state-of-the-art bound for any $k \le n^{0.99}$ and $\eta \in (0.4,0.5)$.
Abstract（参考訳）: 我々は、最低でも$n$変数の$k$を含むスパースシークレットを用いて、ノイズ問題と学習パリティを再考する。 $\eta$は、各ラベルが確率$\eta$でフリップされるようなノイズ率を表す。本研究では,低雑音設定と高雑音設定のアルゴリズムを別々に示す。我々は、任意の$\eta$と$k$に対して、O(\eta \cdot n/k)^k$を走らせるアルゴリズムを示し、$n>k/\eta$を満たす。これにより、$k\le n^{0.99}$や$\eta < \sqrt{k/n}$のような幅広いパラメータでスパースパリティを学習するための最先端技術が向上し、最もよく知られているアルゴリズムは少なくとも${\binom{n}{k/2}} \ge (n/k)^{k/2}$を走らせた。バイアスサンプルの生成に基づく従来のアプローチと異なり、新しいアイデアはサブセットサンプリングとガウス除去を組み合わせることである。得られたアルゴリズムは、$O(k/\eta + k \log \frac{n}{k})$サンプルを必要とし、以前のアルゴリズムよりも構造的に単純である。高雑音設定では、$n^{\frac{\omega+o(1)}{3}\cdot k}$ time (行列乗算定数 $\omega$) と $\tilde{O}(k^2)$ sample を用いてヴァリアントの古典的アルゴリズムを改善する。任意の$\eta<1/2$に対して、我々のアルゴリズムは時間複雑性$(n/k)^{\frac{\omega+o(1)}{3}\cdot k}$とサンプル複雑性$\tilde{O}(k)$を持つ。したがって、時間複雑性とサンプル複雑性の両方の観点からヴァリアントのアルゴリズムを改善し、ヴァリアントのフレームワークを一般化して、任意の$k \le n^{0.99}$と$\eta \in (0.4,0.5)$に対して最先端のバウンドを与える。

関連論文リスト

Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Models [39.33814194788341]
潜在変数モデル学習の課題について検討する。このような応用により、暗黙のモーメント計算のための一般化されたアルゴリズムを開発した。一般的なアルゴリズムを利用して, 以下のモデルに対する初等学習者を得る。
論文参考訳（メタデータ） (2024-11-23T23:13:24Z)
Towards Optimal Circuit Size for Sparse Quantum State Preparation [10.386753939552872]
我々は、$s$非ゼロ振幅を持つ$n$量子ビットスパース量子状態の準備を検討し、2つのアルゴリズムを提案する。最初のアルゴリズムは$O(ns/log n + n)$ gatesを使用し、以前のメソッドを$O(log n)$で改善する。 2番目のアルゴリズムは、短いハミルトニアンパスを示す二進弦向けに調整されている。
論文参考訳（メタデータ） (2024-04-08T02:13:40Z)
A Sub-Quadratic Time Algorithm for Robust Sparse Mean Estimation [6.853165736531941]
逆数外乱の存在下でのスパース平均推定のアルゴリズム的問題について検討する。我々の主な貢献は、$mathrmpoly(k,log d,1/epsilon)$サンプルを用いて、エフェサブクアクラティック時間で実行される頑健なスパース平均推定アルゴリズムである。
論文参考訳（メタデータ） (2024-03-07T18:23:51Z)
Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文参考訳（メタデータ） (2023-07-24T14:37:22Z)
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)
Sparse PCA Beyond Covariance Thresholding [2.311583680973075]
すべての$t ll k$に対して、[gtrsim fracksqrtntsqrtln(2 + td/k2)$] さえあれば、この問題を解決するアルゴリズムがncdot dO(t)$で実行されていることを示す。スパース植込みベクター問題に対する時間アルゴリズムは,一部の制度における技術状況よりも高い保証が得られる。
論文参考訳（メタデータ） (2023-02-20T18:45:24Z)
Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文参考訳（メタデータ） (2022-04-13T22:18:47Z)
Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文参考訳（メタデータ） (2021-08-19T16:16:48Z)
Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文参考訳（メタデータ） (2020-07-07T17:10:00Z)
Improved quantum algorithm for A-optimal projection [4.248054546466641]
本稿では、Duan emphet al.のアルゴリズムの時間的複雑さを$(frackappa4ssqrtks epsilonsmathrmpolylog)$に補正する。我々のアルゴリズムは、Duan emphet al.のアルゴリズムと比較して少なくとも1つのスピードアップを達成する。
論文参考訳（メタデータ） (2020-06-10T09:31:53Z)
Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文参考訳（メタデータ） (2020-06-06T13:34:41Z)

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

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