Polynomial-Time Breakthrough in Learning Combinations of ReLUs

Introduction

PAC learning of positive linear combinations of ReLU activation functions is a fundamental problem in machine learning theory. Recently, a new study proposed the first fully polynomial-time algorithm for learning a positive linear combination of $k$ arbitrary ReLUs on $\mathbb{R}^d$ with respect to the Gaussian distribution under $L_2$ loss. The algorithm draws $\mathrm{poly}(d, k, 1/\epsilon)$ samples, runs in time $\mathrm{poly}(d, k, 1/\epsilon)$, and with high probability outputs a hypothesis that is $\epsilon$-close to the target concept. All previous algorithms required superpolynomial time in $k$ or $1/\epsilon$, or relied on strong well-conditioned assumptions.

Technical Core: Weak Learner and Boosting Framework

The core of the algorithm is a novel boosting procedure that recovers the hidden weight vectors to constant error in a list-decodable manner. Specifically, the research team developed a "weak" learning process that uses implicit tensor computation techniques to build a low-degree filtering process based on the Hermite tensor of the target function. This process amplifies the separation between weight vectors (clusters), thereby learning each weight vector to constant error.

Subsequently, the authors argue that the same process can be used to improve the estimates of the hidden weight vectors through gradient-descent-like updates on the Euclidean sphere. A key component of the algorithm is a pruning method that ensures the algorithm only maintains relevant vectors that are approximately close to the hidden weight vectors at the target accuracy.

Breakthrough Significance

This is the first algorithm to achieve fully polynomial time without any strong assumptions. Previous methods either had excessive computational complexity or required the weight matrix to satisfy strong well-conditioned conditions, limiting practical applicability. The new algorithm effectively addresses these limitations through implicit tensor computation and pruning strategies.

List-decodable learning is a relaxed recovery model in statistical learning: instead of requiring the algorithm to output a single hypothesis, it allows the algorithm to output a candidate list of size at most a preset upper bound, as long as the target concept (or its parameters) appears in the list with high probability. This model is particularly suitable for scenarios with substantial noise or label errors in the data—under the standard PAC framework, if the noise proportion exceeds a certain threshold, no algorithm can uniquely recover the target; list-decodable learning allows the algorithm to still output a short list containing the true parameters in polynomial time under "high noise" conditions. This paper leverages this framework to transform ReLU combination learning into a list-wise recovery problem for multiple hidden weight vectors.

Hermite tensor is a symmetric tensor formed by the coefficients of the high-degree expansion of a function in the Hermite polynomial basis, commonly used to analyze function learning problems under Gaussian distributions. For a positive linear combination of ReLUs of the form (f(x)=\sum_i a_i \sigma(w_i^\top x)), the low-degree part of its Hermite tensor encodes directional information about the weight vectors (w_i): tensor decomposition or spectral structure can reveal approximate values of each weight vector. This paper uses implicit tensor computation techniques to efficiently access these tensor components through random sampling and moment estimation without explicitly constructing high-dimensional tensors, thereby building a low-degree filtering process to amplify the separation between different weight vectors.

Algorithm Details and Theoretical Guarantees

The algorithm enhances the separation of weight vectors through a low-degree filtering process, then fine-tunes the estimates using gradient-descent-like updates. The pruning step ensures the algorithm only retains candidates close to the hidden weight vectors, thereby controlling computational complexity. Theoretical analysis shows that the algorithm outputs an $\epsilon$-close hypothesis with high probability, and both sample complexity and time complexity are $\mathrm{poly}(d, k, 1/\epsilon)$.

Comparison with Prior Work

Prior work typically required complexity beyond $\mathrm{poly}(d, k, 1/\epsilon)$, or assumed the weight matrix is well-conditioned (e.g., bounded condition number). The new algorithm eliminates these restrictions and is applicable to a broader range of ReLU combination learning scenarios.

Pruning strategy plays a key role in controlling complexity in this algorithm. Since the boosting process may generate a large number of candidate vectors, without screening, the candidate set size would grow exponentially with iterations. The pruning step evaluates the correlation of each candidate with the residual of the current target function after each round, and only retains candidates that are potentially close to some hidden weight vector at the target accuracy, thereby keeping the candidate set size within (\mathrm{poly}(d,k,1/\epsilon)). This strategy works in concert with the list-decodable framework: as long as the true weight vectors remain in the candidate list, the algorithm can ultimately output an $\epsilon$-close hypothesis with high probability.

Conclusion

This research provides the first fully polynomial-time algorithm for PAC learning positive linear combinations of ReLUs, advancing theoretical understanding of neural networks. Its technical contributions include a filtering process based on Hermite tensors and a pruning strategy, offering new ideas for related learning problems. Future work may explore extensions to more general activation functions and distributions.

One-line Summary

New research proposes the first fully polynomial-time algorithm for PAC learning positive linear combinations of ReLUs.

Paragraph Summary

This research addresses the fundamental problem of PAC learning positive linear combinations of ReLU activation functions, proposing the first fully polynomial-time algorithm without strong well-conditioned assumptions. The algorithm learns a positive linear combination of k arbitrary ReLUs on R^d under Gaussian distribution with L2 loss, achieving sample and time complexity poly(d,k,1/ε), and outputs an ε-close hypothesis with high probability. The technical core is a novel boosting framework that recovers hidden weight vectors to constant error in a list-decodable manner, combined with a low-degree filtering process based on Hermite tensors to amplify separation between weight vectors, and gradient-descent-like updates on the Euclidean sphere plus pruning to refine estimates and control complexity. Compared to prior work requiring superpolynomial time or relying on strong assumptions such as bounded condition number, this algorithm eliminates these restrictions and is applicable to a broader range of ReLU combination learning scenarios.