Oblivious Sketching-based Central Path Method for Linear Programming

In this work, we propose a sketching-based central path method for solving linear programmings, whose running time matches the state of the art results (Cohen et al., 2019b; Lee et al., 2019) . Our method opens up the iterations of the central path method and deploys an "iterate and sketch" approach towards the problem by introducing a new coordinate-wise embedding technique, which may be of independent interest. Compare to previous methods, the work (Cohen et al., 2019b) enjoys feasibility while being non-oblivious, and (Lee et al., 2019) is oblivious but infeasible, and relies on dense sketching matrices such as subsampled randomized Hadamard/Fourier transform matrices. Our method enjoys the benefits of being both oblivious and feasible, and can use sparse sketching matrix (Nelson & Nguyên, 2013) to speed up the online matrix-vector multiplication. Our framework for solving LP naturally generalizes to a broader class of convex optimization problems including empirical risk minimization.