Minimisation of Submodular Functions Using Gaussian Zeroth-Order Random Oracles
This work addresses optimization challenges in machine learning and operations research, offering incremental improvements in algorithm design for submodular function minimization.
The paper tackles the problem of minimizing submodular functions by applying a zeroth-order method using Gaussian smoothing to estimate gradients, proving convergence to an ε-approximate solution offline and achieving Hannan-consistency with O(√(NP_N*)) dynamic regret online.
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(\sqrt{NP_N^\ast})$ dynamic regret, where $N$ is the number of iterations and $P_N^\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.