Research Workshop

The Multifaceted Complexity of Machine Learning

The Multifaceted Complexity of Machine Learning

April 12-16, 2021

This workshop will take place online.


  • Avrim Blum (Toyota Technological Institute of Chicago)
  • Olgica Milenkovic (Electrical and Computer Engineering, UIUC)
  • Lev Reyzin (Mathematics, UIC)
  • Matus Telgarsky (Computer Science, UIUC)
  • Rebecca Willett (Statistics and Computer Science, Chicago)


Modern machine learning (ML) methods, coupled with new optimization and statistical inference strategies, have demonstrated an unprecedented potential to solve challenging problems in computer vision, natural language processing, healthcare, agriculture, and other application areas. However, foundational understanding regarding how and when certain methods are adequate to use and most effective in solving tasks of interest is still emerging. A central question at the heart of this endeavor is to understand the different facets of the complexity of machine learning tasks. These include sample complexity, computational complexity, Kolmogorov complexity, oracle complexity, memory complexity, model complexity, and the stationarity of the learning problem. This workshop will focus on developing a better understanding of these different types of complexity within machine learning, how they can be jointly leveraged to understand the solvability of learning problems, and fundamental trade-offs among them.

Confirmed speakers

  • Jayadev Acharya (Cornell University)
  • Peter Bartlett (UC Berkeley)
  • Kamalika Chaudhuri (UC San Diego)
  • Moustapha Cisse
  • Jelena Diakonikolas (University of Wisconsin Madison)
  • Vitaly Feldman (Apple)
  • Surbhi Goel (Microsoft Research)
  • Daniel Hsu (Columbia University)
  • Stephanie Jegelka (MIT)
  • Adam Klivans (University of Texas at Austin)
  • Aryeh Kontorovich (Ben-Gurion University)
  • Samory Kpotufe (Columbia University)
  • Po-Ling Loh (University of Wisconsin Madison)
  • Andrei Risteski (Carnegie Mellow University)
  • Tselil Schramm (Stanford University)
  • Gregory Valiant (Stanford University)
  • Rachel Ward (University of Texas at Austin)

In order to apply for this program, you must first register for an account and then login. Refreshing this page should then bring up the application form. Note that, due to requirements related to our NSF grant, you will only be able to apply for funding to attend if you have linked an ORCID® iD to your account. You will have an opportunity to create (if necessary) and connect an ORCID iD to your account once you’ve registered.