Research map / Learning theory and algorithms / Combinatorial and search optimization
Accelerated Combinatorial Search for Outlier Detection with Provable Bound on Sub-Optimality
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 |
|---|---|---|---|
| Use Chunk-A∗ with chunking (c = 0.5*k) instead of c = 1 (ablation) | Chunk-A∗ · Day1 sparse | runtime: 884s -> 607s | Helped |
| Increase chunk size from c = 1 to c = k (ablation) | Chunk-A∗ greedy variant · Sift dense | runtime: 1523s -> 65s | Helped |
| Increase chunk size from c = 1 to c = k (ablation) | Chunk-A∗ greedy variant · Sift dense | PCA error: e1 + 5.95E6 -> e1 + 5.96E6 | Hurt |
| Increase chunk size from c = 1 to c = k (ablation) | Chunk-A∗ greedy variant · YPMSD dense | runtime: 438s -> 17s | Helped |
| Increase chunk size from c = 1 to c = k (ablation) | Chunk-A∗ greedy variant · Covtype dense | runtime: 69s -> 6s | Helped |
| Increase chunk size from c = 1 to c = k (ablation) | Chunk-A∗ · TechTC01 (5:20:0.2) | PCA error: 563,313 -> 583,633 | Hurt |
| Increase chunk size from c = 1 to c = k (ablation) | Chunk-A∗ · TechTC01 (5:60:0.2) | PCA error: 110,054 -> 133,020 | Hurt |
| Increase chunk size from c = 1 to c = k (ablation) | Chunk-A∗ · TechTC01 (10:70:0.1) | PCA error: 46,461 -> 48,148 | Hurt |
| Run Algorithm 2 after Chunk-A∗ (ablation) | Chunk-A∗ · TechTC01 (5:20:0.2), c = k | PCA error: 583,633 -> 577,102 | Helped |
| Use a larger optimality parameter ϵ (ablation) | Chunk-A∗ suboptimal variant · real datasets in Table 2 | PCA error | Hurt |
| Use smaller optimality parameter ϵ (ablation) | Chunk-A∗ suboptimal variant · real datasets in Table 2 | sub-optimality bound | Helped |
| Use Chunk-A∗ with ϵ = 0 (ablation) | Chunk-A∗ · outlier detection | optimality | Helped |
Closest papers by meaning
- Outlier Detection and Robust PCA Using a Convex Measure of Innovation (NeurIPS 2019 · similarity 0.92)
- Fixed-Parameter and Approximation Algorithms for PCA with Outliers (ICML 2021 · similarity 0.89)
- Coherence Pursuit: Fast, Simple, and Robust Subspace Recovery (ICML 2017 · similarity 0.89)
- Refined Complexity of PCA with Outliers (ICML 2019 · similarity 0.89)
- Capturing the denoising effect of PCA via compression ratio (NeurIPS 2024 · similarity 0.87)
- Multi-Subspace Matrix Recovery from Permuted Data (AAAI 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.