math.OCJan 29, 2026

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

Authors: Amir Ali Farzin, Yuen-Man Pun, Philipp Braun, Tyler Summers, Iman Shames

Organizations: School of Engineering, Australian National University, Canberra, Australia · Department of Mechanical Engineering, University of Texas at Dallas, Richardson, Texas, USA · Department of Electrical and Electronic Engineering, The University of Melbourne, Parkville, Australia

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

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 εε-saddle point in the offline case. Moreover, we show that, in the expectation sense, in the online setting, the algorithm achieves O(N(1+PˉN))O(\sqrt{N(1+\bar{P}_N)}) online duality gap, where NN is the number of iterations and PˉN\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.

Figures & tables

PropertyAlgorithm 1U-Net (supervised)U-Net (semi-supervised)
Model typeCustom ZO optimiserU-Net (CNN)U-Net (CNN)
Number of parameters∼\sim 2.52.5 k (Optimisation variables)∼\sim 1.06M (Net weights)∼\sim 1.06M (Net weights)
Training requirementNo pre-trainingSupervised on GTSemi-supervised on seeds
SupervisionSemi-supervisedSupervisedSemi-supervised
InputSeeds + imageImage onlySeeds + image
Adversarial robustnessYes (robust by design)No (standard CNN)No (standard CNN)
Table 1 : Comparison between the ZO online adversarial segmentation method and supervised and semi-supervised trained U-Net
Figure 1 : Offline Image Segmentation
Figure 2 : Online image segmentation under adversarial attack.
Appendix figures & tables10 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 3 : Offline Image Segmentation
Figure 4 : Lovász extension history over iterations for online image segmentation.
Figure 5 : Online image segmentation under adversarial attack using Algorithm 1 at different times.
Figure 6 : Online image segmentation at different times. Top row is predicted by the supervised U-Net and bottom row is predicted by the semi-supervised U-Net.
Figure 7 : Lovász extension history over the sequence generated by Algorithm 1 and the offline clustering for ρ=∞\rho=\infty and ρ=0\rho=0 .
Figure 8 : Lovász extension history over the sequence generated by Algorithm 1 and the offline clustering for ρ=2\rho=2 .
Figure 9 : Offline clustering accuracy versus the attacker’s budget.
Figure 10 : Lovász extension history over iterations for online clustering.
Figure 11 : Online clustering of the Two Moon dataset under adversarial attack using Algorithm 1 .
Figure 12 : Positions and labels over iterations - online robust clustering.

Explore similar work

CardsList

  1. Near-Optimal Single-Loop Predictor--Corrector Extragradient Method for Strongly Convex--Strongly Concave Minimax Optimization

    Sep 17, 2026Minhao Zhang, Zi XuLast-Iterate ConvergenceMin-Max Optimization

    Department of Mathematics, Shanghai University, Shanghai 200444, People’s Republic of China

  2. Zeroth-Order Nonconvex Nonsmooth Optimization with Heavy-Tailed Noise

    May 23, 2026Zhuanghua Liu, Luo LuoStochastic OptimizationGradient Clipping

  3. Lower Bounds for Stochastic First-Order Algorithms with Variance Reduction in Nonconvex--Concave Minimax Optimization

    Oct 1, 2026Jiayi Song, Zi XuMin-Max Optimization

    Department of Mathematics, College of Sciences, Shanghai University, Shanghai 200444, China