- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This work proposes a technique to approximate the John ellipsoid (JE) of a centrally symmetric convex polytope under differential privacy (DP). The authors present this technique in two stages: first, they generalize a non-private version of the approximation algorithm based on multiplicative weight updates by Cohen et al.; second, they construct the DP variant of this generalization by adding Gaussian noise to the weighted covariance matrix at each training step. To incorporate DP, the generalized approximation of JE requires some relaxation on the constraints. Specifically, one must allow the approximate JE to violate a fraction () of the constraints that define the convex polytope, so that for neighboring datasets differing in an arbitrary data point, the corresponding approximate JE does not change significantly. The paper shows their main results in terms of time complexity and sample complexity, with additional utility guarantees provided under certain goodness assumption on the data. Lastly, the paper demonstrates an extension of the proposed algorithm to the centered minimum-volume enclosing ellipsoid (MVEE) problem through standard polar-duality correspondence.
Critical strengths
The strength of the paper comes from the application of DP in a previously unexplored area of research. Although the non-private approximation algorithm is inspired by existing literature, the generalization technique to facilitate strict DP requirements is fairly novel. Notably, the private algorithm does not require the data to satisfy the goodness condition to succeed; it is only used for the theoretical bound on the utility, given in terms of “closeness” to the true covariance matrix. The paper is decently organized with a few notational inconsistencies, the technical details appear correct, and the extension to MVEE and general uncentered ellipsoids seem promising.
Critical weaknesses
-
My primary concern lies in the practicality of the proposed private algorithm. The authors do not demonstrate any application where one might \textit{need} to privatize the JE, which would strengthen the motivation behind their work.
-
The paper lacks concrete comparison with related works. Namely, Cohen et al. compares the number of iterations and total time of the JE approximation to similar algorithms and tools across a set of example polytopes, but this paper does not show how enforcing DP affects these performance metrics.
-
Throughout the paper there are numerous presentation and notational inconsistencies. The main results are presented twice: Theorems 1.1 and 1.3 appear to be the informal statements, whereas Theorems 3.1 and 4.1 again state the same results with revised notation and phrasing. appears in Theorem 3.1 without prior definition, and used interchangeably with . Definition 2.1 states “a scaling of by ", but in the theorems it is .
Questions for authors
Please refer to the weaknesses. Addressing the above issues will help solidify the strengths of the paper.
Additional comments:
- It is not clear which notion of neighboring datasets is used for the private algorithm. In Introduction, the paper explains how adding a new constraint leads to the reduction of the volume of and the corresponding JE. However, this is analogous to neighboring datasets constructed by adding or removing a data point, which is different from the notion of neighbors differing in at most one entry.