Sampling can be faster than optimization.

Area of Science:

• Statistical Machine Learning
• Computational Complexity Theory

Background:

• Optimization and Monte Carlo sampling algorithms underpin modern statistical machine learning.
• Current theoretical understanding of these methods is limited, especially regarding their relationships and comparative strengths.
• Existing research primarily focuses on convex and log-concave functions, where optimization is typically more efficient.

Purpose of the Study:

• To investigate the computational complexity of optimization and sampling algorithms for nonconvex objective functions.
• To compare the performance scaling of these algorithms in a setting relevant to mixture modeling and multistable systems.

Main Methods:

• Analysis of computational complexity for optimization algorithms.
• Analysis of computational complexity for Monte Carlo sampling algorithms.
• Examination of algorithm performance on nonconvex objective functions.

Main Results:

• In the context of nonconvex objective functions, sampling algorithms exhibit linear scaling of computational complexity with model dimension.
• Optimization algorithms demonstrate exponential scaling of computational complexity with model dimension for these nonconvex functions.
• This contrasts with the convex/log-concave settings where optimization is generally more efficient.

Conclusions:

• Nonconvex objective functions present a scenario where sampling algorithms can be computationally more scalable than optimization algorithms.
• The findings highlight the importance of considering function properties (convex vs. nonconvex) when selecting computational methods in statistical machine learning.
• This research provides new theoretical insights into the relative efficiencies of optimization and sampling in complex modeling applications.