PaperlayerView exact revision on arXiv

Source-linked AI summary

Width-Independent Compressibility of Deep Neural Networks

Hong-Yi Wang, Mingze Wang, Liu Ziyin

arXiv:2608.21752v1cs.LGcond-mat.dis-nncs.IT

TL;DR

The paper addresses why wide neural networks can admit much smaller representations by proving a uniform compressibility theorem for analytic deep MLPs. Its derivative-matching and layer-wise compression construction produces same-depth approximations with retained width polylogarithmic in inverse error and no additional explicit original-width factor, subject to teacher-dependent constants.

  • Problem

    The paper studies how to approximately preserve a deep MLP’s input-output mapping while compressing its wide hidden layers, in a phenomenon whose underlying basis remains poorly understood.

  • Method

    The construction matches derivative features on the low-dimensional input and compresses hidden layers backward with layer-wise error allocation and reweighted outgoing connections.

  • Results

    For a fixed teacher, same-depth width caps are polylogarithmic in 1/ε with no additional explicit original-width factor; one-layer compression yields O((log(1/εℓ))^din), and a practical trial reached median width 28 with a 304× parameter reduction.

  • Takeaways & Limitations

    The theorem provides a function-level existence certificate for compressing arbitrary intermediate layers of analytic deep MLPs, complementary to practical post-training methods.

  • Takeaways & Limitations

    The construction is not necessarily practical as-is because evaluating high-order derivative features is compute- and memory-expensive, and extending the result to noisy or approximately low-dimensional inputs remains open.

Abstract

from arXiv · show

It has long been known that well-trained neural networks can be compressed very strongly without affecting their performance, an important phenomenon that remains poorly understood. We prove a uniform compressibility theorem for deep multilayer perceptrons with analytic activations. For a deep, wide fixed teacher network, there exists a narrow (same depth) network that approximately represents the same function as the original. The reachable compressed width is strikingly independent of the original width, but is $O((\log(1/\varepsilon))^{d_{in}})$, where $\varepsilon$ is the error budget and $d_{in}$ is the effective input dimension. Our construction involves a novel derivative-matching technique which is aware of the low-dimensional input, and a layer-wise reweighting that preserves the input-output mapping.

1 Introduction

The paper asks whether a fixed trained deep network admits a uniformly accurate narrow representation and identifies a constructive answer for analytic-activation MLPs. Its compression width depends polylogarithmically on inverse error and the effective input dimension, without an explicit original-width factor.

  • Motivation: A fixed trained deep network may admit a much smaller representation despite interventions ranging from quantization to layer dropping.
  • Open question: Uniform compression theory has largely lacked a constructive, data-free sup-norm guarantee for fixed deep MLPs that composes across layers.
  • Core idea: Holomorphic extensions and Cauchy’s inequality turn finite-order input-derivative matching at the origin into uniform error control on a bounded real domain.
  • Core idea: A deterministic rank-reduction procedure retains at most Dk original neurons and recomputes outgoing weights while controlling input-to-output error.
  • Result: For a fixed teacher, width caps are polylogarithmic in 1/ε with no additional explicit original-width factor, while layer-wise backward composition preserves controlled error.

2 Problem setup

The setup studies same-depth approximation of one fixed finite teacher MLP on a bounded input domain, targeting uniform output error while compressing wide hidden layers. The theorem relies on analyticity, bounded weights, compatible radii, and an admissible effective input dimension.

  • Problem setup: The goal is a same-depth network whose uniform output error satisfies supx∈Ω∥eF(x)−F(x)∥∞≤ε while retaining accuracy-driven hidden-layer widths.
  • Scope: The teacher is one fixed finite network, so the theorems do not provide a common retained-width bound across teachers with varying original widths.
  • Compression procedure: The construction first compresses a single intermediate layer under εℓ, then composes hidden-layer compressions with an assigned total error budget.
  • Effective input dimension: An effective input dimension m requires an exact factorization through reduced coordinates satisfying the stated analytic and radius conditions; m = din is always the baseline.
  • Assumptions: The assumptions include holomorphic upstream maps, real-analytic activations, per-layer weight bounds, outgoing ℓ1-norm bounds, and R < ρ for error-budget compatibility.
  • Limitations: ReLU is outside the stated analytic-activation assumption, and extending the construction to it requires a separate approximation argument.

3 Related works

Related work spans approximation theory, depth–width results, practical compression, constructive theoretical guarantees, and tensor-moment methods. The paper differs by uniformly compressing fixed deep teachers while preserving depth and exploiting effective input dimension.

  • Approximation theory: Classical approximation theory targets external function classes, whereas this work uniformly approximates a fixed teacher network on a bounded domain with accuracy-driven retained width.
  • Approximation theory: Analytic-function entropy comparisons support the [log(1/ε)]^m dependence, although they do not establish a compression lower bound for one fixed teacher.
  • Depth, width, and smoothness: Unlike depth–width separation results for increasingly hard function families, this theory preserves the original depth for each fixed covered teacher.
  • Empirical and theoretical compression: Practical compression commonly uses pruning, quantization, low-rank factorization, and distillation, while existing constructive guarantees are typically data-dependent or structurally restricted.
  • Tensor moment methods: The derivative-feature basis replaces tensor moments over weights and enables compression when adjacent layers are also wide.
  • Tensor moment methods: The paper removes the explicit original-width factor in its fixed-teacher formula and extends layer-wise compressibility from two-layer settings to all hidden layers of deep networks.

4 Proof idea for compressing one layer

The single-layer construction reformulates neurons as a measure, matches low-order input derivatives, and uses sparse rank reduction with reweighting to preserve the layer map. The resulting width depends polylogarithmically on inverse error and on effective input dimension, rather than explicitly on the original width.

  • Measure compression: The ℓ-th layer is represented as an integral over its empirical neuron measure, and compression replaces it with a measure supported on fewer neurons.This converts layer compression into finding a smaller measure that approximates the original input-output map within a layer error budget.
  • Derivative matching: Matching input derivatives at the origin through order k leaves only a Taylor remainder bounded geometrically by (R/ρ0)k+1.The holomorphy radius of the activation controls the remainder rate.
  • Derivative matching: The derivative basis is smaller than a generic monomial basis because it exploits the specific MLP expression and its low-dimensional input dependence.This is the key structural improvement over tensor-moment matching for generic permutation-symmetric functions.
  • Rank reduction and reweighting: A linear-algebra rank-reduction step finds a reweighted compressed measure with at most Dk nonzero columns, while controlling outgoing-weight inflation by at most Dk.The reweighting constructs new incoming and outgoing matrices implementing the compressed layer.
  • Width bound: k* = O(log(1/εℓ)) yields compressed width Dk*(εℓ) = O((log(1/εℓ))^din) for a fixed teacher and effective input dimension.With teacher constants fixed, the cap has no additional explicit dependence on the original layer width; genuine narrowing requires dℓ > Dk*(εℓ).
  • Numerics: Numerics show geometric error decay for sigmoid and GELU, reaching the float32 noise floor near 10^-6 by k ≈5 when R ≤1.At k = 9, the single-layer error is below 10^-5 uniformly in the unit ball for both activations.

5 Compressing all layers

Applying the single-layer theorem backward across hidden layers yields a same-depth deep network with a uniform error guarantee. Theory favors backward order, while experiments find forward and backward compression essentially indistinguishable in the tested networks, including a trained case with substantial parameter reduction.

  • Theory and order: Backward compression preserves bounded analytic constants for subsequently compressed layers, enabling composition of layer-wise error budgets into a total error guarantee.Forward compression recursively inflates constants and has no rigorous guarantee in the presented analysis.
  • Deep theorem: The deep theorem gives every hidden layer a width bound whose suppressed constants depend on the activation and original teacher weights, with total dependence polylogarithmic in 1/ε for fixed depth.The constants incorporate per-layer holomorphic radii, downstream Lipschitz factors, and the single-layer theorem constants.
  • Random-network numerics: Four hidden layers of width 1024 were compressed to 66 neurons at k = 10 in the deep numerical experiment.The experiment compared forward and backward orders across sigmoid and GELU activations and several input radii.
  • Random-network numerics: Forward and backward orders were indistinguishable within float32 noise across every tested k, radius, and activation, while error decayed geometrically with k.The observed rate slowed as the input radius increased, consistent with the single-layer behavior.
  • Post-training compression: A trained [2, 512, 512, 512, 1] sigmoid MLP met the target-MSE criterion at median width 28 across five seeds, corresponding to a 304× reduction in total parameter count.Compression used frozen weights and no fine-tuning; the formal Assumption 4 was violated in all trials.

