acceptodds
Under review as a conference paper at ICLR 2027

Width-Independent Compressibility of Deep Neural Networks

Abstract

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 , where is the error budget and 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.

Primary area:
learning theory
Keywords:
deep learning theory, model compression, moment matching

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_Zb9kOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This manuscript proves that given deep neural network (the teacher network) a smaller network can be found that represents the same function over bounded input. The strategy is to match derivatives at intermediate layers and leverage, essentially, Taylor approximations using those matched derivatives.

Critical strengths

The manuscripts main theoretical contributions seem sound and may be useful to understand, broadly, certain behavior of such models. Moreover, the core derivative matching idea is interesting and clearly workable, if not practical at scale.

Critical weaknesses

I think the theoretical developments here are fine and the derivative matching approach is, to the best of my knowledge, novel in this context. However, I do not really feel there is a substantiate contribution in the overall narrative of the manuscript. This is due to a few factors.

Given the relative complexity and looseness of the theoretical claims and number of "hidden" dependencies it is not clear to me how descriptive or insightful the results are. While some suggestions are made in the manuscript I don't think the connections are sufficiently supported by the results as presented (perhaps via intermediary results in the appendix?)

For example, I think the manuscript oversells its "width independence" claim. In fact, it is not even clear what this means given the implicit dependence on the teacher network. The relevant properties presumably depend on the underlying architecture, data, and training process. How they all factor in is opaque at best.

Building on this point, while there seems to be a discussion in the appendix showing that there are regimes where the bounds are not vacuous it is not clear how common this is. For example, is there any hope (omitting the restriction on activation functions away from ReLU) for anything non-vacuous on any "real world" model? Notably, even the very restricted networks used for numerical experiments simply show the derivative matching scheme is workable at small scale and not that the resulting model is close to a theoretical bound (i.e., there are no bounds to compare with in Fig. 1).

The above critique could be mollified by a practical algorithm. And, perhaps, it is remarkable that the construction from the proof is workable at all (though framed as derivative matching for Taylor approximations it is less surprising). However, as the manuscript notes, the scheme is not particularly scalable.

In summary, on the theoretical front (which is the claimed contribution) I find the manuscript lacking in insight. Importantly, it never satisfactorily answers the question: why is this specific theoretical result interesting.

Questions for authors
  • What does it mean for dind_{in} to be O(1)\mathcal{O}(1) in this context? For big-O notation to make sense there needs to be a natural parameter that is being scaled. E.g., in eq. (2) it could be ϵ\epsilon or din.d_{in}. Is this just supposed to suggest that dind_{in} is some small constant much less than the intermediary sizes? If F is fixed then so is din.d_{in}.

  • Is there any regime where the bounds are informative enough to be compared with experiments?

1 comment

Thank you for the careful report. Short answers first:

  • Why is the result interesting? The true value of our construction is a surprising proof, not a practical algorithm.
  • Can the bounds be compared with experiments (Q2)? Yes (point 2; new Appendix I).
  • "Width independence" is oversold. We were unclear: Remark 7 states it at fixed weight norms, but not prominently enough (point 3).

1. Why is this specific theoretical result interesting?

Our contribution is theoretical, and we believe it is a large step. Previous works mostly report empirical pruning by a constant fraction, say 90% (Section 3); previous theoretical bounds are limited in scope. Very few works anticipated that a network can be compressed to a vanishing fraction of its original width. We prove that it can: polylog(1/ε)\mathrm{polylog}(1/\varepsilon) neurons per hidden layer suffice. This is the true value of our derivative-matching construction: a surprising proof, not a practical algorithm. This is pointed out in Sections 3 and 6.

We agree that our algorithm is not practical as-is when dind_{in} is large. This is not a peculiarity of our construction but an information-theoretic limit: the Kolmogorov widths of analytic function classes grow in the same way, as [log⁡(1/ε)]din[\log(1/\varepsilon)]^{d_{in}} (Appendix E).

