论文标题
通过原始偶尔的在线凸问题的强大算法
Robust Algorithms for Online Convex Problems via Primal-Dual
论文作者
论文摘要
在线优化中的原始偶对偶二方法在这两个最常见的模型中提供了几种最先进的结果：对抗和随机/随机秩序。在这里，我们试图提供对原始偶算法的更统一的分析，以更好地了解这种重要方法背后的机制。因此，我们能够恢复和扩展文献的几个结果。 特别是，对于相当一般的在线凸问题，我们获得了强大的在线算法：我们考虑了混合模型，其中某些时间步骤是随机数据是随机的，而在其他时间则是对抗性的。对抗时间步骤的数量和位置都是算法所未知的。我们的算法的保证在每个纯模型的（接近）最佳保证之间插值。特别是，对抗时代的存在不会降低相对于实例的随机部分的保证。 具体而言，我们首先考虑在线凸面编程：每次揭示可行的集合$ v_t $，并且算法需要选择$ v_t \ in V_T $中的$ v_t \，以最大程度地减少总成本$ψ（\ sum_t v_t v_t）$，对于coNvex函数$ψ$。我们在混合模型上针对此问题的强大原始二重算法恢复并扩展了Gupta等人的结果。以及作者$ \ ell_p $ -norm负载平衡的最新工作。我们还考虑了福利最大化的问题，并以凸生产成本为：每次客户提出一个值$ c_t $和资源消耗量向量$ a_t $，目标是分数选择客户以最大化利润$ \ sum_t c_t c_t c_t c_t x_t x_t -ψ（\ sum_t a_t a_t a_t x_t x_t x_t）$。我们在混合模型上的强大原始二重算法恢复并扩展了Azar等人的结果。 鉴于原始二偶有算法的普遍性，我们希望此处提出的想法对于获得混合或相关模型中的其他健壮算法将很有用。
Primal-dual methods in online optimization give several of the state-of-the art results in both of the most common models: adversarial and stochastic/random order. Here we try to provide a more unified analysis of primal-dual algorithms to better understand the mechanisms behind this important method. With this we are able of recover and extend in one goal several results of the literature. In particular, we obtain robust online algorithm for fairly general online convex problems: we consider the MIXED model where in some of the time steps the data is stochastic and in the others the data is adversarial. Both the quantity and location of the adversarial time steps are unknown to the algorithm. The guarantees of our algorithms interpolate between the (close to) best guarantees for each of the pure models. In particular, the presence of adversarial times does not degrade the guarantee relative to the stochastic part of the instance. Concretely, we first consider Online Convex Programming: at each time a feasible set $V_t$ is revealed, and the algorithm needs to select $v_t \in V_t$ to minimize the total cost $ψ(\sum_t v_t)$, for a convex function $ψ$. Our robust primal-dual algorithm for this problem on the MIXED model recovers and extends, for example, a result of Gupta et al. and recent work on $\ell_p$-norm load balancing by the author. We also consider the problem of Welfare Maximization with Convex Production Costs: at each time a customer presents a value $c_t$ and resource consumption vector $a_t$, and the goal is to fractionally select customers to maximize the profit $\sum_t c_t x_t - ψ(\sum_t a_t x_t)$. Our robust primal-dual algorithm on the MIXED model recovers and extends the result of Azar et al. Given the ubiquity of primal-dual algorithms we hope the ideas presented here will be useful in obtaining other robust algorithm in the MIXED or related models.
