Tracking solutions of time-varying variational inequalities

Hédi Hadiji, Sarah Sachs, Cristóbal GuzmánarXiv 2024 · DOI · arXiv

Introduction

In dynamic environments such as high-frequency trading, multi-agent games, and streaming data analysis, the objective is rarely to find a static optimum. Instead, agents must track a "moving target"—a solution that evolves over time. This paper provides a rigorous theoretical framework for tracking solutions to time-varying Variational Inequalities (VIs), a mathematical class that encompasses convex optimization, Nash equilibria, and fixed-point problems.

Problem Formulation: Tame vs. Periodic Drift

The authors distinguish between two primary tracking scenarios:

  1. Tame VIPs: Problems where the solution path drifts slowly or "tamely," without necessarily requiring strong monotonicity.
  2. Periodic VIPs: Problems characterized by seasonal or cyclical patterns where the period length $k$ is unknown to the learner.

Theoretical Framework and Main Results

The paper establishes several key theorems that provide upper bounds on tracking error $\tau_T(\mathcal{A})$.

Contractive Tracking for Tame Problems

Theorem 2.1 demonstrates that any algorithm with a "one-step contraction" property (e.g., Gradient Descent or Resolvent Iteration) can successfully track a moving target in tame environments. The tracking error is shown to be sublinear, specifically $O(T^\alpha)$, where $\alpha$ relates to the path length of the solution.

Comparison of tracking rates and settings between Theorem 2.1 and prior literature.

As shown in the comparison table above, Theorem 2.1 generalizes previous results by allowing for deterministic feedback in time-varying VIs using any contractive algorithm, matching or improving upon rates found in more specialized settings.

Meta-Algorithms for Periodic Environments

For periodic problems with unknown cycles, the authors propose a meta-algorithm that aggregates multiple base algorithms (like Online Gradient Descent) using Exponential Weights (EW). This approach achieves logarithmic or even constant tracking error, depending on whether the domain is bounded.

Summary of main theoretical results for Tame and k-Periodic VIPs.

The Chaos Phenomenon in Periodic Systems

A significant contribution of this work is the analysis of fixed-step Gradient Descent (GD) in periodic settings. The authors identify three distinct phases of behavior based on the learning rate:

  • Phase I (Convergence): The algorithm successfully tracks the periodic solution.
  • Phase II (Composite): A complex regime where the system may exhibit convergence, periodicity, or Li-Yorke chaos.
  • Phase III (Divergence): The algorithm fails to track and the iterates diverge.

The discovery of Li-Yorke chaos (Observation 1) is particularly striking, proving that even simple 2-periodic problems can become effectively unpredictable if the learning rate is not carefully tuned. Surprisingly, the authors find that increasing the learning rate can sometimes stabilize a chaotic system, defying standard optimization intuition.

Conclusion and Future Directions

This research bridges the gap between classical optimization and dynamic game theory. While the current work focuses on deterministic feedback, future extensions include adapting these meta-algorithms for stochastic (noisy) feedback and exploring the connections between time-varying VIs and fractal geometry through Iterated Function Systems.

Summary updated

BibTeX
@misc{hadiji2024tracking,
  author = {Hédi Hadiji and Sarah Sachs and Cristóbal Guzmán},
  title = {{Tracking solutions of time-varying variational inequalities}},
  year = {2024},
  eprint = {2406.14059},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2406.14059},
}
Figure