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

arXiv: https://arxiv.org/abs/2606.14690 · HTML: https://mlsanity.com/paper/2606.14690/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 17 references that are in the map.
- First posted on arXiv 12 Jun 2026.

## Builds on (most cited first, 9 of 9)

- [Geometric Deep Learning on Molecular Representations](https://mlsanity.com/paper/2107.12375/) (2021)
- [An elementary introduction to information geometry](https://mlsanity.com/paper/1808.08271/) (2018)
- [Lipschitz Bandits: Regret Lower Bounds and Optimal Algorithms](https://mlsanity.com/paper/1405.4758/) (2014)
- [Structure-based drug design with geometric deep learning](https://mlsanity.com/paper/2210.11250/) (2022)
- [Unimodal Bandits: Regret Lower Bounds and Optimal Algorithms](https://mlsanity.com/paper/1405.5096/) (2014)
- [Network Geometry](https://mlsanity.com/paper/2001.03241/) (2020)
- [On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2008.08757/) (2020)
- [Upper-Confidence-Bound Algorithms for Active Learning in Multi-Armed Bandits](https://mlsanity.com/paper/1507.04523/) (2015)
- [A Survey of Geometric Optimization for Deep Learning: From Euclidean Space to Riemannian Manifold](https://mlsanity.com/paper/2302.08210/) (2023)

## Abstract (arXiv)

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.