# Robust Adaptation of Foundation Models with Black-Box Visual Prompting

Changdae Oh, Gyeongdeok Seo,
Geunyoung Jung, Zhi-Qi Cheng, Hosik Choi, Jiyoung Jung, and Kyungwoo Song C.
Oh is with Department of Computer Sciences, University of Wisconsin-Madison,
Madison, WI 53706, USA. E-mail<EMAIL_ADDRESS>Jung and J. Jung are
with Department of Artificial Intelligence and H. Choi is with Department of
Urban Big Data Convergence, University of Seoul, Seoul, Dongdaemun-gu 02504,
South Korea. E-mail<EMAIL_ADDRESS>Seo and K.
Song are with Department of Statistics and Data Science, Yonsei University,
Seoul, Seodaemun-gu 03722, South Korea. E-mail:
<EMAIL_ADDRESS>Cheng is with Language Technologies
Institution, Carnegie Mellon University, Pittsburgh, PA 15289, USA. E-mail:
<EMAIL_ADDRESS>
###### Abstract

With the surge of large-scale pre-trained models (PTMs), adapting these models
to numerous downstream tasks becomes a crucial problem. Consequently,
parameter-efficient transfer learning (PETL) of large models has grasped huge
attention. While PETL methods show impressive performance, they commonly rely
on two optimistic assumptions: 1) the entire parameters of a PTM are
available, and 2) a sufficiently large memory capacity is equipped for caching
all the intermediate activations to compute gradients. However, in most real-
world applications, PTMs are served as black-box APIs or proprietary software
without explicit parameter accessibility. Besides, it is hard to meet a large
memory requirement for modern PTMs. This work proposes black-box visual
prompting (BlackVIP), which efficiently adapts the PTMs without knowledge
about model architectures and parameters. BlackVIP has two components; 1)
Coordinator and 2) simultaneous perturbation stochastic approximation with
gradient correction (SPSA-GC). The Coordinator designs input-dependent visual
prompts, which allow the target PTM to adapt in the wild. SPSA-GC efficiently
estimates the gradient of PTM to update the Coordinator. Besides, we propose a
variant, BlackVIP-SE, which significantly reduces the runtime and
computational cost of BlackVIP. Extensive experiments on 19 datasets
demonstrate that BlackVIPs enable robust adaptation to diverse domains and
tasks with minimal memory requirements. We further provide theoretical
analysis on the generalization of visual prompting methods by presenting their
connection to the certified robustness of randomized smoothing.

###### Index Terms:

Transfer Learning, Black-Box Optimization, Parameter-Efficient Fine-Tuning,
Visual Prompting

##  I Introduction

Based on their excellent transferability, large-scale pre-trained models
(PTMs), a.k.a. foundation models [1, 2], have shown remarkable success on
tasks from diverse domains and absorbed increasing attention in machine
learning communities. By witnessing PTMs’ success, Parameter-Efficient
Transfer Learning (PETL) methods that efficiently utilize the PTMs are
recently emerging. While the standard fine-tuning (FT) updates the entire or
large portion of parameters from a PTM, PETL methods aim to achieve comparable
performance to FT by adapting a tiny amount of learnable parameters. Among
them, prompt-based approaches [3, 4, 5, 6] have been widely investigated on
diverse research areas. For PTMs in the vision domain, Visual Prompt Tuning
[4] is a representative example that injects a few learnable prompt tokens
inside of Vision Transformer’s [7] layers and only optimizes them. Besides,
text encoder-side prompt learning methods for the vision-language models are
also actively studied [8, 9, 10, 11]. Different from the aforementioned
approaches, Bahng et al. [5] initiate an investigation of visual prompting
(VP), which attempts to learn the parameters on input pixel space as a visual
prompt to steer the target PTM’s behavior while the PTM itself is totally
intact.

Figure 1:  While FT updates the entire model, VP adapts a few parameters (that
of visual prompt) in the input pixel space. However, VP still requires a large
memory capacity to optimize the prompt via backpropagation. Moreover, FT and
VP are only feasible if the PTM’s parameters are accessible to the public.
Meanwhile, BlackVIP does not assume such accessibility by adopting a black-box
optimization (SPSA-GC) rather than backpropagating a true gradient. Besides,
BlackVIP reparameterizes the prompt with a neural network for input-dependent
prompt generation. Based on these, BlackVIP can be widely adopted for transfer
learning in the wild.

While existing PETL methods show impressive performance with few learnable
parameters, they rely on two optimistic assumptions. First, they assume that
the full parameters of the PTM are accessible. Second, they require a large
memory capacity to cache all the intermediate activations for the gradient
computation. However, PTMs in real-world applications are commonly served as
black-box APIs and proprietary software, and they do not reveal the
implementation-level information or full parameters due to commercial issues,
e.g., violating model ownership. As a result, exploiting high-performing PTMs
to specific downstream tasks not only in the white-box setting but also in the
black-box setting (where we have limited accessibility to the model’s detail)
is a crucial but unexplored problem. Furthermore, while PETL approaches have
few learnable parameters, they require a large amount of memory for caching
the intermediate activations to backpropagate the gradient. Therefore, users
who want to adopt a large-scale PTM should retain sufficient memory capacity
despite the tiny amount of learnable parameters. Besides, if the users entrust
PTM fine-tuning to the model owner by sending their personal data, privacy
concerns will inevitably arise [12].

To alleviate the above unrealistic assumptions, we pioneer black-box visual
prompting (BlackVIP) approach, which enables the parameter-efficient transfer
learning of pre-trained black-box vision models from the low-resource user
perspective (illustrated in Figure 1). BlackVIP works based on the following
two core components: 1) input-dependent visual prompting and 2) a stable
zeroth-order optimization algorithm.

First, we enhance an input image by attaching a learnable visual prompt per
pixel. It is noted that input space prompting does not require the
accessibility on parts of architecture [6, 11] or the embedding layer [9, 10,
8] of PTM. While the previous work [5] manually determines a structure of the
visual prompt, e.g., a small fraction of the fixed area in the image, we
reparameterize the visual prompt with a small prompt generation network,
Coordinator, that receives the original image and produces a corresponding
visual prompt for each individual image. As a result, the Coordinator
automatically designs each prompt based on the input rather than the shared
manual design of a previous work [5]. Therefore, our prompt has a higher
capability and can flexibly change the semantics of the original image. By
learning the reparameterized model instead of the prompt itself, we greatly
reduce the number of parameters (from 69K of VP [5] to 9K or 1K) so that
suitable for the black-box optimization scenario.

Second, to train the Coordinator, BlackVIP adopts a zeroth-order optimization
(ZOO) that estimates the gradient from the pairs of input queries and outputs
of the black-box model. With this modification, we can adapt any pre-trained
vision model, whether its parameters are available in public or not, and can
significantly reduce the required memory capacity compared to white-box tuning
methods that require caching intermediate activations. For faster and more
accurate optimization, we further present a new ZOO algorithm, Simultaneous
Perturbation Stochastic Approximation with Gradient Correction (SPSA-GC) based
on (SPSA) [13]. SPSA-GC first estimates the gradient of the target black-box
model based on the output difference of perturbed parameters and then corrects
the initial estimates in a momentum-based look-ahead manner. By integrating
the Coordinator and SPSA-GC, BlackVIP achieves significant performance
improvement over baselines.

This work is an extension of a conference paper [14], which has a contribution
as a leading work on black-box visual prompting. We summarize our new
contributions in this paper as follows: (1) We propose a new variant of
BlackVIP, BlackVIP-SE (Statistical feature-guided Efficient prompt), which is
remarkably faster and computationally more efficient than the original
BlackVIP while consistently outperforming other baselines. (2) To investigate
the broad applications of our method, we expand the scope of validation with
more diverse viewpoints, such as real-world distribution shift benchmarks,
compatibility with the post-training quantization method, and white-box
transfer regime. (3) For the first time, we provide a theoretical
understanding on the generalization mechanisms of visual prompting methods
through the lens of the certified robustness of a smoothed classifier.

##  II Related Works

###  II-A Parameter-Efficient Transfer Learning

Adapting the entire PTM to targeted downstream tasks is computationally
prohibited for most users. Parameter-Efficient Transfer Learning (PETL)
methods pursue fine-tuning of a small subset of PTM’s parameter set while
achieving competitive performance compared to full fine-tuning. Some of them
host new learnable modules inside of PTM [4, 15, 16] or on top of PTM
representation [17, 18, 19, 20], and others pursue learning tokens of
Transformer layer [21], e.g., CoOp [22] and its variants [10, 6, 23, 24].
Meanwhile, Bahng et al. [5] and its follow-up research [25, 26, 27] explore
the Visual Prompting (VP) approach, which introduces a learnable prompt in the
input space, neither into the embedding space nor the model’s architectural
building blocks. The prompt is attached to the image (pixel-wise addition) and
updated by gradient descent to optimize the downstream objective function.
However, all the existing PETL methods are not memory-efficient. That is, they
require users to prepare sufficient memory capacity for caching the
intermediate representations inside of PTM to compute the gradient. More
importantly, they assume that the model parameters are fully available to the
public, which is not the case in many cases of real-world AI, where the model
is only provided as a black-box API. While there are some recent attempts
pursuing memory-efficient fine-tuning [28, 29, 30], they still require
accessibility to full model parameters. To break these optimistic assumptions,
we provide the black-box visual prompting approach that does not require
parameter accessibility or large memory capacity.

###  II-B Black-Box Optimization

In many real-world applications, high-performing AI models are provided via
black-box API or proprietary software to protect model ownership. To this end,
there are some recent works that fine-tune the large language model via black-
box optimization [31, 32, 33]. Besides, black-box adversarial reprogramming
(BAR) [34] had been proposed to re-purpose the ImageNet [35] pre-trained
vision model to a specialized classifier for medical images. The previous
works on black-box optimization commonly adopt zeroth-order optimization (that
exploits the estimated gradients) or derivative-free optimization algorithms
for parameter updates. BAR [34] adopts a one-sided approximation gradient
estimator, but we find that the one-sided estimator shows inaccurate gradient
approximations empirically. BBT [31], and BBTv2 [32] adopt CMA-ES [36, 37],
and RLPrompt [33] uses reinforcement learning (RL) to optimize the discrete
prompts. However, It has been known that derivative-free optimizations (e.g.
evolutionary algorithm) are hard to solve large-scale problems and do not
guarantee convergence [38]. Besides, RL approaches are notorious for their
instability and high variance [39]. This work adopts the Simultaneous
Perturbation Stochastic Approximation (SPSA) [13] as a ZOO algorithm. It is
known that SPSA efficiently provides gradient approximation on high-
dimensional problems [13, 40]. Besides, SPSA theoretically guarantees
convergence, and the convergence error is linearly upper bounded by the
dimension of optimization [13]. While SPSA is designed to estimate high-
dimensional gradients efficiently, we found that SPSA-based neural network
optimization still requires many queries in practice. Therefore, we propose
SPSA with Gradient Correction (SPSA-GC) that corrects the approximated
gradients to enhance the convergence speed. This is the first work exploring
the ZOO-based black-box optimization to large PTMs in vision domain for
general-purpose adaptation (rather than a specific domain [34]).

Figure 2: BlackVIPs equip an input-dependent prompt designer (Coordinator) and
an accurate gradient estimation algorithm (SPSA-GC). To produce low-
dimensional latent features of input images, BlackVIP [14] adopts another PTM
as a frozen feature extractor. In this extended work, we relax the reliance on
another PTM with a simple projection obtained by a statistical learning method
and call that approach BlackVIP-SE.

##  III Methodology

Background. We first present an outline of adversarial reprogramming and
visual prompting, that originated from distinct motivations but closely
related topics. Elasyed et al. [41] presented adversarial reprogramming (AR)
inspired by adversarial attack [42, 43, 44]. The goal of AR is repurposing the
pre-trained model to perform a new adversarial task. Let
$x\in\mathbb{R}^{k\times k\times 3}$ be a resized image of the target
adversarial task, and $\tilde{x}\in\mathbb{R}^{n\times n\times 3}$ is a zero-
padded tensor that embeds $x$ in the center, where $k<n$. Given the target
class of adversarial task $y_{adv}\in\\{1,...,C_{tar}\\}$, the AR is
formulated as:

$\displaystyle\operatorname*{arg\,min}_{W}(-\log{P(m(y_{adv})|\tilde{x}_{adv}})+||W||_{F})$

Here, $P(y|x)$ is a softmax output of PTM given $x$ and the adversarial image
is constructed as $\tilde{x}_{adv}=\tilde{x}+\text{tanh}(W\odot M)$, and
$W\in\mathbb{R}^{n\times n\times 3}$ is the adversarial program that is
optimized, where $n$ is the image width of a pre-train dataset, $M$ is an
optional mask for better visualization of the embedded target image, and
$\odot$ denotes the element-wise multiplication. Given a pre-defined hard-
coded mapping $m(\cdot)$ that maps labels from an adversarial task to labels
of a pre-train dataset, AR reprograms the model by learning perturbation
without changing model architecture or weights. The sensitivity of neural
networks to such perturbations has inspired many works that use the AR
approach from transfer learning perspectives [34, 45, 46, 47] i.e., model
reprogramming.

Meanwhile, motivated by the remarkable success of the prompting paradigm in
NLP, Bahng et al. [5] are the first to explore the pixel space visual
prompting (VP) approach for pre-trained vision models. By learning individual
RGB pixels as an input space prompt that is attached to the input images, VP
adapts the frozen PTM to targeted downstream tasks without any modification on
the model architecture and weights. Given the input $x$ and corresponding
label $y$, the learning objective of VP is,
$\operatorname*{arg\,min}_{\phi}-\log P(y|x+\phi)$, where $\phi$ is a
learnable visual prompt and $P(y|x)$ is an output prop of PTM given $x$.
During inference, VP employs the shared input-independent prompt for all
images. It is noted that $\phi$ is attached to the fixed location, e.g., the
outer part of an image like a frame by default. Though AR and VP use different
terms and stem from distinct motivations, they share the fundamental concept:
adapt a PTM to perform new tasks without modifying the model architecture or
its weights. The goal of this work aligns with AR and VP, but we extend and
improve them for broader applications.

We will introduce our novel input-dependent prompt generation module,
Coordinator in Section III-A. Then, we explain the end-to-end framework of
BlackVIP with the new ZOO algorithm, SPSA-GC in Section III-B. Figure 2
illustrates the overall framework of our proposal.

###  III-A Coordinator: Prompt Reparameterization

Our learning objective is to minimize the loss function of a downstream task
with a frozen PTM by optimizing the input space visual prompt. Given a frozen
PTM $P(y|x)$, and prompt-augmented image $\tilde{x}_{\bm{\phi}}$ corresponding
to the label $y$, the training objective is formulated as:

$\displaystyle\operatorname*{arg\,min}_{\bm{\phi}}-\log
P(y|\tilde{x}_{\bm{\phi}}).$

While VP and AR directly optimize the RGB pixels as parameters of the prompt,
we reparameterize the visual prompt to a neural network $v_{\bm{\phi}}(\cdot)$
parameterized by $\bm{\phi}=\\{\phi_{d},\phi_{t}\\}\in\mathbb{R}^{p}$.
Specifically, we design a novel module named Coordinator composed of a fixed
encoder $f(\cdot)$, which projects an input image $x$ to a low-dimensional
feature $z_{x}$, followed by a lightweight decoder $g_{\phi_{d}}(\cdot)$ that
generates a visual prompt from the integration of instance-specific feature
$z_{x}$ and a learnable task-specific prompt trigger vector $\phi_{t}$.
Consequently, the prompt-augmented image is formulated as follows:

