# Vicinity Vision Transformer

Weixuan Sun, Zhen Qin, Hui Deng, Jianyuan Wang, Yi Zhang, Kaihao Zhang,
Nick Barnes, Stan Birchfield, Lingpeng Kong, Yiran Zhong  Weixuan Sun,
Jianyuan Wang, Kaihao Zhang, Nick Barnes are with School of Computing, the
Australian National University, Canberra, Australia. Zhen Qin, Yi Zhang are
with SenseTime research, Shanghai, China. Hui Deng is with School of
Electronics and Information, Northwestern Polytechnical University, Xi’an,
China. Stan Birchfield is with Nvidia, Redmond, WA, USA. Lingpeng Kong is with
the University of Hong Kong, Hong Kong, China and Shanghai AI Lab, China.
Yiran Zhong is with Sensetime Research, Shanghai, China and Shanghai AI Lab,
China. Weixuan Sun and Zhen Qin are with equal contribution. Our code is
available at: https://github.com/OpenNLPLab/Vicinity-Vision-Transformer.
Corresponding author: Yiran Zhong (zhongyiran@gmail.com).

###### Abstract

Vision transformers have shown great success on numerous computer vision
tasks. However, its central component, softmax attention, prohibits vision
transformers from scaling up to high-resolution images, due to both the
computational complexity and memory footprint being quadratic. Although linear
attention was introduced in natural language processing (NLP) tasks to
mitigate a similar issue, directly applying existing linear attention to
vision transformers may not lead to satisfactory results. We investigate this
problem and find that computer vision tasks focus more on local information
compared with NLP tasks. Based on this observation, we present a Vicinity
Attention that introduces a locality bias to vision transformers with linear
complexity. Specifically, for each image patch, we adjust its attention weight
based on its 2D Manhattan distance measured by its neighbouring patches. In
this case, the neighbouring patches will receive stronger attention than far
away patches. Moreover, since our Vicinity Attention requires the token length
to be much larger than the feature dimension to show its efficiency
advantages, we further propose a new Vicinity Vision Transformer (VVT)
structure to reduce the feature dimension without degenerating the accuracy.
We perform extensive experiments on the CIFAR100, ImageNet1K, and ADE20K
datasets to validate the effectiveness of our method. Our method has a slower
growth rate of GFlops than previous transformer-based and convolution-based
networks when the input resolution increases. In particular, our approach
achieves state-of-the-art image classification accuracy with $50\%$ fewer
parameters than previous methods.

###### Index Terms:

Vision Transformer, Image Classification, Linear Transformer, 2D Vicinity,
Semantic Segmentation

##  1 Introduction

Recent years have witnessed the success of the transformer structure in
natural language processing [1] and computer vision [2, 3, 4]. However,
transformers inherently suffer from quadratic computational complexity and a
quadratic memory footprint. As a result, vision transformer methods have to
adopt patch-wise image tokenization and pyramid architectures to reduce the
sequence length. Despite the temporary relief provided by these methods, the
quadratic complexity problem still exists. This limitation prohibits vision
transformers from handling high-resolution images or fine-grained image
patches.

Linear attention may be a promising direction to solve this issue, which
decomposes the self-attention to reduce the computational complexity to
linear. Numerous methods have been proposed for attention decomposition, such
as approximating the softmax [5, 6, 7], finding a new similarity metric [8,
9], and so on. However, most of these methods are only verified on NLP tasks,
and suffer from a crucial performance drop in computer vision tasks, when
compared with conventional softmax attention.

In this paper, we present Vicinity Attention, a new linear attention that is
effective in computer vision tasks. Our intuition is based on the fact that
convolutional neural networks have dominated computer vision tasks since the
rise of deep networks, and most of them have a locality bias—that is,
neighbouring pixels are more likely to be highly related [10, 11, 12, 13, 14,
15]. Therefore we hypothesize that locality bias is an important property and
introduce it into a transformer network. Our re-weighing mechanism is inspired
by the recently proposed cosFormer [9], which uses a cosine re-weighing
mechanism for 1D NLP tasks. However, directly applying the cosFormer to the
vision tasks will lead to unsatisfactory results since the 1D locality
enforces stronger connections only on the 1D tokenized neighbouring image
patches, is not compatible for 2D distance, _i.e._ , it will assign less
weights to vertically connected patches as they are far-away when we tokenized
the patches to 1D tokens as shown in Fig 3a. To solve this issue, we propose a
2D Manhattan distance to encourage visual tokens to have a stronger reaction
to their neighbors in 2D (Fig 3b-d). Since this mechanism is decomposable, it
can be smoothly applied to linear attention.

Comparing with vanilla transformer based methods, our Vicinity Attention can
show its efficiency advantages when the sequence length is much larger than
the feature dimension. To fulfill this requirement, we propose a new vicinity
attention block to reduce the feature dimension without sacrificing
performance. It consists a Feature Reduction Attention (RFA) module to reduce
the input feature dimension by a half and a Feature Preserving Connection
(FRC) to retrieve the original feature distribution and strengthen the
representational ability. Following the classic convolutional networks [16,
17], we create a backbone called Vicinity Vision Transformer (VVT) with the
vicinity attention block in a pyramid structure. Figure 1a compares our method
with current state-of-the-art vision backbones on the ImageNet-1k benchmark.
Our method outperforms all the competitors with only half the parameters. We
also provide the growth rate of flops with different input resolutions for
these methods in Figure 1b. These results demonstrate that our approach can
handle larger images than other transformer-based methods as well as
convolution-based methods with similar computational costs.

Figure 1: Top-1 accuracy of our Vicinity Vision Transformer (VVT) with respect
to parameters on the ImageNet-1k[18] dataset, and the GFLOPs corresponding to
various input image sizes. Our VVT outperforms all competitors with $50\%$
fewer parameters, and it enjoys the lowest GFLOPs growth rate.

Our main contributions are as follows: (1) We propose a new linear vision
self-attention module that introduces a 2D Manhattan distance-based locality
bias to linear vision transformers. (2) We propose a new multi-head self-
attention module called the Vicinity Attention Block, to fulfill the
assumption required by Vicinity Attention. It contains a feature reduction
attention (FRA) module and a feature preserving connection (FPC) module to
control the computational overhead and improve feature extraction ability. (3)
We correspondingly build the Vicinity Vision Transformer (VVT), which serves
as a general-purpose vision backbone and can be easily applied to vision
tasks. Extensive experiments validate the effectiveness of VVT on various
computer vision benchmarks.

##  2 Related Work

###  2.1 Vision Transformer Backbones

In computer vision tasks, CNN networks have achieved great successes, while
recently transformers have gained strong emerging interest. In this section we
mainly discuss vision networks using self-attention.

Some works [19, 20, 21] adopt self-attention mechanisms to replace some or all
convolution layers in the CNN networks for image recognition. To further
leverage the power of self-attention, [22] proposes a non-local operation and
adds it in ResNet [16],the non-local block can capture long-range dependencies
and leads to improvements on vision tasks such as video classification, object
detection, segmentation, and pose estimation. More recently, pure transformer
based vision networks were introduced. ViT [2] splits images into local
patches and then projects and flatten patches into embedding sequences,
subsequently it employs a pure transformer structure for image classification.

More recently, variations of ViT like CVT [10], Swin [23], PVT [24], Twins
[25] and T2T [26] were proposed. CVT [10] introduces Convolutional Token
Embedding and Convolutional Projection for Attention to include desirable
properties of CNNs into ViT [2] to improve both performance and efficiency.
Swin Transformer [23] introduces non-overlapping windows and applies self-
attention in each window, then the window partitions are shifted between
adjacent layers. Swin transformer reduces computational complexity and is
suitable for different vision tasks. PVT [24] introduces a pure transformer
network with a pyramid structure, it further proposes spatial reduction
attention which computes self-attention in low dimensions to reduce
computation. Twins [25] combines locally-grouped self-attention from Swin [23]
and sub-sampled attention from [24], which decreases the computational cost
and enhances communications between sub-windows. However, none of the above
methods are able to directly process full-length self-attention on high
resolution inputs, requiring locally-grouping or sub-sampling. Contrarily, our
method can directly calculate self-attention on high-resolution input.

Figure 2: Illustration of the standard self-attention (left) and linearized
self-attention (right). $N$ denotes the patch number of the input image, and
$d$ is the feature dimension. With $N\gg d$, the computational complexity of
the linearized self-attention grows linearly with respect to the input length,
while that of the standard self-attention is quadratic.

###  2.2 Efficient Transformers

Various works have been proposed to address the computational complexity
problems of transformers in both computer vision and natural language process
areas. In addition to vision backbones such as CVT [10], Swin [23], PVT [24],
Twins [25] introduced in the previous section, in this section we introduce
other more efficient transformer algorithms.

Existing efficient transformer methods can be generally grouped into two
categories: pattern-based and kernel-based. Pattern-based methods sparsify the
attention matrix with handcrafted or learnable patterns. [27] reduces the
complexity by applying a combination of a strided pattern and a local pattern
to the standard attention matrix. Beyond fixed diagonal windows and global
windows, Longformer [28] also extends sliding windows with dilation to enlarge
the receptive field. Instead of fixed patterns, Reformer [29] and [30] adopt
locally sensitive hashing to group tokens into different buckets. On the other
hand, kernel-based methods [6, 7, 31, 5, 9] aim to replace softmax self-
attention with approximations or decomposable functions, which change the
order of scale dot product calculation and reduce the complexity of self-
attention from quadratic to linear.

Two works that are similar to ours are [32] and [33]. [33] applies softmax on
$Q$ and $K$ respectively, then changes the dot product order to access a
linear complexity. However, it is not validated on a large-scale
classification benchmark as a backbone network. SOFT [32] uses a Gaussian
kernel function to replace the dot-product similarity in self attention, it
assumes that the similarity is symmetrical, which may not hold true in
practice. Further, it does not consider the 2D locality mechanism. In this
paper, we propose a linear self-attention which facilitates a 2D locality
mechanism, and we validate the proposed method on various vision tasks.

##  3 Self-attention, Linearization, Locality

Self-attention is originally proposed for 1D NLP tasks [1]. To make it
suitable for 2D CV tasks, we often convert an image to several patches and
then embed them to a sequence $x\in\mathbb{R}^{N\times d}$, where $d$ is the
embedding size and $N=\frac{H}{p}\times\frac{W}{p}$ is the patch number, with
$p$, $H$, $W$ denoting patch size, image height, and image width respectively.
Mathematically, a transformer block $\mathcal{T}:\mathbb{R}^{N\times
d}\to\mathbb{R}^{N\times d}$ with input $x$ is defined as:

$\textstyle{\mathcal{T}(x)=\mathcal{F}(\mathsf{Att}(x)+x),}$ (1)

where $\mathsf{Att}(\cdot)$ is the self-attention module and
$\mathcal{F}(\cdot)$ is a feed-forward network.

The self-attention module $\mathsf{Att}(\cdot)$ adopts three learnable weights
$W_{Q},W_{K},W_{V}$ to project $x$ into _query_ ($Q$), _key_ ($K$), and
_value_ ($V$). It usually computes an attention matrix $A$ by a similarity
function $\mathcal{S}(\cdot)$ over queries and keys. In standard self-
attention, $\mathcal{S(\cdot)}$ is softmax normalization. The outputs of the
self-attention module is hence $\mathcal{O}=\mathsf{Att}(x)=AV$, where
$A\in\mathbb{R}^{N\times N}$ suffers from a quadratic space and time
complexity with respect to the patch number $N$. Therefore, the theoretical
computation complexity here is $\textstyle O(N^{2}d)$ =
$O(\frac{H^{2}W^{2}}{p^{4}}d)$. Consequently the self-attention module becomes
sensitive to image size $H,W$ and patch size $p$, and is the computation
bottleneck in vision transformer networks.

Linearization of the self-attention aims to reduce the quadratic theoretical
computation complexity to linear. It can be achieved by picking a decomposable
similarity function $\mathcal{S}(\cdot)$ to satisfy

$\mathcal{S}(Q_{i},K_{j})=\phi(Q_{i})\phi(K_{j})^{\top},$ (2)

where $\phi(\cdot)$ is a kernel function. Given such a kernel, we can write
the outputs of the self-attention module as follows:

$\mathcal{O}_{i}=\sum_{j}\frac{\mathcal{S}(Q_{i},K_{j})}{\sum_{j}\mathcal{S}(Q_{i},K_{j})}V_{j}=\frac{\sum^{N}_{j=1}(\phi(Q_{i})\phi({K_{j}})^{\top})V_{j}}{\sum^{N}_{j=1}(\phi(Q_{i})\phi({K_{j}})^{\top})}$
(3)

Fig. 2 illustrates the linearization process. Instead of calculating the
attention matrix $A\in\mathbb{R}^{N\times N}$, we compute
$\phi({K})^{\top}V\in\mathbb{R}^{d\times d}$ first:

$\textstyle[\phi(Q)\phi({K})^{\top}]\ V=\phi(Q)\ [\phi({K})^{\top}V],$ (4)

such that the $O(N^{2}d)$ operation is converted to an $O(Nd^{2})$ one. Its
computational complexity grows linearly with respect to the sequence length
$N$ as long as $N\gg d$. A number of linear attention approaches have been
proposed for NLP tasks, which use different kernel functions $\phi(x)$ to
replace the quadratic softmax, as discussed in the Related Work. However,
linear self-attention in vision tasks is not well studied [32, 33] and suffers
from a performance drop compared with the standard self-attention module. To
address this problem, we propose a linear self-attention that is aware of 2D
position.

