Related papers: On the Hypomonotone Class of Variational Inequalities

On the Hypomonotone Class of Variational Inequalities

URL: http://arxiv.org/abs/2410.09182v1
Date: Fri, 11 Oct 2024 18:35:48 GMT
Title: On the Hypomonotone Class of Variational Inequalities
Authors: Khaled Alomar, Tatjana Chavdarova,
Abstract summary: We study the behavior of the extragradient algorithm when applied to hypomonotone operators. We provide a characterization theorem that identifies the conditions under which the extragradient algorithm fails to converge.
Score: 4.204990010424083
License: http://creativecommons.org/publicdomain/zero/1.0/
Abstract: This paper studies the behavior of the extragradient algorithm when applied to hypomonotone operators, a class of problems that extends beyond the classical monotone setting. While the extragradient method is widely known for its efficacy in solving variational inequalities with monotone and Lipschitz continuous operators, we demonstrate that its convergence is not guaranteed in the hypomonotone setting. We provide a characterization theorem that identifies the conditions under which the extragradient algorithm fails to converge. Our results highlight the necessity of stronger assumptions to guarantee convergence of extragradient and to further develop the existing VI methods for broader problems.

Related papers

Convergence of the Chambolle-Pock Algorithm in the Absence of Monotonicity [4.307128674848627]
The Chambolle-Pock algorithm (CPA) has gained popularity over the last decade due to its success in solving large-scale convex structured problems. This work extends its convergence analysis for problems with varying degrees of (non)monotonicity, quantified through a so-called weak Minty condition on the associated primal-dual operator.
arXiv Detail & Related papers (2023-12-11T17:20:24Z)
Eigenvalues asymptotics of unbounded operators. Two-photon quantum Rabi model [0.0]
We consider different cases of compact, relatively compact, selfadjoint or nonselfadjoint perturbations. We give an original proof of the Perelomov factorization theorem for operator of quantum optics.
arXiv Detail & Related papers (2023-12-09T19:27:20Z)
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)
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)
SARAH-based Variance-reduced Algorithm for Stochastic Finite-sum Cocoercive Variational Inequalities [137.6408511310322]
We consider the problem of finite-sum cocoercive variational inequalities. For strongly monotone problems it is possible to achieve linear convergence to a solution using this method.
arXiv Detail & Related papers (2022-10-12T08:04:48Z)
Clipped Stochastic Methods for Variational Inequalities with Heavy-Tailed Noise [64.85879194013407]
We prove the first high-probability results with logarithmic dependence on the confidence level for methods for solving monotone and structured non-monotone VIPs. Our results match the best-known ones in the light-tails case and are novel for structured non-monotone problems. In addition, we numerically validate that the gradient noise of many practical formulations is heavy-tailed and show that clipping improves the performance of SEG/SGDA.
arXiv Detail & Related papers (2022-06-02T15:21:55Z)
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)
Understanding Contrastive Learning Requires Incorporating Inductive Biases [64.56006519908213]
Recent attempts to theoretically explain the success of contrastive learning on downstream tasks prove guarantees depending on properties of em augmentations and the value of em contrastive loss of representations. We demonstrate that such analyses ignore em inductive biases of the function class and training algorithm, even em provably leading to vacuous guarantees in some settings.
arXiv Detail & Related papers (2022-02-28T18:59:20Z)
Some Hoeffding- and Bernstein-type Concentration Inequalities [47.24550702683417]
We prove concentration inequalities for functions of independent random variables under sub-gaussian and sub-exponential conditions. The utility of the inequalities is demonstrated by an extension of the now classical method of Rademacher complexities to Lipschitz function classes and unbounded sub-exponential distribution.
arXiv Detail & Related papers (2021-02-11T23:09:13Z)
The semiring of dichotomies and asymptotic relative submajorization [0.0]
We study quantum dichotomies and the resource theory of asymmetric distinguishability using a generalization of Strassen's theorem on preordered semirings. We find that an variant of relative submajorization, defined on unnormalized dichotomies, is characterized by real-valued monotones that are multiplicative under the tensor product and additive under the direct sum.
arXiv Detail & Related papers (2020-04-22T14:13:26Z)

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