Research map / Learning theory and algorithms / Combinatorial and search optimization
Accelerating ERM for data-driven algorithm design using output-sensitive techniques
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives output-sensitive (output-polynomial FPT) algorithms for enumerating dual-loss pieces to run ERM in data-driven algorithm design, applied to two-part tariff and item pricing, linkage-based clustering, and sequence alignment.
Problem
Computationally efficient ERM for data-driven algorithm design with multi-parameter combinatorial algorithm families, whose piecewise-structured dual loss functions have many pieces that are costly to enumerate.
Approach
Enumerates polytopic cells induced by hyperplanes via a breadth-first search over the implicit cell adjacency graph, using Clarkson's redundancy-removal LP algorithm at each cell, with problem-specific locally relevant separators; the running time scales with the actual number of pieces rather than worst-case bounds. Extends to sums over instances and to execution trees/DAGs for clustering and seq
Key results
- Single-menu two-part tariff pricing: pieces computed in O(mK log(mK) + R_Sigma) time, improving over prior O(m^3K^3), with R_Sigma = O(m^2K).
- Two-part tariff with menu length l: output-polynomial FPT time O(R_Sigma^2 (2l)^(l+2) mK) versus prior XP runtime (mK)^O(l).
- Linkage-based clustering tuning shown FPT in dimension d, versus prior XP; for sequence alignment with d=2 linear dependence on number of pieces versus quadratic in prior work.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use output-sensitive ERM for single-menu two-part tariff pricing | Two-part tariff pricing · Two-part tariff pricing, ℓ=1 | running time: O(m^3K^3) -> O(mK\log(mK)+R_{\Sigma}) | Helped |
| Use the specialized d=2 sequence-alignment enumeration algorithm | DP-based sequence alignment · DP-based sequence alignment, d=2 | running time dependence on number of pieces: O(R^2+RT_{\textsc{dp}}) -> O(RT_{\textsc{dp}}) | Helped |
| Use output-sensitive enumeration for multidimensional linkage-based clustering | Linkage-based clustering · Linkage-based clustering, any d | complexity class | Helped |
| Use output-sensitive enumeration when the number of pieces is small | Data-driven algorithm design · Piecewise-structured dual losses with linear boundaries | running time dependence on output size | Helped |
Limitations
- Efficiency depends on the number of pieces being small; worst-case bounds can be large.
- Polynomial in d only for small constant d; running time grows as d^O(d).
- Requires problem-specific locally relevant separator subroutines for each application.
Experimental setup
Metrics: running time (theoretical) number of pieces R
Baselines: reverse search cell enumeration XP algorithm for TPT pricing (mK)^O(l) O(m^3K^3) single-menu TPT algorithm execution tree clustering approach of prior work sequence alignment partition algorithm for d=2
Builds on: Clarkson's algorithm execution tree approach for single-parameter linkage clustering data-driven algorithm design framework (delineable mechanisms) reverse search for hyperplane arrangements
Closest papers by meaning
- Accelerating data-driven algorithm selection for combinatorial partitioning problems (NeurIPS 2025 · similarity 0.86)
- Sample Complexity of Algorithm Selection Using Neural Networks and Its Applications to Branch-and-Cut (NeurIPS 2024 · similarity 0.85)
- Bayesian Optimization of Combinatorial Structures (ICML 2018 · similarity 0.84)
- On the Universal Near Optimality of Hedge in Combinatorial Settings (NeurIPS 2025 · similarity 0.82)
- Learning Augmented Exact Exponential Algorithms (NeurIPS 2026 · similarity 0.82)
- Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization (ICML 2024 · similarity 0.82)
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.