acceptodds
Under review as a conference paper at ICLR 2027

Differentially Private Approximation of the John Ellipsoid

Abstract

We study the problem of approximating the John ellipsoid (JE) of a given (centrally symmetric) polytope of 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 points in the Euclidean space. Our approach is based on the recent non-private multiplicative-weights algorithm of pmlr-v99-cohen19a. First we introduce a non-private generalization of the Cohen et al algorithm, yielding a -approximation of the JE problem while violating at most constraints in iterations. This variant works by projecting the intermediate weights assigned to the constraints onto the set of -dense distributions, similarly to 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.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
Differential Privacy, John Ellipsoid, Convex Optimization, Multiplicative Weights, Computational Geometry

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_zNt8OpenReview ↗
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 (κ\kappa) of the nn 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. KpK_p appears in Theorem 3.1 without prior definition, and used interchangeably with KK. Definition 2.1 states “a scaling of E(μ)E(\mu) by e−γe^{-\gamma}", but in the theorems it is e−γ/2e^{-\gamma/2}.

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 KK 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.
Reviewer_4EnAOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper studies differentially private approximation of the John ellipsoid of a centrally symmetric polytope under replacement of an individual input constraint. Because a single constraint can substantially change the optimal ellipsoid, the authors adopt a bicriteria formulation: the output approximately preserves the full-data optimal volume while satisfying all but a κ\kappa-fraction of the constraints after rescaling. The proposed algorithm extends the multiplicative-weights approach of Cohen et al. by maintaining unprojected weights and applying a KL projection onto the set of κ\kappa-dense measures before forming each weighted second-moment matrix. The claimed nonprivate iteration complexity is O(log⁡(1/κ)/γ)O(\log(1/\kappa)/\gamma). The private variant adds symmetric Gaussian noise to these matrices and uses their inverses for subsequent updates. Under bounded input norms and a directional anti-concentration assumption termed (κ,τ)(\kappa,\tau)-goodness, the paper derives a ρ\rho-zCDP guarantee and an explicit sufficient sample-size bound. The paper also connects the result to centered minimum-volume enclosing ellipsoids through polarity and proposes an extension to uncentered ellipsoids through homogeneous-coordinate lifting. The contribution is theoretical.

Critical strengths
  1. Allowing arbitrary replacement of a constraint within a bounded input domain is a substantive strengthening over the model used in the cited prior private John-ellipsoid work. The decision to relax feasibility by permitting a small fraction of violations is well motivated by the sensitivity of the original geometric problem. This gives the paper a clear privacy–utility tradeoff. The earlier published result explicitly restricts neighboring inputs to sufficiently close replacements.

  2. The dense-weight formulation yields an iteration bound of O(log⁡(1/κ)/γ)O(\log(1/\kappa)/\gamma), making the iteration count depend on the permitted violation fraction rather than directly on the number of constraints. The KL-potential argument also provides a useful connection between the guarantee over dense measures and satisfaction of a large subset of geometric constraints. This part of the paper has value independently of its privacy application.

Critical weaknesses
  1. The stated assumptions permit zero constraint vectors, but the multiplicative update assigns them zero raw weight. If fewer than κn\kappa n nonzero rows remain, no measure supported on those rows can have total mass dd while respecting the cap d/(κn)d/(\kappa n). Consequently, the next KL projection has no finite-divergence feasible solution. This issue can occur even under the private theorem's goodness assumption. Consider d=1d=1, κ=0.9\kappa=0.9, τ=0.4\tau=0.4, and R=1R=1, with 40%40\% of the rows equal to zero and 60%60\% equal to one. This dataset is (κ,τ)(\kappa,\tau)-good because the bad fraction in either direction is 0.4<κ/2=0.450.4<\kappa/2=0.45. After the first successful update, however, the positive-weight coordinates can carry total projected mass at most 0.6n⋅10.9n=23<1.0.6n\cdot\frac{1}{0.9n}=\frac{2}{3}<1. For parameters requiring multiple iterations, the algorithm is therefore undefined. Increasing nn does not resolve the problem. This is a counterexample to the stated domain of the main guarantees. An explicit treatment of zero constraints or a revised public input domain is needed. The issue appears repairable, but it should be resolved before accepting the theorem as stated.

References: Algorithms 1–2, Lemma B.1, and Theorems 3.1 and 4.1.

  1. Algorithm 3 uses noise scale

σ=4dR2κn2ρ0,\sigma=\frac{4dR^2}{\kappa n\sqrt{2\rho_0}},

whereas Lemma D.3 states a scale with coefficient 22. More substantively, Lemma D.3 uses a spectral-norm concentration threshold whose leading term is σd\sigma\sqrt{d}. Under the symmetric Gaussian normalization specified in Appendix A.3—diagonal variance σ2\sigma^2 and off-diagonal variance σ2/2\sigma^2/2—the leading spectral scale is approximately σ2d\sigma\sqrt{2d}. The asserted bound therefore does not hold in general. The factor-of-two discrepancy in the written noise scales may be absorbed by existing slack; it is the incorrect spectral concentration inequality that leaves the required high-probability perturbation event unsupported. Explicit sample complexity is a central advertised contribution. The proof needs consistent noise calibration and a valid matrix concentration bound. A larger universal constant appears sufficient to repair the argument, so this concern should not be interpreted as disproving the asymptotic rate or the privacy guarantee.

References: Algorithm 3, Appendix A.3, Lemma D.3, and Theorem 4.1.

Questions for authors

See Weaknesses

Reviewer_AY9TOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The authors present a differentially private algorithm for approximating the John Ellipsoid. The John Ellipsoid is the largest volume ellipsoid contained in a symmetric polytope defined by n constraints. The paper's approach is based on the non-private iterative reweighting algorithm from Cohen et al (2019). However, the global sensitivity of that algorithm doesn't decrease with the sample size, since the weights end up concentrating on a handful of points. The authors therefore cap the weight given to any single point, which gives a better sensitivity, and then apply an adaptation of the lazy Bregman projection (dense-measure) framework from private boosting (Bun et al., 2020). Guarantees are provided on the utility of the private ellipsoid (which is allowed to violate a κ fraction of the constraints) and on the number of iterations.

Critical strengths

The utility guarantee seems nontrivial, and this is the first I've seen of privatizing something like an ellipsoid under the standard notion of neighboring datasets. The paper is also well written and structured.

Critical weaknesses

I found the motivation to be extremely lacking. Why is a private version of this ellipsoid remotely important? It is worth spending some space motivating the problem, especially why a private version is needed. This becomes doubly important when you don't have any empirical work in the paper.

Also, I'm a bit unclear on the non-private contribution. As far as I can tell, there isn't a reason to use the new non-private version over Cohen et al. It is primarily there to facilitate privacy.

Minor: Calling a paper from 2019 "recent" is maybe a stretch.

Questions for authors

See weaknesses.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.