Clément Canonne

COLT 2021 Tutorial: Statistical Inference in Distributed or Constrained Settings

Techniques and Recipes

⏰ Tutorial time: August 4, 18:30–21:30 Mountain Time

The goal of this tutorial is to provide the attendees with an overview of techniques and recipes for distributed estimation and testing under constraints. Over the recent years, many papers have obtained both upper and lower bounds for statistical estimation under communication, local privacy, and memory constraints: these questions are motivated by applications in machine learning and distributed computing, and are at the intersection of theoretical computer science, machine learning, statistics, and information theory.

This tutorial will provide a primer of those techniques, aiming to give both an understanding of the underlying challenges and ideas, and “plug-and-play” general recipes the attendees could then apply to the problems of their choice. Our focus will be on establishing lower bounds for statistical estimation, in particular for parameter estimation (single- and high-dimensional) and testing. The tutorial will cover various models: nonadaptive, sequentially adaptive, blackboard model, and memory-constrained settings; with applications to high-dimensional parameter estimation and testing.

Presenters: Jayadev Acharya, Clément Canonne, and Himanshu Tyagi

Recitation tutors: Aditya Vikram Singh, Ziteng Sun

• 🧑‍🏫 Tutorial
  • Part 0 (15mn): Setting the stage: scope, models [📄 slides for parts 0 and 1, 🎞️ video]
  • Part 1 (45mn): Lower bounds for learning/estimation problems over discrete univariate domains, and some general upper bound techniques
  • Part 2 (45mn): Lower bounds for learning/estimation problems: generalisation to high dimensions [📄 slides, 🎞️ video]
• 📝 Recitation (45mn) (exercises, solutions)
  • Mean estimation under local privacy or communication constraints: upper and lower bounds for product and Gaussian distributions
  • Extra exercises and applications: “Simulate-and-Infer,” some sanity checks, and miscellaneous useful tricks.

📚 Bibliography: available here (BibTex source)