- Rating
- 1
- Confidence
- 2
- Informativeness
- 1
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studies the problem of densest sub-matrix: given a n by n matrix, find the indices of the k by k submatrix with largest summation. In the non-private set up, sn iterative algorithm Incremental Greedy Procedure (IGP) achieved the best known result. This paper combines exponential mechanism in differential privacy with IGP, proposing a differetially private algorithm with little utility loss when input matrix entries follow gaussian distribution. Numerical simulations are run to support theoretical claims.
Critical strengths
The theoretical analysis looks solid. Source code is provided which is good for reproducibility.
Critical weaknesses
My largest concern is that this paper may not be well motivated. Although differential privacy is a main topic in this paper, it is not clear what is the exact privacy concern that this paper aims to address. For instance, what is the threat model? Who is the attacker? What is the potential attack? The privacy claims read like if 2 matrices only differ by 1 entry, then the output of the proposed algorithm is indistinguishable. What is revealed to the adversary? If I understand correctly it should be the indices of the densest submatrix. But why would this be a privacy concern from the beginning? Let us say we run the non-DP algorithm and release the index. What is the privacy risk? Further more, the utility is measured as the sum of the submatrix. Does this mean someone needs to access the matrix with the indices? Then how privacy is guaranteed? Looks like privacy and utility are served for different parties.
Questions for authors
Can you elaborate a bit more on the threat model used in the paper? Is there empirical risk for the non-private IGP algorithm?