ReLU Neural Networks

ReLU: Rectified Linear Unit

Follow this topic Ask about this topic

Momentum

12 papers in the last four weeks, up 300% on the four weeks before. 0.1% of all new papers.

Jul 13Week of Sep 28

Latest papers 60

All topics

Oct 1, 2026cs.LG

Removing spurious minima for planar features by skip connections

Understanding loss landscapes is central to explaining neural-network training, yet their structure remains only partially understood even in simple models. We study the Gaussian population loss of shallow, bias-free ReLU networks in the teacher--student setting. This provides a simple model for studying essential aspects such as feature learning and overparameterization. For teacher networks with positive output weights and planar features, we show that including a learned linear skip removes all spurious local minima with non-negative student output weights once the student network is at least as wide as the teacher network. In contrast, without the skip, we construct a fixed teacher network with positive output weights and only three hidden neurons in input dimension two whose spurious local minima persist at every student width at least three. Thus, a learned linear skip can remove spurious minima that persist under arbitrary overparameterization. Furthermore, we show that a positive output weight student network always learns the subspace spanned by the teacher features: student features at local minima with non-negative student output weights lie in the span of the teacher features. For ReLU networks in two dimensions, even heavily overparameterized student networks have effective width controlled by the teacher width: every critical point with positive student output weights has at most twice as many distinct student feature directions as teacher neurons. Finally, we transfer the benignity result to empirical minima over parameter balls of any prescribed radius, with the required sampling accuracy depending on that radius.

Jakob Paul Zimmermann, Moritz Grillo, Andrei Balakin +1

Freie Universität Berlin · Technische Universität Berlin

Shallow Neural Networks ReLU Neural Networks Neural Network Optimization Nonconvex Optimization Teacher-Student Learning

Ask PDF

Sep 30, 2026cs.LG

Awakening of the Buddha: Subspace Learning During Population-Loss Plateaus

Population loss can remain nearly constant while a neural network learns a substantially more predictive representation. We establish this separation for two-layer ReLU and leaky-ReLU networks trained on Gaussian inputs by simultaneous fixed-step population gradient descent on all parameters. For structured additive teachers whose links are positive mixtures of Gaussian-damped cubics in

H^1(γ)

, we give explicit conditions under which small IID Gaussian initialization yields a high-probability guarantee: at a checkpoint during a high-loss plateau, minimum alignment between the rank-

r

teacher subspace and the leading

r

-dimensional eigenspace of the predictor's average gradient outer product (AGOP) increases by at least

1/2

, and the minimum refit MSE under unchanged coefficient budgets decreases by more than

0.399

, both relative to initialization. The same trajectory subsequently attains a trained loss below every value in the plateau window. A complementary result treats unequal-weight cubic teachers and small additive Sobolev perturbations using projected-feature refits. For SwiGLU networks with an exactly fitted intercept, we prove leading-AGOP alignment during a loss plateau at fixed width and dimension as Gaussian initialization vanishes, for square-integrable teachers with nonzero Hermite content of degree one, two, or three. A rank-one cubic specialization also gives simultaneous unrestricted-refit gains at a prescribed width. An approximation lower bound further shows that certain interaction targets retain nonzero error when ridge neurons are restricted to shared orthogonal axes within the teacher subspace. Population-moment experiments with ReLU students across 21 teachers and 50 initializations per teacher complement the analysis.

Akash Kumar

Department of Computer Science & Engineering University of California-San Diego

Representation Learning ReLU Neural Networks Neural Network Training Dynamics

Ask PDF

Sep 30, 2026stat.ML

Minimax rates for learning spectral Barron functions by deep ReLU neural networks

We study how well deep neural networks approximate and learn spectral Barron functions. Recent studies have shown that these function classes can be efficiently approximated by shallow neural networks without suffering from the curse of dimensionality. We complement these results by providing new approximation bounds for deep networks with ReLU activation and establishing the minimax rates for learning these function classes. Specifically, we show that

d

-dimensional spectral Barron functions with smoothness index

s>0

can be approximated by deep ReLU neural networks with approximation rate

\widetilde{\mathcal{O}} (S^{-\frac{1}{2}-\frac{s}{d}})

, where

S

denotes the number of nonzero parameters in the network. Using this approximation result, we further show that deep ReLU neural networks can learn spectral Barron functions in a fast rate

n^{-\frac{d+2s}{2d+2s}}

with

n

training samples. Finally, we prove that this convergence rate is minimax optimal up to logarithmic factors.

Songqiu Ma, Yunfei Yang

School of Mathematics (Zhuhai), Sun Yat-sen University, Zhuhai, China. · School of Mathematics (Zhuhai) and Guangdong Province Key Laboratory of Computational Science, Sun Yat-sen University, Zhuhai, China.

ReLU Neural Networks Minimax Estimation Neural Network Approximation Theory Statistical Learning Theory

Ask PDF

Sep 28, 2026cs.LG

Let the Neurons Die: Exploiting ReLU-Induced Model Degradation

