論文の概要: A Symplectic Analysis of Alternating Mirror Descent
- arxiv url: http://arxiv.org/abs/2405.03472v2
- Date: Tue, 28 May 2024 18:39:53 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-30 22:42:17.560480
- Title: A Symplectic Analysis of Alternating Mirror Descent
- Title（参考訳）: 交互ミラーのシンプレクティック解析
- Authors: Jonas Katona, Xiuyuan Wang, Andre Wibisono,
- Abstract要約: シンプレクティック・オイラー法による連続時間ハミルトン流の離散化について検討する。
段数の順序で切り詰められたとき、修正されたハミルトン多様体上の新しい誤差境界を導出する。
もし本当なら、AMDの完全後悔は$mathcalOleft(K-1+varepsilonright)$、平均反復の双対性ギャップは$mathcalOleft(K-1+varepsilonright)$、任意の$varepsilon>0$であることを意味する。
- 参考スコア（独自算出の注目度）: 11.117320730408272
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Motivated by understanding the behavior of the Alternating Mirror Descent (AMD) algorithm for bilinear zero-sum games, we study the discretization of continuous-time Hamiltonian flow via the symplectic Euler method. We provide a framework for analysis using results from Hamiltonian dynamics, Lie algebra, and symplectic numerical integrators, with an emphasis on the existence and properties of a conserved quantity, the modified Hamiltonian (MH), for the symplectic Euler method. We compute the MH in closed-form when the original Hamiltonian is a quadratic function, and show that it generally differs from the other conserved quantity known previously in that case. We derive new error bounds on the MH when truncated at orders in the stepsize in terms of the number of iterations, $K$, and use these bounds to show an improved $\mathcal{O}(K^{1/5})$ total regret bound and an $\mathcal{O}(K^{-4/5})$ duality gap of the average iterates for AMD. Finally, we propose a conjecture which, if true, would imply that the total regret for AMD scales as $\mathcal{O}\left(K^{\varepsilon}\right)$ and the duality gap of the average iterates as $\mathcal{O}\left(K^{-1+\varepsilon}\right)$ for any $\varepsilon>0$, and we can take $\varepsilon=0$ upon certain convergence conditions for the MH.
- Abstract（参考訳）: 双線型ゼロサムゲームに対する交互ミラーD(Alternating Mirror Descent, AMD)アルゴリズムの挙動を理解することにより, シンプレクティック・オイラー法による連続時間ハミルトン流の離散化について検討する。
我々は、シンプレクティックオイラー法において、保存量である修正ハミルトニアン(MH)の存在と性質に重点を置いて、ハミルトン力学、リー代数、シンプレクティック数値積分器の結果を用いた分析フレームワークを提供する。
元のハミルトニアンが二次函数であるとき、MHを閉形式で計算し、それ以前に知られている他の保存量と一般的に異なることを示す。
AMD の平均イテレートの双対性ギャップは、改良された $\mathcal{O}(K^{1/5})$ total regret bound と $\mathcal{O}(K^{-4/5})$ $\mathcal{O}(K^{-4/5})$ $ である。
最後に、もし真であれば、AMDの完全後悔は$\mathcal{O}\left(K^{\varepsilon}\right)$、平均的なイテレートの双対性ギャップは$\mathcal{O}\left(K^{-1+\varepsilon}\right)$として、任意の$\varepsilon>0$に対して$\mathcal{O}\left(K^{-1+\varepsilon}\right)$であり、MHの収束条件によって$\varepsilon=0$を取ることができるという予想を提案する。
関連論文リスト
- Accelerated Variance-Reduced Forward-Reflected Methods for Root-Finding Problems [8.0153031008486]
そこで本研究では,Nesterovの高速前方反射法と分散還元法を新たに提案し,根絶問題の解法を提案する。
我々のアルゴリズムは単ループであり、ルートフィリング問題に特化して設計された非バイアス分散還元推定器の新たなファミリーを利用する。
論文 参考訳（メタデータ） (2024-06-04T15:23:29Z) - Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。
本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
論文 参考訳（メタデータ） (2024-04-29T15:04:07Z) - Efficient Sampling on Riemannian Manifolds via Langevin MCMC [51.825900634131486]
本稿では,Gibs 分布 $d pi* = eh d vol_g$ over aian manifold $M$ via (geometric) Langevin MCMC。
この結果は、$pi*$ が非指数的であり、$Mh$ が負のリッチ曲率を持つような一般的な設定に適用できる。
論文 参考訳（メタデータ） (2024-02-15T22:59:14Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - Unbiased constrained sampling with Self-Concordant Barrier Hamiltonian
Monte Carlo [18.14591309607824]
Barrier Hamiltonian Monte Carlo (BHMC) は、多様体 $mathrmM$ 上の Gibbs 分布 $pi$ からサンプリングすることを目的とした HMC アルゴリズムのバージョンである。
本稿では,この問題に対処するため,新たなフィルタステップである"進化チェックステップ"を提案する。
我々の主な結果は、これらの2つの新しいアルゴリズムが$pi$に対して可逆的なマルコフ連鎖を生成し、以前の実装と比較してバイアスに悩まされないことを証明している。
論文 参考訳（メタデータ） (2022-10-21T12:56:07Z) - A Law of Robustness beyond Isoperimetry [84.33752026418045]
我々は、任意の分布上でニューラルネットワークパラメータを補間する頑健性の低い$Omega(sqrtn/p)$を証明した。
次に、$n=mathrmpoly(d)$のとき、スムーズなデータに対する過度なパラメータ化の利点を示す。
我々は、$n=exp(omega(d))$ のとき、$O(1)$-Lipschitz の頑健な補間関数の存在を否定する。
論文 参考訳（メタデータ） (2022-02-23T16:10:23Z) - Hamiltonian simulation with random inputs [74.82351543483588]
ランダム初期状態を持つハミルトンシミュレーションの平均ケース性能の理論
数値的な証拠は、この理論がコンクリート模型の平均誤差を正確に特徴づけていることを示唆している。
論文 参考訳（メタデータ） (2021-11-08T19:08:42Z) - Mean-Square Analysis with An Application to Optimal Dimension Dependence
of Langevin Monte Carlo [60.785586069299356]
この研究は、2-ワッサーシュタイン距離におけるサンプリング誤差の非同相解析のための一般的な枠組みを提供する。
我々の理論解析は数値実験によってさらに検証される。
論文 参考訳（メタデータ） (2021-09-08T18:00:05Z) - Mixing Time Guarantees for Unadjusted Hamiltonian Monte Carlo [1.14219428942199]
私たちは、調整されていないハミルトンモンテカルロ(uHMC)アルゴリズムに対応するマルコフ鎖の総変動混合時間に関する定量的な上限を提供します。
2つの一般的なモデルのクラスと固定時間離散化ステップサイズ$h$ に対して、混合時間は次元に対数的にのみ依存することが示される。
UHMCにより,目標分布の精度を$varepsilon$-accurate approximation of the target distribution $mu$ in total variation distanceを実現できることを示す。
論文 参考訳（メタデータ） (2021-05-03T14:13:47Z) - Estimating 2-Sinkhorn Divergence between Gaussian Processes from
Finite-Dimensional Marginals [4.416484585765028]
エルフガウス過程 (GP) 間の2-シンクホーンの偏差を有限次元の辺分布を用いて推定する収束性について検討する。
境界値が基底値に従ってサンプリングされた場合, ほぼ確実に発散の収束を示す。
論文 参考訳（メタデータ） (2021-02-05T16:17:55Z) - Convergence of Langevin Monte Carlo in Chi-Squared and Renyi Divergence [8.873449722727026]
推定値である$widetildemathcalO(depsilon-1)$が,これらの測定値の既知レートを改善することを示す。
特に凸および1次滑らかなポテンシャルについて、LCCアルゴリズムは、これらの測定値の既知率を改善するために$widetildemathcalO(depsilon-1)$を推定する。
論文 参考訳（メタデータ） (2020-07-22T18:18:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。