論文の概要: SGD with shuffling: optimal rates without component convexity and large epoch requirements

• arxiv url: http://arxiv.org/abs/2006.06946v2
• Date: Mon, 22 Jun 2020 03:42:32 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-22 04:37:49.499344
• Title: SGD with shuffling: optimal rates without component convexity and large epoch requirements
• Title（参考訳）: シャッフルを伴うSGD:成分の凸性のない最適速度と大きなエポック要件
• Authors: Kwangjun Ahn, Chulhee Yun, Suvrit Sra
• Abstract要約: 我々はRandomShuffle(各エポックの開始時のシャッフル)とSingleShuffle(1回だけシャッフル)を考える。 我々はこれらのアルゴリズムの最小収束速度をポリログ係数ギャップまで確立する。 我々は、すべての先行芸術に共通する欠点を取り除くことにより、RandomShuffleの厳密な収束結果をさらに強化する。
• 参考スコア（独自算出の注目度）: 60.65928290219793
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study without-replacement SGD for solving finite-sum optimization problems. Specifically, depending on how the indices of the finite-sum are shuffled, we consider the RandomShuffle (shuffle at the beginning of each epoch) and SingleShuffle (shuffle only once) algorithms. First, we establish minimax optimal convergence rates of these algorithms up to poly-log factors. Notably, our analysis is general enough to cover gradient dominated nonconvex costs, and does not rely on the convexity of individual component functions unlike existing optimal convergence results. Secondly, assuming convexity of the individual components, we further sharpen the tight convergence results for RandomShuffle by removing the drawbacks common to all prior arts: large number of epochs required for the results to hold, and extra poly-log factor gaps to the lower bound.
• Abstract（参考訳）: 有限サム最適化問題に対する置き換えのないSGDについて検討する。 具体的には、有限サムの指標がどのようにシャッフルされるかによって、RandomShuffle(各エポックの開始時のシャッフル)とSingleShuffle(シャッフルのみ)のアルゴリズムを考える。 まず、これらのアルゴリズムの最小収束速度をポリログ因子に設定する。 特に, 本解析は, 勾配支配型非凸コストをカバーするのに十分一般的であり, 既存の最適収束結果とは異なり, 個々の成分関数の凸性に依存しない。 第二に、各成分の凸性を仮定すると、従来のすべての芸術に共通する欠点を除去することにより、RandomShuffleの厳密な収束結果をさらに強化する。

関連論文リスト

• Random Scaling and Momentum for Non-smooth Non-convex Optimization [38.443430569753026]
  ニューラルネットワークのトレーニングには、非常に不規則な、特に凸や滑らかな損失関数が必要である。 一般的なトレーニングアルゴリズムは運動量による勾配降下(SGDM)に基づいており、損失が凸あるいは滑らかである場合にのみ解析が適用される。
  論文  参考訳（メタデータ） (2024-05-16T00:52:03Z)
• Private optimization in the interpolation regime: faster rates and hardness results [9.405458160620533]
  プライベートでない凸最適化では、勾配法は非補間法よりも、全てのサンプル損失を同時に最小化する解が存在するという問題にはるかに早く収束する。 プライベートサンプルの複雑さは指数関数的に改善した(近辺)。
  論文  参考訳（メタデータ） (2022-10-31T05:18:27Z)
• Sampling without Replacement Leads to Faster Rates in Finite-Sum Minimax Optimization [12.794526174053134]
  滑らかな有限サム最小値最適化のための勾配アルゴリズムの収束速度を解析する。 このようなアルゴリズムの多くは、置換のないサンプリングポイントが、置換したサンプリングよりも高速な収束をもたらすことを示している。
  論文  参考訳（メタデータ） (2022-06-07T00:37:37Z)
• Accelerated SGD for Non-Strongly-Convex Least Squares [14.010916616909743]
  非強凸設定における最小二乗回帰問題の近似を考察する。 本稿では,問題のノイズに依存して最適な予測誤差率を実現するための,最初の実用的なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-03-03T14:39:33Z)
• Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond [63.59034509960994]
  シャッフルに基づく変種(ミニバッチと局所ランダムリシャッフル)について検討する。 ポリアック・ロジャシエヴィチ条件を満たす滑らかな函数に対して、これらのシャッフル型不変量(英語版)(shuffling-based variants)がそれらの置換式よりも早く収束することを示す収束境界を得る。 我々は, 同期シャッフル法と呼ばれるアルゴリズムの修正を提案し, ほぼ均一な条件下では, 下界よりも収束速度が速くなった。
  論文  参考訳（メタデータ） (2021-10-20T02:25:25Z)
• Optimal Rates for Random Order Online Optimization [60.011653053877126]
  敵が損失関数を選択できるカテットガルバー2020onlineについて検討するが、一様にランダムな順序で提示される。 2020onlineアルゴリズムが最適境界を達成し,安定性を著しく向上することを示す。
  論文  参考訳（メタデータ） (2021-06-29T09:48:46Z)
• Tight Lower Complexity Bounds for Strongly Convex Finite-Sum Optimization [21.435973899949285]
  SAG, SAGA, SVRG, SARAHを含むランダム化漸進勾配法では, 有限和最適化の典型的な2つの場合において, 厳密に低い複雑性境界を導出する。 結果は,各成分関数が強凸で滑らかな場合のKatyushaやVRADAの上部複雑性と密に一致し,有限サム関数が強凸で成分関数が平均滑らかな場合のKatyushaXとSDCAの上部複雑性と密に一致した。
  論文  参考訳（メタデータ） (2020-10-17T11:19:07Z)
• Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits [99.70167985955352]
  強凸関数のゼロ次最適化問題について検討する。 予測勾配降下アルゴリズムのランダム化近似を考察する。 その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
  論文  参考訳（メタデータ） (2020-06-14T10:42:23Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)
• Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
  本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。 Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。 本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
  論文  参考訳（メタデータ） (2020-05-10T19:52:03Z)

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

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