6 Discussion and outlook

The paper establishes uniform compression for analytic deep MLPs and identifies open boundaries involving practicality, activation scope, effective dimension, and critical width.

  • Discussion and outlook: The construction gives a first layer-wise, uniform compression certificate for arbitrary intermediate layers of a deep MLP.It computes derivative features, selects a rank basis, and recomputes outgoing weights.
  • Discussion and outlook: The retained width is polylogarithmic in inverse per-layer error, without an explicit original-width factor after teacher constants are evaluated.Teacher norms and downstream factors can still affect the constants indirectly through width.
  • Limitations: High-order derivative-feature evaluation is compute- and memory-expensive, so the construction is primarily an existence proof rather than an immediately practical method.The authors expect future work to reduce compression cost and residual error.
  • Open problems: The theorem covers admissible effective input dimensions, but extending it to approximately low-dimensional or noisy near-manifold inputs remains open.The paper notes illustrative intrinsic-dimension estimates of roughly 10 to 50 for common image datasets, not admissible theorem dimensions.
  • Open problems: Whether a universal critical width or matching information-theoretic lower bound exists remains unresolved.The paper presents this as a conceptual implication for future work.

B.4 The main theorem for single-layer compression

Single-layer compression combines derivative matching with rank reduction to obtain a uniformly accurate compressed layer whose width grows polylogarithmically with inverse error.

  • Main theorem: The asymptotically minimal matching order satisfies k⋆ = A/λ + O(log A), where A = log(2C0/εℓ).This yields the stated accuracy-dependent width rate.
  • Assumptions: The proof treats depth L as fixed, allowing suppressed constants in the deep theorem to depend on L.The single-layer construction itself is developed under analytic and weight-bound assumptions.
  • Main theorem: Sequential layer compression preserves a same-depth network with total error controlled by the sum of per-step perturbation budgets.The theorem applies when its assumptions hold at every compression step.

C.1 Forward vs. backward order

Backward compression preserves the original teacher’s analytic constants, whereas forward compression can inflate incoming weights and recursively alter later compression bounds.

  • Backward order: Backward order leaves each layer’s upstream map and incoming weights unchanged when that layer is compressed.This preserves Wmax, Lf, ρσ, and the effective holomorphic radius ρ at the step being processed.
  • Backward order: Backward compression yields predicted widths no larger than the original-network prediction because previously compressed downstream matrices do not increase their row ℓ1-norms.Reweighting bounds control the downstream factors used later.
  • Forward order: Forward order can inflate incoming weights recursively, causing later analytic constants and widths to depend on previous compression steps.The resulting recursion is not solved in the paper.
  • Forward order: Forward-order constants are expected to remain polylogarithmic in 1/ε, but with strictly larger constants than the original-network values.The paper therefore develops its rigorous deep result exclusively in backward order.

C.2 Backward compression error bound

With backward order and a uniform error allocation, the deep theorem gives polylogarithmic retained widths and a polylogarithmic parameter bound for fixed depth and teacher constants.

  • Feasibility: A finite a priori downstream bound Λ makes the uniform per-layer allocation feasible in backward compression.The bound is chosen so that ψ(Λ) ≤ Λ.
  • Error allocation: Uniformly splitting the total error as εt = ε/((L − 1)Λ) preserves the asymptotic width bound up to constants.Any allocation with layer shares within constant multiples of 1/L has the same asymptotic width.
  • Deep theorem: For fixed teacher network and depth, every retained hidden width is O((log(1/ε))^din).The accuracy-driven cap depends on effective input dimension rather than an explicit original-width factor.
  • Parameter count: For fixed L, din, dout, and teacher constants, the total parameter count is bounded polylogarithmically in 1/ε.The explicit dependence on depth is recorded separately in Equation (69).
  • Scope condition: The theorem certifies strict width reduction only when the retained dimension is smaller than the original width.This finite-width condition is made explicit using an admissible effective input dimension m.

