Subquadratic submodular function minimization

DOI10.1145/3055399.3055419MaRDI QIDQ4978061zbMATH OpenOpenAlexFDO

Authors Deeparnab Chakrabarty, Yin Tat Lee, Aaron Sidford, Sam Chiu-wai Wong

Publication date 17 August 2017

Published in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1610.09800

zbMATH Keywords

Lovász extensionsubgradient descentsubmodular functions

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59) Abstract computational complexity for mathematical programming problems (90C60)

Abstract: Submodular function minimization (SFM) is a fundamental discrete optimization problem which generalizes many well known problems, has applications in various fields, and can be solved in polynomial time. Owing to applications in computer vision and machine learning, fast SFM algorithms are highly desirable. The current fastest algorithms [Lee, Sidford, Wong, FOCS 2015] run in $O(n^{2}lognMcdotextrmEO+n^{3}lo{g}^{O(1)}nM)$ time and $O(n^{3}lo{g}^{2}ncdotextrmEO+n^{4}lo{g}^{O(1)}n$) time respectively, where $M$ is the largest absolute value of the function (assuming the range is integers) and $extrmEO$ is the time taken to evaluate the function on any set. Although the best known lower bound on the query complexity is only $Omega(n)$, the current shortest non-deterministic proof certifying the optimum value of a function requires $Theta(n^2)$ function evaluations. The main contribution of this paper are subquadratic SFM algorithms. For integer-valued submodular functions, we give an SFM algorithm which runs in $O(n{M}^{3}logncdotextrmEO)$ time giving the first nearly linear time algorithm in any known regime. For real-valued submodular functions with range in $[-1,1]$, we give an algorithm which in $ildeO(n^{5/3}cdotextrmEO/varepsilo{n}^2)$ time returns an $varepsilon$-additive approximate solution. At the heart of it, our algorithms are projected stochastic subgradient descent methods on the Lovasz extension of submodular functions where we crucially exploit submodularity and data structures to obtain fast, i.e. sublinear time subgradient updates. . The latter is crucial for beating the $n^2$ bound as we show that algorithms which access only subgradients of the Lovasz extension, and these include the theoretically best algorithms mentioned above, must make $Omega(n)$ subgradient calls (even for functions whose range is $-1,0,1$).

Recommendations

• A Faster Strongly Polynomial Time Algorithm for Submodular Function Minimization
• A faster strongly polynomial time algorithm for submodular function minimization
• Improved algorithms for submodular function minimization and submodular flow
• Geometric rescaling algorithms for submodular function minimization
• Geometric rescaling algorithms for submodular function minimization

Cited in

(19)

• Robust budget allocation via continuous submodular functions
• Minimizing submodular functions on diamonds via generalized fractional matroid matchings
• A tight analysis of the submodular-supermodular procedure
• Submodular functions: from discrete to continuous domains
• Geometric rescaling algorithms for submodular function minimization
• Geometric rescaling algorithms for submodular function minimization
• Quadratic decomposable submodular function minimization: theory and practice
• Computing exact minimum cuts without knowing the graph
• Efficient minimization of higher order submodular functions using monotonic Boolean functions
• Submodularity in Conic Quadratic Mixed 0–1 Optimization
• New Query Lower Bounds for Submodular Function Minimization
• Walrasian equilibria from an optimization perspective: A guide to the literature
• Tractability of explaining classifier decisions
• Strong substitutes: structural properties, and a new algorithm for competitive equilibrium prices
• Shortest cycles with monotone submodular costs
• Polynomial algorithms to minimize 2/3-submodular functions
• Weakly polynomial-time algorithms to minimize 2/3-submodular functions
• A parametric approach for solving convex quadratic optimization with indicators over trees
• Submodular function minimization

This page was built for publication: Subquadratic submodular function minimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4978061)