Efficient Parameter-Free First-Order Methods for Nonsmooth Composite Minimax Optimization
Abstract
In this paper we propose first-order methods for a class of nonsmooth composite strongly convex--strongly concave and nonconvex--concave minimax optimization. We first develop an inexact proximal method and an accumulative regularizated method for strongly convex--strongly concave problems. The latter achieves the optimal dependence on the curvature parameters and places the smaller curvature inside the accuracy logarithm. Using this method as a subsolver, we propose a proximal point method for nonconvex--concave problems. Under suitable assumptions, it finds an ε-stationary point with an operation complexity of O(ε−5/2), which improves the best-known O(ε−5/2log(1/ε)) bounds by removing the logarithmic factor. We further develop parameter-free variants for both problem classes, and achieve the same complexity without knowledge of any problem constants. All proposed methods are equipped with verifiable termination criteria.
Related
- An Infeasible Method with Feasibility Safeguard for Nonsmooth Composite Optimization Over Manifolds
- A Stochastic Riemannian Alternating Descent Ascent Method for Nonsmooth Composite Expectation Optimization on Riemannian Manifolds
- Exact penalty methods with adaptive discretization for nonsmooth semi-infinite optimization
- Proximal Limited-Memory Quasi-Newton Methods for Nonsmooth Nonconvex Optimization
- Projected Subgradient Methods for a Class of Nonsmooth and Nonconvex Optimization Problems
BibTeX
@misc{ke2026efficient,
title = {{Efficient Parameter-Free First-Order Methods for Nonsmooth Composite Minimax Optimization}},
author = {Shaozhe Ke and Sanyou Mei and Jiheng Zhang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.25752},
eprint = {2609.25752},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.25752},
}
RIS
TY - UNPB
TI - Efficient Parameter-Free First-Order Methods for Nonsmooth Composite Minimax Optimization
AU - Shaozhe Ke
AU - Sanyou Mei
AU - Jiheng Zhang
PY - 2026
DA - 2026/09/22
PB - arXiv
DO - 10.48550/arxiv.2609.25752
UR - https://arxiv.org/abs/2609.25752
AB - In this paper we propose first-order methods for a class of nonsmooth composite strongly convex--strongly concave and nonconvex--concave minimax optimization. We first develop an inexact proximal method and an accumulative regularizated method for strongly convex--strongly concave problems. The latter achieves the optimal dependence on the curvature parameters and places the smaller curvature inside the accuracy logarithm. Using this method as a subsolver, we propose a proximal point method for nonconvex--concave problems. Under suitable assumptions, it finds an ε-stationary point with an operation complexity of O(ε^−5/2), which improves the best-known O(ε^−5/2log(1/ε)) bounds by removing the logarithmic factor. We further develop parameter-free variants for both problem classes, and achieve the same complexity without knowledge of any problem constants. All proposed methods are equipped with verifiable termination criteria.
ER -