$\displaystyle\tilde{x}_{\bm{\phi}}$ $\displaystyle=\text{clip}(x+\epsilon
v_{\bm{\phi}}(x)),\quad v_{\bm{\phi}}(x)=g_{\phi_{d}}(z_{x},\phi_{t})$

where $z_{x}=f(x)$ is the feature vector of $x$ from the fixed encoder
$f(\cdot)$, and $\epsilon\in[0,1]$ is a hyperparameter that controls the
intensity of visual prompt. We concatenate the prompt trigger vector
$\phi_{t}$ with $z_{x}$ and then reshape them into a 3D feature map to feed
into the decoder $g_{\phi_{d}}(\cdot)$ constructed by a stack of convolution
layers. As a result, the instance-specific rich semantic representation
$z_{x}$ and the task-specific prior $\phi_{t}$ are merged to design a valid
visual prompt $v_{\bm{\phi}}(x)$ for a given image. Similar to [45], the
prompted image is bounded to a valid RGB scale of the target model’s input
domain via pixel-wise clipping operation $\text{clip}(\cdot)$.

Unlike previous works [5, 34] that adopt a pre-defined input-independent
prompt to the local regions of an image, our approach automatically designs
the input-dependent prompt that covers an entire image; therefore, it has a
higher capability to change the semantics of images if necessary. Thanks to
this flexibility, it can cover more diverse tasks and be robust to challenging
scenarios, e.g., distribution shift. We demonstrate the efficacy of our prompt
design strategies in Section IV. From now on, we will provide two
specifications of the encoder component $f(\cdot)$ in the following
paragraphs.

####  III-A1 BlackVIP

By default, we adopt an ImageNet pre-trained model with a self-supervised
learning (SSL) objective as a frozen feature encoder $f(\cdot)$. Though the
encoder can also be a supervised counterpart or trained from scratch, we
choose a frozen SSL encoder by following three reasons: 1) It has been widely
substantiated that self-supervised representation contains the multiple
discriminative features and spatial information [48, 49, 50, 51, 52, 53, 54],
so it is more helpful to use SSL pre-trained encoder than label-supervised
encoder for robust adaption of black-box PTM on diverse tasks. 2) ImageNet
pre-trained models are currently well-publicized [55], so they can be readily
adopted by local users, and does not hurt our realistic experimental setting.
3) By leveraging the frozen pre-trained encoder, we significantly reduce the
number of learnable parameters compared to the case of training the encoder
from scratch. The reduced dimension of optimization contributes to efficient
gradient approximation.

####  III-A2 BlackVIP-SE

While BlackVIP allows us to enjoy the rich features as a source of prompts, it
requires an additional forward pass as well as the querying of black-box
target PTM. As a result, it increases the runtime per iteration and during
inference compared with model-free prompting baselines and hinders its wider
applications. Here, we note an observation that the success of transfer
learning is not only attributed to high-level feature reuse but also learning
from the low-level statistics across data instances [56]. Motivated by this
finding, we hypothesize that low-level statistical features can be an
effective alternative to model-based high-level semantic features for
producing visual prompts to adapt the black-box target model. To that end, we
devise a new variant, BlackVIP-SE (Statistical feature-guided Efficient
prompt), by replacing the auxiliary PTM feature extractor with a more
efficient statistical method. Specifically, we conduct the principal component
analysis (PCA) directly on the flattened vectors of train images to find a new
coordinate system that preserves the maximum variation of data. Then, we
project each image into the PCA-induced low-dimensional space (98 by default)
to get statistical features being convened to the decoder of the
Coordinator111We first fit the PCA on the few-shot train samples to get a
projection matrix and use that matrix as a fixed encoder. This simple
modification endows two favorable merits compared to BlackVIP: 1) it
remarkably reduces the runtime (See Table V) during training and inference
phases by replacing the PTM feature extractor into a single projection matrix,
and 2) it also significantly reduces the number of learnable parameters by
setting the projection dimension of PCA much lower than that of auxiliary
PTM’s latent feature dimension in BlackVIP (See Table IV) thereby decreasing
the peak memory usage and computational cost.

Algorithm 1 BlackVIP and BlackVIP-SE algorithms

Downstream dataset $\mathcal{D}$, pre-trained model $P(\cdot|\cdot)$,
Coordinator $v$ with encoder $f$ and prompt decoder $g$, is parameterized by
$\bm{\phi}_{i}=\\{\phi_{d,i},\phi_{t,i}\\}$, SPSA-GC decaying parameters
$\\{a_{i},c_{i}\\}$, smoothness parameters $\beta$, prompt intensity
$\epsilon$, and training iteration $T$.

// Initialize $\bm{\phi}_{1}=\\{\phi_{d,1},\phi_{t,1}\\}$, $\\{a_{1},c_{1}\\}$
and $m_{1}$

for $i$ in $1$ to $T$ do

// Parse a batch $(x,y)\sim\mathcal{D}$ and design the prompt

$v_{\bm{\phi}_{i}}(x)=g_{\phi_{d,i}}(f(x),\phi_{t,i})$

$\tilde{x}_{\bm{\phi}}=\text{clip}(x+\epsilon v_{\bm{\phi}_{i}}(x))$

// Draw a sample $\Delta_{i}$, set $c_{i}$, and estimate the gradient

$L(\bm{\phi}_{i}):=-\log P_{\bm{\phi}_{i}}(y|\tilde{x}_{\bm{\phi}})$

$\hat{e}_{i}(\bm{\phi}_{i})=\frac{L(\bm{\phi}_{i}+c_{i}\Delta_{i})-L(\bm{\phi}_{i}-c_{i}\Delta_{i})}{2c_{i}\Delta_{i}}$

// Set $a_{i}$, and update parameters

$m_{i+1}=\beta m_{i}-a_{i}\hat{e}_{i}(\bm{\phi}_{i}+\beta m_{i})$

$\bm{\phi}_{i+1}=\bm{\phi}_{i}+m_{i+1}$

end for

###  III-B End-to-End Black-Box Visual Prompting

Unlike other PETL approaches, we consider the PTM as a black-box predictor
that gives only a prediction output (i.e. logit vector) for a given input
image query. In this black-box setting, we adopt the ZOO algorithm, SPSA, with
our deliberate modification to optimize Coordinator without the oracle true
gradient.

####  III-B1 SPSA

Spall et al. proposed Simultaneous Perturbation Stochastic Approximation
(SPSA) [13, 57] that approximates the high-dimensional gradient efficiently.
Given the positive decaying sequences of $a_{i}>0$ and $c_{i}\in[0,1]$, the
gradient estimate, $\hat{e}$, and single-step parameter update of SPSA is
described as follows:

$\displaystyle\hat{e}_{i}(\bm{\phi}_{i})$
$\displaystyle=\frac{L(\bm{\phi}_{i}+c_{i}\Delta_{i})-L(\bm{\phi}_{i}-c_{i}\Delta_{i})}{2c_{i}}\Delta_{i}^{-1}$
(1) $\displaystyle\bm{\phi}_{i+1}$
$\displaystyle=\bm{\phi}_{i}-a_{i}\hat{e}_{i}(\bm{\phi}_{i})$ (2)

where $L$ is an objective function, $\bm{\phi}_{i}\in\mathbb{R}^{p}$ is
$p$-dimensional learnable parameters, and $\Delta_{i}\in\mathbb{R}^{p}$ is a
$i^{th}$-step random perturbation vector, sampled from mean-zero distributions
that satisfy finite inverse momentum condition [13, 58] such as Rademacher and
Segmented Uniform distribution. With only two forward evaluations, i.e.,
querying twice to the API service model, SPSA parses the learning signal
(estimate gradient) from the difference between model outputs, and we can
update the parameters $\bm{\phi}$ of Coordinator.

####  III-B2 SPSA with Gradient Correction

Although the standard form of SPSA works well in myriad applications [59, 60,
61], like other ZOO algorithms, it may suffer slow convergence in practice
[62, 63], and the problem gets even bigger on the high-dimensional problem
setting such as neural networks’ optimization. We speculate that the source of
slow convergence is its noisy gradient estimation from the poor direction of
random perturbations or intrinsic data noise. To mitigate the estimation
noise, inspired by Nesterov’s accelerated gradient (NAG) [64], we improve the
update rule in Eq. 2 as below:

$\displaystyle\bm{\phi}_{i+1}$ $\displaystyle=\bm{\phi}_{i}+m_{i+1}$ (3)
$\displaystyle m_{i+1}$ $\displaystyle=\beta
m_{i}-a_{i}\hat{e}_{i}(\bm{\phi}_{i}+\beta m_{i})$ (4)

where $\beta\in[0,1)$ is smoothing parameter. As clearly noted in [65], when
the poor update $\bm{\phi}_{i}+\beta m_{i}$ occurs, this NAG style update rule
strongly pulls it back towards $\bm{\phi}_{i}$. Because of the SPSA’s strongly
stochastic nature, we conjecture that this gradient correction property is
also highly effective for SPSA as well as first-order optimization algorithms.

##  IV Results

TABLE I: Results on synthetic datasets: correlation shifts and varying object location scenarios. | Biased MNIST | Loc-MNIST
---|---|---
Method | 16-Shot | 32-Shot | 16-Shot | 32-Shot
$\rho=0.8$ | $\rho=0.9$ | $\rho=0.8$ | $\rho=0.9$ | 1:1 | 1:4 | 1:1 | 1:4
VP (white-box) | 57.92 | 43.55 | 69.65 | 42.91 | 86.79 | 86.54 | 90 .18 | 92.09
ZS | 37.56 | 37.25 | 37.56 | 37.25 | 29.70 | 22.70 | 29.70 | 22.70
BAR | 53.25 | 53.07 | 53.93 | 53.30 | 33.98 | 26.05 | 34.73 | 27.72
VP w/ SPSA-GC | 60.34 | 53.86 | 59.58 | 51.88 | 16.21 | 25.68 | 18.43 | 30.13
BlackVIP-SE | 55.73 | 55.93 | 61.65 | 60.85 | 62.92 | 55.57 | 70.58 | 56.59
BlackVIP | 66.21 | 62.47 | 65.19 | 64.47 | 69.08 | 60.86 | 76.97 | 67.97

###  IV-A Experimental Setup

Datasets. First, to investigate the importance of prompt design, we first
consider two synthetic datasets that simulate the correlation shift and
varying object location scenarios (see Section IV-B and Appendix). Then, we
extensively evaluate our methods on 14 transfer learning benchmarks. These
cover diverse visual domains and tasks, so they require understanding various
visual semantics like scenes, actions, fine-grained categories, textures,
satellite imagery, the number of objects, and recognition of generic objects.
Moreover, to evaluate the robustness of prompt-based adaptation of PTM in the
wild, we additionally consider three benchmark datasets of distribution shifts
from WILDS [66]. See Supplementary for details.

Figure 3: (Left) loss curve and (right) noise sensitivity analysis of
100-Dimensional Rosenbrock optimization problem with ZOO algorithms.

Figure 4: (Left) Embedding visualization with t-SNE [67] on the prompt-
augmented images from test splits of Loc-MNIST 1:4 setup. (right) Normalized
Mutual Information (NMI) [68] score of the learned embedding.

Backbone model and methods. We adopt CLIP ViT-B/16 [2] as a target PTM because
CLIP does not require a separate classifier for different tasks and performs
classification dynamically with text embedding features by text-side
prompting. As the encoder part of the Coordinator, we use ImageNet pre-trained
vit-mae-base checkpoint for BlackVIP and sci-kit-learn’s vanilla PCA or kernel
PCA for BlackVIP-SE. As baseline methods, we consider 1) zero-shot
classification (ZS) with the standard text prompt “a photo of {classname}”, 2)
black-box adversarial reprogramming (BAR) [34] that embed the downsized images
of the downstream task inside a learnable prompt, and 3) VP with SPSA-GC that
simply replace the backpropagation in VP [5] with our SPSA-GC. Besides, we
validate the effectiveness of our new prompt design on the white-box transfer
learning setup, which enables users to access the true gradient of model
parameters. Following the few-shot classification setting of [22], we use 16
samples per class for training and the entire test set for all evaluations by
default. More details are provided in the Supplementary.

###  IV-B Experiments on Synthetic Datasets

####  IV-B1 Comparison between ZOO algorithms

We validate our SPSA-GC on the well-known optimization benchmark, Rosenbrock
function. We report the normalized loss
($\frac{|L(\theta^{*})-L(\theta)|}{|L(\theta^{*})-L(\theta_{0})|}$) where
$L(\theta^{*})$ and $L(\theta_{0})$ is the loss value on the optimal and
initial point, respectively, and $L(\theta)$ is a loss value on the current
parameter $\theta\in\mathbb{R}^{100}$. In Fig. 3 (left), SPSA-GC shows faster
and more stable convergence than Random Gradient-Free (RGF) adopted in
previous works [69, 34], and even achieves a comparable result to Nesterov’s
Accelerated Gradient (SGD-NAG) method which adopts the true gradient. Besides,
we simulate the noisy loss observation scenario (emulating the mini-batch
optimization) by adding Gaussian noise to learning loss, i.e.,
$L_{noisy}(\theta)=L(\theta)+\xi$, where $\xi\sim\mathcal{(}0,scale^{2})$. In
Fig. 3 (right), as the noise increases, RGF rapidly degenerates while SPSA is
still relatively stable, and our gradient correction (SPSA-GC) gives further
improvement. This verifies the robust gradient approximation of SPSA-GC.

####  IV-B2 Robustness on Correlation Shift

Next, we evaluate our method on Biased MNIST [70] to investigate the
robustness of BlackVIPs’ input-dependent automatic prompt design under the
feature-label correlation shift environment. Biased MNIST is a modified
version of MNIST [71], constructed to validate a model’s generalization
ability under color bias shift. At the train-time, each digit has a unique
preassigned background color that strongly correlates with the target label.
The degree of correlation is determined by the value $\rho\in[0,1]$, and the
correlation ratio is reversed as $1-\rho$ at the inference-time. Results are
summarized in Tab. I (left) and Fig. 4 (right). In this setup, BlackVIPs
remarkably outperform others (even white-box VP), and the performance gap
becomes larger under the stronger correlation. This means that BlackVIPs, by
flexibly modifying the semantics of the image with input-dependent visual
prompts, can be beneficial in challenging adaptation scenarios wherein
spurious correlation exists.

####  IV-B3 Robustness on Varying Object Location

For many object recognition datasets, the target objects are commonly placed
in the center of the image. However, input data of foundation models in the
wild may have varying object locations. We expect that BlackVIP and BlackVIP-
SE adopt input-dependent prompts that cover the entire region of the image so
they are still robust even if the object is not always located in the center
of the image. To validate this, we create a variant of the MNIST, Loc-MNIST,
by putting a real target digit on the four edges and an arbitrary fake digit
in the center of the black blank image. The location of the target digit and
the class of the fake digit are chosen randomly. We further consider a more
challenging setup in that the fake digit is four times larger (1:4) than the
real one. We summarize the results in Tab. I (right) and Fig. 4, respectively.
Compared to the manually designed input-independent prompts (BAR and VP) that
are frame-shaped by default, conditional prompts produced by BlackVIPs achieve
significantly better performance, which supports the superiority of the
Coordinator’s prompt design.