Rectified linear unit (ReLU) networks can suffer from dying neurons, where units with persistently negative pre-activations produce zero outputs, blocking gradients through their activations. To exploit this failure mode, we present three training-time availability attacks based on data ordering and poisoning. We begin with the basic dynamic data-ordering attack (DOA), which greedily constructs a training prefix by selecting the next example that minimizes the target layer's post-update weight sum, aiming to push ReLU units toward negative pre-activations without modifying training samples or labels. We then develop two poisoning attacks, IG-DOA and IG-SKA, which use gradient inversion to synthesize class-conditioned samples by matching reference gradients in adverse model states constructed through data ordering or soft knockout, respectively. Soft knockout rearranges weights across adjacent layers to concentrate negative contributions. On a fully connected ReLU network trained on MNIST, ordering 100 of 60,000 training examples reduces test accuracy from 96% to 95% after only five epochs. Adding 200 poisoned samples from a single class reduces test accuracy to approximately 86-88% after five epochs in most evaluated conditions, compared with approximately 96% under clean training. These results demonstrate that ReLU-targeted data ordering and poisoning can impair learning without directly modifying the victim model's parameters.

Kexin Li, Wenjun Qiu, Joshua Abraham +2

University of Toronto, Toronto, Ontario, Canada

ReLU Neural Networks Adversarial Attacks Neural Network Activation Functions Data Poisoning Attacks

Ask PDF

Sep 28, 2026stat.ML

Two-Timescale Fine-tuning Provably Learns New Features for Two-Layer ReLU Networks

Fine-tuning pre-trained models on specialized tasks with scarce data is central to modern deep learning. Despite its empirical success, theoretical understanding of fine-tuning remains limited. We introduce a Gaussian multi-index setting to study fine-tuning from pre-trained weights, where the teacher network has

m+1

features,

m

of which are learned during pre-training and one of which must be learned during fine-tuning. For two-layer ReLU networks, we show that two-timescale training, i.e., updating the outer weights infinitely faster than the hidden ones, learns the new task-specific feature while preserving the pre-trained ones in the model representation. Moreover, only

\mathcal{O}(d)

fine-tuning samples are required for this recovery, independently of the number of pre-trained features. In contrast, with random initialization, the same number of samples is insufficient to recover the target parameters. Our results therefore demonstrate that pre-training can induce an implicit bias with a clear statistical advantage over random initialization, enabling feature learning from scarce fine-tuning data.

Etienne Boursier, Nicolas Flammarion

INRIA, LMO, Universit´e Paris-Saclay, Orsay, France · EPFL, Lausanne, Switzerland

Representation Learning Fine-Tuning ReLU Neural Networks Neural Network Training Dynamics Data-Efficient Learning

Ask PDF

Sep 23, 2026cs.LG

Minimal-Norm Univariate Two-Layer ReLU Classification: Exact Solutions and Global Optimality with Skip Connections

We study minimal-norm interpolation and

\ell_2

-regularized logistic-loss minimization for binary classification by univariate two-layer ReLU networks. We give complete geometric characterizations of the optimal classifiers in function space, resolving how the solutions depend on whether hidden-layer biases are included in the parameter norm. When biases are unpenalized, the minimal-norm interpolators are exactly the continuous piecewise-affine functions that hug every label switch and have kinks of the appropriate convexity. When biases are penalized, the minimizer is unique in function space, has exactly one kink in each intermediate same-label segment, and is therefore a sparsest positive-margin classifier. We further show that adding a free affine skip connection leaves these function-space solutions unchanged but fundamentally improves the parameter-space landscape: every KKT point of the constrained problem becomes globally optimal, whereas suboptimal KKT points can occur without the skip connection. We establish analogous global-optimality and geometric results for sufficiently weak

\ell_2

-regularization of the logistic loss. In the unpenalized-bias case, we identify an additional sparsity-like restriction, implying that most minimal-norm interpolators cannot arise as small-regularization limits of margin-normalized logistic-loss minimizers. Numerical experiments across varying dataset complexity and network width support the predicted landscape and sparsity phenomena.

Karolina Drabik, Ben Lewis, Antoni Puch +4

Department of Mathematics, Informatics and Mechanics, University of Warsaw, Poland · Department of Computer Science, University of Warwick, UK · INRIA & LMO, Université Paris-Saclay, France

ReLU Neural Networks Neural Network Optimization Binary Classification Implicit Regularization

Ask PDF

Sep 22, 2026stat.ML

Generalized Deep Regression for Repeated Measurements

In this paper, we study the estimation of a marginal regression function from independent units with repeated binary, count, or continuous responses using ReLU deep neural networks. In the model, we assume that the dependence is generated by an unobserved random mean function within each unit. We then fit a neural network with a convex generalized regression loss. We show an oracle inequality by separating conditional measurement variation from between-unit variation. In addition, we prove that with

n

units and

m

measurements per unit, ReLU networks can attain an integrated mean squared error of order

n^{-1}+(nm)^{-2β/(2β+d)}

, up to logarithmic factors, over

β

-Hölder classes. We also derive a weighted oracle inequality for unequal cluster sizes and a rate for compositionally smooth functions. For pointwise ensemble inference, we give a projection central limit theorem and prove infinitesimal jackknife consistency under an explicit asymptotic linearity condition. Simulations and real data examples are provided to support our theoretical findings and practical implications.

Kexuan Li

Bristol Myers Squibb

Neural Network Generalization ReLU Neural Networks Nonparametric Regression

Ask PDF

Sep 17, 2026stat.ML

Error bounds in Sobolev norms for approximations with norm constrained ReLU neural networks

Recent studies have shown that smooth functions can be well approximated by ReLU neural networks with path norm constraint on the weights. We extend these results from uniform approximation to approximation in Sobolev norm. Specifically, we analyze how well Sobolev functions in

W^{n,p}

can be approximated by neural networks with width

