Decision & Control Seminar: Prof. Sean Meyn
Title: The Art of Freezing Fast: Exponential Convergence in Simulated Annealing
Abstract: In 1989, my family and I moved from the Australian National University to the University of Illinois, where I began my academic career. I had already heard about Bruce Hajek's remarkable research on simulated annealing, particularly his 1988 paper that continues to influence research on non-convex optimization nearly four decades later.
Simulated annealing is celebrated for its convergence guarantees, but notorious for its painfully slow convergence rates. We ask in this lecture, could this apparent limitation reflect a misaligned goal? Why should an optimization algorithm be required to converge to a global optimum, rather than simply find one?
Beginning with Hajek's insights we examine simulated annealing and related stochastic gradient methods through the lens of continuous-time Langevin dynamics. Theory and examples reveal that demanding convergence can make both classical simulated annealing and optimally tuned fixed-temperature methods extraordinarily slow.
We then turn to a different approach: separate exploration from exploitation, and remember the best solutions discovered. One or more noisy gradient-based processes explore the landscape, searching for regions from which deterministic gradient descent can reach a global optimizer. Rather than requiring the exploring processes to converge, we ask how quickly they can discover such regions, and how effectively repeated exploration and refinement can exploit these discoveries.
This viewpoint leads naturally to questions of temperature selection, restart strategies, and the design of exploration and exploitation epochs. We will discuss theoretical insights from first-hitting-time distributions, the replica-exchange approach of Dong and Tong, and recent numerical investigations of multi-temperature exploration.
The resulting objective is not convergence of the stochastic process, but a probably approximately correct (PAC) guarantee: finding a sufficiently good solution with high probability and controlled computational effort. Under suitable conditions, failure probabilities can decrease exponentially with computational work. Theory and numerical examples illustrate how this change in perspective can reduce the effort required for successful optimization by orders of magnitude.
Location & Time: CSL B02, November 11, 3:00PM-4:00PM
Reception outside CSL B02 at 2:30PM
Bio: Sean Meyn received the B.A. degree in mathematics from the University of California, Los Angeles (UCLA), in 1982 and the Ph.D. degree in electrical engineering from McGill University, Canada, in 1987 (with Prof. P. Caines, McGill University). He is now Professor and Robert C. Pittman Eminent Scholar Chair in the Department of Electrical and Computer Engineering at the University of Florida, the director of the Laboratory for Cognition & Control, and director of the Florida Institute for Sustainable Energy. His academic research interests include theory and applications of decision and control, stochastic processes, and optimization. He has received many awards for his research on these topics, and is a fellow of the IEEE.
He has held visiting positions at universities all over the world, including the Indian Institute of Science, Bangalore during 1997-1998 where he was a Fulbright Research Scholar. During his latest sabbatical during the 2006-2007 academic year he was a visiting professor at MIT and United Technologies Research Center (UTRC).
His award-winning 1993 monograph with Richard Tweedie, Markov Chains and Stochastic Stability, has been cited thousands of times in journals from a range of fields. The latest version is published in the Cambridge Mathematical Library.
For the past ten years his applied research has focused on engineering, markets, and policy in energy systems. He regularly engages in industry, government, and academic panels on these topics, and hosts an annual workshop at the University of Florida.