arXiv：cs.LG· Gabriel Mancino-Ball, Muhammad Khan, Yangyang Xu·· 5 小时前AI 评分25
VRLM：面向去中心化随机双正则非凸强凹极小极大问题的方差缩减加速方法
Variance-reduced accelerated methods for decentralized stochastic double-regularized nonconvex strongly-concave minimax problems
AI 导读
研究者提出 VRLM，一种用于去中心化随机非凸强凹（NCSC）极小极大问题的方差缩减算法，可同时处理施加于原始与对偶变量的凸非光滑正则项。在一般随机设定下，VRLM 每次迭代仅需一次邻居通信，即可达到 O(κ³ε⁻³) 样本复杂度；配合 big-batch 方差缩减还可实现 O(κ²ε⁻²) 通信复杂度。
正文
Abstract:In this paper, we consider the decentralized, stochastic nonconvex strongly-concave (NCSC) minimax problem with nonsmooth regularization terms on both primal and dual variables, wherein a network of $m$ computing agents collaborate via peer-to-peer communications. We consider when the coupling function is in expectation or finite-sum form and the double regularizers are convex functions, applied separately to the primal and dual variables. Our algorithmic framework introduces a Lagrangian multiplier to eliminate the consensus constraint on the dual variable. Coupling this with variance-reduction (VR) techniques, our proposed method, entitled VRLM, by a single neighbor communication per iteration, is able to achieve an $\mathcal{O}(\kappa^3\varepsilon^{-3})$ sample complexity under the general stochastic setting, with either a big-batch or small-batch VR option, where $\kappa$ is the condition number of the problem and $\varepsilon$ is the desired solution accuracy. With a big-batch VR, we can additionally achieve $\mathcal{O}(\kappa^2\varepsilon^{-2})$ communication complexity. Under the special finite-sum setting, our method with a big-batch VR can achieve an $\mathcal{O}(n + \sqrt{n} \kappa^2\varepsilon^{-2})$ sample complexity and $\mathcal{O}(\kappa^2\varepsilon^{-2})$ communication complexity, where $n$ is the number of components in the finite sum. All complexity results match the best-known results achieved by a few existing methods for solving special cases of the problem we consider. To the best of our knowledge, this is the first work which provides convergence guarantees for NCSC minimax problems with general convex nonsmooth regularizers applied to both the primal and dual variables in the decentralized stochastic setting. Numerical experiments are conducted on two machine learning problems. Our code is downloadable from this https URL.
| Comments: | Updated to include second author Muhammad Khan who contributed during the rebuttal phase of the submission |
| Subjects: | Optimization and Control (math.OC); Machine Learning (cs.LG) |
| Cite as: | arXiv:2307.07113 [math.OC] |
| (or arXiv:2307.07113v2 [math.OC] for this version) | |
| https://doi.org/10.48550/arXiv.2307.07113 arXiv-issued DOI via DataCite |
Submission history
From: Gabriel Mancino-Ball [view email]
[v1]
Fri, 14 Jul 2023 01:32:16 UTC (4,960 KB)
[v2]
Fri, 2 Oct 2026 13:35:53 UTC (5,762 KB)
来源：arXiv：cs.LG · arxiv.org