論文の概要: Robust stochastic first order methods in heavy-tailed noise via medoid mini-batch gradient sampling
- arxiv url: http://arxiv.org/abs/2605.07634v1
- Date: Fri, 08 May 2026 12:01:25 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-05-11 19:43:39.027213
- Title: Robust stochastic first order methods in heavy-tailed noise via medoid mini-batch gradient sampling
- Title（参考訳）: メドイド・ミニバッチ勾配サンプリングによる重み付き雑音のロバスト確率的1次法
- Authors: Manojlo Vukovic, Dusan Jakovetic,
- Abstract要約: 1次最適化フレームワークを考えると、各イテレーションで$K$独立分散データポイントサンプル(すなわち、d.d.)が描画される。
本稿では,ロバストDescent GradientMiniという新しい一階勾配アルゴリズムを提案する。
実験結果から, R-SGD-Mini とそのクリッピング変異体は, Median-of-Means 法と比較して一貫した性能を示した。
- 参考スコア（独自算出の注目度）: 1.439518478021091
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider a first order stochastic optimization framework where, at each iteration, $K$ independent identically distributed (i.i.d.) data point samples are drawn, based on which stochastic gradients can be queried. We allow gradient noise to be heavy-tailed, with possibly infinite variances. For the considered heavy-tailed setting, many algorithmic variants have recently been proposed based on gradient clipping or other nonlinear operators (e.g., normalization) applied over noisy gradients. In this paper, we take an alternative approach and propose a novel stochastic first order method dubbed Robust Stochastic Gradient Descent with medoid mini-batch gradient sampling, R-SGD-Mini for short. The core idea of R-SGD-Mini is to split the $K$-sized data batch into $M$ distinct data chunks, form for each chunk the stochastic gradient, and update the solution estimate with respect to the stochastic gradient direction of the chunk that is medoid of gradients of all data-chunks. Under a general class of symmetric heavy-tailed gradient noises and a standard non-convex setting, we establish explicit bounds on the expected time-averaged squared gradient norm. More precisely, we show that the latter quantity converges at rate $\mathcal{O}(T^{-1})$ to a small neighborhood of zero; we explicitly characterize this neighborhood in terms of noise and algorithm's parameters. Moreover, if the time horizon is known in advance, we establish the rate of $\mathcal{O}(T^{-\frac{1}{2}}).$ Furthermore, when clipping is incorporated, we obtain convergence guaranties in the high-probability sense and recover the same rate. Experimental results indicate that R-SGD-Mini and its clipped variant consistently perform favorably compared to SGD, clipped SGD and Median-of-Means based methods.
- Abstract（参考訳）: 一階確率最適化フレームワークを考えると、各イテレーションにおいて、どの確率勾配を問合せできるかに基づいて、独立に分散された(d.d.)データポイントサンプルを$K$で描画する。
勾配ノイズは、おそらく無限のばらつきを伴う重み付きを許容する。
重み付けされた設定を考えると、最近、勾配クリッピングや他の非線形作用素(例えば正規化)に基づいて多くのアルゴリズム的変種が提案されている。
本稿では,メドイドのミニバッチ勾配サンプリングを用いたロバスト確率勾配勾配法(R-SGD-Mini)を提案する。
R-SGD-Miniの基本的な考え方は、$K$サイズのデータバッチを$M$の別個のデータチャンクに分割し、各チャンクに対して確率勾配を定式化し、すべてのデータチャンクの勾配の中間であるチャンクの確率勾配方向に関する解推定値を更新することである。
対称重み付き勾配雑音の一般クラスと標準非凸設定の下では、期待される時間平均二乗勾配ノルムに明確な境界を確立する。
より正確には、後者の量は、0の小さな近傍に$\mathcal{O}(T^{-1})$で収束していることが示される。
さらに、時間的地平線が予め知られている場合、$\mathcal{O}(T^{-\frac{1}{2}}) の速度を確立する。
さらに, クリッピングを組み込んだ場合, 高確率感の収束保証値を取得し, 同じ速度で回収する。
実験結果から,R-SGD-Miniとそのクリッピング変異体は,SGD,クリッピングSGD,Median-of-Means法と比較して一貫した性能を示した。
関連論文リスト
- Flattened one-bit stochastic gradient descent: compressed distributed optimization with controlled variance [55.01966743652196]
パラメータ・サーバ・フレームワークにおける圧縮勾配通信を用いた分散勾配降下(SGD)のための新しいアルゴリズムを提案する。
平坦な1ビット勾配勾配勾配法(FO-SGD)は2つの単純なアルゴリズムの考え方に依存している。
論文 参考訳（メタデータ） (2024-05-17T21:17:27Z) - Convergence of First-Order Methods for Constrained Nonconvex
Optimization with Dependent Data [7.513100214864646]
収束$tildeO(t-1/4)$とMoreautildeO(vareps-4)$がスムーズな非最適化のために最悪の場合の複雑性を示す。
適応的なステップサイズと最適収束度を持つ投影勾配法に基づく従属データに対する最初のオンライン非負行列分解アルゴリズムを得る。
論文 参考訳（メタデータ） (2022-03-29T17:59:10Z) - Faster One-Sample Stochastic Conditional Gradient Method for Composite
Convex Minimization [61.26619639722804]
滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。
提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
論文 参考訳（メタデータ） (2022-02-26T19:10:48Z) - Towards Noise-adaptive, Problem-adaptive Stochastic Gradient Descent [7.176107039687231]
雑音に対して勾配降下(SGD)を適応させるステップサイズスキームを設計する。
我々は、Nesterov反復によるSGDの$T$反復がほぼ最適であることを示す。
他のステップサイズスキームと比較して、新しい指数的なステップサイズスキームの有効性を実証する。
論文 参考訳（メタデータ） (2021-10-21T19:22:14Z) - 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) - High-probability Bounds for Non-Convex Stochastic Optimization with
Heavy Tails [55.561406656549686]
我々は、勾配推定が末尾を持つ可能性のある一階アルゴリズムを用いたヒルベルト非最適化を考える。
本研究では, 勾配, 運動量, 正規化勾配勾配の収束を高確率臨界点に収束させることと, 円滑な損失に対する最もよく知られた繰り返しを示す。
論文 参考訳（メタデータ） (2021-06-28T00:17:01Z) - A Variance Controlled Stochastic Method with Biased Estimation for
Faster Non-convex Optimization [0.0]
減少勾配(SVRG)の性能を向上させるために, 分散制御勾配(VCSG)という新しい手法を提案する。
ラムダ$はVCSGで導入され、SVRGによる分散の過剰還元を避ける。
$mathcalO(min1/epsilon3/2,n1/4/epsilon)$ 勾配評価の数。
論文 参考訳（メタデータ） (2021-02-19T12:22:56Z) - Carath\'eodory Sampling for Stochastic Gradient Descent [79.55586575988292]
本稿では,Tchakaloff と Carath'eodory の古典的な結果から着想を得た手法を提案する。
我々は、測定値の低減を行う降下ステップを適応的に選択する。
これをBlock Coordinate Descentと組み合わせることで、測定の削減を極めて安価に行えるようにします。
論文 参考訳（メタデータ） (2020-06-02T17:52:59Z) - Byzantine-Resilient SGD in High Dimensions on Heterogeneous Data [10.965065178451104]
ビザンチン攻撃下での主作業者アーキテクチャにおける分散勾配降下(SGD)について検討した。
我々のアルゴリズムは、最大で$frac14$のビザンティン労働者を許容できる。
論文 参考訳（メタデータ） (2020-05-16T04:15:27Z) - The Implicit Regularization of Stochastic Gradient Flow for Least
Squares [24.976079444818552]
最小二乗回帰の基本問題に適用したミニバッチ勾配勾配の暗黙正則化について検討した。
我々は勾配流と呼ばれる勾配降下と同じモーメントを持つ連続時間微分方程式を利用する。
チューニングパラメータ $lambda = 1/t$ で、リッジレグレッションを越えて、時間 $t$ での勾配フローの過剰なリスクに制限を与えます。
論文 参考訳（メタデータ） (2020-03-17T16:37:25Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。