Probably Approximately Correct Learning and Related Topics

Probably Approximately Correct (PAC) learning is a theoretical framework that addresses the problem of learning a function from a set of samples in a way that is both probably correct and approximately correct. In simpler terms, PAC learning formalizes the conditions under which a learning algorithm can be expected to perform well on new, unseen data after being trained on a finite set of examples.
PAC learning is concerned with the feasibility of learning in a probabilistic sense. It asks whether there exists an algorithm that, given enough examples, will find a hypothesis that is approximately correct with high probability. The "probably" aspect refers to the confidence level of the algorithm, while the "approximately correct" aspect refers to the accuracy of the hypothesis.

The tutorial is scheduled for 25 August 2026, from 17:00 to 19:30, and 26 August 2026, from 9:30 to 12:00.

Confirmed Lecturers

• Pascal Germain (Département d’Informatique et de Génie Logiciel, Université Laval, Québec, Canada)
• Ata Kaban (School of Computer Science, University of Birmingham, UK)

Tutorial registration fee: 

• Early registration (until 30 June):  € 90
• Late registration (after 30 June):  € 110

   

Schedule

Contents and references

Lecture 1: PAC learning and random projections (Ata Kaban)

In the first hour we begin with the high-dimensional probability tools that underpin both PAC learning and random projections. In both contexts, we develop uniform concentration inequalities for finite classes, showing that high-probability control of the maximum deviation over a family of random quantities is the key to both statistical generalisation and geometry-preserving dimensionality reduction.
In the second hour, we extend this viewpoint to infinite classes by introducing complexity measures that replace counting arguments, such as covering numbers and Rademacher complexity. We conclude with a brief discussion of implications for learning from randomly projected data and related modern perspectives.

References

• Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, USA, 2014.
• Dasgupta and Gupta. An elementary proof of a theorem of Johnson and Lindenstrauss. Random Structures and Algorithms 22, 1, 2003.
• Huang, Z., Kabán, A. & Reeve, H. Efficient learning with projected histograms. Data Mining and Knowledge Discovery 38, 3948–4000, 2024.
• Reeve, Kaban, Bootkrajang. Heterogeneous sets in dimensionality reduction and ensemble learning. Machine Learning 113, 1683–1704, 2024.
• Kaban and Reeve. Structure discovery in PAC-learning by random projections. Machine Learning 113, 5685–5730, 2024.

Lecture 2 - PAC-Bayesian Learning (Pascal Germain)

In the first hour, I will present the foundation of PAC-Bayesian learning for classification and regression problems and show how this framework reconciles the Probably Approximately Correct (PAC) hypotheses and the Bayesian inference framework.
The second hour will give an overview of several recent usages of the PAC-Bayesian learning framework to conceive "self-certified" learning algorithms, such as applications to neural networks, domain adaptation, meta learning, and generative methods.

References

• Leblanc B., Bazinet M., D'Amours N., Drouin A., Germain P., Generalization Bounds via Meta-Learned Model Representations: PAC-Bayes and Sample Compression Hypernetworks. ICML, 2025.
• Mbacke S., Clerc F., Germain P., Statistical Guarantees for Variational Autoencoders using PAC-Bayesian Theory. NeurIPS, 2023.
• Germain P., Habrard A., Laviolette F., Morvant E., PAC-Bayes and Domain Adaptation. Neurocomputing, Volume 379, 379-397, 2020.
• Germain P., Bach F., Lacoste A., Lacoste-Julien S., PAC-Bayesian Theory Meets Bayesian Inference. NeurIPS, 2016.

For more information: team.mbc2@unict.it

Last update:  27 April 2026.