Black-Box Assisted Regression: Phase Transitions and Minimax Optimality
Yan Zhou 1
arXiv:2606.25743v1 [cs.LG] 24 Jun 2026
Abstract
space access, or the ability to modify the pretrained model. The statistical question is therefore not how to train the foundation model, but how to use its predictions safely when its error on the target distribution is unknown.
Foundation models are often used as fixed blackbox predictors for downstream tasks with limited labeled data, but their predictions may be biased and unsafe to trust blindly. We study this setting through black-box assisted nonparametric regression: a learner observes labeled samples and can query a fixed predictor f0 , while the target f ∗ is close to f0 in L2 (PX ) up to an unknown radius δ. We give a finite-sample minimax characterization showing a phase transition at δc (n) ≍ n−β/(2β+d) , with leading risk min{δ 2 , n−2β/(2β+d) }. We then analyze a Safe Residual Estimator: it learns a correction around f0 , initializes the residual head at zero so the initial predictor equals f0 , and uses holdout selection to revert to f0 when the learned correction is not supported by validation data. Here, “safe” means avoiding negative transfer, i.e., performing worse than the black-box predictor alone. The estimator matches the leading minimax term up to an additive validation-selection cost. Synthetic regression experiments verify the predicted phase transition, while CIFAR-100 with CLIP and AG News with Qwen3-8B provide practice-facing evidence that the same residual-correction tradeoff is useful beyond the formal squared-loss regression setting.
We formalize this problem as Black-Box Assisted NonParametric Regression. The unknown target regression function f ∗ is assumed to satisfy ∥f ∗ − f0 ∥L2 (PX ) ≤ δ for an unknown prior error δ. Small δ defines a prior-dominated regime in which the black-box predictor is already reliable; large δ defines a sample-dominated regime in which labeled data must drive the correction. The challenge is to adapt to these regimes without knowing δ and without suffering negative transfer, meaning a final predictor whose risk is worse than using f0 alone. Our contribution is a finite-sample learning-theoretic characterization of this tradeoff. First, we prove a minimax lower bound showing that the leading risk is governed by min{δ 2 , n−2β/(2β+d) }. Second, we analyze a deliberately simple Safe Residual Estimator that learns a correction r̂ and then selects between f0 and f0 + r̂ on held-out data. Third, we show that this estimator matches the leading minimax term up to an additive validation cost and satisfies an oracle-style no-negative-transfer guarantee. Finally, we use synthetic regression experiments to check the theorem-level predictions and vision/NLP experiments to probe the same qualitative mechanism in practical classification pipelines.
Conflict of Interest Disclosure. The author declares no financial conflicts of interest related to this work.
1. Introduction Modern machine-learning pipelines often start from a strong pretrained system whose internal parameters or source data are unavailable to the downstream learner. The learner may only query a fixed black-box predictor f0 and then use a small labeled dataset from the target task. This access model differs from standard fine-tuning, transfer learning, and distillation: we do not assume source data, parameter-
2. Related Work Transfer, adaptation, and distillation. Classical transfer learning and domain adaptation often assume access to source data, source parameters, shared representations, or an adaptable pretrained model (Pan & Yang, 2010; Weiss et al., 2016; Cai & Pu, 2024; Lin & Reimherr, 2025; Kuzborskij & Orabona, 2013). Distillation similarly uses teacher predictions, but typically studies compression or training a student to imitate a teacher. Our setting is narrower and more statistical: the learner only receives fixed black-box predictions f0 (x) on target-task inputs and seeks minimaxoptimal target-risk guarantees under an unknown prior error.
1
School of Mathematics and Statistics, Changsha University of Science and Technology. Correspondence to: Yan Zhou <[email protected]>. Proceedings of the 43 rd International Conference on Machine Learning, Seoul, South Korea. PMLR 306, 2026. Copyright 2026 by the author(s).
1
Black-Box Assisted Regression: Phase Transitions and Minimax Optimality
continuous with constant L. (See Appendix B for the precise definition.)
Pseudo-labeling, self-training, and noisy labels. Pseudolabeling and self-training are widely used to exploit weak or machine-generated labels (Lee, 2013; Xie et al., 2020; Wang et al., 2021), and several works provide theoretical guarantees under distribution or subpopulation shift (Cai et al., 2021; Joo & Klabjan, 2024). These results are complementary to ours. Our claim is not that self-training lacks theory, but that prior work does not characterize the minimax phase transition min{δ 2 , n−2β/(2β+d) } for fixed black-box assisted regression. Noisy-label correction is also distinct: our target labels are standard noisy regression observations, not corrupted or mislabeled; the imperfect object is the fixed predictor f0 .
This class specifies the regularity of the residual r∗ in the minimax analysis of Section 5. Importantly, we do not assume that the black-box predictor f0 itself belongs to a Hölder or Sobolev class. The regularity condition is placed on the residual r∗ = f ∗ − f0 , together with the radius constraint ∥r∗ ∥L2 (PX ) ≤ δ. Thus f0 may come from a much more general source, including a foundation model, as long as the target-task correction around it is regular.
Prediction-powered inference and model selection. Prediction-powered inference (PPI) uses black-box predictions to construct valid confidence intervals (Angelopoulos et al., 2023; Zrnic & Candès, 2024), whereas our goal is risk-optimal function estimation. Our holdout step is closer to two-model validation/model selection: it selects between f0 and f0 + r̂, enabling an oracle inequality that formalizes no negative transfer.
The estimator is intentionally simple. Its role is not to compete with all possible transfer-learning heuristics, but to provide a clean statistical object for which the minimax tradeoff and no-negative-transfer property can be proved. The procedure has two candidates: the black-box predictor f0 and a residual-corrected predictor f0 + r̂. It then uses held-out data to select between them.
4. Method
We call the procedure safe because the selection step is designed to avoid negative transfer: if the learned residual correction does not improve held-out loss relative to f0 , the final predictor reverts to f0 . The binary selection is deliberate. Estimating a continuous mixing weight from scarce validation data can be unstable, whereas the two-candidate selection admits the oracle inequality in Theorem 5.7.
Summary. We formalize the “foundation model as prior” problem via non-parametric minimax theory, identifying the critical phase transition and proposing a safe residual estimator. A comprehensive discussion of additional literature, including neighboring transfer/adaptation methods (Gu et al., 2023; Lee et al., 2025), kernel methods, and PPI, is provided in Appendix A.
4.1. The Safe Residual Estimator
3. Problem Setup
The core intuition behind our method is to decompose the complexity of the learning task. We posit that the true function can be expressed as the sum of the black-box prior and a residual component:
We consider non-parametric regression with random design (Assumption 5.1) for the theoretical analysis. Random design means that the covariates are sampled i.i.d. from the target marginal distribution PX ; Assumption 5.1 specifies the bounded-domain and density conditions used in the proofs. Let X = [0, 1]d be the normalized input space. We assume the true regression function f ∗ : X → R belongs to a function class F (e.g., Hölder class or Sobolev class). We are given a dataset Dn = {(xi , yi )}ni=1 , where yi = f ∗ (xi )+ϵi and ϵi ∼ N (0, σ 2 ) are independent Gaussian noise.
f ∗ (x) = f0 (x) + r∗ (x),
(2)
where r∗ (x) = f ∗ (x) − f0 (x) is the target-task residual error of the black-box predictor. To achieve adaptivity to the unknown quality of the blackbox prior and mitigate negative transfer, we employ a Selectand-Estimate strategy. We split the available labeled data into a training set Dtr and a validation set Dval . We train a residual model r̂ on Dtr and then decide whether to use it based on performance on Dval .
We have access to a black-box predictor f0 : X → R derived from a pre-trained model, fixed during inference. Assuming f0 approximates f ∗ with a global error bound ∥f0 − f ∗ ∥L2 (PX ) ≤ δ (unknown δ ≥ 0), we construct an estimator fˆ minimizing the MSE risk: h i R(fˆ, f ∗ ) = E ∥fˆ − f ∗ ∥2L2 (PX ) . (1)
The residual-corrected candidate is fˆres = f0 + r̂. The final Safe Residual Estimator takes the form: fˆsafe (x) = f0 (x) + α̂ · r̂(x),
Definition 3.1 (Hölder Class). For β > 0 and L > 0, the Hölder class H(β, L) consists of functions f : [0, 1]d → R whose derivatives up to order ⌊β⌋ exist and are bounded, with the highest-order derivatives being (β − ⌊β⌋)-Hölder
(3)
where α̂ ∈ {0, 1} is a selection variable. If α̂ = 0, this triggers a reversion to the black-box; if α̂ = 1, we correct it. This mechanism is crucial for the “black-box dominated” 2
Black-Box Assisted Regression: Phase Transitions and Minimax Optimality
Formally, let S = span{f0 , fˆscratch } be the subspace spanned by the estimators. If the residual error r∗ contains a component in the orthogonal complement S ⊥ (e.g., r∗ contains high-frequency corrections missing from both f0 and the smooth approximation fˆscratch ), the weighted ensemble is fundamentally insensitive to it:
regime where learning the residual might be noisier than the bias itself. The detailed procedure, including the splitting and selection logic, is formally described in Algorithm 1. Algorithm 1 Safe Residual Estimator Input: Data Dtr , Dval , Prior f0 . 1. Residual Learning: Obtain r̂ by minimizing MSE of (y − f0 (x)) on Dtr . 2. Risk Assessment: P LBB ← (x,y)∈Dval (y − f0 (x))2 P LRes ← (x,y)∈Dval (y − f0 (x) − r̂(x))2 3. Safe Selection: α̂ ← I [LRes < LBB ] Output: fˆsafe (x) = f0 (x) + α̂ · r̂(x)
inf ∥fˆα − f ∗ ∥2 ≥ ∥PS ⊥ (r∗ )∥2 ,
(4)
α∈R
where PS ⊥ is the orthogonal projection operator. Remark 4.1 (Geometric Interpretation: Subspace vs. Ball). The fundamental limitation of the weighted ensemble lies in its geometry. The estimator fˆα is constrained to search within a one-dimensional affine subspace connecting f0 and fˆscratch . In contrast, our residual estimator searches within a ball centered at f0 in the function space F. From a manifold perspective, if the bias r∗ lies in the null space of the projection operator onto the line spanned by {f0 , fˆscratch }, the weighted ensemble is blind to it. Our method, by explicitly modeling the residual map, effectively performs a local re-centering of the hypothesis class, allowing it to recover high-frequency corrections that are orthogonal to the base predictors.
The algorithm selects between f0 and fˆres = f0 + r̂; it is not selecting between zero-shot and scratch. Therefore the selected residual candidate can outperform both the blackbox predictor and a scratch estimator when the correction r̂ is estimable. For neural residual heads used in the classification experiments, we use zero-initialization: the residual head is initialized so that r̂ ≡ 0 at the start of training. Thus the initial predictor equals f0 , and the model departs from the black-box prior only when the labeled data provide a training signal. Detailed hyperparameters and architectures are provided in Appendix F.
4.3. Structural Advantage and Risk Decomposition To understand why the R ESIDUAL estimator provides a fundamental advantage, we analyze the decomposition of the expected risk. Let R(fˆ) = E[∥fˆ − f ∗ ∥2 ] be the L2 risk. For a standard estimator fˆscratch trained on Dn , the risk is governed by the complexity of the entire function class F.
4.2. Why Residualization Rather Than Linear Ensembling?
In our framework, we write fˆ(x) = f0 (x) + r̂(x). Since f0 is a fixed, deterministic black-box, the risk of our estimator becomes:
Linear or validation-tuned ensembling is a natural modelselection baseline, and related forms of ensembling and weight-space adaptation are common in transfer and fewshot settings (Gu et al., 2023; Lee et al., 2025). In our fixed function-access setting, however, a convex combination of f0 and a scratch estimator can only move within their linear span.
2
R(fˆ) = EX,ϵ ∥(f0 + r̂) − (f0 + r∗ )∥L2 2
= E ∥r̂ − r∗ ∥L2 .
(5)
This identity reveals a crucial insight: the statistical difficulty of the task is shifted from estimating f ∗ to estimating the residual r∗ . From a bias-variance perspective, if we use a kernel-based learner with regularization parameter λ, the risk of r̂ can be bounded by:
A common alternative to residual learning is the weighted ensemble, fˆα (x) = αf0 (x) + (1 − α)fˆscratch (x), where α ∈ [0, 1]. While effective for variance reduction, we highlight a fundamental geometric limitation of this approach in correcting residual errors that are not aligned with the scratch estimator.
R(r̂) ≤ ∥(I − Kλ )r∗ ∥2 + | {z } Approximation Bias
σ2 tr(Kλ2 ) , n | {z }
(6)
Estimation Variance
where Kλ is the smoothing operator. While the variance term remains O(n−1 · effective dim), the bias term now depends only on the energy of r∗ . Under Assumption 5.2, ∥r∗ ∥ ≤ δ. When δ is small, the approximation bias is significantly lower than that of fˆscratch , which must account for the full magnitude ∥f ∗ ∥. This structural prior effectively “centers” the learning process around f0 , allowing the model
Consider the Hilbert space L2 (PX ). The weighted ensemble restricts the estimator to the affine line segment connecting the prior f0 and the data-driven estimator fˆscratch . Let the true residual be r∗ = f ∗ − f0 . The approximation error is minimized when (1 − α)(fˆscratch − f0 ) ≈ r∗ . However, fˆscratch is trained to approximate f ∗ , not to align with the bias direction r∗ . 3
Black-Box Assisted Regression: Phase Transitions and Minimax Optimality (a) Function Fitting & Bias Correction
(b) Phase Transition of Minimax Risk
2.5 Noisy Data
Weighted Residual (Ours)
Ground Truth f *
2.0
Mean Squared Error (log)
Black-Box f0
Response y
1.5 1.0 0.5 0.0 −0.5
10
−1
Prior Dominated
10
−2
Black-Box Risk (δ 2) 2β
−1.0
Scratch Risk (n −2β + d )
Phase Transition δc(n)
Residual (Ours)
−1.5
Sample Dominated
0.0
0.2
0.4
0.6
Input Space
0.8
1.0
10
1
10
2
10
3
Sample Size n (log)
Figure 1. Theory in Action: The Phase Transition. (a) Mechanism: Unlike W EIGHTED ensembles (orange) that are constrained to a linear subspace spanned by the prior and data, our R ESIDUAL estimator (blue) performs a non-linear correction, effectively capturing the complex residual r∗ (x). (b) Risk Profile (Key Theoretical Result): We identify a critical threshold δc (n). Left of dashed line (Prior-Dominated): The black-box is accurate (δ is small); our estimator adapts and achieves the fast rate δ 2 . Right of dashed line (Sample-Dominated): The black-box is biased; our estimator safely recovers the optimal non-parametric rate n−α , avoiding the high error floor of the black-box. Note how S AFE R ESIDUAL (blue curve) tracks the lower envelope by selecting between f0 and f0 + r̂, not between zero-shot and scratch.
to allocate its limited sample budget entirely to correcting the prior’s deficiencies.
residual structure. Assumption 5.2 (Residual Regularity and Boundedness). Let f0 be a fixed black-box predictor. The true function satisfies f ∗ = f0 +r∗ where r∗ ∈ H(β, L) and ∥r∗ ∥L2 (PX ) ≤ δ. Moreover, assume ∥r∗ ∥∞ ≤ B and ∥f0 ∥∞ ≤ B0 .
5. Theoretical Analysis We give finite-sample minimax bounds for black-box assisted regression. The results characterize the leading minimax term and the additional cost introduced by holdout selection, rather than claiming exact equality between the lower and upper bounds. Theorem 5.4 gives the minimax lower bound and identifies the phase transition. Theorem 5.5 analyzes a validation-selected residual estimator and shows that it adapts to the unknown prior quality. Theorem 5.7 is an oracle inequality for the concrete holdout selection step in Algorithm 1, showing that the selected predictor performs almost as well as the better of f0 and f0 + r̂.
This definition implies that the residual r∗ = f ∗ − f0 is smooth and has bounded L2 (PX ) energy (controlled by δ). Definition 5.3 (Black-box Assisted Class). Define F(δ) := {f0 + r : r ∈ H(β, L), ∥r∥L2 (PX ) ≤ δ, ∥r∥∞ ≤ B}.
(7)
5.2. Minimax Lower Bounds We first characterize the fundamental limit of this learning problem. The following theorem establishes an informationtheoretic lower bound for any estimator.
5.1. Assumptions and Definitions We consider the non-parametric regression problem yi = f ∗ (xi ) + ϵi with ϵi ∼ N (0, σ 2 ). To rigorously relate the empirical risk to the population L2 risk, we introduce a standard design assumption. Assumption 5.1 (Random Design). The covariates {xi }ni=1 are i.i.d. samples from a distribution PX on X = [0, 1]d with Lebesgue density p(x) satisfying c ≤ p(x) ≤ C for constants 0 < c ≤ C < ∞.
Theorem 5.4 (Minimax Lower Bound). Under Assumptions 5.1 and 5.2, there exists a constant c > 0 depending only on β, L, d, σ and the density bounds in Assumption 5.1 such that: inf sup E∥fˆ − f ∗ ∥2L2 (PX ) fˆ f ∗ ∈F (δ) (8) 2β ≥ c · min δ 2 , n− 2β+d .
Next, we define the structure of the true function f ∗ relative to the black-box f0 . Instead of assuming f ∗ lies in a generic ball, we define the function class explicitly in terms of the
Proof sketch in Appendix C; full proof in Appendix D.2. This theorem rigorously establishes the Phase Transition. The term δ 2 represents the irreducible bias floor if one relies 4
Black-Box Assisted Regression: Phase Transitions and Minimax Optimality Table 1. 1D Synthetic Regression (MSE). Comparison of risk under varying sample size n and prior error δ. R ES ( SAFE ) denotes the selected predictor that chooses between f0 and f0 + r̂, not between BB and S CRATCH. Key Observation: When the black-box is perfect (δ = 0.0), R ESIDUAL ( RAW ) suffers from negative transfer (0.0335), but R ESIDUAL ( SAFE ) effectively falls back (Fallback=65%), reducing risk to 0.0027. When bias is large (δ = 0.8), our method significantly outperforms W EIGHTED (0.097 vs 0.145) by modeling the non-linear residual. In the extreme bias regime (δ = 1.5), R ESIDUAL (0.146) dramatically outperforms S CRATCH (0.189). BB
W GT
C AT
R ES ( RAW )
R ES ( SAFE )
FALLBACK
S CRATCH
0.0000 0.0100 0.6399 2.2496 0.0000 0.6399
0.0007 0.0096 0.1452 0.1700 0.0026 0.0311
0.0501 0.0589 0.1448 0.1599 0.0107 0.0712
0.0335 0.0368 0.0857 0.1461 0.0108 0.0130
0.0027 0.0118 0.0971 0.1461 0.0006 0.0130
65% 60% 5% 0% 65% 0%
0.1894 0.1894 0.1894 0.1894 0.0325 0.0325
S ETTING n = 20, δ = 0.0 n = 20, δ = 0.1 n = 20, δ = 0.8 n = 20, δ = 1.5 n = 50, δ = 0.0 n = 50, δ = 0.8
Table 2. High-Dimensional Regression (d = 20, n = 100). In high dimensions with limited samples, learning the residual is difficult. S CRATCH suffers from the curse of dimensionality, with risk staying high (0.489) even at n = 100. R ES ( SAFE ) selects between f0 and f0 + r̂. When the prior is poor (δ = 1.0), R ESIDUAL ( RAW ) explodes (1.026) due to the curse of dimensionality, performing worse than the black-box (0.994). Our S AFE R ESIDUAL detects this failure, triggering fallback (60%) and stabilizing the risk at 1.007. δ
BB
W GT
C AT
R ES ( RAW )
R ES ( SAFE )
FALLBACK
S CRATCH
0.0 0.2 0.5 1.0
0.000 0.040 0.248 0.994
0.006 0.047 0.253 0.485
0.034 0.074 0.280 0.509
0.006 0.048 0.263 1.026
0.002 0.040 0.250 1.007
40% 70% 60% 60%
0.489 0.489 0.489 0.489
2β
solely on the black-box, while n− 2β+d represents the optimal rate for learning the residual from data. The difficulty is governed by the minimum of these two quantities. See Appendix C for geometric intuition regarding the packing argument.
nonparametric residual regressor on Dtr , and safe holdout selection on Dval ) such that for all δ ≥ 0, sup E∥fˆsafe − f ∗ ∥2L2 (PX )
f ∗ ∈F (δ)
C′ 2β ≤ C · min δ 2 , n− 2β+d + , n
The critical threshold for this phase transition is given by: β
δc (n) ≍ n− 2β+d .
(10)
where C and C ′ depend only on (β, L, d, σ, B, B0 , c, C) and not on n, δ, or f0 .
(9)
When δ ≪ δc (n), we are in the black-box dominated regime; otherwise, we enter the sample dominated regime.
See Appendix D.3 for the detailed construction and proof. Implication. This result shows that the estimator matches the leading minimax term up to the additive validationselection cost C ′ /n. Since 2β/(2β + d) < 1, this cost is asymptotically lower order than the standard nonparametric term, but it can be the active finite-sample price in the strongly prior-dominated regime.
5.3. Upper Bounds and Adaptivity Can we achieve this lower bound? A naive estimator might fail to adapt to the unknown δ. We analyze a theoretically grounded Select-and-Estimate procedure matching the Safe Residual Estimator: it uses sample splitting to choose between the black-box and the residual-corrected estimator.
Corollary 5.6 (Near-Minimax Rate of the Safe Residual Estimator). Let fˆsafe denote the output of Algorithm 1 with split ratio ρ ∈ (0, 1). Under Assumptions 5.1–5.2, fˆsafe is minimax-optimal up to the validation-selection cost and a constant inflation factor from sample splitting:
The following bounds are non-asymptotic: they hold for every finite n, every δ ≥ 0, and every fixed black-box predictor f0 . In particular, δ is a property of the black-box prior and does not vary with n. The phase transition at δc (n) ≍ n−β/(2β+d) should therefore be read as a finitesample tradeoff between prior error and the difficulty of estimating the residual from labeled data.
sup E∥fˆsafe − f ∗ ∥2L2 (PX )
f ∗ ∈F (δ)
2β 2β ≤ (1 − ρ)− 2β+d · C min δ 2 , n− 2β+d
Theorem 5.5 (Upper Bound). There exists an estimator fˆsafe (constructed via sample splitting, a minimax-optimal
+Õ(n−1 ). 5
(11)
Black-Box Assisted Regression: Phase Transitions and Minimax Optimality
In particular, with ρ = 0.2 and β ≈ d, the inflation factor 2β is (1 − ρ)− 2β+d ≈ 1.16. Thus, Algorithm 1 matches the leading lower-bound term in Theorem 5.4 up to constant factors and the additive validation-selection cost.
Remark (no negative transfer up to validation cost). The oracle inequality formalizes safety: relative to the two candidates considered by the algorithm, the selected predictor is within an additive validation cost of the better candidate. In particular, because f0 is one of the candidates, the selected predictor cannot be substantially worse than the black-box route except for the finite-sample validation term.
5.4. Theoretical Guarantee for Safe Selection A key component of our method is the validation-based selection mechanism (Step 2 in Algorithm 1). We now give a rigorous oracle inequality for the selected predictor. Two notions of risk. For any (possibly data-dependent) predictor f , define the population estimation error
Remark (expectation form). Integrating (13) over Dval yields an expectation bound of the same form (with constants), and using (12) one may equivalently state the oracle inequality in prediction risk. A complete proof is provided in Appendix D.
Err(f ) := ∥f − f ∗ ∥2L2 (PX ) ,
5.5. The Price of Safety: Analysis of Sample Splitting
which is random because f depends on the training data. Also define the prediction risk
Our proposed estimator relies on sample splitting, using ntr samples for learning the residual and nval samples for selection. A natural concern is the statistical efficiency loss due to reducing the effective training set size from n to ntr = (1 − ρ)n, where ρ ∈ (0, 1) is the validation fraction (e.g., ρ = 0.2).
L(f ) := E (Y − f (X))2 f . Under the model Y = f ∗ (X) + ϵ with E[ϵ2 ] = σ 2 , we have the exact identity L(f ) = Err(f ) + σ 2 .
We quantify this “price of safety” as the ratio of the minimax risks. In the sample-dominated regime where learning is 2β necessary, the risk scales as n− 2β+d . The inflation factor due to splitting is:
(12)
Hence, oracle guarantees for prediction risk immediately translate to estimation error, up to an additive constant σ 2 .
2β
Inflation Factor = Setup. Let fˆBB := f0 and fˆRes := f0 + r̂, where r̂ is trained on Dtr . On an independent validation set Dval of size nval , define the empirical validation losses L̂val (f ) :=
1 nval
X
2β − 2β+d
(14) .
For ρ = 0.2 and β ≈ d, this factor is ≈ 1.11, implying only an 11% risk increase. In contrast, failing to select (i.e., blindly trusting a biased prior) incurs a risk of δ 2 , which can be arbitrarily larger than the optimal rate n−α as n → ∞. Thus, the sample splitting strategy trades a small, constant-factor increase in variance for robust protection against potentially unbounded bias.
(x,y)∈Dval
and select fˆsafe ∈ {fˆBB , fˆRes } by minimizing L̂val (·). Theorem 5.7 (Oracle Inequality for Safe Selection (holdout)). Assume ϵ is sub-Gaussian with parameter σ (Gaussian is a special case), and ∥f ∗ ∥∞ ≤ B0 + B (implied by Assumption 5.2). Fix any γ ∈ (0, 1) and δ ′ ∈ (0, 1). Then, conditional on the training data Dtr , with probability at least 1 − δ ′ over the validation sample Dval ,
log(2/δ ′ ) +C , nval
2β
n− 2β+d
= (1 − ρ)
(y − f (x))2 ,
Err(fˆsafe ) ≤ (1 + γ) · min Err(fˆBB ), Err(fˆRes )
((1 − ρ)n)− 2β+d
5.6. Proof Intuition: Metric Entropy and Adaptivity The convergence rates in Theorems 5.4 and 5.5 are deeply tied to the metric entropy of the function classes. Let H(ϵ, F, ∥ · ∥) be the ϵ-entropy of class F. The minimax rate for a class is typically determined by the solution to the equation ϵ2 ≍ H(ϵ, F)/n.
(13)
For the standard Hölder class H(β, L), the entropy scales as ϵ−d/β . However, our black-box assisted class F(δ) (Definition 5.3) is the intersection of a smoothness ball and an L2 ball of radius δ.
where C depends only on (B0 + B, σ).
When ϵ > δ, the L2 constraint is active, and the effective entropy is drastically reduced, leading to the δ 2 floor. When
Proof provided in Appendix D.5. 6
Black-Box Assisted Regression: Phase Transitions and Minimax Optimality
ϵ < δ, the smoothness constraint dominates, recovering the 2β n− 2β+d rate.
(Gu et al., 2023; Lee et al., 2025). We therefore discuss them as related work rather than direct baselines for our fixed function-access formulation. All reported classification numbers are mean ± standard deviation over three independent runs; no best-run selection is used.
Our Safe Residual Estimator achieves this regime selection by implicitly performing a multi-scale analysis. The validation step (Algorithm 1) acts as a statistical test that checks whether the data-driven correction r̂ has a higher signal-tonoise ratio than the prior’s error δ. This ensures that we only “pay” the metric entropy cost of the full Hölder class when the evidence from Dn is strong enough to guarantee an improvement over f0 .
We compare five estimators: (1) S CRATCH: Standard supervised learning (KRR/MLP) trained solely on labeled data. (2) BB-O NLY: Direct zero-shot/few-shot predictions. (3) W GT (Val-Tuned): An ensemble αf0 (x) + (1 − α)fˆscratch (x), where α is optimized on the validation set to ensure a strong baseline. (4) C ONCAT: Training on concatenated features [x, f0 (x)]. (5) R ESIDUAL (Ours): The proposed method learning y − f0 (x) with zero-initialization and safe selection.
6. Experiments Connection to Theoretical Analysis. The experiments are designed to test the statistical mechanisms in the theory rather than to provide an exhaustive benchmark against all transfer-learning methods. Each baseline corresponds to a quantity or alternative in the analysis: BB-O NLY realizes the prior-error floor δ 2 ; S CRATCH realizes the standard nonparametric learning route; validation-tuned W GT tests the linear-combination alternative; C ONCAT tests a simple way to expose the learner to black-box information without residual centering; and R ESIDUAL tests the estimator predicted by the theory.
Raw vs. Safe Residual. We distinguish R ESIDUAL ( RAW ) that always predicts f0 (x) + r̂(x), from our final S AFE R ESIDUAL predictor that performs holdout selection between {f0 , f0 + r̂} as in Algorithm 1. Only the latter enjoys the (no-negative-transfer) oracle guarantee in Theorem 5.7. The final method does not choose between zero-shot and scratch. It chooses between f0 and the residual-corrected predictor f0 + r̂. Therefore, when r̂ captures a target-task correction, the selected predictor can outperform both the black-box prior and a scratch estimator.
Synthetic Regression. This controlled setting satisfies the squared-loss regression assumptions directly and numerically verifies the finite-sample phase transition.
6.1. Synthetic Validation 1D Phase Transition & Negative Transfer. We generated data where the black-box f0 has a low-frequency residual error. Figure 1 illustrates the mechanism and risk profile, while Table 1 presents the Mean Squared Error (MSE). Table 1 reports raw residual to illustrate the learning curve; our final method uses safe selection (Alg. 1) with an oracle guarantee (Thm. 5.7). In the “bad black-box” regime (n = 20, δ = 1.5), BB-O NLY incurs huge error (2.25), but R ESIDUAL ( RAW ) adapts effectively (0.146), outperforming S CRATCH (0.189). In the “small sample” regime (n = 50, δ = 0.0), S AFE R ESIDUAL achieves near-zero error (0.0006), vastly outperforming S CRATCH (0.0325). Notably, at n = 20, δ = 0.8, S AFE R ESIDUAL (0.097) beats W EIGHTED (0.145), showing the benefit of non-linear correction.
Real-World Classification (Vision & NLP). Our formal guarantees are for squared-loss regression. The CIFAR100 and AG News experiments use cross-entropy training and accuracy-based selection, and should not be read as theorem-level extensions of Theorems 5.4–5.7. They provide practice-facing evidence that the same qualitative tradeoff between prior quality and correction complexity appears in classification when viewed at the level of score or logit functions. For the classification experiments, we adopt the following mapping to connect with our theoretical framework: we treat multi-class classification as a regression problem on logit/score functions. Specifically, for a K-class problem, we learn K score functions {fk }K k=1 , where each fk : X → R predicts the logit for class k. The black-box prior provides initial logits {f0,k }K k=1 , and our residual esti∗ ∗ mator learns corrections {rk }K k=1 such that fk = f0,k + rk . The same structural intuition may remain informative, but our theorems do not prove minimax rates for cross-entropy training or accuracy-based selection.
Table 1 explicitly demonstrates the protection mechanism. In the noise-dominated regime (n = 20, δ = 0.0), the raw residual estimator overfits the noise (MSE 0.0335). However, the validation-based selection triggers a fallback in 65 Breaking the Curse of Dimensionality (High-Dim). In the d = 20 setting (Table 2), S CRATCH suffers from the curse of dimensionality, with risk staying high (∼ 0.48) at n = 100. In contrast, when the black-box is reasonably good (δ = 0.0), S AFE R ESIDUAL achieves a risk of 0.002,
Recent adaptation methods such as continual/classincremental approaches or weight-space ensembling address neighboring but different access models, often requiring parameter or weight-space access to the pretrained model 7
Black-Box Assisted Regression: Phase Transitions and Minimax Optimality Table 4. NLP Task (AG News with Qwen3-8B, Accuracy %) (mean ± std over 3 runs). BB baseline is 74.06%. At extremely low sample sizes (n = 64), the W GT (Val-Tuned) ensemble collapses to the scratch performance (54.7%) due to validation noise, while R ES remains robust (74.7%). Fallback=0.0% across all settings.
Sample Efficiency on CIFAR-100 (CLIP) 70 Zero-shot (CLIP)
Test Accuracy (%)
60
+2.51%
50 40 30 20
Scratch (Linear Probe) Concat Features Weighted Ensemble Safe Residual (Ours)
10 0
100
200
500
1000
n
S CRATCH W GT (VAL )
16 32 64 128 256
27.4±1.5 29.3±1.6 54.7±2.0 64.5±1.8 69.7±1.5
71.2±0.8 74.5±0.7 54.7±0.7 72.7±0.6 75.6±0.5
C AT
R ES ( SAFE )
31.0±1.8 34.5±1.7 48.8±2.2 65.1±1.9 72.3±1.6
75.2±0.6 74.1±0.5 74.7±0.5 76.6±0.7 77.0±0.6
2000
Number of Labeled Samples (n)
Figure 2. Sample Efficiency on CIFAR-100. Comparison of test accuracy as the number of labeled samples n increases. S CRATCH (gray) and C ONCAT (green) degrade severely in the few-shot regime. In contrast, our S AFE R ESIDUAL estimator (blue) consistently outperforms the strong W EIGHTED ensemble baseline (orange). Notably, at n = 2000, our method achieves a 2.5% gain over the weighted ensemble.
n = 200, we observe that W GT underperforms the zeroshot baseline (54.5% vs 59.4%). This occurs because the validation set is too small to reliably estimate the optimal mixing weight α, leading to overfitting. Similarly, C AT fails completely (0.4%) due to the curse of dimensionality. Our R ES method avoids these pitfalls through zero-initialization. Furthermore, consistent with our L2 theory, R ES achieves the lowest Brier Score (MSE) of 0.443 at n = 2000 (vs 0.538 for Black-Box).
Table 3. CIFAR-100 Accuracy (%) (mean ± std over 3 runs). BB (CLIP Zero-shot) is 59.39%. Our R ES method consistently outperforms baselines. Notably, at n = 2000, it surpasses the strong W GT (Validation-Tuned) ensemble by 2.7%. Zero-initialization provided implicit regularization, preventing negative transfer (Fallback=0.0% across all settings). n
S CRATCH
C AT
100 200 500 1000 2000
2.1±0.3 9.9±0.5 21.7±0.8 42.9±1.2 57.2±1.5
0.4±0.1 13.2±0.6 21.7±0.9 33.3±1.5 45.2±1.8
Robustness in Few-Shot. With only 100 samples (1 per class), S AFE R ESIDUAL maintains performance (59.82%) slightly above the Zero-shot baseline (59.39%), successfully avoiding the collapse seen in C ONCAT (0.39%) and S CRATCH (2.11%).
W GT (VAL ) R ES ( SAFE ) 59.3±0.2 54.5±0.3 59.4±0.3 61.8±0.4 63.9±0.5
59.8±0.2 60.4±0.2 61.0±0.3 64.4±0.4 66.7±0.5
Ablation Studies. We rigorously analyze the sensitivity of our method to the validation fraction ρ and the impact of zero-initialization in Appendix G. Figures 3a and 3b demonstrate that our method remains stable for ρ ∈ [0.15, 0.3] and zero-initialization significantly reduces early training variance compared to random initialization.
a 250× improvement. Table 2 reports raw residual to illustrate the high-dimensional variance barrier; our final method uses safe selection (Alg. 1) with an oracle guarantee (Thm. 5.7).
6.3. NLP: Qwen3-8B on AG News We extend our evaluation to NLP using Qwen3-8B (Yang et al., 2025). We extract 4096-dimensional feature embeddings and use prompt-based generation for f0 . The results are summarized in Table 4.
In high dimensions (d = 20), the phase transition is delayed. As shown in Table 2 (δ = 1.0), the sample size n = 100 is insufficient to resolve the residual, causing the raw estimator to degrade (1.026) compared to the black-box (0.994). The safe selection mechanism acts as a critical brake, maintaining performance near the black-box baseline.
Robustness in Ultra-Low Sample Regime. The NLP task demonstrates a key advantage of our residual structure in the extreme few-shot setting (n = 16). As shown in Table 4, the black-box prior provides a strong baseline (74.06%). Critically, in the ultra-low sample regime, the W GT ensemble suffers from negative transfer (71.21% < 74.06%) due to variance in weight estimation—the limited data is insufficient to reliably estimate the optimal mixing weight. In contrast, our R ES estimator achieves 75.23% at n = 16, demonstrating that the residual structure with zero-initialization is more robust than linear ensembling when data is scarce.
6.2. Vision: CLIP on CIFAR-100 Comparison with Baselines. The results are summarized in Table 3 and visualized in Figure 2. At n = 2000, R ES reaches 66.7%, significantly outperforming W GT (63.9%) and C AT (45.2%). R ES consistently beats W GT across all sizes, providing practice-facing evidence for the benefit of non-linear correction. Addressing Baseline Instability: At 8
Black-Box Assisted Regression: Phase Transitions and Minimax Optimality
Analysis of Baseline Instability. Interestingly, we observe that the validation-tuned weighted ensemble (W GT) exhibits instability in low-sample regimes (e.g., n = 64 in Table 4). Due to the small validation set size, the selection of α becomes noisy, occasionally causing the model to collapse to the weaker scratch learner (54.7% vs 74.7% for Residual). In contrast, our Residual estimator, regularized by zero-initialization, provides more stable performance in this fixed black-box access setting.
work to heavy-tailed noise (e.g., via Huber loss) and online learning settings remains an open problem. Explicit vs. Implicit Safety. Our experiments reveal two distinct mechanisms for safety. In high-noise synthetic settings (Table 1, 2), the explicit validation-based fallback is active (Fallback > 0), effectively filtering out noisy updates. In real-world tasks (Vision/NLP), where pre-trained representations are robust, we observe implicit safety: the fallback rate is 0.0, yet no negative transfer occurs (e.g., Table 4, n = 16). This is attributed to our zero-initialization strategy, which places the estimator exactly at f0 at the start of training. This strong inductive bias ensures that the model only deviates from the prior when the data signal is sufficiently strong, effectively achieving “soft” safety without triggering the hard fallback switch.
Scaling and Crossover. At n = 256, the gap narrows but remains significant (W GT 75.59% vs. R ES 76.95%). This suggests that residual learning is most useful in few-shot regimes via inductive bias (zero-initialization). The fallback rate remains 0.0% across all settings, indicating that zeroinitialization provides implicit regularization even in the n = 16 regime.
8. Conclusion 7. Discussion
We formulated black-box assisted regression as a finitesample minimax problem and characterized a phase transition at δc (n) ≍ n−β/(2β+d) . The Safe Residual Estimator matches the leading minimax term up to an additive validation-selection cost and satisfies an oracle-style safety guarantee relative to the black-box predictor. Synthetic regression experiments verify the predicted phase transition, while vision and NLP experiments suggest that residual correction with zero-initialization is a useful practical principle beyond the formal regression setting.
Statistical Interpretation. From a decision-theoretic perspective, the black-box f0 centers the hypothesis space. Our residual estimator restricts the search to a local ball B(f0 , δ), reducing metric entropy and breaking the curse of dimensionality. Scope of the formal guarantees. The theorems in this paper are for squared-loss regression under the stated randomdesign and residual-regularity assumptions. The classification experiments are meant to probe the same residualcorrection mechanism in practical settings, not to establish minimax guarantees for cross-entropy loss or accuracybased model selection.
Acknowledgements The author would like to thank the School of Mathematics and Statistics, Changsha University of Science and Technology, for its support.
Design assumptions. The compact support and boundeddensity assumptions are used to obtain clean norm equivalences and packing arguments. They are standard in nonparametric random-design theory, but relaxing them to unbounded or heavy-tailed covariate distributions is an important direction for future work.
Impact Statement This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
Selection cost. The additive O(1/n) term is the finitesample cost of holdout-based selection. It is lower order than the nonparametric rate when d < ∞, but can dominate in a strongly prior-dominated regime. Removing or reducing this term may require a different adaptation mechanism, such as a Lepski-type method without sample splitting, or a sharper validation analysis. Generative models. The same black-box-prior plus residual-correction idea may be relevant to score or denoising-function estimation in diffusion models, but our current results do not establish such guarantees. We leave this extension to future work. Limitations. Our current analysis assumes homoscedastic Gaussian noise and a static black-box. Extending the frame9
Black-Box Assisted Regression: Phase Transitions and Minimax Optimality
References
He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learning for image recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2016.
Amini, M.-R., Feofanov, V., Pauletto, L., Hadjadj, L., Devijver, É., and Maximov, Y. Self-training: A survey. Neurocomputing, 616:128904, 2025. doi: 10.1016/j.neuc om.2024.128904.
Hofer, R. A., Maynez, J., Dhingra, B., Fisch, A., Globerson, A., and Cohen, W. W. Bayesian prediction-powered inference, 2024.
Angelopoulos, A. N., Bates, S., Fannjiang, C., Jordan, M. I., and Zrnic, T. Prediction-powered inference. Science, 382 (6671):669–674, 2023. doi: 10.1126/science.adi6000.
Joo, T. and Klabjan, D. Improving self-training under distribution shifts via anchored confidence with theoretical guarantees. In Globerson, A., Mackey, L., Belgrave, D., Fan, A., Paquet, U., Tomczak, J., and Zhang, C. (eds.), Advances in Neural Information Processing Systems, volume 37, pp. 15246–15271. Curran Associates, Inc., 2024. doi: 10.52202/079017-0487. URL https: //proceedings.neurips.cc/paper_files /paper/2024/file/1b99db17b54735d22db ed15c24f2dbdc-Paper-Conference.pdf.
Angelopoulos, A. N., Duchi, J. C., and Zrnic, T. Ppi++: Efficient prediction-powered inference, 2024. Arlot, S. and Celisse, A. A survey of cross-validation procedures for model selection. Statistics Surveys, 4:40–79, 2010. doi: 10.1214/09-SS054. Bai, J., Bai, S., Chu, Y., et al. Qwen technical report, 2023. Cai, T., Gao, R., Lee, J., and Lei, Q. A theory of label propagation for subpopulation shift. In Meila, M. and Zhang, T. (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 1170–1182. PMLR, 18–24 Jul 2021. URL https://proceedi ngs.mlr.press/v139/cai21b.html.
Kage, P., Rothenberger, J. C., Andreadis, P., and Diochnos, D. I. A review of pseudo-labeling for computer vision, 2025. Kim, J., Nakamaki, T., and Suzuki, T. Transformers are minimax optimal nonparametric in-context learners. In Advances in Neural Information Processing Systems, volume 37, pp. 106667–106713, 2024.
Cai, T. T. and Pu, H. Transfer learning for nonparametric regression: Non-asymptotic minimax analysis and adaptive procedure, 2024.
Kluger, D. M., Lu, K., Zrnic, T., Wang, S., and Bates, S. Prediction-powered inference with imputed covariates and nonuniform sampling, 2025.
Caponnetto, A. and De Vito, E. Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics, 7(3):331–368, 2007. doi: 10.1007/s10208-006-0196-8.
Krizhevsky, A. and Hinton, G. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009.
Cortinovis, S. and Caron, F. Fab-ppi: Frequentist, assisted by bayes, prediction-powered inference, 2025.
Kuzborskij, I. and Orabona, F. Stability and hypothesis transfer learning. In Proceedings of the 30th International Conference on Machine Learning, volume 28, pp. 942– 950. PMLR, 2013.
Fan, J. Local Polynomial Modelling and Its Applications. Routledge, 1996. ISBN 9780203748725.
Lee, D.-H. Pseudo-label : The simple and efficient semisupervised learning method for deep neural networks. In ICML 2013 Workshop on Challenges in Representation Learning, 2013.
Fisch, A., Maynez, J., Hofer, R. A., Dhingra, B., Globerson, A., and Cohen, W. W. Stratified prediction-powered inference for hybrid language model evaluation, 2024. Goodfellow, I., Bengio, Y., Courville, A., and Bengio, Y. Deep learning, volume 1. MIT press Cambridge, 2016.
Lee, J., Hayat, M., and Yun, S. Tripartite weight-space ensemble for few-shot class-incremental learning. In Proceedings of the Computer Vision and Pattern Recognition Conference, pp. 15329–15338, 2025.
Gu, Z., Xu, C., Yang, J., and Cui, Z. Few-shot continual infomax learning. In 2023 IEEE/CVF International Conference on Computer Vision (ICCV), pp. 19167–19176, Paris, France, 2023. doi: 10.1109/ICCV51070.2023.017 61.
Liang, J., Hu, D., and Feng, J. Do we really need to access the source data? Source hypothesis transfer for unsupervised domain adaptation. In Proceedings of the 37th International Conference on Machine Learning, volume 119, pp. 6028–6039. PMLR, 2020.
Hastie, T., Tibshirani, R., and Friedman, J. The Elements of Statistical Learning. Springer-Verlag, 2001. 10
Black-Box Assisted Regression: Phase Transitions and Minimax Optimality
Liang, J., He, R., and Tan, T. A comprehensive survey on test-time adaptation under distribution shifts. International Journal of Computer Vision, 133(1):31–64, 2025.
Yang, A., Li, A., Yang, B., et al. Qwen3 technical report, 2025. Yang, Y. On the optimal approximation of sobolev and besov functions using deep relu neural networks. Applied and Computational Harmonic Analysis, 79:101797, 2025. doi: 10.1016/j.acha.2025.101797.
Lin, H. and Reimherr, M. Model-robust and adaptiveoptimal transfer learning for tackling concept shifts in nonparametric regression, 2025. Mani, P., Xu, P., Lipton, Z. C., and Oberst, M. No free lunch: Non-asymptotic analysis of prediction-powered inference, 2025.
Yarowsky, D. Unsupervised word sense disambiguation rivaling supervised methods. In 33rd Annual Meeting of the Association for Computational Linguistics, pp. 189– 196, 1995.
Massart, P. Density Estimation via Model Selection, pp. 201–277. Springer Berlin Heidelberg, 2007. doi: 10.100 7/978-3-540-48503-2 7.
Zhang, H., Dauphin, Y. N., and Ma, T. Residual learning without normalization via better initialization. In International Conference on Learning Representations, 2019.
Pan, S. J. and Yang, Q. A survey on transfer learning. IEEE Transactions on Knowledge and Data Engineering, 22 (10):1345–1359, 2010. doi: 10.1109/TKDE.2009.191.
Zrnic, T. and Candès, E. J. Cross-prediction-powered inference, 2024.
Schölkopf, B. and Smola, A. J. Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond. The MIT Press, 2001. Siegel, J. W. Optimal approximation rates for deep ReLU neural networks on sobolev and besov spaces. Journal of Machine Learning Research, 24(357):1–52, 2023. Sohn, K., Berthelot, D., Carlini, N., et al. Fixmatch: Simplifying semi-supervised learning with consistency and confidence. In Advances in Neural Information Processing Systems, volume 33, pp. 596–608, 2020. Stone, C. J. Optimal global rates of convergence for nonparametric regression. The Annals of Statistics, 10(4): 1040–1053, 1982. Tsybakov, A. B. Introduction to Nonparametric Estimation. Springer, 2009. Wang, D., Shelhamer, E., Liu, S., Olshausen, B., and Darrell, T. Tent: Fully test-time adaptation by entropy minimization. In International Conference on Learning Representations, 2021. Wang, Q., Fink, O., Van Gool, L., and Dai, D. Continual testtime domain adaptation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 7201–7211, 2022. Weiss, K., Khoshgoftaar, T. M., and Wang, D. A survey of transfer learning. Journal of Big Data, 3(1):9, 2016. doi: 10.1186/s40537-016-0043-6. Xie, Q., Luong, M.-T., Hovy, E., and Le, Q. V. Selftraining with noisy student improves imagenet classification. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 10687–10698, 2020. 11
Black-Box Assisted Regression: Phase Transitions and Minimax Optimality
A. Extended Related Work Discussion This appendix provides a comprehensive review of related literature organized by theme. A.1. Prediction-Powered Inference and Post-Prediction Inference Prediction-Powered Inference (PPI) provides a principled framework for constructing confidence intervals by combining a small labeled dataset with a large pool of machine predictions, without assuming the predictor is correct (Angelopoulos et al., 2023). Subsequent work has sharpened the computational and statistical properties of this paradigm, including adaptive and more efficient variants (PPI++) (Angelopoulos et al., 2024), cross-fitting style constructions (Zrnic & Candès, 2024), and Bayesian-regularized extensions (Hofer et al., 2024; Cortinovis & Caron, 2025). Recent analyses further expand this scope to stratified evaluations (Fisch et al., 2024), settings with imputed covariates (Kluger et al., 2025), and non-asymptotic limits (Mani et al., 2025). A.2. Transfer Learning, Domain Adaptation, and Black-Box Regimes Classical transfer learning theory typically assumes access to source data, shared representations, or parametric model classes (Cai & Pu, 2024; Lin & Reimherr, 2025). For broader context, we refer to foundational surveys on transfer learning (Pan & Yang, 2010; Weiss et al., 2016). In parallel, hypothesis-transfer and source-free domain adaptation study regimes where source data are inaccessible (Kuzborskij & Orabona, 2013; Liang et al., 2020). Recent few-shot adaptation methods also study continual or class-incremental settings, or perform adaptation in parameter or weight space (Gu et al., 2023; Lee et al., 2025). These are relevant neighboring empirical directions, but they assume an access model different from ours. Our analysis treats the pretrained system as a fixed function-access black box: the learner cannot access source data or model parameters, only predictions. A.3. Pseudo-Labeling, Self-Training, and Test-Time Adaptation A large body of empirical practice combines weak/cheap labels with a small amount of gold supervision, dating back to early work on word sense disambiguation (Yarowsky, 1995). Modern approaches include pseudo-labeling and self-training for deep networks (Lee, 2013; Xie et al., 2020; Sohn et al., 2020). Several works provide theoretical guarantees under distribution or subpopulation shift (Cai et al., 2021; Joo & Klabjan, 2024); our distinction is therefore not the absence of theory in self-training, but the different statistical object: minimax risk for fixed black-box assisted regression and the phase transition induced by the prior error δ. Recent surveys consolidate this area (Amini et al., 2025; Kage et al., 2025). Test-time adaptation (TTA) further explores adjusting models under shift (Liang et al., 2025), with algorithms such as entropy-minimization (Wang et al., 2021) and continual adaptation (Wang et al., 2022). A.4. Noisy-Label Correction Noisy-label correction studies how to learn when the observed labels are corrupted or biased. Our setting is different: the labels are standard noisy regression observations (true signal plus i.i.d. noise), not corrupted or mislabeled; the imperfect object is a fixed black-box predictor f0 . Thus the statistical question is not label-noise correction, but whether and when a black-box prediction can be safely used as a prior. A.5. Model Selection View: Holdout, Cross-Validation, and Oracle Inequalities Our “safe selection” step is a two-model holdout model selection procedure. This connects to the classical cross-validation literature (Arlot & Celisse, 2010) and concentration-based analyses for model selection (Massart, 2007). A.6. Residual Connections and Zero-Initialization in Deep Networks Our residualization principle mirrors the residual learning perspective popularized by ResNets (He et al., 2016). For the specific inductive bias “start exactly at the black-box” (zero-initialization), we note the close relationship to deep residual training without normalization (Zhang et al., 2019). General foundations of deep learning optimization are covered in Goodfellow et al. (2016).
12
Black-Box Assisted Regression: Phase Transitions and Minimax Optimality Table 5. Notation used in the theoretical analysis.
Symbol
Meaning
f0 f∗ r ∗ = f ∗ − f0 r̂ fˆres = f0 + r̂ fˆsafe δ = ∥f ∗ − f0 ∥L2 (PX ) ρ
fixed black-box predictor target regression function target residual learned residual estimator residual-corrected candidate final Safe Residual Estimator output black-box prior error radius validation fraction
A.7. Kernel Ridge Regression and Approximation Theory When the residual is learned by kernel methods, sharp rates are classically studied in Caponnetto & De Vito (2007). For broader statistical learning foundations, see Hastie et al. (2001) and Schölkopf & Smola (2001). Regarding the approximation power of our function classes, recent work establishes optimal rates for deep ReLU networks in Sobolev and Besov spaces (Siegel, 2023; Yang, 2025) and analyzes Transformers as nonparametric learners (Kim et al., 2024). A.8. Datasets and Foundation Models For CIFAR-100, we cite the original technical report (Krizhevsky & Hinton, 2009). For the language model backbones used in our NLP experiments, we utilize the Qwen model family (Bai et al., 2023). Local polynomial methods (Fan, 1996) serve as a canonical nonparametric reference.
B. Notation and Basic Preliminaries This appendix collects notation and basic facts used throughout the proofs in Appendix D. We work under Assumptions 5.1– 5.2 unless stated otherwise. B.1. Notation Data and distributions.
iid
We observe (xi , yi )ni=1 with xi ∼ PX on X = [0, 1]d and iid
yi = f ∗ (xi ) + ϵi ,
ϵi ∼ N (0, σ 2 ),
(15)
independent of xi . Assumption 5.1 states that PX has a density p w.r.t. Lebesgue measure on [0, 1]d satisfying for all x ∈ [0, 1]d .
0 < c ≤ p(x) ≤ C < ∞ Black-box predictor and residual. residual
(16)
The learner has access to a fixed black-box predictor f0 : X → R. We define the r∗ (x) := f ∗ (x) − f0 (x).
∗
∗
(17) ∗
Assumption 5.2 posits r ∈ H(β, L) and ∥r ∥L2 (PX ) ≤ δ, along with uniform boundedness ∥r ∥∞ ≤ B and ∥f0 ∥∞ ≤ B0 . Norms.
For a measurable function g : X → R, define ∥g∥2L2 (PX ) := EX∼PX [g(X)2 ],
∥g∥2L2 :=
Z
g(x)2 dx,
[0,1]d
∥g∥∞ := sup |g(x)|.
(18)
x∈X
When there is no ambiguity, we write ∥g∥2 := ∥g∥L2 (PX ) . Risk.
For an estimator fˆ (measurable w.r.t. the data), the squared L2 (PX ) risk is R(fˆ, f ∗ ) := E ∥fˆ − f ∗ ∥2L2 (PX ) ,
where the expectation is over the sample (xi , yi )ni=1 and any estimator randomness. 13
(19)
Black-Box Assisted Regression: Phase Transitions and Minimax Optimality
Sample splitting. When we split the labeled dataset into a training set Dtr and a validation set Dval of size nval , we write ntr + nval = n and often parameterize nval = ρn with ρ ∈ (0, 1). B.2. Norm Equivalences Under Random Design The density bounds (16) imply that L2 (PX ) and Lebesgue L2 norms are equivalent on [0, 1]d up to constants depending only on (c, C). Lemma B.1 (Equivalence of L2 (PX ) and Lebesgue L2 ). Assume (16). Then for any measurable g : [0, 1]d → R, c ∥g∥2L2 ≤ ∥g∥2L2 (PX ) ≤ C ∥g∥2L2 .
(20)
In particular, ∥g∥L2 (PX ) ≍ ∥g∥L2 with constants depending only on (c, C). Proof. By definition, ∥g∥2L2 (PX ) = R C g(x)2 dx, which is (20).
R
R R g(x)2 p(x) dx. Using c ≤ p(x) ≤ C yields c g(x)2 dx ≤ g(x)2 p(x)dx ≤
B.3. Residual Class and Centering Recall Definition 5.3: F(δ) := f0 + r : r ∈ H(β, L), ∥r∥L2 (PX ) ≤ δ, ∥r∥∞ ≤ B .
(21)
The bounded-error black-box model can be viewed as a localization of the target around f0 in L2 (PX ). Lemma B.2 (Risk equivalence under residualization). For any estimator fˆ and the associated residual estimator r̂ := fˆ−f0 , we have ∥fˆ − f ∗ ∥2L2 (PX ) = ∥r̂ − r∗ ∥2L2 (PX ) , (22) and hence R(fˆ, f ∗ ) = R(r̂, r∗ ). Proof. Since f ∗ = f0 + r∗ and fˆ = f0 + r̂, we have fˆ − f ∗ = r̂ − r∗ pointwise. Taking ∥ · ∥2L2 (PX ) yields the identity, and taking expectation over data yields the equality of risks. B.4. Validation Losses Used by Safe Selection For completeness, we record the empirical validation losses used in Algorithm 1. Given a validation set Dval = {(xi , yi )}i∈Ival , X X 2 2 LBB := yi − f0 (xi ) , LRes := yi − (f0 (xi ) + r̂(xi )) . (23) i∈Ival
i∈Ival
The selection variable is α̂ = 1{LRes < LBB }, yielding the final predictor fˆsafe (x) = f0 (x) + α̂ r̂(x).
C. Geometric Interpretation and Proof Sketch C.1. Geometric Interpretation of the Phase Transition The phase transition phenomenon identified in Theorem 5.4 can be understood geometrically as an intersection of function classes. The learner knows that f ∗ lies in the intersection of the smoothness ball H(β, L) and the proximity ball B(f0 , δ) = {f : ∥f − f0 ∥ ≤ δ}. • Sample Dominated Regime (δ > δc (n)): When the prior is relatively poor, the proximity ball B(f0 , δ) is large and effectively contains the entire uncertainty region of the non-parametric estimator. In this case, the constraint ∥f − f0 ∥ ≤ δ provides little information gain over the smoothness constraint alone. The minimax risk is thus governed 2β by the metric entropy of H(β, L), yielding the standard non-parametric rate n− 2β+d . • Prior Dominated Regime (δ < δc (n)): Conversely, when δ is small, the proximity ball is significantly smaller than the estimation uncertainty of learning from scratch. The intersection H(β, L) ∩ B(f0 , δ) is effectively constrained by the radius δ. In this regime, the local complexity of the function class around f0 is low, and the risk is saturated by the approximation error δ 2 . 14
Black-Box Assisted Regression: Phase Transitions and Minimax Optimality β
The critical radius δc (n) ≍ n− 2β+d represents the boundary where the “resolution” of the available data matches the “quality” of the prior. Intuitively, with n samples, the non-parametric estimator can only resolve features of scale larger than n−1/(2β+d) . If the black-box error δ operates at a finer scale than this resolution limit, the data cannot improve upon the prior. The estimator only begins to improve upon f0 when the sample size is large enough to resolve the fine-grained structure of the residual bias. C.2. Proof Sketch and Intuition While the rigorous proofs are deferred to Appendix D, we provide here the intuition behind the phase transition established in Theorem 5.4. The minimax risk is governed by a trade-off between two sources of error: the approximation error inherited from the black-box and the estimation error associated with learning from finite samples. The Packing Argument. To derive the lower bound, we employ Fano’s method. We construct a “hardest” sub-problem by packing multiple hypotheses into the function class F(δ). These hypotheses are local perturbations of the black-box f0 . Specifically, we define perturbations ψj supported on disjoint hypercubes. The amplitude h of these perturbations is constrained by two factors: 1. Smoothness Constraint: To remain in the Hölder class H(β, L), the amplitude must decay as the grid size decreases: h ≲ m−β . 2. Black-Box Constraint: To satisfy ∥f − f0 ∥ ≤ δ, the aggregate energy of the perturbations cannot exceed δ 2 . This implies h ≲ δ. The interplay between these two constraints creates the phase transition.
D. Detailed Theoretical Analysis In this appendix, we provide complete proofs for Theorems 5.4, 5.5, and 5.7. Throughout, we work under Assumptions 5.1 and 5.2 unless stated otherwise. Appendix B collects notation and basic identities used below. D.1. Technical Preliminaries Hölder class. We use a standard (isotropic) Hölder class definition on X = [0, 1]d . Let β > 0, write s := ⌊β⌋ and Pd |k| α := β − s ∈ [0, 1). For a multi-index k = (k1 , . . . , kd ) ∈ Nd with |k| := j=1 kj , denote ∂ k := k1∂ kd . Define the ∂x1 ···∂xd
Hölder seminorm of order β by |∂ k f (x) − ∂ k f (x′ )| , ∥x − x′ ∥α |k|=s x̸=x′ 2
[f ]H(β) := max sup
(24)
with the convention that when s = 0, the maximum over |k| = 0 is interpreted as [f ]H(β) = supx̸=x′ |f (x) − f (x′ )|/∥x − x′ ∥β2 . Then the (ball) Hölder class H(β, L) consists of functions f such that max|k|≤s ∥∂ k f ∥∞ ≤ L and [f ]H(β) ≤ L. Probability model and the induced distributions. For any measurable regression function g : X → R, let Pg denote the iid
iid
joint law of (X1:n , Y1:n ) under Yi = g(Xi ) + ϵi with Xi ∼ PX and ϵi ∼ N (0, σ 2 ) independent of X1:n . D.1.1. KL DIVERGENCE UNDER RANDOM DESIGN Definition D.1 (Kullback–Leibler divergence). For probability measures P, Q with P ≪ Q, the KL divergence is R dP KL(P ∥Q) := log dQ dP. Lemma D.2 (KL for Gaussian regression with random design). For any measurable g, h : X → R, KL(Pg ∥Ph ) =
n ∥g − h∥2L2 (PX ) . 2σ 2
(25)
Proof. Condition on X1:n . Under Pg , the conditional law of Y1:n given X1:n is N (µg , σ 2 In ) with (µg )i = g(Xi ); similarly 15
Black-Box Assisted Regression: Phase Transitions and Minimax Optimality
under Ph it is N (µh , σ 2 In ) with (µh )i = h(Xi ). Thus, KL(Pg (Y1:n | X1:n ) ∥ Ph (Y1:n | X1:n )) =
n 1 X 1 2 ∥µ − µ ∥ = (g(Xi ) − h(Xi ))2 . g h 2 2σ 2 2σ 2 i=1
Since the X-marginal is the same under Pg and Ph , the chain rule for KL yields KL(Pg ∥Ph ) = EX1:n [KL(Pg (Y1:n | X1:n ) ∥ Ph (Y1:n | X1:n ))] =
n 1 X E (g(Xi ) − h(Xi ))2 . 2 2σ i=1
Using i.i.d. Xi ∼ PX , we get (25). D.1.2. VARSHAMOV–G ILBERT AND FANO Lemma D.3 (Varshamov–Gilbert bound (Tsybakov, 2009)). Let Ω = {0, 1}M with Hamming distance H(·, ·). There exists Ω′ ⊂ Ω such that |Ω′ | ≥ 2M/8 and for all distinct ω, ω ′ ∈ Ω′ , we have H(ω, ω ′ ) ≥ M/8. Lemma D.4 (Fano’s inequality for metric estimation). Let {Pθ : θ ∈ Θ} be a statistical model and let d(·, ·) be a semimetric on Θ. Assume there exist θ1 , . . . , θM ∈ Θ such that 1. (Separation) d(θi , θj ) ≥ 2s for all i ̸= j, 1 2. (Average KL control) M
PM
j=1 KL(Pθj ∥Pθ1 ) ≤ α log M for some α ∈ (0, 1/8).
Then for any estimator θ̂, α log M + log 2 s sup Eθ d(θ̂, θ) ≥ s 1 − ≥ log M 2 θ∈Θ
(26)
whenever log M ≥ 4 log 2. Proof. Let θ be uniformly distributed over {θ1 , . . . , θM } and let I be the random index. For any estimator θ̂, define the induced decoder Iˆ := arg minj∈[M ] d(θ̂, θj ) (break ties arbitrarily). By the separation assumption, the event {Iˆ ̸= I} implies d(θ̂, θ) ≥ s. Thus, E[d(θ̂, θ)] ≥ s P(Iˆ ̸= I). By the standard Fano bound for multi-hypothesis testing (see, e.g., Tsybakov, 2009, Theorem 2.5), P(Iˆ ̸= I) ≥ 1 −
I(θ; D) + log 2 , log M
1 where D denotes the data. Using the mutual information bound I(θ; D) ≤ M gives (26).
PM
j=1 KL(Pθj ∥Pθ1 ) and the KL condition
D.1.3. A CONCENTRATION LEMMA FOR VALIDATION - BASED SELECTION The proof of Theorem 5.7 uses sample splitting: the candidate predictors are trained on Dtr and evaluated on an independent validation set Dval . Conditional on Dtr , the candidates are fixed functions, so we can apply concentration on the validation sample. Lemma D.5 (From validation ERM to oracle inequality: a two-model version). Assume ϵ is sub-Gaussian with parameter σ (Gaussian is a special case) and f ∗ is bounded: ∥f ∗ ∥∞ ≤ M∗ . Let fˆ1 , fˆ2 be two (possibly random) predictors measurable val w.r.t. Dtr . Let Dval = {(Xi , Yi )}ni=1 be independent of Dtr , and define the validation risks L̂(fˆk ) :=
nval 1 X (Yi − fˆk (Xi ))2 , nval i=1
L(fˆk ) := E (Y − fˆk (X))2 | Dtr . 16
Black-Box Assisted Regression: Phase Transitions and Minimax Optimality
Let fˆsel ∈ {fˆ1 , fˆ2 } minimize L̂(·). This two-model selector is denoted fˆsafe in the main text. Assume additionally that, almost surely, ∥fˆ1 ∥∞ ≤ M and ∥fˆ2 ∥∞ ≤ M for some M < ∞. Then there exists a constant C > 0 depending only on (M, M∗ , σ) such that for all δ ′ ∈ (0, 1), with probability at least 1 − δ ′ (over Dval , conditional on Dtr ), ′
log(2/δ ) L(fˆsel ) ≤ min{L(fˆ1 ), L(fˆ2 )} + C . nval
(27)
Proof. Fix Dtr and abbreviate fk := fˆk as deterministic functions. Let ℓk (x, y) := (y − fk (x))2 . Define the centered loss difference ξi := ℓ1 (Xi , Yi ) − ℓ2 (Xi , Yi ) − E ℓ1 (X, Y ) − ℓ2 (X, Y ) , where (X, Y ) is an independent copy from the validation distribution (conditional on Dtr ). By the selection rule, L̂(fsel ) ≤ min{L̂(f1 ), L̂(f2 )}, hence L(fsel ) − min{L(f1 ), L(f2 )} ≤ max L(fk ) − L̂(fk ) + max L̂(fk ) − L(fk ) = 2 max |L̂(fk ) − L(fk )|. k∈{1,2}
k∈{1,2}
k∈{1,2}
It remains to control |L̂(fk ) − L(fk )| for bounded predictors under sub-Gaussian noise. Write Y = f ∗ (X) + ϵ with ϵ sub-Gaussian and ∥f ∗ ∥∞ ≤ M∗ . Then Y is sub-Gaussian up to an additive bounded shift; moreover, for fixed bounded fk , the random variable (Y − fk (X))2 is sub-exponential with parameters depending only on (M, M∗ , σ). A standard Bernstein inequality for sub-exponential variables implies that for each k, P |L̂(fk ) − L(fk )| ≥ t Dtr ≤ 2 exp − c nval min{t2 , t} for a constant c = c(M, M∗ , σ) > 0. Applying a union bound over k ∈ {1, 2} and choosing t ≍ log(2/δ ′ )/nval yields (27). Remark D.6 (About boundedness of candidate predictors). Lemma D.5 assumes ∥fˆk ∥∞ ≤ M . In our setting, ∥f0 ∥∞ ≤ B0 and ∥r∗ ∥∞ ≤ B imply ∥f ∗ ∥∞ ≤ B0 + B. For theoretical guarantees, one may replace any learned residual predictor r̂ by its clipped version clip(r̂, [−B, B]) and correspondingly clip f0 + r̂ into [−(B0 + B), B0 + B]. This clipping does not increase the squared loss conditional on X when Y is generated from a bounded signal plus noise, and it ensures the boundedness condition required for the concentration step. D.2. Proof of Theorem 5.4 (Minimax Lower Bound) We prove the lower bound via a packing construction and Fano’s method, specialized to the localized class F(δ) (Definition 5.3). S TEP 0: R EDUCTION TO RESIDUAL REGRESSION AND CENTERING AT THE ORIGIN By Lemma B.2 (Appendix B), estimating f ∗ is equivalent to estimating r∗ = f ∗ − f0 from residual observations Zi := Yi − f0 (Xi ) = r∗ (Xi ) + ϵi . Moreover, because f0 is fixed and known, translating the model by f0 does not change the noise distribution or the design. Therefore it suffices to lower bound the minimax risk over the residual class Rn (δ) := inf sup E ∥r̂ − r∥2L2 (PX ) . (28) r̂
r∈H(β,L): ∥r∥L2 (PX ) ≤δ, ∥r∥∞ ≤B
We will show Rn (δ) ≳ min{δ 2 , n−2β/(2β+d) }, which implies the theorem. S TEP 1: A LOCALIZED PACKING VIA DISJOINT BUMPS Fix an integer m ≥ 2 to be chosen later and partition [0, 1]d into M := md disjoint cubes {Rj }M j=1 of side length 1/m. Let xj be the center of Rj . Choose a fixed bump K : Rd → R satisfying: (i) supp(K) ⊂ [−1/2, 1/2]d , (ii) K(0) > 0, (iii) K ∈ H(β, 1) as a function R d 2 on R (restricted to its support), and (iv) ∥K∥L2 = Rd K(u)2 du ∈ (0, ∞). (Such functions exist; for example, one may take a smooth compactly supported bump and rescale its Hölder norm.) 17
Black-Box Assisted Regression: Phase Transitions and Minimax Optimality
For amplitude h > 0, define the bumps ψj (x) := h K m(x − xj ) ,
j = 1, . . . , M,
(29)
and for ω ∈ {0, 1}M define the candidate residuals rω (x) :=
M X
ωj ψj (x).
(30)
j=1
By construction, supp(ψj ) ⊂ Rj , so the supports are disjoint across j. S TEP 2: V ERIFY CLASS CONSTRAINTS (a) Hölder constraint. Scaling properties of Hölder norms imply that ψj ∈ H(β, CK hmβ ) for a constant CK depending only on K, β, d. Consequently, using disjoint supports in (30) and the triangle inequality for derivatives on each cube, there exists C1 = C1 (K, β, d) such that rω ∈ H(β, L) (b) L2 (PX ) constraint.
provided that
h≤
L −β m . C1
(31)
By disjoint supports and Lemma B.1 (Appendix B), ∥rω ∥2L2 (PX ) =
M X
ωj ∥ψj ∥2L2 (PX ) ≤
j=1
M X
∥ψj ∥2L2 (PX ) ≤ C
j=1
M X
∥ψj ∥2L2 .
j=1
A change of variables u = m(x − xj ) gives ∥ψj ∥2L2 = h2 m−d ∥K∥2L2 , hence ∥rω ∥2L2 (PX ) ≤ C M h2 m−d ∥K∥2L2 = C h2 ∥K∥2L2 . Therefore, there exists C2 = C2 (K, c, C) such that ∥rω ∥L2 (PX ) ≤ δ
provided that
h≤
δ . C2
(32)
(c) ∥ · ∥∞ constraint. Since ∥ψj ∥∞ ≤ h∥K∥∞ , we have ∥rω ∥∞ ≤ h∥K∥∞ . Thus h ≤ B/∥K∥∞ ensures ∥rω ∥∞ ≤ B. Choice of amplitude.
Combine (31) and (32) (and the ∥ · ∥∞ bound) by taking h := κ · min Lm−β , δ ,
(33)
for a sufficiently small constant κ = κ(K, β, d, c, C, B) ∈ (0, 1). S TEP 3: S EPARATION VIA VARSHAMOV–G ILBERT By Lemma D.3, there exists Ω ⊂ {0, 1}M with |Ω| ≥ 2M/8 such that for all distinct ω, ω ′ ∈ Ω, H(ω, ω ′ ) ≥ M/8. Using disjoint supports and Lemma B.1, ∥rω − r
ω′
∥2L2 (PX ) =
M X
(ωj − ωj′ )2 ∥ψj ∥2L2 (PX ) ≥
j=1
M M min ∥ψj ∥2L2 (PX ) ≥ c ∥ψ1 ∥2L2 . 8 j 8
Since ∥ψ1 ∥2L2 = h2 m−d ∥K∥2L2 and M = md , we conclude that ∥rω − rω′ ∥2L2 (PX ) ≥ c0 h2 for some constant c0 = c0 (K, c) > 0. 18
(34)
Black-Box Assisted Regression: Phase Transitions and Minimax Optimality
S TEP 4: KL CONTROL For ω, ω ′ ∈ Ω, by Lemma D.2, KL(Prω ∥Prω′ ) =
n n nh2 2 2 ′∥ ′∥ ∥r − r ≤ max , ∥r − r ≤ C ω ω ω ω 3 L2 (PX ) L2 (PX ) 2σ 2 2σ 2 ω̸=ω′ σ2
(35)
where C3 is a constant depending only on (K, C). S TEP 5: A PPLY FANO AND OPTIMIZE OVER m √ Let d(·, ·) be the semimetric d(r, r′ ) := ∥r − r′ ∥L2 (PX ) . By (34), the packing is separated by 2s with s := 21 c0 h. Moreover, choosing m so that the average KL satisfies the Fano condition in Lemma D.4, namely C3
nh2 ≤ α log |Ω| σ2
with
log |Ω| ≥
hence
inf
M log 2, 8
(36)
implies (for a sufficiently small absolute α) that inf r̂
sup
E∥r̂ − r∥L2 (PX ) ≳ h,
r∈{rω :ω∈Ω}
r̂
sup r∈{rω :ω∈Ω}
E∥r̂ − r∥2L2 (PX ) ≳ h2 .
It remains to choose m to maximize h2 subject to (33) and (36). Case 1: sample-dominated regime. Suppose δ ≥ c n−β/(2β+d) (for a small constant c depending on fixed parameters). Choose m ≍ n1/(2β+d) and h ≍ Lm−β ≍ n−β/(2β+d) . Then M = md ≍ nd/(2β+d) and nh2 ≍ nd/(2β+d) ≍ M , so (36) holds for a suitable choice of constants. Thus the minimax risk is lower bounded by h2 ≍ n−2β/(2β+d) . Case 2: black-box-dominated regime. Suppose δ ≤ c n−β/(2β+d) . Set h ≍ δ (consistent with (33)), and choose m to satisfy the KL/Fano feasibility: from (35) and log |Ω| ≍ M = md , it suffices to take md ≳ nδ 2 , i.e. m ≳ (nδ 2 )1/d . On the other hand, the Hölder constraint requires h ≲ Lm−β , i.e. m ≲ (L/δ)1/β . Feasibility of both bounds is equivalent (up to constants) to (nδ 2 )1/d ≲ (L/δ)1/β , which rearranges to δ ≲ n−β/(2β+d) (absorbing fixed constants into c), exactly the present case. Therefore we can pick such an m and conclude the risk lower bound is h2 ≍ δ 2 . Combining the two cases yields n o Rn (δ) ≳ min δ 2 , n−2β/(2β+d) , which proves Theorem 5.4. D.3. Proof of Theorem 5.5 (Upper Bound) We construct an estimator that adaptively achieves the minimum of the black-box error floor δ 2 and the optimal nonparametric rate for learning the residual. S TEP 1: C ANDIDATE ESTIMATORS Split the labeled sample into Dtr and Dval with nval ≍ n. Consider two candidates: fˆBB (x) := f0 (x),
fˆRes (x) := f0 (x) + r̂(x),
where r̂ is trained on Dtr using the residual responses Zi = Yi − f0 (Xi ). S TEP 2: R ISK OF THE BLACK - BOX CANDIDATE By Definition 5.3 (and Lemma B.2), for any f ∗ = f0 + r∗ ∈ F(δ), R(fˆBB , f ∗ ) = E∥f0 − f ∗ ∥2L2 (PX ) = ∥r∗ ∥2L2 (PX ) ≤ δ 2 . 19
(37)
Black-Box Assisted Regression: Phase Transitions and Minimax Optimality
S TEP 3: R ISK OF A MINIMAX - OPTIMAL RESIDUAL REGRESSOR It remains to upper bound the minimax risk for estimating r∗ in H(β, L) under random design with sub-Gaussian noise. A classical result (Stone’s theorem and subsequent refinements) ensures the existence of estimators attaining the optimal rate. Lemma D.7 (Existence of a minimax-optimal estimator for Hölder regression). Under Assumption 5.1, for the regression model Zi = r(Xi ) + ϵi with ϵi ∼ N (0, σ 2 ), there exists an estimator r̂ (measurable w.r.t. Dtr ) such that sup r∈H(β,L): ∥r∥∞ ≤B
− 2β E ∥r̂ − r∥2L2 (PX ) ≤ Cup ntr 2β+d ,
(38)
where Cup depends only on (β, L, d, σ, c, C, B). Proof sketch with precise dependency. This is a standard nonparametric regression upper bound for Hölder smoothness under random design with density bounded away from 0 and ∞. One may take, for example, a local polynomial estimator of degree ⌊β⌋ or an appropriately chosen series/wavelet estimator, which attains the minimax rate n−2β/(2β+d) in L2 (PX ) risk; see, e.g., (Tsybakov, 2009, Chapter 2) and the classical optimality result of (Stone, 1982). The constants depend on (β, L, d, σ) and on the density bounds (c, C) through norm equivalences (Lemma B.1). Applying Lemma D.7 to r∗ yields −
2β
sup R(fˆRes , f ∗ ) = sup E∥r̂ − r∗ ∥2L2 (PX ) ≤ Cup ntr 2β+d .
f ∗ ∈F (δ)
(39)
r∗
S TEP 4: VALIDATION SELECTION AND CONCLUSION Define fˆsafe as the validation-selected predictor between fˆBB and fˆRes , as in Algorithm 1. By Lemma D.5 (applied conditionally on Dtr ), with probability at least 1 − δ ′ over Dval , L(fˆsafe ) ≤ min{L(fˆBB ), L(fˆRes )} + C
log(2/δ ′ ) , nval
for C depending only on (B0 , B, σ) (via boundedness and sub-Gaussianity). Taking expectations and using (37) and (39) gives n o − 2β 1 sup R(fˆsafe , f ∗ ) ≤ C ′ min δ 2 , ntr 2β+d + C ′′ , nval f ∗ ∈F (δ) where we fixed δ ′ as a constant (e.g., δ ′ = 1/4) to absorb log(2/δ ′ ) into C ′′ , and used ntr ≍ n and nval ≍ n. This yields the claimed bound in Theorem 5.5 (up to constant-factor changes). D.4. Proof of Corollary 5.6 The proof follows directly from the risk decomposition and the sample splitting construction. Algorithm 1 constructs two candidates: fˆBB = f0 and fˆRes = f0 + r̂, where r̂ is trained on Dtr with sample size ntr = (1 − ρ)n. From Theorem 5.5 (specifically the oracle inequality argument in its proof), the risk of the validation-selected estimator fˆsafe satisfies: − 2β C′ sup E∥fˆsafe − f ∗ ∥2L2 (PX ) ≤ C · min δ 2 , ntr 2β+d + . (40) nval f ∗ ∈F (δ) Substituting ntr = (1 − ρ)n into the estimation error term: −
2β
2β
2β
2β
ntr 2β+d = ((1 − ρ)n)− 2β+d = (1 − ρ)− 2β+d · n− 2β+d .
(41) 2β
The additive selection cost term is C ′ /nval = C ′ /(ρn) = O(n−1 ). Since the nonparametric rate n− 2β+d is asymptotically slower than n−1 (for any finite d ≥ 1), the O(n−1 ) term is lower order, although it remains an explicit finite-sample validation-selection cost. 20
Black-Box Assisted Regression: Phase Transitions and Minimax Optimality
Thus, we obtain: o n 2β 2β sup E∥fˆsafe − f ∗ ∥2 ≤ (1 − ρ)− 2β+d · C min δ 2 , n− 2β+d + Õ(n−1 ).
(42)
f ∗ ∈F (δ)
For the specific case of ρ = 0.2 and β ≈ d (e.g., d = 1, β = 1), the exponent is −2/3. The inflation factor is (0.8)−2/3 ≈ 1.16. Generally, for β, d > 0, this factor is a constant independent of n. This confirms that Algorithm 1 is minimax-optimal up to the validation-selection cost and a constant factor from sample splitting. D.5. Proof of Theorem 5.7 (Oracle Inequality for Safe Selection) Theorem 5.7 is a direct application of Lemma D.5 with fˆ1 = fˆBB = f0 and fˆ2 = fˆRes = f0 + r̂. Indeed, conditional on Dtr , both candidates are fixed functions, and the validation set is independent. The boundedness assumptions needed for Lemma D.5 are satisfied by ∥f0 ∥∞ ≤ B0 and by clipping f0 + r̂ into [−(B0 + B), B0 + B] if necessary (Remark following Lemma D.5). Therefore, for any δ ′ ∈ (0, 1), with probability at least 1 − δ ′ , R(fˆsafe ) ≤ (1 + γ) min{R(fˆBB ), R(fˆRes )} + C
log(2/δ ′ ) , nval
for constants (γ, C) depending only on boundedness and the sub-Gaussian noise parameter. This is exactly the statement of Theorem 5.7 (up to renaming constants). D.6. The Price of Safety: Sample Splitting Cost Here we justify the inflation factor discussed in Section 5.5. In the sample-dominated regime, the residual estimation error is −2β/(2β+d) of order ntr . With ntr = (1 − ρ)n, we have −
2β
ntr 2β+d = (1 − ρ)n
2β − 2β+d
2β
2β
= (1 − ρ)− 2β+d n− 2β+d .
Thus the sole effect of sample splitting on the main nonparametric term is a multiplicative constant (1 − ρ)−2β/(2β+d) . In addition, the oracle inequality contributes an additive selection penalty of order O(1/nval ) = O(1/(ρn)), which is asymptotically negligible compared to n−2β/(2β+d) whenever 2β/(2β + d) < 1 (i.e., for any finite d and β > 0).
E. Theoretical Novelty and Comparison to Classical Localization E.1. Comparison to Classical Localized Minimax Analysis Standard non-parametric regression typically considers the minimax risk over a global Hölder ball H(β, L). The classical 2β minimax rate is known to be n− 2β+d (Stone, 1982; Tsybakov, 2009). Our work introduces a novel twist by considering the intersection of the Hölder ball with an L2 -neighborhood of a fixed predictor f0 : F(δ) = H(β, L) ∩ {f : ∥f − f0 ∥L2 ≤ δ}. This formulation fundamentally alters the metric entropy of the hypothesis class. β
• Classical Regime: When δ is large (specifically δ > n− 2β+d ), the L2 constraint is inactive. The covering number log N (ϵ, F(δ)) behaves like ϵ−d/β , recovering the standard rate. • Black-Box Regime: When δ is small, the geometry of F(δ) is dominated by the L2 ball. The local entropy integral is truncated, leading to a parametric-like rate limited by δ 2 . While localized analysis (e.g., local Rademacher complexity) deals with adaptivity to the target function’s local smoothness, our analysis characterizes adaptivity to the prior’s quality. The phase transition at δc (n) is the precise mathematical boundary where the ”information content” of the samples n supersedes the ”information content” of the prior constraint δ. 21
Black-Box Assisted Regression: Phase Transitions and Minimax Optimality
F. Implementation Details for Reproducibility To ensure full reproducibility, we provide the specific hyperparameters and architectures used in our experiments. 1. Synthetic Experiments (KRR) • Model: Kernel Ridge Regression with RBF kernel k(x, x′ ) = exp(−γ∥x − x′ ∥2 ). • Hyperparameters: – Regularization α: Grid search over {10−4 , 10−3 , 10−2 , 10−1 }. – Kernel Gamma γ: Grid search over {1, 5, 10, 20}. • Selection: 5-fold cross-validation on the training split. 2. Vision Experiments (ResNet/MLP) • Backbone: CLIP (ViT-B/32) frozen image encoder. • Residual Head Architecture: – Input: 512-dim CLIP features. – Hidden: Linear(512, 512) → ReLU → Dropout(0.3). – Output: Linear(512, NumClasses). • Optimization: AdamW optimizer, Learning rate 10−3 , Weight decay 10−4 . • Training: Batch size 32 (for n < 1000) or 64. Early stopping with patience=10 on validation accuracy. • Zero-Initialization: The weights and biases of the final output layer are explicitly set to 0.0 at initialization. 3. NLP Experiments (Qwen) • Backbone: Qwen3-8B (frozen). • Feature Extraction: Last token hidden state from the last layer. • Head Architecture: Same MLP structure as Vision. • Prompt for f0 : ”Classify the article into one of: {labels}. Article: {text} Category:” F.1. Computational Complexity Analysis A potential concern with two-stage methods is computational overhead. We clarify that Algorithm 1 incurs negligible cost compared to standard baselines: • Training Cost: The residual model r̂ has the same architecture and training complexity as learning from scratch. The black-box f0 is frozen and only requires a one-time forward pass to cache features/logits. • Selection Cost: The safe selection step requires only one forward pass on the validation set to compute two scalars: LBB and LRes . This is O(nval ). • Comparison with Weighted Ensemble: The W GT(Val-Tuned) baseline requires a grid search over α ∈ [0, 1] to minimize validation error. Our method requires no hyperparameter search for the combination mechanism, making it computationally cheaper and more stable than the ensemble baseline.
G. Ablation Studies We conduct additional ablation studies to verify the sensitivity of our method to the validation split ratio ρ and the impact of zero-initialization. 22
Black-Box Assisted Regression: Phase Transitions and Minimax Optimality
G.1. Sensitivity to Validation Fraction ρ We investigate the impact of the validation split ratio ρ = nval /n on the final performance using the 1D synthetic dataset (n = 200, δ = 0.2). As shown in Figure 3a, the risk is stable for ρ ∈ [0.15, 0.3]. • When ρ is too small (< 0.1), the validation set is insufficient to reliably estimate the risk, leading to noisy selection. • When ρ is too large (> 0.5), the training set becomes too small to learn the residual effectively. Our choice of ρ = 0.2 in the main experiments strikes an optimal balance. G.2. Effect of Zero-Initialization We compare our zero-initialization strategy against standard random initialization (Kaiming Uniform) on CIFAR-100 (n = 500). Figure 3b tracks the L2 norm of the residual head’s weights during training. • Random Init: The residual norm starts large, causing the initial predictor fˆ = f0 + r̂ to deviate significantly from the black-box f0 . This high initial variance increases the risk of early overfitting and negative transfer. • Zero Init (Ours): The norm starts at 0 and grows gradually. This acts as a strong inductive bias, ensuring the model starts exactly at the black-box prior and only deviates when the data provides sufficient evidence. This leads to a lower final test error (Accuracy: 61.0% vs. 58.2% for Random Init).
(b) Residual head norm ∥r̂∥2 during training.
(a) Validation fraction ρ and MSE risk.
Figure 3. Ablation studies. Left: the validation split is stable for ρ ∈ [0.15, 0.3]. Right: zero-initialization ensures a smooth departure from the prior f0 .
23