In probabilistic modeling, we frequently encounter the need to calculate the distribution of a sum of independent random variables. Whether we are counting the number of successful outcomes in a series of trials, aggregating label proportions in a dataset, or predicting the total size of a viral cascade, the underlying mathematical operation is the same: discrete convolution.
Traditionally, these calculations suffer from a combinatorial explosion. To find the probability that exactly $k$ events occur, one must typically sum over all possible combinations of outcomes that lead to that total. As the number of variables grows, this approach becomes computationally intractable. However, a growing body of research demonstrates that by shifting these problems into the frequency domain using the Fast Fourier Transform (FFT), we can bypass combinatorial complexity and achieve near-linear scaling.
The Convolutional Nature of Sums
When we add two independent discrete random variables, $X$ and $Y$, the probability mass function (PMF) of their sum $Z = X + Y$ is the convolution of their individual PMFs. If we represent these PMFs as vectors, the direct calculation of their convolution requires $O(N^2)$ operations.
This quadratic bottleneck appears across diverse fields. For instance, in Bayesian Network inference, Hsiao et al. note that summation-based causal independence—where a child node represents the sum of its parents—leads to exponential growth in conditional probability tables. Similarly, De Smet and Zuidberg Dos Martires identify this bottleneck in neurosymbolic reasoning, where performing exact probabilistic integer arithmetic traditionally scales poorly with the size of the integer domain.
The Spectral Shortcut
The core intuition behind this research direction is the Convolution Theorem: a convolution in the time (or spatial) domain is equivalent to point-wise multiplication in the frequency domain. By applying the FFT to the PMFs of independent variables, multiplying the resulting spectra, and then applying the Inverse FFT, we can compute the distribution of the sum in $O(N \log N)$ time.
This transformation is not merely a speedup; it fundamentally changes what is computable:
- Poisson Binomial Distributions: Calculating the probability of $k$ successes in $n$ independent Bernoulli trials (each with a different probability) is a classic challenge. Tong et al. and Wijk et al. use spectral methods to handle these distributions efficiently, enabling exact gradients for subset selection and frequent itemset mining in uncertain databases.
- Polynomial Multiplication: Ma et al. frame the aggregation of instance probabilities into group-level label proportions as a polynomial multiplication problem. By treating PMFs as coefficients of polynomials, the FFT allows for efficient end-to-end training on large data "bags" that were previously too complex to model.
Scaling Subset Selection and Ranking
Many machine learning tasks involve selecting a subset of $k$ items from a larger set of $n$. This appears in $k$-expert problems, caching, and assortment optimization. The challenge lies in calculating marginal inclusion probabilities—the likelihood that a specific item is part of the optimal subset.
Mukhopadhyay et al. and Joshi and Sinha show that these marginals can be represented as coefficients of elementary symmetric polynomials. By leveraging the FFT to compute these coefficients, they reduce the complexity of subset selection from $O(n^2)$ to $O(n \log^2 n)$ or $O(n \log n)$. This allows online learning algorithms to scale to massive libraries of items, such as in universal caching policies.
Similarly, Swersky et al. employ an FFT-based tree algorithm to manage the combinatorial complexity of partition functions in multi-label classification, while Désir et al. use discrete convolutions to evaluate choice probabilities in ranking-based demand models.
Beyond Simple Sums: Causal and Network Dynamics
The utility of spectral acceleration extends to complex system dynamics. In network science, Burkholz and Quackenbush use FFT-optimized convolutions to compute the full distribution of cascade sizes in the Independent Cascade Model, moving beyond simple averages to understand the risk of extreme viral events.
In the realm of causal discovery, Qiao et al. utilize the FFT to accelerate the calculation of likelihoods in Poisson Branching Structural Causal Models. By speeding up the evaluation of probability mass functions, they enable faster skeleton discovery and model selection for discrete count data. Even in continuous processes, Moscovich and Nadler demonstrate that recursive probability calculations for Poisson process boundary crossings can be reframed as truncated convolutions, allowing the FFT to reduce complexity from cubic to nearly quadratic time.
Conclusion
The shift toward spectral likelihood optimization represents a move away from exhaustive enumeration and toward exploiting the algebraic structure of probability. By recognizing that the aggregation of independent discrete evidence is fundamentally a convolutional process, researchers have unlocked the ability to perform exact inference and optimization in domains once considered computationally prohibitive. Whether in air traffic management Marceau et al. or randomized linear algebra Deshpande and Rademacher, the FFT serves as a universal tool for taming combinatorial complexity.
Key Foundational Work
Mining Frequent Itemsets over Uncertain Databases (2012) — contributed 1 concept elements to this direction.
Affine Independent Variational Inference (2012) — contributed 1 concept elements to this direction.
Probabilistic n-Choose-k Models for Classification and Ranking (2012) — contributed 1 concept elements to this direction.