4
$\begingroup$

Suppose $A$ is a diagonal matrix with eigenvalues $1,\frac{1}{2},\frac{1}{3},\ldots,\frac{1}{n}$ and $x$ is drawn from standard Gaussian in $n$ dimensions. Define $z_n$ as follows $$z_n=E_{x\sim \mathcal{N}\left(0, I_n\right)}\left[\frac{x^T A^2 x}{x^T A^3 x}\right]$$

Is it possible to prove or disprove the following?

$$\lim_{n\to \infty} z_n = 2$$

This is a crosspost from math.SE where several people provided altnernative characterizations of $z_n$ but which don't quite settle the question.

Motivation: $z_n$ is the expected value of learning rate which maximizes loss decrease for a gradient descent step on a quadratic $A$ and random starting point. If the limit is 2, this would be a nice mathematical illustration behind the heuristic used in practice, "in high dimensions -- set learning rate as high as possible"

$\endgroup$
6
  • $\begingroup$ I doubt very much one can do better than math.stackexchange.com/a/4228443 $\endgroup$ Aug 31, 2021 at 11:22
  • $\begingroup$ Substituting infinite $s$ expansions from that answer, the integral can be solved exactly, and it evaluates to 0.5513. I'm confused whether this provides evidence that the limit in question is lower than 2 $\endgroup$ Aug 31, 2021 at 11:48
  • $\begingroup$ this follows if your replace the sum over $k$ in the expressions for $G_n$ and $\log F_n$ by an integral $\int_0^\infty dk$; I don't think that is a controlled approximation from which you can make definite conclusions. $\endgroup$ Aug 31, 2021 at 12:58
  • $\begingroup$ @YaroslavBulatov : Those asymptotic expansions are valid only for large $s$, whereas the integral is over all $s>0$. So, there is no reason to substitute those asymptotic expressions for the actual ones. $\endgroup$ Aug 31, 2021 at 13:23
  • $\begingroup$ Is $x$ in $\mathbb {R}^n$ or in $\mathbb{C}^n$? And what is $I_n$? Thx $\endgroup$ Aug 31, 2021 at 15:21

2 Answers 2

3
$\begingroup$

According to this answer, $$z_\infty:=\lim_n z_n=I:=\int_0^\infty F(s)G(s)\,ds,$$ where $$F(s):=\prod_{k=1}^\infty\frac{1}{\sqrt{1+2s/k^3}},\quad G(s):=\sum_{k=1}^\infty\frac k{k^3+2s}.$$

Mathematica can express $F$ and $G$ in terms of functions built-in in Mathematica (and these expressions should be rather straightforward to verify), and then the Mathematica command NIntegrate numerically evaluates $z_\infty=I$ as $\approx1.99218$ -- close to $2$, but not $2$; see the image of the corresponding Mathematica notebook below.

Using the facts that (i) $F$ and $G$ are positive, decreasing, and convex, and hence $FG$ is so, and that (ii) Mathematica can find the values of all its built-in functions with any degree of accuracy, it is rather straightforward to show that, in fact, $I<2$.


enter image description here


$\endgroup$
2
  • $\begingroup$ It is now shown that the limit is indeed $<2$. $\endgroup$ Sep 1, 2021 at 1:58
  • $\begingroup$ Thanks, I guess that's why it was so hard to analyze, the result is not algebraically pretty! notebook $\endgroup$ Sep 1, 2021 at 8:03
0
$\begingroup$

Using the uniform integrability of what is under your expectation sign, we have $$z_\infty:=\lim_n z_n=E(Q_2/Q_3),$$ where $$Q_p:=\sum_1^\infty\frac{Z_k^2}{k^p}$$ and the $Z_k$'s are independent standard normal random variables (r.v.'s). The value of $z_\infty$ is unlikely to be exactly $2$.

(The uniform integrability follows, say, by Rosenthal's inequality for $Q_2-EQ_2$ and the inequality $E(1/Y^2)<\infty$ for any r.v. $Y$ with a gamma distribution with shape parameter $>2$.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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