Fugu-MT 論文翻訳(概要): Rényi-infinity constrained sampling with $d^3$ membership queries

論文の概要: Rényi-infinity constrained sampling with $d^3$ membership queries

arxiv url: http://arxiv.org/abs/2407.12967v1
Date: Wed, 17 Jul 2024 19:20:08 GMT
ステータス: 処理完了
システム内更新日: 2024-07-19 19:33:23.299899
Title: Rényi-infinity constrained sampling with $d^3$ membership queries
Title（参考訳）: $d^3$メンバシップクエリによるRényi-infinity制約サンプリング
Authors: Yunbum Kook, Matthew S. Zhang,
Abstract要約: 本稿では,エレガントな収束保証を有する原理的かつ単純なアルゴリズムである制約付き近位サンプリング手法を提案する。 R'enyi-infinity divergence(mathcal R_infty$)に収束することを示す。
参考スコア（独自算出の注目度）: 2.209921757303168
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Uniform sampling over a convex body is a fundamental algorithmic problem, yet the convergence in KL or R\'enyi divergence of most samplers remains poorly understood. In this work, we propose a constrained proximal sampler, a principled and simple algorithm that possesses elegant convergence guarantees. Leveraging the uniform ergodicity of this sampler, we show that it converges in the R\'enyi-infinity divergence ($\mathcal R_\infty$) with no query complexity overhead when starting from a warm start. This is the strongest of commonly considered performance metrics, implying rates in $\{\mathcal R_q, \mathsf{KL}\}$ convergence as special cases. By applying this sampler within an annealing scheme, we propose an algorithm which can approximately sample $\varepsilon$-close to the uniform distribution on convex bodies in $\mathcal R_\infty$-divergence with $\widetilde{\mathcal{O}}(d^3\, \text{polylog} \frac{1}{\varepsilon})$ query complexity. This improves on all prior results in $\{\mathcal R_q, \mathsf{KL}\}$-divergences, without resorting to any algorithmic modifications or post-processing of the sample. It also matches the prior best known complexity in total variation distance.
Abstract（参考訳）: 凸体上の一様サンプリングは基本的なアルゴリズム上の問題であるが、ほとんどのサンプリング器のKLあるいはR'enyi分散の収束はよく理解されていない。本研究では,エレガントな収束保証を有する原理的かつ単純なアルゴリズムである制約付き近位サンプリング器を提案する。このサンプルの均一なエルゴディディティを利用することで、暖かい開始から開始する際のクエリの複雑さのオーバーヘッドを伴わず、R\'enyi-infinity divergence(\mathcal R_\infty$)に収束することを示す。これは一般に考慮されるパフォーマンス指標の中で最強であり、特別な場合として$\{\mathcal R_q, \mathsf{KL}\}$収束を意味する。このサンプルをアニーリング方式で適用することにより、約$\varepsilon$-closeを$\mathcal R_\infty$-divergence with $\widetilde{\mathcal{O}}(d^3\, \text{polylog} \frac{1}{\varepsilon})の凸体上の均一分布に約$\varepsilon$-closeを適用できるアルゴリズムを提案する。これは、アルゴリズムの変更やサンプルの後処理に頼ることなく、$\{\mathcal R_q, \mathsf{KL}\}$-divergences の全ての事前結果を改善する。また、全変動距離において、最もよく知られた複雑さとも一致している。

関連論文リスト

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)
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)
Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文参考訳（メタデータ） (2023-07-13T18:59:28Z)
Perfect Sampling from Pairwise Comparisons [26.396901523831534]
分散分布$mathcalD$の与えられたアクセスから最適なサンプルを効率よく取得する方法を,サポート対象の要素のペア比較に限定して検討する。固定分布が$mathcalD$と一致するマルコフ連鎖を設計し、過去からの結合技術を用いて正確なサンプルを得るアルゴリズムを提供する。
論文参考訳（メタデータ） (2022-11-23T11:20:30Z)
Sample Complexity Bounds for Learning High-dimensional Simplices in Noisy Regimes [5.526935605535376]
ノイズの多いサンプルから単純さを学習するために、サンプルの複雑さが結びついているのがわかります。我々は、$mathrmSNRgeOmegaleft(K1/2right)$ である限り、ノイズのないシステムのサンプルの複雑さは、ノイズのないケースのそれと同じ順序であることを示す。
論文参考訳（メタデータ） (2022-09-09T23:35:25Z)
Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
論文参考訳（メタデータ） (2022-07-18T12:03:26Z)
Robust Sparse Mean Estimation via Sum of Squares [42.526664955704746]
本研究では,高次元スパース平均推定の問題点を,逆数外乱の$epsilon$-fractionの存在下で検討する。我々のアルゴリズムは、サム・オブ・スクエア(Sum-of-Squares)ベースのアルゴリズムアプローチに従う。
論文参考訳（メタデータ） (2022-06-07T16:49:54Z)
Optimal Gradient Sliding and its Application to Distributed Optimization Under Similarity [121.83085611327654]
積 $r:=p + q$, ここで$r$は$mu$-strong convex類似性である。エージェントの通信やローカルコールにマスターされた問題を解決する方法を提案する。提案手法は$mathcalO(sqrtL_q/mu)$法よりもはるかにシャープである。
論文参考訳（メタデータ） (2022-05-30T14:28:02Z)
Structured Logconcave Sampling with a Restricted Gaussian Oracle [23.781520510778716]
我々は,複数のロジコンケーブファミリーを高精度にサンプリングするアルゴリズムを提案する。凸最適化における近点法にインスパイアされた縮小フレームワークをさらに発展させる。
論文参考訳（メタデータ） (2020-10-07T01:43:07Z)
Optimal Testing of Discrete Distributions with High Probability [49.19942805582874]
高確率状態に着目して離散分布を試験する問題について検討する。一定の要素でサンプル最適である近接性および独立性テストのための最初のアルゴリズムを提供する。
論文参考訳（メタデータ） (2020-09-14T16:09:17Z)
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)

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

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