Revisiting Decomposable Submodular Function Minimization with Incidence Relations

2018-03-10 · NeurIPS 2018 12 · Pan Li, Olgica Milenkovic

We introduce a new approach to decomposable submodular function minimization (DSFM) that exploits incidence relations. Incidence relations describe which variables effectively influence the component functions, and when properly utilized, they allow for improving the convergence rates of DSFM solvers. Our main results include the precise parametrization of the DSFM problem based on incidence relations, the development of new scalable alternative projections and parallel coordinate descent methods and an accompanying rigorous analysis of their convergence rates.

📄 PDF Abstract BibTeX arXiv:1803.03851

Code (1)

lipan00123/DSFM-with-incidence-relations 공식 구현

Efficient Minimization of Decomposable Submodular Functions

2010-12-01 · NeurIPS 2010 12 · Peter Stobbe, Andreas Krause

Many combinatorial problems arising in machine learning can be reduced to the problem of minimizing a submodular function. Submodular functions are a natural discrete analog of convex functions, and can be minimized in s…

Quadratic Decomposable Submodular Function Minimization

2018-06-26 · NeurIPS 2018 12 · Pan Li, Niao He, Olgica Milenkovic

We introduce a new convex optimization problem, termed quadratic decomposable submodular function minimization. The problem is closely related to decomposable submodular function minimization and arises in many learning …

Decomposable Submodular Function Minimization: Discrete and Continuous

2017-03-06 · NeurIPS 2017 12 · Alina Ene, Huy L. Nguyen, László A. Végh

This paper investigates connections between discrete and continuous approaches for decomposable submodular function minimization. We provide improved running time estimates for the state-of-the-art continuous algorithms …

Quadratic Decomposable Submodular Function Minimization: Theory and Practice (Computation and Analysis of PageRank over Hypergraphs)

2019-02-26 · Pan Li, Niao He, Olgica Milenkovic

We introduce a new convex optimization problem, termed quadratic decomposable submodular function minimization (QDSFM), which allows to model a number of learning tasks on graphs and hypergraphs. The problem exhibits clo…

hypergraph partitioning

Decomposable Submodular Function Minimization via Maximum Flow

2021-03-05 · Kyriakos Axiotis, Adam Karczmarz, Anish Mukherjee, Piotr Sankowski 외

This paper bridges discrete and continuous optimization approaches for decomposable submodular function minimization, in both the standard and parametric settings. We provide improved running times for this problem by re…