Covariance loss, Szemeredi regularity, and differential privacy

01/06/2023

∙

by   March Boedihardjo, et al.

∙

0

∙

share

We show how randomized rounding based on Grothendieck's identity can be used to prove a nearly tight bound on the covariance loss–the amount of covariance that is lost by taking conditional expectation. This result yields a new type of weak Szemeredi regularity lemma for positive semidefinite matrices and kernels. Moreover, it can be used to construct differentially private synthetic data.