acceptodds
Under review as a conference paper at ICLR 2027

Minimax Sample Complexity of Full and Low-Rank Bilinear Attention Score Estimation

23 views

Abstract

In attention models, the projection dimensions of queries and keys bound the rank of pre-softmax score matrices, yet the statistical benefit of this low-rank structure for attention score estimation remains insufficiently characterized. To this end, we show that exploiting low-rank structure reduces the sample complexity of score estimation from limited token-pair data, and quantify the gap between the full-matrix and rank- classes in a noisy rank-1 observation model. For -dimensional representations, we prove minimax lower bounds for squared Frobenius error with dimension factors and for the full-matrix and rank- classes, respectively, under independent isotropic sub-Gaussian inputs and Gaussian noise. Correspondingly, global least-squares solutions satisfy matching-order high-probability upper bounds, with dimension factors and . As a convex alternative to rank-constrained estimation, nuclear norm penalized least squares attains the same dependence under independent sub-Gaussian noise. Together, the lower and upper bounds establish an order- sample-complexity advantage for rank- estimation at matched accuracy and confidence under Gaussian noise.

Primary area:
learning theory
Keywords:
Bilinear attention, Low-rank matrix estimation, Sample complexity, Minimax bounds, Rank-one measurements

Reviews

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

In this paper, the authors analyze the sample complexity of estimating attention score matrices. The query and key projection dimension constrain the rank of the bilinear interaction matrix. Therefore, instead of estimating the d×dd \times d matrix, it can be more efficient to estimate the rank rr matrix, where r≪dr \ll d.

Critical strengths

The authors have shown a lower bound of Ω(min⁡B2,σ2(2dr−r2)n)\Omega (\min \\{B^2, \frac{\sigma^2(2dr-r^2)}{n}\\} ) and an upper bound O(σ2rdn)O\left(\frac{\sigma^2rd}{n}\right). Therefore, in the appropriate regime, this is minimax-optimal up to constant factor.

Second, the authors have given a comprehensive theoretical analysis. They consider both the convex and non-convex estimators.

In addition, this paper is organized and easy to follow. It gives a very clear explanation of the problem formulation and theoretical results.

Critical weaknesses

My major concern of this paper is its novelty. The observation model yi=x1,i⊤M∗x2,i+ϵi=⟨x1,ix2,i⊤,M∗⟩+ϵiy_i=x_{1,i}^\top M^* x_{2,i} + \epsilon_i = \langle x_{1,i} x_{2,i}^{\top},M^* \rangle + \epsilon_i is a classical matrix sensing or trace regression problem with rank-one measurements. The authors have given a detailed comparison with prior works showing that the curvature argument can be obtained by specializing the existing theoretical result. However, it is not immediately clear about which part of the paper is a fundamentally novel theoretical contribution.

Second, the attention mechanism in the transformer architecture is defined as Softmax(QK⊤/d)V\mathrm{Softmax}(QK^\top / \sqrt{d}) V for Q=XWQQ = X W_Q and K=XWKK = X W_K, whereas in this paper, the authors mainly focus on yi=x1,i⊤M∗x2,i+ϵiy_i=x_{1,i}^{\top}M^*x_{2,i}+\epsilon_i and the main goal is to recover WQWK⊤/dW_Q W_K^\top / \sqrt{d}. This is simplified from the attention definition.

Questions for authors

Please see weaknesses.

2 comments

We thank you for the careful reading and for the direct questions on novelty and model scope.

