Near-optimal Approximate Discrete and Continuous Submodular Function Minimization

2019/08/31 by Axelrod, Brian, Liu, Yang P., Sidford, Aaron · 3 citations
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.1909.00171

Abstract

In this paper we provide improved running times and oracle complexities for approximately minimizing a submodular function. Our main result is a randomized algorithm, which given any submodular function defined on n-elements with range [-1, 1], computes an ε-additive approximate minimizer in O(n/ε²) oracle evaluations with high probability. This improves over the O(n^5/3/ε²) oracle evaluation algorithm of Chakrabarty \etal~(STOC 2017) and the O(n^3/2/ε²) oracle evaluation algorithm of Hamoudi \etal. Further, we leverage a generalization of this result to obtain efficient algorithms for minimizing a broad class of nonconvex functions. For any function f with domain [0, 1]ⁿ that satisfies (∂²f)/(∂ x_i ∂ x_j) ≤ 0 for all i ≠ j and is L-Lipschitz with respect to the L^∞-norm we give an algorithm that computes an ε-additive approximate minimizer with O(n ⋅ poly(L/ε)) function evaluation with high probability.

Cited by

• Minimum s--t Cuts with Fewer Cut Queries
• Minimisation of Submodular Functions Using Gaussian Zeroth-Order Random Oracles
• Discrete and Continuous Difference of Submodular Minimization

Related

• A brief note on approximate optimization of submodular functions
• Improved randomized algorithm for k-submodular function maximization
• Maximizing Non-Monotone Submodular Functions over Small Subsets: Beyond 1/2-Approximation
• Regularized Non-monotone Submodular Maximization
• Submodular Functions: Extensions, Distributions, and Algorithms. A Survey