Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Unifying Framework of Accelerated First-Order Approach to Strongly Monotone Variational Inequalities
91
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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 the optimal iteration complexity bound of $mathcal{O}left(kappaln(1/epsilon)right)$ to reach an $epsilon$-solution, where $kappa$ is the condition number. This framework provides the flexibility for algorithm designers to train -- among different parameter combinations -- the one that best suits the structure of the problem class at hand. The proposed framework includes the following iterative points and directions as its constituents: the extra-gradient, the optimistic gradient descent ascent (OGDA) direction (aka optimism), the heavy-ball direction, and Nesterovs extrapolation points. As a result, all the afore-mentioned methods become the special cases under the general scheme of extra points. We also specialize this approach to strongly convex minimization, and show that a similar extra-point approach achieves the optimal iteration complexity bound of $mathcal{O}(sqrt{kappa}ln(1/epsilon))$ for this class of problems.
rate research
Read More
In this paper, we propose two new solution schemes to solve the stochastic strongly monotone variational inequality problems: the stochastic extra-point solution scheme and the stochastic extra-momentum solution scheme. The first one is a general scheme based on updating the iterative sequence and an auxiliary extra-point sequence. In the case of deterministic VI model, this approach includes several state-of-the-art first-order methods as its special cases. The second scheme combines two momentum-based directions: the so-called heavy-ball direction and the optimism direction, where only one projection per iteration is required in its updating process. We show that, if the variance of the stochastic oracle is appropriately controlled, then both schemes can be made to achieve optimal iteration complexity of $mathcal{O}left(kappalnleft(frac{1}{epsilon}right)right)$ to reach an $epsilon$-solution for a strongly monotone VI problem with condition number $kappa$. We show that these methods can be readily incorporated in a zeroth-order approach to solve stochastic minimax saddle-point problems, where only noisy and biased samples of the objective can be obtained, with a total sample complexity of $mathcal{O}left(frac{kappa^2}{epsilon}lnleft(frac{1}{epsilon}right)right)$
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 algorithm HigherOrderMirrorProx that achieves an iteration complexity of $O(1/T^{frac{p+1}{2}})$ when given access to an oracle for finding a fixed point of a $p^{th}$-order equation. We give analogous rates for the weak monotone variational inequality problem. For $p>2$, our results improve upon the iteration complexity of the first-order Mirror Prox method of Nemirovski [2004] and the second-order method of Monteiro and Svaiter [2012]. We further instantiate our entire algorithm in the unconstrained $p=2$ case.
We study the robustness of accelerated first-order algorithms to stochastic uncertainties in gradient evaluation. Specifically, for unconstrained, smooth, strongly convex optimization problems, we examine the mean-squared error in the optimization variable when the iterates are perturbed by additive white noise. This type of uncertainty may arise in situations where an approximation of the gradient is sought through measurements of a real system or in a distributed computation over a network. Even though the underlying dynamics of first-order algorithms for this class of problems are nonlinear, we establish upper bounds on the mean-squared deviation from the optimal solution that are tight up to constant factors. Our analysis quantifies fundamental trade-offs between noise amplification and convergence rates obtained via any acceleration scheme similar to Nesterovs or heavy-ball methods. To gain additional analytical insight, for strongly convex quadratic problems, we explicitly evaluate the steady-state variance of the optimization variable in terms of the eigenvalues of the Hessian of the objective function. We demonstrate that the entire spectrum of the Hessian, rather than just the extreme eigenvalues, influence robustness of noisy algorithms. We specialize this result to the problem of distributed averaging over undirected networks and examine the role of network size and topology on the robustness of noisy accelerated algorithms.
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 strong solutions of these problems, and demonstrate how their iteration complexities depend on the global Lipschitz or H{o}lder continuity properties for their operators and the smoothness properties for the distance generating function used in the N-EG algorithms. We also introduce a variant of this algorithm by incorporating a simple line-search procedure to deal with problems with more general continuous operators. Numerical studies are conducted to illustrate the significant advantages of the developed algorithms over the existing ones for solving large-scale GMVI problems.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
