Memoryless Sequences for General Losses

Rafael M. Frongillo, Andrew B. NobelJMLR 2020

TL;DR

This paper generalizes the concept of "memoryless sequences" (sequences that are unpredictable even with past information) from squared loss to a much broader class of loss functions, including Bregman divergences. The authors show that the "memoryless" property is intimately tied to the statistical property elicited by the loss function, leading to a unified framework for understanding sequence randomness across different loss metrics.

What Problem Does This Paper Address?

The concept of randomness for an individual sequence is a fundamental question in probability and information theory. A common way to define randomness is through unpredictability: a random sequence should not be predictable beyond what its marginal distribution tells us. This is strongly related to the idea of "memorylessness," where past observations don't help predict future ones.

Previous work (Nobel, 2004) established that for the specific case of squared loss, memoryless sequences exhibit desirable stochastic properties analogous to independent and identically distributed (i.i.d.) sequences, like laws of large numbers and central limit theorems. However, the question remained: how does this change if we use different ways to measure prediction error (i.e., different loss functions)? This paper tackles this by exploring how the choice of loss function affects the set of memoryless sequences and their associated statistical properties.

Methods

The core of the paper lies in establishing a connection between memoryless sequences and the concept of property elicitation. Property elicitation deals with designing loss functions such that the optimal prediction for a given outcome distribution corresponds to a specific statistical property (like the mean or median) of that distribution.

The authors introduce an "orthogonality condition" that serves as a key mathematical tool. This condition relates the optimal prediction to the gradients of the loss function. They first prove this for differentiable losses and then extend it to non-differentiable losses under certain assumptions, particularly focusing on how "kinks" in the loss function can affect the orthogonality.

A crucial insight is that for a broad class of losses, including Bregman divergences, the set of memoryless sequences is determined solely by the property that the loss function elicits. This allows them to generalize Nobel's results to these more general loss functions. They also introduce a framework for handling non-convex and non-differentiable losses by using a composite form with an invertible link function.

Datasets

Not discussed in the paper. The paper focuses on theoretical properties of sequences and loss functions, rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Loss Function Dictates Memorylessness: The identity and statistical properties of memoryless sequences are fundamentally determined by the specific property elicited by the loss function. This is a major unifying insight.
  • Bregman Divergences are Special: All Bregman divergences (a broad class of convex loss functions) yield the same set of memoryless sequences as the simple squared loss. This means the rich stochastic properties observed for squared loss extend to this entire family.
  • Property Elicitation is Key: The concept of property elicitation is not just an abstract idea; it directly defines which sequences are memoryless. If a loss elicits the mean, the memoryless sequences will behave like martingale differences. If it elicits the median, they behave like "mediangale differences."
  • Orthogonality as a Unifying Principle: The derived "orthogonality condition" provides a powerful mathematical bridge between prediction optimality and the structure of memoryless sequences, applicable across various loss functions.
  • Generalizing Beyond Convexity: The paper develops techniques to handle non-convex and non-differentiable losses by framing them as composite functions, allowing the application of their core theorems to a wider range of practical scenarios.

Key Results

  • Theorem 9: Establishes that a sequence is memoryless for a loss l if and only if its weak limits of empirical measures satisfy a specific optimality condition related to the property elicited by l.
  • Corollary 11: States that two loss functions eliciting the same property will have the same set of memoryless sequences.
  • Generalization of Nobel's Results: The paper shows that the stochastic properties (like martingale difference behavior) observed for memoryless sequences under squared loss extend to any loss function that elicits the mean, including all Bregman divergences.
  • Application to Prediction Markets: The authors demonstrate how their framework can be used to analyze price calibration in prediction markets, showing that if traders cannot make infinite profits, market prices are "calibrated" in a specific sense related to memoryless sequences.

Limitations and Future Work

  • Finite-Memory Predictors: The definition of memorylessness is based on finite-memory predictors. The authors acknowledge that real-world algorithms might use the entire past history, which is a more complex setting. They suggest this could be a direction for future work, potentially linking to game-theoretic probability.
  • Dependent Variables: The current framework focuses on sequences of outcomes. Extending the analysis to incorporate dependent variables is suggested as a future research avenue.
  • Complexity of Prediction Function Class: The relationship between the complexity of the prediction function class and the resulting set of memoryless sequences is noted as an area for further study.
  • Adversarial Settings: The paper primarily deals with sequences that are "fixed" or "random" in a specific sense. Exploring similar results in more adversarial online settings, where outcome sequences can adapt to predictions, is proposed.

Summary updated

BibTeX
@article{frongillo2020memoryless,
  author = {Rafael M. Frongillo and Andrew B. Nobel},
  title = {{Memoryless Sequences for General Losses}},
  journal = {J. Mach. Learn. Res.},
  year = {2020},
}
Figure