#  AdaMAE: Adaptive Masking for Efficient Spatiotemporal
Learning with Masked Autoencoders

Wele Gedara Chaminda Bandara1, Naman Patel2, Ali Gholami2,
Mehdi Nikkhah2, Motilal Agrawal2, and Vishal M. Patel1
1Johns Hopkins University, Baltimore, USA 2Zippin, California, USA
<EMAIL_ADDRESS>{naman, gholami, mehdi<EMAIL_ADDRESS><EMAIL_ADDRESS>
github.com/wgcban/adamae

###### Abstract

Masked Autoencoders (MAEs) learn generalizable representations for image,
text, audio, video, etc., by reconstructing masked input data from tokens of
the visible data. Current MAE approaches for videos rely on random patch,
tube, or frame based masking strategies to select these tokens. This paper
proposes AdaMAE, an adaptive masking strategy for MAEs that is end-to-end
trainable. Our adaptive masking strategy samples visible tokens based on the
semantic context using an auxiliary sampling network. This network estimates a
categorical distribution over spacetime-patch tokens. The tokens that increase
the expected reconstruction error are rewarded and selected as visible tokens,
motivated by the policy gradient algorithm in reinforcement learning. We show
that AdaMAE samples more tokens from the high spatiotemporal information
regions, thereby allowing us to mask 95% of tokens, resulting in lower memory
requirements and faster pre-training. We conduct ablation studies on the
Something-Something v2 (SSv2) dataset to demonstrate the efficacy of our
adaptive sampling approach and report state-of-the-art results of 70.0% and
81.7% in top-1 accuracy on SSv2 and Kinetics-400 action classification
datasets with a ViT-Base backbone and 800 pre-training epochs.

##  1 Introduction

Figure 1: Comparison of our adaptive masking with existing random patch [11],
tube [46, 49], and frame [26, 35, 40] masking for masking ratio of 80%. Our
adaptive masking approach selects more tokens from the regions with  high
spatiotemporal information while a small number of tokens from the background.

Self-supervised learning (SSL) aims to learn transferable representations from
a large collection of unlabeled data for downstream applications (e.g.,
classification and detection). SSL is conducted in a two-stage framework [21],
consisting of pre-training on an unlabeled dataset, and fine-tuning on a
downstream task. Pre-training has shown to improve performance [11],
convergence speed [11], and robustness [18], and reduce model overfitting [11,
14] on downstream tasks.

Recently, masked autoencoders (MAEs) [46, 16, 54, 11, 17, 20, 5] and
contrastive learning [45, 37, 21] approaches are mainly used for SSL. In MAEs,
the input (image or video) is patchified and converted into a set of tokens. A
small percentage (_e.g_., 5-10%) of these tokens, namely visible tokens, are
passed through a Vision Transformer (ViT) [8]. The resulting token embeddings
are then concatenated with a learnable representation for masked tokens, and
are fed into a shallow decoder transformer to reconstruct masked patches. On
the other hand, contrastive learning takes two augmented views of the same
input and pulls them together in the embedding space, while embeddings of
different inputs are pushed away [37]. MAEs have recently gained more
attention over contrastive learning methods due to the inherent use of a high
masking ratio, which enables simple and memory-efficient training.

Mask sampling techniques are critical to the success of MAEs [11, 51].
Previous studies have investigated different sampling techniques that include
random “patch” [11], “tube” [51], and “frame” [51] masking (see Fig. 1).
Random patch sampling has shown to work well compared to its counterparts in
some cases [11]. However, since not all tokens have equal information,
assuming a uniform probability distribution over all input tokens (for
selection of visible tokens) is sub-optimal. In other words, with these random
masking strategies, the visible tokens are sampled from redundant or low
information regions instead of high information ones, hence resulting in
inaccurate reconstructions. This inhibits MAEs from learning meaningful
representations, besides requiring a relatively larger number of training
iterations compared to contrastive learning methods.

In this paper, we propose an adaptive sampling approach that simultaneously
optimizes an MAE and an adaptive token sampling network. Our approach selects
patches based on their spatiotemporal information. Unlike uniform random
sampling, we first estimate the categorical distribution over all input tokens
using an auxiliary network, and then sample visible tokens from that
distribution. Since sampling is a non-differentiable operation, we propose an
auxiliary loss for optimizing the adaptive token sampling network. Our
solution is motivated by the REINFORCE algorithm [53], which comes under the
family of policy gradient algorithms in Reinforcement Learning (RL) [23].

We empirically show that our adaptive token sampling network leads to sampling
more tokens from high spatiotemporal information regions compared to random
masking techniques as shown in Fig. 1. This efficient token allocation also
enables high masking ratios (i.e., 95%) for pre-training MAEs. This ultimately
reduces the GPU memory requirements and expedites pre-training while improving
accuracy on downstream tasks. In summary, our contributions are:

  * •

We propose AdaMAE, a novel, adaptive, and end-to-end trainable token sampling
strategy for MAEs that takes into account the spatiotemporal properties of all
input tokens to sample fewer but informative tokens.

  * •

We empirically show that AdaMAE samples more tokens from high spatiotemporal
information regions of the input, resulting in learning meaningful
representations for downstream tasks.

  * •

We demonstrate the efficiency of AdaMAE in terms of performance and GPU memory
against random “patch”, “tube”, and “frame” sampling by conducting a thorough
ablation study on the SSv2 dataset.

  * •

We show that our AdaMAE outperforms state-of-the-art (SOTA) by 0.7% and 1.1%
(in top-1) improvements on SSv2 and Kinetics-400, respectively.

##  2 Related Work

###  2.1 Masked prediction

Masked prediction has been widely successful in natural language understanding
(e.g. Generative Pre-Training (GPT) [38] and bidirectional encoder (BERT)
[7]). Many researchers have investigated applying masked prediction to
representation learning for images and videos. Generative pre-training from
pixels (iGPT) [6] is the first proof of concept in this direction, where
masked pixel prediction is performed. However, this pixel-based method has a
high pre-training computation cost and performs worse compared to ConvNets.
With the introduction of the Vision Transformer (ViT) [8], the focus shifted
from pixels to patches. The concept of patches enables the ViTs to follow the
masked language modeling task in BERT by predicting masked image patches
(called iBERT) for visual pre-training.

Although initial ViT experiments for representation learning have shown
inferior performance compared to contrastive learning methods [22, 59, 60,
37], subsequent developments such as BERT pre-training including BEiT [2],
BEVT [49], and masked auto-encoders (MAEs) including MaskFeat [51],
spatiotemporal-learner [17], SimMIM [54], MFM [54], VideoMAE [46], ConvMAE
[13], OmniMAE [14], MIMDET [10], paved the way for superior performance and
lower pre-training times.

Since image patches do not have off-the-shelf tokens as words in languages,
BEiT [2] and BEVT [49] adopt a two-stage pre-training strategy, where an
image/video tokenizer is trained via a discrete variational auto-encoder
(dVAE) [39] followed by masked patch prediction using the pre-trained
tokenizer [58]. This two-stage training and the dependence on a pre-trained
dVAE to generate originally continuous but intentionally discretized target
visual tokens leaves room for improving the efficiency. On the other hand,
MAEs [2, 17, 54, 46, 14, 10] directly predict the masked patches from the
visible tokens for pre-training. Moreover, experiments suggest that a high
masking ratio (75% for images [2, 17] and 90% for videos [54, 46]) leads to
better fine-tuning performance. The encoder of MAEs only operates on the
visible patches and the decoder is lightweight for faster pre-training. This
results in MAE pre-training which is three times faster than BEiT [17, 11, 52]
and BEVT [49].

###  2.2 Mask sampling

Various ablation experiments of masked autoencoders on both images and videos
have shown that the performance on downstream tasks depends on the masking
strategy [54, 46, 11]. Various random masking strategies have been proposed
including grid, block, and patch for images [17, 55] and tube, frame and patch
for videos [11, 54, 26, 35, 40]. Experiments have shown that a mask sampling
technique that works well on one dataset might not be ideal for another
dataset. For instance, Video-MAE [46] achieves the best action classification
performance on the SSv2 [15] dataset with random tube masking, whereas
SpatiotemporalMAE [11] achieves its best performance on Kinetics-400 [24] with
random patch masking. This could be due to the diversity of underlying scenes
in the dataset, different acquisition conditions (_e.g_., frame rate), and
high/low spatiotemporal information regions in videos. Even within a dataset,
we observe significant diversity among the videos, where some videos have
dynamic scenes, some have a stationary background and moving foreground (see
Fig. 1), and some videos have almost stationary scenes (no object is moving).
Since the existing masking techniques sample tokens randomly from space
(tube), time (frame), or spacetime (patch) and do not depend on the underlying
scene, it is possible that the decoder tries to reconstruct high
spatiotemporal information regions when most of the visible tokens belong to
low spatiotemporal information regions [19]. Consequently, a large number of
pre-training iterations are required to learn meaningful representations [46,
11] for downstream tasks. Inspired by this phenomenon, we design an adaptive
masking technique based on reinforcement learning that predicts the sampling
distribution for a given video.

###  2.3 Reinforcement learning

Reinforcement learning (RL) [23] has become an increasingly popular research
area due to its effectiveness in various tasks, including playing Atari games
[33], image captioning [56], person re-identification [25], video
summarization [41, 61], etc. Policy gradient methods [53] for RL focus on
selecting optimal policies that maximize expected return by gradient descent.
REINFORCE [42] is commonly seen as the basis for policy gradient methods in
RL. However, its application in MAEs has yet to be explored. Our sampling
network learns a categorical distribution over all tokens to sample
informative visible tokens for pre-training MAEs. We use REINFORCE policy
gradient [42] method as an unbiased estimator for calculating gradients to
update the sampling network parameters $\theta$.

When the probability density function (estimated by the sampling network
$f_{\theta}$) is differentiable with respect to its parameters $\theta$, we
need to sample an action and compute probabilities $p(\cdot)$ to implement
policy gradient [42]:

$\Delta\theta=\alpha\cdot R\cdot\frac{\partial\log p(a)}{\partial\theta},$ (1)

where $R$ is the return, $p(a)$ is the probability of taking action $a$, and
$\alpha$ is the learning rate. In our case, we sample a mask (the action)
based on the probability distribution estimated by the sampling network,
reconstruct masked tokens from the MAE (the environment), and then utilize
reconstruction error (the reward) to compute the expected return.

Figure 2: AdaMAE samples visible tokens based on the categorical distribution
estimated by the sampling network and reconstructs the missing ones with a ViT
encoder-decoder architecture. Since the sampling process is non-
differentiable, we optimize it by maximizing the expected reconstruction loss,
which results in the sampling network predicting high probability values for
tokens that may lead to high reconstruction errors. Our adaptive sampling
process samples more tokens from high spatiotemporal information regions and
fewer tokens from the low information or redundant regions.

##  3 Method

###  3.1 Architecture of AdaMAE

Fig. 2 shows our AdaMAE architecture which consists of four main components,
three of which (Tokenizer, Encoder, and Decoder) are standard to MAE along
with our proposed Adaptive Token Sampler.

#### Tokenizer:

Given an input video $\mathbf{V}$ of size
${\color[rgb]{0,0,1}T}\times{\color[rgb]{1,0,0}C}\times{\color[rgb]{0,.5,.5}H}\times{\color[rgb]{0,.5,.5}W}$,
where ${\color[rgb]{0,0,1}T}$ denotes the number of temporal frames,
${\color[rgb]{1,0,0}C}$ denotes the input (RGB) channels, and
${\color[rgb]{0,.5,.5}H}\times{\color[rgb]{0,.5,.5}W}$ is the spatial
resolution of a frame, we first pass it through a Tokenizer (i.e., 3D
convolution layer with kernel $K$ of size
$({\color[rgb]{0,0,1}t},{\color[rgb]{1,0,0}C},{\color[rgb]{0,.5,.5}h},{\color[rgb]{0,.5,.5}w})$
and stride $S$ of size
$({\color[rgb]{0,0,1}t},{\color[rgb]{0,.5,.5}h},{\color[rgb]{0,.5,.5}w})$, and
${\color[rgb]{1,0,0}d}$ output channels) to tokenize $\mathbf{V}$ into $N$
tokens of dimension ${\color[rgb]{1,0,0}d}$ denoted as $\mathbf{X}$, where
${\color[rgb]{.75,0,.25}N}={\color[rgb]{0,0,1}\frac{T}{t}}\times{\color[rgb]{0,.5,.5}\frac{H}{h}}\times{\color[rgb]{0,.5,.5}\frac{W}{w}}$.
Next, we inject the positional information into the tokens by utilizing the
fixed 3D periodic positional encoding scheme introduced in [47].

#### Adaptive Token Sampler:

Given the tokens $\mathbf{X}$ resulting from the Tokenizer, we pass them
through a light-weight Multi-Head Attention (MHA) network followed by a Linear
layer and a Softmax activation to obtain the probability scores
$\mathbf{P}\in\mathbb{R}^{{\color[rgb]{.75,0,.25}N}}$ for all tokens as
follows:

$\displaystyle\mathbf{Z}$ $\displaystyle=\texttt{MHA}(\mathbf{X});\hskip
10.0pt\mathbf{Z}\in\mathbb{R}^{{\color[rgb]{.75,0,.25}N}\times{\color[rgb]{1,0,0}d}},$
(2) $\displaystyle\mathbf{P}$
$\displaystyle=\texttt{Softmax}(\texttt{Linear}(\mathbf{Z}));\hskip
10.0pt\mathbf{P}\in\mathbb{R}^{{\color[rgb]{.75,0,.25}N}}.$ (3)

We then assign an $N$-dimensional categorical distribution [32] over
$\mathbf{P}$ ($\boldsymbol{p}\sim\text{Categorical}(N,\mathbf{P}))$ and draw
(without replacement) a set of visible token indices $\boldsymbol{I}_{v}$
(hence the set of masked token indices is given by
$\boldsymbol{I}_{m}=U-\boldsymbol{I}_{v}$, where
$U$=$\\{1,2,3,\cdots,{\color[rgb]{.75,0,.25}N}\\}$ is the set of all indices,
i.e., $\boldsymbol{I}_{m}$ is the set complement of $\boldsymbol{I}_{v}$). The
number of sampled visible tokens $N_{v}$ is computed based on a pre-defined
masking ratio $\rho\in(0,1)$ and equals to
${\color[rgb]{.75,0,.25}N}\times(1-\rho)$.

#### Encoder:

Next, we generate latent representations $\mathbf{F}_{v}$ by passing sampled
visible tokens $\mathbf{X}_{v}$ through the ViTEncoder.

#### Decoder:

The visible token representations $\mathbf{F}_{v}$ are concatenated with a
fixed learnable representation $f_{m}$ for masked tokens. Next, positional
information is added [37] for both representations, instead of shuffling them
back to the original order. Finally, we pass this through a light-weight
transformer decoder to obtain the predictions $\mathbf{\widehat{V}}$.

###  3.2 Optimizing AdaMAE

#### Masked reconstruction loss $\mathcal{L}_{R}$:

We utilize the mean squared error (MSE) loss between the predicted and patch
normalized111Each patch is normalized based on the patch mean and variance.
ground-truth RGB values [17] of the masked tokens to optimize the MAE
(parameterzied by $\phi$) as follows:

$\begin{split}\mathcal{L}_{\text{R}}(\phi)&=\frac{1}{N-N_{v}}\sum_{i\in
I_{m}}\lVert\mathbf{\widehat{V}}_{i}-\mathbf{\widetilde{V}}_{i}\rVert_{2},\end{split}$
(4)

where $\widehat{\mathbf{V}}$ denotes the predicted tokens,
$\mathbf{\widetilde{V}}$ denotes the local patch normalized ground-truth RGB
values [46].

#### Adaptive sampling loss $\mathcal{L}_{S}$:

We optimize the adaptive token sampling network (parameterized by $\theta$)
using sampling loss $\mathcal{L}_{\text{S}}$, which enables gradient update
independent of the MAE (parameterized by $\phi$). The formulation of
$\mathcal{L}_{\text{S}}$ is motivated by the REINFORCE algorithm in RL, where
we consider the visible token sampling process as an action, the MAE (ViT-
backbone and decoders) as an environment, and the masked reconstruction loss
$\mathcal{L}_{R}$ as the return. Following the expected reward maximization in
the REINFORCE algorithm, we propose to optimize the sampling network by
maximizing the expected reconstruction error $\mathbb{E}[\mathcal{L}_{R}]$.

Figure 3: Understanding the formulation of $L_{S}$. We observe high $L_{R}$ in
high activity/information regions (third row). Hence, we propose to maximize
expected reconstruction error over masked tokens which ultimately results in
the sampling network predicting higher probability scores for high activity
regions and lower probability scores for low activity (i.e., background or
redundant) regions. See Appendix for more visualizations.

To elucidate why maximizing $\mathbb{E}[\mathcal{L}_{R}]$ works for adaptive
sampling, we use a visual example shown in Figure 3. Given a video (first row)
with high activity/information (i.e., the dancing couple) and low
activity/information (i.e., the teal color background) regions, we observe a
high reconstruction error (third row) around the foreground. Since our
objective is to sample more visible tokens from high activity regions and
fewer tokens from the background, we optimize the sampling network by
maximizing the expected reconstruction error over the masked tokens (denoted
by $\mathbb{E}[\mathcal{L}_{R}]$). When optimized with the above rule, the
adaptive token sampling network predicts high probability scores for the
tokens from the high activity regions compared to the tokens from the
background as shown in the fourth row. We observe that this adaptive token
sampling approach for MAEs closely aligns with non-uniform sampling in
compressed sensing, where more samples are assigned to the regions with high
activity and fewer to those with low activity. Since our adaptive sampling
allocates samples based on the level of spatiotemporal information, it
requires fewer tokens to achieve the same reconstruction error compared to
random sampling (which is not efficient in token allocation). This also
enables using extremely high masking ratios (95%) for MAEs which further
reduces the computational burden, thereby accelerating the pre-training
process.

The objective function to optimize our adaptive token sampling network can be
expressed as:

$\mathcal{L}_{S}(\theta)=-\mathbb{E}_{\theta}[\mathcal{L}_{R}(\phi)]=-\sum_{i\in\mathbf{I}_{m}}P_{\theta}^{i}\cdot\mathcal{L}_{R}^{i}(\phi),$
(5)

where $P_{\theta}^{i}$ is the probability of the mask token at index $i$
inferred from the adaptive token sampling network parameterized by $\theta$
and $\mathcal{L}_{R}^{i}$ is the reconstruction error of the $i$-th masked
token. Note that $\mathcal{L}_{R}(\phi)$ is the reconstruction error incurred
by MAE with parameters $\phi$. Also, we explicitly prevent gradient updates
from $\mathcal{L}_{S}(\theta)$ to propagate through the MAE (i.e., detach from
the computational graph).

Furthermore, we take logarithm of the probabilities to avoid the precision
errors caused by small probability values. Note that the negative sign is due
to gradient descent optimization, whilst the rule above assumes gradient
ascent.

##  4 Experimental Setup

#### Datasets.

We evaluate AdaMAE on two datasets: Something-Something-v2 (SSv2) [15] and
Kinetics-400 [24]. The SSv2 dataset is a relatively large-scale video dataset,
consisting of approximately 170k videos for training, and 20k videos for
validation, categorized into 174 action classes. Kinetics-400 is also a large-
scale dataset which contains 400 action classes, $\sim$240k training videos,
and $\sim$20k validation videos. We conduct ablation studies on the SSv2
dataset and report results on both SSv2 and Kinetics-400.

#### Dataset preprocessing.

We closely follow VideoMAE [46] for dataset preprocessing. For both datasets,
we sample 16 RGB frames, each with $224\times 224$ pixels, from the raw video
with a temporal stride of 4, where the starting frame location is randomly
selected [11]. As part of the data augmentations for pre-training, we employ
random resized crops [43] in spatial domain, random scale $\in[0.5,1]$, and
random horizontal flipping [11].

#### Network architecture.

For our experiments we use vanilla ViT [8]. Specifically, we select ViT-Base
to save GPU memory and avoid longer pre-training time. We use patch size of
$2\times 3\times 16\times 16$ [1, 46, 11], resulting in
$(16/2)\times(3/3)\times(224/16)\times(224/16)=1568$ tokens for an input video
of size $16\times 3\times 224\times 224$. See supplementary material for more
network architecture details.

#### Pre-training setting.

For all experiments, the default number of pre-training epochs is 800 unless
otherwise noted. We use adamw [31] optimizer with a batch size of 32/GPU and 8
GPUs. See supplementary material for more details.

#### Evaluation on action classification.

In order to evaluate the quality of the pre-trained model, we perform end-to-
end fine-tuning (instead of linear probing [3, 17, 46, 11]). During inference,
we follow the common practice of multi-view testing [50, 34] where $K$
temporal clips (by default $K=2$ [46] and 7 [46, 11] on SSv2 and Kinetics,
respectively) to cover the video length. For each clip, we take 3 spatial
views [11, 46] to cover the complete image. The final prediction is the
average across all views.

##  5 Results and Discussion

###  5.1 Ablation studies

We perform pre-training using AdaMAE on ViT-Base backbone and then fine-tune
the encoder with supervision for evaluation on the SSV2 dataset. We present
our ablation study results in Table 1. In the following sections, by accuracy
we refer to top-1 accuracy unless stated otherwise.

case |  ratio |  top-1 |  top-5 |  memory
---|---|---|---|---
Tube [46] |  75 |  67.3 |  91.5 |  16.2 GB
Tube [46] |  90 |  69.3 |  92.3 |  14.7 GB
Random [11] |  75 |  67.9 |  90.6 |  16.2 GB
Random [11] |  90 |  68.3 |  91.8 |  14.7 GB
Frame [11, 46] |  87.5 |  61.5 |  87.6 |  12.8 GB
Adaptive (ours) |  95 |  70.04 |  92.70 |  14.4 GB
(a)

ratio |  top-1 |  top-5 |  memory
---|---|---|---
0.98 |  68.85 |  91.94 |  14.1 GB
0.95 |  70.04 |  92.70 |  14.4 GB
0.90 |  69.55 |  92.62 |  15.1 GB
0.85 |  68.06 |  91.38 |  15.9 GB
0.80 |  66.96 |  90.91 |  16.9 GB
(b)

blocks |  top-1 |  top-5 |  memory
---|---|---|---
1 |  68.86 |  92.07 |  9.2 GB
2 |  69.13 |  92.17 |  11.0 GB
4 |  70.04 |  92.70 |  14.4 GB
8 |  69.97 |  92.67 |  21.3 GB
(c)

case |  top-1 |  top-5
---|---|---
L1 loss (w norm.) |  69.12 |  91.42
L1 loss (w/o norm.) |  68.75 |  91.47
MSE loss (w norm.) |  70.04 |  92.70
MSE loss (w/o norm.) |  68.87 |  91.45
(d)

epochs |  top-1 |  top-5
---|---|---
200 |  66.42 |  90.59
500 |  69.20 |  92.50
600 |  69.47 |  92.52
800 |  70.04 |  92.70
(e)

case |  top-1 |  top-5 |  memory
---|---|---|---
MLP |  65.41 |  89.22 |  11.8 GB
MHA $(D=1,d=384)$ |  69.56 |  90.89 |  14.0 GB
MHA $(D=1,d=768)$ |  70.04 |  92.70 |  14.4 GB
MHA $(D=2,d=384)$ |  70.03 |  92.74 |  17.1 GB
(f)

Table 1: Ablation experiments on SSv2 dataset. We use ViT-Base [47] as the
backbone for all experiments. MHA $(D=2,d=384)$ denotes our adaptive token
sampling network with a depth of two and embedding dimension of $384$. All
pre-trained models are evaluated based on the evaluation protocol described in
Sec. 4. The default choice of our AdaMAE is highlighted in gray color. The GPU
memory consumption is reported for a batch size of 16 on a single GPU.

#### Adaptive vs. random patch, frame, and tube masking.

We compare different masking techniques (as illustrated in Fig. 1) in Table
LABEL:tab:mask_types. Random tube masking [46], which randomly samples masked
tokens in the 2D spatial domain and then extends those along the temporal
axis, works reasonably well with a high masking ratio (69.3% accuracy with 90%
masking). Random patch masking [11], which randomly masks tokens over
spacetime, also works well with high masking ratios (68.3% accuracy with 90%
masking vs. 67.3% accuracy with 75% masking) - note that we observe 1% drop in
performance compared to random tube masking [46]. However, random frame
masking, which masks out all tokens in randomly selected frames, performs
poorly (61.5% accuracy) compared to random patch and tube masking. Our
adaptive token sampling, which samples visible tokens based on a categorical
distribution (instead of assuming a fixed distribution) estimated from a
neural network by exploiting the spatiotemporal relationship of all tokens,
yields the best result (70.04% accuracy) –  0.7% improvement over random patch
and tube masking. Note that this improvement is achieved with a higher masking
ratio (95%) which requires less memory (14.4 GB vs. 14.7 GB) and results in
shorter pre-training time.

(a) Masking ratio $=85\%$.

(b) Masking ratio $=90\%$.

Figure 5: Mask visualizations of our AdaMAE for different masking ratios on
SSV2 dataset [15]. Given a video (first row), our AdaMAE first predicts the
categorical distribution (second row), and then samples the mask (third row)
from that distribution. Refer to the supplementary material for more
visualizations.

#### Masking ratio.

Table LABEL:tab:masking_ratio shows the performance of our model while using
different masking ratios. Our adaptive token sampling achieves the best
performance for masking ratio of 95% (70.04% accuracy); 5% higher masking
ratio compared to random patch masking in SpatiotemporalMAE [11] (90% masking)
and random tube masking in VideoMAE [46] (90% masking). As shown in Fig. 5(a)
and 5(b), we sample a relatively higher number of tokens from regions with
less redundancy and a small number of tokens from regions with high
redundancy. Hence, fewer tokens are required than random sampling to achieve
the same reconstruction error. 98% and 90% masking ratios also perform
reasonably well (68.85% and 69.55% accuracies, respectively), whereas we
observe a significant drop in performance for 85% and 80% masking ratios
(68.06% and 66.96% accuracies, respectively). For lower masking ratios, due to
large number of redundant visible patches being sampled, the network just
copies features from these patches, resulting in poor generalizations and drop
in performance.

#### Decoder depth.

We compare our performance for different decoder depths (i.e., number of
transformer blocks used) in Table LABEL:tab:decoder_depth. Increasing the
decoder depth from 1 block to 4 blocks increases the accuracy (from 68.86% to
70.04%); however, this comes with an additional longer pre-training time.
Increasing the decoder depth from 4 blocks to 8 blocks, however, results in a
slight drop in accuracy (from 70.04% to 69.97%). Hence, we consider 4
transformer blocks as the optimal decoder depth for AdaMAE, on par with the
observation made in VideoMAE [46] and SpatiotemporalMAE [11].

#### Reconstruction target.

Table LABEL:tab:loss_target shows the impact of employing different loss
functions and reconstruction targets. We use RGB pixel values as the
reconstruction target; instead of utilizing complicated features such as HoG
[51], which always comes with additional computational cost. Following an
improved performance with per-patch normalized pixel values for images in
ImageMAE [17] and also verified later for videos in VideoMAE [46] and
SpatiotemporalMAE [11], we consider two scenarios – with and without local
patch normalization. Regression over raw RGB pixels with the L1/MSE loss has
shown poor performance compared to regression over per-patch normalized
pixels. We observe that MSE loss has a slight advantage over L1 loss.

#### Pre-training epochs.

Next, we show in Table LABEL:tab:pretraining_epochs the effect of the number
of pre-training epochs on fine-tuning performance. Increasing the number of
pre-training epochs always increases the performance: for 200 epochs - 66.42%,
for 500 epochs 69.20%, for 600 epochs - 69.47%, for 700 epochs 69.68, and for
800 epochs we achieve the best result of 70.04%. We observe poor performance
when pre-training for fewer than 500 epochs. Hence, considering the trade-off
between pre-training time and performance, we recommend pre-training with
AdaMAE for at least 500 epochs.

#### Mask sampling network.

Finally, we investigate the effect of using different network architectures
for our adaptive token sampling network in Table LABEL:tab:adamae_network.
Considering the importance of a computationally lightweight design for an
adaptive token sampling network, we first experimented with a simple multi-
layer perceptron (MLP) network (see supplementary material). The results of
this MLP network were not encouraging, giving similar performance to random
patch masking. We visualize the predicted probability map to confirm that it
was uncorrelated to the video itself (see supplementary material). This is
expected since a simple MLP network cannot model the relationship between the
tokens as it operates only on the embedding dimension of each token. We next
experimented with an MHA network (see supplementary material). This network
can capture the spatiotemporal relationships between tokens through the
attention mechanism and is able to predict meaningful probability density
maps, as shown in Figs. 5(a), and 5(b). Increasing the number of MHA blocks
results in slight improvements in performance, albeit with more memory and
compute requirements. We selected a single MHA block as our adaptive token
sampling network for all other experiments to keep it as computationally
lightweight as possible. Furthermore, we experimented with different embedding
dimensions (i.e., $d$ and $d/2$) and observed improved performance when
operating MHA at its original embedding dimension $d$.

###  5.2 Main results and analysis

We compare the performance of AdaMAE with previous SOTA results for action
classification on the SSv2 [15] and Kinetics-400 [24] datasets. Our results
are presented in Table 2 (on SSv2) and Table 3 (on Kinetics-400) for the ViT-
Base backbone ($\sim$ 87M parameters).

MAEs (MaskFeat, VideoMAE, SpatioTemporalMAE, OmniMAE, and AdaMAE) generally
outperform previous supervised representation learning approaches (such as TDN
[48], TimeSformer [4], Motionformer [36], Video-Swin [29]), which use
ImageNet-1K (IN1K), ImageNet-21K (IN21K), Kinetics-400, and/or Kinetics-600
labels for supervision, by a significant margin on these datasets. This
empirically demonstrates the powerful representation learning capability of
masked reconstruction methods. Furthermore, they also outperform recent
contrastive learning approaches such as BEVT [49] and hybrid approaches (i.e.,
masked modeling and contrastive learning) such as VIMPAC [44].

We compare AdaMAE with recent MAE-based spatiotemporal representation learning
approaches: VideoMAE [46], SpatioTemporalMAE [11], and OmniMAE [14] with the
same ViT-Base backbone. Among these, VideoMAE performs best when pre-trained
with 90% random tube masking (69.3% and 80.9% in accuracies on SSv2 and
Kinetics-400, respectively). SpatioTemporalMAE achieves its best performance
with 90% random patch masking (68.3% and 81.3% accuracies on SSv2 and
Kinetics-400, respectively). OminiMAE shows lower performance than VideoMAE
and SpatiotemporalMAE on SSv2 and Kinetics-400 datasets (69.3% and 80.6%
accuracies on SSv2 and Kinetics-400, respectively) with 95% random patch
masking, even though it uses extra data (IN1K with 90% random patch masking,
and Kinetics-400 and SSv2 with 95% random masking). In contrast, our
AdaptiveMAE, which utilizes an adaptive masking scheme based on the
spatiotemporal information of a given video, achieves the best performance on
the SSv2 and Kinetics-400 datasets (70.0% and 81.7% accuracies, respectively)
with higher masking ratio (95%). This results in faster pre-training compared
to VideoMAE and SpatitemporalMAE and requires less GPU memory.

#### Transferability:

We investigate the transferability of AdaMAE pre-trained models by evaluating
their performance in scenarios where the pre-training and finetuning datasets
are different. Our AdaMAE pre-trained on Kinetics-400 achieves SOTA results of
69.9% (top-1 accuracy) and 92.7% (top-5 accuracy) on SSv2. On the other hand,
AdaMAE pre-trained on SSv2 achieves 81.2% (top-1 accuracy) and 94.5% (top-5
accuracy) on Kinetics-400, which is better than other frameworks.

Method | Backbone | Extra data | Extra labels | Pre. Epochs | Frames | GFLOPs | Param | Top-1 | Top-5
---|---|---|---|---|---|---|---|---|---
TSM${}_{two\ stream}$ [27] |  ResNet50$\times$2 | IN1K | ✓ | N/A | 16+16 |  130$\times$2$\times$3 | 49 | 66.0 | 90.5
TEINetEn [28] |  ResNet50$\times$2 | ✓ | N/A | 8+16 |  99$\times$10$\times$3 | 50 | 66.6 | N/A
TANetEn [30] |  ResNet50$\times$2 | ✓ | N/A | 8+16 |  99$\times$2$\times$3 | 51 | 66.0 | 90.1
TDNEn [48] |  ResNet101$\times$2 | ✓ | N/A | 8+16 |  198$\times$1$\times$3 | 88 | 69.6 | 92.2
SlowFast [12] | ResNet101 | Kinetics-400 | ✓ | N/A | 8+32 |  106$\times$1$\times$3 | 53 | 63.1 | 87.6
MViTv1 [9] | MViTv1-B | ✓ | N/A | 64 |  455$\times$1$\times$3 | 37 | 67.7 | 90.9
MViTv1 [9] | MViTv1-B | Kinetics-600 | ✓ | N/A | 32 |  170$\times$1$\times$3 | 37 | 67.8 | 91.3
MViTv1 [9] | MViTv1-B-24 | ✓ | N/A | 32 |  236$\times$1$\times$3 | 53 | 68.7 | 91.5
TimeSformer [4] | ViT-B | IN21K | ✓ | N/A | 8 |  196$\times$1$\times$3 | 121 | 59.5 | N/A
TimeSformer [4] | ViT-L | ✓ | N/A | 64 |  5549$\times$1$\times$3 | 430 | 62.4 | N/A
ViViT FE [1] | ViT-L | IN21K+Kinetics-400 | ✓ | N/A | 32 |  995$\times$4$\times$3 | N/A | 65.9 | 89.9
Motionformer [36] | ViT-B | ✓ | N/A | 16 |  370$\times$1$\times$3 | 109 | 66.5 | 90.1
Motionformer [36] | ViT-L | ✓ | N/A | 32 |  1185$\times$1$\times$3 | 382 | 68.1 | 91.2
Video Swin [29] | Swin-B | ✓ | N/A | 32 |  321$\times$1$\times$3 | 88 | 69.6 | 92.7
VIMPAC [44] | ViT-L | HowTo100M+DALLE | ✗ | N/A | 10 |  N/A$\times$10$\times$3 | 307 | 68.1 | N/A
BEVT-V [49] | Swin-B | Kinetics-400+DALLE | ✗ | N/A | 32 |  321$\times$1$\times$3 | 88 | 67.1 | N/A
BEVT [49] | Swin-B | IN-1K+Kinetics-400+DALLE | ✗ | N/A | 32 | 321$\times$1$\times$3 | 88 | 70.6 | N/A
MaskFeat↑312 [51] | MViT-L | Kinetics-400 | ✓ | N/A | 40 | 2828$\times$1$\times$3 | 218 | 74.4 | 94.6
MaskFeat↑312 [51] | MViT-L | Kinetics-600 | ✓ | N/A | 40 | 2828$\times$1$\times$3 | 218 | 75.0 | 95.0
MTV (B/2+S/4+Ti/8) [57] | ViT-B | Kinetics-400+I21K | ✓ | N/A | 32 | $384\times 4\times 3$ | 310 | 67.6 | 90.1
SpatioTemporalMAE [11] | ViT-B | _no external data_ | ✗ | 800 | 16 |  180$\times$2$\times$3 | 87 | 68.3 | 91.8
VideoMAE [46] | ViT-B | _no external data_ | ✗ | 800 | 16 |  180$\times$2$\times$3 | 87 | 69.3 | 92.3
OmniMAE [14] | ViT-B | IN1K | ✗ | 800 | 16 |  180$\times$5$\times$3 | 87 | 69.3 | N/A
AdaMAE ρ=95% (ours) | ViT-B | _no external data_ | ✗ | 800 | 16 | 180$\times$2$\times$3 | 87 | 70.0 | 92.7
Table 2: Comparison of our AdaMAE with SOTA methods on SSv2 [15]. We report the results for ViT-Base [47] architecture. Our model is pre-trained for the default setting in Table 1. The ✓ in extra labels tab denotes supervised data used for pre-training while ✗ denotes only unlabeled data is used for the pre-training. The N/A denotes these numbers are not available/reported in the paper. Method | Backbone | Extra data | Extra labels | Pre. Epochs | Frames | GFLOPs | Param | Top-1 | Top-5
---|---|---|---|---|---|---|---|---|---
NL I3D [50] | ResNet101 | IN1K | ✓ | N/A | 128 |  359$\times$10$\times$3 | 62 | 77.3 | 93.3
TANet [30] | ResNet152 | ✓ | N/A | 16 |  242$\times$4$\times$3 | 59 | 79.3 | 94.1
TDNEn [48] |  ResNet101×2 | ✓ | N/A | 8+16 |  198$\times$10$\times$3 | 88 | 79.4 | 94.4
Video Swin [29] | Swin-B | ✓ | N/A | 32 |  282$\times$4$\times$3 | 88 | 80.6 | 94.6
TimeSformer [4] | ViT-B | IN21K | ✓ | N/A | 8 |  196$\times$1$\times$3 | 121 | 78.3 | 93.7
TimeSformer [4] | ViT-L | ✓ | N/A | 96 |  8353$\times$1$\times$3 | 430 | 80.7 | 94.7
ViViT FE [1] | ViT-L | ✓ | N/A | 128 |  3980$\times$1$\times$3 | N/A | 81.7 | 93.8
Motionformer [36] | ViT-B | ✓ | N/A | 16 |  370$\times$10$\times$3 | 109 | 79.7 | 94.2
Motionformer [36] | ViT-L | ✓ | N/A | 32 |  1185$\times$10$\times$3 | 382 | 80.2 | 94.8
Video Swin [29] | Swin-L | ✓ | N/A | 32 | 604$\times$4$\times$3 | 197 | 83.1 | 95.9
ViViT FE [1] | ViT-L | JFT-300M | ✓ | N/A | 128 | 3980$\times$1$\times$3 | N/A | 83.5 | 94.3
ViViT [1] | ViT-H | JFT-300M | ✓ | N/A | 32 |  3981$\times$4$\times$3 | N/A | 84.9 | 95.8
VIMPAC [44] | ViT-L | HowTo100M+DALLE | ✗ | N/A | 10 |  N/A$\times$10$\times$3 | 307 | 77.4 | N/A
BEVT [49] | Swin-B | IN1K+DALLE | ✗ | N/A | 32 |  282$\times$4$\times$3 | 88 | 80.6 | N/A
ip-CSN [] | ResNet152 | _no external data_ | ✗ | N/A | 32 |  109$\times$10$\times$3 | 33 | 77.8 | 92.8
SlowFast [12] | R101+NL | ✗ | N/A | 16+64 |  234$\times$10$\times$3 | 60 | 79.8 | 93.9
MViTv1 [9] | MViTv1-B | ✗ | N/A | 32 |  170$\times$5$\times$1 | 37 | 80.2 | 94.4
MaskFeat [51] | MViT-L | ✗ | N/A | 16 | 377$\times$10$\times$1 | 218 | 84.3 | 96.3
MaskFeat↑352 [51] | MViT-L | Kinetics-600 | ✗ | N/A | 40 | 3790$\times$4$\times$3 | 218 | 87.0 | 97.4
VideoMAE [46] | ViT-B | _no external data_ | ✗ | 1600 | 16 |  180$\times$5$\times$3 | 87 | 80.9 | 94.7
VideoMAE [46] | ViT-L | ✗ | 1600 | 16 | 597$\times$5$\times$3 | 305 | 84.7 | 96.5
VideoMAE↑320 [46] | ViT-L | ✗ | 1600 | 16 | 3958$\times$5$\times$3 | 305 | 85.8 | 97.1
SpatioTemporalMAE [11] | ViT-B | _no external data_ | ✗ | 1600 | 16 |  180$\times$3$\times$7 | 87 | 81.3 | 94.9
SpatioTemporalMAE [11] | ViT-L | ✗ | 1600 | 16 | 598$\times$3$\times$7 | 305 | 84.8 | 96.2
SpatioTemporalMAE [11] | ViT-H | ✗ | 1600 | 16 | 1193$\times$3$\times$7 | 632 | 85.1 | 96.6
OmniMAE [11] | ViT-B | IN1K + SSv2 | ✗ | 1600 | 16 |  180$\times$3$\times$7 | 87 | 80.6 | N/A
OmniMAE↓512 [11] | ViT-L | ✗ | 1600 | 16 | 598$\times$3$\times$7 | 304 | 84.0 | N/A
OmniMAE [11] | ViT-H | ✗ | 1600 | 16 | 1193$\times$3$\times$7 | 632 | 84.8 | N/A
AdaMAE ρ=95% (ours) | ViT-B | _no external data_ | ✗ | 800 | 16 | 180$\times$5$\times$3 | 87 | 81.7 | 95.2
Table 3: Comparison of our AdaMAE with SOTA methods on Kinetics-400 [24]. We
report the results for ViT-Base [47] architecture. Our model is pre-trained
for the default setting in Table 1. The ✓ in extra labels tab denotes
supervised data used for pre-training while ✗ denotes only unlabeled data is
used for the pre-training. The N/A denotes these numbers are not
available/reported in the paper.

##  6 Limitations and Future Work

Although we have presented results for ViT-Base backbone, our approach for
adaptive token sampling scales-up for larger backbones (e.g., ViT-Large and
ViT-Huge) as well. We expect AdaMAE to achieve better results for these
settings based on the experiments in previous studies [46, 11], and we plan to
conduct similar studies in future. Since AdaMAE outputs a categorical
distribution on the tokens, it could be used for applications such as saliency
detection in videos. Moreover, AdaMAE needs only 5% of the video tokens to
represent the entire video reasonably well. Hence, it could be applied for
efficient video compression and retrieval.

##  7 Conclusion

We propose an adaptive masking technique for MAEs, AdaMAE, that efficiently
learns meaningful spatiotemporal representations from videos for downstream
tasks. Unlike existing masking methods such as random patch, tube, and frame
masking, AdaMAE samples visible tokens based on a categorical distribution. An
auxiliary network is optimized to learn the distribution by maximizing the
expected reconstruction error using policy gradients. AdaMAE outperforms
previous state of the art methods with ViT-Base model on Something-Something
v2 and Kinetics-400 datasets and learns better transferable features, while
lowering GPU memory requirements and masking pre-training faster.

##  Appendix A Supplementary material

###  A.1 Pseudocode for AdaMAE

The pseudocode for our AdaptiveTokenSampler network is given in Algorithm 1
and AdaMAE for 2.

Inputs: Tokenized video: $\boldsymbol{X}\in\mathbb{R}^{N\times d}$, Masking
ratio: $\rho\in(0,1)$

Outputs: Categorical distribution: $\boldsymbol{p}$, Sampled mask indices:
$\boldsymbol{I}_{m}$, Sampled mask: $\boldsymbol{M}$

$P=\texttt{TokenProbs}(\boldsymbol{X})$ $\triangleright$ token probabilities

$\boldsymbol{p}\sim\text{CAT}(\boldsymbol{P})$ $\triangleright$ categorical
distribution

$N_{\text{v}}=\texttt{int}(N\times(1-\rho))$ $\triangleright$ # of visible
tokens

$\boldsymbol{I}_{v}=\boldsymbol{p}.\texttt{sample}(N_{\text{vis}})$
$\triangleright$ visible token indices

$\boldsymbol{I}_{m}=\boldsymbol{U}-\boldsymbol{I}_{v}$ $\triangleright$ mask
token indices

$\boldsymbol{M}=\texttt{GetBooleanMask}(\boldsymbol{I}_{v},\boldsymbol{I}_{m})$
$\triangleright$ binary mask

Algorithm 1 Pseudo-code for AdaptiveTokenSampler.

The pseudocode for our complete AdaMAE is given in 2 (for simplicity we assume
a batch size of one).

Input: The video dataset $\mathcal{D}$ = $\\{\boldsymbol{V}_{i}:\text{ for
}i=1,2,3,\cdots,|\mathcal{D}|\\}$, Masking ratio: $\rho\in(0,1)$

for $\boldsymbol{V}_{i}\in\mathcal{D}$ do

$\boldsymbol{X}_{i}=\texttt{Tokenizer}(\boldsymbol{V}_{i})$
$\triangleright$Tokens

$\boldsymbol{X}_{i}=\boldsymbol{X}_{i}+\texttt{PosEmbd}$
$\triangleright$Positional embedding

$\boldsymbol{p},\boldsymbol{I}_{v},\boldsymbol{M}$
$=\texttt{AdaptiveTokenSampler}(\boldsymbol{X}_{i},\rho)$

$\boldsymbol{X}_{v}=\boldsymbol{X}_{i}[\sim\boldsymbol{M}]$ $\triangleright$
visible tokens

$\boldsymbol{F}_{v}=\texttt{ViTEncoder}(X_{v})$ $\triangleright$ visible feats

$\boldsymbol{F}_{v}=\boldsymbol{F}_{v}+\texttt{PosEmbd}[\sim\boldsymbol{M}]$

$\boldsymbol{F}_{m}=f_{m}+\texttt{PosEmbd}[\boldsymbol{M}]$ $\triangleright$
mask feats

$\boldsymbol{F}=\boldsymbol{F}_{v}\oplus\boldsymbol{F}_{m}$ $\triangleright$
visible + mask feats

$\widehat{\boldsymbol{X}}=\texttt{ViTDecoder}(\boldsymbol{F})$
$\triangleright$Decoder

$\widehat{\boldsymbol{X}}_{m}=\widehat{\boldsymbol{X}}[\boldsymbol{M}]$
$\triangleright$ masked prediction

$\boldsymbol{X}_{m}=\boldsymbol{X}[\boldsymbol{M}]$ $\triangleright$ masked GT

$\mathcal{L}_{R}=\lVert\widehat{\boldsymbol{X}}_{m}-\boldsymbol{X}_{m}\rVert_{2}$
$\triangleright$ reconstruction loss

$\mathcal{L}_{S}=-\left(\boldsymbol{p}.\texttt{LogProb}(\boldsymbol{I}_{m})\right)\cdot\mathcal{L}_{R}.detach()$
$\triangleright$ sampling loss

$\mathcal{L}=\mathcal{L}_{R}+1e-4\cdot\mathcal{L}_{S}$ $\triangleright$ final
loss

$\mathcal{L}.backward()$ $\triangleright$ back-propagation

end for

Algorithm 2 Pseudo-code for our AdaMAE.

###  A.2 Network architectures for adaptive sampling network

We consider two network architectures for our adaptive sampling network.

  1. 1.

MLP: Keeping the importance of a computationally light-weight design for an
adaptive sampling network, we first experimented with a simple MLP network for
the sampling network as shown in Fig. 6 (a). In this architecture, we process
all the tokens $(\mathbf{X}\in\mathbb{R}^{N\times d})$ through a Linear layer
with $\texttt{in\\_features}=\texttt{out\\_features}=d$ (denoted by
$\texttt{Linear}(d,d)$) followed by a $\texttt{Linear}(d,1)$ to bring down the
embedding dimension from $d$ to $1$. We then apply a $\texttt{Softmax}()$
layer to obtain the probability values $\mathbf{P}\in\mathbb{R}^{N}$.

Although this network is computationally very light-weight, the experimental
results were not encouraging. Specially, it was not able to capture the
spatiotemporal information of input tokens; resulted in predicted probability
density map to have no/very-less relationship with the high/low activity
regions. This resulted in poor performance as demonstrated in Table
LABEL:tab:adamae_network. This is understandable because it operates only on
the embedding dimension and not be able to model the interaction between the
patches that is necessary for predicting proper probability map.

  2. 2.

MHA: Motivated from the drawback that we observed with MLP-based sampling
network, we decided to utilize multi-head self-attention network for this
purpose, because it can properly model the interconnectivty between all the
patches through the attention mechanism. Since we want to keep it
computationally light-weight as much as possible, we experimented with the
effect of different number of blocks and reduced emebdding demention as shown
in Table LABEL:tab:adamae_network. By utilizing MHA-based sampling network, we
were able to generate visually appeaing probability density maps (as shown in
Figure 7-11) that are in line with our intuition for adaptive sampling.

Figure 6: The network architectures considered for adaptive token sampling
network: (a) MLP-based sampling network (b) MHA-based sampling network.

###  A.3 Additional examples to understand the formulation of sampling loss
$L_{S}$

Here we provide some assitional visualizations to futher understand our AdaMAE
for selected videos from SSv2 (Figure 7, 8, 9, 10, and 11) and K400 (Figure
12, 13, 14, 15, and 16).

For example, let us consider Figure 7. We see that most of the spatiotemporal
information is concentrated in the upper part of each frame (the region
containing the bottle and the part of a hand), making those patches difficult
to reconstruct accurately (see second and third rows). Since the proposed
AdaptiveSampling network is optimized by maximizng $\mathbb{E}[L_{R}]$, it
predicts higher probabilities for the patches from the high activity region.
Hence, when sampling the visible tokens, MAE gets relatively more tokens from
the high activity region than the low activity region as shown in the last
row.

We can make the similar observervations for the other examples as well.

Note that these results are for the default setting in Table 1 except here we
visualize at 100-th epoch of pre-training.

Figure 7: An example visualization of our adaptive sampling on SSv2 dataset.
Figure 8: An example visualization of our adaptive sampling on SSv2 dataset.
Figure 9: An example visualization of our adaptive sampling on SSv2 dataset.
Figure 10: An example visualization of our adaptive sampling on SSv2 dataset.
Figure 11: An example visualization of our adaptive sampling on SSv2 dataset.
Figure 12: An example visualization of our adaptive sampling on K400 dataset.
Figure 13: An example visualization of our adaptive sampling on K400 dataset.
Figure 14: An example visualization of our adaptive sampling on K400 dataset.
Figure 15: An example visualization of our adaptive sampling on K400 dataset.
Figure 16: An example visualization of our adaptive sampling on K400 dataset.

###  A.4 Encoder-decoder architecture

Table 4 summarizes the encoder-decoder architecture of our AdaMAE.
Specifically, we consider 16-frame valilla ViT-Base architecture for all
experiments. We use assymetirc encoder-decoder architecture for self-
supervised pre-training and discard the decoder during the fine-tuning.

Given a video we first extract 16 frames
(${\color[rgb]{1,0,0}3}\times{\color[rgb]{0,0,1}16}\times{\color[rgb]{0,1,0}224}\times{\color[rgb]{0,1,0}224}$).
We use temporal stride of $4$ and $2$ for K400 and SSv2 datasets,
respectively. Next we process these 16 frames through a Tokenizer which is
essentially a 3D convolution layer with kernel size of
${\color[rgb]{0,0,1}2}\times{\color[rgb]{0,1,0}16}\times{\color[rgb]{0,1,0}16}$,
stride of
${\color[rgb]{0,0,1}2}\times{\color[rgb]{0,1,0}16}\times{\color[rgb]{0,1,0}16}$
and output embedding dimention of 768. This process results in a total of 1568
tokens and each token is represented by a 768 dimention vector. Next, we
sample $(1-\rho)\times{\color[rgb]{.75,0,.25}1568}$ number of tokens as the
visible tokens from our adaptive token sampling network. These visible tokens
are then processed through the ViT encoder that comprises of 12 cascaded
multi-head self-attention blocks (MHA blocks). The outputs from the ViT
encoder is then combined with a fixed learnable representation for masked
tokens which results in the 1568 token represenrations. These 1568
representations are then process through a projectot which brings down their
embedding dimntion from 768 embedding dimention to 384 by an MLP layer. These
projected representationas are then process through the ViT-decoder which
consists of 4 MHA blocks followed by an MLP layer to bring the emebdding
dimention from 384 to the total number of pixels in a cube which given by
${\color[rgb]{0,0,1}2}\times{\color[rgb]{1,0,0}3}\times{\color[rgb]{0,1,0}16}\times{\color[rgb]{0,1,0}16}={\color[rgb]{0,1,0}1536}$.
This is finally reshaped back back to the original space and used to compute
the reconsruction loss.

Table 4: Encoder-Decoder architecture of our AdaMAE. MHA denotes joint space-time multi-head self-attention. Stage | ViT-Base | Output shape
---|---|---
Input Video |  stride ${\color[rgb]{0,0,1}4}\times{\color[rgb]{0,1,0}1}\times{\color[rgb]{0,1,0}1}$ for K400 | ${\color[rgb]{1,0,0}3}\times{\color[rgb]{0,0,1}16}\times{\color[rgb]{0,1,0}224}\times{\color[rgb]{0,1,0}224}$
stride
${\color[rgb]{0,0,1}2}\times{\color[rgb]{0,1,0}1}\times{\color[rgb]{0,1,0}1}$
for SSv2
Tokenization |  stride ${\color[rgb]{0,0,1}2}\times{\color[rgb]{0,1,0}16}\times{\color[rgb]{0,1,0}16}$ | ${\color[rgb]{.75,0,.25}1568}\times{\color[rgb]{1,0,0}768}$
emb. dim 768
Masking | Adaptive Masking | $[(1-\rho)\times{\color[rgb]{.75,0,.25}1568}]\times{\color[rgb]{1,0,0}768}$
masking ratio $\rho$
Encoder | $[MHA({\color[rgb]{1,0,0}768})]\times 12$ | $[(1-\rho)\times{\color[rgb]{.75,0,.25}1568}]\times{\color[rgb]{1,0,0}768}$
Projection | $MHA(384)$ | ${\color[rgb]{.75,0,.25}1568}\times{\color[rgb]{1,0,0}384}$
concat masked tokens
Decoder | $[MHA({\color[rgb]{1,0,0}384})]\times 4$ | $[(1-\rho)\times{\color[rgb]{.75,0,.25}1568}]\times{\color[rgb]{1,0,0}384}$
Projector | $MLP({\color[rgb]{1,0,0}1536})$ | ${\color[rgb]{.75,0,.25}1568}\times{\color[rgb]{1,0,0}1536}$
Reshaping | from 1536 to ${\color[rgb]{1,0,0}3}\times{\color[rgb]{0,0,1}2}\times{\color[rgb]{0,1,0}16}\times{\color[rgb]{0,1,0}16}$ | ${\color[rgb]{1,0,0}3}\times{\color[rgb]{0,0,1}16}\times{\color[rgb]{0,1,0}224}\times{\color[rgb]{0,1,0}224}$

###  A.5 Pre-training setting

Table 5 summarizes the pre-training setting on SSv2 and K400 dataset. In
addition, we linearly scale the base learning rate with respect to the overall
batch size, lr = base learning rate× batch size 256. We adopt the PyTorch and
DeepSpeed frameworks for faster training.

Table 5: Ptr-training setting on SSv2 and K400 datasets. Configuration | SSv2 | K400
---|---|---
Optimizer | Adamw
Optimizer betas | {0.9, 0.95}
Base learning rate | 1.5e-4
Weight decay | 5e-2
Learning rate shedule | cosine decay
Warmup epochs | 40
Flip augmentation | False | True
Augmentation | MultiScaleCrop

###  A.6 End-to-end fine tuning setting

Table 6 summarizes the end-to-end fine-tunining setting on SSv2 and K400
datasets.

Table 6: Ptr-training setting on SSv2 and K400 datasets. Configuration | SSv2 | K400
---|---|---
Optimizer | Adamw
Optimizer betas | {0.9, 0.999}
Base learning rate | 1.5e-4 | 1e-3
Layer-wse lr decay | 0.75 |
Weight decay | 5e-2
Learning rate shedule | cosine decay
Warmup epochs | 40
Flip augmentation | False | True
RandAug | (0.9, 0.05) |
Label smoothing | 0.1 |
Mixup | 0.8 |
Cutmix | 1.0 |
drop path | 0.1 |

###  A.7 Mask visualizations

Figure 17, 18, 19, and 20 show the adaptive mask visualizations for masking
ratio of 80%, 85%, 90%, and 95% for selected videos from SSv2 dataset.

Figure 17: Mask visualizations of our AdaMAE for 80% masking ratio on SSV2
dataset [15].Given a video (first row), our AdaMAE first predicts the
categorical distribution (second row), and then sample the mask (third row)
from that distribution. Colors closer red and blue denotes the patches with
high and low probability, respectively. In mask visualizations, black and
white corresponds to the masked and visible path locations, respectively.
Figure 18: Mask visualizations of our AdaMAE for 85% masking ratio on SSV2
dataset [15].Given a video (first row), our AdaMAE first predicts the
categorical distribution (second row), and then sample the mask (third row)
from that distribution. Colors closer red and blue denotes the patches with
high and low probability, respectively. In mask visualizations, black and
white corresponds to the masked and visible path locations, respectively.
Figure 19: Mask visualizations of our AdaMAE for 90% masking ratio on SSV2
dataset [15].Given a video (first row), our AdaMAE first predicts the
categorical distribution (second row), and then sample the mask (third row)
from that distribution. Colors closer red and blue denotes the patches with
high and low probability, respectively. In mask visualizations, black and
white corresponds to the masked and visible path locations, respectively.
Figure 20: Mask visualizations of our AdaMAE for 95% masking ratio on SSV2
dataset [15].Given a video (first row), our AdaMAE first predicts the
categorical distribution (second row), and then sample the mask (third row)
from that distribution. Colors closer red and blue denotes the patches with
high and low probability, respectively. In mask visualizations, black and
white corresponds to the masked and visible path locations, respectively.

## References

  * [1] Anurag Arnab, Mostafa Dehghani, Georg Heigold, Chen Sun, Mario Lučić, and Cordelia Schmid.  ViViT: A Video Vision Transformer, Nov. 2021.  arXiv:2103.15691 [cs].
  * [2] Hangbo Bao, Li Dong, Songhao Piao, and Furu Wei.  BEiT: BERT Pre-Training of Image Transformers, Sept. 2022\.  arXiv:2106.08254 [cs].
  * [3] Hangbo Bao, Li Dong, Songhao Piao, and Furu Wei.  BEiT: BERT Pre-Training of Image Transformers, Sept. 2022\.  arXiv:2106.08254 [cs].
  * [4] Gedas Bertasius, Heng Wang, and Lorenzo Torresani.  Is Space-Time Attention All You Need for Video Understanding?, June 2021.  arXiv:2102.05095 [cs].
  * [5] Jun Chen, Ming Hu, Boyang Li, and Mohamed Elhoseiny.  Efficient Self-supervised Vision Pretraining with Local Masked Reconstruction, June 2022.  arXiv:2206.00790 [cs].
  * [6] Mark Chen, Alec Radford, Rewon Child, Jeffrey Wu, Heewoo Jun, David Luan, and Ilya Sutskever.  Generative Pretraining From Pixels.  In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 1691–1703. PMLR, July 2020.
  * [7] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding, May 2019.  arXiv:1810.04805 [cs].
  * [8] 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, June 2021.  arXiv:2010.11929 [cs].
  * [9] Haoqi Fan, Bo Xiong, Karttikeya Mangalam, Yanghao Li, Zhicheng Yan, Jitendra Malik, and Christoph Feichtenhofer.  Multiscale Vision Transformers, Apr. 2021.  arXiv:2104.11227 [cs].
  * [10] Yuxin Fang, Shusheng Yang, Shijie Wang, Yixiao Ge, Ying Shan, and Xinggang Wang.  Unleashing Vanilla Vision Transformer with Masked Image Modeling for Object Detection, May 2022.  arXiv:2204.02964 [cs].
  * [11] Christoph Feichtenhofer, Haoqi Fan, Yanghao Li, and Kaiming He.  Masked Autoencoders As Spatiotemporal Learners, May 2022.  arXiv:2205.09113 [cs].
  * [12] Christoph Feichtenhofer, Haoqi Fan, Jitendra Malik, and Kaiming He.  SlowFast Networks for Video Recognition, Oct. 2019.  arXiv:1812.03982 [cs].
  * [13] Peng Gao, Teli Ma, Hongsheng Li, Ziyi Lin, Jifeng Dai, and Yu Qiao.  ConvMAE: Masked Convolution Meets Masked Autoencoders, May 2022.  arXiv:2205.03892 [cs].
  * [14] Rohit Girdhar, Alaaeldin El-Nouby, Mannat Singh, Kalyan Vasudev Alwala, Armand Joulin, and Ishan Misra.  OmniMAE: Single Model Masked Pretraining on Images and Videos, June 2022.  arXiv:2206.08356 [cs, stat].
  * [15] Raghav Goyal, Samira Ebrahimi Kahou, Vincent Michalski, Joanna Materzyńska, Susanne Westphal, Heuna Kim, Valentin Haenel, Ingo Fruend, Peter Yianilos, Moritz Mueller-Freitag, Florian Hoppe, Christian Thurau, Ingo Bax, and Roland Memisevic.  The ”something something” video database for learning and evaluating visual common sense, June 2017.  arXiv:1706.04261 [cs].
  * [16] Agrim Gupta, Stephen Tian, Yunzhi Zhang, Jiajun Wu, Roberto Martín-Martín, and Li Fei-Fei.  MaskViT: Masked Visual Pre-Training for Video Prediction, Aug. 2022.  arXiv:2206.11894 [cs].
  * [17] Kaiming He, Xinlei Chen, Saining Xie, Yanghao Li, Piotr Dollár, and Ross Girshick.  Masked Autoencoders Are Scalable Vision Learners, Dec. 2021\.  arXiv:2111.06377 [cs].
  * [18] Dan Hendrycks, Mantas Mazeika, Saurav Kadavath, and Dawn Song.  Using Self-Supervised Learning Can Improve Model Robustness and Uncertainty.  In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
  * [19] Zejiang Hou, Fei Sun, Yen-Kuang Chen, Yuan Xie, and Sun-Yuan Kung.  MILAN: Masked Image Pretraining on Language Assisted Representation, Aug. 2022.  arXiv:2208.06049 [cs].
  * [20] Lang Huang, Shan You, Mingkai Zheng, Fei Wang, Chen Qian, and Toshihiko Yamasaki.  Green Hierarchical Vision Transformer for Masked Image Modeling, May 2022.  arXiv:2205.13515 [cs].
  * [21] Ashish Jaiswal, Ashwin Ramesh Babu, Mohammad Zaki Zadeh, Debapriya Banerjee, and Fillia Makedon.  A Survey on Contrastive Self-Supervised Learning.  Technologies, 9(1):2, Mar. 2021.  Number: 1 Publisher: Multidisciplinary Digital Publishing Institute.
  * [22] Li Jing, Pascal Vincent, Yann LeCun, and Yuandong Tian.  Understanding Dimensional Collapse in Contrastive Self-supervised Learning, Apr. 2022.  arXiv:2110.09348 [cs].
  * [23] L. P. Kaelbling, M. L. Littman, and A. W. Moore.  Reinforcement Learning: A Survey.  Journal of Artificial Intelligence Research, 4:237–285, May 1996\.
  * [24] Will Kay, Joao Carreira, Karen Simonyan, Brian Zhang, Chloe Hillier, Sudheendra Vijayanarasimhan, Fabio Viola, Tim Green, Trevor Back, Paul Natsev, Mustafa Suleyman, and Andrew Zisserman.  The Kinetics Human Action Video Dataset, May 2017.  arXiv:1705.06950 [cs].
  * [25] Xu Lan, Hanxiao Wang, Shaogang Gong, and Xiatian Zhu.  Deep Reinforcement Learning Attention Selection for Person Re-Identification, July 2018.  arXiv:1707.02785 [cs].
  * [26] Alex X. Lee, Anusha Nagabandi, Pieter Abbeel, and Sergey Levine.  Stochastic Latent Actor-Critic: Deep Reinforcement Learning with a Latent Variable Model, Oct. 2020.  arXiv:1907.00953 [cs, stat].
  * [27] Ji Lin, Chuang Gan, and Song Han.  TSM: Temporal Shift Module for Efficient Video Understanding, Aug. 2019.  arXiv:1811.08383 [cs].
  * [28] Zhaoyang Liu, Donghao Luo, Yabiao Wang, Limin Wang, Ying Tai, Chengjie Wang, Jilin Li, Feiyue Huang, and Tong Lu.  TEINet: Towards an Efficient Architecture for Video Recognition, Nov. 2019.  arXiv:1911.09435 [cs].
  * [29] Ze Liu, Jia Ning, Yue Cao, Yixuan Wei, Zheng Zhang, Stephen Lin, and Han Hu.  Video Swin Transformer, June 2021.  arXiv:2106.13230 [cs].
  * [30] Zhaoyang Liu, Limin Wang, Wayne Wu, Chen Qian, and Tong Lu.  TAM: Temporal Adaptive Module for Video Recognition, Aug. 2021\.  arXiv:2005.06803 [cs].
  * [31] Ilya Loshchilov and Frank Hutter.  Decoupled Weight Decay Regularization, Jan. 2019.  arXiv:1711.05101 [cs, math].
  * [32] Francis Henry Marriott, Charles.  A dictionary of statistical terms. Longman Scientific & Technical, 5-th edition, 1990.
  * [33] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller.  Playing Atari with Deep Reinforcement Learning, Dec. 2013.  arXiv:1312.5602 [cs].
  * [34] Daniel Neimark, Omri Bar, Maya Zohar, and Dotan Asselmann.  Video Transformer Network, Aug. 2021.  arXiv:2102.00719 [cs].
  * [35] Aaron van den Oord, Yazhe Li, and Oriol Vinyals.  Representation Learning with Contrastive Predictive Coding, Jan. 2019.  arXiv:1807.03748 [cs, stat].
  * [36] Mandela Patrick, Dylan Campbell, Yuki M. Asano, Ishan Misra, Florian Metze, Christoph Feichtenhofer, Andrea Vedaldi, and João F. Henriques.  Keeping Your Eye on the Ball: Trajectory Attention in Video Transformers, Oct. 2021.  arXiv:2106.05392 [cs].
  * [37] Rui Qian, Tianjian Meng, Boqing Gong, Ming-Hsuan Yang, Huisheng Wang, Serge Belongie, and Yin Cui.  Spatiotemporal Contrastive Video Representation Learning.  In 2021 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 6960–6970, Nashville, TN, USA, June 2021\. IEEE.
  * [38] Alec Radford, Karthik Narasimhan, Tim Salimans, and Ilya Sutskever.  Improving Language Understanding by Generative Pre-Training.  cs.ubc, page 12, 2018.
  * [39] Aditya Ramesh, Mikhail Pavlov, Gabriel Goh, Scott Gray, Chelsea Voss, Alec Radford, Mark Chen, and Ilya Sutskever.  Zero-Shot Text-to-Image Generation, Feb. 2021.  arXiv:2102.12092 [cs].
  * [40] Evan Shelhamer, Parsa Mahmoudieh, Max Argus, and Trevor Darrell.  Loss is its own Reward: Self-Supervision for Reinforcement Learning, Mar. 2017.  arXiv:1612.07307 [cs].
  * [41] Xinhui Song, Ke Chen, Jie Lei, Li Sun, Zhiyuan Wang, Lei Xie, and Mingli Song.  Category driven deep recurrent neural network for video summarization.  In 2016 IEEE International Conference on Multimedia & Expo Workshops (ICMEW), pages 1–6, July 2016.
  * [42] Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour.  Policy Gradient Methods for Reinforcement Learning with Function Approximation.  In Advances in Neural Information Processing Systems, volume 12. MIT Press, 1999.
  * [43] Christian Szegedy, Wei Liu, Yangqing Jia, Pierre Sermanet, Scott Reed, Dragomir Anguelov, Dumitru Erhan, Vincent Vanhoucke, and Andrew Rabinovich.  Going Deeper with Convolutions, Sept. 2014.  arXiv:1409.4842 [cs].
  * [44] Hao Tan, Jie Lei, Thomas Wolf, and Mohit Bansal.  VIMPAC: Video Pre-Training via Masked Token Prediction and Contrastive Learning, June 2021.  arXiv:2106.11250 [cs].
  * [45] Chenxin Tao, Xizhou Zhu, Gao Huang, Yu Qiao, Xiaogang Wang, and Jifeng Dai.  Siamese Image Modeling for Self-Supervised Vision Representation Learning, July 2022.  arXiv:2206.01204 [cs].
  * [46] Zhan Tong, Yibing Song, Jue Wang, and Limin Wang.  VideoMAE: Masked Autoencoders are Data-Efficient Learners for Self-Supervised Video Pre-Training, July 2022.  arXiv:2203.12602 [cs].
  * [47] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin.  Attention Is All You Need, Dec. 2017.  arXiv:1706.03762 [cs].
  * [48] Limin Wang, Zhan Tong, Bin Ji, and Gangshan Wu.  TDN: Temporal Difference Networks for Efficient Action Recognition, Mar. 2021.  arXiv:2012.10071 [cs].
  * [49] Rui Wang, Dongdong Chen, Zuxuan Wu, Yinpeng Chen, Xiyang Dai, Mengchen Liu, Yu-Gang Jiang, Luowei Zhou, and Lu Yuan.  BEVT: BERT Pretraining of Video Transformers, Mar. 2022.  arXiv:2112.01529 [cs].
  * [50] Xiaolong Wang, Ross Girshick, Abhinav Gupta, and Kaiming He.  Non-local Neural Networks, Apr. 2018.  arXiv:1711.07971 [cs].
  * [51] Chen Wei, Haoqi Fan, Saining Xie, Chao-Yuan Wu, Alan Yuille, and Christoph Feichtenhofer.  Masked Feature Prediction for Self-Supervised Visual Pre-Training, Dec. 2021.  arXiv:2112.09133 [cs].
  * [52] Alexander Wettig, Tianyu Gao, Zexuan Zhong, and Danqi Chen.  Should You Mask 15% in Masked Language Modeling?, May 2022\.  arXiv:2202.08005 [cs].
  * [53] Ronald J. Williams.  Simple statistical gradient-following algorithms for connectionist reinforcement learning.  Machine Learning, 8(3):229–256, May 1992.
  * [54] Jiahao Xie, Wei Li, Xiaohang Zhan, Ziwei Liu, Yew Soon Ong, and Chen Change Loy.  Masked Frequency Modeling for Self-Supervised Visual Pre-Training, June 2022.  arXiv:2206.07706 [cs].
  * [55] Zhenda Xie, Zheng Zhang, Yue Cao, Yutong Lin, Jianmin Bao, Zhuliang Yao, Qi Dai, and Han Hu.  SimMIM: A Simple Framework for Masked Image Modeling, Apr. 2022.  arXiv:2111.09886 [cs].
  * [56] Kelvin Xu, Jimmy Ba, Ryan Kiros, Kyunghyun Cho, Aaron Courville, Ruslan Salakhutdinov, Richard Zemel, and Yoshua Bengio.  Show, Attend and Tell: Neural Image Caption Generation with Visual Attention, Apr. 2016.  arXiv:1502.03044 [cs].
  * [57] Shen Yan, Xuehan Xiong, Anurag Arnab, Zhichao Lu, Mi Zhang, Chen Sun, and Cordelia Schmid.  Multiview Transformers for Video Recognition, May 2022.  arXiv:2201.04288 [cs].
  * [58] Chaoning Zhang, Chenshuang Zhang, Junha Song, John Seon Keun Yi, Kang Zhang, and In So Kweon.  A Survey on Masked Autoencoder for Self-supervised Learning in Vision and Beyond, July 2022.  arXiv:2208.00173 [cs].
  * [59] Chaoning Zhang, Kang Zhang, Trung X. Pham, Axi Niu, Zhinan Qiao, Chang D. Yoo, and In So Kweon.  Dual Temperature Helps Contrastive Learning Without Many Negative Samples: Towards Understanding and Simplifying MoCo, Mar. 2022.  arXiv:2203.17248 [cs].
  * [60] Chaoning Zhang, Kang Zhang, Chenshuang Zhang, Trung X. Pham, Chang D. Yoo, and In So Kweon.  How Does SimSiam Avoid Collapse Without Negative Samples? A Unified Understanding with Self-supervised Contrastive Learning, Mar. 2022.  arXiv:2203.16262 [cs].
  * [61] Kaiyang Zhou, Yu Qiao, and Tao Xiang.  Deep Reinforcement Learning for Unsupervised Video Summarization with Diversity-Representativeness Reward, Feb. 2018.  arXiv:1801.00054 [cs] version: 3.


We start by observing that for $i_{1}\neq i_{2}\in C^{*}$ and $j_{1}\neq
j_{2}\in[n]\setminus C^{*}$ we have that

$e(i_{1},C^{*}\setminus\\{i_{2}\\})\overset{d}{=}N((\gamma n-2)\mu_{1},(\gamma
n-2)\tau^{2})$ $e(i_{2},C^{*}\setminus\\{i_{1}\\})\overset{d}{=}N((\gamma
n-2)\mu_{1},(\gamma n-2)\tau^{2})$ $e_{i_{1},i_{2}}\overset{d}{=}\mu_{1}+\tau
N(0,1)$ $e(j_{1},C^{*}\setminus\\{i_{1}\\})\overset{d}{=}N((\gamma
n-1)\mu_{2},(\gamma n-1)\tau^{2})$
$e(j_{2},C^{*}\setminus\\{i_{2}\\})\overset{d}{=}N((\gamma n-1)\mu_{2},(\gamma
n-1)\tau^{2})$

are jointly independent normal random variables and we have that following
with $Z_{1},Z_{2},Z$ being three IID standard Gaussian random variables.

$\displaystyle\mathbb{P}[\mathcal{C}_{(i_{1},j_{1})}\cap\mathcal{C}_{(i_{2},j_{2})}]$
$\displaystyle=\mathbb{P}\left[\left\\{e(i_{1},C^{*})<e(j_{1},C^{*}\setminus\\{i_{1}\\})\right\\}\bigcap\left\\{e(i_{2},C^{*})<e(j_{2},C^{*}\setminus\\{i_{2}\\})\right\\}\right]$
$\displaystyle=\mathbb{P}\left[\left\\{e(i_{1},C^{*}\setminus\\{i_{2}\\})+e_{i_{1},i_{2}}<e(j_{1},C^{*}\setminus\\{i_{1}\\})\right\\}\right.$
$\displaystyle\quad\bigcap\left\\{e(i_{2},C^{*}\setminus\\{i_{1}\\})+e_{i_{1},i_{2}}<e(j_{2},C^{*}\setminus\\{i_{2}\\})\right\\}\Big{]}$
$\displaystyle=\mathbb{P}\left[\left\\{N((\gamma n-2)\mu_{1},(\gamma
n-2)\tau^{2})+e_{i_{1},i_{2}}<N((\gamma n-1)\mu_{2},(\gamma
n-1)\tau^{2})\right\\}\right.$ $\displaystyle\quad\bigcap\left\\{N((\gamma
n-2)\mu_{1},(\gamma n-2)\tau^{2})+e_{i_{1},i_{2}}<N((\gamma
n-1)\mu_{2},(\gamma n-1)\tau^{2})\right\\}\Big{]}$
$\displaystyle=\mathbb{P}\left[\left\\{(\gamma n-1)(\mu_{1}-\mu_{2})+\tau
Z<\tau\sqrt{2\gamma n-3}Z_{1}\right\\}\right.$
$\displaystyle\quad\bigcap\left\\{(\gamma n-1)(\mu_{1}-\mu_{2})+\tau
Z<\tau\sqrt{2\gamma n-3}Z_{2}\right\\}\Big{]}$
$\displaystyle=\mathbb{P}\left[\left\\{Z_{1}>\frac{Z}{\sqrt{2\gamma
n-3}}+(1+o(1))s\sqrt{\log n}\right\\}\right.$
$\displaystyle\quad\bigcap\left\\{Z_{2}>\frac{Z}{\sqrt{2\gamma
n-3}}+(1+o(1))s\sqrt{\log n}\right\\}\Big{]}$

where we denote that $s=\frac{(\alpha-\beta)\sqrt{\gamma}}{\tau\sqrt{2}}$.
Further, for $i\in C^{*},j\in[n]\setminus C^{*}$ we have from Lemma 41

$\mathbb{P}\left[\mathcal{C}_{ij}\right]=\mathbb{P}\left[\left\\{Z_{1}>\frac{Z}{\sqrt{2\gamma
n-3}}+(1+o(1))s\sqrt{\log n}\right\\}\right]\sim\frac{1}{s\sqrt{\log
n}}\phi(s\sqrt{\log n})$ (101)
$\mathbb{P}[\mathcal{C}_{(i_{1},j_{1})}\cap\mathcal{C}_{(i_{2},j_{2})}]\sim\left(\frac{1}{s\sqrt{\log
n}}\phi(s\sqrt{\log n})\right)^{2}$ (102)

As a consequence, we have the following asymptotic equality.

$\frac{\sum_{i_{1}\neq i_{2}\in C^{*},j_{1}\neq j_{2}\in[n]\setminus
C^{*}}\mathbb{P}\left[\mathcal{C}_{(i_{1},j_{1})}\cap\mathcal{C}_{(i_{2},j_{2})}\right]}{\left(\sum_{(i,j)\in
C^{*}\times[n]\setminus
C^{*}}\mathbb{P}\left[\mathcal{C}_{ij}\right]\right)^{2}}\sim\frac{\gamma
n(\gamma n-1)((1-\gamma)n-1)(1-\gamma)n}{\gamma^{2}(1-\gamma)^{2}n^{4}}\sim 1$

It remains to establish that the following two holds.

$\frac{\sum_{i_{1}=i_{2}\in C^{*},j_{1}\neq j_{2}\in[n]\setminus
C^{*}}\mathbb{P}\left[\mathcal{C}_{(i_{1},j_{1})}\cap\mathcal{C}_{(i_{2},j_{2})}\right]}{\left(\sum_{(i,j)\in
C^{*}\times[n]\setminus
C^{*}}\mathbb{P}\left[\mathcal{C}_{ij}\right]\right)^{2}}\sim\frac{\gamma
n(1-\gamma)^{2}n^{2}\mathbb{P}\left[\mathcal{C}_{(i,j_{1})}\cap\mathcal{C}_{(i,j_{2})}\right]}{\gamma^{2}n^{2}(1-\gamma)^{2}n^{2}\mathbb{P}\left[\mathcal{C}_{ij}\right]^{2}}\sim\frac{\mathbb{P}\left[\mathcal{C}_{(i,j_{1})}\cap\mathcal{C}_{(i,j_{2})}\right]}{\gamma
n\mathbb{P}\left[\mathcal{C}_{ij}\right]^{2}}\sim 0$ $\frac{\sum_{i_{1}\neq
i_{2}\in C^{*},j_{1}=j_{2}\in[n]\setminus
C^{*}}\mathbb{P}\left[\mathcal{C}_{(i_{1},j_{1})}\cap\mathcal{C}_{(i_{2},j_{2})}\right]}{\left(\sum_{(i,j)\in
C^{*}\times[n]\setminus
C^{*}}\mathbb{P}\left[\mathcal{C}_{ij}\right]\right)^{2}}\sim\frac{\gamma^{2}n^{2}(1-\gamma)n\mathbb{P}\left[\mathcal{C}_{(i_{1},j)}\cap\mathcal{C}_{(i_{2},j)}\right]}{\gamma^{2}n^{2}(1-\gamma)^{2}n^{2}\mathbb{P}\left[\mathcal{C}_{ij}\right]^{2}}\sim\frac{\mathbb{P}\left[\mathcal{C}_{(i_{1},j)}\cap\mathcal{C}_{(i_{2},j)}\right]}{(1-\gamma)n\mathbb{P}\left[\mathcal{C}_{ij}\right]^{2}}\sim
0$

For $i\in C^{*}$ and $j_{1}\neq j_{2}\in[n]\setminus C^{*}$ we have for IID
standard normals $Z_{1},Z_{2},$ and $Z$

$\displaystyle\mathbb{P}[\mathcal{C}_{(i,j_{1})}\cap\mathcal{C}_{(i,j_{2})}]$
$\displaystyle=\mathbb{P}\left[\left\\{e(i,C^{*})<e(j_{1},C^{*}\setminus\\{i\\})\right\\}\bigcap\left\\{e(i,C^{*})<e(j_{2},C^{*}\setminus\\{i\\})\right\\}\right]$
$\displaystyle=\mathbb{P}\left[\left\\{N((\gamma n-1)\mu_{1},(\gamma
n-1)\tau^{2})<N((\gamma n-1)\mu_{2},(\gamma n-1)\tau^{2})\right\\}\right.$
$\displaystyle\quad\bigcap\left\\{N((\gamma n-1)\mu_{1},(\gamma
n-1)\tau^{2})<N((\gamma n-1)\mu_{2},(\gamma n-1)\tau^{2})\right\\}\Big{]}$
$\displaystyle=\mathbb{P}\left[\left\\{Z_{1}>Z+s\sqrt{2\log
n}(1+o(1))\right\\}\bigcap\left\\{Z_{2}>Z+s\sqrt{2\log
n}(1+o(1))\right\\}\right]$
$\displaystyle=\int_{\mathbb{R}}\Phi^{2}(z+s\sqrt{2\log n}(1+o(1)))\phi(z)dz$

For $i_{1}\neq i_{2}\in C^{*}$ and $j\in[n]\setminus C^{*}$ we have for IID
standard normals $Z_{1},Z_{2},Z_{3},Z_{4}$ and $Z,Z^{\prime}$

$\displaystyle\mathbb{P}[\mathcal{C}_{(i_{1},j)}\cap\mathcal{C}_{(i_{2},j)}]$
$\displaystyle=\mathbb{P}\left[\left\\{e(i_{1},C^{*})<e(j,C^{*}\setminus\\{i_{1}\\})\right\\}\bigcap\left\\{e(i_{2},C^{*})<e(j,C^{*}\setminus\\{i_{2}\\})\right\\}\right]$
$\displaystyle=\mathbb{P}\left[\left\\{N((\gamma n-2)\mu_{1},(\gamma
n-2)\tau^{2})+e_{i_{1},i_{2}}<N((\gamma n-2)\mu_{2},(\gamma
n-2)\tau^{2})+e_{j,i_{2}}\right\\}\right.$
$\displaystyle\quad\bigcap\left\\{N((\gamma n-2)\mu_{1},(\gamma
n-2)\tau^{2})+e_{i_{1},i_{2}}<N((\gamma n-2)\mu_{2},(\gamma
n-2)\tau^{2})+e_{j,i_{1}}\right\\}\Big{]}$
$\displaystyle=\mathbb{P}\left[\left\\{\tau\sqrt{\gamma n-2}Z+\tau
Z_{3}>(\gamma n-1)(\mu_{1}-\mu_{2})+\tau\sqrt{\gamma n-2}Z_{1}+\tau
Z^{\prime}\right\\}\right.$ $\displaystyle\quad\bigcap\left\\{\tau\sqrt{\gamma
n-2}Z+\tau Z_{4}>(\gamma n-1)(\mu_{1}-\mu_{2})+\tau\sqrt{\gamma n-2}Z_{2}+\tau
Z^{\prime}\right\\}\Big{]}$
$\displaystyle=\mathbb{P}\left[\left\\{\tau\sqrt{\gamma n-1}Z>(\gamma
n-1)(\mu_{1}-\mu_{2})+\tau\sqrt{\gamma n-1}Z_{1}\right\\}\right.$
$\displaystyle\quad\bigcap\left\\{\tau\sqrt{\gamma n-1}Z>(\gamma
n-1)(\mu_{1}-\mu_{2})+\tau\sqrt{\gamma n-1}Z_{2}\right\\}\Big{]}$
$\displaystyle=\mathbb{P}\left[\left\\{Z>Z_{1}+s\sqrt{2\log
n}(1+o(1))\right\\}\bigcap\left\\{Z>Z_{2}+s\sqrt{2\log
n}(1+o(1))\right\\}\right]$
$\displaystyle=\int_{\mathbb{R}}\Phi^{2}(z+s\sqrt{2\log n}(1+o(1)))\phi(z)dz$

So, whenever $\gamma\text{SNR}<\frac{3}{4}$ and with the notations above we
have the following.

$\displaystyle\frac{\mathbb{P}\left[\mathcal{C}_{(i_{1},j)}\cap\mathcal{C}_{(i_{2},j)}\right]}{n\mathbb{P}\left[\mathcal{C}_{ij}\right]^{2}}$
$\displaystyle\sim\frac{\mathbb{P}\left[\mathcal{C}_{(i,j_{1})}\cap\mathcal{C}_{(i,j_{2})}\right]}{n\mathbb{P}\left[\mathcal{C}_{ij}\right]^{2}}$
(103) $\displaystyle\sim\frac{\int_{\mathbb{R}}\Phi^{2}(z+s\sqrt{2\log
n}(1+o(1)))\phi(z)dz}{n\left(\frac{1}{s\sqrt{\log n}}\phi(s\sqrt{\log
n})\right)^{2}}$ (104) $\displaystyle\sim\frac{\int_{-s\sqrt{2\log
n}(1+o(1))}^{s\sqrt{2\log n}(1+o(1))}\Phi^{2}(z+s\sqrt{2\log
n}(1+o(1)))\phi(z)dz}{n\left(\frac{1}{s\sqrt{\log n}}\phi(s\sqrt{\log
n})\right)^{2}}$ (105) $\displaystyle\sim\frac{2\pi s^{2}\log
n}{n}\int_{0}^{2s\sqrt{2\log n}(1+o(1))}\Phi^{2}(z)\phi(z)e^{zs\sqrt{2\log
n}}dz$ (106) $\displaystyle\leqslant\frac{\sqrt{2\pi}e^{2}s^{2}\log
n}{n}\int_{0}^{2s\sqrt{2\log n}(1+o(1))}e^{-\frac{3z^{2}}{2}+zs\sqrt{2\log
n}}dz$ (107) $\displaystyle\leqslant\frac{C\log
n}{n}e^{\frac{4\gamma\text{SNR}\log n}{3}}\int_{0}^{2s\sqrt{2\log
n}(1+o(1))}e^{-\frac{3(z-\frac{s\sqrt{2\log n}}{3})^{2}}{2}}dz$ (108)
$\displaystyle\to 0$ (109)

It is also immediate that up to $\text{poly}(\log n)$ factors555$a_{n}\simeq
b_{n}$ if $a_{n}\leqslant\text{poly}(\log n)b_{n}$ and
$b_{n}\leqslant\text{poly}(\log n)$ we have

$\frac{2\pi s^{2}\log n}{n}\int_{0}^{2s\sqrt{2\log
n}(1+o(1))}\Phi^{2}(z)\phi(z)e^{zs\sqrt{2\log n}}dz\simeq
n^{\frac{4\gamma\text{SNR}}{3}-1}$

∎

###  9.4 Statistical possibility

In this section, we prove that as soon as the $\gamma\text{SNR}>1$, we have
that MLE can recover the planted community $\zeta^{*}$ exactly with
probability approaching one. We prove this result in two steps. On the
impossibility side, we already showed that below a weaker threshold, there
exists a bad pair of vertices, one in the planted community and another one
from the rest, that can be swapped while increasing the likelihood. Here we
show that the 89 gives the planted community, by showing that there is no
possibility to swap any set of $r$ vertices from the planted community and
increase the likelihood for any $r\in\\{1,\cdots,K=\gamma n\\}$ above the
threshold $\gamma\text{SNR}>1$.

####  9.4.1 The statement

######  Theorem 59 (Statistical possibility of exact recovery of the planted
community).

