Seminar in Artificial Intelligence - Theoretical Aspects of Machine Learning

Motivation: The data streaming model deals with processing large data sets that arrive continuously over time, where storing all data is impractical. Algorithms in this model make decisions using limited memory, typically by summarizing or sampling data on-the-fly, making it ideal for real-time applications such as network traffic analysis or sensor data processing.

Overview:

In the context of big data and real-time processing, it is essential to efficiently compute statistics on data streams. One important problem is estimating the number of distinct elements in a data stream, known as the Distinct Elements Problem. This problem has applications in fields such as network traffic monitoring, database management, and large-scale data analysis. This project aims to explore recent contributions in this area and their applications in various real-world scenarios. The goal of this project is to understand and explore space-efficient algorithms for dealing with streaming data, focusing on recent advancements, particularly the contributions of Sourav Chakraborty, Kuldeep Meel, and N.V. Vinodchandran.

Papers and Topics:

This project will focus on recent advances in algorithms for distinct elements in data streams and streaming model optimization. Key papers include:

1. Distinct Elements in Streams: An Algorithm for the (Text) Book. ESA 2022.
2. Estimating the Size of Union of Sets in Streaming Models. PODS 2021.
3. On the Feasibility of Forgetting in Data Streams. PACCOD 2024

Motivation: Discrete diffusion generates text tokens or atomic species through repeated denoising steps. At one such step, the model predicts a distribution for each position. Dang and Ermon and OxiGen use finite-state machines to couple these predictions so that the complete output satisfies a constraint.

This project asks a focused question: can this exact sampling analysis be extended from finite-state constraints to correctly nested brackets of two types? Nested brackets provide a simple model of nesting in JSON. The project is primarily a proof and complexity exercise, building on classical weighted parsing.

Proposed strategy:

1. State the sampling problem precisely. Fix a positive even length n and alphabet Σ = { (, ), [, ] }. For each position i, the input is a probability table p_i(a) over this alphabet. Let C_n be the correctly matched bracket strings of length n. Assume Z_n = ∑_{x ∈ Cn} ∏_i=1ⁿ p_i(x_i) > 0. The target distribution is P_n(x) = 1[x ∈ C_n] · ∏_i=1ⁿ p_i(x_i) / Z_n. This conditions one denoising step’s factorized prediction, rather than the full diffusion model’s final-output distribution.
2. Explain the existing finite-state analysis. Describe how backward probabilities of valid completions enable exact sampling for a deterministic finite automaton. Explain how OxiGen uses cumulative charge as its state. Distinguish exact weighted sampling from merely returning some valid output.
3. Prove the bracket extension. Use the grammar S → (S)S | [S]S | ε, where ε is the empty string. First prove that every valid string has a unique decomposition into its first matching bracket pair, the enclosed substring, and the remaining suffix. Derive an interval recurrence for the total weight of valid substrings. Then prove that choosing decompositions with probabilities proportional to their weights and recursively sampling the two substrings returns exactly P_n.
4. Establish the computational bounds. Show that the interval table requires O(n³) arithmetic operations and O(n²) storage. After the table is built, a direct implementation that scans possible splits needs at most O(n²) additional arithmetic operations per sampled string. State that these are arithmetic-operation bounds under exact arithmetic, not floating-point error or bit-complexity guarantees.

The compulsory deliverable is the bracket sampler’s correctness proof, complexity analysis, and a worked example. Explain why its unambiguous decomposition matters: summing over multiple parses can bias the distribution over strings.

Choose at most one optional extension:

• Representation size: prove that a deterministic finite automaton recognizing all balanced two-type bracket strings with maximum depth d requires at least 2^d states. Compare this with the constant-size grammar. This comparison concerns constraint representations, not an automatic speed advantage on every input.
• A larger grammar: adapt the argument to a specified unambiguous nested-JSON syntax grammar, or to an unambiguous grammar in binary normal form. Keep JSON syntax and additional schema or cross-field constraints distinct.
• Crystal compositions: extend OxiGen by requiring exactly r atoms of one chosen element, with 0 ≤ r ≤ n. Track state (c, k), for cumulative charge and element count. Derive the recurrence, prove exact sampling when the constrained mass is positive, and bound the additional state-space factor by r+1. Use a finite species vocabulary with bounded integer oxidation states.

Implementation is optional: verify the normalizing constant by enumerating a tiny example. Neither model training nor a benchmark suite is required. Present the extension as an adaptation of established inference methods; research novelty would require a separate literature assessment.

Papers and topics:

