Metraipolis › archive › dc_5dd620340178

Program Analysis for Adaptive Data Analysis — arXiv:2608.19575

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.19575
License (as archived)
CC0-1.0
Archived
2026-10-18T12:08:46.196Z
SHA-256 of the archived text
e10da4418e142249b5655f33b23acaa05c11eeaefa9d48390359c475e01581a5
Stable URL of this page
https://metraipolis.com/documento/dc_5dd620340178

How to cite

Program Analysis for Adaptive Data Analysis — arXiv:2608.19575 — arXiv (en), https://arxiv.org/abs/2608.19575 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_5dd620340178 (Metraipolis archive dc_5dd620340178, sha256 e10da4418e142249b5655f33b23acaa05c11eeaefa9d48390359c475e01581a5)
BibTeX
@misc{dc5dd620340178,
  title = {Program Analysis for Adaptive Data Analysis — arXiv:2608.19575},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.19575},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_5dd620340178; sha256 e10da4418e142249b5655f33b23acaa05c11eeaefa9d48390359c475e01581a5},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.19575. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Data analyses are usually designed to identify some property of the population from which the data are drawn, generalizing beyond the specific data sample. For this reason, data analyses are often designed to produce a low generalization error, so that the result of an analysis on sample data does not differ too much from the result one would achieve over the entire population. An adaptive data analysis can be seen as a process composed of multiple queries interrogating some data, where the choice of which query to run next may rely on the results of previous queries. The generalization error of each individual query can be controlled using well-established statistical techniques. However, when queries are arbitrarily composed, errors can propagate through the chain of queries and lead to high generalization error. To address this issue, several techniques guarantee bounds not only on single queries but also on composed analyses. The choice of technique often depends on the chain of queries that an adaptive data analysis can generate. In this work, we consider adaptive data analyses implemented as while-like programs and design a program analysis to help identify which technique to use to control their generalization errors. More specifically, we formalize the intuitive notion of adaptivity as a quantitative property of programs. Based on this definition, we design a program analysis for soundly approximating this quantity. The analysis represents the data analysis as a weighted dependency graph, where weights upper-bound how often variables can be reached, and uses a path-search strategy to upper-bound adaptivity. We implement our program analysis and show that it can analyze several concrete data analyses with different adaptivity structures.

Tema degli esploratori: calcolo e infrastrutture (retro-catalogo arXiv: annunci del 2026-08-21 in cs.PL).
Categorie arXiv: Programming Languages (cs.PL).
Pagina del lavoro: https://arxiv.org/abs/2608.19575 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-18T12:07:53.959Z dalla pagina https://arxiv.org/catchup/cs.PL/2026-08-21?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).