Theory Seminar

  • Professor
  • Computer Sciences Department
  • University of Wisconsin - Madison

Worst Case Analysis Meets Data Driven Optimization

Traditional algorithm design is geared towards worst-case instances and fails to exploit structure that may be present within typical instances. In recent years, data driven algorithm design has emerged as a powerful alternative, offering performance gains in many settings. This line of research develops techniques for tuning parameters and hyperparameters over classes of algorithms using data. But what is the right class of algorithms to optimize over? My work combines these two approaches to algorithm design and aims to identify parameterized classes of algorithms that are simultaneously (1) expressive enough to contain approximately optimal solutions in the worst case, and (2) simple enough to be efficiently learnable from data. I will describe this approach in the simplest algorithmic context -- search for a cheap solution within an unstructured space.

This talk is based on joint work with Evangelia Gergatsouli, Yifeng Teng, Christos Tzamos, and Ruimin Zhang.

Shuchi Chawla received her Ph.D. from Carnegie Mellon University and her B.Tech. from the Indian Institute of Technology, Delhi. She has held postdoctoral or visiting positions at Stanford University, Microsoft Research Silicon Valley, Microsoft Research Redmond, and the University of Washington. She is the recipient of an NSF Career award and a Sloan Foundation fellowship. She currently serves on the editorial boards of the SIAM Journal on Discrete Mathematics, ACM Transactions on Algorithms, and ACM Transactions on Economics and Computation. Shuchi is a member of the ACM SIGACT executive committee and the current chair of CATCS.

Faculty Host: Anupam Gupta

For More Information, Please Contact: