論文の概要: Rejection sampling from shape-constrained distributions in sublinear time

• arxiv url: http://arxiv.org/abs/2105.14166v1
• Date: Sat, 29 May 2021 01:00:42 GMT
• ステータス: 処理完了
• システム内更新日: 2021-06-01 17:30:44.247118
• Title: Rejection sampling from shape-constrained distributions in sublinear time
• Title（参考訳）: 部分線形時間における形状制約分布からの拒絶サンプリング
• Authors: Sinho Chewi, Patrik Gerber, Chen Lu, Thibaut Le Gouic, Philippe Rigollet
• Abstract要約: 離散分布の様々なクラスを対象としたミニマックスフレームワークにおいて,リジェクションサンプリングのクエリ複雑性について検討した。 本研究は,アルファベットサイズに比例して複雑度が増大するサンプリングのための新しいアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 14.18847457501901
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the task of generating exact samples from a target distribution, known up to normalization, over a finite alphabet. The classical algorithm for this task is rejection sampling, and although it has been used in practice for decades, there is surprisingly little study of its fundamental limitations. In this work, we study the query complexity of rejection sampling in a minimax framework for various classes of discrete distributions. Our results provide new algorithms for sampling whose complexity scales sublinearly with the alphabet size. When applied to adversarial bandits, we show that a slight modification of the Exp3 algorithm reduces the per-iteration complexity from $\mathcal O(K)$ to $\mathcal O(\log^2 K)$, where $K$ is the number of arms.
• Abstract（参考訳）: 対象分布から有限アルファベット上の正規化までの正確なサンプルを生成するタスクを考察する。 このタスクの古典的なアルゴリズムは拒絶サンプリングであり、何十年にもわたって実際に使われてきたが、その基本的な限界についてはほとんど研究されていない。 本研究では,離散分布の様々なクラスを対象としたミニマックスフレームワークにおいて,リジェクションサンプリングのクエリ複雑性について検討する。 本研究は,アルファベットサイズに比例して複雑度が増加するサンプリングアルゴリズムを提案する。 敵の包帯に適用すると、Exp3アルゴリズムのわずかな変更により、各項目毎の複雑性が$\mathcal O(K)$から$\mathcal O(\log^2K)$に減少し、$K$が腕の数であることを示す。

関連論文リスト

• Optimal Multi-Distribution Learning [88.3008613028333]
  マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。 本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-08T16:06:29Z)
• Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise [50.64137465792738]
  ランダム分類ノイズを用いたPAC$gamma$-marginハーフスペースの問題について検討する。 我々は、問題のサンプル複雑性と計算効率の良いアルゴリズムのサンプル複雑性との間に固有のギャップを示唆する情報計算トレードオフを確立する。
  論文  参考訳（メタデータ） (2023-06-28T16:33:39Z)
• On-Demand Sampling: Learning Optimally from Multiple Distributions [63.20009081099896]
  社会と現実世界の考察は、マルチディストリビューション学習パラダイムの台頭につながっている。 これらの学習パラダイムの最適なサンプル複雑性を確立し、このサンプル複雑性を満たすアルゴリズムを提供する。 アルゴリズムの設計と解析は,ゼロサムゲーム解決のためのオンライン学習手法の拡張によって実現されている。
  論文  参考訳（メタデータ） (2022-10-22T19:07:26Z)
• Undersampling is a Minimax Optimal Robustness Intervention in Nonparametric Classification [28.128464387420216]
  マイノリティグループサンプルの欠如によって学習が根本的に制約されていることを示す。 特にラベルシフトの場合、最小値のアンダーサンプリングアルゴリズムが常に存在することを示す。
  論文  参考訳（メタデータ） (2022-05-26T00:35:11Z)
• A Proximal Algorithm for Sampling from Non-convex Potentials [14.909442791255042]
  滑らかさに欠ける非滑らかなポテンシャルの問題を考察する。 滑らかではなく、ポテンシャルは半滑らかあるいは多重多重滑らか関数であると仮定される。 我々は、交互サンプリングフレームワークとして知られるGibbsサンプリングの特殊なケースを開発する。
  論文  参考訳（メタデータ） (2022-05-20T13:58:46Z)
• Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
  クラスタリングは教師なし学習における基本的なプリミティブである。 最近の研究は、低次手法のクラスに対する低い境界を確立している。 意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
  論文  参考訳（メタデータ） (2021-12-07T18:50:17Z)
• Improved Algorithms for Agnostic Pool-based Active Classification [20.12178157010804]
  プールに依存しない環境でのバイナリ分類のためのアクティブラーニングを検討する。 我々のアルゴリズムは、画像分類データセットにおけるアートアクティブな学習アルゴリズムの状況よりも優れている。
  論文  参考訳（メタデータ） (2021-05-13T18:24:30Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Bandits [34.06611065493047]
  本稿では、信頼度と予算設定の固定化において、純探索線形帯域問題に対する近似アルゴリズムを提案する。 サンプルの複雑性がインスタンスの幾何でスケールし、アームの数に縛られた明示的な結合を避けるアルゴリズムを提供する。 また,固定予算設定における線形帯域幅に対する最初のアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-21T00:56:33Z)
• Nearly Linear Row Sampling Algorithm for Quantile Regression [54.75919082407094]
  データの次元にほぼ線形なサンプル複雑性を持つ量子化損失関数の行サンプリングアルゴリズムを提案する。 行サンプリングアルゴリズムに基づいて、量子レグレッションの最も高速なアルゴリズムと、バランスの取れた有向グラフのグラフスペーシフィケーションアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-15T13:40:07Z)
• Learning Structured Distributions From Untrusted Batches: Faster and Simpler [26.57313255285721]
  本稿では,Qiao と Valiant [QV17] が導入した信頼できないバッチから学ぶことの問題点を再考する。 我々は,[JO19] と [CLM19] の技法を合成して両世界の長所を与える,魅力的な方法を見出した。
  論文  参考訳（メタデータ） (2020-02-24T18:32:10Z)

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

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