Faster Transition Paths - vfoptions.localsearch

You can set vfoptions.localsearch=1 to access a new algorithm for solving value fn problem on transition paths.

Say we set n_a=501, the basic pure discretization algorithm involves considering every possible value of aprime (all 501) and choosing the one that maximizes the return fn. With divide-and-conquer we exploit monotonicity to slash the number of the aprime points that we have to consider (although because this converts one parallel operation into some serial operations it is not always faster on a GPU). With localsearch, we try to cut the number of aprime points even further, and we just look at a few points either side of a reference point. If the optimal point is near the reference point localsearch will get it correct, but if the optimal point is not near the reference point this will give us numerical error (an incorrect answer, but how incorrect is also important).

The question then is, what is a good reference point? Note that some algorithms, like Upwind Finite Differences and Markov Chain Approximation already do something very similar (they only consider up/down one point, together with linear interpolation to that point, and if the optimal is outside this they produce numerical error; note they only impose this restriction on the value fn, and not on the agent distribution, whereas with localsearch we will impose it on both). Even with continuous time this assumption is very hard to justify (it fails to hold in Moll’s Huggett transition model code examples).

The idea of using localsearch transition paths is that each time we iterate on the path we will only be solving something a little bit different that last iteration (as the price path update will no be massive) and so we can use the optimal aprime grid points from last path as the reference points for this path. That is, we assume that the optimal aprime is within ±nlocalsearch of the policy from last iteration. This leads to massive runtime gains (especially if it allows you to turn on fastOLG in FHorz where you otherwise couldn’t). The risk is that this just ends up finding a locally optimal solution.

The transition paths also try to protect against the local optimum risk. The first iteration of the path will be a ‘full sweep’ (just pure discretization, or divide-and-conquer if you set that in vfoptions). Then it will use localsearch for each iteration until it converges the path. Then it will do a full sweep again and if this does not move the path we found the solution. If the full sweep does move the path we had only found a local optimum and so it now switches to localsearch and iterates to convergence again (taking the full sweep as the new reference policy). This repeats until we get a full sweep that does not move the path. Notice that this is protecting against a local optimum in the localsearch aprime dimension, it is not about whether the transition path is unique.

The way localsearch handles decision variables, exogenous shocks, and other endogenous states is analogous to divide-and-conquer. Namely, localsearch is done conditional on all these others.

How to use localsearch in transition path
Just set vfoptions.localsearch=1;. Works in FHorz and InfHorz transition paths. You must also set vfoptions.nlocalsearch=5; to any integer value (there is no default). Smaller values will run faster per-transition-path-iteration, but are not guaranteed to be faster overall as depends how many iterations are required. No real advice on setting nlocalsearch (as I haven’t done a lot of testing of varying it) maybe just try a few values to see how things go.

Works with both shooting and anderson acceleration algorithms for transition paths.

1 Like

This does not yet work with PType. It has also not yet been implemented for models with more than one endogenous state. But all this should happen over the next month or two.

1 Like

Useful! In principle the same local search option can be used for any iterative algorithm, like vfi in infinite horizon. See this excellent lecture note by Makoto Nakajima that explains this algorithm (infinite horizon value function iteration with local search) here: https://makotonakajima.github.io/homepage/note-ngm-disc.pdf

My understanding is that for now the toolkit implements local search only for transition paths. Is this correct?

1 Like

At least currently it is only for transition paths.

If you try to use it in infinite horizon you will likely just keep getting stuck in local optima (this is a hard problem that occurs in many models, and it is to try and avoid this that the default for postGI is such a wide window). Which is why I haven’t tried it there. And in standard FHorz problems it is just not obvious what a sensible definition of the reference should be.

What makes it work in transition paths is that a good reference point is obvious, namely what was optimal on the previous transition iteration. Because the update the the path is modest it is reasonable to expect we did not move far away.

I took a look at Makoto Nakajima’s doc, it is good and a largely accurate description of what I did except that he has a very different approach to defining the reference policy (I had just made the algorithm up inspired by the upwind finite difference and markov chain approximation methods). He suggests alternating local search with full sweep in an InfHorz setting, which is about trying to avoid local optima (note that upwind finite difference and markov chain approximation methods don’t do this). Maybe I should try this but my intuition was that on a GPU it is building the ReturnFn matrix that takes most of the runtime, so the potential runtime savings of having localsearch index just part of this and then shrinking the max are rather modest.

I could also try local search for OLG models, as there the FHorz could use last iteration (while finding the stationary general eqm) as the reference. Potentially works well (as long as the iteration updates are not too large, so likely depends a fair bit on the optimizer being used).

1 Like

The toolkit implementation uses ± vfoptions.nlocalsearch on the first iteration, but then widens/shrinks this window at each iteration depending on if any points are hitting the edges of the window.

1 Like