Statistics, computational complexity thereof

Statistical inference when computation isn’t free; what does this tell us about the learnable?


Bossaerts, Peter, Nitin Yadav, and Carsten Murawski. 2019. “Uncertainty and Computational Complexity.” Philosophical Transactions of the Royal Society B: Biological Sciences 374 (1766): 20180138.
Frey, B. J., and Nebojsa Jojic. 2005. “A Comparison of Algorithms for Inference and Learning in Probabilistic Graphical Models.” IEEE Transactions on Pattern Analysis and Machine Intelligence 27 (9): 1392–1416.
Jordan, Michael I., and Yair Weiss. 2002. “Probabilistic Inference in Graphical Models.” Handbook of Neural Networks and Brain Theory.
Moshkovitz, Dana, and Michal Moshkovitz. 2017. “Mixing Implies Lower Bounds for Space Bounded Learning.” In Conference on Learning Theory, 1516–66.