Colloquium: Tuesday Nov. 18, 2025 (14:00, room 614). Speaker: Gideon Amir (Bar Ilan). Title: “Convergence rate of l^p-energy minimization on graphs”.
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 >= 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 taken over all 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.
Joint work with Fedor Nazarov and Yuval Peres.
