# Discriminative Class Tokens for Text-to-Image Diffusion Models

Idan Schwartz1 Vésteinn Snæbjarnarson211footnotemark: 1 Hila Chefer1
Serge Belongie2 Lior Wolf1 Sagie Benaim2
1Tel Aviv University 2University of Copenhagen Equal contribution.

###### Abstract

Recent advances in text-to-image diffusion models have enabled the generation
of diverse and high-quality images. While impressive, the images often fall
short of depicting subtle details and are susceptible to errors due to
ambiguity in the input text. One way of alleviating these issues is to train
diffusion models on class-labeled datasets. This approach has two
disadvantages: (i) supervised datasets are generally small compared to large-
scale scraped text-image datasets on which text-to-image models are trained,
affecting the quality and diversity of the generated images, or (ii) the input
is a hard-coded label, as opposed to free-form text, limiting the control over
the generated images.

In this work, we propose a non-invasive fine-tuning technique that capitalizes
on the expressive potential of free-form text while achieving high accuracy
through discriminative signals from a pretrained classifier. This is done by
iteratively modifying the embedding of an added input token of a text-to-image
diffusion model, by steering generated images toward a given target class
according to a classifier. Our method is fast compared to prior fine-tuning
methods and does not require a collection of in-class images or retraining of
a noise-tolerant classifier. We evaluate our method extensively, showing that
the generated images are: (i) more accurate and of higher quality than
standard diffusion models, (ii) can be used to augment training data in a low-
resource setting, and (iii) reveal information about the data used to train
the guiding classifier. The code is available at
https://github.com/idansc/discriminative_class_tokens.

##  1 Introduction

Text-to-image diffusion models [34, 10] have shown remarkable success in
generating diverse and high-quality images conditioned on input text. However,
they often fall short when the input text contains lexical ambiguity or when
generating fine-grained details. For instance, one might wish to render an
image of a clothes ‘iron’, but could instead be presented with an image of the
elemental metal.

To alleviate these issues, pretrained classifiers have been used to guide the
denoising process. One such method mixes the score estimate of a diffusion
model with the gradient of the log probability of a pre-trained classifier
[10]. However, this approach has the downside of requiring a classifier that
works on both real and noisy data. Others have conditioned the diffusion on
class labels using a curated dataset [22] . While effective, this approach
does not lead to the full expressive power of models trained on huge
collections of web-scale image-text pairs.

Figure 1: We propose a technique that introduces a token ($S_{c}$)
corresponding to an external classifier label class $c$. By including the
token in the input text we can improve both text-to-image alignment when there
is lexical ambiguity (left) and enhance the depiction of intricate details
(right).

A different line of work fine-tunes a diffusion model, or some of its input
tokens, using a small ($\scriptstyle\sim$5) collection of images [14, 24, 35].
These methods have the following drawbacks: (i) training new concepts can be
slow, taking upwards of a few hours, (ii) the method may change the
distribution of the generated images (as compared to the original diffusion
model) to fit only the new label or concept, and (iii) the generated images
are based on features from a small group of images and may not capture the
diversity of the entire class.

This work introduces a method that more accurately captures the desired class,
avoiding lexical ambiguity while more accurately portraying fine-grained
details. It does so while retaining the full expressive power of the original
pretrained diffusion model without the above-mentioned drawbacks. Instead of
guiding the diffusion process or updating the entire model with the
classifier, we only update the representation of a single added token,
corresponding to each class of interest. We do this without tuning the model
on labeled images. To learn the token representation corresponding to a given
target class, we iteratively generate new images with a higher class
probability according to the pretrained classifier. At each iteration,
feedback from the classifier steers the designated discriminative class token
to this end. Our optimization process uses a new technique, _gradient
skipping_ , which only propagates the gradient through the final stage of the
diffusion process. The optimized token is then used as part of the
conditioning text-input to generate images using the original diffusion model.

Our method has several advantages. First, unlike other class conditional
methods such as [10], it only requires an off-the-shelf classifier and does
not require a classifier trained on noisy data. Second, our method is fast and
allows for “plug-and-play” improvements of generated images after a class-
token has been trained. This is in comparison to other methods, such as
Textual Inversion [14], which can take a few hours to converge.

Third, our method employs a classifier trained on an extensive collection of
images without needing access to those images. This is beneficial as (i) the
token is trained using the full set of class-discriminative features, as
opposed to features from a small set of images, and (ii) it may be desirable
to share only the classifier and not the data on which it is trained, such as
when privacy concerns are involved.

We evaluate our method both in the fine-grained and coarse-grained settings.
In the fine-grained setting, we investigate the ability of our method to
generate details of species in the CUB [39] and iNat21 [37] datasets. In the
coarse setting, we consider the ImageNet [9] dataset. Our primary metric is
the accuracy of the generated samples as measured in two ways: (i) we show
that our generated images are more often correctly classified using pre-
trained classifiers, in comparison to baselines, and (ii) we show that
classification models trained on generated samples, either on their own or in
combination with a limited amount of real training data, result in improved
accuracy compared to the baseline. We also measure the quality and diversity
of the generated images compared to SD and a different class-conditioning
technique, showing that our method is superior in terms of the commonly used
Fréchet inception distance (FID) [19]. Finally, we include many qualitative
examples demonstrating the effectiveness of our approach. In Fig. 1, we show
how our method can resolve ambiguity in the input text and add discriminative
features for a given class. In the ambiguous category, the image of a _tiger
cat_ becomes the cat species instead of a tiger, _iron_ is made to refer to
the tool as opposed to the metal. _Appenzeller_ moves from depicting a group
of people, from the Appenzeller area, to the dog species. In the fine-grained
category, the _Blue winged warbler’s_ throat color is corrected, the shape
features of the _Coastal woodfern_ are corrected, and the _American gray fox_
more closely resembles the true species.

##  2 Related work

The field of text-based image generation has been studied extensively, both
for GANs [17] and, more recently, for diffusion models [11, 20, 38, 25, 26,
29, 30, 33, 41, 8, 13, 34, 23]. The use of diffusion models has, in
particular, enabled an unprecedented capability in generating high-quality
diverse images from natural language input with models such as DALL$\cdot$E 2
[32], Imagen [36], Parti [40], Make-A-Scene [13], Stable Diffusion (SD) [34],
and CogView2 [12].

A recent line of work extends models of this kind by tuning the input
embeddings to personalize image generation. In particular, some contributions
generate images based on a small group of images: Textual inversion (TI) [14]
optimizes the embedding of a new textual token that represents a concept found
in a handful of images. DreamBooth [35] proposes fine-tuning of the _full_
image generation model where a unique identifier represents the concept. Both
works require 3-5 training images to learn the identity of the target concept.
A related line of work enables editing of a given image based on input text or
another image [28, 15, 7, 3, 2, 4].

More recently, some have suggested methods to leverage large text-based image
generators for image editing. Prompt-to-prompt [18] edits the input prompt
directly via manipulation of cross-attention maps, and Imagic [24] optimizes
the corresponding textual prompt and fine-tunes the model such that the image
is accurately reconstructed. When only a few images are used for training,
though, there is always the inherent risk that a concept can become too
similar to the original images.

In contrast, we aim to steer existing diffusion models toward a more general
understanding of classes via the characteristics needed to discriminate
between them, while still taking full advantage of the diversity of the
underlying generative model. Our method is also faster than image-based
training methods such as TI and can effectively make use of an off-the-shelf
classifier to train the token needed to refine an image within minutes.

Manipulating an image using classifier conditioning can also provide a
counterfactual explanation for classifiers [6, 16, 1]. In that sense, our
method may also be used to reveal salient visual features of the classifer.
Since semantic differences are relatively small during each iteration of the
image generation, they can be detected during the process.

##  3 Method

We now describe how the discriminative token embeddings are learned. We first
introduce conditional diffusion models in general, including _classifier
guidance_ (not to be confused with our method), and then describe our
conditioning approach and the gradient skipping. An overview of our method is
provided in Fig. 2.

Figure 2: An overview of our method for optimizing a new discriminative token
representation ($v_{c}$) using a pre-trained classifier. For the prompt ‘A
photo of a $S_{c}$ tiger cat,’ we expect the output generated with the class
$c$ to be ‘tiger cat’. The classifier, however, indicates that the class of
the generated image is ‘tiger’. We generate images iteratively and optimize
the token representation using cross-entropy. Once $v_{c}$ has been trained,
more images of the target class can be generated by including it in the
context of the input text.

#### Conditional diffusion models

Diffusion models [21, 10] estimate a process that generates data $x\sim p(x)$
from randomly sampled noise. During training, an iterative denoising process
predicts step-wise added noise $x_{T}\sim\mathcal{N}(0,\text{I})$. More
specifically, given an input image (or a latent encoding) $x_{0}\sim p(x)$,
one first produces samples
$x_{t}=\sqrt{\alpha_{t}}x_{0}+\sqrt{1-\alpha_{t}}\cdot\epsilon_{t}$, with
$0<\alpha_{T}<\alpha_{T-1}<\dots<\alpha_{0}=1$ being hyperparameters and
$\epsilon_{t}\sim\mathcal{N}(0,\text{I})$. A neural network is then trained to
predict the added noise $\epsilon_{t}$ via the objective function:

$\mathbb{E}_{x,\epsilon_{t},t}[||\hat{\epsilon}_{\theta}(x_{t},t)-\epsilon_{t}||^{2}_{2}],$
(1)

A conditional denoising process, where each denoising step depends on a
conditioning input (e.g., a class identifier or a text prompt $y$), can be
defined similarly:

$\mathbb{E}_{x,\epsilon_{t},t}[||\hat{\epsilon}_{\theta}(x_{t},t,y)-\epsilon_{t}||^{2}_{2}],$
(2)

To condition the diffusion process on a class, gradients obtained with trained
classifiers can be used in the denoising process [10]. In particular,
gradients of contrastive image-text models, like CLIP [31], have been used for
text conditioning. Utilizing classifier guidance improves the sample quality
and enables a trade-off between sample quality and diversity.

There are two main drawbacks to using classifier guidance within the diffusion
process: (i) the classifier must be retrained to deal with noised images as
every noisy sample generated along the iterative denoising process must be
passed through the classifier, and (ii) the classifier needs to be present
throughout the generative process. To mitigate these issues, a _classifier-
free_ approach has been proposed [10]. Instead of relying on gradients from an
image classifier, this approach approximates the gradient of an implicit
classifier by modeling the difference between conditional, $p_{\theta}(x|y)$,
and unconditional, $p_{\theta}(x)$, denoising modules. The conditional and
unconditional modules are parameterized using the same noise predicting model
$\epsilon_{\theta}(x_{t},y)$. The conditional network then becomes
unconditional by using an empty input, i.e.,
$\epsilon_{\theta}(x_{t})=\epsilon_{\theta}(x_{t}."")$. The final denoising
network is formally expressed as follows:

$\bar{\epsilon}_{\theta}(x,x_{t},y)=(1+w)\epsilon_{\theta}(y_{t},y)-w(\epsilon_{\theta}(x_{t})),$
(3)

where $w$ is a hyperparameter determining the strength of the conditioning
guidance.

Our method is complementary to both the _classifier-based_ and _classifier-
free guidance_ , and can be used in conjunction with both. While our method
can be deployed using any diffusion model, here we consider Stable Diffusion
(SD) [34]. In SD the denoising process is applied not directly to the pixel
values of the images, but in the lower dimensional latent dimensions of a
neural network.

#### Discriminative Token Embeddings

Classifiers capture discriminative signals needed to discern between classes.
In that sense, pretrained classifiers can be seen as experts models in
different domains. For example, a bird classifier can provide a compact source
of discriminative details that separate one species from another.

To avoid relying on a classifier at inference time, and reduce the need to
fine-tune the classifier on noised images (as in earlier work), our method
fine-tunes a token that is added to the input vocabulary. Our technique
iteratively generates images and refines this added token (as opposed to a
word or subword found in the original embedding matrix) to associate the
generated images with a target class of the pre-trained classifier. The only
weights being updated are those of the new class token.

The process starts with a discriminative class token $S_{c}$ and a generic
prompt $p=\text{``A photo of a $S_{c}$ {label}''}$, where label is the English
name of the class. We include the class name as part of the prompt to take
advantage of existing knowledge in the pre-trained diffusion model (but only
update the embedding for $S_{c}$ during training). By looking at the images,
e.g., in Fig. 1 it is evident that the configuration has gained knowledge
across various domains, including expertise in generating specific bird
species, though with some limitations. Our approach aims to enhance the
precision of the generated image by introducing minor semantic modifications
that leverage the model’s existing knowledge.

We now describe how we associate the characteristics of the target class with
the added token’s representation. We denote the embedding of the class token
$S_{c}$ as $v_{c}$, and learn it by utilizing an image classifier $C$. To
speed up training, $v_{c}$ is initialized as the embedding of a related token.
For instance, in the case of a bird classifier, we initialize the embedding to
that of the ‘bird’ token in the input encoder. For more general classifiers,
such as those trained on ImageNet, we use the indefinite article token ‘a’ as
a base for more generalized concepts. Training starts by generating an image
$x(p)$ conditioned on $p$, which includes the $v_{c}$ representation. We feed
the resulting image into the classifier and use cross-entropy loss over the
classifier labels, i.e.,