Locality is a widely used assumption in computer vision [34, 35, 36, 37, 38,
10, 12, 13, 11], _i.e.,_ neighbouring pixels should have higher possibilities
to belong to the same object than distant pixels. Convolution-based networks
are inherently coupled with this assumption as they always exploit feature
locality [39, 40]. However, this assumption does not hold for standard
transformer-based networks due to the self-attention mechanism. Several works
show that with the same number of parameters, transformer-based networks
cannot match the performance of the CNN counterparts, possibly due to the lack
of locality bias [10, 41]. Recent state-of-the-art methods partially introduce
locality bias to vision transformers in architecture level, _i.e.,_ the Swin
transformer [23] uses window self-attention to enforce the locality, PVT [24]
adopts pyramid architectures to explore local information, and [10, 13]
directly combine convolution with transformers. In this paper, we introduce
the locality bias to the self-attention mechanism in linear vision
transformers. It can smoothly integrate into existing architecture level
locality methods for better performance. In fact, our method achieves better
performance than previous state-of-the-art vision transformers in various
computer vision benchmarks.

##  4 Our Method

Figure 3: Visualization of the locality re-weighting patterns. The red cross
symbol denotes the query position and the mask denotes the locality weights
corresponding to it. We use a lighter color to indicate a larger weight. (a)
If we directly adopt 1D distance re-weighting [9] in self-attention, the query
token will assign lower weights on vertically tokens as they are far away when
processed in 1D. (b), (c), (d) In our method, Although self-attention is
calculated in 1D, our re-weighting mechanism ensures a token is encouraged to
have higher relation weights with its neighbours in two dimensions.

###  4.1 Vicinity Attention

It has been verified that the softmax normalization is the root of the
quadratic complexity of self-attention [32]. In this section, we provide the
details of our linear self-attention technique, vicinity attention for vision
tasks. The key insight is to replace the standard softmax operation by another
similarity function, which (1) can be decomposed to simple kernel functions
and (2) introduces a locality constraint that is beneficial in visual
understanding. Inspired by [9], we adopt $\mathrm{ReLU}(\cdot)$ as the kernel
function, and conduct a row-wise normalization to replace softmax. Our self-
attention then can be reformulated as:

$\displaystyle\mathcal{O}_{i}=\frac{\sum^{N}_{j=1}[\mathrm{ReLU}(Q_{i})\mathrm{ReLU}({K_{j}})^{\top}]V_{j}}{\sum^{N}_{j=1}[\mathrm{ReLU}(Q_{i})\mathrm{ReLU}({K_{j}})^{\top}]}$
(5)
$\displaystyle=\frac{\mathrm{ReLU}(Q_{i})\sum^{N}_{j=1}[\mathrm{ReLU}({K_{j}})^{\top}V_{j}]}{\mathrm{ReLU}(Q_{i})\sum^{N}_{j=1}\mathrm{ReLU}({K_{j}})^{\top}}$

where we can reorder the calculation so the complexity is reduced to linear
with respect to the sequence length $N$. This $\mathrm{ReLU}$-based
normalization method retains two important properties of standard self-
attention: (1) it is always positive, avoiding aggregating negatively-
correlated information. (2) all the elements lie between $[0,1]$.

Enforcing 2D Locality Bias The locality bias has been discussed in language
tasks [9, 42, 43] with 1D sequence distance encoding. In vision transformers,
the embedding sequence is flattened from a 2D mask, hence it is essential to
consider token positions in 2D before flattening. To enforce the locality bias
in linear transformers, we need a kernel function that can 1) put more weight
on neighbouring patches and 2) can be decomposed with Eq. (2).

Given two tokens $q_{i}$, $k_{j}$ from $Q$ and $K$ respectively, the positions
of these two tokens on the 2D feature maps before flattening are:

$i=u_{i}m+r_{i},\ j=u_{j}m+r_{j},\quad 0\leq r_{i},r_{j}<m$ (6)

where $m$ is width of the feature map, $u$ denotes the row index, and $r$
denotes the column index. Following Eq. (2), we can define a re-weighted
attention with a distance function $\mathcal{D}$ to enforce the locality bias
between neighbouring tokens as:

${\mathcal{S}(Q_{i},K_{j})}=\phi(Q_{i})\mathcal{G}(\mathcal{D}(i,j))\phi({K_{j}})^{\top}$
(7)

Figure 4: Illustration of the Vicinity Attention Block. The input feature
dimension is down-sampled to reduce the computational cost, while the original
feature distribution is retained by the Feature Preserving Connection.  Figure
5: Grad_CAM of the proposed network and ViT[2]. Our network can generate high-
resolution feature maps in early stages, which contain more fine-grained local
object features.  Figure 6: Overall architecture of our VVT. VVT adopts a
pyramid structure and is divided into four stages. The illustrated sample is
VVT-Small. The output resolution progressively shrinks to generate multi-scale
feature maps.

where $\mathcal{G}$ generates the weight according to the distance. A naive
choice might be directly using the Euclidean distance
$\sqrt{(r_{j}-r_{i})^{2}+(u_{j}-u_{i})^{2}}$. Since this term cannot be
decomposed into two terms relating to $i$ and $j$ separately, it cannot be
applied to the linear transformers.

Instead, we propose to use the 2D Manhattan distance [44] as the distance
function, which can be easily decoupled into the distance in two directions.
However, in direct Manhattan distance decoupling is still hindered:

${\mathcal{S}(Q_{i},K_{j})}=\phi(Q_{i})\mathcal{G}(|r_{j}-r_{i}|+|u_{j}-u_{i}|)\phi({K_{j}})^{\top}$

as the absolute operation cannot be decomposed.

To fulfill the aforementioned requirements, we propose a 2D cos-based re-
weighting mechanism for our self-attention module. First, given the feature
map with size $m$ by $n$, following Eq. (6) we redefine the 2D positions as:

$a_{i}=\frac{\pi{u_{i}}}{2n},\ a_{j}=\frac{\pi{u_{j}}}{2n},\
b_{i}=\frac{\pi{r_{i}}}{2m},\ b_{j}=\frac{\pi{r_{i}}}{2m}$ (8)

Then, using the Manhattan distance, the self-attention calculation can be
decomposed into four terms:

$\displaystyle{\mathcal{S}(Q_{i},K_{j})}=$
$\displaystyle\phi(Q_{i})(\cos(a_{i}-a_{j})+\cos(b_{i}-b_{j}))\phi({K_{j}})^{\top}$
(9) $\displaystyle=$
$\displaystyle\phi(Q_{i})(\cos(a_{i})\cos(a_{j}))\phi({K_{j}})^{\top}+$
$\displaystyle\phi(Q_{i})(\sin(a_{i})\sin(a_{j}))\phi({K_{j}})^{\top}+$
$\displaystyle\phi(Q_{i})(\cos(b_{i})\cos(b_{j}))\phi({K_{j}})^{\top}+$
$\displaystyle\phi(Q_{i})(\sin(b_{i})\sin(b_{j}))\phi({K_{j}})^{\top}$
$\displaystyle=$ $\displaystyle\phi^{\cos a_{i}}(Q_{i})\phi^{\cos
a_{j}}(K_{j})^{\top}+$ $\displaystyle\phi^{\sin a_{i}}(Q_{i})\phi^{\sin
a_{j}}(K_{j})^{\top}+$ $\displaystyle\phi^{\cos b_{i}}(Q_{i})\phi^{\cos
b_{j}}(K_{j})^{\top}+$ $\displaystyle\phi^{\sin b_{i}}(Q_{i})\phi^{\sin
b_{j}}(K_{j})^{\top}$

where $\textstyle\phi^{\cos y}(x)\triangleq\cos(y)\phi(x),\phi^{\sin
y}(x)\triangleq\sin(y)\phi(x)$.

The detailed derivation is included in the supplementary materials. Here the
queries and keys are related to their own positions $i$ and $j$, and hence we
can fulfill the Eq. (4) to reorder the dot product in self-attention. Our
method provides three appealing properties: (1) Linear complexity: cosine can
be decomposed, thus $KV$ is calculated first to ensure linear complexity. (2)
Locality bias: if two tokens are close to each other in 2D feature maps, they
are encouraged to have stronger relationships, as shown in Fig. 3. (3) Global
context: it retains a global receptive field as in the standard self-
attention.

###  4.2 Vicinity Attention Block

The theoretical computational complexity of Vicinity Attention is
$O(N(4d)^{2})$. To achieve a linear computational complexity, the sequence
length $N$ should be much larger than the feature dimension $d$. To ensure the
computational cost is close to linear, we redesign the structure of multi-head
self-attention (MSA) module to reduce the feature dimension without hindering
the performance.

We present a schematic illustration of our Vicinity Attention Block in Fig. 4.
It receives an input $X\in\mathbb{R}^{N\times d}$, which is projected into
$Q\in\mathbb{R}^{N\times\frac{d}{2}}$, $K\in\mathbb{R}^{N\times\frac{d}{2}}$,
$V\in\mathbb{R}^{N\times\frac{d}{2}}$ with a reduced feature dimension. We
call it Feature Reduction Attention (FRA). Then, following our locality
decomposition in Eq. (9), we obtain $Q^{{}^{\prime}}\in\mathbb{R}^{N\times
2d}$, $K^{{}^{\prime}}\in\mathbb{R}^{N\times 2d}$ which is used to calculate
linear self-attention. After that, since our self-attention is calculated in
lower dimensions, we add a skip connection called Feature Preserving
Connection (FRC) which has negligible computational overhead ($O(2d^{2})$). We
also adopt an average pooling operation and two linear layers to retain the
original feature distribution and strengthen the representational ability.
Given the feature dimension is reduced by 2, our current computational
complexity is $O(N(2d)^{2}+2d^{2})$.

In Figure 5, we show some qualitative examples of Grad-CAM [45] obtained from
the proposed VVT and ViT [2]. Our approach is able to produce fine-grained
features whereas the ViT [2] can only capture low-resolution features.

TABLE I: Detailed specifications of our VVT variants. We show four variants of
our VVT structure. C: Feature dimension, P: Patch size, R: Feature reduction,
H: Head number, E: Expansion ratio of the feed-forward layer. Following Swin
Transformer [23], the layers amount of the four stages follow the ratios of
$1:1:3:1$ or $1:1:9:1$.

| Output Size | Layer Name | Tiny | Small | Medium | Large
---|---|---|---|---|---|---
Stage 1 | $\frac{H}{4}\times\frac{W}{4}$ | Patch Embedding | C = 96, P = 4
| Transformer
---
Encoder
| $\begin{bmatrix}R=2\\\ H=1\\\ E=8\end{bmatrix}\times 2$
---
$\begin{bmatrix}R=2\\\ H=1\\\ E=8\end{bmatrix}\times 3$ | $\begin{bmatrix}R=2\\\ H=1\\\ E=8\end{bmatrix}\times 3$ | $\begin{bmatrix}R=2\\\ H=1\\\ E=4\end{bmatrix}\times 4$
Stage 2 | $\frac{H}{8}\times\frac{W}{8}$ | Patch Embedding | C = 160, P = 2
| Transformer
---
Encoder
$\begin{bmatrix}R=2\\\ H=2\\\ E=8\end{bmatrix}\times 2$ | $\begin{bmatrix}R=2\\\ H=2\\\ E=8\end{bmatrix}\times 3$ | $\begin{bmatrix}R=2\\\ H=2\\\ E=8\end{bmatrix}\times 3$ | $\begin{bmatrix}R=2\\\ H=2\\\ E=4\end{bmatrix}\times 4$
Stage 3 | $\frac{H}{16}\times\frac{W}{16}$ | Patch Embedding | C = 320, P = 2
| Transformer
---
Encoder
$\begin{bmatrix}R=2\\\ H=5\\\ E=4\end{bmatrix}\times 2$ | $\begin{bmatrix}R=2\\\ H=5\\\ E=4\end{bmatrix}\times 9$ | $\begin{bmatrix}R=2\\\ H=5\\\ E=4\end{bmatrix}\times 27$ | $\begin{bmatrix}R=2\\\ H=5\\\ E=4\end{bmatrix}\times 36$
Stage 4 | $\frac{H}{32}\times\frac{W}{32}$ | Patch Embedding | C = 512, P = 2
| Transformer
---
Encoder
$\begin{bmatrix}R=2\\\ H=8\\\ E=4\end{bmatrix}\times 2$ | $\begin{bmatrix}R=2\\\ H=8\\\ E=4\end{bmatrix}\times 3$ | $\begin{bmatrix}R=2\\\ H=8\\\ E=4\end{bmatrix}\times 3$ | $\begin{bmatrix}R=2\\\ H=8\\\ E=4\end{bmatrix}\times 4$

###  4.3 The Vicinity Vision Transformer