• Dang, M., & Ermon, S. (2026). Constrained Decoding for Diffusion Language Models via Efficient Inference over Finite Automata. Focus: Sections 3–4.2 and Appendix A.
• John, D., Jelfs, K. E., Ganose, A. M., & Giunchiglia, E. (2026). OxiGen: Oxidation-State-Aware Crystal Generation. Focus: Section 4.3 and Appendix A.
• Goodman, J. (1999). Semiring Parsing. Computational Linguistics, 25(4), 573–606. Focus: the CKY inside recurrence in Section 1.
• Mündler, N., Dekoninck, J., & Vechev, M. (2026). Constrained Decoding of Diffusion LLMs with Context-Free Grammars. ICLR. Related work on grammar-based feasibility checks; distinguish its objective from exact weighted sampling.

Motivation: The generation of discrete objects such as text, molecular graphs, and other combinatorial structures is one of the most prevalent tasks in modern machine learning.

Beyond autoregressive language models, a variety of alternative model classes and techniques are emerging to enable specialised capabilities such as parallel generation, infilling, and controllable sampling. These capabilities largely arise from how the underlying probability distributions are parametrised, rather than from the objects being generated.

Among these, discrete diffusion models are often considered particularly promising alternatives to autoregressive generation, although the term actually encompasses several distinct model classes and formulations. Other approaches, such as discrete flow matching and generative flow networks, provide alternative perspectives on discrete generation.

Expected outcome: Students should investigate several distinct classes of discrete generative models, ideally around three, with an emphasis on diversity in their underlying formulations. Autoregressive language models are also a valid choice. Generative Flow Networks are a particularly interesting, but mathematically more challenging, option.

The following questions may guide the comparison:

• Structure: What assumptions are made about the space of objects?
• Representation: How is the probability distribution parametrised or factorised?
• Training: Which quantities are learned, and what objectives are used?
• Inference: How are samples generated? Which procedures are exact, approximate, or heuristic?

A strong report should aim to analyse these models from a shared mathematical perspective, identify meaningful differences in their training objectives and inference procedures, and discuss their respective trade-offs.

More ambitious reports may develop a taxonomy of model classes or investigate formal relationships between them, such as equivalences, subsumption, or special-case relationships under explicitly stated assumptions.

Students are expected to be comfortable with probability theory.

Overview: The following resources provide background material and broader perspectives on generative modelling. They are intended as starting points rather than required reading.

• Introduction to diffusion and flow matching: Holderrieth, P., & Erives, E. (2025). An Introduction to Flow Matching and Diffusion Models. A self-contained mathematical introduction to diffusion and flow matching, primarily in continuous spaces. Accompanying MIT lecture materials are also available.
• Interactive GFlowNet introduction: GFlowNet Playground. An interactive introduction to the basic principles and learning dynamics of generative flow networks.

Papers and topics: The following papers illustrate different approaches to discrete generative modelling. Students are encouraged to explore additional literature relevant to their chosen comparison.

• Categorical diffusion: Austin, J., Johnson, D. D., Ho, J., Tarlow, D., & van den Berg, R. (2021). Structured Denoising Diffusion Models in Discrete State-Spaces. Advances in Neural Information Processing Systems (NeurIPS 2021).
• Score-based discrete diffusion: Lou, A., Meng, C., & Ermon, S. (2024). Discrete Diffusion Modeling by Estimating the Ratios of the Data Distribution. Proceedings of the 41st International Conference on Machine Learning (ICML 2024).
• Discrete flow matching: Gat, I., Remez, T., Shaul, N., Kreuk, F., Chen, R. T. Q., Synnaeve, G., Adi, Y., & Lipman, Y. (2024). Discrete Flow Matching. Advances in Neural Information Processing Systems (NeurIPS 2024).
• Generative flow networks: Bengio, Y., Lahlou, S., Deleu, T., Hu, E. J., Tiwari, M., & Bengio, E. (2023). GFlowNet Foundations. Journal of Machine Learning Research, 24(210), 1–55.
• Masked diffusion: Sahoo, S. S., Arriola, M., Schiff, Y., Gokaslan, A., Marroquin, E., Chiu, J. T., Rush, A., & Kuleshov, V. (2024). Simple and Effective Masked Diffusion Language Models. Advances in Neural Information Processing Systems (NeurIPS 2024).

Motivation: Explanations are often used to promote trust in machine learning models, but they can be misleading if they do not faithfully reflect the model’s behaviour. Verifying whether an explanation accurately describes a model’s behaviour can itself be a challenging task. A theoretical foundation for explainable AI is therefore essential to establish what explanations guarantee and when they can be computed and verified efficiently.

