論文の概要: Complexity Analysis of Normalizing Constant Estimation: from Jarzynski Equality to Annealed Importance Sampling and beyond

• arxiv url: http://arxiv.org/abs/2502.04575v1
• Date: Fri, 07 Feb 2025 00:05:28 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-10 14:57:10.256729
• Title: Complexity Analysis of Normalizing Constant Estimation: from Jarzynski Equality to Annealed Importance Sampling and beyond
• Title（参考訳）: 正規化定数推定の複雑性解析:ジャジンスキーの等式からアナールされた重要度サンプリングまで
• Authors: Wei Guo, Molei Tao, Yongxin Chen,
• Abstract要約: 非正規化確率密度 $piproptomathrme-V$ が与えられたとき、正規化定数 $Z=int_mathbbRdmathrme-V(x)mathrmdx$ または自由エネルギー $F=-log Z$ はベイズ統計学、統計力学、機械学習において重要な問題である。 本稿では,逆拡散型サンプリング器に基づく新しい正規化定数推定アルゴリズムを提案し,その複雑さを解析するための枠組みを確立する。
• 参考スコア（独自算出の注目度）: 28.931489333515618
• License:
• Abstract: Given an unnormalized probability density $\pi\propto\mathrm{e}^{-V}$, estimating its normalizing constant $Z=\int_{\mathbb{R}^d}\mathrm{e}^{-V(x)}\mathrm{d}x$ or free energy $F=-\log Z$ is a crucial problem in Bayesian statistics, statistical mechanics, and machine learning. It is challenging especially in high dimensions or when $\pi$ is multimodal. To mitigate the high variance of conventional importance sampling estimators, annealing-based methods such as Jarzynski equality and annealed importance sampling are commonly adopted, yet their quantitative complexity guarantees remain largely unexplored. We take a first step toward a non-asymptotic analysis of annealed importance sampling. In particular, we derive an oracle complexity of $\widetilde{O}\left(\frac{d\beta^2{\mathcal{A}}^2}{\varepsilon^4}\right)$ for estimating $Z$ within $\varepsilon$ relative error with high probability, where $\beta$ is the smoothness of $V$ and $\mathcal{A}$ denotes the action of a curve of probability measures interpolating $\pi$ and a tractable reference distribution. Our analysis, leveraging Girsanov theorem and optimal transport, does not explicitly require isoperimetric assumptions on the target distribution. Finally, to tackle the large action of the widely used geometric interpolation of probability distributions, we propose a new normalizing constant estimation algorithm based on reverse diffusion samplers and establish a framework for analyzing its complexity.
• Abstract（参考訳）: 非正規化確率密度 $\pi\propto\mathrm{e}^{-V}$ を与えられたとき、正規化定数 $Z=\int_{\mathbb{R}^d}\mathrm{e}^{-V(x)}\mathrm{d}x$ あるいは自由エネルギー $F=-\log Z$ はベイズ統計学、統計力学、機械学習において重要な問題である。 特に高次元や$\pi$がマルチモーダルである場合には難しい。 従来の重要度推定器の高分散を緩和するため, ジャジンスキー等式や焼鈍重要度推定法などの熱処理法が広く採用されているが, その量的複雑性保証は未解明のままである。 熱処理による重要サンプリングの非漸近解析に向けて第一歩を踏み出した。 特に、オラクルの複雑性を$\widetilde{O}\left(\frac{d\beta^2{\mathcal{A}}^2}{\varepsilon^4}\right)$ for s $Z$ in $\varepsilon$ relative error with high probability, where $\beta$ is the smoothness of $V$ and $\mathcal{A}$は、$\pi$を補間する確率測度の曲線の作用と、抽出可能な参照分布を表す。 我々の解析は、ジルサノフの定理と最適輸送を利用しており、対象分布に対する等尺的な仮定を明示的に必要としない。 最後に, 確率分布の幾何学的補間を広く用いた大規模動作に対処するために, 逆拡散型サンプリング器に基づく新しい正規化定数推定アルゴリズムを提案し, その複雑さを解析するための枠組みを確立する。

関連論文リスト

• Efficient Multivariate Robust Mean Estimation Under Mean-Shift Contamination [35.67742880001828]
  平均シフト汚染を用いた高次元ロバスト平均推定のための計算効率のよい最初のアルゴリズムを提案する。 提案アルゴリズムは, ほぼ最適サンプルの複雑性を持ち, サンプル・ポリノミカル時間で動作し, ターゲット平均を任意の精度で近似する。
  論文  参考訳（メタデータ） (2025-02-20T17:53:13Z)
• Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
  以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。 本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-11-01T17:59:53Z)
• Sum-of-squares lower bounds for Non-Gaussian Component Analysis [33.80749804695003]
  非ガウス成分分析(Non-Gaussian Component Analysis、NGCA)は、高次元データセットにおいて非ガウス方向を求める統計的タスクである。 本稿では Sum-of-Squares フレームワークにおける NGCA の複雑さについて考察する。
  論文  参考訳（メタデータ） (2024-10-28T18:19:13Z)
• Provable Benefit of Annealed Langevin Monte Carlo for Non-log-concave Sampling [28.931489333515618]
  簡単なアンニール型Langevin Monte Carloアルゴリズムに対して$widetildeOleft(fracdbeta2cal A2varepsilon6right)のオラクル複雑性を確立する。 例えば、$cal A$ は対象分布 $pi$ と容易にサンプリング可能な分布を補間する確率測度の曲線の作用を表す。
  論文  参考訳（メタデータ） (2024-07-24T02:15:48Z)
• Robust computation of optimal transport by $\beta$-potential regularization [79.24513412588745]
  最適輸送(OT)は、確率分布間の差を測定する機械学習分野で広く使われているツールである。 我々は、いわゆる$beta$-divergenceに付随するベータポテンシャル項でOTを正規化することを提案する。 提案アルゴリズムで計算した輸送行列は,外乱が存在する場合でも確率分布を頑健に推定するのに役立つことを実験的に実証した。
  論文  参考訳（メタデータ） (2022-12-26T18:37:28Z)
• Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
  カーネルヒルベルト空間を用いて、無限水平割引マルコフ報酬過程の値関数を推定する。 我々は、関連するカーネル演算子の固有値に明示的に依存した誤差の非漸近上界を導出する。 MRP のサブクラスに対する minimax の下位境界を証明する。
  論文  参考訳（メタデータ） (2021-09-24T14:48:20Z)
• The Sample Complexity of Robust Covariance Testing [56.98280399449707]
  i. i. d. 形式 $Z = (1-epsilon) X + epsilon B$ の分布からのサンプル。ここで $X$ はゼロ平均で未知の共分散である Gaussian $mathcalN(0, Sigma)$ である。 汚染がない場合、事前の研究は、$O(d)$サンプルを使用するこの仮説テストタスクの単純なテスターを与えた。 サンプル複雑性の上限が $omega(d2)$ for $epsilon$ an arbitrarily small constant and $gamma であることを証明します。
  論文  参考訳（メタデータ） (2020-12-31T18:24:41Z)
• Optimal Sub-Gaussian Mean Estimation in $\mathbb{R}$ [5.457150493905064]
  ガウス下収束を考慮した新しい推定器を提案する。 我々の推定器はその分散に関する事前の知識を必要としない。 我々の推定器の構成と分析は、他の問題に一般化可能なフレームワークを提供する。
  論文  参考訳（メタデータ） (2020-11-17T02:47:24Z)
• 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)
• 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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。