To validate the effectiveness of our idea, we propose a general-purpose vision
backbone called Vicinity Vision Transformer (VVT), as shown in Fig. 6. VVT
adopts a progressive shrinking pyramid structure and has four stages that
generate feature maps at different scales. Each stage contains a patch
embedding layer and multiple Vicinity Transformer Blocks. In detail, we use a
patch size of $4\times 4$ in the first stage. Given the input image of size
$H\times W\times 3$, we first divide it into $\frac{H}{4}\times\frac{W}{4}$
patches. Then we feed the patches into a patch embedding module to obtain a
flattened embedding sequence with size of $\frac{HW}{4^{2}}\times C_{1}$. Here
we adopt the patch embedding module proposed by [46] to project the patches
into the target feature embedding. The embedding sequence is subsequently fed
into several successive transformer blocks with $L_{1}$ layers.

Compared with the standard transformer block, we only replace the multi-head
self-attention (MSA) module with our proposed linear Vicinity Attention Block,
while other parts are kept the same. In the second stage, the feature sequence
from the first stage is reshaped back to $\frac{H}{4}\times\frac{W}{4}\times
C_{1}$ and fed into the patch embedding module again. It is projected and
down-sampled to a embedding sequence of size $\frac{HW}{8^{2}}\times C_{2}$,
and then processed by the transformer blocks of the second stage. We follow
the same approach to obtain multi-scale output feature maps of the third and
fourth stage with output sizes of $\frac{H}{16}\times\frac{W}{16}$ and
$\frac{H}{32}\times\frac{W}{32}$, respectively. Hierarchical feature maps can
be easily leveraged to many downstream tasks such as image classification,
semantic segmentation and object detection. Similar to other backbone methods,
we introduce different architecture variants like VVT-Tiny or VVT-Large, whose
details are shown in Table I.

##  5 Experiments

To verify the effectiveness of our method, we conduct extensive experiments on
the CIFAR100 [47] and ImageNet1K [39] datasets for image classification, and
on the ADE20K [48] dataset for semantic segmentation. Specifically, we first
make a comparison with existing state-of-the-art methods, and then give an
ablation study over the design of VVT.

###  5.1 Image Classification

TABLE II: Comparison of different backbones on ImageNet1k[39]. All models are
trained and tested on $224\times 224$ resolution. GFLOPs is also calculated
under the input scale of $224\times 224$. MS out represents multi-scale
output.

Method | Style | Resolution | MS out | Param | GFLOPs | Top-1 Acc(%)
---|---|---|---|---|---|---
ResNet18[16] | ConvNets | $224^{2}$ | ${\color[rgb]{0,127,0}\checkmark}$ | 11.7 | 1.8 | 69.8
DeiT-Tiny/16[49] | Transformers | $224^{2}$ | ✗ | 5.7 | 1.3 | 72.2
PVTv2-B1[46] | Transformers | $224^{2}$ | ${\color[rgb]{0,127,0}\checkmark}$ | 13.1 | 2.1 | 78.7
VVT-T(ours) | Transformers | $224^{2}$ | ${\color[rgb]{0,127,0}\checkmark}$ | 12.9 | 3.0 | 79.2
ResNet50[16] | ConvNets | $224^{2}$ | ${\color[rgb]{0,127,0}\checkmark}$ | 25.6 | 4.1 | 76.1
PVT-Small[24] | Transformers | $224^{2}$ | ${\color[rgb]{0,127,0}\checkmark}$ | 24.5 | 3.8 | 79.8
RegNetY-4G[50] | ConvNets | $224^{2}$ | ${\color[rgb]{0,127,0}\checkmark}$ | 21.0 | 4.0 | 80.0
TNT-S[11] | Transformers | $224^{2}$ | ✗ | 23.8 | 5.2 | 81.3
Swin-T[23] | Transformers | $224^{2}$ | ${\color[rgb]{0,127,0}\checkmark}$ | 29.0 | 4.5 | 81.6
CvT-13[10] | Hybrid | $224^{2}$ | ${\color[rgb]{0,127,0}\checkmark}$ | 20.0 | 4.5 | 81.6
Twins-SVT-S[25] | Hybrid | $224^{2}$ | ${\color[rgb]{0,127,0}\checkmark}$ | 24.0 | 2.8 | 81.7
XCiT-S12[51] | Linear Transformers | $224^{2}$ | ✗ | 26.0 | 4.8 | 82.0
PVTv2-B2-Li[46] | Transformers | $224^{2}$ | ${\color[rgb]{0,127,0}\checkmark}$ | 22.6 | 3.9 | 82.1
SOFT[32] | Linear Transformers | $224^{2}$ | ${\color[rgb]{0,127,0}\checkmark}$ | 24.0 | 3.3 | 82.2
VVT-S(ours) | Linear Transformers | $224^{2}$ | ${\color[rgb]{0,127,0}\checkmark}$ | 25.5 | 5.6 | 82.6
ResNet101[16] | ConvNets | $224^{2}$ | ${\color[rgb]{0,127,0}\checkmark}$ | 44.7 | 7.9 | 77.4
ViT-Small16[2] | Transformers | $224^{2}$ | ✗ | 48.8 | 9.9 | 80.8
PVT-Medium[24] | Transformers | $224^{2}$ | ${\color[rgb]{0,127,0}\checkmark}$ | 44.2 | 6.7 | 81.2
RegNetY-8G[50] | ConvNets | $224^{2}$ | ${\color[rgb]{0,127,0}\checkmark}$ | 39.0 | 8.0 | 81.7
CvT-21[10] | Hybrid | $224^{2}$ | ${\color[rgb]{0,127,0}\checkmark}$ | 32.0 | 7.1 | 82.5
XCiT-S24[51] | Linear Transformers | $224^{2}$ | ✗ | 48.0 | 9.1 | 82.6
SOFT[32] | Linear Transformers | $224^{2}$ | ${\color[rgb]{0,127,0}\checkmark}$ | 45.0 | 7.2 | 82.9
Swin-S[23] | Transformers | $224^{2}$ | ${\color[rgb]{0,127,0}\checkmark}$ | 50.0 | 8.7 | 83.0
Twins-SVT-B[25] | Hybrid | $224^{2}$ | ${\color[rgb]{0,127,0}\checkmark}$ | 56.0 | 8.3 | 83.2
PVTv2-B3[46] | Transformers | $224^{2}$ | ${\color[rgb]{0,127,0}\checkmark}$ | 45.2 | 6.9 | 83.2
PVTv2-B4[46] | Transformers | $224^{2}$ | ${\color[rgb]{0,127,0}\checkmark}$ | 62.6 | 10.1 | 83.6
VVT-M(ours) | Linear Transformers | $224^{2}$ | ${\color[rgb]{0,127,0}\checkmark}$ | 47.9 | 9.4 | 83.8
ResNet152[16] | ConvNets | $224^{2}$ | ${\color[rgb]{0,127,0}\checkmark}$ | 60.2 | 11.6 | 78.3
PVT-Large[24] | Transformers | $224^{2}$ | ${\color[rgb]{0,127,0}\checkmark}$ | 61.4 | 9.8 | 81.7
ViT-Base16[2] | Transformers | $224^{2}$ | ✗ | 86.6 | 16.0 | 81.8
T2T-ViT-24[26] | Transformers | $224^{2}$ | ${\color[rgb]{0,127,0}\checkmark}$ | 63.9 | 13.2 | 82.2
XCiT-M24[51] | Linear Transformers | $224^{2}$ | ✗ | 84.0 | 16.2 | 82.7
ResNeXt101-64x4d[52] | ConvNets | $224^{2}$ | ${\color[rgb]{0,127,0}\checkmark}$ | 84.0 | 16.0 | 82.9
TNT-B[11] | Transformers | $224^{2}$ | ✗ | 65.6 | 14.1 | 82.9
RegNetY-16G[50] | ConvNets | $224^{2}$ | ${\color[rgb]{0,127,0}\checkmark}$ | 84.0 | 16.0 | 82.9
SOFT[32] | Linear Transformers | $224^{2}$ | ${\color[rgb]{0,127,0}\checkmark}$ | 64.0 | 11.0 | 83.1
Swin-B[23] | Transformers | $224^{2}$ | ${\color[rgb]{0,127,0}\checkmark}$ | 88.0 | 15.4 | 83.3
Twins-SVT-L[25] | Hybrid | $224^{2}$ | ${\color[rgb]{0,127,0}\checkmark}$ | 99.2 | 14.8 | 83.7
PVTv2-B5[46] | Transformers | $224^{2}$ | ${\color[rgb]{0,127,0}\checkmark}$ | 82.0 | 11.8 | 83.8
VVT-L(ours) | Linear Transformers | $224^{2}$ | ${\color[rgb]{0,127,0}\checkmark}$ | 61.8 | 10.8 | 84.1

The image classification experiments are conducted on the ImageNet1K [39]
dataset, which contains 1.28 million training images and 50 thousand
validation images from $1,000$ categories. We follow the training hyper-
parameters of PVT [24] for a fair comparison. In detail, the model is trained
using an AdamW [53] optimizer with a weight decay of $0.05$ and a momentum of
$0.9$. We use an initial learning rate of $5\times 10^{-4}$ and decrease it by
a cosine schedule [54], with $5$ epochs for warming up. We also adopt the same
data augmentation strategy as in [24], including random cropping, random
horizontal flipping, _etc._ All the models are trained on the training set for
$300$ epochs with a crop size of $224\times 224$. We use the top-1 accuracy as
the evaluation metric.

The quantitative results are shown in Table II, which covers the popular
transformer-based and CNN-based classification networks. We compare the VVT
variants respectively with the networks using similar parameters, split by
solid lines. For example, VVT-L performs better than PVTv2-B5 [24] but only
uses around 70% parameters of the latter. In particular, our medium-size
variant VVT-M surpasses the large models Twins-SVT-L [25] and Swin-B [23] with
substantially fewer parameters (51.7% and 45.5% respectively). Moreover,
compared to the state-of-the-art CNN-based networks such as RegNet [55] and
ResNeXt [52], VVT shows stronger performance while using a similar number of
parameters.

It is worth noting that VVT directly computes self-attention on the high-
resolution feature maps, while the competitors such as PVT [24], Swin
Transformer [23], Twins [25] and SOFT [32] rely on the sub-sampling or window
self-attention to reduce computational cost. The GFLOPs of VVT could be
further reduced if similar subsampling or windowing was used.

TABLE III: Semantic segmentation results on ADE20K[48] validation set.
Competing results come from PVTv2 [46] and Twins [25]. All backbone networks
are pre-trained on ImageNet1k[39].

Method |  Semantic FPN(PVT[24] setting) |  Upernet(Swin[23] setting)
---|---|---
Params | GFLOPs | mIoU(%) | Params | GFLOPs | mIoU(%)
ResNet50 [16] | 28.5 | 45.6 | 36.7 | - | - | -
PVT-Small[24] | 28.2 | 44.5 | 39.8 | - | - | -
Swin-T[23] | 31.9 | 46.0 | 41.5 | 59.9 | 237 | 44.5
Twins-SVT-S[25] | 28.3 | 37.0 | 43.2 | 54.4 | 228 | 46.2
PVTv2-b2[46] | 29.1 | 45.8 | 45.2 | - | - | -
VVT-S(ours) | 29.2 | 50.9 | 45.6 | 55.5 | 240 | 46.8
ResNet101[16] | 47.5 | 65.1 | 38.8 | - | - | -
ResNeXt101-32x4d[52] | 47.1 | 64.7 | 39.7 | - | - | -
PVT-Medium[24] | 51.6 | 61.0 | 41.6 | - | - | -
SWIN-S[23] | 53.2 | 70.0 | 45.2 | 81.3 | 261 | 47.6
Twins-SVT-B[25] | 60.4 | 67.0 | 45.3 | 88.5 | 261 | 47.7
PVTv2-b3[46] | 49.0 | 62.4 | 47.3 | - | - | -
VVT-M(ours) | 51.7 | 70.8 | 47.4 | 77.9 | 260 | 48.1
ResNeXt101-64x4d [52] | 86.4 | 103.9 | 40.2 | - | - | -
PVT-Large[24] | 65.1 | 79.6 | 42.1 | - | - | -
SWIN-B[23] | 91.2 | 107.0 | 46.0 | 121 | 299 | 48.1
Twins-SVT-L[25] | 103.7 | 102.0 | 46.7 | 133 | 297 | 48.8
PVTv2-b4[46] | 66.3 | 81.3 | 47.9 | - | - | -
VVT-L(ours) | 65.5 | 78.1 | 47.9 | 91.9 | 267 | 48.8

Figure 7: Qualitative results of semantic segmentation on ADE20K[48]. The
results are generated by VVT-L based Semantic FPN[56].

###  5.2 Semantic Segmentation

We utilize the challenging ADE20K [48] dataset to evaluate our idea in
semantic segmentation. It has $150$ semantic classes, with $20,210$, $2,000$
and $3,352$ images for training, validation and testing. With the VVT models
(pre-trained on ImageNet1K) as the backbone, we provide the results using two
segmentation methods in Table III. Specifically, we pick Semantic FPN [56] and
UperNet [57] as the semantic segmentation architecture, respectively following
the settings of PVT [24] and Swin Transformer [23] The quantitative results
show that our method is consistently superior to the competing CNN-based
methods. For example, using Semantic FPN, VVT-S outperforms ResNet50 [16] by
8.9%, and VVT-L is 7.7% better than ResNeXt101-32x4d [52], using mIoU as the
metric. VVT also shows a more favourable segmentation result than the
transformer-based competitors such as the Swin Transformer. A similar
phenomenon is observed if taking UperNet [57] as the segmentation method.
These results validate that the extracted features of VVT are also valuable
for semantic segmentation, which benefits from the locality mechanism together
with the global attention.

