Sampling Can Be Faster Than Optimization

Yi-An Ma; Yuansi Chen; Chi Jin; Nicolas Flammarion; Michael I. Jordan

Source-linked AI summary

Sampling Can Be Faster Than Optimization

Yi-An Ma, Yuansi Chen, Chi Jin, Nicolas Flammarion, Michael I. Jordan

arXiv:1811.08413v2Nov 20, 2018stat.MLcs.LG

TL;DR

The paper addresses limited theoretical understanding of how optimization and Monte Carlo sampling compare beyond convex and log-concave settings. It analyzes locally nonconvex objectives arising in mixture models and multistable systems, showing that sampling can have polynomial dimension dependence while optimization has exponential dependence.

Problem
Existing theory mainly compares optimization and sampling in convex or log-concave settings, leaving their relative complexity in relevant nonconvex problems less understood.
Method
The paper analyzes Langevin sampling and broad iterative optimization classes for smooth objectives that are strongly convex outside a bounded nonconvex region, including a Gaussian-mixture example.
Results
Sampling has polynomial complexity in dimension, whereas optimization algorithms display exponential complexity for the studied nonconvex objective family.
Takeaways & Limitations
In the studied setting, sampling can be computationally easier than optimization despite the conventional efficiency advantage of optimization in convex problems.
Takeaways & Limitations
The conclusions are worst-case and depend on the paper’s assumptions; other nonconvexity classes may have exponential sampling bounds.

Abstract

from arXiv · show

Optimization algorithms and Monte Carlo sampling algorithms have provided the computational foundations for the rapid growth in applications of statistical machine learning in recent years. There is, however, limited theoretical understanding of the relationships between these two kinds of methodology, and limited understanding of relative strengths and weaknesses. Moreover, existing results have been obtained primarily in the setting of convex functions (for optimization) and log-concave functions (for sampling). In this setting, where local properties determine global properties, optimization algorithms are unsurprisingly more efficient computationally than sampling algorithms. We instead examine a class of nonconvex objective functions that arise in mixture modeling and multi-stable systems. In this nonconvex setting, we find that the computational complexity of sampling algorithms scales linearly with the model dimension while that of optimization algorithms scales exponentially.

1 Polynomial Convergence of MCMC Algorithms

The paper analyzes Langevin sampling for smooth targets that are strongly convex outside a bounded nonconvex region. Its framework yields polynomial convergence guarantees by combining continuous-time analysis with discretization.

Algorithms: ULA differs from gradient descent by adding Gaussian noise, while MALA additionally applies a Metropolis adjustment.The random term has distribution ξ ∼ N(0, 2h_kI); omitting the acceptance step gives ULA, and including it gives MALA.
Problem setting: Langevin algorithms target distributions whose potentials are strongly convex outside a bounded region and Lipschitz smooth globally.The condition number is κ = L/m, with m and L describing curvature and smoothness outside the nonconvex region.
Convergence guarantees: The Metropolis adjustment improves ULA’s mixing-time dependence on ϵ to logarithmic dependence while sacrificing a factor of dimension d.These are upper bounds specific to the stated assumptions and do not establish that ULA is generically faster than MALA in dimension dependence.
Convergence guarantees: When LR^2 = O(log d), the resulting Langevin sampling complexity is polynomial in dimension d despite local nonconvexity.Relative to strongly convex potentials, local nonconvexity contributes an extra factor of e^O(LR^2).
Proof framework: The analysis separates continuous-time convergence from discretization, using weighted Sobolev properties and step-size control.The continuous process is analyzed first, then an appropriate discretization is chosen to retain the convergence rate.
Proof framework: The target distribution’s log-Sobolev constant converts KL-divergence analysis into convergence rates for the Langevin dynamics.The proof bounds this constant by approximating the locally nonconvex potential with a globally strongly convex function and applying standard inequalities.
Convergence guarantees: The log-Sobolev constant is largely governed by global properties where probability mass concentrates, so local nonconvexity has limited influence.This permits non-asymptotic guarantees in KL divergence and total variation distance.

2 Exponential Dependence on Dimension for Optimization

The paper proves that broad iterative optimization methods can require exponentially many iterations to approximate the global minimum of smooth, locally nonconvex objectives. The lower bound arises from exponentially many locally indistinguishable regions containing a hidden minimum.

