Subspace methods for min-max problems
Abstract
This paper introduces four groups of subspace methods for nonlinear monotone equations, with applications to large-scale machine learning problems. The methods use Jacobian-free subspace ({\tt JFS}) directions of conjugate-gradient type, combined with either fixed step sizes or variable step sizes generated by the projected method of Solodov and Svaiter. To ensure convergence independently of the specific algebraic form of the subspace directions, we impose an angle condition together with an explicit scaling rule controlling the effective search directions. Under monotonicity and Lipschitz continuity of the operator, we establish global convergence for both the line-search and fixed-step frameworks, as well as a best-iterate residual rate O(ℓ−1/2). Under a local error bound, the distance to the solution set satisfies the sharper decay o(ℓ−1/2). If the operator is continuously differentiable and its Jacobian is nonsingular at a solution, the required local error bound and local isolation follow, yielding R-linear local convergence. The residual sequence then converges geometrically and hence satisfies the last-iterate rate o(ℓ−1), without strong monotonicity. We also derive iteration and residual-evaluation complexity bounds: O(ε−2) for the baseline best-iterate guarantee and O(log(ε−1)) in the local linear regime, together with a uniform bound on backtracking residual evaluations. Under additional asymptotic assumptions, the proposed {\tt JFS} directions and several classical update directions admit related optimistic gradient descent--ascent (\texttt{OGDA})-type residual--memory representations. Numerical experiments illustrate the robustness and efficiency of the methods on representative min--max problems.
Related
- Sparse descent subspace-Newton thresholding algorithm for sparse optimization problems
- A Two-level Filtered Subspace Iterative Method for Generalized Hermitian Interior Eigenvalue Problems
- Factorized Krylov subspace methods for solving large Sylvester equations
- A note on the complexity of random subspace model-based methods for derivative-free optimization
- Active Subspace-Guided Free-Form Deformation with Sinkhorn Autoencoders for Reduced-Order Modelling of Parametrised Shape Problems
BibTeX
@misc{kimiaei2026subspace,
title = {{Subspace methods for min-max problems}},
author = {Morteza Kimiaei and Shima Shabani and Michael Breuß},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.17375},
eprint = {2609.17375},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.17375},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Subspace methods for min-max problems
AU - Morteza Kimiaei
AU - Shima Shabani
AU - Michael Breuß
PY - 2026
DA - 2026/09/15
PB - arXiv
DO - 10.48550/arxiv.2609.17375
UR - https://arxiv.org/abs/2609.17375
AB - This paper introduces four groups of subspace methods for nonlinear monotone equations, with applications to large-scale machine learning problems. The methods use Jacobian-free subspace ({\tt JFS}) directions of conjugate-gradient type, combined with either fixed step sizes or variable step sizes generated by the projected method of Solodov and Svaiter. To ensure convergence independently of the specific algebraic form of the subspace directions, we impose an angle condition together with an explicit scaling rule controlling the effective search directions. Under monotonicity and Lipschitz continuity of the operator, we establish global convergence for both the line-search and fixed-step frameworks, as well as a best-iterate residual rate O(ℓ^−1/2). Under a local error bound, the distance to the solution set satisfies the sharper decay o(ℓ^−1/2). If the operator is continuously differentiable and its Jacobian is nonsingular at a solution, the required local error bound and local isolation follow, yielding R-linear local convergence. The residual sequence then converges geometrically and hence satisfies the last-iterate rate o(ℓ^−1), without strong monotonicity. We also derive iteration and residual-evaluation complexity bounds: O(ε^−2) for the baseline best-iterate guarantee and O(log(ε^−1)) in the local linear regime, together with a uniform bound on backtracking residual evaluations. Under additional asymptotic assumptions, the proposed {\tt JFS} directions and several classical update directions admit related optimistic gradient descent--ascent (\texttt{OGDA})-type residual--memory representations. Numerical experiments illustrate the robustness and efficiency of the methods on representative min--max problems.
ER -