Search papers, labs, and topics across Lattice.
This paper develops a $δ$-explicit minimax-quantile theory for interactive statistical decision making (ISDM) that addresses the limitations of traditional minimax risk and regret by incorporating quantile-based criteria to capture rare but significant failures. The authors establish structural relationships between minimax quantiles and risk, and introduce high-probability tools for ISDM that accommodate mutual-information privacy by restricting decision classes. Key results include explicit lower bounds for Gaussian mean estimation and K-armed bandits, demonstrating that privacy considerations lead to variance inflation and affect scaling behaviors in decision-making scenarios.
Rare failures in decision-making can be quantified and bounded, revealing new insights into the trade-offs between privacy and performance in interactive settings.
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.
