acceptodds
Under review as a conference paper at ICLR 2027

Arbitrary-Accuracy Neural Approximation with Optimal Neuron Count and Near-Optimal Bit Complexity

Abstract

We study the minimum number of hidden neurons required for arbitrary-accuracy approximation of multivariate Hölder-continuous functions on and the associated encoding complexity. For , we construct a fixed, explicitly defined activation function for which a closed-form network with two hidden layers of widths and achieves arbitrary accuracy in the uniform norm. We prove that is the exact minimum total number of hidden neurons among standard feedforward networks with locally integrable activations and affine outputs. We further give a simpler construction using a single elementary activation that combines the floor and exponential functions. This construction requires three hidden layers of widths , , and , only two neurons above the minimum. If a skip connection is allowed, widths , , and suffice. These constructions use explicit grid addressing and integer encoding of quantized function values. For a bounded -Hölder class, the target-dependent encoding requires bits, matching the metric-entropy lower bound up to a logarithmic factor.

Primary area:
learning theory
Keywords:
Universal approximation, optimal neuron count, bit complexity, superexpressive activation functions, Hölder-continuous functions.

Reviews

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

This paper considers the construction of finite size neural networks which are dense in the space of continuous functions. This is possible because such networks parameterize space-filling curves (the parameterization is not necessarily continuous). An interesting question is the minimal size of such a super expressive network. The authors present a novel construction which is optimal under certain restrictions. They also consider the bit complexity of representing a function, i.e., how many bits do they need to encode each parameter to the accuracy required for their construction to work.

Critical strengths

The results presented are novel, interesting, and correct. It is very interesting that finite-size neural networks are already dense in the space of continuous functions.

The constructions given in the paper are provably optimal in the given setting.

Critical weaknesses

The activation functions considered are very far from practical implementations of neural networks. In particular, they are discontinuous and a network with such an activation function cannot be trained.

Super-expressive networks are interesting from a theoretical point of view, however they shed no light on the behavior of practical neural networks. Of course, this is not the point of the paper, but it is a weakness since the paper will only appeal to a specialized audience as a result.

Questions for authors

Since the space of H"older continuous functions is dense in CC (the space of continuous functions), by scaling it follows that Definition 2.1 is equivalent to density in CC. I would recommend presenting it this way. Why do you introduce the balls in the H"older spaces? Is it simply to make the proofs easier? I think that the arguments can be made in a more transparent way using the modulus of continuity.

Also, Theorem 3.1 is more naturally stated in terms in density in CC in my opinion. I believe you only need to consider H"older continuity in your estimates of the number of bits required. However, this can also be generalized using the modulus of smoothness. These remarks are not necessary but may improve the presentation.

Do you have any results when the output dimension is greater than 1?

2 comments

We thank the reviewer for the insightful suggestions. The sections, theorems, tables and figures mentioned below refer to the revised manuscript, in which all revisions are marked in blue.

Continuous functions and Hölder balls

Following your suggestion, all results on the neuron count are now stated for continuous functions. Universality is defined as density in C([0,1]d)C([0,1]^d) (Definition 2.1). Theorems 3.1 and 4.1 now hold for every f∈C([0,1]d)f\in C([0,1]^d), with the grid size MM chosen through the modulus of continuity of ff in (5), and Theorem 3.4 shows that, for d≥2d\ge2, no network with at most dd hidden neurons is universal. The lower bound is not affected, because the counterexamples that we use to prove that networks with fewer than d+1d+1 neurons are not universal lie in a Hölder ball and are therefore continuous. Your suggestion extends the scope of our results and makes the paper clearer. Thank you very much.

