論文の概要: Function Value Learning: Adaptive Learning Rates Based on the Polyak Stepsize and Function Splitting in ERM

• arxiv url: http://arxiv.org/abs/2307.14528v1
• Date: Wed, 26 Jul 2023 22:12:31 GMT
• ステータス: 処理完了
• システム内更新日: 2023-07-28 16:17:19.056643
• Title: Function Value Learning: Adaptive Learning Rates Based on the Polyak Stepsize and Function Splitting in ERM
• Title（参考訳）: 関数値学習:ermにおけるpolyakステップと関数分割に基づく適応学習率
• Authors: Guillaume Garrigos, Robert M. Gower, Fabian Schaipp
• Abstract要約: 我々は、経験的リスク最小化(experiical risk minimization)としても知られる有限項和問題に焦点をあてる。 最初に、サンプル損失値を利用する、$textttSPS_+$と呼ばれる理想化された適応メソッドを詳述する。 次に、最適な損失値が徐々に学習される$textttSPS_+$の変種である$textttFUVAL$を開発する。
• 参考スコア（独自算出の注目度）: 6.542289202349586
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Here we develop variants of SGD (stochastic gradient descent) with an adaptive step size that make use of the sampled loss values. In particular, we focus on solving a finite sum-of-terms problem, also known as empirical risk minimization. We first detail an idealized adaptive method called $\texttt{SPS}_+$ that makes use of the sampled loss values and assumes knowledge of the sampled loss at optimality. This $\texttt{SPS}_+$ is a minor modification of the SPS (Stochastic Polyak Stepsize) method, where the step size is enforced to be positive. We then show that $\texttt{SPS}_+$ achieves the best known rates of convergence for SGD in the Lipschitz non-smooth. We then move onto to develop $\texttt{FUVAL}$, a variant of $\texttt{SPS}_+$ where the loss values at optimality are gradually learned, as opposed to being given. We give three viewpoints of $\texttt{FUVAL}$, as a projection based method, as a variant of the prox-linear method, and then as a particular online SGD method. We then present a convergence analysis of $\texttt{FUVAL}$ and experimental results. The shortcomings of our work is that the convergence analysis of $\texttt{FUVAL}$ shows no advantage over SGD. Another shortcomming is that currently only the full batch version of $\texttt{FUVAL}$ shows a minor advantages of GD (Gradient Descent) in terms of sensitivity to the step size. The stochastic version shows no clear advantage over SGD. We conjecture that large mini-batches are required to make $\texttt{FUVAL}$ competitive. Currently the new $\texttt{FUVAL}$ method studied in this paper does not offer any clear theoretical or practical advantage. We have chosen to make this draft available online nonetheless because of some of the analysis techniques we use, such as the non-smooth analysis of $\texttt{SPS}_+$, and also to show an apparently interesting approach that currently does not work.
• Abstract（参考訳）: 本稿では,サンプル損失値を用いた適応ステップサイズのsgd(stochasticgradient descent)の変種を開発した。 特に、経験的リスク最小化(experiical risk minimization)として知られる有限項和問題に焦点をあてる。 まず、サンプル損失値を利用し、サンプル損失の知識を最適に仮定する、$\texttt{SPS}_+$と呼ばれる理想化された適応手法を詳述する。 この$\texttt{SPS}_+$は、ステップサイズを正に強制するSPS(Stochastic Polyak Stepsize)法の小さな修正である。 次に、$\texttt{SPS}_+$ がリプシッツ非滑らかな SGD の収束率の最もよく知られた値であることを示す。 次に、最適な損失値が与えられるのではなく、徐々に学習される$\textt{SPS}_+$の変種である$\textt{FUVAL}$を開発する。 プロジェクションベースメソッドとして$\texttt{fuval}$の3つの視点をprox-linearメソッドの変形として、そして特定のオンラインsgdメソッドとして与える。 次に、$\texttt{FUVAL}$の収束解析と実験結果を示す。 我々の研究の欠点は、$\texttt{FUVAL}$ の収束解析が SGD に勝るものではないことである。 もう一つのショートミームは、現在$\texttt{FUVAL}$のフルバッチバージョンのみが、ステップサイズに対する感度の点でGD(Gradient Descent)の小さな利点を示していることである。 確率版はsgdに対して明確な利点を示さない。 我々は、大きなミニバッチが$\texttt{FUVAL}$競争力を持つ必要があると推測する。 現在、この論文で研究されている新しい$\texttt{FUVAL}$メソッドは、明確な理論的または実用的な利点を提供していない。 それにもかかわらず、我々は、$\texttt{SPS}_+$の非滑らかな分析など、使用している分析手法のいくつかのために、このドラフトをオンラインで公開することにしました。

