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

Technical Deep Dive: Dual Certificate Approach to Sparsity in Infinite-Width Shallow Neural Networks

Overview

This paper studies the sparsity properties of two-layer neural networks with ReLU activations in the infinite-width regime. The authors leverage duality theory to establish rigorous guarantees on the sparsity of the solutions to the training problem, which is formulated as a convex optimization over measures on the unit sphere.

Problem & Context

• Infinite-width shallow neural networks are parametrized by a measure μ on the unit sphere Θ = ℝd-1
• Training these networks involves solving a TV-regularized empirical risk minimization problem:

$$\minμ \frac{1}{n}\sum{j=1}^n\left|y^j - \intΘ σ(〈w, x^j〉) dμ(w)\right| + λ\|μ\|{TV}$$ where σ is the ReLU activation function

• The goal is to understand when and how the solutions to this problem are sparse, i.e. composed of a finite number of Dirac deltas

Methodology

1. Duality theory:
   • Characterize the dual certificate η associated with the primal problem
   • Show that η is piecewise linear on the sphere, with linearity regions determined by the data points {x^j}
2. Sparsity analysis:
   • Prove that every solution is sparse, with the number of Dirac deltas bounded by a quantity depending only on the dimension d and number of data points n
   • Identify sufficient conditions for the uniqueness of the sparse solution
3. Sparse stability:
   • Analyze the robustness of sparsity under perturbations of the regularization parameter λ and the data labels {y^j}
   • Establish quantitative convergence rates for the weights and locations of the Dirac deltas as (λ, ζ) → (0, 0)

Results

1. Sparsity guarantees:
   • Every minimizer of the TV-regularized problem is a finite linear combination of Dirac deltas
   • The number of Dirac deltas in any minimizer is bounded by a quantity depending only on d and n
2. Uniqueness conditions:
   • Provide sufficient conditions for the uniqueness of the sparse minimizer, based on the localization of the dual certificate and the linear independence of the neural network evaluations
3. Sparse stability:
   • Show that for sufficiently small λ and label noise ζ, the sparsity pattern of the solution is preserved
   • Establish linear convergence rates for the weights and locations of the Dirac deltas as (λ, ζ) → (0, 0)

Limitations & Uncertainties

• The sufficient conditions for uniqueness of the sparse minimizer may not be sharp and a complete characterization is left as future work
• The paper focuses on the ReLU activation, and it's unclear how the results would extend to other activation functions
• The analysis is limited to the infinite-width regime and does not consider finite-width networks

What Comes Next

• Extending the analysis to other activation functions and architectures beyond the infinite-width shallow networks studied here
• Investigating the interplay between sparsity, approximation power, and representation costs of shallow neural networks
• Exploring connections between the duality-based approach in this work and other frameworks for analyzing neural network training, such as those based on Barron spaces or reproducing kernel Banach spaces