Local Distributed Sampling from Locally-Defined Distribution Yitong Yin Nanjing University
Local Distributed Sampling !om Locally-Defined Distribution Yitong Yin Nanjing University
Counting and Sampling RANDOM GENERATION OF COMBINATORIAL STRUCTURES FROM A UNIFORM DISTRIBUTION LGORITHMS Mark R.JERRUM Department f Computer Science,Universiry of Edinburgh,Edinburgh EH93 Unied Kingdom Leslie G.VALIANT* Aiken Computation Laboratory,Harard Universiry,Cambridge,MA 02138,U.S.A V灯jayV.VAZIRANI* Computer Scence Department,Comell Universiry,Ithac,NY 14853,U.S.A. [Jerrum-Valiant-Vazirani86]: (For self-reducible problems) approx.counting (approx.,exact)sampling is tractable is tractable
Counting and Sampling approx. counting is tractable (approx., exact) sampling is tractable (For self-reducible problems) [Jerrum-Valiant-Vazirani ’86]:
Computational Phase Transition Sampling almost-uniform independent set in graphs with maximum degree△： ●[Weitz2006]:lf△≤5，poly-time. [Sly 2010]:If A=6,no poly-time algorithm unless NP=RP. A phase transition occurs when△：5→6. Local Computation?
Computational Phase Transition • [Weitz 2006]: If ∆≤5, poly-time. • [Sly 2010]: If ∆≥6, no poly-time algorithm unless NP=RP. Sampling almost-uniform independent set in graphs with maximum degree ∆: A phase transition occurs when ∆: 5→6. Local Computation?
Local Computation "What can be computed locally?"[Naor,Stockmeyer'93] the LOCAC model [Linial '87]: Communications are synchronized. In each round:each node can exchange unbounded messages with all neighbors,perform unbounded local computation,and read/write to unbounded local memory. Complexity:of rounds to terminate in the worst case. In t rounds:each node can collect information up to distance t. PLOCAL:t=polylog(n)
Local Computation • Communications are synchronized. • In each round: each node can exchange unbounded messages with all neighbors, perform unbounded local computation, and read/write to unbounded local memory. • Complexity: # of rounds to terminate in the worst case. • In t rounds: each node can collect information up to distance t. the LOCAL model [Linial ’87]: “What can be computed locally?” [Naor, Stockmeyer ’93] PLOCAL: t = polylog(n)
A Motivation: Distributed Machine Learning ●Data are stored in a distributed system. Distributed algorithms for: sampling from a joint distribution(specified by a probabilistic graphical model); ● inferring according to a probabilistic graphical model
A Motivation: Distributed Machine Learning • Data are stored in a distributed system. • Distributed algorithms for: • sampling from a joint distribution (specified by a probabilistic graphical model); • inferring according to a probabilistic graphical model
Example:Sample Independent Set u:uniform distribution of independent sets in G. Ye0,1 indicates an independent set Each ve∈Vreturns a Y∈{0，l}, such that Y=(YvEr -u Or:drv(Y,u)<1/poly(n) network G(E)
Example: Sample Independent Set • Each v∈V returns a Yv∈ {0,1}, such that Y = (Yv)v∈V ∼ µ • Or: dTV(Y, µ) < 1/poly(n) µ: uniform distribution of independent sets in G. network G(V,E) Y ∈ {0,1}V indicates an independent set
Inference (Local Counting) w:uniform distribution of independent sets in G. g:marginal distribution at v conditioning on o e0,1)5. y∈{0,1}：g(y)=Pr[Y=y|Ys=o] ●Each y∈S receives ov as input. ● Each v E D returns a marginal distributionsuch that: drv(g,hg)≤poim Z=40-ΠyX.=01<i:X,=0 i=1 network G(E) Z:of independent sets
Inference (Local Counting) network G(V,E) µ: uniform distribution of independent sets in G. • Each v ∈ S receives σv as input. • Each v ∈ V returns a marginal distribution such that: µ ˆ v dTV(ˆµ v , µ v ) 1 poly(n) : marginal distribution at v conditioning on σ ∈{0,1}S µ . v 0 1 1 0 8y 2 {0, 1} : µ v (y) = Pr Y ⇠µ [Yv = y | YS = ] 1 Z = µ(;) = Y n i=1 Pr Y ⇠µ [Yvi = 0 | 8j<i : Yvj = 0] Z: # of independent sets
Decay of Correlation g:marginal distribution at v conditioning on o0,1)5. strong spatial mixing(SSM): V boundary condition Be∈{0，l}r-sphere(W: drv(g,ug,B)≤poly(n)·exp(-2(r) SSM(if△≤5 when u is uniform distribution of ind.sets) approx.inference is solvable in O(log n)rounds in the OCA model
Decay of Correlation strong spatial mixing (SSM): SSM approx. inference is solvable in O(log n) rounds in the LOCAL model G v r B σ : marginal distribution at v conditioning on σ ∈{0,1}S µ . v ∀ boundary condition B∈{0,1}r-sphere(v) : dTV(µ v , µ,B v ) poly(n) · exp(⌦(r)) (iff ∆≤5 when µ is uniform distribution of ind. sets)
Gibbs Distribution (with pairwise interactions) Each vertex corresponds to a variable with finite domain g. network G,E): ● Each edge e=(u,v)EE has a matrix (binary constraint): Ae:[q]×[q→[0，l] bN ●Each vertex ve∈has a vector (unary constraint): bm:[g小→[0,1] Gibbs distribution u:Voelg] u(o)xIAe(o,o）Ib(ou) e=(u,v)∈E u∈V
Gibbs Distribution network G(V,E): • Each vertex corresponds to a variable with finite domain [q]. • Each edge e=(u,v)∈E has a matrix (binary constraint): • Each vertex v∈V has a vector (unary constraint): µ() / Y e=(u,v)2E Ae(u, v) Y v2V bv(v) Ae u bv v (with pairwise interactions) Ae: [q] × [q] → [0,1] bv: [q] → [0,1] • Gibbs distribution µ : ∀σ∈[q]V
Gibbs Distribution (with pairwise interactions) Gibbs distribution u:o∈[g]' network G,E): L(a)Ae(ou;ou)bo() e=(u,v)∈E v∈V independent set: bv a-B司6-图 coloring: 10 1 1 Ae= bu= .H Ae:[q]×[q]→[0,1] 1 bm:[q]→[0,1]
Gibbs Distribution • Gibbs distribution µ : ∀σ∈[q]V µ() / Y e=(u,v)2E Ae(u, v) Y v2V bv(v) • independent set: bv = 1 1 Ae = 1 1 1 0 • coloring: network G(V,E): Ae u bv v Ae: [q] × [q] → [0,1] bv: [q] → [0,1] (with pairwise interactions) Ae = 2 6 6 6 4 0 0 ... 0 3 7 7 7 5 1 1 bv = 2 6 4 1 . . . 1 3 7 5