Unified Acceleration Method for Packing and Covering Problems via Diameter Reduction
Unified Acceleration Method for Packing and Covering Problems via Diameter Reduction
复制标题
通过直径减小解决堆积和覆盖问题的统一加速方法
DOI：
10.4230/lipics.icalp.2016.50
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Michael W. Mahoney
中科院分区：
文献类型：
--
作者：
Di Wang;Satish Rao;Michael W. Mahoney
最近Allen-Zhu和Orecchia提出了一种线性耦合方法来求解凸优化问题，它提供了一种概念上简单的方法，在每次迭代中集成梯度下降步骤和镜像下降步骤。线性耦合方法的高级方法是非常灵活的，并且通过提供用于包装和覆盖线性规划的改进算法而显示出初步的希望。然而，令人惊讶的是，虽然填充问题的收敛速度对误差参数的依赖性提高到了O（1/\n）$，这对应于加速梯度方法的设计目标，但覆盖问题的依赖性只提高到了O（1/\n ^{1.5}）$，甚至需要一个不同的更复杂的算法。考虑到填充和覆盖问题之间的密切联系，并且由于这些非常相关的问题的先前算法已经导致了相同的$\n $依赖性，这种差异是令人惊讶的，并且它留下了线性耦合在协调算法的互补梯度和镜像下降步骤中发挥的确切作用的问题。在本文中，我们澄清了包装和覆盖线性规划的线性耦合算法的这些问题，说明线性耦合方法可以以统一的方式导致包装和覆盖问题的改进的O（1/\n）$依赖性，即，用相同的算法和几乎相同的分析我们的主要技术成果是一种新的直径减少方法覆盖的问题，是独立的利益，这可能是有用的加速线性耦合方法应用到其他组合问题。
The linear coupling method was introduced recently by Allen-Zhu and Orecchia for solving convex optimization problems with first order methods, and it provides a conceptually simple way to integrate a gradient descent step and mirror descent step in each iteration. The high-level approach of the linear coupling method is very flexible, and it has shown initial promise by providing improved algorithms for packing and covering linear programs. Somewhat surprisingly, however, while the dependence of the convergence rate on the error parameter $\epsilon$ for packing problems was improved to $O(1/\epsilon)$, which corresponds to what accelerated gradient methods are designed to achieve, the dependence for covering problems was only improved to $O(1/\epsilon^{1.5})$, and even that required a different more complicated algorithm. Given the close connections between packing and covering problems and since previous algorithms for these very related problems have led to the same $\epsilon$ dependence, this discrepancy is surprising, and it leaves open the question of the exact role that the linear coupling is playing in coordinating the complementary gradient and mirror descent step of the algorithm. In this paper, we clarify these issues for linear coupling algorithms for packing and covering linear programs, illustrating that the linear coupling method can lead to improved $O(1/\epsilon)$ dependence for both packing and covering problems in a unified manner, i.e., with the same algorithm and almost identical analysis. Our main technical result is a novel diameter reduction method for covering problems that is of independent interest and that may be useful in applying the accelerated linear coupling method to other combinatorial problems.