  In solving simulation-based stochastic root-finding or optimization problems
that involve rare events, such as in extreme quantile estimation, running crude
Monte Carlo can be prohibitively inefficient. To address this issue, importance
sampling can be employed to drive down the sampling error to a desirable level.
However, selecting a good importance sampler requires knowledge of the solution
to the problem at hand, which is the goal to begin with and thus forms a
circular challenge. We investigate the use of adaptive importance sampling to
untie this circularity. Our procedure sequentially updates the importance
sampler to reach the optimal sampler and the optimal solution simultaneously,
and can be embedded in both sample average approximation and stochastic
approximation-type algorithms. Our theoretical analysis establishes strong
consistency and asymptotic normality of the resulting estimators. We also
demonstrate, via a minimax perspective, the key role of using adaptivity in
controlling asymptotic errors. Finally, we illustrate the effectiveness of our
approach via numerical experiments.