W

, depth

L

and path norm bounded by

K

, when the approximation error is measured in the

W^{1,p}

-norm. For shallow networks with depth

L=1

, we derive the approximation error bound

\mathcal{O}(\max\{W^{-(n-1)/d}, K^{-(n-1)/(s-n)}\})

, when the smoothness index satisfies

n<s=(d+3)/2

and the input is

d

-dimensional. For deep networks, we remove the restriction on the smoothness by showing that the approximation bound

\mathcal{O}(K^{-(n-1)/(d+d/p+1)})

holds if the width

W

and depth

L

are sufficiently large.

Xianjun Li, Yunfei Yang

School of Statistics and Data Science, Capital University of Economics and Business, Beijing, China. · School of Mathematics (Zhuhai) and Guangdong Province Key Laboratory of Computational Science, Sun Yat-sen University, Zhuhai, China.

Shallow Neural Networks ReLU Neural Networks Neural Network Approximation Theory

Ask PDF

Sep 16, 2026stat.ML

Rank and computation of the pathlifting Jacobian of a DAG ReLU network

This paper provides a self-contained proof of the rank of the pathlifting Jacobian of a DAG ReLU network by performing an induction on the network's number of hidden nodes. In fact, the induction is elementary, and the key recipe is to consider the skeleton matrix of the network, a sparse matrix encoding the network paths, and transform the representation of one of its hidden neurons into an output node. The proof relies on intermediate propositions which link the pathlifting, its Jacobian, the network parameters, and its skeleton matrix, which, on top of permitting to conclude on the rank of the pathlifting Jacobian, also provide a way to compute it without backpropagation and whose computation cost is super efficient in practice compare to usual backpropagation. The paper is provided with a Python module that implements the different propositions of the paper for feed forward networks and is used to experimentally quantifies the computational gain of computing the pathlifting Jacobian with the proposed theory.

Manon Verbockhaven

OCKHAM

Automatic Differentiation ReLU Neural Networks

Ask PDF

Sep 14, 2026stat.ML

Approximating Smooth Functionals with ReLU Networks

We study the uniform approximation of smooth scalar-valued functionals on an infinite-dimensional separable Hilbert space by ReLU neural networks. A key feature in deep learning for functional data is the varying importance of different coordinates/dimensions. Representing the functional input in a basis expansion, we quantify the importance of each coordinate through both the magnitude of its corresponding basis score and the directional sensitivity of the target functional. Our analysis combines coordinate truncation, anisotropic partitioning, local Taylor approximation, and ReLU network realization, while allowing unrestricted interactions among the retained coordinates. We establish a general nonasymptotic upper bound for the uniform approximation error and a complementary pseudo-dimension-based lower bound for the worst-case approximation error. Under generalized exponential coordinate decay

w_ds_d\asymp\exp(-cd^ρ)

, with

ρ>0

, the upper and lower bounds match at the leading order, which is stretched-exponential in the logarithm of the network size budget, and thus yield the nearly optimal approximation rate. This is the first work to characterize neural network approximation error for infinite-dimensional functional inputs explicitly through the joint dimensional decay of coordinate magnitudes and directional sensitivities.

Shuhao Jiao

Department of Biostatistics, City University of Hong Kong, Hong Kong SAR, China.

ReLU Neural Networks Neural Network Approximation Theory

Ask PDF

Sep 14, 2026math.OC

Exact ReLU realization of binary affine refinement iterates via reflection folding and cone switching

We study vector-valued binary affine refinement operators with finitely supported matrix masks and compactly supported continuous piecewise linear input and forcing data. We prove that every finite refinement iterate admits an exact ReLU realization of fixed width and depth linear in the number of iterations. No separation of the forcing profile from the binary cell seams is required. The main mechanism is universal reflection doubling. Pairing each residual profile with its reflection replaces the two binary transition matrices by one fixed block matrix together with a fixed swap involution. The cell-seam identity makes the two branch candidates agree at the tent fold, while their swap-odd component is bounded linearly by the distance to the fold. This permits exact branch selection by a fixed continuous piecewise linear cone switch, without multiplication by a variable selector. The resulting primal recursion requires the residual orbit in reverse order. We obtain exact backward replay from the residual memory controller developed previously for affine refinement, interpreted here through the reflection quotient of circle doubling. The construction propagates the full vectorized profiles rather than decomposing the input and forcing into reference atoms. We also treat stage-dependent forcing from a fixed finite-dimensional family and show that genuine reflection equivariance reduces the doubled cascade to a single parity sector.

Boldsaikhan Bolorkhuu, Tsogtgerel Gantumur

National University of Mongolia · McGill University · Institute of Mathematics and Digital Technology, Mongolian Academy of Sciences

ReLU Neural Networks Neural Network Approximation Theory

Ask PDF

Sep 8, 2026cs.LG

Nearly Tight Rademacher Bounds for Sparsely Activated Neural Networks

An input may activate few hidden units even when different inputs collectively use an entire network. We study the statistical complexity of this input-dependent sparsity in the one-hidden-layer ReLU model of Awasthi et al. (COLT 2024). For width

s

, at most

k

active units per input, and effective weight and bias bounds

W,B

, every size-

m

sample in the class's fixed radius-

R

input domain satisfies

\mathcal{R}(S)\le CWR\min\{k,\sqrt{sk/m}\log^{3/2}(2m)\}+kB/\sqrt m

