arXiv 论文：首个在完全多项式时间内学习 ReLU 正线性组合的算法
Learning Positive Linear Combinations of ReLUs in Fully Polynomial Time
一群理论研究者把学 ReLU 线性组合的时间复杂度压到了多项式级别，之前没人做到。做学习理论或理解网络可学性的人可以看看这篇的 boosting 和 Hermite 张量技巧。
一篇 arXiv 论文研究了在高斯分布下、L2 损失下 PAC 学习 k 个任意 ReLU 激活函数正线性组合的问题，并给出首个完全多项式时间算法。算法采样与运行时间均为 poly(d, k, 1/ε)，此前所有算法在 k 或 1/ε 上都需要超多项式时间，或依赖权重矩阵的良态假设。技术核心是对弱学习器的新型 boosting 过程，借助 Hermite 张量的低度滤波做 list-decodable 恢复隐藏权重向量，再在欧氏球面上做梯度下降式更新，并用剪枝保持候选向量集合的规模。
Learning Positive Linear Combinations of ReLUs in Fully Polynomial Time
We study the fundamental problem of PAC learning positive linear combinations of $k$ arbitrary ReLU activations on $\mathbb{R}^d$ with respect to the Gaussian distribution, in $L_2$ loss. We give the first fully-polynomial time algorithm for this learning task. Specifically, our algorithm draws $\mathrm{poly}(d, k, 1/ε)$ samples, runs in $\mathrm{poly}(d, k, 1/ε)$ time, and outputs a hypothesis that is $ε$-close to the target concept with high probability. All prior algorithms for this problem require super-polynomial time in $k$ or $1/ε$, or leverage strong well-conditioned assumptions on the weight matrix. On a technical level, our approach develops a novel boosting procedure of a ``weak'' learner that recovers the hidden weight vectors to constant error, in a list-decodable manner. To develop this ``weak'' learning procedure, we leverage implicit tensor computation techniques to construct a low-degree filtering procedure based on Hermite tensors of the target function. This procedure amplifies separation among (clusters of) weight vectors to learn each of them to constant error. We then argue that the same procedure can be used for improving the estimation of hidden weight vectors, using gradient descent-like updates on the Euclidean sphere. A crucial ingredient of our algorithm is a pruning approach that ensures only relevant vectors that approximate the hidden weight vectors at target accuracy are maintained by the algorithm.