Minimax problems have recently attracted a lot of research interests. A few efforts have been made to solve decentralized nonconvex strongly-concave (NCSC) minimax-structured optimization; however, all of them focus on smooth problems with at most a constraint on the maximization variable. In this paper, we make the first attempt on solving composite NCSC minimax problems that can have convex nonsmooth terms on both minimization and maximization variables. Our algorithm is designed based on a novel reformulation of the decentralized minimax problem that introduces a multiplier to absorb the dual consensus constraint. The removal of dual consensus constraint enables the most aggressive (i.e., local maximization instead of a gradient ascent step) dual update that leads to the benefit of taking a larger primal stepsize and better complexity results. In addition, the decoupling of the nonsmoothness and consensus on the dual variable eases the analysis of a decentralized algorithm; thus our reformulation creates a new way for interested researchers to design new (and possibly more efficient) decentralized methods on solving NCSC minimax problems. We show a global convergence result of the proposed algorithm and an iteration complexity result to produce a (near) stationary point of the reformulation. Moreover, a relation is established between the (near) stationarities of the reformulation and the original formulation. With this relation, we show that when the dual regularizer is smooth, our algorithm can have lower complexity results (with reduced dependence on a condition number) than existing ones to produce a near-stationary point of the original formulation. Numerical experiments are conducted on a distributionally robust logistic regression to demonstrate the performance of the proposed algorithm.
翻译:极小极大问题引起了近期的广泛研究。已经有一些研究致力于解决分布式非凸强凹(NCSC)极小极大优化问题,然而它们都只关注极大化变量上的约束条件最多是光滑问题。本文中,我们首次尝试解决具有凸不光滑项的复合型NCSC极小极大问题,这些项分别分布在最小化和最大化变量上。我们的算法基于分布式极小极大问题的一种新形式,它引入了一个乘子去吸收双重共识约束。去除双重共识约束允许最激进(即本地化极大化而不是梯度上升步骤)的双重更新,从而带来更大的原始步长和更好的复杂度结果。此外,去除了双重变量上的不光滑和共识的耦合,使分布式算法的分析更容易。因此,我们的新形式为有兴趣的研究人员提供了一个设计解决NCSC极小极大问题的新方法(可能更有效)。我们证明了所提出算法的全局收敛性以及产生一个(接近)稳定点的迭代复杂度结果。此外,建立了一种关于原形式和新形式之间(接近)稳定性点的关系。我们还指出,当双重正则化程序为光滑时,算法的复杂度结果会更低(减少了对条件数的依赖),从而产生原形式的(接近)稳定点。我们在分布式鲁莽逻辑回归上进行了数值实验以展示所提出算法的性能。