Separable Neural Networks: Approximation Theory, NTK Regime, and Preconditioned Gradient Descent
Authors: Yisi Luo
Deyu Meng
Venue: ICLR 2026 Poster (2026)
Keywords: Separable Neural Networks
Approximation Theory
Preconditioned Gradient Descent
Neural Tangent Kernel
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning
TL;DR: We derive theories and propose an efficient preconditioned gradient descent for separable neural networks.

Abstract: Separable neural networks (SepNNs) are emerging neural architectures that significantly reduce computational costs by factorizing a multivariate function into linear combinations of univariate functions, benefiting downstream applications such as implicit neural representations (INRs) and physics-informed neural networks (PINNs). However, fundamental theoretical analysis for SepNN, including detailed representation capacity and spectral bias characterization \& alleviation, remains unexplored. This work makes three key contributions to theoretically understanding and improving SepNN. First, using Weierstrass-based approximation and universal approximation theory, we prove that SepNN can approximate any multivariate function with arbitrary precision, confirming its representation completeness. Second, we derive the neural tangent kernel (NTK) regimes for SepNN, showing that the NTK of infinite-width SepNN converges to a deterministic (or random) kernel under infinite (or fixed) decomposition rank, with corresponding convergence and spectral bias characterization. Third, we propose an efficient separable preconditioned gradient descent (SepPGD) for optimizing SepNN, which alleviates the spectral bias of SepNN by provably adjusting its NTK spectrum. The SepPGD enjoys an efficient $\mathcal{O}(nD)$ complexity for $n^D$ training samples, which is much more efficient than previous neural network PGD methods. Extensive experiments for kernel ridge regression, image and surface representation using INRs, and numerical PDEs using PINNs validate the efficiency of SepNN and the effectiveness of SepPGD for alleviating spectral bias.

Published as a conference paper at ICLR 2026
SEPARABLE NEURAL NETWORKS: APPROXIMATION THEORY, NTK REGIME, AND PRECONDITIONED GRA- DIENT DESCENT
Yisi Luo', Deyu Mengi 1*
Xi'an Jiaotong University
yisiluo1221@Ea www.2aiffo.ii..mmmmmmmmmm..mmm.m com, dymeng@mail. edu.
ABSTRACT
Separable neural networks (SepNNs) emerging neural architectures that sig- nificantly reduce computational costs by factorizing a multivariate function into linear combinations of univariate functions. benefiting downstream applications such as implicit neural representations (INRs) and physics-informed neural net- works (PINNs). However, fundamental theoretical analysis for SepNN, including detailed representation capacity and spectral bias characterization & alleviation, remains unexplored. This work makes three key contributions to theoretically un- derstanding and improving SepNN. First, using Weierstrass- and universal approximation theory, we prove that SepNN can approximate any multivariate function with arbitrary precision, confirming its representation com- pleteness. Second, we derive the neural tangent kernel (NTK) regimes for SepNN, showing that the NTK of infinite-width SepNN converges random) kernel under infinite (or fixed) decomposition rank, with corresponding convergence and spectral bias characterization. Third, we propose an efficient sep- arable preconditioned gradient descent (SepPGD) for optimizing SepNN, which alleviates the spectral bias of SepNN by provably adjusting its NTK spectrum. The SepPGD enjoys an efficient (nnD) complexity for n² training samples, which is much more efficient than previous neural network PGD methods. Extensive experiments for kernel ridge regression, image and surface representation using INRs, and numerical PDEs using PINNs validate the efficiency of SepNN and the effectiveness of SepPGD for alleviating spectral bias.
approximation
deterministic (or
INTRODUCTION
Separable neural networks (SepNNs)) are class of neural architectures that represent a multivari- ate function as linear combination of univariate functions, each parameterized by a lightweight factor neural network (Liang et al., 2022; Cho et al., 2023; Luo et al., 2024). A key advantage of SepNNs lies in their ability to significantly reduce computational costs by reducing network prop- agations. The computational efficiency makes SepNN particularly advantageous and efficient in applications such as implicit neural representations (INRs) (Liang et al., 2022; Luo et al., 2024), innfomee neural networks (PINNs) (Cho al., 2023; Yu et al., 2024), and neural radiance fields (Chen et al., 2022). Compared to other efficient architectures for neural networks, SepNNs hold unique efficiency advantages. Especially, classical line of work employs tensor decompo- sition to factorize the weights networks (Liu & Parhi, 2023), thereby reducing the number of parameters. This efficient architecture is the most closely related SepNNs. However, SepNNs are motivated by fundamentally different idea. Rather than decomposing the network weights, the principle of SepNNs is separate the input vector into multiple smaller inputs and process each input using factor networks. This design uniquely improves efficiency in scenarios involving coordinate-based neural networks and function evaluations on grids by reusing the factor outputs. Such structure is particularly advantageous in applications like INRs (Liang et al., 2022), which map coordinates to pixel values, and PINNs (Cho et al., 2023), which map coordinates physical
"Corresponding author. Code of SepPGD is in https: //gi thub. com/ homm/iss /isii luoo/ seppei

---

Published as a conference paper at ICLR 2026
fields. Moreover, SepNNs not only facilitate efficient training, but also offer improved interpretabil- ity and robustness by leveraging low-dimensional representations and interpretable factor modeling, demonstrating strong potential for scientific applications such separable operator learning (Yu et al., 2024), radio map construction in wireless communication (Yuan et al., 2025), geophysical full waveform inversion in Earth science (Chen et al., 2025), and transcriptomics analysis in bioin- formatics (Song et al., 2023). Therefore, the structure and efficiency of SepNNs hold important value across a variety of practical machine learning applications. We make more discussions on the efficiency advantage of SepNNs in Section A.I.
Formally, D-variable SepNN fe(x1, .n)) can be expressed as
(Zn)) fe ,D) = L(fe, (2:), .. (ea))."..,, : 1 - R.
where denotes a type of linear combination that encodes the interactions between different uni- variate factor functions {fe,(zz)) [2=))==1 (the factor functions [,ee, )2= are parameterized by univariate neural networks, such as multi-layer perceptrons (MLPs)), and θ { Op are learnable parameters. In the bivariate case D = 2. the inner product is a classical (if not only) choice for L (see for example (Liang et al., 2022; Wang et al., 2025)):
fe x2) fe, (z1) fe, R² R,
where /e, (x1), (x2) R + R are factor functions mapping separated inputs to Rt-dimensional latent vectors, and R serves as a "rank" parameter that determines the representation capacity of the SepNN. In the multivariate case where D > 2, multiple alternatives exist for defining the linear com- bination L.. A natural and widely-used option the tensor canonical parafac (CP) decomposition (Kargas & Sidiropoulos, 2021), which will be the primary focus of this study:
R
(CP) fa ;.)) Σ (fe, (21)), (fo, (fD)) RD + R
which computes the inner product between D factor functions (Fe) R - 1 and (fe, (x.)),, denotes the r-th component of fe, (za). The CP SepNN (2) degenerates into (I) when D = 2. In addition, other stochastic tensor decomposition formulations can be considered to construct the SepNN. For instance, the tensor-train (TT) decomposition represents multivari- ate functions by a sequence of dimeesiinni tensor functions (Gorodetsky et al., 2019; Zhou et al., 2025), and the tensor Tucker decomposition introduces an additional core tensor C to encode weighted multilinear relationships into SepNNs (Luo et al., 2024):
Rg
Ra
RD
(TT) fe(z1.... ,ID)
Σ ED-1=1
(=1))., (fez (fep (fen (3)
n= m==1
(Tucker) fo(a1, .DD) C x1 fa, (II) x2... xD fep (xD) 12 R.
Here, C RRIx-.RRR denotes the core tensor in the Tucker decomposition model, (RI, Rp)) denotes the TT or Tucker rank of the model, Xa : x x RRd + R x..x..x1 x. Ray1xx XRD denotes the tensor product between tensor and a vector, i... Xa (Ia)),
Rd is the factor output in the Tucker (ra) == (unfoll (Ia),, where (za) E R model, unfold,: R x..x RD + R Rllzza Ry x RR, denotes the unfolding operator from tensor to matrix, and fold, Rl R2 R. XRxx x..a1x---RR denotes the folding operator from a vector to a tensor. The (xa))ra denotes the (ra-1- -th output component of the matrix- valued univariate function for (xz) IR + RR Rx in the TT model. The aforementioned linear combinations L can be viewed as specific instances within the generalized linear Einstein summation for multi-dimenniioal array (Ahlander, 2002). Furthermore, nonlinear combinations (e.g., nonlinear activations (Li et al., 2025b)) can also be considered to enhance the stochasticity among factors.
The efficiency advantage of SepNNs comes from its separability nature. Especially, when training on D-dimensional grid tensor with each dimension containing n training samples (for instance, 1, 2. n,, d -d= 1,. D}. which contains n training samples), the SepNN only needs to query nD times of inputs by querying the separated input za in each dimension via factor functions and then combining the outputs through the linear combination L. Hence, the computational complexity of a SepNN scales as O(nD) in an epoch, compared P) for conventional neural network (Cho al., 2023; Luo al., 2024). This
with training inputs of the form { .DD Z
2

---

Published as a conference paper at ICLR 2026
efficiency superiority makes SepNNS advantageous in downstream applications such as INRs (Liang et al., 2022; Luo et al., 2024) and PINNs (Cho et al., 2023; Vemuri et al., 2025).
While SepNNs have enabled a variety of promising applications, their theoretical foundations main relatively underdeveloped, hindering a deeper understanding of their representation capacity and optimization behaviors. In this work, seek address the following fundamental questions garding the theoretical aspects of SepNNs: 1) Do SepNNs possess sufficient representation capacity to approximate any continuous multivariate function in Euclidean space? How can we character- ize the training dynamics of SepNNs and identify any inherent spectral bias during optimization? 3) How can the spectral bias of SepNNs be mitigated further enhance training efficiency? To address these fundamental questions, this work makes the following contributions:
Using a novel combination of Weierstrass-based approximation and universal approxi- mation theories, we rigorously establish an approximation theorem that SepNNs possess the capacity to approximate any continuous multivariate function with arbitrary precision, thereby confirming their representation completeness.
We derive the neural tangent kernel (NTK) regimes for SepNNs under different asymptotic conditions. The SepNN's & NTK converges to a deterministic kernel under infinite width and infinite rank, and converges to a random kernel under infinite width and fixed rank, provid- ing new insights into the spectral bias characterization and training behavior of SepNNs.
We further propose a scalable separable preconditioned gradient descent (SepPGD) method that provably adjusts the eigenvalue distribution of NTK matrix, effectively alleviating spectral bias of SepNNs. The SepPGD achieves a significantly lower computational com- plexity of (nD)) for n training samples, which is much more efficient than existing neu- ral network preconditioning methods. Extensive experiments across various downstream tasks including kernel ridge regression, image & surface representation using INRs, and PINNs demonstrate the improved efficiency and effectiveness of our SepPGD approach for alleviating spectral bias of SepNNs.
APPROXIMATION THEORY OF SEPNN
Approximation Theory. For any continuous multivariate function fz11.... 2D) defined on compact set, it is well-established that standard neural networks such as MLPs with suitable acti- vation functions can approximate it to arbitrary accuracy (Leshno et al., 1993; Pinkus, 1999)-a result known as the universal approximation theorem. However, such a universal approximation theory remains lacking for SepNN structures. To fill this blank, our first contribution is to establish a universal approximation theorem of SepNNs (including CP, TT, and Tucker (2)(3)) as follows.
Theorem 1 (Universal approximation theorem of multivariate SepNNs). Let X; C R C R. ,ND C. R and X = Xi x X2 x ... X ĀD C. R2 be any compact sets, and let f(x): -X-RR For any statements hold, in which all MLPs are drawn in the set (W2o(W11 + b): W₂ E xW W, E
be continuous multivariate function where x := (I1,-.. ,ID). "I,..)
the following
gWx1 x1 be be RW, W, W E N43 with a a non-polynomial function
(CP) There exist rank R E N+ and univariate MLPs fe. : Xa - R (d=1, 1,...,,) such that
sup xEX
(())
(Et),,
((ep(())) <e.
(TT) There exist ranks R1, Rn- E N2 and univariate MLPs Sea Xa + RRR- Ra (d 1.
D, Ro
Rn such that
R1
R2
an-1
sup x
[())
Σ "D-1m1
(m))),)) (Jeg(1))) ... (.e (ID)) <e.
(Tucker) There exist ranks Ri,". RD E N4. univariate MLPs fei Xa + R (d = 1,..... D), and core tensor C E R RRR.x.. x..x RD such that
sup scx
f(x) Cxi fe, (z1) x.... XD fe (T)) <,
3

---

