Anytime Tail Averaging

Nicolas Le RouxarXiv 2019 · OpenReview

TL;DR

This paper introduces "Anytime Tail Averaging" (ATA), a novel set of techniques for computing running averages of recent data points in a stream. ATA offers a constant memory footprint, providing access to an up-to-date average at every time step, overcoming limitations of existing methods that either require growing memory or are not available continuously.

What Problem Does This Paper Address?

In many applications, such as deep learning optimization, we need to compute a running average of the most recent data points (a "tail average"). The challenge is that traditional methods for calculating this average either:

  1. Require growing memory: The memory needed to store past data points increases with the number of samples we want to average. This is prohibitive when dealing with large datasets or high-dimensional data (like neural network parameters).
  2. Are not available at every timestep: Some methods only provide an average at specific, pre-determined intervals, meaning you might miss recent updates.
  3. Don't handle growing windows well: The number of samples to average might itself increase over time, which complicates existing approaches.

The authors aim to solve this by developing methods that provide an accurate tail average at any time step, with a constant memory cost, even when the window of samples to average is growing.

Methods

The paper proposes two main families of techniques under the umbrella of Anytime Tail Averaging (ATA):

  1. Growing Exponential Average: This method extends the standard exponential average (which has a constant memory cost but doesn't perfectly match a fixed window average) to better approximate the variance of a growing window average. It's designed for efficiency, offering the lowest memory cost.
  2. Anytime Window Average (AWA): This approach uses multiple "accumulators" to store data. New samples are added to the most recent accumulator. When an accumulator fills up, its contents are "flushed" to an older accumulator, and the new one is reset. This allows for a more accurate approximation of the true tail average. The number of accumulators can be adjusted to trade off accuracy for memory consumption.

Both methods are designed to be "anytime" (available at every step) and have a computational cost independent of the window size ($k_t$).

Datasets

Not discussed in the paper. The experiments are conducted in a simulated stochastic linear regression setting.

Key Insights and Ideas

  • The staleness-variance trade-off: Existing methods for tail averaging inherently balance how "fresh" the average is (staleness) against how accurate it is (variance). The authors aim to minimize staleness while maintaining a target variance.
  • Constant memory is achievable: The core contribution is demonstrating that accurate tail averaging can be done with a constant memory footprint, a significant improvement over methods that scale with the window size.
  • Multiple accumulators for accuracy: The AWA method shows that by using multiple, tiered accumulators, one can achieve higher accuracy than a simple exponential average, especially when the data stream has distinct phases (e.g., rapid change followed by stability).
  • Flexibility in memory/accuracy: The AWA approach offers a tunable parameter (the number of accumulators) that allows users to choose between lower memory usage with slightly less accuracy, or higher memory usage for a more precise average.

Key Results

  • Constant $k_t = k$: For a fixed window size $k$, the Anytime Window Average (AWA) with two accumulators performs comparably to the exact moving average, outperforming the standard exponential average, especially as $k$ increases. The exponential average degrades faster because it gives too much weight to old, irrelevant samples when the data stream changes rapidly.
  • Growing $k_t = c \cdot t$: For a growing window size, the proposed methods also perform well. For smaller growth rates ($c=0.25$), most methods are indistinguishable from the true average. However, as the growth rate increases ($c=0.5$), the standard "raw" tail averaging becomes very stale. The growing exponential average offers the best memory-accuracy trade-off here. The AWA with three accumulators matches the true average's performance in this more challenging scenario.

Limitations and Future Work

  • Experimental setting: The experiments were conducted in a simulated stochastic linear regression setting. While this is a common benchmark, testing on real-world, complex deep learning tasks would be valuable.
  • Tuning parameters: The performance of AWA depends on the number of accumulators and the parameters governing when accumulators flush. The paper explores this trade-off but further analysis on optimal tuning strategies could be beneficial.
  • Generalizability: While the paper focuses on optimization, the authors suggest the methods could be useful in other scenarios where tracking averages over changing time windows is important, such as in BatchNorm for tracking means and variances. Future work could explore these broader applications.

Summary updated

Abstract

Tail averaging consists in averaging the last examples in a stream. Common techniques either have a memory requirement which grows with the number of samples to average, are not available at every timestep or do not accomodate growing windows. We propose two techniques with a low constant memory cost that perform tail averaging with access to the average at every time step. We also show how one can improve the accuracy of that average at the cost of increased memory consumption.
BibTeX
@misc{roux2019anytime,
  author = {Nicolas Le Roux},
  title = {{Anytime Tail Averaging}},
  year = {2019},
  eprint = {1902.05083},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1902.05083},
}
Figure