Research map / Learning theory and algorithms / Sample complexity
Optimistic Search: Change Point Estimation for Large-scale Data via Adaptive Logarithmic Queries
Solt Kovács, Housen Li, Lorenz Haubner, Axel Munk, Peter Bühlmann
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 advanced instead of naive optimistic search on unbalanced segments (ablation) | optimistic search · Single univariate mean change, sigma=1, n=5000 | mean absolute error: 1948.79 -> 48.08 | Improved |
| use advanced instead of naive optimistic search on unbalanced segments (ablation) | optimistic search · Single univariate mean change, sigma=0.5, n=5000 | mean absolute error: 1021.12 -> 3.92 | Improved |
| use naive optimistic search instead of advanced on balanced segments | optimistic search · Single univariate mean change, sigma=1.5, n=200 | mean absolute error: 60.82 -> 23.77 | Improved |
| combine naive and advanced optimistic search (ablation) | optimistic search · Single univariate mean change, sigma=1, n=500 | mean absolute error: 26.97 -> 21.06 | Improved |
| combine naive and advanced optimistic search (ablation) | optimistic search · Single univariate mean change, sigma=1, n=5000 | mean absolute error: 48.08 -> 51.94 | No clear effect |
| replace full grid search by combined optimistic search | change point search · Single univariate mean change, sigma=1, n=5000 | average number of evaluations: 5099 -> 58.71 | Improved |
| replace full grid search by combined optimistic search | change point search · Single univariate mean change, sigma=1, n=5000 | mean absolute error: 38.34 -> 51.94 | Hurt |
| replace full grid search by advanced optimistic search | change point search · Single univariate mean change, sigma=0.5, n=5000 | average number of evaluations vs error: 3.05 -> 3.92 | Mixed |
| use optimistic search within SeedBS | SeedBS · Blocks signal, 11 change points, n=2048 | Hausdorff distance | No clear effect |
| use optimistic search within binary segmentation | BS · Changing Gaussian graphical model | computation time speedup: factor 30 | Improved |
| use optimistic search within WBS | WBS · Changing Gaussian graphical model | computation time speedup: factor 35 | Improved |
| use optimistic search within SeedBS | SeedBS · Changing Gaussian graphical model | computation time speedup: factor 10--14 | Improved |
Closest papers by meaning
- Bayesian Model Selection for Change Point Detection and Clustering (ICML 2018 · similarity 0.90)
- Divide and Conquer Dynamic Programming: An Almost Linear Time Change Point Detection Methodology in High Dimensions (ICML 2023 · similarity 0.89)
- Reliever: Relieving the Burden of Costly Model Fits for Changepoint Detection (JMLR 2025 · similarity 0.89)
- Inferring Change Points in High-Dimensional Linear Regression via Approximate Message Passing (ICML 2024 · similarity 0.88)
- The Sample Complexity of Multiple Change Point Identification under Bandit Feedback (NeurIPS 2026 · similarity 0.86)
- Optimal Online Change Detection via Random Fourier Features (NeurIPS 2025 · similarity 0.86)
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.
