Author: AI Research Agent
Date: July 2026
Scope: Mathematical bedrock, architecture theory, and generative models for modern deep learning
Seminal Reference: L. Valiant, "A Theory of the Learnable," Communications of the ACM, 1984.
The Probably Approximately Correct (PAC) framework formalizes the question: Given a hypothesis class H, how many training examples m are needed to guarantee that with high probability, a learned hypothesis h in H has low error?
Definition: A concept class C is PAC-learnable if there exists an algorithm A and a polynomial function m such that for any epsilon > 0, delta > 0, and any distribution D over inputs, given m i.i.d. samples, A outputs h in H satisfying P[R(h) <= epsilon] >= 1 - delta, where R(h) = E[1{h(x) != c(x)}] is the true risk.
Sample Complexity Bounds: For finite hypothesis classes: m >= (1/epsilon)(ln|H| + ln(1/delta))
Agnostic PAC Learning (Haussler, 1992): Removes the realizability assumption; learner competes with best hypothesis in H.
Key Result: PAC learning bridges statistical generalization and computational tractability.
Seminal References: V. Vapnik and A. Chervonenkis, 1971. V. Vapnik, The Nature of Statistical Learning Theory, Springer, 1995.
VC dimension measures hypothesis class capacity by the largest set of points that can be shattered (all 2^n labelings realized).
Sample Complexity via VC Dimension: m >= (1/epsilon)(4 log2(2/delta) + 8 VCdim(H) log2(13/epsilon))
Key Results:
- d-dimensional linear classifiers: VCdim = d+1
- NNs with W params, L layers: O(W L log W) (Bartlett et al., 2019)
- Often loose for overparameterized models
Open Debate: Modern NNs generalize despite massive VC dimension, motivating margin and NTK-based theories.
Seminal Reference: P. Bartlett and S. Mendelson, JMLR, 2002.
Data-dependent complexity measure yielding tighter bounds than VC dimension.
Definition: Rademacher(F) = E_sigma[ sup_{f in F} (1/m) sum sigma_i f(x_i) ], sigma_i ~ Uniform({+-1})
Generalization Bound: R(f) <= R_emp(f) + Rademacher(F) + sqrt(log(1/delta)/(2m))
Key Results:
- L2-bounded linear classifiers: Rademacher <= B||X||_F/m
- ReLU nets with spectral norm: O(B^L prod ||W_i||_2 / sqrt(m))
- Captures the margin theory exploited by NNs
Seminal Reference: A. Jacot, F. Gabriel, C. Hongler, NeurIPS 2018. arXiv:1806.07572.
Core Idea: In the infinite-width limit, an NN trained by gradient descent evolves as a linear model under a fixed kernel -- the Neural Tangent Kernel (NTK).
NTK Definition: Theta_t(x,x') = grad f_{theta(t)}(x) . grad f_{theta(t)}(x')
Infinite-Width Limit:
1. Theta_t -> Theta_infty (deterministic kernel)
2. Theta_t constant during training (lazy training regime)
3. df_t/dt = -Theta_infty(f_t - y)
Solution (MSE): f_t(x) = Theta_infty(x,X) Theta_infty(X,X)^{-1} (I - exp(-eta Theta_infty(X,X) t)) y
Key Results:
- Limiting NTK for ReLU on spheres is positive-definite
- Wide NNs behave like kernel methods
- Generalization governed by kernel eigendecomposition
Subsequent Work:
- Convolutional NTK (Arora et al., 2019, arXiv:1904.11955)
- Deep NTK beyond infinite width (Seleznova and Kutyniok, 2022, arXiv:2202.00553)
- NTK divergence in classification (Yu et al., 2025, arXiv:2504.11130, ICLR 2025)
References: Chizat et al. (2019, arXiv:1812.07956). Yang and Hu (2021, arXiv:2011.14522).
Lazy Training (NTK): Features barely change; effective model is linear.
Feature Learning (muP): Features evolve substantially; representation learning.
| Aspect | NTK/Lazy Regime | Feature Learning |
|---|---|---|
| Feature change | O(1/sqrt(width)) | Theta(1) |
| Effective model | Linear (kernel) | Nonlinear |
| Width scaling | Standard (1/sqrt(w)) | muP scaling |
| Example | Very wide FC nets | Modern LLMs |
Open Debate: Transition between regimes. Tensor Programs framework (Yang, 2019-2023).
Shannon Entropy: C. Shannon, 1948. Info-theoretic bounds (Russo and Zou, 2016; Xu and Raginsky, 2017).
Kolmogorov Complexity / MDL: A. Kolmogorov, 1965. MDL Principle (Rissanen, 1978).
Variational Inference (ELBO): Kingma and Welling, ICLR 2014, arXiv:1312.6114.
- log p(x) >= E_{z~q}[log p(x|z)] - KL(q(z|x) || p(z))
- KL term = information cost of latent (rate-distortion)
Information Bottleneck (Tishby et al., 1999): Debated: holds for saturating activations but not ReLU.
Monge Problem (1781): min_T int c(x, T(x)) dmu(x)
Kantorovich Problem (1942): min_{pi} int c(x,y) dpi(x,y)
Wasserstein Metrics: W_p(mu,nu) = (inf_{pi} int ||x-y||^p dpi)^{1/p}
Kantorovich Duality: W_1 = sup_{f in Lip_1} (int f dmu - int f dnu)
Key ML Applications:
- Wasserstein GANs (Arjovsky et al., 2017, arXiv:1701.07875)
- Sinkhorn (Cuturi, 2013)
- Diffusion PF-ODE as Wasserstein gradient flow of KL
Reference: C. Villani, Optimal Transport: Old and New, Springer, 2009.
Seminal Reference: A. Vaswani et al., "Attention Is All You Need," NeurIPS 2017. arXiv:1706.03762.
Core Mechanism -- Scaled Dot-Product Attention: Attention(Q,K,V) = softmax(QK^T / sqrt(d_k)) V
Key Theoretical Properties:
Permutation Equivariance (without position encodings)
Universal Approximation (Yun et al., 2020):
- arXiv:1912.10077, ICLR 2020
- Transformers with poly(1/epsilon) layers and poly(n,d) width approximate any continuous seq2seq function on compact domains.
- Uses contextual mapping to encode token identity and position.
Chain-of-Thought Expressivity:
- Merrill and Sabharwal (2023, arXiv:2305.02296): Constant-depth transformers without CoT limited to TC^0 complexity class.
- With CoT: can simulate arbitrary Turing machines (P-complete problems solvable).
- CoT adds sequential reasoning capacity beyond parallel attention.
In-Context Learning as Gradient Descent:
- Von Oswald et al. (2023, arXiv:2212.13017): Transformers implement gradient descent in their forward pass.
- Dai et al. (2023, arXiv:2212.10554): Attention as kernel regression.
Open Debates: Required depth for reasoning; attention vs. MLP contribution; RoPE theory (Su et al., 2024); induction heads (Olsson et al., 2022).
Seminal Reference (MPNNs): J. Gilmer et al., ICML 2017. arXiv:1704.01212.
Expressive Power (Xu et al., 2019): K. Xu et al., ICLR 2019. arXiv:1810.00826.
- Core Result: MPNNs at most as powerful as 1-WL test
- GIN (Graph Isomorphism Network) achieves maximal MPNN expressivity with sum aggregation
The 1-WL Test: Color refinement; multiset hashing. Cannot distinguish certain non-isomorphic graphs.
Higher-Order WL: k-WL > (k-1)-WL. k-GNNs (Morris et al., 2019, arXiv:1810.02244). O(n^k) complexity.
Recent Developments: Subgraph GNNs, Graph Transformers, Equivariant GNNs.
Open Debate: Is the WL hierarchy the right complexity measure for learning on graphs?
Structured State Spaces (S4): A. Gu, K. Goel, C. Re, ICLR 2022. arXiv:2111.00396.
SSM Equations: h'(t) = A h(t) + B x(t), y(t) = C h(t) + D x(t)
Discretized (ZOH): h_k = exp(Delta A) h_{k-1} + ...
Key Innovation: A matrix structured as HiPPO (Gu et al., 2020, arXiv:2008.07669) for long-range memory.
Mamba (Gu and Dao, 2023): arXiv:2312.00752.
- Selective SSMs: Parameters (Delta, B, C) become input-dependent (content-aware)
- Hardware-aware parallel scan in SRAM
- Simplified architecture: No attention + no MLP blocks
- 5x higher throughput vs. Transformers, linear scaling in sequence length
- Mamba-3B outperforms same-size Transformers
Connections: Recurrent mode = Linear RNNs. Conv mode (input-independent) = IIR filters.
Open Debates:
- Can SSMs match Transformers on in-context learning? (Ren et al., 2024, arXiv:2410.03810: limitations on COPY and CoT)
- Sufficiency of linear dynamics for compositional generalization
- Mamba-2: State space duality bridging SSM and attention
Telgarsky (2016): arXiv:1602.04485, COLT 2016. Exponential separation: depth-k with O(k) params vs. depth-2 needs 2^{O(k)} units (sawtooth construction).
Eldan-Shamir (2016): arXiv:1512.03965, COLT 2016. Radial functions in R^d: depth-3 with poly(d) width vs. depth-2 needs exp(Omega(d)).
Modern: Depth separation for Transformers (Hahn, 2020; Sanford et al., 2024).
Open Debate: Do these results transfer to practical tasks or remain worst-case artifacts?
Score Matching (Hyvarinen, 2005): A. Hyvarinen, JMLR, 2005. Minimizes E[||s_theta(x) - grad log p_data(x)||^2], avoiding the partition function.
Denoising Score Matching (Vincent, 2011): P. Vincent, Neural Computation, 2011. Estimates score of perturbed distribution.
NCSN (Song and Ermon, 2019): NeurIPS 2019. arXiv:1907.05600. Score network conditioned on noise level; annealed Langevin dynamics.
DDPM (Ho, Jain and Abbeel, 2020): NeurIPS 2020. arXiv:2006.11239.
- Forward: q(x_t|x_{t-1}) = N(x_t; sqrt(1-beta_t) x_{t-1}, beta_t I)
- Marginal: q(x_t|x_0) = N(x_t; sqrt(alpha_bar) x_0, (1-alpha_bar) I)
- Training: L = E[ ||epsilon - epsilon_theta(sqrt(alpha_bar)x_0 + sqrt(1-alpha_bar)epsilon, t)||^2 ]
Score-Based SDEs (Song et al., 2020): ICLR 2021. arXiv:2011.13456.
- Forward SDE: dx = f dt + g dw
- Reverse SDE: dx = [f - g^2 s_theta] dt + g dw_bar
- Probability Flow ODE: dx = [f - (1/2)g^2 s_theta] dt
DDIM (Song, Meng and Ermon, 2021): arXiv:2010.02502, ICLR 2021. Non-Markovian, deterministic generation, step skipping.
Classifier-Free Guidance (Ho and Salimans, 2022): arXiv:2207.12598.
- epsilon_hat(x_t,c) = epsilon(x_t,empty) + w(epsilon(x_t,c) - epsilon(x_t,empty))
Reference: Y. Lipman et al., ICLR 2023. arXiv:2210.02747.
Core Idea: Learn velocity field v_t(x) transporting prior p_0 to data p_1.
Conditional Flow Matching: L_CFM = E[ ||v_theta(x_t,t) - (x_1 - x_0)||^2 ] over OT conditional paths.
Rectified Flows (Liu et al., 2023): arXiv:2202.00212, NeurIPS 2023. Repeated reflow straightens trajectories for 1-step generation.
Relationship to Diffusion: Diffusion = specific probability path (VP/VE SDE). Flow matching generalizes to any differentiable path. PF-ODE is a specific flow instance.
Reference: Y. Song et al., ICML 2023. arXiv:2303.01469.
Core Idea: Learn f_theta(x_t,t) mapping any point on diffusion trajectory directly to x_0.
Self-Consistency: f_theta(x_t,t) = f_theta(x_{t'},t') for all t,t'
Sampling: Single step or few-step refinement.
Formulation: p_theta(x) = e^{-E_theta(x)} / Z_theta (Z_theta intractable)
Langevin Dynamics: x_{t+1} = x_t - (epsilon/2) grad E_theta(x_t) + sqrt(epsilon) z_t
Contrastive Divergence (Hinton, 2002): grad L ~ E[grad E(x+)] - E[grad E(x-)]
Score Matching vs. NCE: Score matching avoids partition function. NCE (Gutmann and Hyvarinen, 2010) distinguishes data from noise.
Open Debate: EBMs largely superseded by diffusion models for generation.
References: Rezende and Mohamed (2015, arXiv:1505.05770). Dinh et al. (2017, arXiv:1605.08803, Real NVP). Kingma and Dhariwal (2018, Glow). Chen et al. (2018, arXiv:1806.07366, Neural ODEs).
Change of Variables: p_X(x) = p_Z(f^{-1}(x)) |det J_{f^{-1}}(x)|
Limitations: Invertibility constraint limits expressivity; competition from diffusion models.
Unified View:
| Concept | Discrete (DDPM) | Continuous (SDE) | Score-Based |
|---|---|---|---|
| Forward | q(x_t | x_{t-1}) | dx = f dt + g dw |
| Reverse | p_theta(x_{t-1} | x_t) | dx = [f - g^2 s_theta] dt + g dw_bar |
| Learned | epsilon_theta | s_theta | Score |
| Training | epsilon - epsilon_theta |
Equivalence: epsilon_theta = -sigma_t * s_theta (reparameterization)
Autoregressive Modeling: p(x_1,...,x_n) = prod p(x_i | x_{<i})
Scaling Laws (Kaplan et al., 2020): arXiv:2001.08361. L(N,D) = A/N^alpha + B/D^beta + C.
Chinchilla Scaling (Hoffmann et al., 2022): arXiv:2203.15556, NeurIPS 2022. Optimal: N ~ C^{0.5}, D ~ C^{0.5}.
Theoretical Understanding: Purely empirical; no first-principles derivation.
Open Debates: Will scaling laws break? Are emergent abilities real (Wei et al., 2022 vs. Schaeffer et al., 2023)? Dataset quality vs. quantity.
The Dual Nature of Learning: PAC theory + VC dimension formalize learning as statistical inference; NTK shows NNs as kernel methods; yet feature learning regimes demonstrate true representation acquisition.
The Expressivity-Learnability Trade-off: Depth-separation results show deeper nets are more expressive; PAC theory shows complex classes need more data. The success of deep learning suggests that natural functions are compressible by deep architectures.
Information and Geometry: Optimal transport provides a geometric framework for comparing distributions; information theory (ELBO, rate-distortion) provides a complementary view. The Wasserstein gradient flow connects both.
From Architecture to Intelligence:
- Transformers: The only architecture shown to scale reliably to AGI-relevant benchmarks.
- SSMs: Challenge the assumption that attention is necessary, suggesting state is fundamental.
- NTK debate: Whether NNs are just kernel methods or truly learn representations.
Generative Models as World Models: Diffusion models learn the score of the data distribution -- the gradient of log-likelihood. Recent work suggests they build internal representations of latent structure (causal variables, object boundaries) useful beyond generation.
Open Frontier:
- Mechanistic interpretability: Reverse-engineering learned algorithms inside NNs.
- Unified scaling theory: Why scaling works.
- Cross-architecture expressivity limits.
- The no-free-lunch of neural architectures.
| Paper | Year | Venue / arXiv |
|---|---|---|
| Valiant -- PAC Learning | 1984 | CACM |
| Vapnik and Chervonenkis -- VC Dimension | 1971 | Theory Prob. App. |
| Bartlett and Mendelson -- Rademacher Complexities | 2002 | JMLR |
| Jacot et al. -- Neural Tangent Kernel | 2018 | arXiv:1806.07572 / NeurIPS |
| Chizat et al. -- Lazy Training | 2019 | arXiv:1812.07956 / NeurIPS |
| Yang and Hu -- Tensor Programs / muP | 2021 | arXiv:2011.14522 / ICML |
| Kingma and Welling -- VAE / ELBO | 2014 | arXiv:1312.6114 / ICLR |
| Villani -- Optimal Transport (book) | 2009 | Springer |
| Arjovsky et al. -- Wasserstein GAN | 2017 | arXiv:1701.07875 / ICML |
| Arora et al. -- Convolutional NTK | 2019 | arXiv:1904.11955 / NeurIPS |
| Seleznova and Kutyniok -- Deep NTK | 2022 | arXiv:2202.00553 / ICML |
| Yu et al. -- NTK Divergence in Classification | 2025 | arXiv:2504.11130 / ICLR |
| Paper | Year | Venue / arXiv |
|---|---|---|
| Vaswani et al. -- Attention Is All You Need | 2017 | arXiv:1706.03762 / NeurIPS |
| Yun et al. -- Transformers Universal Approximators | 2020 | arXiv:1912.10077 / ICLR |
| Merrill and Sabharwal -- Transformer Complexity | 2023 | arXiv:2305.02296 |
| Von Oswald et al. -- Transformers Learn GD | 2023 | arXiv:2212.13017 |
| Gilmer et al. -- Neural Message Passing | 2017 | arXiv:1704.01212 / ICML |
| Xu et al. -- How Powerful Are GNNs? | 2019 | arXiv:1810.00826 / ICLR |
| Morris et al. -- k-WL GNNs | 2019 | arXiv:1810.02244 |
| Gu, Goel and Re -- S4 State Spaces | 2022 | arXiv:2111.00396 / ICLR |
| Gu and Dao -- Mamba | 2023 | arXiv:2312.00752 |
| Telgarsky -- Benefits of Depth | 2016 | arXiv:1602.04485 / COLT |
| Eldan and Shamir -- Power of Depth | 2016 | arXiv:1512.03965 / COLT |
| Ren et al. -- Mamba Limitations in CoT | 2024 | arXiv:2410.03810 |
| Paper | Year | Venue / arXiv |
|---|---|---|
| Hyvarinen -- Score Matching | 2005 | JMLR |
| Vincent -- Denoising Score Matching | 2011 | Neural Comp. |
| Song and Ermon -- NCSN | 2019 | arXiv:1907.05600 / NeurIPS |
| Ho et al. -- DDPM | 2020 | arXiv:2006.11239 / NeurIPS |
| Song et al. -- Score SDEs | 2020 | arXiv:2011.13456 / ICLR |
| Song et al. -- DDIM | 2021 | arXiv:2010.02502 / ICLR |
| Ho and Salimans -- Classifier-Free Guidance | 2022 | arXiv:2207.12598 |
| Lipman et al. -- Flow Matching | 2023 | arXiv:2210.02747 / ICLR |
| Liu et al. -- Rectified Flow | 2023 | arXiv:2202.00212 / NeurIPS |
| Song et al. -- Consistency Models | 2023 | arXiv:2303.01469 / ICML |
| Kaplan et al. -- Scaling Laws | 2020 | arXiv:2001.08361 |
| Hoffmann et al. -- Chinchilla Scaling | 2022 | arXiv:2203.15556 / NeurIPS |
| Rezende and Mohamed -- Normalizing Flows | 2015 | arXiv:1505.05770 / ICML |
| Chen et al. -- Neural ODE / CNF | 2018 | arXiv:1806.07366 / NeurIPS |
| Kingma and Dhariwal -- Glow | 2018 | NeurIPS |
This report was compiled from arxiv API queries and the author knowledge base. For the latest developments, consult arxiv cs.LG, cs.AI, cs.CL, stat.ML, and math.ST.