Solving the Offline and Online Min-Max Problem of Non-smooth Submodular-Concave Functions: A Zeroth-Order Approach

We consider max-min and min-max problems with objective functions that are possibly non-smooth, submodular with respect to the minimiser and concave with respect to the maximiser. We investigate the performance of a zeroth-order method applied to this problem. The method is based on the subgradient of the Lovász extension of the objective function with respect to the minimiser and based on Gaussian smoothing to estimate the smoothed function gradient with respect to the maximiser. In expectation sense, we prove the convergence of the algorithm to an $\epsilon$-saddle point in the offline case. Moreover, we show that, in the expectation sense, in the online setting, the algorithm achieves $O(\sqrt{N(1+\bar{P}_N)})$ online duality gap, where $N$ is the number of iterations and $\bar{P}_N$ is the path length of the sequence of optimal decisions. The complexity analysis and hyperparameter selection are presented for all the cases. The theoretical results are illustrated via numerical examples.

Many real-world decision-making problems involve selecting the best option from a discrete set while simultaneously guarding against worst-case scenarios, for example, determining which pixels belong to an object in an image when some labels may be unreliable or adversarially corrupted. These problems are naturally formulated as min-max optimisation problems, where one player selects a subset and another chooses continuous parameters to make the task as difficult as possible. However, solving such problems is challenging because the discrete structure and potential non-smoothness of the objective prevent the use of standard gradient-based methods. We developed an algorithm that solves these mixed discrete-continuous min-max problems using only function evaluations, without requiring derivatives. The method combines combinatorial techniques for the discrete component with a randomised smoothing approach for the continuous component. We prove convergence guarantees for both fixed (offline) and time-varying (online) settings. In experiments on adversarial image segmentation, our method outperformed trained neural networks while requiring no pre-training, no large datasets, and requiring less memory. These properties make it promising for resource-constrained and safety-critical applications, such as autonomous systems that must make reliable decisions in real time without relying on pre-collected training data.