###  5.3 Ablation Study

Computational Overhead. We plot the GFLOPs growth rates with respect to the
input image size on the right of Fig. 1. The GFLOPs growth rate of VVT
(purple) is substantially lower than other transformer-based methods, and even
slightly lower than ResNet [16]. Note that PVT [24] down-samples the sequence
length to reduce the computational complexity, whereas we directly compute
self-attention without any spatial reduction. If PVT computes self-attention
on the full-length inputs (labeled as PVT_no_SR, grey in Fig. 1), its GFLOP
growth rate becomes notably larger and will exhaust the GPU memory (32G) once
the image size exceeds $640\times 640$. This ablation study validates that VVT
successfully mitigates the computational issue in the vision transformers.

TABLE IV: Analysis of locality constraint on Cifar100[47] and ImageNet1K[39]. The VVT-softmax represents the variant that replaces all Vicinity Attention with the standard softmax attention.  Datasets | Method | Top-1 Acc(%)
---|---|---
Cifar100 | PVT [24] | 81.67
VVT-softmax | 82.68
VVT w/o locality | 82.13
VVT 1D locality | 76.78
VVT 2D locality | 82.92
ImageNet1K | VVT w/o locality | 78.0
VVT 2D locality | 79.2
Figure 8: We compare the class-wise attention maps of the VVT against the VVT
w/o locality, the PVT[24] and the ViT[2]. The attention maps are obtained
using Grad_CAM[45]. By enforcing the locality bias, the activation areas are
more concentrated and correctly locate on the object.

Effect of Locality Constraint. The Vicinity locality mechanism is introduced
in the self-attention module of VVT. We show its effectiveness on the
CIFAR-100 [47] and the ImageNet1K [39] datasets in Table IV. Experiments are
performed on the VVT-Tiny structure. We compare the VVT with the one without
locality (denoted as VVT w/o locality) and the one with 1D locality (denoted
as VVT 1D locality). We add the state-of-the-art vision transformer PVT [24]
as our reference. For the sake of completeness, we also provide a VVT variant
that replaces all Vicinity Attention with the standard softmax attention, and
denote it as the VVT-softmax. As shown in the table, our VVT achieves the best
performance among all the others, even better than the one with standard
softmax attention while it also has only linear computation complexity. By
comparing the VVT w/o locality and VVT 1D locality, we can find that if we
wrongly enforce the locality bias, the performance will drop critically. To
further demonstrate its effectiveness on large-scale data, we also conduct the
ablation on the ImageNet1K [18], where our VVT outperforms the VVT w/o
locality by $1.2\%$.

Furthermore, we show the qualitative examples of Grad-CAM [45] from VVT and
the competitors in Fig. 8. As shown, the locality mechanism encourages the
tokens to assign higher attention to 2D neighbours, and hence the class-wise
activations are more concentrated and accurately located on the target object
regions of Grad-CAM. These results validate that the introduction of the 2D
locality mechanism helps the VVT models generate more reliable object
features, which tend to be beneficial in image classification and downstream
tasks.

Analysis of Vicinity Attention. In order to demonstrate the effectiveness of
our proposed Vicinity attention module solely. We adopt same network structure
and replace Vicinity attention with other efficient attention modules
including vanilla attention[1], Performer[7], Linformer[31], PVTv2[46] and
[33]. Results on Cifar100 are reported in Table V. As shown, under the same
network architecture setting, our Vicinity attention outperforms both the
vanilla attention and all the alternative efficient ones.

TABLE V: Ablation of different attention choices. We fix the architecture to VVT-T and test different attention modules on Cifar100. Architecture | Attention | Param | Top-1 Acc($\%$)
---|---|---|---
VVT-T | Efficient attention[33] | 12.4 | 81.63
VVT-T | Performer[7] | 12.4 | 79.86
VVT-T | Linformer[31] | 13.1 | 80.95
VVT-T | PVTv2[46] | 15.2 | 82.16
VVT-T | Vanilla[1] | 12.4 | 82.68
VVT-T | Ours | 12.4 | 82.92

Analysis of Feature Reduction. In the Vicinity Attention Block, we reduce the
feature dimension to fulfill the assumption of $N\gg d$, which forces the
computational complexity to approach linear. In Fig. 9, we ablate the
computational cost under different feature reduction (FR) ratios. We can
observe an obvious GFLOPs decrease when increasing the FR ratio from 1 to 2
(reducing the feature dimension by half). However, when the FR ratio further
increases, the reduction tends to saturate. This is because the computational
cost of the self-attention module is already significantly reduced and the
other model parts dominate the computational overhead. Additionally, we ablate
the performances under different FR ratios on the Cifar100 dataset, as shown
in Table VI. As shown, when the FR ratio is small, the model retains a similar
performance (_e.g._ , 82.89% vs. 82.92%), indicating that the feature
representation ability is not affected. When the FR ratio increases to a
number like 8, a clear performance drop is observed. As a trade-off, we set
the FR ratio as 2 for our formal model settings.

Figure 9: GFLOPs of VVT using different feature reduction rates. When FR ratio is increased larger than 4, the growth ratio tends to be saturated. TABLE VI: Results of VVT using different feature reduction ratio(FR). We empirically find that the $\text{FR}=2$ leads to the best performance. Method | Feature Reduction ratio | Top-1 Acc(%)
---|---|---
PVT[24] | – | 81.67
VVT | FR=1 | 82.89
VVT | FR=2 | 82.92
VVT | FR=4 | 82.00
VVT | FR=8 | 80.60

Feature Preserving Connection. In the Vicinity Attention Block, feature
preserving connections are added to compensate reduced feature dimensions.
Ablation of feature preserving connection is reported in Table VII. The
results indicate that feature preserving connection effectively retains
original feature distribution, and improves feature extraction ability of
Vicinity attention module even feature dimension is reduced.

TABLE VII: Results of VVT-tiny with and without feature preserving connection(FPC) on ImageNet1k. Method | Feature Preserving Connection | Top-1 Acc(%)
---|---|---
VVT | ✗ | 77.9
VVT | ✓ | 79.2

Image Classification with Different Input Size Table VIII lists the
performances of VVT with a higher input resolution i.e., 384. Obviously,
larger input resolution leads to better top-1 accuracy but requires larger
computation. Compared to Swin[23], VVT achieves better results with similar or
lower computational overhead.

TABLE VIII: Classification results on ImageNet1k under the input scale 384 $\times$ 384. Method |  Param |  GFLOPs |  Top-1 Acc(%)
---|---|---|---
VVT-T |  12.9 |  8.8 |  80.3
Swin-T[23] |  29.0 |  14.0 |  82.2
VVT-S |  25.5 |  16.5 |  83.4
Swin-B[23] |  88.0 |  47.0 |  84.5
VVT-L |  61.8 |  31.8 |  84.7

Image Classification Throughputs Fig.10 illustrates actual image throughputs
of the proposed VVT compared to PVTv2[46] and Swin transformer[23], we run the
test on one local 2080 Ti GPU with 10 Gb memory. Since the theoretical
computational complexity of Vicinity attention is $O(N(2d)^{2}+2d^{2})$, in
low resolution regime where sequence length $N$ does not dominate the
complexity, VVT shows relatively slow speed compared to PVTv2[46] and
Swin[23]. However, when input resolution is gradually increased, the VVT
starts demonstrating better inference speed, while competing methods exhaust
GPU memory in the high resolution regime.

Figure 10: Throughputs-resolution curve. We take $log$ of throughputs for
better readability.

##  6 Conclusion

We have introduced Vicinity Vision Transformer (VVT), a general-purpose vision
backbone that produces hierarchical feature representations through a pyramid
structure. At its core, VVT uses a novel Vicinity Attention Block, which
introduces a 2D locality mechanism into the self-attention module. We validate
that this locality mechanism improves results and helps generate better class
activations. Further, because Vicinity Attention has linear complexity, it
facilitates processing feature maps or input images with higher resolutions.
The proposed VVT has been validated with strong performance on both image
classification and semantic segmentation. Future work will be aimed at using
neural architecture search to further improve upon architectures specifically
designed for linear vision transformers.

