Two-timescale Extragradient for Finding Local Minimax Points

• URL: http://arxiv.org/abs/2305.16242v2
• Date: Mon, 22 Apr 2024 12:06:46 GMT
• Title: Two-timescale Extragradient for Finding Local Minimax Points
• Authors: Jiseok Chae, Kyuwon Kim, Donghwan Kim,
• Abstract summary: We show that the two-timescale extragrad method can be a viable solution to minimax problems. This work provably improves upon all previous results on finding local minimax points.
• Score: 8.056359341994941
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Minimax problems are notoriously challenging to optimize. However, we present that the two-timescale extragradient method can be a viable solution. By utilizing dynamical systems theory, we show that it converges to points that satisfy the second-order necessary condition of local minimax points, under mild conditions that the two-timescale gradient descent ascent fails to work. This work provably improves upon all previous results on finding local minimax points, by eliminating a crucial assumption that the Hessian with respect to the maximization variable is nondegenerate.

Related papers

• A first-order method for nonconvex-nonconcave minimax problems under a local Kurdyka-Łojasiewicz condition [1.534667887016089]
  We study a class of non-nonconcave minimax problems in which the inner problem a local Kurdyka-Lojasiewicz (KL) condition varies with the outer minimization variable.<n>In particular, as an algorithm progresses toward a stationary point of the problem, the region over which the KL condition holds may shrink, resulting in a more potentially ill-conditioned landscape.
  arXiv  Detail & Related papers  (2025-07-02T17:45:10Z)
• Zeroth-Order Optimization Finds Flat Minima [51.41529512093436]
  We show that zeroth-order optimization with the standard two-point estimator favors solutions with small trace of Hessian.<n>We further provide convergence rates of zeroth-order optimization to approximate flat minima for convex and sufficiently smooth functions.
  arXiv  Detail & Related papers  (2025-06-05T17:59:09Z)
• 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)
• Randomized Gradient Descents on Riemannian Manifolds: Almost Sure Convergence to Global Minima in and beyond Quantum Optimization [0.0]
  We study randomization of the tangent space directions of gradient flows for minimizing smooth cost functions. We prove that convergence to local optima can be obtained almost surely despite the existence of saddle points. We discuss the time required by the algorithm to pass a saddle point in a simple two-dimensional setting.
  arXiv  Detail & Related papers  (2024-05-20T14:06:45Z)
• Near-Optimal Algorithms for Making the Gradient Small in Stochastic Minimax Optimization [14.719077076351377]
  We study the problem of finding a near-stationary point for smooth minimax optimization. We show that a novel algorithm called Recursive IteratioNRAIN achieves both convex-concave and strongly-concave cases.
  arXiv  Detail & Related papers  (2022-08-11T16:55:26Z)
• Efficiently Escaping Saddle Points in Bilevel Optimization [48.925688192913]
  Bilevel optimization is one of the problems in machine learning. Recent developments in bilevel optimization converge on the first fundamental nonaptature multi-step analysis.
  arXiv  Detail & Related papers  (2022-02-08T07:10:06Z)
• A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm for Bilevel Optimization [112.59170319105971]
  We propose a new algorithm -- the Momentum- Single-timescale Approximation (MSTSA) -- for tackling problems. MSTSA allows us to control the error in iterations due to inaccurate solution to the lower level subproblem.
  arXiv  Detail & Related papers  (2021-02-15T07:10: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)
• Optimality and Stability in Non-Convex Smooth Games [39.365235811852365]
  An interesting concept is known as the local minimax point, which strongly correlates with descent. gradient algorithms can converge to local/global minimax points in the non-degenerate case, but they would often fail in general cases. This implies the necessity of either novel algorithms or concepts beyond saddle points in non-known smooth games.
  arXiv  Detail & Related papers  (2020-02-27T02:16:01Z)
• 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)
• Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Nets [71.05306664267832]
  Adaptive algorithms perform gradient updates using the history of gradients and are ubiquitous in training deep neural networks. In this paper we analyze a variant of OptimisticOA algorithm for nonconcave minmax problems. Our experiments show that adaptive GAN non-adaptive gradient algorithms can be observed empirically.
  arXiv  Detail & Related papers  (2019-12-26T22:10:10Z)

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.