Computing transition probabilities for multi-type branching processes is a fundamental challenge in stochastic modeling, often hindered by the cubic computational complexity of matrix exponentials. This paper, presented at AISTATS 2023, introduces a novel approach that reformulates the problem as a sparse optimization task. By integrating Compressed Sensing (CS) with a specialized Alternating Direction Method of Multipliers (ADMM) algorithm and leveraging Fast Fourier Transforms (FFT), the authors achieve significant speedups—up to 885x—over existing state-of-the-art methods.
The Computational Bottleneck
Branching processes are essential for modeling population dynamics in fields ranging from epidemiology to evolutionary biology. A critical task in statistical inference for these models is the calculation of transition probabilities: the likelihood that a population transitions from state $A$ to state $B$ over a given time interval.
Traditionally, this requires computing the matrix exponential of the system's generator, a process with $O(N^3)$ complexity, where $N$ is the state space size. For populations exceeding a few hundred, this becomes computationally intractable. While recent sparse recovery techniques have been applied, they often rely on slower proximal gradient methods that struggle with large-scale biological systems.
Methodology: Matrix-Free ADMM
The authors propose a "matrix-free" ADMM-based algorithm that exploits the inherent sparsity of transition probability matrices. The key innovation lies in performing updates in the Fourier domain. By evaluating the Probability Generating Function (PGF) at a small set of random points (Compressed Sensing), the problem is transformed into a sparse recovery task.
Key technical highlights include:
- Variable Splitting: ADMM is used to split the optimization objective into simpler sub-problems solved iteratively.
- Fourier Domain Updates: By staying in the Fourier domain, the sensing matrix becomes a diagonalized operator. The most expensive step (the "U-update") is solved using element-wise division and FFTs, reducing per-iteration complexity to $O(N^2 \log N)$.
- GPU Acceleration: The algorithm is highly parallelizable, allowing for massive acceleration using GPU-based FFT operations.
Robustness and Parameter Tuning
One of the significant advantages of this ADMM approach is its stability. Unlike many optimization-based solvers that require precise hyperparameter tuning, this method remains effective across a broad spectrum of step sizes ($\beta$) and regularization parameters ($\lambda$).
As shown in Figure 1, the relative error remains negligible for several orders of magnitude of the stepsize $\beta$. This "inelasticity" to tuning makes the algorithm highly practical for researchers, as it avoids the need for extensive grid searches for optimal parameters.
Key Results and Accuracy
The method was validated on two biological models: a two-compartment hematopoiesis model and a birth-death-shift model for transposons. The performance gains are dramatic, especially as the population size $N$ increases. For $N=1024$, the GPU-accelerated version was approximately 885 times faster than Proximal Gradient Descent (PGD).
Despite the massive increase in speed, accuracy is not compromised. Figure 3 illustrates that the recovered probability mass functions are nearly identical to the ground truth. Furthermore, the figure highlights the sparsity of the transition matrix; at finite time scales, only a small fraction of the state space has non-zero probability, a property the ADMM algorithm successfully exploits to achieve its efficiency.
Conclusion
The proposed ADMM-based framework represents a significant leap in the computational feasibility of analyzing complex branching processes. By reducing complexity and offering massive parallelization potential, it opens the door to more sophisticated statistical inference, such as Maximum Likelihood Estimation (MLE) or MCMC, where transition probabilities must be computed repeatedly in high-dimensional biological modeling.
Summary updated