- Rating
- 3
- Confidence
- 3(+1)
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
The paper studies how repeated computation (looping) can substitute for stored parameters in looped ReLU networks. The model has J separately stored modules evaluated through T total calls (1 <= J <= T). Each module size depends only on the input dimension d, not on J, T or the target accuracy, and the call sequence is fixed independently of the input and the target. The target class is bounded unit-Lipschitz functions on [0,1]^d.
The paper makes in my understanding three contributions.
-
Storage-computation frontier (Theorem 1). For multi-stage networks, where each module is called in one contiguous stage, the optimal worst-case error is of order (JT)^{-1/d}, with matching upper and lower bounds for every 1 <= J <= T. The product JT acts as the effective budget, so a network can store fewer modules if it makes proportionally more calls. This recovers results from previous works: the T^{-1/d} rate of a single repeated module (J = 1) and the T^{-2/d} rate of untied deep ReLU networks (J = T).
-
Effect of call order (Theorem 2). For any prescribed call sequence, including returns to earlier modules, the error is bounded above and below by two quantities of the so-called "access curve," which counts the distinct modules reached by each call: its largest right-aligned rectangle H and its total area W. The frontier is retained if and only if a constant fraction of the calls remains after a constant fraction of the modules has been visited. Balanced grouped calls and repeated cycles both meet this condition. Two sequences with identical per-module call counts can still attain different rates.
-
Extensions. The results extend to finite L^p error and to Holder targets. For bit-limited descriptions with I bits, extra calls stop helping once the available target information is used up.
The validation is purely theoretical. The appendix gives full proofs for results. There are no experiments. The authors state that the results concern best approximation under exact arithmetic and say nothing about trainability or how trained networks behave, or what happens under finite-precision execution.
I am not an expert in approximation theory for neural networks or in VC-dimension techniques. I read the paper carefully and could follow the main arguments and the proof sketches in Sections 4.1 and 5.1, but I did not check the appendix proofs in detail. Please weigh my assessment accordingly. Several of my comments below are questions, not firm criticisms. My poor knowledge of this literature also make difficult for me to assess if the results are really "new" and if the related work section covers correctly the field.
Critical strengths
Critrical strengths
-
Sharp, matching bounds that unify known results. Theorem 1 gives upper and lower bounds of the same order for every combination of stored modules and calls. Both known endpoints are special cases: a single repeated module and fully untied deep ReLU networks. This weighs in my assessment because the common intuition that loops trade parameters for compute becomes a precise statement. In this model, the budget that matters is the product of the number of stored modules and the number of calls, so fewer modules can be compensated by proportionally more calls (at least under the assumptions they made).
-
A simple, new criterion for call order. Theorem 2 shows that, once the number of modules and calls is fixed, the approximation rate depends on when each module is first reached. The authors capture this with the access curve and two area quantities. The frontier is retained if and only if a constant fraction of the calls remains after a constant fraction of the modules has been visited, which seems easy to check for a given sequence. The sigma_A vs sigma_B example shows that two sequences with identical per-module call counts can reach different rates. I find this the most original part of the paper. It relates to choices practitioners can make, such as grouped vs interleaved calls or where to place the loop.
The figures make both results accessible. They are of very good quality in the sense of transmitting their message. Figure 1 is very pedagogical and shows the model and its two “extreme” endpoints, and Figures 3 and 6 make the access curve and its area quantities intuitive. Is space allowed, i would have prefered to see figure 6 in the main text. As a non-expert, I found the paper much easier to follow because of them. My one reservation is that the colours are not colour-blind friendly. The legends and line styles partly compensate, but a colour-blind-safe palette would improve them further.
Critical weaknesses
I take here the time to restate that my points are more questions than real weaknesses. If i’m wrong in any sense, please take time to correct me.
-
The frontier counts real-valued parameters, not stored information, and the paper does not make this visible enough. The upper-bound construction stores a long sequence of digits in a single real coefficient per block, and the repeated calls mostly read these digits out one at a time.
Appendix D shows what happens when the weights can only be described with a finite number of bits. Extra calls stop helping once the available bits are used up, and to retain the frontier each module then needs a description that grows with the number of calls. If I read this correctly, loops can replace parameters but not stored information. This is consequential because the title asks how much loops can replace parameters, and a reader could take the answer to mean that computation substitutes for storage in a practical sense. I would like it stated in the introduction or right after Theorem 1. I see this mainly as a presentation issue, and it is the main reason my score is not higher.
-
The results assume exact arithmetic with unrestricted coefficient magnitude and precision, and several fixed coefficients in the construction grow with the resolution. The authors say plainly that the bounds do not show that training can find such weights, or that they hold under finite-precision execution. There is also no experiment, even a toy one, to check whether the call-order effect has a counterpart in trained networks. This matters to me because the motivation draws heavily on practical architectures (recurrent-depth language models, grouped vs interleaved calls), and the call-order criterion is the part most likely to interest that audience. For now, its relevance to those architectures remains a hypothesis. For a theory paper I do not consider this disqualifying, which is why I still recommend acceptance, but a short toy experiments in the main could help to understand how practical/mature this theory already is.
Questions for authors
- Clarification: How large do the coefficients in the Theorem 1 construction become as functions of J, T and d, and how many bits per module are needed to reach the (JT)^{-1/d} rate? If Appendix D implies that no construction with a T-independent bit budget per module can achieve the frontier, could you say so in the main text, for example right after Theorem 1?
- Suggestion: Have you tried even a small experiment, such as training looped ReLU networks on a low-dimensional Lipschitz target under the sigma_A and sigma_B call orders, to see whether the predicted rate gap appears after training? A positive or negative result would help me judge how far the call-order criterion is relevant beyond best approximation.
12 comments
Response (Part 2)
C2
Weaknesses (W2): The results assume exact arithmetic with unrestricted coefficient magnitude and precision, and several fixed coefficients in the construction grow with the resolution. The authors say plainly that the bounds do not show that training can find such weights, or that they hold under finite-precision execution.
Question: How large do the coefficients in the Theorem 1 construction become as functions of J, T and d, and how many bits per module are needed to reach the rate? If Appendix D implies that no construction with a T-independent bit budget per module can achieve the frontier, could you say so in the main text, for example right after Theorem 1?
Response. The coefficient bounds, storage requirements, and training question concern different aspects of the result. We address them separately below.
-
Best approximation and training. Our construction proves that networks attaining the upper bound exist. The matching lower bound establishes the optimal approximation order within the admissible class. Whether training finds comparably accurate networks is a separate question, which motivates the paired experiment in C3.
-
Coefficient magnitude. After normalization and layer assembly, all coefficients are rational and have magnitude at most for every , with and depending only on . For example, the slope used to select a coarse block before normalization is bounded by (revised Appendix B.2.3, Proposition 7).
-
Bits to store a module.
-
Sufficient bits for our construction. Within each module, the target-independent coefficients require bits in total, while the target-dependent codes require bits. Thus our exact encoding stores the complete module using bits (revised Appendix B.2.3, Proposition 7).
-
A necessary condition for any construction. If a common cap of bits selects the weights of each module and end map from a fixed codebook, the entire network has at most bits of target information. Attaining the frontier requires bits, so the common cap must be . Consequently, no construction under a -independent common cap can retain the frontier as grows (submitted Appendix D.2).
-
-
Precision during evaluation. The exact-arithmetic construction can also be evaluated with rounding if the precision grows with the call budget. Storing the coefficients accurately is not sufficient by itself: rounding errors must also be controlled as the state passes through repeated calls. Under the specified fixed-point or binary floating-point rules, with state projection after initialization and each module call, bits per scalar suffice to preserve the construction’s approximation order (revised Appendix D.4, Proposition 23).
The revision states the necessary growth of the per-component bit budget immediately after Theorem 1 (pp. 5–6). Appendix B.2.3 gives the coefficient and storage bounds, and Appendix D.4 establishes the rounded execution guarantee. The paired training comparison is reported in Appendix E and discussed in C3 below.
Response (Part 3)
C3
Weaknesses (W2): There is also no experiment, even a toy one, to check whether the call-order effect has a counterpart in trained networks. This matters to me because the motivation draws heavily on practical architectures (recurrent-depth language models, grouped vs interleaved calls), and the call-order criterion is the part most likely to interest that audience. For now, its relevance to those architectures remains a hypothesis.
Question: Have you tried even a small experiment, such as training looped ReLU networks on a low-dimensional Lipschitz target under the sigma_A and sigma_B call orders, to see whether the predicted rate gap appears after training? A positive or negative result would help me judge how far the call-order criterion is relevant beyond best approximation.
Response. To examine whether the call-order effect also appears in trained networks, we added a paired experiment (revised Appendix E, pp. 49–50). Across all six settings, (earlier-access order) had lower mean test-grid errors, which is consistent with the direction of Theorem 2’s comparison.
-
We trained both orders on the same data with identical initial weights, parameter counts, and per-module call counts. The extra calls to occur before visiting the other modules in and after in . We used three budgets each in 2D and 3D with Lipschitz targets built from 100 localized pyramids with random signed heights. We calibrated the scale of the 2D targets using the test function in Zhang et al. (2023, sec. 4.1).
-
The table reports mean errors over three targets and five training seeds per target, in units of . Bold indicates the lower mean within each pair of call orders. Maximum error is computed per fit and then averaged.
| Train RMSE | Train RMSE | Train Max. error | Train Max. error | Test RMSE | Test RMSE | Test Max. error | Test Max. error | ||
|---|---|---|---|---|---|---|---|---|---|
| 2 | 6.567 | 6.175 | 33.965 | 30.348 | 6.787 | 6.413 | 38.612 | 34.762 | |
| 2 | 6.144 | 5.461 | 32.341 | 28.733 | 6.430 | 5.773 | 36.761 | 33.427 | |
| 2 | 5.677 | 5.131 | 29.051 | 27.175 | 5.982 | 5.475 | 34.579 | 32.578 | |
| 3 | 5.962 | 5.489 | 30.526 | 29.924 | 7.090 | 6.619 | 44.005 | 43.332 | |
| 3 | 5.440 | 4.961 | 30.627 | 28.247 | 6.743 | 6.225 | 43.140 | 40.762 | |
| 3 | 5.336 | 4.973 | 30.325 | 29.217 | 6.705 | 6.238 | 42.956 | 41.729 |
Across the six settings, reduced mean test-grid RMSE by 5.5–10.2% and mean test-grid maximum absolute error by 1.5–10.0%. The lower mean errors for the earlier-access order are consistent with the direction of Theorem 2’s comparison.
The code and saved results are available in the anonymous repository.
C4
Suggestions in Critical Strengths: Is space allowed, i would have prefered to see figure 6 in the main text. [...] My one reservation is that the colours are not colour-blind friendly. The legends and line styles partly compensate, but a colour-blind-safe palette would improve them further.
Response. We moved the two panels from the submitted Figure 6 that compare orders with identical per-module call counts into the main text, next to the example they illustrate (revised Figure 4, p. 9). The complete four-panel comparison, including grouped and cyclic calls, remains in Appendix C.3 (revised Figure 7, p. 38).
We replaced the blue–teal shading with blue and rose in the access-curve figures. The rectangle for is hatched and labeled, and is identified as the full area under the curve. These cues keep the two quantities distinguishable in grayscale.
References
- D. Yarotsky. (2018). Optimal Approximation of Continuous Functions by Very Deep ReLU Networks. COLT.
- S. Zhang, J. Lu, and H. Zhao. (2023). On Enhancing Expressive Power via Compositions of Single Fixed-Size ReLU Network. ICML.
Response (Part 1)
We thank the reviewer for the time and effort devoted to reviewing our work. We appreciate the recognition that the joint frontier makes the parameter–computation tradeoff precise, and the positive assessment of the call-order criterion and the illustrations. We address the questions point by point below, with clearer statements of the storage and precision requirements and a new training comparison motivated by the reviewer’s suggestion.
Response. We agree that fewer stored weights need not mean fewer stored bits, and that this distinction should be clear when introducing parameter storage. The title refers to parameter counts under the real-parameter, exact-arithmetic convention of quantitative ReLU approximation (Yarotsky 2018; Zhang et al. 2023).
What loops replace. Additional calls can compensate for fewer stored modules while preserving the best worst-case approximation order. Our encoding–decoding construction provides one way to attain this tradeoff. The matching lower bound shows that no other encoding or construction can improve the worst-case approximation order under the same module-size bounds, stored-module budget, and call budget.
What the submitted bit-budget result establishes. The reviewer's reading of Appendix D is correct. With I bits available to specify the target-dependent weights and a fixed module count J, extra calls improve the error order until JT reaches the scale of I. Beyond that point, the weight description limits the error order (Corollary 17, Eq. (38), p. 38). To attain the full frontier, the common bit cap for selecting each component's weights from its codebook must be at least of order T (Theorem 18, Eq. (40), and Section D.2.4, p. 40).
What this means for actual storage. To quantify the storage cost, we additionally count the total budget S for storing the full coefficient arrays. Under the specified encoding and exact evaluation, the best worst-case error is of order [1+min(S,JT)]−1/d for 1≤J≤T and S≥CdJ (revised Appendix D.1.1, Proposition 19, p. 44). A storage budget of order JT bits is necessary and sufficient to attain the full frontier. At fixed JT, fewer modules and more calls preserve the approximation order, but also preserve the order of the required stored-bit budget.
We now explain the weight-count convention in the introduction (revised p. 1) and state the bit-storage result and per-component description requirement after Theorem 1 (revised pp. 5--6).