On the Convergence of Stochastic Compositional Gradient Descent Ascent Method

Hongchang Gao, Xiaoqian Wang, Lei Luo, Xinghua ShiIJCAI 2021 · DOI

Abstract

This paper introduces the Stochastic Compositional Gradient Descent Ascent (SCGDA) method, the first efficient algorithm designed for nonconvex-strongly-concave compositional minimax problems. By integrating a variance-controlled estimation strategy for inner functions, SCGDA addresses the inherent bias in stochastic gradients of compositional objectives. Theoretical analysis establishes a convergence rate of $O(\kappa^4/\epsilon^4)$, and empirical evaluations on a distributionally robust reinforcement learning task demonstrate the algorithm's effectiveness and sensitivity to hyperparameter selection.

Introduction

Modern machine learning increasingly relies on complex optimization structures, specifically minimax and compositional optimization. Minimax optimization is essential for finding saddle points in Generative Adversarial Networks (GANs) and adversarial training. Compositional optimization is crucial in reinforcement learning (RL) and portfolio management where objectives are nested (e.g., $f(g(x))$).

The challenge arises when these two structures intersect into a compositional minimax problem. In this scenario, standard stochastic gradients become biased because the inner function $g(x)$ is typically accessible only through noisy samples. Existing minimax algorithms assume unbiased gradients, while existing compositional algorithms are not designed for adversarial settings. This work fills this gap by proposing the Stochastic Compositional Gradient Descent Ascent (SCGDA) method for nonconvex-strongly-concave problems.

Methodology: SCGDA

The SCGDA algorithm addresses the "two-level stochasticity" of compositional minimax problems through several key innovations:

  1. Variance-Controlled Estimation: To mitigate the bias arising from stochastic samples of the inner function $g(x)$ and its gradient $\nabla g(x)$, SCGDA maintains moving averages ($u_t$ and $u'_t$). This momentum-like strategy reduces estimation variance, which is the primary source of bias in compositional problems.
  2. Single-Timescale Update: The algorithm updates the minimization variable ($x$) and the maximization variable ($y$) simultaneously using these refined estimates, ensuring computational efficiency.
  3. Projection Operator: To handle constraints on the maximization variable $y$, common in robust optimization, a projection step keeps $y$ within its feasible set.

Experimental Setup

The authors evaluated SCGDA using a synthetic Markov Decision Process (MDP) benchmark for distributionally robust linear value function approximation. The setup included 400 states and 10 actions per state. Transition probabilities were drawn from a uniform distribution $[0, 1]$ and adjusted to ensure ergodicity, mimicking the complexity of learning robust policies in environments with uncertain transitions.

Results and Discussion

Theoretical analysis shows that SCGDA achieves a convergence rate of $O(\kappa^4/\epsilon^4)$, where $\kappa$ is the condition number and $\epsilon$ is the target accuracy. This is a significant improvement over the $O(1/\epsilon^8)$ rates observed in earlier non-minimax compositional works.

Empirically, the "Value Function Gap"—a measure of distance from the optimal solution—decreased consistently across various learning rates. As shown in Figure 1, larger learning rates ($\eta$) lead to faster initial convergence.

Figure 1: Value function gap vs. iterations for varying learning rates η.

Furthermore, the algorithm successfully learns to weight different states differently, confirming that the minimax component effectively prioritizes high-risk states. This is visualized in Figure 2, which shows the deviation of state weights from a uniform distribution ($y - 1/S$).

Figure 2: Distribution of state weights y - 1/S across samples, indicating non-uniform prioritization of states.

Conclusion

SCGDA provides a robust framework for solving compositional minimax problems with provable convergence. While the current theory assumes strong concavity in the maximization variable, it sets a milestone for future research. Future work could extend this to nonconvex-nonconcave problems and explore advanced variance reduction techniques like SPIDER or STORM to further improve the dependence on the condition number. Scaling SCGDA to high-dimensional continuous control tasks remains an important next step for practical deployment.

Summary updated

BibTeX
@inproceedings{gao2021convergence,
  author = {Hongchang Gao and Xiaoqian Wang and Lei Luo and Xinghua Shi},
  title = {{On the Convergence of Stochastic Compositional Gradient Descent Ascent Method}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.24963/ijcai.2021/329},
}
Figure