Regularized Large Neighborhood Search

arXiv:2606.02294 · cs.LG · Submitted 2026-06-01 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: I'm Tom.

Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.

Tom: We're looking at the paper: "Regularized Large Neighborhood Search".

Jane: Here's the gist of the paper. Regularized Large Neighborhood Search introduces Regularized LNS (RLNS), which bridges large neighborhood search heuristics with block Gibbs sampling and allows for end-to-end learning without global solvers By regularizing or perturbing local subproblems, RLNS turns the LNS heuristic into an efficient MCMC sampler over the combinatorial set of feasible solutions with associated Fenchel-Young losses Under entropic regularization, RLNS is proven to perform exact block Gibbs sampling Furthermore, adjusting the number of RLNS iterations allows for interpolation between pseudolikelihood and exact maximum likelihood estimation for end-to-end learning without global solvers Proposed Framework The authors introduce RLNS as a stochastic version of LNS based on smoothed maximum operators, integrating local regularization into the LNS subproblems This is achieved by defining a family of local regularization functions from a global one via inclusion maps RLNS is then obtained by iteratively sampling from these locally regularized distributions as shown in Algorithm 2 Ergodicity of the Markov chain is guaranteed if the algorithm employs an irreducible variable selection scheme and the local update distributions are dense Entropic LNS and Gibbs Sampling When using Shannon’s negative entropy as the regularizer, RLNS implements an exact block Gibbs sampler whose stationary distribution matches the globally regularized distribution Proposition 1 shows that for any current solution and frozen subset, the locally regularized distribution matches the global regularized distribution conditioned on fixed variables This implies that in the Shannon-regularized case, the stationary distribution of RLNS matches the globally-regularized distribution Proposition 2 characterizes this exactness by showing it holds if and only if the regularizer is of the form Omega = -γHs Perturbed LNS and Tractable Updates The authors demonstrate that perturbation-based regularizers allow RLNS to remain tractable even when standard, unregularized LNS is not feasible Proposition 3 shows that exact sampling from the locally regularized distribution can be obtained via perturbed local maximization using standard LNS oracles This tractability is achieved because the local regularizer is exactly the conjugate of the local perturbed maximum function Where the Gains Come From The consistency gap between RLNS and the ideal Gibbs sampler is bounded by Proposition 8, which shows that this distance scales with the number of shared constraints between frozen and free variables For perturbation-based regularization, Proposition 10 bounds this gap by the maximum probability mass of the global regularized distribution falling outside a local neighborhood This bound is further refined by Proposition 13 to show that the consistency gap is bounded by LOmega,γγ, which is independent of the chosen y(k) and S(k) Experimental Details for κ-hot Vector Estimation In experiments on k-hot vectors, RLNS converges faster than Local Search MCMC because its acceptance rate of 100% does not suffer from updating more variables or using a low regularization strength The cut-size based bias bound suggests that variable selection schemes minimizing the number of cut constraints C∂(S(k)) will yield better convergence to the exact global regularized distribution Experimental Details for Generalized Assignment Problem For the generalized assignment problem (GAP), RLNS utilizes a randomized neighborhood system where all bins except one are frozen, and the subproblem is an exact dynamic programming solution to a 0/1 Knapsack problem The results show that higher numbers of RLNS iterations K better approximate global perturbed Fenchel-Young learning (PFY) while only requiring the solver to process a subproblem of approximately one-third the original size Experimental Details for Stochastic Vehicle Scheduling For stochastic vehicle scheduling, RLNS-1 with perturbation-based regularization outperforms blackbox differentiation (DBB) and binary cross-entropy (BCE) baselines in terms of delay cost while only requiring the solver to process a subproblem of approximately one-third the original size The local consistency gap is bounded by 1 - min y(k),S(k)π∗(Y(k)) The authors suggest that LNS can be revisited from a sampling perspective by combining local search heuristics with Metropolis-within-Gibbs MCMC samplers The perturbation-based formulation circumvents the intractability of local marginal oracles by relying solely on standard local MAP oracles The work establishes a principled Fenchel-Young counterpart to pseudolikelihood, enabling interpolation between pseudolikelihood and exact maximum likelihood estimation References

Paper summary: Tom: So, we're talking about this paper called "Regularized Large Neighborhood Search". Essentially, they're taking the Large Neighborhood Search heuristic—which is used to solve really hard combinatorial problems by making local tweaks to a current solution—and they are turning it into something that works like a Markov chain.

Jane: That sounds complicated, Tom. So what’s the big idea here for us? What problem are they trying to solve with this regularized version of Large Neighborhood Search?