Published as a conference paper at ICLR 2026
where xa (R (R X x BRR. Rd) -
R Ra-1 Re- X denotes the mode-d spe-
cific product between a tensor and a vector.
The theorem states that any continuous multivariate function on compact sets can be well approxi- mated by either the CP, TT, or Tucker SepNNs. The detailed proof, which is based on the combina- tion of WeieeeWeissss theorem (Fedorova, 2002) and universal approximation theorem (Leshno al., 1993), placed in Appendix Section A.5. We go through the proof sketch as follows.
First, taking the CP SepNN (2) as an example, we consider the associated separable function class:
A = {g: x R. g(1) ,.N)
Σ (sr(za)), ... ((n())))))))))))))((())) N, (ga(zx)), E C(da))
The function class A consists of all separable functions that can be expressed in the CP form, using the linear combination of vector-valued continuous univariate functions ga Xa - RR defined on compact sets Xa. By slightly extending the classical universal approximation theorem (Leshno al., 1993) to vector-valued functions, we show that each ga(xa) can be approximated by MLP with non non-polynomial activation functions. Hence, for any function in A, there exists a SepNN that approximates up to arbitrary precision-a fact that can be formalized by bounding the total approximation error via the Cauchy-Schwarz inequality across the errors of the factor MLPs.
therefore remains show that dense C(X)), the space of continuous functions over X. This would imply that any continuous multivariate function can be approximated arbitrarily well by an element of A, and consequently by SepNN. To establish the density of A, we leverage the Stone- Weierstrass theorem (Fedorova, 2002), which asserts that a function class defined on compact set X is dense in ( if it: (I) contains the identity function; (2) separates points X' (i.e., for any * b in X, there exists g A such that g(a) # g(b)); and (3) is closed under algebraic operations. We carefully examine that A meets these requirements. By combining this with standard universal approximation results, we conclude with the universal approximation capacity of SepNNs.
Related Work. (Cho et al., 2023) provided the approximation theory for the bivariate SepNN (1). Their proof is based on the orthogonal basis functions construction for the tensor product function space. Compared to this prior art, our approximation theory extends to any multivariate function approximation with D 2 and more types of SepNNs such as TT and Tucker, and includes the result in (Cho et al., 2023) as a special case when D = 2 for CP SepNN (2). Furthermore, our proof offers a simpler alternative against (Cho al., 2023) for the D Another work (Yu et al., 2024) deduced the approximation theory for separable physical-informe operator network, which is related to the CP SepNN (2). Their proof is based on the separability of the sine activation function using trigonometric angle addition and universal approximation theory. Compared to this work, we characterize a more general class of SepNNs using any non-polynomial activation functions and deduce the approximation error more systematically for various types of SepNNs. Our proof technique unified and broadly applicable to these structures, such as separable operator network. The SepNN is also closely related to the Golmogorov-Armole network (KAN) (Liu et al., 2025), which represents learnable neurons as weighted summations of independent spline bases and serves fundamental architecture in seientific applications (Li et al., 2025a). It is promising direction to extend the suggested proof technique to KAN approximation and its variants.
case of CP SepNN.
3 NTK REGIMES AND SPECTRAL BIAS CHARACTERIZATION
NTK Regimes. While the SepNN is demonstrated to be a universal approximator for multivariate function representation, its training dynamics remain poorly understood even for classical learn- ing problems with gradient descent. We borrow the theoretical tools of NTK (Jacot et al., 2018; Arora et al., 2019a) and aim to characterize the training process of SepNNs via associated kernel regression. Our main contributions are as follows. First, under the asymptotic regime of infinite network width and infinite rank, prove that the NTK of SepNN-whid the summation over factor MLPs' NTKs (Lemma 1) converges to a deterministic kernel (Theorem 2), analogous to known results for standard MLPs (Jacot et al., 2018) 8). This result allows to char-
can be expressed as
4

---

Published as a conference paper at ICLR 2026
NIK differenc
Initaal Iniial NTX diffccence
Inoiall NTX dificeence
2 2.
Variance
Variance
Mcan
Variance
NTK digemvales
8 2 S 5 3.5
Variznee
Training NTT
2
2
8 0
SepNN
ScpNNN
ScpMN
Eigenealue ixdlex
(a) Initial NTK (fix rank)
(b) Initial NTK
(c) NTK during training (d) NTK matrix spectrum
Figure I: SepNN NTK verification using ten runs over multiple random seeds for square loss opti- mization using gradient descent. (a) The difference between NTK matrices in adjacent random seeds initialization vs. SepNN width W (under fixed rank = 50). (b) The difference between NTK matrices in adjacent random seeds at initialization
SepNN width W and rank R (we set W R). (c) The difference between NTK matrices at 100 training steps and at initialization over ten random seeds. (d) The NTK matrix eigenvalue distribution initialization over ten random seeds.
acterize the convergence rate of wide SepNNs and to identify spectral bias related to the eigenvalue distribution the NTK matrix!.
Lemma 1 (NTK of CP SepNN). Let the multivariate CP SepNN be defined as fe(11. .DD) = Er= (fe, (z1)), (fe, ... (fe, (#D)), RD + R. where each fe. R + E is parametric MLP with parameters Od. and θ 10,,... θp) is the collection of all parameters.
Then the NTK of fe. defined as Ke == (V))e(x), Vefe for (I1, ,DD) and
x' (x',,'. ,I'D), is given by
1 D
Ke(n, x') )= = Σ
as(a)) (ta, d=1
(4)
where (xa, E RRRR is the NTK matrix of the d-th factor MLP ses with elements Ke,(aa, a'd)), = (Ves (Jea(sa)), Vo, (Je. (()))) and aa(æ) is a vector defined by aa(x)= = (Naaz (fa)), -aazed (fea (Ra)) "M. IIaz (fe (zx)) R) ERR.
Theorem 2 (Deterministic NTK under infinite width and infinite rank). Let the CP SepNN be defined as fe( ,ID) 1 Et= (fe, (z1)), (fe, (22)), (fep (aD)), RD E. where each factor MLP fe, R Rt has the architecture fe, A (W W.) with Wi,d Rx1 ba E W W2, E Rxx and a differentiable activation function with derivative à. Let each element of W1,d, ba, W2,8 be independently initialized by NO. 1). Then, as both the width W + 0o and the rank R + 20, the NTK of fe converges almost surely to deterministic kernel
VR
Ke(x, x') Ang. k(aa, a'd) II car (Na s'r);
d'vdd
where 2(( 1v..b-110.11 (o(wza b)or + 6)) and k(za,z)) calws, x'd) + Eu, ( (ó(uaa + b)å(wr's, b) (aax's + 1)).
Remark 1. The proof of Lemma 1 and Theorem 2 are placed in Appendix Sections A.6-A.7. While we consider the two-layer MLP in Theorem 2, it is straightforward to extend to multi-layer MLPs or other network structures by utilizing the corresponding NTK formulations (Arora el al., 2019b).
Using similar arguments to slundard NTK analysis (Jacot et al., 2018; Aroru et al., 2019a), it is easy to show that the deterministic NTK of SepNN also stays fixed (in terms of a small error) during training when W, R oo (under square loss function and infinitely-sman learning rate). This can be achieved by bounding the difference of NTK at two training time points using O Aa) and ( w related the small movement of each weight. Such asymptotic analysis of NTK during training is formally analyzed in Appendix Section A.4.
Remark 2.
For simplicity, the NTK analysis is primarily conducted for the CP SepNN (2), while we believe it can be readily extended TT and Tucker SepNNs. For the CP SepNN, we introduce a scaling factor v in SepNN ensure the convergence of NTK, which does affect the universal approximation Theorem 1.
5

---

Published as a conference paper at ICLR 2026
Spectral Bias Characterization Consider training pairs {æ;, Voli= and square loss minimization: mine Σi= (f. - y:)² with fe a CP SepNN. Using the same argument as classical NTK analysis (Jacot et al., 2018; Arora et al., 2019a), under infinitely small learning rate, the dynamics (x,)) E R" under standard gradient descent optimizer would follow du(t) = (((())((()) - y), where (l)) and (() E |R respectively denote the weights and NTK matrix of the SepNN at training time t over training samples {æt) (i.e.. (K() = (2 æt)), and y (
of network predictions u(t) (fe())())
di
No.) . If the NTK of the SepNN stays fixed during training (as is expected for SepNNs with sufficiently large width and rank), the dynamics become du(() = K (u(t)) y) where K denotes the fixed NTK matrix. Denote the eigenvalue dt
decomposition of K as K = Ein N,,;u," where A1 2 ... 2 An N 0 are eigenvalue and 11,""" Un are orthogonal eigenvectors. Multiplying both sides by Vi, we obtain d As (u(t) - -y))- This differential equation has an analytical solution: - K(u(t)- y) -
de (v.T uu)))
0, (u(1) - y) = exp (v. (m(0) v))
(5)
Hence, the training error (u(t) ((6))-y)) y) and its convergence rate can be characterized by the eigenvalues of the NTK matrix. Note that {wt.} form an orthogonal basis, hence (u(()= y) >i= V2" (u(t)-
y). Each term d.d (u(t) - y) decays exponentially due to the exp (-x,t) term in (5), driving the total training error (u(()= y) converging to zero as well. The components of labels y that project onto the eigenvectors v, with larger eigenvalue Ar converge faster than those correspond to smaller eigenvalues due to the exp (-X,t) term, a property known as the spectral bias of neural networks trained with gradient descent (Geifman et al., 2024; Shi et al., 2025; 2024). This indicates that convergence is slower along directions corresponding to smaller eigenvalues, often requiring more training steps if the condition number of NTK matrix is large. The NTK-based convergence rate applies to SepNNs as well, hence SepNNs also exhibit inherent spectral bias due to the uneven eigenvalue distribution of the NTK matrix (Fig. I(d)). In Section we introduce an efficient SepPGD method to alleviate spectral bias in SepNNs by adjusting the eigenvalue distribution.
Random NTK Under Fixed Rank. In practice, the rank of SepNNs is often chosen to be smaller compared to network width to promote low- low-dimensional representations and better generalization (Liang et al., 2022; Luo al., 2024). Therefore, we further consider the fixed rank and infinite width asymptotic regime, and prove that the NTK converges to a stochastic kernel defined by Gaussian processes associated with the covariance of factor MLPs. This indicates that infinite rank R is necessary to obtain deterministic NTK by applying the large number law to vanish the covariance. Corollary (Random NTK under infinite width and fixed rank). Let the CP SepNN be defined as fe(a1," ... ,.)) = VR Ei' (Je, (ri)), (Je, ... (Sep (Jep(a))), : :RD - IR and the assump- tions in Theorem hold. Then. for a fixed rank R. as the width of the factor MLP W 0o, the NTK of the SepNN Se converges in distribution stochastic kernel
D K(aa Vam,, d=1
Ke(æ, x¹) 4
where x E. Haza (Fey (zx)), (fea (4'r)),, in which each factor (fe (I ))r =
is Gaussian process with covariance B( B((Je, (Ix )), (Jea (xx))))) calaa,,'a
Remark 3. Under the fixed rank condition, the training dynamic can not be characterized uniformly using a fixed NTK matrix as in (5) due to the randomness. However, the random NTK can at least characterize the training dynamic within a small range of training time around by using the potential stochastic differential equation and probability bound, which are promising future directions. We also empirically find that even with small rank, the proposed SepPGD method is effective in accelerating convergence and alleviating spectral bias in SepNNS (Appendix Table 3).
All NTK theoretical results are empirically validated in Fig. 1. Fig. I(a) shows that under a fixed rank R, the NTK at initialization does not converge to a fixed kernel and holds randomness even with larger network width (Corollary 1). Fig. 1(b) shows that the NTK at initialization tends to converge towards deterministic kernel with joint increase of network width and decomposition rank (Theorem 2). Fig. 1(c) shows that the NTK tends to stay fixed during training with joint increase of network width and decomposition rank (Remark 2). Finally, Fig. 1(d) illustrates the

---

Published as a conference paper at ICLR 2026
spectral bias that the eigenvalues of the SepNN's NTK matrix decay rapidly, resulting in slower convergence within components that project onto eigenvectors of these smaller eigenvalues.
Another positive property of SepNN is that its NTK matrix can be computed in parallel over multiple inputs, resulting in greater efficiency compared to computing the NTK matrices of other neural architectures (Novak et al., 2022; Mohamadi et al., 2023). In fact, the SepNN's NTK (12) admits an elegant form that allows the NTK matrix over grid inputs to be expressed as a Kronecker product of smaller NTK matrices (detailed in Appendix Section A.3), thereby improving efficiency.
4 EFFICIENT SEPARABLE PRECONDITIONED GRADIENT DESCENT
Prior Arts. The NTKKbased preconditioning methods are proposed in recent works (Geifman et al., 2024; Shi et al., 2025), which adjust the eigenvalue distribution of the NTK matrix, thereby mod- ulating the convergence rate. Especially, consider a D-dimensional data grid and n² training la- bels sorted in vector y E R" and the vector of network predictions fe (X) E R" where X E Dxn are batched inputs. The training residual is r fe( y and the square loss is |r|l2, Then, gradient descent iteration with learning rate 7) is given by θ +- θ - VVVVveeeeXX Tr. According to (5), the convergence rate is related to the spectrum of NTK matrix, denoted by K here. (Geifman et al., 2024) proposed the following PGD with a preconditioning matrix S: ④ - θ V (X) T Sr. In this way, the convergence rate is related to the eigenvalues of KS. Hence, the preconditioner S E R x is constructed to modulate the spectrum of K S so to improve convergence (Geifman et al., 2024). For np training samples, this method has complexity (nnP) by applying S. Later, (Shi et al., 2025) leveraged this method to alleviate the spectral bias of INRs. They reduced the complexity of NTK matrix application by sampling a mini-batche which enjoys O(n /p) complexity with p 1 denoting the number of mini-batches. Their precondi- tioning method can be expressed as θ + θ - V fe S.r, where X,, S,, r, are sampled mini-batches. Different from these methods, our SepPGD applies smaller preconditioners separately for factor MLPs, further reducing computational complexity.
ScpPGD and Properties. We first elaborate the training configuration of SepNNs for square loss optimization on grid points?. SepNNs exhibit efficiency benefits when applied to separable grid points (Liang et al., 2022: Cho et al., 2023). We therefore consider input points situated on grid ã1 X ... x ΦD = { zD) zd E Id. d = 1..... D} C R where each & is a discrete set (or say vector) points in F. For simplicity, we assume that each &t has cardinality n. meaning each dimension contains n training samples, resulting in a total of n. training samples. Consider
SepNN fe(x) An Er= (fe, (21)), (fe,, (oD)), Rd + R. Each factor MLP fe. R -
RR is applied in parallel to the input vector Eअ E RR, yielding factor matrix fe, E IR Rxn. The corresponding optimization model formulated as
min e
Σ(ee v.)², x. E di x x...xx RDD 2
1
Owing to the grid structure of the training data, the labels fy can be naturally reshaped into a D-th order tensor y E nx..... Let = (Ze -) E Rax--x denote the residual tensor during training, where (Ze)......s = fe(((1))) ... ".t....,a))....... (TD)i,) is the (i.,... .'D)-th )-t SepNN output.
1n
The motivation behind SepPGD is to perform PGD for each factor MLP separately. We first compute D factor preconditioning matrices { for the D factor MLPs {fe, 1221- This involves calcu- lating pseudo NTK matrix Ke,- RR n for each fe, on the corresponding input data d. E R using sum-of-logits (Mohamadi et al., 2023), followed by eigenvalue modulation as described in (Geifman et al., 2024; Shi et al., 2025). Specifically, we calculate S. I- Σ 20-1(1 A. ju.u." where (Ai, b3) } eigenvalues and eigenvectors of Ke We set the modulation function g Ag for i < 1 and g\x)) = X for i > k by following (Shi et al., 2025), which makes the eigenvalues
2(Ac)
Using grid inputs is a common training configuration for SepNNs, such as coordinate grids of images in INRs (Liang et al., 2022) and grid collocation points in PINNs (Cho et al.. 2023), which facilitate efficient parallel training. For non-grid inputs, SepNNs remain applicahle, though the computational complexity for NTK evaluation and SepPGD hecomes equivalent standard networks (Liang al., 2022; Cho al., 2023).
7

---

Published as a conference paper at ICLR 2026
of Sa more evenly distributed for the first is eigenvalues. Furthermore, denote @ the concatenation of vectors. We are now ready to present the proposed SepPGD algorithm.
Definition 1 (Separable PGD). Consider the optimization problem (6) and the SepNN fe(z) =
R E (fe, (z1)), ..- (ED)), RD + R. Given D symmetric factor preconditioning
matrices {Sa E [Rx"))_ for factor MIPS [fe))=r the SepPGD iteration is given by
D
θ θ - n D (Vey (a))
d=1
gradient factor
where Ma is the mode-d specific preconditioner defined by
Ma-
few a (#w )r:
unfolds
Σ
D (R X Sa)
ERax d= d=1,... D, (8)
1=l d' sed
RxxD-1
where the subscript f (#:)r:: refers to the r-th row of the factor matrix fe, (fxr) E ERR RRRx The X va refers to the outer product that calculates between D 1 vectors {Sea (#x)): )r; E BRIin r=1 and returns a single long vector of size 1 x n- and +r=1 denotes the concatenation between R vectors and returns an R n- matrix. The unfolda TR X.-DD
q ny xna denotes the unfolding operator from tensor to a matrix, and x denotes the mode-d tensor-matrix product, a convention in tensor decomposition literature (Kolda & Bader, 2009; Luo et al., 2024).
Remark 4 (Computational complexity). The computational complexity comparison of different pre- conditioning methods given Table 1. In terms of applying the preconditioner, SepPGD scales as O(nD) by multiplying D n-by-n preconditioning matrices {Ma) while standard NTK-based method (Geifman et al., 2024) scales as O(n)) by multiplying an n- ---by-n preconditioning ma- trix S. Moreover, the preconditioner construction stage in SepPGD is also more efficient. Specifi- cally, SepPGD constructs the preconditioner by calculating the NTK matrix and performing eigen- value decomposition for D factor NTK matrices {Ke,), }. each of size X In contrast, classical NTK-based PGD (Geifman et al., 2024) requires the same operations on a single large NTK ma- trix of size n x n?. Therefore, the preconditioner construction complexity for SepPGD scales as ( + n²2 P)) (note that NTK matrix calculation consumes O(n² P) and eigenvalue decompo- sition consumes O where P is the number of network parameters, while the classical NTK- based PGD method scales as O(n3D + m2DP). We therefore see that SepPGD is more efficient in both preconditioner construction and application.
Table 1: Computational complexity comparison (in terms of applying the preconditioner) of several preconditioning methods for nt" training samples using an over-parameterized SepNN fe: : IR R with P learnable parameters (n < P). Here, r denotes training residual, H E PxP denotes
the Hessian matrix, S E F= ="" xnp denotes the WTK-based preconditioning matrix, S, E denotes the mini-batch version of the NTK preconditioning matrix, and M. E R denotes the proposed mode-d specific preconditioner defined (8).
Proconditioning method
Gradient formulation
Complexity
Hessiann-bssed methods
H (
O(P)
Modified NTK spectrum (Geifman et al., 2024)
Vefe(X) Sr
O(n)) (n < P) O(n (p > 1) O(nD)
Inductive gradient adjustment (Shi al., 2025)
Vefe(X.)) Srr, (mini-batch)
Separable PGD (Ours)
D Vea (fa, Ma)
While the formulations in (7)-(8 seem complicated, we can more easily interpret the motivation and preconditioner construction Ma in the two- -io-dimesioona case D 2 by connecting it with classical methods (Geifman et al., 2024; Shi et al., 2025).
NNote that constructing the preconditioner (8) also involves matrix product with complexity O(n P-1). However, the primary computational cost NTNKT-baa PGD lies in the computation of the NTK matrix, which requires nigh-dimensiona derivative calculations, and the eigenvalue decomposition of the NTK matrix, which involves inner numerical iterations (Geifman et al., 2024; Shi et al., 2025). In comparison, the matrix product in (8) is orders of magnitude less expensive in practice.
8

---

Published as a conference paper at ICLR 2026
kiii ouevergmme surve (setelee))
K-0 coevergence sere (seise veuc)
Imeage reprovetaiiee (wracke))
Irage oprecertaion freise casc)
VIP (ooK)
MIP (oaa)
MEP (U0N)
MIP (00e)
Sex (189))
Sealt (988)
Exeeatio stnee (d)
Executico ther 54)
Elocoraa Eiee (0
Esecation Stzce (5)
(a) Kerne ridge regression
(b) Image representation
Figure 2: Convergence curves for KRR and image representation using INRs.
TR2 + TK and the suppositions in Definition 1 hold. Then the SepPGD iteration in (7) is equivalent to the classical NTK-based PGD as @ < θ --nVefe
Lemma 2. Let the SepNN be Se(æ)) = fe, (
Sr, where X E R 2xn are batched inputs, r vec(R ) is the vectored training residual, and $ (S1 & In + In @ Sa) E B xn² is constructed by Kronecker product. Specifically, this implies [V, (fe, M1), Ve, (fe, (#2). M2) = Vefe(X) Sr.
The proof is provided in Appendix Section A.9. Lemma 2 establishes the connection between the proposed SepPGD method (7) and the classical NTK-based PGD (Geifman et al., 2024; Shi et al., 2025) under an appropriate choice of the large preconditioner S. Although the two PGD methods are equivalent in this setting, SepPGD is computationally more efficient. This effi- ciency comes from the parallel computation of factor gradients. Specifically, the total gradient Vele(X) Sr can be written in the form of outer products like (CT A Ajvec(( (B) (see Section A.9), whereas the factor gradients (.e,(fe products like vec(ABC) in the (n)) dimensional space. This is more efficient than evaluating the matrix product (CT @ A) B) in the O(n²) dimension. The key property we are using here is the equivalence between the Kronecker product expression and the vectorized matrix prod- reC.A This allows us to decompose the large preconditioner S RT x into smaller preconditioners Ma R==x and perform the SepPGD in an efficient manner. Lemma 2 can also be extended to non-grid inputs. Especially, if we construct the precondi- tioner as = Ed Sa. then the SepPGD gradient Ve, (fe, //e,,(() ((X) )a.), Ma) for some non-grid inputs X E R Dxn (n non-grid points in D-dimensional space) is equivalent to the classical NTK-based PGD update Vefe (x) Sr under element-wise evaluation without Kronecker product structure. Here, Ma- = einsum e (Od' felee ((X)a )),;), Ea Sar; (R, n) (n) - (R)
Ma) 12_ in SepPGD are computed via matrix
uct, i.e., (C' @ A)vec(B)
n)) is the d-th precondi- tioner constructed by Einstein product, where @ denotes element-wiss product. We use this formu- lation to test SepPGD for non-grid inputs; see Section A.2.
Given the equivalence between SepPGD and NTK- PGD (Geifman et al., 2024), it therefore remains to show that the constructed preconditioner S = (S, @ I, + In @ S2) is indeed effective in adjusting the eigenvalue distribution of K Ó to accelerate convergence. This can possibly be verified, because the eigenvalue of a Kronecker product matrix S @ I, is the product of eigenvalues of S) and I,, Therefore, Š would have better spectrum (i.e., smaller condition number) than K = (Ke, & In + In 6) Ke,) since S. has better spectrum than Ke,- Suppose that K close to the true NTK matrix K (which can be verified using the NTK matrix formulation in Lemma 3). We can ultimately show that KŠ has better spectrum than K. Therefore, the proposed SepPGD could provably and efficiently adjust the spectrum of the SepNN's NTK matrix during training, effectively alleviating spectral bias. In practice, SepPGD allows the preconditioner (Ma} to be efficiently updated every ten iterations, which is computationally expensive in previous methods. It is believed that the result in Lemma 2 (and the analysis following) be readily extended to multivariate cases D > 2. Also, based on the convergence result of NTTSbbased preconditioning algorithm (Geifman al., 2024),
also deduce the convergence and solution consistency (w.r.t. standard gradient descent) of our SepPGD algorithm by using the equivalence between SepPGD and the corresponding kernel ridge regression with representer theorem. This is left for future research.
5 NUMERICAL EXPERIMENTS
The numerical results are presented to verify the effectiveness of SepPGD for improving conver- gence of SepNNs. Examples include kernel ridge regression (KRR), image and surface representa- tion using INRs, and PINNs. Detailed experimental settings placed in Appendix Section A.12.

---

Published as a conference paper at ICLR 2026
Original PSNR
MLP PSNR 26
SepNN PSNR 26.48
SepNN (SepPGD) PENR 33.30
Original Tall 1.0
MLP fol 0.985
SepNN 16
SupNN (SpPPGD)
lat 0.992
Figure 3: Visual results for image and 3D surface representation using SepPGD.
1334 1900
Gevund-truth
PINN
Seperable PINNI
Seperable PINN (ScPPCD) MS 0.037
MSE 0
MSB 0.092
MSE 0.042
Figure 4: Convergence curves and results for the 3D diffusion equation using PINNs.
KRR. Following (Geifman al., 2024), we perform KRR by using the gradients of neural network w.r.t. parameters as the feature function of kernel (see Appendix Section A.12 for detailed formu- lation and settings). We test both MLP and CP SepNN, and compare SepPGD with the classical NTK-based PGD, the modified spectrum kernel (MSK) (Geifman et al., 2024; Shi et al.. 2025). Fol- lowing (Geifman et al., 2024), we consider both noisy (standard deviation 0.01) and noiseless cases. The convergence behavior, measured by testing MSE during training, is shown in Fig. 2(a). Because the efficiency advantage of SepNN and SepPGD comes from the lower complexity in an iteration, plot the convergence curve w.r.t. execution time rather than iteration number. In noiseless case, SepPGD achieves the fastest convergence. In the presence of noise, SepPGD remains robust, while MSK has slower convergence. SepPGD improves SepNN to large margin shown in Fig. 2.
Image Representation and Recovery. We leverage INR for image representation and recovery (inpainting) by following the settings in (Sitzmann al., 2020; Shi et al., 2025). Convergence curves and representation visual examples are shown in Fig. 2(b) and Fig. 3's left. SepPGD effectively improves the convergence of SepNN by alleviating spectral bias and better capturing image fine details. Moreover, SepPGD accelerates the convergence without affecting the model's generalization (in most cases improving generalization); see image inpainting results Appendix Fig. 10.
Surface Representation. We perform surface representation by representing the volumetric occu- pancy grids of a 3D surface using INRs (Shi al., 2025). The results (under the same iteration num- ber) with intersection over union (IoU) are shown in Fig. 3's right. SepPGD effectively improves the ability of SepNN capture surface textures and details by alleviating spectral bias during training.
PINNs. We use the separable PINN (Cho et al., 2023) (CP SepNN) and perform the tests on 3D diffusion, Klein-Gordon, and Helmholtz equations using grid samples. Convergence curves using testing MSE vs. time and visual examples (under the same iteration) are shown in Fig. 4. More results are shown in Appendix Figs. 13-14. The separable PINN (Cho et al., 2023) more efficient than classical PINN, and SepPGD further enhances the convergence speed of separable PINN.
CONCLUSIONS AND DISCUSSIONS
We established the universal approximation theory for SepNNs, deduced their NTK regimes, and proposed efficient separable PGD to alleviate spectral bias of SepNNs. The algorithm was shown to be effective in various applications such as image & surface representation and PINNs. We fur- ther elaborate on the potential impact of our proposed theory and method. First, SepNNs have been attracting growing attention in various applications due to their efficient structure, such as INRs and PINNs. Numerical experiments demonstrate that SepPGD can effectively speed up convergence in applications involving INRs and PINNs (e.g., in image and surface representation and numerical PDEs). Therefore, we believe that our theory and the corresponding algorithm have the potential to benefit these fields and address related challenges. Moreover, SepNNs are also increasingly being adopted across diverse scientific domains by leveraging their efficient structure and interpretability (Cho et al., 2023; Song et al., 2023: Chen et al., 2025). Therefore, understanding the theoretical ap- proximation ability, training behavior (c.g.. NTK regime), and addressing the potential optimization challenge of SepNNs are believed to be valuable and important for these practical applications.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENTS
This work supported by the Fundamental and Interdisciplinary Disciplines Breakthrough Plan of the Ministry of Education of China (Y22055XXX100) the NSFC (No. 124B2029, 62476214), and the Tianyuan Fund for Mathematies of the National Natural Science Foundation of China (Grant No. 12426105). We thank the anonymous reviewers for the constructive and valuable comments.
REFERENCES
K. Ahlander. Einstein summation for multidimensional arrays. Computers & Mathematics with Applications, 1408:11077-11177 2002.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. Proceedings of the 36th International Conference on Machine Learning (ICML), volume 97, pp. 322-332, 2019a.
Sanjeev Arora, Simon S. Du Wei Hu, Zhiyuan Li, Ruslan Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. Proceedings of the 33rd International Conference Neural Information Processing Systems (NeurlPS), pp. 8141-8150, 2019b.
Liliana Borcea, Josselin Garnier, Alexander V. Mamonov, and Jöm Zimmerling, When data driven reduced order modeling meets full waveform inversion. SIAM Review, 66(3):501-532 2024.
Anpei Chen, Zexiang Xu, Andreas Geiger, Jingyi Yu, and Hao Su. TensoRF: Tensorial radiance fields. In 17th European Conference on Computer Vision (ECCV), pp. 333-350, 2022.
Ruihua Chen, Bangyu Wu, Meng Li, and Yisi Luo. Full-wwveform inversion with velocity model low-rank implicit neural representation. IEEE Transactions on Geoscience and Remote Sensing, 63:1-16, 2025. doi: 10. (09//GGRS.0025.354111
Junwoo Cho, Seungtae Nam, Hyunmo Yang, Seok-Bae Yun, Youngjoon Hong, and Eunbyung Park. Separable physies-informed neural networks. In Thirty-seventh Conference on Neural Informa- tion Processing Systems, pp. 23761-2378 2023.
Sven Dummer, Nicola Strisciuglio, and Christoph Brune. Rda-inr: Riemannian diffeomorphic toencoding via implicit neural representations. SIAM Journal on Imaging Sciences, 17(4):2302- 2330, 2024.
V. P. Fedorova. The Stone-Weierstrass Theorem and Spaces of Measures, volume 72, pp. 417-427. Springer, 2002.
Amnon Geifman, Daniel Barzilai, Ronen Basri, and Meirav Galun. Controlling the inductive bias of wide neural networks by modifying the kernel's s spectrum. Transactions on Machine Learning Research, 2024. ISSN 2835-8856.
Alex Gorodetsky, Sertac Karaman, and Youssef Marzouk. A continuous analogue of the tensor-train decomposition. Computer Methods in Applied Mechanics and Engineering. 347:59-84, 2019.
Yicheng Li Qian Lin Jun S. Liu Haobo Zhang, Jianfa Lai. Towards statistical understanding of neural networks: Beyond the neural tangent kernel theories. arXiv:2412. 18756, 2024.
Russell L. Herman. Generalized fourier series and function spaces. In An Introduction to Fourier Analysis. Chapman and Hall/CRC, 2016.
Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural tangent kemnl:: Convergence and gen- eralization in neural networks. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 31, 2018.
Nikos Kargas and Nicholas D. Sidiropoulos. Supervised learning and canonical decomposition of multivariate functions. IEEE Transactions Signal Processing, 69:1097-1107, 2021.

---

Published as a conference paper at ICLR 2026
Patrick Kidger and Terry Lyons. Universal Approximation with Deep Narrow Networks. In Pro- ceedings of Thirty Third Conference on Learning Theory, volume 125, pp. 2000-2327,222 2020.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations (ICLR), 2015.
Tamara G. Kolda and Brett W. Bader. Tensor decompositions and applications. SIAM Review, 51 (3):4555000, 2009.
Jachoon Lee, Yasaman Bahri, Roman Novak, Sam Schoenholz, Jeffrey Pennington, and Jascha Sohl- dickstein. Deep neural networks gaussian processes. In International Conference on Learning Representations (ICLR), 2018.
Lee, G. Wolberg, and S.Y. Shin. Scattered data interpolation with multilevel b-splines. IEEE Transactions on Visualization and Computer Graphics, 3(3):228-244, 1997. doi: 10. 109/2945. 620490.
Moshe Leshno, Vladimir Ya. Lin, Allan Pinkus, and Shimon Schocken. Multilayer feedforward net- works with nonpolynomial activation function can approximate any function. Neural Networks, 6(6):861-867, 1993.
Longlong Li, Yipeng Zhang, Guanghui Wang, and Kelin Xia. Kolmogonov-arnold graph neural networks for molecular property prediction. Nature Machine Intelligence, 7:1346-1354, 2025a.
Yanyi Li, Xi Zhang, Yisi Luo, and Deyu Meng. Deep rank-one tensor functional factorization for multi cilli-dimensional data recovery. In Proceedings of the AAAI Conference Artificial Intelli- gence, volume 39, pp. 18539-18547, 2025b.
Yicheng Li, Zixiong Yu, Guhan Chen, and Qian Lin. On the eigenvalue decay rates of a class of neural-network related kernel functions defined general domains. Journal of Machine Learning Research, 33:777 - 4023, 2024.
Ruofan Liang, Hongyi Sun, and Nandita Vijaykumar. CoordX: Accelcrating implicit neural repre- sentation with split MLP architecture. In International Conference on Learning Representations (ICLR), 2022.
Chaoyue Liu, Libin Zhu, and Mikhail Belkin. the linearity of large non-linear models: when and why the tangent kernel is constant. In Proceedings of the 34th International Conference Neural Information Processing Systems, pp. 15954 15964, 2020.
Xingyi Liu and Keshab K. Parhi. Tensor decomposition for model reduction in neural networks: A review. IEEE Circuits and Systems Magazine, 23(2):8-28, 2023.
Ziming Liu, Yixuan Wang, Sachin Vaidya, Fabian Ruehle, James Halverson, Marin Soljacic, Thomas Hou, and Max Tegmark. KAN: Kolmogorov-Arnok networks. The Thirteenth International Conference Learning Representations, 2025.
Yisi Luo, Xile Zhao, Zhemin Li, Michael K. Ng. and Deyu Meng. Low-rank tensor function rep- resentation for dimei-ddimnsionall data recovery. IEEE Transactions on Pattern Analysis and Machine Intelligence, 46(5):3351-336 2024.
Mohamad Amin Mohamadi, Wonho Bae, and Danica J. Sutherland. A fast, well-founded approxi- mation the empirical neural tangent kernel. In Proceedings of the 40th International Conference on Machine Learning. pp. 25061-25081) 2023.
Roman Novak, Jascha Sohl-Dickstein and Samuel Schoenholz. Fast finite width neural tangent kernel. In Proceedings of the 39th International Conference on Machine Learning, volume 162, pp. 17018-17044, 2022.
Allan Pinkus. Approximation theory of the MLP model in neural networks. Acta Numerica, 8: 143-195, 1999. doi: 10. 10.1017750964422900229
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In Proceedings of the 21st International Conference on Neural Information Processing Systems, pp. 1177-1184, 2007.
12

---

Published as a conference paper at ICLR 2026
Vishwanath Saragadam, Daniel LeJeune, Jasper Tan, Guha Balakrishnan, Ashok Veeraraghavan, and Richard G. Baraniuk. Wire: Wavelet implicit neural representations. In 2023 IEEE/CVF Conference Computer Vision and Pattern Recognition (CVPR), pp. 18507-18516, 2023.
Kexuan Shi, Xingyu Zhou, and Shuhang Gu. Improved implicit neural representation with fourier reparameterized training. In 2024 IEEE/CVF Conference on Computer Vision and Pattern Recog- nition (CVPR), pp. 25985-25994 2024.
Kexuan Shi, Hai Chen, Leheng Zhang, and Shuhang Gu. Inductive gradient adjustment for spectral bias in implicit neural representations. In The Forty-Second International Conference on Machine Learning, 2025.
Vincent Sitzmann, Julien Martel, Alexander Bergman, David Lindell, and Gordon Wetzstein. Im- plicit neural representations with periodic activation functions. In International Conference on Neural Information Processing Systems, volume 33, pp. 7462-7473, 2020.
Tianci Song, Charles Broadbent, and Rui Kuang. GNTD: reconstructing spatial transcriptomes with graph-guided neural tensor decomposition informed by spatial and functional relations. Nature Communicattonss, 14:8276, 2023.
Matthew Tancik, Pratul Srinivasan, Ben Mildenhall, Sara Fridovich-Keil, Nithin Raghavan, Utkarsh Singhal, Ravi Ramamoorthi, Jonathan Barron, and Ren Ng. Fourier features let networks learn high frequency functions in low dimensional domains. In International Conference on Neural Information Processing Systems, volume 33, pp. 7537-7547, 2020.
Alexander Tsigler and Peter L. Bartlett. Benign overfitting in ridge regression. Journal of Machine Learning Research, 24(123): 2023.
Sai Karthikeya Vemuri, Tim Büchner, Julia Niebling, and Joachim Denzler. Functional tensor decompositions for chysics-informed neural networks. In International Conference on Pattern Recognition, pp. 32-46, 2025.
Ting Wang, Zipei Yan, Jizhou Li, Xile Zhao, Chao Wang, and Michael Ng. Hyperspectral and multispectral image fusion with arbitrary resolution through self-supervised representations. In- ternational Journal of Computer Vision, 2025. https://doi.or//10.10000 1203-01--02------1111111
Xinling Yu, Sean Hooten, Ziyue Liu, Yequan Zhao, Marco Fiorentino, Thomas Van Vaerenbergh, and Zheng Zhang. Separable operator networks. Transactions on Machine Learning Research, 2024. ISSN 2835-8856.
Haoxuan Yuan, Zhe Chen, Zheng Lin, Jinbo Peng, Yuhang Zhong, Xuanjie Hu, Songyan Xue, Wei Li, and Yue Gao. Constructing 4D radio map in LEO satellite networks with limited samples. In IEEE International Conference Computer Communications (INFOCOM), 2025.
Ting- Wei Zhou, Xi-Le Zhao, Wei-Hao Wu, Jian-Li Wang, and Yi-Si Luo. Frequency-aware implicit neural representation for multi-dimensional data recovery. IEEE Transactions on Circuits and Systems for Video Technology, 2025. doi=10.1
A APPENDIX
A.1 MORE DISCUSSIONS
A. EFFICIENCY ADVANTAGE OF SEPNNS
We make more discussions on the efficiency advantage of SepNNs. The computational advantage of SepNNs is most relevant in certain structured settings, and does not directly imply faster training in all scenarios compared to architectures like convolutional neural networks (CNNs). We would like to clarify that SepNNs are primarily designed for problems where the input is a set coordinate points grid, such in INRs and PINNs. In these cases. the input is not a high- high-dimensiioal signal like an image, but rather a low-dimensional coordinate space. CNNs, while highly efficient for image-like data through localized convolution and parallelism, less naturally suited such
13

---

Published as a conference paper at ICLR 2026
coordinate- inputs, they rely on spatial locality and translation invariance, which may not align with the structure of the problem. In contrast, SepNNs exploit the separable structure of the grid to reduce the number of unique function evaluations from ((n)) ") (as in standard MLP applied naively to all grid points) to (nD)), resulting in faster training on grid coordinate points. This makes SepNNs particularly advantageous in training coordinate networks on grids, such as image representation using INRs and evaluating grid collocation points in PINNs. Therefore, the benefits of SepNNs are most pronounced in these structured settings.
From a mathematical perspective, the theory may inspire several promising future research direc- tions. SepNNS are inherently related to decomposition- based algebraic structures such as nonnega- tive matrix factorization (NMF) and tensor decomposition. Therefore, our NTK analysis for SepNNs provides a theoretical tool to bridge neural network optimization with classical NMF, tensor decom- position, and related scientific computing topics. Furthermore, the NTK theory can be naturally extended to separable operator learning (Cho et al., 2023), providing a theoretical tool for learning mappings between function spaces. Moreover, based on the NTK analysis, another future research line is to study adaptive feature learning regime (Haobo Zhang, 2024) induced by SepNNs, which is particularly interesting for SepNNs since they can learn disentangled representations, making them suited to extract interpretable features from multimodal data.
A.1.2 DISCUSSIONS ON THEORETICAL ANALYSIS
Our current theoretical analysis establishes the universal approximation capability of SepNNS and does not yet provide explicit approximation error rates in terms of network rank or width. In future work, we can consider function spaces spanned by Fourier bases and leveraging the decay properties of Fourier coefficients (Herman, 2016) to derive approximation error bounds with respect to the rank, in order to provide theoretical guidance for practical rank selection. This could be achieved by formulating the Fourier expansion in the SepNN form (Kargas & Sidiropoulos, 2021). Moreover, can try to characterize the approximation ability of SepNNs w.r.t. width by borrowing approximation theory for narrow neural networks (Kidger & Lyons, 2020) in future research.
While this work considers the CP-rype SepNN (which is the most classical SepNN type) to perform the NTK analysis, believe the NTK analysis be extended to TT- and Tucker-type SepNNs in a similar fashion. For TT-type SepNNs, the derivation would closely follow CP, relying on tensor products of NTKs corresponding to factor MLPs. For Tucker-type SepNNs, analogous NTK results are also expected to hold, provided the asymptotic behavior and boundedness of the core tensor C are appropriately treated. We regard this extension as valuable direction for future research.
Our current theoretical analysis does not yet provide comprehensive convergence guarantees or generalization error bounds for the fixed-rank regime. Such analysis crucial for deeper un- derstanding of the training and generalization behaviors of SepNNs. Still, we believe the present theoretical framework offers a valuable initial insight, as it establishes a convergence analysis for SepNNs under infinite rank regime. In fact, by applying probability bounds related to the law of large numbers with respect to the rank parameter Rt we anticipate that an e-convergence bound on the training residual could be derived for a fixed rank R = O(1/e),, in a manner analogous to classical probability convergence bound analyses for wide MLPs (see, e.g.. Theorem 4. in (Arora et al., 2019a)). In future work, we can leverage more advanced tools from stochastic NTK analysis and explore training dynamics beyond the convergent NTK regime (Liu et al., 2020), to provide a more comprehensive theoretical understanding on convergence and generalization of SepNNs under small rank. Moreover, in the fixed-rank regime, the factor MLPs of the SepNN converge to random Gaussian processes. This implies that their outputs serve as random feature maps for each input. The SepNN then performs a tensor product of these random features. This connection allows us to consider the well-established theoretical framework of random feature models (Rahimi & Recht, 2007) to analyze the potential property of SepNNs under fixed-rank settings, providing way to derive non-asymptotic convergence rates and generalization bounds for fixed-rank SepNN.
The proposed preconditioner in this work is designed to modulate the eigenvalue distribution of the NTK matrix K to accelerate training convergence. By applying the modulation function gy)) to smooth the top & eigenvalues, the resulting preconditioned product matrix K$ is guaranteed to have condition number no larger than K. This is because the dominant large eigenvalues reduced, leading to a more uniform spectral distribution. In future work, we can derive quantitative bounds on the condition number of the modulated NTK matrix by leveraging its eigenvalue decay properties.
14

---

Published as a conference paper at ICLR 2026
For instance, tools from (Li et al., 2024) on the eigenvalue decay rates of kernel functions could be employed. We regard this as a promising direction for further research. Regarding the effect of the preconditioner on generalization, existing studies (c.g., (Geifman et al., 2024; Tsigler & Bartlett, 2023)) suggest that slowing the eigenvalue decay of the kernel matrix can introduce an implicit regularization effect, helping prevent overfitting and improving generalization. While the current manuscript does not include a rigorous theoretical analysis of generalization, the above references provide a way for establishing formal generalization guarantees for SepPGD.
While we consider the two-layer MLP in Theorem 2, it is straightforward to extend to multi-layer MLPs or other network structures by utilizing the corresponding NTK formulations (Arora et al., 2019b). Especially, for SepNNs with multi-layer factor neural networks, we can use the correspond- ing NTK analysis for multi-layer neural networks to study their theoretical property (Arora et al., 2019b). Especially, (Arora et al., 2019b) has shown that the NTK of a multi-layer neural network (beyond two-layer) converges to a deterministic kernel under infinite width. Their results are based on the recursive formulation of the covariance matrix of hidden layers in multi-layer network (cf. Theorem 3.1 in (Arora et al., 2019b)). By borrowing this type of technique, we believe the theoret- ical result for SepNN (Theorem in our manuscript) by replacing the two-layer factor NTK k(zz, 'n2) with multi-layer NTK formulations.
be readily extended to multi-layer MLPs
Our analysis in this paper can be readily generalized to multi-output SepNN fe : : + Rous by applying multi-output NTK approximation (Mohamadi et al., 2023). Moreover, the detailed convergence and generalization bounds of SepNNs under fixed rank conditions warrants further dis- cussions. is also interesting to apply SepPGD to more applications, such implicit full waveform inversion (Borcea et al., 2024; Chen et al., 2025) and diffcomorphic autoencoding (Dummer et al., 2024).
A.1.3 RELATIONS TO KAN
The recently popular structure KAN (Liu et al., 2025) is closely related to the SepNN. Especially, each layer of KAN can be viewed as a type of SepNN. Specifically, consider the input vector (1) --)))-- #(njj"" A single KAN layer (Liu et al., 2025) (take single-output as an ex- ample), denoted ((-) : R" + R. is defined as (xx) Σÿ= (1)))) where each univariate function (.), TR -> TR is parameterized as ( who (M(TT))) + + (a(()))
Here, {c2-0) for k = 1..... K are trainable parameters, and { (B) are spline basis functions as used in (Liu et al., 2025). We observe that the output ((x)) is a linear combination (specifically, summation) of learnable univariate functions o1.5 (z)))), which shares a similar spirit with SepNNs. Therefore, each KAN layer can be viewed as a SepNN, though does not directly correspond to the CP, TT, Tucker types. The distinction lies in how the linear combination is realized. In KAN, it is implemented via simple addition of univariate functions, while in the SepNNs discussed in our manuscript, the combination is realized via tensor product (e.g., CP, TT, or Tucker). The most sig- nificant commonality between KAN and SepNN is that both architectures learn univariate functions and compose multivariate functions through linear combinations of these univariate components. This characteristic fundamentally differentiates KAN from conventional MLPs, and similarly dis- tinguishes SepNNs from their non-separable counterparts.
A.1.4 MODULATIOO FUNCTION CHOICE
We conducted a sensitivity analysis on the modulation function g()). Specifically, we compared two forms of g(A): 91 (A,,)) = A for < k. and g1 (A.) = X for i > (the version used in the experiment); g2 (>,)) = A; for i < k, and 92(A.) = X; for > A. We also varied the number of modulated eigenvalues & to assess sensitivity. The results in Table 2 below demonstrate that SepPGD remains effective under both modulation functions, and ga (A) yields better performance. Moreover, the method shows robustness to the choice of l within certain range (c.g.. A (60,90) 90)). These findings indicate that with a suitable modulation function that smooths the eigenvalue distribution, the proposed SepPGD method is not overly sensitive the specific form of gA))
15

