Online Learning for Loss Functions with Memory and Applications to Statistical Arbitrage

Oren Anava, Elad Hazan, Shie MannorarXiv 2013 · arXiv

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.

  1. 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.
  2. 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."
Comparison of regret bounds between previous work and the proposed approaches.

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.

Algorithm 2: A randomized approach for OCO with memory.

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

Abstract

The framework of online learning with memory naturally captures learning problems with temporal constraints, and was previously studied for the experts setting. In this work we extend the notion of learning with memory to the general Online Convex Optimization (OCO) framework, and present two algorithms that attain low regret. The first algorithm applies to Lipschitz continuous loss functions, obtaining optimal regret bounds for both convex and strongly convex losses. The second algorithm attains the optimal regret bounds and applies more broadly to convex losses without requiring Lipschitz continuity, yet is more complicated to implement. We complement our theoretic results with an application to statistical arbitrage in finance: we devise algorithms for constructing mean-reverting portfolios.
BibTeX
@misc{anava2013online,
  author = {Oren Anava and Elad Hazan and Shie Mannor},
  title = {{Online Learning for Loss Functions with Memory and Applications to Statistical Arbitrage}},
  year = {2013},
  eprint = {1302.6937},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1302.6937},
}
Figure