acceptodds
Under review as a conference paper at ICLR 2027

One Attention Head Makes Where to Look Almost Free: The Cost of Unknown Support with and without Adaptive Selection

Abstract

A transformer must decide where to look before it decides what to compute. We measure the statistical price of that decision in nonparametric regression. The target depends on an unknown set of of its input coordinates, one token each, through a smooth function of variables, namely an anisotropic Besov ball with a sup-norm envelope; the design is i.i.d. with a density bounded above and below uniformly in and , the noise is Gaussian, and is fixed. Without adaptive selection the price is combinatorial. Every estimator that is affine in the training responses, with offset and coefficients fixed before the responses are read, as in kernel ridge regression at a label-independent regularisation level, random-feature ridge, or lazy/NTK rules, has worst-case risk at least with , which does not vanish once ; for integrability index the exponent is the smaller, shifted one. One positional attention head makes the price additive and polylogarithmic in . The exact clipped least-squares minimiser over an explicitly budgeted class of one-head transformers with positional keys attains in the effective smoothness , up to logarithmic factors in and with a constant free of , plus a single additive selection term polylogarithmic in . The mechanism is a whitening of the positional codes: for every support, the head can attend equally to the relevant tokens, with only a controlled remainder elsewhere, inside one parameter budget that does not depend on which tokens they are. At with all structural parameters fixed, the response-affine worst-case risk stays bounded away from zero while the attention bound vanishes. The saving is not specific to attention, since a direct search over supports attains the same leading bound; what attention supplies is a compact, continuous realisation of it. The upper bound concerns the exact minimiser, and no optimisation guarantee is claimed.

Primary area:
learning theory
Keywords:
transformers, anisotropic Besov spaces, mixed smoothness, variable selection, minimax theory

Reviews

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

The paper studies nonparametric regression where the target depends on an unknown subset of k among D input coordinates, and asks what one positional attention head “buys” for learning where to look.

It proves two main results on the same target class. Its upper bound shows that attention estimator pays the usual low-dimensional rate plus only a slow additive selection cost, avoiding a combinatorial penalty in the ambient dimension, while its lower bound shows every response-affine rule must pay a multiplicative support-uncertainty penalty that saturates once the number of candidate supports is large.

This identifies a separation whenever the upper guarantee beats the lower guarantee, but the paper admits the separation is not specific to attention, rather a direct support search with feed-forward networks attains the same leading rate. Hence attention is one continuous realization of adaptive selection, not a unique advantage. Also no optimization related results were shown here.

Critical strengths
  • A new lower bound which extends previous results for all estimators whose weights are fixed before seeing the responses. It cleanly isolates the extra cost of not knowing which small set of inputs matters, and the hard cases stay inside the paper’s stated target class.

  • The attention-based construction is carefully controlled: it can represent every possible relevant set within one bounded model, and the statistical accounting connects this expressiveness to approximation and complexity without giving the estimator the true set.

Critical weaknesses
  • The result is not really specific to attention. The paper itself shows that a direct search over relevant input sets achieves the same leading rate, and the attention construction selects globally relevant coordinates rather than changing relevance per example. So the conceptual novelty for attention is limited, as somewhat implied from the heading.

  • The upper bound has limited practicality. It applies to an exact global minimizer with symbolic constants, not to an efficient training procedure, and it gives no usable numerical threshold for when the separation appears. The training experiment uses a different, reduced model and gives mixed results.

Questions for authors
  1. Does the lower bound sharply capture the cost of unknown support in your settings? Any proof of optimality?

  2. Can the upper bound use the selector’s effective parameters? This could substantially improve the dimension dependence.

  3. I'm willing to raise my score if the authors could further improve the scope and relevance of this work.

1 comment

Thank you for your constructive review and for highlighting the sharpness and effective-complexity questions. In response, we established two new results, Theorems 5.5 and 5.4, which strengthen the paper from an affine lower bound to a sharp characterization of response-affine limits and a near-minimax guarantee for one-head exact ERM.

