在线学习最小 - 最大离散问题

作者：Evripidis Bampis,Dimitris Christou,Bruno Escoffier,Nguyen Kim Thang

摘要：我们在在线学习框架中研究各种离散非线性组合优化问题。在第一部分中，我们讨论了是否存在负面结果表明获得消失（甚至消失的近似）离散的计算难度的问题。我们提供了平均水平的减少值，表明许多（最小 - 最大）多项式时间可解决的问题不仅没有消失的遗憾，而且对于某些α（除非NP = BPP）也没有消失的近似α-遗憾。然后，我们关注特定的最小 - 最大问题，即顶点覆盖问题的最小 - 最大版本，其可在离线情况下在多项式时间内解决。之前的减少证明没有（2-ε）-regret在线算法，除非Unique Game在inBPP中;我们证明了一个匹配的上界，提供了一种基于在线梯度下降法的在线算法。然后，我们将注意力转向基于离线优化oracle的在线学习算法，在给定一组问题实例的情况下，该算法能够计算出最优的静态解决方案。我们证明了对于不同的非线性离散优化问题，即使在静态情况下可以在多项式时间内解决的问题（例如min-max顶点覆盖，min-max完美匹配，等等。）。从积极的方面来说，我们提出了一个消失后悔的在线算法，该算法基于跟随扰动的领导算法进行广义背包问题。

原文标题：Online-Learning for min-max discrete problems

原文摘要：We study various discrete nonlinear combinatorial optimization problems in an online learning framework. In the first part, we address the question of whether there are negative results showing that getting a vanishing (or even vanishing approximate) regret is computational hard. We provide a general reduction showing that many (min-max) polynomial time solvable problems not only do not have a vanishing regret, but also no vanishing approximationα-regret, for someα(unlessNP=BPP). Then, we focus on a particular min-max problem, the min-max version of the vertex cover problem which is solvable in polynomial time in the offline case. The previous reduction proves that there is no(2−ϵ)-regret online algorithm, unless Unique Game is inBPP; we prove a matching upper bound providing an online algorithm based on the online gradient descent method. Then, we turn our attention to online learning algorithms that are based on an offline optimization oracle that, given a set of instances of the problem, is able to compute the optimum static solution. We show that for different nonlinear discrete optimization problems, it is stronglyNP-hard to solve the offline optimization oracle, even for problems that can be solved in polynomial time in the static case (e.g. min-max vertex cover, min-max perfect matching, etc.). On the positive side, we present an online algorithm with vanishing regret that is based on the follow the perturbed leader algorithm for a generalized knapsack problem.

地址：https://arxiv.org/abs/1907.05944