2. "There are no bounds to compare with in Fig. 1" (Q2).

This was a gap in our presentation. In Fig. 1(a) ([3,2048,2048][3,2048,2048], default initialization) the first-layer row norms are at most 1 and the outgoing norms at most 2048\sqrt{2048}. The certified error ratio per step ek+1/eke_{k+1}/e_k asymptotically equals R/πR/\pi by Theorem 5. The submitted bound gives:

input radius RR0.30.5124
certified width, ε=10−3\varepsilon=10^{-3} (of 2048)1202861330vacuousnot covered
certified error ratio per step (Theorem 5)0.0950.1590.3180.637—
measured error ratio per step0.0600.0800.1700.3100.511

Reading. Non-vacuous for R≤1R\le1; the measured decay is geometric, as predicted, and faster than certified at every covered radius. The sigmoid-specific corollary we add (Appendix H) even covers R=4R=4 (reply to Ydfw, Q2). "Vacuous" means the certified width exceeds the original 2048.

More tests (new Appendix I.1–I.2). On 36 networks that satisfies all of assumptions 1-4 (one or three hidden layers, untrained and trained), the error bound is never exceeded; the certified width is at the order of 10 times the width needed numerically.

Action. Certified and measured ratios tabulated in the new Appendix I.4; tests in I.1–I.2.

3. Overselling of "width independence"; "hidden" dependencies.

"Width-independent" means independent of the widths at fixed weight norms. The submission states this in Section 2, Remark 7, but not prominently enough: the abstract and introduction leave it unclear. We keep the title, where "width-independent" carries this meaning, and state it explicitly at first use in both the abstract and the introduction. The certificate depends on the teacher only through the input radius and the row norms of its weights, so it holds uniformly over all networks with bounded row norms, of any width.

If one naively assumes each neuron's weight to be of order 1, then the ℓ1\ell_1 norm grows with width. But in actual cases, whether norms stay bounded as width grows depends on normalization and training; in practice they usually do, because of the weight regularization typically used in training. This is discussed in Appendix F.

4. How common is the non-vacuous regime? Any hope for "real world" models?

It is narrow, because real-world models (especially generative AIs) usually have a large input dimension. Unless we find a small bottleneck dimension, in the data or in the network (reply to Ydfw, Q4), our compression is not applicable as-is. Our Section 6 explicitly says so.

5. What does din=O(1)d_{in}=O(1) mean? (Q1)

Only that dind_{in} is a small fixed integer. You are right that for a fixed teacher dind_{in} is not scaled; our wording was imprecise. We replace it by "dind_{in} is a fixed integer with din≪dℓd_{in}\ll d_\ell".

Reviewer_YdfwOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposes a derivative-matching approach to compressing deep MLPs with analytic activation functions. By matching input derivatives up to order (k) and applying rank reduction, the authors establish a uniform approximation guarantee with retained width O((log⁡(1/ϵ))din)O((\log(1/\epsilon))^{d_{\mathrm{in}}}), without explicit dependence on the original hidden width for a fixed teacher network. The paper extends the construction to deep networks and presents experiments demonstrating substantial compression.

Critical strengths
  • Extends width-independent compression from shallow networks to arbitrary-depth MLPs through derivative matching and backward layer-wise compression.

  • Provides a theoretically grounded bound on approximation error over a bounded input domain.

  • The discussion of teacher-dependent norms and classical approximation rates helps clarify the scope of the width-independence result.

  • Reports substantial parameter reductions, including on trained sigmoid networks without fine-tuning.

Critical weaknesses
  • The feature count (Dk=(din+kdin))(D_k=\binom{d_{\mathrm{in}}+k}{d_{\mathrm{in}}}) grows rapidly with input dimension and derivative order, potentially making the bound impractical beyond low-dimensional settings.

  • The analyticity-radius condition is violated at Layer 2 for the reported trained-network experiments. Consequently, the theorem does not directly guarantee the observed empirical performance.

  • The theoretical norm-inflation guarantee relies on maximum-volume selection, while the practical implementation uses pivoted QR. The guarantees for the practical alternative are unclear.

  • Experiments focus on low-dimensional networks, leaving scalability and applicability to more realistic settings uncertain.

