Differentially Private Approximation of the John Ellipsoid
Published in (under review)
We study the problem of approximating the John ellipsoid under differential privacy and develop a projected multiplicative-weights framework that controls the influence of individual constraints while preserving strong geometric guarantees. Our private algorithm perturbs weighted covariance matrices with Gaussian noise and, under a mild structural assumption on the data, achieves utility guarantees comparable to its non-private counterpart. The framework also extends to minimum-volume enclosing ellipsoids through geometric duality.
Recommended citation: Mahpud, Bar; Sheffet, Or; Omer, Daniel. (2026). "Differentially Private Approximation of the John Ellipsoid." (under review).
Download Paper | Download Bibtex