Solving stochastic weak Minty variational inequalities without increasing batch size

• URL: http://arxiv.org/abs/2302.09029v1
• Date: Fri, 17 Feb 2023 17:56:26 GMT
• Title: Solving stochastic weak Minty variational inequalities without increasing batch size
• Abstract summary: This paper introduces a family of extragradient-type algorithms for a class of non-nonconcave problems. We show that it is possible to keep one fixed stepsize while it is only the second stepsize that is taken to be diminishing, making it interesting even in the monotone setting.
• Score: 46.71914490521821
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper introduces a family of stochastic extragradient-type algorithms for a class of nonconvex-nonconcave problems characterized by the weak Minty variational inequality (MVI). Unlike existing results on extragradient methods in the monotone setting, employing diminishing stepsizes is no longer possible in the weak MVI setting. This has led to approaches such as increasing batch sizes per iteration which can however be prohibitively expensive. In contrast, our proposed methods involves two stepsizes and only requires one additional oracle evaluation per iteration. We show that it is possible to keep one fixed stepsize while it is only the second stepsize that is taken to be diminishing, making it interesting even in the monotone setting. Almost sure convergence is established and we provide a unified analysis for this family of schemes which contains a nonlinear generalization of the celebrated primal dual hybrid gradient algorithm.

Related papers

• Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Inequality Constraints [12.624604051853657]
  We propose smoothed primal-dual algorithms for solving nonexact optimization problems with linear inequality constraints. Our algorithms are single-loop iterations based on one gradient at each sample. Unlike existing methods, our algorithms are free sub, large sizes or increasing parameters and use dual variable updates to ensure feasibility.
  arXiv  Detail & Related papers  (2025-04-10T09:59:43Z)
• First Order Methods with Markovian Noise: from Acceleration to Variational Inequalities [91.46841922915418]
  We present a unified approach for the theoretical analysis of first-order variation methods. Our approach covers both non-linear gradient and strongly Monte Carlo problems. We provide bounds that match the oracle strongly in the case of convex method optimization problems.
  arXiv  Detail & Related papers  (2023-05-25T11:11:31Z)
• Single-Call Stochastic Extragradient Methods for Structured Non-monotone Variational Inequalities: Improved Analysis under Weaker Conditions [21.681130192954583]
  Single-call extragradient methods are one of the most efficient algorithms for solving large-scale min-max optimization problems. We provide convergence guarantees for two classes of VIPs: (i) quasi-strongly monotone problems (a generalization of strongly monotone problems) and (ii) weak Minty variational inequalities (a generalization of monotone and Minty VIPs) Our convergence analysis holds under the arbitrary sampling paradigm, which includes importance sampling and various mini-batching strategies as special cases.
  arXiv  Detail & Related papers  (2023-02-27T18:53:28Z)
• SGD with AdaGrad Stepsizes: Full Adaptivity with High Probability to Unknown Parameters, Unbounded Gradients and Affine Variance [33.593203156666746]
  We show that AdaGrad stepsizes a popular adaptive (self-tuning) method for first-order optimization. In both the low-noise and high-regimes we find sharp rates of convergence in both the low-noise and high-regimes.
  arXiv  Detail & Related papers  (2023-02-17T09:46:08Z)
• High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance [59.211456992422136]
  We propose algorithms with high-probability convergence results under less restrictive assumptions. These results justify the usage of the considered methods for solving problems that do not fit standard functional classes in optimization.
  arXiv  Detail & Related papers  (2023-02-02T10:37:23Z)
• Beyond the Golden Ratio for Variational Inequality Algorithms [12.470097382737933]
  We improve the understanding of the $textitgolden ratio algorithm$, which solves monotone variational inequalities (VI) and convex-concave min-max problems. We introduce a new analysis that allows to use larger step sizes, to complete the bridge between the golden ratio algorithm and the existing algorithms in the literature.
  arXiv  Detail & Related papers  (2022-12-28T16:58:48Z)
• Tight Last-Iterate Convergence of the Extragradient Method for Constrained Monotone Variational Inequalities [4.6193503399184275]
  We show the last-iterate convergence rate of the extragradient method for monotone and Lipschitz variational inequalities with constraints. We develop a new approach that combines the power of the sum-of-squares programming with the low dimensionality of the update rule of the extragradient method.
  arXiv  Detail & Related papers  (2022-04-20T05:12:11Z)
• Differentiable Annealed Importance Sampling and the Perils of Gradient Noise [68.44523807580438]
  Annealed importance sampling (AIS) and related algorithms are highly effective tools for marginal likelihood estimation. Differentiability is a desirable property as it would admit the possibility of optimizing marginal likelihood as an objective. We propose a differentiable algorithm by abandoning Metropolis-Hastings steps, which further unlocks mini-batch computation.
  arXiv  Detail & Related papers  (2021-07-21T17:10:14Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  We propose two single-timescale single-loop algorithms that require only one data point each step. Our results are expressed in a form of simultaneous primal and dual side convergence.
  arXiv  Detail & Related papers  (2020-08-23T20:36:49Z)
• Balancing Rates and Variance via Adaptive Batch-Size for Stochastic Optimization Problems [120.21685755278509]
  In this work, we seek to balance the fact that attenuating step-size is required for exact convergence with the fact that constant step-size learns faster in time up to an error. Rather than fixing the minibatch the step-size at the outset, we propose to allow parameters to evolve adaptively.
  arXiv  Detail & Related papers  (2020-07-02T16:02:02Z)
• Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scaling [34.35013145885164]
  Extragradient methods have become a staple for solving large-scale saddlepoint problems in machine learning. We show in this paper that running vanilla extragradient with gradients may jeopardize its convergence, even in simple bilinear models. We show that this modification allows the method to converge even with gradients, and we derive sharp convergence rates under an error bound condition.
  arXiv  Detail & Related papers  (2020-03-23T10:24:27Z)

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.