###  IV-C Few-shot Transfer Learning on Benchmarks

####  IV-C1 Main Results

We consider the 14 commonly used few-shot benchmark datasets following [22,
10, 5]. As shown in Tab. II, while BAR and VP undergo large performance
variations across 14 datasets, BlackVIPs boast consistently high performance
(i.e., improve the zero-shot performance on 13 and 14 over 14 datasets).
Specifically, BAR shows promising results on the tasks that require
understanding coarse semantics (DTD [72], EuroSAT [73], and RESISC [74]), but
fails to show competitiveness on CLEVR [75] that requires visual reasoning
(counting objects) by capturing the overall image semantics. Meanwhile,
BlackVIP performs well across various tasks by extending or limiting the
region of attention of the black-box target PTM (Fig. 5), which denotes that
BlackVIP is a high-capability prompt learner that robustly adapts the PTM to
diverse downstream tasks.  Overall, BlackVIP-SE also shows remarkable
performance improvements that are comparable to BlackVIP while significantly
faster and lighter. We speculate that BlackVIP-SE excels on the datasets where
the input feature space has a relatively low intrinsic dimensionality [76,
77], such as SVHN, so the PCA-based approaches can find a sufficiently
expressive low-dimensional manifold [78].

TABLE II: Top-1 classification accuracy on 14 benchmarks that require natural,
specialized, structured, and fine-grained visual recognition. BlackVIP and
BlackVIP-SE show outstanding results among input-space visual prompting
methods. Win means the number of datasets that each method beats the zero-shot
performance. Gray-colored values are the results of white-box prompt learning
with the stochastic gradient descent. All experiments are done in 16-shot
training with three repeated runs.

Method | Caltech | Pets | Cars | Flowers | Food | Aircraft | SUN | DTD | SVHN | EuroSAT | RESISC | CLEVR | UCF | IN | Avg. | Win
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
VP (white-box) | 94.2 | 90.2 | 66.9 | 86.9 | 81.8 | 31.8 | 67.1 | 61.9 | 60.4 | 90.8 | 81.4 | 40.8 | 74.2 | 67.4 | 71.1 | 13
ZS | 92.9 | 89.1 | 65.2 | 71.3 | 86.1 | 24.8 | 62.6 | 44.7 | 18.1 | 47.9 | 57.8 | 14.5 | 66.8 | 66.7 | 57.6 | -
BAR | 93.8 | 88.6 | 63.0 | 71.2 | 84.5 | 24.5 | 62.4 | 47.0 | 34.9 | 77.2 | 65.3 | 18.7 | 64.2 | 64.6 | 61.4 | 6
VP w/ SPSA-GC | 89.4 | 87.1 | 56.6 | 67.0 | 80.4 | 23.8 | 61.2 | 44.5 | 29.3 | 70.9 | 61.3 | 25.8 | 64.6 | 62.3 | 58.8 | 4
BlackVIP-SE | 93.5 | 89.8 | 65.6 | 71.5 | 86.3 | 25.4 | 65.3 | 45.1 | 46.1 | 71.2 | 61.1 | 32.1 | 68.5 | 67.1 | 63.5 | 14
BlackVIP | 93.7 | 89.7 | 65.6 | 70.6 | 86.6 | 25.0 | 64.7 | 45.2 | 44.3 | 73.1 | 64.5 | 36.8 | 69.1 | 67.1 | 64.0 | 13

Figure 5: Grad-CAM analysis on CLEVR, Pets, and UCF101.

####  IV-C2 Visual Prompting in the Wilds

TABLE III: Robustness comparison under real-world distribution shift. Method | iWildCam | FMoW | Camelyon17 | Avg.
---|---|---|---|---
ZS | 9.9 | 18.9 | 55.2 | 28.0
BAR | 11.0 | 22.4 | 76.8 | 36.7
VP w/ SPSA-GC | 10.9 | 22.3 | 66.5 | 32.5
BlackVIP-SE | 10.6 | 21.9 | 79.7 | 37.4
BlackVIP | 12.3 | 22.6 | 76.5 | 37.1

We now validate those approaches on three kinds of real-world datasets
(iWildCam, FMoW, and Camelyon17) from the WILDS distribution shift benchmark
[66]. In iWildCam, the task is to classify the 182 species of animals in the
wild under different remote sensing conditions (location of camera traps). In
FMoW, satellite images should be classified into the building and land types
62 in total, and the shifting factor is the combination of (year, region).
Meanwhile, Camelyon17 requires a binary classification (tumor or normal) on
the patch-level tissue slides under varying hospital imaging conditions. In
Table III, the baseline approaches, BAR and VP w/ SPSA-GC, show their
effectiveness in improving the zero-shot classifier’s performance, and our
BlackVIPs achieve superior average performances. Interestingly, while
BlackVIP-SE underperforms other methods in iWildCam and FMoW, it shows
outstanding performance on Camelyon17, where we speculate the intrinsic
dimensionality of task is relatively low, and the PCA features can be
discriminative enough to generate good prompts.

####  IV-C3 Practical Usefulness

TABLE IV: Train-time peak memory allocation and the number of learnable parameters on ImageNet-1K with batch size 64. Method | Peak Memory (MB) | Params
---|---|---
ViT-B | ViT-L | ViT-B | ViT-L
FT (white-box) | 21,655 | 76,635 | 86M | 304M
LP (white-box) | 1,587 | 3,294 | 513K | 769K
VP (white-box) | 11,937 | 44,560 | 69K | 69K
BAR | 1,649 | 3,352 | 37K | 37K
VP w/ SPSA-GC | 1,665 | 3,369 | 69K | 69K
BlackVIP-SE | 1,319 | 2,540 | 1K | 1K
BlackVIP | 2,428 | 3,260 | 9K | 9K

Memory and computation efficiency (Table IV). First, BlackVIP and BlackVIP-SE
have 9K and 1K parameters in total, respectively. This allows us to remarkably
reduce the computational cost compared with other white-box approaches (such
as FT and LP) or black-box approaches (BAR and VP). Furthermore, all the
black-box adaptation approaches significantly reduce the train-time peak
memory requirement, which is burdening for white-box approaches. Among the
black-box methods, BlackVIP-SE achieves the best memory-and-computation
efficiency.

Figure 6: Query efficiency. (x-axis) A number of queries and cost for
achieving (y-axis) corresponding performance.

Query efficiency (Figure 6). Second, BlackVIPs show outstanding query
efficiency among black-box prompting methods. For instance, by sending just
10K queries with 12 USD (based on Clarifai Vision API), we can improve the
performance of a zero-shot model about two $\sim$ three times better using
BlackVIP and BlackVIP-SE. Given that we pay for each query to adapt black-box
API models, ensuring query efficiency does matter, and our BlackVIPs offer a
favorable cost-and-performance trade-off.

TABLE V: Runtime (second) comparison between prompting methods. Training denotes the sum of the forward prompt generation and the parameter update procedures for a single batch, and Inference indicates per batch forward time. Method | Training | Inference
---|---|---
ZS | - | 0.0044
BAR | 0.1402 | 0.0049
VP | 0.1417 | 0.0049
BlackVIP-SE | 0.1233 | 0.0053
BlackVIP | 0.2684 | 0.0098

Runtime analysis (Table V). Next, we investigate the wall-clock time for the
single-batch forward prompt generation and parameter update during training
and inference time per batch. While BlackVIP achieves superior classification
accuracy on many setups, it compromises the time complexity due to its
reliance on an auxiliary feature extractor during prompt generation. This
hinders the broad use of BlackVIP in some applications where the inference
time is crucial. In contrast, our new variant, BlackVIP-SE, addresses this
issue by replacing the feature extractor model with a single projection matrix
founded by PCA. As a result, BlackVIP-SE achieves a competitive runtime
compared with other baselines (BAR and VP) while significantly outperforming
in terms of classification accuracy (See Table II). This reduced runtime
during training and inference phases allows it to become a favorable
alternative to BlackVIP in time-critical applications.

###  IV-D Ablation Study

####  IV-D1 Model Architectures

To study the versatility of our method, we vary the backbone architecture of
the pre-trained target model and the encoder of Coordinator in Tab. VI. While
BAR and the naive application of SPSA-GC on VP fail to improve the zero-shot
performance of CNN-based target backbones that lack the global attention of
Transformers [21], our BlackVIPs consistently bring huge performance gains
across all the architectures. It implies that BlackVIPs are architecture-
agnostic approaches, which pursue the general adaptation method for high-
performing PTMs. Regarding the comparison between BlackVIP and BlackVIP-SE,
BlackVIP shows better results when the model architecture of the Coordinator
encoder aligns with the target PTM’s architecture. Meanwhile, BlackVIP-SE
achieves more stable performance improvement across all architectures.

TABLE VI: Ablation study for backbone architecture. Classification accuracy on EuroSAT across pre-trained target backbone architectures and BlackVIP’s Coordinators. Method | Target Backbone
---|---
| RN50 | RN101 | ViT-B/32 | ViT-B/16 | Avg.
ZS | 37.5 | 32.6 | 45.2 | 40.8 | 48.4
BAR | 26.9 | 33.5 | 70.3 | 77.2 | 52.0
VP w SPSA-GC | 34.7 | 31.2 | 71.1 | 70.9 | 52.0
BlackVIP-SE | 50.0 | 55.1 | 66.2 | 71.2 | 60.6
BlackVIP (RN50) | 51.3 | 50.8 | 62.9 | 68.5 | 58.4
BlackVIP (ViT-B/16) | 48.4 | 51.3 | 67.9 | 73.1 | 60.2
TABLE VII: Different Coordinator weights with SPSA variants. Mean classification accuracy of three repeated runs on EuroSAT. Encoder Type | Optim. | Acc.
---|---|---
Zero-Shot | 47.9
scratch | SPSA | 49.6
scratch | SPSA-GC | 49.5
Sup. pre-trained | SPSA | 59.4
Sup. pre-trained | SPSA-GC | 65.2
SSL pre-tained | SPSA | 69.4
BlackVIP-SE (PCA matrix with SPSA-GC) | 71.2
BlackVIP (SSL pre-trained with SPSA-GC) | 73.1

####  IV-D2 Coordinator and ZOO Algorithms

BlackVIPs adopt the encoder-decoder structure to efficiently generate the
input-dependent prompts. We exploit an SSL pre-trained encoder (in BlackVIP)
and PCA projection encoder (in BlackVIP-SE) while learning a randomly
initialized lightweight decoder from scratch. From the design philosophy of
BlackVIPs, we expect that the encoder extracts the essential features of the
given image, including the spatial features, and the decoder utilizes the
features to produce a spatially and semantically structured prompt tailored to
the input. We conjecture that SSL pre-trained and PCA encoders are desirable
to capture the demanding semantics instead of a supervised one learned from
pre-defined labels. Here, Table VII confirms that the SSL encoder outperforms
the supervised pre-trained or randomly initialized encoder (scratch). Besides,
the PCA encoder also outperforms the large-scale supervised encoder, which
indicates the potential of the classic statistical methods for feature
extraction during transfer learning. Furthermore, SPSA-GC improves the 3.7%
accuracy than SPSA, from 69.4 to 73.1. It denotes that approximated gradients
by our SPSA-GC are more accurate than the original SPSA.

###  IV-E Broad Applications

####  IV-E1 White-box Transfer Learning

TABLE VIII: White-box transfer learning with true gradients access. Mod. | Method | Params | SVHN | CLEVR | Pets | Avg.
---|---|---|---|---|---|---
- | ZS | - | 18.1 | 14.5 | 89.1 | 40.6
- | FT | 86M | 71.5 | 25.4 | 90.9 | 62.6
L $\&$ V | MaPLe | 1.2M | 66.5 | 40.5 | 92.9 | 66.6
L | CoOp | 9K | 43.8 | 36.1 | 91.7 | 57.2
L | CoCoOp | 35K | 48.6 | 29.7 | 93.0 | 57.1
V | VP | 69K | 60.4 | 40.8 | 90.2 | 63.8
V | VPT | 73K | 62.9 | 39.9 | 93.2 | 65.3
V | Ours-SE | 1K | 60.5 | 36.1 | 90.0 | 62.2
V | Ours | 9K | 60.4 | 42.6 | 90.8 | 64.6
V | Ours | 68K | 61.8 | 43.6 | 90.5 | 65.3
V | Ours | 150K | 61.4 | 45.4 | 91.4 | 66.1

Although the chief motivation of BlackVIP originated from the desire to break
the parameter accessibility assumption and overwhelming memory requirements,
our prompt reparameterization strategy not only resolves the memory issues but
also improves the design of visual prompts compared with other visual
prompting approaches. To validate the efficacy of the prompt designs of
BlackVIPs, we replace the estimated gradients of ZOO with the true gradient
computed by the first-order optimizer, assuming we have access to the entire
model parameters. As shown in Table VIII, our prompting approaches
(corresponding to BlackVIP and BlackVIP-SE) outperform other recent prompt-
based efficient tuning methods such as VP, VPT, CoOp, and CoCoOp under similar
parameter capacity. Even our approach (with 150K parameters) is comparable
with MaPLe [6], which requires eight times more parameters. These results
imply that our innovative design of prompt can be leveraged on the white-box
parameter-efficient tuning regime as well.

####  IV-E2 Visual Prompting for Quantized Models

TABLE IX: Image classification with quantized models (CLIP ViT-B/16). Evaluation is conducted on CPU. Quantization | Method | SVHN | CLEVR | Inference time
---|---|---|---|---
16-bit, float | ZS | 18.0 | 14.7 | 0.3177
VP w/ SPSA-GC | 34.8 | 21.8 | 0.3236
BlackVIP-SE | 47.2 | 29.3 | 0.3223
| BlackVIP | 43.8 | 34.9 | 0.3489
8-bit, int | ZS | 15.0 | 16.6 | 0.0482
VP w/ SPSA-GC | 14.7 | 14.2 | 0.0519
BlackVIP-SE | 16.9 | 15.4 | 0.0548
| BlackVIP | 16.3 | 18.7 | 0.0584

While the main goal of BlackVIPs is to enable memory-efficient transfer
learning without parameter accessibility, as the scale of modern state-of-the-
art AI models continually skyrockets [79], reducing the inference latency is
also increasingly crucial for deploying those models on diverse edge devices.
Post-training quantization is a representative remedy that reduces the model
size and required peak memory by converting the learned model parameters into
low-bit ones. Here, we validate the visual prompting strategies on post-
training quantized low-bit models. Specifically, we produce the visual prompts
learned by the original 32-bit model and equip the prompts with images to feed
into the converted low-bit model for performance evaluation. While the
effectiveness varies across the bit-size and dataset, we confirm that (in
Table IX) BlackVIPs can actually collaborate with the post-training
quantization method to reduce the memory requirement. Compared with VP w/
SPSA-GC, BlackVIPs show remarkably better performance while not significantly
increasing inference-time latency.

##  V Theoretical Understanding on the Generalization of the Visual Prompting

