Projection-Free Algorithms for Nonsmooth Stochastic Convex-Concave Saddle-Point Problems
Abstract
We study nonsmooth convex-concave saddle-point problems over compact convex sets, assuming access to stochastic subgradients of the payoff function. We develop single-loop projection-free algorithms that use linear minimization oracles over the primal and dual domains. Unlike prior projection-free approaches that rely on smoothing, our methods are purely subgradient-based and handle nonsmoothness directly. This design makes the framework modular: when a linear minimization oracle is not used over a specific domain, the corresponding update can be replaced by a standard projection oracle without changing the single-loop structure. Thus, our framework covers both fully projection-free and hybrid oracle configurations. We prove anytime strong saddle gap guarantees under standard unbiased stochastic oracle assumptions with bounded variance. Our algorithms achieve an O(ε−2) iteration complexity, matching projected stochastic subgradient methods. We also provide matching lower bounds for the corresponding oracle models, establishing minimax optimality. Our results show that, for nonsmooth stochastic minimax problems, the computational advantages of linear minimization oracles need not come at the expense of statistical or oracle efficiency.
Related
- Optimal Algorithms for Nonsmooth Nonconvex Stochastic Optimization with Constraints
- Accelerated primal-dual dynamics and algorithms for strongly convex-concave bilinear saddle point problems
- Lower Bounds for Stochastic First-Order Algorithms with Variance Reduction in Nonconvex--Concave Minimax Optimization
- Projection-Free Multi-level Algorithms for Stochastic Constrained Compositional Optimization
- Convergence guarantees for stochastic algorithms solving non-unique problems in metric spaces
BibTeX
@misc{giangtran2026projectionfree,
title = {{Projection-Free Algorithms for Nonsmooth Stochastic Convex-Concave Saddle-Point Problems}},
author = {Khanh-Hung Giang-Tran and Soroosh Shafiee},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.35275},
eprint = {2609.35275},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.35275},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Projection-Free Algorithms for Nonsmooth Stochastic Convex-Concave Saddle-Point Problems
AU - Khanh-Hung Giang-Tran
AU - Soroosh Shafiee
PY - 2026
DA - 2026/09/28
PB - arXiv
DO - 10.48550/arxiv.2609.35275
UR - https://arxiv.org/abs/2609.35275
AB - We study nonsmooth convex-concave saddle-point problems over compact convex sets, assuming access to stochastic subgradients of the payoff function. We develop single-loop projection-free algorithms that use linear minimization oracles over the primal and dual domains. Unlike prior projection-free approaches that rely on smoothing, our methods are purely subgradient-based and handle nonsmoothness directly. This design makes the framework modular: when a linear minimization oracle is not used over a specific domain, the corresponding update can be replaced by a standard projection oracle without changing the single-loop structure. Thus, our framework covers both fully projection-free and hybrid oracle configurations. We prove anytime strong saddle gap guarantees under standard unbiased stochastic oracle assumptions with bounded variance. Our algorithms achieve an O(ε^−2) iteration complexity, matching projected stochastic subgradient methods. We also provide matching lower bounds for the corresponding oracle models, establishing minimax optimality. Our results show that, for nonsmooth stochastic minimax problems, the computational advantages of linear minimization oracles need not come at the expense of statistical or oracle efficiency.
ER -