Competitive online algorithms for resource allocation over the positive semidefinite cone
Competitive online algorithms for resource allocation over the positive semidefinite cone
复制标题
正半定锥上资源分配的竞争性在线算法
DOI：
10.1007/s10107-018-1305-1
复制
发表时间：
2018
影响因子：
2.7
通讯作者：
Fazel, Maryam
中科院分区：
文献类型：
--
作者：
Eghbali, Reza;Saunderson, James;Fazel, Maryam
我们考虑了一个新的和一般的在线资源分配问题，其目标是最大化一个函数的半正定（PSD）矩阵与标量预算约束。问题数据在线到达，算法需要在每一步做出不可撤销的决定。特别感兴趣的是在线设置中的经典实验设计问题，该算法决定是否为每个实验分配预算，因为新的实验顺序可用。我们分析了两个贪婪的原始对偶算法，并提供其竞争比的界限。我们的分析依赖于目标函数的平滑代理，该目标函数需要满足新的收益递减（PSD-DR）属性（其梯度相对于PSD锥是反序的）。利用Löwner定理给出的PSD锥上单调映射的表示，我们得到了满足PSD-DR的函数族的凸参数化。然后，我们提出了一个凸优化问题，直接优化我们在这个集合上的竞争比界。这个设计问题可以在数据开始到达之前离线解决。使用设计的平滑的在线算法是根据给定的成本函数量身定制的，并且具有至少与我们的优化界限一样好的竞争比。我们提供了计算D-最优和A-最优试验设计的光滑代理的例子，并展示了定制设计的算法的性能。
We consider a new and general online resource allocation problem, where the goal is to maximize a function of a positive semidefinite (PSD) matrix with a scalar budget constraint. The problem data arrives online, and the algorithm needs to make an irrevocable decision at each step. Of particular interest are classic experiment design problems in the online setting, with the algorithm deciding whether to allocate budget to each experiment as new experiments become available sequentially. We analyze two greedy primal-dual algorithms and provide bounds on their competitive ratios. Our analysis relies on a smooth surrogate of the objective function that needs to satisfy a new diminishing returns (PSD-DR) property (that its gradient is order-reversing with respect to the PSD cone). Using the representation for monotone maps on the PSD cone given by Löwner’s theorem, we obtain a convex parametrization of the family of functions satisfying PSD-DR. We then formulate a convex optimization problem to directly optimize our competitive ratio bound over this set. This design problem can be solvedofflinebefore the data start arriving. The online algorithm that uses the designed smoothing is tailored to the given cost function, and enjoys a competitive ratio at least as good as our optimized bound. We provide examples of computing the smooth surrogate for D-optimal and A-optimal experiment design, and demonstrate the performance of the custom-designed algorithm.
登录
查看更多内容
关于测量约束回归模型中实验的计算可处理选择
影响因子：
6
作者：
Yining Wang;Adams Wei Yu;Aarti Singh
通讯作者：
Aarti Singh
DOI：
10.1007/978-3-642-31594-7_59
发表时间：
2012-04
期刊：
--
影响因子：
--
作者：
Marco Molinaro Carnegie;Mellon R. Ravi;C. Mellon
通讯作者：
Marco Molinaro Carnegie;Mellon R. Ravi;C. Mellon
DOI：
--
发表时间：
2016
期刊：
IEEE Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
Y. Azar;Niv Buchbinder;T;Shahar Chen;I. Cohen;Anupam Gupta;Zhiyi Huang;N. Kang;V. Nagarajan;J. Naor;Debmalya Panigrahi
通讯作者：
Debmalya Panigrahi
影响因子：
2.7
作者：
Agrawal, Shipra;Wang, Zizhuo;Ye, Yinyu
通讯作者：
Ye, Yinyu
DOI：
10.21067/mpej.v5i1.5184
发表时间：
2016
期刊：
arXiv: Machine Learning
影响因子：
--
作者：
Yining Wang;Adams Wei Yu;Aarti Singh
通讯作者：
Aarti Singh