Questions for authors
  1. What norm-inflation guarantees hold for the practical pivoted-QR implementation, and how do they affect the final approximation bound?

  2. Why does compression remain effective when the analyticity-radius condition is violated in the trained-network experiments?

  3. How do the teacher-dependent constants scale with network depth and weight norms?

  4. Can the method be extended or adapted to higher-dimensional inputs?

1 comment

Thank you for the careful report. Short answers first:

  • Q1. No, but in all our experiments it meets the certified bounds.
  • Q2. The radius condition is sufficient, not necessary. A new corollary removes it for sigmoid.
  • Q3. The outgoing norm enters through a logarithm; depth enters by splitting the error budget across layers.
  • Q4. Yes for small effective input dimension, no for isotropic high-dimensional inputs.

Q1 (W3). Norm-inflation guarantees for pivoted QR.

We first recall the aim of the paper: to prove how much networks can be compressed, not to propose a new practical compression algorithm, although that is an important future direction (Section 6). We use maxvol selection to prove that a suitable compression exists; to demonstrate the theory numerically, we use the much more efficient pivoted QR instead.

With pivoted QR, the outgoing norm Vmax⁡V_{\max} can, in the worst case, inflate too much for the a-priori bound to be useful. Empirically, however, pivoted QR meets our certified error bounds: all our numerical demonstrations use it, and they validate the theory. We therefore take no action on this point.

Q2 (W2). Why compression works beyond the radius condition.

Our theory gives an upper bound on the compression error, so measured errors well below the certified bound are expected. The radius condition (Assumption 4) is a sufficient condition for this bound, not a necessary condition for compression to work.

However, for sigmoid we found a concrete reason why compression works beyond this condition. The new Appendix H (Corollary 25) replaces the disc of Theorem 5 by a strip around the real axis, on which every sigmoid neuron is analytic and bounded. The strip has no radius limit, so the certified error decays geometrically in kk at every input radius RR. For the network of Fig. 1(a), whose first-layer rows have norm at most 1, the error ratio per step ek+1/eke_{k+1}/e_k is:

input radius RR0.30.5124
measured0.0600.0800.1700.3100.511
certified by Corollary 25, tanh⁡(R/4)\tanh(R/4)0.0750.1240.2450.4620.762
certified by Theorem 5, R/πR/\pi0.0950.1590.3180.637—

The certified ratios are the limits as k→∞k\to\infty (Appendix I.4). Theorem 5 does not apply at R=4>πR=4>\pi, but Corollary 25 does.

As a remark, GELU, the other activation in Fig. 1, is holomorphic. It follows that Theorem 5 already gives exponential decay in kk for any RR.

Q3. Scaling of the constants with depth and weight norms.

Disclaimer: our paper concerns one particular teacher network, rather than a family of networks sending any quantity to infinity. Below, we only discuss how the error bound in the form of Theorem 6 scales with depth and Vmax⁡V_{\max} as they go to infinity.

In Eq. (21), C0∝Vmax⁡C_0 \propto V_{\max}, so the dependence of the certified width on Vmax⁡V_{\max} reads D=O((log⁡(1/ε)+12log⁡d)din)D = O((\log(1/\varepsilon)+\tfrac12\log d)^{d_{in}}).

Depth weighs in through splitting the error budget across layers, which means one simply replaces the ε\varepsilon in Theorem 6 by εℓ∝ε/(L−1)\varepsilon_\ell\propto \varepsilon/(L-1). The downstream Lipschitz factor Λˉ\bar{\Lambda} depends on the entire teacher network, which could possibly scale with depth but is largely case dependent. This is explained in Section 5, and Appendix C in detail.

