Title: “Good” computational methods for big data analytics: an gentle introduction on the information-based complexity theory

Abstract: Recent years have witnessed the rapid evolution of big data analytics. With the increasing volumes of data involved in modern-day research, it is critical to build new mathematical and statistical tools that are scalable to huge datasets and less prone to long computational time. Optimization has been an important computational tool for data analysis in various disciplines, and many problems in big data analytics can be modeled as nonlinear optimization. For any big data optimization problem, one would always look for a “good” algorithm for solving the optimization problem as “efficiently” as possible. How do we quantify an algorithm as “good”/”efficient” theoretically? In this talk, we will give a brief introduction on information-based complexity theory, a useful tool to study the theoretical performance limits of certain large-scale optimization algorithms. We will start with Nemirovski’s seminal results on the study of iterative algorithms for solving a large-scale linear system Ax=b, and then move to smooth convex optimization and other nonsmooth optimization models in image reconstruction and machine learning.