# OT-VP: Optimal Transport-guided Visual Prompting for Test-Time Adaptation

Yunbei Zhang1, Akshay Mehra1, Jihun Hamm1
1Tulane University
{yzhang111, amehra<EMAIL_ADDRESS>

###### Abstract

While Vision Transformers (ViTs) have demonstrated remarkable capabilities in
learning representations, their performance is compromised when applied to
unseen domains. Previous methods either engage in prompt learning during the
training phase or modify model parameters at test time through entropy
minimization. The former often overlooks unlabeled target data, while the
latter doesn’t fully address domain shifts. In this work, our approach,
Optimal Transport-guided Test-Time Visual Prompting (OT-VP), handles these
problems by leveraging prompt learning at test time to align the target and
source domains without accessing the training process or altering pre-trained
model parameters. This method involves learning a universal visual prompt for
the target domain by optimizing the Optimal Transport distance. With just four
prompt tokens learned, OT-VP achieves a $5.0\%$ and $1.5\%$ increase in
averaged accuracy across single-source and multi-source settings on three
benchmark datasets, which is $1.2\times$ and $1.5\times$ the improvement of
the state-of-the-art method, respectively.

##  1 Introduction

The remarkable successes of Deep Neural Networks (DNNs) are often tempered by
the challenges posed by discrepancies between training and testing data
distributions [39, 14, 19]. Such discrepancies are not uncommon in real-world
applications, where variations in data due to natural differences and
stylistic changes can significantly impact model performance [21]. Though
Domain Generalization (DG) has been proposed as a solution to ensure model
robustness across unseen domains [4, 50], fully achieving this remains a
challenge. To address this limitation, a new research direction has emerged,
concentrating on enhancing model performance directly at test time [47, 15].
This approach allows models to leverage unlabeled test data from target
domains. This data offers insights into the target distribution, insights that
are typically inaccessible in the DG framework. Test-time adaptation, as
demonstrated in [15], surpasses the capabilities of many existing DG
strategies by utilizing immediate, real-world data to refine model accuracy.
Inspired by these insights, our work pivots towards exploring test-time
adaptation (TTA) as a strategic response to the challenges of domain shifts,
aiming to harness the full potential of DNNs in unseen environments.

Figure 1: Motivation of our approach. (a) An ERM model trained on the source
domain struggles to adapt to the target domain due to domain shifts. (b) Our
method (OT-VP) optimizes a visual prompt by minimizing the Optimal Transport
distance to align the target domain with the source domain without changing
the decision boundary.  Figure 2: An overview of our proposed OT-VP method. At
test time, unlabeled target data are processed through a frozen pre-trained
ViT model with only the prompt tokens (indicated in red) being trainable. This
generates target representations ($z^{t}$) and pseudo-labels ($\hat{y}^{t}$).
We then align these with actual source labels ($y^{s}$) and offline-computed
(the grey shadowed area) source representations ($z^{s}$) via Optimal
Transport (OT) distance. The visual prompts are iteratively optimized based on
this distance to align the source and target domain data more closely.

Our approach is underpinned by leveraging visual prompt learning, designed to
seamlessly bridge the gap between source and target domains during test time.
Vision Transformers (ViTs), known for their remarkable achievements across a
spectrum of computer vision tasks, serve as the backbone of our approach [7,
25]. The self-attention mechanism within ViTs enables comprehensive modeling
of relationships between various segments of an image, making them an ideal
foundation for our work [49, 33, 38]. Visual prompt learning emerges as a
prominent strategy for fine-tuning ViTs without altering model parameters on
specialized downstream tasks [16]. This technique involves embedding task-
specific knowledge directly into the input tokens, allowing for interaction
with prompt tokens via self-attention layers. Such interactions enable the
network to grasp the essence of the task, provided the prompt contains ample
informative content. Although visual prompt tuning is lauded for its precision
in task-oriented learning, it conventionally depends on the availability of
labeled data for the creation of impactful prompt tokens—a requirement not met
in the TTA context.

Current approaches in prompt learning typically incorporate prompts during the
training phase, leveraging source data to create representative prompts [49],
or tuning prompts based on source domains at test time [10] for application in
target domains. However, these conventional strategies often do not directly
address the distribution shifts observed in the target domain, shown in Fig. 1
(a). Meanwhile, recent efforts focusing on prompt learning at test time [40,
27], are specifically designed for the CLIP (Contrastive Language-Image
Pretraining) [37] model, targeting Vision-Language models exclusively. These
methods generate input-specific prompts based on a limited set of augmented
target data, potentially missing the broader differences between source and
target domains. Adopting a universal prompt for the target domain leverages
more data and reduces computation time. Yet, simply learning this universal
prompt by minimizing entropy doesn’t effectively tackle domain shifts or
enhance performance, as evidenced by our experiments in Sec. 4.3.

To enable ViT models to adapt effectively at test time, it’s imperative to
address the fundamental challenge of reducing the distribution gap between
source and target domains. As shown in Fig. 1, this step is crucial for
enhancing the model’s ability to generalize to new, unseen data. Many metrics,
such as Maximum Mean Discrepancy (MMD), Kullback-Leibler (KL) divergence, and
Optimal Transport (OT) distance, have been explored to address distribution
shifts [3, 12, 20, 28]. Among these, Optimal Transport (OT) is distinguished
as particularly effective due to its ability to utilize the geometry of the
underlying space [35]. Numerous studies have demonstrated a strong correlation
between OT distance and target performance, supported by thorough theoretical
analyses [42, 29, 45]. Inspired by these insights, we propose Optimal
Transport [17, 35] guided Test-Time Visual Prompting (OT-VP), a test-time
distribution alignment method using prompt learning. Specifically, OT-VP
explicitly aligns the Optimal Transport distance between the source
representation, computed offline, and the target representation without
accessing the training process and modifying the pre-trained model parameters.
As illustrated in Fig. 2, for a given target dataset, we pass the unlabeled
target image through the visual encoder with learnable prompts to get the
target representation and pseudo-labels. Then we update the prompts by
minimizing the OT distance. This process is repeated iteratively to ensure
that the prompts are well-aligned with the target distribution.

We comprehensively evaluate the efficacy of OT-VP across three standard
benchmarks. Beyond the conventional multi-source DG setting—which leaves one
domain out as the target while treating the remainder as sources—we also
explore a single-source setting. The latter setting, often overlooked in
existing literature [15, 49], involves using one domain as the source and a
different one as the target. Training on a smaller set makes adaptation to the
new target domain more challenging, providing a rigorous test of the model’s
generalization ability. Based on ViT architecture, OT-VP achieves a stable and
significant improvement in ERM, enhancing average accuracy across all three
datasets by $5.0\%$ and $1.5\%$ in single-source and multi-source settings
respectively. Notably, OT-VP surpasses state-of-the-art (SOTA) algorithms in
both single-source and multi-source settings, underscoring its effectiveness
and adaptability. Additionally, our method effectively reduces prediction
entropy without directly minimizing it, thereby boosting model confidence and
reliability on unseen data. Our contribution can be summarized as follows:

  1. •

We propose OT-VP, a novel test-time adaptation that reduces the domain gap
between source and target through minimizing Optimal Transport distance,
facilitating prompts to better adapt to unlabelled target tasks.

  2. •

To the best of our knowledge, we are the first to learn universal prompts in
the TTA setting. Our findings demonstrate that a universal prompt for a target
domain can effectively align it with the source domain and enhance
performance.

  3. •

We demonstrate through extensive experimentation that OT-VP consistently
improves the performance of pre-trained models across a variety of settings,
outperforming existing SOTA methods.

##  2 Related Work

Prompting for Vision Transformers. Vision Transformers (ViTs) have achieved
state-of-the-art results in image classification [7, 25], yet adapting ViTs to
unseen target domains without labels is still a challenge. Many recent methods
enhance ViTs’ transferability by learning visual prompts as continuous,
learnable vectors trained in an end-to-end manner with frozen model parameters
[16, 2, 48]. However, these methods typically require labeled target data for
prompt learning. For example, [49] introduced DoPrompt, a DG method that
learns visual prompts for source domains and generates input-specific prompts
at test time. However, its practical use is limited because it requires
modifications to the training process. In contrast, our approach learns a
universal prompt for the target domain, effectively minimizing the
distribution shift between source and target domains without accessing the
training setup.

Test-Time Adaptation (TTA). TTA [44, 47, 24] aims to improve the performance
of pre-trained models when they are deployed on unseen domains. TTA strategies
are typically bifurcated into two main categories based on their reliance on
source data. The first category comprises approaches that adapt models to new
domains without direct access to source data [22, 23, 36, 32]. Notable
examples within this subset include Tent [47], which updates batch
normalization parameters to minimize entropy. Similarly, T3A [15] innovates by
creating and updating a set of dynamic prototypes, utilizing them to gauge the
similarity between test samples and these prototypes, thereby facilitating
adaptation based on feature resemblance.

Conversely, the second category, which our work aligns with, involves
techniques that leverage source data to inform the adaptation process. Methods
such as NORM [41] and DUA [30] adapt model normalization layers by aligning
batch normalization statistics from the training phase with those observed in
the target data. Similarly, ActMAD [31] and PromptAlign [40] update all model
parameters or employ prompt-based strategies, respectively, utilizing a
distribution matching loss that leverages knowledge of source domain
statistics. This utilization of source data equips these methods with a
foundational understanding of the distribution shift, thereby facilitating
more effective adaptation to the target domain.

A significant portion of existing TTA literature centers around Convolutional
Neural Networks (CNNs), whose methodologies are not directly transferrable to
Vision Transformers (ViTs) due to architectural differences, notably the
absence of batch normalization layers in ViTs [15]. This gap underscores the
necessity for developing TTA strategies specifically tailored to the unique
architecture of ViTs, which our work aims to address.

Innovative approaches like DePT[10], PromptAlign [40], and SwapPrompt [27]
have introduced prompt-based strategies for TTA, learning input-specific
prompts through test image augmentations. However, these methods encounter
limitations due to the restricted number of augmentations available for each
test image, struggling to minimize the distance between the comprehensive
statistics of the source data and the augmented versions of a single test
image. Our methodology circumvents this issue by optimizing a universal prompt
across batches, which not only avoids the pitfalls of limited augmentations
but also more effectively reduces the gap between source and target domains
with only four prompt tokens.

##  3 Method

In this section, we present OT-VP. We begin with a discussion on the problem
setup of TTA in Section 3.1. This is followed by introductions of Vision
Transformers in Section 3.2 and Optimal Transport in Section 3.3. Finally, we
describe our method in Section 3.4, with the method’s workflow illustrated in
Figure 2.

###  3.1 Preliminaries

Problem Definitions. Denote the data from the source (target) domains as
$\mathcal{D}^{s}=\\{\mathbf{x}_{i}^{s},y_{i}^{s}\\}_{i=1}^{n_{s}}$
($\mathcal{D}^{t}=\\{\mathbf{x}_{i}^{t},y_{i}^{t}\\}_{i=1}^{n_{t}}$), where
$\mathbf{x}\in\mathcal{X}$ represents the input image and $y\in\mathcal{Y}$ is
the label. The dataset $\mathcal{D}^{s}$ ($\mathcal{D}^{t}$) comprises samples
that are identically and independently distributed (i.i.d.), characterized by
some probability distribution $P^{s}(X,Y)$ ($P^{t}(X,Y)$).

In the context of TTA, the model $f$ is initially trained on the source
domain, e.g. minimizing the empirical risk,

$\mathop{\arg\min}\limits_{f}\frac{1}{n_{s}}\sum_{i=1}^{n_{s}}\ell(f(\mathbf{x}_{i}^{s}),y^{s})$
(1)

where $\ell$ is a loss function. Throughout this paper, we refer to optimizing
the model with Eq. 1 as ERM. Generally, the model $f$ is structured as a
composition $f=h\circ\phi$, with the feature extractor
$\phi:\mathcal{X}\rightarrow\mathcal{Z}$ learning the input’s representation,
and the classifier $h:\mathcal{Z}\rightarrow\mathcal{Y}$ predicting the class
label.

For any unlabeled target domain $\mathcal{D}^{t}$, TTA aims to adapt model $f$
or/and target input $x^{t}$ to bridge the performance gap under the assumption
that the source domain and target domain share the same label set. In our
approach, we employ a Vision Transformer as the model $f$, which remains fixed
during adaptation.

###  3.2 Vision Transformers

A Vision Transformer (ViT) [7, 25] processes an input image $x$ by initially
dividing it into $k$ patches $\\{I_{i}\\}_{i=1}^{k}$. An encoding layer $E$ is
employed to transform the input patches into patch tokens, to which positional
embedding are subsequently added to retain spatial information. The inputs to
the transformer layers consist of these encoded patch tokens augmented with a
special classification token `[CLS]`. The ViT is composed of several
sequential blocks, and each block contains an attention layer and a Multi-
Layer Perceptron (MLP) layer. The prediction of the vision transformer can be
formulated as follows:

[CLS] $\displaystyle=\phi([\texttt{[CLS]},E(I_{1}),...,E(I_{k})]),$ (2)
$\displaystyle y$ $\displaystyle=h(\texttt{[CLS]}),$

where $[\cdot]$ represents concatenation of tokens.

Incorporating a visual prompt into the ViT represents a parameter-efficient
approach for fine-tuning or adapting the model, particularly when it is fixed
[16, 11]. By introducing $l$ prompt tokens
$\\{\texttt{[Prompt]}_{i}\\}_{i=1}^{l}=:\mathbf{\gamma}$, the prediction
process can be reformulated as follows:

[CLS] $\displaystyle=\phi([\texttt{[CLS]},\\{E(I_{i})\\}_{i=1}^{k},\gamma])$
(3) $\displaystyle y$ $\displaystyle=h(\texttt{[CLS]})$

The optimal prompts can be optimized as follows when the labels are available:

$\mathbf{\gamma}^{*}=\mathop{\arg\min}\limits_{\mathbf{\gamma}}\mathbb{E}[\ell(f(\mathbf{x};\mathbb{\gamma}),y)]$
(4)

###  3.3 Optimal Transport

Optimal Transport (OT) theory, tracing back to the Monge problem in 1781,
evolved significantly with the introduction of the Kantorovich relaxation [17]
in 1942. This advancement transformed OT into a robust framework for comparing
distributions, shapes, and point clouds [35], leveraging the geometry of the
underlying space. OT operates on a complete and separable metric space
$\mathcal{X}$, utilizing continuous or discrete probability measures
$P,Q\in\mathcal{P(X)}$. The Kantorovich formulation defines the OT problem as:

$\mathrm{OT}_{c}(P,Q):=\mathop{\inf}\limits_{\pi\in\Pi(P,Q)}\int_{\mathcal{X}\times\mathcal{X}}c(\mathbf{x}_{1},\mathbf{x}_{2})d\pi(\mathbf{x}_{1},\mathbf{x}_{2}),$
(5)

where $c(\cdot,\cdot):\mathcal{X}\times\mathcal{X}\rightarrow\mathbb{R^{+}}$
denotes a cost function, and $\Pi(P,Q)$ represents the set of all possible
couplings or joint distributions over $\mathcal{X}\times\mathcal{X}$ with $P$
and $Q$ as their marginals. The term
$W_{p}(P,Q):=\mathrm{OT}_{c}(P,Q)^{\frac{1}{p}}$ is referred to as the
$p$-Wasserstein distance when the cost function
$c(\mathbf{x}_{1},\mathbf{x}_{2})=d(\mathbf{x}_{1},\mathbf{x}_{2})^{p}$ for
some $p\geq 1$ where $d$ is a metric of $\mathcal{X}$.

In real-world applications, the true marginal distributions $P,Q$ are often
unknown, leading to reliance on discrete empirical distributions
$\hat{P}=\sum_{i=1}^{m}\mathbf{a}_{i}\delta_{\mathbf{x}_{1}^{i}}$ and
$\hat{Q}=\sum_{i=1}^{n}\mathbf{b}_{i}\delta_{\mathbf{x}_{2}^{i}}$, with
$\mathbf{a},\mathbf{b}$ as vectors in the probability simplex. The cost
function then simplifies to an $m\times n$ cost matrix $\mathbf{C}$, where
$\mathbf{C}_{ij}=c(\mathbf{x}_{1}^{i},\mathbf{x}_{2}^{j})$. For computational
efficiency, the Sinkhorn algorithm [6] introduces an entropic regularizer to
the OT problem, facilitating practical applications such as domain adaptation
[5] and the evaluation of distances between datasets [1]. This regularized
approach, which can be computed using `POT` [9], allows for the computation of
an optimal mapping from source to target domains.

###  3.4 Test-time Adaptation with OT-VP

In the TTA setting, the absence of labeled target data presents a challenge
for prompt optimization as traditionally conducted in Eq. 4. To address this,
we introduce an unsupervised prompt adaptation strategy, termed Optimal
Transport-guided Test-Time Visual Prompting (OT-VP). This method leverages
unlabeled target dataset $\mathcal{D}^{t}$, passing it through the ViT encoder
alongside learnable prompts to obtain a set of representations, as depicted in
Figure 2. Source representations, prepared in advance, are readily applied
during test time to facilitate OT distance computation.

The essence of OT-VP lies in calculating the OT distance between the source
and target representations, underpinned by two distinct cost functions. The
first, OT-VP-base (OT-VP-B), measures the cost between two representations
devoid of label data, with the cost $c_{0}(\mathbf{z}^{s},\mathbf{z}^{t})$
defined as the Euclidean distance between source and target representations
$\mathbf{z}^{s}:=h(\mathbf{x}^{s})$ and
$\mathbf{z}^{t}:=h(\mathbf{x}^{s};\gamma)$:

$c_{0}(\mathbf{z}^{s},\mathbf{z}^{t})=\|\mathbf{z}^{s}-\mathbf{z}^{t}||_{2}$
(6)

The second cost function, OT-VP, enriches this comparison by incorporating
label or pseudo-label information, introducing a penalty term scaled by
hyperparameter $\lambda$ for label mismatches between source and target data:

$c_{\lambda}((\mathbf{z}^{s},y^{s}),(\mathbf{z}^{t},\hat{y}^{t}))=\|\mathbf{z}^{s}-\mathbf{z}^{t}\|_{2}+\lambda\cdot\mathbbm{1}_{\\{y^{s}\neq\hat{y}^{t}\\}}$
(7)

where $\hat{y}^{t}:=f(\mathbf{x}^{t};\mathbf{\gamma}))$ represents the pseudo
label derived from the pre-trained model using the adaptively learned prompts.
Notably, when setting $\lambda$ to infinity in Eq. 7, the OT distance is the
Wasserstein Distance [43], a well-established mathematical framework that has
proven effective for measuring distances between distributions.

