Nearly Optimal Linear Convergence of Stochastic Primal-Dual Methods for Linear Programming

Haihao Lu, Jinwen Yang

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 sha…