Beyond first-order methods for non-convex non-concave min-max optimization

• URL: http://arxiv.org/abs/2304.08389v1
• Date: Mon, 17 Apr 2023 15:55:40 GMT
• Title: Beyond first-order methods for non-convex non-concave min-max optimization
• Authors: Abhijeet Vyas and Brian Bullins
• Abstract summary: We show improvements attainable beyond the monotone and Minty condition settings. Specifically, we provide a new understanding of discrete-time minimization. We present a continuoustime analysis alongside which match those for the discretetime setting.
• Score: 6.097141897343098
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose a study of structured non-convex non-concave min-max problems which goes beyond standard first-order approaches. Inspired by the tight understanding established in recent works [Adil et al., 2022, Lin and Jordan, 2022b], we develop a suite of higher-order methods which show the improvements attainable beyond the monotone and Minty condition settings. Specifically, we provide a new understanding of the use of discrete-time $p^{th}$-order methods for operator norm minimization in the min-max setting, establishing an $O(1/\epsilon^\frac{2}{p})$ rate to achieve $\epsilon$-approximate stationarity, under the weakened Minty variational inequality condition of Diakonikolas et al. [2021]. We further present a continuous-time analysis alongside rates which match those for the discrete-time setting, and our empirical results highlight the practical benefits of our approach over first-order methods.

Related papers

• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  We consider the problem of optimizing second-order smooth and strongly convex functions where the algorithm is only accessible to noisy evaluations of the objective function it queries. We provide the first tight characterization for the rate of the minimax simple regret by developing matching upper and lower bounds.
  arXiv  Detail & Related papers  (2024-06-28T02:56:22Z)
• Strictly Low Rank Constraint Optimization -- An Asymptotically $\mathcal{O}(\frac{1}{t^2})$ Method [5.770309971945476]
  We propose a class of non-text and non-smooth problems with textitrank regularization to promote sparsity in optimal solution. We show that our algorithms are able to achieve a singular convergence of $Ofrac(t2)$, which is exactly same as Nesterov's optimal convergence for first-order methods on smooth convex problems.
  arXiv  Detail & Related papers  (2023-07-04T16:55:41Z)
• A Fully First-Order Method for Stochastic Bilevel Optimization [8.663726907303303]
  We consider unconstrained bilevel optimization problems when only the first-order gradient oracles are available. We propose a Fully First-order Approximation (F2SA) method, and study its non-asymptotic convergence properties. We demonstrate even superior practical performance of the proposed method over existing second-order based approaches on MNIST data-hypercleaning experiments.
  arXiv  Detail & Related papers  (2023-01-26T05:34:21Z)
• Min-Max Optimization Made Simple: Approximating the Proximal Point Method via Contraction Maps [77.8999425439444]
  We present a first-order method that admits near-optimal convergence rates for convex/concave min-max problems. Our work is based on the fact that the update rule of the Proximal Point method can be approximated up to accuracy.
  arXiv  Detail & Related papers  (2023-01-10T12:18:47Z)
• A Primal-Dual Approach to Solving Variational Inequalities with General Constraints [54.62996442406718]
  Yang et al. (2023) recently showed how to use first-order gradient methods to solve general variational inequalities. We prove the convergence of this method and show that the gap function of the last iterate of the method decreases at a rate of $O(frac1sqrtK)$ when the operator is $L$-Lipschitz and monotone.
  arXiv  Detail & Related papers  (2022-10-27T17:59:09Z)
• Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
  We propose and analyze inexact regularized Newton-type methods for finding a global saddle point of emphcon unconstrained min-max optimization problems. We show that the proposed methods generate iterates that remain within a bounded set and that the iterations converge to an $epsilon$-saddle point within $O(epsilon-2/3)$ in terms of a restricted function.
  arXiv  Detail & Related papers  (2022-10-23T21:24:37Z)
• Accelerated Single-Call Methods for Constrained Min-Max Optimization [5.266784779001398]
  Existing methods either require two gradient calls or two projections in each iteration, which may costly in some applications. In this paper, we first show that a variant of the Optimistic Gradient (RGOG) has a rich set of non-comonrate min-max convergence rate problems. Our convergence rates hold for standard measures such as and the natural and the natural.
  arXiv  Detail & Related papers  (2022-10-06T17:50:42Z)
• Higher-order methods for convex-concave min-max optimization and monotone variational inequalities [7.645449711892907]
  We provide improved convergence rates for constrained convex-concave min-max problems and monotone variational inequalities with higher-order smoothness. For $p>2$, our results improve upon the iteration complexity of the first-order Mirror Prox method of Nemirovski. We further instantiate our entire algorithm in the unconstrained $p=2$ case.
  arXiv  Detail & Related papers  (2020-07-09T03:12:33Z)
• Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Condition [52.08417569774822]
  This paper focuses on methods for solving smooth non-concave min-max problems, which have received increasing attention due to deep learning (e.g., deep AUC)
  arXiv  Detail & Related papers  (2020-06-12T00:32:21Z)
• Optimal Epoch Stochastic Gradient Descent Ascent Methods for Min-Max Optimization [61.66927778694731]
  Epoch gradient descent method (a.k.a. Epoch-GD) proposed by Hazan and Kale (2011) was deemed a breakthrough for strongly convex minimization. Our result is the first one that shows Epoch-GDA can achieve the optimal rate of $O (1/T)$ for the duality gap of SCSC min-max problems.
  arXiv  Detail & Related papers  (2020-02-13T02:16:57Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.