論文の概要: Windowed thinning and query complexity for the bouncy particle and Zigzag samplers
- arxiv url: http://arxiv.org/abs/2607.28413v1
- Date: Thu, 30 Jul 2026 15:59:25 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-31 21:37:00.647001
- Title: Windowed thinning and query complexity for the bouncy particle and Zigzag samplers
- Title（参考訳）: 弾力性粒子とZigzagサンプルラーのウィンドウ化とクエリ複雑性
- Abstract要約: 球状粒子サンプリング器と座標Zigzagプロセスの正確なシミュレーション手法である窓面の薄化について検討する。
総変量誤差$varepsilon$は、期待されるクエリカウントが$O(1/2d,(dlog+logfrac1varepsilon))、バウンシー粒子サンプリング器の$グラデーションクエリが$O(d1/4(dlog+logfrac1varepsilon))、Zigzagの$フルグレート等価が$O(d1/4(dlog+logfrac1varepsilon)である。
- 参考スコア（独自算出の注目度）: 5.726854405157353
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Let $μ(d x)\propto e^{-U(x)} d x$ on $\R^d$, where $U$ is $m$-strongly convex and $L$-smooth, and denote by $κ=L/m$ the condition number. We consider windowed thinning, an exact simulation method for the bouncy particle sampler and the coordinate Zigzag process. The method divides a trajectory into deterministic windows and uses a gradient evaluation at the beginning of each window to construct a tractable local envelope for the event rate. Combining this construction with quantitative mixing estimates and finite-time bounds on the expected numbers of bounces and flips yields query complexity guarantees from a Gaussian cold start. For total-variation error $\varepsilon$, the expected query counts are $O(κ^{1/2}d\,(d\logκ+\log\frac1\varepsilon))$ gradient queries for the bouncy particle sampler and $O(κd^{1/4}(d\logκ+\log\frac1\varepsilon))$ full-gradient equivalents for Zigzag, where $d$ coordinate-partial queries count as one equivalent.
- Abstract（参考訳）: μ(d x)\propto e^{-U(x)} d x$ on $\R^d$, where $U$ is $m$-strongly convex and $L$-smooth とし、条件番号は $κ=L/m$ とする。
球状粒子サンプリング器と座標Zigzagプロセスの正確なシミュレーション手法である窓面の薄化について検討する。
トラジェクトリを決定論的ウィンドウに分割し、各ウィンドウの開始時の勾配評価を用いて、イベントレートの抽出可能なローカルエンベロープを構築する。
この構成と定量的な混合推定と、期待されるバウンス数とフリップの有限時間境界を組み合わせることで、ガウスのコールドスタートからクエリ複雑性が保証される。
総変量誤差$\varepsilon$は、期待されるクエリカウントは、$O(κ^{1/2}d\,(d\logκ+\log\frac1\varepsilon))、$O(κd^{1/4}(d\logκ+\log\frac1\varepsilon))、$O(κd^{1/4)、$O(κd^{1/4)(d\logκ+\log\frac1\varepsilon))である。
関連論文リスト
- Smoothed Picard Hamiltonian Monte Carlo [15.748402989364804]
我々は、ガウス的滑らか化、ピカール反復、高次離散化を組み合わせた、Emphsmoothed Picard Hamiltonian Monte Carloと呼ばれる新しい低精度サンプリング器を開発した。
これにより、共振器で導入された近位弾力性粒子サンプリング器が温かいスタートとなり、高精度な対数凹型サンプリング器が複雑になる。
論文 参考訳（メタデータ） (2026-09-07T01:13:28Z) - Accelerated High-Accuracy Sampling from a Warm Start via the Proximal Bouncy Particle Sampler [15.748402989364804]
ここで、$(mathrmdx)propto e-V(x),mathrmdx$ on $mathbbRd$, $V$ is $-strongly convex and $-smooth, and write $:=/$。
我々は, 素粒子サンプリング器と素粒子サンプリング器のアイデアを組み合わせて, 素粒子サンプリング器(素粒子サンプリング器, 素粒子サンプリング器, 素粒子サンプリング器)を設計し, 解析する。
論文 参考訳（メタデータ） (2026-09-07T01:13:27Z) - Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise [49.730496294398726]
重み付き確率変数に対する新しい量子平均推定器を開発した。
尾指数>4/3$のより強い下界を導出し、次元への非自明な依存が避けられないことを示す。
凸目的関数に対して,量子射影勾配降下法を提案する。
論文 参考訳（メタデータ） (2026-07-28T09:29:37Z) - A proximal gradient algorithm for composite log-concave sampling [9.11122093402205]
我々は、$mathbbRd$、すなわち$propto e-f-g$という形の密度の合成対数分布からサンプリングするアルゴリズムを提案する。
さらに、(1)$が非log-concaveであるが、 Poincaré あるいは log-Sobolev の不等式を満たす場合、(2)$f$ が非smooth であるが Lipschitz である場合にも結果を拡張します。
論文 参考訳（メタデータ） (2026-05-12T17:48:09Z) - Zeroth-order log-concave sampling [2.61072980439312]
本研究は,ログ・コンケーブ・サンプリングにおける0次クエリの複雑さについて,メンバシップ・オーラクルを用いて検討する。
本稿では,初期暖かさと出力保証との間の整合したR'enyiオーダーとの複雑性を実現するための,近位サンプリング器の簡易な変種を提案する。
論文 参考訳（メタデータ） (2025-07-24T01:31:49Z) - On the query complexity of sampling from non-log-concave distributions [2.4253233571593547]
密度$p(x)propto e-f(x)$を持つ$d$次元分布からサンプリングする問題を、必ずしも良好な等尺条件を満たすとは限らない。
広い範囲のパラメータに対して、サンプリングは$d$の超指数係数による最適化よりも厳密に容易であることを示す。
論文 参考訳（メタデータ） (2025-02-10T06:54:16Z) - Measuring quantum relative entropy with finite-size effect [53.64687146666141]
相対エントロピー$D(rho|sigma)$を$sigma$が知られているときに推定する。
我々の推定器は次元$d$が固定されたときにCram'er-Rao型境界に達する。
論文 参考訳（メタデータ） (2024-06-25T06:07:20Z) - ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。
我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-01-01T18:51:29Z) - Random quantum circuits transform local noise into global white noise [118.18170052022323]
低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。
十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。
ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
論文 参考訳（メタデータ） (2021-11-29T19:26:28Z) - Complexity of zigzag sampling algorithm for strongly log-concave
distributions [6.336005544376984]
強いログ凹分布に対するジグザグサンプリングアルゴリズムの計算複雑性について検討する。
ジグザグサンプリングアルゴリズムは, 計算コストが$obiglに匹敵するchi-squareの発散において, $varepsilon$ 誤差を達成することを証明した。
論文 参考訳（メタデータ） (2020-12-21T03:10:21Z) - Structured Logconcave Sampling with a Restricted Gaussian Oracle [23.781520510778716]
我々は,複数のロジコンケーブファミリーを高精度にサンプリングするアルゴリズムを提案する。
凸最適化における近点法にインスパイアされた縮小フレームワークをさらに発展させる。
論文 参考訳（メタデータ） (2020-10-07T01:43:07Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。