LSB: Local Self-Balancing MCMC in Discrete Spaces

@InProceedings{pmlr-v162-sansone22a,
  title = 	 {{LSB}: Local Self-Balancing {MCMC} in Discrete Spaces},
  author =       {Sansone, Emanuele},
  booktitle = 	 {Proceedings of the 39th International Conference on Machine Learning},
  pages = 	 {19205--19220},
  year = 	 {2022},
  editor = 	 {Chaudhuri, Kamalika and Jegelka, Stefanie and Song, Le and Szepesvari, Csaba and Niu, Gang and Sabato, Sivan},
  volume = 	 {162},
  series = 	 {Proceedings of Machine Learning Research},
  month = 	 {17--23 Jul},
  publisher =    {PMLR},
  pdf = 	 {https://proceedings.mlr.press/v162/sansone22a/sansone22a.pdf},
  url = 	 {https://proceedings.mlr.press/v162/sansone22a.html},
  abstract = 	 {We present the Local Self-Balancing sampler (LSB), a local Markov Chain Monte Carlo (MCMC) method for sampling in purely discrete domains, which is able to autonomously adapt to the target distribution and to reduce the number of target evaluations required to converge. LSB is based on (i) a parametrization of locally balanced proposals, (ii) an objective function based on mutual information and (iii) a self-balancing learning procedure, which minimises the proposed objective to update the proposal parameters. Experiments on energy-based models and Markov networks show that LSB converges using a smaller number of queries to the oracle distribution compared to recent local MCMC samplers.}
}