• ES Español
• EN English

3.7. Mathematical Foundations of Data Science (FDS)

This area covers the mathematical theory underlying modern data science and machine learning: statistical learning theory, optimization, information theory, dimensionality reduction, and the mathematics of deep learning, all essential for Computing students across AI, data science, and software engineering.

Knowledge Area (KA)	CS Core	KA Core
3.7.1 Statistical Learning Theory	Elective
3.7.2 Optimization for Machine Learning	Elective
3.7.3 Information Theory	Elective
3.7.4 Dimensionality Reduction	Elective
3.7.5 Mathematical Foundations of Deep Learning	Elective

3.7.1. FDS/Statistical Learning Theory ↑ Back to top

PAC learning framework, VC dimension, Rademacher complexity, generalization bounds, and the bias-variance trade-off.
Topics:
Core

• PAC learning framework: sample complexity, hypothesis classes, and learnability
• VC dimension: definition, examples, and the fundamental theorem of learning
• Rademacher complexity and uniform convergence bounds
• Bias-variance decomposition and the double descent phenomenon
• Regularization: Tikhonov regularization and structural risk minimization

Learning Outcomes:
Core:

1. State the PAC learning definition and determine whether a hypothesis class is PAC-learnable [Familiarity]
2. Compute the VC dimension of standard hypothesis classes and derive sample complexity bounds [Usage]
3. Analyze generalization error using Rademacher complexity and explain the double descent phenomenon [Assessment]

3.7.2. FDS/Optimization for Machine Learning ↑ Back to top

Convex optimization theory, SGD and its variants, adaptive methods, and non-convex optimization landscapes for training learning models.
Topics:
Core

• Convexity, strong convexity, and Fenchel duality in optimization
• Stochastic gradient descent: convergence rates for convex and non-convex objectives
• Adaptive gradient methods: AdaGrad, RMSProp, and Adam
• Non-convex optimization: saddle points, local minima, and loss landscape geometry of neural networks
• Proximal gradient methods and coordinate descent for structured problems

Learning Outcomes:
Core:

1. Explain the convergence guarantees of SGD for smooth convex functions and identify the role of the learning rate [Familiarity]
2. Apply Adam and proximal gradient methods to train regularized machine learning models [Usage]
3. Analyze the loss landscape of an overparameterized network and explain why SGD finds good minima [Assessment]

3.7.3. FDS/Information Theory ↑ Back to top

Shannon entropy, mutual information, channel capacity, rate-distortion theory, and applications to machine learning and data compression in computing.
Topics:
Core

• Shannon entropy, joint and conditional entropy, and the chain rule
• Mutual information, KL divergence, and the data processing inequality
• Channel capacity: Shannon's noisy channel coding theorem and the binary symmetric channel
• Rate-distortion theory and the trade-off between compression and fidelity
• Information-theoretic foundations of ML: MDL, variational inference (ELBO), and the information bottleneck

Learning Outcomes:
Core:

1. Compute Shannon entropy and mutual information for discrete distributions and interpret their meaning [Familiarity]
2. Apply Shannon's channel capacity theorem to determine the maximum reliable transmission rate [Usage]
3. Analyze a learning algorithm using the information bottleneck principle and relate compression to generalization [Assessment]

3.7.4. FDS/Dimensionality Reduction ↑ Back to top

Linear and nonlinear dimensionality reduction: PCA, random projections, manifold learning, and modern methods (t-SNE, UMAP), widely used in data science and visualization.
Topics:
Core

• PCA: singular value decomposition, explained variance, and optimal low-rank approximation
• Johnson-Lindenstrauss lemma and random projections for dimensionality reduction
• Manifold learning: Isomap, locally linear embedding (LLE), and spectral embedding
• Modern nonlinear methods: t-SNE and UMAP; theory, parameters, and limitations
• Autoencoders and variational autoencoders (VAEs) as nonlinear dimensionality reduction

Learning Outcomes:
Core:

1. Explain the Johnson-Lindenstrauss lemma and justify why random projections preserve distances [Familiarity]
2. Apply PCA and t-SNE to high-dimensional data and interpret the resulting low-dimensional embeddings [Usage]
3. Compare linear and nonlinear dimensionality reduction methods with respect to geometry preservation and computational cost [Assessment]

3.7.5. FDS/Mathematical Foundations of Deep Learning ↑ Back to top

Universal approximation, neural tangent kernel, implicit bias of SGD, overparameterization, and geometric deep learning — the frontier mathematics behind modern AI.
Topics:
Core

• Universal approximation theorems: width and depth trade-offs for ReLU networks
• Neural tangent kernel (NTK) and the infinite-width limit of neural networks
• Implicit regularization and implicit bias of SGD toward minimum-norm solutions
• Benign overfitting and double descent in overparameterized models
• Geometric deep learning: equivariance, group symmetry, and graph neural networks

Learning Outcomes:
Core:

1. State the universal approximation theorem and identify its assumptions and limitations [Familiarity]
2. Explain the neural tangent kernel and its role in understanding training dynamics of wide networks [Usage]
3. Analyze the implicit bias of gradient descent and relate it to generalization in overparameterized regimes [Assessment]