# A Simple Long-Tailed Recognition Baseline via Vision-Language Model

Teli Ma1, Shijie Geng1, Mengmeng Wang1, Jing Shao2, Jiasen Lu3
Hongsheng Li4, Peng Gao†1, Yu Qiao1
1Shanghai Artificial Intelligence Laboratory 2SenseTime Research
3PRIOR@Allen Institute for AI 4The Chinese University of Hong Kong
{mateli, gaopeng<EMAIL_ADDRESS>
###### Abstract

The visual world naturally exhibits a long-tailed distribution of open
classes, which poses great challenges to modern visual systems. Existing
approaches either perform class re-balancing strategies or directly improve
network modules to address the problem. However, they still train models with
a finite set of predefined labels, limiting their supervision information and
restricting their transferability to novel instances. Recent advances in
large-scale contrastive visual-language pretraining shed light on a new
pathway for visual recognition. With open-vocabulary supervisions, pretrained
contrastive vision-language models learn powerful multimodal representations
that are promising to handle data deficiency and unseen concepts. By
calculating the semantic similarity between visual and text inputs, visual
recognition is converted to a vision-language matching problem. Inspired by
this, we propose BALLAD to leverage contrastive vision-language models for
long-tailed recognition. We first continue pretraining the vision-language
backbone through contrastive learning on a specific long-tailed target
dataset. Afterward, we freeze the backbone and further employ an additional
adapter layer to enhance the representations of tail classes on balanced
training samples built with re-sampling strategies. Extensive experiments have
been conducted on three popular long-tailed recognition benchmarks. As a
result, our simple and effective approach sets the new state-of-the-art
performances and outperforms competitive baselines with a large margin. Code
is released at https://github.com/gaopengcuhk/BALLAD.

Figure 1: Comparison with the state-of-the-art approaches on ImageNet-LT.
BALLAD with ResNet-50 visual backbone outperforms state-of-the-art models
which have more complex backbones and longer training epochs by a large margin
(up to +7.2% improvement on overall accuracy compared with PaCo [10]),
especially for categories without abundant training examples. BALLAD with
ResNet-50$\times$16 achieves a new state-of-the-art performance of 76.5% top-1
accuracy on ImageNet-LT benchmark dataset. (RN50: ResNet-50, RN50$\times$16:
the EfficientNet method with 16$\times$ compute of ResNet-50, RNX50:
ResNeXt-50, RNX101: ResNeXt-101.)

##  1 Introduction

During past years, visual recognition tasks, such as image classification [58,
21, 65], object detection [53, 36], semantic segmentation [42, 5, 74], and
instance segmentation [20, 24, 40] have been significantly improved. The
performance gains can be largely attributed to the availability of large-scale
high-quality datasets [12, 38, 33]. However, the problem of data imbalance has
inevitably emerged since real-world data often abide by a long-tailed
distribution (_e.g_., Pareto distribution[49] or Zipf’s law [78]). In other
words, a few head classes dominate the majority of training examples, whereas
many rare or fine-grained classes only have limited relevant data points.

To alleviate the issue, previous efforts either carefully create more balanced
datasets (_e.g_., ImageNet [12], MSCOCO [38], and Kinetics-400 [31]) with
human labors or develop more robust algorithms to handle data imbalance.
However, since the former is notoriously laborious and expensive, many
researchers have been devoted to the latter. Formally, long-tailed recognition
(LTR) is a research field seeking robust models that 1) are resistant to
significant imbalanced class distribution; 2) can deal with few-shot learning
of tail classes. Many methods [73] have been proposed for solving LTR
problems. According to the core technical contributions, they can be divided
into two categories. Methods in the first line focus on class re-balancing
strategies [44, 22, 70, 29] such as data re-sampling, loss re-weighting, and
logit adjustment. The second category focuses on improving network modules
[10, 30, 72, 54, 59, 9, 75] by classifier designing, decoupled training, and
representation learning. While these methods have achieved significant
progress, the performance of LTR remains unsatisfactory. When delving deeper
into the utilization of the existing imbalance datasets, we have observed that
almost all previous efforts are confined to a predetermined manner which
designs models entirely relying on the visual modality. That is to say, they
totally ignore the semantic features of the raw label text, which may be a
promising solution to exert additional supervision on inadequate data sources.
Therefore, this paper explores whether language modality can be effective and
complementary information for this task. In the meantime, we could broaden
generalization abilities to few-shot categories and zero-shot novel instances.

Figure 2: Overview of our BALLAD framework. In Phase A, we keep pretraining
the text and image branches of the vision-language backbone on long-tailed
data. After Phase A, head classes typically achieve good enough classification
performance, whereas tail classes are still far from perfect. During Phase B,
a linear adapter is adopted to further train the vision-language backbone on
balanced training samples. As a result, tail classes enjoy a performance boost
while head classes slightly increase or maintain their original classification
accuracy.  represents training with parameter update while  represents
freezing parameters.

Recently, contrastive vision-language models such as CLIP [51] and ALIGN [26]
brought a breath of fresh air into the vision community. They learn to align
vision and language representations with a contrastive loss given large-scale
noisy image-text pairs collected from the web. The powerful visual-language
representations obtained from pretraining significantly improve the zero-shot
classification performance in open-vocabulary settings without any additional
annotations. Motivated by the success of contrastive vision-language models
and the curiosity of the language effect mentioned above, we directly test
CLIP on LTR datasets under its zero-shot setting. Surprisingly, the results
are balanced on many-shots ($59.4\%$), medium-shots ($57.5\%$), and low-shots
($57.6\%$) subsets of ImageNet-LT [41] and the overall performance ($58.2\%$)
is comparable to the state-of-the-art [10]. From which we see the great
potential of the multimodality solution for LTR. To further improve the
performance while keep the capability of dealing with data imbalance, an
intuitive way is to finetune the vision-language models on LTR datasets.
However, we find it only brings a slight gain. Therefore, the core task of our
work becomes how to design an effective recipe for training vision-language
models under the circumstances of long-tailed distribution.

Specifically, in this paper, we design a simple framework based on contrastive
vision-language models for LTR. The training procedure of the framework is
broken into two phases from the perspective of distribution skewness: A)
utilizing abundant annotations from LTR datasets; B) tackling few-shot
learning of tail classes on balanced data built with re-sampling strategies.
In Phase A, we continue pretraining CLIP backbone on a specific LTR dataset
through contrastive learning. It enables our framework to fully exploit
available training examples and update visual-language representations on a
new domain. To further facilitate the few-shot learning of tail classes,
during Phase B, we freeze the CLIP backbone and employ an auxiliary linear
adapter for finetuning on re-balanced training samples. The adapter
dynamically combines fixed Phase-A and finetuned Phase-B features via a
residual connection to refine the visual representations of tail classes.
Compared with finetuning the whole CLIP backbone directly, the linear adapter
reduces the number of learnable parameters and thus prevents the potential
overfitting of few-shot setups. According to Figure 1, our framework clearly
achieves better performances than state-of-the-art LTR approaches. The
improvements are especially significant for few-shot and medium-shot classes,
demonstrating our approach’s great capability of handling class imbalance.
Since our framework solves the data imbalance via a linear adapter, we name it
as BALLAD (BALanced Linear ADapter), which implies the harmony of head and
tail classes. Our contributions are three folds:

  * •

We point out the shortcomings of training with fixed class labels and propose
to leverage language modality via contrastive vision-language backbone to
facilitate long-tailed recognition.

  * •

We develop the BALLAD framework consisting of two phases to handle head and
tail classes successively. Specifically, we keep training the visual and
language branches of the pretrained vision-language model simultaneously at
the first stage. Then we adopt a linear adapter to tackle tail classes with
vision-language parameters frozen.

  * •

We conduct extensive experiments to demonstrate the effectiveness of BALLAD.
Our simple baseline achieves the new state-of-the-art performances on all
benchmarks, outperforming the old paradigm by $16.5$ points maximally on
ImageNet-LT.

##  2 Related Work

Contrastive Vision-Language Model.  Contrastive representation learning has
been widely adopted to fulfill self-supervised pretraining in various AI
domains[6, 19, 3, 4, 47, 17]. Recently, the intersection of vision and
language [1, 46, 68, 16, 32, 7, 55] also experienced a revolution sparked by
contrastive representation learning. Contrastive vision-language models like
CLIP [51] and ALIGN [26] demonstrate promising zero-shot performances on
various visual search and recognition tasks. Learning directly from natural
language supervisions that contain rich visual concepts, they are very
flexible and robust to distribution variations across different domains. The
success of CLIP and ALIGN has enlightened many downstream vision-language
tasks. For instance, DeCLIP [35] proposes to utilize self-, multi-view, and
nearest-neighbor supervisions among the image-text pairs for data efficient
pretraining of CLIP. On visual classification tasks, CLIP-Adapter [15] argues
that fine-tuning contrastive vision-language models with linear adapters is a
better alternative to prompt tuning. For video related tasks, VideoCLIP [66]
performs contrastive pretraining with video-text pairs for zero-shot video-
text understanding. ActionCLIP [61] presents a new “pretrain, prompt and fine-
tune” paradigm leveraging pretrained vision-language models for zero-shot/few-
shot action recognition. CLIP-It [45] designs a language-guided multimodal
transformer based on CLIP to address query-focused video summarization.
Moreover, CLIPort [57] combines CLIP with Transporter [69] to endow a robot
with the ability of semantic understanding and spatial perception. In this
paper, we demonstrate that contrastive vision-language models can also
facilitate visual recognition under long-tailed class distribution setups if
properly trained.

Long-Tailed Recognition.  Long-tailed recognition [73] is a practical and
challenging problem in vision domain. General visual models will suffer from
severe performance degradation under such imbalanced class distributions. A
great number of approaches [25, 48, 71, 13, 67, 44, 10, 63, 54, 9] have been
proposed to address LTR from different perspectives. An intuitive solution is
to directly re-balance the number of training samples across all classes [30,
75]. However, naively adjusting the skewness of training samples may lead to
the overfitting of tail classes. Better alternatives include loss re-weighting
[37, 29, 22] and logit adjustment [44, 70] based on label frequencies. Though
efficacious for long-tailed distribution, above methods all sacrifice the
performance of head classes at varying levels. To address the limitations,
researchers turn to explore new network architectures and training paradigms.
Typically, long-tail recognition models contain two key components – feature
extractor and classifier. For each component, there are corresponding
approaches by either designing better classifier [39, 59, 64] or learning
reliable representations [41, 77]. In terms of new training frameworks,
existing efforts seek to divide a one-stage training paradigm into two stages.
For example, decoupled training approaches [30, 28] conduct representation
learning and classifier training in a separate manner. Furthermore, ensemble
learning schemes [75, 72] first learn multiple experts with different data
sub-groups and then merge their complementary knowledge to handle LTR. In
contrast, our BALLAD first utilizes abundant long-tailed data to refine
visual-language representations on a new target domain. Then we apply a
lightweight linear adapter to encourage fine-grained representation learning
from balanced samples. The two phases successively handle the learning of head
and tail classes and ensure a better balanced performance across all classes.

##  3 Our Method

In this section, we first briefly revisit how contrastive vision-language
models leverage contrastive objectives to achieve efficient and scalable
multimodal representation learning. Moreover, we formally present BALLAD
framework and discuss the advantages of the proposed two-stage representation
learning for long-tailed class distributions.

###  3.1 Contrastive Vision-Language Model

