# Optimal approximation for unconstrained non-submodular minimization

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

## Key facts

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

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

- [Training Data Subset Selection for Regression with Controlled Generalization Error](https://mlsanity.com/paper/2106.12491/) (2021)
- [Neural Set Function Extensions: Learning with Discrete Functions in High Dimensions](https://mlsanity.com/paper/2208.04055/) (2022)
- [Bayesian Strategic Classification](https://mlsanity.com/paper/2402.08758/) (2024)
- [Neural Estimation of Submodular Functions with Applications to Differentiable Subset Selection](https://mlsanity.com/paper/2210.11033/) (2022)
- [Automatic feature selection and weighting in molecular systems using Differentiable Information Imbalance](https://mlsanity.com/paper/2411.00851/) (2024)
- [Difference of Submodular Minimization via DC Programming](https://mlsanity.com/paper/2305.11046/) (2023)
- [Joint Continuous and Discrete Model Selection via Submodularity](https://mlsanity.com/paper/2102.09029/) (2021)
- [Online Nonsubmodular Minimization with Delayed Costs: From Full Information to Bandit Feedback](https://mlsanity.com/paper/2205.07217/) (2022)
- [Online Nonsubmodular Optimization with Delayed Feedback in the Bandit Setting](https://mlsanity.com/paper/2508.00523/) (2025)
- [Online Subset Selection using α-Core with no Augmented Regret](https://mlsanity.com/paper/2209.14222/) (2022)
- [Supermodular Rank: Set Function Decomposition and Optimization](https://mlsanity.com/paper/2305.14632/) (2023)

## Abstract (arXiv)

Submodular function minimization is well studied, and existing algorithms solve it exactly or up to arbitrary accuracy. However, in many applications, such as structured sparse learning or batch Bayesian optimization, the objective function is not exactly submodular, but close. In this case, no theoretical guarantees exist. Indeed, submodular minimization algorithms rely on intricate connections between submodularity and convexity. We show how these relations can be extended to obtain approximation guarantees for minimizing non-submodular functions, characterized by how close the function is to submodular. We also extend this result to noisy function evaluations. Our approximation results are the first for minimizing non-submodular functions, and are optimal, as established by our matching lower bound.