Source-linked AI summary
Optimal Approximation with Sparsely Connected Deep Neural Networks
Helmut Bölcskei, Philipp Grohs, Gitta Kutyniok, Philipp Petersen
TL;DR
The paper asks how much connectivity and memory deep neural networks need to uniformly approximate function classes of given complexity. It uses rate-distortion and representation-system arguments to derive lower bounds and transfer optimal sparse approximation to networks, with experiments showing near-limit rates and learned structure. The main scope boundary is that one transfer step does not by itself guarantee logarithmic-bit representations for quantized network weights.
Problem
The paper studies how the complexity of a function class determines the connectivity and memory required for deep networks to approximate every function within prescribed error.
Method
It interprets networks as rate-distortion encoders and transfers optimal approximation from affine representation systems using sparsely connected networks with quantized weights.
Results
Theoretical bounds are achievable for broad affine-system classes, while stochastic gradient descent attains M-edge rates quite close to the fundamental limit in experiments.
Takeaways & Limitations
The results indicate that neural networks can realize sparse approximations aligned with representation systems that optimally sparsify the trained function class.
Takeaways & Limitations
The transfer result from individual representation-system elements does not itself guarantee weights representable with ⌈c log2(ε^-1)⌉ bits at overall error proportional to ε.
Abstract
from arXiv · showhide
We derive fundamental lower bounds on the connectivity and the memory requirements of deep neural networks guaranteeing uniform approximation rates for arbitrary function classes in $L^2(\mathbb R^d)$. In other words, we establish a connection between the complexity of a function class and the complexity of deep neural networks approximating functions from this class to within a prescribed accuracy. Additionally, we prove that our lower bounds are achievable for a broad family of function classes. Specifically, all function classes that are optimally approximated by a general class of representation systems---so-called \emph{affine systems}---can be approximated by deep neural networks with minimal connectivity and memory requirements. Affine systems encompass a wealth of representation systems from applied harmonic analysis such as wavelets, ridgelets, curvelets, shearlets, $α$-shearlets, and more generally $α$-molecules. Our central result elucidates a remarkable universality property of neural networks and shows that they achieve the optimum approximation properties of all affine systems combined. As a specific example, we consider the class of $α^{-1}$-cartoon-like functions, which is approximated optimally by $α$-shearlets. We also explain how our results can be extended to the case of functions on low-dimensional immersed manifolds. Finally, we present numerical experiments demonstrating that the standard stochastic gradient descent algorithm generates deep neural networks providing close-to-optimal approximation rates. Moreover, these results indicate that stochastic gradient descent can actually learn approximations that are sparse in the representation systems optimally sparsifying the function class the network is trained on.
1 Introduction
The paper frames deep neural networks as sparse, weighted layered maps and asks how function-class complexity determines the connectivity and memory needed for uniform approximation. It develops approximation-theoretic notions and establishes lower bounds, transfer principles, memory characterization, and near-optimal stochastic-gradient-descent performance.
- 1 Introduction: The central question is how the complexity of a function class determines the connectivity and memory required to approximate every function within error ε.The paper interprets networks as encoders in rate-distortion theory.
- 1.1 Deep Neural Networks: Deep neural networks concatenate affine maps and nonlinearities, with weights assigned to graph edges and nodes across hierarchical layers.Connectivity is the number of nonzero edge weights; sparse connectivity means few active edges relative to a fully connected network.
- 1.3 Approximation by Deep Neural Networks: The framework replaces best M-term approximation in representation systems with best M-edge approximation by neural networks.Parsimony is measured by participating network connections rather than representation-system elements.
- 1.3 Approximation by Deep Neural Networks: The paper quantifies fundamental connectivity lower bounds, transfers M-term approximation results to neural networks, and characterizes storage for topology and quantized weights.These results link function-class complexity with network connectivity and memory requirements.
- 1.3 Approximation by Deep Neural Networks: Stochastic gradient descent produces M-edge approximation rates quite close to the paper’s fundamental limit in numerical experiments.The experiments assess trained networks relative to the theoretical bounds.
2 Effective Best M-term and Best M-edge Approximation
The paper introduces effective approximation notions that constrain search depth and coefficient or weight growth, preventing unrestricted dense systems or networks from yielding misleadingly infinite rates. These notions support finite complexity-dependent limits and a new effective best M-edge framework.
- 2.1 Effective Best M-term Approximation: Effective best M-term approximation restricts dictionary search to polynomial depth and coefficients to bounded magnitudes.These restrictions address the infeasibility and infinite-description issues of unrestricted dense representation systems.
- 2.1 Effective Best M-term Approximation: Under general conditions, the supremum of effective best M-term rates over representation systems is finite and depends on the function class’s description complexity.This provides an ultimate benchmark for evaluating a representation system.
- 2.2 Effective Best M-edge Approximation: Unconstrained neural-network approximation can have infinite rates for compact function classes because fixed-size networks may achieve arbitrarily small errors.The relevant networks use weights that are not polynomially bounded in ε^-1.
- 2.2 Effective Best M-edge Approximation: When the optimal rate is finite, the weights achieving unrestricted network infima cannot generally be bounded polynomially in M proportional to ε^-1.This motivates imposing polynomial weight-growth constraints.
- 2.2 Effective Best M-edge Approximation: The paper formalizes effective best M-edge approximation subject to polynomial weight growth as a neural-network analogue of effective best M-term approximation.The concept controls network weights while measuring approximation through connectivity.
3 Fundamental Bounds on Effective M-Term and M-Edge Approximation Rate
The paper frames function-class description complexity as a fundamental limit on effective approximation, then establishes matching lower-bound and achievability results for deep neural networks with quantized, polynomially bounded weights.
- Min-Max Rate Distortion Theory: The minimax code length L(ε, C) measures the bits needed for uniform ε-accurate reconstruction, while γ∗(C) quantifies the function class’s description complexity.Larger γ∗(C) corresponds to smaller memory requirements as ε approaches zero.
- Fundamental Approximation Bounds: The optimal exponent γ∗(C) provides a fundamental bound on effective best M-term approximation rates in any representation system.This gives operational meaning to the rate-distortion quantity.
- Neural-Network Bounds: Theorem 3.4 extends the same fundamental exponent to effective best M-edge approximation by deep neural networks with suitable activation functions.The result applies when ρ is Lipschitz-continuous or differentiable with ρ′ dominated by an arbitrary polynomial.
- Conceptual Implications: Neural networks and representation systems share the same approximation limits despite using fundamentally different approximants and structural constraints.The comparison is between sparse representation-system combinations and affine-function/nonlinearity concatenations in networks.
- Achievability and Quantization: Quantized network encodings use at most ⌈c log2(ε−1)⌉ bits per weight while preserving uniform error ε and the required approximation-rate growth.The construction encodes both network topology and quantized weights, with unique reconstruction.
- Strong Converse and Scope: With weights polynomially bounded in ε−1, edge growth cannot be smaller than O(ε−1/γ∗(C)); faster error decay than O(M−γ∗(C)) is impossible.Without this weight-growth constraint, finite-node networks can achieve arbitrarily small error using non-polynomially bounded weights.
4 Transitioning from Representation Systems to Neural Networks
The paper transfers optimal approximation results from representation systems to neural networks by approximating individual representation elements and combining those subnetworks in parallel.
- Transference Principle: The transference framework targets function classes that are optimally approximated by representation systems whose individual elements can be represented by neural networks.The paper develops this as a general framework for converting representation-system approximation results into neural-network results.
- Representation-System Approximation: Theorem 4.2 constructs a neural network for an M-term representation approximation using parallel subnetworks with total connectivity M′ ∈ O(M).The subnetworks share the input, and their one-dimensional outputs are summed with the representation coefficients.
- Scope of the Transfer: The initial transfer theorem controls connectivity but does not by itself guarantee logarithmic weight-bit representations at the overall target error.The stronger effective-representability conditions address this limitation through a further transfer argument.
- Effective Approximation: Theorem 4.3 preserves uniform ε-accuracy while using O(ε−1/γ) edges and at most ⌈c log2(ε−1)⌉ bits per weight for every γ < γ∗,eff(C, D).The construction applies when the representation system is effectively representable and the activation function satisfies the stated regularity conditions.
- Optimal Representability: If a representation system optimally represents C and is effectively representable by neural networks, then C is optimally representable by neural networks.This is the paper’s formal universality implication for the transfer framework.
5 All Affine Representation Systems are Effectively Representable by Neural Networks
The paper shows that affine representation systems can be effectively represented by neural networks, under suitable activation-function and weight-growth conditions. This yields optimal neural-network approximation for function classes optimally represented by such systems.
- Affine systems: Affine systems include wavelets, ridgelets, curvelets, shearlets, α-shearlets, and more generally α-molecules, and can be effectively represented by neural networks.The result applies to systems generated through affine transformations of functions approximable by neural networks.
- Activation functions: The required activation functions are sigmoidal functions or smooth approximations of ReLU, because these support economical representations of multivariate bump functions.The paper notes that strong universality statements require restrictions on the activation function.
- Network constructions: B-splines can be approximated arbitrarily accurately by sigmoidal networks whose depth depends on the spline order, dimension, and sigmoidality order.The construction uses networks in NNL,M,d,ρ with L = ⌈log2(md − d) / log2(k)⌉ + 1 layers.
- Network constructions: Admissible smooth activations can exactly represent a general class of bump functions using networks with only 3 layers.This provides a second route for representing affine systems built from bump functions.
- Affine transformations: Representability is preserved under finite linear combinations and affine transformations, with connectivity and weight bounds controlled by the original network and transformation parameters.The transformation result gives polynomial weight bounds in ||A||∞, E, ||b||∞, and η^-1.
- Optimality and universality: Neural networks optimally represent every function class that is optimally represented by an affine system whose generator can be approximated arbitrarily accurately by neural networks.Under polynomial weight bounds and the stated affine-system growth condition, the approximations use O(ε^-1/γ) nonzero edges and O(log2(ε^-1)) bits per weight for every γ < γ∗(C).
6 α-Shearlets and Cartoon-Like Functions
This section establishes that α-shearlets optimally represent α^-1-cartoon-like functions and that neural networks can achieve the same optimal approximation behavior under suitable activation assumptions.
- α^-1-cartoon-like functions model piecewise-smooth functions separated by smooth interfaces, including curvilinear discontinuities relevant to images and transport equations.
- For cartoon-like functions, networks with weights stored using at most ⌈c log2(ε^-1)⌉ bits have effective best M-edge approximation rate at most β/2.Achievability is stated for β = 1/α with α ∈ [1/2, 1].
- α-shearlets are stated to yield optimal best M-term approximation rates for α^-1-cartoon-like functions.
- For α ∈ [1/2, 1], suitable smooth generators make the α-shearlet system optimally represent E1/α(R2; ν).The generators satisfy smoothness, Fourier nonvanishing, and vanishing-moment conditions.
- Theorem 6.8 states that E1/α(Ω; ν) is optimally representable by neural networks for bounded Ω and strongly sigmoidal or admissible smooth activations.The result applies for every α ∈ [1/2, 1].
- The required network depth depends on the activation function: admissible smooth activations permit three layers, whereas sigmoidal activations require a minimum depth determined by the construction.The theorem does not require particularly smooth network activations; differentiability can suffice.
7 Generalization to Manifolds
The paper extends approximation results from Euclidean domains to low-dimensional immersed manifolds by local parametrization, localization, and recombination with neural networks.
- Functions on an m-dimensional immersed manifold are covered by patches parametrized as graphs over subsets of m Euclidean coordinates.Each patch is represented through a smooth mapping Ξi.
- A smooth partition of unity localizes the target function to the manifold patches before approximation in Euclidean coordinates.The localized functions are fi := fhi and are pulled back through the patch parametrizations.
- An m-dimensional neural network can be lifted to a d-dimensional network by composing it with the linear coordinate projection associated with each patch.The lifted network increases the edge budget from M to M + md.
- Summing the finitely many localized patch networks yields a neural network that approximates the compactly supported function on the manifold.Finiteness follows from the compact support of f.
- Approximation results on Rm lift to m-dimensional submanifolds when the function class is invariant under diffeomorphisms and multiplication by smooth functions.The paper notes that cartoon-function classes satisfy these invariances.
8 Numerical Results
The numerical experiments test stochastic gradient descent on fixed sparse topologies and find approximation rates near theoretical limits, while learned subnetworks resemble representations suited to the target singularities.
- The experiments evaluate stochastic gradient descent against the fundamental lower bound on the number of nonzero-weight edges needed for uniform approximation.
- A fixed sparsely connected ReLU topology produces M-edge approximation rates close to the theoretical limit under stochastic gradient descent.The topology is inspired by the network constructions used for bump functions.
- For a function with a line singularity, approximation error decays faster than exponentially with the number of edges, consistently with ridgelet best M-term rates for piecewise constant functions.The observed faster-than-linear decay is measured in a semi-logarithmic plot.
- The learned subnetworks for the line-singularity experiment form α-molecules with α = 0 and have orientations matching the original function’s ridge structure.These subnetworks can therefore be viewed as elements of a ridgelet system.
- For a curvilinear singularity, trained subnetworks resemble anisotropic molecules across scales and orientations, while unadapted training does not approach the predicted M^-1 rate.A slight adaptation produces the reported Figure 5(b) result.
- Subnetworks with large supports reconstruct smooth regions, whereas subnetworks with small supports resolve the jump singularity.This support-dependent behavior parallels the localization pattern associated with shearlet approximations.