Tom: They're bridging the gap between using these LNS heuristics and using block Gibbs sampling, which is a technique from MCMC methods. The core claim is that by adding regularization or perturbation to those local subproblems, you turn the LNS heuristic into an efficient sampler over all the possible solutions with Fenchel-Young losses.

Lu: What this means conceptually is they are making the LNS move in a way that respects some kind of global structure, even when you don't have a perfect global solver available. They define a family of local regularization functions starting from one global one using inclusion maps, and then they sample from these locally regularized distributions iteratively.

Meng: But if we’re talking about real-world deployment, how does this actually translate to something that runs fast on our production systems? Is it just adding a few more steps or is the whole framework fundamentally different in terms of complexity?

Jane: Well, the paper talks about two ways they regularize: entropic regularization and perturbation-based regularization. When they use Shannon’s negative entropy as the regularizer, they prove that RLNS performs exact block Gibbs sampling, meaning its stationary distribution matches what you'd get from a globally regularized problem.

Tom: That's a big win for the entropic version because it gives us an exact sampler. But then they show that perturbation-based regularizers let RLNS stay tractable even when standard, unregularized LNS would totally break down because the local determination of H0 is too messy to handle directly.

Paper summary: Lu: The paper shows that exact sampling from those locally regularized distributions can be achieved by using perturbed local maximization with standard LNS oracles, which they call a key mechanism for tractability. They achieve this because the local regularizer is exactly the conjugate of the local perturbed maximum function.

Jane: So, if we look at where these methods gain their power, the paper points out that the consistency gap between RLNS and an ideal Gibbs sampler scales with how many constraints are shared between variables that are frozen and variables that are free.

Meng: That sounds like a performance guarantee. For instance, for perturbation-based regularization, they bound this gap by looking at the maximum probability mass of the global regularized distribution falling outside a local neighborhood. This is actually quite concrete information for estimating how much error we can expect when we use this method instead of a perfect solver.

Tom: And they refined that further by showing the consistency gap is bounded by L Omega, gamma, which means it's independent of the specific choice you make for your local functions, like the y function and S function. That independence is pretty important for practical implementation because it means we don't have to perfectly tune those parts of our search every time.

Jane: That independence sounds really good. Now, let’s look at some of their experiments to see how this actually plays out on real problems, like the k-hot vector estimation. The paper suggests RLNS converges faster than standard Local Search MCMC because its acceptance rate is one hundred percent, which means you don't have to worry about updating more variables or using a low regularization strength.

Meng: A one hundred percent acceptance rate sounds fantastic for our deployment pipeline. But what about the generalized assignment problem, or GAP? They use a randomized neighborhood system where most bins are frozen, and the subproblem becomes an exact dynamic programming solution to a zero one knapsack problem.

Tom: And they found that with higher numbers of RLNS iterations K, you get better approximation of what they call the global perturbed Fenchel-Young learning. The interesting part there is that it only requires the solver to process a subproblem that's about one third the original size.

Paper summary: Jane: That reduction in problem size is huge for scaling up computation. And then there’s stochastic vehicle scheduling, where RLNS with perturbation-based regularization outperformed some blackbox differentiation and binary cross-entropy baselines in terms of delay cost, while only needing to process a subproblem about one third the original size too.

Lu: The local consistency gap in that scheduling case is bounded by one minus the minimum y function and S function times pi star of Y k, which gives us a quantifiable measure of how close we are getting to the ideal solution.

Tom: So, summarizing this paper on Regularized Large Neighborhood Search: they're showing how to use local search heuristics in a way that connects them directly to MCMC sampling, turning it into an efficient sampler over combinatorial sets with Fenchel-Young losses.

Jane: And the main implication for us is that we can now interpolate between pseudolikelihood and exact maximum likelihood estimation by adjusting how many RLNS iterations we run. This gives us flexibility in how much approximation we want to accept when a perfect global solver isn't available.

Lu: The authors suggest revisiting LNS from a sampling perspective by combining local search heuristics with Metropolis-within-Gibbs MCMC samplers, and the perturbation-based formulation is key because it lets us rely only on standard local MAP oracles instead of needing complicated marginal oracles.

Meng: I just wonder about the limitations they mentioned. They mention that for some problems, you still need an irreducible variable selection scheme and dense local update distributions to guarantee ergodicity of the Markov chain. That’s a condition we have to meet before we can trust the convergence results on real traffic data, right?

Tom: Exactly. So they set up the theory, and now our job is figuring out how robust these regularized samplers are when applied to messy, real-world combinatorial problems where those ergodicity conditions might be tricky to satisfy.

Conclusion: Tom: So, to wrap up this paper on Regularized Large Neighborhood Search, the authors are basically showing how you can take that local search idea and turn it into a proper Markov chain sampler over all possible solutions with Fenchel-Young losses.

