Near-square-root logarithmic integrality gaps for uniform sparsest cut

Proof. The integral defining c_* converges: its integrand is bounded near zero and is at most 1/(2t^2) for t\ge1. Scaling the integration variable shows that the first component of the squared distance, if integrated over all positive scales, would equal c_*\sqrt m\,|\theta-\eta|. The omitted scales contribute at most

The squared distance in all the additional components is at most 4\varepsilon SN\log(b/a). Consequently the error is at most

which is at most m^{-37} for sufficiently large m.□

Proof. We first identify the profile that the preliminary extension should reproduce. For |\theta|,|\eta|\le3\sqrt m, put w=(\eta-\theta)/\sigma. Differentiation in \theta of the Gaussian term in (3.2) gives the vector

The empirical approximation in Lemma 1 suggests replacing w e^{-|w|^2/2} by N^{-1}\sum_i g_{s,i}\sin\langle g_{s,i},w\rangle. We realize this profile using the auxiliary Fourier components. Define A_s^0(\theta)e_i to be supported in summand (s,i) of \Hh, where it is the function

Its profile is

Since u_{s,i}=g_{s,i}/\sqrt m, the profile of A_s^0J_s is represented by the vector

Thus A_s^0J_s has the intended empirical profile. Set R_s=Dp-A_s^0J_s; we now bound its pairings against the common features before correcting the extension on the chart subspace. For the parameters under consideration, |w|\le6\sqrt m/a<m^{42}. Thus Lemma 1 bounds the difference between these vectors by 2\log(b/a). The gradient of the second term of (3.2) has norm at most

It follows that

Now define

The identity J_s^+J_s=I proves (3.4). Combining (3.7), (3.8), and the column bound |J_s^+e_i|\le4m/N from (2.5) proves (3.5).

For completeness, the required Hilbert norm bounds have ample polynomial slack. Differentiation under the Hilbert space formulas is valid to every order, because a>0 and Gaussian moments of every order are finite. For j=0,1,2, the squared multilinear derivative norm of the first component of p is at most

and that of all the additional components together is at most

Using \E|G|^2=m and \E|G|^4=m(m+2), these estimates give \|D^jp\|_{\op}\le m^{110} for 0\le j\le2. Bounding an operator by \sqrt N times its largest column norm gives

In particular, these two quantities are at most m^{110} and m^{150}, respectively. Substitute these bounds in (3.9), together with R_s=Dp-A_s^0J_s, its derivative, and \|J_s\|_{\op}\le2\sqrt N and \|J_s^+\|_{\op}\le2\sqrt{m/N}. The projection I-J_sJ_s^+ has norm at most one; the last expression in (3.9) and its derivative therefore bound all five quantities in (3.6) by m^{300} for sufficiently large m.□

Proof. For x=X_s(\theta), rounding and (2.5) give

In particular, |J_s^+x|\le3\sqrt m. By (3.6) and (3.10),

The change in a squared distance caused by the two errors in (3.18) is at most m^{610}\tau, since |p(\theta)|\le m^{300}. Therefore Lemma 2 gives (3.16); its last inequality follows directly from (3.1).

Choose parameter representatives in U for v,z,y. Apply (3.16) to their three pairs and use

The corresponding expression for the ordinary Euclidean distances of the three representatives is nonnegative by the triangle inequality. The total error is at most 3r/10, proving (3.14).

For the local estimate, we integrate coordinate profiles so that the bound scales with \|x-x'\|_1. Consider the segment joining x to x'. Every point \xi on this segment satisfies |Q_s\xi|\le\sqrt N\tau and |J_s^+\xi|\le3\sqrt m, by convexity and (3.17). Differentiating (3.10) and using (3.4) gives the exact identity

The operator norm of the second term is at most 2m^{300}\sqrt m\tau\le m^{305}\tau. For a vertex y=v_t(\eta), replace P_y by p(\eta) using (3.18). Equations (3.5) and (3.6) then imply, throughout this segment,

The same bound holds with P_z in place of P_y. Integrating (3.19) along the segment and summing the absolute coordinate increments proves (3.15) after choosing a sufficiently large absolute C_0.□

Proof. We use the convention e^{-\infty}=0. Define a Gram matrix by

This matrix is positive semidefinite. Indeed, in one coordinate the map t\mapsto\mathbf1_{[b,t]} into L_2 has squared distance |t-t'|, where b is a fixed lower bound on the finitely many coordinate values. Direct sums and scaling show that an \ell_1 distance is squared Hilbertian. For finitely many Hilbert vectors h_v, the kernel

