Private Sparse Sketches for Linear Regression
Organizations: Department of Computer Science and Engineering Indian Institute of Technology Gandhinagar · Boston University
Abstract
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 and 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.
Figures & tables
| : MSE | : MAE | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| OLS | DP-SGD | AdaSSP | JL | Alg. 1 | Alg. 3 | LAD | DP-SGD | Alg. 2 | Alg. 4 | |
| 0.1 | 0.025 .00 | 0.120 .06 | 0.076 .01 | 0.145 .05 | 0.187 .07 | 0.072 .01 | 0.112 .00 | 0.188 .02 | 0.393 .06 | 0.401 .06 |
| 0.25 | 0.025 .00 | 0.038 .00 | 0.055 .00 | 0.100 .02 | 0.198 .08 | 0.069 .01 | 0.112 .00 | 0.128 .01 | 0.355 .05 | 0.342 .05 |
| 0.5 | 0.025 .00 | 0.029 .00 | 0.049 .00 | 0.071 .01 | 0.219 .07 | 0.054 .01 | 0.112 .00 | 0.120 .00 | 0.356 .05 | 0.300 .03 |
| 0.75 | 0.025 .00 | 0.028 .00 | 0.045 .00 | 0.069 .02 | 0.175 .04 | 0.045 .01 | 0.112 .00 | 0.119 .00 | 0.374 .06 | 0.253 .03 |
| 1.0 | 0.025 .00 | 0.028 .00 | 0.042 .00 | 0.062 .01 | 0.153 .03 | 0.044 .00 | 0.112 .00 | 0.119 .00 | 0.359 .06 | 0.227 .02 |
Randomized Sketching
Randomized sketching uses compact random projections or summaries to speed computation while approximately preserving data, geometry, or statistical structure.
See all 50 papers