The result that restarted primal-dual hybrid gradient (rPDHG), a matrix-free first-order method, solves linear programs in polynomial time with high probability under random (Gaussian / sub-Gaussian) data models. The analysis expresses rPDHG's convergence through LP-specific condition measures governing how quickly iterates identify the optimal basis and then converge to an epsilon-optimal point, and uses sub-Gaussian concentration to bound those measures for random instances -- turning worst-case, condition-number-dependent rates into average-case polynomial guarantees that explain the empirical scalability of PDHG-based LP solvers.
Xiong (MIT) proves high-probability polynomial-time complexity for restarted primal-dual hybrid gradient (rPDHG), a matrix-free first-order method for linear programming (LP) in standard form. Under …