Tracking solutions of time-varying variational inequalities
<|reference_start|>Tracking solutions of time-varying variational inequalities: 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.<|reference_end|>
@article{hadiji2024tracking,
    title={Tracking solutions of time-varying variational inequalities},
    author={H'edi Hadiji, Sarah Sachs (UvA), Crist'obal Guzm'an (UC)},
    journal={arXiv preprint arXiv:2406.14059},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.14059},
    primaryClass={cs.GT cs.LG math.OC stat.ML}
}