論文の概要: Algorithms for Sparse LPN and LSPN Against Low-noise

• arxiv url: http://arxiv.org/abs/2407.19215v5
• Date: Thu, 28 Nov 2024 15:39:41 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-02 15:14:45.983961
• Title: Algorithms for Sparse LPN and LSPN Against Low-noise
• Title（参考訳）: 低雑音に対するスパースLPNとLSPNのアルゴリズム
• Authors: Xue Chen, Wenxuan Shu, Zhaienhe Zhou,
• Abstract要約: ノイズ問題を伴う古典的学習パリティの2種類のスパース変種に対する学習アルゴリズムについて検討した。 我々は,幅広いパラメータに対する技術状況を改善するための新しいアルゴリズムフレームワークを提供する。
• 参考スコア（独自算出の注目度）: 1.2143710013809321
• License:
• Abstract: We study learning algorithms for two sparse variants of the classical learning parity with noise (LPN) problem. We provide a new algorithmic framework that improves the state of the art for a wide range of parameters. This framework has a simple structure different from previous approaches: the first step is a domain reduction via the knowledge of sparsity; then it solves sub-problems by Gaussian elimination. Let $n$ be the dimension, $k$ be the sparsity parameter, and $\eta$ be the noise rate such that each label gets flipped with probability $\eta$. The learning sparse parity with noise (LSPN) problem assumes the hidden parity is $k$-sparse. LSPN has been extensively studied in both learning theory and cryptography. However, the state of the art needs ${n \choose k/2} = \Omega(n/k)^{k/2}$ time for a wide range of parameters while the simple enumeration algorithm takes ${n \choose k}=O(n/k)^k$ time. Our LSPN algorithm runs in time $O(\eta \cdot n/k)^k$ for any $\eta$ and $k$. This improves the state-of-the-art for learning sparse parity in a wide range of parameters. The sparse LPN problem (with various parameters) has wide applications in cryptography. We present a distinguishing algorithm for sparse LPN with time complexity $e^{O(\eta \cdot n^{\frac{1+\delta}{2}})}$ and sample complexity $m=n^{1+(\frac{k-1}{2})(1-\delta)}$. Furthermore, we show a learning algorithm for sparse LPN in time complexity $e^{\tilde{O}(\eta \cdot n^{\frac{1+\delta}{2}})}$ and $m=\max\{1,\frac{\eta \cdot n^{\frac{1+\delta}{2}}}{k^2}\} \cdot \tilde{O}(n)^{1+(\frac{k-1}{2})(1-\delta)}$ samples. Since all these algorithm are based on one algorithmic framework, our conceptual contribution is a connection between sparse LPN and LSPN.
• Abstract（参考訳）: 本研究では,古典的学習パリティ(LPN)問題の2つのスパース変種に対する学習アルゴリズムについて検討した。 我々は、幅広いパラメータの最先端性を改善する新しいアルゴリズムフレームワークを提供する。 このフレームワークは、従来のアプローチと異なる単純な構造を持ち、最初のステップはスパーシティの知識によるドメインの縮小であり、ガウスの除去によるサブプロブレムの解決である。 n$ を次元とし、$k$ を空間パラメータとし、$\eta$ をノイズレートとし、各ラベルが確率$\eta$ で反転する。 ノイズによる学習スパースパリティ(LSPN)問題は、隠れパリティが$k$スパースであると仮定する。 LSPNは学習理論と暗号の両方で広く研究されている。 しかし、最先端技術は、幅広いパラメータに対して${n \choose k/2} = \Omega(n/k)^{k/2}$時間を必要とし、単純な列挙アルゴリズムは${n \choose k}=O(n/k)^k$時間を必要とする。 LSPNアルゴリズムは、任意の$\eta$と$k$に対して、時間$O(\eta \cdot n/k)^k$で実行される。 これにより、幅広いパラメータでスパースパリティを学習するための最先端技術が改善される。 スパースLPN問題(様々なパラメータを持つ)は、暗号に広く応用されている。 時間複雑性$e^{O(\eta \cdot n^{\frac{1+\delta}{2}})}$とサンプル複雑性$m=n^{1+(\frac{k-1}{2})(1-\delta)}$のスパースLPNの判別アルゴリズムを提案する。 さらに, 時間複雑性$e^{\tilde{O}(\eta \cdot n^{\frac{1+\delta}{2}})}$および$m=\max\{1,\frac{\eta \cdot n^{\frac{1+\delta}{2}}}{k^2}\} \cdot \tilde{O}(n)^{1+(\frac{k-1}{2})(1-\delta)}$サンプルにおけるスパースLPNの学習アルゴリズムを示す。 これらのアルゴリズムは1つのアルゴリズムフレームワークに基づいているため、我々の概念的貢献はスパースLPNとLSPNの接続である。

関連論文リスト

• 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)

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

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