|Stochastic Systems Group|
Regularized Online Optimization: Tracking Regret, Risk Bounds,
and Applications to Online Ising Model Selection
Online optimization methods are useful in a variety of applications with sequential observations of a dynamic environment. Often such methods are designed to minimize an accumulated loss metric, and the analysis techniques are appealing because of their applicability in settings where observations cannot be considered independent or identically distributed, and accurate knowledge of the environmental dynamics cannot be assumed. However, such analyses may mask the role of regularization and adaptivity to environmental changes. This work explores regularized online optimization methods and presents several novel performance bounds. Tracking regret bounds relate the accumulated loss of such an algorithm with that of the best possible dynamic estimate that could be chosen in a batch setting, and risk bounds quantify the roles of both the regularizer and the variability of the (unknown) dynamic environment. The efficacy of the method is demonstrated in an online Ising model selection context applied to U. S. Senate voting data.
Rebecca Willett is an assistant professor in the Electrical and Computer Engineering Department at Duke University. She completed her PhD in Electrical and Computer Engineering at Rice University in 2005. Prof. Willett received the National Science Foundation CAREER Award in 2007, is a member of the DARPA Computer Science Study Group, and received an Air Force Office of Scientific Research Young Investigator Program award in 2010. Prof. Willett has also held visiting researcher positions at the Institute for Pure and Applied Mathematics at UCLA in 2004, the University of Wisconsin-Madison 2003-2005, the French National Institute for Research in Computer Science and Control (INRIA) in 2003, and the Applied Science Research and Development Laboratory at GE Healthcare in 2002. Her research interests include network and imaging science with applications in medical imaging, wireless sensor networks, astronomy, and social networks. Additional information, including publications and software, are available online at http://www.ee.duke.edu/~willett/.
Problems with this site should be emailed to firstname.lastname@example.org