Learning Positive Linear Combinations of ReLUs in Fully Polynomial Time
Abstract
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.
The following analysis is generated by AI and may contain errors. It is separate from the authors’ abstract and is not peer review.
Research summary
The paper provides the first fully-polynomial time algorithm for PAC learning positive linear combinations of ReLUs under Gaussian inputs, resolving a major open problem in the field. By developing a novel boosting procedure based on implicit tensor computation and list-decodable coarse direction recovery, the authors overcome previous super-polynomial complexity barriers, offering significant theoretical insights into the learnability of neural networks without strong structural assumptions.
Methodology
The paper proposes a novel algorithmic framework for learning positive linear combinations of ReLUs under Gaussian inputs. The core contribution is a "Coarse Direction Recovery" (CDR) subroutine that leverages implicit tensor computation and Hermite tensors to identify hidden weight vectors with constant error in a list-decodable manner. This is followed by a boosting procedure that refines these estimates using gradient descent-like updates on the Euclidean sphere, guided by rejection sampling to maintain the Gaussian structure. The use of complex Gaussian vectors to reduce estimation variance is a clever technical detail. The pruning strategy ensures the candidate list size remains polynomial. The methodology is rigorous, moving from a "weak" learner to a strong one via iterative refinement, which is a significant algorithmic advance over previous methods that relied on super-polynomial time or strong conditioning assumptions.
Results & evaluation
This is a theoretical paper. There are no empirical experiments, benchmarks, or datasets evaluated. The "results" are formal theorems proving polynomial sample and time complexity. Therefore, experimental evaluation is not applicable in the standard sense, but the theoretical guarantees are the primary contribution.
Reproducibility
The paper provides full technical details, including pseudocode (Algorithm 1) and rigorous proofs. The algorithm is described in sufficient detail to be implemented, although the constants and specific parameter choices (like the degree $p$ of Hermite tensors) are derived theoretically. Reproducibility of the theoretical claims is high; reproducibility of an implementation would require careful tuning of the theoretical constants.
Limitations
The algorithm is restricted to positive linear combinations of ReLUs (no negative coefficients) and assumes Gaussian inputs. It does not handle biases or general linear combinations, which remain open problems. The hypothesis is improper (a linear function plus absolute values), though interpretable. The complexity, while polynomial, may have high constants that make it impractical for very large $d$ or $k$ in practice, though this is typical for such theoretical algorithms.
Broader impact
This paper resolves a long-standing open problem in the computational learning theory of neural networks, specifically for the simplest non-trivial architecture (single hidden layer ReLUs). It provides the first fully polynomial-time algorithm for this task, removing the need for strong structural assumptions like well-conditioned weight matrices. The techniques developed (implicit tensor computation, list-decodable weak learning, sphere optimization) are likely to be applicable to other latent variable models and deeper network learning problems. It sets a new benchmark for what is computationally feasible in learning neural networks. The paper provides the first fully-polynomial time algorithm for PAC learning positive linear combinations of ReLUs under Gaussian inputs, resolving a major open problem in the field. By developing a novel boosting procedure based on implicit tensor computation and list-decodable coarse direction recovery, the authors overcome previous super-polynomial complexity barriers, offering significant theoretical insights into the learnability of neural networks without strong structural assumptions.
Author of this paper? Send a correction.