A Complexity Measure for Active Learning in Multi-group Mean Estimation

We study a max-risk objective for active learning in a multi-group mean estimation d-armed bandits: a learner adaptively allocates a budget of T samples across d groups to minimize the worst-case uncertainty index maxk∈[d]σk2/nk, where σk is the standard deviation of the distribution of arm d, and nk is the number of times arm d is sampled. We develop a local minimax framework and prove the first general lower bound for this objective, valid for any finite-variance hypothesis class. The bound separates difficulty into three orthogonal factors: a budget term, a heteroscedasticity index measuring how unevenly the uncertainty is spread across arms, and a model-dependent complexity measure, the Variance Local Curvature (VLC), which captures how much information a local change of variance creates inside the hypothesis class. For smooth classes, the VLC is a reparametrization of a variance--Fisher information, with closed-form values for common families. Benchmarking against the strongest available upper bound shows near-optimality up to logarithmic factors in broad regimes, and pinpoints a systematic gap in highly heterogeneous instances. Our proof introduces two key ingredients: a loss-induced ℓ1 geometry on the decision space, and a representation-based instance generator that reduces hard-instance construction to an explicit random matrix calculation.