$\min_{v_{c}}\operatorname{CE}\left(C\left(\psi_{C}(x(p))\right),\mathds{1}_{c}\right),$
(4)

where $\psi_{C}$ transforms the image to align it with the classifier’s
expected input (e.g., resizing), and $\mathds{1}_{c}$ is one hot vector of the
target class. To summarize, our method does not rely on a given set of images.
Instead, it generates images iteratively, starting with the output from SD,
where each optimization step shifts the generated images closer to the target
class distribution by updating the class token. A single image can be
optimized directly by training a token that generally converges in a
relatively small number of steps.

Figure 3: An illustration of the gradient skipping technique (indicated by the
red line). During backpropagation, the gradient is propagated only through the
final denoising step of the diffusion procedure.

#### Gradient skipping

Fig. 3 illustrates the generation of a single image using a diffusion process
and the flow of the learning signal. Propagating gradients through all
diffusion steps requires a significant amount of memory. In our experiments,
propagating gradients solely through the final denoising step (i.e., step $T$)
produces high-quality images representing the intended class while requiring
fewer resources. While deeper backpropagation could lead to further
enhancements, we do not explore this direction further due to memory
constraints.

#### Design Choices

Our approach involves several design choices. (i) Batch size: Our goal is not
to refine a single image but to find a broad token representation that can
generate new images without incurring extra costs. By generating images with
different seeds, we get diverse images. A larger batch size picks up more
generic discriminative features, but training takes slightly longer to
converge. We set the batch size to 5 after experimenting with values of 1-6.
More details and examples of generations are shown in the supplementary. (ii)
Number of prompts: Increasing the number of prompts can introduce additional
variability. However, we find too much variability during training harmful to
convergence. Thus, we limited the number of prompts used in the training phase
to two: $p_{1}=$“A high-resolution realistic image of a $S_{c}$ label”, and
$p_{2}=$“A photo of $S_{c}$ label”. It is worth noting that one can still
utilize the discriminative token across various prompts, as shown in Fig. 7.
(iii) Updated tokens: Our experiments focus on optimizing only the embedding
of $S_{c}$. While it is possible to update other pre-existing tokens, doing so
would modify the model and prevent it e.g. from being used in case of lexical
overlap between classes, such as in the case of mouse as depicted in Fig. 11.
(iv) Early stopping strategy: Please refer to the supplementary for additional
details.

