Workshop — EnCORE Workshop on Computational vs Statistical Gaps in Learning and Optimization

In this workshop, we will explore the statistical and computational requirements for solving various learning problems. The statistical limit is the minimum number of samples needed to solve a learning problem. In contrast, the computational limit is the minimum number of samples required for the problem to be solvable by an efficient algorithm. There is much research on the statistical requirements for many important learning problems, but the computational requirements are less well-understood. We often have large gaps between the two for several important problems (e.g., sparse linear regression). In addition, there are also gaps in our understanding of the costs of various constraints on learning, such as privacy, fairness, interpretability, robustness, and parallelization. This workshop will provide a forum to discuss the latest research and develop new ideas on the above questions. It will help build bridges between different disciplines, such as applied mathematics, statistics, optimization, and theoretical computer science, which will lead to more effective solutions to challenges in statistical inference.