\section{Parametric Contrastive Learning}

\begin{figure*}[t]
		\centering
			\subfloat[Parametric contrastive learning (PaCo).]{
			\includegraphics[width=.616\textwidth]{Figs/PaCo.pdf}%
		}
	\vspace{.1in}
	\subfloat[Curve for $\mathcal{L}_{extra}$.]{
			\includegraphics[width=.32\textwidth]{Figs/psum.pdf}%
		}
		\caption{\textbf{Framework of Parametric Contrastive Learning (PaCo) and $L_{extra}$ curve.} (a) shows the detail of PaCo. We introduce a set of parametric class-wise learnable centers for rebalancing in contrastive learning. More analysis is in Section \ref{Sec:PaCo} for PaCo. (b) plots the curve of $L_{extra}$ instantiated with full ImageNet. More analysis on balanced data is in Section \ref{sec:PaCo_balance}.}
		\label{fig:paco_psum}

\end{figure*}

\subsection{Supervised Contrastive Learning}
\label{Sec:supcon}

Khosla~\cite{DBLP:conf/nips/KhoslaTWSTIMLK20} extended the self-supervised contrastive loss with label information into supervised contrastive loss. Here we present it in the framework of MoCo \cite{DBLP:conf/cvpr/He0WXG20, DBLP:journals/corr/abs-2003-04297} as
\begin{equation}
\mathcal{L}_{i} \!=\! -\sum_{ z_{+} \in P(i)} \log \frac{ \exp({z_{+} \cdot T(x_{i})}) }{\sum_{z_{k} \in A(i)} \exp({z_{k} \cdot T(x_{i})})}. \label{eq:supcon} \\
\end{equation}
MoCo framework \cite{DBLP:conf/cvpr/He0WXG20, DBLP:journals/corr/abs-2003-04297} consists of two networks with the same structure, {\it i.e.}, { \it query network} and {\it key network}. The key network is driven by a momentum update with the query network in training. For each network, it usually contains one encoder CNN and one two-layer MLP transform.

During training, for one two-viewed image batch $B=(B_{v1}, B_{v2})$ and label $y$, $B_{v1}$ and $B_{v2}$ are fed into the {query network} and {key network} respectively and we denote their outputs as $Z_{v1}$ and $Z_{v2}$.
Especially, $Z_{v2}$ is used to update the momentum {\it queue}.

In Eq.~\eqref{eq:supcon}, $x_{i}$ is the representation for image $X_{i}$ in $B_{v1}$ obtained by the encoder of {query network}. The transform $T(\cdot)$ also belongs to the {query network}. We write
\begin{align*}
A(i) ={}& \{z_{k} \in queue \cup Z_{v1} \cup Z_{v2}\} \backslash \{ z_{k} \in Z_{v1}: k=i\}, \\
P(i) ={}& \{z_{k} \in A(i): y_{k} = y_{i}\}.
\end{align*}

In implementation, the loss is usually scaled by $\cfrac{1}{|P(i)|}$ and a temperature $\tau$ is applied like in Eq.~\eqref{eq:infonce}.
Different from self-supervised contrastive loss, which treats query and key as a positive pair if they are the data-augmented version of the same image, supervised contrastive loss treats them as one positive pair if they belong to the same class.

\subsection{Theoretical Motivation}
{\bf Analysis of Supervised Contrastive Learning.}
Khosla~\cite{DBLP:conf/nips/KhoslaTWSTIMLK20} introduced supervised contrastive learning to encourage more compact representation. We observe that it is not directly applicable to long-tailed recognition.
As shown in Table~\ref{tab:motivation}, the performance significantly decreases compared with traditional supervised cross-entropy.
From an optimization point of view, supervised contrastive loss concentrates more on high-frequency classes than low-frequency ones, which is unfriendly for imbalanced learning.

