論文の概要: Optimization, Isoperimetric Inequalities, and Sampling via Lyapunov Potentials
- arxiv url: http://arxiv.org/abs/2410.02979v3
- Date: Tue, 04 Mar 2025 18:48:15 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-03-05 18:50:36.921959
- Title: Optimization, Isoperimetric Inequalities, and Sampling via Lyapunov Potentials
- Title（参考訳）: リアプノフポテンシャルによる最適化、等尺不等式、サンプリング
- Authors: August Y. Chen, Karthik Sridharan,
- Abstract要約: すべての初期化からグラディエントフローを用いた任意のFの最適性は、低温におけるギブス測度 mu_beta = e-beta F/Z のポインカーの不等式を意味することを示す。
特に、mu_beta が Poincar'e の不等式を β >= Omega(d) に対して定数 OC'+1/beta で満たすことを確立し、ここで C' は Mu_beta の Poincar'e 定数であり、F の大域最小化の近傍に制限される。
- 参考スコア（独自算出の注目度）: 8.687754908398079
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper, we prove that optimizability of any F using Gradient Flow from all initializations implies a Poincar\'e Inequality for Gibbs measures mu_{beta} = e^{-\beta F}/Z at low temperature. In particular, under mild regularity assumptions on the convergence rate of Gradient Flow, we establish that mu_{beta} satisfies a Poincar\'e Inequality with constant O(C'+1/beta) for beta >= Omega(d), where C' is the Poincar\'e constant of mu_{beta} restricted to a neighborhood of the global minimizers of F. Under an additional mild condition on F, we show that mu_{beta} satisfies a Log-Sobolev Inequality with constant O(S beta C') where S denotes the second moment of mu_{beta}. Here asymptotic notation hides F-dependent parameters. At a high level, this establishes that optimizability via Gradient Flow from every initialization implies a Poincar\'e and Log-Sobolev Inequality for the low-temperature Gibbs measure, which in turn imply sampling from all initializations. Analogously, we establish that under the same assumptions, if F can be initialized from everywhere except some set S, then mu_{beta} satisfies a Weak Poincar\'e Inequality with parameters (C', mu_{beta}(S)) for \beta = Omega(d). At a high level, this shows while optimizability from 'most' initializations implies a Weak Poincar\'e Inequality, which in turn implies sampling from suitable warm starts. Our regularity assumptions are mild and as a consequence, we show we can efficiently sample from several new natural and interesting classes of non-log-concave densities, an important setting with relatively few examples. As another corollary, we obtain efficient discrete-time sampling results for log-concave measures satisfying milder regularity conditions than smoothness, similar to Lehec (2023).
- Abstract（参考訳）: 本稿では、すべての初期化からグラディエントフローを用いた任意のFの最適性は、低温におけるギブス測度 mu_{beta} = e^{-\beta F}/Z のポアンカーの不等式を意味することを示す。
特に、グラディエントフローの収束率に関する穏やかな正則性仮定の下で、mu_{beta} が定数 O(C'+1/beta) と定数 O(C'+1/beta) をベータ >= Omega(d) を満たすことを証明している。
ここでの漸近記法はF依存的パラメータを隠蔽する。
高いレベルでは、すべての初期化からのグラディエントフローによる最適化性は、低温ギブズ測度に対するポアンカーイーとログソボレフの不等式を意味し、全ての初期化から標本化することを暗示する。
類似して、同じ仮定の下で、F が集合 S 以外の至る所から初期化できるならば、mu_{beta} は \beta = Omega(d) に対してパラメータ (C', mu_{beta}(S)) で弱ポアンカーの不等式を満たす。
高いレベルでは、「最初期の」初期化からの最適化性は弱ポアンカーの不等式を意味するが、これは結果として適切な温暖開始点からのサンプリングを意味する。
我々の正則性仮定は穏やかであり、結果として、比較的少数の例で重要な設定である、非対数凹密度の新しい自然および興味深いクラスを効率的にサンプリングできることが示される。
また,Lhec (2023) と同様, 円滑性よりも緩やかな規則性条件を満たす対数凹度測定のための効率的な離散時間サンプリング結果を得た。
関連論文リスト
- Stochastic Approximation with Unbounded Markovian Noise: A General-Purpose Theorem [7.443139252028032]
非有界な状態空間と報酬関数を持つ平均逆強化学習を考える。
近年の研究では、この問題をアクター批判の枠組みで研究している。
線形関数近似を用いた時間差分学習(TD)について検討した。
論文 参考訳（メタデータ） (2024-10-29T03:40:53Z) - Faster Sampling via Stochastic Gradient Proximal Sampler [28.422547264326468]
非log-concave分布からのサンプリングのための近位サンプリング器 (SPS) について検討した。
対象分布への収束性は,アルゴリズムの軌道が有界である限り保証可能であることを示す。
我々は、Langevin dynamics(SGLD)とLangevin-MALAの2つの実装可能な変種を提供し、SPS-SGLDとSPS-MALAを生み出した。
論文 参考訳（メタデータ） (2024-05-27T00:53:18Z) - A New Random Reshuffling Method for Nonsmooth Nonconvex Finite-sum Optimization [6.314057999212246]
ランダムリシャッフル技術は、ニューラルネットワークのような大規模アプリケーションで使用される。
本稿では,ノルムPRRが生成するランダムリシャッフル型反復が線形設定に収束することを示す。
最後に,提案手法に適用可能な最終収束率を導出する。
論文 参考訳（メタデータ） (2023-12-02T07:12:00Z) - Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems [56.86067111855056]
構造密度の重み付き雑音によるクリップ最適化問題を考察する。
勾配が有限の順序モーメントを持つとき、$mathcalO(K-(alpha - 1)/alpha)$よりも高速な収束率が得られることを示す。
得られた推定値が無視可能なバイアスと制御可能な分散を持つことを示す。
論文 参考訳（メタデータ） (2023-11-07T17:39:17Z) - Robust Stochastic Optimization via Gradient Quantile Clipping [6.2844649973308835]
グラディエントDescent(SGD)のための量子クリッピング戦略を導入する。
通常のクリッピングチェーンとして、グラデーション・ニュー・アウトリージを使用します。
本稿では,Huberiles を用いたアルゴリズムの実装を提案する。
論文 参考訳（メタデータ） (2023-09-29T15:24:48Z) - Sampling from Gaussian Process Posteriors using Stochastic Gradient
Descent [43.097493761380186]
勾配アルゴリズムは線形系を解くのに有効な方法である。
最適値に収束しない場合であっても,勾配降下は正確な予測を導出することを示す。
実験的に、勾配降下は十分に大規模または不条件の回帰タスクにおいて最先端の性能を達成する。
論文 参考訳（メタデータ） (2023-06-20T15:07:37Z) - High-Probability Bounds for Stochastic Optimization and Variational
Inequalities: the Case of Unbounded Variance [59.211456992422136]
制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。
これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
論文 参考訳（メタデータ） (2023-02-02T10:37:23Z) - A Fully First-Order Method for Stochastic Bilevel Optimization [8.663726907303303]
一階勾配オラクルのみが利用できる場合、制約のない二段階最適化問題を考える。
完全一階近似法(F2SA)を提案し,その非漸近収束特性について検討する。
MNISTデータハイパクリーニング実験において,既存の2次手法よりも提案手法の実用性能が優れていることを示す。
論文 参考訳（メタデータ） (2023-01-26T05:34:21Z) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳（メタデータ） (2022-06-17T06:10:20Z) - A Proximal Algorithm for Sampling from Non-convex Potentials [14.909442791255042]
滑らかさに欠ける非滑らかなポテンシャルの問題を考察する。
滑らかではなく、ポテンシャルは半滑らかあるいは多重多重滑らか関数であると仮定される。
我々は、交互サンプリングフレームワークとして知られるGibbsサンプリングの特殊なケースを開発する。
論文 参考訳（メタデータ） (2022-05-20T13:58:46Z) - Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with
Variance Reduction and its Application to Optimization [50.83356836818667]
勾配ランゲヴィン・ダイナミクスは非エプス最適化問題を解くための最も基本的なアルゴリズムの1つである。
本稿では、このタイプの2つの変種、すなわち、分散還元ランジュバンダイナミクスと再帰勾配ランジュバンダイナミクスを示す。
論文 参考訳（メタデータ） (2022-03-30T11:39:00Z) - Asymptotic Bounds for Smoothness Parameter Estimates in Gaussian Process
Interpolation [3.8979646385036175]
マタン核の滑らかさは、大きなデータ限界におけるモデルの多くの重要な性質を決定する。
我々は,滑らか度パラメータの最大推定値が真理の下では過小評価できないことを証明した。
最大推定は、コンパクトに支持された自己相似関数のクラスにおける真の滑らかさを回復することを示す。
論文 参考訳（メタデータ） (2022-03-10T14:45:57Z) - Sensing Cox Processes via Posterior Sampling and Positive Bases [56.82162768921196]
本研究では,空間統計学から広く用いられている点過程の適応センシングについて検討する。
我々は、この強度関数を、特別に構築された正の基底で表される、歪んだガウス過程のサンプルとしてモデル化する。
我々の適応センシングアルゴリズムはランゲヴィン力学を用いており、後続サンプリング(textscCox-Thompson)と後続サンプリング(textscTop2)の原理に基づいている。
論文 参考訳（メタデータ） (2021-10-21T14:47:06Z) - Heavy-tailed Streaming Statistical Estimation [58.70341336199497]
ストリーミング$p$のサンプルから重み付き統計推定の課題を考察する。
そこで我々は,傾きの雑音に対して,よりニュアンスな条件下での傾きの傾きの低下を設計し,より詳細な解析を行う。
論文 参考訳（メタデータ） (2021-08-25T21:30:27Z) - High-probability Bounds for Non-Convex Stochastic Optimization with
Heavy Tails [55.561406656549686]
我々は、勾配推定が末尾を持つ可能性のある一階アルゴリズムを用いたヒルベルト非最適化を考える。
本研究では, 勾配, 運動量, 正規化勾配勾配の収束を高確率臨界点に収束させることと, 円滑な損失に対する最もよく知られた繰り返しを示す。
論文 参考訳（メタデータ） (2021-06-28T00:17:01Z) - High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。
そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
論文 参考訳（メタデータ） (2021-06-10T17:54:21Z) - Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box
Optimization Framework [100.36569795440889]
この作業は、一階情報を必要としない零次最適化(ZO)の反復である。
座標重要度サンプリングにおける優雅な設計により,ZO最適化法は複雑度と関数クエリコストの両面において効率的であることを示す。
論文 参考訳（メタデータ） (2020-12-21T17:29:58Z) - Self-Tuning Stochastic Optimization with Curvature-Aware Gradient
Filtering [53.523517926927894]
サンプルごとのHessian-vector積と勾配を用いて、自己チューニングの二次構造を構築する。
モデルに基づく手続きが雑音勾配設定に収束することを証明する。
これは自己チューニング二次体を構築するための興味深いステップである。
論文 参考訳（メタデータ） (2020-11-09T22:07:30Z) - Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and
Variance Reduction [63.41789556777387]
非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。
Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
論文 参考訳（メタデータ） (2020-06-04T17:51:00Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。