A Dual Certificate Approach to Sparsity in Infinite-Width Shallow Neural Networks

Leonardo Del Grande; Christoph Brune; Marcello Carioni

math.OCMar 18, 2026

A Dual Certificate Approach to Sparsity in Infinite-Width Shallow Neural Networks

Authors: Leonardo Del Grande, Christoph Brune, Marcello Carioni

Organizations: Department of Applied Mathematics, University of Twente, 7500AE Enschede, The Netherlands

Abstract

In this paper, we study total variation (TV)-regularized training of infinite-width shallow ReLU neural networks, formulated as a convex optimization problem over measures on the unit sphere. Our approach leverages the duality theory of TV-regularized optimization problems to establish rigorous guarantees on the sparsity of the solutions to the training problem. Our analysis further characterizes how and when this sparsity persists in a low noise regime and for small regularization parameter. The key observation that motivates our analysis is that, for ReLU activations, the associated dual certificate is piecewise linear in the weight space. Its linearity regions, which we name dual regions, are determined by the activation patterns of the data via the induced hyperplane arrangement. Taking advantage of this structure, we prove that, on each dual region, the dual certificate admits at most one extreme value. As a consequence, the support of any minimizer is finite, and its cardinality can be bounded from above by a constant depending only on the geometry of the data-induced hyperplane arrangement. Then, we further investigate sufficient conditions ensuring uniqueness of such sparse solution. Finally, under a suitable non-degeneracy condition on the dual certificate along the boundaries of the dual regions, we prove that in the presence of low label noise and for small regularization parameter, solutions to the training problem remain sparse with the same number of Dirac deltas. Additionally, their location and the amplitudes converge, and, in case the locations lie in the interior of a dual region, the convergence happens with a rate that depends linearly on the noise and the regularization parameter.

Figures & tables

Panel of Figure 1 — Figure 1: Dual regions on $\mathbb{S}^{1}$ induced by two inputs ( $d=n=2$ ).

Figure 2: Dual region decomposition of $\mathbb{S}^{1}$ and optimal solution $\mu_{\lambda,\zeta}$ . The dashed diameters correspond to the boundaries $\langle w,x_{j}\rangle=0$ induced by the five inputs ( 5.5 ), partitioning $\mathbb{S}^{1}$ into sectors on which $(\mathbf{1}\{\langle w,x_{j}\rangle>0\})_{j=1}^{5}$ is constant. We display the recovered atoms $\{w_{i}\}_{i=1}^{3}$ of $\mu_{\lambda,\zeta}$ . The arrow corresponds to the vector $\frac{\tilde{z}_{\lambda,\zeta}}{\|\tilde{z}_{\lambda,\zeta}\|}$ as in ( 3.19 ) with $\tilde{z}_{\lambda,\zeta}$ defined in ( 3.18 ). As predicted by Lemma 3.9 , this vector aligns with the location of the Dirac delta of the solution $\mu_{\lambda,\zeta}$ belonging to the interior of a dual region.

Figure 3: Dual certificate $\eta_{\lambda,\zeta}$ on $\mathbb{S}^{1}$ . The dashed circles (orange and green) show the locations where $\eta_{\lambda,\zeta}=\pm 1$ . As expected by the optimality conditions, the dual certificate is always between $-1$ and $+1$ . The points where $\eta_{\lambda}=1$ (resp. $\eta_{\lambda}=-1$ ) correspond exactly to the location of positive (resp. negative) Dirac deltas in the TV-regularized solution ( 5.7 ).

Figure 4: Size of the support depending on the regularization parameter. For $\lambda$ in the interval ( $\lambda_{\max}=1$ , $\lambda_{\min}=5\cdot 10^{-7}$ , $11$ values), we compute the cardinality of the support of the solution. As expected, the number of Dirac deltas increases with the decrease of the regularization parameter $\lambda$ . The maximum number of Dirac deltas is, however, still below the theoretical bound determined by the number of regions: $R(X)=10$ .

Panel of Figure 5 — Figure 5: Unperturbed solution and dual certificate for $\lambda=0.2$ . Left: Dual region decomposition of $\mathbb{S}^{1}$ and recovered atoms $\{w_{*}^{i}\}_{i=1}^{2}$ of the solution $\mu_{\lambda,\zeta}=\sum_{i=1}^{2}c_{*}^{i}\,\delta_{w_{*}^{i}}$ with $\zeta=0$ . Both atoms lie in the interior of a dual region. Right: Corresponding dual certificate $\eta_{\lambda,\zeta}$ on $\mathbb{S}^{1}$ . As in Figure 3 , it satisfies $|\eta_{\lambda,\zeta}|\leqslant 1$ everywhere and attains $\pm 1$ exactly at the support of $\mu_{\lambda,\zeta}$ .