## References

  * [1] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, and I. Polosukhin, “Attention is all you need,” Advances in neural information processing systems, vol. 30, 2017.
  * [2] A. Dosovitskiy, L. Beyer, A. Kolesnikov, D. Weissenborn, X. Zhai, T. Unterthiner, M. Dehghani, M. Minderer, G. Heigold, S. Gelly, et al., “An image is worth 16x16 words: Transformers for image recognition at scale,” arXiv preprint arXiv:2010.11929, 2020.
  * [3] X. Cheng, H. Xiong, D.-P. Fan, Y. Zhong, M. Harandi, T. Drummond, and Z. Ge, “Implicit motion handling for video camouflaged object detection,” in Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 13864–13873, 2022.
  * [4] W. Sun, J. Zhang, Z. Liu, Y. Zhong, and N. Barnes, “GETAM: gradient-weighted element-wise transformer attention map for weakly-supervised semantic segmentation,” CoRR, vol. abs/2112.02841, 2021.
  * [5] Y. Xiong, Z. Zeng, R. Chakraborty, M. Tan, G. Fung, Y. Li, and V. Singh, “Nyströmformer: A nystöm-based algorithm for approximating self-attention,” in Proceedings of the… AAAI Conference on Artificial Intelligence. AAAI Conference on Artificial Intelligence, vol. 35, p. 14138, NIH Public Access, 2021.
  * [6] H. Peng, N. Pappas, D. Yogatama, R. Schwartz, N. A. Smith, and L. Kong, “Random feature attention,” arXiv preprint arXiv:2103.02143, 2021.
  * [7] K. Choromanski, V. Likhosherstov, D. Dohan, X. Song, A. Gane, T. Sarlos, P. Hawkins, J. Davis, A. Mohiuddin, L. Kaiser, et al., “Rethinking attention with performers,” arXiv preprint arXiv:2009.14794, 2020.
  * [8] A. Katharopoulos, A. Vyas, N. Pappas, and F. Fleuret, “Transformers are rnns: Fast autoregressive transformers with linear attention,” in International Conference on Machine Learning, pp. 5156–5165, PMLR, 2020.
  * [9] Q. Zhen, W. Sun, H. Deng, D. Li, Y. Wei, B. Lv, J. Yan, L. Kong, and Y. Zhong, “cosformer: Rethinking softmax in attention,” in International Conference on Learning Representations, 2022.
  * [10] H. Wu, B. Xiao, N. Codella, M. Liu, X. Dai, L. Yuan, and L. Zhang, “Cvt: Introducing convolutions to vision transformers,” in Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 22–31, 2021.
  * [11] K. Han, A. Xiao, E. Wu, J. Guo, C. Xu, and Y. Wang, “Transformer in transformer,” Advances in Neural Information Processing Systems, vol. 34, 2021.
  * [12] L. Yuan, Y. Chen, T. Wang, W. Yu, Y. Shi, Z.-H. Jiang, F. E. Tay, J. Feng, and S. Yan, “Tokens-to-token vit: Training vision transformers from scratch on imagenet,” in Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 558–567, 2021.
  * [13] Z. Dai, H. Liu, Q. Le, and M. Tan, “Coatnet: Marrying convolution and attention for all data sizes,” Advances in Neural Information Processing Systems, vol. 34, 2021.
  * [14] Y. Zhong, Y. Dai, and H. Li, “Self-supervised learning for stereo matching with self-improving ability,” arXiv preprint arXiv:1709.00930, 2017.
  * [15] Y. Zhong, Y. Dai, and H. Li, “Stereo computation for a single mixture image,” in Proceedings of the European Conference on Computer Vision (ECCV), September 2018.
  * [16] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 770–778, 2016.
  * [17] T.-Y. Lin, P. Dollár, R. Girshick, K. He, B. Hariharan, and S. Belongie, “Feature pyramid networks for object detection,” in Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 2117–2125, 2017\.
  * [18] A. Krizhevsky, I. Sutskever, and G. E. Hinton, “Imagenet classification with deep convolutional neural networks,” Advances in neural information processing systems, vol. 25, 2012.
  * [19] H. Hu, Z. Zhang, Z. Xie, and S. Lin, “Local relation networks for image recognition,” in Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 3464–3473, 2019.
  * [20] P. Ramachandran, N. Parmar, A. Vaswani, I. Bello, A. Levskaya, and J. Shlens, “Stand-alone self-attention in vision models,” Advances in Neural Information Processing Systems, vol. 32, 2019.
  * [21] H. Zhao, J. Jia, and V. Koltun, “Exploring self-attention for image recognition,” in Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 10076–10085, 2020.
  * [22] X. Wang, R. Girshick, A. Gupta, and K. He, “Non-local neural networks,” in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2018.
  * [23] Z. Liu, Y. Lin, Y. Cao, H. Hu, Y. Wei, Z. Zhang, S. Lin, and B. Guo, “Swin transformer: Hierarchical vision transformer using shifted windows,” in IEEE International Conference on Computer Vision (ICCV), 2021.
  * [24] W. Wang, E. Xie, X. Li, D.-P. Fan, K. Song, D. Liang, T. Lu, P. Luo, and L. Shao, “Pyramid vision transformer: A versatile backbone for dense prediction without convolutions,” in Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV), pp. 568–578, October 2021\.
  * [25] X. Chu, Z. Tian, Y. Wang, B. Zhang, H. Ren, X. Wei, H. Xia, and C. Shen, “Twins: Revisiting the design of spatial attention in vision transformers,” Advances in Neural Information Processing Systems, vol. 34, 2021.
  * [26] L. Yuan, Y. Chen, T. Wang, W. Yu, Y. Shi, Z. Jiang, F. E. Tay, J. Feng, and S. Yan, “Tokens-to-token vit: Training vision transformers from scratch on imagenet,” 2021.
  * [27] R. Child, S. Gray, A. Radford, and I. Sutskever, “Generating long sequences with sparse transformers,” arXiv preprint arXiv:1904.10509, 2019.
  * [28] I. Beltagy, M. E. Peters, and A. Cohan, “Longformer: The long-document transformer,” arXiv preprint arXiv:2004.05150, 2020.
  * [29] N. Kitaev, Ł. Kaiser, and A. Levskaya, “Reformer: The efficient transformer,” arXiv preprint arXiv:2001.04451, 2020.
  * [30] G. Daras, N. Kitaev, A. Odena, and A. G. Dimakis, “Smyrf-efficient attention using asymmetric clustering,” Advances in Neural Information Processing Systems, vol. 33, pp. 6476–6489, 2020.
  * [31] S. Wang, B. Z. Li, M. Khabsa, H. Fang, and H. Ma, “Linformer: Self-attention with linear complexity,” arXiv preprint arXiv:2006.04768, 2020.
  * [32] J. Lu, J. Yao, J. Zhang, X. Zhu, H. Xu, W. Gao, C. Xu, T. Xiang, and L. Zhang, “Soft: Softmax-free transformer with linear complexity,” Advances in Neural Information Processing Systems, vol. 34, 2021.
  * [33] Z. Shen, M. Zhang, H. Zhao, S. Yi, and H. Li, “Efficient attention: Attention with linear complexities,” in Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision, pp. 3531–3539, 2021.
  * [34] Y. Zhong, P. Ji, J. Wang, Y. Dai, and H. Li, “Unsupervised deep epipolar flow for stationary or dynamic scenes,” in CVPR, 2019.
  * [35] J. Wang, Y. Zhong, Y. Dai, S. Birchfield, K. Zhang, N. Smolyanskiy, and H. Li, “Deep two-view structure-from-motion revisited,” in Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 8953–8962, June 2021.
  * [36] X. Cheng, Y. Zhong, Y. Dai, P. Ji, and H. Li, “Noise-aware unsupervised deep lidar-stereo fusion,” in CVPR, 2019.
  * [37] Y. Zhong, H. Li, and Y. Dai, “Open-world stereo video matching with deep rnn,” in ECCV, 2018.
  * [38] W. Sun, J. Zhang, and N. Barnes, “Inferring the class conditional response map for weakly supervised semantic segmentation,” in Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision, pp. 2878–2887, 2022.
  * [39] J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei, “Imagenet: A large-scale hierarchical image database,” in 2009 IEEE conference on computer vision and pattern recognition, pp. 248–255, Ieee, 2009.
  * [40] Y. Zhong, Y. Dai, and H. Li, “3d geometry-aware semantic labeling of outdoor street scenes,” in 2018 24th International Conference on Pattern Recognition (ICPR), pp. 2343–2349, IEEE, 2018.
  * [41] X. Chu, B. Zhang, Z. Tian, X. Wei, and H. Xia, “Do we really need explicit position encodings for vision transformers?,” arXiv e-prints, pp. arXiv–2102, 2021.
  * [42] K. Clark, U. Khandelwal, O. Levy, and C. D. Manning, “What does bert look at? an analysis of bert’s attention,” arXiv preprint arXiv:1906.04341, 2019\.
  * [43] O. Kovaleva, A. Romanov, A. Rogers, and A. Rumshisky, “Revealing the dark secrets of bert,” arXiv preprint arXiv:1908.08593, 2019.
  * [44] H. Minkowski, Geometrie der zahlen, vol. 40.  Teubner, 1910.
  * [45] R. R. Selvaraju, M. Cogswell, A. Das, R. Vedantam, D. Parikh, and D. Batra, “Grad-cam: Visual explanations from deep networks via gradient-based localization,” in Proceedings of the IEEE international conference on computer vision, pp. 618–626, 2017.
  * [46] W. Wang, E. Xie, X. Li, D.-P. Fan, K. Song, D. Liang, T. Lu, P. Luo, and L. Shao, “Pvtv2: Improved baselines with pyramid vision transformer,” 2022.
  * [47] A. Krizhevsky, G. Hinton, et al., “Learning multiple layers of features from tiny images,” 2009.
  * [48] B. Zhou, H. Zhao, X. Puig, S. Fidler, A. Barriuso, and A. Torralba, “Scene parsing through ade20k dataset,” in Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 633–641, 2017.
  * [49] H. Touvron, M. Cord, M. Douze, F. Massa, A. Sablayrolles, and H. Jégou, “Training data-efficient image transformers distillation through attention,” 2021.
  * [50] J. Xu, Y. Pan, X. Pan, S. Hoi, Z. Yi, and Z. Xu, “Regnet: Self-regulated network for image classification,” 2021.
  * [51] A. Ali, H. Touvron, M. Caron, P. Bojanowski, M. Douze, A. Joulin, I. Laptev, N. Neverova, G. Synnaeve, J. Verbeek, et al., “Xcit: Cross-covariance image transformers,” Advances in neural information processing systems, vol. 34, 2021.
  * [52] S. Xie, R. Girshick, P. Dollár, Z. Tu, and K. He, “Aggregated residual transformations for deep neural networks,” 2017.
  * [53] D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” 2017.
  * [54] I. Loshchilov and F. Hutter, “Sgdr: Stochastic gradient descent with warm restarts,” arXiv preprint arXiv:1608.03983, 2016.
  * [55] I. Radosavovic, R. P. Kosaraju, R. Girshick, K. He, and P. Dollár, “Designing network design spaces,” 2020.
  * [56] A. Kirillov, R. Girshick, K. He, and P. Dollár, “Panoptic feature pyramid networks,” in Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 6399–6408, 2019.
  * [57] T. Xiao, Y. Liu, B. Zhou, Y. Jiang, and J. Sun, “Unified perceptual parsing for scene understanding,” in Proceedings of the European Conference on Computer Vision (ECCV), pp. 418–434, 2018.


# Sublacunary sequences that are strong sweeping out

Sovanlal Mondal Supported by the National Science Foundation, grant number
DMS-1855745. Madhumita Roy and Máté Wierdl
Department of Mathematical Sciences  University of Memphis
Memphis  TN 38152  USA
email<EMAIL_ADDRESS>
###### Abstract

An increasing sequence $(a_{n})$ of positive integers which satisfies
$\frac{a_{n+1}}{a_{n}}>1+\eta$ for some positive $\eta$ is called a lacunary
sequence. It has been known for over twenty years that every lacunary sequence
is strong sweeping out which means that in every aperiodic dynamical system we
can find a set $E$ of arbitrary small measure so that
$\limsup_{N}\frac{1}{N}\sum_{n\leq N}\mathds{1}_{E}(T^{n}x)=1$ and
$\liminf_{N}\frac{1}{N}\sum_{n\leq N}\mathds{1}_{E}(T^{n}x)=0$ almost
everywhere. In this paper we improve this result by showing that if $(a_{n})$
satisfies only $\frac{a_{n+1}}{a_{n}}>1+\frac{1}{(\log\log n)^{1-\eta}}$ for
some positive $\eta$ then it is already strong sweeping out.

###### Contents

  1. 1 Introduction and main results:
  2. 2 Proof of the main results:
  3. 3 Open Problems

##  1 Introduction and main results:

Throughout this paper, we use the notation

$[N]\coloneqq\left\\{1,2,\dots,N\right\\}$ (1.1)

Let $T$ be a measure preserving transformation on the probability space
$(X,\Sigma,\mu)$. After Birkhoff’s pointwise ergodic theorem was proved,
naturally the question was raised whether it is possible to generalize the
theorem along any subsequence $(a_{n})$ of integers instead of taking the
entire sequence $(n)$. Krengel[14] was the one who first constructed a
strictly increasing sequence $(a_{n})$ of positive integers so that in every
aperiodic system the ergodic averages
$\frac{1}{N}\displaystyle\sum_{n\in[N]}f(T^{a_{n}}x)$ diverge almost
everywhere. Soon after, Bellow[2] showed that if $(a_{n})$ is a _lacunary
sequence_ , that is, it satisfies $\frac{a_{n+1}}{a_{n}}\geq 1+\eta$ for some
positive $\eta$, then the ergodic averages along $(a_{n})$ diverge a.e. in
every aperiodic system, though she showed divergence only for $f\in L^{p}$ for
$p<\infty$. Our first main result provides a growth condition for a sequence
to be _pointwise bad_ which applies to _non lacunary sequences_ as well, that
is sequences for which $\lim_{n}\frac{a_{n+1}}{a_{n}}=1$.

######  Theorem 1 (label=thm:1).

Strong sweeping out with deterministic conditionSuppose $(a_{n})$ is a
sequence which satisfies

$\frac{a_{n+1}}{a_{n}}\geq 1+{\frac{1}{(\log\log n)^{1-\eta}}}$ (1.2)

for some $\eta>0$.

Then in every aperiodic dynamical system $(X,\Sigma,\mu,T)$ and every
$\epsilon>0$, there exists a set $E\in\Sigma$ with $\mu(E)<\epsilon$ such that
for almost every $x\in X$, we have

$\displaystyle\limsup_{N\to\infty}\frac{1}{N}\sum_{n\in[N]}\mathds{1}_{E}(T^{a_{n}}x)$
$\displaystyle=1$ (1.3) and
$\displaystyle\liminf_{N\to\infty}\frac{1}{N}\sum_{n\in[N]}\mathds{1}_{E}(T^{a_{n}}x)$
$\displaystyle=0$ (1.4)

An example of a sequence $(a_{n})$ which satisfies the growth condition in eq.
1.2 is $a_{n}=\lfloor e^{\frac{n}{(\log\log n)^{1-\eta}}}\rfloor$, for some
$\eta>0$.

######  Definition 2 (label=defn:3).

Pointwise good and bad sequencesLet $1\leq p\leq\infty$ and $(a_{n})$ be a
sequence of positive integers.

We say $(a_{n})$ is _pointwise good_ for $L^{p}$ if for every measure
preserving system $(X,\Sigma,\mu,T)$ and every $f\in L^{p}(X)$,
$\displaystyle\lim_{N\to\infty}\frac{1}{N}\sum_{n\in[N]}f(T^{a_{n}}x)$ exists
a.e.

We say the sequence $(a_{n})$ is _pointwise bad_ for $L^{p}$ if for every
aperiodic measure preserving system $(X,\Sigma,\mu,T)$ there exists a function
$f\in L^{p}(X)$ such that
$\displaystyle\lim_{N\to\infty}\frac{1}{N}\sum_{n\in[N]}f(T^{a_{n}}x)$ fails
to exist a.e.

Whether a sequence will be pointwise good or bad for $L^{p}$ depends on many
factors, such as, the speed of the sequence $(a_{n})$, the value of $p$, and
sometimes the intrinsic arithmetic properties of the sequence $(a_{n})$. From
LABEL:thm:1, we can see that if a sequence grows very fast, then it will be
pointwise bad even for $L^{\infty}$. On the other extreme, if a sequence grows
slower than any positive power of $n$, for example $(a_{n})=\big{(}(\log
n)^{c}\big{)}$ for some $c>0$, then it is again pointwise bad for $L^{\infty}$
as shown in Jones and Wierdl [13, Example 2.18]. See also a related result of
Loyd[17]. Bellow[3] and Reinhold-Larsson[22] proved that whether a sequence
will be pointwise good for $L^{p}$ or not can depend on the value of $p$. More
precisely, they showed that for any given $1\leq p<q\leq\infty$, there are
sequences $(a_{n})$ which are pointwise good for $L^{q}$ but pointwise bad for
$L^{p}$. Parrish[20] gives refinements of these results in terms of Orlicz
spaces. In general, neither the growth rate of the sequence, nor the value of
$p$ alone determines whether the sequence is pointwise good or bad. In some
cases, one has to analyze the intrinsic arithmetic properties of the sequence
$(a_{n})$. One such curious example is $(n^{k})_{n}$. A celebrated result of
Bourgain[6, Theorem 2] says that the sequence $(n^{k})_{n}$ is pointwise good
for $L^{2}$ when $k$ is a positive integer. On the other hand, the sequence
$\left\lparen\lfloor n^{k}+\log n\rfloor\right\rparen$ is known to be
pointwise bad for $L^{2}$ when $k$ is a positive integer[5, Theorem C].

After showing that polynomials are pointwise good for $L^{2}$, Bourgain
showed[7] that a polynomial sequence is pointwise good for $L^{p}$ for every
$p>1$ and Wierdl[26] showed the same for the sequence of primes. However, the
sequence of squares is pointwise bad for $L^{1}$, as was shown by Buczolich-
Mauldin[9], and LaVictoire[16] showed the same for the sequence $(n^{k})$ of
$k$th powers for a fixed positive integer $k$ and for the sequence of primes.
It was largely believed that there cannot be any sequence $(a_{n})$ which is
pointwise good for $L^{1}$ and satisfies $(a_{n+1}-a_{n})\to\infty$ as
$n\to\infty$, but Buczolich[8] disproved this conjecture. LaVictoire[15]
showed that a large class or random sequences also serve as counterexamples.

