Learning Positive Linear Combinations of ReLUs in Fully Polynomial Time

1 Introduction

• The problem remained open despite prior algorithms with super-polynomial dependence on at least one of d, k, or 1/ϵ, and solving it is a step toward understanding learnability of more general networks.The paper also notes that its techniques may be useful for other latent variable models.Source: §1 · p. 3

1.1 Problem Formulation and Main Result

• The learner uses poly(d, k, 1/ϵ) samples and time to achieve the stated PAC guarantee for positive combinations of at most k ReLUs under Gaussian inputs.Its hypothesis is improper but simple: a linear function plus a linear combination of at most k absolute-value functions, equivalently at most 2k ReLUs.Source: §1 · p. 3, §1.1 · p. 4

1.2 Technical Overview

• The algorithm maintains at most k candidate directions, contracts their angular error by a constant factor each round, then estimates coefficients through convex linear regression.It need only recover each relevant hidden vector up to sign, since subtracting the linear part leaves a sum of absolute values; components below about √ϵ/k can be discarded at additive ϵ loss.Source: §1.2 · p. 5

1.2.1 Coarse Direction Recovery

• Coarse Direction Recovery outputs a polynomial-size list containing a constant-correlation candidate for every ϵ0-heavy hidden vector, using Hermite-tensor contractions whose high-degree correlations amplify alignment differences.The method groups directions close up to sign rather than isolating a single component; complex Gaussian probes help keep estimation error growth small enough for a polynomial implementation.Source: §1.2.1 · pp. 5–7

1.2.2 Boosting Coarse Direction Recovery

• Boosting refines coarse candidates by using rejection sampling to form a new Gaussian sum whose hidden directions approximate the targets’ components orthogonal to a candidate, then applying CDR to obtain update directions.A direction with constant alignment to the orthogonal component contracts the angle to the target by a constant factor, enabling iterative refinement and pruning.Source: §1.2.2 · p. 7
• Repeated projected updates generate candidate vectors that contract the distance to each hidden weight by a constant factor.For each candidate, Refine generates a polynomial-size list of update directions and applies updates in both directions, repeating the procedure three times. The resulting list contains an approximation for every hidden weight, but may also contain many irrelevant vectors.Source: §1.2.2 · p. 8
• A Hermite-coefficient test retains candidates within the contracted target angle and rejects candidates farther than a slightly larger threshold.For sufficiently large even degree p, the test distinguishes candidates with angle at most cR_{t+1} from those beyond (1 + τ)cR_{t+1}.Source: §1.2.2 · p. 8
• Geometric pruning reduces the surviving list to at most k vectors while preserving an approximation within R_{t+1} for every hidden weight.Candidates close to the same target are close to one another, so the algorithm adds a candidate only when it is sufficiently far from those already selected; one selected vector may cover multiple targets.Source: §1.2.2 · p. 8

1.3 Related Work

• Prior work on positive ReLU combinations uses Chow parameters, higher-degree moments, or implicit moment estimation to construct predictors [DKKZ20] [DK20] [DK25].[DKKZ20] finds a low-dimensional prediction subspace using degree-2 Chow parameters; [DK20] uses higher-degree moments and a cover of a polynomial near-zero set; [DK25] implicitly estimates high-order tensors to approximate the target’s Hermite expansion, extending a technique of Li and Liu.Source: §1.3 · p. 10
• Algorithms for general ReLU coefficients handle broader function classes but have complexity exponential in hidden-unit count, while other related work assumes nondegeneracy or has exponential dependence on relevant parameters.For general coefficients, [CDG+23], [CN24], and [DK24] give runtimes polynomial in d and 1/ϵ for fixed k, (dk/ϵ)^{O(k^2)}, and (dk/ϵ)^{O(k)}, respectively. Multi-index and deeper-network learning also have exponential dependence on network size or other relevant parameters [DIKZ25] [DIKR25]. Parameter-recovery methods for positive ReLU combinations may depend on rank or condition number [GLM18]; in contrast, this work targets prediction error without configuration assumptions.Source: §1.3 · p. 10
• CSQ lower bounds for general coefficients rule out an immediate extension of this algorithm, and fully polynomial-time learning without biases remains open.The cited lower bounds are due to [DKKZ20] [GGJ+20]; [CGKM22] gives SQ and cryptographic hardness for two-hidden-layer networks, and [LZZ24] gives cryptographic hardness for one-hidden-layer networks with biases and small independent Gaussian label noise. The paper notes that its algorithm can be implemented in the CSQ model. With query access, gives a polynomial-complexity learner under bounds on weights and biases.Source: §1.3 · p. 10