Contrastive vision-language models such as CLIP [51] and ALIGN [26] typically
follow a dual-encoder architecture with a language encoder
$\mathcal{L}_{\mathrm{enc}}$ and a visual encoder
$\mathcal{V}_{\mathrm{enc}}$. Given an input image $\bm{I}$,
$\mathcal{V}_{\mathrm{enc}}$ is adopted to extract the visual feature for
$\bm{I}$:
$\bm{f}_{v}=\mathcal{V}_{\mathrm{enc}}(\bm{I})\in\mathbb{R}^{d_{v}}$.
Likewise, $\mathcal{L}_{\mathrm{enc}}$ is applied to encode an input text
sequence $\bm{T}$ into its corresponding text feature:
$\bm{f}_{l}=\mathcal{L}_{\mathrm{enc}}(\bm{T})\in\mathbb{R}^{d_{l}}$. After
extracting the feature for each modality, two transformation matrices
$\mathbf{W}_{v}\in\mathbb{R}^{d_{v}\times d}$ and
$\mathbf{W}_{l}\in\mathbb{R}^{d_{l}\times d}$ are employed to project the
original visual and text features into a shared embedding space:

$\mathbf{v}=\frac{\mathbf{W}_{v}^{\top}\bm{f}_{v}}{\|\mathbf{W}_{v}^{\top}\bm{f}_{v}\|},\
\ \
\mathbf{u}=\frac{\mathbf{W}_{l}^{\top}\bm{f}_{l}}{\|\mathbf{W}_{l}^{\top}\bm{f}_{l}\|},$
(1)

where $\mathbf{v}$ and $\mathbf{u}$ are both $d$-dimension normalized vectors
in the joint multimodal space. During pretraining, contrastive vision-language
models learn to align image-text pairs inside a batch. The overall training
objective consists of matching losses from two different directions, _i.e._ ,
$\mathscr{L}_{v\rightarrow l}$ for text retrieval and
$\mathscr{L}_{l\rightarrow v}$ for image retrieval. They both maximize the
scores of matched pairs while minimize that of unmatched ones:

$\displaystyle\mathscr{L}_{v\rightarrow l}$
$\displaystyle=-\frac{1}{N}\sum_{i}^{N}\log\frac{\exp\left(\mathbf{v}_{i}^{\top}\mathbf{u}_{i}/\tau\right)}{\sum_{j=1}^{N}\exp\left(\mathbf{v}_{i}^{\top}\mathbf{u}_{j}/\tau\right)},$
(2) $\displaystyle\mathscr{L}_{l\rightarrow v}$
$\displaystyle=-\frac{1}{N}\sum_{i}^{N}\log\frac{\exp\left(\mathbf{u}_{i}^{\top}\mathbf{v}_{i}/\tau\right)}{\sum_{j=1}^{N}\exp\left(\mathbf{u}_{i}^{\top}\mathbf{v}_{j}/\tau\right)},$
(3)

where $\tau$ denotes the temperature hyperparameter and $N$ represents the
number of image-text pairs in the batch.

Trained with large-scale image-text pairs under the open-vocabulary settings,
contrastive vision-language models achieve powerful multimodal representations
and naturally possess the capability of zero-shot visual recognition. A
collection of text descriptions following templates like ”a photo of a
{CLASS}” is created for candidate classes in target datasets to perform zero-
shot prediction. If we represent the normalized test image feature as
$\mathbf{v}$ and all normalized text description features as
$\\{\mathbf{u}_{1},\cdots,\mathbf{u}_{K}\\}$, we can thus compute the class
probability of the test image as below:

$p_{i}=\frac{\exp\left(\mathbf{v}^{\top}\mathbf{u}_{i}\right)/\tau}{\sum_{j=1}^{K}\exp\left(\mathbf{v}^{\top}\mathbf{u}_{j}\right)/\tau},$
(4)

where $p_{i}$ represents the probability for class $i$, and $K$ stands for the
total number of candidate classes. Finally, the text label with the highest
probability is selected as the prediction.

###  3.2 Balanced Linear Adapter

As stated in Section 1, contrastive vision-language models obtain balanced
performance for head and tail classes, whereas traditional approaches like
PaCo [10] suffer from lower performance of tail classes owing to the
deficiency of training samples. Inspired by the zero-shot ability of
contrastive vision-language models, we choose CLIP as our backbone for long-
tailed recognition. The observation in Section 4.3.2 also encourages us to
decouple the training of long-tailed data into two phases. To be specific, the
first phase (Phase A) fully utilizes available training data and ensures the
performance for classes with abundant examples, then the second phase (Phase
B) focuses on improving the few-shot learning of tail classes. Note that LWS
[30] also adopts a decoupled training framework. However, LWS decouples the
training of representation and classifier into two stages. In contrast, our
two phases are for long-tailed and balanced training samples respectively and
both phases conduct representation refinement with contrastive loss.

Phase A.  Recently, Gururangan _et al_. [18] shows that keeping domain-
adaptive and task-adaptive model pretraining can largely improve the
performances on target NLP tasks. Similarly, for our Phase A, we find that
continuing the pretraining of contrastive vision-language backbone on long-
tailed target dataset also benefits the learning of classes with abundant
examples. In this way, Phase A can make full use of available training data
regardless of its skewness. Since we focus on classifying input images into
text labels, the pretraining of Phase A directly follows the loss defined in
Equation (2). As shown in Figure 2, Phase A updates the representations of
both text and image encoders on a new domain. After Phase A, head classes
typically achieve good performance while tail classes still require another
stage of balanced training.

Phase B.  Tail classes are short of training examples and under the few-shot
settings. Directly training the whole vision-language backbone may easily
overfit to them and lead to performance degradation. Inspired by parameter-
efficient adapter modules [23], we freeze the vision-language backbone
obtained from Phase A and utilize an additional linear adapter layer to help
our model refine its visual-language representation on those infrequent
classes. As shown in Figure 2, the text features would remain the same as
Phase A. The only difference lies in the image features. If we assume the
original image feature to be $\bm{f}$, the weight matrix and bias of the
linear adapter as $\mathbf{W}\in\mathbb{R}^{d\times d}$ and
$\mathbf{b}\in\mathbb{R}^{d}$, then we can represent the refined image feature
$\bm{f}^{\star}$ as

$\bm{f}^{\star}=\lambda\cdot\operatorname{ReLU}\left(\mathbf{W}^{\top}\bm{f}+\mathbf{b}\right)+(1-\lambda)\cdot\bm{f},$
(5)

where $\lambda$ indicates the residual factor to dynamically combine Phase-B
fine-tuned image features with the original image features of Phase A.

To avoid the Phase-B training from biasing towards head classes, we also adopt
class-balanced sampling strategy [30] to construct a balanced group of
training samples. Suppose there are $K$ classes that constitute a total of $N$
training samples in the target dataset. We can represent the number of
training samples for class $j$ as $n_{j}$ and thus have
$N=\sum_{j=1}^{K}n_{j}$. If we assume these classes are already sorted in a
decreasing order, then a long-tailed distribution implies $n_{i}\geq n_{j}$ if
$i<j$ and $n_{1}\gg n_{K}$. For class-balanced sampling, we define the
probability of sampling each data point from class $j$ to be
$q_{j}=\frac{1}{K}$. In other words, to construct a balanced group of training
samples, we will first uniformly choose a class out of the $K$ candidates and
then sample one data point from the selected class. Finally, we perform Phase
B finetuning with $\mathscr{L}_{v\rightarrow l}$ on the balanced training
data.

##  4 Experiments

###  4.1 Experiment Setup

Datasets.  We conduct our experiments on three long-tailed benchmark datasets,
namely ImageNet-LT [41], Places-LT [41], and CIFAR100-LT [2]. ImageNet-LT and
Places-LT were first introduced in [41] for long-tailed recognition research.
ImageNet-LT is a long-tailed dataset with 1,000 categories sampled from the
original ImageNet [12] following the Pareto distribution with a power value of
$\alpha=6$. There are 115.8K images in the training split, with maximally
1,280 images per class and minimally 5 images per class. The testing split
maintains the same as the original ImageNet [12], where samples per class are
balanced. Places-LT is a long-tailed version of the original Places2 Database
[76]. The training split of Places-LT contains with 184.5K images from 365
categories, with 4,980 images maximally per class and minimally 5 images per
class. For the testing split, the images of each class is also balanced with
100 images per class. CIFAR100-LT [2] are created by long-tailed imbalance
technique [11] which reduces training examples per class based on an
exponential decay function. In this paper, we directly use the version from
[63] with an imbalance ratio $\rho$ of $100$. The training split contains 50K
images from 100 categories, while the testing split has a uniform 100 images
for each class.

Implementation Details.  We use CLIP as the contrastive vision-language
backbone in all experiments. For the visual branch of CLIP, we vary among
ResNet-50, ResNet-100, ViT-B/16, and ResNet-50$\times$16, which is 16$\times$
computation cost of ResNet-50 following the style of EfficientNet as
introduced in [51]. The ResNet-50 is leveraged for all ablation studies by
default unless specified. We use SGD as the optimizer for all experiments with
a momentum of $0.9$. The batch size is set to $512$. We adopt cosine learning
rate schedule to decay learning rates. The initial learning rate of CLIP
finetuning is set to $1\times 10^{-5}$ for both the visual and language
encoders, while the learning rate of linear adapter is set to $0.2$ at the
start. For data pre-processing, images are resized to $224\times 224$ unless
the ResNet-50$\times$16 visual backbone, which utilizes an image size of
$384\times 384$. Crop and random horizontal flip are also adopted to augment
the original images for robustness considerations. For BALLAD, we train Phase
A for 50 epochs and and Phase B for 10 epochs by default unless specified. For
the hyperparameters, we set the residual factor $\lambda$ to $0.2$ and the
temperature $\tau$ to $1.0$. The feature dimensions of ResNet-50, ResNet-101,
ResNet-50$\times$16 and ViT-B/16 are $1024,512,768,512$ respectively.

Evaluation Metrics.  We evaluate the models for long-tailed recognition on the
balanced test splits and report the commonly used top-1 classification
accuracy of all classes. Following [30], we divide these classes into three
subsets – many-shot, medium-shot, and few-shot categories. Specifically, many-
shot, medium-shot, and few-shot are decided according to the amount of
instances in each category, namely more than 100 images, 20-100 images, and
less than 20 images, respectively.

Method | Backbone | #Epochs | Many | Medium | Few | All
---|---|---|---|---|---|---
$\tau$-normalized [30] | ResNet-50 | 90 | 56.6 | 44.2 | 27.4 | 46.7
ResNet-101 | 90 | 59.4 | 47.0 | 30.6 | 49.6
ResNet-152 | 90 | 59.6 | 47.5 | 32.2 | 50.1
ResNeXt-50 | 90 | 59.1 | 46.9 | 30.7 | 49.4
ResNeXt-101 | 90 | 59.1 | 47.0 | 31.7 | 49.6
ResNeXt-152 | 90 | 62.2 | 50.1 | 35.8 | 52.8
LWS [30] | ResNet-50 | 90 | 57.1 | 45.2 | 29.3 | 47.7
ResNet-101 | 90 | 60.1 | 47.6 | 31.2 | 50.2
ResNet-152 | 90 | 60.6 | 47.8 | 31.4 | 50.5
ResNeXt-50 | 90 | 60.2 | 47.2 | 30.3 | 49.9
ResNeXt-101 | 90 | 60.5 | 47.2 | 31.2 | 50.1
ResNeXt-152 | 90 | 63.5 | 50.4 | 34.2 | 53.3
ResLT [9] | ResNeXt-50 | 180 | 63.0 | 50.5 | 35.5 | 52.9
ResNeXt-101 | 180 | 63.3 | 53.3 | 40.3 | 55.1
Balanced Softmax [52] | ResNet-50 | 400 | 66.7 | 52.9 | 33.0 | 55.0
ResNeXt-50 | 400 | 67.7 | 53.8 | 34.2 | 56.2
ResNeXt-101 | 400 | 69.2 | 55.8 | 36.3 | 58.0
RIDE$\dagger$ [62] | ResNet-50 | 100 | 66.2 | 52.3 | 36.5 | 55.4
ResNeXt-50 | 100 | 68.2 | 53.8 | 36.0 | 56.8
PaCo$\ddagger$ [10] | ResNet-50 | 400 | 65.0 | 55.7 | 38.2 | 57.0
ResNeXt-50 | 400 | 67.5 | 56.9 | 36.7 | 58.2
ResNeXt-101 | 400 | 68.2 | 58.7 | 41.0 | 60.0
BALLAD | ResNet-50 | 50+10 | 71.0 | 66.3 | 59.5 | 67.2 (+7.2)
ResNet-101 | 50+10 | 74.7 | 69.1 | 63.3 | 70.5 (+10.5)
ViT-B/16 | 50+10 | 79.1 | 74.5 | 69.8 | 75.7 (+15.7)
ResNet-50$\times$16 | 50+10 | 81.1 | 75.6 | 67.0 |  76.5 (+16.5)

