技术摘要：未知链接函数的单指数模型主动回归

问题定义

本文研究了在一般 $\ell_p$-损失（$p \ge 1$）下，针对单指数模型（single-index models）的主动回归（active regression）问题。目标是寻找一个向量 $x \in \mathbb{R}^d$ 和一个属于 1-Lipschitz 函数类（$\text{Lip}_1$）的链接函数 $f$，以最小化残差：
$$\min_{f \in \text{Lip}_1, x \in \mathbb{R}^d} \|f(Ax) - b\|_p^p$$
其中 $A \in \mathbb{R}^{n \times d}$ 是已知的观测矩阵（$n \gg d$），$b \in \mathbb{R}^n$ 是标签向量。该设定是主动式的，意味着算法可以完全访问 $A$，但只能通过坐标查询来访问 $b$。本文解决的核心挑战在于链接函数 $f$ 是未知的，这与先前假设 $f$ 已知的研究工作形成了对比。

方法论

上界：非自适应采样算法

作者提出了一种非自适应采样算法（算法 2），该算法扩展了用于线性回归和已知链接单指数模型的 Lewis weight 采样框架。

1. Lewis Weight 构建： 算法计算矩阵 $A$ 的 Lewis 权重 $w_1, \dots, w_n$。
2. 行拆分与采样： 从概念上讲，$A$ 的第 $i$ 行被拆分为 $k_i \approx w_i \cdot (n/d)$ 个副本。这些行以全局概率 $\alpha$ 进行独立采样。
3. 草图优化（Sketched Optimization）： 算法在草图实例上求解一个正则化极小化问题：
   $$(\hat{f}, \hat{x}) := \arg\min_{f \in \text{Lip}_1, x \in \mathbb{R}^d} \|S(f(Ax) - b)\|_p^p + \epsilon \|Ax\|_p^p$$
   其中 $S$ 是一个随机对角采样矩阵。

技术分析：控制未知链接

核心技术贡献在于界定当 $f$ 未知时的均匀采样误差。分析依赖于对集合 $T \subseteq \text{Lip}_1 \times \mathbb{R}^d$ 上的 Rademacher 过程 $\Psi$ 的控制。

• 对称化与 Dudley 积分： 误差使用应用于 Rademacher 过程的 Dudley 积分进行界定。
• 解耦挑战： 与先前具有乘积结构索引集（允许容易地解耦 $f$ 和 $x$）的工作不同，实现 $(1+\epsilon)$-近似的要求导致了一个非矩形索引集。作者在不等式链的中途而非在集合层面进行 $f$ 和 $x$ 的解耦。
• $\text{Lip}_1$ 的度量熵： 一个新颖的贡献是对非标准加权 sup-范数下的 Lipschitz 类度量熵的控制。作者引入了一个覆盖引理（引理 1.3），该引理通过将 $\text{Lip}_1$ 在加权范数下的覆盖数限制在 $[-1, 1]$ 上的标准 $L_\infty$ 覆盖数内，从而避免了先前 $p=2$ 结果中使用的显式离散化的技术开销。
• 自助法（Bootstrapping）： 采用自助法论证将解从常数因子近似精炼为 $(1+\epsilon)$-近似。

下界：困难实例构建

为了建立紧致性，作者构造了一个涉及以下要素的 $p > 2$ 的困难实例：

• 球面码（Spherical Code）： $N$ 个接近正交的单位向量，其相干性为 $\tau$。
• 隐藏索引： 一个均匀随机索引 $I \in [N]$ 被“植入”到响应向量 $b$ 中。
• ReLU 链接： 链接函数固定为 $f(t) = \max\{0, t\}$。
• 短名单保证： 分析表明，任何满足近似保证的算法都必须识别出一个包含真实 $I$ 的候选索引“短名单”。通过界定该短名单的大小，并将基准输入 $b(0)$ 与 $b(I)$ 的查询集进行比较，他们利用 Yao 的极小极大定理推导出了查询下界。

关键贡献与结果

1. 上界 (定理 1.1 / 3.2)

本文提出了一种随机算法，可在未知链接函数的情况下，针对一般 $p \ge 1$ 实现 $(1+\epsilon)$-近似。

• 查询复杂度： 该算法对 $b$ 进行 $O(d^{1 \vee p/2} / \epsilon^{p \vee 2} \cdot \text{poly}(\log n))$ 次非自适应查询。
• 重要性： 该结果严格改进了此前关于未知链接的唯一结果（该结果仅限于 $p=2$ 且为常数因子近似），并在 $n$ 的对数因子范围内匹配了已知链接情况下的查询复杂度。

2. 下界 (定理 1.2 / 4.2)

对于 $p > 2$，本文为查询复杂度建立了一个近乎紧致的下界。

• 复杂度： 在最坏情况下，任何实现近似保证的随机算法必须查询 $\Omega_p(d^{p/2} / (\epsilon^p (\log(d/\epsilon))^{p/2}))$ 个 $b$ 的条目（假设 $d \gtrsim \log(d/\epsilon)$）。
• 重要性： 这填补了 $p > 2$ 时的差距，表明现有的 $\tilde{O}(d^{p/2}/\epsilon^p)$ 上界在对数因子范围内对于自适应查询也是紧致的。

重要性与主张

本文声称填补了单指数模型主动 $\ell_p$-回归中大部分剩余的差距。

• 泛化性： 它将对线性模型和已知链接单指数模型的理解，扩展到了更具挑战性的未知链接函数及一般 $p \ge 1$ 的场景。
• 最优性： 通过为 $p > 2$ 提供匹配的上下界，并改进了 $p=2$ 时的近似保证，这项工作为该问题类提供了全面的查询复杂度表征。
• 技术新颖性： 为 Lipschitz 函数在加权范数下的覆盖引理的开发，以及在 Dudley 积分分析中处理非矩形索引集的方法，被视为实现通用 $p$ 结果的关键技术进展。

作者明确指出，虽然由于 Lipschitz 函数的内在覆盖数，目前上界中仍存在 $\log n$ 因子，但这些因子是否可以被消除仍是一个开放性问题。本文并未在随机数值线性代数框架之外提出实验验证或具体的现实应用。