In the field of Online Convex Optimization (OCO), standard models typically assume a "memoryless" environment where the loss at any given time depends solely on the current decision. However, real-world systems—ranging from control systems to financial markets—often exhibit path-dependency. In these scenarios, past actions influence current costs. This paper, "Online Convex Optimization Against Adversaries with Memory and Application to Statistical Arbitrage" by Anava, Hazan, and Mannor (2014), addresses this gap by extending the OCO framework to handle adversaries with memory and applying these theoretical insights to the domain of statistical arbitrage.
The Challenge of Memory and Policy Regret
In a standard OCO setting, a player chooses $x_t$, an adversary reveals $g_t$, and the player suffers loss $g_t(x_t)$. When memory is introduced, an adversary with memory length $m$ imposes a loss $f_t(x_{t-m}, \dots, x_t)$. This dependency renders standard "regret" metrics insufficient, as they do not account for how a different sequence of past actions would have altered the adversary's state.
To solve this, the authors utilize Policy Regret. This metric compares the player's cumulative loss against the best fixed sequence of actions in hindsight, explicitly accounting for the interaction between that fixed sequence and the adversary's memory.
Algorithmic Frameworks
The authors propose two primary algorithmic approaches to minimize policy regret, achieving bounds that match theoretical lower limits.
- RFTL-M (Regularized Follow The Leader with Memory): This approach adapts the classic RFTL algorithm by minimizing a "memoryless" proxy of the loss functions. If the loss functions are Lipschitz continuous, the player can achieve optimal regret bounds: $O(T^{1/2})$ for general convex losses and $O(\log T)$ for strongly convex losses.
- Low Switches Algorithm: For scenarios where loss functions lack Lipschitz continuity, the authors propose a randomized approach. By ensuring the player changes their decision infrequently—specifically $O(\sqrt{T})$ times—the impact of the adversary's memory is minimized, allowing memory effects to "wash out."
The Low Switches Approach
The second approach relies on stability via randomization. By utilizing a technique similar to the "Shrinking Dartboard," the algorithm maintains a decision with high probability, only sampling a new decision when the weights shift significantly. This stability is key to handling non-Lipschitz losses while maintaining nearly optimal $\tilde{O}(T^{1/2})$ regret.
Application: Online Statistical Arbitrage
The theoretical framework is applied to financial engineering through Online Statistical Arbitrage (OSA). Traditional statistical arbitrage often relies on "offline" models like the Johansen test, which train on historical blocks of data. In contrast, the OSA algorithm is "online," adapting its portfolio weights as new market data arrives.
To handle the non-convex nature of mean-reversion proxies in finance, the authors employ a Positive Semi-Definite (PSD) relaxation. This transformation converts a non-convex problem into a solvable linear optimization over matrices, allowing the OCO-with-memory algorithms to be deployed effectively in a trading context.
Empirical Results
The OSA algorithm was evaluated using daily closing rates for 10 pairs of sector-related stocks (e.g., Coca-Cola and Pepsi) from 2008 to 2013. The results demonstrated significant advantages over traditional baselines:
- Cumulative Wealth: OSA consistently outperformed Orthogonal Least Squares (OLS) and Johansen Vector Error Correction models.
- Risk-Adjusted Returns: OSA achieved a Sharpe ratio of 2.194, surpassing OLS (2.160) and Johansen (1.571).
- Adaptability: As an online method, OSA proved more robust to shifting market regimes, with performance approaching the theoretical "Offline Optimum" over time.
Conclusion
By bridging the gap between theoretical online learning and path-dependent applications, this work provides a robust framework for optimization in environments with memory. While challenges remain—such as accounting for transaction costs and optimizing memory length parameters—the OSA algorithm represents a significant step forward in creating adaptive, theoretically grounded financial models.
Summary updated