Ranking Differential Privacy
- URL: http://arxiv.org/abs/2301.00841v1
- Date: Mon, 2 Jan 2023 19:12:42 GMT
- Title: Ranking Differential Privacy
- Authors: Shirong Xu, Will Wei Sun and Guang Cheng
- Abstract summary: Existing works mainly develop privacy protection on a single ranking within a set of ranking or pairwise comparisons of a ranking under the $epsilon$-differential privacy.
This paper proposes a novel notion called $epsilon$-ranking differential privacy for protecting ranks.
We develop a multistage ranking algorithm to generate synthetic rankings while satisfying the developed $epsilon$-ranking differential privacy.
- Score: 17.826241775212786
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Rankings are widely collected in various real-life scenarios, leading to the
leakage of personal information such as users' preferences on videos or news.
To protect rankings, existing works mainly develop privacy protection on a
single ranking within a set of ranking or pairwise comparisons of a ranking
under the $\epsilon$-differential privacy. This paper proposes a novel notion
called $\epsilon$-ranking differential privacy for protecting ranks. We
establish the connection between the Mallows model (Mallows, 1957) and the
proposed $\epsilon$-ranking differential privacy. This allows us to develop a
multistage ranking algorithm to generate synthetic rankings while satisfying
the developed $\epsilon$-ranking differential privacy. Theoretical results
regarding the utility of synthetic rankings in the downstream tasks, including
the inference attack and the personalized ranking tasks, are established. For
the inference attack, we quantify how $\epsilon$ affects the estimation of the
true ranking based on synthetic rankings. For the personalized ranking task, we
consider varying privacy preferences among users and quantify how their privacy
preferences affect the consistency in estimating the optimal ranking function.
Extensive numerical experiments are carried out to verify the theoretical
results and demonstrate the effectiveness of the proposed synthetic ranking
algorithm.
Related papers
- Rate-Optimal Rank Aggregation with Private Pairwise Rankings [12.511220449652384]
We address the challenge of preserving privacy while ensuring the utility of rank aggregation based on pairwise rankings.
Motivated by this, we propose adaptively debiasing the rankings from the randomized response mechanism.
arXiv Detail & Related papers (2024-02-26T18:05:55Z) - Stability and Multigroup Fairness in Ranking with Uncertain Predictions [61.76378420347408]
Our work considers ranking functions: maps from individual predictions for a classification task to distributions over rankings.
We focus on two aspects of ranking functions: stability to perturbations in predictions and fairness towards both individuals and subgroups.
Our work demonstrates that uncertainty aware rankings naturally interpolate between group and individual level fairness guarantees.
arXiv Detail & Related papers (2024-02-14T17:17:05Z) - Mean Estimation Under Heterogeneous Privacy: Some Privacy Can Be Free [13.198689566654103]
This work considers the problem of mean estimation under heterogeneous Differential Privacy constraints.
The algorithm we propose is shown to be minimax optimal when there are two groups of users with distinct privacy levels.
arXiv Detail & Related papers (2023-04-27T05:23:06Z) - Privacy-Preserving Fair Item Ranking [13.947606247944597]
This work is the first to advance research at the conjunction of producer (item) fairness and consumer (user) privacy in rankings.
Our work extends the equity of amortized attention ranking mechanism to be privacy-preserving, and we evaluate its effects with respect to privacy, fairness, and ranking quality.
arXiv Detail & Related papers (2023-03-06T06:21:20Z) - Algorithms with More Granular Differential Privacy Guarantees [65.3684804101664]
We consider partial differential privacy (DP), which allows quantifying the privacy guarantee on a per-attribute basis.
In this work, we study several basic data analysis and learning tasks, and design algorithms whose per-attribute privacy parameter is smaller that the best possible privacy parameter for the entire record of a person.
arXiv Detail & Related papers (2022-09-08T22:43:50Z) - Individual Privacy Accounting for Differentially Private Stochastic Gradient Descent [69.14164921515949]
We characterize privacy guarantees for individual examples when releasing models trained by DP-SGD.
We find that most examples enjoy stronger privacy guarantees than the worst-case bound.
This implies groups that are underserved in terms of model utility simultaneously experience weaker privacy guarantees.
arXiv Detail & Related papers (2022-06-06T13:49:37Z) - Fully Adaptive Composition in Differential Privacy [53.01656650117495]
Well-known advanced composition theorems allow one to query a private database quadratically more times than basic privacy composition would permit.
We introduce fully adaptive composition, wherein both algorithms and their privacy parameters can be selected adaptively.
We construct filters that match the rates of advanced composition, including constants, despite allowing for adaptively chosen privacy parameters.
arXiv Detail & Related papers (2022-03-10T17:03:12Z) - On the Linear Ordering Problem and the Rankability of Data [0.0]
We use the degree of linearity to quantify what percentage of the data aligns with an optimal ranking.
In a sports context, this is analogous to the number of games that a ranking can correctly predict in hindsight.
We show that the optimal rankings computed via the LOP maximize the hindsight accuracy of a ranking.
arXiv Detail & Related papers (2021-04-12T21:05:17Z) - Differential Privacy of Hierarchical Census Data: An Optimization
Approach [53.29035917495491]
Census Bureaus are interested in releasing aggregate socio-economic data about a large population without revealing sensitive information about any individual.
Recent events have identified some of the privacy challenges faced by these organizations.
This paper presents a novel differential-privacy mechanism for releasing hierarchical counts of individuals.
arXiv Detail & Related papers (2020-06-28T18:19:55Z) - SetRank: A Setwise Bayesian Approach for Collaborative Ranking from
Implicit Feedback [50.13745601531148]
We propose a novel setwise Bayesian approach for collaborative ranking, namely SetRank, to accommodate the characteristics of implicit feedback in recommender system.
Specifically, SetRank aims at maximizing the posterior probability of novel setwise preference comparisons.
We also present the theoretical analysis of SetRank to show that the bound of excess risk can be proportional to $sqrtM/N$.
arXiv Detail & Related papers (2020-02-23T06:40:48Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.