is positive semidefinite: G is a standard Gaussian in their finite linear span, and the cosine is the inner product of the corresponding (\cos,\sin) pairs. This is the Gaussian-kernel criterion of Schoenberg [21], here in its elementary finite form. The kernels in (4.4) are block diagonal across charts; integration preserves positive semidefiniteness. Thus the specified Gram matrix has a Hilbert realization.

The extended distance \delta satisfies the triangle inequality, including triples meeting different charts. Consequently, for a=\delta(v,z) and b=\delta(y,z),

For t=\min\{r,a,b\}, this product is at least (1-e^{-1})^2 when 0<l<t. Equation (4.4) therefore gives

Together with (4.1), this proves (3.13) for Z_v=(P_v,q_v).

The diagonal entries of (4.4) are 4r, which proves (4.2). Finally, 1-e^{-s}\le\min\{1,s\} and

give (4.3). The assertion at distance zero follows directly from (4.2).□

Proof. Let P_v and L=C_0\log m be as in Lemma 4. Within a chart set

and put \delta=\infty between different charts. Equation (3.14) bounds every P-angle below by -r. Equation (3.15) also bounds it below by -\delta(v,z) whenever v,z are in the same chart, and by -\delta(y,z) whenever y,z are in the same chart, after swapping the two arguments of the inner product. Thus the hypothesis of Lemma 5 holds. Use its vectors q_v and set

This is a negative-type semimetric. The bound |q_v-q_w|^2\le8r and (3.16) prove (4.5).

Taking y=v in (3.15) gives |P_v-P_z|^2\le\delta(v,z). If \|x-x'\|_1=\tau, then

Equation (4.3) now proves (4.6).

We next count the rounded labels. Since |u_{s,i}|\le2, a hyperplane \langle u_{s,i},\theta\rangle=k\tau meeting U has |k\tau|<4\sqrt m. Hence at most

threshold hyperplanes meet U in a chart. An arrangement of H hyperplanes in \R^m has at most \sum_{j=0}^m\binom Hj full-dimensional regions (see [22]). This follows by induction: an added hyperplane creates at most as many new regions as the preceding hyperplanes cut out on it. The labels are constant on the regions, and their intersections with the convex cube U are connected. Therefore

because H is bounded by a fixed power of m. The diameter bound in (4.7) follows from (4.5) and \operatorname{diam}(U)=4\sqrt m.

Finally, for independent uniform parameters on T,

It follows that \E|\theta-\eta|\ge\sqrt m/3. Equation (4.5) gives \E d(v_1(\theta),v_1(\eta))\ge c_*m/3-Cr, proving (4.8) for sufficiently large m.□

Proof. Write \Phi for the standard Gaussian distribution function, set \psi(t)=2\Phi(t)-1, and let \Psi:\R^m\to T apply \psi coordinatewise. If G,G' are independent standard Gaussian vectors in \R^m, then \Psi(G),\Psi(G') are independent and uniform on T. For 0\le t\le\pi/2, put

At each fixed time, Y(t) and Y'(t) are independent standard Gaussian vectors. Consequently, conditioning on Y(t) gives

because \sup|\psi'|=\sqrt{2/\pi}. The fundamental theorem of calculus, followed by Tonelli’s theorem, bounds the expected difference between the endpoints by the integral of the expected absolute derivative. The distribution of \Psi(Y(t)) is uniform on T for every t, so integration over [0,\pi/2] proves (5.2). All the integrands are integrable: \nabla h is bounded on \overline T, and Gaussian vectors have finite first moments.□

Proof of Proposition 2. We use r=m^{-8} and \tau=m^{-2000} as in Proposition 1. For each chart, define

and extend f_s by zero outside U. Set f_s=0 also on the threshold hyperplanes and on \partial U. These are bounded, compactly supported functions because V is finite. The macroscopic estimate in Proposition 1 implies

Smoothing. Fix an even, nonnegative function \rho\in C_c^\infty((-1,1)) with \int_\R\rho=1. Set \lambda=m^{-2} and

The functions H_s:\R^m\to\R^D are smooth. For sufficiently large m, the support of x\mapsto\kappa_\lambda(\theta-x) lies in U whenever \theta\in\overline T. Also

Every displacement in the support of \kappa_\lambda has Euclidean norm at most \sqrt m\lambda. Thus (5.4) gives

Since f_s-f_1 vanishes outside U, (5.3) bounds its \ell_1 norm by Cr almost everywhere on \R^m. Differentiating the convolution therefore yields, for every \theta\in T and every j,

The derivative carried by each family of interfaces. Fix a chart s and abbreviate u_i=u_{s,i}. Its interfaces are contained in the hyperplanes

