When analyzing private data, understanding the spread of the data (the covariance) is usually needed. If the spread is known in advance, algorithms can achieve high accuracy regardless of the number of measurements (dimensions). But if the spread is unknown, the data's hidden structure cannot be exploited without cost.
This work proves that when the spread is unknown, the error can be much larger, up to a factor of sqrt(d/n) for small samples, and even larger for diagonal spread. The authors show that the algorithm must effectively learn the spread from the data, which requires many samples.
This matters because it means private data analysis cannot automatically take advantage of low-dimensional structure in high-dimensional data unless the spread is known. Practitioners must account for this extra cost when designing privacy-preserving systems.