LIDS Thesis Defense: Expressivity and Structure in Networks: Ising Models, Random Graphs, and Neural Networks

Thesis Committee: Guy Bresler (thesis advisor), Devavrat Shah, John Tsitsiklis

Networks are used ubiquitously to model emergent global behavior which arises due to pairwise interactions between multiple agents and is among the objects of fundamental interest in machine learning. The purpose of this thesis is to understand expressivity and structure in various network models. The basic high-level question we aim to address is for what ranges of parameters specifying a model does it capture complex dependencies. In particular, we consider widely used models such as a) Ising Model b) Exponential Random Graph Model (ERGM) c) Random Geometric Graphs (RGG) d) Neural Networks, where for each a version of this question is posed and solved.

In this talk, we will explore in detail the problem of neural network representation to characterize the kind of functions which can be represented by neural networks of a given depth. We will show that shallow networks can express highly smooth functions quite efficiently whereas depth is genuinely useful in representing ‘spiky’ functions. In particular, we will construct a natural function class that is represented by a ReLU network of a given depth D and provide minimax optimal rates for its approximation error.