First passage time in geometric resetting of first-order methods in linear programming

Restart strategies play a central role in the performance of first order methods for large-scale linear programming, such as primal-dual hybrid gradient (PDHG) methods. We study mean first passage time of geometric restarting in an abstraction of such methods. This yields a dispersion criterion that characterizes whether introducing a sufficiently small restart probability improves or worsens expected first passage time. We corroborate these criterion through controlled experiments on linear programming instances. The experiments closely agree with the analytical formula, while restarted PDHG experiments exhibit a substantial slowdown in a negative-dispersion regime, consistent with the predicted direction. We further evaluate variants of the restart policy on Mittelmann benchmark instances.