Only finitely many of these hyperplanes meet U. At almost every point of Q_{i,k}\cap U, let \Delta_{i,k}(x)\in\R^D denote the value of f_s on the side of increasing \langle u_i,x\rangle minus its value on the opposite side. This is well-defined away from intersections with the other interface hyperplanes. By the nonparallelism in Lemma 1, those intersections have zero (m-1)-dimensional measure. The two labels at such an interface differ by \tau e_i, so the adjacent-label estimate in Proposition 1 gives

For completeness, the distributional gradient of each scalar component of f_s on U is the vector-valued measure

Indeed, test against a smooth function compactly supported in U and integrate by parts on each polyhedral cell. The cell interiors contribute nothing because f_s is constant there. The two contributions on each shared facet combine into the jump times the unit normal u_i/|u_i|; lower-dimensional intersections have zero facet measure. The test function vanishes near \partial U, so there is no contribution from the outer boundary.

For \theta\in T, the kernel \kappa_\lambda(\theta-\cdot) is a smooth test function compactly supported in U. Convolving (5.8) with this kernel gives, for every component \alpha,

where the vector coefficient b_{s,i}(\theta)\in\R^D is

This identity holds at every \theta\in T: distributional convolution agrees with the classical derivative of the smooth function H_s.

We claim that the coefficients satisfy the pointwise budget

To establish it, fix u=u_{s,i} and \theta, and let Z have density x\mapsto\kappa_\lambda(\theta-x). Write h for the density of the real random variable \langle u,Z\rangle. The coarea formula for this linear functional states that

The lower bound |u|\ge1/2 in Lemma 1 supplies a coordinate j with |u_j|\ge1/(2\sqrt m). Conditional on the other coordinates of Z, the variable \langle u,Z\rangle has a translated, possibly reflected copy of the one-dimensional density \rho, scaled by \lambda|u_j|. Its derivative has L_1 norm \|\rho'\|_{L_1}/(\lambda|u_j|). Taking the mixture over the other coordinates shows that h is continuously differentiable, compactly supported, and satisfies

For any nonnegative, continuously differentiable, compactly supported density h, comparison on each interval [k\tau,(k+1)\tau] gives

Summing and using (5.12), we obtain

for all sufficiently large m. Because the convolution kernel is nonnegative and is supported inside U, the triangle inequality in (5.10), followed by (5.7) and (5.13), proves (5.11).

Combining the charts. Fix \theta\in T and a component \alpha, and put a_\alpha=\nabla H_{1,\alpha}(\theta). If a_\alpha\ne0, the direction property in Lemma 1 gives at least S/2 charts s such that

For each such chart, (5.9) implies

All terms on the right are nonnegative. Summing over the good charts and then enlarging that sum to all charts therefore gives

For a_\alpha=0 the same inequality holds trivially. The good charts may depend on \alpha and \theta; (5.14) removes that dependence before we sum over components.

For each s, the Euclidean norm is at most the sum of absolute coordinates, so (5.6) gives

Sum (5.14) over \alpha and apply this bound and (5.11). We obtain at every \theta\in T

where mr/\lambda=m^{-5}.

Finally, apply Lemma 6 to every component of H_1 and sum. Equation (5.15) yields

The expected distance for f_1 exceeds this by at most 2C(m\lambda+r), by (5.5). Since m\lambda=m^{-1}, this additional term is absorbed into the same bound. The definition of f_1 now proves (5.1).□

Proof. Let \mathcal S be the finite collection of nonempty proper subsets of [n]. For S\in\mathcal S, write \delta_S(i,j)=|\mathbf 1_S(i)-\mathbf 1_S(j)|. Consider the finite linear program.¹

It is feasible by taking every t_S=0. For any feasible t, the map F_t(i)=(t_S\mathbf 1_S(i))_{S\in\mathcal S} takes values in \ell_1^{|\mathcal S|} and is a contraction for d. Its sum of distances over unordered pairs is exactly the objective in (6.3). Consequently (6.1) bounds the primal optimum by n^2b/2. The primal optimum is attained: for each S\in\mathcal S and any pair separated by S, feasibility implies 0\leq t_S\leq d(i,j), so its feasible region is closed and bounded.

The dual of (6.3), with one nonnegative variable c_{ij} for each unordered pair, is

Here the cut sum counts each separated unordered pair once. The dual is feasible, for example with c_{ij}=1 for every pair. Finite-dimensional linear programming duality therefore gives an optimal dual solution C satisfying

Its cut constraints give \OPT(C)\geq1 with exactly unit pair demands.

Set D=\sum_{i<j}d(i,j)\geq n^2a/2>0. If d(i,j)=|z_i-z_j|^2 in a Hilbert space, the vectors z_i/\sqrt D give the feasible normalized SDP distances d(i,j)/D. The span of the finitely many z_i has dimension at most n, so these vectors can be realized in \R^n. The triangles are preserved by normalization, and (6.5) gives \GL(C)\leq b/a.

