Extragradient methods with complexity guarantees for hierarchical variational inequalities
Abstract
In the framework of a real Hilbert space we consider the problem of approaching solutions to a class of hierarchical variational inequality problems, subsuming several other problem classes including certain mathematical programs under equilibrium constraints, constrained min-max problems, hierarchical game problems, optimal control under VI constraints, and simple bilevel optimization problems. For this general problem formulation, we establish rates of convergence in terms of suitably constructed gap functions, measuring feasibility gaps and optimality gaps. We present worst-case iteration complexity results on both levels of the variational problem, as well as weak convergence under a geometric weak sharpness condition on the lower level solution set. Our results match and improve the state of the art in terms of their iteration complexity and the generality of the problem formulation.
Summary
This paper addresses the problem of finding solutions to hierarchical variational inequalities (HVIs) in a real Hilbert space. HVIs encompass a wide range of problems, including bilevel optimization, equilibrium selection in Nash games, and mathematical programs with equilibrium constraints. The authors aim to provide complexity guarantees for algorithms solving these problems, focusing on the optimistic extragradient method. Their approach involves formulating the HVI problem within a general framework and then analyzing the convergence rate of the optimistic extragradient method. They establish worst-case iteration complexity results for both levels of the variational problem by constructing suitable gap functions. A key aspect of their analysis is the use of a Tikhonov regularization technique and the introduction of an "Attouch-Czarnecki condition" to ensure convergence. They also leverage the concept of weak sharpness to derive improved rates under certain geometric conditions. The paper's main contribution lies in providing complexity bounds for a broader class of HVI problems than previously addressed, while also improving algorithmic efficiency by using a single operator evaluation per iteration. The significance of this work is that it provides a theoretical foundation for solving a wide range of hierarchical equilibrium problems that arise in various fields, including mathematical programming, machine learning, and game theory. By establishing complexity guarantees and enhancing algorithmic design, the paper contributes to the development of more efficient and reliable algorithms for solving these challenging problems.
Key Insights
- •The paper provides complexity guarantees for a general class of hierarchical variational inequality problems, extending previous results that focused on more specific problem formulations.
- •The optimistic extragradient method used in the paper requires only one operator evaluation per iteration, improving upon previous approaches that needed two evaluations.
- •Under a polynomial regularization sequence σ_k = O(k^{-δ}) for δ ∈ (0, 1), the authors demonstrate upper complexity bounds on the order of O(k^{-δ}) for the gap function associated with the lower-level equilibrium problem, and a O(k^{-(1-δ)}) complexity bound for the gap function of the entire hierarchical problem.
- •The analysis abandons the compactness assumption used in some previous works, instead relying on ideas from the convergence analysis of non-autonomous evolution equations.
- •The paper introduces an "Attouch-Czarnecki condition" (Assumption 3) that is crucial for proving convergence and boundedness of the iterates. Specifically, it requires summability of a term related to the dual properties of the lower-level variational inequality.
- •The paper demonstrates that under a weak sharpness assumption on the lower-level solution set, the summability condition (Assumption 3) is satisfied if ∑_{k=1}^∞ t_k σ_k^(ρ/(ρ-1)) < ∞, where ρ is a parameter characterizing the weak sharpness.
- •The improved rates under strong monotonicity assumptions (Theorem 5.1) shows that the feasibility gap Θ_Feas and optimality gap Θ_Opt converge faster when the upper-level problem is strongly monotone.
Practical Implications
- •The results can be applied to solve various real-world problems that can be modeled as hierarchical variational inequalities, such as bilevel optimization problems in machine learning, equilibrium selection in game theory, and optimal control problems with variational inequality constraints.
- •Researchers and engineers working on these problems can use the optimistic extragradient method with the proposed regularization strategies to develop efficient algorithms with provable convergence guarantees.
- •The paper provides insights into the relationship between the regularization parameter, step size, and convergence rate, which can guide the design of practical algorithms.
- •The theoretical analysis can be extended to other hierarchical equilibrium problems and algorithmic frameworks, potentially leading to new algorithms and improved complexity results.
- •Future research directions include exploring adaptive step size rules, investigating the performance of the algorithm in stochastic settings, and applying the theoretical framework to specific applications.