DRO-LT [1]}, which enforces an embedding margin \(\epsilon _y \propto {\mathbb {P}(y)}^{-1/2}\) .

For ELM, we set the logit margin \(\Delta _{yy^{\prime }} = \log \frac{\mathbb {P}( y^{\prime } )}{\mathbb {P}( y )}\) ,
following the LogAdj loss;
thus, ELM imposes additional regularisers over this method.
We detail the choice of \(\alpha _y\)  in the Appendix.
One- versus multi-stage methods
We remark here that
DRO-LT is a “multi-stage” method, as it requires first obtaining centroid estimates \(\mu _y\)  from CE training;
training using these, plus the DRO-LT regulariser (REF );
and finally training a balanced classifier on the resulting embeddings.
By contrast, all other baselines — and the proposed ELM — are “one-stage” methods.
Thus, for an equitable comparison, we consider a “one-stage” version of DRO-LT, which does not have a separate estimation of \(\mu _y\) , nor retraining of a linear model on the learned embeddings.
For completness, we additionally quote the results of
multi-stage DRO-LT from [1]}.
As another multi-stage baseline, we report the results of
post-hoc weight normalisation [3]} on the CE solution.
An important goal of our experiments is to understand the performance (balanced accuracy) we can get from training in one stage.
This helps understand losses for long-tailed learning without being occluded by benefits gained from the more generally applicable augmented procedures such as balanced sampling, and fine-tuning the classifier layer.
<FIGURE>
Results and analysis
Table REF  presents the results on all datasets.
We make some key observations.
Logit and embedding margins help.
In keeping with prior work, approaches that enforce a logit margin, e.g., LDAM [4]}, and LogAdj [5]}, [6]}, [7]},
perform significantly better than CE.
Similarly, one-stage CE + DRO-LT,
which enforces an embedding margin,
consistently improves over CE.
Compared to these techniques, combining both logit and embedding margins
yields improvements, as shown by the performance of ELM,
intuitively owing to it encouraging pulling together of similar embeddings.
Interestingly, even when compared to a multi-stage version of DRO-LT, the performance of our one-stage ELM remains favourable, with only a small difference across all datasets.
Breakdown of performance.
The above illustrates the ELM can improve the overall tradeoff between rare and dominant labels.
For a more fine-grained understanding,
following [3]},
we break down the labels into three groups,
termed “Head” (labels with \(\ge 100\)  training samples),
“Torso” (\([ 20, 100)\)  samples), and
“Tail” (\(< 20\)  samples).
Figure REF  reveals that, per [6]},
LogAdj achieves gains on both the Torso and Tail groups, at the mild expense of performance on the Head group.
Further adding an embedding margin via ELM yields gains on the Torso and Tail groups.
Interestingly, on the challenging iNaturalist data, there are gains on the Head group as well.
<FIGURE><FIGURE><FIGURE>Analysis of logit margins.
We analyse the distribution of logit margins \(\gamma ( x, y ) \stackrel{.}{=}f_y( x ) - \max _{y^{\prime } \ne y} f_{y^{\prime }}( x )\)  on CIFAR100-LT.
We pick three labels from the Head, Torso, and Tail slices,
and compare the margin distributions for the cross-entropy loss (CE),
the logit adjustment (LogAdj) loss, the proposed ELM, and DRO-LT.
Figure REF  visualises these margin distributions.
As expected, logit adjustment tends to trade off performance on dominant classes, while significantly increasing margins on rare classes.
Interestingly,
from Figure REF ,
ELM strongly controls the margin distribution, which becomes less variable.
Further, on the tail label, we see that ELM significantly shifts the mode of the margins over cross-entropy and LogAdj.
As such logit margins directly control generalisation performance [10]}, [11]},
this lends further credence to ELM improving classification performance as also suggested by Proposition REF .
Analysis of embeddings.
We conduct a similar analysis on the distances between the learned embeddings.
For instances \(x\)  with label \(y\) ,
Figure REF  visualises the maximum intra-class distances \(d_{\rm max}( x ) \stackrel{.}{=}\max _{x^+\in S_y} \Vert  \Phi ( x ) - \Phi ( x^+) \Vert _2\) .
The distances are normalised by the maximal embedding norm \(\max _{x \in S} \Vert  \Phi ( x ) \Vert _2\) .
We observe that DRO-LT increases the intra-class distances slightly compared to CE, owing to contrasting samples within the same class.
By contrast, the pull part of ELM ensures that these distances remain small, thus encouraging tighter clusters, especially for tail classes.
To visually inspect the learned embeddings,
we create 2D tSNE [12]} visualisations of the embeddings learned by LodAdj, ELM, and DRO-LT.
Figure REF  illustrates these embeddings for a sample of
classes from the previously created Head, Torso and Tail buckets.
ELM is seen to produce more compact and separated embeddings compared to logit-adjusted cross-entropy minimisation and DRO-LT.
For additional experiments and ablations, we refer the reader to the Appendix.

