In 1931-1932, Erwin Schrödinger studied a hot gas Gedankenexperiment (an instance of large deviations of the empirical distribution). Schrödinger's problem represents an early example of a fundamental inference method, the so-called maximum entropy method, having roots in Boltzmann's work and being developed in subsequent years by Jaynes, Burg, Dempster, and Csiszár. The problem, known as the Schrödinger bridge problem (SBP) with "uniform"prior, was more recently recognized as a regularization of the Monge-Kantorovich optimal mass transport (OMT) problem, leading to effective computational schemes for the latter. Specifically, OMT with quadratic cost may be viewed as a zerotemperature limit of the problem posed by Schrödinger in the early 1930s. The latter amounts to minimization of Helmholtz's free energy over probability distributions that are constrained to possess two given marginals. The problem features a delicate compromise, mediated by a temperature parameter, between minimizing the internal energy and maximizing the entropy. These concepts are central to a rapidly expanding area of modern science dealing with the so-called Sinkhorn algorithm, which appears as a special case of an algorithm first studied in the more challenging continuous space setting by the French analyst Robert Fortet in 1938-1940 specifically for Schrödinger bridges. Due to the constraint on end-point distributions, dynamic programming is not a suitable tool to attack these problems. Instead, Fortet's iterative algorithm and its discrete counterpart, the Sinkhorn iteration, permit computation of the optimal solution by iteratively solving the so-called Schrödinger system. Convergence of the iteration is guaranteed by contraction along the steps in suitable metrics, such as Hilbert's projective metric. In both the continuous as well as the discrete time and space settings, stochastic control provides a reformulation of and a context for the dynamic versions of general Schrödinger bridge problems and of their zero-temperature limit, the OMT problem. These problems, in turn, naturally lead to steering problems for flows of one-time marginals which represent a new paradigm for controlling uncertainty. The zero-temperature problem in the continuous-time and space setting turns out to be the celebrated Benamou-Brenier characterization of the McCann displacement interpolation flow in OMT. The formalism and techniques behind these control problems on flows of probability distributions have attracted significant attention in recent years as they lead to a variety of new applications in spacecraft guidance, control of robot or biological swarms, sensing, active cooling, and network routing as well as in computer and data science. This multifaceted and versatile framework, intertwining SBP and OMT, provides the substrate for the historical and technical overview of the field given in this paper. A key motivation has been to highlight links between the classical early work in both topics and the more recent stochastic control viewpoint, which naturally lends itself to efficient computational schemes and interesting generalizations.

Stochastic control liaisons: Richard Sinkhorn meets gaspard monge on a schrödinger bridge

Pavon M.
2021

Abstract

In 1931-1932, Erwin Schrödinger studied a hot gas Gedankenexperiment (an instance of large deviations of the empirical distribution). Schrödinger's problem represents an early example of a fundamental inference method, the so-called maximum entropy method, having roots in Boltzmann's work and being developed in subsequent years by Jaynes, Burg, Dempster, and Csiszár. The problem, known as the Schrödinger bridge problem (SBP) with "uniform"prior, was more recently recognized as a regularization of the Monge-Kantorovich optimal mass transport (OMT) problem, leading to effective computational schemes for the latter. Specifically, OMT with quadratic cost may be viewed as a zerotemperature limit of the problem posed by Schrödinger in the early 1930s. The latter amounts to minimization of Helmholtz's free energy over probability distributions that are constrained to possess two given marginals. The problem features a delicate compromise, mediated by a temperature parameter, between minimizing the internal energy and maximizing the entropy. These concepts are central to a rapidly expanding area of modern science dealing with the so-called Sinkhorn algorithm, which appears as a special case of an algorithm first studied in the more challenging continuous space setting by the French analyst Robert Fortet in 1938-1940 specifically for Schrödinger bridges. Due to the constraint on end-point distributions, dynamic programming is not a suitable tool to attack these problems. Instead, Fortet's iterative algorithm and its discrete counterpart, the Sinkhorn iteration, permit computation of the optimal solution by iteratively solving the so-called Schrödinger system. Convergence of the iteration is guaranteed by contraction along the steps in suitable metrics, such as Hilbert's projective metric. In both the continuous as well as the discrete time and space settings, stochastic control provides a reformulation of and a context for the dynamic versions of general Schrödinger bridge problems and of their zero-temperature limit, the OMT problem. These problems, in turn, naturally lead to steering problems for flows of one-time marginals which represent a new paradigm for controlling uncertainty. The zero-temperature problem in the continuous-time and space setting turns out to be the celebrated Benamou-Brenier characterization of the McCann displacement interpolation flow in OMT. The formalism and techniques behind these control problems on flows of probability distributions have attracted significant attention in recent years as they lead to a variety of new applications in spacecraft guidance, control of robot or biological swarms, sensing, active cooling, and network routing as well as in computer and data science. This multifaceted and versatile framework, intertwining SBP and OMT, provides the substrate for the historical and technical overview of the field given in this paper. A key motivation has been to highlight links between the classical early work in both topics and the more recent stochastic control viewpoint, which naturally lends itself to efficient computational schemes and interesting generalizations.
2021
File in questo prodotto:
File Dimensione Formato  
arXived SIREV revision.pdf

accesso aperto

Tipologia: Preprint (submitted version)
Licenza: Accesso libero
Dimensione 1.45 MB
Formato Adobe PDF
1.45 MB Adobe PDF Visualizza/Apri
20m1339982.pdf

accesso aperto

Tipologia: Published (publisher's version)
Licenza: Accesso libero
Dimensione 1.44 MB
Formato Adobe PDF
1.44 MB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11577/3391262
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 78
  • ???jsp.display-item.citation.isi??? 50
  • OpenAlex ND
social impact