論文の概要: 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)$に対して最先端のバウンドを与える。
関連論文リスト
- Sample-Efficient Linear Regression with Self-Selection Bias [7.605563562103568]
未知のインデックス設定における自己選択バイアスを伴う線形回帰の問題を考察する。
我々は,$mathbfw_1,ldots,mathbfw_kinを復元する,新しい,ほぼ最適なサンプル効率($k$)アルゴリズムを提案する。
このアルゴリズムは雑音の仮定をかなり緩めることに成功し、従って関連する最大線形回帰の設定にも成功している。
論文 参考訳(メタデータ) (2024-02-22T02:20:24Z) - 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) - Fast and Practical Quantum-Inspired Classical Algorithms for Solving
Linear Systems [11.929584800629673]
線形系を解くための高速で実用的な量子インスパイアされた古典的アルゴリズムを提案する。
我々の主な貢献は、線形系を解くために量子に着想を得た古典的アルゴリズムへの重球運動量法の適用である。
論文 参考訳(メタデータ) (2023-07-13T08:46:19Z) - Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。
実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
論文 参考訳(メタデータ) (2021-05-17T16:40:48Z) - Improved quantum data analysis [1.8416014644193066]
我々は、$O(log2 m)/epsilon2)$$$d$次元状態のサンプルのみを必要とする量子"Threshold Search"アルゴリズムを提供する。
また, $tildeO((log3 m)/epsilon2)$サンプルを用いた仮説選択法も提案する。
論文 参考訳(メタデータ) (2020-11-22T01:22:37Z) - The Sparse Hausdorff Moment Problem, with Application to Topic Models [5.151973524974052]
我々は$m=2k$iid二進確率変数のサンプルを用いて$k$-mixtureを同定するアルゴリズムを提案する。
加法精度$w_mincdotzetaO(k)$のモーメントを知るだけで十分である。
論文 参考訳(メタデータ) (2020-07-16T04:23:57Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳(メタデータ) (2020-07-07T17:10:00Z) - 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) - A Randomized Algorithm to Reduce the Support of Discrete Measures [79.55586575988292]
離散確率測度が$N$原子と$n$実数値関数の集合で成り立つと、元の$N$原子の$n+1$の部分集合で支えられる確率測度が存在する。
我々は、負の円錐によるバリセンターの簡単な幾何学的特徴付けを与え、この新しい測度を「グリード幾何学的サンプリング」によって計算するランダム化アルゴリズムを導出する。
次に、その性質を研究し、それを合成および実世界のデータにベンチマークして、$Ngg n$ regimeにおいて非常に有益であることを示す。
論文 参考訳(メタデータ) (2020-06-02T16:38:36Z) - Efficient active learning of sparse halfspaces with arbitrary bounded
noise [34.406103025985445]
我々は,同種$s$スパース半空間の非ラベルデータ分布が等方性対数凹であるような条件下で,$mathbbRd$におけるアクティブラーニングを研究する。
高レベルのラベルノイズの下では、計算効率のよいアルゴリズムによって達成されるラベルの複雑さ境界ははるかに悪化する。
これは、この設定で$frac11-2eta$にラベル複雑性を持つ最初の効率的なアルゴリズムである。
論文 参考訳(メタデータ) (2020-02-12T08:28:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。