Technical Summary: Black-Box Assisted Regression: Phase Transitions and Minimax Optimality

1. Problem Formulation

The paper addresses Black-Box Assisted Non-Parametric Regression, a setting where a learner possesses a small labeled dataset $\mathcal{D}_n = \{(x_i, y_i)\}_{i=1}^n$ from a target distribution but lacks access to the source data, model parameters, or the ability to fine-tune a pre-trained foundation model. Instead, the learner can only query a fixed black-box predictor $f_0: \mathcal{X} \to \mathbb{R}$.

The core statistical challenge is that the error of $f_0$ on the target distribution is unknown. The target regression function $f^*$ is assumed to satisfy:
$$\|f^* - f_0\|_{L^2(P_X)} \le \delta$$
where $\delta \ge 0$ is an unknown prior error radius. The goal is to construct an estimator $\hat{f}$ that minimizes the Mean Squared Error (MSE) risk $R(\hat{f}, f^*) = \mathbb{E}[\|\hat{f} - f^*\|_{L^2(P_X)}^2]$ while guaranteeing no negative transfer—meaning the final predictor should not perform significantly worse than using $f_0$ alone, even if $f_0$ is highly biased or the labeled data is scarce.

2. Methodology: The Safe Residual Estimator

The authors propose a Safe Residual Estimator that decomposes the learning task into estimating a residual correction around the fixed prior. The method operates on the decomposition $f^*(x) = f_0(x) + r^*(x)$, where $r^*$ is the unknown residual.

The procedure follows a Select-and-Estimate strategy using sample splitting:

1. Data Splitting: The labeled data is split into a training set $\mathcal{D}_{tr}$ and a validation set $\mathcal{D}_{val}$.
2. Residual Learning: A residual model $\hat{r}$ is trained on $\mathcal{D}_{tr}$ to minimize the squared error of the residuals $y - f_0(x)$.
   • Key Implementation Detail: For neural network implementations, the residual head is zero-initialized. This ensures that at the start of training, $\hat{r} \equiv 0$, and the predictor is exactly $f_0$. The model only deviates from the prior when the data provides a strong signal.
3. Safe Selection: The algorithm evaluates two candidates on the held-out validation set $\mathcal{D}_{val}$:
   • Candidate A: The black-box prior $f_0$.
   • Candidate B: The corrected predictor $f_0 + \hat{r}$.
   • The final estimator $\hat{f}_{safe}$ selects the candidate with the lower validation loss:
     $$\hat{f}_{safe}(x) = f_0(x) + \hat{\alpha} \cdot \hat{r}(x), \quad \text{where } \hat{\alpha} = \mathbb{I}[L_{val}(f_0 + \hat{r}) < L_{val}(f_0)]$$

This binary selection mechanism is designed to prevent negative transfer. If the learned correction is not supported by the validation data (e.g., due to noise or high dimensionality), the estimator reverts to $f_0$.

3. Key Contributions and Theoretical Results

A. Minimax Lower Bounds and Phase Transitions

The paper establishes a finite-sample minimax lower bound for this problem. Theorem 5.4 proves that the leading risk term is governed by the minimum of two quantities:
$$\text{Risk} \gtrsim \min\left( \delta^2, \, n^{-\frac{2\beta}{2\beta+d}} \right)$$
where $\beta$ is the smoothness parameter of the residual class (Hölder class) and $d$ is the input dimension.

This result identifies a critical phase transition at a threshold $\delta_c(n) \asymp n^{-\frac{\beta}{2\beta+d}}$:

• Prior-Dominated Regime ($\delta \ll \delta_c(n)$): The black-box error is small. The optimal risk is bounded by the irreducible bias $\delta^2$. Learning from data cannot improve upon the prior significantly.
• Sample-Dominated Regime ($\delta \gg \delta_c(n)$): The black-box is biased. The optimal risk follows the standard non-parametric rate $n^{-\frac{2\beta}{2\beta+d}}$, as the data must drive the correction.

B. Optimality of the Safe Residual Estimator

The authors prove (Theorem 5.5 and Corollary 5.6) that the Safe Residual Estimator achieves this minimax lower bound up to:

1. An additive validation-selection cost of order $O(1/n)$.
2. A constant inflation factor $(1-\rho)^{-\frac{2\beta}{2\beta+d}}$ due to sample splitting (where $\rho$ is the validation fraction).

Crucially, the estimator satisfies an Oracle Inequality (Theorem 5.7):
$$\text{Err}(\hat{f}_{safe}) \le (1+\gamma) \min\left( \text{Err}(f_0), \text{Err}(f_0 + \hat{r}) \right) + \frac{C \log(1/\delta')}{n_{val}}$$
This formalizes the "safety" guarantee: the selected predictor performs almost as well as the better of the two candidates, ensuring no negative transfer relative to the black-box prior (except for the finite-sample validation cost).

C. Geometric Advantage over Linear Ensembling

The paper argues that linear ensembling (weighted combinations of $f_0$ and a scratch estimator) is geometrically limited. Such ensembles are constrained to the affine line segment between the prior and the scratch estimator. In contrast, the residual estimator searches within a ball centered at $f_0$ in the function space. This allows the residual method to capture high-frequency corrections orthogonal to the direction of the scratch estimator, which linear ensembles cannot access.

4. Experimental Results

Synthetic Regression

Experiments on 1D and high-dimensional ($d=20$) synthetic data verify the theoretical phase transition:

• Negative Transfer Prevention: In regimes where the black-box is perfect ($\delta=0$) but data is noisy, the "Raw Residual" (always using $f_0 + \hat{r}$) suffers from overfitting. The Safe Residual successfully reverts to $f_0$ (fallback rate > 60%), reducing risk significantly.
• High-Dimensional Robustness: In high dimensions with limited samples, "Scratch" estimators suffer from the curse of dimensionality. The Safe Residual estimator adapts, falling back to the black-box when the residual cannot be reliably learned, maintaining stability where other methods fail.

Real-World Classification (Vision & NLP)

While the theoretical guarantees are for squared-loss regression, the authors test the mechanism on classification tasks:

• CIFAR-100 (CLIP): The Safe Residual method consistently outperforms zero-shot baselines, scratch training, and validation-tuned weighted ensembles. Notably, at low sample sizes ($n=200$), weighted ensembles collapse due to validation noise, while the Safe Residual method remains robust.
• AG News (Qwen3-8B): In ultra-low sample regimes ($n=16$), the method achieves 75.2% accuracy, outperforming the black-box baseline (74.1%) and significantly beating weighted ensembles (71.2%) which suffer from negative transfer.

5. Significance and Claims

The paper claims to provide the first finite-sample minimax characterization of the tradeoff between prior quality and sample complexity in black-box assisted regression. Its significance lies in:

1. Theoretical Rigor: Identifying the precise phase transition $\delta_c(n)$ and proving that a simple, safe selection strategy achieves the minimax optimal rate.
2. Safety Guarantee: Formalizing "no negative transfer" via an oracle inequality, ensuring that leveraging a foundation model does not degrade performance below the baseline of using the model alone.
3. Practical Mechanism: Demonstrating that zero-initialization combined with holdout selection provides a robust, computationally efficient alternative to complex transfer learning or fine-tuning, particularly in few-shot and high-dimensional settings.

The authors explicitly state that their formal guarantees apply to squared-loss regression under random design assumptions. The classification experiments are presented as evidence that the qualitative tradeoff between prior quality and correction complexity extends to practical settings, rather than as a proof of minimax rates for cross-entropy loss.