Imagine you run a thermostat, but instead of a fixed temperature setting, you want the thermostat to observe the room and pick its own setting. The catch: if the thermostat ever overshoots — even once — the building inspector shuts you down. You need a way to let the thermostat adapt while guaranteeing it never exceeds the safety limit. That is the core mechanism of this paper: replacing a fixed, worst-case "temperature" in the exponential mechanism of differential privacy with a data-dependent one, without ever violating the privacy guarantee. The committed claim: for the first time, the authors systematically map out when and how dataset-dependent (local) sensitivity can safely replace global sensitivity in private selection, and they provide three distinct valid approaches with formal regret bounds for each. This is not a single new mechanism — it is a taxonomy of valid calibration strategies, which is arguably more useful. The three approaches are cleanly separated. First, a private high-probability upper bound on local sensitivity yields approximate DP, extendable to finite higher-order sensitivity hierarchies. Second, a Propose-Test-Release (PTR) variant privately searches a finite public grid for a temperature scale rather than committing to one in advance. Third, smooth sensitivity supports multiple designs: a candidate-independent smooth geometric construction that fits the local dampening framework, and a logarithmic transformation that produces a smoothed score with controlled global sensitivity while preserving the maximizers of the original utility. Both smooth sensitivity designs yield range-independent pure DP. Where does this sit on the ladder? The exponential mechanism (McSherry & Talwar, 2007) is the baseline. Subsequent work on smooth sensitivity (Nissim, Raskhodnikova, Smith, 2007), local dampening (Farhadi et al., 2022), and PTR variants have each addressed pieces of this problem. This paper's contribution is unifying these threads, showing failure modes of naive local-sensitivity substitution, and providing the first systematic regret analysis across all three approaches. It does not claim to beat any single prior method on a benchmark — it claims to complete the map. The integrity posture is theoretical. Every mechanism comes with a formal proof and a high-probability regret bound under stated conditions. There are no experiments, no empirical benchmarks, no code. This is a theory paper in the classical sense: the "grading" is mathematical proof, which is the strongest form of validation for this type of claim. The absence of experiments is not a weakness — it would be a weakness if the claims were empirical. The milestone question for local sensitivity in DP selection is practical adoption. The exponential mechanism with global sensitivity is used in production systems (e.g., Google's RAPPOR, Apple's differential privacy deployments). The gap between theory and deployment is not qubit-count-style hardware scaling — it is implementation complexity and practitioner trust. The next concrete milestone is an open-source implementation with empirical benchmarks on standard DP selection tasks (e.g., private top-k, private hyperparameter tuning) demonstrating measurable utility gains over global-sensitivity EM. The obvious experiment not run: empirical evaluation on real or synthetic datasets showing how much utility is actually gained by switching from global to local sensitivity calibration across the three approaches. The honest read is (a) — the authors are theorists and this is a theory contribution. The empirical follow-up is a different paper, likely by a different team.