. A support-preserving cover and a single normalized chaining argument remove the previous explicit dimension factor, up to logarithms. Lower bounds on appropriate i.i.d. marginals match up to those logarithms, showing how changing active units across inputs retains a width dependence. The input domain matters: zero-bias networks sparse on the entire ball have at most

2k

nonzero units and complexity

O(kWR/\sqrt m)

, whereas bias bounds comparable to

WR

restore the worst-case rate on that same domain in only logarithmic dimension. A spherical-cap construction proves the latter claim without assuming sparsity merely on the sampling support. For a specified normalized bounded loss and biases comparable to

WR

, we also obtain agnostic minimax excess-risk bounds of order

\min\{1,\sqrt{s/(km)}\}

up to logarithms.

Xiaoyu Li, Zhizhou Sha, Jiaojiao Jiang +2

University of New South Wales · University of Texas at Austin · University of Sydney

Neural Network Generalization ReLU Neural Networks Activation Sparsity Statistical Learning Theory

Ask PDF

Aug 30, 2026cs.LG

Towards an Expressivity-Normalized Energy-Demand Comparison of ANNs and SNNs

Spiking neural networks (SNNs) are often regarded as energy-efficient alternatives to artificial neural networks (ANNs), yet their advantage depends critically on both network architecture and data properties. We develop an analytical framework to compare fully-connected ReLU ANNs and integrate-and-fire SNNs for time-series data with respect to their theoretical energy efficiency at matched expressive capacity. By relating an inference-energy model to theoretical bounds on representational expressivity, we derive an expressivity-normalized efficiency ratio and explicit thresholds in network width, spike sparsity, and ANN depth scaling. Our analysis characterizes the regimes in which event-driven computation offsets the temporal overhead of SNNs, providing capacity-aware principles for designing energy-efficient temporal networks. It shows that ANNs exceed SNNs in expressivity-normalized efficiency only in specific regimes.

Miriam Kranzlmüller, Pascal Esser, Gitta Kutyniok

Department of Mathematics LMU Munich, Germany · *Munich Center for Machine Learning (MCML) · †Department of Physics and Technology, University of Tromsø, Norway, DLR-German Aerospace Center, Germany

Efficient Neural Network Inference ReLU Neural Networks Energy-Efficient ML Spiking Neural Networks

Ask PDF

Aug 24, 2026cs.LG

Every Layer Counts: An Exponential $L_2$ Depth Hierarchy for ReLU Networks

We prove a depth hierarchy for ReLU neural networks in which every additional ReLU layer can save exponentially many neurons. For all

k\geq2

, we construct a globally

[0,1]

-valued,

1

-Lipschitz function realized by a depth-

(k+1)

network of width

\mathcal{O}(d^4)

, whereas any depth-

k

network with unrestricted weights and width at most

\frac{2^d}{2d(k-1)}

has squared

L_2

error at least

1/24

under an absolutely continuous distribution supported at exponential distance from the origin. To the best of our knowledge, this is the first exponential hierarchy across all adjacent fixed depths, and the first exponential separation for ReLU networks between two fixed depths whose shallower network has depth at least

3

. The lower bound also immediately yields the corresponding hierarchy for exact computation. Moreover, the case

k=2

gives a compactly supported separation between depths

3

and

2

with unrestricted shallow-network weights, answering a question raised by Safran, Eldan, and Shamir (2019). The distribution used in our construction nevertheless has all its mass at exponential radius, placing the hierarchy outside the regularity regime in which such a separation would imply major threshold-circuit lower bounds. We also prove an exact separation for a more regular target, which is globally

[0,1]

-valued and

\mathcal{O}(\sqrt d)

-Lipschitz and maps the unit hypercube onto

[0,1]

. It is computed by a polynomial-width depth-

4

network, whereas any depth-

3

network agreeing with it on the unit hypercube requires exponentially many first-layer neurons, even with unrestricted weights.

Itay Safran

Stein Faculty of Computer and Information Science, Ben-Gurion University of the Negev

Shallow Neural Networks ReLU Neural Networks Neural Network Approximation Theory Neural Network Expressivity

Ask PDF

Aug 12, 2026cs.LG

The Boolean Power of ReLU

We prove that, on finite simple undirected graphs equipped with a single Boolean node feature, the Boolean queries expressible in

Σ

-MPLang, for any collection

Σ

of eventually constant activation functions and with arbitrary real coefficients, form a strict subclass of the Boolean queries expressible in ReLU-MPLang. We thereby settle a recently posed open problem: whether ReLU-MPLang is more powerful than trReLU-MPLang when it comes to Boolean queries. In particular, this implies that ReLU-GNNs are strictly more expressive than {TrReLU,id}-GNNs with respect to Boolean queries on Boolean-featured graphs.

Pablo Barceló, Floris Geerts, Matthias Lanzinger +2

Pontifical Catholic University · IMFD & CENIA, Chile · University of Antwerp +4

ReLU Neural Networks GNN Expressivity Neural Network Expressivity

Ask PDF

Aug 7, 2026cs.LG

Hidden Gauge Controls Feature Specialization in ReLU Networks

Training changes a network's predictions while allocating task-relevant structure across its internal units. In an overparameterized ReLU network, several neurons can begin with exactly the same functional role, yet one may acquire a teacher feature while the others become redundant. We call the identity of that neuron feature ownership and ask whether it can be controlled by a parameter choice invisible to the initial predictor. In a tractable Gaussian teacher--student model, we fix the complete initial function and vary only a positive-homogeneous scaling gauge. Opposite gauges produce distinct feature trajectories and a sharp

