# Reformulation as optimization on probability distributions

This is a "soft" question, in the sense that I'm looking for historical remarks and general commentary rather than a definite answer.

For compact $$X \in R^n$$ and $$f : R^n \to R$$ consider the problem $$\min_{x \in X} ~ f(x).$$

A common trick that I've stumbled upon in several applications is to look at a "probabilistic" but equivalent reformulation $$\min_{\mu \in P(X)} \int f(x) \, \mathrm{d}\mu(x),$$ where $$P(X)$$ denote the set of probability distributions over $$X$$.

I'm interested in history/old references on this "lifting" principle, where the idea is to artificially enlarge the solution space in order to gain some favorable properties (such as linearity or convexity).

A popular example is the linear programming formulation of optimal transport due to Kantorovich, but I wonder where this idea of "probabilistic reformulation" originated or was first used (maybe in statistical physics)?

Another example of this trick are policy gradient methods in reinforcement learning, for an explanation see this blog post: http://www.argmin.net/2018/02/20/reinforce/

• It is notable that the post you link to seems to think that the use of this technique in policy gradient methods is ill-advised. – R Hahn Jul 21 at 15:49

One thing that comes to mind is the modern approach to solving partial differential equations by looking for solutions that are distributions instead of only differentiable functions; see chapter 8 in Folland's Real Analysis, and chapters 6 through 8 in Rudin's Functional Analysis, for example. The connection is very close to a kind of dual to your example: distributions in this context are defined as continuous linear functionals on the space $$\mathcal{D}(\mathbb{R}^n)$$ of smooth, compactly supported functions on $$\mathbb{R}^n$$. Examples of such distributions include:
1. Evaluation at a point, $$\delta_x(f) = f(x)$$. This includes the famous Dirac point mass, $$\delta_0$$.
2. Integration against probability measures, $$f \mapsto \int f\,d\mu$$.
One benefit is that some problems have new distributional solutions that do not correspond to something like $$\mu = f\,dx$$ (for $$f$$ differentiable and $$L^1$$ and $$dx$$ the Lebesgue measure) including some problems that don't have a solution corresponding to any smooth function.