Typically Variational Inference relies on taking gradient steps on KL divergence between the variational and true posterior, or on the ELBO. This does not seem valid when variational parameters are discrete (since gradients wrt those arguments are not defined). How can we perform VI on discrete variational parameters?


Well, in general this is an instance of a discrete optimization problem, and in general there are no methods more efficient than brute-force search over all possible values of these parameters. In some special cases though, one might use problem's structure to be much better. This is studied by the field of Combinatorial Optimization. In some cases when efficient exact solutions are unknown, there exist good approximate ones.

There are practical heuristics such as Evolutionary algorithms which are not guaranteed to be better than an exhaustive search, but might lead to a decent solution (in a short amount of time).

However, design of a variational approximation in VI is arbitrary, and it makes sense to choose its family so as to make the optimization process efficient and tractable. In practice, variational approximations are almost always parametrized by continuous parameters and thus allow gradient-based optimization.

  • $\begingroup$ how about using continuous approximations via the Gumbel-Softmax trick or concrete distributions? $\endgroup$ – Dionysis M Sep 27 '19 at 23:38
  • $\begingroup$ @DionysisM, Gumbel-Softmax solves an unrelated problem. It assumes you have discrete random variables parametrized by continuous parameters and it relaxes these discrete r.v. into continuous ones. Crucially, parameters are continuous all along. $\endgroup$ – Artem Sobolev Sep 28 '19 at 13:26
  • $\begingroup$ One could attempt using Gumbel-Softmax for discrete parameters, but the problem here is that discrete parameters are not random variables, they are deterministic values, and thus the particular technique of G-S does not bring anything. You could consider other relaxations though – this is also a part of approximate discrete optimization. $\endgroup$ – Artem Sobolev Sep 28 '19 at 13:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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