Differentially private method approximates shapes inside data constraints
Differentially Private Approximation of the John Ellipsoid
Data Structures and Algorithms
Summary
This paper deals with finding the best-fitting shape called the John ellipsoid inside a geometric space defined by many constraints while keeping the input data private. The authors create an algorithm that protects individuals' data by adding controlled noise to the calculations, ensuring privacy without losing much accuracy. Their method builds on previous work but adds the ability to do this privately and efficiently. It also works for a related problem of fitting the smallest ellipsoid around a set of points.
What this means in practice
- •For data privacy engineers: Implement privacy-preserving geometric approximations for sensitive dataset constraints using minimal noise and provable accuracy.
- •For computer graphics developers: Use private algorithms to approximate shape enclosures for point clouds that contain sensitive or confidential information.
Authors
Bar Mahpud, Daniel Omer, Or Sheffet
Abstract
We study the problem of approximating the John ellipsoid (JE) of a given (centrally symmetric) polytope of $n$ constraints in a Euclidean space under differential privacy (DP). We give the first differentially private algorithm for this problem under the standard model, where neighboring datasets may differ arbitrarily in one a single constraint. Our work also extends to the complimentary problem of Minimum Enclosing Ellipsoid of $n$ points in the Euclidean space. Our approach is based on the recent non-private multiplicative-weights algorithm of~\cite{pmlr-v99-cohen19a}. First we introduce a non-private generalization of the Cohen et al algorithm, yielding a $(1+γ)$-approximation of the JE problem while violating at most $κn$ constraints in $O(\log(1/κ)/γ)$ iterations. This variant works by projecting the intermediate weights assigned to the constraints onto the set of $κ$-dense distributions, similarly to~\cite{bun2020efficientnoisetolerantprivatelearning}. We then design a $ρ$-zCDP variant of this algorithm by adding Gaussian noise to the weighted covariance matrix aggregated in each step of the algorithm. Under a mild goodness assumption on the data we can assert that the resulting noisy matrix is close to the true matrix, thereby achieving essentially the same guarantee as the non-private algorithm provided sufficiently many input points. Thus our method achieves an efficient DP poly-time algorithm under concrete sample complexity bounds.