Summary
This paper proposes a differentially private algorithm for regression problems. The algorithm protects the privacy of the labels ("label DP"), in contrast to the entire example. The canonical application of this is digital advertising, where the label might be transaction data from a separate website. Furthermore, the algorithm operates in what [GKK+23] term the "feature-oblivious" model, where a private algorithm, operating solely on the labels, sends a message to the "features party," who then uses these together to learn a model.
[GKK+23] studied a label randomizer that aims to minimize the difference between the true and noisy labels. This work studies a unbiased randomizers. In addition to experiments, the paper provides some theoretical evidence that unbiased estimators, even if they have high variance, may be superior.
The private algorithm (which, again, only has access to the labels) proceeds in two steps. First, it uses a private histogram to estimate a prior over the labels. It then solves a linear program, the output of which is our label randomizer. The LP minimizes the expected difference between the true and noisy labels, subject to privacy, unbiasedness, and normalization constraints.
An important technical question is the randomizer's output space. Let $\mathcal{Y}\subseteq \mathbb{R}$ be the label space and $\hat{\mathcal{Y}}\subseteq \mathbb{R}$ the set of possible outputs of the randomizer. The solution to the LP has $|\mathcal{Y}|\times|\hat{\mathcal{Y}}|$ entries, representing a probability distribution over $\hat{\mathcal{Y}}$ for each entry in $\mathcal{Y}$. Thus it is clear that this approach demands both sets be finite (and of modest size, to solve the LP). What is less clear, due to the unbiasedness constraint, is what $\hat{\mathcal{Y}}$ should be. Note that if $\min \mathcal{Y} =0 $ and $\hat{\mathcal{Y}}=\mathcal{Y}$, then unbiasedness demands we map $0\to 0$ with probability 1, violating privacy. Thus the endpoints of $\hat{\mathcal{Y}}$ must exceed those of $\mathcal{Y}$. The authors set the endpoints of $\hat{\mathcal{Y}}$ so that (provably) the LP is feasible. They "fill in" the rest of $\hat{\mathcal{Y}}$ with a grid, as finely spaced as their computational constraints allow.
For a fixed $\hat{\mathcal{Y}}$ and prior on $\mathcal{Y}$, the LP finds the unbiased private randomizer with the lowest expected difference (or loss) in labels. Experiments demonstrate improvements over prior work on three data sets.
I noticed that parts of the submission (introducing the label DP recipe, describing data sets, and reviewing related work) had substantial overlap with text from GKK+23. After discussion with my chair, I have not used this information in my evaluation of the paper.
Strengths
Without unbiasedness constraints, GKK+23 find the best randomizer is of a form they call "RR-on-Bins." The authors nicely sum up their core innovation: "the addition of an unbiasedness constraint to the linear program leads to solutions to the LP that (i) are not RR-on-Bins solutions, (ii) can have substantially higher variance than RR-on-Bins, and (iii) nevertheless have a much lower train and test error due to the reduction in bias." This is a clear observation that allows them to move past prior work.
I buy that this is a practical problem, that the feature-oblivious model is useful.
Their approach does seem to significantly improve on that of GKK+23 on the data sets they tested. Their experimental results are complemented by their formal claims (Theorem 6 and Proposition 7) about the output label space of randomizers.
With minor exceptions, I found the presentation very clear throughout.
Weaknesses
In light of the work of GKK+23, this paper has limited novelty. Originality is also a serious weakness: GKK+23 point out that "our noising mechanism typically introduces a bias; mitigating it, say by adding unbiasedness constraints into the LP, is an interesting direction."
The title says the work finds "optimal" unbiased randomizers, but that optimality only holds once the choice of output space is selected. Theorem 6 (there is an optimal unbiased randomizer with at most $2|\mathcal{Y}|$ labels) and Proposition 7 (selecting endpoints to ensure feasibility) are good steps, but do not get us all the way there. As far as I can tell, it remains possible that some other scheme generates better unbiased randomizers, at least for some priors.
The paper's focus is on feature-oblivious algorithms, but I would have liked to see a comparison with other label-DP algorithms that solve this problem. How much are we giving up by moving to feature-oblivious?
Questions
Is there evidence (even informal) that this discretization approach is close to optimal? For instance, can we rule out that the LP's objective is highly sensitive to the choice of endpoints (in the regime considered)?
Can you briefly sketch out what you feel are the key innovations beyond GKK+23?
Estimating the prior requires some privacy budget for each bin. Do you expect that, as $|\mathcal{Y}|$ grows, another approach will perform better than yours?
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Limitations
The algorithm operates in the feature-oblivious model; other label-DP algorithms might perform better in different settings.
The algorithm assumes prior knowledge of $\mathcal{Y}$; it is not always clear where this information comes from.