Minimisation of Submodular Functions Using Gaussian Zeroth-Order Random Oracles
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917021165289472 |
|---|---|
| author | Farzin, Amir Ali Pun, Yuen-Man Braun, Philipp Summers, Tyler Shames, Iman |
| author_facet | Farzin, Amir Ali Pun, Yuen-Man Braun, Philipp Summers, Tyler Shames, Iman |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_15257 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Minimisation of Submodular Functions Using Gaussian Zeroth-Order Random Oracles Farzin, Amir Ali Pun, Yuen-Man Braun, Philipp Summers, Tyler Shames, Iman Optimization and Control Machine Learning Numerical Analysis 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. |
| title | Minimisation of Submodular Functions Using Gaussian Zeroth-Order Random Oracles |
| topic | Optimization and Control Machine Learning Numerical Analysis |
| url | https://arxiv.org/abs/2510.15257 |