Tracking solutions of time-varying variational inequalities

This paper extends tracking guarantees for time-varying variational inequalities to non-monotone functions and periodic problems without sublinear solution paths, while also demonstrating that the associated discrete dynamical systems can exhibit either convergence or provably chaotic behavior.

The Gist

Imagine you are trying to catch a moving target. Maybe it's a drone flying through a storm, or a stock price that changes every second, or a game opponent who keeps changing their strategy. Your goal is to predict where the target will be right now and move your own position to match it.

This paper is about the math behind that chase. Specifically, it looks at a class of problems called Variational Inequalities (VIs). Don't let the fancy name scare you; think of a VI as a general rule for finding a "sweet spot" or an equilibrium. It covers:

• Finding the lowest point in a valley (Optimization).
• Finding a fair deal where no one wants to change their move (Game Theory/Nash Equilibrium).
• Finding a balance point in a complex system.

The twist in this paper is that the "sweet spot" isn't sitting still. It's moving, dancing, or shifting over time. The authors ask: How well can an algorithm track this moving target?

Here is the breakdown of their findings, translated into everyday language:

1. The "Slow Walker" Scenario (Tame Problems)

Imagine the target is moving, but it's moving slowly and smoothly, like a turtle taking a leisurely stroll. It doesn't jump around wildly.

• The Finding: If the target moves slowly enough (mathematically called "sublinear path length"), you can track it very well.
• The Method: You just need an algorithm that is "contractive." Think of this like a rubber band. If you pull the rubber band (the algorithm) away from the target, the rubber band naturally snaps it back closer.
• The Result: Even if the target moves, your error (the distance between you and the target) stays small and manageable. You don't need to know exactly how the target moves, you just need to know it's not running a marathon.

2. The "Dancing Partner" Scenario (Periodic Problems)

Now, imagine the target isn't just walking slowly; it's dancing in a circle. It repeats the same moves over and over (e.g., every 10 seconds, it goes left, then right, then up). This is called a Periodic problem.

• The Problem: If you just use the "rubber band" method from above, you might get tired. Because the target keeps coming back to the same spots, a simple "snap back" strategy might make you overshoot and undershoot constantly, accumulating a lot of error over time.
• The Solution: The authors built a "Meta-Algorithm." Imagine you have a team of 100 different trackers.
  • Tracker A thinks the dance cycle is 5 seconds long.
  • Tracker B thinks it's 10 seconds.
  • Tracker C thinks it's 20 seconds.
  • They all guess where the target will be.
  • A "Manager" (the Meta-Algorithm) watches who is doing the best and gives more weight to their guess.