Under the Gaussian weighted planted dense subgraph model
PDSM$(n,\mu_{1},\mu_{2},\tau^{2})$ [81], MLE can exactly recover the community
labelling $\zeta^{*}$ as soon as $\gamma\text{SNR}>1$. More precisely,
$\mathbb{P}\left[M(\hat{\zeta}_{\text{MLE}},\zeta^{*})=1\right]\to 1$.

######  Notations 3.

With $\zeta^{*}=\\{\mathbf{1}_{\gamma
n},\mathbf{0}_{(1-\gamma)n}\\}\in\Theta_{n}^{\gamma}$ we have the true planted
community $C^{*}:=\\{1,\cdots,\gamma n\\}$, and the complement $[n]\setminus
C^{*}:=\\{\gamma n+1,\cdots,n\\}$. Further, let
$\hat{\zeta}\in\Theta_{n}^{\gamma}$ and denote the predicted community labels
with $\hat{C}=\\{i\in[n]:\hat{\zeta}(i)=1\\},$ and the complement
$[n]\setminus\hat{C}:=\\{i\in[n]:\hat{\zeta}(i)=0\\}$. We observe that MLE 89
fails to recover the true planted community labeling $\zeta^{*}$ if and only
if there exists $\hat{\zeta}\in\Theta_{n}^{\gamma}$ such that
$g_{A}(\hat{\zeta})>g_{A}(\zeta^{*})$. For subsets of vertices
$A,B\subseteq[n]$ with $A\cap B=\emptyset$ we define the following