Dataset | Classifier | Guidance | Top-1 | Top-5
---|---|---|---|---
ImageNet | ImageNet | - | 70.5 | 89.7
ImageNet | ImageNet | ImageNet | 74.5 | 92.6
CUB | CUB | - | 39.7 | 73.3
CUB | CUB | CUB | 57.9 | 88.6
iNat179 | iNat | - | 28.5 | 56.5
iNat179 | iNat | CUB | 32.8 | 63.5
iNat50 | iNat | - | 14.1 | 28.7
iNat50 | iNat | iNat | 25.8 | 50.3
Table 1: Classification results on four datasets: ImageNet, CUB, and two subsets from iNaturalist21: iNat50, and iNat179. For each dataset, we calculate the accuracy using a classifier (Classifier) on images generated with or without the guidance of another classifier (Guidance). For all datasets, accuracy is higher when guidance is used, including in the case (iNat179) where the classifier used (iNat) differs from that used for guidance (CUB). | # Real img. | Baseline | SD | Ours (CUB)
---|---|---|---|---
| per class | T-1 | T-5 | T-1 | T-5 | T-1 | T-5
CUB | 0 | 0.0 | 0.0 | 37.1 | 67.8 | 48.6 | 78.5
3 | 1.8 | 5.1 | 52.6 | 84.9 | 62.5 | 87.9
9 | 35.1 | 72.3 | 68.3 | 92.7 | 76.3 | 95.1
15 | 71.5 | 94.1 | 77.3 | 95.8 | 81.4 | 96.4
iNat179 | 0 | 0.0 | 0.0 | 22.1 | 47.7 | 28.1 | 55.2
3 | 1.3 | 5.7 | 31.6 | 61.1 | 37.1 | 66.9
9 | 8.0 | 27.3 | 43.0 | 74.3 | 49.5 | 78.3
15 | 28.7 | 62.9 | 49.8 | 81.4 | 58.3 | 84.1
Table 2: Results for classifiers trained with 100 generated and 0-15 real images (# Real img.) from each CUB class, and in the overlap of 179 species in iNat. For the baseline column, we use only real images. Results with our method use CUB guidance and improve performance even for the different iNat179 dataset.  Method |  FID $\downarrow$ |  KID $\downarrow$
---|---|---
Text-conditioned (SD v1.4) | 23.0 | 0.00398
Text-conditioned (SD v2.1) | 15.7 | 0.00858
Class Conditioned Methods
Class-conditioned [34] | 47.6 | 0.0115
Ours (SD v1.4) | 22.4 | 0.00364
Ours (SD v2.1) | 14.7 | 0.00775
Table 3: FID and KID scores for generated ImageNet classes. For SD and our
method, we consider two versions of the underlying SD model (1.4/2.1). Figure
4: Images generated based on ImageNet classes, using SD or our method. Real
images are shown for comparison.

(a)

(b)

(c)

(d)

SD

Ours

Real

(e)

(f)

(g)

(h)

SD

Ours

Real

Figure 5: A selection of images based on iNat classes generated with Stable
Diffusion (SD) and our method. A real image is shown for comparison. (a)
Yellow pine chipmunk, (b) Jelly antler, (c) Salamander, (d) Pacific lions mane
jelly, (e) Leaf mite, (f) Red sea urchin, (g) Seashore mallow, (h) Sheepshead
minnow.

Figure 6: Images generated using class-conditioned LDM, text-conditioning
(SD), and our method with ImageNet classifier guidance.

Figure 7: Results with different prompts for three classes: (i) tiger cat,
(ii) Japanese spaniel, and (iii) beach wagon.  Figure 8: Comparison of our
method to Textual Inversion (TI). TI-generated images often lack diversity and
are prone to incorporating background features from a limited set of images.
For example, in the Japanese spaniel class, TI generates a black-and-white dog
due to limited color variations in the given images. In the beach wagon class,
TI includes the road as part of the object, changing the background to a road
from a beach. For reference, we also display SD’s generated samples.

##  4 Results

Quantitatively, we evaluate the ability of our method to conform to the input
class and to generate high-fidelity images. For the former, we consider the
following: (i) taking pre-trained classifiers and assessing the classification
accuracy of generated images, and (ii) evaluating the accuracy of classifiers
trained using generated and real images. This assesses the generated images in
two complementary ways. If the pre-trained classifier correctly classifies
generated images, then they capture features from the correct class. If the
generated images can be used to improve a classifier’s performance (over the
same evaluation set), then they capture a broad range of additional
discriminative features that can improve classification accuracy. To evaluate
the quality of generated images, we consider the commonly used FID score [19]
and KID score [5]. Finally, we consider the memory footprint and the speed of
our method. Qualitatively, we demonstrate the effectiveness of our approach in
adding fine-grained details and resolving problematic cases of ambiguity.
Please refer to the supplementary for a full description of the experimental
setup, including implementation and training details. We note that all
reported SD baselines are with classifier-free guidance using default
parameters.

#### Datasets

For fine-grained categories, such as those of birds and animal species, we use
the CUB dataset [39] and the iNaturalist 2021-mini (iNat from here on) dataset
[37]. We also consider two subsets of iNat: (a) iNat179, a subset that
overlaps with CUB in 179 out of the 200 labels and allows us to classify
images generated when utilizing guidance from a different classifier (in
particular, one trained on a different dataset), (b) iNat50, a sample of 50
species randomly selected from each of the 11 supercategories. In the course-
grained setting, we consider the ImageNet dataset [9].

###  4.1 Quantitative evaluation

#### Evaluation using pre-trained classifiers

We first evaluate the generated images with classifiers trained on real data.
We generate 100 images for each class and calculate the accuracy of each
method: one employing our class token and another with only SD. In Tab. 1, we
show that for ImageNet, which mainly consists of classes at a coarse level of
granularity, the vanilla SD can generate most classes accurately (70.5%). By
utilizing class token guidance, we get better results in complex cases, such
as those with ambiguity, resulting in an improved accuracy of 74.5%. For our
method and SD, the seed and textual context were held constant, so the images
correspond to each other, with the differences being due to the use of the
token. As a further comparison, we consider SD model v2.1 (as opposed to the
default v1.4 but with the same hyperparameter configuration). Here our method
achieves $57.1\%$ accuracy in comparison to SD’s $54.6\%$.

We next assess fine-grained classes. Testing the model on the images generated
with labels found in the CUB dataset, the accuracy of SD-generated images is
only 39.7%. This emphasizes the inherent limitations of the SD model in
generating highly detailed and specific categories, such as bird species. Our
approach adds the fine details necessary to improve accuracy to 57.9%. As a
further comparison, we consider SD model v2.1 (as opposed to the default
v1.4). Here our method achieves $47.7\%$ accuracy in comparison to SD’s
$44.0\%$. We also assess the accuracy of the generated images using the iNat
classifier (trained on 10k species) on the same image generated with the
guidance of the CUB classifier. Our approach yields a noteworthy improvement
in performance from 28.5% to 32.8%, indicating its potential to enhance fine-
grained classes beyond the specific classifier-selected characteristics.
Finally, we look at a diverse set of 50 classes from the iNat dataset. SD only
generates images that are classified accurately 14.1% of the time. Our method
significantly improves accuracy to 25.8%, while still leaving ample room for
further improvement.

#### Evaluation by training classifiers

In Tab. 2, we show results for training classifiers on 100 generated images
and 0-15 real images. When we incorporate the classifier-guided generated
images, the real evaluation accuracy is better than when augmenting only with
SD-generated images. With only nine real images per class, we already reach
76.3% accuracy compared to 35.1% with no generated images and 68.3% with SD-
only augmentations. A high accuracy indicates that the generated images
capture a large part of the distribution necessary to classify images
correctly. Our findings also show that utilizing the CUB classifier for
generating images can enhance performance when evaluated in the iNat179
setting. Specifically, incorporating our proposed image augmentation method
improves accuracy, reaching 58.3% with only 15 real images, compared to the
significantly lower accuracy of 49.8% and 28% with SD or when no augmentation
is applied. These results indicate that our approach shows potential for
augmenting data in low-resource settings by transferring knowledge from
diverse classifiers.

#### FID and KID evaluation

Class-conditioned image generation models may enjoy the benefit of eliminating
ambiguity in generated images. However, datasets used to train these models
are limited only to specific classes, and do not capture the wide variety of
images depicting free-form text. In Tab. 3, we make use of FID [19] and KID
[5] scores to assess the quality of the generated images with respect to the
real datasets. Our evaluation shows that the text-conditioned method generates
higher-quality images compared to a prior class-conditioned method. The text-
conditioned method of SD, on the other hand, is limited by ambiguity issues
and has difficulty in depicting fine details. Our proposed method provides a
balance between generating high-quality images accurately and avoiding
ambiguity issues.

#### Memory Requirements and Speed

Our memory footprint is low, due to our gradient skipping method. For training
and inference, a single commercial GPU with 10GB of VRAM can be used. This is
comparable to Textual Inversion (TI). At inference, the same memory
requirements are needed as for classifier-free guidance, TI, and SD.

In terms of speed, our method takes $\scriptstyle\sim$10 minutes to train on a
single GPU. For TI, $\scriptstyle\sim$1 hour is required. To capture
additional class diversity with TI, one must train on a full class-
representative set of images ($\scriptstyle\sim$1000 for ImageNet), with
$\scriptstyle\sim$5 images (1 hour) at a time, requiring days at best.
Further, our method doesn’t require retraining an expensive diffusion model
(e.g. 256 A100 for two weeks as SD). Inference time is the same as for SD/TI
and takes about 0.88s per sample using our configuration.

###  4.2 Qualitative assessment

Figure 9: Demonstration of using discriminative tokens for gender and bald
attributes, ‘SD’ shows the initial generation.  Figure 10: Examples of
revealed features from the training data when using an ImageNet classifier for
guidance.

In Fig. 4, we show various generated samples based on ImageNet classes. From
left to right, our method reinforces distinctive features of the dog species,
in particular, the face. The distinct characteristics of the custard apple and
slot images are highlighted with our method. For the mailbag, the ‘mail’ term
appears to confuse SD to generate a mail-related image rather than a mailbag.
More ambiguities arise from the term wheel in potter’s wheel and the kite
class. In some cases, we only partially resolve ambiguity. For instance, beach
wagon cars still appear on the beach, the bird kite resembles a toy kite.
Another interesting case is when the method adds another instance of the
target class object, as is the case in the pug image.

In Fig. 5, we show images generated using labels from the iNat dataset. We
sample 50 species from each and compare them using SD and our method. Our
method corrects for attributes such as patterns (e.g., (a), and (h)),
anatomical issues (e.g., (b), (c), (f)), and resolves lexical ambiguity (e.g.,
(b), (d), (g)).

In Fig. 7, we show that only class-conditioned images appear less natural
despite being highly relevant to the class. Our approach allows us to benefit
from the advantages of both worlds, producing high-quality images that are
both precise and devoid of ambiguity.

Another advantage of our approach over simple class conditioning [34] is the
flexibility to use trained tokens with various prompts. In Fig. 7, we
demonstrate that our discriminative tokens can be employed in different
prompts, resulting in minimal semantic changes that primarily affect the
object of interest that is relevant to the class.

#### Textual Inversion

Textual Inversion (TI) employs an optimization technique whereby embeddings
are found to represent a given concept captured by a small set of 5 images. As
can be seen in Figure 8, TI’s generated images can lack diversity and are
prone to incorporating background features from a limited set of images. For
example, in the Japanese spaniel class, TI generates a black-and-white dog due
to limited color variations in the given images. In the beach wagon class, TI
includes the road as part of the object, preventing it from appearing in the
snow.

#### Face attributes

Our method is not only capable of enhancing objects and animals. We show that
a classifier based on CelebFaces attributes [27] can be used to learn a token
representing a facial attribute. We generate a facial image using the prompt
“An image of a $S_{c}$ person’s face.”. We optimize $S_{c}$ using a classifier
consisting of six convolutional layers followed by two fully connected layers.
In Fig. 9, we present our results obtained by training with the guidance of
baldness and gender attributes. During training, we observed that the hair
feature is more dominant for the ‘not bald’ class. For the ‘bald’ class, the
generated image depicts old men and their identity is lost. This suggests that
age may be a hidden factor in the training data.

#### Classifier inversion

Our method has the ability to inverse the action of a classifier without
access to its trained data. For example, we often observe changes in the
background when optimizing for an object’s class. As Fig. 10 shows, applying
our method with ImageNet-trained classifier results in an image of a lobster
on a plate given the phrase ‘American lobster.’ Another example is the
‘horizontal bar’ class, for which our method predominantly generates images
containing athletes and a gym environment. We manually assessed ImageNet’s
training data by classifying 100 images from the ‘American lobster’ and
‘horizontal bar’ classes and determining whether they exhibit these features
in the training data. For the ‘American lobster’ class, 55% of the images
featured a plate, and the lobster in an edible form, and for the ‘horizontal
bar’ class, 95% of the images included an athlete performer. In Fig. 10, we
present some instances from the training data that illustrate these
characteristics. Nevertheless, interpreting the results needs to be done with
caution. It is possible that this bias toward a certain type of image reflects
one local minimum in our optimization process.

#### Ablation

To illustrate the benefit of using a special token, instead of directly
updating the original tokens, we ran a simple experiment where the ‘mouse’
token is updated using the class when used in the sense of ‘computer mouse’.
This can prevent the model from generating the animal ‘mouse’ when using that
token, as shown in Figure 11.

Figure 11:  An advantage of employing a special token over directly modifying
original tokens. Updating the ‘mouse’ token directly would mistakenly
associate attributes with all instances of ‘mouse,’ including the animal with
‘computer mouse.’

##  5 Conclusion

In this paper, we introduced a “plug-and-play” approach for rapidly fine-
tuning text-to-image diffusion models by using a discriminative signal. Our
approach trains a new token without additional images, enhancing fine-grained
details for classifiers pre-trained on datasets such as CUB and iNat and
resolving lexical ambiguity. We have also demonstrated how our method can be
used to distill generative image models to supplement datasets lacking
imagery, edit faces based on attributes classifier, and analyze hidden factors
in the training data. Going forward, we aim to extend our approach to other
model types beyond classification.

##  6 Acknowledgements

This project was supported by a grant from the Tel Aviv University Center for
AI and Data Science (TAD). VS, SB, and SB are supported by the Pioneer Centre
for AI, DNRF grant number P1.

## References

  * [1] Maximilian Augustin, Valentyn Boreiko, Francesco Croce, and Matthias Hein.  Diffusion Visual Counterfactual Explanations.  NeurIPS, 2022.
  * [2] Omri Avrahami, Ohad Fried, and Dani Lischinski.  Blended latent diffusion.  ACM Trans. Graph., 42(4), jul 2023.
  * [3] Omri Avrahami, Dani Lischinski, and Ohad Fried.  Blended diffusion for text-driven editing of natural images.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 18208–18218, 2022.
  * [4] Omer Bar-Tal, Dolev Ofri-Amar, Rafail Fridman, Yoni Kasten, and Tali Dekel.  Text2LIVE: Text-Driven Layered Image and Video Editing.  In Computer Vision – ECCV 2022, pages 707–723, Cham, 2022. Springer Nature Switzerland.
  * [5] Mikołaj Bińkowski, Dougal J. Sutherland, Michael Arbel, and Arthur Gretton.  Demystifying MMD GANs.  In International Conference on Learning Representations, 2018.
  * [6] Valentyn Boreiko, Maximilian Augustin, Francesco Croce, Philipp Berens, and Matthias Hein.  Sparse visual counterfactual explanations in image space.  In DAGM German Conference on Pattern Recognition, pages 133–148. Springer, 2022.
  * [7] Hila Chefer, Sagie Benaim, Roni Paiss, and Lior Wolf.  Image-Based CLIP-Guided Essence Transfer.  In Computer Vision – ECCV 2022, pages 695–711, Cham, 2022. Springer Nature Switzerland.
  * [8] Katherine Crowson, Stella Biderman, Daniel Kornis, Dashiell Stander, Eric Hallahan, Louis Castricato, and Edward Raff.  VQGAN-CLIP: Open Domain Image Generation and Editing with Natural Language Guidance.  In Shai Avidan, Gabriel Brostow, Moustapha Cissé, Giovanni Maria Farinella, and Tal Hassner, editors, Computer Vision – ECCV 2022, pages 88–105, Cham, 2022. Springer Nature Switzerland.
  * [9] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei.  Imagenet: A large-scale hierarchical image database.  In 2009 IEEE conference on computer vision and pattern recognition, pages 248–255. Ieee, 2009.
  * [10] Prafulla Dhariwal and Alexander Nichol.  Diffusion models beat gans on image synthesis.  Advances in Neural Information Processing Systems, 34:8780–8794, 2021.
  * [11] Ming Ding, Zhuoyi Yang, Wenyi Hong, Wendi Zheng, Chang Zhou, Da Yin, Junyang Lin, Xu Zou, Zhou Shao, Hongxia Yang, et al.  Cogview: Mastering text-to-image generation via transformers.  Advances in Neural Information Processing Systems, 34:19822–19835, 2021.
  * [12] Ming Ding, Wendi Zheng, Wenyi Hong, and Jie Tang.  Cogview2: Faster and better text-to-image generation via hierarchical transformers.  arXiv preprint arXiv:2204.14217, 2022.
  * [13] Oran Gafni, Adam Polyak, Oron Ashual, Shelly Sheynin, Devi Parikh, and Yaniv Taigman.  Make-A-Scene: Scene-Based Text-to-Image Generation with Human Priors.  In Computer Vision – ECCV 2022, pages 89–106, Cham, 2022. Springer Nature Switzerland.
  * [14] Rinon Gal, Yuval Alaluf, Yuval Atzmon, Or Patashnik, Amit Haim Bermano, Gal Chechik, and Daniel Cohen-or.  An image is worth one word: Personalizing text-to-image generation using textual inversion.  In The Eleventh International Conference on Learning Representations, 2023.
  * [15] Rinon Gal, Or Patashnik, Haggai Maron, Amit H. Bermano, Gal Chechik, and Daniel Cohen-Or.  StyleGAN-NADA: CLIP-Guided Domain Adaptation of Image Generators.  ACM Trans. Graph., 41(4), jul 2022.
  * [16] Itai Gat, Guy Lorberbom, Idan Schwartz, and Tamir Hazan.  Latent space explanation by intervention.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 679–687, 2022.
  * [17] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio.  Generative adversarial nets.  Advances in neural information processing systems, 27, 2014.
  * [18] Amir Hertz, Ron Mokady, Jay Tenenbaum, Kfir Aberman, Yael Pritch, and Daniel Cohen-or.  Prompt-to-Prompt Image Editing with Cross-Attention Control.  In The Eleventh International Conference on Learning Representations, 2023.
  * [19] Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter.  GANs trained by a two time-scale update rule converge to a local nash equilibrium.  In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
  * [20] Tobias Hinz, Stefan Heinrich, and Stefan Wermter.  Semantic object accuracy for generative text-to-image synthesis.  IEEE transactions on pattern analysis and machine intelligence, 2020\.
  * [21] Jonathan Ho, Ajay Jain, and Pieter Abbeel.  Denoising diffusion probabilistic models.  Advances in Neural Information Processing Systems, 33:6840–6851, 2020.
  * [22] Jonathan Ho and Tim Salimans.  Classifier-Free Diffusion Guidance.  In NeurIPS 2021 Workshop on Deep Generative Models and Downstream Applications, 2021.
  * [23] Ajay Jain, Ben Mildenhall, Jonathan T Barron, Pieter Abbeel, and Ben Poole.  Zero-shot text-guided object generation with dream fields.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 867–876, 2022.
  * [24] Bahjat Kawar, Shiran Zada, Oran Lang, Omer Tov, Huiwen Chang, Tali Dekel, Inbar Mosseri, and Michal Irani.  Imagic: Text-Based Real Image Editing with Diffusion Models.  In Conference on Computer Vision and Pattern Recognition 2023, 2023\.
  * [25] Bowen Li, Xiaojuan Qi, Thomas Lukasiewicz, and Philip Torr.  Controllable text-to-image generation.  Advances in Neural Information Processing Systems, 32, 2019.
  * [26] Wenbo Li, Pengchuan Zhang, Lei Zhang, Qiuyuan Huang, Xiaodong He, Siwei Lyu, and Jianfeng Gao.  Object-driven text-to-image synthesis via adversarial training.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 12174–12182, 2019.
  * [27] Z Liu, P Luo, X Wang, and X Tang.  Deep learning face attributes in the wild. arxiv.  ICCV, 2015.
  * [28] Or Patashnik, Zongze Wu, Eli Shechtman, Daniel Cohen-Or, and Dani Lischinski.  StyleCLIP: Text-Driven Manipulation of StyleGAN Imagery.  In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV), pages 2085–2094, October 2021.
  * [29] Tingting Qiao, Jing Zhang, Duanqing Xu, and Dacheng Tao.  Learn, imagine and create: Text-to-image generation from prior knowledge.  Advances in neural information processing systems, 32, 2019.
  * [30] Tingting Qiao, Jing Zhang, Duanqing Xu, and Dacheng Tao.  Mirrorgan: Learning text-to-image generation by redescription.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 1505–1514, 2019.
  * [31] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, Gretchen Krueger, and Ilya Sutskever.  Learning Transferable Visual Models From Natural Language Supervision.  In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 8748–8763. PMLR, 2021.
  * [32] Aditya Ramesh, Prafulla Dhariwal, Alex Nichol, Casey Chu, and Mark Chen.  Hierarchical text-conditional image generation with clip latents.  arXiv preprint arXiv:2204.06125, 2022.
  * [33] Aditya Ramesh, Mikhail Pavlov, Gabriel Goh, Scott Gray, Chelsea Voss, Alec Radford, Mark Chen, and Ilya Sutskever.  Zero-shot text-to-image generation.  In International Conference on Machine Learning, pages 8821–8831. PMLR, 2021.
  * [34] Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Björn Ommer.  High-resolution image synthesis with latent diffusion models.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 10684–10695, June 2022.
  * [35] Nataniel Ruiz, Yuanzhen Li, Varun Jampani, Yael Pritch, Michael Rubinstein, and Kfir Aberman.  Dreambooth: Fine tuning text-to-image diffusion models for subject-driven generation.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2023.
  * [36] Chitwan Saharia, William Chan, Saurabh Saxena, Lala Li, Jay Whang, Emily Denton, Seyed Kamyar Seyed Ghasemipour, Raphael Gontijo-Lopes, Burcu Karagol Ayan, Tim Salimans, Jonathan Ho, David J. Fleet, and Mohammad Norouzi.  Photorealistic Text-to-Image Diffusion Models with Deep Language Understanding.  In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022.
  * [37] Jong-Chyi Su and Subhransu Maji.  The semi-supervised inaturalist challenge at the FGVC8 workshop, 2021\.
  * [38] Ming Tao, Hao Tang, Fei Wu, Xiao-Yuan Jing, Bing-Kun Bao, and Changsheng Xu.  DF-GAN: A Simple and Effective Baseline for Text-to-Image Synthesis.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 16515–16525, 2022.
  * [39] C. Wah, S. Branson, P. Welinder, P. Perona, and S. Belongie.  The Caltech-UCSD birds-200-2011 dataset.  Technical Report CNS-TR-2011-001, California Institute of Technology, 2011\.
  * [40] Jiahui Yu, Yuanzhong Xu, Jing Yu Koh, Thang Luong, Gunjan Baid, Zirui Wang, Vijay Vasudevan, Alexander Ku, Yinfei Yang, Burcu Karagol Ayan, Ben Hutchinson, Wei Han, Zarana Parekh, Xin Li, Han Zhang, Jason Baldridge, and Yonghui Wu.  Scaling Autoregressive Models for Content-Rich Text-to-Image Generation.  Transactions on Machine Learning Research, 2022.  Featured Certification.
  * [41] Zizhao Zhang, Yuanpu Xie, and Lin Yang.  Photographic text-to-image synthesis with a hierarchically-nested adversarial network.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 6199–6208, 2018.

