Near-Interpolators: Rapid Norm Growth and the Trade-Off between Interpolation and Generalization

Yutong Wang, Rishi Sonthalia, Wei Hu

Abstract

Cyclical MCMC is a novel MCMC framework recently proposed by Zhang et al. (2019) to address the challenge posed by high-dimensional multimodal posterior distributions, such as those arising in deep learning. The algorithm works by generating a nonhomogeneous Markov chain that tracks—cyclically in time—tempered versions of the target distribution. We show in this work that cyclical MCMC converges to the desired probability distribution in settings where the Markov kernels used are fast mixing and sufficiently long cycles are employed. However, in the far more common settings of slow mixing kernels, the algorithm may fail to produce samples from the desired distribution. In particular, in a simple mixture example with unequal variance, we show by simulation that cyclical MCMC fails to converge to the desired limit. Finally, we show that cyclical MCMC typically estimates well the local shape of the target distribution around each mode, even when we do not have convergence to the target.

Introduction

In fields like Bayesian deep learning, we often need to sample from "multimodal" posterior distributions—landscapes with many peaks (modes) separated by deep valleys. Standard Markov Chain Monte Carlo (MCMC) methods often get stuck in one peak and fail to explore the rest. To fix this, researchers use "tempering," which flattens the distribution to make it easier for the sampler to move between peaks. Recently, "Cyclical MCMC" was proposed as a faster alternative that oscillates the temperature in cycles. While it works well in practice for some deep learning tasks, this paper provides the first rigorous theoretical analysis to understand why and when it succeeds or fails.

Methods

The authors analyze Cyclical MCMC through two theoretical lenses:

  1. Fast Mixing Regime: They adapt spectral gap theory to handle the nonhomogeneous (time-varying) nature of cyclical sampling. They prove that if the underlying kernels mix quickly enough and the cycles are long enough, the algorithm can converge to the true target.
  2. Highly Multimodal Regime: They use Lyapunov drift conditions to study what happens when the sampler is trapped within modes during the exploitation phase of a cycle.
  3. Simulations: They test the algorithm on synthetic Gaussian mixture models, specifically comparing "equal variance" (easy) vs. "unequal variance" (hard) settings to evaluate global and local accuracy.

The "Witch-Hat" Problem and Global Bias

A major insight of this work is the distinction between local and global convergence. The authors show that tempering by "powering" the distribution can turn a broad mode into a tiny, sharp spike, often referred to as a "witch hat." Most MCMC algorithms, including cyclical ones, are virtually blind to these spikes, leading to massive biases in how much weight is assigned to that mode.

An unequal variance 1D mixture illustrating the 'witch-hat' problem, where a broad mode and a sharp spike lead to significant sampling bias.

In an unequal variance 1D mixture where the true weights were 50/50, Cyclical MCMC produced a biased estimate of 0.87 vs 0.13. This confirms that the algorithm is not a drop-in replacement for mathematically exact methods like Parallel Tempering if global accuracy is required. Because the algorithm struggles with these spikes, it naturally spends more time in flatter, broader modes. In deep learning, this bias might actually be a feature, as flatter modes are often associated with better generalization.

Local Shape Recovery

Despite the failure to achieve global convergence in complex landscapes, the algorithm remains remarkably effective at capturing local structure. Even when the algorithm fails to tell you which mode is more likely (global failure), it still does a great job of describing the local curvature and shape of whichever mode it happens to be in.

Comparison of the estimated local density (dashed) against the true target density (solid), showing that the algorithm recovers the local shape almost perfectly.

Experiments on 2D mixtures showed that the x-component of individual densities was recovered almost perfectly, validating the algorithm's use for local uncertainty quantification even when global weights are incorrect.

Conclusion

Cyclical MCMC offers a high-speed alternative for exploring multimodal distributions but comes with a critical trade-off: it excels at local shape recovery while often failing to converge to the correct global distribution. Future research should move beyond simple powering for tempering to find paths that maintain fast mixing without creating problematic "witch hat" distributions. Additionally, the bias toward flatter modes deserves more study to see if it can be formally leveraged to improve machine learning model performance.

Summary updated

Abstract

Cyclical MCMC is a novel MCMC framework recently proposed by Zhang et al. (2019) to address the challenge posed by high- dimensional multimodal posterior distributions like those arising in deep learning. The algorithm works by generating a nonhomogeneous Markov chain that tracks —cyclically in time— tempered versions of the target distribution. We show in this work that cyclical MCMC converges to the desired probability distribution in settings where the Markov kernels used are fast mixing, and sufficiently long cycles are employed. However in the far more common settings of slow mixing kernels, the algorithm may fail to produce samples from the desired distribution. In particular, in a simple mixture example with unequal variance we show by simulation that cyclical MCMC fails to converge to the desired limit. Finally, we show that cyclical MCMC typically estimates well the local shape of the target distribution around each mode, even when we do not have convergence to the target.
BibTeX
@inproceedings{wang2024near,
  author = {Yutong Wang and Rishi Sonthalia and Wei Hu},
  title = {{Near-Interpolators: Rapid Norm Growth and the Trade-Off between Interpolation and Generalization}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2024},
  url = {https://openreview.net/forum?id=wtJqDPk2p4},
}
Figure