Minimax Rates for Learning Pairwise Interactions in Attention-Style Models
Authors: Shai Zucker
Xiong Wang
Fei Lu
Inbar Seroussi
Venue: ICLR 2026 Poster (2026)
Keywords: Attention mechanism
Interacting particle systems
Minimax rates
Nonparametric estimation
Primary area: learning theory
TL;DR: Analyzing attention mechanisms as interacting particle systems, we prove that learning pairwise token interactions achieves a minimax scalar rate of $M^{-\frac{2\beta}{2\beta+1}}$ when $M$ is large enough.

Abstract: We study the convergence rate of learning pairwise interactions in single-layer attention-style models, where tokens interact through a weight matrix and a nonlinear activation function. We prove that the minimax rate is $M^{-\frac{2\beta}{2\beta+1}}$, where $M$ is the sample size and $\beta$ is the H\"older smoothness of the activation function. Importantly, this rate is independent of the embedding dimension $d$, the number of tokens $N$, and the rank $r$ of the weight matrix, provided that $rd \le (M/\log M)^{\frac{1}{2\beta+1}}$. These results highlight a fundamental statistical efficiency of attention-style models, even when the weight matrix and activation are not separately identifiable, and provide a theoretical understanding of attention mechanisms and guidance on training.

Published as a conference paper at ICLR 2026
MINIMAX RATES FOR LEARNING PAIRWISE INTERAC- TIONS IN ATTENTION-STYLE STYLE MODELS
Shai Z
Xiong Wang* School of Mathematics
Department of Applied Mathematics,
School of Mathematical Science Tel Aviv University shai zucker@maillllccmmmoemmmm.. tau. ac.ic
Sun Yat-sen University Guangzhou, China x xiongyangg@ullbertta.cc
Fei Lu
Inbar Seroussi
Department of Mathematics Johns Hopkins University Baltimore, USA fei luêmath, Shu.edu
Department of Applied Mathematics,
School Mathematical Science
School of Computer Science
Tel Aviv University inbarser@tauex. tau. ac
ABSTRACT
We study the convergence rate of learning pairwise interactions in single-layer attention-style models, where tokens interact through weight matrix and non- linear activation function. We prove that the minimax rate M -5 where M is the sample size and B is the Hölder smoothness of the activation function. Impor- tantly, this rate independent
the embedding dimension d, the number of to- kens N, and the rank r of the weight matrix, provided that rd & (M/ log M) aFTI, These results highlight fundamental statistical efficiency of attention-style mod- els, even when the weight matrix and activation are not separately identifiable, and provide a thcoretical understanding of attention mechanisms and guidance on training.
INTRODUCTION
The transformer architecture (Vaswani 2017) has achieved remarkable success in natural lan- guage processing, computer vision, and other AT domains, with its impact most visible in large language models (LLMs) such as GPT (OpenAl 2024). LLaMA (Touvron et al., (202)), and BERT (Devlin et al., 2019). At its core, attention mechanisms model nonlocal dependencies between in- put tokens through pairwise interactions, creating function class capable of representing intricate contextual relationships.
Despite the empirical success, our theoretical understanding remains incomplete. The attention mechanism computes weighted averages of token representations using pairwise similarities, but we observe only the aggregated outputs and not the underlying interaction structure that generates them. This creates fundamental inverse problem with critical sample complexity questions: recover the interaction function from these aggregated observations, how many samples are needed to learn token-to-token interactions for given accuracy level, and how does the convergence rate depend on embedding dimension, number of tokens, and smoothness of the activation function?
Recent phenomena like extreme attention weights certain tokens (Sun et al. 2024 Guo al., 2024b Xiao et al.) 2024 Wang et al. 2021) further highlight gaps in our understanding of how transformers process token interactions.
In this paper, we tackle these questions by analyzing an Interacting Particle System (IPS) model for attention-style mechanisms. Tokens are viewed as "particles." and the self-attention aggregates pair- wise interactions between them. The interaction is a composite of an unknown embedding matrix
$ These authors contributed equally this work.

---

Published as a conference paper at ICLR 2026
and unknown nonlinear activation function, both of which are learned from data. This makes the problem challenging as it is fundamentally nonconvex. Our IPS approach provides natural frame- work for understanding how transformers process inputs with a large number of correlated tokens, moving beyond the restrictive assumption of independent, isotropic token distributions.
We summarize main contributions below:
We establish a connection between transformers and IPS models, enabling us to address the challenging inverse problem inferring nonlinear interactions learned by attention mecha- nisms. Our analysis extends beyond the standard assumption of independent, isotropic token distributions to allow for dependent and anisotropic data.
Inferring interaction function an inverse problem. We prove that under a coercivity condition (Lemma 3.4). this problem is well-posed in the large sample limit. This condition holds for a large class of input distributions.
We prove that the rate of M 28+T is the optimal (up to logarithmic factors) minimax con- vergence rate in estimating the 2d-dimensional pairwise interaction function, where M is the sample size and 3 the Hölder exponent the function. The error is composed of parametric and nonparametric terms. Importantly when rd (M/ /og M) æ the leading term is the nonparametric term M ăžчт, which does not depend on the embedding dimension d or the rank This confirms that the attention-style model evades the curse of dimensionality.
24
RELATED WORKS
Neural networks and IPS. Modeling neural networks dynamical systems through depth was introduced in Chen et al. (2018), which framed updates in ResNet architectures as the dynamics of state vector. This perspective has been generalized to various architectures, typically treating skip connections as the evolving state across layers. Following this approach, in
Geshkovski al. 2023 2025)
they view tokens as interacting particles, analyze the attention as an IPS, and study clustering phe- nomena in continuous time (in depth).
Similarly, Dutta et al. [2021) leverages a similar framework to compute attention outputs directly from an initial state evolved over depth, thereby reducing computational costs. While these works provide valuable insights, they focus exclusively on the dynamics of tokens through the layers. To our knowledge, no existing work addresses the learning theory for estimating the pairwise interac- tions in such particle systems.
Inference in attention models. Many theoretical works have studied the Iearnability of attention, focusing on specific regimes. Some consider simplified variants, such as linear or random feature
target attention models (Wang et al. 2020 [Lu et al.) 20255) Marion et al.) 2025) Hron al., 2020 Fu
al. 2023), which explore the capability of this model under simple regression tasks.
Deora et (2024) analyze logistic-loss optimization and prove a generalization rate under "good" initialization.
Others consider a more specific architecture, Li al. (002)) study the training of shallow vision transformers (ViT) and show that, with suitable initialization and enough stochastic gradient steps, a transformer with additional ReLU layer can achieve zero error.
Several works study softmax attention layers with trainable key and query matrices in the limit of high embedding dimension quadratically proportionate to samples with i.i.d. tokens Troiani et al. : Cui et al. (2024); Cui (2025): |Boncoraglio et al. (2025). which is further expanded in Troiani ct al. (2225) for softmax attention (without the value matrix) with multiple layers.
These works have mainly focused the linear/softmax attention model and do not consider gen- eral interaction function. In addition, most studies assume the tokens are independent and do not draw connection to the IPS system.
Inference for systems of interacting particles. There is large body of work on the inference of systems of interacting particles; we state few here. Parametric inference has been studied in
2

---

Published as a conference paper at ICLR 2026
Amorino al. 2023); Chen (2021) ): Della Maestra & Hoffmann (2023); Kasonga (1990): Liu &
Qiao (2022 : Sharrock et al. ) for the operator (drift term) and in Huang et al. (0019) for the
noise variance (diffusion term). Nonparametric inference on estimating the entire operator Rg. but
not the kernel y, has been studied in Della Maestra & Hoffmann (2022) Yao et al. 2022).
The closest to this study are Lu et al. these studies is that their goal is to estimate the radial interaction kernel, whereas our 2d-dimensional pairwise interaction function is not shift-invariant due the weight matrix. In addition, all these studies focus on IPS in general, without a clear connection to attention models.
(2021a 2022
2019): Wang al. (2025). A key difference from
Activation function in transformer layer. Recent work has shown that attention models suf- fer from the "cxtreme-token phenomenon", where certain tokens receive disproportionately high weights, creating challenges for downstream tasks (Sun al. 2024; Guo al. 2024b Xiao al. 2024 Wang et al., (022)) )). To address this, it was proposed to replace softmax with altematives, such as ReLU (Guo et a 2024a Zhang et al.) (20T), which can "turn off" irrelevant tokens, a capability that softmax lacks. While linear attention can outperform softmax in regression tasks by avoid- ing additional error offsets (Von Oswald et al. 2023; Katharopoulos et al.) 2020 Yu et al. [024] Han et al. 2024), it may be inferior for classification (Oymak et al. (023). These findings sug- gest no universally optimal activation function exists, making the theoretical analysis of a general interaction function in transformer-ty type models crucial. As for vision tasks, several Vision Trans- former (ViT) variants remove the softmax activation while remaining competitive. For example, Lu et al. (021h) consider attention mechanism based Gaussian kernel, and [Koohpayegani & Pirsiavash (2024) apply linear attention after normalizing the Key-Query columns. Furthermore, Ramapuram al. (2025) examine sigmoid function as the attention activation, showing acts as a universal function approximator and benefits from improved regularity compared to softmax attention.
Nonparametric and Semiparametric Estimation for Neural Networks Classical nonparametric estimation provides optimal minimax rates for simple structures. Gaiffas & Lecué (2007) provide bounds for the single index model f(w Ta) of order T For the more general projection pursuit model fx) = Σبك [r (3))) Györfi et al. (2006) shows that the minimax rate the standard rate up to a log factor. These results directly apply to small single-layer neural networks.
Closer to deep learning, Horowitz & Mammen (2007) analyze generalized additive models with nested k-times differentiable compositions, showing the rate is -M _2__ proves that connected deep ReLU networks achieve near-optimal minimax rate (up to log factors) over class of composed functions. In Bhattacchary et al. (2024) they study a nonparametric interac- tion model in high dimension settings and show sparsity assumptions and associated regularization are required in order to obtain optimal rates of convergence.
Sehmmidt-Hebber (2020)
Notation.
Throughout the paper, we use C to denote universal constants independent of the sample size M, particles N and the embedding dimension d, The notations C3 Cg. denote constants depending on the subscripts. We introduce the L inner product as (f.g) r = {f(r)g())((dr)) and denote the LP norm by Ilfl = (" for all p > 1. For vectors a, E Rd and Rdxd we write (a, b)a = T Ab.
2 PROBLEM FORMULATION
In this section, we describe our statistical task and connect it to the attention model.
Model setup and learning task.
We consider a model of N interacting particles,
N
Y
Σ
(X,, Xy)A.) +
(2.1)
N
j-1,4+
where 17 E RNN noise as specified in Assumption 2.2 Φ. R - is an unknown interaction kernel,
and A. e Rdd is unknown interaction matrix. Here, write (I, v) A x. Ay for x, y R
3

---