Figure 7: Illustration on a classifier’s decision boundary. The dotted
contours are the level sets of Gaussian where the mean and covariance
parameters are set manually or learned from data, and the red and blue arrows
indicate the transformation of data $x$ by attaching visual prompts. Here, the
circle and star symbols denote the original and transformed data. Two left
plots (a) present the comparison between the randomized smoothing classifier
and the visual prompting classifier. Under some assumptions, a classifier with
visual prompting methods can be interpreted as a data-driven adaptive
smoothing classifier. Two right plots (b) provide explanations on the
generalization behavior of different visual prompting methods. While the
vanilla VP applies a single shared prompt to all test inputs that might induce
incorrect transform, e.g., regardless of the true classes (Blue and Green) of
input samples $x_{1}|y=\text{Blue}$ and $x_{2}|y=\text{Green}$, respectively,
they apply the same offset vector that minimizes the expected loss and give a
unified robustness degree, our BlackVIPs can flexibly provide the instance-
specific smoothing distributions that have varying mean and covariance
structures suitable for each data to be correctly classified.

Preliminary and Overview. A classifier $\mathcal{F}(\cdot)$ maps a $d$
dimensional input variable $x\in\mathbb{R}^{d}$ to the categorical variable
$c\in\mathcal{C}$. Here, we define a randomized smoothing classifier
$\mathcal{G}(x):=\operatorname*{arg\,max}_{c}\text{Pr}(\mathcal{F}(x+\varepsilon)=c)$
which returns the class $c$ that maximizes the aggregated classification
probability under Gaussian noise
$\varepsilon\sim\mathcal{N}(0,\sigma^{2}\mathbf{I})$ with an noise intensity
$\sigma$ and an identity matrix $\mathbf{I}$. Some recent works [80, 81]
showed that the smoothed classifier maintains its prediction (the most
probable class) against $l_{2}$-norm bounded perturbations. This robustness
guarantee of the smoothed classifier originated from the additive noise
following a Gaussian distribution. Here, we note that the optimization
trajectory of a visual prompt via stochastic gradient descent (SGD) with a
constant learning rate can be viewed as a sampling process from a Gaussian
posterior distribution that centered at the local optimum defined by the
objective function [82, 83]. This indicates the prompted classifier imitates
the behavior of a smoothed classifier, ensuring robustness against input
perturbations at test time. The illustration in Figure 7 summarizes our
statements.

###  V-A Visual Prompting as Adaptive Randomized Smoothing

Recall the general form of the BlackVIP loss function:

$\displaystyle L(\phi)=-\log{P(y|x+v_{\phi}(x))},$

where $P(y|x)$ is a PTM’s output probability for ground truth $y$ given $x$
and the $v_{\phi}(x)$ is a visual prompt parameterized by $\phi$. This
expression is reduced to the learning objective of VP, when
$v_{\phi}(x)=\phi$. For simplicity, we assume the input-dependent prompt
generation process BlackVIP as $v_{\phi}(x)\approx x\odot\phi$, the Hadamard
product of input $x$ and the learnable parameter $\phi$. We optimize the
visual prompt parameter $\phi$ via SGD with a constant learning rate $\alpha$
as $\phi_{t+1}=\phi_{t}-\alpha\nabla L(\phi_{t})$. As shown in a previous work
[82], given a sufficiently large time step $t$, when the $\phi_{t}$ converges
to the minimum of loss function and $\nabla L(\phi_{t})$ approaches zero,
$\phi^{*}=\phi_{t}=\phi_{t+1},...$ becomes samples from a stationary Gaussian
as below:

$\phi^{*}\sim
N(\mu_{\phi^{*}},\Sigma_{\phi^{*}}),\quad\Sigma_{\phi^{*}}\mathbf{A}+\mathbf{A}\Sigma_{\phi^{*}}=\frac{\alpha}{S}\mathbf{B}\mathbf{B}^{T},$
(5)

where $S$ is the minibatch size. We view $\phi^{*}$ as a random variable near
the minimum of the loss function, showing Gaussian approximation after the
time step $t$ from initialization. Here,
$\mu_{\phi^{*}}:=\operatorname*{arg\,min}_{\phi}-\log{P(y|x+v_{\phi}(x))}$ is
the point where our loss function is minimized, and $\mathbf{A}$ is a Hessian
of loss w.r.t. the optimal point of $\phi^{*}$ and $\mathbf{B}\mathbf{B}^{T}$
is a covariance matrix of the SGD’s gradient noise (See [82]. Now, given that
we repeatedly encounter the same sample data instance $x$ several times during
training, we get the following statement,

$\displaystyle\mathcal{G}_{\phi^{*}}(x)=\operatorname*{arg\,max}_{c\in\mathcal{C}}\text{Pr}(\mathcal{F}(x+v_{\phi^{*}}(x))=c)$
$\displaystyle(i)\,\;v_{\phi^{*}}(x)=\phi^{*}\sim\mathcal{N}(\mu_{\phi^{*}},\Sigma_{\phi^{*}})\quad\textrm{(VP)}$
$\displaystyle(ii)\,v_{\phi^{*}}(x)=x\odot\phi^{*}\sim\mathcal{N}(x\odot\mu_{\phi^{*}},\mathbf{D}_{x}\Sigma_{\phi^{*}}\mathbf{D}_{x})\quad\textrm{(BlackVIP)}$

where $\mathbf{D}_{x}=\textrm{diag}(x)$ given an input $x$. This statement
reveals that a classifier with visual prompt learning can be interpreted as a
randomized smoothing classifier $\mathcal{G}_{\phi^{*}}(x)$ where the location
parameter ($\mu$) of Gaussian distribution is adapted towards a direction that
the downstream classification loss to be minimized. This allows us to leverage
the robustness guarantee [80, 81] of a smoothed classifier for explaining the
generalization behavior of visual prompting.

###  V-B Certified Robustness of Visual Prompting Classifier

In the previous section, we present a new interpretation of visual prompting:
the visual prompting classifier at the later part of the training stage is
approximately an adaptive randomized smoothing classifier. In this section, we
will derive a new statement on the generalization of the visual prompting
classifier during the inference stage: the visual prompting classifier
provides a robustness guarantee against perturbation $\delta$ within the
radius $R$ for a given sample $x$. In other words, it preserves the most
probable class $c$ for the sample $x+\delta$, which a smoothed classifier
$\mathcal{G}_{\phi^{*}}(x)$ returns on the input $x$. Let $c_{A}$ be the most
probable class for given $x$, and $p_{A}$ be the corresponding output
probability of the classifier $\mathcal{F}$. The second most probable class is
similarly defined as $c_{B}$ with the corresponding probability to $p_{B}$.
The probabilities of $p_{A}$ and $p_{B}$ vary by given input, so it is useful
to bound the range of these probabilities and explain the relationship with
the smoothed classifier. We denote $\underline{p_{A}}$ as a lower bound for
$p_{A}$ and $\overline{p_{B}}$ as an upper bound for $p_{B}$ as done in [80].
Now, assume there exists $c_{A}\in\mathcal{C}$ and
$\underline{p_{A}},\overline{p_{B}}$ such that:

$\displaystyle\begin{aligned}
\text{Pr}(\mathcal{F}(x+v_{\phi^{*}}(x))=c_{A})&\geq\underline{p_{A}}\geq\overline{p_{B}}\geq\\\
&\max_{c\neq c_{A}}\text{Pr}(\mathcal{F}(x+v_{\phi^{*}}(x))=c).\end{aligned}$

Then,

$\displaystyle\mathcal{G}_{\phi^{*}}(x+\delta)$
$\displaystyle=c_{A},\;\forall\delta\in\\{\delta:||\delta||_{2}<R\\}$
$\displaystyle\text{where }R$
$\displaystyle=\frac{1}{2}\sqrt{\lambda_{\min}}(\Phi^{-1}(\underline{p_{A}})-\Phi^{-1}(\overline{p_{B}})).$

Here, $\Phi$ denotes the cumulative distribution function (CDF) of
standardized normal distribution and $\lambda_{\min}$ refers to the minimum
eigenvalue of a covariance matrix $\textrm{Cov}(v_{\phi^{*}}(x))$, and the
$\sqrt{\lambda_{\min}}$ is bounded from above by
$\min\\{\sigma_{i}\\}_{i=1}^{d}$ where $\sigma_{i}^{2}$ is the
$i^{th}$-diagonal component of $\textrm{Cov}(v_{\phi^{*}}(x))$ from Rayleigh
quotient, elaborated in Supplementary.

Remark 1) Generalization of Visual Prompting Classifiers. From above
statement, we observed that visual prompting classifier222Given a test sample,
VP and BlackVIP conduct inference with a single prompt in practice, but one
can pursue a more accurate approximation of the behavior of smoothed
classifier by storing SGD samples from the few last iterations and averaging
the classifier’s predictions over them. $\mathcal{G}_{\phi^{*}}$ is robust
around $x+v_{\phi^{*}}(x)$ within the radius $R$, which is impacted by the
minimum variance of visual prompt $\min\\{\sigma_{i}\\}_{i=1}^{d}$ and the
difference between $\underline{p_{A}}$ and $\overline{p_{B}}$. Importantly,
this robustness guarantee is distinctive from that of randomized smoothing
classifier $\mathcal{G}$, which ensures the robust prediction around $x$. That
is, $\mathcal{G}_{\phi^{*}}$ first move the given sample $x$ with a learned
offset direction $v_{\phi^{*}}(x)$ and holds the prediction of base classifier
$\mathcal{F}(x+v_{\phi^{*}}(x))$ for the prompt-augmented sample
$x+v_{\phi^{*}}(x)$ against a perturbation $\delta$, so that it can fix the
incorrect prediction of base classifier $\mathcal{F}(x)$ by a prompt
$v_{\phi}(x)$ learned to minimize the classification loss. Then, if we assume
the test sample is a perturbed version of a train sample, i.e.,
$x_{\text{test}}=x_{\text{train}}+\delta$, and both have the same ground truth
class label $c$, our $\mathcal{G}_{\phi^{*}}$ ensure generalization of the
test sample within $||\delta||_{2}<R$ as it do on the unperturbed train
sample, i.e.,
$\mathcal{G}_{\phi^{*}}(x_{\text{train}})=\mathcal{G}_{\phi^{*}}(x_{\text{test}})=c$.
Here, the radius to ensure such generalization is determined by how large the
minimum variance of a learned visual prompt is and how large the minimum gap
between the top two confidence of the base classifier
($\underline{p_{A}}-\overline{p_{B}}$) given input $x$.

Remark 2) Comparison between VP and BlackVIP.  According to the above
analysis, the following three components are crucial to induce successful
generalization in visual prompting classifiers: 1) learned offset
$v_{\phi^{*}}(x)$, 2) minimum variance among visual prompt elements
$\min\\{\sigma_{i}\\}_{i=1}^{d}$, and 3) the difference between output
probabilities of the most and second-most probable classes from base
classifier $\mathcal{F}$. Because the third component is shared for VP and
BlackVIP, we focus on the first two components for comparison of VP and
BlackVIP in terms of their generalization capability. About the learned offset
$v_{\phi^{*}}(x)$, VP uses a universal prompt $v_{\phi^{*}}(x)=\phi$
regardless of input $x$ while BlackVIP adopt input-dependent prompt
$v_{\phi^{*}}(x)$ which is depend on the input $x$ during both train-time and
test-time. Therefore, our BlackVIP has significantly better capability to
modify the incorrect classification of the base model on train samples,
$\mathcal{F}(x_{\text{train}})$, and results in generalization for test sample
$\mathcal{F}(x_{\text{train}}+\delta)$. Moreover, the radius of robustness
guarantee is much more flexible in BlackVIP due to its input-dependency on the
variance of visual prompt. We speculate that this kind of conditional coverage
of BlackVIP assists flexible generalization depending on the samples’
intrinsic variation, and results in better transfer learning performance
across diverse environments.

##  VI Conclusion

We pioneer black-box visual prompting for the realistic and robust adaptation
of PTMs. We propose BlackVIP and its efficient alternative, BlackVIP-SE, which
reparameterizes the visual prompt with a conditional generation network,
Coordinator. By equipping our new ZOO algorithm, SPSA-GC, BlackVIPs do not
require any accessibility on model architecture or parameters and efficiently
adapt the pre-trained vision model to downstream tasks. Extensive empirical
results on 19 datasets show that BlackVIP and BlackVIP-SE consistently improve
the performance over baseline methods on few-shot adaptation in the wilds,
with minimal computational cost, memory capacity, and API queries. We further
provide theoretical analyses of the generalization of visual prompting methods
by providing a novel connection between the certified robustness of randomized
smoothing and visual prompting.

