Earning Extra Performance From Restrictive Feedbacks

Jing Li, Yuangang Pan, Yueming Lyu, Yinghua Yao, Yulei Sui, Ivor W. Tsang

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$).

Comparison of EXPECTED with traditional learning paradigms.

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.

Visualizing model adaptation from source to target using PPS.

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

Abstract

Many machine learning applications encounter a situation where model providers are required to further refine the previously trained model so as to gratify the specific need of local users. This problem is reduced to the standard model tuning paradigm if the target data is permissibly fed to the model. However, it is rather difficult in a wide range of practical cases where target data is not shared with model providers but commonly some evaluations about the model are accessible. In this paper, we formally set up a challenge named \emph{Earning eXtra PerformancE from restriCTive feEDdbacks} (EXPECTED) to describe this form of model tuning problems. Concretely, EXPECTED admits a model provider to access the operational performance of the candidate model multiple times via feedback from a local user (or a group of users). The goal of the model provider is to eventually deliver a satisfactory model to the local user(s) by utilizing the feedbacks. Unlike existing model tuning methods where the target data is always ready for calculating model gradients, the model providers in EXPECTED only see some feedbacks which could be as simple as scalars, such as inference accuracy or usage rate. To enable tuning in this restrictive circumstance, we propose to characterize the geometry of the model performance with regard to model parameters through exploring the parameters' distribution. In particular, for the deep models whose parameters distribute across multiple layers, a more query-efficient algorithm is further tailor-designed that conducts layerwise tuning with more attention to those layers which pay off better. Extensive experiments on different applications demonstrate that our work forges a sound solution to the EXPECTED problem. Code is available via https://github.com/kylejingli/EXPECTED.
BibTeX
@article{li2023earning,
  author = {Jing Li and Yuangang Pan and Yueming Lyu and Yinghua Yao and Yulei Sui and Ivor W. Tsang},
  title = {{Earning Extra Performance From Restrictive Feedbacks}},
  journal = {IEEE Trans. Pattern Anal. Mach. Intell.},
  year = {2023},
  doi = {10.1109/tpami.2023.3273249},
}
Figure