Discussion and Future Work
The ELM method presents a unified approach to enforce margins in logit space, and regularise the distribution of embeddings.
Our argument for the value of such regularisation is instructive, and
such regularisation implies better generalisation as shown in Proposition REF .
Yet a key question remains elusive:
can we improve the performance of the tail group without trading off the performance of the head?
The breakdown of per-group accuracies in Figure REF , especially on the challenging iNaturalist problem,
offers some hope of this possibility.
Exploring conditions under which this is possible would be a worthwhile direction for future work.
More broadly, studying the efficacy of ELM in fairness settings with under-represented samples,
to ensure it does not introduce unforeseen biases,
is another important direction.

ELM: Embedding and Logit Margins for Long-Tail Learning
Supplementary Material


Experiment setup: hyperparameters
Architecture and optimisation hyperparameters
To facilitate a fair comparison, we use the same setup for all the methods for each dataset.
These settings are summarised in Table REF .
For CIFAR,
we use the standard CIFAR data augmentation procedure used in previous works such as [4]}, [14]}, where 4 pixels are padded on each size and a random \(32 \times 32\)  crop is taken.
Images are horizontally flipped with a probability of 0.5.
For ImageNet and iNaturalist,
we apply the standard data augmentation comprising of random cropping and flipping as described in [15]}.
<TABLE>
Settings for ELM
We detail hyperparameter settings for the proposed ELM.
For all the four datasets considered in §, we set the pull margin to be \(\alpha _y \propto \mathbb {P}(y)^a\) 
for some \(a > 0\) .
This choice allows the ELM to pull embeddings of tail
classes more strongly compared to frequent classes.
Empirically we found that setting \(a= \frac{1}{2}\)  or \(a=1\)  works well for most datasets.
CIFAR10-LT
:
We use \(\alpha _y = \mathbb {P}(y)\) , and set the
regularization parameter \(\lambda = 0.01\) .

CIFAR100-LT
:
We set \(\alpha _y= \sqrt{n_y}\) , and
regularization parameter \(\lambda = 0.01\)  (see (REF )),
where \(n_y\)  denotes the number of training samples in class \(y\) .

ImageNet-LT
:
We set \(\alpha _y = 10 \times \sqrt{\mathbb {P}(y)}\)  and \(\lambda =0.001\) .

iNaturalist
:
We set \(\alpha _y = \sqrt{n_y}\) , and set \(\lambda = 0.01\) .
Based on our investigation, the choice \(\alpha _y = n_y\)  with \(\lambda = 0.01\)  appears to offer good performance across many datasets.
See also §REF  where we show how various choices of \(\alpha _y\)  and \(\lambda \)  affect the test accuracy of ELM.