Table 1: Long-tailed recognition accuracy on ImageNet-LT for different methods
and backbones. The red colored numbers represent the improvement of overall
accuracy compared with the state-of-the-art performance (PaCo with $60.0$%
overall accuracy). $\dagger$: RIDE uses 4 experts. $\ddagger$: the state-of-
the-art model.

###  4.2 Performance Comparison

In this section, we compare the performance of BALLAD with long-tailed
recognition approaches that report state-of-the-art results on three benchmark
datasets, _i.e._ , ImageNet-LT, Places-LT, and CIFAR100-LT.

ImageNet-LT.  Table 1 shows the long-tailed recognition results on ImageNet-
LT. We present BALLAD variants with ResNet-50, ResNet-101,
ResNet-50$\times$16, and ViT-B/16 as the visual backbone. From the table, we
observe that with only $50+10$ epochs ($50$ epochs for Phase A and $10$ epochs
for Phase B), our smallest BALLAD variant with ResNet-50 visual backbone can
surpass the largest model of the state-of-the-art PaCo [10] using ResNeXt-101
by $+7.2\%$. When gradually increasing the size of visual backbone, we find
the performance of BALLAD also enjoys an improvement. It is worth noting that
BALLAD with ResNet-50$\times$16 achieves an accuracy of $76.5\%$, which
outperforms other state-of-the-art models with a large margin.

Method | Backbone | #Pretrain | Many | Medium | Few | All
---|---|---|---|---|---|---
OLTR [41] | ResNet-152 | Y | 44.7 | 37.0 | 25.3 | 35.9
cRT [30] | ResNet-152 | Y | 42 | 37.6 | 24.9 | 36.7
$\tau$-normalized [30] | ResNet-152 | Y | 37.8 | 40.7 | 31.8 | 37.9
LWS [30] | ResNet-152 | Y | 40.6 | 39.1 | 28.6 | 37.6
Balanced Softmax [52] | ResNet-152 | Y | 42.0 | 39.3 | 30.5 | 38.6
ResLT [9] | ResNet-152 | Y | 39.8 | 43.6 | 31.4 | 39.8
PaCo [10] | ResNet-152 | Y | 37.5 | 47.2 | 33.9 | 41.2
PaCo$\dagger$ [10] | ResNet-152 | Y | 36.1 | 47.9 | 35.3 | 41.2
BALLAD | ResNet-50 | N | 46.7 | 48.0 | 42.7 | 46.5 (+5.3)
ResNet-101 | N | 48.0 | 48.6 | 46.0 | 47.9 (+6.7)
ViT-B/16 | N | 49.3 | 50.2 | 48.4 |  49.5 (+8.3)
ResNet-50$\times$16 | N | 49.4 | 50.5 | 46.6 | 49.3 (+8.1)

Table 2: Long-tailed recognition accuracy on Places-LT for different methods.
The red colored numbers represent improvement of overall accuracy compared
with the state-of-the-art performance (PaCo with $41.2$% overall accuracy).
#Pretrain: whether pretrain visual backbone on full ImageNet-2012 or not.
$\dagger$: PaCo variant trained with RandAugment [8].

Places-LT.  We further evaluate BALLAD on Places-LT dataset and report the
results in Table 2. It is a commonly used scheme of previous approaches to
pretrain their models on ImageNet-2012 full dataset first to enrich the visual
representation before finetuning on Places-LT. However, BALLAD can directly
perform training on Places-LT thanks to the additional language representation
of contrastive vision-language models. As shown in Table 2, BALLAD with
ResNet-50 visual backbone achieves $46.5\%$ accuracy for all categories, which
beats the state-of-the-art model PaCo with ResNet-152 by $+5.3\%$. This shows
BALLAD can not only achieve better performance with smaller visual backbone
but also save a great amount of training time by skipping the ImageNet
pretraining.

Method | Backbone | Many | Medium | Few | All
---|---|---|---|---|---
OLTR [41] | ResNet-32 | 61.8 | 41.4 | 17.6 | 41.2
LDAM+DRW [2] | ResNet-32 | 61.5 | 41.7 | 20.2 | 42.0
$\tau$-normalized [30] | ResNet-32 | 65.7 | 43.6 | 17.3 | 43.2
cRT [30] | ResNet-32 | 64.0 | 44.8 | 18.1 | 43.3
RIDE [62] | ResNet-32 | 69.3 | 49.3 | 26.0 | 49.1
TADE [72] | ResNet-32 | 65.4 | 49.3 | 29.3 | 49.8
BALLAD | ResNet-50 | 62.4 | 52.3 | 38.2 | 51.6 (+1.8)
ResNet-101 | 69.5 | 59.3 | 47.1 | 59.2 (+9.4)
ViT-B/16 | 84.9 | 79.7 | 67.3 |  77.8 (+28.0)
ResNet-50$\times$16 | 74.6 | 62.8 | 52.0 | 63.7 (+13.9)

Table 3: Long-tailed recognition performance comparison on CIFAR100-LT with an
imbalance ratio of $100$. The red numbers represent the improvement of overall
accuracy compared with the state-of-the-art performance (TADE with $49.8$%
overall accuracy).

CIFAR100-LT.  We also evaluate the models on CIFAR100-LT and show their
performances in Table 3. As reported in the table, BALLAD outperforms the
state-of-the-art expert-based ensemble methods RIDE [63] and TADE [72] by
$+28.7\%$ and $+28.0\%$, respectively.

###  4.3 Ablation Studies

In this section, we conduct extensive ablation studies to validate the design
choices of BALLAD from three aspects. We first explore how to best utilize
vision-language backbone for finetuning. Moreover, we shows the effectiveness
of linear adapter and how to make use of linear adapter for better
performance. Finally, we demonstrate where and how to conduct data balancing.

####  4.3.1 Vision-Language Models

We conduct ablations to demonstrate the effectiveness of vision-language
backbones as introduced in Section 3.

The Effectiveness of Pretrained Weights.  In Table 4, we validate the
effectiveness of pretrained CLIP weights compared with random initialized
visual and language weights. All the four ablations are conducted on Phase A
without data balancing for 50 epochs. The large gaps between random and
pretrained CLIP initialization demonstrate the advantage of utilizing
pretrained contrastive vision-language models. Besides, we find that visual
encoder has much more influence than text encoder on the performance as random
initialized vision encoder drops the accuracy close to zero. Note that poor
performance of random initialization is primarily attributed to short training
periods and pretrained vision-language weights fastening the convergence
largely.

Vision | Language | Many | Medium | Few | All
---|---|---|---|---|---
random | random | 0.3 | 0.0 | 0.0 | 0.1
random | CLIP | 0.3 | 0.0 | 0.0 | 0.1
CLIP | random | 36.8 | 2.9 | 0.0 | 15.6
CLIP | CLIP | 75.5 | 56.3 | 41.0 | 61.6
Table 4: Ablations of pretrained vision-language weights on ImageNet-LT dataset. CLIP means using pre-trained weights as initialization and random represents random initialization. Vision | Language | Many | Medium | Few | All
---|---|---|---|---|---
$\times$ | $\times$ | 59.4 | 57.5 | 57.6 | 58.2
$\surd$ | $\times$ | 70.4 | 65.4 | 58.0 | 66.3
$\times$ | $\surd$ | 70.6 | 65.4 | 55.9 | 66.1
$\surd$ | $\surd$ | 71.3 | 65.4 | 54.1 | 66.1
Table 5: Different methods of finetuning CLIP on ImageNet-LT. ”$\surd$” means
finetuning and ”$\times$” means freezing the parameters of model. Vision and
Language denotes the visual and text encoders of CLIP respectively. All models
are finetuned for $50$ epochs.

Finetune the Vision-Language Model.  To empirically discover how to utilize
contrastive vision-language models, we probe the finetuning process by
freezing the pre-trained image encoder and text encoder respectively. When
both encoders are frozen, the model directly perform zero-shot predictions.
From Table 5, we can easily find the following pattern – as more components
are finetuned in CLIP, more accuracy improvement is obtained for many-shot
categories whereas more accuracy drop happens in few-shot division. We
hypothesize it is because the many-shot classes dominate the visual feature
space during finetuning. Therefore, for Phase A, it is necessary to adapt CLIP
on specific long-tailed dataset as much as possible, and we choose to finetune
both the vision and language branches of CLIP.

Visual Backbones. We try CLIP with different visual backbones to explore its
influence on final performance of BALLAD. We report the Phase A results of
different backbones in Figure 3 on both ImageNet-LT and Places-LT benchmarks.
When the visual backbone becomes deeper and larger, the finetuned performance
is also gradually improved for all, many-shot, and medium-shot categories.
Surprisingly, the Vision Transformer structure [14] achieves the best accuracy
in few-shot subset, probably owing to multi-head self-attention mechanism’s
ability in capturing minor features.

(a) ImageNet-LT (b) Places-LT.

Figure 3: Comparisons between several visual backbones for ImageNet-LT (left)
and Places-LT (right).

####  4.3.2 Linear Adapter

We validate the effectiveness of adopting linear adapter in Phase B and
explore the key factors that determines the performance of linear adapter.

The Effectiveness of Linear Adapter.  We design ablations to demonstrate the
influence of linear adapter. First, we freeze the parameters of CLIP and
finetune the linear adapter for $10$ epochs to mix the original zero-shot
visual embedding with the corresponding finetuned visual features via residual
connection. As illustrated in Figure 4, the simple $10$-epoch training
improves the performance from $58.2\%$ to $61.8\%$ even without data
balancing. Moreover, we finetune both the visual and language encoders of CLIP
for $50$ epochs and then finetune the linear adapter for another $10$ epochs
with CLIP parameters fixed. Compared with an equal $60$-epoch training scheme
of finetuning the visual and language encoder of the CLIP, an extra $10$-epoch
finetuning of linear adapter based on $50$-epoch finetuning of CLIP backbone
can further boost the top-1 accuracy from $66.4\%$ to $67.2\%$.

Figure 4: Ablations of effectiveness of Linear Adapter and decouple
finetuning. Z-CLIP: zero-shot CLIP model; Z-CLIP+A: finetune adapter based on
zero-shot CLIP; CLIP: directly finetune CLIP; Joint-CLIP+A: jointly finetune
CLIP and adapter; De-CLIP+A: the BALLAD style which decouples the CLIP and
adapter finetuning into two phases.

V-Adapter | L-Adapter | Many | Medium | Few | All
---|---|---|---|---|---
$\surd$ | $\times$ | 71.0 | 66.3 | 59.5 | 67.2
$\times$ | $\surd$ | 71.0 | 66.2 | 59.0 | 67.0
$\surd$ | $\surd$ | 70.6 | 66.2 | 58.4 | 66.8

Table 6: Variants of linear adapter. V-Adapter and L-Adapter represents using
linear adapter layer to adapt visual and language encoders respectively. All
results are trained on ImageNet-LT for $10$ epochs.

