Minimax Quantile Lower Bounds for Interactive Statistical Decision Making with Privacy

arXiv:2606.23096v1 Announce Type: new Abstract: Minimax risk and regret are expectation-based criteria and do not capture rare but consequential failures. To address this concern, we develop a elta-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 elta and in the privacy budget for the private problems. They yield log(1/elta)/n scaling for squared-error Gaussian mean estimation, sqrt{Tlog(1/elta)} scaling for two-armed bounded-mean Gaussian bandits, and sqrt{KTlog(1/elta)}-type scaling for the K-armed bandits, with privacy appearing through a Gaussian variance-inflation factor for the private problems.

Source: arXiv cs.LG | 2026-06-23