Experiments: additional results
Additional margin distributions
Figure REF  plots the cumulative margin distributions
(\(\gamma ( x, y ) \stackrel{.}{=}f_y( x ) - \max _{y^{\prime } \ne y} f_{y^{\prime }}( x )\)  for instances \(x\)  with label \(y\) )
for various methods on CIFAR100-LT.
Here, we clearly see a significant gap between ERM and method that enforce a logit margin,
which are in turn bested with those that enforce an embedding margin.
<FIGURE>
Sensitivity to Regularisation Strength
Figure REF  shows how the choice of regularisation strength \(\lambda \)  affects final test set performance of ELM.
When \(\lambda \)  is too large, performance suffers considerably;
when \(\lambda \)  is too small, performance is indistinguishable from that of standard cross-entropy minimisation.
However, for intermediate values of \(\lambda \)  we see some gains, indicating the value of the regulariser.
<FIGURE>
Proof
Proof of Proposition  REF
We start with the definition of \(\Omega _{\mathrm {pull}}(x,y)\) :
\(\Omega _{\mathrm {pull}}(x,y) & =\log \text{$\left[1+\sum _{x^{+}\in S_{y}\backslash \lbrace x\rbrace }e^{\Vert \Phi (x)-\Phi (x^{+})\Vert ^{2}-\alpha _{y}}\right]$}\\& =\log \text{$\left[\frac{1}{|S_{y}|-1}\sum _{x^{+}\in S_{y}\backslash \lbrace x\rbrace }1+\frac{1}{|S_{y}|-1}\sum _{x^{+}\in S_{y}\backslash \lbrace x\rbrace }(|S_{y}|-1)e^{\Vert \Phi (x)-\Phi (x^{+})\Vert ^{2}-\alpha _{y}}\right]$}\\& \stackrel{(a)}{\ge }\frac{1}{|S_{y}|-1}\sum _{x^{+}\in S_{y}\backslash \lbrace x\rbrace }\log \text{$\left[1+(|S_{y}|-1)e^{\Vert \Phi (x)-\Phi (x^{+})\Vert ^{2}-\alpha _{y}}\right]$}\\& \ge \frac{1}{|S_{y}|-1}\sum _{x^{+}\in S_{y}\backslash \lbrace x\rbrace }\log \text{$\left[(|S_{y}|-1)e^{\Vert \Phi (x)-\Phi (x^{+})\Vert ^{2}-\alpha _{y}}\right]$}\\& =\frac{1}{|S_{y}|-1}\sum _{x^{+}\in S_{y}\backslash \lbrace x\rbrace }\Vert \Phi (x)-\Phi (x^{+})\Vert ^{2}-\alpha _{y}+\log \left(|S_{y}|-1\right),\) 

where at \((a)\)  we use Jensen's inequality i.e., \(\log \left(\frac{1}{m}\sum _{i=1}^{m}f(x_{i})\right)\ge \frac{1}{m}\sum _{i=1}^{m}\log (f(x_{i}))\) .
This implies that
\(\bar{\Omega }_{\mathrm {pull}}(y) & =\frac{1}{|S_{y}|}\sum _{x\in S_{y}}\Omega _{\mathrm {pull}}(x,y)\\& \ge \frac{1}{|S_{y}|(|S_{y}|-1)}\sum _{x\in S_{y}}\sum _{x^{+}\in S_{y}\backslash \lbrace x\rbrace }\Vert \Phi (x)-\Phi (x^{+})\Vert ^{2}-\alpha _{y}+\log \left(|S_{y}|-1\right)\\& =\frac{1}{|S_{y}|(|S_{y}|-1)}\sum _{x,x^{+}\in S_{y}}\Vert \Phi (x)-\Phi (x^{+})\Vert ^{2}-\alpha _{y}+\log \left(|S_{y}|-1\right),\) 

