Timeline for Estimating $\max_{\|u\|=1} \frac{ E\left[\langle u\cdot x\rangle ^4\right]}{E\left[\langle u\cdot x\rangle ^2\right]}$
Current License: CC BY-SA 4.0
10 events
when toggle format | what | by | license | comment | |
---|---|---|---|---|---|
Nov 10, 2023 at 16:46 | comment | added | Iosif Pinelis | (i) In your post, you did not say that your $d$ is so large. (ii) The paper should have been referred to right away. (iii) Your updates seem quite different from those in the paper. In particular, importantly, the updates in the paper do not involve taking expectations. (iv) Again, if more is known about $\Sigma$ and $\mu$, then I think one can give good enough bounds on the $\max$. | |
Nov 10, 2023 at 15:55 | comment | added | Yaroslav Bulatov | Your formula involves $u$, how do I estimate it? I have $d\approx 10^{12}, \frac{\operatorname{Tr}(\Sigma)}{\|\Sigma\|} < 100$, with only access to samples of $x$, which calls for online estimation. Iterating $g_x$ from the previous comment is known to rapidly converge to the maximizer of $\max_v E[\langle v\cdot x\rangle^2]$ in this setting, so I can use your formula for the centered $x$. It's Eq 1 of paper with convergence proof. Now I need a way I can use for uncentered | |
Nov 10, 2023 at 14:11 | comment | added | Iosif Pinelis | @YaroslavBulatov : How do you prove the convergence? Also, why do you need all this? The expectation of the random iteration seems very hard to compute, whereas the maximized ratio is given explicitly and seems computationally easy to maximize. Also, if more is known about $\Sigma$ and $\mu$ (such as, say, $\|\mu\|$ being much greater than $\|\Sigma\|$), I think one can give good enough bounds on the $\max$. | |
Nov 10, 2023 at 7:35 | comment | added | Yaroslav Bulatov | If $x_1,x_2,x_3,\ldots$ are copies of random variable $x$ then as $n\to \infty$ we have $E[f_{x_n}\circ \ldots \circ f_{x_1} \circ \mathbf{1}]$ converging to $\operatorname{argmax}_u E[\langle u\cdot x\rangle^2]$. I want to find analogous $g_x$ such that $E[g_{x_n}\circ \ldots \circ g_{x_1} \circ \mathbf{1}]$ converges to $\operatorname{argmax}_u \frac{E[\langle u\cdot x\rangle^4]}{E[\langle u\cdot x\rangle^2]}$ | |
Nov 10, 2023 at 4:08 | comment | added | Iosif Pinelis | @YaroslavBulatov : Your $f_x(v)$ and all its iterations will just be $\pm x/\|x\|$. I don't see how this could work and what your point here is. | |
Nov 10, 2023 at 3:53 | comment | added | Yaroslav Bulatov | $f_x(v)$ is a random function of arbitrary vector. The other arrow indicates that iterating $f_x$ on some starting point converges to $u$, the maximizer, in expectation as the number of iterations grow to infinity. An example of such iteration is $f_x(v)=(x x^T v)/\|x x^T v\|$ which appears to converge to $\operatorname{argmax}_uE[\langle u \cdot x\rangle^2]$ in this fashion | |
Nov 10, 2023 at 3:12 | comment | added | Iosif Pinelis | @YaroslavBulatov : I don't understand notations in your comment. What is $v$? What is $f_x$? What are the left and right arrows? | |
Nov 10, 2023 at 1:38 | comment | added | Yaroslav Bulatov | Thanks....I'm dealing with a non-centered case, and was looking for a computational approach to improve on the upper bound. As an intermediate step, I was looking for a iteration $v\leftarrow f_x(v)$ where $E[\ldots \circ f_x\circ f_x \circ f_x \circ 1] \to u$ where $u$ is the maximizer | |
Nov 9, 2023 at 21:10 | history | edited | Iosif Pinelis | CC BY-SA 4.0 |
added 335 characters in body
|
Nov 9, 2023 at 20:42 | history | answered | Iosif Pinelis | CC BY-SA 4.0 |