Randomized Numerical Linear Algebra for Interior Point Methods

Abstract: Linear programming is a central problem in computer science and applied mathematics with numerous applications across a wide range of domains, including machine learning and data science.  Interior point methods (IPMs) are a common approach to solving linear programs 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 data science 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. Approximately solving the linear system at each iteration of an IPM invalidates common analyses of IPMs and the theoretical guarantees they provide.  In this talk, we will discuss how randomized linear algebra can be used to design and analyze theoretically and practically efficient IPMs when using approximate linear solvers.

Speaker’s Bio: Dr. Chowdhury is a Postdoctoral Research Associate in the Computer Science and Mathematics Division of Oak Ridge National Laboratory.  He obtained his PhD in Statistics from Purdue University in 2021.  Previously, he obtained a master’s degree in statistics from the Indian Institute of Technology Kanpur in 2011 and a bachelor’s degree in statistics from the University of Calcutta in 2009.  His research revolves around developing fast and efficient randomized algorithms for various large-scale statistical, as well as more general linear algebraic problems.  Using the tools from randomized numerical linear algebra and subspace embedding, his goal is to come up with provably accurate and fast solutions to those problems which are computationally challenging.  Dr. Chowdhury is also interested in various aspects of statistical machine learning including dimensionality reduction and feature selection in high dimensional data.  Before joining Purdue as a PhD student, Agniva spent a few years in the data science and analytics industry.