論文の概要: Adjusted Shuffling SARAH: Advancing Complexity Analysis via Dynamic Gradient Weighting

• arxiv url: http://arxiv.org/abs/2506.12444v1
• Date: Sat, 14 Jun 2025 10:46:03 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-17 17:28:46.200981
• Title: Adjusted Shuffling SARAH: Advancing Complexity Analysis via Dynamic Gradient Weighting
• Title（参考訳）: 調整シャッフルSARAH:動的勾配重み付けによる複雑度解析の高速化
• Authors: Duc Toan Nguyen, Trang H. Tran, Lam M. Nguyen,
• Abstract要約: 本稿では、シャッフル手法とよく知られた分散還元アルゴリズムSARAHを統合する新しいアルゴリズムであるAdjusted Shuffling SARAHを提案する。 Inexact Adjusted Reshuffling SARAHも導入した。これはAdjusted Shuffling SARAHの不正確な変種であり、フルバッチ勾配計算を不要とする。
• 参考スコア（独自算出の注目度）: 14.056428870985458
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we propose Adjusted Shuffling SARAH, a novel algorithm that integrates shuffling techniques with the well-known variance-reduced algorithm SARAH while dynamically adjusting the stochastic gradient weights in each update to enhance exploration. Our method achieves the best-known gradient complexity for shuffling variance reduction methods in a strongly convex setting. This result applies to any shuffling technique, which narrows the gap in the complexity analysis of variance reduction methods between uniform sampling and shuffling data. Furthermore, we introduce Inexact Adjusted Reshuffling SARAH, an inexact variant of Adjusted Shuffling SARAH that eliminates the need for full-batch gradient computations. This algorithm retains the same linear convergence rate as Adjusted Shuffling SARAH while showing an advantage in total complexity when the sample size is very large.
• Abstract（参考訳）: 本稿では,シャッフル手法をよく知られた分散還元アルゴリズムSARAHと統合し,各更新の確率勾配重みを動的に調整して探索を強化するアルゴリズムであるAdjusted Shuffling SARAHを提案する。 本手法は,強い凸条件下で分散低減法をシャッフルする上で,最もよく知られた勾配複雑性を実現する。 この結果は、一様サンプリングとシャッフルデータの分散還元法における複雑性解析のギャップを狭めるシャッフル法に適用できる。 さらに,適応シャッフルSARAHの非コンパクトな変種であるInexact Adjusted Reshuffling SARAHを導入し,フルバッチ勾配計算の必要性を排除した。 このアルゴリズムは、サンプルサイズが非常に大きい場合、全複雑性の利点を示しながら、調整されたシャッフルング SARAH と同じ線形収束率を保持する。

関連論文リスト

• Variance Reduction Methods Do Not Need to Compute Full Gradients: Improved Efficiency through Shuffling [44.31966204357333]
  大規模機械学習問題に対するメモリ効率のアルゴリズムを開発した。 メモリ効率を向上し、完全な計算を避けるために、2つの重要な手法を用いる。
  論文  参考訳（メタデータ） (2025-02-20T15:37:45Z)
• Gradient Normalization Provably Benefits Nonconvex SGD under Heavy-Tailed Noise [60.92029979853314]
  重み付き雑音下でのグラディエントDescence(SGD)の収束を確実にする上での勾配正規化とクリッピングの役割について検討する。 我々の研究は、重尾雑音下でのSGDの勾配正規化の利点を示す最初の理論的証拠を提供する。 我々は、勾配正規化とクリッピングを取り入れた加速SGD変種を導入し、さらに重み付き雑音下での収束率を高めた。
  論文  参考訳（メタデータ） (2024-10-21T22:40:42Z)
• SMIXS: Novel efficient algorithm for non-parametric mixture regression-based clustering [0.0]
  縦方向データ解析のための非パラメトリック回帰に基づくクラスタリングアルゴリズムを開発した。 クラスタリングおよび回帰性能の観点から,合成データセット上でのGMMよりも優れた性能を示す。
  論文  参考訳（メタデータ） (2022-09-19T14:03:51Z)
• Federated Optimization Algorithms with Random Reshuffling and Gradient Compression [2.7554288121906296]
  勾配圧縮法と非置換サンプリング法を初めて解析する。 制御イテレートを用いて勾配量子化から生じる分散を減少させる方法を示す。 既存のアルゴリズムを改善するいくつかの設定について概説する。
  論文  参考訳（メタデータ） (2022-06-14T17:36:47Z)
• Random-reshuffled SARAH does not need a full gradient computations [61.85897464405715]
  StochAstic Recursive grAdientritHm (SARAH)アルゴリズムは、Gradient Descent (SGD)アルゴリズムのばらつき低減版である。 本稿では,完全勾配の必要性を除去する。 集約された勾配は、SARAHアルゴリズムの完全な勾配の見積もりとなる。
  論文  参考訳（メタデータ） (2021-11-26T06:00:44Z)
• Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond [63.59034509960994]
  シャッフルに基づく変種(ミニバッチと局所ランダムリシャッフル)について検討する。 ポリアック・ロジャシエヴィチ条件を満たす滑らかな函数に対して、これらのシャッフル型不変量(英語版)(shuffling-based variants)がそれらの置換式よりも早く収束することを示す収束境界を得る。 我々は, 同期シャッフル法と呼ばれるアルゴリズムの修正を提案し, ほぼ均一な条件下では, 下界よりも収束速度が速くなった。
  論文  参考訳（メタデータ） (2021-10-20T02:25:25Z)
• Differentiable Annealed Importance Sampling and the Perils of Gradient Noise [68.44523807580438]
  Annealed importance sample (AIS) と関連するアルゴリズムは、限界推定のための非常に効果的なツールである。 差別性は、目的として限界確率を最適化する可能性を認めるため、望ましい性質である。 我々はメトロポリス・ハスティングスのステップを放棄して微分可能アルゴリズムを提案し、ミニバッチ計算をさらに解き放つ。
  論文  参考訳（メタデータ） (2021-07-21T17:10:14Z)
• Adaptive Importance Sampling for Finite-Sum Optimization and Sampling with Decreasing Step-Sizes [4.355567556995855]
  ステップサイズを小さくした有限サム最適化とサンプリングのための適応的重要度サンプリングのための簡易かつ効率的なアルゴリズムであるavareを提案する。 標準的な技術的条件下では、$mathcalO(T2/3)$と$mathcalO(T5/6)$の動的後悔をそれぞれ、$mathcalO(T5/6)$のステップサイズで実行するときに達成している。
  論文  参考訳（メタデータ） (2021-03-23T00:28:15Z)
• AI-SARAH: Adaptive and Implicit Stochastic Recursive Gradient Methods [7.486132958737807]
  適応性に対する暗黙的アプローチによる適応分散低減手法を提案する。 有限サム最小化問題に対する収束保証を提供し,局所幾何が許せばサラよりも高速に収束できることを示す。 このアルゴリズムはステップサイズを暗黙的に計算し、関数の局所リプシッツ滑らかさを効率的に推定する。
  論文  参考訳（メタデータ） (2021-02-19T01:17:15Z)
• Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clipping [69.9674326582747]
  そこで本研究では,重み付き分散雑音を用いたスムーズな凸最適化のための,クリップ付きSSTMと呼ばれる新しい1次高速化手法を提案する。 この場合、最先端の結果を上回る新たな複雑さが証明される。 本研究は,SGDにおいて,ノイズに対する光細かな仮定を伴わずにクリッピングを施した最初の非自明な高確率複雑性境界を導出した。
  論文  参考訳（メタデータ） (2020-05-21T17:05:27Z)

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

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