Research map / Learning theory and algorithms / Sample complexity
Divide and Conquer Dynamic Programming: An Almost Linear Time Change Point Detection Methodology in High Dimensions
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (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 |
|---|---|---|---|
| Add the PLR local-refinement conquer step after the divide step (ablation) | DCDP · Mean model; synthetic simulations | Localization error | Helped |
| Use DCDP instead of Inspect | Mean model, n = 200, p=100, K =3, δ = 5 · High-dimensional mean shift | Hausdorff distance: 0.40 (3.50) -> 0.00 (0.00) | Helped |
| Use DCDP instead of vanilla DP | Linear regression model, n = 200, p=100, K =3, δ = 5 · High-dimensional regression coefficient shifts | Time: 220.3s (16.8) -> 18.4s (1.1) | Helped |
| Use DCDP instead of vanilla DP | Linear regression model, n = 200, p=100, K =3, δ = 5 · High-dimensional regression coefficient shifts | Hausdorff distance: 0.01 (0.10) -> 0.13 (0.39) | Hurt |
| Use DCDP instead of CF | Gaussian graphical model, n = 400, p=10, K =3 · Precision matrix shifts | Hausdorff distance: 5.54 (14.71) -> 0.42 (0.64) | Helped |
Closest papers by meaning
- TSB-SEG: A Systematic Time-Series Segmentation Benchmark (NeurIPS 2026 · similarity 0.89)
- Inferring Change Points in High-Dimensional Linear Regression via Approximate Message Passing (ICML 2024 · similarity 0.86)
- The Sample Complexity of Multiple Change Point Identification under Bandit Feedback (NeurIPS 2026 · similarity 0.85)
- Optimal Online Change Detection via Random Fourier Features (NeurIPS 2025 · similarity 0.85)
- Non-parametric Online Change Point Detection on Riemannian Manifolds (ICML 2024 · similarity 0.84)
- FM-ChangeNet: Learning Change through Pathwise Feature Transport (NeurIPS 2026 · similarity 0.84)
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.