In machine learning and statistics, we frequently encounter a fundamental tension between two tasks: optimization (finding the single best configuration) and inference (sampling from a distribution to quantify uncertainty).
Optimization is often fast, highly parallelizable, and scales gracefully to millions of variables thanks to decades of engineering in hardware and convex/non-convex solvers. Inference, by contrast, typically relies on Markov Chain Monte Carlo (MCMC) methods. MCMC explores a probability landscape via sequential random walks, a process that is notoriously slow to mix, prone to getting trapped in local modes, and inherently difficult to parallelize.
What if we could use the machinery of optimization to perform inference? This is the core insight behind optimization-based sampling (often called Perturb-and-MAP or pathwise conditioning). Instead of exploring a fixed probability landscape with a random walk, we randomly shift the landscape itself by injecting structured noise, and then use a deterministic solver to find the new peak. By repeating this independent optimization process in parallel, we obtain exact or highly accurate samples from the target distribution.
The Core Intuition: Shifting the Landscape
To understand why this works, consider the classic Gumbel-Max trick for discrete choices. Suppose you want to sample a category $i$ with probability proportional to $\exp(\theta_i)$. Instead of computing the normalized probabilities, you can add independent, standard Gumbel-distributed noise $g_i$ to each log-potential $\theta_i$ and find the maximum:
$$i^* = \arg\max_i (\theta_i + g_i)$$
Remarkably, the probability that category $i$ achieves the maximum value is exactly equal to its original Gibbs probability.
Optimization-based sampling scales this mathematical property to high-dimensional structured spaces (like graphs, images, and continuous fields). Instead of running a random walk that takes thousands of steps to explore a distribution, we inject noise directly into the model's local potentials or data weights, and then hand the perturbed objective function over to a high-performance solver. Each optimization run yields a single, independent sample from the target distribution.
Traditional MCMC:
[Fixed Landscape] ---> (Random Walk Step 1) ---> (Step 2) ---> (Step 3) ... (Slow Mixing)
Perturbed Optimization:
[Base Landscape] + [Random Noise 1] ---> [MAP Solver] ---> Sample 1 \ Embarrassingly
[Base Landscape] + [Random Noise 2] ---> [MAP Solver] ---> Sample 2 /_ Parallel
Continuous Spaces: Gaussian Fields and Pathwise Conditioning
In continuous domains, sampling from high-dimensional Gaussian Markov Random Fields (GMRFs) or Gaussian Process (GP) posteriors is a major computational bottleneck. Drawing a sample typically requires factorizing a massive covariance matrix, an operation that scales cubically ($O(N^3)$) with the number of variables.
George Papandreou et al. demonstrated in Gaussian sampling by local perturbations that this cubic bottleneck can be bypassed entirely. If a Gaussian distribution is defined by local interactions (as in an image or a spatial grid), one can inject independent white noise into these local components and solve the resulting linear system as a deterministic optimization problem. Because the optimization operator implicitly propagates the local noise across the entire system, the correct global correlations emerge naturally. This allows ultra-fast iterative solvers, such as Conjugate Gradients, to generate exact samples.
This formulation bridges point estimation and full posterior inference. For instance, Alan Yuille et al. leveraged this technique in Efficient variational inference in large-scale Bayesian compressed sensing to estimate Gaussian variances across millions of variables, inheriting the parallelization and speed of modern optimization primitives.
In the context of non-parametric models like Gaussian Processes, this idea manifests as pathwise conditioning. As shown by Jihao Andreas Lin et al. in Sampling from Gaussian Process Posteriors using Stochastic Gradient Descent, a posterior sample can be constructed by combining a prior sample with a deterministic correction term. This transforms posterior sampling into a quadratic optimization problem that can be solved efficiently using Stochastic Gradient Descent (SGD).
This deep connection between numerical optimization and probabilistic sampling is formalized by Nicolas Dobigeon et al. in High-Dimensional Gaussian Sampling: A Review and a Unifying Approach Based on a Stochastic Proximal Point Algorithm, where the authors reveal that many advanced high-dimensional MCMC samplers are actually stochastic counterparts of the celebrated Proximal Point Algorithm used in optimization. Similarly, Dan MacKinlay et al. demonstrated in The Ensemble Kalman Update Is an Empirical Matheron Update that the Ensemble Kalman Filter (EnKF) relies on an identical algebraic structure to perform pathwise conditioning efficiently for data assimilation.
Discrete Spaces: Perturb-and-MAP
For discrete energy-based models—such as those used in image segmentation, structured prediction, and graph clustering—sampling is exceptionally difficult because the state space grows exponentially.
To solve this, Subhransu Maji et al. (On Sampling from the Gibbs Distribution with Random Maximum A-Posteriori Perturbations) and Tamir Hazan et al. (High Dimensional Inference With Random Maximum A-Posteriori Perturbations) extended the Gumbel-Max intuition to complex Gibbs distributions. Because adding independent noise to every single global configuration is combinatorially impossible, they showed that injecting low-dimensional Gumbel noise into local potentials (unary or pairwise terms) and finding the Maximum A-Posteriori (MAP) configuration yields an effective approximation.
Discrete Perturb-and-MAP Pipeline:
[Local Potentials] ---> Add Local Gumbel Noise ---> [Discrete MAP Solver] ---> Global Sample
This mechanism transforms a global sampling problem into a discrete optimization task, which is highly effective in rugged energy landscapes where traditional MCMC methods get stuck. This framework has been successfully adapted across several domains:
- Graph Clustering: Jörg Hendrik Kappes et al. applied this in Multicuts and Perturb & MAP for Probabilistic Graph Clustering, using integer programming to find optimal cuts on perturbed graphs to represent uncertainty in data partitions.
- Message Passing: To scale this up without relying on heavy integer linear programming solvers, Miguel Lazaro-Gredilla et al. introduced Perturb-and-max-product: Sampling and learning in discrete energy-based models, substituting global solvers with parallelizable max-product message passing to find discrete modes rapidly.
- Structured Prediction: For learning parameters from data, Subhransu Maji et al. (Learning Efficient Random Maximum A-Posteriori Predictors with Non-Decomposable Loss Functions) and Andreea Gane et al. (Learning with Maximum A-Posteriori Perturbation Models) demonstrated that injecting noise into model parameters before MAP inference creates a smooth, differentiable probability distribution that can be trained via standard gradient descent. Asish Ghoshal et al. proved in Learning Maximum-A-Posteriori Perturbation Models for Structured Prediction in Polynomial Time that such models can be trained in provably polynomial time using randomized surrogate losses, bypassing NP-hard exact inference.
Generalizing to Nonparametrics and Black-Box Spaces
The philosophy of "sampling via randomized optimization" extends beyond explicit Gaussian or discrete graphical models. It can be generalized to arbitrary posteriors and black-box search spaces by randomizing the data or the objective functions themselves.
The Posterior Bootstrap
Instead of perturbing model parameters, why not perturb the data? Edwin Fong et al. developed this perspective in Scalable Nonparametric Sampling from Multimodal Posteriors with the Posterior Bootstrap. By placing a Dirichlet Process prior on the data distribution, they showed that a series of independent optimizations over randomly reweighted datasets (combined with samples from a prior centering measure) yields independent samples from the true nonparametric posterior. This approach is "embarrassingly parallel" and uniquely capable of jumping between isolated modes in highly multimodal landscapes.
Randomized Priors
In a similar vein, Ziyu Wang et al. addressed the challenge of scaling kernel-based causal inference in Scalable Quasi-Bayesian Inference for Instrumental Variable Regression. By adding a randomized prior (or "anchor") directly to the objective function, they transformed posterior sampling into a series of regularized optimization problems. This avoids the cubic matrix inversions typical of kernel methods while providing reliable confidence intervals at a computational cost comparable to standard point estimation.
Flipping the Perspective: Optimization as Inference
Finally, this duality can be run in reverse: if sampling can be solved via optimization, then complex black-box optimization can be solved via inference. Dinghuai Zhang et al. demonstrated this unification in Unifying Likelihood-free Inference with Black-box Optimization and Beyond. By mathematically reframing the goal of finding a high-scoring sequence (e.g., DNA or protein design) as a posterior inference problem conditioned on the event of achieving a high score, optimization tasks can directly leverage advanced techniques from likelihood-free inference to navigate high-dimensional search spaces.
Summary
Optimization-based sampling changes the fundamental geometry of inference. Rather than forcing a sampler to slowly climb and descend a fixed probability landscape, we use structured randomness to alter the landscape itself, turning the search for a distribution into a parallelizable search for individual peaks. Whether through local Gaussian perturbations, discrete Gumbel-MAP models, or randomized data bootstrapping, this paradigm allows Bayesian inference to fully inherit the speed, scalability, and hardware acceleration of modern optimization.
Key Foundational Work
Efficient variational inference in large-scale Bayesian compressed sensing (2011) — contributed 2 concept elements to this direction.
Gaussian sampling by local perturbations (2010) — contributed 2 concept elements to this direction.