# Learning Thresholds with Latent Values and Censored Feedback

arXiv: https://arxiv.org/abs/2312.04653 · HTML: https://mlsanity.com/paper/2312.04653/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 36 references that are in the map.
- First posted on arXiv 7 Dec 2023.

## Builds on (most cited first, 19 of 19)

- [Bandits and Experts in Metric Spaces](https://mlsanity.com/paper/1312.1277/) (2013)
- [Lipschitz Bandits: Regret Lower Bounds and Optimal Algorithms](https://mlsanity.com/paper/1405.4758/) (2014)
- [Smoothed Analysis with Adaptive Adversaries](https://mlsanity.com/paper/2102.08446/) (2021)
- [The Sample Complexity of Revenue Maximization](https://mlsanity.com/paper/1502.00963/) (2015)
- [Bilateral Trade: A Regret Minimization Perspective](https://mlsanity.com/paper/2109.12974/) (2021)
- [Efficient Statistics, in High Dimensions, from Truncated Samples](https://mlsanity.com/paper/1809.03986/) (2018)
- [Settling the Sample Complexity of Single-parameter Revenue Maximization](https://mlsanity.com/paper/1904.04962/) (2019)
- [Computationally and Statistically Efficient Truncated Regression](https://mlsanity.com/paper/2010.12000/) (2020)
- [Multi-Item Mechanisms without Item-Independence: Learnability via Robustness](https://mlsanity.com/paper/1911.02146/) (2019)
- [Efficient Truncated Statistics with Unknown Truncation](https://mlsanity.com/paper/1908.01034/) (2019)
- [A Regret Analysis of Bilateral Trade](https://mlsanity.com/paper/2102.08754/) (2021)
- [The Role of Transparency in Repeated First-Price Auctions with Unknown Valuations](https://mlsanity.com/paper/2307.09478/) (2023)
- [Censored Semi-Bandits: A Framework for Resource Allocation with Censored Feedback](https://mlsanity.com/paper/1909.01504/) (2019)
- [Pricing Query Complexity of Revenue Maximization](https://mlsanity.com/paper/2111.03158/) (2021)
- [Efficient Empirical Revenue Maximization in Single-Parameter Auction Environments](https://mlsanity.com/paper/1610.09976/) (2016)
- [On the Minimax Regret for Online Learning with Feedback Graphs](https://mlsanity.com/paper/2305.15383/) (2023)
- [Reserve Price Optimization for First Price Auctions](https://mlsanity.com/paper/2006.06519/) (2020)
- [Description Complexity of Regular Distributions](https://mlsanity.com/paper/2305.05590/) (2023)
- [Effective Dimension in Bandit Problems under Censorship](https://mlsanity.com/paper/2302.06916/) (2023)

## Built on by (most cited first, 3 of 3)

- [Generalization Error Bounds for Learning under Censored Feedback](https://mlsanity.com/paper/2404.09247/) (2024)
- [Pricing Query Complexity of Multiplicative Revenue Approximation](https://mlsanity.com/paper/2602.10483/) (2026)
- [Cost of Structural Learning Under Censored Feedback: A Threshold-Bandit Approach](https://mlsanity.com/paper/2605.27076/) (2026)

## Abstract (arXiv)

In this paper, we investigate a problem of actively learning threshold in latent space, where the unknown reward g(γ, v) depends on the proposed threshold γ and latent value v and it can be only achieved if the threshold is lower than or equal to the unknown latent value. This problem has broad applications in practical scenarios, e.g., reserve price optimization in online auctions, online task assignments in crowdsourcing, setting recruiting bars in hiring, etc. We first characterize the query complexity of learning a threshold with the expected reward at most ε smaller than the optimum and prove that the number of queries needed can be infinitely large even when g(γ, v) is monotone with respect to both γ and v. On the positive side, we provide a tight query complexity tildeTheta(1/ε3) when g is monotone and the CDF of value distribution is Lipschitz. Moreover, we show a tight tildeTheta(1/ε3) query complexity can be achieved as long as g satisfies one-sided Lipschitzness, which provides a complete characterization for this problem. Finally, we extend this model to an online learning setting and demonstrate a tight Theta(T2/3) regret bound using continuous-arm bandit techniques and the aforementioned query complexity results.