論文の概要: Gaussian Approximation and Multiplier Bootstrap for Stochastic Gradient Descent
- arxiv url: http://arxiv.org/abs/2502.06719v1
- Date: Mon, 10 Feb 2025 17:49:05 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-11 14:33:15.507721
- Title: Gaussian Approximation and Multiplier Bootstrap for Stochastic Gradient Descent
- Title(参考訳): 確率勾配の老化に対するガウス近似と乗算ブートストラップ
- Authors: Marina Sheshukova, Sergey Samsonov, Denis Belomestny, Eric Moulines, Qi-Man Shao, Zhuo-Song Zhang, Alexey Naumov,
- Abstract要約: 我々は、勾配勾配のポリアック=ルパート平均的反復に対する中心極限定理において、非漸近収束率を確立する。
最適化問題に対する信頼度セットを構築するための乗算器ブートストラップの非漸近的妥当性を実証する。
- 参考スコア(独自算出の注目度): 14.19520637866741
- License:
- Abstract: In this paper, we establish non-asymptotic convergence rates in the central limit theorem for Polyak-Ruppert-averaged iterates of stochastic gradient descent (SGD). Our analysis builds on the result of the Gaussian approximation for nonlinear statistics of independent random variables of Shao and Zhang (2022). Using this result, we prove the non-asymptotic validity of the multiplier bootstrap for constructing the confidence sets for the optimal solution of an optimization problem. In particular, our approach avoids the need to approximate the limiting covariance of Polyak-Ruppert SGD iterates, which allows us to derive approximation rates in convex distance of order up to $1/\sqrt{n}$.
- Abstract(参考訳): 本稿では,Polyak-Ruppert-averaged iterates of stochastic gradient descent (SGD)に対する中心極限定理において,非漸近収束率を確立する。
本分析は,Shao と Zhang (2022) の独立確率変数の非線形統計量に対するガウス近似の結果に基づく。
この結果を用いて、最適化問題の最適解に対する信頼性セットを構築するための乗算器ブートストラップの非漸近妥当性を証明した。
特に、我々のアプローチは、Polyak-Ruppert SGD 反復の制限共分散を近似する必要性を回避し、1/\sqrt{n}$までの凸距離での近似率を導出することができる。
関連論文リスト
- Quantitative Error Bounds for Scaling Limits of Stochastic Iterative Algorithms [10.022615790746466]
アルゴリズムのサンプルパスとOrnstein-Uhlenbeck近似の非漸近関数近似誤差を導出する。
我々は、L'evy-Prokhorov と有界ワッサーシュタイン距離という2つの一般的な測度で誤差境界を構築するために、主要な結果を使用する。
論文 参考訳(メタデータ) (2025-01-21T15:29:11Z) - Robust Stochastic Optimization via Gradient Quantile Clipping [6.2844649973308835]
グラディエントDescent(SGD)のための量子クリッピング戦略を導入する。
通常のクリッピングチェーンとして、グラデーション・ニュー・アウトリージを使用します。
本稿では,Huberiles を用いたアルゴリズムの実装を提案する。
論文 参考訳(メタデータ) (2023-09-29T15:24:48Z) - Curvature-Independent Last-Iterate Convergence for Games on Riemannian
Manifolds [77.4346324549323]
本研究では, 多様体の曲率に依存しないステップサイズが, 曲率非依存かつ直線的最終点収束率を達成することを示す。
我々の知る限りでは、曲率非依存率や/または最終点収束の可能性はこれまでに検討されていない。
論文 参考訳(メタデータ) (2023-06-29T01:20:44Z) - Online Bootstrap Inference with Nonconvex Stochastic Gradient Descent
Estimator [0.0]
本稿では,凸問題の文脈における統計的推論のための勾配降下(SGD)の理論的性質について検討する。
多重誤差最小値を含む2つの干渉手順を提案する。
論文 参考訳(メタデータ) (2023-06-03T22:08:10Z) - Parameter-free projected gradient descent [0.0]
我々は、射影勾配 Descent (PGD) を用いて、閉凸集合上の凸関数を最小化する問題を考える。
本稿では,AdaGradのパラメータフリーバージョンを提案する。これは初期化と最適化の距離に適応し,下位段階の平方ノルムの和に適応する。
提案アルゴリズムはプロジェクションステップを処理でき、リスタートを伴わず、従来のPGDと比較して軌道に沿ってリウィーディングや追加評価を行うことができる。
論文 参考訳(メタデータ) (2023-05-31T07:22:44Z) - Kinetic Langevin MCMC Sampling Without Gradient Lipschitz Continuity --
the Strongly Convex Case [0.0]
目的がグローバルリプシッツであると仮定することなく,ハミルトン条件下での対数凹面分布からのサンプリングを検討する。
本稿では,多角勾配(テード)オイラースキームに基づく2つのアルゴリズムを提案し,各アルゴリズムのプロセスの法則と対象測度との間の非漸近的な2-ワッサーシュタイン距離を求める。
論文 参考訳(メタデータ) (2023-01-19T12:32:41Z) - Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector
Problems [98.34292831923335]
オンライン相関解析の問題から,emphStochastic Scaled-Gradient Descent (SSD)アルゴリズムを提案する。
我々はこれらのアイデアをオンライン相関解析に適用し、局所収束率を正規性に比例した最適な1時間スケールのアルゴリズムを初めて導いた。
論文 参考訳(メタデータ) (2021-12-29T18:46:52Z) - Differentiable Annealed Importance Sampling and the Perils of Gradient
Noise [68.44523807580438]
Annealed importance sample (AIS) と関連するアルゴリズムは、限界推定のための非常に効果的なツールである。
差別性は、目的として限界確率を最適化する可能性を認めるため、望ましい性質である。
我々はメトロポリス・ハスティングスのステップを放棄して微分可能アルゴリズムを提案し、ミニバッチ計算をさらに解き放つ。
論文 参考訳(メタデータ) (2021-07-21T17:10:14Z) - High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。
そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
論文 参考訳(メタデータ) (2021-06-10T17:54:21Z) - 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) - GradientDICE: Rethinking Generalized Offline Estimation of Stationary
Values [75.17074235764757]
対象ポリシーの状態分布とサンプリング分布の密度比を推定するグラディエントDICEを提案する。
GenDICEはそのような密度比を推定するための最先端技術である。
論文 参考訳(メタデータ) (2020-01-29T22:10:11Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。