Panel of Figure 6 — Figure 6: Linear decay of coefficients and locations under label noise. Left: Coefficient mismatch $L_{c}^{i}(\zeta)=|c_{\lambda,\zeta}^{i}-c_{*}^{i}|$ as a function of the noise level $\|\zeta\|$ for $i=1,2$ , together with linear fits. Right: Location mismatch $L_{w}^{i}(\zeta)=\|w_{\lambda,\zeta}^{i}-w_{*}^{i}\|$ for $i=1,2$ . Both quantities exhibit the linear dependence on $\|\zeta\|$ predicted by Theorem 4.7 .

TV Regularization

See all 10 papers

Feb 19, 2026

From Approximation Rates to Loss-Landscape Barrier Decay in Shallow ReLU Networks

We study pathwise connectivity of sublevel sets for one-hidden-layer ReLU networks with constrained first-layer weights and an

\ell_1

penalty on the output layer. The data term is assumed convex and globally Lipschitz in the scalar logit. We first give a finite-width construction that connects any two points of a common sublevel through a path controlled by a loss-consistent compression functional and a first-order perturbation term. The proof replaces the quadratic perturbation estimate in the Freeman--Bruna mechanism by a direct Lipschitz bound. Positive homogeneity is then used in a direction that is compatible with the penalty: every active atom is moved monotonically from the unit ball to the unit sphere while its output coefficient is reduced. Sphere covering and cluster merging consequently give

O(m^{-1/(n-1)})

fixed-level thickening for

n\ge2

, while the one-dimensional two-ray dictionary gives exact connectivity for every

m\ge4

. We also prove internally that the regularized approximation values satisfy

e(l)-e_\infty=O(l^{-1/2})

. More generally, a rate

O(l^{-s})

transfers to a near-optimal barrier rate

O(m^{-s/((n-1)s+1)})

; under the standing assumptions, this yields the explicit rate

O(m^{-1/(n+1)})

. A theorem-aligned finite-distribution experiment complements the analysis. The primary Huber run yields a maximal best certified upper gap

1.66\times10^{-5}

over 720 recorded pairs at widths

m\ge16

; a matched binary-cross-entropy rerun and a 720-endpoint dense-representation stress test probe loss robustness and the active cluster-merging mechanism.

Saveliy Baturin

Independent Researcher, Russia.

Shallow Neural Networks ReLU Neural Networks Mode Connectivity Neural Network Approximation Theory

Ask PDF

Jul 3, 2026

Implicit Bias of SGD in Multivariate ReLU Networks: Effective Width Collapse

We study the implicit bias of noisy stochastic gradient descent in training wide two-layer ReLU networks for multivariate regression. In a mean-field regime, the training dynamics are approximated by a Wasserstein gradient flow that converges to a unique stationary measure. We characterize the structure of this stationary measure and the predictor it represents. We show that, despite the network being infinitely overparameterized, the learned predictor admits an effectively finite representation: the input weights and biases align along finitely many directions, leading to an effective width collapse. In particular, the solution function is continuous piecewise affine, with affine regions determined by the cells of a finite hyperplane arrangement. The number of learned directions, and hence hyperplanes, is bounded above by

2\mathcal{P}-1

, where

\mathcal{P}

denotes the number of linear dichotomies realizable on the training inputs. We further establish a non-redundancy property of the learned representation by proving that each learned direction induces a unique ternary activation pattern on the training data. Consequently, the complexity of the learned predictor is governed by the combinatorial geometry of the training data.

Shuang Liang, Tom Jacobs, Guido Montúfar

Department of Statistics & Data Science University of California, Los Angeles Los Angeles, CA 90095, USA · CISPA Helmholtz Center for Information Security · Departments of Mathematics and Statistics & Data Science University of California, Los Angeles; and Max Planck Institute for Mathematics in the Sciences

Shallow Neural Networks ReLU Neural Networks Implicit Bias Neural Network Training Dynamics Stochastic Gradient Descent

Ask PDF

Sep 8, 2026

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

Abstract

TV Regularization

Explore similar work

From Approximation Rates to Loss-Landscape Barrier Decay in Shallow ReLU Networks

Implicit Bias of SGD in Multivariate ReLU Networks: Effective Width Collapse

Nearly Tight Rademacher Bounds for Sparsely Activated Neural Networks