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

In this paper, we revisit the problem of sparse linear regression in thelocal differential privacy (LDP) model. Existing research in thenon-interactive and sequentially local models has focused on obtaining thelower bounds for the case where the underlying parameter is $1$-sparse, andextending such bounds to the more general $k$-sparse case has proven to bechallenging. Moreover, it is unclear whether efficient non-interactive LDP(NLDP) algorithms exist. To address these issues, we first consider the problemin the $\epsilon$ non-interactive LDP model and provide a lower bound of$\Omega(\frac{\sqrt{dk\log d}}{\sqrt{n}\epsilon})$ on the $\ell_2$-normestimation error for sub-Gaussian data, where $n$ is the sample size and $d$ isthe dimension of the space. We propose an innovative NLDP algorithm, the veryfirst of its kind for the problem. As a remarkable outcome, this algorithm alsoyields a novel and highly efficient estimator as a valuable by-product. Ouralgorithm achieves an upper bound of$\tilde{O}({\frac{d\sqrt{k}}{\sqrt{n}\epsilon}})$ for the estimation error whenthe data is sub-Gaussian, which can be further improved by a factor of$O(\sqrt{d})$ if the server has additional public but unlabeled data. For thesequentially interactive LDP model, we show a similar lower bound of$\Omega({\frac{\sqrt{dk}}{\sqrt{n}\epsilon}})$. As for the upper bound, werectify a previous method and show that it is possible to achieve a bound of$\tilde{O}(\frac{k\sqrt{d}}{\sqrt{n}\epsilon})$. Our findings revealfundamental differences between the non-private case, central DP model, andlocal DP model in the sparse linear regression problem.

Improved Analysis of Sparse Linear Regression in Local Differential Privacy Model