Should the Finetuning of CLIP and Linear Adapter be Decoupled?  As mentioned
in Section 3 and illustrated in Figure 2, we decouple the training process
into two phases – in Phase A, we train both the vision and language encoder of
CLIP based on pre-trained weights; in Phase B, we freeze the parameters of
visual and language encoders while only finetuning the linear adapter. An
alternative scheme is to jointly train the CLIP and linear adapter rather than
decoupling the training processes. According to Figure 4, joint training of
CLIP and linear adapter (_Joint-CLIP+A_) leads to a $0.4\%$ accuracy drop
compared with directly finetuning CLIP without adapter (_CLIP_). In contrast,
the decoupled training of CLIP and linear adapter (_De-CLIP+A_) can largely
boost the accuracy from $66.0\%$ to $67.2\%$ and the ascent mainly comes from
tail classes, which is up to $6.0\%$. We visualize the joint and decoupling
training schemes using t-SNE [60] and present the results in the
supplementary. Compared with joint training, decoupled training better
separates the tail-class feature embeddings from head-classes. This
demonstrates that the proposed decoupled training of vision-language model and
adapter is effective to handle long-tailed distribution.

Variants of Linear Adapter.  Since CLIP has dual encoders, the auxiliary
linear adapter could be added to either or both of the two branches. As
reported in Table 6, we try linear adapter for adapting visual and language
encoders respectively. From the table, we can find that applying the linear
adapter to the visual branch of CLIP achieves the best overall performance and
is the optimal choice.

Figure 5: The top-1 accuracy on ImageNet-LT with different values of residual
factor $\lambda$ in Phase B of BALLAD.

Hyperparameters of the Linear Adapter.  Moreover, we explore the influence of
linear adapter’s residual factor $\lambda$. $\lambda$ determines the
importance of new knowledge obtained from finetuning the linear adapter. Note
that when $\lambda$ equals to $1.0$, the classification is fully determined by
the adapted image features. We explore different values of $\lambda$ from
$0.0$ to $1.0$ and conduct the ablations of Phase B finetuning on ImageNet-LT.
As shown in Figure 5, the best performance of linear adapter can be obtained
when $\lambda$ is around $0.2$, with a top-1 accuracy of $67.1\%$ on ImageNet-
LT. The empirical results reveal the knowledge of finetuned CLIP is already
good enough to handle most cases, a slight and balanced adaptation would
further improve the performance.

####  4.3.3 Balancing Methods

Balancing methods can alleviate the severe performance degradation due to
class imbalance. In this section, we explore different balancing methods for
BALLAD to reveal two significant problems: 1) where to utilize balancing
methods, and 2) which balancing methods to apply.

Where to balance.  Here, we compare balancing the long-tailed data
distribution on either or both of two phases. The experiments are performed on
ImageNet-LT and Places-LT datasets with ResNet-50-backboned CLIP. As mentioned
earlier, many-shot categories dominate the feature space of long-tailed
distribution. The performance drops of many-shot categories on both datasets,
as reported in Table 7, suggest that balancing during Phase A tends to
sacrifice many-shot representations. Since Phase A is mainly designed for
updating representations on a new domain, we thereby abandon Phase-A data
balancing. When applying balancing strategies to Phase B alone, BALLAD can
achieve a more balanced performance for different shots and improve the
overall top-1 accuracy thanks to the rich features learned from Phase A.

Dataset | Balance | Many | Medium | Few | All
---|---|---|---|---|---
Phase A | Phase B
ImageNet-LT | $\times$ | $\times$ | 77.3 | 57.4 | 39.0 | 62.6
$\surd$ | $\times$ | 76.6 | 58.4 | 42.7 | 63.3
$\surd$ | $\surd$ | 70.7 | 66.2 | 58.5 | 66.9
$\times$ | $\surd$ | 71.0 | 66.3 | 59.5 | 67.2
Places-LT | $\times$ | $\times$ | 52.7 | 32.9 | 23.4 | 38.2
$\surd$ | $\times$ | 51.3 | 33.2 | 25.5 | 38.2
$\surd$ | $\surd$ | 44.6 | 46.7 | 44.1 | 45.5
$\times$ | $\surd$ | 46.7 | 48.0 | 42.7 | 46.5

Table 7: Where to employ balance strategies ablations. On both ImageNet-LT and
Places-LT, balance only in Phase B make BALLAD perform the best.

Balance Methods | Many | Medium | Few | All
---|---|---|---|---
Class-balanced | 71.0 | 66.3 | 59.5 | 67.2
Square-root | 75.2 | 62.8 | 50.9 | 66.0
Mix-balanced | 72.6 | 64.9 | 59.1 | 67.1

Table 8: Comparison of different balanced sampling strategies on ImageNet-LT.

How to balance.  Furthermore, we explore different sampling strategies
including class-balanced sampling, square-root sampling and mix-balanced
sampling for Phase B. Class-balanced sampling samples the categories from
original dataset in equal probability rather than the natural instance-
balanced sampling which selects instances regardless of classes. The process
can be decoupled into two steps – first selecting classes equally from the
list of categories and then randomly sampling a data point from the selected
class. Square-root sampling [43] first computes the square-root of the number
of head classes, then re-normalize and conduct sampling according to the
resulting distribution. Mix-balanced sampling combines the instance-balanced
sampling and class-balanced sampling, thus takes advantage of both strategies
to avoid overfitting at early epochs and underfitting at late epochs.
Motivated by the [30], we adopt a soft version of mix-balanced sampling to
dynamically interpolates between instance-balanced sampling and class-balanced
sampling as learning progresses. As shown in Table 8, class-balanced sampling
can best benefit _medium-shot_ and _few-shot_ categories. Thus we adopt class-
balanced sampling as the balancing method of BALLAD.

##  5 Conclusion

In this paper, we proposed BALLAD which tackles long-tailed recognition by
leveraging contrastive vision-language models. We decouple BALLAD into two
phases for training with long-tailed and balanced samples respectively. We
first continue pretraining with contrastive loss to fully utilize abundant
data to update visual-language representation on specific domains. After that,
we employ an auxiliary linear adapter to refine the visual representation of
tail classes. We hope our simple BALLAD baseline could stimulate more future
researches on exploring vision-language models for long-tailed recognition.

