Fugu-MT 論文翻訳(概要): Zeroth-order log-concave sampling

論文の概要: Zeroth-order log-concave sampling

arxiv url: http://arxiv.org/abs/2507.18021v1
Date: Thu, 24 Jul 2025 01:31:49 GMT
ステータス: 翻訳完了
システム内更新日: 2025-07-25 15:10:42.815367
Title: Zeroth-order log-concave sampling
Title（参考訳）: ゼロオーダーログコンケーブサンプリング
Authors: Yunbum Kook,
Abstract要約: 本研究は,ログ・コンケーブ・サンプリングにおける0次クエリの複雑さについて,メンバシップ・オーラクルを用いて検討する。本稿では,初期暖かさと出力保証との間の整合したR'enyiオーダーとの複雑性を実現するための,近位サンプリング器の簡易な変種を提案する。
参考スコア（独自算出の注目度）: 2.61072980439312
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We study the zeroth-order query complexity of log-concave sampling, specifically uniform sampling from convex bodies using membership oracles. We propose a simple variant of the proximal sampler that achieves the query complexity with matched R\'enyi orders between the initial warmness and output guarantee. Specifically, for any $\varepsilon>0$ and $q\geq2$, the sampler, initialized at $\pi_{0}$, outputs a sample whose law is $\varepsilon$-close in $q$-R\'enyi divergence to $\pi$, the uniform distribution over a convex body in $\mathbb{R}^{d}$, using $\widetilde{O}(qM_{q}^{q/(q-1)}d^{2}\,\lVert\operatorname{cov}\pi\rVert\log\frac{1}{\varepsilon})$ membership queries, where $M_{q}=\lVert\text{d}\pi_{0}/\text{d}\pi\rVert_{L^{q}(\pi)}$. We further introduce a simple annealing scheme that produces a warm start in $q$-R\'enyi divergence (i.e., $M_{q}=O(1)$) using $\widetilde{O}(qd^{2}R^{3/2}\,\lVert\operatorname{cov}\pi\rVert^{1/4})$ queries, where $R^{2}=\mathbb{E}_{\pi}[|\cdot|^{2}]$. This interpolates between known complexities for warm-start generation in total variation and R\'enyi-infinity divergence. To relay a R\'enyi warmness across the annealing scheme, we establish hypercontractivity under simultaneous heat flow and translate it into an improved mixing guarantee for the proximal sampler under a logarithmic Sobolev inequality. These results extend naturally to general log-concave distributions accessible via evaluation oracles, incurring additional quadratic queries.
Abstract（参考訳）: 本稿では,ログコンケーブサンプリングにおける0次クエリの複雑さについて検討する。本稿では,初期暖かさと出力保証の一致したR'enyiオーダーによるクエリ複雑性を実現するための,近位サンプリング器の簡易な変種を提案する。具体的には、$\varepsilon>0$と$q\geq2$に対して、サンプルは$\pi_{0}$で初期化され、法則が$\varepsilon$-close in $q$-R\enyi divergence to $\pi$、$\mathbb{R}^{d}$の凸体上の均一な分布を$\widetilde{O}(qM_{q}^{q/(q-1)}d^{2}\,\lVert\operatorname{cov}\pi\rVert\log\frac{1}{\varepsilon})で出力する。さらに、$\widetilde{O}(qd^{2}R^{3/2}\,\lVert\operatorname{cov}\pi\rVert^{1/4})$クエリを使って、$q$-R\enyi divergence (すなわち$M_{q}=O(1)$) の温かい開始を生成する単純なアニーリングスキームを導入する。これは、全変量におけるウォームスタート生成の既知の複雑さとR'enyi-infinity divergenceの間の補間である。熱処理方式でR'enyi温熱を中継するため, 同時熱流下で過収縮性を確立し, 対数的ソボレフ不等式下での近位試料の混合保証を改良した。これらの結果は、評価オラクルを介してアクセス可能な一般的な対数凹分布に自然に拡張され、追加の2次クエリが生成される。

関連論文リスト

Improved sampling algorithms and Poincaré inequalities for non-log-concave distributions [1.9753732769115382]
これは$d$と$frac1epsilon$である。 $L=mathcalO(1)$と$M=mathrmpoly(d)$である。
論文参考訳（メタデータ） (2025-07-15T12:06:11Z)
On the $O(\rac{\sqrt{d}}{K^{1/4}})$ Convergence Rate of AdamW Measured by $\ell_1$ Norm [54.28350823319057]
本稿では、$ell_$ノルムで測定されたAdamWの収束率$frac1Ksum_k=1KEleft[|nabla f(xk)|_1right]leq O(fracsqrtdCK1/4)を確立する。
論文参考訳（メタデータ） (2025-05-17T05:02:52Z)
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)
Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan [49.1574468325115]
ランク1テンソルを$otimes_i=1N mathbbRd$で完了する際のサンプルと計算複雑性を再考する。本稿では,一対のランダム線形系上で,ガウス・ヨルダンに相当するアルゴリズムを許容する問題のキャラクタリゼーションを提案する。
論文参考訳（メタデータ） (2024-08-10T04:26:19Z)
Rényi-infinity constrained sampling with $d^3$ membership queries [2.209921757303168]
本稿では,エレガントな収束保証を有する原理的かつ単純なアルゴリズムである制約付き近位サンプリング手法を提案する。 R'enyi-infinity divergence(mathcal R_infty$)に収束することを示す。
論文参考訳（メタデータ） (2024-07-17T19:20:08Z)
A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文参考訳（メタデータ） (2023-09-25T17:54:19Z)
Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyond [89.72693227960274]
本稿では,グループ分散ロバスト最適化 (GDRO) を,$m$以上の異なる分布をうまく処理するモデルを学習する目的で検討する。各ラウンドのサンプル数を$m$から1に抑えるため、GDROを2人でプレイするゲームとして、一方のプレイヤーが実行し、他方のプレイヤーが非公開のマルチアームバンディットのオンラインアルゴリズムを実行する。第2のシナリオでは、最大リスクではなく、平均的最上位k$リスクを最適化し、分散の影響を軽減することを提案する。
論文参考訳（メタデータ） (2023-02-18T09:24:15Z)
Hamiltonian Monte Carlo for efficient Gaussian sampling: long and random steps [0.0]
Hamiltonian Monte Carlo (HMC) は密度$e-f(x)$の高次元分布からサンプリングするマルコフ連鎖アルゴリズムである。 HMCは,$widetildeO(sqrtkappa d1/4 log(1/varepsilon)$グラデーションクエリを用いて,全変動距離で$varepsilon$-closeの分布からサンプリングできることを示す。
論文参考訳（メタデータ） (2022-09-26T15:29:29Z)
Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文参考訳（メタデータ） (2022-06-17T17:55:43Z)
Structured Logconcave Sampling with a Restricted Gaussian Oracle [23.781520510778716]
我々は,複数のロジコンケーブファミリーを高精度にサンプリングするアルゴリズムを提案する。凸最適化における近点法にインスパイアされた縮小フレームワークをさらに発展させる。
論文参考訳（メタデータ） (2020-10-07T01:43:07Z)
Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文参考訳（メタデータ） (2020-06-06T13:34:41Z)
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)

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

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