FastDOG: Fast Discrete Optimization on GPU

• URL: http://arxiv.org/abs/2111.10270v1
• Date: Fri, 19 Nov 2021 15:20:10 GMT
• Title: FastDOG: Fast Discrete Optimization on GPU
• Authors: Ahmed Abbas, Paul Swoboda
• Abstract summary: We present a massively parallel Lagrange decomposition method for solving 0-1 integer linear programs occurring in structured prediction. Our primal and dual algorithms require little synchronization between subproblems and optimization over BDDs. We come close to or outperform some state-of-the-art specialized algorithms while being problem agnostic.
• Score: 23.281726932718232
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present a massively parallel Lagrange decomposition method for solving 0-1 integer linear programs occurring in structured prediction. We propose a new iterative update scheme for solving the Lagrangean dual and a perturbation technique for decoding primal solutions. For representing subproblems we follow Lange et al. (2021) and use binary decision diagrams (BDDs). Our primal and dual algorithms require little synchronization between subproblems and optimization over BDDs needs only elementary operations without complicated control flow. This allows us to exploit the parallelism offered by GPUs for all components of our method. We present experimental results on combinatorial problems from MAP inference for Markov Random Fields, quadratic assignment and cell tracking for developmental biology. Our highly parallel GPU implementation improves upon the running times of the algorithms from Lange et al. (2021) by up to an order of magnitude. In particular, we come close to or outperform some state-of-the-art specialized heuristics while being problem agnostic.

Related papers

• GreedyML: A Parallel Algorithm for Maximizing Submodular Functions [2.9998889086656586]
  We describe a parallel approximation algorithm for maximizing monotone submodular functions on distributed memory multiprocessors. Our work is motivated by the need to solve submodular optimization problems on massive data sets, for practical applications in areas such as data summarization, machine learning, and graph sparsification.
  arXiv  Detail & Related papers  (2024-03-15T14:19:09Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  A current standard approach to solving convex discrete optimization problems is the use of cutting-plane algorithms. Despite the existence of a number of general-purpose cut-generating algorithms, large-scale discrete optimization problems continue to suffer from intractability. We propose a method for accelerating cutting-plane algorithms via reinforcement learning.
  arXiv  Detail & Related papers  (2023-07-17T20:11:56Z)
• Second-order optimization with lazy Hessians [55.51077907483634]
  We analyze Newton's lazy Hessian updates for solving general possibly non-linear optimization problems. We reuse a previously seen Hessian iteration while computing new gradients at each step of the method.
  arXiv  Detail & Related papers  (2022-12-01T18:58:26Z)
• On a class of geodesically convex optimization problems solved via Euclidean MM methods [50.428784381385164]
  We show how a difference of Euclidean convexization functions can be written as a difference of different types of problems in statistics and machine learning. Ultimately, we helps the broader broader the broader the broader the broader the work.
  arXiv  Detail & Related papers  (2022-06-22T23:57:40Z)
• DOGE-Train: Discrete Optimization on GPU with End-to-end Training [28.795080637690095]
  We present a fast, scalable, data-driven approach for solving relaxations of 0-1 integer linear programs. We use a combination of graph neural networks (GNN) and the Lagrange decomposition based algorithm FastDOG.
  arXiv  Detail & Related papers  (2022-05-23T21:09:41Z)
• RAMA: A Rapid Multicut Algorithm on GPU [23.281726932718232]
  We propose a highly parallel primal-dual algorithm for the multicut (a.k.a.magnitude correlation clustering) problem. Our algorithm produces primal solutions and dual lower bounds that estimate the distance to optimum. We can solve very large scale benchmark problems with up to $mathcalO(108)$ variables in a few seconds with small primal-dual gaps.
  arXiv  Detail & Related papers  (2021-09-04T10:33:59Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  Bilevel optimization has been widely applied in many important machine learning applications. We propose two new algorithms for bilevel optimization. We show that both algorithms achieve the complexity of $mathcalO(epsilon-1.5)$, which outperforms all existing algorithms by the order of magnitude.
  arXiv  Detail & Related papers  (2021-06-08T21:05:30Z)
• Fast Parallel Algorithms for Euclidean Minimum Spanning Tree and Hierarchical Spatial Clustering [6.4805900740861]
  We introduce a new notion of well-separation to reduce the work and space of our algorithm for HDBSCAN$*$. We show that our algorithms are theoretically efficient: they have work (number of operations) matching their sequential counterparts, and polylogarithmic depth (parallel time) Our experiments on large real-world and synthetic data sets using a 48-core machine show that our fastest algorithms outperform the best serial algorithms for the problems by 11.13--55.89x, and existing parallel algorithms by at least an order of magnitude.
  arXiv  Detail & Related papers  (2021-04-02T16:05:00Z)
• Kernel methods through the roof: handling billions of points efficiently [94.31450736250918]
  Kernel methods provide an elegant and principled approach to nonparametric learning, but so far could hardly be used in large scale problems. Recent advances have shown the benefits of a number of algorithmic ideas, for example combining optimization, numerical linear algebra and random projections. Here, we push these efforts further to develop and test a solver that takes full advantage of GPU hardware.
  arXiv  Detail & Related papers  (2020-06-18T08:16:25Z)
• MPLP++: Fast, Parallel Dual Block-Coordinate Ascent for Dense Graphical Models [96.1052289276254]
  This work introduces a new MAP-solver, based on the popular Dual Block-Coordinate Ascent principle. Surprisingly, by making a small change to the low-performing solver, we derive the new solver MPLP++ that significantly outperforms all existing solvers by a large margin.
  arXiv  Detail & Related papers  (2020-04-16T16:20:53Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.