## References

  * [1] Stanislaw Antol, Aishwarya Agrawal, Jiasen Lu, Margaret Mitchell, Dhruv Batra, C Lawrence Zitnick, and Devi Parikh.  Vqa: Visual question answering.  In Proceedings of the IEEE international conference on computer vision, pages 2425–2433, 2015.
  * [2] Kaidi Cao, Colin Wei, Adrien Gaidon, Nikos Arechiga, and Tengyu Ma.  Learning imbalanced datasets with label-distribution-aware margin loss.  In Advances in Neural Information Processing Systems, pages 1567–1578, 2019.
  * [3] Mathilde Caron, Ishan Misra, Julien Mairal, Priya Goyal, Piotr Bojanowski, and Armand Joulin.  Unsupervised learning of visual features by contrasting cluster assignments.  In Advances in Neural Information Processing Systems, 2020.
  * [4] Mathilde Caron, Hugo Touvron, Ishan Misra, Hervé Jégou, Julien Mairal, Piotr Bojanowski, and Armand Joulin.  Emerging properties in self-supervised vision transformers.  In Proceedings of the International Conference on Computer Vision (ICCV), 2021.
  * [5] Liang-Chieh Chen, George Papandreou, Iasonas Kokkinos, Kevin Murphy, and Alan L Yuille.  Deeplab: Semantic image segmentation with deep convolutional nets, atrous convolution, and fully connected crfs.  IEEE transactions on pattern analysis and machine intelligence, 40(4):834–848, 2017.
  * [6] Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton.  A simple framework for contrastive learning of visual representations.  In International conference on machine learning, pages 1597–1607. PMLR, 2020.
  * [7] Yen-Chun Chen, Linjie Li, Licheng Yu, Ahmed El Kholy, Faisal Ahmed, Zhe Gan, Yu Cheng, and Jingjing Liu.  Uniter: Learning universal image-text representations.  2019\.
  * [8] Ekin Dogus Cubuk, Barret Zoph, Jon Shlens, and Quoc Le.  Randaugment: Practical automated data augmentation with a reduced search space.  In Advances in Neural Information Processing Systems, 2020.
  * [9] Jiequan Cui, Shu Liu, Zhuotao Tian, Zhisheng Zhong, and Jiaya Jia.  Reslt: Residual learning for long-tailed recognition.  arXiv preprint arXiv:2101.10633, 2021.
  * [10] Jiequan Cui, Zhisheng Zhong, Shu Liu, Bei Yu, and Jiaya Jia.  Parametric contrastive learning.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 715–724, 2021.
  * [11] Yin Cui, Menglin Jia, Tsung-Yi Lin, Yang Song, and Serge Belongie.  Class-balanced loss based on effective number of samples.  In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 9268–9277, 2019.
  * [12] 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.
  * [13] Qi Dong, Shaogang Gong, and Xiatian Zhu.  Class rectification hard mining for imbalanced deep learning.  In Proceedings of the IEEE International Conference on Computer Vision, pages 1851–1860, 2017.
  * [14] 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.
  * [15] Peng Gao, Shijie Geng, Renrui Zhang, Teli Ma, Rongyao Fang, Yongfeng Zhang, Hongsheng Li, and Yu Qiao.  Clip-adapter: Better vision-language models with feature adapters.  arXiv preprint arXiv:2110.04544, 2021.
  * [16] Peng Gao, Zhengkai Jiang, Haoxuan You, Pan Lu, Steven CH Hoi, Xiaogang Wang, and Hongsheng Li.  Dynamic fusion with intra-and inter-modality attention flow for visual question answering.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 6639–6648, 2019.
  * [17] Tianyu Gao, Xingcheng Yao, and Danqi Chen.  Simcse: Simple contrastive learning of sentence embeddings.  In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), 2021.
  * [18] Suchin Gururangan, Ana Marasović, Swabha Swayamdipta, Kyle Lo, Iz Beltagy, Doug Downey, and Noah A Smith.  Don’t stop pretraining: adapt language models to domains and tasks.  arXiv preprint arXiv:2004.10964, 2020.
  * [19] Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick.  Momentum contrast for unsupervised visual representation learning.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 9729–9738, 2020.
  * [20] Kaiming He, Georgia Gkioxari, Piotr Dollár, and Ross Girshick.  Mask r-cnn.  In Proceedings of the IEEE international conference on computer vision, pages 2961–2969, 2017.
  * [21] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770–778, 2016.
  * [22] Youngkyu Hong, Seungju Han, Kwanghee Choi, Seokjun Seo, Beomsu Kim, and Buru Chang.  Disentangling label distribution for long-tailed visual recognition.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 6626–6636, 2021.
  * [23] Neil Houlsby, Andrei Giurgiu, Stanislaw Jastrzebski, Bruna Morrone, Quentin De Laroussilhe, Andrea Gesmundo, Mona Attariyan, and Sylvain Gelly.  Parameter-efficient transfer learning for nlp.  In International Conference on Machine Learning, pages 2790–2799. PMLR, 2019.
  * [24] Ronghang Hu, Piotr Dollár, Kaiming He, Trevor Darrell, and Ross Girshick.  Learning to segment every thing.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 4233–4241, 2018.
  * [25] Chen Huang, Yining Li, Chen Change Loy, and Xiaoou Tang.  Learning deep representation for imbalanced classification.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 5375–5384, 2016.
  * [26] Chao Jia, Yinfei Yang, Ye Xia, Yi-Ting Chen, Zarana Parekh, Hieu Pham, Quoc V Le, Yunhsuan Sung, Zhen Li, and Tom Duerig.  Scaling up visual and vision-language representation learning with noisy text supervision.  In International Conference on Machine Learning, 2021.
  * [27] Zhengbao Jiang, Frank F Xu, Jun Araki, and Graham Neubig.  How can we know what language models know?  Transactions of the Association for Computational Linguistics, 8:423–438, 2020.
  * [28] Bingyi Kang, Yu Li, Sa Xie, Zehuan Yuan, and Jiashi Feng.  Exploring balanced feature spaces for representation learning.  In International Conference on Learning Representations, 2021.
  * [29] Bingyi Kang, Zhuang Liu, Xin Wang, Fisher Yu, Jiashi Feng, and Trevor Darrell.  Few-shot object detection via feature reweighting.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 8420–8429, 2019.
  * [30] Bingyi Kang, Saining Xie, Marcus Rohrbach, Zhicheng Yan, Albert Gordo, Jiashi Feng, and Yannis Kalantidis.  Decoupling representation and classifier for long-tailed recognition.  In International Conference on Learning Representations, 2020.
  * [31] Will Kay, Joao Carreira, Karen Simonyan, Brian Zhang, Chloe Hillier, Sudheendra Vijayanarasimhan, Fabio Viola, Tim Green, Trevor Back, Paul Natsev, et al.  The kinetics human action video dataset.  arXiv preprint arXiv:1705.06950, 2017.
  * [32] Jin-Hwa Kim, Jaehyun Jun, and Byoung-Tak Zhang.  Bilinear attention networks.  arXiv preprint arXiv:1805.07932, 2018.
  * [33] Ranjay Krishna, Yuke Zhu, Oliver Groth, Justin Johnson, Kenji Hata, Joshua Kravitz, Stephanie Chen, Yannis Kalantidis, Li-Jia Li, David A Shamma, et al.  Visual genome: Connecting language and vision using crowdsourced dense image annotations.  International journal of computer vision, 123(1):32–73, 2017.
  * [34] Xiang Lisa Li and Percy Liang.  Prefix-tuning: Optimizing continuous prompts for generation.  arXiv preprint arXiv:2101.00190, 2021.
  * [35] Yangguang Li, Feng Liang, Lichen Zhao, Yufeng Cui, Wanli Ouyang, Jing Shao, Fengwei Yu, and Junjie Yan.  Supervision exists everywhere: A data efficient contrastive language-image pre-training paradigm.  arXiv preprint arXiv:2110.05208, 2021.
  * [36] Tsung-Yi Lin, Piotr Dollár, Ross Girshick, Kaiming He, Bharath Hariharan, and Serge Belongie.  Feature pyramid networks for object detection.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 2117–2125, 2017.
  * [37] Tsung-Yi Lin, Priya Goyal, Ross Girshick, Kaiming He, and Piotr Dollár.  Focal loss for dense object detection.  In Proceedings of the IEEE international conference on computer vision, pages 2980–2988, 2017.
  * [38] Tsung-Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C Lawrence Zitnick.  Microsoft coco: Common objects in context.  In European conference on computer vision, pages 740–755. Springer, 2014.
  * [39] Jialun Liu, Yifan Sun, Chuchu Han, Zhaopeng Dou, and Wenhui Li.  Deep representation learning on long-tailed data: A learnable embedding augmentation perspective.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 2970–2979, 2020.
  * [40] Shu Liu, Lu Qi, Haifang Qin, Jianping Shi, and Jiaya Jia.  Path aggregation network for instance segmentation.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 8759–8768, 2018.
  * [41] Ziwei Liu, Zhongqi Miao, Xiaohang Zhan, Jiayun Wang, Boqing Gong, and Stella X Yu.  Large-scale long-tailed recognition in an open world.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 2537–2546, 2019.
  * [42] Jonathan Long, Evan Shelhamer, and Trevor Darrell.  Fully convolutional networks for semantic segmentation.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 3431–3440, 2015.
  * [43] Dhruv Mahajan, Ross Girshick, Vignesh Ramanathan, Kaiming He, Manohar Paluri, Yixuan Li, Ashwin Bharambe, and Laurens Van Der Maaten.  Exploring the limits of weakly supervised pretraining.  In Proceedings of the European conference on computer vision (ECCV), pages 181–196, 2018.
  * [44] Aditya Krishna Menon, Sadeep Jayasumana, Ankit Singh Rawat, Himanshu Jain, Andreas Veit, and Sanjiv Kumar.  Long-tail learning via logit adjustment.  In International Conference on Learning Representations, 2021.
  * [45] Medhini Narasimhan, Anna Rohrbach, and Trevor Darrell.  Clip-it! language-guided video summarization.  In Advances in Neural Information Processing Systems, 2021.
  * [46] Duy-Kien Nguyen and Takayuki Okatani.  Improved fusion of visual and language representations by dense symmetric co-attention for visual question answering.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 6087–6096, 2018.
  * [47] Aaron van den Oord, Yazhe Li, and Oriol Vinyals.  Representation learning with contrastive predictive coding.  arXiv preprint arXiv:1807.03748, 2018.
  * [48] Wanli Ouyang, Xiaogang Wang, Cong Zhang, and Xiaokang Yang.  Factors in finetuning deep model for object detection with long-tail distribution.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 864–873, 2016.
  * [49] Vilfredo Pareto.  Cours d’économie politique.  Librairie Droz, 1964.
  * [50] Fabio Petroni, Tim Rocktäschel, Sebastian Riedel, Patrick Lewis, Anton Bakhtin, Yuxiang Wu, and Alexander Miller.  Language models as knowledge bases?  In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pages 2463–2473, 2019.
  * [51] 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, 2021.
  * [52] Jiawei Ren, Cunjun Yu, Shunan Sheng, Xiao Ma, Haiyu Zhao, Shuai Yi, and Hongsheng Li.  Balanced meta-softmax for long-tailed visual recognition.  arXiv preprint arXiv:2007.10740, 2020.
  * [53] Shaoqing Ren, Kaiming He, Ross Girshick, and Jian Sun.  Faster r-cnn: Towards real-time object detection with region proposal networks.  Advances in neural information processing systems, 28:91–99, 2015\.
  * [54] Dvir Samuel and Gal Chechik.  Distributional robustness loss for long-tail learning.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 9495–9504, 2021.
  * [55] Lei Shi, Kai Shuang, Shijie Geng, Peng Su, Zhengkai Jiang, Peng Gao, Zuohui Fu, Gerard de Melo, and Sen Su.  Contrastive visual-linguistic pretraining.  arXiv preprint arXiv:2007.13135, 2020.
  * [56] Taylor Shin, Yasaman Razeghi, Robert L Logan IV, Eric Wallace, and Sameer Singh.  Eliciting knowledge from language models using automatically generated prompts.  In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 4222–4235, 2020.
  * [57] Mohit Shridhar, Lucas Manuelli, and Dieter Fox.  Cliport: What and where pathways for robotic manipulation.  In Proceedings of the 5th Conference on Robot Learning (CoRL), 2021\.
  * [58] Karen Simonyan and Andrew Zisserman.  Very deep convolutional networks for large-scale image recognition.  In International Conference on Learning Representations, 2015.
  * [59] Kaihua Tang, Jianqiang Huang, and Hanwang Zhang.  Long-tailed classification by keeping the good and removing the bad momentum causal effect.  In Advances in Neural Information Processing Systems, 2020.
  * [60] Laurens Van der Maaten and Geoffrey Hinton.  Visualizing data using t-sne.  Journal of machine learning research, 9(11), 2008.
  * [61] Mengmeng Wang, Jiazheng Xing, and Yong Liu.  Actionclip: A new paradigm for video action recognition.  arXiv preprint arXiv:2109.08472, 2021.
  * [62] Xudong Wang, Long Lian, Zhongqi Miao, Ziwei Liu, and Stella Yu.  Long-tailed recognition by routing diverse distribution-aware experts.  In International Conference on Learning Representations, 2020.
  * [63] Xudong Wang, Long Lian, Zhongqi Miao, Ziwei Liu, and Stella Yu.  Long-tailed recognition by routing diverse distribution-aware experts.  In International Conference on Learning Representations, 2021.
  * [64] Tz-Ying Wu, Pedro Morgado, Pei Wang, Chih-Hui Ho, and Nuno Vasconcelos.  Solving long-tailed recognition with deep realistic taxonomic classifier.  In European Conference on Computer Vision, pages 171–189. Springer, 2020.
  * [65] Saining Xie, Ross Girshick, Piotr Dollár, Zhuowen Tu, and Kaiming He.  Aggregated residual transformations for deep neural networks.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1492–1500, 2017.
  * [66] Hu Xu, Gargi Ghosh, Po-Yao Huang, Dmytro Okhonko, Armen Aghajanyan, Florian Metze, Luke Zettlemoyer, and Christoph Feichtenhofer.  Videoclip: Contrastive pre-training for zero-shot video-text understanding.  In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), 2021.
  * [67] Xi Yin, Xiang Yu, Kihyuk Sohn, Xiaoming Liu, and Manmohan Chandraker.  Feature transfer learning for face recognition with under-represented data.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 5704–5713, 2019.
  * [68] Zhou Yu, Jun Yu, Yuhao Cui, Dacheng Tao, and Qi Tian.  Deep modular co-attention networks for visual question answering.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 6281–6290, 2019.
  * [69] Andy Zeng, Pete Florence, Jonathan Tompson, Stefan Welker, Jonathan Chien, Maria Attarian, Travis Armstrong, Ivan Krasin, Dan Duong, Vikas Sindhwani, and Johnny Lee.  Transporter networks: Rearranging the visual world for robotic manipulation.  In Proceedings of the 4th Conference on Robot Learning (CoRL), 2020\.
  * [70] Songyang Zhang, Zeming Li, Shipeng Yan, Xuming He, and Jian Sun.  Distribution alignment: A unified framework for long-tail visual recognition.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 2361–2370, 2021.
  * [71] Xiao Zhang, Zhiyuan Fang, Yandong Wen, Zhifeng Li, and Yu Qiao.  Range loss for deep face recognition with long-tailed training data.  In Proceedings of the IEEE International Conference on Computer Vision, pages 5409–5418, 2017.
  * [72] Yifan Zhang, Bryan Hooi, Lanqing Hong, and Jiashi Feng.  Test-agnostic long-tailed recognition by test-time aggregating diverse experts with self-supervision.  arXiv preprint arXiv:2107.09249, 2021.
  * [73] Yifan Zhang, Bingyi Kang, Bryan Hooi, Shuicheng Yan, and Jiashi Feng.  Deep long-tailed learning: A survey.  arXiv preprint arXiv:2110.04596, 2021.
  * [74] Hengshuang Zhao, Jianping Shi, Xiaojuan Qi, Xiaogang Wang, and Jiaya Jia.  Pyramid scene parsing network.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 2881–2890, 2017.
  * [75] Boyan Zhou, Quan Cui, Xiu-Shen Wei, and Zhao-Min Chen.  Bbn: Bilateral-branch network with cumulative learning for long-tailed visual recognition.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 9719–9728, 2020.
  * [76] Bolei Zhou, Agata Lapedriza, Aditya Khosla, Aude Oliva, and Antonio Torralba.  Places: A 10 million image database for scene recognition.  IEEE transactions on pattern analysis and machine intelligence, 40(6):1452–1464, 2017.
  * [77] Linchao Zhu and Yi Yang.  Inflated episodic memory with region self-attention for long-tailed visual recognition.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 4344–4353, 2020.
  * [78] George Kingsley Zipf.  Human behavior and the principle of least effort: An introduction to human ecology.  Addison-Wesley Press, Inc., 1949.

Appendices

This supplementary file includes more details and results of BALLAD that were
not contained in the main manuscript due to the limited paper size. We start
with elaborating the two-phase training of BALLAD in Appendix A. Then we
provide the zero-shot long-tailed recognition performance of the vision-
language model CLIP in three benchmark datasets (Appendix B). Moreover, we
perform ablations of different text prompts in Appendix C. Appendix D shows
visualization results of the decoupled training of CLIP and linear adapter as
discussed in Sec. 4.3.2 in main manuscript.

##  Appendix A Algorithm

We provide the pseudo code of training BALLAD as shown in Algorithm 1. In
phase A, we keep training the vision-language model, updating parameters of
both visual and language encoders. Afterward, in phase B, we train a single
linear adapter with vision-language model frozen to adapt visual features in a
balanced way.

Algorithm 1 Two-phases training of BALLAD

Training samples $\\{(\bm{I},y)\\}$, visual and language encoder
$\mathcal{V}_{\mathrm{enc}}$, $\mathcal{L}_{\mathrm{enc}}$, linear adapter
$\mathcal{LA}$

