Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2508.19411 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912556047663104 |
|---|---|
| author | Amir, Gideon Nazarov, Fedor Peres, Yuval |
| author_facet | Amir, Gideon Nazarov, Fedor Peres, Yuval |
| contents | 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 $ε$ is at most $n^{β_p}$ (up to logarithmic factors in $n$ and $ε$), where $β_p:=max(\frac{2p}{p-1},3)$; we prove that the exponent $β_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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_19411 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Convergence rate of $\ell^p$-energy minimization on graphs: sharp polynomial bounds and a phase transition at $p=3$ Amir, Gideon Nazarov, Fedor Peres, Yuval Probability 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 $ε$ is at most $n^{β_p}$ (up to logarithmic factors in $n$ and $ε$), where $β_p:=max(\frac{2p}{p-1},3)$; we prove that the exponent $β_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. |
| title | Convergence rate of $\ell^p$-energy minimization on graphs: sharp polynomial bounds and a phase transition at $p=3$ |
| topic | Probability |
| url | https://arxiv.org/abs/2508.19411 |