論文の概要: Intractability of Learning the Discrete Logarithm with Gradient-Based Methods

• arxiv url: http://arxiv.org/abs/2310.01611v1
• Date: Mon, 2 Oct 2023 20:01:12 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-04 18:56:53.809865
• Title: Intractability of Learning the Discrete Logarithm with Gradient-Based Methods
• Title（参考訳）: 勾配法に基づく離散対数学習の難易度
• Authors: Rustem Takhanov, Maxat Tezekbayev, Artur Pak, Arman Bolatov, Zhibek Kadyrsizova, Zhenisbek Assylbekov
• Abstract要約: 次数有限巡回群における離散対数のパリティビットを学習するための勾配に基づく手法の限界について検討する。 この濃度特性は勾配法を用いてパリティビットを効率的に学習する能力に制限を与える。 ニューラルネットワークベースのアプローチを用いた実証実験は、勾配に基づく学習の限界をさらに検証する。
• 参考スコア（独自算出の注目度）: 8.813846754606898
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The discrete logarithm problem is a fundamental challenge in number theory with significant implications for cryptographic protocols. In this paper, we investigate the limitations of gradient-based methods for learning the parity bit of the discrete logarithm in finite cyclic groups of prime order. Our main result, supported by theoretical analysis and empirical verification, reveals the concentration of the gradient of the loss function around a fixed point, independent of the logarithm's base used. This concentration property leads to a restricted ability to learn the parity bit efficiently using gradient-based methods, irrespective of the complexity of the network architecture being trained. Our proof relies on Boas-Bellman inequality in inner product spaces and it involves establishing approximate orthogonality of discrete logarithm's parity bit functions through the spectral norm of certain matrices. Empirical experiments using a neural network-based approach further verify the limitations of gradient-based learning, demonstrating the decreasing success rate in predicting the parity bit as the group order increases.
• Abstract（参考訳）: 離散対数問題は、暗号プロトコルに重要な意味を持つ数論における根本的な問題である。 本稿では,次数有限巡回群における離散対数のパリティビットを学習するための勾配に基づく手法の限界について検討する。 本研究の主な成果は, 理論解析と実証的検証によって支えられ, 対数基底とは独立に, 一定点付近の損失関数の勾配が集中していることが判明した。 この濃度特性は、トレーニングされるネットワークアーキテクチャの複雑さに関係なく、勾配に基づく手法を用いてパリティビットを効率的に学習する能力を制限する。 我々の証明は内積空間におけるボアス=ベルマンの不等式に依存しており、ある行列のスペクトルノルムを通して離散対数のパリティビット函数の近似直交性を確立する。 ニューラルネットワークベースのアプローチを用いた実証実験は、勾配に基づく学習の限界をさらに検証し、グループの順序が増加するにつれてパリティビットを予測する成功率の低下を示す。

関連論文リスト

• Taming Score-Based Diffusion Priors for Infinite-Dimensional Nonlinear Inverse Problems [4.42498215122234]
  本研究では,関数空間におけるベイズ逆問題の解法を提案する。 可能性の対数共空性は仮定せず、非線型逆問題と互換性がある。 従来の正規化法で確立された固定点法に着想を得た新しい収束解析を行う。
  論文  参考訳（メタデータ） (2024-05-24T16:17:01Z)
• Learning Discretized Neural Networks under Ricci Flow [51.36292559262042]
  低精度重みとアクティベーションからなる離散ニューラルネットワーク(DNN)について検討する。 DNNは、訓練中に微分不可能な離散関数のために無限あるいはゼロの勾配に悩まされる。
  論文  参考訳（メタデータ） (2023-02-07T10:51:53Z)
• Convergence analysis of unsupervised Legendre-Galerkin neural networks for linear second-order elliptic PDEs [0.8594140167290099]
  教師なしレジェンダ-ガレルキンニューラルネットワーク(ULGNet)の収束解析を行う。 ULGNetは偏微分方程式(PDE)を解くためのディープラーニングに基づく数値法である
  論文  参考訳（メタデータ） (2022-11-16T13:31:03Z)
