3
$\begingroup$

Suppose $x_i \stackrel{\text{i.i.d}}{\sim} \mathcal{N}(\mu,\Sigma)$. What can we say about dependence on $b$ of Frobenius/spectral norm quantities below?

$$f(b)=\left\|\frac{1}{b}\sum_{i=1}^b x_i x_i^T\right\|_F^2$$

$$g(b)=\left\|\frac{1}{b}\sum_{i=1}^b x_i x_i^T\right\|$$

Empirically, the following gives a near perfect fit for some problems, how can this be explained?

$$E\frac{b}{f(b)} \approx \frac{1}{E f(1)}+ \frac{b-1}{Ef(\infty)}$$

$$E\left(\frac{b}{g(b)}\right)^2 \approx \frac{1}{E g(1)}+ \frac{b-1}{Eg(\infty)}$$

For instance, here's a check of this formula against empirically estimated quantities for 1000-dimensional Gaussian centered at zero and covariance matrix having eigenvalues $1,\frac{1}{2},\ldots,\frac{1}{1000}$.

enter image description here

enter image description here

notebook

Any pointers appreciated!

Edit we can write $f(b)$ in terms of Wishart random variable $W_b$ ($b$ degrees of freedom, covariance $\Sigma$). The following quantity has a simple dependence on $b$ (first graph)

$$E\left[\frac{b}{f(b)}\right]=E\left[\frac{b^3}{\operatorname{Tr}(W_b W_b^T)}\right]$$

Motivation: expected value of dot product squared for a random pair of vectors in a batch of size $b$ converges to $\operatorname{Tr}E[xx']^2$, behavior above suggests a way to estimate this value for finite $b$ which in term informs the largest useful batch size in mini-batch SGD, related question

$\endgroup$
4
  • 1
    $\begingroup$ you might also explicitly write down the corresponding Wishart matrix $W$, and the corresponding expression for $f$ and $g$ (is $f^2={\rm tr}\,WW^\top$ ?) $\endgroup$ Sep 4, 2022 at 21:02
  • 1
    $\begingroup$ @CarloBeenakker updated post. The question is equivalent to asking why $E\left[\frac{b^3}{\operatorname{Tr}(W_b W_b^T)}\right]$ is well predicted by a simple formula in terms of $b$ $\endgroup$ Sep 4, 2022 at 22:19
  • 1
    $\begingroup$ I interpret your finding as the statement that for $n\gg 1$ and $n\gg b$ the function $\mathbb{E}[b/f(b)]$ depends linearly on $b$; then you find the parameters of this line by fitting to two values of $b$ (you take $b=1$ and $b\rightarrow\infty$, but I guess taking $b=1$ and $b=2$ would fit equally well). There is probably a "law of large numbers" that explains why this expectation value scales linearly with the number of samples $b$. $\endgroup$ Sep 6, 2022 at 6:26
  • 1
    $\begingroup$ $f(b)$ is the average value of dot product across all pairs of vectors in batch of size $b$. This converges to $\operatorname{Tr}(\Sigma^2)$, hence $\frac{b}{f(b)}$ eventually scales linearly with $b$. What's more interesting is understanding why $E[1/f(b)]$ scales harmonically with $b$ before having converged to $1/\operatorname{Tr}(\Sigma^2)$ $\endgroup$ Sep 6, 2022 at 7:59

1 Answer 1

0
$\begingroup$

Answering Frobenius norm part of the question, $f(b)$. Still curious how to do the equivalent for $g(b)$


Suppose $X$ contains $b$ IID instances of random variable $x$ stacked as rows. Let $x$ be distributed as zero-centered Gaussian with covariance $\Sigma$. We can show the following

$$f(b)=\frac{1}{b^2}E[\|X'X\|_F^2]=\frac{(b+1)}{b}\operatorname{Tr}\Sigma^2+\frac{1}{b} (\operatorname{Tr} \Sigma)^2$$

To prove this, first note that:

$$\|X^T X\|_F^2=\operatorname{Tr} X^T X X^T X$$

And that for arbitrary R.V. $x$ we have $$E[X'XX'X]=bE[xx'xx']+b(b-1)E[xx']E[xx']$$

For Gaussian $x$ centered at zero we can apply Wick's theorem to get:

$$E[xx'xx']=2E[xx']E[xx']+E[xx'] \operatorname{Tr}E[xx']$$

Combining these three equations yields the result above

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.