Greedy R2T: Approximate Truncation under User-level Differential Privacy

The Hong Kong University of Science and Technology
Department of Computer Science and Engineering

Final Year Thesis Oral Defense

Title: "Greedy R2T: Approximate Truncation under User-level Differential 
Privacy"

by

SHU Tian

Abstract:

Releasing privatized results for SJA and SPJA queries under user-level 
differential privacy has long been an industrial demand. This task is 
challenging due to the possible many-to-many mapping between users and tuples 
and the excessive global sensitivity. The prevailing approach is to bound the 
sensitivity by truncating or projecting the dataset on a per-instance basis. 
The state-of-the-art R2T mechanism performs adaptive truncations to achieve 
down-neighborhood optimality while preserving user-DP. In comparison with other 
solutions, R2T is more accurate but inefficient, and its bottleneck is solving 
LPs when finding optimal truncation. In this thesis, we observed that the 
optimality of truncation is in fact unnecessary for the utility guarantees and 
that combinatorial approximations for the optimal solution can be applied to 
avoid solving LPs. We designed Greedy R2T, which is an almost linear variant of 
R2T that applies to the marginal case when each tuple is contributed by at most 
two users. Experiments and comparisons are performed to evaluate the accuracy 
and efficiency of Greedy R2T.


Date            : 2 May 2024 (Thursday)

Time            : 16:45 - 17:25

Venue           : Room 4475 (near lifts 25/26), HKUST

Advisor         : Prof. YI Ke

2nd Reader      : Dr. GOHARSHADY Amir