# Primal-dual algorithm for contextual stochastic combinatorial optimization

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 30 references that are in the map.
- First posted on arXiv 7 May 2025.

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

- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Coordinate Descent Algorithms](https://mlsanity.com/paper/1502.04759/) (2015)
- [Learning with Fenchel-Young Losses](https://mlsanity.com/paper/1901.02324/) (2019)
- [A Survey of Contextual Optimization Methods for Decision Making under Uncertainty](https://mlsanity.com/paper/2306.10374/) (2023)
- [Stochastic Mirror Descent on Overparameterized Nonlinear Models: Convergence, Implicit Regularization, and Generalization](https://mlsanity.com/paper/1906.03830/) (2019)
- [Learning with Combinatorial Optimization Layers: a Probabilistic Approach](https://mlsanity.com/paper/2207.13513/) (2022)
- [Stochastic Mirror Descent: Convergence Analysis and Adaptive Variants via the Mirror Stochastic Polyak Stepsize](https://mlsanity.com/paper/2110.15412/) (2021)
- [Stochastic Block Mirror Descent Methods for Nonsmooth and Stochastic Optimization](https://mlsanity.com/paper/1309.2249/) (2013)
- [Combinatorial Optimization enriched Machine Learning to solve the Dynamic Vehicle Routing Problem with Time Windows](https://mlsanity.com/paper/2304.00789/) (2023)
- [Unifying mirror descent and dual averaging](https://mlsanity.com/paper/1910.13742/) (2019)
- [Learning structured approximations of combinatorial optimization problems](https://mlsanity.com/paper/2107.04323/) (2021)
- [Gradient descent with a general cost](https://mlsanity.com/paper/2305.04917/) (2023)
- [Generalization Bounds of Surrogate Policies for Combinatorial Optimization Problems](https://mlsanity.com/paper/2407.17200/) (2024)

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

- [Structured Reinforcement Learning for Combinatorial Decision-Making](https://mlsanity.com/paper/2505.19053/) (2025)
- [Combinatorial Optimization Augmented Machine Learning](https://mlsanity.com/paper/2601.10583/) (2026)
- [Decision-Focused On-Policy Learning for Contextual Linear Optimization with Partial Feedback](https://mlsanity.com/paper/2606.01081/) (2026)
- [Regularized Large Neighborhood Search](https://mlsanity.com/paper/2606.02294/) (2026)

## Abstract (arXiv)

This paper introduces a novel approach to contextual stochastic optimization, integrating operations research and machine learning to address decision-making under uncertainty. Traditional methods often fail to leverage contextual information, which underscores the necessity for new algorithms. In this study, we utilize neural networks with combinatorial optimization layers to encode policies. Our goal is to minimize the empirical cost, which is estimated from past data on uncertain parameters and contexts. To that end, we present a surrogate learning problem and a generic primal-dual algorithm that is applicable to various combinatorial settings in stochastic optimization. Our approach extends classic Fenchel--Young loss results and introduces a new regularization method using sparse perturbations on the distribution simplex. This allows for tractable updates in the original space and can accommodate diverse objective functions. We establish sublinear convergence for the exact linear-parametric version and provide a bound on the non-optimality of the resulting policy in terms of the empirical cost. Experiments on three contextual stochastic optimization problems show that our algorithm is efficient and scalable, achieving performance comparable to state-of-the-art baselines with significantly reduced computational requirements.