論文の概要: Query lower bounds for log-concave sampling

• arxiv url: http://arxiv.org/abs/2304.02599v2
• Date: Mon, 30 Oct 2023 03:01:43 GMT
• ステータス: 処理完了
• システム内更新日: 2023-11-02 03:18:16.202990
• Title: Query lower bounds for log-concave sampling
• Title（参考訳）: log-concaveサンプリングのためのクエリ下限
• Authors: Sinho Chewi, Jaume de Dios Pont, Jerry Li, Chen Lu, Shyam Narayanan
• Abstract要約: 強い対数凹と対数平滑な分布を次元$dge 2$でサンプリングする際の下限を証明した。 我々の証明は(1)幾何測度論におけるカキーア予想に着想を得たマルチスケールの構成と(2)アルゴリズムブロッククリロフアルゴリズムがこの問題に最適であることを示す新しい還元に依存している。
• 参考スコア（独自算出の注目度）: 22.446060015399905
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Log-concave sampling has witnessed remarkable algorithmic advances in recent years, but the corresponding problem of proving lower bounds for this task has remained elusive, with lower bounds previously known only in dimension one. In this work, we establish the following query lower bounds: (1) sampling from strongly log-concave and log-smooth distributions in dimension $d\ge 2$ requires $\Omega(\log \kappa)$ queries, which is sharp in any constant dimension, and (2) sampling from Gaussians in dimension $d$ (hence also from general log-concave and log-smooth distributions in dimension $d$) requires $\widetilde \Omega(\min(\sqrt\kappa \log d, d))$ queries, which is nearly sharp for the class of Gaussians. Here $\kappa$ denotes the condition number of the target distribution. Our proofs rely upon (1) a multiscale construction inspired by work on the Kakeya conjecture in geometric measure theory, and (2) a novel reduction that demonstrates that block Krylov algorithms are optimal for this problem, as well as connections to lower bound techniques based on Wishart matrices developed in the matrix-vector query literature.
• Abstract（参考訳）: ログ・コンケーブのサンプリングは近年顕著なアルゴリズムの進歩をみせたが、このタスクの下位境界を証明するための対応する問題は、以前は次元1でしか知られていなかった。 本研究では, 1次元の強いlog-concaveおよびlog-smooth分布からのサンプリングには,任意の定数次元においてシャープな$\omega(\log \kappa)$クエリ, 2次元のガウス分布からのサンプリング$d$(一般のlog-concaveおよびlog-smooth分布からも$d$となる)には$\widetilde \omega(\min(\sqrt\kappa \log d, d)$クエリが必要である。 ここで$\kappa$はターゲット分布の条件番号を表す。 本証明は,(1)幾何学的測度論におけるカヤヤ予想の研究に触発された多元的構成と,(2)ブロッククリロフアルゴリズムがこの問題に最適であることを示す新しい還元と,行列・ベクトル問合せ文献で開発されたウィッシュアート行列に基づく下限手法との関係に依存する。

関連論文リスト

• 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)
• Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems [61.85150061213987]
  一般化線形モデル (GLM) フレームワークを用いて, citelu2021low で提案した一般化低ランク行列帯域問題について検討する。 既存のアルゴリズムの計算不可能性と理論的制約を克服するため,まずG-ESTTフレームワークを提案する。 G-ESTT は $tildeO(sqrt(d_1+d_2)3/2Mr3/2T)$ bound of regret を達成でき、G-ESTS は $tildeO を達成できることを示す。
  論文  参考訳（メタデータ） (2024-01-14T14:14:19Z)
• Causal Bandits for Linear Structural Equation Models [58.2875460517691]
  本稿では,因果図形モデルにおける最適な介入順序を設計する問題について検討する。 グラフの構造は知られており、ノードは$N$である。 頻繁性(UCBベース)とベイズ的設定に2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-08-26T16:21:31Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Minimax Optimal Quantization of Linear Models: Information-Theoretic Limits and Efficient Algorithms [59.724977092582535]
  測定から学習した線形モデルの定量化の問題を考える。 この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。 本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
  論文  参考訳（メタデータ） (2022-02-23T02:39:04Z)
• Near-Optimal Statistical Query Lower Bounds for Agnostically Learning Intersections of Halfspaces with Gaussian Marginals [10.06689891744466]
  本稿では,ガウス分布下での中間空間の学習に関するよく研究された問題について,難易度学習モデルを用いて考察する。 下界の2つの変種を証明し、それぞれがダイアコニコラスら (2021) の成分と、Boolean の設定に対する SQ 下界に対する異なる以前のアプローチ(拡張)を組み合わせた。
  論文  参考訳（メタデータ） (2022-02-10T15:34:10Z)
• The query complexity of sampling from strongly log-concave distributions in one dimension [14.18847457501901]
  Omega(loglogkappa)$の最初の厳密な下限を、強い対数凹と対数平滑な分布のクラスからサンプリングするクエリに設定する。 本稿では,この指数的ギャップを埋めるリジェクションに基づく新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-05-29T00:51:17Z)
• Complexity of zigzag sampling algorithm for strongly log-concave distributions [6.336005544376984]
  強いログ凹分布に対するジグザグサンプリングアルゴリズムの計算複雑性について検討する。 ジグザグサンプリングアルゴリズムは, 計算コストが$obiglに匹敵するchi-squareの発散において, $varepsilon$ 誤差を達成することを証明した。
  論文  参考訳（メタデータ） (2020-12-21T03:10:21Z)
• Thresholded Lasso Bandit [70.17389393497125]
  Thresholded Lasso banditは、報酬関数を定義するベクトルとスパースサポートを推定するアルゴリズムである。 一般には $mathcalO( log d + sqrtT )$ や $mathcalO( log d + sqrtT )$ としてスケールする非漸近的後悔の上界を確立する。
  論文  参考訳（メタデータ） (2020-10-22T19:14:37Z)
• 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)
• Oracle Lower Bounds for Stochastic Gradient Sampling Algorithms [39.746670539407084]
  我々は、$bbRd$の強い対数凹密度からサンプリングする問題を考察する。 必要なログ密度の勾配クエリ数に基づいて,情報理論の下界を証明した。
  論文  参考訳（メタデータ） (2020-02-01T23:46:35Z)

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

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