Program Analysis for Adaptive Data Analysis

on YouTube ↗19m

" summary

Static analysis estimates the adaptivity of while-like adaptive data analyses by building a weighted dependency graph whose node weights are reachability upper bounds, then computing an adaptivity upper bound via an SCC-based reduction and a longest-weighted-path algorithm called adapBD. The implementation AdaptFun (OCaml + Python, artifacts available) matches exact adaptivity on two-round examples, gives loose bounds on part-insensitive loop patterns, times out on deeply nested loops, and outputs mechanism recommendations (data-split vs Gaussian vs threshold).

AI-written summary · about

" chapters (10)

1. 0:00Adaptive data analysis intro
2. 2:07Controlling generation errors
3. 3:53Two-round adaptivity example
4. 6:01Programming framework for queries
5. 7:46Semantic adaptivity and graphs
6. 10:19AdaptFun tool for adaptivity
7. 13:55Limitations and alternatives
8. 15:19Mechanism selection guide
9. 16:23Conclusion and future work
10. 17:06Q&A