##  Appendix A Supplementary

In this supplementary, we extend the concepts presented in the main paper and
describe the findings of our empirical analysis. The supplementary comprises
the following subsections:

  1. 1.

Appendix B, batch size comparison

  2. 2.

Appendix C, examples of image generations with tokens trained different number
of steps

  3. 3.

Appendix D, more details on the training setup

  4. 4.

Appendix E, capabilities of SD on CUB with failure cases

  5. 5.

Appendix F, FID comparison with SD

  6. 6.

Appendix G, qualitative samples

##  Appendix B Batch size ablation study

We experimented with the following batch sizes: $1,2,3,4,5,6$. To measure the
accuracy of each experiment, we generated 20 images with the trained
discriminative token. We used three datasets: (1) CUB, (2) iNat21, and (3)
ImageNet. Our study included a specific set of difficult classes, including
those with ambiguous class names or those distinguished with fine details. The
labels used for CUB are: _Chuck will Widow, Grasshopper Sparrow, Pied
Kingfisher, Scissor tailed Flycatcher, Worm eating Warbler, Rhinoceros Auklet,
Gadwall, Mourning Warbler, Spotted Catbird, Olive sided Flycatcher, Blue
Grosbeak, Black billed Cuckoo, Brown Pelican, White necked Raven, Tree
Swallow, Black throated Sparrow, Pied billed Grebe, Horned Grebe, Spotted
Catbird, Heermann Gull_. The labels used for iNat are randomly selected:
_grosbeak weaver, skeleton weed, ribbon jumping spider, common garden orbweb
spinner, glass shrimp, crevice swift, eastern spiny lizard, double-barred
finch, speckled swimming crab, new zealand cockle, common wall lizard, red-
bordered pixie, old mans beard, rough-mantled dorid, green shore crab, ear
fungus, european common cuttlefish, argentine black-and-white tegu, cassins
vireo, steenbok_. The labels used for ImageNet are: _trilobite, kite, eft,
bullfrog, Gila monster, crane, Japanese spaniel, drake, quail, Scotch terrier,
curly-coated retriever, English setter, American chameleon, brass, bonnet,
amphibian, ashcan, horizontal bar, iron, slot, spindle, sundial, steel drum,
gong, coffee mug, vault, axolotl, tiger cat, bearskin_.

The results are summarized in Tab. 4. Using batch sizes 4-6 gives the best
result depending on the dataset.

| CUB | iNat | iNet
---|---|---|---
Batch Size | Acc | Acc | Acc
Baseline | 14.2 | 4.8 | 15.7
1 | 28.2 | 26.8 | 22.5
2 | 40.1 | 35.8 | 27.0
3 | 34.0 | 34.0 | 21.8
4 | 43.7 | 29.6 | 29.7
5 | 54.2 | 28.3 | 35.3
6 | 50.3 | 29.4 | 39.3
Table 4: Summary of accuracy and average steps needed over different batch
sizes. SD accuracy is provided as a baseline.

In Fig. 12, we show comparisons over the CUB200 dataset for different batch
sizes. In Fig. 13, the same sort of comparison is shown for iNat21. The images
show that classifier guidance can adjust the appearance and add features to
make the generated image more like a true sample. Note that the true images
were hand-picked to be in a similar position as that in the generated images.

Figure 12: A comparison between Stable Diffusion, and six different batch
sizes using CUB200 classifier guidance, as well as a real image. Figure 13: A
comparison between Stable Diffusion, and six different batch sizes using
iNat21 classifier guidance, as well as a real image.

##  Appendix C Tokens from different training steps

Our proposed technique performs iterative updates on the class tokens, and the
progress can be demonstrated by comparing images at each stage. For instance,
we modified an image by utilizing class tokens from various training stages,
as shown in Fig. 14, to depict this process. Our results indicate that at
times the modified images become increasingly similar to authentic images in
terms of structure, with less noticeable changes in color patterns. This
finding suggests that shape may be more critical to classifiers, given the
high variability in color patterns among objects and animals of the same
class.

Anna Hummingbird

(a) Step 1

(b) Step 2

(c) Step 3

(d) Step 4

(e) Step 5

(f) Step 6

(g) Real

Sptd. catbird

(h) Step 1

(i) Step 9

(j) Step 10

(k) Step 12

(l) Step 16

(m) Step 19

(n) Real

Bull frog

(o) Step 1

(p) Step 5

(q) Step 7

(r) Step 8

(s) Step 9

(t) Step 11

(u) Real

Marmoset

(v) Step 1

(w) Step 7

(x) Step 13

(y) Step 19

(z) Step 29

(aa) Step 46

(ab) Real

Madag. cat

(ac) Step 1

(ad) Step 11

(ae) Step 14

(af) Step 15

(ag) Step 26

(ah) Step 34

(ai) Real

Ashcan

(aj) Step 1

(ak) Step 2

(al) Step 3

(am) Step 4

(an) Real

Figure 14: Intermediary results from class tokens fine-tuned for differing
numbers of steps. Steps are chosen to highlight the overall changes.

##  Appendix D More details on the training setup

In this section, additional information regarding our setup is provided. Our
approach involved employing classifier-free guidance, with a scale of 7 and
executing $T=50$ denoising steps for the Stable Diffusion process. The
generated images were created with a height and width of 512 pixels. Along
with these parameters, there were other hyperparameters: (i) The learning
rate; we used 0.0005. We recommend adapting it based on the batch size with
the formula $0.00025\cdot bsz$, where $bsz$ indicates the batch size. (ii)
Early stopping; we had three rules to stop: 1) If all the samples in the batch
were classifier correctly. 2) If, for 20 steps, the loss has not improved, and
at least 50% were classified correctly. 3) If we had trained for 200 steps. On
average, seven steps are required, while the third rule appears in less than
1% of the examples. (iii) We used gradient clipping with a norm of one.

##  Appendix E SD knowledge and failure cases in CUB

To evaluate the efficacy of SD in generating fine-grained categories, we
conducted an analysis of SD’s capabilities using the labels from the CUB
dataset. This involved a thorough examination of all 20k images generated for
CUB. Our investigation revealed that SD faced difficulties in generating
images for seven out of the two hundred labels in CUB, as highlighted in
Figure 15. Specifically, two species (Whip poor Will and Geococcyx) failed
completely, with not a single image depicting a bird. ‘Whip poor Will’
generated images featuring whips and people, while ‘Chuck Will Widow’ captions
resulted in 31 failing images that related mainly to hunting or dogs.
Additionally, the Parakeet Auklet input rendered many images of its more
colorful relatives, the Parakeets. Some species that mention other animals in
their names resulted in mixed-up images that were still birdlike, such as the
Rhinoceros Auklet (where all cases almost contained rhinoceros attributes) and
the Fox sparrow (where 22 images contained fox-like attributes). Furthermore,
three of the generated images for Scott Oriole contained scenes from baseball
matches (the Baltimore Orioles is a baseball team). Our approach was
successful in improving image generation for all classes except one: the ‘Whip
Poor Will’ images ended up being of snakes. It appears that the specific
camouflage of the bird in question misled both SD and our method.

Ours |  |  |  |  |  |  |
---|---|---|---|---|---|---|---
SD |  |  |  |  |  |  |

(a) Chuck Will Widow (b) Geococcyx

(c) Whip poor Will (d) Rhinoceros Auklet

(e) Fox sparrow (f) Scott Oriole

(g) Parakeet Auklet

Figure 15: Examples of SD failures for the CUB classes where the output does
not represent the class as found in CUB, with our improvements on top. While
193 out of 200 bird names resulted in images of birds for SD, 6 classes were
particularly troublesome and one happened to have three baseball-related
pictures among the generations.

##  Appendix F FID results comparison to SD

To further confirm the effectiveness of our method compared to SD, we employed
the Frechet Inception Distance (FID) [19] to evaluate the similarity of the
generated images to the real images in the CUB, iNat21, and ImageNet datasets.
FID is a metric that assesses the quality of generated images by comparing
them to a baseline dataset through the analysis of activations in classifiers.
A lower FID score indicates a higher degree of resemblance between the
generated and real images. We computed FID scores using two classifier models:
one trained on ImageNet and another trained on CUB200. The FID results are
presented in Table 5. Our findings suggest that our approach produces images
that more accurately resemble the real images compared to those generated
using only SD, as demonstrated by the lower FID scores for the InceptionV3 and
CUB activations.

Dataset | Method | IncV3 | CUB / iNat
---|---|---|---
CUB200 | SD | 14.7 | 116.8
CUB200 | SD + Guidance | 13.3 | 90.6
iNat | SD | 83.7 | 225.6
iNat | SD + Guidance | 82.4 | 207.3
ImageNet | SD | 23.0 | –
ImageNet | SD + Guidance | 22.4 | –
Table 5: FID scores, for all generated datasets compared to the real dataset,
where features used for calculating the FID statistics are extracted from an
Inception-v3 classifier trained on ImageNet, and classifiers trained on CUB200
/ iNat. Lower is better.

##  Appendix G Qualitative study

In this section, we provide more qualitative results.

We show examples of ambiguous classes in Fig. 16 and Fig. 17. We note that
even after our method’s improvements, some may retain some characteristics of
the original ambiguous image. House sparrows, for example, are often depicted
in birdhouses, and Crane bird images still might depict a crane.

In Fig. 23, we show examples of coarse-grained classes from ImageNet. Images
include various animals, everyday life objects, and places. With the imagenet
classifier, we can improve fine details from dog faces to the style of a
coffee mug. Our next step is to assess fine detail abilities. We show in Fig.
18 accuracy improvements using CUB and iNat datasets. Notably, the classifier
pays careful attention to details. For instance, in the Red Sea Urchin, the
red bubble in the center is incorrect, and in the Yellow-pine Chipmunk, the
lines on his back are different.

Figure 16: Examples of ambiguous class names from CUB and iNat.

(a) Class: House Sparrow, Method: Ours using CUB guidance, Acc. 0.27.

(b) Class: House Sparrow, Method: Stable Diffusion, Acc. 0.0

(c) Class: Saltmarsh mallow, Method: iNat guidance, Acc. 0.40

(d) Class: Saltmarsh mallow, Method: SD. Acc. 0.0

(e) Class: Clown doris, Method: Ours using iNat guidance, Acc 0.0

(f) Class: Clown doris, Method: Stable Diffusion. Acc 0.0

Figure 17: Examples of ambiguous class names from ImageNet.

(a) Class: Ashcan, Method: Ours, Acc: 0.7.

(b) Class: Aschen, Method: Stable Diffusion, Acc: 0.05.

(c) Class: Bearskin, Method: Ours, Acc: 0.75.

(d) Class: Bearskin, Method: Stable Diffusion, Acc: 0.15.

(e) Class: Crane, Method: Ours, Acc: 0.75.

(f) Class: Crane, Method: Stable Diffusion, Acc: 0.25.

Figure 18: Images generated based on CUB classes. We show results with our
discriminative token and vanilla Stable Diffusion. We provide the accuracy of
the classification for each batch.

(a) Class: Florida Jay, Method: Ours using CUB guidance, Acc. 0.49.

(b) Class: Florida Jay, Method: Stable Diffusion. Acc. 0.10.

(c) Class: Fox Sparrow, Method: Ours using CUB guidance, Acc. 0.72.

(d) Class: Fox Sparrow, Method: Stable Diffusion. Acc. 0.9.

(a) Class: Red Sea Urchin, Method: iNat guidance, Acc. 0.70

(b) Class: Red Sea Urchin, Method: SD. Acc. 0.0

(c) Class: Red-bellied Squirrel, Method: iNat guidance, Acc. 0.70

(d) Class: Red-bellied Squirrel, Method: SD. Acc. 0.0

(e) Class: Tricolored Bat, Method: iNat guidance, Acc. 0.70

(f) Class: Tricolored Bat, Method: SD. Acc. 0.0

(g) Class: Yellow-pine Chipmunk, Method: iNat guidance, Acc. 0.70

(h) Class: Yellow-pine Chipmunk, Method: SD. Acc. 0.0

(a) Class: Yellow-throated Bunting, Method: iNat guidance, Acc. 0.70

(b) Class: Yellow-throated Bunting, Method: SD. Acc. 0.0

