Computational Separations between Sampling and Optimization

Convex optimization: Algorithms and complexity

Sébastien Bubeck · 1935

Earlier work this paper cites.

Equation of state calculations by fast computing machines

Nicholas Metropolis, Arianna W. Rosenbluth, Marshall N. Rosenbluth, Augusta H. Teller, and Edward Teller · 1953

Earlier work this paper cites.

Monte carlo sampling methods using markov chains and their applications

W. K. Hastings · 1970

Earlier work this paper cites.

Class of constructive asymptotically good algebraic codes

Jørn Justesen · 1972

Earlier work this paper cites.

Reducibility among combinatorial problems

R. Karp · 1972

Earlier work this paper cites.

Brownian dynamics as smart monte carlo simulation

P. J. Rossky, J. D. Doll, and H. L. Friedman · 1978

Earlier work this paper cites.

The complexity of computing the permanent

Leslie G. Valiant · 1979

Earlier work this paper cites.

Optimization by simulated annealing

S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi · 1983

Earlier work this paper cites.

Problem complexity and method efficiency in optimization

Arkadii Semenovich Nemirovsky and David Borisovich Yudin · 1983

Cited alongside, same era.

PP is as hard as the polynomial-time hierarchy

S. Toda · 1991

Cited alongside, same era.

On the complexity of k-SAT

Russell Impagliazzo and Ramamohan Paturi · 2000

Cited alongside, same era.

Langevin diffusions and metropolis-hastings algorithms

G O. Roberts and Osnat Stramer · 2002

Cited alongside, same era.

Computational complexity lecture notes

Salil Vadhan · 2002

Cited alongside, same era.

A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries

Mark Jerrum, Alistair Sinclair, and Eric Vigoda · 2004

Cited alongside, same era.

The computational hardness of counting in two-spin models on d-regular graphs

Allan Sly and Nike Sun · 2012

Later among the works it cites.

Concentration Inequalities: A Nonasymptotic Theory of Independence

Stéphane Boucheron, Gábor Lugosi, and Pascal Massart · 2013

Later among the works it cites.

Introductory Lectures on Convex Optimization: A Basic Course

Yurii Nesterov · 2014

Later among the works it cites.

Introduction to online convex optimization

Elad Hazan · 2016

Later among the works it cites.

Nonasymptotic convergence analysis for the unadjusted langevin algorithm

Alain Durmus and Éric Moulines · 2017

Later among the works it cites.

Sampling can be faster than optimization

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

Closest in time.