  Interior point methods (IPMs) are a common approach for solving linear
programs (LPs) with strong theoretical guarantees and solid empirical
performance. The time complexity of these methods is dominated by the cost of
solving a linear system of equations at each iteration. In common applications
of linear programming, particularly in machine learning and scientific
computing, the size of this linear system can become prohibitively large,
requiring the use of iterative solvers, which provide an approximate solution
to the linear system. However, approximately solving the linear system at each
iteration of an IPM invalidates the theoretical guarantees of common IPM
analyses. To remedy this, we theoretically and empirically analyze (slightly
modified) predictor-corrector IPMs when using approximate linear solvers: our
approach guarantees that, when certain conditions are satisfied, the number of
IPM iterations does not increase and that the final solution remains feasible.
We also provide practical instantiations of approximate linear solvers that
satisfy these conditions for special classes of constraint matrices using
randomized linear algebra.
