ReLU组合学习获全多项式时间突破

引言

PAC学习ReLU激活函数的正线性组合是机器学习理论中的基础问题。近日，一项新研究提出了首个全多项式时间算法，在$\mathbb{R}^d$上关于高斯分布、以$L_2$损失学习$k$个任意ReLU的正线性组合。该算法抽取$\mathrm{poly}(d, k, 1/\epsilon)$个样本，运行时间为$\mathrm{poly}(d, k, 1/\epsilon)$，并以高概率输出与目标概念$\epsilon$-接近的假设。此前所有算法都需要在$k$或$1/\epsilon$上超多项式的时间，或依赖强良态假设。

技术核心：弱学习器与提升框架

该算法的核心是一个新颖的提升（boosting）过程，用于以列表可解码（list-decodable）方式将隐藏权重向量恢复到常数误差。具体而言，研究团队开发了一种“弱”学习过程，利用隐式张量计算技术，基于目标函数的Hermite张量构建低阶过滤过程。这一过程放大了权重向量（簇）之间的分离度，从而将每个权重向量学习到常数误差。

随后，作者论证了同一过程可用于改进隐藏权重向量的估计，通过在欧几里得球面上进行类梯度下降更新。算法的一个关键组件是剪枝方法，确保算法仅维护那些在目标精度上近似隐藏权重向量的相关向量。

突破性意义

这是首个在没有任何强假设下实现全多项式时间的算法。先前方法要么计算复杂度过高，要么要求权重矩阵满足强良态条件，限制了实际应用。新算法通过隐式张量计算和剪枝策略，有效解决了这些限制。

列表可解码（list-decodable）学习是统计学习中的一种放宽的恢复模型：算法不要求输出单一假设，而是允许输出一个大小不超过预设上限的候选列表，只要目标概念（或其参数）以较高概率出现在列表中即可。该模型特别适用于数据中存在大量噪声或标签错误的情形——在标准PAC框架下，若噪声比例超过某个阈值，任何算法都无法唯一恢复目标；而列表可解码允许算法在“高噪声”条件下仍能以多项式时间输出一个包含真实参数的短列表。本文正是利用这一框架，将ReLU组合学习转化为对多个隐藏权重向量的列表式恢复问题。

Hermite张量是函数在Hermite多项式基下的高阶展开系数所构成的对称张量，常用于分析高斯分布下的函数学习问题。对于形如 (f(x)=\sum_i a_i \sigma(w_i^\top x)) 的ReLU正线性组合，其Hermite张量的低阶部分隐含了权重向量 (w_i) 的方向信息：张量的分解或特征结构可揭示各权重向量的近似值。本文利用隐式张量计算技术，在不显式构造高维张量的前提下，通过随机采样和矩估计高效地访问这些张量信息，从而构建低阶过滤过程来放大不同权重向量之间的分离度。

算法细节与理论保证

算法通过低阶过滤过程增强权重向量的分离性，然后使用梯度下降类更新微调估计。剪枝步骤确保算法仅保留接近隐藏权重向量的候选，从而控制计算复杂度。理论分析表明，算法以高概率输出$\epsilon$-接近的假设，样本复杂度和时间复杂度均为$\mathrm{poly}(d, k, 1/\epsilon)$。

与先前工作的对比

先前工作通常需要$\mathrm{poly}(d, k, 1/\epsilon)$之外的复杂度，或假设权重矩阵良态（如条件数有界）。新算法消除了这些限制，适用于更广泛的ReLU组合学习场景。

剪枝策略在本算法中承担控制复杂度的关键角色。由于提升过程可能产生大量候选向量，若不加筛选，候选集规模会随迭代指数增长。剪枝步骤在每一轮后评估每个候选与当前目标函数残差的相关性，仅保留那些在目标精度上可能接近某个隐藏权重向量的候选，从而将候选集大小控制在 (\mathrm{poly}(d,k,1/\epsilon)) 以内。这一策略与列表可解码框架相配合：只要真实权重向量始终留在候选列表中，算法最终就能以高概率输出 (\epsilon)-接近的假设。

结论

该研究为PAC学习ReLU正线性组合提供了首个全多项式时间算法，推动了神经网络理论理解。其技术贡献包括基于Hermite张量的过滤过程和剪枝策略，为相关学习问题提供了新思路。未来工作可能探索更一般激活函数和分布下的扩展。