Fugu-MT 論文翻訳(概要): The query complexity of sampling from strongly log-concave distributions in one dimension

論文の概要: The query complexity of sampling from strongly log-concave distributions in one dimension

arxiv url: http://arxiv.org/abs/2105.14163v1
Date: Sat, 29 May 2021 00:51:17 GMT
ステータス: 処理完了
システム内更新日: 2021-06-01 16:49:56.943541
Title: The query complexity of sampling from strongly log-concave distributions in one dimension
Title（参考訳）: 1次元の強い対数対数分布からのサンプリングの問合せ複雑性
Authors: Sinho Chewi, Patrik Gerber, Chen Lu, Thibaut Le Gouic, Philippe Rigollet
Abstract要約: Omega(loglogkappa)$の最初の厳密な下限を、強い対数凹と対数平滑な分布のクラスからサンプリングするクエリに設定する。本稿では,この指数的ギャップを埋めるリジェクションに基づく新しいアルゴリズムを提案する。
参考スコア（独自算出の注目度）: 14.18847457501901
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We establish the first tight lower bound of $\Omega(\log\log\kappa)$ on the query complexity of sampling from the class of strongly log-concave and log-smooth distributions with condition number $\kappa$ in one dimension. Whereas existing guarantees for MCMC-based algorithms scale polynomially in $\kappa$, we introduce a novel algorithm based on rejection sampling that closes this doubly exponential gap.
Abstract（参考訳）: 1次元の条件数$\kappa$の強い対数凹および対数平滑分布のクラスからサンプリングするクエリ複雑性に基づいて、最初の厳密な下限$\Omega(\log\log\kappa)$を確立する。 MCMCに基づくアルゴリズムの既存の保証は$\kappa$で多項式的にスケールするが、この2倍の指数ギャップを閉じるリジェクションサンプリングに基づく新しいアルゴリズムを導入する。

関連論文リスト

Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
論文参考訳（メタデータ） (2024-05-10T09:58:47Z)
Query lower bounds for log-concave sampling [22.446060015399905]
強い対数凹と対数平滑な分布を次元$dge 2$でサンプリングする際の下限を証明した。我々の証明は(1)幾何測度論におけるカキーア予想に着想を得たマルチスケールの構成と(2)アルゴリズムブロッククリロフアルゴリズムがこの問題に最適であることを示す新しい還元に依存している。
論文参考訳（メタデータ） (2023-04-05T17:10:53Z)
Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPs [60.40452803295326]
線形マルコフ決定過程(MDP)を学習するための新たな報酬なしアルゴリズムを提案する。我々のアルゴリズムの核心は、探索駆動の擬似回帰を用いた不確実性重み付き値目標回帰である。我々のアルゴリズムは$tilde O(d2varepsilon-2)$ episodesを探索するだけで、$varepsilon$-optimal policyを見つけることができる。
論文参考訳（メタデータ） (2023-03-17T17:53:28Z)
Improved dimension dependence of a proximal algorithm for sampling [16.147290924171692]
そこで本研究では,すべての古典的設定において,より優れた複雑性境界を実現するサンプリングアルゴリズムを提案する。提案アルゴリズムは,2021年に導入した近位サンプルを用いた。強い対数対数分布の場合、この手法は温度開始を伴わずに$tildemathcalO(kappa d1/2)$の複雑さを持つ。 LSI を満たす分布に対して、我々は $tilde MathcalO(hat kappa d1/2)$ ここで $hat kappa$ は滑らかさと滑らかさの比である。
論文参考訳（メタデータ） (2023-02-20T16:44:48Z)
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)
Towards Sample-Optimal Compressive Phase Retrieval with Sparse and Generative Priors [59.33977545294148]
O(k log L)$サンプルは振幅に基づく経験損失関数を最小化する任意のベクトルに信号が近いことを保証するのに十分であることを示す。この結果はスパース位相検索に適応し、基底信号が$s$-sparseおよび$n$-dimensionalである場合、$O(s log n)$サンプルは同様の保証に十分であることを示す。
論文参考訳（メタデータ） (2021-06-29T12:49:54Z)
Rejection sampling from shape-constrained distributions in sublinear time [14.18847457501901]
離散分布の様々なクラスを対象としたミニマックスフレームワークにおいて,リジェクションサンプリングのクエリ複雑性について検討した。本研究は,アルファベットサイズに比例して複雑度が増大するサンプリングのための新しいアルゴリズムを提案する。
論文参考訳（メタデータ） (2021-05-29T01:00:42Z)
Complexity of zigzag sampling algorithm for strongly log-concave distributions [6.336005544376984]
強いログ凹分布に対するジグザグサンプリングアルゴリズムの計算複雑性について検討する。ジグザグサンプリングアルゴリズムは, 計算コストが$obiglに匹敵するchi-squareの発散において, $varepsilon$ 誤差を達成することを証明した。
論文参考訳（メタデータ） (2020-12-21T03:10:21Z)
Revisiting the Sample Complexity of Sparse Spectrum Approximation of Gaussian Processes [60.479499225746295]
本稿では,ガウス過程に対して,パラメータ空間全体に対して同時に保持可能な保証付きスケーラブルな近似を導入する。我々の近似は、スパーススペクトルガウス過程(SSGP)のための改良されたサンプル複雑性解析から得られる。
論文参考訳（メタデータ） (2020-11-17T05:41:50Z)
Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model [50.38446482252857]
本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
論文参考訳（メタデータ） (2020-05-26T17:53:18Z)

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