There is a recent interest on first-order methods for linear programming (LP). In this paper,we propose a stochastic algorithm using variance reduction and restarts for solving sharp primal-dual problems such as LP. We show that the proposed stochastic method exhibits a linear convergence rate for solving sharp instances with a high probability. In addition, we propose an efficient coordinate-based stochastic oracle for unconstrained bilinear problems, which has $\mathcal O(1)$ per iteration cost and improves the complexity of the existing deterministic and stochastic algorithms. Finally, we show that the obtained linear convergence rate is nearly optimal (upto $\log$ terms) for a wide class of stochastic primal dual methods.
翻译:最近有人对线性编程的第一阶方法(LP)感兴趣。在本文中,我们提出使用差异减少和重新启动的随机算法来解决尖锐的原始和双重问题(如LP)。我们表明,拟议的随机方法显示了一种线性趋同率,以极有可能的方式解决尖锐的事例。此外,我们建议对未受约束的双线性问题采用一种高效的基于协调的随机拼凑法,即每迭代费用为$\mathcal O(1)美元,提高现有确定性和随机性算法的复杂性。最后,我们表明,获得的线性趋同率对于一系列广泛的随机性初线性双轨方法来说几乎是最佳的(最高为$\log$ )。