Question 1 — Sharpness.

Does the lower bound sharply capture the cost of unknown support in your settings? Any proof of optimality?

Response. Yes, under uniform design. Theorem 5.5 (Appendix F.5, Theorem F.10) proves, for fixed structural parameters,

\asymp\min\{1,(M/n)^\gamma\},\quad M=\binom Dk,\quad r=\bar s-(1/p-1/2)_+,\quad\gamma=\frac{2r}{2r+1}.$$ A response-linear series estimator on a fixed spline space spanning all supports has squared bias at most $CQ^{-2r}$ and variance at most $C'MQ/n$. Balancing them gives the rate; for $n\le M$ the zero rule suffices. Thus the support factor and shifted $p<2$ exponent are sharp within the full response-affine class under uniform design, not artifacts of the lower-bound proof. **Question 2 — Effective parameters.** > Can the upper bound use the selector’s effective parameters? **Response.** Yes, for the original class and estimator. Theorem 5.4 (Appendix E.7, Theorem E.20) covers the actual image $(K^\top q,RV)$ of the original parameter box, with centres in that image. The covering exponent falls from $2m^2+(k+1)m$ to $(k+1)m$, without enlarging the class or changing the approximation witness. At $D=n$, the selector remainder improves from $O(\log^4n/n)$ to $O(\log^3n/n)$ for fixed structural parameters. This improves function-class complexity; the full model retains its original trainable parameter count. **Weakness 1 / Question 3 — Architectural contribution and relevance.** > The result is not really specific to attention. **Response.** The strengthened result places the head against the unrestricted statistical benchmark. Theorem G.2 lower-bounds all-estimator minimax risk by $c\min\{1,n^{-\alpha}+\log M/n\}$, where $\alpha=2\bar s/(2\bar s+1)$; support search matches it up to logarithms. Theorem 5.4 and output clipping put our bounded one-head exact ERM within $C\log^{\max\{3\alpha,2\}}(2n)$ of all-estimator minimax risk, uniformly for $n\ge2,D\ge2k$, with fixed $k$, other structural parameters and design-density bounds (Appendix G.1). The contribution is a single continuous, bounded model containing suitable selectors for every support, without giving the estimator that support. Support search is another realisation, not a contradiction to this architectural guarantee. The abstract and Introduction explicitly describe global positional selection rather than per-example relevance. **Weakness 2 — Practicality.** > The upper bound has limited practicality. **Response.** Appendix K.6/Table 8 adds concrete training successes. On pure interaction at $D=1024,n=16384$, twelve restarts and held-out selection yield mean risk **0.262 versus 0.969**, a paired difference **−0.707 [−0.880,−0.509]**, against the prior-optimal affine rule. Fixed-step training with marginal signals reaches **0.255 versus 0.957** at $D=16384,n=1024$. These follow-ups use different conditions from the adverse fixed-budget primary retained in Table 6; K.6 reports budgets, failures and screening controls. Corollary E.21 also covers the bounded $K=V=I$ subclass, while practical fits do not enforce all theorem-class bounds. Constants remain symbolic, without a numerical crossover threshold. Corollary G.5 exposes the optimisation residual; it is not an algorithmic convergence result. We hope these direct answers to sharpness and effective complexity, together with the near-minimax comparison and training evidence, support reassessment of the contribution.
Reviewer_TYyfOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

This paper studies the statistical cost of learning a target function on $ [0,1]^D $ which takes the form $ f(x)=g(x_S)$ where S is an unknown set of $ k$ coordinates and ff is smooth enough. Using a database of n iid points $x_i $ and the labels $y_i=f(x_i)+ \xi_i $ where $\xi $ is Gaussian noise, the authors study first the case of estimators which are affine in the labels, and show that the mean square error of such estimators is bounded away from 0 when (Dk)D\choose{k} $ >n$. Then the paper studies the case of a specific attention head, where the queries and key weights depend only on coordinate positions not on the current value of the input x. The entire head is thus a linear map of x, which aims at identifying the subset S of relevant coordinates for the target function f, it is followed by a deep ReLU network. For this class of function, the paper establishes an upper bound for the exact global least square minimizer, showing that if D grows like n the error goes to zero at large n, contrary to what happened in the affine estimator.The paper also studies how attention head selects the relevant coordinates. These theoretical estimates are complemented by some illustrative experiments.

