# Near-optimal Approximate Discrete and Continuous Submodular Function Minimization

arXiv: https://arxiv.org/abs/1909.00171 · HTML: https://mlsanity.com/paper/1909.00171/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Aug 2019.

## Built on by (most cited first, 11 of 11)

- [Submodularity In Machine Learning and Artificial Intelligence](https://mlsanity.com/paper/2202.00132/) (2022)
- [Submodular Minimax Optimization: Finding Effective Sets](https://mlsanity.com/paper/2305.16903/) (2023)
- [Difference of Submodular Minimization via DC Programming](https://mlsanity.com/paper/2305.11046/) (2023)
- [A Whole New Ball Game: A Primal Accelerated Method for Matrix Games and Minimizing the Maximum of Smooth Functions](https://mlsanity.com/paper/2311.10886/) (2023)
- [Reusing Combinatorial Structure: Faster Iterative Projections over Submodular Base Polytopes](https://mlsanity.com/paper/2106.11943/) (2021)
- [Minimisation of Submodular Functions Using Gaussian Zeroth-Order Random Oracles](https://mlsanity.com/paper/2510.15257/) (2025)
- [Solving the Offline and Online Min-Max Problem of Non-smooth Submodular-Concave Functions: A Zeroth-Order Approach](https://mlsanity.com/paper/2601.21243/) (2026)
- [Logarithmic Regret for Unconstrained Submodular Maximization Stochastic Bandit](https://mlsanity.com/paper/2410.08578/) (2024)
- [Corporate Needs You to Find the Difference: Revisiting Submodular and Supermodular Ratio Optimization Problems](https://mlsanity.com/paper/2505.17443/) (2025)
- [Discrete and Continuous Difference of Submodular Minimization](https://mlsanity.com/paper/2506.07952/) (2025)
- [Avoiding Exponential Blow-Up in Distributive Lattice Submodular Minimization](https://mlsanity.com/paper/2606.14764/) (2026)

## Abstract (arXiv)

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 tildeO(n/ε2) oracle evaluations with high probability. This improves over the tildeO(n5/3/ε2) oracle evaluation algorithm of Chakrabarty etal~(STOC 2017) and the tildeO(n3/2/ε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]n that satisfies fracpartial2fpartial xi partial xj ≤ 0 for all i neq j and is L-Lipschitz with respect to the L^∞-norm we give an algorithm that computes an ε-additive approximate minimizer with tildeO(n · poly(L/ε)) function evaluation with high probability.