Initialize $\mathcal{V}_{\mathrm{enc}}$, $\mathcal{L}_{\mathrm{enc}}$ with
web-data pretrained parameters $\Theta_{v}$ and $\Theta_{l}$

for epoch $=1,...,N_{A}$ do $\triangleright$ Phase A

for minibatch $B\in\\{(\bm{I},y)\\}$ do

$\bm{f}_{v}\leftarrow\mathcal{V}_{\mathrm{enc}}(\bm{I})\in\mathbb{R}^{d_{v}}$

$\bm{T}\leftarrow tokenize(y)$

$\bm{f}_{l}\leftarrow\mathcal{L}_{\mathrm{enc}}(\bm{T})\in\mathbb{R}^{d_{l}}$

Project into embedding space $\mathbf{u},\mathbf{v}$ as Eq.(1)

$p_{i}\leftarrow\frac{\exp\left(\mathbf{v}^{\top}\mathbf{u}_{i}\right)/\tau}{\sum_{j=1}^{K}\exp\left(\mathbf{v}^{\top}\mathbf{u}_{j}\right)/\tau}$

Update $\Theta_{v}$ and $\Theta_{l}$

end for

end for

Initialize $\Theta_{LA}$ randomly for $\mathcal{LA}$ $\triangleright$ Phase B

Freeze $\Theta_{v}$ and $\Theta_{l}$

for epoch $=1,...,N_{B}$ do

for minibatch $B\in\\{Balanced(\bm{I},y)\\}$ do

$\bm{f}_{v}\leftarrow\lambda\mathcal{LA}(\mathcal{V}_{\mathrm{enc}}(\bm{I}))+(1-\lambda)\mathcal{V}_{\mathrm{enc}}(\bm{I})\in\mathbb{R}^{d_{v}}$

$\bm{T}\leftarrow tokenize(y)$

$\bm{f}_{l}\leftarrow\mathcal{L}_{\mathrm{enc}}(\bm{T})\in\mathbb{R}^{d_{l}}$

Project into embedding space $\mathbf{u},\mathbf{v}$ as Eq.(1)

$p_{i}\leftarrow\frac{\exp\left(\mathbf{v}^{\top}\mathbf{u}_{i}\right)/\tau}{\sum_{j=1}^{K}\exp\left(\mathbf{v}^{\top}\mathbf{u}_{j}\right)/\tau}$

Update $\Theta_{LA}$

end for

end for

##  Appendix B Zero-shot Performance

The zero-shot long-tailed recognition performances on three benchmark datasets
are presented in Table 9. The red numbers show how much BALLAD has improved
compared with zero-shot CLIP results. It illustrates the training scheme of
BALLAD is effective as raising the initial vision-language model by a large
margin ($+12.2\%$ maximally).

Visual Backbone | ImageNet-LT | Places-LT | CIFAR100-LT
---|---|---|---
zero-shot | BALLAD | zero-shot | BALLAD | zero-shot | BALLAD
ResNet-50 | 58.2 | 67.2 (+9) | 35.3 | 46.5 (+11.2) | 40.2 | 51.6 (+11.4)
ResNet-101 | 61.2 | 70.5 (+9.3) | 36.2 | 47.9 (+11.7) | 47.8 | 59.2 (+11.4)
ViT-B/16 | 66.7 | 75.7 (+9) | 37.8 | 49.5 (+11.7) | 66.4 | 77.8 (+11.4)
ResNet-50$\times 16$ | 69.0 | 76.5 (+7.5) | 37.1 | 49.3 (+12.2) | 52.9 | 63.7 (+10.8)
Table 9: Top-1 accuracy of zero-shot CLIP and BALLAD-training.

##  Appendix C Text Prompting

Text Prompts | Many | Medium | Few | All
---|---|---|---|---
Single prompt | 71.0 | 66.3 | 59.5 | 67.2
Random single prompt | 70.5 | 66.1 | 59.8 | 66.9
Ensemble prompts | 70.5 | 66.0 | 59.5 | 66.8

Table 10: Comparison of different balanced sampling strategies on ImageNet-LT.

Prompt engineering is initially proposed for knowledge probing in large
pretrained language models [50, 56, 34, 27]. Prompting is adding extra
instructions to task inputs to generate specific outputs from pretrained
language model. In this paper, we utilize manually designed prompts following
CLIP [51]. Specifically, a prompt template like a photo of a {CLASS} is
adopted to all experiments reported in main manuscript. However, CLIP [51]
claims that ensembling several classifiers using different hand-crafted
prompts as follows can improve the performance of zero-shot tasks.

  * •

itap of a {CLASS}.

  * •

a bad photo of the {CLASS}.

  * •

a origami {CLASS}.

  * •

a photo of the large {CLASS}.

  * •

a {CLASS} in the video game.

  * •

art of the {CLASS}.

  * •

a photo of the small {CLASS}.

Therefore, we perform ablations on ensembling the multiple prompts and
randomly choosing one of them for language model training. Ablations are
conducted on ImageNet-LT benchmark [41] with ResNet-50 visual backbone.
Results are reported in Table 10. Surprisingly, prompts ensembling decays
performance from $67.2\%$ to $66.8\%$ rather than raising accuracy. Randomly
choosing a template from above seven prompts also results in performance drop,
by $0.3\%$ overall accuracy. We hypothesize different prompting templates from
multiple views may confuse the pretrained language model finetuning, which is
different from zero-shot task. Thus, we choose a single template a photo of a
{CLASS} in all our ablations.

##  Appendix D Visualization

As discussed in Sec. 4.3.2 in main manuscript, decoupled training of vision-
language model and linear adapter largely boost the performance, especially
for few-shot categories. We visualize the classification space of several few-
shot categories using t-SNE [60] as shown in Fig. 6. It is clearly illustrated
in Sub-figure (a) that decoupled training achieves much more obvious
separation boundary among different classes, especially for some easily
confusing ones such as kingsnake (purple), water snake (brown) and sea snake
(pink).

(a) Decoupled training. (b) Joint training.

(c) Legends

Figure 6: Comparisons of training vision-language model and linear adapter
decoupled and jointly.


###### Abstract

We establish the boundedness character of solutions of a system of rational
difference equations with a variable coefficient.

On the Boundedness of Solutions of a Rational System with a Variable
Coefficient

E. CAMOUZIS

American College of Greece, Deree College, 6 Gravias Street, Aghia Paraskevi,
15342 Athens, Greece

##  1 Introduction

Consider the system of difference equations

$x_{n+1}=\frac{x_{n}}{y_{n}}\;\;\text{and}\;\;y_{n+1}=x_{n}+\gamma_{n}y_{n},\;\;n=0,1,\ldots$
(1.1)

where $\displaystyle\\{\gamma_{n}\\}_{n=0}^{\infty}$ is an arbitrary sequence
of positive real numbers and the initial conditions $\displaystyle x_{0}$ and
$\displaystyle y_{0}$ are positive real numbers.

When $\displaystyle\gamma_{n}=\gamma>1$, the solution
$\displaystyle\\{x_{n},y_{n}\\}_{n=0}^{\infty}$ converges to
$\displaystyle(0,\infty)$ and so it is unbounded. When
$\displaystyle\gamma=1$, the solution
$\displaystyle\\{x_{n},y_{n}\\}_{n=0}^{\infty}$ satisfies the identity

$\displaystyle
x_{n}+y_{n}+\frac{x_{n}}{y_{n}}+\frac{1}{y_{n}}=x_{0}+y_{0}+\frac{x_{0}}{y_{0}}+\frac{1}{y_{0}}=A>2$

and it is easy to see that it converges to

$\displaystyle(0,\frac{A+\sqrt{A^{2}-4}}{2})$

and so is bounded. Finally, when $\displaystyle 0<\gamma<1$, it was
established in [2] that both components of every solution
$\displaystyle\\{x_{n},y_{n}\\}_{n=0}^{\infty}$ are bounded from above by a
positive constant. The proof that was presented in [2] was based on the
properties of the double sequence of finite sums

$\displaystyle\phi(i,n)=\sum_{k=0}^{n}\gamma^{k}x_{k+i+1},\;\;i=0,1,\ldots,\;\;n=0,1,\ldots,$

for which, as it was shown in [2], it holds that

$\displaystyle\lim_{n\rightarrow\infty}\phi(i,n)=\frac{\gamma+x_{i}}{y_{i}},\;\;i=0,1,\ldots\;.$

In this paper we extend the ideas of the proof presented in [2] to establish
that when $\displaystyle\\{\gamma_{n}\\}_{n=0}^{\infty}$ is bounded from below
and from above by two positive constants $\displaystyle\gamma^{\prime}$ and
$\displaystyle\gamma$, and more precisely,

$\displaystyle 0<\gamma^{\prime}\leq\gamma_{n}\leq\gamma<1,$

both components of every solution of System (1.1) are bounded from above by a
positive constant. It was also shown in [2] that when
$\displaystyle\gamma_{n}=\gamma\in(0,1)$ and the initial conditions are
positive real numbers, the dynamics of System (1.1), in terms of boundedness,
are equivalent with the dynamics of the system

$x_{n+1}=\frac{x_{n}y_{n}}{x_{n}+\gamma}\;\;\text{and}\;\;y_{n+1}=\frac{y_{n}}{x_{n}+\gamma},\;\;n=0,1,\ldots\;.$
(1.2)

More precisely, as it was shown in [2], given a solution
$\displaystyle\\{x_{n},y_{n}\\}_{n=0}^{\infty}$ of System (1.1) with
$\displaystyle\gamma_{n}=\gamma>0$, the sequence
$\displaystyle\\{x_{n},w_{n}\\}_{n=0}^{\infty}$, for which,

$\displaystyle w_{n}=\frac{\gamma+x_{n}}{y_{n}},\;\;n=0,1,\ldots,$

satisfies

$x_{n+1}=\frac{x_{n}w_{n}}{x_{n}+\gamma}\;\;\text{and}\;\;w_{n+1}=\frac{w_{n}}{x_{n}+\gamma},\;\;n=0,1,\ldots\;.$
(1.3)

This is also true for System (1.1) with the variable coefficient
$\displaystyle\gamma_{n}$. That is, given a solution
$\displaystyle\\{x_{n},y_{n}\\}_{n=0}^{\infty}$ of System (1.1), the sequence
$\displaystyle\\{x_{n},w_{n}\\}_{n=0}^{\infty}$, where

$\displaystyle w_{n}=\frac{\gamma_{n-1}+x_{n}}{y_{n}},\;\;n=0,2,\ldots,$

with $\displaystyle\gamma_{-1}=\gamma_{0}$, satisfies the system

$x_{n+1}=\frac{x_{n}w_{n}}{x_{n}+\gamma_{n-1}}\;\;\text{and}\;\;w_{n+1}=\frac{w_{n}}{x_{n}+\gamma_{n-1}},\;\;n=0,1,\ldots\;.$
(1.4)

Furthermore,

$w_{n+1}=\frac{1}{y_{n}},\;\;\text{for all}\;\;n\geq 0.$ (1.5)

The following definitions and theorems for double sequences will be useful in
the sequel. Assume that $\displaystyle\\{\phi(k,n)\\}_{k,n=1}^{\infty}$, is a
double sequence of positive real numbers. Then we say that
$\displaystyle\phi(k,n)$ converges to $\displaystyle L\in[0,\infty)$, if for
every $\displaystyle\epsilon>0$, there exists $\displaystyle N(\epsilon)$ such
that

$\displaystyle|\phi(k,n)-L|<\epsilon,\;\;\text{for all}\;\;k,n\geq N.$

We write

$\displaystyle\lim_{k,n\rightarrow\infty}\phi(k,n)=L,$

and $\displaystyle L$ is called the double limit of the sequence. The two
limits

$\displaystyle\lim_{k\rightarrow\infty}\lim_{n\rightarrow\infty}\phi(k,n)\;\;\text{and}\;\;\lim_{n\rightarrow\infty}\lim_{k\rightarrow\infty}\phi(k,n)$

