פתרון בעיות מינ-מקס/מקס-מינ של פונקציות חד-פעמיות וקונקבות: גישה ראשונה-סדר

תקציר מקורי באנגליתarXiv:2601.21243v5 Announce Type: replace-cross 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\'asz 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 g