Lower-bound setting: The optimization lower bound applies to algorithms querying function values and derivatives of any fixed order, using deterministic or randomized updates.The theorem considers the full query history when selecting each next point.
Scope: The lower bound is information-theoretic and unconditional, rather than dependent on conjectures such as P ≠ NP.It concerns the specified iterative algorithm class and query forms.
Lower-bound construction: The hard instance packs exponentially many small balls inside the nonconvex region and places the global minimum in one unknown ball.Other balls receive a larger constant value, making the relevant region difficult to identify through local queries.
Interpretation: The construction models settings where attraction regions around minima are small and each region behaves relatively autonomously.The paper connects this pattern to multistable physical systems with local stable regimes and transitions between them.
Statistical example: The Gaussian-mixture example demonstrates that this combinatorial complexity occurs in a natural statistical model.For EM, the paper reports more than K ≥ min{O(d^(1/ϵ)), O(d^d)} queries under a stated initialization and condition.
Sampling for optimization: Using Langevin samples to approximate a global minimizer also requires β = e^Ω(d/ϵ) in the stated construction.The required smoothness then scales with d, producing exponential sampling complexity in dimension.

3 Parameter Estimation from Gaussian Mixture Model: Sampling versus Optimization

In a Gaussian mixture model, the paper compares Langevin sampling with EM optimization for estimating mean parameters and finds sampling computationally preferable in the studied nonconvex setting.

Model and algorithms: The study compares Langevin sampling and EM optimization for inferring Gaussian mixture mean parameters.EM produces maximum a posteriori estimates, while ULA produces mean estimates evaluated using objective values, cross entropy, and expected parameters.
Sampling results: Under MR2 = O(log d), ULA and MALA converge to ϵ accuracy within a polynomial-in-dimension iteration bound.
Optimization results: For suitable datasets and initialization near data points, EM requires more than K ≥ min{O(d^1/ϵ), O(d^d)} queries to converge.For small ϵ, the stated complexity scales exponentially with dimension; for large ϵ, its dependence on d can have arbitrarily high order.
Optimization results: EM is significantly harder to converge when initialized close to the given data points, consistent with the use of heuristic, problem-dependent initialization in practice.
Experimental comparison: When d ≥ 10, EM requires too many gradient queries for accurate convergence-time estimation, whereas ULA converges within 1500 queries at d = 32.
Optimization results: Gradient-based optimization methods can become trapped in one of the many local optima.

4 Discussion

The discussion explains why local nonconvexity can favor sampling over optimization, while identifying parameter regimes and open questions that limit the scope of the comparison.

Main comparison: For a natural family of locally nonconvex functions, sampling has polynomial complexity in dimension while optimization has exponential complexity.
Interpretation: Optimization complexity depends heavily on local properties of U, whereas sampling complexity depends more heavily on its global properties.
Regimes: With constant L, sampling is generally easier than optimization when R = O(log d), while the comparison becomes indeterminate for d < R < d.
Regimes: When R = 0, GD converges in κ log(1/ϵ) steps whereas ULA converges in κ^2d/ϵ^2 steps.
Open questions: The analysis suggests developing MCMC lower bounds and studying other forms of nonconvexity, including strongly dissipative functions.

Appendix B Proofs for Sampling

The appendix proves sampling guarantees for locally nonconvex targets by reducing them to strongly convex analysis and controlling the resulting perturbation.

Theorem and assumptions: Theorem 1 analyzes ULA and MALA for targets whose potential satisfies the local nonconvexity assumptions.The target density is p∗ ∝ e^-U, with initialization p0 specified in the theorem.
Theorem and assumptions: The assumptions imply that the nonconvex region has small probability mass in high dimensions, so its effect does not qualitatively perturb ULA and MALA mixing times.
Generalization: If the exterior Lipschitz and strong-convexity parameters scale with d, the ULA complexity becomes O(d^3/ϵ^2), with the additional d^2 factor arising from the step size.
Proof strategy: The proof constructs a globally m/2-strongly convex auxiliary potential ˆU that differs from the modified potential by at most 16LR^2.
Proof strategy: The auxiliary potential is built through convex extension, smoothing, and interpolation across the nonconvex region.
Proof strategy: Holley–Stroock comparison transfers the strongly log-concave auxiliary potential's log-Sobolev control to the original target.

B.2 Proof of ULA Convergence Rate (Equation (1) of Theorem 1)

The proof analyzes discretized Langevin dynamics through KL divergence, bounds its evolution using functional inequalities, and selects a stepsize and iteration count to obtain dimension-dependent convergence complexity.

