論文の概要: The Last-Iterate Convergence Rate of Optimistic Mirror Descent in
Stochastic Variational Inequalities
- arxiv url: http://arxiv.org/abs/2107.01906v1
- Date: Mon, 5 Jul 2021 09:54:47 GMT
- ステータス: 処理完了
- システム内更新日: 2021-07-06 19:06:02.888407
- Title: The Last-Iterate Convergence Rate of Optimistic Mirror Descent in
Stochastic Variational Inequalities
- Title（参考訳）: 確率的変分不等式における楽観的ミラー降下のラストイテレート収束率
- Authors: Wa\"iss Azizian, Franck Iutzeler, J\'er\^ome Malick, Panayotis
Mertikopoulos
- Abstract要約: 本稿では,アルゴリズムの収束率とBregman関数によって誘導される局所幾何学との複雑な関係を示す。
この指数はアルゴリズムの最適ステップサイズポリシーと得られた最適レートの両方を決定する。
- 参考スコア（独自算出の注目度）: 29.0058976973771
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper, we analyze the local convergence rate of optimistic mirror
descent methods in stochastic variational inequalities, a class of optimization
problems with important applications to learning theory and machine learning.
Our analysis reveals an intricate relation between the algorithm's rate of
convergence and the local geometry induced by the method's underlying Bregman
function. We quantify this relation by means of the Legendre exponent, a notion
that we introduce to measure the growth rate of the Bregman divergence relative
to the ambient norm near a solution. We show that this exponent determines both
the optimal step-size policy of the algorithm and the optimal rates attained,
explaining in this way the differences observed for some popular Bregman
functions (Euclidean projection, negative entropy, fractional power, etc.).
- Abstract（参考訳）: 本稿では,確率的変分不等式における楽観的ミラー降下法の局所収束率について解析する。
解析の結果,アルゴリズムの収束率とBregman関数によって誘導される局所幾何学との複雑な関係が明らかになった。
この関係をレジェンド指数を用いて定量化し, 解近傍の環境ノルムに対するブレグマンの発散速度を測定するために導入する概念である。
この指数はアルゴリズムの最適ステップサイズポリシーと達成した最適レートの両方を決定づけるものであり、一般的なブレグマン関数(ユークリッド射影、負エントロピー、分数パワーなど)で観測される差を説明する。
).
関連論文リスト
- Analytical Approximation of the ELBO Gradient in the Context of the Clutter Problem [0.0]
変分推論問題におけるエビデンス下界(ELBO)の勾配を近似する解析解を提案する。
提案手法は線形計算複雑性とともに精度と収束率を示す。
論文 参考訳（メタデータ） (2024-04-16T13:19:46Z) - Distributed Markov Chain Monte Carlo Sampling based on the Alternating
Direction Method of Multipliers [143.6249073384419]
本論文では,乗算器の交互方向法に基づく分散サンプリング手法を提案する。
我々は,アルゴリズムの収束に関する理論的保証と,その最先端性に関する実験的証拠の両方を提供する。
シミュレーションでは,線形回帰タスクとロジスティック回帰タスクにアルゴリズムを配置し,その高速収束を既存の勾配法と比較した。
論文 参考訳（メタデータ） (2024-01-29T02:08:40Z) - Stochastic Mirror Descent for Large-Scale Sparse Recovery [13.500750042707407]
本稿では,2次近似の高次元スパースパラメータの統計的推定への応用について論じる。
提案アルゴリズムは, 回帰器分布の弱い仮定の下で, 推定誤差の最適収束を実現する。
論文 参考訳（メタデータ） (2022-10-23T23:23:23Z) - Stochastic Approximation with Decision-Dependent Distributions: Asymptotic Normality and Optimality [8.771678221101368]
我々は、アルゴリズムが使用するデータ分布が反復列に沿って進化する決定依存問題に対する近似を解析する。
軽微な仮定の下では、アルゴリズムの反復と解の偏差は正規であることを示す。
また,平均化アルゴリズムの性能は局所的に最小限であることを示す。
論文 参考訳（メタデータ） (2022-07-09T01:44:17Z) - Optimal variance-reduced stochastic approximation in Banach spaces [114.8734960258221]
可分バナッハ空間上で定義された収縮作用素の定点を推定する問題について検討する。
演算子欠陥と推定誤差の両方に対して漸近的でない境界を確立する。
論文 参考訳（メタデータ） (2022-01-21T02:46:57Z) - Amortized Implicit Differentiation for Stochastic Bilevel Optimization [53.12363770169761]
決定論的条件と決定論的条件の両方において、二段階最適化問題を解決するアルゴリズムのクラスについて検討する。
厳密な勾配の推定を補正するために、ウォームスタート戦略を利用する。
このフレームワークを用いることで、これらのアルゴリズムは勾配の偏りのない推定値にアクセス可能な手法の計算複雑性と一致することを示す。
論文 参考訳（メタデータ） (2021-11-29T15:10:09Z) - Statistical optimality and stability of tangent transform algorithms in
logit models [6.9827388859232045]
我々は,データ生成過程の条件として,ロジカルオプティマによって引き起こされるリスクに対して,非漸近上界を導出する。
特に,データ生成過程の仮定なしにアルゴリズムの局所的変動を確立する。
我々は,大域収束が得られる半直交設計を含む特別な場合について検討する。
論文 参考訳（メタデータ） (2020-10-25T05:15:13Z) - Robust, Accurate Stochastic Optimization for Variational Inference [68.83746081733464]
また, 共通最適化手法は, 問題が適度に大きい場合, 変分近似の精度が低下することを示した。
これらの結果から,基礎となるアルゴリズムをマルコフ連鎖の生成とみなして,より堅牢で正確な最適化フレームワークを開発する。
論文 参考訳（メタデータ） (2020-09-01T19:12:11Z) - Sparse recovery by reduced variance stochastic approximation [5.672132510411465]
雑音観測によるスパース信号回復問題に対する反復2次最適化ルーチンの適用について論じる。
本稿では,Median-of-Meansのような手法を用いて,対応するソリューションの信頼性を向上する方法について述べる。
論文 参考訳（メタデータ） (2020-06-11T12:31:20Z) - A Distributional Analysis of Sampling-Based Reinforcement Learning
Algorithms [67.67377846416106]
定常ステップサイズに対する強化学習アルゴリズムの理論解析に対する分布的アプローチを提案する。
本稿では,TD($lambda$)や$Q$-Learningのような値ベースの手法が,関数の分布空間で制約のある更新ルールを持つことを示す。
論文 参考訳（メタデータ） (2020-03-27T05:13:29Z) - Is Temporal Difference Learning Optimal? An Instance-Dependent Analysis [102.29671176698373]
我々は、割引決定過程における政策評価の問題に対処し、生成モデルの下で、ll_infty$errorに対するマルコフに依存した保証を提供する。
我々は、ポリシー評価のために、局所ミニマックス下限の両漸近バージョンと非漸近バージョンを確立し、アルゴリズムを比較するためのインスタンス依存ベースラインを提供する。
論文 参考訳（メタデータ） (2020-03-16T17:15:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。