SurCo: Learning Linear Surrogates For Combinatorial Nonlinear Optimization Problems
This addresses the problem of slow and inefficient optimization for nonlinear combinatorial problems in fields like machine learning and engineering, offering a novel hybrid approach that is incremental in combining gradient-based methods with linear solvers.
The paper tackles the challenge of efficiently solving combinatorial optimization problems with nonlinear cost functions by proposing SurCo, which learns linear surrogate costs for use in existing combinatorial solvers, resulting in better solutions faster than state-of-the-art and domain expert approaches in real-world applications like embedding table sharding and nonlinear route planning.
Optimization problems with nonlinear cost functions and combinatorial constraints appear in many real-world applications but remain challenging to solve efficiently compared to their linear counterparts. To bridge this gap, we propose $\textbf{SurCo}$ that learns linear $\underline{\text{Sur}}$rogate costs which can be used in existing $\underline{\text{Co}}$mbinatorial solvers to output good solutions to the original nonlinear combinatorial optimization problem. The surrogate costs are learned end-to-end with nonlinear loss by differentiating through the linear surrogate solver, combining the flexibility of gradient-based methods with the structure of linear combinatorial optimization. We propose three $\texttt{SurCo}$ variants: $\texttt{SurCo}-\texttt{zero}$ for individual nonlinear problems, $\texttt{SurCo}-\texttt{prior}$ for problem distributions, and $\texttt{SurCo}-\texttt{hybrid}$ to combine both distribution and problem-specific information. We give theoretical intuition motivating $\texttt{SurCo}$, and evaluate it empirically. Experiments show that $\texttt{SurCo}$ finds better solutions faster than state-of-the-art and domain expert approaches in real-world optimization problems such as embedding table sharding, inverse photonic design, and nonlinear route planning.