arXiv:2606.11130cs.LG2026-06NeurIPS被引 1

通过查询提升非齐次ReLU的鲁棒回归效率,显著减少标签需求。

Robust Regression of General ReLUs with Queries

  • 引入交互式查询机制,以极少标签完成高精度学习
  • 仅需 $d \text{polylog}(1/\varepsilon) + \tilde{O}(\min\{1/p, 1/\varepsilon\})$ 查询次数
  • 证明查询必要性:被动学习无法在标签数上突破

我们研究在高斯分布下,针对平方损失对一般(非齐次)ReLu进行抗扰动学习的问题。在被动学习设定中,已有工作提出了一个计算高效的算法,使用 $\text{poly}(d,1/\varepsilon)$ 个带标签样本,输出误差为 $O(opt)+\varepsilon$,其中 $opt$ 是最优拟合 ReLU 的平方损失。本文聚焦于交互式学习设定,即学习者可对未标记样本进行标签查询。主要成果是首个计算高效的算法,仅需 $d \text{polylog}(1/\varepsilon) + \tilde{O}(\min\{1/p, 1/\varepsilon\})$ 个黑盒标签查询,即可实现 $O(opt)+\varepsilon$ 的误差。我们进一步证明该查询复杂度在定性意义上接近最优,即使忽略计算开销亦然。最后,我们证明:要优于被动学习的标签复杂度,查询访问几乎是必需的;对于基于池的主动学习,除非抽取超多项式数量的未标记样本,否则任何主动学习者均需 $\tilde{\Omega}(d/\varepsilon)$ 个标签。

原文摘要 · Abstract (English)

We study the task of agnostically learning general (as opposed to homogeneous) ReLUs under the Gaussian distribution with respect to the squared loss. In the passive learning setting, recent work gave a computationally efficient algorithm that uses $poly(d,1/ε)$ labeled examples and outputs a hypothesis with error $O(opt)+ε$, where $opt$ is the squared loss of the best fit ReLU. Here we focus on the interactive setting, where the learner has some form of query access to the labels of unlabeled examples. Our main result is the first computationally efficient learner that uses $d polylog(1/ε)+\tilde{O}(\min\{1/p, 1/ε\})$ black-box label queries, where $p$ is the bias of the target function, and achieves error $O(opt)+ε$. We complement our algorithmic result by showing that its query complexity bound is qualitatively near-optimal, even ignoring computational constraints. Finally, we establish that query access is essentially necessary to improve on the label complexity of passive learning. Specifically, for pool-based active learning, any active learner requires $\tildeΩ(d/ε)$ labels, unless it draws a super-polynomial number of unlabeled examples.

机器学习主动学习回归分析查询学习

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