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 consider the problem of model selection in a high-dimensional sparselinear regression model under the differential privacy framework. Inparticular, we consider the problem of differentially private best subsetselection and study its utility guarantee. We adopt the well-known exponentialmechanism for selecting the best model, and under a certain margin condition,we establish its strong model recovery property. However, the exponentialsearch space of the exponential mechanism poses a serious computationalbottleneck. To overcome this challenge, we propose a Metropolis-Hastingsalgorithm for the sampling step and establish its polynomial mixing time to itsstationary distribution in the problem parameters $n,p$, and $s$. Furthermore,we also establish approximate differential privacy for the final estimates ofthe Metropolis-Hastings random walk using its mixing property. Finally, we alsoperform some illustrative simulations that echo the theoretical findings of ourmain results.

On the Computational Complexity of Private High-dimensional Model Selection via the Exponential Mechanism