# Generalization Bounds of Surrogate Policies for Combinatorial Optimization Problems

arXiv: https://arxiv.org/abs/2407.17200 · HTML: https://mlsanity.com/paper/2407.17200/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 49 references that are in the map.
- First posted on arXiv 24 Jul 2024.

## Builds on (most cited first, 22 of 22)

- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Smart "Predict, then Optimize"](https://mlsanity.com/paper/1710.08005/) (2017)
- [Differentiation of Blackbox Combinatorial Solvers](https://mlsanity.com/paper/1912.02175/) (2019)
- [Learning with Fenchel-Young Losses](https://mlsanity.com/paper/1901.02324/) (2019)
- [Best Subset Selection via a Modern Optimization Lens](https://mlsanity.com/paper/1507.03133/) (2015)
- [A Survey of Contextual Optimization Methods for Decision Making under Uncertainty](https://mlsanity.com/paper/2306.10374/) (2023)
- [Learning with Differentiable Perturbed Optimizers](https://mlsanity.com/paper/2002.08676/) (2020)
- [A PAC Approach to Application-Specific Algorithm Selection](https://mlsanity.com/paper/1511.07147/) (2015)
- [Generalization Bounds in the Predict-then-Optimize Framework](https://mlsanity.com/paper/1905.11488/) (2019)
- [Non-parametric Models for Non-negative Functions](https://mlsanity.com/paper/2007.03926/) (2020)
- [A General Framework for Consistent Structured Prediction with Implicit Loss Embeddings](https://mlsanity.com/paper/2002.05424/) (2020)
- [A Consistent Regularization Approach for Structured Prediction](https://mlsanity.com/paper/1605.07588/) (2016)
- [Learning with Combinatorial Optimization Layers: a Probabilistic Approach](https://mlsanity.com/paper/2207.13513/) (2022)
- [Integrated Conditional Estimation-Optimization](https://mlsanity.com/paper/2110.12351/) (2021)
- [Finding Global Minima via Kernel Approximations](https://mlsanity.com/paper/2012.11978/) (2020)
- [SurCo: Learning Linear Surrogates For Combinatorial Nonlinear Optimization Problems](https://mlsanity.com/paper/2210.12547/) (2022)
- [A General Theory for Structured Prediction with Smooth Convex Surrogates](https://mlsanity.com/paper/1902.01958/) (2019)
- [Learning-based Online Optimization for Autonomous Mobility-on-Demand Fleet Control](https://mlsanity.com/paper/2302.03963/) (2023)
- [Combinatorial Optimization enriched Machine Learning to solve the Dynamic Vehicle Routing Problem with Time Windows](https://mlsanity.com/paper/2304.00789/) (2023)
- [Combinatorial Optimization and Machine Learning for Dynamic Inventory Routing](https://mlsanity.com/paper/2402.04463/) (2024)
- [Learning to solve the single machine scheduling problem with release times and sum of completion times](https://mlsanity.com/paper/2101.01082/) (2021)
- [Second order conditions to decompose smooth functions as sums of squares](https://mlsanity.com/paper/2202.13729/) (2022)

## Built on by (most cited first, 3 of 3)

- [Primal-dual algorithm for contextual stochastic combinatorial optimization](https://mlsanity.com/paper/2505.04757/) (2025)
- [Combinatorial Optimization Augmented Machine Learning](https://mlsanity.com/paper/2601.10583/) (2026)
- [DistrictNet: Decision-aware learning for geographical districting](https://mlsanity.com/paper/2412.08287/) (2024)

## Abstract (arXiv)

Many real-world decision problems require solving, again and again, combinatorial optimization instances drawn from a common distribution. A recent line of structured learning methods exploits this regularity by learning policies that pair a statistical model with a tractable combinatorial oracle, instead of solving each instance independently. Training such policies is notoriously difficult, however: the resulting empirical risk is piecewise constant in the model parameters, which hinders gradient-based optimization, and only a few theoretical guarantees have been provided so far. We address this issue by analyzing smoothed (perturbed) policies: adding controlled random perturbations to the direction used by the linear oracle yields a differentiable surrogate risk and improves generalization. Our main contribution is a generalization bound that decomposes the excess risk into (mathiti) perturbation bias, (mathitii) statistical estimation error, and (mathitiii) optimization error. The perturbation bias is controlled by the fan-crossing probability, a new geometric quantity measuring the likelihood that a perturbation changes the oracle solution. We introduce two complementary conditions to bound it--the Uniformly Bounded Density (UBD) property, yielding a sharp O(λ) bias, and the weaker Uniform Weak moment (UW) property, yielding a sub-linear bound--both capturing the geometric interaction between the statistical model and the normal fan of the feasible polytope. The statistical estimation error is controlled via a uniform deviation bound over the policy class, with rate O(1/(λ√n)) that scales inversely in the smoothing parameter. Concerning the optimization error, we exploit kernel Sum-of-Squares methods to mitigate the curse of dimensionality of global optimization.