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

• arxiv url: http://arxiv.org/abs/2407.19215v3
• Date: Fri, 4 Oct 2024 23:06:19 GMT
• ステータス: 処理完了
• システム内更新日: 2024-11-08 14:38:53.647772
• Title: Algorithms for Sparse LPN and LSPN Against Low-noise
• Title（参考訳）: 低雑音に対するスパースLPNとLSPNのアルゴリズム
• Authors: Xue Chen, Wenxuan Shu, Zhaienhe Zhou,
• Abstract要約: 本研究では,古典的学習パリティ(LPN)問題の2つの変種に対する学習アルゴリズムについて検討する。 我々は,幅広いパラメータに対する技術状況を改善するための新しいアルゴリズムフレームワークを提供する。
• 参考スコア（独自算出の注目度）: 1.2143710013809321
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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 sparse LPN problem (with various parameters) has wide applications in cryptography. Different from the standard LPN problem that samples random vectors in $\mathbf{F}_2^n$, it samples random $k$-sparse vectors. The birthday paradox implies a trivial distinguishing algorithm given $m=n^{k/2}$ samples. For $m=n^{1+(\frac{k}{2}-1)(1-\delta)}$ with $\delta \in (0,1)$, the best known algorithm has running time $\min\{e^{\eta n}, e^{\tilde{O}(n^{\delta})}\}$. We present a learning algorithm for sparse LPN with time complexity $e^{\tilde{O}(\eta \cdot n^{\frac{1+\delta}{2}})}$ and sample complexity $m=\max\{1,\frac{\eta \cdot n^{\frac{1+\delta}{2}}}{k^2}\} \cdot \tilde{O}(n)^{1+(\frac{k-1}{2})(1-\delta)}$. It improves previous results for any constant or super-constant $k$ with a wide range of $\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.
• Abstract（参考訳）: 本研究では,古典的学習パリティ(LPN)問題の2つのスパース変種に対する学習アルゴリズムについて検討した。 我々は、幅広いパラメータの最先端性を改善する新しいアルゴリズムフレームワークを提供する。 このフレームワークは、従来のアプローチと異なる単純な構造を持ち、最初のステップはスパーシティの知識によるドメインの縮小であり、ガウスの除去によるサブプロブレムの解決である。 n$ を次元とし、$k$ を空間パラメータとし、$\eta$ をノイズレートとし、各ラベルが確率$\eta$ で反転する。 スパースLPN問題(様々なパラメータを持つ)は、暗号に広く応用されている。 標準のLPN問題とは異なり、$\mathbf{F}_2^n$のランダムベクトルをサンプリングし、ランダムな$k$スパースベクトルをサンプリングする。 誕生日パラドックスは、$m=n^{k/2}$サンプルを与えられた自明な区別アルゴリズムを意味する。 m=n^{1+(\frac{k}{2}-1)(1-\delta)}$と$\delta \in (0,1)$の場合、最もよく知られているアルゴリズムは実行時間$\min\{e^{\eta n}, e^{\tilde{O}(n^{\delta})}\}$である。 時間複雑性$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の学習アルゴリズムを提案する。 これは、より広い範囲の$\eta$を持つ任意の定数または超定数$k$に対する以前の結果を改善する。 ノイズによる学習スパースパリティ(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$で実行される。 これにより、幅広いパラメータでスパースパリティを学習するための最先端技術が改善される。

関連論文リスト

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

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

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