We keep the Hölder balls only for the bit complexity. A worst-case bit count needs a compact class: on the unit ball of C([0,1]d)C([0,1]^d), no fixed architecture reaches accuracy ε<1/2\varepsilon\lt 1/2 with a bounded number of bits. We choose the Hölder balls because they are compact and their ε\varepsilon-entropy is known [2], so that our bit complexity can be compared with the optimal one; in addition, our optimality in bit complexity is restricted to the Hölder balls. In detail:

  1. The bit complexity of our networks can be extended to continuous functions by bounding their modulus of continuity by a fixed concave ω\omega. The newly constructed network Φf,εϱ~\Phi_{f,\varepsilon}^{\widetilde\varrho} (Section 3.1.2) then needs Θ(ω−1(ε/2)−d)\Theta\bigl(\omega^{-1}(\varepsilon/2)^{-d}\bigr) bits, whereas the ε\varepsilon-entropy of this class is of order ω−1(2ε)−d\omega^{-1}(2\varepsilon)^{-d} [1]. Hence its bit complexity matches the ε\varepsilon-entropy when ω−1(2ε)/ω−1(ε/2)\omega^{-1}(2\varepsilon)/\omega^{-1}(\varepsilon/2) stays bounded, as for the Hölder modulus ω(t)=λtα\omega(t)=\lambda t^\alpha, and the network is not optimal when this ratio is unbounded, e.g., for ω(t)=1/log⁡(1/t)\omega(t)=1/\log(1/t). The same applies to the other three networks in the original manuscript, up to a logarithmic factor.
  2. Our networks are constant on each cell QℓQ_\ell (Figure 1b) and do not use a local Taylor expansion. For smoothness s>1s\gt 1 they therefore need Ω(ε−d)\Omega(\varepsilon^{-d}) bits, or Ω(ε−dlog⁡(1/ε))\Omega(\varepsilon^{-d}\log(1/\varepsilon)) bits for the networks in the original manuscript, whereas the ε\varepsilon-entropy is only O(ε−d/s)O(\varepsilon^{-d/s}) [2], so they are neither optimal nor near-optimal.

We have added Remark 5.3 on this limitation of our optimality claim, and we list the case s>1s\gt 1 in Section 7 as an open problem.

Extension to vector-valued functions

Thank you for the question on output dimensions greater than 11, which inspired a new part of the paper (Remark 4.2 and Appendix F). We now prove that, for input dimension d≥2d\ge2 and output dimension doutd_{\mathrm{out}}, the minimal number of hidden neurons among networks without skip connections is d+doutd+d_{\mathrm{out}} (Theorem F.4).

All four networks of the main text extend to doutd_{\mathrm{out}} outputs with the same activations (Propositions F.1 and F.2):

  • Φϱ\Phi^{\varrho}, the (d+1)(d+1)-neuron network with digit extraction, needs d+doutd+d_{\mathrm{out}} hidden neurons;
  • Φϱ~\Phi^{\widetilde\varrho}, the (d+1)(d+1)-neuron network with tree difference encoding, which is new in this revision, also needs d+doutd+d_{\mathrm{out}};
  • Φσ\Phi^{\sigma}, with the elementary activation, needs d+dout+2d+d_{\mathrm{out}}+2;
  • Φσ,skip\Phi^{\sigma,\mathrm{skip}}, with the elementary activation and skip connections, needs d+dout+1d+d_{\mathrm{out}}+1.

We also tested the four networks in exact arithmetic for d=dout=2d=d_{\mathrm{out}}=2 with f7(x)=(12sin⁡(πx1)cos⁡(πx2),12cos⁡(πx1)sin⁡(πx2))\boldsymbol f_7(\boldsymbol x)=\bigl(\tfrac{1}{2}\sin(\pi x_1)\cos(\pi x_2), \tfrac{1}{2}\cos(\pi x_1)\sin(\pi x_2)\bigr) and ε=2−1,…,2−6\varepsilon=2^{-1},\dots,2^{-6}; all errors, measured in the Euclidean norm, are below ε\varepsilon (Table 2). The details are in Appendix F, and we have also updated the code in the supplementary material to include this example.

The practical aspects raised in the review, namely the discontinuous activations and training, are now discussed in the Limitations (Section 7).

We hope that these answers and revisions address your concerns, and we thank you again for the suggestions to improve the quality of our manuscript.

References

[1] G. G. Lorentz. Metric entropy and approximation. Bulletin of the American Mathematical Society, 1966.

[2] A. N. Kolmogorov and V. M. Tikhomirov. ε\varepsilon-entropy and ε\varepsilon-capacity of sets in function spaces. Uspekhi Matematicheskikh Nauk, 1959.

I thank the authors for their revision and their answers to my questions. This makes the paper clearer and addresses some of the issues I raised. However, my main objection about the very narrow intended audience remains and so I maintain my score of 3 (weak accept).

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