• Efficient and Near-Optimal Smoothed Online Learning for Generalized Linear Functions [28.30744223973527]
  我々は,K-wise線形分類において,統計学的に最適なログ(T/sigma)の後悔を初めて楽しむ計算効率のよいアルゴリズムを提案する。 一般化線形分類器によって誘導される不一致領域の幾何学の新たな特徴付けを開発する。
  論文  参考訳（メタデータ） (2022-05-25T21:31:36Z)
• On the Benefits of Large Learning Rates for Kernel Methods [110.03020563291788]
  本稿では,カーネル手法のコンテキストにおいて,現象を正確に特徴付けることができることを示す。 分離可能なヒルベルト空間における2次対象の最小化を考慮し、早期停止の場合、学習速度の選択が得られた解のスペクトル分解に影響を及ぼすことを示す。
  論文  参考訳（メタデータ） (2022-02-28T13:01:04Z)
• Learning Frequency Domain Approximation for Binary Neural Networks [68.79904499480025]
  フーリエ周波数領域における符号関数の勾配を正弦関数の組み合わせを用いて推定し,BNNの訓練を行う。 いくつかのベンチマークデータセットとニューラルネットワークの実験により、この手法で学習したバイナリネットワークが最先端の精度を達成することが示されている。
  論文  参考訳（メタデータ） (2021-03-01T08:25:26Z)
• Behavior of linear L2-boosting algorithms in the vanishing learning rate asymptotic [0.0]
  学習速度が0に収束し、繰り返し回数が再スケールされるとき、勾配向上アルゴリズムの挙動について検討する。 消滅する学習速度の限界を証明し、無限次元関数空間における線形微分方程式のユニークな解として限界を特徴づける。
  論文  参考訳（メタデータ） (2020-12-29T08:37:54Z)
• On the Iteration Complexity of Hypergradient Computation [38.409444179509705]
  機械学習では、上層目標(過度)の勾配は、正確に計算するのは難しいか、あるいは不可能である。 逆モード反復微分と近似的暗黙的微分に基づく過次微分を計算するための一般的なアプローチについて検討する。 この分析は, 共役勾配に基づく近似的暗黙差を最良とする, 上記の手法の計算効率の階層性を示す。
  論文  参考訳（メタデータ） (2020-06-29T17:32:47Z)
• Multipole Graph Neural Operator for Parametric Partial Differential Equations [57.90284928158383]
  物理系をシミュレーションするためのディープラーニングベースの手法を使用する際の大きな課題の1つは、物理ベースのデータの定式化である。 線形複雑度のみを用いて、あらゆる範囲の相互作用をキャプチャする、新しいマルチレベルグラフニューラルネットワークフレームワークを提案する。 実験により, 離散化不変解演算子をPDEに学習し, 線形時間で評価できることを確認した。
  論文  参考訳（メタデータ） (2020-06-16T21:56:22Z)
• Interpolation Technique to Speed Up Gradients Propagation in Neural ODEs [71.26657499537366]
  本稿では,ニューラルネットワークモデルにおける勾配の効率的な近似法を提案する。 我々は、分類、密度推定、推論近似タスクにおいて、ニューラルODEをトレーニングするリバースダイナミック手法と比較する。
  論文  参考訳（メタデータ） (2020-03-11T13:15:57Z)
• Semiparametric Nonlinear Bipartite Graph Representation Learning with Provable Guarantees [106.91654068632882]
  半パラメトリック指数族分布におけるパラメータの統計的推定問題として、両部グラフを考察し、その表現学習問題を定式化する。 提案手法は, 地中真理付近で強い凸性を示すため, 勾配降下法が線形収束率を達成できることを示す。 我々の推定器は指数族内の任意のモデル誤特定に対して頑健であり、広範な実験で検証されている。
  論文  参考訳（メタデータ） (2020-03-02T16:40:36Z)

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

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