96764 - Mathematics for Complex Systems

Learning outcomes

At the end of the course the student : - has in-depth knowledge of the possible applications of complex system's theory to the study of statistical inference and machine learning problems; - is able to introduce a stochastic generative model, set up an inference procedure to extract information from data and discuss process complexity and theoretical limits of the inference/learning performance from the perspective of the theory of complex systems and phase transitions.

Course contents

• Review of Probability Theory;
• Statistical Mechanics approach to Complex Systems, with examples based on Ising models;
• From Statistical Mechanics to Bayesian Inference: Mapping between physical systems and computational problems;
• Statics and Dynamics of Complex Systems, with applications to physical and machine learning systems (e.g., image reconstruction)
• Bayesian Inference on Graphs (e.g., community detection)
• From Bayesian Inference to Optimization in Machine Learning problems (e.g., linear regression)

Tools

By the end of the course, the student will have learned mainly to use the following mathematical methods and algorithms:

• Replica Theory and Cavity Method;
• Dynamical Mean Field Theory and Online Dynamics;
• Belief Propagation;
• Monte Carlo Methods and Markov Chains.

Readings/Bibliography

Main references:

• M.Mézard, A.Montanari - Information, Physics, and Computation - Oxford University Press, USA
  (2009);
• Nishimori, H.: Statistical Physics of Spin Glasses and Information processing. An Introduction. Oxford
  Science Publications 2001;
• Coolen, Kuhn, Sollich, Theory of Neural InformationProcessing Systems, Oxford University Press;
• Engel, A., Van Den Broeck, C., Statistical Mechanics of Learning, Cambridge University Press.

Suggested reading:

• Mark Newman - Networks_ An Introduction - Oxford University Press (2010);
• Decelle, A., Krzakala, F., Moore, C., & Zdeborová, L. (2011). Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications. Physical Review E, 84(6), 066106;
• Zdeborová, L., Krzakala, F. (2016). Statistical physics of inference: Thresholds and algorithms. Advances in Physics, 65(5), 453-552;
• Gardner, E., and Derrida, B.: Optimal storage properties of neural network models. J. Phys. A: Math. Gen. 21, 271-284 (1988).

Teaching methods

Frontal Lectures.

Assessment methods

The exam consists of an oral interview in order to verify the knowledge of the arguments listed in the Course Contents and the skills achieved as:

• Advanced Concepts of Applied Statistical Mechanics and Random Graph Theory;
• Ability of reading an optimization, inference, machine learning problem from the statistical mechanics perspective, designing both mathematical structure and possible solutions;
• Ability of performing a numerical experiment, running the studied algorithms on both synthetic and real data;
• Ability of deepening the analyzed topics through the most recent results in the literature.

Teaching tools

The teaching tools will be available on the Virtuale platform.

Office hours

See the website of Federica Gerace