$e(A,B)=\sum_{p\in A,q\in B}A_{pq}$ $e(A)=\sum_{p\in A,q\in A}A_{pq}$

####  9.4.2 The proof – union bound

######  Lemma 60.

$\exists$ $\hat{\zeta}\in\Theta_{n}^{\gamma}$ with
$g_{A}(\hat{\zeta})>g_{A}(\zeta^{*})\mathrel{\text{\scalebox{0.7}{$\implies$}}}$
$\exists S_{+}\subseteq C^{*},S_{-}\subseteq[n]\setminus C^{*}$ such that
$1\leqslant|S_{+}|=|S_{-}|\leqslant\gamma n$ and we have

$e(S_{-})+e(C^{*}\setminus S_{+},S_{-})>e(S_{+})+e(C^{*}\setminus
S_{+},S_{+})$ (110)

###### Proof.

For $\zeta\in\Theta_{n}^{\gamma}$ let $C_{\zeta}=\\{i\in[n]:\zeta_{i}=1\\}$.
We observe that
$g_{A}(\zeta)=\sum_{i,j}A_{ij}\zeta_{i}\zeta_{j}=\sum_{\zeta_{i}=\zeta_{j}=1}A_{ij}\zeta_{i}\zeta_{j}=e(C_{\zeta})$

