Perseus: A Simple and Optimal High-Order Method for Variational Inequalities

• URL: http://arxiv.org/abs/2205.03202v6
• Date: Thu, 15 Feb 2024 01:00:50 GMT
• Title: Perseus: A Simple and Optimal High-Order Method for Variational Inequalities
• Authors: Tianyi Lin and Michael. I. Jordan
• Abstract summary: A VI involves finding $xstar in mathcalX$ such that $langle F(x), x - xstarrangle geq 0$ for all $x in mathcalX$. We propose a $pth$-order method that does textitnot require any line search procedure and provably converges to a weak solution at a rate of $O(epsilon-2/(p+1))$.
• Score: 81.32967242727152
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper settles an open and challenging question pertaining to the design of simple and optimal high-order methods for solving smooth and monotone variational inequalities (VIs). A VI involves finding $x^\star \in \mathcal{X}$ such that $\langle F(x), x - x^\star\rangle \geq 0$ for all $x \in \mathcal{X}$. We consider the setting in which $F$ is smooth with up to $(p-1)^{th}$-order derivatives. For $p = 2$, the cubic regularized Newton method was extended to VIs with a global rate of $O(\epsilon^{-1})$. An improved rate of $O(\epsilon^{-2/3}\log\log(1/\epsilon))$ can be obtained via an alternative second-order method, but this method requires a nontrivial line-search procedure as an inner loop. Similarly, high-order methods based on line-search procedures have been shown to achieve a rate of $O(\epsilon^{-2/(p+1)}\log\log(1/\epsilon))$. As emphasized by Nesterov, however, such procedures do not necessarily imply practical applicability in large-scale applications, and it would be desirable to complement these results with a simple high-order VI method that retains the optimality of the more complex methods. We propose a $p^{th}$-order method that does \textit{not} require any line search procedure and provably converges to a weak solution at a rate of $O(\epsilon^{-2/(p+1)})$. We prove that our $p^{th}$-order method is optimal in the monotone setting by establishing a matching lower bound under a generalized linear span assumption. Our method with restarting attains a linear rate for smooth and uniformly monotone VIs and a local superlinear rate for smooth and strongly monotone VIs. Our method also achieves a global rate of $O(\epsilon^{-2/p})$ for solving smooth and nonmonotone VIs satisfying the Minty condition and when augmented with restarting it attains a global linear and local superlinear rate for smooth and nonmonotone VIs satisfying the uniform/strong Minty condition.

Related papers

• First-Order Methods for Linearly Constrained Bilevel Optimization [38.19659447295665]
  We present first-order linearly constrained optimization methods for high-level Hessian computations. For linear inequality constraints, we attain $(delta,epsilon)$-Goldstein stationarity in $widetildeO(ddelta-1 epsilon-3)$ gradient oracle calls.
  arXiv  Detail & Related papers  (2024-06-18T16:41:21Z)
• Efficient Continual Finite-Sum Minimization [52.5238287567572]
  We propose a key twist into the finite-sum minimization, dubbed as continual finite-sum minimization. Our approach significantly improves upon the $mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$ requires. We also prove that there is no natural first-order method with $mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$, establishing that the first-order complexity of our method is nearly tight.
  arXiv  Detail & Related papers  (2024-06-07T08:26:31Z)
• Faster Linear Systems and Matrix Norm Approximation via Multi-level Sketched Preconditioning [10.690769339903941]
  We present a new class of preconditioned iterative methods for solving linear systems of the form $Ax = b$. Our methods are based on constructing a low-rank Nystr"om approximation to $A$ using sparse random sketching. We prove that the convergence of our methods depends on a natural average condition number of $A$, which improves as the rank of the Nystr"om approximation.
  arXiv  Detail & Related papers  (2024-05-09T15:53:43Z)
• A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
  In this paper we consider finding an approximate second-order stationary point (SOSP) that minimizes a twice different subject general non conic optimization. In particular, we propose a Newton-CG based-augmentedconjugate method for finding an approximate SOSP.
  arXiv  Detail & Related papers  (2023-01-10T20:43:29Z)
• Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
  We propose and analyze inexact regularized Newton-type methods for finding a global saddle point of emphcon unconstrained min-max optimization problems. We show that the proposed methods generate iterates that remain within a bounded set and that the iterations converge to an $epsilon$-saddle point within $O(epsilon-2/3)$ in terms of a restricted function.
  arXiv  Detail & Related papers  (2022-10-23T21:24:37Z)
• Decomposable Non-Smooth Convex Optimization with Nearly-Linear Gradient Oracle Complexity [15.18055488087588]
  We give an algorithm that minimizes the above convex formulation to $epsilon$-accuracy in $widetildeO(sum_i=1n d_i log (1 /epsilon))$ gradient computations. Our main technical contribution is an adaptive procedure to select an $f_i$ term at every iteration via a novel combination of cutting-plane and interior-point methods.
  arXiv  Detail & Related papers  (2022-08-07T20:53:42Z)
• Lifted Primal-Dual Method for Bilinearly Coupled Smooth Minimax Optimization [47.27237492375659]
  We study the bilinearly coupled minimax problem: $min_x max_y f(x) + ytop A x - h(y)$, where $f$ and $h$ are both strongly convex smooth functions. No known first-order algorithms have hitherto achieved the lower complexity bound of $Omega(sqrtfracL_xmu_x + frac|A|sqrtmu_x,mu_y) log(frac1vareps
  arXiv  Detail & Related papers  (2022-01-19T05:56:19Z)
• A first-order primal-dual method with adaptivity to local smoothness [64.62056765216386]
  We consider the problem of finding a saddle point for the convex-concave objective $min_x max_y f(x) + langle Ax, yrangle - g*(y)$, where $f$ is a convex function with locally Lipschitz gradient and $g$ is convex and possibly non-smooth. We propose an adaptive version of the Condat-Vu algorithm, which alternates between primal gradient steps and dual steps.
  arXiv  Detail & Related papers  (2021-10-28T14:19:30Z)

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.