Global convergence of optimized adaptive importance samplers

Ömer Deniz Akyıldız

TL;DR

This paper provides the first global convergence guarantees for Adaptive Importance Sampling (AIS) using general, non-convex proposal distributions. By framing the adaptation process as a global optimization problem solved via Stochastic Gradient Langevin Dynamics (SGLD), the author derives explicit, uniform-in-time error bounds for the mean-squared error of the resulting estimates.

What Problem Does This Paper Address?

Importance Sampling (IS) is a cornerstone of Monte Carlo integration, used to estimate expectations of a target distribution $\pi$ by sampling from a proposal distribution $q$. However, IS fails when $q$ is "far" from $\pi$, leading to high-variance weights. Adaptive Importance Sampling (AIS) attempts to fix this by iteratively updating the proposal.

While AIS is popular, its theoretical foundations have been shaky for general cases. Previous proofs of convergence mostly relied on the proposal being part of an "exponential family," where the objective function (minimizing the $\chi^2$-divergence between target and proposal) is conveniently convex. In the real world, researchers often use complex proposals—like neural networks or heavy-tailed distributions—where the objective is non-convex. Until now, there was a lack of theoretical guarantees for whether these general adaptive schemes actually converge to the global optimum or at what rate they do so.

Methods

The paper analyzes the Optimized Adaptive Importance Sampler (OAIS). The core idea is to treat the adaptation of the proposal parameters ($\theta$) as a global optimization problem to minimize the $\chi^2$-divergence.

Key components include:

  • Stochastic Gradient Langevin Dynamics (SGLD): To navigate the non-convex landscape of the $\chi^2$-divergence, the author employs SGLD. Unlike standard gradient descent, SGLD injects controlled noise, allowing the algorithm to escape local minima and "flat valleys" to find the global optimum.
  • Reparameterization Trick: To obtain low-variance stochastic gradients of the objective function, the author assumes the proposal is reparameterizable (a technique widely used in Variational Autoencoders).
  • Non-Asymptotic Analysis: Instead of just proving the algorithm works "eventually," the author leverages recent results from non-convex optimization literature to derive explicit bounds on the Mean Squared Error (MSE) that hold for a finite number of iterations and samples.

Datasets

As a theoretical paper, the work focuses on mathematical proofs rather than large-scale empirical benchmarks. However, it includes a numerical example to validate the theory:

  • Target: A standard Gaussian distribution.
  • Proposal: A Student’s-t distribution (which is outside the exponential family).
  • Setup: The algorithm starts with a proposal mean far from the target ($\theta_0 = -10$) and uses SGLD to adapt it. The results are averaged over 1000 runs to demonstrate stability and convergence.

Key Insights and Ideas

  • Adaptation as Global Optimization: The paper shifts the perspective of AIS from a heuristic "moving toward the target" to a formal global optimization of the variance of importance weights.
  • The Necessity of Noise: In non-convex settings, the noise in SGLD isn't a nuisance; it's a feature. It ensures the proposal doesn't get stuck in a sub-optimal configuration, which is critical when the proposal family is complex.
  • Implicit vs. Explicit Assumptions: Rather than restricting the type of proposal distribution (e.g., must be Gaussian), the author places assumptions on the behavior of the $\chi^2$-divergence function itself (such as Lipschitz continuity and dissipativity). This makes the theory applicable to a much wider range of models, including neural-network-parameterized proposals.
  • Uniform-in-Time Guarantees: The derived error bounds are "uniform-in-time," meaning the error doesn't accumulate or explode as you run more iterations of the adaptive process.

Key Results

  • Global Convergence Theorem: The author proves that the MSE of the OAIS estimator is bounded by a sum of terms that vanish as the number of samples ($N$) and iterations ($k$) increase.
  • Convergence Rate: For SGLD-driven adaptation, the error scales with the step-size $\eta$ at a rate of $O(\eta^{1/4})$. While slower than the $O(\eta)$ rate seen in deterministic/convex cases, it is a robust guarantee for the non-convex regime.
  • Numerical Success: In the Student's-t example, the algorithm successfully moved the proposal mean to the target and significantly increased the Effective Sample Size (ESS), even though the gradients vanish at infinity (a scenario where standard SGD would likely fail).

Limitations and Future Work

  • Dimension Dependence: The theoretical constants in the error bounds scale exponentially with the dimension ($d$) of the parameter space. While this is a common "worst-case" result in non-convex theory, in practice, SGLD often performs better than these bounds suggest.
  • Dissipativity Verification: The "dissipativity" assumption (which ensures the optimizer stays within a reasonable region) can be hard to verify for very complex target distributions. The author suggests using "Projected SGLD" as a practical workaround.
  • Optimizer Variants: The current analysis focuses on SGLD. Future work could extend these global convergence proofs to other popular optimizers like Adam, momentum-based Langevin dynamics, or variance-reduced methods to see if they offer faster convergence rates (e.g., improving the $O(\eta^{1/4})$ dependence).

Summary updated

Abstract

We analyze the optimized adaptive importance sampler (OAIS) for performing Monte Carlo integration with general proposals. We leverage a classical result which shows that the bias and the mean-squared error (MSE) of the importance sampling scales with the $χ^2$-divergence between the target and the proposal and develop a scheme which performs global optimization of $χ^2$-divergence. While it is known that this quantity is convex for exponential family proposals, the case of the general proposals has been an open problem. We close this gap by utilizing the nonasymptotic bounds for stochastic gradient Langevin dynamics (SGLD) for the global optimization of $χ^2$-divergence and derive nonasymptotic bounds for the MSE by leveraging recent results from non-convex optimization literature. The resulting AIS schemes have explicit theoretical guarantees that are uniform-in-time.
BibTeX
@inproceedings{akyldz2024global,
  author = {Ömer Deniz Akyıldız},
  title = {{Global convergence of optimized adaptive importance samplers}},
  booktitle = {Foundations},
  year = {2024},
  doi = {10.3934/fods.2024003},
}
Figure