Variance reduction for Random Coordinate Descent-Langevin Monte Carlo

Zhiyan Ding, Qin LiNeurIPS 2020

Introduction

Sampling from complex, high-dimensional probability distributions is a fundamental bottleneck in Bayesian inference. For log-concave distributions (where the density is $p(x) \propto e^{-f(x)}$), the gold standard approach is Langevin Monte Carlo (LMC), which utilizes the gradient of the log-density ($\nabla f$) to navigate the parameter space.

However, in many real-world scenarios—such as climate modeling or petroleum engineering—an explicit formula for $\nabla f$ is unavailable. Researchers must instead rely on finite-difference approximations, which require $d$ (the dimension) function evaluations per step. In high-dimensional settings ($d \gg 1$), this becomes prohibitively expensive. This paper introduces Randomized Coordinates Averaging Descent (RCAD) for LMC, a method that cleverly reuses gradient information from previous steps to reduce the per-iteration cost of sampling without falling victim to the "variance tax" typical of randomized coordinate methods.

The Variance Trap of Naive Methods

A seemingly straightforward solution to the high cost of finite differences is Random Coordinate Descent (RCD), which updates only one randomly selected direction per step, making each iteration $d$ times cheaper.

However, the authors formally prove a "negative result" (Theorem 4.1): blindly applying RCD to Langevin dynamics fails to provide a meaningful speedup. The randomness of selecting a single direction introduces significant variance, forcing the algorithm to take much smaller step sizes to maintain stability. Consequently, the method requires vastly more iterations to converge, entirely negating the per-iteration computational savings.

Proposed Method: RCAD-LMC

To overcome this variance trap, the authors propose the RCAD-LMC framework, available in both Overdamped (RCAD-O-LMC) and Underdamped (RCAD-U-LMC) variants.

The Core Innovation: Gradient Memory Instead of discarding information after each step, RCAD maintains a running estimate of the full gradient ($g$). The process works as follows:

  1. Initialization: Compute a full, accurate gradient once at the very beginning of the process.
  2. The Update: In each subsequent iteration, pick only one random coordinate $i$ and update only that specific component of the gradient estimate.
  3. The "Flux" Trick: The algorithm employs a specific unbiased estimator for the gradient (the "flux" $F^m$) that incorporates the history of the trajectory.

Inspired by variance reduction techniques in standard optimization (like SAGA), this approach is uniquely adapted for the stochastic differential equations (SDEs) governing Langevin dynamics. Because the gradient estimate "remembers" the other $d-1$ directions, the variance remains low, granting the stability of a full-gradient method at the cost of a coordinate-method.

Experimental Setup

As a theoretical paper focused on algorithmic foundations, the authors evaluate their method using synthetic, high-dimensional target distributions where the ground truth is perfectly known:

  • Example 1: A standard Gaussian distribution $\mathcal{N}(0, I_d)$ with $d = 1000$.
  • Example 2: A more complex mixture of two Gaussians.

These benchmarks allow for precise measurements of the Mean Squared Error (MSE) and convergence rates relative to the step size ($h$).

Key Results

The primary triumph of RCAD-LMC is its ability to drastically reduce the total number of directional derivative evaluations required to reach a target accuracy $\epsilon$.

Complexity comparison of LMC algorithms in terms of iterations and directional derivative evaluations.
  • Overdamped Speedup: For the overdamped case, RCAD-O-LMC reduces the total number of $\partial f$ evaluations from $\tilde{O}(d^2/\epsilon)$ to $\tilde{O}(d^{3/2}/\epsilon)$.
  • Underdamped Efficiency: In the underdamped case (which generally converges faster), RCAD-U-LMC achieves $\epsilon$-accuracy with an evaluation cost of $\tilde{O}(\max\{d^{4/3}/\epsilon^{2/3}, d^{1/2}/\epsilon\})$.
  • Empirical Validation: In numerical tests with $d=1000$, the RCAD methods demonstrated a much steeper error decay (slopes of -2.1 to -2.8 on log-log plots) compared to vanilla RCD methods (slopes around -1.1). This confirms that the variance reduction mechanism works exactly as intended in practice.

Limitations and Future Work

While RCAD-LMC offers significant theoretical and practical improvements, the authors note a few limitations and avenues for future research:

  • Structure Blindness: The current algorithm treats all dimensions equally. In many practical problems, certain coordinates are more "important" or have higher Lipschitz constants. Incorporating importance sampling for coordinate selection could yield further performance boosts.
  • Strong Convexity Requirement: The theoretical guarantees currently rely on the target distribution $f(x)$ being $\mu$-strongly convex. Extending these variance reduction benefits to non-convex landscapes (such as those in deep learning) remains an open challenge.
  • SPSA Integration: The authors suggest that this variance reduction strategy could potentially be combined with Simultaneous Perturbation Stochastic Approximation (SPSA), another popular gradient-free approach, leaving this synthesis for future exploration.

Summary updated

BibTeX
@inproceedings{ding2020variance,
  author = {Zhiyan Ding and Qin Li},
  title = {{Variance reduction for Random Coordinate Descent-Langevin Monte Carlo}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
}
Figure