Nearly Optimal Linear Convergence of Stochastic Primal-Dual Methods for Linear Programming
This work addresses the need for efficient algorithms for linear programming, offering a stochastic method with improved per-iteration cost and competitive performance, though it is incremental in advancing existing primal-dual techniques.
The authors tackled the problem of solving linear programming (LP) with first-order methods by proposing a stochastic primal-dual algorithm using variance reduction and restarts, achieving a linear convergence rate with high probability and nearly optimal complexity up to logarithmic terms.
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.