0
$\begingroup$

I'm trying to analyze convergence of $x\in \mathbb{R}^{+d}$ which follows the following recurrence

$$\mathbf{x}\leftarrow (\mathbf{1}-\mathbf{h})^2 \mathbf{x} + \mathbf{h}\langle \mathbf{x}, \mathbf{h}\rangle$$

Here $\mathbf{1}$ indicates a vector of $1$'s, vector multiplication, addition, squaring are applied pointwise and $\mathbf{h}\propto (1^{-p},2^{-p},\ldots ,d^{-p})$ for some $p\in (1,2)$.

I care about L1 norm after $t$ steps which is well approximated by the following:

$$f(t)=\|\mathbf{x}_t\|_1\approx e^{t(\operatorname{diag}[(\mathbf{1}-\mathbf{h})^2]+\mathbf{h}\mathbf{h}^T)}\mathbf{h}$$

For a given $p$, how do I get a nice upper bound on $f(t)$ which holds when $d\to \infty$?

Things are easy if we didn't have the the $\mathbf{h}\mathbf{h}^T$ term: approximating $\|\mathbf{x}_t\|_1$ with an integral I get formulas which match observed behavior very well:

enter image description here Notebook

Keeping $\mathbf{h}\mathbf{h}^T$ term makes things much harder to handle. Straightforward approach gives formula in terms of roots of diagonal + rank-1 matrix, but not practical for large $d$. There's also a numeric approach which works but also leaves unclear the dependence on $p$.

Motivation: this equation models expected value of iterated Gaussian linear system like this for non-isotropic Gaussian case. Used to model training curve of neural network training.

Improve this question
$\endgroup$
15
  • $\begingroup$ I think the letter $h$ may be doing too many different jobs here. $\endgroup$
    – Robert Israel
    Commented Mar 31, 2023 at 18:11
  • $\begingroup$ Ah right, I got too used to frameworks just letting me add $1$ to a vector and various operations applying pointwise by default. Updated for clarity $\endgroup$
    – Yaroslav Bulatov
    Commented Mar 31, 2023 at 18:32
  • $\begingroup$ Fully explicit equation is $x_i^{t+1}=(1-h_i)^2 x_i^t + h_i \sum_i x_i^t h_i$ , this form feels verbose $\endgroup$
    – Yaroslav Bulatov
    Commented Mar 31, 2023 at 22:35
  • 1
    $\begingroup$ Somewhat related $\endgroup$
    – Rodrigo de Azevedo
    Commented Mar 31, 2023 at 23:18
  • 2
    $\begingroup$ OK, give me a few days :-) $\endgroup$
    – fedja
    Commented Apr 3, 2023 at 21:26

0

Reset to default

You must log in to answer this question.