Using Optimization to Solve Positive LPs Faster in Parallel
Allen-Zhu, Orecchia · cs.DS,cs.DC,cs.NA,math.NA,math.OC · 2016-11-13 · 原文
Positive linear programs (LP), also known as packing and covering linear programs, are an important class of problems that bridges computer science, operations research, and optimization. Despite the consistent efforts on this problem, all known nearly-linear-time algorithms require \tilde{O}(\varepsilon^{-4}) iterations to converge to 1\pm \varepsilon approximate solutions. This \varepsilon^{-4} dependence has not been improved since 1993, and limits the performance of parallel implementations for such algorithms. Moreover, previous algorithms and their analyses rely on update steps and convergence arguments that are combinatorial in nature and do not seem to arise naturally from an optimization viewpoint. In this paper, we leverage new insights from optimization theory to construct a novel algorithm that breaks the longstanding \varepsilon^{-4} barrier. Our algorithm has a simple analysis and a clear motivation. Our work introduces a number of novel techniques, such as the combined application of gradient descent and mirror descent, and a truncated, smoothed version of the standard multiplicative weight update, which may be of independent interest.
讲义
讲义·推断 依据「原文」自动生成的结构化摘要（推断），非原文表述；以原文为准。
1. 人话版
Positive linear programs (LP), also known as packing and covering linear programs, are an important class of problems that bridges computer science, operations research, and optimization.
Despite the consistent efforts on this problem, all known nearly-linear-time algorithms require \tilde{O}(\varepsilon^{-4}) iterations to converge to 1\pm \varepsilon approximate solutions.
2. 领域脉络
本文类目：cs.DS、cs.DC、cs.NA、math.NA、math.OC，属于其所在研究脉络的最新进展。
3. 机制拆解
Moreover, previous algorithms and their analyses rely on update steps and convergence arguments that are combinatorial in nature and do not seem to arise naturally from an optimization viewpoint.
4. 证据与数字
This \varepsilon^{-4} dependence has not been improved since 1993, and limits the performance of parallel implementations for such algorithms.
In this paper, we leverage new insights from optimization theory to construct a novel algorithm that breaks the longstanding \varepsilon^{-4} barrier.
5. 反例与边界
摘要未声明局限与反例——这是需要警惕的信号，精读时先问边界。
6. 跨领域连接与意外收获
横跨 5 个类目（cs.DS、cs.DC、cs.NA、math.NA），关注其在你兴趣板块间的迁移面。
7. 可复用方法
把本文机制与你手头项目对照，找一个两周内能验证的最小实验。
8. 术语表
精读时把不熟的术语记入此处，作为下次回忆的锚点。