Abstract: 

Termination tests are central to scientific computing but are sometimes treated as an afterthought in machine learning,  often not even mentioned in published papers.  In this talk, termination tests will be proposed and analyzed for two core problems in machine learning where the termination question is important.  First, I will propose a new, simple, and computationally inexpensive termination test for constant step-size stochastic gradient descent (SGD) applied to binary classification with homogeneous linear predictors. Constant step-size SGD is a widely used but non-convergent algorithm, so the issue of termination is nontrivial.  Given the huge resource demands of machine learning (e.g., training a neural network has a carbon footprint equal to five times that of an automobile over its life), good termination tests in this regime have a larger environmental significance.  The second termination test in my talk applies to sum-of-norms (SON) clustering, a recent convex formulation of the classical clustering problem.  Identifying clusters in the SON formulation apparently requires exact knowledge of the optimizer, but all known algorithms are iterative and exact only in the infinite limit, so correct termination is central to correctness of the method.

Biography: 

Vavasis received a Bachelors in Mathematics from Princeton in 1984, a Masters (i.e., Part III of the Tripos) in Mathematics from Cambridge in 1985, and PhD in Computer Science from Stanford in 1989.  He was an assistant, then associate, then full professor of computer science at Cornell University from 1989 to 2006.  Since 2006 he has been a professor in the Department of Combinatorics and Optimization at University of Waterloo.  He has served as Associate Dean for Computing since 2017.  He has held summer or sabbatical positions at Argonne, Sandia, Bell Labs, Xerox PARC, NASA Ames and elsewhere.  He is a past winner of the Hertz Graduate Fellowship, Churchill Scholarship, Presidential Young Investigator award, and Guggenheim Fellowship.

For scheduling information, please contact Anna Stroup at astroup@cc.gatech.edu.