Jane: It sounds like they’re taking a heuristic approach and making it behave like a more rigorous sampling method, which is pretty interesting if you’re not deep in combinatorial optimization.

Lu: The core idea is using local regularization—adding some kind of constraint or smoothing to the local problems—to make sure the search process moves toward the right global distribution.

Meng: If this works, it means we can use LNS when a perfect solver isn't available, just by adding these mathematical constraints to guide the search better.

Tom: Right, and they prove this works exactly for some cases using entropic regularization, which means the sampler actually hits the target distribution perfectly.

Jane: So if it hits the target distribution exactly in those cases, what about when you can't use that specific type of regularization?

Lu: They also showed that even when you use a different type of regularization called perturbation-based, you can still get exact sampling using standard local solvers, which is a big deal for practicality.

Tom: It sounds like the authors are giving us a way to bridge the gap between fast heuristics and high-quality sampling methods.

Jane: Exactly, and what this means for people using these algorithms is that they can now interpolate between getting an approximate answer quickly versus getting the exact maximum likelihood estimation.

Lu: They even suggest adjusting how many times you run the RLNS process to decide exactly how much approximation you want to accept.

Meng: So, the implication is that we’re not stuck picking one method or the other; we can tune it based on what our system needs right now.

Tom: It really frames LNS from a sampling perspective instead of just looking at it as a pure search trick.

Jane: And if this holds up in real-world scenarios, it suggests we can build more robust systems that don't need a perfect global solver to get high-quality results.

Germain Vivier-Ardisson, Laurent Demonet, Axel Parmentier, Mathieu Blondel

Google DeepMind · CERMICS Institute for Research in Machine Learning and Cognitive Science

cs.LG

Submitted: 2026-06-01

Updated: 2026-11-06

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 95/100

The gist: Regularized Large Neighborhood Search introduces Regularized LNS (RLNS), which bridges large neighborhood search heuristics with block Gibbs sampling and allows for end-to-end learning without global…

Key concepts

Regularized Large Neighborhood Search (RLNS)
RLNS is a stochastic version of LNS that integrates local regularization into the search subproblems. It uses a family of local regularizers derived from a global one to iteratively sample from locally regularized distributions, making the heuristic behave like an efficient MCMC sampler.
Entropic LNS and Gibbs Sampling
When using Shannon's negative entropy as the regularizer, RLNS implements an exact block Gibbs sampler. This means the resulting stationary distribution of the algorithm matches the globally regularized distribution, ensuring high-quality sampling.
Perturbed LNS and Tractable Updates
Perturbation-based regularizers allow RLNS to remain computationally tractable even when standard LNS is too difficult. Exact sampling from these locally regularized distributions can be achieved using standard local maximization oracles, as the local regularizer is the conjugate of the perturbed maximum function.
Consistency Gap
The consistency gap measures how close RLNS is to an ideal Gibbs sampler. For perturbation-based regularization, this gap scales with shared constraints between frozen and free variables, allowing researchers to bound its error based on specific problem structure.

Terminology

Summary

Regularized Large Neighborhood Search introduces Regularized LNS (RLNS), which bridges large neighborhood search heuristics with block Gibbs sampling and allows for end-to-end learning without global solvers By regularizing or perturbing local subproblems, RLNS turns the LNS heuristic into an efficient MCMC sampler over the combinatorial set of feasible solutions with associated Fenchel-Young losses Under entropic regularization, RLNS is proven to perform exact block Gibbs sampling Furthermore, adjusting the number of RLNS iterations allows for interpolation between pseudolikelihood and exact maximum likelihood estimation for end-to-end learning without global solvers

Proposed Framework

The authors introduce RLNS as a stochastic version of LNS based on smoothed maximum operators, integrating local regularization into the LNS subproblems This is achieved by defining a family of local regularization functions from a global one via inclusion maps RLNS is then obtained by iteratively sampling from these locally regularized distributions as shown in Algorithm 2 Ergodicity of the Markov chain is guaranteed if the algorithm employs an irreducible variable selection scheme and the local update distributions are dense

Entropic LNS and Gibbs Sampling

When using Shannon’s negative entropy as the regularizer, RLNS implements an exact block Gibbs sampler whose stationary distribution matches the globally regularized distribution Proposition 1 shows that for any current solution and frozen subset, the locally regularized distribution matches the global regularized distribution conditioned on fixed variables This implies that in the Shannon-regularized case, the stationary distribution of RLNS matches the globally-regularized distribution Proposition 2 characterizes this exactness by showing it holds if and only if the regularizer is of the form Omega = -γHs

