Private Densest Submatrix Selection: Privacy is Nearly Free

We study the densest $k\times k$ submatrix problem for an $n\times n$ Gaussian random matrix under differential privacy, where a record is either one entry or one row. Without privacy, the optimum is ${\eta }_{\mathrm{OPT}}=2\sqrt{\log n/k}$, and the best known polynomial-time algorithm attains a $\frac{2\sqrt{2}}{3}$ 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 $\epsilon$-DP mechanism that attains the same $\frac{2\sqrt{2}}{3}$ fraction once $k\gg \log n\cdot \log (k\log n)/{\epsilon }^2$. We also show that no $\epsilon$-DP mechanism, efficient or not, achieves a per-entry average above a constant depending on $\epsilon$ alone. In fact the recoverable fraction of the optimum at fixed $\epsilon$ is $\Theta (\min \{1,\epsilon \sqrt{k/\log n}\})$, so the threshold of our main result is within a $\log \log$ factor of optimal. Under row-level privacy, no mechanism recovers a constant fraction of the optimum unless $\epsilon =\Omega (\log n)$, regardless of $k$.