- 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
-
Does the lower bound sharply capture the cost of unknown support in your settings? Any proof of optimality?
-
Can the upper bound use the selector’s effective parameters? This could substantially improve the dimension dependence.
-
I'm willing to raise my score if the authors could further improve the scope and relevance of this work.
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.
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.