Θ(D^2)

separation in specialization time that no global change of clock can explain. Among any fixed number of initially duplicate students, assigning the favorable gauge to one neuron deterministically selects it as the owner and drives the remaining functional contribution to zero. An exact reaction--transport decomposition attributes the effect to different mobilities for changing a feature's coefficient and direction. We prove global selection and functional pruning, extend finite-time selection to visible perturbations and small-step full-batch gradient descent, and verify the predicted loss, alignment, pruning, and dissipation trajectories in population and finite-sample training. The initial predictor therefore determines neither when the feature is learned nor which neuron learns it.

Tongxi Wang

School of Future Technology Southeast University Nanjing, China

ReLU Neural Networks Neural Network Training Dynamics

Ask PDF

Aug 7, 2026math.NA

Optimal Neural Network Approximation via Empirical Least Squares with Deterministic Samples

We develop a rigorous theory of discrete residual least-squares approximation for elliptic spectral equations

\mathfrak L_βu=f

using linearized ReLU

^k

neural networks on the sphere, where

\mathfrak L_β

is a positive elliptic spectral multiplier of order

β

. Given a parameter set

Θ_n=\{θ_{j}^*\}_{j=1}^n\subset\mathbb S^d

, we approximate

u

in the linearized network space

L_n^k(Θ_n)

by the discrete residual on the collocation points

\{η_i^*\}_{i=1}^m

\begin{equation*} u_{n,m}\in\arg\min_{v_n\in L_n^k(Θ_n)}\frac1m\sum_{i=1}^m\left(f(η_i^)-\mathfrak L_βv_n(η_i^)\right)^2. \end{equation*} With

k>\frac{d-1}{2}+β

, for antipodally quasi-uniform network parameter sets and any quasi-uniform collocation points with

m\gtrsim n

, we prove that \begin{equation*} |u-u_{n,m}|{\mathcal H^β(\mathbb S^d)}\eqsim|f-\mathfrak L_βu{n,m}|{\mathcal L^2(\mathbb S^d)}\lesssim n^{-\frac{r}{d}} \begin{cases} |f|{\mathcal W^{r,p}(\mathbb S^d)},&\frac{d}{p}<r\leq \frac{d}{2},~p>2,\ |f|{\mathcal H^r(\mathbb S^d)},&r>\frac{d}{2}. \end{cases} \end{equation*} We also establish a high-probability residual estimate, up to a logarithmic factor and an arbitrarily small smoothness loss, for i.i.d.\ uniformly distributed collocation points. The key analytical ingredient is a Bernstein inequality for linearized ReLU $^k$ network spaces. If $\underline h$ denotes the antipodal separation distance of the network parameters, then \begin{equation*} |v_n|{\mathcal H^r(\mathbb S^d)}\lesssim\underline h^{-(r-s)}|v_n|_{\mathcal H^s(\mathbb S^d)},\qquad 0\leq s<r<k+\tfrac12. \end{equation*}

Xinliang Liu, Tong Mao, Jinchao Xu

School of Mathematical Sciences, Ocean University of China, Qingdao 266100, China · Shenzhen Loop Area Institute, Shenzhen 518000, P. R. China

Neural PDE Solvers ReLU Neural Networks Neural Network Approximation Theory

Ask PDF

Aug 5, 2026math.OC

A Counterexample to Fourier Alignment in Single-Neuron Modular Addition

We give a negative solution to MAIS-O60. We first construct an example in which an initially active ReLU neuron becomes completely inactive in finite time and thereafter remains frozen at a limit whose Fourier energy is equally distributed among all nonzero real frequency classes. The counterexample holds on an open set of initial conditions and therefore occurs with positive probability under Gaussian initialization. An appendix prepared by GPT-5.6 Sol strengthens the counterexample by showing that the same failure can occur for every Clarke trajectory from an open set of initial conditions, under the convention

\mathrm{ReLU}'(0)=0

, for smooth dead-zone approximations of ReLU, and for fixed-step full-batch gradient descent. Thus, single-frequency alignment is not a general consequence of training a single neuron on modular addition.

Gautam Neelakantan Memana

Shallow Neural Networks ReLU Neural Networks Frequency-Domain Feature Learning Neural Network Training Dynamics

Ask PDF

Aug 4, 2026cs.LG

Tight Worst-Case Bounds for the Smallest Eigenvalue of ReLU NTK Gram Matrices

For

n

unit vectors

x_1,\ldots,x_n \in \mathbb{R}^d

, we study the continuous ReLU derivative Gram matrix

H

, whose entries are obtained by averaging pairwise gated inner products over a standard Gaussian direction. Writing

Δ_\pm := \min_{i \neq j} \min\{ \|x_i-x_j\|_2, \|x_i+x_j\|_2 \}

for their projective separation, we prove the universal dimension-free lower bound

λ_{\min}(H) = Ω( Δ_\pm/\sqrt{\log n} )

. Conversely, we construct worst-case families satisfying the matching upper bound

λ_{\min}(H) = O( Δ_\pm/\sqrt{\log n} )

, showing that this rate is tight up to universal constants.

Zhao Song

ReLU Neural Networks Spectral Methods Neural Tangent Kernel

Ask PDF

Jul 31, 2026cs.LG

Learning Lookahead Lemmas for Neural Network Verification