Q4 (W1, W4). Higher-dimensional inputs.

(i) Low effective dimension: yes. If the data have an exact mm-dimensional analytic parameterization, or the network has a width-mm bottleneck, dind_{in} is replaced by mm (the two corollaries after Theorem 6).

(ii) Isotropic high-dimensional inputs: no. The growth of DkD_k is not a peculiarity of our construction: it reflects an information-theoretic limit for analytic function classes, whose Kolmogorov widths grow in the same way, as [log⁡(1/ε)]din[\log(1/\varepsilon)]^{d_{in}} (Appendix E; reply to Zb9k). We therefore claim no certificate there, and the revision says so in the main text.

Reviewer_hTW4OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies the compression of a fixed deep network with analytic activations, while preserving its depth and uniformly controlling the error over a bounded input domain. The method selects neurons from the initial network and recalculates their output weights to preserve the derivatives of the function with respect to the input up to a given order. Analyticity then allows the approximation error to be bounded. The authors compose these compressions from the last hidden layer to the first, while controlling the amplification of errors.

Under the assumptions of the paper, for a fixed input dimension and fixed network constants, the chosen width is bounded by �0��0�. This bound does not contain any additional explicit factor for the initial width, but its constants depend on the specific network under consideration.

Experiments on sigmoid and GELU random networks illustrate the construction and the decrease in error with the order of the derivatives.

Critical strengths

1. A structured and relevant approach

The number of features to be preserved depends on the input dimension and the order of derivatives. This allows for the handling of intermediate layers with wide neighboring layers. The approach preserves depth an uses neurons from the initial network.

1. A rigorous and clearly presented mathematical analysis.

The authors take into account the increase in weights after reweighting and how that affects the error propagation. The order of the backward compression order allows these interactions to be controlled. The central arguments examined are consistent under the formal assumptions. I have not identified any major mathematical errors.

Critical weaknesses

1. The quantitative utility of the certificate remains unproven.

The paper does not clearly present an exemple in which the evaluation of the constants certifies strict deep compression. The post-training experiments are encouraging, but the five corresponding networks violate Hypothesis 4. They show that the construction can work outside the guaranteed domain, without establishing the certificate’s utility in such cases.

2. Width independence remains conditional.

The constants depend on the weight and analytical properties of the initial network. They may therefore vary as the width increases. The authors acknowledge this limitation but its quantitative implications should be made more explicit to assess the scope of the claimed contribution.

These remarks are only about the importance of the results. My recommendation is weak rejection, but a convincing clarification of their scope and quantitative value could lead me to change my mark.

Questions for authors
  1. Can you provide an example that satisfies the assumptions, where the constants are evaluated and the certified width is actually less than the initial width This would help us understand when the guarantee provides useful compression.

  2. For explicit normalization of the weights, can you specify how the certified width changes as the initial width increases, taking into account the network-dependent constants ? This would help assess the exact extent of the independence from width.

A clarification based on the existing analysis may be sufficient to answer my questions.

2 comments

Thank you for the careful report. Short answers first:

  • Q1. Yes: compressible to a finite (91) width for an explicit norm-bounded class of networks, whatever its width; hidden widths [136,210,253][136,210,253] for a three-hidden-layer class.
  • Q2. One hidden layer: the certified width is constant in the original width under mean-field scaling, and grows like a power of log⁡d\log d under standard scaling. Note: our paper concerns one particular teacher network, rather than a family of networks sending dd to infinity; but if it has to be applied to a family, the "standard" scaling violates Assumption 3 so is out of our scope, whereas the "mean-field" scaling does not.
  • Scope. The revision adds trained networks inside the certified regime (new Appendix I).

Q1. An evaluated example with certified width below the original.

One hidden layer. Every sigmoid network on the unit disk (din=2d_{in}=2) with first-layer row norms at most 1 and outgoing ℓ1\ell_1 norm at most 1, of any width and with any biases, is certified compressible to 91 neurons at sup-error 10−310^{-3} (sharper bound, Eq. (71); constants in Appendix D).