Perturbed LNS and Tractable Updates

The authors demonstrate that perturbation-based regularizers allow RLNS to remain tractable even when standard, unregularized LNS is not feasible Proposition 3 shows that exact sampling from the locally regularized distribution can be obtained via perturbed local maximization using standard LNS oracles This tractability is achieved because the local regularizer is exactly the conjugate of the local perturbed maximum function

Where the Gains Come From

The consistency gap between RLNS and the ideal Gibbs sampler is bounded by Proposition 8, which shows that this distance scales with the number of shared constraints between frozen and free variables For perturbation-based regularization, Proposition 10 bounds this gap by the maximum probability mass of the global regularized distribution falling outside a local neighborhood This bound is further refined by Proposition 13 to show that the consistency gap is bounded by LOmega,γγ, which is independent of the chosen y(k) and S(k)

Experimental Details for κ-hot Vector Estimation

In experiments on k-hot vectors, RLNS converges faster than Local Search MCMC because its acceptance rate of 100% does not suffer from updating more variables or using a low regularization strength The cut-size based bias bound suggests that variable selection schemes minimizing the number of cut constraints C∂(S(k)) will yield better convergence to the exact global regularized distribution

Experimental Details for Generalized Assignment Problem

For the generalized assignment problem (GAP), RLNS utilizes a randomized neighborhood system where all bins except one are frozen, and the subproblem is an exact dynamic programming solution to a 0/1 Knapsack problem The results show that higher numbers of RLNS iterations K better approximate global perturbed Fenchel-Young learning (PFY) while only requiring the solver to process a subproblem of approximately one-third the original size

Experimental Details for Stochastic Vehicle Scheduling

For stochastic vehicle scheduling, RLNS-1 with perturbation-based regularization outperforms blackbox differentiation (DBB) and binary cross-entropy (BCE) baselines in terms of delay cost while only requiring the solver to process a subproblem of approximately one-third the original size The local consistency gap is bounded by 1 - min y(k),S(k)π∗(Y(k))

Conclusion

The authors suggest that LNS can be revisited from a sampling perspective by combining local search heuristics with Metropolis-within-Gibbs MCMC samplers The perturbation-based formulation circumvents the intractability of local marginal oracles by relying solely on standard local MAP oracles The work establishes a principled Fenchel-Young counterpart to pseudolikelihood, enabling interpolation between pseudolikelihood and exact maximum likelihood estimation

References

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Regularized Large Neighborhood Search (RLNS) can be used as a combinatorial layer in neural networks to output discrete decisions that satisfy complex constraints by iteratively refining a current solution through local re-optimization. This allows machine learning models to bridge the gap between differentiable outputs and NP-hard combinatorial problems without requiring access to exact global solvers.

  2. RLNS, when using perturbation-based regularization, can be implemented such that samples from the local regularized distribution can be obtained simply by performing local maximization with perturbed costs, leveraging standard LNS oracles for tractable updates. This enables end-to-end learning where the number of RLNS iterations allows interpolation between pseudolikelihood and exact maximum likelihood estimation.

  3. The system can perform block Gibbs sampling exactly when using Shannon regularization, as RLNS implements an exact block Gibbs sampler with pOmega(stheta) as a target distribution, leading to stationary distributions that match the globally regularized distribution under specific conditions.

  4. The AI system can achieve unbiased stochastic gradient estimation for local Fenchel-Young losses by executing RLNS with a single iteration (K=1), which yields an unbiased estimator of the gradient of the local Fenchel-Young loss.

  5. The system can handle constrained optimization problems like the generalized assignment problem and stochastic vehicle scheduling by using LNS subproblems that admit exact dynamic programming solutions, enabling sampling from local regularized distributions via perturbed or regularized dynamic programming.

Abstract

Operations research practitioners typically tackle NP-hard combinatorial problems using large neighborhood search (LNS), a scalable heuristic that iteratively refines a current solution by locally re-optimizing subsets of its variables. In contrast, most existing approaches for integrating combinatorial optimization layers into neural networks still assume access to an exact global solution, which is computationally intractable. We bridge this gap by introducing regularized LNS (RLNS). By regularizing or perturbing local subproblems, we turn the LNS heuristic into an efficient MCMC sampler over the combinatorial set of feasible solutions, with associated Fenchel-Young losses. Under entropic regularization, we prove that RLNS performs exact block Gibbs sampling. Furthermore, adjusting the number of RLNS iterations allows us to interpolate between pseudolikelihood and exact maximum likelihood estimation, for end-to-end learning without global solvers. We demonstrate our approach on k-subset selection, generalized assignment, and stochastic vehicle scheduling problems.

Sources

Related papers