Published October 23, 2026 | Version v1

Instance-Optimal Identity Testing at the Original Total-Variation Radius: Resolving Canonne's 2024 Open Question 1

Authors/Creators

  • 1. Wuhan university

Description

Instance-optimal identity testing seeks the number of samples needed to distinguish an unknown distribution from a specified discrete reference at a given total-variation radius. Existing characterizations evaluate their functionals at different constant multiples of the radius, which can leave an arbitrarily large gap in sample complexity. We give an explicit functional that characterizes the fixed-sample complexity up to universal constants at the original radius, for every finite or countable reference distribution. The functional combines a strictly concave allocation problem with a truncated 3/2-moment and a count-fluctuation term for a heavy largest atom. Matching tests and normalized lower-bound priors establish the characterization throughout the radius interval, including transitions at the mass outside a largest atom and the regime of almost disjoint alternatives. For explicit rational input, a deterministic algorithm computes a factor-two bracket for the functional in polynomial bit complexity. This answers Open Question 1 posed by Canonne at COLT 2024 in the model of distributions on a countable alphabet.

Files

instance_optimal_identity_testing_v1.pdf

Files (544.4 kB)

Name Size
md5:828f994723a4e91d60e565e3687212ba
501.1 kB Preview Download
md5:f54797c642e339a487dca7cda190e20d
43.3 kB Preview Download