## References

  * [1] T. Brown, B. Mann, N. Ryder, M. Subbiah, J. D. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam, G. Sastry, A. Askell _et al._ , “Language models are few-shot learners,” _Advances in neural information processing systems_ , vol. 33, pp. 1877–1901, 2020.
  * [2] A. Radford, J. W. Kim, C. Hallacy, A. Ramesh, G. Goh, S. Agarwal, G. Sastry, A. Askell, P. Mishkin, J. Clark _et al._ , “Learning transferable visual models from natural language supervision,” in _International Conference on Machine Learning_. PMLR, 2021, pp. 8748–8763.
  * [3] X. L. Li and P. Liang, “Prefix-tuning: Optimizing continuous prompts for generation,” _arXiv preprint arXiv:2101.00190_ , 2021.
  * [4] M. Jia, L. Tang, B.-C. Chen, C. Cardie, S. Belongie, B. Hariharan, and S.-N. Lim, “Visual prompt tuning,” _arXiv preprint arXiv:2203.12119_ , 2022.
  * [5] H. Bahng, A. Jahanian, S. Sankaranarayanan, and P. Isola, “Visual prompting: Modifying pixel space to adapt pre-trained models,” _arXiv preprint arXiv:2203.17274_ , 2022.
  * [6] M. U. Khattak, H. Rasheed, M. Maaz, S. Khan, and F. S. Khan, “Maple: Multi-modal prompt learning,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2023, pp. 19 113–19 122.
  * [7] A. Dosovitskiy, L. Beyer, A. Kolesnikov, D. Weissenborn, X. Zhai, T. Unterthiner, M. Dehghani, M. Minderer, G. Heigold, S. Gelly _et al._ , “An image is worth 16x16 words: Transformers for image recognition at scale,” in _International Conference on Learning Representations_ , 2020.
  * [8] C. Ju, T. Han, K. Zheng, Y. Zhang, and W. Xie, “Prompting visual-language models for efficient video understanding,” _arXiv preprint arXiv:2112.04478_ , 2021.
  * [9] K. Zhou, J. Yang, C. C. Loy, and Z. Liu, “Learning to prompt for vision-language models,” _International Journal of Computer Vision_ , vol. 130, no. 9, pp. 2337–2348, 2022.
  * [10] K. Zhou, J. Yang, C. C. Loy, and Z. Liu, “Conditional prompt learning for vision-language models,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2022.
  * [11] Y. Zang, W. Li, K. Zhou, C. Huang, and C. C. Loy, “Unified vision and language prompt learning,” _arXiv preprint arXiv:2210.07225_ , 2022.
  * [12] G. Xiao, J. Lin, and S. Han, “Offsite-tuning: Transfer learning without full model,” _arXiv preprint arXiv:2302.04870_ , 2023.
  * [13] J. Spall, “Multivariate stochastic approximation using a simultaneous perturbation gradient approximation,” _IEEE Transactions on Automatic Control_ , vol. 37, no. 3, pp. 332–341, 1992.
  * [14] C. Oh, H. Hwang, H.-y. Lee, Y. Lim, G. Jung, J. Jung, H. Choi, and K. Song, “Blackvip: Black-box visual prompting for robust transfer learning,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2023, pp. 24 224–24 235.
  * [15] S. Chen, C. Ge, Z. Tong, J. Wang, Y. Song, J. Wang, and P. Luo, “Adaptformer: Adapting vision transformers for scalable visual recognition,” _arXiv preprint arXiv:2205.13535_ , 2022.
  * [16] Z. Chen, Y. Duan, W. Wang, J. He, T. Lu, J. Dai, and Y. Qiao, “Vision transformer adapter for dense predictions,” in _The Eleventh International Conference on Learning Representations_ , 2023.
  * [17] P. Gao, S. Geng, R. Zhang, T. Ma, R. Fang, Y. Zhang, H. Li, and Y. Qiao, “Clip-adapter: Better vision-language models with feature adapters,” _arXiv preprint arXiv:2110.04544_ , 2021.
  * [18] R. Zhang, W. Zhang, R. Fang, P. Gao, K. Li, J. Dai, Y. Qiao, and H. Li, “Tip-adapter: Training-free adaption of clip for few-shot classification,” in _European conference on computer vision_. Springer, 2022.
  * [19] Y. Ouali, A. Bulat, B. Matinez, and G. Tzimiropoulos, “Black box few-shot adaptation for vision-language models,” in _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 2023.
  * [20] M. Zhang and C. Ré, “Contrastive adapters for foundation model group robustness,” _Advances in Neural Information Processing Systems_ , vol. 35, pp. 21 682–21 697, 2022.
  * [21] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, and I. Polosukhin, “Attention is all you need,” _Advances in neural information processing systems_ , vol. 30, 2017.
  * [22] K. Zhou, J. Yang, C. C. Loy, and Z. Liu, “Learning to prompt for vision-language models,” _International Journal of Computer Vision (IJCV)_ , 2022.
  * [23] B. Zhu, Y. Niu, Y. Han, Y. Wu, and H. Zhang, “Prompt-aligned gradient for prompt tuning,” in _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 2023, pp. 15 659–15 669.
  * [24] S. Ren, A. Zhang, Y. Zhu, S. Zhang, S. Zheng, M. Li, A. J. Smola, and X. Sun, “Prompt pre-training with twenty-thousand classes for open-vocabulary visual recognition,” _Advances in Neural Information Processing Systems_ , vol. 36, 2023.
  * [25] Q. Huang, X. Dong, D. Chen, W. Zhang, F. Wang, G. Hua, and N. Yu, “Diversity-aware meta visual prompting,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2023, pp. 10 878–10 887.
  * [26] A. Chen, Y. Yao, P.-Y. Chen, Y. Zhang, and S. Liu, “Understanding and improving visual prompting: A label-mapping perspective,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2023, pp. 19 133–19 143.
  * [27] L. Yang, Y. Wang, X. Li, X. Wang, and J. Yang, “Fine-grained visual prompting,” _Advances in Neural Information Processing Systems_ , vol. 36, 2023.
  * [28] Y.-L. Sung, J. Cho, and M. Bansal, “Lst: Ladder side-tuning for parameter and memory efficient transfer learning,” _Advances in Neural Information Processing Systems_ , vol. 35, pp. 12 991–13 005, 2022.
  * [29] B. Liao, S. Tan, and C. Monz, “Make your pre-trained model reversible: From parameter to memory efficient fine-tuning,” _arXiv preprint arXiv:2306.00477_ , 2023.
  * [30] J. Kim, J. H. Lee, S. Kim, J. Park, K. M. Yoo, S. J. Kwon, and D. Lee, “Memory-efficient fine-tuning of compressed large language models via sub-4-bit integer quantization,” _Advances in Neural Information Processing Systems_ , vol. 36, 2023.
  * [31] T. Sun, Y. Shao, H. Qian, X. Huang, and X. Qiu, “Black-box tuning for language-model-as-a-service,” in _Proceedings of ICML_ , 2022.
  * [32] T. Sun, Z. He, H. Qian, Y. Zhou, X. Huang, and X. Qiu, “Bbtv2: Towards a gradient-free future with large language models,” in _Proceedings of EMNLP_ , 2022.
  * [33] M. Deng, J. Wang, C.-P. Hsieh, Y. Wang, H. Guo, T. Shu, M. Song, E. P. Xing, and Z. Hu, “Rlprompt: Optimizing discrete text prompts with reinforcement learning,” _arXiv preprint arXiv:2205.12548_ , 2022.
  * [34] Y.-Y. Tsai, P.-Y. Chen, and T.-Y. Ho, “Transfer learning without knowing: Reprogramming black-box machine learning models with scarce data and limited resources,” in _International Conference on Machine Learning_. PMLR, 2020, pp. 9614–9624.
  * [35] J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei, “Imagenet: A large-scale hierarchical image database,” in _2009 IEEE Conference on Computer Vision and Pattern Recognition_ , 2009, pp. 248–255.
  * [36] N. Hansen and A. Ostermeier, “Completely derandomized self-adaptation in evolution strategies,” _Evolutionary computation_ , vol. 9, no. 2, pp. 159–195, 2001.
  * [37] N. Hansen, S. D. Müller, and P. Koumoutsakos, “Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (cma-es),” _Evolutionary computation_ , vol. 11, no. 1, pp. 1–18, 2003.
  * [38] S. Liu, P.-Y. Chen, B. Kailkhura, G. Zhang, A. O. Hero III, and P. K. Varshney, “A primer on zeroth-order optimization in signal processing and machine learning: Principals, recent advances, and applications,” _IEEE Signal Processing Magazine_ , vol. 37, no. 5, pp. 43–54, 2020.
  * [39] T. Zhao, H. Hachiya, G. Niu, and M. Sugiyama, “Analysis and improvement of policy gradient estimation,” _Advances in Neural Information Processing Systems_ , vol. 24, 2011.
  * [40] J. C. Spall, “An overview of the simultaneous perturbation method for efficient optimization,” _Johns Hopkins apl technical digest_ , vol. 19, no. 4, pp. 482–492, 1998.
  * [41] G. F. Elsayed, I. Goodfellow, and J. Sohl-Dickstein, “Adversarial reprogramming of neural networks,” _arXiv preprint arXiv:1806.11146_ , 2018.
  * [42] I. J. Goodfellow, J. Shlens, and C. Szegedy, “Explaining and harnessing adversarial examples,” _arXiv preprint arXiv:1412.6572_ , 2014.
  * [43] N. Papernot, P. McDaniel, S. Jha, M. Fredrikson, Z. B. Celik, and A. Swami, “The limitations of deep learning in adversarial settings,” in _IEEE European Symposium on Security and Privacy (EuroS &P)_, 2016.
  * [44] H. Xu, Y. Ma, H.-C. Liu, D. Deb, H. Liu, J.-L. Tang, and A. K. Jain, “Adversarial attacks and defenses in images, graphs and text: A review,” _International Journal of Automation and Computing_ , vol. 17, no. 2, pp. 151–178, 2020.
  * [45] P. Neekhara, S. Hussain, J. Du, S. Dubnov, F. Koushanfar, and J. McAuley, “Cross-modal adversarial reprogramming,” in _Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision_ , 2022, pp. 2427–2435.
  * [46] P.-Y. Chen, “Model reprogramming: Resource-efficient cross-domain machine learning,” _arXiv preprint arXiv:2202.10629_ , 2022.
  * [47] I. Melnyk, V. Chenthamarakshan, P.-Y. Chen, P. Das, A. Dhurandhar, I. Padhi, and D. Das, “Reprogramming large pretrained language models for antibody sequence infilling,” _arXiv preprint arXiv:2210.07144_ , 2022.
  * [48] M. Caron, H. Touvron, I. Misra, H. Jégou, J. Mairal, P. Bojanowski, and A. Joulin, “Emerging properties in self-supervised vision transformers,” in _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 2021, pp. 9650–9660.
  * [49] K. He, X. Chen, S. Xie, Y. Li, P. Dollár, and R. Girshick, “Masked autoencoders are scalable vision learners,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2022.
  * [50] Y. Li, S. Xie, X. Chen, P. Dollar, K. He, and R. Girshick, “Benchmarking detection transfer learning with vision transformers,” _arXiv preprint arXiv:2111.11429_ , 2021.
  * [51] H. Liu, J. Z. HaoChen, A. Gaidon, and T. Ma, “Self-supervised learning is more robust to dataset imbalance,” in _International Conference on Learning Representations_ , 2022.
  * [52] G. Huang, I. Laradji, D. Vázquez, S. Lacoste-Julien, and P. Rodriguez, “A survey of self-supervised and few-shot object detection,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 2022.
  * [53] Y. Fang, S. Yang, S. Wang, Y. Ge, Y. Shan, and X. Wang, “Unleashing vanilla vision transformer with masked image modeling for object detection,” _arXiv preprint arXiv:2204.02964_ , 2022.
  * [54] J. Pan, P. Zhou, and S. Yan, “Towards understanding why mask-reconstruction pretraining helps in downstream tasks,” _arXiv preprint arXiv:2206.03826_ , 2022.
  * [55] R. Wightman, “Pytorch image models,” https://github.com/rwightman/pytorch-image-models, 2019.
  * [56] B. Neyshabur, H. Sedghi, and C. Zhang, “What is being transferred in transfer learning?” _Advances in neural information processing systems_ , vol. 33, pp. 512–523, 2020.
  * [57] J. C. Spall, “A one-measurement form of simultaneous perturbation stochastic approximation,” _Automatica_ , vol. 33, no. 1, 1997.
  * [58] J. Spall, _Introduction to Stochastic Search and Optimization_ , 1st ed. USA: John Wiley & Sons, Inc., 2003.
  * [59] Q. Song, J. C. Spall, Y. C. Soh, and J. Ni, “Robust neural network tracking controller using simultaneous perturbation stochastic approximation,” _IEEE Transactions on Neural Networks_ , vol. 19, no. 5, pp. 817–835, 2008.
  * [60] D. Stein, J. Schwenninger, and M. Stadtschnitzer, “Simultaneous perturbation stochastic approximation for automatic speech recognition,” in _Proc. Interspeech 2013_ , 2013, pp. 622–626.
  * [61] A. Boiarov, O. Granichin, and O. Granichina, “Simultaneous perturbation stochastic approximation for few-shot learning,” in _2020 European Control Conference (ECC)_ , 2020, pp. 350–355.
  * [62] J. Spall, “Adaptive stochastic approximation by the simultaneous perturbation method,” _IEEE Transactions on Automatic Control_ , vol. 45, no. 10, pp. 1839–1853, 2000.
  * [63] J. C. Spall, “Accelerated second-order stochastic optimization using only function measurements,” _Proceedings of the 36th IEEE Conference on Decision and Control_ , vol. 2, pp. 1417–1424 vol.2, 1997.
  * [64] Y. Nesterov, “A method for solving the convex programming problem with convergence rate $o(1/k^{2})$,” _Proceedings of the USSR Academy of Sciences_ , vol. 269, pp. 543–547, 1983.
  * [65] I. Sutskever, J. Martens, G. Dahl, and G. Hinton, “On the importance of initialization and momentum in deep learning,” in _Proceedings of the 30th International Conference on Machine Learning_ , ser. Proceedings of Machine Learning Research, vol. 28, no. 3. PMLR, 17–19 Jun 2013.
  * [66] P. W. Koh, S. Sagawa, H. Marklund, S. M. Xie, M. Zhang, A. Balsubramani, W. Hu, M. Yasunaga, R. L. Phillips, I. Gao _et al._ , “Wilds: A benchmark of in-the-wild distribution shifts,” in _International conference on machine learning_. PMLR, 2021, pp. 5637–5664.
  * [67] L. Van der Maaten and G. Hinton, “Visualizing data using t-sne.” _Journal of machine learning research_ , vol. 9, no. 11, 2008.
  * [68] J. Loedeman, M. C. Stol, T. Han, and Y. M. Asano, “Prompt generation networks for efficient adaptation of frozen vision transformers,” _arXiv preprint arXiv:2210.06466_ , 2022.
  * [69] S. Liu, B. Kailkhura, P.-Y. Chen, P. Ting, S. Chang, and L. Amini, “Zeroth-order stochastic variance reduction for nonconvex optimization,” _Advances in Neural Information Processing Systems_ , vol. 31, 2018.
  * [70] H. Bahng, S. Chun, S. Yun, J. Choo, and S. J. Oh, “Learning de-biased representations with biased representations,” in _International Conference on Machine Learning_. PMLR, 2020, pp. 528–539.
  * [71] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner, “Gradient-based learning applied to document recognition,” _Proceedings of the IEEE_ , vol. 86, no. 11, pp. 2278–2324, 1998.
  * [72] M. Cimpoi, S. Maji, I. Kokkinos, S. Mohamed, and A. Vedaldi, “Describing textures in the wild,” in _2014 IEEE Conference on Computer Vision and Pattern Recognition_ , 2014, pp. 3606–3613.
  * [73] P. Helber, B. Bischke, A. Dengel, and D. Borth, “Eurosat: A novel dataset and deep learning benchmark for land use and land cover classification,” _IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing_ , vol. 12, no. 7, pp. 2217–2226, 2019.
  * [74] G. Cheng, J. Han, and X. Lu, “Remote sensing image scene classification: Benchmark and state of the art,” _Proceedings of the IEEE_ , vol. 105, no. 10, pp. 1865–1883, 2017.
  * [75] J. Johnson, B. Hariharan, L. Van Der Maaten, L. Fei-Fei, C. Lawrence Zitnick, and R. Girshick, “Clevr: A diagnostic dataset for compositional language and elementary visual reasoning,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2017, pp. 2901–2910.
  * [76] C. Li, H. Farkhoor, R. Liu, and J. Yosinski, “Measuring the intrinsic dimension of objective landscapes,” in _International Conference on Learning Representations_ , 2018.
  * [77] P. Pope, C. Zhu, A. Abdelkader, M. Goldblum, and T. Goldstein, “The intrinsic dimension of images and its impact on learning,” in _International Conference on Learning Representations_ , 2021.
  * [78] T. Hastie, R. Tibshirani, J. H. Friedman, and J. H. Friedman, _The elements of statistical learning: data mining, inference, and prediction_. Springer, 2009, vol. 2.
  * [79] J. Kaplan, S. McCandlish, T. Henighan, T. B. Brown, B. Chess, R. Child, S. Gray, A. Radford, J. Wu, and D. Amodei, “Scaling laws for neural language models,” _arXiv preprint arXiv:2001.08361_ , 2020.
  * [80] J. Cohen, E. Rosenfeld, and Z. Kolter, “Certified adversarial robustness via randomized smoothing,” in _international conference on machine learning_. PMLR, 2019, pp. 1310–1320.
  * [81] H. Hong and Y. Hong, “Certified adversarial robustness via anisotropic randomized smoothing,” _arXiv preprint arXiv:2207.05327_ , 2022.
  * [82] M. Stephan, M. D. Hoffman, D. M. Blei _et al._ , “Stochastic gradient descent as approximate bayesian inference,” _Journal of Machine Learning Research_ , vol. 18, no. 134, pp. 1–35, 2017.
  * [83] Y. Wu, R. Luo, C. Zhang, J. Wang, and Y. Yang, “Revisiting the characteristics of stochastic gradient noise and dynamics,” _arXiv preprint arXiv:2109.09833_ , 2021.
  * [84] R. A. Horn and C. R. Johnson, _Matrix analysis_. Cambridge university press, 2012.
  * [85] L. Fei-Fei, R. Fergus, and P. Perona, “Learning generative visual models from few training examples: An incremental bayesian approach tested on 101 object categories,” in _2004 Conference on Computer Vision and Pattern Recognition Workshop_ , 2004, pp. 178–178.
  * [86] O. M. Parkhi, A. Vedaldi, A. Zisserman, and C. V. Jawahar, “Cats and dogs,” in _2012 IEEE Conference on Computer Vision and Pattern Recognition_ , 2012, pp. 3498–3505.
  * [87] J. Krause, M. Stark, J. Deng, and L. Fei-Fei, “3d object representations for fine-grained categorization,” in _2013 IEEE International Conference on Computer Vision Workshops_ , 2013, pp. 554–561.
  * [88] M.-E. Nilsback and A. Zisserman, “Automated flower classification over a large number of classes,” in _2008 Sixth Indian Conference on Computer Vision, Graphics & Image Processing_, 2008, pp. 722–729.
  * [89] L. Bossard, M. Guillaumin, and L. Van Gool, “Food-101 – mining discriminative components with random forests,” in _Computer Vision – ECCV 2014_ , D. Fleet, T. Pajdla, B. Schiele, and T. Tuytelaars, Eds. Cham: Springer International Publishing, 2014, pp. 446–461.
  * [90] S. Maji, E. Rahtu, J. Kannala, M. Blaschko, and A. Vedaldi, “Fine-grained visual classification of aircraft,” _arXiv preprint arXiv:1306.5151_ , 2013.
  * [91] J. Xiao, J. Hays, K. A. Ehinger, A. Oliva, and A. Torralba, “Sun database: Large-scale scene recognition from abbey to zoo,” in _2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition_ , 2010, pp. 3485–3492.
  * [92] Y. Netzer, T. Wang, A. Coates, A. Bissacco, B. Wu, and A. Y. Ng, “Reading digits in natural images with unsupervised feature learning,” in _NIPS Workshop on Deep Learning and Unsupervised Feature Learning 2011_ , 2011. [Online]. Available: http://ufldl.stanford.edu/housenumbers/nips2011_housenumbers.pdf
  * [93] K. Soomro, A. R. Zamir, and M. Shah, “Ucf101: A dataset of 101 human actions classes from videos in the wild,” _arXiv preprint arXiv:1212.0402_ , 2012.
  * [94] P. Bandi, O. Geessink, Q. Manson, M. Van Dijk, M. Balkenhol, M. Hermsen, B. E. Bejnordi, B. Lee, K. Paeng, A. Zhong _et al._ , “From detection of individual metastases to classification of lymph node status at the patient level: the camelyon17 challenge,” _IEEE transactions on medical imaging_ , vol. 38, no. 2, pp. 550–560, 2018.
  * [95] G. Christie, N. Fendley, J. Wilson, and R. Mukherjee, “Functional map of the world,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2018, pp. 6172–6180.
  * [96] S. Beery, A. Agarwal, E. Cole, and V. Birodkar, “The iwildcam 2021 competition dataset,” _arXiv preprint arXiv:2105.03494_ , 2021.
  * [97] C. Jia, Y. Yang, Y. Xia, Y.-T. Chen, Z. Parekh, H. Pham, Q. Le, Y.-H. Sung, Z. Li, and T. Duerig, “Scaling up visual and vision-language representation learning with noisy text supervision,” in _International Conference on Machine Learning_. PMLR, 2021, pp. 4904–4916.
  * [98] Y. Nesterov and V. Spokoiny, “Random gradient-free minimization of convex functions,” _Found. Comput. Math._ , vol. 17, no. 2, p. 527–566, apr 2017. [Online]. Available: https://doi.org/10.1007/s10208-015-9296-2
  * [99] F. Chollet, “Xception: Deep learning with depthwise separable convolutions,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2017, pp. 1251–1258.
  * [100] R. R. Selvaraju, M. Cogswell, A. Das, R. Vedantam, D. Parikh, and D. Batra, “Grad-cam: Visual explanations from deep networks via gradient-based localization,” in _Proceedings of the IEEE international conference on computer vision_ , 2017, pp. 618–626.