where the last line follows from the fact that \(\Vert \Phi (x)-\Phi (x)\Vert ^{2}=0\) .
Observe that \(\frac{1}{|S_{y}|^{2}}\sum _{x,x^{+}\in S_{y}}\Vert \Phi (x)-\Phi (x^{+})\Vert ^{2}=\frac{2}{|S_{y}|}\sum _{x\in S_{y}}\Vert \Phi (x)-\hat{\mu }_{y}\Vert ^{2}\) 
where \(\hat{\mu }_{y}=\frac{1}{|S_{y}|}\sum _{x\in S_{y}}\Phi (x)\) .
To show this, we will start by expanding the square in \(\frac{2}{|S_{y}|}\sum _{x\in S_{y}}\Vert \Phi (x)-\hat{\mu }_{y}\Vert ^{2}\) .
In the following derivation, it is useful to note that \(\frac{1}{|S_{y}|}\sum _{x\in S_{y}}1=1\) 
is used in many steps, and that \(\frac{1}{|S_{y}|}\sum _{x\in S_{y}}1\) 
is introduced for the purpose of rearranging the expression into a
form that has two nested sums:
\(& \frac{2}{|S_{y}|}\sum _{x\in S_{y}}\Vert \Phi (x)-\hat{\mu }_{y}\Vert ^{2}\\& =\frac{2}{|S_{y}|}\sum _{x\in S_{y}}\left[\Vert \Phi (x)\Vert ^{2}+\Vert \hat{\mu }_{y}\Vert ^{2}-2\Phi (x)^{\top }\hat{\mu }_{y}\right]\\& =\frac{2}{|S_{y}|}\sum _{x\in S_{y}}\Vert \Phi (x)\Vert ^{2}+2\,\bigg \Vert \frac{1}{|S_{y}|}\sum _{x\in S_{y}}\Phi (x)\bigg \Vert ^{2}-\frac{4}{|S_{y}|}\sum _{x\in S_{y}}\Phi (x)^{^{\top }}\left(\frac{1}{|S_{y}|}\sum _{x^{+}\in S_{y}}\Phi (x^{+})\right)\\& =\frac{2}{|S_{y}|^{2}}\sum _{x,x^{+}\in S_{y}}\Vert \Phi (x)\Vert ^{2}+2\,\left(\frac{1}{|S_{y}|}\sum _{x\in S_{y}}\Phi (x)\right)^{\top }\left(\frac{1}{|S_{y}|}\sum _{x^{\prime }\in S_{y}}\Phi (x^{\prime })\right)-\frac{4}{|S_{y}|}\sum _{x\in S_{y}}\Phi (x)^{^{\top }}\left(\frac{1}{|S_{y}|}\sum _{x^{+}\in S_{y}}\Phi (x^{+})\right)\\& =\frac{2}{|S_{y}|^{2}}\sum _{x,x^{+}\in S_{y}}\Vert \Phi (x)\Vert ^{2}+\frac{2}{|S_{y}|^{2}}\sum _{x,x^{+}\in S_{y}}\Phi (x)^{\top }\Phi (x^{+})-\frac{4}{|S_{y}|^{2}}\sum _{x,x^{+}\in S_{y}}\Phi (x)^{^{\top }}\Phi (x^{+})\\& ={\frac{2}{|S_{y}|^{2}}\sum _{x,x^{+}\in S_{y}}\Vert \Phi (x)\Vert ^{2}}-\frac{2}{|S_{y}|^{2}}\sum _{x,x^{+}\in S_{y}}\Phi (x)^{^{\top }}\Phi (x^{+})\\& ={\frac{1}{|S_{y}|^{2}}\sum _{x,x^{+}\in S_{y}}\Vert \Phi (x)\Vert ^{2}+\frac{1}{|S_{y}|^{2}}\sum _{x,x^{+}\in S_{y}}\Vert \Phi (x^{+})\Vert ^{2}}-\frac{2}{|S_{y}|^{2}}\sum _{x,x^{+}\in S_{y}}\Phi (x)^{^{\top }}\Phi (x^{+})\\& {\normalcolor =}\frac{1}{|S_{y}|^{2}}\sum _{x,x^{+}\in S_{y}}\left[\Vert \Phi (x)\Vert ^{2}+\Vert \Phi (x^{+})\Vert ^{2}-2\Phi (x)^{^{\top }}\Phi (x^{+})\right]\\& =\frac{1}{|S_{y}|^{2}}\sum _{x,x^{+}\in S_{y}}\Vert \Phi (x)-\Phi (x^{+})\Vert ^{2}.\) 

It follows that
\(\bar{\Omega }_{\mathrm {pull}}(y) & \ge \frac{2}{(|S_{y}|-1)}\sum _{x\in S_{y}}\Vert \Phi (x)-\hat{\mu }_{y}\Vert ^{2}-\alpha _{y}+\log \left(|S_{y}|-1\right)\\& =\frac{2|S_{y}|}{(|S_{y}|-1)}\sum _{j=1}^{K}\frac{1}{|S_{y}|}\sum _{x\in S_{y}}(\Phi (x)_{j}-\hat{\mu }_{y,j})^{2}-\alpha _{y}+\log \left(|S_{y}|-1\right)\\& =\frac{2|S_{y}|}{(|S_{y}|-1)}\sum _{j=1}^{K}\hat{\mathbb {V}}[\Phi _{j}(x)\mid y]-\alpha _{y}+\log \left(|S_{y}|-1\right).\) 

