On the Space Complexity of Online Convolution

Joel Daniel Andersson, Amir YehudayoffarXiv 2025 · DOI · arXiv

Abstract

This paper provides a complete characterization of the space complexity required for online discrete convolution. By establishing a formal streaming model over real numbers, the authors prove that the memory needed to process a stream is fundamentally determined by the "rationality" of the operation's generating function. Rational functions allow for constant-space computation, while irrational functions—including those critical for optimal private data analysis—require memory that grows linearly with time.

1. Introduction

Online convolution is a cornerstone of signal processing, time-series analysis, and differential privacy. In a streaming context, an incoming sequence $z = (z_0, z_1, \dots)$ must be processed such that at every time step $t$, the system outputs a weighted sum of all inputs seen so far. The central question addressed in this work is: How much past information must be stored in a buffer to maintain correct outputs?

While it was previously understood that certain "simple" convolutions (rational functions) could be computed with constant memory, matching lower bounds and a characterization of "complex" (irrational) functions remained missing. This paper closes these gaps, particularly highlighting the inherent memory costs of high-accuracy privacy-preserving algorithms.

2. The Streaming Model and Continuity

The authors establish a formal streaming model over $\mathbb{R}$, where an algorithm's internal state updates and output functions are assumed to be continuous. This continuity restriction is vital; without it, one could theoretically use space-filling curves to encode an infinite history into a single real-valued register. By requiring continuity, the model remains physically and computationally realistic.

To derive their results, the authors utilize several sophisticated mathematical frameworks:

  • Generating Functions: Representing the convolution as a formal power series $G(x)$.
  • Hankel Matrices: Relating memory buffer size to the rank of a matrix derived from convolution weights.
  • Borsuk-Ulam Theorem: Using this topological result to prove that if a continuous map compresses too much information, it must eventually map two distinct histories to the same state, causing the algorithm to fail.

3. Key Insights: Rationality as the Boundary

The "aha moment" of the research is that the degree of rationality of the generating function $G(x)$ perfectly determines the space complexity.

3.1 The Rational Case

If $G(x)$ is a rational function of degree $d$, the space complexity is exactly $d$ for all $t \ge d$ (Theorem 3). These functions represent the "easy" cases where a finite number of registers can track the necessary state of the system indefinitely.

3.2 The Irrational Case

For any irrational generating function, the space required at time $t$ is $t+1$ (Theorem 4). In these instances, the algorithm is forced to store the entire history of the stream. The authors suggest a Diophantine analogy: just as some irrational numbers are harder to approximate with rationals, some convolutions are "further" from being rational and thus more memory-intensive.

4. The "Hardness" of Differential Privacy

A significant application of this theory lies in Differential Privacy (DP). The function $G_{1/2}(x) = 1/\sqrt{1-x}$ is considered the "gold standard" for DP continual counting. This paper proves that $G_{1/2}$ is irrational and requires $\Omega(t)$ space (Theorem 5). This result explains why researchers have struggled to find memory-efficient versions of the most accurate DP algorithms—it is mathematically impossible within this model. Furthermore, the authors prove that neither "look-ahead" capabilities nor complex factorizations/parallelizations can reduce this fundamental memory requirement.

5. Limitations and Future Work

The current results focus on exact computation over real numbers. While the authors indicate that their lower-bound techniques can extend to approximate (Lipschitz) maps, the primary characterization assumes perfect precision.

A natural progression for this research is the exploration of the "space-accuracy tradeoff." Since exact computation of irrational functions is impossible in limited space, determining how much accuracy must be sacrificed to achieve sublinear (e.g., logarithmic) space is a high-priority question for scaling private machine learning to long-term data streams.

Summary updated

BibTeX
@misc{andersson2025space,
  author = {Joel Daniel Andersson and Amir Yehudayoff},
  title = {{On the Space Complexity of Online Convolution}},
  year = {2025},
  eprint = {2505.00181},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2505.00181},
}
Figure