Interactions of Algebra, Statistics and Optimization
Loading...
Journal Title
Journal ISSN
Volume Title
School of Science 
Doctoral thesis (articlebased)
 Defence date: 20230719
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
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 logconcave densities. We show that there exists a fulldimensional 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: logconcave density estimation and graphical models. We show that the maximum likelihood logconcave 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 logconcave 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 gradientsolvable 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, FinlandThesis advisor
Kubjas, Kaie, Asst. Prof., Aalto University, Department of Mathematics and Systems Analysis, FinlandKeywords
logconcave density estimation, graphical models, gradientsolvable optimization, constrained optimization
Other note
Parts

[Publication 1]: Alexandros Grosdos, Alexander Heaton, Kaie Kubjas, Olga Kuznetsova, Georgy Scholten, MirunaStefana Sorea. Exact Solutions in LogConcave Maximum Likelihood Estimation. Advances in Applied Mathematics, Volume 143, 102448, February 2023.
Full text in Acris/Aaltodoc: http://urn.fi/URN:NBN:fi:aalto202211306679DOI: 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. Logconcave 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 pnorm Distance Degree. Submitted, May 2021.
DOI: 10.48550/arXiv.2105.07785 View at publisher