{"ID":2853852,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.15257","arxiv_id":"2510.15257","title":"Minimisation of Submodular Functions Using Gaussian Zeroth-Order Random Oracles","abstract":"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.","short_abstract":"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 so...","url_abs":"https://arxiv.org/abs/2510.15257","url_pdf":"https://arxiv.org/pdf/2510.15257v1","authors":"[\"Amir Ali Farzin\",\"Yuen-Man Pun\",\"Philipp Braun\",\"Tyler Summers\",\"Iman Shames\"]","published":"2025-10-17T02:36:46Z","proceeding":"math.OC","tasks":"[\"math.OC\",\"cs.LG\",\"math.NA\"]","methods":"[]","has_code":false}