$g_{A}(\zeta)>g_{A}(\zeta^{*})\iff e(C_{\zeta})>e(C^{*})$

Now given $\hat{\zeta}$ and $\zeta^{*}$ we define
$S_{+}:=C^{*}\setminus\hat{C},$ $S_{-}:=\hat{C}\cap[n]\setminus
C^{*}=\hat{C}\setminus C^{*}\implies|S_{+}|=|S_{-}|$, and observe that
$g_{A}(\zeta)>g_{A}(\zeta^{*})$ implies $|S_{+}|\geqslant 1$. Further,

$e(\hat{C})=e(\hat{C}\cap C^{*})+e(\hat{C}\setminus C^{*})+e(\hat{C}\cap
C^{*},\hat{C}\setminus C^{*})$
$e(C^{*})=e(C^{*}\cap\hat{C})+e(C^{*}\setminus\hat{C})+e(C^{*}\cap\hat{C},C^{*}\setminus\hat{C})$

Combining the above, we have the following equivalence.

$\displaystyle g_{A}(\hat{\zeta})>g_{A}(\zeta^{*})$ $\displaystyle\iff
e(\hat{C}\setminus C^{*})+e(\hat{C}\cap C^{*},\hat{C}\setminus
C^{*})>e(C^{*}\setminus\hat{C})+e(C^{*}\cap\hat{C},C^{*}\setminus\hat{C})$
$\displaystyle\iff e(S_{-})+e(C^{*}\setminus
S_{+},S_{-})>e(S_{+})+e(C^{*}\setminus S_{+},S_{+})$