State-of-the-art neural network verifiers use the branch-and-bound procedure as their core solving mechanism. We introduce an inprocessing framework for neural network verification driven by the lookahead procedure. Under this framework, lookahead derives new lemmas over the phases of unstable ReLUs, which are collected into an implication graph that is used to prune the search space and vivify boolean cuts. We instantiate the framework in two state-of-the-art verifiers, Marabou and

α

β

-CROWN, and demonstrate that it improves performance in both, proving up to 34% more instances unsatisfiable.

Liam Davis, Haoze Wu

Amherst College

Neural Network Verification ReLU Neural Networks Branch and Bound Tree Search

Ask PDF

Jul 23, 2026cs.LG

New Complexity-Theoretic Frontiers of Tractability for Neural Network Training

In spite of the fundamental role of neural networks in contemporary machine learning research, our understanding of the computational complexity of optimally training neural networks remains incomplete even when dealing with the simplest kinds of activation functions. Indeed, while there has been a number of very recent results that establish ever-tighter lower bounds for the problem under linear and ReLU activation functions, less progress has been made towards the identification of novel polynomial-time tractable network architectures. In this article we obtain novel algorithmic upper bounds for training linear- and ReLU-activated neural networks to optimality which push the boundaries of tractability for these problems beyond the previous state of the art. In particular, for ReLU networks we establish the polynomial-time tractability of all architectures where hidden neurons have an out-degree of

1

, improving upon the previous algorithm of Arora, Basu, Mianjy and Mukherjee. On the other hand, for networks with linear activation functions we identify the first non-trivial polynomial-time solvable class of networks by obtaining an algorithm that can optimally train network architectures satisfying a novel data throughput condition.

Cornelius Brand, Robert Ganian, Mathis Rocton

Algorithms & Complexity Group Vienna University of Technology Favoritenstraße 9-11, 1040 Vienna, Austria

ReLU Neural Networks Neural Network Optimization Deep Linear Networks

Ask PDF

Jul 22, 2026cs.LG

Shallower ReLU Network Representations via Exact Linear Algebra

We study the depth required by ReLU networks to exactly represent piecewise linear functions, focusing specifically on the maximum function. This problem has recently received significant attention in both the ML and TCS literature. We prove that

\max_n(x)=\max\{x_1,\ldots,x_n\}

is exactly representable with two hidden layers for every

n\leq 12

. Previously, this was only known up to

n\leq5

