Daily AI Paper

Learning a positive linear combination of ReLUs sounds, at first glance, like a fairly specialized problem. But this paper is really about one of the most basic open questions in provable machine learning: can we efficiently learn even a simple one-hidden-layer neural network, with no special assumptions on the hidden weights, when the inputs are Gaussian? That matters because if we can understand the computational limits and possibilities here, we get a much clearer picture of what kinds of neural networks are actually learnable in polynomial time, and which ones seem to require more structure. The concept class here is a sum of up to k ReLU units, each with a nonnegative coefficient. So the target function looks like a weighted sum of activations of the form max of zero and a linear projection. The learner sees labeled examples where the inputs come from a standard Gaussian distribution, and the goal is to produce a hypothesis that is close in L2 loss. This is a natural and well-studied setting in theory, because Gaussian inputs often let us exploit symmetry and moment-based structure, while still being rich enough to capture real geometric difficulty. What makes the problem hard is that, although information-theoretically it is learnable with polynomially many samples, the computational side has been stubborn. Previous algorithms either had running time that was super-polynomial in k or in 1 over epsilon, or they needed strong conditions like well-conditioned hidden weights. So the key question is whether arbitrary positive sums of ReLUs can be learned in fully polynomial time in all the relevant parameters: dimension, number of units, and accuracy. This paper answers yes. The main result is an algorithm that uses polynomially many samples and polynomial time in d, k, and 1 over epsilon, and returns a hypothesis that is close to the target with high probability. The hypothesis is not required to be another sum of positive ReLUs. Instead, it has a very simple form: a linear function plus a sum of absolute-value terms. Since absolute value can be written as a sum of two ReLUs, this is still a small neural network, but it is a more convenient representation for the analysis and for evaluation. That simplicity is one of the nice practical features of the result. To understand the method, it helps to recall a basic identity for ReLUs. A ReLU can be decomposed into a linear part plus an absolute-value part. So if you take the expectation of the label times the input vector, you recover a linear combination of the hidden directions. In other words, the first moment reveals a linear component that can be peeled off, leaving a residual function that behaves like a sum of absolute values. That is important because absolute value is insensitive to sign: a hidden direction and its negative produce the same absolute-value term. So the algorithm only needs to recover each hidden vector up to sign, not orientation. The paper’s strategy is to recover the hidden directions gradually, in rounds. It does not try to identify every hidden vector exactly from the start. Instead, it maintains a small list of candidate directions, with the guarantee that for every “heavy” hidden unit, meaning one whose coefficient is not too small, there is at least one candidate in the list that is reasonably close to it. Then, round by round, the candidates are improved until they are accurate enough to support final coefficient estimation. This is a classic boosting-style idea, but applied to a weak learner for latent directions. The challenge is to design that weak learner in a way that is both efficient and robust enough to work in the fully general setting. The paper’s weak learner has two main ingredients. The first ingredient is a coarse direction recovery procedure. Given samples from the target function, it outputs a polynomial-size list of candidate vectors. The guarantee is that for every sufficiently important hidden vector, at least one candidate in the list has large correlation with it. The text describes this as getting a vector whose dot product with the hidden vector is at least 0.99 in absolute value, which means the angle is already quite small. This is not full recovery, but it is enough to seed the refinement process. The second ingredient is a way to refine those coarse guesses using low-degree information extracted from Hermite tensors of the target function. Hermite polynomials are natural for Gaussian analysis because they form an orthogonal basis under the Gaussian measure, so moments expressed in that basis can isolate structured components of the target. The paper uses implicit tensor computation techniques to build a filtering procedure from these Hermite tensors. The intuition is that the correct hidden directions create stronger signatures in these low-degree statistics than incorrect directions do, so the method can amplify the separation between clusters of candidate vectors. In effect, it turns a rough geometric guess into a more precise one. Once the algorithm has a candidate direction that is already somewhat close to a hidden vector, it can make gradient-descent-like updates on the unit sphere. The paper argues that the same filtering machinery used for coarse recovery can also support this local improvement step. So the algorithm is not just a one-shot estimator; it is a hybrid of moment-based global search and iterative local refinement. A crucial practical issue is pruning. Because the algorithm works with lists of candidates, there is a risk that the list grows with many irrelevant vectors, or that vectors that are no longer useful continue to clutter the process. The pruning step ensures that only vectors that are actually relevant at the target accuracy are kept. This matters both for efficiency and for maintaining the invariant that each heavy hidden unit remains represented by a nearby candidate. The high-level invariant is simple: at every round, there is a set of at most k vectors, and each heavy hidden weight vector has at least one nearby representative in that set. The radius of closeness shrinks by a constant factor each round. After O of log of k over epsilon rounds, the approximation error is small enough that the remaining task is just to estimate the coefficients of the absolute-value representation. That final estimation step is much easier. Once the directions are known, the problem reduces to linear regression over a feature map consisting of the candidate absolute-value terms and the linear term. Since the number of features is only linear in k, this can be solved efficiently with standard convex optimization methods. So the hard part of the learning problem is really recovering the hidden geometry; once that is done, fitting the coefficients is routine. On the experimental side, this is a theory paper, so the “experiments” are formal sample and time guarantees rather than empirical benchmarks. The main theorem states that the algorithm uses poly d, k, and 1 over epsilon samples and time, and succeeds with constant probability, which can be boosted in the usual way. The paper also notes that the method extends to additive label noise, with only polynomial overhead in the noise level. That is a useful robustness statement, because it shows the approach is not limited to perfectly realizable data. Another important point is normalization. The authors explain that they can rescale the target without loss of generality, even if the original coefficients and hidden vector norms are not bounded in advance. They estimate the overall scale from a small number of samples, normalize the labels, run the learner, and then rescale the output. So the algorithm does not require prior knowledge of the target magnitude. What do the results actually show? First, they settle a long-standing open problem for this class under Gaussian inputs: arbitrary positive linear combinations of k ReLUs can be learned in fully polynomial time. Second, they do so with a hypothesis that remains simple and interpretable. Third, the method avoids the super-polynomial dependence that plagued earlier approaches, and it does so without imposing strong conditioning assumptions on the hidden weight matrix. That is the real conceptual advance. The limitations are also worth keeping in mind. The result is for Gaussian marginals, so it does not immediately solve the problem under arbitrary input distributions. The concept class is still restricted to positive linear combinations of ReLUs, not arbitrary signed combinations or deeper networks. And while the hypothesis is compact, the method itself is technically sophisticated, relying on Hermite analysis, tensor computation, and a carefully engineered boosting-and-pruning framework. So this is not yet a plug-and-play practical learner for general neural networks. Still, from a theoretical perspective, this is a major step. It shows that a fairly natural neural network class, previously out of reach in fully polynomial time, is in fact tractable under a standard and mathematically clean distributional assumption. More broadly, the techniques here may be useful anywhere hidden directions need to be recovered from noisy low-degree structure. That makes this paper interesting not only as a result about ReLUs, but as a template for learning latent-variable models more generally.