Sampling can be faster than optimization

Abstract

Modern large-scale data analysis and machine learning applications rely critically on computationally efficient algorithms. There are 2 main classes of algorithms used in this setting—those based on optimization and those based on Monte Carlo sampling. The folk wisdom is that sampling is necessarily slower than optimization and is only warranted in situations where estimates of uncertainty are needed. We show that this folk wisdom is not correct in general—there is a natural class of nonconvex problems for which the computational complexity of sampling algorithms scales linearly with the model dimension while that of optimization algorithms scales exponentially.

Document Details

• Document Type: Pub Defense Publication
• Publication Date: Sep 30, 2019
• Source ID: 10.1073/pnas.1820003116

Entities

People

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

Organizations

• Army Research Office
• Office of Naval Research Global
• Statistics New Zealand

Tags

Fields of Study

• Computer science

Readers

• Adaptive Control and Estimation with Uncertainty in Dynamic Systems.
• Educational Psychology
• Operations Research

Technology Areas

• AI & ML
• AI & ML - Bayesian Inference
• AI & ML - Machine Learning Algorithms