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

Networks are used ubiquitously to model global phenomena which emerge due to interactions between multiple agents and are among the objects of fundamental interest in machine learning. The purpose of this dissertation 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. For the case of Ising Model, ERGM, and RGG, we establish statistical tests which can distinguish them from the respective mean-field models by just using structural information (without the information about specific parameters) whenever it is possible or develop convergence results to show statistical indistinguishability. We then explore the problem of neural network representation to characterize the kind of functions which can be represented by neural networks of a given depth. In doing so, we establish that even shallow networks can express smooth functions efficiently whereas depth is genuinely useful in representing spiky functions.

Name thesis:degree_name

Doctoral

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2022

Author dc:creator

• Nagaraj, Dheeraj M.

Advisor dc:contributor.advisor

• Bresler, Guy

Statement dc:rights

• In Copyright - Educational Use Permitted
• Copyright MIT

Licence dc:rights.uri

• http://rightsstatements.org/page/InC-EDU/1.0/

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/143250

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/143250