論文の概要: When is the Convergence Time of Langevin Algorithms Dimension
Independent? A Composite Optimization Viewpoint
- arxiv url: http://arxiv.org/abs/2110.01827v1
- Date: Tue, 5 Oct 2021 05:40:06 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-06 22:54:16.712392
- Title: When is the Convergence Time of Langevin Algorithms Dimension
Independent? A Composite Optimization Viewpoint
- Title（参考訳）: ランゲヴィンアルゴリズムの収束時間はいつ独立か?
複合最適化の視点
- Authors: Yoav Freund, Yi-An Ma, Tong Zhang
- Abstract要約: ランゲヴィンアルゴリズムのすべての既知収束速度は問題の次元に依存するが、最適化のための収束速度は凸問題に対しては次元自由である。
本稿では、リプシッツや平滑な凸問題のいずれかの大きなクラスに対して、この問題に対する肯定的な答えを提供する。
- 参考スコア（独自算出の注目度）: 26.967330269493097
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: There has been a surge of works bridging MCMC sampling and optimization, with
a specific focus on translating non-asymptotic convergence guarantees for
optimization problems into the analysis of Langevin algorithms in MCMC
sampling. A conspicuous distinction between the convergence analysis of
Langevin sampling and that of optimization is that all known convergence rates
for Langevin algorithms depend on the dimensionality of the problem, whereas
the convergence rates for optimization are dimension-free for convex problems.
Whether a dimension independent convergence rate can be achieved by Langevin
algorithm is thus a long-standing open problem. This paper provides an
affirmative answer to this problem for large classes of either Lipschitz or
smooth convex problems with normal priors. By viewing Langevin algorithm as
composite optimization, we develop a new analysis technique that leads to
dimension independent convergence rates for such problems.
- Abstract（参考訳）: MCMCサンプリングと最適化の橋渡し作業が急増しており、MCMCサンプリングにおいて最適化問題に対する非漸近収束保証をランゲヴィンアルゴリズムの解析に翻訳することに焦点を当てている。
ランゲヴィンサンプリングの収束解析と最適化の区別は、ランゲヴィンアルゴリズムの既知収束速度が問題の次元に依存するのに対して、最適化の収束速度は凸問題に対して次元自由である点である。
次元独立収束率がランジュバンアルゴリズムによって達成できるかどうかは、長年の未解決問題である。
本稿では、リプシッツや平滑な凸問題のいずれかの大きなクラスに対して、この問題に対する肯定的な答えを提供する。
本稿では,Langevinアルゴリズムを複合最適化とみなして,次元独立収束率を導出する新たな解析手法を提案する。
関連論文リスト
- An Improved Analysis of Langevin Algorithms with Prior Diffusion for
Non-Log-Concave Sampling [27.882407333690267]
本研究では, 先行拡散を用いた改良型ランゲヴィンアルゴリズムが, 強対数対数対象分布に対して独立に次元を収束させることができることを示す。
また、修正したランゲヴィンアルゴリズムは、異なるステップサイズスケジュールを持つKL発散の次元非依存収束も得ることを証明した。
論文 参考訳（メタデータ） (2024-03-10T11:50:34Z) - Convergence of Expectation-Maximization Algorithm with Mixed-Integer Optimization [5.319361976450982]
本稿では,特定の種類のEMアルゴリズムの収束を保証する一連の条件を紹介する。
本研究では,混合整数非線形最適化問題の解法として,反復アルゴリズムの新しい解析手法を提案する。
論文 参考訳（メタデータ） (2024-01-31T11:42:46Z) - A simple uniformly optimal method without line search for convex optimization [9.280355951055865]
パラメータが優先されていない凸最適化問題の解法として最適収束率を得るには,線探索が過剰であることを示す。
滑らかな凸最適化のために最適な$mathcalO (1/k2)$収束率を達成できるAC-FGMと呼ばれる新しい勾配降下型アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-10-16T05:26:03Z) - Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。
微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
論文 参考訳（メタデータ） (2023-02-24T18:41:48Z) - First-Order Algorithms for Min-Max Optimization in Geodesic Metric
Spaces [93.35384756718868]
min-maxアルゴリズムはユークリッド設定で解析されている。
指数関数法 (RCEG) が線形速度で最終収束を補正したことを証明した。
論文 参考訳（メタデータ） (2022-06-04T18:53:44Z) - Constrained Langevin Algorithms with L-mixing External Random Variables [0.0]
ランゲヴィンサンプリングアルゴリズムは付加雑音で拡張される。
学習のためのランゲヴィンアルゴリズムの非同化解析は広く研究されている。
ここでは,Langevinアルゴリズムが22点の偏差を達成することを示す。
論文 参考訳（メタデータ） (2022-05-27T18:44:35Z) - Non-Convex Optimization with Certificates and Fast Rates Through Kernel
Sums of Squares [68.8204255655161]
非最適化近似問題を考える。
本稿では,最優先計算を保証するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-04-11T09:37:04Z) - Distributed stochastic optimization with large delays [59.95552973784946]
大規模最適化問題を解決する最も広く使われている手法の1つは、分散非同期勾配勾配(DASGD)である。
DASGDは同じ遅延仮定の下で大域的最適実装モデルに収束することを示す。
論文 参考訳（メタデータ） (2021-07-06T21:59:49Z) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。
我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文 参考訳（メタデータ） (2020-06-11T17:43:19Z) - Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。
我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。
得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文 参考訳（メタデータ） (2020-02-21T17:45:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。