(c) Class: Monterey Indian Paintbrush, Method: iNat guidance, Acc. 0.60

(d) Class: Monterey Indian Paintbrush, Method: SD. Acc. 0.0

(e) Class: Snakelocks anemone, Method: iNat guidance, Acc. 0.70

(f) Class: Snakelocks anemone, Method: SD. Acc. 0.10

(g) Class: South American Gray Fox, Method: iNat guidance, Acc. 1.00

(h) Class: South American Gray Fox, Method: SD. Acc. 0.40

(a) Class: Red Rock Crab, Method: iNat guidance, Acc. 0.50

(b) Class: Red Rock Crab, Method: SD. Acc. 0.0

(c) Class: Philadelphia Vireo, Method: iNat guidance, Acc. 0.50

(d) Class: Philadelphia Vireo, Method: SD. Acc. 0.0

(e) Class: Asian Clam, Method: iNat guidance, Acc. 0.50

(f) Class: Asian Clam, Method: SD. Acc. 0.10

(g) Class: Sandy Stilt-puffball, Method: iNat guidance, Acc. 0.40

(h) Class: Sandy Stilt-puffball, Method: SD. Acc. 0.0

(i) Class: Black-tailed Jackrabbit, Method: iNat guidance, Acc. 0.7

(j) Class: Black-tailed Jackrabbit, Method: Stable Diffusion. Acc. 0.0

(a) Class: Scarlet Elfcup, Method: iNat guidance, Acc. 0.50

(b) Class: Scarlet Elfcup, Method: SD. Acc. 0.10

(c) Class: Six-lined Racerunner, Method: iNat guidance, Acc. 0.40

(d) Class: Six-lined Racerunner, Method: SD. Acc. 0.0

(e) Class: Goose Barnacle, Method: iNat guidance, Acc. 0.55

(f) Class: Goose Barnacle, Method: SD. Acc. 0.0

Figure 23: Images generated based on ImageNet classes. We show results with
our discriminative token and vanilla stable diffusion. We provide the accuracy
of the classification for each batch.

(a) Class: Japanese spaniel, Method: Ours, Acc: 0.6.

(b) Class: Japanese spaniel, Method: Stable Diffusion, Acc: 0.12.

(c) Class: eft, Method: Ours, Acc: 0.56.

(d) Class: eft, Method: Stable Diffusion, Acc: 0.06.

(a) Class: Robin, Method: Ours, Acc: 0.8.

(b) Class: Robin, Method: Stable Diffusion, Acc: 0.68.

(c) Class: Red-backed sandpiper, Method: Ours, Acc: 0.92.

(d) Class: Eed-backed sandpiper, Method: Stable Diffusion, Acc: 0.56.

(a) Class: Ruffed grouse, Method: Ours, Acc: 0.64.

(b) Class: Ruffed grouse, Method: Stable Diffusion, Acc: 0.12.

(c) Class: Ptarmigan, Method: Ours, Acc: 0.64.

(d) Class: Ptarmigan, Method: Stable Diffusion, Acc: 0.08.

(a) Class: Fiddler crab, Method: Ours, Acc: 0.76.

(b) Class: Fiddler crab, Method: Stable Diffusion, Acc: 0.12.

(c) Class: Hermit crab, Method: Ours, Acc: 0.4.

(d) Class: Hermit crab, Method: Stable Diffusion, Acc: 0.12.

(a) Class: Bullfrog, Method: Ours, Acc: 1.0.

(b) Class: Bullfrog, Method: Stable Diffusion, Acc: 0.24.

(c) Class: Komodo dragon, Method: Ours, Acc: 0.92.

(d) Class: Komodo dragon, Method: Stable Diffusion, Acc: 0.48.

(a) Class: black and gold garden spider, Method: Ours, Acc: 0.16.

(b) Class: Black and gold garden spider, Method: Stable Diffusion, Acc: 0.0.

(c) Class: Garden spider, Method: Ours, Acc: 0.4.

(d) Class: Garden spider, Method: Stable Diffusion, Acc: 0.28.

(a) Class: Spindle, Method: Ours, Acc: 0.12.

(b) Class: Spindle, Method: Stable Diffusion, Acc: 0.04.

(c) Class: Stage, Method: Ours, Acc: 0.88.

(d) Class: Stage, Method: Stable Diffusion, Acc: 0.48.

(a) Class: Slot, Method: Ours, Acc: 0.96.

(b) Class: Slot, Method: Stable Diffusion, Acc: 0.64.

(c) Class: Steel drum, Method: Ours, Acc: 0.28.

(d) Class: Steel drum, Method: Stable Diffusion, Acc: 0.16.

(a) Class: Bell cote, Method: Ours, Acc: 0.88.

(b) Class: Bell cote, Method: Stable Diffusion, Acc: 0.08.

(a) Class: Gong, Method: Ours, Acc: 0.68.

(b) Class: Gong, Method: Stable Diffusion, Acc: 0.44.

(c) Class: Tub, Method: Ours, Acc: 0.72.

(d) Class: Tub, Method: Stable Diffusion, Acc: 0.48.

(a) Class: Coffee mug, Method: Ours, Acc: 0.8.

(b) Class: Coffee mug, Method: Stable Diffusion, Acc: 0.16.

(c) Class: Panpipe, Method: Ours, Acc: 0.36.

(d) Class: Panpipe, Method: Stable Diffusion, Acc: 0.08.


# A Concentration Bound for Distributed Stochastic Approximation
††thanks: VB was supported by the S. S. Bhatnagar Fellowship from Council of
Scientific and Industrial Research, Government of India. The authors thank
Siddharth Chandak for a careful scrutiny of the manuscript.

Harsh Dolhare and Vivek Borkar  Dept. of Electrical Engineering
Indian Institute of Technology Bombay
Mumbai, India

###### Abstract

We revisit the classical model of Tsitsiklis, Bertsekas and Athans [10] for
distributed stochastic approximation with consensus. The main result is an
analysis of this scheme using the ‘ODE’ (for ‘Ordinary Differential
Equations’) approach to stochastic approximation, leading to a high
probability bound for the tracking error between suitably interpolated
iterates and the limiting differential equation. Several future directions
will also be highlighted.

###### Index Terms:

distributed algorithms; consensus; two time scale algorithms; ODE limit;
concentration bound

##  I Introduction

In a landmark work, Tsitsiklis, Bertsekas and Athans [10] laid down a paradigm
for distributed incremental recursions with consensus, which has been a
template for much subsequent work in distributed algorithms, particularly for
distributed optimization (see, e.g., [7]). The basic idea is to use a
classical ‘gossip’ scheme for averaging iterates across processors/agents,
with an additive perturbation given by a processor-specific stochastic
approximation. It is well known that under reasonable conditions, a stand-
alone stochastic approximation iteration asymptotically tracks a limiting
ordinary differential equation (ODE) (see, e.g., [1]). In the present
scenario, the averaging is on a faster time scale dictated by the iteration
count whereas the stochastic approximation is on a slower time scale dictated
by the stepsizes (or ‘learning parameters’) chosen. The net effect then is to
confine the limiting dynamics of the latter to the invariant subspace of the
former, i.e., the one dimensional space of constant vectors. What this
translates into is that the iterates of all the processors asymptotically
track common trajectory segments of an ‘averaged’ ODE with probability one,
which is tantamount to ‘consensus’ in a generalized sense. This interpretation
(see, e.g., section 8.4, [1], also, [6]) differs from the original approach of
[10], but gives a different and useful perspective.

Operating within this framework, our objective here is to derive an estimate
for the ‘trapping probability’, i.e., the probability that the iterates
converge to a specific asymptotically stable attractor if they are in its
domain of attraction at some time. This can be combined with finite time
estimates, if available, to give an ‘all time’ bound from time zero. The key
step is to bound the departure of suitably interpolated iterates from the
trajectory of the averaged ODE (Lemma 2 below). The remainder of the proof
then closely mimics that for the centralized stochastic approximation (section
3.1, [1]).

##  II Algorithm

Following [10], a standard distributed stochastic approximation scheme with
$M$ agents in $\Re^{d}$ can be described as follows. Consider a connected
directed graph $\mathcal{G}=\\{V,\mathcal{E}\\}$ such that $|V|=M$. Each node
of this graph represents one agent. We assume that there is a directed path
from each node of the graph to every other node, i.e. $\mathcal{G}$ is
irreducible. We are given a stochastic matrix $P=[p_{i,j}]\in\Re^{M\times M}$
compatible with $\mathcal{G}$ (i.e. the edge
$(i,j)\in\mathcal{E}\Longleftrightarrow p_{i,j}>0$), with $p_{i,j}:=$ the
weight assigned to the edge $i\rightarrow j$. At each time $n$, node $i$
updates its $d$-dimensional iterate $x^{i}(n)$ as

$x^{i}(n+1)=\sum_{j=1}^{M}p_{i,j}x^{j}(n)+a(n)\big{(}h^{i}(x^{i}(n))+\mathcal{M}^{i}(n+1)\big{)}.$
(II.1)

Here $a(n)\geq 0$ is the stepsize, $h^{i}:\Re^{d}\rightarrow\Re^{d}$, and
$\\{\mathcal{M}^{i}(n+1)\\}$ is a $\Re^{d}$-valued ‘martingale difference’
noise defined below. Define
$X(n),\widetilde{\mathcal{M}}(n+1),h(X(n))\in\mathbf{R}^{M\times d}$ by: the
$i$th row of $X(n)$ ($\widetilde{\mathcal{M}}(n+1),h(X(n))$, resp.) is
$x^{i}(n)$ ($\mathcal{M}^{i}(n+1),h^{i}(x^{i}(n))$, resp.). Then (II.1) can be
written in matrix form as

$X(n+1)=PX(n)+a(n)\left(h(X(n))+\widetilde{\mathcal{M}}(n+1)\right)$ (II.2)

Let $\pi$ be the unique stationary distribution for $P$, $\mathbf{1}$ the
vector $[1,1,\cdots,1]^{T}\in\Re^{M}$, and and $\Pi=\mathbf{1}\pi^{T}$. Define
$Q:=P-\Pi$. Then all eigenvalues of $Q$ have magnitude strictly less than 1.
It is well known [3] that this is so if and only if for every positive
definite matrix $R\in\mathbb{R}^{M\times M}$, there exits a unique positive
definite matrix $H\in\mathbb{R}^{M\times M}$ satisfying the discrete Lyapunov
equation

$Q^{T}HQ-H=-R.$ (II.3)

We take $R=I$. Let $\|\cdot\|_{H}$ denote the norm $\sqrt{x^{T}Hx}$ and also
the corresponding induced matrix norm.

######  Lemma 1.

$Q$ is an $\|\cdot\|_{H}$-norm contraction, i.e. there exists an
$\alpha\in(0,1)$ such that $\|Qx-Qy\|_{H}\leq\alpha\|x-y\|_{H}$ $\forall\
x,y$.

###### Proof.

For any $x\in\mathbb{R}^{d}$,

$\displaystyle x^{T}Q^{T}HQx=x^{T}Hx-x^{T}x$ $\displaystyle\implies$
$\displaystyle\|Qx\|^{2}_{H}=\|x\|^{2}_{H}-x^{T}x.$ (II.4)

Let $(\lambda_{i}>0,v_{i})$ denote the eigenvalue - normalized eigenvector
pairs of $H$. Then since $H>I$ in the usual order for positive definite
matrices (as is obvious from (II.3) with $R=I$), we have $\lambda_{i}\geq 1\
\forall i$. Hence

$\displaystyle\alpha\coloneqq\max_{\|x\|\neq
0}\frac{\|Qx\|_{H}}{\|x\|_{H}}=\max_{\|x\|\neq
0}\frac{\sqrt{x^{T}Q^{T}HQx}}{\sqrt{x^{T}Hx}}$ $\displaystyle=$
$\displaystyle\max_{\|x\|\neq 0}\frac{\sqrt{x^{T}(H-I)x}}{\sqrt{x^{T}Hx}}$
$\displaystyle=$ $\displaystyle\max_{\|x\|\neq
0}\frac{\sqrt{\sum_{i}(\lambda_{i}-1)\langle
x,v_{i}\rangle^{2}}}{\sqrt{\sum_{i}\lambda_{i}\langle x,v_{i}\rangle^{2}}}\ <\
1.$

∎

We now state our key assumptions.

  * •

$h^{i}$ (hence $h$) are Lipshitz, i.e. there exists a constant $L>0$ such that

$\|h(X)-h(Y)\|_{H}\leq L\|X-Y\|_{H},$

implying in particular that for a suitable $K_{1}>0$,

$\|h(X)\|_{2}\leq K_{1}(1+\|X\|_{2}).$

  * •

$\mathcal{M}^{i}(n+1)$ is a $\Re^{d}$-valued martingale difference sequence
with respect to the increasing $\sigma$-fields
$\mathcal{F}_{n}:=\sigma(X(k),\mathcal{M}(k),k\leq n)$ (i.e.,
$E\left[\mathcal{M}^{i}(n+1)|\mathcal{F}_{n}\right]=\theta:=$ the zero
vector), satisfying

