Abhishek Sinha

EE 6180: Advanced Topics in Artificial Intelligence

Piazza signup link (Access Code: ee6180)


Venue: Online
Slot: E (Three classes per week, no class on Thursday)
Office Hours: TBD


In Fall 2020, I am offering an advanced graduate-level course on Artificial Intelligence with an emphasis on the theoretical foundations of Machine Learning. This course will tentatively cover the following topics.

A. Review of Information Measures

  • Entropy, KL-Divergence and its properties, Submodularity
  • Gibb’s, (Strong) Data Processing, Fano’s inequality
  • Concentration Inequalities
    • Martingale Method, Mcdiarmid’s inequality, Sanov’s Theorem, Donsker-Varadhan's variational lemma
  • Interactive Data Analysis

B. The PAC Learning Set Up

  • Introduction to PAC learning
  • Uniform Convergence
  • The No-Free-Lunch Theorem
  • VC-dimension
  • Algorithms: Decision Trees, AdaBoost

C. Fundamental limits of Estimation and Testing

  • Minimax Lower Bounds
    • Fano’s method
    • LeCam’s method
    • Assouad’s method
  • Applications
    • Community detection in Stochastic Block Model
    • Sparse recovery
    • Non-parametric regression

D. Bandits and Online Learning

  • Stochastic, Adversarial, Linear Bandits
  • Bandit Algorithms (UCB, EXPx)
  • Information Theoretic Regret lower bounds
  • Contextual Bandits and Experts
  • Online Convex Optimization

E. Further Topics

  • Privacy and Differential Privacy
  • Entropy Estimation
  • Structure Learning in graphical models
    • Chow-Liu algorithm


Evaluations

Problem-solving will be our primary vehicle for learning the material. We will have bi-weekly problem sets, a mid-term and a final project. The final grade will be a weighted average of these four components as detailed below:
  • Problem Sets (40%)
  • Take-home Mid-term (20%)
  • Reading/Research project (25%)
  • Scribing (15%)


Problem Sets

Prerequisites

  • Strong background in Probability Theory and sufficient mathematical maturity.
  • Prior exposure to elementary Information theory will be helpful but not mandatory.


References

We will not follow any one particular source, in general. However, the following references will be useful