論文の概要: Practically Solving LPN in High Noise Regimes Faster Using Neural Networks

• arxiv url: http://arxiv.org/abs/2303.07987v1
• Date: Tue, 14 Mar 2023 15:44:20 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-15 14:35:28.154089
• Title: Practically Solving LPN in High Noise Regimes Faster Using Neural Networks
• Title（参考訳）: ニューラルネットワークによる高騒音レジームにおけるLPNの解法
• Authors: Haozhe Jiang, Kaiyue Wen, Yilei Chen
• Abstract要約: 我々は、2層ニューラルネットワークのファミリを設計し、高ノイズ、低次元のシステムにおいて古典的アルゴリズムを実質的に上回ります。 我々のアルゴリズムは、中大または大小のインスタンスを解くためのハイブリッドアルゴリズムにプラグインすることもできる。
• 参考スコア（独自算出の注目度）: 2.750124853532831
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We conduct a systematic study of solving the learning parity with noise problem (LPN) using neural networks. Our main contribution is designing families of two-layer neural networks that practically outperform classical algorithms in high-noise, low-dimension regimes. We consider three settings where the numbers of LPN samples are abundant, very limited, and in between. In each setting we provide neural network models that solve LPN as fast as possible. For some settings we are also able to provide theories that explain the rationale of the design of our models. Comparing with the previous experiments of Esser, Kubler, and May (CRYPTO 2017), for dimension $n = 26$, noise rate $\tau = 0.498$, the ''Guess-then-Gaussian-elimination'' algorithm takes 3.12 days on 64 CPU cores, whereas our neural network algorithm takes 66 minutes on 8 GPUs. Our algorithm can also be plugged into the hybrid algorithms for solving middle or large dimension LPN instances.
• Abstract（参考訳）: ニューラルネットワークを用いて,雑音問題(LPN)を用いた学習パリティの解法を系統的に検討する。 我々の主な貢献は、2層ニューラルネットワークのファミリを設計し、高ノイズ、低次元のシステムにおいて古典的アルゴリズムを実質的に上回ります。 LPNサンプルの数が豊富で、非常に限られている3つの設定について検討する。 それぞれの設定で、できるだけ早くlpnを解くニューラルネットワークモデルを提供します。 いくつかの設定では、モデルの設計の合理性を説明する理論を提供することもできます。 Esser、Kubler、May(CRYPTO 2017)の以前の実験と比較すると、次元$n = 26$、ノイズレート$\tau = 0.498$、'Guess-then-Gaussian-elimination'アルゴリズムは64CPUコアで3.12日かかり、ニューラルネットワークアルゴリズムは8GPUで66分かかる。 我々のアルゴリズムは、中または大次元のLPNインスタンスを解くためのハイブリッドアルゴリズムにプラグインすることもできる。

関連論文リスト

• LinSATNet: The Positive Linear Satisfiability Neural Networks [116.65291739666303]
  本稿では,ニューラルネットワークに人気の高い正の線形満足度を導入する方法について検討する。 本稿では,古典的なシンクホーンアルゴリズムを拡張し,複数の辺分布の集合を共同で符号化する,最初の微分可能満足層を提案する。
  論文  参考訳（メタデータ） (2024-07-18T22:05:21Z)
• On Statistical Learning of Branch and Bound for Vehicle Routing Optimization [3.6922704509753084]
  我々は,計算コストの高いStrong Branching戦略の決定過程をエミュレートするためにニューラルネットワークを訓練する。 このアプローチは分岐とバウンドのアルゴリズムの性能にマッチするか、改善することができる。
  論文  参考訳（メタデータ） (2023-10-15T23:59:57Z)
• Latent Space Representations of Neural Algorithmic Reasoners [15.920449080528536]
  アルゴリズムの実行時にGNNによって誘導される潜伏空間の構造を詳細に解析する。 i) 分解能の喪失、(i) 類似した値の識別が困難、(ii) トレーニング中に観察された範囲外の値を扱うことができない、という2つの可能な障害モードを特定します。 これらの変更は、最先端のTriplet-GMPNNプロセッサを使用する場合、CLRS-30ベンチマークのアルゴリズムの大部分の改善につながることを示す。
  論文  参考訳（メタデータ） (2023-07-17T22:09:12Z)
• The Clock and the Pizza: Two Stories in Mechanistic Explanation of Neural Networks [59.26515696183751]
  ニューラルネットワークにおけるアルゴリズム発見は、時としてより複雑であることを示す。 単純な学習問題でさえ、驚くほど多様なソリューションを許容できることが示されています。
  論文  参考訳（メタデータ） (2023-06-30T17:59:13Z)
• Towards Better Out-of-Distribution Generalization of Neural Algorithmic Reasoning Tasks [51.8723187709964]
  ニューラルネットワーク推論タスクのOOD一般化について検討する。 目標は、ディープニューラルネットワークを使用して入出力ペアからアルゴリズムを学ぶことである。
  論文  参考訳（メタデータ） (2022-11-01T18:33:20Z)
• Algorithms for Efficiently Learning Low-Rank Neural Networks [12.916132936159713]
  低ランクニューラルネットワークの学習アルゴリズムについて検討する。 単層ReLUネットワークに最適な低ランク近似を学習するアルゴリズムを提案する。 低ランク$textitdeep$ネットワークをトレーニングするための新しい低ランクフレームワークを提案する。
  論文  参考訳（メタデータ） (2022-02-02T01:08:29Z)
• Revisiting Recursive Least Squares for Training Deep Neural Networks [10.44340837533087]
  再帰最小二乗法(RLS)アルゴリズムは、その高速収束のため、かつては小規模ニューラルネットワークのトレーニングに広く用いられていた。 従来のRSSアルゴリズムは、計算複雑性が高く、事前条件が多すぎるため、ディープニューラルネットワーク(DNN)のトレーニングには適さない。 本稿では,フィードフォワードニューラルネットワーク,畳み込みニューラルネットワーク,リカレントニューラルネットワークの3つの新しいRSS最適化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-09-07T17:43:51Z)
• A quantum algorithm for training wide and deep classical neural networks [72.2614468437919]
  勾配勾配勾配による古典的トレーサビリティに寄与する条件は、量子線形系を効率的に解くために必要な条件と一致することを示す。 MNIST画像データセットがそのような条件を満たすことを数値的に示す。 我々は、プールを用いた畳み込みニューラルネットワークのトレーニングに$O(log n)$の実証的証拠を提供する。
  論文  参考訳（メタデータ） (2021-07-19T23:41:03Z)
• Waypoint Planning Networks [66.72790309889432]
  本稿では,ローカルカーネル(A*のような古典的アルゴリズム)と学習アルゴリズムを用いたグローバルカーネルを用いたLSTMに基づくハイブリッドアルゴリズムを提案する。 我々は、WPNとA*を比較し、動き計画ネットワーク(MPNet)やバリューネットワーク(VIN)を含む関連する作業と比較する。 WPN の探索空間は A* よりもかなり小さいが、ほぼ最適な結果が得られることが示されている。
  論文  参考訳（メタデータ） (2021-05-01T18:02:01Z)
• Neural Thompson Sampling [94.82847209157494]
  本稿では,ニューラルトンプソンサンプリング(Neural Thompson Smpling)と呼ばれる新しいアルゴリズムを提案する。 我々のアルゴリズムの中核は報酬の新たな後部分布であり、その平均はニューラルネットワーク近似器であり、その分散は対応するニューラルネットワークのニューラル・タンジェントな特徴に基づいて構築されている。
  論文  参考訳（メタデータ） (2020-10-02T07:44:09Z)

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

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