Changdae Oh is currently a Ph.D. student at Department of Computer Sciences at
University of Wisconsin-Madison, and he received his bachelor’s degree in
Statistics and his master’s in Artificial Intelligence from University of
Seoul in 2022 and 2024, respectively.
---
Gyeongdeok Seo is currently a Master’s degree student at the Department of
Statistics and Data Science at Yonsei University. He received his bachelor’s
degree in Applied Statistics from Yonsei University in 2022 and worked as a
Data Analyst at Naver Financial in 2022-2024.
---
Geunyoung Jung is currently an integrated Ph.D. student at the Department of
Artificial Intelligence at University of Seoul, and he received his bachelor’s
degree in Physics from University of Seoul in 2022.
---
Zhi-Qi Cheng is a Project Scientist at the Language Technologies Institute
(LTI), which is part of the School of Computer Science at Carnegie Mellon
University (CMU). He earned his B.S. in Computer Science from Southwest
Jiaotong University in 2014 and completed his Ph.D. in 2019. During his
doctoral studies, he was a visiting Ph.D. student at the City University of
Hong Kong (2016-2017) and later at CMU (2017-2019). He also gained valuable
experience through internships at Alibaba DAMO Academy (2016), Google Brain
(2018), and Microsoft Research (2019). From 2019 to 2022, he served as a
postdoctoral research associate at CMU.
---
Hosik Choi received the B.S. and Ph.D. degrees in Statistics from the Seoul
National University, in 2000 and 2007. He is currently a Professor at
Department of Urban Big Data Convergence, and an Adjunct Professor at
Department of Artificial Intelligence at University of Seoul (UOS). Before
joining UOS, he was a full-time Lecturer and Assistant Professor at Hoseo
University from 2008 to 2014. Then, he was an Assistant/Associate Professor at
Department of Applied Statistics, Kyonggi University from 2014 to 2020. In
2023, he was a Visiting Professor at Korea Institute for Advanced Study.
---
Jiyoung Jung received the B.S., M.S., and Ph.D. degrees in Electrical
Engineering from the Korea Advanced Institute of Science and Technology
(KAIST), in 2008, 2010, and 2016, respectively. She is currently an Associate
Professor at the Department of Artificial Intelligence, University of Seoul.
She joined the department in September 2021. She served as an Assistant
Professor at the Department of Software Convergence, Kyung Hee University in
2017-2021. Previously, she worked as a research engineer at Naver Labs.
---
Kyungwoo Song received the B.S. degree in mathematical sciences and industrial
and systems engineering and the M.S. and Ph.D. degrees in industrial and
systems engineering from the Korea Advanced Institute of Science and
Technology (KAIST), in 2017 and 2021. In 2017, he was a part-time Professor
with Hanbat National University. In 2018, he was a Visiting Researcher with
Naver Clova. From 2021 to 2023, he was an Assistant Professor with the
Department of Artificial Intelligence, University of Seoul. He is currently an
Assistant Professor with the Department of Applied Statistics and the
Department of Statistics and Data Science, Yonsei University
---

##  Appendix A Details of Theoretical Analysis

###  A-A Normal Approximation

The approximation of updating parameters to sampling from a normal
distribution is based on the fact that batch-wise updates introduce
variability in the gradient of the loss function. As the batch size $S$
increases, the gradient noise converges to a normal distribution according to
a central limit theorem. The central limit theorem is applied under the
assumption that a stochastic gradient is the sum of independent and uniform
sampled $S$, which is illustrated below:

$\displaystyle\nabla\hat{L}_{S}(\phi)\xrightarrow{d}\mathcal{N}(\nabla
L(\phi),\frac{1}{S}C(\phi)).$

We also assume that the variance of this gradient noise is approximated by the
constant matrix $\mathbf{C}=\mathbf{B}\mathbf{B}^{T}$, where $\mathbf{C}$ is
factorized into $\mathbf{B}\mathbf{B}^{T}$. Including these assumptions, If
the four assumptions detailed in the research [82] are met, then the update of
$\phi$ corresponds to sampling from the stationary distribution of an
Ornstein-Uhlenbeck process as [82] shows, where:

$\displaystyle
q(\phi)\propto\exp\\{-\frac{1}{2}\phi^{T}\Sigma_{\phi}^{-1}\phi\\}$

In this context, the covariance $\Sigma_{\phi}$ satisfies
$\Sigma_{\phi}\mathbf{A}+\mathbf{A}\Sigma_{\phi}=\frac{\alpha}{S}\mathbf{B}\mathbf{B}^{T}$,
with $\mathbf{A}$ being the hessian matrix at the optimal point.

###  A-B Randomized Smoothing and Certified Robustness

A smoothed classifier exhibits robust properties within a radius $R$.
Specifically, when an input is perturbed within the ball
$B(x,R)=\\{y:||x-y||<R\\}$, the classification consistently predicts the most
probable class. Building upon the foundational work by [80] which introduced a
certified radius for a smoothed classifier using an isotropic Gaussian
covariance, and further extensions by [81] to an anisotropic Gaussian model
with a diagonal covariance matrix, our analysis advances these models by
relaxing the diagonal constraint on the covariance matrix, thus proposing a
more generalized form and redefining the radius based on the derived proof.

To set the stage for our proof, consider the following settings:

$\displaystyle
X=x+\phi^{*}\sim\mathcal{N}_{d}(x+\mu_{\phi^{*}},\Sigma_{\phi^{*}})$
$\displaystyle
X^{*}=x+\phi^{*}+\delta\sim\mathcal{N}_{d}(x+\mu_{\phi^{*}}+\delta,\Sigma_{\phi^{*}}).$

We examine the ratio of the probability density functions of $X^{*}$ and $X$,
which manifests in an exponential form with the precision matrix
$K=\Sigma_{\phi^{*}}^{-1}$. The ratio $\frac{p_{X^{*}}(z)}{p_{X}(z)}$ is given
by:

$\displaystyle\frac{\exp\\{-\frac{1}{2}(z-(x+\mu_{\phi^{*}}+\delta))^{T}K(z-(x+\mu_{\phi^{*}}+\delta))\\}}{\exp\\{-\frac{1}{2}(z-(x+\mu_{\phi^{*}}))^{T}K(z-(x+\mu_{\phi^{*}}))\\}}$
$\displaystyle=\exp\\{\frac{1}{2}(2\delta^{T}Kz-2\delta^{T}K(x+\mu_{\phi^{*}})-\delta^{T}K\delta)\\}$
$\displaystyle=\exp\\{\delta^{T}Kz-\delta^{T}K(x+\mu_{\phi^{*}})-\frac{1}{2}\delta^{T}K\delta\\}$
$\displaystyle=\exp\\{\delta^{T}Kz-\tau\\}$

where $\tau=\delta^{T}K(x+\mu_{\phi^{*}})+\dfrac{1}{2}\delta^{T}K\delta$. This
leads us to the following inequality:

$\displaystyle\exp\\{\delta^{T}Kz-\tau\\}\leq
w\Longleftrightarrow\delta^{T}Kz\leq\log{w}+\tau=\eta.$

Leveraging the Neyman-Pearson theorem in [80], we establish that if the
following condition holds for any binary classifier
$\mathcal{F}_{\textrm{bin}}:\mathbb{R}^{d}\rightarrow\\{0,1\\}$:

$\displaystyle\text{Pr}(\mathcal{F}_{\textrm{bin}}(X)=1)\geq\text{Pr}(X\in\Omega)$
$\displaystyle\Omega=\\{z\in$
$\displaystyle\mathbb{R}^{d}:\frac{p_{X^{*}}(z)}{p_{X}(z)}\leq w\\}\textrm{
for some }w>0$

then it must hold that
$\text{Pr}(\mathcal{F}_{\textrm{bin}}(X^{*})=1)\geq\text{Pr}(X^{*}\in\Omega)$.
This statement is also satisfied when the direction of the inequality is
reversed:

$\displaystyle\text{Pr}(\mathcal{F}_{\textrm{bin}}(X)=1)\leq\text{Pr}(X\in\Omega)$
$\displaystyle\Omega=\\{z\in$
$\displaystyle\mathbb{R}^{d}:\frac{p_{X^{*}}(z)}{p_{X}(z)}\geq w\\}\textrm{
for some }w>0$

indicating that
$\text{Pr}(\mathcal{F}_{\textrm{bin}}(X^{*})=1)\leq\text{Pr}(X^{*}\in\Omega)$
is also true. This principle underpins our main claim. Suppose there exists a
class $c_{A}$ within the set $\mathcal{C}$ with probability $p_{A}$ bounded by
$\underline{p_{A}}$ and $\overline{p_{B}}$ such that:

$\displaystyle\text{Pr}(\mathcal{F}(x+\phi^{*})=c_{A})$
$\displaystyle\geq\underline{p_{A}}\geq\overline{p_{B}}\geq$
$\displaystyle\max_{c\neq c_{A}}\text{Pr}(\mathcal{F}(x+\phi^{*})=c).$

Then, it necessarily follows that:

$\displaystyle\mathcal{G}_{\phi^{*}}(x+\delta)$
$\displaystyle=c_{A},\;\forall\delta\in\\{\delta:||\delta||_{2}<R\\}$
$\displaystyle\text{where }R$
$\displaystyle=\frac{1}{2}\sqrt{\lambda_{\min}}(\Phi^{-1}(\underline{p_{A}})-\Phi^{-1}(\overline{p_{B}})).$

The result means that our smoothed classifier $\mathcal{G}_{\phi^{*}}$ retains
the most probable class of the original classifier even in the presence of
input perturbation. Formally, it implies that
$\text{Pr}(\mathcal{F}(X^{*})=c_{A})$ is at least as large as
$\text{Pr}(\mathcal{F}(X^{*})=c)$ for any $c\in\mathcal{C}-\\{c_{A}\\}$.
Without loss of generality, we fix $c$ as $c_{B}$ which is the second most
probable class, then we need to show that
$\text{Pr}(\mathcal{F}(X^{*})=c_{A})\geq\text{Pr}(\mathcal{F}(X^{*})=c_{B})$.
The bounds for probabilities $\underline{p_{A}}$ and $\overline{p_{B}}$ can be
expressed as $\text{Pr}(X\in\Omega_{A})$ and $\text{Pr}(X\in\Omega_{B})$ when
the regions $\Omega_{A}$ and $\Omega_{B}$ are given by:

$\displaystyle\Omega_{A}=\\{z:\delta^{T}K(z-(x+\mu_{\phi^{*}}))^{T}\leq\kappa\Phi^{-1}(\underline{p_{A}})\\}$
$\displaystyle\Omega_{B}=\\{z:\delta^{T}K(z-(x+\mu_{\phi^{*}}))^{T}\geq\kappa\Phi^{-1}(1-\overline{p_{B}})\\}.$

In defining these regions, we denote $\kappa$ as the norm
$=||\delta^{T}\Sigma_{\phi^{*}}^{-1/2}||_{2}.$ To further clarify the
discussion, we define several useful random variables transformed from $X$:

$\displaystyle Y=X-(x+\mu_{\phi^{*}})\sim\mathcal{N}_{d}(0,\Sigma_{\phi^{*}})$
$\displaystyle
Y^{*}=X-(x+\mu_{\phi^{*}}+\delta)\sim\mathcal{N}_{d}(\delta,\Sigma_{\phi^{*}})$
$\displaystyle\Xi=\Sigma_{\phi^{*}}^{-1/2}Y\sim\mathcal{N}_{d}(0,\mathbf{I})$
$\displaystyle Z\sim\mathcal{N}(0,1).$

