These labels were automatically added by AI and may be inaccurate. For details, see About Literature Database.
Abstract
Determining the John ellipsoid - the largest volume ellipsoid contained
within a convex polytope - is a fundamental problem with applications in
machine learning, optimization, and data analytics. Recent work has developed
fast algorithms for approximating the John ellipsoid using sketching and
leverage score sampling techniques. However, these algorithms do not provide
privacy guarantees for sensitive input data. In this paper, we present the
first differentially private algorithm for fast John ellipsoid computation. Our
method integrates noise perturbation with sketching and leverage score sampling
to achieve both efficiency and privacy. We prove that (1) our algorithm
provides $(\epsilon,\delta)$-differential privacy, and the privacy guarantee
holds for neighboring datasets that are $\epsilon_0$-close, allowing
flexibility in the privacy definition; (2) our algorithm still converges to a
$(1+\xi)$-approximation of the optimal John ellipsoid in
$O(\xi^{-2}(\log(n/\delta_0) + (L\epsilon_0)^{-2}))$ iterations where $n$ is
the number of data point, $L$ is the Lipschitz constant, $\delta_0$ is the
failure probability, and $\epsilon_0$ is the closeness of neighboring input
datasets. Our theoretical analysis demonstrates the algorithm's convergence and
privacy properties, providing a robust approach for balancing utility and
privacy in John ellipsoid computation. This is the first differentially private
algorithm for fast John ellipsoid computation, opening avenues for future
research in privacy-preserving optimization techniques.