Sparse Submodular Function Minimization

In this paper we study the problem of minimizing a submodular function $f: 2^{V} \rightarrow \mathbb{R}$ that is guaranteed to have a k-sparse minimizer. We give a deterministic algorithm that computes an additive $\epsilon$-approximate minimizer of such f in $\widetilde{O}(\operatorname{poly}(k) \log (|f| / \epsilon))$ parallel depth using a polynomial number of queries to an evaluation oracle of f, where $|f|=\max_{S \subseteq V}|f(S)|$. Further, we give a randomized algorithm that computes an exact minimizer of f with high probability using $\widetilde{O}(|V| \cdot \operatorname{poly}(k))$ queries and polynomial time. When $k=\widetilde{O}(1)$, our algorithms use either nearly-constant parallel depth or a nearly-linear number of evaluation oracle queries. All previous algorithms for this problem either use $\Omega(|V|)$ parallel depth or $\Omega\left(|V|^{2}\right)$ queries. In contrast to state-of-the-art weakly-polynomial and strongly-polynomial time algorithms for SFM, our algorithms use first-order optimization methods, e. g. , mirror descent and follow the regularized leader. We introduce what we call sparse dual certificates, which encode information on the structure of sparse minimizers, and both our parallel and sequential algorithms provide new algorithmic tools for allowing first-order optimization methods to efficiently compute them. Correspondingly, our algorithm does not invoke fast matrix multiplication or general linear system solvers and in this sense is more combinatorial than previous state-of-the-art methods.

Authors

• Andrei Graur
• Haotian Jiang
• Aaron Sidford

Keywords

• Linear systems
• Computer science
• Additives
• Optimization methods
• Minimization
• Complexity theory
• Sparse matrices
• Submodular Function
• Submodular Function Minimization
• High Probability
• Optimization Method
• Minimum Estimate
• Sequential Algorithm
• Parallel Algorithm
• First-order Method
• Lower Bound
• Optimization Problem
• Dimensionality Reduction
• Sparsity
• Set Of Elements
• Convex Optimization
• Constant Factor
• Line Of Work
• Convex Optimization Problem
• Polynomial-time Algorithm
• Combinatorial Optimization Problem
• Local Norms
• Cutting-plane
• Parallel Set
• Precedence Constraints
• Detailed Version
• Convex Optimization Methods
• Logarithmic Factor
• query complexity
• parallel complexity