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 [1]} 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 [2]}, [3]}, [4]}, [5]};
e.g.,
under the assumption that embeddings are normalised,
the spreadout regulariser [2]} 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 [7]}.
None of the above techniques consider an explicit margin for their “pull” or “push” regularisation.
Deep LDA.
Fisher linear discriminant analysis [8]} 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, [9]} proposed a form of deep LDA.
This is not attuned to the long-tail setting, and does not enforce classification or embedding margins.