The paper investigates the minimum number of hidden neurons required for arbitrary-accuracy approximation of multivariate Hölder-continuous functions. The authors construct a fixed activation function that achieves arbitrary uniform approximation using only d+1 hidden neurons and establish a matching lower bound for feedforward networks with locally integrable activations. They further provide constructions using an elementary floor–exponential activation and analyze the associated bit complexity, obtaining an upper bound that matches the metric-entropy lower bound up to a logarithmic factor.

The paper addresses an interesting theoretical problem and presents potentially significant mathematical results. In particular, the exact characterization of the minimum neuron count is a valuable contribution. However, I have several concerns.

  1. Incomplete discussion of closely related literature.

The authors should discuss the following two papers and include their relevant results in Table 1:

  • Maiti, Michelle, and Yang, "Optimal Neural Network Approximation for High-Dimensional Continuous Functions" (arXiv:2409.02363). This work establishes arbitrary-accuracy approximation using O(d) unique nonzero parameters and proves the optimality of linear scaling with the input dimension. Its construction uses an elementary universal activation function.

  • Li, Shen, Yang, and Zhang, "Optimal Tradeoffs Between Network Size and Parameter Magnitude in Neural Approximation and Minimax Regression" (arXiv:2609.25710). This work establishes sharp tradeoffs between network size and parameter magnitude, including fixed-size constructions with O(d) nonzero parameters and optimal-order parameter magnitude. It also establishes matching lower bounds through the information capacity of neural network classes.

These works are directly related to the manuscript's two central questions: optimal network size and the information required for arbitrary-accuracy approximation. In particular, the optimal O(d) dependence on input dimension has already been established, while information-theoretic limitations on network representations have also been investigated.

The authors should therefore clarify that their principal improvement in network size is the exact minimum of d+1 hidden neurons, rather than establishing the optimal order of dimensional scaling for the first time. The results should be compared carefully under their respective assumptions, particularly regarding approximation norms, activation regularity, neuron counts, nonzero parameters, parameter magnitude, and bit complexity.

  1. The comparison with Yarotsky (2021) needs clarification.

Yarotsky (2021) established superexpressiveness for several elementary activation families. In particular, Corollary 1 provides an O(d²) upper bound on the number of neurons and connections, while the proof of Theorem 3 also describes an O(d)-neuron construction for its first activation family.

However, Table 1 of the submitted manuscript reports an exact d+2 neuron count with three hidden layers and a skip connection for Yarotsky (2021). It is unclear how this exact count and architecture are derived from the original paper. The authors should provide a precise derivation or reference supporting this entry.

More generally, Table 1 should distinguish explicitly stated results from architectural bounds derived by interpreting previous constructions. This is particularly important because the claimed improvement in the exact neuron count is central to the manuscript.

  1. Interpretation of the bit-complexity contribution.

The authors establish a bit-complexity upper bound of O(ε^{-d/α} log(1/ε)) and compare it with the classical metric-entropy lower bound Ω(ε^{-d/α}). This provides a useful characterization of the storage requirements of their constructions.

However, information-theoretic lower bounds and optimal tradeoffs between network size and parameter magnitude have also been investigated in recent work, particularly Li, Shen, Yang, and Zhang (2026). Although parameter magnitude and binary encoding length are distinct complexity measures, they are closely related in understanding how fixed-size networks encode increasingly accurate approximations.

A more detailed comparison would help establish what is genuinely new in the present bit-complexity analysis. The authors should also discuss whether the remaining logarithmic gap is inherent to the proposed network architectures or a consequence of their particular encoding scheme.

  1. Limited computational practicality.

The proposed constructions rely on discontinuous or nonstandard activation functions and extremely large integer-valued parameters. Although the number of neurons is minimal, the required parameter precision increases rapidly as the approximation error decreases.

Moreover, the computational complexity of evaluating the specialized activation and performing the associated arbitrary-precision arithmetic is not fully characterized. Consequently, minimizing neuron count does not necessarily lead to computationally efficient approximation. The authors should better discuss the tradeoff between network size, parameter storage, and evaluation complexity.

  1. Limited numerical investigation.

The numerical examples primarily verify the theoretical constructions using exact arithmetic. While these experiments are appropriate for confirming correctness, they do not provide much additional insight into approximation efficiency.

It would be useful to report the computational costs associated with increasing approximation accuracy, particularly the time required for constructing the encoded parameters and evaluating the resulting networks.

Overall, the manuscript establishes an interesting exact neuron-count result and provides explicit approximation constructions. These are meaningful theoretical contributions. However, the comparison with prior work should be substantially strengthened, especially regarding previously established optimal O(d) scaling and information-theoretic complexity bounds. The precise novelty of the bit-complexity contribution and the computational implications of the proposed constructions also require clarification.

Critical strengths
  1. Sharp theoretical result. The paper establishes the exact minimum of d+1 hidden neurons for arbitrary-accuracy uniform approximation under the specified activation assumptions, improving upon previously known order-optimal constructions.

  2. Explicit constructions and complexity analysis. The paper provides closed-form network constructions and analyzes their bit complexity, offering a quantitative perspective on the storage cost of fixed-size universal approximation.

Critical weaknesses
  1. Incomplete comparison with closely related theoretical results. Previous work has already established optimal O(d) network-size scaling and information-theoretic lower bounds on approximation complexity. These results are not adequately discussed, making the precise novelty of the manuscript difficult to assess.

  2. Limited computational significance. The constructions require specialized activations and extremely high-precision parameters. Their computational complexity is not adequately characterized, and optimal neuron count does not necessarily imply efficient approximation.

Questions for authors
  1. Can the authors incorporate Maiti, Michelle, and Yang (arXiv:2409.02363) and Li, Shen, Yang, and Zhang (arXiv:2609.25710) into the related-work discussion and Table 1, carefully comparing the optimal O(d) scaling and information-theoretic complexity results?

  2. Can the authors justify the exact d+2 neuron count attributed to Yarotsky (2021) in Table 1? Where is this specific architecture established or derived?

  3. How does the proposed bit-complexity lower bound relate to existing information-theoretic lower bounds on parameter magnitude and network size? Is the additional logarithmic factor necessary?

  4. What are the computational costs of constructing and evaluating the proposed networks when arbitrary-precision arithmetic is required?

4 comments

We thank the reviewer for the careful reading and the constructive suggestions. The sections, theorems, tables and figures mentioned below refer to the revised manuscript, in which all revisions are marked in blue.

Q1. Related work discussion.

Thank you for pointing us to these two papers. We have revised Table 1: it now includes both works, and it has a new column with the number of parameters. In our understanding, their contributions are the following. Maiti et al. [1] reduce the O(d2)O(d^2) parameters of Zhang et al. [3] to O(d)O(d) nonzero parameters, for uniform approximation with the same continuous elementary activation. Li et al. [2] obtain LpL^p approximation with a Lipschitz continuous activation by fixed-size networks with O(d)O(d) neurons and O(d)O(d) parameters. To our knowledge, they are also the first to establish a matching information-theoretic lower bound on the parameter magnitude of fixed-size networks.

Accordingly, we revised the two paragraphs of the Introduction on the neuron count (“How few neurons suffice?”) and on the cost of a small network (“What does a small network cost?”). In particular, the Introduction now clarifies that our contribution in network size is the exact minimum, d+1d+1 hidden neurons, and not the linear order in dd (see lines 45–49). We hope that the discussion of fixed-size networks in the Introduction is now clearer. We also added an explicit discussion of the matching information-theoretic lower bound of [2] after Proposition 5.2 (lines 468–477).

Q2. The (d+2)(d+2)-neuron construction of Yarotsky [4].

Yarotsky [4] does not state an explicit neuron count. For the family A1={σ1,⌊⋅⌋}\mathcal A_1=\lbrace\sigma_1,\lfloor\cdot\rfloor\rbrace, he notes in the proof of his Theorem 3 that the computation defined by his Eqs. (1)–(3) can be represented by a network of fixed size O(d)O(d). The count d+2d+2 and the architecture in Table 1 are our derivation from these equations. To be specific, in his notation,

gM(x)=1+∑k=1d(M+1)k−1⌊Mxk⌋,ϕ(t)=t−⌊t⌋,f~(x)=u(gM(x)),u(y)=(B−A)ϕ(sσ1(α+β2+wy))+A.g_M(x) = 1+\sum_{k=1}^{d}(M+1)^{k-1}\lfloor Mx_k\rfloor, \quad \phi(t)=t-\lfloor t\rfloor, \quad \tilde f(x) = u\bigl(g_M(x)\bigr), \quad u(y)=(B-A)\phi\Bigl(s\sigma_1\bigl(\tfrac{\alpha+\beta}{2}+wy\bigr)\Bigr)+A .