$\|\widetilde{\mathcal{M}}(n+1)\|_{H}\leq K_{2}(1+\|X(n)\|).$

Furthermore, we assume that there exist constants $\kappa,C>0$ such that

$\sup_{i,j,n}E\left[e^{\kappa|\mathcal{M}_{ij}(n+1)|}\Big{|}\mathcal{F}_{n}\right]\leq
C.$ (II.5)

  * •

$\\{a(n)\\}$ is a non-negative sequence of stepsizes satisfying, for some
$c>1$,

$\sum_{n}a(n)=\infty,\;\sum_{n}a^{2}(n)<\infty$ $a(m)\leq
ca(n)\;\forall\;m\geq n.$

Furthermore, $\\{a(n)\\}$ is eventually decreasing and satisfies: If for
$T>0$, $m(n):=\min\\{k\geq n:\sum_{i=n}^{k}a(i)\geq T\\}$, then for a suitable
constant $C^{*}$,

$m(n)-n\leq C^{*}T.$ (II.6)

This condition is satisfied by $a(n)=\frac{1}{1+n},\frac{1}{1+nlogn}$, etc.,
but not, e.g., by $a(n)=\frac{1}{1+n^{2/3}}$.

We make the following key assumption:

(A1) Assume that the iterates remain a.s. bounded, i.e.,

$\sup_{n}\|X(n)\|<\infty\ \mbox{a.s.}.$ (II.7)

Suppose the ODE

$\dot{\tilde{x}}(s)=\sum_{j=1}^{M}\pi(j)h^{j}(\tilde{x}(s))$ (II.8)

has an asymptotically stable compact attractor $A$. Consider a bounded open
subset $B^{\prime}\subset\Re^{d}$ in the domain of attraction of $A$,
positively invariant under (II.8). In particular, all trajectories of (II.8)
initiated in $B^{\prime}$ converge to $A$. We also assume that a bounded open
set $\breve{B}$ containing $\tilde{B}:=\\{x:\inf_{y\in
B^{\prime}}\|x-y\|\leq\delta\\}$ shares these properties for some $\delta>0$
that we choose later. Our objective will be to show that with high
probability, the iterates $x^{i}(n),n\geq n_{0}$, remain in a small tube
around trajectory segments of (II.8) initialized in $\breve{B}$ if it is
sufficiently close to it at $n=n_{0}$ for some $n_{0}\geq 0,\ \forall i$.

We conclude this section with the remark that we can take the argument of
$h^{i}(\cdot)$ above to be $X(n)$ instead of $x^{i}(n)$ by letting it be a map
$\Re^{M\times d}\mapsto\Re^{d}$. This does not affect the analysis, but we
lose the ‘distributed computation’ viewpoint.

##  III Preliminaries

Let $B=(B^{\prime})^{M},\hat{B}:=(\breve{B})^{M}$. Suppose that
$\|X_{n_{0}}-\Pi X_{n_{0}}\|<\delta$ and $\Pi X_{n_{0}}\in B$ for some
$n_{0}\geq 0$. That these hold simultaneously is possible with probability
increasing to $1$ as $n_{0}\uparrow\infty$ because $\|X_{n_{0}}-\Pi
X_{n_{0}}\|$ $\to 0$ a.s. [6]. Fix a $T^{\prime}>0$. Define
$t(n):=\sum_{m=0}^{n}a(m),n\geq 0$, and, for $\ k\geq 1$,

$n_{k}:=\min\\{n:t(n)\geq t(n_{k-1})+T^{\prime}\\},\
\upsilon_{k}:=n_{k+1}-n_{k}.$

Define a sequence of time instants $T_{0},T_{1},T_{2},\dots$ by
$T_{m}=t(n_{m})$ and let $I_{m}:=[T_{m},T_{m+1}]$. Then $T_{m+1}-T_{m}\leq
T:=T^{\prime}+ca(0)$. Next, define a piecewise linear, continuous function
$\bar{X}(t)$, $t\geq 0$ such that $\bar{X}(t(n))=X(n),n\geq 0,$ and it is
linearly interpolated in each $I_{n}$. Let $x^{T_{m}}(s)\in\Re^{d},s\in
I_{m}$, be the unique solution to the ODE (II.8) with initial condition
$x^{T_{m}}(T_{m})=\sum_{j=1}^{M}\pi(j)x^{j}(T_{m})$. Let $\Phi_{t}$ be the
time-t flow map of the ODE (II.8) and let
$C_{T}:=\max_{t\in[0,T],x\in\bar{B}}\|h(\Phi_{t}(x))\|_{H}<\infty$. Define

$\displaystyle\rho_{k}$ $\displaystyle=$ $\displaystyle\sup_{t\in
I_{k}}\|\bar{X}(t)-\textbf{1}(x^{T_{k}})^{T}(t)\|_{H},$ (III.1)
$\displaystyle\delta_{n,m}$ $\displaystyle:=$
$\displaystyle\sum_{i=1}^{m-1}a(n+i)P^{m-1-i}\widetilde{\mathcal{M}}(t(n+i+1)).$

######  Lemma 2.

There exists a sequence $K_{T,n}^{*}>0$ and a constant $K_{T}>0$ such that
$K_{T,n}^{*}\downarrow 0$ as $n\uparrow\infty$ and for any $k\geq 0$,

$\rho_{k}\leq K_{T,k}^{*}+K_{T}\max_{\upsilon_{k}>l\geq 0}\delta_{n_{k},l}.$
(III.2)

###### Proof.

For any $n_{k}$,

$\bar{X}(t(n_{k}+1))=P\bar{X}(t(n_{k}))+a(n)\big{(}h(\bar{X}(t(n_{k})))+\widetilde{\mathcal{M}}(n_{k}+1)\big{)}.$

Iterating this through $n_{k}\leq n_{k}+m\leq n_{k+1}$,

$\displaystyle\bar{X}(t(n_{k}+m))=P^{m}\bar{X}(t(n_{k}))$ (III.3)
$\displaystyle+$
$\displaystyle\sum_{i=1}^{m-1}a(n_{k}+i)P^{m-1-i}h(\bar{X}(t(n_{k}+i)))$
$\displaystyle+$
$\displaystyle\sum_{i=1}^{m-1}a(n_{k}+i)P^{m-1-i}\widetilde{\mathcal{M}}(n_{k}+1).$

Defining $X^{T_{m}}(s)=\mathbf{1}(x^{T_{m}})^{T}(s)$,

$\displaystyle X^{T_{k}}(t(n_{k}+m))=\Pi X^{T_{k}}(t(n_{k}))$ (III.4)
$\displaystyle+$ $\displaystyle\int_{t(n_{k})}^{t(n_{k}+m)}\Pi
h(X^{T_{k}}(s))\,ds.$

Let $\lfloor s\rfloor:=\max\\{t(n):t(n)\leq s\\}$. Subtracting (III.4) from
(III.3) and using $Q^{k}=P^{k}-\Pi$, we get

$\displaystyle\bar{X}(t(n_{k}+m))-X^{T_{k}}(t(n_{k}+m))=\left(P^{m}-\Pi\right)\bar{X}(t(n_{k}))$
$\displaystyle+\sum_{i=1}^{m-1}a(n_{k}+i)P^{m-1-i}h(\bar{X}(t(n_{k}+i)))$
$\displaystyle-\int_{t(n_{k}*)}^{t(n_{k}+m)}\Pi
h(X^{T_{k}}(s))\;ds+\delta_{n_{k},m}$
$\displaystyle=Q^{m}\bar{X}(t(n_{k}))+\sum_{i=0}^{m-1}a(n_{k}+i)\Pi\big{(}h(\bar{X}(t(n_{k}+i)))$
$\displaystyle\ \ \ \ \ \ \ \ \ -\ h(X^{T_{k}}(t(n_{k}+i)))\big{)}$
$\displaystyle+\sum_{i=1}^{m-1}a(n_{k}+i)Q^{m-1-i}h(\bar{X}(t(n_{k}+i)))$
$\displaystyle-\int_{t(n_{k})}^{t(n_{k}+m)}\Pi\Big{(}h(X^{T_{k}}(s))-h(X^{T_{k}}(\lfloor
s\rfloor))\Big{)}\;ds+\delta_{n_{k},m}.$ (III.5)

Define

$z_{m}:=\|\bar{X}(t(n_{k}+m))-X^{T_{k}}(t(n_{k}+m))\|_{H}.$ (III.6)

Taking $\|\cdot\|_{H}$ norm on both sides of (III.5)and using Lemma 1,

$\displaystyle
z_{m}\leq\|Q^{m}\bar{X}(t(n_{k}))\|_{H}+\sum_{i=1}^{m-1}a(n_{k}+i)\|\Pi\|_{H}Lz_{i}$
$\displaystyle+\sum_{i=1}^{m-1}a(n_{k}+i)\alpha^{m-1-i}\|h(\bar{X}(t(n_{k}+i)))\|_{H}$
$\displaystyle+\int_{t(n_{k})}^{t(n_{k}+m)}\|\Pi\left(h(X^{T_{k}}(s))-h(X^{T_{k}}(\lfloor
s\rfloor))\right)\|_{H}ds$ $\displaystyle+\|\delta_{n_{k},m}\|_{H}.$ (III.7)

For the first term on the r.h.s.,

$\displaystyle\|Q^{m}\bar{X}(t(n_{k}))\|_{H}$ $\displaystyle=$
$\displaystyle\|Q^{m}\Big{(}\bar{X}(t(n_{k}))-\Pi\bar{X}(t(n_{k}))\Big{)}\|_{H}$
(III.8) $\displaystyle=$
$\displaystyle\|Q^{m}\Big{(}\bar{X}(t(n_{k}))-X^{T_{k}}(t(n_{k}))\Big{)}\|_{H}$
$\displaystyle\leq$ $\displaystyle\alpha^{m}z_{0}.$

For the third term,

$\displaystyle\sum_{i=1}^{m-1}a(n_{k}+i)\alpha^{m-1-i}\|h(\bar{X}(t(n_{k}+i)))\|_{H}$
$\displaystyle\leq\sum_{i=1}^{m-1}a(n_{k}+i)\alpha^{m-1-i}\|h(X^{T_{k}}(t(n_{k}+i)))\|_{H}$
$\displaystyle+\sum_{i=1}^{m-1}a(n_{k}+i)\alpha^{m-1-i}\times$
$\displaystyle\|h(\bar{X}(t(n_{k}+i)))-h(X^{T_{k}}(t(n_{k}+i)))\|_{H}$
$\displaystyle\leq
C_{T}\sum_{i=0}^{m-1}a(n+i)\alpha^{m-1-i}+L\sum_{i=0}^{m-1}a(n_{k}+i)\alpha^{m-1-i}z_{i}.$
(III.9)

By the Cauchy-Schwarz inequality,

$\displaystyle\sum_{i=1}^{m-1}a(n+i)\alpha^{m-1-i}$ $\displaystyle\leq$
$\displaystyle\sqrt{\sum_{i=1}^{m-1}a^{2}(n_{k}+i)\sum_{i=1}^{m-1}\alpha^{2i}}$
$\displaystyle\leq$ $\displaystyle\sqrt{\frac{\sum_{i\geq
1}a^{2}(n_{k}+i)}{1-\alpha^{2}}}.$

Note that if $t(n_{k}+m)\leq t\leq t(n_{k}+m+1)$, then

$\displaystyle\|X^{T_{m}}(t)-X^{T_{m}}(t(n_{k}+m))\|_{H}$
$\displaystyle\leq\left\|\int_{t(n_{k}+m)}^{t}h(X^{T_{m}}(s))ds\right\|_{H}$
$\displaystyle\leq C_{T}(t-t(n_{k}+m))$ $\displaystyle\leq C_{T}a(n_{k}+m).$

Now consider the fourth term.

$\displaystyle\int_{t(n_{k})}^{t(n_{k}+m)}\|\Pi\left(h(X^{T_{k}}(s))-h(X^{T_{k}}(\lfloor
s\rfloor))\right)\|_{H}ds$
$\displaystyle\leq\int_{t(n_{k})}^{t(n_{k}+m)}L\|\Pi\|_{H}\|X^{T_{k}}(s)-X^{T_{k}}(\lfloor
s\rfloor)\|_{H}ds$ $\displaystyle\leq
L\|\Pi\|_{H}\sum_{i=1}^{m-1}\int_{t(n_{k}+i)}^{t(n_{k}+i+1)}\|X^{T_{k}}(s)-X^{T_{k}}(t(n_{k}+i))\|_{H}$
$\displaystyle\leq L\|\Pi\|_{H}C_{T}\sum_{i=1}^{m-1}a^{2}(n_{k}+i).$ (III.10)

Combining (III), (III.8), (III) and (III),

$z_{m}\leq K_{T,m}+\sum_{i=1}^{m-1}q_{i}z_{i}.$ (III.11)

Here, for $b(n):=\sum_{m\geq n}a(n)^{2}$,