---

Published as a conference paper at ICLR 2026
Table 2: PSNR performance image representation using INRs with different modulation func- tions.
30
40
50
60
70
80
90
100
w/o SepPGD
26.48
26.48
26.48
26.48
26.48
26.48
26.48
26.48
91 (A)
26.79
26.95
29.65
33.04
33. 30
34.28
34.21
34.06
(2
Table 3: Sensitivity analysis (PSNR) for rank R in the SepNN and is in the eigenvalue modulation function for image representation on the original sized Plane image.
Rank
100
200
300
400
500
600
700
30
40
60
SepNN
26.36 26.74
26.54
26.61 26.48 26.49
26.45
SepNN
26.48 26.48 26.48 26 26, 26.48
26.48
SepNN (SepPGD)
SepNN (SepPGD)
A.1.5 HYPERPARAMETER SENSITIVITY AND MORE EXPERIMENTS
We conduct sensitivity analysis on critical hyperparameters: the rank R in SepNN and the pa- rameter k in the modulation function g()) used in the SepPGD algorithm. The image representation results are summarized in Table 3. For varying ranks our SepPGD consistently enhances the performance of SepNN. We find that setting k > 60 in this case effectively mitigates the spectral bias SepNN by adjusting the NTK spectrum. In particular, values of k E (60, 70, 80, 90) produce desirable effect for enhancing convergence efficiency. Our SepPGD method is not overly sensitive to the choice of
The sensitivity analysis of our SepPGD w.r.t. the preconditioner update frequency is shown in the Table 4 below. SepPGD is relatively not sensitive to the preconditioner update frequency. This is because the NTK matrix would not change abruptly during training and thus the preconditioner is effective for NTK eigenvalue modulation across a number of iterations.
Table 4: PSNR performance on image representation using INRs with different preconditioner up- date frequency (number of iterations between preconditioner updates).
Update frequency
10
100
300
500
700
900
1100
ScpNN
26.48
26.48
26.48
26.48
26.48
26.48
26.48
SepNN (SepPDD)
The performance of SepPGD with different activation functions as well as the Fourier feature map- ping (Tancik et al., 2020) is shown in the Table 5 below. SepPGD improves the convergence speed of the SepNN baseline with different activation functions and Fourier encoding structures.
Table 5: PSNR performance image representation using INRs with different activation func- tion/network structure.
Activation
Sin
Cos
ReI.U
LeakyReL.U
Fourier feature +ReLU
Fourier feature-I.cokyRel.U
SepNN
26.48
21.83
18.20
30.89 20.74
18.20
30.94
SepNN (SepPGD)
33.30
30.06
20.02
.0.49
40.51
The performance with different width is shown in the Table 6 below. With sufficient width (c.g.. width>> 200), the SepPGD effective accelerating the convergence of SepNN.
The experimental results for the image representation under additive Gaussian noise are shown in the Table 7 below. Under moderate to low noise deviation, SepPGD demonstrates robustness and im- proves the denoising performance of SepNN. However, when the noise deviation is large, SepPGD tends to overfit to the noise components. This behavior is expected, as SepPGD accelerates con- vergence toward high-freyuency details, which cause fit high-frequeney noise more rapidly
16

