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