13
$\begingroup$

I'm doing a PhD in probability theory, focusing mostly on mixing times. It's a pure maths PhD, considering precise models and showing rigorous mixing results. I'm also interested in stuff like machine learning. A brief overview of some google results suggests that MCMC is used quite a lot in these fields, however any references that I could find are of the following (approximate) form:

we want to simulate a complicated distribution; write a piece of code to sample this and run it 1,000,000 times.

The questions aren't about using rigorous probabilistic methods to find the mixing time. Maybe this is because in general people doing MC/AI aren't so interested in this? I don't know, so I thought I'd ask here..

Specifically, I'm asking for references to work in AI/ML that uses rigorous probabilistic methods to shows bounds on mixing times (runtimes for MCMC algorithms).

As mentioned above, it's possible that such a reference doesn't exist. If this is the case, any suggestions of ways that mixing times could be applied to AI/ML would be equally desirable. (Just because there isn't work in an area yet doesn't mean it can't be started!)

$\endgroup$

2 Answers 2

11
$\begingroup$

The question as asked is rather broad, because there are several works in ML/AI dedicated to mixing time analysis, as well as to detecting if mixing has happened. I would not draw too sharp a boundary about whether the work is in the ML domain or in a closely related domain. Though, I agree, in ML, often MCMC is used with Bayesian methods, and given the complexity of the distributions involved, often rigorous mixing time bounds are not derived / not possible to derive there.

However, there are some recent works in ML/AI, where the distributions involve enough structure, so as to permit a rigorous mixing time analysis. A (biased) list of some references to begin with:

  1. N. Anari, S. O. Gharan, and A. Rezaei. Monte Carlo Markov chain algorithms for sampling strongly Rayleigh distributions and determinantal point processes. Conference on Learning Theory, 2016.
  2. C. Li, S. Sra., and S. Jegelka. Fast mixing markov chains for strongly Rayleigh measures, DPPs, and constrained sampling. Advances in Neural Information Processing Systems (NIPS) 2016.
  3. C. Li, S. Jegelka, and S. Sra. Polynomial time algorithms for dual volume sampling. Advances in Neural Information Processing Systems (NIPS) 2017.
  4. Y. T. Lee and S. Vempala. Convergence Rate of Riemannian Hamiltonian Monte Carlo and Faster Polytope Volume Computation. 2017. (this is more a math paper though).
  5. J. Gorham and L. Mackey. Measuring sample quality with Stein's method. Advances in Neural Information Processing Systems (NIPS) 2017.
$\endgroup$
5
  • 1
    $\begingroup$ Interesting, thank you. Particularly interesting how it's mostly the spectral gap (relaxation time) rather than mixing time that is studied! $\endgroup$
    – Sam OT
    Jun 19, 2018 at 14:13
  • $\begingroup$ Well, there's a direct relation between the spectral gap and mixing time, given some precise analysis of the initialization; the works do study that. $\endgroup$
    – Suvrit
    Jun 19, 2018 at 15:11
  • 1
    $\begingroup$ Yeah, of course. In probability papers, it's pretty unusual to see someone upper bound the spectral gap and then say that the mixing time is upper bounded by that times $\log n$. At least, I haven't seen it very often. I did see in one of the references the informal statement "the spectral gap governs the mixing from a 'warm start'". Maybe people designing algorithms feel providing they choose their initial condition well enough they don't need to use the full (worst-case) mixing time, but just the spectral gap? $\endgroup$
    – Sam OT
    Jun 20, 2018 at 20:19
  • $\begingroup$ that's why i noted: "given some precise analysis of the initialization" -- $\endgroup$
    – Suvrit
    Jun 21, 2018 at 2:20
  • 1
    $\begingroup$ I wondered if you meant that. Of course, there is also a direct relation between the spectral gap $\gamma$ and the mixing time $t_{\text{mix}}$ via $$ \gamma^{-1} - 1 \le t_{\text{mix}} \le \gamma^{-1} \log \pi_{\text{min}}^{-1}. $$ How rigorous is the 'direct relation' given some analysis of the initialisation? $\endgroup$
    – Sam OT
    Jun 21, 2018 at 9:53
5
$\begingroup$

Mark Jerrum has rigorous results (bounds) on mixing times for Markov Chain Monte Carlo algorithms, as summarized in this presentation. In the context of deep learning, such bounds have been used in Layerwise Systematic Scan: Deep Boltzmann Machines and Beyond.

$\endgroup$
1
  • $\begingroup$ Thanks for the reference. I don't actually see how the latter paper uses the permanent, or really any of Jerrum's work. The approximating the permanent is interesting in of itself, though $\endgroup$
    – Sam OT
    Jun 19, 2018 at 14:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.