Phase transitions in statistical inference
There is a deep analogy between statistical inference and statistical physics; I will give a friendly introduction to both of these fields. I will then discuss phase transitions in two problems of interest to a broad range of data sciences: community detection in social and biological networks, and clustering of sparse high-dimensional data. In both cases, if our data becomes too sparse or too noisy, it suddenly becomes impossible to find the underlying pattern, or even tell if there is one. Physics both helps us locate these phase transitions, and design optimal algorithms that succeed all the way up to this point. Along the way, I will visit ideas from computational complexity, random graphs, random matrices, and spin glass theory.
See Igor Carron’s “phase diagram” list, and stuff like this Weng et al “Overcoming The Limitations of Phase Transition by Higher Order Analysis of Regularization Techniques” (WeMZ16) or possibly OyTr15. Likely there are connections to Erdős-Renyi giant components and other complex network things in probabilisitic graph learning. Read Barb15, PLRS16, WeMZ16.
Replicator equations and evolutionary processes
Gentle intro lecture by John Baez, Biology as Information Dynamics.
- Baez, J. C.(2011) Renyi Entropy and Free Energy.
- Barbier, J. (2015) Statistical physics and approximate message-passing algorithms for sparse linear estimation problems in signal processing and coding theory. ArXiv:1511.01650 [Cs, Math].
- Harper, M. (2009a) Information Geometry and Evolutionary Game Theory.
- Harper, M. (2009b) The Replicator Equation as an Inference Dynamic.
- Oymak, S., & Tropp, J. A.(2015) Universality laws for randomized dimension reduction, with applications. ArXiv:1511.09433 [Cs, Math, Stat].
- Poole, B., Lahiri, S., Raghu, M., Sohl-Dickstein, J., & Ganguli, S. (2016) Exponential expressivity in deep neural networks through transient chaos. In D. D. Lee, M. Sugiyama, U. V. Luxburg, I. Guyon, & R. Garnett (Eds.), Advances in Neural Information Processing Systems 29 (pp. 3360–3368). Curran Associates, Inc.
- Shalizi, C. R.(2009) Dynamics of Bayesian updating with dependent data and misspecified models. Electronic Journal of Statistics, 3, 1039–1074. DOI.
- Sinervo, B., & Lively, C. M.(1996) The rock–paper–scissors game and the evolution of alternative male strategies. Nature, 380(6571), 240. DOI.
- Weng, H., Maleki, A., & Zheng, L. (2016) Overcoming The Limitations of Phase Transition by Higher Order Analysis of Regularization Techniques. ArXiv:1603.07377 [Cs, Math, Stat].