Constructing accurate and computationally tractable approximation spaces is a fundamental task in scientific computing. Partially trainable neural networks bridge fixed random features and fully adaptive representations. This paper quantifies a phase transition pattern in approximation bounds and observes analogous behavior in training errors: a rapid but smooth initial improvement followed by diminishing returns, with a sharper transition under greater initialization mismatch. Under polynomial spectral decay with exponent α>1 and leverage compatibility, we establish a squared L2 approximation rate O((κPlog(m/δ)/m)α) for two-layer networks of width m and trainable proportion P, where κP=(P/κ1∗+(1−P)/κ0∗)−1. The bound holds uniformly over the unit ball of a reproducing kernel Hilbert space (RKHS) with probability at least 1−δ. The constants κ0∗ and κ1∗ quantify the fixed and trainable groups' sampling mismatches relative to the target RKHS. For spherical biased-ReLU features in dimension d, we verify these assumptions with α=(d+2)/(d−1) and κ0∗=42τ(d+1)/d for initialization scale τ≥1, and κ1∗=1 under ridge leverage sampling. For d=5 and τ=10, a trainable proportion of approximately 4.1% captures 90% of the reduction in the approximation bound from P=0 to P=1. A structured three-layer example illustrates how a few trainable first-layer neurons exploit fixed downstream blocks through nonlinear composition. Numerical experiments across diverse settings, including networks with up to 15 layers, exhibit similar phase transitions in training errors.
Figures & tables
Figure 1: Phase transitions for two-layer spherical biased-ReLU P -trainable networks with d=5 . Red curves are derived from the approximation bound, while blue curves show training results for a fixed RKHS target. Increasing the fixed initialization scale τ≥1 raises the mismatch constant from its minimum at τ=1 . Both theory and training show qualitatively similar transition shapes and sharper transitions at larger τ . Quantitative differences are expected because training also depends on finite sampling, the optimizer, and the training budget. Threshold P0.1 marks 90% normalized gain. Shaded bands indicate 95% bootstrap intervals. See experimental details in Appendix E.1 .
Figure 3: A P -trainable network with hidden layers of equal width W . Each hidden layer contains ⌊PW⌋ trainable neurons and W−⌊PW⌋ fixed neurons. Thus, the network has O(PW2L+W) trainable parameters out of O(W2L) total parameters.
Figure 4: Schematic illustration of the mismatch factor κγP(λ) . The sampling density closely follows the ridge leverage density in (a), but assigns insufficient mass near the right peak in (b).
Figure 5: Minimum trainable proportion for 90% normalized gain, with α=2 and ε=0.1 . Shaded region above Pε(r) satisfies G(P)≥1−ε . The endpoint at r=1 represents the limit 1−ε as r→1+ .
Figure 6: Scaled spherical initialization. Increasing τ shifts fixed-neuron parameters toward the poles b=±1 . The right panel schematically shows how greater mismatch can sharpen the gain at small P .
Figure 7: Normalized gain predicted by the spherical biased-ReLU bound in dimension d=20 ( α=22/19 ) for increasing τ . Gray dashed guides mark 90% gain and the endpoint G(1)=1 .
Figure 8: Architectural comparison with 220 hidden neurons and four trainable neurons. In (a), 20 first-layer neurons form 10 pairs, each feeding a block of 20 fixed neurons with tied incoming weights. In (b), the second-layer budget is reallocated to the single hidden layer. Only representative fixed neurons are shown.
Trainable Neurons
Architecture
Error Bound
Gain
Bound Ratio
2 in the first layer
Three-layer f3
2.22×10−2
0.7998
E(2)(2)E(3)(2)≈0.9539
Two-layer f2
2.33×10−2
0.7902
4 in the first layer
Three-layer f3
2.82×10−5
0.9997
E(2)(4)E(3)(4)≈0.0206
Two-layer f2
1.37×10−3
0.9877
Table 1: Approximation error upper bounds and normalized gains with two or four trainable hidden neurons. Both baseline bounds equal 1/9 . Each gain is normalized relative to its architecture’s bound at mfree=20 .
Figure 9: Target functions in the numerical experiments. Targets f1∗ and f2∗ are shown as curves, while f3∗ is shown as a heatmap, with color indicating the function value.
Item
Value
Item
Value
Batch size
Full batch
Optimizer
Adam
Training steps
12,000
Base LR
10−3
Gradient clipping
10.0
LR schedule
ReduceLROnPlateau
Early stopping
Disabled
LR factor
0.5
Precision
float32
LR patience
400
Hardware
Single NVIDIA A100
LR threshold
10−6
Table 2: Experimental configuration with ReLU activation.
Figure 10: Training results for f1∗ with ReLU activation. The top and bottom rows show depth and width variation, respectively. The left column reports the geometric mean of the best training loss across 21 repetitions, and the right column shows the normalized gain.
Figure 11: Training loss and normalized gain for f2∗ . The layout and axis scales follow Figure 10 .
Activation
Target
E(0)
E(1/32)
E(1)
G(1/32)
G(1/8)
GELU
f1∗
9.70×10−5
2.13×10−6
3.33×10−7
0.9814
0.9927
f2∗
6.80×10−1
1.78×10−1
7.69×10−4
0.7390
0.9723
f3∗
1.72×10−1
1.59×10−3
4.24×10−6
0.9908
0.9996
tanh
f1∗
3.63×10−3
1.96×10−5
4.69×10−7
0.9947
0.9997
f2∗
6.18×10−1
3.17×10−1
3.30×10−4
0.4867
0.9552
f3∗
6.35×10−2
4.18×10−3
1.11×10−5
0.9343
0.9973
Table 3: Training losses and normalized gains for GELU and tanh with depth L=5 and width W=64 . Losses are geometric means of the best training losses across 21 repetitions.
Appendix figures & tables5 assets
Supplementary material from the paper’s appendix.
Appendix
Symbols
Descriptions
X\penalty&\penaltyΘ
The input domain and the parameter space.
ϕ(x;θ)
Feature map and its reweighted form ϕP(x;θ) .
F(W,L)
The neural network class with W width and depth L in ( 2.1 ).
FP(W,L)
The partially trainable counterpart of F(W,L) in ( 2.2 ).
kρ(x,x′)\penalty&\penaltyTρ
Kernel induced by ϕ(x;θ) ( 2.5 ) and the corresponding integral operator ( 2.6 ).
Hρ
Reproducing Kernel Hilbert Space (RKHS) induced by ρ in ( 2.8 ).
Appendix
Table 5: Notation used throughout the paper.
Figure 2 (reproduced). Theoretical and numerical phase transitions for two-layer spherical biased-ReLU P -trainable networks with d=5 . Red curves are derived from the approximation bound, while blue curves show illustrative training results for a fixed RKHS target. Threshold P0.1 marks 90% normalized gain. Shaded bands indicate 95% bootstrap intervals.
Figure 13: Training results for f1∗ with GELU activation.
Figure 15: Training results for f3∗ with GELU activation.
Figure 17: Training results for f2∗ with tanh activation.
Understanding how structured internal structure emerges during neural network training is central to the study of deep learning. We investigate this phenomenon through the group composition task, where a two-layer neural network is trained to predict g1⋆g2 for elements of a finite group G. By lifting the projected gradient flow to the Fourier domain, we demonstrate that the training dynamics are governed by a Riemannian gradient ascent on a representation-theoretic energy functional. We prove that, under random initialization, this flow drives each neuron to converge almost surely toward a single irreducible representation, while the cross-layer Fourier coefficients achieve a rotational rank-one alignment. This framework provides a representation-theoretic account of feature learning and characterizes a novel low-rank compression phenomenon for matrix-valued group representations. Moreover, for Abelian groups, we provide a complete population-level description: random initialization promotes uniform diversification across nontrivial representations and induces Haar-uniform phases, jointly approximating the indicator via a majority-vote mechanism. We further prove that both phase alignment and representation competition emerge with exponential convergence rates.
Jianliang He, Leda Wang, Fengzhuo Zhang +2
Department of Statistics and Data Science, Yale University
Universal approximation theorems provide a mathematical explanation for the expressive power of neural networks. They assert that, under mild conditions on the activation function, feedforward neural networks are dense in broad function classes, such as continuous functions on compact subsets of Rd, Lp spaces, or Sobolev spaces. Over the past four decades, these qualitative universality results have evolved into a rich quantitative theory addressing approximation rates, parameter efficiency, and the role of architectural features such as depth and width. This survey presents several glimpses into this theory. We review classical density results for single-hidden-layer networks, as well as quantitative bounds that relate approximation error to network size and smoothness assumptions on target functions. Particular emphasis is placed on depth--width trade-offs and on results demonstrating that deeper architectures can achieve superior parameter efficiency for structured function classes. In addition to standard feedforward neural networks, we also review recent developments on Kolmogorov--Arnold Networks (KANs), which offer an alternative architectural paradigm and whose approximation-theoretic properties have begun to attract significant theoretical attention.
Soumendu Sundar Mukherjee, Himasish Talukdar
Statistics and Mathematics Unit, Indian Statistical Institute, Kolkata
The success of neural networks is largely attributed to their ability to learn useful representations from training data. However, known results that prove a computational advantage of learned features over fixed ones are restricted to specific input distributions. We settle the COLT open question of Feldman, Kamath, and Srebro (2026) by showing that this advantage can persist in the distribution-free setting. We construct a family of hypothesis classes that can be efficiently learned by a natural gradient-based algorithm on a two-layer ReLU network, but cannot be represented by linear predictors over any fixed feature map with polynomial dimension (and runtime). Specifically, for any sufficiently small error and any sufficiently large runtime budget R (depending on the error), there exists a hypothesis class that the neural network learns under any input distribution to the desired expected classification error in time at most R, while the dimension complexity (governing the dimension needed by linear predictors) is superpolynomial in R.