Critical strengths
  • The formulation of a clear question, learning the coordinates which matter.
  • The combination of the lower bound for estimators which are affine in the labels, and an upper bound for the estimator which includes first an attention head focusing on position.
  • The analysis of what the attention head can do.
Critical weaknesses
  • The advantage is not specific to attention. Exhaustive support selection followed by feed-forward networks attains roughly the same performance. The authors acknowledge this fact in section 6. Therefore, the paper establishes an advantage of decomposing the problem and first learning the positions. The specific attention mechanism is one possible tool for support selection, but its computational advantage is not established.
  • The lower bound is restricted to estimators which are affine in the responses, with label-independent coefficients. It does not cover more general nonlinear adaptation. Even clipping an affine estimator falls outside of the hypotheses of the theorem. Therefore the paper cannot be understood as giving a general statement on the separation between attention-helped methods and conventional regression methods.
  • The attention mechanism is highly specialized, with queries and keys depending only on positions. Therefore the paper does not provide real insight on more general attention.
  • There is no study of the computational tractability of the risk minimization used in the upper bound.
Questions for authors
  • The paper is hard to read. While the first paragraph clearly states the main questions, already in the second paragraph the main message is mixed with technicalities about the Besov norm. There should be a clearer summary of the main results at the beginning of the paper without entering in the technical details, The section on numerical simulations is cryptic.
1 comment

Thank you for recognising the question of learning which coordinates matter. We sharpen its statistical answer and address each concern below.

Weakness 1 — Why attention when support search also works?

The advantage is not specific to attention.

Response. Support search supplies an unrestricted statistical benchmark. Our construction contains a selector for every support inside one continuous model with a common parameter budget, without giving the estimator the support. Theorem 5.4 now sharpens this class's effective complexity. Combined with the all-estimator lower bound, it gives near-minimax exact ERM for this bounded class: a polylogarithmic factor in nn, uniform in DD for fixed structural parameters (Appendix G.1). This establishes an explicit statistical realisation, not cheaper optimisation than enumeration.

Weakness 2 — The response-affine restriction.

Even clipping an affine estimator falls outside of the hypotheses of the theorem.

Response. The multiplicative lower bound concerns f^(x)=a(X,x)+∑i=1nwi(X,x)Yi,\hat f(x)=a(X,x)+\sum_{i=1}^n w_i(X,x)Y_i, where the offset and weights are independent of the training responses. Fixed-kernel and fixed-feature ridge with response-independent tuning are included; clipping, response-dependent tuning and validation selection are not automatically covered.

New Theorem 5.5 matches the lower bound under uniform design. It therefore characterises the sharp limit of the whole response-affine class, rather than a weak chosen baseline. Separately, Theorem G.2 lower-bounds all-estimator minimax risk by cmin⁡{1,n−α+log⁡M/n}c\min\{1,n^{-\alpha}+\log M/n\}, where M=(Dk)M=\binom Dk and α=2sˉ/(2sˉ+1)\alpha=2\bar s/(2\bar s+1). This common benchmark includes attention and clipped or tuned methods; it does not extend the affine penalty to all regression algorithms.

Weakness 3 — Positional rather than content-dependent attention.

The attention mechanism is highly specialized, with queries and keys depending only on positions.

Response. The unknown support is shared across examples, so the model uses global positional selection. At fixed fitted parameters the selector is linear in the input and followed by a nonlinear readout, exactly as your summary describes. The abstract and Sections 1 and 2 state this scope. It isolates a well-defined cost of learning where to look, without claiming a result about per-example content routing.

Weakness 4 — Computational tractability.

