Comparison with Kothari-Manurangsi-Velingker
Both Kothari-Manurangsi-Velingker (KMV) and our work obtained private algorithms for high-dimensional statistical estimation problems by privatizing strongly convex programs, more specifically, sum-of-squares (SoS) programs. On a high level, we both first solve an SoS program, and then add Gaussian noise to the solution, and return the result.
The main difference between KMV and our work lies in how we choose the SoS program. Such a difference saves us a computationally-expensive but necessary step for KMV.
For the problem of robust moment estimation, KMV considered the canonical SoS program [1] which contains a minimum cardinality constraint. In robust statistics literature, such minimum cardinality constraints are added to ensure good utility, without privacy concerns [1]. However, from the perspective of privacy, such a constraint is problematic, since there will always exist two adjacent input datasets such that the constraints are satisfiable for one but not for the other. KMV and us resolve this privacy issue in different ways as follows:
- KMV uses an exponential mechanism to pick the lower bound of the minimum cardinality constraint. This step also ensures that solutions to the resulting SoS program will have low sensitivity.
- In contrast, we simply drop the minimum cardinality constraint. Then the resulting SoS program is always feasible for any input dataset! However, the resulting SoS program will not have good utility if we do nothing else. To have good utility, we need to pick an appropriate objective function. For example, in Gaussian mixture models, we dropped the constraint that $\sum_{j}W_{ij}$ should be lower bounded and turned to minimize $||W-J||_F^2$ (where $J$ is the all-one matrix).
Our approach provides some advantages over KMV.
From a purely algorithmic point of view, the exponential mechanism in KMV requires computing $O(n)$ scores. Computing each of these scores requires solving a large semidefinite program. In contrast, our algorithm completely avoids this step. This difference can provide significant improvement in the running time.
From the point of view of algorithm analysis, proving that the exponential mechanism in KMV works requires several steps: 1) defining a (clever) score function, 2) bounding the sensitivity of this score function and, 3) showing existence of a large range of parameters with high score.
Our approach completely bypasses these steps by directly bounding the sensitivity of the program via the key lemma, hence significantly simplifying the proofs.
[1] Kothari, Pravesh K., and David Steurer. "Outlier-robust moment-estimation via sum-of-squares." _arXiv preprint arXiv:1711.11581_ (2017).