Abstract
We consider stochastic strongly-convex-strongly-concave (SCSC) saddle point (SP) problems which frequently arise in applications ranging from distributionally robust learning to game theory and fairness in machine learning. We focus on the recently developed stochastic accelerated primal-dual algorithm (SAPD), which admits optimal complexity in several settings as an accelerated algorithm. We provide high probability guarantees for convergence to a neighborhood of the saddle point that reflects accelerated convergence behavior. We also provide an analytical formula for the limiting covariance matrix of the iterates for a class of stochastic SCSC quadratic problems where the gradient noise is additive and Gaussian. This allows us to develop lower bounds for this class of quadratic problems which show that our analysis is tight in terms of the high probability bound dependency to the parameters. We also provide a risk-averse convergence analysis characterizing the "Conditional Value at Risk", the "Entropic Value at Risk", and the $\chi^2$-divergence of the distance to the saddle point, highlighting the trade-offs between the bias and the risk associated with an approximate solution obtained by terminating the algorithm at any iteration.
Introduction
Many modern machine learning challenges—such as distributionally robust optimization, game theory, and algorithmic fairness—are formulated as saddle-point (SP) problems. These involve a "minimax" objective where one player tries to minimize a cost while an adversary tries to maximize it. While efficient algorithms like the Stochastic Accelerated Primal-Dual (SAPD) method exist to solve these, most theoretical guarantees only describe performance "in expectation."
In practice, average performance is often insufficient. For safety-critical models, practitioners need to know the probability that an algorithm will fail to converge within a specific threshold. The challenge in analyzing SAPD lies in its "Gauss-Seidel" style updates, where variables are updated sequentially using the most recent information. This alternating structure makes the mathematical analysis of "tail events" (rare but large errors) significantly more difficult than standard simultaneous update methods.
Methodology
The authors establish a new theoretical framework to analyze SAPD under the assumption of "light-tailed" (sub-Gaussian) gradient noise for Strongly-Convex-Strongly-Concave (SCSC) problems. Central to this work is the characterization of convergence using sophisticated risk measures beyond simple expectation.
Key technical components include:
- A New Lyapunov Function: A novel function ($V_n$) designed to handle the alternating update structure of SAPD, proving it has favorable contraction properties.
- Concentration Inequalities: Specialized inequalities to bound the distance to the saddle point with high probability.
- Risk-Averse Analysis: Characterization of convergence using Value at Risk (VaR), Conditional Value at Risk (CVaR), and Entropic Value at Risk (EVaR), as defined in the table above.
- Quadratic Tightness: For quadratic problems with Gaussian noise, the authors derived an analytical formula for the limiting covariance matrix, proving their theoretical bounds are tight.
Key Insights and Results
Acceleration in the Tails
The most significant insight is that SAPD's "acceleration"—its ability to scale linearly with the condition number $\kappa$ rather than quadratically—is preserved in high-probability bounds. This means the algorithm reaches a neighborhood of the solution faster not just on average, but with high certainty.
The Price of Early Termination
As shown in the figure above, the risk-averse analysis provides a way to quantify the trade-off between "bias" (proximity to the solution) and "risk" (the variance/tail behavior of that solution). This allows engineers to make informed decisions about when to terminate the algorithm based on their specific risk tolerance.
Performance Metrics
- Iteration Complexity: SAPD reaches an $\epsilon$-accurate neighborhood in $O(\kappa \log(1/\epsilon))$ iterations with high probability, matching optimal rates for deterministic accelerated methods.
- Numerical Robustness: Experiments on synthetic bilinear games and UCI datasets (DryBean, Arcene) for distributionally robust logistic regression show that SAPD significantly outperforms non-accelerated methods like SGDA in controlling tail risk.
Limitations and Future Work
While this work provides a robust foundation, it assumes light-tailed noise. In some deep learning contexts, gradient noise can be "heavy-tailed," suggesting that future work should explore techniques like gradient clipping to extend these guarantees. Additionally, the current results are limited to SCSC problems; extending high-probability guarantees to non-convex saddle-point problems, such as those found in GAN training, remains an open challenge. Finally, the authors suggest that future research could investigate adaptive step-size rules to maintain these guarantees without manual parameter tuning.
Summary updated