∎

Now, to prove that MLE 89 can solve exact recovery 59 as soon as $\gamma$ SNR
$>1$ by proving that such events of the kind 110 occur with probability
approaching zero. We define the following events as the following.

$\begin{split}E:=\\{\exists S_{+}\subseteq C^{*},&S_{-}\subseteq[n]\setminus
C^{*}:1\leqslant|S_{+}|=|S_{-}|\leqslant\min(\gamma n,(1-\gamma)n),\\\
&e(S_{-})+e(C^{*}\setminus S_{+},S_{-})>e(S_{+})+e(C^{*}\setminus
S_{+},S_{+})\\}\end{split}$ $E_{l}=\\{\exists S_{+}\subseteq
C^{*},S_{-}\subseteq[n]\setminus
C^{*}:|S_{+}|=|S_{-}|=l,e(S_{-})+e(C^{*}\setminus
S_{+},S_{-})>e(S_{+})+e(C^{*}\setminus S_{+},S_{+})\\}$

######  Lemma 61.

Let $K=\gamma n$. Then

$\mathbb{P}\left[E\right]=\mathbb{P}\left[\bigcup_{l=1}^{\min(K,n-K)}E_{l}\right]\to
0$

###### Proof.

We prove this by observing the following for a fixed pair $(S_{+},S_{-})$ of
size $l$.