1.4 Concurrent Work and AI Use

• The authors report that GPT models helped improve presentation, generate Figures 1 and 2, audit proofs, and simplify statements; they also note a very recent paper claiming essentially the same result [Zhe26].They say the concurrent work uses some of the same core techniques and terminology but lacks most proof details; they report rushing their posting while including complete technical details.Source: §1.4 · p. 11

1.5 Paper Organization

• Section 2 gives notation and background, while Sections 3–5 describe and analyze the algorithm.Source: §1.5 · p. 11

• The notation sets [n], vector and matrix conventions, norms, angles, projections, and asymptotic shorthand.It also defines complex-number notation and vector normalization.Source: §2 · p. 11
• Wedin’s theorem bounds the leading-eigenvector angle using the matrix perturbation norm and the leading eigengap.The stated condition requires the eigengap to exceed the perturbation norm.Source: §2 · p. 11
• Complex tensors are treated as multilinear arrays with inner products, adjoints, contractions, and symmetrization; covariance is defined after flattening.The section distinguishes covariance from the uncentered second moment.Source: §2 · pp. 11–12
• Under the standard Gaussian, the section defines the L2 inner product and norm, and normalized one-dimensional Hermite polynomials form an orthonormal basis.It also states Gaussian hypercontractivity and defines Hermite coefficients by inner products with the basis.Source: §2 · p. 12
• Hermite preliminaries include degree and smoothing identities, directional expansions, and the ReLU Hermite expansion, whose squared coefficients scale as Θ(p^-5/2).The ReLU expansion can also be formally differentiated.Source: §2 · pp. 12–13
• Normalized Hermite tensors are defined through partitions into singleton and pair-index sets, with an order-2 identity relating a Gaussian expectation to f''(v·z)vv⊤.Source: §2 · p. 13

3 Optimization via Coarse Direction Recovery, Refinement, and Pruning

• With a CDR procedure satisfying Assumption 1, the learner uses polynomial samples and time and achieves expected squared loss at most ε with probability at least 2/3.The algorithm repeatedly calls CDR with parameters polynomial in ε/k; its runtime is polynomial in d, its sample count, and T_CDR.Source: §3 · p. 14

3.1 Learning λ-Heavy Hidden Weight Vectors

• The λ-heavy-vector recovery pipeline refines candidate estimates, tests for vectors too far from every relevant hidden weight, and prunes the remaining list to at most k candidates.The subsection identifies this recovery as the technical core and states that CoverAndPrune provides the complete algorithm.Source: §3.1 · p. 14

3.1.2 Closeness Tester

• A closeness tester identifies candidates farther than a specified threshold from every λ-heavy hidden weight vector, before final pruning limits the retained list.Refine first produces a large list containing a sufficiently close vector for each λ-heavy hidden vector.Source: §3.1 · p. 14, §3.1.2 · p. 18

3.1.1 Boosting Hidden Vector Estimates

• If β_i ≥ ε_0 and θ±(v,w_i) ≤ r, Refine returns a list containing a vector v_i with probability at least 1 − O(L_CDR^3 δ_CDR); its procedure uses three update steps.The update procedure creates a set containing vectors closer than before to some hidden vectors by a multiplicative factor of 3/5.Source: §3.1.1 · pp. 16–17

