Technical Summary: Regularized Large Neighborhood Search (RLNS)

Problem Statement

Integrating combinatorial optimization layers into neural networks has emerged as a powerful paradigm for structured prediction, enabling models to output discrete decisions satisfying complex constraints. The standard formulation involves a layer defined by $\hat{y}(\theta) \triangleq \arg \max_{y \in \mathcal{Y}} \langle \theta, y \rangle$, where $\mathcal{Y}$ is a finite but combinatorially large set of feasible outputs.

The fundamental challenge in this setting is differentiability. Since the $\arg \max$ operator provides zero gradients almost everywhere, existing approaches typically rely on regularization to yield a continuous, differentiable relaxation. However, most current methods (e.g., Fenchel-Young losses, perturbed optimizers) fundamentally assume access to a global exact solver (a global MAP oracle) or a marginal oracle to compute expectations of the Gibbs distribution. For NP-hard optimization problems common in operations research, calling a global oracle at every training step is computationally intractable. Consequently, practitioners rely on scalable heuristics like Large Neighborhood Search (LNS), which iteratively refines solutions by freezing subsets of variables and re-optimizing the rest. The lack of a principled framework to use LNS as a differentiable combinatorial layer remains a critical bottleneck.

Methodology: Regularized LNS (RLNS)

The authors introduce Regularized Large Neighborhood Search (RLNS), a stochastic version of LNS that bridges the gap between scalable heuristics and differentiable optimization layers. The core idea is to regularize or perturb the local subproblems within the LNS framework, transforming the heuristic into an efficient Markov Chain Monte Carlo (MCMC) sampler over the combinatorial set of feasible solutions.

1. Framework and Local Regularization

RLNS defines a family of local regularization functions derived from a global regularizer $\Omega$. For a subset of solutions $\mathcal{Z} \subseteq \mathcal{Y}$, a local regularizer $\Omega_{\mathcal{Z}}$ is defined via an inclusion map. Instead of solving the global regularized problem, RLNS iteratively samples from locally regularized distributions $p_{\Omega_{\mathcal{Y}(k)}}((s_\theta)[\mathcal{Y}(k)])$, where $\mathcal{Y}(k)$ is the local neighborhood defined by freezing a subset of coordinates $S^{(k)}$.

2. Entropic Regularization and Block Gibbs Sampling

When the global regularizer is Shannon's negative entropy ($\Omega = -\gamma H_s$), the authors prove that RLNS performs exact block Gibbs sampling. Specifically, the locally regularized distribution matches the global regularized Gibbs distribution conditioned on the fixed variables:
$$p_{\Omega_{\mathcal{Y}(k)}}((s_\theta)[\mathcal{Y}(k)])(y) = p_{\Omega}(s_\theta)(y \mid y^{(k)}_{[S^{(k)}]})$$
Under an irreducible variable selection scheme, the stationary distribution of the RLNS iterates converges exactly to the globally regularized Gibbs distribution. This result is unique to entropic regularization; Proposition 2 characterizes Shannon's entropy as the only separable regularizer that guarantees this exactness.

3. Perturbation-Based Regularization

In scenarios where local marginal oracles (required for entropic sampling) are intractable, but local MAP oracles are available, the authors propose using perturbation-based regularization. By adding noise $\epsilon Z$ to the local scores and solving the perturbed local maximization problem, RLNS can sample from the local regularized distribution. This approach leverages standard LNS oracles (e.g., dynamic programming for knapsack subproblems) without requiring sample rejection mechanisms, unlike Metropolis-Hastings-based local search.

4. Learning and Interpolation

The paper establishes a connection between the number of RLNS iterations ($K$) and the learning objective:

• $K=1$ (Local Fenchel-Young Loss): A single step of RLNS provides an unbiased estimator for a local Fenchel-Young loss. In the entropic setting, this recovers the pseudolikelihood (composite likelihood) objective, which maximizes the likelihood of subsets of variables conditioned on the rest.
• $K \to \infty$ (Global Fenchel-Young Loss): As iterations increase, the estimator converges to the gradient of the global Fenchel-Young loss, approximating exact maximum likelihood estimation.
  This allows practitioners to interpolate between pseudolikelihood and exact maximum likelihood estimation by tuning $K$, enabling end-to-end learning without global solvers.

Key Contributions

1. RLNS Framework: Introduction of a stochastic, regularized version of LNS that integrates local regularization into LNS subproblems, creating a differentiable combinatorial layer.
2. Theoretical Equivalence: Proof that under entropic regularization, RLNS implements an exact block Gibbs sampler whose stationary distribution matches the globally regularized Gibbs distribution.
3. Tractability via Perturbation: Demonstration that perturbation-based regularization allows RLNS to utilize standard local MAP oracles, ensuring tractability whenever standard LNS is tractable.
4. Interpolation of Learning Paradigms: Theoretical and empirical demonstration that the number of RLNS iterations allows interpolation between pseudolikelihood and exact maximum likelihood estimation.
5. Empirical Validation: Evaluation on three distinct problems:
   • $\kappa$-hot vectors: Controlled estimation task validating convergence against ground truth.
   • Generalized Assignment Problem (GAP): Learning to predict assignments where local subproblems are 0/1 Knapsack problems.
   • Stochastic Vehicle Scheduling: A real-world benchmark where RLNS-1 outperforms blackbox differentiation and binary cross-entropy baselines while requiring significantly less computation than global solvers.

Results

• Convergence: In the $\kappa$-hot vector experiment, RLNS converges faster than Local Search MCMC and achieves lower Mean Absolute Error (MAE) than Monte-Carlo estimation for the same number of samples, particularly when a high proportion of variables are kept free.
• Scalability: In the GAP experiments, local MAP oracles used by RLNS are orders of magnitude faster than global Mixed Integer Linear Programming (MILP) solvers, especially as problem scale increases.
• Performance: In stochastic vehicle scheduling, RLNS-1 (using a single iteration) nearly matches the performance of global perturbed Fenchel-Young (PFY) learning in terms of delay cost, while only requiring the solver to process subproblems of approximately one-third the original size. It significantly outperforms Blackbox Differentiation (DBB) and Binary Cross-Entropy (BCE) baselines.
• Bias Analysis: Theoretical bounds show that the approximation error scales with the number of shared constraints (cut constraints) between frozen and free variables, motivating variable selection schemes that minimize these cross-dependencies (e.g., min-cut selection).

Significance and Claims

The paper claims to bridge a critical gap in the literature by enabling the use of highly scalable heuristics (LNS) as differentiable layers in neural networks, removing the reliance on computationally intractable global solvers. By establishing a rigorous connection between LNS and Gibbs sampling, the work provides a principled framework for differentiating through combinatorial optimization layers using only local oracles. The authors position RLNS as a practical solution for end-to-end learning in structured prediction tasks involving NP-hard constraints, offering a tunable trade-off between computational cost and statistical accuracy via the iteration count $K$.