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"

Improve this question
$\endgroup$
6
  • $\begingroup$ I doubt very much one can do better than math.stackexchange.com/a/4228443 $\endgroup$
    – Carlo Beenakker
    Commented 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$
    – Yaroslav Bulatov
    Commented 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$
    – Carlo Beenakker
    Commented 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$
    – Iosif Pinelis
    Commented 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$
    – Pietro Majer
    Commented Aug 31, 2021 at 15:21

2 Answers 2

Reset to default
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

Improve this answer
$\endgroup$
2
  • $\begingroup$ It is now shown that the limit is indeed $<2$. $\endgroup$
    – Iosif Pinelis
    Commented 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$
    – Yaroslav Bulatov
    Commented 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$.)

Improve this answer
$\endgroup$

You must log in to answer this question.

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