funsor icon indicating copy to clipboard operation
funsor copied to clipboard

Fix optimizer objective function for Gaussian variable elimination

Open fritzo opened this issue 6 years ago • 1 comments

Whereas the space complexity of a joint categorical distribution grows exponentially in the number of dimensions (aka variables), joint Gaussians grow only quadratically. So for example the tractability theorem is weaker for Gaussian models than discrete models. This is relevant for funsor.optimizer because opt_einsum's greedy objective is memory size assuming exponential growth (in compute_size_by_dict).

We should send a fix to opt_einsum to support a more general flop_count() function, possibly supporting non-integer sizes in their shapes. If this change is too intrusive upstream, we might simply fork their path optimizer for use in finsor. However it would be preferable to keep funsor simple and defer to opt_einsum wherever possible.

fritzo avatar Mar 03 '19 18:03 fritzo

Note that this is low priority, since even under the current objective function, the optimizer should do something reasonable for most real examples.

fritzo avatar Mar 06 '19 20:03 fritzo