Convergence rate of ${\ell }^p$-energy minimization on graphs: sharp polynomial bounds and a phase transition at $p=3$

Abstract

We consider the following dynamics on a connected graph $(V,E)$ with $n$ vertices. Given $p>1$ and an initial opinion profile $f_0:V\to [0,1]$, at each integer step $t\ge 1$ a uniformly random vertex $v=v_t$ is selected, and the opinion there is updated to the value $f_t(v)$ that minimizes the sum ${\sum }_{w\sim v}|f_t(v)-f_{t-1}(w){|}^p$ over neighbours $w$ of $v$. The case $p=2$ yields linear averaging dynamics, but for all $p\ne 2$ the dynamics are nonlinear. In the limiting case $p=\infty$ (known as Lipschitz learning), $f_t(v)$ is the average of the largest and smallest values of $f_{t-1}(w)$ among the neighbours $w$ of $v$. We show that the number of steps needed to reduce the oscillation of $f_t$ below $\epsilon$ is at most $n^{{\beta }_p}$ (up to logarithmic factors in $n$ and $\epsilon$), where ${\beta }_p:=max(\frac{2p}{p-1},3)$; we prove that the exponent ${\beta }_p$ is optimal. The phase transition at $p=3$ is a new phenomenon. We also derive matching upper and lower bounds for convergence time as a function of $n$ and the average degree; these are the most challenging to prove.

42 pages, 18 figures