Improving gradient mapping complexity for constrained stochastic min max problems

How to Make the Gradient Mapping Small for Constrained Stochastic Min-Max Problems and Beyond

Machine Learning

Summary

Stochastic min-max problems arise in many applications where one wants to optimize the worst-case scenario under constraints. A common way to measure progress is using something called the gradient mapping, which generalizes gradients to constrained settings. Previously, the best known methods required a lot of steps to reduce this gradient mapping to a small value. The authors found a way to achieve the same efficiency in these constrained problems as is known for unconstrained cases, speeding up the process significantly. They also extended their results to cases where the usual assumptions about randomness do not fully hold.

What this means in practice

  • For machine learning engineers: Design optimization algorithms for training models with constraints and adversarial components more efficiently using improved complexity bounds.
  • For financial modelers: Enhance risk management techniques by using faster methods to solve constrained stochastic min-max problems involved in worst-case scenario analysis.

A theory result. No direct application yet.

Authors

Ahmet Alacaoglu

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.
View PDFOpen arXiv