The computed OT distance informs the prompt update process for the target
dataset, optimizing the prompts to minimize the distance between the source
and target distributions. This optimization is formalized as seeking the
optimal prompts $\mathbf{\gamma}^{*}$ that minimize the OT cost, thereby
aligning the target dataset’s representation with that of the source:

$\mathbf{\gamma}^{*}=\mathop{\arg\min}\limits_{\mathbb{\gamma}}\mathrm{OT}_{c}(P^{s}_{\\#},P^{t}_{\\#})$
(8)

where $P^{s}_{\\#}$ is a joint distribution over source representations and
source labels: $(\phi(\mathbf{x}^{s}),y^{s})$, and $P^{t}_{\\#}$ is a
distribution over target representations and target pseudo labels:
$(\phi(\mathbf{x}^{t}),\hat{y}^{t})$.

During inference, we apply the optimized prompt tokens $\gamma^{*}$ to make
predictions for a given target input $\mathbf{x}^{t}$, following the Eq. 3.

Algorithm | PACS | VLCS | OfficeHome | Avg |  $\Delta$ Avg
---|---|---|---|---|---
ERM | 64.5$\pm$3.2 | 63.8$\pm$2.2 | 66.7$\pm$0.7 | 65.0 | 0.0
DoPrompt | 64.3$\pm$2.3 | 65.8$\pm$2.1 | 67.6$\pm$0.6 | 65.9 | +0.9
Tent-C | 64.4$\pm$2.4 | 65.0$\pm$3.2 | 66.6$\pm$1.2 | 65.3 | +0.3
Tent-BN | 69.0$\pm$2.9 | 58.5$\pm$2.3 | 67.6$\pm$0.9 | 65.0 | 0.0
T3A | 71.2$\pm$2.8 |  68.3$\pm$2.2 |  68.1$\pm$0.8 | 69.2 | +4.2
OT-VP-B | 69.8$\pm$2.8 | 65.2$\pm$1.8 | 66.9$\pm$0.5 | 67.3 | +2.3
OT-VP |  73.5$\pm$2.7 |  68.4$\pm$2.3 |  68.1$\pm$0.7 | 70.0 | +5.0

Table 1: Accuracy ($\%$) in Single-Source Settings across Datasets and
Algorithms. The last column represents the relative improvement over the
baseline established by ERM on a ViT-B16 model. Full results can be found in
Appendix B.

Algorithm | PACS | VLCS | OfficeHome | Avg |  $\Delta$ Avg
---|---|---|---|---|---
ERM | 87.0$\pm$0.1 | 78.5$\pm$0.3 | 73.6$\pm$0.1 | 79.7 | 0.0
DoPrompt |  87.5$\pm$0.2 | 80.3$\pm$0.4 | 74.7$\pm$0.2 | 80.8 | +1.1
Tent-C | 87.2$\pm$0.2 | 78.8$\pm$0.5 | 73.6$\pm$0.2 | 79.9 | +0.2
Tent-BN | 87.2$\pm$0.2 | 78.5$\pm$0.3 | 74.6$\pm$0.3 | 80.1 | +0.4
T3A | 87.4$\pm$0.1 | 80.0$\pm$0.4 | 74.7$\pm$0.2 | 80.7 | +1.0
OT-VP-B | 87.3$\pm$0.2 | 80.2$\pm$0.3 | 74.3$\pm$0.3 | 80.6 | +0.9
OT-VP |  87.7$\pm$0.1 |  80.9$\pm$0.4 |  75.1$\pm$0.1 | 81.2 | +1.5

Table 2: Accuracy ($\%$) in Multi-Source Settings across Datasets and
Algorithms. The last column represents the relative improvement over the
baseline established by ERM on a ViT-B16 model. Full results can be found in
Appendix B.

##  4 Experiments

###  4.1 Experimental Setup

Datasets. We evaluate OT-VP on three datasets for TTA: PACS [21], VLCS [8],
and OfficeHome [46]. PACS [21] is composed of four domains: Photos, Art,
Cartoon, and Sketch, containing 9,991 images in 7 classes. VLCS [8] comprises
four real-world photographic datasets: VOC2007, LabelMe, Caltech, and SUN09,
containing 10,729 images in 5 classes. OfficeHome [46] consists of four
domains: Art, Clipart, Product, Real, containing 15,588 images in 65 classes.

Baselines. We compare OT-VP against the following state-of-the-art TTA
approaches:

  1. 1.

Tent [47] is a TTA method that fine-tunes the batch normalization (BN)
parameters to minimize prediction entropy during test time. Notably, ViTs do
not contain BN layers. Following the methodology outlined by [15], we adapt
Tent for use with ViTs in two distinct manners. Specifically, Tent-BN
introduces a BN layer immediately preceding the linear classifier, allowing
for the adjustment of normalization parameters within this BN layer. Tent-C
modulates the entire classifier to reduce prediction entropy.

  2. 2.

T3A [15] begins with generating pseudo-prototype representations for each
class using unlabeled target data and the pre-trained classifier.
Subsequently, the classification of each target sample is performed based on
its distance to the pseudo-prototypes.

  3. 3.

DoPrompt [49] learns domain-specific prompts for each source domain during the
training phase. Additionally, it employs a prompt adapter, a mechanism trained
to craft an appropriate prompt for individual input images. At test time, this
prompt adapter generates an input-specific prompt based on the learned source
domain prompts. Note that DoPrompt is NOT a TTA method as the prompts are
optimized during the training time.

Implementation details. Following [13], we partition the data from each domain
into training and validation splits of $80\%$ and $20\%$, respectively,
utilizing the larger split for training and the smaller one for model
selection. For all experiments, we utilize the ViT-B16 model pre-trained on
ImageNet, sourced from PyTorch [34]. Our training approach for ERM adheres to
the hyperparameters specified by [49], incorporating a dropout rate of $0.1$
and a weight decay of $10^{-2}$. The learning rate is $5\times 10^{-6}$ for
PACS and VLCS, and $10^{-5}$ for OfficeHome.

For all baseline methods, we use their official
implementation111https://github.com/DequanWang/tent
222https://github.com/matsuolab/T3A 333https://github.com/zhengzangw/DoPrompt
(see details in Appendix B.2). For implementation of our methods, we uses the
`DomainBed` library [13] 444https://github.com/facebookresearch/DomainBed.
Adopting DoPrompt’s strategy, we use 4 prompts, optimized via the AdamW
optimizer [26, 18] with a 0.1 learning rate on the target validation set. The
target dataset’s batch size is 64, with prompt training capped at 5 epochs to
avoid overfitting. We set $\lambda$ in Eq. 6 to $10^{8}$, as an estimate of
infinity. All experiments were conducted using an RTX 6000 Ada GPU.

###  4.2 Results

Tables 1 and 2 summarize our experimental outcomes in single-source and multi-
source settings, respectively. In the single-source scenario, the model is
trained on one domain and then adapted to another. The average accuracy is
calculated across all 12 domain pairings for each trial. In the multi-source
setting, one domain is designated as the target while the remaining three
serve as sources. Each reported value is an average, with standard deviations
across three separate trials. These trials vary by weight initialization and
data splits. Comprehensive results can be found in the Appendix B.

OT-VP consistently outperforms SOTA TTA methods across all datasets in both
settings. Demonstrated by the results in Tables 1 and 2, OT-VP remarkably
boosts the ERM model’s performance in both single-source and multi-source
settings. Notably, OT-VP secures substantial improvements, with enhancements
of $9.0\%$, $4.6\%$, and $1.4\%$ in the single-source scenario, and $0.7\%$,
$2.4\%$, and $1.5\%$ in the multi-source scenario across the respective
datasets: PACS, VLSC, and OfficeHome, highlighting its potent effect on model
accuracy.

The contrast in performance between alternative approaches and our OT-VP is
noteworthy. The observation that Tent-BN and Tent-C exhibit only nominal or no
improvements, and sometimes even lead to declines in performance on ViT
models, aligns with expectations considering the original design of Tent. Tent
was initially conceived for models relying heavily on batch normalization
layers for domain adaptation by adjusting these layers to minimize prediction
entropy. However, ViTs operate on a different architectural principle, lacking
batch normalization layers in their standard configuration. This fundamental
discrepancy underscores the challenges of directly applying methodologies
designed for CNNs to ViTs without modifications or considerations of
architectural differences. Furthermore, T3A consistently improves performance
over Tent in both experimental setups, though its gains are lower than those
achieved by OT-VP.

Remarkably, OT-VP demonstrates significant potential in the single-source
setting. In such cases, while methods like T3A show limited improvements, OT-
VP significantly boosts accuracy. For example, in the PACS dataset with P as
the source and S as the target (P $\rightarrow$ S), T3A increases accuracy by
only 1.8%. In contrast, OT-VP raises it by 33.1%. Another case from A to C (A
$\rightarrow$C) in PACS sees OT-VP improving accuracy by 17.3%, against T3A’s
5.7%. These results are depicted in a t-SNE visualization 3. For more details,
see the Appendix, Table 4.

Moreover, while ERM on ViTs demonstrates significant potential in adapting to
unseen target domains, many prior DG and TTA methods struggle to enhance
performance [15, 49]. This highlights the superior adaptability and efficacy
of OT-VP.

(a) Before OT-VP

(b) After OT-VP

Figure 3: t-SNE visualization showcasing the impact of OT-VP. The figures
display the representation space before and after the application of OT-VP for
A $\rightarrow$ C in the PACS dataset with the pre-trained ViT encoder.
Different numbers represent distinct class labels. (a) The initial state from
ERM, as indicated in the left image, shows the target data points are not only
distant from the source but also exhibit considerable class overlap,
especially within the central region enclosed by the ellipse. This
misalignment reflects an accuracy of $63.5\%$, an OT distance of $29.1$, and a
prediction entropy of $0.54$. (b) After employing OT-VP, the right image shows
that the target representations become more distinct and well-separated, with
classes from source and target better aligned. The target data have shifted
closer to the corresponding source representations, improving accuracy to
$81.4\%$—an increase of 17.9%, and reducing the OT distance and prediction
entropy to $25.8$ and $0.27$ respectively.  Figure 4: Prediction entropy
across Algorithms in Single-Source and Multi-Source settings on PACS. In both
settings, OT-VP demonstrates a marked reduction in entropy, outperforming
Tent-C and Tent-BN, which target entropy minimization directly.

OT-VP achieves superior performance over training-time prompt learning. Unlike
DoPrompt, our approach eliminates the need to delve into the training process,
significantly enhancing practical applicability. By leveraging target data,
OT-VP adeptly navigates the distributional shifts present in the target
domain. It optimizes target-specific prompts to effectively bridge any gaps,
moving beyond reliance solely on source domain insights.

DoPrompt, while innovative, learns domain prompts by treating training data as
out-of-distribution (OOD) samples. This strategy does not ensure that the
prompts will perform well across all potential target domains. Furthermore,
DoPrompt requires prompt learning for each domain alongside a prompt adapter
(an auxiliary model) to tailor prompts for every target input image. In
contrast, our method optimizes universal prompts for a singular target domain,
streamlining the process.

As evidenced in Table 1, DoPrompt experiences significant performance drops
when limited to a single domain, which could limit its applicability in
scenarios where source data is scarce, such as in medical imaging. Our method
surpasses DoPrompt in both scenarios, underscoring the efficiency and
accessibility of learning prompts at test time.

OT-VP implicitly reduces prediction entropy. Consistent with prior research
[47], there’s an observed correlation between prediction entropy and
accuracy—lower entropy often signifies more accurate and confident
predictions. Unlike traditional approaches that explicitly target entropy
reduction by adjusting model parameters [47, 40], OT-VP achieves this
indirectly through the strategic application of Optimal Transport. This
involves leveraging a cost metric that encompasses both features and labels 7,
aiming to align the target distribution more closely with the source
distribution, thereby enhancing model confidence near the decision boundary.
This alignment is visually supported by representations such as those depicted
in Fig. 3, a t-SNE visualization for source A and the target C (A
$\rightarrow$ C) within the PACS dataset.

A comparative analysis of prediction entropy among ERM, Tent-C, Tent-BN, and
OT-VP—illustrated in Fig. 4—demonstrates that OT-VP can significantly lower
entropy through the refined optimization of prompts. Remarkably, it does so
even when compared with methods like Tent-C and Tent-BN, which pursue entropy
minimization directly. It’s important to note that the improvements achieved
by Tent-C and Tent-BN result from carefully balancing accuracy and entropy
reduction when selecting their hyperparameters.

###  4.3 Ablation Study

Analysis on the objective functions.  To explore the efficacy of our approach,
we experimented with directly minimizing entropy during the prompt learning
process. Interestingly, this direct focus on entropy reduction did not yield
improvements. Instead, we observed a monotonic decrease in accuracy as entropy
was reduced. This suggests that while reducing entropy might intuitively seem
beneficial, focusing solely on this aspect can lead to overconfidence in the
model’s predictions, including those that are incorrect. Such over-trust
manifests as high confidence in erroneous predictions, underlining a potential
pitfall of learning universal visual prompts purely on entropy reduction.
These findings validate the effectiveness of our chosen objective function,
which not only achieves the desired outcome but also implicitly manages
entropy without compromising the reliability of predictions.

Analysis on $\lambda$.  In our further investigations, we delved into the
impact of the hyperparameter $\lambda$ within Eq. 7, particularly in the
single-source setting for PACS, across two distinct scenarios:
S$\rightarrow$C, P$\rightarrow$S, and P$\rightarrow$C. These scenarios
represent conditions where OT-VP underperforms, outperforms, and performs
similarly to other methods, respectively. Our experiments spanned a range of
$\lambda$ values: $[0,1,10^{2},10^{4},10^{6},10^{8}]$, where $\lambda=0$ and
$\lambda=10^{8}$ corresponds to the OT-VP-B and OT-VP, respectively (details
in Appendix 4).

Our results highlight two crucial insights: Firstly, incorporating label
information into the learned prompts significantly enhances the alignment
between the source and target domains, corroborating findings from prior
research [1]. This label augmentation facilitates a deeper, more meaningful
adaptation process. Secondly, we observed a performance decrement with the
reduction of $\lambda$ values, as illustrated in Fig. 5. However, performance
reaches a plateau and stabilizes when $\lambda$ is sufficiently large,
approaching an effective infinity in relation to feature distance, indicating
an optimal balance in the adaptation mechanism.

The role of $\lambda$ in the cost function is crucial—it modulates the extent
to which transportation across different classes is permissible. A higher
$\lambda$ effectively restricts cross-class transport, serving as a
preventative measure against such occurrences. Notably, setting $\lambda$ to
infinity aligns the OT distance with the Wasserstein distance, underlining the
significance of this parameter. Our analysis suggests that a larger $\lambda$
facilitates a reduction in overfitting risk during prompt optimization with
stochastic gradient descent (SGD), especially when utilizing pseudo labels.
This is achieved by imposing a stricter barrier against cross-class
transportation, thereby ensuring a more disciplined adaptation process.

Figure 5: Influence of hyperparameter $\lambda$ on Single-Source performance.
Accuracy declines with smaller $\lambda$ values but stabilizes when $\lambda$
is large. These trends reveal the pivotal role of $\lambda$ in preventing
cross-class transport and its impact on overfitting, particularly when using
pseudo labels during prompt optimization. Notably, OT-VP’s $\lambda$ is
$10^{8}$.

Analysis on prompt length. We opted for a prompt length of 4, aligning with
DoPrompt’s configuration. Our experiments across varying prompt lengths—2, 4,
6, and 8—revealed that OT-VP’s performance remained relatively stable for
smaller lengths (2, 4, 6), as indicated in Fig. 6. However, a notable decline
in performance was observed with a length of 8, attributed to the increased
risk of overfitting, a consequence of the absence of target labels. The
decision to fix the prompt length is driven by the necessity to pre-select all
parameters prior to any engagement with the target data, ensuring a
standardized approach in our experiments.

Analysis on computation time.  Despite employing SGD to optimize prompt
tokens, OT-VP remains computationally efficient. We optimize only 4 prompt
tokens over 5 epochs, utilizing a 20% hold-out split from both source and
target data. While the multi-source setting involves processing triple the
data to compute source representations compared to the single-source setting,
the time required for both is nearly identical. Specifically, the average time
is 39.5 seconds for the multi-source and 38.7 seconds for the single-source
setting on the PACS dataset on our hardware. Moreover, the computational time
is slightly influenced by the size of the datasets but remains relatively
quick. For instance, in the PACS dataset, domain S, which has more than double
the data of domain P, requires more processing time—51.7 seconds for S versus
34.5 seconds for P in the multi-source setting. Full results for PACS can be
found in Table 3 in Appendix. In conclusion, OT-VP can efficiently learn
prompts in both single and multi-source settings without significant
computational overhead.

Figure 6: Effect of Prompt Length on OT-VP Performance. Consistency in
performance is maintained for shorter prompt lengths (2, 4, 6), but an
extended length of 8 prompts leads to a performance drop, likely due to
overfitting in the absence of target labels.

##  5 Conclusion

In this paper, we present OT-VP, a novel test-time adaptation approach that
leverages visual prompt learning for effective test-time adaptation. OT-VP
stands out by adapting without altering the pre-trained model and effectively
aligning the source and target domains, offering a more practical solution
than established methods. Our experiments reveal OT-VP’s strengths:
consistently outperforming existing TTA methods for ViT and DG prompt
learning, and reducing prediction entropy to increase model confidence. By
optimizing universal prompts for the target domain, OT-VP simplifies the
adaptation process, enhancing the applicability of deep learning models in
real-world settings.

## References

  * Alvarez-Melis and Fusi [2020] David Alvarez-Melis and Nicolo Fusi.  Geometric dataset distances via optimal transport.  _Advances in Neural Information Processing Systems_ , 33:21428–21439, 2020.
  * Bahng et al. [2022] Hyojin Bahng, Ali Jahanian, Swami Sankaranarayanan, and Phillip Isola.  Visual prompting: Modifying pixel space to adapt pre-trained models.  _arXiv preprint arXiv:2203.17274_ , 2(3):7, 2022.
  * Ben-David et al. [2006] Shai Ben-David, John Blitzer, Koby Crammer, and Fernando Pereira.  Analysis of representations for domain adaptation.  In _Advances in Neural Information Processing Systems_. MIT Press, 2006.
  * Blanchard et al. [2011] Gilles Blanchard, Gyemin Lee, and Clayton Scott.  Generalizing from several related classification tasks to a new unlabeled sample.  _Advances in neural information processing systems_ , 24, 2011.
  * Courty et al. [2016] Nicolas Courty, Rémi Flamary, Devis Tuia, and Alain Rakotomamonjy.  Optimal transport for domain adaptation.  _IEEE transactions on pattern analysis and machine intelligence_ , 39(9):1853–1865, 2016.
  * Cuturi [2013] Marco Cuturi.  Sinkhorn distances: Lightspeed computation of optimal transport.  _Advances in neural information processing systems_ , 26, 2013.
  * Dosovitskiy et al. [2021] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby.  An image is worth 16x16 words: Transformers for image recognition at scale.  In _International Conference on Learning Representations_ , 2021.
  * Fang et al. [2013] Chen Fang, Ye Xu, and Daniel N Rockmore.  Unbiased metric learning: On the utilization of multiple datasets and web images for softening bias.  In _Proceedings of the IEEE International Conference on Computer Vision_ , pages 1657–1664, 2013.
  * Flamary et al. [2021] Rémi Flamary, Nicolas Courty, Alexandre Gramfort, Mokhtar Z. Alaya, Aurélie Boisbunon, Stanislas Chambon, Laetitia Chapel, Adrien Corenflos, Kilian Fatras, Nemo Fournier, Léo Gautheron, Nathalie T.H. Gayraud, Hicham Janati, Alain Rakotomamonjy, Ievgen Redko, Antoine Rolet, Antony Schutz, Vivien Seguy, Danica J. Sutherland, Romain Tavenard, Alexander Tong, and Titouan Vayer.  Pot: Python optimal transport.  _Journal of Machine Learning Research_ , 22(78):1–8, 2021.
  * Gao et al. [2023] Yunhe Gao, Xingjian Shi, Yi Zhu, Hao Wang, Zhiqiang Tang, Xiong Zhou, Mu Li, and Dimitris N. Metaxas.  Visual prompt tuning for test-time domain adaptation, 2023.
  * Ge et al. [2023] Chunjiang Ge, Rui Huang, Mixue Xie, Zihang Lai, Shiji Song, Shuang Li, and Gao Huang.  Domain adaptation via prompt learning.  _IEEE Transactions on Neural Networks and Learning Systems_ , 2023.
  * Gretton et al. [2012] Arthur Gretton, Karsten M Borgwardt, Malte J Rasch, Bernhard Schölkopf, and Alexander Smola.  A kernel two-sample test.  _The Journal of Machine Learning Research_ , 13(1):723–773, 2012.
  * Gulrajani and Lopez-Paz [2020] Ishaan Gulrajani and David Lopez-Paz.  In search of lost domain generalization.  _arXiv preprint arXiv:2007.01434_ , 2020.
  * Hendrycks and Dietterich [2019] Dan Hendrycks and Thomas Dietterich.  Benchmarking neural network robustness to common corruptions and perturbations.  _arXiv preprint arXiv:1903.12261_ , 2019.
  * Iwasawa and Matsuo [2021] Yusuke Iwasawa and Yutaka Matsuo.  Test-time classifier adjustment module for model-agnostic domain generalization.  In _Advances in Neural Information Processing Systems_ , pages 2427–2440. Curran Associates, Inc., 2021.
  * Jia et al. [2022] Menglin Jia, Luming Tang, Bor-Chun Chen, Claire Cardie, Serge Belongie, Bharath Hariharan, and Ser-Nam Lim.  Visual prompt tuning.  In _European Conference on Computer Vision_ , pages 709–727. Springer, 2022.
  * Kantorovich [1942] Leonid V Kantorovich.  On the translocation of masses.  In _Dokl. Akad. Nauk. USSR (NS)_ , pages 199–201, 1942.
  * Kingma and Ba [2014] Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ , 2014.
  * Koh et al. [2021] Pang Wei Koh, Shiori Sagawa, Henrik Marklund, Sang Michael Xie, Marvin Zhang, Akshay Balsubramani, Weihua Hu, Michihiro Yasunaga, Richard Lanas Phillips, Irena Gao, et al.  Wilds: A benchmark of in-the-wild distribution shifts.  In _International conference on machine learning_ , pages 5637–5664. PMLR, 2021.
  * Le et al. [2021] Trung Le, Tuan Nguyen, Nhat Ho, Hung Bui, and Dinh Phung.  Lamda: Label matching deep domain adaptation.  In _Proceedings of the 38th International Conference on Machine Learning_ , pages 6043–6054. PMLR, 2021.
  * Li et al. [2017] Da Li, Yongxin Yang, Yi-Zhe Song, and Timothy M Hospedales.  Deeper, broader and artier domain generalization.  In _Proceedings of the IEEE international conference on computer vision_ , pages 5542–5550, 2017.
  * Liang et al. [2020] Jian Liang, Dapeng Hu, and Jiashi Feng.  Do we really need to access the source data? source hypothesis transfer for unsupervised domain adaptation.  In _International conference on machine learning_ , pages 6028–6039. PMLR, 2020.
  * Liang et al. [2021] Jian Liang, Dapeng Hu, Yunbo Wang, Ran He, and Jiashi Feng.  Source data-absent unsupervised domain adaptation through hypothesis transfer and labeling transfer.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 44(11):8602–8617, 2021.
  * Liang et al. [2023] Jian Liang, Ran He, and Tieniu Tan.  A comprehensive survey on test-time adaptation under distribution shifts.  _arXiv preprint arXiv:2303.15361_ , 2023.
  * Liu et al. [2021] Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo.  Swin transformer: Hierarchical vision transformer using shifted windows.  In _Proceedings of the IEEE/CVF international conference on computer vision_ , pages 10012–10022, 2021.
  * Loshchilov and Hutter [2017] Ilya Loshchilov and Frank Hutter.  Decoupled weight decay regularization.  _arXiv preprint arXiv:1711.05101_ , 2017.
  * Ma et al. [2024] Xiaosong Ma, Jie Zhang, Song Guo, and Wenchao Xu.  Swapprompt: Test-time prompt adaptation for vision-language models.  _Advances in Neural Information Processing Systems_ , 36, 2024.
  * Mansour et al. [2009] Yishay Mansour, Mehryar Mohri, and Afshin Rostamizadeh.  Domain adaptation: Learning bounds and algorithms.  _arXiv preprint arXiv:0902.3430_ , 2009.
  * Mehra et al. [2023] Akshay Mehra, Yunbei Zhang, and Jihun Hamm.  Analysis of task transferability in large pre-trained classifiers.  _arXiv preprint arXiv:2307.00823_ , 2023.
  * Mirza et al. [2022] M Jehanzeb Mirza, Jakub Micorek, Horst Possegger, and Horst Bischof.  The norm must go on: Dynamic unsupervised domain adaptation by normalization.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , pages 14765–14775, 2022.
  * Mirza et al. [2023] Muhammad Jehanzeb Mirza, Pol Jané Soneira, Wei Lin, Mateusz Kozinski, Horst Possegger, and Horst Bischof.  Actmad: Activation matching to align distributions for test-time-training.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 24152–24161, 2023.
  * Mummadi et al. [2021] Chaithanya Kumar Mummadi, Robin Hutmacher, Kilian Rambach, Evgeny Levinkov, Thomas Brox, and Jan Hendrik Metzen.  Test-time adaptation to distribution shift by confidence maximization and input transformation.  _arXiv preprint arXiv:2106.14999_ , 2021.
  * Naseer et al. [2021] Muhammad Muzammal Naseer, Kanchana Ranasinghe, Salman H Khan, Munawar Hayat, Fahad Shahbaz Khan, and Ming-Hsuan Yang.  Intriguing properties of vision transformers.  _Advances in Neural Information Processing Systems_ , 34:23296–23308, 2021.
  * Paszke et al. [2019] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al.  Pytorch: An imperative style, high-performance deep learning library.  _Advances in neural information processing systems_ , 32, 2019.
  * Peyré et al. [2019] Gabriel Peyré, Marco Cuturi, et al.  Computational optimal transport: With applications to data science.  _Foundations and Trends® in Machine Learning_ , 11(5-6):355–607, 2019.
  * Prabhudesai et al. [2023] Mihir Prabhudesai, Tsung-Wei Ke, Alexander Cong Li, Deepak Pathak, and Katerina Fragkiadaki.  Diffusion-tta: Test-time adaptation of discriminative models via generative feedback.  In _Thirty-seventh Conference on Neural Information Processing Systems_ , 2023.
  * Radford et al. [2021] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al.  Learning transferable visual models from natural language supervision.  In _International conference on machine learning_ , pages 8748–8763. PMLR, 2021.
  * Raghu et al. [2021] Maithra Raghu, Thomas Unterthiner, Simon Kornblith, Chiyuan Zhang, and Alexey Dosovitskiy.  Do vision transformers see like convolutional neural networks?  _Advances in neural information processing systems_ , 34:12116–12128, 2021.
  * Recht et al. [2019] Benjamin Recht, Rebecca Roelofs, Ludwig Schmidt, and Vaishaal Shankar.  Do imagenet classifiers generalize to imagenet?  In _International conference on machine learning_ , pages 5389–5400. PMLR, 2019.
  * Samadh et al. [2023] Jameel Hassan Abdul Samadh, Hanan Gani, Noor Hazim Hussein, Muhammad Uzair Khattak, Muzammal Naseer, Fahad Khan, and Salman Khan.  Align your prompts: Test-time prompting with distribution alignment for zero-shot generalization.  In _Thirty-seventh Conference on Neural Information Processing Systems_ , 2023.
  * Schneider et al. [2020] Steffen Schneider, Evgenia Rusak, Luisa Eck, Oliver Bringmann, Wieland Brendel, and Matthias Bethge.  Improving robustness against common corruptions by covariate shift adaptation.  _Advances in neural information processing systems_ , 33:11539–11551, 2020.
  * Shen et al. [2018] Jian Shen, Yanru Qu, Weinan Zhang, and Yong Yu.  Wasserstein distance guided representation learning for domain adaptation.  In _Proceedings of the AAAI conference on artificial intelligence_ , 2018.
  * Sinha et al. [2017] Aman Sinha, Hongseok Namkoong, Riccardo Volpi, and John Duchi.  Certifying some distributional robustness with principled adversarial training.  _arXiv preprint arXiv:1710.10571_ , 2017.
  * Sun et al. [2020] Yu Sun, Xiaolong Wang, Zhuang Liu, John Miller, Alexei Efros, and Moritz Hardt.  Test-time training with self-supervision for generalization under distribution shifts.  In _International conference on machine learning_ , pages 9229–9248. PMLR, 2020.
  * Tan et al. [2021] Yang Tan, Yang Li, and Shao-Lun Huang.  Otce: A transferability metric for cross-domain cross-task representations.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , pages 15779–15788, 2021.
  * Venkateswara et al. [2017] Hemanth Venkateswara, Jose Eusebio, Shayok Chakraborty, and Sethuraman Panchanathan.  Deep hashing network for unsupervised domain adaptation.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2017.
  * Wang et al. [2021] Dequan Wang, Evan Shelhamer, Shaoteng Liu, Bruno Olshausen, and Trevor Darrell.  Tent: Fully test-time adaptation by entropy minimization.  In _International Conference on Learning Representations_ , 2021.
  * Wang et al. [2022] Zifeng Wang, Zizhao Zhang, Chen-Yu Lee, Han Zhang, Ruoxi Sun, Xiaoqi Ren, Guolong Su, Vincent Perot, Jennifer Dy, and Tomas Pfister.  Learning to prompt for continual learning.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 139–149, 2022.
  * Zheng et al. [2022] Zangwei Zheng, Xiangyu Yue, Kai Wang, and Yang You.  Prompt vision transformer for domain generalization.  _arXiv preprint arXiv:2208.08914_ , 2022.
  * Zhou et al. [2022] Kaiyang Zhou, Ziwei Liu, Yu Qiao, Tao Xiang, and Chen Change Loy.  Domain generalization: A survey.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 45(4):4396–4415, 2022.

Supplementary Material

##  Appendix A Limitations

One limitation of our OT-VP approach is its reliance on the quality of pseudo
labels for computing the Optimal Transport distance. As visualized in our
t-SNE plots 3, there’s a risk of occasional misalignment due to inaccurate
pseudo-labeling, which can adversely affect the model’s ability to accurately
bridge the source and target domain gap. While implementing entropy-based
filtering akin to T3A [15] could mitigate this by filtering out high-entropy,
less reliable pseudo labels, the fundamental limitation remains: OT-VP’s
capacity to perform effective test-time adaptation may be significantly
hindered if the pseudo labels are entirely unreliable or carry no meaningful
information about the true class distribution.

##  Appendix B Full Results

### B.1

In this section, we present the computation time for OT-VP on the PACS
dataset. For the single-source setting, the average computation time is
calculated across three different sources.

Setting | A | C | P | S | Average
---|---|---|---|---|---
Single-Source | 32.6 | 37.5 | 33.7 | 50.8 | 38.7
Multi-Source | 33.9 | 38.0 | 34.5 | 51.7 | 39.5
Table 3: Average computation time (seconds) for OT-VP on PACS dataset.

### B.2

We present the implementation details of all baseline methods. For the
implementation of DoPrompt, we set the prompt length to 4, with the
coefficient $\lambda$ explored over the set $\\{0.1,1,10\\}$. The $M$
parameter for T3A is chosen from $\\{1,5,20,50,100,\mathrm{N/A}\\}$, while the
configuration for Tent is determined from combinations of $\\{0.1,1.0,10.0\\}$
and $\\{1,3\\}$.

### B.3

In this section, we present the comprehensive outcomes in Tables 1 and 2. The
experiments were conducted using three different seeds {0, 1, 2} within the
`DomainBed` framework.

Algorithm |  | A | C | P | S
---|---|---|---|---|---
ERM | A | - |  64.5$\pm$0.9 |  98.9$\pm$0.2 |  56.4$\pm$2.0
C |  83.9$\pm$3.3 | - |  89.6$\pm$0.5 |  69.2$\pm$2.1
P |  74.2$\pm$1.4 |  44.4$\pm$1.2 | - |  34.1$\pm$4.3
S |  50.8$\pm$3.6 |  58.4$\pm$6.0 |  49.5$\pm$4.4 | -
DoPrompt | A | - |  64.6$\pm$0.6 |  98.5$\pm$0.7 |  56.5$\pm$4.7
C |  84.1$\pm$2.2 | - |  90.1$\pm$1.7 |  74.0$\pm$2.2
P |  75.6$\pm$2.0 |  46.2$\pm$0.7 | - |  35.2$\pm$3.8
S |  46.4$\pm$4.9 |  55.0$\pm$5.8 |  45.1$\pm$3.0 | -
Tent-C | A | - |  64.6$\pm$0.6 |  98.9$\pm$0.2 |  56.3$\pm$5.8
C |  83.9$\pm$3.0 | - |  89.6$\pm$0.2 |  69.0$\pm$2.0
P |  74.4$\pm$1.9 |  44.5$\pm$1.3 | - |  33.7$\pm$4.9
S |  50.4$\pm$3.5 |  58.3$\pm$6.0 |  49.0$\pm$3.7 | -
Tent-BN | A | - |  71.9$\pm$0.9 |  98.9$\pm$0.5 |  66.6$\pm$3.7
C |  84.9$\pm$2.1 | - |  91.3$\pm$1.7 |  71.7$\pm$1.0
P |  78.0$\pm$1.7 |  56.0$\pm$3.6 | - |  41.8$\pm$2.5
S |  56.3$\pm$4.0 |  62.9$\pm$3.1 |  47.5$\pm$2.9 | -
T3A | A | - |  70.2$\pm$2.1 |  98.6$\pm$0.5 |  67.9$\pm$4.5
C |  86.3$\pm$1.7 | - |  94.4$\pm$1.4 |  71.1$\pm$1.4
P |  80.2$\pm$1.6 |  53.9$\pm$3.9 | - |  35.9$\pm$2.4
S |  69.0$\pm$4.0 |  69.9$\pm$5.9 |  56.9$\pm$2.5 | -
OT-VP-B | A | - |  76.7$\pm$2.9 |  98.3$\pm$0.1 |  66.8$\pm$2.8
C |  84.4$\pm$0.8 | - |  92.2$\pm$2.2 |  69.8$\pm$1.2
P |  77.8$\pm$0.4 |  56.8$\pm$6.9 | - |  63.9$\pm$2.1
S |  44.7$\pm$3.1 |  58.1$\pm$3.6 |  40.4$\pm$3.3 | -
OT-VP | A | - |  81.8$\pm$0.3 |  99.0$\pm$0.3 |  72.2$\pm$2.9
C |  84.4$\pm$2.2 | - |  92.6$\pm$1.6 |  69.5$\pm$0.8
P |  80.4$\pm$1.7 |  64.3$\pm$4.2 | - |  67.2$\pm$2.6
S |  56.0$\pm$3.9 |  64.6$\pm$4.4 |  50.5$\pm$1.0 | -
Table 4: Single-Source Full Results on PACS in Table 1

Algorithm | A | C | P | S | Average
---|---|---|---|---|---
ERM |  91.3$\pm$0.5 |  82.3$\pm$0.7 |  98.9$\pm$0.3 |  75.6$\pm$0.4 | 87.0
DoPrompt |  91.4$\pm$0.5 |  81.8$\pm$0.4 |  99.5$\pm$0.4 |  77.1$\pm$0.5 | 87.5
Tent-C |  91.6$\pm$0.7 |  82.7$\pm$1.3 |  98.9$\pm$0.4 |  75.7$\pm$0.5 | 87.2
Tent-BN |  91.1$\pm$0.3 |  82.4$\pm$1.3 |  98.3$\pm$0.4 |  76.8$\pm$0.7 | 87.2
T3A |  91.5$\pm$0.5 |  81.8$\pm$0.9 |  99.0$\pm$0.5 |  77.4$\pm$0.3 | 87.4
OT-VP-B |  91.2$\pm$0.5 |  81.8$\pm$0.7 |  99.4$\pm$0.5 |  77.4$\pm$0.5 | 87.3
OT-VP |  92.0$\pm$0.5 |  83.0$\pm$0.4 |  99.2$\pm$0.4 |  76.4$\pm$0.2 | 87.7

Table 5: Multi-Source Full Results on PACS in Table 2 Algorithm |  | C | L | S | V
---|---|---|---|---|---
ERM | C | - |  50.7$\pm$1.2 |  47.9$\pm$2.3 |  47.0$\pm$2.1
L |  62.9$\pm$1.4 | - |  55.8$\pm$1.6 |  63.1$\pm$2.2
S |  67.5$\pm$1.5 |  59.9$\pm$1.3 | - |  67.7$\pm$2.4
V |  96.5$\pm$0.7 |  66.1$\pm$2.1 |  80.3$\pm$1.5 | -
DoPrompt | C | - |  53.4$\pm$1.5 |  50.0$\pm$1.6 |  50.5$\pm$1.8
L |  71.7$\pm$2.1 | - |  57.8$\pm$1.5 |  70.1$\pm$1.3
S |  67.8$\pm$1.9 |  62.5$\pm$0.8 | - |  66.2$\pm$1.9
V |  98.6$\pm$0.8 |  62.0$\pm$1.9 |  78.8$\pm$2.1 | -
Tent-C | C | - |  50.4$\pm$1.7 |  48.3$\pm$1.3 |  47.0$\pm$2.9
L |  70.3$\pm$1.9 | - |  55.8$\pm$2.4 |  63.2$\pm$2.1
S |  67.2$\pm$2.1 |  59.8$\pm$1.7 | - |  67.9$\pm$2.0
V |  96.5$\pm$0.6 |  66.0$\pm$2.1 |  88.2$\pm$1.8 | -
Tent-BN | C | - |  71.9$\pm$2.6 |  98.9$\pm$2.1 |  66.6$\pm$1.8
L |  84.9$\pm$2.8 | - |  91.3$\pm$3.0 |  71.7$\pm$2.1
S |  78.0$\pm$1.9 |  56.0$\pm$0.7 | - |  41.8$\pm$1.8
V |  56.3$\pm$2.2 |  62.9$\pm$1.9 |  47.5$\pm$1.3 | -
T3A | C | - |  51.8$\pm$1.6 |  57.0$\pm$1.8 |  57.3$\pm$1.2
L |  83.6$\pm$1.8 | - |  62.7$\pm$1.2 |  64.3$\pm$2.1
S |  71.1$\pm$1.9 |  60.5$\pm$1.7 | - |  67.4$\pm$1.8
V |  97.3$\pm$0.6 |  66.8$\pm$1.9 |  80.3$\pm$1.4 | -
OT-VP-B | C | - |  55.7$\pm$2.4 |  50.0$\pm$2.1 |  47.0$\pm$2.6
L |  73.1$\pm$1.8 | - |  56.4$\pm$1.8 |  60.7$\pm$2.1
S |  67.1$\pm$2.3 |  60.8$\pm$1.5 | - |  67.3$\pm$1.9
V |  96.8$\pm$0.6 |  68.4$\pm$1.9 |  79.1$\pm$1.2 | -
OT-VP | C | - |  59.9$\pm$1.2 |  51.3$\pm$2.3 |  48.9$\pm$0.8
L |  90.8$\pm$0.6 | - |  56.3$\pm$1.2 |  63.8$\pm$0.9
S |  69.6$\pm$1.9 |  64.2$\pm$0.8 | - |  68.8$\pm$1.2
V |  96.8$\pm$0.6 |  69.3$\pm$0.9 |  80.8$\pm$1.5 | -
Table 6: Single-Source Full Results on VLCS in Table 1

Algorithm | C | L | S | V | Average
---|---|---|---|---|---
ERM |  96.5$\pm$0.5 |  65.5$\pm$1.1 |  75.2$\pm$0.8 |  76.7$\pm$0.4 | 78.5
DoPrompt |  98.2$\pm$0.8 |  67.8$\pm$0.8 |  75.3$\pm$0.7 |  79.9$\pm$0.5 | 80.3
Tent-C |  97.7$\pm$0.5 |  65.2$\pm$1.0 |  75.3$\pm$0.7 |  76.9$\pm$0.4 | 78.8
Tent-BN |  86.3$\pm$1.0 |  66.2$\pm$0.9 |  68.8$\pm$0.7 |  72.6$\pm$0.5 | 73.5
T3A |  97.3$\pm$0.5 |  65.6$\pm$0.9 |  78.0$\pm$0.7 |  79.3$\pm$0.7 | 80.0
OT-VP-B |  96.8$\pm$0.4 |  71.9$\pm$0.8 |  75.2$\pm$0.8 |  76.9$\pm$0.4 | 80.2
OT-VP |  96.8$\pm$0.4 |  73.1$\pm$1.1 |  76.8$\pm$0.8 |  77.0$\pm$0.5 | 80.9

Table 7: Multi-Source Full Results on VLCS in Table 2 Algorithm |  | A | C | P | R
---|---|---|---|---|---
ERM | A | - |  54.3$\pm$0.5 |  71.4$\pm$1.6 |  77.0$\pm$0.4
C |  67.4$\pm$0.7 | - |  70.0$\pm$1.2 |  73.2$\pm$0.4
P |  62.9$\pm$2.3 |  47.8$\pm$0.1 | - |  78.9$\pm$0.7
R |  70.3$\pm$0.7 |  49.2$\pm$1.8 |  78.5$\pm$0.5 | -
DoPrompt | A | - |  52.1$\pm$3.2 |  71.7$\pm$0.1 |  79.0$\pm$0.5
C |  67.4$\pm$0.1 | - |  71.7$\pm$0.4 |  75.5$\pm$0.1
P |  66.8$\pm$1.4 |  47.8$\pm$0.1 | - |  79.0$\pm$0.1
R |  72.2$\pm$1.1 |  48.8$\pm$1.9 |  79.6$\pm$0.7 | -
Tent-C | A | - |  54.5$\pm$0.6 |  69.9$\pm$1.5 |  76.9$\pm$0.6
C |  66.9$\pm$0.7 | - |  69.6$\pm$1.4 |  73.6$\pm$0.2
P |  62.9$\pm$0.3 |  47.9$\pm$0.1 | - |  78.6$\pm$0.7
R |  71.0$\pm$0.5 |  47.1$\pm$1.7 |  79.9$\pm$0.3 | -
Tent-BN | A | - |  56.7$\pm$0.7 |  70.5$\pm$0.8 |  77.5$\pm$0.8
C |  67.9$\pm$0.6 | - |  70.4$\pm$1.4 |  72.9$\pm$0.4
P |  65.4$\pm$1.2 |  48.6$\pm$0.3 | - |  79.1$\pm$0.3
R |  72.8$\pm$0.5 |  49.5$\pm$1.2 |  79.9$\pm$0.3 | -
T3A | A | - |  55.1$\pm$0.7 |  71.2$\pm$1.2 |  76.6$\pm$0.7
C |  67.9$\pm$0.7 | - |  71.5$\pm$1.2 |  74.8$\pm$0.3
P |  67.1$\pm$0.8 |  48.7$\pm$0.2 | - |  80.3$\pm$0.5
R |  72.9$\pm$0.5 |  49.8$\pm$1.5 |  80.9$\pm$0.4 | -
OT-VP-B | A | - |  55.1$\pm$0.8 |  70.5$\pm$0.8 |  75.0$\pm$0.5
C |  65.8$\pm$0.4 | - |  69.4$\pm$0.8 |  73.1$\pm$0.2
P |  64.6$\pm$1.8 |  49.1$\pm$0.1 | - |  77.4$\pm$0.4
R |  71.1$\pm$0.9 |  52.1$\pm$1.8 |  79.6$\pm$0.6 | -
OT-VP | A | - |  55.0$\pm$0.7 |  71.4$\pm$1.2 |  76.9$\pm$0.7
C |  67.6$\pm$0.7 | - |  70.1$\pm$0.9 |  73.6$\pm$0.8
P |  68.7$\pm$0.9 |  49.7$\pm$0.6 | - |  79.9$\pm$0.5
R |  71.3$\pm$0.5 |  52.2$\pm$1.3 |  80.8$\pm$0.4 | -
Table 8: Single-Source Full Results on OfficeHome in Table 1

Algorithm | A | C | P | S | Average
---|---|---|---|---|---
ERM |  73.8$\pm$0.2 |  57.3$\pm$0.6 |  80.3$\pm$0.1 |  83.0$\pm$0.8 | 73.6
DoPrompt |  73.4$\pm$0.4 |  58.8$\pm$0.5 |  81.7$\pm$0.2 |  84.8$\pm$0.7 | 74.7
Tent-C |  73.5$\pm$0.4 |  57.3$\pm$0.6 |  80.4$\pm$0.1 |  83.2$\pm$0.9 | 73.6
Tent-BN |  73.5$\pm$0.4 |  58.8$\pm$0.5 |  81.9$\pm$0.2 |  84.0$\pm$0.8 | 74.6
T3A |  74.2$\pm$0.3 |  58.3$\pm$0.5 |  81.8$\pm$0.1 |  84.6$\pm$0.7 | 74.7
OT-VP-B |  74.0$\pm$0.4 |  58.9$\pm$0.5 |  80.7$\pm$0.2 |  83.5$\pm$0.7 | 74.3
OT-VP |  74.2$\pm$0.4 |  59.6$\pm$0.5 |  82.3$\pm$0.1 |  84.1$\pm$0.8 | 75.1

Table 9: Multi-Source Full Results on OfficeHome in Table 2


# On proximal gradient mapping and its minimization in norm via potential
function-based acceleration

Beier Chen  Department of Mathematics, National University of Defense
Technology, Changsha, Hunan 410073, China. Email<EMAIL_ADDRESS>Hui
Zhang Department of Mathematics, National University of Defense Technology,
Changsha, Hunan 410073, China. Email<EMAIL_ADDRESS>
###### Abstract

The proximal gradient descent method, well-known for composite optimization,
can be completely described by the concept of proximal gradient mapping. In
this paper, we highlight our previous two discoveries of proximal gradient
mapping–norm monotonicity and refined descent, with which we are able to
extend the recently proposed potential function-based framework from gradient
descent to proximal gradient descent.

Keywords. potential function-based framework, proximal gradient mapping,
acceleration, proximal gradient method, composite optimization

AMS subject classifications. 90C25, 90C33, 90C47

##  1 Introduction

First-order methods, which go back to 1847 with the work of Cauchy on the
vanilla gradient descent, have recently revived a great deal of research
interest due to their low iteration cost as well as low memory storage. How to
establish convergence criteria and determine convergence rates for a given
first-order method heavily depends on the choice of optimality measures. The
standard optimization literature on smooth convex first-order optimization
mainly provides guarantees for optimality gap (in terms of function value) and
distance gap (between the iterate and the minimizer set). However, these
optimality measures only have theoretical value but do not fit practical
applications because the optimal function value and the minimizer set are
usually unknown before applying first-order methods.

Due to the basic fact that minimizing a smooth convex function is equivalent
to minimizing the norm of its gradient, a more practical alternative to the
optimality gap and distance gap may be the norm of gradient. This fact was
initially exploited by Nesterov in the work [5], which argued that using the
norm of gradient as an optimality measure is natural and more practical. There
are many different potential function-based frameworks covering broad classes
of first-order methods for providing optimality gap and distance gap
guarantees, but not for the norm of gradient. This absence motives the authors
of [2] to introduce a novel potential function-based framework, with which
they are able to address the problem of minimizing the norm of the gradient of
a smooth convex function. As a natural development, we wonder whether their
potential function-based framework can be extended to other types of first-
order methods.

In this paper, we go a small step further along this direction by applying
their potential function-based framework to composite optimization–minimizing
the sum of a smooth convex function and a possibly nonsmooth convex function.
To this end, we first revisit the proximal gradient mapping and highlight our
previous two discoveries–norm monotonicity and refined descent; both of them
may have an independent interest in their own. Then, built on the newly
discovered properties and the potential function-based framework of [2], we
establish the sublinear convergence for the norm sequence of proximal gradient
mapping. Moreover, we construct a new potential function to obtain faster
convergence.

At the time of writing this paper, a closely related work [3], posted on arXiv
very recently, also addressed the problem of minimizing the proximal gradient
mapping under the name of proximal subgradient norm minimization. Here, we
would like to point out three main differences between this work and ours.
First, the potential function-based frameworks are different: they followed
the discrete Lyapunov function in [6] while we extended that in [2]. Second,
the accelerated algorithmic schemes are different: they analyzed the faster
iterative shrinkage-thresholding algorithm (FISTA) in [1] while we run two
iterative processes for acceleration. At last, the main results are different:
they never used the norm monotonicity of proximal gradient mapping so that
their result on proximal subgradient norm minimization for ISTA seems
suboptimal. Nevertheless, we believe that these two works have their own
merits and complement each other.

The remainder of the paper is organized as follows. In Section 2, we present
the basic notation and preliminary knowledge of different function classes,
the proximal gradient method, and the potential function-based framework of
[2]. In Section 3, we revisit the proximal gradient mapping and establish two
new properties. In Section 4, we study the problem of minimizing the norm of
proximal gradient mapping and show convergence results. Finally, section 5
gives some concluding remarks.

##  2 Preliminaries and preliminary results

In this paper, we restrict our attention to an arbitrary finite dimensional
space $\mathbb{R}^{d}$ associated with inner product
$\langle\cdot,\cdot\rangle$ and norm
$\|\cdot\|:=\sqrt{\langle\cdot,\cdot\rangle}$. For a closed subset
$Q\subseteq\mathbb{R}^{d}$ and a point $x\in\mathbb{R}^{d}$, we define by
$d(x,Q):=\inf_{y\in Q}\|x-y\|$ the distance function from $x$ to $Q$, and
define the indicator function of $Q$ by

$\displaystyle\delta_{Q}(x):=\left\\{\begin{array}[]{lll}0,&\textrm{if}~{}~{}x\in
Q;\\\ +\infty,&\textrm{otherwise}.\end{array}\right.$

###  2.1 Different classes of functions

In order to introduce the class of smooth convex functions, we first give the
definitions of convexity and smoothness. There are several equivalent
definitions of convexity; here we present the first-order definition of
convexity in the following form:

$(\forall x,y\in\mathbb{R}^{n}):\quad f(y)\geq f(x)+\left\langle\nabla
f(x),y-x\right\rangle.$ (2.2)

The convexity of $f$ essentially says that the function $f$ can be lower
bounded by a linear function; In contrast, the smoothness of $f$ actually says
that the function $f$ can be upper bounded by a quadratic function, that is

$(\forall x,y\in\mathbb{R}^{n}):\quad f(y)\leq f(x)+\left\langle\nabla
f(x),y-x\right\rangle+\frac{L}{2}\|y-x\|^{2},$ (2.3)

where $L>0$ is a constant. A function is called smooth convex if the
inequalities (2.2) and (2.3) hold at the same time; the class of smooth convex
functions is denoted by $\mathcal{F}^{1,1}_{L}(\mathbb{R}^{n})$. Surprisingly,
the convexity inequality (2.2) and the smoothness inequality (2.3) can be
equivalently characterized by a single inequality, that is

$(\forall x,y\in\mathbb{R}^{n}):\quad f(y)\geq f(x)+\left\langle\nabla
f(x),y-x\right\rangle+\frac{1}{L}\|\nabla f(x)-\nabla f(y)\|^{2},$ (2.4)

from which the convexity is obviously implied. Interestingly, the inequality
(2.4) is also equivalent to the cocoercive property of gradient, formulated as

$(\forall x,y\in\mathbb{R}^{n}):\quad\left\langle\nabla f(x)-\nabla
f(y),x-y\right\rangle\geq\frac{1}{2L}\|\nabla f(x)-\nabla f(y)\|^{2}.$ (2.5)

The fact of equivalence between the inequalities above was observed in the
book [4]. In order to describe a more general fact, we introduce the first-
order definition of strong convexity in the form

$(\forall x,y\in\mathbb{R}^{n}):\quad f(y)\geq f(x)+\left\langle\nabla
f(x),y-x\right\rangle+\frac{\mu}{2}\|y-x\|^{2},$ (2.6)

where $\mu\geq 0$ is a constant, called modulus of strong convexity. In
particular, for $\mu=0$ the strong convexity reduces to convexity. In this
sense, strong convexity with constant $\mu$ is more general than convexity and
hence a wider class of functions, denoted by
$\mathcal{S}^{1,1}_{\mu,L}(\mathbb{R}^{n})$ and called $L$-smooth and
$\mu$-strongly convex, follows. As a matter of fact, we have

$\mathcal{S}^{1,1}_{\mu=0,L}(\mathbb{R}^{n})=\mathcal{F}^{1,1}_{L}(\mathbb{R}^{n}).$

Now, the following statement extends the basic fact that convexity and
smoothness is equivalent to (2.4) or (2.5); for more details please refer to
[9].

######  Fact 2.1.

Let $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$ be a given real-valued function.
Then, $f\in\mathcal{S}^{1,1}_{\mu,L}(\mathbb{R}^{n})$ if and only if one of
the following inequalities holds:

$(\forall x,y\in\mathbb{R}^{n}):\quad\left\langle\nabla f(x)-\nabla
f(y),x-y\right\rangle\geq\frac{\mu
L}{\mu+L}\|x-y\|^{2}+\frac{1}{\mu+L}\|\nabla f(x)-\nabla f(y)\|^{2},$ (2.7)
$\displaystyle(\forall x,y\in\mathbb{R}^{n}):\quad f(x)\geq$ $\displaystyle
f(y)+\left\langle\nabla f(y),x-y\right\rangle+\frac{1}{2L}\|\nabla f(x)-\nabla
f(y)\|^{2}$ (2.8) $\displaystyle+\frac{\mu
L}{2(L-\mu)}\|x-y-\frac{1}{L}(\nabla f(x)-\nabla f(y))\|^{2},$

and

$\mu\|x-y\|\leq\|\nabla f(x)-\nabla f(y)\|\leq L\|x-y\|.$ (2.9)

At last, we let $\Gamma_{0}(\mathbb{R}^{n})$ be the class of proper closed and
convex functions from $\mathbb{R}^{n}$ to $(-\infty,+\infty]$. For any
$g\in\Gamma_{0}(\mathbb{R}^{n})$, its subdifferential at $x$ is given by

$\partial g(x):=\\{y\in\mathbb{R}^{n}:g(u)\geq g(x)+\langle
y,u-x\rangle,\quad\forall u\in\mathbb{R}^{n}\\}.$

The inequality $g(u)\geq g(x)+\langle y,u-x\rangle$ is called subgradient
inequality, each vector in $\partial g(x)$ is called a subgradient of $g$ at
$x$.

###  2.2 The proximal gradient method

The proximal gradient method, also called the forward-backward splitting
method, is a well-known method for minimizing the sum of a smooth function and
a non-smooth function. In the paper, we will be concerned with the following
composite optimization

$\min_{x\in\mathbb{R}^{n}}\varphi(x):=f(x)+g(x),$ (2.10)

where we assume the following.

######  Assumption 2.1 (Composite model assumption).

The component functions $f$ and $g$ satisfy that

  1. (A)

$f\in\mathcal{S}^{1,1}_{\mu,L}(\mathbb{R}^{n})$, i.e., $f$ is a $L$-smooth and
$\mu$-strongly convex function,

  2. (B)

$g\in\Gamma_{0}(\mathbb{R}^{n})$, i.e., $g$ is a proper closed convex function
but it is possibly not smooth, and

  3. (C)

$X^{*}$, the set of optimal solutions to (2.10), is nonempty. The optimal
value of the problem is denoted by $\bar{\varphi}$.

Before introducing the concrete iterative scheme of the proximal gradient
method, we first give the definition of proximal gradient mapping.

######  Definition 2.1 (PG mapping).

Suppose that $f$ and $g$ satisfy properties (A) and (B) of Assumption 2.1.
Then the proximal gradient mapping is the operator
$\mathcal{G}:\mathbb{R}^{n}\times\mathbb{R}_{+}\rightarrow\mathbb{R}^{n}$
defined by

$\mathcal{G}(x,t):=t^{-1}\left(x-{\mathbf{prox}}_{tg}(x-t\nabla f(x))\right),$
(2.11)

where ${\mathbf{prox}}_{tg}:\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$ is the
proximal mapping given by

${\mathbf{prox}}_{tg}(x):=\arg\min_{y\in\mathbb{R}^{n}}\\{g(y)+\frac{1}{2t}\|y-x\|^{2}\\}.$

In particular, when $g=\delta_{Q}$, the proximal gradient mapping reduces to
the gradient mapping in [4].

Now, the proximal gradient method, originally given by

$x^{k+1}={\mathbf{prox}}_{t_{k}g}\left(x^{k}-t_{k}\cdot\nabla
f(x^{k})\right),$

can be equivalently written into the following form

$x^{k+1}=x^{k}-t_{k}\cdot\mathcal{G}(x^{k},t_{k}).$ (2.12)

###  2.3 The potential function-based framework

The authors of [2] introduced a novel potential function-based framework to
study the convergence of standard gradient-type methods for making the
gradients small in smooth convex optimization. In this part, we first review
how their method applies to the standard gradient descent for minimizing a
smooth convex function $f\in\mathcal{F}^{1,1}_{L}(\mathbb{R}^{n})$. The key
ingredient is that they constructed a potential function of the form

${\mathcal{C}}_{k}=\frac{k}{L}\|\nabla f(x^{k})\|^{2}+f(x^{k}),$

where the sequence $\\{x^{k}\\}_{k\geq 0}$ is generated by the standard
gradient descent method, i.e.,

$x^{k+1}=x^{k}-\frac{1}{L}\nabla f(x^{k}),~{}~{}\forall k\geq 0.$

By invoking the inequalities (2.4) or (2.5), they can show that the sequence
$\\{{\mathcal{C}}_{k}\\}_{k\geq 0}$ is nonincreasing with $k$ and hence can
conclude that $\forall k\geq 0$

$\|\nabla f(x^{k})\|^{2}\leq\frac{2L(f(x^{0})-f(x^{*}))}{2k+1},$

where $x^{0}$ is an arbitrary initial point and $x^{*}$ is a minimizer of $f$.
In order to design a faster method than the standard gradient descent, they
considered a different potential function of the form

${\mathcal{C}}_{k}=\sum_{i=0}^{k-1}a_{i}\|\nabla
f(x^{i})\|^{2}+B_{k}(f(x^{k})-f(x^{*})),$ (2.13)

where $a_{i}>0$ ($\forall i\geq 0$) the sequence of scalars $B_{k}>0$
($\forall k\geq 0$) is strictly increasing, and the sequence
$\\{x^{k}\\}_{k\geq 0}$ is generated by the following fast gradient method

$\left\\{\begin{aligned} v^{k}:=&v^{k-1}-\frac{b_{k-1}}{L}\cdot\nabla
f(x^{k-1}),\\\
x^{k}:=&\frac{B_{k-1}}{B_{k}}\left(x^{k-1}-\frac{1}{L}\cdot\nabla
f(x^{k-1})\right)+\frac{b_{k}}{B_{k}}v^{k},\end{aligned}\right.$ (FGM)

with a given arbitrary initial point $x^{0}$ and $v^{0}=x^{0}$. Under some
restrictions on the parameters $a_{i}$ and $B_{k}$, invoking again the
inequalities (2.4) and (2.5) they showed that

${\mathcal{C}}_{k+1}-{\mathcal{C}}_{k}\leq\frac{L}{2}(\|x^{*}-v^{k}\|^{2}-\|x^{*}-v^{k+1}\|^{2}),\forall
k\geq 0,$

from which both convergences in function value and in norm of gradient can be
obtained. As pointed out, their analysis is the first one that simultaneously
leads to both convergence guarantees.

##  3 New properties on proximal gradient mapping

In this section, we first introduce three basic properties of proximal
gradient mapping, whose proofs are postponed to Appendix. Then, we highlight
two new properties, both of which were discovered in [10] by the second author
of this paper and posted on arXiv three years ago but they have not yet been
submitted for publication.

###  3.1 Basic lemmas

The first lemma is an equivalent characterization of the proximal mapping.

######  Lemma 3.1.

Let $g\in\Gamma_{0}(\mathbb{R}^{n})$ and $t>0$. Thus
$z={\mathbf{prox}}_{tg}(y)$ if and only if $y\in(I+t\cdot\partial g)(z)$.

The second lemma provides the relationship between the norm of proximal
gradient mapping and the smallest norm of subgradient.

######  Lemma 3.2.

Suppose that $f$ and $g$ satisfy properties (A) and (B) of Assumption 2.1. For
any $x\in\mathbb{R}^{n}$ and $t>0$, we have

$\|\mathcal{G}(x,t)\|\leq d(0,\partial\varphi(x)).$ (3.1)

The last lemma is a slight modification of the classic descent lemma,
originally discovered by Beck and Teboulle in [1]. It also extends Corollary
2.3.2 in [4] from gradient mapping to proximal gradient mapping. When $\mu=0$,
it reduces to the pivotal inequality in the recent work [3].

######  Lemma 3.3.

Suppose that $f$ and $g$ satisfy properties (A) and (B) of Assumption 2.1.
Then, we have

$\varphi(x)-\varphi(y-t\mathcal{G}(y,t))\geq
t(1-\frac{L}{2}t)\|\mathcal{G}(y,t)\|^{2}+\left\langle\mathcal{G}(y,t),x-y\right\rangle+\frac{\mu}{2}\|x-y\|^{2}.$
(3.2)

In particular, the inequality above with $t=\frac{1}{L}$ and $\mu=0$ in (3.2)
yields

$\varphi(x)-\varphi(y-\frac{1}{L}\mathcal{G}(y,\frac{1}{L}))\geq\frac{1}{2L}\|\mathcal{G}(y,\frac{1}{L})\|^{2}+\left\langle\mathcal{G}(y,\frac{1}{L}),x-y\right\rangle.$
(3.3)

###  3.2 New and refined results

For simplicity, we define the updated iterate point by using the superscript
”+” as follows:

$\quad x^{+}:={\mathbf{prox}}_{tg}(x-t\nabla
f(x))=x-t\cdot\mathcal{G}_{t}(x),$

where the step size $t>0$ is clear from the context. Using this notation and
Lemma 3.1, we immediately have

$x-t\nabla f(x)\in x^{+}+t\partial g(x^{+}).$

Thus, there must exist a subgradient $s^{+}\in\partial g(x^{+})$ such that

$x^{+}=x-t(\nabla f(x)+s^{+}).$ (3.4)

Now, we are ready to present the first new property of proximal gradient
mapping.

######  Theorem 3.1 (Norm monotonicity).

Suppose that $f$ and $g$ satisfy properties (A) and (B) of Assumption 2.1.
Denote $\rho(t):=\max\\{|1-Lt|,|1-\mu t|\\}$. Then, we have

$\|\mathcal{G}(x^{+},t)\|\leq
d(0,\partial\varphi(x^{+}))\leq\rho(t)\|\mathcal{G}(x,t)\|\leq\rho(t)d(0,\partial\varphi(x)).$
(3.5)

In particular, for $f\in\mathcal{F}^{1,1}_{L}(\mathbb{R}^{n})$,
$g\in\Gamma_{0}(\mathbb{R}^{n})$, and $0<t\leq\frac{2}{L}$, it holds that

$\|\mathcal{G}(x^{+},t)\|\leq
d(0,\partial\varphi(x^{+}))\leq\|\mathcal{G}(x,t)\|\leq
d(0,\partial\varphi(x)).$

###### Proof.

The inequalities $\|\mathcal{G}(x^{+},t)\|\leq d(0,\partial\varphi(x^{+}))$
and $\rho(t)\|\mathcal{G}(x,t)\|\leq\rho(t)d(0,\partial\varphi(x))$ directly
follow from Lemma 3.2. To show the relationship (3.5), it suffices to show
that

$d(0,\partial\varphi(x^{+}))\leq\rho(t)\|\mathcal{G}(x,t)\|.$ (3.6)

Since $s^{+}\in\partial g(x^{+})$, we have
$d(0,\partial\varphi(x^{+}))\leq\|\nabla f(x^{+})+s^{+}\|$. Therefore, if we
can show that

$\|\nabla f(x^{+})+s^{+}\|^{2}\leq\rho^{2}(t)\|\mathcal{G}(x,t)\|^{2},$ (3.7)

then the desired inequality (3.6) follows immediately. Using he expression
$x^{+}=x-t(\nabla f(x)+s^{+})$ in (3.4), we derive that

$\displaystyle\|\nabla f(x^{+})+s^{+}\|^{2}$ $\displaystyle=$
$\displaystyle\|\nabla f(x)+s^{+}+\nabla f(x^{+})-\nabla f(x)\|^{2}$
$\displaystyle=$ $\displaystyle\|\nabla f(x)+s^{+}\|^{2}+2\left\langle\nabla
f(x)+s^{+},\nabla f(x^{+})-\nabla f(x)\right\rangle+\|\nabla f(x^{+})-\nabla
f(x)\|^{2}$ $\displaystyle=$
$\displaystyle\frac{1}{t^{2}}\|x^{+}-x\|^{2}-\frac{2}{t}\left\langle
x^{+}-x,\nabla f(x^{+})-\nabla f(x)\right\rangle+\|\nabla f(x^{+})-\nabla
f(x)\|^{2}$ $\displaystyle\leq$
$\displaystyle\frac{1}{t^{2}}\|x^{+}-x\|^{2}-\frac{2}{t}\left(\frac{\mu
L}{\mu+L}\|x^{+}-x\|^{2}+\frac{1}{\mu+L}\|\nabla f(x^{+})-\nabla
f(x)\|^{2}\right)+\|\nabla f(x^{+})-\nabla f(x)\|^{2}$ $\displaystyle=$
$\displaystyle\frac{1}{t^{2}}\left[(1-\frac{2t\mu
L}{\mu+L})\|x^{+}-x\|^{2}+t(t-\frac{2}{\mu+L})\|\nabla f(x^{+})-\nabla
f(x)\|^{2}\right],$

where the inequality follows from (2.7) in Fact 2.1. In order to bound
$\|\nabla f(x^{+})-\nabla f(x)\|^{2}$ in terms of $\|x^{+}-x\|^{2}$, we use
(2.9) in Fact 2.1 to get

$\mu^{2}\|x^{+}-x\|^{2}\leq\|\nabla f(x^{+})-\nabla f(x)\|^{2}\leq
L^{2}\|x^{+}-x\|^{2}.$

If $t-\frac{2}{\mu+L}\geq 0$, then we have

$(t-\frac{2}{\mu+L})\|\nabla f(x^{+})-\nabla f(x)\|^{2}\leq
L^{2}(t-\frac{2}{\mu+L})\|x^{+}-x\|^{2}.$

If $t-\frac{2}{\mu+L}<0$, then we have

$(t-\frac{2}{\mu+L})\|\nabla f(x^{+})-\nabla
f(x)\|^{2}\leq\mu^{2}(t-\frac{2}{\mu+L})\|x^{+}-x\|^{2}.$

In both cases, we always have that

$(t-\frac{2}{\mu+L})\|\nabla f(x^{+})-\nabla
f(x)\|^{2}\leq\max\left\\{L^{2}(t-\frac{2}{\mu+L}),\mu^{2}(t-\frac{2}{\mu+L})\right\\}\|x^{+}-x\|^{2}.$

Therefore, we can continue to derive that

$\displaystyle\|\nabla f(x^{+})+s^{+}\|^{2}$ $\displaystyle\leq$
$\displaystyle\frac{1}{t^{2}}\left[(1-\frac{2t\mu
L}{\mu+L})\|x^{+}-x\|^{2}+t\max\left\\{L^{2}(t-\frac{2}{\mu+L}),\mu^{2}(t-\frac{2}{\mu+L})\right\\}\|x^{+}-x\|^{2}\right]$
$\displaystyle=$ $\displaystyle\frac{1}{t^{2}}\max\left\\{1-\frac{2t\mu
L}{\mu+L}+tL^{2}(t-\frac{2}{\mu+L}),1-\frac{2t\mu
L}{\mu+L}+t\mu^{2}(t-\frac{2}{\mu+L})\right\\}\|x^{+}-x\|^{2}$
$\displaystyle=$ $\displaystyle\frac{1}{t^{2}}\max\\{(1-Lt)^{2},(1-\mu
t)^{2}\\}\|x^{+}-x\|^{2}$ $\displaystyle=$
$\displaystyle\rho^{2}(t)\|\mathcal{G}(x,t)\|^{2},$

from which the inequality (3.7) follows. This completes the proof. ∎

######  Remark 3.1.

Here, the factor $\rho(t)$ is optimal; otherwise, it will contradict the
following exact worst-case convergence rate, which was recently established in
[7]:

$\|\nabla f(x^{+})+s^{+}\|\leq\rho(t)\|\nabla f(x)+s\|,~{}~{}\forall
s\in\partial g(x).$

In fact, the inequality above is equivalent to

$\|\nabla f(x^{+})+s^{+}\|\leq\rho(t)d(0,\partial\varphi(x));$

whilst in our proof, we have shown $\|\nabla
f(x^{+})+s^{+}\|\leq\rho(t)\|\mathcal{G}(x,t)\|$ in (3.7) which is a tighter
estimation and hence it is impossible to improve.

Below, we state the second new property of proximal gradient mapping.

######  Theorem 3.2 (Refined descent).

Suppose that $f$ and $g$ satisfy properties (A) and (B) of Assumption 2.1.
Then, we have

$\varphi(x)\geq\varphi(x^{+})+\frac{t}{2}\|\mathcal{G}(x,t)\|^{2}+\frac{t}{2(1-\mu
t)}\|\mathcal{G}(x^{+},t)\|^{2},0<t\leq\frac{1}{L}.$ (3.8)

In particular,

  * •

for $f\in\mathcal{F}^{1,1}_{L}(\mathbb{R}^{n})$,
$g\in\Gamma_{0}(\mathbb{R}^{n})$, it holds that

$\varphi(x)\geq\varphi(x^{+})+\frac{t}{2}\|\mathcal{G}(x,t)\|^{2}+\frac{t}{2}\|\mathcal{G}(x^{+},t)\|^{2},0<t\leq\frac{1}{L}.$
(3.9)

  * •

for $f\in\mathcal{F}^{1,1}_{L}(\mathbb{R}^{n})$, $g\equiv 0$, it holds that

$f(x)\geq f(x^{+})+\frac{t}{2}\|\nabla f(x)\|^{2}+\frac{t}{2}\|\nabla
f(x^{+})\|^{2},0<t\leq\frac{1}{L}.$ (3.10)

###### Proof.

Note that $0<t\leq L^{-1}$ implies $t^{-1}\geq L$ which further implies that
the $L$-smooth function must also be $t^{-1}$-smooth; hence, we can conclude
that

${\mathcal{S}}^{1,1}_{\mu,L}(\mathbb{R}^{n})\subset{\mathcal{S}}^{1,1}_{\mu,t^{-1}}(\mathbb{R}^{n}).$

We now use (2.8) in Fact 2.1 with $L=t^{-1}$ and $y=x^{+}$ to get

$f(x)\geq f(x^{+})+\left\langle\nabla
f(x^{+}),x-x^{+}\right\rangle+\frac{t}{2}\|\nabla f(x)-\nabla
f(x^{+})\|^{2}+\frac{\mu}{2(1-\mu t)}\|x-x^{+}-t(\nabla f(x)-\nabla
f(x^{+}))\|^{2}.$

The subgradient inequality of $g$ gives $g(x)\geq g(x^{+})+\left\langle
s^{+},x-x^{+}\right\rangle$ since $s^{+}\in\partial g(x^{+})$. Adding up these
two inequalities, we derive that

$\displaystyle\varphi(x)\geq$ $\displaystyle\varphi(x^{+})+\left\langle\nabla
f(x^{+})+s^{+},x-x^{+}\right\rangle+\frac{t}{2}\|\nabla f(x)-\nabla
f(x^{+})\|^{2}$ $\displaystyle+\frac{\mu}{2(1-\mu t)}\|x-x^{+}-t(\nabla
f(x)-\nabla f(x^{+}))\|^{2}$ $\displaystyle=$
$\displaystyle\varphi(x^{+})+\left\langle\nabla
f(x)+s^{+},x-x^{+}\right\rangle-\left\langle\nabla f(x^{+})-\nabla
f(x),x^{+}-x\right\rangle$ $\displaystyle+\frac{t}{2}\|\nabla f(x)-\nabla
f(x^{+})\|^{2}+\frac{\mu}{2(1-\mu t)}\|x-x^{+}-t(\nabla f(x)-\nabla
f(x^{+}))\|^{2}$

Using the expression $x^{+}=x-t(\nabla f(x)+s^{+})$ in (3.4), we can further
derive that

$\displaystyle\varphi(x)\geq$
$\displaystyle\varphi(x^{+})+\frac{1}{t}\|x-x^{+}\|^{2}-\left\langle\nabla
f(x^{+})-\nabla f(x),x^{+}-x\right\rangle$ $\displaystyle+\frac{t}{2}\|\nabla
f(x)-\nabla f(x^{+})\|^{2}+\frac{\mu t^{2}}{2(1-\mu t)}\|s^{+}+\nabla
f(x^{+})\|^{2}$ $\displaystyle=$
$\displaystyle\varphi(x^{+})+\frac{1}{2t}\|t(\nabla f(x^{+})-\nabla
f(x))-x^{+}+x\|^{2}$ $\displaystyle+\frac{1}{2t}\|x-x^{+}\|^{2}+\frac{\mu
t^{2}}{2(1-\mu t)}\|s^{+}+\nabla f(x^{+})\|^{2}$ $\displaystyle=$
$\displaystyle\varphi(x^{+})+\frac{1}{2t}\|x-x^{+}\|^{2}+\frac{t}{2(1-\mu
t)}\|s^{+}+\nabla f(x^{+})\|^{2}.$

Note that $x-x^{+}=t\mathcal{G}(x,t)$ and use the fact that

$\|s^{+}+\nabla f(x^{+})\|\geq
d(0,\partial\varphi(x^{+}))\geq\|\mathcal{G}(x^{+},t)\|.$

We finally obtain

$\varphi(x)\geq\varphi(x^{+})+\frac{t}{2}\|\mathcal{G}(x,t)\|^{2}+\frac{t}{2(1-\mu
t)}\|\mathcal{G}(x^{+},t)\|^{2}.$

This completes the proof. ∎

######  Remark 3.2.

We make a few remarks:

  * •

In [4], for $\varphi=f+g$ with
$f\in{\mathcal{S}}^{1,1}_{\mu,L}(\mathbb{R}^{n})$ and $g$ being the indicator
function of a set $Q$, the descent lemma of the projected gradient method can
be stated as

$\varphi(x)\geq\varphi(x^{+})+\frac{t}{2}\|g_{Q}(x,t)\|^{2},0<t\leq\frac{1}{L}.$
(3.11)

where $g_{Q}(x,t):=t^{-1}(x-x^{+})$ is the gradient mapping of $f$ on $Q$. In
[1], for $\varphi=f+g$ with $f\in\mathcal{F}^{1,1}_{L}(\mathbb{R}^{n})$ and
$g\in\Gamma_{0}(\mathbb{R}^{n})$, the corresponding descent lemma of the
proximal gradient method is

$\varphi(x)\geq\varphi(x^{+})+\frac{L}{2}\|x^{+}-x\|^{2}.$ (3.12)

It is not hard to see that our result improves these existing descent lemmas.

  * •

At the time of this paper was under preparation, we noticed that the special
case (3.9) was implicitly rediscovered by combining Lemma 9 and Lemma 11 in
[8].

##  4 Small norm of proximal gradient mapping

In this section, we aim to extend the potential function-based framework
previously reviewed from gradient descent to proximal gradient descent and its
acceleration.

###  4.1 Proximal gradient descent

The following result is a direct extension of Lemma 2.1 in [2]. However, its
proof relies on the new properties of proximal gradient mapping in the last
section.

######  Theorem 4.1.

Suppose that Assumption 2.1 holds. Let $x^{0}$ be an arbitrary initial point
and assume that $x^{k+1}=x^{k}-t_{k}\mathcal{G}(x^{k},t_{k})$ with constant
step sizes $t_{k}\equiv\frac{\eta}{L}$ for some $0<\eta\leq 1$. Then

$\mathcal{C}_{k}:=\frac{\eta}{L}\cdot
k\|\mathcal{G}(x^{k},\frac{\eta}{L})\|^{2}+\varphi(x^{k})-\bar{\varphi}$

is nonincreasing with $k$, and the norm sequence of proximal gradient mappings
converges sublinearly in the sense that $\forall k\geq 0$

$\|\mathcal{G}(x^{k},\frac{\eta}{L})\|\leq\frac{L(\varphi(x^{0})-\bar{\varphi})}{\eta
k}.$

###### Proof.

We first show that $\forall k\geq 0$,

$\mathcal{C}_{k+1}\leq\mathcal{C}_{k}.$

Using the definition of $\mathcal{C}_{k}$, we have that

$\mathcal{C}_{k+1}-\mathcal{C}_{k}=\frac{\eta}{L}(k+1)\|\mathcal{G}(x^{k+1},\frac{\eta}{L})\|^{2}-\frac{\eta
k}{L}\|\mathcal{G}(x^{k},\frac{\eta}{L})\|^{2}+\varphi(x^{k+1})-\varphi(x^{k}).$

Using Theorem 3.2 yields

$\varphi(x^{k})-\varphi(x^{k+1})\geq\frac{\eta}{2L}\|\mathcal{G}(x^{k},\frac{\eta}{L})\|^{2}+\frac{\eta}{2L}\|\mathcal{G}(x^{k+1},\frac{\eta}{L})\|^{2}.$

Thus,

$\mathcal{C}_{k+1}-\mathcal{C}_{k}\leq\frac{\eta}{L}\left(k+\frac{1}{2}\right)(\|\mathcal{G}(x^{k+1},\frac{\eta}{L})\|^{2}-\|\mathcal{G}(x^{k},\frac{\eta}{L})\|^{2}).$

In addition, using Theorem 3.1 yields

$\|\mathcal{G}(x^{k+1},\frac{\eta}{L})\|\leq\|\mathcal{G}(x^{k},\frac{\eta}{L})\|,$

which leads to the monotonically decreasing
$\mathcal{C}_{k+1}\leq\mathcal{C}_{k}$ and the result

$\varphi(x^{k})-\bar{\varphi}+\frac{\eta
k}{L}\cdot\|\mathcal{G}(x^{k},\frac{\eta}{L})\|^{2}\leq\cdots\leq\mathcal{C}_{0}=\varphi(x^{0})-\bar{\varphi}.$

Equivalently,

$\frac{\eta
k}{L}\|\mathcal{G}(x^{k},\frac{\eta}{L})\|^{2}\leq\varphi(x^{0})-\varphi(x^{k})\leq\varphi(x^{0})-\bar{\varphi},$

from which the conclusion follows. ∎

###  4.2 Accelerated norm minimization

We start with the following iterative scheme which is obtained by replacing
the gradient in the fast gradient method (FGM) by the proximal gradient
mapping and introducing a new sequence $\\{y^{k}\\}$. For any $k\geq 1$,

$\left\\{\begin{aligned}
&y^{k-1}:=x^{k-1}-\frac{1}{L}\cdot\mathcal{G}(x^{k-1},\frac{1}{L}),\\\
&v^{k}:=v^{k-1}-\frac{b_{k-1}}{L}\cdot\mathcal{G}(x^{k-1},\frac{1}{L}),\\\
&x^{k}:=\frac{B_{k-1}}{B_{k}}y^{k-1}+\frac{b_{k}}{B_{k}}v^{k},\end{aligned}\right.$
(APG)

where the sequence of scalars $B_{k}>0$ will be determined later and the
sequence of scalars $b_{k}$ is defined by $b_{0}=B_{0}$ and
$b_{k}=B_{k}-B_{k-1}$ for $k\geq 1$. For simplicity, we let
$\mathcal{G}(x^{k})\equiv\mathcal{G}(x^{k},\frac{1}{L})$ be the proximal
gradient mapping when the step size $t$ equals to $\frac{1}{L}$. Our
forthcoming analysis mainly relies on the following potential function: for
any $k\geq 0$

$\mathcal{C}_{k}:=\sum\limits^{k}_{i=0}a_{i}\|\mathcal{G}(x^{i})\|^{2}+B_{k}(\varphi(y^{k})-\bar{\varphi}),$
(4.1)

which is inspired by the potential function (2.13). However, when zooming into
the expression more carefully, the reader can find that it is not obtained by
simply replacing the gradient in (2.13) by the proximal gradient mapping.
Actually, we use the function value at $y^{k}$ rather than at $x^{k}$ and the
sum is from $i=0$ to $k$ rather than to $k-1$. These modifications are pivotal
to deduce our desired conclusions.

######  Lemma 4.1.

Suppose that Assumption 2.1 holds. Let $x^{0}$ be an arbitrary initial point
with $v^{0}=x^{0}$ and assume that the sequences of $\\{x^{k}\\}$,
$\\{y^{k}\\}$, and $\\{v^{k}\\}$ are generated by the algorithm (APG). If the
nonnegative scalars $a_{k},b_{k},B_{k}$ satisfy that $\forall k\geq 1$,

$a_{k}\leq\frac{B_{k}-b_{k}^{2}}{2L},$

then we have

$\mathcal{C}_{k}-\mathcal{C}_{k-1}\leq\frac{L}{2}(\|x^{*}-v^{k}\|^{2}-\|x^{*}-v^{k+1}\|^{2}),\forall
k\geq 1,$

where $x^{*}\in X^{*}$.

###### Proof.

Using the definition of $\mathcal{C}_{k}$ in (4.1), we have that for any
$k\geq 1$,

$\mathcal{C}_{k}-\mathcal{C}_{k-1}\leq
a_{k}\|\mathcal{G}(x^{k})\|^{2}+B_{k}\varphi(y^{k})-B_{k-1}\varphi(y^{k-1})-b_{k}\bar{\varphi}.$
(4.2)

Now, we use (3.3) in Lemma 3.3 to bound the unknown optimal function value
$\bar{\varphi}$. Actually, the inequality (3.3) with $x=x^{*}$ and $y=x^{k}$
gives us

$\bar{\varphi}=\varphi(x^{*})\geq\varphi(y^{k})+\frac{1}{2L}\|\mathcal{G}(x^{k})\|^{2}+\left\langle\mathcal{G},x^{*}-x^{k}\right\rangle.$
(4.3)

Using (3.3) again with $x=y^{k-1}$ and $y=x^{k}$ leads to

$\varphi(y^{k-1})-\varphi(y^{k})\geq\frac{1}{2L}\|\mathcal{G}(x^{k})\|^{2}+\left\langle\mathcal{G}(x^{k}),y^{k-1}-x^{k}\right\rangle.$
(4.4)

Combining the three inequalities above, we derive that

$\displaystyle\mathcal{C}_{k}-\mathcal{C}_{k-1}\leq$ $\displaystyle
a_{k}\|\mathcal{G}(x^{k})\|^{2}+B_{k}\varphi(y^{k})-B_{k-1}\varphi(y^{k-1})-b_{k}\varphi(y^{k})-\frac{b_{k}}{2L}\|\mathcal{G}(x^{k})\|^{2}$
(4.5) $\displaystyle-
b_{k}\left\langle\mathcal{G}(x^{k}),x^{*}-x^{k}\right\rangle$ $\displaystyle=$
$\displaystyle
a_{k}\|\mathcal{G}(x^{k})\|^{2}+B_{k-1}(\varphi(y^{k})-\varphi(y^{k-1}))-\frac{b_{k}}{2L}\|\mathcal{G}(x^{k})\|^{2}$
$\displaystyle-b_{k}\left\langle\mathcal{G}(x^{k}),x^{*}-x^{k}\right\rangle$
$\displaystyle\leq$ $\displaystyle
a_{k}\|\mathcal{G}(x^{k})\|^{2}-\frac{B_{k-1}}{2L}\|\mathcal{G}(x^{k})\|^{2}-B_{k-1}\left\langle\mathcal{G}(x^{k}),y^{k-1}-x^{k}\right\rangle-\frac{b_{k}}{2L}\|\mathcal{G}(x^{k})\|^{2}$
$\displaystyle+b_{k}\left\langle\mathcal{G}(x^{k}),x^{k}-x^{*}\right\rangle$
$\displaystyle=$
$\displaystyle\left(a_{k}-\frac{B_{k}}{2L}\right)\|\mathcal{G}(x^{k})\|^{2}+B_{k-1}\left\langle\mathcal{G}(x^{k}),x^{k}-x^{k-1}+\frac{1}{L}\mathcal{G}(x^{k-1})\right\rangle$
$\displaystyle+b_{k}\left\langle\mathcal{G}(x^{k}),x^{k}-x^{*}\right\rangle.$

In order to get an acceptable upper bound of
$\mathcal{C}_{k}-\mathcal{C}_{k-1}$, we need to estimate the inner product
term $\left\langle\mathcal{G}(x^{k}),x^{k}-x^{*}\right\rangle$. This can be
done by going through the following arguments which are standard in mirror-
descent-type analysis. First, note that

$\displaystyle v^{k+1}$
$\displaystyle=\arg\min\limits_{u}\left\\{b_{k}\left\langle\mathcal{G}(x^{k}),u-v^{k}\right\rangle+\frac{L}{2}\|u-v^{k}\|^{2}\right\\}$
$\displaystyle=v^{k}-\frac{b_{k}}{L}\mathcal{G}(x^{k}).$

Then, we can deduce that

$\displaystyle b_{k}\left\langle\mathcal{G}(x^{k}),x^{k}-x^{*}\right\rangle=$
$\displaystyle
b_{k}\left\langle\mathcal{G}(x^{k}),x^{k}-v^{k+1}\right\rangle+L\left\langle
v^{k}-v^{k+1},v^{k+1}-x^{*}\right\rangle$ (4.6) $\displaystyle=$
$\displaystyle
b_{k}\left\langle\mathcal{G}(x^{k}),x^{k}-v^{k}\right\rangle+\frac{b_{k}^{2}}{L}\|\mathcal{G}(x^{k})\|^{2}+\frac{L}{2}\|x^{*}-v^{k}\|^{2}$
$\displaystyle-\frac{L}{2}\|x^{*}-v^{k+1}\|^{2}-\frac{L}{2}\|v^{k+1}-v^{k}\|^{2}$
$\displaystyle=$ $\displaystyle
b_{k}\left\langle\mathcal{G}(x^{k}),x^{k}-v^{k}\right\rangle+\frac{b_{k}^{2}}{2L}\|\mathcal{G}(x^{k})\|^{2}$
$\displaystyle+\frac{L}{2}\|x^{*}-v^{k}\|^{2}-\frac{L}{2}\|x^{*}-v^{k+1}\|^{2},$

where the relationship
$v^{k+1}:=v^{k}-\frac{b_{k}}{L}\cdot\mathcal{G}(x^{k},\frac{1}{L})$ have been
repeatedly used. Now, combining (4.6) and (4.5), we can get

$\displaystyle\mathcal{C}_{k}-\mathcal{C}_{k-1}\leq$
$\displaystyle\left(a_{k}-\frac{B_{k}-b_{k}^{2}}{2L}\right)\|\mathcal{G}(x^{k})\|^{2}+\frac{L}{2}\|x^{*}-v^{k}\|^{2}-\frac{L}{2}\|x^{*}-v^{k-1}\|^{2}$
(4.7)
$\displaystyle+\left\langle\mathcal{G}(x^{k}),B_{k}x^{k}-B_{k-1}(x^{k-1}-\frac{1}{L}\mathcal{G}(x^{k-1}))-b_{k}v^{k}\right\rangle.$

Note that

$B_{k}x^{k}-B_{k-1}\left(x^{k-1}-\frac{1}{L}\mathcal{G}(x^{k-1})\right)-b_{k}v^{k}=B_{k}x^{k}-B_{k-1}y^{k-1}-b_{k}v^{k}=0.$

The inner product term (4.7) disappears and hence using the condition
$a_{k}\leq\frac{B_{k}-b_{k}^{2}}{2L}$ we finally obtain

$\mathcal{C}_{k}-\mathcal{C}_{k-1}\leq\frac{L}{2}\|x^{*}-v^{k}\|^{2}-\frac{L}{2}\|x^{*}-v^{k+1}\|^{2}.$

This completes the proof. ∎

Now, we are ready to present the accelerated convergence of proximal gradient
mapping.

######  Theorem 4.2.

Suppose that the assumption in lemma 4.1 holds. Denote

$\tilde{\mathcal{C}}:=a_{0}\|\mathcal{G}(x^{0})\|^{2}+b_{0}(\varphi(y^{0})-\bar{\varphi})+\frac{L}{2}\|x^{*}-v^{0}\|^{2}.$

Then, we have

$\varphi(y^{k})-\bar{\varphi}\leq\frac{\tilde{\mathcal{C}}}{B_{k}},k\geq 1,$
(4.8)
$\sum\limits^{k}_{i=0}a_{i}\|\mathcal{G}(x^{i})\|^{2}\leq\tilde{\mathcal{C}},k\geq
1.$ (4.9)

In particular, if $b_{k}=\frac{1}{4}(k+1)$, $B_{k}=\frac{1}{8}(k+1)(k+2)$,
$a_{k}=\frac{1}{32L}(k+1)^{2}$ for $k\geq 1$, then

$\varphi(y^{k})-\bar{\varphi}\leq\frac{8\tilde{\mathcal{C}}}{(k+1)(k+2)},$
(4.10)

and

$\min\limits_{0\leq i\leq
k}\|\mathcal{G}(x^{i})\|^{2}\leq\frac{192L\tilde{\mathcal{C}}}{(k+1)(k+2)(k+3)}.$
(4.11)

###### Proof.

Using Lemma 4.1 and the definition ${\mathcal{C}}_{k}$, we have

$\displaystyle\mathcal{C}_{k}$
$\displaystyle\leq\mathcal{C}_{0}+\frac{L}{2}\|x^{*}-v^{0}\|^{2}-\frac{L}{2}\|x^{*}-v^{k+1}\|^{2}$
(4.12) $\displaystyle\leq
a_{0}\|\mathcal{G}(x^{0})\|^{2}+B_{0}(\varphi(y^{0})-\bar{\varphi})+\frac{L}{2}\|x^{*}-v^{0}\|^{2}$
$\displaystyle=\tilde{\mathcal{C}}.$

Note that each term in ${\mathcal{C}}_{k}$ is nonnegative. Thus, for any
$k\geq 1$ we can get

$B_{k}(\varphi(y^{k})-\bar{\varphi})\leq\mathcal{C}_{k}\leq\tilde{\mathcal{C}}$

and

$\sum\limits^{k}_{i=0}a_{i}\|\mathcal{G}(x^{i})\|^{2}\leq\mathcal{C}_{k}\leq\tilde{\mathcal{C}},$

from which the first part follows.

As for the second part, we first show that the condition
$a_{k}\leq\frac{B_{k}-b_{k}^{2}}{2L}$ can be verified by the current setting
$b_{k}=\frac{1}{4}(k+1)$, $B_{k}=\frac{1}{8}(k+1)(k+2)$, and
$a_{k}=\frac{1}{32L}(k+1)^{2}$. In fact,

$\displaystyle\frac{B_{k}-b_{k}^{2}}{2L}$
$\displaystyle=\frac{1}{2L}\left[\frac{1}{8}(k+1)^{2}+\frac{1}{8}(k+1)-\frac{1}{16}(k+1)^{2}\right]$
$\displaystyle\geq\frac{1}{2L}\cdot\frac{1}{16}(k+1)^{2}$
$\displaystyle=a_{k}.$

Now, summing $a_{i}$ from $i=0$ to $i=k$, we obtain

$\sum\limits^{k}_{i=0}a_{i}=\sum^{k}_{i=0}\frac{1}{32L}(i+1)^{2}=\frac{(k+1)(k+2)(2k+3)}{192L}.$

Therefore, combining with (4.9) in the first part, we finally get

$\min\limits_{0\leq i\leq
k}\|\mathcal{G}(x^{i})\|^{2}\leq\frac{\sum\limits^{k}_{i=0}a_{i}\|\mathcal{G}(x^{i})\|^{2}}{\sum\limits^{k}_{i=0}a_{i}}\leq\frac{192L\cdot\tilde{\mathcal{C}}}{(k+1)(k+2)(2k+3)},$

which completes the proof. ∎

##  5 Concluding remarks

In this paper, we successfully extended the potential function-based framework
in [2] from gradient descent to proximal gradient descent, with the help of
two newly discovered properties on the proximal gradient mapping. However, the
modulus of strong convexity has not yet been exploited in the current
potential function-based framework to provide linear convergence guarantees
for the norm of gradient or proximal gradient mapping; we would like to leave
it as future work.

## Acknowledgements

This work is supported by the National Science Foundation of China
(Nos.11971480).

## Appendix: The missing proofs

The proof of Lemma 3.1: Using the definition of the proximal mapping yields

$z={\mathbf{prox}}_{tg}(y)=\arg\min\limits_{x}\\{tg(x)+\frac{1}{2}\|x-y\|^{2}\\}.$

Based on the first-order optimality condition, we have

$0\in t\cdot\partial g(z)+z-y.$

Hence, the relationship $y\in(I+t\cdot\partial g)(z)$ follows. This completes
the proof.

The proof of Lemma 3.2: Take a subgradient $s\in\partial\varphi(x)=\partial
g(x)+\nabla f(x)$; then, it holds that

$x-t\nabla f(x)+ts\in(I+t\partial g)(x).$

Hence, from Lemma 3.1 we have

$x={\mathbf{prox}}_{tg}(x-t\nabla f(x)+ts).$

Using the nonexpansive property of proximal mapping, for any
$s\in\partial\varphi(x)$ we have

$\displaystyle t\|\mathcal{G}(x,t)\|$
$\displaystyle=\|x-{\mathbf{prox}}_{tg}(x-t\nabla f(x))\|$
$\displaystyle=\|{\mathbf{prox}}_{tg}(x-t\nabla
f(x)+ts)-{\mathbf{prox}}_{tg}(x-t\nabla f(x))\|$ $\displaystyle\leq
t\|s\|,~{}~{}\forall s\in\partial\varphi(x),$

from which the upper bound (3.1) follows. This completes the proof.

The proof of Lemma 3.3: First of all, we define the following auxiliary
function

$h(x,y):=g(x)+f(y)+\left\langle\nabla
f(y),x-y\right\rangle+\frac{1}{2t}\|x-y\|^{2}.$

Denote

$y^{+}:=\arg\min\limits_{x}h(x,y).$ (A.1)

Then, one can verify that

$y^{+}=y-t\mathcal{G}(y,t).$

Applying the $L$-smoothness of $f$ in (2.3), we obtain

$\displaystyle\varphi(x)$ $\displaystyle=f(x)+g(x)\leq
h(x,y)+(\frac{L}{2}-\frac{1}{2t})\|x-y\|^{2}.$

Plugging $x=y^{+}$ in the above equation, we get

$\varphi(y^{+})\leq h(y^{+},y)+(\frac{L}{2}-\frac{1}{2t})\|y^{+}-y\|^{2},$

or equivalently,

$\varphi(x)-\varphi(y^{+})\geq\varphi(x)-h(y^{+},y)-(\frac{L}{2}-\frac{1}{2t})\|y^{+}-y\|^{2}.$
(A.2)

Due to the optimality condition of (A.1), there must exist a subgradient
$g_{s}\in\partial g(y^{+})$ such that

$0=g_{s}+\nabla f(y)+\frac{1}{t}(y^{+}-y).$ (A.3)

Invoking the subgradient inequality for $g$ and the $\mu$-strong convexity for
$f$, we have

$\displaystyle f(x)$ $\displaystyle\geq f(y)+\left\langle\nabla
f(y),x-y\right\rangle+\frac{\mu}{2}\|x-y\|^{2},$ $\displaystyle g(x)$
$\displaystyle\geq g(y^{+})+\left\langle g_{s},x-y^{+}\right\rangle.$

Adding these two inequalities together, we get

$\varphi(x)\geq f(y)+g(y^{+})+\left\langle\nabla
f(y),x-y\right\rangle+\left\langle
g_{s},x-y^{+}\right\rangle+\frac{\mu}{2}\|x-y\|^{2}.$ (A.4)

On the other hand,

$h(y^{+},y)=g(y^{+})+f(y)+\left\langle y^{+}-y,\nabla
f(y)\right\rangle+\frac{1}{2t}\|y^{+}-y\|^{2}.$

Combining the preceding equation with (A.2) and (A.4), we finally get

$\displaystyle\varphi(x)-\varphi(y^{+})$
$\displaystyle\geq\varphi(x)-h(y^{+},y)-(\frac{L}{2}-\frac{1}{2t})\|y^{+}-y\|^{2}$
$\displaystyle\geq-\frac{1}{2t}\|y^{+}-y\|^{2}+\left\langle x-y^{+},\nabla
f(y)+y_{s}\right\rangle-(\frac{L}{2}-\frac{1}{2t})\|y^{+}-y\|^{2}+\frac{\mu}{2}\|x-y\|^{2}$
$\displaystyle\mathop{=}\limits^{\text{\eqref{eq:zero}}}-\frac{1}{2t}\|y^{+}-y\|^{2}+\frac{1}{t}\left\langle
y-y^{+},x-y^{+}\right\rangle-(\frac{L}{2}-\frac{1}{2t})\|y^{+}-y\|^{2}+\frac{\mu}{2}\|x-y\|^{2}.$

The desired conclusion follows by substituting
$\mathcal{G}(y,t)=t^{-1}(y-y^{+})$ into the above relationship. This completes
the proof.

## References

  * [1] Beck, A., Teboulle, M.: A fast iterative shrinkage-thresholding algorithm for linear inverse problems.  SIAM J. Imaging Sciences 2, 183–202 (2009).  DOI 10.1137/080716542
  * [2] Diakonikolas, J., Wang, P.: Potential function-based framework for minimizing gradients in convex and min-max optimization.  SIAM Journal on Optimization 32, 1668–1697 (2022).  DOI 10.1137/21M1395302
  * [3] Li, B., Shi, B., Yuan, Y.X.: Proximal subgradient norm minimization of ISTA and FISTA.  arXiv preprint arXiv:2211.01610 (2022)
  * [4] Nesterov, Y.: Introductory Lectures on Convex Optimization: A Basic Course, vol. 87.  Springer New York, NY (2004).  DOI 10.1007/978-1-4419-8853-9
  * [5] Nesterov, Y.: How to make the gradients small.  Optima. 88, 10–11 (2012)
  * [6] Shi, B., Du, S., Jordan, M., Su, W.: Understanding the acceleration phenomenon via high-resolution differential equations.  Mathematical Programming 195, 79–148 (2022).  DOI 10.1007/s10107-021-01681-8
  * [7] Taylor, A., Hendrickx, J., Glineur, F.: Exact worst-case convergence rates of the proximal gradient method for composite convex minimization.  Journal of Optimization Theory and Applications 178 (2018).  DOI 10.1007/s10957-018-1298-1
  * [8] Teboulle, M., Vaisbourd, Y.: An elementary approach to tight worst case complexity analysis of gradient based methods.  Mathematical Programming (2022).  DOI 10.1007/s10107-022-01899-0
  * [9] Zhang, L., Wang, J., Zhang, H.: New insights in smoothness and strong convexity with improved convergence of gradient descent.  arXiv preprint arXiv:2110.15470 (2021)
  * [10] Zhang, X., Zhang, H.: A new exact worst-case linear convergence rate of the proximal gradient method.  arXiv preprint arXiv:1902.09181 (2019)