Papers and Topics:

• Robi Bhattacharjee, Ulrike von Luxburg. “Auditing Local Explanations is Hard.” NeurIPS 2024.

Advisor: Christoph

Motivation: Many modern datasets live on non-grid structured domains (graphs/meshes/manifolds) and/or come with continuous symmetries (e.g., E(3) in 3D geometry). Geometric deep learning seeks neural architectures that respect these structures, in particular equivariance to transformations (rotations, translations, permutations) and the ability to exploit continuous symmetry groups. Recent work shows that building these inductive biases into graph neural networks leads to models that are both more accurate and more interpretable when handling geometric data.

Papers:

• Victor Garcia Satorras, Emiel Hoogeboom, Max Welling, E(n) Equivariant Graph Neural Networks,International Conference on Machine Learning 2021
• Chaitanya K. Joshi, Cristian Bodnar, Simon V. Mathis, Taco Cohen, Pietro Liò, On the Expressive Power of Geometric Graph Neural Networks, International Conference on Machine Learning 2023

Motivation: This project studies a very small and fully self-contained special case of PAC-distillation. The starting point is the PAC-distillation framework introduced in Towards a theory of model distillation, which formalizes the task of converting a function given in one representation into an approximately equivalent function in another representation. In the paper, juntas are used as a warm-up case before more difficult results. In this project, students consider the easiest nontrivial variant: a neural network over {0,1}^d that computes a 1-junta, i.e. a Boolean function depending on exactly one input coordinate. The goal is to prove a simplified exact theorem: from oracle access to the teacher network, one can recover an explicit decision stump representing the same function using at most d+1 evaluations and hence obtain (ε, δ) = (0, 0)-PAC-distillation with 0 random samples.

Prerequisites: Basic PAC-learning in the theoretical computer science sense. Students should be familiar with the notions of concept class, hypothesis class, distribution-free learning, generalization error, and the parameters ε and δ. They should also understand the difference between learning from labeled samples and distillation, where the source function itself is available to the algorithm in addition to sampled inputs.

Methodology:

1. Read the definitions of PAC-learning and PAC-distillation, and restate them in your own notation for Boolean functions f : {0,1}^d → {0,1}. Make explicit that in PAC-learning the learner only receives sampled labeled examples, whereas in PAC-distillation the algorithm additionally receives the source function f itself.
2. Introduce the source and target classes for the simplified project. The source class should be neural networks that compute 1-juntas. The target class should be explicit 1-juntas, represented as a pair (i, h), where i ∈ {1, …, d} is the relevant coordinate and h : {0,1} → {0,1}.
3. State the exact target theorem to be proved: for every neural network f computing a 1-junta, there exists a deterministic distillation algorithm that outputs an explicit 1-junta g such that g(x) = f(x) for all x ∈ {0,1}^d, using at most d+1 evaluations of the teacher and no random samples. Conclude that this gives (0, 0)-PAC-distillation.
4. Present the distillation algorithm explicitly. Query the teacher on the all-zero input 0^d, and on each unit vector e₁, …, e_d. Show how these values identify either the unique relevant coordinate or the constant-function case.
5. Prove correctness formally. Split the proof into the constant and non-constant cases. In the non-constant case, prove that if f(x) = h(x_i), then all queries e_j with j ≠ i return h(0), while the query e_i returns h(1). Deduce that the algorithm recovers the correct coordinate and truth table exactly.
6. Reformulate the result in PAC-distillation language. Define error_f,D(g) = Pr_x∼D[g(x) ≠ f(x)], and prove that for every distribution D, the constructed hypothesis satisfies error_f,D(g) = 0.
7. Explain in the written report and presentation why this example is conceptually useful. The main point is not the difficulty of the proof, but the separation between learning and distillation: once the teacher representation is available, recovering an equivalent symbolic model can be much easier than learning the same function from labeled data alone.

Papers and topics:

• E. Boix-Adsera. “Towards a theory of model distillation.” arXiv, 2024.
• L. G. Valiant. “A Theory of the Learnable.” Communications of the ACM, 27(11), 1984.
• M. Kearns and U. Vazirani. “An Introduction to Computational Learning Theory.” MIT Press, 1994.
• S. Shalev-Shwartz and S. Ben-David. “Understanding Machine Learning: From Theory to Algorithms.” Cambridge University Press, 2014.