• The Result:
  • If the dance happens in a small room (bounded domain), the team can track the target with logarithmic error (the error grows very, very slowly, almost like it's flatlining).
  • If the dance happens in an infinite field (unbounded domain) but the moves are predictable, they can achieve constant error. This means no matter how long the dance goes on (1 hour or 100 years), your distance from the target never exceeds a fixed, small number. You essentially "lock on" to the pattern.

3. The "Chaotic Rollercoaster" (The Warning)

This is the most surprising and "scary" part of the paper.
The authors asked: What happens if we just use a standard, simple method (Gradient Descent) with a fixed speed on a periodic problem?

They discovered that depending on how fast you move (the "learning rate"), the system can behave in wild, unpredictable ways:

• Convergence: You glide smoothly to the target.
• Oscillation: You get stuck in a loop, circling the target but never landing on it.
• Divergence: You fly off into space, getting infinitely far away.
• Chaos: This is the kicker. For certain speeds, the system becomes Chaotic (in the mathematical sense of Li-Yorke chaos).
  • Analogy: Imagine two people starting at almost the exact same spot on a rollercoaster track. In a normal system, they stay close. In a chaotic system, after a few loops, one person is at the top of the hill and the other is at the bottom, and their paths will never look alike again. Tiny differences in your starting position or speed lead to completely different outcomes.
  • The Lesson: Just because a problem is "periodic" (repeating) doesn't mean a simple algorithm will work. If you pick the wrong speed, you might trigger chaos instead of finding the solution.

Why Does This Matter?

This isn't just abstract math; it applies to real life:

• Online Auctions: Bidding prices change every second based on demand. If the demand shifts slowly (Tame), simple bidding works. If it follows a daily cycle (Periodic), you need a smarter strategy to not overpay.
• Machine Learning: Training AI models often involves "streaming data" (data coming in a continuous flow). If the data distribution changes over time (e.g., user behavior changes seasonally), the AI needs to track these changes.
• Game Theory: In competitive games (like poker or stock trading), opponents adapt. If their strategy shifts in a pattern, you can learn to predict it. But if you react too aggressively (too high a learning rate), you might start making erratic, self-destructive moves.

The Big Takeaway

Tracking a moving target is hard.

1. If the target moves slowly, a simple "pull back" strategy works.
2. If the target moves in a repeating pattern, you need a "team of experts" to figure out the rhythm and lock onto it.
3. If you try to use a simple, fixed-speed strategy on a repeating pattern, you might accidentally trigger chaos, where your predictions become completely random and useless.

The paper gives us the rules of the road so we know when to drive slowly, when to use a GPS with a team of drivers, and when to avoid a specific speed that leads to a crash.

Technical Summary

Here is a detailed technical summary of the paper "Tracking Solutions of Time-Varying Variational Inequalities" by Hadiji, Sachs, and Guzmán.

1. Problem Definition

The paper addresses the problem of online tracking of solutions to Time-Varying Variational Inequalities (TV-VI).

• Setting: A learner sequentially encounters a sequence of operators $(F_t)_{t \in \mathbb{N}}$ defined on a closed convex set $Z \subseteq \mathbb{R}^d$. At each time step $t$, the learner outputs a candidate solution $Z_t$ based on past observations and then observes $F_t$.
• Goal: Minimize the tracking error, defined as the cumulative squared distance between the learner's output and the true solution $Z^\star_t$ of the instantaneous VI problem:
  $$\tau_T(A) = \sum_{t=1}^T \|Z_t - Z^\star_t\|^2$$
• Challenge: If the solution path varies arbitrarily, sublinear tracking error is impossible. The paper focuses on two specific regimes where tracking is feasible:
  1. Tame TV-VI: The quadratic path length of the solutions ($P^\star_T = \sum \|Z^\star_t - Z^\star_{t-1}\|^2$) is sublinear.
  2. Periodic TV-VI: The solutions (or operators) repeat with a period $k$ (i.e., $Z^\star_{t+k} = Z^\star_t$).

2. Methodology and Theoretical Framework

The authors develop two distinct methodological approaches corresponding to the two problem regimes.

A. Contractive Algorithms for Tame Problems

For problems where the solution path changes slowly (sublinear path length), the authors utilize the concept of contraction.

• Definition: An algorithm is $C$-contractive if, for any operator $F$ with solution $Z^\star$, the update rule $Z^+ = A(Z, F)$ satisfies $\|Z^+ - Z^\star\| \leq C \|Z - Z^\star\|$ for some $C \in (0,1)$.
• Key Insight: Strong monotonicity or bounded domains are not strictly required for contraction; certain non-monotone games and unbounded domains can also satisfy this property under specific conditions (e.g., Restricted Secant Inequality).
• Mechanism: By leveraging the contraction property, the tracking error is bounded by the cumulative movement of the true solutions (the path length).

B. Meta-Algorithm Aggregation for Periodic Problems

For periodic problems, simple contraction yields linear (vacuous) bounds because the solutions cycle. The authors propose a meta-algorithm that aggregates multiple "expert" base algorithms.

• Base Algorithms: Cyclic Forward-Backward methods (variants of Gradient Descent) tuned to specific assumed periods $i \in [1, K]$.
• Aggregation: An Exponential Weights (EW) meta-algorithm combines the predictions of these base algorithms.
  • Bounded Domains: Uses surrogate operators and fixed learning rates to achieve logarithmic regret.
  • Unbounded Domains: Uses adaptive learning rates (similar to AdaHedge) and Lipschitz continuity assumptions to achieve constant tracking error.
• Surrogate Operators: To handle the non-convexity of the VI gap function, the meta-algorithm uses affine surrogate operators $\tilde{F}_t(z) = F_t(Z_t) + \mu(z - Z_t)$ to construct the loss function for the aggregation step.

C. Dynamical Systems Analysis

The authors analyze the behavior of Gradient Descent (GD) with a fixed step size on periodic optimization problems. They treat the composition of periodic operators as an autonomous dynamical system $\Phi_\eta = \Phi_{\eta,1} \circ \dots \circ \Phi_{\eta,k}$. They investigate the stability, periodicity, and chaos of this system as the step size $\eta$ varies.

3. Key Contributions and Results

Contribution 1: Tracking Bounds for Tame TV-VI (Section 2)

• Result: For any $C$-contractive algorithm applied to a $\alpha$-tame problem (where path length $P^\star_T \leq c T^\alpha$), the tracking error is sublinear:
  $$\tau_T(A) \leq O(T^\alpha)$$
• Generality: This generalizes previous results from strongly convex optimization to general VIs and non-strongly monotone operators.
• Tightness: The authors prove this bound is tight; no uniform improvement is possible for all contractive algorithms.
• Examples: Includes Projected Gradient Descent, Resolvent Iteration, and specific non-monotone zero-sum games satisfying the Restricted Secant Inequality.

Contribution 2: Periodic TV-VI with Logarithmic and Constant Bounds (Section 3)

• Bounded Domain (Theorem 3.1): For strongly monotone operators on a bounded domain, the meta-algorithm achieves a logarithmic tracking bound:
  $$\tau_T(A) \leq O(k \log(T/k))$$
  This holds even if the period $k$ is unknown, provided an upper bound $K$ is known.
• Unbounded Domain (Theorem 3.2): For Lipschitz continuous, strongly monotone operators on unbounded domains ($\mathbb{R}^d$), the adaptive meta-algorithm achieves a constant tracking bound:
  $$\tau_T(A) \leq O(1)$$
  This bound depends on the initial distance to the solution set and the condition number, but is independent of $T$.

Contribution 3: Chaos and Complex Dynamics in Periodic GD (Section 5)

• Negative Result: The paper demonstrates that even for simple periodic optimization problems with a shared minimizer, fixed-step Gradient Descent can exhibit Li-Yorke chaos.
• Phenomena: Depending on the step size $\eta$, the system can:
  1. Converge to the minimizer.
  2. Diverge to infinity.
  3. Enter stable periodic cycles of arbitrary length.
  4. Exhibit chaotic behavior (scrambled sets).
• Star-Shaped Attractors: In higher dimensions, specific step sizes lead to iterates filling a "star-shaped" limit set, linking the problem to Iterated Function Systems (IFS).
• Implication: Tuning step sizes in periodic settings is non-trivial; increasing the step size can sometimes stabilize a divergent system or induce chaos in a convergent one.

4. Significance and Applications

• Theoretical Advancement: The work bridges the gap between online optimization, game theory, and dynamical systems. It extends tracking guarantees beyond the restrictive assumptions of strong convexity and bounded domains.
• Algorithm Design: The proposed meta-algorithms provide a robust framework for handling time-varying problems with unknown periodicity, offering the first constant tracking bounds for unbounded periodic VIs.
• Practical Relevance:
  • Applications: The framework applies to time-varying Kelly auctions, streaming linear regression, and Generalized Linear Models (GLMs) where parameters evolve over time.
  • Warning on Step Sizes: The chaos results serve as a critical warning for practitioners using fixed-step methods in periodic environments (e.g., single-shuffle SGD), highlighting that standard convergence guarantees may fail or lead to unpredictable behavior.
• Future Directions: The paper identifies the need for robust algorithms under stochastic feedback and the exploration of tracking in stochastic games.

Summary Table of Results

Setting	Assumptions	Algorithm Type	Tracking Bound
Tame TV-VI	Sublinear path length, Contractive Algo	Contractive (e.g., GD, Resolvent)	$O(T^\alpha)$ (Sublinear)
Periodic (Bounded)	Strongly Monotone, Bounded Domain	Meta-Algorithm (Aggregation)	$O(k \log T)$ (Logarithmic)
Periodic (Unbounded)	Strongly Monotone, Lipschitz, Unbounded	Meta-Algorithm (Adaptive)	$O(1)$ (Constant)
Periodic GD	Fixed Step Size, Periodic Functions	Gradient Descent	Can be Chaotic / Divergent

In conclusion, this paper provides a comprehensive theory for tracking time-varying equilibria, offering positive guarantees for tame and periodic settings while rigorously characterizing the potential for chaotic instability in standard iterative methods.