CS Paper Radar

Polynomial Learning of Positive ReLU Networks under Gaussian Inputs

Zhijie Zheng

cs.LG ·submitted 2026-10-18 08:46 UTC · v2

Abstract

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.

Comment
32 pages; expanded to include agnostic learning guarantees

Closest papers

Nearest neighbours by meaning across the whole index.

Learning Positive Linear Combinations of ReLUs in Fully Polynomial Time

cs.DS cs.LG ·2026-10-23 ·Ilias Diakonikolas, Jelena Diakonikolas, Puqian Wang, Nikos Zarifis
published similarity 0.72
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.

0.19

A Distribution-Free Separation Between Learned and Fixed Features

cs.LG stat.ML ·2026-10-18 ·Daniel Barzilai
hot direction similarity 0.68
Abstract

The success of neural networks is largely attributed to their ability to learn useful representations from training data. However, known results that prove a computational advantage of learned features over fixed ones are restricted to specific input distributions. We settle the COLT open question of Feldman, Kamath, and Srebro (2026) by showing that this advantage can persist in the distribution-free setting. We construct a family of hypothesis classes that can be efficiently learned by a natural gradient-based algorithm on a two-layer ReLU network, but cannot be represented by linear predictors over any fixed feature map with polynomial dimension (and runtime). Specifically, for any sufficiently small error and any sufficiently large runtime budget R (depending on the error), there exists a hypothesis class that the neural network learns under any input distribution to the desired expected classification error in time at most R, while the dimension complexity (governing the dimension needed by linear predictors) is superpolynomial in R.

0.33

Para-Gaussian Approximations of Random Deep Neural Networks

cs.LG math.PR ·2026-10-27 ·Mihai Nica, Janosch Ortmann
similarity 0.67
Abstract · 34 pages, 9 figures

It is known that randomly initialized neural networks have Gaussian behaviour in the $n\to \infty$ limit. Unfortunately, this approximation can be poor for finite $n$ and gets worse as one goes deeper into the network. In this work, we develop a more accurate approximation that is \emph{slightly} non-Gaussian, which we call the para-Gaussian distribution and is constructed from the Hermite polynomials. We show how this para-Gaussian approximation can lead to a practical recursive method to approximate the deeper layers of the network. Finally, we apply this theory to linear neural networks (where things can be solved exactly) and to ReLU neural networks (where things can be approximated).

0.15

Optimal approximation of smooth functions by ReLU neural networks

cs.LG stat.MLmath.NA ·2026-10-15 ·Thomas Nagler
similarity 0.65
Abstract

We study uniform approximation of the Hölder ball $\mathcal H_1^s([0,1]^D)$ by fully connected ReLU networks. Except in the one-dimensional Lipschitz case, existing constructions remain separated from the information-theoretic efficiency limit. This article closes the gap for every $s>0$ and $D\ge1$: networks with width $O(N)$, depth $O(L)$, and parameter magnitude $O(1)$ attain uniform approximation error of order $(N^2L^2\log N)^{-s/D}$. No relation between width and depth is required. The construction uses new encoding and decoding mechanisms that exploit higher-order finite-difference bounds for local Taylor coefficients of the target function. As a statistical consequence, empirical risk minimizers over the corresponding clipped network classes attain the minimax regression rate $n^{-2s/(2s+D)}$ without additional logarithmic factors. The paper also gives a detailed exposition of the key approximation techniques, covering both established and new mechanisms.

0.19

Training-Loss Guarantees for Muon with Finite-Step Newton--Schulz Orthogonalization

cs.LG cs.AImath.OC ·2026-10-02 ·Amartya Roy, Souvik Chakraborty
theory similarity 0.62
Abstract · 22 pages, 5 figures

Existing convergence analyses of Muon either assume exact orthogonalization or analyze classical Newton--Schulz polynomials, and guarantee only stationarity, so it is unresolved what Muon's five tuned Newton--Schulz steps preserve and whether that suffices to reach a prescribed neural-network training loss. We establish a finite-time training guarantee that accounts for both momentum accumulation before orthogonalization and the tuned finite-step update. For full-batch training of a sufficiently wide two-layer ReLU network with fixed random output weights and a positive-definite limiting neural tangent kernel, we prove that Muon reaches any target empirical squared loss $\varepsilon>0$ with high probability over initialization. For every momentum parameter $μ\in[0,1)$, a target-dependent constant learning rate proportional to $(1-μ)\sqrt{\varepsilon}$ yields a hitting-time bound of $O((1-μ)^{-1}\varepsilon^{-1/2})$, with other problem parameters fixed. The sufficient width is independent of both target accuracy and momentum. The analysis shows that the tuned Newton--Schulz map preserves alignment with the momentum buffer while bounding the update's spectral norm. Control of gradient variation near initialization transfers this alignment to the current gradient, ensuring descent until the target is reached without requiring exact orthogonalization. Numerical experiments support these mechanisms at widths below the sufficient theoretical threshold: gradient-update alignment remains above the analytical reference, and all 30 runs across six widths and five student initializations on a fixed teacher-student dataset reach the target loss while maintaining kernel positivity.

