# Minimisation of Submodular Functions Using Gaussian Zeroth-Order Random Oracles

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 26 references that are in the map.
- First posted on arXiv 17 Oct 2025.

## Builds on (most cited first, 9 of 9)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Reflection methods for user-friendly submodular optimization](https://mlsanity.com/paper/1311.4296/) (2013)
- [Near-optimal Approximate Discrete and Continuous Submodular Function Minimization](https://mlsanity.com/paper/1909.00171/) (2019)
- [Provable Submodular Minimization using Wolfe's Algorithm](https://mlsanity.com/paper/1411.0095/) (2014)
- [Subquadratic Submodular Function Minimization](https://mlsanity.com/paper/1610.09800/) (2016)
- [Min-Max Optimisation for Nonconvex-Nonconcave Functions Using a Random Zeroth-Order Extragradient Algorithm](https://mlsanity.com/paper/2504.07388/) (2025)
- [Minimisation of Polyak-Lojasewicz Functions Using Random Zeroth-Order Oracles](https://mlsanity.com/paper/2405.09106/) (2024)
- [Minimisation of Quasar-Convex Functions Using Random Zeroth-Order Oracles](https://mlsanity.com/paper/2505.02281/) (2025)
- [Quantum and Classical Algorithms for Approximate Submodular Function Minimization](https://mlsanity.com/paper/1907.05378/) (2019)

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

- [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)
- [From Cursed to Competitive: Closing the ZO-FO Gap via Input-to-State Stability](https://mlsanity.com/paper/2604.25372/) (2026)

## Abstract (arXiv)

We consider the minimisation problem of submodular functions and investigate the application of a zeroth-order method to this problem. The method is based on exploiting a Gaussian smoothing random oracle to estimate the smoothed function gradient. We prove the convergence of the algorithm to a global ε-approximate solution in the offline case and show that the algorithm is Hannan-consistent in the online case with respect to static regret. Moreover, we show that the algorithm achieves O(√NPN^ast) dynamic regret, where N is the number of iterations and PN^ast is the path length. The complexity analysis and hyperparameter selection are presented for all the cases. The theoretical results are illustrated via numerical examples.