Fugu-MT 論文翻訳(概要): Complexity of zigzag sampling algorithm for strongly log-concave distributions

論文の概要: Complexity of zigzag sampling algorithm for strongly log-concave distributions

arxiv url: http://arxiv.org/abs/2012.11094v1
Date: Mon, 21 Dec 2020 03:10:21 GMT
ステータス: 翻訳完了
システム内更新日: 2021-04-27 06:40:19.711617
Title: Complexity of zigzag sampling algorithm for strongly log-concave distributions
Title（参考訳）: 強対数凹分布に対するジグザグサンプリングアルゴリズムの複雑さ
Authors: Jianfeng Lu and Lihan Wang
Abstract要約: 強いログ凹分布に対するジグザグサンプリングアルゴリズムの計算複雑性について検討する。ジグザグサンプリングアルゴリズムは, 計算コストが$obiglに匹敵するchi-squareの発散において, $varepsilon$ 誤差を達成することを証明した。
参考スコア（独自算出の注目度）: 6.336005544376984
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We study the computational complexity of zigzag sampling algorithm for strongly log-concave distributions. The zigzag process has the advantage of not requiring time discretization for implementation, and that each proposed bouncing event requires only one evaluation of partial derivative of the potential, while its convergence rate is dimension independent. Using these properties, we prove that the zigzag sampling algorithm achieves $\varepsilon$ error in chi-square divergence with a computational cost equivalent to $O\bigl(\kappa^2 d^\frac{1}{2}(\log\frac{1}{\varepsilon})^{\frac{3}{2}}\bigr)$ gradient evaluations in the regime $\kappa \ll \frac{d}{\log d}$ under a warm start assumption, where $\kappa$ is the condition number and $d$ is the dimension.
Abstract（参考訳）: 強対数凹分布に対するジグザグサンプリングアルゴリズムの計算複雑性について検討した。 zigzagプロセスは、実装に時間的離散化を必要とせず、それぞれのバウンシングイベントはポテンシャルの部分微分の1つの評価しか必要とせず、その収束率は次元に依存しないという利点がある。これらの特性を用いて、ジグザグサンプリングアルゴリズムは、計算コストが$O\bigl(\kappa^2 d^\frac{1}{2}(\log\frac{1}{\varepsilon})^{\frac{3}{2}}\bigr)$gradient evaluations in the regime $\kappa \ll \frac{d}{\log d}$ in a warm start assumption, where $\kappa$ is the condition number and $d$ is the dimension.

関連論文リスト

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)
Polynomial time sampling from log-smooth distributions in fixed dimension under semi-log-concavity of the forward diffusion with application to strongly dissipative distributions [9.48556659249574]
固定次元の複雑なサンプリングアルゴリズムを提案する。我々は,提案アルゴリズムが予測される$epsilon$誤差を$KL$ばらつきで達成することを証明する。応用として、$L$-log-smooth分布からサンプリングする問題に対する指数関数的複雑性の改善を導出する。
論文参考訳（メタデータ） (2024-12-31T17:51:39Z)
Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
複素勾配問題に対する2つの分散化ZO推定器を提案する。我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
論文参考訳（メタデータ） (2024-10-03T15:04:01Z)
Entropy contraction of the Gibbs sampler under log-concavity [0.16385815610837165]
ランダムスキャンギブスサンプリング器は相対エントロピーで収縮し、関連する収縮率を鋭く評価する。我々の手法は多用途であり、Metropolis-within-GibbsスキームやHit-and-Runアルゴリズムにまで拡張されている。
論文参考訳（メタデータ） (2024-10-01T16:50:36Z)
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)
Quantum Algorithms for Sampling Log-Concave Distributions and Estimating Normalizing Constants [8.453228628258778]
我々は,対数凹分布をサンプリングし,正規化定数を推定するための量子アルゴリズムを開発した。我々はモンテカルロ法と量子ウォークの量子アナログを利用する。また、正規化定数を推定するための1/epsilon1-o(1)$量子下界も証明する。
論文参考訳（メタデータ） (2022-10-12T19:10:43Z)
Robust Sparse Mean Estimation via Sum of Squares [42.526664955704746]
本研究では,高次元スパース平均推定の問題点を,逆数外乱の$epsilon$-fractionの存在下で検討する。我々のアルゴリズムは、サム・オブ・スクエア(Sum-of-Squares)ベースのアルゴリズムアプローチに従う。
論文参考訳（メタデータ） (2022-06-07T16:49:54Z)
Random quantum circuits transform local noise into global white noise [118.18170052022323]
低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
論文参考訳（メタデータ） (2021-11-29T19:26:28Z)
Structured Logconcave Sampling with a Restricted Gaussian Oracle [23.781520510778716]
我々は,複数のロジコンケーブファミリーを高精度にサンプリングするアルゴリズムを提案する。凸最適化における近点法にインスパイアされた縮小フレームワークをさらに発展させる。
論文参考訳（メタデータ） (2020-10-07T01:43:07Z)
Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
論文参考訳（メタデータ） (2020-09-18T02:18: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)

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