There is no study of the computational tractability of the risk minimization used in the upper bound.

Response. The theory is for exact ERM; Corollary G.5 states the additional empirical optimisation residual for approximate fitting. We now complement it with actual training evidence. On pure interaction at D=1024,n=16384D=1024,n=16384, twelve restarts and held-out selection yield a single head with mean risk 0.262 versus 0.969 for the prior-optimal affine rule, with paired difference −0.707 [−0.880,−0.509]. A fixed-step study with marginal signals extends to D=16384D=16384. Appendix K.6 reports these follow-up procedures, their budgets, unsuccessful fits and stronger screening controls. This establishes average-success regimes for specified training procedures, not a general optimisation guarantee.

Question 1 — Clearer opening and numerical section.

The paper is hard to read. The section on numerical simulations is cryptic.

Response. The abstract and Introduction now begin with the unknown-coordinate problem, explain why response-adaptation matters, introduce positional selection and then give the statistical guarantees. Terms are explained before use. Section 5.7 separates three questions: finite-prior support uncertainty, known-support construction diagnostics and actual training performance. Each experiment now has a distinct role.

The result is a sharper statistical characterisation, an explicit near-minimax exact-ERM realisation, and concrete evidence of trainability in stated regimes.

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

The paper studies nonparametric regression where the target depends on an unknown set of kk out of DD input coordinates (tokens) through a smooth function in an anisotropic Besov ball. It compares two kinds of learners. For response-affine estimators, whose weights are fixed before the labels are seen (kernel ridge at a fixed regularisation, random-feature ridge, NTK rules), it proves a worst-case lower bound cmin⁡{1,(M/n)β}c \min\{1, (M/n)^\beta\} with M=(Dk)M = \binom{D}{k}, which stays constant once M≥nM \ge n. For the exact least-squares minimiser over a class of one-head transformers with fixed positional codes followed by a ReLU network, it proves an upper bound n−αn^{-\alpha} (up to logarithms) plus an additive selection term polylogarithmic in DD. The upper bound rests on a whitened query that makes the head attend equally to the kk relevant tokens, inside one parameter budget valid for every support.

Critical strengths

The paper shows a statistical separation between response-affine estimators (kernel ridge, random features, NTK) and a one-head attention estimator on kk-sparse function classes, with an explicit support factor min⁡{1,(M/n)β}\min\{1, (M/n)^\beta\}. The paper is well written and lower bound is interesting.

Critical weaknesses
  1. The separation is not specific to attention. Exact least squares over the union of feed-forward networks on all supports attains the same leading bound (Section 6, Appendix G), so the result is a separation between response-affine and label-adaptive nonlinear estimators, and the title and framing overstate the role of attention.

  2. The upper bound mainly reduces to approximation. Theorem 5.1 combines a standard oracle inequality, known Besov approximation and a covering count; the attention-specific part is the whitening witness of Lemma E.9.

  3. The guarantee concerns the exact non-convex least-squares minimiser, with no optimisation result, and the claimed regime is never tested empirically. The only experiment that trains attention (Appendix J) uses a single dimension D=32D = 32 (M=496M = 496), so the central claim, that one head pays about log⁡2D\log^2 D while response-affine rules pay the factor MM, in particular for M≥nM \ge n and large DD, is not checked for a trained model.

Questions for authors
  1. Could you test the claimed regime empirically, by training the attention head for increasing DD (including M≥nM \ge n) and comparing it with a response-affine baseline such as kernel or random-feature ridge? Does the risk of the trained head grow only polylogarithmically in DD, while that of the affine baseline saturates?

  2. The construction of Lemma E.9 uses K=V=IK = V = I, yet KK and VV are trainable m×mm \times m matrices that dominate the selector count Psel=2m2+km+mP_{\mathrm{sel}} = 2m^2 + km + m. Fixing them would reduce PselP_{\mathrm{sel}} to O(k3log⁡D)O(k^3 \log D) and improve the selection term. Why are they included, and does the bound improve without them?

3 comments

