Poster

Oblivious Sketching-based Central Path Method for Linear Programming

Zhao Song · Zheng Yu

Keywords: [ Gaussian Processes ] [ Sparsity and Compressed Sensing ] [ Algorithms ] [ Bayesian Theory ]

[ Abstract ]
[ Paper ]
[ Visit Poster at Spot B4 in Virtual World ]
Tue 20 Jul 9 p.m. PDT — 11 p.m. PDT
 
Spotlight presentation: Optimization 4
Tue 20 Jul 7 p.m. PDT — 8 p.m. PDT

Abstract: 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, Lee, Song STOC 19; Lee, Song, Zhang COLT 19]. 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, Lee, Song STOC 19] enjoys feasibility while being non-oblivious, and [Lee, Song, Zhang COLT 19] is oblivious but infeasible, and relies on $\mathit{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 $\mathit{sparse}$ sketching matrix [Nelson, Nguyen FOCS 13] 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.

Chat is not available.