論文の概要: Algorithms for Sparse LPN and LSPN Against Low-noise
- arxiv url: http://arxiv.org/abs/2407.19215v2
- Date: Wed, 02 Oct 2024 07:36:29 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-10-03 15:16:22.746559
- 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:
- 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$で実行される。
これにより、幅広いパラメータでスパースパリティを学習するための最先端技術が改善される。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。