Metraipolis › archive › dc_27d28f8bebfa
Projection-Free Algorithms for Nonsmooth Stochastic Convex-Concave Saddle-Point Problems — arXiv:2609.35275
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.35275
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-07T23:06:48.731Z
- SHA-256 of the archived text
5fb8e7dbf45888131234a17bf2cbeda0a4e37d825ac0d2ce50bdac050e1fbcdc- Stable URL of this page
https://metraipolis.com/documento/dc_27d28f8bebfa
How to cite
Projection-Free Algorithms for Nonsmooth Stochastic Convex-Concave Saddle-Point Problems — arXiv:2609.35275 — arXiv (en), https://arxiv.org/abs/2609.35275 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_27d28f8bebfa (Metraipolis archive dc_27d28f8bebfa, sha256 5fb8e7dbf45888131234a17bf2cbeda0a4e37d825ac0d2ce50bdac050e1fbcdc)
BibTeX
@misc{dc27d28f8bebfa,
title = {Projection-Free Algorithms for Nonsmooth Stochastic Convex-Concave Saddle-Point Problems — arXiv:2609.35275},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.35275},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_27d28f8bebfa; sha256 5fb8e7dbf45888131234a17bf2cbeda0a4e37d825ac0d2ce50bdac050e1fbcdc},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.35275. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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(\epsilon^{-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.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-29 in math.OC).
Categorie arXiv: Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2609.35275 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T22:42:39.280Z dalla pagina https://arxiv.org/catchup/math.OC/2026-09-29?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).