提出零阶方法求解非光滑子模-凹函数的极小极大问题
Solving the Offline and Online Min-Max Problem of Non-smooth Submodular-Concave Functions: A Zeroth-Order Approach
- 基于洛瓦兹扩展子梯度与高斯平滑估计梯度
- 离线收敛至ε-鞍点，在线情形达O(√(N(1+P̄_N)))对偶间隙
- 适用于优化决策路径变化不大的在线场景
我们研究目标函数可能非光滑、在最小化变量上为子模、在最大化变量上为凹函数的极大极小与极小极大问题。针对此类问题，提出一种零阶方法：对最小化变量使用洛瓦兹扩展的子梯度，对最大化变量采用高斯平滑来估计梯度。在期望意义下，证明了该算法在离线情况下可收敛至ε-鞍点。此外，在在线设定中，算法在期望意义下实现O(√(N(1+P̄_N)))的在线对偶间隙，其中N为迭代次数，P̄_N为最优决策序列的路径长度。文中给出了所有情形下的复杂度分析与超参数选择方法，并通过数值实验验证了理论结果。
原文摘要 · Abstract (English)
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(\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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。