An Approximate, Efficient LP Solver for LP Rounding

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.

• Publication year

  2013

• Venue

  Neural Information Processing Systems

• Publication date

  2013-11-11

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 1311.2661
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Approximation Algorithms

  2021cited by this paper
• An asynchronous parallel stochastic coordinate descent algorithm

  2013influential reference
• A Distributed Algorithm for Large-Scale Generalized Matching

  2013cited by this paper
• Towards high-throughput gibbs sampling at scale: a study across storage managers

  2013cited by this paper
• An Approximate, Efficient Solver for LP Rounding

  2013cited by this paper
• Solving Packing Integer Programs via Randomized Rounding with Alterations

  2012cited by this paper
• A practical relative error criterion for augmented Lagrangians

  2012cited by this paper
• Coupling detection and data association for multiple object tracking

  2012cited by this paper
• Hogwild: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent

  2011cited by this paper
• Web Scale Entity Resolution using Relational Evidence

  2011cited by this paper
• Message-passing for Graph-structured Linear Programs: Proximal Methods and Rounding Schemes

  2010influential reference
• Classification by Set Cover: The Prototype Vector Machine

  2009cited by this paper
• Global Optimization for Shape Fitting

  2007cited by this paper
• Correlation Clustering for Crosslingual Link Detection

  2007cited by this paper
• Linear programming analysis of loopy belief propagation for weighted matching

  2007cited by this paper
• Integer linear programming inference for conditional random fields

  2005cited by this paper
• Many hard examples in exact phase transitions

  2003cited by this paper
• Factor graphs and the Sum-Product Algorithm

  2002cited by this paper
• Approximation Algorithms

  2001cited by this paper
• Factor graphs and the sum-product algorithm

  2001cited by this paper
• An experimental comparison of min-cut/max- flow algorithms for energy minimization in vision

  2001cited by this paper
• Improved Approximation Guarantees for Packing and Covering Integer Programs

  1999cited by this paper
• An improved approximation algorithm for multiway cut

  1998cited by this paper
• Some perturbation theory for linear programming

  1994influential reference
• Implementing proximal point methods for linear programming

  1990cited by this paper
• Approximation Algorithms for the Set Covering and Vertex Cover Problems

  1982cited by this paper

• Fair Class-Incremental Learning using Sample Weighting

  2024cites this paper
• Improving timing analysis effectiveness for scenario-based specifications by combining SAT and LP techniques

  2022cites this paper
• Fast and Accurate Machine Learning on Distributed Systems and Supercomputers

  2020cites this paper
• SAT and LP Collaborative Bounded Timing Analysis of Scenario-Based Specifications

  2020cites this paper
• Towards an efficient penalty method for convex quadratic programming ∗

  2019cites this paper
• Towards an efficient augmented Lagrangian method for convex quadratic programming

  2019cites this paper
• A Parallelizable Acceleration Framework for Packing Linear Programs

  2017influential citation
• Asynchronous Decentralized Parallel Stochastic Gradient Descent

  2017cites this paper
• Creating Robust Relation Extract and Anomaly Detect via Probabilistic Logic-Based Reasoning and Learning

  2017cites this paper
• A Comprehensive Linear Speedup Analysis for Asynchronous Stochastic Parallel Optimization from Zeroth-Order to First-Order

  2016cites this paper
• Asynchronous Parallel Greedy Coordinate Descent

  2016cites this paper
• A new correlation clustering method for cancer mutation analysis

  2016cites this paper
• Motif clustering and overlapping clustering for social network analysis

  2016cites this paper
• Online Feature Selection: A Limited-Memory Substitution Algorithm and Its Asynchronous Parallel Variation

  2016cites this paper
• Research Statement Thesis Research

  2015cites this paper
• Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization

  2015cites this paper
• DimmWitted: A Study of Main-Memory Statistical Analytics

  2014cites this paper
• Links between Join Processing and Convex Geometry

  2014cites this paper
• Scalable optimization algorithms for recommender systems

  2014cites this paper
• Information Basis in Dynamic Robust Optimization

  year unknowncites this paper