Anderson Acceleration - Faster Transition Path solver

Uncategorized
1

VFI Toolkit now supports Anderson Acceleration (AA). AA is an algorithm for solving a fixed-point problem, so it can be used for transition path general eqm, or for stationary general eqm. It is a substantial improvement on the shooting algorithm that used to be the main transition path general eqm algorithm. You can use AA with InfHorz or FHorz, and with/without PType.

A very brief explanation of AA
Many problems in the toolkit are fixed-point problems, x = G(x). Plain iteration uses only the most recent iterate to compute the next one. Anderson Acceleration keeps the last m iterates and their residuals (G(x)−x). It then solves a small least-squares problem to find the combination of them that best cancels the residual, and uses that combination as the next guess. It needs no derivatives and only one evaluation of G per iteration, so each iteration costs about the same as before, but far fewer iterations are usually needed.

How to use AA
I am just going to explain for transition path, for stationary general eqm it is similar. You need one line to say that you want to use AA, then you set “how to update” in the same layout as you would for shooting. So,

transpathoptions.GEnewprice=2; % Anderson acceleration
% howtoupdate in same format as shooting: 
% {GECondnName, PriceName, add, factor}
transpathoptions.GEnewprice2.howtoupdate={...
    'capitalmarket','r',0,0.1;...
    'labormarket','w',0,0.1;...
    };

and if you wanted to, you could specify the memory length of AA
transpathoptions.anderson.memory=5; % m, how many past iterates to use (default 5)

AA is powerful, and while it is only sometimes worthwhile for stationary GE it represents a major improvement to transition path GE where it is much faster and also creates much cleaner (less tiny wiggles in the solution). Anyone solving transition paths definitely wants to switch over to using AA, so far it just strictly dominates shooting in every model I have tried.

Thanks to @aledinola for suggesting AA as something to look at adding to the toolkit, and especially to Jeffrey Sun who helped explain AA to me and was kind enough to share his Julia code implementation.

PS. There are lots of other minor options around the precise details of AA that you can set. Ask you AI to explain them to you if you want to know more about them.

2 Likes