[Bakaev, Brunck, Hertrich, Stade, Yehudayoff, STOC'26]. We obtain our constructions through an exact computer-assisted search within a space of candidate solutions: After a symmetry reduction, we obtain a finite system of linear equations over

\mathbb{Q}

such that any solution yields a valid representation of the maximum function. The resulting constructions have a structured first hidden layer, which enables recursive substitution into deeper networks. This yields an exact ReLU representation of

\max_n

with at most

\lceil \log_6(n/2) \rceil+1

hidden layers. Consequently, every continuous piecewise-linear function on

\mathbb{R}^d

admits an exact representation with at most

\lceil\log_6((d+1)/2)\rceil+1

hidden layers; in particular, two hidden layers suffice for

d\leq 11

. Again, these results improve upon [Bakaev, Brunck, Hertrich, Stade, Yehudayoff, STOC'26], who proved analogous logarithmic bounds with base three.

Kilian Rueß, Gennadiy Averkov, Florestan Brunck +7

University of Technology Nuremberg · Brandenburg University of Technology Cottbus–Senftenberg · University of Copenhagen +3

Shallow Neural Networks ReLU Neural Networks Neural Network Approximation Theory

Ask PDF

Jul 22, 2026cs.LG

Exact ReLU realization of affine one-dimensional refinement iterates via residual memory and offset frames

We study vector-valued affine refinement operators of the form [ (Wγ)(t)=\sum_{j\in\mathbb{Z}} A_jγ(Mt-j)+B(t), ] with finitely supported matrix mask and compactly supported continuous piecewise linear input and forcing data. Building on the homogeneous realization theorem for (B\equiv 0), we prove that, for (M\ge 3), every finite affine iterate (W^nγ) admits an exact fixed-width ReLU realization whose depth is (O(n)). The main new ingredient is a residual memory controller. It replaces the noninvertible residual dynamics by an injective skew-product and permits exact backward replay of the residual states required by a Horner-type evaluation of the affine forcing sum. Offset frames align the forcing atoms away from residual seams, allowing complementary loop readouts to recover their values exactly. The remaining branch-selection ambiguity occurs only where the accumulated affine state has already vanished. For (M\ge 3), the result applies to arbitrary compactly supported continuous piecewise linear forcing terms. For (M=2), the same construction applies to ordinary-frame seam-separated forcing. We also prove a stage-dependent extension for forcing terms in a fixed finite-dimensional continuous piecewise linear span and record the resulting linear-depth upgrade for open-curve, finite-state, and Hilbert- and Morton-type recursive constructions.

Boldsaikhan Bolorkhuu, Tsogtgerel Gantumur

2National University of Mongolia · 1McGill University · Institute of Mathematics and Digital Technology, Mongolian Academy of Sciences

ReLU Neural Networks Iterative Refinement

Ask PDF

Jul 21, 2026math.NA

Neural network realization of binary refinement iterates via a two-chart atlas selector

Refinement operators generate many functions used in wavelet constructions, subdivision schemes, and geometric modeling. Their finite iterates can develop rapidly increasing numbers of linear pieces, making them a natural test case for the expressive power of deep neural networks. Earlier work showed that, for scalar binary refinement with a finitely supported mask, every compactly supported continuous piecewise linear seed has finite refinement iterates that admit exact ReLU realizations of fixed width and depth growing linearly with the number of refinement steps. The present paper gives a new construction of this known theorem. The difficulty is that the refinement cascade is driven by discontinuous binary digit choices, whereas ReLU networks produce continuous piecewise linear maps. We represent the residual dynamics on a polygonal model of the circle and describe each residual position in two overlapping coordinate systems, one ordinary and one shifted by one half. Their discontinuities occur at different points. The network switches between the two descriptions only where both are valid and the corresponding fixed linear cascade updates agree, so the switch is exact and requires no multiplication by a variable selector. The construction also gives exact readout of every continuous piecewise linear circle function satisfying the natural endpoint compatibility condition. Localized seeds are handled by a two-pass network, and translation covariance, finite decomposition, and gluing extend the result to arbitrary compactly supported continuous piecewise linear seeds in a preserved support window.

Tsogtgerel Gantumur

McGill University, Montr´eal, QC, Canada · National University of Mongolia, Ulaanbaatar, Mongolia · Mongolian Academy of Sciences, Institute of Mathematics and Digital Technology

ReLU Neural Networks Neural Network Approximation Theory Iterative Refinement Neural Network Expressivity

Ask PDF

Jul 18, 2026cs.LG

Effects of width-dependent model hyperparameters and $\ell_2$ -regularization on the loss landscape of two-layer ReLU networks

Understanding deep neural networks remains a central challenge in machine learning. In particular, the theoretical properties of even two-layer ReLU networks, especially in the presence of weight decay, remain poorly understood. To this end, we derive a sufficient condition on the hyperparameter settings under which the global minima collapse to the zero solution. Interestingly, our experiments reveal that using AdamW as an optimizer prevents the collapse of the learned parameters, whereas using SGD does not, which may help explain the success of AdamW in deep learning training. In addition, when restricting the input dimension to one, we derive an analytical solution for the globally optimal parameter sets of two-layer ReLU networks and show that

\ell_2

-regularization has a width-invariant effect on connectivity, but its dimensionality-reducing effect becomes stronger as the network width increases. These results provide insight into how width-dependent hyperparameters influence the geometry of regularized loss landscapes.

Haruka Eshima, Makoto Yamada

Okinawa Institute of Science and Technology, Okinawa, Japan

ReLU Neural Networks Weight Decay Neural Network Optimization Loss Landscape Geometry Hyperparameter Optimization

Ask PDF

Jul 15, 2026cs.CC

Random Parameter Noise Does Not Make Exact ReLU Verification Easy

We study exact verification of ReLU networks in an adversarial smoothed model. Every network weight and bias is independently perturbed by Gaussian noise, clipped to

[-2,2]

, and rounded to the exact dyadic grid determined by the input bit complexity. We show that, under the standard assumption

\mathrm{NP}\not\subseteq\mathrm{BPP}

, there is no sound and complete verifier whose expected running time is polynomial in network size, bit complexity, and inverse noise level for every base instance. The conclusion already holds at the fixed noise level

σ_\star=2^{-11}

for one-hidden-layer networks over a unit box, with hidden fan-in at most three and base coefficients in

[-1,1]

. The proof combines an exact gap embedding with a quantitative robustness argument. For every E3SAT formula

Φ

with

m

clauses, a four-ReLU-per-clause construction satisfies

\max_{x\in[0,1]^n} g_Φ(x)=(m-\operatorname{unsat}(Φ))/3

, and coordinatewise threshold rounding never decreases the objective. A weighted parameter-sensitivity inequality and Gaussian concentration then show that a verification gap linear in

m

survives the aggregate perturbation of all coefficients with probability at least

1-e^{-m/8}

. The proof includes clipping, exact dyadic rounding, output-layer perturbations, polynomial-bit sampling of the rounded Gaussian law, and the conversion from expected smoothed running time to a BPP algorithm. Computational checks test the exact identity and illustrate the different scaling of extensive and constant gaps; they are diagnostics rather than evidence for the complexity theorem. The result concerns worst-case base networks in the stated absolute-noise model, but it shows that parameter nondegeneracy alone does not yield a universal smoothed-polynomial guarantee for exact verification.

Mojtaba Soltanalian

Department of Electrical and Computer Engineering University of Illinois Chicago

Neural Network Verification ReLU Neural Networks

Ask PDF

Jul 12, 2026stat.ML

Approximation of Analytic Functions by ReLU Neural Networks with Adjustable Depth and Width

In contrast to most studies on neural network approximation theory that characterize results through a single parameter, such as the total number of network parameters, \cite{shen2020deep} pioneered the characterization of approximation rates as a joint function of the width parameter

N

and the depth parameter

L

, thereby granting greater architectural flexibility. Existing works using the

(N,L)

-characterization focus on function classes with finite smoothness

s

, establishing a typical approximation rate of

\mathcal{O}\left(N^{-2s/d}L^{-2s/d}\right)

with

d

denoting the input dimension, which indicates that network depth and width play symmetric roles for these classes. In contrast, this paper establishes upper bounds for the approximation of analytic functions, which possess infinite smoothness, via ReLU networks under the

(N,L)

-characterization. Specifically, we derive approximation rates of

\mathcal{O}\left(N^{-C L^τ}\right)

, where

C>0

is some constant and

τ>0

is a parameter influenced by the relation between

L

and

N

. In particular,

τ=1

N

scales roughly as

L^d

. Our findings reveal that depth plays a more critical role than width in the context of analytic function approximation. The main technical difficulty of obtaining such upper bounds lies in the trade-off between the smoothness parameters and the approximation accuracy. To overcome this difficulty, we employ refined constructions of several ReLU networks to approximate power functions, multivariate multiplication, and polynomials, which may be of independent interest.

Yanming Lai, Defeng Sun, Yang Wang

Department of Applied Mathematics, The Hong Kong Polytechnic University, Hung Hom, Hong Kong, China · Department of Mathematics, The University of Hong Kong, Pokfulam, Hong Kong, China

ReLU Neural Networks Neural Network Approximation Theory

Ask PDF

Jul 8, 2026cs.LG

Explaining Near-Zero Hessian Eigenvalues Through Approximate Symmetries in Neural Networks

The Hessian of the training loss governs the local geometry of the loss landscape, yet despite existing explanations for its largest eigenvalues, the origin of the vast multitude of vanishingly small eigenvalues remains elusive. We argue that the bulk consists of the weakly lifted pseudo-Goldstone modes of the continuous symmetries of the network parametrization. In deep linear networks these symmetries are exact: they generate flat directions and hence exact zero modes, whose eigenvectors we construct explicitly. Introducing a ReLU nonlinearity as a perturbation, we show that it breaks these symmetries weakly and explicitly. Resolving the spectrum at the level of eigenvectors, we find that the high-curvature directions are orthogonal to the symmetry subspace, while the bulk lies almost entirely within it. We demonstrate the mechanism in a two-layer ReLU student--teacher model and in a network trained on CIFAR-10. A convolutional example demonstrates that the same diagnostic extends beyond fully connected layers. Together, these results link the Hessian bulk to weakly broken symmetries and clarify the origin of near-zero modes.

Marcel Kühn, Bernd Rosenow

Institut für Theoretische Physik, Universität Leipzig, 04103 Leipzig, Germany · ScaDS.AI Dresden/Leipzig, Universität Leipzig, 04105 Leipzig, Germany

ReLU Neural Networks Symmetry Breaking

Ask PDF

Jul 8, 2026cs.LG

On the Principles of Deep Feedforward ReLU Networks

The architecture of deep feedforward neural networks is ubiquitous in deep learning, either as a whole system or as a subnetwork of other architectures, and thus its mechanism is a key ingredient of the black box of neural networks. On the basis of the simplest two-layer ReLU network, this paper systematically studies the mechanism of deep feedforward ReLU networks with multiple hidden layers and successfully explains the training solution obtained by the back-propagation algorithm. The concept of a path, especially in terms of the relationships between paths, plays a central role in uncovering the mystery of the black box. It is shown that a unit of a deep ReLU network can form a piecewise linear manifold to divide the input space, instead of a hyperplane of the two-layer case. How to efficiently use the hidden-layer units to produce both linear functions and partitions of the input space is also a central problem. The principles of a two-layer ReLU network can be generalized to the deeper case to a large extent, such as multiple strict partial orders and continuity restriction. The combination of the basic and simple principles proposed can yield complicated instantiations including the training solutions, and in this sense the black box of deep feedforward ReLU networks is revealed.

Changcun Huang

Shuitu Institute of Applied Mathematics, Chongqing 400700, P.R.C

ReLU Neural Networks Neural Network Interpretability Neural Network Training Dynamics Feedforward Neural Networks Neural Network Expressivity

Ask PDF

Jul 7, 2026stat.ML

A Function-Space Dichotomy for Compositional Learning: Exponential Sub-Optimality of the Neural Tangent Kernel

A persistent empirical observation is that trained neural networks outperform their neural tangent kernel (NTK) limit on tasks with compositional structure, yet a quantitative account of

\textbf{when}

and

\textbf{by how much}

has been lacking. Working on the unit circle, we give such an account through a dichotomy between two complexity measures of the target: its

\textbf{Fourier complexity}

, which controls NTK kernel regression, and its

\textbf{architectural complexity}

, which controls learning over depth-

L

, width-

w

ReLU networks with the variation norm of the weights bounded by

R

. We first characterize the minimax rate of the architecture class

\mathcal{C}_{L,w,R}

, pinning it down up to a single factor of

L

: between

Ω(Lw^2R^2/n)

and

\tilde{O}(L^2w^2R^2/n)

. We then show the NTK estimator sits

\textbf{exponentially}

above this floor whenever the two complexities decouple: for the depth-

L

iterated sawtooth, NTK regression needs

Ω(4^L)

samples while the minimax floor is polynomial in

L

. Numerical experiments confirm the theoretical claims: on bandlimited smooth targets, the NTK is competitive or better, while on the hypercube sparse-parity model, a standard two-layer network beats the NTK by four to six orders of magnitude in test error. The gap is thus a function-space property, a mismatch between the kernel's smoothness bias and the target's compositional structure, rather than a generic kernel-versus-network phenomenon.

Arkaprabha Ganguli, Emil Constantinescu

Mathematics & Computer Science Division, Argonne National Laboratory, Lemont, IL, USA

Neural Network Generalization Kernel Regression ReLU Neural Networks Neural Network Approximation Theory Neural Tangent Kernel

Ask PDF

Momentum

Related topics

Latest papers 60