Research map / Learning theory and algorithms / Combinatorial and search optimization
Cakewalk Sampling
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 the scaled empirical CDF surrogate, uniform on [-1,1], rather than the unscaled empirical CDF (ablation) | Cakewalk with AdaGrad · DIMACS graphs | rate of locally optimal solutions: 0.164 -> 0.835 | Helped |
| Use the scaled empirical CDF surrogate, uniform on [-1,1], rather than the unscaled empirical CDF (ablation) | Cakewalk with AdaGrad · DIMACS graphs | rate of inclusion maximal cliques: 0.175 -> 0.912 | Helped |
| Use the scaled empirical CDF surrogate rather than the unscaled empirical CDF (ablation) | Cakewalk with AdaGrad · DIMACS graphs | largest-returned-clique to largest-known-clique ratio: 0.161 -> 0.756 | Helped |
| Use a predetermined-distribution surrogate objective rather than REINFORCE-style raw objective weighting | Adaptive samplers with AdaGrad · DIMACS graphs | rate of locally optimal solutions: 0.427 -> 0.835 | Helped |
| Fix the objective-weight distribution rather than merely normalize objective values with an estimated z-score | Adaptive samplers · DIMACS graphs | rate of locally optimal solutions: 0.427 -> 0.835 | Helped |
| Use the OCE 0.01 percentile surrogate instead of Cakewalk's scaled empirical CDF | Adaptive samplers with AdaGrad · DIMACS graphs | rate of locally optimal solutions: 0.077 -> 0.835 | Hurt |
| Use the unscaled empirical CDF surrogate rather than the scaled, centered version (ablation) | Cakewalk with AdaGrad · DIMACS graphs | rate of locally optimal solutions: 0.835 -> 0.164 | Hurt |
| Use Adam rather than AdaGrad for the Cakewalk update (ablation) | Cakewalk with scaled empirical CDF · DIMACS graphs | rate of locally optimal solutions: 0.835 -> 0.753 | Hurt |
| Use Adam rather than AdaGrad for the Cakewalk update (ablation) | Cakewalk with scaled empirical CDF · DIMACS graphs | best-sample to total-samples ratio: 0.657 -> 0.619 | Helped |
| Use Cakewalk to initialize Voronoi iteration rather than run Voronoi iteration alone | Voronoi iteration on k-medoids · k-medoids, 38 datasets, k=10 | objective averaged ratio: 1.6373 -> 1.0002 | Helped |
| Use Cakewalk to initialize Voronoi iteration rather than Cakewalk alone | Cakewalk on k-medoids · k-medoids, 38 datasets, k=10 | objective evaluations averaged ratio: 4352.3860 -> 1764.1380 | Helped |
Closest papers by meaning
- Revisiting Sampling for Combinatorial Optimization (ICML 2023 · similarity 0.90)
- Bayesian Optimization of Functions over Node Subsets in Graphs (NeurIPS 2024 · similarity 0.88)
- Differentiable Quadratic Optimization For the Maximum Independent Set Problem (ICML 2025 · similarity 0.87)
- COMBHelper: A Neural Approach to Reduce Search Space for Graph Combinatorial Problems (AAAI 2024 · similarity 0.87)
- Approximation algorithms for combinatorial optimization with predictions (ICLR 2025 · similarity 0.87)
- Accelerating data-driven algorithm selection for combinatorial partitioning problems (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.