[W1] What is novel. We agree that Eq. (1) is the classical trace-regression / matrix-sensing model with rank-1 measurements. Appendix D makes this connection explicit and quantitative. The two-term dimension scaling matches Cai & Zhang (2015), and we verify that our inputs satisfy Hamidi & Bayati (2022) Thm. 3.2 by checking their Assumption 3.3 and the required operator-norm bound. We will restate the contribution as a specific finite-sample comparison in the revised paper and made the division of labor explicit in two parts.

  1. What prior work supplies. Thms. 2.3/3.1 of [6] give Cσ2min⁡rd/n+rd2log⁡n/n2,1C\sigma^2\min\\{rd/n+rd^2\log n/n^2,1\\} for residual-constrained nuclear-norm minimization. Thm. 3.2 of [7] gives restricted curvature for general sampling distributions. Appendix D gives γmin⁡=γmax⁡=1\gamma_{\min}=\gamma_{\max}=1 (Assumption 3.2) and, with L4=C4K8L_4=C_4K^8, ctr2=2L4c_{\rm tr}^2=2L_4 (Assumption 3.3), and derives the sphere-net bound E∥Rn∥op≤CK2(d/n+d/n)\mathbb{E}\|R_n\|_{\rm op}\le CK^2(\sqrt{d/n}+d/n), yielding curvature at least 1/81/8 for n≥CK{qd+log⁡(8/η)}n\ge C_K\{qd+\log(8/\eta)\}. Appendix D also shows that the deterministic ERM step is an instance of the Negahban et al. analysis.
  2. What this paper adds. (a) We analyze least-squares estimators instead of residual-constrained ones, namely the global rank-constrained ERM of Eq. (9) and nuclear-penalized LS of Eq. (15), with explicit 1−η1-\eta confidence (tη=log⁡(8/η)t_\eta=\log(8/\eta)) and directional sub-Gaussian inputs that allow dependence among coordinates within each vector (Eq. 2, Appendix B.2). (b) A conditional Bernstein/net bound on Gn=n−1∑iϵix1,ix2,i⊤G_n=n^{-1}\sum_i\epsilon_i x_{1,i}x_{2,i}^\top, which is the argument needed to control the noise term for these objectives. (c) Minimax lower bounds for Frobenius-bounded classes under the joint law of inputs and labels, using KL(PM,PM′)=n2σ2∥M−M′∥F2\mathrm{KL}(P_M,P_{M'})=\frac{n}{2\sigma^2}\|M-M'\|_F^2 and packing inside the radius BB. These hold for every nn, including the saturation regime min⁡B2,⋅\min\\{B^2,\cdot\\}. Cor. 1 gives fixed-confidence probability lower bounds to pair with our high-probability upper bounds. Together (a)–(c) give the order-d/rd/r sample-complexity separation of the two target classes at the same radius, noise, accuracy and confidence (Thm. 5), in the non-saturated regime and when the noise-dependent requirements dominate the curvature sample-size thresholds, built on the curvature and scaling results whose specialization we verify in Appendix D. This is the stated aim of the paper. We will state this comparison in these terms in the revised abstract and the contribution list, and added a labeled comparison table to Appendix D.

[W2] Scope of the attention model. We accept that our model is a simplification. The estimand is the pre-softmax query–key interaction matrix. Sec. 2 states that the fixed attention scaling is absorbed into M∗M^*, Sec. 2.2 identifies A=WQ⊤WKA=W_Q^\top W_K (equivalently WqWk⊤/dhW_qW_k^\top/\sqrt{d_h} under the row-vector convention), and Appendix "Prediction of pretrained BERT attention scores" verifies the label implementation against the model's query and key linear layers on sampled token pairs. Softmax normalization, value aggregation and interactions among heads are not covered and are listed as future work in the Conclusion. To make the model scope explicit, we will add a scope paragraph stating that the bilinear reduction is exact when queries and keys are linear in the inputs and that it does not model the softmax or value path. The statistical bounds also assume isotropic, independent inputs, which is a separate assumption from the bilinear form itself. This keeps the distance from Softmax(QK⊤/d)V\mathrm{Softmax}(QK^\top/\sqrt d)V explicit. We will also relate this target to linear-attention formulations (Katharopoulos, 2020), which use a different kernelized attention computation, whereas we study the original pre-softmax QK⊤/dhQK^\top/\sqrt{d_h} interaction matrix.

Dear reviewer, we've addressed your questions in our responses and would be glad to clarify anything further. We'd appreciate your thoughts if you get a chance to check in before the window closes, looking forward to resolving any remaining concerns together.

Reviewer_LvVsOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This work aims to establish a statistical foundation for the attention mechanism in transformers. Authors simplify the attention model into a bilinear attention score y=x1⊤M∗x2+ϵy = x_1^{\top}M^*x_2 + \epsilon, and establish upper and lower error bounds for approximating M∗M^*. Authors have discussed the cases when M∗M^* is of full-rank or low-rank.

Critical strengths
  1. This work studies how to establish a statistical foundation for attention mechanism. This problem is critical in theoretical machine learning, since attention mechanism is challenging to analyze due to its non-linearity.

  2. Authors provide detailed study on the upper and lower bound of the approximation error ∥∥M^−M∗∥∥F2\|\|\widehat{M} - M^*\|\|_F^2.

  3. The whole paper is clean and readable.

Critical weaknesses
  1. Calling y=x1⊤M∗x2+ϵy = x_1^{\top}M^*x_2 + \epsilon (Eq. (1)) the rank-11 "bilinear attention score" seems like a rebranding. It is known as the 1-dimensional case of bilinear regression Y=XM∗Z+EY = XM^*Z + E (Mai, 2023). (Mai, 2023) has also studied the upper error bound of using an estimator M^\widehat{M} to approximate M∗M^*, including the case where M^\widehat{M} is of low-rank. Authors should compare their work with Mai's work.

  2. The relationship between y=x1⊤M∗x2+ϵy = x_1^{\top}M^*x_2 + \epsilon and attention is unclear.
    Suppose I express attention as Attention(Q,K,V)=softmax(QKTc)V\text{Attention}(Q, K, V) = \text{softmax}(\frac{QK^T}{c})V with Q=XWq,K=XWkQ = XW_q, K = XW_k and V=XWvV = XW_v. XX is the data matrix and Wq,Wk,WvW_q, W_k, W_v are weight matrices.
    Authors intend to establish a statistical foundation to enhance the understanding of attention mechanism in transformer (Line 36). But they do not explain:

  • The relationship between y=x1⊤M∗x2+ϵy = x_1^{\top}M^*x_2 + \epsilon and attention.
  • Why y=x1⊤M∗x2+ϵy = x_1^{\top}M^*x_2 + \epsilon is an appropriate simplification of attention.
    Moreover, existing work typically simplifies attention into a Linear Attention (Katharopoulos, 2020) for analysis purpose. Linear attention kernelizes the softmax layer in attention and expresses it as an inner product, which supports linear operation. Authors should compare y=x1⊤M∗x2+ϵy = x_1^{\top}M^*x_2 + \epsilon with linear attention and explain why y=x1⊤M∗x2+ϵy = x_1^{\top}M^*x_2 + \epsilon should be a better simplified attention model than linear attention.
  1. Authors do not explain the significance of their theoretical results. For example, by Eq. (11), we know that ∥∥M^−M∗∥∥F2\|\|\widehat{M} - M^*\|\|_F^2 admits an upper bound under given assumptions and we know how it is proved. But why is it important to know them? Do these results provide any new insights or improve any earlier results or solve any challenging problems? These questions are not answered in the manuscript.

  2. Experimental work does not relate to theoretical work. In Section 6, authors do not explain how their experimental results match the prediction of their theoretical bounds. I did not see any description like "this experimental result matches the prediction of our xxx bound because xxx".

  3. The theorems and proofs seem completely AI-generated and are hard to follow. In the AI statement, authors vaguely describe that AI is used "to assist in proving mathematical claims", without mentioning how much human effort was truly involved. Authors should provide a more clear statement on how they use AI to assist proof, and attach an example of their conversation with AI as an evidence to support their claim.

References:

The Tien Mai. From bilinear regression to inductive matrix completion: a quasi-bayesian analysis. Entropy, 2023.

Angelos Katharopoulos, et al. Transformers are rnns: Fast autoregressive transformers with linear attention. ICML, 2020.

Questions for authors
  1. What is the definition of M^\widehat{M} in Eqs. (6)(7)(8)? How is it obtained?

  2. What are the relationships between M^,M\widehat{M}, M and M∗M^* in Eqs. (7)(8)(11)?

  3. Why do you make the upper bound Eq. (11) be deterministic while the lower bound Eq. (8) be probabilistic?

  4. In Line 216, why does the rank subadditivity give rank⁡(M^−M∗)≤min⁡2r,d\operatorname{rank}(\widehat{M} - M^*) \le \min\\{2r, d\\}?

6 comments

We thank you for the detailed, point-by-point feedback.

[W1] Relation to Mai (2023). We will add the citation. "Rank-1" modifies the measurement matrix x1x2⊤x_1x_2^\top. Eq. (1) and Mai's model share the bilinear-regression family but differ. Mai uses known designs X,ZX,Z, a matrix response Y=XM∗Z+EY=XM^*Z+E, and PAC-Bayes bounds on the quasi-posterior average of entrywise-clipped predictions ΠC(XMZ)\Pi_C(XMZ), reconstructing M^\widehat M when X⊤XX^\top X, ZZ⊤ZZ^\top are invertible. We use random rank-1 measurements and scalar labels, targeting the parameter error ∥M^−M∗∥F2\|\widehat M-M^*\|_F^2 of global minimizers over Mr(B)\mathcal M_r(B), with minimax lower and matching upper bounds.

[W2] Attention. Sec. 2 estimates the query–key interaction matrix from noisy pre-softmax scores with 1/dh1/\sqrt{d_h} absorbed into M∗M^*. Sec. 2.2 gives A=WQ⊤WKA=W_Q^\top W_K and A=UV⊤A=UV^\top. Appendix "Prediction of pretrained BERT attention scores" gives the exact label yij=(hiWq+bq)⊤(hjWk+bk)/dhy_{ij}=(h_iW_q+b_q)^\top(h_jW_k+b_k)/\sqrt{d_h}. The bilinear reduction is exact when queries and keys are linear functions of the inputs. Independence and isotropy are separate assumptions for our statistical bounds. Softmax normalization, value aggregation and head interactions are out of scope (Conclusion). Linear attention (Katharopoulos, 2020) kernelizes softmax differently. We study the original pre-softmax QK⊤/dhQK^\top/\sqrt{d_h} interaction matrix, so the bounds address estimation error.

[W3] Significance. The contribution list over-emphasized d2/nd^2/n vs rd/nrd/n. We will rewrite it as follows. (a) minimax lower bounds for both classes, with fixed-confidence formulations (Thms. 1–2, Cor. 1), (b) high-probability bounds for every global minimizer over Mr(B)\mathcal M_r(B) with explicit η\eta under isotropic x1,x2x_1,x_2 (Thm. 3), plus a convex nuclear-penalized estimator adapting to rank without knowing rr (Thm. 4, whose sample-size condition still depends on target rank), (c) a matched-accuracy/confidence separation in the non-saturated regime (Thm. 5, Sec. 5). (a)–(c) give that comparison at matched confidence, radius and noise, built on the [6],[7] connections in Appendix D.

[W4] Experiments vs. bounds. We will add a theorem-to-experiment table with columns for theorem, trend, and scope gap. Simulations test the dimension-scaling trends predicted by Thms. 1–2. Thm. 3 covers global minimizers, Thm. 4 prescribes λ\lambda and an exact minimizer, whereas numerics use factorized iterates, validation tuning and finite steps. Sec. 6.1 (error ratio d2/(2dr−r2)d^2/(2dr-r^2)), Sec. 6.2 (ratio 2.22.2–2.72.7 vs the 2.292.29 DoF ratio, nn normalized by 2dr−r22dr-r^2 gives a common trend), and Appendix "Synthetic Experiments" (1.35→8.701.35\to8.70 vs DoF 1.33→8.261.33\to8.26). The correlated-Gaussian design keeps x1,x2x_1,x_2 independent with non-isotropic marginal covariance. Fits on raw inputs check robustness of the input assumptions. The cross-input sweep and residualization probe finite-sample behavior, and STS-B and BERT are real-feature stress tests.

[Q1–Q2] notation. We will extend the Notation appendix. In Thms. 1–2/Cor. 1, M^\widehat M is an arbitrary measurable estimator and MM the truth in the class supremum. In Thm. 3, M^\widehat M is a global minimizer of Eq. (9) and M∗M^* the truth. Thm. 4 uses M^λ\widehat M_\lambda (Eq. 15). The reused symbol and MM/M∗M^* switch are a weakness.

[Q3] Eq. (11) vs Eq. (8). The basic inequality is deterministic conditional on the event (restricted curvature and noise bounds, Eq. 14, App. B.1/D). Eq. (11)'s conclusion is high-probability, with probability ≥1−η\ge1-\eta, every global minimizer satisfies it, with tη=log⁡(8/η)t_\eta=\log(8/\eta). Eq. (8) is Cor. 1's fixed-confidence lower bound, so both compare at matched confidence.

[Q4] rank bound. This follows in two steps. rank⁡(M^−M∗)≤rank⁡(M^)+rank⁡(M∗)≤2r\operatorname{rank}(\widehat M-M^*)\le\operatorname{rank}(\widehat M)+\operatorname{rank}(M^*)\le2r by subadditivity and membership in Mr(B)\mathcal M_r(B), and ≤d\le d for any d×dd\times d matrix.

[W5] AI use and proof provenance. We disclose AI use for clarity and readability, assistance with the mathematical derivations and calculations in the proofs, and retrieval and discovery, including related-work search, per the ICLR 2027 template. We selected the proof strategy (minimax lower bounds via packing/Fano and Le Cam, upper bounds via small-ball curvature) from prior work. AI assistance carried out the specific derivations and calculations, and we verified the complete proofs. We will add a proof roadmap and an expanded Notation appendix to the revised paper. We do not attach raw AI conversation logs during review. Sharing them could breach the double-blind process, and we follow the double-blind disclosure guidance for this stage. All authors take responsibility for the paper.

Thanks for your clarification. I think authors should upload a revised manuscript, and highlight the modified and newly added part in color.

W1: I see the difference now. You take a different statistical assumption from Mai's. You assume x1x_1 and x2x_2 in y=x1⊤M∗x2+ϵy = x_1^{\top}M^*x_2 + \epsilon to be sub-Gaussian, which has unbounded norms. Mai's bound requires XX and ZZ in y=XM∗Z+ϵy = XM^*Z + \epsilon to have bounded norms (see their Theorem 1), otherwise their bound would be infinite.

But I think that your theoretical framework is still established on the bilinear regression. Your contribution, precisely speaking, is to apply this old framework to a new data assumption, rather than inventing an entirely new framework.

W2: This explanation is too vague for me to understand. Can you write down the connection between y=x1⊤M∗x2+ϵy = x_1^{\top}M^*x_2 + \epsilon and Attention(Q,K,V)=softmax⁡(QKTc)V\text{Attention}(Q, K, V) = \operatorname{softmax}(\frac{QK^T}{c})V in mathematical expressions, and demonstrate what this connection mean?

W3: I still do not understand the significance of your work. Let me ask a few explicit questions:

  • What is the problem that drives you to distinguish rdrd and d2d^2? Why is this problem critical and challenging?

  • What are the limitations of existing works in addressing this problem? How does your approach overcome these limitations? And how does your approach differ from existing works?

W4: Please submit your revised manuscript so that I can re-evaluate the experiment part.

W5: Please add the proof roadmap you mentioned to the revised manuscript, so that I can re-evaluate this part.

Q1-Q4: Authors have addressed my concerns on these questions.

We thank you for the close reading and for confirming that Q1–Q4 are addressed. We will upload the revised PDF with all modified and newly added parts highlighted in color. This comment covers W1 and the attention connection in W2. The next two cover significance, the revised PDF, and the proof roadmap.

[W1] Relation to Mai (2023). We agree on the difference in assumptions. Mai's Theorem 1 assumes a bounded signal matrix, ∣XM∗Z∣∞≤C\\|XM^{\ast}Z\\|_\infty\le C, and sub-exponential noise, and it bounds the quasi-posterior mean of the entrywise-clipped prediction ΠC(XMZ)\Pi_C(XMZ). That argument reconstructs a parameter estimator from the prediction estimator, which uses the invertibility of X⊤XX^\top X and ZZ⊤ZZ^\top. Our Sec. 2.1 inputs are independent isotropic sub-Gaussian vectors, and we target the Frobenius parameter error of global minimizers over Mr(B)\mathcal{M}_r(B).

The bilinear signal then has sub-Gaussian tails, and bounded and unbounded sub-Gaussian inputs are both covered, a weaker requirement than a deterministic bound on ∣XM∗Z∣∞\\|XM^{\ast}Z\\|_\infty. We also agree that Eq. (1) is the one-dimensional case of bilinear regression, and we will state this in the scope paragraph of the appendix. We build on that family, on the dimension scaling of Cai and Zhang (2015), and on the curvature result of Hamidi and Bayati (2022), and we will tabulate the division of labor in Appendix D.

For sub-Gaussian inputs the entries of the rank-1 measurement x1x2⊤x_1x_2^\top are generally dependent, and its projections have at most sub-exponential tail bounds. Under this observation regime, our analysis combines the small-ball method for uniform curvature with conditional Bernstein bounds on sphere nets for the noise term (Appendix B). We establish minimax lower bounds with dimension factors d2d^2 and 2dr−r22dr-r^2 for the two classes (Thms. 1–2), their fixed-confidence counterparts (Cor. 1), high-probability upper bounds with explicit η\eta for every global least-squares minimizer (Thm. 3), a convex nuclear-norm estimator that adapts to rank (Thm. 4), and an order-d/rd/r sample-complexity separation (Thm. 5, Sec. 5).

[W2] The connection to attention. Let the rows of X∈RT×dX\in\mathbb{R}^{T\times d} be token representations and write Q=XWqQ=XW_q, K=XWkK=XW_k, with c=dhc=\sqrt{d_h}. The pre-softmax score matrix is S=QK⊤cS=\frac{QK^\top}{c}, which equals XM∗X⊤XM^{\ast}X^\top with cM∗=WqWk⊤cM^{\ast}=W_qW_k^\top. Each score is sij=xi⊤M∗xjs_{ij}=x_i^\top M^{\ast}x_j with x1=xix_1=x_i and x2=xjx_2=x_j, the bilinear form of Eq. (1). M∗M^{\ast} has rank at most dhd_h, the query and key projection width. In Sec. 2.2 we write the same matrix as A=WQ⊤WKA=W_Q^\top W_K with WQ=Wq⊤W_Q=W_q^\top and WK=Wk⊤W_K=W_k^\top as a transpose convention, and A=UV⊤A=UV^\top for U,V∈Rd×rU,V\in\mathbb{R}^{d\times r} gives Mr(B)\mathcal{M}_r(B). The width dhd_h bounds the rank of the score matrix, while rr is a separate quantity indexing the class we compare. In the BERT experiment the fitted ranks 4,8,16,324,8,16,32 vary this constraint, while the head width stays fixed.

Equation (1) adds an observation noise term, yij=sij+ϵijy_{ij}=s_{ij}+\epsilon_{ij}, which is the label model for a sampled query–key pair. The BERT labels are the measured pre-softmax scores. For affine query and key maps on a residual state hih_i, write h~i\tilde h_i for hih_i with a constant coordinate appended, and Wˉq=[Wq⊤bq]\bar W_q=[W_q^\top\\ b_q] and Wˉk=[Wk⊤bk]\bar W_k=[W_k^\top\\ b_k] for the augmented maps. Then qi=Wˉqh~iq_i=\bar W_q\tilde h_i and kj=Wˉkh~jk_j=\bar W_k\tilde h_j, so sijs_{ij} equals h~i⊤Ch~j\tilde h_i^\top C\tilde h_j where cC=Wˉq⊤WˉkcC=\bar W_q^\top\bar W_k, and the query and key biases are absorbed by the augmented input. Here hih_i is a column vector, qi=Wq⊤hi+bqq_i=W_q^\top h_i+b_q and kj=Wk⊤hj+bkk_j=W_k^\top h_j+b_k, so the score yijy_{ij} is qi⊤kjq_i^\top k_j scaled by 1c\frac{1}{c}, the BERT label in the appendix, which agrees with the model's linear layers to float32 rounding. Full attention is O=D−1exp⁡(S)VO=D^{-1}\exp(S)V, with DD normalizing each row of exp⁡(S)\exp(S). The model ends at SS. Row normalization, the value path V=XWvV=XW_v, and interactions among heads act on OO after SS is formed.

In the BERT experiment the labels come from the original residual states, while the fitted covariates are 6464 standardized PCA coordinates with one appended constant coordinate, so the fitted matrix captures the score on the retained directions. Under the independent isotropic design of Sec. 2, E[ZZ⊤]=Id2\mathbb{E}[ZZ^\top]=I_{d^2} makes the excess prediction risk above the noise floor σ2\sigma^2 equal to the squared Frobenius error, so prediction error is the quantity the bounds control. The BERT fits report prediction error on held-out token pairs, normalized by the training-mean error of each head. The score identity fixes the estimation target for linear query and key maps, and these real feature pairs act as an out-of-model stress test at 6464 coordinates. What the theory bounds is the pre-softmax score matrix SS, the matrix that feeds the softmax.

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

In this paper the authors study how rank/width constraints affect the number of samples needed to estimate a matrix formed of bilinear interactions among inputs. In their setting, they observe independent pairs of dd dimensional input vectors and scalar labels of the form y=x1⊤M⋆x2y=x_1^\top M^\star x_2 with noise, and the goal is to estimate the matrix M⋆M^\star. These bilinear forms are typically found in attention models (before the softmax activation), where indeed the product of query and key projection matrices determines the interaction among the tokens and its rank.

The authors compare the performances of estimators over targets that belong to a full matrix class versus another rank rr (at most) class under the same Frobenius norm constraint. They derive minimax lower bounds (finite dimensional) with dimension factors d2d^2 and 2dr−r22dr-r^2, and they also derive high-probability upper bounds for global least squares minimizers. Among their results, they show that least squares regression with nuclear norm regularization/penalty achieves the same order rdrd dependence without requiring the target rank in the penalty choice. Under their sample size conditions, these bounds establish an order d/rd/r difference between the sample requirements of the two target classes.

The authors also provide many synthetic experiments varying dimension and sample size scaling, regularization, and rank. They also provide more realistic experiments using frozen BERT input representations with pretrained attention scores to investigate whether low rank fitting remains useful beyond their theory.

Critical strengths

I personally find the finite sample comparison between full matrix and low-rank estimation useful and scientifically relevant. The lower and upper bounds the authors provide make the dependence on dimension, rank, noise, and the probability of estimation failure explicit under their synthetic model. The analysis provided by the authors handle the actual bilinear measurements due to the outer product x1x2⊤x_1x_2^\top, whose entries are dependent (even when the inputs are independent). I acknowledge that accounting for this structure is important for this problem and goes beyond applying results for matrices with independent measurement entries.

I also appreciate that the authors analyze both least squares with a prescribed rank constraint and a convex estimator using a nuclear norm penalty. The latter shows that one can optimize over all d×dd\times d matrices while obtaining an error bound that depends on the smaller rank of the target, without using that rank to choose the penalty. When it comes to the numerical experiments provided in the manuscript, I finally appreciate that the authors include comparisons where both estimators have the same matrix norm bound and reports cases where imposing a smaller rank does not improve prediction. Indeed this makes the empirical discussion more informative rather than just showing advantages of low-rank fitting.

Critical weaknesses

My main concerns regard the positioning of the contribution relative to previous work and the interpretation of the attention experiments. I find the finite sample guarantees useful, but I think the manuscript should distinguish more clearly what is established in this paper from the existing understanding of low-rank learning.

First, I noticed that the related work discussion misses several analyses of attention, quadratic networks, and overparameterized matrix estimation that I believe are closely connected to this work. In the abstract, the authors state that the statistical benefit of low-rank structure for attention score estimation "remains insufficiently characterized." I think the question of what is missing should be formulated more precisely. Previous works already study recovery of low-rank matrices through overparameterized factorizations [1], the effects of target and architectures widths on recovery and generalization in quadratic networks [2], and Bayesian [3] and empirical risk minimization [4] analyses of attention when varying the key/query ranks. In particular, [4] compares factorized and nonfactorized attention estimation, while [5] connects weight regularization in quadratic networks to matrix estimation with a nuclear norm penalty. These are, in my opinion, substantial connections to the motivation of the present paper. Some of these works provide sharp high-dimensional predictions, whereas the present results give finite dimensional minimax results; others study related recovery problems under different measurement and optimization assumptions. I think the authors should discuss the connections of their work with these lines of related works and explain their relationships and differences.

There is also a close relationship to the classical matrix estimation results already cited by the authors. [6] obtain low-rank recovery rates under noisy rank-one measurements, while [7] provide a curvature result applicable to the present input assumptions. The authors acknowledge these two works and they explain further differences in the least squares objectives, input coordinates, and probability bounds. However I would appreciate a clearer explanation of which part of the final guarantee goes beyond [6] and [7], and what additional argument is needed to establish it. This would make the authors' contribution easier to assess rather than emphasizing mainly the d2/nd^2/n versus rd/nrd/n scaling, which is already familiar from low-rank estimation.

Second, I think the message about attention width needs some qualification. In theorem 5 the authors compare estimating an arbitrary matrix with bounded Frobenius norm against estimating a target assumed to have rank at most rr. The first problem must also handle high-rank targets, so to me this is not a direct comparison of two architectures learning the same low-rank target. In fact, in theorem 4 the authors show that one can fit an unrestricted matrix and still obtain an error bound of order σ2rd/n\sigma^2 rd/n through nuclear norm regularization (fixed confidence and under the sample size conditions they state). This is interesting but it also means that reducing the fitted width is not necessary to obtain the low-rank statistical benefit. I would make this distinction explicit in the motivation for narrower query and key projections.

Regarding the experiments, I find section 6.3 useful as a qualitative case study, but its conclusions depend on the estimator comparison. If I understood correctly the authors fit bilinear predictors to scores from two heads of a frozen BERT model. In figure 3 the low-rank estimator has both a rank constraint and a Frobenius norm bound, whereas ordinary least squares has neither. The improvement can therefore reflect both restrictions, rather than the rank constraint alone. The authors also compare estimators with the same norm bound, and these comparisons favor low-rank fitting in one head and full-matrix fitting in the other. I appreciate that this is reported, but I think it should be more central to the interpretation of Figure 3. Comparisons against ridge (tuned over the regularization) and least squares with nuclear norm penalty on the same task would also help clarify if small rank offers an advantage over regularizing a full matrix.

In the end, despite the weaknesses stated above, I personally lean towards weak acceptance. My positive assessment is based mainly on the theoretical guarantees presented by the authors, and I would appreciate the authors' response to the related work and empirical concerns above. I am happy to maintain or raise the score in case my concerns are addressed.

[1] Li, Y., Ma, T., and Zhang, H. Algorithmic Regularization in Over-parameterized Matrix Sensing and Neural Networks with Quadratic Activations. COLT, 2018.

[2] Martin, S., Biroli, G., and Bach, F. High-Dimensional Analysis of Gradient Flow for Extensive-Width Quadratic Neural Networks. JMLR, 2026.

[3] Boncoraglio, F., Troiani, E., Erba, V., and Zdeborová, L. Bayes optimal learning of attention-indexed models. NeurIPS, 2025.

[4] Boncoraglio, F., Erba, V., Troiani, E., Xu, Y., Krzakala, F., and Zdeborová, L. Single-Head Attention in High Dimensions: A Theory of Generalization, Weights Spectra, and Scaling Laws. ICML, 2026.

[5] Erba, V., Troiani, E., Zdeborová, L., and Krzakala, F. The Nuclear Route: Sharp Asymptotics of ERM in Overparameterized Quadratic Networks. NeurIPS, 2025.

[6] T. T. Cai and A. Zhang. ROP: Matrix recovery via rank-one projections. The Annals of Statistics, 2015.

[7] N. Hamidi and M. Bayati. On low-rank trace regression under general sampling distribution. JMLR, 2022.

Questions for authors

I list my main questions below in a synthetic way. Please refer to the weaknesses section above for the more detailed discussion.

  1. Can the authors discuss the relationship to the attention/quadratic networks/matrix factorization analyses in the references [1,2,3,4,5] in the weakness section? How do the present finite sample minimax guarantees complement those results?
  2. Relative to [6] and [7], what is the main additional guarantee for the least squares estimators considered here, and what additional argument is needed to obtain it?
  3. What conclusion about choosing attention width follows from theorem 5, given that it compares different target classes and theorem 4 allows an unrestricted matrix estimator to exploit a low-rank target through regularization?
  4. It seems to me that the matched norm comparisons favor different estimators in the two tested BERT settings. Can the authors clarify what these results allow them to conclude about the benefit of the rank constraint itself (beyond the norm bound used in figure 3)? As an additional check, comparisons with tuned ridge or least squares with nuclear norm penalty on these same data would possibly be informative.
4 comments

We thank you for the questions on related work and for the discussion of Thm. 5 and attention width.

[Q1] [1]–[5]. We agree the distinctions should be drawn, and will revise Related Work to position our object against all five. They study different targets. [1] factorized-GD implicit regularization under RIP, [2] gradient-flow recovery thresholds in teacher–student quadratic nets (we fix dd, non-asymptotic), [3] Bayes-optimal learning and width effects in attention-indexed models, [4] (closest to our motivation) single-head-attention ERM, query–key spectra and factorized versus direct fitting of the attention matrix, and [5] ℓ2\ell_2-regularized quadratic-network ERM mapped to nuclear-norm matrix sensing. Relative to them, our added result is a finite-nn, η\eta-explicit bound on all global LS minimizers (no optimizer assumed) for noisy rank-1 measurements of a pre-softmax score matrix. The full comparison will appear in Related Work (all five).

[Q2] Beyond [6],[7]. Our main additional guarantee pairs bounded-class minimax lower bounds (Thms. 1–2, Cor. 1) with η\eta-explicit upper bounds for rank-constrained and nuclear-penalized LS, so both sides compare at the same fixed η∈(0,η0)\eta\in(0,\eta_0), BB, σ\sigma. The extra arguments beyond [6],[7] are as follows:

(i) L4=C4K8L_4=C_4K^8 and E∥Rn∥op≤CK2(d/n+d/n)\mathbb{E}\|R_n\|_{\rm op}\le CK^2(\sqrt{d/n}+d/n) for Assumption 3.3 of [7].

(ii) a sphere-net bound on Gn=n−1∑iϵix1,ix2,i⊤G_n=n^{-1}\sum_i\epsilon_i x_{1,i}x_{2,i}^\top.

(iii) the empirical-LS basic inequality (∥Δ∥∗≤kr∥Δ∥F\|\Delta\|_*\le\sqrt{k_r}\|\Delta\|_F or nuclear-norm cone), a Negahban-style step.

The lower bounds use KL(PM,PM′)=n2σ2∥M−M′∥F2\mathrm{KL}(P_M,P_{M'})=\frac{n}{2\sigma^2}\|M-M'\|_F^2 with packing inside BB, giving min⁡(B2,⋅)\min(B^2, \cdot) for every nn. (Appendix D records that CZ and HB already supply the two-term dimension order and the restricted curvature we specialize.)

[Q3] Thm. 5 and attention width. We agree. Thm. 5 compares minimax risk over two different target classes (worst-case target in each), isolating the class-wise sample-complexity gap. Thm. 4 shows an unrestricted nuclear-penalized estimator attains O(σ2rd/n)O(\sigma^2rd/n) at fixed confidence without using rr to set λ\lambda. The penalty is rank-free, though the sufficient sample-size condition still depends on the target rank. Hence reducing fitted width is not necessary for the low-rank benefit via regularization. The d/rd/r gap concerns sample complexity of the two classes.

[Q4] Rank beyond the norm bound. The submitted Figure 3 conflated rank-4 ERM (∥M∥F≤2\|M\|_F\le2) with unconstrained OLS. The published matched-radius results show different outcomes across the two examples (raw median test MSE, Appendix Table "Attention-score prediction audits"(b)). At L0/n=2048n=2048, full-ball has MSE 3.8773.877 versus 0.27050.2705 for rank-4, and rank-4 wins 8/88/8. At L6/n=1024n{=}1024, full-ball has MSE 2.3912.391 versus 3.3323.332 for rank-4, and rank-4 wins 0/80/8. We ran the full grid (layers 0/6, seven nn, eight paired seeds) with full-matrix LS at B=2B=2, tuned Ridge and nuclear-norm LS, with penalties using a separate validation set, keeping the held-out set as the test set. Rank-4 beats matched-radius full-matrix LS 8/88/8 for L0 at n≥1024n\ge1024 and L6 at 4096,81924096,8192 (7/87/8 at 2048) and 0/80/8 elsewhere. Norm control curbs the OLS blow-up. At L0 with n=4096n=4096, OLS has median normalized test MSE 1.35×10121.35\times10^{12} versus 6.906.90 for full-ball. At matched radius the rank-4 / full-ball normalized-MSE ratio is 0.0470.047 at L0/n=4096n{=}4096, 0.3270.327 at n=16384n{=}16384 and 0.820.82 at n=32768n{=}32768, below one for L6 at n=2048,4096,8192n{=}2048,4096,8192 (0.811/0.734/0.8940.811/0.734/0.894), and above one only in 0/80/8 cells. By per-cell median normalized MSE, tuned nuclear-norm LS is no worse than rank-4 in 10/1410/14 cells and tuned Ridge in 6/146/14 cells. At L6 with n=32768n=32768, nuclear and Ridge have medians of 0.1560.156 and 0.1280.128, respectively, versus 0.2140.214 for rank-4. These results show where the rank benefit applies. We will make this central to Figure 3, keep the (b) panel in Appendix Table "Attention-score prediction audits" (cited in §6.3), and restate the conclusion as an estimator-level comparison. Full setup, checks and the 14-row table are in our second comment.

Presentation. We will add an Appendix B proof roadmap (packing →\to small-ball curvature →\to noise-operator bound →\to empirical-LS basic inequality →\to nuclear-norm cone) and extend the existing Notation appendix to disambiguate M^\widehat M and MM / M∗M^*. The sample-size conditions for Thms. 3–4 are stated alongside the theorems.

Supplementary results.

We provide the missing head-to-head comparison among OLS, SVD-4, rank-4, full-ball, Ridge and nuclear norm for layers 0 and 6.

Setup. Frozen pipeline, frozen token pool, identical seeded train/test pairs across layers 0/6, n∈{512,1024,2048,4096,8192,16384,32768}n\in\{512,1024,2048,4096,8192,16384,32768\}, eight paired seeds, test size ndev=min⁡(4096,max⁡(1000,n/4))n_{\rm dev}=\min(4096,\max(1000,n/4)). Penalties tuned on a separate validation set, nval=min⁡(2048,max⁡(512,n/4))n_{\rm val}=\min(2048,\max(512,n/4)). The held-out set stays the test set. We compare full-matrix LS with ∥M∥F≤B=2\|M\|_F\le B=2, Ridge over λ∈{10−6,10−4,10−2,10−1,1,10,100}\lambda\in\{10^{-6},10^{-4},10^{-2},10^{-1},1,10,100\}, nuclear-norm LS over λ∈{10−4,10−3,10−2,10−1}\lambda\in\{10^{-4},10^{-3},10^{-2},10^{-1}\} with 1500 proximal steps, each λ\lambda by validation MSE.

Reproduction checks. Pool invariants (MtrueM_{\rm true}, MdM_d norms, leading spectrum) and per-cell OLS/mean-baseline MSE match the original run that produced the published numbers. SVD-reused Ridge matches the closed-form Ridge to ∼10−14\sim10^{-14}. Both published matched-radius results are reproduced. At L0 with n=2048n=2048, raw median test MSE is 3.8773.877 for full-ball versus 0.27050.2705 for rank-4. At L6 with n=1024n=1024, it is 2.3912.391 for full-ball versus 3.3323.332 for rank-4.

Full results. Median normalized test MSE over eight seeds. <1 beats the training-mean baseline. r4 = rank-4 ERM with B=2B=2, full-ball = full-matrix LS with B=2B=2, ridge / nuc = validation-tuned, and SVD-4 = OLS then rank-4 truncation. All entries normalized, unlike the two raw published values.

LnOLSSVD-4r4full-ballridgenuc
05121.951.887.721.951.831.47
010244.414.223.033.981.530.912
0204821.716.70.6308.711.290.561
040961.35×10121.35\times10^{12}6.48×10116.48\times10^{11}0.3236.900.9690.403
0819213506130.2863.890.7110.335
0163840.8250.5280.2700.8250.5380.370
0327680.3220.3120.2640.3220.3220.288
65120.7760.8411.180.7760.5800.572
6102447.520.60.6620.4930.4630.431
620484871730.3280.4040.3610.298
640961350032900.2390.3250.2830.213
681920.5320.6330.2200.2470.2240.176
6163840.1720.2740.2170.1720.1720.160
6327680.1280.2350.2140.1420.1280.156

Win counts. Rank-4 beats the matched-radius full-matrix fit 8/88/8 for L0 at n≥1024n\ge1024 and L6 at n=4096,8192n=4096,8192 (7/87/8 at n=2048n=2048). It wins 0/80/8 for L0 at n=512n=512 and L6 at n=512,1024,16384,32768n=512,1024,16384,32768.

Interpretation. These results show where the rank benefit applies. Controlling the fitted norm curbs the catastrophic OLS blow-up (L0/n=4096n{=}4096, OLS 1.35×10121.35\times10^{12} vs full-ball 6.906.90). At matched radius the rank gain is large in L0's mid nn range (rank-4 / full-ball =0.047=0.047 at n=4096n{=}4096), substantial at n=16384n{=}16384 (0.3270.327), smaller at n=32768n{=}32768 (0.820.82). It stays positive for L6 at n=2048,4096,8192n{=}2048,4096,8192 (0.811/0.734/0.8940.811/0.734/0.894), reversing only in the 0/80/8 cells. By per-cell median normalized MSE (not paired-seed wins), tuned nuclear-norm LS is no worse than rank-4 in 10/1410/14 cells and tuned Ridge in 6/146/14 cells. At L6 with n=32768n=32768, nuclear and Ridge have medians of 0.1560.156 and 0.1280.128, respectively, versus 0.2140.214 for rank-4. The rank benefit is head- and sample-size dependent. We will restate the conclusion as an estimator-level comparison, noting that under Thm. 4's assumptions a regularized full matrix attains the same low-rank-order rate without narrowing fitted width (our main response, Q3). These validation-tuned, finite-step fits are practical estimator stress tests, and Thm. 4's prescribed λ\lambda and exact minimizer set the theoretical benchmark they are evaluated against.

We will add this table to the revised appendix.

I thank the authors for the detailed response and additional experiments. I consider my doubts addressed by the authors, in particular regarding the comparison with previous work, the clarification about their theorem 5, and the new comparisons with the tuned ridge and nuclear norm baselines. This makes the BERT results more informative on my side.

I still regard the contribution as incremental but I find the finite sample guarantees they provide useful. For this reason I maintain my score, provided that the authors incorporate the changes they promised into the revised manuscript.

Thank you again for your feedback. The revised manuscript with all promised changes is now uploaded.

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

The paper studies the estimation of a matrix from noisy bilinear measurements, motivated by the Q and K of the attention mechanism. The two input vectors are independent, isotropic, and directionally sub-Gaussian. Under Gaussian noise, the paper gives bounded-class minimax lower bounds. It also proves high-probability bounds for global rank-constrained least squares and nuclear-norm penalized least squares. The experiments examine the dimension scaling, while experiments on frozen BERT features and two attention heads explore behavior outside the independent input model.

Critical strengths

(1) The derivation of the bounds are careful and clean. The small-ball proof in Appendix B.2 allows dependence among coordinates within each input vector, and the nuclear-norm analysis handles full-rank estimation errors through the appropriate cone.

(2) It also proposes several controls make the experimental evidence easier to assess, which is a smart design. These include matched-radius full-matrix and low-rank fits, diagnostics of the OLS interpolation spike, and a clear separation between a generated target and a numerical reference fitted to real ratings.

Critical weaknesses

(1) I am not sure the theoretical contribution goes far enough beyond existing results. As Appendix D discusses, Cai and Zhang (2015) already obtain the same two-term dimension scaling, and the curvature theorem of Hamidi and Bayati (2022) covers the input class used here. The least-squares formulation, dependent coordinates, explicit confidence dependence, and bounded-radius comparison are useful additions, but I do not see a substantial improvement in the statistical rate.

(2) he attention experiments do not clearly show that low rank itself gives the claimed sample savings. The eight-fold improvement in Section 6.3 compares rank-4 fitting with a radius constraint against unconstrained OLS. For layer 6, however, OLS already beats the mean baseline at (n=512) in seven of eight runs, while rank-4 first does so at (n=1024). When both methods use the same radius, full-matrix fitting also outperforms rank-4 in all eight layer-6 runs at (n=1024). I appreciate that these results are included, but they suggest that the practical benefit depends on the layer and the comparison setup. The evidence is less clear than in the synthetic low-rank experiments.

Questions for authors

Could the main attention figure include full-matrix least squares at the same radius, along with a tuned nuclear-norm baseline, over the whole sample-size grid? The two isolated matched-radius comparisons have opposite outcomes, so this would help establish where the gain comes from rank restriction and where it comes from controlling the fitted norm.

3 comments

We thank you for the questions on the Cai & Zhang and Hamidi & Bayati comparison and for prompting the full-grid baselines.

[W1] Relation to Cai and Zhang (2015) and Hamidi and Bayati (2022). Appendix D matches Cai and Zhang's dimension scaling and specializes Hamidi and Bayati's Thm. 3.2 to our input model. The four differences are as follows.

  1. Objective. Cai and Zhang's Thms. 2.3/3.1 analyze nuclear-norm minimization under both an ℓ1\ell_1 constraint on the residual and an operator-norm constraint on the adjoint applied to the residual (failure at most 11/n+3e−c2d11/n+3e^{-c_2d} and 2/n+5e−c3d2/n+5e^{-c_3d}, respectively). We analyze least squares, specifically global rank-constrained ERM (Eq. 9) and nuclear-penalized LS (Eq. 15), at explicit 1−η1-\eta (tη=log⁡(8/η)t_\eta=\log(8/\eta)).

  2. Inputs. Eq. (2) is directional sub-Gaussian, allowing dependent coordinates (Appendix B.2, E⟨A,D⟩4≤CK8∥D∥F4\mathbb{E}\langle A,D\rangle^4\le CK^8\|D\|_F^4). Cai and Zhang's Thm. 3.1 assumes independent coordinates (symmetric, variance-one sub-Gaussian entries).

  3. Additional step. For Hamidi and Bayati's Thm. 3.2, Appendix D gives γmin⁡=γmax⁡=1\gamma_{\min}=\gamma_{\max}=1 (Assumption 3.2) and, with L4=C4K8L_4=C_4K^8, ctr2=2L4c_{\rm tr}^2=2L_4 (Assumption 3.3), and derives the sphere-net bound E∥Rn∥op≤CK2(d/n+d/n)\mathbb{E}\|R_n\|_{\rm op}\le CK^2(\sqrt{d/n}+d/n).

    Our empirical-LS bound then combines the Appendix D curvature event (HB Thm. 3.2) with a conditional Bernstein/net control of Gn=n−1∑iϵix1,ix2,i⊤G_n=n^{-1}\sum_i\epsilon_i x_{1,i}x_{2,i}^\top and the empirical-LS basic inequality, a Negahban-style step.

  4. Lower bounds. Thms. 1–2 bound Frobenius-bounded classes under the joint law via KL(PM,PM′)=n2σ2∥M−M′∥F2\mathrm{KL}(P_M,P_{M'})=\frac{n}{2\sigma^2}\|M-M'\|_F^2, for every nn including saturation min⁡(B2,⋅)\min(B^2, \cdot). Cor. 1 gives fixed-confidence lower bounds, so both sides compare at the same η∈(0,η0)\eta\in(0,\eta_0), BB, σ\sigma.

Contribution. We compare two target classes under one model at matched confidence, radius, and noise, building on Appendix D's verified curvature and scaling results. We will state this in the revised abstract, contribution list, and labeled Appendix D table.

[W2] Attention experiments. In layer 6, OLS beats the training-mean baseline in 7/87/8 runs at n=512n=512 while rank-4 ERM first reaches 8/88/8 at n=1024n=1024 (Appendix Table "Attention-score prediction audits"(a)). At n=1024n=1024 the matched-radius full-ball fit wins 8/88/8 (raw median test MSE was 2.3912.391 for full-ball and 3.3323.332 for rank-4, as shown in panel (b)). The submitted eight-fold statement compares rank-4 ERM with ∥M∥F≤2\|M\|_F\le2 to unconstrained OLS, conflating rank restriction with norm control. The full-grid results below disambiguate where the gain comes from rank restriction versus fitted-norm control.

[Q1] Full-grid baselines. We ran the requested grid (layers 0/6, all seven nn from 512 to 32768, eight paired seeds) with full-matrix LS at B=2B=2, validation-tuned Ridge (7 λ\lambda) and nuclear-norm LS (4 λ\lambda, 1500 steps), penalties tuned on a separate validation set, keeping the held-out set as the test set. The complete setup, reproduction checks, and the 14-row table are in our second comment. The same table will also appear in the revised paper's appendix. We will add Figure 3 panels covering the full grid with these baselines alongside rank-4 ERM. The matched-radius audit panel (b) stays in Appendix Table "Attention-score prediction audits", cited in §6.3. Key values below give median normalized test MSE over eight seeds. Values below 1 beat the training-mean baseline, and both r4 and full-ball use a Frobenius radius B=2B=2.

Lnr4full-ballridgenuc
05127.721.951.831.47
020480.6308.711.290.561
0327680.2640.3220.3220.288
65121.180.7760.5800.572
620480.3280.4040.3610.298
6327680.2140.1420.1280.156

Rank-4 beats matched-radius full-matrix LS 8/88/8 for L0 at n≥1024n\ge1024 and L6 at 4096,81924096,8192 (7/87/8 at 2048), and 0/80/8 elsewhere. These results qualify our claim. Norm control curbs the OLS blow-up. At L0 with n=4096n=4096, OLS has median normalized test MSE 1.35×10121.35\times10^{12} versus 6.906.90 for full-ball. At matched radius the rank-4 / full-ball normalized-MSE ratio is 0.0470.047 at L0/n=4096n{=}4096, still low at n=16384n{=}16384 (0.3270.327), closer to one at n=32768n{=}32768 (0.820.82), and below one for L6 at n=2048,4096,8192n{=}2048,4096,8192 (0.811/0.734/0.8940.811/0.734/0.894), reversing only in the 0/80/8 cells. By per-cell median normalized MSE (not paired wins), tuned nuclear-norm LS is no worse than rank-4 in 10/1410/14 cells and tuned Ridge in 6/146/14. We will restate the eight-fold gap in §6.3 as an estimator-level comparison, noting that under Thm. 4 a regularized full matrix can attain the same low-rank-order rate.

Ethics flag. We will expand the AI-use disclosure in the revised paper per the ICLR 2027 template.

Supplementary results.

We provide the missing head-to-head comparison among OLS, SVD-4, rank-4, full-ball, Ridge and nuclear norm for layers 0 and 6.

Setup. We reused the frozen pipeline and its frozen token pool, with identical seeded train/test pairs across layers 0 and 6, n∈{512,1024,2048,4096,8192,16384,32768}n\in\{512,1024,2048,4096,8192,16384,32768\}, eight paired seeds, test size ndev=min⁡(4096,max⁡(1000,n/4))n_{\rm dev}=\min(4096,\max(1000,n/4)) drawn from the held-out sentences. Penalties were tuned on a separate validation set drawn from the training sentences, nval=min⁡(2048,max⁡(512,n/4))n_{\rm val}=\min(2048,\max(512,n/4)), keeping the original held-out set as the test set. We compare full-matrix LS with ∥M∥F≤B=2\|M\|_F\le B=2, Ridge over λ∈{10−6,10−4,10−2,10−1,1,10,100}\lambda\in\{10^{-6},10^{-4},10^{-2},10^{-1},1,10,100\}, and nuclear-norm LS over λ∈{10−4,10−3,10−2,10−1}\lambda\in\{10^{-4},10^{-3},10^{-2},10^{-1}\} with 1500 proximal steps. Each λ\lambda is selected by validation MSE.

Reproduction checks. Pool invariants (MtrueM_{\rm true}, MdM_d norms and leading spectrum), per-cell OLS test MSE, and mean-baseline test MSE match the original run that produced the published numbers. SVD-reused Ridge agrees with the closed-form Ridge in the paper to ∼10−14\sim10^{-14}. The two published matched-radius results are reproduced. At L0 with n=2048n=2048, raw median test MSE is 3.8773.877 for full-ball versus 0.27050.2705 for rank-4. At L6 with n=1024n=1024, it is 2.3912.391 for full-ball versus 3.3323.332 for rank-4.

Full results. Median normalized test MSE over eight seeds. Values below 1 beat the training-mean baseline. r4 = rank-4 ERM with B=2B=2, full-ball = full-matrix LS with B=2B=2, ridge / nuc = validation-tuned, and SVD-4 = OLS followed by rank-4 truncation. All entries below are normalized, unlike the two raw reproduction values above.

LnOLSSVD-4r4full-ballridgenuc
05121.951.887.721.951.831.47
010244.414.223.033.981.530.912
0204821.716.70.6308.711.290.561
040961.35×10121.35\times10^{12}6.48×10116.48\times10^{11}0.3236.900.9690.403
0819213506130.2863.890.7110.335
0163840.8250.5280.2700.8250.5380.370
0327680.3220.3120.2640.3220.3220.288
65120.7760.8411.180.7760.5800.572
6102447.520.60.6620.4930.4630.431
620484871730.3280.4040.3610.298
640961350032900.2390.3250.2830.213
681920.5320.6330.2200.2470.2240.176
6163840.1720.2740.2170.1720.1720.160
6327680.1280.2350.2140.1420.1280.156

Win counts. Against the matched-radius full-matrix fit, rank-4 wins 8/88/8 runs for L0 at n≥1024n\ge1024 and for L6 at n=4096,8192n=4096,8192 (7/87/8 at n=2048n=2048). It wins 0/80/8 for L0 at n=512n=512 and for L6 at n=512,1024,16384,32768n=512,1024,16384,32768.

Interpretation. These results show where the rank benefit applies. Controlling the fitted norm curbs the catastrophic OLS blow-up (L0/n=4096n{=}4096, 1.35×10121.35\times10^{12} for OLS vs 6.906.90 for full-ball). At matched radius, the further gain from the rank constraint is large in L0's intermediate nn range (rank-4 / full-ball =0.047=0.047 at n=4096n{=}4096), remains substantial at L0/n=16384n{=}16384 (ratio 0.3270.327) and positive but smaller at L0/n=32768n{=}32768 (0.820.82). It also stays positive for L6 at n=2048,4096,8192n{=}2048,4096,8192 (ratios 0.811/0.734/0.8940.811/0.734/0.894), and reverses only in the 0/80/8 cells. By median normalized test MSE per cell (not paired-seed win counts), tuned nuclear-norm LS is no worse than rank-4 in 10/1410/14 cells and tuned Ridge in 6/146/14 (L6/n=32768n{=}32768, 0.1280.128 / 0.1560.156 vs 0.2140.214). The rank benefit is head- and sample-size dependent. We will restate the eight-fold gap in §6.3 as an estimator-level comparison, noting that under Thm. 4's assumptions a regularized full matrix can attain the same low-rank-order rate. These validation-tuned, finite-step fits are practical estimator stress tests, and Thm. 4's prescribed λ\lambda and exact minimizer set the theoretical benchmark they are evaluated against.

We will add the 14-row full-grid table to the appendix of the revised paper, and narrow the §6.3 conclusion accordingly.

Thank you for your rebuttals and they address my concerns. I decide to raise my rating as positive.

Comments on the paper

1 comment

We have uploaded a revised version of the manuscript that incorporates the changes described in our rebuttal. Revisions are highlighted in blue for ease of reference. The main updates include:

  • clarifying the scope, assumptions, and contributions of the minimax comparison
  • adding related-work discussion and citations
  • expanding technical details and notation in the appendix
  • updating the experiments and numerical diagnostics

We hope these changes address the points raised in the discussion. We welcome any further comments.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.