A Complexity Measure for Active Learning in Multi-group Mean Estimation: Variance Local Curvature

Summary

This arXiv paper (2606.14690) by Abdellah Aznag, Rachel Cummings, and Adam N. Elmachtoub studies a max-risk objective for active learning in multi-group mean estimation modeled as d-armed bandits. A learner adaptively allocates a budget of T samples across d groups to minimize the worst-case uncertainty index max sigma_k^2 / n_k, where sigma_k is the standard deviation of arm k and n_k is its sample count. The authors develop a local minimax framework and prove the first general lower bound for this objective, valid for any finite-variance hypothesis class. The bound decomposes difficulty into three orthogonal factors: a budget term, a heteroscedasticity index capturing how unevenly uncertainty is spread across arms, and a model-dependent complexity measure called Variance Local Curvature (VLC). For smooth classes, VLC is a reparameterization of variance-Fisher information with closed forms for common families. Benchmarks against the strongest known upper bounds show near-optimality up to logarithmic factors, while revealing systematic gaps in highly heterogeneous instances. Key proof techniques include a loss-induced l1 geometry on the decision space and a representation-based instance generator reducing hard-instance constructions to explicit random matrix computations.