Urban and Zienkiewicz[25] showed that $\lfloor n^{c}\rfloor,c\in(1,1.001)$ is
pointwise good for $L^{1}$. The current best result is due to Mirek[18] who
showed that $\lfloor n^{c}\rfloor,c\in(1,\frac{30}{29})$ is pointwise good for
$L^{1}$, see also [24]. It would be interesting to know if the latter result
can be extended to all positive non integer $c$. The case of $L^{2}$ is
known[5] as well as $L^{p}$, $p>1$.

For further exposition in this area, the reader is referred to the survey
article of [23].

The extreme case scenario of non-convergence is the strong sweeping out
property of a sequence.

######  Definition 3 (label=defn:1).

strong sweeping outLet $(a_{n})$ be a sequence of integers.

We say $(a_{n})$ is _strong sweeping out_ if in every aperiodic dynamical
system $(X,\Sigma,\mu,T)$ and every $\epsilon>0$, there exists a set
$E\in\Sigma$ with $\mu(E)<\epsilon$ such that for almost every $x\in X$ we
have

$\displaystyle\limsup_{N\to\infty}\frac{1}{N}\sum_{n\in[N]}\mathds{1}_{E}(T^{a_{n}}x)$
$\displaystyle=1$ (1.5) and
$\displaystyle\liminf_{N\to\infty}\frac{1}{N}\sum_{n\in[N]}\mathds{1}_{E}(T^{a_{n}}x)$
$\displaystyle=0$ (1.6)

Akcoglu etal[1] showed that every lacunary sequence is strong sweeping out,
and our LABEL:thm:1 extends their result.

LABEL:thm:1 can also be interpreted from a different viewpoint. Jones-
Wierdl[13, Corollary 2.14] proved that for $1\leq p<\infty$ if a sequence
$(a_{n})$ satisfies $\dfrac{a_{n+1}}{a_{n}}\geq 1+{\frac{1}{(\log
n)^{\frac{1}{p}-\eta}}}$ for some $\eta>0$, then $(a_{n})$ is pointwise bad,
and our LABEL:thm:1 can be viewed as an extension of this result to not only
$L^{\infty}$ but indicators as well. It is also interesting to compare our
result with the results of Berkes[4] on lacunary polynomials.

In the next theorem, we will give a probabilistic condition for a sequence to
be strong sweeping out. Before we state the result, let us explain the notion
of a randomly generated sequence. Suppose $(\sigma_{n})$ is a sequence of
positive numbers; $\sigma_{n}$ is the probability with which $n$ is chosen
into the random sequence. More precisely, let $Y_{n}$ be a sequence of $0-1$
valued random variables on the probability space $(\Omega,\beta,P)$ so that
$P(Y_{n}=1)=\sigma_{n}$ and $P(Y_{n}=0)=1-\sigma_{n}.$ For each
$\omega\in\Omega$, let $A^{\omega}$ be the sequence defined by the property
that $n\in A^{\omega}$ if and only if $Y_{n}(\omega)=1.$ Our second main
result is the following:

######  Theorem 4 (label=thm:3).

Strong sweeping out with probabilistic conditionLet $\eta>0$ be arbitrary and
$\sigma_{n}=\frac{(\log\log\log n)^{1-\eta}}{n}$.

Then for a.e. $\omega$ the random sequence $A^{\omega}=(a_{n}(\omega))$ is
strong sweeping out.

This result is an improvement of a result of Jones-Lacey-Wierdl[12, Theorem C]
where they reach the same conclusion under the stronger hypothesis
$\sigma(n)=\frac{1}{n}$.

##  2 Proof of the main results:

Let $S$ be a finite set and let $f=(f_{n})_{n\in S}$ be a sequence of numbers
or functions indexed by $S$. We denote the arithmetic average of $(f_{n})$ by
$\mathds{A}_{S}f$,

$\mathds{A}_{S}f=\mathds{A}_{n\in S}f_{n}\coloneqq\frac{1}{\\#S}\sum_{n\in
S}f_{n}$ (2.1)

For a sequence $w=(w(n))_{n\in S}$ of numbers not identically $0$, which we
regard as the sequence of weights, we denote the $w$-weighted average of $f$
by $\mathds{A}^{w}_{S}f$,

$\mathds{A}^{w}_{S}f=\mathds{A}^{w}_{n\in S}f_{n}\coloneqq\frac{1}{\sum_{n\in
S}w(n)}\sum_{n\in S}w(n)f_{n}$ (2.2)

We will consider higher dimensional torus for proving our result. Originally,
such argument was used by Jones[11] to prove that the finite union of lacunary
sequences is strong sweeping out. Later an extension of this method was used
by Mondal[19]. We call this technique as the _grid method_.

To prove LABEL:thm:1, we need the following two lemmas:

######  Lemma 5 (label=lem:1).

Let $\tilde{A}=(a_{n})_{n\in[N]}$ be a finite sequence of integers which
satisfies $\frac{a_{n+1}}{a_{n}}>2Q$ for some $Q\leq N$. Suppose that
$\tilde{A}=\cdot\bigcup\limits_{q\in[Q]}A_{q}$ be partition of $\tilde{A}$.

Then there exists an irrational number $r\in[0,1]$ such that for all $q\in[Q]$
we have $ra_{n}\in I_{Q-q}$ (mod $1$) whenever $a_{n}\in A_{q}$, where
$I_{q}=\big{(}\frac{q-1}{Q},\frac{q}{Q}\big{)}.$

######  Proof 2.1.

This lemma in a bit different form appeares elsewhere[13, Lemma 2.13], hence
its proof is skipped here.

######  Lemma 6 (label=lem:conze).

Let $A=(a_{n})$ be a sequence of integers which satisfies the following
property:

for every $C>0$, $\epsilon>0$ and $N_{1}\in\mathds{N}$, there exists a
dynamical system $(X,\Sigma,\mu,T)$, a set $E\in\Sigma$ with
$\mu(E)<\epsilon$, and an integer $N_{2}>N_{1}$ such that

$\mu\Big{\\{}x\in X:\max_{N_{2}\leq N\leq
N_{2}}\mathds{A}_{n\in[N]}\mathds{1}_{E}(T^{a_{n}}x)>1-\epsilon\Big{\\}}\geq
C\mu(E).$ (2.3)

Then the sequence $A=(a_{n})$ is strong sweeping out.

######  Proof 2.2.

A version of this lemma appears elsewhere[19, Theorem 3.1] already with
detailed proof, so we will just outline the proof here.

First, by using Calderon’s transference principle[10], one can prove that if
we have a maximal inequality on $\mathds{R}$ (with respect to the
transformation $\tau(n)=n+1$), then the maximal inequality transfers to any
dynamical system with the same constant. Hence the hypothesis of
LABEL:lem:conze implies that there is a denial of a maximal inequality on
$\mathds{R}$. Now, we invoke Akcoglu etal’s result[1, Theorem 2.3] to finish
the proof of this theorem.

######  Proof 2.3 (Proof of LABEL:thm:1).

Let $C>0$, $N_{1}\in\mathds{N}$, and $\epsilon>0$. By LABEL:lem:conze, it will
be sufficient to find a set $E$ in $\mathds{T}^{K}$ with
$\lambda^{(K)}(E)<\epsilon$, and an integer $N_{2}>N_{1}$ which satisfy eq.
2.3. Here $\mathds{T}^{K}$ denotes the $K$-dimensional torus and
$\lambda^{(K)}$ means the Haar-Lebesgue measure on $\mathds{T}^{K}$.

Let $N>N_{1}$ be a very large positive integer. Since,

$a_{n}\neq a_{m}\text{ if }n\neq m$

so $(a_{n})$ can also be considered as a set. Since, for $x\in(0,1)$, we have
$e^{x}=1+x+O(x^{2})$, we can rewrite the given condition as

$\frac{a_{n+1}}{a_{n}}>e^{\frac{1}{(\log\log N)^{1-\eta}}}\text{ for
}n\in[N].$ (2.4)

Let us choose a natural number $Q=Q(N)$ which just needs to go to $\infty$ as
$N\to\infty.$ Choose another integer $K=K(N)$ large enough so that

$e^{\frac{K}{(\log\log N)^{1-\eta}}}>2Q.$ (2.5)

This implies

$\frac{a_{n+K}}{a_{n}}>2Q\text{ for }n\in[N].$ (2.6)

For any $k\in[K]$, define

$A_{k}:=\big{\\{}a_{n}:n\equiv k\ (\text{mod }K)\text{ and }n\in[N]\big{\\}}.$
(2.7)

Observe that for each $k\in[K]$, $A_{k}$ satisfies the hypothesis of
LABEL:lem:1. That means each $A_{k}$ has the property that if it is
partitioned into $Q$ sets, so
$A_{k}=\displaystyle\cdot\bigcup_{q\in[Q]}A_{k,q}$ then there is an irrational
number $r_{k}$ so that

$r_{k}a_{n}\in I_{Q-q}\ \ (\text{mod }1)\text{ for all }a_{n}\in A_{k,q},\
q\in[Q],$ (2.8)

where

$I_{q}:=\big{(}\frac{q-1}{Q},\frac{q}{Q}\big{)}.$ (2.9)

The above partition $A_{1},A_{2},...,A_{K}$ of $(a_{n})_{n\in[N]}$ naturally
induces a partition of the index set $[N]$ into $K$ index sets
$\mathcal{N}_{k},k\in[K]$. We then have

$\mathds{A}_{n\in J}f(T^{a_{n}}x)=\frac{1}{\\#J}\sum_{k\in[K]}\sum_{n\in
J\cap\mathcal{N}_{k}}f(T^{a_{n}}x).$ (2.10)

The space of action is the $K$ dimensional torus ${\mathbb{T}}^{K}$,
subdivided into little $K$ dimensional cubes $C$ of the form

$C=I_{q(1)}\times I_{q(2)}\times......\times I_{q(k)}\text{ for some
}{q(k)}\leq Q\text{ for }q\leq Q.$ (2.11)

At this point it is useful to introduce the following vectorial notation to
describe these cubes $C$. For a vector
$\mathbf{q}=\big{(}q(1),q(2),...,q(K)\big{)}$ with $q(k)\in[Q]$, define

$I_{\mathbf{q}}:=I_{q(1)}\times I_{q(2)}\times\dots\times I_{q(K)}.$ (2.12)

Since each component $q(k)$ can take up the values $1,2,\dots,Q$, we divided
$\mathds{T}^{Q}$ into $Q^{k}$ cubes. We also consider the “bad” set $E$
defined by

$E:=\cup_{k\leq
K}(0,1)\times(0,1)\times\dots\times\underbrace{\big{(}I_{1}\cup
I_{2}\big{)}}_{\text{k-th coordinate}}\times\dots\times(0,1).$ (2.13)

Defining the set $E_{k}$ by

$E_{k}:=(0,1)\times(0,1)\times\dots\times\underbrace{\big{(}I_{1}\cup
I_{2}\big{)}}_{\text{k-th coordinate}}\times\dots\times(0,1)$ (2.14)

we have

$E=\cup_{k\leq K}E_{k}\text{ and }\lambda^{(K)}(E_{k})\leq\frac{2}{Q}\text{
for every }k\leq K$ (2.15)

By eq. 2.15, we have

$\lambda^{(K)}(E)\leq\frac{2K}{Q}.$ (2.16)

Since we want the measure of the “bad set” to be smaller and smaller, we must
assume

$K<<Q.$ (2.17)

Now the idea is to have averages that move each of the cubes into the support
of the set $E$. The $2$-dimensional version of the process is illustrated in
Figure 1.

$0$$\frac{2}{10}$$\frac{4}{10}$$\frac{6}{10}$$\frac{7}{10}$$\frac{8}{10}$$\frac{2}{10}$$\frac{4}{10}$$\frac{5}{10}$$\frac{6}{10}$$\frac{8}{10}$$E$$(x_{1},x_{2})\in
B_{6,3}$ Figure 1: Illustration of the 2-dimensional case. Here the “bad set”
E is the orange colored region. Let $(x_{1},x_{2})$ be an arbitrary point
(which belongs to $B_{6,3}$ in this case). We need to look at an average where
$r_{1}a_{n}\in(\frac{4}{10},\frac{5}{10})$ for all $n\in{A_{1}}$ and
$r_{2}a_{n}\in(\frac{7}{10},\frac{8}{10})$ for all $n\in{A_{2}}.$ Then it
would give us $(x_{1},x_{2})+(r_{1}a_{n},r_{2}a_{n})\in E$ for all
$n\in{A_{1}}\cup{A_{2}}.$

Since we have $Q^{K}$ cubes, we need to have $Q^{K}$ averages
$\mathds{A}_{J_{i}}$. This means we need to have $Q^{K}$ disjoint intervals
$J_{i}$ of indices. The length of these intervals $J_{i}$ needs to be
“significant”, in comparison with $J_{i-1}$. For our purpose,
$J_{i}=(2^{N_{1}+i},2^{N_{1}+i+1})$ will be suitable. This means we need to
have $Q^{K}$ exponents to be available, which implies that

$N\geq 2^{Q^{K}}.$ (2.18)

