Learning Positive Linear Combinations of ReLUs in Fully Polynomial Time

Ilias Diakonikolas; Jelena Diakonikolas; Puqian Wang; Nikos Zarifis

cs.DSOct 23, 2026

Learning Positive Linear Combinations of ReLUs in Fully Polynomial Time

Authors: Ilias Diakonikolas, Jelena Diakonikolas, Puqian Wang, Nikos Zarifis

Organizations: UW Madison · CSAIL, MIT

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.

Figures & tables

Panel of Figure 1 — Figure 1: The update procedure of the 5 CoverAndPrune ( ϵ 0 , δ , D ) algorithm. $\times$ denotes the hidden weight, $\bullet$ denotes the candidate vector at step $t$ , $\circ$ denotes the vectors generated after step $t$ . Only the hidden weight vectors with not-too-small coefficients are displayed.

Panel of Figure 2 — Figure 2: List of candidate vectors over the different stages of $\mathsf{CoverAndPrune}$ . Left : after $\mathsf{Refine}$ is called, each $\mathbf{v}\in{\mathcal{V}}_{t}$ produces a large list of new candidate vectors; all produced lists combined contain, for each $\lambda$ -heavy $\mathbf{w}_{i},$ at least one candidate $\mathbf{v}_{i}$ with $\theta_{\pm}(\mathbf{v}_{i},\mathbf{w}_{i})\leq r$ . Center : $\mathsf{Test}$ procedure is used to prune all candidates $\mathbf{v}$ far from all $\mathbf{w}_{i},$ that is, all $\mathbf{v}$ such that $\theta_{\pm}(\mathbf{v},\mathbf{w}_{i})>(1+\tau)r$ , $\forall i\in[k].$ Right : $\mathsf{Prune}$ procedure makes a single iterative pass through the candidate vectors that survive after $\mathsf{Test},$ forming the output list ${\mathcal{V}}_{t+1};$ it starts with an empty list and adds a new iterate if and only if it is at least $r$ -far from all the candidates already in the list.

PAC Learning

Probably approximately correct (PAC) learning studies when finite samples can yield predictors that generalize with bounded error and confidence.

See all 45 papers

Oct 18, 2026

Polynomial Learning of Positive ReLU Networks under Gaussian Inputs

We study positive, bias-free, one-hidden-layer ReLU networks under standard Gaussian inputs. We obtain algorithms with polynomial sample and real-arithmetic complexity, without separation or conditioning assumptions on the hidden directions. When the conditional label mean is a width-

k

network with total output weight at most one, the learner achieves squared prediction error

\varepsilon

with output width at most

k+\min\{k,d\}

and complexity linear in one plus the residual second moment. For arbitrary labels with bounded second moment, we obtain a positive ReLU network of width

O(k\log(2/\varepsilon))

. Its risk is bounded by the irreducible noise variance plus

Ck^3\log^{9/2}(2k/\varepsilon)

times the squared distance of the conditional mean to the target class, plus

\varepsilon

. The proofs combine implicit Hermite moments, orthogonal tensor-train compression, and a direction decoder whose probability of returning a direction far from every atom is bounded linearly in the compression and estimation errors. Exact Gaussian localization refines the resulting direction covers. In the agnostic setting, a cone-constrained convex program with a scale-dependent penalty produces a positive network; in the conditional-mean setting, exact sparsification yields the smaller width. We also establish projective direction recovery and confidence amplification with sample complexity proportional to the logarithm of the reciprocal failure probability.

Zhijie Zheng

Peking University

ReLU Neural Networks

Ask PDF

Jun 9, 2026

Robust Regression of General ReLUs with Queries

We study the task of agnostically learning general (as opposed to homogeneous) ReLUs under the Gaussian distribution with respect to the squared loss. In the passive learning setting, recent work gave a computationally efficient algorithm that uses

poly(d,1/ε)

labeled examples and outputs a hypothesis with error

O(opt)+ε

, where

opt

is the squared loss of the best fit ReLU. Here we focus on the interactive setting, where the learner has some form of query access to the labels of unlabeled examples. Our main result is the first computationally efficient learner that uses

d polylog(1/ε)+\tilde{O}(\min\{1/p, 1/ε\})

black-box label queries, where

p

is the bias of the target function, and achieves error

O(opt)+ε

. We complement our algorithmic result by showing that its query complexity bound is qualitatively near-optimal, even ignoring computational constraints. Finally, we establish that query access is essentially necessary to improve on the label complexity of passive learning. Specifically, for pool-based active learning, any active learner requires

\tildeΩ(d/ε)

labels, unless it draws a super-polynomial number of unlabeled examples.

Ilias Diakonikolas, Daniel M. Kane, Mingchen Ma

University of Wisconsin-Madison · University of California, San Diego

ReLU Neural Networks Active Learning Statistical Learning Theory Supervised Learning Agnostic Learning

Ask PDF

Oct 16, 2026

"Deep lifts": Neural networks can generalize even with the dumbest optimizer

Given a labeled dataset

\{(x_i, y_i)\}_{i = 1}^n

, consider drawing a parameter vector

\hatθ

uniformly at random from those that interpolate the data within a width-

W

depth-

D

ReLU architecture with continuous weights bounded within

[-M, M]

. We study the generalization properties of

\hatθ

in the case where the dataset can, in fact, be explained by a smaller

w

-by-

d

ReLU network. Despite the obliviousness of the selection rule for

\hatθ

, it adaptively generalizes at the rate

\tilde O\left(\frac{wdWD}{n}\right)

, rather than being governed by the VC dimension of the full

W

-by-

D

hypothesis class. The reason is due to a particular inductive bias in ReLU networks: the

w

-by-

d

parameter witnesses an exponential volume of

W

-by-

D

interpolating parameters, which dwarfs the volume of poorly generalizing parameters (conditioned on interpolation). We explicitly construct this set of near-equivalent

W

-by-

D

parameters by a proof technique called deep lifting, and then tie the achievable volume to stability properties of the

w

-by-

d

witness. Examples show that these techniques allow us to convert approximation-theoretic results into generalization guarantees for nonparametric classes. We further show that generalization of uniform-random interpolators can survive label corruptions.

Sunil Madhow, Yu-Xiang Wang

UC San Diego

Neural Network Generalization Generalization Bounds Overparameterized Neural Network ReLU Neural Networks Benign Overfitting

Ask PDF

Abstract

PAC Learning

Explore similar work

Polynomial Learning of Positive ReLU Networks under Gaussian Inputs

Robust Regression of General ReLUs with Queries

"Deep lifts": Neural networks can generalize even with the dumbest optimizer