Skip to content. | Skip to navigation

Personal tools

Theme for TIFR Centre For Applicable Mathematics, Bangalore


You are here: Home / Events / Optimization on graphons: two approaches

Optimization on graphons: two approaches

Speaker: Raghavendra Tripathi (University of Washington)
Speaker: Raghavendra Tripathi (University of Washington)
When Jan 11, 2024
from 02:00 PM to 03:00 PM
Where Lecture Hall- LH 111 (Hybrid)
Add event to calendar vCal

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

Meeting ID: 946 2794 4993
Passcode: 317741

Filed under: