PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal Tradeoffs Between Network Size and Parameter Magnitude in Neural Approximation and Minimax Regression

Baicheng Li, Zuowei Shen, Haizhao Yang, Shijun Zhang

arXiv:2609.25710v1stat.MLcs.LG

TL;DR

The paper asks whether larger parameter magnitudes can compensate for fewer neurons while preserving approximation and statistical accuracy. It establishes a sharp width–magnitude approximation law and applies it to minimax regression, yielding a continuum of statistically optimal network choices.

  • Problem

    Network accuracy depends on both approximation power and the complexity of the fitted class, but the role of parameter magnitude in both is not quantified by network size alone.

    Source: §1 · p. 2

  • Method

    The paper proves a joint width–magnitude approximation law using DTA, then combines it with least-squares bounds for the full clipped network class.

    Source: §1 · pp. 2–3

  • Results

    O(M^-2β/(2β+d)) squared risk is attained when N^2 log(eNT) is of order M^d/(2β+d), with choices ranging from unit radius to fixed width.

    Source: §1.1 · p. 5, §5 · p. 24

  • Takeaways & Limitations

    The approximation law provides a continuum of statistically optimal allocations between network width and parameter magnitude.

    Source: §1 · p. 3, §5 · p. 24

    Algorithms that attain the required empirical-loss tolerance while controlling arithmetic precision and sensitivity to large parameters remain to be found.

    Source: §5 · p. 24

Abstract

from arXiv · show

The statistical accuracy of neural networks depends on both their approximation power and the complexity of the class fitted from data. While increasing network size is a natural way to improve approximation, parameter magnitude provides another resource whose role must be quantified in both respects. We establish a sharp width--magnitude tradeoff at fixed depth using one elementary bounded $1$-Lipschitz Dyadic--Triangular Activation. For the unit $β$-Hölder ball on $[0,1]^d$ with $0<β\leq1$, the optimal $L^p$ approximation error for $0<p<\infty$ is of order $[N^2\log(eNT)]^{-β/d}$ when the network width satisfies $N\geq2d+3$ and the parameter magnitudes are bounded by $T\geq1$. Matching lower bounds hold for every fixed globally Hölder activation; its Hölder exponent affects the constants but not the rate. Under bounded design densities and independent centered sub-Gaussian noise, approximate least squares over the full clipped class at depth $23$ attains the classical Hölder minimax risk $\mathcal{O}(M^{-\frac{2β}{2β+d}})$ without logarithmic loss whenever $N^2\log(eNT)\asymp M^{\frac{d}{2β+d}}$, where $M$ is the sample size. This yields a continuum of statistically optimal choices, ranging from unit parameter radius to fixed network size. At fixed size, four hidden layers with at most $8d+7$ nonzero parameters give a near-optimal radius, while six layers with at most $8d+27$ attain the optimal order $\log T=\mathcal{O}(η^{-d/β})$ at approximation error $η$. The same decoding method also yields fixed-size Transformer approximation.

1 Introduction

The introduction asks whether larger parameter magnitudes can compensate for fewer neurons while preserving approximation and statistical accuracy. It presents a sharp width–magnitude tradeoff, its minimax regression consequence, and constructions for fixed-size networks.

1 Introduction

  • Parameter magnitude affects both approximation power and class complexity, so determining whether it can compensate for width requires tracking it in both parts of the approximation–estimation balance.The motivating question is whether larger parameters can recover accuracy lost by using a smaller network.Source: §1 · pp. 2–3
  • The paper introduces DTA, a fixed bounded 1-Lipschitz activation whose rescaled periodic branch supplies oscillations for fixed-architecture approximation, unlike the cited classical activations’ fixed-size obstruction.DTA combines a triangular wave with a shifted exponential branch; its parameter radius is retained to control estimation complexity.Source: §1 · p. 4

1.1 Main contributions

  • [N^2 log(eNT)]^-β/d is the optimal Lp approximation error for 0 < p < ∞, attained by DTA and matched by lower bounds for fixed globally Hölder activations.The result holds for N ≥ 2d + 3 and T ≥ 1; the activation’s Hölder exponent affects the constants, not the rate.Source: §1.1 · p. 4
  • The same least-squares inequality gives the exact minimax rate along a curve: at TM = 1, NM ≍Md/[2(2β+d)]/√log M; at NM = 2d + 3, log TM ≍Md/(2β+d).Source: §1.1 · p. 5
  • Six hidden layers and at most 8d + 27 nonzero parameters attain the optimal fixed-size radius order log T ≲ η^-d/β; four layers with at most 8d + 7 retain a logarithmic overhead.The decoding method also yields fixed-size Transformer approximation, with log T ≲ η^-dn/β for fixed sequence length n.Source: §1.1 · p. 5

1.2 Related work and comparison

  • Earlier sparse ReLU regression bounds cited here retain logarithmic losses, whereas this paper’s matching width–radius bounds cover the full curve of minimax-optimal choices.The curve includes growing width at unit radius and fixed width with increasing radius.Source: §1.2 · pp. 6–7

2 Setting and main results

At fixed depth, this section quantifies how network width and parameter radius jointly govern approximation and regression, using a fixed Dyadic–Triangular Activation. It gives fixed-size neural and Transformer constructions alongside a minimax regression guarantee.

2.1 The Dyadic–Triangular Activation

  • DTA joins a shifted exponential on negative inputs to a triangular wave on nonnegative inputs, and is globally 1-Lipschitz with values in (-1, 1].It also acts as the identity on inputs from 0 to 1.Source: §2.1 · p. 8

2.2 Network convention

  • The network convention defines width as the largest hidden-layer width, depth as the number of hidden layers, and parameter radius through the largest absolute weight or bias.The final affine map is not counted as a hidden layer.Source: §2.2 · p. 8

2.3 Target, hypothesis classes, and approximation theorems

  • Four hidden layers and at most 8d + 7 nonzero parameters give a near-optimal radius; six layers and at most 8d + 27 attain the optimal order log T = O(η^-d/β).The six-layer construction removes the logarithmic overhead of the four-layer radius bound.Source: §2.3 · pp. 9–10
  • DTA achieves fixed-depth Lp approximation error of order [N^2 log(eNT)]^-β/d; matching lower bounds hold for every globally Hölder activation.The stated range is N ≥ 2d + 3 and T ≥ 1.Source: §2.3 · p. 10

2.4 Fixed-size Transformer approximation

  • A fixed-size Transformer with one size-two attention head approximates the stated sequence maps with error at most η and log radius bounded by CTrη^-dn/β.For fixed d and n, its architecture is independent of accuracy.Source: §2.4 · p. 11

2.5 Sampling model and the regression rate

  • At depth 23, approximate least squares over the full clipped class attains classical Hölder minimax risk without logarithmic loss under uniform design and fixed nondegenerate Gaussian noise.The guarantee applies along the width–radius curve and concerns measurable approximate minimizers; it does not assert efficient computation.Source: §2.5 · p. 12

3 Proofs of Theorems 1–3

The proofs establish the approximation results by locating grid cells and decoding stored values, using narrow boundary strips to control error and constructions that cover every parameter bound T ≥ 1.

3.1 Dyadic table decoder

  • The dyadic table decoder fits an arbitrary finite list using one hidden unit and at most four nonzero parameters, approximating each listed value within ε.Its construction encodes the table through a single integer.Source: §3 · p. 12, §3.1 · p. 13

3.2 Trifling region and grid encoder

  • The grid encoder has hidden-layer widths [2d+1, d+1], at most 8d+3 nonzero parameters, and parameter radius at most 4 max{K,(Kδ)^-1}.It combines the d grid-cell indices into a base-K integer outside the trifling boundary strips.Source: §3.2 · pp. 13–14

3.3 Proof of Theorem 1

  • Theorem 1’s composed network uses at most 8d+7 nonzero parameters for approximation across every 0<p<∞.It combines a grid encoder and a dyadic table decoder, with boundary-strip error controlled separately.Source: §3.3 · p. 15

3.4 Block-grid encoding and coupled decoding

  • The coupled decoder stores neighboring rounded values as ternary increments and uses affine subtraction of two evaluations with common error to recover the required partial sum.A square-array code further reduces code length.Source: §3.4 · p. 16

3.5 Proof of Theorem 2

  • For n = 2, the logarithmic term is bounded by a constant multiple of η−d/β; a coupled decoder uses affine subtraction of two evaluations with a common error to recover the exact position of the required partial sum.Source: §3.4 · p. 16, §3.5 · p. 18

3.6 The unit-radius theorem and Proof of Theorem 3

  • For 1≤T<N^γ, the unit-radius theorem gives Lp error at most Cur[N^2log(eN)]^-β/d; the proof uses the large-radius construction when T≥N^γ.The unit-radius construction encodes a table of order N^2log(eN) grid values with every parameter bounded by one.Source: §3.6 · p. 19
  • Two cases cover every T ≥1 and prove the theorem.Source: §3.6 · p. 19

4 Proofs of Theorems 4 and 6

The proof section establishes the width–radius approximation lower bound through entropy and network covering arguments, then uses approximation and empirical-risk bounds to analyze regression. The regression proof also controls the extra logarithmic covering term along the width–radius tradeoff.

4.1 Proof of Theorem 4

  • The entropy argument uses a direct Hölder-ball packing that covers the endpoint β = 1 and the quasi-norm range 0 < p < 1.The packing proof is included in the form needed for the approximation lower bound.Source: §4.1 · p. 20
  • Hölder packing and network-covering estimates yield a lower bound on worst-case approximation error for globally Hölder activations.The proof uses separated functions in the Hölder ball and compares their packing size with the network class's empirical cover.Source: §4.1 · pp. 20, 22
  • [N^2 log(eNT)]^-β/d is the sharp Lp approximation order for DTA at depth 17 + ⌈3pβ⌉, N ≥ 2d + 3, and T ≥ 1.The lower bound matches the upper bound, including at unit radius.Source: §4.1 · p. 22

4.2 Proof of Theorem 6

  • The regression proof combines approximation error with an empirical-risk bound and absorbs the extra log M term using the width–radius constraint.The argument applies the covering estimate and controls the added logarithm along the tradeoff, including the unit-radius endpoint.Source: §4 · p. 19, §4.2 · p. 23

5 Conclusion

The paper establishes sharp fixed-depth approximation tradeoffs and uses them to obtain minimax regression accuracy across a continuum of network width and parameter-radius choices. It also identifies unresolved questions about variable depth, activation scope, and efficient training.

5 Conclusion

  • The DTA approximation order is sharp at fixed depth, and the regression result attains squared risk O(M^-2β/(2β+d)) along choices satisfying N^2 log(eNMTM) ≍ M^d/(2β+d).The choices range from unit radius to fixed width.Source: §5 · p. 24
  • For the unit β-Hölder ball with 0 < β ≤ 1 in every finite Lp, at fixed size, four hidden layers give log T ≲ η^-d/β log(η^-1), while six attain optimal order log T ≲ η^-d/β.Source: §5 · p. 24
  • The decoding method also gives fixed-size Transformer approximation with log T ≲ η^-dn/β.Source: §5 · p. 24
  • Whether the same optimal laws extend to variable depth or broader activation classes remains open; connecting the guarantees to effective training is another direction.The paper specifically raises algorithmic attainment of the required empirical-loss tolerance while controlling arithmetic precision and sensitivity to large parameters.Source: §5 · p. 24

A Proofs of Propositions 2 and 3

The proofs use two encoders: one returns a normalized grid address, and the other returns a block index and position within the block. Both use the same scalar staircase, whose interpolation controls outputs across the cube.

A Proofs of Propositions 2 and 3

A.1 Proof of Proposition 2

The construction uses a scalar staircase to recover grid indices away from short boundary strips and interpolate within those strips. A shared-carrier encoder then combines coordinatewise addresses into a normalized grid address.

A.1 Proof of Proposition 2

  • Outside the trifling intervals, the scalar staircase equals the grid floor; on each such interval, it interpolates between adjacent integer values.The construction also bounds the staircase output within [0, K].Source: §A.1 · p. 30
  • The encoder applies the staircase to each coordinate and uses a shared carrier to cancel linear terms, leaving the normalized grid address.Figure 7 depicts the shared-carrier architecture for d = 2.Source: §A.1 · pp. 30–31
  • The three affine maps use at most 8d + 3 nonzero parameters and have parameter radius at most 4 max{K, (Kδ)^-1}.Source: §A.1 · p. 31

A.2 Proof of Proposition 3

The encoder recovers a block index and normalized within-block position outside the fine trifling set, using three affine maps with explicit parameter and radius bounds.

A.2 Proof of Proposition 3

  • Three affine maps take dimensions d → 2d + 3 → d + 2 → 2, and the reused c coordinate remains unchanged by the activations.Source: §A.2 · pp. 31–32
  • Outside the fine trifling set, the encoder returns the stated block index and normalized within-block position.The proof considers fine intervals immediately before k/H, distinguishing whether they also lie in a coarse trifling interval.Source: §A.2 · pp. 31–32
  • The encoder has at most 8d + 12 nonzero parameters and radius at most max{4Hd, B/(2Hδ)}.The three affine maps contain at most 4d + 3, 3d + 4, and d + 5 nonzero parameters, with radii at most H, max{1, B/(2Hδ)}, and 4Hd, respectively.Source: §A.2 · p. 32

B Proof of Proposition 1

The proofs use bounded integer phase approximation to construct a scalar table decoder, while related coding arguments handle row sequences and guarded phase storage.

B Proof of Proposition 1

  • Dyadic orbit density supplies a uniformly bounded integer phase approximation, which the decoder uses to recover table values with parameter radius at most 6R.The proof combines algebraic separation of the dyadic frequencies with Gaussian Fourier analysis and lattice covering; the orbit bound gives |q| ≤ Q.Source: B Proof of Proposition 1 · pp. 32, 36, 37

C Proof of Proposition 4

  • The width-two construction stores row sequences through starting values and increments, using shared evaluation error that cancels when forming the next address.The wider construction preserves this cancellation while distributing the data among shorter integers.Source: C Proof of Proposition 4 · p. 37

C.1 A phase-coding lemma

  • The guarded phase code stores interior target phases through successive base-G digits, keeping perturbations within the same linear branch of the triangular wave.The stored integer is bounded by GN − 1, and the construction uses target values restricted to [ζ, 1 − ζ].Source: §C.1 · pp. 37–38

C.2 Proof of Proposition 4, part (a)

The proof develops a scalar decoder that encodes block increments and recovers partial sums and selected phase information, with lemmas controlling the choice of rows, phases, and powers of G. It also describes distributing phases across shorter codes without added approximation error and extending the construction to every width N≥2 by zero padding while preserving output and parameter bounds.

C.2 Proof of Proposition 4, part (a)

  • The decoder uses four hidden layers to recover a starting value and ternary code, address a partial sum, and add that sum; shared phase errors cancel.Its five affine maps use at most 18 nonzero parameters, and the proof bounds the output between prescribed inputs.Source: §C.2 · pp. 39–41

C.3 Two technical lemmas

  • The cyclic triangular selector lemma provides a matrix-based way to select a row from an integer address, with properties established for integer and real inputs.The wider construction uses this selector to choose a row before extracting a prescribed phase from a short integer.Source: §C.3 · p. 42
  • The short-code array lemma selects the required integer and power of G without multiplying network outputs, while retaining the selected row and input value.For an address i = qWM + W(ℓ−1) + p + 1, it returns the encoded integer scaled by G^-ℓ; its affine maps have explicit parameter bounds.Source: §C.3 · p. 44
  • The four-layer decoder cancels unwanted terms around the selected column, recovers the short integer, and proves parts (i) and (ii) of Lemma C.2.It also carries the coordinate unchanged through the final activation.Source: §C.3 · p. 46

C.4 Proof of Proposition 4, part (b)

  • Distributing phases among W² shorter codes introduces no additional error when reconstructing the table value at table inputs.The two-stage read recovers an integer address, then reads the corresponding second phase to reconstruct the value.Source: §C.4 · pp. 48–49
  • N≥2 widths are covered, with the scalar decoder used for N≤11 or Q<9; zero padding preserves outputs and parameter bounds.The parameter estimates in the remaining cases hold with CD=1500.Source: §C.4 · p. 50

D Proof of Theorem 7

The construction normalizes grid indices and fits their assigned values with parameters of magnitude at most one, then composes the networks.

D Proof of Theorem 7

  • The construction first produces normalized grid indices and then fits the values assigned to them using parameters of magnitude at most one.Source: D Proof of Theorem 7 · p. 50
  • Repeated coordinates replace large multipliers, while Lemma C.2 selects the stored values.Source: D Proof of Theorem 7 · p. 50
  • The encoder and value-fitting networks are composed, and the resulting affine interface is checked.Source: D Proof of Theorem 7 · p. 50

D.1 The unit-radius encoder

The appendix constructs a normalized grid encoder with unit-bounded parameters by building staircases and refining their transition intervals. In d dimensions, parallel scalar encoders recover coordinatewise grid indices outside a trifling region.

D.1 The unit-radius encoder

  • The scalar construction generates grid frequency using repeated coordinates, with all affine parameters bounded by one.It applies when m and K are powers of two and δ is between zero and 1/K.Source: §D.1 · pp. 50–51
  • The d-dimensional encoder returns (⌊Kx_1⌋, …, ⌊Kx_d⌋) outside the trifling region, with width at most d(2m + 1), hidden depth at most 1 + qK + qδ, and parameter radius one.Only the width is multiplied by d when scalar copies are placed in parallel.Source: §D.1 · pp. 50, 52
  • On each trifling interval, the scalar output interpolates between consecutive normalized indices and stays in [0, 1].The construction sharpens the short transition intervals before recovering the normalized grid index.Source: §D.1 · pp. 51–52

D.2 The unit-radius decoder

The unit-radius decoder fits finite sequences by encoding block addresses, retrieving stored values, and summing only the required prefix of increments. The construction composes these components into a width-N, depth-13 DTA network under a stated capacity condition.

D.2 The unit-radius decoder

  • For values in [−1, 1] with adjacent differences at most ε, the construction yields a width-at-most-N, depth-13 DTA network with parameter radius at most one when (24 log 5)M ≤ N^2 log(eN).The decoder may extend the sequence by repeating its last value to a length M*.Source: §D.2 · pp. 52, 57
  • The decoder stores each block’s starting value and a base-five word of increments, then recovers and sums the first r digits for the requested position.The proof composes a block-index encoder, a two-table decoder, and a prefix decoder.Source: §D.2 · pp. 52, 55, 57
  • The block-index encoder maps a sample address to its block and position using four hidden layers, width at most 2W + 1, and unit parameter radius.The address encodes the table entry as (qW + p)/W^2.Source: §D.2 · p. 53
  • The square-table decoder retrieves table entries with five hidden layers and width at most max{2W + 2, 2hW}, while keeping parameter magnitudes at most one.Extra inputs in [0, 1] can be carried through without changing depth or radius.Source: §D.2 · pp. 53, 55
  • The three decoder components have depths 4, 5, and 4, and their merged affine maps preserve the unit parameter bound.Their depths add to 13 hidden layers.Source: §D.2 · pp. 52, 58

D.3 Proof of Theorem 7

The proof of Theorem 7 builds an approximation from grid values arranged as a slowly varying sequence, then composes a grid encoder with a point-fitting decoder. The construction keeps parameter radius one and also treats bounded widths with a constant network.

D.3 Proof of Theorem 7

  • The grid encoder and point-fitting decoder are composed while checking that merged affine maps still have weights and biases bounded by one.The decoder handles a sequence of length M = 3K^d with adjacent differences at most K^-β.Source: §D.3 · p. 59
  • The constructed approximant belongs to FDTA(N, 17 + ⌈3pβ⌉, 1), establishing the required bound for widths N ≥ N0.N0 depends only on d.Source: §D.3 · p. 60
  • For 1 ≤ N < N0, a constant network gN ≡ f(x◦) satisfies ∥f − gN∥Lp ≤ 2^-β.The construction uses x◦ = (1/2, …, 1/2) and belongs to the same network class.Source: §D.3 · p. 60

E Proof of Theorem 5

The proof combines local grid addresses into global addresses with one attention layer, then applies a decoder to all output coordinates in parallel. It bounds the Transformer parameter radius in terms of the approximation target.

E Proof of Theorem 5

  • One attention layer combines local addresses into a global address, and the output block decodes all coordinates in parallel.The proof specifies input, attention, and output architectures.Source: E Proof of Theorem 5 · pp. 60, 63
  • On the trifling region, the decoder output is uniformly bounded by 1 + B/U, and each coordinate error is at most 2 + B/U.The proof separately bounds the contribution from this region to the approximation error.Source: E Proof of Theorem 5 · pp. 63–64
  • The Transformer construction satisfies log T_Tr,η ≤ C_Tr η^(-dn/β).The input and attention terms have logarithmic size in η^-1, while the output block determines the stated bound.Source: E Proof of Theorem 5 · p. 64

F Proofs of Propositions 6 and 7

The proofs turn parameter stability into empirical covers, control random-design and noise fluctuations, then combine those bounds in a measurable approximate least-squares argument.

Loading 2609.25710v1…