2025/10/17 by Amir Ali Farzin, Farzin, Amir Ali, Yuen-Man Pun +7
Computer Science · Decision Sciences · #Stochastic Gradient Optimization Techniques #Complexity and Algorithms in Graphs #Advanced Bandit Algorithms Research
paper · pdf · doi:10.48550/arxiv.2510.15257
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^∗)) dynamic regret, where N is the number of iterations and PN^∗ is the path length. The complexity analysis and hyperparameter selection are presented for all the cases. The theoretical results are illustrated via numerical examples.