Thank you for recognising the statistical separation. We answer your two questions directly and then address the two concerns about the contribution.

Question 1 / Weakness 3 — High-dimensional training.

Does the risk of the trained head grow only polylogarithmically in DD, while that of the affine baseline saturates?

Response. We now exhibit high-dimensional training successes and separately report the fixed-sample scan you requested. In Table 8(a), a single head selected using twelve restarts and a held-out quarter of the labels has mean normalised risks 0.116, 0.140, 0.262 at D=256,512,1024D=256,512,1024 along n=16Dn=16D, versus 0.887, 0.942, 0.969 for the prior-optimal response-affine rule. At D=1024D=1024, the paired difference is −0.707 [−0.880,−0.509] (95% dataset-bootstrap interval). The selected state uses neither test-loss selection nor rounding, refitting or ensembling.

Table 8(b) holds n=1024n=1024 and the 600-step recipe fixed on a target with marginal signals. At D=1024,4096,16384D=1024,4096,16384, head risks are 0.106,0.157,0.255, versus 0.503,0.843,0.957; each cell favours the head on all twenty datasets.

For the requested fixed-nn pure-interaction scan, however, the 600-step head instead loses to both baselines at the larger dimensions. At n=512n=512, its risk rises from 0.179 to 2.938 as DD increases from 16 to 512 (Table 6/Figure 6). At the prespecified D=256D=256 primary, risks are 2.058 (head), 0.982 (prior-affine) and 1.059 (random-feature ridge); the head-minus-affine difference is +1.076 [0.974,1.171], adverse on 20/20 datasets.

The successes above are follow-ups designed after those outcomes, with fresh seeds and protocols fixed before their formal runs. The twelve-restart procedure uses up to 12×960012\times9600 updates per dataset. Its largest cell favours the head on 16/20 datasets; four selected heads are worse than zero. With one initialisation and the same held-out rule, mean risk is 0.807 and the interval for its difference from affine includes zero. Pairwise screening does better on every dataset. K.6 reports the full comparisons. These results identify concrete average-success regimes, not a trained-model polylogarithmic scaling law or a general optimisation guarantee.

Question 2 — Fixing keys and values.

Why are they included, and does the bound improve without them?

Response. The original class retained trainable query, key and value maps, counted entry by entry; the witness itself needs only K=V=IK=V=I. Corollary E.21 gives exact ERM over that bounded fixed-K,VK,V subclass, with (k+1)m=O(k3log⁡D)(k+1)m=O(k^3\log D) trainable selector scalars. More strongly, Theorem 5.4/E.20 covers the original box's image (K⊤q,RV)(K^\top q,RV) and gives the same exponent (k+1)m(k+1)m for the full class without changing its estimator. At D=nD=n and fixed structural parameters, the selector remainder improves from O(log⁡4n/n)O(\log^4n/n) to O(log⁡3n/n)O(\log^3n/n). The full model's trainable count and fixed codebook are unchanged.

Weaknesses 1 and 2 — Framing and the upper-bound contribution.

The separation is not specific to attention. The upper bound mainly reduces to approximation.

Response. The title is now "The Statistical Cost of Unknown Support: Response-Affine Limits and One-Head Attention". The oracle inequality and Besov approximation are established ingredients. The architecture-specific result is a common bounded class containing a balanced selector for every support, combined with effective complexity accounting. Support search remains another adaptive solution.

Theorem 5.5 now makes the affine rate sharp under uniform design. With the all-estimator benchmark, Theorem 5.4 yields a one-head exact-ERM risk within a polylogarithmic factor in nn of minimax, uniformly in DD for fixed structural parameters (Appendix G.1). These additions strengthen the statistical result beyond the original separation.

Thank you for the response and the revision. The new framing and results address my theoretical concerns, and I appreciate the clear answer on K and V. I maintain my score.

Thank you for reading the revision. We’re glad the new results addressed your theoretical concerns, and we appreciate your support.

Reviewer_wqSYOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
3
Read review
Paper summary

