Fundamental Limits of Private Covariance Estimation under Vertical Partitioning

Different features, matched observations

We study covariance estimation when two parties hold different features of the same observations. Neither party sees complete records, making relationships between their features difficult to estimate. We design separate releases satisfying pure differential privacy that allow an analyst to estimate the full covariance matrix without interaction between the parties.

For mean-zero sub-Gaussian data, we prove matching upper and lower error bounds up to logarithmic factors among noninteractive protocols. The bounds identify each party’s privacy cost and remain sharp when the parties hold very different numbers of features or use different privacy budgets.

One matrix · two data holders

The information neither party observes alone

Select a block to explore

Within a partyAcross parties

Cross-party covariance

Linking X and Y

These entries describe how X’s features vary with Y’s. Neither party can compute them from its own feature table alone.

X Private releaseY Private release

Analyst estimates Σ

Both parties hold the same matched records, split by features. The analyst estimates all four blocks from their separate pure-DP releases.

Related paper

2026

Fundamental Limits of Private Covariance Estimation under Vertical Partitioning

R. Zare Moayedi^*, P. Halvachi^*, A. Najafi and M. H. Yassaee

Preprint

BibTeX

@unpublished{raoof_private_splt,
  title = {{Fundamental Limits of Private Covariance Estimation under Vertical Partitioning}},
  author = {Zare Moayedi, Raoof and Halvachi, Paniz and Najafi, Amir and Yassaee, Mohammad Hossein},
  year = {2026},
  note = {Preprint}
}