Efficient Single-Loop Stochastic Algorithms for Nonconvex-Concave Minimax Optimization
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909838388232192 |
|---|---|
| author | Jiang, Xia Zhu, Linglingzhi Zheng, Taoli So, Anthony Man-Cho |
| author_facet | Jiang, Xia Zhu, Linglingzhi Zheng, Taoli So, Anthony Man-Cho |
| contents | Nonconvex-concave (NC-C) finite-sum minimax problems have wide applications in signal processing and machine learning tasks. Conventional stochastic gradient algorithms, which rely on uniform sampling for gradient estimation, often suffer from slow convergence rates and require bounded variance assumptions. While variance reduction techniques can significantly improve the convergence of stochastic algorithms, the inherent nonsmooth nature of NC-C problems makes it challenging to design effective variance reduction techniques. To address this challenge, we develop a novel probabilistic variance reduction scheme and propose a single-loop stochastic gradient algorithm called the probabilistic variance-reduced smoothed gradient descent-ascent (PVR-SGDA) algorithm. The proposed PVR-SGDA algorithm achieves an iteration complexity of $\mathcal{O}(ε^{-4})$, surpassing the best-known rates of stochastic algorithms for NC-C minimax problems and matching the performance of state-of-the-art deterministic algorithms. Furthermore, to completely eliminate the need for full gradient computation and reduce the gradient complexity, we explore another variance reduction technique with auxiliary gradient trackers and propose a smoothed gradient descent-ascent algorithm without full gradient calculation, called ZeroSARAH-SGDA, for NC-C problems. The ZeroSARAH-SGDA algorithm achieves a comparable iteration complexity to PVR-SGDA, while reducing the gradient oracle calls at each iteration. Finally, we demonstrate the effectiveness of the proposed two algorithms through numerical simulations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_05677 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Efficient Single-Loop Stochastic Algorithms for Nonconvex-Concave Minimax Optimization Jiang, Xia Zhu, Linglingzhi Zheng, Taoli So, Anthony Man-Cho Optimization and Control Nonconvex-concave (NC-C) finite-sum minimax problems have wide applications in signal processing and machine learning tasks. Conventional stochastic gradient algorithms, which rely on uniform sampling for gradient estimation, often suffer from slow convergence rates and require bounded variance assumptions. While variance reduction techniques can significantly improve the convergence of stochastic algorithms, the inherent nonsmooth nature of NC-C problems makes it challenging to design effective variance reduction techniques. To address this challenge, we develop a novel probabilistic variance reduction scheme and propose a single-loop stochastic gradient algorithm called the probabilistic variance-reduced smoothed gradient descent-ascent (PVR-SGDA) algorithm. The proposed PVR-SGDA algorithm achieves an iteration complexity of $\mathcal{O}(ε^{-4})$, surpassing the best-known rates of stochastic algorithms for NC-C minimax problems and matching the performance of state-of-the-art deterministic algorithms. Furthermore, to completely eliminate the need for full gradient computation and reduce the gradient complexity, we explore another variance reduction technique with auxiliary gradient trackers and propose a smoothed gradient descent-ascent algorithm without full gradient calculation, called ZeroSARAH-SGDA, for NC-C problems. The ZeroSARAH-SGDA algorithm achieves a comparable iteration complexity to PVR-SGDA, while reducing the gradient oracle calls at each iteration. Finally, we demonstrate the effectiveness of the proposed two algorithms through numerical simulations. |
| title | Efficient Single-Loop Stochastic Algorithms for Nonconvex-Concave Minimax Optimization |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2501.05677 |