$\displaystyle\mathbb{P}[E]$ $\displaystyle\leqslant\sum_{1\leqslant
l\leqslant\min(K,n-K)}\mathbb{P}[E_{l}]$ (111)
$\displaystyle\leqslant\sum_{1\leqslant
l\leqslant\min(K,n-K)}\binom{K}{l}\binom{n-K}{l}\mathbb{P}\left[e(S_{-})+e(C^{*}\setminus
S_{+},S_{-})>e(S_{+})+e(C^{*}\setminus S_{+},S_{+})\right]\to 0$ (112)

We observe that $e(S_{-}),e(S_{+}),e(C^{*}\setminus S_{+},S_{-}),$ and
$e(C^{*}\setminus S_{+},S_{+})$ are jointly independent random variables with

$e(S_{+})\overset{d}{=}N\left(\binom{l}{2}\mu_{1},\binom{l}{2}\tau^{2}\right)$
$e(S_{-})\overset{d}{=}N\left(\binom{l}{2}\mu_{2},\binom{l}{2}\tau^{2}\right)$
$e(C^{*}\setminus
S_{+},S_{+})\overset{d}{=}N\left(l(K-l)\mu_{1},l(K-l)\tau^{2}\right)$
$e(C^{*}\setminus
S_{+},S_{-})\overset{d}{=}N\left(l(K-l)\mu_{2},l(K-l)\tau^{2}\right)$