関連論文リスト

• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Two Sides of One Coin: the Limits of Untuned SGD and the Power of Adaptive Methods [22.052459124774504]
  本研究では,未調整のSGDに対する適応的手法により,スムーズさと情報優位性で問題を緩和することを示す。 この結果から, 指数関数依存性が欠如している場合, 未修正SGDに対する適応手法の理論的正当性について検討した。
  論文  参考訳（メタデータ） (2023-05-21T14:40:43Z)
• Lower Generalization Bounds for GD and SGD in Smooth Stochastic Convex Optimization [9.019243171993553]
  トレーニングステップ$T$とStep-size$eta$は、滑らかな凸最適化(SCO)問題の認定に影響を与える可能性がある。 まず、グラディエントDescent(GD)とグラディエントDescent(SGD)の厳密な過剰リスク低境界を提供する。 近年の作業は、より良い速度で達成できるが、トレーニング時間が長い場合には改善が減少する。
  論文  参考訳（メタデータ） (2023-03-19T20:24:33Z)
• Revisiting Weighted Strategy for Non-stationary Parametric Bandits [82.1942459195896]
  本稿では,非定常パラメトリックバンディットの重み付け戦略を再考する。 より単純な重みに基づくアルゴリズムを生成する改良された分析フレームワークを提案する。 我々の新しいフレームワークは、他のパラメトリックバンディットの後悔の限界を改善するのに使える。
  論文  参考訳（メタデータ） (2023-03-05T15:11:14Z)
• Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processes [62.90204655228324]
  我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。 我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
  論文  参考訳（メタデータ） (2022-10-20T21:32:01Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Sharper Rates and Flexible Framework for Nonconvex SGD with Client and Data Sampling [64.31011847952006]
  我々は、平均$n$スムーズでおそらくは非カラー関数のほぼ定常点を求める問題を再考する。 我々は$smallsfcolorgreen$を一般化し、事実上あらゆるサンプリングメカニズムで確実に動作するようにします。 我々は、スムーズな非カラー状態における最適境界の最も一般的な、最も正確な解析を提供する。
  論文  参考訳（メタデータ） (2022-06-05T21:32:33Z)
• A Variance-Reduced Stochastic Accelerated Primal Dual Algorithm [3.2958527541557525]
  このような問題は、堅牢な経験的リスク最小化という文脈で機械学習で頻繁に発生する。 高速化された原始双対 (SAPD) アルゴリズムは勾配雑音に対する頑健な手法であると考えている。 提案手法は,SAPDの実践と理論の両方において改善されていることを示す。
  論文  参考訳（メタデータ） (2022-02-19T22:12:30Z)
• What Happens after SGD Reaches Zero Loss? --A Mathematical Framework [35.31946061894308]
  SGD(Gradient Descent)の暗黙のバイアスを理解することは、ディープラーニングにおける重要な課題の1つである。 本稿では、Katzenberger (1991) のアイデアを適応させることにより、そのような分析の一般的な枠組みを提供する。 1) a global analysis of the implicit bias for $eta-2$ steps, not to the local analysis of Blanc et al. (2020) that is only for $eta-1.6$ steps and (2) allowing any noise covariance。
  論文  参考訳（メタデータ） (2021-10-13T17:50:46Z)
• Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning [52.76230802067506]
  漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。 提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。 初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
  論文  参考訳（メタデータ） (2021-10-09T21:13:48Z)

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

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