are called iterated limits.

Assume that $\displaystyle\\{\phi(k,n)\\}$ is a double sequence of positive
real numbers and

$\displaystyle(k_{1},n_{1})<(k_{2},n_{2})<\ldots<(k_{s},n_{s})<\ldots$

is a strictly increasing sequence of pairs of positive integers. Then
$\displaystyle\\{\phi(k_{s},n_{t})\\}$ is a double subsequence of
$\displaystyle\\{\phi(k,n)\\}$.

The following three theorems will be useful in the sequel. For the proof see
[3].

######  Theorem 1.1.

Assume that $\displaystyle\\{\phi(k,n)\\}_{k,n=1}^{\infty}$ is a double
sequence of positive real numbers which is bounded from above by a positive
constant. Also, assume that for each $\displaystyle k\geq 1$

$\displaystyle\lim_{n\rightarrow\infty}\phi(k,n)=w_{k}\;\;\text{exists}.$

Then for any subsequence $\displaystyle\\{\phi(k_{s},n_{t})\\}$ of
$\displaystyle\\{\phi(k,n)\\}$,

$\displaystyle\lim_{t\rightarrow\infty}\phi(k_{s},n_{t})=w_{k_{s}}\;\;\text{exists}\;\;\text{for
all}\;\;s.$

Furthermore, if

$\displaystyle\lim_{k\rightarrow\infty}\lim_{n\rightarrow\infty}\phi(k,n)=L\;\;\text{exists},$

then for any subsequence $\displaystyle\\{\phi(k_{s},n_{t})\\}$ of
$\displaystyle\\{\phi(k,n)\\}$,

$\displaystyle\lim_{s\rightarrow\infty}\lim_{t\rightarrow\infty}\phi(k_{s},n_{t})=L.$

######  Theorem 1.2.

Assume that $\displaystyle\\{\phi(k,n)\\}_{k,n=1}^{\infty}$ is a double
sequence of positive real numbers, which is bounded from above by a positive
constant. Also, assume that $\displaystyle\\{\phi(k_{s},n_{t})\\}$ is a double
subsequence of $\displaystyle\\{\phi(k,n)\\}$ which strictly decreases (resp.
increases) to a nonnegative value $\displaystyle L$ and also

$\displaystyle\phi(k_{s},n_{t})<\phi(i,j),\;(\text{resp.}\phi(k_{s},n_{t})>\phi(i,j))\;\text{for
all}\;\;(i,j)<(k_{s},n_{t})$

and for all $\displaystyle(k_{s},n_{t})$. Then

$\displaystyle\lim_{s,t\rightarrow\infty}\phi(k_{s},n_{t})=\lim_{s\rightarrow\infty}\lim_{t\rightarrow\infty}\phi(k_{s},n_{t})=\lim_{t\rightarrow\infty}\lim_{s\rightarrow\infty}\phi(k_{s},n_{t})=L\in[0,\infty).$

######  Theorem 1.3.

Assume that $\displaystyle\\{\phi(k,n)\\}_{k,n=1}^{\infty}$ is a double
sequence of positive real numbers such that

$\displaystyle\lim_{n\rightarrow\infty}\phi(k,n)\;\;\text{exists
uniformly}\;\;\text{in}\;\;k$

and that

$\displaystyle\lim_{k\rightarrow\infty}\lim_{n\rightarrow\infty}\phi(k,n)=L.$

Then the double limit of the sequence $\displaystyle\\{\phi(k,n)\\}$ exists
and

$\displaystyle\lim_{k,n\rightarrow\infty}\phi(k,n)=L.$

##  2 Boundedness

In this section we establish that both components of every solution of System
(1.1) are bounded from above by a positive constant.

######  Theorem 2.1.

Let $\displaystyle\\{x_{n},y_{n}\\}_{n=0}^{\infty}$ be a solution of System
(1.1) with positive initial conditions $\displaystyle x_{0}$ and
$\displaystyle y_{0}$ and such that

$\displaystyle 0<\gamma^{\prime}\leq\gamma_{n}\leq\gamma<1,\;\;\text{for
all}\;\;n\geq 0$

and $\displaystyle\gamma^{\prime},\gamma\in(0,1)$. Then both components of the
solution $\displaystyle\\{x_{n},y_{n}\\}_{n=0}^{\infty}$ are bounded from
above by a positive constant.

The proof of the theorem will be presented at the end of this section.

Set $\displaystyle\gamma_{-1}=\gamma_{0}$. Consider the double sequence of
finite sums

$\displaystyle\phi(i,n)=x_{i+1}+\gamma_{i-1}x_{i+2}+\gamma_{i-1}\gamma_{i}x_{i+3}+\ldots+\gamma_{i-1}\cdots\gamma_{i+n-3}x_{i+n},$

with

$\displaystyle i=0,1,\ldots\;\;\text{and}\;\;n=1,2,\ldots,$

or equivalently,

$\phi(i,n)=\sum_{k=0}^{n-1}\mu(i,k)x_{i+k+1},\;\;i=0,1,\ldots,\;n=1,2,\ldots,$
(2.1)

where for each $\displaystyle i\geq 0$,

$\displaystyle\mu(i,k)=\prod_{j=i-1}^{k+i-3}\gamma_{j},\;\;k=2,3,\ldots$

and

$\displaystyle\mu(i,1)=1.$

The following lemmas will be useful in the sequel.

######  Lemma 2.2.

It holds that

$\displaystyle\lim_{i\rightarrow\infty}\lim_{k\rightarrow\infty}\mu(i,k)=\lim_{i,k\rightarrow\infty}\mu(i,k)=0.$

###### Proof.

In view of Theorem 1.3, it suffices to show that

$\displaystyle\lim_{k\rightarrow\infty}\mu(i,k)=0$

uniformly for each $\displaystyle i$. Indeed, for a given positive number
$\displaystyle\epsilon$ and $\displaystyle i$ arbitrary but fixed, we choose
$\displaystyle k>\frac{\ln\epsilon}{\ln\gamma}+1$, or equivalently
$\displaystyle\gamma^{k-1}<\epsilon$. Then

$\displaystyle\mu(i,k)<\gamma^{k-1}<\epsilon$

from which the result follows. ∎

######  Lemma 2.3.

Let $\displaystyle\\{x_{n},y_{n}\\}_{n=0}^{\infty}$ be a solution of System
(1.1). Then for each $\displaystyle i\geq 0$,

$\displaystyle\lim_{n\rightarrow\infty}\frac{y_{i+n}}{\mu(i,n+2)}=\infty.$

###### Proof.

From the first equation of System (1.1) we see that

$\displaystyle\frac{y_{i+n+1}}{\mu(i,n+3)}=\frac{x_{i+n}}{\mu(i,n+3)}+\frac{y_{i+n}}{\mu(i,n+2)},\;\;n=0,1,\ldots$

and so the sequence
$\displaystyle\left\\{\frac{y_{i+n}}{\mu(i,n+2)}\right\\}_{n=0}^{\infty}$ is
strictly increasing. Now assume for the sake of contradiction that

$\displaystyle\lim_{n\rightarrow\infty}\frac{y_{i+n}}{\mu(i,n+2)}=L\in(0,\infty).$

Then, there exists a positive number $\displaystyle\epsilon$ arbitrarily small
and a positive integer $\displaystyle N$ sufficiently large such that

$\displaystyle y_{n+i}<(L+\epsilon)\mu(i,n+2),\;\;\text{for all}\;\;n\geq N.$

From Lemma 2.2, the sequence $\displaystyle\\{\mu(i,n+2)\\}_{n=0}^{\infty}$
converges to zero. Thus, the sequence
$\displaystyle\\{y_{i+n}\\}_{n=0}^{\infty}$ goes to zero as well. Furthermore,

$\displaystyle\mu(i,n+2)=\prod_{j=i-1}^{n+i-1}\gamma_{j}\leq\gamma^{n+1},\;\;\text{for
all}\;\;n\geq 0$

implies that

$\displaystyle y_{i+n}\leq(L+\epsilon)\gamma^{n+1},\;\;\text{for all}\;\;n\geq
N$

and so

$\displaystyle
x_{i+n+1}=\frac{x_{i+n}}{y_{i+n}}\geq\frac{1}{(L+\epsilon)\gamma^{n+1}}\cdot
x_{i+n},\;\;\text{for all}\;\;n\geq N$

from which it follows that

$\displaystyle\lim_{n\rightarrow\infty}x_{i+n+1}=\infty.$

However, from the second equation

$\displaystyle y_{i+n+1}>x_{i+n},\;\;\text{for all}\;\;n\geq 0$

which contradicts the fact that the sequence
$\displaystyle\\{y_{i+n}\\}_{n=0}^{\infty}$ converges to 0.

∎

######  Lemma 2.4.

Let $\displaystyle\\{x_{n},y_{n}\\}_{n=0}^{\infty}$ be a solution of (1.1).
Then for all $\displaystyle i\geq 0$,

$\frac{x_{i}+\gamma_{i-1}}{y_{i}}=w_{i}=\phi(i,n)+\mu(i,n+1)w_{i+n},\;\;n=1,2,\ldots\;.$
(2.2)

###### Proof.

Let $\displaystyle i\geq 0$ be given. Clearly, in view of (1.4),

$\displaystyle w_{i}=x_{i+1}+\gamma_{i-1}w_{i+1}$

and so the result is true when $\displaystyle n=1$. Assume that $\displaystyle
k>1$ and that

$\displaystyle
w_{i}=x_{i+1}+\gamma_{i-1}x_{i+2}+\ldots+\gamma_{i-1}\cdots\gamma_{i+k-3}x_{i+k}+\gamma_{i-1}\cdots\gamma_{i+k-2}w_{i+k}$
$\displaystyle=\phi(i,k)+\mu(i,k+1)w_{k+i}.$

Then

$\displaystyle w_{i}=\phi(i,k)+\mu(i,k+1)(x_{i+k+1}+\gamma_{i+k-1}w_{i+k+1})$
$\displaystyle=\phi(i,k)+\mu(i,k+1)x_{i+k+1}+\mu(i,k+1)\gamma_{i+k-1}w_{i+k+1}$
$\displaystyle=\phi(i,k+1)+\mu(i,k+2)w_{i+k+1}.$

The proof is complete.

∎

######  Lemma 2.5.

Let $\displaystyle\\{x_{n},y_{n}\\}_{n=0}^{\infty}$ be a solution of (1.1).
Then for all $\displaystyle i\geq 0$,

$\lim_{n\rightarrow\infty}\phi(i,n)=\sum_{k=0}^{\infty}\mu(i,k)x_{i+k+1}=\frac{x_{i}+\gamma_{i-1}}{y_{i}}=w_{i}.$
(2.3)

###### Proof.

The result follows from (2.2) together with the fact, in view of (1.5) and
Lemma 2.3, that

$\displaystyle\lim_{n\rightarrow\infty}\mu(i,n+1)w_{i+n}=\lim_{n\rightarrow\infty}\frac{\mu(i,n+1)}{y_{i+n-1}}=0.$

∎

######  Lemma 2.6.

Let $\displaystyle\\{x_{n},y_{n}\\}_{n=0}^{\infty}$ be a solution of (1.1) and
assume that for an infinite sequence of positive integers
$\displaystyle\\{k_{i}\\}_{i=1}^{\infty}$, $\displaystyle\\{x_{k_{i}}\\}$ is a
bounded subsequence of $\displaystyle\\{x_{n}\\}$ and

$\displaystyle\lim_{i\rightarrow\infty}\frac{x_{k_{i}}+\gamma_{k_{i}-1}}{y_{k_{i}}}=\lim_{i\rightarrow\infty}w_{k_{i}}=M\in(0,\infty).$

Then the following statements are true:

1.

$\displaystyle\lim_{i\rightarrow\infty}\lim_{n\rightarrow\infty}\phi(k_{i},n)=M.$