Combining the above distributional identities we have the following
simplification.

$\displaystyle\mathbb{P}$ $\displaystyle\left[e(S_{-})+e(C^{*}\setminus
S_{+},S_{-})>e(S_{+})+e(C^{*}\setminus S_{+},S_{+})\right]$
$\displaystyle=\mathbb{P}\left[\tau\sqrt{2}\sqrt{\left(\binom{K}{2}-\binom{K-l}{2}\right)}N(0,1)>\left(\binom{K}{2}-\binom{K-l}{2}\right)(\mu_{1}-\mu_{2})\right]$
$\displaystyle=\mathbb{P}\left[N(0,1)>\sqrt{\left(\binom{K}{2}-\binom{K-l}{2}\right)}\left(\frac{\mu_{1}-\mu_{2}}{\tau\sqrt{2}}\right)\right]$
$\displaystyle\leqslant
e^{-\frac{2\text{SNR}\left(\binom{K}{2}-\binom{K-l}{2}\right)\log
n}{n}}=\frac{1}{n^{\frac{l(2K-1-l)\text{SNR}}{n}}}$

From the standard Gaussian tail bounds 52 we have the following for $l=1$ with
$\gamma\text{SNR}=1+2\delta$.

$\mathbb{P}\left[E_{1}\right]\leqslant
K(n-K)\frac{1}{n^{\frac{2(K-1)\text{SNR}}{n}}}\leqslant\gamma(1-\gamma)n^{2}n^{-2\gamma\text{SNR}(1+o(1))}=\frac{\gamma(1-\gamma)}{n^{4\delta+o(1)}}\to
0$

More generally, let $\epsilon=\frac{l}{n}$. Then we apply the bounds on the
binomial coefficients for $1\leqslant l\leqslant p$.

$\left(\frac{p}{l}\right)^{l}\leqslant\binom{p}{l}\leqslant\left(\frac{ep}{l}\right)^{l}$
(113)

We choose $\epsilon_{\delta}>0$ be such that
$\epsilon_{\delta}\text{SNR}=\delta\implies$ For
$\epsilon\leqslant\epsilon_{\delta}$ we have
$-2\delta+\frac{(l+1)\text{SNR}}{2n}\leqslant-\delta$

$\frac{\binom{K}{l}\binom{n-K}{l}}{n^{\frac{l(2K-1-l)\text{SNR}}{n}}}\leqslant\left(\frac{e^{2}\gamma(1-\gamma)}{l^{2}}\right)^{l}\frac{n^{2l}}{n^{2\gamma\text{SNR}l}}n^{\frac{l(l+1)\text{SNR}}{n}}\leqslant
n^{2l(-2\delta+\frac{(l+1)\text{SNR}}{2n})}\leqslant\frac{1}{n^{2l\delta}}$

For $\epsilon\geqslant\epsilon_{\delta}$ we use the simpler binomial identity
$\binom{p}{l}\leqslant 2^{p}$ and use the fact that $l\leqslant\min(K,n-K)$

$\frac{\binom{K}{l}\binom{n-K}{l}}{n^{\frac{l(2K-1-l)\text{SNR}}{n}}}\leqslant\frac{2^{n}}{n^{\delta(\gamma
n-1)}}\leqslant\frac{1}{n^{\delta\gamma n(1-o(1))}}$
$\displaystyle\sum_{1\leqslant
l\leqslant\min(K,n-K)}\frac{\binom{K}{l}\binom{n-K}{l}}{n^{\frac{l(2K-1-l)\text{SNR}}{n}}}\leqslant\sum_{\frac{1}{n}\leqslant\frac{l}{n}\leqslant\epsilon_{\delta}}\frac{1}{n^{2l\delta}}+\sum_{\epsilon_{\delta}\leqslant\frac{l}{n}\leqslant\min(\gamma,1-\gamma)}\frac{1}{n^{\delta\gamma
n(1-o(1))}}\to 0.$

∎

###  9.5 Semi-definite relaxation

We begin with the observation that we can write the MLE 90 in the form of an
SDP with rank one constraints.

####  9.5.1 The statement

######  Lemma 62.

The optimization problem corresponding to MLE 90 is equivalent to the
following optimization problem.

$\max_{Z,\zeta}\hskip 2.84544pt\langle
A,Z\rangle:Z=\zeta\zeta^{\top},Z_{ii}\leqslant 1,\hskip 2.84544pt\forall\hskip
2.84544pti\in[n],Z_{ij}\geqslant 0,\hskip 2.84544pt\forall\hskip
2.84544pti,j\in[n],\langle\mathbf{I},Z\rangle=\gamma
n,\langle\mathbf{J},Z\rangle=\gamma^{2}n^{2},$ (114)

###### Proof.

The objective function is the same for both 90 and 114. We also observe that
if $\zeta$ is a solution to 114, then $-\zeta$ is a solution too. It suffices
to prove that the constraint sets are equal up to a global sign flip. Let
$\zeta\in\Theta^{\gamma}_{n}$.

$Z_{ii}=\zeta_{i}^{2}\leqslant 1\forall\hskip 2.84544pti\in[n],$
$Z_{ij}=\zeta_{i}\zeta_{j}\geqslant 0\hskip 2.84544pt\forall\hskip
2.84544pti,j\in[n]$
$\langle\mathbf{I},Z\rangle=\sum_{i}\zeta_{i}^{2}=\sum_{i}\zeta_{i}=\gamma n$
$\langle\mathbf{J},Z\rangle=\left(\sum_{i}\zeta_{i}\right)^{2}=\gamma^{2}n^{2}$

This clearly implies that the constraint set of 90 is a subset of 114. On the
other hand

$\zeta_{i}^{2}\leqslant 1\forall\hskip
2.84544pti\in[n]\implies-1\leqslant\zeta_{i}\leqslant 1,$
$Z_{ij}=\zeta_{i}\zeta_{j}\geqslant 0\hskip 2.84544pt\forall\hskip
2.84544pti,j\in[n]\implies\hskip 2.84544pt\text{ all }\hskip
2.84544pt\zeta_{i}\hskip 2.84544pt\text{have the same signs}$

Combining the above, we have either $\zeta\in[0,1]^{n}$ or
$\zeta\in[-1,0]^{n}$.

$\langle\mathbf{I},Z\rangle=\sum_{i}\zeta_{i}^{2}=\gamma n$
$\langle\mathbf{J},Z\rangle=\left(\sum_{i}\zeta_{i}\right)^{2}=\gamma^{2}n^{2}\implies\sum_{i}\zeta_{i}=\pm\gamma
n$

Assuming $\zeta\in[0,1]^{n}$ we have
$\sum_{i}\zeta_{i}^{2}=\sum_{i}\zeta_{i}=\gamma n$. Therefore we have

$\sum_{i}\zeta_{i}(1-\zeta_{i})=0\implies\zeta_{i}(1-\zeta_{i})=0\forall
i\in[n]\implies\zeta\in\\{0,1\\}^{n}\cap\langle\zeta,\mathbf{1}_{n}\rangle=\gamma
n\equiv\zeta\in\Theta^{\gamma}_{n}.$

Similarly, assuming $\zeta\in[-1,0]^{n}$ we have
$\sum_{i}\zeta_{i}^{2}=-\sum_{i}\zeta_{i}=\gamma n$, and hence

$\sum_{i}\zeta_{i}(1+\zeta_{i})=0\implies\zeta_{i}(1+\zeta_{i})=0\forall
i\in[n]\implies-\zeta\in\\{0,1\\}^{n}\cap\langle-\zeta,\mathbf{1}_{n}\rangle=\gamma
n\equiv-\zeta\in\Theta^{\gamma}_{n}$

∎

In the above formulation 114 the matrix $Z=\zeta\zeta^{\top}$ is positive
semidefinite and rank-one. Removing the rank-one restriction leads to the
following convex relaxation of 114, which is a semidefinite program.

$\hat{Z}_{\mathrm{SDP}}=\underset{Z}{\arg\max}\langle A,Z\rangle:Z\succeq
0,Z_{ii}\leqslant 1,\hskip 2.84544pt\forall\hskip
2.84544pti\in[n],Z_{ij}\geqslant 0,\hskip 2.84544pt\forall\hskip
2.84544pti,j\in[n],\langle\mathbf{I},Z\rangle=\gamma
n,\langle\mathbf{J},Z\rangle=\gamma^{2}n^{2}.$ (115)

Let $Z^{*}=\zeta^{*}\zeta^{*^{\top}}$ correspond to the true cluster and
define
$\mathcal{Z}_{n}=\left\\{\zeta\zeta^{\top}:\zeta\in\\{0,1\\}^{n},\langle\zeta,\mathbf{1}\rangle=\gamma
n\right\\}$. The threshold for the exact recovery of the densely weighted
community for the SDP 115 is given as follows.

$Z^{*}=\begin{bmatrix}\begin{array}[]{c|c}\mathbf{1}_{\gamma n\times\gamma
n}&\mathbf{0}_{\gamma n\times n}\\\\[4.30554pt] \hline\cr\\\\[-8.61108pt]
\mathbf{0}_{n\times\gamma
n}&\mathbf{0}_{(1-\gamma)n\times(1-\gamma)n}\end{array}\end{bmatrix}.$

######  Theorem 63 (Semi-definite relaxation achieves exact recovery of the
planted community).

Under the Gaussian weighted planted dense subgraph model 81 with parameter
$\gamma\in(0,1)$,

$\text{if}\hskip 2.84544pt\gamma\text{SNR}\hskip 2.84544pt>1,\hskip
2.84544pt\text{then}\hskip
2.84544pt\min_{Z\in\mathcal{Z}_{n}}\mathbb{P}\left[\hat{Z}_{\mathrm{SDP}}=Z^{*}\right]\to
1\hskip 2.84544pt\text{as}\hskip 2.84544ptn\rightarrow\infty.$

####  9.5.2 A deterministic condition

Now, we prove this theorem by first establishing a deterministic condition for
a unique solution.

######  Lemma 64.

Suppose $\exists$ $D^{*}=\operatorname{diag}\left\\{d_{i}^{*}\right\\}$ with
$\\{d^{*}_{i}\\}_{i=1}^{n}\in\mathbb{R}_{\geqslant 0}^{n}$,
$B^{*}\in\mathbb{R}^{n\times n}_{\geqslant 0},$ and
$\lambda^{*},\eta^{*}\in\mathbb{R}$ such that

$S^{*}\triangleq D^{*}-B^{*}-A+\eta^{*}\mathbf{I}+\lambda^{*}\mathbf{J}\hskip
2.84544pt\text{satisfies}\hskip 2.84544ptS^{*}\succeq
0,\lambda_{2}\left(S^{*}\right)>0,\hskip 2.84544pt\text{and}\hskip
2.84544ptS^{*}\zeta^{*}=0,$ (116) $\hskip
2.84544ptd_{i}^{*}\left(Z_{ii}^{*}-1\right)=0\quad\forall i,\quad
B_{ij}^{*}Z_{ij}^{*}=0\quad\forall i,j,$ (117)

Then SDP recovers the true solution. More precisely,
$\widehat{Z}_{\mathrm{SDP}}=Z^{*}$ is the unique solution to 115.

###### Proof.

For auxiliary Lagrangian multipliers denoted by $S\succeq
0,D=\operatorname{diag}\left\\{d_{i}\right\\}$ with
$\\{d_{i}\\}_{i=1}^{n}\in\mathbb{R}_{\geqslant 0}^{n}$, $B\geqslant 0$, and
$\lambda,\eta\in\mathbb{R}$, we define the Lagrangian dual function of the
original semi-definite program 115 as

$\displaystyle L(Z,S,D,B,\lambda,\eta)$ $\displaystyle:=\langle
A,Z\rangle+\langle S,Z\rangle+\langle D,\mathbf{I}-Z\rangle+\langle
B,Z\rangle+\eta(\gamma
n-\langle\mathbf{I},Z\rangle)+\lambda\left(\gamma^{2}n^{2}-\langle\mathbf{J},Z\rangle\right)$
(118) $\displaystyle=\langle
A+S-D+B-\eta\mathbf{I}-\lambda\mathbf{J},Z\rangle+\langle
D,\mathbf{I}\rangle+\eta\gamma n+\lambda\gamma^{2}n^{2}$ (119)

Then, for any $Z$ satisfying the constraints in 115, we have the following
weak duality inequality.

$\displaystyle\langle A,Z\rangle$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leqslant}}L\left(Z,S^{*},D^{*},B^{*},\lambda^{*},\eta^{*}\right)\stackrel{{\scriptstyle(b)}}{{=}}\left\langle
D^{*},I\right\rangle+\eta^{*}\gamma
n+\lambda^{*}\gamma^{2}n^{2}\stackrel{{\scriptstyle(c)}}{{=}}\left\langle
D^{*},Z^{*}\right\rangle+\eta^{*}\gamma n+\lambda^{*}\gamma^{2}n^{2}$ (120)
$\displaystyle=\left\langle
A+B^{*}+S^{*}-\eta^{*}\mathbf{I}-\lambda^{*}\mathbf{J},Z^{*}\right\rangle+\eta^{*}\gamma
n+\lambda^{*}\gamma^{2}n^{2}\stackrel{{\scriptstyle(c)}}{{=}}\left\langle
A,Z^{*}\right\rangle$ (121)

where (a) follows from 116 and 115 implying $\left\langle
S^{*},Z\right\rangle\geqslant 0,\left\langle
D^{*},\mathbf{I}-Z\right\rangle\geqslant 0$, and $\left\langle
B^{*},Z\right\rangle\geqslant 0$; (b) holds directly from 116; (c) holds
because $d_{i}^{*}\left(Z_{ii}^{*}-1\right)=0,\forall i$; (d) holds because
$B_{ij}^{*}Z_{ij}^{*}=0,\hskip 2.84544pt\forall\hskip 2.84544pti,j\in[n]$ from
117 implying $\langle B^{*},Z^{*}\rangle=0$ and it follows from 116 that
$\left\langle S^{*},Z^{*}\right\rangle=\zeta^{*^{\top}}S^{*}\zeta^{*}=0$.
Therefore, $Z^{*}$ is an optimal solution to 115.

We now establish its uniqueness. To this end, suppose $Z_{2}$ be another
optimal solution to 115. Then we have,

