提出新方法解决未知链接函数下的单指标回归问题。
Active Regression for Single-Index Models with Unknown Link Functions
- 设计非自适应采样算法，高效逼近最优解。
- 理论证明在 p>2 时查询次数接近最优，误差可控。
- 适合关注高维回归与主动学习的算法研究者。
本文研究在一般 ℓ_p 损失下，具有未知 1-利普希茨链接函数的单指标模型主动回归问题，形式化为 min_{f,x} ||f(Ax)−b||_p^p，其中可完全访问矩阵 A，但仅能通过坐标查询获取 b。已有工作对已知链接函数在所有 p≥1 情况下建立了上界，对未知链接函数仅在 p=2 时成立，并给出 p≤2 时的下界。本文填补了未知链接函数与一般 p≥1 情况下的空白：提出一种非自适应采样算法，可在使用 O(d^{p/2∨1}/ε^{p∨2} poly log(n/ε)) 次查询的情况下实现 (1+ε) 近似解；同时建立接近紧致的 p>2 下界。这些结果基本弥合了单指标模型主动 ℓ_p 回归中的剩余差距。
原文摘要 · Abstract (English)
This paper studies active regression for single-index models under general $\ell_p$-loss with an unknown $1$-Lipschitz link function $f$, formulated as $\min_{f,x} \|f(Ax)-b\|_p^p$ with full access to $A$ but coordinate-query access to $b$. Prior work established upper bounds for known link functions for all $p\geq 1$ and for unknown link functions only in the $p=2$ case, together with lower bounds for $p\leq 2$. This work addresses the more challenging setting of unknown link functions and general $p \geq 1$. A non-adaptive sampling algorithm is presented that achieves a $(1+ε)$-approximation using $O(d^{p/2\vee 1}/ε^{p\vee 2}\operatorname{poly}\log(n/ε))$ queries. Nearly tight lower bounds are also established for $p>2$. These results close much of the remaining gap in active $\ell_p$-regression for single-index models.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。