tonga: low rank approximation of the natural gradient, question regarding Le Roux et al. 2007

This question concerns an implementation of the topmoumoute natural gradient (tonga) algorithm as described in page 5 in the paper Le Roux et al 2007 http://research.microsoft.com/pubs/64644/tonga.pdf.

I understand that the basic idea is to augment stochastic gradient ascent with the covariance of the stochastic gradient estimates. Basically, the natural gradient approach multiplies a stochastic gradient with the inverse of the covariance of the gradient estimates in order to weight each component of the gradient by the variance of this component. We prefer moving into directions that show less variance during the stochastic gradient estimates:

$ng \propto C^{-1} g$

Since updating and inverting the covariance in an online optimisation setting is costly, the authors describe a cheap'' approximate update algorithm as described on page 5 as:

$C_t = \gamma \hat{C}_{t-1} + g_tg_t^T$ where $C_{t-1}$ is the low rank approximation at time step t-1. Writing $\hat{C}_{t} = X_tX_t^T$ with $X_t =\sqrt{\gamma} X_{t-1}\ \ g_t]$ they use an iterative update rule for the gram matrix $X_t^T X_T = G_t = \begin{pmatrix}\gamma G_{t-1}&\sqrt{\gamma} X^T_{t-1}g_t\\ \sqrt{\gamma} g^T_t X_{t-1}&g_t^Tg_t\end{pmatrix}$

They then state To keep a low-rank estimate of $\hat{C}_{t} = X_tX_t^T$, we can compute its eigendecomposition and keep only the first k eigenvectors. This can be made low cost using its relation to that of the Gram matrix

$G_t= X_t^T X_T$:

$G_t = VDV^T$

$C_t = (X_tVD^{-\frac12})D(X_tVD^{-\frac12})^T$''

Because it's cheaper than updating and decomposing G at every step, they then suggest that you should update X for several steps using $C_{t+b} = X_{t+b}X_{t+b}^T$ with $X_{t+b} = \left[\gamma U_t, \ \gamma^{\frac{b-1}{2}g_{t+1}},...\ \ \gamma^{-\frac12}g_{t+b-1}, \ \gamma^{\frac{t+b}{2}g_{t+b}}\right]$

I can see why you can get $C_t$ from $G_t$ using the eigendecomposition. But I'm unsure about their update rule for X. The authors don't explain where U is coming from.

My first assumptions (by notation) was, that this is the first k eigenvectors of $C_t$.

But this makes little sense.

My second assumption was that:

$U = (X_tVD^{-\frac12})D^{\frac12}$ because then $UU^T \approx XX^T = C$, but again I'm not sure if this is reasonable, because I don't think that then $[\gamma U, g]$ is a good approximation for $[\gamma X_{t-1}, g]$.

So if anyone has any advice as to what U should be, that would be much appreciated. I'm not getting good results using this method and want to make sure I have implemented it as intended.

• I am reading the paper now too, and as I expected, it's indeed a straightforward application of Sherman-Morrison-Woodbury for updating the covariance's inverse (though personally I feel they should be updating a (QR?) decomposition of the covariance instead of the covariance's inverse), but indeed, only in page 5 of the paper (the expression after equation 14) is $U_t$ mentioned, undefined. Maybe send the author(s) an e-mail for clarification? Aug 15 '10 at 1:56
• J. Mangaldan, thanks for the helpful comment. I emailed Le Roux and will update if hear back from him. You mention Sherman-Morrison. As I understand it, we don't want to remember C^{-1} but only a low rank decomposition. But we can't decompose C directly - it's too expensive. As long as gram matrix G is small, decomposing via G is fast. But G is growing one row/column for each observed gradient g. Now perhaps I'm confused, but if we don't use the update rule for X (that seems to be an optional part of the algorithm), how do we keep G small? The SVD does not lower the matrix's size, right? Aug 15 '10 at 9:38
• Well, the motivation for using the SMW formula (e.g. in the old-school quasi-Newton optimization algorithms) is that if your matrix A to be inverted/decomposed is not "easy" to invert/decompose, but is expressible in the form $C+UV^T$ where C is an easily inverted/decomposed matrix (e.g. diagonal or triangular) and U and V are low-rank matrices of appropriate dimensions, SMW allows you to express the inverse of A in terms of the inverse of C plus correction terms derived from U and V. I only did a quick overview of the paper and will get back to you on how SMW is exactly applied. Aug 15 '10 at 12:21
• As for updated matrices growing by rows or columns, IIRC a similar situation happens in linear programming; I will have to check by notes first to be sure. SVD is rather expensive to both compute and update, so unless your matrices are badly conditioned, QR decomposition might be a good compromise on speed and stability. Though SMW no longer exactly applies for QR, updating algorithms (column/row addition) for QR exist (e.g. MATLAB has functions for these). Aug 15 '10 at 12:26
• Thanks again for your comments. I really appreciate your help! I have just now gotten reply by one of the authors and a yet unpublished article, that seems to explain the method much better. Once I've made sure I understand the new article, I'll report back. At first glance it looks like $U = X_tV\Sigma^{-1}$ where $\Sigma$ comes from a SVD of X_t (not G). Aug 15 '10 at 14:21

So it turns out the first assumption was actually correct: $U$ is indeed the first $k$ eigenvectors of $C$, that we calculate from $G$ by means of the eigendecomposition $(X_tVD^{-\frac12})$. Thanks to $J$. Mangaldan for his comments and especially the pointers to Sherman-Morrison-Woodbury.