For simplicity, we assume that

$N=2^{Q^{K}}$ (2.19)

To make our plan work, first let us check that we can really choose such
$K(N)$ which satisfies the condition eq. 2.17, eq. 2.19 and eq. 2.5. Let us
write eq. 2.5 as

$\frac{K}{(\log\log N)^{1-\eta}}>\log 2Q.$ (2.20)

Using the assumption $N=2^{Q^{K}}$, the condition in eq. 2.20 becomes

$\frac{K}{(K\log Q)^{1-\eta}}>\log 2Q.$ (2.21)

After rearranging and ignoring the difference between $\log Q$ and $\log 2Q$,
we get

$K^{\eta}>\big{(}\log Q\big{)}^{2-\eta},$ (2.22)

which we can simplify a bit generously to

$K>(\log Q)^{\frac{2}{\eta}}.$ (2.23)

We certainly can choose $K$ to satisfy eq. eq. 2.23 and also make sure that
$\frac{K(N)}{Q(N)}$ goes to $0$ and $N\to\infty.$ Choose $N_{2}$ large enough
so that $K(N_{2})$ and $Q(N_{2})$ satisfy eq. 2.23 and the following:

$\frac{2K(N_{2})}{Q(N_{2})}<\min\\{\epsilon,\frac{1}{C}\\}.$ (2.24)

So we have $Q^{K}$ cubes $C_{i},i\in[Q^{K}]$ and $Q^{K}$ intervals
$J_{i},i\in[Q^{K}]$. We match $C_{i}$ with $J_{i}$. We know that $C_{i}$ is of
the form

$C_{i}=I_{\mathsf{q}_{i}},$ (2.25)

for some $K$ dimensional vector $\mathsf{q}_{i}=\big{(}q_{i}(1),q_{i}(2),\dots
q_{i}(K)\big{)}$ with $q_{i}(k)\in[Q]$ for every $k\in[K].$ The interval
$J_{i}$ is partitioned as

$J_{i}=\displaystyle\bigcup_{k\in[K]}(J_{i}\cap\mathcal{N}_{k}).$ (2.26)

For a given $k\in[K]$, let us define the set of indices $\mathcal{N}_{k,q}$
for $q\leq Q$, by

$\mathcal{N}_{k,q}:=\displaystyle\bigcup_{i\leq
Q^{K},q_{i}(k)=q}(J_{i}\cap\mathcal{N}_{k})$ (2.27)

Since the sets $A_{k,q}:=\big{\\{}a_{n}:n\in\mathcal{N}_{k,q}\big{\\}}$ form a
partition of $A_{k}$, by the argument above eq. 2.8, there is a real number
$r_{k}$ so that

$r_{k}a_{n}\in I_{Q-q}\ \ (\text{ mod }1)\text{ for
}n\in\mathcal{N}_{k,q}\text{ and }q\leq Q.$ (2.28)

Define the transformation $T$ on the $K$ dimensional torus $\mathds{T}^{K}$ by

$T(x_{1},x_{2},\dots,x_{K}):=(x_{1}+r_{1}t,x_{2}+r_{2}t,\dots,x_{K}+r_{K}t).$
(2.29)

We claim that

$\Big{\\{}x|\max_{i\in[Q^{K}]}\mathds{A}_{n\in
J_{i}}\mathds{1}_{E}(T^{a_{n}}x)=1\Big{\\}}=\mathds{T}^{K}$ (2.30)

Indeed, let $x\in C_{i}$ and consider the averages $\mathds{A}_{J_{i}}$. Let
us write

$\mathds{A}_{n\in
J_{i}}\mathds{1}_{E}(T^{a_{n}}x)=\frac{1}{\\#J_{i}}\sum_{k\leq{K}}\sum_{n\in
J_{i}\cap\mathcal{N}_{k}}\mathds{1}_{E}(T^{a_{n}}{x})$ (2.31)
$=\frac{1}{\\#J_{i}}\sum_{k\leq{K}}\sum_{n\in
J_{i}\cap\mathcal{N}_{k}}\mathds{1}_{E}(x_{1}+r_{1}a_{n},x_{2}+r_{2}a_{n},\dots,x_{K}+r_{K}a_{n}).$
(2.32)

We claim that for each $k\in[K]$

$(x_{1}+r_{1}a_{n},x_{2}+r_{2}a_{n},\dots
x_{k}+r_{k}a_{n},\dots,x_{K}+r_{K}a_{n})\in E_{k}\text{ if }n\in
J_{i}\cap\mathcal{N}_{k}$ (2.33)

Since, $E_{k}\subset E$, we would have

$\mathds{1}_{E}(x_{1}+r_{1}a_{n},x_{2}+r_{2}a_{n},\dots
x_{k}+r_{k}a_{n},\dots,x_{K}+r_{K}a_{n})=1\text{ if }n\in
J_{i}\cap\mathcal{N}_{k}$ (2.34)

which would mean

$\mathds{1}_{E}(T^{a_{n}}x)=1\text{ for all }n\in J_{i}.$ (2.35)

So let us prove eq. 2.33. Since $x\in C_{i}=I_{\mathsf{q}}$ we have $x_{k}\in
I_{q_{i}(k)}$ for every $k$. By the definition of $r_{k}$ in eq. (eq. 2.28) we
have $r_{k}a_{n}\in I_{Q-q_{i}(k)}$ if $n\in J_{i}\cap\mathcal{N}_{k}$. It
follows that

$x_{k}+r_{k}a_{n}\in I_{q_{i(k)}}+I_{Q-q_{i}(k)}\text{ if }n\in
J_{i}\cap\mathcal{N}_{k}.$ (2.36)

Since $I_{q_{i(k)}}+I_{Q-q_{i(k)}}\subset I_{1}\cup I_{2}$, we get

$x_{k}+r_{k}a_{n}\in I_{1}\cup I_{2}\text{ if }n\in J_{i}\cap\mathcal{N}_{k}.$

By the definition of $E_{k}$ in eq. 2.14, this implies that

$(x_{1}+r_{1}a_{n},x_{2}+r_{2}a_{n},\dots
x_{k}+r_{k}a_{n},\dots,x_{K}+r_{K}a_{n})\in E_{k}$

as claimed.

######  Remark.

  1. 1.

Sharpness: We can prove LABEL:thm:1 by replacing the assumption eq. 1.2 with
$\frac{a_{n+1}}{a_{n}}>1+\frac{(\log\log\log n)^{2+\eta}}{\log\log n}$,
$\eta>0.$

  2. 2.

LABEL:thm:1 can also be proved by using [21, Theorem 3.1]. By applying this
result, one can slightly weaken the hypothesis. More precisely, we can prove
that any sequence $(a_{n})$ satisfying
$\frac{a_{n+1}}{a_{n}}>1+\frac{(\log\log\log n)^{1+\eta}}{\log\log n}$,
$\eta>0$ is strong sweeping out.

We can generalize LABEL:thm:1 for weighted ergodic averages in the following
way:

######  Theorem 7 (label=thm:4).

Let $(w(n))$ be a sequence of real numbers from the interval $(0,1]$ and
denote $G(n):=\sum_{i\in[n]}w(i)$. Suppose $(a_{n})$ is a sequence of integer
which satisfies

$\frac{a_{n+1}}{a_{n}}\geq 1+{\frac{1}{(\log\log G(n))^{1-\eta}}}$ (2.37)

for some $\eta>0$. Then $(a_{n})$ satisfies the strong sweeping out property
for the $w$-weighted averages $\mathds{A}^{w}_{n\in[N]}f(T^{a_{n}}x)$.

######  Proof 2.4.

The proof of LABEL:thm:1 will work in this case after the following obvious
modifications. Because of changing the summation method, instead of
$\mathds{A}_{J}$, we have to work with the averages $\mathds{A}^{w}_{J}$.
Accordingly, the length of $J_{i}$ also has to be changed. A suitable choice
of $J_{i}$ in this case would be following:

$J_{i}=\Big{(}G^{-1}(2^{N_{1}+i}),G^{-1}(2^{N_{1}+i+1})\Big{)}$ (2.38)

Now, one can reiterate the argument given in LABEL:thm:1 to get the desired
conclusion.

######  Corollary 8 (label=cor:1).

If $(a_{n})$ is a sequence of integers satisfying $\frac{a_{n+1}}{a_{n}}\geq
1+{\frac{1}{(\log\log\log n)^{1-\eta}}}$ for some $\eta>0$, then $({a_{n}})$
is strong sweeping out for the logarithmic averages
$\mathds{A}^{1/n}_{n\in[N]}f(T^{a_{n}}x)=\dfrac{1}{\log
N}\sum_{n\in[N]}\frac{1}{n}f(T^{a_{n}}x)$.

Now, we will prove LABEL:thm:3. For any sequence $A$ of integers, we define
$A(t):=\\{n\in A:n\leq t\\}.$ Observe that LABEL:thm:3 will follow from
LABEL:thm:1 and the following lemma.

######  Lemma 9 (label=lem:5).

Under the hypothesis of LABEL:thm:3, for a.e. $\omega$, there exists a
subsequence $B^{\omega}=(b_{n}(\omega))$ of $A^{\omega}=(a_{n}(\omega))$ such
that the following holds:

$\displaystyle\lim_{t\to\infty}\frac{B^{\omega}(t)}{A^{\omega}(t)}$
$\displaystyle=1$ (2.39) $\displaystyle\frac{b_{n+1}(\omega)}{b_{n}(\omega)}$
$\displaystyle>e^{\frac{1}{(\log\log n)^{1-{\eta/2}}}}$ (2.40)

######  Proof 2.5.

Let $u_{n}=\min\\{t|\displaystyle\sum_{k\leq t}\sigma_{k}\geq n\\}$. First
observe that $u_{n}\sim e^{n(\log\log n)^{-1+\eta}}.$

By the strong law of large numbers, we have for a.e. $\omega$,

$\displaystyle\lim_{n\to\infty}\frac{A^{\omega}(u_{n})}{\displaystyle\sum_{u\leq
u_{n}}\sigma_{u}}=1\text{ which implies that\ \
}\lim_{n\to\infty}\frac{A^{\omega}(u_{n})}{n}=1.$

Clearly, $\frac{u_{n+1}}{u_{n}}\sim e^{\frac{1}{(\log\log n)^{1-\eta}}}.$
However, this does not imply that
$\frac{a_{n+1}(\omega)}{a_{n}(\omega)}>e^{\frac{1}{(\log\log n)^{1-\eta}}}$.

Figure 2: An example where $A^{\omega}$ may not satisfy the condition eq.
2.40$u_{k}$$a_{k}(\omega)$$u_{k+1}$$a_{k+1}(\omega)$$a_{k+2}(\omega)$$u_{k+2}$$u_{k+3}$$a_{k+3}(\omega)$$u_{k+4}$

So, we need to modify our sequence.

Let $v_{n}=e^{n(\log\log n)^{-1+\frac{\eta}{2}}}$ and
$I_{n}=[v_{n},v_{n+1})\cap\mathbb{N}$. The properties of $(v_{n})$, that we
shall use here are the following:

$\frac{v_{n+1}}{v_{n}}\geq e^{\frac{1}{(\log\log n)^{1-\frac{\eta}{2}}}}\text{
and }\lim_{n\to\infty}\sum_{u\in I_{n}}\sigma_{u}=0.$ (2.41)

Let $D^{\omega}=(d_{n}(\omega)):=\\{d:d\in I_{n}\cap A^{\omega}\text{ for some
}n\in\mathbb{N}\text{ satisfying }I_{n+1}\cap A^{\omega}\neq\emptyset\\}$.

And
$E^{\omega}=(e_{n}(\omega)):=\displaystyle\bigcup_{n\in\mathds{N}}\\{I_{n}\cap
A^{\omega}:|I_{n}\cap A^{\omega}|>1\\}$.

In Figure , $a_{k+1}(\omega)\in D^{\omega}$ because $I_{k+1}\cap
A^{\omega}\neq\emptyset$. And $a_{k+3}(\omega),a_{k+4}(\omega)\in E^{\omega}.$

$v_{k}$$a_{k}(\omega)$$v_{k+1}$$a_{k+1}(\omega)$$a_{k+2}(\omega)$$v_{k+2}$$v_{k+3}$$a_{k+3}(\omega)$$v_{k+4}$$v_{k+5}$$a_{k+5}(\omega)$$v_{k+6}$$a_{k+4}(\omega)$$v_{k+7}$
$D^{\omega}$$E^{\omega}$

Define $B^{\omega}:=A^{\omega}\setminus\ (D^{\omega}\cup E^{\omega})$. Note
that $B^{\omega}$ satisfies the following properties

  1. 1.

If $|B^{\omega}\cap I_{n}|=1$ then $|B^{\omega}\cap I_{n+1}|=0.$

  2. 2.

$|B^{\omega}\cap I_{n}|\leq 1$ for all $n$.

from which it follows that $(b_{n}(\omega))$ satisfies eq. 2.40.

$v_{k}$$a_{k}(\omega)$$v_{k+1}$$a_{k+2}(\omega)$$v_{k+2}$$v_{k+3}$$v_{k+4}$$v_{k+5}$$a_{k+3}(\omega)$$v_{k+6}$$v_{k+7}$
$B^{\omega}$

It remains to verify Equation 2.39.

It will be sufficient to show that for a.e. $\omega$,