3.1.2 Closeness Tester

• The tester separates vectors within r of an epsilon0-heavy weight from vectors farther than (1 + τ)r, using degree p = 2⌈(1/(τr^2)) log(k/epsilon0)⌉.For r ≥ epsilon0/(5k), it uses poly(k, 1/epsilon0)(1/δTest) samples and O(dN) time with probability at least 1 − δTest.Source: §3.1.2 · p. 19

3.1.3 Covering and Pruning

• Refine and Test reduce the covering radius geometrically, while Prune keeps candidates separated and limits each iteration’s list to at most k vectors.Prune removes near-duplicate candidates without substantially altering coverage; the maintained radius satisfies Rt+1 = ρRt for ρ < 1.Source: §3.1.3 · pp. 21, 23
• With probability at least 1 − δ, CoverAndPrune returns a list covering every epsilon0-heavy weight within angle epsilon0, in poly(d, N, TCDR) time.The procedure draws i.i.d. samples from D; its proposition assumes access to a CDR algorithm satisfying Assumption 1.Source: §3.1.3 · pp. 23–24
• CoverAndPrune succeeds with probability at least 1 − δ and has runtime poly(d, k/ϵ0, 1/δ, L_CDR, N_CDR, T_CDR).Its Refine and Test subroutines are called across T rounds; the runtime is also summarized as poly(d, N, T_CDR).Source: §3.1.3 · p. 24
• With probability at least 1 − δ, CoverAndPrune returns at most k candidates, including one within angle ϵ0 of each hidden weight whose coefficient is at least ϵ0.Weights with smaller coefficients can be ignored, increasing the L2 squared error by at most ϵ.Source: §3.1.3 · p. 24, §3.2 · p. 25

3.2 Proof of Theorem 3.1

• Fitting coefficients by minimizing over α is a convex program, and the empirical minimizer uses d poly(k/ϵ) samples to satisfy the stated error bound.The proof estimates g = E[yx] and constructs an empirical distribution for the quadratic terms used in the fit.Source: §3.2 · p. 25
• The learner uses eO(d poly(k/ϵ) + poly(k/ϵ)L_CDR^3(L_CDR^3 + N_CDR)) samples and runs in poly(d, N, T_CDR) time.The proof sets ϵ0 = √ϵ/(4k).Source: §3.2 · p. 25

4 Efficient Coarse Direction Recovery

• For each weight with β_i ≥ λ, polynomial-time CDR returns a list containing a unit vector with absolute correlation at least 0.99, with probability at least 1 − δ.The algorithm uses poly(d, k, 1/λ, 1/δ) samples and runs in poly(d, N) time; the list size is poly(k/λ) log(1/δ).Source: §4 · p. 26

4.1 Low-Degree Filtering: Revealing Hidden Directions

• A low-degree Hermite filter makes the target matrix approximately rank one, so its top eigenvector aligns with a hidden direction when the probing vector separates that direction.Implicit tensor computation estimates the contracted matrix directly with polynomially many samples, avoiding full estimation of the Hermite tensor; a relative spectral-norm approximation preserves alignment of at least 0.99.Source: §4.1 · p. 27

4.2 Warm-up: Quasi-Polynomial Time CDR Algorithm

• When the weight span has dimension m ≲ log(k), random directions in that span suffice to obtain 0.99 correlation with every hidden weight using poly(k, 1/ε) log(1/δ) vectors.For each fixed unit vector, a uniform random unit vector has correlation at least 0.99 with probability 2^-O(m).Source: §4.2 · p. 29
• The warm-up spectral CDR achieves the same 0.99 correlation guarantee for λ-heavy weights, but requires d^2 k^O(log(k/λ)) log(1/δ) samples.It samples probing vectors uniformly from the sphere in the weight span and runs in time polynomial in d and the sample count.Source: §4.2 · p. 29
• The quasi-polynomial warm-up uses d^2 k^O(log(k/λ)) log(1/δ) samples and returns poly(k) log(1/δ) candidates, including a vector with 0.99 correlation for every β_i ≥ λ weight with probability at least 1−δ.Its running time is poly(d, N).Source: §4.2 · p. 34

