Introduction
In modern machine learning, the ability to fine-tune pre-trained models on specific target domains is often hampered by significant real-world constraints. Privacy regulations may prevent users from sharing sensitive data, while intellectual property concerns might stop model providers from distributing raw weights for local tuning. Furthermore, many real-world signals are "restrictive"—they arrive as simple scalar scores (e.g., a user rating or a binary success/fail) rather than differentiable loss functions.
The EXPECTED Problem
The authors formalize this challenge as the EXPECTED framework: Earning eXtra PerformancE from Constrained Target Evaluation and Data. In this setting, the optimizer has no access to target features ($\mathcal{X}$) or labels ($\mathcal{Y}$). Instead, it must update model parameters ($\theta$) using a limited query budget ($Q$), where each query returns only a performance score ($s$).
As shown in the comparison above, EXPECTED represents a more restrictive regime than even unsupervised tuning or federated learning, as it operates without any direct observation of the data distribution.
Methodology
To navigate this "blind" optimization landscape, the paper introduces two key algorithmic strategies.
Performance-guided Parameter Search (PPS)
PPS treats the tuning process as a derivative-free optimization problem using a Natural Evolution Strategy (NES). Since gradients cannot be computed via backpropagation, PPS samples random perturbations ($\epsilon$) in the parameter space. By evaluating the model's performance on these perturbed versions, the algorithm estimates a gradient direction. To ensure stability and efficiency, the authors utilize antithetic sampling (evaluating both $+\epsilon$ and $-\epsilon$) and normalize the resulting feedback.
The visualization above demonstrates how PPS successfully adapts a decision boundary from a source distribution to a target distribution using only 80 queries, effectively "earning" performance without seeing the target data points.
Layerwise Coordinate Parameter Search (LCPS)
While PPS works for smaller models, the high dimensionality of modern Deep Neural Networks (DNNs) makes global parameter search inefficient. LCPS addresses this by framing layer selection as a Multi-Armed Bandit (MAB) problem. The algorithm first explores by allocating small query budgets to different layers to identify which ones are most sensitive to the target task. It then exploits this knowledge by concentrating the remaining budget on the most impactful layers. This prioritization is crucial, as different tasks (e.g., image corruption vs. linguistic shift) often require updates to different parts of the network.
Experimental Evaluation and Results
The framework was tested across diverse modalities, including tabular data (Adult), text (Amazon Reviews, STS-B), and images (CIFAR-10/100-C).
- Efficiency: LCPS significantly outperformed standard PPS. On CIFAR-10-C, LCPS reached a 13.8% error rate with 1,000 queries, whereas PPS required 3,000 queries to achieve only 15.1%.
- Versatility: The method proved capable of optimizing for complex objectives, such as balancing accuracy and fairness (demographic parity) simultaneously.
- Robustness: Surprisingly, the algorithms remained effective even when feedback precision was low (e.g., accuracy rounded to two decimal places), which provides an additional layer of privacy protection.
Key Insights
A major takeaway is that scalar feedback, while seemingly sparse, contains enough signal to project a true gradient onto a lower-dimensional subspace. Furthermore, LCPS occasionally outperformed "white-box" unsupervised methods like Tent. This suggests that even a small amount of label-informed scalar feedback can be more valuable than full access to unlabeled features when adapting to new domains.
Conclusion
The EXPECTED framework provides a robust path forward for model adaptation in privacy-sensitive and IP-restricted environments. By intelligently estimating gradients from scores and prioritizing neural layers, it demonstrates that models can continue to learn and improve even when the data itself remains entirely out of sight.
Summary updated