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(n2lognM· EO + n3logO(1)nM) time and O(n3log2n· EO +n4logO(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 Ω(n2) 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(nM3logn· EO) 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 Õ(n5/3· EO/ε2) time returns an ε-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 n2 bound - we show that algorithms which access only subgradients of the Lovasz extension, and these include the empirically fast Fujishige-Wolfe heuristic [Fujishige, 1980; Wolfe, 1976]