ﻻ يوجد ملخص باللغة العربية
The optimization problems associated with training generative adversarial neural networks can be largely reduced to certain {em non-monotone} variational inequality problems (VIPs), whereas existing convergence results are mostly based on monotone or strongly monotone assumptions. In this paper, we propose {em optimistic dual extrapolation (OptDE)}, a method that only performs {em one} gradient evaluation per iteration. We show that OptDE is provably convergent to {em a strong solution} under different coherent non-monotone assumptions. In particular, when a {em weak solution} exists, the convergence rate of our method is $O(1/{epsilon^{2}})$, which matches the best existing result of the methods with two gradient evaluations. Further, when a {em $sigma$-weak solution} exists, the convergence guarantee is improved to the linear rate $O(logfrac{1}{epsilon})$. Along the way--as a byproduct of our inquiries into non-monotone variational inequalities--we provide the near-optimal $Obig(frac{1}{epsilon}log frac{1}{epsilon}big)$ convergence guarantee in terms of restricted strong merit function for monotone variational inequalities. We also show how our results can be naturally generalized to the stochastic setting, and obtain corresponding new convergence results. Taken together, our results contribute to the broad landscape of variational inequality--both non-monotone and monotone alike--by providing a novel and more practical algorithm with the state-of-the-art convergence guarantees.
In this paper, we study a class of generalized monotone variational inequality (GMVI) problems whose operators are not necessarily monotone (e.g., pseudo-monotone). We present non-Euclidean extragradient (N-EG) methods for computing approximate stron
We provide improved convergence rates for constrained convex-concave min-max problems and monotone variational inequalities with higher-order smoothness. In min-max settings where the $p^{th}$-order derivatives are Lipschitz continuous, we give an al
In this paper, we propose a unifying framework incorporating several momentum-related search directions for solving strongly monotone variational inequalities. The specific combinations of the search directions in the framework are made to guarantee
In this paper we propose a primal-dual homotopy method for $ell_1$-minimization problems with infinity norm constraints in the context of sparse reconstruction. The natural homotopy parameter is the value of the bound for the constraints and we show
In this article, we study algorithms for nonnegative matrix factorization (NMF) in various applications involving streaming data. Utilizing the continual nature of the data, we develop a fast two-stage algorithm for highly efficient and accurate NMF.