Proof of Proposition REF  (Generalisation Bound)
Before we give proof for Proposition REF , we present a few
lemmas (Lemmas REF , REF , and
REF ) that will be useful later for proving the proposition.
We start with Lemma REF , a known result that gives a probabilistic
upper bound of the population mean in terms of an empirical variance.
Lemma 3 (Bennett's inequality [16]}) 
 Let \(Z_{1},\ldots ,Z_{n}\)  be i.i.d. random variables
with values in \([0,B]\)  and let \(\delta >0\) . Then, with probability
at least \(1-\delta \)  in \((Z_{1},\ldots ,Z_{n})\) ,
\(\text{$\mathbb {E}Z$} & \le \frac{1}{n}\sum _{i=1}^{n}Z_{i}+\sqrt{\frac{2\hat{\mathbb {V}}[Z]\ln 2/\delta }{n}}+\frac{7B\ln 2/\delta }{3(n-1)}.\) 

We will use Lemma REF  as the starting point for proving our generalisation
bound of the logit-adjusted cross entropy loss.
The logit-adjusted cross entropy loss is a special case of the log loss.
Lemma REF  states that the variance of the log loss is no
larger than the variance of the linear loss.
This observation, together with Lemma REF , will provide
necessary intermediate steps in our main proof for connecting the
variance of the log loss to the proposed pull objective.
Lemma 4 Let \(\ell _{\mathrm {log}}(y,f(x)):=\log \left(1+e^{-yf(x)}\right)\) 
and \(\ell _{\mathrm {lin}}(y,f(x))=-yf(x).\)  Then, for any \(y\in \lbrace -1,1\rbrace \) ,
\(\mathbb {V}_{x|y}[\ell _{\mathrm {log}}(y,f(x))]\le \mathbb {V}_{x|y}[\ell _{\mathrm {lin}}(y,f(x))]\) .

Proof
Let \(s_{y}(z):=\log \left(1+e^{-yz}\right)\)  for \(y\in \lbrace -1,1\rbrace \) . Observe
that \(s^{\prime }_{y}(z)=-\frac{ye^{-yz}}{1+e^{-yz}}\)  so that \(\sup _{z}|s^{\prime }_{y}(z)|\le 1\) .
That is, \(s_{y}\)  is a 1-Lipschitz function i.e., for any \(z,z^{\prime }\in \mathbb {R}\) ,
\(|s_{y}(z)-s_{y}(z^{\prime })|\le |z-z^{\prime }|\) . By definition of variance, for any
real-valued function \(h\) ,
\(\mathbb {V}[h(z)] & =\mathbb {E}[h^{2}(z)]-\mathbb {E}^{2}[h(z)]\\& \le \mathbb {E}[h^{2}(z)].\) 

It follows that
\(\mathbb {V}_{x|y}[\ell _{\mathrm {log}}(y,f(x))] & =\mathbb {V}_{x|y}[s_{y}(f(x))]\\& \stackrel{(a)}{=}\mathbb {V}_{x|y}[s_{y}(f(x))-s_{y}(\mathbb {E}_{x^{\prime }|y}[f(x^{\prime })])]\\& \le \mathbb {E}_{x|y}\left[\left(s_{y}(f(x))-s_{y}(\mathbb {E}_{x^{\prime }|y}[f(x^{\prime })])\right)^{2}\right]\\& \stackrel{(b)}{\le }\mathbb {E}_{x|y}\left[\left(f(x)-\mathbb {E}_{x^{\prime }|y}[f(x^{\prime })]\right)^{2}\right]\\& =\mathbb {E}_{x|y}\left[\left(yf(x)-\mathbb {E}_{x^{\prime }|y}[yf(x^{\prime })]\right)^{2}\right]\\& =\mathbb {V}_{x|y}[\ell _{\mathrm {lin}}(y,f(x))],\) 

where at \((a)\)  we note that adding a constant \(s_{y}(\mathbb {E}_{x^{\prime }|y}[f(x^{\prime })])\) 
does not change the variance, and at \((b)\)  we use the fact that \(s_{y}\) 
is 1-Lipschitz.
Lemma 5 Consider the binary classification case where \(y\in \lbrace -1,1\rbrace \) .
Let \(f(x)\stackrel{.}{=}w^{\top }\Phi (x)+b\in \mathbb {R}\)  be the logit
function for class \(y=1\) . Define
\(\Omega _{\mathrm {cen}}(y):=\mathbb {E}_{x|y}\Vert \Phi (x)-\mu _{y}\Vert ^{2}\) 
where \(\mu _{y}\stackrel{.}{=}\mathbb {E}_{x|y}\Phi (x)\) . Let \(\Omega _{\mathrm {cen}}\stackrel{.}{=}\frac{1}{2}\left[\Omega _{\mathrm {cen}}(-1)+\Omega _{\mathrm {cen}}(1)\right]\) 
be the center loss. Then, for
any \(\Delta _{y}\in \mathbb {R}\) , we have \(\mathbb {V}_{x|y}[\ell _{\mathrm {log}}(y,f(x)+\Delta _{y})]\le \Vert w\Vert ^{2}\mathrm {tr}(C_{y})\)  where \(C_{y}\stackrel{.}{=}\mathbb {E}_{x|y}(\Phi (x)-\mu _{y})(\Phi (x)-\mu _{y})^{\top }.\)

Proof
Let \(\lambda _{\max }(A)\)  be the the maximum eigenvalue of a square
positive definite matrix \(A\) . Consider the variance of the linear
loss as in Lemma REF . Observe that
\(\mathbb {V}_{x|y}[\ell _{\mathrm {lin}}(y,f(x)+\Delta _{y})] & =\mathbb {V}_{x|y}[-y(f(x)+\Delta _{y})]\nonumber \\& =\mathbb {V}_{x|y}[f(x)]\nonumber \\& =w^{\top }C_{y}w\nonumber \\& \le \Vert w\Vert ^{2}\Vert C_{y}\Vert _{2}\nonumber \\& =\Vert w\Vert ^{2}\lambda _{\mathrm {max}}(C_{y})\nonumber \\& \le \Vert w\Vert ^{2}\mathrm {tr}(C_{y}).\) 
Proof of Proposition  REF
We are now ready to prove Proposition REF .
Proof
We first consider the class-conditional logit adjusted loss \(\mathbb {E}_{x|y}\ell _{\mathrm {log}}(y,f(x)+\Delta _{y})\) .
For \(y\in \lbrace -1,1\rbrace \) , Lemma REF  implies that with probability
at least \(1-\delta /2\)
\(\mathbb {E}_{x|y}\ell _{\mathrm {log}}(y,f(x)+\Delta _{y}) & \le \frac{1}{|S_{y}|}\sum _{x\in S_{y}}\ell _{\mathrm {log}}(y,f(x)+\Delta _{y})+\sqrt{\frac{2\hat{\mathbb {V}}_{x|y}[\ell _{\mathrm {log}}(y,f(x)+\Delta _{y})]\ln 4/\delta }{|S_{y}|}}+\frac{7B\ln 4/\delta }{3(|S_{y}|-1)}.\) 

As a consequence of the union bound, we have with probability at least
\(1-\delta \) ,
\(& \sum _{y\in \lbrace -1,1\rbrace }\mathbb {P}(y)\mathbb {E}_{x|y}\ell _{\mathrm {log}}(y,f(x)+\Delta _{y})\\& \le \sum _{y\in \lbrace -1,1\rbrace }\mathbb {P}(y)\left[\frac{1}{|S_{y}|}\sum _{x\in S_{y}}\ell _{\mathrm {log}}(y,f(x)+\Delta _{y})+\sqrt{\frac{2\hat{\mathbb {V}}_{x|y}[\ell _{\mathrm {log}}(y,f(x)+\Delta _{y})]\ln 2/\delta }{|S_{y}|}}+\frac{7B\ln 2/\delta }{3(|S_{y}|-1)}\right]\\& =\sum _{y\in \lbrace -1,1\rbrace }\frac{\mathbb {P}(y)}{|S_{y}|}\sum _{x\in S_{y}}\ell _{\mathrm {log}}(y,f(x)+\Delta _{y})\\& \phantom{=}+\sum _{y\in \lbrace -1,1\rbrace }\mathbb {P}(y)\sqrt{\frac{2\hat{\mathbb {V}}_{x|y}[\ell _{\mathrm {log}}(y,f(x)+\Delta _{y})]\ln 2/\delta }{|S_{y}|}}+\frac{7B\ln 2/\delta }{3}\sum _{y\in \lbrace -1,1\rbrace }\frac{\mathbb {P}(y)}{|S_{y}|-1}\\& \stackrel{.}{=}T_{n}+V_{n}+\frac{7B\ln 2/\delta }{3}\sum _{y\in \lbrace -1,1\rbrace }\frac{\mathbb {P}(y)}{|S_{y}|-1}\\& \stackrel{.}{=}(\heartsuit ),\) 

where we define \(T_{n}\stackrel{.}{=}\sum _{y\in \lbrace -1,1\rbrace }\frac{\mathbb {P}(y)}{|S_{y}|}\sum _{x\in S_{y}}\ell _{\mathrm {log}}(y,f(x)+\Delta _{y})\) 
and \(V_{n}\stackrel{.}{=}\sum _{y\in \lbrace -1,1\rbrace }\mathbb {P}(y)\sqrt{\frac{2\hat{\mathbb {V}}_{x|y}[\ell _{\mathrm {log}}(y,f(x)+\Delta _{y})]\ln 2/\delta }{|S_{y}|}}\) .
We upper bound \(V_{n}\)  as
\(V_{n} & \stackrel{(a)}{\le }\sqrt{\sum _{y\in \lbrace -1,1\rbrace }\frac{2\mathbb {P}(y)}{|S_{y}|}\hat{\mathbb {V}}_{x|y}[\ell _{\mathrm {log}}(y,f(x)+\Delta _{y})]\ln 2/\delta }\\& \stackrel{(b)}{\le }\sqrt{\ln \frac{2}{\delta }\sum _{y\in \lbrace -1,1\rbrace }\frac{2\mathbb {P}(y)}{|S_{y}|}\Vert w\Vert ^{2}\mathrm {tr}(\hat{C}_{y})}\\& \stackrel{.}{=}(\bigstar )\) 

where at \((a)\)  we use Jensen's inequality, \((b)\)  follows from Lemma
REF , \(\hat{C}_{y}\stackrel{.}{=}\frac{1}{|S_{y}|}\sum _{x\in S_{y}}(\Phi (x)-\hat{\mu }_{y})(\Phi (x)-\hat{\mu }_{y})^{\top },\) 
and \(\hat{\mu }_{y}\stackrel{.}{=}\frac{1}{|S_{y}|}\sum _{x\in S_{y}}\Phi (x)\) .
By Proposition REF , we have
\(\frac{2|S_{y}|}{|S_{y}|-1}\cdot \mathrm {tr}(\hat{C}_{y})-\alpha _{y}+\log \left(|S_{y}|-1\right) & \le \bar{\Omega }_{\mathrm {pull}}(y),\text{ implying that}\\2\mathrm {tr}(\hat{C}_{y}) & \le \bar{\Omega }_{\mathrm {pull}}(y)+\alpha _{y}-\log \left(|S_{y}|-1\right)\\& \le \bar{\Omega }_{\mathrm {pull}}(y)+\alpha _{y}.\) 

The last inequality suggests that
\(V_{n}\le (\bigstar ) & \le \Vert w\Vert \sqrt{\ln \frac{2}{\delta }\sum _{y\in \lbrace -1,1\rbrace }\frac{\mathbb {P}(y)}{|S_{y}|}\left[\bar{\Omega }_{\mathrm {pull}}(y)+\alpha _{y}\right]}.\) 

Combining the last line with \((\heartsuit )\)  gives the result.
Additional related work
Improved embedding geometry.
Several works have studied means of improving the geometry of learned embeddings for clasification tasks.
The center loss [17]} pulls sample embeddings towards their class
centroid \(\mu _y\) :
\( \Omega _{\rm center}( x, y ) \stackrel{.}{=}\Vert  \Phi ( x ) - \mu _y \Vert _2^2. \) 
Conversely, several works have studied regularisers that push apart embeddings [18]}, [19]}, [20]}, [21]};
e.g.,
under the assumption that embeddings are normalised,
the spreadout regulariser [18]} is
\(M_1 = \frac{1}{|\lbrace x \ne x^{\prime }\rbrace |}\sum _{x \ne x^{\prime }}\Phi ( x )^\top \Phi ( x^{\prime } ) \\M_2 = \frac{1}{|\lbrace x \ne x^{\prime }\rbrace |} \sum _{x^{\prime } \ne x} ( \Phi ( x )^\top \Phi ( x^{\prime } ) )^2 \\\Omega _{\rm spread}( x, y ) \stackrel{.}{=}M_1^2 + \max \left(0, M_2 - \frac{1}{d}\right).\) 
Similar regularisers were also explored in a long-tailed setting by [23]}.
None of the above techniques consider an explicit margin for their “pull” or “push” regularisation.
Deep LDA.
Fisher linear discriminant analysis [24]} is a classical means of tackling classification,
which relies on finding projections that minimise intra-class variance (i.e., pull together projected scores) and maximise inter-class variance (i.e., push apart projected scores).
In a deep learning context, [25]} proposed a form of deep LDA.
This is not attuned to the long-tail setting, and does not enforce classification or embedding margins.
