論文の概要: 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)$に対して最先端のバウンドを与える。

関連論文リスト

• A Near-optimal Algorithm for Learning Margin Halfspaces with Massart Noise [36.29182619215646]
  我々は、マスアートノイズの存在下で、PACが$gamma$-marginハーフスペースを学習する際の問題について検討する。 我々のアルゴリズムは単純で実用的であり、慎重に選択された凸損失の列にオンラインSGDを頼っている。
  論文  参考訳（メタデータ） (2025-01-16T17:44:18Z)
• Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Models [39.33814194788341]
  潜在変数モデル学習の課題について検討する。 このような応用により、暗黙のモーメント計算のための一般化されたアルゴリズムを開発した。 一般的なアルゴリズムを利用して, 以下のモデルに対する初等学習者を得る。
  論文  参考訳（メタデータ） (2024-11-23T23:13:24Z)
• Faster Private Minimum Spanning Trees [11.72102598708538]
  本稿では,時間内で動作中の既存手法の実用性に適合する新しい差分プライベートMSTアルゴリズムを提案する。 我々は,少なくとも$O(n2)$カットエッジを$O(sqrtn log n)$ timeでサンプリングすることのできるデータ構造を示す。
  論文  参考訳（メタデータ） (2024-08-13T16:00:30Z)
• A Sub-Quadratic Time Algorithm for Robust Sparse Mean Estimation [6.853165736531941]
  逆数外乱の存在下でのスパース平均推定のアルゴリズム的問題について検討する。 我々の主な貢献は、$mathrmpoly(k,log d,1/epsilon)$サンプルを用いて、エフェサブクアクラティック時間で実行される頑健なスパース平均推定アルゴリズムである。
  論文  参考訳（メタデータ） (2024-03-07T18:23:51Z)
• Do you know what q-means? [50.045011844765185]
  クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。 クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。 また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
  論文  参考訳（メタデータ） (2023-08-18T17:52:12Z)
• 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)
• Most Neural Networks Are Almost Learnable [52.40331776572531]
  固定された$epsilon>0$とdeep $i$に対して、深さ$i$のランダムなXavierネットワークを学習するポリ時間アルゴリズムが存在することを示す。 このアルゴリズムは時間とサンプルの複雑さが$(bard)mathrmpoly(epsilon-1)$であり、$bar d$はネットワークのサイズである。 シグモイドやReLU様の活性化の場合、境界は$(bard)mathrmpolylog(eps)に改善できる。
  論文  参考訳（メタデータ） (2023-05-25T22:27:42Z)
• 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)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)

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

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