4.3 Polynomial Time CDR via Implicit Tensor Computation

• Polynomial-time CDR uses poly(d, k, 1/λ, 1/δ) samples and poly(d, N) time, returning poly(k/λ) log(1/δ) candidates with 0.99 correlation for every β_i ≥ λ weight with probability at least 1−δ.The output is a list of unit vectors.Source: §4.3 · p. 35

4.3.1 Determining the Probability of the Probing Event

• The complex-Gaussian probing event that separates a target weight from sufficiently uncorrelated weights occurs with probability at least poly(λ/k).The filter degree is p = ⌈log(k/λ)/log(1+ξ)⌉.Source: §4.3.1 · pp. 35–36

4.3.2 Estimating the Target Matrix Using Implicit Tensor Computation

• Implicit tensor computation estimates each target matrix within √ξλ in operator norm with probability at least 1−δ/2, reducing estimation dimension from d^2p to k^2 + (dk)^2.The reduction uses a compressor constructed recursively from samples.Source: §4.3.2 · pp. 36–37
• The method represents Hermite moment and filter tensors as size-O(t) and size-O(p) sequential tensor computations, enabling recursive compression of their contractions.The compressor maps order-p tensors into the subspace spanned by the hidden weight tensors raised to the pth tensor power.Source: §4.3.2 · p. 38
• With p = O(log(k/λ)), TensorCompressor uses poly(d, k/λ, 1/τ) samples and polynomial time to approximate the span of λ-heavy hidden weight tensors.The resulting pseudo-projection maps a tensor O(λ)-close to that span with probability at least 1 − τ.Source: §4.3.2 · p. 41
• Applying the recursive pseudo-projection to the filter and moment tensors, including their tensor contractions, takes poly(d, k, p) time.The procedures use a recursive pseudo-projection together with the sequential tensor computation representation.Source: §4.3.2 · pp. 41–42
• The complex Gaussian filter has second- and fourth-moment bounds of 2^O(p), while a real Gaussian filter would have much larger covariance.These bounds support concentration when comparing the empirical matrix estimate with the target matrix.Source: §4.3.2 · p. 42
• With probability at least 1 − δ/2, implicit tensor computation estimates every probed M_2p+2(u) within √(ξλ) in spectral norm.Source: §4.3.2 · pp. 44, 48

4.4 Proof of the Main Result of the Section: Polynomial Complexity

• With probability at least 1 − δ, CDR uses poly(d, k, 1/λ, 1/δ) samples and poly(d, N) time to return poly(k/λ) log(1/δ) unit vectors, including one with |r_i · w_i| ≥ 0.99 for each β_i ≥ λ.Source: §4.4 · p. 49
• The separation and correlation events occur with probability at least poly(λ/k) per random complex Gaussian probe, and the algorithm uses poly(k/λ) log(k/δ) probes.Source: §4.4 · p. 49

5 Putting Everything Together: Proof of Theorem 1.3

• With probability at least 2/3, the learner achieves squared L2 error at most ϵ using poly(d, k, 1/ϵ) samples and time.The guarantee applies to targets with Gaussian inputs and parameters λ = poly(ϵ/k) and δ = poly(ϵ/k).Source: §5 · p. 49
• The theorem follows by applying the learning guarantee for a CDR procedure satisfying its required assumption, then substituting the polynomial CDR bounds.The proof identifies the CDR sample complexity, runtime, and output list length as the quantities used in the composition.Source: §5 · p. 49
• The CDR procedure has polynomial sample complexity and runtime in d, k, 1/λ, and 1/δ, with list size at most poly(k/λ) log(1/δ).The proof uses this procedure with λ and δ polynomial in ϵ/k.Source: §5 · pp. 49–50