Tracking solutions of time-varying variational inequalities
This work addresses the problem of tracking solutions in time-varying variational inequalities for applications in game theory, optimization, and machine learning, representing an incremental extension of existing results.
The paper extends tracking guarantees for time-varying variational inequalities to non-monotone functions with sublinear solution paths and to periodic problems without sublinear paths, and analyzes discrete dynamical systems for such problems, showing they can exhibit chaotic behavior or converge to solutions, with experimental validation.
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, these 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. In this work we extend existing results in two ways: In our first result, we provide tracking bounds for (1) variational inequalities with a sublinear solution path but not necessarily monotone functions, and (2) 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 VI. We show that these systems can exhibit provably chaotic behavior or can converge to the solution. Finally, we illustrate our theoretical results with experiments.