Boţ Radu Ioan, Csetnek Ernö Robert, Sedlmayer Michael
Faculty of Mathematics, University of Vienna, Vienna, Austria.
Research Network Data Science @ Uni Vienna, University of Vienna, Vienna, Austria.
Comput Optim Appl. 2023;86(3):925-966. doi: 10.1007/s10589-022-00378-8. Epub 2022 Jun 4.
In this work we aim to solve a convex-concave saddle point problem, where the convex-concave coupling function is smooth in one variable and nonsmooth in the other and assumed to be linear in either. The problem is augmented by a nonsmooth regulariser in the smooth component. We propose and investigate a novel algorithm under the name of , consisting of an step in the smooth variable coupled with a proximal step of the regulariser, and which is alternated with a in the nonsmooth component of the coupling function. We consider the situations convex-concave, convex-strongly concave and strongly convex-strongly concave related to the saddle point problem under investigation. Regarding iterates we obtain (weak) convergence, a convergence rate of order and linear convergence like with , respectively. In terms of function values we obtain ergodic convergence rates of order , and with , respectively. We validate our theoretical considerations on a nonsmooth-linear saddle point problem, the training of multi kernel support vector machines and a classification problem incorporating minimax group fairness.
在这项工作中，我们旨在解决一个凸-凹鞍点问题，其中凸-凹耦合函数在一个变量中是光滑的，在另一个变量中是非光滑的，并且假设在两者中都是线性的。该问题通过在光滑分量中添加一个非光滑正则化项来增强。我们提出并研究了一种名为 的新算法，它由光滑变量中的 步与正则化项的近端步相结合组成，并与耦合函数非光滑分量中的 交替进行。我们考虑了与所研究的鞍点问题相关的凸-凹、凸-强凹和强凸-强凹情况。关于迭代，我们分别得到了（弱）收敛、阶为 的收敛速率以及形如 且 的线性收敛。就函数值而言，我们分别得到了阶为 、 和 的遍历收敛速率。我们在一个非光滑-线性鞍点问题、多核支持向量机的训练以及一个包含极小极大群体公平性的分类问题上验证了我们的理论考量。
