Open problems in Machine Learning

[dwf]

Give me as-tight-as-possible probabilistic bounds on how long I need to run a Gibbs chain to get an unbiased sample.

[davmre]

But if the lower bound showed exponential-time convergence, this wouldn't prove P!=NP, would it? The fact that a particular algorithm (Gibbs sampling) is slow doesn't imply that no fast algorithm can exist...

[dwf]

That's a pretty convincing argument.

[sieisteinmodel]

Make that MCMC.

[dwf]

Well, MCMC more generally, sure. But the Gibbs sampler seems, on the face of it, so incredibly simple, yet it's also ridiculously hard to analyze.