論文の概要: Fast PAC Global Optimization via Restarted Langevin: Exploration, Exploitation, and Degenerate Cooling
- arxiv url: http://arxiv.org/abs/2609.06196v1
- Date: Sat, 05 Sep 2026 17:36:18 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-10 19:44:08.218553
- Title: Fast PAC Global Optimization via Restarted Langevin: Exploration, Exploitation, and Degenerate Cooling
- Title（参考訳）: Restarted Langevinによる高速PACグローバル最適化 - 探索, 爆発, 退化冷却
- Abstract要約: アルゴリズムの設計と分析は連続している。
世界の探検は搾取から切り離されている。
6つのラクダとラストリギンの目的に関する実験は、より暖かい探検の利点を示している。
- 参考スコア（独自算出の注目度）: 7.018547803286913
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the computational effort required for global optimization of a smooth, possibly nonconvex objective $Γ:\mathbb{R}^d\to\mathbb{R}$. An algorithm satisfies the $(\varepsilon,δ)$-PAC performance requirement if its output $\widehat X$ obeys $\mathbb{P}\{Γ(\widehat X)-Γ^\star>\varepsilon\}\leqδ$. Algorithm design and analysis are in continuous time. We compare classical simulated annealing and fixed-temperature Langevin diffusion with two approaches introduced and analyzed here: parallel-restart Langevin and a Langevin--gradient scheme using stochastic dynamics for global exploration and gradient flow for local exploitation. Let $L=\log(1/δ)$ and let $E_*$ denote the dominant energy barrier. At logarithmic precision in the low-temperature regime, the first two approaches require simulation time exponential in $L/\varepsilon$. For parallel fixed-temperature Langevin, an appropriate number of independent trials gives $ C_3=L^{1+o(1)}/\varepsilon$ as $δ\downarrow0$, for each fixed $\varepsilon>0$. The most substantial improvement comes from separating exploration from exploitation. If $η$ is the attraction margin of a target region containing the global minimizers, a sufficient low-temperature estimate for total simulation time in the best-state Langevin--gradient variant is $ C_4^{(c)}\approx N\exp\{EL/(Nη)\} +O(\log(1/\varepsilon))$, with $E>E_*$. Thus global exploration is decoupled from the requested accuracy. Analysis beyond logarithmic precision reveals dimension-dependent prefactors, while experiments on the six-hump camel and Rastrigin objectives illustrate the benefits of warmer exploration and the usefulness of spectral information for understanding exploration time.
- Abstract（参考訳）: 滑らかで、おそらくは非凸な目的 $ の大域的最適化に必要な計算労力について検討する。
アルゴリズムが$(\varepsilon,δ)$-PACパフォーマンス要求を満たす場合、出力 $\widehat X$ が $\mathbb{P}\{\(\widehat X)-\^\star>\varepsilon\}\leqδ$ に従う。
アルゴリズムの設計と分析は連続している。
古典的アニーリング法と固定温度ランゲヴィン拡散法を, 並列再スタートランゲヴィン法と, 大域的探索のための確率力学と局所的利用のための勾配流を用いた段階的スキームの2つのアプローチと比較した。
L =log(1/δ)$ とし、E_*$ を支配的エネルギー障壁とする。
低温状態における対数精度では、最初の2つのアプローチは、$L/\varepsilon$のシミュレーション時間指数を必要とする。
C_3=L^{1+o(1)}/\varepsilon$ as $δ\downarrow0$, for each fixed $\varepsilon>0$。
最も顕著な改善は、探検と搾取の分離である。
もし$η$が大域最小化器を含む対象領域のアトラクションマージンであれば、最高状態ランゲヴィン-勾配変種における全シミュレーション時間に対する十分な低温推定値は$C_4^{(c)}\approx N\exp\{EL/(Nη)\} +O(\log(1/\varepsilon))$, with $E>E_*$である。
したがって、グローバルな探索は要求された精度から切り離される。
対数精度を超越した分析は次元に依存した事前因子を明らかにし、一方6ハンプラクダとラストリギンの目的に関する実験は、より温かい探査の利点と、探査時間を理解するためのスペクトル情報の有用性を示している。
関連論文リスト
- Sequential Physics-Constrained Neural Operator Forward Modeling for the $\textit{Norne}$ Reservoir System [3.175986877079391]
ニューラル演算子を用いたブラックオイル貯留層力学の逐次サロゲートモデリングのための包括的フレームワークを開発した。
アプリケーション焦点はNorneベンチマーク貯水池で、不均一な$46times112times22$グリッドで定義されている。
1000人組のアンサンブルは、1つのB200 GPU上で1分以下で動作し、OPM有限体積シミュレータよりも$sim104times$ Wall-clockのスピードアップを提供する。
論文 参考訳（メタデータ） (2026-05-27T17:18:39Z) - PAC global optimization for VQE in low-curvature geometric regimes [0.3553493344868413]
変分量子固有解法における大域的な$varepsilon$-optimalityのノイズロスト保証
Morse--Bott 部分多様体は座標整列な埋め込みフラットに対してファイバー正則性を満たす。
論文 参考訳（メタデータ） (2025-11-18T16:18:26Z) - Faster Spectral Density Estimation and Sparsification in the Nuclear Norm [28.368253322669336]
我々は,新しいグラフスペーシフィケーションの概念を導入し,これを核スペーシフィケーションと呼ぶ。
また,本手法はスペクトル密度推定のための最初の決定論的アルゴリズムを導出することを示した。
論文 参考訳（メタデータ） (2024-06-11T17:50:20Z) - Fast Rates for Maximum Entropy Exploration [52.946307632704645]
エージェントが未知の環境下で活動し、報酬が得られない場合、強化学習(RL)における探索の課題に対処する。
本研究では,最大エントロピー探索問題を2つの異なるタイプで検討する。
訪問エントロピーには、$widetildemathcalO(H3S2A/varepsilon2)$ sample complexity を持つゲーム理論アルゴリズムを提案する。
軌道エントロピーに対しては,次数$widetildemathcalO(mathrmpoly(S,)の複雑さのサンプルを持つ単純なアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-03-14T16:51:14Z) - ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。
我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-01-01T18:51:29Z) - Penalized Overdamped and Underdamped Langevin Monte Carlo Algorithms for Constrained Sampling [17.832449046193933]
目的が目標分布である$pi(x)prop ef(x)$から$x$が制約されたときにサンプリングする制約付きサンプリング問題を考える。
ペナルティ法によって動機付けられた制約付き問題を,制約違反に対するペナルティ関数を導入することにより,非制約サンプリング問題に変換する。
PSGLD と PSGULMC の場合、$tildemathcalO(d/varepsilon18)$ が強凸で滑らかであるとき、$tildemathcalO(d/varepsilon) を得る。
論文 参考訳（メタデータ） (2022-11-29T18:43:22Z) - Improved Sample Complexity for Incremental Autonomous Exploration in
MDPs [132.88757893161699]
我々は $epsilon$-optimal 目標条件付きポリシーのセットを学び、$ L$ ステップ内で段階的に到達可能なすべての状態を達成します。
DisCoは、コストに敏感な最短経路問題に対して$epsilon/c_min$-optimalポリシーを返すことができる最初のアルゴリズムです。
論文 参考訳（メタデータ） (2020-12-29T14:06:09Z) - Faster Convergence of Stochastic Gradient Langevin Dynamics for
Non-Log-Concave Sampling [110.88857917726276]
我々は,非log-concaveとなる分布のクラスからサンプリングするために,勾配ランゲヴィンダイナミクス(SGLD)の新たな収束解析を行う。
我々のアプローチの核心は、補助的時間反転型マルコフ連鎖を用いたSGLDのコンダクタンス解析である。
論文 参考訳（メタデータ） (2020-10-19T15:23:18Z) - 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) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文 参考訳（メタデータ） (2020-07-16T06:44:44Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。