Subquadratic submodular function minimization

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, 2015] run in O ( n 2 log nM · EO + n 3 log O (1) nM ) time and O ( n 3 log 2 n · EO + n 4 log O (1) n )time respectively, where M is the largest absolute value of the function (assuming the range is integers) and is the time taken to evaluate the function on any set. Although the best known lower bound on the query complexity is only Ω( n ) [Harvey, 2008], the current shortest non-deterministic proof [Cunningham, 1985] certifying the optimum value of a function requires Ω(n 2 ) function evaluations.

Authors

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

Keywords

• Submodular Functions
• Lovasz Extension
• Subgradient Descent