28 January 2021 in Foundations of Computational Mathematics
2 April 2021 in Proceedings of the IEEE
Tropical geometry is a relatively recent field in mathematics and computer science, combining elements of algebraic geometry and polyhedral geometry. The scalar arithmetic of its analytic part preexisted in the form of max-plus and min-plus semiring arithmetic used in finite automata, nonlinear image processing, convex analysis, nonlinear control, optimization, and idempotent mathematics. Tropical geometry recently emerged in the analysis and extension of several classes of problems and systems in both classical machine learning and deep learning. Three such areas include: 1) deep neural networks with piecewise linear (PWL) activation functions; 2) probabilistic graphical models; and 3) nonlinear regression with PWL functions. In this article, we first summarize introductory ideas and objects of tropical geometry, providing a theoretical framework for both the max-plus algebra that underlies tropical geometry and its extensions to general max algebras. This unifies scalar and vector/signal operations over a class of nonlinear spaces, called weighted lattices, and allows us to provide optimal solutions for algebraic equations used in tropical geometry and generalize tropical geometric objects. Then, we survey the state of the art and recent progress in the aforementioned areas. First, we illustrate a purely geometric approach for studying the representation power of neural networks with PWL activations. Then, we review the tropical geometric analysis of parametric statistical models, such as HMMs; later, we focus on the Viterbi algorithm and related methods for weighted finite-state transducers and provide compact and elegant representations via their formal tropical modeling. Finally, we provide optimal solutions and an efficient algorithm for the convex regression problem, using concepts and tools from tropical geometry and max-plus algebra. Throughout this article, we also outline problems and future directions in machine learning that can benefit from the tropical-geometric point of view.
1 August 2024 in Mathematics of Operations Research
Subgradient methods comprise a fundamental class of nonsmooth optimization algorithms. Classical results show that certain subgradient methods converge sublinearly for general Lipschitz convex functions and converge linearly for convex functions that grow sharply away from solutions. Recent work has moreover extended these results to certain nonconvex problems. In this work, we seek to improve the complexity of these algorithms by asking the following question. Is it possible to design a superlinearly convergent subgradient method? We provide a positive answer to this question for a broad class of sharp semismooth functions. Funding: The research of D. Davis was supported by the Division of Mathematical Sciences [Grant 2047637] and the Alfred P. Sloan Foundation.
3 February 2025 in Journal of Computational Physics