arXiv：cs.LG· Amir Ali Farzin, Yuen-Man Pun, Philipp Braun, Tyler Summers, Iman Shames·· 3 小时前
非光滑子模-凹函数的离线与在线 Min-Max 问题：一种零阶方法
Solving the Offline and Online Min-Max Problem of Non-smooth Submodular-Concave Functions: A Zeroth-Order Approach
AI 导读
针对对最小化方非光滑子模、对最大化方凹的 max-min / min-max 问题，该研究采用基于 Lovász 扩展次梯度与高斯平滑的零阶方法求解。理论上证明离线情形期望收敛到 ε-鞍点，在线情形达到 O(√(N(1+P̄_N))) 的对偶间隙，并给出复杂度分析与超参数选择，结果以数值实验验证。
正文
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 $\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.
| Subjects: | Optimization and Control (math.OC); Machine Learning (cs.LG); Numerical Analysis (math.NA) |
| Cite as: | arXiv:2601.21243 [math.OC] |
| (or arXiv:2601.21243v5 [math.OC] for this version) | |
| https://doi.org/10.48550/arXiv.2601.21243 arXiv-issued DOI via DataCite |
Submission history
From: Amir Ali Farzin Mr. [view email]
[v1]
Thu, 29 Jan 2026 04:04:27 UTC (1,061 KB)
[v2]
Thu, 28 May 2026 02:06:41 UTC (1,062 KB)
[v3]
Sun, 19 Jul 2026 23:47:03 UTC (1,065 KB)
[v4]
Mon, 7 Sep 2026 00:08:04 UTC (1,065 KB)
[v5]
Thu, 8 Oct 2026 03:15:26 UTC (1,065 KB)
来源：arXiv：cs.LG · arxiv.org