Learning-Augmented Algorithms for Online Linear and Semidefinite Programming
Learning-Augmented Algorithms for Online Linear and Semidefinite Programming
复制标题
DOI：
10.48550/arxiv.2209.10614
复制
发表时间：
2022-09
期刊：
影响因子：
--
通讯作者：
Elena Grigorescu;Young-San Lin;Sandeep Silwal;Maoyuan Song;Samson Zhou
中科院分区：
文献类型：
--
作者：
Elena Grigorescu;Young-San Lin;Sandeep Silwal;Maoyuan Song;Samson Zhou
半定规划（SDP）是一个统一的框架，它概括了线性规划和二次约束二次规划，同时在理论和实践中也产生了有效的求解器。然而，当覆盖SDP的约束以在线方式到达时，存在用于近似最优解的已知不可能结果。在本文中，我们研究了在线覆盖的线性和半定的计划，其中的算法是增加了一个可能错误的预测咨询。我们表明，如果预测是准确的，我们可以有效地绕过这些不可能的结果，并实现一个常数因子近似的最优解，即，一致性另一方面，如果预测器是不准确的，在某些技术条件下，我们实现了与经典最优上界和紧下界都匹配到常数因子的结果，即，鲁棒性更广泛地说，我们引入了一个框架，扩展了（1）由Bamas，Maggiori和Svensson研究的机器学习预测器增强的在线集合覆盖问题（NeurIPS 2020），以及（2）由Elad，Kale和Naor发起的在线覆盖SDP问题（ICALP 2016）。具体来说，我们得到了一般的在线学习增强算法覆盖线性规划与分数的建议和约束，并开始学习增强算法覆盖SDP问题的研究。我们的技术基于Buchbinder和Naor的原始-对偶框架（Mathematics of Operations Research，34，2009），并且可以进一步调整以处理变量位于有界区域中的约束，即，框约束。
Semidefinite programming (SDP) is a unifying framework that generalizes both linear programming and quadratically-constrained quadratic programming, while also yielding efficient solvers, both in theory and in practice. However, there exist known impossibility results for approximating the optimal solution when constraints for covering SDPs arrive in an online fashion. In this paper, we study online covering linear and semidefinite programs in which the algorithm is augmented with advice from a possibly erroneous predictor. We show that if the predictor is accurate, we can efficiently bypass these impossibility results and achieve a constant-factor approximation to the optimal solution, i.e., consistency. On the other hand, if the predictor is inaccurate, under some technical conditions, we achieve results that match both the classical optimal upper bounds and the tight lower bounds up to constant factors, i.e., robustness. More broadly, we introduce a framework that extends both (1) the online set cover problem augmented with machine-learning predictors, studied by Bamas, Maggiori, and Svensson (NeurIPS 2020), and (2) the online covering SDP problem, initiated by Elad, Kale, and Naor (ICALP 2016). Specifically, we obtain general online learning-augmented algorithms for covering linear programs with fractional advice and constraints, and initiate the study of learning-augmented algorithms for covering SDP problems. Our techniques are based on the primal-dual framework of Buchbinder and Naor (Mathematics of Operations Research, 34, 2009) and can be further adjusted to handle constraints where the variables lie in a bounded region, i.e., box constraints.