論文の概要: Gradient Descent Fails to Learn High-frequency Functions and Modular Arithmetic

• arxiv url: http://arxiv.org/abs/2310.12660v2
• Date: Thu, 29 Aug 2024 09:58:47 GMT
• ステータス: 処理完了
• システム内更新日: 2024-08-30 19:38:30.292889
• Title: Gradient Descent Fails to Learn High-frequency Functions and Modular Arithmetic
• Title（参考訳）: 高周波関数とモジュラー算術を学習するグラディエントDescent Fails
• Authors: Rustem Takhanov, Maxat Tezekbayev, Artur Pak, Arman Bolatov, Zhenisbek Assylbekov,
• Abstract要約: 本稿では,勾配に基づく学習手法を用いて,限界と課題の数学的解析を行う。 我々は、周波数または素基底$p$が大きい場合、両方の場合において勾配のばらつきが無視できるほど小さいことを強調する。
• 参考スコア（独自算出の注目度）: 8.813846754606898
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Classes of target functions containing a large number of approximately orthogonal elements are known to be hard to learn by the Statistical Query algorithms. Recently this classical fact re-emerged in a theory of gradient-based optimization of neural networks. In the novel framework, the hardness of a class is usually quantified by the variance of the gradient with respect to a random choice of a target function. A set of functions of the form $x\to ax \bmod p$, where $a$ is taken from ${\mathbb Z}_p$, has attracted some attention from deep learning theorists and cryptographers recently. This class can be understood as a subset of $p$-periodic functions on ${\mathbb Z}$ and is tightly connected with a class of high-frequency periodic functions on the real line. We present a mathematical analysis of limitations and challenges associated with using gradient-based learning techniques to train a high-frequency periodic function or modular multiplication from examples. We highlight that the variance of the gradient is negligibly small in both cases when either a frequency or the prime base $p$ is large. This in turn prevents such a learning algorithm from being successful.
• Abstract（参考訳）: 近似直交要素を多数含む対象関数のクラスは、統計的クエリーアルゴリズムによって学習することが難しいことが知られている。 この古典的な事実は、ニューラルネットワークの勾配に基づく最適化の理論に再燃した。 新たな枠組みでは、クラスの硬さは、通常、対象関数のランダムな選択に対する勾配の分散によって定量化される。 x\to ax \bmod p$($a$は${\mathbb Z}_p$から取られる)という形の関数の集合は、最近ディープラーニング理論家や暗号学者から注目を集めている。 このクラスは${\mathbb Z}$上の$p$-周期関数の部分集合として理解することができ、実数直線上の高周波周期関数のクラスと密接に結びついている。 本稿では、勾配に基づく学習技術を用いて高頻度周期関数やモジュラ乗法を例から学習する際の限界と課題を数学的に解析する。 我々は、周波数または素基底$p$が大きい場合、両方の場合において勾配のばらつきが無視できるほど小さいことを強調する。 これにより、そのような学習アルゴリズムが成功するのを防ぐことができる。

関連論文リスト

• Learning sum of diverse features: computational hardness and efficient gradient-based training for ridge combinations [40.77319247558742]
  目的関数 $f_*:mathbbRdtomathbbR$ を加法構造で学習する際の計算複雑性について検討する。 2層ニューラルネットワークの勾配学習により,$f_*$の大規模なサブセットを効率的に学習できることを実証した。
  論文  参考訳（メタデータ） (2024-06-17T17:59:17Z)
• Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit [75.4661041626338]
  単一インデックス対象関数 $f_*(boldsymbolx) = textstylesigma_*left(langleboldsymbolx,boldsymbolthetarangleright)$ の等方的ガウスデータの下で勾配降下学習の問題を考察する。 SGDアルゴリズムで最適化された2層ニューラルネットワークは、サンプル付き任意のリンク関数の$f_*$を学習し、実行時の複雑さは$n asymp T asymp C(q) cdot dであることを示す。
  論文  参考訳（メタデータ） (2024-06-03T17:56:58Z)
• 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)
• Randomized Exploration for Reinforcement Learning with General Value Function Approximation [122.70803181751135]
  本稿では,ランダム化最小二乗値反復(RLSVI)アルゴリズムに着想を得たモデルレス強化学習アルゴリズムを提案する。 提案アルゴリズムは,スカラーノイズを用いたトレーニングデータを簡易に摂動させることにより,探索を促進する。 我々はこの理論を、既知の困難な探査課題にまたがる実証的な評価で補完する。
  論文  参考訳（メタデータ） (2021-06-15T02:23:07Z)
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
  強化学習のコアにおける探索・探索トレードオフについて検討する。 特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。 私たちの後悔の限界はエピソードの数とは無関係です。
  論文  参考訳（メタデータ） (2020-11-09T18:32:22Z)
• Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
  非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。 特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
  論文  参考訳（メタデータ） (2020-02-10T23:23:04Z)
• Backward Feature Correction: How Deep Learning Performs Deep (Hierarchical) Learning [66.05472746340142]
  本稿では,SGD による階層的学習 _efficiently_ と _automatically_ を学習目標として,多層ニューラルネットワークがどのように行うかを分析する。 我々は、下位機能のエラーを上位層と共にトレーニングする際に自動的に修正できる"後方特徴補正"と呼ばれる新しい原則を確立する。
  論文  参考訳（メタデータ） (2020-01-13T17:28:29Z)

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

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