Interactions of Algebra, Statistics and Optimization

Thumbnail Image
Files
isbn9789526413211.pdf (1.48 MB)
Journal Title
Journal ISSN
Volume Title
School of Science | Doctoral thesis (article-based) | Defence date: 2023-07-19
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Author
Date
2023
Department
Matematiikan ja systeemianalyysin laitos
Department of Mathematics and Systems Analysis
Major/Subject
Mcode
Degree programme
Language
en
Pages
110 + app. 124
Series
Aalto University publication series DOCTORAL THESES, 95/2023
Abstract
This thesis studies the interplay between algebra and statistics in constrained optimization. It contains four papers: Publications I - III study constrained optimization from the perspective of maximum likelihood estimation in statistics, and Publication IV looks at the optimization problems with polynomial constraints. In maximum likelihood estimation, one observes a data sample and computes the probability density that maximizes the likelihood of observing the given set of data points. As an additional property, we allow assigning different weights to each observation in the sample, for example, to reflect their relative importance. In Publication I, we study the complexity of computing the optimal solution over the family of log-concave densities. We show that there exists a full-dimensional set of weights, such that the corresponding optimal solution is transcendental whenever the data sample consists of rational points. In Publication II, we look at the family of Gaussian distributions and impose that the random variables satisfy certain dependence relations induced by graphs with undirected, directed and bidirected edges. We develop a package GraphicalModelsMLE for the computer algebra system Macaulay2 and discuss interesting applications to enable further research in this field. In Publication III, we take the first step to combine two rich research areas: log-concave density estimation and graphical models. We show that the maximum likelihood log-concave density estimator exists and is unique when the underlying undirected graph is chordal, the number of data points is strictly larger than the size of the largest clique of the graph, and all feasible densities can be written as a product of non- negative log-concave functions, each corresponding to a clique of the graph. Moreover, this estimator is consistent when the undirected graph is a disjoint union of cliques under mild assumptions on the true density. Optimization with polynomial constraints is another rich area of research that is interesting theoretically and useful in various applications. We focus on the case where the objective function has some desirable algebraic properties and the feasible set is the zero set of a system of polynomial equations. Specifically, in Publication IV, we study gradient-solvable objective functions parametrized by data. Roughly speaking, gradient solvability means there exists an explicit formula in radicals that connects the data points and the critical points. We show that there is a finite number of critical points whenever the data is sufficiently general.
Description
Supervising professor
Kubjas, Kaie, Asst. Prof., Aalto University, Department of Mathematics and Systems Analysis, Finland
Thesis advisor
Kubjas, Kaie, Asst. Prof., Aalto University, Department of Mathematics and Systems Analysis, Finland
Keywords
log-concave density estimation, graphical models, gradient-solvable optimization, constrained optimization
Other note
Parts
  • [Publication 1]: Alexandros Grosdos, Alexander Heaton, Kaie Kubjas, Olga Kuznetsova, Georgy Scholten, Miruna-Stefana Sorea. Exact Solutions in Log-Concave Maximum Likelihood Estimation. Advances in Applied Mathematics, Volume 143, 102448, February 2023.
    Full text in Acris/Aaltodoc: http://urn.fi/URN:NBN:fi:aalto-202211306679
    DOI: 10.1016/j.aam.2022.102448 View at publisher
  • [Publication 2]: Carlos Améndola, Luis David García Puente, Roser Homs Pons, Olga Kuznetsova, Harshit J Motwani. Computing MLEs for Gaussian Graphical Models in Macaulay2. Journal of Software for Algebra and Geometry, Volume 12, pages 1–10, 2022.
    DOI: 10.2140/jsag.2022.12.1 View at publisher
  • [Publication 3]: Kaie Kubjas, Olga Kuznetsova, Elina Robeva, Pardis Semnani, Luca Sodomaco. Log-concave Density Estimation in Undirected Graphical Models. Submitted, June 2022.
    DOI: 10.48550/arXiv.2206.05227 View at publisher
  • [Publication 4]: Kaie Kubjas, Olga Kuznetsova, Luca Sodomaco. Algebraic degree of optimization over a variety with an application to p-norm Distance Degree. Submitted, May 2021.
    DOI: 10.48550/arXiv.2105.07785 View at publisher
Citation
Permanent link to this item
https://urn.fi/URN:ISBN:978-952-64-1321-1
Collections
[diss] Perustieteiden korkeakoulu / SCI