論文の概要: Exponential Concentration of Stochastic Approximation with Non-vanishing
Gradient
- arxiv url: http://arxiv.org/abs/2208.07243v3
- Date: Thu, 3 Aug 2023 19:22:21 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-07 16:42:13.797342
- Title: Exponential Concentration of Stochastic Approximation with Non-vanishing
Gradient
- Title(参考訳): 非消滅勾配による確率近似の指数集中
- Authors: Kody Law and Neil Walton and Shangda Yang
- Abstract要約: 近似アルゴリズムの振る舞いを分析し,各ステップで目標に向かって進行する。
非消滅マルコフを持つ射影勾配 Descent に対して、我々の結果は$O(t)$および線形収束率を証明するのに使うことができる。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We analyze the behavior of stochastic approximation algorithms where
iterates, in expectation, make progress towards an objective at each step. When
progress is proportional to the step size of the algorithm, we prove
exponential concentration bounds. These tail-bounds contrast asymptotic
normality results which are more frequently associated with stochastic
approximation. The methods that we develop rely on a geometric ergodicity
proof. This extends a result on Markov chains due to Hajek (1982) to the area
of stochastic approximation algorithms. For Projected Stochastic Gradient
Descent with a non-vanishing gradient, our results can be used to prove
$O(1/t)$ and linear convergence rates.
- Abstract(参考訳): 我々は,確率近似アルゴリズムの振る舞いを分析し,各ステップで目標に向かって進行していくことを期待する。
進行がアルゴリズムのステップサイズに比例すると指数集中境界が証明される。
これらのテールバウンドのコントラスト漸近正規性の結果は、より頻繁に確率近似と関連付けられる。
私たちが開発する手法は幾何学的エルゴディディティ証明に依存している。
これはHajek (1982) によるマルコフ連鎖上の結果を確率近似アルゴリズムの領域に拡張する。
非消滅勾配の射影確率勾配 Descent に対して、この結果は$O(1/t)$と線形収束率の証明に利用できる。
関連論文リスト
- Variance reduction techniques for stochastic proximal point algorithms [5.871583927216651]
本稿では,SVRG,SAGAの近位バージョンと,そのスムーズな凸関数に対する変種について紹介する。
数値実験により, 勾配法に対する近似分散低減法の利点を実証した。
論文 参考訳(メタデータ) (2023-08-18T05:11:50Z) - Asymptotically efficient one-step stochastic gradient descent [62.997667081978825]
これはフィッシャースコアリングアルゴリズムの単一ステップで補正された対数型関数の勾配勾配に基づいている。
理論的およびシミュレーションにより、これは平均勾配あるいは適応勾配勾配の通常の勾配勾配の代替として興味深いものであることをi.d設定で示す。
論文 参考訳(メタデータ) (2023-06-09T13:43:07Z) - A Gradient Smoothed Functional Algorithm with Truncated Cauchy Random
Perturbations for Stochastic Optimization [10.820943271350442]
本稿では,雑音の多いコストサンプルに対する期待値であるスムーズな目的関数を最小化するための凸勾配アルゴリズムを提案する。
また,本アルゴリズムは局所最小値への収束を示唆し,レートリリアを回避できることも示している。
論文 参考訳(メタデータ) (2022-07-30T18:50:36Z) - Stochastic Approximation with Decision-Dependent Distributions: Asymptotic Normality and Optimality [8.771678221101368]
我々は、アルゴリズムが使用するデータ分布が反復列に沿って進化する決定依存問題に対する近似を解析する。
軽微な仮定の下では、アルゴリズムの反復と解の偏差は正規であることを示す。
また,平均化アルゴリズムの性能は局所的に最小限であることを示す。
論文 参考訳(メタデータ) (2022-07-09T01:44:17Z) - Heavy-tailed Streaming Statistical Estimation [58.70341336199497]
ストリーミング$p$のサンプルから重み付き統計推定の課題を考察する。
そこで我々は,傾きの雑音に対して,よりニュアンスな条件下での傾きの傾きの低下を設計し,より詳細な解析を行う。
論文 参考訳(メタデータ) (2021-08-25T21:30:27Z) - Differentiable Annealed Importance Sampling and the Perils of Gradient
Noise [68.44523807580438]
Annealed importance sample (AIS) と関連するアルゴリズムは、限界推定のための非常に効果的なツールである。
差別性は、目的として限界確率を最適化する可能性を認めるため、望ましい性質である。
我々はメトロポリス・ハスティングスのステップを放棄して微分可能アルゴリズムを提案し、ミニバッチ計算をさらに解き放つ。
論文 参考訳(メタデータ) (2021-07-21T17:10:14Z) - On the Convergence of Stochastic Extragradient for Bilinear Games with
Restarted Iteration Averaging [96.13485146617322]
本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。
平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
論文 参考訳(メタデータ) (2021-06-30T17:51:36Z) - Spectral clustering under degree heterogeneity: a case for the random
walk Laplacian [83.79286663107845]
本稿では,ランダムウォークラプラシアンを用いたグラフスペクトル埋め込みが,ノード次数に対して完全に補正されたベクトル表現を生成することを示す。
次数補正ブロックモデルの特別な場合、埋め込みはK個の異なる点に集中し、コミュニティを表す。
論文 参考訳(メタデータ) (2021-05-03T16:36:27Z) - ROOT-SGD: Sharp Nonasymptotics and Asymptotic Efficiency in a Single
Algorithm [77.71051081132912]
第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。
emphRecursive One-Over-T Root (ROOTSGD) と呼ばれる小説を考案する。
有限サンプル勾配, 漸近感覚, 感覚を同時に達成することを証明する。
論文 参考訳(メタデータ) (2020-08-28T14:46:56Z) - Asymptotic Analysis of Conditioned Stochastic Gradient Descent [0.0]
本研究では、勾配方向の事前条件付けに基づいて、条件付きSGDと呼ばれる勾配降下法(SGD)アルゴリズムのクラスについて検討する。
ほぼ確実に、独立した関心を持つかもしれない収束結果が提示される。
論文 参考訳(メタデータ) (2020-06-04T10:08:05Z) - Non-asymptotic bounds for stochastic optimization with biased noisy
gradient oracles [8.655294504286635]
関数の測定値が推定誤差を持つ設定を捉えるために,バイアス付き勾配オラクルを導入する。
提案するオラクルは,例えば,独立分散シミュレーションと同一分散シミュレーションのバッチによるリスク計測推定の実践的な状況にある。
論文 参考訳(メタデータ) (2020-02-26T12:53:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。