Research map / Learning theory and algorithms / Combinatorial and search optimization
Learning Configurations for Data-Driven Multi-Objective Optimization
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 a learning-theory framework for data-driven tuning of multi-objective optimization algorithm parameters, with sample complexity bounds via piecewise-constant structure and smoothed analysis, plus a (1-1/e)-approximate ERM for Pareto volume.
Problem
Selecting tunable parameters for heuristic multi-objective optimization algorithms from sampled instances, with generalization guarantees and efficient learning; existing tuning is empirical without theory.
Approach
Bounds sample complexity of parameter configuration via the piecewise-constant structure of algorithm output in the parameter, uses smoothed analysis to reduce exponential piece counts to polynomial (or log sample complexity), and exploits submodularity of Pareto volume for a (1-1/e)-approximate PAC learner.
Key results
- On SALT shallow-light Steiner tree benchmarks, ERM-learned parameters achieve Pareto volume 0.1157 vs 0.0159 for vanilla SALT at k=1, and 0.1638 vs 0.1610 at k=11.
- Local search and MDP experiments show the number of pieces grows mildly with problem size, so generalization error stays small (e.g., below 0.2 for local search and 0.015 for MDP).
- ERM for Pareto volume is (1-1/e)-approximate PAC-learnable in polynomial time, and (1-1/e) is tight unless P=NP.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace geometric-series parameter selection with empirical risk minimization | SALT · Shallow-light Steiner tree benchmarks | Pareto volume: 0.0159 -> 0.1157 (k=1); 0.0206 -> 0.1338 (k=2); 0.0374 -> 0.1487 (k=3); 0.0557 -> 0.1529 (k=4); 0.0782 -> 0.1559 (k=5); | Helped |
Surprising findings
- Worst-case piece counts for local search and LPs can be exponential, yet smoothed analysis yields polynomial or logarithmic sample complexity.
Limitations
- Analysis restricted to two objectives in the main results; extension to d objectives is conjectured only.
- MDP smoothed analysis limited to tabular settings.
- Worst-case lower bound for MDP shadow path not proven.
Experimental setup
Datasets: real-world VLSI shallow-light Steiner tree benchmarks VLSI circuit partitioning instances (Hu et al., 2022) resource-gathering MDP (Barrett & Narayanan, 2008)
Benchmarks: VLSI shallow-light Steiner tree benchmarks
Metrics: Pareto volume generalization error number of pieces
Baselines: vanilla SALT geometric-series parameter selection
Builds on: data-driven algorithm design (Gupta & Roughgarden) smoothed analysis (Spielman & Teng) SALT (Chen & Young) Ravi-Goemans bi-criterion MST
Closest papers by meaning
- Preference-Guided Diffusion for Multi-Objective Offline Optimization (NeurIPS 2025 · similarity 0.86)
- FERERO: A Flexible Framework for Preference-Guided Multi-Objective Learning (NeurIPS 2024 · similarity 0.86)
- PSMGD: Periodic Stochastic Multi-Gradient Descent for Fast Multi-Objective Optimization (AAAI 2025 · similarity 0.85)
- Aligned Multi Objective Optimization (ICML 2025 · similarity 0.85)
- Interactive Hyperparameter Optimization in Multi-Objective Problems via Preference Learning (AAAI 2024 · similarity 0.85)
- Few for Many: Tchebycheff Set Scalarization for Many-Objective Optimization (ICLR 2025 · similarity 0.85)
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.