The cut norm and Sampling Lemmas for unbounded kernels

Fekete, Panna Tímea and Kunszenti-Kovács, Dávid (2024) The cut norm and Sampling Lemmas for unbounded kernels. ANALYSIS MATHEMATICA. ISSN 0133-3852 (Submitted)

Preview

Text arxiv-preprint-2203.07581v2.pdf - Submitted Version Download (365kB) | Preview

Abstract

Generalizing the bounded kernel results of Borgs, Chayes, Lovász, Sós and Vesztergombi (2008), we prove two Sampling Lemmas for unbounded kernels with respect to the cut norm. On the one hand, we show that given a (symmetric) kernel U∈Lp([0,1]2) for some 3<p<∞, the cut norm of a random k-sample of U is with high probability within O(k−14+14p) of the cut norm of U. The cut norm of the sample has a strong bias to being larger than the original, allowing us to actually obtain a stronger high probability bound of order O(k−12+1p+ε) for how much smaller it can be (for any p>2 here). These results are then partially extended to the case of vector valued kernels. On the other hand, we show that with high probability, the k-samples are also close to U in the cut metric, albeit with a weaker bound of order O((lnk)−12+12p) (for any appropriate p>2). As a corollary, we obtain that whenever U∈Lp with p>4, the k-samples converge almost surely to U in the cut metric as k→∞.

Actions (login required)

Edit Item