The Critical Renyi Order for Sharp Minimax Channel Design

Abstract

We study categorical channel design under a bound on the maximum directed pairwise Renyi divergence. We determine exactly which orders make randomized response optimal in every dimension and at every finite budget: the orders strictly above one and at most two. In that range we identify the full information-trace frontier and its unique optimal anchored law. The channel is visibly thinned randomized response below a uniquely defined threshold and ordinary randomized response above it. A fixed-second-moment inequality and a second-order variational argument reduce arbitrary channel columns to singleton templates. Above order two, an explicit subset-selection channel beats every mixture of singleton templates in a finite dimension. The trace frontier also gives the exact finite-sample minimax risk among all unbiased real-valued vector estimators, and the asymptotic minimax risk among all estimators for every budget sequence with diverging total information. Appendices compare pure local privacy and distinguish homogeneous shuffle contamination from arbitrary neighboring datasets.

arXiv commentv2: complete rewrite with a new title; 23 pages; ancillary Python script. The v1 shuffle privacy envelope is restricted to homogeneous contamination (Appendix D), with a counterexample for arbitrary neighbors