論文の概要: Demystifying SGD with Doubly Stochastic Gradients

• arxiv url: http://arxiv.org/abs/2406.00920v1
• Date: Mon, 3 Jun 2024 01:13:19 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-06 02:47:03.196630
• Title: Demystifying SGD with Doubly Stochastic Gradients
• Title（参考訳）: 二重確率勾配によるSGDのデマイタイズ
• Authors: Kyurae Kim, Joohwan Ko, Yi-An Ma, Jacob R. Gardner,
• Abstract要約: 一般条件下では、独立なミニバッチとランダムリシャッフルを併用した2重SGDの収束特性を確立する。 ランダムリシャッフルによりサブサンプリングノイズの複雑性依存性が向上することが証明された。
• 参考スコア（独自算出の注目度）: 13.033133586372612
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Optimization objectives in the form of a sum of intractable expectations are rising in importance (e.g., diffusion models, variational autoencoders, and many more), a setting also known as "finite sum with infinite data." For these problems, a popular strategy is to employ SGD with doubly stochastic gradients (doubly SGD): the expectations are estimated using the gradient estimator of each component, while the sum is estimated by subsampling over these estimators. Despite its popularity, little is known about the convergence properties of doubly SGD, except under strong assumptions such as bounded variance. In this work, we establish the convergence of doubly SGD with independent minibatching and random reshuffling under general conditions, which encompasses dependent component gradient estimators. In particular, for dependent estimators, our analysis allows fined-grained analysis of the effect correlations. As a result, under a per-iteration computational budget of $b \times m$, where $b$ is the minibatch size and $m$ is the number of Monte Carlo samples, our analysis suggests where one should invest most of the budget in general. Furthermore, we prove that random reshuffling (RR) improves the complexity dependence on the subsampling noise.
• Abstract（参考訳）: 難解な期待の和の形の最適化の目的は重要度(拡散モデル、変分オートエンコーダなど)が高くなり、「無限のデータ付き有限和」とも呼ばれる。 これらの問題に対して、一般的な戦略は、SGDを2倍確率勾配(二重確率勾配)で採用することであり、期待値は各成分の勾配推定器を用いて推定され、その和はこれらの推定器のサブサンプリングによって推定される。 その人気にもかかわらず、有界分散のような強い仮定の下では、二重SGDの収束性についてはほとんど知られていない。 本研究では,従属成分勾配推定器を含む独立ミニバッチとランダムリシャッフルによる2つのSGDの収束を確立する。 特に、依存推定器の場合、我々の分析は効果相関の微粒化解析を可能にする。 その結果,1項目あたりの計算予算は$b \times m$で,$b$はミニバッチサイズであり,$m$はモンテカルロのサンプル数である。 さらに、ランダムリシャッフル(RR)がサブサンプリングノイズの複雑性依存性を向上させることを証明する。

関連論文リスト

• Multivariate root-n-consistent smoothing parameter free matching estimators and estimators of inverse density weighted expectations [51.000851088730684]
  我々は、パラメトリックな$sqrt n $-rateで収束する、最も近い隣人の新しい修正とマッチング推定器を開発する。 我々は,非パラメトリック関数推定器は含まないこと,特に標本サイズ依存パラメータの平滑化には依存していないことを強調する。
  論文  参考訳（メタデータ） (2024-07-11T13:28:34Z)
• Empirical Risk Minimization with Shuffled SGD: A Primal-Dual Perspective and Improved Bounds [12.699376765058137]
  勾配降下法(SGD)は、おそらく現代の機械学習において最も一般的な最適化法である。 SGDを交換せずにサンプリングするSGDが分析されたのはごく最近のことだ。 データマトリックスに依存し、既存の境界によって予測されるものよりも決して悪くない、きめ細かい複雑性境界を証明します。
  論文  参考訳（メタデータ） (2023-06-21T18:14:44Z)