2\. For any subsequence $\displaystyle\\{\phi(k_{i_{s}},n_{j})\\}$ of
$\displaystyle\\{\phi(k_{i},n)\\}$, it holds

$\displaystyle\lim_{s\rightarrow\infty}\lim_{j\rightarrow\infty}\phi(k_{i_{s}},n_{j})=M.$

3.

$\displaystyle\limsup_{i,n\rightarrow\infty}\phi(k_{i},n)\leq M.$

4.

$\displaystyle\liminf_{i,n\rightarrow\infty}\phi(k_{i},n)>0.$

5.

$\displaystyle\liminf_{i\rightarrow\infty}x_{k_{i}+1}>0.$

###### Proof.

1\. The proof follows from Lemma 2.5 and the hypothesis.

2\. The proof is an immediate consequence of the result of Part 1 and Theorem
1.1, which is presented in the Introduction.

3\. The proof is an immediate consequence of the fact that, for each
$\displaystyle i\geq 1$,

$\displaystyle\phi(k_{i},n)<\sum_{k=0}^{\infty}\mu(k_{i},n)x_{k+k_{i}+1}=w_{k_{i}},\;\;\text{for
all}\;\;n\geq 1$

and the hypothesis that $\displaystyle w_{k_{i}}\rightarrow M$.

4\. The proof will be by contradiction. Assume for the sake of contradiction
that there exists a decreasing subsequence
$\displaystyle\\{\phi(k_{i_{s}},n_{j})\\}_{s,j=1}^{\infty}$ of
$\displaystyle\\{\phi(k_{i},n)\\}$, for which

$\displaystyle\lim_{s,j\rightarrow\infty}\phi(k_{i_{s}},n_{j})=0$

and

$\displaystyle\phi(k_{i_{s}},n_{j})<\phi(p,q),\;\;\text{for
all}\;\;(p,q)<(k_{i_{s}},n_{j}).$

We claim that both $\displaystyle\\{k_{i_{s}}\\}$ and
$\displaystyle\\{n_{j}\\}$ must increase to infinity. Otherwise, for
$\displaystyle k_{i_{s}}$ finite and fixed,

$\displaystyle\lim_{j\rightarrow\infty}\phi(k_{i_{s}},n_{j})=0.$

In view of the result of Part 2 and the hypothesis, we see that

$\displaystyle\lim_{j\rightarrow\infty}\phi(k_{i_{s}},n_{j})=w_{k_{i_{s}}}>0$

which is a contradiction.

On the other hand assume that there exists a positive integer $\displaystyle
N$ such that

$\displaystyle\lim_{s\rightarrow\infty}\phi(k_{i_{s}},j)=0,\;\;j=1,2,\ldots,N\;\;\text{and}\;\;\liminf_{s\rightarrow\infty}\phi(k_{i_{s}},N+1)>0.$

In view of (2.1), as $\displaystyle s\rightarrow\infty$, it is easy to see
that

$\displaystyle x_{k_{i_{s}}+t}\rightarrow 0,\;\;\text{for
all}\;\;t=1,\ldots,N.$

By choosing a further subsequence of
$\displaystyle\\{k_{i_{s}}\\}_{s=1}^{\infty}$, which for economy in notation
we still denote it as $\displaystyle\\{k_{i_{s}}\\}$, it holds that for each
$\displaystyle j=-1,0,\ldots,N-2,\;$ the sequence
$\displaystyle\\{\gamma_{k_{i_{s}}+j}\\}_{s=1}^{\infty}$ converges to a
positive number. Set

$\displaystyle
m=\lim_{s\rightarrow\infty}\prod_{j=-1}^{N-2}\gamma_{k_{i_{s}}+j}\in(0,\infty).$

Clearly, and in view of (1.4),

$\displaystyle w_{k_{i_{s}}+N}\rightarrow\frac{M}{m}>0.$

Therefore,

$\displaystyle
x_{k_{i_{s}}+N+1}=\frac{x_{k_{i_{s}}+N}w_{k_{i_{s}}+N}}{\gamma_{k_{i_{s}}+N-1}+x_{k_{i_{s}}+N}}\rightarrow
0$

and so, in view of (2.1),

$\displaystyle\lim_{s\rightarrow\infty}\phi(k_{i_{s}},N+1)=0$

which is a contradiction. Therefore, the sequences
$\displaystyle\\{k_{i_{s}}\\}$ and $\displaystyle\\{n_{j}\\}$ are infinite
sequences of positive integers and both increase to infinity. By applying
Theorem 1.2, we get

$\displaystyle\lim_{s,j\rightarrow\infty}\phi(k_{i_{s}},n_{j})=\lim_{s\rightarrow\infty}\lim_{j\rightarrow\infty}\phi(k_{i_{s}},n_{j})=0.$

On the other hand, by applying the result of Part 2, we see that

$\displaystyle\lim_{s\rightarrow\infty}\lim_{j\rightarrow\infty}\phi(k_{i_{s}},n_{j})=M\in(0,\infty)$

which is a contradiction.

5\. From Part 4, clearly, there exists a positive number $\displaystyle I$
such that

$\displaystyle\phi(k_{i},n)>I,\;\;\text{for all}\;\;i,n\geq N.$

In particular,

$\phi(k_{i},N)=x_{k_{i}+1}+\gamma_{k_{i}-1}x_{k_{i}+2}+\ldots+\gamma_{k_{i}-1}\cdots\gamma_{k_{i}-3+N}x_{k_{i}+N}>I>0,$
(2.4)

for all $\displaystyle i\geq N$. Now assume for the sake of contradiction and
without loss of generality that

$\displaystyle x_{k_{i}+1}\rightarrow 0.$

Note that

$\displaystyle w_{k_{i}}=x_{k_{i}+1}+\gamma_{k_{i}-1}w_{k_{i}+1}\Rightarrow
w_{k_{i}+1}=\frac{w_{k_{i}}}{\gamma_{k_{i}-1}}-\frac{x_{k_{i}+1}}{\gamma_{k_{i}-1}}$

and so there exists a further subsequence of
$\displaystyle\\{k_{i}\\}_{i=1}^{\infty}$, which for economy in notation we
still denote as $\displaystyle\\{k_{i}\\}$, such that

$\displaystyle\gamma_{k_{i}-1}\rightarrow
m>0\;\;\text{and}\;\;w_{k_{i}+1}\rightarrow\frac{M}{m},$

and so

$\displaystyle
x_{k_{i}+2}=\frac{x_{k_{i}+1}w_{k_{i}+1}}{\gamma_{k_{i}}+x_{k_{i}+1}}\rightarrow
0.$

By induction, we see that

$\displaystyle\lim_{i\rightarrow\infty}x_{k_{i}+j}=0,\;\;\text{for
all}\;\;j=1,2,\ldots,N.$

By taking limits in (2.4), as $\displaystyle i\rightarrow\infty$, we get a
contradiction.

∎

We now present the proof of Theorem 2.1

###### Proof.

Let $\displaystyle\\{x_{n},y_{n}\\}_{n=0}^{\infty}$ be a solution of System
(1.1). First we establish that the component
$\displaystyle\\{y_{n}\\}_{n=0}^{\infty}$ of the solution is bounded from
below by a positive constant. Assume for the sake of contradiction that there
exists an infinite sequence of indices
$\displaystyle\\{n_{i}\\}_{i=1}^{\infty}$ such that

$\displaystyle y_{n_{i}+1}=x_{n_{i}}+\gamma_{n_{i}}y_{n_{i}}\rightarrow 0.$

Clearly,

$\displaystyle x_{n_{i}-t}\rightarrow
0\;\;\text{and}\;\;y_{n_{i}-t}\rightarrow 0,\;\;\text{for
all}\;\;t=0,1,\ldots\;.$

In addition, there exists a sequence of indices
$\displaystyle\\{k_{i}\\}_{i=1}^{\infty}$ such that

$\displaystyle k_{i}\leq n_{i},\;\;\text{for all}\;\;i,$

for which

$(y_{k_{i}-1}\geq
1\;\text{and}\;y_{k_{i}}<1)\;\text{and}\;(y_{t}<1,\;\;\text{for
all}\;\;t\in\\{k_{i}+1,\ldots,n_{i}\\}),$ (2.5)

because otherwise,

$\displaystyle x_{n_{i}}=\frac{x_{0}}{\prod_{j=0}^{n_{i}-1}y_{j}}>x_{0},$

which is a contradiction. From

$\displaystyle
y_{k_{i}}=x_{k_{i}-1}+\gamma_{k_{i}-1}y_{k_{i}-1}\;\;\text{and}\;\;y_{k_{i}-1}\geq
1,\;\;\text{for all}\;\;i,$

it follows that

$\displaystyle y_{k_{i}}\geq\gamma_{k_{i}-1}\geq\gamma^{\prime},\;\;\text{for
all}\;\;i,$

and so

$\displaystyle y_{k_{i}}\in[\gamma^{\prime},1),\;\;\text{for all}\;\;i.$

For $\displaystyle i$ sufficiently large, when $\displaystyle
r\in\\{k_{i}+1,\ldots,n_{i}\\}$,

$\displaystyle x_{r}=\frac{x_{r-1}}{y_{r-1}}>x_{r-1}$

and more precisely,

$\displaystyle x_{n_{i}}>x_{n_{i}-1}>\ldots>x_{k_{i}+1}>x_{k_{i}}.$

Therefore,

$\displaystyle x_{k_{i}}<x_{n_{i}},$

from which it follows that $\displaystyle x_{k_{i}}\rightarrow 0$. By
utilizing the fact that

$\displaystyle y_{k_{i}}\in[\gamma^{\prime},1),\;\;\text{for all}\;\;i,$

we may select a further subsequence of $\displaystyle\\{k_{i}\\}$, still
denoted as $\displaystyle\\{k_{i}\\}$ such that

$\displaystyle y_{k_{i}}\rightarrow
L\in[\gamma^{\prime},1]\;\;\text{and}\;\;\gamma_{k_{i}-1}\rightarrow
l_{-1}\in[\gamma^{\prime},\gamma].$

Therefore,

$\displaystyle x_{k_{i}+1}=\frac{x_{k_{i}}}{y_{k_{i}}}\rightarrow
0\;\;\text{and}\;\;w_{k_{i}}=\frac{\gamma_{k_{i}-1}+x_{k_{i}}}{y_{k_{i}}}\rightarrow\frac{l_{-1}}{L}=M\in\left[\gamma^{\prime},\frac{\gamma}{\gamma^{\prime}}\right].$

By applying Lemma 2.6, we get

$\displaystyle\liminf_{i\rightarrow\infty}x_{k_{i}+1}>0$

which is a contradiction. Hence, the component
$\displaystyle\\{y_{n}\\}_{n=0}^{\infty}$ of the solution is bounded from
below by a positive constant $\displaystyle m$. In view of

$\displaystyle
x_{n+1}=\frac{x_{n}}{y_{n}}=\frac{1}{y_{n-1}}\cdot\frac{x_{n}}{x_{n}+\gamma_{n-1}},\;\;\text{for
all}\;\;n\geq 1,$

we see that

$\displaystyle x_{n+1}<\frac{1}{m},\;\;\text{for all}\;\;n\geq 1,$

and so the component $\displaystyle\\{x_{n}\\}_{n=0}^{\infty}$ is bounded from
above. From the second equation of the system, clearly

$\displaystyle y_{n+1}<\frac{1}{m}+\gamma y_{n},\;\;\text{for all}\;\;n\geq
2,$

and so

$\displaystyle\limsup_{n\rightarrow\infty}y_{n}\leq\frac{1}{m(1-\gamma)}.$

The proof of the Theorem is complete.

∎

## References

  * [1]
  * [2] E. Camouzis, On the Boundedness of Solutions of a Rational System, _International Journal of Difference Equations and Applications_ , (to appear).
  * [3] Habil, E. D., Double sequences and double series, submitted to the Islamaic University Journal, (2005).