Minimisation of Submodular Functions Using Gaussian Zeroth-Order Random Oracles

• URL: http://arxiv.org/abs/2510.15257v1
• Date: Fri, 17 Oct 2025 02:36:46 GMT
• Title: Minimisation of Submodular Functions Using Gaussian Zeroth-Order Random Oracles
• Authors: Amir Ali Farzin, Yuen-Man Pun, Philipp Braun, Tyler Summers, Iman Shames,
• Abstract summary: We prove the convergence of the algorithm to a global $epsilon$-approximate solution in the offline case.<n>We show that the algorithm is Hannan-consistent in the online case with respect to static regret.
• Score: 1.220074067604011
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• 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 $\epsilon$-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.

Related papers

• Solving the Offline and Online Min-Max Problem of Non-smooth Submodular-Concave Functions: A Zeroth-Order Approach [1.220074067604011]
  We consider problems with objective functions that are possibly non-smooth, submodular with respect to the minimiser and concave with respect to the maximiser.<n>We investigate the performance of a zeroth-order method applied to this problem.
  arXiv  Detail & Related papers  (2026-01-29T04:04:27Z)
• Accelerated Stochastic Min-Max Optimization Based on Bias-corrected Momentum [30.01198677588252]
  First-order algorithms require at least $mathcalO(varepsilonepsilon-4)$ complexity to find an $varepsilon-stationary point.<n>We introduce novel momentum algorithms utilizing efficient variable complexity.<n>The effectiveness of the method is validated through robust logistic regression using real-world datasets.
  arXiv  Detail & Related papers  (2024-06-18T20:14:52Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss. Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
  arXiv  Detail & Related papers  (2023-07-24T14:37:22Z)
• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  We show that any efficient SQ algorithm for the problem requires sample complexity at least $Omega(d1/2/(maxp, epsilon)2)$. Our lower bound suggests that this quadratic dependence on $1/epsilon$ is inherent for efficient algorithms.
  arXiv  Detail & Related papers  (2023-07-13T18:59:28Z)
• Gradient-free optimization of highly smooth functions: improved analysis and a new algorithm [87.22224691317766]
  This work studies problems with zero-order noisy oracle information under the assumption that the objective function is highly smooth. We consider two kinds of zero-order projected gradient descent algorithms.
  arXiv  Detail & Related papers  (2023-06-03T17:05:13Z)
• Deterministic Nonsmooth Nonconvex Optimization [82.39694252205011]
  We show that randomization is necessary to obtain a dimension-free dimension-free algorithm.<n>Our algorithm yields the first deterministic dimension-free algorithm for optimizing ReLU networks.
  arXiv  Detail & Related papers  (2023-02-16T13:57:19Z)
• Derivative-free Alternating Projection Algorithms for General Nonconvex-Concave Minimax Problems [9.173866646584031]
  In this paper, we propose an algorithm for nonsmooth zeroth-order minimax problems. We show that it can be used to attack nonconcave minimax problems.
  arXiv  Detail & Related papers  (2021-08-01T15:23:49Z)
• Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence [120.9336529957224]
  In this paper, we denote the non-strongly setting on the magnitude of a gradient-free minimax optimization problem. We show that a novel zeroth-order variance reduced descent algorithm achieves the best known query complexity.
  arXiv  Detail & Related papers  (2020-06-16T17:55:46Z)
• Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits [99.70167985955352]
  We study the problem of zero-order optimization of a strongly convex function. We consider a randomized approximation of the projected gradient descent algorithm. Our results imply that the zero-order algorithm is nearly optimal in terms of sample complexity and the problem parameters.
  arXiv  Detail & Related papers  (2020-06-14T10:42:23Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.