$\displaystyle K_{T,k}$
$\displaystyle=LC_{T}\|\Pi\|_{H}b(n_{k})+C_{T}\sqrt{\frac{b(n_{k})}{1-\alpha^{2}}}+\max_{\upsilon_{k}>l\geq
0}\|\delta_{n_{k},l}\|_{H},$ $\displaystyle q_{i}=$ $\displaystyle
La(n+i)(1+\|\Pi\|_{H})\ \forall\ i\neq 0,$ $\displaystyle q_{0}=$
$\displaystyle La(n)(1+\|\Pi\|_{H})+1.$

Also, $\sum_{i=0}^{m-1}q_{i}\leq LT(1+\|\Pi\|_{H})+1$. Using discrete Gronwall
inequality,

$\displaystyle z_{m}$ $\displaystyle\leq$ $\displaystyle
K_{T,n_{k}}\exp\left(\sum_{i=0}^{m-1}q_{i}\right)$ $\displaystyle\implies
z_{m}$ $\displaystyle\leq$ $\displaystyle
K_{T,n_{k}}\exp(LT(1+\|\Pi\|_{H}+1)).$

For $t(n_{k}+m)\leq t\leq t(n_{k}+m+1)$, we have

$\bar{X}(t)=\lambda\bar{X}(t(n_{k}+m))+(1-\lambda)\bar{X}t(n_{k}+m+1)$

for some $\lambda\in[0,1]$. Then a routine calculation as in [1], pp. 15-16,
shows that

$\rho_{k}:=\sup_{t\in I_{k}}\|\bar{X}(t)-X^{T_{k}}(t)\|_{H}\leq
K_{T,k}^{*}+K_{T}\max_{\upsilon_{k}>l\geq 0}\delta_{n_{k},l}$ (III.12)

for suitably defined $K_{T,k}^{*}$ and $K_{T}$, where $K_{T,k}^{*}\to 0$ as
$n_{k}\uparrow\infty$. ∎

Let $V:\hat{B}\rightarrow[0,\infty)$ be a continuously differentiable function
such that $\lim_{x\to\partial\hat{B}}V(x)=\infty$, $\dot{V}:=\langle\nabla
V,h\rangle:\hat{B}\rightarrow\mathbf{R}$ is non-positive,
$A:=\\{x:V(x)=0\\}=\\{x:\dot{V}(x)=0\\}.$ That is, V is a local Lyapunov
function associated with the attractor $A$ of (II.8). ($V$ exists by the
converse Lyapunov theorem [4].)

Fix $\epsilon\geq 0$ such that the set
$\overline{A^{\epsilon}}:=\\{x:V(x)\leq\epsilon\\}\subset B$. Fix some $T>0$
and let $\Delta>0$ satisfy

$\Delta<\min_{x\in\hat{B}\backslash A^{\epsilon}}[V(x)-V(\Phi_{T}(x))].$
(III.13)

For any set $D$ and $\delta>0$, denote the $\delta$-neighbourhood of $D$ by
$N^{(\delta)}(D)$. Next, pick $\delta\geq 0$ in the definition of $\hat{B}$
such that $N^{(\delta)}(A^{\epsilon})\subset B$ and furthermore, if $x\in B$
and $\|x-y\|_{H}<\delta$, then $|V(x)-V(y)|<\frac{\Delta}{3}$. By increasing
$T$ if necessary, assume that for any trajectory $x(\cdot)$ of (II.8)
initiated in $\bar{B^{\prime}}$, $x(T)$ is at least $\delta$ away from
$\partial B^{\prime}$. Now we state our main result. Define

$\tilde{\delta}:=\frac{\delta}{2K_{T}\sqrt{\Lambda(H)M^{3}d}}.$

######  Theorem 3.

There exist constants $C_{1},C_{2},\tau>0$ such that if $n_{0}$ is
‘sufficiently large’, then

$\displaystyle P\Big{(}\bar{X}(t)\in
N^{(\delta)}\left(A^{\epsilon+\frac{2\Delta}{3}}\right)\;\forall\;t\geq
T_{0}+\tau\big{|}$ $\displaystyle\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\|X_{n_{0}}-\Pi X_{n_{0}}\|<\delta,\Pi X_{n_{0}}\in B\Big{)}$
$\displaystyle\geq 1-2M^{2}dC^{*}\sum_{n\geq
n_{0}}ne^{-\frac{D\tilde{\delta}^{2}}{a(n)}}\ \ \mbox{if}\
\tilde{\delta}\in\Big{(}0,\frac{CT}{\varepsilon}\Big{]},$ $\displaystyle\ \ \
\ 1-2M^{2}dC^{*}\sum_{n\geq n_{0}}ne^{-\frac{D\tilde{\delta}}{a(n)}}\ \
\mbox{otherwise}.$

We prove this in the next section.

##  IV Proof of the Main result

Suppose $\rho_{k}<\delta\;\forall\;k\geq 0$. If $\Pi\bar{X}(T_{0})\in
B\backslash A^{\epsilon}$, then $X^{T_{0}}(t)\in B$ for $t\in[T_{0},T_{1}]$
and because $\Pi\bar{X}(T_{0})=X^{T_{0}}(T_{0})$ and (III.13), we have

$V(X^{T_{0}}(T_{1}))\leq V(X^{T_{0}}(T_{0}))-\Delta.$

Since $\|\bar{X}(t)-X^{T_{0}}(t)\|_{H}<\delta,t\in[T_{0},T_{1}]$, we have

$V(\bar{X}(T_{1}))\leq V(\bar{X}(T_{0}))-\frac{\Delta}{3}$

and $\bar{X}(t)\in\hat{B},t\in[T_{0},T_{1}]$. Also, since $\Pi Q=Q\Pi=$ the
zero matrix, it follows from (II.3) that $\|\Pi x\|_{H}=\|\Pi x\|$. Clearly
$\Pi X^{T_{0}}(t)=X^{T_{0}}(t)$. Thus we also have
$\|\Pi\bar{X}(t)-X^{T_{0}}(t)\|_{H}<\delta$. If
$\Pi\bar{X}(T_{1})\in\hat{B}\backslash A^{\epsilon}$ then, the same argument
can be repeated. But since $V(\bar{X}(T_{m}))$ cannot decrease indefinitely,
there exists some $m_{0}$ such that $\Pi\bar{X}(T_{m_{0}})\in A^{\epsilon}$.
In fact,

$\tau:=\frac{3(\max_{x\in\bar{B}}V(x)-\epsilon)}{\Delta}(T+1)\Longrightarrow
T_{m_{0}}\leq T_{0}+\tau.$

Thus $X^{T_{m_{0}}}(T_{m_{0}})=\Pi\bar{X}(T_{m_{0}})\in A^{\epsilon}$,
implying $X^{T_{m_{0}}}(t)\in A^{\epsilon}$ for $t\in I_{m_{0}}$. Therefore
$\bar{X}(T_{m_{0}+1})\in A^{\epsilon+\frac{\Delta}{3}}$. Again, because
$\|\bar{X}(T_{m_{0}+1})-X^{T_{m_{0}+1}}(T_{m_{0}+1})\|_{H}<\delta$, we have
$X^{T_{m_{0}+1}}(T_{m_{0}+1})=\Pi\bar{X}(T_{m_{0}+1})\in
A^{\epsilon+\frac{2\Delta}{3}}$. Now there are two possibilities: either
$X^{T_{m_{0}+1}}(T_{m_{0}+1})\in A^{\epsilon}$ or
$X^{T_{m_{0}+1}}(T_{m_{0}+1})\in A^{\epsilon+\frac{2\Delta}{3}}\backslash
A^{\epsilon}$. In the former case, $X^{T_{m_{0}+1}}(t)\in A^{\epsilon}$ for
$t\in I_{{m_{0}}+1}$, implying $X^{T_{m_{0}+1}}(T_{m_{0}+2})\in A^{\epsilon}$.
Since $\|\bar{X}(T_{m_{0}+2})-X^{T_{m_{0}+1}}(T_{m_{0}+2})\|_{H}<\delta$,
$\bar{X}(T_{m_{0}+2})\in A^{\epsilon+\frac{\Delta}{3}}$. Otherwise, if
$X^{T_{m_{0}+1}}(T_{m_{0}+1})\in A^{\epsilon+\frac{2\Delta}{3}}\backslash
A^{\epsilon}$, $X^{T_{m_{0}+1}}(t)\in A^{\epsilon+\frac{\Delta}{3}}$ on
$I_{{m_{0}}+1}$ and there will be a drop of $\Delta$ in $V$ along the
trajectory of ODE from $T_{m_{0}+1}$ to $T_{m_{0}+2}$. Therefore
$X^{T_{m_{0}+1}}(T_{m_{0}+2})\in A^{\epsilon-\frac{\Delta}{3}}\subset
A^{\epsilon}$. This again implies that $\bar{X}(T_{m_{0}+2})\in
A^{\epsilon+\frac{\Delta}{3}}$. This argument can be repeated. Thus we can
conclude that if for some $n_{0}$, $\Pi X(n_{0})\in B$ and
$\rho_{k}<\delta\;\forall\;k\geq 0$, then there exists some $m_{0}$ such that
$X^{T_{m_{0}+k}}(t)\in A^{\epsilon+\frac{2\Delta}{3}}$ on $I_{m_{0}+k}$ for
all $k\geq 0$, implying that $\bar{X}(t)\in
N^{(\delta)}(A^{\epsilon+\frac{2\Delta}{3}})$ for $t\geq T_{m_{0}}$, hence for
$t\geq T_{0}+\tau$. Let
$\mathcal{B}_{k}:=\mathcal{B}_{-1}\cap\\{\rho_{m}<\delta\ \forall\ 0\leq m\leq
k\\}$, with $\mathcal{B}_{-1}:=\\{\|X_{n_{0}}-\Pi X_{n_{0}}\|<\delta,\ \Pi
X_{n_{0}}\in B\\}$. Then by the foregoing,

$\displaystyle P\left(\bar{X}(t)\in
N^{(\delta)}(A^{\epsilon+\frac{2\Delta}{3}})\ \forall\;t\geq
T_{0}+\tau\Big{|}\mathcal{B}_{-1}\right)$ $\displaystyle\geq
P\big{(}\rho_{k}<\delta\ \forall\;k\geq 0|\mathcal{B}_{-1}\big{)}$ (IV.1)

Thus we have:

######  Lemma 4.

$\displaystyle P\big{(}\rho_{k}<\delta\ \forall\;k\geq
0|\mathcal{B}_{-1}\big{)}$ $\displaystyle\geq
1-\sum_{k=0}^{\infty}P\big{(}\rho_{k}\geq\delta|\mathcal{B}_{k-1}\big{)}.$
(IV.2)

This follows as in [1], p. 25. Recall that $\upsilon_{k}:=n_{k+1}-n_{k}$. If
we select $n_{0}$ large enough so that

$K_{T,k}<\frac{\delta}{2}\ \ \forall\;k\geq 0,$ (IV.3)

then the inequality $\rho_{k}\geq\delta$ and Lemma 2 together imply that
$\max_{\upsilon_{k}>l\geq 0}\|\delta_{n_{k},l}\|_{H}>\frac{\delta}{2K_{T}}$.
Thus

$P\left(\rho_{k}\geq\delta|\mathcal{B}_{k-1}\right)\leq
P\left(\max_{\upsilon_{k}>l\geq
0}\|\delta_{n_{k},l}\|_{H}>\frac{\delta}{2K_{T}}\Big{|}\mathcal{B}_{k-1}\right)$

The next lemma establishes a useful bound.

######  Lemma 5.

There exists a constant $K_{3}$ such that for any $t\in I_{k}$,

$\|\bar{X}(t)\|_{2}\leq K_{3}\left(1+\|\bar{X}(T_{k})\|_{2}\right).$

###### Proof.

We have

$X(n_{k}+1)=PX(n_{k})+a(n_{k})\big{(}h(X(n_{k}))+\widetilde{\mathcal{M}}(n_{k}+1)\big{)}.$

Taking $\|\cdot\|_{2}$ norm and using the linear growth property of the
function $h$ and of the martingale difference noise,

$\displaystyle\|X(n_{k}+1)\|_{2}\leq\|P\|_{2}\|X(n_{k})\|_{2}$
$\displaystyle+a(n_{k})\big{(}K_{1}(1+\|X(n_{k})\|_{2})+K_{2}(1+\|X(n_{k})\|_{2})\big{)}.$

But because $P$ is a stochastic matrix, $\|P\|_{2}\leq 1$, so

$\displaystyle\|X(n_{k}+1)\|_{2}\leq\|X(n_{k})\|_{2}(1+K^{{}^{\prime}}a(n_{k}))+a(n_{k})K^{{}^{\prime}},$

where $K^{{}^{\prime}}:=K_{1}+K_{2}$. Iterating this for $n_{k}\leq j\leq
n_{m+1}$ and using the fact that $1+aK^{{}^{\prime}}\leq\exp(aK^{\prime})$ and
the fact that if $j<n_{k+1}$, then
$a(n_{k})+a(n_{k}+1)+\dots+a(j-1)<t(n_{k+1})-t(n_{k})<T$, we get

