arXiv:2606.14690cs.LGcs.IT2026-06

提出多组均值估计中主动学习的复杂度度量,量化样本分配最优性。

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

  • 基于最大风险目标构建局部极小极大框架,分析样本分配策略。
  • 首次证明通用下界,分离出预算、异方差性和模型复杂度三要素。
  • 引入新复杂度指标VLC,适用于平滑模型且可计算,适合理论研究者。

我们研究多组均值估计 $d$-臂老虎机中的最大风险目标:学习者在 $T$ 次采样预算下,自适应分配样本到 $d$ 个组,以最小化最坏情况下的不确定性指标 $ ext{max}_{k o[d]} σ_k^2/n_k$,其中 $σ_k$ 为第 $k$ 组的方差,$n_k$ 为该组采样次数。我们建立局部极小极大框架,证明了首个针对任意有限方差假设类的通用下界。该下界将难度分解为三个正交因素:预算项、衡量不确定性分布不均的异方差性指数,以及依赖于模型的复杂度度量——方差局部曲率(Variance Local Curvature, VLC),其反映局部方差变化在假设类中产生的信息量。对于光滑类,VLC 可重参数化为方差-费舍尔信息形式,并对常见分布族给出闭式表达。与最强上界对比表明,在广泛场景下接近最优,仅差对数因子;在高度异方差情形中揭示系统性差距。证明引入两个关键工具:由损失诱导的决策空间 $oldsymbol{ ext{l}_1}$ 几何,以及基于表示的实例生成器,将难例构造转化为显式随机矩阵计算。

原文摘要 · Abstract (English)

We study a \emph{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]}σ_k^2/n_k$, where $σ_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 \emph{budget} term, a \emph{heteroscedasticity} index measuring how unevenly the uncertainty is spread across arms, and a model-dependent complexity measure, the \emph{Variance Local Curvature} ($\mathrm{VLC}$), which captures how much information a local change of variance creates inside the hypothesis class. 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.

主动学习统计推断复杂度度量多组估计

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。