D.1 Matching order and realized rank

The analysis distinguishes a finite-scale certification order from the asymptotic matching order and uses realized derivative-feature rank to characterize actual compression. The resulting sufficient width-reduction condition is conservative, while analytic function-class comparisons support the logarithmic exponent without proving a fixed-teacher lower bound.

  • Matching order: kcert ≤ k⋆, with identical asymptotic order but different constant factors, gives a sharper finite-scale certification condition.The explicit condition follows from bounding the derivative-feature dimension by (k + m)^m/m!.
  • Realized rank: The rank-basis construction retains rk neurons, where rk is the realized derivative-feature rank.This rank can be smaller than the ambient derivative-feature count when feature dependencies occur.
  • Strict compression: Condition (74) is sufficient but not necessary for strict compression, because feature dependencies can make rk ≪ D(m)k.When the condition fails, the compression error may still remain safe; only the guaranteed width reduction becomes vacuous.
  • Information-theoretic evidence: The same logarithmic power as the derivative-feature count appears for a canonical analytic function class, indicating that exponent m is natural.This comparison is supporting evidence rather than a compression lower bound for one fixed teacher.

E.2 Metric-entropy

Metric-entropy comparisons connect the retained-width exponent to analytic function classes, while approximation-family analysis explains why fixed-teacher polylogarithmic compression does not contradict classical polynomial rates. The argument also identifies why universal activation-independent lower bounds are unavailable.

  • Metric-entropy: P ≳ [log(1/ε)]^m is suggested by comparing analytic ε-entropy with the covering entropy of P bounded-precision parameters.The comparison is explicitly heuristic and is not an information-theoretic theorem for arbitrary neural parameterizations.
  • Lower-bound scope: No hidden-width lower bound can hold uniformly over all analytic sigmoidal activations, because one particular analytic strictly monotone activation yields dense fixed-width two-hidden-layer networks.A matching lower bound therefore requires restrictions such as a fixed nonpathological activation and quantitative bounds on weights, precision, or parameter stability.
  • Consistency with classical rates: A fixed-teacher polylogarithmic statement does not contradict classical polynomial approximation rates because universal-approximation families change with ε.For such families, finite weight-range assumptions need not hold uniformly, although they naturally hold for each fixed network.
  • Derivative matching: Derivative matching reduces to matching polynomial moments of neuron weights because derivative features are weighted monomials in the weights.This supplies the finite-dimensional structure used by the compression analysis for scalar-output bilayer MLPs.
  • Consistency with classical rates: The accuracy-indexed family cannot keep the outgoing-mass bound uniformly, even though that bound remains finite for each fixed teacher.The retained derivative dimension consequently recovers the classical ε-exponent when teacher-family accuracy dependence is included.

G Experimental details

The experiment compresses frozen three-hidden-layer teachers trained on Sobol inputs and evaluates both task error and teacher–compression fidelity. Diagnostics show that the first layer passes the radius check, whereas the sampled second-layer diagnostic fails for every seed.

  • Training and compression setup: [2, 512, 512, 512, 1] teachers are compressed across all three hidden layers in backward order, with no fine-tuning or post-compression seed selection.Compression is evaluated for k = 0, . . . , 10 using the same Dk across hidden layers.
  • Evaluation: 150,000 held-out Sobol points measure task MSE and the largest teacher–compression discrepancy measures function fidelity.Local projected searches are initialized at the largest sampled discrepancies.
  • Diagnostics: bq2 ≥ 1 for every seed, with first sampled violating radii of (0.300, 0.287, 0.248, 0.290, 0.261).The resulting lower bounds on R/ρ2 are (3.33, 3.48, 4.03, 3.45, 3.83), respectively.
  • Diagnostics: 527,361 original parameters are compressed across three hidden layers; layer 1 passes the radius check, while the sampled layer-2 diagnostic fails for every seed.These are the per-seed diagnostics reported after backward compression.
  • Observed performance: The teachers have median MSE 2.445×10^-4, median width-66 fidelity error 2.305×10^-3, and random-control median 2.60 × 10^-11.Test/train and validation/train ratios remain close to one, with no generalization gap indicative of overfitting.
Loading 2608.21752v1…