$\displaystyle\|X(j)\|_{2}\leq$
$\displaystyle\|X(n_{k})\|_{2}\exp(K^{{}^{\prime}}T)\ +$ $\displaystyle\ \
K^{\prime}T\exp(K^{{}^{\prime}}T)$ $\displaystyle\implies$ $\displaystyle\
\|X(j)\|_{2}\leq K_{3}(1+\|X(n_{k})\|_{2})$

for some constant $K_{3}>0$. ∎

Let $[\cdots]_{a,b}$ denote the $(a,b)$th term of the matrix ‘$\cdots$’ and
let $\Lambda(H):=\lambda_{max}(H)/\lambda_{min}(H)$. Then for any
$G\in\Re^{M\times d}$,

$\|G\|_{H}\leq\sqrt{\Lambda(H)}\|G\|_{F}\leq\sqrt{\Lambda(H)Md}\max_{i,j}[G]$

where $\|\cdot\|_{F}$ is the Frobenius norm. Thus we have

$\displaystyle P\left(\max_{\upsilon_{k}>l\geq
0}\|\delta_{n_{k},l}\|_{H}>\frac{\delta}{2K_{T}}\Big{|}\mathcal{B}_{k-1}\right)$
$\displaystyle\leq P\left(\max_{\upsilon_{k}>l\geq
0}\max_{a,b}|[\delta_{n_{k},l}]_{a,b}|>\frac{\delta}{2K_{T}\sqrt{\Lambda(H)Md}}\Big{|}\mathcal{B}_{k-1}\right)$
$\displaystyle\leq\sum_{a,b}P\left(\max_{\upsilon_{k}>l\geq
0}|[\delta_{n_{k},l}]_{a,b}|>\frac{\delta}{2K_{T}\sqrt{\Lambda(H)Md}}\Big{|}\mathcal{B}_{k-1}\right).$
(IV.4)

But

$\displaystyle|[\delta_{n_{k},l}]_{a,b}|$ $\displaystyle=$
$\displaystyle\left|\sum_{i=0}^{l-1}a(n_{k}+i)\sum_{c=1}^{M}[P^{l-1-i}]_{a,c}[\mathcal{M}]_{c,b}(n_{k}+i+1)\right|$
$\displaystyle\leq$
$\displaystyle\sum_{c=1}^{M}\left|\sum_{i=0}^{l-1}a(n_{k}+i)[P^{l-1-i}]_{a,c}[\mathcal{M}]_{c,b}(n_{k}+i+1)\right|$
$\displaystyle\leq$ $\displaystyle M\max_{1\leq c\leq
M}\Bigg{|}\sum_{i=0}^{l-1}a(n_{k}+i)[P^{l-1-i}]_{a,c}\times$ $\displaystyle\ \
\ \ \ \ \ \ \ \ [\mathcal{M}]_{c,b}(n_{k}+i+1)\Bigg{|}.$

Combining this with (IV),

$\displaystyle P\left(\max_{\upsilon_{k}>l\geq
0}\|\delta_{n_{k},l}\|_{H}>\frac{\delta}{2K_{T}}\ \Big{|}\
\mathcal{B}_{k-1}\right)\ \leq$
$\displaystyle\sum_{a,b,c}\sum_{i=0}^{\upsilon_{k}-1}P\Bigg{(}\Big{|}\sum_{i=0}^{l-1}a(n_{k}+i)[P^{l-1-i}]_{a,c}\mathcal{M}_{c,b}(n_{k}+i+1)\Big{|}$
$\displaystyle\ \ \ \ \ \ \ \ \ >\
\frac{\delta}{2K_{T}\sqrt{\Lambda(H)M^{3}d}}\ \Big{|}\
\mathcal{B}_{k-1}\Bigg{)}.$

Let
$S_{m}:=\sum_{i=0}^{m-1}a(n_{k}+i)[P^{l-1-i}]_{a,c}[\mathcal{M}]_{c,b}(n_{k}+i+1)$.
Then $\\{(S_{m},\mathcal{F}_{n_{k}+m}),0\leq m\leq l\\}$ is a martingale and
$\mathcal{B}_{n_{k}+m}\in\mathcal{F}_{n_{k}+m}.$ Let $Y_{1}=S_{1}$ and
$Y_{m}=S_{m}-S_{m-1}\;\forall\;l\geq m>1$. Then

$\displaystyle|Y_{i}|$
$\displaystyle=|a(n_{k}+i)[P^{l-1-i}]_{a,c}[\mathcal{M}]_{c,b}(n_{k}+i+1)|$
$\displaystyle\leq a(n_{k}+i)|[\mathcal{M}]_{c,b}(n_{k}+i+1)|$
$\displaystyle\leq a(n_{k}+i)\|\mathcal{M}(n_{k}+i+1)\|_{\infty}$
$\displaystyle\leq da(n_{k}+i)\|\mathcal{M}(n_{k}+i+1)\|_{2}$
$\displaystyle\leq da(n_{k}+i)K_{2}(1+\|X(n_{k}+i+1)\|_{2})$
$\displaystyle\leq da(n_{k}+i)K_{2}(1+K_{3}(1+\|\bar{X}(T_{k})\|_{2}))$
$\displaystyle\leq K_{4}da(n_{k}+i),$

where $K_{4}:=K_{2}(1+K_{3}(1+K_{5}))$ for $K_{5}=sup_{X\in\hat{B}}\|X\|_{2}$.

Now we use the conditional version of the inequality for martingale arrays
from the Appendix with $A_{m,l}=a(m)p_{a,c}^{l-m-1},\gamma_{1}=T$ and
$\gamma_{2}=c,w(m)=a(n_{k})$ for $0\leq m\leq l$. Recall that

$\tilde{\delta}:=\frac{\delta}{2K_{T}\sqrt{\Lambda(H)M^{3}d}}.$

Then for a constant $D>0$ depending on $\kappa,C,T,c$,

$\displaystyle\sum_{a,b,c,l}P\Bigg{(}\left|\sum_{i=0}^{l-1}a(n_{k}+i)[P^{l-1-i}]_{a,c}[\mathcal{M}]_{c,b}(n_{k}+i+1)\
\right|$ $\displaystyle\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ >\tilde{\delta}\ \Big{|}\
\mathcal{B}_{k-1}\Bigg{)}$ $\displaystyle\leq
2M^{2}d(n_{k+1}-n_{k})e^{-\frac{D\tilde{\delta}^{2}}{a(n_{k})}}\ \ \mbox{if}\
\tilde{\delta}\in\Big{(}0,\frac{CT}{\kappa}\Big{]},$ $\displaystyle\ \ \
2M^{2}d(n_{k+1}-n_{k})e^{-\frac{D\tilde{\delta}}{a(n_{k})}}\ \
\mbox{otherwise}$ $\displaystyle\leq
2M^{2}dC^{*}n_{k}e^{-\frac{D\tilde{\delta}^{2}}{a(n_{k})}}\ \ \mbox{if}\
\tilde{\delta}\in\Big{(}0,\frac{CT}{\kappa}\Big{]},$ $\displaystyle\ \ \
2M^{2}dC^{*}n_{k}e^{-\frac{D\tilde{\delta}}{a(n_{k})}}\ \ \mbox{otherwise},$

where the summations over $a,b,c,l$ are over their respective ranges and
$C^{*}$ is as in (II.6).

Combining this with (IV) and (4) we get,

$\displaystyle P\Big{(}\bar{X}(t)\in
N^{(\delta)}\left(A^{\epsilon+\frac{2\Delta}{3}}\right)\;\forall\;t\geq
T_{0}+\tau\Big{|}$ $\displaystyle\ \ \ \ \ \ \ \ \ \ \ \ \|X_{n_{0}}-\Pi
X_{n_{0}}\|<\delta,\Pi X_{n_{0}}\in B\Big{)}$ $\displaystyle\geq
1-2M^{2}dC^{*}\sum_{n\geq n_{0}}ne^{-\frac{D\tilde{\delta}^{2}}{a(n)}}\ \
\mbox{if}\ \tilde{\delta}\in\Big{(}0,\frac{CT}{\kappa}\Big{]}$ (IV.5)
$\displaystyle\ \ \ \ 1-2M^{2}dC^{*}\sum_{n\geq
n_{0}}ne^{-\frac{D\tilde{\delta}}{a(n)}}\ \ \mbox{otherwise}.$ (IV.6)

This completes the proof of the main result.

##  V Future directions

This is only a first step towards a finer analysis of this class of
algorithms. In fact there have been other variants of the basic scheme (II.1),
one of the important strands being the case when instead of a weighted average
of the iterate over all neighbors, each processor polls one of the neighbors
with a prescribed probability and takes an average of its own iterate with
that of the selected neighbor, see, e.g., [7]. The development above does not
carry over to this case automatically and will have to now include analysis of
a product of random stochastic matrices.

A further extension of the basic paradigm itself has been to replace the
averaging operator by a nonlinear map so that asymptotically, the ODE limit of
the stochastic approximation gets confined to the set of its fixed points [6].
This idea has been used for distributed projected stochastic approximation
where the projection is also enforced by a distributed scheme [8]. It will be
challenging and useful to extend the foregoing analysis to cover such
scenarios.

Finally, there is always scope to tighten the bounds above, as we have been
rather generous with them at various points.

APPENDIX

Let $\\{\mathcal{M}_{n}\\}$ be a real valued martingale difference sequence
with respect to an increasing family of $\sigma$-fields
$\\{\mathcal{F}_{n}\\}$. Assume that there exist $\varepsilon,C>0$ such that

$E\left[e^{\varepsilon|\mathcal{M}_{n}|}\Big{|}\mathcal{F}_{n-1}\right]\leq C\
\ \forall\;n\geq 1,\mbox{a.s.}$

Let $S_{n}:=\sum_{m=1}^{n}\xi_{m,n}\mathcal{M}_{m}$, where $\xi_{m,n},\ m\leq
n,$, for each $n$, are a.s. bounded $\\{\mathcal{F}_{n}\\}$-previsible random
variables, i.e., $\xi_{m,n}$ is $\mathcal{F}_{m-1}$-measurable $\forall\;m\geq
1$, and $|\xi_{m,n}|\leq A_{m,n}$ a.s. for some constant $A_{m,n}$,
$\forall\;m,n$. Suppose

$\sum_{m=1}^{n}A_{m,n}\leq\gamma_{1},\ \max_{1\leq m\leq
n}A_{m,n}\leq\gamma_{2}\omega(n),$

for some $\gamma_{i},\omega(n)>0,\ i=1,2;n\geq 1$. Then we have:

######  Theorem 6.

There exists a constant $D>0$ depending on
$\varepsilon,C,\gamma_{1},\gamma_{2}$ such that for $\epsilon>0$,

$\displaystyle P\left(|S_{n}|>\epsilon\right)$ $\displaystyle\leq$
$\displaystyle 2e^{-\frac{D\epsilon^{2}}{\omega(n)}},\ \ \mbox{if}\
\epsilon\in\left(0,\frac{C\gamma_{1}}{\varepsilon}\right],$ (V.2)
$\displaystyle 2e^{-\frac{D\epsilon}{\omega(n)}},\ \ \mbox{otherwise.}$

This is a variant of Theorem 1.1 of [5]. See [9], Theorem A.1, pp. 21-23, for
details.

## References

  * [1] Borkar, V.S., 2022. Stochastic approximation: a dynamical systems viewpoint (2nd ed.). Hindustan Publishing Agency, New Delhi, and Springer Nature.
  * [2] Chandak, S.; Borkar, V. S. and Dodhia, P., 2022. Concentration of contractive stochastic approximation and reinforcement learning. Stochastic Systems (online).
  * [3] Kailath, T., 1980. Linear systems. Prentice-Hall.
  * [4] Krasovskii, N. N., 1963. Stability of motion. Stanford Uni. Press.
  * [5] Liu, Q. and Watbled, F., 2009. Exponential inequalities for martingales and asymptotic properties of the free energy of directed polymers in random environment. Stochastic Processes and Their Applications, 119(10), 3101-3132.
  * [6] Mathkar, A. S. and Borkar, V. S., 2016. Nonlinear gossip. SIAM J. Control and Optim., 54(3), 1535-1557.
  * [7] Nedic, A., 2015. Convergence rate of distributed averaging dynamics and optimization in networks. Foundations and Trends® in Systems and Control, 2(1), pp.1-100.
  * [8] Shah, S. M. and Borkar, V. S., 2018. Distributed stochastic approximation with local projections. SIAM J. Optimization, 28(4), 3375-3401.
  * [9] Thoppe, G. and Borkar, V. S., 2019. A concentration bound for stochastic approximation via Alekseev’s formula. Stochastic Systems, 9(1), 1-26.
  * [10] Tsitsiklis, J., Bertsekas, D. and Athans, M., 1986. Distributed asynchronous deterministic and stochastic gradient optimization algorithms. IEEE Transactions on Automatic Control, 31(9), 803-812.