Overcoming the Label Generation Bottleneck in Neural Optimization

486 concepts364 papers2 proposals

Deep learning has achieved remarkable success by mimicking human-labeled datasets. However, when applying supervised learning to combinatorial optimization and mathematical modeling, we immediately hit a fundamental paradox. To train a neural network to find optimal solutions for NP-hard or highly complex problems, we must first provide it with a massive dataset of ground-truth optimal labels. But generating these labels requires running classical exact solvers, which scale exponentially with problem size.

As noted by Oriol Vinyals et al. in their seminal work on Pointer Networks, the scalability of deep learning models for algorithmic problems is inherently bounded by the very solvers used to create their training data. If we can only compute optimal labels for small or simple instances, the model never learns how to navigate the intricate landscapes of large-scale, real-world problems. This creates a severe label generation bottleneck: the data needed to train a neural solver is just as computationally expensive to obtain as the solutions the model is intended to find.

Unsupervised Loss: Letting the Objective Function Be the Teacher

How do we break this circle? The key insight is that while finding an optimal solution is hard, evaluating the quality and validity of a given solution is often computationally cheap. Optimization problems come equipped with mathematical definitions: an objective function to minimize or maximize, and a set of constraints to satisfy. Instead of training a network to match a pre-computed target, we can train it to minimize the objective function directly using differentiable formulations.

Consider the Traveling Salesman Problem (TSP). Instead of using expensive ground-truth routes, Andis Draguns et al. demonstrated in Unsupervised Training for Neural TSP Solver that the mathematical constraints of the problem can be transformed into a differentiable loss function. By penalizing invalid tours and rewarding shorter path lengths, the network learns the underlying structure of the problem without ever seeing a single optimal example.

For highly constrained spaces where simple penalties fail, researchers leverage classical optimization theory within neural architectures. Pascal Van Hentenryck et al. introduced this paradigm in Self-Supervised Primal-Dual Learning for Constrained Optimization. Instead of relying on pre-solved instances, they train two networks simultaneously to mimic the Augmented Lagrangian Method—one network predicts the primal solution, while the other updates instance-specific constraint penalties. This self-supervised loop ensures feasibility and near-optimality without requiring hundreds of hours of data generation. Similarly, Carla P Gomes et al. in Unsupervised Learning for Quadratic Assignment showed that minimizing the objective function directly allows neural networks to "warm-start" traditional search heuristics, bypassing the need for explicit supervision entirely.

Inverting the Generation Pipeline: Bidirectional and Dual Synthesis

When unsupervised learning is insufficient—such as when training models to translate natural language descriptions into mathematical optimization models—we face a different flavor of data scarcity. Real-world optimization problems are often proprietary, and verifying mathematical consistency requires rare domain expertise.

To circumvent this, researchers invert the problem generation pipeline. Instead of collecting natural language problems and paying experts to formulate them, Hongliang Lu et al. proposed OptMATH, a bidirectional data synthesis framework. The framework generates valid mathematical formulations first, and then back-translates them into natural language descriptions. Because the ground-truth mathematical structure is known from the start, the framework can use solver-based rejection sampling to rigorously verify consistency, synthesizing high-quality datasets at scale.

A parallel approach works for structural optimization problems like Mixed-Integer Linear Programming (MILP). In DIG-MILP, Haoyu Peter Wang et al. leveraged mathematical duality to generate synthetic MILP instances. By constructing problems from their dual representations, the generator provides a mathematical feasibility guarantee, ensuring that every generated instance is bounded and solvable without needing to run an expensive solver to verify it.

When labels are scarce but unlabeled problem instances are abundant, self-supervised representation learning can bridge the gap. Haonan Duan demonstrated in Augment with Care: Contrastive Learning for Combinatorial Problems that by designing label-preserving augmentations, a model can learn powerful structural features from unlabeled combinatorial instances. This approach matches supervised performance while requiring 100x fewer labels, effectively mitigating the dependency on exhaustive solvers during the training phase.

Online Adaptation: Eliminating Offline Data Entirely

The ultimate way to resolve the label generation bottleneck is to abandon offline training datasets altogether. Instead of training a model on thousands of past examples hoping it generalizes to a new one, models can learn and adapt online, directly on the instance they are trying to solve.

Junyang Cai et al. implemented this concept in Balans for Mixed-Integer Programming. By framing the choice of search heuristics as a Multi-Armed Bandit problem, the solver adaptively learns which strategy works best for a specific instance on the fly. This eliminates the brittle dependency on historical datasets and allows the system to tackle novel, highly complex instances where optimal solutions are entirely unknown.

For dynamic environments where optimization problems evolve over time, Yiqiao Liao developed Learning for Dynamic Combinatorial Optimization without Training Data. Rather than relying on massive pre-solved trajectories, this framework uses a training-free "shrink and perturb" strategy to adapt neural network parameters between consecutive problem snapshots. By exploiting the temporal continuity of the problem space, it achieves high-quality solutions up to 60x faster than traditional methods without requiring a single byte of offline training data.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 377 papers
  2. Version 1 · 2026-10-04 · 404 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_label_generation_bottleneck_f384bfbc,
  title = {label generation bottleneck},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/label-generation-bottleneck/rdr_f384bfbca6134fc1819fe278c4c04ce9},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 2, frozen text):

@misc{lacuna_label_generation_bottleneck_f384bfbc_v2,
  title = {label generation bottleneck},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/label-generation-bottleneck/rdr_f384bfbca6134fc1819fe278c4c04ce9/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake