acceptodds
Withdrawn from ICLR 2027

Private Densest Submatrix Selection: Privacy is Nearly Free

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

We study the densest submatrix problem for an Gaussian random matrix under differential privacy, where a record is either one entry or one row. Without privacy, the optimum is , and the best known polynomial-time algorithm attains a fraction of it. This constant is optimal among online algorithms and conjectured optimal among all polynomial-time ones. Our main result is an online polynomial-time -DP mechanism that attains the same fraction once . We also show that no -DP mechanism, efficient or not, achieves a per-entry average above a constant depending on alone. In fact the recoverable fraction of the optimum at fixed is , so the threshold of our main result is within a factor of optimal. Under row-level privacy, no mechanism recovers a constant fraction of the optimum unless , regardless of .

Primary area:
learning theory
Keywords:
Differential privacy, Densest submatrix, Phase transitions

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_VSrKOpenReview ↗
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?

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

This paper studies the densest k×kk \times k submatrix problem under differential privacy. Given an n×nn \times n matrix, this problem asks us to find the k×kk \times k submatrix (i.e., a set of kk rows and a set of kk columns) which maximum the average matrix entry. This generalizes other well-studied problems, e.g., when applied to the adjacency matrix of a graph this turns into the celebrated densest kk-subgraph problem. This paper gives an ϵ\epsilon-DP algorithm for this problem which runs in polynomial time and which gives a good approximation (basically 223\frac{2\sqrt{2}}{3}) if every entry is chosen iid from N(0,1)N(0,1) and if kk is large enough (basically at least logarithmic). In this regime the optimal value is highly concentrated (this is known from previous work), so the issue is finding the submatrix, not finding the value. Their algorithm starts from the "incremental greedy" algorithm, which was introduced previously for this problem by Gamarnick and Li, and which just alternates picking the best row/column given the previous choices. They slightly modify this algorithm in three ways: they batch it (choosing about k\sqrt{k} rows/columns per iteration rather than 11), they use the exponential mechanism to pick this set privately in each iteration, and they clip values to ensure that the sensitivity is reasonable. They also provide a lower bound for the case when kk is small and a simple algorithm which matches it. Finally, for row-level privacy (rather than entry-level) they prove a lower bound showing that ϵ\epsilon needs to be extremely large (Ω(log⁡n)\Omega(\log n)) to do anything reasonable, and that in this regime a simple algorithm gets a constant approximation.

Overall, I don't think that this paper should be accepted to ICLR. While I like the problem from an algorithmic viewpoint (as someone who likes the densest kk-subgraph problem), the assumption of iid Gaussian entries is extremely strong, and I don't see the motivation for it or why it is interesting outside of a pure probability theory context. The authors also do not motivate why we should care about the DP version of this problem, other than stating related results that do not assume iid entries (e.g., for densest subgraph with adversarial inputs or private recovery in planted models). I just don't see why it is interesting or important to study the private version of this problem under such a strong assumption.

Critical strengths
  • The algorithm is reasonably simple but has a nontrivial analysis.
  • Densest k×kk \times k submatrix seems like an interesting an natural generalization of other problems.
Critical weaknesses

I fundamentally don't understand why this question is interesting.

  • Forgetting the DP issue for a minute, why is the purely algorithmic version of this question interesting when every entry is N(0,1)N(0,1)? The authors cite and build on significant previous non-private work on this problem, but all of those papers appeared in probability theory journals. I can imagine that probability theorists would find this setting interesting, but I don't at all understand why it's interesting from either an ML or algorithmic point of view. It doesn't seem to me like a problem that is either useful in practice or is interesting from a theoretical point of view for anyone other than pure probabilists.
  • Now even if we believe that the non-private version of the problem is interesting (with N(0,1)N(0,1) entries), why do we care about the DP version of this problem? Usually one would tell a story either about applications or about how natural the problem is. But I don't see anything like that in this paper. The closest that they come is in the first paragraph, where they discuss DkS but also collaborative filtering and fraud detection. But they do not actually explain any of these problems or how their problem relates, and they certainly do not explain why it is reasonable to assume iid Gaussians. This is, in my opinion, unacceptable. ICLR is not a math journal, and problems need motivation even if they are theoretically focused. The motivation need not be practical, but if the authors are going to propose a new problem (densest k×kk \times k submatrix for iid Gaussian matrices) then they need to at least explain why anyone should care about it.
Questions for authors
  • Why is it reasonable to combine privacy with the iid Gaussian model? Is there any reasonable application or story as to why one should care about privacy with such a strong assumption on entries?
Reviewer_GqLjOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes a new online differentially private selection of dense k\times k submatrix from n\times n matrix where the entries are i.i.d distributed variables.The authors proposed a batched incremental procedure for the problem, and showed that it asymptotically achieves the same approximation factor as the best known non-private online algorithm under the DP setting with an appropriate budget. The authors also analyzes the differences between entry-level and row-level privacy.

Critical strengths

This paper introduces a novel interesting problem how the differential privatacy setting affects the incrimental greedy procedure for finding a dense submatrix from a matrix with i.i.d. Gaussian random variables. Their information-theoretic upper bounds are interesting.

Critical weaknesses
  1. My primary concern is the significance of the problem the authors are dealing with. I think the mathematical model itself is interesting, but at the same time, I think the assumptions in the problem are rather artificial, in particular:
  • All matrix entries are i.i.d. Gaussian random variables, which means there should be no structure like dense matrix in the matrix. The authors mention biclustering as an application, but the entries of the matrix to be bi-clustered should not be i.i.d. random entries.
  • The submatrix size is restricted to very small subpolynomial size.
  • The online model is very artificial. I cannot find any motivation on this online setting. It should be more natural if the online stream is just row by row or column by column.
  • The main positive results concern entry-level privacy, but motivating applications would relate to the row-level privacy.
  1. Regarding sequential composition The authors state in Lemma E.3 that the sets of matrix entries accessed by different stages are predetermined and pairwise disjoint regions. I think it means there's no need to consider sequentional composition and we can consider parallel composition. So I suppose there should be no need for batching. The authors should discuss why the authors cannot apply parallel composition.

  2. Regarding experiments (p.37) I think the baseline per-row DP-IGP is too weak. The authors divide the privacy budget among all selection stages in this algorithm, but we do not need to do so, as we can apply parallel composition here. Thus I think the comparison in this experiments is unfair.

  3. Minor comments -p.30 E.1 The authors say they output the matrix, but it should be indices of matrix.

Questions for authors

As I wrote in the comments above, I have a concern on the necessity of batching as we can apply parallel composition in this problem, if I understand this problem correctly. I also think the DP-IGP algorithm in p.37 can use the full budget for all selection stages for the same reason. Can you explain why parallel composition cannot be applied?

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

Related papers

Discussion (0)

Sign in to comment.