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(\ell^{-1/2})$. Under a local error bound, the distance to the solution set satisfies the sharper decay $o(\ell^{-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(\ell^{-1})$, without strong monotonicity. We also derive iteration and residual-evaluation complexity bounds: $O(\varepsilon^{-2})$ for the baseline best-iterate guarantee and $O(\log(\varepsilon^{-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.