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

Abstract

We study a max-risk objective for active learning in d-armed bandits: a learner adaptively allocates a budget of T samples across d groups to minimize the worst-case per-group uncertainty index max_k∈[d]σ_k^2/n_k. 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 curvature functional, the Variance Local Curvature (VLC), which captures how much information a local change of variance creates inside ℋ. 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.