Combining Regularization with Look-Ahead for Competitive Online Convex Optimization
Combining Regularization with Look-Ahead for Competitive Online Convex Optimization
复制标题
DOI：
10.1109/infocom42981.2021.9488766
复制
发表时间：
2021-05
期刊：
影响因子：
--
通讯作者：
Ming Shi;Xiaojun Lin;Lei Jiao
中科院分区：
文献类型：
--
作者：
Ming Shi;Xiaojun Lin;Lei Jiao
利用有限的外观以实现在线凸优化（OCO）的低竞争比率。但是，现有的在线算法（例如平均固定的地平线控制（AFHC））可以利用外观来降低竞争比仍然会产生竞争比，这些比率仍然会随着系数比率而不受限制（即，开关-SCOST系数的最大比率和服务成本系数的最大比率）增加了。另一方面，正则化方法可以达到系数比率较大时保持有限的竞争比率，但它并不能从中受益。在本文中，我们提出了一种新算法，称为look-head（RLA），可以在AFHC和正则化方法中获得最好的算法，即，当该系数比率很小时，其竞争比随着图的窗口尺寸而降低，并且在该系数较大时保持界限。我们还为所有在线算法的竞争比率提供了匹配的下限，而look-averm却与RLA的可实现的竞争比率不同，而RLA的竞争比率仅取决于问题大小。 RLA的竞争分析涉及对在线原始二重要分析对案例的非平凡概括。
There has been significant interest in leveraging limited look-ahead to achieve low competitive ratios for online convex optimization (OCO). However, existing online algorithms (such as Averaging Fixed Horizon Control (AFHC)) that can leverage look-ahead to reduce the competitive ratios still produce competitive ratios that grow unbounded as the coefficient ratio (i.e., the maximum ratio of the switching-cost coefficient and the service-cost coefficient) increases. On the other hand, the regularization method can attain a competitive ratio that remains bounded when the coefficient ratio is large, but it does not benefit from look-ahead. In this paper, we propose a new algorithm, called Regularization with Look-Ahead (RLA), that can get the best of both AFHC and the regularization method, i.e., its competitive ratio decreases with the look-ahead window size when the coefficient ratio is small, and remains bounded when the coefficient ratio is large. We also provide a matching lower bound for the competitive ratios of all online algorithms with look-ahead, which differs from the achievable competitive ratio of RLA by a factor that only depends on the problem size. The competitive analysis of RLA involves a non-trivial generalization of online primal-dual analysis to the case with look-ahead.