← 研踪 PaperTrailarXiv:2511.07365 · v3
Private Sparse Sketches for Linear Regression
首次提交 2025-11-11 02:22
版本更新 2026-11-08 13:30
雷达观测 2026-11-10 12:16
摘要
Sketching compresses a large dataset into a smaller summary, allowing regression on the sketch to approximate the full-data objective. A sketch released under differential privacy can be reused with any non-private regression solver, any number of times, without further privacy loss. We study private sparse sketches for $\ell_2$ and $\ell_1$ regression. We first prove lower bounds on the noise required by common sparse sketches for both problems when the sketching matrix is public. Since regression on a sketch can be solved without revealing the sketching matrix, we construct sketches whose randomness is kept secret. Hiding how individual records enter the sketch provides an additional source of privacy, allowing less noise for the same privacy guarantee. We prove differential privacy guarantees for both constructions, and experiments on real datasets show improved utility over public-sketch baselines.
作者备注：24 pages
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v3 · 2026-11-08 13:30 · 最新观测版本
Private Sparse Sketches for Linear Regression
Sketching compresses a large dataset into a smaller summary, allowing regression on the sketch to approximate the full-data objective. A sketch released under differential privacy can be reused with any non-private regression solver, any number of times, without further privacy loss. We study private sparse sketches for $\ell_2$ and $\ell_1$ regression. We first prove lower bounds on the noise required by common sparse sketches for both problems when the sketching matrix is public. Since regression on a sketch can be solved without revealing the sketching matrix, we construct sketches whose randomness is kept secret. Hiding how individual records enter the sketch provides an additional source of privacy, allowing less noise for the same privacy guarantee. We prove differential privacy guarantees for both constructions, and experiments on real datasets show improved utility over public-sketch baselines.
查看此版本解读 →查看此版本原文 ↗