\begin{table}[tb!]
	\small
	\centering
	\caption{\textbf{Supervised contrastive learning is more sensitive to data imbalance.} Top-1 accuracy (\%) on ImageNet-LT with ResNet-50 is reported. Implementation details are in supplementary file. ``\dag" represents model is trained with PaCo loss without center learning rebalance.}
	\vspace{0pt}
	{
		\begin{tabular}{lcccc}
			\toprule
			Method &Many &Medium &Few &All \\
			\midrule
			Cross-Entropy &67.5 &42.6 &13.7 &48.4\\
			SupCon        &53.4 &2.9 &0 &22.0\\
			PaCo (ours) \dag    &69.6 &45.8 &16.0 &51.0\\
			\bottomrule
		\end{tabular}
	}
	\label{tab:motivation}
\end{table}

\begin{theorem}
	\label{thm:01_supcon}
	\normalfont{(Optimal value for supervised contrastive learning).}
	When supervised contrastive loss converges, the optimal value for the probability that two samples are a true positive pair with label $y$ is $\cfrac{1}{K_{y}}$, where, $q(y)$ is the frequency of class $y$ over the whole dataset, {\it queue} is the momentum  {\it queue} in MoCo \cite{DBLP:conf/cvpr/He0WXG20, DBLP:journals/corr/abs-2003-04297} and $K_{y} \approx \mathtt{length}(queue) \cdot q(y)$.
	\textit{Proof~~} See supplementary material.
\end{theorem}

\vspace{+0.1in}
\noindent {\bf Interpretation.} As indicated by Remark \ref{thm:01_supcon}, high-frequency classes have a higher lower bound of loss value and contribute much more importance than low-frequency classes in training. Thus the training process can be dominated by high-frequency classes. To handle this issue, we introduce a set of parametric class-wise learnable centers for rebalancing in contrastive learning.

\subsection{Rebalance in Contrastive Learning}
\label{Sec:PaCo}
As described in Fig.~\ref{fig:paco_psum} (a), we introduce a set of parametric class-wise learnable centers $\mathbf{C} =\{c_{1}, c_{2},..., c_{n} \}$ into the original supervised contrastive learning, and called this new form {\bf Parametric Contrastive Learning (PaCo)}. Correspondingly, the loss function is changed to
\begin{equation}
\mathcal{L}_{i} \!=\! \sum_{ z_{+} \in P(i) \cup \{c_{y}\} } \!-w(z_{+}) \log \frac{ \exp({z_{+} \cdot T(x_{i})}) }{\sum_{z_{k} \in A(i) \cup \mathbf{C}} \exp({z_{k} \cdot T(x_{i})})},\label{eq:PaCo}
\end{equation}
\text{where}
\iffalse
\begin{gather*}
w(x_{+})\!=\!\left\{
\begin{aligned}
\alpha, \!\quad\! z_{+} \!\in\! P(i) \\
1.0, \!\quad\! z_{+} \!\in\! \{c_{y} \}
\end{aligned}
\right.,
\!\quad\!
T(x_{i})\!=\!\left\{
\begin{aligned}
\mathcal{G}(x_{i}), \!\quad\! z_{+} \!\in\! P(i) \\
\mathcal{F}(x_{i}), \!\quad\! z_{+} \!\in\! \{c_{y} \}
\end{aligned}
\right.
\end{gather*}
\fi
\begin{equation}
w(z_{+})\!=\!\left\{
\begin{array}{lr}
\alpha, \!\quad\! z_{+} \!\in\! P(i) &  \\
1.0, \!\quad\! z_{+} \!\in\! \{c_{y} \} & \\
\end{array}
\right.
\nonumber
\end{equation}
and
\begin{equation}
z \cdot T(x_{i})\!=\!\left\{
\begin{array}{lr}
z \cdot \mathcal{G}(x_{i}), \!\quad\! z \!\in\! A(i) &  \\
z \cdot \mathcal{F}(x_{i}), \!\quad\! z \!\in\! \mathbf{C}. & \\
\end{array}
\right.
\nonumber
\end{equation}

Following Chen~\cite{DBLP:journals/corr/abs-2003-04297}, the transform $\mathcal{G}(\cdot)$ is a two-layer MLP while $\mathcal{F}(\cdot)$ is the identity mapping, {\textit i.e.}, $\mathcal{F}(x)=x$. $\alpha$ is one hyper-parameter in (0,1). $P(i)$ and $A(i)$ are the same with supervised contrastive learning in Eq.~\eqref{eq:supcon}. In implementation, the loss is scaled by $\cfrac{1}{\sum_{ z_{+} \in P(i) \cup \{ c_{y} \} } w(z_{+})}$ and a temperature $\tau$ is applied like in Eq.~\eqref{eq:supcon}.

\begin{theorem}
	\label{thm:02_pcl}
	\normalfont{(Optimal value for parametric contrastive learning)~~}
	When parametric contrastive loss converges, the optimal value for the probability that two samples are a true positive pair with label $y$ is $\cfrac{\alpha}{1+\alpha \cdot K_{y}}$ and the optimal value for the probability that a sample is closest to its corresponding center $c_{y}$ among $\mathbf{C}$ is $\cfrac{1}{1+\alpha \cdot K_{y}}$, where $q(y)$ is the frequency of class $y$ over the whole dataset, {\it queue} is the momentum  {queue} in MoCo \cite{DBLP:conf/cvpr/He0WXG20, DBLP:journals/corr/abs-2003-04297} and $K_{y} \approx \mathtt{length}(queue) \cdot q(y)$.
	\textit{Proof~~} See the Supplementary Material.
\end{theorem}

\vspace{+0.1in}
\noindent {\bf Interpretation.} Suppose the most frequent class $y_{h}$ has $K_{y_{h}} \approx q(y_{h}) \cdot \mathtt{length}(queue)$ and the least frequent class $y_{t}$ has $K_{y_{t}} \approx q(y_{t}) \cdot \mathtt{length}(queue)$. As indicated by Remarks \ref{thm:02_pcl} and \ref{thm:01_supcon}, the optimal value for the probability that two samples are a true positive pair varying from the most frequent class to the least one is rebalanced from $\cfrac{1}{K_{y_{h}}}$ $\longrightarrow$ $\cfrac{1}{K_{y_{t}}}$ to $\cfrac{1}{\frac{1}{\alpha} + K_{y_{h}}}$ $\longrightarrow$ $\cfrac{1}{\frac{1}{\alpha} + K_{y_{t}}}$. The smaller $\alpha$, the more uniform the optimal value from the most frequent class to the least one is, friendly to low- frequency classes learning.

However, when $\alpha$ decreases, the intensity of contrast among samples will be weaker, the intensity of contrast between samples and centers will be stronger. The whole loss becomes closer to supervised cross-entropy. To make good use of contrastive learning and rebalance at the same time, we observe that $\alpha$=0.05 is a reasonable choice.

\subsection{PaCo under balanced setting}
\label{sec:PaCo_balance}
For balanced datasets, all classes have the same frequency, {\it i.e.}, $q^{*}$=$q(y_{i})$=$q(y_{j})$ and $K^{*}$=$K_{y_{i}}$=$K_{y_{j}}$ for any class $y_{i}$ and class $y_{j}$. In this case, PaCo reduces to an improved version of multi-task with weighted sum of supervised cross-entropy loss and supervised contrastive loss. The connection between PaCo and multi-task is
\begin{equation*}
ExpSum = \sum_{c_{k} \in \mathbf{C}} \exp(c_{k} \!\cdot\! \mathcal{F}(x_{i})) + \sum_{z_{k} \in A(i)} \exp(z_{k} \cdot \mathcal{G}(x_{i})).
\end{equation*}

We also write the PaCo loss as
\begin{align*}
\mathcal{L}_{i}
={}& \sum_{ z_{+} \in P(i) \cup \{c_{y}\} } \!-w(z_{+}) \log \frac{ \exp({z_{+} \cdot T(x_{i})}) }{\sum_{z_{k} \in A(i) \cup \mathbf{C}} \exp({z_{k} \cdot T(x_{i})})} \\
={}& -\log \frac{\exp(c_{y} \cdot \mathcal{F}(x_{i}) )}{ExpSum} - \alpha\sum_{z_{+} \in P(i) }\log \frac{\exp(z_{+} \cdot \mathcal{G}(x_{i}) )}{ExpSum}\\
={}& \mathcal{L}_{sup} \!+\! \alpha  \mathcal{L}_{supcon} \!-\! \left( \log P_{sup} \!+\! \alpha K^{*}  \log P_{supcon} \right)  \\
={}& \mathcal{L}_{sup} \!+\! \alpha \mathcal{L}_{supcon} \!-\! \left( \log P_{sup} \!+\! \alpha K^{*}  \log (1-P_{sup}) \right), \\
\notag
\end{align*}
\begin{equation}
\text{where}\quad \  \left\{
\begin{aligned}
P_{sup} &= \frac{\sum_{c_{k} \in \mathbf{C}} \exp(c_{k} \!\cdot\! \mathcal{F}(x_{i}))}{ExpSum}; \\
P_{supcon} &= \frac{\sum_{z_{k} \in A(i)} \exp(z_{k} \cdot \mathcal{G}(x_{i}))}{ExpSum}. \label{eq:pcl_multitask} \\
\end{aligned}
\right.
\end{equation}

Multi-task learning combines supervised cross-entropy loss and supervised contrastive loss with a fixed weighted scalar. When these two losses conflict, the training can suffer from slower or sub-optimization. Our PaCo contrarily adjust the intensity of supervised cross-entropy loss and supervised contrastive loss in an adaptive way and potentially avoids conflict as analyzed in the following.

\subsubsection{Analysis of PaCo under balanced setting}
As indicated by Eq.~\eqref{eq:pcl_multitask}, compared with multi-task, PaCo has an additional loss item:
\begin{equation}
\mathcal{L}_{extra}=-\log(P_{sup}) - \alpha K^{*} \log (1-P_{sup}). \label{eq:PaCo_extra}
\end{equation}

Here, we take full ImageNet as an example, {\it i.e.}, $q^{*}=0.001, \mathtt{length}(queue)=8192, \alpha=0.05, \alpha K^{*}=0.41$.
Then the function curve for $\mathcal{L}_{extra}$ is shown in Fig.~\ref{fig:paco_psum} (b).
With $P_{sup}$ increases from 0 to 1.0, the function value decreases until $P_{sup}=0.71$ and then goes up, which implies $\mathcal{L}_{extra}$ obtains the smallest loss value when $P_{sup}=0.71$. Note that, when the whole PaCo loss in Eq.~\eqref{eq:PaCo} achieves the optimal solution, $P_{sup}=0.71$ still establishes as demonstrated by Remark \ref{thm:02_pcl}. With $P_{sup}$ increases in the training, we analyze how does it affect the intensity of supervised contrastive loss and supervised cross-entropy loss in the following.

\vspace{+0.1in}
\noindent {bf Adaptive weighting between $\mathcal{L}_{sup}$ and $\mathcal{L}_{supcon}$.}
Note that the optimal value for the probability that two samples are a true positive pair with label $y$ is 0.035 as indicated by Remark \ref{thm:02_pcl}. We suppose $p_{l}$, $p_{h}$ $\in$ (0, 0.71) and $p_{l}$ $\textless$ $p_{h}$. To achieve the optimal value, when $P_{sup}$=$p$, the supervised contrastive loss value $\mathcal{L}_{supcon}$ must decrease as in Eq.~\eqref{eq:PaCo_adaptive}.

\begin{equation}
\begin{aligned}
\mathcal{L}_{supcon}
={}& -\sum_{z_{+} \in P(i)} \log \frac{\exp(z_{+} \cdot \mathcal{G}(x_{i}) )}{\sum_{z_{k} \in A(i)} \exp(z_{k} \cdot \mathcal{G}(x_{i})) } \\
={}& -\sum_{z_{+} \in P(i)} \log \frac{ \frac{\exp(z_{+} \cdot \mathcal{G}(x_{i}) )}{ExpSum}}{\frac{\sum_{z_{k} \in A(i)} \exp(z_{k} \cdot \mathcal{G}(x_{i}))}{ExpSum}} \\
={}& -K^{*} \log \frac{0.035}{1-p}. \label{eq:PaCo_adaptive}
\end{aligned}
\end{equation}

Here $P_{sup}$ increases from $p_{l}$ to $p_{h}$, $\mathcal{L}_{supcon}$ must decrease to a much smaller loss value to achieve the optimal solution, which implies the need to make two different class samples much more discriminative, {\it i.e.}, increasing inter-class margins, and thus the intensity of supervised contrastive loss will enlarge.

An intuition is that as $P_{sup}$ increases, more samples are pulled together with their corresponding centers.
Along with stronger intensity of supervised contrastive loss at that time, it is more likely to push hard examples close to those samples that are already around right centers.

\subsection{Center Learning Rebalance}
PaCo balances the contrastive learning (for moderating contrast among samples). However the center learning also needs to be balanced, which has been explored in \cite{DBLP:journals/nn/BudaMM18,DBLP:conf/cvpr/HuangLLT16,DBLP:conf/cvpr/CuiJLSB19, he2009learning,chawla2002smote, shen2016relay, DBLP:conf/nips/RenYSMZYL20, DBLP:conf/iclr/KangXRYGFK20, DBLP:journals/corr/abs-2010-01809, DBLP:journals/corr/abs-2101-10633, DBLP:conf/nips/TangHZ20,duggal2020elf, Zhong_2021_CVPR}. We incorporate Balanced Softmax \cite{DBLP:conf/nips/RenYSMZYL20} into the center learning. Then the PaCo loss is changed from Eq.~\eqref{eq:PaCo} to what follows:
\begin{equation}
\mathcal{L}_{i} \!=\! \sum_{ z_{+} \in P(i) \cup \{c_{y}\} } \!-w(z_{+}) \log \frac{ \psi(z_{+}, T(x_{i})) }{\sum_{z_{k} \in A(i) \cup \mathbf{C}} \psi(z_{k}, T(x_{i}))},\label{eq:center_rebalance}
\end{equation}
\text{where}
\begin{equation}
\psi(z_{k}, T(x_{i}))\!=\!\left\{
\begin{array}{ll}
\exp(z_{k} \cdot \mathcal{G}(x_{i})), & z_{k} \!\in\! A(i);   \\
\exp(z_{k} \cdot \mathcal{F}(x_{i})) \cdot q(y_{k}), & z_{k} \!\in\! \mathbf{C}. \\
\end{array}
\right.
\nonumber
\end{equation}
We emphasize that Balanced Softmax is only a practical remedy for center learning rebalance. The theoretical analysis remains as a future work.

\subsection{Generalized Parametric Contrastive Learning}
MoCo \cite{DBLP:conf/cvpr/He0WXG20} and MoCo v2 \cite{DBLP:journals/corr/abs-2003-04297} use a momentum encoder and a queue to allow small mini-batch training and achieve even better performance than SimCLR \cite{DBLP:conf/icml/ChenK0H20} which requires large mini-batch training, in self-supervised learning.

To simplify the framework of PaCo, we validate how each component, {\textit i.e.}, augmentation strategy, formulation of GPaCo/PaCo, the momentum encoder and queue size, make effects in Sec. \ref{sec:ablation_study}. Interestingly, we observe that the derived Generalized Parametric Contrastive Learning (GPaCo) by removing the momentum encoder boosts performance on imbalanced and balanced data again.

In addition to long-tailed recognition, GPaCo models enjoy better generalization ability across CNNs (ResNets) to vision transformers (ViT models) on full ImageNet and CIFAR, which is demonstrated in Sec. \ref{sec:full_imagenet_cifar} and Sec. \ref{sec:robustness}.
Besides image classification, GPaCo shows its great generality on other tasks, {\textit e.g.}, out-of-distribution robustness, and semantic segmentation.

To demonstrate the advantages of GPaCo on out-of-distribution data, we load MAE \cite{he2022masked} pre-trained weights and then fine-tune on full ImageNet with same training strategy as in \cite{he2022masked}. Compared with MAE baselines, GPaCo models achieve much stronger robustness across different benchmarks, which is discussed in Sec. \ref{sec:robustness}.

For semantic segmentation task, GPaCo treats each pixel as an example. However, huge number of pixels make it unpractical to directly apply GPaCo to pixel classification. To reduce computational cost and GPU memory, we randomly sample 8192 pixels from down-sampled pixel features. These selected pixel features go through a 3-layer mlp transform and then are fed into GPaCo, which is adopted as an auxiliary loss for training optimization. GPaCo models on semantic segmentation show obvious improvements compared with baselines across 4 most popular datasets in semantic segmentation community. More details are introduced in Sec. \ref{sec:semantic_seg}.

\section{Proof to Remark 1}
For an image $X_{i}$ and its label $y_{i}$, the expectation number of positive pairs with respect to $X_{i}$ will be:

\begin{equation}
K_{y_{i}} = q(y_{i}) * (\mathtt{length}(queue) + batchsize * 2 - 1) \approx \mathtt{length}(queue) \cdot q(y_{i}),
\label{eq:K_approx}
\end{equation}

$q(y_{i})$ is the class frequency over the whole dataset. Here the "$\approx$" establishes because $batchsize \ll \mathtt{length}(queue)$ in training process. Note that we use such approximation just for simplification. Our analysis holds for the precise $K_{y_{i}}$. In what follows, we prove the optimal values for supervised contrastive loss.

Suppose training samples are i.i.d.
To minimize the supervised contrastive loss for sample $X_{i}$, according to Eq.~\eqref{eq:supcon}, we rewrite:
\begin{equation}
    \left\{
        \begin{aligned}
            P(i)&=&\{z_{1}^{+}, z_{2}^{+}, ..., z_{K_{y_{i}}}^{+} \}; \nonumber \\
            p_{i}^{+}&=&\frac{ \exp({z_{i}^{+} \cdot T(x_{i})}) }{\sum_{z_{k} \in A(i)} \exp({z_{k} \cdot T(x_{i})}) }; \nonumber \\
            p_{sum}^{+} &=& p_{1}^{+} + p_{2}^{+}+...+p_{K_{y_{i}}}^{+}. \nonumber \\
        \end{aligned}
        \right.
\end{equation}

Then the supervised contrastive loss will be:
\begin{eqnarray}
\mathcal{L}_{i} \!&=&\! -\sum_{ z_{+} \in P(i)} \log \frac{ \exp({z_{+} \cdot T(x_{i})}) }{\sum_{z_{k} \in A(i)} \exp({z_{k} \cdot T(x_{i})})}  \nonumber \\
&=& - (\log p_{1}^{+} + \log p_{2}^{+} + ... + \log p_{K_{y_{i}}}^{+}). \nonumber
\end{eqnarray}

For obtaining its optimal solution, we define the Lagrange multiplier form of $\mathcal{L}_{i}$ as:

\begin{equation}
l = - (\log p_{1}^{+} + \log p_{2}^{+} + ... + \log p_{K_{y_{i}}}^{+}) + \lambda (p_{1}^{+} + p_{2}^{+}+...+p_{K_{y_{i}}}^{+} - p_{sum}^{+}), \label{eq:largrange}
\end{equation}

where $\lambda$ is the Lagrange multiplier. The first order conditions of Eq.~\eqref{eq:largrange} w.r.t. $\lambda$ and $p_{i}^{+}$ can be written as follows:
\begin{equation}
    \left\{
        \begin{aligned}
            \frac{\partial l}{\partial p_{i}^{+}} &= -\frac{1}{p_{i}^{+}} + \lambda = 0;\\
            \frac{\partial l}{\partial \lambda} &= p_{1}^{+} + p_{2}^{+}+...+p_{K_{y_{i}}}^{+} - p_{sum}^{+} =0. \\
        \end{aligned}
        \right.
        \label{eq:largrange_conditions}
\end{equation}

From Eq.~\eqref{eq:largrange_conditions}, the optimal solution for $p_{i}^{*}$ will be $\cfrac{p_{sum}^{+}}{K_{y_{i}}}$. Note that $p_{sum}^{+} \in [0,1]$,  with a specific $p_{sum}^{+}$, the minimal loss value of $\mathcal{L}_{i}$ is:
\begin{equation}
\mathcal{L}_{i} = -K_{y_{i}} \log \frac{p_{sum}^{+}}{K_{y_{i}}}.
\end{equation}

Thus, when $p_{sum}^{+}=1.0$, $\mathcal{L}_{i}$ achieves minimum with the optimal value $p_{i}^{+}=\cfrac{1}{K_{y_{i}}}$ which is exactly the probability that two samples of the same class are a true positive pair.

\newpage
\section{Proof to Remark 2}
For the image $X_{i}$ and its label $y_{i}$,  Eq.~\eqref{eq:K_approx} still establishes for our parametric contrastive loss. To minimize the parametric contrastive loss for sample $X_{i}$, according to Eq. \eqref{eq:PaCo}, we similarly rewrite:

\begin{equation}
\left\{
\begin{aligned}
P(i)&=&\{z_{1}^{+}, z_{2}^{+}, ..., z_{K_{y_{i}}}^{+} \} \nonumber \\
p_{i}^{+}&=&\frac{ \exp({z_{i}^{+} \cdot T(x_{i})}) }{\sum_{z_{k} \in A(i) \cup \mathbf{C}} \exp({z_{k} \cdot T(x_{i})})} \nonumber \\
p_{c}^{+}&=&\frac{exp(c_{y} \cdot T(x_{i}))}{\sum_{z_{k} \in A(i) \cup \mathbf{C}} \exp({z_{k} \cdot T(x_{i})})} \\
p_{sum}^{+} &=& p_{1}^{+} + p_{2}^{+}+...+p_{K_{y_{i}}}^{+} + p_{c}^{+}. \nonumber \\
\end{aligned}
\right.
\end{equation}

Then the parametric contrastive loss will be:

\begin{eqnarray}
\mathcal{L}_{i} \!&=&\! \sum_{ z_{+} \in P(i) \cup \{c_{y}\} } \!-w(z_{+}) \log \frac{ \exp({z_{+} \cdot T(x_{i})}) }{\sum_{z_{k} \in A(i) \cup \mathbf{C}} \exp({z_{k} \cdot T(x_{i})})} \\
&=& -\left( \log p_{c}^{+} +  \alpha \cdot (\log p_{1}^{+} + \log p_{2}^{+} + ... + \log p_{k_{y_{i}}}^{+} )     \right).
\end{eqnarray}

For obtaining its optimal solution, we define the Lagrange multiplier form of $\mathcal{L}_{i}$ as:

\begin{equation}
l = -\left( \log p_{c}^{+} +  \alpha \cdot (\log p_{1}^{+} + \log p_{2}^{+} + ... + \log p_{k_{y_{i}}}^{+} )     \right) + \lambda (p_{1}^{+} + p_{2}^{+}+...+p_{K_{y_{i}}}^{+} + p_{c}^{+} - p_{sum}^{+}), \label{eq:largrange_paco}
\end{equation}

where $\lambda$ is the Lagrange multiplier. The first order conditions of Eq.~\eqref{eq:largrange_paco} w.r.t. $\lambda$, $p_{c}^{+}$ and $p_{i}^{+}$ can be written as follows:

\begin{equation}
    \left\{
        \begin{aligned}
            \frac{\partial l}{\partial p_{i}^{+}} &= - \frac{\alpha}{p_{i}^{+}} + \lambda = 0; \\
            \frac{\partial l}{\partial p_{c}^{+}} &= -\frac{1}{p_{c}^{+}} + \lambda = 0; \\
            \frac{\partial l}{\partial \lambda} &= p_{1}^{+} + p_{2}^{+}+...+p_{K_{y_{i}}}^{+} + p_{c}^{+} - p_{sum}^{+} =0. \\
        \end{aligned}
        \right.
        \label{eq:largrange_conditions_paco}
\end{equation}

From Eq.~\eqref{eq:largrange_conditions_paco}, the optimal solution for $p_{i}^{+}$ and $p_{c}^{+}$ will be $\cfrac{\alpha p_{sum}^{+}}{1+ \alpha K_{y_{i}}}$ and $\cfrac{p_{sum}^{+}}{1+ \alpha K_{y_{i}}}$ respectively. Note that $p_{sum}^{+} \in [0,1]$,  with a specific $p_{sum}^{+}$, the minimal loss value of $\mathcal{L}_{i}$ is:

\begin{equation}
\mathcal{L}_{i} = - \log \cfrac{p_{sum}^{+}}{1+ \alpha K_{y_{i}}} - \alpha K_{y_{i}} \log \frac{\alpha p_{sum}^{+}}{1+\alpha K_{y_{i}}}.
\end{equation}

Thus, when $p_{sum}^{+}=1.0$, $\mathcal{L}_{i}$ achieves minimum with the optimal value $p_{i}^{+}=\cfrac{\alpha}{1+\alpha K_{y_{i}}}$ , which is the probability that two samples of the same class are a true positive pair, and the optimal value $p_{c}^{+}=\cfrac{1}{1+\alpha K_{y_{i}}}$ which is the probability that a sample is closest to its corresponding center $c_{y_{i}}$ among $\mathbf{C}$.

\newpage
\section{Gradient Derivation}
In Section~\ref{sec:PaCo_balance}, we analyze PaCo loss under balanced setting, taking full ImageNet as an example. With $P_{sup}$ increases from 0 to 0.71, the intensity of supervised contrastive loss will enlarge. Here we show that more samples will be pulled together with their corresponding centers when $P_{sup}$ increases from 0 to 0.71 from the perspective of gradient derivation.

\begin{equation}
    \frac{\partial \mathcal{L}}{\partial c_{k}} = \left \{
        \begin{aligned}
            &(\alpha K^{*} +1 )p_{c_{k}} x_{i}, &\quad y_{i} \neq k; \\
            &\left\{ (\alpha K^{*} + 1)p_{c_{k}} -1 \right\} x_{i}, &\quad y_{i}=k. \\
        \end{aligned}
        \right.
        \label{eq:gradient_derivation}
\end{equation}

It is worthy to note that when $p_{c_{k}} \in (0,0.71)$, we have
\begin{equation}
    \left \{
        \begin{aligned}
            &\frac{\partial \mathcal{L}}{\partial c_{k}} >0, &\quad y_{i} \neq k; \\
            &\frac{\partial \mathcal{L}}{\partial c_{k}} <0, &\quad y_{i}=k. \\
        \end{aligned}
\right.
\label{eq:gradient_derivation2}
\end{equation}
Eqs.~\eqref{eq:gradient_derivation} and \eqref{eq:gradient_derivation2} mean that as $P_{sup}$ increases in training process, the probability that a sample is closest to its corresponding center will increase and the probability that a sample is closest to other centers will decrease. Thus, more and more samples will be pulled together with their right centers.

\section{Implementation details for Table 1}
We train models with cross-entropy, parametric contrastive loss 400 epochs without RandAugment respectively. For supervised contrastive loss, following the original paper, we firstly train the model 400 epochs. Then we fix the backbone and train a linear classifier 400 epochs.

\section{More Experimental Results on Many-shot, Medium-shot, and Few-shot.}

\begin{table*}[h]
	\caption{\textbf{Comprehensive results on ImageNet-LT with different backbone networks (ResNet-50, ResNeXt-50 \& ResNeXt-101).} Models are trained with RandAugment in 400 epochs. Inference time is calculated with a batch of 64 images on Nvidia GeForce 2080Ti GPU, Pytorch1.5, Python3.6.}
	\label{tab:imagenet_extra}

	\begin{center}
		\begin{tabular}{llccccc}
			\toprule
			Backbone & Method & \textbf{Inference time (ms)} & Many & Medium & Few & All\\
			\midrule
			\multirow{3}{*}{ResNet-50}
			&$\tau$-normalize &8.3 &65.0 &52.2 &32.3 &54.5 \\
			&Balanced Softmax &8.3 &66.7 &52.9 &33.0 &55.0 \\
			&PaCo             &8.3 &65.0 &55.7 &38.2 &57.0 \\
			&GPaCo            &8.3 &66.1 &57.3 &40.2 &58.5 \\
			\midrule
			\multirow{3}{*}{ResNeXt-50}
			&$\tau$-normalize &13.1 &66.4 &53.4 &38.2 &56.0 \\
			&Balanced Softmax &13.1 &67.7 &53.8 &34.2 &56.2 \\
			&PaCo             &13.1 &67.5 &56.9 &36.7 &58.2 \\
			&GPaCo            &13.1 &67.4 &57.1 &41.2 &58.9 \\
			\midrule
			\multirow{3}{*}{ResNeXt-101}
			&$\tau$-normalize &25.0 &69.0 &55.1 &36.9 &57.9 \\
			&Balanced Softmax &25.0 &69.2 &55.8 &36.3 &58.0 \\
			&PaCo             &25.0 &68.2 &58.7 &41.0 &60.0 \\
			&GPaCo            &25.0 &68.7 &59.5 &42.8 &60.8 \\
			\bottomrule
		\end{tabular}
	\end{center}
\end{table*}

\begin{table*}[h]
	\caption{\textbf{Comprehensive results on ImageNet-LT with RIDE.} Models are trained with RandAugment in 400 epochs. Inference time is calculated with a batch of 64 images on Nvidia GeForce 2080Ti GPU, Pytorch1.5, Python3.6.}

	\label{tab:imagenet_ride}
	\begin{center}
		\begin{tabular}{llccccc}
			\toprule
			Backbone & Method & \textbf{Inference time (ms)} & Many & Medium & Few & All\\
			\midrule
			\multirow{3}{*}{RIDEResNet}
			&1 expert  &8.2  &64.8 &49.8 &29.6 &52.8 \\
			&2 experts &12.0 &67.7 &53.5 &31.5 &56.0 \\
			&3 experts &15.3 &69.0 &54.7 &32.5 &57.0 \\
			\midrule
			\multirow{3}{*}{RIDEResNeXt}
			&1 expert  &13.0 &67.2 &49.0 &28.1 &53.2 \\
			&2 experts &19.0 &70.4 &52.6 &30.3 &56.4 \\
			&3 experts &26.0 &71.8 &53.9 &32.0 &57.8 \\
			\bottomrule
		\end{tabular}
	\end{center}
\end{table*}

\begin{table*}[h]
	\caption{\textbf{Comprehensive results on iNaturalist 2018 with ResNet-50 and ResNet-152.} \dag represents the models are trained without RandAugment. Inference time is calculated with a batch of 64 images on Nvidia GeForce 2080Ti GPU, Pytorch1.5, Python3.6.}

	\label{tab:inat_extra}
	\begin{center}
		\begin{tabular}{llccccc}
			\toprule
			Backbone & Method & \textbf{Inference time (ms)} & Many & Medium & Few & All\\
			\midrule
			\multirow{3}{*}{ResNet-50}
			&$\tau$-normalize &8.3 &74.1 &72.1 &70.4 &71.5 \\
			&Balanced Softmax &8.3 &72.3 &72.6 &71.7 &71.8 \\
			&PaCo             &8.3 &70.3 &73.2 &73.6 &73.2 \\
			\midrule
			\multirow{2}{*}{ResNet-50 \dag}
			&Balanced Softmax &8.3 &72.5 &72.3 &71.4 &71.7 \\
			&PaCo             &8.3 &69.5 &73.4 &73.0 &73.0 \\
			&GPaCo            &8.3 &73.1 &75.4 &75.9 &75.4 \\
			\midrule
			\multirow{1}{*}{ResNet-152}
			&PaCo &20.1 &75.0 &75.5 &74.7 &75.2  \\
			\bottomrule
		\end{tabular}
	\end{center}
\end{table*}

\newpage
\begin{table*}[t]
	\caption{\textbf{Comprehensive results on iNaturalist 2018 with RIDE.} Models are trained with RandAugment in 400 epochs without knowledge distillation. Inference time is calculated with a batch of 64 images on Nvidia GeForce 2080Ti GPU, Pytorch1.5, Python3.6.}

	\label{tab:inat_ride}
	\begin{center}
		\begin{tabular}{llccccc}
			\toprule
			Backbone & Method & \textbf{Inference time (ms)} & Many & Medium & Few & All\\
			\midrule
			\multirow{4}{*}{RIDEResNet}
			&1 expert  &8.2  &56.0 &66.3 &66.0 &65.2 \\
			&2 experts &12.0 &62.2 &70.5 &70.0 &69.5 \\
			&3 experts &15.3 &66.5 &72.1 &71.5 &71.3 \\
			\bottomrule
		\end{tabular}
	\end{center}
\end{table*}
}

\section{Conclusion}
In this paper, we have proposed the Generalized Parametric Contrastive Learning (GPaCo/PaCo), which can deal with both imbalanced and balanced data well. It is based on the theoretical analysis of supervised contrastive learning and rebalance from the convergent optimal values. On balanced data, our analysis of PaCo demonstrates that it can adaptively enhance the intensity of pushing two samples of the same class close as more samples are pulled together with their corresponding centers, which can potentially benefit hard examples learning in training.

We conduct experiments on various benchmarks of CIFAR-LT, ImageNet-LT, Places-LT, and iNaturalist 2018. The experimental results show that we create a new state-of-the-art for long-tailed recognition. With balanced data, experimental results on full ImageNet and CIFAR show that GPaCo models have better generalization ability and stronger robustness. Transfering GPaCo to semantic segmentation, obvious improvements are obtained.

\section{Experiments}
\subsection{Long-tailed Recognition}
We follow the common evaluation protocol \cite{Liu_2019_CVPR, DBLP:journals/corr/abs-2101-10633,DBLP:conf/iclr/KangXRYGFK20} in long-tailed recognition -- that is, training models on the long-tailed source label distribution and evaluating their performance on the uniform target label distribution.
We conduct experiments on long-tailed version of CIFAR-100 \cite{cb-focal, DBLP:conf/nips/CaoWGAM19}, Places~\cite{Liu_2019_CVPR}, ImageNet \cite{Liu_2019_CVPR} and iNaturalist 2018 \cite{van2018inaturalist} datasets.

\begin{table}[t]
	\centering
	\caption{\textbf{Top-1 accuracy on ImageNet-LT for different backbone architectures.}  ``\dag"~denotes models are trained with RandAugment \cite{DBLP:conf/nips/CubukZS020} in 400 epochs. More comparisons with RIDE \cite{DBLP:journals/corr/abs-2010-01809} are in Fig.~\ref{fig:comparison}.}
	\label{tab:imagenet_main}
	{
		\begin{tabular}{lc@{\ \ }c@{\ \ }c}
			\toprule
			Method & ResNet-50 & ResNeXt-50 & ResNeXt-101 \\%S & M & L  \\
			\midrule
			CE(baseline)                &41.6 &44.4 &44.8 \\
			Decouple-cRT                &47.3 &49.6 &49.4 \\
			Decouple-$\tau$-norm        &46.7 &49.4 &49.6 \\
			De-confound-TDE    &51.7 &51.8 &53.3 \\
			ResLT              &-    &52.9 &54.1 \\
			MiSLAS             &52.7 &-    & -   \\
			\midrule
			Decouple-$\tau$-norm \dag     &54.5 &56.0 &57.9 \\
			Balanced Softmax \dag         &55.0 &56.2 &58.0 \\
			PaCo\dag                      &57.0 &58.2 &60.0 \\
			GPaCo\dag                     &\textbf{58.5} &\textbf{58.9} &\textbf{60.8} \\
			\bottomrule
		\end{tabular}
	}
	\vspace{-0.15in}
\end{table}

\vspace{+0.1in}
\noindent {\bf CIFAR-100-LT datasets.}
We use the long-tailed version of CIFAR datasets with the same setting as those used in \cite{cao2019learning, zhou2019bbn, cb-focal}. They control the degrees of data imbalance with an imbalance factor $\beta$. $\beta$= $\frac{N_{max}}{N_{min}}$ where $N_{max}$ and $N_{min}$ are the numbers of training samples for the most and least frequent classes respectively. Following \cite{zhou2019bbn}, we conduct experiments with imbalance factors 100, 50, and 10.

\vspace{+0.1in}
\noindent {\bf ImageNet-LT and Places-LT.}
ImageNet-LT and Places-LT were proposed in \cite{Liu_2019_CVPR}. ImageNet-LT is a long-tailed version of ImageNet dataset \cite{imagenet} by sampling a subset following the Pareto distribution with power value $\alpha$=6. It contains 115.8K images from 1,000 categories, with class cardinality ranging from 5 to 1,280. Places-LT is a long-tailed version of the large-scale scene classification dataset Places \cite{zhou2017places}. It consists of 184.5K images from 365 categories with class cardinality ranging from 5 to 4,980.

\vspace{+0.1in}
\noindent{ \bf iNaturalist 2018.}
The iNaturalist 2018 \cite{van2018inaturalist} is one species classification dataset, which is on a large scale and suffers from extremely imbalanced label distribution. It is composed of 437.5K images from 8,142 categories. In addition to the extreme imbalance, the iNaturalist 2018 dataset also confronts the fine-grained problem \cite{wei2019piecewise}.

\vspace{+0.1in}
\noindent{\bf Implementation details.}
For image classification on ImageNet-LT, we used ResNet-50, ResNeXt-50-32x4d, and ResNeXt-101-32x4d as our backbones for experiments. For iNaturalist 2018, we conduct experiments with ResNet-50 and ResNet-152. All models were trained using SGD optimizer with momentum $\mu = 0.9$.

Contrastive learning benefits from longer training compared with traditional supervised learning with cross-entropy as Chen~\cite{DBLP:conf/icml/ChenK0H20} concluded, which is also validated by previous work of \cite{DBLP:conf/icml/ChenK0H20, DBLP:conf/cvpr/He0WXG20, DBLP:journals/corr/abs-2003-04297, DBLP:conf/nips/GrillSATRBDPGAP20, DBLP:conf/nips/CaronMMGBJ20}.
MoCo \cite{DBLP:conf/cvpr/He0WXG20, DBLP:journals/corr/abs-2003-04297}, BYOL \cite{DBLP:conf/nips/GrillSATRBDPGAP20} and SWAV \cite{DBLP:conf/nips/CaronMMGBJ20} train 800 epochs for model convergence. Supervised contrastive learning \cite{DBLP:conf/nips/KhoslaTWSTIMLK20} trains 350 epochs for feature learning and another 350 epochs for classifier learning.

Following MoCo \cite{DBLP:conf/cvpr/He0WXG20, DBLP:journals/corr/abs-2003-04297}, when we train models with GPaCo/PaCo, the learning rate decays by a cosine scheduler from 0.04/0.02 to 0 with batch size 128 on 4 GPUs in 400 epochs. The temperature is set to 0.2. $\alpha$ is 0.05.
For a fair comparison, we re-implement baselines with the same training time and RandAugment \cite{DBLP:conf/nips/CubukZS020} for recent state-of-the-arts of Decouple \cite{DBLP:conf/iclr/KangXRYGFK20}, Balanced Softmax \cite{DBLP:conf/nips/RenYSMZYL20} and RIDE~\cite{DBLP:journals/corr/abs-2010-01809}. Especially, for RIDE, based on model ensemble, we compare with it under comparable inference latency in Fig.~\ref{fig:comparison} (a).

For Places-LT, following previous setting \cite{Liu_2019_CVPR, DBLP:journals/corr/abs-2101-10633},
we choose ResNet-152 as the backbone network, pre-train it on the full ImageNet-2012 dataset (provided by torchvision), and finely tune it for 30 epochs on Places-LT. The learning rate decays by a cosine scheduler from 0.02 to 0 with batch size 128. The temperature is set to 0.2. $\alpha$ is 0.02/0.05 for GPaCo and PaCo. For CIFAR-100-LT, we strictly follow the setting of \cite{DBLP:conf/nips/RenYSMZYL20} for fair comparison. A smaller temperature of 0.07 and $\alpha= 0.01$ are adopted.

\vspace{+0.1in}
\noindent{ \bf Comparison on ImageNet-LT.}
Table~\ref{tab:imagenet_main} shows extensive experimental results for comparison with recent SOTA methods. We observe that Balanced Softmax \cite{DBLP:conf/nips/RenYSMZYL20} still achieves comparable results with Decouple \cite{DBLP:conf/iclr/KangXRYGFK20} across various backbones under such strong training setting on ImageNet-LT, consistent with what is claimed in the original paper. For RIDE that is based on model ensemble, we analyze the real inference speed by calculating inference time with a batch of 64 images on Nvidia GeForce 2080Ti GPU.

We observe RIDEResNet with 3 experts even has higher inference latency than a standard ResNeXt-50-32x4d (\textbf{15.3ms vs 13.1ms}); RIDEResNeXt with 3 experts yields higher inference latency than a standard ResNeXt-101-32x4d (\textbf{26ms vs 25ms}). This result is in accordance with the conclusion that network fragmentation reduces the degree of parallelism and thus decreases efficiency in \cite{DBLP:conf/eccv/MaZZS18, DBLP:conf/iccv/CuiCLLSJ19}. For fair comparison, we do not apply knowledge distillation tricks for all these methods. As shown in Fig.~\ref{fig:comparison} (a) and Table~\ref{tab:imagenet_main}, under comparable inference latency, GPaCo/PaCo significantly surpasses these baselines.

\begin{table}[t]
	\centering
	\caption{\textbf{Performance on Places-LT~\cite{Liu_2019_CVPR}, starting from an ImageNet pre-trained ResNet-152 provided by torchvision.} ``\dag" denotes the model trained with RandAugment \cite{DBLP:conf/nips/CubukZS020}.}
	\label{tab:place_main}
	{
		\begin{tabular}{lc@{\ \ }c@{\ \ }c@{\ \ }c}
			\toprule
			Method & Many & Medium & Few & \textbf{All}      \\
			\midrule
			CE(baseline)      & 45.7 & 27.3 & 8.2 & 30.2     \\
			OLTR              & 44.7 & 37.0 & 25.3 & 35.9    \\
			Decouple-$\tau$-norm & 37.8 & 40.7 & 31.8 & 37.9 \\
			Balanced Softmax     & 42.0 & 39.3 & 30.5 & 38.6 \\
			ResLT                & 39.8 & 43.6 & 31.4 & 39.8 \\
			MiSLAS               & 39.6 & 43.3 & 36.1 & 40.4 \\
			RIDE (2 experts)     & -    & -    & -    & -    \\
			\midrule
			PaCo                  & 37.5 & 47.2 & 33.9 & 41.2 \\
			PaCo \dag             & 36.1 & 47.9 & 35.3 & 41.2 \\
			GPaCo                 & 39.5 & 47.2 & 33.0 &\textbf{41.7} \\
			\bottomrule
		\end{tabular}
	}
	\vspace{-0.15in}
\end{table}

\begin{table*}
	\centering
	\setlength{\tabcolsep}{7.5pt}
	\caption{\textbf{Evaluation with ViT models\cite{dosovitskiy2020image} on full ImageNet and out-of-distribution data.} GPaCo models enjoy better generalization ability and stronger robustness compared with MAE models. We use their official open-source code for reproduing results of MAE models with 8 Nvidia GeForce RTX3090 GPUs. Top-1 accuracy are reported for full ImageNet, ImageNet-R, and ImageNet-S. mCE and rel. mCE are reported for ImageNet-C.}
	\label{tab:full_imagenet_vit}

	{
		\begin{tabular}{lcccccc}
			\toprule
			Method &Model &Full ImageNet ($\uparrow$) &ImageNet-C (mCE $\downarrow$) &ImageNet-C (rel. mCE $\downarrow$) & ImageNet-R ($\uparrow$) &ImageNet-S ($\uparrow$) \\
			\midrule
			\multicolumn{7}{c}{w/ Mixup and CutMix} \\
			\midrule
			MAE    &ViT-B &83.6 &39.1 &49.9 &49.9 &36.1 \\
			MAE    &ViT-L &85.7 &32.4 &41.4 &60.3 &45.5 \\
			\midrule
			\multicolumn{7}{c}{w/o Mixup and CutMix} \\
			\midrule
			SupCon       &ResNet-50 &78.7 &67.2 &94.6 &-     &-    \\
			GPaCo        &ResNet-50 &\textbf{79.7} &\textbf{50.9} &\textbf{64.4} &\textbf{41.1} &\textbf{30.9} \\
			\midrule
			MAE    &ViT-B &82.5 &44.9 &56.9 &44.9 &32.9 \\
			MAE    &ViT-L &85.2 &36.4 &46.3 &55.3 &42.6 \\
			GPaCo        &ViT-B  &\textbf{84.0} &\textbf{37.2} &\textbf{47.3} &\textbf{51.7} &\textbf{39.4} \\
			GPaCo        &ViT-L  &\textbf{86.0} &\textbf{30.7} &\textbf{39.0} &\textbf{60.3} &\textbf{48.3} \\
			\bottomrule
		\end{tabular}
	}
\end{table*}

\begin{table}
	\centering
	\setlength{\tabcolsep}{5pt}
	\caption{\textbf{Top-1 accuracy on full ImageNet with ResNets.} ``$\star$" denotes supervised contrastive learning with additional operation of image warping before Gaussian blur.}
	\label{tab:full_imagenet}

	{
		\begin{tabular}{lccc}
			\toprule
			Method & Model & augmentation &Top-1 Acc \\
			\midrule
			Supcon     &ResNet-50  &SimAugment $\star$   &77.9 \\
			Supcon     &ResNet-50  &RandAugment          &78.4 \\
			Supcon     &ResNet-101 &StackedRandAugment   &80.2 \\
			\midrule
			multi-task &RandAugment         &ResNet-50 &78.1 \\
			\midrule
			PaCo        &ResNet-50  &SimAugment           &\textbf{78.7} \\
			PaCo        &ResNet-50  &RandAugment          &\textbf{79.3} \\
			PaCo        &ResNet-101 &StackedRandAugment   &\textbf{80.9} \\
			PaCo        &ResNet-200 &StackedRandAugment   &\textbf{81.8} \\
			\midrule
			GPaCo        &ResNet-50  &RandAugment         &\textbf{79.5} \\
			GPaCo        &ResNet-50  &StackedRandAugment  &\textbf{79.7} \\
			\bottomrule
		\end{tabular}
	}
\end{table}

\vspace{+0.1in}
\noindent{\bf Comparison on Places-LT.}
The experimental results on Places-LT are summarized in Table~\ref{tab:place_main}. Due to the architecture change of RIDE, it is not applicable to load the publicly pre-trained model on full ImageNet, while GPaCo/PaCo is more flexible because the network architecture is the same as those of \cite{Liu_2019_CVPR, DBLP:journals/corr/abs-2101-10633}. Under fair training setting by finely tuning 30 epochs without RandAugment, PaCo surpasses SOTA Balanced Softmax by 2.6\%. GPaCo even achieves 41.7\% after removing the momentum encoder. An interesting observation is that RandAugment has little effect on the Places-LT dataset. A similar phenomenon can be observed on the iNaturalist 2018 dataset. More evaluation numbers are in the supplementary file. They can be intuitively understood since RandAugment is designed for ImageNet classification, which inspires us to explore general augmentations across different domains.

\vspace{+0.1in}
\noindent{\bf Comparison on iNaturalist 2018.}
Table~\ref{tab:inat_main} lists experimental results on iNaturalist 2018. Under fair training setting, PaCo consistently surpasses recent SOTA methods of Decouple, Balanced Softmax and RIDE. Our method is 1.4\% higher than Balanced Softmax. We also apply PaCo on large ResNet-152 architecture. And the performance boosts to \textbf{75.3\%} top-1 accuracy. Surprisingly, With GPaCo, a ResNet-50 model achieves \textbf{75.4\%} top-1 accuracy, implying that the momentum encoder for PaCo can hurt optimization in training.
Note that we only transfer the hyper-parameters of PaCo on ImageNet-LT to iNaturalist 2018 without any change. Tuning hyper-parameters for GPaCo/PaCo will bring further improvement.

\vspace{+0.1in}
\noindent{\bf Comparison on CIFAR-100-LT.}
The experimental results on CIFAR-100-LT are listed in Table~\ref{tab:cifar100_main}. For the CIFAR-100-LT dataset, we mainly compare with the SOTA method Balanced Softmax \cite{DBLP:conf/nips/RenYSMZYL20} with the same training setting where Cutout \cite{DBLP:journals/corr/abs-1708-04552} and AutoAugment \cite{DBLP:conf/cvpr/CubukZMVL19} are used in training. As shown in Table~\ref{tab:cifar100_main}, PaCo consistently outperforms Balanced Softmax across different imbalance factors with such a strong setting. Specifically, PaCo surpasses Balanced Softmax by 1.2\%, 1.8\% and 1.2\% under imbalance factor 100, 50 and 10 respectively, which testify the effectiveness of our PaCo method. GPaCo models show better performance than PaCo models.

\subsection{Full ImageNet and CIFAR Recognition}
\label{sec:full_imagenet_cifar}
As analyzed in Section \ref{sec:PaCo_balance}, for balanced datasets, PaCo reduces to an improved version of multi-task learning, which adaptively adjusts the intensity of supervised cross-entropy loss and supervised contrastive loss. To verify the effectiveness of PaCo under this balanced setting, we conduct experiments on full ImageNet and full CIFAR. They are indicative to compare GPaCo/PaCo with supervised contrastive learning (Supcon) \cite{DBLP:conf/nips/KhoslaTWSTIMLK20}. Note that, under full ImageNet and CIFAR, we remove the rebalance in center learning, {\it i.e.}, Balanced Softmax, for fair comparisons.

\begin{table}[t]
	\centering
	\setlength{\tabcolsep}{30pt}
	\caption{\textbf{Top-1 accuracy over all classes on iNaturalist 2018 with ResNet-50.} Knowledge distillation is not applied for fair comparison. We compare with RIDE under comparable inference latency. ``\dag"~denotes models trained with RandAugment \cite{DBLP:conf/nips/CubukZS020} in 400 epochs.}
	\vspace{+0.03in}
	\label{tab:inat_main}

	{
		\begin{tabular}{lc}
			\toprule
			Method & Top-1 Acc \\
			\midrule

			LDAM+DRW                   & 68.0 \\

			Decouple-LWS               & 69.5 \\
			BBN                        & 69.6 \\
			ResLT                      & 70.2 \\
			MiSLAS                     & 71.6 \\
			\midrule
			RIDE (2 experts) \dag         & 69.5 \\
			Decouple-$\tau$-norm \dag     & 71.5 \\
			Balanced Softmax \dag         & 71.8 \\
			PaCo \dag                     & 73.2 \\
			GPaCo \dag                    & \textbf{75.4} \\
			\bottomrule
		\end{tabular}
	}
\end{table}

\vspace{+0.1in}
\noindent{\bf Full ImageNet.}
In the implementation, we transfer hyper-parameters of GPaCo/PaCo on ImageNet-LT to full ImageNet without modification. SGD optimizer with momentum $\mu = 0.9$ is used. $\alpha$=0.05, temperature is 0.2 and queue size is 8,192.
For multi-task training, the supervised contrastive loss is an additional regularization and the loss weight is extensively explored from 0.1 to 1.0 in Sec. \ref{sec:ablation_study}. The same data augmentation strategy is applied as in GPaCo/PaCo, which is discussed in Section~\ref{Sec:data_augmentation}.

The experimental results are summarized in Table~\ref{tab:full_imagenet}. With SimAugment, our ResNet-50 PaCo model achieves 78.7\% top-1 accuracy, which outperforms supervised contrastive learning model by 0.8\%. Equipped with strong augmentation, {\it i.e.}, RandAugment \cite{DBLP:conf/nips/CubukZS020}, the performance further improves to 79.3\%. ResNet-101/200 trained with PaCo consistently surpass supervised contrastive learning.
Replacing PaCo with GPaCo, The ResNet-50 model boosts to \textbf{79.7\%} top-1 accuracy.

\vspace{+0.1in}
\noindent{\bf Full CIFAR-100.}
For CIFAR implementation, we follow supervised contrastive learning and train ResNet-50 with only the SimAugment. Compared with full ImageNet, we adopt a smaller temperature of 0.07, $\alpha=0.01$ and batch size 256 with learning rate 0.1. As shown in Table~\ref{tab:full_cifar}, on CIFAR-100, PaCo outperforms supervised contrastive learning by 2.6\%, which validates the advantages of PaCo. Again, the GPaCo model achieves \textbf{80.3\%} top-1 accuracy, significantly surpassing supervised contrastive learning by \textbf{3.8\%}.
Note that, following \cite{DBLP:conf/iccv/CuiCLLSJ19}, we use a weight-decay of 5e-4.

\begin{table}[t]
	\centering
	\caption{\textbf{Transfering GPaCo to the semantic segmentation.} }
	\label{tab:ade20k_smseg}

	{
		\begin{tabular}{lccc}
			\toprule
			Method &Backbone &mIoU (s.s.) &mIoU (m.s.) \\
			\midrule
			\multicolumn{4}{c}{\textbf{ADE20K Dataset}} \\
			\midrule
			\multirow{3}{*}{UperNet}  &Swin-T &44.5 &45.8\\
			                          &Swin-B &50.0 &51.7\\
			                          &Swin-L &52.0 &53.5\\
			\midrule
			\multirow{3}{*}{UperNet w/ GPaCo}     &Swin-T &\textbf{45.4} &\textbf{46.8} \\
		                	                      &Swin-B &\textbf{51.6} &\textbf{53.2} \\
			                                      &Swin-L &\textbf{52.8} &\textbf{54.3} \\
			\midrule
			\multicolumn{4}{c}{\textbf{COCO-Stuff Dataset}} \\
			\midrule
			\multirow{2}{*}{deeplabv3+} &ResNet-50  &35.8 &36.8\\
			                            &ResNet-101 &38.1 &39.0\\
			\midrule
			\multirow{2}{*}{deeplabv3+ w/ GPaCo}     &ResNet-50  &\textbf{37.0} &\textbf{37.9} \\
		                	                         &ResNet-101 &\textbf{38.8} &\textbf{40.1} \\
		    \midrule
			\multicolumn{4}{c}{\textbf{PASCAL Context Dataset}} \\
			\midrule
			\multirow{2}{*}{deeplabv3+} &ResNet-50  &50.5 &52.1\\
			                            &ResNet-101 &52.9 &54.5\\
			\midrule
			\multirow{2}{*}{deeplabv3+ w/ GPaCo}     &ResNet-50  &\textbf{51.9} &\textbf{53.7} \\
		                	                         &ResNet-101 &\textbf{54.2} &\textbf{56.2} \\
		    \midrule
		    \multicolumn{4}{c}{\textbf{Cityscapes}} \\
			\midrule
			\multirow{3}{*}{deeplabv3+} &ResNet-18  &76.9 &78.8 \\
			                            &ResNet-50  &80.1 &81.1 \\
			                            &ResNet-101 &81.0 &82.0 \\
			\midrule
			\multirow{3}{*}{deeplabv3+ w/ GPaCo}     &ResNet-18  &\textbf{78.1} &\textbf{79.7} \\
			                                         &ResNet-50  &\textbf{80.8} &\textbf{82.0} \\
		                	                         &ResNet-101 &\textbf{81.4} &\textbf{82.1} \\

			\bottomrule
		\end{tabular}
	}
\end{table}

\subsection{Out-of-distribution Robustness}
\label{sec:robustness}
He et al. \cite{he2022masked} justifies that masked autoencoders are scalable vision learners. With such a simple pre-training strategy that masking random patches of the input image and reconstructing the missing pixels, the good representation is learned and well transffered to downstream tasks, {\textit i.e.}, full ImageNet classification, object detection, semantic segmentaiton, and robustness on out-of-distribution data. In this section, we verify that GPaCo can enhance model generalization ability and robustness on full ImageNet and its variants when compared with MAE \cite{he2022masked} models.

\vspace{+0.1in}
\noindent {\bf Robustness Evaluation.}
We extensively evaluate the model performance on out-of-distribution robustness using following benchmarks: 1) ImageNet-C \cite{hendrycks2018benchmarking}, with various common image corruptions; 2) ImageNet-R \cite{hendrycks2021many}, which contains natural renditions of ImageNet object classes with different textures and local image statistics; 3) ImageNet-Sketch \cite{wang2019learning}, which includes sketch images of the same ImageNet classes collected online.

\begin{table}[t]
	\setlength{\tabcolsep}{15pt}
	\centering
    \caption{\textbf{Top-1 accuracy on CIFAR-100-LT with different imbalance factors.} ``\dag" represents that models are trained in same setting.}

	{
		\begin{tabular}{l  c  c  c}
			\toprule
			Dataset & \multicolumn{3}{c}{CIFAR-100 LT} \\
			\midrule
			Imbalance factor &100 &50 & 10 \\
			\midrule
			Focal Loss  & 38.4 & 44.3 & 55.8 \\
			LDAM+DRW    & 42.0 & 46.6 & 58.7 \\
			BBN         & 42.6 & 47.0 & 59.1 \\
			Causal Norm & 44.1 & 50.3 & 59.6 \\
			ResLT       & 45.3 & 50.0 & 60.8 \\
			MiSLAS      & 47.0 & 52.3 & 63.2 \\
			\midrule

			Balanced Softmax \dag &50.8 &54.2 &63.0 \\
			PaCo \dag    &52.0 &56.0 &64.2 \\
			GPaCo \dag   &\textbf{52.3} &\textbf{56.4} &\textbf{65.4} \\
			\bottomrule
		\end{tabular}
	}
	\label{tab:cifar100_main}
\end{table}

\begin{table}[t]
	\setlength{\tabcolsep}{19pt}
	\centering
	\caption{\textbf{Top-1 accuracy on full CIFAR-100 with ResNet-50.}}
	\label{tab:full_cifar}

	{
		\begin{tabular}{lccc}
			\toprule
			Method & dataset &Top-1 Acc \\
			\midrule
			CE(baseline)    &CIFAR-100    &77.9 \\
			multi-task      &CIFAR-100    &78.0 \\
			\midrule
			Supcon          &CIFAR-100    &76.5 \\
			PaCo            &CIFAR-100    &79.1 \\
			GPaCo           &CIFAR-100    &\textbf{80.3} \\
			\bottomrule
		\end{tabular}
	}
\end{table}

\vspace{+0.1in}
\noindent {\bf Comparison with MAE Models \cite{he2022masked}.}
We summarize experimental results in Table~\ref{tab:full_imagenet_vit}. Top-1 accuracy is reported on full ImageNet, ImageNet-R, and ImageNet-S. Mean Corruption Error (mCE) and Relative Mean Corruption Error (rel. mCE) \cite{hendrycks2018benchmarking} are used for ImageNet-C. mCE is to measure absolute robustness to corruptions while rel. mCE is a better metric when we compare models with different top-1 accuracy.

Compared with MAE models, we achieve better performance on full ImageNet, surpassing them by \textbf{0.4} and \textbf{0.3} respectively for ViT-B \cite{dosovitskiy2020image} and ViT-L \cite{dosovitskiy2020image}. On ImageNet-C, ImageNet-R, and ImageNet-S, GPaCo models usually outperforms MAE models by \textbf{1.7 $\sim$ 3.3}, demonstrating much stronger robustness on out-of-distribution data.

\subsection{Semantic Segmentation}
\label{sec:semantic_seg}
In this section, we transfer GPaCo to the downstream task, {\textit i.e.}, semantic segmentation. In implementation, we use GPaCo as an auxiliary loss. Specifically, for each image, we randomly sample 8192 pixel features on the donwn-sampled feature map and feed them into GPaCo loss for training optimization.

\vspace{+0.1in}
\noindent {\bf Datasets.}
ADE20K \cite{zhou2017scene} contains 22K densely annotated images with 150 fine-grained semantic concepts. The training and validation sets consist of 20K and 2K images, respectively.
COCO-Stuff \cite{caesar2018coco} includes 10K images from the COCO training set. The training and validation sets consist of 9K and 1K images, respectively. It covers 171 classes.
For PASCAL Context \cite{mottaghi2014role}, the subset of 59 frequent classes is used following previous work.
Cityscapes \cite{cordts2016cityscapes} consists of 19 classes, covering street scenes from 50 different cities.

\vspace{+0.1in}
\noindent {\bf Training and Evaluation.}
We implement our GPaCo in mmseg codebase \cite{mmseg2020}. On ADE20K \cite{zhou2017scene}, we follow \cite{liu2021swin} to experiment with Swin transformers and UperNet \cite{xiao2018unified}. On COCO-Stuff \cite{caesar2018coco}, Pascal Context \cite{mottaghi2014role} and Cityscapes \cite{cordts2016cityscapes}, we use ResNet-50/101 and deeplabv3+.
Default training hyper-parameters in baselines are adopted in the GPaCo model training phase, {\textit i.e.}, the standard random scale jittering between 0.5 and 2.0, random horizontal flipping, random cropping, as well as random color jittering. We report both single scale (s.s.) and multi-scale (m.s.) evaluation results on validation data. For multi-scale inference, scales of 0.5, 0.75, 1.0, 1.25, 1.5, 1.75 are used.

\vspace{+0.1in}
\noindent {\bf Results.}
Experimental results are summarized in Table~\ref{tab:ade20k_smseg}. On ADE20K, obvious improvements are observed from Swin-T to Swin-L models when equipped with GPaCo, outperforming baselines by \textbf{1.0}, \textbf{1.5}, \textbf{0.8} mIoU respectively. On COCO-Stuff and PASCAL Context, GPaCo models significantly surpass baselines by around \textbf{1.1 $\sim$ 1.7} mIoU.

\begin{table}[t]
	\centering
	\setlength{\tabcolsep}{10pt}
	\caption{\textbf{Ablation on augmentation strategies for GPaCo/PaCo on ImageNet-LT with ResNet-50.}}
	\label{tab:ablation_strongaug}
	{
		\begin{tabular}{lccc}
			\toprule
			Methods  &View-1 & View-2 &Top-1 Acc \\
			\midrule
			PaCo      &SimAug  &SimAug   &55.0 \\
			PaCo      &RandAug &SimAug   &57.0 \\
			PaCo      &RandAug &RandAug  &56.5 \\
			\midrule
			GPaCo     &RandAug &SimAug        &57.9 \\
			GPaCo     &RandAug &RandAugStack  &58.5 \\
			\bottomrule
		\end{tabular}
	}
\end{table}

\begin{table}[t]
	\centering
	\setlength{\tabcolsep}{22pt}
	\caption{\textbf{Comparison with multi-task re-weighting baselines on ImageNet-LT with ResNet-50.} The re-weighting strategy is applied to the supervised contrastive loss. Models are all trained without RandAugment. }
	\label{tab:ablation_reweighting_supp}
	\vspace{0pt}
	{
		\begin{tabular}{lc}
			\toprule
			Method  &Top-1 Acc \\
			\midrule
			CE                              &48.4 \\
			multi-task (CE+Re-weighting)    &49.0 \\
			multi-task (CE+BalSfx)  &48.6 \\
			\midrule
			PaCo                &51.0 \\
			\bottomrule
		\end{tabular}
	}
\end{table}

\begin{table}[t]
	\centering
	\setlength{\tabcolsep}{8pt}
	\caption{\textbf{Comparison with multi-task re-weighting baselines that perform center learning rebalance on ImageNet-LT.} Models are all trained with RandAugment in 400 epochs.}
	\label{tab:ablation_center_rebalance_supp}
	\vspace{0pt}

	{
		\begin{tabular}{lccc}
			\toprule
			Method  &Backbone &Weight &Top-1 Acc \\
			\midrule
			multi-task (BalSfx \!+\! rw)      &ResNeXt-50 &0.05 &57.0  \\
			multi-task (BalSfx \!+\! rw)      &ResNeXt-50 &0.10 &57.1  \\
			multi-task (BalSfx \!+\! rw)      &ResNeXt-50 &0.20 &57.1  \\
			multi-task (BalSfx \!+\! rw)      &ResNeXt-50 &0.30 &57.0  \\
			multi-task (BalSfx \!+\! rw)      &ResNeXt-50 &0.50 &57.2  \\
			multi-task (BalSfx \!+\! rw)      &ResNeXt-50 &0.80 &57.2  \\
			multi-task (BalSfx \!+\! rw)      &ResNeXt-50 &1.00 &56.9  \\
			PaCo                &ResNeXt-50 &- &58.2 \\
			\midrule
			multi-task* (BalSfx \!+\! rw)     &ResNeXt-50 &0.50 &58.3  \\
			multi-task* (BalSfx \!+\! rw)     &ResNeXt-50 &0.80 &58.2  \\
			GPaCo               &ResNeXt-50 &- &58.9 \\
			\midrule
			multi-task* (BalSfx \!+\! rw)     &ResNet-50 &0.50 &57.8  \\
			GPaCo                             &ResNet-50 &-    &58.5  \\
			\midrule
			multi-task* (BalSfx \!+\! rw)     &ResNeXt-101 &0.50 &60.0  \\
			GPaCo                             &ResNeXt-101 &-    &60.8  \\
			\bottomrule
		\end{tabular}
	}
\end{table}

\begin{table}[t]
	\centering
	\setlength{\tabcolsep}{10pt}
	\caption{\textbf{Comparison with multi-task baselines on balanced data.}}
	\label{tab:ablation_multitask_cifar100}

	\resizebox{1.0\linewidth}{!}
	{
		\begin{tabular}{lccc}
			\toprule
			Method  &Backbone &Weight &Top-1 Acc \\
			\midrule
			\multicolumn{4}{c}{\textbf{Full CIFAR-100 Dataset}} \\
			\midrule
			multi-task (CE \!+\! Supcon)       &ResNet-50 &0.50 &78.0  \\
			PaCo                &ResNet-50 &- &79.1 \\
			\midrule
			multi-task* (CE \!+\! Supcon)      &ResNet-50 &0.10 &79.0  \\
			multi-task* (CE \!+\! Supcon)      &ResNet-50 &0.30 &79.1  \\
			multi-task* (CE \!+\! Supcon)      &ResNet-50 &0.50 &79.1  \\
			multi-task* (CE \!+\! Supcon)      &ResNet-50 &0.80 &78.9  \\
			multi-task* (CE \!+\! Supcon)      &ResNet-50 &1.00 &79.0  \\
			GPaCo               &ResNet-50 &- &80.3 \\
			\midrule
			\multicolumn{4}{c}{\textbf{Full ImageNet Dataset}} \\
			\midrule
			multi-task* (CE \!+\! Supcon)      &ViT-B &0.50 &83.4  \\
			GPaCo               &ViT-B &- &84.0 \\
			\bottomrule
		\end{tabular}
	}
\end{table}

\subsection{Ablation Study}
\label{sec:ablation_study}
\vspace{+0.1in}
\noindent{\bf Data augmentation strategy for PaCo \& GPaCo.}
\label{Sec:data_augmentation}
Data augmentation is the key for success of contrastive learning as indicated by Chen~\cite{DBLP:conf/icml/ChenK0H20}. For PaCo \& GPaCo, we also conduct ablation studies for different augmentation strategies. Several observations are intriguingly different from those of \cite{ouyang2016factors}.
We experiment with the following ways of data augmentation.
\begin{itemize}
	\item SimAug: an augmentation policy \cite{DBLP:conf/cvpr/He0WXG20, DBLP:journals/corr/abs-2003-04297} that applies random flips and color jitters followed by Gaussian blur.
	\item RandAug \cite{DBLP:conf/nips/CubukZS020}: A two stage augmentation policy that uses random parameters in place of parameters tuned by AutoAugment. The random parameters do not need to be tuned and hence reduces the search space.
	\item RandAugStack: RandAug followed by Gaussian blur.
\end{itemize}

For the common {\it random resized crop} used along with the above three strategies, work of \cite{ouyang2016factors} explains that the optimal hyper-parameter for random resized crop is (0.2,1) in self-supervised contrastive learning. This setting is also adopted by other work of \cite{DBLP:conf/icml/ChenK0H20, DBLP:conf/cvpr/He0WXG20, DBLP:journals/corr/abs-2003-04297, DBLP:conf/nips/GrillSATRBDPGAP20, DBLP:conf/nips/CaronMMGBJ20}. However, in this paper, we observe severe performance degradation on ImageNet-LT with ResNet-50 (55.0\% vs 52.2\%) for PaCo when we change the hyper-parameter from (0.08,1) to (0.2, 1).
This is because PaCo involves center learning while other self-supervised frameworks only apply non-parametric contrastive loss as described in Section \ref{Sec:contrastive_learning}.
Note that the same phenomenon is also observed on traditional supervised learning with cross-entropy loss.

Another observation is that GPaCo can make better use of strong augmentations compared with PaCo. The work of \cite{wang2021contrastive} demonstrates that directly applying strong data augmentation in MoCo \cite{DBLP:conf/cvpr/He0WXG20, DBLP:journals/corr/abs-2003-04297} does not work well. Here we observe a similar conclusion with RandAug \cite{DBLP:conf/nips/CubukZS020} for PaCo. However, after removing the momentum encoder, GPaCo can achieve better performance with stronger augmentation as shown in Table~\ref{tab:ablation_strongaug}.

\begin{table}[t]
	\centering
	\setlength{\tabcolsep}{10pt}
	\caption{\textbf{Ablation for the necessary of two-view training on full ImageNet with ViT-B.}}
	\label{tab:ablation_twoview}

	{
		\begin{tabular}{lcc}
			\toprule
			Method  &Full ImageNet($\uparrow$) &ImageNet-C(rel. mCE $\downarrow$) \\
			\midrule
			single-view   &82.5 & 49.1\\
			two-view      &84.0 & 47.3\\
			\bottomrule
		\end{tabular}
	}
\end{table}

\begin{table}[t]
	\centering
	\setlength{\tabcolsep}{10pt}
	\caption{\textbf{Ablation for model ensemble on ImageNet-LT.} ``\dag" represents the ensemble model of a ResNeXt-50 and a ResNeXt-101. ``*" represents the results are from their original paper \cite{9774921}.}
	\label{tab:ablation_ensemble}

	\resizebox{1.0\linewidth}{!}
	{
		\begin{tabular}{lcccc}
			\toprule
			Method  &Many &Medium &Few &All\\
			\midrule
			\multicolumn{5}{c}{\textbf{Single Model}} \\
			\midrule
			ResLT *(ResNeXt-50)    &63.0 &50.5 &35.5 &52.9 \\
			RIDE (ResNeXt-50)      &67.2 &49.0 &28.1 &53.2 \\
			GPaCo (ResNeXt-50)     &67.4 &57.1 &41.2 &58.9 \\
			GPaCo (ResNeXt-101)    &68.7 &59.5 &42.8 &60.8 \\
			\midrule
			\multicolumn{5}{c}{\textbf{Model Ensemble}} \\
			\midrule
			ResLT*           &64.0 &56.6 &44.8 &57.6 \\
			RIDE             &71.8 &53.9 &32.0 &57.8 \\
			GPaCo (ResNeXt-50 2-experts)           &69.9 &59.5 &43.4 &61.3 \\
			GPaCo \dag                             &70.1 &61.2 &45.0 &62.4 \\
			GPaCo (ResNeXt-101 2-experts)          &70.9 &62.0 &45.2 &\textbf{63.2} \\
			\bottomrule
		\end{tabular}
	}
\end{table}

\vspace{+0.1in}
\noindent {\bf Multi-task Learning.}
Re-weighting is a classical method for dealing with imbalanced data. Here we directly apply the re-weighting method of Cui~\cite{cb-focal} in contrastive learning to compare with PaCo. Moreover, Balanced softmax (BalSfx) \cite{DBLP:conf/nips/RenYSMZYL20}, as one state-of-the-art method for traditional cross-entropy in long-tailed recognition, is also applied to contrastive learning rebalance. The experimental results are summarized in Table~\ref{tab:ablation_reweighting_supp}. It is obvious PaCo significantly surpasses the two baselines.

PaCo/GPaCo balances the contrastive learning (for moderating contrast among samples). However the center learning also needs to be balanced, which has been explored in \cite{DBLP:journals/nn/BudaMM18,DBLP:conf/cvpr/HuangLLT16,DBLP:conf/cvpr/CuiJLSB19, he2009learning,chawla2002smote, shen2016relay, DBLP:conf/nips/RenYSMZYL20, DBLP:conf/iclr/KangXRYGFK20, DBLP:journals/corr/abs-2010-01809, DBLP:journals/corr/abs-2101-10633, DBLP:conf/nips/TangHZ20,duggal2020elf}. To compare with state-of-the-art methods in long-tailed recognition, we incorporate Balanced Softmax (BalSfx) \cite{DBLP:conf/nips/RenYSMZYL20} into the center learning. As shown in Table~\ref{tab:ablation_center_rebalance_supp}, after rebalance in center learning, GPaCo boosts performance to 58.9\%, surpassing baselines.

We also verify the advantage of GPaCo over multi-task learning on balanced data --- full ImageNet and full CIFAR-100. As shown in Table~\ref{tab:ablation_multitask_cifar100}, extensive values for the weight between cross-entropy and supervised contrastive learning have been explored. GPaCo obviously achieve much higher performance.

\vspace{+0.1in}
\noindent {\bf GPaCo with Queue Length.}
The queue is designed to enlarge the number of samples for GPaCo/PaCo loss. We examine the effects of different queue size on model performance.
Empirical study on ImageNet-LT with ResNeXt-50 is conducted. As shown in Fig~\ref{fig:ablation_queuesize}, the larger queue size usually leads to better performance. However, when the queue size increase from 4096 to 8192, the performance gains become much smaller.

\vspace{+0.1in}
\noindent {\bf Necessary of Two Views in GPaCo.}
In training of GPaCo, a positive pair consists of two images belonging to the same class. We explore whether it is necessary to generate two views as in the self-supervised learning \cite{DBLP:conf/icml/ChenK0H20, DBLP:conf/cvpr/He0WXG20,DBLP:journals/corr/abs-2003-04297}. As shown in Table~\ref{tab:ablation_twoview}, performance and robustness significantly drops with single view training, which implies the vast importance of two views training in GPaCo.

\begin{figure}[t]
	\begin{center}
		\includegraphics[width=0.8\linewidth]{Figs/ablation_queuesize.pdf}
		\caption{\textbf{The larger queue size, the better performance.} Experimental results with ResNeXt-50 on ImageNet-LT are plotted. }
		\label{fig:ablation_queuesize}
	\end{center}
\end{figure}

\vspace{+0.1in}
\noindent{\bf Model Ensemble.}
Models trained on imbalanced data can easily suffer from over-fitting issue on low-frequency classes, thus leading to high variance of model predictions. RIDE proposes an improved version of model ensemble strategy and has verified the advantages of model ensemble for long-tailed recognition. However, GPaCo/PaCo improves single model performance with better feature representation. We go deeper to explore the model ensemble strategy on GPaCo models. As shown in Table \ref{tab:ablation_ensemble},  the improvements coming from model ensemble is much smaller for GPaCo models when compared with RIDE and ResLT (improvements of ResLT v.s. RIDE v.s. GPaCo are 4.7\% v.s. 4.6\% v.s. 2.4\% ), demonstrating that GPaCo training can reduce prediction variance of trained models.

\section{Introduction}\label{sec:introduction}}

\IEEEPARstart{C}{onvolutional} neural networks (CNNs) have achieved great success in various tasks, including image classification \cite{he2016deep,vggnet}, object detection \cite{DBLP:conf/cvpr/LinDGHHB17, DBLP:conf/cvpr/LiuQQSJ18} and semantic segmentation \cite{DBLP:conf/cvpr/ZhaoSQWJ17}. Especially, with the rise of neural network search \cite{DBLP:conf/cvpr/ZophVSL18, DBLP:conf/iclr/LiuSY19, DBLP:conf/cvpr/TanCPVSHL19, DBLP:conf/iccv/CuiCLLSJ19, DBLP:conf/iclr/CaiGWZH20}, performance of CNNs have further taken a big step. However, The huge progress highly depends on large-scale and high-quality datasets, such as ImageNet \cite{imagenet}, MS COCO \cite{coco} and Places \cite{zhou2017places}. But when deal with real-world applications, generally we face the long-tailed distribution problem -- a few classes contain many instances, while most classes contain only a few instances. Learning in such an imbalanced setting is challenging as the low-frequency classes can be easily overwhelmed by high-frequency ones. Without considering this situation, CNNs will suffer from significant performance degradation.

\begin{figure*}[ht]
\centering
\subfloat[Comparison on ImageNet-LT for long-tailed image classification.]{
    \includegraphics[width=0.48\textwidth]{Figs/gpaco_lt.pdf}%
}
\hspace{0.05in}
\subfloat[Comparison on ADE20K for semantic segmentation.]{
    \vspace{-0.2in}
    \includegraphics[width=0.48\textwidth]{Figs/gpaco_ade20k.pdf} %
}
\vspace{0.05in}
\subfloat[Comparison with MAE \cite{he2022masked} ViT models on full ImageNet and out-of-distribution robustness.]{
    \begin{tabular}{lccccc}
    \toprule
        Models & ImageNet($\uparrow$) & ImageNet-C(mCE $\downarrow$) &ImageNet-C(rel. mCE $\downarrow$) &ImageNet-R($\uparrow$) &ImageNet-S($\uparrow$) \\
        \midrule
        ViT-B &+0.4 &-1.9 &-2.6 &+1.8 &+3.3\\
        \midrule
        ViT-L &+0.3 &-1.7 &-2.4 &+0.0 &+2.8\\
        \bottomrule
        \end{tabular}
}
\caption{\textbf{GPaCo demonstrates impressive performance on imbalanced and balanced data.} (a) shows that GPaCo achieves state-of-the-art on long-tailed classification. GPaCo benefits semantic segmentation task and significant improvement is observed on ADE20K in (b). In (c), top-1 accuracy are reported for full ImageNet, ImageNet-R, and ImageNet-S. mCE and rel. mCE are used for ImageNet-C. Compared with MAE models, GPaCo enjoys better generalization ability and stronger robustness on ImageNet and its variants.}
\label{fig:comparison}
\end{figure*}

Contrastive learning \cite{DBLP:conf/icml/ChenK0H20, DBLP:conf/cvpr/He0WXG20, DBLP:journals/corr/abs-2003-04297, DBLP:conf/nips/GrillSATRBDPGAP20, DBLP:conf/nips/CaronMMGBJ20} is a major research topic due to its success in self-supervised representation learning. Khosla~\cite{DBLP:conf/nips/KhoslaTWSTIMLK20} extend non-parametric contrastive loss into non-parametric supervised contrastive loss by leveraging label information, which trains representation in the first stage and learns the linear classifier with the fixed backbone in the second stage. Though supervised contrastive learning works well in a balanced setting, for imbalanced datasets, our theoretical analysis shows that high-frequency classes will have a higher lower bound of loss and contribute much higher importance than low-frequency classes when equipping it in training.
This phenomenon leads to model bias on high-frequency classes and increases the difficulty of imbalanced learning.
As shown in Fig.~\ref{fig:gradient}, when the model is trained with supervised contrastive loss on ImageNet-LT, the gradient norm varying from the most frequent class to the least one is rather steep. In particular, the gradient norm dramatically decreases for the top 200 most frequent classes.

Previous work \cite{DBLP:journals/nn/BudaMM18,DBLP:conf/cvpr/HuangLLT16,DBLP:conf/cvpr/CuiJLSB19, he2009learning,chawla2002smote, shen2016relay, DBLP:conf/nips/RenYSMZYL20, DBLP:conf/iclr/KangXRYGFK20, DBLP:journals/corr/abs-2010-01809, DBLP:journals/corr/abs-2101-10633, DBLP:conf/nips/TangHZ20, DBLP:journals/corr/abs-2101-10633, Zhong_2021_CVPR, cui2022region} explored to rebalance in traditional supervised cross-entropy learning. In this paper, we tackle the above mentioned imbalance issue in supervised contrastive learning and make use of contrastive learning for long-tailed recognition.

\begin{figure}[t]
	\begin{center}
		\includegraphics[width=0.98\linewidth]{Figs/gradient_norm.pdf}
		\caption{\textbf{Rebalance in contrastive learning.} We collect the average L2 norm of the gradient of weights in the last classifier layer on ImageNet-LT. Category indices are sorted by their image counts. The gradient norm varying from the most frequent class to the least one is steep for supervised contrastive learning \cite{DBLP:conf/nips/KhoslaTWSTIMLK20}. In particular, the gradient norm dramatically decreases for the top 200 most frequent classes. Trained with PaCo, the gradient norm is better balanced.}
		\label{fig:gradient}
	\end{center}
	\vspace{-0.2in}
\end{figure}

To rebalance in supervised contrastive learning, we introduce a set of parametric class-wise learnable centers into supervised contrastive learning. We name our algorithm \textbf{Parametric Contrastive Learning (PaCo)} shown in Fig.~\ref{fig:paco_psum} (a). With such a simple and yet effective operation, we theoretically prove that the optimal values for the probability that two samples are a true positive pair (belonging to the same class), varying from the most frequent class to the least frequent class, are more balanced. Thus their lower bound of loss values are better organized. This phenomenon means the model takes more care of low-frequency classes, making the PaCo loss benefit imbalanced learning. Fig.~\ref{fig:gradient} shows that, with our PaCo loss in training, gradient norm varying from the most frequent class to the least one are moderated better than supervised contrastive learning, which matches our analysis.

Further, we analyze the PaCo loss under a balanced setting. Our analysis demonstrates that with more samples clustered around their corresponding centers in training, the PaCo loss increases the intensity of pushing samples of the same class close, which benefits hard examples learning.

MoCo \cite{DBLP:conf/cvpr/He0WXG20} enables small mini-batch training for self-supervised contrastive learning with a momentum encoder and a queue. \cite{chen2021exploring} claims that it is the ``stop-gradient" but not the momentum encoder that is necessary to avoid collapsing solutions for self-supervised learning. We examine the effects of each component in PaCo including augmentation strategy, loss function (relation to multi-task), momentum encoder and queue size. Simplifying it to \textbf{Generalized Parametric Contrastive Learning (GPaCo)} by removing the momentum encoder boosts model performance and robustness. Moreover, GPaco demonstrates its great generality with various tasks in Fig~\ref{fig:comparison}.

Finally, we conduct experiments on imbalanced data including long-tailed version of CIFAR \cite{cb-focal, DBLP:conf/nips/CaoWGAM19}, ImageNet \cite{Liu_2019_CVPR}, Places \cite{Liu_2019_CVPR} and iNaturalist 2018 \cite{van2018inaturalist}. Experimental results show that we create a new record for long-tailed recognition.
On balanced data, We testify the effectiveness of GPaCo on full ImageNet \cite{imagenet} and CIFAR \cite{krizhevsky2009learning}. Compared with MAE models, we achieve better generalization ability and stronger robustness. With GPaCo loss for semantic segmentation, obvious improvements are obtained on popular benchmarks including ADE20K \cite{zhou2017scene}, COCO-Stuff \cite{caesar2018coco}, PASCAL Context \cite{mottaghi2014role} and Cityscapes \cite{cordts2016cityscapes}.
Our key contributions are as follows.
\begin{itemize}
	\item We identify the shortcoming of supervised contrastive learning under an imbalanced setting -- it tends to bias high-frequency classes.
	\item We extend supervised contrastive loss to the PaCo loss, which is more friendly to imbalanced learning, by introducing a set of parametric class-wise learnable centers.
	\item We examine the necessary of components in PaCo and simplify PaCo to GPaCo, observing that the momentum encoder can hurt model performance and should be removed.
	\item GPaCo can benefit the training on imbalanced data and balanced data varying from CNNs to vision transformers. Experiments on tasks {\it e.g.}, long-tailed classification, full ImageNet/CIFAR classifcation, out-of-distribution robustness, and semantic segmentation demonstrate the generality of GPaCo.
\end{itemize}

\section{Related Work}

\noindent{\bf Re-sampling/re-weighting.}
The most classical way to deal with long-tailed datasets is to over-sample low-frequency class images \cite{shen2016relay, zhong2016towards, buda2018systematic, byrd2019effect}
or under-sample high-frequency class images \cite{he2009learning, japkowicz2002class,buda2018systematic}. However, Oversampling can suffer from heavy over-fitting to low-frequency
classes especially on small datasets. For under-sampling, discarding a large portion of high-frequency class data inevitably causes degradation of the generalization ability of CNNs. Re-weighting \cite{huang2016learning, huang2019deep,wang2017learning,ren2018learning,shu2019meta,jamal2020rethinking} the loss functions is an alternative way to rebalance by either enlarging weights on more challenging and sparse classes or randomly ignoring gradients from high-frequency classes \cite{tan2020eql}. However, with large-scale data, re-weighting makes CNNs difficult to optimize during training \cite{huang2016learning, huang2019deep}.

\vspace{+0.1in}
\noindent{\bf One/two-stage Methods.}
Since deferred re-weighting and re-sampling were proposed by Cao ~\cite{DBLP:conf/nips/CaoWGAM19}, Kang~\cite{DBLP:conf/iclr/KangXRYGFK20} and Zhou~\cite{zhou2019bbn} observed re-weighting or re-sampling strategies could benefit classifier learning while hurting representation learning. Kang~\cite{DBLP:conf/iclr/KangXRYGFK20} proposed to decompose representation and classifier learning. It first trains the CNNs with uniform sampling, and then fine-tune the classifier with class-balanced sampling while keeping parameters of representation learning fixed. Zhou~\cite{zhou2019bbn} proposed one cumulative learning strategy, with which they bridge representation learning and classifier re-balancing.

The two-stage design is not for end-to-end frameworks.
Tang~\cite{DBLP:conf/nips/TangHZ20} analyzed the reason from the perspective of causal graph and concluded that the bad momentum causal effects played a vital role.
Cui ~\cite{DBLP:journals/corr/abs-2101-10633} proposed residual learning mechanism to address this issue.

\vspace{+0.1in}
\noindent{\bf Non-parametric Contrastive Loss.}
\label{Sec:contrastive_learning}
Contrastive learning \cite{DBLP:conf/icml/ChenK0H20, DBLP:conf/cvpr/He0WXG20, DBLP:journals/corr/abs-2003-04297, DBLP:conf/nips/GrillSATRBDPGAP20, DBLP:conf/nips/CaronMMGBJ20} is a framework that learns similar/dissimilar representations from data that are organized into similar/dissimilar pairs. An effective contrastive loss function, called InfoNCE \cite{DBLP:journals/corr/abs-1807-03748}, is
\begin{equation}
\mathcal{L}_{q, k^+, \{k^-\}} = -\log \frac{\exp(q{\cdot}k^+ / \tau)}{\exp(q{\cdot}k^+ / \tau) + {\displaystyle\sum_{k^-}}\exp(q{\cdot}k^-  / \tau)},
\label{eq:infonce}
\end{equation}
where $q$ is a query representation, $k^+$ is for the positive (similar) key sample, and $\{k^-\}$ denotes negative (dissimilar) key samples. $\tau$ is a temperature hyper-parameter. In the {instance discrimination} pretext task \cite{DBLP:conf/cvpr/WuXYL18} for self-supervised learning, a query and a key form a positive pair if they are data-augmented versions of the same image. It forms a negative pair otherwise.

Traditional cross-entropy with linear fc layer weight $w$ and true label $y$ among $n$ classes is expressed as
\begin{equation}
\mathcal{L}_{cross-entropy} = -\log \frac{\exp(q{\cdot} w_{y})}{\sum_{i=1}^{n} \exp(q{\cdot}w_{i})}.
\label{eq:cross-entropy}
\end{equation}

Compared to it, InfoNCE does not get involved with parametric learnable parameters.
To distinguish our proposed parametric contrastive learning from previous ones, we treat the InfoNCE as a non-parametric contrastive loss following \cite{wu2018unsupervised}.

Chen~\cite{DBLP:conf/icml/ChenK0H20} used self-supervised contrastive learning SimCLR to first match the performance of a supervised ResNet-50 with only a linear classifier trained on self-supervised representation on full ImageNet.
He~\cite{DBLP:conf/cvpr/He0WXG20} proposed MoCo and Chen ~\cite{DBLP:journals/corr/abs-2003-04297} extended MoCo to MoCo v2, with which small batch size training can also achieve competitive results on full ImageNet \cite{imagenet}.
In addition, many other methods \cite{DBLP:conf/nips/GrillSATRBDPGAP20, DBLP:conf/nips/CaronMMGBJ20} are also proposed to further boost performance.


\section{Introduction}

Anomaly detection is the task of classifying patterns that depict abnormal behavior. Outliers can arise due to (human/equipment) errors, faulty systems, and others. Anomaly detection is well-suited for unbalanced data, where the ideal scenario is to predict the behavior of the minority class. There are numerous applications in detecting default on loans, fraud detection, and network intrusion detections. An anomaly detection algorithm can work in Unsupervised, Supervised, or hybrid mode.

There are different types of anomalies described as follows.
\begin{itemize}
\item Point Anomaly: the algorithm decide a single instance as an anomaly concerning the entire data set.
\item Contextual Anomaly: a data instance can be anomalous based on the context (attributes and position in the stream) and proximity of the chosen anomaly. This anomaly type is ideal for multivariate data, e.g. in the snapshot reading of a machine, an attribute of a single data point may seem abnormal but can be normal behavior based on consideration of the entire data.
\item Collective Anomaly: the algorithm decide a set of data points that are anomalies as a group, but individually these data points exhibit normal behaviors.
\end{itemize}

Anomaly detection algorithms can operate in the following setting:
\begin{itemize}
\item Static: These algorithms work in static datasets. Every item is loaded into memory at one time to perform computation.
\item Online: These algorithms work in real-time data streams. Items are incrementally loaded into memory and processed in chunks.
\item Static + Online: The model may operate in two stages as initial parameters get estimated in the static setting. The parameters are incrementally updated as more data arrives. Our work is of this type.
\end{itemize}

PEWMA was introduced in the work~\cite{Carter2012} for online anomaly detection on univariate time series. Drawing inspiration from their work, we have provided extensions to support real-time anomaly detection of a multivariate data stream.

\footnote{Source code: \url{https://github.com/kenluck2001/anomalyMulti}, Blog: \url{https://kenluck2001.github.io/blog_post/real-time_anomaly_detection_for_multivariate_data_stream.html}}

\section{Background}
An anomaly detection algorithm can identify outliers in several signal changes in time-dependent data.
Signal changes are common in time-dependent data. They include abrupt transient shift, abrupt distributional shift, and gradual distributional shift~\cite{Carter2012} labeled as "A", "B", and "C"  in Figure~\ref{anomalytype} respectively.

\begin{figure}[H]
\centering
\includegraphics[scale=0.45]{anomaly-types-timeseries.png}
\caption{Different types of signal changes: abrupt transient, abrupt distributional shift, and gradual distributional shift~\cite{Carter2012} (from left to right). }
\label{anomalytype}
\end{figure}

Online algorithms are useful for real-time applications, as they operate incrementally on data streams. These algorithms incrementally receive input and decide based on an updated parameter that conveys the current state of the data stream. This philosophy contrasts with offline algorithms that assume the entire data is available in memory. The issue with an offline algorithm is that the data must fit in memory. The online algorithm should be both time and space-efficient.

Anomaly detection algorithm can work in modes such as diagnosis and accommodation~\cite{hodge2004}. Firstly, the diagnosis method finds the outlier in the data and removes it from the data sample to avoid skewing the distribution. This method is applicable when the distribution of expected behaviors is known. The outliers get excluded when the estimation of the parameters of the distribution~\cite{hodge2004}. Secondly, the accommodation method finds the outliers in the data and includes estimating the parameters of the statistical model. The accommodation method is suitable for data streams that account for the effect of concept drift~\cite{Ditzler2013}.

Muth~\cite{muth60} laid the foundation for exponential smoothing by showing that it provides optimal estimates using random walk with some noise. Further works were done to provide a statistical framework for exponential smoothing leading to the creation of linear models~\cite{boxjen76, roberts82}. Unfortunately, this does apply to nonlinear models. Yule postulated a formulation of time series as a realization of a stochastic process~\cite{yule27}. Exponential Weighted Moving Average (EWMA) is ideal for keeping a set of running moments in the data stream. EWMA is a smoothing technique that adds a forgetting parameter to modify the influence of a recent item in the data stream as shown in Equation~\ref{emwa_equation}. This smoothing causes volatility in abrupt transient changes and is unfit for distribution shifts.

\begin{equation}
\label{emwa_equation}
\mu_{t+1} = \alpha\mu_{t-1} + (1 - \alpha) X_{t}
\end{equation}

EWMA limitations motivated the discovery of Probabilistic Exponentially Weighted Moving Average (PEWMA). PEWMA~\cite{Carter2012} improves on EMWA by adding parameter which includes the probability of the data in the model as shown in Equation~\ref{pewma_equation}. PEWMA works for every shift including abrupt transient shift, abrupt distributional shift, and gradual distributional shift respectively. PEWMA and EWMA make use of a damped window~\cite{Salehi2018}.

\begin{equation}
\label{pewma_equation}
\mu_{t+1} = \alpha(1 - \beta P_{t}) \mu_{t-1} + (1 - \alpha(1 - \beta P_{t}) ) X_{t}
\end{equation}

\section{Method}
Our formulation provided an implementation of the online covariance matrix in Subsection~\ref{online-covariance-matrix}, alongside an online inverse covariance matrix based on Sherman$-$Morrison formula in Subsection~\ref{online-inverse-covariance-matrix}, and PEWMA in Subsection~\ref{prob-exp-weighted-avg}.

Our implementation of the online covariance matrix builds on work~\cite{Igel2006}. We simplify the algorithm by ignoring the details of evolutionary computation in the paper. Our work adapted evolution as described in the paper~\cite{Igel2006} as a transition from one generation to the next; is equivalent to moving from one state to another state. This is analogous to how online algorithms work with dynamic changes as new data enters the stream. Cholesky decomposition is used extensively in the algorithms.

\subsection{Probabilistic Exponentially Weighted Moving Average (PEWMA)}
\label{prob-exp-weighted-avg}

PEWMA~\cite{Carter2012} algorithm works in the accommodation mode. The routine shown in Algorithm [1] allows for concept drift~\cite{Ditzler2013}, which occurs in data streams by updating the set of parameters that convey the state of the stream.

\begin{algorithm}
\caption{Probabilistic Exponential Weighted Moving Average~\cite{Carter2012}}
\begin{algorithmic}

\REQUIRE $X_{t},  \hat{X_{t}}, \hat{\alpha_{t}}, T, t$
\ENSURE $P_{t}, \hat{X_{t+1}}, \hat{\alpha_{t+1}} $

\begin{verbatim}
//incremental Z score
\end{verbatim}
\STATE $Z_{t} \leftarrow \frac{ X_{t} - \hat{X_{t}} }  {\hat{\alpha_{t}}}$

\begin{verbatim}
//probability density function
\end{verbatim}

\STATE $P_{t} \leftarrow     \frac{ Z_{t} }  {  \sqrt{2\pi} }   e^{ \frac{ Z_{t} }  { 2 } }$

\IF{$t < T$}

\begin{verbatim}
//increment standard deviation (training phase)
\end{verbatim}
\STATE $\alpha_{t} \leftarrow 1 - 1/t$
\ELSE

\begin{verbatim}
//increment standard deviation
\end{verbatim}
\STATE $\alpha_{t} \leftarrow (1 - \beta P_{t} ) \alpha$
\ENDIF

\begin{verbatim}
//moving average
\end{verbatim}
\STATE $s_{1} \leftarrow \alpha_{t} s_{1} + (1 - \alpha_{t} )X_{t}$
\STATE $s_{2}  \leftarrow \alpha_{t} s_{2} + (1 - \alpha_{t} )X_{t}^2$

\begin{verbatim}
//incremental mean
\end{verbatim}
\STATE $\hat{X_{t+1}} \leftarrow s_{1}$

\begin{verbatim}
//incremental standard deviation
\end{verbatim}
\STATE $\hat{\alpha_{t+1}} \leftarrow \sqrt{ s_{2} - s_{1}^2  }$

\label{anomalgo }
\end{algorithmic}
\end{algorithm}

The parameters of the anomaly detection algorithm consist of $X_{t}$ the current data, $\mu_{t}$ the mean of the data, $\hat{X_{t}}$ is the mean of the data, $\hat{\alpha_{t}}$ the current standard deviation, $P_{t}$ the probability density function, $\hat{X_{t+1}}$ the mean of the next data (incremental aggregate), $\hat{\alpha_{t+1}}$ the next standard deviation (incremental aggregates), $T$ the data size, and $t$ a point in $T$. Initialize the process by setting the initial data for training the model $s_{1} = X_{1}$ and $s_{2} = X_{1}^{2}$.

Our work made use of the following parameters $\alpha = 0.98, \beta = 0.98$, and $\tau = 0.0044$. These thresholds are chosen based on the criteria that outliers are $\geq 3$ times the standard deviation in normally distributed data.

\subsection{Online Covariance matrix}
\label{online-covariance-matrix}
\begin{enumerate}
\item Estimate covariance matrix for initial data, $X \in R^{n \times m}$.
Initial covariance matrix, $C$ where $C \in R^{n \times m}$, $n$ is the number of samples, $m$ is the number of dimensions as shown in Equation~\ref{cov_equation}.

\begin{equation}
\label{cov_equation}
C = X * {X}^T
\end{equation}

\item Perform Cholesky factorization on the initial covariance matrix (positive-definite), $C$ as shown in Equation~\ref{cov_chol_equation}.
\begin{equation}
\label{cov_chol_equation}
C_t = A_t * {A_t}^T
\end{equation}

\item The updated covariance in the presence of new data is equivalent to the weighted average of the past covariance without the updated data and covariance of the transformed input as shown in Equation~\ref{xxincr_cov_chol_equation}.

\begin{equation}
\label{xxincr_cov_chol_equation}
C_{t+1} = \alpha * C_t + \beta * v_t * {v_t}^T
\end{equation}

Where $v_t = A_t * z_t$ and $z_t \in R^m$ is understood in our implementation is the current data. $\alpha$ and $\beta$ are positive scalar values.

\item Increment the Cholesky factor of the covariance matrix as shown in Equation~\ref{incr_cov_chol_coeff}.

\begin{equation}
\label{incr_cov_chol_coeff}
A_{t+1} = \sqrt{\alpha} * A_t + \frac{\sqrt{\alpha}}{\Big\|z_t \Big\|^2} * \left( \sqrt{1 + \frac{\beta * \Big\|z_t \Big\|^2}{\alpha}} - 1 \right) * v_t * z_t
\end{equation}

\item There are difficulties with setting the values of $\alpha$ and $\beta$ respectively. $\alpha + \beta = 1$ as an explicit form of exponential moving average coefficients. The author chose to set the values of $\alpha$, $\beta$ using the statistics of the data stream as shown in Equation~\ref{incr_cov_chol_coeff2}.

The parameters are set as $\alpha = {C_{a}}^2$, $\beta = 1 - {C_{a}}^2$ and $n$ is the size of the original data in the static settings.
Where ${C_{a}} = \sqrt{1 - C_{cov}}$ and $C_{cov} = \frac{2}{{n^2}+6}$.

\begin{equation}
\label{incr_cov_chol_coeff2}
A_{t+1} = {C_{a}} * A_t + \frac{{C_{a}}}{\Big\|z_t \Big\|^2} * \left( \sqrt{1 + \frac{(1 - {C_{a}}^2) * \Big\|z_t \Big\|^2}{{C_{a}}^2}} - 1 \right) * v_t * z_t
\end{equation}

\end{enumerate}

\subsection{Online Inverse Covariance matrix}
\label{online-inverse-covariance-matrix}
\begin{enumerate}
\item Estimate covariance matrix for initial data, $X \in R^{n \times m}$.
Initial covariance matrix, $C$ where $C \in R^{n \times m}$, $n$ is the number of samples, $m$ is the number of dimensions as shown in Equation~\ref{inverse_cov_equation}.

\begin{equation}
\label{inverse_cov_equation}
C = X * {X}^T
\end{equation}

Inverse the covariance matrix, $C^{-1}$ as shown in Equation~\ref{inverse_cov_equation_real}.

\begin{equation}
\label{inverse_cov_equation_real}
C^{-1} = \left( X * {X}^T \right)^{-1}
\end{equation}

\item Perform Cholesky factorization on initial covariance matrix, $C$ as shown in Equation~\ref{inverse_cov_chol_equation_real}.
\begin{equation}
\label{inverse_cov_chol_equation_real}
C_t = A_t * {A_t}^T
\end{equation}

\item Increment the Cholesky factor of the covariance matrix

\begin{equation}
\label{incr_cov_chol_equation1}
C_{t+1}^{-1} = (\alpha * C_t + \beta * v_t * {v_t}^T)^{-1}
\end{equation}

\begin{equation}
\label{incr_cov_chol_equation2}
C_{t+1}^{-1} = \alpha^{-1} * (C_t + \frac{\beta * v_t * {v_t}^T}{\alpha})^{-1}
\end{equation}

Let us fix, $\hat{v_t} = \frac{\beta * v_t}{\alpha}$. The resulting simplification using Sherman$-$Morrison Formula reduces the expression to

\begin{equation}
\label{incr_cov_chol_equation3}
C_{t+1}^{-1} = \frac{1}{\alpha} * \left({{C_t}^{-1}} - \frac{{{C_t}^{-1}} * \hat{v_t} * {v_t}^T * {{C_t}^{-1}}}{1 + (\hat{v_t} * {{C_t}^{-1}} * {v_t}^T)} \right)
\end{equation}
\end{enumerate}

\subsection{Online Multivariate Anomaly Detection}

The probability density function utilizes ideas from hypothesis testing for Deciding on a threshold to set the confidence level for determining the acceptance and rejection regions of the Gaussian distribution curve.

\begin{enumerate}
\item Use the covariance matrix, $C_{t+1}$ and inverse covariance matrix, ${C_{t+1}}^{-1}$.

\item We increment the mean vector, $\mu$ as new data arrives. It is possible to simplify the Covariance matrix, $C$, which will capture a number of the dynamics of the system. Let $n$ represent the current count of data before new data has arrived. Also, $\hat{x}$: is the new data, $\mu_{t+1}$: moving average as shown in Equation~\ref{incr_mean}.
\begin{equation}
\label{incr_mean}
\mu_{t+1} = \frac{(n * \mu_t) + \hat{x}}{n+1}
\end{equation}

\item Set a threshold to determine the acceptance and rejection regions. Items in the acceptance region are considered to be normal behavior as shown in Equation~\ref{pdf_equation}.
\begin{equation}
\label{pdf_equation}
p(x)=\frac{1}{\sqrt{(2\pi)^m|C|}} \exp\left(-\frac{1}{2}(x-\mu)^T{C}^{-1}(x-\mu) \right)
\end{equation}
Where $\mu$ is mean vector, $C$ is covariance matrix, $|C|$ is the determinant of $C$ matrix, $x \in R^{m}$ is data vector, and $m$ is the dimension of $x$ respectively.

\end{enumerate}

\section{Experiment}
Furthermore, we have provided a set of detailed experiments on the proposed algorithms in different realistic scenarios. However, we maintain the statistical framework provided by the work~\cite{Carter2012} with theoretical guarantees.

We have experimented to determine the usefulness of our algorithm by creating a simulation with 10000000 random vectors with dimensions of 15. The repeated trial shows that our algorithm is not sensitive to initialization seeds and dimensions of the matrix. This requirement was a deciding factor in the choice of the evaluation metric as shown in Equation~\ref{aad_equation}. We have provided more information on the metric in Section~\ref{result-analysis}.

Our experiment will check the effect of varying the size of the initial static window versus the update window as shown in Subsection~\ref{experiment-1} and Subsection~\ref{experiment-2}.

\begin{figure}[H]
\centering
\includegraphics[scale=0.45]{chart1.png}
\caption{Compare the threshold of static vs incremental impact performance of anomaly detection (Version 1)}
\label{experimentchart1}
\end{figure}

\subsection{Experiment 1}
\label{experiment-1}
We evaluate the trade-off between the static window and the update window. The experiment setup is as follows:

\begin{itemize}
\item Split the data into 5 segments train on 1st segment(static), update covariance on 2nd (online), compare with static covariance, and calculate the error.

\item Train on 1, 2 segments (static), update covariance on 3rd (online), compare with static covariance and calculate the error.

\item Train on 1, 2, 3 segments (static), update covariance on 4th (online), compare with static covariance and calculate the error.

\item Train on 1, 2, 3, 4 segments (static), update covariance on 5th (online), compare with static covariance and calculate the error.

\end{itemize}

Figure~\ref{experimentchart1} contains the experimental result.

\begin{figure}[H]
\centering
\includegraphics[scale=0.45]{chart2.png}
\caption{Compare the threshold of static vs incremental impact performance of anomaly detection (Version 2)}
\label{experimentchart2}
\end{figure}

\subsection{Experiment 2}
\label{experiment-2}
The experiment setup is as follows:
\begin{itemize}
\item Split the data into 5 segments.

\item Train on 1st segment(static), update covariance on remaining segments (2,3,4,5) (online), compare with static covariance and calculate error on segments (2,3,4,5)

\item Train on 1, 2 segments (static), update covariance on remaining segments (3,4,5) (online), compare with static covariance and calculate error on segments (3,4,5)

\item Train on 1, 2, 3 segments (static), update covariance on remaining segments (4,5) (online), compare with static covariance and calculate error on segments (4,5)

\item Train on 1, 2, 3, 4 segment(static), update covariance on remaining segments (5) (online), compare with static covariance and calculate error on segments (5)
\end{itemize}

Figure~\ref{experimentchart2} contains the experimental result.

\section{Result Analysis}
\label{result-analysis}
Our random matrices get flattened to a vector and utilized as input. The length of the flattened vector is used as a normalization factor to make the loss metric that is agnostic to the dimension of the matrix. The loss function used in the evaluation is Absolute Average Deviation (AAD) because it gives a tighter bound on the error compared to mean squared error (MSE) or mean absolute deviation (MAD)  as shown in Equation~\ref{aad_equation}. We take the average of the residuals divided by the ground truth for every sample in our evaluation set. If the residual is close to zero, we contribute almost nothing to the measure. On the contrary, if the residual is high, we want to know the difference from the ground truth.

\begin{equation}
\label{aad_equation}
AAD = \sum_{i=1}^{n} \left| \frac{\hat{Y_i} - Y_i}{Y_i} \right|
\end{equation}

Where $\hat{Y_i}$ is the predicted value, $Y_i$ is the ground truth, and $n$ is the length of the flattened matrix.

We can observe that building your model with more data in the init (static) phase leads to lower errors compared to having fewer data in the init phase and using more of the data for an update. The observation matches our intuition because when you operate in an online mode, you tend to use smaller storage space. However, there is still a performance trade-off when compared to batch mode.

The error at the beginning of our training is significant in both charts. This insight shows that rather than performing the expensive operation of converting a covariance matrix to have the property of positive definiteness, it is better to use random matrices that are positive definite. More data would help us get to convergence as more data arrives.

The success of the experiments has given us the confidence that our multivariate anomaly detection algorithm would have similar characteristics to the univariate case described in the work~\cite{Carter2012}.

\section{Conclusion}
There is no generic anomaly detection that works for every possible task. The underlying assumption in this work is that the features in use capture relevant information about the underlying dynamic of the system. Our proposed implementation is an anomaly detection algorithm for handling multivariate streams even with challenging shifts. In future work, we will make extensions to support non-stationary distributions in multivariate data streams.

\bibliographystyle{ACM-Reference-Format}