cs.LGNov 10, 2025

Private Sparse Sketches for Linear Regression

Authors: Shrutimoy Das, Anirban Dasgupta

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 ℓ2\ell_2 and ℓ1\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.

Figures & tables

Explore similar work

CardsList
  1. The Fast Mixing Mechanism for Differential Privacy

    May 28, 2026Omri Lev, Moshe Shenfeld, Vishwak Srinivasan +2Randomized SketchingDifferential Privacy

  2. On Differentially Private Mechanisms for Linear Regression

    Nov 5, 2026Bardiya Aryanfard, Monika Henzinger, Farhood RostamkhaniLinear RegressionDifferential Privacy

  3. Refined Differentially Private Linear Regression via Extension of a Free Lunch Result

    Apr 11, 2026Sasmita Harini S, Anshoo TandonDifferential PrivacyLinear Regression