Linear Convergence of Stochastic Primal Dual Methods for Linear Programming Using Variance Reduction and Restarts

11/10/2021

∙

by   Haihao Lu, et al.

∙

0

∙

share

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 sharp instances with a high probability, which improves the complexity of the existing deterministic and stochastic algorithms. In addition, we propose an efficient coordinate-based stochastic oracle for unconstrained bilinear problems, which has 𝒪(1) per iteration cost and improves the total flop counts to reach a certain accuracy.