• Benign Underfitting of Stochastic Gradient Descent [72.38051710389732]
  本研究では,適切な学習データを得ることで,一般化性能を実現する「従来型」学習ルールとして,勾配降下度(SGD)がどの程度理解されるかを検討する。 類似現象が起こらない近縁な交換SGDを解析し、その集団リスクが実際に最適な速度で収束することを証明する。
  論文  参考訳（メタデータ） (2022-02-27T13:25:01Z)
• A Unified Framework for Multi-distribution Density Ratio Estimation [101.67420298343512]
  バイナリ密度比推定(DRE)は多くの最先端の機械学習アルゴリズムの基礎を提供する。 ブレグマン最小化の発散の観点から一般的な枠組みを開発する。 我々のフレームワークはバイナリDREでそれらのフレームワークを厳格に一般化する手法に導かれることを示す。
  論文  参考訳（メタデータ） (2021-12-07T01:23:20Z)
• Gaussian Process Inference Using Mini-batch Stochastic Gradient Descent: Convergence Guarantees and Empirical Benefits [21.353189917487512]
  勾配降下(SGD)とその変種は、機械学習問題のアルゴリズムとして確立されている。 我々は、最小バッチSGDが全ログ類似損失関数の臨界点に収束することを証明して一歩前進する。 我々の理論的な保証は、核関数が指数的あるいは固有デカイを示すことを前提としている。
  論文  参考訳（メタデータ） (2021-11-19T22:28:47Z)
• On the Double Descent of Random Features Models Trained with SGD [78.0918823643911]
  勾配降下(SGD)により最適化された高次元におけるランダム特徴(RF)回帰特性について検討する。 本研究では, RF回帰の高精度な非漸近誤差境界を, 定常および適応的なステップサイズSGD設定の下で導出する。 理論的にも経験的にも二重降下現象を観察する。
  論文  参考訳（メタデータ） (2021-10-13T17:47:39Z)
• Heavy-tailed Streaming Statistical Estimation [58.70341336199497]
  ストリーミング$p$のサンプルから重み付き統計推定の課題を考察する。 そこで我々は,傾きの雑音に対して,よりニュアンスな条件下での傾きの傾きの低下を設計し,より詳細な解析を行う。
  論文  参考訳（メタデータ） (2021-08-25T21:30:27Z)
• A general sample complexity analysis of vanilla policy gradient [101.16957584135767]
  政策勾配(PG)は、最も一般的な強化学習(RL)問題の1つである。 PG軌道の「バニラ」理論的理解は、RL問題を解く最も一般的な方法の1つである。
  論文  参考訳（メタデータ） (2021-07-23T19:38:17Z)
• Optimal Sub-Gaussian Mean Estimation in $\mathbb{R}$ [5.457150493905064]
  ガウス下収束を考慮した新しい推定器を提案する。 我々の推定器はその分散に関する事前の知識を必要としない。 我々の推定器の構成と分析は、他の問題に一般化可能なフレームワークを提供する。
  論文  参考訳（メタデータ） (2020-11-17T02:47:24Z)
• Optimal Algorithms for Stochastic Multi-Armed Bandits with Heavy Tailed Rewards [24.983866845065926]
  我々は、重い尾の報酬を持つマルチアームのバンディットを考えており、そのp$-thのモーメントは、定数$nu_p$が1pleq2$である。 本稿では,従来の情報として$nu_p$を必要としない新しいロバストな推定器を提案する。 提案した推定器の誤差確率は指数関数的に高速に減衰することを示す。
  論文  参考訳（メタデータ） (2020-10-24T10:44:02Z)
• The Heavy-Tail Phenomenon in SGD [7.366405857677226]
  最小損失のHessianの構造に依存すると、SGDの反復はエンフェビーテールの定常分布に収束する。 深層学習におけるSGDの行動に関する知見に分析結果を変換する。
  論文  参考訳（メタデータ） (2020-06-08T16:43:56Z)

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

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