---

Published as a conference paper at ICLR 2026
Table 6: PSNR performance image representation using INRs with different network width.
Width
100
200
300
400
500
600
700
SepNN
SepNN (SepPGD)
22.79
31.46
32.75
33.22
33.30
33.89
34.35
when the noise level is high and explicit regularizations are applied. In future work, we can introduce suitable regularizations (e.g., total variation) to enhance robustness in noisy scenarios.
Table 7: PSNR performance on image representation using INRs with Gaussian noise.
standard deviation
SepNN SepNN (SepPGD)
25.29 33,26 31,08 28.20
26.40
26.35
26.27
25.85
26.35
25.06
Moreover, we employ SVD truncation to synthesize images with varying ranks, and then apply a SepNN model with fixed rank of R 100 represent these images via INRs. The relationship between the approximation error (MSE) and the true separation rank the target image is given in the Table 8 below. It be observed that as the image rank increases, the approximation er- ror of SepNN also grows. In contrast, SepPGD effectively enhances convergence efficiency (and consequently reduces the approximation error) across different data ranks.
Table 8: Approximation error (MSE) vs. true separation rank of the target image data (Setting the model rank R 100) using bivariate CP SepNN.
Data rank
100
200
300
400
500
SepNN
0.052
0.061
0.063
0.064
0,066
SepNN (SepPGD)
0.030
0.036
0.037
A.2 EXPERIMENTS ON NON-GRID INPUTS
We further conducted experiments on non-grid tasks using INRs. Specifically, we randomly sam- pled 500 non-grid points along with their corresponding function values (fi v). fa(x,, y), fs y) from Eqs. (16)-(18) to form the non-grid training dataset. We then train SepNN to fit these non-grid samples, as shown in Table below. For non-grid data, the proposed SepPGD gradient is formulated as Ve. (/e. ((X )a.); Ma), where X E IR Dxn are non-grid input points and M& is con- structed by some Einstein products between factor outputs. preconditioner S,, and training residual (especially, M, = einsum @d ((X)ar,) .),, Σn Sar; (R. n) x (n) + (R, n)), where @ de- notes element- wise product and einsum denotes the Einstein product between matrix and vector). This formulation reduces to point-wise evaluations and yields similar efficiency and effectiveness to classical NTK-based preconditioning methods, such as the MSK (Geifman et al., 2024). Therefore, it is reasonable that SepNN (SepPGD) performs comparably to SepNN (MSK) non-grid data, while both outperform the original SepNN. The efficiency advantage of SepPGD comes primarily from the separable structure of grid inputs, which is prevalent training configuration in applications such as image grids in INRs and grid collocation points in PINNs.
Table 9: MSE performance of SepPGD for non-grid data fa y), fz 3). fz(x, y) by learning function representations using INRs.
Data
fi(a, w)
f2(2,
fa(2, v)
SepNN
0.020
0.030
0.075
SepNN (MSK)
0.014
0.024
0.058
SepNN (SepPGD)
17

---

Published as a conference paper at ICLR 2026
A.3 EFFICIENT NTK MATRIX COMPUTATION
Another merit of the SepNN's NTK is that its NTK matrix can be computed in parallel over multi- ple inputs, resulting in greater efficiency compared computing the NTK matrices of other neural architectures (Novak et al., 2022; Mohamadi et al., 2023). In fact, the SepNN's s NTK (12) admits an elegant form that allows the NTK matrix over grid imputs to be expressed as a Kronecker product of smaller NTK matrices (Lemma 3), thereby improving efficiency. For simplicity, the NTK ma- trix derivation is presented for the bivariate case D because the NTK matrix formulation for multivariate cases D > 2 would be much more lengthy.
Lemma (Exact NTK matrix of SepNN), Let the bivariate CP SepNN be fe( = VR Ex=n (Je, (Z1 )), (Se, (I, where each Sea: : :R + R 1, is a parametric MLP with parameters Od. and θ = (0), 02). Consider the grid input points (2)1a E &a, d = 1,23
where &s E IR". The NTK matrix K E R.a xn? of fe over these grid points is given by:
R (K((ee) @ (fo
K
Σ
(K
(ff @ Kf)te).
R
where (fa)):: R2Ixn denotes the r-th row of the oulput factor matrix (ea E Bax (fe, takes each element in &t input in parallel) and each smaller NTK matrix K (1,s) gaxx K|
(d = 1,2) is defined by (K(())) 2. (Ve. (fo)))
Ve. (F=(
(for((ea)))
The is in Section 10 Lemma shows that computing the NTK matrix of the SepNN on grid points only requires computing some Kronecker products between smaller matrices of size n, compared to computing the direct n² x n² NTK matrix needed by other neural architectures for n² grid points. Furthermore, we can further decrease the complexity using pseudo NTK. While computing the exact NTK matrices {K (r+(+))) } of multi-output factor MLPs fe, requires O(nR) complexity due to the f outputs, researchers usually consider computing the pseudo NTK matrix (Mohamadi et al., 2023; Novak et al., 2022) instead. In this work, we leverage the rank-one sum-of- logits approximation to approximate the NTK matrix of the multi-output factor MLP fe.. reducing complexity to Onn). The pseudo NTK of the bivariate SepNN fe is formulated as
K ~ R
K1 @ (12) fe, + (#1)
(#11 fe, (e (#1) & K2)
(10)
where K1, K2 E Raxn are pseudo NTK matrices of the multi-output factor MLPs fe, : R - R on training points क E and ेे E IR", computed using sum-of-logits (Mohamadi et al., 2023). The relative approximation error between the pseudo NTK matrix (10) and the exact NTK matrix (9), which simple weighted addition of the errors induced by K1, K2, would scale as O(VW) (network width) by using analogous arguments as in (Mohamadi et al., 2023).
A.4 FIXED NTK DURING TRAINING
Theorem 3 (SepNN NTK during training). Let the multivariate CP SepNN be defined as fe(#1, ... TD) J ER=, (Fe, (z1)), (fe, ... (Fer( : RD IR where each fe. - R is parametric MLP with parameters Oa and θ = ( ,D) is the col- lection of all parameters. Let each factor MLP fe. : R + HR has the architecture (ea = /W W2.ao(Wsaaze + bb), with W1.a E Rx bJ E R.W. W2,d E R. Rx and a differentiable activation function with derivative o. Let a. ô be Lipschitz smooth. Consider n. training samples (14,V:)2 Assume the weight (e.g.. Wi,l are initialized by i.i.d. (0. Let the input norm | le, and label yi being uniformly bounded by some constants O()). Consider standard gradient descent optimizer with infinitely small learning rate. Then, given training time t O, as both the width W + co and the rank R + oc, the NTK of fe during training converges to the NTK at initialization Kou)( 2,) + Ke (z,, 2,)) all x,, Zy E {
The proof of Theorem 3 is placed in Section A.1I. The NTK matrix of SepNN during training converges to the NTK matrix at initialization, meaning that the training dynamic of SepNN under infinite width and rank can be characterized by the corresponding linear kernel regression associated
18

---

Published as a conference paper at ICLR 2026
with its NTK, allowing the convergence analysis in Eq. (5) to be true. is also possible to bound the NTK change (e(;) - K by Chebyshev-type inequality through leveraging the variance of (ee)) - K related to + with a fixed R and small step sizes. Indeed, when W, R - oc, the variance vanishes and Ке(t) converges Ke(0) almost surely under infinitely small step sizes. With fixed Rt and small step sizes, we can instead use the Chebyshev inequality to quantify the error (e())
(e using probability bounds related R and the step size.
A.5 Proof of Theorem
Proof. The proof consists of two main steps, including demonstrating the density of the separable function classes (CP, TT, and Tucker), and approximating the univariate functions the decompo- sitions using neural networks.
We first demonstrate the density of separable function classes using the Stone- Weierstrass theorem. Consider the algebra A functions on X Xi ... x XN defined by
R
- R: gg INN Σ (g) (zr)), (ox(s))) (e)()))))))))))))))))))))))))))) A= {g: x
(9a(zx)), e C(xa)
We show that this algebra closed under addition, multiplication, and scalar multiplication. Closed Under Multiplication. Let two functions h E A be given by
Rg II (as(()))) h(x) Σ II (ha(za)), E..
R4
g(x) Σ
where (ga(#a))r: (Hd,) C(Ka) are continuous univariate functions. Their product
Rn
RR D
s(x)h((x)- = ([lllaaaa))
EI (ha(zw)))
>ΣI (a(zz)))((aa(z)))))
Define new rank R Rg For each d and each index pair (r, s) (where 1,... R), define new continuous functions
(ca(ar)); (ea(ta)),
Then we have
n D
(()))((w))
ΣII (ca(a.)).,
(=1 d=1
which is clearly in A. Thus, the CP form is closed under multiplication. Meanwhile, let two functions and h have TT decompositions:
R2
g(x)
Σ
Σ
gi
(e22))) ... -g((D))
TD-1=1
R
R
h(x)
Σ
Σ
#D-1=1
where ga(xa) E IR R%_,,xP R and ha(ar) E R xRİ are matuix-valued continuous functions with
R R2 = and R!] n² = 1. Their product is
((x) = Σ Σ
(01(21),,, (1 (12)))) (1(2)))n..)) Paym JD SD
Define new ranks - R2 for d = I,..,, D-1 1, and define new matrix-valued functions falza) as follows. For 1, (z)) a ball x Ti matrix with elements
f((1)) gu (x.).. h111)1..1
19

