Tracking Solutions of Time-Varying Variational Inequalities

• 成果类型: Article; Early Access
• 署名作者: Hadiji, Hedi; Sachs, Sarah; Guzman, Cristobal
• 署名单位: Universite Paris Saclay; University of Bristol; Pontificia Universidad Catolica de Chile; Pontificia Universidad Catolica de Chile
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X; 1526-5471
• DOI: 10.1287/moor.2024.0571
• 发表日期: 2026-03-26
• 关键词: Online learning; time-varying variational inequalities; dynamic regret; Li-Yorke chaos

摘要

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.