Information-theoretic Lower Bounds in Data Science“Grant me the serenity to accept the things I cannot change, courage to change the things I can, and wisdom to know the difference,” Reinhold Niebuhr (1892–1971) Description:
Much scientific research is devoted to providing constructive and explicit solutions to real problems. However, there is another important line of research aimed at an understanding of what is impossible. Impossibility results allow to characterize fundamental limits, spot unrealistic targets, provide optimality guarantees for constructive procedures, and recognize bottlenecks in problem formulations that may call for improvement. Establishing impossibility results is a common task in various fields of data science; for example, what is the smallest error one could achieve in a classification problem? How many iterations do we need to approach the optimal solution in optimization? How much computation or communication or memory do we need to learn the distribution of the data? What is the optimal data querying or collection scheme in online and reinforcement learning? What is the best representation or coding of a message in a given communication channel? Prerequisites:
EE 278, or CS 229T, or STATS 300A, or equivalent, or Instructor’s permission. This course will be mostly self-contained, but requires mathematical maturity at a graduate level. Background in statistics, information theory, machine learning, and/or optimization is recommended. Course requirements:
|