English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study the differential privacy (DP) of a core ML problem, linear ordinaryleast squares (OLS), a.k.a. $\ell_2$-regression. Our key result is that theapproximate LS algorithm (ALS) (Sarlos, 2006), a randomized solution to the OLSproblem primarily used to improve performance on large datasets, also preservesprivacy. ALS achieves a better privacy/utility tradeoff, without modificationsor further noising, when compared to alternative private OLS algorithms whichmodify and/or noise OLS. We give the first {\em tight} DP-analysis for the ALSalgorithm and the standard Gaussian mechanism (Dwork et al., 2014) applied toOLS. Our methodology directly improves the privacy analysis of (Blocki et al.,2012) and (Sheffet, 2019)) and introduces new tools which may be of independentinterest: (1) the exact spectrum of $(\epsilon, \delta)$-DP parameters (``DPspectrum") for mechanisms whose output is a $d$-dimensional Gaussian, and (2)an improved DP spectrum for random projection (compared to (Blocki et al.,2012) and (Sheffet, 2019)).  All methods for private OLS (including ours) assume, often implicitly,restrictions on the input database, such as bounds on leverage and residuals.We prove that such restrictions are necessary. Hence, computing the privacy ofmechanisms such as ALS must estimate these database parameters, which can beinfeasible in big datasets. For more complex ML models, DP bounds may not evenbe tractable. There is a need for blackbox DP-estimators (Lu et al., 2022)which empirically estimate a data-dependent privacy. We demonstrate theeffectiveness of such a DP-estimator by empirically recovering a DP-spectrumthat matches our theory for OLS. This validates the DP-estimator in anontrivial ML application, opening the door to its use in more complexnonlinear ML settings where theory is unavailable.

Privacy-Utility Tradeoff of OLS with Random Projections