Learning/Optimization over abstract non-manifold structures: A case in biological data analysis

Biological data analysis often involves optimization problems where the objective function is efficient to compute, but the feasible set is of complex combinatorial and geometric nature. In particular, phylogenetic studies involve inferring tree structures that depict evolutionary relationships, from information at their leaf nodes (DNA sequences of existing species, for example). One approach that works well in theory and practice models evolution as a parametric stochastic process and performs maximum likelihood analysis. While the likelihood function is easy to compute, the set of all tree structures over a fix number of leaves has high dimension and is, in fact, a non-manifold. Despite these obstacles, there are known discrete algorithms that solve this problem with efficient runtime and sample complexity. In this talk, we visit known results on the algebro-geometric properties of this space and expand on how smooth optimization can be a novel tool to design even more efficient algorithms/heuristics for these problems. Based on on-going work with Stefanie Jegelka.