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.


翻译:我们考虑的是从一个已知为正常化的目标分布中生成精确样本的任务。 这项工作的经典算法是拒绝抽样, 尽管它实际上已经使用了数十年, 却很少研究它的基本局限性。 在这项工作中, 我们研究的是拒绝抽样在各种离散分布类型迷你马克框架中的质询复杂性。 我们的结果为取样提供了新的算法, 其复杂性以字母大小为亚直线的精度。 当应用到对抗性强盗时, 我们显示对Exp3算法略作修改后, 使每通量复杂性从 $\ mathcal O(K) 降低到 $\ mathcal O( log2K) 美元, 即武器数量为$ 。

0
下载
关闭预览

相关内容

Linux导论,Introduction to Linux,96页ppt
专知会员服务
78+阅读 · 2020年7月26日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
109+阅读 · 2020年5月15日
深度强化学习策略梯度教程,53页ppt
专知会员服务
178+阅读 · 2020年2月1日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
已删除
将门创投
4+阅读 · 2018年6月26日
Arxiv
0+阅读 · 2021年7月22日
Arxiv
0+阅读 · 2021年7月22日
Arxiv
0+阅读 · 2021年7月19日
Few Shot Learning with Simplex
Arxiv
5+阅读 · 2018年7月27日
VIP会员
相关VIP内容
Linux导论,Introduction to Linux,96页ppt
专知会员服务
78+阅读 · 2020年7月26日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
109+阅读 · 2020年5月15日
深度强化学习策略梯度教程,53页ppt
专知会员服务
178+阅读 · 2020年2月1日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
相关资讯
已删除
将门创投
4+阅读 · 2018年6月26日
Top
微信扫码咨询专知VIP会员