An Approximate, Efficient LP Solver for LP Rounding
By Srikrishna Sridhar, Stephen J. Wright, Christopher R'e, Ji Liu, Victor Bittorf, Ce Zhang. 2013
25 citations recorded by the source corpus.
Many problems in machine learning can be solved by rounding the solution of an appropriate linear program (LP). This paper shows that we can recover solutions of comparable quality by rounding an approximate LP solution instead of the exact one. These approximate LP solutions can be computed efficiently by applying a parallel stochastic-coordinate-descent method to a quadratic-penalty formulation of the LP. We derive worst-case runtime and solution quality guarantees of this scheme using novel perturbation and convergence analysis. Our experiments demonstrate that on such combinatorial problems as vertex cover, independent set and multiway-cut, our approximate rounding scheme is up to an order of magnitude faster than Cplex (a commercial LP solver) while producing solutions of similar quality.
Subfields: Artificial Intelligence, Computational Theory and Mathematics, Computer Networks and Communications
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
In Computational Theory and Mathematics
In Computer Networks and Communications
Citations in the corpus
- Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization (2015, methodology): “…2011, Zhang et al., 2014, Feyzmahdavian et al., 2015, Paine et al., 2013, Mania et al., 2015], stochastic coordinate descent [Avron et al., 2014, Liu et al., 2014a, Sridhar et al., 2013], dual stochastic coordinate ascent [Tran et al., 2015], and randomized Kaczmarz algorithm [Liu et al., 2014b].”
- A Comprehensive Linear Speedup Analysis for Asynchronous Stochastic Parallel Optimization from Zeroth-Order to First-Order (2016, methodology): “This paper provides a comprehensive and generic analysis to study the speedup property for a broad range of asynchronous parallel stochastic algorithms from the zeroth order to the first order methods.”
- Asynchronous Stochastic Coordinate Descent: Parallelism and Convergence Properties (2014, unknown): “Recently, parallel multicore versions of stochastic gradient and stochastic coordinate descent have been described for problems involving large data sets; see for example [30, 33, 3, 20, 37, 21].”