Hi @twistedcubic , @hoonose,
I appreciate your giving a nice paper and codes. I really enjoyed reading the paper. However, I found some typos and issues regarding the results of the code.
In Lemma C.3 of the paper, the error term is written as
$$
\Vert \hat \Sigma - \Sigma \Vert_2 \le \Vert \Sigma \Vert_2 \left( 2\left( \sqrt{d/n} + \sqrt{2\ln(\beta/2)/n} \right) + \left( \sqrt{d/n} + \sqrt{2\ln(\beta/2)/n} \right)^2 \right).
$$
However, since $\beta \in (0, 1)$, $\ln(\beta/2)$ is not a real number, and the above inequality is not well-defined.
Actually, in the original reference of the book of Wainwright, the probability bound is given as
$$
\Vert \hat \Sigma - \Sigma \Vert_2 \le \Vert \Sigma \Vert_2 \left( 2\left( \sqrt{d/n} + \delta \right) + \left( \sqrt{d/n} + \delta \right)^2 \right)
$$
with probability at least $1-2\exp(-n\delta^2 / 2)$. By setting $2\exp(-n\delta^2 / 2) = \beta$, we have
$$
\delta = \sqrt{\frac{2\ln(2/\beta)}{n}}.
$$
Thus, $\eta$ in eq.(1) in the paper should be
$$
2\left( \sqrt{d/n} + \sqrt{2\ln(2/\beta)/n} \right) + \left( \sqrt{d/n} + \sqrt{2\ln(2/\beta)/n} \right)^2.
$$
As a result, the line 21 of algos.py also should be
0.5*(2*(np.sqrt(d/n) + np.sqrt(2*np.log(2/b)/n) + (np.sqrt(d/n)+np.sqrt(2*np.log(2/b)/n)**2)
Also, in the definition of gaussian_tailbound (the line 65), 1/b should be n/b.
For the second issue, I found that the output of Algorithm 4 may not be symmetric matrix. However, the covariance matrix should be a symmetric matrix. This is because $A_{t-1}$ may not be symmetric after some $t$ steps. To resolve this problem, I suggest modifying the line 7 of the algorithm to
$$
\mathrm{return} \quad A_{t-1}^{-1} Z_t (A_{t-1}^{-1})^\top.
$$
Is this the correct way? Please check this issue, and I would appreciate it if you could consider this suggestion.
Hi @twistedcubic , @hoonose,
I appreciate your giving a nice paper and codes. I really enjoyed reading the paper. However, I found some typos and issues regarding the results of the code.
In Lemma C.3 of the paper, the error term is written as
However, since$\beta \in (0, 1)$ , $\ln(\beta/2)$ is not a real number, and the above inequality is not
well-defined.Actually, in the original reference of the book of Wainwright, the probability bound is given as
with probability at least$1-2\exp(-n\delta^2 / 2)$ . By setting $2\exp(-n\delta^2 / 2) = \beta$ , we have
Thus,$\eta$ in eq.(1) in the paper should be
As a result, the line 21 of
algos.pyalso should beAlso, in the definition of
gaussian_tailbound(the line 65),1/bshould ben/b.For the second issue, I found that the output of$A_{t-1}$ may not be symmetric after some $t$ steps. To resolve this problem, I suggest modifying the line 7 of the algorithm to
Algorithm 4may not be symmetric matrix. However, the covariance matrix should be a symmetric matrix. This is becauseIs this the correct way? Please check this issue, and I would appreciate it if you could consider this suggestion.