# Stochastic Primal-Dual Algorithms with Faster Convergence than O(1/√T) for Problems without Bilinear Structure

arXiv: https://arxiv.org/abs/1904.10112 · HTML: https://mlsanity.com/paper/1904.10112/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Apr 2019.

## Built on by (most cited first, 15 of 15)

- [AUC Maximization in the Era of Big Data and AI: A Survey](https://mlsanity.com/paper/2203.15046/) (2022)
- [Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results and Construction](https://mlsanity.com/paper/2103.08280/) (2021)
- [Near Optimal Stochastic Algorithms for Finite-Sum Unbalanced Convex-Concave Minimax Optimization](https://mlsanity.com/paper/2106.01761/) (2021)
- [Stochastic Constrained DRO with a Complexity Independent of Sample Size](https://mlsanity.com/paper/2210.05740/) (2022)
- [Zero-Regret Performative Prediction Under Inequality Constraints](https://mlsanity.com/paper/2309.12618/) (2023)
- [An Efficient Stochastic Algorithm for Decentralized Nonconvex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2212.02387/) (2022)
- [Decentralized gradient descent maximization method for composite nonconvex strongly-concave minimax problems](https://mlsanity.com/paper/2304.02441/) (2023)
- [Learning Distributionally Robust Models at Scale via Composite Optimization](https://mlsanity.com/paper/2203.09607/) (2022)
- [Stochastic Compositional Optimization with Compositional Constraints](https://mlsanity.com/paper/2209.04086/) (2022)
- [Decentralized Stochastic Variance Reduced Extragradient Method](https://mlsanity.com/paper/2202.00509/) (2022)
- [Accelerated Stochastic Min-Max Optimization Based on Bias-corrected Momentum](https://mlsanity.com/paper/2406.13041/) (2024)
- [Stochastic Gradient Methods with Compressed Communication for Decentralized Saddle Point Problems](https://mlsanity.com/paper/2205.14452/) (2022)
- [FedDRO: Federated Compositional Optimization for Distributionally Robust Learning](https://mlsanity.com/paper/2311.12652/) (2023)
- [Switch and Conquer: Efficient Algorithms By Switching Stochastic Gradient Oracles For Decentralized Saddle Point Problems](https://mlsanity.com/paper/2309.00997/) (2023)
- [SOREL: A Stochastic Algorithm for Spectral Risks Minimization](https://mlsanity.com/paper/2407.14618/) (2024)

## Abstract (arXiv)

Previous studies on stochastic primal-dual algorithms for solving min-max problems with faster convergence heavily rely on the bilinear structure of the problem, which restricts their applicability to a narrowed range of problems. The main contribution of this paper is the design and analysis of new stochastic primal-dual algorithms that use a mixture of stochastic gradient updates and a logarithmic number of deterministic dual updates for solving a family of convex-concave problems with no bilinear structure assumed. Faster convergence rates than O(1/√T) with T being the number of stochastic gradient updates are established under some mild conditions of involved functions on the primal and the dual variable. For example, for a family of problems that enjoy a weak strong convexity in terms of the primal variable and has a strongly concave function of the dual variable, the convergence rate of the proposed algorithm is O(1/T). We also investigate the effectiveness of the proposed algorithms for learning robust models and empirical AUC maximization.