$\displaystyle\lim_{t\to\infty}\frac{D^{\omega}(t)}{A^{\omega}(t)}=0\text{ and
}\lim_{t\to\infty}\frac{E^{\omega}(t)}{A^{\omega}(t)}=0.$

By the strong law of large numbers, we need to show that

$\displaystyle\lim_{t\to\infty}\frac{\mathbb{E}D^{\omega}(t)}{\sum_{n\leq
t}\sigma_{n}}=0\text{ and
}\lim_{t\to\infty}\frac{\mathbb{E}E^{\omega}(t)}{\sum_{n\leq t}\sigma_{n}}=0.$

Note that $D^{\omega}(t)\leq\displaystyle\sum_{v_{k}\leq t}\big{(}\sum_{n\in
I_{k}}Y_{n}(\omega)\big{)}.\sup_{n\in I_{k+1}}Y_{n}$. Since, the random
variables $X_{k}=\sum_{n\in I_{k}}Y_{n},k=1,2,3,....,$ are independent, it
follows that

$\displaystyle\mathbb{E}D^{\omega}(t)$
$\displaystyle\leq\mathbb{E}\sum_{v_{k}\leq t}\Big{(}\sum_{n\in
I_{k}}Y_{n}\Big{)}.\sup_{n\in I_{k+1}}Y_{n}$
$\displaystyle\leq\mathbb{E}\sum_{v_{k}\leq t}\Big{(}\sum_{n\in
I_{k}}Y_{n}\Big{)}.\Big{(}\sum_{n\in I_{k+1}}Y_{n}\Big{)}$
$\displaystyle\leq\sum_{v_{k}\leq t}\big{(}\sum_{n\in
I_{k}}\sigma_{n}\big{)}.\big{(}\sum_{n\in I_{k+1}}\sigma_{n}\big{)}$

Hence,

$\displaystyle\limsup_{t\to\infty}\frac{\mathbb{E}D^{\omega}(t)}{\sum_{n\leq
t}\sigma_{n}}$ $\displaystyle\leq\limsup_{t\to\infty}\frac{\sum_{v_{k}\leq
t}\big{(}\sum_{n\in I_{k}}\sigma_{n}\big{)}.\big{(}\sum_{n\in
I_{k+1}}\sigma_{n}\big{)}}{\sum_{n\leq t}\sigma_{n}}$
$\displaystyle\leq\limsup_{k\to\infty}\Big{(}\sum_{n\in
I_{k+1}}\sigma_{n}\Big{)}\frac{\sum_{v_{k}\leq t}\big{(}\sum_{n\in
I_{k}}\sigma_{n}\big{)}}{\sum_{n\leq t}\sigma_{n}}$ $\displaystyle=0\text{
\big{(} By \lx@cref{creftype~refnum}{eq:64}\big{)}}$

Similarly,

$\displaystyle\limsup_{t\to\infty}\frac{\mathbb{E}E^{\omega}(t)}{\sum_{n\leq
t}\sigma_{n}}$ $\displaystyle=\limsup_{t\to\infty}\frac{\sum_{v_{k}\leq
t}\big{(}2\cdot\sum_{m\neq n\in
I_{k}}\sigma_{m}\cdot\sigma_{n}+3\cdot\sum_{m\neq n\neq p\in
I_{k}}\sigma_{m}\cdot\sigma_{n}\cdot\sigma_{p}+\dots+l\cdot\sum_{m_{1}\neq
m_{2}\neq\dots\neq m_{l}\in
I_{k}}\sigma_{m_{1}}\cdot\sigma_{m_{2}}\dots\sigma_{m_{l}}\big{)}}{\sum_{n\leq
t}\sigma_{n}}\ \ (\text{here}|I_{k}|=l)$
$\displaystyle\leq\limsup_{t\to\infty}\frac{\sum_{v_{k}\leq
t}\Big{(}2\cdot\big{(}\sum_{m\in
I_{k}}\sigma_{m}\big{)}^{2}+3\cdot\big{(}\sum_{m\in
I_{k}}\sigma_{m}\big{)}^{3}+\dots+l\cdot\big{(}\sum_{m\in
I_{k}}\sigma_{m}\big{)}^{l}\Big{)}}{\sum_{n\leq t}\sigma_{n}}$
$\displaystyle\leq\limsup_{t\to\infty}\frac{\sum_{v_{k}\leq
t}\big{(}\sum_{m\in I_{k}}\sigma_{m}\big{)}\cdot\Big{(}2\cdot\big{(}\sum_{m\in
I_{k}}\sigma_{m}\big{)}+3\cdot\big{(}\sum_{m\in
I_{k}}\sigma_{m}\big{)}^{2}+\dots+l\cdot\big{(}\sum_{m\in
I_{k}}\sigma_{m}\big{)}^{(l-1)}\Big{)}}{\sum_{n\leq t}\sigma_{n}}$
$\displaystyle\leq\limsup_{k\to\infty}\Big{(}2\cdot\big{(}\sum_{m\in
I_{k}}\sigma_{m}\big{)}+3\cdot\big{(}\sum_{m\in
I_{k}}\sigma_{m}\big{)}^{2}+\dots l\cdot\big{(}\sum_{m\in
I_{k}}\sigma_{m}\big{)}^{(l-1)}\Big{)}$
$\displaystyle\leq\limsup_{k\to\infty}x\cdot\frac{(2-x)}{(1-x)^{2}}\text{
\Big{(} where $x=\sum_{m\in I_{k}}\sigma_{m}$ \Big{)}}$ $\displaystyle=0\text{
\big{(} By \lx@cref{creftype~refnum}{eq:64}\big{)}}$

This completes the proof.

##  3 Open Problems

The first problem asks if our result in LABEL:thm:1 is sharp.

######  Problem 3.1.

Suppose the sequence $(a_{n})$ of positive integers satisfies

$\frac{a_{n+1}}{a_{n}}>1+\frac{1}{\log\log n}$ (3.1)

Is $(a_{n})$ strong sweeping out?

It is known[12] that there is a pointwise good sequence $(a_{n})$ for $L^{2}$
satisfying $\dfrac{a_{n+1}}{a_{n}}\geq 1+{\frac{1}{(\log n)^{1+\eta}}}$ for
every $\eta>0$ and large enough $n$. We already mentioned[13, Corollary 2.14]
that if $(a_{n})$ satisfies $\dfrac{a_{n+1}}{a_{n}}\geq 1+{\frac{1}{(\log
n)^{1/2-\eta}}}$ for some positive $\eta$ then $(a_{n})$ is pointwise bad for
$L^{2}$.

######  Problem 3.2.

Suppose the sequence $(a_{n})$ of positive integers satisfies

$\dfrac{a_{n+1}}{a_{n}}\geq 1+{\frac{1}{\log n}}$ (3.2)

for every large enough $n$.

Is $(a_{n})$ then pointwise bad for $L^{2}$?

## References

  * [1] Mustafa Akcoglu et al.  “The strong sweeping out property for lacunary sequences, Riemann sums, convolution powers, and related matters”  In _Ergodic Theory Dynam. Systems_ 16.2, 1996, pp. 207–253  DOI: 10.1017/S0143385700008798
  * [2] Alexandra Bellow  “On “bad universal” sequences in ergodic theory. II”  In _Measure theory and its applications (Sherbrooke, Que., 1982)_ 1033, Lecture Notes in Math.  Springer, Berlin, 1983, pp. 74–78  DOI: 10.1007/BFb0099847
  * [3] Alexandra Bellow  “Perturbation of a sequence”  In _Adv. Math._ 78.2, 1989, pp. 131–139  DOI: 10.1016/0001-8708(89)90030-3
  * [4] István Berkes  “On the convergence of $\sum c_{n}f(nx)$ and the ${\rm Lip}\ 1/2$ class”  In _Trans. Amer. Math. Soc._ 349.10, 1997, pp. 4143–4158  DOI: 10.1090/S0002-9947-97-01837-0
  * [5] Michael Boshernitzan, Grigori Kolesnik, Anthony Quas and Máté Wierdl  “Ergodic averaging sequences”  In _J. Anal. Math._ 95, 2005, pp. 63–103  DOI: 10.1007/BF02791497
  * [6] J. Bourgain  “On the maximal ergodic theorem for certain subsets of the integers”  In _Israel J. Math._ 61.1, 1988, pp. 39–72  DOI: 10.1007/BF02776301
  * [7] Jean Bourgain  “Pointwise ergodic theorems for arithmetic sets” With an appendix by the author, Harry Furstenberg, Yitzhak Katznelson and Donald S. Ornstein  In _Inst. Hautes Études Sci. Publ. Math._ , 1989, pp. 5–45  URL: http://www.numdam.org/item?id=PMIHES_1989__69__5_0
  * [8] Z. Buczolich  “Universally $L^{1}$ good sequences with gaps tending to infinity”  In _Acta Math. Hungar._ 117.1-2, 2007, pp. 91–140  DOI: 10.1007/s10474-007-6068-8
  * [9] Zoltán Buczolich and R. Mauldin  “Divergent square averages”  In _Ann. of Math. (2)_ 171.3, 2010, pp. 1479–1530  DOI: 10.4007/annals.2010.171.1479
  * [10] A.-P. Calderón  “Ergodic theory and translation-invariant operators”  In _Proc. Nat. Acad. Sci. U.S.A._ 59, 1968, pp. 349–353  DOI: 10.1073/pnas.59.2.349
  * [11] Roger L. Jones  “Strong sweeping out for lacunary sequences”  In _Chapel Hill Ergodic Theory Workshops_ 356, Contemp. Math.  Amer. Math. Soc., Providence, RI, 2004, pp. 137–144  DOI: 10.1090/conm/356/06501
  * [12] Roger L. Jones, Michael Lacey and Máté Wierdl  “Integer sequences with big gaps and the pointwise ergodic theorem”  In _Ergodic Theory Dynam. Systems_ 19.5, 1999, pp. 1295–1308  DOI: 10.1017/S0143385799146819
  * [13] Roger L. Jones and Máté Wierdl  “Convergence and divergence of ergodic averages”  In _Ergodic Theory Dynam. Systems_ 14.3, 1994, pp. 515–535  DOI: 10.1017/S0143385700008002
  * [14] Ulrich Krengel  “On the individual ergodic theorem for subsequences”  In _Ann. Math. Statist._ 42, 1971, pp. 1091–1095  DOI: 10.1214/aoms/1177693338
  * [15] Patrick LaVictoire  “An $L^{1}$ ergodic theorem for sparse random subsequences”  In _Math. Res. Lett._ 16.5, 2009, pp. 849–859  DOI: 10.4310/MRL.2009.v16.n5.a8
  * [16] Patrick LaVictoire  “Universally $L^{1}$-bad arithmetic sequences”  In _J. Anal. Math._ 113, 2011, pp. 241–263  DOI: 10.1007/s11854-011-0006-y
  * [17] Kaitlyn Loyd  “A dynamical approach to the asymptotic behavior of the sequence”  In _Ergodic Theory and Dynamical Systems_ Cambridge University Press (CUP), 2022, pp. 1–22  DOI: 10.1017/etds.2022.81
  * [18] Mariusz Mirek  “Weak type $(1,1)$ inequalities for discrete rough maximal functions”  In _J. Anal. Math._ 127, 2015, pp. 247–281  DOI: 10.1007/s11854-015-0030-4
  * [19] Sovanlal Mondal  “Grid method for divergence of averages”, 2022  URL: https://arxiv.org/abs/2207.09032
  * [20] Andrew Parrish  “Pointwise convergence of ergodic averages in Orlicz spaces”  In _Illinois J. Math._ 55.1, 2011, pp. 89–106 (2012)  URL: http://projecteuclid.org/euclid.ijm/1355927029
  * [21] Yuval Peres and Wilhelm Schlag  “Two Erdős problems on lacunary sequences: chromatic number and Diophantine approximation”  In _Bull. Lond. Math. Soc._ 42.2, 2010, pp. 295–300  DOI: 10.1112/blms/bdp126
  * [22] Karin Reinhold-Larsson  “Discrepancy of behavior of perturbed sequences in $L^{p}$ spaces”  In _Proc. Amer. Math. Soc._ 120.3, 1994, pp. 865–874  DOI: 10.2307/2160481
  * [23] Joseph M. Rosenblatt and Máté Wierdl  “Pointwise ergodic theorems via harmonic analysis”  In _Ergodic theory and its connections with harmonic analysis (Alexandria, 1993)_ 205, London Math. Soc. Lecture Note Ser.  Cambridge Univ. Press, Cambridge, 1995, pp. 3–151  DOI: 10.1017/CBO9780511574818.002
  * [24] Bartosz Trojan  “Weak type $(1,1)$ estimates for maximal functions along 1-regular sequences of integers”  In _Studia Math._ 261.1, 2021, pp. 103–108  DOI: 10.4064/sm200702-21-12
  * [25] Roman Urban and Jacek Zienkiewicz  “Weak type $(1,1)$ estimates for a class of discrete rough maximal functions”  In _Math. Res. Lett._ 14.2, 2007, pp. 227–237  DOI: 10.4310/MRL.2007.v14.n2.a6
  * [26] Máté Wierdl  “Pointwise ergodic theorem along the prime numbers”  In _Israel J. Math._ 64.3, 1988, pp. 315–336 (1989)  DOI: 10.1007/BF02882425