Finally, the graph of pairs with c_{ij}>0 is connected: otherwise the vertex set of one component would violate a cut constraint in (6.4). Choose a spanning tree \mathcal T in this graph and put \gamma=\min_{\{i,j\}\in\mathcal T}c_{ij}>0. For any feasible SDP distance array d', the triangle inequalities along tree paths imply

Hence its objective is at least \gamma/\binom n2>0. This proves \GL(C)>0, including when the original semimetric d has zero distances between distinct vertices.□

Proof of Lemma 1. Choose all the g_{s,i} independently with the standard Gaussian distribution on \R^m. We show that the required events hold simultaneously with probability tending to one as m\to\infty.

We first record the elementary estimates used below. For a standard Gaussian G in \R^m,

Indeed, rotation reduces the first identity to the one-dimensional cosine transform. Gaussian integration by parts gives the differential equation \phi'(t)=-t\phi(t) for that transform, with \phi(0)=1. Differentiating the first identity with respect to w gives the second; the finite first Gaussian moment justifies this differentiation. Also, exponential Markov inequalities applied to \E e^{t|G|^2}=(1-2t)^{-m/2}, for t<1/2, give for an absolute c>0

We will use the following bounded-variable estimate, a form of Hoeffding’s inequality [9]. If X_1,\ldots,X_n are independent real random variables with |X_j|\le B, then, for 0<u\le B,

For completeness, Taylor expansion, the vanishing first centered moment, and |X_j-\E X_j|\le2B give \E e^{t(X_j-\E X_j)}\le e^{C t^2B^2} when |t|\le1/(2B). Independence and exponential Markov, with t a sufficiently small constant multiple of u/B^2, give both tails in (A.3).

To obtain (2.2), truncate each Gaussian summand on the event |G|>2\sqrt m. By Cauchy–Schwarz and (A.2), uniformly in w,

after decreasing the positive constant c' and taking m large. For a fixed unit vector v and fixed w, the scalar truncated summand

has absolute value at most 2\sqrt m. Thus (A.3), with n=N and u=1/(2\sqrt m), bounds its empirical-mean deviation probability by 2e^{-cN/m^2}.

Choose a 1/8-net \mathcal V of the unit sphere and an m^{-3}-net \mathcal W of the ball of radius m^{42}. The usual disjoint-ball packing argument gives

Union bound the preceding scalar deviations over s, v\in\mathcal V, and w\in\mathcal W. The failure probability tends to zero, since N/m^2=m^4. On the resulting event, for every s and w\in\mathcal W, the vector deviation from its truncated expectation is at most 4/(7\sqrt m): bounds on inner products with a 1/8-net control the Euclidean norm with factor 8/7.

Each truncated empirical vector function is 4m-Lipschitz in w, because the operator norm of its derivative is at most the average of the truncated |g_{s,i}|^2. The function w\mapsto we^{-|w|^2/2} is 2-Lipschitz. Consequently the bias bound (A.4) and interpolation from \mathcal W give, uniformly on the whole ball, an error at most

for all sufficiently large m. This proves the desired approximation for the truncated samples.

The covariance estimate follows from the same argument with quadratic forms. For a fixed unit vector v, the variable \langle v,G\rangle^2\mathbf 1_{\{|G|\le2\sqrt m\}} is bounded by 4m, and its expectation differs from 1 by at most

where constants can again be adjusted, since \E\langle v,G\rangle^4=3. Apply (A.3) with u=1/8, and union bound over s and v\in\mathcal V. With probability tending to one, every truncated empirical covariance matrix M_s satisfies

Here we used the elementary symmetric-matrix net estimate \|A\|_{\op}\le(1-2\rho)^{-1}\max_{v\in\mathcal V}|\langle Av,v\rangle| for a sphere net of radius \rho<1/2.

By (A.2), all SN=m^9 original Gaussian samples satisfy (2.1) with probability tending to one. On this event the truncations change no sample, so the preceding conclusions establish the first two assertions. Pairwise nonparallelism within each family holds almost surely.

It remains to establish (2.3). For a fixed unit vector v, the one-dimensional Gaussian tail bound gives

Call such an index s bad for v. Before any conditioning, these bad-index events are independent across s. Therefore the probability that at least S/2 indices are bad for this fixed v is at most

Take a sphere net of radius 1/m, with cardinality at most (1+2m)^m, and union bound this last estimate over its points. The resulting failure probability tends to zero. Finally intersect with the already established norm event. If v_0 is a net point with |v-v_0|\le1/m, then

for every s,i. Every chart good for v_0 consequently satisfies (2.3) for v, with C=11 for all sufficiently large m. This argument uses independence only for the unconditioned Gaussian samples. A final union bound intersects this event with the preceding high-probability events and proves the lemma.□