Published as a conference paper at ICLR 2026
and A E Raxd, The input X
CØ (fO, 11 11dVV R Nxd denotes
the particle positions (or token values), and the output y (Y1,... YN) RNx1 represents the average interactions between the particles.
We observe M i..d. samples
DM {(X",, )"")
XT C. == (fo. 11 /v)/ Y R.Y
allowing the N partieles and their entries be dependent.
The task is to learn the pairwise interaction function g. R x R R
g.(2,)) y) = o. ((z, v)A.), (a. E R x Rd
(2.2)
from the dataset of observations DD-
We introduce the vectorized view of the model via the forward operator Rg for any candidate inter- -)=1,++((,,, Xy). Accordingly, our model action function R x F - R as Rg[X]: == N-1 ΣN in equation 2.1 becomes Y; Rg. [X] + 1/s-
Connection to self-attention layer. We view self-attention through the lens of IPS: tokens "particles," " and attention aggregates pairwise interactions between them. A typical self-attention layer is composed of an attention block with learnable query, key, and value matrices, Wq. WK Rexds with dy & d and Wv Rddd that compute
Au K, V) softmax
OK VoL
V,
Q K XWR, V XWv.
(2.3)
The attention operation is then often followed by application of multilayer perceptron (MLP), which maps the above into some other nonlinear function. The pairwise structure of attention mo- tivates modeling token interactions via scalar kernel function applied to bilinear form of some score interaction matrix A, that can be viewed as the learned projections through 1 W-W W i.c.
va.
softmax
QK Vdl
= softmax (XA.X)). XA,X (X.
WoWK (X, 1 dda
The interaction function in equation 2.2 can be interpreted either function induced by the MLP and the softmax function, or as a general activation function with a constant value matrix; see more details in Appendix
As stated in the related work, such setup for a general activation function is often desirable due to the extreme-token phenomenon (Sun al. 2024 Guo et al. 2024b) Xiao et al. 2024 Wang al.) 2021)
Consequently, the problem of estimating 9.
from the samples described in equation 1. 2. analogous to the joint estimation of the activation func- tion and weight matrix governing nonlocal token-token interactions in single-layer self- mechanism.
Goal of this study. Our goal is to characterize the optimal (minimax) convergence rate of estima- tors of g. as the sample size M grows.
To assess the estimation error for the interaction function, we introduce empirical measures over pairs of particles/tokens (x. v). Termed exploration measures, they quantify the extent to which the data explores the argument space relevant to the function.
Definition 2.1 (Exploration measure) Let "X E Ca)M be sampled sequence. Define the em- pirical exploration measure of off-diagonal pairs of particles
M Σ
Par (B) = MN(N 1)
1 ((xxxxx)))
and the population exploration measure as (B = limm-x PM B) (B))(
for any Lebesgue measurable set B Rd Rdd

---

Published as a conference paper at ICLR 2026
We aim provide matching upper and lower bound rates for the L3 error of the estimator g. as to obtain a minimax convergence rate:
@ 9.12g 2 M 2041, as M D0;
(2.4)
where 3 the Hölder exponent of g. (which is determined by the smoothness of Φ.). This then demonstrates that the attention model is not susceptible the curse of dimensionaliiy. In particular, we aim to characterize the dependence of the rate on the embedding dimension d, the rank r of the interaction matrix, and the number of tokens N.
2.1 ASSUMPTIONS ON THE DATA DISTRIBUTION
We now state the assumptions the distributions of the input and the noise used throughout this work. We not assume that the N tokens are independent of each other.
Assumption 2.1 (Data Distribution) We assume the entries of the C.² ([0, d) NaoVVddvvveee vvauudd random variable X = (X1,...,XM) satisfy the following conditions:
(A1) The components of the random vector X =X11...,, are exchangeable.
(A2) For each E (1,...,N) NN) and any j + j' j.j + i, there exists o-algebra X; 2 (X;)) such that Xj and Xy conditionally independent given X4.
(A3) The joint distribution of (X,,,) has continuous density function for each pair.
These assumptions simplify the inverse problem and may be replaced by weaker constraints; Wang et al. (2025) for a discussion and references therein. The exchangeability in [A1] simplifies the exploration measure Lemma B.T It enables the coercivity condition for the inverse problem
to be well-posed, as detailed in Lemma 3.4 and is only used in the upper bound in Theorem 3.1
The continuity Assumption (A3) ensures that the exploration measure has a continuous density, which is used in proving the lower minimax rate Theorem 4.4
We next specify the noise setting. Assumption 2.2 details the constraints we assume for the noise:
Assumption 2.2 (Noise Distribution) The noise vi R.N is centered and independent of the dom array X. Moreover, we assume the following conditions:
(B1) The entries of the noise vector (1h,..., 7N) are nub-Gaussian in the sense that for all i, Bleent] < 00 for some c >> 0.
(B2) There exists a constant Cr O such that The density Pr of 1) satisfies the following:
Pn( du & 2/
(u) log
VOERN.
(2.5)
JRN
Pu v)
We note that assumptions (1))
and (32)
hold for instance for Gaussian noise ry ~ NO0,, oN with
Gg
1/(20?))
2.2 FUNCTION CLASSES AND MODEL/ESTIMATTOR ASSUMPTIONS
We introduce the functional classes where g. lies. Our goal is consider as large class of functions as possible while also tracking the properties of the models ø that control the rate. For that purpose, we introduce the Hölder class and assume that Φ. satisfies some smoothness order 3.
Definition 2.2 (Hölder classes) For 33 L, a > the Hölder class C (P, on [-a, a] is given by
c (L, a) = {f: a. R: I (() L|x 8| Vz, -a,a (2.6)
where (6] denotes the j-th order derivative of functions f and 133.
5

---

Published as a conference paper at ICLR 2026
Low-rank Key and Query matrices often play important role in the attention model. To keep track of the effects of the rank on the minimax rate, we introduce the following matrix class for the interaction matrix A., which is the product of the Key and Query matrices.
Definition 2.3 (Interaction matrix class) For à > O, the d-dimensional matrix class Ad(r, ū) with rank r E N and 2 < E is given by
Aa(r, a) {A Rddd rank A) & r., |Al $ a).
(2.7)
Combining both classes, we consider the following function class g. for all the possible pair- wise interaction functions.
Definition 2.4 (Target function class) Given L., B a > and rank r >
define
(L, a) = (9,.A(I,)) y) = 6(x Ay) O (L, a), |0ll & AE AE Au(r,a)).
(2.8)
Moreover, for any Gf (L, a), it follows that [RgX]]l & Bg. For technical reasons, require L & BB(2a)². This holds without loss of generality for any â 3 1 and L Bg.
We provide both lower and upper bounds for the possible enror rate by the number of samples for the interaction g(-,)) E G. We consider the following functional class for our estimator:
Definition 2.5 (Estimator function class) Let s == max( 1) and KM N. Let D denote the class of piecewise polynomials of degree s, defined on KM equal sub- sobb-ntervall of - a.
The corresponding estimator model class is
g = { go.A: DE &K 10 + 110' & Bø, A Au(r,a)) = g..
(2.9)
UPPER BOUND
In this section, provide upper bound on estimating the token-token interaction. We propose the following estimator Im (z, v) Ō((2, A)
as the empirical risk minimizer over the functional class 2.5
JM arg min Egs(go.)) = N Σ 80 (go.a) with 8o.1E0%.KM
(3.1)
M
EM (Jo.A) = M
Σ m-1
Y
Rgo. [x]
D Here, Rg N-I 2j=1,j A (X, Xÿ) is the forward operator with interaction function As.A. Our goal is to prove that the estimator ÿM achieves the optimal upper bound. The large sample limit of EM (go.A) is then
Eoo( = Jim EN (g6.A) 1 [|| [ R [X]1
M -0220
The i-th error elt) A for any 1 i & N is defined in the same manner.
The next theorem states that this estimator achieves the nearly optimal rate in estimating the inter- action function. This rate matches the lower bound in Theorem up to a logarithmic factor. Its proof is deferred to Appendix B.I
Theorem 3.1 Suppose rd & (M/ log M) MYTT, Consider the estimator ÿM defined in equation 3.1 computed data M i.i.d. observations satisfying Assumptions and and (B1) Then, for 9M defined in equation 3. it holds that
lim sup M
sup g (L.
2P41 1 - 9.llig] & CN.La,B..
(3.2)
where CN NIC
(e 28 (d))²
+ C2) for some universal positive constants C1, Cz-

---

Published as a conference paper at ICLR 2026
Remark 3.2 The symbol & indicates that the upper bound holds up to logarithmic factor of (log M) ズान max(28.1). We believe this factor can be improved, as it currently creates a gap between upper and lower bounds, representing limitation of our methods. It is worth noting that by working with uniformly bounded noise, this factor can be simplified (e.g. see Theorem 22.2 in Györfi al. (2006)). In simpler settings, such as standard regression or when the interaction matrix A is constant (e.g., for Euclidean distances), this logarithmic factor can be removed using more advanced techniques. This topic is discussed several works, including Wang al. (2025); Györfi et al.) (2006): Van der Vaart (2000) and the references therein. However, in our model, the optimization depends on both the interaction matrix A and the function 6, which makes the problem non-convex. This difficulty makes the aforementioned teceeddeeeeee techniques harder to implement. We therefore leave this for future work.
This theorem demonstrates that the nonparametric component of the estimation error 22 of 9. avoids the usual curse of dimensionality: the leading term M 20+1 does not depend on d. The dimension enters only through the additional parametric contribution associated with estimating A., which dominated under rd & (M/ log M) ziTr.
Remark 3.3
The proof extends the technique in Györfi et al. (2006) Theorem 22.2) originally developed for the projection pursuit algorithm for multi index models. Our setup differs from the multi-index setup in which one estimates Y = > fa(b x) + with {fs R. - R and 6, e [R] from sample data {(X", y" where the data Y depends locally on projected values of single particle X. Here, the attention-style model involves averaging multiple values of the pairwise interaction function, which is a composition of the unknown o, and A. This nonlocal dependence, combined with the mixture of parametric and nonparametric estimations, presents significant challenge.
We list below the main challenges we address in the proof of Theorem 3.1
1. Nonlocal dependency. The nonlocal dependence presents challenge in estimating the interac- tion function. The forward operator Rg [X] depends on the non-locally through the weighted sum of multiple values of g of pairwise interaction. Thus, this a type of inverse problem that raises significant hurdles in both well-posedness and the construction of estimators to achieve the minimax rate. To address these challenges, we show first that the inverse problem in the large sample limit is well-posed for large class of distributions of X satisfying Assumption 2.1 A crucial condition for well-posedness of this inverse problem is the coercivity condition
studied in Li & Lu (2023); Li et al. (202T): ): Lu et al. (2019): Wang et al. (2025):
[0M - l11 (Gs) (g.
N
We prove this condition holds for a general function in our class in Lemma 3.4 Importantly, differing from these studies where the goal is estimate the radial interaction kernel, our in- teraction is not shift-invariant due to the matrix and it is 2d-dimensional pairwise interaction function.
2. Tail decay noise distribution. The proof in Györfi et al, (2006) is limited to bounded noise. We provide a more general statement for any sub-Gaussian noise. This is done by decomposing the enror bound now into three parts.
Exp (āM) (g.( & [E[i,M]] + M[T2,M] + [[T..M]
(3.3)
The first two terms a clever form of bias- decomposition applied to truncated version of the target. To bound these terms, we use a similar technique as in Györr et al. (2006). To control the last term T3.s due to the truncation, we apply a lemma proved in (Kohler & Mehnert 2011 Lemma 2).
3. Covering numbers estimates. Since our interaction is of the form N شلح 6(X AX,) instead of working in the space of vectors, we provide a covering estimate for the class of matrices with rank less than or equal to r. This is done in Lemma B.3
The next lemma proves the crucial condition for the well-posedness of the inverse problem of esti- mating the interaction function. This Lemma assumes exchangeability and allows us to extract the error of the mean interaction. Its proof is based on the exchangeability of the particle distribution and is postponed to Appendix B.1 B.1
7

---

Published as a conference paper at ICLR 2026
Lemma 3.4 (Coercivity) Let 9.9. GL, Bo.a) a). Under exchangeability of (x)) in Assump-
tion A1)
we have
N - 1 1g s.l123 1--ll122g & Ex(s) Ex (g.).
4 LOWER BOUND
This section establishes a lower bound for estimating 9+ (x, y) == 2.(x' A.y) that matches the upper bound in Theorem 3.I] together, these results determine the minimax rate.
The main challenge lies in the nonlocal dependence of the output Y; on 9.. which is determined through averaging
all particles, as we don't 't directly observe any value of g.. Thus, the estima- tion of g, a deconvolution-type inverse problem, which harder than estimating the single index model Y f(b X) in Gaiffas & Lecué (007). Importantly, the nonlinear joint dependence of 9. on the unknown Φ. and A, further complicates the problem.
We address the challenge by first reducing the supremum over all g. the supremum over all ø. with a fixed A, E Aa(r, a), building on a technical result in Lemma This reduces the problem the minimax lower bound of estimating the interaction kernel d. only. We derive this lower bound using the scheme in Wang et al. (2025), a variant of the Fano-T aoo-TTybakov method in Tsybakov 20088)
Let A. E Aa(r, a) and let
N
Unj == X; X, U ~ pu( N(N - ==1j=1
Σ
Puny (u),
(4.1)
where Pv,, denotes the probability density of Un.. Here, the density PU., exists and is continuous because (a.k(A.) > 2 and the joint density of X;) exists by Assumption (A3) see Lemma Hence, the density py continuous. Furthermore, since ||A. & and X, Ca. we have à and supp(pu) = [-ā, a]. In particular, when the distribution X is exchangeable, we have PU., (w) , (v) = pu (u) for all (i,5), u E [-ā. a]. However, our proof below works for non-exchangeable distributions.
C.I
The next lemma allows us to reduce the supremum over all (x = o.(x A.y) to all ø. by bounding 9 9- 9-12 from below by || --112z for a function & determined by 9 and A. Its proof can be found in Section
Lemma 4.1 Suppose Assumption (A3) holds. Let A., Ae Aa(r, a). Recall the definitions of Usj and U pu (defined according to A.) in equation 4.1 Let Φ., E L2 and define a function vi
that determined by (Ø, A, A.) and the distribution of as
N
N
:=) = A AX, u].
$(4) = Σ
Σ
N(N - ()) Pis(ay.
(u)
(4.2)
Then, the following inequality holds:
S (a(n)) (u) (u)du.
g
g-llitg >
The next lemma constructs finite family of hypothesis functions that well-separated in 7,2 while their induced distributions remain close with a slowly increasing total Kullback-Leibler "pg:" vergence, enabling the application of Fano's method derive the minimax lower bound. Its proof follows the scheme in Wang et al. (2025) and is postponed to Section C
Lemma 4.2 For each data set {(X", Ym) H
sampled from the model Y Ro..A. [X] + n,
and there exists set of hypothesis functions (0o.M = O, @I,M, ... .KKM) and positive constants [Co, Ci independent of M, N, d, F, where
where A, Aa(r, â) satisfying assumptions (B2)
K> 28/8 with K Mc 2 J. Co.N = -o.N
(4.3)
such that the following conditions hold:
8

---

Published as a conference paper at ICLR 2026
(D1) Holder continuity: Φk,M C (L, and Mlo for each k: = 1,... K,
(D2) 2s -separaepp l - ΦK M 1220 i 28N with SN.M C1 M
(D3) Kullback-Leibler divergence estimate: te E (RE,PE, & log((() with 1/8,
where (.) = P 1 |X .X..,..."") and pu is the density of defined in equation 4.1
The following theorem provides lower minimax rate for estimating d. when A, is given. Its proof is available in Section
Theorem 4.3
Suppose Assumptions (A3) and B2 hold. Let pu be the density U defined in Then, for any 3 > 0, there exists a constant co > independent of M, d, r and N
equation 4.1 such that
lim inf inf M- Lo
sup (LEC)(L.a) 1e.
Bs. M 28-1 1&M $-112g,, -
234
(4.4)
where VM is estimated based on the observation model with M i.i.d. samples.
Following the above results, we can now provide lower bound for the convergence rate when estimating 9. over all possible estimators in the worst-case scenario.
Theorem 4.4 (Minimax lower bound) Suppose Assumptions (A3) and (B2) hold. Then, for any > O there exists a constant > 0 independent of M, d. and N, such that the following inequality holds:
inf inf g.egf (L.
sup
M 20
22
1 g-l12g] 3 No rartI
28
(4.5)
M-x
where the infinum inf, is taken over all ((v, v) = H(xT Ag) with Ā E Ad(r, and such that
g L2g
NUMERICAL SIMULATIONS
In this section, we empirically verify the convergence rates predicted by our theory, emphasizing their independence from the ambient dimension and their dependence on the activation function's smoothness.
For all experiments, we use B-splines to represent the ground-trun truth activation o.: a degree-p B- spline is CP-1, so the degree directly controls the smoothness (Lyche et al. 2017). B-splines linear in their basis coefficients, allowing us to efficiently compute an optimal coefficient estimator by least squares. Our estimator for the interaction function exploits this structure: first fit 6. in the B-spline basis by least squares, then approximate the fitted activation with a multi-layer perceptron enable backpropagation when estimating A.. This design enables the smoothness and the approximation accuracy of I. ensuring that it achieves the minimax rate. Full simulation and parameter details appear in Appendix D
control both
Our experiments confirm the theoretical minimax rates.
Independence from the ambient dimension d. Figure I compares convergence
bedding dimensions d e {1,5, 5, 30). In the log-log plots, the slopes (which encode the rates) are nearly parallel and close to the theoretical exponent 22, 1) for all three dimensions, indicating that the convergence rate is independent of
for varying smoothness exponents 3, controlled by the B-spline degree used to represent o.. As the spline degree (and hence 3) increases, the log-log slope steepens as predicted by theory: for example, the empirical slopes are -0.81 for degree P = 3 and x -0.899 for P 8, closely matching the theoretical values -0.80 and -0.933.
Dependence the activation function's smoothness. Figure [bb reports
The two plots illustrate that the minimax rate is fully determined by the smoothness 3 and it is doesn't 't change with the dimension.

---

Published as a conference paper at ICLR 2026
Iestpmal fezppe aap.aammp.... (ratgral) 115, eeprodd 2000
Teet MSB
Toxt
13
Expected (Alpe-
Ped (esppea)
5
Expatedl Rate Se P-6 (depem-2500))
Sample Stee
Saauple Sios
(b)
Figure 1: (a) Convergence rates with d E {1, 50).. Composed test Mean Squared Error (MSE) vs. sample size M in log scale; dashed lines show the expected rate M M229/(28+1), and the markers represent the median across seeds. The convergence rates are nearly the same for different values of d. (b) Convergence rates with varying smoothness exponents, which are controlled by the spline degree of 6, and the estimator, with Pine Pest E {3, 8). corresponding to 3 (2, and expected slopes -.8000 and - 0.933. The parameters in each simulation are described in Appendix D
CONCLUSIONS
We have established minimax convergence rates for estimating the pairwise interaction functions in self-attention style models. The rates include leading term M 2 that is indepen- dent of d which controls the parametric rate of estimating A, when the sample size adheres to rd & (M/ / log M) माा condition. This result achieved using direct connection interacting particle systems (IPS), we have proved that under coercivity condition, one can learn the interac- tion function at an optimal rate 28/((2+++) with 3 being the smoothness of the function. Notably, under the rd & (M/ log M) M condition, this rate is independent of both the embedding dimen- sion and the number of tokens. Our analysis extends beyond the standard assumption of independent, isotropic token distributions to allow for correlated and anisotropic token distributions. These results illuminate how attention can avoid the curse of dimensionality in gigh-dimensional regimes. View- ing attention through the IPS lens suggests broad research agenda for understanding the attention models. Promising next steps include extending the theory to multi-head attention, residual connec- tions and self-attention interactions induced by the value matrix. Advances in these directions will improve our understanding of learning mechanisms and generalization in transformers.
ACKNOWLEDGMENTS
This project is part of the NSF-BSF grant 0603624011 and DMS 2511283. XW was partially sup- ported by the Sun Yat-sen University research startup. IS was partially supported by the Israel Science Foundation grant 777/25 and by the Alon fellowship. FL was partially supported by the NSF grant DMS 2238486.
REFERENCES
Chiara Amorino, Akram Heidari, Vytauté Pilipauskaité, and Mark Podolskij. Parameter esti- mation of discretely observed interacting particle systems. Stochastic Processes and their
Applications, 163:350-386. 2023. ISSN 0304-4149. doi: http:://bbi.og//1..110/...
URL https:/ www.
$030441492300132
Sohom Bhattacharya, Jianqing Fan, and Debarghya Mukherjee. Deep neural networks for nonpara- metric interaction models with diverging dimension. The Annals of Statistics, 52(6):2738 2766,
10

---

Published as a conference paper at ICLR 2026
2024. doi: 10.1214/2-A0S2442
Fabrizio Boncoraglio, Emanuele Troiani, Vittorio Erba Lenka Zdeboovvá Bayes optimal learn- ing of attention-indexed models, 2025. URL/htttss//arrtt.orrr///a////b 01582
Giuseppe Bruno, Federico Pasqualotto. and Andrea Agazzi. Emergence of meta-stable clustering in mean-field transformer models. In The Thirteenth International Conference on Learning Repre- sentations, 2025. URL https: / http::///ppeeeeeeeeeee http:/wwwwwweeeeeeeeeeeeeeeeeeee Eorum?
Tian Qi Chen, Yulia Rubanova, Jesse Bettencourt, and David Duvenaud. Neural ordi- nary differential equations. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett (eds.), Advances in Neu- ral Information Processing Systems 31: Annual Conference on Neural Information Pro- cessing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, pp- 6572 6583, 2018. URL httph:tpss.... Absttrattttbbttttttttto... html
19386f6bbldfeen 2533fffbb..cad662222266666399999
Xiaohui Chen. Maximum likelihood estimation of potential energy interacting particle systems from single-trajectory data. Electron. Commun. Probab., pp. 1-1,,201,,
Hugo Cui. High-dimensional learning of narrow neural networks. Journal of Statistical Mechanics: Theory and Experiment, 2025(2):023002, 2025.
Hugo Cui, Freya Behrens, Florent Krzakala, and Lenka Zdeborová. phase transition between positional and semantic learning in solvable model of dot-producc' attention. Advances in Neural Information Processing Systems, 17:36322-363899 2024.
Laetitia Della Maestra and Marc Hoffmann. Nonparametric estimation for interacting particle sys-
tems: McKean-Vlasee models. Probubility Theory and Related Fields, pp. 1-63, 2022.
Laetitia Della Maestra and Mare Hoffmann. The lan property for mckean-vlasov models in a mean- field regime. Stochastic Processes and their Applications, 155:109 2023.
Puneesh Deora, Rouzbeh Ghaderi, Hossein Taheri, and Christos Thrampoulidis. On the optimization and generalization of multi-head attention, 2024. URL httpp//t////xxx..ooro//bbb////// 12680
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding, 2019. URL https::/arxiv..rr
04805
Subhabrata Dutta, Tanya Gautam, Soumen Chakrabarti, and Tanmoy Chakraborty. Redesigning the transformer architecture with insights from multi-particle dynamical systems, 2021. URL
https://arxx org/ wwwp///....... 15142
Lawrence Craig Evans. Measure theory and fine properties of functions. Routledge, 2018
Hengyu Fu, Tianyu Guo, Yu Bai, and Song Mei. What can a single attention layer learn? study through the random features lens. Advances in Neural Information Processing Systems, 36:1 1912-199119 2023.
Stéphane Gaiffas and Guillaume Lecué. Optimal rates and adaptation in the single-index model using aggregation. Electronic Journal of Statistics, 1:538-573, 2007.
Borjan Geshkovski, Cyril Letrouit, Yury Polyanskiy, and Philippe Rigollet. The emergence of clus- ters in self-attention dynamics. In Thirty-seventh Conference on Neural Information Processing Systems, 2023. URL http:pss///oeeeeeeeiee... wttp:e/oorrrmidaaaaaaaaaaaaa
Borjan Geshkovski, Cyril Letrouit, Yury Polyanskiy, and Philippe Rigollet. mathematical per- spective transformers. Bulletin the American Mathematical Society, 62(3):427-479, 2025.
Tianyu Guo, Druv Pai, Yu Bai, Jiantao Jiao, Michael Jordan, and Song Mei. Active-dorman attention heads: Mechanistically demystifying extreme-token phenomena in 1lms, 2024a. URL httpps//awee wttp://ggg///.//.// 13835

---

Published as a conference paper at ICLR 2026
Zhiyu Guo, Hidetaka Kamigaito, and Taro Watanabe. Attention score is not all you need for token importance indicator in kv cache reduction: Value also matters, 2024b. URL htLhttps:////
org/abs/ 2406. 12335
László Györfi, Michael Kohler, Adam Krzyzak, and Harro Walk. A distribution-free theory of nonparametric regression. Springer Science & Business Media, 2006.
Dongchen Han, Yifan Pu, Zhuofan Xia, Yizeng Han, Xuran Pan, Xiu Li, Jiwen Lu, Shiji Song, and Gao Huang. Bridging the divide: Reconsidering softmax and linear attention. Advances Neural Information Processing Systems, 37:79221-79245, 2024.
Joel L. Horowitz and Enno Mammen. Rate-optimal estimation for a general class of nonpara- metric regression models with unknown link functions. The Annals of Statisties, 35(6):2589 2619, 2007. doi: 10. 10.121400995::000000000000
URL https:s:: org 10. 12144
009053607000000411
Jiri Hron, Yasaman Bahri, Jascha Sohl-Dickstein, and Roman Novak. Infinite attention: Nngp and ntk for deep attention networks. In International Conference Machine Learning, pp. 4376- 4386. PMLR, 2020.
Hui Huang, Jian-Guo Liu, and Jianfeng Lu. Learning interacting particle systems: Diffusion pa- rameter estimation for aggregation equations. Mathematical Models and Methods in Applied Sciences, 29(01):1-29, 2019.
Raphael A. Kasonga. Maximum likelihood theory for large interacting systems. SIAM J. Appl. Math., 50(3):865-875 1990. ISSN 0036-1399, 1095-712X. doi: 10.1137/0150050.
Angelos Katharopoulos, Apoorv Vyas, Nikolaos Pappas, and François Fleuret. Transformers are rnns: Fast autoregressive transformers with linear attention. In International conference on ma- chine learning, pp. 3156-5165. PMLR, 2020.
Michael Kohler and Jens Mehnert. Analysis of the rate of convergence of least squares neural network regression estimates in case of measurement errors. Neural Networks, 24(3):273-279 2011. ISSN 0893-6080. doi: http://dab.ogg//o.oooo///emmeeed .003. URL https://
www. www.ecceeeeeetccoo com/ http://rrrr..rroo.ccoc.e.eereeee http:///ii.eeeereee/////////0000
Soroush Abbasi Koohpayegani and Hamed Pirsiavash. Sima: Simple softmax-free attention for vision transformers. In 2024 IEEE/CVF Winter Conference on Applications of Computer Vision (WACV), pp. 2595-26000 2605, 2024. doi: 10.1 http///CV57000.0222...00
Hongkang Li, Meng Wang, Sijia Liu, and Pin yu Chen. A theoretical understanding of shallow vision transformers: Learning, generalization, and sample complexity, 2023. URL https:
arxiv.org/abs//2300 /ttp:/aab.222..2 2302.06015
Zhongyang Li and Fei Lu. On the coercivity condition in the learning of interacting particle systems. Stochastics and Dynamics, pp. 2340003, 2023.
Zhongyang Li, Fei Lu, Mauro Maggioni, Sui Tang, and Cheng Zhang. On the identifiability of inter- action functions systems of interacting particles. Stochastic Processes and their Applications, 132:135-163, 2021.
Meiqi Liu and Huijie Qiao. Parameter estimation of path-dependent McKean- Vlasov stochastic differential equations. Acta Mathematica Scientia, 42(3):876-888 886,, 2022.
Fei Lu, Ming Zhong, Sui Tang, and Mauro Maggioni. Nonparametrie inference of interaction laws in systems of agents from trajectory data. Proc. Natl. Acad. Sci. USA, 116(29): 2019.
Fei Lu, Mauro Maggioni, and Sui Tang. Learning interaction kernels in heterogencous systems of agents from multiple trajectories. Journal of Machine Learning Research, 22(32);1167, 202
Fei Lu, Mauro Maggioni, and Sui Tang. Learning interaction kemels in stochastic systems of in- teracting particles from multiple trajectories. Foundations of Computational Mathematics, 22: 1013-1067, 2022.
12

---

Published as a conference paper at ICLR 2026
Jiachen Lu, Jinghan Yao, Junge Zhang, Xiatian Zhu, Hang Xu, Weiguo Gao, Chunjing Xu, Tao Xiang, and Li Zhang. Soft: Softmax free transformer with linear complexity. In NeurlPS, 2021b.
Yue M. Lu, Mary Letey, Jacob A. Zavatone- Veth, Anindita Maiti, and Cengiz Pehlevan. Asymp- totic theory of in-context learning by linear attention. Proceedings of the National Academy
of Sciences, 122129):2250259912,, 2025. doi: 10. (0,0073/paas22522599222 2502599122.
URL https:
www. pnas. ort/
10. 10100..11/10aa1 http:/paa.2200259935 2502599122
Tom Lyche, Carla Manni, and Hendrik Speleers. B-splines and spline approximation. 2017. URL
www.cccshhhiic wttp:llaaa..g//oouoosssooo :9: 195737484
Pierre Marion, Raphaël Berthier, Gérard Biau, and Claire Boyer, Attention layers provably solve
single-location regression. The Thirteenth International Conference on Learning Representa- tions, 2025.
OpenAl. Gpt-4 technical report, 2024. URL |BLL/tttss//aaxii..r/////////// 08774
Samet Oymak, Ankit Singh Rawat, Mahdi Soltanolkotabi, and Christos Thrampoudiss On the role of attention prompt-tuning, 2023.
Jason Ramapuram, Federico Danieli, Eeshan Dhekane, Floris Weers, Dan Busbridge, Pierre Ablin, Tatiana Likhomanenko, Jagrit Digani, Zijin Gu, Amitis Shidani, and Russ Webb. Theory, analysis, and best practices for sigmoid self-attention. In International Conference on Learning Represen- tations (ICLR), 2025. BRLhhttp:: http::::////peeevvieeee net forum?ide Torummmd--2ahhgnnn.22
Michael E. Sander, Pierre Ablin, Mathieu Blondel, and Gabriel Peyré. Sinkformers: Transformers with doubly stochastic attention. In Gustau Camps-Vall Francisco J. R. Ruiz, and Isabel Valera (eds.), Proceedings The 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pp. 3515-3530. PMLR, 28-30 Mar 2022.
Johannes Schmidt-Hieber Nonparametric regression using deep neural networks with ReLU acti- vation function. The Annals of Statistics, 48(4):1875 - 1897, 2020. doi: 10.1214/19-AOS/
URL https://doo. org. 10. 1214/19-A0011777
Louis Sharrock, Nikolas Kantas, Panos Parpas, and Grigorios A. Pavliotis. Parameter stimation for the McKean- Vlasov stochastic differrnniill equation. ArXiv210613751 Math Stat, 2021.
Christopher D Sogge. Fourier integrals in classical analysis, volume 210. Cambridge University Press, 2017.
Mingjie Sun, Xinlei Chen, J. Zico Kolter, and Zhuang Liu. Massive activations in large language models, 2024. URL
http://axxvvv.r..o.. abs 240.. 17762
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, Aurelien Rodriguez, Ar- mand Joulin, Edouard Grave, and Guillaume Lample. Llama: Open and efficient foundation language models, 2023. URL httts:://// http:://axivvv.ooo httgg/bbs/20 2202 13971
Emanuele Troiani, Hugo Cui, Yatin Dandi, Florent Krzakala, and Lenka Zdeborová. Fundamental limits of learning sequence multi-index models and deep attention networks: High-dimensional asymptotics and sharp thresholds. arXiv preprint wxXiv22502.0000. 2025.
Alexandre B. Tsybakov. Introduction to Nonparametric Estimation. Springer New York, NY, 1st edition, 2008 ISBN 978-0-387-79051--.
Aad W Van der Vaart. Asymptotic statistics, volume Cambridge university press, 2000.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, E ukasz Kaiser, and Illia Polosukhin. Attention is all you need. In I. Guyon, U. Von Luxburg, S. Bengio. H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Ad- vances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017. URL 44care/eeeeea...03333cc444444aa2
13

---

Published as a conference paper at ICLR 2026
Roman Vershynin. High-dimensioaal probability: An introduction with applications in data science, volume 47. Cambridge University Press, 2018.
Johannes Von Oswald, Eyvind Niklasson, Ettore Randazzo, Joao Sacramento, Alexander Mordvint- sev, Andrey Zhmoginov, and Max Vladymyrov. Transformers learn in-context by gradient de- scent. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), Proceedings of the 40th International Conference on Machine Learn- ing. volume 202 of Proceedings of Machine Learning Research, pp. 35151-35174, PMLR, 23-29 pattps::/proceeddiieee press v202
Jul 2023,
mlr press
von www-://///o--/-o- owwaaaowswaaal22 html
Shulun Wang, Feng Liu, and Bin Liu. Escaping the gradient vanishing: Periodic alternatives of softmax in attention mechanism. IEEE Access, 9: 9:168749-16888 2021. doi: 10.1109/ACCESS. 2021.313820..
Sinong Wang, Belinda Z. Li. Madian Khabsa, Han Fang, and Hao Ma. Linformer: Self-attention with linear complexity, 2020. URL https::/aaaat wtw.wxwwwwwww//.//...o/5/ absp///ss/2200./. 04768
org
Xiong Wang, Inbar Seroussi, and Fei Lu. Optimal minimax rate of learning nonlocal interaction kernels, 2025. UtLthttss://arrt //tpl////./llll/////////////o/// 16852
Guangxuan Xiao, Yuandong Tian, Beidi Chen, Song Han, and Mike Lewis. Efficient streaming language models with attention sinks. In The Twelfth International Conference on Learning Rep- resentations, 2024. URL htttts://oppereeeeesee
net / wow.rrmmmi-nG7Gsaa-S NS5522
Rentian Yao, Xiaohui Chen, and Yun Yang. Mean-field nonparametric estimation of interacting particle systems. Conference on Learning Theory, pp. 2242-222222222 -2755. PMLR, 2022.
Yue Yu, Ning Liu, Fei Lu, Tian Gao, Siavash Jafarzadeh, and Stewart A Silling. Nonlocal attention operator: Materializing hidden knowledge towards interpretable physics discovery. Advances in Neural Information Processing Systems, 37:1 11::11377-113822 2024.
Biao Zhang, Ivan Titov, and Rico Sennrich. Sparse attention with linear units. In Marie-Francine Moens, Xuanjing Huang. Lucia Specia, and Scott Wen-tau Yih (eds.), Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, EMNLP 2021, Vir- tual Event / Punta Cana, Dominican Republic, 7-11 November, 2021, pp. 6507-6522 Associ- ation for Computational Linguistics, 2021. doi: 10. 10.18653/V1/2021.0 SBBSS//1/222.EMM.PPMMMMM EMNLP-MAIN.522 URL
emr.:22eeem.111.. emn.pp main. 523
A APPENDIX: REDUCTION FROM ATTENTION TO IPS ATTENTION MODEL
In this section, we provide direct connection between the IPS attention model and the softmax self- attention layer, which typically includes an additional normalization step. Consider sequence of tokens (X The output of the softmax self-attention layer is typically composed of an attention block with learnable query, key, and value matrices, Wq, WK Rdxd, with dg & and Wv Idxd that compute
Y Att(Q, K, V) softmax
OK
V, vdz
Q = XWQ, K = XWK, = XWv.
(A.1) WoW the score interaction matrix. Using
As explained in the main text, denote by A the definition of the softmax function, the output of the softmax self-attention layer for each particle can then be written
da
8x.
AX VS,
N x AX2
Y
Z[X]
[
with 3 > 0 being the inverse temperature parameter. When the number of particles is large, the partition function Zx[ concentrates around its mean-field value with respect to the empirical dis- tribution of the particles. If we denote by the continuum limit of the empirical measure, then [[X]= NZ,- N exT Avdu(y) conditioned on the i-th particle.
14

---

Published as a conference paper at ICLR 2026
For the IPS surrogate consider in this paper. adopt two standard simplifications (Sander al. 2022 Geshkovski et al,, [025] Bruno et al., 2025): we set d, = 1, and treat 2; as a constant (independent of X) that can be absorbed into the nonlinearity, and focus only the self-interaction for y j. and setting Vj to be a constant, we get our IPS Attention Model:
1 Σ OXTAXX) N
Y,
j+i
This reduction is similar in spirit to the surrogate model (USA) presented in Geshkovski et al. 20025) We note that possible extension of model to account for the softmax normalization would be to learn a function for each particle, 6t. We suspect it will not change the overall rate. In fact, as stated in Geshkovski al. (2025), this reduction seems capture the essence of the dynamics of the self-attention (SA) model. Therefore, to simplify the setting, we focus on estimating a single function.
B APPENDIX: UPPER BOUND PROOFS
We begin by reducing the distribution of the pair-wise particles the distribution of one pair by exchangeability. The exchangeability not only simplifies the proof of the upper bound, but also provides a sufficient condition for the coercivity, which makes the inverse problem well-posed.
Lemma B.1 (Exploration measure under exchangeability) Under Assumplion the measure P is the distribution of X2) Rd x Rd and has continuous densiry.
Proof. The exchangeability in Assumption 2.1 implies that the distributions of XX, and (X1, X2) are the same for any i yt j. Hence, by definition, the exploration measure is the distribution of the random variables (X1, X2):
P ((( B)
which has a continuous density by Assumption 2.1
B. PROOF OF THE UPPER BOUND IN THEOREM 3.1
In this section, we provide the proof of the upper bound.
We begin with the proof of the key coercivity lemma, which is crucial in bounding the error of the interaction function and making the inverse problem well-posed in the large sample limit.
Proof of Lemma Recall Rx(X),
Nー se4 I(x,, Xj). By definition
N Rogo-111) N(N 1)2
- (g.)
1 N
EE
ΣΣΣEA,,
U where Aij (g gx)((i, and Mijrs -ij By exchangeability,
1 N(N 1)2
N -
BAj., Agy
E EI
E(A 12, 1I XiD
1
E|
N
since E| 2 > 0. The statement of the Lemma follows.
Proof of Theorem 3.1 The proof is divided into five steps.
Step 1: Error decomposition. In this step, we decompose the mean squared error E[ 2 9.1 Lal to two terms. Using Lemma 3.4 i.e., the coercivity condition and the definition of (g)(g) =
15

---

Published as a conference paper at ICLR 2026
E [| Rg ], we have for on N
ex | [ar(( v) - go (x, 1l
Ex (TM)) (g.(
1 [|YY - Rg. [X]]]]]
Ellly - -RiM [x]]
N
N
Y Rig [X]] Dwu]] N
[|Y - Rg. [x]1
(B.1)
N
Let Bys = c1 log(M) with some constant 01 > and YM == min( BM: max(- - Max; Y)). Let us denote
TTM = ( - ENs (g.)]
(B.2)
and
1
1 N BLIYYM - Rg [X][3] Ti,
T2,M
F||Ym RiN [X]1 DM]
(B.3)
N
1
T3,M == E [IIX Ras [X]] DM]
N [[]Y -
(B.4)
B[1 Road
[XII [D]] + N [ R. [X]]
By equation B.1 we can decompose the upper bound of the mean squared error as
E || (
E
ga,, v) (ddp:.) w)
cx' [E[ + E + B[Ts.M]).
(B.5)
We shall proceed with our proof by bounding (E[T,, 132 in the following Steps 2-4 via approxi- mation error estimate, covering number estimate, and sub-Gaussian property, respectively.
Step 2: Bounding E[Ti.]] via polynomial approximation. Recall that GM is the minimizer of the empirical error functional EM (g) over the estimator space Gi Thus, we have
Ear(āM) (M(()) & Em Ens(ge);
where gr.6% is a minimizer G attaining inf inf (Ex(g) - Exp (g-)] (see, Györli al. 2006 Lemma 11.1)). Therefore,
E[T ((M (Mr)
E Emr Exr(1+))
Eg Egol
inf [Exo(]) (x gesr
(B.6)
Note that
Eg)(g) - Exo
- E [|| - [X] + 1/1 -1|n1
N
E
1
Σ
[g 9. 9.](X,, X1)
(B.7)
N
1
Applying Jensen's inequality to get
N N
1
E
Σ - 9. 9x1((x:),))
1
Σ
BlI
g. x.)(
N
1 j=1,j+1
N(N
1)
(B.8)
16

---

Published as a conference paper at ICLR 2026
and by the exchangeability assumption A1
have that the expectations equal and thus
1
inf gegt,
l1g
g. 12
2
inf se A1
()(( - b)
(B.9)
Next, setting A A, in equation B.9 it is clear that
E[Ti,
E
& inf delkkar
[0((,,))))) -0. u) (()ppaa)
2
inf de0%
(6(u) - (u)) ue(-a,0
sup
Then, choose e following the construction in (Gyrrfi et al. 2006 Lemma 11.1) and that 6. E C (L, which shows that there exists a piecewise polynomial function f of degree or less with respect to equidistant partition of [-ā, a] consisting of KM intervals of length 1/ K/KM- For any x, p and any matrix A E Idxd such that u 4), E ā, a]. we will choose the dimension KM (to be specified later) that
La
sup [ó(u) p.(1)) & NE ( [0
|3|1K
We thus conclude that
2L2028
M[Ti,M]
(B.
(1811)2
Step 3: Bounding B[T2,ar] via covering number estimates.
We introduce the following nota-
tions to simplify the presentation. Define AE (g) e(i (g) c (g.). Also, we denote
A (ÂM) == E[ Rig. [x] DMrl E| Rg. [
where IM E -o, depends on the samples Das = { (Xmm y JMM and write similarly
AE (g) = EIJY; - Rg [x][ - B[ Rg [x
for any g E Kr, Note that AE (g) = A (g) for any (deterministic) g E G
is straightforward to observe that M[ can be expressed as the average error per particle, that is, E[T2,1r] 1 V. BTT(() where T:()) : AELi), (āx) TT(i) with T 2 Mr (πM).
To estimate E[T suffices bound the following probability tail for the i-th particle
P
(T((
2, > 1
P
Ae (āM) - SE (īM) [ AE (fM))
1
P
3ʃ Kn
Aeft)) De (f) AE (f)
2 [t Sebl, (m))
1
(35 Kr Ael (f) - (E 1 11 A Un))
P
(B.11)
We first observe that the probability tail above depends on the joint distribution of all particles since the term Ac( (f) in equation B.11 involves all particles. To bound the tail probability of
TT(i)) we invoke Györfi et al. (2006) Theorem 11.4), which is applicable to classes of uniformly
bounded functions. In our setting, this condition translates to the boundedness of the operator Rg- Specifically, if gl & B., then for all i [N], we have |R[X]d Bg- Recall that B
17

---

Published as a conference paper at ICLR 2026
C1 (M) and Cu := ([0, 1///// Applying Theorem 11.4 in Györfi et al. (2006) to equation B.11
(with a = t/2 and é = 1/2), we get for arbitrary > 1/M
P
T
2.M
$) $ 14
sup
M
80BM
t
- Kr PM
24-31-013
14
sup EC Fmmm
NI
80
(B.12)
where (s, G Kr, PM) is the empirical covering number with respect to the L3 radius smaller than over the function class "r,
Employing the identity [[ So P(( t)dt and the standard integral decomposition Se So + Se with be determined, we get for & > 1/M
P(T (1) 2 > t) & e [ P(T.. > t)dt.
E[T2Ms]
(B.13)
Then, substituting equation
B.12 equation B.13
leads to
1MM 20-244 dr.
B 2.M & e
14
sup
N1 808as Ii,KM
(B.14)
(X""CCN MM Ima
Notice that we can bound the covering number by its value at 1/M since s e 1/M inside the integral in equation B.14 when & 2 e. It then follows that
2 & e 14
sup
Ni
80BMM 9 Kr PM
e 24.214.84 dt.
(B.15)
(Xm pM
We can now apply the estimate of covering number in equation B.22
N
M
(I,,M M) [22,,, M) Ls.Ms eM
E + 42
(B.16)
M
with LI, == 12rāBB 80B L2.M = B4cB 80 and La.M == 24 214 B1,- Since the quantity on the right-hand hand side of equation 16 arbitrary, we may tighten the bound by choosing
L3.M log [42 (L) 2rd (L2M 2M)
M
which yields the desired upper bound:
L3.M
M[ &
+ log (42) + 2rd log (L1,3)
M
2(KM(s 1) 1) log (L2 + 2(KM(s + 1 + rd) log(M)
L (20K Ms + 5rd) log(M)
(B.17)
M
when M 2 max(42. IT,M I2,2s)
Step 4: Bounding B[T3,ar] via sub-Gaussian property. As Rg. [X]; & B By and Riss [X]: & Bg < Bas a.s. We assume that the noise 77 is sub- Gaussian and that Rg is bounded for any E G.S. Thus, using Lemma 2 in Kohler & Mehnert (001 with Ym and BM given above, one obtain that with
B[T
$
E E[ Rg. [3
E Y, Rg. [x:]]]]
N
Y RB [x,1+]] - E[ - RaNs [x,1
N
log
M
<
C2
(B.18)
M
for constant C2 > 0 independent of M and N.
18

---

Published as a conference paper at ICLR 2026
Step 5: Deriving the upper optimal rate. We now combine the bounds from equation B.10 equa- tion B.16 and equation B.18 which control the terms T Ml. [[T2.M] and E[T respectively, to obtan an upper bound on the total error in equation B.5
E AM
9x112
2L
(2.M( MS + 5rd) MM)
+ log( M)
< CH
+
(B.19)
(s!)>K>
M
M
2L2
La.M20K 20 M (1+ + 5 log(M)
log(M) M
& CH
C2
(s!)*
M
using the assumption of the theorem rd <
M Tog M
and setting the value of KM as
M
KM
(B.20)
20L3,
log M
relatively straightforward choice of KM balances the terms in equation B.19 and leads to a desired upper bound. We note that careful choice of Kas may affect the constants and the power of log M) the upper bound.
-1 Putting equation B.20 back into equation B. and noticing CH
& N, we get
(2,
|log M M
20
log M M
20
E |0oN 2-1iz]
CH
(s!)2
(1 5l.3,M)
C2 log(M)
M
2L (23s20sss 23
1
(log M
3547
28
< N
+ (1 +1+ 5L3 + C2
(B.21)
(s!)²
M
when M > max(42 2rd L2,3s) with LI. == 12raBB 80BM L2.M == 24eB, 80
Recalling that L3.M = 24 214 - Bi = 24 214 C1 log(M), we get from equation B.21 that
E 10 - ge < N 22024 214 C1 sa)"
[lo
(s!)2
36
28 (log M)
M
2UFI
+4
+ NN N[1+5. 551 24 214 + 02)
M 2341
N ci T7(
+ C22 Dlog( M) bet m21(29
(s!)2
M
for some positive constant C1 C2. We complete the proof of Theorem 3.1 with CN.L,,D [3(sa)
N[C
(2]) + C2].
Finally, highlight the tradeoff between the parametric and the non-parametric part of the error, we present the following corollary. This corollary is directly derived from equation B.19 and equa-
tion B.20 without using the assumption rd A8
J84T
log
Corollary B.2 Consider the estimator GM defined in equation 3.1 computed on data M i.i.d. ob-
servation satisfying Assumptions 2.1 and (B1) Then, for IM defined in equation 3.1 it holds that
(
[log( M)]
max(2211)
(log M)²
1 - g-1lig| < N
0
+ C2
Card
(s!)²
28 M 23
M
where C1, C2 and C3 are positive constants (maybe take different values than in the Theorem 3.1
19

---

Published as a conference paper at ICLR 2026
B.2 AUXILIARY LEMMAS FOR THE UPPER BOUND
Recall that the covering number (E, G, d) is defined as the cardinality of the smallest e-cover of g with respect to the metric d. When d the Euclidean metric, we omit it from the notation and simply write (e, 9). It is also common to take to be an L--norm, either with respect to a probability measure p or its empirical counterpart PM. In these cases, we write
Ny = ((e, lle,), Ng(e,9.PM) = (e, 1legze
1 We next derive an upper bound for (1 KMr PM),iie... p 1, by covering the matrix component and the functional component separately. Our argument combines the covering number estimates for matrices from Vershynin (2018) with the results of Giörr et al. (2006) for function classes.
Lemma B.3 Let 9r, Ky be defined in Definition 2.5 Assume that the sampled data {
M N.M Jim-l are
distributed according to Assumption 2.1 Then we have
(12ra
2nd
(2ABB
2K 2
Ni(e, (. PM) & 3
(B.22)
8
8
Proof. Recall the matrix class defined in Definition 2.3
Aa(r, @) = {A IR ddddd rank( A) & r, || < a].
Write A QK via the truncated SVD, where Q U dd and K V, Rd with singular values belonging to [0, a]. and U,, V, are semi unitary matrices of size d x r, and E, a diagonal matrix of size r r. Then
Q Tr(E,)) < rā,
| < rā
Indeed, let 8 0. The d-covering of the matrix class Qral Qra(Vrā) = (Q Rdxr 1QQ| & Vva is equivalent to the d-covering of Brd( (vrā), centered ball with radius vra in Red and (Verhynnin 2018 Corollary 4.2.11) implies that
N(ee, 2ra(Vra), 1--1)) Nle,, Bra(Vra)) & (3rrā (
(B.23)
Notice that for A1 QiKT and A2 Q2Kg with (Qi E Qra( K₁ E @ra(Vra)Ke such that |Q: Q2 & 6/(2v | -22llr & 6 @). we have
| - A2llop = [QQIK] - Q2K lop < 1Q Ki K2llF + 1Q Q211 < 6.
Moreover, by Assumption 2.1 that X,, X, lie within the unit ball and the assumption that @ E Φx degree-s piecewise-ppllynomial approximation with KM intervals, we get:
(á( A.) - (( (z))) BolA1 A2 BBd
since |||||| |y| < 1. This proves that A1, A2 are within 8 in operator norm, the corresponding functions differ by at most Bod. Thus,
t N (2B 8, Pr PM) & Be Mi 8, (0((z, (Z.0))) : DE & h.r))
(B.24)
On the other hand, Györfi et al. 2006 Theorem. 9.4-9.5) shows the following bound
(G + 11
2kx(
12e
2x
N 8, D KM PMr) < 3
< 3
Bg 8
8
for the empirical measure PM in Definition 2.1 with {xm e Ca) M m- Putting it back to equa- we obtain that
tion B.24
3. 6rā 2rd 12e
2km(++1)-2
NG (2B 8, Si PM)
(B.25)
Now re- ce-parmmterriee by E = 2B,8, i.e. 5
e/2B., and absorb constants in equation B.25 This
gives our desired estimate in equation B.22
20

---

Published as a conference paper at ICLR 2026
Remark B.4 As by-product, we show that 2vra -over for Q and K induces 8-cover for & in equation B.23 give
Aa(r, a) in operator norm. Taking all pairs 3 and substituting 20ra that
N6 0), lap)) $ ((5)
(6rä 2rd
C APPENDIX: LOWER BOUND PROOFS
Lemma C.I (Continuous density of the bilinear form.) Let (X, E R2dd have a joint density P E (D(D) with D 12dd being bounded open set. Let A Rdxd have rank " 1, and define = AY. Then:
(Existence) For every 1, the law of is absolutely continuous with respect to Lebesgue measure on R with density denoted by pu.
(ii) (Continuity) Ifr > 2, then pc E C(R).
Note that r > is sharp for py to be continuous: for r 1, continuity at 0 may not hold: if X, Y independent standard Gaussian in IR and A = I, then U XYY has density pu( = Koll)) where Ko(x) ~ log x as x O, so py is singular at 0.
Proof. The proof consists of three steps: reduction canonical quadratic form on R existence of the density, and continuity.
Step 1. Reduction to the canonical quadratic form on R Let A WEVT be singular value decomposition with = diag(or... .01.....Grr Cp......,,,.......... 0. O..... 0). where o; > 0 and W, V e gdx are orthonormal. Set W X 3 v Orthonormal changes preserve absolute continuity, so (a,3) (3) has joint density p(a, B) p (Waa a, V with support D {(a, 3) (W-1x, V-1 (x, y) E D}, which bounded subset in Rddd Split a (a at) and (8t)) where the superscript (r) denotes the first r coordinates. Then
U = XTAY X = Σ o.
(n) 3/r)
Integrating out (a+1, , ) yields marginal density g L' (I22) ) for Z = ((()))))) and it has
bounded support, which we denote by Ω. Thus suffices to work in 2r with
(a 3) Σ o;
U= +(),
Z Z~ge (
Step 2. Existence by the coarea formula. For any bounded measurable test function & E R.
E [[p(U)) = ((((2))
(C.1)
on
Note that & has gradient Vob(o, 3) = (0131. 3r aii,,...... ar))). which Lipschitz contin- uous on Applying the Coarea formula (i.e., for any f QE Rn Lipschitz and y (RR")
Sam 9(2) V [V( dz
Se (S--(w)) g(=) (())) du, where 7- H²-1(2) denotes the Hausdorff measure, see, e.g.. Evans (2018) to ʃ = with g(z) = ((z) (+()))/\VV(( gives
[ v()(2)) <(2) dz = [ (Jo g(>)
d2 (x) ((()) du.
[+(())
Hence, (u( So (())
((=) [+c d7 for u o 0.
Note that under the change of variables 2 Mu w the Hausdorff surface measure scales by |u| (2r-1)/2 and | by |u| 1/2 Then, for u * O, the above equation can be written as
(Dor q 1 w) 2 (
((((2)) ((2) dz=
|u|--1
p(u) du.
(C.2)
JB
21

---

Published as a conference paper at ICLR 2026
Comparing equation C.1 and equation C.2 the push-forward measure is absolutely continuous with density
q( w) an(²-((w)
Pu (u) = |u|"-1 ((v)==))g(())
(C.3)
for all u # O. This proves (i) for all r > 1.
Step 3. Continuity. Let (t) = Ele"d] Iga. (x*(()) ((2) dz be the characteristic function. The
0
Σ
phase (2) is non-degenerate quadratic form with constant Hessian H =
(of full rank
Σ
2r ). By the standard stationary phase bound for quadratic phases (see, e.g.. (Sogge 2017 Theorem
1.1.4))
(t)( & C (d)=
with C depending q (e.g. if q C then C depends on finite number of derivatives; and it extends to general q E L since Co is dense in L'). Hence, if 3 2, then Eu e I. (R) and Fourier inversion yields bounded continuous density pu(u) 2z SR e (u(()) dt.
Next, we provide the proof of Lemma 4.1
Proof of Lemma 4.1
Consider
Uij = X A.X,+
= XT
so that g(X;, Xz) = ((Vg)) and g" (X,, = (U,r) Recall that pu., is the density of U3y and pu II 2 2isj PU Also, recall that the following functions are defined in equation 4.2
N
N (u:)(u)
(ur(u)= = E BT (V)))))) = uJ, ((u): = Σ
Σ
Vo(l)
N(N - (u)
Since Σ/ Σg 2y=1,f41 N(N 1)
PUry(M
1, have, by applying Jensen's inequality,
N
PU.,(u)
(b(u) - (w))² =
Σ
Pig(u) - (u))
N(N - 1)pu (u)
(=1
--1j=1j
PU,, (u)
(u) (u)
(C.4)
N(N ())
Also, by applying Jensen's 's inequality to the conditional expectation, we have El ②.. (U+)) [V[ o. (U,)) (U,,)
([] o. (U. (U,)), S (er((u) (w)l pui, (u)du.
Averaging the pairs as in equation C.4 we have
N N
Σ
Σ
El
B((o(V))) - (U,)))
N(N - 1)
11
(e)(()) (1) 2Pey (u)
Σ Σ
po po pop (u)du
N(N - 1) 1-1 1
((()) - (w))²² (u( du,
which is the desired inequality.
Proof of Lemma 4.2 construct K = |co.,o M 2
disjoint equidistant intervals.
Lo 8ng
( (re - Fre-hM.Te horethm)]E hM) with hM
(C.5)
22

---

Published as a conference paper at ICLR 2026
where {re), ny and Lo are specific values that will be determined below. We will define the intervals by separating into two cases: one where the density of pu is bounded below by ag > 0 and one where it is not.
If (e(U) >0 2n > O, we can simply use the uniform partition of supp(pu) to obtain the desired (dr)- That is, we set no 1, To 4, and rg -a (2f - 1)h3 If py is not bounded away from zero, we shall build the partition based on its continuity. Since pv is continuous on [-ā, a]. the constant ao au.aa]- (x) exists, now consider 2p ag A 1. We can construct the K intervals described in equation C.5 which satisfy the following U₂ A = Ao == {ue [-ā. a] pu ag}-
Let Lo ==
1-2g, Since for all u E Ao, pr)()) & ao and for all u E Aς. polu) < an together with the fact that = SA, pr + SAg po(u)du, we get:
E agLeb(Au) + a2 Leb(Au) = Lo & Leb(An) & 2a.
(C.6)
Also, note that the set Ao is open by continuity of pu. Thus, there exist disjoint intervals (aj, by) such that Ao = ( b,). Without loss of generality, we assume that these intervals are de- scendingly ordered according their length by aj. Let
Lo 2
min(n (n: Eb, -aa))=
(C.7)
One can see that no Now, we construct the first nı disjoint intervals (De (re- - har rt + has) by) such that rg = 01 + E and n1 1 11-01 If n1 2 K, we stop. Otherwise, we construct additional disjoint intervals (de (r2 hM, + h2)))+t and continue to (az:b) by) until obtaining K intervals {Ae}-
2h
(a2, similarly,
To show that will at least obtain K such intervals, show that K. > K, where K. is the
total number of intervals ( Since the Lebesgue measure of (aj, by) U Ae is less than
M for each j, the Lebesgue measure of the uncovered parts UJ- (a,, by)) (U-=1 Ae) is at most 2nghM-
Thus, by equation C.7 the intervals ( must have a total length no less than La -/r 2 And since each of them is in length of 2h the total number must satisfy:
Lo
K. 2 2
M ((2hm)
and plugging in the definition of hM from equation
C.5 we get:
K. 2kno no K.
Now we construct hypothesis functions satisfying Conditions (DI) (D3) We first define 2 func- tions, from which we will select a subset of 2s sepaarttd hypothesis functions,
dw (u) = Σ webe,,((u) w= (wi,... .R) {0, 10.
where the basis functions are
( Lh v
M-Tz 7e
u L-ā- a]
(C.8)
with (u))) = (2m) ////21/2 Note that the support of (r) is Ar, and SA, M (u) =d
=
n 2821 21 By definition, these hypothesis functions satisfy Condition (D1) i.e., they are Holder continuous and
WeeMl & & & L|poll < L( < B
since hM
To & ag with dg l and |pollso 28
8no k K
Then, denoting (x) = )دا (z), we proceed to verify Conditions (D2) D3
Next, we select a
subset of 28 -separatdd functions (øu. &wnn } satisfying Condition D2 i.e. (wwck)
23

---

Published as a conference paper at ICLR 2026
&-10) 28N.M for any 1' E {1...., Kj. Here 8N.M CICo,N M कीं with C being positive constant to be determined below. Since A, supp( = Dr are disjoint, we have
llw - -ulll,, = =(12)
1 (e - (() (o(()ddu) Σ
R
RR
R
S pu Jac
Σ
(we w/)²
Since pu) 2o over each Ar, have
S Lebe pu (u)du ao S (w) du hg |//12
23+1
D.
Applying the Varshamov-Gilbert bound Tsybakov ) with K > 28/8 such that Σe (wl
2008
Lemma 2.9), one can obtain subset for any lo 5e k E (1,..., Kj. Thus,
(1)
R
we
K
Lo
8+1/2
11ow Pul1
SngK
~o
K 1/22
Lo
9+1/2
(-(++1/2)
2/2
8m1
/ L 11ll2
Lo
9+1/2
K-8 SN,M
2/2
8n1
where SN C1 2841 with
v Van L1
Lo
8+1/2
C
4v2
8mi
Im=1- we first compute the Kullback-Leibler (KI.) divergence. Define (XT²) AXTT Then for each m,
To verify condition (D3) for each fixed dataset {X
R TM J.
Σ (u.)).
N
j
Under the hypothesis M,,M, the density of the outputs {Y "mm is
M II
Pk ,
MM
Ro Lx
m=1
where ndh Ied represents the observed output ym, By definition of KI. divergence and the i.i.d. noise assumption,
DKL (P.. = ff... ... log M
Po
I1
PP(""))d
m Po (ym + Ron.se [xm)
m--
This simplifies
DKL (PA, Po)
Σ
log
Pa nm Ro mr (Xm]) "
Finally, by the noise smoothness assumption
2.2 for each m,
(v) log
(v+ dy Cy cylv12
P. (v)
24

---

Published as a conference paper at ICLR 2026
where v Re [X Summing over 1,...,,M. M yields
DKL (Px. & Cy
Σ m=1
Rs ar [xm]]]
(C.9)
Employing Jensen's inequality, we have
N
N [lo
N @K.M (u²))
Rog, Mr [X
Σ )u
N-1
(C.10)
Recalling that (v. 1 (u7)) Li
2 w/ Ve,M (ufj), where supp(ur,M) E De are disjoint and
Lh w x (uzesee we have
has
( (uff)1
(1) Σ W (eeas(u)))) 12
(uffede))
(C.11)
(k)
where we have used the fact that 0 &
< 1. By plugging in both equation C.10 and equa-
tion C.11 into equation C.9 we obtain
M
N
DKL (PR, Po) &
Cy
Σ
Σ
1 Lugessi
N
m=
2= jzt
1=1
Cip 1. 191.
29
K
Σ
1 Auzgsee
N
k.J.
Since the intervals {Ap) are disjoint, the inner sum is most The total sum over i, m therefore bounded by 2 M, which gives:
DKL (Pr, & e, 1 N M
Hence, by assigning haM-
Lo 8ng
from equation C.5 and K
[co,xe M 5641 1. we obtain
1 K
Lu
29
K
28+1
D KLL
P Po)
Co 1
N
R-28
K
8mg
CO.N
1,
Lo
29
K < aog
28+1
8mo
Co.N
29
with
G 1F4 CU.Y
Ln.
since K > 28/8, Thus, for condition
(D3) to hold, i.e..
log
< 1/8, we need
Lp 8rz
28
28+1
6.c, 11b.,
C0
Following Co,N = Co. CETI, it suffices to set Co to be
Lo
28
Co = (32
)
8no
To prove the lower bound minimax rate, we will use the following lower bound for hypothesis test error, e.g., Proposition 2.3 T'ybakov (2008) or Lemma 4.3 in Wang al. (2025)
25

---

Published as a conference paper at ICLR 2026
Lemma C.2 (Lower bound for hypothesis test error) ) Ler θ {0x]k_ with K 2 2 be of 28 2s-separated hypotheses. i.e., d(0k, (2)) > 2s > for all 0 & k < & K, for a given metric on
+ Denote PR Pd, and suppose they satisfy Pk. < for each k > = and
K
1
Σ
(KL, Po) & log(()), with
1/8.
(C.12)
K+1
Then, the average probability of the hypothesis testing error has lower bound:
Pa # k) log(K K + 1) - log(2) a,
inf
Σ
(C.13)
log(K)
==
where inf infkes kes denotes the infimum over all tests.
We aim apply Tsybakov's method to simplify probability bounds by con- sidering finite set of hypothesis functions. Reducing the supremum over CL) to the finite set of hypothesis functions, and applying the Markov inequality, we obtain
Proof of Theorem 4.3
Es, 11 Φ. 12
sup (L.a)
10.
Exp,, [1āer ox, ou.Nrlig,
max dv.M e (Vo.i............
NR, Pon [1ŌN @N,,rll1 SN.M
max
du.nd o ( .x.........
K Σ Ext...
(oon. (lōar - ou,M 1y SN x x .x.,., x
(C.14)
K
where the last inequality follows since the maximal value over the functions is no less than the average and since ((AA) = [[[A] Ez Ez[E[[a|Z]] E[P(A[Z)].
Next, we transform bounds the average probability of testing error of the 28 wew.ar-epprraee hypothesis functions. Define kust the minimum distance test:
kiestt =
arg min I Φu.M Lig'
ko.....,KK
Since Ok M is the closest one, we have that 11am - ob M 12 & 11xm -k.Mllz for all k * Meea Using the fact that the function Φ built as 28 separated functions and using the triangle inequality we have:
2
10 Ó 120 & 110m O + 1l Mu.Ml < 211@em ox.Mllez
so SN,M & 16E - Ōx,nrllez, for all * keest- Hence,
P P (1pM - db 12p 2 8NNM x x!.... xx) 2 (ireest * 11,
(C.15)
Consequently,
K
Por, (1ōm- - 2x > SNN x! x..... ,.,...,MMM)
K + 1
k=
K
K
inf
TP Ponne (Riess * 1 x²)
inf Aist
Σ k-
Ps (hiest * k)
(C.16)
K +
K + 1
where
(x)
Po Pon ( (.IX
The Kullback divergence estimate in equation
(D3)
from Lemma 4.2
holds with 0 < a < 1/8, and
by Lemma C.2 and the fact that K 2 Z in equation 4.3 increases exponentially in M,
we have:
K Pa (Krest * k))
log(K (K + 1) log(2) a > 2
inf Rese
>
(C.17)
K +
log(K) K)
km0
26

---

Published as a conference paper at ICLR 2026
if M is large. Note that the above lower bound of inf
Σ
k== Pk Muet # k) is independent
K+1
of the dataset [Xm) mm-1- Using equation C.17 eequation
C.16
equation
C.14
we obtain with
co [C1
sup d.eca (L.))
Es. |1 2.1i,,
N.M
Co
2841
M 20+1
(C.18)
for any estimator. Hence, the lower bound equation 4.3 holds.
Proof of Theorem 4.4 First, reduce the supremum over all A, to single one. Let A Aa(r,ā)
with rank( A >> 2. Since
AΛ = (9 (bxTA'yy) : C we have for any 9.
loll & BB| = (L, Bo,
3 --1l2z > sup 3 9. 9.l2gg
(C.19)
Rve@e (L.),.0)
g.ErA
Thus, to prove equation 4.5 it suffices to prove it with g. G
Let U be the random variable defined in (4.1) with A. A Then, Lemma 4.1 implies that
1
g. 2 2 11 o. 6.17? Pea
for any g(x,y) == 0(x Ay) with Z L2 and A E Aa(r, a) and any J. E GaI. Here, v defined in equation 4.2 varies according to ÿ since both A, and the distribution of X are fixed. Taking first the expectation over Z. then taking the supremum over g. E 9A followed by the infimum over Á and o, we obtain
inf sup Eliğ AcAa(na) a. JELL
9- ll22
sup 0.e0" (L.a) 1
inf
Eliú o. 0.122 PU1
(C.20)
&..
Meanwhile, Theorem
4.3 gives a lower bound
lim inf inf M- LE
sup (e,a) 1..
20 M 2D E
211 13
3 No -
(C.21)
with cu > 0.
Combining (C.19
C.21
then obtain:
lim inf inf -
sup
28 M 254T
9 - g.12:
L. Bg.a)
lim inf inf sup M g.
M 2 E
1 9- 9-122g]
lim inf inf
sup
20 M 28क E 2
20.123
2
Co.N
29 28+1
M- weL 2 yi
e. (L.a)
10. n.
which gives the desired result in equation 4.5
D NUMERICAL. SIMULATIONS CONFIGURATION
This section provides detailed description of the simulations presented in Section 5
D.1 DATA GENERATION
For each sample size M, we run Monte Carlo simulation over different seeds as follows. We draw
token arrays (m) (x(m) x(m)
CN i.i.d. with x(m) Unif[o, 1nj sampled i.i.d
27

---

Published as a conference paper at ICLR 2026
and construct the (X("))) A. x.m) terms, evaluate the interaction via d. (the sampling method of de and A. is detailed below, and aggregate and add i.i.d noise 7i (m) _N(0, o²) described in equation 2.1 to generate y:(m) (m)
For each simulation, we sample the ground truth interaction ga (x, y) - 0. A.y) by drawing random o, and choosing A.. We represent Φ. a B-spline degree defined on an open uniform knots with K basis functions on [-1,
K.
(.(2) Σ A (cu))
For each seed, draw 0. N(O,, Ix,) and then normalize for ||0.|| VK..
D.2 ESTIMATOR
If A. was known, the estimator can be computed by setting A = A. and setting o(u) = Σ Bx with degree Pes and chosen according to the ridge regression formula:
Ô= (U U + Aal) -1 UTY, y.
(D.1)
where = (U),,)),.)) E RANKK with
Ulm.0)&
Σ
Ba ((x ( "Ax(m))
(D.2)
N-
3F1
and = (X:(1)) RNMX
However, since A, unknown, the joint estimation of (A, Φ) is non-convex due the composition 6(x Ay). To mitigate local minima, we use hot start and an alternating scheme. We perform the hot start by setting ( A. + AA with Aa being a perturbation specified in Table I and setting the initial ((0) as the matching ridge solution D.1 In the PyTorch implementation, the scheme includes a description of the function as a neural network. This is because representing it as B-splines directly would require differentiating through the B-spline basis, which is cumbersome for automatic differentiation. To address this, we introduce neural-network surrogate Pnet that approximates the spline and can be used as differentiable link in the A-step.
Alternating Optimization for J,
"UT with U 1. Hot start: set (0)) A. + Aл and compute ((0) (UTU + -oT)
computed according A in equation D.2
2. For t= I,...T':
(a) Approximate the current spline using a multilayer perceptron (MLP). Fit an MLP
o (t-1) a grid {ue} to minimize Σe [ (1-11) ()e)))(e)) - (ut=1)(w))1
(b) A-step through optimization. Update A by minimizing the empirical loss with &
$ (t-1) held fixed using the Adam optimizer
min MN
Σ
Σ - (x()) ( x(m)) - -x(m)) + AA 1A J+s
(D.3)
1=-
(c) 0-step through closed form. With fixed at A compute g(t) by ridge regression: stack y MN from y((m) and build U E RMNNK x with
N Σ (T x(0))
U(m.)).
and compute
000 (UTU + >o1) -UT
28

---

Published as a conference paper at ICLR 2026
Choice of Kest and Ag- We set the number of spline coefficients by the bias variance trade-off for a 8-Hölder smoothness as done in equation B.20
Kest = round Kscale log M M
where Kscale a chosen constant. For the ridge regularization constant A we follow the standard scaling for least squares models with MN responses and K coefficients, the variance of & should scale like (/MMN), take
Kea
Ag = Agcale M
D.3 ERROR ESTIMATE
We measure accuracy via the estimator test MSE, sampling never seen inputs X Unif[0, /j and evaluating:
Neant
N
9 (x("() :x/m)) g. (x.mm) (xfm))))ff))
MSE
Ntest
N(N
fti
D.4 SIMULATION PARAMETERS
The following table details the parameters used for the simulations described Section
Table 1: Chosen parameters for the simulation
Parameter
Value
Seeds
300
A.
Diagonal matrix with i.i.d. entries An = 1, Vi > 1 Aus ~ Unif[-1, 1]
Sample sizes M
[20000, 27355, 37416, 51177, 70000]
N
3
Gaussian noise dy
0.07 (Gaussian)
Estimator degree
Peu P.
K.
16
K Kecale
((a) and (b) for P. 3]: 16
[(b) for P, 8]: 30
Basis size Kea
[(a) and (b)
3J: (73, 78, 82, 92) (matching the grid)
[bb) for P. 8]: (50,51, 51, 52, 53, 54) (matching the M grid)
Aa
1
Ascale Ag
((a) and (b) for P. = 30 (6.85, 5.30, 4.12, 2.46)
[(b) for P. 81/2.50, 1.86, 1.39, 1.04, 0.77)
(matching the M grid)
AA
Entry wise Gaussian noise with an std of 5/d x 10 4
T
A-step optimizer
Adam, Ir 10-8 8, 20 epachs.
(0) architecture
1-hidden layer of width 32 (GELU activation)
$ net optimization
1000 epochs (Adam) Ir= 0.01
Test set
2000 samples
29


Reviews:
[{"review_id": "nXkQrHrsx6", "reviewer": "Reviewer_xCfy", "summary": "This paper concerns the study of asymptotic sample complexity for learning attention like models.\nThe main claim is that attention like models are free from the curse of dimensionality.\nMore precisely, while classical results for function regression leads to $M^{-2\\beta/(2\\beta+d)}$ scalings,\nwith beta the Holder exponent characterizing the smoothness of the function and d the embedding dimension,\nthey get a scaling corresponding to $d=1$.", "questions": "In order to better understand this result I have the following questions:\n\n- do the scaling in $M^{-2\\beta/(2\\beta+1)}$ corresponds to what would be obtained if the attention matrix A would be known in advance,\nbecause then we are back to the parallel regression of N functions of a real variable (x=X_i^tAX_j, leaving aside the extra difficulty of the convolution over the particles j)? If this interpretation is correct,  does this mean that the identification of A (i.e. the r directions among d)  do play a role only in a transient regime? is this the reason for the hypothesis that one need a number of samples $M > (rd)^{2\\beta+1}$ (in my understanding this is the amount of samples it takes to approximately align with A), beyond which the sample complexity becomes 1d?\n- Is this also related to the reason why the rank of the matrix is not involved in the asymptotic?\n- I did not understand the role played by the interacting particle system interpretation for obtaining this result, it seems not to play any role in the proof.\n- Concerning the regression assumption: usually the g function is actually not observed, it represents a  kind of virtual supervised function regression setting taking the functional form of an attention layer, so why should we expect this regression setting to be relevant to the full attention layer, i.e. when combining the attention weights with the values?\n- if we compare to ordinary NN layers, should we obtain similar behaviour? I presume for a single layer function like $f(x) = W_1\\phi(W_2^T x)$ the same rate should hold. What about more complex architectures? a rapid summary of existing results obtained so far for NN functions could be useful.\n\nOverall my recomendation would be to save a little bit a room in the plain text to discuss the interpretation of the results.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "The paper is making a strong statement, which is interesting in many respects and raises a lot of questions. It seems technically\nsolid (with quite general assumptions for the noise in particular), being grounded  on proven techniques (which I am not specialist of)\nfor obtaining minimax rates for non-parametric regressions,  which are adapted here to a context where the function is  observed through an average over particles, hence the function estimation is a deconvolution type inverse problem more involved than the usual single index model inference. The result is nicely backed by numerical  experiments. The paper is clearly written, despite the rather lengthy and technically complex  line of arguments.", "weaknesses": "Beside the technical proof, there is maybe a lack of interpretation of this result, which at least at first glance might look very surprising.\nNot much intuition is given, and one wonder then if this quite paradoxical result stems from the assumptions which are taken.", "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": "YAnAePMjmX", "reviewer": "Reviewer_QFiw", "summary": "The paper studies learning interactions in attention-style models where the parameters are unknown. Specifically, they consider the function $Y_i=\\frac{1}{N-1}\\sum_{j\\ne i} \\phi(X_i^\\top AX_j) +\\text{noise}$ from $M$ i.i.d. samples $(X,Y)$ where input $X=(X_1,\\cdots,X_N)$ consists of $N$ possibly dependent $d$-dimensional tokens and output $Y=(Y_1,\\cdots,Y_N)$ measures average interactions. When $A$ is a rank $r$ matrix and $\\phi$ is a $\\beta$-Hölder function, the empirical risk minimizer is shown to have error $M^{-\\frac{2\\beta}{2\\beta+1}}$ when $M\\gtrsim (rd)^{2\\beta+1}$.", "questions": "See Weaknesses.", "limitations": "", "rating": 2, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 1, "strengths": "The paper derives near-optimal minimax rates for estimation of interaction models such as a self-attention layer. This goes beyond existing frameworks for analyzing optimality of regression models as each sample consists of a possibly dependent sequence of tokens.", "weaknesses": "My main concern is novelty and motivation. I do not believe the results are interesting enough to merit publication.\n\n* The problem is not clearly motivated. When do we need to estimate unknown parameters of attention models?\n\n* The main result (i.e. the dimension-free rate) seems straightforward. Since $\\phi$ is a 1-dimensional $\\beta$-Hölder function (not $d$-dimensional), it is intuitive that $d$ does not appear in the exponent, and so the dependency on $d$ only arises through learning $A$ which is $rd$-dimensional due to low rank. So there is no \"curse of dimensionality\" to avoid in the first place, this does not really point to a \"fundamental statistical efficiency\" of attention models as the paper claims. Also for the comment in the abstract on weight matrix and activation not being separately identifiable, this is not really surprising as identifiability of parameters does not affect minimax rates in general.\n\n* The paper claims the main challenge is going beyond the independency assumption, however the sample objects $X^m$ for $m=1,\\cdots,M$ are assumed to be i.i.d. and only the tokens $X_1^m,\\cdots,X_N^m$ can be dependent (with an exchangability assumption which immediately implies coercivity). Since the rate is given only for $M$ and not convergent in $N$, this also does not seem surprising. Other aspects of the proof seem more or less standard in minimax analysis (covering number bound, controlling tails by chaining, lower bound via Fano's inequality).", "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": "f0BB7kZPxm", "reviewer": "Reviewer_o395", "summary": "The paper studies a model of $N$ particles with pairwise interactions which resembles attention networks. In particular, one can consider the problem under study as being given $M$ examples of $N$ tokens each in dimension $d$ and the measures of their interaction strength, defined as an element-wise non-linearity applied to a linear dot-product attention of rank $r$ (plus some noise). Given this data, you wish to recover both the attention matrix and the non-linearity. The authors prove that the error on learning the interaction models decays as a certain dimension-free power of the number of examples $M$ as long as the product $rd$ is smaller than a power of $M/log(M)$. This result is verified in one case on synthetic data.", "questions": "1. Would it be possible to extend your model to include row-wise non-linearities? I believe it would be incredibly interesting, as it would be a data generating model that naturally mimics softmax attention.\n2. Could you provide some practical examples of data that you believe can be effectively described by your particle model?", "limitations": "", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is clear and well written, making the proof easy to follow. Within the modeled under consideration the results are intriguing and sufficiently novel. In particular the authors have very permissive assumptions on the distribution of the examples and the additive noise. I believe the contribution to the theory landscape can be significant, as not many theory papers tackle the problem of dependent token sequences.", "weaknesses": "Although the mathematical analysis is solid, the link to real attention mechanisms is tenuous. The model studied is not an actual dot-product attention layer: it lacks the row-wise softmax normalization that defines attention, and instead applies an element-wise nonlinearity to pairwise scores. As a result, the interacting-particle formulation captures only a simplified kernel-like approximation of attention. I would have liked the authors to better justify why this simplified model is a meaningful generative proxy for attention data, and why its minimax rates are relevant to understanding transformers. A broader empirical study comparing to actual softmax attention or multi-head layers could have clarified the connection and strengthened the practical implications.\n\nMinor typo: in line 154 you refer to $g_*$ in 2.1, which is not there, but a few lines later.", "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": "3iF75ohtpl", "reviewer": "Reviewer_Yn8U", "summary": "This paper studies the statistical problem of learning pairwise interactions in sequences with attention layers. The learning task is a sequence-to-sequence task, which consists in an attention matrix (i.e., a quadratic form in the input tokens) followed by element-wise activation and averaging. The goal is to learn the activation function (among a class of $\\beta$-smooth functions) and the attention matrix (which can incorporate a rank constraint). Authors show that the empirical risk minimizer reaches minimax optimality for this problem, and that the minimax rate depends only on the smoothness of the activation, and not on the dimension of the data and on the sequence length.", "questions": "- line 125: most theoretical works rather assume that the particles are on the sphere rather than on the cube, due to the layer normalization operation in Transformers. Do you think it would be possible to change to the sphere?\n- line 150: the formulation is misleading as it may lead the reader to believe that softmax is included in the setting under study, whereas only element-wise activations are included. How difficult would it be to extend the results to a function $\\phi_\\star: \\mathbb{R}^n \\to \\mathbb{R}$?", "limitations": "", "rating": 10, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "The paper tackles important questions related to characterizing the statistical properties of sequence-to-sequence tasks that are representative of settings where Transformer performs well (which typically differ from usual time series models in statistics). In particular the paper studies pairwise interactions between input tokens, which are known to be a crucial feature of attention models, under reasonable assumptions on the data distribution. Obtaining the minimax rate and showing that it is reached by the ERM is a good contribution. The paper is clear to follow, and the proofs seem correct.", "weaknesses": "I did not see any major weakness. While I give suggestions below to improve the impact of the paper, I do not expect the authors to answer on these points during the rebuttal.\n\nAlthough the paper is well-written, I encourage the authors to revisit their paper to give more interpretation of what is going on. For instance, while the authors state several times that the attention avoids the curse of dimensionality in their model, they do not explain _why_: because the nonparametric estimation problem is a unidimensional problem, while in high-dimension you \"only\" have to estimate a matrix. Similarly, the authors begin in the introduction by stating that the problem is difficult because we only observe an average interaction over the tokens. I imagine this is solved by the exchangeability assumption, which also explains why the sequence length does not appear in the rate, but this could be explained a bit more clearly. I also think it would be very insightful to state the equation on line 859 as an intermediate result in the main text, before deriving the asymptotic rate by assuming $rd$ is small enough and solving for $K_M$.\n\nMinor remarks:\n- line 183: while I appreciate going from independence to exchangeability, I suggest rephrasing this paragraph, because exchangeability is not much more realistic than independence when thinking about NLP.\n- line 238: $R_g[X]$ is not defined yet at this point.\n- line 243: please explain somewhere in the main text how $K_M$ is chosen. Besides, $K_M$ is a natural number so there is a floor function missing in equation (A.20).\n- line 252: state that this estimator is the empirical risk minimizer.\n- line 292: I disagree with the formulation of the last sentence of the remark. It suggests that taking a rougher activation function helps to mitigate the curse of dimensionality, which does not seem to be a correct interpretation. Indeed, in the proof, before replacing $rd$ using the assumption of the theorem in eq. (A.19), one sees that increasing either $d$ or $\\beta$ can only degrade the bound. I would rather say that the contribution of the dimension $d$ to the error comes from the estimation of $A_*$, and that this term does not dominate as long as $rd \\leq (M/\\log M)^{1/2\\beta + 1}$, and that for a fixed $d$ this condition becomes looser as $\\beta$ decreases because the other error terms increase.", "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)