The original question was asked in 2015. So I believe it is appropriate to include surveys with mathematical flavor on more recent/advanced topics in neural networks and deep learning.
The survey paper rigorously formulate the problem that a Generative Adversarial Network (GAN) tries to solve as a min-max optimization problem (Theorem 2.3).
A quite bit of analysis is involved in studying the Expressive Power of Neural Networks, especially when it comes to approximation theorems. The lecture notes above survey classical universal approximation results for shallow neural nets as well as more advanced topics including approximation results under the manifold hypothesis, benefits of depth to expressivity, and results on the VC dimension and the convexity of the set of functions implemented by feedforward neural networks.
(Another mathematical question pertaining to this topic which can be of interest to a combinatorialist is to count/bound the number of activation regions of a ReLU network as a measure of its complexity/expressiveness; see this paper for instance.)
After a review of older methods of node embedding (e.g. using random walks on graphs), the book presents a careful treatment of Graph Neural Networks (GNNs). The message passing framework in GNNs is rigorously defined; and it is discussed how different update and aggregation operations in message passing yield different types of GNNs (Graph Convolutional Networks, Graph Attention Networks, GraphSAGE etc.). Furthermore, there is a chapter discussing the mathematical motivation such as the graph Fourier transform and the Weisfeiler-Lehman algorithm.
The article provides an overview of Geometric Deep Learning, an "umbrella term" for deep learning on "non-Euclidean structured domains". This goes beyond graph neural networks and involves many problems in which a geometric prior (e.g. symmetry or scale separation) is present such as when the data lives on a submanifold, or Convolutional Neural Networks (CNNs) in which a grid-like structure is exploited. A more comprehensive and recent treatment can be found in this book which brands geometric deep learning as an "attempt to apply the Erlangen Programme mindset to the domain of deep learning".
- A mathematician's introduction to transformers and large language models - 2022
Formal Algorithms for Transformers - 2022
No theorems are involved but these surveys on Transformers were rigorous enough for my taste. The first one explains the attention mechanism, and the second one precisely presents the algorithms for various components of a transformer (positional embedding, attention, layer normalization etc.). Both references are self-contained.
The paper gives an introduction to Large Language Models (LLMs) "for mathematicians, physicists, and other scientists and readers who are mathematically knowledgeable but not necessarily expert in machine learning or artificial intelligence."