---

Published as a conference paper at ICLR 2026
where 1 71811 For d = 2, 2.... .. 1. is Ta-1 Ta matrix with elements
fa(aa) - sul (aa
where -d------ and tu = rd8d- For d D, (2 is TD-1 x matrix with elements
fn(an) www_)))((0ppp).) Rotooo)
Then we have
71
To
g(a)h(()))
Σ
Σ
$D-1=1
which is in TT form. Thus, the TT form is closed under multiplication. Let two functions and h have Tucker decompositions:
g(x) C X1 ((1)) X2. XD xDgD((D)
Σ mrmrr
C II (aa( d=
h1()) = Ch x1 (1(1)) ..... xp bp(ap) =
Σ Ch aD II (ha(#z)))s>
where ga(#a) E R2, ha(za) E & are vector-valued continuous functions, and Ca E R x..x XR, Ch R Ri x..x Rb core tensors. Their product
g(x)h(x)) = Σ Σ
Ch ch
Define new ranks Ta = R² Ra for = 1,.., D. and define a new core tensor Cah E x with elements
Ch Chp... Ca, sD Ch. .p*
where tu = Tasa for each d. Define new vector-valued functions fa(ss) E RT with elements
(fa(za)) (ga(za))ra (ha(za)))
Then we have
g(=))((x) = C* X1 fi (x1) X2 Xp fD(æp).
which is in Tucker form. Thus, the Tucker form is closed under multiplication.
Closed Under Addition. We verify that the function classes defined by CP, TT. and Tucker decom- positions are closed under addition. Let two functions h. be
Rg D g( "I(((((a)))) M())= E1 (lalaa)) E A. =1
ng D
==
where (ga(#a))r: (ha(#a))s E O(Ka)) are continuous univariate functions. Their sum is
Ry D
R4. EI[haaaaa
g(x) + h(x)
II
(aa(=a))
r=1d=1
s=1dm1
Define new rank R = Rg R2 and for each d, define new continuous functions sa Xa -> RR with components
(aa(()a)) (ha(we)))- r Rg + 1,... R.
r 1, Rg
(fa(za))
Then we have
g(x) h(xx) = EI(
d=l
which is clearly in A. Thus, the CP form is closed under addition.
20

---

Published as a conference paper at ICLR 2026
Let two functions g and h have TT decompositions
R
o(x) =
Σ
TD-1=1
R1
R
M(x) Σ
Σ
...
1.1
sp-1-1
where ga( E I - and ha(aa) E g are matrix-valued continuous functions with R = RD = and 2 = D = 1. Their sum is g(x) + h(x). Define new ranks Ta = R + R for d. 1, and define new matrix-valuce functions fa(za) follows. For d fi (+1) a x Ti matrix with elements
fi(2)) (g((1)) (1((1))
t 1, R2
t= R4 + +1, 1, Tı
For d = 2,,... , fa(za) is Ta-1 Ta matrix with elements
ga(xa)),us Ra
t Rd 11 u S Rag
fa(wa)en
1 R2 12 u R
0,
otherwise.
For d = D. (D(DD) is Tp- x matrix with elements
go(0D),1 bo(
t S RD-1"
(p(an)a
1 >> R D-
Then we have
TD-1
((0) h(xx)
Σ -1
Σ
(((1)). :. fD(D))
to
which is in TT form. Thus, the TT form is closed under addition.
Let two functions g and h have Tucker decompositions
g(a)) Ca X1 (x1) x2... xp (D(FD), h(x) = x1 hi(1) X2 X hD(rD),
where C9 x ch E x R and ga(ra) RR, ha( E R& are vector-valued
continuous functions. Their sum is g(x) h(x).. Define new ranks Ta R2 + Ra for 1, D, and define new core tensor C E R xT with elements
C9 upp
if i < Rg for all d,
if if > Ra for all d, otherwise.
q Rq... an
Defined new vector-valued functions fa(xa) Raa with elements
(ga(xa))r: (ha(za))) r = R + 1, Ta-
1.... R2g
(Ja(za))
Then have
g(x) h(x))()))))))(())) = C xı fi( x x fD(ØD),
which is in Tucker form. Thus, the Tucker form is closed under addition.
Closed Under Scalar Multiplication. For any CP, Tucker, or TT functions, it is easy to show that multiplying them with scalar are still CP. Tucker, or TT functions. Hence the separable function classes are closed under scalar multiplication.
Separate Points. We further verify that the function classes defined by CP. TT, and Tucker de- compositions separate points. That is, for any distinct points p * q in the compact set
21

---

Published as a conference paper at ICLR 2026
== X1 x ... XD. there exists function g in the respective class such that g(p) + 9(q). Consider the CP form:
R
(
Since p * 9, there exists some dimension dg such that Pdo 7 Ado Choose and define the functions such that for d = do. Ido Ado - IR to be a continuous function such that Idg (Pd,) * Idg (9d,) (such function exists since continuous functions can separate points in one dimension) and for d * dg 9a(#z) = 1. Then we have
g(x) = πI
ga(ms) d=1
and
g(p) gāo (páo)
II
+ gdo (gdo)
II 1- g(q).
dddd
defida
Thus, the CP form separates points.
Consider the TT form:
R
g(x) Σ
Σ
(a1()))),, (0a(#2))...>>" ( ("ggg()))))
TD-1=1
Choose all ranks R₂ = for d = 1,, D - 1. Then the TT form simplifies to
g(x: (x1)),, (02(x2)),, (
(gD((=)))), (-
Since p * q. there exists do such that Pdo * Ado Choose Id. such that (ga, (Pa. + (gdo(%a,)),, and for other d, choose Ja to be the constant function (ga(za))ın = 1. Then we have
g(p) + g(g).
(11)
Thus, the TT form separates points.
Note that CP is a special case of Tucker by setting the core tensor C as diagonal. Since the CP function class separates points, the Tucker function class separates points well.
Contain Identity Functions. We verify that the function classes defined by CP, TT, and Tucker decompositions contain identity functions (constant functions). Consider the CP form:
g(x)
EI (ga(x.))r
To obtain a constant function g(x) = for some constant c E R, we can choose R = 1, ga(aa)))) = ca where is constant for each d - 1, ... D such that D Then we have
g
Ca =
Thus, the CP form contains identity functions. Consider the TT form:
Rp Σ
(
... (g (x1)), ( ('-((((0)))
To obtain a constant function g(x) = c, we can choose all ranks R. = for d = 1,... , D - 1, and for each = 1, ..... D. (a(z)) to be a constant matrix with all elements equal to such that I Ca
Then have
(xx) =
Thus, the TT form contains identity functions.
22

---

Published as a conference paper at ICLR 2026
Note that CP is special case of Tucker, hence the Tucker function class contains the identity function as well.
By the Stone- Weierstrassss theorem (Fedorova, 2002), the CP function class A is dense in C(²) (as well as the TT and Tucker function classes). Therefore, for any continuous multivariate function R (g1 (21)), (92(x2)), (oD(xD)), such that
and 2 > 0, there exists CP function
sup #EX
(()
(91(z))), (92(22)), (on(xn)), < ~
Likewise, there exist TT function =m==1 Emy=1 Emp (9) (1) (11))., (92(22)) ... (gD(ED))ro-n.) and Tucker function C X 9l (21)
R1
X2 ... x (D(D) such that
R1 Rg
RD-1
sup mEX
f(x)
Σ
(0i(z))),,, (0a(s2))) (OD((D))) <
72
'D-1=1
sup f(x) - x1 (1(1) X2 XD gp(xD) < 2/
where each component of the factor function ga(x)) (i... (ga(I))))) is single-output continuous function defined compact set X2- The standard universal approximation theory (Leshno al., 1993) states that for any > and any single-output continuous function (ga(#a)), defined on compact sets, there exists an MLP (fe, (za)), sampled {W2o +b) W2 g1xW W1 RW x1 b E R W E ]+} with a a non munn-pployyn polonopooooomallll function such that
sup (()a(xa)) (fe, (x.))rr < 6, r= r...... zEda
Let these R single-output MLPs be {(f', (ra)), = W + 6') Therefore, we can construct a single R-output vector-valued MLP with the form
(xa) = W2o 6) R
where W2 dW ......... .... R W1 (WI ..... W TT, b (b) 6 T such that su,zexx, (ea(( (fe. (z.) < 8 for each component r = 1, 1,... R. We have thus extended the classical universal approximation theorem (Leshno et al., 1993) to vector-valued func- tions. Especially, each ga(aa) can be well approximated (in component-wise manner) by vector- valued MLP fei: Na RR sampled in the set WW2a(Wer , + b) W2 R W1 Rxx1 b E W W W E N+) with a non-polynomial activation function.
For any continuous multivariate function f X R, let the CP approximation be
s(x) Σ (an (2) ())=)()))))))))))))))))))))))))) (gn(#)))..
such that supeex [f(z) g(x) < Let the CP SepNN approximation be:
fe (m) = Σ (fe, (m))) -.. (ff
with sup,,ex, (9a(xa)), - (fe, (2a)) < 8 for d 1,... and r 1, R. The total error is bounded by
If(x) fo(w)] S [5(x) 9(x)) lm(=) - fe(w)]
R
D
Σ
II (a((xa))) dd=1
-II d=1
Since each (ga(xa))r and (xa)) is continuous on a compact set, they are bounded. Let M be common upper bound such that ((a((aa))r < M and ([ee) M for all d,r, and
E X. Using the generalized Cauchy-Schware inequality [ as H bu - Eb las
bal (IT= laj)) (ITp=441 byl) we have that for each
D
D II (Tees (xa))r D-1 max (ga(aa)) (Jer(u)))rl (aoG((ta)))-UG((())))))))) D-
II (ga(w))))>
d=1
23