$\displaystyle\left\langle S^{*},Z_{2}\right\rangle$
$\displaystyle=\left\langle
D^{*}-B^{*}-A+\eta^{*}\mathbf{I}+\lambda^{*}\mathbf{J},Z_{2}\right\rangle\stackrel{{\scriptstyle(a)}}{{=}}\left\langle
D^{*}-B^{*},Z_{2}\right\rangle+\langle-A+\eta^{*}\mathbf{I}+\lambda^{*}\mathbf{J},Z^{*}\rangle$
(122) $\displaystyle\stackrel{{\scriptstyle(b)}}{{\leqslant}}\left\langle
D^{*}-B^{*},Z^{*}\right\rangle+\langle-A+\eta^{*}\mathbf{I}+\lambda^{*}\mathbf{J},Z^{*}\rangle=\left\langle
S^{*},Z^{*}\right\rangle=0$ (123)

where $(a)$ holds because $\langle\mathbf{I},Z_{2}\rangle=\gamma
n=\langle\mathbf{I},Z^{*}\rangle$,
$\langle\mathbf{J},Z_{2}\rangle=\gamma^{2}n^{2}=\langle\mathbf{J},Z^{*}\rangle$
and $\langle A,Z_{2}\rangle=\left\langle A,Z^{*}\right\rangle$ ;(b) holds
because from 115 and 117 we have $B^{*},Z_{2}\geqslant 0$ and therefore
$\langle-B^{*},Z_{2}\rangle\leqslant 0=\langle B^{*},Z^{*}\rangle$.
Furthermore, we have $\left\langle
D^{*},Z_{2}\right\rangle=\sum_{i:\zeta_{i}=1}D^{*}_{ii}Z_{2_{ii}}\leqslant\sum_{i:\zeta_{i}=1}d_{i}^{*}=\left\langle
D^{*},Z^{*}\right\rangle$ since $d_{i}^{*}\geqslant 0$ and
$Z_{2_{ii}}\leqslant 1$ for all $i\in[n]$. Since $Z_{2}\succeq 0$ and
$S^{*}\succeq 0$ we also have $\langle S^{*},Z_{2}\rangle\geqslant 0$.
Combining with the above we have that $\langle S^{*},Z_{2}\rangle=0$.

We are now in a position to apply lemma 47 with $S^{*}\succeq 0$,
$\lambda_{2}\left(S^{*}\right)>0,$ and $\langle S^{*},Z_{2}\rangle=\langle
S^{*},Z^{*}\rangle=0$. By lemma 47 $Z_{2}$ needs to be a multiple of
$Z^{*}=\zeta^{*}\zeta^{*^{\top}}$. Finally, we have $Z_{2}=Z^{*}$ since
$\operatorname{Tr}(Z_{2})=\operatorname{Tr}\left(Z^{*}\right)=\gamma n$. ∎

####  9.5.3 A high probability event and the proof

We are now in a position to provide a proof of theorem 63. Let
$C^{*}:=\\{i\in[n]:\zeta_{i}=1\\}$. We shall choose $\lambda^{*}$ later. For
now, we choose
$\eta^{*}=2\|A-\mathbb{E}[A]\|,D^{*}=\operatorname{diag}\left\\{d_{i}^{*}\right\\}$
with
$d^{*}_{i}=\langle(A-\eta^{*}\mathbf{I}-\lambda^{*}\mathbf{J})_{i},\zeta^{*}\rangle\mathbf{1}_{i\in
C^{*}}$. More precisely,

$d_{i}^{*}=\begin{cases}\sum_{j\in C^{*}}A_{ij}-\eta^{*}-\lambda^{*}\gamma
n&\text{if }i\in C^{*}\\\ 0&\text{otherwise}\end{cases}$ (124)

Define $b_{i}^{*}\gamma n\triangleq\lambda^{*}\gamma n-\sum_{j\in
C^{*}}A_{ij}=\langle(\lambda^{*}\mathbf{J}-A)_{i},\zeta^{*}\rangle$ for
$i\notin C^{*}$. We define $B^{*}\in\mathbb{R}^{n\times n}$ as the following.

$B_{ij}^{*}=b_{i}^{*}\mathbf{1}_{\left\\{i\notin C^{*},j\in
C^{*}\right\\}}+b_{j}^{*}\mathbf{1}_{\left\\{i\in C^{*},j\notin
C^{*}\right\\}}$ (125)

It remains to show that $\left(S^{*},D^{*},B^{*}\right)$ satisfies the
conditions in Lemma 64 with probability approaching one.

By definition of $D^{*}$ and $B^{*}$, we have
$d_{i}^{*}\left(Z_{ii}^{*}-1\right)=0$ $\forall$ $i\in[n]$ and
$B_{ij}^{*}Z_{ij}^{*}=0$ $\forall$ $i,j\in[n]$. Moreover, $\forall$ $i\in
C^{*}$,

$d_{i}^{*}\zeta_{i}^{*}=d_{i}^{*}=\sum_{j}A_{ij}\zeta_{j}^{*}-\eta^{*}-\lambda^{*}\gamma
n\stackrel{{\scriptstyle(a)}}{{=}}\sum_{j}A_{ij}\zeta_{j}^{*}+\sum_{j}B_{ij}^{*}\zeta_{j}^{*}-\eta^{*}-\lambda^{*}\gamma
n=\langle(A+B^{*}-\eta^{*}\mathbf{I}-\lambda^{*}\mathbf{J})_{i},\zeta^{*}\rangle$
(126)

where equality $(a)$ holds because $B_{ij}^{*}=0$ if $(i,j)\in C^{*}\times
C^{*}$. Furthermore, $\forall$ $i\notin C^{*}$,

$\sum_{j}A_{ij}\zeta_{j}^{*}+\sum_{j}B_{ij}^{*}\zeta_{j}^{*}-\lambda^{*}\gamma
n=\sum_{j\in C^{*}}A_{ij}+\gamma nb_{i}^{*}-\lambda^{*}\gamma
n=\langle(A+B^{*}-\eta^{*}\mathbf{I}-\lambda^{*}\mathbf{J})_{i},\zeta^{*}\rangle\stackrel{{\scriptstyle(a)}}{{=}}0=d^{*}_{i}\zeta^{*}_{i}$
(127)

where the final equality (a) follows from our choice of $b_{i}^{*}$. Combining
the two above we have,

$D^{*}\zeta^{*}=A\zeta^{*}+B^{*}\zeta^{*}-\eta^{*}\zeta^{*}-\lambda^{*}\gamma
n\mathbf{1}=(A+B^{*}-\eta^{*}\mathbf{I}-\lambda^{*}\mathbf{J})\zeta^{*}$

As a consequence $S^{*}$ satisfies the following condition.

$S^{*}\zeta^{*}=D^{*}\zeta^{*}-(A+B^{*}-\eta^{*}\mathbf{I}-\lambda^{*}\mathbf{J})\zeta^{*}=0.$

We next prove that $D^{*}\geqslant 0,B^{*}\geqslant 0$ with probability
approaching one. It follows again from 69 standard bounds on norms of Gaussian
random matrices that $\eta^{*}=2\|A-\mathbb{E}[A]\|\leqslant 6\tau\sqrt{n}$
with probability at least $1-2e^{-cn}$ for some absolute positive constant
$c$. Furthermore, let $X_{i}\triangleq\sum_{j\in C^{*}}A_{ij}=\langle
A_{i},\zeta^{*}\rangle$. Then we have the distributional identity.

$X_{i}\sim\begin{cases}N(\gamma n\mu_{1},\gamma n\tau^{2})&\text{if }i\in
C^{*}\\\ N(\gamma n\mu_{2},\gamma n\tau^{2})&i\notin C^{*}\end{cases}$

We will show using union bound that with probability approaching one

$d^{*}_{i}=X_{i}-6\tau\sqrt{n}-\lambda^{*}\gamma n\geqslant 0\hskip
2.84544pt\forall\hskip 2.84544pti\in C^{*}$ (128) $b_{i}^{*}\gamma
n=\lambda^{*}\gamma n-X_{i}\geqslant 0\hskip 2.84544pt\forall\hskip
2.84544pti\notin C^{*}$ (129)

We prove that $\mathbb{P}\left[\cap_{i\in C^{*}}\\{d^{*}_{i}\geqslant
0\\}\right]\to 1\iff\mathbb{P}\left[\cup_{i\in
C^{*}}\\{d^{*}_{i}<0\\}\right]\to 0$ by showing the following with
$\lambda^{*}=\frac{\mu_{1}+\mu_{2}}{2}$.

$\displaystyle\gamma n\mathbb{P}\left[d^{*}_{i}<0\right]$
$\displaystyle=\gamma n\mathbb{P}\left[\gamma
n(\mu_{1}-\lambda^{*})-\tau\sqrt{\gamma n}N(0,1)<6\tau\sqrt{n}\right]$
$\displaystyle=\gamma n\mathbb{P}\left[N(0,1)>\sqrt{\gamma
n}\frac{(\mu_{1}-\mu_{2})}{2\tau}-\frac{6}{\sqrt{\gamma}}\right]$
$\displaystyle\leqslant\gamma ne^{-\gamma\text{SNR}(1+o(1))\log
n}=\frac{\gamma}{n^{\gamma\text{SNR}-1+o(1)}}\to 0$

Similarly, we prove that $\mathbb{P}\left[\cap_{i\notin
C^{*}}\\{b^{*}_{i}\geqslant 0\\}\right]\to 1\iff\mathbb{P}\left[\cup_{i\notin
C^{*}}\\{b^{*}_{i}<0\\}\right]\to 0$ by showing the following.

$\displaystyle(1-\gamma)n\mathbb{P}\left[b^{*}_{i}\leqslant 0\right]$
$\displaystyle=(1-\gamma)n\mathbb{P}\left[\tau\sqrt{\gamma n}N(0,1)>\gamma
n(\lambda^{*}-\mu_{2})\right]$
$\displaystyle=(1-\gamma)n\mathbb{P}\left[N(0,1)>\sqrt{\gamma
n}\frac{(\mu_{1}-\mu_{2})}{2\tau}\right]$
$\displaystyle\leqslant(1-\gamma)ne^{-\gamma\text{SNR}\log
n}=\frac{(1-\gamma)}{n^{\gamma\text{SNR}-1}}\to 0$

Finally, it remains to prove that $S^{*}\succeq 0$ with
$\lambda_{2}\left(S^{*}\right)>0$ with probability approaching one. More
precisely,

$\mathbb{P}\left[\inf_{x\perp\zeta^{*},\|x\|=1}\langle
x,S^{*}x\rangle>0\right]\to 1$

Note that we have the following decomposition of the expected adjacency matrix
$\mathbb{E}\left[A\right]$.

$\mathbb{E}[A]=(\mu_{1}-\mu_{2})Z^{*}-\mu_{1}\left[\begin{array}[]{rr}\mathbf{I}_{\gamma
n\times\gamma n}&\mathbf{0}\\\
\mathbf{0}&\mathbf{0}\end{array}\right]-\mu_{2}\left[\begin{array}[]{cc}\mathbf{0}&\mathbf{0}\\\
\mathbf{0}&\mathbf{I}_{(1-\gamma)n\times(1-\gamma)n}\end{array}\right]+\mu_{2}\mathbf{J}.$

It follows that for any $x\perp\zeta^{*}$ and $\|x\|=1$, we have $\langle
x,Z^{*}x\rangle=(\langle x,\zeta^{*}\rangle)^{2}=0$ and

$\displaystyle\langle x,S^{*}x\rangle$ $\displaystyle=\langle
x,D^{*}x\rangle-\langle
x,B^{*}x\rangle+\left(\lambda^{*}-\mu_{2}\right)\langle
x,\mathbf{J}x\rangle+\mu_{1}\sum_{i\in C^{*}}x_{i}^{2}+\mu_{2}\sum_{i\notin
C^{*}}x_{i}^{2}+\eta^{*}-\langle x,(A-\mathbb{E}[A])x\rangle$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\sum_{i\in
C^{*}}d_{i}^{*}x_{i}^{2}+\left(\lambda^{*}-\mu_{2}\right)\langle
x,\mathbf{J}x\rangle+\mu_{1}\sum_{i\in C^{*}}x_{i}^{2}+\mu_{2}\sum_{i\notin
C^{*}}x_{i}^{2}+\eta^{*}-\langle x,(A-\mathbb{E}[A])x\rangle$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\geqslant}}\left(\min_{i\in
C^{*}}d_{i}^{*}\right)\sum_{i\in
C^{*}}x_{i}^{2}+\frac{\left(\mu_{1}-\mu_{2}\right)}{2}(\langle
x,\mathbf{1}\rangle)^{2}+\mu_{1}\sum_{i\in
C^{*}}x_{i}^{2}+\mu_{2}\sum_{i\notin
C^{*}}x_{i}^{2}+\eta^{*}-\|A-\mathbb{E}[A]\|$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\geqslant}}\left(\min_{i\in
C^{*}}d_{i}^{*}\right)\sum_{i\in C^{*}}x_{i}^{2}+\mu_{1}\sum_{i\in
C^{*}}x_{i}^{2}+\mu_{2}\sum_{i\notin C^{*}}x_{i}^{2}+\|A-\mathbb{E}[A]\|$
$\displaystyle\stackrel{{\scriptstyle(d)}}{{\geqslant}}\|A-\mathbb{E}[A]\|+(\mu_{1}-\mu_{2})\sum_{i\in
C^{*}}x_{i}^{2}+\mu_{2}\quad\text{with probability approaching one}$
$\displaystyle\stackrel{{\scriptstyle(e)}}{{\geqslant}}\|A-\mathbb{E}[A]\|+\mu_{2}\stackrel{{\scriptstyle(f)}}{{>}}0\quad\text{with
probability approaching one}$

where (a) holds because $B_{ij}^{*}=0$ for all $(i,j)\in C^{*}\times C^{*}$
and $(i,j)\in[n]\setminus C^{*}\times[n]\setminus C^{*}$

$\displaystyle\langle x,B^{*}x\rangle$ $\displaystyle=\sum_{i\notin
C^{*}}\sum_{j\in C^{*}}x_{i}x_{j}B_{ij}^{*}+\sum_{i\in C^{*}}\sum_{j\notin
C^{*}}x_{i}x_{j}B_{ij}^{*}$ (130) $\displaystyle=2\sum_{i\notin
C^{*}}\sum_{j\in C^{*}}x_{i}x_{j}B_{ij}^{*}$ (131)
$\displaystyle=2\sum_{i\notin C^{*}}x_{i}b_{i}^{*}\sum_{j\in C^{*}}x_{j}$
(132) $\displaystyle=2\langle x,\zeta^{*}\rangle\sum_{i\notin
C^{*}}x_{i}b_{i}^{*}$ (133) $\displaystyle=0$ (134)

(b) holds because $\lambda^{*}=\frac{\mu_{1}+\mu_{2}}{2}$ and
$\|A-\mathbb{E}[A]\|\geqslant\langle x,A-\mathbb{E}[A]x\rangle$. Further,
$(c)$ holds because $\eta^{*}=2\|A-\mathbb{E}[A]\|$ and
$\mu_{1}\geqslant\mu_{2}$. (d) holds because $\min_{i\in
C^{*}}d_{i}^{*}\geqslant 0$ with probability approaching one. Finally, again
from standard bounds on norms on Gaussian random matrices, for some absolute
positive constant $c>0$

$\mathbb{P}\left[\|A-\mathbb{E}[A]\|\geqslant\tau c\sqrt{n}\right]\to 1$ (135)

This along with $\tau c\sqrt{n}\geqslant|\mu_{2}|=|\alpha|\sqrt{\frac{\log
n}{n}}$ implies $(f)$ holds with probability approaching one. Hence, the
result.