論文の概要: Strong Gaussian Approximation of Constant-Learning-Rate SGD: Bias and Trajectory Inference
- arxiv url: http://arxiv.org/abs/2610.14567v1
- Date: Sat, 10 Oct 2026 04:38:25 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-15 21:06:15.067428
- Title: Strong Gaussian Approximation of Constant-Learning-Rate SGD: Bias and Trajectory Inference
- Title（参考訳）: 定学習率SGDの強ガウス近似:バイアスと軌道推定
- Abstract要約: 我々は、同じ空間と境界上の単純なガウス過程を構築し、確率において、誤差とそれぞれの極限の間の最大差を推定する。
最適点を中心とする累積誤差に対しては、まず学習率が mathbbR+$ の定数 $c に対して $_n=fraccsqrt n+o(n-1/2)$ のときに KMT 型近似境界を得る。
- 参考スコア（独自算出の注目度）: 1.4037095606573828
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This paper develops strong Gaussian approximations (KMT type) for constant learning rate stochastic gradient descent (SGD). We work with heavy tailed noise and assume that the number of iterates grows and the learning rate shrinks simultaneously. Our work constructs simple Gaussian processes on the same space and bounds, in probability, the maximum difference between the SGD errors and their respective limits. While there exist central limit theorems for constant rate SGD centered at the optimum, these only provide individual iterate inference. By contrast, our quenched KMT approximations allow for finite sample, simultaneous, whole-trajectory-level inference and imply stochastic process convergence (Functional Central Limit Theorems (FCLTs)). For accumulated errors centered at the true optimum, we first obtain a KMT-type approximation bound when the learning rate scales as $γ_n=\frac{c}{\sqrt n}+o(n^{-1/2})$ for a constant $c \in \mathbb{R}^+$ and $n$ iterations. The result reveals a trade off between controlling the bias of SGD and the initialization effect, with no learning rate scaling generally making both contributions vanish in the accumulated error limit. To eliminate these contributions, we consider a Burn in scheme and Richardson-Romberg extrapolation and prove respective KMT and FCLT theorems. We also prove a finite-horizon KMT-type approximation and FCLT for the rescaled iterate trajectory to a stationary Ornstein--Uhlenbeck (OU) process. We consider applications in risk control and simultaneous inference and perform simulations to illustrate our results.
- Abstract（参考訳）: 本稿では,定常学習速度確率勾配降下(SGD)のための強ガウス近似(KMT型)を開発する。
我々は、重く尾のついたノイズで作業し、繰り返しの数が増加し、学習率が同時に減少すると仮定する。
我々の研究は、同じ空間上の単純なガウス過程と、確率において、SGD誤差とそれぞれの極限の間の最大差を構築する。
最適点を中心とする定数速度 SGD に対する中心極限定理は存在するが、これらは個別の反復推論を与えるのみである。
対照的に、クエンチされたKMT近似は有限標本、全軌跡レベルの同時推論および確率過程収束(Functional Central Limit Theorems (FCLTs))を可能にする。
真の最適点を中心とする累積誤差に対して、学習速度が$γ_n=\frac{c}{\sqrt n}+o(n^{-1/2})$で、定数$c \in \mathbb{R}^+$および$n$反復に対してスケールすると、KMT型近似境界が得られる。
その結果、SGDのバイアスと初期化効果のトレードオフが明らかとなり、学習率のスケーリングは一般的には、両方のコントリビューションが累積誤差限界で消滅する。
これらの寄与を排除するために、Burn in scheme と Richardson-Romberg の外挿を考え、それぞれの KMT と FCLT の定理を証明した。
また, 定常オーンシュタイン-ウレンベック (OU) 過程に再スケールした反復軌道に対する有限水平KMT型近似とFCLTを証明した。
我々はリスク制御と同時推論の応用を検討し、その結果を説明するシミュレーションを行う。
関連論文リスト
- Steady-State Convergence of Stochastic Approximation [19.40811084751516]
我々はマルコフ型乗法雑音によって駆動される定数ステップサイズの収縮型SAに対する統一SSC理論を開発する。
主要な方法論的貢献は、トラクタブルな補助力学への元の再帰を段階的に減少させる多段階フレームワークである。
主次バイアスは、スムーズな状態における$$-orderバイアスとは対照的に、次数$sqrt$の普遍性であることが示される。
論文 参考訳（メタデータ） (2026-09-14T02:15:03Z) - Closing the Approximation Gap of Partial AUC Optimization: A Tale of Two Formulations [121.39938773554523]
ROC曲線の下の領域(AUC)は、クラス不均衡と決定制約の両方を持つ実世界のシナリオにおける重要な評価指標である。
PAUC最適化の近似ギャップを埋めるために,2つの簡単なインスタンス単位のミニマックス修正を提案する。
得られたアルゴリズムは、サンプルサイズと典型的な一方方向と双方向のPAUCに対して$O(-2/3)$の収束率の線形パーイテレーション計算複雑性を享受する。
論文 参考訳（メタデータ） (2025-12-01T02:52:33Z) - Nonasymptotic CLT and Error Bounds for Two-Time-Scale Stochastic Approximation [12.69327994479157]
We consider linear two-time-scale approximation algorithm driven by martingale noise。
我々は、PolyakRuppert平均化を用いた2時間スケール近似のためのワッサーシュタイン-1距離に関する最初の漸近的中心極限定理を導出した。
論文 参考訳（メタデータ） (2025-02-14T03:20:30Z) - Gaussian Approximation and Multiplier Bootstrap for Stochastic Gradient Descent [14.19520637866741]
信頼性セット構築のための乗算器ブートストラップの非漸近的妥当性を確立する。
我々は1/sqrtn$までの凸距離の近似レートを導出する。
論文 参考訳（メタデータ） (2025-02-10T17:49:05Z) - Compressed and distributed least-squares regression: convergence rates with applications to Federated Learning [11.870656106069447]
機械学習の勾配アルゴリズムに対する圧縮の影響について検討する。
いくつかの非バイアス圧縮演算子間の収束率の差を強調した。
我々はその結果を連合学習の事例にまで拡張する。
論文 参考訳（メタデータ） (2023-08-02T18:02:00Z) - Kernel-based off-policy estimation without overlap: Instance optimality
beyond semiparametric efficiency [53.90687548731265]
本研究では,観測データに基づいて線形関数を推定するための最適手順について検討する。
任意の凸および対称函数クラス $mathcalF$ に対して、平均二乗誤差で有界な非漸近局所ミニマックスを導出する。
論文 参考訳（メタデータ） (2023-01-16T02:57:37Z) - Faster One-Sample Stochastic Conditional Gradient Method for Composite
Convex Minimization [61.26619639722804]
滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。
提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
論文 参考訳（メタデータ） (2022-02-26T19:10:48Z) - Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
カーネルヒルベルト空間を用いて、無限水平割引マルコフ報酬過程の値関数を推定する。
我々は、関連するカーネル演算子の固有値に明示的に依存した誤差の非漸近上界を導出する。
MRP のサブクラスに対する minimax の下位境界を証明する。
論文 参考訳（メタデータ） (2021-09-24T14:48:20Z) - Mean-Square Analysis with An Application to Optimal Dimension Dependence
of Langevin Monte Carlo [60.785586069299356]
この研究は、2-ワッサーシュタイン距離におけるサンプリング誤差の非同相解析のための一般的な枠組みを提供する。
我々の理論解析は数値実験によってさらに検証される。
論文 参考訳（メタデータ） (2021-09-08T18:00:05Z) - On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and
Non-Asymptotic Concentration [115.1954841020189]
The inequality and non-asymptotic properties of approximation procedure with Polyak-Ruppert averaging。
一定のステップサイズと無限大となる反復数を持つ平均的反復数に対する中心極限定理(CLT)を証明する。
論文 参考訳（メタデータ） (2020-04-09T17:54:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。