論文の概要: Can Single-Shuffle SGD be Better than Reshuffling SGD and GD?

• arxiv url: http://arxiv.org/abs/2103.07079v1
• Date: Fri, 12 Mar 2021 04:34:45 GMT
• ステータス: 処理完了
• システム内更新日: 2021-03-15 13:11:29.134090
• Title: Can Single-Shuffle SGD be Better than Reshuffling SGD and GD?
• Title（参考訳）: シングルシャッフルSGDはSGDとGDのリシャッフルより優れているか?
• Authors: Chulhee Yun, Suvrit Sra, Ali Jadbabaie
• Abstract要約: 我々は、SGDの非置換変種に対応する行列積の手段が一連のスペクトルノルムの不等式を満たすと仮定する。 我々は、いくつかの特別な場合を証明し、予想を支持する定理を示す。
• 参考スコア（独自算出の注目度）: 77.82009268160053
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose matrix norm inequalities that extend the Recht-R\'e (2012) conjecture on a noncommutative AM-GM inequality by supplementing it with another inequality that accounts for single-shuffle, which is a widely used without-replacement sampling scheme that shuffles only once in the beginning and is overlooked in the Recht-R\'e conjecture. Instead of general positive semidefinite matrices, we restrict our attention to positive definite matrices with small enough condition numbers, which are more relevant to matrices that arise in the analysis of SGD. For such matrices, we conjecture that the means of matrix products corresponding to with- and without-replacement variants of SGD satisfy a series of spectral norm inequalities that can be summarized as: "single-shuffle SGD converges faster than random-reshuffle SGD, which is in turn faster than with-replacement SGD." We present theorems that support our conjecture by proving several special cases.
• Abstract（参考訳）: 非可換 AM-GM の不等式上の Recht-R\'e (2012) 予想を拡張する行列ノルムの不等式を提案する。 一般の正の半定値行列の代わりに、SGDの分析で生じる行列とより関係のある十分な条件数を持つ正の定値行列に注意を限定する。 そのような行列に対して、SGDの非置換変種に対応する行列積の手段は、一連のスペクトルノルムの不等式を満たすことを予想する: 「単一シャッフルSGDはランダムリシャッフルSGDよりも早く収束し、非置換SGDよりも高速である」。 我々は、いくつかの特別な場合を証明し、予想を支持する定理を示す。

関連論文リスト

• Stochastic Extragradient with Random Reshuffling: Improved Convergence for Variational Inequalities [40.1331539540764]
  本稿では,3種類のVIPに対してランダムリシャッフル(SEG-RR)を用いたSEGの収束解析を行う。 我々は,SEG-RRが均一な置換サンプリングSEGよりも高速に収束する条件を導出する。 単調な設定では,SEG-RRの解析により,大きなバッチサイズを伴わずに任意の精度で収束が保証される。
  論文  参考訳（メタデータ） (2024-03-11T20:35:52Z)
• Positive Semidefinite Matrix Supermartingales [30.14855064043107]
  正半定値行列の空間における超行列と後方部分行列の収束性と漸近的最大不等式について検討する。 その結果, 種々の尾条件下でのマルティンゲール依存あるいは交換可能なランダム対称行列に対する新しい濃度不等式が得られた。 これらの不等式は通常、バウンスナー順序で表され、全てのサンプルサイズまたは任意のデータ依存の停止時間で同時に有効であり、しばしば外部ランダム化係数によって引き締められる。
  論文  参考訳（メタデータ） (2024-01-28T04:22:43Z)
• Empirical Risk Minimization with Shuffled SGD: A Primal-Dual Perspective and Improved Bounds [12.699376765058137]
  勾配降下法(SGD)は、おそらく現代の機械学習において最も一般的な最適化法である。 SGDを交換せずにサンプリングするSGDが分析されたのはごく最近のことだ。 データマトリックスに依存し、既存の境界によって予測されるものよりも決して悪くない、きめ細かい複雑性境界を証明します。
  論文  参考訳（メタデータ） (2023-06-21T18:14:44Z)
• Rank-1 Matrix Completion with Gradient Descent and Small Random Initialization [15.127728811011245]
  我々は,GDの暗黙的正規化が分析において重要な役割を担っていることを示す。 我々は、手頃な分析において暗黙の正規化GDが重要な役割を担っていることを観察する。
  論文  参考訳（メタデータ） (2022-12-19T12:05:37Z)
• Risk Bounds of Multi-Pass SGD for Least Squares in the Interpolation Regime [127.21287240963859]
  勾配降下(SGD)は最適化と一般化の両方において優れた性能を持つため、大きな成功を収めている。 本稿では,マルチパスSGDの一般化を強く特徴付けることを目的とする。 我々は,SGDが同じレベルの過剰リスクを達成するためには,GD以上を必要とするが,勾配評価の回数を削減できることを示した。
  論文  参考訳（メタデータ） (2022-03-07T06:34:53Z)
• 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)
• Benign Overfitting of Constant-Stepsize SGD for Linear Regression [122.70478935214128]
  帰納バイアスは 経験的に過剰フィットを防げる中心的存在です この研究は、この問題を最も基本的な設定として考慮している: 線形回帰に対する定数ステップサイズ SGD。 我々は、(正規化されていない)SGDで得られるアルゴリズム正則化と、通常の最小二乗よりも多くの顕著な違いを反映する。
  論文  参考訳（メタデータ） (2021-03-23T17:15:53Z)
• Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform [64.90148466525754]
  最小二乗問題に対する反復スケッチの性能について検討する。 本研究では、Haar行列とランダム化されたHadamard行列の収束速度が同一であることを示し、ランダムなプロジェクションを経時的に改善することを示した。 これらの手法は、ランダム化次元還元を用いた他のアルゴリズムにも適用することができる。
  論文  参考訳（メタデータ） (2020-02-03T16:17:50Z)

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

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