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

• URL: http://arxiv.org/abs/2603.17785v1
• Date: Wed, 18 Mar 2026 14:46:55 GMT
• Title: A Dual Certificate Approach to Sparsity in Infinite-Width Shallow Neural Networks
• Abstract summary: 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.<n>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.
• Score: 1.516610503825416
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Nonconvex Composite Functional Constraints via First-Order Augmented Lagrangian Methods under Local Regularity [10.643433352418915]
  We show uniformly augmented condition bounds of primal non-balancing non-concave minimax reformulation.<n>With dual regularization, a global local argument together with a bias.<n>$KKT.
  arXiv  Detail & Related papers  (2026-07-09T21:28:29Z)
• On the Rate of Convergence of GD in Non-linear Neural Networks: An Adversarial Robustness Perspective [2.268525139011456]
  We study the convergence dynamics of Gradient Descent (GD) in a minimal binary classification setting.<n>We prove that while GD successfully converges to an optimal robustness margin, this convergence occurs at a prohibitively slow rate.<n>Our theoretical guarantees are derived via a rigorous analysis of the GD trajectories across the distinct activation patterns of the model.
  arXiv  Detail & Related papers  (2026-03-02T17:13:33Z)
• Optimal Boundary Control of Diffusion on Graphs via Linear Programming [2.064612766965483]
  We propose a framework for steady-state diffusion and flux optimization on geometric networks.<n> Boundary potentials act as controls that drive interior flux according to a linear network Laplacian.<n>The analysis connects classical results such as the Minkowski--Weyl decomposition, Hoffman's bound, and the fundamental theorem of linear programming with modern network-based diffusion modeling.
  arXiv  Detail & Related papers  (2025-11-05T02:41:07Z)
• Revisiting Zeroth-Order Optimization: Minimum-Variance Two-Point Estimators and Directionally Aligned Perturbations [57.179679246370114]
  We identify the distribution of random perturbations that minimizes the estimator's variance as the perturbation stepsize tends to zero.<n>Our findings reveal that such desired perturbations can align directionally with the true gradient, instead of maintaining a fixed length.
  arXiv  Detail & Related papers  (2025-10-22T19:06:39Z)
• A Local Polyak-Lojasiewicz and Descent Lemma of Gradient Descent For Overparametrized Linear Models [6.734175048463699]
  We derive a linear convergence rate for gradient descent for two-layer linear neural networks trained with squared loss.<n>Our convergence analysis not only improves upon prior results but also suggests a better choice for the step size.
  arXiv  Detail & Related papers  (2025-05-16T19:57:22Z)
• A Lipschitz spaces view of infinitely wide shallow neural networks [3.0017241250121387]
  We revisit the mean field parametrization of shallow neural networks, using signed measures on parameter spaces and duality pairings. We prove a compactness result in strong Kantorovich-Rubinstein norm, and in the absence of which we show several examples demonstrating undesirable behavior.
  arXiv  Detail & Related papers  (2024-10-18T16:41:37Z)
• Double Duality: Variational Primal-Dual Policy Optimization for Constrained Reinforcement Learning [132.7040981721302]
  We study the Constrained Convex Decision Process (MDP), where the goal is to minimize a convex functional of the visitation measure. Design algorithms for a constrained convex MDP faces several challenges, including handling the large state space.
  arXiv  Detail & Related papers  (2024-02-16T16:35:18Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  This paper presents a theoretical analysis of linearahead as a principled method for stabilizing (large-scale) neural network training. We argue that instabilities in the optimization process are often caused by the nonmonotonicity of the loss landscape and show how linear can help by leveraging the theory of nonexpansive operators.
  arXiv  Detail & Related papers  (2023-10-20T12:45:12Z)
• Beyond the Edge of Stability via Two-step Gradient Updates [49.03389279816152]
  Gradient Descent (GD) is a powerful workhorse of modern machine learning. GD's ability to find local minimisers is only guaranteed for losses with Lipschitz gradients. This work focuses on simple, yet representative, learning problems via analysis of two-step gradient updates.
  arXiv  Detail & Related papers  (2022-06-08T21:32:50Z)
• Lifting the Convex Conjugate in Lagrangian Relaxations: A Tractable Approach for Continuous Markov Random Fields [53.31927549039624]
  We show that a piecewise discretization preserves better contrast from existing discretization problems. We apply this theory to the problem of matching two images.
  arXiv  Detail & Related papers  (2021-07-13T12:31:06Z)
• Convex Geometry and Duality of Over-parameterized Neural Networks [70.15611146583068]
  We develop a convex analytic approach to analyze finite width two-layer ReLU networks. We show that an optimal solution to the regularized training problem can be characterized as extreme points of a convex set. In higher dimensions, we show that the training problem can be cast as a finite dimensional convex problem with infinitely many constraints.
  arXiv  Detail & Related papers  (2020-02-25T23:05:33Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.