Fugu-MT 論文翻訳(概要): Algorithms for Sparse LPN and LSPN Against Low-noise

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

arxiv url: http://arxiv.org/abs/2407.19215v8
Date: Mon, 02 Jun 2025 11:28:36 GMT
ステータス: 翻訳完了
システム内更新日: 2025-06-03 18:39:35.426755
Title: Algorithms for Sparse LPN and LSPN Against Low-noise
Title（参考訳）: 低雑音に対するスパースLPNとLSPNのアルゴリズム
Authors: Xue Chen, Wenxuan Shu, Zhaienhe Zhou,
Abstract要約: ランダムノイズ(LPN)問題を伴う古典的学習環境のスパース変種を考察する。我々の主な貢献は、LSPN(Learning Sparse Parities)問題とスパースCSP(SparseCSP)問題の両方に対して、低雑音に対する学習アルゴリズムを提供する新しいフレームワークである。
参考スコア（独自算出の注目度）: 1.2143710013809321
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We consider sparse variants of the classical Learning Parities with random Noise (LPN) problem. Our main contribution is a new algorithmic framework that provides learning algorithms against low-noise for both Learning Sparse Parities (LSPN) problem and sparse LPN problem. Different from previous approaches for LSPN and sparse LPN, this framework has a simple structure and runs in polynomial space. Let $n$ be the dimension, $k$ denote the sparsity, and $\eta$ be the noise rate. As a fundamental problem in computational learning theory, Learning Sparse Parities with Noise (LSPN) assumes the hidden parity is $k$-sparse. While a simple enumeration algorithm takes ${n \choose k}=O(n/k)^k$ time, previously known results stills need ${n \choose k/2} = \Omega(n/k)^{k/2}$ time for any noise rate $\eta$. Our framework provides a LSPN algorithm runs in time $O(\eta \cdot n/k)^k$ for any noise rate $\eta$, which improves the state-of-the-art of LSPN whenever $\eta \in ( k/n,\sqrt{k/n})$. The sparse LPN problem is closely related to the classical problem of refuting random $k$-CSP and has been widely used in cryptography as the hardness assumption. Different from the standard LPN, it samples random $k$-sparse vectors. Because the number of $k$-sparse vectors is ${n \choose k}<n^k$, sparse LPN has learning algorithms in polynomial time when $m>n^{k/2}$. However, much less is known about learning algorithms for constant $k$ like 3 and $m<n^{k/2}$ samples, except the Gaussian elimination algorithm of time $e^{\eta n}$. Our framework provides a learning algorithm in $e^{O(\eta \cdot n^{\frac{\delta+1}{2}})}$ time given $\delta \in (0,1)$ and $m \approx n^{1+(1-\delta)\cdot \frac{k-1}{2}}$ samples. This improves previous learning algorithms. For example, in the classical setting of $k=3$ and $m=n^{1.4}$, our algorithm would be faster than than previous approaches for any $\eta<n^{-0.7}$.
Abstract（参考訳）: ランダムノイズ(LPN)問題を伴う古典的学習環境のスパース変種を考察する。我々の主な貢献は、LSPN(Learning Sparse Parities)問題とスパースLPN(Learning Sparse Parities)問題の両方に対して、低雑音に対する学習アルゴリズムを提供する新しいアルゴリズムフレームワークである。 LSPNやスパースLPNの以前のアプローチとは異なり、このフレームワークは単純な構造を持ち、多項式空間で実行される。 n$ を次元とし、k$ を空間とし、$\eta$ を雑音率とする。計算学習理論の根本的な問題として、LSPN(Learning Sparse Parities with Noise)は、隠れたパリティが$k$-sparseであると仮定する。単純な列挙アルゴリズムは${n \choose k}=O(n/k)^k$timeを取るが、これまで知られていた結果は${n \choose k/2} = \Omega(n/k)^{k/2}$time for any noise rate $\eta$である。我々のフレームワークは、任意のノイズレート$\eta$に対して、時間$O(\eta \cdot n/k)^k$でLSPNアルゴリズムを実行し、$\eta \in (k/n,\sqrt{k/n})$のたびにLSPNの最先端性を改善する。スパースLPN問題は、ランダム$k$-CSPを論じる古典的な問題と密接に関連しており、暗号学においてハードネスの仮定として広く用いられている。標準のLPNとは異なり、ランダムな$k$-sparseベクトルをサンプリングする。 k$-スパースベクトルの数は${n \choose k}<n^k$であるため、スパースLPNは$m>n^{k/2}$の多項式時間で学習アルゴリズムを持つ。しかし、時間$e^{\eta n}$のガウス除去アルゴリズムを除いて、3 と $m<n^{k/2}$のサンプルに対する一定の$k$の学習アルゴリズムについてはあまり知られていない。我々のフレームワークは、$\delta \in (0,1)$と$m \approx n^{1+(1-\delta)\cdot \frac{k-1}{2}}$サンプルの学習アルゴリズムを$e^{O(\eta \cdot n^{\frac{\delta+1}{2}})} で提供する。これにより、従来の学習アルゴリズムが改善される。例えば、$k=3$と$m=n^{1.4}$の古典的な設定では、我々のアルゴリズムは任意の$\eta<n^{-0.7}$に対する以前のアプローチよりも高速である。

関連論文リスト

Improved Robust Estimation for Erdős-Rényi Graphs: The Sparse Regime and Optimal Breakdown Point [3.793609515750114]
我々は、ErdHos-R'enyiランダムグラフのエッジ密度を強く推定する問題を、$G(n, dcirc/n)$で検討する。我々のアルゴリズムは2乗の総和階層に基づいている。
論文参考訳（メタデータ） (2025-03-05T21:45:17Z)
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)
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)
Sketching Algorithms for Sparse Dictionary Learning: PTAS and Turnstile Streaming [48.18845814885398]
本研究は,スプリス辞書学習とユークリッド語$k$-meansクラスタリング問題に対するスケッチベースアプローチの適用性を高めるための新しい手法を開発した。高速アルゴリズムでは、$k$-meansクラスタリング問題に対してPTASを設計するための新しいアプローチを得る。ストリーミングアルゴリズムの分野では、辞書学習と$k$-meansクラスタリングのための新しい上限と下位境界を得る。
論文参考訳（メタデータ） (2023-10-29T16:46:26Z)
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)
Sparse PCA Beyond Covariance Thresholding [2.311583680973075]
すべての$t ll k$に対して、[gtrsim fracksqrtntsqrtln(2 + td/k2)$] さえあれば、この問題を解決するアルゴリズムがncdot dO(t)$で実行されていることを示す。スパース植込みベクター問題に対する時間アルゴリズムは,一部の制度における技術状況よりも高い保証が得られる。
論文参考訳（メタデータ） (2023-02-20T18:45:24Z)
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)
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)

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

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