- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The paper considers so called prophet inequalities under differential privacy. The task is to learn a threshold for stopping streams of data from distributions, where samples are drawn independently one at a time. The training data is a matrix of size , where is the number of samples from each distributions, and the DP indistinguishability guarantees are with respect to change of a single element in each of the streams of training data. The paper considers two kinds of mechanisms, index release mechanisms (release , the maximizing stream) or threshold mechanisms which release a suitable threshold for the max value over the n distributions. The index mechanisms are essentially exponential mechanisms and the threshold mechanism is essentially the AboveThreshold mechanism.
Critical strengths
Seems like a clear contribution: first DP results for a well-known problem in theoretical computer science, with minimax utility bounds (matchins upper and lower bounds).
Generally the paper seems quite well written, though at times the writing seems a bit strange, perhaps due to the use of the word 'inequality' (e.g., the main research question "When can a differentially private mechanism be competitive with an optimal prophet inequality?" sounds a bit weird first, though it makes more sense after closer look at the paper)
Critical weaknesses
-
I think one main weakness is that the paper misses key references (e.g., work by Kobbi Nissim and others. For example Algorithm 2 is clearly the so called AboveThreshold mechanism (see e.g., Algorithm 1 in Dwork and Roth, 2014). Also, I get the impression that there are similar results in Bun, Mark, et al. "Differentially private release and learning of threshold functions." 2015 IEEE 56th annual symposium on foundations of computer science. IEEE, 2015. which is not cited.
-
unrealistically large / small constants in the bounds. this is a proper CS theory paper in a sense that the constants in the bounds make the results inpractical. I recognize the value of finding tight asymptotic bounds, but I am not sure if ICLR is the right venue for a this kind of contribution.
-
the results hold only for pure -DP, no results for -DP
Questions for authors
Can you tell how the results are related to those of
and especially to the sample complexity results of
which look very similar (also this paper by Feldman and Xiao is not cited).
3 comments
Thank you for the reply. I don't quite understand this part:
"Feldman and Xiao (2014) study private PAC learning from labeled examples of an unknown target classifier. Transferring their lower bounds would require reducing threshold learning to our selection problem; transferring their learning guarantees would require connecting classification accuracy to welfare. Neither implication is automatic, particularly because classification error does not account for the magnitude of lost rewards. In addition, any loss function based on deviation from a given target value is characterized by very different measures than a loss against a distribution optimum."
What is here "welfare"? It is not defined in this paper nor in Feldman and Xiao (2014).
Thank you for pointing out the ambiguity. By “welfare”, we mean the expected value of the selected online element, that is, the expected-reward objective in our paper. In the posted-pricing interpretation of prophet inequalities, where the goal is to sell an item to one of bidders, this corresponds to the expected social welfare.
Reply to your questions
We thank the reviewer for their comments and suggestions.
Questions on Additional References
Algorithm 2 is indeed an instantiation of AboveThreshold. We thank the reviewers for pointing out the missing attribution and will add the citation when we introduce Algorithm 2. Our additional contribution is its prophet analysis: using the standard uniform accuracy bound (Dwork and Roth, Theorem 3.24) would introduce a dependence on the sequence length n. We instead exploit the stochastic arrivals to control premature acceptance and establish constant competitiveness with L=O(1/ϵ) samples per distribution, independently of n.
Bun et al. (2015) establish sample-complexity bounds for private threshold-query release, distribution estimation, and threshold learning. Our paper studies a different objective: learning an online stopping rule whose expected reward competes with a prophet, under either threshold privacy or index privacy. Private quantile estimation provides relevant tools for our threshold mechanisms, but additional analysis is needed to connect estimation accuracy to online reward. Existing work on private quantiles and private threshold classifiers offer very different guarantees, and cannot be straightforwardly transferred to our setting.
Feldman and Xiao (2014) study private PAC learning from labeled examples of an unknown target classifier. Transferring their lower bounds would require reducing threshold learning to our selection problem; transferring their learning guarantees would require connecting classification accuracy to welfare. Neither implication is automatic, particularly because classification error does not account for the magnitude of lost rewards. In addition, any loss function based on deviation from a given target value is characterized by very different measures than a loss against a distribution optimum.
Weakness 3. Note that pure DP implies the more general (ϵ,δ)-DP, and in the setting of Algorithm 2, we are able to maintain this stronger notion of index privacy while still obtaining a constant-factor welfare approximation. In general, allowing δ>0 may improve these tradeoffs further, and we regard this as a valuable extension.