A recent arXival by Liviu Aolaritei, Bart Van Parys, Henry Lam, and Michael Jordan (a co-PI in our ERC Synergy Ocean project) discusses optimal importance sampling schemes for stochastic optimisation, processed by an iterative Robbins-Munro algorithm improvement (with the Polyak-Ruppert improvement).
“Despite its popularity, IS is often described as a `double-edged sword.’ Its performance depends critically on the choice of the proposal distribution, which is typically sensitive to the underlying model”
I had never thought of optimising the importance function in this context, even after the seminaire of Tom Guédon mentioned in a recent ‘og. The paper considers the optimisation of f(θ)=E[F(θ,X)] whose expectation is under a certain distribution P, through
“an iterative gradient-based algorithm that jointly updates the decision variable and the IS distribution without requiring time-scale separation between the two. Our method achieves the lowest possible asymptotic variance and guarantees global convergence under convexity of the objective and mild assumptions on the IS distribution family. Furthermore, we show that these properties are preserved under linear constraints by incorporating a recent variant of Nesterov’s dual averaging method”
with the Robbins-Munro algorithm updating the value of both θ and the parameter of the importance function. One specific difficulty is that the ideal importance function depends on the argument of the optimisation problem, obviously unknown, a “curse of circularity” I had not met previously. The linear constraint creates another kind of difficulty in order to derive the active constraint set while requiring an adapted (eg, absolutely continuous) importance function. This leads the authors to introduce a different (secondary) importance distribution on X, opening a Pandora box of infinite tuning that they opt to terminate by fixing an importance function at some finite stage. I am however uncertain as to how the combinatoric difficulty of exploring all active constraint sets at each iteration is handled. The paper being mostly theoretical, there is no illustration therein. Nor a computational cost evaluation.