We show $\text{Pr}(X\in\Omega_{A})=\underline{p_{A}}$ as follows:

$\displaystyle\text{Pr}(X\in\Omega_{A})$
$\displaystyle=\text{Pr}(\delta^{T}K(X-x-\mu_{\phi^{*}})\leq\kappa\Phi^{-1}(\underline{p_{A}}))$
$\displaystyle=\text{Pr}(\delta^{T}KY\leq\kappa\Phi^{-1}(\underline{p_{A}}))$
$\displaystyle=\text{Pr}(\delta^{T}K\Sigma_{\phi^{*}}^{1/2}\Xi\leq\kappa\Phi^{-1}(\underline{p_{A}}))$
$\displaystyle=\text{Pr}(\delta^{T}\Sigma_{\phi^{*}}^{-1/2}\Xi\leq\kappa\Phi^{-1}(\underline{p_{A}}))$
$\displaystyle=\text{Pr}(||\delta^{T}\Sigma_{\phi^{*}}^{-1/2}||_{2}Z\leq\kappa\Phi^{-1}(\underline{p_{A}}))$
$\displaystyle=\text{Pr}(Z\leq\Phi^{-1}(\underline{p_{A}}))$
$\displaystyle=\underline{p_{A}}.$

Here, $\delta^{T}\Sigma_{\phi^{*}}^{-1/2}$ is a row vector in
$\mathbb{R}^{1\times d}$ and a random vector $\Xi$ in $\mathbb{R}^{d\times 1}$
follows a multivariate standard normal distribution. The inner product of
theses vectors results in a weighted sum of univariate standard normal
distributions, which reduces to a univariate normal distribution scaled by the
constant $\kappa$. For $\Omega_{B}$, the probability is calculated as:

$\displaystyle\text{Pr}(X\in\Omega_{B})$
$\displaystyle=\text{Pr}(\delta^{T}K(X-x-\mu_{\phi^{*}})\geq\kappa\Phi^{-1}(1-\overline{p_{B}}))$
$\displaystyle=\text{Pr}(\delta^{T}KY\geq\kappa\Phi^{-1}(1-\overline{p_{B}}))$
$\displaystyle=\text{Pr}(\delta^{T}K\Sigma_{\phi^{*}}^{1/2}\Xi\geq\kappa\Phi^{-1}(1-\overline{p_{B}}))$
$\displaystyle=\text{Pr}(\delta^{T}\Sigma_{\phi^{*}}^{-1/2}\Xi\geq\kappa\Phi^{-1}(1-\overline{p_{B}}))$
$\displaystyle=\text{Pr}(||\delta^{T}\Sigma_{\phi^{*}}^{-1/2}||_{2}Z\geq\kappa\Phi^{-1}(1-\overline{p_{B}}))$
$\displaystyle=\text{Pr}(Z\geq\Phi^{-1}(1-\overline{p_{B}}))$
$\displaystyle=\overline{p_{B}}.$

We can modify our initial assumption by replacing $\underline{p_{A}}$ to
$\text{Pr}(X\in\Omega_{A})$ and $\overline{p_{B}}$ to
$\text{Pr}(X\in\Omega_{B})$.

$\displaystyle\text{Pr}(\mathcal{F}(X)=c_{A})\geq\text{Pr}(X\in\Omega_{A})$
$\displaystyle\text{Pr}(\mathcal{F}(X)=c_{B})\leq\text{Pr}(X\in\Omega_{B}).$

We utilize Neyman-Pearson theorem by defining
$\mathcal{F}_{\textrm{bin}}(z)=I[\mathcal{F}(z)=c_{A}]$ where $I$ is an
indicator function, then the result are ensured

$\displaystyle\text{Pr}(\mathcal{F}(X^{*})=c_{A})\geq\text{Pr}(X^{*}\in\Omega_{A})$
$\displaystyle\text{Pr}(\mathcal{F}(X^{*})=c_{B})\leq\text{Pr}(X^{*}\in\Omega_{B}).$

If $\text{Pr}(X^{*}\in\Omega_{A})\geq\text{Pr}(X^{*}\in\Omega_{B})$ is
satisfied,
$\text{Pr}(\mathcal{F}(X^{*})=c_{A})\geq\text{Pr}(\mathcal{F}(X^{*})=c_{B})$
is held with a certain radius, which is the destination of our proof.

$\displaystyle\text{Pr}(\mathcal{F}(x+\phi+\delta)=c_{A})\geq\max_{c\neq
c_{A}}\text{Pr}(\mathcal{F}(x+\phi+\delta)=c).$

To show the inequality, we plug in the space $\Omega_{A}$ we defined into
$\text{Pr}(X^{*}\in\Omega_{A})$

$\displaystyle\text{Pr}(X^{*}\in\Omega_{A})$
$\displaystyle=\text{Pr}(\delta^{T}K(X^{*}-x-\mu_{\phi^{*}})\leq\kappa\Phi^{-1}(\underline{p_{A}}))$
$\displaystyle=\text{Pr}(\delta^{T}KY^{*}\leq\kappa\Phi^{-1}(\underline{p_{A}}))$
$\displaystyle=\text{Pr}(\delta^{T}KY+\delta^{T}K\delta\leq\kappa\Phi^{-1}(\underline{p_{A}}))$
$\displaystyle=\text{Pr}(\delta^{T}\Sigma_{\phi^{*}}^{-1/2}\Xi\leq\kappa\Phi^{-1}(\underline{p_{A}})-\delta^{T}K\delta)$
$\displaystyle=\text{Pr}(\kappa
Z\leq\kappa(\Phi^{-1}(\underline{p_{A}})-\frac{1}{\kappa}\delta^{T}K\delta))$
$\displaystyle=\text{Pr}(Z\leq\Phi^{-1}(\underline{p_{A}})-\frac{1}{\kappa}\delta^{T}K\delta)$
$\displaystyle=\Phi(\Phi^{-1}(\underline{p_{A}})-\frac{1}{\kappa}\delta^{T}K\delta).$

We follow a similar procedure for the space $\Omega_{B}$

$\displaystyle\text{Pr}(X^{*}\in\Omega_{B})$
$\displaystyle=\text{Pr}(\delta^{T}K(X^{*}-x-\mu_{\phi^{*}})\geq\kappa\Phi^{-1}(1-\overline{p_{B}}))$
$\displaystyle=\text{Pr}(\delta^{T}KY^{*}\geq\kappa\Phi^{-1}(1-\overline{p_{B}}))$
$\displaystyle=\text{Pr}(\delta^{T}KY+\delta^{T}K\delta\geq\kappa\Phi^{-1}(1-\overline{p_{B}}))$
$\displaystyle=\text{Pr}(\delta^{T}\Sigma_{\phi^{*}}^{-1/2}\Xi\geq\kappa\Phi^{-1}(1-\overline{p_{B}})-\delta^{T}K\delta)$
$\displaystyle=\text{Pr}(\kappa
Z\geq\kappa(\Phi^{-1}(1-\overline{p_{B}})-\frac{1}{\kappa}\delta^{T}K\delta))$
$\displaystyle=\text{Pr}(Z\geq\Phi^{-1}(1-\overline{p_{B}})-\frac{1}{\kappa}\delta^{T}K\delta)$
$\displaystyle=\text{Pr}(Z\leq\Phi^{-1}(\overline{p_{B}})+\frac{1}{\kappa}\delta^{T}K\delta)$
$\displaystyle=\Phi(\Phi^{-1}(\overline{p_{B}})+\frac{1}{\kappa}\delta^{T}K\delta).$

By comparing these two probabilities, we identify the condition under which
$\text{Pr}(X^{*}\in\Omega_{A})\geq\text{Pr}(X^{*}\in\Omega_{B})$ holds as
follows:

$\displaystyle\Phi(\Phi^{-1}(\underline{p_{A}})-\frac{1}{\kappa}\delta^{T}K\delta)\geq\Phi(\Phi^{-1}(\overline{p_{B}})+\frac{1}{\kappa}\delta^{T}K\delta)$
$\displaystyle\Longleftrightarrow\quad\Phi^{-1}(\underline{p_{A}})-\frac{1}{\kappa}\delta^{T}K\delta\geq\Phi^{-1}(\overline{p_{B}})+\frac{1}{\kappa}\delta^{T}K\delta$
$\displaystyle\Longleftrightarrow\quad\frac{\delta^{T}K\delta}{\kappa}\leq\frac{1}{2}(\Phi^{-1}(\underline{p_{A}})-\Phi^{-1}(\overline{p_{B}})).$

$\kappa$ is previously defined as
$||\delta^{T}\Sigma^{-1/2}_{\phi^{*}}||_{2}$, which is
$\sqrt{\delta^{T}\Sigma^{-1}_{\phi^{*}}\delta}$. Since $\Sigma_{\phi^{*}}$ is
a Hermitian matrix, $K=\Sigma^{-1}_{\phi^{*}}$ is also a Hermitian matrix,
satisfying the condition for Rayleigh quotient in [84]. The upper bound of
$\frac{\delta^{T}K\delta}{\kappa}$ is
$\frac{||\delta||}{\sqrt{\lambda_{\min}}}$, as determined by Rayleigh
quotient:

$\displaystyle\frac{\delta^{T}K\delta}{\kappa}=\frac{\delta^{T}\Sigma^{-1}_{\phi^{*}}\delta}{\sqrt{\delta^{T}\Sigma^{-1}_{\phi^{*}}\delta}}=\sqrt{\delta^{T}\Sigma^{-1}_{\phi^{*}}\delta}\leq\sqrt{\frac{||\delta||^{2}}{\lambda_{\min}}}=\frac{||\delta||}{\sqrt{\lambda_{\min}}}.$

Here, $\lambda_{\min}$ stands for the minimum eigenvalue of
$\Sigma_{\phi^{*}}$. The right side is derived by the equality
$\lambda_{\max}(\Sigma_{\phi^{*}}^{-1})=\frac{1}{\lambda_{\min}(\Sigma_{\phi^{*}})}$,
where $\lambda_{\max}(\Sigma_{\phi^{*}}^{-1})$ denotes the maximum eigenvalue
of the matrix $\Sigma^{-1}_{\phi^{*}}$, and
$\lambda_{\min}(\Sigma_{\phi^{*}})$ is the minimum eigenvalue of
$\Sigma_{\phi^{*}}$ denoted as $\lambda_{\min}$. When the upper bound is less
than or equal to $\frac{\kappa}{2}\Psi$ such that
$\Psi=\Phi^{-1}(\underline{p_{A}})-\Phi^{-1}(\overline{p_{B}})$,
$\mathcal{G}_{\phi^{*}}(x+\delta)=c_{A}$ is supported.

$\displaystyle\frac{||\delta||}{\sqrt{\lambda_{\min}}}\leq\frac{1}{2}\Psi\Longleftrightarrow||\delta||\leq\frac{1}{2}\sqrt{\lambda_{\min}}\Psi=R.$

In other words, our classifier with Gaussian visual prompt ensures the
robustness against the perturbation $\delta$ by $R$. Also, for any vector $x$
in $\mathbb{R}^{d}$, the upper bound of $\lambda_{\min}$ is introduced by
Rayleigh quotient.

$\displaystyle\lambda_{\min}$ $\displaystyle\leq\min_{x\neq
0}{\frac{x^{T}\Sigma_{\phi^{*}}x}{x^{T}x}}$
$\displaystyle=\min_{\sum^{d}_{i=1}x_{i}^{2}=1}{(x_{1}^{2}\sigma_{1}^{2}+\cdots+x_{d}^{2}\sigma_{d}^{2})}$
$\displaystyle=\min\\{\sigma_{i}^{2}\\}^{d}_{i=1}.$

This induces the upper bound of $R$, which is
$\overline{R}=\frac{1}{2}\min\\{\sigma_{i}\\}^{d}_{i=1}\Psi$.

##  Appendix B Experimental Setting

###  B-A Datasets

##### Synthetic Datasets

Our BlackVIP generates the input-dependent image-size visual prompt which
covers the whole image region, so we expect that this flexible prompt design
can improve some kind of robustness as well as general recognition capability:
(1) To evaluate the robustness on distribution shift (i.e., domain
generalization), we consider Biased-MNIST [70] dataset. (2) To evaluate the
robustness on adversarial noise and location-agnostic recognition capacity, we
create a variant of the MNIST dataset called Loc-MNIST. Examples of these two
datasets are provided in Figure 10.

(a)

Figure 8: Examples of $y=7$ subset in Biased-MNIST [70] with $\rho=0.9$. (Top)
the train set is constructed with the spurious correlation between the
background color and digit class (e.g., $y=7$ occurs $90\%$ with pink
background and $10\%$ with other random colors in this case). (Bottom) the
test set is constructed with a reversed correlation to that of the train set
(e.g., $y=7$ occurs $10\%$ with pink background and $90\%$ with other random
colors in this case).

(a)

Figure 9: Examples of Loc-MNIST dataset. The real digit from MNIST is located
in the outer area, while the fake digit from another random MNIST image is
placed in the center of the image. (Top) the case where the size ratio of the
real digit to the fake digit is 1:1, and (Bottom) 1:4. Figure 10: Examples of
two synthetic datasets. (a) Biased MNIST and (b) Loc-MNIST.

Biased MNIST is a modified version of MNIST [71] where the biases reside in
the background colors of the images of each digit. At train time, each digit
has a unique preassigned background color that strongly correlates with the
label. The degree of correlation is determined by the value $\rho\in[0,1]$,
such that $(100\times\rho)\%$ of the images that belong to the same digit have
the preassigned color of that digit as their background color, and the rest
are uniformly assigned to have any of the other colors as their background
color. At test time, we reverse the ratio so that $(100\times(1-\rho))\%$ of
the images now have the preassigned color as their background color and vice
versa to evaluate the model’s dependency on superficial features such as the
color of the background that a digit is located on. We prepare the following
two environments 1) easy: $\rho=0.8$ and 2) hard: $\rho=0.9$.

On the given black blank image with $224\times 224$ resolution, i.e., zero’s
array, Loc-MNIST puts an original target digit image from MNIST that has
$28\times 28$ resolution on the edge-side (e.g., 0$\sim$27 or 196$\sim$223 for
one of vertical or horizontal side and 0$\sim$223 for another side) and puts a
random fake digit (also from the MNIST dataset) on the center. The location of
the target digit in the edge and the class of fake digit are chosen randomly
with uniform probability. A synthetic image is created one by one for each
original MNIST image. We prepare the following two environments 1) easy: the
scale of the target and the fake digit is the same, i.e., 1:1, and 2) hard:
the fake digit is four times larger than the original digit, i.e., 1:4.

For consistency, we perform the experiments on these two datasets with a few-
shot evaluation protocol. To construct a train set, we randomly sample a
subset (K-shot) of the created images for each class and use the whole test
set.

##### Datasets

To extensively evaluate the effectiveness of our proposed method and baseline
approaches, we measure performance across the following 14 datasets that are
widely used for transfer learning benchmark: Caltech101 [85], OxfordPets [86],
StanfordCars [87], Flowers102 [88], Food101 [89], FGVCAircraft [90], SUN397
[91], DTD [72], SVHN [92], EuroSAT [73], Resisc45 [74], CLEVR [75], UCF101
[93], and ImageNet (IN) [35]. Note that these 14 datasets cover diverse visual
domains, and they require understanding various visual semantics like scenes,
actions, fine-grained categories, textures, satellite imagery, digits, the
number of objects, and the recognition of generic objects. Moreover, to
evaluate the robustness of prompt-based adaptation of PTM in the wild, we
additionally consider three benchmark datasets of distribution shifts from
WILDS [66]: Camelyon17 [94], FMoW [95], and iWildCam [96].