Motivation: Message passing graph neural networks are at most as expressive as the 1-Weisfeiler-Leman test (1-WL), which fails on simple graphs such as regular graphs and cannot count cycles. Higher-order variants like k-WL are more expressive but scale poorly with the size of the graph. Paths are one of the simplest substructures of a graph, and aggregating the paths starting at each node, together with shortest path distances, gives a family of tests called Path-WL. Path-WL is strictly more expressive than 1-WL, can count cycles, and is incomparable to the k-WL hierarchy, while its cost depends on the maximum degree rather than the number of nodes, which makes it practical on sparse graphs such as molecules. The goal is to understand, summarise, and explain how Path-WL works, why paths with distance information go beyond 1-WL, and how shortest path distances allow Path-WL to count cycles of arbitrary length.

Overview:

• Weisfeiler-Leman and GNNs (Huang and Villar. “A short tutorial on the Weisfeiler-Lehman test and its variants.” ICASSP 2021) (arXiv)
• expressive power of message passing (Xu, Hu, Leskovec, and Jegelka. “How powerful are graph neural networks?” ICLR 2019)

Papers and topics:

• Path-WL and its expressive power (Graziani, Drucks, Jogl, Bianchini, Scarselli, and Gärtner. “The expressive power of path-based graph neural networks.” ICML 2024) (link)
• path neural networks (Michel, Nikolentzos, Lutzeyer, and Vazirgiannis. “Path neural networks: expressive and accurate graph neural networks.” ICML 2023)
• shortest path message passing (Abboud, Dimitrov, and Ceylan. “Shortest path networks for graph property prediction.” LoG 2022)
• counting substructures (Chen, Chen, Villar, and Bruna. “Can graph neural networks count substructures?” NeurIPS 2020)

Motivation: Message passing graph neural networks are at most as expressive as the 1-Weisfeiler-Leman test and cannot distinguish even simple pairs of planar graphs, a class that includes most molecules. Planar graph isomorphism, however, can be solved efficiently by classical algorithms that decompose a graph into its biconnected and triconnected components. PlanE turns such an algorithm into a neural architecture that is complete on planar graphs, using the Block-Cut tree and the SPQR tree of the input graph. The goal is to understand, summarise, and explain how PlanE leverages the SPQR decomposition.

Overview:

• Weisfeiler-Leman and GNNs (Huang and Villar. “A short tutorial on the Weisfeiler-Lehman test and its variants.” ICASSP 2021) (arXiv)
• SPQR trees (Gutwenger and Mutzel. “A linear time implementation of SPQR-trees.” Graph Drawing 2000)

Papers and topics:

• SPQR decomposition in PlanE (Dimitrov, Zhao, Abboud, and Ceylan. “PlanE: Representation Learning over Planar Graphs.” NeurIPS 2023) (link)
• classical planar isomorphism (Kukluk, Holder, and Cook. “Algorithm and experiments in testing planar graphs for isomorphism.” Journal of Graph Algorithms and Applications 2004)
• outerplanar graphs (Bause, et al. “Maximally expressive GNNs for outerplanar graphs.” NeurIPS 2023 Workshop on New Frontiers in Graph Learning)
• Weisfeiler-Leman on planar graphs (Kiefer, Ponomarenko, and Schweitzer. “The Weisfeiler-Leman dimension of planar graphs is at most 3.” LICS 2017) (arXiv)

Motivation: Quantization replaces a model’s weights with values from a small, fixed set, so that each weight can be stored using fewer bits. For example, a weight of 0.37 might be replaced by 0.25 or 0.50. This reduces storage but can change the model’s predictions.

This project studies QuIP, a quantization method that uses information about the data. The main question is: when does accounting for feature correlations reduce the prediction error caused by quantization? The core project concerns linear regression; logistic regression and a one-layer ReLU model are optional extensions.

Proposed strategy: Start by understanding three methods:

• Nearest rounding: replace each weight independently with the closest allowed value. In the example above, 0.37 becomes 0.25.
• Stochastic rounding: randomly choose one of the two neighbouring values, with probabilities that preserve the original weight on average. Here, choose 0.25 with probability 52% and 0.50 with probability 48%.
• LDLQ: QuIP’s data-dependent rounding method. It rounds weights one at a time and uses feature correlations to adjust later weights, compensating for the prediction changes introduced by earlier rounding. The corrections are computed using an LDL matrix factorization. LDLQ is the main component studied in this project.

Then carry out three tasks:

