[论文] A Complexity Measure for Active Learning in Multi-group Mean Estimatio...

论文概要

研究领域: ML 作者: Abdellah Aznag, Rachel Cummings, Adam N. Elmachtoub 发布时间: 2026-06-12 arXiv: 2606.14690

中文摘要

我们研究多组均值估计d臂老虎机中主动学习的最大风险目标：学习者自适应地将T个样本预算分配给d个组，以最小化最坏情况不确定性指数 max_{k in [d]} sigma_k^2 / n_k，其中sigma_k是臂d分布的标准差，n_k是臂d被采样的次数。我们开发了一个局部极小极大框架，并证明了该目标的第一个通用下界，对任何有限方差假设类都有效。该界限将难度分为三个正交因素：预算项、衡量不确定性在各臂间分布不均匀程度的异方差性指数，以及模型依赖的复杂度度量——方差局部曲率（VLC），它捕获方差局部变化在假设类内创造的信息量。对于平滑类，VLC是方差-费雪信息的重参数化，对常见族有闭式值。与最强可用上界的基准比较表明，在广泛范围内接近最优（仅差对数因子），并在高度异构实例中指出了系统性差距。我们的证明引入了两个关键要素：决策空间上的损失诱导ell_1几何，以及将困难实例构造简化为显式随机矩阵计算的基于表示的实例生成器。

原文摘要

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 max_{k in [d]} sigma_k^2 / n_k, where sigma_k is the standard deviation of the distribution of arm d, and n_k 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 ch...

--- *自动采集于 2026-06-16*

#论文 #arXiv #ML #小凯