Geometry plays a crucial role in machine learning. We study the geometric properties of machine learning problems and use that information to develop new algorithms that are accurate and efficient. We present three works that lie at the intersection of machine learning and geometry, and we hope to promote more research on geometry-inspired machine learning methods.

We first introduce \textit{geometric policy iteration}~(GPI), a new dynamic programming approach for finite Markov decision process. Recently discovered polyhedral structures of the value function for finite discounted Markov decision processes (MDP) shed light on understanding the success of reinforcement learning. We investigate the value function polytope in greater detail and characterize the polytope boundary using a hyperplane arrangement. We further show that the value space is a union of finitely many cells of the same hyperplane arrangement, and relate it to the polytope of the classical linear programming formulation for MDPs. Inspired by these geometric properties, we propose GPI to solve discounted MDPs. GPI updates the policy of a single state by switching to an action that is mapped to the boundary of the value function polytope, followed by an immediate update of the value function. This new update rule aims at a faster value improvement without compromising computational efficiency. Moreover, our algorithm allows asynchronous updates of state values which is more flexible and advantageous compared to traditional policy iteration when the state set is large. We prove that the complexity of GPI achieves the best known bound $\bigO{\frac{|\actions|}{1 - \gamma}\log \frac{1}{1-\gamma}}$ of policy iteration and empirically demonstrate the strength of GPI on MDPs of various sizes.

In the second project, we consider the \emph{integer feasibility problem}, the challenge of deciding whether a system of linear equations and inequalities has a solution with integer values. This is a famous NP-complete problem with applications in many areas of Mathematics and Computer Science. We show that the integer feasibility problem can be transformed into a 3-D tensor game which we call the \textit{Feasibility Game}~(FG). To win the game the player must find a path between the initial state and a final terminal winning state, if one exists. Finding such a winning state is equivalent to solving the integer feasibility problem. The key algebraic ingredient is a Gr\"obner basis of the toric ideal for the underlying axial transportation polyhedron. The Gr\"obner basis can be seen as a set of connecting moves (actions) of the game. We then propose a novel RL approach that trains an agent to predict moves in continuous space to cope with the large size of action space. The continuous move is then projected onto the set of legal moves so that the path always leads to valid states. As a proof of concept we demonstrate in experiments that our agent can play well the simplest version of our game for 2-way tables. Our work highlights the potential to train agents to solve non-trivial mathematical queries through contemporary machine learning methods used to train agents to play games.

% In the third project, we applied persistence-based clustering for microglia segmentation which is a critical problem in biology and immunology. Light microscopy methods have continued to advance allowing for unprecedented analysis of various cell types in tissues including the brain. Although the functional state of some cell types such as microglia can be determined by morphometric analysis, techniques to perform robust, quick, and accurate measurements have not kept pace with the amount of imaging data that can now be generated. Here we present PrestoCell, a novel use of persistence-based clustering to segment cells in light microscopy images, as a customized Python-based tool that leverages the free visualization tool Napari. In evaluating and comparing PrestoCell to several existing tools, including a commercial machine-learning implementation, we demonstrate that PrestoCell produces image segmentations that rival or exceed existing solutions. In particular, our use of cell nuclei information resulted in the ability to correctly segment individual cells that were interacting with one another, increasing the accuracy of the segmentation. These benefits are in addition to the simplified graphically based user refinement of cell masks that does not require expensive commercial software licenses. We further demonstrate that PrestoCell can complete image segmentation in large samples from light sheet microscopy, allowing quantitative analysis of these large datasets. As an open-source program that leverages freely available visualization software, with minimum computer requirements, we believe that PrestoCell can significantly increase the ability of users without data or computer science expertise to perform complex image analysis.

In the third work, we develop \textit{PrestoCell} which is a Python-based topological framework for segmenting objects with complex shapes. The main contribution of this work is the use of persistence-based clustering~(PBC) to generate segmentations that are topologically correct. Specifically, we use PBC to segment microglia whose 0-d homology is 1 (one connected component), and higher-order homology is 0. PBC, as an unsupervised method, is able to generate high-quality clusters that can be easily improved by some post-processing steps. Our framework is able to take as input very large 3D light microscopy imaging data where a single input volume can contain hundreds of microglia and nuclei. We use PBC to quickly generate candidate microglia clusters which are later refined by the coupled nuclei information. We present the machine-generated segmentation in the free visualization tool Napari. In evaluating and comparing PrestoCell to several existing tools, including a commercial machine-learning implementation, we demonstrate that PrestoCell produces image segmentations that rival or exceed existing solutions. In particular, our use of cell nuclei information resulted in the ability to correctly segment individual cells that were interacting with one another, increasing the accuracy of the segmentation. These benefits are in addition to the simplified graphically based user refinement of cell masks that does not require expensive commercial software licenses. We further demonstrate that PrestoCell can complete image segmentation in large samples from light sheet microscopy, allowing quantitative analysis of these large datasets. As an open-source program that leverages freely available visualization software, with minimum computer requirements, we believe that PrestoCell can significantly increase the ability of users without data or computer science expertise to perform complex image analysis.

This dissertation discusses several problems motivated by the simplex method, one of the most influential algorithms in optimization.