1. Connect quantization to regression error. Fit an ordinary least-squares model with weights w. Define L(v) = ‖Xv − y‖₂² / n and H = X^⊤X / n, where X contains the inputs and n is the number of examples. Prove L(q) − L(w) = (q − w)^⊤ H (q − w), where q contains the quantized weights. This connects QuIP’s objective directly to the increase in training MSE.
2. Reproduce an error guarantee. Study Sections 3.1–3.2 and reproduce LDLQ’s nearest-rounding error bound, initially for a grid without range limits. Work through a two-feature example to understand how correlation affects the guarantee.
3. Test the theory. Compare the three methods on small synthetic regression datasets, varying feature correlations and precision. Use roughly 1,000 examples and 10–30 features. Compare theoretical bounds with observed training-error increases and measure held-out MSE separately. For finite 2-, 4-, and 8-bit grids, investigate clipping—forcing values outside the allowed range to an endpoint—using Section 5.2.

Possible extensions:

• Logistic regression: quantize the weights of f_w(x) = σ(w^⊤x), where σ maps the score to a probability. Derive bounds on changes in predicted probabilities and conditions under which predicted labels remain unchanged.
• One-layer ReLU model: quantize f_W(x) = ReLU(Wx), where ReLU replaces negative outputs with zero. Use the fact that ReLU cannot increase distances to turn the linear reconstruction bound into an output-error guarantee. Test a layer with a few neurons.

Papers and topics:

• Chee, J., Cai, Y., Kuleshov, V., & De Sa, C. (2023). QuIP: 2-Bit Quantization of Large Language Models With Guarantees. NeurIPS. Main reading: Sections 3.1–3.2; finite-grid discussion: Section 5.2.

Motivation: Our environment suffers from the enormous energy consumed in data centers around the world for training and applying machine learning algorithms. Approaches to more resource friendly machine learning include low-precision computations, low-rank approximations, sparsification, and mixture-of-experts.

Papers and topics:

Potential topics include guarantees for approximate representations (Johnson-Lindenstrauss or Nyström), Expectation-Complete Representations, low rank computations (post-processing or training), and quantisation.

• Ludziejewski, Krajewski, Adamczewski, Pióro, Krutul, Antoniak, Ciebiera, Król, Odrzygóźdź, Sankowski, Cygan, and Jaszczur. Scaling Laws for Fine-Grained Mixture of Experts
• Saha, Sagan, Srivastava, Goldsmith, and Pilanci. Compressing Large Language Models using Low Rank and Low Precision Decomposition. NeurIPS 2024
• Savostianova, Zangrando, Ceruti, and Tudisco. Robust low-rank training via approximate orthonormal constraints. NeurIPS 2023
• Oglic and Gärtner. Nyström Method with Kernel K-means++ Samples as Landmarks. ICML 2017

Motivation:

Graphs can be used to model many areas of interest: e.g. molecules, geographical maps, spread of diseases, or communication networks. They can be used to model physical systems and solve partial differential equations. Even images and text can be seen as a special case of graphs. Learning on graphs nowadays is mostly done using message passing graph neural networks (MPNNs). MPNNs are connected to the classical Weisfeiler Leman graph isomorphism algorithm (WL) by the fact that they will always compute identical representations for two graphs which cannot be distinguished by WL. Current theoretical and practical work focuses hence on more expressive graph neural networks which can distinguish more graph pairs.

However, learning (particularly with neural networks) is based on similarities between representations. We will delve into recent methods which combine Weisfeiler Leman based graph representations with ideas from optimal transport. Ideally, we will investigate options to transfer some of the ideas to analyze similarities that MPNNs compute.

Papers of Interest:

Note: For very long papers we do not expect you to read the entire appendix.

• Fang, Huang, Su, and Kasai (2023) - Wasserstein Graph Distance Based on L1–Approximated Tree Edit Distance between Weisfeiler–Lehman Subtrees. AAAI
• Kriege, Giscard, Wilson (2016) - On Valid Optimal Assignment Kernels and Applications to Graph Classification. NeurIPS
• Schulz, Horvath, Welke, Wrobel (2022) - A generalized Weisfeiler-Lehman graph kernel
• Nikolentzos, Vazirgiannis (2023) - Graph Alignment Kernels using Weisfeiler and Leman Hierarchies
• Chen, Lim, Memoli, Wan, Wang (2022) - Weisfeiler-Lehman Meets Gromov-Wasserstein
• Togninalli, Ghisu, Llinares-López, Rieck, Borgwardt (2019) - Wasserstein Weisfeiler-Lehman Graph Kernels