Research map / Learning theory and algorithms / Sample complexity
Worst-Case Analysis for Randomly Collected Data
Justin Chen, Gregory Valiant, Paul Valiant
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use SDP-derived estimator instead of inverse proportional reweighting | SDP Alg · Importance sampling, worst-case bound | expected squared error: 0.101 -> 0.053 | Improved |
| Use SDP-derived estimator instead of subgroup estimation | SDP Alg · Importance sampling, worst-case bound | expected squared error: 0.122 -> 0.053 | Improved |
| Use SDP Alg instead of subgroup estimation when values are constant | SDP Alg · Importance sampling, constant values | expected squared error: 0.018 -> 0.051 | Hurt |
| Use SDP Alg instead of subgroup estimation on intergroup variance | SDP Alg · Importance sampling, intergroup variance | expected squared error: 0.018 -> 0.053 | Hurt |
| Use SDP Alg instead of subgroup estimation on intragroup variance | SDP Alg · Importance sampling, intragroup variance | expected squared error: 0.121 -> 0.052 | Improved |
| Use SDP Alg instead of inverse proportional reweighting on constant values | SDP Alg · Importance sampling, constant values | expected squared error: 0.100 -> 0.051 | Improved |
| Use SDP Alg instead of sample mean on spatially-correlated values | SDP Alg · Snowball sampling, spatially-correlated values | expected squared error: 2--4x reduction | Improved |
| Use SDP Alg instead of sample mean on worst-case values | SDP Alg · Snowball sampling, worst-case values | expected squared error: 4--7x reduction | Improved |
| Use SDP Alg instead of mean of most recent w points | SDP Alg · Selective prediction, worst-case bound | expected squared error: 2--3x reduction | Improved |
Closest papers by meaning
- Faster Algorithms and Constant Lower Bounds for the Worst-Case Expected Error (NeurIPS 2021 · similarity 0.87)
- Truthful Univariate Estimators (ICML 2016 · similarity 0.83)
- Statistical-Computational Trade-offs for Density Estimation (NeurIPS 2024 · similarity 0.82)
- Towards a statistical theory of data selection under weak supervision (ICLR 2024 · similarity 0.82)
- Identification and Estimation for Nonignorable Missing Data: A Data Fusion Approach (ICML 2024 · similarity 0.81)
- Robust Estimation Under Heterogeneous Corruption Rates (NeurIPS 2025 · similarity 0.81)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
