Optimization on graphons: two approaches

Abstract: The problem of finding minimizers of functions on large graphs arises naturally in many different domains, for example, exponential random graphs and extremal combinatorics. In Euclidean setting, there are two widely used approaches for minimizing a given objective function. First approach involves gradient based algorithms like gradient descent and stochastic gradient descent. And the second approach involves running MCMC algorithms, like Metropolis, to sample from a suitable Gibbs measure which is concentrated around the minimizers. We develop these two approaches for minimizing functions on large graphs or more precisely on the space of graphons—which arises as the limits of dense graphs.


In this talk, we will provide a gentle introduction to the limit theory of dense graphs and hence introduce graphons. Then, we will describe how optimization problems on large graphs can be analysed by considering optimization problems on the space of graphons. Finally, we will see how gradient based and MCMC based approaches to solve optimization problem can be implemented on the space of graphons.

Join Zoom Meeting
https://zoom.us/j/94627944993?pwd=WnExeklRaDJuTHV6SkFFTjViVExWdz09

Meeting ID: 946 2794 4993
Passcode: 317741