Introduction
Given a bipartite graph G G G , the problem #BIS asks for the number Z ( G ) Z(G) Z ( G ) of its independent sets. Exact counting is #P-complete even on bipartite graphs [73 ] . In approximate counting, #BIS represents a broad class of problems equivalent to it under approximation-preserving reductions. Dyer, Goldberg, Greenhill, and Jerrum [25 ] showed that #BIS is complete for a logically defined class #RHΠ 1 \Pi_1 Π 1 under these reductions. Equivalent problems include counting downsets of a partial order and satisfying assignments of conjunctions of implications [25 ] , counting stable matchings [48 , 25 , 15 ] , and approximating the partition function of the ferromagnetic Ising model with mixed local fields [35 ] . #BIS is also a benchmark for weighted constraints, spin systems, and list homomorphisms [4 , 9 , 38 , 34 ] .
By the trichotomy of Dyer, Goldberg, and Jerrum [26 ] , every counting constraint satisfaction problem with a fixed finite set of Boolean relations is polynomial-time computable, #BIS-equivalent, or equivalent to counting satisfying assignments of Boolean formulas (#SAT). Yet the approximation complexity of the #BIS-equivalent case remains unresolved: algorithmic techniques have not yielded a fully polynomial randomized approximation scheme (FPRAS), and hardness reductions have not established NP-hardness of approximation [25 ] . The problems in this equivalence class are conjectured to have intermediate approximation complexity : they have no FPRAS, yet they are strictly easier to approximate than #SAT [25 , 36 , 13 ] . Determining the approximation complexity of #BIS, and hence of this entire equivalence class, is a central open problem in the area of approximate counting.
#BIS also fits into the broader framework of log-supermodular weights on Boolean variables: positive weights whose logarithms are supermodular set functions. This is the FKG lattice condition [32 ] , also called multivariate total positivity of order two (MTP2) [58 ] . The framework includes ferromagnetic Ising models with arbitrary local fields, whose partition functions are #BIS-equivalent [35 ] ; when all fields favor the same spin, they admit an FPRAS [55 ] . It also allows terms coupling more than two variables. For #BIS, summing out one side gives such a weight on the other, with no more variables than vertices. Log-supermodularity also marks a complexity boundary for Boolean weighted counting CSPs with nonnegative constraints and all unary weights available: apart from a tractable class generated by unary weights and disequality, a non-log-supermodular constraint gives #SAT-equivalence [4 Theorem 10.2] . Whether general log-supermodular counting reduces to #BIS remains open [9 Theorem 6] .
Substantial algorithmic progress has been made on restricted graph classes and in favorable parameter regimes. High-temperature algorithms exploit weak long-range dependence through correlation decay or rapid mixing. The hard-core model weights an independent set I I I by λ ∣ I ∣ \lambda^{|I|} λ ∣ I ∣ for a fugacity λ > 0 \lambda> 0 λ > 0 . On graphs of maximum degree at most a fixed Δ ≥ 3 \Delta\ge3 Δ ≥ 3 , Weitz’s correlation-decay algorithm [Wei06] gives a deterministic fully polynomial-time approximation scheme (FPTAS) whenever λ < λ c ( Δ ) = ( Δ − 1 ) Δ − 1 / ( Δ − 2 ) Δ \lambda< \lambda_c(\Delta) = (\Delta- 1)^{\Delta-1}/(\Delta- 2)^\Delta λ < λ c ( Δ ) = ( Δ − 1 ) Δ − 1 / ( Δ − 2 ) Δ , the uniqueness threshold of the infinite Δ \Delta Δ -regular tree. At λ = 1 \lambda= 1 λ = 1 this means maximum degree at most five, and Liu and Lu [62 ] need this bound on one side only. With the same fugacity on both sides, Chen, Liu, and Yin [21 ] show that λ c ( Δ ) \lambda_c(\Delta) λ c ( Δ ) remains the uniqueness threshold when the degree bound Δ \Delta Δ holds on one side only, and they sample rapidly below it. Low-temperature algorithms exploit concentration around structured phases. Algorithmic Pirogov–Sinai theory gives high-fugacity algorithms on lattice regions with suitable boundary conditions [47 ] and beyond lattices [18 ] . Polymer methods yield approximation algorithms on bounded-degree bipartite expanders [50 ] and on bipartite graphs with sufficiently unbalanced degrees or fugacities [22 ] , the latter including λ = 1 \lambda= 1 λ = 1 . On almost every random regular bipartite graph of sufficiently large fixed degree, recent work of Kocurek, Oveis Gharan, and Tjowasi [57 ] , together with [50 ] , covers all fugacities. Graph containers give an FPTAS for #BIS on weakly expanding regular bipartite graphs of large fixed degree, and inverse-polynomial relative approximation in subexponential time on regular bipartite graphs of growing degree [54 ] ; spectral methods give an FPRAS in the dense regular case [10 ] . These guarantees rely on assumptions that need not hold on arbitrary bipartite graphs.
Recent announcements of subexponential-time algorithms for exactly counting satisfying assignments of fixed-width CNF formulas [72 , 20 ] would, if confirmed, yield 2 O ( n log log n / log n ) 2^{O(n\log\log n/\sqrt{\log n})} 2 O ( n l o g l o g n / l o g n ) -time exact counting algorithms for #BIS on arbitrary n n n -vertex bipartite graphs. Before these announcements, the best known approximation algorithm for #BIS was the deterministic approximation algorithm of Goldberg, Lapinskas, and Richerby [39 ] , running in time O ( 2 0.2372 n ) poly ( ϵ − 1 ) O(2^{0.2372n})\operatorname{poly}(\epsilon^{-1}) O ( 2 0.2372 n ) poly ( ϵ − 1 ) for relative error ϵ \epsilon ϵ . The conjectured intermediate approximation complexity of the #BIS-equivalent class motivates the search for algorithms substantially faster than those available for SAT. Against the traditional exponential-time benchmark for SAT, obtaining a subexponential-time approximation algorithm for #BIS has been a prominent open direction in approximate counting (see, e.g., [74 , 60 ] ). The question was explicitly posed by Jenssen, Perkins, and Potukuchi [54 Question 1] and reiterated by Carlson, Davies, Kolla, and Potukuchi [10 ] . If confirmed, the announced algorithms would answer the question as stated, while also changing the SAT benchmark. The underlying algorithmic goal remains to exploit the special structure of #BIS to obtain algorithms substantially faster than those available for SAT. Against the announced SAT bounds, a natural quantitative target is a fixed-power saving in the exponent: does #BIS admit a 2 O ( n c ) 2^{O(n^c)} 2 O ( n c ) -time approximation algorithm at fixed accuracy for some fixed 0 < c < 1 0<c<1 0 < c < 1 ?
Results
We resolve this question by giving randomized algorithms for approximately counting and nearly uniformly sampling independent sets in arbitrary bipartite graphs. At fixed accuracy, both algorithms run in exp ( O ( n 1 / 3 log 4 / 3 n ) ) \exp(O(n^{1/3}\log^{4/3} n)) exp ( O ( n 1/3 log 4/3 n )) time on n n n -vertex graphs. We state the precise bounds in the exact real-arithmetic model of § 5 ; implementations using bit operations and fair random bits have the same exponential factors (Theorem A.1 ).
Write I ( G ) \mathcal{I}(G) I ( G ) for the independent sets of G G G , Z ( G ) = ∣ I ( G ) ∣ Z(G)=|\mathcal{I}(G)| Z ( G ) = ∣ I ( G ) ∣ , and U G U_G U G for the uniform law on I ( G ) \mathcal{I}(G) I ( G ) .
Theorem 1.1 (Bipartite independent sets). There are randomized algorithms with the following guarantees for every bipartite graph G G G with n ≥ 2 n\ge2 n ≥ 2 vertices.
For every real 0 < η ≤ 1 / 2 0<\eta\le1/2 0 < η ≤ 1/2 , the sampling algorithm returns an independent set of G G G whose law is within total variation distance η \eta η of U G U_G U G . Its running time is at most
exp ( O ( n 1 / 3 log 4 / 3 n ) ) poly ( n , log ( 1 / η ) ) . \exp\left(O\left(n^{1/3}\log^{4/3} n\right)\right)\operatorname{poly}(n,\log(1/\eta)). exp ( O ( n 1/3 log 4/3 n ) ) poly ( n , log ( 1/ η )) . For all reals ϵ , δ ∈ ( 0 , 1 / 2 ] \epsilon,\delta\in(0,1/2] ϵ , δ ∈ ( 0 , 1/2 ] , the counting algorithm returns an estimate Z ^ \widehat{Z} Z satisfying
Pr [ ∣ Z ^ Z ( G ) − 1 ∣ ≤ ϵ ] ≥ 1 − δ . \Pr\left[\left|\frac{\widehat{Z}}{Z(G)}-1\right|\le\epsilon\right]\ge1-\delta. Pr [ Z ( G ) Z − 1 ≤ ϵ ] ≥ 1 − δ . Its running time is at most
exp ( O ( n 1 / 3 log 4 / 3 n ) ) poly ( n , ϵ − 1 , log ( 1 / δ ) ) . \exp\left(O\left(n^{1/3}\log^{4/3} n\right)\right)\operatorname{poly}(n,\epsilon^{-1},\log(1/\delta)). exp ( O ( n 1/3 log 4/3 n ) ) poly ( n , ϵ − 1 , log ( 1/ δ )) . Both bounds hold on every execution in the exact real-arithmetic model.
The constants are absolute. For rational accuracy and failure-probability parameters, Theorem A.1 gives a bit implementation with polynomial overhead in their encoding lengths.
Log-supermodular weights. The algorithms follow from a general result for log-supermodular weights on Boolean variables. A positive weight W : { 0 , 1 } d → Q > 0 W : \{0,1\}^{d} \to\mathbb{Q}_{>0} W : { 0 , 1 } d → Q > 0 is log-supermodular if
W ( x ∧ y ) W ( x ∨ y ) ≥ W ( x ) W ( y ) ( x , y ∈ { 0 , 1 } d ) , (1) W(x \wedge y) W(x \vee y) \ge W(x) W(y) \qquad(x,y \in\{0,1\}^{d}), \tag*{(1)} W ( x ∧ y ) W ( x ∨ y ) ≥ W ( x ) W ( y ) ( x , y ∈ { 0 , 1 } d ) , (1)
where ∧ \wedge ∧ and ∨ \vee ∨ are the coordinatewise minimum and maximum.
The algorithms receive the dimension d ≥ 2 d \ge2 d ≥ 2 and use the following representation of W W W .
(Exact evaluation ) The weight is given by an exact evaluator using at most T W T_W T W operations per value; in the bit implementation, T W T_W T W denotes the bit cost of returning an exact rational value.
(Value length ) The algorithms receive a bound B ≥ 1 B \ge1 B ≥ 1 on the bit length of every value of W W W , where the bit length of a rational is the larger of those of its numerator and denominator.
Write Z W = ∑ x W ( x ) Z_W = \sum_x W(x) Z W = ∑ x W ( x ) for the partition function and μ W = W / Z W \mu_W = W/Z_W μ W = W / Z W for the target law.
Theorem 1.2 (Log-supermodular weights). For every log-supermodular weight W W W given in this representation, there are randomized algorithms with the following guarantees.
(i) For every real 0 < η ≤ 1 / 2 0 < \eta\le1/2 0 < η ≤ 1/2 , the sampling algorithm returns a configuration whose law is within total variation distance η \eta η of μ W \mu_W μ W . Its running time is at most
exp ( O ( min { d , d 1 / 3 log 2 / 3 d log 2 / 3 ( d + B ) } ) ) poly ( d , B , T W , log ( 1 / η ) ) . \exp\left(O\left(\min\left\{d,d^{1/3}\log^{2/3}d\log^{2/3}(d+B)\right\}\right)\right)\operatorname{poly}(d,B,T_W,\log(1/\eta)). exp ( O ( min { d , d 1/3 log 2/3 d log 2/3 ( d + B ) } ) ) poly ( d , B , T W , log ( 1/ η )) . (ii) For all reals ϵ , δ ∈ ( 0 , 1 / 2 ] \epsilon,\delta\in(0,1/2] ϵ , δ ∈ ( 0 , 1/2 ] , the counting algorithm returns an estimate Z ^ \widehat{Z} Z satisfying
Pr [ ∣ Z ^ Z W − 1 ∣ ≤ ϵ ] ≥ 1 − δ . \Pr\left[\left|\frac{\widehat{Z}}{Z_W}-1\right|\le\epsilon\right]\ge1-\delta. Pr [ Z W Z − 1 ≤ ϵ ] ≥ 1 − δ . Its running time is at most
exp ( O ( min { d , d 1 / 3 log 2 / 3 d log 2 / 3 ( d + B ) } ) ) poly ( d , B , T W , ϵ − 1 , log ( 1 / δ ) ) . \exp\left(O\left(\min\left\{d,d^{1/3}\log^{2/3}d\log^{2/3}(d+B)\right\}\right)\right)\operatorname{poly}(d,B,T_W,\epsilon^{-1},\log(1/\delta)). exp ( O ( min { d , d 1/3 log 2/3 d log 2/3 ( d + B ) } ) ) poly ( d , B , T W , ϵ − 1 , log ( 1/ δ )) . Both bounds hold on every execution in the exact real-arithmetic model.
When B B B and T W T_W T W are polynomial in d d d , both algorithms run in exp ( O ( d 1 / 3 log 4 / 3 d ) ) \exp(O(d^{1/3}\log^{4/3}d)) exp ( O ( d 1/3 log 4/3 d )) time at fixed accuracy. The algorithms access W W W only through its evaluator; no factorization into local interactions or correlation-decay assumption is required.
To apply Theorem 1.2 to #BIS, let G = ( L , R , E ) G=(L,R,E) G = ( L , R , E ) be a bipartite graph and write N ( S ) N(S) N ( S ) for the neighborhood of a vertex set S S S and N ( r ) = N ( { r } ) N(r)=N(\{r\}) N ( r ) = N ({ r }) . Summing out R R R gives the positive weight
W ( S ) = 2 ∣ R ∖ N ( S ) ∣ ( S ⊆ L ) , (2) W(S)=2^{|R\setminus N(S)|} \qquad(S\subseteq L), \tag*{(2)} W ( S ) = 2 ∣ R ∖ N ( S ) ∣ ( S ⊆ L ) , (2)
since S S S can be completed to an independent set by adjoining any subset of R ∖ N ( S ) R\setminus N(S) R ∖ N ( S ) .
Proof of Theorem 1.1 from Theorem 1.2. If ∣ L ∣ ≤ 1 |L|\le1 ∣ L ∣ ≤ 1 , the at most two choices of S ⊆ L S\subseteq L S ⊆ L , together with (1.2), give exact counting and sampling algorithms in polynomial time. Otherwise set d = ∣ L ∣ ≥ 2 d=|L|\ge2 d = ∣ L ∣ ≥ 2 . For S , S ′ ⊆ L S,S'\subseteq L S , S ′ ⊆ L , we have N ( S ∪ S ′ ) = N ( S ) ∪ N ( S ′ ) N(S\cup S')=N(S)\cup N(S') N ( S ∪ S ′ ) = N ( S ) ∪ N ( S ′ ) and N ( S ∩ S ′ ) ⊆ N ( S ) ∩ N ( S ′ ) N(S\cap S')\subseteq N(S)\cap N(S') N ( S ∩ S ′ ) ⊆ N ( S ) ∩ N ( S ′ ) , so
∣ N ( S ∪ S ′ ) ∣ + ∣ N ( S ∩ S ′ ) ∣ ≤ ∣ N ( S ) ∣ + ∣ N ( S ′ ) ∣ . |N(S\cup S')|+|N(S\cap S')|\le|N(S)|+|N(S')|. ∣ N ( S ∪ S ′ ) ∣ + ∣ N ( S ∩ S ′ ) ∣ ≤ ∣ N ( S ) ∣ + ∣ N ( S ′ ) ∣.
Thus the coverage function S ↦ ∣ N ( S ) ∣ S\mapsto|N(S)| S ↦ ∣ N ( S ) ∣ is submodular, so log W \log W log W is supermodular and W W W satisfies (1.1). The values are integers at most 2 n 2^n 2 n , so we may take B = n + 1 B=n+1 B = n + 1 and T W = poly ( n ) T_W=\operatorname{poly}(n) T W = poly ( n ) . Since Z W = Z ( G ) Z_W=Z(G) Z W = Z ( G ) , the counter of Theorem 1.2 counts independent sets.
For sampling, complete the sampler’s output S S S by adjoining a uniform subset of R ∖ N ( S ) R\setminus N(S) R ∖ N ( S ) , using at most n n n additional uniform draws. This maps μ W \mu_W μ W to U G U_G U G without increasing total variation distance. The running-time bounds follow from Theorem 1.2 with d ≤ n d\le n d ≤ n and B = n + 1 B=n+1 B = n + 1 . ∎
When k = min { ∣ L ∣ , ∣ R ∣ } ≥ 2 k = \min\{|L|,|R|\} \ge2 k = min { ∣ L ∣ , ∣ R ∣ } ≥ 2 , choosing the smaller side as L L L gives the exponent
O ( min { k , k 1 / 3 log 2 / 3 k log 2 / 3 n } ) . O\left(\min\left\{k,k^{1/3}\log^{2/3}k\log^{2/3}n\right\}\right). O ( min { k , k 1/3 log 2/3 k log 2/3 n } ) .
Both algorithms also apply under every feasible pinning, that is, one whose occupied vertices form an independent set. Deleting the occupied vertices, their neighbors, and the pinned vacant vertices leaves a bipartite induced subgraph. If this subgraph has fewer than two vertices, count and sample by exact enumeration. Restoring the occupied vertices gives a bijection between its independent sets and those consistent with the pinning.
The bipartite hard-core model. With positive rational vertex fugacities λ v \lambda_v λ v , the hard-core model assigns each independent set I I I weight ∏ v ∈ I λ v \prod_{v\in I}\lambda_v ∏ v ∈ I λ v . Summing out R R R gives
W λ ( S ) = ∏ v ∈ S λ v ∏ r ∈ R ∖ N ( S ) ( 1 + λ r ) , S ⊆ L . W_\lambda(S)=\prod_{v\in S}\lambda_v\prod_{r\in R\setminus N(S)}(1+\lambda_r),\qquad S\subseteq L. W λ ( S ) = v ∈ S ∏ λ v r ∈ R ∖ N ( S ) ∏ ( 1 + λ r ) , S ⊆ L .
Its partition function is the hard-core partition function of G G G . Up to an additive constant, log W λ \log W_\lambda log W λ is a modular function minus the weighted coverage function S ↦ ∑ r ∈ N ( S ) log ( 1 + λ r ) S\mapsto\sum_{r\in N(S)}\log(1+\lambda_r) S ↦ ∑ r ∈ N ( S ) log ( 1 + λ r ) , so W λ W_\lambda W λ is log-supermodular. Complete the sampler’s output S S S by occupying each r ∈ R ∖ N ( S ) r\in R\setminus N(S) r ∈ R ∖ N ( S ) independently with probability λ r / ( 1 + λ r ) \lambda_r/(1+\lambda_r) λ r / ( 1 + λ r ) . This completion does not increase total variation distance.
The weight is exactly evaluable in time polynomial in n n n and the total bit length of the fugacities, with B B B at most n n n plus that length. Thus, with exact enumeration of S S S when ∣ L ∣ ≤ 1 |L|\le1 ∣ L ∣ ≤ 1 , Theorem 1.2 covers the hard-core model on arbitrary bipartite graphs with arbitrary positive rational vertex fugacities. When the fugacities’ total bit length is polynomial in n n n , the algorithms preserve exp ( O ( n 1 / 3 log 4 / 3 n ) ) \exp(O(n^{1/3}\log^{4/3}n)) exp ( O ( n 1/3 log 4/3 n )) time at fixed accuracy.
Bipartiteness makes this marginalization produce a positive log-supermodular weight, although the original hard-core edge constraint 1 { x u x v = 0 } \mathbf{1}\{x_ux_v=0\} 1 { x u x v = 0 } fails (1.1). For every fixed Δ ≥ 3 \Delta\ge3 Δ ≥ 3 and fixed rational λ > λ c ( Δ ) = ( Δ − 1 ) Δ − 1 / ( Δ − 2 ) Δ \lambda>\lambda_c(\Delta)=(\Delta-1)^{\Delta-1}/(\Delta-2)^\Delta λ > λ c ( Δ ) = ( Δ − 1 ) Δ − 1 / ( Δ − 2 ) Δ , approximating the partition function at uniform fugacity λ \lambda λ is #BIS-hard on bipartite graphs of maximum degree Δ \Delta Δ [13 Corollary 3] . On general Δ \Delta Δ -regular graphs at the same fugacity, there is a constant c = c ( Δ , λ ) > 0 c=c(\Delta,\lambda)>0 c = c ( Δ , λ ) > 0 such that approximation within a factor e c n e^{cn} e c n is NP-hard under randomized reductions [SS14, p. 2387].
The random-cluster and ferromagnetic Potts models. Let G = ( V , E ) G=(V,E) G = ( V , E ) be a graph, not necessarily bipartite, with n = ∣ V ∣ n=|V| n = ∣ V ∣ vertices and m m m edges, and for A ⊆ E A\subseteq E A ⊆ E let κ ( A ) \kappa(A) κ ( A ) be the number of connected components of ( V , A ) (V,A) ( V , A ) , isolated vertices included. With a rational q ≥ 1 q\ge1 q ≥ 1 and positive rational edge weights v e v_e v e , the random-cluster model gives A A A the weight
W q , v ( A ) = q κ ( A ) ∏ e ∈ A v e , A ⊆ E . W_{q,v}(A)=q^{\kappa(A)}\prod_{e\in A}v_e,\qquad A\subseteq E. W q , v ( A ) = q κ ( A ) e ∈ A ∏ v e , A ⊆ E .
and its partition function Z W q , v Z_{W_{q,v}} Z W q , v is the multivariate Tutte polynomial Z G ( q , v ) Z_G(q,v) Z G ( q , v ) [Sko05, (1.1)]. The rank n − κ ( A ) n-\kappa(A) n − κ ( A ) of A A A in the cycle matroid of G G G is submodular, so log W q , v \log W_{q,v} log W q , v is supermodular when q ≥ 1 q\ge1 q ≥ 1 ; this is the FKG lattice condition for the random-cluster measure [40 ] . Computing κ ( A ) \kappa(A) κ ( A ) by graph search evaluates the weight exactly in time polynomial in n n n , m m m and the bit lengths of q q q and the v e v_e v e . Since κ ( A ) ≤ n \kappa(A)\le n κ ( A ) ≤ n , we may take B B B to be n n n times the bit length of q q q plus the total bit length of the v e v_e v e . If m ≤ 1 m\le1 m ≤ 1 , enumerating the at most two edge sets counts and samples exactly; otherwise Theorem 1.2 applies with d = m d=m d = m . When the bit lengths are polynomial in n + m n+m n + m , the algorithms run in exp ( O ( m 1 / 3 log 4 / 3 ( n + m ) ) ) \exp(O(m^{1/3}\log^{4/3}(n+m))) exp ( O ( m 1/3 log 4/3 ( n + m ))) time at fixed accuracy: exp ( O ( n 1 / 3 log 4 / 3 n ) ) \exp(O(n^{1/3}\log^{4/3}n)) exp ( O ( n 1/3 log 4/3 n )) on graphs of bounded degree, and exp ( O ( n 2 / 3 log 4 / 3 n ) ) \exp(O(n^{2/3}\log^{4/3}n)) exp ( O ( n 2/3 log 4/3 n )) on all graphs. Multigraphs reduce to simple graphs: a loop e e e contributes 1 + v e 1+v_e 1 + v e , while a parallel bundle F F F becomes one edge of activity ∏ e ∈ F ( 1 + v e ) − 1 \prod_{e\in F}(1+v_e)-1 ∏ e ∈ F ( 1 + v e ) − 1 . Lift samples by including loops independently with probabilities v e / ( 1 + v e ) v_e/(1+v_e) v e / ( 1 + v e ) and replacing each present bundle by a nonempty S ⊆ F S\subseteq F S ⊆ F according to weights ∏ e ∈ S v e \prod_{e\in S}v_e ∏ e ∈ S v e . The latter is the law of independent Bernoulli choices with probabilities v e / ( 1 + v e ) v_e/(1+v_e) v e / ( 1 + v e ) conditioned on being nonempty. Sequential conditioning, using suffix products of the exclusion probabilities, samples this law in O ( ∣ F ∣ ) O(|F|) O ( ∣ F ∣ ) arithmetic operations and uniform draws. For a matroid M M M on E E E with a polynomial-time rank oracle, the weight q − r M ( A ) ∏ e ∈ A v e q^{-r_M(A)}\prod_{e\in A}v_e q − r M ( A ) ∏ e ∈ A v e is log-supermodular because r M r_M r M is submodular, and sums to the multivariate Tutte polynomial Z ~ M ( q , v ) \widetilde Z_M(q,v) Z M ( q , v ) [Sok05, (1.3)]. Use d = ∣ E ∣ d=|E| d = ∣ E ∣ , replace n n n by d d d in the bound on B B B , and enumerate directly when d ≤ 1 d\leq1 d ≤ 1 .
For an integer q ≥ 2 q\geq2 q ≥ 2 and rational y e > 1 y_e>1 y e > 1 , the ferromagnetic q q q -state Potts model assigns a coloring σ : V → { 1 , … , q } \sigma:V\to\{1,\ldots,q\} σ : V → { 1 , … , q } the weight ∏ e y e \prod_e y_e ∏ e y e over the edges e e e whose endpoints receive the same color. Writing each factor as 1 + ( y e − 1 ) 1 { the endpoints of e agree } 1+(y_e-1)1\{\text{the endpoints of }e\text{ agree}\} 1 + ( y e − 1 ) 1 { the endpoints of e agree } and expanding gives the Fortuin–Kasteleyn representation: the Potts partition function equals Z G ( q , v ) Z_G(q,v) Z G ( q , v ) with v e = y e − 1 v_e=y_e-1 v e = y e − 1 [Sok05, Theorem 2.3], so the counter estimates it. Coloring each component of the sampler’s output A A A independently and uniformly from { 1 , … , q } \{1,\ldots,q\} { 1 , … , q } maps the random-cluster law to the Potts law, by the Edwards–Sokal coupling [30 ] , and does not increase total variation distance. For every integer q ≥ 3 q\geq3 q ≥ 3 , approximating the ferromagnetic Potts partition function is #BIS-hard [36 ] , whereas the ferromagnetic Ising model, the case q = 2 q=2 q = 2 , has an FPRAS [55 ] .
Overview of the proof
Self-reduction and coarse estimates (§ 5 ). Sampling and counting reduce to the conditional marginal probabilities along the self-reduction tree . Fix an order of the d d d coordinates; the nodes are the prefixes x v ∈ { 0 , 1 } j x_v\in\{0,1\}^j x v ∈ { 0 , 1 } j , 0 ≤ j ≤ d 0\leq j\leq d 0 ≤ j ≤ d , with children v 0 v0 v 0 and v 1 v1 v 1 , and the mass Z v Z_v Z v of a node is the partition function of the residual weight left by pinning its prefix. The next coordinate is 1 1 1 with conditional marginal probability p v = Z v 1 / Z v p_v=Z_{v1}/Z_v p v = Z v 1 / Z v . The classical self-reduction as in [56 ] multiplies estimated probabilities, so their errors accumulate along a path and it needs relative accuracy O ( 1 / d ) O(1/d) O ( 1/ d ) at every node. A different self-reduction by Sinclair and Jerrum [SJ89, Section 4] uses a reversible tree walk and needs much less. Because the leaves carry exact weights, its stationary law conditioned on the leaves is exactly the target law. Mass estimates with approximation ratio r = e b r=e^b r = e b , which we call the distortion , cost only a factor e O ( b ) e^{O(b)} e O ( b ) in running time (Proposition 2.1 ). Our task is therefore to estimate the logarithm of every residual mass from below within an additive error b b b as in equation (5) ; since pinning preserves log-supermodularity, the same estimator applies to every node along the self-reduction tree.
A variational principle on the self-reduction tree (§ 6.1 ). Lower estimates come from Gibbs’ variational principle [WJ08], which we write on the tree. Express a strictly positive law as μ = e Φ / Z Φ \mu=e^\Phi/Z_\Phi μ = e Φ / Z Φ , with potential Φ : { 0 , 1 } d → R \Phi:\{0,1\}^d\to\mathbb{R} Φ : { 0 , 1 } d → R and Z Φ = ∑ x e Φ ( x ) Z_\Phi=\sum_x e^{\Phi(x)} Z Φ = ∑ x e Φ ( x ) . A branching rule assigns a probability θ v \theta_v θ v to moving from each internal node v v v to v 1 v1 v 1 ; write θ v ( x ) \theta_v(x) θ v ( x ) for the probability of reaching v v v , and ν θ \nu_\theta ν θ for the law of the leaf reached, which can be any law. Write H ( ν ) = − ∑ x ν ( x ) log ν ( x ) H(\nu)=-\sum_x\nu(x)\log\nu(x) H ( ν ) = − ∑ x ν ( x ) log ν ( x ) for the entropy of a finite law ν \nu ν and H ( p ) = − p log p − ( 1 − p ) log ( 1 − p ) H(p)=-p\log p-(1-p)\log(1-p) H ( p ) = − p log p − ( 1 − p ) log ( 1 − p ) for the binary entropy of p ∈ [ 0 , 1 ] p\in[0,1] p ∈ [ 0 , 1 ] , with 0 log 0 = 0 0\log0=0 0 log 0 = 0 . By the chain rule for entropy, H ( ν θ ) = ∑ v ν θ ( v ) H ( θ v ) H(\nu_\theta)=\sum_v\nu_\theta(v)H(\theta_v) H ( ν θ ) = ∑ v ν θ ( v ) H ( θ v ) , where the sum runs over internal nodes. Gibbs’ principle therefore becomes
log Z Φ = max θ ( ∑ v ν θ ( v ) H ( θ v ) + E ν θ Φ ) , \log Z_\Phi=\max_\theta\left(\sum_v\nu_\theta(v)H(\theta_v)+\mathbb{E}_{\nu_\theta}\Phi\right), log Z Φ = θ max ( v ∑ ν θ ( v ) H ( θ v ) + E ν θ Φ ) ,
with the conditional marginal probabilities θ = p \theta=p θ = p as its unique maximizer (Proposition 3.1 ). Every branching rule thus gives a lower bound, and the best one is exactly what self-reduction needs. The objective, however, is not concave in θ \theta θ , even for log-supermodular laws. It is concave in the leaf probabilities, but evaluating its entropy requires those probabilities.
Relaxing to guides (Sections 3.2 and 3.3). The above variational formulation is not friendly to optimization algorithms. Both parts inside its objective stand in the way of concavity: the non-linear entropy terms, and the expected potential that depends on the branching probabilities through products along paths. There is a standard way to linearize an entropy (see equation (13) and Remark 3.7), and for the potential term we apply the Lovász extension in equation (19) . The identity (13) linearizes a binary entropy as H ( p ) = E [ a ( U ) 1 { U ≥ 1 − p } ] H(p) = \mathbb{E}[a(U)\mathbf{1}\{U \ge1-p\}] H ( p ) = E [ a ( U ) 1 { U ≥ 1 − p }] for U U U uniform on ( 0 , 1 ) (0,1) ( 0 , 1 ) and the logit a ( u ) = log ( u / ( 1 − u ) ) a(u) = \log(u/(1-u)) a ( u ) = log ( u / ( 1 − u )) . Driving the descent by independent uniform inputs U 1 , … , U d U_1,\ldots,U_d U 1 , … , U d , one per depth, with the binary decision rule F i = 1 { U i ≥ 1 − θ v } F_i = \mathbf{1}\{U_i \ge1-\theta_v\} F i = 1 { U i ≥ 1 − θ v } at the node v v v reached at depth i − 1 i-1 i − 1 , turns the entropy terms at depth i − 1 i-1 i − 1 into E [ a ( U i ) F i ] \mathbb{E}[a(U_i)F_i] E [ a ( U i ) F i ] . The binary decision rules 1 { U ≥ 1 − p } \mathbf{1}\{U \ge1-p\} 1 { U ≥ 1 − p } do not form a convex domain (for optimization), so we have to further relax to an appropriate set of real-valued decision functions F i ∈ [ 0 , 1 ] F_i \in[0,1] F i ∈ [ 0 , 1 ] of U 1 , … , U i U_1,\ldots,U_i U 1 , … , U i that we call guides (see Definition 3.5). This relaxation also means that the potential term needs to be evaluated at fractional decisions, which is provided by its Lovász extension Φ L \Phi^{\mathrm L} Φ L [65 ] after normalizing by Φ ( 0 ) = 0 \Phi(0)=0 Φ ( 0 ) = 0 . This gives the variational objective in equation (20)
P ( F ) = ∑ i = 1 d E [ a ( U i ) F i ( U ) ] + E Φ L ( F ( U ) ) , \mathcal{P}(F) = \sum_{i=1}^{d} \mathbb{E}[a(U_i)F_i(U)] + \mathbb{E}\Phi^{\mathrm L}(F(U)), P ( F ) = i = 1 ∑ d E [ a ( U i ) F i ( U )] + E Φ L ( F ( U )) ,
a linear score term plus a potential term. Every guide satisfies P ( F ) ≤ log Z Φ \mathcal{P}(F) \le\log Z_\Phi P ( F ) ≤ log Z Φ , with equality only for the exact guide f f f , the guide defined by the true conditional marginal probabilities. Furthermore, P \mathcal{P} P is concave exactly when μ \mu μ is log-supermodular (Proposition 3.8). It is an expectation over independent inputs of quantities computed from the guide and from values of the potential, so it can be estimated and optimized without evaluating the probabilities of the law induced by the guide. What remains is the size of the search space: a guide is a [ 0 , 1 ] d [0,1]^d [ 0 , 1 ] d -valued function of d d d continuous inputs.
Low-degree approximation and coarse estimation (Section 4). Such a function can depend on exponentially many interactions among its inputs. We restrict the search to functions whose coordinates have interaction degree at most D D D : every nonzero component of their Hoeffding decompositions [71 §8.3] involves at most D D D inputs (Section 4.1). Once each input is discretized to poly( d ) (d) ( d ) bins, such a function has d O ( D + 1 ) d^{O(D+1)} d O ( D + 1 ) coefficients. For related uses of low-degree approximation, see [64 , 68 ] . To show that this restricted search contains a good candidate, the argument follows f → g → u f \to g \to u f → g → u : Section 5 turns the exact guide f f f into a witness g g g , a guide with a small objective gap log Z Φ − P ( g ) ≤ b ∗ \log Z_\Phi-\mathcal{P}(g) \le b_* log Z Φ − P ( g ) ≤ b ∗ and small degree-D D D tails (25) , and Section 4 discretizes and truncates g g g into a candidate u u u that is nearly as good. Crucially, the algorithm never evaluates f f f or g g g explicitly; their existence merely certifies that the low-degree search space contains a near-optimal candidate u u u . Instead, the algorithm optimizes the low-degree Walsh coefficients of u u u directly via projected stochastic supergradient ascent [NJL$^{+}$09]. A penalty for values outside [ 0 , 1 ] [0,1] [ 0 , 1 ] keeps the objective at most log Z Φ \log Z_\Phi log Z Φ for every candidate. We estimate this value on fresh samples and subtract an error margin, giving a lower estimate with high probability. The additive error is b ∗ + O ( 1 ) b_*+O(1) b ∗ + O ( 1 ) at cost exp ( O ( ( D + 1 ) log d ) ) \exp(O((D+1)\log d)) exp ( O (( D + 1 ) log d )) up to polynomial factors (Theorem 4.1). It remains to construct witnesses.
Ordinary resampling and the square-root baseline (Section 5.1). The exact guide has objective gap zero, but its moving thresholds can create interactions of every order, so it need not be a witness. Ordinary resampling replaces each input independently with probability τ \tau τ , which multiplies a component involving k k k inputs by ( 1 − τ ) k (1-\tau)^k ( 1 − τ ) k [71 §8.3] and costs at most τ H ( μ ) ≤ d τ log 2 \tau H(\mu) \le d\tau\log2 τ H ( μ ) ≤ d τ log 2 of objective value (Lemma 5.1). Taking D = O ( τ − 1 log ( d + B ) ) D = O(\tau^{-1}\log(d + B)) D = O ( τ − 1 log ( d + B )) gives exponential cost exp ( O ( d τ + Q / τ ) ) \exp(O(d\tau+ Q/\tau)) exp ( O ( d τ + Q / τ )) , where Q = log d log ( d + B ) Q = \log d\log(d + B) Q = log d log ( d + B ) , and balancing the terms gives the square-root baseline of Corollary 5.2: exp ( O ( n log n ) ) \exp(O(\sqrt{n\log n})) exp ( O ( n log n )) time for #BIS at fixed accuracy, which already answers the question of [54 ] . The loss is linear in τ \tau τ because a resampled input contributes nothing to the linear score.
Threshold smoothing and the cube-root bound (Section 5.2). Threshold smoothing keeps every input and shifts its threshold instead. For a smoothing parameter 0 < w ≤ 1 / 2 0 < w \le1/2 0 < w ≤ 1/2 , each threshold c c c encountered by the exact guide becomes c ± w c ( 1 − c ) c \pm wc(1-c) c ± w c ( 1 − c ) with a fresh fair sign. The perturbed decisions determine the next threshold. Averaging the signs at fixed inputs, with one sign sequence shared by all output coordinates, gives the guide g g g of (5.2). The two shifted thresholds have mean c c c , which preserves each branching probability and hence the joint law μ \mu μ . Concavity therefore protects the potential term. Symmetry cancels the first-order score change, while the factor c ( 1 − c ) c(1-c) c ( 1 − c ) compensates for the entropy curvature − H ′ ′ ( c ) = 1 / [ c ( 1 − c ) ] -H''(c) = 1/[c(1-c)] − H ′′ ( c ) = 1/ [ c ( 1 − c )] . The linear-score loss is at most w 2 c ( 1 − c ) w^2c(1-c) w 2 c ( 1 − c ) per comparison and d w 2 / 4 dw^2/4 d w 2 /4 in total (Proposition 5.5). For a fixed threshold c c c , the averaged indicator has variance ( 1 − w / 2 ) c ( 1 − c ) (1-w/2)c(1-c) ( 1 − w /2 ) c ( 1 − c ) (Lemma 5.7), a factor 1 − w / 2 1-w/2 1 − w /2 smaller than the original indicator’s variance. An exact energy identity for threshold trees (5.5) turns this into geometric decay of the high-degree tails at a rate linear in w w w . This is an aggregate statement rather than a componentwise contraction. Thus D = O ( w − 1 log ( d + B ) ) D = O(w^{-1}\log(d + B)) D = O ( w − 1 log ( d + B )) suffices, the distortion costs the walk exp ( O ( d w 2 + 1 ) ) \exp(O(dw^2 + 1)) exp ( O ( d w 2 + 1 )) , and each estimate costs exp ( O ( Q / w ) ) \exp(O(Q/w)) exp ( O ( Q / w )) . Choosing w w w of order ( Q / d ) 1 / 3 (Q/d)^{1/3} ( Q / d ) 1/3 when this is at most 1 / 2 1/2 1/2 , and using exact enumeration otherwise, gives the exponent O ( min { d , d 1 / 3 Q 2 / 3 } ) O(\min\{d,d^{1/3}Q^{2/3}\}) O ( min { d , d 1/3 Q 2/3 }) of Theorem 1.2.
Related work
Algorithms for independent sets. Ge and Štefankovič [41 ] proposed a Markov chain for #BIS on edge subsets, with weights determined by adjacency-matrix ranks over F 2 \mathbb{F}_2 F 2 . Goldberg and Jerrum [37 ] later proved exponential mixing time on an infinite family of bipartite graphs.
For fixed Δ ≥ 3 \Delta\ge3 Δ ≥ 3 and fixed 0 < λ < λ c ( Δ ) 0 < \lambda< \lambda_c(\Delta) 0 < λ < λ c ( Δ ) , a degree bound Δ \Delta Δ on one side suffices for nearly linear field-dynamics sampling and nearly cubic Glauber mixing [21 ] . Faster Glauber mixing from a fully occupied side is known with degree balance [11 ] or with no degree bound on the other side [33 ] . At criticality, results require a bound on the maximum degree of the whole graph [7 , 19 ] and draw on spectral independence and field dynamics [1 , 12 ] .
Low-temperature methods include polymer and clique dynamics [14 , 31 ] , perfect sampling in an unbalanced regime [3 ] , and improved fugacity bounds on regular bipartite expanders [53 ] . For sufficiently large fixed Δ \Delta Δ , algorithms cover fugacities down to Ω ~ ( 1 / Δ ) \widetilde{\Omega}(1/\Delta) Ω ( 1/Δ ) , including λ = 1 \lambda= 1 λ = 1 , on almost every Δ \Delta Δ -regular bipartite graph [50 , 63 , 17 ] .
For every fixed c > 0 c > 0 c > 0 , the randomized container algorithm of [54 ] , Theorem 3 achieves n − c n^{-c} n − c relative error with probability at least 2 / 3 2/3 2/3 in time exp ( O ( n log 3 Δ / Δ ) ) \exp(O(n\log^3\Delta/\Delta)) exp ( O ( n log 3 Δ/Δ )) on Δ \Delta Δ -regular bipartite graphs. Its guarantee does not cover arbitrary accuracy [10 ] . Pinning can also destroy regularity, obstructing the usual sampling self-reduction [54 ] . Our estimator handles every pinned residual, yielding counting and sampling at arbitrary accuracy (Proposition 2.1).
Cardinality-constrained independent sets. Counting bipartite independent sets of a given total size or occupation of one side is NP-hard to approximate within any polynomial factor when the prescription is part of the input [8 ] . Further hardness results hold at certain fixed occupation densities on bounded-degree bipartite graphs [70 ] . Such constraints generally destroy log-supermodularity, even after complementing one side.
Self-reduction and marginal estimation. Bounded self-reductions [16 ] and rejection sampling on self-reduction trees [43 , 44 ] require upper bounds on residual masses that remain consistent under recursion. Moitra [66 ] estimates conditional marginals by a coupling-based linear program for bounded-degree CNFs in the local-lemma regime. We use the Sinclair–Jerrum tree walk [SJ89, Section 4] with coarse variational lower estimates of log-partition functions, without requiring consistency between parent and child estimates. Samples yield relative counts by self-reduction [56 ] . Our estimates apply even when bipartite hard-core models have coexisting phases and exponentially slow local dynamics [24 , 67 ] .
Variational bounds on partition functions. Bethe bounds are lower bounds for Boolean models with log-supermodular factors [77 ] ; other approaches use convex hierarchies, mean-field approximation, and correlation rounding [75 , 49 , 51 ] . For an Ising interaction matrix J J J , with Frobenius norm ∥ J ∥ F \lVert J\rVert_F ∥ J ∥ F , the additive guarantees of [49 Theorem 12 and Remark 13] have leading scale ϵ n ∥ J ∥ F \epsilon n\lVert J\rVert_F ϵ n ∥ J ∥ F . Jain, Koehler, and Risteski [51 ] bound the mean-field error by O ( ( n ∥ J ∥ F ) 2 / 3 ) O((n\lVert J\rVert_F)^{2/3}) O (( n ∥ J ∥ F ) 2/3 ) and give subexponential algorithms with o ( n ) o(n) o ( n ) additive error when ∥ J ∥ F 2 = o ( n ) \lVert J\rVert_F^2=o(n) ∥ J ∥ F 2 = o ( n ) . Our estimator gives error ϵ d + 1 / 8 \epsilon d+1/8 ϵ d + 1/8 for arbitrary positive log-supermodular weights, with weight sizes entering its running time through B B B (Corollary 2.3 ).
L-FIELD [27 , 28 ] produces factorized laws from sub- and supergradient bounds; its log-supermodular upper bound has a concave Lovász-extension formulation [27 Lemma 3 and Section 4.1] . The logistic perturb-and-MAP upper bound is at least as tight as the L-FIELD upper bound [SB16, Proposition 1].
Sequential variational representations. For binary variables, Lemma 3.6 is equivalent to Hazan and Jaakkola’s random-perturbation identity [42 Theorem 1] (Remark 3.7 ). Sequential perturbation samplers use upper bounds [44 ] ; lower bounds from perturbing a fixed variable subset generally fall below log Z Z Z [44 Corollary 1] , while using all variables gives equality but requires one Gumbel perturbation per configuration. Variational autoregressive networks [WWZ19] optimize the objective of Proposition 3.1 using network branching rules. It need not be concave even for log-supermodular laws, and its evaluation uses the candidate law’s conditional probabilities. Our fractional relaxation is concave for log-supermodular laws and evaluable under a fixed product law using only guide and weight evaluations, without evaluating the induced law’s probabilities.
Organization. Section 2 reduces sampling and counting to coarse mass estimation; Section 3 develops the variational principle and concave relaxation. Section 4 builds the estimator from guides constructed in Section 5 using resampling and threshold smoothing. Section 6 discusses scope and open questions; Appendix A gives quantitative conversion and bit implementation details.
Counting and sampling from coarse estimates
We first explain how coarse lower estimates of residual log-partition functions suffice for sampling and counting. We then derive Theorem 1.2 assuming an estimator with the accuracy and running-time guarantees stated below. To construct such an estimator, Section 3 develops a concave variational formulation, which Section 4 turns into a finite-dimensional optimization problem. Section 5 uses threshold smoothing to establish the approximation bounds needed for the stated guarantees.
Notation and computational model. All logarithms are natural unless a base is specified. Write [ k ] = { 1 , … , k } [k]=\{1,\ldots,k\} [ k ] = { 1 , … , k } , let e j e_j e j be the j j j th unit vector, and identify subsets with their indicator vectors.
We use x < i x_{<i} x < i and x ≤ i x_{\leq i} x ≤ i for prefixes, and 1 { ⋅ } \mathbf{1}\{\cdot\} 1 { ⋅ } and 1 A \mathbf{1}_A 1 A for indicators. For finite laws, ∥ μ − ν ∥ T V = 1 2 ∑ x ∣ μ ( x ) − ν ( x ) ∣ \lVert\mu-\nu\rVert_{\mathrm{TV}}=\frac{1}{2}\sum_x\lvert\mu(x)-\nu(x)\rvert ∥ μ − ν ∥ TV = 2 1 ∑ x ∣ μ ( x ) − ν ( x )∣ . Graphs are finite, simple, and labeled.
We work in an exact real-arithmetic model . Arithmetic operations, comparisons, and evaluations of log \log log and exp \exp exp on real numbers have unit cost, as does an independent uniform draw from ( 0 , 1 ) (0,1) ( 0 , 1 ) . We also charge one operation for each accessed coefficient or graph entry, and T W T_W T W operations for each evaluation of a weight W W W . The model has no oracle for partition functions, conditional probabilities or expectations: the algorithm estimates expectations from independent samples and computes every function it queries. Running-time bounds count operations and random draws on every execution. Appendix A implements the algorithm with bit operations and fair random bits at the claimed cost.
The self-reduction tree
Let W : { 0 , 1 } d → Q > 0 W:\{0,1\}^d\to\mathbb{Q}_{>0} W : { 0 , 1 } d → Q > 0 satisfy the evaluator and value-length assumptions of Theorem 1.2 , and fix an order of its d ≥ 2 d\geq2 d ≥ 2 coordinates. The estimator bounds use this original dimension d d d , including for residuals with fewer than two free coordinates.
The self-reduction tree is the complete binary tree of depth d d d whose nodes v v v at depth j j j are the prefixes x v ∈ { 0 , 1 } j x_v\in\{0,1\}^j x v ∈ { 0 , 1 } j ; it is a special case of the self-reducibility tree of Sinclair and Jerrum [SJ89, p. 100]. We write depth ( v ) = j \operatorname{depth}(v)=j depth ( v ) = j . The root o o o is the empty prefix, the leaves are the configurations x x x , v − v^{-} v − denotes the parent of a node v ≠ o v\neq o v = o , and v 0 v0 v 0 and v 1 v1 v 1 denote the children of a node v v v with depth ( v ) < d \operatorname{depth}(v)<d depth ( v ) < d .
Pinning the prefix x v x_v x v at a node v v v of depth j j j leaves the residual weight W v ( x ′ ) = W ( x v , x ′ ) W_v(x')=W(x_v,x') W v ( x ′ ) = W ( x v , x ′ ) on the free coordinates x ′ ∈ { 0 , 1 } d − j x'\in\{0,1\}^{d-j} x ′ ∈ { 0 , 1 } d − j . Its partition function Z v = ∑ x ′ W v ( x ′ ) Z_v=\sum_{x'}W_v(x') Z v = ∑ x ′ W v ( x ′ ) is the mass of v v v , and its residual law W v / Z v W_v/Z_v W v / Z v is the conditional law of the free coordinates given the prefix x v x_v x v . Thus Z o = Z W Z_o=Z_W Z o = Z W , the residual law of the root is μ W \mu_W μ W , and Z x = W ( x ) Z_x=W(x) Z x = W ( x ) at a leaf x x x . Pinning the next coordinate to 0 0 0 or 1 1 1 gives the two child residuals, so Z v = Z v 0 + Z v 1 Z_v=Z_{v0}+Z_{v1} Z v = Z v 0 + Z v 1 at every internal node. If W W W is log-supermodular, so is every residual, since (1.1) remains valid when the prefix coordinates are fixed. Let X X X have law μ W \mu_W μ W . The conditional marginal probability at a node v v v with depth ( v ) = i − 1 < d \operatorname{depth}(v)=i-1<d depth ( v ) = i − 1 < d is
p v = Z v 1 Z v = μ W ( X i = 1 ∣ X < i = x v ) , (3) p_v=\frac{Z_{v1}}{Z_v}=\mu_W(X_i=1\mid X_{<i}=x_v), \tag*{(3)} p v = Z v Z v 1 = μ W ( X i = 1 ∣ X < i = x v ) , (3)
and we write p i ( x < i ) = p v p_i(x_{<i})=p_v p i ( x < i ) = p v when x < i = x v x_{<i}=x_v x < i = x v . Every prefix has positive probability, so these probabilities are defined at every internal node. If they were available, we could sample μ W \mu_W μ W by descending the tree, choosing child v 1 v1 v 1 with probability p v p_v p v . They also determine the partition function: telescoping the masses along any root-to-leaf path gives the chain rule
Z W = W ( x ) ∏ i = 1 d μ W ( X i = x i ∣ X < i = x < i ) ( x ∈ { 0 , 1 } d ) . (4) Z_W=\frac{W(x)}{\prod_{i=1}^{d}\mu_W(X_i=x_i\mid X_{<i}=x_{<i})}\qquad(x\in\{0,1\}^d). \tag*{(4)} Z W = ∏ i = 1 d μ W ( X i = x i ∣ X < i = x < i ) W ( x ) ( x ∈ { 0 , 1 } d ) . (4)
For the coarse estimates in the next subsection, we normalize each residual by its value at 0 0 0 . The resulting normalized potential is Φ v ( x ′ ) = log ( W v ( x ′ ) / W v ( 0 ) ) \Phi_v(x')=\log(W_v(x')/W_v(0)) Φ v ( x ′ ) = log ( W v ( x ′ ) / W v ( 0 )) , with partition function Z Φ v = ∑ x ′ e Φ v ( x ′ ) = Z v / W v ( 0 ) Z_{\Phi_v}=\sum_{x'}e^{\Phi_v(x')}=Z_v/W_v(0) Z Φ v = ∑ x ′ e Φ v ( x ′ ) = Z v / W v ( 0 ) . This rescaling leaves the residual law unchanged. We have Φ v ( 0 ) = 0 \Phi_v(0)=0 Φ v ( 0 ) = 0 , the normalization used for the Lovász extension in Section 3.3, and log Z Φ v ≥ 0 \log Z_{\Phi_v}\geq0 log Z Φ v ≥ 0 , because the configuration x ′ = 0 x'=0 x ′ = 0 contributes 1 1 1 to Z Φ v Z_{\Phi_v} Z Φ v . At a leaf, Z Φ v = 1 Z_{\Phi_v}=1 Z Φ v = 1 and hence log Z Φ v = 0 \log Z_{\Phi_v}=0 log Z Φ v = 0 .
From coarse estimates to counting and sampling
We first specify the estimates needed for the counting and sampling conversion. At a node v v v , the estimator approximates the normalized residual log-partition function log Z Φ v = log Z v − log W v ( 0 ) \log Z_{\Phi_v}=\log Z_v-\log W_v(0) log Z Φ v = log Z v − log W v ( 0 ) . Since W v ( 0 ) W_v(0) W v ( 0 ) can be evaluated exactly, adding log W v ( 0 ) \log W_v(0) log W v ( 0 ) to such an estimate gives an estimate of log Z v \log Z_v log Z v with the same additive error.
Suppose that, given any node v v v and any failure parameter 0 < δ e s t ≤ 1 / 2 0 < \delta_{\mathrm{est}} \le1/2 0 < δ est ≤ 1/2 , a randomized estimator returns a real A v ≥ 0 A_v \ge0 A v ≥ 0 with
Pr [ log Z Φ v − b ≤ A v ≤ log Z Φ v ] ≥ 1 − δ e s t , (5) \Pr\left[\log Z_{\Phi_v} - b \le A_v \le\log Z_{\Phi_v}\right] \ge1-\delta_{\mathrm{est}}, \tag*{(5)} Pr [ log Z Φ v − b ≤ A v ≤ log Z Φ v ] ≥ 1 − δ est , (5)
where b ≥ 0 b \ge0 b ≥ 0 is a known one-sided additive error bound common to all nodes. Thus, with the stated probability, A v A_v A v is a lower bound on log Z Φ v \log Z_{\Phi_v} log Z Φ v and underestimates it by at most b b b . The bound b b b may depend on the original input parameters and the chosen estimator construction; in particular, it may grow with d d d . At a leaf, Z Φ v = 1 Z_{\Phi_v}=1 Z Φ v = 1 , so we require the estimator to return A v = 0 A_v=0 A v = 0 exactly.
We also assume a cost bound that is uniform over the nodes. Every execution, including one on which the accuracy guarantee fails, uses at most C 0 poly ( d , log ( 1 / δ e s t ) ) C_0\operatorname{poly}(d,\log(1/\delta_{\mathrm{est}})) C 0 poly ( d , log ( 1/ δ est )) operations and uniform draws, including evaluations of W W W . The factor C 0 ≥ T W C_0 \ge T_W C 0 ≥ T W absorbs the dependence on the estimator’s other construction parameters, which are fixed in advance. It may depend on the original input parameters and need not be polynomial in d d d , but it is independent of the node and the requested failure probability. The condition C 0 ≥ T W C_0 \ge T_W C 0 ≥ T W also pays for evaluating the exact leaf weights and the normalizing value W v ( 0 ) W_v(0) W v ( 0 ) , as needed by the conversion.
Proposition 2.1 (Counting and sampling from coarse estimates ). Suppose every residual admits the estimator in (5) , with additive error bound b b b and cost C 0 poly ( d , log ( 1 / δ e s t ) ) C_0\operatorname{poly}(d,\log(1/\delta_{\mathrm{est}})) C 0 poly ( d , log ( 1/ δ est )) . For η , ϵ , δ ∈ ( 0 , 1 / 2 ] \eta,\epsilon,\delta\in(0,1/2] η , ϵ , δ ∈ ( 0 , 1/2 ] , every residual law can be sampled within total variation distance η \eta η at cost
exp ( O ( b + 1 ) ) C 0 poly ( d , log ( 1 / η ) ) , \exp(O(b+1))C_0\operatorname{poly}(d,\log(1/\eta)), exp ( O ( b + 1 )) C 0 poly ( d , log ( 1/ η )) , and Z W Z_W Z W can be estimated within relative error ϵ \epsilon ϵ , with failure probability at most δ \delta δ , at cost
exp ( O ( b + 1 ) ) C 0 poly ( d , ϵ − 1 , log ( 1 / δ ) ) . \exp(O(b+1))C_0\operatorname{poly}(d,\epsilon^{-1},\log(1/\delta)). exp ( O ( b + 1 )) C 0 poly ( d , ϵ − 1 , log ( 1/ δ )) . These bounds hold on every execution. No log-supermodularity is needed for this conversion.
Why coarse estimates suffice. Direct self-reduction by descent [56 ] would use ratios of mass estimates in place of the conditional probabilities in (3) . If e − b Z y ≤ q y ≤ Z y e^{-b}Z_y \le q_y \le Z_y e − b Z y ≤ q y ≤ Z y for both children y y y of v v v , then e − b p v ≤ q v 1 / ( q v 0 + q v 1 ) ≤ e b p v e^{-b}p_v \le q_{v1}/(q_{v0}+q_{v1}) \le e^b p_v e − b p v ≤ q v 1 / ( q v 0 + q v 1 ) ≤ e b p v . These errors multiply along the path, up to a factor e b d e^{bd} e b d , so obtaining relative error ϵ \epsilon ϵ from this product bound calls for b = O ( ϵ / d ) b=O(\epsilon/d) b = O ( ϵ / d ) . The walk of Sinclair and Jerrum [SJ89, Section 4] pays for the error once, in its running time. The sampling half of Proposition 2.1 is a quantitative form of their theorem [SJ89, Theorems 4.4 and 4.5]: for self-reducible relations, counts within a polynomial ratio r r r suffice for almost uniform generation. They weight each edge of the tree by the estimated number of solutions below it, and run the lazy walk that, when it moves, chooses an incident edge in proportion to its weights. Its stationary probabilities are proportional to the sums of incident edge weights. Single solutions are counted exactly, so the stationary law conditioned on the leaves is uniform. To obtain samples efficiently, it remains to control both the time to approach stationarity and the probability that the endpoint is a leaf. On a tree of depth d d d , the leaves carry stationary probability at least 1 / ( 2 r d ) 1/(2rd) 1/ ( 2 r d ) [SJ89, Lemma 4.1], which controls the number of runs needed to obtain a leaf endpoint. Each subtree hangs from a single edge whose weight is within the ratio r r r of the number of leaves below it, so the conductance is at least 1 / ( 4 r 2 d ) 1/(4r^2d) 1/ ( 4 r 2 d ) [SJ89, Lemma 4.2]. Their bound on mixing in terms of conductance then controls the length of each run [SJ89, Theorem 3.4 and Lemma 4.3]. What changes here. We need this conversion for weighted leaves and for approximation ratios r = e b r=e^b r = e b that may be superpolynomial in d d d . To turn our logarithmic estimates into edge weights, we use the mass estimates q v = W v ( 0 ) e A v q_v=W_v(0)e^{A_v} q v = W v ( 0 ) e A v , which satisfy q x = W ( x ) q_x=W(x) q x = W ( x ) at leaves and e − b Z v ≤ q v ≤ Z v e^{-b}Z_v\le q_v\le Z_v e − b Z v ≤ q v ≤ Z v when all estimates are good. The arguments for the stationary law, leaf mass and conductance bound above use only these two properties, so they carry over with leaf weights W ( x ) W(x) W ( x ) and r = e b r=e^b r = e b . In particular, the stationary law conditioned on the leaves is μ W \mu_W μ W . For the running time, however, their bound through the minimum stationary probability could depend on very small leaf weights. We avoid this dependence by bounding convergence from the root using its stationary probability, which is at least 1 / ( 2 r 2 d ) 1/(2r^2d) 1/ ( 2 r 2 d ) . This gives mixing time polynomial in r r r , d d d , and log ( 1 / η ) \log(1/\eta) log ( 1/ η ) . Together with the leaf-mass bound, it gives an e O ( b ) e^{O(b)} e O ( b ) sampling overhead up to polynomial factors in d d d and log ( 1 / η ) \log(1/\eta) log ( 1/ η ) , even when b b b grows with d d d . Randomized estimates are computed once and cached, as in [SJ89, Remark after Theorem 4.5], so that the analysis can condition on fixed edge weights. Since the same construction applies to every residual, the resulting samples give a relative counter by self-reduction [56 ] . Appendix A.1 gives the full construction and failure-probability analysis.
The log-supermodular estimator. The following estimator supplies the estimates required by Proposition 2.1; its proof is completed in Section 5.2.
Theorem 2.2 (Estimator from threshold smoothing). Assume W W W is log-supermodular and let 0 < w ≤ 1 / 2 0<w\le1/2 0 < w ≤ 1/2 . For every node v v v and every real 0 < δ ≤ 1 / 2 0<\delta\le1/2 0 < δ ≤ 1/2 , a randomized algorithm returns a real A v ∈ [ 0 , d ( 1 + 2 B ) ] A_v\in[0,d(1+2B)] A v ∈ [ 0 , d ( 1 + 2 B )] such that
Pr [ log Z Φ v − ( d w 2 4 + 1 8 ) ≤ A v ≤ log Z Φ v ] ≥ 1 − δ . (6) \Pr\left[\log Z_{\Phi_v}-\left(\frac{dw^2}{4}+\frac{1}{8}\right)\le A_v\le\log Z_{\Phi_v}\right]\ge1-\delta. \tag*{(6)} Pr [ log Z Φ v − ( 4 d w 2 + 8 1 ) ≤ A v ≤ log Z Φ v ] ≥ 1 − δ . (6) Every execution uses at most
exp ( O ( w − 1 log d log ( d + B ) ) ) poly ( d , B , T W , log ( 1 / δ ) ) (7) \exp\left(O\left(w^{-1}\log d\log(d+B)\right)\right)\operatorname{poly}\left(d,B,T_W,\log(1/\delta)\right) \tag*{(7)} exp ( O ( w − 1 log d log ( d + B ) ) ) poly ( d , B , T W , log ( 1/ δ ) ) (7) operations and uniform draws. At leaves it returns A v = 0 A_v=0 A v = 0 .
The estimator subtracts an error margin from an estimated objective value; the objective itself never exceeds log Z Φ v \log Z_{\Phi_v} log Z Φ v .
The cube-root balance. The parameter w w w trades accuracy against cost. In the additive error bound b = d w 2 / 4 + 1 / 8 b=dw^2/4+1/8 b = d w 2 /4 + 1/8 , the term d w 2 / 4 dw^2/4 d w 2 /4 bounds how far the value of the guide constructed in Section 5 falls below log Z Φ v \log Z_{\Phi_v} log Z Φ v , and 1 / 8 1/8 1/8 bounds the further loss of discretization, truncation, optimization and validation in Section 4. The error bound b b b contributes exp ( O ( d w 2 + 1 ) ) \exp(O(dw^2+1)) exp ( O ( d w 2 + 1 )) to the walk, whereas each estimate costs exp ( O ( Q / w ) ) \exp(O(Q/w)) exp ( O ( Q / w )) up to polynomial factors, with Q = log d log ( d + B ) Q=\log d\log(d+B) Q = log d log ( d + B ) . Balancing d w 2 dw^2 d w 2 and Q / w Q/w Q / w yields d 1 / 3 Q 2 / 3 d^{1/3}Q^{2/3} d 1/3 Q 2/3 .
Proof of Theorem 1.2. Put ℓ d = ⌈ log 2 d ⌉ \ell_d=\lceil\log_2 d\rceil ℓ d = ⌈ log 2 d ⌉ and ℓ B = ⌈ log 2 ( d + B ) ⌉ \ell_B=\lceil\log_2(d+B)\rceil ℓ B = ⌈ log 2 ( d + B )⌉ . Suppose first that ℓ d ℓ B < d / 8 \ell_d\ell_B<d/8 ℓ d ℓ B < d /8 , and let w w w be the largest number 2 − j 2^{-j} 2 − j , j ≥ 1 j\ge1 j ≥ 1 , with d w 2 ≤ ℓ d ℓ B dw^2\le\ell_d\ell_B d w 2 ≤ ℓ d ℓ B ; it is found by comparing d d d with ℓ d ℓ B 8 j \ell_d\ell_B8^j ℓ d ℓ B 8 j for j = 1 , 2 , … j=1,2,\ldots j = 1 , 2 , … . Then w < 1 / 2 w<1/2 w < 1/2 , and maximality gives 8 d w 3 > ℓ d ℓ B 8dw^3>\ell_d\ell_B 8 d w 3 > ℓ d ℓ B , whence
d w 2 ≤ d 1 / 3 ( ℓ d ℓ B ) 2 / 3 , w − 1 ℓ d ℓ B < 2 d 1 / 3 ( ℓ d ℓ B ) 2 / 3 . dw^2\le d^{1/3}(\ell_d\ell_B)^{2/3},\qquad w^{-1}\ell_d\ell_B<2d^{1/3}(\ell_d\ell_B)^{2/3}. d w 2 ≤ d 1/3 ( ℓ d ℓ B ) 2/3 , w − 1 ℓ d ℓ B < 2 d 1/3 ( ℓ d ℓ B ) 2/3 .
By Theorem 2.2, the estimator with this parameter satisfies (2.3) with b = d w 2 / 4 + 1 / 8 b=dw^2/4+1/8 b = d w 2 /4 + 1/8 and C 0 = exp ( O ( w − 1 ℓ d ℓ B ) ) poly ( d , B , T W ) C_0=\exp(O(w^{-1}\ell_d\ell_B))\operatorname{poly}(d,B,T_W) C 0 = exp ( O ( w − 1 ℓ d ℓ B )) poly ( d , B , T W ) . Proposition 2.1 then gives the required sampler and relative counter, with exponential factor exp ( O ( d 1 / 3 ( ℓ d ℓ B ) 2 / 3 ) ) \exp(O(d^{1/3}(\ell_d\ell_B)^{2/3})) exp ( O ( d 1/3 ( ℓ d ℓ B ) 2/3 )) .
If instead ℓ d ℓ B ≥ d / 8 \ell_d\ell_B \ge d/8 ℓ d ℓ B ≥ d /8 , then d ≤ 4 d 1 / 3 ( ℓ d ℓ B ) 2 / 3 d \le4d^{1/3}(\ell_d\ell_B)^{2/3} d ≤ 4 d 1/3 ( ℓ d ℓ B ) 2/3 , and we evaluate all 2 d 2^d 2 d weights, sum them, and sample by comparing one uniform draw with their cumulative sums. This exact enumeration costs 2 d poly ( d , T W ) 2^d\operatorname{poly}(d,T_W) 2 d poly ( d , T W ) . In both cases the exponent is O ( min { d , d 1 / 3 ( ℓ d ℓ B ) 2 / 3 } ) O(\min\{d,d^{1/3}(\ell_d\ell_B)^{2/3}\}) O ( min { d , d 1/3 ( ℓ d ℓ B ) 2/3 }) . Since ℓ d ≤ 2 log 2 d \ell_d \le2\log_2 d ℓ d ≤ 2 log 2 d and ℓ B ≤ 2 log 2 ( d + B ) \ell_B \le2\log_2(d+B) ℓ B ≤ 2 log 2 ( d + B ) , this gives the bound of Theorem 1.2.
At the root, the same estimator gives additive estimates directly.
Corollary 2.3 (Additive estimates). Let W W W be log-supermodular. For all reals 0 < ϵ ≤ 1 / 16 0 < \epsilon\le1/16 0 < ϵ ≤ 1/16 and 0 < δ ≤ 1 / 2 0 < \delta\le1/2 0 < δ ≤ 1/2 , a randomized algorithm returns a real A A A with Pr [ log Z W − ϵ d − 1 / 8 ≤ A ≤ log Z W ] ≥ 1 − δ \Pr[\log Z_W-\epsilon d-1/8 \le A \le\log Z_W] \ge1-\delta Pr [ log Z W − ϵ d − 1/8 ≤ A ≤ log Z W ] ≥ 1 − δ . Every execution uses at most exp ( O ( ϵ − 1 / 2 log d log ( d + B ) ) ) poly ( d , B , T W , log ( 1 / δ ) ) \exp(O(\epsilon^{-1/2}\log d\log(d+B)))\operatorname{poly}(d,B,T_W,\log(1/\delta)) exp ( O ( ϵ − 1/2 log d log ( d + B ))) poly ( d , B , T W , log ( 1/ δ )) operations and uniform draws.
Proof. Apply Theorem 2.2 at the root with w = 2 ϵ ≤ 1 / 2 w=2\sqrt{\epsilon}\le1/2 w = 2 ϵ ≤ 1/2 , so that d w 2 / 4 = ϵ d dw^2/4=\epsilon d d w 2 /4 = ϵ d , and add log W ( 0 ) \log W(0) log W ( 0 ) , since Z Φ o = Z W / W ( 0 ) Z_{\Phi_o}=Z_W/W(0) Z Φ o = Z W / W ( 0 ) .
Such an additive estimate at the root is not a relative approximation of Z W Z_W Z W . By Proposition 2.1 , lower estimates within additive error polylogarithmic in d + B d+B d + B at every node, at quasi-polynomial cost, would already give a randomized quasi-polynomial approximation scheme.
The next three sections prove Theorem 2.2. Section 3 writes log Z Φ v \log Z_{\Phi_v} log Z Φ v as the maximum of an objective that is concave for log-supermodular weights, Section 4 maximizes a finite-dimensional version of it from samples, and Section 5 shows that this version loses little.
A variational principle on the self-reduction tree
We develop a variational formulation for constructing the coarse lower estimates of the residual log-partition functions log Z Φ v \log Z_{\Phi_v} log Z Φ v required by (5) . Starting from Gibbs’ variational principle on the self-reduction tree (Section 3.1), we linearize the entropy terms (Section 3.2) and use the Lovász extension for the potential term (Section 3.3). The resulting objective has maximum log Z Φ v \log Z_{\Phi_v} log Z Φ v , so every feasible choice gives a lower bound; it is concave when the weight is log-supermodular.
We state the formulation for a general potential Φ : { 0 , 1 } d → R \Phi:\{0,1\}^d\to\mathbb{R} Φ : { 0 , 1 } d → R normalized by Φ ( 0 ) = 0 \Phi(0)=0 Φ ( 0 ) = 0 . Write Z Φ = ∑ x e Φ ( x ) Z_\Phi=\sum_x e^{\Phi(x)} Z Φ = ∑ x e Φ ( x ) and μ = e Φ / Z Φ \mu=e^\Phi/Z_\Phi μ = e Φ / Z Φ . Every strictly positive law on the cube has this form for a unique normalized potential, namely Φ = log ( μ / μ ( 0 ) ) \Phi=\log(\mu/\mu(0)) Φ = log ( μ / μ ( 0 )) . The tree masses and conditional marginal probabilities in this section are those of the weight e Φ e^\Phi e Φ .
Branching rules
Sampling by self-reduction descends the tree from the root, moving from each internal node v v v to v 1 v1 v 1 with probability p v p_v p v and to v 0 v0 v 0 otherwise. To obtain p p p as the solution of an optimization problem, we let these probabilities vary. A branching rule θ \theta θ assigns a probability θ v ∈ [ 0 , 1 ] \theta_v\in[0,1] θ v ∈ [ 0 , 1 ] to every internal node v v v of the self-reduction tree, that is, to every node with depth ( v ) < d \operatorname{depth}(v)<d depth ( v ) < d . We write θ x \theta_x θ x for the branching probability at the node with prefix x x x , so that θ o \theta_o θ o is the branching probability at the root o o o .
The descent with rule θ \theta θ starts at the root and moves from each internal node v v v to v 1 v1 v 1 with probability θ v \theta_v θ v and to v 0 v0 v 0 otherwise (Figure 1). It reaches the node with prefix x ∈ { 0 , 1 } j x\in\{0,1\}^j x ∈ { 0 , 1 } j with probability
ν θ ( x ) = ∏ i ≤ j : x i = 1 θ x < i ∏ i ≤ j : x i = 0 ( 1 − θ x < i ) , (8) \nu_\theta(x)=\prod_{\substack{i\le j:x_i=1}}\theta_{x_{<i}}\prod_{\substack{i\le j:x_i=0}}(1-\theta_{x_{<i}}), \tag*{(8)} ν θ ( x ) = i ≤ j : x i = 1 ∏ θ x < i i ≤ j : x i = 0 ∏ ( 1 − θ x < i ) , (8)
the product of the branching probabilities along the path. We write ν θ ( v ) \nu_\theta(v) ν θ ( v ) for the probability of reaching node v v v and ν θ \nu_\theta ν θ for the induced law on leaves. Every law ν \nu ν on { 0 , 1 } d \{0,1\}^d { 0 , 1 } d is ν θ \nu_\theta ν θ for some θ \theta θ : at each node that ν \nu ν reaches, let θ v \theta_v θ v be the conditional probability under ν \nu ν that the next coordinate is 1, and choose arbitrary values elsewhere. In particular ν p = μ \nu_p=\mu ν p = μ by (4) .
To apply Gibbs’ variational principle, we express the entropy of ν θ \nu_\theta ν θ in terms of the branching probabilities. The entropy of a law ν \nu ν on a finite set is H ( ν ) = − ∑ x ν ( x ) log ν ( x ) H(\nu)=-\sum_x \nu(x)\log\nu(x) H ( ν ) = − ∑ x ν ( x ) log ν ( x ) , and the binary entropy of p ∈ [ 0 , 1 ] p\in[0,1] p ∈ [ 0 , 1 ] is H ( p ) = − p log p − ( 1 − p ) log ( 1 − p ) H(p)=-p\log p-(1-p)\log(1-p) H ( p ) = − p log p − ( 1 − p ) log ( 1 − p ) , where 0 log 0 = 0 0\log0=0 0 log 0 = 0 [23 Chapter 2] . Let X X X have law ν θ \nu_\theta ν θ . Given X < i X_{<i} X < i , the coordinate X i X_i X i is a Bernoulli variable with mean θ X < i \theta_{X_{<i}} θ X < i , so the chain rule for entropy [23 Theorem 2.5.1] gives
H ( ν θ ) = ∑ i = 1 d H ( X i ∣ X < i ) = ∑ i = 1 d E H ( θ X < i ) = ∑ v ν θ ( v ) H ( θ v ) . (9) H(\nu_\theta)=\sum_{i=1}^{d}H(X_i\mid X_{<i})=\sum_{i=1}^{d}\mathbb{E}\,H(\theta_{X_{<i}})=\sum_v\nu_\theta(v)H(\theta_v). \tag*{(9)} H ( ν θ ) = i = 1 ∑ d H ( X i ∣ X < i ) = i = 1 ∑ d E H ( θ X < i ) = v ∑ ν θ ( v ) H ( θ v ) . (9)
the last sum over internal nodes. At each depth, the probabilities ν θ ( v ) \nu_\theta(v) ν θ ( v ) sum to one, so that depth contributes the expected binary entropy of the next branch.
Figure 1. A branching rule on the self-reduction tree for d = 2 d=2 d = 2 . Nodes other than the root o o o are labeled by their prefixes, and edges by the probabilities with which the descent takes them. The probability of reaching each leaf, shown below it, is the product along its path, and by (9) the entropy of the leaf law is H ( θ o ) + ( 1 − θ o ) H ( θ 0 ) + θ o H ( θ 1 ) H(\theta_o)+(1-\theta_o)H(\theta_0)+\theta_oH(\theta_1) H ( θ o ) + ( 1 − θ o ) H ( θ 0 ) + θ o H ( θ 1 ) .
For every law ν \nu ν on the cube, Gibbs’ variational principle, in the form of [WJ08, Theorem 3.4 and §5.2.2], gives
H ( ν ) + E ν Φ = log Z Φ − KL ( ν ∥ μ ) ≤ log Z Φ , KL ( ν ∥ μ ) = ∑ x ν ( x ) log ν ( x ) μ ( x ) ≥ 0 , (10) H(\nu)+\mathbb{E}_\nu\Phi=\log Z_\Phi-\operatorname{KL}(\nu\Vert\mu)\leq\log Z_\Phi,\qquad\operatorname{KL}(\nu\Vert\mu)=\sum_x\nu(x)\log\frac{\nu(x)}{\mu(x)}\geq0, \tag*{(10)} H ( ν ) + E ν Φ = log Z Φ − KL ( ν ∥ μ ) ≤ log Z Φ , KL ( ν ∥ μ ) = x ∑ ν ( x ) log μ ( x ) ν ( x ) ≥ 0 , (10)
with equality exactly when ν = μ \nu=\mu ν = μ ; here KL ( ν ∥ μ ) \operatorname{KL}(\nu\Vert\mu) KL ( ν ∥ μ ) is the relative entropy of ν \nu ν with respect to μ \mu μ , and terms with ν ( x ) = 0 \nu(x)=0 ν ( x ) = 0 are zero. Substituting (9) for the entropy of ν = ν θ \nu=\nu_\theta ν = ν θ writes the principle on the tree.
Proposition 3.1 (Variational principle on the self-reduction tree). For every strictly positive law μ = e Φ / Z Φ \mu=e^\Phi/Z_\Phi μ = e Φ / Z Φ on { 0 , 1 } d \{0,1\}^d { 0 , 1 } d ,
log Z Φ = max θ ( ∑ v ν θ ( v ) H ( θ v ) + E ν θ Φ ) , (11) \log Z_\Phi=\max_\theta\left(\sum_v\nu_\theta(v)H(\theta_v)+\mathbb{E}_{\nu_\theta}\Phi\right), \tag*{(11)} log Z Φ = θ max ( v ∑ ν θ ( v ) H ( θ v ) + E ν θ Φ ) , (11) the maximum over branching rules θ \theta θ , and the unique maximizer is the vector θ = p \theta=p θ = p of conditional marginal probabilities of $\mu.
Proof. By (9) and (10) , the bracket equals H ( ν θ ) + E ν θ Φ = log Z Φ − KL ( ν θ ∥ μ ) H(\nu_\theta)+\mathbb{E}_{\nu_\theta}\Phi=\log Z_\Phi-\operatorname{KL}(\nu_\theta\Vert\mu) H ( ν θ ) + E ν θ Φ = log Z Φ − KL ( ν θ ∥ μ ) , which is maximal exactly when ν θ = μ \nu_\theta=\mu ν θ = μ . Since μ \mu μ is strictly positive, every internal node v v v is reached with positive probability, so θ v = ν θ ( X i = 1 ∣ X < i = x v ) = p v \theta_v=\nu_\theta(X_i=1\mid X_{<i}=x_v)=p_v θ v = ν θ ( X i = 1 ∣ X < i = x v ) = p v for i − 1 = depth ( v ) i-1=\operatorname{depth}(v) i − 1 = depth ( v ) .
The maximizer is the vector of conditional marginal probabilities that self-reduction needs, and by (10) every branching rule gives a lower bound. This formulation does not yet yield the desired algorithm. It has 2 d − 1 2^d-1 2 d − 1 variables, and the probabilities ν θ ( v ) \nu_\theta(v) ν θ ( v ) in (3.1) are products along paths. The objective is not concave in θ \theta θ , even for log-supermodular laws: for d = 2 d=2 d = 2 and Φ ( x ) = 3 x 1 x 2 \Phi(x)=3x_1x_2 Φ ( x ) = 3 x 1 x 2 , its Hessian in the two branching probabilities on the path to ( 1 , 1 ) (1,1) ( 1 , 1 ) has determinant − 1 -1 − 1 at θ ≡ 1 2 \theta\equiv\frac{1}{2} θ ≡ 2 1 .
Using the probabilities ν ( v ) \nu(v) ν ( v ) , or equivalently the leaf law ν \nu ν , as variables restores concavity, but leaves an evaluation problem. Direct Monte Carlo evaluation of H ( ν ) = E ν [ − log ν ( X ) ] H(\nu)=\mathbb{E}_{\nu}[-\log\nu(X)] H ( ν ) = E ν [ − log ν ( X )] requires sampling from the candidate law and evaluating its probabilities. Rewriting this expectation under the uniform law on leaves introduces the weights 2 d ν ( x ) 2^d\nu(x) 2 d ν ( x ) , and the resulting integrand can have exponentially large second moment. We next drive every descent by the same independent uniform inputs. Thresholding a fresh input at each step expresses the entropy as an expectation under this fixed law. The expectation is linear in the map computing the descent and requires no evaluation of the induced leaf probabilities.
Linearizing the entropy
The linearization rests on an identity for a single bit. Let U U U be uniform on ( 0 , 1 ) (0,1) ( 0 , 1 ) , and let a ( u ) = log ( u / ( 1 − u ) ) a(u)=\log(u/(1-u)) a ( u ) = log ( u / ( 1 − u )) be the logit function . It is integrable, strictly increasing and antisymmetric, a ( 1 − u ) = − a ( u ) a(1-u)=-a(u) a ( 1 − u ) = − a ( u ) , so E a ( U ) = 0 \mathbb{E}a(U)=0 E a ( U ) = 0 . Since H ′ = − a H'=-a H ′ = − a on ( 0 , 1 ) (0,1) ( 0 , 1 ) ,
∫ c 1 a ( u ) d u = H ( c ) ( 0 ≤ c ≤ 1 ) . (12) \int_c^1 a(u)\,\mathrm{d}u=H(c) \qquad(0\le c\le1). \tag*{(12)} ∫ c 1 a ( u ) d u = H ( c ) ( 0 ≤ c ≤ 1 ) . (12)
We call E [ a ( U ) ϕ ( U ) ] = ∫ 0 1 a ϕ \mathbb{E}[a(U)\phi(U)]=\int_0^1 a\phi E [ a ( U ) ϕ ( U )] = ∫ 0 1 a ϕ the linear score of a bounded measurable function ϕ \phi ϕ on ( 0 , 1 ) (0,1) ( 0 , 1 ) . The threshold indicator 1 [ c , 1 ) \mathbf{1}_{[c,1)} 1 [ c , 1 ) , where c = 1 − p c=1-p c = 1 − p , equals 1 1 1 at U U U with probability p p p , and by (12) its linear score is the entropy of that bit:
E [ a ( U ) 1 { U ≥ 1 − p } ] = H ( p ) ( 0 ≤ p ≤ 1 ) . (13) \mathbb{E}[a(U)\mathbf{1}\{U\ge1-p\}]=H(p) \qquad(0\le p\le1). \tag*{(13)} E [ a ( U ) 1 { U ≥ 1 − p }] = H ( p ) ( 0 ≤ p ≤ 1 ) . (13)
The left side is linear in the indicator, whereas H ( p ) H(p) H ( p ) is concave in p p p . No other [ 0 , 1 ] [0,1] [ 0 , 1 ] -valued function with the same mean scores as much; this is the bathtub principle [61 Theorem 1.14] with its equality case.
Lemma 3.2 (Bathtub principle). If ϕ : ( 0 , 1 ) → [ 0 , 1 ] \phi:(0,1)\to[0,1] ϕ : ( 0 , 1 ) → [ 0 , 1 ] is measurable and ∫ 0 1 ϕ = p \int_0^1\phi=p ∫ 0 1 ϕ = p , then ∫ 0 1 a ϕ ≤ H ( p ) \int_0^1a\phi\le H(p) ∫ 0 1 a ϕ ≤ H ( p ) , with equality only if ϕ = 1 [ 1 − p , 1 ) \phi=\mathbf{1}_{[1-p,1)} ϕ = 1 [ 1 − p , 1 ) almost everywhere.
Proof. For p ∈ { 0 , 1 } p\in\{0,1\} p ∈ { 0 , 1 } , ϕ \phi ϕ equals the constant p = 1 [ 1 − p , 1 ) p=\mathbf{1}_{[1-p,1)} p = 1 [ 1 − p , 1 ) almost everywhere, and ∫ 0 1 a ϕ = 0 = H ( p ) \int_0^1a\phi=0=H(p) ∫ 0 1 a ϕ = 0 = H ( p ) . Otherwise put c = 1 − p c=1-p c = 1 − p and ψ = 1 [ c , 1 ) − ϕ \psi=\mathbf{1}_{[c,1)}-\phi ψ = 1 [ c , 1 ) − ϕ , so that ∫ ψ = 0 \int\psi=0 ∫ ψ = 0 , ψ ≥ 0 \psi\ge0 ψ ≥ 0 on [ c , 1 ) [c,1) [ c , 1 ) and ψ ≤ 0 \psi\le0 ψ ≤ 0 on ( 0 , c ) (0,c) ( 0 , c ) . Since a a a is increasing,
H ( p ) − ∫ 0 1 a ϕ = ∫ 0 1 a ψ = ∫ 0 1 ( a ( u ) − a ( c ) ) ψ ( u ) d u ≥ 0. H(p)-\int_0^1a\phi=\int_0^1a\psi=\int_0^1(a(u)-a(c))\psi(u)\,\mathrm{d}u\ge0. H ( p ) − ∫ 0 1 a ϕ = ∫ 0 1 a ψ = ∫ 0 1 ( a ( u ) − a ( c )) ψ ( u ) d u ≥ 0. The last integrand is nonnegative, and since a a a is strictly increasing it vanishes only where u = c u=c u = c or ψ ( u ) = 0 \psi(u)=0 ψ ( u ) = 0 ; so equality forces ψ = 0 \psi=0 ψ = 0 almost everywhere.
The identity (13) is also the one-bit case of Hazan and Jaakkola’s random-perturbation identity (Remark 3.7).
Encoding a descent. To apply (13) at every step of a descent, let U 1 , … , U d U_1,\ldots,U_d U 1 , … , U d be independent uniform inputs on ( 0 , 1 ) (0,1) ( 0 , 1 ) , one for each depth, and write U = ( U 1 , … , U d ) U=(U_1,\ldots,U_d) U = ( U 1 , … , U d ) . The threshold descent f θ f^\theta f θ of a branching rule θ \theta θ compares each fresh input with 1 − θ v 1-\theta_v 1 − θ v at the current node v v v . Let f = f p f=f^p f = f p be the threshold descent using the conditional marginal probabilities of μ \mu μ :
f i θ ( U ) = 1 { U i ≥ 1 − θ f < i θ ( U ) } , f i ( U ) = f i p ( U ) = 1 { U i ≥ 1 − p i ( f < i ( U ) ) } . (14) f_i^\theta(U)=\mathbf{1}\{U_i\ge1-\theta_{f^\theta_{<i}(U)}\},\qquad f_i(U)=f_i^p(U)=\mathbf{1}\{U_i\ge1-p_i(f_{<i}(U))\}. \tag*{(14)} f i θ ( U ) = 1 { U i ≥ 1 − θ f < i θ ( U ) } , f i ( U ) = f i p ( U ) = 1 { U i ≥ 1 − p i ( f < i ( U ))} . (14)
Because U i U_i U i is uniform on ( 0 , 1 ) (0,1) ( 0 , 1 ) and independent of U < i U_{<i} U < i , the conditional probability that f i θ ( U ) = 1 f_i^\theta(U)=1 f i θ ( U ) = 1 given U < i U_{<i} U < i is the branching probability of the node f < i θ ( U ) f^\theta_{<i}(U) f < i θ ( U ) , so f θ ( U ) f^\theta(U) f θ ( U ) has law ν θ \nu_\theta ν θ ; in particular f ( U ) f(U) f ( U ) has law μ \mu μ . The map f f f performs sequential inverse-transform sampling, the discrete analogue of the inverse Rosenblatt transformation [76 ] .
Lemma 3.3 (Entropy identity for threshold descents). *For every branching rule θ \theta θ , the threshold descent f θ f^\theta f θ takes values in { 0 , 1 } d \{0,1\}^d { 0 , 1 } d , its i i i th coordinate depends only on U 1 , … , U i U_1,\ldots,U_i U 1 , … , U i , and E [ a ( U i ) f i θ ( U ) ∣ U < i ] = H ( θ f < i θ ( U ) ) \mathbb{E}[a(U_i)f_i^\theta(U)\mid U_{<i}]=\mathrm{H}(\theta_{f^\theta_{<i}(U)}) E [ a ( U i ) f i θ ( U ) ∣ U < i ] = H ( θ f < i θ ( U ) ) for every i i i . Hence ∑ i E [ a ( U i ) f i θ ( U ) ] = H ( ν θ ) \sum_i\mathbb{E}[a(U_i)f_i^\theta(U)]=\mathrm{H}(\nu_\theta) ∑ i E [ a ( U i ) f i θ ( U )] = H ( ν θ ) , and adding E Φ ( f θ ( U ) ) \mathbb{E}\Phi(f^\theta(U)) E Φ ( f θ ( U )) gives the bracket in (11) . In particular ∑ i E [ a ( U i ) f i ( U ) ] = H ( μ ) \sum_i\mathbb{E}[a(U_i)f_i(U)]=\mathrm{H}(\mu) ∑ i E [ a ( U i ) f i ( U )] = H ( μ ) , and
∑ i = 1 d E [ a ( U i ) f i ( U ) ] + E Φ ( f ( U ) ) = log Z Φ . \sum_{i=1}^{d}\mathbb{E}[a(U_i)f_i(U)]+\mathbb{E}\Phi(f(U))=\log Z_\Phi. i = 1 ∑ d E [ a ( U i ) f i ( U )] + E Φ ( f ( U )) = log Z Φ .
Proof. The first two claims are immediate from (14) . The identity is (13) with p = θ f < i θ ( U ) p=\theta_{f^\theta_{<i}(U)} p = θ f < i θ ( U ) , which is a function of U < i U_{<i} U < i . Since f θ ( U ) f^\theta(U) f θ ( U ) has law ν θ \nu_\theta ν θ , summing over i i i gives ∑ v ν θ ( v ) H ( θ v ) = H ( ν θ ) \sum_v\nu_\theta(v)\mathrm{H}(\theta_v)=\mathrm{H}(\nu_\theta) ∑ v ν θ ( v ) H ( θ v ) = H ( ν θ ) by (9) , and E Φ ( f θ ( U ) ) = E ν θ Φ \mathbb{E}\Phi(f^\theta(U))=\mathbb{E}_{\nu_\theta}\Phi E Φ ( f θ ( U )) = E ν θ Φ . For θ = p \theta=p θ = p , Proposition 3.1 gives the value log Z Φ \log Z_\Phi log Z Φ .
Example 3.4 (Threshold descent on a path). Let G G G be the path r 1 v 1 r 2 v 2 r 3 r_1\,v_1\,r_2\,v_2\,r_3 r 1 v 1 r 2 v 2 r 3 with L = { v 1 , v 2 } L=\{v_1,v_2\} L = { v 1 , v 2 } , in this order, and R = { r 1 , r 2 , r 3 } R=\{r_1,r_2,r_3\} R = { r 1 , r 2 , r 3 } . Summing out R R R gives W ( ∅ ) = 8 W(\varnothing)=8 W ( ∅ ) = 8 , W ( { v 1 } ) = W ( { v 2 } ) = 2 W(\{v_1\})=W(\{v_2\})=2 W ({ v 1 }) = W ({ v 2 }) = 2 , and W ( { v 1 , v 2 } ) = 1 W(\{v_1,v_2\})=1 W ({ v 1 , v 2 }) = 1 , so Z ( G ) = 13 Z(G)=13 Z ( G ) = 13 . The conditional marginal probabilities are p 1 = 3 / 13 p_1=3/13 p 1 = 3/13 , p 2 ( 0 ) = 1 / 5 p_2(0)=1/5 p 2 ( 0 ) = 1/5 , and p 2 ( 1 ) = 1 / 3 p_2(1)=1/3 p 2 ( 1 ) = 1/3 . Thus f f f is given by
f 1 ( U ) = 1 { U 1 ≥ 10 / 13 } , f 2 ( U ) = { 1 { U 2 ≥ 4 / 5 } , U 1 < 10 / 13 , 1 { U 2 ≥ 2 / 3 } , U 1 ≥ 10 / 13. f_1(U)=\mathbf{1}\{U_1\ge10/13\},\qquad
f_2(U)=
\begin{cases}
\mathbf{1}\{U_2\ge4/5\}, & U_1<10/13,\\
\mathbf{1}\{U_2\ge2/3\}, & U_1\ge10/13.
\end{cases} f 1 ( U ) = 1 { U 1 ≥ 10/13 } , f 2 ( U ) = { 1 { U 2 ≥ 4/5 } , 1 { U 2 ≥ 2/3 } , U 1 < 10/13 , U 1 ≥ 10/13. By Lemma 3.3, with Φ = log ( W / 8 ) \Phi=\log(W/8) Φ = log ( W /8 ) ,
∑ i E [ a ( U i ) f i ( U ) ] + E Φ ( f ( U ) ) = log Z Φ = log ( 13 / 8 ) . \sum_i\mathbb{E}[a(U_i)f_i(U)]+\mathbb{E}\Phi(f(U))=\log Z_\Phi=\log(13/8). i ∑ E [ a ( U i ) f i ( U )] + E Φ ( f ( U )) = log Z Φ = log ( 13/8 ) . The second coordinate illustrates an interaction: its threshold for U 2 U_2 U 2 moves with the decision on U 1 U_1 U 1 , a dependence measured in § 7.1 and reduced by averaging in § 8 .
From threshold descents to guides. By Lemma 3.3, the bracket in (11) is a score that is linear in the descent f θ f^\theta f θ , plus an expected potential. This represents the objective under a fixed product law without evaluating the induced leaf probabilities. We now optimize over the map computing the descent instead of the branching probabilities. Threshold descents do not form a convex set: the average of 1 { U 1 ≥ 1 2 } \mathbf{1}\{U_1\ge\frac{1}{2}\} 1 { U 1 ≥ 2 1 } and 1 { U 1 ≥ 3 4 } \mathbf{1}\{U_1\ge\frac{3}{4}\} 1 { U 1 ≥ 4 3 } equals 1 2 \frac{1}{2} 2 1 on [ 1 2 , 3 4 ) [\frac{1}{2},\frac{3}{4}) [ 2 1 , 4 3 ) . To obtain a convex feasible set we allow maps with values in [ 0 , 1 ] d [0,1]^d [ 0 , 1 ] d .
Definition 3.5 (Guides). A guide is a measurable map F : ( 0 , 1 ) d → [ 0 , 1 ] d F:(0,1)^d\to[0,1]^d F : ( 0 , 1 ) d → [ 0 , 1 ] d whose i i i th coordinate depends only on U 1 , … , U i U_1,\ldots,U_i U 1 , … , U i . Its coordinates F i F_i F i are its rows , and its linear score is ∑ i = 1 d E [ a ( U i ) F i ( U ) ] \sum_{i=1}^d\mathbb{E}[a(U_i)F_i(U)] ∑ i = 1 d E [ a ( U i ) F i ( U )] . A guide is Boolean if its values lie in { 0 , 1 } d \{0,1\}^d { 0 , 1 } d .
We write F F F for a general guide and call f = f p f=f^p f = f p the exact guide of μ \mu μ . Every threshold descent is a Boolean guide, and by Lemma 3.3 its linear score is the entropy of its law. A general Boolean guide may depend on the full earlier input history and may use an arbitrary measurable set of values of the fresh input to decide its next bit.
We first prove that the variational bound remains valid for all Boolean guides. This is the form needed in § 6.3 , where general guides are expressed as averages of Boolean guides that need not be threshold descents. The restriction to earlier and current inputs is essential: choosing x x x after all inputs are revealed attains E max x [ Φ ( x ) + ∑ i a ( U i ) x i ] \mathbb{E}\max_x[\Phi(x)+\sum_i a(U_i)x_i] E max x [ Φ ( x ) + ∑ i a ( U i ) x i ] , which can exceed log Z Φ \log Z_\Phi log Z Φ (Remark 3.7 ).
Lemma 3.6 (Variational principle for Boolean guides). Let μ = e Φ / Z Φ \mu=e^\Phi/Z_\Phi μ = e Φ / Z Φ be a strictly positive law on { 0 , 1 } d \{0,1\}^d { 0 , 1 } d . Every Boolean guide F F F satisfies
∑ i = 1 d E [ a ( U i ) F i ( U ) ] + E Φ ( F ( U ) ) ≤ log Z Φ , (15) \sum_{i=1}^{d}\mathbb{E}[a(U_i)F_i(U)]+\mathbb{E}\Phi(F(U))\leq\log Z_\Phi, \tag*{(15)} i = 1 ∑ d E [ a ( U i ) F i ( U )] + E Φ ( F ( U )) ≤ log Z Φ , (15) with equality if and only if F = f F=f F = f almost everywhere. Thus log Z Φ \log Z_\Phi log Z Φ is the maximum of the left-hand side over Boolean guides, and the unique maximizer is the exact guide.
Proof. We express the deficit as a sum of two nonnegative losses at each step. By § 5.1 , applied to the weight e Φ e^\Phi e Φ , the masses satisfy Z o = Z Φ Z_o=Z_\Phi Z o = Z Φ , Z v = Z v 0 + Z v 1 Z_v=Z_{v0}+Z_{v1} Z v = Z v 0 + Z v 1 at internal nodes and log Z x = Φ ( x ) \log Z_x=\Phi(x) log Z x = Φ ( x ) at a leaf x x x , and p v = Z v 1 / Z v ∈ ( 0 , 1 ) p_v=Z_{v1}/Z_v\in(0,1) p v = Z v 1 / Z v ∈ ( 0 , 1 ) . Write Ber ( q ) \operatorname{Ber}(q) Ber ( q ) for the Bernoulli law of mean q q q . Since Z v 0 = ( 1 − p v ) Z v Z_{v0}=(1-p_v)Z_v Z v 0 = ( 1 − p v ) Z v and Z v 1 = p v Z v Z_{v1}=p_vZ_v Z v 1 = p v Z v , expanding relative entropy gives the one-step identity
H ( q ) + ( 1 − q ) log Z v 0 + q log Z v 1 = log Z v − KL ( Ber ( q ) ∥ Ber ( p v ) ) ( 0 ≤ q ≤ 1 ) . (16) H(q)+(1-q)\log Z_{v0}+q\log Z_{v1}=\log Z_v-\operatorname{KL}(\operatorname{Ber}(q)\mathbin{\|}\operatorname{Ber}(p_v))\qquad(0\leq q\leq1). \tag*{(16)} H ( q ) + ( 1 − q ) log Z v 0 + q log Z v 1 = log Z v − KL ( Ber ( q ) ∥ Ber ( p v )) ( 0 ≤ q ≤ 1 ) . (16)
The endpoint cases use 0 log 0 = 0 0\log0=0 0 log 0 = 0 .
Now write X = F ( U ) X=F(U) X = F ( U ) and q i = Pr ( X i = 1 ∣ U < i ) q_i=\Pr(X_i=1\mid U_{<i}) q i = Pr ( X i = 1 ∣ U < i ) . Given U < i U_{<i} U < i , the reached node X < i X_{<i} X < i is fixed. As a function of the fresh input U i U_i U i , the next bit X i X_i X i is the indicator of a measurable set, with mean q i q_i q i . Its rearrangement loss is nonnegative by Lemma 3.2 :
R i = H ( q i ) − E [ a ( U i ) X i ∣ U < i ] ≥ 0. (17) R_i=H(q_i)-\mathbb{E}[a(U_i)X_i\mid U_{<i}]\geq0. \tag*{(17)} R i = H ( q i ) − E [ a ( U i ) X i ∣ U < i ] ≥ 0. (17)
By (16) at v = X < i v=X_{<i} v = X < i with q = q i q=q_i q = q i , and by (17) ,
log Z X < i − E [ log Z X ≤ i ∣ U < i ] − E [ a ( U i ) X i ∣ U < i ] = R i + KL ( Ber ( q i ) ∥ Ber ( p i ( X < i ) ) ) . \log Z_{X_{<i}}-\mathbb{E}[\log Z_{X_{\leq i}}\mid U_{<i}]-\mathbb{E}[a(U_i)X_i\mid U_{<i}]=R_i+\operatorname{KL}(\operatorname{Ber}(q_i)\mathbin{\|}\operatorname{Ber}(p_i(X_{<i}))). log Z X < i − E [ log Z X ≤ i ∣ U < i ] − E [ a ( U i ) X i ∣ U < i ] = R i + KL ( Ber ( q i ) ∥ Ber ( p i ( X < i ))) .
Taking expectations and summing over i i i telescopes the masses from log Z o = log Z Φ \log Z_o=\log Z_\Phi log Z o = log Z Φ to log Z X = Φ ( X ) \log Z_X=\Phi(X) log Z X = Φ ( X ) , giving
log Z Φ − ∑ i = 1 d E [ a ( U i ) X i ] − E Φ ( X ) = ∑ i = 1 d E [ R i + KL ( Ber ( q i ) ∥ Ber ( p i ( X < i ) ) ) ] ] . (18) \log Z_\Phi-\sum_{i=1}^{d}\mathbb{E}[a(U_i)X_i]-\mathbb{E}\Phi(X)=\sum_{i=1}^{d}\mathbb{E}\left[R_i+\operatorname{KL}(\operatorname{Ber}(q_i)\mathbin{\|}\operatorname{Ber}(p_i(X_{<i})))]\right]. \tag*{(18)} log Z Φ − i = 1 ∑ d E [ a ( U i ) X i ] − E Φ ( X ) = i = 1 ∑ d E [ R i + KL ( Ber ( q i ) ∥ Ber ( p i ( X < i )))] ] . (18)
Both losses are nonnegative. They vanish for the exact guide, since its conditional mean is p i ( f < i ( U ) ) p_i(f_{<i}(U)) p i ( f < i ( U )) and each step is the maximizing threshold in Lemma 3.2 . Conversely, equality forces q i = p i ( X < i ) q_i=p_i(X_{<i}) q i = p i ( X < i ) and R i = 0 R_i=0 R i = 0 almost surely for every i i i . The equality case of Lemma 3.2 then gives F i ( U ) = 1 { U i ≥ 1 − p i ( F < i ( U ) ) } F_i(U)=1\{U_i\geq1-p_i(F_{<i}(U))\} F i ( U ) = 1 { U i ≥ 1 − p i ( F < i ( U ))} almost surely. Induction using (14) yields F = f F=f F = f almost everywhere.
Two Boolean guides with the same law can have different linear scores. The guide f ˇ \check{f} f ˇ with f ˇ i ( U ) = 1 { U i < p i ( f ˇ < i ( U ) ) } \check{f}_i(U)=1\{U_i<p_i(\check{f}_{<i}(U))\} f ˇ i ( U ) = 1 { U i < p i ( f ˇ < i ( U ))} samples μ \mu μ like the exact guide, but in (18) its Bernoulli relative entropies vanish and its rearrangement losses total 2 H ( μ ) 2H(\mu) 2 H ( μ ) , so its linear score is − H ( μ ) -H(\mu) − H ( μ ) : the left side of (15) depends on the guide, not only on its law.
The concave relaxation
Guides form the convex feasible set announced in § 6.2 . The linear score is already defined on this set; it remains to extend the potential to fractional points while preserving the variational bound. By the layer cake representation [61 Theorem 1.13] , a guide F F F is the average ∫ 0 1 1 { F > s } d s \int_0^1 1\{F>s\}\,ds ∫ 0 1 1 { F > s } d s of its layers 1 { F > s } = ( 1 { F i > s } ) i = 1 d 1\{F>s\}=(1\{F_i>s\})_{i=1}^d 1 { F > s } = ( 1 { F i > s } ) i = 1 d , which are Boolean guides. Equivalently, take U 0 U_0 U 0 uniform on ( 0 , 1 ) (0,1) ( 0 , 1 ) , independently of U U U , and set X = 1 { F ( U ) > U 0 } X=1\{F(U)>U_0\} X = 1 { F ( U ) > U 0 } . Then F i ( U ) = Pr ( X i = 1 ∣ U ) F_i(U)=\Pr(X_i=1\mid U) F i ( U ) = Pr ( X i = 1 ∣ U ) for every i i i . We extend the objective in (15) by averaging over these layers. For a constant guide z ∈ [ 0 , 1 ] d z\in[0,1]^d z ∈ [ 0 , 1 ] d , whose linear score is zero, this gives the potential value ∫ 0 1 Φ ( 1 { z > s } ) d s \int_0^1\Phi(1\{z>s\})\,ds ∫ 0 1 Φ ( 1 { z > s }) d s at z z z . This is the Lovász extension (L2) below, which is computed from d + 1 d+1 d + 1 values of Φ \Phi Φ and is concave exactly when μ \mu μ is log-supermodular (L3).
We define the extension on all of R d \mathbb{R}^d R d , because the search of § 7.2 evaluates it at points outside [ 0 , 1 ] d [0,1]^d [ 0 , 1 ] d . For z ∈ R d z\in\mathbb{R}^d z ∈ R d , order its coordinates as z j 1 ≥ ⋯ ≥ z j d z_{j_1}\ge\cdots\ge z_{j_d} z j 1 ≥ ⋯ ≥ z j d , put S t = { j 1 , … , j t } S_t=\{j_1,\ldots,j_t\} S t = { j 1 , … , j t } , with S 0 = ∅ S_0=\varnothing S 0 = ∅ , and define the Lovász extension [65 ]
Φ L ( z ) = ∑ t = 1 d z j t ( Φ ( S t ) − Φ ( S t − 1 ) ) ; (19) \Phi^{\mathrm{L}}(z)=\sum_{t=1}^{d}z_{j_t}\bigl(\Phi(S_t)-\Phi(S_{t-1})\bigr); \tag*{(19)} Φ L ( z ) = t = 1 ∑ d z j t ( Φ ( S t ) − Φ ( S t − 1 ) ) ; (19)
ties may be broken arbitrarily.
A marginal difference of Φ \Phi Φ is a value Φ ( x ∨ e j ) − Φ ( x ) \Phi(x\vee e_j)-\Phi(x) Φ ( x ∨ e j ) − Φ ( x ) , and Φ \Phi Φ is supermodular if Φ ( x ∧ y ) + Φ ( x ∨ y ) ≥ Φ ( x ) + Φ ( y ) \Phi(x\wedge y)+\Phi(x\vee y)\ge\Phi(x)+\Phi(y) Φ ( x ∧ y ) + Φ ( x ∨ y ) ≥ Φ ( x ) + Φ ( y ) for all x , y x,y x , y , that is, if μ \mu μ is log-supermodular. We use five standard facts from [65 ] and [2 Definition 3.1 and Propositions 3.1, 3.2 and 3.6] , stated here for supermodular functions. (L1), (L2) and (L4) hold for every potential with Φ ( 0 ) = 0 \Phi(0)=0 Φ ( 0 ) = 0 .
(L1) Φ L ( 1 S ) = Φ ( S ) \Phi^{\mathrm{L}}(1_S)=\Phi(S) Φ L ( 1 S ) = Φ ( S ) for every set S S S , by telescoping.
(L2) For z ∈ [ 0 , 1 ] d z\in[0,1]^d z ∈ [ 0 , 1 ] d , Φ L ( z ) = ∫ 0 1 Φ ( 1 { z > s } ) d s \Phi^{\mathrm{L}}(z)=\int_0^1\Phi(1\{z>s\})\,ds Φ L ( z ) = ∫ 0 1 Φ ( 1 { z > s }) d s , where 1 { z > s } = ( 1 { z i > s } ) i = 1 d 1\{z>s\}=(1\{z_i>s\})_{i=1}^d 1 { z > s } = ( 1 { z i > s } ) i = 1 d : this layer equals S t S_t S t for z j t + 1 < s ≤ z j t z_{j_{t+1}}<s\le z_{j_t} z j t + 1 < s ≤ z j t (0 ≤ t ≤ d 0\le t\le d 0 ≤ t ≤ d , with z j 0 = 1 z_{j_0}=1 z j 0 = 1 and z j d + 1 = 0 z_{j_{d+1}}=0 z j d + 1 = 0 ), and summation by parts gives (19) . (L3) If Φ \Phi Φ is supermodular, then Φ L \Phi^{\mathrm{L}} Φ L is concave on all of R d \mathbb{R}^{d} R d , and at every z z z the vector of chain increments in (19) , for any ordering of z z z , is a supergradient. Conversely, concavity of Φ L \Phi^{\mathrm{L}} Φ L forces supermodularity.
(L4) If every marginal difference of Φ \Phi Φ has absolute value at most Λ \Lambda Λ , then so does every chain increment in (19) ; since Φ L \Phi^{\mathrm{L}} Φ L is continuous and linear wherever the order of the coordinates is fixed, ∣ Φ L ( z ) − Φ L ( z ′ ) ∣ ≤ Λ ∥ z − z ′ ∥ 1 \lvert\Phi^{\mathrm{L}}(z)-\Phi^{\mathrm{L}}(z^{\prime})\rvert\leq\Lambda\lVert z-z^{\prime}\rVert_{1} ∣ Φ L ( z ) − Φ L ( z ′ )∣ ≤ Λ ∥ z − z ′ ∥ 1 .
(L5) If Φ \Phi Φ is supermodular and X X X is a random Boolean vector, then E Φ ( X ) = E Φ L ( X ) ≤ Φ L ( E X ) \mathbb{E}\Phi(X)=\mathbb{E}\Phi^{\mathrm{L}}(X)\leq\Phi^{\mathrm{L}}(\mathbb{E}X) E Φ ( X ) = E Φ L ( X ) ≤ Φ L ( E X ) , by (L1), (L3) and Jensen’s inequality.
By (L5) and (L2), for supermodular Φ \Phi Φ and z ∈ [ 0 , 1 ] d z\in[0,1]^{d} z ∈ [ 0 , 1 ] d , Φ L ( z ) \Phi^{\mathrm{L}}(z) Φ L ( z ) is the largest E Φ ( X ) \mathbb{E}\Phi(X) E Φ ( X ) over random Boolean vectors X X X with mean z z z . The maximum is attained by X = 1 { z > U 0 } X=\mathbf{1}\{z>U_{0}\} X = 1 { z > U 0 } . Thus Φ L \Phi^{\mathrm{L}} Φ L is the concave closure of Φ \Phi Φ on [ 0 , 1 ] d [0,1]^{d} [ 0 , 1 ] d [2 Section 5.1] . For independent sets with the right side summed out, Φ ( S ) = − ∣ N ( S ) ∣ log 2 \Phi(S)=-\lvert N(S)\rvert\log2 Φ ( S ) = − ∣ N ( S )∣ log 2 and Φ L ( z ) = − log 2 ∑ r ∈ R max v ∈ N ( r ) z v \Phi^{\mathrm{L}}(z)=-\log2\sum_{r\in R}\max_{v\in N(r)}z_{v} Φ L ( z ) = − log 2 ∑ r ∈ R max v ∈ N ( r ) z v , an empty maximum being zero.
The variational objective. Using this extension, define the objective of a guide F F F by
P ( F ) = ∑ i = 1 d E [ a ( U i ) F i ( U ) ] + E Φ L ( F ( U ) ) . (20) \mathcal{P}(F)=\sum_{i=1}^{d}\mathbb{E}[a(U_{i})F_{i}(U)]+\mathbb{E}\Phi^{\mathrm{L}}(F(U)). \tag*{(20)} P ( F ) = i = 1 ∑ d E [ a ( U i ) F i ( U )] + E Φ L ( F ( U )) . (20)
The last term is the potential term . We call P \mathcal{P} P the variational objective and P ( F ) \mathcal{P}(F) P ( F ) the objective value of F F F . Both terms are finite because a a a is integrable and Φ L ( F ( U ) ) \Phi^{\mathrm{L}}(F(U)) Φ L ( F ( U )) is bounded. We call log Z Φ − P ( F ) \log Z_{\Phi}-\mathcal{P}(F) log Z Φ − P ( F ) the objective gap of F F F .
Proposition 3.8 (Exactness and concavity of the relaxation). Every guide F F F satisfies P ( F ) ≤ log Z Φ \mathcal{P}(F)\leq\log Z_{\Phi} P ( F ) ≤ log Z Φ , with equality if and only if F = f F=f F = f almost everywhere. The objective is concave on the convex set of these guides if and only if Φ \Phi Φ is supermodular, that is, if and only if μ \mu μ is log-supermodular.
Proof. Write F = ∫ 0 1 1 { F > s } d s F=\int_{0}^{1}\mathbf{1}\{F>s\}\,\mathrm{d}s F = ∫ 0 1 1 { F > s } d s as above; for each s ∈ [ 0 , 1 ) s\in[0,1) s ∈ [ 0 , 1 ) the layer 1 { F > s } \mathbf{1}\{F>s\} 1 { F > s } is a Boolean guide. The score is linear in F F F , Φ L ( F ) = ∫ 0 1 Φ ( 1 { F > s } ) d s \Phi^{\mathrm{L}}(F)=\int_{0}^{1}\Phi(\mathbf{1}\{F>s\})\,\mathrm{d}s Φ L ( F ) = ∫ 0 1 Φ ( 1 { F > s }) d s by (L2), and by (L1) the objective P \mathcal{P} P agrees on Boolean guides with the left side of (15) . Since ∣ a ( U i ) 1 { F i > s } ∣ ≤ ∣ a ( U i ) ∣ \lvert a(U_{i})\mathbf{1}\{F_{i}>s\}\rvert\leq\lvert a(U_{i})\rvert ∣ a ( U i ) 1 { F i > s }∣ ≤ ∣ a ( U i )∣ is integrable and Φ \Phi Φ is bounded, Fubini’s theorem and Lemma 3.6 give
P ( F ) = ∫ 0 1 P ( 1 { F > s } ) d s ≤ log Z Φ , (21) \mathcal{P}(F)=\int_{0}^{1}\mathcal{P}(\mathbf{1}\{F>s\})\,\mathrm{d}s\leq\log Z_{\Phi}, \tag*{(21)} P ( F ) = ∫ 0 1 P ( 1 { F > s }) d s ≤ log Z Φ , (21) and P ( f ) = log Z Φ \mathcal{P}(f)=\log Z_{\Phi} P ( f ) = log Z Φ by Lemma 3.3. If P ( F ) = log Z Φ \mathcal{P}(F)=\log Z_{\Phi} P ( F ) = log Z Φ , then for almost every s ∈ [ 0 , 1 ) s\in[0,1) s ∈ [ 0 , 1 ) the layer attains equality, so 1 { F > s } = f \mathbf{1}\{F>s\}=f 1 { F > s } = f almost everywhere by Lemma 3.6. By Fubini’s theorem, for almost every u u u and every i i i we have 1 { F i ( u ) > s } = f i ( u ) \mathbf{1}\{F_{i}(u)>s\}=f_{i}(u) 1 { F i ( u ) > s } = f i ( u ) for almost every s ∈ [ 0 , 1 ) s\in[0,1) s ∈ [ 0 , 1 ) ; since F i ( u ) ∈ [ 0 , 1 ] F_{i}(u)\in[0,1] F i ( u ) ∈ [ 0 , 1 ] , this forces F i ( u ) = f i ( u ) F_{i}(u)=f_{i}(u) F i ( u ) = f i ( u ) .
If Φ \Phi Φ is supermodular, then Φ L \Phi^{\mathrm{L}} Φ L is concave by (L3), and so are the potential term and P \mathcal{P} P . Conversely, following [2 Proposition 3.6] , a constant guide F ≡ z ∈ [ 0 , 1 ] d F\equiv z\in[0,1]^{d} F ≡ z ∈ [ 0 , 1 ] d has linear score zero, because E a ( U i ) = 0 \mathbb{E}a(U_{i})=0 E a ( U i ) = 0 , so P ( z ) = Φ L ( z ) \mathcal{P}(z)=\Phi^{\mathrm{L}}(z) P ( z ) = Φ L ( z ) . For sets S S S and T T T , the layers of z = 1 2 ( 1 S + 1 T ) z=\frac{1}{2}(\mathbf{1}_{S}+\mathbf{1}_{T}) z = 2 1 ( 1 S + 1 T ) are S ∪ T S\cup T S ∪ T for s < 1 2 s<\frac{1}{2} s < 2 1 and S ∩ T S\cap T S ∩ T for s ≥ 1 2 s\geq\frac{1}{2} s ≥ 2 1 , so by (L1) and (L2), concavity of P \mathcal{P} P on constant guides gives
1 2 Φ ( S ∪ T ) + 1 2 Φ ( S ∩ T ) = Φ L ( z ) ≥ 1 2 Φ L ( 1 S ) + 1 2 Φ L ( 1 T ) = 1 2 Φ ( S ) + 1 2 Φ ( T ) , \frac{1}{2}\Phi(S\cup T)+\frac{1}{2}\Phi(S\cap T)=\Phi^{\mathrm{L}}(z)\geq\frac{1}{2}\Phi^{\mathrm{L}}(\mathbf{1}_{S})+\frac{1}{2}\Phi^{\mathrm{L}}(\mathbf{1}_{T})=\frac{1}{2}\Phi(S)+\frac{1}{2}\Phi(T), 2 1 Φ ( S ∪ T ) + 2 1 Φ ( S ∩ T ) = Φ L ( z ) ≥ 2 1 Φ L ( 1 S ) + 2 1 Φ L ( 1 T ) = 2 1 Φ ( S ) + 2 1 Φ ( T ) , which is supermodularity.
Averaging Boolean guides. When Φ \Phi Φ is supermodular, averaging Boolean guides cannot increase their average objective gap. The guides constructed in Section 5 use this property. Let ξ \xi ξ be independent of U U U , and let X X X be a random Boolean vector with each X i X_i X i a function of ( U ≤ i , ξ ) (U_{\leq i},\xi) ( U ≤ i , ξ ) . The average g ( U ) = E [ X ∣ U ] g(U)=\mathbb{E}[X\mid U] g ( U ) = E [ X ∣ U ] is a guide, and averaging preserves the linear score. Applying (L5) conditionally on U U U , then taking expectations, gives E Φ L ( g ( U ) ) ≥ E Φ ( X ) \mathbb{E}\Phi^{\mathrm{L}}(g(U))\geq\mathbb{E}\Phi(X) E Φ L ( g ( U )) ≥ E Φ ( X ) . Thus
P ( g ) ≥ E ξ P ( X ( ⋅ , ξ ) ) . (22) \mathcal{P}(g)\geq\mathbb{E}_{\xi}\mathcal{P}(X(\cdot,\xi)). \tag*{(22)} P ( g ) ≥ E ξ P ( X ( ⋅ , ξ )) . (22)
By (3.11) for each fixed ξ \xi ξ , the objective gap of g g g is therefore at most the average over ξ \xi ξ of the rearrangement losses and Bernoulli relative entropies of the Boolean guide X ( ⋅ , ξ ) X(\cdot,\xi) X ( ⋅ , ξ ) . In ordinary resampling and in threshold smoothing (Section 5), each X ( ⋅ , ξ ) X(\cdot,\xi) X ( ⋅ , ξ ) is the threshold descent of a branching rule, so its rearrangement losses vanish. When X ∼ μ X\sim\mu X ∼ μ under the joint law of ( U , ξ ) (U,\xi) ( U , ξ ) , as in both constructions, the potential inequality above and H ( μ ) + E μ Φ = log Z Φ H(\mu)+\mathbb{E}_{\mu}\Phi=\log Z_{\Phi} H ( μ ) + E μ Φ = log Z Φ give
0 ≤ log Z Φ − P ( g ) ≤ H ( μ ) − ∑ i = 1 d E [ a ( U i ) g i ( U ) ] . 0\leq\log Z_{\Phi}-\mathcal{P}(g)\leq H(\mu)-\sum_{i=1}^{d}\mathbb{E}[a(U_i)g_i(U)]. 0 ≤ log Z Φ − P ( g ) ≤ H ( μ ) − i = 1 ∑ d E [ a ( U i ) g i ( U )] .
Sampling from a guide. Every guide F F F also defines a sampler, for every potential: X = 1 { F ( U ) > U 0 } X=\mathbf{1}\{F(U)>U_0\} X = 1 { F ( U ) > U 0 } has a law ν \nu ν with KL ( ν ∥ μ ) ≤ log Z Φ − P ( F ) \operatorname{KL}(\nu\mathbin{\|}\mu)\leq\log Z_{\Phi}-\mathcal{P}(F) KL ( ν ∥ μ ) ≤ log Z Φ − P ( F ) , by (3.11) for each layer, (3.14), the chain rule and the convexity of relative entropy.
For the coarse objective gaps used here, this bound does not guarantee small total variation distance. We therefore use Section 2 to turn lower estimates into samples through the tree walk. Section 4 optimizes a finite-dimensional version of P \mathcal{P} P from samples and turns the value it finds into a lower estimate of log Z Φ \log Z_{\Phi} log Z Φ .
Constructing the coarse estimator
We turn the variational formulation developed in the previous section (Proposition 3.8) into an algorithm for the coarse lower estimates (2.3) required by our counting and sampling algorithms. We first use the Hoeffding decomposition to measure interactions among the independent inputs (Section 4.1). We then discretize the inputs and restrict to low interaction degree to obtain a finite-dimensional concave optimization problem (Section 4.2). The accuracy guarantee assumes the existence of a nearly optimal guide with small high-degree tails. Such a guide is used only to show that the search space contains a good candidate; the algorithm optimizes and validates candidates using independent uniform inputs and evaluations of the weight W W W . Section 5 constructs guides satisfying the required bounds.
Throughout this section, W W W is log-supermodular and satisfies the evaluator and value-length assumptions of Theorem 1.2. Its normalized potential Φ = log ( W / W ( 0 ) ) \Phi=\log(W/W(0)) Φ = log ( W / W ( 0 )) is supermodular, with Z Φ = Z W / W ( 0 ) Z_{\Phi}=Z_W/W(0) Z Φ = Z W / W ( 0 ) and μ = μ W \mu=\mu_W μ = μ W . The value-length bound gives 2 − B < W ( x ) < 2 B 2^{-B}<W(x)<2^B 2 − B < W ( x ) < 2 B , so every marginal difference of Φ \Phi Φ has absolute value at most Λ = 2 B \Lambda=2B Λ = 2 B . Every residual W v W_v W v likewise has a supermodular normalized potential Φ v = log ( W v / W v ( 0 ) ) \Phi_v=\log(W_v/W_v(0)) Φ v = log ( W v / W v ( 0 )) . Its marginal differences are those of log W \log W log W with the prefix fixed, so the same bound Λ \Lambda Λ applies.
Interaction degree
Let ϕ ∈ L 2 ( ( 0 , 1 ) d ) \phi\in L^2((0,1)^d) ϕ ∈ L 2 (( 0 , 1 ) d ) be a function of independent uniform inputs. For j ∈ [ d ] j\in[d] j ∈ [ d ] let E j E_j E j integrate out coordinate j j j , and for S ⊆ [ d ] S\subseteq[d] S ⊆ [ d ] put
ϕ S = ∏ j ∈ S ( I − E j ) ∏ j ∉ S E j ϕ . (23) \phi_S=\prod_{j\in S}(I-E_j)\prod_{j\notin S}E_j\phi. \tag*{(23)} ϕ S = j ∈ S ∏ ( I − E j ) j ∈ / S ∏ E j ϕ . (23)
where I I I is the identity. These are the components of the Hoeffding decomposition ϕ = ∑ S ϕ S \phi= \sum_S \phi_S ϕ = ∑ S ϕ S [45 , 29 ] , also called the Efron–Stein or functional ANOVA decomposition, and presented as the orthogonal decomposition in [71 §8.3] . The component ϕ S \phi_S ϕ S depends only on the coordinates in S S S and has mean zero in each of them, and distinct components are orthogonal.
We call ∥ ϕ S ∥ 2 2 \lVert\phi_S\rVert_2^2 ∥ ϕ S ∥ 2 2 the interaction energy on S S S . For an integer D ≥ 0 D \ge0 D ≥ 0 , the function ϕ \phi ϕ has interaction degree at most D D D if ϕ S = 0 \phi_S = 0 ϕ S = 0 whenever ∣ S ∣ > D |S| > D ∣ S ∣ > D . Write Π > D ϕ = ∑ ∣ S ∣ > D ϕ S \Pi_{>D}\phi= \sum_{|S|>D}\phi_S Π > D ϕ = ∑ ∣ S ∣ > D ϕ S for its degree-D D D tail, and Π ≤ D = I − Π > D \Pi_{\le D} = I - \Pi_{>D} Π ≤ D = I − Π > D . By orthogonality, Π ≤ D ϕ \Pi_{\le D}\phi Π ≤ D ϕ is the best L 2 L^2 L 2 approximation of interaction degree at most D D D , with squared error ∥ Π > D ϕ ∥ 2 2 = ∑ ∣ S ∣ > D ∥ ϕ S ∥ 2 2 \lVert\Pi_{>D}\phi\rVert_2^2 = \sum_{|S|>D}\lVert\phi_S\rVert_2^2 ∥ Π > D ϕ ∥ 2 2 = ∑ ∣ S ∣ > D ∥ ϕ S ∥ 2 2 . These degrees and squared norms correspond to Fourier degree, weight and high-degree weight on the Boolean cube and finite product spaces [71 Definitions 1.17, 8.32 and 8.38 and Proposition 8.33] . Interaction degree counts the input coordinates in a component, not powers of their values or their binary digits. In Example 3.4, the second row has a nonzero component on { 1 , 2 } \{1,2\} { 1 , 2 } .
To represent low-degree functions with finitely many coefficients, we partition each input interval into finitely many bins. Averaging a function over each product of bins gives a function of the bin indices alone. This averaging does not increase high-degree tail norms. Indeed, any linear operator T T T that commutes with every E j E_j E j satisfies ( T ϕ ) S = T ϕ S (T\phi)_S = T\phi_S ( T ϕ ) S = T ϕ S for every S S S . If T T T is also an L 2 L^2 L 2 contraction, then ∥ Π > D T ϕ ∥ 2 ≤ ∥ Π > D ϕ ∥ 2 \lVert\Pi_{>D}T\phi\rVert_2 \le\lVert\Pi_{>D}\phi\rVert_2 ∥ Π > D T ϕ ∥ 2 ≤ ∥ Π > D ϕ ∥ 2 . Bin averaging has both properties (§ 7.2 ). We will also use this observation for the noise operator , which averages a function over independent choices to keep or resample each input (§ 8.1 ).
From guides to coarse estimates
Fix d ≥ 2 d \ge2 d ≥ 2 , B ≥ 1 B \ge1 B ≥ 1 and an integer 0 ≤ D ≤ d 0 \le D \le d 0 ≤ D ≤ d , put Λ = 2 B \Lambda= 2B Λ = 2 B , and let v v v be a node of the self-reduction tree of W W W whose residual has k ≥ 1 k \ge1 k ≥ 1 free coordinates, identified with positions 1 , … , k 1,\ldots,k 1 , … , k in the inherited order. Write Φ = Φ v \Phi= \Phi_v Φ = Φ v . The guide and its interaction decomposition use these k k k inputs. We allocate the additive slack 1 / 8 1/8 1/8 as 1 / 32 1/32 1/32 for binning and truncation, 1 / 16 1/16 1/16 for optimization, and 1 / 32 1/32 1/32 for validation. The following parameters depend only on the original dimension d d d and the bound B B B , uniformly over all residuals:
s = min { j ≥ 0 : 2 j ≥ 64 d } , m = 4 s , A 0 = log m + 1 , G 0 = A 0 + 2 Λ , κ = min { j ≥ 0 : 2 j ≥ 64 d G 0 } . (24) \begin{aligned}
s &= \min\{j \ge0 : 2^j \ge64d\}, \qquad m = 4^s, \qquad A_0 = \log m + 1,\\
G_0 &= A_0 + 2\Lambda, \qquad\kappa= \min\{j \ge0 : 2^j \ge64dG_0\}. \tag*{(24)}
\end{aligned} s G 0 = min { j ≥ 0 : 2 j ≥ 64 d } , m = 4 s , A 0 = log m + 1 , = A 0 + 2Λ , κ = min { j ≥ 0 : 2 j ≥ 64 d G 0 } . (24)
Both minima are over nonnegative integers. Thus ( 64 d ) 2 ≤ m < ( 128 d ) 2 (64d)^2 \le m < (128d)^2 ( 64 d ) 2 ≤ m < ( 128 d ) 2 and κ = O ( log ( d + B ) ) \kappa= O(\log(d+B)) κ = O ( log ( d + B )) . Here m m m is the number of bins per input, A 0 A_0 A 0 bounds the bin scores (Lemma 4.2), G 0 G_0 G 0 bounds the absolute slope of the objective in each row (Lemma 4.3), and e − κ ≤ 1 / ( 64 d G 0 ) e^{-\kappa} \le1/(64dG_0) e − κ ≤ 1/ ( 64 d G 0 ) . The auxiliary parameter κ \kappa κ will be used in § 8 to choose D D D so that the required tail bound holds.
Suppose that there is a guide g g g on k k k inputs for which
log Z Φ − P ( g ) ≤ b ∗ , ∥ Π > D g i ∥ 2 ≤ 1 128 d G 0 ( 1 ≤ i ≤ k ) . (25) \log Z_{\Phi} - \mathcal{P}(g) \le b_*, \qquad\lVert\Pi_{>D}g_i\rVert_2 \le\frac{1}{128dG_0} \quad(1 \le i \le k). \tag*{(25)} log Z Φ − P ( g ) ≤ b ∗ , ∥ Π > D g i ∥ 2 ≤ 128 d G 0 1 ( 1 ≤ i ≤ k ) . (25)
Here, b ∗ ≥ 0 b_* \ge0 b ∗ ≥ 0 is a known bound. The guide g g g may depend on the residual, while b ∗ b_* b ∗ and D D D are common to all residuals. The first inequality controls the achievable additive error; the second ensures that low-degree truncation loses at most 1 / 128 1/128 1/128 of objective value (Lemma 4.4 ). We call such a guide a witness : it is used only to prove that a good coefficient vector exists, and the algorithm does not evaluate it.
Theorem 4.1 (Estimator from a guide). If (4.2) holds for every residual, then for every node v v v and 0 < δ ≤ 1 / 2 0 < \delta\le1/2 0 < δ ≤ 1/2 a randomized algorithm returns A v ∈ [ 0 , d ( 1 + 2 B ) ] A_v \in[0,d(1+2B)] A v ∈ [ 0 , d ( 1 + 2 B )] such that
Pr [ log Z Φ v − b ∗ − 1 8 ≤ A v ≤ log Z Φ v ] ≥ 1 − δ . \Pr\left[\log Z_{\Phi_v} - b_* - \frac{1}{8} \le A_v \le\log Z_{\Phi_v}\right] \ge1-\delta. Pr [ log Z Φ v − b ∗ − 8 1 ≤ A v ≤ log Z Φ v ] ≥ 1 − δ .
At leaves it returns 0. Every execution costs at most
exp ( O ( ( D + 1 ) log d ) ) poly ( d , B , T W , log ( 1 / δ ) ) (26) \exp(O((D+1)\log d))\operatorname{poly}(d,B,T_W,\log(1/\delta)) \tag*{(26)} exp ( O (( D + 1 ) log d )) poly ( d , B , T W , log ( 1/ δ )) (26)
operations and uniform draws.
To prove Theorem 4.1, we construct a concave objective bounded above by log Z Φ \log Z_{\Phi} log Z Φ , show that its low-degree search space contains a good candidate, and optimize and validate candidate values using independent samples. Throughout the proof, v v v , k k k , Φ = Φ v \Phi=\Phi_v Φ = Φ v and Λ = 2 B \Lambda=2B Λ = 2 B are as above.
A sound concave objective. Divide each input interval into m m m equal bins and put Y i = ⌊ m U i ⌋ ∈ { 0 , … , m − 1 } Y_i=\lfloor mU_i\rfloor\in\{0,\ldots,m-1\} Y i = ⌊ m U i ⌋ ∈ { 0 , … , m − 1 } for 1 ≤ i ≤ k 1\le i\le k 1 ≤ i ≤ k . The variables Y i Y_i Y i are independent and uniform. Low-degree truncation need not preserve the range [ 0 , 1 ] [0,1] [ 0 , 1 ] . For optimization, a candidate is therefore a vector u = ( u 1 , … , u k ) u=(u_1,\ldots,u_k) u = ( u 1 , … , u k ) whose i i i th row is a real-valued function u i ( Y 1 , … , Y i ) u_i(Y_1,\ldots,Y_i) u i ( Y 1 , … , Y i ) . Clipping its rows to [ 0 , 1 ] [0,1] [ 0 , 1 ] produces a guide.
For a function of the bins, replacing a ( U i ) a(U_i) a ( U i ) by its conditional mean preserves the linear score. The score of bin j j j is
a ˉ j = m ∫ j / m ( j + 1 ) / m a ( t ) d t = m [ H ( j / m ) − H ( ( j + 1 ) / m ) ] , \bar a_j=m\int_{j/m}^{(j+1)/m}a(t)\,\mathrm{d}t=m\left[H(j/m)-H((j+1)/m)\right], a ˉ j = m ∫ j / m ( j + 1 ) / m a ( t ) d t = m [ H ( j / m ) − H (( j + 1 ) / m ) ] ,
since H ′ = − a H'=-a H ′ = − a on ( 0 , 1 ) (0,1) ( 0 , 1 ) . The following bounds control the size of these scores and the score error when a guide is averaged over bins.
Lemma 4.2 (Bin scores). The bin scores satisfy max j ∣ a ˉ j ∣ ≤ A 0 \max_j|\bar a_j|\le A_0 max j ∣ a ˉ j ∣ ≤ A 0 and E ∣ a ( U 1 ) − a ˉ Y 1 ∣ ≤ ( 2 log m + 6 ) / m \mathbb{E}|a(U_1)-\bar a_{Y_1}|\le(2\log m+6)/m E ∣ a ( U 1 ) − a ˉ Y 1 ∣ ≤ ( 2 log m + 6 ) / m .
Proof. Since a ( 1 − t ) = − a ( t ) a(1-t)=-a(t) a ( 1 − t ) = − a ( t ) , we have a ˉ m − 1 − j = − a ˉ j \bar a_{m-1-j}=-\bar a_j a ˉ m − 1 − j = − a ˉ j . The interior bins lie in [ 1 / m , 1 − 1 / m ] [1/m,1-1/m] [ 1/ m , 1 − 1/ m ] , where ∣ a ∣ ≤ log ( m − 1 ) |a|\le\log(m-1) ∣ a ∣ ≤ log ( m − 1 ) . For the first bin, m ∫ 0 1 / m log t d t = − log m − 1 m\int_0^{1/m}\log t\,\mathrm{d}t=-\log m-1 m ∫ 0 1/ m log t d t = − log m − 1 and 0 ≤ − m ∫ 0 1 / m log ( 1 − t ) d t ≤ − log ( 1 − 1 / m ) ≤ 2 / m 0\le-m\int_0^{1/m}\log(1-t)\,\mathrm{d}t\le-\log(1-1/m)\le2/m 0 ≤ − m ∫ 0 1/ m log ( 1 − t ) d t ≤ − log ( 1 − 1/ m ) ≤ 2/ m , so a ˉ 0 ∈ [ − A 0 , − A 0 + 2 / m ] \bar a_0\in[-A_0,-A_0+2/m] a ˉ 0 ∈ [ − A 0 , − A 0 + 2/ m ] . This proves the first bound.
An increasing function ϕ \phi ϕ with mean ϕ ˉ \bar\phi ϕ ˉ on an interval of length 1 / m 1/m 1/ m satisfies ∫ ∣ ϕ − ϕ ˉ ∣ = 2 ∫ ( ϕ − ϕ ˉ ) + ≤ 2 m ( sup ϕ − ϕ ˉ ) \int|\phi-\bar\phi|=2\int(\phi-\bar\phi)_+\le\frac{2}{m}(\sup\phi-\bar\phi) ∫ ∣ ϕ − ϕ ˉ ∣ = 2 ∫ ( ϕ − ϕ ˉ ) + ≤ m 2 ( sup ϕ − ϕ ˉ ) , and likewise with ϕ ˉ − inf ϕ \bar\phi-\inf\phi ϕ ˉ − inf ϕ ; hence ∫ ∣ ϕ − ϕ ˉ ∣ \int|\phi-\bar\phi| ∫ ∣ ϕ − ϕ ˉ ∣ is at most 1 / m 1/m 1/ m times the oscillation of ϕ \phi ϕ . The oscillations of a a a over the interior bins sum to a ( 1 − 1 / m ) − a ( 1 / m ) = 2 log ( m − 1 ) a(1-1/m)-a(1/m)=2\log(m-1) a ( 1 − 1/ m ) − a ( 1/ m ) = 2 log ( m − 1 ) . For the boundary bins, we use the one-sided bound. On the first bin sup a − a ˉ 0 ≤ − log ( m − 1 ) + log m + 1 ≤ 1 + 2 / m \sup a-\bar a_0\le-\log(m-1)+\log m+1\le1+2/m sup a − a ˉ 0 ≤ − log ( m − 1 ) + log m + 1 ≤ 1 + 2/ m , and the last bin is symmetric. Summing, E ∣ a ( U 1 ) − a ˉ Y 1 ∣ ≤ ( 2 log ( m − 1 ) + 4 + 8 / m ) / m ≤ ( 2 log m + 6 ) / m \mathbb{E}|a(U_1)-\bar a_{Y_1}|\le(2\log(m-1)+4+8/m)/m\le(2\log m+6)/m E ∣ a ( U 1 ) − a ˉ Y 1 ∣ ≤ ( 2 log ( m − 1 ) + 4 + 8/ m ) / m ≤ ( 2 log m + 6 ) / m .
Substituting the clipped candidate into P \mathcal{P} P gives a lower bound, but need not preserve concavity. We therefore extend the bin scores concavely and subtract a penalty that controls the change in the potential under clipping. For t ∈ R t\in\mathbb{R} t ∈ R let ψ t ( y ) = t min { y , 1 } \psi_t(y)=t\min\{y,1\} ψ t ( y ) = t min { y , 1 } if t ≥ 0 t\ge0 t ≥ 0 and ψ t ( y ) = t max { y , 0 } \psi_t(y)=t\max\{y,0\} ψ t ( y ) = t max { y , 0 } if t < 0 t<0 t < 0 . This function is concave and ∣ t ∣ |t| ∣ t ∣ -Lipschitz, equals t y ty t y on [ 0 , 1 ] [0,1] [ 0 , 1 ] , and satisfies ψ t ( y ) ≤ t clip ( y ) \psi_t(y)\le t\operatorname{clip}(y) ψ t ( y ) ≤ t clip ( y ) , where clip ( y ) = min { 1 , max { 0 , y } } \operatorname{clip}(y)=\min\{1,\max\{0,y\}\} clip ( y ) = min { 1 , max { 0 , y }} ; we write dist ( y , [ 0 , 1 ] ) = ∣ y − clip ( y ) ∣ \operatorname{dist}(y,[0,1])=|y-\operatorname{clip}(y)| dist ( y , [ 0 , 1 ]) = ∣ y − clip ( y ) ∣ for the distance to the interval. For a candidate u u u define the penalized objective
J v ( u ) = ∑ i = 1 k E a ˉ Y i ( u i ( Y ) ) + E Φ L ( u ( Y ) ) − Λ ∑ i = 1 k E dist ( u i ( Y ) , [ 0 , 1 ] ) . (27) J_v(u)=\sum_{i=1}^{k}\mathbb{E}\bar a_{Y_i}\bigl(u_i(Y)\bigr)+\mathbb{E}\Phi^{L}\bigl(u(Y)\bigr)-\Lambda\sum_{i=1}^{k}\mathbb{E}\operatorname{dist}\bigl(u_i(Y),[0,1]\bigr). \tag*{(27)} J v ( u ) = i = 1 ∑ k E a ˉ Y i ( u i ( Y ) ) + E Φ L ( u ( Y ) ) − Λ i = 1 ∑ k E dist ( u i ( Y ) , [ 0 , 1 ] ) . (27)
The objective is an expectation under the fixed product law of the bins; its integrand uses only candidate values and evaluations of W W W .
Lemma 4.3 (Soundness for every candidate). The objective J v J_v J v is concave. Every candidate u u u satisfies J v ( u ) ≤ log Z Φ J_v(u)\le\log Z_{\Phi} J v ( u ) ≤ log Z Φ , and any two candidates satisfy ∣ J v ( u ) − J v ( u ′ ) ∣ ≤ G 0 ∑ i E ∣ u i − u i ′ ∣ |J_v(u)-J_v(u')|\le G_0\sum_i\mathbb{E}|u_i-u'_i| ∣ J v ( u ) − J v ( u ′ ) ∣ ≤ G 0 ∑ i E ∣ u i − u i ′ ∣ .
Proof. Concavity holds termwise: ψ t \psi_t ψ t , Φ L \Phi^L Φ L and minus the distance to an interval are concave, and u ↦ u i ( Y ) u \mapsto u_i(Y) u ↦ u i ( Y ) is linear. Let F = clip ( u ) F=\operatorname{clip}(u) F = clip ( u ) , coordinatewise; it is a guide. Then ψ t ( u i ) ≤ t F i \psi_t(u_i) \le tF_i ψ t ( u i ) ≤ t F i for every t t t , and (L4) gives Φ L ( u ) ≤ Φ L ( F ) + Λ ∑ i dist ( u i , [ 0 , 1 ] ) \Phi^L(u) \le\Phi^L(F) + \Lambda\sum_i \operatorname{dist}(u_i,[0,1]) Φ L ( u ) ≤ Φ L ( F ) + Λ ∑ i dist ( u i , [ 0 , 1 ]) : the penalty pays for the change of the potential term under clipping. Hence
J v ( u ) ≤ ∑ i E [ a ˉ Y i F i ] + E Φ L ( F ) = P ( F ) ≤ log Z Φ . J_v(u) \le\sum_i \mathbb{E}[\bar a_{Y_i}F_i] + \mathbb{E}\Phi^L(F) = \mathcal{P}(F) \le\log Z_\Phi. J v ( u ) ≤ i ∑ E [ a ˉ Y i F i ] + E Φ L ( F ) = P ( F ) ≤ log Z Φ .
The equality holds because F i F_i F i is a function of the bins and a ˉ Y i = E [ a ( U i ) ∣ Y ] \bar a_{Y_i} = \mathbb{E}[a(U_i)\mid Y] a ˉ Y i = E [ a ( U i ) ∣ Y ] ; the last inequality is Proposition 3.8.
For the Lipschitz bound, the term ψ a ˉ Y i ( u i ) \psi_{\bar a_{Y_i}}(u_i) ψ a ˉ Y i ( u i ) of row i i i is A 0 A_0 A 0 -Lipschitz by Lemma 4.2, and the potential term and the penalty are Λ \Lambda Λ -Lipschitz in each row.
A good low-degree candidate exists. We now represent low-degree candidates by finitely many bounded coefficients and show that one preserves nearly the witness’s objective value. We use Walsh characters because their orthogonality controls truncation error, while their values in { − 1 , 1 } \{-1,1\} { − 1 , 1 } ensure that [ 0 , 1 ] [0,1] [ 0 , 1 ] -valued functions of the bins have coefficients in [ − 1 , 1 ] [-1,1] [ − 1 , 1 ] . Since m = 2 2 s m=2^{2s} m = 2 2 s , identify each bin index y ∈ { 0 , … , m − 1 } y\in\{0,\ldots,m-1\} y ∈ { 0 , … , m − 1 } with its vector of 2 s 2s 2 s binary digits. For β ∈ { 0 , 1 } 2 s \beta\in\{0,1\}^{2s} β ∈ { 0 , 1 } 2 s put χ β ( y ) = ( − 1 ) β ⋅ y \chi_\beta(y)=(-1)^{\beta\cdot y} χ β ( y ) = ( − 1 ) β ⋅ y , where β ⋅ y \beta\cdot y β ⋅ y is the inner product of the digit vectors, and for β = ( β 1 , … , β k ) \beta=(\beta_1,\ldots,\beta_k) β = ( β 1 , … , β k ) put χ β ( Y ) = ∏ j χ β j ( Y j ) \chi_\beta(Y)=\prod_j\chi_{\beta_j}(Y_j) χ β ( Y ) = ∏ j χ β j ( Y j ) . These m k m^k m k Walsh characters [71 ] are an orthonormal basis for the functions of Y Y Y . The support of β \beta β is { j : β j ≠ 0 } \{j:\beta_j\ne0\} { j : β j = 0 } . For a function ϕ \phi ϕ of the bins write ϕ ^ ( β ) = E [ ϕ χ β ] \widehat{\phi}(\beta)=\mathbb{E}[\phi\chi_\beta] ϕ ( β ) = E [ ϕ χ β ] . Viewed as a function of U U U , the Hoeffding component of ϕ \phi ϕ on S S S is ∑ ϕ ^ ( β ) χ β \sum\widehat{\phi}(\beta)\chi_\beta ∑ ϕ ( β ) χ β over the β \beta β with support S S S [71 Proposition 8.36] .
Lemma 4.4 (Low-degree candidate). There is a candidate u ∗ u^* u ∗ such that each row u i ∗ u_i^* u i ∗ is a linear combination, with coefficients in [ − 1 , 1 ] [-1,1] [ − 1 , 1 ] , of the Walsh characters whose supports lie in { 1 , … , i } \{1,\ldots,i\} { 1 , … , i } and have at most D D D elements, and
J v ( u ∗ ) ≥ log Z Φ − b ∗ − 1 32 . J_v(u^*) \ge\log Z_\Phi-b_*-\frac{1}{32}. J v ( u ∗ ) ≥ log Z Φ − b ∗ − 32 1 .
Proof. Let g g g be the guide assumed in (4.2), and put g ˉ i = E [ g i ∣ Y ] \bar g_i=\mathbb{E}[g_i\mid Y] g ˉ i = E [ g i ∣ Y ] . Conditioning on Y Y Y averages the guide over each product of input bins. Thus g ˉ \bar g g ˉ takes values in [ 0 , 1 ] k [0,1]^k [ 0 , 1 ] k , and g ˉ i \bar g_i g ˉ i depends only on Y 1 , … , Y i Y_1,\ldots,Y_i Y 1 , … , Y i . Its penalty vanishes, and since Φ L \Phi^L Φ L is concave, Φ L ( g ˉ ( Y ) ) ≥ E [ Φ L ( g ( U ) ) ∣ Y ] \Phi^L(\bar g(Y))\ge\mathbb{E}[\Phi^L(g(U))\mid Y] Φ L ( g ˉ ( Y )) ≥ E [ Φ L ( g ( U )) ∣ Y ] . Since g i ∈ [ 0 , 1 ] g_i\in[0,1] g i ∈ [ 0 , 1 ] , Lemma 4.2 and the choice of m m m give
J v ( g ˉ ) ≥ ∑ i E [ a ˉ Y i g i ] + E Φ L ( g ) ≥ P ( g ) − k ( 2 log m + 6 ) m ≥ log Z Φ − b ∗ − 1 64 . J_v(\bar g)\ge\sum_i\mathbb{E}[\bar a_{Y_i}g_i]+\mathbb{E}\Phi^L(g)\ge\mathcal{P}(g)-\frac{k(2\log m+6)}{m}\ge\log Z_\Phi-b_*-\frac{1}{64}. J v ( g ˉ ) ≥ i ∑ E [ a ˉ Y i g i ] + E Φ L ( g ) ≥ P ( g ) − m k ( 2 log m + 6 ) ≥ log Z Φ − b ∗ − 64 1 .
For the last step use (4.2) and d ( 2 log m + 6 ) / m < 1 / 64 d(2\log m+6)/m<1/64 d ( 2 log m + 6 ) / m < 1/64 : with d ≤ 2 s / 64 d\le2^s/64 d ≤ 2 s /64 and s ≥ 6 s\ge6 s ≥ 6 the left-hand side is at most ( 4 s log 2 + 6 ) / ( 64 ⋅ 2 s ) < 1 / 64 (4s\log2+6)/(64\cdot2^s)<1/64 ( 4 s log 2 + 6 ) / ( 64 ⋅ 2 s ) < 1/64 .
Now truncate to interaction degree D D D , setting u i ∗ = Π ≤ D g ˉ i u_i^*=\Pi_{\le D}\bar g_i u i ∗ = Π ≤ D g ˉ i . Conditioning on the bins acts on each coordinate separately, commutes with every E j E_j E j and does not increase norms, so by Section 4.1 Π ≤ D g ˉ i = E [ Π ≤ D g i ∣ Y ] \Pi_{\le D}\bar g_i=\mathbb{E}[\Pi_{\le D}g_i\mid Y] Π ≤ D g ˉ i = E [ Π ≤ D g i ∣ Y ] , and (4.2) gives ∥ Π ≤ D g ˉ i ∥ 2 ≤ 1 / ( 128 d G 0 ) \|\Pi_{\le D}\bar g_i\|_2\le1/(128dG_0) ∥ Π ≤ D g ˉ i ∥ 2 ≤ 1/ ( 128 d G 0 ) . By Cauchy–Schwarz, E ∣ g ˉ i − u i ∗ ∣ ≤ 1 / ( 128 d G 0 ) \mathbb{E}|\bar g_i-u_i^*|\le1/(128dG_0) E ∣ g ˉ i − u i ∗ ∣ ≤ 1/ ( 128 d G 0 ) . Summing over the k ≤ d k\le d k ≤ d rows, Lemma 4.3 turns this into objective loss of at most 1 / 128 1/128 1/128 . Together with the preceding bound, this gives the claimed objective value. In the Walsh basis u i ∗ u_i^* u i ∗ keeps exactly the characters of g ˉ i \bar g_i g ˉ i whose supports have at most D D D elements. Their coefficients E [ g ˉ i χ β ] \mathbb{E}[\bar g_i\chi_\beta] E [ g ˉ i χ β ] lie in [ − 1 , 1 ] [-1,1] [ − 1 , 1 ] because 0 ≤ g ˉ i ≤ 1 0\le\bar g_i\le1 0 ≤ g ˉ i ≤ 1 , and they vanish unless the support lies in { 1 , … , i } \{1,\ldots,i\} { 1 , … , i } , since g ˉ i \bar g_i g ˉ i does not depend on later bins.
Stochastic optimization. For row i i i let F i \mathcal{F}_i F i be the set of β \beta β whose support lies in { 1 , … , i } \{1,\ldots,i\} { 1 , … , i } and has at most D D D elements. Put
M i = ∣ F i ∣ = ∑ j = 0 min ( D , i ) ( i j ) ( m − 1 ) j , M = max i M i , P = ∑ i = 1 k M i ≤ k M . (28) M_i = |\mathcal{F}_i| = \sum_{j=0}^{\min(D,i)} \binom{i}{j}(m-1)^j,\qquad M = \max_i M_i,\qquad P = \sum_{i=1}^{k} M_i \le kM. \tag*{(28)} M i = ∣ F i ∣ = j = 0 ∑ m i n ( D , i ) ( j i ) ( m − 1 ) j , M = i max M i , P = i = 1 ∑ k M i ≤ k M . (28)
A coefficient vector θ ∈ C = [ − 1 , 1 ] P \theta\in\mathcal{C} = [-1,1]^P θ ∈ C = [ − 1 , 1 ] P (unrelated to the branching rules of § 6.1 ) defines the candidate u i θ = ∑ β ∈ F i θ i , β χ β u_i^\theta= \sum_{\beta\in\mathcal{F}_i}\theta_{i,\beta}\chi_\beta u i θ = ∑ β ∈ F i θ i , β χ β , and we write J ( θ ) = J v ( u θ ) J(\theta)=J_v(u^\theta) J ( θ ) = J v ( u θ ) . By Lemma 4.4, some θ ∘ ∈ C \theta^\circ\in\mathcal{C} θ ∘ ∈ C has J ( θ ∘ ) ≥ log Z Φ − b ∗ − 1 / 32 J(\theta^\circ)\ge\log Z_\Phi-b_* - 1/32 J ( θ ∘ ) ≥ log Z Φ − b ∗ − 1/32 . Since M ≤ ( 1 + d m ) D M\le(1+dm)^D M ≤ ( 1 + d m ) D and m = poly ( d ) m=\operatorname{poly}(d) m = poly ( d ) ,
log P ≤ log d + D log ( 1 + d m ) = O ( ( D + 1 ) log d ) . (29) \log P \le\log d + D\log(1+dm)=O((D+1)\log d). \tag*{(29)} log P ≤ log d + D log ( 1 + d m ) = O (( D + 1 ) log d ) . (29)
A fresh sample of the bins allows us to evaluate a sample objective and a stochastic supergradient. Generating the sample uses k k k uniform draws and O ( k log m ) O(k\log m) O ( k log m ) comparisons. At a sample every character is a sign, so ∣ u i θ ( Y ) ∣ ≤ M |u_i^\theta(Y)|\le M ∣ u i θ ( Y ) ∣ ≤ M . Dropping the expectations in (27) gives the sample objective J ^ Y ( θ ) \widehat{J}_Y(\theta) J Y ( θ ) , which is concave and piecewise linear in θ \theta θ . For every fixed θ \theta θ , E J ^ Y ( θ ) = J ( θ ) \mathbb{E}\widehat{J}_Y(\theta)=J(\theta) E J Y ( θ ) = J ( θ ) . The potential term of J ^ Y ( θ ) \widehat{J}_Y(\theta) J Y ( θ ) is evaluated by sorting the k k k values u i θ ( Y ) u_i^\theta(Y) u i θ ( Y ) and applying (19) to k + 1 k+1 k + 1 values of W W W . Choose a supergradient ζ Y ( θ ) \zeta_Y(\theta) ζ Y ( θ ) from the chain increments of that sorting (L3), with slope zero at every kink of ψ t \psi_t ψ t and of the penalty. The slope of each row then has magnitude at most G 0 G_0 G 0 . The ( i , β ) (i,\beta) ( i , β ) coordinate of ζ Y ( θ ) \zeta_Y(\theta) ζ Y ( θ ) is the chosen row-i i i slope multiplied by χ β ( Y ) \chi_\beta(Y) χ β ( Y ) . Put G 1 = k G 0 G_1=kG_0 G 1 = k G 0 . Since Φ L ( 0 ) = 0 \Phi^L(0)=0 Φ L ( 0 ) = 0 , the sample objective satisfies ∣ J ^ Y ( θ ) ∣ ≤ G 0 ∑ i ∣ u i θ ( Y ) ∣ ≤ M G 1 |\widehat{J}_Y(\theta)|\le G_0\sum_i|u_i^\theta(Y)|\le MG_1 ∣ J Y ( θ ) ∣ ≤ G 0 ∑ i ∣ u i θ ( Y ) ∣ ≤ M G 1 , and
∥ ζ Y ( θ ) ∥ 2 2 ≤ ∑ i M i G 0 2 ≤ M G 1 2 . (30) \|\zeta_Y(\theta)\|_2^2\le\sum_i M_iG_0^2\le MG_1^2. \tag*{(30)} ∥ ζ Y ( θ ) ∥ 2 2 ≤ i ∑ M i G 0 2 ≤ M G 1 2 . (30)
Averaging the supergradient inequality gives a supergradient E ζ Y ( θ ) \mathbb{E}\zeta_Y(\theta) E ζ Y ( θ ) of J J J at fixed θ \theta θ . We use projected stochastic supergradient ascent [69 §2.2] with target expected optimization gap γ = 1 / 64 \gamma=1/64 γ = 1/64 . Set α = γ / ( M G 1 2 ) \alpha=\gamma/(MG_1^2) α = γ / ( M G 1 2 ) and n i t = ⌈ P M G 1 2 / γ 2 ⌉ n_{\mathrm{it}}=\lceil PMG_1^2/\gamma^2\rceil n it = ⌈ P M G 1 2 / γ 2 ⌉ . Initialize θ 1 = 0 \theta_1=0 θ 1 = 0 and iterate
θ j + 1 = Π C ( θ j + α ζ Y ( j ) ( θ j ) ) , j = 1 , … , n i t , (31) \theta_{j+1}=\Pi_{\mathcal{C}}\bigl(\theta_j+\alpha\zeta_{Y^{(j)}}(\theta_j)\bigr),\qquad j=1,\ldots,n_{\mathrm{it}}, \tag*{(31)} θ j + 1 = Π C ( θ j + α ζ Y ( j ) ( θ j ) ) , j = 1 , … , n it , (31)
with a fresh sample Y ( j ) Y^{(j)} Y ( j ) each time; the projection Π C \Pi_{\mathcal{C}} Π C clips each coordinate to [ − 1 , 1 ] [-1,1] [ − 1 , 1 ] . Return
θ ˉ = n i t − 1 ∑ j = 1 n i t θ j . \bar{\theta}=n_{\mathrm{it}}^{-1}\sum_{j=1}^{n_{\mathrm{it}}}\theta_j. θ ˉ = n it − 1 j = 1 ∑ n it θ j .
If θ ∗ \theta^* θ ∗ maximizes J J J on C \mathcal{C} C , then projection does not increase the distance to θ ∗ \theta^* θ ∗ , and the conditional supergradient inequality gives
E ∥ θ j + 1 − θ ∗ ∥ 2 2 ≤ E ∥ θ j − θ ∗ ∥ 2 2 − 2 α E [ J ( θ ∗ ) − J ( θ j ) ] + α 2 M G 1 2 . \mathbb{E}\|\theta_{j+1}-\theta^*\|_2^2\le\mathbb{E}\|\theta_j-\theta^*\|_2^2-2\alpha\,\mathbb{E}[J(\theta^*)-J(\theta_j)]+\alpha^2MG_1^2. E ∥ θ j + 1 − θ ∗ ∥ 2 2 ≤ E ∥ θ j − θ ∗ ∥ 2 2 − 2 α E [ J ( θ ∗ ) − J ( θ j )] + α 2 M G 1 2 .
Summing over j j j , using ∥ θ 1 − θ ∗ ∥ 2 2 ≤ P \|\theta_1-\theta^*\|_2^2\le P ∥ θ 1 − θ ∗ ∥ 2 2 ≤ P and concavity of J J J at θ ˉ \bar{\theta} θ ˉ ,
E [ J ( θ ∗ ) − J ( θ ˉ ) ] ≤ P 2 α n i t + α M G 1 2 2 ≤ γ . (32) \mathbb{E}[J(\theta^*)-J(\bar{\theta})]\le\frac{P}{2\alpha n_{\mathrm{it}}}+\frac{\alpha MG_1^2}{2}\le\gamma. \tag*{(32)} E [ J ( θ ∗ ) − J ( θ ˉ )] ≤ 2 α n it P + 2 α M G 1 2 ≤ γ . (32)
By Markov’s inequality, J ( θ ˉ ) ≥ J ( θ ∗ ) − 4 γ J(\bar{\theta})\ge J(\theta^*)-4\gamma J ( θ ˉ ) ≥ J ( θ ∗ ) − 4 γ with probability at least 3 / 4 3/4 3/4 . The finite-precision implementation and its rounding analysis are given in Appendix § 12 .§ 6 .
Validation. For a requested failure probability 0 < δ ≤ 1 / 2 0 < \delta\le1/2 0 < δ ≤ 1/2 , run the ascent independently n a t t = ⌈ log 2 ( 4 / δ ) ⌉ n_{\mathrm{att}} = \lceil\log_2(4/\delta) \rceil n att = ⌈ log 2 ( 4/ δ )⌉ times to amplify the probability of finding a good candidate. We estimate each returned candidate’s objective value using fresh samples, since the candidate depends on the samples used during ascent. Subtracting the validation error margin then gives a lower estimate of log Z Φ \log Z_{\Phi} log Z Φ whenever validation is accurate. For each candidate, average J ^ Y \widehat{J}_Y J Y over
n v a l = ⌈ 2 M 2 G 1 2 γ − 2 log ( 8 n a t t / δ ) ⌉ (33) n_{\mathrm{val}} = \left\lceil2M^2G_1^2\gamma^{-2}\log(8n_{\mathrm{att}}/\delta)\right\rceil \tag*{(33)} n val = ⌈ 2 M 2 G 1 2 γ − 2 log ( 8 n att / δ ) ⌉ (33)
fresh samples. Conditional on the candidate, Hoeffding’s inequality [46 ] shows that this average differs from its objective value by more than γ \gamma γ with probability at most δ / ( 4 n a t t ) \delta/(4n_{\mathrm{att}}) δ / ( 4 n att ) .
Proof of Theorem 4.1. At a leaf return 0 0 0 . Otherwise compute the parameters (4.1) by comparisons, and the m m m bin scores from the m + 1 m+1 m + 1 values H ( j / m ) H(j/m) H ( j / m ) . Run n a t t n_{\mathrm{att}} n att ascent and validation attempts as above, writing θ ˉ ( ρ ) \bar{\theta}^{(\rho)} θ ˉ ( ρ ) and J ^ ( ρ ) \widehat{J}^{(\rho)} J ( ρ ) for the averaged iterate and validation average in attempt ρ \rho ρ . Return
A v = min { k ( 1 + Λ ) , max { 0 , max ρ ( J ^ ( ρ ) − γ ) } } . A_v = \min\left\{k(1+\Lambda),\max\left\{0,\max_{\rho}\left(\widehat{J}^{(\rho)}-\gamma\right)\right\}\right\}. A v = min { k ( 1 + Λ ) , max { 0 , ρ max ( J ( ρ ) − γ ) } } .
By a union bound, with probability at least 1 − δ / 4 1-\delta/4 1 − δ /4 every validation is accurate within γ \gamma γ , and with probability at least 1 − 4 − n a t t ≥ 1 − δ / 4 1-4^{-n_{\mathrm{att}}}\ge1-\delta/4 1 − 4 − n att ≥ 1 − δ /4 some attempt has J ( θ ˉ ( ρ ) ) ≥ J ( θ ∗ ) − 4 γ J(\bar{\theta}^{(\rho)})\ge J(\theta^*)-4\gamma J ( θ ˉ ( ρ ) ) ≥ J ( θ ∗ ) − 4 γ . On both events every J ^ ( ρ ) − γ \widehat{J}^{(\rho)}-\gamma J ( ρ ) − γ is at most J ( θ ˉ ( ρ ) ) ≤ log Z Φ J(\bar{\theta}^{(\rho)})\le\log Z_{\Phi} J ( θ ˉ ( ρ ) ) ≤ log Z Φ by Lemma 4.3, and the best one is at least
J ( θ ∗ ) − 6 γ ≥ J ( θ ∘ ) − 6 γ ≥ log Z Φ − b ∗ − 1 32 − 6 64 = log Z Φ − b ∗ − 1 8 . J(\theta^*)-6\gamma\ge J(\theta^\circ)-6\gamma\ge\log Z_{\Phi}-b_*-\frac{1}{32}-\frac{6}{64}=\log Z_{\Phi}-b_*-\frac{1}{8}. J ( θ ∗ ) − 6 γ ≥ J ( θ ∘ ) − 6 γ ≥ log Z Φ − b ∗ − 32 1 − 64 6 = log Z Φ − b ∗ − 8 1 .
The clamps keep A v A_v A v in [ 0 , k ( 1 + Λ ) ] ⊆ [ 0 , d ( 1 + 2 B ) ] [0,k(1+\Lambda)]\subseteq[0,d(1+2B)] [ 0 , k ( 1 + Λ )] ⊆ [ 0 , d ( 1 + 2 B )] , since k ≤ d k\le d k ≤ d . They are harmless because 0 ≤ log Z Φ ≤ k ( log 2 + Λ ) < k ( 1 + Λ ) 0\le\log Z_{\Phi}\le k(\log2+\Lambda)<k(1+\Lambda) 0 ≤ log Z Φ ≤ k ( log 2 + Λ ) < k ( 1 + Λ ) : the configuration 0 0 0 contributes e Φ ( 0 ) = 1 e^{\Phi(0)}=1 e Φ ( 0 ) = 1 , and Φ ( x ) ≤ k Λ \Phi(x)\le k\Lambda Φ ( x ) ≤ k Λ by telescoping from 0 0 0 .
For the cost, the characters χ β \chi_\beta χ β with β ∈ F i \beta\in F_i β ∈ F i are listed by choosing a support of at most D D D positions and nonzero digit patterns on it, and a character is evaluated in O ( 1 + D s ) O(1+Ds) O ( 1 + D s ) operations. One ascent step or one validation sample costs poly ( d ) P \operatorname{poly}(d)P poly ( d ) P operations and k + 1 k+1 k + 1 evaluations of W W W . There are n a t t n i t n_{\mathrm{att}}n_{\mathrm{it}} n att n it steps and n a t t n v a l n_{\mathrm{att}}n_{\mathrm{val}} n att n val validation samples, all fixed in advance, and G 1 = poly ( d , B ) G_1=\operatorname{poly}(d,B) G 1 = poly ( d , B ) . By (4.6) and M M M , P ≤ exp ( O ( ( D + 1 ) log d ) ) P\le\exp(O((D+1)\log d)) P ≤ exp ( O (( D + 1 ) log d )) , the total is (4.3) on every execution. □ \square □
Low-degree approximation and threshold smoothing
We construct nearly optimal guides with small high-degree tails, providing the witnesses required by the estimator of Theorem 4.1. These guides are obtained by averaging random perturbations of the exact guide and serve only to certify that the search space contains a good candidate. We first analyze ordinary resampling, which gives the square-root baseline (Section 5.1). We then introduce threshold smoothing, which improves the objective-loss bound from linear to quadratic in the perturbation parameter while preserving comparable high-degree decay (Section 5.2). This improved tradeoff completes the proof of Theorem 2.2 and yields the cube-root running-time exponent.
Throughout this section, Φ \Phi Φ is a supermodular potential on { 0 , 1 } d \{0,1\}^d { 0 , 1 } d , normalized by Φ ( 0 ) = 0 \Phi(0)=0 Φ ( 0 ) = 0 , and μ = e Φ / Z Φ \mu=e^\Phi/Z_\Phi μ = e Φ / Z Φ . We use the exact guide f f f of (3.7), the variational objective P \mathcal{P} P , and the Hoeffding decomposition of Section 4.1. The constructions work in any fixed coordinate order and apply, in particular, to every pinned residual from Section 2.
Ordinary resampling and the square-root baseline
The simplest way to shrink the high-degree components of the exact guide (14) is to resample its inputs: for 0 < τ ≤ 1 / 2 0<\tau\le1/2 0 < τ ≤ 1/2 , let g = T τ f g=T_\tau f g = T τ f , where T τ = ∏ j = 1 d ( ( 1 − τ ) I + τ E j ) T_\tau=\prod_{j=1}^{d}((1-\tau)I+\tau E_j) T τ = ∏ j = 1 d (( 1 − τ ) I + τ E j ) is the noise operator. O’Donnell [71 Definitions 8.26–8.27, Proposition 8.28 and §8.3] treats it on finite product spaces, with the correlation 1 − τ 1-\tau 1 − τ as its parameter.
Lemma 5.1 (Ordinary resampling). For every 0 < τ ≤ 1 / 2 0<\tau\le1/2 0 < τ ≤ 1/2 , g = T τ f g=T_\tau f g = T τ f is a guide, and
0 ≤ log Z Φ − P ( g ) ≤ τ H ( μ ) ≤ d τ log 2 , ∥ Π > D g i ∥ 2 ≤ 1 2 ( 1 − τ ) D + 1 0\le\log Z_\Phi-\mathcal{P}(g)\le\tau H(\mu)\le d\tau\log2,\qquad\|\Pi_{>D}g_i\|_2\le\frac{1}{2}(1-\tau)^{D+1} 0 ≤ log Z Φ − P ( g ) ≤ τ H ( μ ) ≤ d τ log 2 , ∥ Π > D g i ∥ 2 ≤ 2 1 ( 1 − τ ) D + 1 for every row i i i and integer $D\ge 0.
Proof. The operator is positive, fixes constants, and preserves the uniform product measure. Because f i f_i f i depends only on the first i i i inputs, so does g i g_i g i . Sample a noisy copy V V V of U U U by independently keeping each coordinate with probability 1 − τ 1-\tau 1 − τ and otherwise drawing a fresh uniform value. Then g ( U ) = E [ f ( V ) ∣ U ] g(U)=\mathbb{E}[f(V)\mid U] g ( U ) = E [ f ( V ) ∣ U ] , while V V V is uniform. As in (22) , (L5) applied given U U U gives E Φ L ( g ) ≥ E Φ ( f ( V ) ) = E μ Φ \mathbb{E}\Phi^{L}(g)\ge\mathbb{E}\Phi(f(V))=\mathbb{E}_{\mu}\Phi E Φ L ( g ) ≥ E Φ ( f ( V )) = E μ Φ . Consider the linear score of row i i i . If U i U_i U i is resampled, the row contributes zero, since E a ( U i ) = 0 \mathbb{E}a(U_i)=0 E a ( U i ) = 0 . If U i U_i U i is kept, the noisy prefix V < i V_{<i} V < i has the uniform product law and is independent of U i U_i U i ; hence
E [ a ( U i ) g i ( U ) ] = ( 1 − τ ) E [ a ( U i ) f i ( U ) ] . \mathbb{E}[a(U_i)g_i(U)]=(1-\tau)\mathbb{E}[a(U_i)f_i(U)]. E [ a ( U i ) g i ( U )] = ( 1 − τ ) E [ a ( U i ) f i ( U )] .
By Lemma 3.3, the sum of the latter expectations is H ( μ ) H(\mu) H ( μ ) . This proves the objective-gap bound using Proposition 3.8. Finally T τ T_\tau T τ multiplies the Hoeffding component on S S S by ( 1 − τ ) ∣ S ∣ (1-\tau)^{|S|} ( 1 − τ ) ∣ S ∣ . Orthogonality and Var ( f i ) ≤ 1 / 4 \operatorname{Var}(f_i)\le1/4 Var ( f i ) ≤ 1/4 give ∥ Π > D g i ∥ 2 2 ≤ 1 4 ( 1 − τ ) 2 ( D + 1 ) \|\Pi_{>D}g_i\|_2^2\le\frac{1}{4}(1-\tau)^{2(D+1)} ∥ Π > D g i ∥ 2 2 ≤ 4 1 ( 1 − τ ) 2 ( D + 1 ) . □ \square □
Corollary 5.2 (Square-root baseline). Ordinary resampling and the estimator of Theorem 4.1 give the counting and sampling guarantees of Theorem 1.2 within the bound
exp ( O ( min { d , d log d log ( d + B ) } ) ) \exp\left(O\left(\min\left\{d,\sqrt{d\log d\log(d+B)}\right\}\right)\right) exp ( O ( min { d , d log d log ( d + B ) } ) ) times the same polynomial factors. For bipartite independent sets this gives exp ( O ( n log n ) ) \exp(O(\sqrt{n}\log n)) exp ( O ( n log n )) times the polynomial factors in Theorem 1.1.
Proof. For 0 < τ ≤ 1 / 2 0<\tau\le1/2 0 < τ ≤ 1/2 , take D = min { d , ⌈ κ / τ ⌉ } D=\min\{d,\lceil\kappa/\tau\rceil\} D = min { d , ⌈ κ / τ ⌉} , with the parameters of (4.1). Apply Lemma 5.1 to any residual with k ≤ d k\le d k ≤ d free coordinates. Its objective gap is at most d τ log 2 d\tau\log2 d τ log 2 . If D < d D<d D < d , the degree-D D D tail of each row has norm at most 1 2 ( 1 − τ ) D + 1 ≤ 1 2 e − κ ≤ 1 / ( 128 d G 0 ) \frac{1}{2}(1-\tau)^{D+1}\le\frac{1}{2}e^{-\kappa}\le1/(128dG_0) 2 1 ( 1 − τ ) D + 1 ≤ 2 1 e − κ ≤ 1/ ( 128 d G 0 ) ; if D = d D=d D = d the tail vanishes. Thus Theorem 4.1 supplies, at every node, a one-sided estimate with additive error bound b = d τ log 2 + 1 / 8 b=d\tau\log2+1/8 b = d τ log 2 + 1/8 and cost
exp ( O ( τ − 1 log d log ( d + B ) ) ) poly ( d , B , T W , log ( 1 / δ ) ) . \exp(O(\tau^{-1}\log d\log(d+B)))\operatorname{poly}(d,B,T_W,\log(1/\delta)). exp ( O ( τ − 1 log d log ( d + B ))) poly ( d , B , T W , log ( 1/ δ )) .
The conversion of Proposition 2.1 therefore has exponential cost exp ( O ( d τ + ℓ d ℓ B / τ ) ) \exp(O(d\tau+\ell_d\ell_B/\tau)) exp ( O ( d τ + ℓ d ℓ B / τ )) , with ℓ d \ell_d ℓ d and ℓ B \ell_B ℓ B as in the proof of Theorem 1.2.
If ℓ d ℓ B < d / 4 \ell_d\ell_B<d/4 ℓ d ℓ B < d /4 , choose the largest τ = 2 − j \tau=2^{-j} τ = 2 − j with integer j ≥ 1 j\ge1 j ≥ 1 for which d τ 2 ≤ ℓ d ℓ B d\tau^2\le\ell_d\ell_B d τ 2 ≤ ℓ d ℓ B . Then both d τ d\tau d τ and ℓ d ℓ B / τ \ell_d\ell_B/\tau ℓ d ℓ B / τ are O ( d ℓ d ℓ B ) O(\sqrt{d\ell_d\ell_B}) O ( d ℓ d ℓ B ) . If ℓ d ℓ B ≥ d / 4 \ell_d\ell_B\ge d/4 ℓ d ℓ B ≥ d /4 , exact enumeration instead costs 2 d poly ( d , T W ) 2^d\operatorname{poly}(d,T_W) 2 d poly ( d , T W ) , and d = O ( d ℓ d ℓ B ) d=O(\sqrt{d\ell_d\ell_B}) d = O ( d ℓ d ℓ B ) . Taking the cheaper of the resulting algorithm and enumeration gives the stated minimum. Finally, ℓ d ℓ B = O ( log d log ( d + B ) ) \ell_d\ell_B=O(\log d\log(d+B)) ℓ d ℓ B = O ( log d log ( d + B )) ; for # B I S \#\mathrm{BIS} # BIS use d ≤ n d\le n d ≤ n , B ≤ n + 1 B\le n+1 B ≤ n + 1 , and n ≥ 2 n\ge2 n ≥ 2 . □ \square □
Threshold smoothing and the two guarantees
Resampling loses linearly in τ \tau τ , because a resampled input contributes nothing to the linear score. Threshold smoothing keeps every input and shifts its threshold instead, which loses only quadratically while reducing the variance of the averaged indicator at each threshold by a fraction linear in w w w .
Theorem 5.3 (Near-optimal guides with small high-degree tails). Let Φ \Phi Φ be a normalized supermodular potential on d d d coordinates. For every 0 < w ≤ 1 / 2 0<w\le1/2 0 < w ≤ 1/2 there is a guide g g g such that
(i) Near-optimal objective value: 0 ≤ log Z Φ − P ( g ) ≤ d w 2 / 4 0\le\log Z_{\Phi}-\mathcal{P}(g)\le dw^{2}/4 0 ≤ log Z Φ − P ( g ) ≤ d w 2 /4 , and
(ii) Low-degree approximation: ∥ Π > D g i ∥ 2 ≤ 1 2 ( 1 − w / 2 ) ( D + 1 ) / 2 \|\Pi_{>D}g_i\|_2\le\frac{1}{2}(1-w/2)^{(D+1)/2} ∥ Π > D g i ∥ 2 ≤ 2 1 ( 1 − w /2 ) ( D + 1 ) /2 for every row i i i and every integer D ≥ 0 D\ge0 D ≥ 0 .
We construct g g g , in any coordinate order, by smoothing the thresholds of the exact guide. Item (i) controls the additive error in the estimate of log Z Φ \log Z_{\Phi} log Z Φ ; item (ii) controls the degree needed for an accurate truncation of g g g , and hence the size of the search space.
The construction. Fix a smoothing parameter 0 < w ≤ 1 / 2 0<w\le1/2 0 < w ≤ 1/2 .
Definition 5.4 (Ordered threshold tree). A function T : ( 0 , 1 ) d → R \mathcal{T}:(0,1)^d\to\mathbb{R} T : ( 0 , 1 ) d → R is an ordered threshold tree if it can be computed as follows. For j = 1 , … , d j=1,\ldots,d j = 1 , … , d in turn, compare u j u_j u j with a threshold c j ∈ [ 0 , 1 ] c_j\in[0,1] c j ∈ [ 0 , 1 ] that depends only on the outcomes x 1 , … , x j − 1 x_1,\ldots,x_{j-1} x 1 , … , x j − 1 of the previous comparisons, and record x j = 1 { u j ≥ c j } x_j=\mathbf{1}\{u_j\ge c_j\} x j = 1 { u j ≥ c j } . Finally output a real number that depends only on x 1 , … , x d x_1,\ldots,x_d x 1 , … , x d . Equivalently, T \mathcal{T} T is computed by a decision tree that queries u 1 , … , u d u_1,\ldots,u_d u 1 , … , u d in this order, each query a threshold comparison.
Each row f i f_i f i of the exact guide is an ordered threshold tree: for j ≤ i j\le i j ≤ i the threshold is c j = 1 − p j ( x < j ) c_j=1-p_j(x_{<j}) c j = 1 − p j ( x < j ) , the later comparisons are ignored, and the output is x i x_i x i . Earlier inputs influence a later threshold only through the earlier binary decisions.
For c ∈ [ 0 , 1 ] c\in[0,1] c ∈ [ 0 , 1 ] put h ( c ) = w c ( 1 − c ) h(c)=wc(1-c) h ( c ) = w c ( 1 − c ) . To smooth an ordered threshold tree, draw independent fair signs σ 1 , … , σ d ∈ { − 1 , 1 } \sigma_1,\ldots,\sigma_d\in\{-1,1\} σ 1 , … , σ d ∈ { − 1 , 1 } , independent of the uniform inputs, and in the j j j th comparison replace c j c_j c j by c j + σ j h ( c j ) c_j+\sigma_jh(c_j) c j + σ j h ( c j ) . Here c j c_j c j is the threshold at the node reached by the perturbed comparisons. Write T σ ( U ) \mathcal{T}^{\sigma}(U) T σ ( U ) for the resulting output, and define its smoothing by averaging the signs at fixed inputs:
g T ( u ) = E σ T σ ( u ) . (34) g_{\mathcal{T}}(u)=\mathbb{E}_{\sigma}\mathcal{T}^{\sigma}(u). \tag*{(34)} g T ( u ) = E σ T σ ( u ) . (34)
We call this perturbation and averaging operation threshold smoothing , and g T g_{\mathcal{T}} g T the smoothing of T \mathcal{T} T ; it need not be continuous. Both shifted thresholds lie in [ 0 , 1 ] [0,1] [ 0 , 1 ] . Conditional on the preceding inputs and signs, the probability of taking branch 1 is
1 2 ( 1 − c j − h ( c j ) ) + 1 2 ( 1 − c j + h ( c j ) ) = 1 − c j . \frac{1}{2}(1-c_j-h(c_j))+\frac{1}{2}(1-c_j+h(c_j))=1-c_j. 2 1 ( 1 − c j − h ( c j )) + 2 1 ( 1 − c j + h ( c j )) = 1 − c j .
By induction on j j j , the perturbed outcomes ( x 1 , … , x d ) (x_1,\ldots,x_d) ( x 1 , … , x d ) , with inputs and signs random, have the same law as the unperturbed ones. In particular, under the joint law of ( U , σ ) (U,\sigma) ( U , σ ) , T σ ( U ) \mathcal{T}^{\sigma}(U) T σ ( U ) has the law of T ( U ) \mathcal{T}(U) T ( U ) , and E g T = E T \mathbb{E}g_{\mathcal{T}}=\mathbb{E}\mathcal{T} E g T = E T .
For the exact guide, use one perturbed sequential run for all rows: with independent uniform inputs U i U_i U i and independent fair signs σ i \sigma_i σ i , set
c i σ = 1 − p i ( X < i σ ) , X i σ = 1 { U i ≥ c i σ + σ i h ( c i σ ) } , g ( U ) = E σ [ X σ ∣ U ] . (35) c_i^{\sigma}=1-p_i(X_{<i}^{\sigma}),\qquad X_i^{\sigma}=\mathbf{1}\{U_i\ge c_i^{\sigma}+\sigma_i h(c_i^{\sigma})\},\qquad g(U)=\mathbb{E}_{\sigma}[X^{\sigma}\mid U]. \tag*{(35)} c i σ = 1 − p i ( X < i σ ) , X i σ = 1 { U i ≥ c i σ + σ i h ( c i σ )} , g ( U ) = E σ [ X σ ∣ U ] . (35)
Thus g i = g f i g_i=g_{f_i} g i = g f i . Averaging each row with its own independent sign sequence would give the same g g g . By the calculation above, X σ ∼ μ X^{\sigma}\sim\mu X σ ∼ μ when inputs and signs are both random; for fixed signs the law is in general different. The shared run gives one random Boolean vector X σ X^{\sigma} X σ with conditional mean g ( U ) g(U) g ( U ) and law μ \mu μ , which the potential bound of Proposition 5.5 needs.
The two guarantees. Proposition 5.5 bounds the objective gap of the smoothed guide, and Theorem 5.6 bounds the high-degree tails of the smoothing of any ordered threshold tree. Together they prove Theorem 5.3 .
Proposition 5.5 (Near-optimal objective value for the smoothed guide). The guide g g g of (5.2) has the following properties.
(1) g g g is a guide.
(2) With X ∼ μ X \sim\mu X ∼ μ , c i = 1 − p i ( X < i ) c_i = 1 - p_i(X_{<i}) c i = 1 − p i ( X < i ) and Δ w ( c ) = H ( c ) − 1 2 H ( c − h ( c ) ) − 1 2 H ( c + h ( c ) ) \Delta_w(c) = \mathrm{H}(c) - \frac{1}{2}\mathrm{H}(c-h(c)) - \frac{1}{2}\mathrm{H}(c+h(c)) Δ w ( c ) = H ( c ) − 2 1 H ( c − h ( c )) − 2 1 H ( c + h ( c )) ,
H ( μ ) − ∑ i = 1 d E [ a ( U i ) g i ( U ) ] = ∑ i = 1 d E Δ w ( c i ) . (36) \mathrm{H}(\mu)-\sum_{i=1}^{d}\mathbb{E}[a(U_i)g_i(U)]=\sum_{i=1}^{d}\mathbb{E}\Delta_w(c_i). \tag*{(36)} H ( μ ) − i = 1 ∑ d E [ a ( U i ) g i ( U )] = i = 1 ∑ d E Δ w ( c i ) . (36) (3) For every c ∈ [ 0 , 1 ] c \in[0,1] c ∈ [ 0 , 1 ] , 0 ≤ Δ w ( c ) ≤ w 2 c ( 1 − c ) 0 \leq\Delta_w(c) \leq w^2c(1-c) 0 ≤ Δ w ( c ) ≤ w 2 c ( 1 − c ) .
(4) E Φ L ( g ( U ) ) ≥ E μ Φ \mathbb{E}\Phi^{\mathrm{L}}(g(U)) \geq\mathbb{E}_{\mu}\Phi E Φ L ( g ( U )) ≥ E μ Φ . Consequently
0 ≤ log Z Φ − P ( g ) ≤ w 2 ∑ i = 1 d E [ c i ( 1 − c i ) ] ≤ d w 2 4 . (37) 0 \leq\log Z_{\Phi}-P(g) \leq w^2\sum_{i=1}^{d}\mathbb{E}[c_i(1-c_i)] \leq\frac{dw^2}{4}. \tag*{(37)} 0 ≤ log Z Φ − P ( g ) ≤ w 2 i = 1 ∑ d E [ c i ( 1 − c i )] ≤ 4 d w 2 . (37)
Theorem 5.6 (Energy identity). Let T \mathcal{T} T be an ordered threshold tree on d d d coordinates and g T g_{\mathcal{T}} g T its smoothing. Then
∑ S ⊆ [ d ] ( 1 − w 2 ) − ∣ S ∣ ∥ ( g T ) S ∥ 2 2 = ∥ T ∥ 2 2 . (38) \sum_{S\subseteq[d]}\left(1-\frac{w}{2}\right)^{-|S|}\lVert(g_{\mathcal{T}})_S\rVert_2^2=\lVert\mathcal{T}\rVert_2^2. \tag*{(38)} S ⊆ [ d ] ∑ ( 1 − 2 w ) − ∣ S ∣ ∥( g T ) S ∥ 2 2 = ∥ T ∥ 2 2 . (38) Consequently ∑ S ≠ ∅ ( 1 − w / 2 ) − ∣ S ∣ ∥ ( g T ) S ∥ 2 2 = Var ( T ) \sum_{S\ne\varnothing}(1-w/2)^{-|S|}\lVert(g_{\mathcal{T}})_S\rVert_2^2=\operatorname{Var}(\mathcal{T}) ∑ S = ∅ ( 1 − w /2 ) − ∣ S ∣ ∥( g T ) S ∥ 2 2 = Var ( T ) , and for every integer D ≥ 0 D\geq0 D ≥ 0 ,
∥ Π > D g T ∥ 2 2 ≤ ( 1 − w 2 ) D + 1 Var ( T ) . (39) \lVert\Pi_{>D}g_{\mathcal{T}}\rVert_2^2\leq\left(1-\frac{w}{2}\right)^{D+1}\operatorname{Var}(\mathcal{T}). \tag*{(39)} ∥ Π > D g T ∥ 2 2 ≤ ( 1 − 2 w ) D + 1 Var ( T ) . (39)
Proof of Theorem 5.3 . Take g g g as in (5.2). By Proposition 5.5 it is a guide satisfying the near-optimal objective value guarantee (i). For the low-degree approximation guarantee (ii), apply (5.6) to the ordered threshold tree f i f_i f i , whose variance is at most 1 / 4 1/4 1/4 .
Theorem 5.3 supplies the witness required by Theorem 4.1 , which completes the main line.
Proof of Theorem 2.2 . Apply the generic estimator of Theorem 4.1 with b ∗ = d w 2 / 4 b_* = dw^2/4 b ∗ = d w 2 /4 and D = min { d , ⌈ 4 κ / w ⌉ } D=\min\{d,\lceil4\kappa/w\rceil\} D = min { d , ⌈ 4 κ / w ⌉} . Apply Theorem 5.3 to the normalized potential Φ v \Phi_v Φ v of each residual, which is supermodular with k ≤ d k\leq d k ≤ d free coordinates; its objective gap is at most k w 2 / 4 ≤ b ∗ kw^2/4\leq b_* k w 2 /4 ≤ b ∗ . If D < d D<d D < d , item (ii) of Theorem 5.3 and 1 − w / 2 ≤ e − w / 2 1-w/2\leq e^{-w/2} 1 − w /2 ≤ e − w /2 give ∥ Π > D g i ∥ 2 2 ≤ 1 2 e − κ ≤ 1 / ( 128 d G 0 ) \lVert\Pi_{>D}g_i\rVert_2^2\leq\frac{1}{2}e^{-\kappa}\leq1/(128dG_0) ∥ Π > D g i ∥ 2 2 ≤ 2 1 e − κ ≤ 1/ ( 128 d G 0 ) ; if D = d D=d D = d the tail vanishes. The generic cost is (4.3), and D = O ( w − 1 log ( d + B ) ) D=O(w^{-1}\log(d+B)) D = O ( w − 1 log ( d + B )) .
Quadratic objective gap. It remains to prove Proposition 5.5 and Theorem 5.6 . The objective gap uses the one-bit identity (3.5) for the linear score and the averaging argument of (3.15) for the potential term.
Proof of Proposition 5.5 . (1) Each X i σ X_i^\sigma X i σ is Boolean and depends only on U ≤ i , σ ≤ i U_{\leq i},\sigma_{\leq i} U ≤ i , σ ≤ i , so its average lies in [ 0 , 1 ] [0,1] [ 0 , 1 ] and depends only on U ≤ i U_{\leq i} U ≤ i .
(2) Conditional on U < i , σ < i U_{<i},\sigma_{<i} U < i , σ < i , c i σ c_i^\sigma c i σ is fixed and ( U i , σ i ) (U_i,\sigma_i) ( U i , σ i ) is fresh. By (3.5),
E [ a ( U i ) X i σ ∣ U < i , σ < i ] = 1 2 H ( c i σ − h ( c i σ ) ) + 1 2 H ( c i σ + h ( c i σ ) ) . \mathbb{E}[a(U_i)X_i^\sigma\mid U_{<i},\sigma_{<i}]=\frac{1}{2}\mathrm{H}(c_i^\sigma-h(c_i^\sigma))+\frac{1}{2}\mathrm{H}(c_i^\sigma+h(c_i^\sigma)). E [ a ( U i ) X i σ ∣ U < i , σ < i ] = 2 1 H ( c i σ − h ( c i σ )) + 2 1 H ( c i σ + h ( c i σ )) .
Since X σ ∼ μ X^\sigma\sim\mu X σ ∼ μ , c i σ c_i^\sigma c i σ has the law of c i c_i c i . Also E [ a ( U i ) g i ( U ) ] = E [ a ( U i ) X i σ ] \mathbb{E}[a(U_i)g_i(U)] = \mathbb{E}[a(U_i)X_i^\sigma] E [ a ( U i ) g i ( U )] = E [ a ( U i ) X i σ ] , and H ( μ ) = ∑ i E H ( c i ) H(\mu) = \sum_i \mathbb{E}H(c_i) H ( μ ) = ∑ i E H ( c i ) by Lemma 3.3 . Subtracting proves (36) .
(3) At c = 0 , 1 c = 0,1 c = 0 , 1 the loss is zero. For 0 < c < 1 0 < c < 1 0 < c < 1 , put h = h ( c ) h = h(c) h = h ( c ) . The two shifted thresholds c ± h c \pm h c ± h have mean c c c , so expanding Bernoulli relative entropy gives
Δ w ( c ) = 1 2 KL ( Ber ( c − h ) ∥ Ber ( c ) ) + 1 2 KL ( Ber ( c + h ) ∥ Ber ( c ) ) . (40) \Delta_w(c) = \frac{1}{2}\operatorname{KL}(\operatorname{Ber}(c-h)\Vert\operatorname{Ber}(c)) + \frac{1}{2}\operatorname{KL}(\operatorname{Ber}(c+h)\Vert\operatorname{Ber}(c)). \tag*{(40)} Δ w ( c ) = 2 1 KL ( Ber ( c − h ) ∥ Ber ( c )) + 2 1 KL ( Ber ( c + h ) ∥ Ber ( c )) . (40)
The inequality log t ≤ t − 1 \log t \le t - 1 log t ≤ t − 1 yields
KL ( Ber ( q ) ∥ Ber ( c ) ) ≤ ( q − c ) 2 c ( 1 − c ) ( 0 ≤ q ≤ 1 ) , \operatorname{KL}(\operatorname{Ber}(q)\Vert\operatorname{Ber}(c)) \le\frac{(q-c)^2}{c(1-c)} \qquad(0 \le q \le1), KL ( Ber ( q ) ∥ Ber ( c )) ≤ c ( 1 − c ) ( q − c ) 2 ( 0 ≤ q ≤ 1 ) ,
by applying it to the two probability ratios. Hence 0 ≤ Δ w ( c ) ≤ h 2 / [ c ( 1 − c ) ] = w 2 c ( 1 − c ) 0 \le\Delta_w(c) \le h^2/[c(1-c)] = w^2c(1-c) 0 ≤ Δ w ( c ) ≤ h 2 / [ c ( 1 − c )] = w 2 c ( 1 − c ) .
(4) Given U U U , the Boolean vector X σ X^\sigma X σ has mean g ( U ) g(U) g ( U ) , so (L5) gives E [ Φ ( X σ ) ∣ U ] ≤ Φ L ( g ( U ) ) \mathbb{E}[\Phi(X^\sigma)\mid U] \le\Phi^L(g(U)) E [ Φ ( X σ ) ∣ U ] ≤ Φ L ( g ( U )) , as in (22) . Averaging and using X σ ∼ μ X^\sigma\sim\mu X σ ∼ μ proves the potential inequality. Together with items (2) and (3) this gives P ( g ) ≥ H ( μ ) + E μ Φ − w 2 ∑ i E [ c i ( 1 − c i ) ] P(g) \ge H(\mu) + \mathbb{E}_\mu\Phi- w^2\sum_i\mathbb{E}[c_i(1-c_i)] P ( g ) ≥ H ( μ ) + E μ Φ − w 2 ∑ i E [ c i ( 1 − c i )] . Now H ( μ ) + E μ Φ = log Z Φ H(\mu) + \mathbb{E}_\mu\Phi= \log Z_\Phi H ( μ ) + E μ Φ = log Z Φ , the lower bound in (37) is Proposition 3.8, and c ( 1 − c ) ≤ 1 / 4 c(1-c) \le1/4 c ( 1 − c ) ≤ 1/4 .
Geometric decay of high-degree tails
We prove Theorem 5.6 by induction on d d d , using only the mean and variance of a single smoothed indicator.
Let ι c = 1 [ c , 1 ) \iota_c = 1_{[c,1)} ι c = 1 [ c , 1 ) be the threshold indicator of Section 3.2. The smoothing of a single comparison is
ϕ c ( u ) = 1 2 ι c − h ( c ) ( u ) + 1 2 ι c + h ( c ) ( u ) . (41) \phi_c(u) = \frac{1}{2}\iota_{c-h(c)}(u) + \frac{1}{2}\iota_{c+h(c)}(u). \tag*{(41)} ϕ c ( u ) = 2 1 ι c − h ( c ) ( u ) + 2 1 ι c + h ( c ) ( u ) . (41)
Lemma 5.7 (Moments of a smoothed indicator). For every c ∈ [ 0 , 1 ] c \in[0,1] c ∈ [ 0 , 1 ] , with p = 1 − c p = 1-c p = 1 − c ,
E ϕ c = p , Var ( ϕ c ) = ( 1 − w 2 ) p ( 1 − p ) . (42) \mathbb{E}\phi_c = p,\qquad\operatorname{Var}(\phi_c) = \left(1-\frac{w}{2}\right)p(1-p). \tag*{(42)} E ϕ c = p , Var ( ϕ c ) = ( 1 − 2 w ) p ( 1 − p ) . (42) Proof. Write h = h ( c ) h = h(c) h = h ( c ) . The two indicators in (41) are nested, with means p + h p+h p + h and p − h p-h p − h , so E ϕ c = p \mathbb{E}\phi_c = p E ϕ c = p and E ϕ c 2 = 1 4 ( p + h ) + 3 4 ( p − h ) = p − h / 2 \mathbb{E}\phi_c^2 = \frac{1}{4}(p+h) + \frac{3}{4}(p-h) = p-h/2 E ϕ c 2 = 4 1 ( p + h ) + 4 3 ( p − h ) = p − h /2 . Subtracting p 2 p^2 p 2 gives p ( 1 − p ) − h / 2 = ( 1 − w / 2 ) c ( 1 − c ) p(1-p)-h/2 = (1-w/2)c(1-c) p ( 1 − p ) − h /2 = ( 1 − w /2 ) c ( 1 − c ) . This also holds at c = 0 , 1 c = 0,1 c = 0 , 1 , where h = 0 h = 0 h = 0 .
Proof of Theorem 5.6. Put ρ = 1 − w / 2 \rho= 1-w/2 ρ = 1 − w /2 . On any product of input coordinates, use the squared norm
∥ H ∥ ρ 2 = ∑ S ρ − ∣ S ∣ ∥ H S ∥ 2 2 , \lVert H\rVert_\rho^2 = \sum_S \rho^{-|S|}\lVert H_S\rVert_2^2, ∥ H ∥ ρ 2 = S ∑ ρ − ∣ S ∣ ∥ H S ∥ 2 2 ,
with Hoeffding components as in Section 4.1. We prove ∥ g T ∥ ρ 2 = ∥ T ∥ 2 2 \lVert g_T\rVert_\rho^2 = \lVert T\rVert_2^2 ∥ g T ∥ ρ 2 = ∥ T ∥ 2 2 by induction on d d d ; for d = 0 d = 0 d = 0 the tree and its smoothing are the same constant.
For d ≥ 1 d \ge1 d ≥ 1 , let c c c be the first threshold, put p = 1 − c p = 1-c p = 1 − c , and let T ( 1 ) T^{(1)} T ( 1 ) and T ( 0 ) T^{(0)} T ( 0 ) be the two remaining ordered threshold trees, with smoothings g ( 1 ) g^{(1)} g ( 1 ) and g ( 0 ) g^{(0)} g ( 0 ) . Writing u ′ = ( u 2 , … , u d ) u' = (u_2,\ldots,u_d) u ′ = ( u 2 , … , u d ) , independence of the signs gives
g T ( u ) = ϕ c ( u 1 ) g ( 1 ) ( u ′ ) + ( 1 − ϕ c ( u 1 ) ) g ( 0 ) ( u ′ ) = A ( u ′ ) + ( ϕ c ( u 1 ) − p ) H ( u ′ ) , (43) g_T(u) = \phi_c(u_1)g^{(1)}(u') + (1-\phi_c(u_1))g^{(0)}(u') = A(u') + (\phi_c(u_1)-p)H(u'), \tag*{(43)} g T ( u ) = ϕ c ( u 1 ) g ( 1 ) ( u ′ ) + ( 1 − ϕ c ( u 1 )) g ( 0 ) ( u ′ ) = A ( u ′ ) + ( ϕ c ( u 1 ) − p ) H ( u ′ ) , (43)
where A = p g ( 1 ) + ( 1 − p ) g ( 0 ) A = pg^{(1)} + (1-p)g^{(0)} A = p g ( 1 ) + ( 1 − p ) g ( 0 ) and H = g ( 1 ) − g ( 0 ) H = g^{(1)} - g^{(0)} H = g ( 1 ) − g ( 0 ) . The first summand has no interaction involving coordinate 1. In the second, the factor ϕ c − p \phi_c-p ϕ c − p is centered, so a component of H H H on S ⊆ { 2 , … , d } S \subseteq\{2,\ldots,d\} S ⊆ { 2 , … , d } produces a component on S ∪ { 1 } S \cup\{1\} S ∪ { 1 } . Orthogonality and Lemma 5.7 therefore give
∥ g T ∥ ρ 2 = ∥ A ∥ ρ 2 + ρ − 1 Var ( ϕ c ) ∥ H ∥ ρ 2 = ∥ p g ( 1 ) + ( 1 − p ) g ( 0 ) ∥ ρ 2 + p ( 1 − p ) ∥ g ( 1 ) − g ( 0 ) ∥ ρ 2 = p ∥ g ( 1 ) ∥ ρ 2 + ( 1 − p ) ∥ g ( 0 ) ∥ ρ 2 . \begin{aligned}
\lVert g_T\rVert_\rho^2 &= \lVert A\rVert_\rho^2 + \rho^{-1}\operatorname{Var}(\phi_c)\lVert H\rVert_\rho^2 \\
&= \lVert pg^{(1)} + (1-p)g^{(0)}\rVert_\rho^2 + p(1-p)\lVert g^{(1)}-g^{(0)}\rVert_\rho^2 \\
&= p\lVert g^{(1)}\rVert_\rho^2 + (1-p)\lVert g^{(0)}\rVert_\rho^2.
\end{aligned} ∥ g T ∥ ρ 2 = ∥ A ∥ ρ 2 + ρ − 1 Var ( ϕ c ) ∥ H ∥ ρ 2 = ∥ p g ( 1 ) + ( 1 − p ) g ( 0 ) ∥ ρ 2 + p ( 1 − p ) ∥ g ( 1 ) − g ( 0 ) ∥ ρ 2 = p ∥ g ( 1 ) ∥ ρ 2 + ( 1 − p ) ∥ g ( 0 ) ∥ ρ 2 .
The last equality is the usual quadratic identity in an inner-product norm. By the induction hypothesis, the last line equals p ∥ T ( 1 ) ∥ 2 2 + ( 1 − p ) ∥ T ( 0 ) ∥ 2 2 p\lVert T^{(1)}\rVert_2^2+(1-p)\lVert T^{(0)}\rVert_2^2 p ∥ T ( 1 ) ∥ 2 2 + ( 1 − p ) ∥ T ( 0 ) ∥ 2 2 , which is ∥ T ∥ 2 2 \lVert T\rVert_2^2 ∥ T ∥ 2 2 because T T T follows T ( 1 ) T^{(1)} T ( 1 ) when u 1 ≥ c u_1\ge c u 1 ≥ c and T ( 0 ) T^{(0)} T ( 0 ) otherwise. This proves (38) .
The constant component is E g T = E T \mathbb{E}g_T=\mathbb{E}T E g T = E T . Subtracting its square gives the variance identity; for the tail, use ( 1 − w / 2 ) ∣ S ∣ ≤ ( 1 − w / 2 ) D + 1 (1-w/2)^{|S|}\le(1-w/2)^{D+1} ( 1 − w /2 ) ∣ S ∣ ≤ ( 1 − w /2 ) D + 1 when ∣ S ∣ > D |S|>D ∣ S ∣ > D .
The factor ρ − 1 \rho^{-1} ρ − 1 for the added coordinate 1 1 1 exactly offsets the variance that the smoothing removes from the indicator, so the weighted energy passes down the tree without loss. This is an aggregate identity: an individual component’s squared norm need not shrink by ( 1 − w / 2 ) ∣ S ∣ (1-w/2)^{|S|} ( 1 − w /2 ) ∣ S ∣ , as Example 5.8 shows.
Example 5.8. (The path, smoothed). In Example 3.4 with w = 1 / 2 w=1/2 w = 1/2 , the smoothed guide loses approximately 0.0449 0.0449 0.0449 of linear score and gains 0.0018 0.0018 0.0018 in the potential term. Its objective value is approximately log 13 8 − 0.0431 \log\frac{13}{8}-0.0431 log 8 13 − 0.0431 , against the loss bound w 2 ∑ i E [ c i ( 1 − c i ) ] ≈ 0.0880 w^2\sum_i\mathbb{E}[c_i(1-c_i)]\approx0.0880 w 2 ∑ i E [ c i ( 1 − c i )] ≈ 0.0880 in (37) . The exact interaction energies of row 2 are
Table 5.8.
With ρ = 1 − w / 2 = 3 / 4 \rho=1-w/2=3/4 ρ = 1 − w /2 = 3/4 , the table gives
∑ S ⊆ { 1 , 2 } ρ − ∣ S ∣ ∥ ( g 2 ) S ∥ 2 2 = 9 169 + 4 3 ( 2 845 + 619 5070 ) + 16 9 11 1690 = 3 13 = ∥ f 2 ∥ 2 2 . \sum_{S\subseteq\{1,2\}}\rho^{-|S|}\lVert(g_2)_S\rVert_2^2=\frac{9}{169}+\frac{4}{3}\left(\frac{2}{845}+\frac{619}{5070}\right)+\frac{16}{9}\frac{11}{1690}=\frac{3}{13}=\lVert f_2\rVert_2^2. S ⊆ { 1 , 2 } ∑ ρ − ∣ S ∣ ∥( g 2 ) S ∥ 2 2 = 169 9 + 3 4 ( 845 2 + 5070 619 ) + 9 16 1690 11 = 13 3 = ∥ f 2 ∥ 2 2 .
The interaction energy on { 2 } \{2\} { 2 } is multiplied by 619 / 780 619/780 619/780 , which exceeds ρ = 3 / 4 \rho=3/4 ρ = 3/4 .
More generally, fix a common 0 < ρ ≤ 1 0<\rho\le1 0 < ρ ≤ 1 at every node. If each threshold ι c \iota_c ι c is replaced by a function of its input with mean p = 1 − c p=1-c p = 1 − c and variance ρ p ( 1 − p ) \rho p(1-p) ρp ( 1 − p ) , the recursion (43) gives the same identity with this ρ \rho ρ . If every variance is at most ρ p ( 1 − p ) \rho p(1-p) ρp ( 1 − p ) , it gives the corresponding inequality. For example, resampling the queried input replaces ι c \iota_c ι c by ( 1 − τ ) ι c + τ ( 1 − c ) (1-\tau)\iota_c+\tau(1-c) ( 1 − τ ) ι c + τ ( 1 − c ) and turns T T T into T τ T T_\tau T T τ T . Its variance factor is ( 1 − τ ) 2 (1-\tau)^2 ( 1 − τ ) 2 , and the identity holds component by component: ∑ S ( 1 − τ ) − 2 ∣ S ∣ ∥ ( T τ T ) S ∥ 2 2 = ∥ T ∥ 2 2 \sum_S(1-\tau)^{-2|S|}\lVert(T_\tau T)_S\rVert_2^2=\lVert T\rVert_2^2 ∑ S ( 1 − τ ) − 2∣ S ∣ ∥( T τ T ) S ∥ 2 2 = ∥ T ∥ 2 2 . With ( 1 − τ ) 2 = 1 − w / 2 (1-\tau)^2=1-w/2 ( 1 − τ ) 2 = 1 − w /2 , that is, τ = w / 4 + O ( w 2 ) \tau=w/4+O(w^2) τ = w /4 + O ( w 2 ) , resampling removes the same fraction of variance as threshold smoothing, but on a fair bit it lowers the score by τ log 2 \tau\log2 τ log 2 , whereas threshold smoothing lowers it only from log 2 \log2 log 2 to H ( 1 / 2 + w / 4 ) = log 2 − O ( w 2 ) H(1/2+w/4)=\log2-O(w^2) H ( 1/2 + w /4 ) = log 2 − O ( w 2 ) .
The cost of variance reduction. The energy identity shows how variance contraction at each comparison controls the decay of high-degree tails. We now bound the linear-score loss required for a given variance reduction.
Proposition 5.9. (The cost of smoothing one threshold). For c ∈ ( 0 , 1 ) c\in(0,1) c ∈ ( 0 , 1 ) , put p = 1 − c p=1-c p = 1 − c and recall ι c = 1 [ c , 1 ) \iota_c=\mathbf{1}_{[c,1)} ι c = 1 [ c , 1 ) . Write Var ( ϕ ) \operatorname{Var}(\phi) Var ( ϕ ) for the variance of ϕ ( U 1 ) \phi(U_1) ϕ ( U 1 ) . Every measurable ϕ : ( 0 , 1 ) → [ 0 , 1 ] \phi:(0,1)\to[0,1] ϕ : ( 0 , 1 ) → [ 0 , 1 ] with ∫ 0 1 ϕ = p \int_0^1\phi=p ∫ 0 1 ϕ = p satisfies
H ( p ) − ∫ 0 1 a ϕ ≥ 3 32 c ( 1 − c ) ( Var ( ι c ) − Var ( ϕ ) ) 2 . (44) H(p)-\int_0^1a\phi\ge\frac{3}{32c(1-c)}\left(\operatorname{Var}(\iota_c)-\operatorname{Var}(\phi)\right)^2. \tag*{(44)} H ( p ) − ∫ 0 1 a ϕ ≥ 32 c ( 1 − c ) 3 ( Var ( ι c ) − Var ( ϕ ) ) 2 . (44)
Proof. The map ϕ ↦ 1 − ϕ ( 1 − ⋅ ) \phi\mapsto1-\phi(1-\mathord\cdot) ϕ ↦ 1 − ϕ ( 1 − ⋅ ) exchanges c c c and 1 − c 1-c 1 − c and, since a a a is antisymmetric with ∫ 0 1 a = 0 \int_0^1a=0 ∫ 0 1 a = 0 , preserves both sides of (44) ; so assume c ≤ 1 / 2 c\le1/2 c ≤ 1/2 . Put ψ = ι c − ϕ \psi=\iota_c-\phi ψ = ι c − ϕ and t = ∫ 0 1 ∣ ψ ∣ t=\int_0^1|\psi| t = ∫ 0 1 ∣ ψ ∣ . Then ∫ 0 1 ψ = 0 \int_0^1\psi=0 ∫ 0 1 ψ = 0 , ∣ ψ ∣ ≤ 1 |\psi|\le1 ∣ ψ ∣ ≤ 1 , and ψ \psi ψ has the same sign as u − c u-c u − c . The variance deficit is
Var ( ι c ) − Var ( ϕ ) = ∫ 0 1 ϕ ( 1 − ϕ ) ∈ [ 0 , t ] , (45) \operatorname{Var}(\iota_c)-\operatorname{Var}(\phi)=\int_0^1\phi(1-\phi)\in[0,t], \tag*{(45)} Var ( ι c ) − Var ( ϕ ) = ∫ 0 1 ϕ ( 1 − ϕ ) ∈ [ 0 , t ] , (45)
because ϕ ( 1 − ϕ ) ≤ ∣ ψ ∣ \phi(1-\phi)\leq|\psi| ϕ ( 1 − ϕ ) ≤ ∣ ψ ∣ pointwise. Since ∫ 0 1 ψ = 0 \int_{0}^{1}\psi=0 ∫ 0 1 ψ = 0 , each of ( 0 , c ) (0,c) ( 0 , c ) and [ c , 1 ) [c,1) [ c , 1 ) carries mass t / 2 t/2 t /2 of ∣ ψ ∣ |\psi| ∣ ψ ∣ , and t / 2 ≤ c t/2\leq c t /2 ≤ c . Since ∫ c 1 a ( u ) d u = H ( p ) \int_{c}^{1}a(u)\,\mathrm{d}u=\mathsf{H}(p) ∫ c 1 a ( u ) d u = H ( p ) ,
H ( p ) − ∫ 0 1 a ϕ = ∫ 0 1 ( a ( u ) − a ( c ) ) ψ ( u ) d u . \mathsf{H}(p)-\int_{0}^{1}a\phi=\int_{0}^{1}(a(u)-a(c))\psi(u)\,\mathrm{d}u. H ( p ) − ∫ 0 1 a ϕ = ∫ 0 1 ( a ( u ) − a ( c )) ψ ( u ) d u .
where a ( c ) − a ( u ) ≥ log ( c / u ) ≥ ( c − u ) / c a(c)-a(u)\geq\log(c/u)\geq(c-u)/c a ( c ) − a ( u ) ≥ log ( c / u ) ≥ ( c − u ) / c for u < c u<c u < c and a ( u ) − a ( c ) ≥ log ( u / c ) ≥ ( u − c ) / u a(u)-a(c)\geq\log(u/c)\geq(u-c)/u a ( u ) − a ( c ) ≥ log ( u / c ) ≥ ( u − c ) / u for u > c u>c u > c . On each side, ∣ a ( u ) − a ( c ) ∣ |a(u)-a(c)| ∣ a ( u ) − a ( c ) ∣ increases with the distance from c c c . For this fixed t t t , the bathtub principle minimizes the integral subject to these sign and mass constraints by placing ∣ ψ ∣ = 1 |\psi|=1 ∣ ψ ∣ = 1 on [ c − t / 2 , c + t / 2 ) [c-t/2,c+t/2) [ c − t /2 , c + t /2 ) . Hence
H ( p ) − ∫ 0 1 a ϕ ≥ ∫ c − t / 2 c c − u c d u + ∫ c c + t / 2 u − c c + t / 2 d u = t 2 8 c + t 2 8 ( c + t / 2 ) ≥ 3 t 2 16 c ≥ 3 t 2 32 c ( 1 − c ) ≥ 3 32 c ( 1 − c ) ( Var ( ι c ) − Var ( ϕ ) ) 2 . \begin{aligned}
\mathsf{H}(p)-\int_{0}^{1}a\phi
&\geq\int_{c-t/2}^{c}\frac{c-u}{c}\,\mathrm{d}u+\int_{c}^{c+t/2}\frac{u-c}{c+t/2}\,\mathrm{d}u \\
&=\frac{t^{2}}{8c}+\frac{t^{2}}{8(c+t/2)} \\
&\geq\frac{3t^{2}}{16c}\geq\frac{3t^{2}}{32c(1-c)}
\geq\frac{3}{32c(1-c)}\left(\operatorname{Var}(\iota_c)-\operatorname{Var}(\phi)\right)^{2}.
\end{aligned} H ( p ) − ∫ 0 1 a ϕ ≥ ∫ c − t /2 c c c − u d u + ∫ c c + t /2 c + t /2 u − c d u = 8 c t 2 + 8 ( c + t /2 ) t 2 ≥ 16 c 3 t 2 ≥ 32 c ( 1 − c ) 3 t 2 ≥ 32 c ( 1 − c ) 3 ( Var ( ι c ) − Var ( ϕ ) ) 2 .
□ \square □
Threshold smoothing removes variance w c ( 1 − c ) / 2 wc(1-c)/2 w c ( 1 − c ) /2 (Lemma 5.7) and loses at most w 2 c ( 1 − c ) w^{2}c(1-c) w 2 c ( 1 − c ) of linear score (Proposition 5.5). For the variance contraction ρ = 1 − w / 2 \rho=1-w/2 ρ = 1 − w /2 , its linear-score loss is therefore within a factor 128 / 3 128/3 128/3 of the minimum over all replacements with the same mean and variance, uniformly for 0 < c < 1 0<c<1 0 < c < 1 .
Closing remarks
Discussion
Log-supermodularity. Our algorithm treats #BIS through the more general problem of counting with efficiently evaluable positive log-supermodular weights. Log-supermodularity also plays a central role in classifications of approximate counting problems [4 , 9 ] . The general log-supermodular counting problem is #BIS-hard, but is not known to be #BIS-equivalent. Our algorithm may therefore be solving a strictly harder problem than #BIS. Can one establish #BIS-equivalence, or identify a separation that can be exploited to obtain faster algorithms for #BIS?
Bipartite and general hard-core models. Extending our counting or sampling bound to general hard-core models, including fugacities approaching the uniqueness threshold, would also speed up SAT algorithms. Our companion paper [52 Theorems 1.6 and 2.8] shows that an exp ( O ~ ( n 1 / 3 ) ) \exp(\widetilde{O}(n^{1/3})) exp ( O ( n 1/3 )) hard-core sampling algorithm for general graphs at fixed accuracy in this setting would give a randomized SAT algorithm running in exp ( O ~ ( s 3 / 5 ) ) \exp(\widetilde{O}(s^{3/5})) exp ( O ( s 3/5 )) time on inputs of binary length s s s .
Open questions
Improving the running time. For arbitrary bipartite graphs, can the exponent 1 / 3 1/3 1/3 be reduced, and is a quasi-polynomial-time approximation scheme or an FPRAS possible? Within our approach, Proposition 2.1 reduces this question to the accuracy and cost of lower estimates on every pinned residual. Additive error log O ( 1 ) n \log^{O(1)}n log O ( 1 ) n at quasi-polynomial cost would suffice for a quasi-polynomial scheme; error O ( log n ) O(\log n) O ( log n ) at polynomial cost would suffice for an FPRAS and polynomial-time sampling.
Improving the estimator. Write Q = log d log ( d + B ) Q = \log d \log(d + B) Q = log d log ( d + B ) . For fixed p > 0 p > 0 p > 0 , an objective gap O ( d w p ) O(dw^p) O ( d w p ) and estimation cost exp ( O ( Q / w ) ) \exp(O(Q/w)) exp ( O ( Q / w )) up to polynomial factors, uniformly over residuals and 0 < w ≤ 1 / 2 0 < w \le1/2 0 < w ≤ 1/2 , give a total exponent O ( d w p + Q / w ) O(dw^p+Q/w) O ( d w p + Q / w ) by Proposition 2.1 . Balancing at w = ( Q / d ) 1 / ( p + 1 ) w = (Q/d)^{1/(p+1)} w = ( Q / d ) 1/ ( p + 1 ) , with enumeration if this exceeds 1 / 2 1/2 1/2 , gives
O ( d 1 / ( p + 1 ) Q p / ( p + 1 ) ) . O\left(d^{1/(p+1)}Q^{p/(p+1)}\right). O ( d 1/ ( p + 1 ) Q p / ( p + 1 ) ) .
Resampling has p = 1 p = 1 p = 1 with w = τ w = \tau w = τ , and threshold smoothing has p = 2 p = 2 p = 2 . Changing only the constants in these bounds leaves these powers unchanged.
Proposition 5.9 shows that threshold smoothing is optimal up to an absolute constant in linear-score loss at its given variance reduction. Potential gains can offset score losses (Example 5.8), so the proposition gives no corresponding lower bound on the full objective gap. Can a sharper analysis of the full objective, a different guide construction, or better control of interaction tails improve this balance and reduce the exponent 1 / 3 1/3 1/3 ?
Quantitative reductions. Approximation-preserving reductions may enlarge instances and alter accuracy requirements, so their quantitative costs must be composed with our running-time bound. Which problems in the # B I S \#\mathrm{BIS} # BIS -equivalence class admit reductions, or direct log-supermodular representations, that preserve a comparable saving in their natural size parameters?
Acknowledgements
We thank Weiming Feng and Heng Guo for constructive feedback during early stages of the project.
AI methodology
The coarse estimator idea first emerged during interactions with GPT 5.5 Pro. The first such construction was suggested by GPT 6 Pro on 7 October 2026, when the authors asked specifically for ideas that make use of convex optimization (with pointers to OpenAI’s math GitHub repo) and “the difference between bipartite q q q -coloring and # B I S \#\mathrm{BIS} # BIS ” (with a note on bipartite q q q -coloring from Heng Guo through private communication). The initial proof completed by AI claimed an algorithm running in time exp ( n ( ( log log n ) 2 log n ) 1 / 5 ) \exp\left(n\left(\frac{(\log\log n)^2}{\log n}\right)^{1/5}\right) exp ( n ( l o g n ( l o g l o g n ) 2 ) 1/5 ) . We subsequently identified the Sinclair–Jerrum walk on the self-reduction tree, the variational principle on that tree, and the use of the Lovász extension as implicit ingredients hidden in the proofs. We also abstracted the log-supermodular structure underlying the algorithm, leading to the current organization and presentation of the paper. OpenAI Codex assisted with mathematical development, finite-algorithm accounting, source drafting, literature checks, and bibliography preparation. We also used Codex and Claude to help polish and check proofs.
Algorithmic and bit implementation details
We first give the quantitative conversion promised in Proposition 2.1 , then implement the algorithm with bit operations and independent fair random bits.
Conventions. In the exact-arithmetic algorithm, a fixed rule resolves bin and transition boundaries. Integer indices are obtained by comparisons and binary search, with the logarithm of their range charged to the operation count. The bit implementation uses the following conventions. Integers are encoded in binary, and a rational by its numerator and denominator. Arithmetic, comparisons and memory access are charged by bit complexity. Every loop, transition and evaluation has a predetermined cap, so all bounds hold on every execution. There is no transcendental primitive: logarithms of rationals and the constant log 2 \log2 log 2 are computed to absolute error 2 − ℓ 2^{-\ell} 2 − ℓ , with certified error bounds, in time polynomial in ℓ \ell ℓ and the input length [6 ] . The evaluator returns W ( x ) W(x) W ( x ) for every configuration x x x as a rational whose numerator and denominator have at most B B B bits, in at most T W T_W T W bit operations. Accuracy and failure-probability parameters are rationals, and ℓ p a r \ell_{\mathrm{par}} ℓ par denotes the total length of their encodings. Each is first rounded down to a power of two, within a factor two, at cost poly ( ℓ p a r ) \operatorname{poly}(\ell_{\mathrm{par}}) poly ( ℓ par ) .
Theorem A.1 (Bit model). When the cost counts bit operations and fair random bits, Theorems 1.1 and 1.2 and Corollary 2.3 hold for rational accuracy and failure-probability parameters with the same exponential factors and with the polynomial factors multiplied by poly ( ℓ p a r ) \operatorname{poly}(\ell_{\mathrm{par}}) poly ( ℓ par ) . On every execution the sampler of Theorem 1.2 returns a configuration, that of Theorem 1.1 an independent set, and the counters and additive estimator return rationals.
Quantitative conversion from coarse estimates
Keep the tree and residual notation of Section 2.1. We give the tree walk and the failure-probability and time bounds used in Proposition 2.1. The conversion is classical [56 SJ89] ; we track the constants because the ratio e b e^b e b between estimates and masses, the distortion of (A.1) below, is superpolynomial and its exponent enters the main bound, and because Appendix A.3 needs explicit caps. The walk is that of Sinclair and Jerrum [SJ89, Section 4], and Lemma A.3 states the weighted form of their bounds that we use.
Counting from residual samples.
Proposition A.2 (Counting from the sampler). Suppose that the residual law of every node can be sampled within total variation distance η \eta η at cost C s poly ( d , log ( 1 / η ) ) C_{\mathrm{s}} \operatorname{poly}(d,\log(1/\eta)) C s poly ( d , log ( 1/ η )) . Then relative counting of Z W Z_W Z W with error 0 < ϵ ≤ 1 / 2 0<\epsilon\le1/2 0 < ϵ ≤ 1/2 and failure probability 0 < δ ≤ 1 / 2 0<\delta\le1/2 0 < δ ≤ 1/2 costs ( C s + T W ) poly ( d , ϵ − 1 , log ( 1 / δ ) ) (C_{\mathrm{s}}+T_W)\operatorname{poly}(d,\epsilon^{-1},\log(1/\delta)) ( C s + T W ) poly ( d , ϵ − 1 , log ( 1/ δ )) on every execution.
Proof. Put
n c = ⌈ 8192 d ϵ − 2 ⌉ ⌈ log 2 ( 4 d / δ ) ⌉ . n_{\mathrm{c}}=\left\lceil8192d\epsilon^{-2}\right\rceil\left\lceil\log_2(4d/\delta)\right\rceil. n c = ⌈ 8192 d ϵ − 2 ⌉ ⌈ log 2 ( 4 d / δ ) ⌉ . For i = 1 , … , d i=1,\ldots,d i = 1 , … , d , with the prefix x < i x_{<i} x < i already chosen, draw n c n_{\mathrm{c}} n c samples from the residual law of x < i x_{<i} x < i within total variation distance ϵ / ( 128 d ) \epsilon/(128d) ϵ / ( 128 d ) , each with fresh randomness. Let x i x_i x i be the more frequent value of coordinate i i i among them, with ties broken toward zero, and let μ ^ i ≥ 1 / 2 \widehat{\mu}_i\ge1/2 μ i ≥ 1/2 be its frequency. Return Z ^ = W ( x ) / ∏ i μ ^ i \widehat{Z}=W(x)/\prod_i\widehat{\mu}_i Z = W ( x ) / ∏ i μ i .
With μ i = μ W ( X i = x i ∣ X < i = x < i ) \mu_i=\mu_W(X_i=x_i\mid X_{<i}=x_{<i}) μ i = μ W ( X i = x i ∣ X < i = x < i ) , the chain rule (4) gives Z W = W ( x ) / ∏ i μ i Z_W=W(x)/\prod_i\mu_i Z W = W ( x ) / ∏ i μ i exactly. Conditional on the earlier choices, each value of coordinate i i i has a sampled frequency whose mean is within ϵ / ( 128 d ) \epsilon/(128d) ϵ / ( 128 d ) of its conditional probability. By Hoeffding’s inequality [46 ] , a further deviation larger than ϵ / ( 128 d ) \epsilon/(128d) ϵ / ( 128 d ) has probability at most 2 exp ( − 2 n c ϵ 2 / ( 128 d ) 2 ) ≤ δ / ( 2 d ) 2\exp(-2n_{\mathrm{c}}\epsilon^2/(128d)^2)\le\delta/(2d) 2 exp ( − 2 n c ϵ 2 / ( 128 d ) 2 ) ≤ δ / ( 2 d ) . The two frequencies are complementary, so with probability at least 1 − δ 1-\delta 1 − δ every level has ∣ μ ^ i − μ i ∣ ≤ ϵ / ( 64 d ) |\widehat{\mu}_i-\mu_i|\le\epsilon/(64d) ∣ μ i − μ i ∣ ≤ ϵ / ( 64 d ) , and then μ i ≥ 1 / 2 − 1 / 128 ≥ 1 / 3 \mu_i\ge1/2-1/128\ge1/3 μ i ≥ 1/2 − 1/128 ≥ 1/3 . The logarithm is 3-Lipschitz on [ 1 / 3 , 1 ] [1/3,1] [ 1/3 , 1 ] , so
∣ log Z ^ Z W ∣ ≤ 3 ∑ i ∣ μ ^ i − μ i ∣ ≤ 3 ϵ 64 , \left|\log\frac{\widehat{Z}}{Z_W}\right|\le3\sum_i|\widehat{\mu}_i-\mu_i|\le\frac{3\epsilon}{64}, log Z W Z ≤ 3 i ∑ ∣ μ i − μ i ∣ ≤ 64 3 ϵ , and 1 − ϵ ≤ Z ^ / Z W ≤ 1 + ϵ 1-\epsilon\le\widehat{Z}/Z_W\le1+\epsilon 1 − ϵ ≤ Z / Z W ≤ 1 + ϵ for 0 < ϵ ≤ 1 / 2 0<\epsilon\le1/2 0 < ϵ ≤ 1/2 . On every execution μ ^ i ≥ 1 / 2 \widehat{\mu}_i\ge1/2 μ i ≥ 1/2 , so Z ^ \widehat{Z} Z is finite. The algorithm makes exactly d n c dn_{\mathrm{c}} d n c sampler calls, each of cost C s poly ( d , log ( d / ϵ ) ) C_{\mathrm{s}}\operatorname{poly}(d,\log(d/\epsilon)) C s poly ( d , log ( d / ϵ )) , and one evaluation of W W W .
The Sinclair–Jerrum walk. As explained in Section 2.2, Sinclair and Jerrum [SJ89, Section 4] replace the one-way descent by a reversible walk on the tree. Suppose that every node v v v carries a mass estimate q v > 0 q_v>0 q v > 0 and that, for a distortion B ≥ 1 \mathcal{B}\ge1 B ≥ 1 ,
Z v / B ≤ q v ≤ Z v at every node v , q x = W ( x ) at every leaf x . (46) Z_v/\mathcal{B}\le q_v\le Z_v\quad\text{at every node }v,\qquad q_x=W(x)\quad\text{at every leaf }x. \tag*{(46)} Z v / B ≤ q v ≤ Z v at every node v , q x = W ( x ) at every leaf x . (46)
No estimate is required to equal the sum of the estimates of its children. For depth ( v ) < d \operatorname{depth}(v)<d depth ( v ) < d the estimates determine the conditional marginal probabilities only within the factor B \mathcal{B} B , p v / B ≤ q v 1 / ( q v 0 + q v 1 ) ≤ B p v p_v/\mathcal{B}\le q_{v1}/(q_{v0}+q_{v1})\le\mathcal{B}p_v p v / B ≤ q v 1 / ( q v 0 + q v 1 ) ≤ B p v , so a descent driven by them loses a factor at every level. The walk avoids this loss.
As in [SJ89, (8)–(10)], give the edge between a node v ≠ o v\ne o v = o and its parent v − v^{-} v − the weight q v q_v q v , the estimate at its lower endpoint, and give every node v v v the weighted degree
s v = 1 { v ≠ o } q v + ∑ y child of v q y . (47) s_v=\mathbf{1}\{v\ne o\}q_v+\sum_{y\text{ child of }v}q_y. \tag*{(47)} s v = 1 { v = o } q v + y child of v ∑ q y . (47)
the total weight of its edges, which Sinclair and Jerrum write d ( v ) d(v) d ( v ) . Let S o = ∑ v s v S_o = \sum_v s_v S o = ∑ v s v . The walk P t r P_{\mathrm{tr}} P tr holds with probability 1 / 2 1/2 1/2 and otherwise moves along an edge at the current node, chosen with probability proportional to its weight:
P t r ( v , y ) = q y 2 s v ( y a child of v ) , P t r ( v , v − ) = q v 2 s v ( v ≠ o ) , P t r ( v , v ) = 1 2 . P_{\mathrm{tr}}(v,y)=\frac{q_y}{2s_v}\quad(y\text{ a child of }v),\qquad P_{\mathrm{tr}}(v,v^{-})=\frac{q_v}{2s_v}\quad(v\ne o),\qquad P_{\mathrm{tr}}(v,v)=\frac{1}{2}. P tr ( v , y ) = 2 s v q y ( y a child of v ) , P tr ( v , v − ) = 2 s v q v ( v = o ) , P tr ( v , v ) = 2 1 .
Exact leaf weights make its stationary law, conditioned on the leaves, equal to μ W \mu_W μ W ; the distortion affects only the mixing time and the stationary probability of the leaves.
Lemma A.3 (Sinclair–Jerrum walk). Consider any rooted tree whose leaves all have depth d ≥ 1 d\ge1 d ≥ 1 , with the chain P t r P_{\mathrm{tr}} P tr and the notation above defined on it. Give each leaf x x x a weight ω x > 0 \omega_x>0 ω x > 0 , let Z v Z_v Z v be the sum of the weights of the leaves below v v v , and suppose that Z v / B ≤ q v ≤ Z v Z_v/\mathcal{B}\le q_v\le Z_v Z v / B ≤ q v ≤ Z v at every node and q x = ω x q_x=\omega_x q x = ω x at every leaf. Put h 0 = 2 B d h_0=2\mathcal{B}d h 0 = 2 B d and Γ = 32 B 2 d 2 \Gamma=32\mathcal{B}^2d^2 Γ = 32 B 2 d 2 , and let L L L be the set of leaves. Then P t r P_{\mathrm{tr}} P tr is reversible with stationary law π ( v ) = s v / S o \pi(v)=s_v/S_o π ( v ) = s v / S o ; moreover π ( L ) ≥ 1 / h 0 \pi(L)\ge1/h_0 π ( L ) ≥ 1/ h 0 , π ( o ) ≥ 1 / ( h 0 B ) \pi(o)\ge1/(h_0\mathcal{B}) π ( o ) ≥ 1/ ( h 0 B ) , π ( x ∣ L ) = ω x / Z o \pi(x\mid L)=\omega_x/Z_o π ( x ∣ L ) = ω x / Z o at each leaf x x x , and, for 0 < η 0 < 1 0<\eta_0<1 0 < η 0 < 1 ,
∥ P t r t ( o , ⋅ ) − π ∥ T V ≤ η 0 whenever t ≥ Γ log h 0 B η 0 . (48) \lVert P_{\mathrm{tr}}^t(o,\cdot)-\pi\rVert_{\mathrm{TV}}\le\eta_0\qquad\text{whenever}\qquad t\ge\Gamma\log\frac{h_0\mathcal{B}}{\eta_0}. \tag*{(48)} ∥ P tr t ( o , ⋅ ) − π ∥ TV ≤ η 0 whenever t ≥ Γ log η 0 h 0 B . (48)
Proof. Every estimate is within the ratio r = B r=\mathcal{B} r = B of its mass, and every leaf carries its exact weight. The proofs of [SJ89, (11), Lemma 4.1 and Lemma 4.2] use only these two facts and the disjointness of the subtrees at each depth, so they hold verbatim with the number of leaves below a node replaced by its mass and with their depth m m m equal to our d d d . They give the stationary law, π ( L ) ≥ 1 / ( 2 r d ) = 1 / h 0 \pi(L)\ge1/(2rd)=1/h_0 π ( L ) ≥ 1/ ( 2 r d ) = 1/ h 0 , and conductance at least 1 / ( 4 r 2 d ) 1/(4r^2d) 1/ ( 4 r 2 d ) , half of whose square is 1 / Γ 1/\Gamma 1/Γ . The conditional leaf law follows from s x = q x = ω x s_x=q_x=\omega_x s x = q x = ω x . By [SJ89, (12)] with leaf weights, S o ≤ 2 r d Z o S_o\le2rdZ_o S o ≤ 2 r d Z o , while s o = ∑ y q y ≥ Z o / B s_o=\sum_y q_y\ge Z_o/\mathcal{B} s o = ∑ y q y ≥ Z o / B , the sum over the children y y y of the root; hence π ( o ) ≥ 1 / ( 2 r 2 d ) = 1 / ( h 0 B ) \pi(o)\ge1/(2r^2d)=1/(h_0\mathcal{B}) π ( o ) ≥ 1/ ( 2 r 2 d ) = 1/ ( h 0 B ) . Finally, the chain holds with probability 1 / 2 1/2 1/2 , and it is ergodic because every q v q_v q v is positive, so [SJ89, Theorem 3.4], applied with the set { o } \{o\} { o } in the role of their U U U , gives
P t r 2 t ( o , o ) / π ( o ) − 1 ≤ ( 1 − 1 / Γ ) 2 t / π ( o ) . P_{\mathrm{tr}}^{2t}(o,o)/\pi(o)-1\le(1-1/\Gamma)^{2t}/\pi(o). P tr 2 t ( o , o ) / π ( o ) − 1 ≤ ( 1 − 1/Γ ) 2 t / π ( o ) .
By reversibility,
∑ v ( P t r t ( o , v ) − π ( v ) ) 2 / π ( v ) = P t r 2 t ( o , o ) / π ( o ) − 1 , \sum_v(P_{\mathrm{tr}}^t(o,v)-\pi(v))^2/\pi(v)=P_{\mathrm{tr}}^{2t}(o,o)/\pi(o)-1, v ∑ ( P tr t ( o , v ) − π ( v ) ) 2 / π ( v ) = P tr 2 t ( o , o ) / π ( o ) − 1 ,
so by the Cauchy–Schwarz inequality
2 ∥ P t r t ( o , ⋅ ) − π ∥ T V ≤ ( 1 − 1 / Γ ) t π ( o ) − 1 / 2 ≤ ( h 0 B ) 1 / 2 e − t / Γ , 2\lVert P_{\mathrm{tr}}^t(o,\cdot)-\pi\rVert_{\mathrm{TV}}\le(1-1/\Gamma)^t\pi(o)^{-1/2}\le(h_0\mathcal{B})^{1/2}e^{-t/\Gamma}, 2 ∥ P tr t ( o , ⋅ ) − π ∥ TV ≤ ( 1 − 1/Γ ) t π ( o ) − 1/2 ≤ ( h 0 B ) 1/2 e − t /Γ ,
which proves (A.3).
Additive estimates and a cached table
Assume the estimator guarantee (2.3) of § 5.2 , with the same additive error bound b b b for all nodes.
Proposition A.4 (Sampling from additive estimates). Given (2.3), for every 0 < η ≤ 1 / 2 0<\eta\le1/2 0 < η ≤ 1/2 there is a sampler within total variation distance η \eta η of μ W \mu_W μ W , and one within η \eta η of the residual law W v / Z v W_v/Z_v W v / Z v of every node v v v . Every execution uses at most exp ( O ( b + 1 ) ) C 0 poly ( d , log ( 1 / η ) ) \exp(O(b+1))C_0\operatorname{poly}(d,\log(1/\eta)) exp ( O ( b + 1 )) C 0 poly ( d , log ( 1/ η )) operations and uniform draws.
Each sampler invocation, including each call in Proposition A.2, uses fresh randomness and an initially empty cache. Within an invocation, cache the first answer of the estimator for each node v v v and set
q v = W v ( 0 ) e A v , B = e b . (49) q_v=W_v(0)e^{A_v},\qquad\mathcal{B}=e^b. \tag*{(49)} q v = W v ( 0 ) e A v , B = e b . (49)
At a leaf x x x the estimate is the exact weight q x = W ( x ) q_x=W(x) q x = W ( x ) . On the success event in (2.3) these estimates satisfy (A.1), and on every execution, including a failure of the estimator, they are positive.
For the analysis, assign an independent seed of the estimator to each of the fewer than 2 d + 1 2^{d+1} 2 d + 1 nodes, with δ e s t = η / 2 d + 5 \delta_{\mathrm{est}}=\eta/2^{d+5} δ est = η / 2 d + 5 ; then with probability at least 1 − η / 16 1-\eta/16 1 − η /16 all estimates satisfy (A.1). The algorithm builds this table lazily: it generates a seed and stores the resulting estimate on the first request for a node, as in the implementation that remembers earlier answers [SJ89, Remark after Theorem 4.5, pp. 118–119]. The seed for each new node is independent of all previous randomness, even when requests are adaptive, so deferred generation has the same law as the complete table. Since log ( 1 / δ e s t ) = O ( d + log ( 1 / η ) ) \log(1/\delta_{\mathrm{est}})=O(d+\log(1/\eta)) log ( 1/ δ est ) = O ( d + log ( 1/ η )) , each request costs C 0 poly ( d , log ( 1 / η ) ) C_0\operatorname{poly}(d,\log(1/\eta)) C 0 poly ( d , log ( 1/ η )) .
Proof of Proposition A.4. Use the cached mass estimates (A.4) and the chain of Lemma A.3 with leaf weights ω x = W ( x ) \omega_x=W(x) ω x = W ( x ) , and choose integer caps
t w a l k = ⌈ Γ log 32 h 0 2 B η ⌉ , n c h = ⌈ 2 h 0 log 16 η ⌉ , n t r = n c h t w a l k . t_{\mathrm{walk}}=\left\lceil\Gamma\log\frac{32h_0^2\mathcal{B}}{\eta}\right\rceil,\qquad n_{\mathrm{ch}}=\left\lceil2h_0\log\frac{16}{\eta}\right\rceil,\qquad n_{\mathrm{tr}}=n_{\mathrm{ch}}t_{\mathrm{walk}}. t walk = ⌈ Γ log η 32 h 0 2 B ⌉ , n ch = ⌈ 2 h 0 log η 16 ⌉ , n tr = n ch t walk .
Run n c h n_{\mathrm{ch}} n ch independent chains from the root for t w a l k t_{\mathrm{walk}} t walk steps each, sharing the same cache and using fresh transition randomness. Return the configuration of the first endpoint that is a leaf, and the all-zero configuration if none is a leaf.
Condition on a table for which (A.1) holds. By Lemma A.3 the endpoint law π ′ = P t r t w a l k ( o , ⋅ ) \pi'=P_{\mathrm{tr}}^{t_{\mathrm{walk}}}(o,\cdot) π ′ = P tr t walk ( o , ⋅ ) of every chain is within η 0 = η / ( 32 h 0 ) \eta_0=\eta/(32h_0) η 0 = η / ( 32 h 0 ) of π \pi π . Each chain ends at a leaf with probability at least 1 / h 0 − η 0 ≥ 1 / ( 2 h 0 ) 1/h_0-\eta_0\ge1/(2h_0) 1/ h 0 − η 0 ≥ 1/ ( 2 h 0 ) , and
∥ π ′ ( ⋅ ∣ L ) − π ( ⋅ ∣ L ) ∥ T V ≤ 2 η 0 1 / h 0 − η 0 < η / 8. \left\|\pi'(\cdot\mid\mathcal{L})-\pi(\cdot\mid\mathcal{L})\right\|_{\mathrm{TV}}\le\frac{2\eta_0}{1/h_0-\eta_0}<\eta/8. ∥ π ′ ( ⋅ ∣ L ) − π ( ⋅ ∣ L ) ∥ TV ≤ 1/ h 0 − η 0 2 η 0 < η /8.
The first leaf endpoint has the conditional law π ′ ( ⋅ ∣ L ) \pi'(\cdot\mid\mathcal{L}) π ′ ( ⋅ ∣ L ) . The probability of no leaf endpoint is at most e − n c h / ( 2 h 0 ) ≤ η / 16 e^{-n_{\mathrm{ch}}/(2h_0)}\le\eta/16 e − n ch / ( 2 h 0 ) ≤ η /16 , and a bad table adds at most η / 16 \eta/16 η /16 , so the total variation error is smaller than η \eta η . Each transition is implemented exactly: one uniform draw selects the hold event and, if needed, an edge by cumulative comparison of the positive edge weights. For the residual law of a node v v v of depth less than d d d , run the same construction on the subtree below v v v . Lemma A.3 applies to it with leaves at depth d − depth ( v ) d-\operatorname{depth}(v) d − depth ( v ) . Its constants h 0 h_0 h 0 and Γ \Gamma Γ are no larger than those of the whole tree, so the same caps suffice. At a leaf the residual law is a point mass, returned exactly.
There are n t r = exp ( O ( b + 1 ) ) poly ( d , log ( 1 / η ) ) n_{\mathrm{tr}}=\exp(O(b+1))\operatorname{poly}(d,\log(1/\eta)) n tr = exp ( O ( b + 1 )) poly ( d , log ( 1/ η )) transitions and at most 3 n t r + 1 3n_{\mathrm{tr}}+1 3 n tr + 1 new requests, each costing C 0 poly ( d , log ( 1 / η ) ) C_0\operatorname{poly}(d,\log(1/\eta)) C 0 poly ( d , log ( 1/ η )) . Mass estimates are stored in a binary trie keyed by the prefixes, and the current path is kept on a stack, so lookups and updates take poly ( d ) \operatorname{poly}(d) poly ( d ) operations. The integer caps are found by doubling and binary search in O ( log ( n t r + 2 ) ) O(\log(n_{\mathrm{tr}}+2)) O ( log ( n tr + 2 )) operations. These bounds hold on every execution, regardless of failures of the estimator.
Together, Propositions A.2 and A.4 prove Proposition 2.1.
Finite-precision arithmetic and bounded random choices
Two standard lemmas replace exact uniform draws.
Lemma A.5 (Accumulated simulation error). Consider a randomized procedure with at most t t t sequential steps. If, conditional on every common past, the ideal and the implemented step j j j have output laws at total variation distance at most η j \eta_j η j , then the final outputs are at total variation distance at most ∑ j ≤ t η j \sum_{j\le t}\eta_j ∑ j ≤ t η j .
Proof. Couple each pair of steps maximally while the histories agree. By a union bound, the histories disagree with probability at most ∑ j ≤ t η j \sum_{j\le t}\eta_j ∑ j ≤ t η j , and otherwise the outputs coincide.
Lemma A.6 (Finite choices from fair bits). Let ω 1 , … , ω n ω \omega_1,\ldots,\omega_{n_\omega} ω 1 , … , ω n ω be positive rationals whose numerators and denominators have at most ℓ ω \ell_\omega ℓ ω bits, and let ℓ ≥ 1 \ell\ge1 ℓ ≥ 1 . Using ℓ \ell ℓ fair bits and poly ( n ω , ℓ ω , ℓ ) \operatorname{poly}(n_\omega,\ell_\omega,\ell) poly ( n ω , ℓ ω , ℓ ) bit operations one can draw an index whose law is within total variation distance ( n ω − 1 ) 2 − ℓ (n_\omega-1)2^{-\ell} ( n ω − 1 ) 2 − ℓ of ( ω j / ∑ i ω i ) j (\omega_j/\sum_i\omega_i)_j ( ω j / ∑ i ω i ) j .
Proof. Read the bits as a grid point y ∈ { 0 , 2 − ℓ , … , 1 − 2 − ℓ } y \in\{0,2^{-\ell},\ldots,1-2^{-\ell}\} y ∈ { 0 , 2 − ℓ , … , 1 − 2 − ℓ } and return the least j j j with y < ∑ i ≤ j w i / ∑ i w i y < \sum_{i\le j} w_i/\sum_i w_i y < ∑ i ≤ j w i / ∑ i w i , by exact integer cross multiplication. For U U U uniform on [ y , y + 2 − ℓ ) [y,y+2^{-\ell}) [ y , y + 2 − ℓ ) , this agrees with the inverse transform of U U U unless the cell contains one of the n w − 1 n_w-1 n w − 1 interior cumulative boundaries.
Without truncation, fair bits generate such choices exactly with a random number of bits [59 ] ; the truncation makes the cost bounded on every execution.
Finite-precision optimization and simulation
The estimator. At a node whose residual has k ≥ 1 k \ge1 k ≥ 1 free coordinates, run the generic estimator of Theorem 4.1 with γ = 1 / 128 \gamma=1/128 γ = 1/128 in place of 1 / 64 1/64 1/64 . Choose a known bound b ∗ b_\ast b ∗ on the objective gap, and choose a degree D D D after the rounded parameter κ \kappa κ of item (b) below has been computed. For threshold smoothing use b ∗ = d w 2 / 4 b_\ast=d w^2/4 b ∗ = d w 2 /4 and D = min { d , ⌈ 4 κ / w ⌉ } D=\min\{d,\lceil4\kappa/w\rceil\} D = min { d , ⌈ 4 κ / w ⌉} ; for ordinary resampling use the rational bound b ∗ = d τ b_\ast=d\tau b ∗ = d τ and D = min { d , ⌈ κ / τ ⌉ } D=\min\{d,\lceil\kappa/\tau\rceil\} D = min { d , ⌈ κ / τ ⌉} . These choices satisfy the required tail bound with the rounded G 0 G_0 G 0 of item (b); if D = d D=d D = d , the tail vanishes. Make the following further changes.
(a) Each bin Y i Y_i Y i is read from 2 s 2s 2 s fair bits, since m = 4 s m=4^s m = 4 s .
(b) Each bin score a ˉ j \bar a_j a ˉ j is replaced by a dyadic rational a ~ j \tilde a_j a ~ j with 0 ≤ a ˉ j − a ~ j ≤ 1 / ( 64 d ) 0\le\bar a_j-\tilde a_j\le1/(64d) 0 ≤ a ˉ j − a ~ j ≤ 1/ ( 64 d ) , computed from certified values of H ( j / m ) H(j/m) H ( j / m ) . In the definitions of G 0 G_0 G 0 and κ \kappa κ in (4.1), A 0 A_0 A 0 is replaced by the integer 2 s + 2 ≥ A 0 + 1 2s+2\ge A_0+1 2 s + 2 ≥ A 0 + 1 , so that G 0 = 2 s + 2 + 4 B G_0=2s+2+4B G 0 = 2 s + 2 + 4 B ; in (4.10), log ( 8 n a t t / δ ) \log(8n_{\mathrm{att}}/\delta) log ( 8 n att / δ ) is replaced by the larger integer ⌈ log 2 ( 8 n a t t / δ ) ⌉ \lceil\log_2(8n_{\mathrm{att}}/\delta)\rceil ⌈ log 2 ( 8 n att / δ )⌉ . All parameters are then integers or rationals computed exactly.
(c) The residual weight W v ( x ′ ) / W v ( 0 ) W_v(x')/W_v(0) W v ( x ′ ) / W v ( 0 ) is formed exactly, a rational whose numerator and denominator have at most 2 B 2B 2 B bits. Each value Φ ( S t ) \Phi(S_t) Φ ( S t ) , t ≥ 1 t\ge1 t ≥ 1 , entering the potential term is computed to absolute error ξ = γ / ( 64 P ) \xi=\gamma/(64P) ξ = γ / ( 64 P ) on a common dyadic grid, and Φ ( ∅ ) = 0 \Phi(\varnothing)=0 Φ ( ∅ ) = 0 is exact.
(d) Let α \alpha α be the power of two with γ / ( 2 M G 1 2 ) < α ≤ γ / ( M G 1 2 ) \gamma/(2MG_1^2)<\alpha\le\gamma/(MG_1^2) γ / ( 2 M G 1 2 ) < α ≤ γ / ( M G 1 2 ) , take n i t = ⌈ 2 P M G 1 2 / γ 2 ⌉ n_{\mathrm{it}}=\lceil2PMG_1^2/\gamma^2\rceil n it = ⌈ 2 P M G 1 2 / γ 2 ⌉ steps, and return max ρ ( J ^ ( ρ ) − γ − 3 P ξ ) \max_\rho(\widehat J(\rho)-\gamma-3P\xi) max ρ ( J ( ρ ) − γ − 3 P ξ ) , clamped as before, where J ^ ( ρ ) \widehat J(\rho) J ( ρ ) averages the computed sample values.
Soundness is unchanged: for the clipped guide F = clip ( u ) F=\operatorname{clip}(u) F = clip ( u ) of the proof of Lemma 4.3, ψ a ~ j ( u i ) ≤ a ~ j F i ≤ a ˉ j F i \psi_{\tilde a_j}(u_i)\le\tilde a_jF_i\le\bar a_jF_i ψ a ~ j ( u i ) ≤ a ~ j F i ≤ a ˉ j F i because F i ≥ 0 F_i\ge0 F i ≥ 0 , so the objective with scores a ~ j \tilde a_j a ~ j is at most log Z Φ \log Z_\Phi log Z Φ for every candidate. In the proof of Lemma 4.4 , the rounded scores lower the objective at g ˉ \bar g g ˉ , which takes values in [ 0 , 1 ] k [0,1]^k [ 0 , 1 ] k , by at most k / ( 64 d ) ≤ 1 / 64 k/(64d)\le1/64 k / ( 64 d ) ≤ 1/64 . The truncation step is unchanged, because κ \kappa κ is defined from the new G 0 G_0 G 0 , which bounds ∣ a ~ j ∣ + 2 Λ |\tilde a_j|+2\Lambda ∣ a ~ j ∣ + 2Λ . The losses are 1 / 64 1/64 1/64 from score rounding, 1 / 64 1/64 1/64 from the bins, and 1 / 128 1/128 1/128 from truncation, totaling 5 / 128 5/128 5/128 . Thus J ( θ ) ≥ log Z Φ − b ∗ − 5 / 128 J(\theta)\ge\log Z_\Phi-b_\ast-5/128 J ( θ ) ≥ log Z Φ − b ∗ − 5/128 .
In the analysis below, J ( θ ) J(\theta) J ( θ ) denotes the objective with the dyadic scores a ~ j \tilde a_j a ~ j and the exact potential Φ \Phi Φ . Write the potential term as Φ L ( z ) = ∑ t = 1 k Φ ( S t ) ( z j t − z j t + 1 ) \Phi^L(z)=\sum_{t=1}^k\Phi(S_t)(z_{j_t}-z_{j_{t+1}}) Φ L ( z ) = ∑ t = 1 k Φ ( S t ) ( z j t − z j t + 1 ) , where z j 1 ≥ ⋯ ≥ z j k z_{j_1}\ge\cdots\ge z_{j_k} z j 1 ≥ ⋯ ≥ z j k and z j k + 1 = 0 z_{j_{k+1}}=0 z j k + 1 = 0 . The first k − 1 k-1 k − 1 differences are nonnegative, and
∑ t = 1 k − 1 ∣ z j t − z j t + 1 ∣ + ∣ z j k ∣ = z j 1 − z j k + ∣ z j k ∣ ≤ 3 max i ∣ z i ∣ . \sum_{t=1}^{k-1}|z_{j_t}-z_{j_{t+1}}|+|z_{j_k}|=z_{j_1}-z_{j_k}+|z_{j_k}|\le3\max_i|z_i|. t = 1 ∑ k − 1 ∣ z j t − z j t + 1 ∣ + ∣ z j k ∣ = z j 1 − z j k + ∣ z j k ∣ ≤ 3 i max ∣ z i ∣.
Thus errors of at most ξ \xi ξ in the values Φ ( S t ) \Phi(S_t) Φ ( S t ) change the computed sample objective at z ~ = u θ ( Y ) \tilde z=u^\theta(Y) z ~ = u θ ( Y ) by at most 3 ξ max i ∣ z i ∣ ≤ 3 P ξ 3\xi\max_i|z_i|\le3P\xi 3 ξ max i ∣ z i ∣ ≤ 3 P ξ , and each chain increment by at most 2 ξ 2\xi 2 ξ .
Rounded values need not define a supermodular potential. For a fixed sorted chain, let ζ Y ( θ ) \zeta_Y(\theta) ζ Y ( θ ) be the supergradient obtained from the exact potential increments and let ζ ~ Y ( θ ) \tilde\zeta_Y(\theta) ζ ~ Y ( θ ) be the computed vector. A computed row slope has magnitude at most
∣ a ~ j ∣ + 2 Λ + 2 ξ ≤ G 0 , |\tilde a_j|+2\Lambda+2\xi\le G_0, ∣ a ~ j ∣ + 2Λ + 2 ξ ≤ G 0 ,
so the bounds (30) remain valid, and
∥ ζ ~ Y ( θ ) − ζ Y ( θ ) ∥ 2 ≤ 2 ξ P . \left\lVert\widetilde{\zeta}_Y(\theta)-\zeta_Y(\theta)\right\rVert_2 \le2\xi\sqrt{P}. ζ Y ( θ ) − ζ Y ( θ ) 2 ≤ 2 ξ P .
Since ∥ θ − θ ∗ ∥ 2 ≤ 2 P \lVert\theta-\theta^*\rVert_2 \le2\sqrt{P} ∥ θ − θ ∗ ∥ 2 ≤ 2 P , the additional term in the distance recursion contributes at most 4 P ξ = γ / 16 4P\xi=\gamma/16 4 P ξ = γ /16 to (32) . Consequently
E [ J ( θ ∗ ) − J ( θ ˉ ) ] ≤ 17 γ 16 , \mathbb{E}[J(\theta^*)-J(\bar{\theta})]\le\frac{17\gamma}{16}, E [ J ( θ ∗ ) − J ( θ ˉ )] ≤ 16 17 γ ,
and Markov’s inequality gives J ( θ ˉ ) ≥ J ( θ ∗ ) − 17 γ / 4 J(\bar{\theta})\ge J(\theta^*)-17\gamma/4 J ( θ ˉ ) ≥ J ( θ ∗ ) − 17 γ /4 with probability at least 3 / 4 3/4 3/4 .
Validate as in (33) . Let J ^ t r u e ( ρ ) \widehat{J}^{(\rho)}_{\mathrm{true}} J true ( ρ ) be the validation average using the exact potential values in attempt ρ \rho ρ . The computed average satisfies
∣ J ^ ( ρ ) − J ^ t r u e ( ρ ) ∣ ≤ 3 P ξ . \left|\widehat{J}^{(\rho)}-\widehat{J}^{(\rho)}_{\mathrm{true}}\right|\le3P\xi. J ( ρ ) − J true ( ρ ) ≤ 3 P ξ .
With probability at least 1 − δ / 4 1-\delta/4 1 − δ /4 , every J ^ t r u e ( ρ ) \widehat{J}^{(\rho)}_{\mathrm{true}} J true ( ρ ) differs from J ( θ ˉ ( ρ ) ) J(\bar{\theta}^{(\rho)}) J ( θ ˉ ( ρ ) ) by at most γ \gamma γ . On this event every corrected value J ^ ( ρ ) − γ − 3 P ξ \widehat{J}^{(\rho)}-\gamma-3P\xi J ( ρ ) − γ − 3 P ξ is at most J ( θ ˉ ( ρ ) ) ≤ log Z Φ J(\bar{\theta}^{(\rho)})\le\log Z_{\Phi} J ( θ ˉ ( ρ ) ) ≤ log Z Φ .
With probability at least 1 − 4 − n a t t ≥ 1 − δ / 4 1-4^{-n_{\mathrm{att}}}\ge1-\delta/4 1 − 4 − n att ≥ 1 − δ /4 , some ascent attempt satisfies J ( θ ˉ ( ρ ) ) ≥ J ( θ ∗ ) − 17 γ / 4 J(\bar{\theta}^{(\rho)})\ge J(\theta^*)-17\gamma/4 J ( θ ˉ ( ρ ) ) ≥ J ( θ ∗ ) − 17 γ /4 . On the intersection of the two events, the largest corrected validation value is at least
log Z Φ − b ∗ − 5 128 − ( 17 4 + 2 ) γ − 6 P ξ ≥ log Z Φ − b ∗ − 1 8 . \log Z_{\Phi}-b_*-\frac{5}{128}-\left(\frac{17}{4}+2\right)\gamma-6P\xi
\ge\log Z_{\Phi}-b_*-\frac{1}{8}. log Z Φ − b ∗ − 128 5 − ( 4 17 + 2 ) γ − 6 P ξ ≥ log Z Φ − b ∗ − 8 1 .
The logarithms need O ( log P ) O(\log P) O ( log P ) bits of precision beyond the input length, the iterates stay on a common dyadic grid in [ − 1 , 1 ] [-1,1] [ − 1 , 1 ] , and the cost is (26) , now in bit operations and fair bits.
Additive estimation. To implement Corollary 2.3, let ϵ 0 \epsilon_0 ϵ 0 be the rounded dyadic accuracy, with ϵ / 2 < ϵ 0 ≤ ϵ \epsilon/2<\epsilon_0\le\epsilon ϵ /2 < ϵ 0 ≤ ϵ , and choose the largest power of two w w w with w 2 ≤ ϵ 0 w^2\le\epsilon_0 w 2 ≤ ϵ 0 . Integer comparisons find it, and ϵ 0 / 2 < w ≤ ϵ 0 ≤ 1 / 4 \sqrt{\epsilon_0}/2<w\le\sqrt{\epsilon_0}\le1/4 ϵ 0 /2 < w ≤ ϵ 0 ≤ 1/4 . Run the preceding estimator at the root with b ∗ = d w 2 / 4 b_* = dw^2/4 b ∗ = d w 2 /4 and the rounded failure probability, and compute a rational L 0 L_0 L 0 satisfying 0 ≤ log W ( 0 ) − L 0 ≤ ϵ 0 / 4 0\le\log W(0)-L_0\le\epsilon_0/4 0 ≤ log W ( 0 ) − L 0 ≤ ϵ 0 /4 by certified logarithm evaluation. Return the sum A A A of L 0 L_0 L 0 and the estimate at the root. With probability at least 1 − δ 1-\delta 1 − δ ,
0 ≤ log Z W − A ≤ d w 2 4 + 1 8 + ϵ 0 4 ≤ ϵ 0 d 2 + 1 8 ≤ ϵ d + 1 8 . 0\le\log Z_W-A\le\frac{dw^2}{4}+\frac{1}{8}+\frac{\epsilon_0}{4}\le\frac{\epsilon_0d}{2}+\frac{1}{8}\le\epsilon d+\frac{1}{8}. 0 ≤ log Z W − A ≤ 4 d w 2 + 8 1 + 4 ϵ 0 ≤ 2 ϵ 0 d + 8 1 ≤ ϵ d + 8 1 .
Since w − 1 = O ( ϵ − 1 / 2 ) w^{-1}=O(\epsilon^{-1/2}) w − 1 = O ( ϵ − 1/2 ) , the exponential factor is unchanged; the additional logarithm uses poly ( B , ℓ p a r ) \operatorname{poly}(B,\ell_{\mathrm{par}}) poly ( B , ℓ par ) bit operations.
The walk. Let A max = d ( 1 + 2 B ) A_{\max}=d(1+2B) A m a x = d ( 1 + 2 B ) , so that 0 ≤ A v ≤ A max 0\le A_v\le A_{\max} 0 ≤ A v ≤ A m a x , compute a rational log 2 ~ \widetilde{\log2} log 2 with log 2 ≤ log 2 ~ ≤ log 2 + 1 / ( 2 ( A max + 1 ) ) \log2\le\widetilde{\log2}\le\log2+1/(2(A_{\max}+1)) log 2 ≤ log 2 ≤ log 2 + 1/ ( 2 ( A m a x + 1 )) , and use the mass estimates
q v = W v ( 0 ) 2 ⌈ A v / log 2 ~ ⌉ , q_v=W_v(0)\,2^{\left\lceil A_v/\widetilde{\log2}\right\rceil}, q v = W v ( 0 ) 2 ⌈ A v / l o g 2 ⌉ ,
and q x = W ( x ) q_x=W(x) q x = W ( x ) at leaves. Then 0 ≤ A v − ⌈ A v / log 2 ~ ⌉ log 2 < A v ( log 2 ~ − log 2 ) / log 2 ~ + log 2 < 2 0\le A_v-\lceil A_v/\widetilde{\log2}\rceil\log2<A_v(\widetilde{\log2}-\log2)/\widetilde{\log2}+\log2<2 0 ≤ A v − ⌈ A v / log 2 ⌉ log 2 < A v ( log 2 − log 2 ) / log 2 + log 2 < 2 , so on the success event e − b − 2 Z v ≤ q v ≤ Z v e^{-b-2}Z_v\le q_v\le Z_v e − b − 2 Z v ≤ q v ≤ Z v , and on every execution the estimates are positive rationals of polynomial length. Lemma A.3 applies with the power of two B = 2 ⌈ 2 ( b + 2 ) ⌉ B=2^{\lceil2(b+2)\rceil} B = 2 ⌈ 2 ( b + 2 )⌉ . With η = 2 − ℓ η \eta=2^{-\ell_\eta} η = 2 − ℓ η , take the integer caps t w a l k = Γ ℓ η + ⌈ log 2 ( 32 h 0 2 B ) ⌉ t_{\mathrm{walk}}=\Gamma^{\ell_\eta+\lceil\log_2(32h_0^2B)\rceil} t walk = Γ ℓ η + ⌈ l o g 2 ( 32 h 0 2 B )⌉ , n c h = 2 h 0 ( ℓ η + 4 ) n_{\mathrm{ch}}=2h_0(\ell_\eta+4) n ch = 2 h 0 ( ℓ η + 4 ) and n t r = n c h t w a l k n_{\mathrm{tr}}=n_{\mathrm{ch}}t_{\mathrm{walk}} n tr = n ch t walk , and the estimator failure probability δ e s t = 2 − ℓ η − d − 5 \delta_{\mathrm{est}}=2^{-\ell_\eta-d-5} δ est = 2 − ℓ η − d − 5 . Each transition draws the hold event with one fair bit and an edge among at most three by Lemma A.6 with ℓ = ℓ η + ⌈ log 2 n t r ⌉ + 4 \ell=\ell_\eta+\lceil\log_2 n_{\mathrm{tr}}\rceil+4 ℓ = ℓ η + ⌈ log 2 n tr ⌉ + 4 bits. Each step then has error at most 2 1 − ℓ ≤ η / ( 8 n t r ) 2^{1-\ell}\le\eta/(8n_{\mathrm{tr}}) 2 1 − ℓ ≤ η / ( 8 n tr ) , so by Lemma A.5 the bit model adds at most η / 8 \eta/8 η /8 to the error budget in the proof of Proposition A.4, and the total stays below η \eta η .
Counting. Proposition A.2 calls this sampler at accuracy ϵ / ( 128 d ) \epsilon/(128d) ϵ / ( 128 d ) , rounded down to a power of two, and computes n c n_c n c with integer logarithms. The frequencies are rationals with denominator n c n_c n c and are at least 1 / 2 1/2 1/2 , so W ( x ) / ∏ i μ i W(x)/\prod_i \mu_i W ( x ) / ∏ i μ i is a rational of polynomial length on every execution.
Proof of Theorem A.1. The additive-estimation construction above proves Corollary 2.3 in the bit model. For Theorem 1.2 , the balance is unchanged, with ℓ d \ell_d ℓ d and ℓ B \ell_B ℓ B as in its proof: w w w is a power of two found by integer comparisons, and the degree D = min { d , ⌈ 4 κ / w ⌉ } D=\min\{d,\lceil4\kappa/w\rceil\} D = min { d , ⌈ 4 κ / w ⌉} makes each estimator call cost
exp ( O ( w − 1 ℓ d ℓ B ) ) poly ( d , B , T W , log ( 1 / δ e s t ) ) \exp\left(O\left(w^{-1}\ell_d\ell_B\right)\right)\operatorname{poly}\left(d,B,T_W,\log(1/\delta_{\mathrm{est}})\right) exp ( O ( w − 1 ℓ d ℓ B ) ) poly ( d , B , T W , log ( 1/ δ est ) )
bit operations and fair bits. The ordinary-resampling choice likewise gives the square-root bound of Corollary 5.2 in the bit model: take the power of two τ \tau τ of that proof, give the walk the rational additive error bound b = d τ + 1 / 8 ≥ d τ log 2 + 1 / 8 b=d\tau+1/8\ge d\tau\log2+1/8 b = d τ + 1/8 ≥ d τ log 2 + 1/8 , and use the corresponding degree D D D . In the enumeration case the 2 d 2^d 2 d weights are summed exactly, with exp ( O ( d ) ) poly ( B ) \exp(O(d))\operatorname{poly}(B) exp ( O ( d )) poly ( B ) bits, and a configuration is drawn by Lemma A.6 with n ω = 2 d n_\omega=2^d n ω = 2 d and ℓ = d + ℓ η + 1 \ell=d+\ell_\eta+1 ℓ = d + ℓ η + 1 , within η / 2 \eta/2 η /2 . For Theorem 1.1 , the weights (2) are integers with at most n + 1 n+1 n + 1 bits, and the completion by a uniform subset of R ∖ N ( S ) R\setminus N(S) R ∖ N ( S ) uses at most n n n fair bits.