Introduction
The Maximum Cut problem (Max-Cut) is a fundamental optimization problem that asks for a bipartition of a graph’s vertices that maximizes the total weight of edges crossing between the two parts. Formally, given an undirected graph G G G V V V A u v A_{uv} A uv
OPT = MaxCut ( G ) : = max S ⊆ V ∑ u ∈ S , v ∉ S A u v . \operatorname{OPT}=\operatorname{MaxCut}(G):=\max_{S\subseteq V}\sum_{u\in S,v\notin S} A_{uv}. OPT = MaxCut ( G ) := S ⊆ V max u ∈ S , v ∈ / S ∑ A uv . By convention, A u v = 0 A_{uv}=0 A uv = 0 ( u , v ) (u,v) ( u , v )
The problem is NP-hard and APX-hard even on unweighted graphs [14 , 24 ] , so a polynomial-time approximation scheme would imply P = NP. For general graphs, a common goal is therefore to design an α \alpha α 0 < α ≤ 1 0<\alpha\leq1 0 < α ≤ 1 α OPT \alpha\operatorname{OPT} α OPT [12 ] achieves approximation ratio ≈ 0.87856 \approx0.87856 ≈ 0.87856 [13 ] proved that achieving a ratio of 16 / 17 + γ 16/17+\gamma 16/17 + γ 0 < γ < 1 / 17 0<\gamma<1/17 0 < γ < 1/17 [15 ] .
Dense and metric instances, however, admit ( 1 − ε ) (1-\varepsilon) ( 1 − ε ) 0 < ε < 1 0 < \varepsilon< 1 0 < ε < 1 A u v ∈ [ 0 , 1 ] A_{uv} \in[0,1] A uv ∈ [ 0 , 1 ] O P T − ε n 2 \mathrm{OPT} - \varepsilon n^2 OPT − ε n 2 n : = ∣ V ∣ n := |V| n := ∣ V ∣ W : = 1 2 ∑ u , v ∈ V A u v W := \frac{1}{2}\sum_{u,v\in V} A_{uv} W := 2 1 ∑ u , v ∈ V A uv W ≥ ρ n 2 W \ge\rho n^2 W ≥ ρ n 2 ρ > 0 \rho> 0 ρ > 0 O P T ≥ W / 2 ≥ ρ n 2 / 2 \mathrm{OPT} \ge W/2 \ge\rho n^2/2 OPT ≥ W /2 ≥ ρ n 2 /2 ε ρ n 2 / 2 \varepsilon\rho n^2/2 ερ n 2 /2 ( 1 − ε ) O P T (1-\varepsilon)\mathrm{OPT} ( 1 − ε ) OPT ( 1 − ε ) (1-\varepsilon) ( 1 − ε ) [6 ] and independently by Arora, Karger, and Karpinski [3 ] . The same additive viewpoint applies also to metric Max-Cut, where the weights satisfy the triangle inequality. Fernandez de la Vega and Kenyon [8 ] reduce these instances to dense weighted graphs, such that accurate additive approximation on the resulting dense graph gives a ( 1 − ε ) (1-\varepsilon) ( 1 − ε )
We focus on fast additive approximation of the Max-Cut value without reporting a cut. That is, for bounded weights A u v ∈ [ 0 , 1 ] A_{uv} \in[0,1] A uv ∈ [ 0 , 1 ] O P T ^ \widehat{\mathrm{OPT}} OPT
∣ O P T ^ − O P T ∣ ≤ ε n 2 , \left|\widehat{\mathrm{OPT}}-\mathrm{OPT}\right| \le\varepsilon n^2, OPT − OPT ≤ ε n 2 , where throughout, randomized guarantees hold with probability at least 2 / 3 2/3 2/3
Sublinear algorithms for Max-Cut
To obtain the desired additive approximation, it suffices to sample vertices uniformly and examine their induced subgraph. The number of sampled vertices depends only on ε \varepsilon ε [2 , 25 ] . The estimator simply computes Max-Cut on this graph after rescaling all edge weights by a suitable factor. Such a small reweighted graph is a value coreset because its Max-Cut value approximates that of the original graph. With access to each edge weight in constant time and a fixed target success probability, constructing the value coreset takes time poly ( 1 / ε ) \operatorname{poly}(1/\varepsilon) poly ( 1/ ε ) n n n
While this sampling algorithm is straightforward, analyzing it is nontrivial because the sampled graph’s optimal cut is determined after the sample is realized and need not correspond to any original cut fixed in advance. Several different approaches have led to an O ~ ( ε − 4 ) \widetilde{O}(\varepsilon^{-4}) O ( ε − 4 ) 3 [2 ] use matrix decompositions and linear programming. Rudelson and Vershynin [25 ] use tools from geometric functional analysis, whereas Mathieu and Schudy [22 ] use a greedy construction for unweighted graphs. These last two analyses remove the logarithmic factors, but retain the ε − 4 \varepsilon^{-4} ε − 4
This may be viewed as an indication that a smaller sample bound is not likely. For metric Max-Cut, importance sampling proportionally to the weighted degrees gives a ( 1 ± ε ) (1\pm\varepsilon) ( 1 ± ε ) O ( ε − 4 ) O(\varepsilon^{-4}) O ( ε − 4 ) [5 ] .
Currently there is a gap between this O ( ε − 4 ) O(\varepsilon^{-4}) O ( ε − 4 ) Ω ( ε − 2 ) \Omega(\varepsilon^{-2}) Ω ( ε − 2 ) [2 technical report version] .
These results raise a few questions about the size of value coresets: For graphs with weights in [ 0 , 1 ] [0,1] [ 0 , 1 ] ε n 2 \varepsilon n^2 ε n 2 O ( ε − 4 ) O(\varepsilon^{-4}) O ( ε − 4 )
Our results
Our main contribution is to close the sampling gap, by showing that sampling O ( ε − 2 ) O(\varepsilon^{-2}) O ( ε − 2 ) [ 0 , 1 ] [0,1] [ 0 , 1 ] O ( ε − 4 ) O(\varepsilon^{-4}) O ( ε − 4 ) [25 ] and matches the known lower bound [2 ] .
Theorem 1.1 (Uniform sampling for Max-Cut, follows from Theorem 2.1 ). Consider an n n n A u v ∈ [ 0 , 1 ] A_{uv} \in[0,1] A uv ∈ [ 0 , 1 ] k k k X 1 , … , X k X_1,\ldots,X_k X 1 , … , X k 4 [ k ] [k] [ k ] A ^ i j = ( n / k ) 2 A X i X j \widehat{A}_{ij} = (n/k)^2 A_{X_iX_j} A ij = ( n / k ) 2 A X i X j
E ∣ O P T ^ − O P T ∣ = O ( n 2 k ) , \mathbb{E}\lvert\widehat{\mathrm{OPT}}-\mathrm{OPT}\rvert= O\left(\frac{n^2}{\sqrt{k}}\right), E ∣ OPT − OPT ∣ = O ( k n 2 ) , where O P T : = MaxCut ( A ) \mathrm{OPT} := \operatorname{MaxCut}(A) OPT := MaxCut ( A ) O P T ^ : = MaxCut ( A ^ ) \widehat{\mathrm{OPT}} := \operatorname{MaxCut}(\widehat{A}) OPT := MaxCut ( A )
Our analysis applies more generally to independent draws from any sampling distribution p ∈ R V p \in\mathbb{R}^{V} p ∈ R V p v ≥ d ( v ) / n 2 p_v \ge d(v)/n^2 p v ≥ d ( v ) / n 2 d ( v ) d(v) d ( v ) v v v
A ^ i j = A X i X j k 2 p X i p X j . \widehat{A}_{ij} = \frac{A_{X_iX_j}}{k^2p_{X_i}p_{X_j}}. A ij = k 2 p X i p X j A X i X j . Theorem 1.2 (General sampling distributions, follows from Corollary 2.2). Consider an n n n A u v ∈ [ 0 , 1 ] A_{uv} \in[0,1] A uv ∈ [ 0 , 1 ] p ∈ R V p \in\mathbb{R}^{V} p ∈ R V p v ≥ d ( v ) / n 2 p_v \ge d(v)/n^2 p v ≥ d ( v ) / n 2 v v v d ( v ) : = ∑ u A v u d(v) := \sum_u A_{vu} d ( v ) := ∑ u A v u ε , δ ∈ ( 0 , 1 ) \varepsilon,\delta\in(0,1) ε , δ ∈ ( 0 , 1 ) C > 0 C > 0 C > 0 k ≥ C ε − 2 δ − 2 k \ge C\varepsilon^{-2}\delta^{-2} k ≥ C ε − 2 δ − 2
P ( ∣ O P T ^ − O P T ∣ ≤ ε n 2 ) ≥ 1 − δ . \mathbb{P}\left(\left\lvert\widehat{\mathrm{OPT}}-\mathrm{OPT}\right\rvert\le\varepsilon n^2\right) \ge1-\delta. P ( OPT − OPT ≤ ε n 2 ) ≥ 1 − δ . We also prove a matching lower bound of Ω ( ε − 2 ) \Omega(\varepsilon^{-2}) Ω ( ε − 2 ) § 5 ). Together with the known lower bound for uniform sampling [2 ] , this establishes that the optimal sample complexity is Θ ( ε − 2 ) \Theta(\varepsilon^{-2}) Θ ( ε − 2 )
Extensions. We actually prove a more general form of Theorem 1.2 (see Theorem 2.1 ), and it has two additional consequences.
The first one is that in graphs with edge weights in [ 0 , 1 ] [0,1] [ 0 , 1 ] d ˉ \bar{d} d ˉ O ( ε − 2 n / d ˉ ) O(\varepsilon^{-2}n/\bar{d}) O ( ε − 2 n / d ˉ ) ( 1 ± ε ) (1\pm\varepsilon) ( 1 ± ε ) O ~ ( ε − 4 n / d ˉ ) \widetilde{O}(\varepsilon^{-4}n/\bar{d}) O ( ε − 4 n / d ˉ ) [4 ] , by matching their n / d ˉ n/\bar{d} n / d ˉ ε − 4 \varepsilon^{-4} ε − 4 ε − 2 \varepsilon^{-2} ε − 2 log n \log n log n 1 − 1 / n 2 1-1/n^2 1 − 1/ n 2
The second consequence is that in metric Max-Cut instances, importance sampling of O ( ε − 2 ) O(\varepsilon^{-2}) O ( ε − 2 ) ( 1 ± ε ) (1\pm\varepsilon) ( 1 ± ε ) [8 , 5 ] .
The value coreset also supports cut recovery , i.e., finding a nearly-optimal cut of the original graph G G G § 4 ). For weights in [ 0 , 1 ] [0,1] [ 0 , 1 ] G G G G G G O P T − ε n 2 \mathrm{OPT}-\varepsilon n^2 OPT − ε n 2
The LP has n + k n+k n + k 2 k 2k 2 k k = O ( ε − 2 ) k=O(\varepsilon^{-2}) k = O ( ε − 2 ) O ( n ε − 2 ) O(n\varepsilon^{-2}) O ( n ε − 2 )
Earlier work on cut recovery for unweighted graphs by Goldreich, Goldwasser, and Ron [11 ] constructs a cut achieving additive ε n 2 \varepsilon n^2 ε n 2 O ( ε − 7 log 2 ( 2 / ε ) + n ε − 2 log ( 2 / ε ) ) O(\varepsilon^{-7}\log^2(2/\varepsilon)+n\varepsilon^{-2}\log(2/\varepsilon)) O ( ε − 7 log 2 ( 2/ ε ) + n ε − 2 log ( 2/ ε )) [28 ] later obtained a cut achieving an additive ε n 2 \varepsilon n^2 ε n 2 O ( n ε − 2 ) + 2 O ( ε − 2 ) O(n\varepsilon^{-2})+2^{O(\varepsilon^{-2})} O ( n ε − 2 ) + 2 O ( ε − 2 ) ( 1 − ε ) (1-\varepsilon) ( 1 − ε ) [3 , 9 , 29 ] .
Finally, our result extends to Max-r r r r r r Theorem 5.1 ). For graphs with edge weights in [ 0 , 1 ] [0,1] [ 0 , 1 ] r ≥ 2 r\ge2 r ≥ 2 ε n 2 \varepsilon n^2 ε n 2 O ( ε − 2 log ( 2 r ) ) O(\varepsilon^{-2}\log(2r)) O ( ε − 2 log ( 2 r )) O ~ ( r 8 ε − 4 ) \widetilde{O}(r^8\varepsilon^{-4}) O ( r 8 ε − 4 ) [16 ] , we improve the dependence on both r r r ε \varepsilon ε
Our techniques
Each technical section includes an overview of its proof, and here we only briefly summarize the main ideas. Our proof for Max-Cut in § 2 expresses the (normalized) weight of cuts in the graph as a quadratic form in a vector p ∈ R V p\in\mathbb{R}^{V} p ∈ R V V V V
It therefore remains to bound the difference between the linear maxima uniformly over this family. The difficulty is that the feasible region itself depends on the sample. Our analysis bounds this difference uniformly by drawing on tools from statistical learning theory like symmetrization and contraction.
We extend this approach to Max-r r r § 6 . For a bipartition, choosing one part completely determines the other. But with more than two parts, the vertices not in one part can be divided among the other r − 1 r-1 r − 1
Related work
Estimating the optimum. Goldreich, Goldwasser, and Ron [11 ] gave the first sublinear-time algorithm achieving an additive ε n 2 \varepsilon n^2 ε n 2 O ( ε − 7 log 2 ( 2 / ε ) ) O(\varepsilon^{-7}\log^2(2/\varepsilon)) O ( ε − 7 log 2 ( 2/ ε )) O ~ ( ε − 5 ) \widetilde{O}(\varepsilon^{-5}) O ( ε − 5 )
Alon, Fernandez de la Vega, Kannan, and Karpinski [2 ] improved the sample bound, showing that the rescaled Max-Cut value of the induced subgraph on O ~ ( ε − 4 ) \widetilde{O}(\varepsilon^{-4}) O ( ε − 4 ) ε n 2 \varepsilon n^2 ε n 2 [7 ] , with linear programming. Rudelson and Vershynin [25 ] removed the logarithmic factor using tools from geometric functional analysis, showing that O ( ε − 4 ) O(\varepsilon^{-4}) O ( ε − 4 ) [22 ] obtain the same sample bound for unweighted graphs by analyzing a greedy algorithm.
This sampling approach was extended to non-dense graphs by Bhaskara, Daruki, and Venkatasubramanian [4 ] . They show that degree-based importance sampling in unweighted graphs of average degree d ˉ \bar{d} d ˉ ( 1 ± ε ) (1 \pm\varepsilon) ( 1 ± ε ) O ( n log n / ( d ˉ ε 4 ) ) O(n\log n/(\bar{d}\varepsilon^4)) O ( n log n / ( d ˉ ε 4 ))
For unweighted Max-r r r [11 ] obtained an additive ε n 2 \varepsilon n^2 ε n 2 O ( ε − 7 log 2 ( 2 r / ε ) ) O(\varepsilon^{-7}\log^2(2r/\varepsilon)) O ( ε − 7 log 2 ( 2 r / ε )) [1 ] extended their combinatorial sampling approach to finite-domain CSPs. For Max-r r r O ( ε − 7 log ( 2 r ) log 2 ( 2 r / ε ) ) O(\varepsilon^{-7}\log(2r)\log^2(2r/\varepsilon)) O ( ε − 7 log ( 2 r ) log 2 ( 2 r / ε )) [16 ] used cut decompositions and LP duality to analyze the rescaled optimum of a uniformly sampled induced subgraph, i.e., a value coreset, and showed that O ~ ( r 8 ε − 4 ) \widetilde{O}(r^8\varepsilon^{-4}) O ( r 8 ε − 4 )
Metric importance sampling. Fernandez de la Vega and Kenyon [8 ] obtained a polynomial-time approximation scheme (PTAS) for metric Max-Cut by reducing it to dense weighted Max-Cut. Their reduction replicates each vertex according to its weighted degree and rescales the edge weights. Chen, Jiang, and Krauthgamer [5 ] combined this reduction with uniform-sampling bounds to show that importance sampling of O ( ε − 4 ) O(\varepsilon^{-4}) O ( ε − 4 ) ( 1 ± ε ) (1 \pm\varepsilon) ( 1 ± ε )
Constructing a cut. The first PTASes for dense Max-Cut were obtained independently by Arora, Karger, and Karpinski [3 ] and Fernandez de la Vega [6 ] . Fernandez de la Vega uses a small vertex sample to guide the assignment of the remaining vertices, searching exhaustively over assignments within small blocks. Arora, Karger, and Karpinski enumerate assignments to O ( ε − 2 log n ) O(\varepsilon^{-2}\log n) O ( ε − 2 log n ) [9 ] extended this approach to unweighted graphs with Ω ( n 1 + σ ) \Omega(n^{1+\sigma}) Ω ( n 1 + σ ) 0 < σ ≤ 1 0 < \sigma\le1 0 < σ ≤ 1 1 − ε 1-\varepsilon 1 − ε 2 O ( n 1 − σ log n / ε 3 ) 2^{O(n^{1-\sigma}\log n/\varepsilon^3)} 2 O ( n 1 − σ l o g n / ε 3 )
Mathieu and Schudy [22 ] obtained additive O ( ε n 2 ) O(\varepsilon n^2) O ( ε n 2 ) O ( n 2 ) + 2 O ( ε − 2 ) O(n^2)+2^{O(\varepsilon^{-2})} O ( n 2 ) + 2 O ( ε − 2 ) [28 ] obtained the same approximation in faster time O ( n ε − 2 ) + 2 O ( ε − 2 ) O(n\varepsilon^{-2})+2^{O(\varepsilon^{-2})} O ( n ε − 2 ) + 2 O ( ε − 2 )
Yoshida and Zhou [29 ] use the Sherali–Adams hierarchy of LP relaxations and show that an optimal solution at level O ( ( ρ ε 2 ) − 1 ) O((\rho\varepsilon^2)^{-1}) O (( ρ ε 2 ) − 1 ) ( 1 − ε ) (1-\varepsilon) ( 1 − ε ) ρ n 2 \rho n^2 ρ n 2 ρ > 0 \rho>0 ρ > 0 O ( ε − 2 ) O(\varepsilon^{-2}) O ( ε − 2 )
Cut oracles. A cut oracle is an implicit representation (data structure) of a cut of value at least ( 1 − ε ) O P T (1-\varepsilon)\mathrm{OPT} ( 1 − ε ) OPT [ Δ ] d [\Delta]^d [ Δ ] d [17 ] combine dimension reduction with the cut oracle of Frahling and Sohler [10 ] , to obtain a ( 1 − ε ) (1-\varepsilon) ( 1 − ε ) exp ( poly ( ε − 1 ) ) poly ( d log Δ ) \exp(\operatorname{poly}(\varepsilon^{-1}))\operatorname{poly}(d\log\Delta) exp ( poly ( ε − 1 )) poly ( d log Δ ) [23 ] combine a sampled version of the greedy algorithm of Mathieu and Schudy [22 ] with the streaming sampler of Chen, Jiang, and Krauthgamer [5 ] , to obtain such an oracle using the smaller space bound poly ( d log Δ / ε ) \operatorname{poly}(d\log\Delta/\varepsilon) poly ( d log Δ/ ε )
Sample Complexity for Max-Cut
In this section, we prove our main theorem that sampling O ( ε − 2 ) O(\varepsilon^{-2}) O ( ε − 2 ) ε n 2 \varepsilon n^2 ε n 2 Theorem 2.1 . We then give an overview of the proof (in § 2.1 ), which is followed by the proof itself: We express the two cut values through a common functional (in § 2.2 ), then reduce the comparison of these two cut values to a certain difference between two linear maximization problems (in § 2.3 ), and then bound the expectation of this difference (in § 2.4 ). Finally, we specialize the error bound to uniform and importance sampling (in § 3.1 ).
Let V V V n n n A ∈ R V × V A \in\mathbb{R}^{V \times V} A ∈ R V × V A u v ≥ 0 A_{uv} \ge0 A uv ≥ 0 u , v ∈ V u,v \in V u , v ∈ V d ( v ) : = ∑ u ∈ V A v u d(v) := \sum_{u \in V} A_{vu} d ( v ) := ∑ u ∈ V A v u v v v D : = ∑ v ∈ V d ( v ) D := \sum_{v \in V} d(v) D := ∑ v ∈ V d ( v ) d ( v ) > 0 d(v) > 0 d ( v ) > 0 v ∈ V v \in V v ∈ V
Fix an integer k ≥ 1 k \ge1 k ≥ 1 p ∈ R V p \in\mathbb{R}^{V} p ∈ R V p v ≥ d ( v ) λ D p_v \ge\frac{d(v)}{\lambda D} p v ≥ λ D d ( v ) v ∈ V v \in V v ∈ V λ ≥ 1 \lambda\ge1 λ ≥ 1 p v = 1 / n p_v = 1/n p v = 1/ n X 1 , … , X k ∈ V X_1,\ldots,X_k \in V X 1 , … , X k ∈ V p p p [ k ] [k] [ k ] ( X 1 , … , X k ) (X_1,\ldots,X_k) ( X 1 , … , X k ) A ^ \widehat{A} A K ∈ R V × V K \in\mathbb{R}^{V \times V} K ∈ R V × V
A ^ i j : = A X i X j k 2 p X i p X j , K u v : = A u v n 2 p u p v . (1) \widehat{A}_{ij} := \frac{A_{X_iX_j}}{k^2p_{X_i}p_{X_j}}, \qquad K_{uv} := \frac{A_{uv}}{n^2p_up_v}. \tag*{(1)} A ij := k 2 p X i p X j A X i X j , K uv := n 2 p u p v A uv . (1) Let P X ∈ R V P_X \in\mathbb{R}^{V} P X ∈ R V P X ( v ) : = ∣ { i : X i = v } ∣ / k P_X(v) := |\{i:X_i=v\}|/k P X ( v ) := ∣ { i : X i = v } ∣/ k v ∈ V v \in V v ∈ V K K K 1 / n 2 1/n^2 1/ n 2 p p p P X P_X P X
MaxCut ( A ) n 2 = max S ⊆ V ∑ u ∈ S ∑ v ∉ S p u p v K u v , MaxCut ( A ^ ) n 2 = max S ⊆ V ∑ u ∈ S ∑ v ∉ S P X ( u ) P X ( v ) K u v . \frac{\operatorname{MaxCut}(A)}{n^2} = \max_{S \subseteq V} \sum_{u \in S}\sum_{v \notin S} p_up_vK_{uv}, \qquad\frac{\operatorname{MaxCut}(\widehat{A})}{n^2} = \max_{S \subseteq V} \sum_{u \in S}\sum_{v \notin S} P_X(u)P_X(v)K_{uv}. n 2 MaxCut ( A ) = S ⊆ V max u ∈ S ∑ v ∈ / S ∑ p u p v K uv , n 2 MaxCut ( A ) = S ⊆ V max u ∈ S ∑ v ∈ / S ∑ P X ( u ) P X ( v ) K uv . The second identity uses the fact that in the sampled graph, at least one optimal cut keeps all copies of the same vertex together. Lemma Lemma 2.4 proves this fact and both identities.
We will use the following quantity to control the sampling error through second moment estimates.
H : = ∑ v ∈ V p v ( ∑ u ∈ V p u K u v 2 ) 1 / 2 . H := \sum_{v \in V} p_v\left(\sum_{u \in V} p_uK_{uv}^2\right)^{1/2}. H := v ∈ V ∑ p v ( u ∈ V ∑ p u K uv 2 ) 1/2 . A simple calculation (see Lemma 2.10) shows that H ≤ 1 H \le1 H ≤ 1 A u w A_{uw} A u w [ 0 , 1 ] [0,1] [ 0 , 1 ]
p v ≥ d ( v ) n 2 , ∀ v ∈ V . (2) p_v \ge\frac{d(v)}{n^2}, \qquad\forall v \in V. \tag*{(2)} p v ≥ n 2 d ( v ) , ∀ v ∈ V . (2) Theorem 2.1 (Sampling approximates the Max-Cut value). For every positive probability vector p ∈ R V p \in\mathbb{R}^{V} p ∈ R V
E ∣ MaxCut ( A ^ ) − MaxCut ( A ) n 2 ∣ ≤ 48 H k . (3) \mathbb{E}\left|\frac{\operatorname{MaxCut}(\widehat{A})-\operatorname{MaxCut}(A)}{n^2}\right| \le\frac{48H}{\sqrt{k}}. \tag*{(3)} E n 2 MaxCut ( A ) − MaxCut ( A ) ≤ k 48 H . (3) Corollary 2.2 (High-probability bound). Assume 0 ≤ A u v ≤ 1 0 \le A_{uv} \le1 0 ≤ A uv ≤ 1 for every u , v ∈ V u,v \in V u , v ∈ V Then for every positive sampling distribution satisfying (2) , including uniform and importance sampling with λ = 1 \lambda=1 λ = 1
∀ 0 < ε < 1 , P ( ∣ MaxCut ( A ^ ) − MaxCut ( A ) ∣ ≥ ε n 2 ) ≤ 48 ε k . (4) \forall\,0 < \varepsilon< 1,\quad\mathbb{P}\left(\left|\operatorname{MaxCut}(\widehat{A})-\operatorname{MaxCut}(A)\right| \ge\varepsilon n^2\right) \le\frac{48}{\varepsilon\sqrt{k}}. \tag*{(4)} ∀ 0 < ε < 1 , P ( MaxCut ( A ) − MaxCut ( A ) ≥ ε n 2 ) ≤ ε k 48 . (4) Consequently, to get error probability at most δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) it suffices to take any k ≥ 2304 / ( δ 2 ε 2 ) k \ge2304/(\delta^2\varepsilon^2) k ≥ 2304/ ( δ 2 ε 2 )
Proof. § 3.1 verifies the bound H ≤ 1 H \le1 H ≤ 1 (2) , and then Markov’s inequality implies (4) . Solving for k k k δ \delta δ
A simple calculation shows that, for importance sampling with parameter λ ≥ 1 \lambda\ge1 λ ≥ 1 λ \lambda λ k ≥ 20736 λ ε − 2 k \ge20736\lambda\varepsilon^{-2} k ≥ 20736 λ ε − 2 1 / 3 1/3 1/3
Proof overview
Our first step is to view sampling as a change in vertex weights. Given K K K r ∈ R V r \in\mathbb{R}^{V} r ∈ R V F K ( r ) F_K(r) F K ( r ) K K K r v r_v r v ( u , v ) (u,v) ( u , v ) r u r v K u v r_ur_vK_{uv} r u r v K uv r v r_v r v § 2.2 that this does not change the optimum value, and in fact
F K ( p ) = MaxCut ( A ) n 2 , F K ( P X ) = MaxCut ( A ^ ) n 2 . F_K(p)=\frac{\operatorname{MaxCut}(A)}{n^2},\qquad F_K(P_X)=\frac{\operatorname{MaxCut}(\widehat{A})}{n^2}. F K ( p ) = n 2 MaxCut ( A ) , F K ( P X ) = n 2 MaxCut ( A ) . We then compare in § 2.3 these two values, and more generally F K ( r ) F_K(r) F K ( r ) F K ( s ) F_K(s) F K ( s ) r , s ∈ R V r,s \in\mathbb{R}^{V} r , s ∈ R V r r r s s s q ∈ { r , s } q \in\{r,s\} q ∈ { r , s } 0 ≤ a ≤ q 0 \le a \le q 0 ≤ a ≤ q a T K ( q − a ) a^{\mathsf{T}}K(q-a) a T K ( q − a ) a T K ( q − a ) a^{\mathsf{T}}K(q-a) a T K ( q − a ) a T K c a^{\mathsf{T}}Kc a T K c c ∈ R V c \in\mathbb{R}^{V} c ∈ R V a a a 0 ≤ c ≤ r 0 \le c \le r 0 ≤ c ≤ r 0 ≤ c ≤ s 0 \le c \le s 0 ≤ c ≤ s c c c a a a M q ( c ) : = max 0 ≤ a ≤ q a T K c M_q(c):=\max_{0\le a\le q}a^{\mathsf{T}}Kc M q ( c ) := max 0 ≤ a ≤ q a T K c M r ( c ) M_r(c) M r ( c ) M s ( c ) M_s(c) M s ( c ) c c c Δ K ( r , s ) \Delta_K(r,s) Δ K ( r , s ) C ( r , s ) C(r,s) C ( r , s ) c c c
Δ K ( r , s ) : = max c ∈ C ( r , s ) ∣ M r ( c ) − M s ( c ) ∣ . \Delta_K(r,s):=\max_{c\in C(r,s)}\left|M_r(c)-M_s(c)\right|. Δ K ( r , s ) := c ∈ C ( r , s ) max ∣ M r ( c ) − M s ( c ) ∣ . A minimax argument converts the comparison of these maxima into a matching of fractional cuts. For each a ∈ R V a \in\mathbb{R}^{V} a ∈ R V 0 ≤ a ≤ r 0 \le a \le r 0 ≤ a ≤ r b ∈ R V b \in\mathbb{R}^{V} b ∈ R V 0 ≤ b ≤ s 0 \le b \le s 0 ≤ b ≤ s a T K c a^{\mathsf{T}}Kc a T K c b T K c b^{\mathsf{T}}Kc b T K c c c c
max c ∣ ( a − b ) T K c ∣ ≤ Δ K ( r , s ) . \max_c\left|(a-b)^{\mathsf{T}}Kc\right| \le\Delta_K(r,s). c max ( a − b ) T K c ≤ Δ K ( r , s ) . Using this matching, a simple calculation shows that
∣ F K ( r ) − F K ( s ) ∣ ≤ 4 Δ K ( r , s ) . \left|F_K(r)-F_K(s)\right| \le4\Delta_K(r,s). ∣ F K ( r ) − F K ( s ) ∣ ≤ 4 Δ K ( r , s ) . Applying this bound with r = p r=p r = p s = P X s=P_X s = P X E X Δ K ( p , P X ) \mathbb{E}_X\Delta_K(p,P_X) E X Δ K ( p , P X ) § 2.4 . The main difficulty is that both the sampling error for a given c c c c c c X X X c c c Δ K ( p , P X ) \Delta_K(p,P_X) Δ K ( p , P X ) symmetrization . We draw an independent ghost sample Y 1 , … , Y k Y_1,\ldots,Y_k Y 1 , … , Y k p p p P Y P_Y P Y Δ K ( p , P X ) \Delta_K(p,P_X) Δ K ( p , P X )
Δ K ( p , P X ) = max c ∈ C ( p , P X ) ∣ E Y [ M P X ( c ) − M P Y ( c ) ] ∣ . \Delta_K(p,P_X)=\max_{c\in\mathcal{C}(p,P_X)}\left|\mathbb{E}_Y\left[M_{P_X}(c)-M_{P_Y}(c)\right]\right|. Δ K ( p , P X ) = c ∈ C ( p , P X ) max ∣ E Y [ M P X ( c ) − M P Y ( c ) ] ∣ . We enlarge the feasible region for c c c X i X_i X i Y i Y_i Y i k k k σ 1 , … , σ k ∈ { ± 1 } \sigma_1,\ldots,\sigma_k\in\{\pm1\} σ 1 , … , σ k ∈ { ± 1 } + 1 +1 + 1 X i , Y i X_i,Y_i X i , Y i − 1 -1 − 1 [ t ] + : = max { t , 0 } [t]_+:=\max\{t,0\} [ t ] + := max { t , 0 } M P X ( c ) − M P Y ( c ) M_{P_X}(c)-M_{P_Y}(c) M P X ( c ) − M P Y ( c )
1 k ∑ i = 1 k σ i ( [ ( K c ) X i ] + − [ ( K c ) Y i ] + ) . \frac{1}{k}\sum_{i=1}^{k}\sigma_i\left([(Kc)_{X_i}]_+-[(Kc)_{Y_i}]_+\right). k 1 i = 1 ∑ k σ i ( [( K c ) X i ] + − [( K c ) Y i ] + ) . This lets us apply Ledoux–Talagrand contraction to reduce to a signed sum linear in c c c c c c ∣ c v ∣ |c_v| ∣ c v ∣
E X Δ K ( p , P X ) ≤ 12 H k . \mathbb{E}_X\Delta_K(p,P_X)\leq\frac{12H}{\sqrt{k}}. E X Δ K ( p , P X ) ≤ k 12 H . Reduce both Max-Cut values to one functional
We express the normalized Max-Cut values of the original graph A A A A ^ \widehat{A} A F K ( ⋅ ) F_K(\cdot) F K ( ⋅ ) p p p P X P_X P X
To define F K F_K F K x v ∈ { 0 , 1 } x_v\in\{0,1\} x v ∈ { 0 , 1 } v v v x v = 1 x_v=1 x v = 1 x v = 0 x_v=0 x v = 0 x v ∈ [ 0 , 1 ] x_v\in[0,1] x v ∈ [ 0 , 1 ] x v x_v x v v v v 1 − x v 1-x_v 1 − x v r v ≥ 0 r_v\geq0 r v ≥ 0 v v v a v = r v x v a_v=r_vx_v a v = r v x v weighted fraction of v v v a v a_v a v v v v r v − a v r_v-a_v r v − a v 0 ≤ a v ≤ r v 0\leq a_v\leq r_v 0 ≤ a v ≤ r v a v ∈ { 0 , r v } a_v\in\{0,r_v\} a v ∈ { 0 , r v } p p p P X P_X P X
Define the feasible fractional cuts by
Z ( r ) : = { a ∈ R V : 0 ≤ a v ≤ r v for every v } Z(r):=\{a\in\mathbb{R}^{V}:0\leq a_v\leq r_v\text{ for every }v\} Z ( r ) := { a ∈ R V : 0 ≤ a v ≤ r v for every v } and their optimal value by
F K ( r ) : = max a ∈ Z ( r ) a ⊤ K ( r − a ) . (5) F_K(r):=\max_{a\in Z(r)}a^\top K(r-a). \tag*{(5)} F K ( r ) := a ∈ Z ( r ) max a ⊤ K ( r − a ) . (5) Allowing fractional cuts makes the feasible set convex, which is useful for the comparison in § 2.3 .
Lemma 2.3 (The maximum is attained by a cut). For every nonnegative weight vector r ∈ R V r\in\mathbb{R}^{V} r ∈ R V there exists a maximizer a ∈ Z ( r ) a\in Z(r) a ∈ Z ( r ) in (5) that corresponds to a cut, i.e., a v ∈ { 0 , r v } a_v\in\{0,r_v\} a v ∈ { 0 , r v } for all v ∈ V v\in V v ∈ V
Proof. Since K v v = 0 K_{vv}=0 K v v = 0 a T K ( r − a ) \mathbf{a}^{\mathsf{T}}K(\mathbf{r}-\mathbf{a}) a T K ( r − a ) a v a_v a v [ 0 , r v ] [0,r_v] [ 0 , r v ] a v a_v a v a v ∈ { 0 , r v } a_v \in\{0,r_v\} a v ∈ { 0 , r v } v v v
Lemma 2.4 (The two Max-Cut values). With p p p P X P_X P X and K K K defined above,
F K ( p ) = MaxCut ( A ) n 2 , F K ( P X ) = MaxCut ( A ^ ) n 2 . F_K(p)=\frac{\operatorname{MaxCut}(A)}{n^2},\qquad F_K(P_X)=\frac{\operatorname{MaxCut}(\widehat{A})}{n^2}. F K ( p ) = n 2 MaxCut ( A ) , F K ( P X ) = n 2 MaxCut ( A ) . Proof. For the first identity, Lemma 2.3 lets us maximize over cuts S ⊆ V S \subseteq V S ⊆ V p u p v K u v = A u v / n 2 p_up_vK_{uv}=A_{uv}/n^2 p u p v K uv = A uv / n 2
F K ( p ) = max S ⊆ V ∑ u ∈ S ∑ v ∉ S p u p v K u v = MaxCut ( A ) n 2 . F_K(p)=\max_{S\subseteq V}\sum_{u\in S}\sum_{v\notin S}p_up_vK_{uv}=\frac{\operatorname{MaxCut}(A)}{n^2}. F K ( p ) = S ⊆ V max u ∈ S ∑ v ∈ / S ∑ p u p v K uv = n 2 MaxCut ( A ) . For the second identity, we first show that all copies of a repeatedly sampled vertex can be moved to the same side without decreasing the cut value. Start with an optimal cut for the sampled subgraph (induced on X 1 , … , X k X_1,\ldots,X_k X 1 , … , X k
For an original vertex v v v v v v
Such a cut is described by a set S ⊆ V S \subseteq V S ⊆ V S S S u ∈ S u\in S u ∈ S v ∉ S v\notin S v ∈ / S k P X ( u ) k P X ( v ) kP_X(u)\,kP_X(v) k P X ( u ) k P X ( v ) ( i , j ) (i,j) ( i , j ) X i = u X_i=u X i = u X j = v X_j=v X j = v n 2 n^2 n 2
A ^ i j n 2 = A u v k 2 n 2 p u p v = K u v k 2 . \frac{\widehat{A}_{ij}}{n^2}=\frac{A_{uv}}{k^2n^2p_up_v}=\frac{K_{uv}}{k^2}. n 2 A ij = k 2 n 2 p u p v A uv = k 2 K uv . Therefore, applying Lemma 2.3 with r = P X r=P_X r = P X
F K ( P X ) = max S ⊆ V ∑ u ∈ S ∑ v ∉ S P X ( u ) P X ( v ) K u v = MaxCut ( A ^ ) n 2 . F_K(P_X)=\max_{S\subseteq V}\sum_{u\in S}\sum_{v\notin S}P_X(u)P_X(v)K_{uv}=\frac{\operatorname{MaxCut}(\widehat{A})}{n^2}. F K ( P X ) = S ⊆ V max u ∈ S ∑ v ∈ / S ∑ P X ( u ) P X ( v ) K uv = n 2 MaxCut ( A ) . By Lemma 2.4,
∣ MaxCut ( A ^ ) − MaxCut ( A ) ∣ n 2 = ∣ F K ( P X ) − F K ( p ) ∣ . \frac{\left|\operatorname{MaxCut}(\widehat{A})-\operatorname{MaxCut}(A)\right|}{n^2}=\left|F_K(P_X)-F_K(p)\right|. n 2 MaxCut ( A ) − MaxCut ( A ) = ∣ F K ( P X ) − F K ( p ) ∣ . Compare cut values under two vertex distributions
In this subsection, we bound the difference between F K ( r ) F_K(r) F K ( r ) F K ( s ) F_K(s) F K ( s ) r , s r,s r , s V V V r = p r=p r = p s = P X s=P_X s = P X
For a nonnegative vector q q q M q ( c ) M_q(c) M q ( c ) x T K c \mathbf{x}^{\mathsf{T}}Kc x T K c x ∈ Z ( q ) \mathbf{x}\in Z(q) x ∈ Z ( q )
M q ( c ) : = max x ∈ Z ( q ) x T K c = ∑ v q v [ ( K c ) v ] + , where [ t ] + : = max { t , 0 } . (6) M_q(c):=\max_{\mathbf{x}\in Z(q)}\mathbf{x}^{\mathsf{T}}Kc=\sum_v q_v[(Kc)_v]_+,\qquad\text{where }[t]_+:=\max\{t,0\}. \tag*{(6)} M q ( c ) := x ∈ Z ( q ) max x T K c = v ∑ q v [( K c ) v ] + , where [ t ] + := max { t , 0 } . (6) The equality follows by choosing x v = q v x_v=q_v x v = q v ( K c ) v > 0 (Kc)_v>0 ( K c ) v > 0 x v = 0 x_v=0 x v = 0
To compare M r M_r M r M s M_s M s Z ( r ) Z(r) Z ( r ) Z ( s ) Z(s) Z ( s )
C ( r , s ) : = conv ( Z ( r ) ∪ − Z ( r ) ∪ Z ( s ) ∪ − Z ( s ) ) . (7) C(r,s) := \operatorname{conv}\bigl(Z(r) \cup-Z(r) \cup Z(s) \cup-Z(s)\bigr). \tag*{(7)} C ( r , s ) := conv ( Z ( r ) ∪ − Z ( r ) ∪ Z ( s ) ∪ − Z ( s ) ) . (7) We consider their largest absolute difference, defined by
Δ K ( r , s ) : = max c ∈ C ( r , s ) ∣ M r ( c ) − M s ( c ) ∣ . (8) \Delta_K(r,s) := \max_{c \in C(r,s)} \lvert M_r(c) - M_s(c) \rvert. \tag*{(8)} Δ K ( r , s ) := c ∈ C ( r , s ) max ∣ M r ( c ) − M s ( c )∣ . (8) Lemma 2.5 (Comparison of cut values). For every pair of probability vectors r , s ∈ R V r,s \in\mathbb{R}^V r , s ∈ R V
∣ F K ( r ) − F K ( s ) ∣ ≤ 4 Δ K ( r , s ) . (9) \lvert F_K(r) - F_K(s) \rvert\le4\Delta_K(r,s). \tag*{(9)} ∣ F K ( r ) − F K ( s )∣ ≤ 4 Δ K ( r , s ) . (9) Taking r = p r=p r = p s = P X s=P_X s = P X ∣ F K ( P X ) − F K ( p ) ∣ ≤ 4 Δ K ( p , P X ) \lvert F_K(P_X) - F_K(p) \rvert\le4\Delta_K(p,P_X) ∣ F K ( P X ) − F K ( p )∣ ≤ 4 Δ K ( p , P X ) E X Δ K ( p , P X ) \mathbb{E}_X\Delta_K(p,P_X) E X Δ K ( p , P X ) § 2.4 .
To prove Lemma 2.5, we first prove two bounds. One matches fractional cuts under r r r s s s
Lemma 2.6 (Matching fractional cuts). Let r , s ∈ R V r,s \in\mathbb{R}^V r , s ∈ R V a ∈ Z ( r ) a \in Z(r) a ∈ Z ( r ) b ∈ Z ( s ) b \in Z(s) b ∈ Z ( s )
max c ∈ C ( r , s ) ∣ ( a − b ) T K c ∣ ≤ Δ K ( r , s ) . (10) \max_{c \in C(r,s)} \lvert(a-b)^{\mathsf{T}} Kc \rvert\le\Delta_K(r,s). \tag*{(10)} c ∈ C ( r , s ) max ∣( a − b ) T K c ∣ ≤ Δ K ( r , s ) . (10) Consequently,
max c ∈ C ( r , s ) ∣ ( r − s ) T K c ∣ ≤ 2 Δ K ( r , s ) . (11) \max_{c \in C(r,s)} \lvert(r-s)^{\mathsf{T}} Kc \rvert\le2\Delta_K(r,s). \tag*{(11)} c ∈ C ( r , s ) max ∣( r − s ) T K c ∣ ≤ 2 Δ K ( r , s ) . (11) Proof. Fix a ∈ Z ( r ) a \in Z(r) a ∈ Z ( r ) C ( r , s ) = − C ( r , s ) C(r,s)=-C(r,s) C ( r , s ) = − C ( r , s ) [26 ] to the function ( b , c ) ↦ ( a − b ) T K c (b,c) \mapsto(a-b)^{\mathsf{T}}Kc ( b , c ) ↦ ( a − b ) T K c Z ( s ) Z(s) Z ( s ) C ( r , s ) C(r,s) C ( r , s )
min b ∈ Z ( s ) max c ∈ C ( r , s ) ∣ ( a − b ) T K c ∣ = min b ∈ Z ( s ) max c ∈ C ( r , s ) ( a − b ) T K c = max c ∈ C ( r , s ) min b ∈ Z ( s ) ( a − b ) T K c = max c ∈ C ( r , s ) ( a T K c − M s ( c ) ) ≤ max c ∈ C ( r , s ) ( M r ( c ) − M s ( c ) ) ≤ Δ K ( r , s ) . \begin{aligned}
\min_{b \in Z(s)} \max_{c \in C(r,s)} \lvert(a-b)^{\mathsf{T}}Kc \rvert
&= \min_{b \in Z(s)} \max_{c \in C(r,s)} (a-b)^{\mathsf{T}}Kc \\
&= \max_{c \in C(r,s)} \min_{b \in Z(s)} (a-b)^{\mathsf{T}}Kc \\
&= \max_{c \in C(r,s)} \left(a^{\mathsf{T}}Kc-M_s(c)\right) \\
&\le\max_{c \in C(r,s)} \left(M_r(c)-M_s(c)\right) \le\Delta_K(r,s).
\end{aligned} b ∈ Z ( s ) min c ∈ C ( r , s ) max ∣( a − b ) T K c ∣ = b ∈ Z ( s ) min c ∈ C ( r , s ) max ( a − b ) T K c = c ∈ C ( r , s ) max b ∈ Z ( s ) min ( a − b ) T K c = c ∈ C ( r , s ) max ( a T K c − M s ( c ) ) ≤ c ∈ C ( r , s ) max ( M r ( c ) − M s ( c ) ) ≤ Δ K ( r , s ) . The minimum is attained, so (10) follows.
To prove the second inequality, fix c ∈ C ( r , s ) c \in C(r,s) c ∈ C ( r , s ) [ t ] + − [ − t ] + = t [t]_+ - [-t]_+ = t [ t ] + − [ − t ] + = t (6) give
( r − s ) T K c = ( M r ( c ) − M s ( c ) ) − ( M r ( − c ) − M s ( − c ) ) . (r-s)^{\mathsf{T}}Kc = \left(M_r(c)-M_s(c)\right) - \left(M_r(-c)-M_s(-c)\right). ( r − s ) T K c = ( M r ( c ) − M s ( c ) ) − ( M r ( − c ) − M s ( − c ) ) . Both c c c − c -c − c C ( r , s ) C(r,s) C ( r , s ) Δ K ( r , s ) \Delta_K(r,s) Δ K ( r , s )
The triangle inequality gives ∣ ( r − s ) T K c ∣ ≤ 2 Δ K ( r , s ) \lvert(r-s)^{\mathsf{T}}Kc \rvert\le2\Delta_K(r,s) ∣( r − s ) T K c ∣ ≤ 2 Δ K ( r , s ) (11) . □
Proof of Lemma 2.5. Let a ∈ Z ( r ) a \in Z(r) a ∈ Z ( r ) F K ( r ) F_K(r) F K ( r ) b ∈ Z ( s ) b \in Z(s) b ∈ Z ( s ) Δ = Δ K ( r , s ) \Delta= \Delta_K(r,s) Δ = Δ K ( r , s ) c ∈ C ( r , s ) c \in C(r,s) c ∈ C ( r , s )
∣ ( a − b ) T K c ∣ ≤ Δ , ∣ ( r − s ) T K c ∣ ≤ 2 Δ . (12) \left|(a-b)^{\mathsf{T}}Kc\right| \le\Delta,\qquad\left|(r-s)^{\mathsf{T}}Kc\right| \le2\Delta. \tag*{(12)} ( a − b ) T K c ≤ Δ , ( r − s ) T K c ≤ 2Δ. (12) Since F K ( s ) ≥ b T K ( s − b ) F_K(s) \ge b^{\mathsf{T}}K(s-b) F K ( s ) ≥ b T K ( s − b ) K K K
F K ( r ) − F K ( s ) ≤ a T K ( r − a ) − b T K ( s − b ) = ( a − b ) T K ( r − a ) + ( r − s ) T K b − ( a − b ) T K b ≤ ∣ ( a − b ) T K ( r − a ) ∣ + ∣ ( r − s ) T K b ∣ + ∣ ( a − b ) T K b ∣ . (13) \begin{aligned}
F_K(r)-F_K(s) &\le a^{\mathsf{T}}K(r-a)-b^{\mathsf{T}}K(s-b) \\
&=(a-b)^{\mathsf{T}}K(r-a)+(r-s)^{\mathsf{T}}Kb-(a-b)^{\mathsf{T}}Kb \\
&\le\left|(a-b)^{\mathsf{T}}K(r-a)\right|+\left|(r-s)^{\mathsf{T}}Kb\right|+\left|(a-b)^{\mathsf{T}}Kb\right|. \tag*{(13)}
\end{aligned} F K ( r ) − F K ( s ) ≤ a T K ( r − a ) − b T K ( s − b ) = ( a − b ) T K ( r − a ) + ( r − s ) T K b − ( a − b ) T K b ≤ ( a − b ) T K ( r − a ) + ( r − s ) T K b + ( a − b ) T K b . (13) Since r − a ∈ Z ( r ) r-a \in Z(r) r − a ∈ Z ( r ) b ∈ Z ( s ) b \in Z(s) b ∈ Z ( s ) C ( r , s ) C(r,s) C ( r , s ) (12) to get
F K ( r ) − F K ( s ) ≤ Δ + 2 Δ + Δ = 4 Δ . F_K(r)-F_K(s) \le\Delta+2\Delta+\Delta=4\Delta. F K ( r ) − F K ( s ) ≤ Δ + 2Δ + Δ = 4Δ. Interchanging r r r s s s F K ( s ) − F K ( r ) F_K(s)-F_K(r) F K ( s ) − F K ( r ) (9) .
Bound the sampling error
In this subsection we prove that
E X Δ K ( p , P X ) ≤ 12 H k . (14) \mathbb{E}_X\Delta_K(p,P_X) \le\frac{12H}{\sqrt{k}}. \tag*{(14)} E X Δ K ( p , P X ) ≤ k 12 H . (14) Together with Lemmas 2.4 and 2.5, this completes the proof of Theorem 2.1 . Recall that Δ K ( p , P X ) \Delta_K(p,P_X) Δ K ( p , P X )
M p ( c ) = ∑ v p v [ ( K c ) v ] + , M P X ( c ) = 1 k ∑ i = 1 k [ ( K c ) X i ] + , M_p(c)=\sum_v p_v[(Kc)_v]_+,\qquad M_{P_X}(c)=\frac{1}{k}\sum_{i=1}^{k}[(Kc)_{X_i}]_+, M p ( c ) = v ∑ p v [( K c ) v ] + , M P X ( c ) = k 1 i = 1 ∑ k [( K c ) X i ] + , over c ∈ C ( p , P X ) c \in C(p,P_X) c ∈ C ( p , P X ) X X X M P X M_{P_X} M P X
The proof has two steps, using several tools from statistical learning theory.
Symmetrization. Instead of comparing P X P_X P X p p p P X , P Y P_X,P_Y P X , P Y X , Y X,Y X , Y c c c B X , Y B_{X,Y} B X , Y [20 ] .
We use symmetrization and Ledoux–Talagrand contraction [18 ] to reduce the problem to bounding the expected maximum of sums of ( K c ) X i (Kc)_{X_i} ( K c ) X i Lemma 2.7 ).
Second-moment bounds. The signed sums are linear in c c c p p p P X P_X P X P Y P_Y P Y H / k H/\sqrt{k} H / k L 1 L^1 L 1 3 H / k 3H/\sqrt{k} 3 H / k Lemma 2.8 ).
Combining the two estimates gives (14) . Lemma 2.5 then bounds the expected normalized Max-Cut error by 48 H / k 48H/\sqrt{k} 48 H / k
Step 1. Symmetrization
Lemma 2.7 (Reduction to a signed linear maximum). Let Y 1 , … , Y k Y_1,\ldots,Y_k Y 1 , … , Y k p p p X X X P Y P_Y P Y σ 1 , … , σ k ∈ { ± 1 } \sigma_1,\ldots,\sigma_k \in\{ \pm1\} σ 1 , … , σ k ∈ { ± 1 } X , Y X,Y X , Y
B X , Y : = { c ∈ R V : ∀ v ∈ V , ∣ c v ∣ ≤ p v + P X ( v ) + P Y ( v ) } . \mathcal{B}_{X,Y} := \left\{c \in\mathbb{R}^{V} : \forall v \in V,\ |c_v| \le p_v + P_X(v) + P_Y(v)\right\}. B X , Y := { c ∈ R V : ∀ v ∈ V , ∣ c v ∣ ≤ p v + P X ( v ) + P Y ( v ) } . Then
E X Δ K ( p , P X ) ≤ 4 E X , Y , σ max c ∈ B X , Y ∣ 1 k ∑ i = 1 k σ i ( K c ) X i ∣ . (15) \mathbb{E}_X \Delta_K(p,P_X) \le4\mathbb{E}_{X,Y,\sigma}\max_{c\in\mathcal{B}_{X,Y}}\left|\frac{1}{k}\sum_{i=1}^{k}\sigma_i(Kc)_{X_i}\right|. \tag*{(15)} E X Δ K ( p , P X ) ≤ 4 E X , Y , σ c ∈ B X , Y max k 1 i = 1 ∑ k σ i ( K c ) X i . (15) Proof. We begin with the symmetrization step using a ghost sample. For every c ∈ C ( p , P X ) c \in C(p,P_X) c ∈ C ( p , P X ) M p ( c ) M_p(c) M p ( c )
E Y M P Y ( c ) = ∑ v p v [ ( K c ) v ] + = M p ( c ) . \mathbb{E}_Y M_{P_Y}(c) = \sum_v p_v[(Kc)_v]_+ = M_p(c). E Y M P Y ( c ) = v ∑ p v [( K c ) v ] + = M p ( c ) . The box B X , Y \mathcal{B}_{X,Y} B X , Y C ( p , P X ) C(p,P_X) C ( p , P X )
C ( p , P X ) ⊆ B X , Y . (16) C(p,P_X) \subseteq\mathcal{B}_{X,Y}. \tag*{(16)} C ( p , P X ) ⊆ B X , Y . (16) With X X X C ( p , P X ) C(p,P_X) C ( p , P X ) Y Y Y
Δ K ( p , P X ) = max c ∈ C ( p , P X ) ∣ E Y [ M P X ( c ) − M P Y ( c ) ] ∣ ≤ max c ∈ C ( p , P X ) E Y ∣ M P X ( c ) − M P Y ( c ) ∣ ≤ E Y max c ∈ C ( p , P X ) ∣ M P X ( c ) − M P Y ( c ) ∣ ≤ E Y max c ∈ B X , Y ∣ 1 k ∑ i = 1 k ( [ ( K c ) X i ] + − [ ( K c ) Y i ] + ) ∣ . \begin{aligned}
\Delta_K(p,P_X)
&= \max_{c\in C(p,P_X)} \left|\mathbb{E}_Y[M_{P_X}(c)-M_{P_Y}(c)]\right| \\
&\le\max_{c\in C(p,P_X)} \mathbb{E}_Y\left|M_{P_X}(c)-M_{P_Y}(c)\right| \\
&\le\mathbb{E}_Y\max_{c\in C(p,P_X)}\left|M_{P_X}(c)-M_{P_Y}(c)\right| \\
&\le\mathbb{E}_Y\max_{c\in\mathcal{B}_{X,Y}}\left|\frac{1}{k}\sum_{i=1}^{k}\left([(Kc)_{X_i}]_+-[(Kc)_{Y_i}]_+\right)\right|.
\end{aligned} Δ K ( p , P X ) = c ∈ C ( p , P X ) max ∣ E Y [ M P X ( c ) − M P Y ( c )] ∣ ≤ c ∈ C ( p , P X ) max E Y ∣ M P X ( c ) − M P Y ( c ) ∣ ≤ E Y c ∈ C ( p , P X ) max ∣ M P X ( c ) − M P Y ( c ) ∣ ≤ E Y c ∈ B X , Y max k 1 i = 1 ∑ k ( [( K c ) X i ] + − [( K c ) Y i ] + ) . We next take expectation over X X X σ ∈ { ± 1 } k \sigma\in\{\pm1\}^k σ ∈ { ± 1 } k
( X ~ i , Y ~ i ) : = { ( X i , Y i ) , σ i = 1 , ( Y i , X i ) , σ i = − 1. (\widetilde{X}_i,\widetilde{Y}_i) :=
\begin{cases}
(X_i,Y_i), & \sigma_i=1,\\
(Y_i,X_i), & \sigma_i=-1.
\end{cases} ( X i , Y i ) := { ( X i , Y i ) , ( Y i , X i ) , σ i = 1 , σ i = − 1. Each exchange reverses its pair’s contribution, so
[ ( K c ) X ~ i ] + − [ ( K c ) Y ~ i ] + = σ i ( [ ( K c ) X i ] + − [ ( K c ) Y i ] + ) . [(Kc)_{\widetilde{X}_i}]_+-[(Kc)_{\widetilde{Y}_i}]_+
=\sigma_i\left([(Kc)_{X_i}]_+-[(Kc)_{Y_i}]_+\right). [( K c ) X i ] + − [( K c ) Y i ] + = σ i ( [( K c ) X i ] + − [( K c ) Y i ] + ) . The exchanges preserve the joint distribution of the samples. They also preserve P X + P Y P_X+P_Y P X + P Y B X ~ , Y ~ = B X , Y \mathcal{B}_{\widetilde{X},\widetilde{Y}}=\mathcal{B}_{X,Y} B X , Y = B X , Y
E X Δ K ( p , P X ) ≤ E X , Y max c ∈ B X , Y ∣ 1 k ∑ i = 1 k ( [ ( K c ) X i ] + − [ ( K c ) Y i ] + ) ∣ = E X , Y , σ max c ∈ B X , Y ∣ 1 k ∑ i = 1 k σ i ( [ ( K c ) X i ] + − [ ( K c ) Y i ] + ) ∣ \begin{aligned}
\mathbb{E}_{X}\Delta_{K}(p,P_X) \le\mathbb{E}_{X,Y}\max_{c\in\mathcal{B}_{X,Y}}\left|\frac{1}{k}\sum_{i=1}^{k}\left([(Kc)X_i]_+ - [(Kc)Y_i]_+\right)\right| \\
&= \mathbb{E}_{X,Y,\sigma}\max_{c\in\mathcal{B}_{X,Y}}\left|\frac{1}{k}\sum_{i=1}^{k}\sigma_i\left([(Kc)X_i]_+ - [(Kc)Y_i]_+\right)\right|
\end{aligned} E X Δ K ( p , P X ) ≤ E X , Y c ∈ B X , Y max k 1 i = 1 ∑ k ( [( K c ) X i ] + − [( K c ) Y i ] + ) = E X , Y , σ c ∈ B X , Y max k 1 i = 1 ∑ k σ i ( [( K c ) X i ] + − [( K c ) Y i ] + ) ≤ 2 E X , Y , σ max c ∈ B X , Y ∣ 1 k ∑ i = 1 k σ i [ ( K c ) X i ] + ∣ . (17) \le2\mathbb{E}_{X,Y,\sigma}\max_{c\in\mathcal{B}_{X,Y}}\left|\frac{1}{k}\sum_{i=1}^{k}\sigma_i[(Kc)X_i]_+\right| . \tag*{(17)} ≤ 2 E X , Y , σ c ∈ B X , Y max k 1 i = 1 ∑ k σ i [( K c ) X i ] + . (17) where the last inequality uses the triangle inequality and symmetry between X X X Y Y Y g : t ↦ [ t ] + g:t\mapsto[t]_+ g : t ↦ [ t ] + X , Y X,Y X , Y [18 ] ) therefore gives
E σ max c ∈ B X , Y ∣ 1 k ∑ i = 1 k σ i [ ( K c ) X i ] + ∣ ≤ 2 E σ max c ∈ B X , Y ∣ 1 k ∑ i = 1 k σ i ( K c ) X i ∣ . \mathbb{E}_{\sigma}\max_{c\in\mathcal{B}_{X,Y}}\left|\frac{1}{k}\sum_{i=1}^{k}\sigma_i[(Kc)X_i]_+\right|\le2\mathbb{E}_{\sigma}\max_{c\in\mathcal{B}_{X,Y}}\left|\frac{1}{k}\sum_{i=1}^{k}\sigma_i(Kc)X_i\right| . E σ c ∈ B X , Y max k 1 i = 1 ∑ k σ i [( K c ) X i ] + ≤ 2 E σ c ∈ B X , Y max k 1 i = 1 ∑ k σ i ( K c ) X i . Taking expectation over X , Y X,Y X , Y (17) proves the lemma. □
Second-moment bounds
Lemma 2.8 (Bound for the signed maximum).
E X , Y , σ max c ∈ B X , Y ∣ 1 k ∑ i = 1 k σ i ( K c ) X i ∣ ≤ 3 H k . (18) \mathbb{E}_{X,Y,\sigma}\max_{c\in\mathcal{B}_{X,Y}}\left|\frac{1}{k}\sum_{i=1}^{k}\sigma_i(Kc)X_i\right|\le\frac{3H}{\sqrt{k}} . \tag*{(18)} E X , Y , σ c ∈ B X , Y max k 1 i = 1 ∑ k σ i ( K c ) X i ≤ k 3 H . (18) Proof. We first bound the maximum. Fix X , Y , σ X,Y,\sigma X , Y , σ b v b_v b v v v v B X , Y \mathcal{B}_{X,Y} B X , Y
b v : = p v + P X ( v ) + P Y ( v ) . b_v := p_v + P_X(v) + P_Y(v). b v := p v + P X ( v ) + P Y ( v ) . Since K K K c ∈ B X , Y c\in\mathcal{B}_{X,Y} c ∈ B X , Y
∣ ∑ i = 1 k σ i ( K c ) X i ∣ = ∣ ∑ v c v ∑ i σ i K v X i ∣ ≤ ∑ v b v ∣ ∑ i σ i K v X i ∣ . (19) \left|\sum_{i=1}^{k}\sigma_i(Kc)X_i\right| = \left|\sum_v c_v\sum_i\sigma_iK_{vX_i}\right| \le\sum_v b_v\left|\sum_i\sigma_iK_{vX_i}\right| . \tag*{(19)} i = 1 ∑ k σ i ( K c ) X i = v ∑ c v i ∑ σ i K v X i ≤ v ∑ b v i ∑ σ i K v X i . (19) Taking the maximum over c ∈ B X , Y c\in\mathcal{B}_{X,Y} c ∈ B X , Y b v b_v b v
max c ∈ B X , Y ∣ ∑ i = 1 k σ i ( K c ) X i ∣ ≤ ∑ v p v ∣ ∑ i σ i K v X i ∣ + ∑ v P X ( v ) ∣ ∑ i σ i K v X i ∣ + ∑ v P Y ( v ) ∣ ∑ i σ i K v X i ∣ . (20) \max_{c\in\mathcal{B}_{X,Y}}\left|\sum_{i=1}^{k}\sigma_i(Kc)X_i\right|\le\sum_v p_v\left|\sum_i\sigma_iK_{vX_i}\right|+\sum_v P_X(v)\left|\sum_i\sigma_iK_{vX_i}\right|+\sum_v P_Y(v)\left|\sum_i\sigma_iK_{vX_i}\right| . \tag*{(20)} c ∈ B X , Y max i = 1 ∑ k σ i ( K c ) X i ≤ v ∑ p v i ∑ σ i K v X i + v ∑ P X ( v ) i ∑ σ i K v X i + v ∑ P Y ( v ) i ∑ σ i K v X i . (20) We have bounded the maximum over all c c c P X P_X P X P Y P_Y P Y
Bound the sum weighted by p p p Since K K K H = ∑ v p v h v H=\sum_v p_vh_v H = ∑ v p v h v v ∈ V v\in V v ∈ V
h v : = ( ∑ u p u K v u 2 ) 1 / 2 . h_v:=\left(\sum_u p_uK_{vu}^{2}\right)^{1/2}. h v := ( u ∑ p u K v u 2 ) 1/2 . For fixed X X X L 1 L^1 L 1 Lemma A.2 ) gives
E σ ∣ ∑ i σ i K v X i ∣ ≤ ( ∑ i K v X i 2 ) 1 / 2 . \mathbb{E}_{\sigma}\left|\sum_i \sigma_i K_{vX_i}\right| \le\left(\sum_i K_{vX_i}^2\right)^{1/2}. E σ i ∑ σ i K v X i ≤ ( i ∑ K v X i 2 ) 1/2 . Taking expectation over X X X
E X , σ ∣ ∑ i σ i K v X i ∣ ≤ E X ( ∑ i K v X i 2 ) 1 / 2 ≤ ( ∑ i E X K v X i 2 ) 1 / 2 = k h v , \mathbb{E}_{X,\sigma}\left|\sum_i \sigma_i K_{vX_i}\right| \le\mathbb{E}_X\left(\sum_i K_{vX_i}^2\right)^{1/2} \le\left(\sum_i \mathbb{E}_X K_{vX_i}^2\right)^{1/2} = \sqrt{k}\,h_v, E X , σ i ∑ σ i K v X i ≤ E X ( i ∑ K v X i 2 ) 1/2 ≤ ( i ∑ E X K v X i 2 ) 1/2 = k h v , where the last equality uses E X K v X i 2 = ∑ u p u K v u 2 = h v 2 \mathbb{E}_X K_{vX_i}^2 = \sum_u p_u K_{vu}^2 = h_v^2 E X K v X i 2 = ∑ u p u K v u 2 = h v 2 X i X_i X i p p p
E X , σ ∑ v p v ∣ ∑ i σ i K v X i ∣ ≤ k ∑ v p v h v = k H . (21) \mathbb{E}_{X,\sigma}\sum_v p_v\left|\sum_i \sigma_i K_{vX_i}\right| \le\sqrt{k}\sum_v p_v h_v = \sqrt{k}\,H. \tag*{(21)} E X , σ v ∑ p v i ∑ σ i K v X i ≤ k v ∑ p v h v = k H . (21) Bound the sum weighted by P Y P_Y P Y We can use the preceding estimate directly for P Y P_Y P Y Y Y Y X X X σ \sigma σ E Y P Y ( v ) = p v \mathbb{E}_Y P_Y(v) = p_v E Y P Y ( v ) = p v
E X , Y , σ ∑ v P Y ( v ) ∣ ∑ i σ i K v X i ∣ = E X , σ ∑ v p v ∣ ∑ i σ i K v X i ∣ ≤ k H . (22) \mathbb{E}_{X,Y,\sigma}\sum_v P_Y(v)\left|\sum_i \sigma_i K_{vX_i}\right| = \mathbb{E}_{X,\sigma}\sum_v p_v\left|\sum_i \sigma_i K_{vX_i}\right| \le\sqrt{k}\,H. \tag*{(22)} E X , Y , σ v ∑ P Y ( v ) i ∑ σ i K v X i = E X , σ v ∑ p v i ∑ σ i K v X i ≤ k H . (22) Bound the sum weighted by P X P_X P X We can write the P X P_X P X
∑ v P X ( v ) ∣ ∑ i σ i K v X i ∣ = 1 k ∑ ℓ = 1 k ∣ ∑ i σ i K X ℓ X i ∣ . \sum_v P_X(v)\left|\sum_i \sigma_i K_{vX_i}\right| = \frac{1}{k}\sum_{\ell=1}^k\left|\sum_i \sigma_i K_{X_\ell X_i}\right|. v ∑ P X ( v ) i ∑ σ i K v X i = k 1 ℓ = 1 ∑ k i ∑ σ i K X ℓ X i . Fix ℓ \ell ℓ X ℓ = u X_\ell= u X ℓ = u K u u = 0 K_{uu} = 0 K uu = 0 ∑ i σ i K X ℓ X i = ∑ i ≠ ℓ σ i K u X i \sum_i \sigma_i K_{X_\ell X_i} = \sum_{i\ne\ell} \sigma_i K_{uX_i} ∑ i σ i K X ℓ X i = ∑ i = ℓ σ i K u X i X i X_i X i p p p
E X , σ [ ∣ ∑ i σ i K X ℓ X i ∣ | X ℓ = u ] ≤ E X [ ( ∑ i ≠ ℓ K u X i 2 ) 1 / 2 | X ℓ = u ] ≤ ( ( k − 1 ) h u 2 ) 1 / 2 = k − 1 h u . \begin{aligned}
\mathbb{E}_{X,\sigma}\left[\left|\sum_i \sigma_i K_{X_\ell X_i}\right|\middle|X_\ell=u\right] \le\mathbb{E}_X\left[\left(\sum_{i\ne\ell} K_{uX_i}^2\right)^{1/2}\middle|X_\ell=u\right] \\
&\le\left((k-1)h_u^2\right)^{1/2} = \sqrt{k-1}\,h_u.
\end{aligned} E X , σ [ i ∑ σ i K X ℓ X i X ℓ = u ] ≤ E X i = ℓ ∑ K u X i 2 1/2 X ℓ = u ≤ ( ( k − 1 ) h u 2 ) 1/2 = k − 1 h u . We remove the conditioning on X ℓ = u X_\ell=u X ℓ = u ℓ \ell ℓ k k k H = ∑ u p u h u H=\sum_u p_u h_u H = ∑ u p u h u
E X , σ ∑ v P X ( v ) ∣ ∑ i σ i K v X i ∣ ≤ k − 1 ∑ u p u h u = k − 1 H ≤ k H . (23) \mathbb{E}_{X,\sigma}\sum_v P_X(v)\left|\sum_i \sigma_i K_{vX_i}\right| \le\sqrt{k-1}\sum_u p_u h_u = \sqrt{k-1}\,H \le\sqrt{k}\,H. \tag*{(23)} E X , σ v ∑ P X ( v ) i ∑ σ i K v X i ≤ k − 1 u ∑ p u h u = k − 1 H ≤ k H . (23) Each of the three unnormalized sums has expected value at most k H \sqrt{k}\,H k H k k k 3 H / k 3H/\sqrt{k} 3 H / k
Putting it together
Theorem 2.9 (Expected error in F K F_K F K X 1 , … , X k X_1,\ldots,X_k X 1 , … , X k p p p P X P_X P X
E X ∣ F K ( P X ) − F K ( p ) ∣ ≤ 48 H k . (24) \mathbb{E}_X\left|F_K(P_X)-F_K(p)\right| \le\frac{48H}{\sqrt{k}}. \tag*{(24)} E X ∣ F K ( P X ) − F K ( p ) ∣ ≤ k 48 H . (24) Proof. Taking expectations in Lemma 2.5 with r = p r=p r = p s = P X s=P_X s = P X Lemmas 2.7 and 2.8 , gives
E X ∣ F K ( P X ) − F K ( p ) ∣ ≤ 4 E X Δ K ( p , P X ) ≤ 4 ⋅ 4 ⋅ 3 H k = 48 H k . \mathbb{E}_X\left|F_K(P_X)-F_K(p)\right| \le4\mathbb{E}_X\Delta_K(p,P_X) \le4\cdot4\cdot\frac{3H}{\sqrt{k}}=\frac{48H}{\sqrt{k}}. E X ∣ F K ( P X ) − F K ( p ) ∣ ≤ 4 E X Δ K ( p , P X ) ≤ 4 ⋅ 4 ⋅ k 3 H = k 48 H . Bound H H H
The sampling probabilities determine H H H d ( v ) / p v d(v)/p_v d ( v ) / p v H H H
Lemma 2.10 (Bounding H H H p ∈ R V p\in\mathbb{R}^V p ∈ R V K K K H H H 0 ≤ A u v ≤ 1 0\le A_{uv}\le1 0 ≤ A uv ≤ 1 u , v ∈ V u,v\in V u , v ∈ V
H 2 ≤ 1 n 3 ∑ v ∈ V d ( v ) p v . (25) H^2\le\frac{1}{n^3}\sum_{v\in V}\frac{d(v)}{p_v}. \tag*{(25)} H 2 ≤ n 3 1 v ∈ V ∑ p v d ( v ) . (25) In particular, if p v ≥ d ( v ) / n 2 p_v\ge d(v)/n^2 p v ≥ d ( v ) / n 2 v ∈ V v\in V v ∈ V H ≤ 1 H\le1 H ≤ 1
Proof. Substituting the definition of K K K H H H
H = 1 n 2 ∑ v ∈ V ( ∑ u ∈ V A u v 2 p u ) 1 / 2 . (26) H=\frac{1}{n^2}\sum_{v\in V}\left(\sum_{u\in V}\frac{A_{uv}^2}{p_u}\right)^{1/2}. \tag*{(26)} H = n 2 1 v ∈ V ∑ ( u ∈ V ∑ p u A uv 2 ) 1/2 . (26) Jensen’s inequality and A u v 2 ≤ A u v A_{uv}^2\le A_{uv} A uv 2 ≤ A uv
H 2 ≤ 1 n 3 ∑ u , v ∈ V A u v 2 p u ≤ 1 n 3 ∑ u ∈ V d ( u ) p u . H^2\le\frac{1}{n^3}\sum_{u,v\in V}\frac{A_{uv}^2}{p_u}\le\frac{1}{n^3}\sum_{u\in V}\frac{d(u)}{p_u}. H 2 ≤ n 3 1 u , v ∈ V ∑ p u A uv 2 ≤ n 3 1 u ∈ V ∑ p u d ( u ) . If p v ≥ d ( v ) / n 2 p_v\ge d(v)/n^2 p v ≥ d ( v ) / n 2 v ∈ V v\in V v ∈ V H 2 ≤ n − 3 ⋅ n ⋅ n 2 = 1 H^2\le n^{-3}\cdot n\cdot n^2=1 H 2 ≤ n − 3 ⋅ n ⋅ n 2 = 1
Uniform and exact importance sampling both satisfy p v ≥ d ( v ) / n 2 p_v\ge d(v)/n^2 p v ≥ d ( v ) / n 2 p v = d ( v ) / D p_v=d(v)/D p v = d ( v ) / D D ≤ n 2 D\le n^2 D ≤ n 2 p v = 1 / n p_v=1/n p v = 1/ n d ( v ) ≤ n d(v)\le n d ( v ) ≤ n H ≤ 1 H\le1 H ≤ 1
Keeping the dependence on D D D Theorem 2.10 gives a relative-error bound in terms of the average weighted degree.
Corollary 2.11 (Relative error from average weighted degree). Assume 0 ≤ A u v ≤ 1 0\le A_{uv}\le1 0 ≤ A uv ≤ 1 u , v ∈ V u,v\in V u , v ∈ V d ˉ = D / n > 0 \bar d=D/n>0 d ˉ = D / n > 0 O P T = MaxCut ( A ) \mathrm{OPT}=\operatorname{MaxCut}(A) OPT = MaxCut ( A ) p p p
∑ v ∈ V d ( v ) p v ≤ λ n D \sum_{v\in V}\frac{d(v)}{p_v}\le\lambda nD v ∈ V ∑ p v d ( v ) ≤ λn D for some λ ≥ 1 \lambda\ge1 λ ≥ 1
E ∣ MaxCut ( A ^ ) − O P T ∣ ≤ 192 λ n d ˉ k O P T . \mathbb{E}\left|\operatorname{MaxCut}(\widehat A)-\mathrm{OPT}\right|\le192\sqrt{\frac{\lambda n}{\bar d k}}\,\mathrm{OPT}. E MaxCut ( A ) − OPT ≤ 192 d ˉ k λn OPT . Proof. We first bound H H H Theorem 2.10 and the assumption on p p p
H 2 ≤ 1 n 3 ∑ v ∈ V d ( v ) p v ≤ λ D n 2 = λ d ˉ n . H^2 \le\frac{1}{n^3}\sum_{v\in V}\frac{d(v)}{p_v}\le\frac{\lambda D}{n^2}=\frac{\lambda\bar d}{n}. H 2 ≤ n 3 1 v ∈ V ∑ p v d ( v ) ≤ n 2 λ D = n λ d ˉ . A uniformly random cut has expected value D / 4 D/4 D /4 O P T ≥ n d ˉ / 4 \mathrm{OPT}\ge n\bar d/4 OPT ≥ n d ˉ /4 Theorem 2.1 gives
E ∣ MaxCut ( A ^ ) − O P T ∣ O P T ≤ 48 n 2 H O P T k ≤ 192 λ n d k . \frac{\mathbb{E}\lvert\operatorname{MaxCut}(\widehat{A})-\mathrm{OPT}\rvert}{\mathrm{OPT}}
\le\frac{48n^2H}{\mathrm{OPT}\sqrt{k}}\le192\sqrt{\frac{\lambda n}{d k}}. OPT E ∣ MaxCut ( A ) − OPT ∣ ≤ OPT k 48 n 2 H ≤ 192 d k λn . Importance sampling with parameter λ \lambda λ p v ≥ d ( v ) / ( λ D ) p_v\ge d(v)/(\lambda D) p v ≥ d ( v ) / ( λ D ) ∑ v d ( v ) / p v ≤ λ n D \sum_v d(v)/p_v\le\lambda nD ∑ v d ( v ) / p v ≤ λn D ∑ v d ( v ) / p v = n D \sum_v d(v)/p_v=nD ∑ v d ( v ) / p v = n D 0 < ε < 1 0<\varepsilon<1 0 < ε < 1 k ≥ 576 2 λ n / ( d ˉ ε 2 ) k\ge576^2\lambda n/(\bar d\varepsilon^2) k ≥ 57 6 2 λn / ( d ˉ ε 2 ) ( 1 ± ε ) (1\pm\varepsilon) ( 1 ± ε ) O P T \mathrm{OPT} OPT 2 / 3 2/3 2/3
For metric weights, importance sampling gives an error bound relative to the optimal cut value. For λ \lambda λ λ \sqrt{\lambda} λ
Corollary 2.12 (Relative error for metric weights). Assume A u v ≥ 0 A_{uv}\ge0 A uv ≥ 0 and A u v ≤ A u w + A w v A_{uv}\le A_{uw}+A_{wv} A uv ≤ A u w + A w v u , v , w ∈ V u,v,w\in V u , v , w ∈ V Use exact importance sampling p v = d ( v ) / D p_v=d(v)/D p v = d ( v ) / D and write O P T = MaxCut ( A ) \mathrm{OPT}=\operatorname{MaxCut}(A) OPT = MaxCut ( A ) Then
E ∣ MaxCut ( A ^ ) − O P T ∣ ≤ 192 2 k O P T . \mathbb{E}\lvert\operatorname{MaxCut}(\widehat{A})-\mathrm{OPT}\rvert\le\frac{192\sqrt{2}}{\sqrt{k}}\mathrm{OPT}. E ∣ MaxCut ( A ) − OPT ∣ ≤ k 192 2 OPT . Proof. Theorem 2.1 bounds the expected error by 48 n 2 H / k 48n^2H/\sqrt{k} 48 n 2 H / k n 2 H n^2H n 2 H O P T \mathrm{OPT} OPT v v v ∑ v p v = 1 \sum_v p_v=1 ∑ v p v = 1 p v = d ( v ) / D p_v=d(v)/D p v = d ( v ) / D
n 2 H = n 2 ∑ v p v ( p v ∑ u p u K u v 2 ) 1 / 2 ≤ n 2 ( ∑ u , v p u p v K u v 2 ) 1 / 2 = D ( ∑ u , v A u v 2 d ( u ) d ( v ) ) 1 / 2 ≤ 2 D . n^2H=n^2\sum_v\sqrt{p_v}\left(p_v\sum_u p_uK_{uv}^2\right)^{1/2}
\le n^2\left(\sum_{u,v}p_up_vK_{uv}^2\right)^{1/2}
=D\left(\sum_{u,v}\frac{A_{uv}^2}{d(u)d(v)}\right)^{1/2}
\le\sqrt{2}D. n 2 H = n 2 v ∑ p v ( p v u ∑ p u K uv 2 ) 1/2 ≤ n 2 ( u , v ∑ p u p v K uv 2 ) 1/2 = D ( u , v ∑ d ( u ) d ( v ) A uv 2 ) 1/2 ≤ 2 D . The last inequality follows from the next calculation. For fixed u , v u,v u , v A u v ≤ A u w + A w v A_{uv}\le A_{uw}+A_{wv} A uv ≤ A u w + A w v n n n w ∈ V w\in V w ∈ V
n A u v ≤ ∑ w ∈ V A u w + ∑ w ∈ V A w v = d ( u ) + d ( v ) . nA_{uv}\le\sum_{w\in V}A_{uw}+\sum_{w\in V}A_{wv}=d(u)+d(v). n A uv ≤ w ∈ V ∑ A u w + w ∈ V ∑ A w v = d ( u ) + d ( v ) . Multiply the preceding inequality by 1 n A u v / ( d ( u ) d ( v ) ) \frac{1}{n}A_{uv}/(d(u)d(v)) n 1 A uv / ( d ( u ) d ( v )) u , v u,v u , v
∑ u , v ∈ V A u v 2 d ( u ) d ( v ) ≤ 1 n ( ∑ u , v ∈ V A u v d ( u ) + ∑ u , v ∈ V A u v d ( v ) ) = 2. \sum_{u,v\in V}\frac{A_{uv}^2}{d(u)d(v)}
\le\frac{1}{n}\left(\sum_{u,v\in V}\frac{A_{uv}}{d(u)}+\sum_{u,v\in V}\frac{A_{uv}}{d(v)}\right)=2. u , v ∈ V ∑ d ( u ) d ( v ) A uv 2 ≤ n 1 u , v ∈ V ∑ d ( u ) A uv + u , v ∈ V ∑ d ( v ) A uv = 2. Each vertex contributes 1 1 1
∑ u , v ∈ V A u v d ( u ) = ∑ u ∈ V ∑ v ∈ V A u v d ( u ) = ∑ u ∈ V 1 = n . \sum_{u,v\in V}\frac{A_{uv}}{d(u)}
=\sum_{u\in V}\frac{\sum_{v\in V}A_{uv}}{d(u)}
=\sum_{u\in V}1=n. u , v ∈ V ∑ d ( u ) A uv = u ∈ V ∑ d ( u ) ∑ v ∈ V A uv = u ∈ V ∑ 1 = n . The second sum also equals n n n D / 4 D/4 D /4 D ≤ 4 O P T D\le4\mathrm{OPT} D ≤ 4 OPT n 2 H ≤ 4 2 O P T n^2H\le4\sqrt{2}\,\mathrm{OPT} n 2 H ≤ 4 2 OPT
Solution Recovery for Max-Cut
We recover a nearly optimal cut of A A A A ^ \widehat{A} A Cut A ( S ) \operatorname{Cut}_{A}(S) Cut A ( S ) S ⊆ V S \subseteq V S ⊆ V
The same quantity H H H H ≤ 1 H \le1 H ≤ 1 A u v A_{uv} A uv [ 0 , 1 ] [0,1] [ 0 , 1 ] (2) .
Theorem 3.1 (Recovery from edges to the sampled vertices). For every positive probability vector p ∈ R V p \in\mathbb{R}^{V} p ∈ R V k ≥ 1 k \ge1 k ≥ 1 A ^ \widehat{A} A X 1 , … , X k X_1,\ldots,X_k X 1 , … , X k S ⊆ V S \subseteq V S ⊆ V
E [ MaxCut ( A ) − Cut A ( S ) n 2 ] ≤ 120 H k . (27) \mathbb{E}\left[\frac{\operatorname{MaxCut}(A)-\operatorname{Cut}_{A}(S)}{n^2}\right] \le\frac{120H}{\sqrt{k}}. \tag*{(27)} E [ n 2 MaxCut ( A ) − Cut A ( S ) ] ≤ k 120 H . (27) The expectation is over both sampling and rounding. The algorithm uses at most n k nk nk
The query bound assumes access to the probabilities p v p_v p v p p p
Corollary 3.2 (High-probability bound). Assume 0 ≤ A u v ≤ 1 0 \le A_{uv} \le1 0 ≤ A uv ≤ 1 u , v ∈ V u,v \in V u , v ∈ V (2) , including uniform and importance sampling with λ = 1 \lambda=1 λ = 1
∀ 0 < ε < 1 , P ( MaxCut ( A ) − Cut A ( S ) ≥ ε n 2 ) ≤ 120 ε k . (28) \forall\,0<\varepsilon<1,\quad\mathbb{P}\left(\operatorname{MaxCut}(A)-\operatorname{Cut}_{A}(S)\ge\varepsilon n^2\right)\le\frac{120}{\varepsilon\sqrt{k}}. \tag*{(28)} ∀ 0 < ε < 1 , P ( MaxCut ( A ) − Cut A ( S ) ≥ ε n 2 ) ≤ ε k 120 . (28) The probability is over both sampling and rounding. Consequently, to get error probability at most δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) k ≥ 14400 / ( δ 2 ε 2 ) k \ge14400/(\delta^2\varepsilon^2) k ≥ 14400/ ( δ 2 ε 2 )
Proof. Lemma 2.10 gives H ≤ 1 H \le1 H ≤ 1 MaxCut ( A ) − Cut A ( S ) ≥ 0 \operatorname{MaxCut}(A)-\operatorname{Cut}_{A}(S)\ge0 MaxCut ( A ) − Cut A ( S ) ≥ 0 (27) gives (28) . Solving for k k k δ \delta δ
Under the same bounded-weight assumption, importance sampling with parameter λ ≥ 1 \lambda\ge1 λ ≥ 1 H ≤ λ H \le\sqrt{\lambda} H ≤ λ λ \lambda λ
Overview. We first show how an optimal cut a a a b b b b b b a a a
Recover a fractional cut by a linear program
Write Δ = Δ K ( p , P X ) \Delta=\Delta_K(p,P_X) Δ = Δ K ( p , P X )
Lemma 3.3 (Comparison using edges to the sampled vertices). Let a ∈ Z ( P X ) a \in Z(P_X) a ∈ Z ( P X ) b ∈ Z ( p ) b \in Z(p) b ∈ Z ( p )
b T K ( p − b ) ≥ F K ( P X ) − 4 Δ − 1 k ∑ i = 1 k ∣ ( K a ) X i − ( K b ) X i ∣ . (29) b^{\mathsf{T}}K(p-b) \ge F_K(P_X)-4\Delta-\frac{1}{k}\sum_{i=1}^{k}\left|(Ka)_{X_i}-(Kb)_{X_i}\right|. \tag*{(29)} b T K ( p − b ) ≥ F K ( P X ) − 4Δ − k 1 i = 1 ∑ k ∣ ( K a ) X i − ( K b ) X i ∣ . (29) Proof. Fix b ∈ Z ( p ) b \in Z(p) b ∈ Z ( p ) b X ∈ Z ( P X ) b_X \in Z(P_X) b X ∈ Z ( P X ) Lemma 2.6 . We first bound the two error terms that arise when replacing b b b b X b_X b X p p p P X P_X P X a , b ∈ C ( p , P X ) a,b \in C(p,P_X) a , b ∈ C ( p , P X ) K = K ⊤ K=K^{\top} K = K ⊤
∣ ( a − b ) ⊤ K ( b − b X ) ∣ ≤ ∣ ( b − b X ) ⊤ K a ∣ + ∣ ( b − b X ) ⊤ K b ∣ ≤ 2 Δ , \left|(a-b)^{\top}K(b-b_X)\right| \leq\left|(b-b_X)^{\top}Ka\right|+\left|(b-b_X)^{\top}Kb\right| \leq2\Delta, ( a − b ) ⊤ K ( b − b X ) ≤ ( b − b X ) ⊤ K a + ( b − b X ) ⊤ K b ≤ 2Δ , ∣ ( P X − p ) ⊤ K b ∣ ≤ 2 Δ . \left|(P_X-p)^{\top}Kb\right| \leq2\Delta. ( P X − p ) ⊤ K b ≤ 2Δ. Since a a a F K ( P X ) F_K(P_X) F K ( P X ) b X b_X b X
F K ( P X ) − b ⊤ K ( p − b ) = ( a − b ) ⊤ K ( P X − a − b ) + ( P X − p ) ⊤ K b = ( a − b ) ⊤ K ( P X − a − b X ) − ( a − b ) ⊤ K ( b − b X ) + ( P X − p ) ⊤ K b ≤ ( a − b ) ⊤ K ( P X − a − b X ) + 4 Δ . \begin{aligned}
F_K(P_X)-b^{\top}K(p-b)=(a-b)^{\top}K(P_X-a-b)+(P_X-p)^{\top}Kb \\
&=(a-b)^{\top}K(P_X-a-b_X)-(a-b)^{\top}K(b-b_X)+(P_X-p)^{\top}Kb \\
&\leq(a-b)^{\top}K(P_X-a-b_X)+4\Delta.
\end{aligned} F K ( P X ) − b ⊤ K ( p − b ) = ( a − b ) ⊤ K ( P X − a − b ) + ( P X − p ) ⊤ K b = ( a − b ) ⊤ K ( P X − a − b X ) − ( a − b ) ⊤ K ( b − b X ) + ( P X − p ) ⊤ K b ≤ ( a − b ) ⊤ K ( P X − a − b X ) + 4Δ. It remains to bound the first term using edges to the sampled vertices. Since a , b X ∈ Z ( P X ) a,b_X \in Z(P_X) a , b X ∈ Z ( P X ) − P X ≤ P X − a − b X ≤ P X -P_X \leq P_X-a-b_X \leq P_X − P X ≤ P X − a − b X ≤ P X K K K
( a − b ) ⊤ K ( P X − a − b X ) ≤ ∑ v P X ( v ) ∣ ( K a ) v − ( K b ) v ∣ = 1 k ∑ i = 1 k ∣ ( K a ) X i − ( K b ) X i ∣ . (a-b)^{\top}K(P_X-a-b_X)\leq\sum_v P_X(v)\left|(Ka)_v-(Kb)_v\right|=\frac{1}{k}\sum_{i=1}^{k}\left|(Ka)_{X_i}-(Kb)_{X_i}\right|. ( a − b ) ⊤ K ( P X − a − b X ) ≤ v ∑ P X ( v ) ∣ ( K a ) v − ( K b ) v ∣ = k 1 i = 1 ∑ k ∣ ( K a ) X i − ( K b ) X i ∣ . Substituting this bound proves the claim.
Fix an optimal cut a a a (29) over b ∈ Z ( p ) b \in Z(p) b ∈ Z ( p )
Lemma 3.4 (Recovery by minimizing the error). Every b ∈ Z ( p ) b \in Z(p) b ∈ Z ( p )
1 k ∑ i = 1 k ∣ ( K a ) X i − ( K b ) X i ∣ (30) \frac{1}{k}\sum_{i=1}^{k}\left|(Ka)_{X_i}-(Kb)_{X_i}\right| \tag*{(30)} k 1 i = 1 ∑ k ∣ ( K a ) X i − ( K b ) X i ∣ (30) satisfies
b ⊤ K ( p − b ) ≥ F K ( p ) − 10 Δ . (31) b^{\top}K(p-b)\geq F_K(p)-10\Delta. \tag*{(31)} b ⊤ K ( p − b ) ≥ F K ( p ) − 10Δ. (31) Proof. Lemma 2.6 , with Z ( P X ) ⊆ C ( p , P X ) Z(P_X)\subseteq C(p,P_X) Z ( P X ) ⊆ C ( p , P X ) K = K ⊤ K=K^{\top} K = K ⊤ b ∈ Z ( p ) b \in Z(p) b ∈ Z ( p )
∣ w ⊤ K ( a − b ) ∣ ≤ Δ for every w ∈ Z ( P X ) . \left|w^{\top}K(a-b)\right|\leq\Delta\qquad\text{for every } w \in Z(P_X). w ⊤ K ( a − b ) ≤ Δ for every w ∈ Z ( P X ) . Thus,
1 k ∑ i = 1 k ∣ ( K a ) X i − ( K b ) X i ∣ ≤ 2 max w ∈ Z ( P X ) ∣ w ⊤ K ( a − b ) ∣ ≤ 2 Δ . \frac{1}{k}\sum_{i=1}^{k}\left|(Ka)_{X_i}-(Kb)_{X_i}\right|\leq2\max_{w\in Z(P_X)}\left|w^{\top}K(a-b)\right|\leq2\Delta. k 1 i = 1 ∑ k ∣ ( K a ) X i − ( K b ) X i ∣ ≤ 2 w ∈ Z ( P X ) max w ⊤ K ( a − b ) ≤ 2Δ. For any minimizer b b b 2.5 give
b ⊤ K ( p − b ) ≥ F K ( P X ) − 4 Δ − 1 k ∑ i = 1 k ∣ ( K a ) X i − ( K b ) X i ∣ ≥ F K ( P X ) − 6 Δ ≥ F K ( p ) − 10 Δ . \begin{aligned}
b^{\top}K(p-b)\geq F_K(P_X)-4\Delta-\frac{1}{k}\sum_{i=1}^{k}\left|(Ka)_{X_i}-(Kb)_{X_i}\right| \\
&\geq F_K(P_X)-6\Delta\geq F_K(p)-10\Delta.
\end{aligned} b ⊤ K ( p − b ) ≥ F K ( P X ) − 4Δ − k 1 i = 1 ∑ k ∣ ( K a ) X i − ( K b ) X i ∣ ≥ F K ( P X ) − 6Δ ≥ F K ( p ) − 10Δ. We compute a minimizer by solving
min b , t 1 k ∑ i = 1 k t i \min_{b,t}\ \frac{1}{k}\sum_{i=1}^{k} t_i b , t min k 1 i = 1 ∑ k t i subject to 0 ≤ b ≤ p , t ≥ 0 , 0 \le b \le p,\quad t \ge0, 0 ≤ b ≤ p , t ≥ 0 ,
− t i ≤ ( K a ) X i − ( K b ) X i ≤ t i ( i = 1 , … , k ) . (32) -t_i \le(Ka)_{X_i}-(Kb)_{X_i} \le t_i\quad(i=1,\ldots,k). \tag*{(32)} − t i ≤ ( K a ) X i − ( K b ) X i ≤ t i ( i = 1 , … , k ) . (32) At any optimal solution ( b , t ) (b,t) ( b , t ) (32) , t i = ∣ ( K a ) X i − ( K b ) X i ∣ t_i=\left|(Ka)_{X_i}-(Kb)_{X_i}\right| t i = ∣ ( K a ) X i − ( K b ) X i ∣ i i i t i t_i t i b b b (30) and satisfies (31) by Lemma 3.4 .
Round the fractional cut and count queries
The LP assigns b v b_v b v v v v p v p_v p v v v v S S S b v / p v ∈ [ 0 , 1 ] b_v/p_v \in[0,1] b v / p v ∈ [ 0 , 1 ]
Proof of Theorem 3.1 . Condition on the sample X X X b b b A v v = 0 A_{vv}=0 A v v = 0 A u v = n 2 p u p v K u v A_{uv}=n^2p_up_vK_{uv} A uv = n 2 p u p v K uv (31) give
E [ Cut A ( S ) ∣ X , b ] = ∑ u ≠ v A u v P ( u ∈ S , v ∉ S ∣ X , b ) = ∑ u , v ∈ V A u v b u p u ( 1 − b v p v ) = n 2 b ⊤ K ( p − b ) ≥ n 2 F K ( p ) − 10 n 2 Δ . (33) \begin{aligned}
\mathbb{E}[\operatorname{Cut}_A(S)\mid X,b]
=\sum_{u\ne v}A_{uv}\mathbb{P}(u\in S,v\notin S\mid X,b) \\
&=\sum_{u,v\in V}A_{uv}\frac{b_u}{p_u}\left(1-\frac{b_v}{p_v}\right) \\
&=n^2b^\top K(p-b)\ge n^2F_K(p)-10n^2\Delta. \tag*{(33)}
\end{aligned} E [ Cut A ( S ) ∣ X , b ] = u = v ∑ A uv P ( u ∈ S , v ∈ / S ∣ X , b ) = u , v ∈ V ∑ A uv p u b u ( 1 − p v b v ) = n 2 b ⊤ K ( p − b ) ≥ n 2 F K ( p ) − 10 n 2 Δ. (33) This bound holds for every optimal b b b X X X (14) gives
E [ MaxCut ( A ) − Cut A ( S ) n 2 ] ≤ 10 E X Δ ≤ 120 H k . \mathbb{E}\left[\frac{\operatorname{MaxCut}(A)-\operatorname{Cut}_A(S)}{n^2}\right]\le10\mathbb{E}_X\Delta\le\frac{120H}{\sqrt{k}}. E [ n 2 MaxCut ( A ) − Cut A ( S ) ] ≤ 10 E X Δ ≤ k 120 H . The edges to the sampled vertices determine A ^ \widehat{A} A n k nk nk
Lower Bound
We prove a matching Ω ( ε − 2 ) \Omega(\varepsilon^{-2}) Ω ( ε − 2 ) MaxCut ( A ^ ) \operatorname{MaxCut}(\widehat{A}) MaxCut ( A ) (1) . The main example is a balanced complete tripartite graph. An imbalance of order k \sqrt{k} k n 2 / k n^2/\sqrt{k} n 2 / k
For every positive integer n n n
B n = K n / 2 , n / 2 , T n = K n / 3 , n / 3 , n / 3 , G n , k = { B n , 1 ≤ k < 512 , T n , k ≥ 512. B_n=K_{n/2,n/2},\qquad T_n=K_{n/3,n/3,n/3},\qquad
G_{n,k}=
\begin{cases}
B_n, & 1\le k<512,\\
T_n, & k\ge512.
\end{cases} B n = K n /2 , n /2 , T n = K n /3 , n /3 , n /3 , G n , k = { B n , T n , 1 ≤ k < 512 , k ≥ 512. Both graphs are simple, unweighted, and regular, so importance sampling uses p v = d ( v ) / D = 1 / n p_v=d(v)/D=1/n p v = d ( v ) / D = 1/ n (1) , every edge in the sampled graph has weight n 2 / k 2 n^2/k^2 n 2 / k 2 k < 512 k<512 k < 512
Theorem 4.1 (Lower bound for importance sampling). Set c = 1 / 5184 c = 1/5184 c = 1/5184 ε 0 = 1 / ( 4 ⋅ 512 2 ) \varepsilon_0 = 1/(4 \cdot512^2) ε 0 = 1/ ( 4 ⋅ 51 2 2 ) 0 < ε ≤ ε 0 0 < \varepsilon\le\varepsilon_0 0 < ε ≤ ε 0 1 ≤ k ≤ c ε − 2 1 \le k \le c\varepsilon^{-2} 1 ≤ k ≤ c ε − 2 n n n G n , k G_{n,k} G n , k
P ( ∣ MaxCut ( A ^ ) − MaxCut ( A ) ∣ > ε n 2 ) > 3 8 . \mathbb{P}\left(\left|\operatorname{MaxCut}(\widehat{A})-\operatorname{MaxCut}(A)\right|>\varepsilon n^2\right)>\frac{3}{8}. P ( MaxCut ( A ) − MaxCut ( A ) > ε n 2 ) > 8 3 . Thus, for this estimator under importance sampling, a worst-case guarantee of additive error ε n 2 \varepsilon n^2 ε n 2 2 / 3 2/3 2/3 k = Ω ( ε − 2 ) k=\Omega(\varepsilon^{-2}) k = Ω ( ε − 2 )
Proof. We first express the error on the tripartite graph in terms of its sample counts. Lemma 4.2 then gives the required probability bound. We handle k < 512 k < 512 k < 512
Compute the estimator on the tripartite graph. Suppose first that k ≥ 512 k \ge512 k ≥ 512 G n , k = T n G_{n,k}=T_n G n , k = T n N j N_j N j j j j M M M
( N 1 , N 2 , N 3 ) ∼ Multinomial ( k ; 1 / 3 , 1 / 3 , 1 / 3 ) , M : = max j N j . (N_1,N_2,N_3)\sim\operatorname{Multinomial}(k;1/3,1/3,1/3),\qquad M:=\max_j N_j. ( N 1 , N 2 , N 3 ) ∼ Multinomial ( k ; 1/3 , 1/3 , 1/3 ) , M := j max N j . The sampled graph is complete tripartite with part sizes N 1 , N 2 , N 3 N_1,N_2,N_3 N 1 , N 2 , N 3
An optimal cut may be chosen to keep each part on one side. Indeed, vertices within a part have no edges between them and have identical neighborhoods. Holding the other parts fixed, we can therefore move all vertices of this part to whichever side gives the larger contribution, without decreasing the cut value. Among cuts that split no part, an optimal cut separates the largest part from the other two, leaving only the edges between the two smallest parts uncut.
An optimal cut of the sampled graph therefore has M ( k − M ) M(k-M) M ( k − M ) n / 3 n/3 n /3 ( n / 3 ) ( 2 n / 3 ) = 2 n 2 / 9 (n/3)(2n/3)=2n^2/9 ( n /3 ) ( 2 n /3 ) = 2 n 2 /9
MaxCut ( A ) = 2 n 2 9 , MaxCut ( A ^ ) = n 2 k 2 M ( k − M ) . (34) \operatorname{MaxCut}(A)=\frac{2n^2}{9},\qquad\operatorname{MaxCut}(\widehat{A})=\frac{n^2}{k^2}M(k-M). \tag*{(34)} MaxCut ( A ) = 9 2 n 2 , MaxCut ( A ) = k 2 n 2 M ( k − M ) . (34) To compare these values, let L : = M − k / 3 ≥ 0 L:=M-k/3\ge0 L := M − k /3 ≥ 0 k / 3 k/3 k /3 M = k / 3 + L M=k/3+L M = k /3 + L
MaxCut ( A ^ ) − MaxCut ( A ) n 2 = M ( k − M ) k 2 − 2 9 = L 3 k − L 2 k 2 . (35) \frac{\operatorname{MaxCut}(\widehat{A})-\operatorname{MaxCut}(A)}{n^2}
=\frac{M(k-M)}{k^2}-\frac{2}{9}
=\frac{L}{3k}-\frac{L^2}{k^2}. \tag*{(35)} n 2 MaxCut ( A ) − MaxCut ( A ) = k 2 M ( k − M ) − 9 2 = 3 k L − k 2 L 2 . (35) Identify an event on which the estimator fails. When L ≤ k / 6 L\le k/6 L ≤ k /6 (35) is at most half the linear term. Thus an imbalance of order k \sqrt{k} k n 2 / k n^2/\sqrt{k} n 2 / k
k 12 < L ≤ k 6 , \frac{\sqrt{k}}{12}<L\le\frac{k}{6}, 12 k < L ≤ 6 k , equation (35) gives
MaxCut ( A ^ ) − MaxCut ( A ) = n 2 L k ( 1 3 − L k ) ≥ n 2 L 6 k > n 2 72 k ≥ ε n 2 . (36) \operatorname{MaxCut}(\widehat{A})-\operatorname{MaxCut}(A)
=\frac{n^2L}{k}\left(\frac{1}{3}-\frac{L}{k}\right)
\ge\frac{n^2L}{6k}
>\frac{n^2}{72\sqrt{k}}\ge\varepsilon n^2. \tag*{(36)} MaxCut ( A ) − MaxCut ( A ) = k n 2 L ( 3 1 − k L ) ≥ 6 k n 2 L > 72 k n 2 ≥ ε n 2 . (36) The last inequality uses k ≤ 1 / ( 5184 ε 2 ) k\le1/(5184\varepsilon^2) k ≤ 1/ ( 5184 ε 2 ) 3 / 8 3/8 3/8 k ≥ 512 k\ge512 k ≥ 512
Cover the smaller sample sizes. For 1 ≤ k < 512 1 \le k < 512 1 ≤ k < 512 B n B_n B n
Let B ∼ Bin ( k , 1 / 2 ) B \sim\operatorname{Bin}(k,1/2) B ∼ Bin ( k , 1/2 ) B B B k − B k-B k − B
MaxCut ( A ) = n 2 4 , MaxCut ( A ^ ) = n 2 k 2 B ( k − B ) . \operatorname{MaxCut}(A)=\frac{n^2}{4}, \qquad\operatorname{MaxCut}(\widehat{A})=\frac{n^2}{k^2}B(k-B). MaxCut ( A ) = 4 n 2 , MaxCut ( A ) = k 2 n 2 B ( k − B ) . The error is therefore determined by the difference between the two sample counts:
∣ MaxCut ( A ^ ) − MaxCut ( A ) ∣ n 2 = 1 4 − B ( k − B ) k 2 = ( 2 B − k ) 2 4 k 2 . \frac{\left|\operatorname{MaxCut}(\widehat{A})-\operatorname{MaxCut}(A)\right|}{n^2}
=\frac{1}{4}-\frac{B(k-B)}{k^2}
=\frac{(2B-k)^2}{4k^2}. n 2 MaxCut ( A ) − MaxCut ( A ) = 4 1 − k 2 B ( k − B ) = 4 k 2 ( 2 B − k ) 2 . If B ≠ k / 2 B \ne k/2 B = k /2 2 B − k 2B-k 2 B − k
∣ MaxCut ( A ^ ) − MaxCut ( A ) ∣ n 2 ≥ 1 4 k 2 ≥ 1 4 ⋅ 512 2 = ε 0 ≥ ε . \frac{\left|\operatorname{MaxCut}(\widehat{A})-\operatorname{MaxCut}(A)\right|}{n^2}
\ge\frac{1}{4k^2} \ge\frac{1}{4\cdot512^2}=\varepsilon_0\ge\varepsilon. n 2 MaxCut ( A ) − MaxCut ( A ) ≥ 4 k 2 1 ≥ 4 ⋅ 51 2 2 1 = ε 0 ≥ ε . The final sample belongs to either part with equal probability, and at most one of these two choices makes the counts equal. Hence P ( B = k / 2 ) ≤ 1 / 2 \mathbb{P}(B=k/2)\le1/2 P ( B = k /2 ) ≤ 1/2 1 / 2 > 3 / 8 1/2>3/8 1/2 > 3/8
Lemma 4.2 (Imbalance among three sample counts). Let ( N 1 , N 2 , N 3 ) (N_1,N_2,N_3) ( N 1 , N 2 , N 3 ) ( k ; 1 / 3 , 1 / 3 , 1 / 3 ) (k;1/3,1/3,1/3) ( k ; 1/3 , 1/3 , 1/3 ) M : = max j N j M:=\max_j N_j M := max j N j L : = M − k / 3 L:=M-k/3 L := M − k /3 k ≥ 512 k\ge512 k ≥ 512
P ( k 12 < L ≤ k 6 ) > 3 8 . (37) \mathbb{P}\left(\frac{\sqrt{k}}{12}<L\le\frac{k}{6}\right)>\frac{3}{8}. \tag*{(37)} P ( 12 k < L ≤ 6 k ) > 8 3 . (37) Proof. We first bound the probability that L > k / 12 L>\sqrt{k}/12 L > k /12 L > k / 6 L>k/6 L > k /6
R : = ∑ j = 1 3 ( N j − k / 3 ) 2 . R:=\sum_{j=1}^{3}(N_j-k/3)^2. R := j = 1 ∑ 3 ( N j − k /3 ) 2 . The advantage of R R R
Bound R R R L L L For this comparison, label the parts so that N 1 = M = k / 3 + L N_1=M=k/3+L N 1 = M = k /3 + L R R R L 2 L^2 L 2 R ≥ L 2 R\ge L^2 R ≥ L 2 N 2 + N 3 = k − M N_2+N_3=k-M N 2 + N 3 = k − M
R = 6 L 2 − 2 ( M − N 2 ) ( M − N 3 ) ≤ 6 L 2 , R=6L^2-2(M-N_2)(M-N_3)\le6L^2, R = 6 L 2 − 2 ( M − N 2 ) ( M − N 3 ) ≤ 6 L 2 , since both factors in the product are nonnegative.
Compute the first two moments. For $1 \le a < b \le k$, let I a b I_{ab} I ab a a a b b b j j j ( N j 2 ) \binom{N_j}{2} ( 2 N j ) ∑ j ( N j 2 ) = ∑ a < b I a b \sum_j \binom{N_j}{2} = \sum_{a<b} I_{ab} ∑ j ( 2 N j ) = ∑ a < b I ab N j 2 = N j + 2 ( N j 2 ) N_j^2 = N_j + 2\binom{N_j}{2} N j 2 = N j + 2 ( 2 N j ) ∑ j N j = k \sum_j N_j = k ∑ j N j = k
R = ∑ j = 1 3 N j 2 − k 2 3 = k + 2 ∑ a < b I a b − k 2 3 . R = \sum_{j=1}^{3} N_j^2 - \frac{k^2}{3} = k + 2\sum_{a<b} I_{ab} - \frac{k^2}{3}. R = j = 1 ∑ 3 N j 2 − 3 k 2 = k + 2 a < b ∑ I ab − 3 k 2 . Each indicator has mean 1 / 3 1/3 1/3 2 / 9 2/9 2/9
P ( I a b = I a c = 1 ) = 3 ( 1 3 ) 3 = 1 9 = P ( I a b = 1 ) P ( I a c = 1 ) . \mathbb{P}(I_{ab}=I_{ac}=1) = 3\left(\frac{1}{3}\right)^3 = \frac{1}{9} = \mathbb{P}(I_{ab}=1)\mathbb{P}(I_{ac}=1). P ( I ab = I a c = 1 ) = 3 ( 3 1 ) 3 = 9 1 = P ( I ab = 1 ) P ( I a c = 1 ) . We can therefore compute both the mean and variance of R R R
E R = k + 2 ( k 2 ) 1 3 − k 2 3 = 2 k 3 , \mathbb{E}R = k + 2\binom{k}{2}\frac{1}{3} - \frac{k^2}{3} = \frac{2k}{3}, E R = k + 2 ( 2 k ) 3 1 − 3 k 2 = 3 2 k , Var ( R ) = 4 ( k 2 ) 2 9 = 4 k ( k − 1 ) 9 . \operatorname{Var}(R) = 4\binom{k}{2}\frac{2}{9} = \frac{4k(k-1)}{9}. Var ( R ) = 4 ( 2 k ) 9 2 = 9 4 k ( k − 1 ) . In particular,
E R 2 = ( E R ) 2 + Var ( R ) = 4 k 2 9 + 4 k ( k − 1 ) 9 ≤ 8 k 2 9 . (38) \begin{aligned}
\mathbb{E}R^2 = (\mathbb{E}R)^2 + \operatorname{Var}(R) \\
&= \frac{4k^2}{9} + \frac{4k(k-1)}{9} \le\frac{8k^2}{9}. \tag*{(38)}
\end{aligned} E R 2 = ( E R ) 2 + Var ( R ) = 9 4 k 2 + 9 4 k ( k − 1 ) ≤ 9 8 k 2 . (38) Bound the probability of the required imbalance. Since R ≤ 6 L 2 R \le6L^2 R ≤ 6 L 2 R > k / 24 R > k/24 R > k /24 L > k / 12 L > \sqrt{k}/12 L > k /12 R R R k / 24 k/24 k /24 R ≤ k / 24 R \le k/24 R ≤ k /24 k / 24 k/24 k /24
E R = E [ R 1 { R ≤ k / 24 } ] + E [ R 1 { R > k / 24 } ] ≤ k 24 + E R 2 P ( R > k / 24 ) . \begin{aligned}
\mathbb{E}R = \mathbb{E}[R1_{\{R\le k/24\}}] + \mathbb{E}[R1_{\{R>k/24\}}] \\
&\le\frac{k}{24} + \sqrt{\mathbb{E}R^2\,\mathbb{P}(R>k/24)}.
\end{aligned} E R = E [ R 1 { R ≤ k /24 } ] + E [ R 1 { R > k /24 } ] ≤ 24 k + E R 2 P ( R > k /24 ) . Isolating P ( R > k / 24 ) \mathbb{P}(R > k/24) P ( R > k /24 )
P ( L > k / 12 ) ≥ P ( R > k / 24 ) ≥ ( E R − k / 24 ) 2 E R 2 ≥ ( 2 k / 3 − k / 24 ) 2 8 k 2 / 9 = 225 512 . \begin{aligned}
\mathbb{P}(L > \sqrt{k}/12) \ge\mathbb{P}(R > k/24) \ge\frac{(\mathbb{E}R-k/24)^2}{\mathbb{E}R^2} \\
&\ge\frac{(2k/3-k/24)^2}{8k^2/9} = \frac{225}{512}.
\end{aligned} P ( L > k /12 ) ≥ P ( R > k /24 ) ≥ E R 2 ( E R − k /24 ) 2 ≥ 8 k 2 /9 ( 2 k /3 − k /24 ) 2 = 512 225 . We now bound the probability that the imbalance is too large. If L > k / 6 L > k/6 L > k /6 R ≥ L 2 > k 2 / 36 R \ge L^2 > k^2/36 R ≥ L 2 > k 2 /36
P ( L > k / 6 ) ≤ P ( R > k 2 / 36 ) ≤ E R k 2 / 36 = 24 k . \mathbb{P}(L > k/6) \le\mathbb{P}(R > k^2/36) \le\frac{\mathbb{E}R}{k^2/36} = \frac{24}{k}. P ( L > k /6 ) ≤ P ( R > k 2 /36 ) ≤ k 2 /36 E R = k 24 . Subtracting this from the lower bound, and using k ≥ 512 k \ge512 k ≥ 512
P ( k 12 < L ≤ k 6 ) = P ( L > k / 12 ) − P ( L > k / 6 ) ≥ 225 512 − 24 k ≥ 201 512 > 3 8 . \begin{aligned}
\mathbb{P}\left(\frac{\sqrt{k}}{12} < L \le\frac{k}{6}\right) = \mathbb{P}(L > \sqrt{k}/12) - \mathbb{P}(L > k/6) \\
&\ge\frac{225}{512} - \frac{24}{k} \ge\frac{201}{512} > \frac{3}{8}.
\end{aligned} P ( 12 k < L ≤ 6 k ) = P ( L > k /12 ) − P ( L > k /6 ) ≥ 512 225 − k 24 ≥ 512 201 > 8 3 . Sample Complexity for Max-r r r
In this section, we extend the sampling bound of § 2 to Max-r r r O ( ε − 2 log ( 2 r ) ) O(\varepsilon^{-2}\log(2r)) O ( ε − 2 log ( 2 r )) ε n 2 \varepsilon n^2 ε n 2 r r r Theorem 5.1 . We then give an overview of the proof (in § 6.1 ), which is followed by the proof itself: We express the two cut values through a common functional (in § 6.2 ), then reduce the comparison of these two cut values to the difference between two linear maximization problems (in § 6.3 ), and then bound the expectation of this difference (in § 6.4 ).
Let A ∈ R V × V A \in\mathbb{R}^{V \times V} A ∈ R V × V A u v ≥ 0 A_{uv} \ge0 A uv ≥ 0 u , v ∈ V u,v \in V u , v ∈ V d ( v ) > 0 d(v)>0 d ( v ) > 0 v ∈ V v \in V v ∈ V r ≥ 2 r \ge2 r ≥ 2 r r r V V V ( S 1 , … , S r ) (S_1,\ldots,S_r) ( S 1 , … , S r ) V V V B B B V V V
∑ 1 ≤ j < ℓ ≤ r ∑ u ∈ S j ∑ v ∈ S ℓ B u v . \sum_{1 \le j < \ell\le r}\sum_{u \in S_j}\sum_{v \in S_\ell} B_{uv}. 1 ≤ j < ℓ ≤ r ∑ u ∈ S j ∑ v ∈ S ℓ ∑ B uv . The r r r MaxCut r ( B ) \operatorname{MaxCut}_r(B) MaxCut r ( B ) r r r V V V
Draw X 1 , … , X k ∈ V X_1,\ldots,X_k \in V X 1 , … , X k ∈ V p p p k ≥ 1 k \ge1 k ≥ 1 p ∈ R V p \in\mathbb{R}^{V} p ∈ R V p v ≥ d ( v ) λ D p_v \ge\frac{d(v)}{\lambda D} p v ≥ λ D d ( v ) v ∈ V v \in V v ∈ V λ ≥ 1 \lambda\ge1 λ ≥ 1 p v = 1 / n p_v = 1/n p v = 1/ n
If the same vertex is sampled more than once, its copies remain distinct vertices of the output. The sampled graph has vertex set [ k ] [k] [ k ] X 1 , … , X k X_1,\ldots,X_k X 1 , … , X k A ^ \widehat{A} A K ∈ R V × V K \in\mathbb{R}^{V \times V} K ∈ R V × V
A ^ i j : = A X i X j k 2 p X i p X j , K u v : = A u v n 2 p u p v . (39) \widehat{A}_{ij} := \frac{A_{X_iX_j}}{k^2p_{X_i}p_{X_j}}, \qquad K_{uv} := \frac{A_{uv}}{n^2p_up_v}. \tag*{(39)} A ij := k 2 p X i p X j A X i X j , K uv := n 2 p u p v A uv . (39) Let P X ∈ R V P_X \in\mathbb{R}^{V} P X ∈ R V P X ( v ) : = ∣ { i : X i = v } ∣ / k P_X(v) := |\{i:X_i=v\}|/k P X ( v ) := ∣ { i : X i = v } ∣/ k v ∈ V v \in V v ∈ V K K K r r r 1 / n 2 1/n^2 1/ n 2 p p p P X P_X P X
MaxCut r ( A ) n 2 = max V = S 1 ∪ ˙ ⋯ ∪ ˙ S r ∑ j < ℓ ∑ u ∈ S j ∑ v ∈ S ℓ p u p v K u v , \frac{\operatorname{MaxCut}_r(A)}{n^2}
=
\max_{V=S_1\mathbin{\dot\cup}\cdots\mathbin{\dot\cup}S_r}
\sum_{j<\ell}\sum_{u \in S_j}\sum_{v \in S_\ell}p_up_vK_{uv}, n 2 MaxCut r ( A ) = V = S 1 ∪ ˙ ⋯ ∪ ˙ S r max j < ℓ ∑ u ∈ S j ∑ v ∈ S ℓ ∑ p u p v K uv , MaxCut r ( A ^ ) n 2 = max V = S 1 ∪ ˙ ⋯ ∪ ˙ S r ∑ j < ℓ ∑ u ∈ S j ∑ v ∈ S ℓ P X ( u ) P X ( v ) K u v . \frac{\operatorname{MaxCut}_r(\widehat{A})}{n^2}
=
\max_{V=S_1\mathbin{\dot\cup}\cdots\mathbin{\dot\cup}S_r}
\sum_{j<\ell}\sum_{u \in S_j}\sum_{v \in S_\ell}P_X(u)P_X(v)K_{uv}. n 2 MaxCut r ( A ) = V = S 1 ∪ ˙ ⋯ ∪ ˙ S r max j < ℓ ∑ u ∈ S j ∑ v ∈ S ℓ ∑ P X ( u ) P X ( v ) K uv . The second identity uses the fact that in the sampled graph, at least one optimal cut keeps all copies of the same vertex together. Lemma 5.4 proves this fact and both identities.
We will use the following quantity to control the sampling error through second moment estimates.
H : = ∑ v ∈ V p v ( ∑ u ∈ V p u K u v 2 ) 1 / 2 . H := \sum_{v \in V}p_v\left(\sum_{u \in V}p_uK_{uv}^{2}\right)^{1/2}. H := v ∈ V ∑ p v ( u ∈ V ∑ p u K uv 2 ) 1/2 . A simple calculation (see Lemma 2.10) shows that H ≤ 1 H \le1 H ≤ 1 A u v A_{uv} A uv [ 0 , 1 ] [0,1] [ 0 , 1 ]
p v ≥ d ( v ) n 2 , ∀ v ∈ V . (40) p_v \ge\frac{d(v)}{n^2}, \qquad\forall v \in V. \tag*{(40)} p v ≥ n 2 d ( v ) , ∀ v ∈ V . (40) Theorem 5.1 (Sampling approximates the r r r For every positive probability vector p ∈ R V p \in\mathbb{R}^{V} p ∈ R V
E [ ∣ MaxCut r ( A ^ ) − MaxCut r ( A ) n 2 ∣ ] ≤ 48 2 H log ( 2 r ) k . (41) \mathbb{E}\left[\left|\frac{\operatorname{MaxCut}_{r}(\widehat{A})-\operatorname{MaxCut}_{r}(A)}{n^{2}}\right|\right]\leq48\sqrt{2}\,H\sqrt{\frac{\log(2r)}{k}}. \tag*{(41)} E [ n 2 MaxCut r ( A ) − MaxCut r ( A ) ] ≤ 48 2 H k log ( 2 r ) . (41) Applying Markov’s inequality gives the following high-probability guarantee.
Corollary 5.2 (High-probability bound). Assume 0 ≤ A u v ≤ 1 0\leq A_{uv}\leq1 0 ≤ A uv ≤ 1 for every u , v ∈ V u,v\in V u , v ∈ V Then for every positive sampling distribution satisfying (40) , including uniform and importance sampling with λ = 1 \lambda=1 λ = 1
∀ 0 < ε < 1 , P ( ∣ MaxCut r ( A ^ ) − MaxCut r ( A ) ∣ ≥ ε n 2 ) ≤ 48 2 ε log ( 2 r ) k . (42) \forall\ 0<\varepsilon<1,\qquad\mathbb{P}\left(\left|\operatorname{MaxCut}_{r}(\widehat{A})-\operatorname{MaxCut}_{r}(A)\right|\geq\varepsilon n^{2}\right)\leq\frac{48\sqrt{2}}{\varepsilon}\sqrt{\frac{\log(2r)}{k}}. \tag*{(42)} ∀ 0 < ε < 1 , P ( MaxCut r ( A ) − MaxCut r ( A ) ≥ ε n 2 ) ≤ ε 48 2 k log ( 2 r ) . (42) Consequently, to get error probability at most δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) it suffices to take any
k ≥ 4608 log ( 2 r ) δ 2 ε 2 . (43) k\geq\frac{4608\log(2r)}{\delta^{2}\varepsilon^{2}}. \tag*{(43)} k ≥ δ 2 ε 2 4608 log ( 2 r ) . (43) The probability bound holds for each fixed r ≥ 2 r\geq2 r ≥ 2
Proof. § 3.1 verifies the bound H ≤ 1 H\leq1 H ≤ 1 (40) , and then Markov’s inequality implies (42) . Solving for k k k δ \delta δ
A simple calculation shows that, for importance sampling with parameter λ ≥ 1 \lambda\geq1 λ ≥ 1 λ \lambda λ k ≥ 41472 λ ε − 2 log ( 2 r ) k\geq41472\lambda\varepsilon^{-2}\log(2r) k ≥ 41472 λ ε − 2 log ( 2 r ) 1 / 3 1/3 1/3
Proof overview
The proof follows the same three stages as for Max-Cut: express both optima through a common functional, compare fractional cuts by minimax, and bound the resulting sampling error. The main change is that each vertex’s weight is now divided among r r r log ( 2 r ) \sqrt{\log(2r)} log ( 2 r )
Our first step is to view sampling as a change in vertex weights. Given K K K q ∈ R V q\in\mathbb{R}^{V} q ∈ R V F K , r ( q ) F_{K,r}(q) F K , r ( q ) r r r K K K q v q_v q v ( u , v ) (u,v) ( u , v ) q u q v K u v q_uq_vK_{uv} q u q v K uv q v q_v q v r r r § 6.2 that this does not change the optimum value, and in fact
F K , r ( p ) = MaxCut r ( A ) n 2 , F K , r ( P X ) = MaxCut r ( A ^ ) n 2 . F_{K,r}(p)=\frac{\operatorname{MaxCut}_{r}(A)}{n^{2}},\qquad F_{K,r}(P_X)=\frac{\operatorname{MaxCut}_{r}(\widehat{A})}{n^{2}}. F K , r ( p ) = n 2 MaxCut r ( A ) , F K , r ( P X ) = n 2 MaxCut r ( A ) . We then compare in § 6.3 these two values, and more generally F K , r ( q ) F_{K,r}(q) F K , r ( q ) F K , r ( s ) F_{K,r}(s) F K , r ( s ) q , s ∈ R V q,s\in\mathbb{R}^{V} q , s ∈ R V q q q s s s t ∈ { q , s } t\in\{q,s\} t ∈ { q , s } a = ( a 1 , … , a r ) ∈ ( R V ) r a=(a^{1},\ldots,a^{r})\in(\mathbb{R}^{V})^{r} a = ( a 1 , … , a r ) ∈ ( R V ) r a j ≥ 0 a^{j}\geq0 a j ≥ 0 ∑ j a j = t \sum_{j}a^{j}=t ∑ j a j = t 1 2 ∑ j ≠ ℓ ( a j ) ⊤ K a ℓ \frac{1}{2}\sum_{j\neq\ell}(a^{j})^{\top}Ka^{\ell} 2 1 ∑ j = ℓ ( a j ) ⊤ K a ℓ ∑ j ≠ ℓ ( a j ) ⊤ K a ℓ \sum_{j\neq\ell}(a^{j})^{\top}Ka^{\ell} ∑ j = ℓ ( a j ) ⊤ K a ℓ ∑ j ≠ ℓ ( a j ) ⊤ K c ℓ \sum_{j\neq\ell}(a^{j})^{\top}Kc^{\ell} ∑ j = ℓ ( a j ) ⊤ K c ℓ c ∈ ( R V ) r c\in(\mathbb{R}^{V})^{r} c ∈ ( R V ) r a a a c j ≥ 0 c^{j}\geq0 c j ≥ 0 ∑ j c j = q \sum_{j}c^{j}=q ∑ j c j = q ∑ j c j = s \sum_{j}c^{j}=s ∑ j c j = s c c c a a a M t , r ( c ) : = max a 1 , … , a r ≥ 0 ∑ j a j = t ∑ j ≠ ℓ ( a j ) ⊤ K c ℓ M_{t,r}(c):=\max_{a^{1},\ldots,a^{r}\geq0\atop\sum_{j}a^{j}=t}\sum_{j\neq\ell}(a^{j})^{\top}Kc^{\ell} M t , r ( c ) := max ∑ j a j = t a 1 , … , a r ≥ 0 ∑ j = ℓ ( a j ) ⊤ K c ℓ M q , r ( c ) M_{q,r}(c) M q , r ( c ) M s , r ( c ) M_{s,r}(c) M s , r ( c ) c c c Δ K , r ( q , s ) \Delta_{K,r}(q,s) Δ K , r ( q , s ) C r ( q , s ) \mathcal{C}_r(q,s) C r ( q , s ) c c c
Δ K , r ( q , s ) : = max c ∈ C r ( q , s ) ∣ M q , r ( c ) − M s , r ( c ) ∣ . \Delta_{K,r}(q,s) := \max_{c \in\mathcal{C}_r(q,s)} \lvert M_{q,r}(c) - M_{s,r}(c) \rvert. Δ K , r ( q , s ) := c ∈ C r ( q , s ) max ∣ M q , r ( c ) − M s , r ( c )∣ . A minimax argument converts the comparison of these maxima into a matching of fractional cuts. For each a ∈ ( R V ) r a \in(\mathbb{R}^{V})^r a ∈ ( R V ) r a j ≥ 0 a^j \ge0 a j ≥ 0 ∑ j a j = q \sum_j a^j = q ∑ j a j = q b ∈ ( R V ) r b \in(\mathbb{R}^{V})^r b ∈ ( R V ) r b j ≥ 0 b^j \ge0 b j ≥ 0 ∑ j b j = s \sum_j b^j = s ∑ j b j = s ∑ j ≠ ℓ ( a j ) T K c ℓ \sum_{j \ne\ell} (a^j)^{\mathsf T} K c^\ell ∑ j = ℓ ( a j ) T K c ℓ ∑ j ≠ ℓ ( b j ) T K c ℓ \sum_{j \ne\ell} (b^j)^{\mathsf T} K c^\ell ∑ j = ℓ ( b j ) T K c ℓ c c c
max c ∈ C r ( q , s ) ∣ ∑ j ≠ ℓ ( a j − b j ) T K c ℓ ∣ ≤ Δ K , r ( q , s ) . \max_{c \in\mathcal{C}_r(q,s)} \left\lvert\sum_{j \ne\ell} (a^j-b^j)^{\mathsf T}Kc^\ell\right\rvert\le\Delta_{K,r}(q,s). c ∈ C r ( q , s ) max j = ℓ ∑ ( a j − b j ) T K c ℓ ≤ Δ K , r ( q , s ) . Using this matching, a simple calculation shows that
∣ F K , r ( q ) − F K , r ( s ) ∣ ≤ Δ K , r ( q , s ) . \lvert F_{K,r}(q) - F_{K,r}(s) \rvert\le\Delta_{K,r}(q,s). ∣ F K , r ( q ) − F K , r ( s )∣ ≤ Δ K , r ( q , s ) . Applying this bound with q = p q=p q = p s = P X s=P_X s = P X E X Δ K , r ( p , P X ) \mathbb{E}_X\Delta_{K,r}(p,P_X) E X Δ K , r ( p , P X ) § 6.4 . The main difficulty is that both the sampling error for a given c c c c c c X X X c c c Δ K , r ( p , P X ) \Delta_{K,r}(p,P_X) Δ K , r ( p , P X ) symmetrization . We draw an independent ghost sample Y 1 , … , Y k Y_1,\ldots,Y_k Y 1 , … , Y k p p p P Y P_Y P Y Δ K , r ( p , P X ) \Delta_{K,r}(p,P_X) Δ K , r ( p , P X )
Δ K , r ( p , P X ) = max c ∈ C r ( p , P X ) ∣ E Y [ M P X , r ( c ) − M P Y , r ( c ) ] ∣ . \Delta_{K,r}(p,P_X) = \max_{c \in\mathcal{C}_r(p,P_X)} \left\lvert\mathbb{E}_Y[M_{P_X,r}(c)-M_{P_Y,r}(c)] \right\rvert. Δ K , r ( p , P X ) = c ∈ C r ( p , P X ) max ∣ E Y [ M P X , r ( c ) − M P Y , r ( c )] ∣ . We enlarge the feasible region for c c c X i X_i X i Y i Y_i Y i k k k τ 1 , … , τ k ∈ { ± 1 } \tau_1,\ldots,\tau_k \in\{\pm1\} τ 1 , … , τ k ∈ { ± 1 } + 1 +1 + 1 X i , Y i X_i,Y_i X i , Y i − 1 -1 − 1 g c ( v ) : = max 1 ≤ j ≤ r ∑ ℓ ≠ j ( K c ℓ ) v g_c(v) := \max_{1 \le j \le r}\sum_{\ell\ne j}(Kc^\ell)_v g c ( v ) := max 1 ≤ j ≤ r ∑ ℓ = j ( K c ℓ ) v M P X , r ( c ) − M P Y , r ( c ) M_{P_X,r}(c)-M_{P_Y,r}(c) M P X , r ( c ) − M P Y , r ( c )
1 k ∑ i = 1 k τ i ( g c ( X i ) − g c ( Y i ) ) . \frac{1}{k}\sum_{i=1}^{k}\tau_i\bigl(g_c(X_i)-g_c(Y_i)\bigr). k 1 i = 1 ∑ k τ i ( g c ( X i ) − g c ( Y i ) ) . This lets us apply Maurer’s vector contraction inequality to reduce to a signed sum linear in c c c c c c ∑ j ∣ c j ∣ \sum_j \lvert c^j \rvert ∑ j ∣ c j ∣ log ( 2 r ) \sqrt{\log(2r)} log ( 2 r ) r r r
E X Δ K , r ( p , P X ) ≤ 48 2 H log ( 2 r ) k . \mathbb{E}_X\Delta_{K,r}(p,P_X) \le48\sqrt{2}\,H\sqrt{\frac{\log(2r)}{k}}. E X Δ K , r ( p , P X ) ≤ 48 2 H k log ( 2 r ) . Reduce both r r r
We express the normalized r r r A A A A ^ \widehat{A} A F K , r ( ⋅ ) F_{K,r}(\cdot) F K , r ( ⋅ ) p p p P X P_X P X
To define F K , r F_{K,r} F K , r x v j ∈ { 0 , 1 } x_v^j \in\{0,1\} x v j ∈ { 0 , 1 } v v v x v j = 1 x_v^j=1 x v j = 1 j j j ∑ j = 1 r x v j = 1 \sum_{j=1}^{r}x_v^j=1 ∑ j = 1 r x v j = 1 v v v x v j ∈ [ 0 , 1 ] x_v^j \in[0,1] x v j ∈ [ 0 , 1 ] x v j x_v^j x v j v v v j j j q v ≥ 0 q_v \ge0 q v ≥ 0 v v v j j j a v j = q v x v j a_v^j = q_v x_v^j a v j = q v x v j weighted fraction of v v v a v j a_v^j a v j v v v a v j ≥ 0 a_v^j \ge0 a v j ≥ 0 ∑ j a v j = q v \sum_j a_v^j = q_v ∑ j a v j = q v a v j ∈ { 0 , q v } a_v^j \in\{0,q_v\} a v j ∈ { 0 , q v } p p p P X P_X P X
Define the feasible fractional cuts by
Z r ( q ) : = { a = ( a 1 , … , a r ) ∈ ( R V ) r : a v j ≥ 0 , ∑ j = 1 r a v j = q v for every v ∈ V } (44) Z_r(q) := \left\{a = (a^1,\ldots,a^r) \in(\mathbb{R}^{V})^r : a_v^j \ge0,\ \sum_{j=1}^{r} a_v^j = q_v\ \text{for every }v \in V\right\} \tag*{(44)} Z r ( q ) := { a = ( a 1 , … , a r ) ∈ ( R V ) r : a v j ≥ 0 , j = 1 ∑ r a v j = q v for every v ∈ V } (44) and their optimal value by
F K , r ( q ) : = max a ∈ Z r ( q ) ∑ j < ℓ ( a j ) T K a ℓ = 1 2 max a ∈ Z r ( q ) ∑ j ≠ ℓ ( a j ) T K a ℓ . (45) F_{K,r}(q) := \max_{a \in Z_r(q)} \sum_{j<\ell} (a^j)^{\mathsf T} K a^\ell= \frac{1}{2}\max_{a \in Z_r(q)} \sum_{j \ne\ell} (a^j)^{\mathsf T} K a^\ell. \tag*{(45)} F K , r ( q ) := a ∈ Z r ( q ) max j < ℓ ∑ ( a j ) T K a ℓ = 2 1 a ∈ Z r ( q ) max j = ℓ ∑ ( a j ) T K a ℓ . (45) The tuple a = ( a 1 , … , a r ) a = (a^1,\ldots,a^r) a = ( a 1 , … , a r ) V V V j , ℓ j,\ell j , ℓ r r r j j j ℓ \ell ℓ ∑ u , v a u j K u v a v ℓ = ( a j ) T K a ℓ \sum_{u,v}a_u^jK_{uv}a_v^\ell= (a^j)^{\mathsf T}Ka^\ell ∑ u , v a u j K uv a v ℓ = ( a j ) T K a ℓ ∑ j ≠ ℓ \sum_{j\ne\ell} ∑ j = ℓ K K K 1 / 2 1/2 1/2 § 6.3 .
Lemma 5.3 (The maximum is attained by a cut). For every nonnegative weight vector q ∈ R V q \in\mathbb{R}^{V} q ∈ R V a ∈ Z r ( q ) a \in Z_r(q) a ∈ Z r ( q ) (45) that corresponds to a cut, i.e., a v j ∈ { 0 , q v } a_v^j \in\{0,q_v\} a v j ∈ { 0 , q v } v ∈ V v \in V v ∈ V 1 ≤ j ≤ r 1 \le j \le r 1 ≤ j ≤ r
Proof. Since K v v = 0 K_{vv}=0 K v v = 0 ∑ j < ℓ ( a j ) T K a ℓ \sum_{j<\ell}(a^j)^{\mathsf T}Ka^\ell ∑ j < ℓ ( a j ) T K a ℓ ( a v 1 , … , a v r ) (a_v^1,\ldots,a_v^r) ( a v 1 , … , a v r ) { z ∈ R r : z j ≥ 0 , ∑ j = 1 r z j = q v } \{z \in\mathbb{R}^r : z_j \ge0,\ \sum_{j=1}^{r}z_j=q_v\} { z ∈ R r : z j ≥ 0 , ∑ j = 1 r z j = q v } ( a v 1 , … , a v r ) (a_v^1,\ldots,a_v^r) ( a v 1 , … , a v r ) q v q_v q v a v j ∈ { 0 , q v } a_v^j \in\{0,q_v\} a v j ∈ { 0 , q v } v , j v,j v , j
Lemma 5.4 (The two r r r With p p p P X P_X P X K K K
F K , r ( p ) = MaxCut r ( A ) n 2 , F K , r ( P X ) = MaxCut r ( A ^ ) n 2 . F_{K,r}(p) = \frac{\operatorname{MaxCut}_r(A)}{n^2}, \qquad F_{K,r}(P_X) = \frac{\operatorname{MaxCut}_r(\widehat{A})}{n^2}. F K , r ( p ) = n 2 MaxCut r ( A ) , F K , r ( P X ) = n 2 MaxCut r ( A ) . Proof. For the first identity, Lemma 5.3 lets us maximize over r r r V = S 1 ∪ ˙ ⋯ ∪ ˙ S r V = S_1 \mathbin{\dot\cup} \cdots\mathbin{\dot\cup} S_r V = S 1 ∪ ˙ ⋯ ∪ ˙ S r p u p v K u v = A u v / n 2 p_up_vK_{uv}=A_{uv}/n^2 p u p v K uv = A uv / n 2
F K , r ( p ) = max V = S 1 ∪ ˙ ⋯ ∪ ˙ S r ∑ j < ℓ ∑ u ∈ S j ∑ v ∈ S ℓ p u p v K u v = MaxCut r ( A ) n 2 . F_{K,r}(p) = \max_{V=S_1\mathbin{\dot\cup}\cdots\mathbin{\dot\cup}S_r} \sum_{j<\ell}\sum_{u\in S_j}\sum_{v\in S_\ell}p_up_vK_{uv} = \frac{\operatorname{MaxCut}_r(A)}{n^2}. F K , r ( p ) = V = S 1 ∪ ˙ ⋯ ∪ ˙ S r max j < ℓ ∑ u ∈ S j ∑ v ∈ S ℓ ∑ p u p v K uv = n 2 MaxCut r ( A ) . For the second identity, we first show that all copies of a repeatedly sampled vertex can be moved to the same part without decreasing the cut value. Start with an optimal cut for the sampled subgraph (induced on X 1 , … , X k X_1,\ldots,X_k X 1 , … , X k
For an original vertex v v v v v v
Such a cut is described by a partition V = S 1 ∪ ˙ ⋯ ∪ ˙ S r V = S_1 \mathbin{\dot\cup} \cdots\mathbin{\dot\cup} S_r V = S 1 ∪ ˙ ⋯ ∪ ˙ S r S j S_j S j j j j u ∈ S j u \in S_j u ∈ S j v ∈ S ℓ v \in S_\ell v ∈ S ℓ j < ℓ j < \ell j < ℓ k P X ( u ) k P X ( v ) kP_X(u)\,kP_X(v) k P X ( u ) k P X ( v ) ( i , i ′ ) (i,i') ( i , i ′ ) X i = u X_i = u X i = u X i ′ = v X_{i'} = v X i ′ = v n 2 n^2 n 2
A ^ i i ′ n 2 = A u v k 2 n 2 p u p v = K u v k 2 . \frac{\widehat{A}_{ii'}}{n^2} = \frac{A_{uv}}{k^2 n^2 p_u p_v} = \frac{K_{uv}}{k^2}. n 2 A i i ′ = k 2 n 2 p u p v A uv = k 2 K uv . Therefore, applying Lemma 5.3 with q = P X q = P_X q = P X
F K , r ( P X ) = max V = S 1 ∪ ˙ ⋯ ∪ ˙ S r ∑ j < ℓ ∑ u ∈ S j ∑ v ∈ S ℓ P X ( u ) P X ( v ) K u v = MaxCut r ( A ^ ) n 2 . (46) F_{K,r}(P_X) = \max_{V=S_1\mathbin{\dot\cup}\cdots\mathbin{\dot\cup}S_r} \sum_{j<\ell}\sum_{u\in S_j}\sum_{v\in S_\ell} P_X(u)P_X(v)K_{uv} = \frac{\operatorname{MaxCut}_r(\widehat{A})}{n^2}. \tag*{(46)} F K , r ( P X ) = V = S 1 ∪ ˙ ⋯ ∪ ˙ S r max j < ℓ ∑ u ∈ S j ∑ v ∈ S ℓ ∑ P X ( u ) P X ( v ) K uv = n 2 MaxCut r ( A ) . (46) By Lemma 5.4 ,
∣ MaxCut r ( A ^ ) − MaxCut r ( A ) ∣ n 2 = ∣ F K , r ( P X ) − F K , r ( p ) ∣ . \frac{\left|\operatorname{MaxCut}_r(\widehat{A})-\operatorname{MaxCut}_r(A)\right|}{n^2} = \left|F_{K,r}(P_X)-F_{K,r}(p)\right|. n 2 MaxCut r ( A ) − MaxCut r ( A ) = ∣ F K , r ( P X ) − F K , r ( p ) ∣ . Compare cut values under two vertex distributions
In this subsection, we bound the difference between F K , r ( q ) F_{K,r}(q) F K , r ( q ) F K , r ( s ) F_{K,r}(s) F K , r ( s ) q , s q,s q , s V V V q = p q=p q = p s = P X s=P_X s = P X
For a nonnegative vector q q q c ∈ ( R V ) r c\in(\mathbb{R}^V)^r c ∈ ( R V ) r M q , r ( c ) M_{q,r}(c) M q , r ( c ) ∑ j ≠ ℓ ( x j ) T K c ℓ \sum_{j\ne\ell}(x^j)^\mathsf{T}Kc^\ell ∑ j = ℓ ( x j ) T K c ℓ x ∈ Z r ( q ) x\in Z_r(q) x ∈ Z r ( q )
M q , r ( c ) : = max x ∈ Z r ( q ) ∑ j ≠ ℓ ( x j ) T K c ℓ = ∑ v ∈ V q v g c ( v ) . (47) M_{q,r}(c) := \max_{x\in Z_r(q)} \sum_{j\ne\ell}(x^j)^\mathsf{T}Kc^\ell= \sum_{v\in V}q_v g_c(v). \tag*{(47)} M q , r ( c ) := x ∈ Z r ( q ) max j = ℓ ∑ ( x j ) T K c ℓ = v ∈ V ∑ q v g c ( v ) . (47) where
g c ( v ) : = max 1 ≤ j ≤ r ∑ ℓ ≠ j ( K c ℓ ) v . (48) g_c(v) := \max_{1\le j\le r}\sum_{\ell\ne j}(Kc^\ell)_v. \tag*{(48)} g c ( v ) := 1 ≤ j ≤ r max ℓ = j ∑ ( K c ℓ ) v . (48) The equality follows by choosing x v j = q v x_v^j=q_v x v j = q v j j j g c ( v ) g_c(v) g c ( v ) x v ℓ = 0 x_v^\ell=0 x v ℓ = 0 ℓ ≠ j \ell\ne j ℓ = j M q , r M_{q,r} M q , r M s , r M_{s,r} M s , r Z r ( q ) Z_r(q) Z r ( q ) Z r ( s ) Z_r(s) Z r ( s )
C r ( q , s ) : = conv ( Z r ( q ) ∪ − Z r ( q ) ∪ Z r ( s ) ∪ − Z r ( s ) ) . (49) C_r(q,s) := \operatorname{conv}\left(Z_r(q)\cup-Z_r(q)\cup Z_r(s)\cup-Z_r(s)\right). \tag*{(49)} C r ( q , s ) := conv ( Z r ( q ) ∪ − Z r ( q ) ∪ Z r ( s ) ∪ − Z r ( s ) ) . (49) We consider their largest absolute difference, defined by
Δ K , r ( q , s ) : = max c ∈ C r ( q , s ) ∣ M q , r ( c ) − M s , r ( c ) ∣ . (50) \Delta_{K,r}(q,s) := \max_{c\in C_r(q,s)}\left|M_{q,r}(c)-M_{s,r}(c)\right|. \tag*{(50)} Δ K , r ( q , s ) := c ∈ C r ( q , s ) max ∣ M q , r ( c ) − M s , r ( c ) ∣ . (50) Lemma 5.5 (Comparison of cut values). For every pair of probability vectors q , s ∈ R V q,s\in\mathbb{R}^V q , s ∈ R V
∣ F K , r ( q ) − F K , r ( s ) ∣ ≤ Δ K , r ( q , s ) . (51) \left|F_{K,r}(q)-F_{K,r}(s)\right|\le\Delta_{K,r}(q,s). \tag*{(51)} ∣ F K , r ( q ) − F K , r ( s ) ∣ ≤ Δ K , r ( q , s ) . (51) Taking q = p q=p q = p s = P X s=P_X s = P X ∣ F K , r ( P X ) − F K , r ( p ) ∣ ≤ Δ K , r ( p , P X ) \lvert F_{K,r}(P_X)-F_{K,r}(p)\rvert\le\Delta_{K,r}(p,P_X) ∣ F K , r ( P X ) − F K , r ( p )∣ ≤ Δ K , r ( p , P X ) E X Δ K , r ( p , P X ) \mathbb{E}_X\Delta_{K,r}(p,P_X) E X Δ K , r ( p , P X ) § 6.4 .
To prove Lemma 5.5 , we first prove a bound that matches fractional cuts under q q q s s s
Lemma 5.6 (Matching fractional cuts). Let q , s ∈ R V q,s \in\mathbb{R}^{V} q , s ∈ R V a ∈ Z r ( q ) a \in Z_r(q) a ∈ Z r ( q ) b ∈ Z r ( s ) b \in Z_r(s) b ∈ Z r ( s )
max c ∈ C r ( q , s ) ∣ ∑ j ≠ ℓ ( a j − b j ) T K c ℓ ∣ ≤ Δ K , r ( q , s ) . (52) \max_{c \in C_r(q,s)} \left\lvert\sum_{j \ne\ell}(a^j-b^j)^{\mathsf{T}}Kc^\ell\right\rvert\le\Delta_{K,r}(q,s). \tag*{(52)} c ∈ C r ( q , s ) max j = ℓ ∑ ( a j − b j ) T K c ℓ ≤ Δ K , r ( q , s ) . (52) Conversely, every b ∈ Z r ( s ) b \in Z_r(s) b ∈ Z r ( s ) a ∈ Z r ( q ) a \in Z_r(q) a ∈ Z r ( q )
Proof. Fix a ∈ Z r ( q ) a \in Z_r(q) a ∈ Z r ( q ) C r ( q , s ) = − C r ( q , s ) C_r(q,s)=-C_r(q,s) C r ( q , s ) = − C r ( q , s ) [26 ] to the function ( b , c ) ↦ ∑ j ≠ ℓ ( a j − b j ) T K c ℓ (b,c) \mapsto\sum_{j \ne\ell}(a^j-b^j)^{\mathsf{T}}Kc^\ell ( b , c ) ↦ ∑ j = ℓ ( a j − b j ) T K c ℓ Z r ( s ) Z_r(s) Z r ( s ) C r ( q , s ) C_r(q,s) C r ( q , s )
min b ∈ Z r ( s ) max c ∈ C r ( q , s ) ∣ ∑ j ≠ ℓ ( a j − b j ) T K c ℓ ∣ = min b ∈ Z r ( s ) max c ∈ C r ( q , s ) ∑ j ≠ ℓ ( a j − b j ) T K c ℓ = max c ∈ C r ( q , s ) min b ∈ Z r ( s ) ∑ j ≠ ℓ ( a j − b j ) T K c ℓ = max c ∈ C r ( q , s ) ( ∑ j ≠ ℓ ( a j ) T K c ℓ − M s , r ( c ) ) ≤ max c ∈ C r ( q , s ) ( M q , r ( c ) − M s , r ( c ) ) ≤ Δ K , r ( q , s ) . \begin{aligned}
\min_{b \in Z_r(s)}\max_{c \in C_r(q,s)}\left\lvert\sum_{j \ne\ell}(a^j-b^j)^{\mathsf{T}}Kc^\ell\right\rvert
&= \min_{b \in Z_r(s)}\max_{c \in C_r(q,s)}\sum_{j \ne\ell}(a^j-b^j)^{\mathsf{T}}Kc^\ell\\
&= \max_{c \in C_r(q,s)}\min_{b \in Z_r(s)}\sum_{j \ne\ell}(a^j-b^j)^{\mathsf{T}}Kc^\ell\\
&= \max_{c \in C_r(q,s)}\left(\sum_{j \ne\ell}(a^j)^{\mathsf{T}}Kc^\ell-M_{s,r}(c)\right) \\
&\le\max_{c \in C_r(q,s)}\left(M_{q,r}(c)-M_{s,r}(c)\right)\le\Delta_{K,r}(q,s).
\end{aligned} b ∈ Z r ( s ) min c ∈ C r ( q , s ) max j = ℓ ∑ ( a j − b j ) T K c ℓ = b ∈ Z r ( s ) min c ∈ C r ( q , s ) max j = ℓ ∑ ( a j − b j ) T K c ℓ = c ∈ C r ( q , s ) max b ∈ Z r ( s ) min j = ℓ ∑ ( a j − b j ) T K c ℓ = c ∈ C r ( q , s ) max j = ℓ ∑ ( a j ) T K c ℓ − M s , r ( c ) ≤ c ∈ C r ( q , s ) max ( M q , r ( c ) − M s , r ( c ) ) ≤ Δ K , r ( q , s ) . The minimum is attained, so (52) follows.
Interchanging q q q s s s b ∈ Z r ( s ) b \in Z_r(s) b ∈ Z r ( s ) □ \square □
Proof of Lemma 5.5. Let a ∈ Z r ( q ) a \in Z_r(q) a ∈ Z r ( q ) F K , r ( q ) F_{K,r}(q) F K , r ( q ) b ∈ Z r ( s ) b \in Z_r(s) b ∈ Z r ( s ) Lemma 5.6 . Write Δ = Δ K , r ( q , s ) \Delta=\Delta_{K,r}(q,s) Δ = Δ K , r ( q , s )
For every c ∈ C r ( q , s ) c \in C_r(q,s) c ∈ C r ( q , s ) Lemma 5.6 gives
∣ ∑ j ≠ ℓ ( a j − b j ) T K c ℓ ∣ ≤ Δ . \left\lvert\sum_{j \ne\ell}(a^j-b^j)^{\mathsf{T}}Kc^\ell\right\rvert\le\Delta. j = ℓ ∑ ( a j − b j ) T K c ℓ ≤ Δ. Since F K , r ( s ) ≥ 1 2 ∑ j ≠ ℓ ( b j ) T K b ℓ F_{K,r}(s)\ge\frac{1}{2}\sum_{j \ne\ell}(b^j)^{\mathsf{T}}Kb^\ell F K , r ( s ) ≥ 2 1 ∑ j = ℓ ( b j ) T K b ℓ K K K
F K , r ( q ) − F K , r ( s ) ≤ 1 2 ∑ j ≠ ℓ ( ( a j ) T K a ℓ − ( b j ) T K b ℓ ) = 1 2 ∑ j ≠ ℓ ( a j − b j ) T K a ℓ + 1 2 ∑ j ≠ ℓ ( a j − b j ) T K b ℓ ≤ 1 2 ∣ ∑ j ≠ ℓ ( a j − b j ) T K a ℓ ∣ + 1 2 ∣ ∑ j ≠ ℓ ( a j − b j ) T K b ℓ ∣ . (53) \begin{aligned}
F_{K,r}(q)-F_{K,r}(s)
&\le\frac{1}{2}\sum_{j \ne\ell}\left((a^j)^{\mathsf{T}}Ka^\ell-(b^j)^{\mathsf{T}}Kb^\ell\right) \\
&= \frac{1}{2}\sum_{j \ne\ell}(a^j-b^j)^{\mathsf{T}}Ka^\ell+\frac{1}{2}\sum_{j \ne\ell}(a^j-b^j)^{\mathsf{T}}Kb^\ell\\
&\le\frac{1}{2}\left\lvert\sum_{j \ne\ell}(a^j-b^j)^{\mathsf{T}}Ka^\ell\right\rvert+\frac{1}{2}\left\lvert\sum_{j \ne\ell}(a^j-b^j)^{\mathsf{T}}Kb^\ell\right\rvert. \tag*{(53)}
\end{aligned} F K , r ( q ) − F K , r ( s ) ≤ 2 1 j = ℓ ∑ ( ( a j ) T K a ℓ − ( b j ) T K b ℓ ) = 2 1 j = ℓ ∑ ( a j − b j ) T K a ℓ + 2 1 j = ℓ ∑ ( a j − b j ) T K b ℓ ≤ 2 1 j = ℓ ∑ ( a j − b j ) T K a ℓ + 2 1 j = ℓ ∑ ( a j − b j ) T K b ℓ . (53) Since a ∈ Z r ( q ) a \in Z_r(q) a ∈ Z r ( q ) b ∈ Z r ( s ) b \in Z_r(s) b ∈ Z r ( s ) C r ( q , s ) C_r(q,s) C r ( q , s ) (52) to get
F K , r ( q ) − F K , r ( s ) ≤ 1 2 Δ + 1 2 Δ = Δ . F_{K,r}(q)-F_{K,r}(s) \le\frac{1}{2}\Delta+\frac{1}{2}\Delta=\Delta. F K , r ( q ) − F K , r ( s ) ≤ 2 1 Δ + 2 1 Δ = Δ. Interchanging q q q s s s F K , r ( s ) − F K , r ( q ) F_{K,r}(s)-F_{K,r}(q) F K , r ( s ) − F K , r ( q ) (51) .
Bound the sampling error
In this subsection we prove that
E X Δ K , r ( p , P X ) ≤ 48 2 H log ( 2 r ) k . (54) \mathbb{E}_{X}\Delta_{K,r}(p,P_X) \le48\sqrt{2}\,H\sqrt{\frac{\log(2r)}{k}}. \tag*{(54)} E X Δ K , r ( p , P X ) ≤ 48 2 H k log ( 2 r ) . (54) Together with Lemmas 5.4 and 5.5, this completes the proof of Theorem 5.1. Recall that Δ K , r ( p , P X ) \Delta_{K,r}(p,P_X) Δ K , r ( p , P X )
M p , r ( c ) = ∑ v p v max 1 ≤ j ≤ r ∑ ℓ ≠ j ( K c ℓ ) v , M P X , r ( c ) = 1 k ∑ i = 1 k max 1 ≤ j ≤ r ∑ ℓ ≠ j ( K c ℓ ) X i , (55) M_{p,r}(c)=\sum_v p_v\max_{1\le j\le r}\sum_{\substack{\ell\ne j}}(Kc^\ell)_v,\qquad M_{P_X,r}(c)=\frac{1}{k}\sum_{i=1}^{k}\max_{1\le j\le r}\sum_{\substack{\ell\ne j}}(Kc^\ell)_{X_i}, \tag*{(55)} M p , r ( c ) = v ∑ p v 1 ≤ j ≤ r max ℓ = j ∑ ( K c ℓ ) v , M P X , r ( c ) = k 1 i = 1 ∑ k 1 ≤ j ≤ r max ℓ = j ∑ ( K c ℓ ) X i , (55) over c ∈ C r ( p , P X ) c\in C_r(p,P_X) c ∈ C r ( p , P X ) X X X M P X , r M_{P_X,r} M P X , r
Symmetrization. Instead of comparing P X P_X P X p p p P X , P Y P_X,P_Y P X , P Y X , Y X,Y X , Y c c c B X , Y ( r ) \mathcal{B}^{(r)}_{X,Y} B X , Y ( r )
We use symmetrization and Maurer’s vector contraction inequality [19 ] to reduce the problem to bounding the expected maximum of sums of ( K c j ) X i (Kc^j)_{X_i} ( K c j ) X i
Second-moment bounds. The signed sums are linear in c c c p p p P X P_X P X P Y P_Y P Y 2 2 H log ( 2 r ) / k 2\sqrt{2}\,H\sqrt{\log(2r)/k} 2 2 H log ( 2 r ) / k L 1 L^1 L 1 6 2 H log ( 2 r ) / k 6\sqrt{2}\,H\sqrt{\log(2r)/k} 6 2 H log ( 2 r ) / k
Combining the two estimates gives (54) . Lemma 5.5 then bounds the expected normalized r r r 48 2 H log ( 2 r ) / k 48\sqrt{2}\,H\sqrt{\log(2r)/k} 48 2 H log ( 2 r ) / k
Symmetrization
Lemma 5.7 (Reduction to a signed linear maximum). Let Y 1 , … , Y k Y_1,\ldots,Y_k Y 1 , … , Y k p p p X X X P Y P_Y P Y σ i j ∈ { ± 1 } \sigma_{ij}\in\{\pm1\} σ ij ∈ { ± 1 } 1 ≤ i ≤ k 1\le i\le k 1 ≤ i ≤ k 0 ≤ j ≤ r 0\le j\le r 0 ≤ j ≤ r X , Y X,Y X , Y
B X , Y ( r ) : = { c ∈ ( R V ) r : ∑ j = 1 r ∣ c v j ∣ ≤ p v + P X ( v ) + P Y ( v ) for every v ∈ V } . (56) \mathcal{B}^{(r)}_{X,Y}:=\left\{c\in(\mathbb{R}^{V})^r:\sum_{j=1}^{r}|c^j_v|\le p_v+P_X(v)+P_Y(v)\text{ for every }v\in V\right\}. \tag*{(56)} B X , Y ( r ) := { c ∈ ( R V ) r : j = 1 ∑ r ∣ c v j ∣ ≤ p v + P X ( v ) + P Y ( v ) for every v ∈ V } . (56) Then
E X Δ K , r ( p , P X ) ≤ 8 E X , Y , σ max c ∈ B X , Y ( r ) ∣ 1 k ∑ i = 1 k ∑ j = 1 r ( σ i 0 + σ i j ) ( K c j ) X i ∣ . (57) \mathbb{E}_{X}\Delta_{K,r}(p,P_X)\le8\mathbb{E}_{X,Y,\sigma}\max_{c\in\mathcal{B}^{(r)}_{X,Y}}\left|\frac{1}{k}\sum_{i=1}^{k}\sum_{j=1}^{r}(\sigma_{i0}+\sigma_{ij})(Kc^j)_{X_i}\right|. \tag*{(57)} E X Δ K , r ( p , P X ) ≤ 8 E X , Y , σ c ∈ B X , Y ( r ) max k 1 i = 1 ∑ k j = 1 ∑ r ( σ i 0 + σ ij ) ( K c j ) X i . (57) Proof. We begin with the symmetrization step using a ghost sample. For every c ∈ C r ( p , P X ) c \in C_r(p,P_X) c ∈ C r ( p , P X ) M p , r ( c ) M_{p,r}(c) M p , r ( c )
E Y M P Y , r ( c ) = ∑ v p v g c ( v ) = M p , r ( c ) . \mathbb{E}_Y M_{P_Y,r}(c) = \sum_v p_v g_c(v) = M_{p,r}(c). E Y M P Y , r ( c ) = v ∑ p v g c ( v ) = M p , r ( c ) . The region B X , Y ( r ) B_{X,Y}^{(r)} B X , Y ( r ) C r ( p , P X ) C_r(p,P_X) C r ( p , P X )
C r ( p , P X ) ⊆ B X , Y ( r ) . (58) C_r(p,P_X) \subseteq B_{X,Y}^{(r)}. \tag*{(58)} C r ( p , P X ) ⊆ B X , Y ( r ) . (58) With X X X C r ( p , P X ) C_r(p,P_X) C r ( p , P X ) Y Y Y
Δ K , r ( p , P X ) = max c ∈ C r ( p , P X ) ∣ E Y [ M P X , r ( c ) − M P Y , r ( c ) ] ∣ ≤ max c ∈ C r ( p , P X ) E Y ∣ M P X , r ( c ) − M P Y , r ( c ) ∣ ≤ E Y max c ∈ C r ( p , P X ) ∣ M P X , r ( c ) − M P Y , r ( c ) ∣ ≤ E Y max c ∈ B X , Y ( r ) ∣ 1 k ∑ i = 1 k ( g c ( X i ) − g c ( Y i ) ) ∣ . \begin{aligned}
\Delta_{K,r}(p,P_X)
&= \max_{c \in C_r(p,P_X)} \left|\mathbb{E}_Y[M_{P_X,r}(c)-M_{P_Y,r}(c)]\right| \\
&\leq\max_{c \in C_r(p,P_X)} \mathbb{E}_Y\left|M_{P_X,r}(c)-M_{P_Y,r}(c)\right| \\
&\leq\mathbb{E}_Y \max_{c \in C_r(p,P_X)} \left|M_{P_X,r}(c)-M_{P_Y,r}(c)\right| \\
&\leq\mathbb{E}_Y \max_{c \in B_{X,Y}^{(r)}} \left|\frac{1}{k}\sum_{i=1}^{k}\left(g_c(X_i)-g_c(Y_i)\right)\right|.
\end{aligned} Δ K , r ( p , P X ) = c ∈ C r ( p , P X ) max ∣ E Y [ M P X , r ( c ) − M P Y , r ( c )] ∣ ≤ c ∈ C r ( p , P X ) max E Y ∣ M P X , r ( c ) − M P Y , r ( c ) ∣ ≤ E Y c ∈ C r ( p , P X ) max ∣ M P X , r ( c ) − M P Y , r ( c ) ∣ ≤ E Y c ∈ B X , Y ( r ) max k 1 i = 1 ∑ k ( g c ( X i ) − g c ( Y i ) ) . We next take expectation over X X X τ 1 , … , τ k ∈ { ± 1 } \tau_1,\ldots,\tau_k \in\{ \pm1\} τ 1 , … , τ k ∈ { ± 1 } X , Y , σ X,Y,\sigma X , Y , σ τ ∈ { ± 1 } k \tau\in\{ \pm1\}^k τ ∈ { ± 1 } k
( X ~ i , Y ~ i ) : = { ( X i , Y i ) , τ i = 1 , ( Y i , X i ) , τ i = − 1. (\widetilde{X}_i,\widetilde{Y}_i) :=
\begin{cases}
(X_i,Y_i), & \tau_i=1,\\
(Y_i,X_i), & \tau_i=-1.
\end{cases} ( X i , Y i ) := { ( X i , Y i ) , ( Y i , X i ) , τ i = 1 , τ i = − 1. Each exchange reverses its pair’s contribution, so
g c ( X ~ i ) − g c ( Y ~ i ) = τ i ( g c ( X i ) − g c ( Y i ) ) . g_c(\widetilde{X}_i)-g_c(\widetilde{Y}_i)=\tau_i\left(g_c(X_i)-g_c(Y_i)\right). g c ( X i ) − g c ( Y i ) = τ i ( g c ( X i ) − g c ( Y i ) ) . The exchanges preserve the joint distribution of the samples. They also preserve P X + P Y P_X+P_Y P X + P Y B X ~ , Y ~ ( r ) = B X , Y ( r ) B_{\widetilde{X},\widetilde{Y}}^{(r)}=B_{X,Y}^{(r)} B X , Y ( r ) = B X , Y ( r )
E X Δ K , r ( p , P X ) ≤ E X , Y max c ∈ B X , Y ( r ) ∣ 1 k ∑ i = 1 k ( g c ( X i ) − g c ( Y i ) ) ∣ = E X , Y , τ max c ∈ B X , Y ( r ) ∣ 1 k ∑ i = 1 k τ i ( g c ( X i ) − g c ( Y i ) ) ∣ ≤ 2 E X , Y , τ max c ∈ B X , Y ( r ) ∣ 1 k ∑ i = 1 k τ i g c ( X i ) ∣ . (59) \begin{aligned}
\mathbb{E}_{X}\Delta_{K,r}(p,P_X)
&\leq\mathbb{E}_{X,Y}\max_{c \in B_{X,Y}^{(r)}}\left|\frac{1}{k}\sum_{i=1}^{k}\left(g_c(X_i)-g_c(Y_i)\right)\right| \\
&= \mathbb{E}_{X,Y,\tau}\max_{c \in B_{X,Y}^{(r)}}\left|\frac{1}{k}\sum_{i=1}^{k}\tau_i\left(g_c(X_i)-g_c(Y_i)\right)\right| \\
&\leq2\mathbb{E}_{X,Y,\tau}\max_{c \in B_{X,Y}^{(r)}}\left|\frac{1}{k}\sum_{i=1}^{k}\tau_i g_c(X_i)\right|. \tag*{(59)}
\end{aligned} E X Δ K , r ( p , P X ) ≤ E X , Y c ∈ B X , Y ( r ) max k 1 i = 1 ∑ k ( g c ( X i ) − g c ( Y i ) ) = E X , Y , τ c ∈ B X , Y ( r ) max k 1 i = 1 ∑ k τ i ( g c ( X i ) − g c ( Y i ) ) ≤ 2 E X , Y , τ c ∈ B X , Y ( r ) max k 1 i = 1 ∑ k τ i g c ( X i ) . (59) The last inequality uses the triangle inequality and symmetry between X X X Y Y Y
Finally, ϕ : ( z 0 , z 1 , … , z r ) ↦ z 0 − min 1 ≤ j ≤ r z j \phi: (z_0,z_1,\ldots,z_r) \mapsto z_0-\min_{1\le j\le r} z_j ϕ : ( z 0 , z 1 , … , z r ) ↦ z 0 − min 1 ≤ j ≤ r z j 2 \sqrt{2} 2 X , Y X,Y X , Y g c ( v ) = ϕ ( f c ( v ) ) g_c(v)=\phi(f_c(v)) g c ( v ) = ϕ ( f c ( v ))
f c ( v ) : = ( ∑ ℓ = 1 r ( K c ℓ ) v , ( K c 1 ) v , … , ( K c r ) v ) . f_c(v):=\left(\sum_{\ell=1}^{r}(Kc^\ell)_v,(Kc^1)_v,\ldots,(Kc^r)_v\right). f c ( v ) := ( ℓ = 1 ∑ r ( K c ℓ ) v , ( K c 1 ) v , … , ( K c r ) v ) . The region B X , Y ( r ) \mathcal{B}_{X,Y}^{(r)} B X , Y ( r ) f c f_c f c c c c ( f c ( X 1 ) , … , f c ( X k ) ) (f_c(X_1),\ldots,f_c(X_k)) ( f c ( X 1 ) , … , f c ( X k )) Lemma A.3 ; see [Maul16, Corollary 1]) therefore gives
E c ∈ B X , Y ( r ) max ∣ 1 k ∑ i = 1 k τ i g c ( X i ) ∣ ≤ 4 E σ max c ∈ B X , Y ( r ) ∣ 1 k ∑ i = 1 k ∑ j = 1 r ( σ i 0 + σ i j ) ( K c j ) X i ∣ . (60) \mathbb{E}_{c\in\mathcal{B}_{X,Y}^{(r)}}\max\left|\frac{1}{k}\sum_{i=1}^{k}\tau_i g_c(X_i)\right|
\le4\mathbb{E}_{\sigma}\max_{c\in\mathcal{B}_{X,Y}^{(r)}}\left|\frac{1}{k}\sum_{i=1}^{k}\sum_{j=1}^{r}(\sigma_{i0}+\sigma_{ij})(Kc^j)_{X_i}\right|. \tag*{(60)} E c ∈ B X , Y ( r ) max k 1 i = 1 ∑ k τ i g c ( X i ) ≤ 4 E σ c ∈ B X , Y ( r ) max k 1 i = 1 ∑ k j = 1 ∑ r ( σ i 0 + σ ij ) ( K c j ) X i . (60) See Section A.3 for the application to g c g_c g c X , Y X,Y X , Y
Step 2. Second-moment bounds
Lemma 5.8 (Bound for the signed maximum). For the samples and signs above,
E X , Y , σ max c ∈ B X , Y ( r ) ∣ 1 k ∑ i = 1 k ∑ j = 1 r ( σ i 0 + σ i j ) ( K c j ) X i ∣ ≤ 6 2 H log ( 2 r ) k . (61) \mathbb{E}_{X,Y,\sigma}\max_{c\in\mathcal{B}_{X,Y}^{(r)}}\left|\frac{1}{k}\sum_{i=1}^{k}\sum_{j=1}^{r}(\sigma_{i0}+\sigma_{ij})(Kc^j)_{X_i}\right|
\le6\sqrt{2}H\sqrt{\frac{\log(2r)}{k}}. \tag*{(61)} E X , Y , σ c ∈ B X , Y ( r ) max k 1 i = 1 ∑ k j = 1 ∑ r ( σ i 0 + σ ij ) ( K c j ) X i ≤ 6 2 H k log ( 2 r ) . (61) Proof. We first bound the maximum. Fix X , Y , σ X,Y,\sigma X , Y , σ b v b_v b v ∑ j ∣ c v j ∣ \sum_j|c_v^j| ∑ j ∣ c v j ∣ B X , Y ( r ) \mathcal{B}_{X,Y}^{(r)} B X , Y ( r )
b v : = p v + P X ( v ) + P Y ( v ) . b_v:=p_v+P_X(v)+P_Y(v). b v := p v + P X ( v ) + P Y ( v ) . Since K K K c ∈ B X , Y ( r ) c\in\mathcal{B}_{X,Y}^{(r)} c ∈ B X , Y ( r )
∣ ∑ i = 1 k ∑ j = 1 r ( σ i 0 + σ i j ) ( K c j ) X i ∣ = ∣ ∑ v ∑ j = 1 r c v j ∑ i = 1 k ( σ i 0 + σ i j ) K v X i ∣ ≤ ∑ v b v max 1 ≤ j ≤ r ∣ ∑ i = 1 k ( σ i 0 + σ i j ) K v X i ∣ . (62) \begin{aligned}
\left|\sum_{i=1}^{k}\sum_{j=1}^{r}(\sigma_{i0}+\sigma_{ij})(Kc^j)_{X_i}\right|
=
\left|\sum_v\sum_{j=1}^{r}c_v^j\sum_{i=1}^{k}(\sigma_{i0}+\sigma_{ij})K_{vX_i}\right| \\
&\le\sum_v b_v\max_{1\le j\le r}\left|\sum_{i=1}^{k}(\sigma_{i0}+\sigma_{ij})K_{vX_i}\right|. \tag*{(62)}
\end{aligned} i = 1 ∑ k j = 1 ∑ r ( σ i 0 + σ ij ) ( K c j ) X i = v ∑ j = 1 ∑ r c v j i = 1 ∑ k ( σ i 0 + σ ij ) K v X i ≤ v ∑ b v 1 ≤ j ≤ r max i = 1 ∑ k ( σ i 0 + σ ij ) K v X i . (62) Here we used ∑ j ∣ c v j ∣ ≤ b v \sum_j|c_v^j|\le b_v ∑ j ∣ c v j ∣ ≤ b v c ∈ B X , Y ( r ) c\in\mathcal{B}_{X,Y}^{(r)} c ∈ B X , Y ( r ) b v b_v b v
max c ∈ B X , Y ( r ) ∣ ∑ i = 1 k ∑ j = 1 r ( σ i 0 + σ i j ) ( K c j ) X i ∣ ≤ ∑ v p v max j ∣ ∑ i ( σ i 0 + σ i j ) K v X i ∣ \max_{c\in\mathcal{B}_{X,Y}^{(r)}}\left|\sum_{i=1}^{k}\sum_{j=1}^{r}(\sigma_{i0}+\sigma_{ij})(Kc^j)_{X_i}\right|
\le\sum_v p_v\max_j\left|\sum_i(\sigma_{i0}+\sigma_{ij})K_{vX_i}\right| c ∈ B X , Y ( r ) max i = 1 ∑ k j = 1 ∑ r ( σ i 0 + σ ij ) ( K c j ) X i ≤ v ∑ p v j max i ∑ ( σ i 0 + σ ij ) K v X i + ∑ v P X ( v ) max j ∣ ∑ i ( σ i 0 + σ i j ) K v X i ∣ + ∑ v P Y ( v ) max j ∣ ∑ i ( σ i 0 + σ i j ) K v X i ∣ . (63) \quad+\sum_v P_X(v)\max_j\left|\sum_i(\sigma_{i0}+\sigma_{ij})K_{vX_i}\right|
+\sum_v P_Y(v)\max_j\left|\sum_i(\sigma_{i0}+\sigma_{ij})K_{vX_i}\right|. \tag*{(63)} + v ∑ P X ( v ) j max i ∑ ( σ i 0 + σ ij ) K v X i + v ∑ P Y ( v ) j max i ∑ ( σ i 0 + σ ij ) K v X i . (63) We have bounded the maximum over all c c c P X P_X P X P Y P_Y P Y Bound the sum weighted by p p p Since K K K H = ∑ v p v h v H=\sum_v p_vh_v H = ∑ v p v h v v ∈ V v\in V v ∈ V
h v : = ( ∑ u p u K v u 2 ) 1 / 2 . h_v:=\left(\sum_u p_uK_{vu}^2\right)^{1/2}. h v := ( u ∑ p u K v u 2 ) 1/2 . For fixed X X X L 1 L^1 L 1
E σ ∣ ∑ i σ i 0 K v X i ∣ ≤ ( ∑ i K v X i 2 ) 1 / 2 . \mathbb{E}_{\sigma}\left|\sum_i\sigma_{i0}K_{vX_i}\right|\leq\left(\sum_iK_{vX_i}^2\right)^{1/2}. E σ i ∑ σ i 0 K v X i ≤ ( i ∑ K v X i 2 ) 1/2 . The triangle inequality and Massart’s finite-class lemma (Lemma A.4) therefore give
E σ max 1 ≤ j ≤ r ∣ ∑ i ( σ i 0 + σ i j ) K v X i ∣ ≤ E σ ∣ ∑ i σ i 0 K v X i ∣ + E σ max 1 ≤ j ≤ r ∣ ∑ i σ i j K v X i ∣ ≤ ( 1 + 2 log ( 2 r ) ) ( ∑ i K v X i 2 ) 1 / 2 ≤ 2 2 log ( 2 r ) ( ∑ i K v X i 2 ) 1 / 2 . (64) \begin{aligned}
\mathbb{E}_{\sigma}\max_{1\leq j\leq r}\left|\sum_i(\sigma_{i0}+\sigma_{ij})K_{vX_i}\right|
&\leq\mathbb{E}_{\sigma}\left|\sum_i\sigma_{i0}K_{vX_i}\right|+\mathbb{E}_{\sigma}\max_{1\leq j\leq r}\left|\sum_i\sigma_{ij}K_{vX_i}\right|\\
&\leq\left(1+\sqrt{2\log(2r)}\right)\left(\sum_iK_{vX_i}^2\right)^{1/2}\leq2\sqrt{2\log(2r)}\left(\sum_iK_{vX_i}^2\right)^{1/2}. \tag*{(64)}
\end{aligned} E σ 1 ≤ j ≤ r max i ∑ ( σ i 0 + σ ij ) K v X i ≤ E σ i ∑ σ i 0 K v X i + E σ 1 ≤ j ≤ r max i ∑ σ ij K v X i ≤ ( 1 + 2 log ( 2 r ) ) ( i ∑ K v X i 2 ) 1/2 ≤ 2 2 log ( 2 r ) ( i ∑ K v X i 2 ) 1/2 . (64) Taking expectation over X X X
E X , σ max j ∣ ∑ i ( σ i 0 + σ i j ) K v X i ∣ ≤ 2 2 log ( 2 r ) E X ( ∑ i K v X i 2 ) 1 / 2 \mathbb{E}_{X,\sigma}\max_j\left|\sum_i(\sigma_{i0}+\sigma_{ij})K_{vX_i}\right|\leq2\sqrt{2\log(2r)}\mathbb{E}_X\left(\sum_iK_{vX_i}^2\right)^{1/2} E X , σ j max i ∑ ( σ i 0 + σ ij ) K v X i ≤ 2 2 log ( 2 r ) E X ( i ∑ K v X i 2 ) 1/2 ≤ 2 2 log ( 2 r ) ( ∑ i E X K v X i 2 ) 1 / 2 = 2 2 k log ( 2 r ) h v , \leq2\sqrt{2\log(2r)}\left(\sum_i\mathbb{E}_XK_{vX_i}^2\right)^{1/2}=2\sqrt{2k\log(2r)}\,h_v, ≤ 2 2 log ( 2 r ) ( i ∑ E X K v X i 2 ) 1/2 = 2 2 k log ( 2 r ) h v , where the last equality uses E X K v X i 2 = ∑ u p u K v u 2 = h v 2 \mathbb{E}_XK_{vX_i}^2=\sum_up_uK_{vu}^2=h_v^2 E X K v X i 2 = ∑ u p u K v u 2 = h v 2 X i X_i X i p p p
E X , σ ∑ v p v max j ∣ ∑ i ( σ i 0 + σ i j ) K v X i ∣ ≤ 2 2 k log ( 2 r ) ∑ v p v h v = 2 H 2 k log ( 2 r ) . (65) \mathbb{E}_{X,\sigma}\sum_vp_v\max_j\left|\sum_i(\sigma_{i0}+\sigma_{ij})K_{vX_i}\right|\leq2\sqrt{2k\log(2r)}\sum_vp_vh_v=2H\sqrt{2k\log(2r)}. \tag*{(65)} E X , σ v ∑ p v j max i ∑ ( σ i 0 + σ ij ) K v X i ≤ 2 2 k log ( 2 r ) v ∑ p v h v = 2 H 2 k log ( 2 r ) . (65) Bound the sum weighted by P Y P_Y P Y We can use the preceding estimate directly for P Y P_Y P Y Y Y Y X X X σ \sigma σ E Y P Y ( v ) = p v \mathbb{E}_YP_Y(v)=p_v E Y P Y ( v ) = p v (65) gives
E X , Y , σ ∑ v P Y ( v ) max j ∣ ∑ i ( σ i 0 + σ i j ) K v X i ∣ = E X , σ ∑ v p v max j ∣ ∑ i ( σ i 0 + σ i j ) K v X i ∣ ≤ 2 H 2 k log ( 2 r ) . (66) \begin{aligned}
\mathbb{E}_{X,Y,\sigma}\sum_vP_Y(v)\max_j\left|\sum_i(\sigma_{i0}+\sigma_{ij})K_{vX_i}\right|
&=\mathbb{E}_{X,\sigma}\sum_vp_v\max_j\left|\sum_i(\sigma_{i0}+\sigma_{ij})K_{vX_i}\right|\\
&\leq2H\sqrt{2k\log(2r)}. \tag*{(66)}
\end{aligned} E X , Y , σ v ∑ P Y ( v ) j max i ∑ ( σ i 0 + σ ij ) K v X i = E X , σ v ∑ p v j max i ∑ ( σ i 0 + σ ij ) K v X i ≤ 2 H 2 k log ( 2 r ) . (66) Bound the sum weighted by P X P_X P X We can write the P X P_X P X
∑ v P X ( v ) max j ∣ ∑ i ( σ i 0 + σ i j ) K v X i ∣ = 1 k ∑ ℓ = 1 k max j ∣ ∑ i ( σ i 0 + σ i j ) K X ℓ X i ∣ . \sum_vP_X(v)\max_j\left|\sum_i(\sigma_{i0}+\sigma_{ij})K_{vX_i}\right|=\frac{1}{k}\sum_{\ell=1}^k\max_j\left|\sum_i(\sigma_{i0}+\sigma_{ij})K_{X_\ell X_i}\right|. v ∑ P X ( v ) j max i ∑ ( σ i 0 + σ ij ) K v X i = k 1 ℓ = 1 ∑ k j max i ∑ ( σ i 0 + σ ij ) K X ℓ X i . Fix ℓ \ell ℓ X ℓ = u X_\ell=u X ℓ = u K u u = 0 K_{uu}=0 K uu = 0
∑ i ( σ i 0 + σ i j ) K X ℓ X i = ∑ i ≠ ℓ ( σ i 0 + σ i j ) K u X i . \sum_i(\sigma_{i0}+\sigma_{ij})K_{X_\ell X_i}=\sum_{i\ne\ell}(\sigma_{i0}+\sigma_{ij})K_{uX_i}. i ∑ ( σ i 0 + σ ij ) K X ℓ X i = i = ℓ ∑ ( σ i 0 + σ ij ) K u X i . The other X i X_i X i p p p
E X , σ [ max j ∣ ∑ i ( σ i 0 + σ i j ) K X ℓ X i ∣ | X ℓ = u ] \mathbb{E}_{X,\sigma}\left[\max_j\left|\sum_i(\sigma_{i0}+\sigma_{ij})K_{X_\ell X_i}\right|\middle|X_\ell=u\right] E X , σ [ j max i ∑ ( σ i 0 + σ ij ) K X ℓ X i X ℓ = u ] ≤ 2 2 log ( 2 r ) E X [ ( ∑ i ≠ ℓ K u X i 2 ) 1 / 2 ∣ X ℓ = u ] \le2\sqrt{2\log(2r)}\ \mathbb{E}_X\left[\left.\left(\sum_{i\ne\ell}K_{uX_i}^2\right)^{1/2}\right|X_\ell=u\right] ≤ 2 2 log ( 2 r ) E X i = ℓ ∑ K u X i 2 1/2 X ℓ = u ≤ 2 2 log ( 2 r ) ( ( k − 1 ) h u 2 ) 1 / 2 = 2 2 ( k − 1 ) log ( 2 r ) h u . \le2\sqrt{2\log(2r)}\left((k-1)h_u^2\right)^{1/2}=2\sqrt{2(k-1)\log(2r)}\ h_u. ≤ 2 2 log ( 2 r ) ( ( k − 1 ) h u 2 ) 1/2 = 2 2 ( k − 1 ) log ( 2 r ) h u . We remove the conditioning on X ℓ = u X_\ell=u X ℓ = u ℓ \ell ℓ k k k H = ∑ u p u h u H=\sum_u p_u h_u H = ∑ u p u h u
E X , σ ∑ v P X ( v ) max j ∣ ∑ i ( σ i 0 + σ i j ) K v X i ∣ ≤ 2 2 ( k − 1 ) log ( 2 r ) ∑ u p u h u = 2 H 2 ( k − 1 ) log ( 2 r ) ≤ 2 H 2 k log ( 2 r ) . (67) \begin{aligned}
\mathbb{E}_{X,\sigma}\sum_v P_X(v)\max_j\left|\sum_i(\sigma_{i0}+\sigma_{ij})K_{vX_i}\right|\le2\sqrt{2(k-1)\log(2r)}\sum_u p_u h_u \\
&=2H\sqrt{2(k-1)\log(2r)}\le2H\sqrt{2k\log(2r)}. \tag*{(67)}
\end{aligned} E X , σ v ∑ P X ( v ) j max i ∑ ( σ i 0 + σ ij ) K v X i ≤ 2 2 ( k − 1 ) log ( 2 r ) u ∑ p u h u = 2 H 2 ( k − 1 ) log ( 2 r ) ≤ 2 H 2 k log ( 2 r ) . (67) Each of the three unnormalized sums has expected value at most 2 H 2 k log ( 2 r ) 2H\sqrt{2k\log(2r)} 2 H 2 k log ( 2 r ) (63) and dividing by k k k 6 2 H log ( 2 r ) / k 6\sqrt{2}H\sqrt{\log(2r)/k} 6 2 H log ( 2 r ) / k 5.8 5.8 5.8
Putting it together
Corollary 5.9 (Expected error in F K , r F_{K,r} F K , r X 1 , … , X k X_1,\ldots,X_k X 1 , … , X k p p p P X P_X P X
E X ∣ F K , r ( P X ) − F K , r ( p ) ∣ ≤ 48 2 H log ( 2 r ) k . (68) \mathbb{E}_X\left|F_{K,r}(P_X)-F_{K,r}(p)\right|\le48\sqrt{2}H\sqrt{\frac{\log(2r)}{k}}. \tag*{(68)} E X ∣ F K , r ( P X ) − F K , r ( p ) ∣ ≤ 48 2 H k log ( 2 r ) . (68) Proof. Taking expectations in Lemma 5.5 5.5 5.5 q = p q=p q = p s = P X s=P_X s = P X 5.7 5.7 5.7 5.8 5.8 5.8
E X ∣ F K , r ( P X ) − F K , r ( p ) ∣ ≤ E X Δ K , r ( p , P X ) ≤ 8 ⋅ 6 2 H log ( 2 r ) k = 48 2 H log ( 2 r ) k . \mathbb{E}_X\left|F_{K,r}(P_X)-F_{K,r}(p)\right|\le\mathbb{E}_X\Delta_{K,r}(p,P_X)\le8\cdot6\sqrt{2}H\sqrt{\frac{\log(2r)}{k}}=48\sqrt{2}H\sqrt{\frac{\log(2r)}{k}}. E X ∣ F K , r ( P X ) − F K , r ( p ) ∣ ≤ E X Δ K , r ( p , P X ) ≤ 8 ⋅ 6 2 H k log ( 2 r ) = 48 2 H k log ( 2 r ) . This also proves the sampling bound (54) .
Proof of Theorem 5.1. Lemma 5.4 5.4 5.4 ∣ F K , r ( P X ) − F K , r ( p ) ∣ \left|F_{K,r}(P_X)-F_{K,r}(p)\right| ∣ F K , r ( P X ) − F K , r ( p ) ∣ 5.9 5.9 5.9
Technical lemmas
Ledoux–Talagrand contraction
We use the following standard form of the Ledoux–Talagrand contraction in Lemma 2.7 2.7 2.7 [18 ] .
Lemma A.1 (Absolute-value Rademacher contraction). Let T ⊆ R k \mathcal{T}\subseteq\mathbb{R}^k T ⊆ R k g : R → R g:\mathbb{R}\to\mathbb{R} g : R → R 1 1 1 g ( 0 ) = 0 g(0)=0 g ( 0 ) = 0 σ 1 , … , σ k \sigma_1,\ldots,\sigma_k σ 1 , … , σ k
E σ max t ∈ T ∣ 1 k ∑ i = 1 k σ i g ( t i ) ∣ ≤ 2 E σ max t ∈ T ∣ 1 k ∑ i = 1 k σ i t i ∣ . \mathbb{E}_\sigma\max_{t\in\mathcal{T}}\left|\frac{1}{k}\sum_{i=1}^k\sigma_i g(t_i)\right|\le2\mathbb{E}_\sigma\max_{t\in\mathcal{T}}\left|\frac{1}{k}\sum_{i=1}^k\sigma_i t_i\right|. E σ t ∈ T max k 1 i = 1 ∑ k σ i g ( t i ) ≤ 2 E σ t ∈ T max k 1 i = 1 ∑ k σ i t i . Khintchine inequality
We use the following form of the upper L 1 L^1 L 1 [27 ] .
Lemma A.2 (Upper L 1 L^1 L 1 k ≥ 1 k \ge1 k ≥ 1 a 1 , … , a k ∈ R a_1,\ldots,a_k \in\mathbb{R} a 1 , … , a k ∈ R σ 1 , … , σ k ∈ { ± 1 } \sigma_1,\ldots,\sigma_k \in\{\pm1\} σ 1 , … , σ k ∈ { ± 1 }
E σ ∣ ∑ i = 1 k σ i a i ∣ ≤ ( ∑ i = 1 k a i 2 ) 1 / 2 . \mathbb{E}_{\sigma}\left|\sum_{i=1}^{k}\sigma_i a_i\right| \le\left(\sum_{i=1}^{k}a_i^2\right)^{1/2}. E σ i = 1 ∑ k σ i a i ≤ ( i = 1 ∑ k a i 2 ) 1/2 . Proof. This L 1 L^1 L 1 E ∣ Z ∣ ≤ ( E Z 2 ) 1 / 2 \mathbb{E}|Z| \le(\mathbb{E}Z^2)^{1/2} E ∣ Z ∣ ≤ ( E Z 2 ) 1/2 Z = ∑ i σ i a i Z = \sum_i \sigma_i a_i Z = ∑ i σ i a i E Z 2 = ∑ i a i 2 \mathbb{E}Z^2 = \sum_i a_i^2 E Z 2 = ∑ i a i 2 □ \square □
Vector contraction
We use the following absolute-value consequence of Maurer’s vector contraction inequality in Lemma 5.7; see [Maul6, Corollary 1].
Lemma A.3 (Absolute-value consequence of Maurer’s inequality). Let T ⊂ ( R m ) k T \subset(\mathbb{R}^m)^k T ⊂ ( R m ) k 0 ∈ T 0 \in T 0 ∈ T t = ( t 1 , … , t k ) t=(t_1,\ldots,t_k) t = ( t 1 , … , t k ) t i = ( t i 1 , … , t i m ) ∈ R m t_i=(t_{i1},\ldots,t_{im}) \in\mathbb{R}^m t i = ( t i 1 , … , t im ) ∈ R m ϕ : R m → R \phi:\mathbb{R}^m \to\mathbb{R} ϕ : R m → R L 0 L_0 L 0 ϕ ( 0 ) = 0 \phi(0)=0 ϕ ( 0 ) = 0 τ i \tau_i τ i σ i ℓ \sigma_{i\ell} σ i ℓ 1 ≤ i ≤ k 1 \le i \le k 1 ≤ i ≤ k 1 ≤ ℓ ≤ m 1 \le\ell\le m 1 ≤ ℓ ≤ m
E τ max t ∈ T ∣ 1 k ∑ i = 1 k τ i ϕ ( t i ) ∣ ≤ 2 2 L 0 E σ max t ∈ T ∣ 1 k ∑ i = 1 k ∑ ℓ = 1 m σ i ℓ t i ℓ ∣ . (69) \mathbb{E}_{\tau}\max_{t\in T}\left|\frac{1}{k}\sum_{i=1}^{k}\tau_i\phi(t_i)\right|
\le2\sqrt{2}L_0\mathbb{E}_{\sigma}\max_{t\in T}\left|\frac{1}{k}\sum_{i=1}^{k}\sum_{\ell=1}^{m}\sigma_{i\ell}t_{i\ell}\right|. \tag*{(69)} E τ t ∈ T max k 1 i = 1 ∑ k τ i ϕ ( t i ) ≤ 2 2 L 0 E σ t ∈ T max k 1 i = 1 ∑ k ℓ = 1 ∑ m σ i ℓ t i ℓ . (69) Proof. The finite-dimensional case of [Maul6, Corollary 1], applied to f t ( i ) = t i f_t(i)=t_i f t ( i ) = t i h i = ϕ h_i=\phi h i = ϕ k k k
E τ max t ∈ T 1 k ∑ i = 1 k τ i ϕ ( t i ) ≤ 2 L 0 E σ max t ∈ T 1 k ∑ i = 1 k ∑ ℓ = 1 m σ i ℓ t i ℓ . \mathbb{E}_{\tau}\max_{t\in T}\frac{1}{k}\sum_{i=1}^{k}\tau_i\phi(t_i)
\le\sqrt{2}L_0\mathbb{E}_{\sigma}\max_{t\in T}\frac{1}{k}\sum_{i=1}^{k}\sum_{\ell=1}^{m}\sigma_{i\ell}t_{i\ell}. E τ t ∈ T max k 1 i = 1 ∑ k τ i ϕ ( t i ) ≤ 2 L 0 E σ t ∈ T max k 1 i = 1 ∑ k ℓ = 1 ∑ m σ i ℓ t i ℓ . For each sign vector τ \tau τ 0 ∈ T 0 \in T 0 ∈ T ϕ ( 0 ) = 0 \phi(0)=0 ϕ ( 0 ) = 0 t = 0 t=0 t = 0 τ \tau τ − τ -\tau − τ
E τ max t ∈ T ∣ 1 k ∑ i = 1 k τ i ϕ ( t i ) ∣ ≤ 2 E τ max t ∈ T 1 k ∑ i = 1 k τ i ϕ ( t i ) . \mathbb{E}_{\tau}\max_{t\in T}\left|\frac{1}{k}\sum_{i=1}^{k}\tau_i\phi(t_i)\right|
\le2\mathbb{E}_{\tau}\max_{t\in T}\frac{1}{k}\sum_{i=1}^{k}\tau_i\phi(t_i). E τ t ∈ T max k 1 i = 1 ∑ k τ i ϕ ( t i ) ≤ 2 E τ t ∈ T max k 1 i = 1 ∑ k τ i ϕ ( t i ) . Combining these bounds and inserting an absolute value in the linear sum proves the claim. □ \square □
Application to r r r The function ϕ ( z 0 , z 1 , … , z r ) = z 0 − min 1 ≤ j ≤ r z j \phi(z_0,z_1,\ldots,z_r)=z_0-\min_{1\le j\le r}z_j ϕ ( z 0 , z 1 , … , z r ) = z 0 − min 1 ≤ j ≤ r z j
∣ ϕ ( z ) − ϕ ( w ) ∣ ≤ ∣ z 0 − w 0 ∣ + max 1 ≤ j ≤ r ∣ z j − w j ∣ ≤ ∣ z 0 − w 0 ∣ + ( ∑ j = 1 r ∣ z j − w j ∣ 2 ) 1 / 2 ≤ 2 ∥ z − w ∥ 2 . \begin{aligned}
|\phi(z)-\phi(w)| \le|z_0-w_0|+\max_{1\le j\le r}|z_j-w_j| \\
&\le|z_0-w_0|+\left(\sum_{j=1}^{r}|z_j-w_j|^2\right)^{1/2}
\le\sqrt{2}\|z-w\|_2.
\end{aligned} ∣ ϕ ( z ) − ϕ ( w ) ∣ ≤ ∣ z 0 − w 0 ∣ + 1 ≤ j ≤ r max ∣ z j − w j ∣ ≤ ∣ z 0 − w 0 ∣ + ( j = 1 ∑ r ∣ z j − w j ∣ 2 ) 1/2 ≤ 2 ∥ z − w ∥ 2 . To apply Lemma A.3 to the function g c g_c g c g c ( v ) = ϕ ( f c ( v ) ) g_c(v)=\phi(f_c(v)) g c ( v ) = ϕ ( f c ( v ))
f c ( v ) = ( ∑ ℓ = 1 r ( K c ℓ ) v , ( K c 1 ) v , … , ( K c r ) v ) . f_c(v)=\left(\sum_{\ell=1}^{r}(Kc^\ell)v,(Kc^1)v,\ldots,(Kc^r)v\right). f c ( v ) = ( ℓ = 1 ∑ r ( K c ℓ ) v , ( K c 1 ) v , … , ( K c r ) v ) . Coordinate 0 stores the sum of all part contributions, while coordinate j j j ( K c j ) v (Kc^j)v ( K c j ) v j j j 2 \sqrt{2} 2 r r r
Apply the lemma with m = r + 1 m=r+1 m = r + 1 0 , … , r 0,\ldots,r 0 , … , r i i i
∑ j = 0 r σ i j ( f c ( X i ) ) j = σ i 0 ∑ j = 1 r ( K c j ) X i + ∑ j = 1 r σ i j ( K c j ) X i = ∑ j = 1 r ( σ i 0 + σ i j ) ( K c j ) X i . \begin{aligned}
\sum_{j=0}^{r}\sigma_{ij}(f_c(X_i))_j=\sigma_{i0}\sum_{j=1}^{r}(Kc^j)X_i+\sum_{j=1}^{r}\sigma_{ij}(Kc^j)X_i \\
&=\sum_{j=1}^{r}(\sigma_{i0}+\sigma_{ij})(Kc^j)X_i.
\end{aligned} j = 0 ∑ r σ ij ( f c ( X i ) ) j = σ i 0 j = 1 ∑ r ( K c j ) X i + j = 1 ∑ r σ ij ( K c j ) X i = j = 1 ∑ r ( σ i 0 + σ ij ) ( K c j ) X i . Thus each part contribution receives the sign σ i 0 \sigma_{i0} σ i 0 σ i j \sigma_{ij} σ ij L 0 = 2 L_0=\sqrt{2} L 0 = 2 2 2 L 0 = 4 2\sqrt{2}L_0=4 2 2 L 0 = 4
Massart’s finite-class lemma
We use the following form of Massart’s finite-class lemma in Lemma 5.8; see [21 Theorem 3.7] .
Lemma A.4 (Absolute-value consequence of Massart’s lemma). Let m , r ≥ 1 m,r\ge1 m , r ≥ 1 a i j ∈ R a_{ij}\in\mathbb{R} a ij ∈ R σ i j ∈ { ± 1 } \sigma_{ij}\in\{\pm1\} σ ij ∈ { ± 1 } 1 ≤ i ≤ m 1\le i\le m 1 ≤ i ≤ m 1 ≤ j ≤ r 1\le j\le r 1 ≤ j ≤ r
E σ max 1 ≤ j ≤ r ∣ ∑ i = 1 m σ i j a i j ∣ ≤ 2 log ( 2 r ) max 1 ≤ j ≤ r ( ∑ i = 1 m a i j 2 ) 1 / 2 . \mathbb{E}_{\sigma}\max_{1\le j\le r}\left|\sum_{i=1}^{m}\sigma_{ij}a_{ij}\right|\le\sqrt{2\log(2r)}\max_{1\le j\le r}\left(\sum_{i=1}^{m}a_{ij}^{2}\right)^{1/2}. E σ 1 ≤ j ≤ r max i = 1 ∑ m σ ij a ij ≤ 2 log ( 2 r ) 1 ≤ j ≤ r max ( i = 1 ∑ m a ij 2 ) 1/2 . Proof. Set T : = { ± b j : 1 ≤ j ≤ r } \mathcal{T}:=\{\pm b^j:1\le j\le r\} T := { ± b j : 1 ≤ j ≤ r } b j ∈ R m r b^j\in\mathbb{R}^{mr} b j ∈ R m r ( i , ℓ ) (i,\ell) ( i , ℓ ) b i j j = a i j b^j_{ij}=a_{ij} b ij j = a ij b i ℓ j = 0 b^j_{i\ell}=0 b i ℓ j = 0 ℓ ≠ j \ell\ne j ℓ = j [21 Theorem 3.7] to T \mathcal{T} T 1 / ( m r ) 1/(mr) 1/ ( m r )
E σ max 1 ≤ j ≤ r ∣ ∑ i = 1 m σ i j a i j ∣ = E σ max t ∈ T ∑ i = 1 m ∑ ℓ = 1 r σ i ℓ t i ℓ ≤ 2 log ∣ T ∣ max t ∈ T ∥ t ∥ 2 \mathbb{E}_{\sigma}\max_{1\le j\le r}\left|\sum_{i=1}^{m}\sigma_{ij}a_{ij}\right|
=\mathbb{E}_{\sigma}\max_{t\in\mathcal{T}}\sum_{i=1}^{m}\sum_{\ell=1}^{r}\sigma_{i\ell}t_{i\ell}
\le\sqrt{2\log|\mathcal{T}|}\max_{t\in\mathcal{T}}\|t\|_2 E σ 1 ≤ j ≤ r max i = 1 ∑ m σ ij a ij = E σ t ∈ T max i = 1 ∑ m ℓ = 1 ∑ r σ i ℓ t i ℓ ≤ 2 log ∣ T ∣ t ∈ T max ∥ t ∥ 2 ≤ 2 log ( 2 r ) max 1 ≤ j ≤ r ( ∑ i = 1 m a i j 2 ) 1 / 2 . \le\sqrt{2\log(2r)}\max_{1\le j\le r}\left(\sum_{i=1}^{m}a_{ij}^{2}\right)^{1/2}. ≤ 2 log ( 2 r ) 1 ≤ j ≤ r max ( i = 1 ∑ m a ij 2 ) 1/2 . Here ∣ T ∣ ≤ 2 r |\mathcal{T}|\le2r ∣ T ∣ ≤ 2 r ∥ b j ∥ 2 2 = ∑ i a i j 2 \|b^j\|_2^2=\sum_i a_{ij}^2 ∥ b j ∥ 2 2 = ∑ i a ij 2
AI disclosure
We used ChatGPT as a writing assistant to improve the writing and clarity of the paper, and Perplexity to help identify relevant literature we might have missed. The results and proof ideas were developed by the authors, who checked all AI-assisted content and are responsible for the paper’s accuracy and originality.