Following the protocol in [9, 10], we conduct a few-shot evaluation for all
datasets: 16-shot for the train set, 4-shot for the validation set, and the
whole test set. We use the few-shot split by [9] for each dataset those are
also used in [9], while for Resisc45, CLEVR, and WILDS datasets, we randomly
select the 16-shot and 4-shot samples for training and validation dataset,
respectively.

###  B-B Backbone Model

In this work, we aim at the robust adaptation of pre-trained models on diverse
downstream tasks. For these pre-trained models, all experiments in this paper
are done with the off-the-shelf vision-language model CLIP [2], and we adopt
the ViT-B/16 for image encoder backbone architecture by default. During the
adaptation (training) phase, the entire components of the pre-trained model
are frozen without any architectural modification, and we only manage and
optimize the learnable module Coordinator from the outside of the pre-trained
model.

While input space visual prompting allows it to be applied to not only VLM,
but also any other vision models like CNNs and ViTs, it requires the user to
define the output space mapping, which maps the output prediction category set
of a pre-trained task to a new downstream category set [41, 34, 5]. This is
another non-trivial problem. Therefore, we limit our focus to only the VLM
that can dynamically build the task-specific head from manual text template
[2, 97] so that free from defining output space mapping.

###  B-C Baseline Methods

##### CLIP Zero-Shot (ZS)

CLIP [2] is one of the most popular vision-language zero-shot models that is
widely exploited for classification, detection, segmentation, and other vision
or vision-language tasks. Based on its well-aligned vision-language joint
embedding space, the zero-shot classification can be performed with a manual
text prompt (also called template) of each pre-defined class category. In this
paper, we are mainly aiming to improve the CLIP’s strong zero-shot performance
in the few-shot adaptation setting.

##### BAR

Black-Box Adversarial Reprogramming (BAR) [34] was proposed for efficient
transfer learning of pre-trained model to the medical image domain. Different
from the previous works on Adversarial Reprogramming (AR), BAR exploits the
perturbation-vulnerability of neural networks for adaptation purpose rather
than attack. By optimizing the frame-shaped learnable program, which embeds a
downstream target image inside of that, BAR steers the ImageNet pre-trained
model to classify the specialized medical images. Moreover, BAR adopts the
zeroth-order optimizer (ZOO), Randomized Gradient-Free (RGF) [98] minimization
algorithm for black-box transfer learning to broaden its applications.

When the resolution of the downstream input image is over that of the pre-
training phase, Tsai et al. [34] set the embedded target image size for
$64\times 64$ resolution in the $299\times 299$-size learnable program by
default. However, we observe that such a heavy-pad thin-image design of prompt
degrade the performance significantly, so we tune the resolution of the
embedded image and set $194\times 194$.

##### VP

Similarly, Visual Prompting (VP) aims at adapting a pre-trained model to
downstream tasks via learning input space visual prompts. Among some
candidates for prompt designs, Bahng et al. [5] adopt the padding-style prompt
so that realized prompts look like the frame-shape program of ARs. VP learns a
universal visual prompt per each downstream task, and it just adds to all of
the images in a task. Unlike the AR methods or our BlackVIP, the range of
prompted images is unbounded. Following [5], we use the padding-style prompt,
which is 30-pixel sized for each side by default.

While VP optimizes the parameters in the input space, it relies on a first-
order optimization algorithm that uses the true gradient of entire model
parameters, and we establish the performance of VP as a kind of upper bound
for other input space black-box optimization approaches, including BlackVIP
and BlackVIP-SE. Additionally, by replacing the first-order algorithm with
zeroth-order counterparts, we build two new baselines VP w/ SPSA and VP w/
SPSA-GC on our extensive experiments. These two methods confirm the
effectiveness of our new components Coordinator and SPSA-GC.

Furthermore, we consider some representative prompt learning methods as
baselines on language modality (CoOp [22] and CoCoOp [10]), vision modality
(VP [5] and VPT [4]), and both modality (MaPLe [6]) for an evaluation of
white-box transfer learning experiments to validate the effectiveness of the
design of our visual prompt, solely. All of these methods adapt parameters
inside the model, e.g., tokens in the embedding layer or intermediate layers
of text or visual encoder of the target vision-language model.

##### Discussion

Although BAR, VP, and BlackVIP share the generic goal: efficient transfer
learning of pre-trained models via input-space optimization, there are several
significant differences. (1) We propose a novel prompt design that is
automatically formed in an input-dependent manner rather than the frame-shaped
manual design of the input-independent prompt (or program) of VP (or BAR). (2)
While VP relies on first-order algorithms and BAR adopts the RGF, we utilize
the new variants of SPSA [40], SPSA-GC, which is enhanced with a proper
modification in the parameter update rule. (3) Contrary to the medical
imaging-only validation in BAR, based on the above two technical difference,
BlackVIP successfully adapt the pre-trained model to diverse data domains
(described in Section B.1.).

###  B-D Implementation Details

##### Architecture

For the fixed text prompt design of each dataset those are shared across all
baseline methods and BlackVIPs, we use the same templates provided by [5] for
SVHN, CLEVR, and Resisc45, and [9] for remaining 11 datasets. For the fixed
encoder part of our Coodinator, we use the ImageNet pre-trained vit-mae-base
checkpoint333https://huggingface.co/docs/transformers/model_doc/vit_mae from
the HuggingFace. The output shape of the encoder is $N\times 768$, where $N$
is the number of instances in the batch. For the BlackVIP-SE, we used the
scikit-learn’s vanilla PCA or kernel PCA method444We considered whether to use
a kernel or not and which kernel (among RBF, cosine, and polynomial kernels)
to use as hyperparameters.. For fast training, we pre-computed the PCA
features for BlackVIP-SE and retrieved them by index during each training
iteration. During the inference phase, we load the trainset-fitted PCA
projection matrix and apply it to the flattened test input $x$ to get the
feature vector fed into the prompt decoder. Here, we design the decoder based
on depth-wise separable convolution (DSC) layer [99] for parameter efficiency.
Specifically, we build a block of [NORM-ACT-CONV] and stack it five times. The
NORM and ACT denote Batch Normalization and Gaussian Error Linear Unit,
respectively. The CONV operation of the first four blocks is DSC, and the last
one is a standard convolutional layer. Our implementation code is available at
https://github.com/changdaeoh/BlackVIP

To satisfy a fully convolutional design without loss of expressiveness,
tensors that are fed into the decoder must be shaped in a 3D feature map. For
this, we additionally govern a task-specific single continuous vector
$\phi_{t}$ (called prompt trigger vector), which is concatenated with the
output feature vector of encoder leading the appropriate size of 1d vector for
reshaping to 3d tensor. For the BlackVIP, we set the dimension of the prompt
trigger vector to 800, resulting in 1568 dimensions of concatenated vector
that can be reshaped to $32\times 7\times 7$ shaped 3D tensor. Meanwhile,
BlackVIP-SE allows users to set the latent feature dimension (for the reduced
PCA coordinate system) as their own preference. This contributes to further
reducing the input dimension of the decoder feature map, and we set the PCA
feature dimension to 98, and rather than concatenation, we simply use the sum
of the trigger vector and PCA feature as input of the prompt decoder. The
prompt trigger is shared across all instances for a given task.

##### Optimization and other configurations

For a stable approximation of gradient in practice, ZOO algorithms repeat the
gradient estimation step for several times and use the mean of those estimates
as a final approximation of the gradient. Usually, the approximation quality
is proportional to the number of these repeats. We set this repeat as five
times for all baselines that use ZOO.

Besides the learning rate and learning rate schedule parameters, ZOO
algorithms have some additional algorithm-specific hyperparameters that need
to be tuned. For RGF, these are the standard deviation of a random gaussian
vector and a smoothing parameter, and for SPSA, these are the perturbation
magnitude and its decaying factor. We provide the search range of each
hyperparameter in Table X. The search range for algorithm-specific parameters
is based on the proposal of authors of SPSA [13] and BAR [34]. Moreover, among
the valid perturbation distributions of SPSA, we adopt the Segmented Uniform
$[-1.0,-0.5]\cup[0.5,1.0]$.

The learning objective is a cross-entropy loss for VP and BlackVIP and focal
loss for BAR (following [34]). For all black-box approaches, the batch size is
set to 128 across all datasets. Except for the SUN397 (1,000), StanfordCars
(2,500), and ImageNet (500), we optimize all methods during 5,000 epochs for
convergence. Note that the input space visual prompting with first-order
algorithm already requires sufficiently large iterations, e.g., 1,000 epoch
[5] with full dataset, and ZOO demands much more iterations due to the lack of
gradient information.

###  B-E Hyperparameter Sweep

In this section, we provide the hyperparameter search range of each algorithm,
summarized in Table X.

TABLE X: Hyperparameter sweep. Large LR (learning rate) of BAR and VP is based
on [5] to directly optimize pixel values rather than the neural network’s
weights. PM denotes perturbation scale $c_{i}$, and parameters of
dimensionality reduction algorithm.

Hyperparameter | Algorithm | Search Range
---|---|---
initial LR | BAR, VP |  $\\{$40.0, 20.0, 10.0, 5.0, 1.0$\\}$
initial LR ($a_{1}$) | BlackVIPs |  $\\{$1.0, 0.1, 0.01, 0.005$\\}$
min LR | BAR |  $\\{$0.1, 0.01, 0.001$\\}$
decaying step | BAR |  $\\{$0.9, 0.5, 0.1$\\}$
LR decaying factor | VP, BlackVIPs |  $\\{$0.6, 0.5, 0.4, 0.3$\\}$
initial PM ($c_{1}$) | BlackVIPs |  $\\{$0.01, 0.005, 0.001$\\}$
PM decaying factor | BlackVIPs |  $\\{$0.2, 0.1$\\}$
std. of perturbation | BAR |  $\\{$1.0, 0.5$\\}$
smoothing | BAR |  $\\{$0.1, 0.01, 0.001$\\}$
gradient smoothing | VP, BlackVIPs |  $\\{$0.9, 0.7, 0.5, 0.3$\\}$
dimension of features | BlackVIP-SE |  $\\{$32, 49, 98, 196$\\}$
PCA kernel type | BlackVIP-SE |  $\\{$linear, RBF, cosine, polynomial$\\}$

##  Appendix C Detail Description of BlackVIP’s Coodinator

On the transfer learning of a pre-trained model which provides no
accessibility about any architectural information or actual model parameters,
BlackVIP treats this situation with two novel mechanisms: (1) parameter-
efficient instance-aware prompt generation network, and (2) stable zeroth-
order optimization algorithm that is based on SPSA [13]. In this section, we
provide a detailed description of the first component, Coordinator.

Different from existing works on visual prompting, we reparameterize the input
space visual prompt $\phi$ as a neural network, Coordinator
$v_{\bm{\phi}}(\cdot)$ that generates an input-dependent visual prompt
$v_{\bm{\phi}}(x)$. Coordinator is composed with encoder $f(\cdot)$, decoder
$g_{\phi_{d}}(\cdot)$ and task-specific learnable vector $\phi_{t}$. The
encoder is used for extracting instance-specific latent feature vector
$z_{x}=f(x)$ contributing to the construction of the optimal input space
visual prompt for each instance. Because our goal in this work is the broad
utilization of pre-trained models on diverse downstream tasks, we adopt a pre-
trained encoder network optimized by a self-supervised learning objective, not
by a supervised learning objective or scratch network. Specifically, we use
the ViT-B/16 weights from the Masked AutoEncoding pre-training [49]. We
present the grounds for using the self-supervised learning encoder in the main
paper, refer to Sec. 3. During the training phase, this pre-trained encoder
part is frozen (not updated) and just acts as a feature extractor. Then, the
instance-specific feature vector from the encoder is conveyed to the decoder
for a prompt generation.

Prompt decoder $g_{\phi_{d}}(\cdot)$ is a lightweight convolutional neural
network, which has learnable parameters less than 10K by default. Note that
the generated prompt has the same shape as the input image, so our prompt
covers the entire region of the image, unlike previous visual prompting and
reprogramming works applied to the partial region of the image by human-
designed.

In addition to the feature vector from the fixed encoder, the decoder also
incorporates an additional input which is shared for all instances across the
current dataset. The so-called prompt trigger vector $\phi_{t}$ is a
continuous vector that also contributes to the design of a visual prompt by
collaborating with the instance-specific rich feature vector from the encoder.
By introducing this prompt trigger vector, the decoder of the Coordinator can
enjoy additional information to generate more proper prompts for a given task.
Besides, it helps to build the 3D feature map for the decoder’s input, which
is necessary for designing a parameter-efficient fully convolutional decoder
network.

##  Appendix D Grad-CAM Analysis

To investigate whether visual prompts produced by each method adapt the pre-
trained model, we visualize the Grad-CAM [100] on the original image and
prompted image of the encoder’s penultimate layer (Figure 11-18). We select
eight datasets that represent the diverse image domains and experimental
conditions: (Natural) OxfordPets and SVHN, (Specialized) EuroSAT, (Structured)
CLEVR-count, (Action Recognition) UCF101, (Fine-Grained) StanfordCars,
(Synthetic) Biased-MNIST and Loc-MNIST. Detail descriptions for each dataset
are provided in Sec. A.1.

BlackVIP generates diverse prompts to properly adapt the pre-trained model to
the targeted data domains. When the task is counting the number of objects
(CLEVR) in the entire region of an image, BlackVIP extends the attention of
the pre-trained model to the whole view of an image as shown in Figure 11. If
the task requires a fine-grained understanding of objects or recognition of
actions (UCF101), BlackVIP concentrates the model’s attention on class-related
regions, as shown in Figure 12.

Figure 11: Grad-CAM on CLEVR. Compared to baseline methods, BlackVIP extends
the attention of models to broad areas of the image for effective reasoning on
the number of objects.

Figure 12: Grad-CAM on UCF101. Compared to baseline methods, BlackVIP
concentrates the attention of models on local areas of the image for effective
recognition of the specific actions.

Figure 13: Grad-CAM on OxfordPets. Compared to baseline methods, BlackVIP
effectively adapts the model to focus on the target object rather than
spurious features such as the background.

Figure 14: Grad-CAM on SVHN. Compared to baseline methods, BlackVIP
effectively adapts the model to focus on the target digit rather than spurious
features such as the background.

Figure 15: Grad-CAM on EuroSAT. Compared to baseline methods, BlackVIP extends
the attention of models to broad areas of the image for effective
classification of satellite imagery.

Figure 16: Grad-CAM on StanfordCars. Compared to baseline methods, BlackVIP
concentrates the attention of models on an object or local areas of an image
for effective fine-grained classification.

Figure 17: Grad-CAM on Biased-MNIST. While baseline methods attend to the
background rather than digit shape, our BlackVIP can bypass this spurious
feature through a widely scattered visual prompt and focus more of the
attention on the shape of the digit.

Figure 18: Grad-CAM on Loc-MNIST. Compared to baseline methods, BlackVIP
effectively adapts the model to aim at edge-located true digit corresponding
true label rather than the obstructive fake digit in the center of the image.