When is Fine-Tuning Scalable? Certified Recovery from Noisy Data and Linear-Cost Fine-Tuning on Structured Task Shifts

arXiv:2509.00924v2 Announce Type: replace-cross Abstract: Transformers often transfer across related tasks with little fine-tuning; we study this question in noisy nonparametric regression for continuous maps f,g:[0,1]^doR^D, representing the source and shifted tasks, using a single-query, single-head transformer T(dot)=Voperatorname{Softmax}(-alpha(dot,K)) with ell^{infty}-based alignment scores alpha. Rather than assume that gradient-based training reaches an empirical risk minimizer, we give a model-specific two-stage procedure extbf{certifying} source-task recovery and out-of-distribution (OOD) adaptation. With high probability, the resulting attention head recovers f to arbitrary accuracy arepsilon>0 in every fixed L^p([0,1]^d) norm, 1le p0. Importantly, our training procedure encodes all our identified (potentially) shared geometric structure from f only into the values matrix factor C and the keys matrix K allowing for rapid access, and all f-specific structure only into A. Our main result concerns the OOD phase; where we identify geometric structures, which if shared by the source f and OOD g task; then only only the values matrix factor A needs to be fine-tuned to guarantee an L^p-recovery of g. Critically, fine-tuning only A is a convex problem which involving an extit{at-most linear} number of parameters O(arepsilon^{-1}); dramatically cutting down on the worst-case scaling of O(arepsilon^{-mathbf{d}}) unavoidable in the source-training phase.

Source: arXiv cs.LG | 2026-10-28