Understanding Model Reprogramming: A Reachability and Relabeling Perspective

Model reprogramming adapts a *frozen* source model to a target task by wrapping it in a *learnable* input transformation from target input to the source-model input space, and an output mapping from source-model outputs to target predictions. Despite extensive empirical progress, the *finite-sample learnability* of the induced wrapper hypothesis class $\mathcal{F}\_{\rm MR}$ remains underexplored. We address this for source models that expose hard source labels and analyze through the wrapper structure: on any target samples, the input transformation selects *reachable* source labels that the output mapping relabels. Through this lens, we answer two questions: ① how many target samples are needed to approach the best predictor in $\mathcal{F}\_{\rm MR}$, and ② what gap remains between the optimum over $\mathcal{F}\_{\rm MR}$ and the target Bayes risk. For ①, the wrapper structure factorizes the sample-wise complexity of $\mathcal{F}\_{\rm MR}$ into a *reachability* term counting reachable source-label patterns, and a *conditional relabeling* term counting their relabelings. This yields an agnostic-PAC bound on the *estimation error*, with sample complexity scaling additively in the two terms; this bound becomes closed-form on additive input transformations and is matched by a lower bound on an explicit binary classification construction. For ②, the same structure decomposes the *approximation error* exactly into the source-label information loss and output-mapping restriction with a source-conditional upper bound on this gap. We extend the approximation analysis to logit-exposing source models, where the upper bound is empirically estimable. The wrapper-side analysis localizes both errors to specific components, giving a structural view of reprogramming practice.