Crossing the Chromatic Barrier Sequential Parallel O(n log n)→O(△logn) parallel speedup =0(n/△) △=max-degree X=chromatic no. Do not update adjacent vertices simultaneously. It takes =steps to update all vertices at least once. Q:"How to update all variables simultaneously and still converge to the correct distribution?
Crossing the Chromatic # Barrier Sequential Parallel O(n log n) O(Δ log n) ∆ = max-degree parallel speedup = θ(n /Δ) Q: “How to update all variables simultaneously and still converge to the correct distribution?” χ = chromatic no. Do not update adjacent vertices simultaneously. It takes ≥χ steps to update all vertices at least once
Markoy Random Fields (MRF) o∈[q]':4(o)xΠ4，(o,)Π(oo,) v∈V e=(u,v)∈E Each vertex vEV:a variable over X∈[q] domain [g]with distribution 中。 ●Each edge e-(u,v)∈E:a symmetric binary constraint: φe:[q]×[q]→[0,1] G(V,E)
Markov Random Fields G(V,E) • Each vertex v∈V: a variable over domain [q] with distribution • Each edge e=(u,v)∈E: a symmetric binary constraint: Xv∈[q] u v (MRF) νv ϕe : [q ] × [q ] → [0,1] νv ϕe ∀σ ∈ [q ] V : μ(σ) ∝ ∏ v∈V νv(σv) ∏ e= (u ,v)∈E ϕe(σu , σv)
The Local-Metropolis Algorithm [Feng,Sun,Y.,What can be sample locally?PODC'17] proposals: current: Markoy chain Xi→X+l: each vertex vEV independently proposes a random oyy; each edge e=(u,v)passes its check independently with prob: 中(X,O,)·中(o,X)·中e(o,o,) each vertex vEV update Xy to oy if all its edges pass checks; Local-Metropolis converges to the correct distribution u
The Local-Metropolis Algorithm Markov chain Xt → Xt+1 : each vertex v∈V independently proposes a random ; each edge e=(u,v) passes its check independently with prob: each vertex v∈V update Xv to σv if all its edges pass checks; u v w current: Xu Xv Xw proposals: σu σv σw • Local-Metropolis converges to the correct distribution µ. σv ∼ νv ϕe(Xu , σv) ⋅ ϕe(σu , Xv) ⋅ ϕe(σu , σv); [Feng, Sun, Y., What can be sample locally? PODC’17]
The Local-Metropolis Algorithm [Feng,Sun,Y.,What can be sample locally?PODC'17] each vertex vEV independently proposes a random y; each edge e=(4,v)passes its check independently with prob: 中e(X,o,)·中e(o,X)·中e(ou,o, each vertex vev update Xy to ov if all its edges pass checks; Local-Metropolis converges to the correct distribution u. MRF:(o)cΠ，(a,)Π(oa) v∈V e=(u,v)∈E under coupling condition for Metropolis-Hastings: Metropolis-Hastings:O(n log n)time (lazy)Local-Metropolis:O(log n)time
The Local-Metropolis Algorithm each vertex v∈V independently proposes a random ; each edge e=(u,v) passes its check independently with prob: each vertex v∈V update Xv to σv if all its edges pass checks; • Local-Metropolis converges to the correct distribution µ. σv ∼ νv ϕe(Xu , σv) ⋅ ϕe(σu , Xv) ⋅ ϕe(σu , σv); μ(σ) ∝ ∏ v∈V νv(σv) ∏ e= (u ,v)∈E ϕe(σu , σv MRF ) : • under coupling condition for Metropolis-Hastings: • Metropolis-Hastings: O(n log n) time • (lazy) Local-Metropolis: O(log n) time [Feng, Sun, Y., What can be sample locally? PODC’17]
Lower Bounds [Feng,Sun,Y.,What can be sample locally?PODC'17] Approx sampling from any MRF requires (log n)rounds. for sampling:O(log n)is the new criteria of"local" If sampling from hardcore model requires (diam)rounds. X(△)= (△-1)a-1) strong separation:sampling vs other (△-2)A local computation tasks Independent set is trivial to construct locally (e.g.) The lower bound holds not because of the locality of information,but max-deg△ because of the locality of correlation
Lower Bounds Approx sampling from any MRF requires Ω(log n) rounds. • for sampling: O(log n) is the new criteria of “local” If λ>λc, sampling from hardcore model requires Ω(diam) rounds. • Independent set is trivial to construct locally (e.g. ∅). • The lower bound holds not because of the locality of information, but because of the locality of correlation. strong separation: sampling vs other local computation tasks [Feng, Sun, Y., What can be sample locally? PODC’17] c() = ( 1)(1) ( 2) 2 4 6 8 10 1 2 3 4 5 6 Hard Easy max-deg Δ λ