---

Published as a conference paper at ICLR 2026
Thus have
D -((ed ) RDDMP1..
Σ
II (od(Faa)
Choosing 8 2-DM we have
[f()) - fe(x)) < c
2
and the approximation theory of CP SepNN is thus established.
For any continuous multivariate function f X + R, let the TT approximation be
R1
RD-1
g(x)=
Σ
Σ
r1
TD-1=1
with sup 1f(x) g(x))
i.2
Let the TT SepNN approximation be
Rp-1
fe(x) = Σ
Σ
(fe, (21)).. (fex (22)) ... (fen (TD))r--aa
1D-1-1
with x,x, ((da(T))) - (fe, (za))r,s for all d, s. The total error is bounded by
[f(=) - fa(x)) 5 (x) - g(x)) + +lg(a) fe(x)]
Σ
II Da
[[ee (ta)
Pl. DD-1
where ro = 1 and TD = (oa(Fa))aasnir (fe, (2a) on compact sets. The number of terms in the sum Er,... .D-1 is
Let M be a common upper bound for all components
I Ra. Using the generalized Cauchy-Schweer inequality N P. ITa ba S Ed= and
bal [1 (I7-at1 b;l). for each term we have the bound
D
I
(aa(aa))
DDM--28
d=1
Thus we have
D-1
19(x) fe(())
II Ra DM d=1
Choosing
2(II R.)DMP-T we have
lf()) fo(m)) < < + =
2
and the universal approximation theory of TT SepNN is established.
Let the Tucker approximation be
g(x) x1 91 (21) x.... ... x
gD(x));
with supaex [f(x) g(x:) < Let the Tucker SepNN approximation be
fe(x) x1 (x1) X2 ... x fen
with sup ((a((T))) - (s.)),r < for all d, r. The total error is bounded by: If(=) - fe(x)) S [f()) g(x)l + (g(x) fe(
< 2 + CC x1 9n (m1) X2 xD (D C x1 (ei) X2... X.D (ZD)
Using the property of mode-d product, we have
[g(=) - fe(w))
Σ
CC mpl
I (ga(=a))ne (Ta)
Ti
24

---

Published as a conference paper at ICLR 2026
Let M be common upper bound for all components (ga(#a))ra (za))r compact sets, and assume each element of bounded by N. The number of terms in the summation is [ Ra- For each term we have
D (Iaa II (sa(ra))
< D
d=1
Thus we have
D II d=
(0(z)) fe(w)]
<
Ra
NDM
Choosing
2 Rs NDDP-IT we have
[f()) fe(=)) 2
and the approximation theory of Tucker SepNN established. Note that the approximation theory of Tucker SepNN can also be directly concluded by using the fact that CP is a special case of Tucker. The proof is finally completed.
A.6 Proof of Lemma 1
Proof. The NTK is defined as
Ke(r, x') = (Vefe(>), Vofe(z'))
The gradient could decompose as
Vele(æ)= (Ve,Se(z)) VeLSe(x); Vep)e(
Thus, the inner product becomes
D Ke = Σ
(Ve.fe(x)) Vezfe(x'))
d=1
For fixed d, the gradient with respect to θ is
VeyJe(a)
Σ
II a'
(Jew (
Vea (zon)
VR
We first compute the inner product of factor gradients
(I (os (Ver (fos) Ve, (Jer
(Venfe(z), Vezfa(z'))
1 R
(Jey (cx))) d'
II
By definition, the inner product of gradients is the (r, s)-th element the NTK matrix i... (Vea (fe)( Ve, (f)))) (Ke, (Id, ='()),. Define the vector
a=(x)=
II
(xw)), II (fe,, (tw)), II (fe, (z.e)) ad
d'std
d'sd
Then the summation above simplifies to
R H
1
1 (ta,, R [a((a) z's)a
Therefore we have
(eese(()) Ve,Se(x))) 1 aa(()) (a,
R
Summing over all d yields the final NTK
Ke x') Σ (Ve)f(()), Veuse(a'))
Σ ax(x) (as
R
d=1
The proof is completed.
25

---

Published as a conference paper at ICLR 2026
A.7 Proof of Theorem 2
Proof. By Lemma the NTK of the CP SepNN is given by
1 E (a(w) (ts,
Ke(x, xt) We then analyze the behavior of this expression as W + 00 and R + cc.
R d=1
We first analyze the behavior of each factor function [e, - VW output component (j =, 1. , of the network is
W 22.1 (W. 1, + ba). The j-th
w
(x),(
W2 Wa
(ba).).
Let 2; (W1,a)x0+ + (ba): The gradients of (fe, (x)); w.r.t. the parameters are
((fe, 1 (z)) and (x)e, = 0, j' 3 j.
a(Waa))s VW
a(Wa,))s
((fo, 1
(W (z))
a(Wi,a)
VW
@(fe((a))
1
(W2 ((z).
a(ba);
VW
The (j.j')-th element of the NTK matrix is
(x, Σ (e)) (1)e,
Σ (a)) (1)) ((fe(()) ((So((x))))
a(W2,))s 8(W2,)))
a(Wi.)); a(Wi,));
O(ba):
8(ba);
For j * j', all terms involve products of independent zero-mean variables (i.e., (W2,a)5, and (W2.a) hence the diagonal elements (Ke, ()).. For a fixed j. we have
= O. Thus, the NTK matrix is diagonal. We now compute
(x)), o(fe, (x'')s a(W2,))s a(W2ddss
Σ @(fe,())) ((fo,("')) O(Wi,a): 8(Wi,));
a(fe,())), ((fe,
(x, Σ
O(b.); a(ba);
1 Σ W ((())o)()))) + Σ
( (wr (Wa.))
Σ (M(WWWa))
where 2, (W W1,a) (ba); and 2 = (W..)).z + (ba)i- Combining these terms we have
(f, = w Σ (z))o(=)))) 1 w
1
Σ [ ((Wa)).oods))))))) 1).
Taking the expectation over parameters we have
(x, (),0))) w Σ [o(z)o(4)) +
W [(Waa)). +
Since (W2,a)g; is independent of (W1,)) and (ba):. and B( 22 3 = 1, we have
((W22)33.6((2))()) ((Wa.)B...(())))00) =(o(
Thus we have
E (K, =
W Σ ((x))o(a))
+E
1 W
Σ ((2))((2))
(ax' + +1).
As W + co, by the law of large numbers, get
1 w Σ [((2)((2)) + Emo-wronn + b)o + 6)],
1
Σ (()))(())) Ema bwo + b)].
W
26

---

Published as a conference paper at ICLR 2026
Therefore we have
lim (x, D'sss = Ew.b (o(wa b)o(wr' +)) Ew (d(wr + ()o(wx' + +b]) (Nx' + +)
= =(xxx')
by definition of k(x,,') Since this limit is identical for all j. the NTK matrix Ke (") converges to ((x,x") Substituting the diagonal form of Ke, into the NTK expression
R
Ke x')
R Σ
k(aaa 2'a)
((a.(t)))
where (aa(x))), II ad , (x ))r. Consider the inner summation for each d:
R Σ R
R Σ
Va ((a(()))
II (tw))) (d'a)).
R ral1 d'sdd
The factor MIPs are i.i.d. across the output components (see (Lee et al., 2018)). and the terms (fe, (mr)),, and (Jear (x'e))r are also independent across d' By the law of large numbers, as R > 00, we have
Va -E
II ( d'v
(cle)))
EI (xx)))) (f (1a)))))
d'y
As W + oo, by the neural network Gaussian process theory (Lee et al., 2018), we have that fe. converges to a Gaussian process with covariance
E (Lar (2'ar De) = Ew bu + b)o + b)] = (xtr 2'dr),
where car (x = (= (owwx b)o + b)) is by definition. Therefore, we have
Va
car (Far, d'
II
and the overall NTK converges
Ke( x²) +
Σ k(Ta; I'd)
II car (Tar, alr)) d'ipd
as stated in the theorem. Since the convergence of each factor MLP's NTK matrix is almost sure W co, and the law of large numbers gives almost sure convergence R - oc, the overall convergence is almost sure regime.
A.8 Proof of Corollary
Proof. We prove Corollary by leveraging the results from Theorem 2 and Lemma 1. Recall that the CP SepNN is defined as
.e (T)
VR Σ (Je, (2i)), (fe,()))) ... (fep (xD)),
1
where each factor MLP fe, + R has the architecture
(aa 1
VW Wa Wi.a + ba)
with parameters initialized independently from from.N(O. (0, 1). From Lemma the NTK of the SepNN is
1 Σ
(e x²) ) ad(w) Ko, (Ma, (w)')
where (a.(w)), II )r and Ke (Ir, x/d) is the NTK matrix of the d-th factor MLP. Consider the limit the width W oo while the rank R is fixed. From the proof of Theorem 2,
27

---