Here A=min⁡fA=\min f, B=max⁡fB=\max f, α+β2\frac{\alpha+\beta}{2} is the centre of an interval on which σ1\sigma_1 is analytic and non-polynomial, and s,ws,w are weights. Written as a network:

  • First hidden layer: dd neurons with activation ⌊⋅⌋\lfloor\cdot\rfloor; the kk-th computes hk=⌊Mxk⌋h_k=\lfloor Mx_k\rfloor.
  • Second hidden layer: one neuron with activation σ1\sigma_1, computing z=σ1(α+β2+w+w∑k=1d(M+1)k−1hk)=σ1(α+β2+wgM(x)).z=\sigma_1\Bigl(\tfrac{\alpha+\beta}{2}+w+w\sum_{k=1}^{d}(M+1)^{k-1}h_k\Bigr)=\sigma_1\bigl(\tfrac{\alpha+\beta}{2}+w g_M(x)\bigr). Its pre-activation is affine in h1,…,hdh_1,\dots,h_d.
  • Third hidden layer: one neuron with activation ⌊⋅⌋\lfloor\cdot\rfloor, computing t=⌊sz⌋t=\lfloor sz\rfloor.
  • Output: f~(x)=(B−A)(sz−t)+A=(B−A)sz−(B−A)t+A,\tilde f(x)=(B-A)(sz-t)+A=(B-A)sz-(B-A)t+A, which is affine in zz and tt. Because zz belongs to the second hidden layer, the output reads it directly, through a skip connection from the second hidden layer.

This gives d+2d+2 hidden neurons in three hidden layers with one skip connection. In the revised Table 1, the entries that we derived from published constructions, including this one, are marked with †.

(continued in the next comment)

References

[1] A. Maiti, M. Michelle, and H. Yang. Optimal neural network approximation for high-dimensional continuous functions. arXiv preprint, 2024.

[2] B. Li, Z. Shen, H. Yang, and S. Zhang. Optimal tradeoffs between network size and parameter magnitude in neural approximation and minimax regression. arXiv preprint, 2026.

[3] S. Zhang, Z. Shen, and H. Yang. Deep network approximation: Achieving arbitrary accuracy with fixed number of neurons. Journal of Machine Learning Research, 2022.

[4] D. Yarotsky. Elementary superexpressive activations. International Conference on Machine Learning (ICML), 2021.

Q3. Bit complexity and information-theoretic lower bounds.

Network size. The information-theoretic lower bound holds for any network. Networks whose size grows as ε\varepsilon decreases spread the information about ff over many parameters: for uniform accuracy ε\varepsilon on functions of smoothness s>0s>0, shallow ReLU networks usually have about ε−d/s\varepsilon^{-d/s} parameters of O(log⁡(1/ε))O(\log(1/\varepsilon)) bits each [6, 7], and very deep ReLU networks can remove the logarithm, with about ε−d/(2s)\varepsilon^{-d/(2s)} parameters of about ε−d/(2s)\varepsilon^{-d/(2s)} bits each [7]. In contrast, fixed-size constructions pay for accuracy with the magnitude and precision of their parameters, a phenomenon Zhang et al. [3] call the curse of memory but do not quantify. We have added this comparison to the Introduction paragraph “What does a small network cost?” (lines 55–63).

Parameter magnitude. The bit complexity can come from either the magnitude or the precision of the parameters. A lower bound on the magnitude was recently obtained by Li et al. [2]: for a fixed-size network with a globally Hölder continuous activation to reach LpL^p accuracy ε\varepsilon on the Hölder class, its largest weight or bias in absolute value, TT, must satisfy log⁡T≥cε−d/α\log T\ge c\varepsilon^{-d/\alpha} for a constant c>0c>0. Their proof needs the continuity of the activation: a small change of the parameters causes only a small change of the output, so the digits far after the binary point can be dropped, and parameters with few digits cannot distinguish all functions in the class; hence large parameters are needed. For a discontinuous activation, this argument does not apply, and a network could also use parameters with many digits after the binary point. Proposition 5.2, which counts these digits as well, holds for every activation. In our constructions, however, almost all the information is still stored in a single large integer. We have added this discussion after Proposition 5.2 (lines 468–477).

