该论文给出了首个在 Gaussian 分布、\(L_2\) 损失下,以全多项式时间 PAC 学习 \(k\) 个任意 ReLU 激活函数正线性组合的算法,样本与时间复杂度均为 \(\mathrm{poly}(d,k,1/\epsilon)\),且无需对权重矩阵做强条件假设。
值得关注:ReLU 正线性组合是浅层神经网络的基本形式,其 PAC 可学习性的时间复杂度长期受制于维度 \(d\) 之外的参数 \(k\) 与精度 \(1/\epsilon\)。全多项式时间算法的出现,意味着该模型类在计算上被视…