Yury Polyanskiy         Associate Professor         (EECS)               Curriculum Vitae               Publications & Preprints               Other

Information Theoretic Methods in Statistics and Computer Science

Class notes and materials (2019-2020)

• This page contains some supplementary materials for a 10-hour course taught by Y. Polyanskiy in EPFL'2019 and ENSAE CREST'2020.
• The notes are in rather preliminary form and are only useful in conjunction with the actual lectures given. Apologies for a number of typos, missing references etc.
• Lecture 1: f-divergences.
  • Define entropy, divergence and f-divergence
  • Special properties of Shannon measures: submodularity, chain rule
  • Shearer's lemma. Counting subgraphs.
  • Data-processing inequality (DPI) for f-divergence
  • Fano's inequality from DPI
  • f-information and subadditivity
• Lecture 2: DPI and statistics.
• Importance of χ²-divergence.
• Most f-divergences are locally χ²-divergence
• Application to density/pmf estimation
• Convexity of D_f and convex duality
• Variational representation of D_f
• HCR lower bound
• Most f-divergences are locally Fisher-information
• Cramer-Rao lower bound
• Short summary of Lectures 1-2 (actual material covered in L1 in the CREST course).
• Lecture 3: Strong DPI and directed information percolation.
  • Computation via noisy gates and von Neumann theorem
  • Evans-Schulman impossibility bound
  • Strong DPI for f-divergence and for f-information
  • SDPI for total variation, Dobrushin's theorem
  • SDPI constant: general properties, binary input symmetric channels
  • Information percolation bound
• Lecture 4: SDPI and undirected information percolation.
  • Input-dependent SDPI
  • Broadcasting on trees
  • Reconstruction of random colorings on a tree
  • Undirected information percolation
  • Application: Spiked Wigner model
  • SDPI and less-noisy channel comparison
• Lecture 5: Post-SDPI and distributed estimation.
  • Tensorization of SDPI
  • Communication complexity of estimating correlations
  • Post-processing SDPI constant
  • Distributed Gaussian mean estimation
• Problem Set (for ENSAE masters students)