###### tags: `one-offs` `sampling` `polynomials`

# Polynomials and Sampling

**Overview**: In this note, I discuss the extent to which polynomials turn out to be useful in a sampling context.

## Densities, Potentials, and Ratios

Polynomials are ubiquitous, so it is natural to wonder how the presence of polynomials in sampling problems affects things. Actually, their relative convenience is somewhat variable:

1. In low dimensions, if a density takes the form of a polynomial, then simulation is easy.

2. In general dimensions, if a log-density takes the form of a polynomial, then this isn't necessarily useful.

3. In general dimensions, if a density takes the form of a rational function, then this isn't necessarily useful.

That is, when moving between different specifications of a problem, the utility of working with polynomials is quite brittle; you are easily back to the general task of sampling. Probably this is not too surprising in any big sense, but I found it worthwhile to reflect upon.

A related question which is potentially interesting: suppose that you have a sampling problem in which the log-density is strictly convex (perhaps in some certifiable way, e.g. involving sum-of-squares formulations). What sort of computational oracles would be useful in terms of developing an efficient sampling method for this target? In principle, we know of good diffusion processes in this context (as implied by e.g. the Brascamp-Lieb inequality), but these diffusions are not so easy to discretise and solve in general. Perhaps the polynomial case allows for some more robust approaches to work?

All of these thoughts are motivated by recent advances in Tensor Methods for convex optimisation, in which one tackles an optimisation problem by reduction to solving a sequence of (regularised) polynomial optimisation problems. So far, I have not seen anything analogous attempted in the context of simulation.