The Living Thing / Notebooks :

Statistical mechanics of statistics

Boaz Barak has a miniature dictionary for statisticians:

I’ve always been curious about the statistical physics approach to problems from computer science. The physics-inspired algorithm survey propagation is the current champion for random 3SAT instances, statistical-physics phase transitions have been suggested as explaining computational difficulty, and statistical physics has even been invoked to explain why deep learning algorithms seem to often converge to useful local minima.

Unfortunately, I have always found the terminology of statistical physics, “spin glasses”, “quenched averages”, “annealing”, “replica symmetry breaking”, “metastable states” etc.. to be rather daunting

Phase transitions in statistical inference

Cristopher Moore says

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

See also evolution, game theory.

Gentle intro lecture by John Baez, Biology as Information Dynamics.

See Baez11, Harp09a, Harp09b, Shal09, SiLi96.

Refs

Baez11
Baez, J. C.(2011) Renyi Entropy and Free Energy.
Barb15
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].
BKMM17
Barbier, J., Krzakala, F., Macris, N., Miolane, L., & Zdeborová, L. (2017) Phase Transitions, Optimal Errors and Optimality of Message-Passing in Generalized Linear Models. ArXiv:1708.03395 [Cond-Mat, Physics:Math-Ph].
CaCa05
Castellani, T., & Cavagna, A. (2005) Spin-Glass Theory for Pedestrians. Journal of Statistical Mechanics: Theory and Experiment, 2005(05), P05012. DOI.
Comp90
Complexity, Entropy and the Physics of Information: The Proceedings of the 1988 Workshop on Complexity, Entropy, and the Physics of Information. (1990). Addison-Wesley Pub. Co.
Harp09a
Harper, M. (2009a) Information Geometry and Evolutionary Game Theory. ArXiv:0911.1383.
Harp09b
Harper, M. (2009b) The Replicator Equation as an Inference Dynamic.
Moor17
Moore, C. (2017) The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness. Bulletin of the EATCS.
OyTr15
Oymak, S., & Tropp, J. A.(2015) Universality laws for randomized dimension reduction, with applications. ArXiv:1511.09433 [Cs, Math, Stat].
PLRS16
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.
Shal09
Shalizi, C. R.(2009) Dynamics of Bayesian updating with dependent data and misspecified models. Electronic Journal of Statistics, 3, 1039–1074. DOI.
SiLi96
Sinervo, B., & Lively, C. M.(1996) The rock–paper–scissors game and the evolution of alternative male strategies. Nature, 380(6571), 240. DOI.
SzRi17
Székely, G. J., & Rizzo, M. L.(2017) The Energy of Data. Annual Review of Statistics and Its Application, 4(1), 447–479. DOI.
WeMZ16
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].
ZdKr16
Zdeborová, L., & Krzakala, F. (2016) Statistical physics of inference: Thresholds and algorithms. Advances in Physics, 65(5), 453–552. DOI.