Revisiting Decomposable Submodular Function Minimization with Incidence Relations

Pan Li; Olgica Milenkovic

NeurIPS 2018poster21 citations

Revisiting Decomposable Submodular Function Minimization with Incidence Relations

Abstract

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.

BibTeX

@inproceedings{NEURIPS2018_c21002f4,
 author = {Li, Pan and Milenkovic, Olgica},
 booktitle = {Advances in Neural Information Processing Systems},
 editor = {S. Bengio and H. Wallach and H. Larochelle and K. Grauman and N. Cesa-Bianchi and R. Garnett},
 pages = {},
 publisher = {Curran Associates, Inc.},
 title = {Revisiting Decomposable Submodular Function Minimization with Incidence Relations},
 url = {https://proceedings.neurips.cc/paper_files/paper/2018/file/c21002f464c5fc5bee3b98ced83963b8-Paper.pdf},
 volume = {31},
 year = {2018}
}