論文の概要: Random Shuffling Beats SGD Only After Many Epochs on Ill-Conditioned Problems

• arxiv url: http://arxiv.org/abs/2106.06880v1
• Date: Sat, 12 Jun 2021 23:07:27 GMT
• ステータス: 処理完了
• システム内更新日: 2021-06-15 15:49:04.003858
• Title: Random Shuffling Beats SGD Only After Many Epochs on Ill-Conditioned Problems
• Title（参考訳）: ランダム・シャッフルがSGDを抜いたのは、多くのEpochsのあと
• Authors: Itay Safran and Ohad Shamir
• Abstract要約: その結果,非置換型SGDエンファンドは最悪のケース境界において,非置換型SGDに対して顕著な改善は得られなかった。 機械学習や他の分野の多くの問題は条件が不適切であり、大きなデータセットが関与しているため、非置換が現実的な予算のための非置換サンプリングよりも必ずしも改善しないことを示している。
• 参考スコア（独自算出の注目度）: 55.40911408462676
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recently, there has been much interest in studying the convergence rates of without-replacement SGD, and proving that it is faster than with-replacement SGD in the worst case. However, these works ignore or do not provide tight bounds in terms of the problem's geometry, including its condition number. Perhaps surprisingly, we prove that when the condition number is taken into account, without-replacement SGD \emph{does not} significantly improve on with-replacement SGD in terms of worst-case bounds, unless the number of epochs (passes over the data) is larger than the condition number. Since many problems in machine learning and other areas are both ill-conditioned and involve large datasets, this indicates that without-replacement does not necessarily improve over with-replacement sampling for realistic iteration budgets. We show this by providing new lower and upper bounds which are tight (up to log factors), for quadratic problems with commuting quadratic terms, precisely quantifying the dependence on the problem parameters.
• Abstract（参考訳）: 近年,非置換性SGDの収束速度の研究や,非置換性SGDよりも高速であることの証明に多くの関心が寄せられている。 しかし、これらの著作は、その条件数を含む問題の幾何について、厳密な境界を与えないか無視する。 意外なことに、条件番号が考慮されると、条件番号よりもエポック数(データを越えるパス)が大きければ、非置換SGD \emph{does not} は最悪ケース境界の点で、不置換SGDを大幅に改善する。 機械学習や他の分野の多くの問題は条件が不適切であり、大きなデータセットが関与しているため、現実的なイテレーション予算のために、置き換えのないサンプリングは必ずしも改善されない。 我々は,二次項を可換とする二次問題に対して,(対数係数まで)密接な新しい下界と上界を提供することにより,問題パラメータへの依存度を正確に定量化する。

関連論文リスト

• Empirical Risk Minimization with Shuffled SGD: A Primal-Dual Perspective and Improved Bounds [12.699376765058137]
  勾配降下法(SGD)は、おそらく現代の機械学習において最も一般的な最適化法である。 SGDを交換せずにサンプリングするSGDが分析されたのはごく最近のことだ。 データマトリックスに依存し、既存の境界によって予測されるものよりも決して悪くない、きめ細かい複雑性境界を証明します。
  論文  参考訳（メタデータ） (2023-06-21T18:14:44Z)
• SketchySGD: Reliable Stochastic Optimization via Randomized Curvature Estimates [19.420605210427635]
  SketchySGDは、サブサンプルヘッセンに対するランダム化低ランク近似を用いることで、機械学習の既存の勾配法を改善する。 固定段数を持つSketchySGDが最適の周りの小さな球に線形に収束することを理論的に示す。 条件のない設定では、最小二乗問題に対してSketchySGDはSGDよりも高速に収束することを示す。
  論文  参考訳（メタデータ） (2022-11-16T01:05:41Z)
• Benign Underfitting of Stochastic Gradient Descent [72.38051710389732]
  本研究では,適切な学習データを得ることで,一般化性能を実現する「従来型」学習ルールとして,勾配降下度(SGD)がどの程度理解されるかを検討する。 類似現象が起こらない近縁な交換SGDを解析し、その集団リスクが実際に最適な速度で収束することを証明する。
  論文  参考訳（メタデータ） (2022-02-27T13:25:01Z)
• The Benefits of Implicit Regularization from SGD in Least Squares Problems [116.85246178212616]
  勾配降下(SGD)はアルゴリズム正則化効果が強い。 我々は、(正規化されていない)平均SGDで得られる暗黙の正則化とリッジ回帰の明示的な正則化の比較を行う。
  論文  参考訳（メタデータ） (2021-08-10T09:56:47Z)
• Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
  本稿では,SGDA と SCO の最終的な収束保証として,期待されるコヒーレンシティ条件を導入し,その利点を説明する。 定常的なステップサイズを用いた場合、両手法の線形収束性を解の近傍に証明する。 我々の収束保証は任意のサンプリングパラダイムの下で保たれ、ミニバッチの複雑さに関する洞察を与える。
  論文  参考訳（メタデータ） (2021-06-30T18:32:46Z)
• Can Single-Shuffle SGD be Better than Reshuffling SGD and GD? [77.82009268160053]
  我々は、SGDの非置換変種に対応する行列積の手段が一連のスペクトルノルムの不等式を満たすと仮定する。 我々は、いくつかの特別な場合を証明し、予想を支持する定理を示す。
  論文  参考訳（メタデータ） (2021-03-12T04:34:45Z)
• IntSGD: Floatless Compression of Stochastic Gradients [19.99615698375829]
  本研究では,1つのフロートを乗算して通信しないグラディエントDescent (SGD) に対する損失整数圧縮のファミリを提案する。 データが著しく異質である場合には、整数を保ち続けることがますます難しくなり、このタイプの問題を解決するための代替アルゴリズムであるIntyAを提案する。
  論文  参考訳（メタデータ） (2021-02-16T18:58:57Z)
• On Tight Convergence Rates of Without-replacement SGD [52.99237600875452]
  有限サム最適化問題を解くために、置換サンプリングのないSGDは、SGDより優れていることを実証的に示している。 本研究では, 時代によって異なるステップサイズを解析することによって, これらの制約を克服する。
  論文  参考訳（メタデータ） (2020-04-18T16:14:11Z)

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

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