Foundations of Deep Learning Reading Group

• Tansformers: the transformer architecture, as well as (some of) the recent works on subquadratic attention mechanisms (xformers, State Space models, Hyena etc).
• Which functions can transformers learn: classes of functions that transformers can provably learn in-context.
• Graph neural networks: expressivity of graph neural networks (connections to the Weissfeiler-Lehman test), information bottlenecks in graph neural networks
• Reinforement learning: algorithmic foundations of reinforcement learning, including Markov Decision Processes and Monte Carlo Tree Search

• Wed March 6, 2.15pm in BC04, Basics of the Transformer architecture

We will talk about the basics of neural networks, introduce the transformer architecture and discuss some approaches to reducing quadratic runtime of attention mechanisms.

Reading material:

The original transformer paper.
The annotated transformer by Sasha Rush.
A great blog post by Peter Bloem on a simplified version of the transformer architecture.
A more formal treatment of transformer architecture.

Additional reading: transformers for vision.

• Wed March 13, 2.15pm in BC04, More o transformer architecture, and subquadratic attention mechanisms

We will talk about some recent approaches to reducing quadratic runtime of attention mechanisms (xformers).

Reading material:

A more formal treatment of transformer architecture.

Some xformers:

KDEFormer: approximating softmax via kernel density estimation.
HyperAttention:fast spectral approximation to the attention matrix
Polysketchformer: sketching the attention matrix.
Nyströmformer: approximating the attention matrix using the Nyström method.

• Wed March 20, 2.15pm in BC04, Subquadratic attention mechanisms through sketching

We will talk about Performer and Polysketchformer, which are approaches for approximating the attention matrix using a low rank matrix.

References:

Performer: applying Fourier features to approximate the attention matrix (see also blogpost)
HyperAttention:fast spectral approximation to the attention matrix
Polysketchformer: sketching the attention matrix.

• Wed March 27th, 2.15pm in BC04, State space models

We will talk about state space models, which attempt to match the amazing performance of transformers with alternative attention mechanisms.

Reading material:

Original state space paper: modeling long sequences with state space models
Hungry hungry hippos: an improved state space architecture for language modeling
Hyena hierarchy: replacing the attention matrix with a sequence of diagonal multiplies in time and Fourier domain.
A nice ablation study on SSMs: significant simplifications to SSM can be made without sacrificing performance.
Mamba: the most recent state space model

• Fri April 19th, 1.00pm in INJ114, Which functions are representable/learnable by a transformer, or a state space model?

We will discuss empirical studies of which functions transformers learn well and which they do not, as well as some progress towards a theoretical explanation of these phenomena.

Reading material:

Thinking like a transformer: a programming language that compiles into ransformers.
An empirical study of length generalization in transformers, with some nice formalism to explain the fundings (the RASP-L language).
An empirical study of when in-context learning emerges in transformers. Talk video.
In-context learning: an empirical study of in-context learnability of simple function classes such as linear functions and shallow neural nets. Talk video.
Linear regression can be learned in-context by a transformer: some analysis plus empirical validation.
Empirical study of in-context learning of regular languages.
Gated recurrent neural networks discover attention
Transformers are better at copying than state space models are.

• Fri May 1st, 2.15pm in BC04, Transformers can solve linear regression in context

We will talk about the ability of transformers to perform in-context learning.

Reading material:

An empirical study of when in-context learning emerges in transformers. Talk video.
In-context learning: an empirical study of in-context learnability of simple function classes such as linear functions and shallow neural nets. Talk video.
Linear regression can be learned in-context by a transformer: some analysis plus empirical validation.
Empirical study of in-context learning of regular languages.
Gated recurrent neural networks discover attention

• Wed May 3rd, 1.15pm in INJ114, Trained transformers can in-context learn linear regression

We will talk about this paper, which proves actual learnability (as opposed to representability) guarantees

• Wed May 1st, 2.15pm in BC04, Graph embeddings

• Wed May 3rd, 2.15pm in BC04, Basics of graph neural networks

• Wed May 8th, 2.15pm in BC04, Graph neural networks and the Weisfeiler Lehmann test

• Wed May 15th, 2.15pm in BC04, ADAM

• Wed May 22nd, 2.15pm in BC04, Reinforcement learning, Markov Decision Processes, Monte-Carlo tree search

• Wed May 29th, 2.15pm in BC04, Differentially private training of neural etworks