Divide and Learn: Multi-Objective Combinatorial Optimization at Scale
This provides a scalable and efficient alternative for multi-objective optimization problems, such as hardware-software co-design for AI accelerators, though it is incremental in its approach.
The paper tackled multi-objective combinatorial optimization by reformulating it as an online learning problem over decomposed decision spaces, achieving 80-98% of specialized solvers' performance with two to three orders of magnitude improvement in sample and computational efficiency over Bayesian optimization methods.
Multi-objective combinatorial optimization seeks Pareto-optimal solutions over exponentially large discrete spaces, yet existing methods sacrifice generality, scalability, or theoretical guarantees. We reformulate it as an online learning problem over a decomposed decision space, solving position-wise bandit subproblems via adaptive expert-guided sequential construction. This formulation admits regret bounds of $O(d\sqrt{T \log T})$ depending on subproblem dimensionality \(d\) rather than combinatorial space size. On standard benchmarks, our method achieves 80--98\% of specialized solvers performance while achieving two to three orders of magnitude improvement in sample and computational efficiency over Bayesian optimization methods. On real-world hardware-software co-design for AI accelerators with expensive simulations, we outperform competing methods under fixed evaluation budgets. The advantage grows with problem scale and objective count, establishing bandit optimization over decomposed decision spaces as a principled alternative to surrogate modeling or offline training for multi-objective optimization.