Minimax Quantile Lower Bounds for Interactive Statistical Decision Making with Privacy
2026-06-22 • Machine Learning
Machine LearningInformation Theory
AI summaryⓘ
The authors focus on improving decision-making methods by considering not just average outcomes, but also rare, impactful failures. They develop a theory that explicitly incorporates confidence levels (δ) into the risk assessment, connecting it to traditional risk concepts. They introduce new techniques to analyze decisions made interactively and show how privacy constraints affect these decisions. Using Gaussian models, they provide concrete examples and derive lower bounds that clearly show how confidence and privacy impact the difficulty of estimation and learning problems. Their results give precise formulas for error rates and exploration costs depending on the confidence level and privacy budget.
minimax riskquantileinteractive statistical decision makingFano's methodLe Cam's methodmutual-information privacyGaussian mean estimationmulti-armed banditsconfidence levelprivacy budget
Authors
Raghav Bongole, Amirreza Zamani, Tobias J. Oechtering, Mikael Skoglund
Abstract
Minimax risk and regret are expectation-based criteria and do not capture rare but consequential failures. To address this concern, we develop a $δ$-explicit minimax-quantile theory for interactive statistical decision making (ISDM). We first provide structural relations between minimax quantiles, lower minimax quantiles, and minimax risk. This includes a quantile-to-expectation conversion and an equivalence between strict and lower minimax quantiles outside a countable set of confidence levels. We then derive two converse tools for ISDM: a high-probability interactive Fano's method and a high-probability interactive Le Cam's method. Then, we show that mutual-information (MI) privacy can be handled in the same framework by restricting the admissible decision class. For coordinatewise Gaussian privatization, we derive a two-point template that isolates the privacy-induced variance inflation. We instantiate this template for Gaussian mean estimation, and use the same two-point strategy directly for two-armed Gaussian bandits. We then derive a minimax quantile lower bound for the $K$-armed Gaussian bandit problem, showing that the interactive Fano method captures the exploration cost over multiple possible best arms. The resulting lower bounds are explicit in the confidence level $δ$ and in the privacy budget for the private problems. They yield $\log(1/δ)/n$ scaling for squared-error Gaussian mean estimation, $\sqrt{T\log(1/δ)}$ scaling for two-armed bounded-mean Gaussian bandits, and $\sqrt{KT\log(1/δ)}$-type scaling for the $K$-armed bandits, with privacy appearing through a Gaussian variance-inflation factor for the private problems.