The paper claims to study something about the price of knowing which tokens one should attend to. This is a somewhat unusual problem that is worth motivating, though it was not motivated in the paper. Unfortunately I cannot say much more about the paper's contributions, as I found it virtually incomprehensible.

The issues appear as early as the abstract. Line 17: What is the meaning of "Without adaptive selection the price is combinatorial." Line 22: What is the "integrability index"? What do you mean by "the exponent \beta is the smaller, shifted one"? Line 27: "The mechanism is a whitening of the positional codes" -- what does this mean?

I simply was not able to follow the paper's writing.

Critical strengths

None

Critical weaknesses

I found the paper to be virtually impossible to follow, despite careful reading.

Questions for authors

The AI use statement states that the authors reviewed all AI-assisted work. Is that true? Was the paper's main body carefully read by at least one author, one time?

3 comments

Thank you for your careful reading and constructive feedback. We have revised the manuscript to improve clarity and address your concerns. We respond to your comments point by point below.

Questions for authors — Human reading and AI use.

The AI use statement states that the authors reviewed all AI-assisted work. Is that true? Was the paper's main body carefully read by at least one author, one time?

Response. Yes to the main-text question: before the original submission, at least one listed human author carefully read the entire submitted main text. On the broader AI-use question, the revised statement replaces a blanket assurance with the specific human activities performed: reading manuscript and proof drafts, examining experimental records, checking code logic, recomputing key quantities and rerunning code. It separately identifies model-assisted cross-checks; these are not human verification. The authors take responsibility for the paper.

Weakness 1 / paper summary — Motivation and readability.

I found the paper to be virtually impossible to follow, despite careful reading.

Response. We rewrote the opening around a concrete question: if two of a thousand measured variables determine the response, what extra prediction error is caused by not knowing which two? The abstract now opens:

"When a response depends on only a few input coordinates, the learner faces uncertainty about both their identities and their joint effect. We ask how the statistical cost of locating them depends on the learner, and whether one attention head can achieve a near-optimal cost."

A response-affine rule uses labels in a weighted sum, but its weights are determined from inputs rather than labels. Fitting a selector from labels allows a different kind of adaptation. Fixed-kernel and fixed-feature ridge motivate this comparison. The Introduction now develops the question, comparator, architecture and statistical results in that order; Section 2 supplies the related-work context.

Summary, line 17 — The combinatorial price.

Without adaptive selection the price is combinatorial.

Response. We removed this compressed sentence. The restriction is response-affinity, not absence of attention. There are M=(Dk)M=\binom Dk candidate coordinate sets; this count enters the class's worst-case prediction risk as a multiplicative penalty. For M≥nM\ge n, the lower bound stays bounded away from zero. This is a risk statement, not an enumeration-time statement. Theorem 5.5 now shows sharpness under uniform design.

Summary, line 22 — The smoothness parameter.

integrability index

Response. This is pp, the exponent of the LpL^p norm used to measure smoothness. The abstract no longer uses this term. Section 1 introduces it in words; the norm appears after Assumption 3.1.

Summary, line 22 — The shifted exponent.

the exponent β\beta is the smaller, shifted one

Response. This referred to the slower response-affine rate for p<2p<2. The abstract no longer requires that technical distinction. Section 1 introduces effective smoothness and defines both exponents before the displayed rate; Theorem 5.5 covers both regimes.

Summary, line 27 — The positional-code construction.

The mechanism is a whitening of the positional codes

Response. Each coordinate has a fixed identifying vector. Correcting correlations among the selected vectors lets one query give those positions equal attention scores; a decoder then approximately recovers their values. This establishes a suitable selector for every support within the same budget. The estimator is not told the support. The opening explains this mechanism in words before Section 5.5 gives the construction.

The revised opening makes the problem and comparison accessible before the proof details: sharp response-affine limits, and exact fitting in one bounded attention class approaching the general minimax benchmark up to logarithms. Section 5.7 distinguishes statistical illustrations, construction diagnostics and training evidence.

