# On Accelerated Methods for Saddle-Point Problems with Composite Structure

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Mar 2021.

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

- [Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient Methods](https://mlsanity.com/paper/2202.07262/) (2022)
- [Near Optimal Stochastic Algorithms for Finite-Sum Unbalanced Convex-Concave Minimax Optimization](https://mlsanity.com/paper/2106.01761/) (2021)
- [Optimal Algorithms for Decentralized Stochastic Variational Inequalities](https://mlsanity.com/paper/2202.02771/) (2022)
- [Optimal Gradient Sliding and its Application to Distributed Optimization Under Similarity](https://mlsanity.com/paper/2205.15136/) (2022)
- [Smooth Monotone Stochastic Variational Inequalities and Saddle Point Problems: A Survey](https://mlsanity.com/paper/2208.13592/) (2022)
- [Faster Stochastic Algorithms for Minimax Optimization under Polyak--Lojasiewicz Conditions](https://mlsanity.com/paper/2307.15868/) (2023)
- [A Survey of Decision Making in Adversarial Games](https://mlsanity.com/paper/2207.07971/) (2022)
- [Multiple Greedy Quasi-Newton Methods for Saddle Point Problems](https://mlsanity.com/paper/2408.00241/) (2024)
- [Primal-dual extrapolation methods for monotone inclusions under local Lipschitz continuity](https://mlsanity.com/paper/2206.00973/) (2022)
- [An accelerated first-order regularized momentum descent ascent algorithm for stochastic nonconvex-concave minimax problems](https://mlsanity.com/paper/2310.15448/) (2023)
- [Iterative Minimax Games with Coupled Linear Constraints](https://mlsanity.com/paper/2212.04672/) (2022)
- [Federated Composite Saddle Point Optimization](https://mlsanity.com/paper/2305.15643/) (2023)
- [Accelerated Methods with Complexity Separation Under Data Similarity for Federated Learning Problems](https://mlsanity.com/paper/2601.08614/) (2026)

## Abstract (arXiv)

We consider strongly-convex-strongly-concave saddle-point problems with general non-bilinear objective and different condition numbers with respect to the primal and the dual variables. First, we consider such problems with smooth composite terms, one of which having finite-sum structure. For this setting we propose a variance reduction algorithm with complexity estimates superior to the existing bounds in the literature. Second, we consider finite-sum saddle-point problems with composite terms and propose several algorithms depending on the properties of the composite terms. When the composite terms are smooth we obtain better complexity bounds than the ones in the literature, including the bounds of a recently proposed nearly-optimal algorithms which do not consider the composite structure of the problem. If the composite terms are prox-friendly, we propose a variance reduction algorithm that, on the one hand, is accelerated compared to existing variance reduction algorithms and, on the other hand, provides in the composite setting similar complexity bounds to the nearly-optimal algorithm which is designed for non-composite setting. Besides that, our algorithms allow to separate the complexity bounds, i.e. estimate, for each part of the objective separately, the number of oracle calls that is sufficient to achieve a given accuracy. This is important since different parts can have different arithmetic complexity of the oracle, and it is desired to call expensive oracles less often than cheap oracles. The key thing to all these results is our general framework for saddle-point problems, which may be of independent interest. This framework, in turn is based on our proposed Accelerated Meta-Algorithm for composite optimization with probabilistic inexact oracles and probabilistic inexactness in the proximal mapping, which may be of independent interest as well.