2022/05/06 by Tianyi Lin, Michael I. Jordan, Lin, Tianyi +1 · 4 citations
Computer Science · Medicine · #Contact Mechanics and Variational Inequalities #FOS: Computer and information sciences #FOS: Mathematics #Hip disorders and treatments #Machine Learning (cs.LG) #Optimization and Control (math.OC) #Optimization and Variational Analysis
paper · pdf · doi:10.48550/arxiv.2205.03202
openalex publication_date 2022/05/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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^⋆ ∈ X such that ⟨ F(x), x - x^⋆⟩ ≥ 0 for all x ∈ 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(ε-1). An improved rate of O(ε-2/3loglog(1/ε)) 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(ε-2/(p+1)loglog(1/ε)). 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 pth-order method that does not require any line search procedure and provably converges to a weak solution at a rate of O(ε-2/(p+1)). We prove that our pth-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(ε-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.