SILO: Convex analysis at infinity: An introduction to astral space

Abstract

Not all convex functions have finite minimizers; some can only be minimized by a sequence as it heads to infinity, making it much harder, for instance, to prove convergence. This work develops an expansive new theory for understanding such minimizers at infinity, introducing astral space, a compact extension of Euclidean space to which such points at infinity have been added. Astral space is constructed to be as small as possible while still ensuring that all linear functions can be continuously extended to the new space. Astral space is especially compatible with standard convex analysis and is meant to provide the foundation for a more complete theory. Although not a vector space, nor even a metric space, astral space is nevertheless so well-structured as to allow useful and meaningful extensions of the most important concepts from convex analysis, including convexity of sets and functions, conjugacy, separation theorems, subdifferentials, as well as central topics from optimization and applications. Applied to widely used algorithms, these tools afford simplified proofs of convergence, even when the only minimizers are at infinity.

This is joint work with Miroslav Dudík and Matus Telgarsky.

Bio

Robert Schapire is a Partner Researcher at Microsoft Research in New York City. He received his PhD from MIT in 1991. After a short postdoc at Harvard, he joined the technical staff at AT&T Labs (formerly AT&T Bell Laboratories) in 1991. In 2002, he became a Professor of Computer Science at Princeton University. He joined Microsoft Research in 2014. His awards include the 1991 ACM Doctoral Dissertation Award, the 2003 Gödel Prize, and the 2004 Kanelakkis Theory and Practice Award (both of the last two with Yoav Freund). He is a fellow of the AAAI, and a member of both the National Academy of Engineering and the National Academy of Sciences. His main research interest is in theoretical and applied machine learning. He is the co-author most recently of Astral Space: Convex Analysis at Infinity.