acceptodds
Under review as a conference paper at ICLR 2027

Private Prophets

Abstract

Prophet inequalities are a basic problem in decision making: values drawn independently from fixed distributions arrive sequentially and a mechanism must irrevocably select one while competing with the expected maximum. In the learning version of the problem, distributions are unknown, but we are given independently drawn samples from each distribution from which a mechanism is learned. Our focus is differentially private learning, requiring the learned decision rule to be insensitive to any single training sample. We study two natural notions of privacy. First, we consider public threshold mechanisms, which release a collection of thresholds and accept the first value exceeding its corresponding decision threshold. Second, we consider index-private mechanisms where only the identity of the selected element is released. For both privacy notions, we obtain essentially tight sample-privacy-utility tradeoffs.

Primary area:
learning theory
Keywords:
Online Algorithms, Prophet Inequalities, Differential Privacy

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_K3H7OpenReview ↗
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 nn distributions, where samples are drawn independently one at a time. The training data is a matrix of size L×nL \times n, where LL 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 nn streams of training data. The paper considers two kinds of mechanisms, index release mechanisms (release i∈[n]i \in [n], 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
3 comments
AuthorsOpenReview ↗

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 nn. We instead exploit the stochastic arrivals to control premature acceptance and establish constant competitiveness with L=O(1/ϵ)L=O(1/\epsilon) samples per distribution, independently of nn.

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 (ϵ,δ)(\epsilon,\delta)-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\delta>0 may improve these tradeoffs further, and we regard this as a valuable extension.

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 nn bidders, this corresponds to the expected social welfare.

Reviewer_M72NOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies prophet inequalities under differential privacy. In the prophet inequality problem, values arrive sequentially from distributions, and the decision maker must immediately and irrevocably decide whether to accept the current value, with the goal of selecting a value close to the maximum. The paper proposes private mechanisms under two privacy notions: (1) threshold privacy, where the selection threshold is released privately; and (2) index privacy, where only the index and value of the selected element are released. It theoretically characterizes the resulting trade-offs among sample complexity, privacy, and utility.

Critical strengths
  • The paper introduces a novel problem at the intersection of prophet inequalities and differential privacy.
  • The theoretical analysis is comprehensive.
Critical weaknesses
  • The paper has no experiments and does not present a concrete scenario in which this form of privacy protection is needed.
  • The connection to machine learning theory is weak.
  • The algorithmic novelty appears limited (see Questions).
  • It is unclear how the privacy guarantee degrades when the same learned rule is reused across multiple instances.
Questions for authors
  • Could the authors add experiments, or explain why they are unnecessary for the paper's claims?
  • Could the authors describe a concrete scenario in which privacy protection is required for this problem?
  • Algorithm 1 appears to be a variant of the standard exponential-mechanism-based private quantile estimator [1], and Algorithm 2 appears to be a variant of the Sparse Vector Technique [2]. Are these works cited and discussed? Please clarify what is new relative to them.
  • How does the privacy loss compose when the same learned rule is used to serve multiple online sequences?

[1] Smith, Adam. "Privacy-preserving statistical estimation with optimal convergence rates." Proceedings of the forty-third annual ACM symposium on Theory of computing. 2011.

[2] Dwork, Cynthia, et al. "On the complexity of differentially private data release: efficient algorithms and hardness results." Proceedings of the forty-first annual ACM symposium on Theory of computing. 2009.

1 comment
AuthorsOpenReview ↗

Reply to your questions.

We thank the reviewer for their comments and insights and attempt to address their questions below. Q1. Our submission is intended as a learning-theory paper: our claims are proven worst-case guarantees and matching lower bounds. Experiments could illustrate particular instances, but may not give further intuition on why the bounds hold in general.

Q2. There is a recent but extensive computer science literature on prophet inequalities motivated by the applications to pricing items in online marketplaces. Consider any online platform selling relatively inexpensive items. For many such platforms, it is a fair assumption that buyers arrive online and make an instantaneous decision, without planning to return at a later time. Such a platform may want to use historical valuations to learn a posted price to offer to these sequentially arriving buyers, without exposing any individual historical records. Differential privacy makes this possible.

Q3.

Algorithm 1 Citation: We will add the missing citation to Smith, Adam (STOC ’11) on the exponential mechanism for quantile estimation.

New ideas: Standard private quantile guarantees describe how accurately a threshold locates a target rank in the training data. Our problem requires a different guarantee: how much reward is obtained by accepting the first online value above that threshold. We choose thresholds on a dyadic grid and analyze them through symmetrization: we pair two draws from each distribution and randomly assign their roles as training sample and online value. This lets us control both the threshold’s magnitude and whether the online sequence crosses it.

Algorithm 2 Citation: Algorithm 2 is an instantiation of the AboveThreshold mechanism described in Dwork and Roth (2014), applied to our pooled sample-rank queries. We thank the reviewers for pointing out the missing attribution and will add the citation when we introduce Algorithm 2.

New Ideas: AboveThreshold provides the privacy guarantee, but does not by itself establish a prophet inequality. Our contribution is to analyze the stopping rule obtained by applying it to the queries c(s,xi)c(s,x_i). We control the probability of premature acceptance using the aggregate tail probabilities of the underlying distributions, while showing that sufficiently high values are selected with constant probability. The standard uniform accuracy analysis (Dwork and Roth, Theorem 3.24) of AboveThreshold introduces a logarithmic dependence on the number of queries, while our reward analysis avoids this factor.

Q4: The two mechanisms differ in this respect. A privately released threshold can be reused without additional privacy loss, since subsequent decisions do not affect the value of the chosen threshold. Algorithm 2 does not provide the same guarantee of unrestricted reuse at a fixed privacy budget. This is because it does not output a numerical threshold but rather a rank that depends on the given instance and randomness. Exact quantification of the privacy loss is indeed an interesting question for further investigation.

Reviewer_KWgcOpenReview ↗
Rating
4
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This work studies prophet inequalities under pure differential privacy. Prophet inequalities generally concern the problem in online stochastic optimization of selecting an approximation to the maximal element from a sequence drawn from distributions.

This work gives two prophet inequalities, both in the setting in which the distributions are not fully specified beforehand and only samples are available. The work motivates the constraint of privacy for prophet inequalities as offering a robust learning rule in the sample access setting.

The first prophet inequality concerns the setting where only a single sample per distribution is available and it is desired that the policy is based on a private threshold. In this case, the authors show matching upper/lower bounds under pure differential privacy. While the maximal element cannot be approximated in expectation, the qqth best element can be up to an additive error where qq is roughly log⁡(log⁡(B))/ε\log(\log(B))/\varepsilon and BB is a bound on the support of the distributions.

The second prophet inequality concerns the setting where multiple samples per distribution are available and only the index released by the policy must be private. Here, the authors again show matching upper/lower bounds under pure differential privacy. In this case, the best element can be approximated up to a constant as in the classic non-private setting, at the expense of requiring on the order of 1/ε1/\varepsilon samples per distribution.

Critical strengths

This work appears to be the first to address prophet inequalities under central pure DP constraints. Both presented prophet inequalities tightly characterize two different relatively natural and clearly defined settings.

The paper is also clearly written and easy to follow.

Critical weaknesses

While it is not a major issue, the motivation for first setting (single sample + private threshold) is not very clear to me. It seems natural to me to characterize the single sample setting but it is not clear to me why it is necessary to impose the private threshold assumption when ultimately only the selected index is to be released.

Questions for authors

Can the authors explain why the private threshold + single sample setting is indepently interesting compared to, say, simply the single sample setting?

Also, one of the main motivations for studying prophet inequalities under privacy is to ensure robustness. Can the authors say what it known about these settings when a robustness constraint is directly imposed, as opposes to relying on privacy?

2 comments
AuthorsOpenReview ↗

Reply to your questions.

Thank you for your questions and the positive assessment.

Q1. Threshold-based policies are standard in prophet inequalities. Threshold privacy matters when the learned rule is public, for example, when a posted price is learned from confidential historical valuations. It also allows us to release a threshold once and reuse it without further privacy loss. The single-sample setting isolates the cost of this requirement relative to the classical 1/21/2-competitive guarantee. We also cover multiple samples in Appendix A. Q2. On robustness, pure DP gives a precise guarantee against sample manipulation: replacing tt training entries changes output-event probabilities by at most a factor etϵe^{t\epsilon}. This covers a bounded number of adversarial corruptions or erroneous observations. For robustness imposed directly, Dütting and Kesselheim (2019) study inaccurate priors and establish welfare-loss bounds in terms of distributional distance. We will discuss this connection.

Thank you for the clarifications! I have no further questions.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.