We present a local search framework to design and analyze both combinatorial algorithms and rounding algorithms for experimental design problems. This framework provides a unifying approach to match and improve all known results in D/A/E-design and to obtain new results in previously unknown settings. For combinatorial algorithms, we provide a new analysis of the classical Fedorov's exchange method. We prove that this simple local search algorithm works well as long as there exists an almost optimal solution with good condition number. Moreover, we design a new combinatorial local search algorithm for E-design using the regret minimization framework. For rounding algorithms, we provide a unified randomized exchange algorithm to match and improve previous results for D/A/E-design. Furthermore, the algorithm works in the more general setting to approximately satisfy multiple knapsack constraints, which can be used for weighted experimental design and for incorporating fairness constraints into experimental design.


翻译:我们提出了一个本地搜索框架,用于设计和分析用于实验设计问题的组合算法和四舍五入算法。这个框架提供了一种统一的方法,以匹配和改进D/A/E-设计中所有已知结果,并在先前未知的环境下获得新结果。对于组合算法,我们提供了对古典Fedorov的交换方法的新分析。我们证明,只要存在一个具有良好条件编号的近乎最佳的解决方案,这种简单的本地搜索算法是有效的。此外,我们设计了一种新的组合本地搜索算法,用于使用最小度最小化框架进行电子设计。对于四舍五入算法,我们提供了一种统一的随机交换算法,以匹配和改进D/A/E-设计先前的结果。此外,在更笼统的环境下,算法可以大致满足多种 knapsack 限制,这些限制可用于加权实验设计,并将公平性限制纳入实验设计。

0
下载
关闭预览

相关内容

因果图,Causal Graphs,52页ppt
专知会员服务
250+阅读 · 2020年4月19日
专知会员服务
61+阅读 · 2020年3月19日
强化学习最新教程,17页pdf
专知会员服务
181+阅读 · 2019年10月11日
LibRec 精选:AutoML for Contextual Bandits
LibRec智能推荐
7+阅读 · 2019年9月19日
Hierarchically Structured Meta-learning
CreateAMind
27+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
29+阅读 · 2019年5月18日
LibRec 精选:位置感知的长序列会话推荐
LibRec智能推荐
3+阅读 · 2019年5月17日
逆强化学习-学习人先验的动机
CreateAMind
16+阅读 · 2019年1月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
18+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
43+阅读 · 2019年1月3日
RL 真经
CreateAMind
5+阅读 · 2018年12月28日
Linguistically Regularized LSTMs for Sentiment Classification
黑龙江大学自然语言处理实验室
8+阅读 · 2018年5月4日
Arxiv
0+阅读 · 2021年2月22日
Arxiv
0+阅读 · 2021年2月17日
Arxiv
3+阅读 · 2018年2月24日
Arxiv
3+阅读 · 2016年2月24日
VIP会员
相关资讯
LibRec 精选:AutoML for Contextual Bandits
LibRec智能推荐
7+阅读 · 2019年9月19日
Hierarchically Structured Meta-learning
CreateAMind
27+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
29+阅读 · 2019年5月18日
LibRec 精选:位置感知的长序列会话推荐
LibRec智能推荐
3+阅读 · 2019年5月17日
逆强化学习-学习人先验的动机
CreateAMind
16+阅读 · 2019年1月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
18+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
43+阅读 · 2019年1月3日
RL 真经
CreateAMind
5+阅读 · 2018年12月28日
Linguistically Regularized LSTMs for Sentiment Classification
黑龙江大学自然语言处理实验室
8+阅读 · 2018年5月4日
Top
微信扫码咨询专知VIP会员