Skip to main content
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