提出首个近似最优的单指标模型主动回归算法，大幅减少对目标向量的查询次数。
Near-optimal Active Regression of Single-Index Models
- 设计新算法，在 Lipschitz 条件下实现 (1+ε) 近似解。
- 查询次数为 Õ(d^{p/2∨1}/ε^{p∨2})，对 p∈[1,2] 和 p>2 均接近最优。
- 适用于需高效获取目标数据的高维优化场景，如稀疏感知或实验设计。
单指标模型的主动回归问题旨在求解最小化‖f(Ax)−b‖_p，其中矩阵A完全可访问，而向量b只能通过逐项查询获取，目标是尽可能减少对b的查询次数。当f满足Lipschitz条件时，以往方法仅能获得常数因子近似。本文首次提出一个(1+ε)-近似算法，仅需查询Õ(d^{p/2∨1}/ε^{p∨2})个b的分量。该查询复杂度对p∈[1,2]被证明在对数因子内最优，且当p>2时，1/ε^p的ε依赖性也被证明最优。
原文摘要 · Abstract (English)
The active regression problem of the single-index model is to solve $\min_x \lVert f(Ax)-b\rVert_p$, where $A$ is fully accessible and $b$ can only be accessed via entry queries, with the goal of minimizing the number of queries to the entries of $b$. When $f$ is Lipschitz, previous results only obtain constant-factor approximations. This work presents the first algorithm that provides a $(1+\varepsilon)$-approximation solution by querying $\tilde{O}(d^{\frac{p}{2}\vee 1}/\varepsilon^{p\vee 2})$ entries of $b$. This query complexity is also shown to be optimal up to logarithmic factors for $p\in [1,2]$ and the $\varepsilon$-dependence of $1/\varepsilon^p$ is shown to be optimal for $p>2$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。