Is the additional logarithmic factor necessary? The factor comes from our encoding, not from the architecture. The networks Φf,εϱ\Phi_{f,\varepsilon}^{\varrho}, Φf,εσ\Phi_{f,\varepsilon}^{\sigma} and Φf,εσ,skip\Phi_{f,\varepsilon}^{\sigma,\mathrm{skip}} store the quantized value qℓq_\ell of every cell QℓQ_\ell separately, as one digit of Θ(log⁡(1/ε))\Theta(\log(1/\varepsilon)) bits, and they do not use the continuity of ff.

The factor is not necessary for fixed-size networks, and we thank the reviewer for this question: it led us to improve our result from near-optimal to optimal. Following Yarotsky's 2018 work [5], whose idea is also used by Li et al. [2], we use in our construction that the values of ff at neighboring grid points differ little, so that ∣qℓ−qℓ′∣≤2|q_\ell-q_{\ell'}|\le2 for neighboring cells. We modified the digit-extraction activation ϱ\varrho and the corresponding (d+1)(d+1)-neuron network accordingly (new Section 3.1.2). The differences of the quantized values along a spanning tree of the grid (Figure 1c) are stored as base-55 digits, and the new activation ϱ~\widetilde\varrho sums them along a tree path. The new network Φf,εϱ~\Phi_{f,\varepsilon}^{\widetilde\varrho} keeps the widths (d,1)(d,1), and its bit complexity is Θ(ε−d/α)\Theta(\varepsilon^{-d/\alpha}) (Theorem 5.1), which matches the lower bound of Proposition 5.2. It is therefore optimal both in neuron count for C([0,1]d)C([0,1]^d) and in bit complexity for the Hölder class Hλ,Rα([0,1]d)\mathcal H_{\lambda,R}^{\alpha}([0,1]^d), and we changed the title and the abstract accordingly. We have also added Φf,εϱ~\Phi_{f,\varepsilon}^{\widetilde\varrho} to the numerical verification in exact arithmetic (Section 6 and Table 6) and to the code in the supplementary material.

In summary, what is new in our analysis of the bit complexity is that the lower bound holds for every activation and in the uniform norm, and the optimal bit complexity is attained with the minimal d+1d+1 neurons.

(continued in the next comment)

References

[2] B. Li, Z. Shen, H. Yang, and S. Zhang. Optimal tradeoffs between network size and parameter magnitude in neural approximation and minimax regression. arXiv preprint, 2026.

[3] S. Zhang, Z. Shen, and H. Yang. Deep network approximation: Achieving arbitrary accuracy with fixed number of neurons. Journal of Machine Learning Research, 2022.

[5] D. Yarotsky. Optimal approximation of continuous functions by very deep ReLU networks. Conference on Learning Theory (COLT), 2018.

[6] R. Hong and A. Kratsios. Bridging the gap between approximation and learning via optimal approximation by ReLU MLPs of maximal regularity. arXiv preprint, 2024.

[7] D. Yarotsky and A. Zhevnerchuk. The phase diagram of approximation rates for deep neural networks. Advances in Neural Information Processing Systems (NeurIPS), 2020.

Q4. Computational costs of construction and evaluation.

We agree that a network with the optimal neuron count does not mean parameters of small magnitude (or, when the activation is not restricted to be continuous, a small bit complexity), and it does not mean a cheap evaluation either. The price of such a fixed-size network is the information-theoretic lower bound that a single parameter must satisfy, as stated by Li et al. [2] and in our Proposition 5.2. The Limitations (Section 7) now state this explicitly.

Apart from the discussion of the bit complexity in Section 5, the revised manuscript also includes a new Appendix G on the computational cost. First, it gives theoretical bounds on the bit operations needed to build each network from the quantized values q0,…,qK−1q_0,\dots,q_{K-1} and to evaluate it at one input. The following table is a simplified version of Table 3, which also lists the steps that determine these bounds.