Reviewer_wqSYOpenReview ↗

Reviewer response

I thank the authors for the response.

I maintain my score, as the original paper had serious presentation issues that give me concerns about how carefully the paper was checked before submission. Such issues require another round of submission and review, I believe, and should not be fixed between submission and the camera-ready stage.

Thank you for following up. We recognize that the original presentation made the paper harder to assess. The rewritten abstract and introduction are already in the discussion revision. They now start with the cost of not knowing which coordinates matter and explain the response-affine comparison before introducing the attention construction. If a particular part of the revised presentation still makes the results difficult to assess, we would appreciate knowing which part.

Comments on the paper

1 comment

We thank the reviewers for their constructive feedback. The revision strengthens the statistical results, adds high-dimensional training evidence, and presents the problem and contributions more clearly.

1. A sharp characterization of unknown-support cost. The original lower bound identifies a combinatorial penalty for response-affine estimators, whose prediction weights and offset may use inputs but not labels. New Theorem 5.5 establishes a matching upper bound under uniform design, including the p<2p<2 regime. Under uniform design, the dependence on the number of candidate supports M=(Dk)M=\binom Dk is minimax-sharp within the entire response-affine class, rather than an artifact of the lower-bound construction.

2. A stronger one-head bound and a near-minimax guarantee. New Theorem 5.4 identifies the effective selector coordinates (K⊤q,RV)(K^\top q,RV), reducing the covering exponent from 2m2+(k+1)m2m^2+(k+1)m to (k+1)m(k+1)m for the original bounded class, without changing the estimator. Combined with the all-estimator lower bound in Appendix G.1, this places the exact least-squares estimator's worst-case risk within a factor Clog⁡max⁡{3α,2}(2n)C\log^{\max\{3\alpha,2\}}(2n) of minimax, where α=2sˉ/(2sˉ+1)\alpha=2\bar s/(2\bar s+1). For fixed structural parameters, including kk and the design-density bounds, the guarantee is uniform over D≥2kD\ge2k, for n≥2n\ge2.

This gives a coherent statistical comparison: sharp response-affine limits under uniform design, a general minimax benchmark, and a bounded continuous one-head class whose exact ERM approaches that benchmark up to logarithmic factors.

3. Concrete training successes, including pure interaction. Appendix K.6 and Table 8 extend the practical evaluation. On the pure-interaction target at D=1024,n=16384D=1024,n=16384, twelve restarts with held-out selection produce a single trained head with mean normalised risk 0.262 versus 0.969 for the prior-optimal response-affine comparator. The paired difference is −0.707, with a 95% dataset-bootstrap interval [−0.880,−0.509]. Average gains also occur at D=256D=256 and 512512 along n=16Dn=16D.

The fixed-step recipe also succeeds on a target with marginal signals: at D=16384,n=1024D=16384,n=1024, its mean risk is 0.255 versus 0.957. These are measured advantages over the rule optimal in prior-average affine risk for each disclosed target family, not claims of samplewise optimality.

The follow-up designs were informed by preceding results; their formal runs used fresh seeds and fixed protocols. The adverse prespecified fixed-budget primary remains in Table 6; the largest restart comparison favours the head on 16/20 datasets. Protocols, budgets, screening controls and all outcomes are in K.6. The empirical gains complement, rather than establish attainment of, the exact-ERM guarantee.

4. Clearer scientific positioning. The abstract and Introduction now move from the unknown-coordinate problem to the estimator comparison, the single-head construction and its statistical consequences. Positional selection is shared across examples; support search provides another adaptive solution. The theoretical claim is near-minimax statistical performance of exact ERM, not an attention-exclusive or efficient-optimisation guarantee.

Overall, the revision goes beyond a separation: it provides sharp response-affine limits under uniform design, near-minimax one-head exact-ERM guarantees, and high-dimensional settings with substantial average gains over the prior-optimal affine comparator. We hope these additions address the central concerns and support a reassessment of the paper's contribution.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.