Position: Temporal Measurement Interval Determines Computational and Model Complexity in Single-Cell Perturbation Analysis

Alireza Jafari, Heman Shakeri, Hadi Daneshmand
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:170607-170631, 2026.

Abstract

Single-cell perturbation analysis aims to predict how cellular states change after interventions such as drug treatments or genetic edits. A central difficulty is that pre- and post-perturbation measurements are typically observed as unpaired populations, so accurate prediction requires inferring a latent coupling and learning a transition map. In this position paper, we argue that the measurement time gap is the key experimental knob controlling both the computational tractability of coupling and the effective model complexity. We identify a critical time gap $\Delta$ that induces a phase transition, under biologically inspired conditions; for "measurement-time $< \Delta$", matching is polynomial-time tractable and the task reduces to supervised learning, whereas for "measurement-time $>\Delta$", recovering the matching is NP-hard in the worst case. The required conditions are restricted isometry of the initial states and temporal smoothness of the transition dynamics. We complement the theory with empirical evidence on synthetic and biological datasets showing a sharp regime change as the time gap increases. Furthermore, we demonstrate that a linear model can match or exceed the performance of higher-capacity neural approaches when our conditions hold.

Cite this Paper


BibTeX
@InProceedings{pmlr-v306-jafari26a, title = {Position: Temporal Measurement Interval Determines Computational and Model Complexity in Single-Cell Perturbation Analysis}, author = {Jafari, Alireza and Shakeri, Heman and Daneshmand, Hadi}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {170607--170631}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/jafari26a/jafari26a.pdf}, url = {https://proceedings.mlr.press/v306/jafari26a.html}, abstract = {Single-cell perturbation analysis aims to predict how cellular states change after interventions such as drug treatments or genetic edits. A central difficulty is that pre- and post-perturbation measurements are typically observed as unpaired populations, so accurate prediction requires inferring a latent coupling and learning a transition map. In this position paper, we argue that the measurement time gap is the key experimental knob controlling both the computational tractability of coupling and the effective model complexity. We identify a critical time gap $\Delta$ that induces a phase transition, under biologically inspired conditions; for "measurement-time $< \Delta$", matching is polynomial-time tractable and the task reduces to supervised learning, whereas for "measurement-time $>\Delta$", recovering the matching is NP-hard in the worst case. The required conditions are restricted isometry of the initial states and temporal smoothness of the transition dynamics. We complement the theory with empirical evidence on synthetic and biological datasets showing a sharp regime change as the time gap increases. Furthermore, we demonstrate that a linear model can match or exceed the performance of higher-capacity neural approaches when our conditions hold.} }
Endnote
%0 Conference Paper %T Position: Temporal Measurement Interval Determines Computational and Model Complexity in Single-Cell Perturbation Analysis %A Alireza Jafari %A Heman Shakeri %A Hadi Daneshmand %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-jafari26a %I PMLR %P 170607--170631 %U https://proceedings.mlr.press/v306/jafari26a.html %V 306 %X Single-cell perturbation analysis aims to predict how cellular states change after interventions such as drug treatments or genetic edits. A central difficulty is that pre- and post-perturbation measurements are typically observed as unpaired populations, so accurate prediction requires inferring a latent coupling and learning a transition map. In this position paper, we argue that the measurement time gap is the key experimental knob controlling both the computational tractability of coupling and the effective model complexity. We identify a critical time gap $\Delta$ that induces a phase transition, under biologically inspired conditions; for "measurement-time $< \Delta$", matching is polynomial-time tractable and the task reduces to supervised learning, whereas for "measurement-time $>\Delta$", recovering the matching is NP-hard in the worst case. The required conditions are restricted isometry of the initial states and temporal smoothness of the transition dynamics. We complement the theory with empirical evidence on synthetic and biological datasets showing a sharp regime change as the time gap increases. Furthermore, we demonstrate that a linear model can match or exceed the performance of higher-capacity neural approaches when our conditions hold.
APA
Jafari, A., Shakeri, H. & Daneshmand, H.. (2026). Position: Temporal Measurement Interval Determines Computational and Model Complexity in Single-Cell Perturbation Analysis. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:170607-170631 Available from https://proceedings.mlr.press/v306/jafari26a.html.

Related Material