4
$\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

Improve this 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$
    – Carlo Beenakker
    Commented 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$
    – Yaroslav Bulatov
    Commented 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$
    – Carlo Beenakker
    Commented 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$
    – Yaroslav Bulatov
    Commented Sep 6, 2022 at 7:59

1 Answer 1

Reset to default
2
$\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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .