Fugu-MT 論文翻訳(概要): Oracle-based Uniform Sampling from Convex Bodies

論文の概要: Oracle-based Uniform Sampling from Convex Bodies

arxiv url: http://arxiv.org/abs/2510.02983v1
Date: Fri, 03 Oct 2025 13:21:05 GMT
ステータス: 翻訳完了
システム内更新日: 2025-10-06 16:35:52.393892
Title: Oracle-based Uniform Sampling from Convex Bodies
Title（参考訳）: 凸体からのOracleベースの一様サンプリング
Authors: Thanh Dang, Jiaming Liang,
Abstract要約: 我々は新しいマルコフ連鎖モンテカルロアルゴリズムを提案し、凸体上の一様分布をK$とする。提案アルゴリズムは,Gibsサンプリングを用いたAlternating Smpling Framework/proximal samplerに基づく。
参考スコア（独自算出の注目度）: 2.087898608419977
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We propose new Markov chain Monte Carlo algorithms to sample a uniform distribution on a convex body $K$. Our algorithms are based on the Alternating Sampling Framework/proximal sampler, which uses Gibbs sampling on an augmented distribution and assumes access to the so-called restricted Gaussian oracle (RGO). The key contribution of this work is the efficient implementation of RGO for uniform sampling on $K$ via rejection sampling and access to either a projection oracle or a separation oracle on $K$. In both oracle cases, we establish non-asymptotic complexities to obtain unbiased samples where the accuracy is measured in R\'enyi divergence or $\chi^2$-divergence.
Abstract（参考訳）: 我々は新しいマルコフ連鎖モンテカルロアルゴリズムを提案し、凸体上の一様分布をK$とする。このアルゴリズムは,拡張分布上でギブズサンプリングを使用し,いわゆる制限ガウスオラクル(RGO)へのアクセスを前提としている。この研究の重要な貢献は、$K$上の一様サンプリングのためのRGOの効率的な実装と、$K$上の射影オラクルまたは分離オラクルへのアクセスである。どちらのオラクルの場合も、R'enyiの発散や$\chi^2$-divergenceの精度が測定されるような不偏のサンプルを得るために、非漸近複雑度を確立する。

関連論文リスト

Constrained and Composite Sampling via Proximal Sampler [2.087898608419977]
本研究では,制約サンプリングと複合サンプリングの2つの対数凹型サンプリング問題について検討する。主な課題は、ミキシングを劣化させることなくフィージビリティを強制することである。複合サンプリングでは、ターゲットは$exp(-f(x)-h(x))$に比例する。
論文参考訳（メタデータ） (2026-02-16T05:36:36Z)
Wedge Sampling: Efficient Tensor Completion with Nearly-Linear Sample Complexity [9.42598427201735]
低ランクテンソル補完のための新しい非適応サンプリングスキームであるウェッジサンプリングを導入する。次数$kの低ランクテンソルの次元$n倍の倍数n$を、そのエントリのサブセットから復元する。
論文参考訳（メタデータ） (2026-02-05T16:47:13Z)
Approximating a RUM from Distributions on k-Slates [88.32814292632675]
与えられた分布を平均で最もよく近似するRUMを求める一般化時間アルゴリズムを求める。我々の理論的結果は、実世界のデータセットに効果的でスケール可能なものを得るという、実践的な結果も得られます。
論文参考訳（メタデータ） (2023-05-22T17:43:34Z)
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)
On-Demand Sampling: Learning Optimally from Multiple Distributions [63.20009081099896]
社会と現実世界の考察は、マルチディストリビューション学習パラダイムの台頭につながっている。これらの学習パラダイムの最適なサンプル複雑性を確立し、このサンプル複雑性を満たすアルゴリズムを提供する。アルゴリズムの設計と解析は,ゼロサムゲーム解決のためのオンライン学習手法の拡張によって実現されている。
論文参考訳（メタデータ） (2022-10-22T19:07:26Z)
Langevin Monte Carlo for Contextual Bandits [72.00524614312002]
Langevin Monte Carlo Thompson Sampling (LMC-TS) が提案されている。提案アルゴリズムは,文脈的帯域幅の特別な場合において,最高のトンプソンサンプリングアルゴリズムと同じサブ線形残差を達成できることを示す。
論文参考訳（メタデータ） (2022-06-22T17:58:23Z)
Rejection sampling from shape-constrained distributions in sublinear time [14.18847457501901]
離散分布の様々なクラスを対象としたミニマックスフレームワークにおいて,リジェクションサンプリングのクエリ複雑性について検討した。本研究は,アルファベットサイズに比例して複雑度が増大するサンプリングのための新しいアルゴリズムを提案する。
論文参考訳（メタデータ） (2021-05-29T01:00:42Z)
Revisiting the Sample Complexity of Sparse Spectrum Approximation of Gaussian Processes [60.479499225746295]
本稿では,ガウス過程に対して,パラメータ空間全体に対して同時に保持可能な保証付きスケーラブルな近似を導入する。我々の近似は、スパーススペクトルガウス過程(SSGP)のための改良されたサンプル複雑性解析から得られる。
論文参考訳（メタデータ） (2020-11-17T05:41:50Z)
A Provably Efficient Sample Collection Strategy for Reinforcement Learning [123.69175280309226]
オンライン強化学習(RL)における課題の1つは、エージェントがその振る舞いを最適化するために、環境の探索とサンプルの活用をトレードオフする必要があることである。 1) 生成モデル(環境のスパースシミュレータなど)にアクセス可能な状態のサンプル数を規定する「対象別」アルゴリズム,2) 所定のサンプルをできるだけ早く生成する「対象別」サンプル収集。
論文参考訳（メタデータ） (2020-07-13T15:17:35Z)
Composite Logconcave Sampling with a Restricted Gaussian Oracle [23.781520510778716]
dpi(x) propto exp(-f(x) - g(x)dx)$ for well-conditioned $f$ and convex (しかし、おそらくは非滑らか) $g$ である。 for $f$ with condition number $kappa$, our algorithm run in $O left(kappa2 d log2tfrackappa depsilonright)$, each querying a gradient of $f$
論文参考訳（メタデータ） (2020-06-10T17:43:55Z)

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