This chapter introduces mathematical tools for establishing the foundations of deep learning and, more broadly, machine learning. We first introduce Glivenko-Cantelli theorem and concentration inequalities, which characterizes the convergence of an empirical process in the context of convergence in probability. The Glivenko-Cantelli theorem and concentration inequalities also inspire the concept of the sample complexity required to ensure a desirable level of generalizability on unseen data. We then discuss the Probably Approximately Correct (PAC) learning framework, which characterizes learning algorithms that can learn a target concept in an appropriate amount of time given a sufficiently high sample complexity. The PAC framework has become the foundation of statistical learning. Usually, PAC is categorized in the ‘frequentist’ sense, which suffers from significant deficiency in studying stochastic algorithms. To address this issue, the PAC-Bayes framework is also discussed, which integrates the PAC framework with Bayesian methods to characterize randomness.