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.

此文讨论了优化算法与蒙特卡罗采样算法之间的关系以及在非凸优化函数中，采样算法的计算复杂度与模型维度呈线性关系而优化算法的计算复杂度呈指数关系。