Published as a conference paper at ICLR 2026
for each factor MLP fe.. W co, the NTK matrix Ke (Fd, converges almost surely to deterministic diagonal matrix
Ke, (xa, x'a) - k(xa, IR) where k(Td, x'd) ca(ra, r'd) + En ()N(..) (ō + ( + b) + 1)) and ca(za, d'a) = (w..1) (o(waa + b)o(wwx') + b)). Substiruting this into the NTK expression
Ke(wx + 2 klas, r'a)
Σ
(an(z)))
Define
Va 20)
1 R
[as( (r) (as))))))((())))
1
Σ
II (a (G (c.)).
R
Then we have
Ke(ø, x²) Kles, Vu
d=1
remains to characterize the behavior of Va(x,, 2'). The factor MLPs are initialized independently across dimensions d', and for each fixed d', the output components (Je (x&)), for 1, R
are independent and i.i.d. due to the independent initialization of W2.2' (Lee et al., 2018). As W + 0o, each output (fe, (Iw)), converges to Gaussian process with covariance function
E ((fe (x. D) (fe,, (dd)), = ca (Mar x'ar)
by the neural network Gaussian process theory (Lee et al., 2018). Consequently, W + Ke( æ') converges in distribution to the stochastic kernel
Σ klea, V'ze
where Va(æ, a') = 3/ Σ He Ta (xt))) (Jee (rr))rr and each (Je (x D) is a Gaussian process with covariance ca (Ird) ).
A.9 Proof of Lemma 2
Proof. From the construction of Ma in (8) we can see that
Mi fey R S S2R ) M2 fe, (.1) (S RS2).
where we have used the symmetry of Sq. Let A = fe, ( Rxn, B = (02 E R Rxn.
Then the output matrix of the SepNN is Ze A B. The vectorized output (let X R22nn be row-first batched inputs) is
vec 2 vec(B" A) (I, & B (ve(
For parameters O₁, the gradient given by classical NTK-based PGD is
Ve) Sr (ōvec(Zā)
Sr.
00,
Since @vec(2]] 89,
(I, 69 B
Over
we have
8e,
(Ovec(25))
(Dvec(A))
(In @ B).
00,
Thus we have
Te) Sr (Dvec(A))
00, (10))
(In 30 B)šr.
The gradient in SepPGD is
(Ovec(A)) T
(Over(A))" A1)
Ve, (1,
vec(Mi)
vec(B(R S, + +
ae,
a
28

---

Published as a conference paper at ICLR 2026
By the Kronecker product property (C* A)vec(B) vec(ABC). we can obtain
(In @ B) = (I, @ () @ I. + In @ Se)vec(R2))
= (In @ (e - S + S2R
vec(BR S1 + BS.
= veo(B(R S1 + S.R )).
Therefore we have Similarly we can show that Ve, Sr = Ve, (B, M2) These results imply that [Ve, (Se, ( Mi), Ve, (12), M2)] Vefe(X) Sr,
VaiJe(X) Sr = Ve, (A,
and hence the SepPGD is equivalent to the classical NTK-based PGD.
A.10
Proof Lemma 3
Proof. The NTK of the SepNN for two points a = (ri, and x' = (x1, is (a xt) (Va,fe(a), Va, + (Vezfe(x), fer
The gradients are
Ve, fe(x)= 1
VR Σ (fe)()))), Ve, (fe, (2:)),
VegJe(x) = VR
(z))), Vo, (eo)
Thus we have
(Ve, (er = Σ
(Se, (22)), (fer(ús)), (Ve, (fe)()))), Vo, Vo, (Jo) .),
R r,s=1
(Ve, Ve.folx1) = Σ (fo, (x1),, (fe, (x1)), (Ve, (fe)), Vo, Ve, (foz
Therefore.
R Ko(o, Σ ((a)( (fe) (Ve) (Ve, (zi),, Ve, (Je, (x1)),)
(Je, (21)),, (x1)), (Ve, (fe) Ve, (fer
Let 4u = (( (T for 1,2. Define Fd Rxn with (Fa)r. = (fe, ((ta), so
(:a)):: E Rixn is the r-th row of Fa. For r, 1,.., R. define k((1,)) E Ruxn by (Ve, ((a))) Ves (fom
The NTK matrix K E R xn? has entries
K Kanæe) = Ko (((ē)), (Lz))). ((t)),
Substituting into the above expression:
K(n)a))) = Σ ((Tes(( (1=z) ((=a()))))) (ve, (fe, ((+1)))) Ve, (Se, ((+1).))..
(f+1(()))))) (fe, (( (()),,)), (Vo, (fo, Ve, (fo, ((+2) (
According to the definitions of Fa and KS (ra) we have
K6 = R Σ (Fa))) (k(T))) v
+ (FF)).(FF)ss)) (K(
29

---

Published as a conference paper at ICLR 2026
Note that
(Fa)aa (P2)ay' ( (bz))a.
and
(Fi),,(Fi)e (fee, ( (0
(2::
Therefore, the first term in K (15)(89)) corresponds to
k @
and the second term in K (1 corresponds to
(fT. @ K/m.
Summing over r, and scaling by 1/R gives
Σ (K!' @ (Ue ( + (() r,0=1
@ k((wo)
K
R
as required.
A.11 Proof of Theorem 3
Proof. According to Lemma 1, the NTK of fe. defined as Ke(a, == (Vefe(z), Vefe(z'))
for x (Z1, (D) and x' (o',... d' is given by
1 D R
Ke(æ, x¹)
Σ
ad(x) Ke, (sa,
(12)
where (es, E RRR is the NTK matrix of the d-th factor MLP fe. with elements (e,(Ka, a'd))re = (Ves (fe)( Ve, (fe))) and (x( is a vector defined by
aa(æ)) = (Ileza (Je,, (sta)); Ila zd (Je ()2x) ) II (Je (aar)) T
E RR In the infinitely small under standard gradient descent optimizer with infinitely smaller learning rate, the dynamics of network predictions u(t) = (fere(())) (21), (ee)),...,ffo.) ffe( (z.)) E R" under standard gradi- du(t)
ent descent optimizer would follow dt
(()(((()) - y), where K(t) E Ruxx is the NTK matrix over {x,}. The dynamics of each network weight w(t) under standard gradient descent op- (fau)( Σ, (fe(o) - y:) dw(()
timizer with infinitely smaller learning rate would follow dwr(()
dt
For fixed d, denote at a=;);) RR where au(=;;) are defined using the network weights at time t, i.e., (tt) (since the asymptotic behavior of each a,(x;) is the same, we can discard the subseript d for simplicity). Denote K (ence)((ass)) (mz)a) E R We bound the difference Ke æx,) Ke(o) (z) using
Ko(o) 25) Kero 2;)1 = Σ (atkina) af afji + af af at o.
< (aa K') + (K Kb
(13)
< R (a) a. Ki) az + la] (aj aه)l + +la?(Ki, K2,) )a
We next show that the variance of the movements la a.', lay a²1, (Kt, a/. a. a.. Ki are bounded by some constants related to R, W.
K and
30

---

vW Published as a conference paper at ICLR 2026
Let the loss function be -= (ffe(xx)) y.) Then the dynamic of each weight matrix W2 2, is
d( 2(2)a.
dc
D(W2,))m
--E(e((es) y1) (a.) D( D(Wa,a)n
= - --E -v:)
1 VR
II a (crs)rr) d'
c(x))
VW
Var. O(1)
Var. O
O(1)
O )x,
VRW
where 2s (W1,a) + (ba)s and X is n.v with variance O(),, and (())) has variance (1) by the ii.d (N0,, 1) weight assumption and the scaling factor - following the neural network Gaussian process theory (Lee et al., 2018). Also, we have used the fact that D is fixed constant dimension. Therefore d(Wgdd) has variance O O(RW). Similarly, we have
d( (.1)) [(fa(x))) v.)
(x:)a
Σ
II (Te (Wa,))..d d'
dt
VW VR
O(R)
0 Y
VR
where Y has variance ORR), and thus 1 Y has variance ((1). Therefore d(Wi,a) has variance O ()) Similarly, d(bale can be written as O ( VR each weight w={), its movement (w((t) w(0) < Jo change ((=; fea(o) ((z;)a)lle, is bounded by
vn
Y for some L.V. Y of variance O(R). For
(x(=) dr. Therefore, the network prediction dr
[l.eato (ear)) = VW
ba(()) W..:0))((...(())))... + ba(O))
$ VW
(..t ll,
Var. O(8)
Var. O(W)
(2,((0)
(o(Wi, ba(()) a (O) b.(())) lea..
v
Var. O(RW)
O(t)
where we have used the Lipschitz smoothness of and the small movement of each Wi,d)s and (Wza)r.s to compose the total movement by summing over the variance. This implies that the total movement [[fea(e)((;:)a)) rank component's movement ((feate ((x(((()) ((z;)))r, - ((=;)) has variance not larger than (I).. According to the proof of Theorem 2, we have each factor MLP's NTK formulation:
fe) ((v:)a)lle, has variance not larger than O(R)), and thus each
(K,((,,))) 1
Eo(x)o(=)) 1 w
[(Wa.)B.dd 1),
(14)
W
31

---

Published as a conference paper at ICLR 2026
where 2; (W1.d) + (ba); and 2 (Wi,d) + (ba)). According to (14), for two points x. x,,', the change of factor NTK matrix
I(Ka (2, D)s, (oly-KKenon (z,, Mall
Σ -ott W
1
1
(W JM0.0000000440000000000000000000 +1|
W
W
Var. +(+))
Var. (+))
1 Σ (aat00ihccaa00000000000000000000
W www.0001...41000000000-0-001.110
Var. o
(|/) + 1/.
Var. xivv
Therefore, the change | (Kea(t) (x, 1'ss) - (2, 2'sss would have variance not larger than O(++) by summing over i and the scaling factor W. In the infinite width limit, the factor NTK matrix Ke (I,x²) E R RRxR is diagonal. Hence the factor NTK matrix Ke, (z), x²) E R R change norm ( x²) ) - ( (x,, x²) lopp has variance not larger than O( ( in terms of operator norm (the largest diagonal element). Similarly, the NTK matrix norm ( lop has variance not larger than (1) from the operator norm of a matrix. The vector ax((x) is defined
as az(x) = (faazaafe ... III (zx)))
Each element has variance O(1),
so the norm (x)(z)lle, has variance not larger than O Its change norm [[a](x) a²(x)) lle, has variance not larger than (t)) by the argument before and the neural network Gaussian process (Lee et al., 2018). By substituting all the variance bounds into (13), we see that स (af - lodi-ap)an a?) has variance not larger than N2 (H) = ( Ht a K Ki (a} - a②)l has variance not larger than 1 (R))(()O(() = O()) 1 of
w )O(R) = ( )- Hence the total error has variance not larger than O(+) 0 w When W. R oc, such variance vanishes and the total error Keece (23, ..y) K Ke(o) (a,, m.
K L ) has variance 1 O(R)O &
R²
R
R²
0 almost surely. This
implies that Ke(t) (2; (z)) - Ke (I., 2.) for all K3, Dy in training data.
A.12 DETAILED EXPERIMENTAL SETTINGS AND MORE RESULTS
KRR. Using the KRR of NTK could mimic the behavior of infinite-width neural networks because the training dynamic of neural networks with infinite width can be characterized by their correspond- ing NTK. Following (Geifman al., 2024), we perform KRR by using the gradients of the neural network w.r.t. parameters as the feature function of the kerne.. We test both MLP and CP SepNN, and compare the CP SepPGD with the classical NTK-based PGD, the modified spectrum kernel (MSK) (Geifman et al., 2024). Following (Geifman et al., 2024), we consider both noisy (standard deviation 0.01) and noiseless cases. The convergence behavior is measured by testing MSE during training. Because the efficiency advantage of SepNN and SepPGD comes from the lower complexity in an iteration, we plot the convergence curve w.r.t. exccution time rather than iteration number. All experiments are conducted on an RTX 2080TI GPU. All experiments conducted in the full-batch optimization setting to align with theories.
Specifically, given an initialization of network parameters Og E Rp (with P denoting the number of parameters), let o(x) := Ve.fe, (x) and h(2, 0') := (e', Φ(x)). Let X denote the batched inputs and y the batched labels. The KRR w.r.t. the preconditioned loss is
/1/2 (M(X 0') - w) w 2 110'11
min O'ERP
(15)
where S is the preconditioner in the NTK- PGD. We use gradient descent to optimize the parameters O' to perform the KRR by using the NTK at initialization. We utilize the Adam optimizer (Kingma & Ba, 2015) with learning rate 0.001 and weight decay 0.0001, where the weight decay serves the regularization term (fz-norm of weight vector O') in KRR. The rank of the bivariate
32

---

Published as a conference paper at ICLR 2026
KRR oorringetee curve (arieloo))
KRR ouaveigenct surve (teie caac)
IRR coneoirreeee caree (wclalees)
KRR ourreeggen curve (atiee caid)
UIP (loR)
MLP (USK)
MLP QUERO
MBB
Sex0 (S84)
lis (293))
Exscation thes
Resortice tome
Reseution tiee
Eloectriion trese (40
(ix)))
(b),f(k)))
Figure 5: Convergence curves for KRR data fi v) and f2(2,
CP SepNN is set as 100. The network width is set as 200. The depth of MLPs is set to 3. The preconditioner of each method is updated once every 10 iterations. In the modulation function g()), we set = 5 for SepPGD and l = 25 for MSK ffied-tunnd using -nd-rrr-. The activation function in MLPs and factor MLPs in SepNNs is set ReLU for KRR. We use the following analytical functions from (Lee et al., 1997) to perform the KRR testing.
1
81
fi v)
3 exp (
4 ((z - 1/2)² + (v - 1/2)²))
(16)
1.25 + cos (5.44))
f2(1,y)
(17)
6+ 663x - 1)2
fs(r, 9
(tanh(9 - 9x - 9y) + 1).
(18)
We randomly select 30 x 30 900 training points and 30 x 30 900 testing points on grids in
the interval [-1, x 1]. We add Gaussian noise with standard deviation 0.01 on the training set in the noise case. Results are averaged across five random seeds. The result in Fig. 2 lists the convergence curves for fa y). The results (convergence curves during training, i... MSE on testing sets during training) for fi and f2 are shown in Fig. 5.
Imaage ripeoreraatee (asteriker)
Ireage reproeetationn Ohiles cMR)
Ierags reproretattoo (sstedierr
Iraags reprnsepction thviss ch65)
XLLF (ASK)
MLP puski
MED (ARR)
paRt)
ScAt (SBR)
Seatt (SBK)
(ARR))
Seltt (USRO
Seal (5gg)122)
301
350
Booorion Gine 6)
Esccotico Cine 50
Euocution Kize (s)
Enscution Line 66)
(a) Peppers
(b) Plane
Figure 6: Convergence curves for image representation on downsampled data Peppers and Plane.
Offoar
(Robase)
(Popperr)
PSNIC
PONEE
PANEE
2014
Docuation
Dicatton
Dicration
Figure 7: Convergence curves for image representation using PSNR vs. iteration.
Image Representation and Recovery. For image representation, we consider using the SepNN to approximate the image by feeding the coordinates of images into the SepNNs and output the image values, a convention in INRs (Sitzmann et al., 2020; Shi et al., 2025). We use the image datasets Baboon, Peppers, and Plane* (512 x 512 x 3) as shown in Figs. 10-12.
The experiments contain two parts. In the first part, we run MLP, MLP (MSK), CP SepNN, CP SepNN (MSK), and CP SepNN (SepPGD) for image representation (Fig. 2(b) and Fig. 6) on down- sampled images with smaller resolution to fit the computational overhead, since the NTK calculation in MSK is expensive for images of large sizes. In the second part, we run MLP, SepNN, and SepNN (SepPGD) for image representation and recovery (inpainting) (Fig. 3 and Figs. 12) on the original image sizes. For the original size, the MSK run out of memory
GPU and hence omit
33

---

Published as a conference paper at ICLR 2026
SepNN (8ppPCD)
21.58
PSNR
PSNR 23.13
Figure 8: Visual results for image representation via INR and SepPGD on Baboon
Original PSNR Inf
MLP PSNR 27
SepNN PSNR 27.34
SepNN (Spp!G PSNR 33.17
Figure 9: Visual results for image representation via INR and SepPGD on Peppers.
Observed
Original
StpNN PSNR
SopNN (SepPGD) PSNR 28.93
PSNR
PSNR 26.75
Figure 10: Visual results for image inpainting via INR and SepPGD on Plane.
Observel
Original PSNR
MLP PSNR
StpNN PSNR
SepNN (SepPGD) PSNR 21.21
Figure 11: Visual results for image inpainting via INR and SepPGD on Baboon.
Observedd
Original PSNR Tnf
MLP PSNR 27
ScpNN PSNR 29.01
ScpNN (SepPGD) PSNR 29.5 58
Figure 12: Visual results for image inpainting via INR and SepPGD Peppers.
the comparison with MSK on original sized images. The network width is set to 150 for smaller images, smaller value since the NTK calculation for MLP and MSK runs out of memory for larger width. We train the neural networks using INRs by feeding the image coordinates into the network and output the corresponding image value for image representation, following INR works (Sitzmann et al., 2020; Shi al., 2025). For image recovery (i.e., image inpainting), we randomly sample 30% points in the image as incompleted entries. We then train the models on other 70% known pixels and predict the values of incompleted entries using the trained model for image inpainting. For the first part using smaller images, we report the image representation MSE w.r.t. execution time using convergence curves (Fig. 2(b) and Fig. 6) show the convergence superiority of SepPGD. For the
34

---

Published as a conference paper at ICLR 2026
Kidns Cuedon
Separahle
Separable (SepP
MSE
MSE 0.056
MSE 0,015
Figure 13: Convergence curves and results for the 3D equation using PINNs.
root 1837
Exuciion laan
Separabla (SepP
MSD
MISE 5-129
MSEE D.L
MST bass
Figure 14: Convergence curves and results for the 3D Helmholtz equation using PINNS.
second part using larger images, we present visual results to display the recovery of image details and textures (Fig. 3 and Figs. 8-12).
In the first part using smaller images, we consider both noisy (standard deviation 0.01) and noiseless cases. The convergence behavior is measured by image MSE during training. Because the efficiency advantage of SepNN and SepPGD comes from the lower complexity in an iteration, we plot the convergence curve w.r.t. execution time rather than iteration number (While we have also reported the convergence curves w.r.t. iteration for larger images; see Fig. 7). All experiments are conducted on an RTX 2080TI GPU. For all experiments of image representation, we utilize the Adam optimizer (Kingma& & Ba, 2015) with learning rate 0.0001 and without weight decay. For smaller images, the rank of the bivariate CP SepNN is set as 150. The network width is set as 150. For original sized images, the rank and network width are set 500. The depth of MLPs is set to 3. The preconditioner of each method is updated once every 10 iterations. The images are fitted channel-by- bivariate SepNNs. In the modulation function g()), set k = 10 for smaller images and k = 70 for original sized images. For MSK, we set k = 25 in the modulation function (fine-tuned using trial-and-error) All MLPs and factor MLPs in SepNNs are parameterized by the SIREN structure (Sitzmann et al., 2020), well-studied method in INRs. For original sized images, we run 1300 iterations for all methods to ensure fair comparisons between their convergence behavior.
using
Convergence curves in Fig. 2(b) list the result for Baboon. The convergence curves for Peppers We note that in these figures, MLP (MSK) does not obviously
and Plane are shown in Fig. improve the convergence of MLP. This is because the MSK under full-batch condition requires gen- erally larger computational costs for image data, resulting similar convergence speed as compared with the pure MLP. Image representation results in Fig. 3 and Figs. 8-9 (under the same iteration number for different methods) show that SepPGD effectively alleviates the spectral bias of SepNN to improve convergence, thus better capturing image details and structures. Figs. 10- 12 (under the same iteration number for different methods) show that SepPGD does not affect the generalization ability of the SepNN for image inpainting, even leads to improvements in most time. This shows the robustness and effectiveness of the proposed SepPGI for preserving the generalization while accelerating training convergence. In Fig. 7, we show the PSNR vs. iteration curves using original sized images. SepPGD clearly enhances the convergence speed and alleviates spectral bias of the SepNN by observing the convergence curves.
Surface Representation. The 3D surface representation in Fig. 3 is conducted on the Thai statue dataset (Saragadam et al., 2023; Shi et al., 2025) (304 512 262 occupancy cube). In the mod- ulation function 9()), we set k = 20 for SepPGD. All MLPs and factor MLPs in SepNNs are parameterized by the SIREN structure (Sitzmann et al., 2020), a well-studied method in INRs. We run 1000 iterations for all methods to ensure fair comparisons between their convergence behavior. We utilize the Adam optimizer (Kingma & Ba, 2015) with learning rate 0.005 and without weight decay. The rank of the CP SepNN is set 200. The network width is set as 256. The depth of MLPs is set to 3. The preconditioner of each method is updated once every 10 iterations. Here, the CP SepNN and SepPGD are the three-dimensional case in Definition 1 (D 3). Since the MSK run out of memory for full-batch settings in our platform, we do not compare this method for surface representation. Although can run the MSK using mini-batch versions (Shi et al., 2025) (i.e., by
35

---

Published as a conference paper at ICLR 2026
sampling a part of training samples in each iteration), remark that theory and algorithm mainly derived for full-batch settings, and hence comparing with tory. In contrast, our SepPGD can be efficiently implemented for full-batch algorithms by virtue of the (nD) complexity. Deriving the training dynamics and implicit regularization of mini-hatch algorithms are promising directions for future researches.
methods is not manda-
PINN. Following the framework of separable PINNs as introduced in (Cho et al., 2023), our ex- periments are performed on the 3D diffusion, Helmholtz, and Klein-Gordon equations (Figs. 4, 13, and 14). For the detailed formulations of these equations, we refer readers to equations (51)-(59) in (Cho al., 2023). Unlike the loss function used (Cho et al., 2023), the physics-informed loss in our experiments contains four components: the PDE residual loss, the initial condition loss, the boundary condition loss, and an additional data loss. Here, the data loss corresponds to training the PINN model using a set of grid-based training points, which enables the application of the pro- posed SepPGD algorithm via the --rnrr of the data loss. We also apply SepPGD to the initial and boundary condition losses. For the PDE residual loss, which involves derivatives, we do not employ the SepPGD algorithm, as extending PGD to derivative-based losses requires substantially different algorithmic treatment. We leave this promising direction to future work.
In the modulation function (A), we set = in SepPGD for the data loss in PINNs, while setting k 2 for boundary and initial losses after trial-and-eme parameter tuning. All MLPs and factor ML.s in SepNNs are parameterized by the SIREN structure (Sitzmann et al., 2020) to enhance the convergence for PINNs. We 5000 iterations for all methods to ensure fair comparisons between their convergence behavior. We utilize the Adam optimizer (Kingma & Ba. 2015) with learning rate 0.005 and without weight decay. The rank of the CP SepNN set as 64. The network width is set as 64 as well. The preconditioners for the three loss functions (data, boundary, and initial loss functions) are computed at initialization and remain fixed throughout the training process to reduce computational cost, since we need to update three preconditioners for the PINN. For each example, we sample x 16 16 grid collocation and training points, while evaluating the trained models on 30 x 30 x 30 grid testing points to test the generalization ability. The number of layers in all MI.Ps set to 4 by following (Cho et al., 2023). The results in Figs. 4, 13, and 14 show that SepPGD has substantial potential in accelerating the convergence of separable PINNs.
LLM use. LLMs were rarely used in this paper to polish writing. All technical contents and con- ceptualizations were made by humans.
36


Reviews:
[{"review_id": "rTOLG2A9xM", "reviewer": "Reviewer_dMQY", "summary": "The paper begins by establishing the universal approximation theory for three classes of separable neural networks (SepNNs): the CP type, TT type, and Tucker type. The proofs are built on classical results (Stone-Weierstrass, universal approximation theorems) and well-motivated in the context of separable function spaces. The results extend beyond the bivariate approximation in (Cho et al., 2023) to general D-variate functions.\n\nFurther, the paper prove that, under the asymptotic regime of infinite network width and infinite rank, the NTK of a CP type SepNN converges to a deterministic kernel, provide an analogous result to that of a standard MLP. In contrast, under infinite width and fixed rank, the NTK converges to a stochastic kernel defined via Gaussian processes.\n\nFinally, the paper introduces the SepPGD training algorithm that exploits the Kronecker product structure of SepNN NTKs to reduce computational complexity from $\\mathcal{O}(n^D)$ to $\\mathcal{O}(nD)$.", "questions": "I have some additional questions:\n\n1. The manuscript briefly mentions that SepNN is closely related to the Kolmogorov-Arnold network (KAN). Since KAN is a timely and widely-discussed topic these days, could the authors elaborate more on this connection? Specifically, can KAN be regarded as a special caseof a SepNN under the definitions used in this paper? If so, how do the function composition structures in KAN (i.e., sums of univariate functions composed with multivariate linear transforms) relate to the separable architectures (e.g., CP, TT, Tucker) defined here?\n\n2. I may have missed this in the manuscript, but how does SepPGD perform with varying eigenvalue modulation functions $g(\\lambda)$? Is the choice critical?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. To the best of my knowledge, this is the first work to formally establish the universal approximation theorem for SepNNs, including CP, TT, and Tucker variants. Although the result may not be entirely surprising given known approximation capabilities of neural networks, it fills a gap in the theoretical understanding of SepNNs.\n\n2. I find the introduction of the SepPGD algorithm to be a significant contribution to the application of SepNN, even though no theoretica guarantees is given, its efficiency is demonstrated through various numerical experiments.", "weaknesses": "1. While the universal approximation theory for SepNNs is novel, the paper does not provide explicit approximation error rates as a function of network size. In particular, it does not show how the approximation error scales with respect to rank or width.\n2. The analysis of the NTK is restricted to the CP-type SepNN, whereas analogous results for TT and Tucker types are not provided.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "xqU5wdSOkC", "reviewer": "Reviewer_A9Bg", "summary": "This paper provides a comprehensive theoretical and algorithmic framework for Separable Neural Networks (SepNNs), a class of efficient models that factorize a multivariate function into a combination of univariate functions. The main contributions are:\n1. Approximation Theory:Proving that SepNNs are universal approximators, capable of approximating any continuous multivariate function with arbitrary precision.\n2. NTK Analysis:Deriving the Neural Tangent Kernel (NTK) for SepNNs, characterizing their training dynamics and inherent spectral bias.\n3. Efficient Algorithm:Proposing a novel Separable Preconditioned Gradient Descent (SepPGD)method that effectively alleviates spectral bias with significantly lower computational cost than existing preconditioning methods.", "questions": "Same to the weakness.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The authors performed an analysis of the sepNN parallel to the fully-connected neural networks. They built the uniform approximation theorem, the NTK regime, and the gradient descent.", "weaknesses": "My major concern with this work is that I fail to see the potential impact of developing this theory for separable neural networks (SepNNs). After several years of developments in NTK research, this type of work feels somewhat routine.\n\nIf the author could explain a little bit on the potential application and the near future goal of this theory, I would be happy to increase the score.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Kiy1zfptz2", "reviewer": "Reviewer_3E8r", "summary": "This work makes contributions to theoretically understanding SepNN. First, using Weierstrass-based approximation and universal approximation theory, they prove that SepNN can approximate any multivariate function with arbitrary precision, confirming its representation completeness. Second, they derive the neural tangent kernel (NTK) regimes for SepNN, showing that the NTK of infinite-width SepNN converges to a deterministic (or random) kernel under infinite (or fixed) decomposition rank, with corresponding convergence and spectral bias characterization. Third, they propose an efficient separable preconditioned gradient descent (SepPGD) for optimizing SepNN, which alleviates the spectral bias of SepNN by provably adjusting its NTK spectrum. The SepPGD enjoys an efficient order of complexity and is much more efficient than previous neural network PGD methods. Extensive experiments for kernel ridge regression, image and surface representation using INRs, and numerical PDEs using PINNs validate the efficiency of SepNN and the effectiveness of SepPGD for alleviating spectral bias.", "questions": "No question.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well written. Ideas are well presented.", "weaknesses": "No obvious weakness.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "zCG7SIsr3X", "reviewer": "Reviewer_WM7X", "summary": "The paper studies real valued separable neural networks (SepNNs), an alternative architecture which combines some univariate functions linearly to represent multivariate functions. SepNNs combine univariate factor functions $f_{\\theta_i}(x_i)$, with linearity $L$ (equation 1). Authors considered three cases of this $L$ function, CP, TT, Tucker.\nThe paper build up on three claims:\n1. Similar universal approximation guarantees of neural networks in terms of expressivity for SepNNs.\n2. Analyzing neural tangent kernels in the case where rank or width goes to infinity and it establishes that under infinite width and rank, NTK converges to a deterministic kernel and under infinite width and finite fixed rank it converges to a random kernel\n3. Using theoretical analysis of NTK they propose a training algorithm (SepPGD) that reshapes the spectrum with O(nD) preconditioning cost on n grids per axis reaching faster convergence in tasks KRR, INRs, PINNs.", "questions": "I find the definition of TT and Tucker not well placed in the article and equation 2, 3 lacks some notations, since it’s not obvious what are R and the tensor product and what are $f_{\\theta_i}_{i_{i-1}, r_i}$, and $C$, maybe they can be moved to theorem 1 ot a preliminaries section.\n\nThe claim in remark 1 is not obvious to me, how can the results be extended to multi layers?\n\nLine 337 is incomplete, there seems to be a missing sentence.\n\nWhat is the computational cost for calculating the preconditioner?\n\nIn the fixed rank regime is it possible to bound $$||K(t) - K(0)|| over finite time with small step sizes?\n\nHow sensitive is SepPHD to the choice of k?\n\nCould Lemma 2 be extended to non-grid inputs?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The most interesting thing about this paper is how they use their theoretical analysis on optimization of SepNNs and the limitations they found to come up with a prescription as a training algorithm.\n\nTheir universal approximation theorem nicely shows the expressivity power of SepNNs. Also, the proof sketch is nicely and understandably stated in the main body and it’s intuitive enough for readers. (Theorem 1).\n\nThey use NTK to study optimization regimes under asymptotic assumptions (Theorem2, lemma1) and they characterize when training dynamics are kernel-like vs. stochastic.\n\nThey use spectral bias already known results to argue that SepNN suffers from a similar problem, this is not particularly novel but the discussion of spectral bias and how they propose a new training algorithm inspired by similar works for SepNN is nice.\n\nThe training algorithm (SepPGD) is a slightly complicated but good-sounding idea. The authors support this algorithm with nice theoretical analysis showing equivalence to full NTK-PGD step with smoothened eigenvalue spectrum which improves convergence.", "weaknesses": "In terms of motivation, I found the introduction to be a bit lacking. The authors don’t clearly discuss the advantages of SepNNs.\nMore thoroughly, the motivation for SepNNs is not well positioned against established efficient architectures. The paper frames SepNNs as a new paradigm but does not convincingly argue why this approach matters beyond reinterpreting classical separability. Without this context, the work risks appearing incremental from the perspective of practical ML.\n\nThe authors mentioned computational complexity: the paper mentions that SepNNs need only $$O(nD) $$ computations (n being number of data and D being dimension). They compare it to computational complexity of NN being $$O(n^D)$. This is true in terms of unique function evaluations but is does not imply faster training since regular models for example a CNN do their computation of all the dimension D in parallel. My impression is that SepNNs’ benefits are limited to high dimensional, low sample problems, with structured scientific problems in terms of learnable parameters and memory efficiency; but the authors don’t discuss that.\n\nTheorem 1, does not say anything about rank, for example there’s no rate describing rank R must grow with target smoothness of dimension or something similar to that. This limits the theorem's relevance for practical rank selection.\n\nThe paper lacks theory for fixed-rank regimes, which is the setting that actually matters in practice. The entire motivation mentioned for using SepNNs is to have low rank structure to achieve parameter efficiency, scalability and interpretability, but the theory for this is limited in terms of convergence guarantees, or bound for generalization errors.\n\nThe random NTK in the fixed rank case is mathematically similar to random features maps. It would be nice for authors to make this connection and use the well-studied random feature maps. This can address the lack between asymptotic assumptions in theorem and finite rank networks used in experiments.\n\nThe preconditioner choices appear to be heuristics and there is no discussion/guarantee on what their condition number might be, or their possible effect on generalization. \n\nThe experiment focuses on grid structured problems; adding other experiments, with non-grid tasks (e.g. tabular inputs) might strengthen things. This is just a suggestion, rather than a requirement.\n\nSome reproducibility details are missing.\n\nSome experiments:\nAblations study on sensitivity to rank, also k in the eigen-leveling and update frequency, choice of activation and width.\nSome baseline are missing specially fourier feature maps.\nSome experiments on robustness to noise and overfitting behaviors of SepPGD \n\nThe claimed efficiency of SepPGD neglects the high upfront cost of constructing the preconditioner. The claim of $O(nD)$ refers to applying the preconditioner while constructing them seems expensive. Also it requires a lot of memory to store these pre-conditioned matrices $O(Dn^2)$ which makes the method not scalable for a higher amount of data.\n\nWhat if the target is not well-separable? It would be nice to have approximation-error curves vs true separation rank of the target (synthetics with controllable TT/Tucker rank). Or some similar attempt to address the real-world misspecification gap.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)