• A
• A
• A
• ABC
• ABC
• ABC
• А
• А
• А
• А
• А
Regular version of the site
Menu

Estimating Probability Distributions through Gradient Optimization over the Wasserstein Space

Student: Ilya Semenkov

Supervisor:

Faculty: Faculty of Computer Science

Educational Programme: Data Science (Master)

Year of Graduation: 2021

This work is dedicated to the task of estimating an absolutely continuous probability measure in context of online optimization in the Wasserstein space. Moreover, in the general statement of the considered problem it is assumed that a measure might insignificantly change in time between iterations. To achieve an effective algorithm for solving this task, the problem was restated in the optimal transport terms. The connection between the Wasserstein distance and optimal transport was used for that. During the problem statement entropical regularization was added to increase the efficiency of the algorithm. It was followed by the usage of the theorem about a duality of the optimal transport problem. After that, it became possible to use c-transforms of Kantorovich potentials. That led to the simplification of the task into a minimax optimization in finite-dimensional space. It was proven that this problem belongs to the class of Nonconvex-Concave Minimax optimization. Based on the gradient descent ascent algorithm, which is widely used in similar tasks, the algorithm for the estimation of a probability density in online optimization framework was developed. Further, this algorithms was programmed. To evaluate its quality a series of tests was held using different generated samples and true distributions. Particularly, tests were done for normal, exponential and power law distributions. Furthermore, algorithm’s behavior was tested using datasets generated by a normal distributions with monotonically changing means between iterations; and by an exponential distribution with the addition of a noise random variable into parameter’s value (each datapoint was generated with a parameter with different value of a noise random variable). Algorithm shown multiple significant results on a multiple used datasets. Keywords: estimating distribution from a sample, semidiscrete optimal transport, online learning, nonidentical data distribution.

Student Theses at HSE must be completed in accordance with the University Rules and regulations specified by each educational programme.

Summaries of all theses must be published and made freely available on the HSE website.

The full text of a thesis can be published in open access on the HSE website only if the authoring student (copyright holder) agrees, or, if the thesis was written by a team of students, if all the co-authors (copyright holders) agree. After a thesis is published on the HSE website, it obtains the status of an online publication.

Student theses are objects of copyright and their use is subject to limitations in accordance with the Russian Federation’s law on intellectual property.

In the event that a thesis is quoted or otherwise used, reference to the author’s name and the source of quotation is required.