Private Incremental Regression

Summary: Introduce private incremental ERM/regression under differential privacy, with a generic batch→incremental reduction and two streaming-regression mechanisms. One gives ~√d risk via noisy incremental gradients; the other uses random projections and Gaussian width to get ~T^{1/3}W^{2/3}, resolving adaptivity. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1711
Venue: PODS
Year: 2017
Pagerank: 5.6029996e-05
Overall Rank: 7,517 | 48.43%
DOI: 10.1145/3034786.3034795

Incoming Non-self Citations Over Time

Authors

1. Shiva Prasad Kasiviswanathan (Samsung)
2. Kobbi Nissim (Georgetown University)
3. Hongxia Jin (Samsung)

BibTeX Citation

@inproceedings{kasiviswanathan_pods17,
        address = {New York, NY, USA},
        series = {{PODS} '17},
        title = {{Private Incremental Regression}},
        url = {https://dl.acm.org/doi/10.1145/3034786.3034795},
        doi = {10.1145/3034786.3034795},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Kasiviswanathan, Shiva Prasad and Nissim, Kobbi and Jin, Hongxia},
        year = {2017}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
11,529	Lower Bounds for Sparse Oblivious Subspace Embeddings	2022	PODS	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
123	Revealing Information while Preserving Privacy	2003	PODS	0.00031082693
510	Practical Privacy: The SuLQ Framework	2005	PODS	0.00017220509
4,562	Private Multiplicative Weights Beyond Linear Queries	2015	PODS	6.6298422e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,545	PrivRM: A Framework for Range Mean Estimation under Local Differential Privacy	2025	SIGMOD
2	70	Privacy-Preserving Data Mining	2000	SIGMOD
3	4,562	Private Multiplicative Weights Beyond Linear Queries	2015	PODS
4	7,841	Quantifying identifiability to choose and audit epsilon in differentially private deep learning	2021	VLDB
5	13,406	High Dimensional Differentially Private Stochastic Optimization with Heavy-tailed Data	2022	PODS
6	10,484	Privacy Loss of Noise Perturbation via Concentration Analysis of A Product Measure	2026	SIGMOD
7	244	On the Design and Quantification of Privacy Preserving Data Mining Algorithms	2001	PODS
8	10,647	Private Synthetic Data Generation in Bounded Memory	2025	PODS
9	5,248	Functional Mechanism: Regression Analysis under Differential Privacy	2012	VLDB
10	10,158	Improved Lower Bounds for Privacy under Continual Release	2026	PODS