0.45

Width-Independent Compressibility of Deep Neural Networks

cs.LG cond-mat.dis-nncs.IT ·2026-08-22 ·Hong-Yi Wang, Mingze Wang, Liu Ziyin
theory similarity 0.62
Abstract · 11 pages main text, 28 pages total, 4 figures

It has long been known that well-trained neural networks can be compressed very strongly without affecting their performance, an important phenomenon that remains poorly understood. We prove a uniform compressibility theorem for deep multilayer perceptrons with analytic activations. For a deep, wide fixed teacher network, there exists a narrow (same depth) network that approximately represents the same function as the original. The reachable compressed width is strikingly independent of the original width, but is $O((\log(1/\varepsilon))^{d_{in}})$, where $\varepsilon$ is the error budget and $d_{in}$ is the effective input dimension. Our construction involves a novel derivative-matching technique which is aware of the low-dimensional input, and a layer-wise reweighting that preserves the input-output mapping.

0.36

Flat Loss, Evolving Features: Grokking in Modular Addition

cs.LG stat.ML ·2026-10-15 ·Akash Kumar, Karthik Sankaranarayanan
theorycode/datahot direction similarity 0.61
Abstract · 97 pages, 17 figures. Code: https://github.com/akashkumar-d/flat-loss-evolving-features

Can a network keep learning while its training cross-entropy stays nearly flat at a positive level? We show that it can. On modular addition, a standard testbed for grokking, ReLU networks trained with supported-Polar hidden updates, normalized output-layer updates and weight decay can keep 100% training accuracy while their hidden features change and held-out accuracy rises from zero to above 90%, at relatively flat training cross-entropy. Correct classification need not minimize cross-entropy, which still depends on prediction confidence. We prove this coexistence for one-hidden-layer networks in two finite-window theorems from constructed initializations: one gives a constant gain in the Fourier fraction of the hidden features, and the other holds at arbitrarily low positive loss, where a readout refitted on the training data generalizes before the network. Experiments from random initialization show the same coexistence on a window fixed in advance, and in deeper networks held-out accuracy also rises over post-hoc windows with a net increase in training cross-entropy. With a last-layer rate set per training fraction and head decay scaled with the prime, deeper networks at p=47 and 61 meet a criterion on post-hoc windows, fixed in advance, in nearly all fresh runs. A one-block transformer trained with the same updates and a slowly decaying output gain keeps every training pair correct at every logged checkpoint while its training cross-entropy rises and its held-out accuracy approaches one; with two blocks this holds through the held-out rise, after which training pairs begin to flip. A plateau in training loss need not be a plateau in learning. Code: https://github.com/akashkumar-d/flat-loss-evolving-features.

0.46

Lifting Finite-Sample Gaussian Approximation of Wide Neural Networks to Functional Convergence

cs.AI stat.MLcs.LG ·2026-10-13 ·Luis Wiederhold, Nil Ayday, Debarghya Ghoshdastidar
similarity 0.61
Abstract · 19 pages, 1 table, 1 figure, preprint

Randomly initialised neural networks of width $m$ converge to Gaussian processes as $m \to \infty$, with two types of quantitative bounds characterising this convergence. Finite-sample bounds compare the network with its Gaussian limit at a fixed finite sample set, on an arbitrary domain, in the quadratic Wasserstein distance $\mathcal W_2$, achieving a convergence rate of $m^{-1/2}$ with explicit constants. However, these constants grow with the number of samples, so the bound becomes uninformative as the sample set is refined. Functional bounds remove that dependence by comparing the two as random functions, at the price of spherical input, metrics weaker than $\mathcal W_2$, or slower rates. In this paper, we therefore lift a finite-sample bound to a functional one. The lifting refines the sample set until it is dense in the domain, so the bound must first be made independent of the number of samples. We achieve this by measuring the error per sample, which makes the constant uniform. For a polynomial activation and any compact input set, this gives a rate of $m^{-1/2}$ in the supremum norm, with an explicit constant.

0.27