Tracking Solutions of Time-Varying Variational Inequalities

Abstract

Tracking the solution of time-varying variational inequalities is an important problem with applications in game theory, optimization, and machine learning. Existing work considers time-varying games or time-varying optimization problems. For strongly convex optimization problems or strongly monotone games, such results provide tracking guarantees under the assumption that the variation of the time-varying problem is restrained, that is, problems with a sublinear solution path. We extend existing results in two ways: In our first result, we provide tracking bounds for (i) variational inequalities with a sublinear solution path but not necessarily monotone functions and (ii) for periodic time-varying variational inequalities that do not necessarily have a sublinear solution path length. Our second main contribution is an extensive study of the convergence behavior and trajectory of discrete dynamical systems of periodic time-varying variational inequalities. We show that these systems can either exhibit provably chaotic behavior or can converge to the solution. Funding: Work was done when S. Sachs was supported by the Netherlands Organization for Scientific Research [Grant VI.Vidi.192.095], and parts of the revision were done when S. Sachs was supported by the European Union–Next Generation EU, PRIN 2022 (Progetti di ricerca di Rilevante Interesse Nazionale) 2022 [Grant CUP:J53D23007170001]. C. Guzmán’s research was partially supported by the INRIA (Institut national de recherche en sciences et technologies du numérique) Associate Teams project [Grants ANID FONDECYT 1210362 and ANID Anillo ACT210005] and the National Center for Artificial Intelligence CENIA (Centro Nacional de Inteligencia Artificial) [Grant FB210017], Basal ANID (Agencia Nacional de Investigación y Desarrollo).