First, every generic linear functional $f$ on a convex polytope $P$ induces an orientation on the graph of $P$. We introduce the notions of $f$-arborescence and $f$-monotone path on$P$, as well as a natural graph structure on the vertex set of $f$-monotone paths on the resulting directed graphs. These combinatorial objects are proxies for pivot rules and simplex method pivot steps. We bound the number of $f$-arborescences, the number of $f$-monotone paths, and the diameter of the graph of $f$-monotone paths for polytopes $P$ in terms of their dimension and number of vertices or facets. We also sample the distribution of lengths of monotone paths over different classes of random polytopes.

Second, inspired by the simplex and the criss-cross methods, we present an update on the search for bounds on the diameter of the cocircuit graph of an oriented matroid. We review the diameter problem and show the diameter bounds of general oriented matroids reduce to those of uniform oriented matroids. We give the latest exact bounds for oriented matroids of low rank and low corank, and for all oriented matroids with up to nine elements. For arbitrary oriented matroids, we present an improvement to a quadratic bound of Finschi. Our discussion highlights an old conjecture that states a linear bound for the diameter is possible. On the positive side, we show the conjecture is true for oriented matroids of low rank and low corank, and, verified with computers, for all oriented matroids with up to nine elements. On the negative side, our computer search showed two natural strengthenings of the main conjecture are false.

Finally, we discuss a data-driven, empirically-based framework to make algorithmic decisions or recommendations without expert knowledge. We improve the performance of the simplex method by selecting different pivot rules for different linear programs. We train machine learning methods to select the optimal pivot rule for given data without expert opinion. We use two types of techniques, neural networks and boosted decision trees. Our selection framework recommends various pivot rules that improve overall total performance over just using a default fixed pivot rule. Here our recommendation system is best when using gradient boosted trees. Our data analysis also shows that the number of iterations by steepest-edge is no more than four percent from the optimal selection.

The thesis is structured as follows: In Chapter 1 we introduce the readers to the basic notions in Sections 1.1 and 1.2, and summarize our main results in Sections 1.3, 1.4 and 1.5. Section 2.1 through Section 2.4 prove our stated bounds on number of arborescences, monotone paths, and the diameter of flip graphs; Section 2.5 demonstrates the distributions related to length of monotone paths, and we conclude Chapter 2 with some open problems in Section 2.6. Chapter 3 proves the diameter conjecture in low rank and corank oriented matroids and shows the constructions of counterexamples. In Chapter 4 we show how we generate the training data and the comparison between different machine learning models to select pivot rules. In Appendix, we present the pseudocode for converting oriented matroids in different representations and for computing different features on directed polytope graphs.

A foundational problem in optimization is that of linear programming, the problem of maximizing a linear function subject to linear inequality constraints. Geometrically, this problem corresponds to finding the highest point in some direction on a polytope. The simplex method, one of the oldest and most famous algorithms for linear programming, does this by following a path on the graph of the polytope such that at each step the linear objective function value increases. Such a path is called a monotone path. The simplex method could potentially follow any monotone path on the polytope. For implementation, one must specify a rule to choose such a path called a pivot rule. The goal of this thesis is to study the geometric combinatorics of monotone paths and pivot rules for linear programs and bound the performance of the simplexmethod.

We first show performance bounds for the simplex method in the case of 0/1-polytopes. In thiscase, we introduce two pivot rules guaranteed to follow paths of length at most the dimension of the polytope matching optimal bounds of Naddef. We extend these results to d-dimensional (0, k)-lattice polytopes finding a path following algorithm using the simplex method as a subroutine guaranteed to follow a path of length at most 2dk asymptotically matching the best known bounds on diameters of their graphs due to Kleinschmidt and Onn and improving upon the best known bounds in this framework due to Del Pia and Michini. It remains open whether there is a pivot rule for the simplex method that guarantees even a polynomial in d and k many steps.

In the remainder of this thesis, we study two constructions: the monotone path polytope andpivot rule polytope. The monotone path polytope, introduced by Billera and Sturmfels, is a geometric model for the spaces of all monotone paths on a polytope that could be chosen by a shadow pivot rule for a fixed linear program. We study these on examples of polytopes fundamental in algebraic combinatorics such as cross-polytopes and products of simplices. We also study how monotone path polytopes are affected by other constructions such as prisms and pyramids. In each case, we find rich combinatorics with surprising new interpretations in terms of the simplex method. The pivot rule polytope is an alteration of the monotone path polytope to classify a broad set of pivot rules we study in detail called normalized weight pivot rules, both of which are defined in this thesis. In particular, we show that if a polynomial time version of the simplex method exists, there must be a normalized weight pivot rule guaranteed to always choose polynomial length paths. Finally, we study this construction on examples finding new realizations of polytopes in algebraic combinatorics such as the associahedron.

We investigate the problem of computing tensor product multiplicities for complex semisimple Lie algebras. Even though computing these numbers is #P-hard in general, we show that when the rank of the Lie algebra is assumed fixed, then there is a polynomial-time algorithm, based on counting lattice points in polytopes. In fact, for Lie algebras of type A, there is an algorithm, based on the ellipsoid algorithm, to decide when the coefficients are nonzero in polynomial time for arbitrary rank. Our experiments show that the lattice point algorithm is superior in practice to the standard techniques for computing multiplicities when the weights have large entries but small rank. Using an implementation of this algorithm, we provide experimental evidence for two conjectured generalizations of the saturation property of Littlewood-Richardson coefficients. One of these conjectures seems to be valid for types B, C, and D.