The proof measures convergence to p∗ with KL divergence and uses Pinsker’s inequality to control total variation distance.
The discretized Langevin process is represented through continuous-time dynamics between grid points, with transition densities characterized by a Kolmogorov forward equation.
The KL divergence derivative is bounded using the process representation, Young’s inequality, and the target distribution’s log-Sobolev inequality.
Gronwall’s inequality propagates the divergence bound across time intervals, after which the stepsize is chosen to control discretization error.
The resulting computation complexity is obtained by focusing on its dependence on the dimension and combining the convergence bounds with the target assumptions.

B.3 Proof of MALA Convergence Rate (Equation (2) of Theorem 1)

The MALA proof establishes convergence by combining warm-start control, conductance bounds on a high-probability region, and a Markov-chain convergence theorem.

The proof reduces MALA convergence to two lemmas: one for a β-warm initial distribution and one for the selected initial distribution.
The initial distribution is shown to be e16LR2 (2κ)d/2-warm with respect to the target distribution.
The argument restricts attention to a truncated high-probability ball and lower-bounds s-conductance for sufficiently small stepsizes.
Lovász–Simonovits convergence is then applied using the conductance bound, the initial distribution, and the stationary target distribution.
Under the current assumptions, the stepsize scales as h = O(d−1), while improved h = O(d−1/3) scaling requires extra smoothness and decomposability assumptions.

B.3.1 Supporting Proofs for Equation (2) of Theorem 1

The supporting proofs establish concentration and isoperimetric properties of the target, then use proposal-overlap bounds and smoothness arguments to support MALA conductance.

The starting distribution is analyzed through concentration of the stationary target around the origin, obtained from its log-Sobolev constant.
The target’s log-Sobolev inequality is converted into Poincaré and isoperimetric inequalities with constants of the same order.
The proposal and transition distributions are compared using total variation and KL-divergence bounds for Gaussian proposals.
A direct application of Buser’s inequality is unavailable because the potential may have negative curvature.
Smoothness of U controls the proposal acceptance analysis without relying on convexity, although one factor of 2 is lost in a bound.

C.1 Proof of Theorem 2

The optimization lower bound constructs many separated candidate regions whose local information is indistinguishable, forcing algorithms to search for the region containing the favorable minimum.

A packing argument constructs η non-intersecting radius-r balls inside a larger radius-R ball.
The constructed objective is smooth and strongly convex outside the nonconvex region while remaining flat around most candidate regions.
Inside nonoptimal candidate balls, the objective and all queried derivatives provide no information identifying the distinguished ball.
For T ≤ η, the probability of finding the distinguished region is bounded by the fraction of candidate regions examined.

C.2 Proof of Corollary 2

The corollary separates obtaining an approximately optimal sample from sampling that distribution, yielding an exponential iteration requirement for Langevin algorithms in the constructed setting.

β = eΩ(d/ϵ) is required for a constant probability of achieving U(ˆx) − U(x∗) < ϵ.
The proof first chooses β so q∗_β places constant probability within ϵ of the optimum.It then targets total-variation error at most p/2 when sampling q∗_β.
The Langevin algorithms require K = e O(d·LR2/ϵ) steps to guarantee convergence.
The construction applies to a Gaussian mixture model with isotropic, uniform covariance and bounded data, using the log posterior as objective.

D.2 Proofs for the EM Algorithm

The EM construction uses a Gaussian-mixture dataset with many local minima, showing that random initialization can require high-order or exponential dependence on dimension.

K ≥ min{O(d1/ϵ), O(dd)} queries are required for EM to converge when initialized near given data points.
The constructed objective is strongly convex outside radius R but has local minima matching those of the corresponding Gaussian mixture model.
Any M combinations of N − 9M data points form fixed points for EM under the stated initialization condition.
Random initialization from the dataset requires K = O(p · N M) re-initializations when N ≫ M.
Gradient descent has the same behavior as EM when initialized randomly from the dataset.

Appendix E Detailed Experimental Settings for Gaussian Mixture Models

The experiments evaluate EM and ULA on synthetic Gaussian-mixture data across dimensions 2 through 32, using separate convergence criteria for optimization and sampling.

The synthetic data have ⌊log2 d⌋ nonzero entries per point, uniformly distributed supports, and M = ⌊log2 d⌋ mixture components.
The study records gradient entries required for EM and ULA to converge as dimension d ranges from 2 to 32.Results are averaged over 20 trials.
When dimension d ≥ 10, EM requires too many gradient queries for its convergence time to be accurately estimated.
For EM, convergence requires U(µK) − U(c µ∗) < 10−6.
For ULA, convergence requires both expected-objective and expected-mean-parameter errors below 10−3.
Uniform initialization in the ball of radius R produces poorer convergence than initialization from data points, indicating more local minima than those near the data.