Abstract
Tracking the solution of time-varying variational inequalities is animportant problem with applications in game theory, optimization, and machinelearning. Existing work considers time-varying games or time-varyingoptimization problems. For strongly convex optimization problems or stronglymonotone games, these results provide tracking guarantees under the assumptionthat the variation of the time-varying problem is restrained, that is, problemswith a sublinear solution path. In this work we extend existing results in twoways: In our first result, we provide tracking bounds for (1) variationalinequalities with a sublinear solution path but not necessarily monotonefunctions, and (2) for periodic time-varying variational inequalities that donot necessarily have a sublinear solution path-length. Our second maincontribution is an extensive study of the convergence behavior and trajectoryof discrete dynamical systems of periodic time-varying VI. We show that thesesystems can exhibit provably chaotic behavior or can converge to the solution.Finally, we illustrate our theoretical results with experiments.