networkconstructionone evaluation
Φf,εϱ\Phi_{f,\varepsilon}^{\varrho}O(ε−2d/αlog⁡2(1/ε))O(\varepsilon^{-2d/\alpha}\log^2(1/\varepsilon))O(ε−d/αlog⁡2(1/ε))O(\varepsilon^{-d/\alpha}\log^2(1/\varepsilon))
Φf,εϱ~\Phi_{f,\varepsilon}^{\widetilde\varrho}O(ε−d/αlog⁡2(1/ε))O(\varepsilon^{-d/\alpha}\log^2(1/\varepsilon))O(ε−d/αlog⁡2(1/ε))O(\varepsilon^{-d/\alpha}\log^2(1/\varepsilon))
Φf,εσ\Phi_{f,\varepsilon}^{\sigma}, Φf,εσ,skip\Phi_{f,\varepsilon}^{\sigma,\mathrm{skip}}O(ε−d/αlog⁡(1/ε))O(\varepsilon^{-d/\alpha}\log(1/\varepsilon))O(ε−d/αlog⁡(1/ε))O(\varepsilon^{-d/\alpha}\log(1/\varepsilon))

Second, Table 4 reports the measured construction and evaluation times of the four networks for the test functions f1,…,f6f_1,\dots,f_6 at all accuracies of Section 6. The construction of Φf,εϱ\Phi_{f,\varepsilon}^{\varrho} is very time-consuming and is dominated by the offset SnS_n, but since SnS_n does not depend on ff, it can be computed once for all targets.

We have also accelerated the code. For example, in Φf,εσ\Phi_{f,\varepsilon}^{\sigma} and Φf,εσ,skip\Phi_{f,\varepsilon}^{\sigma,\mathrm{skip}}, the stored integer AfA_f is multiplied by v(x)+1=12B−r(x)v(x)+1=\tfrac{1}{2}B^{-r(x)}, which is a power of two (Eqs. (23), (24) and (26)); the code now carries out these multiplications by bit shifts of AfA_f instead of multiplications of long integers as before. We have updated the code in the supplementary material accordingly. The outputs of the networks are the same, and only the running times differ.

We hope that these answers and revisions address your concerns, and we thank you again for the suggestions to improve the quality of our manuscript.

References

[2] B. Li, Z. Shen, H. Yang, and S. Zhang. Optimal tradeoffs between network size and parameter magnitude in neural approximation and minimax regression. arXiv preprint, 2026.

Thank you very much for the eplanation. You have addressed all my questions. I recommen clear acceptance.

I also read the comment by Reviewer N5AP. Though it may be in appropriate to comment on other reviewer's comments. But I found that Reviewer N5AP has mis-interpretated the result of this paper under review. I think the paper Hong & Kratsios [1] solved a different problem. We cannot naively extend the result in Hong & Kratsios [1] to obtain the result in this paper.

Reviewer_N5APOpenReview ↗
Rating
3(+2)
Confidence
4
Informativeness
2(+1)
Presentation
2(−1)
Soundness
2(−1)
Read review
Paper summary

The paper studies the very interesting problem of minimax (uniform) universal approximation by MLPs, where optimality is quantified in terms of bit complexity. However, as far as I know, this problem is already solved. (see below).

Critical strengths

I think the solution to this problem is already known and worked out in this paper:

"Bridging the Gap Between Approximation and Learning via Optimal Approximation by ReLU MLPs of Maximal Regularity" by Ruiyang Hong, Anastasis Kratsios in Proposition 4.1; all the hidden weights and biases are shown to be 1/2, 0, 1, (plus or minus); and the final layer has the sample function values.

Moreover their solution also achieves the optimal modulus of continuity, in addition.

So in that way, I don't know what this paper provides.

Critical weaknesses

^ See above, the results are known.

Questions for authors

NA

2 comments
AuthorsOpenReview ↗

Revised manuscript uploaded

Following up on our earlier reply, we have now uploaded the revised manuscript, in which all changes are marked in blue. Hong & Kratsios [1] and Yarotsky & Zhevnerchuk [5] are now cited in the Introduction (lines 59-61). In addition, a new network with the same fixed number of d+1d+1 neurons (Section 3.1.2) now attains optimal, rather than near-optimal, bit complexity over the Hölder class (Theorem 5.1). We would be grateful if the reviewer could take a look at the revised version, and we are happy to answer any further questions.

Works for me; thanks.

Comments on the paper

1 comment
Area_Chair_782zOpenReview ↗

Reminder: Follow-up Feedback Before Discussion Closes

Dear reviewers,

With the discussion period nearing its end, I would appreciate it if you could review the authors’ responses and revised manuscript and share their follow-up feedback.

Please indicate which concerns have been addressed and which remain, and update your assessment and score where appropriate.

Thank you for your time and contributions to the discussion.

Best, AC

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.