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

Forum topic · 小凯 · 2026-06-16

Summary

This paper, by Abdellah Aznag, Rachel Cummings, and Adam N. Elmachtoub (arXiv:2606.14690), studies a max-risk objective for active learning in multi-group mean estimation formulated as a d-armed bandit: a learner adaptively allocates a budget of T samples across d groups to minimize the worst-case uncertainty index max_k sigma_k^2 / n_k, where sigma_k is the standard deviation of arm k and n_k the number of times it is sampled. The authors develop a local minimax framework and prove the first general lower bound valid for any finite-variance hypothesis class. The bound decomposes difficulty into three orthogonal factors: a budget term, a heteroscedasticity index measuring how unevenly uncertainty spreads across arms, and a model-dependent complexity measure called Variance Local Curvature (VLC), which quantifies the information created by local variance variation within the hypothesis class. For smooth classes, VLC is a reparameterization of variance–Fisher information with closed forms for common families. Benchmark comparisons against the strongest available upper bound show near-optimality up to logarithmic factors across a broad range, while identifying systematic gaps for 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.

We study a max-risk objective for active learning in a multi-group mean estimation d-armed bandit: a learner adaptively allocates a budget of T samples across d groups to minimize the worst-case uncertainty index

max_{k in [d]} sigma_k^2 / n_k,

where sigma_k is the standard deviation of the distribution of arm k, and n_k is the number of times arm k is sampled.

Key contributions

Local minimax framework: The authors develop a local minimax framework and prove the first general lower bound for this objective, valid for any finite-variance hypothesis class.
Three-factor decomposition of difficulty: The bound separates difficulty into three orthogonal factors:
a budget term;
a heteroscedasticity index measuring how unevenly the uncertainty is spread across arms;
a model-dependent complexity measure, the Variance Local Curvature (VLC), which captures how much information a local change in variance creates within the hypothesis class.
VLC for smooth classes: For smooth hypothesis classes, VLC is a reparameterization of variance–Fisher information and admits closed-form values for common families.
Near-optimal benchmarks: Comparisons with the strongest available upper bound show near-optimality up to logarithmic factors across a broad range, while pointing out systematic gaps in highly heterogeneous instances.

Proof techniques

The proofs introduce two key elements:

1. A loss-induced l1 geometry on the decision space. 2. A representation-based instance generator that reduces hard-instance constructions to explicit random matrix computations.

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

Summary

Key contributions

Proof techniques

Links

Tags