Three hidden layers (any widths; first-layer row norms at most 12\tfrac12, later rows of ℓ1\ell_1 norm at most 4): certified hidden widths [136,210,253][136,210,253] at total sup-error 10−310^{-3} (Theorem 16; Appendix D), 6.4× fewer parameters than the original [2,512,512,512,1][2,512,512,512,1] network.

Tests of the above claims. Every compression at a certified width met its target, on synthetic class members and on [2,4096,1][2,4096,1] networks trained with first-layer norms held at most 1 (certified 153 neurons, but 21–28 suffice). The certificate is conservative, by a factor of about 5 to 35.

Action. New subsection of Appendix D with the above examples. The tests are in the new Appendix I.

Q2. Certified width versus original width.

For the one-hidden-layer class above and ε=10−3\varepsilon=10^{-3}, our theory gives the following certified widths:

original width dd2102^{10}2142^{14}2202^{20}2302^{30}
mean-field, ∑i∣vi∣≤1\sum_i\lvert v_i\rvert\le191919191
standard, ∣vi∣≤d−1/2\lvert v_i\rvert\le d^{-1/2}153171210300

Reading. Width independence is conditional, but the width enters only through log⁡Vmax⁡\log V_{\max} (Theorem 6), which is 12log⁡d\tfrac12\log d under standard scaling, so the certified width grows like (log⁡(1/ε)+12log⁡d)din(\log(1/\varepsilon)+\tfrac12\log d)^{d_{in}}. The same holds for deep networks with bounded row ℓ1\ell_1 norms.

Action. The above numerical findings are recorded in detail in the new Appendix I.3 and Fig. 5.

Thank you for this clear and precise response. The examples in which the constants are explicitly evaluated and where the certified width is significantly smaller than the initial width, as well as the table showing the effect of weight normalization, answer both of my questions. The addition of trained networks that satisfy the assumptions also shows that the certificate can be applied in practice, even if it remains conservative.

As mentioned in my review, these clarifications address my main reservations about the scope of the result. However, the examples remain limited to low-dimensional input spaces, which seems to be a natural limitation of the approach. I am therefore raising my rating to 3 (weak acceptance)

Comments on the paper

1 comment
AuthorsOpenReview ↗

Why it matters + summary of changes

We thank all the reviewers for their careful reports.


What the paper shows and why it matters

The result. A wide MLP with analytic activations contains a same-depth network with O(log⁡din(1/ε))O(\log^{d_{in}}(1/\varepsilon)) neurons per hidden layer that matches it to sup-error ε\varepsilon on a bounded input domain.

It matters as we identify it as a surprising step in compression theory. Previous works mostly report empirically that networks can be pruned by a constant fraction, and previous theoretical bounds are mostly niche. Very few works anticipated that a network can be compressed to a vanishing fraction of its original width. We prove that it can: at fixed weight norms, polylog(1/ε)\mathrm{polylog}(1/\varepsilon) neurons per hidden layer suffice.


Changes to the manuscript

  1. We updated the "main idea" sentence in Introduction, to better concede with the revisions, especially to specify what we mean by "width-independent compressibility":
At fixed weight norms and a given accuracy, a wide network is no more expressive than a narrow one. Its expressiveness is set by the input dimension, rather than the width.
  1. Worked examples (new Appendix D.3): two explicit classes of sigmoid networks, defined only by bounds on their weight norms, are certified compressible to 91 neurons (one hidden layer) and to hidden widths [136,210,253][136,210,253] (three hidden layers) at sup-error 10−310^{-3}, whatever the original width.
  2. Sigmoid networks beyond Assumption 4 (new Appendix H): the certified error decays geometrically in kk at every input radius, so the radius condition is not needed.
  3. Experiments validating the bounds (new Appendix I): the certified bounds are compared with measured errors on various network setups allowed by our assumptions.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.