Summary
This work looks at how hard it is to solve certain optimization problems where you try to minimize and maximize at the same time under constraints, and where randomness is involved. Usually, checking how close you are to the best solution involves measuring something called the gradient mapping, which is a general way to track progress. Before this paper, the best methods for constrained problems took much longer than for simpler unconstrained cases. The authors improve the methods so that the time needed is as good as the unconstrained case, making these problems easier to solve in practice. They also show their approach works even without some common assumptions about randomness.
stochastic optimizationconvex-concave min-max problemsgradient mappingconstrained optimizationoracle complexityvariational inequalitiesvariance assumptionsBlum-Gladyshev assumptionfirst-order methods
Abstract
We study the stochastic first-order oracle complexity for constrained or regularized convex-concave min-max optimization and stochastic monotone variational inequalities. We focus on the case when suboptimality is measured in terms of the gradient mapping, also known as, forward-backward or natural residual, an optimality notion that generalizes the gradient norm for unconstrained problems. In this setting, under standard unbiased oracle access with now-standard variance assumptions, the best-known complexity for making the norm of the gradient mapping less than $\varepsilon$ is $\widetilde{O}(\varepsilon^{-4})$, compared to the near-optimal $\widetilde{O}(\varepsilon^{-2})$ that is established in the unconstrained case. We bridge this gap to improve the gradient mapping complexity for constrained convex-concave min-max problems to $\widetilde{O}(\varepsilon^{-2})$. We then extend to prove the same complexity for problems without the bounded variance, by using the Blum-Gladyshev assumption.