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

Abdellah Aznag, Rachel Cummings, Adam N. Elmachtoub
Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:472-473, 2026.

Abstract

We study a \emph{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\in[d]}\sigma_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 $\mathcal H$. The bound separates difficulty into three orthogonal factors: a \emph{budget} term, a \emph{heteroscedasticity} index measuring how unevenly the uncertainty is spread across arms, and a model-dependent curvature functional, the \emph{Variance Local Curvature} ($\mathrm{VLC}$), which captures how much information a local change of variance creates inside $\mathcal H$. For smooth classes, the $\mathrm{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 $\ell_1$ geometry on the decision space, and a representation-based instance generator that reduces hard-instance construction to an explicit random matrix calculation.

Cite this Paper

BibTeX
@InProceedings{pmlr-v336-aznag26a, title = {A Complexity Measure for Active Learning in Multi-group Mean Estimation}, author = {Aznag, Abdellah and Cummings, Rachel and Elmachtoub, Adam N.}, booktitle = {Proceedings of Thirty Ninth Conference on Learning Theory}, pages = {472--473}, year = {2026}, editor = {Hanneke, Steve and Lattimore, Tor}, volume = {336}, series = {Proceedings of Machine Learning Research}, month = {29 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v336/main/assets/aznag26a/aznag26a.pdf}, url = {https://proceedings.mlr.press/v336/aznag26a.html}, abstract = {We study a \emph{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\in[d]}\sigma_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 $\mathcal H$. The bound separates difficulty into three orthogonal factors: a \emph{budget} term, a \emph{heteroscedasticity} index measuring how unevenly the uncertainty is spread across arms, and a model-dependent curvature functional, the \emph{Variance Local Curvature} ($\mathrm{VLC}$), which captures how much information a local change of variance creates inside $\mathcal H$. For smooth classes, the $\mathrm{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 $\ell_1$ geometry on the decision space, and a representation-based instance generator that reduces hard-instance construction to an explicit random matrix calculation.} }
Endnote
%0 Conference Paper %T A Complexity Measure for Active Learning in Multi-group Mean Estimation %A Abdellah Aznag %A Rachel Cummings %A Adam N. Elmachtoub %B Proceedings of Thirty Ninth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2026 %E Steve Hanneke %E Tor Lattimore %F pmlr-v336-aznag26a %I PMLR %P 472--473 %U https://proceedings.mlr.press/v336/aznag26a.html %V 336 %X We study a \emph{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\in[d]}\sigma_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 $\mathcal H$. The bound separates difficulty into three orthogonal factors: a \emph{budget} term, a \emph{heteroscedasticity} index measuring how unevenly the uncertainty is spread across arms, and a model-dependent curvature functional, the \emph{Variance Local Curvature} ($\mathrm{VLC}$), which captures how much information a local change of variance creates inside $\mathcal H$. For smooth classes, the $\mathrm{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 $\ell_1$ geometry on the decision space, and a representation-based instance generator that reduces hard-instance construction to an explicit random matrix calculation.
APA
Aznag, A., Cummings, R. & Elmachtoub, A.N.. (2026). A Complexity Measure for Active Learning in Multi-group Mean Estimation. Proceedings of Thirty Ninth Conference on Learning Theory, in Proceedings of Machine Learning Research 336:472-473 Available from https://proceedings.mlr.press/v336/aznag26a.html.

Related Material