On the Convergence of Inexact Predictor-Corrector Methods for Linear Programming

Gregory Dexter, Agniva Chowdhury, Haim Avron, Petros Drineas
Proceedings of the 39th International Conference on Machine Learning, PMLR 162:5007-5038, 2022.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v162-dexter22a, title = {On the Convergence of Inexact Predictor-Corrector Methods for Linear Programming}, author = {Dexter, Gregory and Chowdhury, Agniva and Avron, Haim and Drineas, Petros}, booktitle = {Proceedings of the 39th International Conference on Machine Learning}, pages = {5007--5038}, year = {2022}, editor = {Chaudhuri, Kamalika and Jegelka, Stefanie and Song, Le and Szepesvari, Csaba and Niu, Gang and Sabato, Sivan}, volume = {162}, series = {Proceedings of Machine Learning Research}, month = {17--23 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v162/dexter22a/dexter22a.pdf}, url = {https://proceedings.mlr.press/v162/dexter22a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T On the Convergence of Inexact Predictor-Corrector Methods for Linear Programming %A Gregory Dexter %A Agniva Chowdhury %A Haim Avron %A Petros Drineas %B Proceedings of the 39th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2022 %E Kamalika Chaudhuri %E Stefanie Jegelka %E Le Song %E Csaba Szepesvari %E Gang Niu %E Sivan Sabato %F pmlr-v162-dexter22a %I PMLR %P 5007--5038 %U https://proceedings.mlr.press/v162/dexter22a.html %V 162 %X 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.
APA
Dexter, G., Chowdhury, A., Avron, H. & Drineas, P.. (2022). On the Convergence of Inexact Predictor-Corrector Methods for Linear Programming. Proceedings of the 39th International Conference on Machine Learning, in Proceedings of Machine Learning Research 162:5007-5038 Available from https://proceedings.mlr.press/v162/dexter22a.html.

Related Material