論文の概要: Tighter Lower Bounds for Shuffling SGD: Random Permutations and Beyond

• arxiv url: http://arxiv.org/abs/2303.07160v1
• Date: Mon, 13 Mar 2023 14:35:55 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-14 14:22:10.240424
• Title: Tighter Lower Bounds for Shuffling SGD: Random Permutations and Beyond
• Title（参考訳）: SGDをシャッフルするためのより低い境界:ランダムな置換とそれを超える
• Authors: Jaeyoung Cha, Jaewook Lee, Chulhee Yun
• Abstract要約: 有限サム最小化問題を解くための勾配勾配勾配勾配(SGD)について述べる。 Random Reshuffling の場合、既存の境界よりも$kappa$ がより狭い境界が見つかる。
• 参考スコア（独自算出の注目度）: 18.176606453818557
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study convergence lower bounds of without-replacement stochastic gradient descent (SGD) for solving smooth (strongly-)convex finite-sum minimization problems. Unlike most existing results focusing on final iterate lower bounds in terms of the number of components $n$ and the number of epochs $K$, we seek bounds for arbitrary weighted average iterates that are tight in all factors including the condition number $\kappa$. For SGD with Random Reshuffling, we present lower bounds that have tighter $\kappa$ dependencies than existing bounds. Our results are the first to perfectly close the gap between lower and upper bounds for weighted average iterates in both strongly-convex and convex cases. We also prove weighted average iterate lower bounds for arbitrary permutation-based SGD, which apply to all variants that carefully choose the best permutation. Our bounds improve the existing bounds in factors of $n$ and $\kappa$ and thereby match the upper bounds shown for a recently proposed algorithm called GraB.
• Abstract（参考訳）: 非置換確率勾配勾配勾配(SGD)の収束下界を滑らかな(強い-)凸有限サム最小化問題の解法として検討する。 成分数$n$とエポック数$K$という観点で最終反復下界に焦点を絞った既存の結果とは異なり、条件数$\kappa$を含むすべての因子において厳密な任意の重み付き平均的反復に対する境界を求める。 Random Reshuffling を持つ SGD の場合、既存の境界よりもより強い$\kappa$ 依存を持つ低い境界を示す。 その結果, 強凸と凸のいずれにおいても, 重み付き平均イテレートに対する下界と上界のギャップを完全に閉じることができた。 また、重み付け平均は任意の置換ベースのsgdに対して下限を反復し、最良の置換を慎重に選択する全ての変種に適用する。 我々の境界は、$n$と$\kappa$の因子の既存の境界を改善し、その結果、最近提案されたGraBアルゴリズムで示される上限と一致する。

関連論文リスト

• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Revisiting the Last-Iterate Convergence of Stochastic Gradient Methods [25.831462008050387]
  グラディエント・Descent(SGD)アルゴリズムは、実際の性能が良く、理論的な理解が欠如していることから、人々の関心を喚起している。 有限収束がより広い合成最適化や非ユークリッドノルムに証明可能な拡張が可能かどうかはまだ不明である。
  論文  参考訳（メタデータ） (2023-12-13T21:41:06Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• Gaussian Process Bandit Optimization with Few Batches [49.896920704012395]
  有限腕バンディットアルゴリズムにインスパイアされたバッチアルゴリズムを導入する。 O(log T)$ batches in time horizon $T$.sqrtTgamma_T)$ using $O(log T)$ batches in time horizon。 さらに,アルゴリズムの修正版を提案し,バッチ数によって後悔がどう影響するかを特徴付ける。
  論文  参考訳（メタデータ） (2021-10-15T00:54:04Z)
• The Convergence Rate of SGD's Final Iterate: Analysis on Dimension Dependence [2.512827436728378]
  Gradient Descent (SGD) は最適化において最も単純で一般的な手法の一つである。 定次元設定におけるSGDの最終点収束を特徴付ける方法を示す。
  論文  参考訳（メタデータ） (2021-06-28T11:51:04Z)
• The Complexity of Nonconvex-Strongly-Concave Minimax Optimization [43.07732143522183]
  本稿では,非強凹型(nc-sc)滑らかなミニマックス問題の近似定常点を求めるための複雑さを確立する。 提案された$Omega-strong$lyconcaveサブ2問題を一般複雑性と平均複雑性の両方で展開する。 提案する有限和設定では,提案するアルゴリズムは条件数にほぼ依存している。
  論文  参考訳（メタデータ） (2021-03-29T18:53:57Z)
• ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
  第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。 我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。 有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
  論文  参考訳（メタデータ） (2020-08-28T14:46:56Z)
• Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations [54.42518331209581]
  私たちは発見するアルゴリズムを見つけます。 epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using $(epsilon,gamma)$surimateランダムランダムポイント。 ここでの私たちの下限は、ノイズのないケースでも新規です。
  論文  参考訳（メタデータ） (2020-06-24T04:41:43Z)
• SGD with shuffling: optimal rates without component convexity and large epoch requirements [60.65928290219793]
  我々はRandomShuffle(各エポックの開始時のシャッフル)とSingleShuffle(1回だけシャッフル)を考える。 我々はこれらのアルゴリズムの最小収束速度をポリログ係数ギャップまで確立する。 我々は、すべての先行芸術に共通する欠点を取り除くことにより、RandomShuffleの厳密な収束結果をさらに強化する。
  論文  参考訳（メタデータ） (2020-06-12T05:00:44Z)

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

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