Teacher(s)
Language
English
> French-friendly
> French-friendly
Prerequisites
This course assumes prior knowledge of the basic concepts taught in the following courses:
LEPL1108 - Discrete Mathematics and Probability
LEPL1101 - Linear Algebra
LEPL1109 - Statistics and Data Science
LEPL1402 - Computer Science II
LEPL1108 - Discrete Mathematics and Probability
LEPL1101 - Linear Algebra
LEPL1109 - Statistics and Data Science
LEPL1402 - Computer Science II
Main themes
The course will cover various fundamental topics in machine learning and cryptography, and the associated mathematical tools.
Learning: concepts of randomness and pseudo-randomness, sampling, probabilistic algorithms (Monte Carlo, hash maps, etc.), elements of information theory, Bayesian inference, statistical foundations of machine learning.
Cryptography: security concepts, basic primitives (pseudo-random functions, cryptographic hash functions, block ciphers, etc.), elements of symmetric cryptography, elements of public-key cryptography.
Learning: concepts of randomness and pseudo-randomness, sampling, probabilistic algorithms (Monte Carlo, hash maps, etc.), elements of information theory, Bayesian inference, statistical foundations of machine learning.
Cryptography: security concepts, basic primitives (pseudo-random functions, cryptographic hash functions, block ciphers, etc.), elements of symmetric cryptography, elements of public-key cryptography.
Learning outcomes
At the end of this learning unit, the student is able to : | |
At the end of this course unit, students will be able to:
|
|
Content
The course consists of two parts.
The first part (Foundation of Machine Learning) will cover foundations of learning with the concepts of PAC-learning and VC-dimension. It will also provide an information theoretical viewpoint to inference with the introduction of the Shannon entropy, mutual information and KL divergence. It then ends with the concept of pseudo-randomness.
The first part (Foundation of Machine Learning) will cover foundations of learning with the concepts of PAC-learning and VC-dimension. It will also provide an information theoretical viewpoint to inference with the introduction of the Shannon entropy, mutual information and KL divergence. It then ends with the concept of pseudo-randomness.
The second part (Foundations of Cryptography) will cover the foundations of modern cryptography. It will introduce the fundamental cryptographic primitives, including encryption, authentication, and digital signatures. It will also highlight security modeling, the reductionist proof paradigm, and computational indistinguishability. Examples of cryptographic schemes based on discrete mathematical structures will also be discussed.
Teaching methods
The course consists of ex cathedra lectures introducing the concepts, algorithms, and their theoretical foundations, exercise sessions to practice and a project for the Machine Learning part with written and/or oral reports.
Evaluation methods
The contribution of the homework to the grade for the Machine Learning part is computed as follows. Let
HW be the homework grade (out of 20) and EX the exam grade (also out of 20). If both HW and EX are at least 10, we take 0.3 * HW + 0.7 * EX. We define the weight associated with a grade x as f(x) = min(x/20, 0.5). Thus, the weight increases linearly from 0 to 0.5 as the grade increases from 0 to 10. If EX < HW, we compute G1 = f(EX) * 0.6 * HW + (1 - f(EX)) * 1.4 * EX; if HW ≤ EX, we compute G2 = (1 - f(HW)) * 0.6 * HW + f(HW) * 1.4 * EX. In other words, the combined homework and exam grade is min(G1, G2). Bonus points are added on top of this grade, without exceeding 20.
Online resources
Bibliography
- Understanding Machine Learning, Shai Shalev-Shwartz and Shai Ben-David,
- Information Theory, Inference and Learning Algorithms, D. MacKay,
- Introduction to Modern Cryptography, J. Katz and Y. Lindell, 3rd ed.
Faculty or entity
