論文の概要: Learning to Shuffle: Block Reshuffling and Reversal Schemes for Stochastic Optimization
- arxiv url: http://arxiv.org/abs/2604.00260v1
- Date: Tue, 31 Mar 2026 21:40:43 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-04-02 16:44:31.734348
- Title: Learning to Shuffle: Block Reshuffling and Reversal Schemes for Stochastic Optimization
- Title（参考訳）: シャッフル学習:確率最適化のためのブロックリシャッフルとリバーサルスキーム
- Authors: Lam M. Nguyen, Dzung T. Phan, Jayant Kalagnanam,
- Abstract要約: 大規模言語モデル(LLM)誘導プログラム進化フレームワークを用いて,SGDを置き換えることなく,効率的なシャッフルルールを発見する。
ブロックリシャッフルは, 統一シャッフルにおけるプレフィックス-勾配変動定数を厳格に低減し, 弱条件下でのランダムリシャッフルよりも良好な改善をもたらすことを示す。
また、ペア逆転がエポックマップを対称性付け、先行する順序依存の2次項をキャンセルし、ステップサイズにおいて2次から3次への順序感度を低下させることを示した。
- 参考スコア（独自算出の注目度）: 20.63685754619351
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Shuffling strategies for stochastic gradient descent (SGD), including incremental gradient, shuffle-once, and random reshuffling, are supported by rigorous convergence analyses for arbitrary within-epoch permutations. In particular, random reshuffling is known to improve optimization constants relative to cyclic and shuffle-once schemes. However, existing theory offers limited guidance on how to design new data-ordering schemes that further improve optimization constants or stability beyond random reshuffling. In this paper, we design a pipeline using a large language model (LLM)-guided program evolution framework to discover an effective shuffling rule for without-replacement SGD. Abstracting from this instance, we identify two fundamental structural components: block reshuffling and paired reversal. We analyze these components separately and show that block reshuffling strictly reduces prefix-gradient variance constants within the unified shuffling framework, yielding provable improvements over random reshuffling under mild conditions. Separately, we show that paired reversal symmetrizes the epoch map and cancels the leading order-dependent second-order term, reducing order sensitivity from quadratic to cubic in the step size. Numerical experiments with the discovered algorithm validate the theory and demonstrate consistent gains over standard shuffling schemes across convex and nonconvex benchmarks.
- Abstract（参考訳）: 漸進勾配, シャッフルオンス, ランダム再シャッフルを含む確率勾配降下(SGD)のシャッフル戦略は, 任意の時間内置換に対する厳密な収束解析によって支持される。
特に、ランダムリシャッフルは、循環およびシャッフルオンススキームに対する最適化定数を改善することが知られている。
しかし、既存の理論では、ランダムリシャッフルを超える最適化定数や安定性をさらに改善する新しいデータ順序付けスキームを設計する方法について、限定的なガイダンスを提供している。
本稿では,大規模言語モデル (LLM) 誘導型プログラム進化フレームワークを用いてパイプラインを設計し,SGD を置き換えないための効率的なシャッフルルールを探索する。
この例から要約すると、ブロックのリシャッフルとペアの逆転という2つの基本構造成分を識別する。
我々はこれらの成分を分離して解析し、ブロック再シャッフルが統一シャッフルフレームワーク内のプレフィックス-段階的分散定数を厳密に低減し、緩やかな条件下でのランダム再シャッフルよりも証明可能な改善をもたらすことを示す。
これとは別に、ペアの逆転がエポックマップをシミュレートし、先行する順序依存の2次項をキャンセルし、ステップサイズの2次から3次への順序感度を低下させることを示した。
発見アルゴリズムによる数値実験により、凸および非凸のベンチマークにおける標準シャッフル方式よりも一貫した利得が証明された。
関連論文リスト
- Closed-Form Last Layer Optimization [72.49151473937319]
正方形損失の下では、線形最終層重みに対する最適解は閉形式で知られている。
これは、バックボーン上の勾配降下ステップと最終層上のクローズドフォーム更新の交互に行われることを示す。
論文 参考訳（メタデータ） (2025-10-06T09:14:39Z) - Inference-Time Scaling of Diffusion Language Models with Particle Gibbs Sampling [70.8832906871441]
我々は、モデルを再訓練することなく、所望の報酬に向けて世代を操る方法を研究する。
従来の手法では、通常は1つの認知軌道内でサンプリングやフィルタを行い、軌道レベルの改善なしに報酬をステップバイステップで最適化する。
本稿では,拡散言語モデル(PG-DLM)の粒子ギブスサンプリングについて紹介する。
論文 参考訳（メタデータ） (2025-07-11T08:00:47Z) - Gradient Normalization Provably Benefits Nonconvex SGD under Heavy-Tailed Noise [60.92029979853314]
重み付き雑音下でのグラディエントDescence(SGD)の収束を確実にする上での勾配正規化とクリッピングの役割について検討する。
我々の研究は、重尾雑音下でのSGDの勾配正規化の利点を示す最初の理論的証拠を提供する。
我々は、勾配正規化とクリッピングを取り入れた加速SGD変種を導入し、さらに重み付き雑音下での収束率を高めた。
論文 参考訳（メタデータ） (2024-10-21T22:40:42Z) - Cyclic Block Coordinate Descent With Variance Reduction for Composite
Nonconvex Optimization [26.218670461973705]
非漸近勾配ノルム保証を協調する問題の解法を提案する。
本研究は,ニューラルネットの深部学習における循環還元方式の有効性を実証するものである。
論文 参考訳（メタデータ） (2022-12-09T19:17:39Z) - Convergence of ease-controlled Random Reshuffling gradient Algorithms under Lipschitz smoothness [0.0]
非常に多くのスムーズで可能な非サイズの関数の平均を考慮し、この問題に対処するために2つの広く最小限のフレームワークを使用します。
IG/RRスキームの簡易制御による修正を定義する。
我々は、完全なバッチ勾配(L-BFGS)とIG/RR手法の実装の両方で実装を証明し、アルゴリズムが同様の計算作業を必要とすることを証明した。
論文 参考訳（メタデータ） (2022-12-04T15:26:36Z) - Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and
Beyond [63.59034509960994]
シャッフルに基づく変種(ミニバッチと局所ランダムリシャッフル)について検討する。
ポリアック・ロジャシエヴィチ条件を満たす滑らかな函数に対して、これらのシャッフル型不変量(英語版)(shuffling-based variants)がそれらの置換式よりも早く収束することを示す収束境界を得る。
我々は, 同期シャッフル法と呼ばれるアルゴリズムの修正を提案し, ほぼ均一な条件下では, 下界よりも収束速度が速くなった。
論文 参考訳（メタデータ） (2021-10-20T02:25:25Z) - On the Convergence of Stochastic Extragradient for Bilinear Games with
Restarted Iteration Averaging [96.13485146617322]
本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。
平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
論文 参考訳（メタデータ） (2021-06-30T17:51:36Z) - Optimal Rates for Random Order Online Optimization [60.011653053877126]
敵が損失関数を選択できるカテットガルバー2020onlineについて検討するが、一様にランダムな順序で提示される。
2020onlineアルゴリズムが最適境界を達成し,安定性を著しく向上することを示す。
論文 参考訳（メタデータ） (2021-06-29T09:48:46Z) - Stochastic Reweighted Gradient Descent [4.355567556995855]
SRG(stochastic reweighted gradient)と呼ばれる重要サンプリングに基づくアルゴリズムを提案する。
我々は、提案手法の時間とメモリオーバーヘッドに特に注意を払っています。
我々はこの発見を裏付ける実験結果を示す。
論文 参考訳（メタデータ） (2021-03-23T04:09:43Z) - SGB: Stochastic Gradient Bound Method for Optimizing Partition Functions [15.33098084159285]
本稿では,学習環境における分割関数の最適化の問題に対処する。
本稿では,2次代理を持つ分割関数の上界に依存する有界偏化アルゴリズムの変種を提案する。
論文 参考訳（メタデータ） (2020-11-03T04:42:51Z) - Variance Regularization for Accelerating Stochastic Optimization [14.545770519120898]
ミニバッチ勾配に隠れた統計情報を利用してランダムな誤りの蓄積を低減する普遍原理を提案する。
これは、ミニバッチのばらつきに応じて学習率を正規化することで達成される。
論文 参考訳（メタデータ） (2020-08-13T15:34:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。