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


Event Speaker: 

Dheeraj Mysore Nagaraj

Event Location: 

via Zoom, see details below

Event Date/Time: 

Tuesday, June 15, 2021 - 1:00pm


Networks are used ubiquitously to model emergent global behavior which arise due to pairwise interactions between multiple agents and are 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 which is represented by a ReLU network of a given depth D and provide minimax optimal rates for its approximation error.
Thesis Supervisor: Prof. Guy Bresler
Readers: Profs. Devavrat Shah, John Tsitsiklis 
To attend this defense, please contact the doctoral candidate at dheeraj at mit dot edu